基于區(qū)塊鏈的隱私保護(hù)交集算法*

熊 璐，楊 陽(yáng)，沙金銳，范 磊

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

0 引言

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

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

（3）公平性。誠(chéng)實(shí)節(jié)點(diǎn)能夠?yàn)樽罱K的區(qū)塊鏈產(chǎn)生區(qū)塊，所有用戶的信息都能得到記錄和存儲(chǔ)。

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

1.2 隱私保護(hù)交集

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

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

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

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

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

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

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

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

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

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

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

2.1 場(chǎng)景描述

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

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

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

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

2.2 符號(hào)定義

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

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

2.3 協(xié)議流程

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

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

圖1 BPSI 協(xié)議流程

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

協(xié)議流程：

3 協(xié)議分析

3.1 安全性分析

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

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

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

3.2 協(xié)議有效性

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

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

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

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

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

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

（5）如果a個(gè)數(shù)據(jù)點(diǎn)全部檢測(cè)出來(lái)，認(rèn)為服務(wù)提供者P2是誠(chéng)實(shí)的；否則，服務(wù)提供者P2是惡意的。

下面對(duì)有效性機(jī)制進(jìn)行證明。

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

3.3 協(xié)議仲裁機(jī)制

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

對(duì)于本系統(tǒng)，因?yàn)橛脩鬚1與服務(wù)提供者P2雙方資源差距過(guò)大，所以只考慮用戶P1申請(qǐng)仲裁帶來(lái)的影響。

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

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

4 結(jié)語(yǔ)

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