安全多方計算介紹
安全多方計算（ Secure Multi-Party Computation，MPC）于1986 年由姚期智院士提出【2】肉瓦。安全多方計算協(xié)議允許多個數(shù)據(jù)所有者在互不信任的情況下進(jìn)行協(xié)同計算，輸出計算結(jié)果船殉，并保證任何一方均無法得到除應(yīng)得的計算結(jié)果之外的其他任何信息挨厚。換句話說疫剃，MPC技術(shù)可以獲取數(shù)據(jù)使用價值，卻不泄露原始數(shù)據(jù)內(nèi)容壤躲。
互聯(lián)網(wǎng)已經(jīng)完成了從IT時代向DT時代的轉(zhuǎn)變，數(shù)據(jù)已經(jīng)成為DT時代企業(yè)的核心競爭力漏麦。數(shù)據(jù)作為一種新能源撕贞，只有流動起來才能產(chǎn)生價值。不過脊奋，大多數(shù)企業(yè)考慮到數(shù)據(jù)安全和個人隱私等問題诚隙，對數(shù)據(jù)共享都非常謹(jǐn)慎久又。而MPC對打破數(shù)據(jù)孤島炉峰，實現(xiàn)數(shù)據(jù)的可控共享疼阔，具有重要的理論和現(xiàn)實意義。
MPC方案主要可分為基于混淆電路(Garbled Circuit淘邻，GC)和基于秘密共享兩種宾舅。本文主要關(guān)注GC類方案。
不經(jīng)意傳輸(Oblivious Transfer)
我們首先介紹一種基礎(chǔ)的安全多方計算協(xié)議：不經(jīng)意傳輸(Oblivious Transfer, OT)崎溃。
來看一個例子：假設(shè)某旅行社擁有N個景點的旅游資料袁串，小淘想去其中的A景點游玩，希望向旅行社購買相關(guān)資料做好出游功課破镰。但是小淘非常在意自己的隱私鲜漩，不希望向旅行社泄露自己的目的地是哪里。因此雙方希望這筆交易能夠滿足以下隱私條件：
- 小淘不希望向旅行社泄露“我準(zhǔn)備去A景點”這一信息喉祭；
- 旅行社只希望出售小淘出錢購買的那份資料泛烙，而不泄露小淘未購買的N-1份資料傻工；
粗看起來這種隱私條件似乎是無法滿足的：旅行社只要把景點A的資料給到小淘，就必然了解了“小淘正在關(guān)注A景點”這一信息坊饶；除非旅行社把所有N份資料都給出匿级，但是這又違背了旅行社的利益；
但是神奇的OT可以讓交易在這種“不可能的條件”下達(dá)成孤页。簡而言之行施，在OT協(xié)議中，旅行社把他擁有的N份資料使用某種雙方協(xié)商同意的加密算法和參數(shù)進(jìn)行加密涯雅，然后發(fā)送給小淘精刷；小淘可以從密文中解密出A的資料贬养，而無法解密出其他N-1份資料误算。
以下以N=2為例儿礼，基于Diffie-Hellman密鑰交換協(xié)議诉字，給出一種1 of 2 OT實現(xiàn)方法的非正式描述壤圃；其中S（Sender）=旅行社伍绳，R（Receiver）=小淘，S擁有兩份資料；
- S秘密生成隨機(jī)數(shù)a; R秘密生成隨機(jī)數(shù)b甥绿；
-
S將
發(fā)送給S；
-
S計算
图谷；
-
S以
發(fā)送給R承璃；
-
由于
。
如果R希望取得即可盗舰。
OT除了可以直接用于構(gòu)造MPC方案之外川陆，也是GC等許多MPC方案的基石较沪。
混淆電路
我們知道，任意函數(shù)最后在計算機(jī)語言內(nèi)部都是由加法器萄焦、乘法器茬射、移位器在抛、選擇器等電路表示肠阱，而這些電路最后都可以僅由AND和XOR兩種邏輯門組成辖所。一個門電路其實就是一個真值表缘回，例如AND門的真值表就是：
例如其中右下格表示兩根輸入線(wire)都取1時您觉，輸出wire=1：即 1 AND 1 = 1。
假設(shè)我們把每個wire都使用不同的密鑰加密，把真值表變成這樣：
例如其中右下格表示如果門的輸入是b和d诚啃，那么輸出加密的f(密鑰是b和d)。這個門從控制流的角度來看還是一樣的造垛，只不過輸入和輸出被加密了，且輸出必須使用對應(yīng)的輸入才能解密晰搀，解密出的f又可以作為后續(xù)門的輸入五辽。這種加密方式就稱為“混淆電路(Garbled Circuit，GC)”厕隧。
將電路中所有的門都按順序進(jìn)行這樣的加密奔脐，我們就得到了一個GC表示的函數(shù)。這個函數(shù)接收加密的輸入吁讨，輸出加密的結(jié)果髓迎。
假設(shè)有兩個參與方A和B各自提供數(shù)據(jù)a、b建丧，希望安全的計算約定的函數(shù)F(a,b)尺铣，那么一種基于GC的安全兩方計算協(xié)議過程可以非正式的描述如下：
-
A把F進(jìn)行加密店溢，得到GC表示的函數(shù)
; （注意這里A是電路的生成者，所以他了解每根wire的密鑰）；
- A把自己的輸入a使用第1步中對應(yīng)的wire密鑰加密效拭，得到Encrypt(a)；
-
A將Encrypt(a)、
發(fā)送給B摇肌；
- A將B的輸入b使用第1步中對應(yīng)的wire密鑰加密变秦，得到Encrypt(b)钳垮，并將Encrypt(b)發(fā)送給B肚医；
- B擁有完整的GC和輸入你稚，因此可以運行電路得到加密的輸出鸡典；
- A把輸出wire的密鑰發(fā)給B，B解密得到最終結(jié)果F(a,b)；
- 如果A需要的話涮总，B再把(a,b)發(fā)給A谤职；
細(xì)心的同學(xué)一定會指出：第4步中A怎么可以接觸B的輸入b呢？這不是違背了安全多方計算的假設(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)差不多可以實用了。以求兩個百萬維向量的漢明距離(Hamming Distance)為例（應(yīng)用場景是兩份數(shù)據(jù)求相似度磅轻，卻互相不泄露數(shù)據(jù)內(nèi)容）凝果，這樣的安全兩方計算已經(jīng)可以在1.5秒左右完成冤荆。
安全多方計算的安全模型 半誠實行為模型與惡意行為模型
更細(xì)心的同學(xué)還會進(jìn)一步提出問題：“怎么確保A給B的
就是一個正確的GC呢？例如A和B商定要比a和b的大小服赎，商定了F(a,b)=a>b?1:0曹傀，但是A可以制作一個別的函數(shù)的GC，例如F(a,b)=b的第1個比特瑟由，這樣顯然是會侵害B的隱私的歹苦，但是由于函數(shù)是以GC形式發(fā)給B的，B是沒有辦法發(fā)現(xiàn)這個問題?”
這確實是一個安全問題神得，事實上，GC還存在如selective failure等其他更多的安全問題碌上。在介紹解決方案之前馏予，我們需要先定義安全多方計算的安全模型。
安全多方計算的安全模型包含多個角度的內(nèi)容盔性，在上述上下文中霞丧，我們關(guān)注的是其中的“行為模型”，即參與方可能進(jìn)行何種行為以獲取其他方的隱私冕香。常見的行為模型包括“半誠實(Semi Honest)”和“惡意(Malicious)”兩種蛹尝。前者假設(shè)所有參與方都是忠實的按照協(xié)議步驟進(jìn)行執(zhí)行后豫，只是想通過協(xié)議內(nèi)容推測其他方的隱私，而后者假設(shè)惡意參與方為了獲取其他方的隱私可以不遵循協(xié)議內(nèi)容突那。
用撲克牌打個不嚴(yán)謹(jǐn)?shù)谋确酱炷穑胝\實的牌友會試圖從自己的手牌和已經(jīng)打出的牌來推測他人的手牌，但是還是遵循撲克牌規(guī)則的愕难；而一個惡意的牌友則換牌早龟、偷牌等手段無所不用。
可見猫缭，本節(jié)開始提出的問題屬于惡意行為的范疇葱弟，而原始的GC只能說在半誠實行為模型下是安全的，無法抵御惡意行為攻擊猜丹。有許多對GC方案的改進(jìn)方案可以達(dá)到惡意行為模型下的安全性芝加，但是它們都需要付出很大的性能代價：仍然以求兩個百萬維向量的漢明距離為例，其中最快的方法也需要10秒+射窒，比同等的半誠實方案慢7倍以上藏杖。事實上，經(jīng)過我們的調(diào)研脉顿，若想真正的實現(xiàn)支持大規(guī)模數(shù)據(jù)的MPC產(chǎn)品制市，基本上只能考慮半誠實方案。這嚴(yán)重影響了安全多方計算的實用性弊予。
公開可驗證(Public Verifiable Covert, PVC)行為模型
PVC是在半誠實祥楣、惡意之間的一種折中。其主要思想是：每個參與方的所有行為都自動帶有類似簽名的機(jī)制以供其他參與方存證汉柒。假設(shè)某個參與方實施惡意行為误褪，那么其他參與方可以有稱為威懾因子，一般>=50%碾褂，不能100%發(fā)現(xiàn)兽间，因為100%那就直接滿足惡意行為模型了）這一惡意行為，并將該行為及其簽名公開正塌，令作惡者承受名譽(yù)損失嘀略。考慮到名譽(yù)對一個數(shù)據(jù)所有者的重要性（例如此后可能再也找不到合作）乓诽，50%左右的威懾力已經(jīng)足以讓理性者不考慮作惡帜羊。
PVC模型最開始是由學(xué)者在Asiacrypt2012【3】提出，Asiacrypt2015【4】上也有學(xué)者提出相關(guān)的改進(jìn)方案鸠天，但是這些方案不僅效率較低讼育，而且只有復(fù)雜的理論描述，實現(xiàn)可能性低。我們提出的新型PVC方案不僅協(xié)議簡潔奶段，性能有大幅提升饥瓷，而且首次進(jìn)行了完整的代碼實現(xiàn)。仍然以求兩個百萬維向量的漢明距離為例痹籍，使用我們威懾因子為50%的PVC方法大概只需要2.5秒呢铆。
以下仍假設(shè)有兩個參與方A和B各自提供數(shù)據(jù)a、b蹲缠，希望安全的計算約定的函數(shù)F(a,b)刺洒，以威懾因子=50%為例，給出我們的PVC方案的非正式描述：
- A選擇兩個隨機(jī)種子s1和s2吼砂， B和A運行OT隨機(jī)選擇其中一個（不妨設(shè)B獲取了s1）；
- A使用s1和s2分別生成GC1和GC2鼎文；
- B和A運行OT獲取GC1中B輸入wire的加密值（我們后面可以看到GC1不會真正被使用渔肩，因此這里可以不與b對應(yīng)，比如是任意常數(shù)值的密文）拇惋；
- B和A運行OT獲取GC2中B輸入wire對應(yīng)的b的加密值周偎；
- A對GC1進(jìn)行Hash，并把Hash發(fā)給B撑帖；
- A對GC2進(jìn)行Hash蓉坎，并把Hash發(fā)給B；
- A對上述所有流程進(jìn)行簽名胡嘿，并把簽名發(fā)送給B蛉艾；
- B由于有s1，因此可以自行生成GC1衷敌，可以自己模擬第3步和第5步勿侯；如果結(jié)果與A發(fā)的不一致，則公布相關(guān)簽名作為A作惡證據(jù)缴罗。如果一致助琐，就用GC2進(jìn)行真實計算。
可見面氓，A如果作惡兵钮，總有50%的概率被B抽查到（因為A不知道B到底掌握了哪個GC的隨機(jī)種子）。因此理性的A會選擇不作惡舌界，忠實的執(zhí)行安全多方計算協(xié)議掘譬。
需要再次強(qiáng)調(diào)的是，為便于理解呻拌，所有的協(xié)議都僅僅是非正式描述屁药，有興趣進(jìn)一步研究細(xì)節(jié)的同學(xué)歡迎參閱我們的論文【1】。 總結(jié) 我們與馬里蘭大學(xué)等高校合作，首次實現(xiàn)了一種“公開可驗證(PVC)” 的安全兩方計算方案酿箭，這種方案的性能接近半誠實方案复亏，同時其PVC特性能夠?qū)ψ鞅仔袨樾纬赏亓Γ钇渚哂羞h(yuǎn)強(qiáng)于半誠實模型的安全性缭嫡，具有很高的實用價值缔御。
參考資料：
[1] https://eprint.iacr.org/2018/1108
[2] Yao.A.C. How to Generate and Exchange Secrets. FOCS 1986: 162-167
[3] Asharov G , Orlandi C . Calling Out Cheaters:Covert Security with Public Verifiability, Advances in Cryptology – ASIACRYPT 2012. Springer Berlin Heidelberg, 2012.
[4] Kolesnikov V , Malozemoff A J . PublicVerifiability in the Covert Model (Almost) for Free, Advances in Cryptology – ASIACRYPT 2015. Springer Berlin Heidelberg, 2015.
本文轉(zhuǎn)載自《安全多方計算新突破！阿里首次實現(xiàn)“公開可驗證” 的安全方案》妇蛀，感謝鴻程 阿里技術(shù)提供知識傳播耕突。
