一種基于并行化OPPRF的隱私集合交集協(xié)議*

李 順

（四川大學(xué)，四川 成都 610207）

0 引言

在大數(shù)據(jù)以及移動互聯(lián)網(wǎng)環(huán)境下，數(shù)據(jù)成為推動技術(shù)發(fā)展的重要驅(qū)動力，但與此同時隱私數(shù)據(jù)泄漏事件頻繁發(fā)生，加深了人們對隱私數(shù)據(jù)保護的擔(dān)憂。安全多方計算最早由Yao[1]提出，它作為一種以密碼學(xué)為基礎(chǔ)的高可靠數(shù)據(jù)保護技術(shù)，可以很好地解決現(xiàn)實環(huán)境中的隱私泄露問題。隱私集合交集（Private Set Intersection，PSI）是安全多方計算中最為活躍的應(yīng)用領(lǐng)域之一。PSI 可以使提供數(shù)據(jù)并參與計算的協(xié)議方在不泄露其他數(shù)據(jù)的情況下得到最終的交集信息，從而達到保護各方隱私的效果。

在基于半誠實模型的兩方PSI 協(xié)議方面，Dong等人[2]將布隆過濾器用于解決PSI 問題，并設(shè)計了混淆布隆過濾器以滿足協(xié)議的安全性要求。Pinkas等人[3-6]詳細分析了當(dāng)時PSI 協(xié)議的主要構(gòu)造方法，提出了基于不經(jīng)意傳輸（Oblivious Transfer，OT）擴展的專用PSI 協(xié)議和基于電路實現(xiàn)的通用PSI 協(xié)議，并將協(xié)議和布谷鳥哈希方法相結(jié)合，在縮小元素長度以及擴展布谷鳥哈希算法的維度等方面進行優(yōu)化。Kolesnikov 等人[7]將不經(jīng)意偽隨機函 數(shù)（Oblivious Pseudo-random Function，OPRF）規(guī)范引入到PSI 協(xié)議中，設(shè)計了一種批處理相關(guān)密鑰OPRF 結(jié)構(gòu)，將不經(jīng)意傳輸、哈希算法、對稱密碼體系以及位運算有效地結(jié)合起來，可以高效求解PSI 問題。Kolesnikov 等人[8]首先提出了不經(jīng)意編碼偽隨機函數(shù)（Programmable OPRF，OPPRF）的概念，其次給出了OPPRF 的3 種構(gòu)造方法，包括多項式、布隆過濾器和表，最后結(jié)合零共享實現(xiàn)了多方PSI協(xié)議。Pinkas 等人[9]基于多項式實現(xiàn)了稀疏不經(jīng)意傳輸（Sparse Oblivious Transfer，SpOT）的構(gòu)造，此協(xié)議在通信復(fù)雜度方面具有較好的表現(xiàn)。

本文采用文獻[10]中將元素散列到矩陣中的思想，通過比較偽隨機函數(shù)值求出集合交集。本文第2 節(jié)敘述協(xié)議實現(xiàn)需要使用的基本技術(shù)，第3 節(jié)詳細說明基于可并行化OPPRF 的PSI 協(xié)議的構(gòu)造方法，第4 節(jié)給出協(xié)議的安全性證明，第5 節(jié)為協(xié)議的實驗結(jié)果，第6 節(jié)對本文進行總結(jié)。

1 相關(guān)技術(shù)

1.1 安全模型

計算不可區(qū)分是安全多方計算中的基本概念，文獻[11]給出了計算不可區(qū)分的定義，具體如下文所述。

定義1 計算不可區(qū)分

在n的值足夠大的情況下，對于每一個概率多項式時間的算法D，總存在一個可忽略函數(shù)negl滿足：

則稱概率集合α={Xn}n∈N和β={Yn}n∈N計算不可區(qū)分。

在理想的PSI 函數(shù)中，發(fā)送方和接收方以各自的集合元素作為函數(shù)輸入，接收方得到函數(shù)輸出即集合交集。在現(xiàn)實的半誠實模型中，存在一個半誠實的攻擊者，遵守協(xié)議規(guī)定的同時想盡可能獲取更多信息。在通用安全計算中基于模擬的現(xiàn)實理想模型中，如果協(xié)議中所遭受的攻擊在理想場景中同樣可以實現(xiàn)，則說明協(xié)議是安全的。

定義2 計算不可區(qū)分的基于半誠實模型的PSI協(xié)議

式中：view1和view2分別為發(fā)送方和接收方在協(xié)議中的視圖；≈表示計算不可區(qū)分。

1.2 不經(jīng)意傳輸

OT是安全多方計算中的基礎(chǔ)兩方密碼學(xué)協(xié)議，OT 的不經(jīng)意特性能夠很好地保護參與方的隱私。1-out-of-2 OT 函數(shù)如圖1 所示，發(fā)送方有兩個輸入x1和x2，接收方有一個選擇位c，最后接收方可以得到輸出xc。

圖1 OT 函數(shù)

為了減少原始OT 協(xié)議中的交互次數(shù)，Asharov等人[12]提出了隨機OT（Random OT，R-OT），在R-OT 中，發(fā)送方S 的輸入保持不變，接收方R 不需要提供任何輸入，而是由協(xié)議隨機確定選擇位c，并最終向接收方發(fā)送{xc,c}。

2 協(xié)議構(gòu)造

2.1 協(xié)議概述

本文構(gòu)造了一個基于不經(jīng)意編碼偽隨機函數(shù)的隱私集合交集協(xié)議。該協(xié)議主要包括元素散列、位置映射、OT 交互以及OPRF 值對比等階段。下面概述協(xié)議的構(gòu)造思想，主要協(xié)議過程如圖2 所示，圖中簡化了OT 階段發(fā)送方與接收方之間的交互。

圖2 協(xié)議架構(gòu)

對于發(fā)送方，首先基于簡單哈希將元素散列到不同的桶中；其次分配線程處理一定數(shù)量的桶，根據(jù)從接收方得到的OPPRF 矩陣計算每個桶中的哈希值所對應(yīng)的偽隨機值；最后將該值發(fā)送給接收方。對于接收方，先通過均衡哈希將元素散列到桶中，然后分配線程，根據(jù)桶中的元素生成位置矩陣，在與發(fā)送方OT 交互完畢后，生成每個元素對應(yīng)的偽隨機值，最后從發(fā)送方接收信息并計算交集。

2.2 不經(jīng)意可編碼偽隨機函數(shù)

2.2.1 OPPRF 定義

定義3 OPPRF

不經(jīng)意可編碼偽隨機函數(shù)在OPPRF 的基礎(chǔ)上支持對多個元素的操作，可以通過將多個元素編碼到偽隨機函數(shù)中形成OPPRF 函數(shù)，該函數(shù)對于每一個輸入會產(chǎn)生特定的偽隨機數(shù)出。OPPRF 的定義如圖3 所示。

圖3 OPPRF 函數(shù)

2.2.2 OPPRF 構(gòu)造

OPPRF 的構(gòu)造過程可以分為初始化、不經(jīng)意傳輸以及生成OPRF 值等3 個階段，具體如下文所述。

（1）初始化：首先由P1生成隨機字符串s，P2生成m×w維的全1 矩陣L；其次基于PRF密鑰k對元素的哈希值做加密運算，將密文作為位置向量，在矩陣L中將位置向量所對應(yīng)的位置設(shè)置為0。

（2）不經(jīng)意傳輸：P2隨機生成m×w維的位矩陣R，然后計算矩陣B=L⊕R，P2以矩陣R和矩陣B輸入，P1以隨機字符串s作為輸入，共同執(zhí)行w次不經(jīng)意傳輸后，P1得到矩陣A。

（3）計算OPRF 值：P2將PRF 密鑰k傳送給P1，P1先計算每個集合元素的位置向量，然后拼接矩陣R中位置向量對應(yīng)的比特位，最后對拼接結(jié)果進行哈希得到OPRF 值，將其發(fā)送給P2并由P2計算集合交集。由協(xié)議構(gòu)造可知，如果雙方存在交集元素，其所對應(yīng)的OPRF 值相等，否則OPRF 值相同的概率幾乎可以忽略。

OPPRF 的標(biāo)準(zhǔn)構(gòu)造過程如圖4 所示，協(xié)議分為編碼和解碼兩個階段，在編碼階段雙方根據(jù)各自的元素生成OPPRF 矩陣，在解碼階段通過OPPRF 矩陣得到每個元素對應(yīng)的OPRF 值。

圖4 ∏OPPRF 協(xié)議

該OPPRF結(jié)構(gòu)主要基于輕量級的密碼學(xué)工具，只在OT 階段使用到必要的非對稱密碼工具，相對于傳統(tǒng)的基于多項式計算的方法在效率上得到一定程度的提升。但是當(dāng)集合元素個數(shù)增加時，計算位置映射矩陣階段時間占比提升，協(xié)議實用性降低。針對這一問題，引入了簡單哈希與均衡哈希，使協(xié)議支持多線程運行，每個線程處理的元素個數(shù)大幅度降低，在保證安全性的同時提升了運行效率。

2.3 基于并行化OPPRF 的PSI 協(xié)議

首先構(gòu)造并行化的OPPRF，P1和P2的輸入被劃分成多個子集。每個子集合對應(yīng)一個OPPRF實例，在所有實例運行結(jié)束后，P1得到輸出集合。并行化OPPRF 的主要構(gòu)造過程如下：

（1）P1與P2共同執(zhí)行β個OPPRF 實例，對于第i個實例，執(zhí)行（2）和（3）。

（2）P2將密鑰kj,j∈[β]發(fā)送給P1，然后計算Hint(kj,Yj)，得到hint，與P1執(zhí)行OT 交互后，P1得到對應(yīng)的hint′。

（3）P1根據(jù)hint得到輸出Φ={φ1,…,φβ}，其中φi=H(A1[v[1]]||…||Aw[v[w]])，在所有的OPPRF 完成后，P1得到全部輸出{Φ1,…,Φβ}。

并行化PSI 協(xié)議在并行OPPRF 構(gòu)造基礎(chǔ)上引入了兩種哈希算法。P1使用簡單哈希算法，P2使用均衡哈希算法，分別將各自的集合元素散列到Bin中。然后在每對Bin 中計算OPPRF，在所有OPPRF執(zhí)行完畢后P1得到全部OPRF 輸出，并將其發(fā)送給P2。P2執(zhí)行類似的操作得到OPRF 輸出，與P1的結(jié)果對比后即可得到所有的交集元素。圖5 為基于并行化OPPRF 的PSI 協(xié)議。

圖5 并行化PSI 協(xié)議

3 安全性證明

本文根據(jù)半誠實模型下的通用定義[11]證明協(xié)議的安全性。在協(xié)議中給定各參與方與輸入輸出的情況下，各方的視圖均可由模擬得到。

本文基于哈希函數(shù)的確定性，對于元素x∈X和y∈Y，如果x=y，則散列值相同，基于哈希函數(shù)的隨機性，如果x ≠y，則出現(xiàn)哈希碰撞的概率可以忽略。另外，本文假設(shè)OT 協(xié)議安全地實現(xiàn)了OT 函數(shù)，可以將協(xié)議替換為一個完全可信方，該可信方接收來自接收方的輸入x，并返回給發(fā)送方隨機密鑰k，向接收方輸出值Fk(x)。

由于P1在PSI 協(xié)議中得到的唯一信息是在隨機OT 中選擇的隨機密鑰ki和hint，獨立于P2的輸入。因此，P1在協(xié)議中的視圖可以通過向其發(fā)送隨機值列表、使用密鑰加密輸入，并將結(jié)果發(fā)送給P2模擬得到，從而滿足式（2）。

P2在協(xié)議中的視圖由其在OT 協(xié)議中得到的密文集合M2和P1發(fā)送的密文集合M1組成。假設(shè)存在元素x∈X和y∈Y，如果x=y，則有相應(yīng)的值mx∈M1，my∈M2，其中mx=my。基于F的偽隨機性，M1、M2中的所有其他值與隨機值無法區(qū)分。因此，可以在給定協(xié)議輸出的情況下模擬P2的視圖：集合M2由隨機值m1,…,my組成。對于每個y∈X∩Y，將my添加到M1中，然后向M1中填充|X|-|Y|個隨機值。這與可信情況下，P2所接收到的值的分布情況相同，從而滿足式（3）。

4 實驗結(jié)果

在本部分，將從協(xié)議的總時間開銷、位置映射階段的開銷等方面評估方案的效果。協(xié)議基于C++語言實現(xiàn)，實驗環(huán)境配置如表1 所示。

表1 實驗環(huán)境

圖6 為在局域網(wǎng)環(huán)境下，集合元素數(shù)量分別為214、216、218、220、222、224時文獻[8]方案、文獻[10]方案與2 個線程下的本文方案總時間開銷的情況。當(dāng)元素數(shù)量低于216時，協(xié)議表現(xiàn)大致相近，當(dāng)元素數(shù)量繼續(xù)增加時，本文協(xié)議的優(yōu)勢更加明顯。

圖6 協(xié)議總時間開銷

圖7 為本文協(xié)議與文獻[10]方案計算位置映射矩陣的開銷。由于在實驗中使用了兩個線程，該階段的時間開銷降低了一半左右。

圖7 計算位置映射矩陣的時間開銷

5 結(jié)語

隱私集合交集作為安全多方計算的一個特殊應(yīng)用場景，在很多領(lǐng)域有著廣泛的應(yīng)用空間。本文針對半誠實模型下有兩個參與方的PSI 問題，采用位置映射矩陣和不經(jīng)意傳輸構(gòu)造OPPRF，避免了復(fù)雜的多項式操作，并且可以達到同樣的隱私保護效果。另外，本文給出了協(xié)議構(gòu)造過程，并證明了協(xié)議的安全性，還引入了簡單哈希和均衡哈希技術(shù)，使得協(xié)議可以并行執(zhí)行，提升運行效率。下一步工作將進一步優(yōu)化方案，比如研究支持多方集合交集、集合元素更新、滿足惡意安全假設(shè)等操作。