為什麼我們總是假設協議可以複製的功能是形式F:{0,1}∗→{0,1}∗F:{0,1}∗→{0,1}∗f:{0,1}^to{0,1}^?
考慮到安全多方計算和秘密共享的大量文獻，對規則函式的計算做了一個特定的假設。後一個函式將代理的個人秘密作為輸入，並根據代理想要模仿的規則給出個人指令作為輸出。再次回想一下，每個玩家 $ i $ ， 的 $ N<+\infty $ 玩家，有一個秘密說 $ x_i $ . 他們都希望以規則起作用的方式共享他們的資訊 $ f(x_1,x_2,\cdots,x_N)=(a_1,a_2,…a_N) $ 以某種方式形成，協議末尾的每個玩家都只會知道她自己的組件 $ a_i=f(x_i) $ 並且沒有其他資訊。
- 為什麼我們假設 $ f $ 是多項式函式還是時間多項式？這背後的直覺是什麼？
- Rabin、Ben-or和Ben-or 等人的協議假設 $ f $ 是一個函式，使得她的域和共域是相同的，即 $ f:{0,1}^\to{0,1}^ $ ，但這限制了我們可以藉助協議複製的功能類型，不是嗎？為什麼我們假設這是協議可以模仿的唯一功能係列？這個函式族是否也將問題限制為多項式函式？這個假設能改變嗎？
- 也在頁面中 $ 79 $ Rabin 和 Ben-or 的協議引用了 $ P_i $ 分享 $ \beta_i $ 使用 $ h_i(x) $ …”但是這個功能在哪裡 $ h_i $ 來自？直到那時他們還沒有定義任何這樣的功能？
為什麼我們假設 f 是多項式函式或時間多項式？這背後的直覺是什麼？
我相信您已經熟悉為什麼我們使用多項式時間作為基本上所有密碼學的基線（查看 Kelalaka 的評論）。簡而言之，有無數理由讓我們相信這是一個合理合理的模型，我們直覺地稱之為“高效計算”。在這裡，在 MPC 的上下文中，沒有什麼不同：我們希望能夠專注於高效執行的計算。
這限制了我們可以藉助協議複製的功能類型，不是嗎？為什麼我們假設這是協議可以模仿的唯一功能係列？這個函式族是否也將問題限制為多項式函式？這個假設可以嗎
我不熟悉這些論文中的確切措辭，但通常每當您提到具有無限輸入/輸出的函式時，您實際上是在考慮這些仍然可以在多項式時間內相對於輸入長度進行計算的函式。再一次，這是因為我們將協議的參與者建模為多項式時間機器，並且我們希望他們能夠完成計算。
此外，還有一些安全概念依賴於對手是計算受限的假設。例如，有些協議的安全性依賴於對手無法分解大量數據。如果有足夠的計算時間來嘗試所有可能的素因子，這當然是可能的，但是多項式時間的對手無法做到這一點。
然而，在安全多方計算的背景下，我們確實可以容忍在超多項式時間內執行的對手。具有完美和統計安全性的協議（包含**資訊理論安全性的總稱）的設計方式是，無論計算資源的數量或執行時間如何，任何對手都不能破壞協議的安全性。
鑑於此，原則上，我們可以讓所有各方（不僅是對手）在超多項式時間內執行，但問題就變成了這樣做的真正收穫。基本上，我想不出我們想要計算的有意義的非多項式函式。