廖鵬程，陳小軍，申立艷,3, 時金橋

(1. 吉林大學(xué)，長春130000；2. 中國科學(xué)院信息工程研究所，北京100093；3.中國科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，北京 100049)

0 引言

隨著物聯(lián)網(wǎng)技術(shù)、云計算技術(shù)的快速發(fā)展，信息系統(tǒng)中每時每刻都會產(chǎn)生大量的數(shù)據(jù)。據(jù)統(tǒng)計，在2013年時社交網(wǎng)站Twitter每天活躍用戶達(dá)到2億人次，每天發(fā)送信息超過4 億條，在2017年，F(xiàn)acebook自己披露每日活躍用戶達(dá)到13 億。

這是一個數(shù)據(jù)爆發(fā)的時代，每天都有大量數(shù)據(jù)產(chǎn)生，那么大數(shù)據(jù)下的隱私保護(hù)問題已經(jīng)成為學(xué)術(shù)界和工業(yè)界的關(guān)注焦點(diǎn)。

隱私集合交集(Private Set Intersection，PSI)是安全多方計算的一個重要協(xié)議，它允許參與計算的各方只能獲得交集元素的信息?，F(xiàn)在大部分PSI為參與方為兩方的協(xié)議，以實現(xiàn)的方法不同來分類?；诠€密碼體制的PSI，根據(jù)協(xié)議的設(shè)計思想不同可以分為：基于不經(jīng)意多項式計算PSI[1]，本方案將元素表示為方程的根，然后通過同態(tài)加密方案來保證數(shù)據(jù)的安全性；基于不經(jīng)意偽隨機(jī)函數(shù)PSI[2]，本方案客戶端和服務(wù)端通過不經(jīng)意偽隨機(jī)函數(shù)將客戶端隱私集合加密，然后在密文上做交集，保證隱私數(shù)據(jù)的安全性?；诿ず灻腜SI[3]，本方案客戶端將數(shù)據(jù)進(jìn)行盲化操作，然后服務(wù)器在盲化操作的數(shù)據(jù)上簽名和本地數(shù)據(jù)簽名之后發(fā)送給客戶端，客戶端執(zhí)行去盲化操作，就可以在元素的簽名上做交集運(yùn)算?；诨靵y電路的PSI[4]，本方案通過設(shè)計混亂電路來實現(xiàn)所需要的交集功能，基于OT協(xié)議的PSI[5]，本方案通過執(zhí)行隨機(jī)OT協(xié)議將元素變?yōu)橐粋€隨機(jī)值，在隨機(jī)值的基礎(chǔ)上做交集計算。

產(chǎn)生大量數(shù)據(jù)的終端大多數(shù)為低性能設(shè)備，如手機(jī)、傳感器等。需要大量計算力的兩方的隱私集合交集計算協(xié)議不適用于這類設(shè)備。由此產(chǎn)生了基于云環(huán)境的隱私集合交集計算協(xié)議。在該協(xié)議中低性能設(shè)備將部分計算外包給高性能的服務(wù)器，從而降低計算開銷。

現(xiàn)有的基于云環(huán)境的PSI大體上分為基于對稱密碼體制的PSI[6]和基于非對稱密碼體制的PSI[7]兩種。其中基于對稱密碼體制的PSI，兩個客戶端將自己的元素用對面密碼體制的加密算法將元素加密，發(fā)送給服務(wù)器，服務(wù)器在密文上做交集計算，將結(jié)果返回給客戶端；基于非對稱密碼體制的PSI，將本地元素用非對稱密碼體制的加密算法加密，發(fā)送給服務(wù)器，服務(wù)器利用加密之后的數(shù)學(xué)性質(zhì)做交集計算。但是以上兩種協(xié)議都各有缺點(diǎn)，不能很好地滿足人們的需求。

本文提出一種新的基于云環(huán)境的PSI，本協(xié)議是在兩方的基于OT協(xié)議PSI上進(jìn)行擴(kuò)展而衍生的新協(xié)議。本協(xié)議的效率遠(yuǎn)遠(yuǎn)高于基于非對稱密碼體制的PSI，安全性高于基于對稱密碼體制的PSI。

1 預(yù)備知識

1.1 安全模型

目前，在安全多方計算領(lǐng)域，GOLDREICH O所提出的安全性定義[8]是被廣泛接受的，所以以下采用該定義，將參與方分為三類：

(1)誠實參與者：完全遵守協(xié)議的執(zhí)行過程，在協(xié)議執(zhí)行過程中不會監(jiān)聽，偽造各參與方的信息。

(2)半誠實參與者：完全遵守協(xié)議的執(zhí)行過程，但是可能會在執(zhí)行過程中監(jiān)聽其他參與方的輸入輸出信息，從而推測其他參與者的隱私信息。

(3)惡意參與者：可能不會完全遵守協(xié)議的執(zhí)行過程，可能會拒絕參與協(xié)議，終止協(xié)議，或者在協(xié)議執(zhí)行過程中發(fā)送虛假的數(shù)據(jù)。

其中半誠實模型是在安全多方計算中廣泛使用的模型，也是更接近于真實場景的模型，以下就以半誠實模型為安全模型對協(xié)議進(jìn)行分析。

1.2 不經(jīng)意傳輸(Oblivious Transfer，OT)

OT協(xié)議[9-10]是一種基于公鑰密碼體制的協(xié)議，也是一種多方安全計算的基礎(chǔ)協(xié)議。在協(xié)議中有兩個參與方分別為發(fā)送方P1和接收方P2，P1有N條數(shù)據(jù)d1,d2,…,dn，P2擁有選擇向量σ。在協(xié)議執(zhí)行前P1的輸入為N條數(shù)據(jù)d1,d2,…,dn，P2的輸入為選擇向量σ。在執(zhí)行完協(xié)議之后P2會獲得數(shù)據(jù)dσ，并且不能獲取P1的其他數(shù)據(jù)的信息。P1沒有輸出且不能獲取P2的選擇向量σ。

OT協(xié)議在近些年發(fā)展也很迅速，由最初的二選一OT協(xié)議、N選一OT協(xié)議，為減少計算開銷而發(fā)展為二選一擴(kuò)展OT協(xié)議、N選一擴(kuò)展OT協(xié)議，同時為了減少通信開銷發(fā)展為它們對應(yīng)的隨機(jī)OT協(xié)議。本文所采用的是隨機(jī)N選一OT協(xié)議。

1.3 布谷鳥哈希

布谷鳥哈希是在簡單哈希函數(shù)的基礎(chǔ)上解決了哈希函數(shù)的沖突問題?？梢酝ㄟ^添加哈希函數(shù)或者通過哈希表來實現(xiàn)。

本文通過添加哈希函數(shù)來解決沖突，算法的實現(xiàn)步驟為，首先將元素用不同的哈希函數(shù)映射到哈希桶中對應(yīng)的位置。在所有映射到的位置中，如果有空的哈希桶，則選擇任意一個插入，如果映射到的位置全都有元素，則任意選擇一個桶插入，將桶中的元素踢出，被踢出的元素繼續(xù)執(zhí)行以上操作，直到找到合適的位置插入。

經(jīng)過多次循環(huán)之后，有的元素仍然不能找到合適的位置插入，則可以將插入失敗的元素插入到一個數(shù)據(jù)結(jié)構(gòu)Stash中。

2 基于OT協(xié)議的外包隱私集合交集協(xié)議

本節(jié)對基于OT協(xié)議的外包隱私集合交集協(xié)議的主體部分進(jìn)行描述，然后對協(xié)議的效率、正確性和安全性進(jìn)行分析。在協(xié)議中所用到的符號，參與方分別為Alice、Bob，Alice的集合為Da={x1,x2,…,xn1}，Bod的集合為Db={y1,y2,…,yn2}。Alice和Bob執(zhí)行OT協(xié)議之后所產(chǎn)生的隨機(jī)序列mask。服務(wù)器為C。

2.1 協(xié)議過程

協(xié)議主體分為三個階段：

第一階段：Hash(本地執(zhí)行)

(1)Alice將集合中的元素通過設(shè)置中的k次不同哈希函數(shù)的簡單哈希映射到哈希表中。

(2)Bob將集合中的元素映射用設(shè)置中的k個不同哈希函數(shù)的布谷鳥哈希，將元素映射到哈希表中。

第二階段:OT協(xié)議(兩個客戶端通信)

(1)對于每個哈希桶，Alice、Bob執(zhí)行隨機(jī)OT協(xié)議，Bob作為OT協(xié)議的發(fā)送方以哈希桶中的元素為選擇向量，Alice作為OT協(xié)議的接收方。

(2)Alice將收到的mask添加到集合中，作為對隱私集合的加密，Bob選擇哈希桶中對應(yīng)元素的mask，作為對隱私集合的加密。

第三階段：計算交集(客戶端和云服務(wù)器通信)

758 Permanent pacemaker implantation after cardiac surgery: an analysis of 103 cases

(1)Alice、Bob在自己的mask集合發(fā)送給服務(wù)器，服務(wù)器在mask上做交集計算，并將結(jié)果返回給Alice、Bob。

(2)Alice，Bob收到返回的集合后，就可以根據(jù)mask找到對應(yīng)的元素，得到最后的隱私集合交集。

基于OT協(xié)議的隱私集合交集計算過程如圖1所示。

圖1 基于OT協(xié)議的隱私集合交集計算

2.2 協(xié)議分析

(1)正確性

在這里考慮元素成功映射到哈希桶中的情況，如果插入失敗，而放到Stash時，原理和在哈希桶中的正確性證明無差異。假設(shè)Da中有一個元素xi，Db中有一個元素yj。下面分兩種情況討論。

當(dāng)xi=yj時，因為兩個元素相同，所以肯定會通過k個哈希函數(shù)中的一個映射同一個桶中，對這個桶中的元素執(zhí)行OT協(xié)議之后，這兩個元素的mask也是相同的，之后計算交集時能正確判斷兩個元素相等。

當(dāng)xi≠yj時，如果要錯誤地判斷它們?yōu)橄嗟?，它們的mask必須相同，mask相等的概率為2，Alice的mask和Bob對應(yīng)的桶中的所有mask都要進(jìn)行比較，Alice和Bob桶中任意元素相等的概率為kn1n22，所以要讓它們都不相同的概率為1-kn1n22。

(2)安全性

在半誠實模型下考慮協(xié)議的安全性。只有在協(xié)議的第二階段和第三階段才有可能泄露隱私信息。

首先考慮第二階段，兩個客戶端執(zhí)行OT協(xié)議，對于Bob來說肯定是安全的，因為在協(xié)議執(zhí)行期間并沒有輸入隱私信息。對于Alice來說輸入了選擇向量，即對應(yīng)的元素哈希之后的值，但是OT協(xié)議保證了Bob不能獲取該選擇向量。所以對于Alice來說也是安全的。

再來考慮第三階段，在本階段所發(fā)送的都是mask，該值是雙方通過隨機(jī)OT協(xié)議所產(chǎn)生的和原來的元素是獨(dú)立的隨機(jī)序列，所以不能通過mask推斷出原有隱私集合的信息。

(3)效率

下面分析該協(xié)議的效率，將協(xié)議的效率分為計算效率和通信效率。假設(shè)交集大小為I。

首先分析協(xié)議的計算效率，對于客戶端來說，在協(xié)議的第一階段對隱私集合中的元素用哈希函數(shù)映射到對應(yīng)的哈希桶中，所執(zhí)行的哈希操作為|Da|×k(元素個數(shù)乘哈希函數(shù)的數(shù)量)。第二階段，計算雙方執(zhí)行OT協(xié)議，一共執(zhí)行了(s+b)次OT協(xié)議，可以通過增加哈希函數(shù)來減少Stash的大小，從而減少執(zhí)行OT協(xié)議的次數(shù)來降低計算開銷，第三階段，根據(jù)服務(wù)器返回的結(jié)果查詢對應(yīng)的元素，在時間復(fù)雜度為O(I)。對于服務(wù)器來說，只有在密文上計算交集，時間復(fù)雜度為O(|Da|+|Db|)。

然后分析協(xié)議的通信開銷，對客戶端來說通信開銷為兩個客戶端執(zhí)行OT協(xié)議時和發(fā)送給服務(wù)器mask所產(chǎn)生的流量，這兩部分通信開銷都和元素的大小呈正相關(guān)。對于服務(wù)器來說，只是最后將交集結(jié)果返回給客戶端所以通信開銷和交集的大小呈正相關(guān)。

3 實驗

在實驗部分，實現(xiàn)了基于對稱密碼體制的PSI、基于非對稱密碼體制的PSI和基于OT協(xié)議的PSI，并將三種協(xié)議進(jìn)行對比分析。

實驗設(shè)置：隱私集合分為25，210，216,220,224等數(shù)量級不同的集合，分析三種協(xié)議在集合大小不同時的計算和通信開銷。

假設(shè)計算隱私集合交集的兩個客戶端分別為Alice和Bob，Alice和Bob分別選用以上的數(shù)量級大小不同的集合作為自己的隱私集合，和對方做隱私集合交集計算。

首先對表1分析，首先看Alice集合小于等于Bob集合時，固定Alice的集合大小不變增大Bob集合的大小，所需的計算時間增大；再看Alice集合大于Bob集合時，固定Alice集合大小不變增大Bob集合大小，所需的計算時間基本不變。這里是因為采用采用布谷鳥哈希插入元素時，所需的時間大于采用簡單哈希插入元素的時間，而且需要等待哈希操作結(jié)束之后才能執(zhí)行之后的OT協(xié)議。

現(xiàn)在對表2分析，第一，Alice和Bob發(fā)送的數(shù)據(jù)量相互獨(dú)立，且只與本地數(shù)據(jù)集大小有關(guān)；第二，當(dāng)Alice和Bob本地數(shù)據(jù)集大小相同時，Alice所需要發(fā)送的數(shù)據(jù)量大致為Bob的兩倍，這是因為Alice作為OT協(xié)議的發(fā)送方，需要發(fā)送更多的數(shù)據(jù)；第三，本協(xié)議所需發(fā)送的數(shù)據(jù)量較大，比如在集合大小為224時，Bob所要發(fā)送的數(shù)據(jù)為480 MB。

從圖2中可以看出，基于對稱密碼體制的隱私集合交集計算協(xié)議所需的計算量和發(fā)送的數(shù)據(jù)量都是最少的，基于非對稱密碼體制的隱私集合交集計算協(xié)議所需的計算量和發(fā)送的數(shù)據(jù)量是最多的，而本協(xié)議基于OT協(xié)議的隱私集合交集計算協(xié)議所需的計算量和發(fā)送的數(shù)據(jù)量居中。

表1 協(xié)議的計算時間 (ms)

注：1)表中第一行為Bob即接收方的隱私集合大小，第一列為Alice即發(fā)送方的隱私集合大小。

表2 協(xié)議的通信開銷 (MB)

注：1)表中第一行為Bob即接收方的隱私集合大小，第一列為Alice即發(fā)送方的隱私集合大小。

2)表中A表示客戶端Alice，B表示客戶端Bob。

圖2 在數(shù)據(jù)量為時三種方法所需的計算時間和發(fā)送數(shù)據(jù)量對比

下面對三種協(xié)議的安全性進(jìn)行對比，三種協(xié)議安全性最主要的區(qū)別就是是否可以抵抗服務(wù)器與任意一端客戶端的合謀攻擊?；趯ΨQ加密體制的隱私集合交集協(xié)議不能抗合謀攻擊，因為客戶端雙方所用密鑰相同，只要有一方客戶端和服務(wù)器合謀，就會泄露另一客戶端的信息，基于非對稱加密的隱私集合交集協(xié)議和基于OT協(xié)議的隱私集合交集協(xié)議可以抗合謀攻擊。

總的來說，本協(xié)議證明半誠實模型下是安全的，可以抵抗合謀攻擊，并且有較高的計算效率。

4 結(jié)論

本文提出了一種新的在云環(huán)境下的基于OT協(xié)議的隱私集合交集計算協(xié)議，該協(xié)議提供了比基于對稱密碼體制的隱私集合交集計算協(xié)議更高的安全性，而計算開銷和通信開銷遠(yuǎn)小于基于非對稱密碼體制的隱私集合交集算法。

在未來工作中會繼續(xù)對隱私集合交集協(xié)議的計算效率和通信效率進(jìn)行優(yōu)化。目前為止大多是兩個客戶端計算交集，未來的一個研究方向是將隱私集合交集計算協(xié)議擴(kuò)展為多個客戶端同時計算交集。

[1] FREEDMAN M J, NISSIM K, PINKAS B. Efficient private matching and set intersection[C]//International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2004: 1-19.

[2] FREEDMAN M J, ISHAI Y, PINKAS B, et al. Keyword search and oblivious pseudorandom functions[C]//Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2005: 303-324.

[3] DE CRISTOFARO E, TSUDIK G. Experimenting with fast private set intersection[C]//International Conference on Trust and Trustworthy Computing. Springer, Berlin, Heidelberg, 2012: 55-73.

[4] YAO A C C. How to generate and exchange secrets[C]//27th Annual Symposium on Foundations of Computer Science. IEEE, 1986: 162-167.

[5] PINKAS B, SCHNEIDER T, ZOHNER M. Scalable private set intersection based on OT extension[J]. IACR Cryptology ePrint Archive, 2016, 2016: 930.

[6] KAMARA S, MOHASSEL P, RAYKOVA M, et al. Scaling private set intersection to billion-element sets[C]//International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2014: 195-215.

[7] KERSCHBAUM F. Collusion-resistant outsourcing of private set intersection[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing. ACM, 2012: 1451-1456.

[8] GOLDREICH O. Secure multi-party computation[J]. Manuscript. Preliminary version, 1998: 86-97.

[9] NAOR M, PINKAS B. Efficient oblivious transfer protocols[C]//Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2001: 448-457.

[10] ASHAROV G, LINDELL Y, SCHNEIDER T, et al. More efficient oblivious transfer and extensions for faster secure computation[C]//Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. ACM, 2013: 535-548.