用於安全儲存的同態模組化約簡

我的問題與Homomorphic modulo非常相似，但我想給出一個在外包環境中進行操作的上下文。

是否有任何特定的同態密碼方案可以同時進行模減法和減法運算。

認為 $ Enc(x) $ 的密文 $ x $ 在同態加密之後，和 $ mod $ 是模減運算。

$$ (Enc(x)-Enc(a))\ mod\ Enc(N) == (x-a)\ mod\ N $$ 儘管 $ x $ , $ a $ 和 $ N $ 都是自然數。和 $ N $ 大於 $ x $ 和 $ a $ .

我知道 $ mod $ 可以轉化為額外的 ( $ + $ ) 和乘法 ( $ * $ ) 操作，這是 HE 支持的操作。但我不希望這些因素暴露給進行此類操作的人，例如 $ Server $ .

例如

$ (6-5)\ mod\ 10 = 1+(010)=1 $ , $ (4-5)\ mod\ 10 = -1+(110)=9 $

但是當一個 $ Server $ 被分配這樣做，像這樣的因素 $ 0 $ 和 $ 1 $ 這裡暴露了。

所以我想知道，是否有任何特定的HE方案可以直接進行模組化減少操作，或者有沒有任何解決方案可以保持 $ Server $ 從知道這些因素？

您的模運算不需要真正的除法，因為您離模數不遠。

使用TFHE或HELib庫用 2 的補碼表示您的數字。在這種情況下，您的數字在 FHE 中使用位算術，即您將擁有一個密文 $ {c_0,c_1,\ldots,c_{k-1}} $ 為了 $ k $ 位數。

你需要什麼手術？

• $ Add(A,B) $ : 同態加法
• $ Sub(A,B) = Add(A,-B) $ : 通過使用同態減法 $ Add $ .
• $ MSB(A) $ : 返回密文的最高位
• 比較 $ Comp(A,B) = MSB(Sub(A,B)) = MSN(Add(A,-B)) $
• If ：對於單個加密位的單個 if else 情況 $ S $ ,$$ I = S \cdot A + S’ \cdot B $$在哪裡 $ \cdot $ 是個 $ \text{AND} $ 手術。根據價值 $ S $ , $ I $ 或者是 $ A $ 或者 $ B $ .

有關這些操作的更多詳細資訊，請參見先前關於 FHE 中常見電路的答案。

讓 $ A = Enc_{pk}(A) $ , $ B=Enc_{pk}(b) $ ， 和 $ N = Enc_{pk}(n) $ 是明文的加密 $ a,b,\text{and } n $ 在具有公鑰的語義安全的完全同態加密下 $ pk $ ， 在哪裡 $ n $ 是模數。

1. $ S = Sub(A,B) = Add(A,-B) $
2. $ C = MSB(S)\quad\quad\quad; $ //一位比較結果。
3. $ F = S + N\quad\quad\quad\quad; $ // 如果需要，添加模數
4. $ R = C * F + C’ * S\quad $ // 如果條件為 $ C $ 選擇任一 $ F $ 或者 $ S $ .
5. 返回 $ R $

電路不完整，因為答案仍然可能是否定的。在這種情況下，與零加密進行比較 $ E_0 =Enc_{pk}(0) $ 並添加 $ N $ 再次。

一個通用的解決方案是固定位長 $ N $ 成為，說， $ \ell $ ，然後表示 $ a, x $ ， 和 $ N $ 作為 $ \ell $ 維二進制向量並加密每一位（獲得 $ 3\ell $ 密文），然後同態地執行一個執行兩個減法的電路 $ \ell $ -位整數和執行減少的電路（如@kelalaka的回答）……

然而，如果 $ N $ 很小，那麼您可以簡單地使用其消息空間的方案 $ \mathcal M $ 對於可能的值來說足夠大 $ x - a $ 置身其中，也就是說， $ [-N, N]\cap\mathbb{Z} \subset \mathcal M. $ 在這種情況下，減法不會“溢出”，您仍然可以通過簡單的解密和自己執行模組化減少來恢復結果。

這或多或少等價於選擇消息空間為 $ \mathbb{Z}_N $ ，這也是一個簡單的解決方案，如果 $ N $ 是小。

大多數方案都帶有二進制消息空間，但它們可以很容易地擴展到工作 $ \mathbb{Z}_N $ 代替 $ \mathbb{Z}_2 $ .

引用自：https://crypto.stackexchange.com/questions/76065