陳萬(wàn)東 尹天宇 王璇 呂家興

摘? ?要：保護(hù)隱私的集合交集運(yùn)算是當(dāng)前信息安全領(lǐng)域的研究熱點(diǎn)，它使擁有秘密集合的參與者在不泄露各自隱私數(shù)據(jù)的前提下共同輸出秘密集合上的交集結(jié)果，但是現(xiàn)階段的隱私集合交集運(yùn)算方案允許的參與方少并且效率低下，不能保證參與方之間的公平性。針對(duì)這些問(wèn)題，文章提出了一種基于區(qū)塊鏈的隱私集合交集求解方案，要求參與方共同部署并簽訂智能合約，將運(yùn)算結(jié)果公布至區(qū)塊鏈，保證參與者共同獲得正確的交集結(jié)果。在進(jìn)行隱私交集運(yùn)算時(shí)，參照YAO氏通用混淆電路估值技術(shù)，使用保護(hù)隱私的集合交集運(yùn)算電路和去重電路，設(shè)計(jì)了一種區(qū)塊鏈上保護(hù)隱私的集合交集運(yùn)算方案。

關(guān)鍵詞：混淆電路;區(qū)塊鏈;隱私集合比較;智能合約

1? ? 隱私集合交集簡(jiǎn)要介紹

隱私集合交集（Private Set Intersection，PSI）使擁有隱私數(shù)據(jù)集合的多個(gè)參與者能夠合作利用他們的私有數(shù)據(jù)計(jì)算交集，同時(shí)不泄露各自的私有信息，是安全多方計(jì)算研究方向的一個(gè)重要分支，在網(wǎng)絡(luò)信息安全、人類(lèi)基因研究等領(lǐng)域有廣泛的應(yīng)用?，F(xiàn)階段的隱私集合比較方案存在不能保證參與方的公平性、運(yùn)算效率低下等問(wèn)題，本文將介紹一種新的隱私集合交集計(jì)算方案，參與方可以在不泄露自己隱私信息的前提下公平、高效地得到交集結(jié)果。

2? ? 預(yù)備知識(shí)

2.1? 隱私集合交集

隱私集合交集指的是有N方的參與者Pi（i=1，2，…，N），各個(gè)參與者擁有自己的隱私信息Xi={x1，x2，…}（i=1，2，…，N），在不泄露參與者各自隱私信息的情況下計(jì)算出共有的集合元素信息X1∩X2∩…∩XN，在經(jīng)過(guò)計(jì)算后，參與者最終得到交集結(jié)果，且不知道其他參與者的隱私信息。

2.2? 區(qū)塊鏈及智能合約

區(qū)塊鏈（Block chain）是一種新型技術(shù)，可以看作是網(wǎng)絡(luò)上存放所有交易信息的一本公共賬簿，賬簿的內(nèi)容是不可修改的。每個(gè)節(jié)點(diǎn)代表一個(gè)用戶(hù)，每一個(gè)節(jié)點(diǎn)都可以獲取到在這個(gè)區(qū)塊鏈中的所有交易信息，當(dāng)部分節(jié)點(diǎn)的交易信息被篡改，區(qū)塊鏈上的其他節(jié)點(diǎn)會(huì)在短時(shí)間內(nèi)發(fā)現(xiàn)這些未共識(shí)的節(jié)點(diǎn)并進(jìn)行維護(hù)和更新。區(qū)塊鏈內(nèi)的所有數(shù)據(jù)以鏈?zhǔn)酱鎯?chǔ)，通過(guò)時(shí)間戳技術(shù)可以追溯每筆數(shù)據(jù)的所有信息以及來(lái)源。智能合約（Smart contract）是一種可以在區(qū)塊鏈上部署的合約，一旦某個(gè)事件觸發(fā)合約中的條款，合約自動(dòng)執(zhí)行相應(yīng)的措施。智能合約有去中心化的特點(diǎn)，合約透明并且一旦簽署便無(wú)法更改，保證簽署方的公平性。

2.3? 混淆電路

混淆電路是Andrew Yao在20世紀(jì)80年代發(fā)明的一種很智能的技術(shù)。它可以讓兩個(gè)人針對(duì)某個(gè)算式來(lái)計(jì)算答案，而不需要知道他們?cè)谟?jì)算式所輸入的數(shù)字?；煜娐肥前踩喾接?jì)算的一種解決方案，可以在參與方不泄露自己隱私信息的情況下進(jìn)行多種類(lèi)型的計(jì)算。例如Andrew Yao提出的百萬(wàn)富翁問(wèn)題：兩個(gè)百萬(wàn)富翁想要知道誰(shuí)的財(cái)產(chǎn)更多一些，但是不想讓對(duì)方知道自己的財(cái)富信息?？梢允褂没煜娐贩桨冈O(shè)計(jì)相應(yīng)的電路計(jì)算出來(lái)結(jié)果并且不會(huì)泄露參與方的信息?；煜娐贩桨缚梢酝ㄟ^(guò)電路的設(shè)計(jì)來(lái)解決更為復(fù)雜的問(wèn)題。

3? ? 方案描述

在這個(gè)方案中，參與方會(huì)在不泄露自己隱私信息的前提下獲得所有參與者隱私信息所計(jì)算出來(lái)的交集結(jié)果。首先，各個(gè)參與方共同部署智能合約，協(xié)商智能合約內(nèi)容，保證各個(gè)參與方能夠在不泄露自己隱私的前提下公平地、正確地、及時(shí)地獲取結(jié)果。簽署智能合約之后，如果一方違約，將會(huì)給其嚴(yán)厲的懲罰。其次，使用設(shè)計(jì)好的混淆電路（參照下一段）將隱私信息交集結(jié)果計(jì)算出來(lái)。最后，智能合約接收到結(jié)果觸發(fā)條件，將交集結(jié)果同時(shí)發(fā)送給所有參與方。

將介紹混淆電路的設(shè)計(jì)方案。讓C是一個(gè)布爾電路接收兩個(gè)輸入x，y∈{0，1}n和輸出C{x，y}∈{0，1}n（為簡(jiǎn)單起見(jiàn)， 假設(shè)輸入長(zhǎng)度、輸出長(zhǎng)度和安全參數(shù)都是相同長(zhǎng)度n）。還假設(shè)C具有這樣的性質(zhì)：如果電路輸出線來(lái)自門(mén)g，那么門(mén)g沒(méi)有輸入到其他門(mén)的線。（同樣地，如果電路輸入線本身也是電路輸出，那么它就不是輸入到任何柵極中。）

首先描述了C中單個(gè)雜亂門(mén)g的構(gòu)造。電路C是布爾型的，因此，任何門(mén)都由函數(shù)g表示：{0，1}X{0，1}→{0，1}?，F(xiàn)在，將g的兩條輸入線標(biāo)記為w1和w2，并將g的輸出線標(biāo)記為w3。此外，讓k10，k11，k20，k21，k30，k31為獨(dú)立調(diào)用密鑰生成算法G（1n）獲得的6個(gè)鍵;為了簡(jiǎn)單起見(jiàn)，假設(shè)這些鍵的長(zhǎng)度也為n。直觀地說(shuō)，希望能夠從k1α和k2β計(jì)算k3g（α，β），而不揭示其他3個(gè)值中的任何一個(gè)：k3g（1-α，β）、k3g（α，1-β）、k3g（1-α，1-β）。門(mén)g由以下4個(gè)值定義c（0，0），c（0，1），c（1，0），c（1，1）：

其中，E來(lái)自一個(gè)私鑰加密方案（例如G，E，D），該方案對(duì)多條消息進(jìn)行了不可區(qū)分的加密，并且具有難以捉摸的有效驗(yàn)證范圍。實(shí)際的門(mén)是由上述值的隨機(jī)排列來(lái)定義的，表示為c0，c1，c2，c3;從這里稱(chēng)它們?yōu)殚T(mén)g的雜亂表。注意，給定k1α和k2β，以及c0，c1，c2，c3的值，可以如下計(jì)算門(mén)k3g（α，β）的輸出。對(duì)于每個(gè)i，計(jì)算。如果多個(gè)解密返回一個(gè)非值，則輸出中止。否則，將k3λ定義為獲得的唯一非值。（請(qǐng)注意，如果只獲得一個(gè)非值，那么這將是k3g（α，β），因?yàn)樗窃诮o定的密鑰k1α和k2β下加密的。）

現(xiàn)在，我們準(zhǔn)備展示如何構(gòu)造整個(gè)混淆電路。設(shè)m為電路C中的導(dǎo)線數(shù)，設(shè)w1，…wj是這些電線的標(biāo)簽。除以下情況外，這些標(biāo)簽都是只選擇wi和wj為同一柵極g的兩根輸出線，則wi=wj。如果g>1，就會(huì)發(fā)生這種情況。同樣地，如果一個(gè)輸入位進(jìn)入一個(gè)以上的柵極，那么與這個(gè)位相關(guān)聯(lián)的所有電路輸入線將具有相同的標(biāo)簽。接下來(lái)，對(duì)于每個(gè)標(biāo)簽wi，選擇兩個(gè)獨(dú)立的ki0，ki1←G（1n）;強(qiáng)調(diào)所有這些鍵都是獨(dú)立于其他鍵選擇的?，F(xiàn)在，給定這些鍵，按上面描述的方式計(jì)算每個(gè)門(mén)的4個(gè)混淆值，并隨機(jī)排列結(jié)果。最后，計(jì)算了混淆電路的輸出或解密表。這些表只是由（0，ki0）和（1，ki1）的值組成，其中，wi是一種電路輸出線?；蛘?，輸出門(mén)可以直接計(jì)算0或1。也就是說(shuō)，在輸出門(mén)中，可以為每一個(gè)α，β∈{0，1}定義。C的整個(gè)亂碼電路，即G（C），由每個(gè)門(mén)的亂碼表和輸出表組成。由此注意到，給出了C的結(jié)構(gòu)，通過(guò)指定每個(gè)門(mén)的輸出表和混亂表，可以簡(jiǎn)單地定義C的混亂版本。這就完成了對(duì)混淆電路的描述。

最后，智能合約會(huì)將混淆電路的運(yùn)算結(jié)果，同時(shí)返回給參與方。利用偽隨機(jī)函數(shù)生成公開(kāi)參數(shù)，這些參數(shù)會(huì)影響到計(jì)算的結(jié)果。所以，根據(jù)密文計(jì)算的方法以及參數(shù)需要部署到智能合約，并由其執(zhí)行驗(yàn)證。智能合約計(jì)算出來(lái)的密文結(jié)果會(huì)由智能合約同時(shí)公開(kāi)給每個(gè)參與方，避免參與方提前獲取結(jié)果并欺騙其他參與方。

[參考文獻(xiàn)]

[1]HUANG Y，EVANS D，KATZ J，et al.Faster secure two-party computation using garbled circuits[C].San Diego：20th USENIX Conference on Security，2011.

[2]MOHASSEL P，RIVA B.Garbled circuits checking garbled circuits：more efficient and secure two-party computation[M].Newyork：Advances in Cryptology—CRYPTO，2013.

[3]WATANABE H，F(xiàn)UJIMURA S，NAKADAIRA A，et al.An efficient energy monitoring method based on bluetooth low energy[C].Las Vegas：IEEE International Conference on Consumer Electronics，2016.

[4]WATANABE H，F(xiàn)UJIMURA S，NAKADAIRA A，et al.Blockchain contract：Securing a blockchain applied to smart contracts[C].Las Vegas：IEEE International Conference on Consumer Electronics，2016.

[5]FREDERIKSEN T K，NIELSEN J B，ORLANDI C.Privacy-free garbled circuits with applications to efficient zero-knowledge[C].Springer：Annual International Conference on the Theory and Applications of Cryptographic Techniques，2015.

[6]BELLARE M，HOANG V T，ROGAWAY P.12-foundations of garbled circuits[C].North Carolina：ACM Conference on Computer and Communications Security，2012.