摘要：今天，我們邀請(qǐng)阿里高級(jí)安全專(zhuān)家鴻程，深入解讀業(yè)界首個(gè)公開(kāi)可驗(yàn)證的安全兩方計(jì)算方案。這嚴(yán)重影響了安全多方計(jì)算的實(shí)用性。

阿里妹導(dǎo)讀：近日，阿里安全雙子座實(shí)驗(yàn)室與馬里蘭大學(xué)等高校合作的論文《Covert Security with Public Verifiability: Faster, Leaner, and Simpler 》【1】被歐洲密碼年會(huì)(Eurocrypt)2019接收。這是國(guó)內(nèi)公司在安全多方計(jì)算領(lǐng)域的第一篇頂會(huì)論文（Eurocrypt2018只有3篇大陸作者論文，難度可見(jiàn)一斑）。

今天，我們邀請(qǐng)阿里高級(jí)安全專(zhuān)家鴻程，深入解讀業(yè)界首個(gè)“公開(kāi)可驗(yàn)證(PVC)” 的安全兩方計(jì)算方案。

安全多方計(jì)算（ Secure Multi-Party Computation，MPC）于1986 年由姚期智院士提出【2】。安全多方計(jì)算協(xié)議允許多個(gè)數(shù)據(jù)所有者在互不信任的情況下進(jìn)行協(xié)同計(jì)算，輸出計(jì)算結(jié)果，并保證任何一方均無(wú)法得到除應(yīng)得的計(jì)算結(jié)果之外的其他任何信息。換句話說(shuō)，MPC技術(shù)可以獲取數(shù)據(jù)使用價(jià)值，卻不泄露原始數(shù)據(jù)內(nèi)容。

互聯(lián)網(wǎng)已經(jīng)完成了從IT時(shí)代向DT時(shí)代的轉(zhuǎn)變，數(shù)據(jù)已經(jīng)成為DT時(shí)代企業(yè)的核心競(jìng)爭(zhēng)力。數(shù)據(jù)作為一種新能源，只有流動(dòng)起來(lái)才能產(chǎn)生價(jià)值。不過(guò)，大多數(shù)企業(yè)考慮到數(shù)據(jù)安全和個(gè)人隱私等問(wèn)題，對(duì)數(shù)據(jù)共享都非常謹(jǐn)慎。而MPC對(duì)打破數(shù)據(jù)孤島，實(shí)現(xiàn)數(shù)據(jù)的可控共享，具有重要的理論和現(xiàn)實(shí)意義。

MPC方案主要可分為基于混淆電路(Garbled Circuit，GC)和基于秘密共享兩種。本文主要關(guān)注GC類(lèi)方案。

不經(jīng)意傳輸(Oblivious Transfer)

我們首先介紹一種基礎(chǔ)的安全多方計(jì)算協(xié)議：不經(jīng)意傳輸(Oblivious Transfer, OT)。

來(lái)看一個(gè)例子：假設(shè)某旅行社擁有N個(gè)景點(diǎn)的旅游資料，小淘想去其中的A景點(diǎn)游玩，希望向旅行社購(gòu)買(mǎi)相關(guān)資料做好出游功課。但是小淘非常在意自己的隱私，不希望向旅行社泄露自己的目的地是哪里。因此雙方希望這筆交易能夠滿(mǎn)足以下隱私條件：

小淘不希望向旅行社泄露“我準(zhǔn)備去A景點(diǎn)”這一信息；

旅行社只希望出售小淘出錢(qián)購(gòu)買(mǎi)的那份資料，而不泄露小淘未購(gòu)買(mǎi)的N-1份資料；

粗看起來(lái)這種隱私條件似乎是無(wú)法滿(mǎn)足的：旅行社只要把景點(diǎn)A的資料給到小淘，就必然了解了“小淘正在關(guān)注A景點(diǎn)”這一信息；除非旅行社把所有N份資料都給出，但是這又違背了旅行社的利益；

但是神奇的OT可以讓交易在這種“不可能的條件”下達(dá)成。簡(jiǎn)而言之，在OT協(xié)議中，旅行社把他擁有的N份資料使用某種雙方協(xié)商同意的加密算法和參數(shù)進(jìn)行加密，然后發(fā)送給小淘；小淘可以從密文中解密出A的資料，而無(wú)法解密出其他N-1份資料。

OT除了可以直接用于構(gòu)造MPC方案之外，也是GC等許多MPC方案的基石。

混淆電路

我們知道，任意函數(shù)最后在計(jì)算機(jī)語(yǔ)言?xún)?nèi)部都是由加法器、乘法器、移位器、選擇器等電路表示，而這些電路最后都可以?xún)H由AND和XOR兩種邏輯門(mén)組成。一個(gè)門(mén)電路其實(shí)就是一個(gè)真值表，例如AND門(mén)的真值表就是：

例如其中右下格表示兩根輸入線(wire)都取1時(shí)，輸出wire=1：即 1 AND 1 = 1。

假設(shè)我們把每個(gè)wire都使用不同的密鑰加密，把真值表變成這樣：

例如其中右下格表示如果門(mén)的輸入是b和d，那么輸出加密的f(密鑰是b和d)。這個(gè)門(mén)從控制流的角度來(lái)看還是一樣的，只不過(guò)輸入和輸出被加密了，且輸出必須使用對(duì)應(yīng)的輸入才能解密，解密出的f又可以作為后續(xù)門(mén)的輸入。這種加密方式就稱(chēng)為“混淆電路(Garbled Circuit，GC)”。

將電路中所有的門(mén)都按順序進(jìn)行這樣的加密，我們就得到了一個(gè)GC表示的函數(shù)。這個(gè)函數(shù)接收加密的輸入，輸出加密的結(jié)果。

假設(shè)有兩個(gè)參與方A和B各自提供數(shù)據(jù)a、b，希望安全的計(jì)算約定的函數(shù)F(a,b)，那么一種基于GC的安全兩方計(jì)算協(xié)議過(guò)程可以非正式的描述如下：

細(xì)心的同學(xué)一定會(huì)指出：第4步中A怎么可以接觸B的輸入b呢？這不是違背了安全多方計(jì)算的假設(shè)嗎？這里就需要使用OT，A扮演Sender，B扮演Receiver，讓B從A處得到Encrypt( b)，卻不向A透露b的內(nèi)容。如圖所示：

需要注意的是，上述流程只是最原始的GC方法的不嚴(yán)謹(jǐn)描述，GC后續(xù)還有Point & Permute、Free XOR、Half Gates等多種細(xì)節(jié)優(yōu)化，隨著最近幾年的研究進(jìn)展，GC的性能已經(jīng)差不多可以實(shí)用了。以求兩個(gè)百萬(wàn)維向量的漢明距離(Hamming Distance)為例（應(yīng)用場(chǎng)景是兩份數(shù)據(jù)求相似度，卻互相不泄露數(shù)據(jù)內(nèi)容），這樣的安全兩方計(jì)算已經(jīng)可以在1.5秒左右完成。

半誠(chéng)實(shí)行為模型與惡意行為模型

更細(xì)心的同學(xué)還會(huì)進(jìn)一步提出問(wèn)題：“怎么確保A給B的

就是一個(gè)正確的GC呢？例如A和B商定要比a和b的大小，商定了F(a,b)=a>b?1:0，但是A可以制作一個(gè)別的函數(shù)的GC，例如F(a,b)=b的第1個(gè)比特，這樣顯然是會(huì)侵害B的隱私的，但是由于函數(shù)是以GC形式發(fā)給B的，B是沒(méi)有辦法發(fā)現(xiàn)這個(gè)問(wèn)題?”

這確實(shí)是一個(gè)安全問(wèn)題，事實(shí)上，GC還存在如selective failure等其他更多的安全問(wèn)題。在介紹解決方案之前，我們需要先定義安全多方計(jì)算的安全模型。

安全多方計(jì)算的安全模型包含多個(gè)角度的內(nèi)容，在上述上下文中，我們關(guān)注的是其中的“行為模型”，即參與方可能進(jìn)行何種行為以獲取其他方的隱私。常見(jiàn)的行為模型包括“半誠(chéng)實(shí)(Semi Honest)”和“惡意(Malicious)”兩種。前者假設(shè)所有參與方都是忠實(shí)的按照協(xié)議步驟進(jìn)行執(zhí)行，只是想通過(guò)協(xié)議內(nèi)容推測(cè)其他方的隱私，而后者假設(shè)惡意參與方為了獲取其他方的隱私可以不遵循協(xié)議內(nèi)容。

用撲克牌打個(gè)不嚴(yán)謹(jǐn)?shù)谋确?，半誠(chéng)實(shí)的牌友會(huì)試圖從自己的手牌和已經(jīng)打出的牌來(lái)推測(cè)他人的手牌，但是還是遵循撲克牌規(guī)則的；而一個(gè)惡意的牌友則換牌、偷牌等手段無(wú)所不用。

可見(jiàn)，本節(jié)開(kāi)始提出的問(wèn)題屬于惡意行為的范疇，而原始的GC只能說(shuō)在半誠(chéng)實(shí)行為模型下是安全的，無(wú)法抵御惡意行為攻擊。有許多對(duì)GC方案的改進(jìn)方案可以達(dá)到惡意行為模型下的安全性，但是它們都需要付出很大的性能代價(jià)：仍然以求兩個(gè)百萬(wàn)維向量的漢明距離為例，其中最快的方法也需要10秒+，比同等的半誠(chéng)實(shí)方案慢7倍以上。事實(shí)上，經(jīng)過(guò)我們的調(diào)研，若想真正的實(shí)現(xiàn)支持大規(guī)模數(shù)據(jù)的MPC產(chǎn)品，基本上只能考慮半誠(chéng)實(shí)方案。這嚴(yán)重影響了安全多方計(jì)算的實(shí)用性。

公開(kāi)可驗(yàn)證(Public Verifiable Covert, PVC)行為模型

PVC是在半誠(chéng)實(shí)、惡意之間的一種折中。其主要思想是：每個(gè)參與方的所有行為都自動(dòng)帶有類(lèi)似簽名的機(jī)制以供其他參與方存證。假設(shè)某個(gè)參與方實(shí)施惡意行為，那么其他參與方可以有

的概率發(fā)現(xiàn)（

稱(chēng)為威懾因子，一般>=50%，不能100%發(fā)現(xiàn)，因?yàn)?00%那就直接滿(mǎn)足惡意行為模型了）這一惡意行為，并將該行為及其簽名公開(kāi)，令作惡者承受名譽(yù)損失?？紤]到名譽(yù)對(duì)一個(gè)數(shù)據(jù)所有者的重要性（例如此后可能再也找不到合作），50%左右的威懾力已經(jīng)足以讓理性者不考慮作惡。

PVC模型最開(kāi)始是由學(xué)者在Asiacrypt2012【3】提出，Asiacrypt2015【4】上也有學(xué)者提出相關(guān)的改進(jìn)方案，但是這些方案不僅效率較低，而且只有復(fù)雜的理論描述，實(shí)現(xiàn)可能性低。我們提出的新型PVC方案不僅協(xié)議簡(jiǎn)潔，性能有大幅提升，而且首次進(jìn)行了完整的代碼實(shí)現(xiàn)。仍然以求兩個(gè)百萬(wàn)維向量的漢明距離為例，使用我們威懾因子為50%的PVC方法大概只需要2.5秒。

以下仍假設(shè)有兩個(gè)參與方A和B各自提供數(shù)據(jù)a、b，希望安全的計(jì)算約定的函數(shù)F(a,b)，以威懾因子

=50%為例，給出我們的PVC方案的非正式描述：

A選擇兩個(gè)隨機(jī)種子s1和s2， B和A運(yùn)行OT隨機(jī)選擇其中一個(gè)（不妨設(shè)B獲取了s1）；

A使用s1和s2分別生成GC1和GC2；

B和A運(yùn)行OT獲取GC1中B輸入wire的加密值（我們后面可以看到GC1不會(huì)真正被使用，因此這里可以不與b對(duì)應(yīng)，比如是任意常數(shù)值的密文）；

B和A運(yùn)行OT獲取GC2中B輸入wire對(duì)應(yīng)的b的加密值；

A對(duì)GC1進(jìn)行Hash，并把Hash發(fā)給B；

A對(duì)GC2進(jìn)行Hash，并把Hash發(fā)給B；

A對(duì)上述所有流程進(jìn)行簽名，并把簽名發(fā)送給B；

B由于有s1，因此可以自行生成GC1，可以自己模擬第3步和第5步；如果結(jié)果與A發(fā)的不一致，則公布相關(guān)簽名作為A作惡證據(jù)。如果一致，就用GC2進(jìn)行真實(shí)計(jì)算。

可見(jiàn)，A如果作惡，總有50%的概率被B抽查到（因?yàn)锳不知道B到底掌握了哪個(gè)GC的隨機(jī)種子）。因此理性的A會(huì)選擇不作惡，忠實(shí)的執(zhí)行安全多方計(jì)算協(xié)議。

需要再次強(qiáng)調(diào)的是，為便于理解，所有的協(xié)議都僅僅是非正式描述，有興趣進(jìn)一步研究細(xì)節(jié)的同學(xué)歡迎參閱我們的論文【1】。

我們與馬里蘭大學(xué)等高校合作，首次實(shí)現(xiàn)了一種“公開(kāi)可驗(yàn)證(PVC)” 的安全兩方計(jì)算方案，這種方案的性能接近半誠(chéng)實(shí)方案，同時(shí)其PVC特性能夠?qū)ψ鞅仔袨樾纬赏亓?，令其具有遠(yuǎn)強(qiáng)于半誠(chéng)實(shí)模型的安全性，具有很高的實(shí)用價(jià)值。

閱讀原文

本文來(lái)自云棲社區(qū)合作伙伴“?阿里技術(shù)”，如需轉(zhuǎn)載請(qǐng)聯(lián)系原作者。