基于區塊鏈的隱私集合交集方案研究

陳萬東 尹天宇 王璇 呂家興

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

關鍵詞：混淆電路;區塊鏈;隱私集合比較;智能合約

1? ? 隱私集合交集簡要介紹

隱私集合交集（Private Set Intersection，PSI）使擁有隱私數據集合的多個參與者能夠合作利用他們的私有數據計算交集，同時不泄露各自的私有信息，是安全多方計算研究方向的一個重要分支，在網絡信息安全、人類基因研究等領域有廣泛的應用。現階段的隱私集合比較方案存在不能保證參與方的公平性、運算效率低下等問題，本文將介紹一種新的隱私集合交集計算方案，參與方可以在不泄露自己隱私信息的前提下公平、高效地得到交集結果。

2? ? 預備知識

2.1? 隱私集合交集

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

2.2? 區塊鏈及智能合約

區塊鏈（Block chain）是一種新型技術，可以看作是網絡上存放所有交易信息的一本公共賬簿，賬簿的內容是不可修改的。每個節點代表一個用戶，每一個節點都可以獲取到在這個區塊鏈中的所有交易信息，當部分節點的交易信息被篡改，區塊鏈上的其他節點會在短時間內發現這些未共識的節點并進行維護和更新。區塊鏈內的所有數據以鏈式存儲，通過時間戳技術可以追溯每筆數據的所有信息以及來源。智能合約（Smart contract）是一種可以在區塊鏈上部署的合約，一旦某個事件觸發合約中的條款，合約自動執行相應的措施。智能合約有去中心化的特點，合約透明并且一旦簽署便無法更改，保證簽署方的公平性。

2.3? 混淆電路

混淆電路是Andrew Yao在20世紀80年代發明的一種很智能的技術。它可以讓兩個人針對某個算式來計算答案，而不需要知道他們在計算式所輸入的數字。混淆電路是安全多方計算的一種解決方案，可以在參與方不泄露自己隱私信息的情況下進行多種類型的計算。例如Andrew Yao提出的百萬富翁問題：兩個百萬富翁想要知道誰的財產更多一些，但是不想讓對方知道自己的財富信息。可以使用混淆電路方案設計相應的電路計算出來結果并且不會泄露參與方的信息。混淆電路方案可以通過電路的設計來解決更為復雜的問題。

3? ? 方案描述

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

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

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

其中，E來自一個私鑰加密方案（例如G，E，D），該方案對多條消息進行了不可區分的加密，并且具有難以捉摸的有效驗證范圍。實際的門是由上述值的隨機排列來定義的，表示為c0，c1，c2，c3;從這里稱它們為門g的雜亂表。注意，給定k1α和k2β，以及c0，c1，c2，c3的值，可以如下計算門k3g（α，β）的輸出。對于每個i，計算。如果多個解密返回一個非值，則輸出中止。否則，將k3λ定義為獲得的唯一非值。（請注意，如果只獲得一個非值，那么這將是k3g（α，β），因為它是在給定的密鑰k1α和k2β下加密的。）

現在，我們準備展示如何構造整個混淆電路。設m為電路C中的導線數，設w1，…wj是這些電線的標簽。除以下情況外，這些標簽都是只選擇wi和wj為同一柵極g的兩根輸出線，則wi=wj。如果g>1，就會發生這種情況。同樣地，如果一個輸入位進入一個以上的柵極，那么與這個位相關聯的所有電路輸入線將具有相同的標簽。接下來，對于每個標簽wi，選擇兩個獨立的ki0，ki1←G（1n）;強調所有這些鍵都是獨立于其他鍵選擇的。現在，給定這些鍵，按上面描述的方式計算每個門的4個混淆值，并隨機排列結果。最后，計算了混淆電路的輸出或解密表。這些表只是由（0，ki0）和（1，ki1）的值組成，其中，wi是一種電路輸出線。或者，輸出門可以直接計算0或1。也就是說，在輸出門中，可以為每一個α，β∈{0，1}定義。C的整個亂碼電路，即G（C），由每個門的亂碼表和輸出表組成。由此注意到，給出了C的結構，通過指定每個門的輸出表和混亂表，可以簡單地定義C的混亂版本。這就完成了對混淆電路的描述。

最后，智能合約會將混淆電路的運算結果，同時返回給參與方。利用偽隨機函數生成公開參數，這些參數會影響到計算的結果。所以，根據密文計算的方法以及參數需要部署到智能合約，并由其執行驗證。智能合約計算出來的密文結果會由智能合約同時公開給每個參與方，避免參與方提前獲取結果并欺騙其他參與方。

[參考文獻]

[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，FUJIMURA 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，FUJIMURA 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.