基于OT協議的外包隱私集合交集計算協議

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

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

0 引言

隨著物聯網技術、云計算技術的快速發展，信息系統中每時每刻都會產生大量的數據。據統計，在2013年時社交網站Twitter每天活躍用戶達到2億人次，每天發送信息超過4 億條，在2017年，Facebook自己披露每日活躍用戶達到13 億。

這是一個數據爆發的時代，每天都有大量數據產生，那么大數據下的隱私保護問題已經成為學術界和工業界的關注焦點。

隱私集合交集(Private Set Intersection，PSI)是安全多方計算的一個重要協議，它允許參與計算的各方只能獲得交集元素的信息。現在大部分PSI為參與方為兩方的協議，以實現的方法不同來分類。基于公鑰密碼體制的PSI，根據協議的設計思想不同可以分為：基于不經意多項式計算PSI[1]，本方案將元素表示為方程的根，然后通過同態加密方案來保證數據的安全性；基于不經意偽隨機函數PSI[2]，本方案客戶端和服務端通過不經意偽隨機函數將客戶端隱私集合加密，然后在密文上做交集，保證隱私數據的安全性。基于盲簽名的PSI[3]，本方案客戶端將數據進行盲化操作，然后服務器在盲化操作的數據上簽名和本地數據簽名之后發送給客戶端，客戶端執行去盲化操作，就可以在元素的簽名上做交集運算。基于混亂電路的PSI[4]，本方案通過設計混亂電路來實現所需要的交集功能，基于OT協議的PSI[5]，本方案通過執行隨機OT協議將元素變為一個隨機值，在隨機值的基礎上做交集計算。

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

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

本文提出一種新的基于云環境的PSI，本協議是在兩方的基于OT協議PSI上進行擴展而衍生的新協議。本協議的效率遠遠高于基于非對稱密碼體制的PSI，安全性高于基于對稱密碼體制的PSI。

1 預備知識

1.1 安全模型

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

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

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

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

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

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

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

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

1.3 布谷鳥哈希

布谷鳥哈希是在簡單哈希函數的基礎上解決了哈希函數的沖突問題。可以通過添加哈希函數或者通過哈希表來實現。

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

經過多次循環之后，有的元素仍然不能找到合適的位置插入，則可以將插入失敗的元素插入到一個數據結構Stash中。

2 基于OT協議的外包隱私集合交集協議

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

2.1 協議過程

協議主體分為三個階段：

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

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

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

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

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

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

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

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

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

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

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

圖1 基于OT協議的隱私集合交集計算

2.2 協議分析

(1)正確性

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

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

當xi≠yj時，如果要錯誤地判斷它們為相等，它們的mask必須相同，mask相等的概率為2，Alice的mask和Bob對應的桶中的所有mask都要進行比較，Alice和Bob桶中任意元素相等的概率為kn1n22，所以要讓它們都不相同的概率為1-kn1n22。

(2)安全性

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

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

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

(3)效率

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

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

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

3 實驗

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

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

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

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

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

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

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

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

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

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

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

圖2 在數據量為時三種方法所需的計算時間和發送數據量對比

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

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

4 結論

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

在未來工作中會繼續對隱私集合交集協議的計算效率和通信效率進行優化。目前為止大多是兩個客戶端計算交集，未來的一個研究方向是將隱私集合交集計算協議擴展為多個客戶端同時計算交集。

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