兩富人比誰錢多。如何能實現互相保密但可以比出誰錢多？

01-25

兩個富人想比較誰的錢多，他們之間可以發送任何信息，但不能告訴對方自己有多少錢。比較苛刻的是，他們也不能說自己大致有多少錢（諸如大於1000小於2000）。請問要如何實現？方法是否有優劣？這種保密的演算法或者通信方法應用前景如何？

搜：安全多方計算，基礎是 RSA 的不經意傳輸

Update:評論里 @菜魚ftfish 提到這個是著名的姚氏百萬富翁問題

有一些比較成熟的解法...

以下為原回答..班門弄斧了.&>&>逃

這個問題必須有第三方公證,兩個人是搞不定的.

假如存在這麼個過程,可以抽象成函數 $f(x)$

使得 $f(x_1)>f(x_2),forall x_1>x_2$

也就是說 $f(x)$ 是個隨機單調遞增函數.

那麼鮑伯知道了愛麗絲說的 $f(x_1)$ 後就能用二分窮舉法在 $O(log_2x)$ 時間內反推出 $x_1$ .

當然你要說第三方公證,我不信任公證人怎麼辦...

公證又不一定要是人...

計算機不行嗎...

想像有這樣一個邪惡賭博遊戲,兩人比出錢多少,出錢多的人能把錢全拿走...

所有玩家的信息都儲存在伺服器特倫特(Trent)上,沒有人能漫天要價,比如自己只有10萬卻報100萬.

兩位參與者分別在自己的手機上填上出價後會發送到伺服器,伺服器進行判定...

那麼問題來了,輸的人會很不服氣...

我怎麼知道這個演算法寫的不是

For All ; Return["A win"]

演算法必須公開!

好的,現在可以了嗎...還是不行...

這個遊戲不只有愛麗絲(Alice)與鮑伯(Bob)在玩,還有邪惡的伊夫(Eve)也在玩這個遊戲,她能監控網路上的流量,如果明文傳送的話,就統統泄露了!

解決方案也很簡單,非對稱加密傳輸唄...

按照如圖規則生成一對公鑰和私鑰.

Alice 看到了公證人Trent發布的 $(N,e)$ 的值

於是她就可以加密自己的密文了:

$明文(A)equiv n^e pmod{N} =520^{635} mod 2279 =1970$

你要問了,這麼大的數不會爆炸嗎,當然不會,有個叫快速冪模的演算法可以輕易得到這個值.

Bob也看到了,Bob按照同樣的方法計算

$明文(B)equiv n^e pmod{N} =1314^{635} mod 2279=99$

然後他倆把這個值都發給Trent,Eve雖然知道了他們傳輸的內容,但是她不知道 $(p,q)$ 就沒法反推出 $n$ .

注意現在還沒有一個有效的因式分解演算法,實際應用中 $(p,q)$ 是個幾百位的大數,原則上不可破解...

Trent 收到了兩人的信息,然後用私鑰反推密文.

$密文(A)equiv 明文(A)^d pmod{N} =1970^{227} mod 2279 =520$

$密文(B)equiv 明文(B)^d pmod{N} =99^{227} mod 2279 =1314$

Trent 看了下 $520<1314$ ,而且查了下Bob的賬號確實有1314元,所以把 Alice 判給了 Bob...

一切演算法都是公開的, 用到的數字都是隨機的,輸的人願賭服輸,沒有第四方泄密,那麼就宣布故事贏來圓滿結局啦...

姚期智的百萬富翁演算法

專欄上看到一篇介紹還挺清楚的知道了這個方法，兩個人不需要裁判就能玩暗軍棋

這篇文章寫得很清楚了：知道了這個方法，兩個人不需要裁判就能玩暗軍棋

簡單的說，分為三步：

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

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

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

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

首先，李選取一個隨機的大整數 x ，把 x 用王的公鑰加密，得到密文 K 。李發送 K-j 給王。
王收到密文 c=K-j 之後，對 c+1,...,c+10 進行解密，得到十個數字。再選取一個適當大小的素數 p , 把這十個數字除以 p 的餘數記作 d1,...,d10.
注意：這十個數字看起來應該是完全隨機的，關鍵是等式 dj=x mod p 成立。

第一步是整個過程的點睛之筆，由非對稱加密實現的。李通過用王的公鑰加密，得到K，但是發送 K-j 給王。這時候王知道李能夠解密c+1,...,c+10中的某一個(第 j 個)，但是並不知道 j 是幾。

最後，王對這一串數字作如下操作：前面 i 個數不動，後面的數字每個加一，然後發回給李。
這樣一通複雜的操作之後，李檢查第 j 個數字。如果等於 x mod p 的話，說明這個數字沒有被加一，所以 i &>= j. 反之，則 i &< j。

第二步，因為李只能解密第 j 項，也就是只知道 dj, 對 d1 到 d10 中的其他項一無所知，這時候把前 i 項不變，後面的加 1，發回給李。李只能知道 dj 是否被加了1，通過這個信息判斷兩者大小關係。

姚期智在1982年提出的百萬富翁問題應該是開創了安全多方計算的先河，後面湧現了茫茫多的協議演算法，比較常見的是利用同態加密來實現。

舉個實際例子，比如Paillier加密演算法就具有比較好的同態屬性：

$E(m_1,r_1) cdot E(m_2,r_2) = E(m_1+m_2,r_1+r_2)$

$E(m,r)^C=E(m cdot C,r cdot C)$

我們可以用它來設計具體的比富協議(假設 Alice 財富是 $a$ ，Bob的財富是 $b$ )：

第一步：Bob生成兩個非常大的隨機正整數 $x$ 和 $y$ ，但是並不公開只有他自己知道；

第二步：Alice生成一對屬於自己的密鑰(公鑰是pub，私鑰是pri)，用公鑰加密自己的財富的到 $E(a)$ ，並將它和公鑰一起公布出去；

第三步：Bob得到Alice公布出來的數據以後，首先用Alice公鑰計算出 $E(b cdot x+y)$ ，然後用Paillier演算法的同態屬性計算出 $E(a cdot x+y) = E(a)^x cdot E(y)$ ，並將這兩個結果也公布出去；

第四步：Alice得到Bob公布出來的計算結果以後，用自己的私鑰分別反解出 $A = a cdot x+y$ 和 $B = b cdot x+y$ 的值。Alice雖然對 $x$ 、 $y$ 和 $b$ 一無所知，但她只要比較 $A$ 和 $B$ 的大小就行了。而對於Bob來說，他對 $A$ 、 $B$ 和 $a$ 也是一無所知，如果他也想要知道相對大小，要麼Alice告訴他，要麼把角色對換重新執行一遍協議即可。

這個方法有效的前提是Alice和Bob都會誠實地執行協議，關於如何防止他們作弊而使得比較結果是可驗證的，可以參考李向陽他們在2013年發表的一篇論文，當然具體細節會比上述協議稍微複雜一些。

這種不泄漏自己信息比較大小的演算法有什麼實際應用？一個很直觀的應該就是在線拍賣，所有的競價方希望決出一個最高競價(或者第二競價)但是並不希望頻繁泄漏自己的競價策略。另一方面來講，比較大小只是同態加密的一個非常非常小的應用方向，很明顯如果擁有全同態的加密系統，我們可以很放心地把數據加密然後交給別人計算，然後把他計算出來的結果解密即可而不用擔心原始數據泄露。不過很遺憾Paillier加密系統不具備這種性質，不過處理比富問題剛好夠用了。

最後寫了段簡單的Python程序來模擬了整個過程：

#!/usr/bin/env python


from paillier import *

from primes   import *
# Bob

b = 2333333

x = generate_random(100)

y = generate_random(128)
# Alice

a = 2578466

pri, pub = generate_keypair(512)

E_a = encrypt(pub, a)

print("Alice: pub =", pub)

print("Alice: E(a) =", E_a)
# Bob

E_bxy = encrypt(pub, b*x+y)

E_axy = e_add_const(pub,

    e_mul_const(pub, E_a, x), y)

print("Bob: E(b*x+y) =", E_bxy)

print("Bob: E(a*x+y) =", E_axy)

# Alice bxy = decrypt(pri, pub, E_bxy) axy = decrypt(pri, pub, E_axy) print("Alice: b*x+y =", bxy) print("Alice: a*x+y =", axy)

以下是輸出列印(應該很直觀了吧)：

Alice: pub = & Alice: E(a) = 4968512766090949180669170559957452717494049844479002110445123942551676679906252413711009624735729906635967551926069731416878655716309624313367185335551492246695219172804484937096244634803236873292495605021741681328394185268831677160127700775541140435576607127972386587900675971625862609134341949097306109694 Bob: E(b*x+y) = 78069472270630060916606096600507250169159579661207403128669332538535612717207871265810735387655792138231410905886798136066046955699948551501839777500559977007762158634331881486742617837691582987876994902606739653098544230039086128371956175439177761045082327247819561763324114826997271075910092429003392478 Bob: E(a*x+y) = 104561632080136594066348339301905599982191403947698856626743680045058520250858370819374335554314580722136907382008024868484633580579612028150379242570803004867721472194721685344550543943705587829046277503121661431237459322367517951428419482725455956873466560779025879725945654431808048866844777222317703313 Alice: b*x+y = 25176283170138758568634968198123146770 Alice: a*x+y = 25200844139169272487711888736752166063

姚氏百萬富翁的那個函數可能是一個簡化解法。

但姚氏百萬富翁問題，是否泄露了額外信息呢？從理論上來說， $|X|>>|Y|$ 意味著儘管我無法推算出具體的數值，但是我們可以知道大致的數值範圍呢。

舉例而言，假定A取數15，B取數5。 $[15]_{10}=2,[5]_{10}=1$ ，但在這種條件下，A知道B的範圍為1~9，而B知道A的範圍在10~99。這是否也算是一種信息泄露呢。

考慮到信息的保密特性，比較函數設計最好是一個階躍函數。即 $N_A$ &> $N_B$ 時，A只知道 $N_Bin(-infty,N_A)$ ，同理B也僅知道 $N_Ain(N_B,+infty)$ 。如果在強假設條件下，則本答案給出的方法也有一定的適用範圍。

——————以下為原答案——————

原命題相當於：已知A和B兩人隨機定兩個數字比大小，求一種方法，使得二人可以比較數字Na和Nb的大小，且大的人知道對方比自己小，此外不知道任何信息，反之亦然。

這是一個盲比較問題。

（1）考慮A，B均為君子的情況下。

這裡應用通信界一個定理（奈奎斯特採樣定理）：

為了不失真地恢復模擬信號，採樣頻率應該不小於模擬信號頻譜中最高頻率的2倍。

也就是說，如果信號頻率為 $f_A$ ，而採樣頻率為 $f_B$ ，則只要 $f_A>f_B$ ，則無論如何也無法恢復出信號，反之，則總能完美的恢復出信號。

這裡假定A採用一段波形作為信息，用自己的數字Na作為基帶頻率進行發送。而B採用自己的頻率Nb進行採樣後恢復。

如果B可以完整的恢復出這段波形，那麼就有B的數字較大，反之，則A的數字較大。

但是在這種情況下，信息的發出者為A，信息的比較者為B，相當於B從整個過程中獲得了信息，因此，B可以採用牛頓法等類似的方法去得到A的頻率信息。同時，整個比較環節中，大小信息最後是由B通知A的，如果B刻意隱瞞，則A絲毫不知。

（2）假定A，B均為小人，即他們不希望給出自己的信息，但是希望獲取別人的信息。

為了避免A，B能夠互相知道對方的信息，通過不斷嘗試逼近對方的頻率，這裡將直接限制信道所能發出的信息量，確保雙方僅能收到有且僅有的一位比較信息。

A採用固定頻率 $f_A$ 生成一段模擬信號 $A_A$ ，B在接收時不獲得模擬信號，而是採用一個 $f_B$ 的矩形窗濾波器預處理，且B只獲得用 $f_B$ 採樣得到數字信號 $D_B$ ，用 $f_B$ 進行恢復得到模擬信號 $A_B$ 。且對形成的信號 $A_B$ 進行標準採樣，標準由雙方協商確定，採樣後進行MD5（或者其他等價變換），將MD5結果發回給A，A在接收後同樣採用標準採樣對原信息進行採樣，將原信息的MD5與新信息的MD5相比較，如果一致，則B的數字比A大，反之，A的數值較大。對B，同樣有此結論。

這裡用濾波器的技巧，將矩形窗濾波採樣恢復重新標準採樣設計成【一個濾波器】，使之對B形成黑箱，B所要做的就是輸入 $f_B$ ，剩下啥都不知道，啥也不能做，信息就自動發出去了。B最多就做一個MD5（考慮複雜性，B連這個也可以不做）。

形象化的比喻是，A站在B前面，B選了一個哈哈鏡，A看不到哈哈鏡的型號，B被哈哈鏡擋住，看不到A也看不到A的像，但A可以知道哈哈鏡是變大了還是變小了。

此時，比較者為信息的發出者A，整個過程中，B對信息是盲的，因此信息不在B處泄露。由於A無法獲知B給出的原始信息，而A僅知道B給出的MD5是否與自己相同，相當於B所傳送的信息只有1位的比較信息，因此A也無法得知B的額外信息。

其實考慮的更複雜一些，MD5還是可能會出現碰撞的，因此，我們完全可以採用任一隨機的無窮域到無窮域的一一映射。由於是隨機映射，A從B處所得到的任意信息本質只有1位，即信息的「一一映射」是否在兩處相等，也即只有1位信息「誰大」，其他的額外信息則完全消失。由於是無窮域到無窮域，因此也無法出現窮舉獲知原信息的可能。

（3）演算法拆解

這個演算法的核心思想在於資訊理論的自由度不對稱特性，即，低自由度發射機的信息能被高自由度的接收機完美接收，但反之不可。在這種情況下，加入MD5或無窮域到無窮域的隨機一一映射只是為了採用隨機性掩蓋住額外信息，僅僅保留「一一映射」的這個特性。

這個題目與加密問題不同在於，加密問題是一個無損的過程，最終加密結果需要被無損的恢復。而本題目中，A或B只需要知道1位信息（0/1）即可知道誰更大。因此，在加密過程中可以只保留1位信息。而同理，由於「誰更大」這個信息佔用了1位，因此，當加密後僅傳輸1位信息的情況下，是可以保證其他信息完全丟失的。

這個方法相較於姚方法在於改變了信道條件，原始題目中為自由信道（無限自由度信道），但是在這個方法中，人工將信道進行設限，即A只有fa以下的信道，B只有fb以下的信道。

某種意義上，這個方法可以等效A發出一束激光，而B對光進行濾波，A通過反射光和原始光線能否干涉來判定B定的濾波頻率與光的頻率是否相同。判定位只有1位，即是否發生干涉。B只能改信道，A只能發光並只收穫1位判定位。

當然，上面的激光實驗現實中是不可能實現的，只是說給出的方法某種意義上等效於上述的思想實驗。

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

兩人以自己的錢除以一個約定值為濃度配置強酸/鹼溶液，混合後以非定量方式測試ph。

1982年，姚啟智教授在提出百萬富翁問題後就給出了該問題的一種解決方案。該方案用於對兩個數進行比較，以確定哪一個較大。Alice知道一個整數i；Bob知道一個整數j, Alice與B0b希望知道究竟i&>=j還是j&>i，但都不想讓對方知道自己的數。為簡單起見，假設j與i的範圍為[1，100】。Bob有一個公開密鑰Eb和私有密鑰Db。

百萬富翁問題協議一

(1)Alice選擇一個大隨機數x，並用Bob的公開密鑰加密c=Eb(x)；

(2)Alice計算c—i，並將結果發送給Bob：

(3)Bob計算下面的100個數：Yu=Db(c-i+w), u=1，2，．．．，100 其中Db是Bob的私有解密密鑰。B0b選擇一個大素數p(p應該比x稍小一點，Bob不知道x，但Alice能容易地告訴他x的大小)，然後計算下面的100個數：Zu=(Yu mod p), u=1，2，．．．，100。然後驗證對所有的u≠v, |Zu-Zv|&>=2，並對所有的u驗證：0(4)Bob將以下數列發送給Alice：Z1，Z2，．．．，Zj，Zj+1+1．．．，Z100+1，p；

(5)Alice驗證這個數列的第i個數是否與x模p同餘。如果同餘，她得出的結論是i&<=j;如果不同餘，她得出的結論是i&>j;

(6)Alice把這個結論告訴Bob。

或者還聽說過一個有趣的方法，就是每個人按照一定的換算調製不同PH的酸鹼試劑，比如一位調酸性，一位調鹼性，然後將兩種試劑混合，最後使用試紙，如果試紙紅色，則說明酸性更強，藍色則說明鹼性更強，以此達到比較目的。

怎麼感覺是零知識證明？zcash用的技術

Yao"s Millionaires" Problem

你需要全同態密碼學。

你這個問題，問的非常好，同時需要零知識證明，同態加密，和多方安全計算，要完美的回答估計有極大的難度，等大神來解答

哎，真丟臉，這題其實不需要同態加密，自己之前題目沒看對，丟人呀

這是安全多方計算的一個著名問題，劉木蘭的那本書最後一節有詳細的介紹

看到各位數學大佬用數學方法來解題，小白就來抖個機靈，權當狗尾續貂了。

首先這裡的富人比誰有錢應該是比較的總資產，而非持有現金。

那麼倆人就得找同一個專業人士以統一的標準做個資產評估，標準要統一，不然就沒法比較。

此時倆人就知道了一個具體的數字，並得到一份個人資產證明。

倆人約定拿著這個證明去黃金市場按同一個非常小（如1:1億）的比例去質押得到黃金。

然後就祭出亘古以來作比較的神器——天平。

然後就不用我描述了吧。

—————————————————————————

其實個人覺得這裡比較的實質就是比較兩個人擁有的所有有價的資源，錢或者說貨幣只是一種價值尺度。

我第一時間就想到了天平兩邊直接放錢比，但是兩個人太富有了，其資產也不可能全部套現，就算套現了也不好找一個無限大的天平。於是就得想辦法按比例縮小再比較。

然後天平最終比較的還是重量，黃金的價值的衡量尺度也是重量，（比貨幣的重量更加規範）且黃金是貴金屬的代表，所以選擇了質押得到黃金再放天平上比較。

艷紅：來我們比比誰有錢，但不能說出來自己有多少錢，你有什麼辦法嗎

碼云：很簡單哈，說福布斯國內排名唄，你多少

艷紅：我第5

碼云：哈哈，我第一

我竟然不知道姚氏百萬富翁演算法。

尷尬了，哈哈哈

就題目而言，不停設置購買物給他們兩個，直到有一方買不起為止。

在演算法上的應用...... 加權值的做法吧。