姚氏百萬富翁問題，你看得懂嗎？看懂說明智商極高

理解姚氏百萬富翁問題

Posted on 2017-10-13 | In 解問題

昨天在知乎上看到了一個問題：兩富人比誰錢多。如何能實現互相保密但可以比出誰錢多？

乍一看感覺不是什麼特別複雜的問題，比如知乎使用者@辰艦長的答案：

用天平，每個富商領到一個質量固定的黑箱，讓富商在其中放入質量與財富相對應的籌碼（例如除以1000000）。放在天平兩邊看哪邊重一點，就醬。

但更多的人引用了文獻：

Yao， Andrew C。 “Protocols for secure computations。” *Foundations of Computer Science， 1982。 SFCS’08。 23rd Annual Symposium on

。 IEEE， 1982。*。這個問題其實是著名的

姚氏百萬富翁問題

，是計算機學家姚期智1982年的一篇論文。

姚期智（Andrew Chi-Chih Yao），祖籍湖北省孝感市孝昌縣，世界著名計算機學家，2000年圖靈獎得主，中國科學院院士，美國科學院院士，美國科學與藝術學院院士，清華大學高等研究中心教授，香港中文大學博文講座教授。1967年獲得臺灣大學物理學士學位，1972年獲得美國哈佛大學物理博士學位，1975年獲得美國伊利諾依大學計算機科學博士學位。1975年至1986年曾先後在美國麻省理工學院數學系、斯坦福大學計算機系、加利福尼亞大學伯克利分校計算機系任助理教授、教授。2004年起在清華大學任全職教授。2005年出任香港中文大學博文講座教授。2017年2月，姚期智教授放棄外國國籍成為中國公民，正式轉為中國科學院院士，加入中國科學院資訊科技科學部。

——引自百度百科

在看論文之前還看了一些參考資料，比如知乎專欄用密碼學玩暗軍棋 – 閒聊多方計算

，但對於其中的演算法細節還是存疑的，以及公鑰這樣的概念個人比較含糊。乾脆直接啃原文了（原文連結：1982 749 AC Yao， Protocols for secure computations）。感謝@能縱玄的孫權對我的部分問題進行答疑解惑。

下面用盡量簡單易懂的語言介紹一下這個演算法的過程。

問題描述

假設富翁A和B分別有ii，jj億資產，其中0

（假設A和B都是君子，必須嚴格誠信執行下面的演算法）

演算法

設富翁A有4百萬資產，富翁B有2百萬資產，即i=4，j=2i=4，j=2，且A和B互不知曉對方的資產。演算法過程如下：

1。生成N−bitN−bit正整數集MM，bit是二進位制位，設N=5N=5（實際操作中N應該根據i，ji，j的上限取值，且儘量取大。為了書寫方便這裡的取值較小），生成正整數集MM如下，共計16個數：

16，17，18，19，20，。。。，29，30，31

2。生成M−MM−M的所有一一對映集合QNQN。則步驟1的例子中，得到的QNQN含16！16！個元素。

3。富翁A隨機選取QNQN中的一個元素作為公鑰（用於加密傳輸的加密方式），並告知B

（注意：這個對映關係的反向就是私鑰，A不能將此私鑰資訊告訴B）

，不妨設A選擇的公鑰為：

16-24，17-16，18-29，19-31，20-17，21-22，22-27，23-28，24-18，25-30，26-25，27-19，28-23，29-26，30-21，31-30

4。富翁B隨機選擇一個N−bitN−bit正整數xx，因為x∈Mx∈M，所以B可以在公鑰中找到xx的對應元素kk。設x=20x=20，則對應的k=17k=17。

5。B將k−jk−j的計算結果發給A，即這裡B將傳送15。

6。A透過第三步的加密／解密方法，將k−j+1，k−j+2，…，k−j+10k−j+1，k−j+2，…，k−j+10逐個解密，計作序列yuyu：

yu = ［17，20，24，27，31，30，21，28，16，26］

並選取N/2−bitN/2−bit的素數pp，將yuyu中每個元素除以pp得到的餘數（即yi mod pyi mod p）計作序列zuzu，若zuzu中至少有兩個元素不相同則pp滿足條件，否則更換pp。這裡取p=3p=3，則zuzu如下：

zu = ［2，2，0，0，1，0，0，1，1，2］

7。A將上述zuzu序列進行處理：保持前ii個數字不變，從第i+1i+1個數到最後一個數全部增加1。並將處理過的序列z′uzu′和素數pp發給B，如下：

zu‘ = ［2，2，0，0，2，1，1，2，2，3］， p = 3

8。B接收z′uzu′和pp，檢視z′uzu′中的第jj個元素z′u（j）zu′（j），若x mod p=z′u（j）x mod p=zu′（j），則i≥ji≥j，反之，i

9。B將結果告訴A，演算法結束。

正確性

第一遍看這個演算法的時候，雖然自己按照上面的過程帶入數值模擬了一遍，但沒有想通為什麼這樣做是正確的。思考了一陣後豁然開朗。

因為0

反之，若：x mod p≠z′u（j）x mod p≠zu′（j），即第jj個數被A處理過了，那麼B就知道i≤ji≤j。

說明

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

回答是：不能省略！

假設省略了素數pp的參與，直接進入第七步，A將得到：

yu’ = ［17，20，24，27，32，31，22，29，17，27］

併發給B。

B在查看了第2個元素後發現與xx一致，B就知道A的資產比自己多了。

這個時候B不甘心：我倒要看看你A有多少錢！

B用A給的公鑰將y′uyu′中的數字全部編碼，依次得到：

16，17，18，19

這樣的自然序列，在第5個元素的時候，發現找不到對應的加密方式了（數字32在本例中產生了溢位，如果序列範圍更大理論上可以避免），第6個元素對應的密文為20，第7個元素對應密文為27…從第5個元素開始就已經被A處理過了，於是B知道了，A的資產是4百萬。

從這個過程我們看出，一定需要合適的素數pp來對A的資訊加密。

小結

引用Vichare Wang的一段回答：

第一步，經過特定的操作，讓A構造出 n 把鎖，B有且僅有第 j 把鎖的鑰匙，但是A不知道 j 是多少；

第二步，A給B n 把鎖鎖著的標誌位，其中前 i 個標誌位置0，後 n-i 擱置1；

第三步，B檢查第 j 把鎖鎖著的標誌位是否為0。如果為0則 i >= j，否則 i < j。

這差不多就是這個演算法的精髓所在。

原論文還討論了防作弊、多方比較等通用方案，本文不再贅述。

回到這篇文章：用密碼學玩暗軍棋 – 閒聊多方計算，如果真的要用密碼學玩暗軍棋，則一定是需要程式解決的。上面演算法中也舉出了簡單的例子，這個演算法看似不復雜，但手工計算和處理還是挺麻煩的。

參考文章：

公鑰與私鑰

補充回覆評論區的一些問題

「演算法」的第1點： 『1。生成N−bit正整數集M，bit是二進位制位，設N=5（實際操作中N應該根據i，j的上限取值，且儘量取大。為了書寫方便這裡的取值較小），生成正整數集M如下，共計16個數：』

Q： 這個N=5在後方好像沒用到？ 正整數集M為什麼有16個數呢？又為什麼從16開始，到31結束？

A： N−bitN−bit中的NN是指二進位制的位數，N=5N=5即5位（最高位為1），所以：

$16=10000

{（2）}， 17=10001

{（2）}， …， 31=11111_{（2）}$

「演算法」的第3點： 『富翁A隨機選取QN中的一個元素作為公鑰（用於加密傳輸的加密方式），並告知B（注意：這個對映關係的反向就是私鑰，A不能將此私鑰資訊告訴B），不妨設A選擇的公鑰為：』

Q。 不是選擇『一個』元素嗎？ 怎麼又有這麼多數字跑出來？而且您沒有說到Alice的公鑰e是什麼，也沒輸到兩個質數p，q，以及兩質數相乘的n

A： 因為第二步中，QNQN的生成條件是M−MM−M的對映集合，運用排列組合的相關知識，我們知道這樣的對映有A1616=16！A1616=16！個，每一個對映都由16個數的兩兩對應組成，因此會有下面的：

16−24，17−16，18−29，…，31−3016−24，17−16，18−29，…，31−30 （隨機選出一種對映方式）

公鑰在這裡就是一種對映方式。

關於質數的問題，因為N2−bit=5/2=2N2−bit=5/2=2（向下取整），回憶上面講到的N−bitN−bit概念，2−bit2−bit的數字包括：

$10

{（2）}，11

{（2）}$，對應自然數2，3。

所以後面的pp選為3。

「演算法」的第4點： 『富翁B隨機選擇一個N−bit正整數x，因為x∈M，所以B可以在公鑰中找到x的對應元素k。設x=20，則對應的k=17。』

Q。 為什麼x∈M？

A： 我們在第一點中講到，M是5bit數字的集合，所以自然有x∈Mx∈M。