惡意模型下漢明距離的保密計(jì)算

劉 新,涂小芬,胡翔瑜,徐 剛,陳秀波,劉曉夢(mèng)

(1.內(nèi)蒙古科技大學(xué) 信息工程學(xué)院,內(nèi)蒙古 包頭 014010;2.北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)全國(guó)重點(diǎn)實(shí)驗(yàn)室,北京 100876;3.北方工業(yè)大學(xué) 信息學(xué)院,北京 100144)

0 引 言

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

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

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

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

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

1 相關(guān)知識(shí)

根據(jù)安全多方計(jì)算中惡意模型的安全性定義,設(shè)計(jì)0-1編碼規(guī)則,本文提出惡意模型下漢明距離的安全計(jì)算協(xié)議。因此,本部分對(duì)相關(guān)知識(shí)進(jìn)行介紹。

1.1 漢明距離

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

1.2 0-1編碼規(guī)則

本文的2個(gè)協(xié)議中均需要將明文編碼為二進(jìn)制數(shù),針對(duì)不同明文采用不同的二進(jìn)制編碼方式,能有效減少編碼后明文的長(zhǎng)度。對(duì)于少量固定幾個(gè)字符序列的明文,往往采用一一對(duì)應(yīng)的方式進(jìn)行0-1編碼,例如文獻(xiàn)[13]中把脫氧核糖核酸(DNA)序列編碼為二進(jìn)制時(shí),將A編為1000、C編為0100、G編為0010、T編為0001。對(duì)于具有26個(gè)英文字母字符串的二進(jìn)制編碼方式,往往采用將字母和空格一一對(duì)應(yīng)轉(zhuǎn)變?yōu)槭M(jìn)制,然后將十進(jìn)制轉(zhuǎn)變?yōu)槎M(jìn)制(5比特)的方式進(jìn)行編碼,編碼如表1所示。

1.3 惡意模型的安全性定義

安全多方計(jì)算的參與者主要分為半誠(chéng)實(shí)的和惡意的參與者[16]。半誠(chéng)實(shí)參與者按照協(xié)議規(guī)則忠誠(chéng)地執(zhí)行協(xié)議,在執(zhí)行過程中不會(huì)中途停止或提供虛假信息,但是他們可能會(huì)記錄中間計(jì)算結(jié)果和最終結(jié)果,嘗試推導(dǎo)其余參與者的信息。惡意參與者在執(zhí)行協(xié)議過程中不遵守協(xié)議規(guī)則,可能篡改中間數(shù)據(jù)或終止協(xié)議等(不考慮提供虛假輸入信息的情況,因?yàn)樵诶硐肽Ｐ蛥f(xié)議中也無法避免這一情況)。惡意模型的安全性定義[16]如下。

表1 字母轉(zhuǎn)化二進(jìn)制列表Tab.1 Letter conversion binary list

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

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

如果Alice是誠(chéng)實(shí)的,那么

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

(1)

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

如果Bob是誠(chéng)實(shí)的,那么

γ(x,y,z,r)=

(2)

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

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

(3)

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

2 半誠(chéng)實(shí)模型下漢明距離的保密計(jì)算

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

協(xié)議1半誠(chéng)實(shí)模型下保密計(jì)算漢明距離。

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

輸出:HMD(X,Y)。

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

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

(4)

然后計(jì)算每個(gè)密文Er(ai)對(duì)應(yīng)的標(biāo)識(shí)符Ci=ri·G,最后將長(zhǎng)度為l的加密向量Er(X)和l個(gè)標(biāo)識(shí)符Ci發(fā)送給Tom,即(Er(X),Ci)。

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

步驟2.1:選擇l個(gè)隨機(jī)數(shù)si,其中,i=1,2,…l,利用隨機(jī)數(shù)si和Steven的公鑰K逐比特加密字符串Y上的每一個(gè)元素,得到長(zhǎng)度為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將計(jì)算結(jié)果Sum告知Tom。

協(xié)議1結(jié)束。

執(zhí)行協(xié)議1過程中,參與者可能存在惡意行為,因此,需要對(duì)可能出現(xiàn)的惡意行為進(jìn)行分析,并提出相應(yīng)的解決方案。

3 惡意模型下漢明距離的保密計(jì)算

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

分析協(xié)議1中可能出現(xiàn)以下惡意行為。

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

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

3)Steven或Tom在協(xié)議1的步驟4中發(fā)送錯(cuò)誤的數(shù)據(jù)給對(duì)方,使其無法計(jì)算出正確的結(jié)果。解決思路是在協(xié)議1中加入零知識(shí)證明,使得Steven和Tom可以驗(yàn)證數(shù)據(jù)的正確性。

3.1 具體協(xié)議

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

協(xié)議2:惡意模型下保密計(jì)算漢明距離。

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

輸出:HMD(X,Y)。

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

(7)

(8)

Steven計(jì)算公式為

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

p1·K2

(9)

Tom計(jì)算公式為

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

p2·G,λs=p2·K1

(10)

Steven和Tom將ct+P1和cs+P2發(fā)送給對(duì)方。

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

步驟6Steven和Tom此時(shí)再將ct和cs發(fā)送給對(duì)方。

步驟7Steven計(jì)算ms=k1·cs發(fā)送給Tom,Tom計(jì)算mt=k2·ct發(fā)送給Steven。

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

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

協(xié)議2結(jié)束。

3.2 正確性分析

1)Steven利用零知識(shí)證明驗(yàn)證Tom發(fā)送的mt,通過計(jì)算mt-a·v得到的結(jié)果是正確的,過程如下

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利用零知識(shí)證明驗(yàn)證Steven發(fā)送的ms,通過計(jì)算ms-b·u得到的結(jié)果是正確的,過程如下

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)在協(xié)議2的步驟8中零知識(shí)證明是正確的。由于Steven和Tom雙方過程對(duì)稱,所以只需要證明一方即可,這里假設(shè)Steven驗(yàn)證Tom發(fā)送的mt是正確的,即驗(yàn)證mt確實(shí)是用Tom的私鑰k2與ct相乘得到的,分析如下。

3.3 安全性證明

需要分析協(xié)議2中Steven和Tom能否利用雙方公布的數(shù)據(jù),破解對(duì)方的輸入數(shù)據(jù)或者提前得到輸出結(jié)果。

2)在協(xié)議2的步驟6中,Steven和Tom發(fā)送加密數(shù)據(jù)ct和cs給對(duì)方后,因?yàn)镾teven不知道cs=b·(M1-M2)+b·s·G中Tom選取的隨機(jī)數(shù)b,所以無法計(jì)算出數(shù)據(jù)b·(M1-M2)來提前得到輸出結(jié)果。同樣,因?yàn)門om不知道ct=a·(M2-M1)+a·t·G中Steven選取的隨機(jī)數(shù)a,所以無法計(jì)算出數(shù)據(jù)a·(M2-M1)來提前得到輸出結(jié)果。

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

安全性證明采用理想-實(shí)際范例,即,對(duì)比模擬執(zhí)行理想?yún)f(xié)議和實(shí)際協(xié)議2,若2個(gè)協(xié)議在計(jì)算上不可區(qū)分,即可證明協(xié)議2的安全性。

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

1)在理想模型中,B1模擬誠(chéng)實(shí)的A1執(zhí)行協(xié)議,給TTP發(fā)送正確的M1,且收到消息后一定會(huì)給發(fā)送消息B2。不誠(chéng)實(shí)的B2調(diào)用A2來執(zhí)行協(xié)議。B2把M2發(fā)送給A2,然后獲取執(zhí)行協(xié)議時(shí)A2使用的數(shù)據(jù)A2(M2)。B2向TTP發(fā)送A2(M2),然后獲取數(shù)據(jù)F(M1,A2(M2)),同時(shí)B1也需要得到F(M1,A2(M2)))。

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

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

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

4 性能分析

本文通過效率分析和實(shí)驗(yàn)仿真對(duì)協(xié)議性能進(jìn)行分析,具體如下。

4.1 效率分析

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

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

本文協(xié)議1和協(xié)議2與文獻(xiàn)[12]、[13]和[16]進(jìn)行對(duì)比,如表2所示。

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

表2 方案對(duì)比Tab.2 Scheme comparison

4.2 實(shí)驗(yàn)仿真

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

圖1 效率對(duì)比Fig.1 Efficiency comparison

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

因?yàn)閻阂饽Ｐ拖碌陌踩喾接?jì)算協(xié)議需要使用cut-choose和零知識(shí)證明等方法,所以協(xié)議執(zhí)行時(shí)間一般高于相同輸入長(zhǎng)度的半誠(chéng)實(shí)模型下的協(xié)議,但可以采用云服務(wù)外包計(jì)算等方式來降低惡意模型下的計(jì)算開銷。

5 結(jié)束語

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