乘法的安全多方計算
假設有 $ N $ 派對 $ p_j $ , 每個都有一個二進制 $ b_j\in{{0,1}} $ . 問題需要計算一個個數乘以零個數的乘積，即 $ R=(\sum{b_j})\times(N-\sum{b_j}) $ .
計算應該是安全的，因為任何一方都不能知道比最終結果更多的資訊 $ R $ . 例如，執行安全求和是不行的，因為那時 $ \sum{b_j} $ 是已知的，這對我的問題很敏感。那麼，是否有任何現有的安全計算協議適合我的需求？
好吧，我不知道關於這個精確問題的任何已發表的工作，但是我相信我確實有一個解決方案。
首先，我會注意到你的問題相當於問題“如果每一方都有一點 $ b_i $ , 他們能安全地計算一個值嗎 $ k $ 與 $ k = \sum b_i $ 或者 $ k = N - \sum b_i $ （不提供任何進一步的資訊，包括它可能是哪些值）”。因此，我們可以使用安全總和作為解決方案的一部分，只要我們小心不要提供有關它是哪個總和的任何資訊。
這是我的協議的工作原理；它需要4輪和 $ 4N $ 黨員之間的消息。每一輪，黨員自己安排一個循環；每個黨員從前一個黨員那裡獲取一個值（或第一個黨員的周期開始時的數據），對這些值進行一些計算，然後將其傳遞給下一個黨員。我也不認為黨員之間的資訊是私人的。
在初始化階段，黨員在一個很難解決 Diffie-Hellman 問題的小組上達成一致，並且兩名小組成員 $ A $ 和 $ B $ 這樣 $ A \neq 2^k \cdot B $ 和 $ B \neq 2^k \cdot A $ 對於任何值 $ 0 \leq k \leq N $ （注意：我對組使用加法符號，如果您使用的是乘法組，通常會寫成 $ A \neq B ^ {2^k} $ 和 $ B \neq A ^ {2^k} $ )
現在，第 1 輪：我們從包含該對的數據開始 $ (A, B) $ . 每個黨員拿他們得到的那對 $ (X, Y) $ , 選擇一個整數 $ c_i $ , 隨機選擇 $ (c_i \cdot X, c_i \cdot Y) $ 或者 $ (c_i \cdot Y, c_i \cdot X) $ ，並將該對發送給下一個黨員。
- 這一輪的重點是，最後一方的輸出將是 $ (c \cdot A, c \cdot B) $ 或者 $ (c \cdot B, c \cdot A) $ （對於一些致盲因素 $ c $ ) 沒有人能夠確定哪個。
現在，第 2 輪：我們從上一輪的數據開始。每一方都拿他們得到的一對 $ (X, Y) $ , 選擇另一個整數 $ d_i $ ，然後如果他們的位 $ b_i $ 為零，計算 $ (2 \cdot d_i \cdot X, d_i \cdot Y) $ ，如果他們的位 $ b_i $ 是一，計算 $ (d_i \cdot X, 2 \cdot d_i \cdot Y) $ ，並將該對發送給下一個黨員
- 這一輪的重點是收集選票；這對中的第一個收集零票，第二對收集一票（同樣，有一個致盲因素，所以沒有人可以看到其他人投票的內容）。
現在，第 3 輪：我們從上一輪的數據開始。每個黨員拿他們得到的那對 $ (X, Y) $ , 選擇一個整數 $ e_i $ , 隨機選擇 $ (e_i \cdot X, e_i \cdot Y) $ 或者 $ (e_i \cdot Y, e_i \cdot X) $ ，並將該對發送給下一個黨員（最後一個黨員除外；他們隨機選擇 $ (e_N \cdot X) $ 或者 $ (e_N \cdot Y) $ 並發送
- 這一輪的重點是偽裝這對中的哪一個是“0”票，哪一個是“1”票；最後一個成員返回其中一個，但沒有人知道它有哪一個。
現在，第 4 輪：我們從上一輪的數據開始。每個黨員都拿他們得到的價值 $ (X) $ 並刪除他們應用的致盲因素；也就是說，計算 $ ((c_i \cdot d_i \cdot e_i) ^ {-1} \cdot X) $ ，並將其傳遞給下一個部分成員。
最後一名黨員的結果將是 $ 2^k \cdot A $ 或者 $ 2^k \cdot B $ ; 我們可以恢復價值 $ k $ 在 $ \sqrt N $ 時間，這就是我們的結果。
注意：
- 這將是 $ 2^k \cdot A $ 如果偶數個黨員決定在第 1 輪中交換，並且 $ 2^k \cdot B $ 如果一個奇數決定交換。因為每個黨員都是隨機選擇的，並且獨立於其他任何東西，所以它是公正的，並且與任何東西都不相關。
- 計算出的 $ k $ 將會 $ \sum b_i $ 如果在第 3 輪期間有奇數個黨員決定交換，並且 $ N - \sum b_i $ 如果偶數決定交換（對於最後一個黨員，如果他選擇了，我們將他視為交換 $ (e_N \cdot Y) $ . 再一次，因為每個黨員都是隨機選擇的，並且獨立於其他任何東西，所以這是不偏不倚的，並且與任何東西都不相關。
我不是專家，但同態加密可能適用於此。我相信你可以使用一個支持無限加法和一次乘法的系統。