保護(hù)隱私的集合相似性度量協(xié)同計算協(xié)議

逯紹鋒，胡玉龍，逯躍鋒

(1.東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，遼寧 沈陽 110189；2.中國交通通信信息中心，北京 100011；3.山東理工大學(xué) 建筑工程學(xué)院，山東 淄博 255049；4.中國科學(xué)院 地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國家重點(diǎn)實驗室，北京 100101)

0 引 言

機(jī)器學(xué)習(xí)(Machine Learning，ML)作為一種實現(xiàn)人工智能的方法，主要是通過算法來解析數(shù)據(jù)，不斷學(xué)習(xí)，進(jìn)而對事物做出判斷和預(yù)測[1]。機(jī)器學(xué)習(xí)廣泛應(yīng)用于計算機(jī)視覺、語音識別和自然語言處理等領(lǐng)域，是近些年學(xué)術(shù)研究上的重要方向。然而，蓬勃發(fā)展的機(jī)器學(xué)習(xí)技術(shù)在給人們帶來便利的同時，也使數(shù)據(jù)安全與隱私面臨更加嚴(yán)峻的挑戰(zhàn)[2]。目前，研究人員提出了許多解決機(jī)器學(xué)習(xí)中的隱私問題的方法[3-6]。

解決隱私保護(hù)的安全多方計算(Secure Multi- party Computation，SMC)由Yao在文獻(xiàn)[7]中首先提出。在安全多方計算中，參與方將各自的隱私數(shù)據(jù)輸入到一個約定函數(shù)進(jìn)行協(xié)同計算，可以實現(xiàn)保證參與方的原始隱私數(shù)據(jù)不被泄露的同時，輸出正確計算結(jié)果[8]。SMC作為近年來密碼學(xué)界的研究熱點(diǎn)，被認(rèn)為是解決協(xié)同計算問題中保護(hù)數(shù)據(jù)信息隱私的一項核心技術(shù)[9-10]。利用SMC來實現(xiàn)保護(hù)隱私的機(jī)器學(xué)習(xí)由Goldwasser在CRYPTO2018上提出[11]，可以在機(jī)器學(xué)習(xí)的明文架構(gòu)中引入安全多方計算技術(shù)實現(xiàn)隱私保護(hù)。

在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域，一般都是通過計算樣本間的距離來完成對樣本數(shù)據(jù)的相似性度量[1]。采用什么樣的方法來計算兩者間距離，需要根據(jù)實際進(jìn)行選擇，計算結(jié)果直接影響到匹配的準(zhǔn)確與否。比如采用歐氏距離計算兩者之間的空間距離，使用漢明距離來度量兩個文本或者圖像之間的差異，使用杰卡德距離(Jaccard distance)來度量兩個集合之間的相似程度等[12]。文獻(xiàn)[13]對DNA序列進(jìn)行0-1編碼，以GM加密方案為主要工具，通過計算兩序列的漢明距離的隱私保護(hù)方法，解決了保護(hù)隱私的DNA序列比較問題。保密的集合計算是安全多方計算的一個重要方向，文獻(xiàn)[14]針對參與者集合為有限集合子集的問題，根據(jù)Diffie-Hellman的密鑰分配方案基于離散對數(shù)困難性，給出一個具體的適用于有限集合子集的交集計算協(xié)議。文獻(xiàn)[15]針對惡意模型下多方集合交集基數(shù)計算問題，提出了一個有效的計算協(xié)議。文獻(xiàn)[16]通過對任意有理數(shù)進(jìn)行特殊的編碼，將有理數(shù)域上元素與集合關(guān)系問題轉(zhuǎn)化為整數(shù)范圍內(nèi)的向量內(nèi)積問題，以Paillier加密方案為主要工具，將兩方集合保密計算推廣到有理數(shù)領(lǐng)域。文獻(xiàn)[17]提出了計算集合運(yùn)算統(tǒng)計量的專用安全計算協(xié)議，可以在不泄露交集元素的情況下高效計算集合交集、并集及交集權(quán)值和等統(tǒng)計量，解決了隱私保護(hù)集合運(yùn)算解決方案單一性問題。盡管人們針對隱私保護(hù)集合及機(jī)器學(xué)習(xí)已經(jīng)研究并提出了一些安全多方計算解決方案[18]，但關(guān)于保護(hù)隱私的集合相似性度量問題，在當(dāng)前的文獻(xiàn)研究中尚未發(fā)現(xiàn)。該文嘗試通過解決杰卡德距離的安全多方計算問題，來進(jìn)一步解決關(guān)于集合相似度計算的隱私保護(hù)問題。

1 相關(guān)知識

1.1 半誠實模型下協(xié)議的安全性定義

Goldreich在文獻(xiàn)[19]中指出：半誠實模型中的參與者會誠實地執(zhí)行協(xié)議，但他們會根據(jù)自己在協(xié)議執(zhí)行過程中獲得的信息對其他參與者的秘密數(shù)據(jù)進(jìn)行推導(dǎo)，下面給出半誠實模型下的安全性模擬范例。

設(shè)分別持有秘密數(shù)據(jù)x和y的協(xié)同計算參與者A和B，一起執(zhí)行協(xié)議π，協(xié)同合作計算函數(shù)f(x,y)=(f1(x,y),f2(x,y))。協(xié)議執(zhí)行中參與計算雙方獲得信息序列為：

(1)

(2)

定義:在半誠實模型下，對于計算函數(shù)f的協(xié)議π，如果存在概率多項式時間算法S1與S2，使得：

(3)

(4)

1.2 杰卡德距離

在機(jī)器學(xué)習(xí)中估算不同樣本集合之間的相似性時，通常要計算樣本之間的相似度，將這一類集合之間相似度統(tǒng)稱為集合距離。其中，最常用到的集合距離就是杰卡德距離。實際上，杰卡德距離和杰卡德相似系數(shù)互補(bǔ)，是通過計算集合間的交集和并集的基數(shù)來完成對兩個集合的相似性衡量的一種集合距離。

杰卡德相似系數(shù)[12]實際就是兩個集合交集大小與并集大小的比值(見圖1)：

圖1 兩集合的杰卡德相似系數(shù)

(5)

杰卡德距離與杰卡德相似系數(shù)互補(bǔ)，其公式可推導(dǎo)如下：

(6)

由于集合容斥原理，|A∪B|=|A|+|B|-|A∩B|，因此杰卡德距離公式可以推演為如下公式：

(7)

1.3 異 或

異或是一種基于二進(jìn)制的位運(yùn)算，該文用符號⊕表示，其運(yùn)算法則是對運(yùn)算符兩側(cè)數(shù)的每一個二進(jìn)制位，同值取0，異值取1。如表1所示，可以得到異或運(yùn)算具有下面的性質(zhì)。

性質(zhì)1:對于一個數(shù)，存在與0異或值不變的恒等特性。

表1 異或運(yùn)算

性質(zhì)2:對于一個數(shù)，存在與自身異或值為零的歸零特性。

1.4 GM同態(tài)加密方案

GM同態(tài)加密方案是Goldwasser與Micali在文獻(xiàn)[20]中提出的一種概率加密方案。

系統(tǒng)建立。系統(tǒng)選取N=pq，其中p，q為兩個大素數(shù)，y為模N的非二次剩余。系統(tǒng)公鑰為(N,y)，私鑰為(p,q)。

解密過程。密文c

明文：

(8)

性質(zhì)3:GM加密方案具有異或同態(tài)性質(zhì)。

證明：設(shè)E是一個加密算法，c1=E(m1,r1)是對m1的加密，c2=E(m2,r2)是對m2的加密，若有c1c2=E(m1⊕m2,r)，其中r1，r2，r是隨機(jī)數(shù)，⊕表示異或，則稱E是一個異或同態(tài)加密算法。在Goldwasser-Micali方案中，令r1r2=r，則有：

gm1⊕m2(r1r2)2modN=gm1⊕m2r2modN

(9)

即有，E(m1)E(m2)=E(m1⊕m2,r)。因此，GM加密方案具有異或同態(tài)性質(zhì)[10,20]。

性質(zhì)4:GM加密方案具有自反性質(zhì)。

證明:根據(jù)前文所述異或運(yùn)算的性質(zhì)，對GM加密方案進(jìn)行異或同態(tài)操作時有：

gm1⊕m2⊕m2(r1r2)2modN=

gm1⊕0r2modN=gm1r2modN

(10)

即經(jīng)過兩次對同一密文的異或，可使得密文c1變成另一個密文c1c2c2，但不影響解密的明文m1。因此，由以上推理可得到:在GM加密方案中，異或具有自反性質(zhì)。

2 問題描述及轉(zhuǎn)化

集合距離計算是機(jī)器學(xué)習(xí)、人工智能等領(lǐng)域的一個基本問題，由于經(jīng)常會用到敏感信息，因此就不得不考慮參與計算各方數(shù)據(jù)的隱私問題。進(jìn)而研究如何在保證各參與方數(shù)據(jù)隱私的前提下進(jìn)行集合距離計算也變得十分必要，該文將保護(hù)隱私的集合距離問題描述如下：

問題描述：假設(shè)Alice輸入集合數(shù)據(jù)D1，Bob輸入集合數(shù)據(jù)D2，Alice和Bob想要共同協(xié)作計算出D1和D2兩個集合的相似度距離，同時又不泄露各自的元素數(shù)據(jù)信息。

問題轉(zhuǎn)化：為了更好地解決上述問題，該文采用如下稱之為位置編碼的方法，對參與計算的數(shù)據(jù)進(jìn)行處理。假設(shè)存在集合U={x1,x2,…,xi,…,xn}，i∈[1,n]為一個全集，|U|=n。Alice擁有集合D1={a1,a2,…,ai,…,an1}，其中ai∈U，Bob擁有集合D2={b1,b2,…,bj,…,bn2}，其中bj∈U，該文將集合元素按照以下規(guī)則先行進(jìn)行編碼:

(11)

下面以具體的例子來說明問題轉(zhuǎn)化過程。

例1：假設(shè)存在全集U={a,b,c,d,e,f,g,h,i,j,k,l}及兩個集合D1、D2，分別為：D1={f,a,c,e}、D2={f,a,c,i,l}。對集合D1按照前文規(guī)則(11)對其編碼，可得到新的編碼集合為A={6,1,3,5}，同樣，對集合D2編碼之后對應(yīng)的編碼集合為B={6,1,3,9,12}，如表2所示。

表2 對集合進(jìn)行位置編碼

計算原理說明：經(jīng)過分析發(fā)現(xiàn)，D1和D2兩個集合經(jīng)過位置編碼后，計算D1和D2兩個集合的相似性度量問題就轉(zhuǎn)化為求A和B兩集合的相同數(shù)字個數(shù)問題。

該文通過對轉(zhuǎn)化后的問題設(shè)計具體協(xié)議進(jìn)行解決，實現(xiàn)保護(hù)隱私的集合相似性度量協(xié)同計算。對編碼后的兩集合中的數(shù)字先進(jìn)行逐位異或運(yùn)算，再根據(jù)異或運(yùn)算的歸零率特性，一個數(shù)與它本身進(jìn)行異或運(yùn)算等于零，否則為非零，求出兩個集合異或運(yùn)算后新的集合中的零的個數(shù)，即可求出A和B兩集合相似性度量值，對基數(shù)較小集合，不足部分補(bǔ)零。例如，在上述例1中兩個集合D1和D2經(jīng)過位置編碼后，再進(jìn)行逐位異或運(yùn)算的結(jié)果為：C={0,0,0,1,1}，結(jié)果集中0的個數(shù)為3，從而可知D1和D2兩個集合的相似性距離值為1/2。

3 具體協(xié)議

協(xié)議1：保護(hù)隱私的集合杰卡德距離協(xié)同計算協(xié)議。

輸入：Alice和Bob分別輸入私密的集合：

D1={a1,a2,…,ai,…,an1}，D2={b1,b2,…,bj,…,bn2}，其中ai∈U，bj∈U，U為包含集合的全集。

輸出：兩集合的杰卡德距離Jd。

(2)Bob生成自己的GM加密系統(tǒng)的公鑰為PK=(δ,n)，私鑰為SK=(p,q)。

(3)Alice將收到的E(A)和E(B)兩兩相乘，并進(jìn)行同態(tài)操作：

C=E(A)E(B)=

E(A⊕B)=

{E(c1),E(c2),…,E(cm)}

(4)Alice選取隨機(jī)置換T對上述結(jié)果進(jìn)行置換，得到隨機(jī)置換后的m個密文：

并將該密文發(fā)回給Bob。

(5)Alice計算自己集合的基數(shù)CA=|D1|，隨同之前E(A)一并發(fā)給Bob。

步驟3：(1)Bob收到置換后的m個密文后，進(jìn)行逐次解密，得到：

(3)Bob計算集合的大小值CB=|D2|，并完成兩集合的杰卡德相似性值計算。

(4)Bob將Jd值傳送給Alice。

分析：在協(xié)議1中，由于Bob發(fā)送給Alice的是自己對集合D2進(jìn)行位置編碼后的密文E(B)，其他合作計算方不能解密，因此也不能從中得到集合D2的隱私信息。另一方面，Alice將自己的集合D1進(jìn)行位置編碼并加密后獲得E(A)，兩者相乘后得到E(A)E(B)=E(A⊕B)，若直接將計算結(jié)果傳給Bob，由于Bob可以解密得到A⊕B，在這個基礎(chǔ)上，Bob就可以通過加密機(jī)制的自反特性A⊕B⊕B得到A，從而得到Alice的隱私集合D1的信息。因此，為了防止這種隱私泄露，Alice將E(A⊕B)隨機(jī)置換得到(E(A⊕B))T，這樣使得Bob解密后只能得到(A⊕B)T，由于置換函數(shù)為Alice獨(dú)自掌握，因此Bob無法從中獲取到A的信息，從而Alice保護(hù)了自己的隱私。

4 協(xié)議分析

4.1 正確性分析

根據(jù)GM的同態(tài)加密方案的異或同態(tài)性，任何數(shù)字對自身進(jìn)行異或結(jié)果為零。并且在協(xié)議第3步雖然進(jìn)行了置換，但置換前后集合中零的總數(shù)是不變的，即：

(12)

由于CA=|D1|、CB=|D2|的值不變，因此所得Jd的值即為兩集合的杰卡德距離值。協(xié)議1是正確的。

4.2 安全性分析

定理1：協(xié)議1能夠保密地協(xié)同計算出兩集合的杰卡德距離值。

證明：下面用模擬范例的方法來嚴(yán)格證明協(xié)議的安全性。

首先，構(gòu)造模擬器S1，令f1(A,B)=f2(A,B) =Jd(A,B)，并將(A,f1(A,B))輸入S1。

具體步驟如下：

第2步：S1將集合D1進(jìn)行位置編碼得到：

然后，再逐位加密，得到n長密文：

然后將收到的E(B')和E(A')兩兩相乘，并進(jìn)行同態(tài)操作：

C=E(A')E(B')=

E(A'⊕B')={E(c1),E(c2),…,E(cn)}

S1選取隨機(jī)置換T對上述結(jié)果進(jìn)行置換，得到隨機(jī)置換后的n個密文：

第3步：將此n個密文逐次解密得到：

即兩集合的杰卡德距離值：

在本協(xié)議中，

E(B')。

又因為E(C)=(E(A)E(B))T，E(C')=(E(A)E(B'))T，且隨機(jī)置換為同一置換T，從而可知：

因此可得：

同理，用類似的方法可以構(gòu)造模擬器S2，使得：

因此，協(xié)議1可以保密地協(xié)同計算出兩集合的杰卡德距離值。

4.3 計算與通信復(fù)雜性分析

計算復(fù)雜性。文中協(xié)議借助GM同態(tài)加密方案來解決問題，計算開銷主要來自于模乘運(yùn)算，因此以模乘運(yùn)算次數(shù)作為衡量指標(biāo)。在協(xié)議1中，Alice執(zhí)行加密m次，Bob執(zhí)行加密、解密各m次，由GM同態(tài)加密方案可知，加密一次需要2次模乘運(yùn)算，解密一次需要logp(p為GM同態(tài)加密方案中的大素數(shù)私鑰)次模乘運(yùn)算，而m≤n，因此協(xié)議1最多需進(jìn)行4n+nlogp次模乘運(yùn)算。

通信復(fù)雜性。一般用協(xié)議交換信息的比特數(shù)或者通信輪數(shù)作為衡量通信復(fù)雜度指標(biāo),在安全多方計算中通常用輪數(shù)[10]。在協(xié)議1中，計算雙方共需進(jìn)行兩輪通信。

文獻(xiàn)[13]基于GM同態(tài)方案解決漢明距離，經(jīng)過改造后也可用于計算集合相似度，但文中協(xié)議要對數(shù)據(jù)長度進(jìn)行擴(kuò)展，因此協(xié)議雙方計算共需要做4n(4+logp)模乘運(yùn)算，但協(xié)議同樣需要2輪通信。

文獻(xiàn)[14]提出協(xié)議4經(jīng)過變形后可保密計算兩個集合交集的基數(shù)，用于集合相似度評價。該協(xié)議是借助Diffie-Hellman的密鑰分配方案設(shè)計的解決方案，協(xié)議中計算雙方共需要做4n次模乘運(yùn)算，進(jìn)行3輪通信。

協(xié)議效率分析比較如表3所示。

表3 協(xié)議效率分析比較

5 文中協(xié)議應(yīng)用推廣

從協(xié)議1可以看出，協(xié)同計算的核心是求解參與計算的兩個集合的交集的基數(shù)，通過對協(xié)議1的必要改造后，可以構(gòu)建其他類似的保護(hù)隱私的相似性度量協(xié)同計算協(xié)議，完成對Dice系數(shù)、Tversky系數(shù)、集合余弦相似性的計算。

Dice系數(shù)最初是被用來定量表達(dá)兩個不同物種在自然界中的關(guān)聯(lián)程度[21]，作為一種集合相似度度量函數(shù)，如今被廣泛應(yīng)用于深度學(xué)習(xí)圖像分割和目標(biāo)檢測中。其公式含義可解讀為真實數(shù)據(jù)集和預(yù)測數(shù)據(jù)集中的正確部分之和占兩者之和的比例，具體公式如下所示：

(13)

Tversky系數(shù)是由Tversky等在文獻(xiàn)[22]中提出的用于特征相似性測度的函數(shù)，杰卡德系數(shù)和Dice系數(shù)均是Tversky系數(shù)的參數(shù)取特定值時的一種表達(dá)。

(14)

余弦距離和余弦相似度互補(bǔ)，集合的余弦距離是通過計算兩集合夾角的余弦值作為衡量兩個集合之間的相似性的一種方法[12]，具體公式如下：

(15)

事實上對于文本相似性也可以借助shingling算法將文檔轉(zhuǎn)化為集合，再借助文中協(xié)議進(jìn)行保密協(xié)同計算出其相似性[23]。對于海量數(shù)據(jù)，可以借助最小哈希和局部敏感哈希[24]尋找相似集合的算法實現(xiàn)數(shù)據(jù)的相似性度量保密協(xié)同計算。

6 結(jié)束語

集合相似性度量問題是機(jī)器學(xué)習(xí)領(lǐng)域的基本問題之一，在能夠保護(hù)隱私的前提下計算兩集合對象間的相似性距離值是密碼學(xué)中一個新的問題，在機(jī)器學(xué)習(xí)、圖形識別、人工智能、生物信息學(xué)等方面有著重要的應(yīng)用。該文設(shè)計了一種新的編碼方法，將相似性度量問題轉(zhuǎn)化為計算兩集合相同數(shù)字個數(shù)的問題，使集合相似性度量距離計算問題普適化，并結(jié)合異或的思想，借助同態(tài)加密算法來解決杰卡德距離計算的隱私保護(hù)問題。然后，用模擬器證明了該協(xié)議是安全的，并分析了協(xié)議可以高效安全地計算兩集合對象間的杰卡德距離。最后，將問題擴(kuò)展至其他方面，證明該協(xié)議具備一定的普適性，經(jīng)過必要的改造后可以解決保密計算Dice系數(shù)、Tversky系數(shù)、集合余弦相似性等問題。由于該協(xié)議仍是基于半誠實模型，惡意模型下的保護(hù)隱私的集合相似性度量協(xié)同計算問題將是后續(xù)研究的方向。