與受約束的 3 方秘密共享
假設我們有 $ 3 $ 與愛麗絲、鮑勃和查理聚會，使愛麗絲無法與鮑勃交談。
假設 Alice 有一些字元串 $ x\in{0,1}^n $ Bob 有一個字元串 $ y\in{0,1}^n $ .
假設 Alice 和 Bob 可以訪問一個共享的隨機字元串 $ r $ 和一個共享的秘密 $ s $ .
假設查理兩者都知道 $ x $ 和 $ y $ 他無權訪問 $ r $ .
描述 Alice 向 Charlie 發送一條消息的協議（它可能取決於 $ x,r,s $ ）同時 Bob 向 Charlie 發送一條消息（它可能取決於 $ y,r,s $ ）。之後，如果 $ x=y $ 查理會知道的 $ s $ 而如果 $ x\neq y $ 查理將無法知道 $ s $ .
這個問題的一般背景是秘密共享，例如Shamir的秘密共享等。
我有一個解決這個問題的逆版本的提議，即如果 $ x\neq y $ 查理會知道的 $ s $ 而如果 $ x=y $ 查理將無法知道 $ s $ :
我的建議是考慮 $ x,y,r $ 作為該領域的成員 $ \mathbb{Z}_{2^n} $ .
愛麗絲計算 $ s+rx $ 並將其發送給查理。
Bob 計算 $ s+ry $ 並將其發送給查理。
如果 $ x\neq y $ 查理可以插值得到 $ s $ ， 否則 $ x=y $ 而查理只看到了一些隨機元素 $ \mathbb{Z}_{2^n} $ : $ s+rx=s+ry $ ，所以他無法恢復 $ s $ .
但這不是原始問題，我不知道如何處理原始問題。
我們可以將它推廣到一些布爾函式嗎 $ f:{0,1}^n\times{0,1}^n\to{0,1} $ ，即僅當 $ f(x,y)=1 $ 查理將能夠康復 $ s $ ?
這個問題在密碼學中被稱為有條件的秘密洩露。最近有很多關於這個主題的不錯的作品，我建議快速瀏覽一下這個例子。
在您的確切情況下，可以 $ r $ 有長度 $ 2n $ ? 如果是這樣，這是一個簡單的解決方案：呼叫 $ (r_0,r_1) $ 的左右部分 $ r $ , 每個長度 $ n $ .
- 愛麗絲發送 $ s + r_0x - r_1 $
- 鮑勃發送 $ r_1-r_0y $
因為面具 $ r_1 $ ，這兩個值只會洩漏 $ (s + r_0x - r_1) + (r_1-r_0y) = s + r_0(x-y) $ . 如果 $ x=y $ ，這揭示了 $ s $ ; 否則， $ r_0(x-y) $ 完美隱藏 $ s $ （加法和乘法在 $ \mathbb{F}_{2^n} $ ).
關於你的第二個問題，是的，有條件公開任意功能的秘密的結果。我們所知道的任意謂詞的最佳結果 $ f:[N]\times[N] \mapsto {0,1} $ 有交流 $ 2^{O(\sqrt{\log N \log\log N})} $ . 對於由布爾電路表示的謂詞，我認為我們可以在電路大小上進行線性通信，但我需要檢查這一點。