申立艷 陳小軍 時金橋 胡蘭蘭

1(中國科學院大學網(wǎng)絡空間安全學院 北京 100049) 2(中國科學院信息工程研究所 北京 100093) (shenliyan@iie．a(chǎn)c．cn)

2017-06-11；

2017-07-28

國家自然科學基金項目(61602474) This work was supported by the National Natural Science Foundation of China (61602474).

陳小軍(chenxiaojun@iie.ac.cn)

隱私保護集合交集計算技術研究綜述

申立艷1,2陳小軍2時金橋2胡蘭蘭2

1(中國科學院大學網(wǎng)絡空間安全學院 北京 100049)2(中國科學院信息工程研究所 北京 100093) (shenliyan@iie．a(chǎn)c．cn)

隱私保護集合交集(private set intersection, PSI)計算屬于安全多方計算領域的特定應用問題，不僅具有重要的理論意義也具有很強的應用背景，在大數(shù)據(jù)時代，對該問題的研究更是符合人們日益強烈的在享受各種服務的同時達到隱私保護的需求.對安全多方計算基礎理論進行了簡要介紹，并重點介紹了目前主流的安全多方計算框架下2類PSI研究技術：傳統(tǒng)的基于公鑰加密機制，混亂電路，不經(jīng)意傳輸?shù)腜SI協(xié)議和新型的云輔助的PSI協(xié)議，并對各類協(xié)議的過程、適用性、復雜性進行簡要分析總結.同時，也對隱私保護集合交集問題的應用場景進行詳細說明，進一步體現(xiàn)對該問題的實際研究價值.隨著對該問題的不斷深入研究，目前已經(jīng)設計了在半誠實模型下快速完成上億元素規(guī)模的隱私集合求交集協(xié)議.

隱私保護集合交集；安全多方計算；不經(jīng)意傳輸；混亂電路；不經(jīng)意偽隨機函數(shù)計算；不經(jīng)意多項式計算；云計算

隨著通信技術、網(wǎng)絡技術等的快速發(fā)展以及移動計算、云計算、分布式計算等廣泛應用，虛擬網(wǎng)絡和人們的生活聯(lián)系更加緊密，互聯(lián)網(wǎng)大數(shù)據(jù)的各種應用滲透到人們的社交、購物、出行等方方面面.這些應用讓人們享受到更加便捷的服務，但同時大量有價值的客戶信息、個人的隱私記錄、企業(yè)運營數(shù)據(jù)不斷被挖掘，人們的隱私受到越來越強烈的威脅.因此，大數(shù)據(jù)時代的隱私保護問題成為學術界及工業(yè)界關注的焦點.

從數(shù)據(jù)生命周期角度來看，數(shù)據(jù)經(jīng)歷了數(shù)據(jù)發(fā)布、數(shù)據(jù)存儲、計算挖掘和數(shù)據(jù)使用等環(huán)節(jié)，據(jù)此研究者提出了大數(shù)據(jù)發(fā)布隱私保護技術、大數(shù)據(jù)存儲隱私保護技術、大數(shù)據(jù)計算和挖掘隱私保護技術以及大數(shù)據(jù)訪問控制技術等來從各個環(huán)節(jié)保護數(shù)據(jù)的隱私[1].而在這些大數(shù)據(jù)隱私保護技術里，更基本的技術是隱私保護的數(shù)據(jù)計算，指能夠滿足人們在不泄露額外信息的同時，完成隱私數(shù)據(jù)之間的計算任務，比如相似性計算[2-3]、距離計算[4-6]等任務.本文主要關注其中的一類即隱私保護集合交集計算技術.

常用的大數(shù)據(jù)隱私保護技術手段包括匿名、失真、加密、安全多方計算等的方法[1].安全多方計算作為一種特殊的分布式環(huán)境下的隱私保護計算方法在近年來受到研究者的普遍關注，已經(jīng)成為密碼學領域的重要研究方向.安全多方計算是由圖靈獎獲得者姚期智在1982年提出[7]，主要解決在分布式計算場景下互不信任的數(shù)據(jù)擁有者安全協(xié)同計算問題，既實現(xiàn)了資源共享又保證了數(shù)據(jù)隱私性需求.安全多方計算包含的內容十分豐富，包括基礎理論模型研究[8-10]、基礎密碼協(xié)議研究、特定應用協(xié)議等的研究.基礎密碼協(xié)議包含混亂電路(garbled circuit， GC)、不經(jīng)意傳輸(oblivious transfer, OT)、秘密共享(secret sharing, SS)、同態(tài)加密(homomorphic encryp-tion, HE)、零知識證明(zero knowledge proof)、擲幣協(xié)議(coin tossing)、比特承諾(bit commitment)協(xié)議等，這些密碼協(xié)議都可以看作特殊的安全多方計算問題，由一組存在各種信任關系的參與者通過交互或非交互操作來完成某一功能函數(shù)的安全計算；特定應用協(xié)議研究包括隱私集合運算[11-12]、隱私保護數(shù)據(jù)挖掘[13-16]、隱私保護信息檢索[17-19]、幾何計算[20-21]等.基礎密碼協(xié)議成為應用協(xié)議設計的基本工具，其安全性和效率直接影響調用它們的應用協(xié)議的安全性和效率.

隱私保護集合交集(private set intersection, PSI)計算是安全多方計算領域的一個重要方面，不僅在科學計算中有很好的體現(xiàn)，在現(xiàn)實生活中很多數(shù)據(jù)都可以用集合來表示，并用集合間的隱私保護計算來完成一些數(shù)據(jù)計算問題，因此PSI計算有很廣泛的應用場景.對該問題的具體定義是在不泄露各自參與方輸入信息的前提下，協(xié)同計算輸入集合的交集.典型的應用場景有隱私保護相似文檔檢測、私有聯(lián)系人發(fā)現(xiàn)、安全的人類基因檢測[22]、隱私保護的近鄰檢測[23]、隱私保護的社交網(wǎng)絡關系發(fā)現(xiàn)[24]、在線推薦服務和婚戀網(wǎng)站配對等.在數(shù)據(jù)由不同管理者持有的條件下，PSI計算達到一種保護隱私與信息共享的共贏.

PSI計算研究由Freedman等人在2004年提出[25]，借助不經(jīng)意多項式求值和同態(tài)加密實現(xiàn).這種實現(xiàn)受限于基礎密碼協(xié)議的計算代價，傳統(tǒng)的應用系統(tǒng)還是采用不安全Hash協(xié)議*https://www.eff.org/deeplinks/2012/09/deep-dive-facebook-and-datalogix-whats-actually-getting-shared-and-how-you-can-opt實現(xiàn)PSI，即對參與方的集合分別進行Hash映射，在Hash值基礎上求集合交集.顯而易見，這種方法很容易受到碰撞攻擊.隨著近年來對PSI問題的深入研究，在NDSS，USENIX，CCS等著名國際信息安全會議上涌現(xiàn)了大量的相關研究成果.對該問題的研究不僅推動安全多方計算基礎理論的研究發(fā)展，也推動了PSI計算實際應用問題研究的發(fā)展.目前某些PSI協(xié)議的性能已經(jīng)得到了很大的提高，在通信和計算復雜度上達到了與不安全的Hash協(xié)議同樣的量級[26].

PSI計算技術根據(jù)是否有第三方參與主要分為兩大類：1)傳統(tǒng)的PSI計算技術，參與方直接交互執(zhí)行真實的協(xié)議，達到隱私計算集合交集的目的，這類技術根據(jù)實現(xiàn)原理又包含基于公鑰加密機制、混亂電路和不經(jīng)意傳輸?shù)?類PSI協(xié)議；2)云輔助的PSI計算技術，也叫外包的隱私保護集合交集計算(outsourced private set intersection, OPSI)，主要利用云服務器的強大計算資源，完成安全交集計算.與理想?yún)f(xié)議中的可信第三方一樣，云服務器主要承擔計算交集的作用，但沒有任何輸入輸出信息.表1為2類方法異同點對比.

Table 1 The Comparison of Two Research Methods for PSI表1 PSI兩類研究方法對比

本文擬對PSI技術的研究現(xiàn)狀進行全面的梳理，針對傳統(tǒng)的PSI計算技術和云輔助的PSI技術的具體研究思路、研究方法、適用的安全假設、敵手模型和性能開銷進行詳細介紹和對比，并對基于PSI計算技術的應用研究做了簡要的整理，對當前PSI計算技術存在的問題和研究趨勢進行總結和建議.

1 基礎原語

1.1安全性證明方法

任何提出的安全協(xié)議都需要進行安全性證明，一般來說，在安全多方計算中提出的安全協(xié)議通過與理想模型進行對比來證明其安全性.所謂理想模型是指存在可信的第三方，其計算能力是概率多項式時間，通過安全信道獲得各參與方的隱私輸入并計算功能函數(shù)f，將結果秘密發(fā)送給協(xié)議參與方.對于所提出的安全協(xié)議在證明其安全性時，需要對比理想模型來說明每一個參與方都不會獲得更多的信息，這種安全性證明方法叫理想-現(xiàn)實模擬方法[27]；如果放寬安全性要求，只需某一參與方遵循安全要求的話，稱為單邊模擬方法.

1.2安全模型

在協(xié)議的安全性證明過程中，有2類非常重要的基礎模型，分別是標準模型和隨機預言模型.標準模型(standard model， Std)指不依賴任何假想模型，僅依賴于被廣泛接受的困難性假設(如因子分解、離散對數(shù)等)，這些數(shù)學難題是攻擊者在多項式時間內不可解的.僅使用困難性假設證明安全的機制稱為在標準模型下是安全的.隨機預言模型(random oracle model， ROM)[28]比標準模型多了一個隨機預言機的假設，隨機預言機假設存在一個公共的、隨機選擇的函數(shù)(理論上的黑盒子)，只能通過問詢的方式進行計算，對每一次查詢都從輸出域中均勻隨機地輸出一個響應，對相同的查詢總是得到相同的響應.由于現(xiàn)實中沒有函數(shù)能夠實現(xiàn)真正的隨機函數(shù)，因此隨機預言模型下可證明安全的方案在實際應用中通常用Hash函數(shù)進行實例化.

1.3敵手模型

根據(jù)敵手腐敗參與方的行為方式，敵手模型一般分為3類[27]：

1) 半誠實模型(honest but curious adversary, HbC).協(xié)議的各參與方遵守協(xié)議的執(zhí)行過程，但可以在協(xié)議執(zhí)行過程中，根據(jù)輸入和協(xié)議的輸出信息推斷其他參與者的信息.

2) 惡意模型(malicious adversary, Mal).參與者不遵守協(xié)議的執(zhí)行過程，可能拒絕參與協(xié)議、修改隱私的輸入集合信息、提前終止協(xié)議的執(zhí)行等，因此需要使用更多的密碼協(xié)議或技術(位比特承諾協(xié)議、零知識證明等)來保證計算結果的正確性.

3) 隱蔽敵手模型(covert adversary).是一種安全性介于半誠實模型和惡意模型之間的更符合真實場景的模型，由于擔心惡意行為被協(xié)議檢測出來并受到懲罰，隱蔽敵手使其惡意行為混淆在正常行為中，只能以一定的概率被檢測到.

1.4基礎協(xié)議

不經(jīng)意傳輸協(xié)議(OT)是基于公鑰密碼體制的密碼學基本協(xié)議，是安全多方計算的基石.最基本的二選一OT協(xié)議的發(fā)送方Bob輸入2個隨機位串(x0,x1)，接收方Alice輸入選擇向量c；協(xié)議結束后Alice獲得選擇向量對應的位串xc，對另一個位串x1-c一無所知；Bob的輸出為空[29].在1988年Impagliazzo 和 Rudich 證明了從不經(jīng)意傳輸協(xié)議到單向函數(shù)的黑盒式規(guī)約蘊含著另一個難以被證明的問題，即P≠NP的問題，并表示不存在黑盒方式的OT協(xié)議[30]，因此OT協(xié)議通常是基于公鑰密碼體制來構造.然而在安全多方計算應用中一般需要大量的OT協(xié)議作為子協(xié)議，計算復雜的模指數(shù)運算，使得OT協(xié)議的實用價值不高.1996年Beaver依據(jù)混合加密構想提出了第1個非黑盒方式的不經(jīng)意傳輸擴展協(xié)議[31]，可以執(zhí)行少數(shù)基礎OT協(xié)議(傳統(tǒng)的基于公鑰加密算法的OT協(xié)議)來構造大量的OT協(xié)議，然而Beaver提出的協(xié)議需要計算復雜的偽隨機發(fā)生器，在實際中也不高效，但是擴展協(xié)議的思想具有重要的影響.基于OT擴展協(xié)議的思想Ishai等人在2003年提出了以黑盒方式構造的OT擴展協(xié)議[32]，將基礎OT協(xié)議和隨機預言模型相結合，把少量基礎OT的計算代價通過對稱加密操作均攤到大量的OT操作，可以達到1 min執(zhí)行數(shù)百萬次的OT協(xié)議，該協(xié)議可以同時滿足實用性和安全性需求，具有重要的意義并得到很廣泛的應用，例如GMW協(xié)議、姚氏混亂電路、PSI等.隨著人們對實用性要求越來越高，OT擴展協(xié)議得到了快速發(fā)展，主要包括對N選1不經(jīng)意傳輸擴展協(xié)議[33]及隨機OT[34]協(xié)議的提出.

混亂電路(GC)模型最早是由圖靈獎獲得者姚期智在1986年提出的半誠實模型下的姚氏電路[35]，用來解決著名的百萬富翁問題.姚氏電路主要是將任意功能函數(shù)轉化為布爾電路，由Alice生成混亂電路表、Bob計算混亂電路；針對每一個電路門進行兩重對稱加解密運算，調用四選一OT協(xié)議進行混亂電路表中秘鑰信息交換.早期的安全函數(shù)計算問題主要采用混亂電路來解決，由于混亂電路對每一位進行電路門計算并且電路門數(shù)量巨大，導致計算效率較低，例如計算AES加密大約需要30 000個電路門，計算50個字符串的編輯距離大約需要250 000個電路門[36].混亂電路作為通用的安全多方計算工具，可以用來計算任意的功能函數(shù),相對于特定問題的安全協(xié)議計算效率較低.針對這些問題，研究者提出了一系列的電路優(yōu)化策略[37]，包括Free-XOR、行約減[38-39]、Half-Gate技術[40].此外還提出了新的混亂電路協(xié)議，包括由Goldreich等人提出基于秘密共享和OT協(xié)議的GMW編譯器[8]以及基于剪切-選擇技術(cut and choose)[41]的適用于惡意模型的混亂電路等.除了對布爾電路的研究人們也提出了算術電路，完成有限域上加法或乘法運算.混亂電路方法作為安全多方計算問題的一般通用解決方法，近年來得到了快速的發(fā)展，已經(jīng)有很多實用的安全多方計算工具，例如Fairplay[42],FastGC[43],Oblivm[44],SEPIA[45],VIFF[46],Sharemind[47]等.

同態(tài)加密(HE)是滿足同態(tài)性質的公鑰加密技術，屬于語義安全的公鑰加密體制范疇.同態(tài)加密對密文進行某種算術操作(加或者乘)，滿足對密文計算結果的解密值與對明文進行同樣算術操作的值是相同的性質.由于計算是在密文上進行，因此同態(tài)加密是一種常用的實現(xiàn)隱私保護的方法.

秘密共享(SS)將秘密以適當?shù)姆绞椒譃閚份，每一份由不同的管理者持有，每個參與者無法單獨恢復秘密，只有達到指定數(shù)目的參與者才能恢復秘密.構建秘密共享系統(tǒng)的關鍵是設計好的秘密拆分和恢復方式.第1個秘密共享方案是(t,n)門限秘密共享方案，由Shamir[48]和Blakley[49]分別在1979年各自獨立提出，他們的方案分別是基于拉格朗日插值法和線性幾何投影性質設計的.此后很多研究者提出了不同的秘密共享實現(xiàn)方法，如基于中國剩余定理的秘密共享策略、可驗證的秘密共享等.秘密共享在密鑰管理分布式數(shù)據(jù)安全領域有許多應用，如電子投票、 密鑰托管、電子支付協(xié)議等，可以防止密鑰存儲過于集中，是一種兼顧機密性和可靠性的方法.

1.5符號說明

為了方便后續(xù)的討論，本文對所有的數(shù)學符號含義進行統(tǒng)一約定，如表2所示:

Table 2 The Notation and Description表2 符號說明

2 傳統(tǒng)的PSI計算技術

傳統(tǒng)的PSI協(xié)議主要是參與方之間通過一系列底層的密碼學技術直接進行交互計算，根據(jù)底層所采用技術的不同主要分為3類協(xié)議，分別為基于公鑰加密機制的PSI、基于混亂電路的PSI、基于OT協(xié)議的PSI.

2.1基于公鑰加密體制

基于公鑰加密體制的方法主要對集合元素進行復雜的公鑰加密操作如同態(tài)加密，并在密文上進行計算.根據(jù)協(xié)議設計思想的不同又分為基于不經(jīng)意多項式計算(oblivious polynomial evaluation, OPE[50])的PSI、基于不經(jīng)意偽隨機函數(shù)(oblivious evaluation of pseudorandom functions, OPRF)的PSI和基于盲簽名的PSI.

2.1.1 基于不經(jīng)意多項式計算的PSI

不經(jīng)意多項式計算的PSI協(xié)議主要是將參與方集合元素表示為多項式的根，利用多項式的數(shù)學性質來計算交集，并采用同態(tài)加密算法加密交互過程中的信息來保證協(xié)議的隱私性.

與文獻[25]中的方法不同，2005年Kissner等人提出不經(jīng)意多項式計算PSI協(xié)議的另一種實現(xiàn)[11].該協(xié)議依據(jù)多項式的數(shù)學性質來求集合交集：任意2個集合SA,SB表示為多項式PA,PB，那么gcd(PA,PB)表示集合交集SA∩SB，gcd表示最大公約數(shù).協(xié)議的計算過程為：客戶端將集合元素表示為v次多項式PA的根,在多項式環(huán)R[x]上隨機選取v次多項式γA并計算PA.γA,同理服務端將集合元素表示為v次多項式PB的根*為描述簡單起見，此處假設客戶端和服務器端集合大小相同均為v.，隨機選取v次多項式γB計算PB.γB并將計算結果同態(tài)加密發(fā)送給客戶端；此時，客戶端可以計算PA.γA+PB.γB=u.gcd(PA,PB) .根據(jù)文獻[11]中的定理有：由于γA和γB為隨機選擇的多項式，u為多項式環(huán)上均勻分布的任意2v-|SA∩SB|次多項式，其解為集合SA或SB中元素的概率可忽略不計.因此,客戶端利用同態(tài)加密的性質在密文上完成PSI計算.該協(xié)議被證明多個參與者在半誠實敵手模型下是安全的.針對惡意敵手模型,文中采用零知識證明技術防止參與方偏離協(xié)議執(zhí)行.基于同樣的思想，Dachman等人提出將多項式進行秘密共享的惡意模型下的PSI協(xié)議[56].在2017年，周素芳等人也在將集合表示成多項式的基礎上利用秘密共享協(xié)議設計了半誠實模型下高效的PSI方案[57].

針對惡意敵手模型，文獻[25]在其基礎上提出對惡意客戶端采用cut and choose技術，對惡意服務器端采用隨機預言模型，保證協(xié)議的安全性.2010年Hazay等人對文獻[25]中協(xié)議進一步改進，提出了一種適用于標準模型下惡意敵手的協(xié)議[59].該協(xié)議將文獻[25]中的z=Enc(r.P(y)+y)替換為z=Enc(r.P(y)+s)，其中s與y相互獨立，s由服務器端隨機生成，并將s的比特承諾值發(fā)送給客戶端，s同時也用來計算偽隨機函數(shù)[60]r=Fk(s).如果客戶端某一元素x不屬于集合交集，那么Dec(z)為一隨機數(shù)，反之客戶端會獲得s=Dec(z)，客戶端通過對比Dec(z)的值和s的比特承諾值確定元素x是否屬于集合交集.進一步，客戶端通過與服務器端交互可獲得偽隨機函數(shù)值r=Fk(s)，可以用來檢驗服務器端傳輸加密數(shù)據(jù)的正確性.該協(xié)議采用比特承諾協(xié)議可以有效防止服務端輸入數(shù)據(jù)不一致以及零知識證明協(xié)議保證客戶端輸入多項式不恒為零.

2.1.2 基于不經(jīng)意偽隨機函數(shù)的PSI

基于不經(jīng)意偽隨機函數(shù)的PSI協(xié)議主要思想是客戶端和服務器端利用不經(jīng)意偽隨機函數(shù)Fk()來計算不經(jīng)意偽隨機函數(shù)值集合{Fk(x)}x∈X,{Fk(y)}y∈Y,再完成集合交集計算.其中，在不經(jīng)意偽隨機函數(shù)的計算過程中，服務器端擁有計算秘鑰k,客戶端輸入X通過協(xié)同計算得到{Fk(x)}x∈X，服務器端在本地計算{Fk(y)}y∈Y并發(fā)送給客戶端.該過程中客戶端不能得到任何有關函數(shù)Fk()和秘鑰k的信息，服務器端不能得到任何有關X的信息，從而保證信息的隱私性.

與文獻[61]不同，2009年Jarecki等人基于復合剩余假設提出了另一種PSI協(xié)議[62]，該協(xié)議采用Dodis-Yampolskiy偽隨機函數(shù)[63]的形式:Fk(x)=g,利用Camenisch-Shoup[64]加同態(tài)加密和零知識證明技術實現(xiàn)偽隨機函數(shù)的計算，進一步在偽隨機函數(shù)值集合上完成交集運算.該協(xié)議依賴于公共參考串模型并限制輸入集合定義域大小，是惡意模型下可證明安全的PSI協(xié)議.

2.1.3 基于盲簽名的PSI

基于盲簽名PSI協(xié)議的主要思想是客戶端將集合元素盲化處理，然后讓服務器端對盲化的消息進行簽名，最后客戶端對簽字除去盲因子，得到服務器端關于集合元素的簽名{Sign(x)}x∈X；服務器端在本地計算集合元素簽名{Sign(y)}y∈Y并發(fā)送給客戶端；客戶端在{Sign(x)}x∈X{Sign(y)}y∈Y的基礎計算集合交集.基于盲簽名函數(shù)的設計本身可保證協(xié)議信息的隱私性.

2.1.4 公鑰加密的PSI性能比較分析

為了對以上各協(xié)議性能有更直觀的認識，分別從安全模型(標準模型、隨機預言模型)、敵手模型(半誠實、惡意敵手)的角度對客戶端和服務器端計算和通信復雜度進行漸進分析.分析結果如表3所示：

Table 3 Comparison of Private Set Intersection Protocols表3 隱私集合交集協(xié)議性能比較

Note： exps denotes modular exponentiations operation.

幾種協(xié)議的通信復雜度一般都與集合元素成線性關系，協(xié)議主要的操作均為復雜的模指數(shù)操作，計算復雜度通常與模指數(shù)的長度成線形關系，由于大部分協(xié)議采用同態(tài)加密及其他公鑰算法指數(shù)和模數(shù)一般為1 024 b以上，而De Cristofaro等人提出的PSI協(xié)議模指數(shù)計算中的指數(shù)為160 b，模數(shù)為1 024 b，因此計算復雜度最低.

2.2基于混亂電路

理論上講，任意的功能函數(shù)均可用基本的電路門形式來表示，即可以通過電路解決任意功能函數(shù)計算問題，因此可以用混亂電路的方法計算PSI問題.基于混亂電路的PSI協(xié)議主要思想有2種:1)將元素映射到二進制向量，通過向量的與運算求集合交集；2)通過電路解決隱私保護的元素相等性判斷問題，然后通過集合中元素的兩兩比較以O(n2)復雜度計算集合交集.

2012年Huang等人提出了3種基于姚氏混亂電路PSI協(xié)議的實現(xiàn)[71]，分別為BWA(Bitwise-AND)，PWC(Pairwise-Comparisons)，SCS(Sort-Compare-Shuffle)，分別適用于不同的集合規(guī)模和集合定義域大小的計算.其中，BWA協(xié)議將集合中σ位長的元素表示成長度為2σ位向量，向量中每一位表示集合中一個元素，位向量中某一位為1表示元素在集合中，為0表示該元素不在集合中.通過混亂電路對參與方集合向量進行位與運算得出交集集合的位向量，進而得到相應元素.PWC協(xié)議主要通過混亂電路對兩方的元素進行兩兩相等判斷，首先將2個長度為σ位的元素進行XOR運算，并將計算結果的每個位進行OR運算，由于協(xié)議采用了Free-XOR技術[72]，每對元素間相等性判斷只需要實現(xiàn)σ-1個非異或門電路.SCS協(xié)議的主要過程為：客戶端和服務器端分別在本地對各自集合中元素進行排序，并通過混亂電路進行按序合并；對合并后集合中相鄰元素進行相等性判斷，如果相等則為交集中元素；最后將計算結果亂序(分別采用了3種方法實現(xiàn)亂序：不經(jīng)意排序網(wǎng)絡、同態(tài)加密、Waksman 網(wǎng)絡，亂序目的是防止泄露集合元素位置信息)輸出給客戶端.該協(xié)議通過使用不經(jīng)意擴展傳輸協(xié)議及其他各種電路優(yōu)化技術，僅需要O(σnlogn)非異或門電路操作，大大加快了協(xié)議的計算速度.這些實現(xiàn)方案均假設參與方集合沒有重復元素，在半誠實敵手模型下是可證明安全的.

2014年Pinkas等人對Huang提出的PWC，SCS協(xié)議進行優(yōu)化[73]，主要是采用目前最快的隨機OT協(xié)議對混亂電路進行優(yōu)化.由于混亂電路以OT子協(xié)議為基礎完成安全計算，因此OT協(xié)議的改進很大程度減少協(xié)議的計算和通信代價.此外Pinkas等人也利用GMW混亂電路進行PSI協(xié)議計算，該協(xié)議同樣采用隨機OT協(xié)議加快PSI的計算.除了從OT協(xié)議的角度對姚氏混亂電路和GMW混亂電路進行優(yōu)化外，在PWC協(xié)議中作者采用Hash函數(shù)將集合元素進行映射來減少兩兩元素相等判斷比較次數(shù)，很大程度減少協(xié)議計算復雜度.

2016年Pinkas等人通過電路實現(xiàn)了基于不經(jīng)意偽隨機函數(shù)的PSI[74]，該協(xié)議的關鍵在于如何高效地實例化OPRF，作者采用文獻[38]中AES實例化OPRF，并分別用姚氏混亂電路和GMW混亂電路計算AES函數(shù)完成PSI計算.

表4對以上基于混亂電路的協(xié)議進行漸進復雜度分析，分析結果如下：

Table 4 Comparison of Private Set Intersection Protocols表4 集合交集協(xié)議性能比較

Note：n: the size of sets;κ: the symmetric security parameter.

Fig. 1 The private set intersection protocol based on Bloom filter.圖1 基于布隆過濾器的隱私集合交集協(xié)議

BWA協(xié)議計算代價與σ成指數(shù)關系，適用于較小的σ值.結合文獻[73-74]中實驗結果對以上PWC，SCS協(xié)議進行分析，由于PWC協(xié)議采用Hash函數(shù)減少比較次數(shù)，無論采用姚氏混亂電路還是GMW混亂電路在計算和通信復雜度上都優(yōu)于SCS協(xié)議.

盡管混亂電路的PSI協(xié)議一般具有通用性、靈活性和可擴展性，但功能函數(shù)的電路設計一般要求很大的門電路個數(shù)和電路深度，因此基于此技術的協(xié)議一般計算效率很低，人們更偏向于使用特殊的高效協(xié)議.

2.3基于不經(jīng)意傳輸協(xié)議

基于不經(jīng)意傳輸?shù)腜SI協(xié)議主要是通過OT協(xié)議進行向量或元素相等性判斷來完成集合交集計算.隨著近年來OT協(xié)議的快速發(fā)展，基于OT協(xié)議的應用協(xié)議也得到了快速發(fā)展.特別是基于OT協(xié)議的PSI計算可以快速完成上億元素規(guī)模的交集計算，逐漸可適用于大數(shù)據(jù)下的應用場景.

2013年Dong等人提出了第1個可處理集合元素達到億級別大小的PSI協(xié)議[75]，該協(xié)議基于布隆過濾器(Bloom filter, BF)[76]、秘密共享和擴展不經(jīng)意傳輸協(xié)議，主要依賴于高效的對稱加密操作.布隆過濾器主要用來判斷一個元素是否在集合中，通過引入一定的假陽率來節(jié)省大量的存儲空間.由于2個集合的布隆過濾器結構直接進行與運算BFc∩BFs的結果和集合交集表示成布隆過濾器BFc∩s的結果不一致，通過邏輯與運算求集合交集會泄露集合中的信息，因此作者采用OT協(xié)議來保證安全性.該協(xié)議的過程為：客戶端將集合n個元素表示為布隆過濾器結構(布隆過濾器本質為長度為m的位向量，每個集合元素用k個不同的Hash函數(shù){h1,h2,…,hk}映射到位向量)；服務器端將集合元素表示為GBF(garbled Bloom filter)結構，GBF與BF本質相同，區(qū)別在于索引位置存儲的是元素基于異或操作的秘密共享份額ri，即x=r1⊕r2⊕…⊕rk，x為長度為σ位的集合元素；雙方執(zhí)行m次OT協(xié)議，客戶端的BF結構作為選擇向量，服務器端的GBF結構為輸入數(shù)據(jù)，由于2方采用相同的Hash函數(shù)映射，相同的元素映射到BF和GBF上的索引位置一定相同，因此經(jīng)過OT協(xié)議，客戶端能得到交集中元素的秘密共享份額，進一步通過查詢算法可獲得集合交集中元素.該協(xié)議示意過程如圖1所示:

2016年Rindal等人對文獻[75]中協(xié)議的惡意模型進行修正，針對惡意的客戶端，采用cut and choose技術來保證協(xié)議的安全并同樣采用隨機OT減少服務器端通信復雜度[77].

2014年Pinkas等人在文獻[73]中除了對混亂電路協(xié)議優(yōu)化外，也對Dong提出的協(xié)議[75]進行優(yōu)化,使用隨機OT協(xié)議代替擴展OT協(xié)議,服務器端不需要保存GBF結構，節(jié)省了大量空間.具體而言，客戶端和服務器端分別生成各自集合的布隆過濾器BFc,BFs，并作為m次隨機OT的輸入，輸出分別為Gc,Gs，在每一次二選一OT計算中，如果BFc[i]=BFs[i]=1,那么Gc[i]=Gs[i]=randomstring∈{0,1}；對于?xi∈X,yj∈Y，客戶端計算maskc[i]=服務器端計算masks[j]=并發(fā)送給客戶端；客戶端檢查是否存在j滿足masks[j]=maskc[i]來判斷元素xi是否在交集中.由于隨機OT比OT擴展協(xié)議有更低的計算和通信復雜度，優(yōu)化后的協(xié)議效率提升達到55%～60%.

基于Hash和隨機OT協(xié)議的PSI協(xié)議的計算和通信復雜度和元素的位長度σ成正比，為了進一步減少計算和通信開銷，2015年Pinkas等人基于置換Hash的思想，又提出了效率更高的PSI協(xié)議[78].該協(xié)議采用置換Hash[79]算法，主要思想是將元素x表示為左右2部分x=xL|xR,|xL|=logβ，左半部分主要用來表示元素索引位置p(x)=xL⊕f(xR)，其中f為隨機函數(shù):[1…2|xR|]→[1…2|xL|]，右半部分為Hash桶中實際存儲的元素部分.Hash桶中只需要存儲σ-logβ比特的元素，因此改進的PSI協(xié)議可以將一次元素相等性判別過程中隨機OT子協(xié)議的執(zhí)行次數(shù)從σ減少為σ-logβ，這進一步降低了協(xié)議的計算和通信復雜度.

基于不經(jīng)意傳輸?shù)腜SI協(xié)議其效率主要依賴于OT子協(xié)議的效率，通過采用N選一OT協(xié)議，可進一步減少OT協(xié)議執(zhí)行的次數(shù).在Kolesnikov等人提出的N選一OT協(xié)議中[33],采用Walsh-Hadamard(WH)錯誤糾正碼對選擇向量進行編碼，使得對長度為σ位的元素進行相等性判斷時可以將隨機OT協(xié)議執(zhí)行次數(shù)從σ次減少為t次，其中t=σ/logN，但該協(xié)議只適用于較小的N，如N=256. 2016年Kolesnikov等人又提出一種新的協(xié)議[80],該協(xié)議對選擇向量采用偽隨機編碼的方式，使元素相等性判斷執(zhí)行的OT協(xié)議的次數(shù)不依賴于σ，即通過一次OT協(xié)議就可以判斷2個元素是否相等.作者采用固定秘鑰的AES實例化偽隨機函數(shù).在σ取值為64或128時，改進的PSI協(xié)議比文獻[78]中的協(xié)議快2.3～3.6 倍.

同樣，為了使PSI協(xié)議的效率只與元素個數(shù)成正比而不依賴于元素的位長度σ，2016年Pinkas等人采用新的錯誤糾正碼實現(xiàn)OT協(xié)議，并在此基礎上改進PSI[74].因為以上PSI協(xié)議采用的都是基于隨機預言模型和半誠實模型下的OT擴展協(xié)議，因此PSI協(xié)議一般適用于隨機預言模型和半誠實模型.表5為基于OT的PSI協(xié)議漸進復雜度分析：

Table 5 Comparison of Private Set Intersection Protocols表5 隱私集合交集協(xié)議性能比較

Note：n: the size of sets;κ: the symmetric security parameter;

k: the number of the Hash functions.

此外作者通過實驗對比了半誠實模型下的不安全Hash的PSI和基于RSA公鑰加密算法、混亂電路和OT協(xié)議的PSI.表6為文獻[74]中部分實驗結果，該實驗中用到的2臺設備為Intel Haswell i7-4770K，3.5 GHz CPU 16 GB內存，通過OpenSSL(v.1.0.1e)密碼學庫實現(xiàn)論文中的對稱加密操作，Miracl(v.5.6.1)和GMP庫(v.5.1.2)實現(xiàn)OT擴展協(xié)議和公鑰加密操作*https://github.com/encryptogroup/PSI，通過實驗結果我們可以對各類協(xié)議的性能有更直觀的認識.

Table 6 Comparison of Private Set Intersection Protocols [74]表6 集合交集協(xié)議性能比較

Note： Protocols on sets with 220over Gigabit LAN.σis 32 b and the security parameter is 128 b.

Fig. 2 Outsourced private set intersection protocol圖2 外包的隱私集合交集協(xié)議

通過表6可以分析出基于公鑰加密的協(xié)議計算復雜度最高，但是具有較小的通信復雜度，適用于參與方計算能力較強但是通信帶寬為瓶頸的情景；基于電路和GBF的協(xié)議計算復雜度優(yōu)于基于公鑰的協(xié)議，但是通信復雜度最高；基于OT和Hash策略的PSI協(xié)議在計算和通信復雜度上都達到了和不安全Hash一樣的量級，既滿足安全性要求又達到較高的計算效率，適合處理大數(shù)據(jù)量問題.以上分析結果反映出了PSI協(xié)議的效率直接取決于底層基礎協(xié)議的效率.

此外，從2個角度對協(xié)議的適用性進行分析:1)大規(guī)模場景適用性分析.基于混亂電路的協(xié)議需要將電路提前構建并全部加載到內存中，當集合很大時會有內存限制；同樣對于布隆過濾器的協(xié)議也需要加載全部布隆過濾器結構到內存，因此此類協(xié)議不適合處理大數(shù)據(jù)應用問題.2)并行性分析.基于公鑰加密的PSI處理單元為相互獨立的元素因此可以并行化加速計算；基于混亂電路的PWC，OPRF協(xié)議可并行化處理，而SCS協(xié)議中門電路都是相互關聯(lián)的不適合并行化計算；基于OT的PSI協(xié)議由于底層基礎模塊OT擴展協(xié)議的可并行化因此也可以進行并行計算.

3 云輔助的PSI

傳統(tǒng)PSI協(xié)議主要是參與方之間交互完成集合交集計算，然而，有限存儲資源和計算資源的終端設備和移動設備無法應對大規(guī)模數(shù)據(jù)集的PSI計算需求.與此同時，隨著云計算應用的興起，大量的存儲資源和計算資源以一種按需服務的方式向用戶提供，使得大量的應用借助于第三方云計算框架來完成計算.因此研究者提出了新的借助于云服務器的安全函數(shù)計算問題[36].其中，外包的隱私集合交集(OPSI)協(xié)議作為特殊的云輔助的安全函數(shù)計算問題是指存在一個不可信的第三方服務提供商P，參與方采取一系列方式將輸入集合加密盲化處理(如同態(tài)加密、偽隨機函數(shù)、Hash函數(shù)等)后上傳到云端，然后由P在密文上完成集合交集的計算，在協(xié)議執(zhí)行過程中P沒有獲得任何輸入輸出信息，主要是利用云服務器的存儲和計算資源.

相比于傳統(tǒng)的PSI協(xié)議，在設計云輔助的PSI協(xié)議時，一般需要滿足抗合謀性，因為如果服務器和某一參與方進行合謀，將退化為參與方之間計算能力相差懸殊的傳統(tǒng)的安全多方計算協(xié)議[81].外包的隱私集合交集協(xié)議示意圖如圖2所示，其中一部分協(xié)議設計需要可信的第三方生成共享秘鑰信息.

Kerschbaum等人又提出了另一種采用布隆過濾器和同態(tài)加密實現(xiàn)的PSI協(xié)議[83].協(xié)議過程為：客戶端將集合表示成布隆過濾器結構并采用同態(tài)加密技術將布隆過濾器加密后外包給服務器；第三方服務提供商利用加密的布隆過濾器Enc(BFA),Enc(BFB)求集合交集并將集合交集的布隆過濾器結構的密文Enc(BFA∩B)返回給客戶端，客戶端用戶對收到的密文解密并結合本地的集合即可計算集合交集.該協(xié)議在密文上進行計算主要采用SYY技術，SYY技術[84]是一種在密文上進行某種運算對應于明文的邏輯與運算的技術，在該協(xié)議中體現(xiàn)為通過加密布隆過濾器的與運算求明文集合信息，即Enc(BFA)*Enc(BFB)=Enc(BFA∩B),*表示秘文運算.

2014年Liu等人提出了一種相對簡單但是會泄露集合交集基數(shù)的PSI協(xié)議[85]，該協(xié)議過程為：客戶端用戶分別各自生成協(xié)議中采用的對稱和非對稱加密算法秘鑰；客戶端用戶生成隨機數(shù)rI,rI∈，作用在數(shù)據(jù)集的Hash值上并對隨機數(shù)和原始數(shù)據(jù)集進行對稱加密Enc(rI);Enc(SI)，將VI,Enc(rI);Enc(SI)上傳給云服務器；客戶端用戶與服務器端進行交互使服務器獲得CI=VI+rA+rB，通過計算|CA-CB|是否為0判斷元素是否屬于交集.該協(xié)議是半誠實模型下可證明安全的，但是同不安全Hash協(xié)議一樣存在暴力破解的風險.2015年Zheng等人提供了一種可驗證機制PSI[86].

2016年李順東等人利用哥德爾編碼和ElGamal同態(tài)加密算法構造了一種半誠實模型下適用于云計算的集合交集計算方案[89].該方案解決了多個集合間的交集并集問題，但不能解決2個集合間的交集問題.

表7為云輔助PSI協(xié)議的計算和通信漸進復雜度分析.分析結果如下：

Table 7 Comparison of Private Set Intersection Protocols表7 集合交集協(xié)議性能比較

Note：exps denotes modular exponentiations operation; sym: symmetric cryptographic operations; add denotes modular additional operation;m=max(v,w)k: the number of the Hash functions.

通過對以上具體協(xié)議的分析，目前已有的云輔助PSI主要采用公鑰加密和私鑰加密2種類型，在協(xié)議的安全性和高效性上各具有很鮮明的特點，其中Kamara提出的協(xié)議全部采用對稱加密操作，計算復雜度最低，適合大規(guī)模數(shù)據(jù)集計算，但是不能抵抗第三方服務器和參與方的合謀攻擊；其他的采用同態(tài)加密等公鑰加密算法對數(shù)據(jù)集進行加密計算的PSI協(xié)議，計算復雜度較高但是達到了較高的安全性，可抵抗合謀攻擊.此外，傳統(tǒng)的PSI協(xié)議一般可以經(jīng)過簡單調整轉化為云輔助的PSI協(xié)議，在采用相同的底層密碼學技術實現(xiàn)PSI協(xié)議時，2類協(xié)議的復雜度基本不會有很大偏差.

4 PSI應用場景

從參與方的角度考慮，PSI協(xié)議應用場景可以分為2類：1)場景中參與方均是大型企業(yè)或醫(yī)療政府軍事機構等，都擁有大量隱私、有價值和具有核心競爭力的數(shù)據(jù)，雙方通過安全協(xié)作計算在保護自身數(shù)據(jù)隱私性的同時達到信息共享的目的；2)場景中參與方是不對等的關系，其中一方是通過收集用戶的隱私數(shù)據(jù)來提供更好服務的企業(yè)，一方是享受服務的用戶，雙方通過安全協(xié)作計算是為了提供/享受服務的同時保護用戶隱私.因此PSI的研究具有重要意義，一方面促進具有利益沖突的企業(yè)、機構等更好的進行合作；另一方面減輕大數(shù)據(jù)時代隱私泄露問題帶來的危害.對5個典型的應用場景簡要說明:

1) 隱私保護相似文檔檢測.隱私保護相似文檔檢測技術主要應用于如醫(yī)療病歷共享、一稿多投行為審查等.例如會議或者期刊組織方在收到提交稿時，希望在其他會議或期刊檢查一下作者是否存在一稿多投現(xiàn)象.但通常未發(fā)表的提交稿是不能對其他會議或期刊組織者公開的，針對這個問題可以通過隱私保護相似文檔檢測協(xié)議進行計算，首先將雙方的文檔表示成文檔指紋集合，通過PSI協(xié)議求得2篇文檔的指紋集合交集，進而計算集合的Jaccard距離得到2篇文檔的相似度[90].

2) 安全的人類基因檢測.人類基因測序研究及其應用越來越普遍，在很多醫(yī)療行業(yè)有廣泛的應用，比如疾病預測、個人醫(yī)療、親子鑒定等.基因信息的共享和交換有利于加速科學研究發(fā)展，提升人類醫(yī)療保健質量，不少基因組織通過基因工程項目比如Personal Genome Project和HapMap致力于建立龐大的公共基因數(shù)據(jù)庫.然而，基因信息中也包含大量的個人隱私，比如人種信息、顯性體征以及疾病信息等，基因數(shù)據(jù)濫用或者非法散播會造成嚴重的隱私泄露.為了實現(xiàn)在基因數(shù)據(jù)上隱私保護的信息共享，Baldi等人基于PSI-CA，APSI和PSI協(xié)議構建了有效的基因數(shù)據(jù)隱私保護計算算法，并應用在親子鑒定、個人醫(yī)療和基因兼容測試等場景上[22].

3) 在線廣告轉化率評估.在線廣告作為企業(yè)營銷策略的重要組成部分，蘊藏著巨大的商機.傳統(tǒng)的評估廣告影響力指標是廣告點擊率，但是隨著人們對廣告了解的深入，點擊人數(shù)越來越少，點擊率不能真正反映廣告的效果.針對這個問題提出了廣告轉化率這個指標，指受網(wǎng)絡廣告影響而發(fā)生購買、注冊或信息需求行為的瀏覽者占總廣告點擊人數(shù)的比例，用來反映網(wǎng)絡廣告對產(chǎn)品銷售情況影響程度.然而廣告瀏覽數(shù)據(jù)、交易完成數(shù)據(jù)分別掌握在廣告商如谷歌、Facebook手中和商家手中，這些數(shù)據(jù)都包含有顧客的隱私信息，不能在明文信息進行交集計算，因此，可以通過信用卡號、email地址等身份表示信息進行PSI計算，在保護顧客隱私的同時實現(xiàn)對在線廣告轉化率的評估.

4) 私有聯(lián)系人發(fā)現(xiàn).很多手機社交類的APP要求訪問新注冊用戶的手機通信錄，通過對比通信錄和APP服務器的注冊用戶，給新用戶推薦共同使用該APP的好友.但是允許APP訪問用戶的手機通信錄會將用戶所有的聯(lián)系人信息暴露給APP服務商，存在很大的隱私泄露問題.通過在APP手機端和APP服務器端運行PSI協(xié)議，計算手機通信錄和服務器已注冊用戶集之間的交集，可以在不泄露用戶隱私信息的條件下進行聯(lián)系人及好友推薦[91].

5) 隱私保護的近鄰檢測.近鄰檢測是社交網(wǎng)絡中基于位置服務的一種重要應用，但位置服務在給人們帶來方便的同時也面臨著嚴重的位置隱私泄露問題.隱私保護的近鄰檢測可以通過同態(tài)加密等技術實現(xiàn)對精準位置數(shù)據(jù)的密文計算，也可以通過WiFi、藍牙、GPS等信號給位置打上的標簽信息進行隱私集合交集計算，完成對近鄰關系的評估[23].

5 總 結

隨著信息化和網(wǎng)絡化的不斷發(fā)展，隱私保護成為一個越來越重要的課題，不僅關系到公民個人利益更關乎到國家的安全.安全多方計算作為隱私保護的一個重要密碼學研究方法，也由最初的采用通用協(xié)議解決安全函數(shù)計算問題發(fā)展到設計特殊的針對具體問題的高效協(xié)議.PSI作為安全多方計算的一個重要應用問題，近年來也得到快速發(fā)展.目前，為了適應大數(shù)據(jù)時代的計算需求，PSI協(xié)議的發(fā)展歷程主要由最初的基于公鑰加密機制到基于混亂電路、不經(jīng)意傳輸協(xié)議，以及新的計算模式——云計算環(huán)境下的協(xié)議設計.無論是傳統(tǒng)的方法還是云輔助的PSI協(xié)議，對該問題的主要研究趨勢是均衡安全性和高效性、可擴展性，研究思路主要是由最初的基于公鑰加密機制到依賴更多的對稱加密操作.

雖然對PSI協(xié)議的研究取得了一定的進展，但是現(xiàn)有協(xié)議普遍存在一些問題：1)在惡意模型下，為了驗證輸入數(shù)據(jù)的一致性等導致計算通信代價高，不具有實用性；2)大多數(shù)傳統(tǒng)的高效的PSI協(xié)議主要依賴于備受爭議的隨機預言模型，隨機預言模型的安全性證明并不能保證實際方案的安全性.

結合當前PSI問題的研究進展，未來對PSI協(xié)議研究的重點包括：1)新的不可信計算模式云計算環(huán)境下的PSI安全協(xié)議研究，隨著更多公司和個人對云計算的使用，基于云計算服務的PSI協(xié)議將成為熱點研究問題；2)在當前大數(shù)據(jù)背景下，已有的PSI協(xié)議盡管已經(jīng)取得了很大的突破但仍有性能上的瓶頸，未來需要設計出更高效的協(xié)議來滿足大數(shù)據(jù)隱私保護需求.

[1] Fang Binxing, Jia Yan, Li Aiping, et al. Privacy preservation in big data: A survey[J]. Big Data Research, 2017, 2(1): 1-18 (in Chinese)

(方濱興, 賈焰, 李愛平, 等. 大數(shù)據(jù)隱私保護技術綜述[J]. 大數(shù)據(jù), 2017, 2(1): 1-18)

[2] Du Wenliang, Atallah M. Secure multi-party computation problems and their applications: A review and open problems[C] //Proc of the 2001 Workshop on New Security Paradigms. New York:ACM, 2001: 13-22

[3] Mu Bin. A survey on secure processing of similarity queries[OL]. (2014-05-01) [2017-09-06]. https://pdfs.semantics cholar.org/d602/831fc377fd9b84366c3e8a5ab736c9c3a5ef.pdf

[4] Erkin Z, Franz M, Guajardo J, et al. Privacy-preserving face recognition[G] //LNCS 5672: Proc of Int Symp on Privacy Enhancing Technologies. Berlin: Springer, 2009: 235-253

[5] Jagannathan G, Wright R N. Privacy-preserving distributedk-means clustering over arbitrarily partitioned data[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery in Data Mining. New York: ACM, 2005: 593-599

[6] Bringer J, Chabanne H, Favre M, et al. GSHADE: Faster privacy-preserving distance computation and biometric identification[C] //Proc of the 2nd ACM Workshop on Information Hiding and Multimedia Security. New York: ACM, 2014: 187-198

[7] Yao A C-C. Protocols for secure computations[C] //Proc of the 23rd Annual Symp on Foundations of Computer Science (SFCS’82). Piscataway, NJ: IEEE, 1982: 160-164

[8] Goldreich O, Micali S, Wigderson A. How to play any mental game, or a completeness theorem for protocols with an honest majority[C] //Proc of the 19th Annual ACM STOC. New York: ACM, 1987: 218-229

[9] Goldreich O. Secure multi-party computation[J]. 1998 (2002-10-27) [2017-09-06]. http://www.wisdom.weizmann.ac.il/～oded/PSX/prot.pdf

[10] Goldwasser S. Multi party computations: Past and present[C] //Proc of the 16th Annual ACM Symp on Principles of Distributed Computing. New York: ACM, 1997: 1-6

[11] Kissner L, Song D. Privacy-preserving set operations[G] //LNCS 3621: Proc of Annual Int Cryptology Conf. Berlin: Springer, 2005: 241-257

[12] Sang Yingpeng, Shen Hong. Efficient and secure protocols for privacy-preserving set operations[J]. ACM Trans on Information and System Security, 2009, 13(1): 1-35

[13] Lindell Y, Pinkas B. Secure multiparty computation for privacy-preserving data mining[J]. Journal of Privacy and Confidentiality, 2009, 1(1): 59-98

[14] Agrawal R, Srikant R. Privacy-preserving data mining[C] //Proc of the 2000 ACM SIGMOD Int Conf on Management of Data Record. New York: ACM, 2000: 439-450

[15] Aggarwal C C, Philip S Y. A General Survey of Privacy-Preserving Data Mining Models and Algorithms[M]. Berlin: Springer, 2008: 11-52

[16] Pinkas B. Cryptographic techniques for privacy-preserving data mining[J]. ACM SIGKDD Explorations Newsletter, 2002, 4(2): 12-19

[17] Cao Ning, Wang Cong, Li Ming, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(1): 222-233

[18] Wang Cong, Cao Ning, Li Jin, et al. Secure ranked keyword search over encrypted cloud data[C] //Proc of the 30th Int Conf on Distributed Computing Systems (ICDCS). Piscataway, NJ: IEEE, 2010: 253-262

[19] Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C] //Proc of the 2000 IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2000: 44-55

[20] Atallah M, Du Wenliang. Secure multi-party computational geometry[G] //LNCS 2125: Proc of Workshop on Algorithms and Data Structures (WADS 2001). Berlin: Springer, 2001: 165-179

[21] Vaidya J, Clifton C. Privacy preserving association rule mining in vertically partitioned data[C] //Proc of the 8th ACM SIGKDD Int Conf on Knowledge Discovery and Ddata Mining. New York: ACM, 2002: 639-644

[22] Baldi P, Baronio R, De Cristofaro E, et al. Countering gattaca: Efficient and secure testing of fully-sequenced human genomes[C] //Proc of the 18th ACM Conf on Computer and Communications Security. New York: ACM, 2011: 691-702

[23] Narayanan A, Thiagarajan N, Lakhani M, et al. Location privacy via private proximity testing[C] //Proc of the Network and Distributed System Security Symp. Reston, VA: ISOC, 2011

[24] Mezzour G, Perrig A, Gligor V, et al. Privacy-preserving relationship path discovery in social networks[G] //LNCS 5888: Proc of Int Conf on Cryptology and Network Security. Berlin: Springer, 2009: 189-208

[25] Freedman M J, Nissim K, Pinkas B. Efficient private matching and set intersection[G] //LNCS 3027: Proc of Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2004: 1-19

[26] Kamara S, Mohassel P, Raykova M, et al. Scaling private set intersection to billion-element sets[G] //LNCS 8437: Proc of Int Conf on Financial Cryptography and Data Security. Berlin: Springer, 2014: 195-215

[27] Goldreich O. Foundations of Cryptography Ⅱ Basic Applications[M]. Cambridge, UK: Cambridge University Press, 2004

[28] Katz J, Lindell Y. Introduction to Modern Cryptography[M]. New York: CRC Press, 2014

[29] Even S, Goldreich O, Lempel A. A randomized protocol for signing contracts[J]. Communications of the ACM, 1985, 28(6): 637-647

[30] Impagliazzo R, Rudich S. Limits on the provable consequences of one-way permutations[C] //Proc of the 21st Annual ACM Symp on Theory of Computing. New York: ACM, 1989: 44-61

[31] Beaver D. Correlated pseudorandomness and the complexity of private computations[C] //Proc of the 28th Annual ACM Symp on Theory of Computing. New York: ACM, 1996: 479-488

[32] Ishai Y, Kilian J, Nissim K, et al. Extending oblivious transfers efficiently[G] //LNCS 2729: Annual Int Cryptology Conf. Berlin: Springer, 2003: 145-161

[33] Kolesnikov V, Kumaresan R. Improved OT extension for transferring short secrets[G] //LNCS 8043: Advances in Cryptology (CRYPTO 2013). Berlin: Springer, 2013: 54-70

[34] Asharov G, Lindell Y, Schneider T, et al. More efficient oblivious transfer and extensions for faster secure computation[C] //Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 535-548

[35] Yao A C C. How to generate and exchange secrets[C] //Proc of the 27th Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE,1986: 162-167

[36] Kamara S, Mohassel P, Riva B. Salus: A system for server-aided secure function evaluation[C] //Proc of the 2012 ACM Conf on Computer and Communications Security. New York: ACM, 2012: 797-808

[37] Jiang Han, Xu Qiuliang. Advances in key techniques of practical secure multi-party computation[J]. Journal of Computer Research and Development, 2015, 52(10): 2247-2257 (in Chinese)

(蔣瀚, 徐秋亮. 實用安全多方計算協(xié)議關鍵技術研究進展[J]. 計算機研究與發(fā)展, 2015, 52(10): 2247-2257)

[38] Pinkas B, Schneider T, Smart N P, et al. Secure two-party computation is practical[G] //LNCS 5912: Proc of Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2009: 250-267

[39] Naor M, Pinkas B, Sumner R. Privacy preserving auctions and mechanism design[C] //Proc of the 1st ACM Conf on Electronic Commerce. New York: ACM, 1999: 129-139

[40] Zahur S, Rosulek M, Evans D. Two halves make a whole[G] //LNCS 9057: Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015). Berlin: Springer, 2015: 220-250

[41] Pinkas B. Fair secure two-party computation[G] //LNCS 2656: Proc of Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2003: 87-105

[42] Malkhi D, Nisan N, Pinkas B, et al. Fairplay-secure two-party computation system[C] //Proc of the 13th Conf on USENIX Security Symp. Berkeley, CA: USENIX Association, 2004

[43] Huang Yan, Evans D, Katz J, et al. Faster secure two-party computation using garbled circuits[C] //Proc of the 20th Conf on USENIX Security Symp. Berkeley, CA: USENIX Association, 2011

[44] Liu Chang, Wang Xiao, Nayak K, et al. Oblivm: A programming framework for secure computation[C] //Proc of 2015 IEEE Symp on Security and Privacy (SP). Piscataway, NJ: IEEE, 2015: 359-376

[45] Burkhart M, Strasser M, Many D, et al. SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics[C] //Proc of the 19th Conf on USENIX Security. Berkeley, CA: USENIX Association, 2010

[46] Damg?rd I, Geisler M, Kr?igaard M, et al. Asynchronous multiparty computation: Theory and implementation[G] //LNCS 5443: Proc of Int Workshop on Public Key Cryptography. Berlin: Springer, 2009: 160-179

[47] Bogdanov D, Laur S, Willemson J. Sharemind: A framework for fast privacy-preserving computations[G] //LNCS 5283: European Symp on Research in Computer Security. Berlin: Springer, 2008: 192-206

[48] Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612-613

[49] Blakley G R. Safeguarding cryptographic keys[C] //Proc of American Federation of Information Processing Socicties National Computer Conf. Wuhan: SCIRP, 1979: 313-317

[50] Naor M, Pinkas B. Oblivious transfer and polynomial evaluation[C] //Proc of the 21st Annual ACM Symp on Theory of Computing. New York: ACM, 1999: 245-254

[51] Paillier P. Public-key cryptosystems based on composite degree residuosity classes[G] //LNCS 1592: Proc of Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 1999: 223-238

[52] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans on Information Theory, 1985, 31(4): 469-472

[53] Azar Y, Broder A Z, Karlin A R, et al. Balanced allocations[J]. SIAM Journal on Computing, 1999, 29(1): 180-200

[54] Freedman M J, Hazay C, Nissim K, et al. Efficient set intersection with simulation-based security[J]. Journal of Cryptology, 2016, 29(1): 115-155

[55] Pagh R, Rodler F F. Cuckoo hashing[C] //Proc of European Symp on Algorithms. Berlin: Springer, 2001: 121-133

[56] Dachman-Soled D, Malkin T, Raykova M, et al. Efficient robust private set intersection[G] //LNCS 5536: Proc of Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2009: 125-142

[57] Zhou Sufang, Li Shundong, Guo Yimin, et al. Efficient set intersection problem computation[OL].[2017-06-01]. http://kns.cnki.net/KCMS/detail/11.1826.TP.20170526.1938.014.html (in Chinese)

(周素芳, 李順東, 郭奕旻, 等. 保密集合相交問題的高效計算[OL]. [2017-06-01]. http://kns.cnki.net/KCMS/detail/11.1826.TP.20170526.1938.014.html)

[58] Chen Zhenhua, Li Shundong, Huang Qiong, et al. Protocols for secure computation of two set-relationships with the unencrypted method[OL]. [2017-06-01]. http://kns.cnki.net/KCMS/detail/11.2560.TP.20170331.2154.001.html (in Chinese)

(陳振華, 李順東, 黃瓊, 等. 非加密方法安全計算兩種集合關系[OL]. [2017-06-01]. http://kns.cnki.net/KCMS/detail/11.2560.TP.20170331.2154.001.html)

[59] Hazay C, Nissim K. Efficient set operations in the presence of malicious adversaries[G] //LNCS 6056: Proc of Int Workshop on Public Key Cryptography. Berlin: Springer, 2010: 312-331

[60] Naor M, Reingold O. Number-theoretic constructions of efficient pseudo-random functions[J]. Journal of the ACM, 2004, 51(2): 231-262

[61] Hazay C, Lindell Y. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries[G] //LNCS 4948: Theory of Cryptography Conf. Berlin: Springer, 2008: 155-175

[62] Jarecki S, Liu Xiaomin. Efficient oblivious pseudorandom function with applications to adaptive ot and secure computation of set intersection[G] //LNCS 5444: Proc of Theory of Cryptography Conf (TCC 2009). Berlin: Springer, 2009: 577-594

[63] Dodis Y, Yampolskiy A. A verifiable random function with short proofs and keys[G] //LNCS 3386: Proc of Int Workshop on Public Key Cryptography. Berlin: Springer, 2005: 416-431

[64] Camenisch J, Shoup V. Practical verifiable encryption and decryption of discrete logarithms[G] //LNCS 2729: Proc of Annual Int Cryptology Conf (CRYPTO 2003). Berlin: Springer, 2003: 126-144

[65] Jarecki S, Liu Xiaomin. Fast secure computation of set intersection[G] //LNCS 6280: Proc of Int Conf on Security and Cryptography for Networks. Berlin: Springer, 2010: 418-435

[66] Bellare M, Namprempre C, Pointcheval D, et al. The one-more-RSA-inversion problems and the security of Chaum’s blind signature scheme[J]. Journal of Cryptology, 2003, 16(3): 185-215

[67] De Cristofaro E, Tsudik G. Practical private set intersection protocols with linear complexity[G] //LNCS 6052: Proc of Int Conf on Financial Cryptography and Data Security. Berlin: Springer, 2010: 143-159

[68] De Cristofaro E, Kim J, Tsudik G. Linear-complexity private set intersection protocols secure in malicious model[G] //LNCS 6477: Proc of Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2010: 213-231

[69] De Cristofaro E, Tsudik G. Experimenting with fast private set intersection[G] //LNCS 7344: Proc of Int Conf on Trust and Trustworthy Computing. Berlin: Springer, 2012: 55-73

[70] Ateniese G, De Cristofaro E, Tsudik G. (If) size matters: Size-hiding private set intersection[G] //LNCS 6571: Proc of Int Workshop on Public Key Cryptography. Berlin: Springer, 2011: 156-173

[71] Huang Y, Evans D, Katz J. Private set intersection: Are garbled circuits better than custom protocols?[C] //Proc of the Network and Distributed System Security Symp. Reston, VA: ISOC, 2012

[72] Kolesnikov V, Schneider T. Improved garbled circuit: Free XOR gates and applications[G] //LNCS 5126: Proc of Int Colloquium on Automata, Languages, and Programming. Berlin: Springer, 2008: 486-498

[73] Pinkas B, Schneider T, Zohner M. Faster private set intersection based on OT extension[C] //Proc of the 23rd USENIX Security Symp. Berkeley, CA: USENIX Association, 2014: 797-812

[74] Pinkas B, Schneider T, Zohner M. Scalable private set intersection based on OT extension[OL]. [2017-06-01]. https://eprint.iacr.org/2016/930.pdf

[75] Dong Changyu, Chen Liqun, Wen Zikai. When private set intersection meets big data: An efficient and scalable protocol[C] //Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 789-800

[76] Bloom B H. Space/time trade-offs in Hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422-426

[77] Rindal P, Rosulek M. Improved private set intersection against malicious adversaries[G] //LNCS 10210: Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2017: 235-259

[78] Pinkas B, Schneider T, Segev G, et al. Phasing: Private set intersection using permutation-based hashing[C] //Proc of the 24th USENIX Security Symp. Berkeley, CA: USENIX Association, 2015: 515-530

[79] Arbitman Y, Naor M, Segev G. Backyard cuckoo hashing: Constant worst-case operations with a succinct representation[C] //Proc of the 51st Annual IEEE Symp on Foundations of Computer Science (FOCS). Piscataway, NJ: IEEE, 2010: 787-796

[80] Kolesnikov V, Kumaresan R, Rosulek M, et al. Efficient batched oblivious PRF with applications to private set intersection[C] //Proc of the 2016 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 818-829

[81] Jiang Han, Xu Qiuliang. Secure Multi-party computation in cloud computing[J].Journal of Computer Research and Development, 2016, 53(10): 2152-2162 (in Chinese)

(蔣瀚, 徐秋亮. 基于云計算服務的安全多方計算[J]. 計算機研究與發(fā)展, 2016, 53(10): 2152-2162)

[82] Kerschbaum F. Collusion-resistant outsourcing of private set intersection[C] //Proc of the 27th Annual ACM Symp on Applied Computing. New York: ACM, 2012: 1451-1456

[83] Kerschbaum F. Outsourced private set intersection using homomorphic encryption[C] //Proc of the 7th ACM Symp on Information, Computer and Communications Security. New York: ACM, 2012: 85-86

[84] Sander T, Young A, Yung M. Non-interactive crypto-computing for NC/sup 1[C] //Proc of the 40th Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1999: 554-566

[85] Liu Fang, Ng W K, Zhang Wei, et al. Encrypted set intersection protocol for outsourced datasets[C] //Proc of 2014 IEEE Int Conf on Cloud Engineering (IC2E). Piscataway, NJ: IEEE, 2014: 135-140

[86] Zheng Qingji, Xu Shouhuai. Verifiable delegated set intersection operations on outsourced encrypted data[C] //Proc of 2015 IEEE Int Conf on Cloud Engineering (IC2E). Piscataway, NJ: IEEE, 2015: 175-184

[87] Abadi A, Terzis S, Dong Changyu. O-PSI: Delegated private set intersection on outsourced datasets[C] //Proc of IFIP Int Information Security Conf. Berlin: Springer, 2015: 3-17

[88] Abadi A, Terzis S, Dong Changyu. VD-PSI: Verifiable delegated private set intersection on outsourced private datasets[G] //LNCS 9603: Proc of Int Conf on Financial Cryptography and Data Security. Berlin: Springer, 2016: 149-168

[89] Li Shundong, Zhou Sufang, Guo Yimin, et al. Secure set computing in cloud environment[J].Journal of Software, 2016, 27(6): 1549-1565 (in Chinese)

(李順東, 周素芳, 郭奕旻, 等. 云環(huán)境下集合隱私計算[J]. 軟件學報, 2016, 27(6): 1549-1565)

[90] Blundo C, De Cristofaro E, Gasti P. EsPRESSO: Efficient privacy-preserving evaluation of sample set similarity[J]. Journal of Computer Security, 2014, 22(3): 355-381

[91] Huang Yan, Chapman P, Evans D. Privacy-preserving applications on smartphones[C] //Proc of the 6th USENIX Conf on Hot Topic in Security. Berkeley, CA: USENIX Association, 2011

SurveyonPrivatePreservingSetIntersectionTechnology

Shen Liyan1,2, Chen Xiaojun2, Shi Jinqiao2, and Hu Lanlan2

1(SchoolofCyberSecurity,UniversityofChineseAcademyofSciences,Beijing100049)2(InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093)

The private set intersection (PSI) is a specific application problem that belongs to the field of secure multi-party computation. It not only has important theoretical significance but also has many application scenarios. In the era of big data, the research on this problem is in accord with people’s increasing privacy preserving demands at the same time to enjoy a variety of services. This paper briefly introduces the basic theory of secure multi-party computation, and highlights the two categories of current mainstream research methods of PSI under the framework of secure multi-party computation: the traditional PSI protocols based on the public key encryption mechanism, garbled circuit, oblivious transfer and the outsourced PSI protocols based on the untrusted third party service provider. Besides, we have briefly summarized the characteristic, applicability and complexity of those protocols. At the same time, the application scenarios of privacy preserving set intersection problem are also explained in detail, which further reflects the practical research value of the problem. With the deep research on the PSI problem, researchers have designed a set of private protocols that can quickly complete set intersection of millions of elements in the semi-honest model.

private set intersection (PSI); secure multi-party computation; oblivious transfer; garbled circuit; oblivious pseudorandom function evaluation; oblivious polynomial evaluation; cloud computing

TP309

ShenLiyan, born in 1992. PhD candidate. Her main research interests include privacy preserving, information security.

ChenXiaojun, born in 1979. PhD. Member of CCF. His main research interests include big data, privacy preserving, data security.

ShiJinqiao, born in 1978. PhD, associate professor. Member of CCF. His main research interests include network anonymous communication and network threats detection.

HuLanlan, born in 1979. PhD, research assistant. Her main research interests include big data, privacy preserving and information security.