多密鑰同態加密中的門檻值解密
我很難理解多密鑰同態加密（MKHE）中門檻值解密的安全性，即所謂的“雜訊氾濫”。特別是我認為它不安全，所以可能我誤解了一些東西。
MKHE 允許多個客戶端加密他們的輸入 $ x_i $ 與他們的私鑰，它被加入到一個共同的密文中 $ C $ . 任意函式 $ f $ 然後可以用於 $ C $ 產生加密 $ C_f $ 的 $ f(x_1,\ldots, x_k) $ . 最後（對於這個問題也是最重要的），每個客戶端創建一個部分解密 $ C_f $ ，它被連接以獲得 $ f(x_1,\ldots, x_k) $ .
我將在本文中解釋這是如何基於 BFV FHE 方案 (RLWE) 完成的，因為我認為它可能是最簡單的。還有其他具有類似想法的方法，例如第一篇論文，這篇論文 ，…
為簡單起見，我將只考慮一個簡單的加法運算。假設我們有三個客戶端，每個客戶端都加密 $ x_i $ 最後我們想要得到 $ f(x_1,x_2,x_3) = x_1 + x_2 + x_3 $ . 該方案基於 RLWE 問題，所以讓 $ R $ 成為一個戒指和 $ D_{\sigma} $ RLWE 問題很難解決的分佈。讓 $ q $ 是的模數 $ R $ 和 $ t $ 明文的模數。定義 $ \Delta = \lfloor q/t \rceil $ .
設置：讓 $ a \in R $ 是均勻隨機元素。
密鑰生成：每個客戶端都對秘密和雜訊進行採樣 $ s_i, e_i $ 和 $ D_{\sigma} $ 並設置 $ b_i = -as_i + e_i $ . 然後 $ (s_i, b_i) $ 是他的鑰匙。
加密：每個客戶端加密 $ x_i $ 通過抽樣 $ r_i, e_i^1, e_i^2 $ 和 $ D_{\sigma} $ 環境 $ (c_i^0, c_i^1) = (b_ir_i + e_i^1 + \Delta x_i, a_ir_i + e_i^2) $
評估：密文 $ (c_i^0, c_i^1) $ 被評估為加密 $ f(x_1,x_2,x_3) $ 通過定義： $ C_{f} = (c_0, c_1, c_2, c_3) $ 在哪裡 $ c_0 = c_1^0 + c_2^0 + c_3^0 $ , $ c_1 = c_1^1 $ , $ c_2 = c_2^1 $ , $ c_3 = c_3^1 $ .
PartDec：每個客戶端都採樣所謂的“污跡雜訊” $ e_i^{sm} $ 並發送： $ \mu_i = c_i^1s_i + e_i^{sm} $
MergeDec : 每個人都可以計算 $ \mu = c_0 + \mu_1 + \mu_2 + \mu_3 $ 對應於 $ \Delta(x_1 + x_2 + x_3) + \text{noise} $ 所以可以提取結果。
**問題：**部分解密安全的原因是“污跡雜訊”應該隱藏秘密。但是如果我使用部分解密 $ \mu_i $ 客戶連同他的部分密文： $$ c_i^0 + \mu_i = (b_ir_i + e_i^1 + \Delta x_i) + (c_i^1s_i + e_i^{sm}) = ((-as_i + e_i)r_i + e_i^1 + \Delta x_i) + ((a_ir_i + e_i^2)s_i + e_i^{sm}) = e_ir_i + e_i^1 + e_i^2s_i + e_i^{sm} + \Delta x_i $$ 但這意味著一個人可以得到 $ x_i $ 這是不行的。一個可以隱藏 $ x_i $ 除非 $ e_i^{sm} $ 會大到足以隱藏它。但後來也 $ \mu $ 會被噪音淹沒。我錯過了什麼？
你寫的一切看起來都是正確的。但是，您可能期望分佈式解密協議具有它不具有的安全屬性（並且不打算，並且在您的範例中實際上不能）。
具體來說，您連結的 Mukherjee-Wichs 論文定義了安全性，以（粗略地）說，鑑於評估的密文、其基礎明文以及除一方之外的所有各方的密鑰，我們可以統計模擬該方的部分解密。這對應於除一方之外的所有方都是半誠實的，並保護其余誠實方輸入的隱私（盡可能）。
在您的範例中，評估函式只是將三個輸入相加。因為除了一方之外的所有一方都是半誠實的，所以對手知道他們所有的輸入。它還有權獲得所有各方投入的產出總和。這意味著它可以輕鬆計算誠實方的輸入！因此，實際上並沒有因為解密協議隱含地揭示誠實方的輸入而導致“安全違規”，因為該輸入是由函式本身隱含地揭示的。
如果你考慮一個不同的評估函式，它不會隱含地揭示誠實方的輸入，那麼我認為你應該明白為什麼“污點”噪音會按預期工作。