前言
想象一下兩個富豪想要知道誰更有錢，但是誰也不願意說出自己有多少錢。這種情況下如何比較呢？這其實就是經典的百萬富翁問題。在不暴露彼此隱私的情況下，如何進行加密對比呢？
背景
上世紀80年代，姚期智院士提出了“百萬富翁”問題。這個問題引出了密碼學的眾多研究。而隱私保護作為聯邦學習系統中最重要的特徵，引用了許多加密算法，如同態加密，差分隱私，DH算法，混淆電路以及國密SM算法等。本文將結合部分加密算法，對此問題給出解釋與答案。
加密與解密
這部分簡單介紹加密與解密，以幫助後面的理解。
加密分為對稱加密和非對稱加密，對稱加密即只有一個密鑰，你可以用這個密鑰去加密所需要的信息（明文）獲得密文，同時也可以利用該密鑰對密文進行解密獲得明文。非對稱加密則是有公鑰和私鑰之分。公鑰常用來加密信息，而獲得的密文只能用對應的私鑰來解密。比如你想讓你的好朋友給你發送一條隱私信息，你就可以將你的公鑰發送給他，你的朋友拿到公鑰後加密信息併發送給你。你拿到密文後，通過你的私鑰來解密從而獲得信息。
百萬富翁問題解法
假設小李與小左是這兩個不願透漏姓名和資產的百萬富翁，各自擁有的資產為i和j（ i≠j ），那麼如何進行比較呢？
- 首先小李利用加密函數生成自己的私鑰和公鑰，這裡是不包含任何資產信息的。小李把公鑰發給小左。小左呢，隨機選取一個較大的數x，利用小李發來的公鑰對x進行加密，獲得y=Enc(x)，Enc為加密函數。這時候小左把y-j+1發送給小李。
- 小李拿到小左發來的數據後，是不知道小左的具體資產數目j的。而且對(y-j+1)解密後的與x和j都無關。這時小李利用自己的私鑰對以下幾個數進行解密：(y-j+1), (y-j+2), … ,(y-j+p)。p是大於max(i, j)的一個整數。解密後的小李獲得p個數，但是哪個數字有意義呢？可以發現對(y-j+j)解密後獲得的數字有意義，因為這個是x, Dec(y-j+j) = Dec(y) = x。只可惜小李不知道哪個是x。
- 小李接下來，對解密後的p個數進行如下的操作。對前i個數，保持不變；從第i個數開始一直到最後的所有數字都+1，然後把新的p個數字發給小左。
- 小左根據這p個數字就可以知道誰的資產更多了。
結果分析
現在小左收到了p個數字，如果i比j大，那麼這p個數字中第j個數字一定是x。如果i比j小，那麼這p個數字中，第j個數字就是x+1。所以，小左只需要看第j個數字是x還是x+1就可以知道誰更有錢了。
總結
以上只是對這種情況的一種簡單解釋，實際應用的過程中會更加複雜，以避免特殊情況的出現。各種各樣的加密措施保護了我們的數據安全。聯邦學習更是藉此在建立更優秀的模型的同時，進一步的保障數據隱私。
END
本文為原創文章，轉載請聯繫小編獲得授權
投稿或尋求報道：[email protected]
Federated Learning
長按上方二維碼
關注【聯邦學習】頭條號
