程 楠, 趙運(yùn)磊

1. 復(fù)旦大學(xué) 軟件學(xué)院, 上海210203

2. 復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 上海210203

1 引言

在當(dāng)今的數(shù)字時(shí)代, 越來(lái)越多的公司通過(guò)收集數(shù)據(jù), 并基于自身的合理需求加以利用而獲得了相當(dāng)?shù)幕貓?bào), 例如: 基于消費(fèi)者使用偏好等數(shù)據(jù), 互聯(lián)網(wǎng)公司研發(fā)出推薦系統(tǒng), 個(gè)性化地提供互聯(lián)網(wǎng)產(chǎn)品或服務(wù);基于用戶歷史瀏覽數(shù)據(jù)并結(jié)合智能算法, 廣告商實(shí)現(xiàn)了精準(zhǔn)營(yíng)銷. 這一回報(bào)也就反過(guò)來(lái)激發(fā)出更多的數(shù)據(jù)采集需求, 在這個(gè)過(guò)程中, 用戶的個(gè)人隱私必然越來(lái)越難以被保護(hù), 因此數(shù)據(jù)隱私計(jì)算技術(shù)就變得越來(lái)越重要: 于用戶而言, 這一技術(shù)能在最大限度地保護(hù)他們的隱私的同時(shí)提供便捷; 于商家而言, 這一技術(shù)可以在幫助他們避免核心數(shù)據(jù)的泄漏的前提下最大限度地發(fā)揮其核心數(shù)據(jù)的價(jià)值. 在全球日益重視數(shù)據(jù)安全的背景下, 各大國(guó)家已紛紛立法保護(hù)數(shù)據(jù)隱私(如美國(guó)的HIPAA、COPPA、GLBA、歐盟的DPP), 數(shù)據(jù)隱私計(jì)算技術(shù)逐漸成為當(dāng)前學(xué)界研究的一個(gè)熱潮.

兩方PSI (Private Set Intersection) 問(wèn)題是關(guān)于安全兩方計(jì)算模型中最基礎(chǔ)的一類問(wèn)題. 在兩方PSI問(wèn)題中, 我們用Alice 和Bob 表示參與方, 并假設(shè)其分別持有任意長(zhǎng)度字符集合X 和Y. 在一系列的交互完成后, 我們要求至少有一方能得到雙方的交集X ∩Y, 并且每一參與方都不能獲知關(guān)于對(duì)方集合元素的任何其它知識(shí). 我們可以使用基于不經(jīng)意傳輸(Oblivious Transfer, OT) 的協(xié)議[1–4]來(lái)高效地解決這個(gè)問(wèn)題.

兩方PSU/PSI-CA (Private Set Union/Private Set Intersection Cardinality) 問(wèn)題是兩方PSI 問(wèn)題的延伸, 它要求最終計(jì)算出|X ∪Y|/|X ∩Y|, 且在此過(guò)程中不泄漏任何其它的信息(包括自己的任何一個(gè)元素信息及自己的集合大小). 該問(wèn)題對(duì)應(yīng)于現(xiàn)實(shí)中許多隱私計(jì)算場(chǎng)景, 例如: 在社交網(wǎng)絡(luò)中, 兩個(gè)用戶可以在不泄漏自己具體好友信息的情況下比較其相同好友的比例, 來(lái)計(jì)算社交關(guān)系重合度; 在健康領(lǐng)域, 持有私有基因數(shù)據(jù)的客戶可以放心地與公共風(fēng)險(xiǎn)基因數(shù)據(jù)庫(kù)交互, 從而得知自己感染某種疾病的概率; 本文就是要討論解決PSU/PSI-CA 問(wèn)題的相關(guān)協(xié)議.

一般而言, 理論上所有的隱私計(jì)算問(wèn)題都可以用通用的的安全計(jì)算協(xié)議來(lái)解決(如GMW 協(xié)議[5]、混淆電路[6]). 但這些通用的方案需要較高的計(jì)算和通訊代價(jià). 因而, 對(duì)于具體的安全計(jì)算問(wèn)題, 我們通常使用專用的高效協(xié)議. 具體地, 對(duì)于解決PSU/PSI-CA 問(wèn)題的協(xié)議而言, 從輸出結(jié)果的精確程度來(lái)分類, 我們分為如下兩類.

(1) 第一類協(xié)議為完美計(jì)算協(xié)議, 它輸出精確的結(jié)果. 以文獻(xiàn)[7–12] 等工作為例, 它使用模糊多項(xiàng)式評(píng)估方法, 選定一個(gè)多項(xiàng)式來(lái)代表輸入集合并通過(guò)同態(tài)加密技術(shù)來(lái)合并評(píng)估集合的交. 但是這一類的協(xié)議使用大量的公鑰原語(yǔ), 因此, 即使在半誠(chéng)實(shí)模型下, 它們實(shí)際執(zhí)行時(shí)的資源消耗也非常大.

(2) 第二類協(xié)議為不完美計(jì)算協(xié)議, 它的輸出結(jié)果容許一定的誤差. 面對(duì)數(shù)量級(jí)較大的數(shù)據(jù)時(shí), 該類協(xié)議由于能夠在效率與可用性之間取得較好的平衡, 因而在現(xiàn)實(shí)中得到更廣泛的應(yīng)用. 例如:

? Egert-Fischlin 協(xié)議[13]通過(guò)將其中一方的布隆過(guò)濾器的每一位用ElGamal 公鑰系統(tǒng)[14]進(jìn)行加密, 從而實(shí)現(xiàn)隱私計(jì)算. Egert-Fischlin 協(xié)議的優(yōu)點(diǎn)在于非平衡性, 協(xié)議的主要計(jì)算開銷集中于其中一方, 因此它適合于服務(wù)器-客戶端類型的應(yīng)用場(chǎng)景[13]. 不過(guò)因其計(jì)算與通信復(fù)雜度均為O(n),所以當(dāng)輸入量級(jí)逐漸變大時(shí), 它便難以推廣應(yīng)用.

? Dong-Loukides 協(xié)議[15]基于Flajolet-Martin 技術(shù)[16]和OT14技術(shù), 它夠?qū)㈤L(zhǎng)度為n 的集合預(yù)處理為長(zhǎng)度為log(n) 的Flajolet-Martin 概要[16], 因而大大降低了后續(xù)使用OT14原語(yǔ)產(chǎn)生的計(jì)算開銷. 但該計(jì)算必須串行地調(diào)用OT14協(xié)議, 因此它的通信輪數(shù)較多, 網(wǎng)絡(luò)環(huán)境較差時(shí), 網(wǎng)絡(luò)時(shí)延影響比較明顯. 此外, 為了提高輸出結(jié)果的精確度, 這一協(xié)議需要在離線階段對(duì)同一個(gè)集合生成大量不同的Flajolet-Martin 概要[16], 因此它的哈希成本相對(duì)較高. 不過(guò), 實(shí)驗(yàn)數(shù)據(jù)[15]表明,Dong-Loukides 協(xié)議依然是目前解決PSU/PSI-CA 問(wèn)題最高效的協(xié)議之一.

本文側(cè)重于不完美計(jì)算協(xié)議的設(shè)計(jì)與分析, 因?yàn)樗軌蛟谛逝c可用性之間取得較好的平衡. 受Dong-Loukides 協(xié)議的啟發(fā), 我們提出一種基于預(yù)計(jì)算OT 模型[17]的方案, 在該方案中, 無(wú)論是解決PSU-CA 問(wèn)題還是PSI-CA 問(wèn)題, 首先都要進(jìn)行秘密分享(Secret Sharing), 它分為兩個(gè)階段: 即離線階段和在線處理階段. 離線階段中, Alice 和Bob 分別調(diào)用Silent-OT 協(xié)議[18]交互生成足夠多的偽隨機(jī)相關(guān)消息對(duì). 在線階段中, 假設(shè)Bob 為不經(jīng)意傳輸?shù)陌l(fā)送方, 則Bob 根據(jù)之前已生成好的偽隨機(jī)相關(guān)消息對(duì)跟自己真正要發(fā)送的消息做掩碼運(yùn)算, 之后發(fā)送給Alice, Alice 直接通過(guò)離線階段收到的消息進(jìn)行解密.這兩步操作完成后, Alice 和Bob 將分別得到關(guān)于HW(BFA∨BFB) 的秘密分享SA和SB. 而后:

? 在解決PSU-CA 問(wèn)題的子協(xié)議中, 不妨設(shè)Alice 為最終結(jié)果的輸出方, 那么此時(shí)Bob 需將其秘密分享SB發(fā)送給Alice, 則Alice 將兩個(gè)秘密分享SA和SB合并, 最終輸出估算的兩個(gè)集合的并集的勢(shì).

? 在解決PSI-CA 問(wèn)題的子協(xié)議中, Alice 和Bob 還需要額外執(zhí)行一個(gè)同態(tài)計(jì)算協(xié)議, 完成協(xié)議執(zhí)行后, 輸出方輸出估算的兩個(gè)集合的交集的勢(shì).

由于進(jìn)行秘密分享的離線過(guò)程的計(jì)算可以事先完成, 而在線階段的計(jì)算只進(jìn)行高效的掩碼運(yùn)算, 因此我們的秘密分享非常高效. 而且無(wú)論是對(duì)應(yīng)PSU-CA 還是PSI-CA 問(wèn)題的子協(xié)議, 后續(xù)的開銷都很小. 因此同之前大部分基于公鑰計(jì)算的協(xié)議相比, 我們的方案帶來(lái)了較大的效率提升.

2 預(yù)備知識(shí)

在本文中, 對(duì)于一個(gè)有限集合X 我們用符號(hào)|X| 表示它的勢(shì), 符號(hào)|X|?表示集合勢(shì)的近似整數(shù)估值. 符號(hào)BFX表示對(duì)應(yīng)集合X 的布隆過(guò)濾器. 表達(dá)式r ←$S 表示從有限集合S 中隨機(jī)均勻選取一個(gè)元素r. 對(duì)于正實(shí)數(shù)x, 符號(hào)?x?表示x 向下取整的值. 對(duì)于二進(jìn)制串B, 符號(hào)HW(B) 表示B 上1 的個(gè)數(shù).

2.1 布隆過(guò)濾器

在我們的方案設(shè)計(jì)中, 我們首先使用布隆過(guò)濾器(Bloom Filter, BF) 對(duì)集合進(jìn)行預(yù)處理, 布隆過(guò)濾器被Bloom[19]首次提出, 他將一個(gè)集合中的每一個(gè)元素通過(guò)若干哈希函數(shù)到映射到一個(gè)二進(jìn)制串, 最終得到一個(gè)輕量級(jí)的二進(jìn)制串, 這就是布隆過(guò)濾器. 它主要被用于檢測(cè)一個(gè)元素是否隸屬于某些數(shù)據(jù)集合. 當(dāng)構(gòu)建某個(gè)數(shù)據(jù)集X 的布隆過(guò)濾器時(shí), 首先我們會(huì)選定生成參數(shù): 包括k 個(gè)相互獨(dú)立的哈希函數(shù), 該布隆過(guò)濾器所預(yù)設(shè)的容量d, 錯(cuò)誤率e. 此外初始化一個(gè)全為0 的二進(jìn)制串BFX, 設(shè)其長(zhǎng)度為m, 繼而使用k個(gè)彼此獨(dú)立的哈希函數(shù)hi: {0,1}{1,··· ,m} (其中i ∈{1,··· ,k}) 將集合中的每一個(gè)元素映射到某個(gè)正整數(shù), 若BFX對(duì)應(yīng)位置的值為0, 則將其更改為1. 任何第三方若要檢測(cè)某個(gè)元素a 是否位于集合X中, 首先可使用對(duì)應(yīng)的哈希函數(shù)組計(jì)算a 所有的映射值, 接著檢查BFX上對(duì)應(yīng)位置是否全為1, 是的話說(shuō)明元素a 很可能位于集合X 中, 否則說(shuō)明a 一定不是集合X 中的元素.

圖1 展示了對(duì)集合{x,y,z} 生成布隆過(guò)濾器及進(jìn)行元素檢測(cè)的圖示[20], 其中哈希函數(shù)組的個(gè)數(shù)為k =3, 最終生成的布隆過(guò)濾器長(zhǎng)度m=18, 其中元素w 經(jīng)過(guò)檢測(cè)可知不在集合{x,y,z} 中, 因?yàn)樵撛氐哪硞€(gè)哈希值對(duì)應(yīng)的位置為0.

由于哈希碰撞的存在, 布隆過(guò)濾器存在一定的假陽(yáng)性檢測(cè). 布隆過(guò)濾器的長(zhǎng)度m 與哈希函數(shù)組的大小k 和其容量大小d 直接相關(guān), 直觀上, 將m 取得很大的話, 哈希的碰撞會(huì)減少, 布隆過(guò)濾器的檢測(cè)錯(cuò)誤率e 會(huì)降低, 但這樣在計(jì)算上會(huì)降低效率. 根據(jù)文獻(xiàn)[21], 使用如下公式對(duì)k 和m 進(jìn)行約束, 我們可以在布隆過(guò)濾器的計(jì)算效率與錯(cuò)誤率之間取得較好的平衡.

圖1 布隆過(guò)濾器生成及元素檢測(cè)示例Figure 1 Example for Bloom filter generating and membership checking

對(duì)于一個(gè)集合X, 我們可以用如下公式[22]估算它的勢(shì):

對(duì)兩個(gè)不同的集合A 和B, 設(shè)其使用同樣的參數(shù)分別生成BFA,BFB, 令BFA∨BFB表示BFA和BFB按位求或的二進(jìn)制串, 則估算兩個(gè)集合A, B 的并交集大小的公式分別為:

綜上所述, 布隆過(guò)濾器可以被用來(lái)估算兩方集合的并集的勢(shì), 不過(guò)這隱含地意味著它們都知曉對(duì)方集合的勢(shì)的上界.

2.2 Paillier 加密系統(tǒng)

本文在解決PSI-CA 問(wèn)題的協(xié)議中使用了Paillier 加密系統(tǒng)[23], 它是一個(gè)具有同態(tài)性質(zhì)的公鑰加密系統(tǒng), 分為密鑰生成算法、加密算法和解密算法, 如下所示(其中符號(hào)Z?n表示集合, 它滿足Z?n= {x ∈Zn:gcd(x,n)=1}).

密鑰生成算法:

Paillier 加密系統(tǒng)的安全性基于判定性復(fù)合剩余類假設(shè)(Decisional Composite Residuosity Assumptio, DCRA). 一般認(rèn)為, 當(dāng)n 足夠大時(shí), 對(duì)攻擊者而言, 不知道n 的素因式分解, 判定性復(fù)合剩余問(wèn)題是困難的. 該加密系統(tǒng)具備加法同態(tài)性:

2.3 不經(jīng)意傳輸

圖2 離線-在線框架Figure 2 Offline-online framework

3 兩方PSU/PSI-CA 協(xié)議

本節(jié)中, 我們將給出解決PSU-CA 問(wèn)題和PSI-CA 問(wèn)題的協(xié)議構(gòu)造和相關(guān)證明. 首先, 我們分別給出解決PSU-CA 問(wèn)題和PSI-CA 問(wèn)題的兩個(gè)協(xié)議構(gòu)造(3.1 節(jié)), 然后分別給出它們的正確性證明(3.2 節(jié)),最后我們給出基于模擬的安全性證明(3.3 節(jié)).

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

在兩個(gè)協(xié)議執(zhí)行中, 我們不妨設(shè)兩方參與者分別為Alice 和Bob, 分別持有集合A 和B. 我們的協(xié)議要求兩方輸入兩個(gè)結(jié)構(gòu)相同的布隆過(guò)濾器, 其生成過(guò)程如下:

(1) Alice 和Bob 約定足夠大的容量d, 輸入錯(cuò)誤率e, 由公式(1)并經(jīng)過(guò)取整計(jì)算, 分別得到所使用哈希函數(shù)個(gè)數(shù)k 及所要生成的布隆過(guò)濾器的長(zhǎng)度m.

(2) Alice 和Bob 分別使用相同的k 個(gè)哈希函數(shù)對(duì)他們的輸入集合A,B 進(jìn)行處理, 最終獨(dú)立地得到各自的布隆過(guò)濾器BFA,BFB.

此后在協(xié)議描述中我們直接將BFA,BFB作為輸入, 不再贅述該生成過(guò)程. 無(wú)論是PSU-CA 協(xié)議或者PSI-CA 協(xié)議, Alice 和Bob 在離線階段執(zhí)行相同的操作, 如下所示.

3.1.1 離線階段

3.1.2 在線階段

無(wú)論是計(jì)算PSU-CA 問(wèn)題還是PSI-CA 問(wèn)題, Alice 和Bob 首先都要執(zhí)行秘密分享協(xié)議, 如圖3 所示.

圖3 秘密分享協(xié)議Figure 3 Secret sharing protocol

(i) 首先Alice 和Bob 執(zhí)行兩輪交互, 具體步驟如下:

圖4 同態(tài)計(jì)算協(xié)議Figure 4 Homomorphic computing protocol

3.2 正確性分析

故原命題得證.

3.3 安全性分析

目前兩大主流安全模型是半誠(chéng)實(shí)模型(Semi-Honest Model) 和惡意模型(Malicious Model)[27]. 在半誠(chéng)實(shí)模型下, 敵手會(huì)記錄協(xié)議交互過(guò)程中的所有數(shù)據(jù), 并嘗試提取其它參與方的秘密信息. 在惡意模型下, 敵手會(huì)以任意的方式偏離協(xié)議的執(zhí)行來(lái)進(jìn)行破壞或窺探.

本文所涉及的所有安全協(xié)議都是在半誠(chéng)實(shí)模型下[27]證明的. 一般而言, 當(dāng)構(gòu)建一個(gè)隱私計(jì)算協(xié)議時(shí),我們會(huì)首先在半誠(chéng)實(shí)模型下構(gòu)建. 雖然半誠(chéng)實(shí)模型比惡意模型的假設(shè)要弱, 但實(shí)際上, 現(xiàn)實(shí)的業(yè)務(wù)部署都必須符合某些安全法令的制約, 這保證了半誠(chéng)實(shí)模型下的協(xié)議依然有廣泛的應(yīng)用前景.

定理1 存在一個(gè)概率多項(xiàng)式時(shí)間的模擬器Sim1使得對(duì)于所有的安全參數(shù)n 滿足2n> |BFA| 和輸入BFA, 有其中S(·),R(·) 分別表示Alice 和Bob 的偽隨機(jī)相關(guān)預(yù)設(shè)消息,(BFA,BFB,S(·),R(·)) 表示在協(xié)議#1 執(zhí)行中Alice 的視圖.

算法1: Alice 的模擬算法Input: 1n,BFA,{(R01,R11),··· ,(R0m,R1m)}Output: Sim1(·)1 隨機(jī)選取¨r ←${0,1}m, 作為Bob 第一輪發(fā)送給Alice 的輸入模擬.2 Alice 真實(shí)按照協(xié)議執(zhí)行計(jì)算{(M0i,M1i)}i∈[m] 和S1, 模擬第二輪的輸出.

證明: 我們用算法1 描述Sim1(·).

在算法1 的第一步中, ¨r 在 {0,1}m上隨機(jī)均勻選取, 而在真實(shí)的執(zhí)行中, ¨r = {d1⊕(1 ?BFB[1]),··· ,dm⊕(1 ?BFB[m])}, 因?yàn)閐i為隨機(jī)選取, 因此模擬的Bob 輸入¨r 與真實(shí)協(xié)議執(zhí)行中Bob發(fā)送給Alice 的¨r 是計(jì)算不可區(qū)分的. 在第二步中, 由于上述模擬算法完全按照真實(shí)協(xié)議執(zhí)行的步驟, 因此模擬的輸出與真實(shí)的輸出同分布.

綜上所述, 上述Alice 的模擬算法能模擬協(xié)議#1 執(zhí)行中Alice 的交互視圖. 因此定理得證.

定理2 存在一個(gè)概率多項(xiàng)式時(shí)間的模擬器Sim2使得對(duì)于所有的安全參數(shù)n 滿足2n> |BFA| 和輸入BFA,BFB, 有

其中S(·),R(·) 分別為Alice 和Bob 的偽隨機(jī)相關(guān)預(yù)設(shè)消息, View#1

B (BFA,BFB,S(·),R(·)) 為上述協(xié)議

#1 中Bob 的交互視圖.

算法2: Bob 的模擬算法Input: 1n,BFB,HW(BFA ∨BFB),R(·)Output: Sim2(·)1 Bob 輸入R(·) 和BFB 之后, 按照協(xié)議#1 的真實(shí)執(zhí)行過(guò)程輸出Bob 第一輪的輸出模擬¨r.2 對(duì)于?i ∈[m], 選取ri ←${0,1}n. 選取MBFB[i]i = ri ⊕Rdii . 計(jì)算S1 = (2n +m ?HW(BFA ∨BFB)?(∑m i=1 ri) mod 2n)) mod 2n. 則上述{(M0i,M1 i)}i∈[m],S1 即為對(duì)第i ←${0,1}n；令M1?BFB[i]二輪Alice 輸入的模擬.3 真實(shí)地按照第三輪的執(zhí)行計(jì)算S2 作為對(duì)S2 的模擬輸出.

定理3 存在一個(gè)概率多項(xiàng)式時(shí)間的模擬器Sim1使得對(duì)于所有的安全參數(shù)λ 滿足2λ>m 和所有的輸入(S(·),R(·),|A|,|B|,m,k,(pk,sk)), 有

算法3: Alice 的模擬算法Input: 1λ,S(·),|A|,f(·)Output: Sim1(·)1 令S?1 := Encpk(0), 模擬Alice 第一輪輸出S1 的模擬.2 令?S?:= Encpk(0), 作為第二輪中?S 的模擬輸出.3 隨機(jī)選取β ←$(0,1) (表示從該區(qū)間選取小數(shù)點(diǎn)后四位的小數(shù)), 計(jì)算? = |A|?f(·)+β, 然后計(jì)算Dec ?S?= p·m ?·k exp m, 模擬Bob 的?S 的解密值T?, 最后輸出f(·).

算法4: Bob 的模擬算法Input: 1λ,R(·),|B|,BFB Output: Sim2(·)1 令 ?S1?:= Encpk(0), 模擬協(xié)議第一輪Alice 的輸入 ?S1 的模擬.2 令?S?:= Encpk(0), 作為第二輪?S 的模擬輸出.

證明: 我們用算法4 描述Sim2. 由于Bob 只需要模擬由同態(tài)加密保護(hù)的消息, 由于Paillier 加密系統(tǒng)抗選擇明文攻擊(Chosen Plaintext Attack, CPA) 的特性, 因此其能夠完美模擬真實(shí)協(xié)議中的消息. 那么通過(guò)上述給定輸入1λ,R(·),|B|,BFB, 該構(gòu)造能夠模擬協(xié)議#2 中Bob 的交互視圖, 故定理得證.

綜上所述, 結(jié)合定理1 和定理2, 我們使用模擬的方式證明了協(xié)議#1 在半誠(chéng)實(shí)模型下的安全性. 結(jié)合定理1–4, 我們證明了協(xié)議#2, 即解決PSI-CA 問(wèn)題的協(xié)議在半誠(chéng)實(shí)模型下也是安全的.

4 性能評(píng)估

本節(jié)我們從理論分析和具體實(shí)驗(yàn)兩個(gè)方面, 將我們的協(xié)議同Dong-Loukides 協(xié)議[15]在不同指標(biāo)上進(jìn)行比較, 來(lái)說(shuō)明我們的協(xié)議在總體上有較好的性能, 并且適用于更廣泛的應(yīng)用場(chǎng)景.

4.1 理論評(píng)估

表1 為定性的性能對(duì)比. 其中N 為集合的大小, k1為生成布隆過(guò)濾器的哈希函數(shù)個(gè)數(shù), k2為生成Flajolet-Matin 概要所需的哈希函數(shù)個(gè)數(shù). 且k1?k2. 其中的哈希開銷一列是指預(yù)處理階段的哈希開銷,在Dong-Loukides 協(xié)議中即指將集合轉(zhuǎn)化為Flajolet-Martin 概要[16]的哈希開銷(為了提高協(xié)議的計(jì)算結(jié)果準(zhǔn)確度, 一般需要將k2設(shè)置為比較大的常數(shù)), 而在協(xié)議#1,#2 中, 指布隆過(guò)濾器生成時(shí)的哈希開銷(此時(shí)k1=?, r 為錯(cuò)誤率).

從表1 可以看出協(xié)議#1 和協(xié)議#2 的通信輪數(shù)及冪指數(shù)運(yùn)算開銷均為為常數(shù), 此外可知, 協(xié)議#1和協(xié)議#2 除了通信量比Dong-Loukides 協(xié)議要大之外, 其它方面都更好. 且當(dāng)一個(gè)數(shù)據(jù)集的數(shù)據(jù)有微小更新時(shí), 在Dong-Loukides 協(xié)議中也需要幾乎重新生成Flajolet-Matin 概要, 這一不足也大大限制了Dong-Loukides 協(xié)議可能適用的應(yīng)用場(chǎng)景. 此外, Dong-Loukides 協(xié)議的離線預(yù)計(jì)算依賴于具體的數(shù)據(jù)集,而我們所調(diào)用的Silent-OT 協(xié)議[18]不依賴于任何具體的數(shù)據(jù)集, 因此它具有更廣的應(yīng)用場(chǎng)景.

表1 理論對(duì)比Table 1 Theoretical comparison

4.2 實(shí)驗(yàn)評(píng)估

我們分別對(duì)三個(gè)協(xié)議做了實(shí)現(xiàn)(https://github.com/athenKing/PSU-PSI-CA) 來(lái)對(duì)比他們具體的性能表現(xiàn), 三個(gè)協(xié)議都通過(guò)C++ 完成實(shí)現(xiàn), 進(jìn)行測(cè)試的平臺(tái)搭載了2.9 GHz double core Intel-core I5 處理器和16 GB 1867 MHz DDR3 內(nèi)存. 該測(cè)試在LAN 網(wǎng)絡(luò)環(huán)境下完成, 網(wǎng)絡(luò)時(shí)延較低. 在Dong-Loukides協(xié)議的實(shí)現(xiàn)中, 設(shè)置安全參數(shù)λ = 128, 設(shè)置獨(dú)立哈希函數(shù)的個(gè)數(shù)k2為4096, 輸出的Flajolet-Martin 概要[16]長(zhǎng)度設(shè)置為32 (其理論上能統(tǒng)計(jì)至多232?1 個(gè)元素). 協(xié)議#1 和協(xié)議#2 的實(shí)現(xiàn)中, 同樣設(shè)置安全參數(shù)λ=128, 布隆過(guò)濾器的錯(cuò)誤率設(shè)為r =0.05, 三組數(shù)據(jù)(從小到大) 對(duì)應(yīng)的布隆過(guò)濾器最大容量分別設(shè)為5000, 50 000, 400 000. 表2 展示了它們?cè)诓煌瑪?shù)量級(jí)輸入下的實(shí)際性能比較結(jié)果. 其中Nx和Ny表示輸入的兩個(gè)集合的大小, PSU/PSI-CA 誤差(%) 表示輸出結(jié)果的相對(duì)誤差, 即兩個(gè)集合并集和交集基數(shù)輸出結(jié)果相對(duì)真實(shí)結(jié)果的誤差. DL 協(xié)議表示Dong-Loukides 協(xié)議.

表2 實(shí)驗(yàn)對(duì)比Table 2 Experimental comparision

由表2 的實(shí)驗(yàn)結(jié)果可知, Dong-Loukides 協(xié)議的預(yù)處理階段比較耗時(shí), 因此它不適合數(shù)據(jù)集更新頻繁的場(chǎng)景, 只適用于某些數(shù)據(jù)永久或半永久化存儲(chǔ)場(chǎng)景下的安全計(jì)算. 可以看到, 無(wú)論數(shù)據(jù)集的大小, 相比Dong-Loukides 協(xié)議協(xié)議#1 和協(xié)議#2 的總耗時(shí)都更小, 而且當(dāng)數(shù)據(jù)集的輸入從小變大時(shí), 這種性能優(yōu)勢(shì)也越來(lái)越明顯. 所以, 我們的協(xié)議在數(shù)據(jù)集更新頻繁的計(jì)算場(chǎng)景中有比Dong-Loukides 協(xié)議更高的計(jì)算效率.

5 總結(jié)與展望

本文提出一種新的解決PSU/PSI-CA 問(wèn)題的不完美計(jì)算協(xié)議, 并在半誠(chéng)實(shí)模型下證明了它的安全性.它使用布隆過(guò)濾器對(duì)集合預(yù)處理, 并混合了OT 預(yù)處理[17]和Paillier 同態(tài)加密技術(shù)[23]. 同最先進(jìn)的協(xié)議之一Dong-Loukides 協(xié)議相比, 該協(xié)議總耗時(shí)更低, 并且有較廣泛的應(yīng)用場(chǎng)景.

我們的協(xié)議不能抵抗惡意的敵手, 因此下一步, 通過(guò)結(jié)合當(dāng)前方案和零知識(shí)證明[27]的技巧, 我們會(huì)嘗試構(gòu)建一個(gè)高效的在惡意模型下[27]可證明安全的協(xié)議.