熊 璐，楊 陽，沙金銳，范 磊

（1.中國銀聯(lián)股份有限公司，上海 201201；2.電子商務(wù)與電子支付國家工程實驗室，上海 201201；3.上海交通大學 網(wǎng)絡(luò)空間安全學院，上海 200240）

0 引言

近年來，區(qū)塊鏈技術(shù)作為密碼技術(shù)和分布式計算的一個重要研究方向得到了廣泛研究。由于它可以實現(xiàn)去中心化的數(shù)據(jù)一致性，可以廣泛應(yīng)用于數(shù)據(jù)交換與共享領(lǐng)域。但是，區(qū)塊鏈本身并不提供隱私保護功能，因此在需要對數(shù)據(jù)進行隱私保護的領(lǐng)域需要疊加額外的密碼協(xié)議給予保護。

目前，區(qū)塊鏈主要利用零知識證明、同態(tài)加密等密碼學技術(shù)解決數(shù)據(jù)隱私保護問題。例如，匿名電子貨幣系統(tǒng)Zcash[1]使用非交互式的零知識證明進行隱私保護。零知識證明允許雙方在不泄露任何信息的情況下，證明某個提議的真實性[2]。交易信息在Zcash 中是保密的，無關(guān)人員無法獲得交易中發(fā)送方地址、接收方地址與轉(zhuǎn)賬數(shù)額，但是他們通過零知識證明可以驗證支付是否有效。

零知識證明、全同態(tài)加密等密碼技術(shù)雖然可以實現(xiàn)數(shù)據(jù)的隱私保護，但是運行效率較低，在需要大量數(shù)據(jù)共享的領(lǐng)域無法提供有效的性能支持。隱私保護交集計算（Private Set Intersection，PSI）是安全多方計算領(lǐng)域內(nèi)的一個特殊應(yīng)用，應(yīng)用場景是參與者的數(shù)據(jù)表示成集合的形式，在不泄露各自參與方輸入信息的前提下，協(xié)同計算輸入集合的交集。

PSI 計算是Freedom 等[3]在2004 年提出，借助不經(jīng)意多項式求值和同態(tài)加密得以實現(xiàn)。但是，這種實現(xiàn)由于同態(tài)加密的效率問題計算代價較高。因此，傳統(tǒng)的應(yīng)用采用了單向散列函數(shù)實現(xiàn)PSI 技術(shù)，即對參與雙方的集合分別進行單向散列映射，在散列值的基礎(chǔ)上進行集合交集計算。這種方法很容易受到敵手的碰撞攻擊。

本文設(shè)計了一種基于區(qū)塊鏈的隱私保護交集算法（Blockchain Private Set Intersection，BPSI），利用區(qū)塊鏈的抗合謀性，解決服務(wù)端與參與的一方進行合謀的安全隱患，同時分析了該協(xié)議在惡意模型下的安全性機制、有效性機制以及仲裁機制。

1 預(yù)備知識

1.1 區(qū)塊鏈及其安全特性

區(qū)塊鏈是一種由區(qū)塊構(gòu)成的鏈式數(shù)據(jù)結(jié)構(gòu)，通過數(shù)字簽名等密碼算法實現(xiàn)數(shù)據(jù)的防篡改、防抵賴等安全特性。區(qū)塊鏈作為新型的分布式多方記賬系統(tǒng)，依托于智能合約技術(shù)逐漸由單純記錄數(shù)字貨幣的交易信息發(fā)展為一種支持多方參與的分布式計算系統(tǒng)。

Juan[4]等人于2015 年證明了區(qū)塊鏈理論的安全性。區(qū)塊鏈所能提供的安全性特性包括如下內(nèi)容。

（1）一致性。在分布式環(huán)境中，除了最新的若干區(qū)塊，所有的參與節(jié)點都能夠得到一致的數(shù)據(jù)結(jié)果。

（2）存活性。即便有惡意節(jié)點存在，區(qū)塊鏈仍然能持續(xù)不斷地記錄新的數(shù)據(jù)，保證系統(tǒng)的活性。

（3）公平性。誠實節(jié)點能夠為最終的區(qū)塊鏈產(chǎn)生區(qū)塊，所有用戶的信息都能得到記錄和存儲。

但是，區(qū)塊鏈協(xié)議并不能提供數(shù)據(jù)的隱私保護，區(qū)塊鏈中所承載的數(shù)據(jù)所有參與節(jié)點均能接收與防范，因此在需要隱私保護的場景應(yīng)疊加其他密碼技術(shù)。

1.2 隱私保護交集

PSI 計算技術(shù)根據(jù)是否有第三方參與可以分為兩大類。

1.2.1 傳統(tǒng)的PSI 計算技術(shù)

參與方直接交互執(zhí)行真實的協(xié)議，從而實現(xiàn)對隱私集合的交集計算。這類技術(shù)可以根據(jù)實現(xiàn)的原理分為基于公鑰加密機制的PSI、基于混亂電路的PSI 以及基于不經(jīng)意多項式的PSI。這里著重關(guān)注基于公鑰加密體制的PSI 協(xié)議。

基于公鑰加密體制的PSI 協(xié)議主要是對集合進行復雜的公鑰加密操作，并通過協(xié)議的設(shè)計使之能在密文上進行計算。根據(jù)協(xié)議的設(shè)計思想，又可以分為基于不經(jīng)意多項式的PSI、基于不經(jīng)意偽隨機函數(shù)的PSI 以及基于盲簽名的PSI。

對于基于不經(jīng)意多項式的PSI，自從Freedom等[3]在2004 年最先提出后，2016 年Freedom 等[5]又給出了隨機Hash、負載均衡Hash、布谷鳥Hash的實驗比對，證明了負載均衡Hash 和布谷鳥Hash的實驗效果相對更好。同時，2005 年Kissner 等[6]給出了利用基于多項式環(huán)的裴蜀定理的協(xié)議設(shè)計方法；2010 年Hazay[7]、Freedom 等[3]提出同態(tài)加密的PSI 協(xié)議，給出了惡意模型下利用cut and choose 的解決辦法；2017 年陳振華等[8]給出了給予離散對數(shù)且不依賴加密算法的PSI 協(xié)議。

對于基于不經(jīng)意偽隨機函數(shù)的PSI 協(xié)議，2008年Hazay 等[9]給出了根據(jù)OT 協(xié)議涉及的不經(jīng)意偽隨機函數(shù)的PSI 協(xié)議；2009 年Jarecki 等[10]基于復合剩余假設(shè)，利用Dodis-Yampolskiy 偽隨機函數(shù)[11]、Camenisch-Shoup 加法同態(tài)[12]以及零知識證明，提出了另一種PSI；2010 年Jarecki 等[13]又利用不可預(yù)測函數(shù)，提出了速度提升20 倍的PSI 協(xié)議。

對于基于盲簽名的PSI 協(xié)議，2010 年De Cristrofaro等[14]提出了基于RSA 的PSI 協(xié)議，但是該協(xié)議僅針對半誠實模型是安全的。為了解決惡意模型下的安全性問題，De Cristrofaro 等[15]在2010 年提出了基于零知識證明的PSI 協(xié)議，同時給出了傳統(tǒng)PSI的效率比對[16]，證明了基于零知識證明的PSI 協(xié)議是在幾個經(jīng)典的傳統(tǒng)PSI 模型中效率最高的。

1.2.2 云輔助的PSI 計算技術(shù)

主要利用云服務(wù)器的計算資源進行隱私交集的安全計算，云服務(wù)器承擔著交集計算的作用，但是不會得到任何的明文信息。云輔助的PSI 技術(shù)大大提升了隱私計算的效率，但是在模型中要假設(shè)云端是可信的，從而解決云端與某一參與方的合謀性，否則將退化成兩個計算能力相差懸殊的安全多方計算協(xié)議。

近幾年，云輔助的PSI 協(xié)議才有了相關(guān)細致的研究，由Kerschbaum 等[17]在2012 年提出，分別是基于hash 函數(shù)和RSA 公鑰加密算法的PSI 協(xié)議。但是，兩個方案一個是犧牲安全性換來高效性，另一個是犧牲高效性換來安全性。2014 年Liu 等[18]提出了基于對稱加密和非對稱加密的PSI 協(xié)議，實現(xiàn)相對簡單，但泄露了交集基數(shù)。2014 年Kamara等[19]提出了基于偽隨機函數(shù)的PSI 協(xié)議，解決了惡意模型，且有著較高的計算效率，但存在不抗合謀缺陷。2015 年Abadi[20]提出了基于同態(tài)加密和多項式插值的PSI 協(xié)議，但是存在效率較低的問題。

2 協(xié)議設(shè)計

2.1 場景描述

傳統(tǒng)的PSI 技術(shù)不適用于大規(guī)模場景，這是因為基于公鑰加密機制協(xié)議的開銷很大，不適合大規(guī)模信息的傳輸比對；基于混亂電路的協(xié)議需要將電路提前構(gòu)建并全部加載到內(nèi)存中，當集合很大時會造成內(nèi)存的限制；基于布隆過濾器的協(xié)議需要加載布隆過濾器結(jié)構(gòu)至內(nèi)存。所以，上述辦法都不適合大規(guī)模數(shù)據(jù)的應(yīng)用。

云輔助的PSI 技術(shù)解決了大規(guī)模數(shù)據(jù)的應(yīng)用問題，但由于現(xiàn)在的云服務(wù)器大多都是私有云，所以云服務(wù)器存在與參與方進行合謀的隱患。區(qū)塊鏈相比云服務(wù)端，由于是基于去中心化的共識協(xié)議，可以有效避免某一參與者與中心合謀的攻擊問題。

相比傳統(tǒng)的PSI 協(xié)議和云輔助的PSI 協(xié)議，區(qū)塊鏈因為鏈上信息公開透明，任何人都可以看到鏈上的信息，所以對于密鑰協(xié)商、加密處理等步驟是完全不同的。因此，需要根據(jù)區(qū)塊鏈的特性設(shè)計新的PSI 協(xié)議，這里稱為基于區(qū)塊鏈的隱私保護交集協(xié)議——BPSI 協(xié)議。

本文尤其關(guān)注一類具體的應(yīng)用場景，如金融機構(gòu)間信用數(shù)據(jù)共享、致病基因檢測等。在這種場景中，服務(wù)的申請者可以預(yù)先知道服務(wù)提供者數(shù)據(jù)集合的部分信息，如所有金融機構(gòu)已知的失信人員、部分已知的致病基因片段等?；诖思僭O(shè)，服務(wù)申請者可嵌入隨機先驗點位，從而檢測服務(wù)提供者返回結(jié)果的有效性。

2.2 符號定義

本文基于Kamara 等[19]提出的云輔助的基于偽隨機函數(shù)加密的PSI 技術(shù)的基礎(chǔ)協(xié)議，設(shè)計了一種適用于區(qū)塊鏈系統(tǒng)的BPSI 協(xié)議。在給出具體的算法前，本文協(xié)議設(shè)計中使用的參數(shù)定義如表1 所示。

表1 協(xié)議符號與參數(shù)

2.3 協(xié)議流程

協(xié)議的執(zhí)行流程如圖1 所示。

協(xié)議執(zhí)行過程如下。

圖1 BPSI 協(xié)議流程

定義與輸出：F:{0,1}k×U→{0,1}≥k

協(xié)議流程：

3 協(xié)議分析

3.1 安全性分析

協(xié)議的兩個參與方分別為服務(wù)的發(fā)起者P1服務(wù)提供者P2以及區(qū)塊鏈系統(tǒng)S。由于用戶P1是協(xié)議的發(fā)起者，在計算過程中由于需要獲取有用信息，故需要提供自己真實信息并按照協(xié)議要求執(zhí)行，為半誠實模型。協(xié)議執(zhí)行過程的安全性依賴于區(qū)塊鏈技術(shù)保證。在區(qū)塊鏈參與節(jié)點較多時，它被惡意節(jié)點控制的概率較小，即是惡意模型的概率很小。因此，假設(shè)S是半誠實模型（由于區(qū)塊鏈上信息公開，故存在被第三方利用的可能）。

服務(wù)提供者P2可能不遵守服務(wù)過程與協(xié)議，因此被視為惡意模型。容易得到，當P2發(fā)生不遵守協(xié)議的行為時，用戶P1可以在本地進行安全性核查。這是由于在偽隨機置換協(xié)議中引入了信息復制操作Sλ、補充參量操作τi=D0∪D1和隨機擾動操作∏，從而客戶端不履行協(xié)議（如：不參與協(xié)議、修改隱私的輸入集合信息、提前終止協(xié)議的執(zhí)行）時，會導致最后上傳集合的不完整或錯誤，從而在進行安全性校驗時發(fā)現(xiàn)該錯誤。此外，由于引入冗余保護機制，P2的破解空間明顯增大（λ倍以上），使得暴力破解方式（如彩虹表攻擊等）難度更大，破解成功概率更低。

另外，考慮到由于P2可能提供錯誤的信息來達到獲取他人信息的惡意目的，在算法外引入有效性機制檢驗。在區(qū)塊鏈可信任的前提下，用戶端通過引入先驗性知識對服務(wù)商數(shù)據(jù)進行概率性校驗，避免服務(wù)商惡意更改輸出的情況。在區(qū)塊鏈可信任的前提下，本系統(tǒng)的安全級別超過了多種傳統(tǒng)云隱私保護交集技術(shù)的安全性能[17-20]，并從根本上解決了多方合謀的安全隱患。

3.2 協(xié)議有效性

有效性機制是考慮如果P2并沒有真正利用有限數(shù)據(jù)做交集計算，在這種情況下P1應(yīng)能驗證結(jié)果的有效性。

對于用戶P1，其上傳自己數(shù)據(jù)前應(yīng)該先進行監(jiān)測點嵌入。

（1）用戶P1在需要檢測的數(shù)據(jù)結(jié)合中，隨機嵌入a個P2數(shù)據(jù)集合中明確包含的數(shù)據(jù)點，上傳到區(qū)塊并請求計算服務(wù)；

（2）服務(wù)方P2訪問區(qū)塊鏈，得到P1上傳的待計算集合；

（3）服務(wù)提供者P2將進行交集計算，并將結(jié)果上傳到區(qū)塊；

（4）用戶P1訪問區(qū)塊鏈，比對服務(wù)提供者P2是否檢測出a個隨機嵌入的數(shù)據(jù)點；

（5）如果a個數(shù)據(jù)點全部檢測出來，認為服務(wù)提供者P2是誠實的；否則，服務(wù)提供者P2是惡意的。

下面對有效性機制進行證明。

不妨設(shè)雙方數(shù)據(jù)集合公有n+a個元素。如果服務(wù)提供者P2是惡意的，第一種可能是P2故意上傳了錯誤的交集元素，由有效性機制可直接判定；第二種可能是交集元素是服務(wù)提供者P2隨機生成的，所以服務(wù)提供者P2為惡意的敵手，且無法檢測出來的概率為。例如，惡意服務(wù)提供者隨機返回交集，安全參數(shù)α≥10 時，計算得到無法檢測出敵手的概率，是一個較小的數(shù)值。因此，當安全參數(shù)a足夠大時，服務(wù)提供者P2成功欺騙用戶的概率可以忽略不計。

3.3 協(xié)議仲裁機制

本節(jié)給出該系統(tǒng)的仲裁機制算法設(shè)計和說明。值得注意的是，仲裁機制依賴于安全性與有效性的分析。仲裁節(jié)點由可信第三方負責，若用戶P1與服務(wù)提供者P2雙方在整個過程中完全遵守協(xié)議運行，則無需仲裁節(jié)點參與。但是，在數(shù)據(jù)傳輸和結(jié)果返回過程中，若有任何一方提出異議，則需要將此次共享過程提交給仲裁方進行判定。仲裁法進行審判后，失敗方將受到懲罰，具體懲罰機制可由聯(lián)盟自行約定，不在本系統(tǒng)中做具體規(guī)定。本系統(tǒng)設(shè)計的仲裁機制需要在聯(lián)盟中的各個節(jié)點配合的情況下才能成功解決爭議。該仲裁機制與CCP 機制中的中央對手方作用類似，增加了系統(tǒng)的中心化色彩，區(qū)別在于CCP 需要對每一筆交易進行校驗，但本系統(tǒng)的仲裁只在參與雙方提出異議時工作。

對于本系統(tǒng)，因為用戶P1與服務(wù)提供者P2雙方資源差距過大，所以只考慮用戶P1申請仲裁帶來的影響。

用戶P1控訴服務(wù)提供者P2，當用戶P1對交集部分的數(shù)據(jù)解密后，安全校驗出現(xiàn)錯誤，即出現(xiàn)且時，說明安全校驗出現(xiàn)問題，此時仲裁介入。由于區(qū)塊鏈的不可篡改性，D0、D1、D2均有記錄。用戶P1將安全校驗的錯誤通過智能合約發(fā)布在鏈上，仲裁通過判定安全校驗的錯誤性，判定用戶P1與服務(wù)提供者P2誰將勝訴。

用戶P1控訴服務(wù)提供者P2上傳的數(shù)據(jù)不正確，當進行有效性檢測時，用戶P1上傳的集合中k個數(shù)據(jù)點存在未檢測出的，此時仲裁介入。用戶P1將進行有效性檢測的加密密鑰和上傳的帶有的k個數(shù)據(jù)點通過智能合約發(fā)布在鏈上。仲裁通過將這k個數(shù)據(jù)點利用密鑰加密，與之前得到的交集進行比較。仲裁通過是否存在某加密后的序列段不在之前的交集內(nèi)，判定用戶P1與服務(wù)提供者P2誰將勝訴。

4 結(jié)語

本項目研究了隱私保護交集（PSI）協(xié)議的設(shè)計方法，分析了現(xiàn)有方案中傳統(tǒng)PSI 技術(shù)和云輔助PSI 技術(shù)的不足，提出了基于區(qū)塊鏈的隱私保護交集協(xié)議BPSI，并給出了針對惡意模型下的安全性和有效性的算法改進。該方案在特定的數(shù)據(jù)共享場景下，解決了現(xiàn)有模型不抗合謀、效率較低、可追蹤等缺陷，具有廣闊的應(yīng)用前景。