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

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

1(中國科學院大學網絡空間安全學院 北京 100049) 2(中國科學院信息工程研究所 北京 100093) (shenliyan@iie．ac．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(中國科學院大學網絡空間安全學院 北京 100049)2(中國科學院信息工程研究所 北京 100093) (shenliyan@iie．ac．cn)

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

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

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

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

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

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

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

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

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

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

1 基礎原語

1.1安全性證明方法

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

1.2安全模型

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

1.3敵手模型

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

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

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

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

1.4基礎協議

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

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

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

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

1.5符號說明

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

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

2 傳統的PSI計算技術

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

2.1基于公鑰加密體制

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

2.1.1 基于不經意多項式計算的PSI

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

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

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

2.1.2 基于不經意偽隨機函數的PSI

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

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

2.1.3 基于盲簽名的PSI

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

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

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

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

Note： exps denotes modular exponentiations operation.

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

2.2基于混亂電路

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

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

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

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

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

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

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

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

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

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

2.3基于不經意傳輸協議

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

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

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

2014年Pinkas等人在文獻[73]中除了對混亂電路協議優化外，也對Dong提出的協議[75]進行優化,使用隨機OT協議代替擴展OT協議,服務器端不需要保存GBF結構，節省了大量空間.具體而言，客戶端和服務器端分別生成各自集合的布隆過濾器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]=并發送給客戶端；客戶端檢查是否存在j滿足masks[j]=maskc[i]來判斷元素xi是否在交集中.由于隨機OT比OT擴展協議有更低的計算和通信復雜度，優化后的協議效率提升達到55%～60%.

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

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

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

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

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

k: the number of the Hash functions.

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

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

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 外包的隱私集合交集協議

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

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

3 云輔助的PSI

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

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

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

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

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

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

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

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.

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

4 PSI應用場景

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

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

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

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

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

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

5 總 結

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

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

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

[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)

(方濱興, 賈焰, 李愛平, 等. 大數據隱私保護技術綜述[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)

(蔣瀚, 徐秋亮. 實用安全多方計算協議關鍵技術研究進展[J]. 計算機研究與發展, 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]. 計算機研究與發展, 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)

(李順東, 周素芳, 郭奕旻, 等. 云環境下集合隱私計算[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.