從「比較GPA」談起

先給大家說個問題啊。

很有意思的問題啊，它有一個腦洞很大的名字「Yaos Millionaires Problem」，姚期智在82年FOCS上的文章 "Protocols for secure computations"中提出來的（http://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf），「安全多方計算」的奠基之作。

這篇文章我之前曾發在人人上，今天興起，索性轉過來。

不過事先說明的是，在知乎上最可怕的就是裝學術逼，尤其對於我這種大水逼來說，這是我第一次裝學術逼，所以希望大家輕撕。。哦。哦。。。疼疼疼。。。?

???再者往往評論中總會有人憑著臨時百度或者谷歌幾下，就固執的堅持一些自己的看法，把評論拉向「民科式」的討論之中，這是我不願看到的，我希望看到的是小姑娘們說「哇，作者好帥，好厲害。」 所以希望諸位大神們靜靜地成全我裝逼的夢想！

回到正題，對於我們這個比較GPA的問題：

我們的目標是設計一個協議能夠正確地比較出兩者的大小，而且保證這個結果不會被任意一方欺騙。我們的要求有兩點：一是不能求助於第三方，二是不能讓對方知道自己的GPA，更為特別的說是除了讓對方知道自己的GPA比他大還是小之外，不能透露出任何有助於對方得到自己GPA的信息（事實上，這種說法和前面那種說法是等價的）。關於這點我們後面如果有機會，會給出一個更為嚴謹的定義，也就是基於零知識性的定義。

有了以上的要求，我們先來看看大家的一些常見想法為什麼會不滿足要求。

第一種很常見的方法：比如可以比排名，找人編程序輸入讓計算機比，還有每個人配置自己GPA重量的溶液放在天平上比。但這些方法都引入了一個「可信任」的第三方。這裡面排名的人，計算機程序，還有天平都成了「第三方」，而且他還要求比較GPA的兩個人必須「信任」第三方，也就是說無論程序也好，天平也好，你要相信比較的結果是正確的，而且他們不會把你的GPA再透露給別人。就好比，我怎麼相信你找來的天平一定是公正的？我怎麼相信你寫的程序不會把我輸入的GPA記錄下來。所以這和我們的要求不符。

第二種常見的方法是找一個隨機值來比較，有同學提出了一個很好的想法：??

直接約定二分法說數，然後告訴對方這個大了還是小了就行了。比如不妨設gpa滿分4.0。第一個數就取2.0，兩個如果說的不一樣，問題終止。如果都說大了，就取3.0，都說小了就取1.0，總能收斂。

顯然這種方法會透露出更多有利於對方推測出自己GPA的信息，為了便於理解，這種方法其實是在逐比特的向對方揭露自己的信息，假設A和B兩人都把自己的GPA寫成二進位，顯然每個GPA都是小數點前只有兩位的的一個二進位數，那麼第一步比較和2的大小，其實就是在告訴對方自己第一位的數字是0或1，0代表比2小，1代表比2大，然後再和1或3比較，就是在告訴對方自己第二比特的數字是多少，直到兩人有一位數字不同，則比較出大小。這種方法會更多有利於對方推測出自己GPA的信息，比如說每個人的GPA都能換為一個十位的二進位數，那麼你想憑空猜測一個人的GPA，猜對的可能性是1/1024，但是在這種比較的情況下，你會透露出若干比特的值，從而導致對手猜對的可能性會增加。而零知識性要求，對方憑空猜和你提供一定量信息之後對方再猜，猜對的可能性是一樣的，或者至少概率分布是計算不可區分的，也就是說你提供的多餘的信息對對手應該沒幫助。基於零知識的安全計算是87年 goldreich, micali 還有wigderson提出來的。

但這還不是這個方法最關鍵的問題所在，這裡最關鍵的問題在於這種方法對一方是不公平的，有一方能做到欺騙。

比如現在有A，B兩個人，他們拿出3來做比較，A告訴了B他的GPA比3高，假設B的GPA比3小，這時他就已經知道了結果：自己的GPA比A低，但是這時B變地陰險起來：

他開始了欺騙的策略，他告訴A自己的GPA比3高，然後後邊不論他們拿出什麼樣的中間值，B都說自己的GPA比這個中間值高，那麼最後A就一定會得到A的GPA比B低的結果。顯然B欺騙了A，他自己知道了正確的結果，但是A卻得到了錯誤的結果。（事實上，Yao最初的協議也存在這個問題，一方會比另一方優先知道結果，不過在更強的假設下，他證明了一方成功欺騙另一方的概率存在一個上界）。

回到上面的問題，上面之所以能夠欺騙的關鍵在於A和B兩個人沒有同時告訴對方自己的GPA比中間值大還是小，而是一方先告訴，另一方又告訴的。試想如果每次都是A先說，然後B再說的話，只要每次B和A說一樣，你說大我就說大，你說小我就說小，那麼B總能把A的GPA給算出來。所以我們要想辦法做到讓A和B同時說，那麼怎麼做到呢？這個問題就是「bit commitment」， 它也有個腦洞很大的例子就是「toss coins over phone」。

說那個例子之前，我們先說一個大家更熟悉的例子，小時候大家都玩過「剪子包袱錘」，我們很多時候會陷入這樣一種爭執，一方會懷疑另一方是「慢抻手」，也就是說你是看了我出了什麼之後，你才出的手，而被懷疑的一方也無法證明自己的清白。當然這種問題也可以去找一個可信任的第三方，A和B分別把自己想出什麼寫到紙上，然後把自己寫的都交給C，然後C同時公布A和B寫的內容，顯然這裡還是要求C可信任，C不能偷偷的更改A和B寫好的值。那麼能不能我們不引人第三方C呢？

如果我們的A和B是面對面的，顯然可以不引入C，A先把自己想出的寫到紙上，然後翻過來不讓B看到，然後和B說我已經寫好了，這時B告訴A自己打算出什麼，然後A當著B的面掀開自己寫在紙上的東西，然後A和B就可以愉快的玩耍了。在這樣一個交互中，「比特承諾」的思想就已經顯現出來了，為了方便說明，我們把「剪子包袱錘」的遊戲換成「黑白剪」，就是說每次伸手，手心朝上或者手背朝上，因為這個遊戲是「二進位」的，我們把0記為手心，1記為手背。A向B承諾A已經給出了一比特的信息（手心0或手背1），並且A能讓B相信A的承諾（寫在紙上了），但又不能讓B知道自己的比特（把紙翻過來）。B在相信A做出承諾之後，給出自己的比特，然後A揭示自己的比特值與B比較。顯然當A和B面對面的時候，可以通過寫在紙上再掀開來實現。可是如果A和B不是面對面，而是打著電話玩「黑白剪」要怎麼辦？

我們想想上面「面對面」協議的關鍵地方在什麼？A把自己的值寫在紙上，把這個紙翻過來給B，此時B不能夠通過這張翻著的紙得到A寫的值。但是他能相信A已經寫了，這時他把自己的值告訴A，A也把自己寫下的值告訴B，然後進行比較，可是如果A告訴的B的值和A前面寫下的值不一樣怎麼辦？所以這時我們要求B能夠驗證A說的值是不是A剛才寫下的值！ 那麼怎麼用計算機來模擬這個過程呢？單向函數，這個現代密碼學中最最關鍵的概念呼之欲出，（當然了單向函數的概念並不是為了解決這類問題才提出的，只不過單向函數幾乎能用於現代密碼學的各個方面。）

簡單的講，單向函數就是這樣一個函數f(x)，告訴你定義域上的任意x，f(x)總是可以容易求出來的（多項式時間求解），但是對於值域上的絕大多數y，在沒有別的信息的幫助下，你是很難找出他的一個原象(多項式時間內解不出來)，（如果存在一個信息，只要有個這個信息就很容易求逆的話，這就叫作這個單向函數的陷門）。關於單向函數嚴謹的定義，後面有機會的話會給出。顯然的，單向函數的存在是基於P!=NP的假設，同時又是強於P!=NP的，事實上整個現代密碼學可以說都是基於計算複雜度的，當然這一部分更多被稱為密碼學基礎，和應用密碼學還有一些區別。Goldreich 有一本書《foundations of cryptography》，非常非常好的書，有興趣的可以看看。這本書還有一個中文譯本，也正是這個中文譯本讓我知道翻譯的書究竟能爛到什麼地步，我甚至看不懂譯本上的每個詞的意思，我覺著譯本連最基本的通暢都做不到，有興趣的也可以看看。

這裡多說一句，關於單向函數，最有名的應用應該是RSA公鑰密碼了，事實上，馮諾伊曼在很早就提出來過單向函數，Rabin就曾用單向函數解決過加密的問題。差不多也正是自Rabin起，理論計算機科學開始真正蓬勃的發展起來，而這個方向也算是整個CS裡面最重要的方向，自76年Rabin獲圖靈獎以來，不到四十年間，9次都是頒給計算機理論方向的，共計14人，這還不包括像hopcropt這樣做演算法獲圖靈獎的。順便說一句這其中猶太人至少有四個。圖靈獎第二多的方嚮應該是人工智慧方向，共計4次6人獲獎。可見計算理論這個方向在CS中的重要性，不過國內並沒有太多人做這個方向，除了清華有姚期智撐起來的，及上交的致遠學院。當然，隨著清華姚班這些年的發展，如今國內高校理論方向也開始開枝散葉起來。

作者本科所在的學校並無老師從事相關方向的研究，我屬於七拐八拐，誤打誤撞入坑的。當然了，這個方向也是最壞的方向， It is very hard to get a good job as a pure theoretical computer scientist nowadays. 這是我拒掉一個從計算機理論轉去做密碼學的老師的時候，那個老師說的。

回到正題，下面我們來看看怎麼用單向函數來實現電話上玩」黑白剪「的問題，a表示A所選的一個n比特的值，f(x)表示一個一對一的單向函數，那麼A只需把f(a)的值發給B，由於f是單向的，B不能通過f(a)求出a, 然後B把他的值b發給A，A收到之後把A選的值a發給B，這是B就可以通過計算f(a)驗證這時A發來的這個值a，是不是一開始選好的那個a。

當然了，上面的只是一個大致的模擬，如果a是一個1比特的值，因為1比特是很容易求逆的，我只要把兩個值0和1試一下就知道了。所以此時A要發一個n比特的而不是1比特的，然後通過兩個n比特的求內積來確定自己的1比特的值。

那麼回到我們最最一開始的問題，究竟要怎麼樣才能比較出兩個值的大小呢？顯然我們需要利用單向函數，有同學提出來了一個非常好的想法：

「尋找到一個與GPA正相關的函數，並且這個函數的逆函數十分複雜，幾乎不可解析，數值計算也很麻煩，找到這樣的函數不就差不多了嗎。」

這個同學已經有了單向函數的概念，但是有兩個問題：

1，保序的函數，或者說單調的函數一定不可能是單向的，因為可以用二分法確定出來原象，比如說定義域是[0 X]，則通過比較y和f(X/2)的大小，就能判斷y的原象在[0.X/2]，還是[X/2,X]，以此下去，只需要做log X次，這是X的規模|X|的多項式函數，所以這樣的函數，一定是多項式時間內可逆的。

2，即使存在這樣一個函數，這個函數也必要要靠可信任的第三方來提供，所以，還是不行。

關於這個問題的一個原始的協議，大家可以參考Yao的文章http://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf 的3.1部分，我有空再細說。

這篇文章所提出來的最最關鍵的問題就是前面說過的安全多方計算的問題，舉一個更直觀的例子，就是說有那麼一群人，每個人都不想讓別人知道自己的工資是多少，在這樣的一個情況下，怎麼把這些人的平均工資算出來？

先把這個問題留給大家想想，有空再寫吧。