在不透露保留價格和必須信任第三方的情況下辨識潛在協議區域的協議?
A 想從 B 那裡購買一家公司。在 A 和 B 進入談判之前,他們想確保實際上存在一個潛在協議區域。顯然,他們不想將他們的預訂價格傳達給對方(A 只以低於 100m 的價格購買,B 只以至少 90m 的價格出售)。因此,他們都將他們的預訂價格傳達給一個值得信賴的調解員,然後他們會告訴他們談判是否有意義。
有沒有一種協議可以讓 A 和 B 使用來找出相同的東西而不必信任對方和任何第三方?
有沒有一種協議可以讓 A 和 B 使用來找出相同的東西而不必信任對方和任何第三方?
有。甚至不止一個。
你的問題其實相當於姚明的百萬富翁問題。
您有兩個數字,雙方都想保密,並且您希望雙方找出一個是否大於另一個,即比較 $ a\geq b $ 和 $ a $ 是 A 願意支付的最大價格,並且 $ b $ 是 B 會賣出的最低價格。
解決這個問題的安全多方協議(感謝 Ricky 指出)是多種多樣的。因為它們並不容易,如果你從原始碼中獲取它們會更好,我將快速命名三個(歡迎更好的協議建議):
這是@SEJPM 答案的擴展。我想擴展最適合使用的協議(我提前為自引用道歉)。首先,關於 Yao 協議的詳細資訊,請參閱A Proof of Security of Yao 協議的兩方計算。但是,要非常有效地執行此操作,您需要有兩個非常有效的組件:
- 一個快速的亂碼方案:參見JustGarble和這個替代方案。亂碼程式碼可以在 Github 上的開源SCAPI庫中找到。
- 快速不經意傳輸:當您需要執行很多時,應使用不經意傳輸擴展。有關目前最快的協議,請參閱本文。(它的實現也可以在SCAPI找到。)
另一種選擇是執行基於不經意傳輸擴展的 GMW 協議。參見GMW vs Yao和這裡。
以上都與半誠實的對手有關。如果您想要惡意對手的安全,那麼您需要更加努力地工作。這取決於您是否想要一次執行多次執行(您提前準備的地方)。對於一些選擇,請參閱:here、here和here。最後一個在SCAPI也有程式碼。
這是一個非常有偏見的列表(我真的很抱歉),還有很多其他的選擇。但是,我嘗試為您提供也有可用程式碼和支持的東西。您可以在我指出的論文中找到許多其他工作的引用。