章磊回答： 姚期智提出的百万富翁难题被破解? 多方安全计算MPC到底是个什么鬼？
姚期智提出的"百萬(wàn)富翁"難題被破解? 多方安全計(jì)算MPC到底是個(gè)什么鬼？
?
作者 | 章磊
責(zé)編 | Aholiab
出品 | CSDN、ARPA
?
?
在越來(lái)越多對(duì)數(shù)據(jù)隱私的擔(dān)憂聲中，政府開始行動(dòng)制定數(shù)據(jù)使用合規(guī)法案。而另一方面，對(duì)數(shù)據(jù)的保護(hù)，卻產(chǎn)生了一個(gè)矛盾：大量的數(shù)據(jù)因?yàn)樾枰婪ūＷo(hù)而無(wú)法被聯(lián)合在一起計(jì)算。
?
反過(guò)來(lái)試想一下，如果全世界的基因數(shù)據(jù)能夠聯(lián)合在一起分析，人類或許可以更快找到癌癥的解藥。這讓我們大膽地去思考，是否存在一種保護(hù)數(shù)據(jù)安全而又能夠有效利用數(shù)據(jù)的方式？
?
1980年代，姚期智院士提出了「百萬(wàn)富翁」問(wèn)題：兩個(gè)百萬(wàn)富翁街頭邂逅，他們都想炫一下富，比比誰(shuí)更有錢，但是出于隱私，都不想讓對(duì)方知道自己到底擁有多少財(cái)富，如何在不借助第三方的情況下，讓他們知道他們之間誰(shuí)更有錢？
?
?
在這個(gè)經(jīng)典問(wèn)題之下，誕生了「多方安全計(jì)算」(Multiparty Computation, MPC)這門密碼學(xué)分支。MPC技術(shù)能夠讓數(shù)據(jù)在不泄露的情況下聯(lián)合多方的數(shù)據(jù)進(jìn)行聯(lián)合計(jì)算并得到明文計(jì)算結(jié)果，最終實(shí)現(xiàn)數(shù)據(jù)的所有權(quán)和數(shù)據(jù)使用權(quán)的分離。
?
今天我們就來(lái)介紹一下MPC的出現(xiàn)背景和應(yīng)用場(chǎng)景。在開始前，我們先來(lái)看看如今數(shù)據(jù)對(duì)于我們的意義。
?
?
我們正生活在數(shù)據(jù)保護(hù)的時(shí)代
?
個(gè)人隱私和數(shù)據(jù)隱私
?
2018 年 5 月 25 日正式生效的歐盟通用數(shù)據(jù)保護(hù)條例（GDPR）引起全球廣泛關(guān)注，這部被稱為「史上最嚴(yán)」的數(shù)據(jù)保護(hù)法案將對(duì)科技行業(yè)和個(gè)人生活產(chǎn)生深遠(yuǎn)影響，因?yàn)樗侨祟悮v史上第一個(gè)定義個(gè)人數(shù)據(jù)所有權(quán)的規(guī)則，它在法律上明確規(guī)定了個(gè)人數(shù)據(jù)是個(gè)人所有的數(shù)據(jù)資產(chǎn)。
?
這項(xiàng)法律將保障人們對(duì)個(gè)人數(shù)據(jù)有更多的掌控權(quán)。舉例說(shuō)明，社交網(wǎng)絡(luò)公司在使用你的數(shù)據(jù)前必須征得你的同意。此項(xiàng)法律對(duì)創(chuàng)Facebook等科技巨頭無(wú)疑影響很大，因?yàn)檫@些公司就指望著用戶數(shù)據(jù)賺錢。
?
商業(yè)利益中的數(shù)據(jù)保護(hù)
?
數(shù)據(jù)是現(xiàn)代商業(yè)與個(gè)人的核心價(jià)值與重要資產(chǎn)。數(shù)據(jù)正在重新塑造人類生活的方方面面，包括 金融、廣告、零售、醫(yī)療、物流、能源和工業(yè)等。
?
隨著人工智能時(shí)代的到來(lái)，數(shù)據(jù)在現(xiàn)代商業(yè)活動(dòng)中也成為了最重要的競(jìng)爭(zhēng)資源。巨頭公司利用數(shù)據(jù)壟斷的優(yōu)勢(shì)建筑起了行業(yè)壁壘。
?
例如，打車軟件公司擁有人們每天出行的數(shù)據(jù)，包括乘客的起點(diǎn)與終點(diǎn)，他們可以利用這些數(shù)據(jù)來(lái)優(yōu)化自己的產(chǎn)品和業(yè)務(wù)，甚至是用這些數(shù)據(jù)來(lái)進(jìn)行一些預(yù)測(cè)，比如一個(gè)房地產(chǎn)價(jià)格指數(shù)或者一個(gè)政府道路優(yōu)化方案。
?
數(shù)據(jù)的融合可提高其價(jià)值，數(shù)據(jù)的交叉使用可產(chǎn)生協(xié)同作用。但因?yàn)閿?shù)據(jù)本身的可復(fù)制性和易傳播性，一經(jīng)分享無(wú)法追蹤使用情況，數(shù)據(jù)資產(chǎn)的分享與協(xié)同開發(fā)受到嚴(yán)重制約。
?
既然如此，那數(shù)據(jù)保護(hù)的價(jià)值又從何說(shuō)起呢？
?
?
被保護(hù)的數(shù)據(jù)如何產(chǎn)生價(jià)值?
?
雖然個(gè)人對(duì)隱私的保護(hù)、商業(yè)公司的數(shù)據(jù)保護(hù)，都是正當(dāng)?shù)睦嬖V求，但卻產(chǎn)生了一個(gè)個(gè)數(shù)據(jù)孤島。擁有數(shù)據(jù)源的中小型公司無(wú)法安全的將數(shù)據(jù)共享或變現(xiàn)。
?
對(duì)于數(shù)據(jù)使用者，大數(shù)據(jù)公司、開發(fā)者和科學(xué)家僅能接觸到有限的數(shù)據(jù)集，并且費(fèi)用高昂。與運(yùn)營(yíng)商等大數(shù)據(jù)源的合作需要開發(fā)人員現(xiàn)場(chǎng)部署模型于數(shù)據(jù)源的服務(wù)器上，模型算法存在泄露風(fēng)險(xiǎn)，且效率低下。
?
一方面，數(shù)據(jù)需要得到保護(hù)和隔離；另一方面，數(shù)據(jù)對(duì)人類社會(huì)的價(jià)值在于聯(lián)合在一起的計(jì)算和分析。這是否是一個(gè)不可破解的矛盾？
?
理想情況下，我們可以委托一個(gè)安全可信的第三方對(duì)數(shù)據(jù)進(jìn)行計(jì)算。然而，現(xiàn)實(shí)中，要么數(shù)據(jù)太重要而沒(méi)有第三方，要么第三方會(huì)因?yàn)橛辛藬?shù)據(jù)而擁有過(guò)多的權(quán)利，例如信用卡公司和電商公司，如果乙方能有對(duì)方的數(shù)據(jù)，會(huì)非常可怕。
?
要解決這個(gè)問(wèn)題，就回到了本文最初提到的「多方安全計(jì)算技術(shù)」（MPC）。通過(guò)MPC，我們可以實(shí)現(xiàn)聯(lián)合多方的隱私數(shù)據(jù)，在沒(méi)有一個(gè)可信第三方的情況下，一起計(jì)算并得到分析的結(jié)果，而不擔(dān)心各自的數(shù)據(jù)被泄露。
?
MPC是一套基于現(xiàn)代密碼學(xué)的協(xié)議組，這個(gè)工具組里面有很多組件組成。
?
簡(jiǎn)單的來(lái)說(shuō)，這套工具組里面有零知識(shí)證明（ZKP）、概率加密、信息理論消息認(rèn)證碼（MAC），各種分布式溝通協(xié)議和不經(jīng)意的轉(zhuǎn)移（OT），以及最重要的基礎(chǔ)技術(shù)：秘密共享和秘密分片計(jì)算是實(shí)現(xiàn)安全多方計(jì)算的基礎(chǔ)。
?
特別是，在被動(dòng)對(duì)手的情況下，Shamir的多項(xiàng)式秘密共享是多方計(jì)算的基石，而Chor、Goldwasser、Micali和Awerbuch的可驗(yàn)證秘密共享在拜占庭對(duì)手問(wèn)題中起著類似的作用。
?
在過(guò)去35年中，MPC算法和工程設(shè)計(jì)得到了實(shí)質(zhì)性的改進(jìn)，并且已經(jīng)達(dá)到性能上不需要考慮協(xié)議性能視為使用的主要障礙的程度。?
?
MPC社區(qū)采用了事實(shí)上的基準(zhǔn)，即在兩個(gè)參與者之間執(zhí)行AES加密，一個(gè)帶有加密消息，另一個(gè)帶有密鑰。 AES包含各種算術(shù)和布爾運(yùn)算符，因此非常適合直接在硬件和MPC中進(jìn)行計(jì)算。?在過(guò)去十年中，安全計(jì)算提高了4-5個(gè)數(shù)量級(jí)。
?
出于比較目的和考慮摩爾定律的影響，下圖顯示了在相同時(shí)間段內(nèi)本機(jī)AES計(jì)算的性能。
?
通過(guò)MPC實(shí)現(xiàn)的性能提升?
?
接下來(lái)，我們?cè)賮?lái)通過(guò)一個(gè)例子，更清晰的理解MPC的實(shí)現(xiàn)原理。請(qǐng)看下圖：
?
?
根據(jù)上圖所示，假設(shè)我們的目標(biāo)是聯(lián)合計(jì)算所有各方秘密數(shù)據(jù)的總和，這可以通過(guò)秘密共享來(lái)實(shí)現(xiàn)。
?
首先，每一方將其秘密號(hào)碼隨機(jī)分成三部分，并將其中兩部分別分享給其他部分。
?
然后，每個(gè)方在本地對(duì)來(lái)自其他對(duì)等方及其自身的所有三個(gè)共享進(jìn)為了公開最終結(jié)果，每個(gè)方的本地總和（local sum）都會(huì)公開給同行（Peers）。
?
最后，任何一方都可以通過(guò)將所有三個(gè)公共本地總和相加來(lái)知道最終結(jié)果。
?
秘密共享的關(guān)鍵點(diǎn)在于，通過(guò)了解秘密共享，一方不會(huì)獲知有關(guān)私有數(shù)據(jù)的信息。例如，在通過(guò)揭示秘密共享5的三方計(jì)算中，秘密數(shù)據(jù)可以是10、79、-11這樣的隨機(jī)數(shù)字。即使知道秘密共享，該方也可以猜測(cè)私人數(shù)據(jù)，而不是猜測(cè)隨機(jī)數(shù)。
?
由于在整個(gè)過(guò)程中沒(méi)有顯示隱私數(shù)據(jù)，因此秘密共享計(jì)算可以保護(hù)隱私。對(duì)手方不能發(fā)現(xiàn)秘密信息。
?
正式因?yàn)閾碛羞@樣的特性，MPC在現(xiàn)實(shí)世界中受到越來(lái)越多的重視，也被更多領(lǐng)域所采用。比如以下3類場(chǎng)景。
?
聯(lián)合征信?
MPC可賦能金融、保險(xiǎn)企業(yè)對(duì)客戶的負(fù)債率等風(fēng)險(xiǎn)指標(biāo)進(jìn)行聯(lián)合分析。目前各家金融、保險(xiǎn)、資產(chǎn)管理機(jī)構(gòu)只掌握客戶部分?jǐn)?shù)據(jù)，從而導(dǎo)致風(fēng)險(xiǎn)評(píng)估誤差。聯(lián)合分析不泄露各參與方數(shù)據(jù)，對(duì)客戶的風(fēng)險(xiǎn)有整體評(píng)估，在多頭借貸等場(chǎng)景下能有效降低違約風(fēng)險(xiǎn)。?
?
多維度健康分析?
MPC賦能醫(yī)療機(jī)構(gòu)對(duì)病人在多家醫(yī)院的病歷和智能硬件生物數(shù)據(jù)進(jìn)行分析，從而在病人、醫(yī)院和智能硬件廠商數(shù)據(jù)不泄露的情況下，對(duì)病人有更精準(zhǔn)的診斷。同時(shí)，針對(duì)醫(yī)療機(jī)構(gòu)的聯(lián)合數(shù)據(jù)分析可以讓藥品研究機(jī)構(gòu)對(duì)某特定地區(qū)特定病種有更全面的了解。?
?
聯(lián)合精準(zhǔn)營(yíng)銷
MPC賦能商戶對(duì)潛在客戶多維度信息進(jìn)行分析，從而更精準(zhǔn)的投放廣告。廣告投放機(jī)構(gòu)可以從更多數(shù)據(jù)維度對(duì)客戶購(gòu)買意向建模，且數(shù)據(jù)源不泄露個(gè)人隱私數(shù)據(jù)。 ?
?
?
?
MPC與現(xiàn)實(shí)世界
?
以上是幾個(gè)例子過(guò)于簡(jiǎn)單，現(xiàn)實(shí)世界的情況比這更復(fù)雜。
?
例如，用于添加的MPC是容易的，因?yàn)榭梢栽诿孛芄蚕砩媳镜赜?jì)算加法操作。但是，乘法更加困難，因?yàn)槿绻麤](méi)有其他工具幫助，它不能單獨(dú)在本地共享上計(jì)算。不過(guò)利用同態(tài)加密（Somewhat Homomorphic Encryption, SHE），有更復(fù)雜的MPC協(xié)議可以實(shí)現(xiàn)安全的乘法。
?
好消息是任何函數(shù)都可以轉(zhuǎn)換為加法和乘法的組合，因此基于秘密共享的MPC能夠進(jìn)行任何類型的通用計(jì)算，就像現(xiàn)代PC一樣。
?
另一個(gè)例子是主動(dòng)惡意節(jié)點(diǎn)（Actively Malicious）。主動(dòng)惡意被定義為節(jié)點(diǎn)將偏離協(xié)議，與被動(dòng)惡意相反，其中節(jié)點(diǎn)試圖學(xué)習(xí)其他對(duì)等方秘密數(shù)據(jù)但始終遵循協(xié)議。
?
在上述秘密共享示例中，雖然沒(méi)有節(jié)點(diǎn)可以學(xué)習(xí)其他私有數(shù)據(jù)，但是惡意節(jié)點(diǎn)可以發(fā)布錯(cuò)誤的本地共享總和，從而使所有其他對(duì)等體學(xué)習(xí)錯(cuò)誤的最終結(jié)果。
?
有各種方法可以發(fā)現(xiàn)這種惡意行為，甚至可以防止這種行為的發(fā)生。最流行的一種稱為消息驗(yàn)證代碼（MAC），其中每個(gè)操作都與一個(gè)數(shù)字相關(guān)聯(lián)，以驗(yàn)證其正確性。一旦節(jié)點(diǎn)發(fā)出錯(cuò)誤的消息，這個(gè)錯(cuò)誤將很容易被其他節(jié)點(diǎn)驗(yàn)證。
?
而偽造一個(gè)能通過(guò)驗(yàn)證的錯(cuò)誤數(shù)據(jù)的難度將是極其困難，這個(gè)難度非常大以至于造假的成本大于數(shù)據(jù)的收益。
?
?
MPC與其他實(shí)現(xiàn)技術(shù)的對(duì)比
?
除了MPC之外，還有一些能夠?qū)崿F(xiàn)類似功能的技術(shù)，包括同態(tài)加密、零知識(shí)證明、可信執(zhí)行環(huán)境等。
?
但這些技術(shù)與MPC相比，都有一定的不足，我們一個(gè)個(gè)的來(lái)看看。
?
同態(tài)加密
同態(tài)加密（HE）是一種加密形式，允許對(duì)密文進(jìn)行計(jì)算，生成加密結(jié)果，加密后的結(jié)果與操作結(jié)果相匹配，就好像它們是在明文上執(zhí)行一樣。?
?
使用這樣的工具，可以在不危及數(shù)據(jù)隱私的情況下外包存儲(chǔ)和/或計(jì)算。 因?yàn)镠E允許在保持加密的同時(shí)計(jì)算加密數(shù)據(jù)，所以它已被廣泛研究作為安全計(jì)算的候選者。
?
?
然而，即使最前沿同態(tài)加密方案仍然不能提供計(jì)有效運(yùn)算深度算術(shù)電路。
?
首先，“bootstrapping”為已經(jīng)非常繁重的過(guò)程增加了額外的成本。 目前，HE的實(shí)際應(yīng)用主要集中在評(píng)估函數(shù)的優(yōu)化上，這通過(guò)限制電路倍增深度來(lái)避免昂貴的過(guò)程。?
?
此外，根據(jù)該方案和目標(biāo)安全級(jí)別，使用HE方案將導(dǎo)致巨大的密文擴(kuò)展（從2,000到500,000甚至1,000,000倍的開銷）。這是因?yàn)橥瑧B(tài)方案必須是概率性的，以確保語(yǔ)義安全性和特定的基礎(chǔ)數(shù)學(xué)結(jié)構(gòu)。正如我們所看到的，SHE方案在HE變體中是最有希望的，它將在我們后面提到的安全計(jì)算程序中使用。
?
零知識(shí)證明
零知識(shí)證明（ZKP）是一種這樣的方法：一方（證明者Peggy）可以向另一方（驗(yàn)證者Victor）證明她知道值x，而不傳達(dá)任何信息，除了她知道值x（讀起來(lái)好繞口）。
?
?最近很多的區(qū)塊鏈項(xiàng)目在嘗試?yán)肸KP作為可信的離線計(jì)算解決方案。在這些協(xié)議中，該運(yùn)算模塊被編譯成電路并傳輸?shù)降谌綀?zhí)行環(huán)境，在該環(huán)境中將使用該電路評(píng)估數(shù)據(jù)。
?
不過(guò)，與FHE方案類似，ZKP無(wú)法證明在遠(yuǎn)程環(huán)境中完成的實(shí)際工作量。 除此之外，ZKP也無(wú)法保證計(jì)算是從惡意方的黑客手中獲得的。
?
可信執(zhí)行環(huán)境
可信執(zhí)行環(huán)境（TEE）是一種在防分離內(nèi)核上運(yùn)行的防篡改處理環(huán)境。理想的TEE保證了執(zhí)行代碼的真實(shí)性、運(yùn)行時(shí)狀態(tài)、寄存器、內(nèi)存和敏感I / O的完整性、以及存儲(chǔ)在持久內(nèi)存中的代碼、數(shù)據(jù)和運(yùn)行時(shí)狀態(tài)的機(jī)密性。此外，它應(yīng)能夠提供遠(yuǎn)程證明，證明其對(duì)第三方的可信賴性。
?
硬件制造商渴望提出他們自己的可信硬件解決方案，但缺乏不同平臺(tái)的通用標(biāo)準(zhǔn)。 最杰出的工藝單元設(shè)計(jì)人員已將其硬件安全模塊嵌入其產(chǎn)品中（例如英特爾軟件保護(hù)擴(kuò)展（SGX），ARM TrustZone，AMD安全加密虛擬化（SEV）和NVIDIA可信小內(nèi)核（TLK）。
?
然而，最近的一些黑客攻擊證明SGX還不能夠承載協(xié)議級(jí)別的數(shù)據(jù)安全保護(hù)。 事實(shí)上，這種看似安全的協(xié)議并不安全。
?
遠(yuǎn)程鑒權(quán)不會(huì)阻止一個(gè)惡意云服務(wù)提供商首先忠實(shí)地響應(yīng)遠(yuǎn)程證明查詢，然后在enclave外部模仿遠(yuǎn)程鑒定協(xié)議（例如KeyGen和CSR）。
?
換句話說(shuō)，SGX不是為“通用組合”（Universal Composition）設(shè)計(jì)的協(xié)議，其中協(xié)議的真實(shí)行為和理想世界定義（功能）在計(jì)算上對(duì)于每個(gè)對(duì)手控制的環(huán)境都是無(wú)法區(qū)分的。?簡(jiǎn)單來(lái)說(shuō)，使用TEE，可以信任硬件，但不能信任控制硬件的人。?因此，SGX最好用于許可網(wǎng)絡(luò)，其中所有節(jié)點(diǎn)都經(jīng)過(guò)預(yù)先批準(zhǔn)，環(huán)境經(jīng)過(guò)認(rèn)證和信任。
?
?
在對(duì)即同態(tài)加密、零知識(shí)證明和可信執(zhí)行環(huán)境有了基本了解之后，我們可以得出這樣的結(jié)論：雖然某些技術(shù)具有計(jì)算效率等優(yōu)勢(shì)，但它們無(wú)法提供無(wú)先驗(yàn)網(wǎng)絡(luò)（permissionless network）所需的安全性和功能。?
?
具體來(lái)說(shuō)，一個(gè)好的技術(shù)解決方案，需要能夠驗(yàn)證計(jì)算的安全性，正確性和隱私保護(hù)性：
?
-
效率：計(jì)算的效率
-
隱私保留：在這里指的是在不向任何節(jié)點(diǎn)透露細(xì)節(jié)的前提下，數(shù)據(jù)集上的函數(shù)計(jì)算能力。這是安全計(jì)算的核心。
-
證明正確性：證明計(jì)算工作實(shí)際上是使用規(guī)定的函數(shù)。在無(wú)信任的網(wǎng)絡(luò)中，證明以正確的方式執(zhí)行某個(gè)函數(shù)是非常重要的。
-
安全性證明：證明計(jì)算實(shí)際上是在安全環(huán)境中進(jìn)行的。
?
那么從MPC與上述3中技術(shù)的對(duì)比中，我們可以得到如下結(jié)論：
?
?
最后，MPC是一個(gè)龐大的密碼學(xué)領(lǐng)域，在密碼學(xué)和分布式系統(tǒng)中結(jié)合了許多概念和工具，它是一個(gè)不斷發(fā)展的活躍研究領(lǐng)域。
?
希望這篇文章能帶給你關(guān)于什么是MPC以及隱私計(jì)算為什么是可能的。在以后的文章中，我們將帶來(lái)關(guān)于密碼學(xué)更多更加深入的主題。小伙伴們敬請(qǐng)期待！
?
?
*關(guān)于作者：
章磊，ARPA聯(lián)合創(chuàng)始人&首席科學(xué)家，美國(guó)喬治華盛頓大學(xué)金融工程碩士，擁有十年深度學(xué)習(xí)、AI算法和風(fēng)險(xiǎn)建模經(jīng)驗(yàn)，并對(duì)密碼學(xué)有深度鉆研。曾于硅谷最大的股權(quán)眾籌公司CircleUp擔(dān)任資深數(shù)據(jù)科學(xué)家；此前其就職于世界銀行、AIG、PineBridge等大型金融機(jī)構(gòu)，精通人工智能和量化策略。同時(shí)章磊于2017年創(chuàng)立星塵數(shù)據(jù)，為AI行業(yè)提供數(shù)據(jù)賦能。
?
ARPA是一家專注于安全加密計(jì)算和區(qū)塊鏈底層技術(shù)的研發(fā)的公司，其核心產(chǎn)品為基于安全多方計(jì)算的隱私計(jì)算平臺(tái)，并提供全套區(qū)塊鏈+安全計(jì)算解決方案。同時(shí)ARPA作為行業(yè)成員，參與起草了工信部中國(guó)信息通信研究院即將出臺(tái)的安全多方計(jì)算標(biāo)準(zhǔn)。
總結(jié)
以上是生活随笔為你收集整理的章磊回答： 姚期智提出的百万富翁难题被破解? 多方安全计算MPC到底是个什么鬼？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： SpringBoot Thymeleaf
- 下一篇： 老夫疗法少年狂：微软中国CTO黎江：不要