Multiparty-Computation
是否可以執行 MPC 協議來計算多項式環中的乘積？
我希望不要問太多，但我有 N 方，每方都持有一個多項式，係數為 0-1，度數固定 $ n-1 $ . 如果有可能（我的意思是可行）用 MPC 協議計算所有這些多項式的乘積，我一直在徘徊。
實際上，為了安全起見，我需要結果模 $ X^n+1 $ ，所以我的實際要求如下： $ N $ 多項式 $ P_1,P_2,\dots,P_N $ 和 $ 0-1 $ 係數和度數 $ n-1 $ , 計算 $ (\prod P_i)\mod(X^n+1) $ 使用多方計算協議，其中每一方都持有一個 $ P_i $ .
我的問題是關於這種產品的複雜性（ $ O(n \log n\log N) $ 如果使用 FFT 算法，則整數乘法？）
這是我在這裡的第一個問題，所以請附上歡迎資訊給你回答:-)
您提到了一個環，但您只使用了乘法運算。因此，它實際上只是您想要的組操作的協議。如果群是阿貝爾群，那麼有一個簡單的經典協議 $ n $ -黨組產品：
- 各方表演 $ n $ -在……之外- $ n $ 他們的輸入的乘法秘密共享。更詳細地說，派對 $ i $ 有輸入 $ P_i $ 並選擇隨機多項式 $ P_{i,j} $ 以便 $ \prod_j P_{i,j} = P_i $ ，然後私下發送 $ P_{i,j} $ 聚會 $ j $ .
- 每一方 $ j $ 現在有 $ { P_{i,j} \mid i \in [n] } $ . 他/她計算他們的產品 $ P’j = \prod_i P{i,j} $ 並公開宣布 $ P’_j $ .
- 如果群是阿貝爾群，那麼 $ \prod_j P’j = \prod{i,j} P_{i,j} = \prod_i P_i $ ，所以每個人都可以計算出公眾的最終答案 $ P’_j $ 價值觀。
此外，任何數量的勾結半誠實方的觀點只會洩漏最終結果。
為了 $ N=2 $ ，有協議可以在向量之間執行多方內部產品（快速Google搜尋找到一些關於此的文章）。由於結果的每個係數都可以寫成內部乘積（實際上是一個有趣的練習），他們可以為每個係數繼續使用這些協議。最後，一方持有產品 $ fg+r $ 而對方持有隨機 $ r $ . 我應該補充一點，這些協議是嚴格的隨機數交換，它們只會洩漏所需的輸出。至於 $ N>2 $ ，我還沒準備好回答