回合複雜度在確定 MPC 協議效率中的重要性

文獻有不同的方式來指定 MPC 協議的複雜性：

• 衡量各方執行的（假定的原始）操作數量的計算複雜度；
• 通信複雜度，衡量協議期間各方之間通信的比特數；
• 測量算法中連續步驟數的回合複雜度（不考慮可以並行完成的操作）。

在分析任何提議的 MPC 協議的效率時，我覺得上述所有參數都很重要，需要討論。然而，我觀察到只有少數作品討論了回合的複雜性。因此，我想知道，在確定任何提議的協議的效率方面，回合複雜性扮演了多麼重要的角色。也就是說，什麼時候考慮協議的輪複雜度很重要？

如果您能指出我的文獻，討論可以使用 MPC 以恆定循環實現的功能的性質以及那些不能實現的功能，那將會很有幫助。

首先請注意，所有多項式時間函式都可以使用恆定輪數（Yao 和 BMR 系列）安全地計算，並且所有多項式時間函式都可以使用具有取決於計算函式的電路深度的輪數的協議（GMW 系列）安全地計算。問題是什麼時候一種類型比另一種更好。

這個問題的答案並不簡單，取決於許多參數。顯然，如果您使用的是慢速網路（往返時間為 30 毫秒的 Internet），那麼任何有很多輪次的協議都會非常慢。然而，如果你在一個快速的網路上，那麼多輪的影響就較小（除非在非常深的電路的極端情況下）。事實證明，我們所知道的恆定輪次協議比那些複雜性取決於電路深度的協議具有更高的頻寬。因此，在一個非常快速的網路中，多輪協議的性能通常優於恆定輪協議。正如我所提到的，在慢速網路中情況並非如此。

沒有太多與這個問題直接相關的出版物。然而，對於半誠實的對手，Schneider 和 Zohner 想到了一篇論文，標題為：GMW vs. Yao？在 Financial Crypto 2013 上出現的具有低深度電路的高效安全兩方計算。這是開始閱讀的好地方。

引用自：https://crypto.stackexchange.com/questions/37224