用密碼學玩暗軍棋 -- 閑聊多方計算

01-26

暗軍棋

我們先來回顧一下兒時玩的軍棋遊戲，然後探討一下如何使用密碼學來代替裁判。軍棋遊戲的目標是通過在棋盤上移動自己的部隊攻佔對方的軍旗。當兩方的棋子碰撞時，採取如下規則

司令 > 軍長 > 師長 > 旅長 > 團長 > 營長 > 連長 > 排長 > 工兵
炸彈與任何非軍旗棋子相遇時，雙方都消失
工兵 > 地雷
地雷 > 除炸彈和工兵以外的任何子力
任何棋子 > 對方的軍旗 (遊戲結束，一方勝利）。

軍棋有明與暗兩種下法。在明軍棋中，雙方的棋子正面朝上放置。暗軍棋是一種更刺激的玩法，雙方把棋子扣過來背面朝上，用來隱藏自己的布陣和行動。但是暗軍棋的特點是需要一個裁判：當兩枚棋子碰撞的時候，裁判觀看棋子的正面，然後執行上述的吃子規則。那麼問題來了：如果沒有裁判，兩個人還可以玩暗軍棋嗎？

YES! 用密碼學不僅能實現暗軍棋，還可以不依賴公正的第三方（裁判/法官/拍賣行）來進行任何博弈（古董拍賣，德州撲克，狼人殺等等。。。）不過實現的方法稍微有一點複雜，所以我們先來講簡單的情形～首先，兩枚軍棋的碰撞可以抽象成一個比較函數:

$f(x, y ) = 1 mbox{ if } x > y, -1 mbox{ if } x <y, 0 mbox{ if } x = y$

假設我的軍長是10級，對方的連長是3級，那麼因為10 > 3, 所以比較的結果是1 ，我的軍長吃掉對方的連長。問題是，我擁有數字10，對方擁有數字3，我們怎麼能在不透露具體軍階的情況下，比較這兩個數的大小呢？這裡我們就要隆重介紹 --- 姚期智院士的百萬富翁問題！

百萬富翁問題

在文章[1]中，姚老師提出了如下問題：

兩個富翁的財產是1到10之間的整數。他們如何在不透露自己財產的情況下，比較誰更富有？

很容易看出，百萬富翁問題和暗軍棋比較軍銜問題是等價的：無非是比較大小。我們下面來介紹姚老師的精妙解法 ---

假設富翁王有 $i$ 億資產，李有 $j$ 億資產。王選取一個公鑰，使得李可以傳遞加密的信息。

首先，李選取一個隨機的大整數 $x$ ，把 $x$ 用王的公鑰加密，得到密文 $K$ 。李發送 $K -j$ 給王。

王收到密文 $c = K - j$ 之後，對 $c+ 1, ldots, c+ 10$ 進行解密，得到十個數字。再選取一個適當大小的素數 $p$ , 把這十個數字除以 $p$ 的餘數記作 $d_1, ldots, d_{10}$ .

注意: 這十個數字看起來應該是完全隨機的，關鍵是等式 $d_j = x mod{p}$ 成立。

最後，王對這一串數字作如下操作：前面 i 個數不動，後面的數字每個加一，然後發回給李。

這樣一通複雜的操作之後，李檢查第j個數字。如果等於 $x mod{p}$ 的話，說明這個數字沒有被加一，所以 i >= j. 反之，則 i < j。

這個過程的絕妙之處在於：在協議完成之後，王不知道j的具體值，而李也不知道 i 的值，但是雙方都知道誰的財富更多，這就是安全多方計算。一般來說，在甲只知道x，乙只知道y的情況下，雙方可以合作計算一個函數 f(x,y)。協議完成時，只有函數值是公開的，而彼此都不知道對方的輸入值。

回到暗軍棋

在解決了百萬富翁問題之後，暗軍棋的玩法就很簡單了。在每次兩枚棋子碰撞的時候，只需要對弈兩方進行一次上述的比較計算就可以了。有細心的同學要問了：且慢，這種玩法下難道不可以作弊嗎？比如我的棋子只是2級，但我可以在比較的時候輸入一個10級，而對方是無法發現的，因為計算結果只會表明我的棋子比他大？確實如此，注意到上面的協議是無法確保輸入的數字和棋子的軍階是一致的。但是解決的方法也很簡單，如在遊戲結束之後，雙方都翻開自己的所有棋子，再對照遊戲記錄進行明軍棋的復盤，就可以找出有沒有人作弊了～

安全多方計算(secure multiparty computation)

安全多方計算，可以說是密碼學中的又一項黑科技。它可以看作是上面比較函數的一個推廣，是可以實現任意數量的參與者共同計算任意函數的！它的應用就非常廣泛了，所有需要公正裁判的場景，都可以用這個協議來代替裁判～

兩個經典的應用：

拍賣 -- 對應的函數是取所有輸入的最大值。利用安全多方計算，在拍賣結束後每個人的出價都還保持隱私。

選舉 -- 對應的函數是對所有輸入求和（假設 1 代表選舉人A , 0 代表選舉人 B)。在這裡，安全多方計算可以確保每個人的投票是保密的，而且計票完全公正。

兩個新穎的應用：

共同好友 -- 兩個初次見面的人希望找到彼此的共同好友，而不向對方透露自己所有的好友。這裡雙方的輸入是兩個集合，對應的函數是取交集。

合作機器學習 -- 對應的函數是一個訓練演算法，而輸入是每人各自的data set。這個應用是近年來興起的。如果使用得當，可以打破數據的隱私壁壘。。。

那麼這麼強大的協議是怎麼實現的呢？這就得介紹到姚老師的神作 亂碼電路 了。今天先到這裡吧～

附加思考題：在上面的百萬富翁問題的解法，有一步是取十個明文除以素數p的餘數。這一步可以省略嗎？

參考文獻

[1] Yao, Andrew C. "Protocols for secure computations." In Proc. 23rd Annual Symp. on Foundations ofComputer Science (FOCS), pages 160–164. IEEE, 1982.