惡意模型下漢明距離的保密計算

劉 新,涂小芬,胡翔瑜,徐 剛,陳秀波,劉曉夢

(1.內蒙古科技大學 信息工程學院,內蒙古 包頭 014010;2.北京郵電大學 網絡與交換技術全國重點實驗室,北京 100876;3.北方工業大學 信息學院,北京 100144)

0 引 言

漢明距離[1]是指2個長度相等的序列X和Y之間同一位置元素不相等的數量,記為HMD(X,Y)。漢明距離在數據相似度計算、誤差檢測、數據清洗和文字查重等方面具有廣泛應用[2]。如何在保護數據隱私的情況下,保密地計算字符串的漢明距離,成為亟待解決的問題。

安全多方計算由Yao[3]等提出,隨后Goldreich[4]、Cramer[5]等對其提出了系統的論述。針對安全多方計算的研究包括保密數據挖掘[6-7]、保密的計算幾何和集合問題[8]、保密的科學計算[9]等。這些研究推動了安全多方計算的發展,解決了許多實際問題[10-11]。

目前,漢明距離的安全計算協議并不多見,僅有的協議均是在半誠實模型下提出的。文獻[12]中將漢明距離轉換為集合相交問題,保密地計算2個集合的交集基數。文獻[13]以此基礎,利用高德瓦瑟-米卡列(GM)加密算法[14]在半誠實模型下設計了保密計算2個序列漢明距離的安全協議。但以上兩協議的計算效率較低,本文在此基礎上進行改進,利用橢圓曲線加密算法[15],設計了半誠實模型下保密計算漢明距離的安全協議,提升了協議計算效率,并用模擬范例證明了協議的安全性。

以上協議均在半誠實模型下完成計算,但參與者有可能是惡意的,所以半誠實模型下的協議有一定的局限性。因此,需要設計惡意模型下的安全多方計算協議來抵抗惡意敵手的攻擊行為[16]。

本文定義了0-1編碼規則,將字母字符串采用二進制編碼方式進行編碼后計算漢明距離,在分析了半誠實模型下保密計算漢明距離協議中可能存在的惡意行為基礎上,利用零知識證明和分割-選擇方法,設計了惡意模型下的安全計算協議,并利用理想-實際范例[16]證明了協議的安全性,同時分析了惡意敵手攻擊成功的概率。

1 相關知識

根據安全多方計算中惡意模型的安全性定義,設計0-1編碼規則,本文提出惡意模型下漢明距離的安全計算協議。因此,本部分對相關知識進行介紹。

1.1 漢明距離

在信息論中,漢明距離表示2個長度相等字符串中,同一位置上元素不相等的數量,例如“gyda”與“uyga”之間的漢明距離為2。在海量數據對比過程中,漢明距離可以反映數據之間的相似程度,以解決數據分類、數據篩選、數據重復等問題。在通信編碼中,漢明距離可表達一個字符串轉化為另一個字符串所需的轉變次數,用于編碼體系中的糾錯、驗錯。在二進制中,a和b的漢明距離等于a⊕b結果中“1”的個數,例如“1010010”與“0110110”之間的漢明距離是3。

1.2 0-1編碼規則

本文的2個協議中均需要將明文編碼為二進制數,針對不同明文采用不同的二進制編碼方式,能有效減少編碼后明文的長度。對于少量固定幾個字符序列的明文,往往采用一一對應的方式進行0-1編碼,例如文獻[13]中把脫氧核糖核酸(DNA)序列編碼為二進制時,將A編為1000、C編為0100、G編為0010、T編為0001。對于具有26個英文字母字符串的二進制編碼方式,往往采用將字母和空格一一對應轉變為十進制,然后將十進制轉變為二進制(5比特)的方式進行編碼,編碼如表1所示。

1.3 惡意模型的安全性定義

安全多方計算的參與者主要分為半誠實的和惡意的參與者[16]。半誠實參與者按照協議規則忠誠地執行協議,在執行過程中不會中途停止或提供虛假信息,但是他們可能會記錄中間計算結果和最終結果,嘗試推導其余參與者的信息。惡意參與者在執行協議過程中不遵守協議規則,可能篡改中間數據或終止協議等(不考慮提供虛假輸入信息的情況,因為在理想模型協議中也無法避免這一情況)。惡意模型的安全性定義[16]如下。

表1 字母轉化二進制列表Tab.1 Letter conversion binary list

惡意模型的安全性證明過程需要借助擁有可信第三方的理想協議來完成,由于理想協議是最安全的協議,如果設計的實際協議(惡意模型下)與理想協議具有相同的安全性,即可說明協議在惡意模型下是安全的。

1)理想協議。假設Alice和Bob擁有數據x和y,他們借助可信第三方(trusted third party,TTP)執行函數f(x,y)=(f1(x,y),f2(x,y))后,各自可得到結果f1(x,y)和f2(x,y),同時不會泄漏自己的數據x和y。如果Alice為惡意參與者,在收到數據f1(x,y)后終止協議,這種情況下TTP給Bob發送終止符號⊥,否則將f2(x,y)發送給Bob。

如果Alice是誠實的,那么

γ(x,y,z,r)=(f1(x,y′),B2(y,z,r,f2(x,y′)))

(1)

(1)式中,y′=B2(y,z,r)。

如果Bob是誠實的,那么

γ(x,y,z,r)=

(2)

在2種情況下x′=B1(x,z,r)。

定義1惡意模型的安全性。

(3)

那么,協議Π安全計算F,其中,x,y,z∈{0,1}*使得|x|=|y|并且|z|=poly(|x|)。

2 半誠實模型下漢明距離的保密計算

問題描述。假設Steven和Tom將自己的信息按照“0-1編碼規則”都編碼為一條長度為l的0-1字符串X=(a1,a2,…,al)和Y=(b1,b2,…,bl),Steven和Tom保密計算字符串X和Y的漢明距離HMD(X,Y)。具體協議如下。

協議1半誠實模型下保密計算漢明距離。

輸入:Steven的字符串X=(a1,a2,…,al),Tom的字符串Y=(b1,b2,…,bl);

輸出:HMD(X,Y)。

準備階段。利用橢圓曲線加密算法,選擇生成元為G,Steven選擇私鑰k,然后計算k·G=K得到公鑰K,將公鑰(K,G)發送給Tom。

步驟1Steven選擇l個隨機數ri,其中,i=1,2,…l,利用ri和K依次加密字符串X上的所有字符,得到長度為l加密向量Er(X)=(Er1(a1),…,Eri(ai),…,Erl(al)),加密過程如下

(4)

然后計算每個密文Er(ai)對應的標識符Ci=ri·G,最后將長度為l的加密向量Er(X)和l個標識符Ci發送給Tom,即(Er(X),Ci)。

步驟2Tom收到(Er(X),Ci)后,執行以下步驟。

步驟2.1:選擇l個隨機數si,其中,i=1,2,…l,利用隨機數si和Steven的公鑰K逐比特加密字符串Y上的每一個元素,得到長度為l的加密向量Es(Y)=(Es1(b1),Es2(b2),…,Esl(bl)),加密過程如下

(5)

T(Er(X)+Es(Y))=(Er(aT(1))+Es(bT(1)),

Er(aT(2))+Es(bT(2)),…,Er(aT(l))+Es(bT(l)))

(6)

步驟4Steven將計算結果Sum告知Tom。

協議1結束。

執行協議1過程中,參與者可能存在惡意行為,因此,需要對可能出現的惡意行為進行分析,并提出相應的解決方案。

3 惡意模型下漢明距離的保密計算

解決思路:基于半誠實模型協議1下可能存在的惡意行為,來設計抗惡意敵手的漢明距離保密計算協議2。但是,對于在理想協議中都無法阻止的惡意行為,惡意模型下的安全協議同樣也無法阻止,因此也不予考慮,包括:①一方不參加協議;②任意一方輸入虛假的數據;③一方突然終止執行協議。

分析協議1中可能出現以下惡意行為。

1)在協議1中,Steven擁有公私鑰,而Tom只有公鑰,不能解密,對于Tom來說不公平。解決思路是需要雙方都具有公私鑰,最終可以同時得到正確的計算結果,避免不公平性。

2)在Steven或Tom加密自己的數據時,執行過程中一方可能提供虛假的密文,從而導致結果錯誤。解決思路是利用分割-選擇(cut-choose)方法來驗證密文的正確性,但依然可能成功欺騙,但成功欺騙的概率隨著引入隨機數的增加而趨近于零。

3)Steven或Tom在協議1的步驟4中發送錯誤的數據給對方,使其無法計算出正確的結果。解決思路是在協議1中加入零知識證明,使得Steven和Tom可以驗證數據的正確性。

3.1 具體協議

Steven和Tom各自選取公私鑰,同時執行協議,但最后不用將結果HMD(X,Y)告知對方,而是各自將結果編碼到橢圓曲線上,Steven得到點M1,Tom得到點M2。由于惡意模型下對方可能存在惡意行為,所以Steven和Tom需要對比M1和M2是否相等,若相等則計算結果正確,否則對方是惡意的。

協議2:惡意模型下保密計算漢明距離。

輸入:Steven的字符串X=(a1,a2,…,al),Tom的字符串Y=(b1,b2,…,bl);

輸出:HMD(X,Y)。

準備階段。參與雙方共同選擇橢圓曲線加密算法生成元G,Steven和Tom分別選擇自己的私鑰k1和k2,并計算公鑰K1=k1·G和K2=k2·G。Steven和Tom分別保密選擇隨機數s和t,并計算u=s·K1和v=t·K2,雙方交換(K1,G,u)和(K2,G,v)。Steven和Tom各自執行到協議1的前3步后,將得到的結果編碼為M1和M2,執行以下步驟。

(7)

(8)

Steven計算公式為

a·(M2-M1)+a·t·G,P1=p1·G,λt=

p1·K2

(9)

Tom計算公式為

b·(M1-M2)+b·s·G,P2=

p2·G,λs=p2·K1

(10)

Steven和Tom將ct+P1和cs+P2發送給對方。

步驟5Steven計算ωs=k1·(cs+P2)發送給Tom,Tom計算ωt=k2·(ct+P1)發送給Steven。

步驟6Steven和Tom此時再將ct和cs發送給對方。

步驟7Steven計算ms=k1·cs發送給Tom,Tom計算mt=k2·ct發送給Steven。

步驟8Steven收到mt后利用零知識證明驗證數據的真實性,即證明(mt=ωt-λt)是否成立。Tom收到ms后利用零知識證明驗證數據的真實性,即證明(ms=ωs-λs)是否成立。若沒有通過驗證,則說明對方是惡意參與者。

步驟9若雙方都通過驗證,則Tom計算ms-b·u得到k1·b·(M1-M2),從而判斷M1和M2是否相等,若相等則計算結果正確。Steven通過計算mt-a·v得到k2·a·(M2-M1),從而判斷M1和M2是否相等,若相等則計算結果正確。

協議2結束。

3.2 正確性分析

1)Steven利用零知識證明驗證Tom發送的mt,通過計算mt-a·v得到的結果是正確的,過程如下

mt-a·v=mt-a·t·K2=

k2·ct-a·t·k2·G=

k2·a(M2-M1)+k2·a·t·G-a·t·k2·G=

k2·a(M2-M1)

(11)

Tom利用零知識證明驗證Steven發送的ms,通過計算ms-b·u得到的結果是正確的,過程如下

ms-b·u=ms-b·s·K1=

k1·cs-b·s·k1·G=

k1·b(M1-M2)+k1·b·s·G-b·s·k1·G=

k1·b(M1-M2)

(12)

2)在協議2的步驟8中零知識證明是正確的。由于Steven和Tom雙方過程對稱,所以只需要證明一方即可,這里假設Steven驗證Tom發送的mt是正確的,即驗證mt確實是用Tom的私鑰k2與ct相乘得到的,分析如下。

3.3 安全性證明

需要分析協議2中Steven和Tom能否利用雙方公布的數據,破解對方的輸入數據或者提前得到輸出結果。

2)在協議2的步驟6中,Steven和Tom發送加密數據ct和cs給對方后,因為Steven不知道cs=b·(M1-M2)+b·s·G中Tom選取的隨機數b,所以無法計算出數據b·(M1-M2)來提前得到輸出結果。同樣,因為Tom不知道ct=a·(M2-M1)+a·t·G中Steven選取的隨機數a,所以無法計算出數據a·(M2-M1)來提前得到輸出結果。

3)在協議2中雙方唯一可以達成欺騙的行為是在協議2的步驟1時提供虛假的密文,即在cut-choose時通過了驗證,而對方在協議2的步驟4中剛好又選中了錯誤的加密數據,這樣對方就無法得到正確的結論,但欺騙方也無法通過提供錯誤的密文來得到對方的輸入,也無法提前得到輸出結果。下面分析達成欺騙的概率(Steven與Tom的概率相同)。

安全性證明采用理想-實際范例,即,對比模擬執行理想協議和實際協議2,若2個協議在計算上不可區分,即可證明協議2的安全性。

定理2惡意模型下的保密計算漢明距離協議2(記作Π)是安全的。

1)在理想模型中,B1模擬誠實的A1執行協議,給TTP發送正確的M1,且收到消息后一定會給發送消息B2。不誠實的B2調用A2來執行協議。B2把M2發送給A2,然后獲取執行協議時A2使用的數據A2(M2)。B2向TTP發送A2(M2),然后獲取數據F(M1,A2(M2)),同時B1也需要得到F(M1,A2(M2)))。

步驟2B2公布協議2的步驟2中A2要求A1公布的消息。

在理想模型中,B2嚴格執行協議Π并輸出。B1接受輸入M1并調用A1,獲取A1實際執行Π時發送的消息A1(M1)。B1將A1(M1)發送給TTP后獲取F(A1(M1),M2)。若實際協議中A1在第7步發送了解密的結果,并在第8步完了驗證,則B1告知TTP發送結果F(A1(M1),M2)給B2;若實際協議中A1在第7步終止協議,或在第8步無法完成驗證,則B1告知TTP給B2發送⊥。

因此,協議2在惡意模型下是安全的。

4 性能分析

本文通過效率分析和實驗仿真對協議性能進行分析,具體如下。

4.1 效率分析

1)協議1效率分析:協議1與文獻[12]、[13]進行比較,假設0-1字符串長度均為l。文獻[12]、[13]均采用GM加密算法,模數為N,文獻[12]計算復雜度為4l次模指數運算,通信復雜度為1輪。文獻[13]計算復雜度為3l次加解密運算和l次模N乘法運算,共需要7l次模指數運算,通信復雜度為1輪。本文的協議1中采用橢圓曲線加密算法,計算復雜度為15l次乘法運算,通信復雜度為1輪。

2)協議2效率分析:目前尚未發現惡意模型下漢明距離安全計算協議的提出。雖然文獻[16]是針對百萬富翁問題提出的惡意模型安全協議,與本文應用場景不同,但是其中的數據相等判斷協議與本文協議2中比較兩個漢明距離是否相等問題基本一致,因此,協議2與文獻[16]進行比較。假設都加密m組密文。在計算復雜度上,文獻[16]中采用Paillier加密算法,雙方各自加密密文需要2m次模指數運算,驗證時需要m/2次模指數運算,其余需要6次模指數運算,一個參與者需要2.5m+6次模指數運算,則整個協議計算復雜度為5m+12次模指數運算。本文協議2利用橢圓曲線加密算法,雙方各自加密密文時只需要m次乘法運算,驗證階段不需要用到橢圓曲線上的乘法運算,其余只需要7次乘法運算,整個協議計算復雜度為30l+2m+14次乘法運算。在通信復雜度上,文獻[16]通信復雜度為3輪,協議2需要4輪。

本文協議1和協議2與文獻[12]、[13]和[16]進行對比,如表2所示。

在計算復雜度上,本文的協議1和協議2采用橢圓曲線加密算法,相比于GM加密算法和Paillier加密算法的模指數運算,橢圓曲線的乘法運算計算量較低。在通信復雜度上,協議2與文獻[16]的通信輪數有所增加,但均能抵抗惡意敵手的攻擊。協議2相比文獻[16]僅增加了1輪交互,通信效率并無顯著降低。

表2 方案對比Tab.2 Scheme comparison

4.2 實驗仿真

為了驗證協議的計算效率,本文利用Python語言進行模擬實驗,采用配置為Intel Core i5-8400 CPU,8 GByte DDR4內存,512 GByte SSD硬盤的電腦運行實驗。實驗中橢圓曲線采用secp256k1曲線,惡意模型下m取20,l取10,模擬不同密鑰長度下實驗1 000次協議所用時間取平均值,如圖1所示。

圖1 效率對比Fig.1 Efficiency comparison

實驗結果表明,本文采用橢圓曲線加密設計的協議1和協議2,在協議執行效率上較文獻[12]、[13]和[16]有所提升。惡意模型下的文獻[16]與半誠實模型下的協議1、文獻[12]、[13]相比,惡意模型下的協議需要花費更多計算時間,但本文惡意模型下的協議2相比于半誠實模型下的文獻[12]、[13],計算時間更短。從圖1可以看出,隨著密鑰長度的增長,執行時間都有所增加,相比而言,協議1和協議2執行時間增加緩慢,且斜率相比而言增加較為平緩,是因為橢圓曲線加密數據僅使用乘法運算,而同級別下的GM、Paillier加密算法中使用的是模指數運算,因此,橢圓曲線加密算法具有耗時短、存儲空間低等優點。

因為惡意模型下的安全多方計算協議需要使用cut-choose和零知識證明等方法,所以協議執行時間一般高于相同輸入長度的半誠實模型下的協議,但可以采用云服務外包計算等方式來降低惡意模型下的計算開銷。

5 結束語

保密計算漢明距離具有廣泛的應用場景,現有安全多方計算協議大多是在半誠實模型下設計的,當有惡意敵手存在的情況下是不安全的。本文針對字母字符串進行0-1編碼,利用橢圓曲線加密算法,首先設計了半誠實模型下保密計算漢明距離的協議,在此基礎上分析惡意敵手可能的攻擊行為,設計了惡意模型下保密計算漢明距離協議。惡意模型下的協議利用cut-choose和零知識證明方法,可以阻止或發現惡意行為,最后分析了協議的計算效率和通信效率,并進行了實驗對比。本文構造的惡意模型協議更具有實用價值,為保密計算漢明距離提供了高效的解決方案。