Multiparty-Computation
被動和完美安全的最佳門檻值
《安全多方計算和秘密共享》一書的作者聲稱，存在無法用被動完美安全計算的函式 $ t \geq n/2 $ 腐敗的政黨，其中 $ n $ 是參與方的總數。作者通過證明沒有協議來證明這一點 $ \pi $ 存在於安全的 2 方和一個腐敗方。但是，對於 2 方協議（ $ n=2 $ )，門檻值 1 可以寫成 $ n $ 作為 $ n/2 $ 或者 $ (n-1) $ ， 自從 $ n=2 $ . 那麼我們如何保證 $ n/2 $ 最優腐敗有界嗎？
有人可以幫助填補我理解的空白嗎？
將證明擴展到任意的方法 $ t,n $ 這個門檻值如下。假設存在任何協議 $ n $ 經受住門檻的締約方 $ t=n/2 $ 腐敗方，用於計算 $ f(x_1,\ldots,x_n)=x_1 \wedge x_{n/2+1} $ . （如果能承受 $ t>n/2 $ 那麼它也能承受 $ t=n/2 $ ，所以很好。）我現在將建構一個用於安全計算的兩方協議，並且該協議對一個損壞具有彈性。這將與已知的不可能結果相矛盾。
該協議的工作原理如下。雙方模擬執行 $ n $ - 方協議。聚會 $ P_1 $ 內部經營派對 $ P_1,\ldots,P_{n/2} $ 和派對 $ P_2 $ 內部經營派對 $ P_{n/2+1},\ldots,P_n $ . 聚會 $ P_1 $ 將其輸入作為 $ P_1 $ 在裡面 $ n $ -派對協議和派對 $ P_2 $ 將其輸入作為 $ P_{n/2+1} $ 在裡面 $ n $ - 方協議。各方輸出多方協議要求輸出的任何內容。
為了爭論安全性，您真正需要注意的是，如果一方被破壞，那麼這相當於 $ t=n/2 $ 在多方協議中。因此，保持了安全性。