兩個(gè)百萬富翁都想比較到底誰更富有，但是有都不想讓別人知道自己有多少錢。在沒有可信的第三方的情況下如何進(jìn)行？
這個(gè)問題就是著名的姚式百萬富翁問題。姚式，即大名鼎鼎的姚期智，我國(guó)唯一一個(gè)圖靈獎(jiǎng)獲得者，此問題開創(chuàng)了安全多方計(jì)算領(lǐng)域，在如今，以區(qū)塊鏈為先導(dǎo)的一系列可信（Trustless）架構(gòu)中，多方計(jì)算問題是建立機(jī)器信任的關(guān)鍵技術(shù)之一。
簡(jiǎn)化問題
為了簡(jiǎn)單描述問題，我們假設(shè)兩個(gè)富翁的財(cái)產(chǎn)在一千萬到一億之間，而且他們也只想做千萬級(jí)的比較，也即每個(gè)人只在乎是否在千萬級(jí)別上誰更多。問題簡(jiǎn)化為：
兩個(gè)富翁，分別為張三和李四。他們自己都清楚自己有幾千萬財(cái)產(chǎn)，也即，他們心里清楚 1～10中的一個(gè)數(shù)（代表自己千萬級(jí)的財(cái)富）；他們想知道到底誰的數(shù)更大一些。
這里假定：
- 兩人都值得信任，不會(huì)作假
- 兩人都希望誠(chéng)實(shí)地比較出誰更服務(wù)（即誰的數(shù)更大）
- 兩人又都希望知道對(duì)方財(cái)產(chǎn)到底是多少，如果可能的話，拿到具體數(shù)字最好了
其實(shí)這里假定的是一個(gè)安全多方計(jì)算的模型 - 半誠(chéng)實(shí)對(duì)手模型，即計(jì)算方存在獲取其他計(jì)算方原始數(shù)據(jù)的需求，但仍然按照計(jì)算協(xié)議執(zhí)行。另外有惡意敵手模型，在這種模型中，參與方可以造假，即不按照計(jì)算協(xié)議執(zhí)行計(jì)算過程。這就要復(fù)雜很多。為簡(jiǎn)化期間，本文僅討論半誠(chéng)實(shí)對(duì)手模型。
一個(gè)”解決方案”
有人提出這樣一個(gè)解決方案：放一個(gè)天平，兩邊放上封閉的盒子，讓兩個(gè)富翁分別在兩邊放入質(zhì)量相同的蘋果，有幾千萬財(cái)富就放幾個(gè)，最后看哪邊重就可以了。就這么簡(jiǎn)單。
真的這么簡(jiǎn)單么？這里方案的提出者忽略了一個(gè)條件，也就是不存在可信的第三方，天平誰來提供？提供天平者是可以知道一切的。
這是一個(gè)看似簡(jiǎn)單實(shí)則非常復(fù)雜的問題。
不經(jīng)意傳輸?shù)慕鉀Q方案
這個(gè)問題在數(shù)學(xué)上，必須借助于密碼學(xué)。不經(jīng)意傳輸是解決這個(gè)問題的絕妙方案。
那么什么是不經(jīng)意傳輸呢？拿這個(gè)例子來說，就是張三給李四提供 n 個(gè)選擇，這n個(gè)選擇對(duì)李四而言都是無法分辨的（即無法獲知原始內(nèi)容的），李四從中選擇一個(gè)并告訴張三。但有趣的是，張三不能知道李四選擇的是哪一個(gè)。這個(gè)有點(diǎn)難了吧。
回到百萬富翁問題，一個(gè)簡(jiǎn)單的解決方案就是一下步驟：
- 張三找10個(gè)一模一樣的箱子，按照1～10的順序擺好，并按照自己的財(cái)富值分別往里面放入蘋果梨和香蕉，具體放法為：如果序號(hào)小于自己的財(cái)富之，放入蘋果，相等，則放入梨，大于自己的財(cái)富值，放入香蕉；
- 把10個(gè)盒子都叫上鎖；并叫李四過來（或者寄給李四）
- 李四根據(jù)自己的財(cái)富值對(duì)相應(yīng)的箱子再加一把鎖。然后把其他所有箱子銷毀。并把這個(gè)選擇的箱子送給張三。
- 張三看到送回來的箱子，但他不知道李四選擇的是第幾個(gè)箱子，因?yàn)槊總€(gè)箱子都是一樣的
- 張三李四分別開鎖，看里面是什么水果：
-- 如果是蘋果，張三比李四富有；
-- 如果是梨，兩人一樣有錢
-- 如果是香蕉，李四比張三富有
簡(jiǎn)單吧，可行嗎？當(dāng)然可行！前提是雙方都是可信的，雙方會(huì)遵守協(xié)議，所以這是一個(gè)半誠(chéng)實(shí)對(duì)手模型。如果有一方造假，那么結(jié)果就不可信了。那是惡意敵手模型要討論的問題。
密碼學(xué)的解決方案
上文中所述的方式在算法中如何實(shí)現(xiàn)呢？這就要借助密碼學(xué)了。覺得密碼學(xué)太麻煩的同學(xué)可以略過以下部分。
無需不經(jīng)意傳輸?shù)慕鉀Q方案
同樣，對(duì)此問題進(jìn)行抽象化，其實(shí)就是兩個(gè)數(shù)的安全比較大小問題，以確定哪一個(gè)較大。張三知道一個(gè)整數(shù)i，李四知道一個(gè)整數(shù)j。張三和李四希望知道究竟是 i<=j 呢還是 i>j，但都不想讓對(duì)方知道自己的數(shù)。為簡(jiǎn)單期間，假設(shè) i 與 j 的范圍為 [1, 10]。李四有一個(gè)公開密鑰Eb與私有密鑰Db。
- 張三選擇一個(gè)大隨機(jī)數(shù) x，并用李四的公開密鑰加密：
c = Eb(x) - 張三計(jì)算 c-i， 并傳送給 李四
- 李四 計(jì)算下面的 10個(gè)數(shù)：
Yu=Db(c-i+u) , u[1, 10]
并取一個(gè)大素?cái)?shù) p (p 比 x 稍小，李四不知道x，但張三可以告訴李四 x 的大小范圍），計(jì)算：
Zu=Yu mod p , u屬于[1, 10]
這里需要驗(yàn)證：
對(duì)所有的 u 下式成立： 0<Zu<p-1
對(duì)所有的 uv: |Zu-Zv| >= 2
如果不成立，選擇另一個(gè)p，重新計(jì)算
注意： 這里有一個(gè)顯然的性質(zhì)： Zi=x mod p - 李四將以下數(shù)列發(fā)給張三：
{Z1, Z2, ... , Zi, Zj+1+1, Zj+2+1, ... Z10+1 } - 張三驗(yàn)證這個(gè)數(shù)列的第 i 個(gè)數(shù)是否與 x mod p 相同，如果相同，則 i<=j, 否則， i>j。
- 張三把這個(gè)結(jié)論告訴李四。
不經(jīng)意傳輸
不經(jīng)意傳輸本身是一套協(xié)議和算法。相對(duì)比較復(fù)雜。其基本原理還是基于密碼學(xué)，基于大數(shù)分解的復(fù)雜性或離散對(duì)數(shù)解的復(fù)雜性。一般在一個(gè)有限群中進(jìn)行。具體這里不贅述，有興趣的自行g(shù)oogle。
在不經(jīng)意傳輸?shù)闹С窒?，上述方案可以?jiǎn)化為以下版本：
- 令 X = {1,2, … , 10}, R=Pi(X) 是 X的一個(gè)隨機(jī)置換。李四計(jì)算下面的10個(gè)數(shù)，得到一個(gè)數(shù)組 Y = {Y1, Y2, … , Y10}, 其中：
- Yi = g(i, b) = 0 + Ri, 如果 i==b
- Yi = g(i, b) = 10 + Ri, 如果 i > b
- Yi = g(i, b) = 20 + Ri, 如果 i < b
- 利用不經(jīng)意傳輸，張三能夠選擇她愿意得到的唯一的數(shù) Ya=g(a,b)。不經(jīng)意傳輸方案保證了張三可以決定要得到的唯一的數(shù)，而李四并不知道張三選擇了哪一個(gè)數(shù)。如果Ya<10，則：a==b; 如果 10<Ya<=20, 則： a>b; 如果 Ya>20， 則 a<b。
- 張三將結(jié)果告訴李四
看，是不是跟我們的水果解法比較類似呢？
拓展
百萬富翁問題可以說是安全多方計(jì)算的最基本的問題了。無論從方案還是算法復(fù)雜度而言，都不簡(jiǎn)單。但是，這里看到了通過安全計(jì)算做比較和加法的方案?？紤]到所有的算法實(shí)現(xiàn)都是最后眼花成計(jì)算機(jī)門電路，那么把一個(gè)算法轉(zhuǎn)換成電路（與，非，異或等），那算法就是這些簡(jiǎn)單的操作的組合了。這就為復(fù)雜的安全計(jì)算推開了一扇門，盡管需要突破的技術(shù)難點(diǎn)還很多，實(shí)現(xiàn)和優(yōu)化還有很長(zhǎng)的路要走，但相信在計(jì)算能力日益強(qiáng)大的今天，在需求的拉動(dòng)之下，會(huì)很快迎來突破。
