Protocol-Design
檢測兩個數字是否相等而不透露更多資訊
考慮以下場景。愛麗絲選擇了一個數字 A；Bob 選擇了一個數字 B。A 和 B 都屬於一個相對較小的集合 X（我所說的小是指 X 可以很容易地循環：為了直覺，想像 X 是一副紙牌的大小）。我希望 Alice 和 Bob 參與一個協議，告訴兩者是否 A = B。如果 A != B，那麼 Alice 應該沒有關於 B 的更多資訊，Bob 應該沒有關於 A 的更多資訊。
我想知道這是否可能？如果 X 非常大，並且不失一般性地假設 A 是素數，Alice 可以選擇一個大於 X 中的最大值的任意 P 素數並將 A * P 發送給 Bob。然後 Bob 可以嘗試用 B 分解 A * P：如果可行，則 A = B。但是，這顯然假設 Bob 嘗試 X 的所有元素是不可行的。如果 X 很小，這個假設會立即失效。
是的，這很有可能。
顯而易見的方法是讓 Alice 和 Bob 執行平衡密碼認證密鑰交換 (PAKE) 協議，其中 $ A $ 和 $ B $ 成為他們的“密碼”。如果他們想出相同的共享秘密， $ A=B $ ，如果他們想出 $ A \ne B $ 他們沒有學到任何其他的東西 $ A $ 和 $ B $
那裡有許多 PAKE 協議。有關一些更常見的內容，請參閱wikipedia 文章。
一種比較值的方法（簡化的 CPACE） $ a $ 愛麗絲和 $ b $ Bob 知道的是選擇不相關的值 $ G $ 和 $ N $ （我寫了這個假設橢圓曲線；它可以直接轉換為 modp 組，除了減法變成模反轉）和：
- Alice 選擇一個隨機值 $ r $ 併計算 $ C = r G + a N $ ; 她發送 $ C $
- Bob 選擇一個隨機值 $ s $ 併計算 $ D = s G + b N $ ; 他寄出 $ D $
- 愛麗絲計算 $ S = r (D - a N) $ ; Bob 計算 $ T = s (C - b N) $ ; 如果 $ a=b $ ， 然後 $ S=T $ ; 否則它們是無關的。
Alice 和 Bob 都可以發送 $ S $ 和 $ T $ 彼此（如果他們相信對方是誠實的），或者使用它們來生成加密密鑰並執行簡單的驗證協議。