一個高效的安全兩方近似模式匹配協(xié)議

徐 琳 魏曉超 蔡國鵬 王 皓 鄭志華

(山東師范大學(xué)信息科學(xué)與工程學(xué)院 濟南 250358)

模式匹配作為計算科學(xué)領(lǐng)域中的一個典型問題，其功能是確定模式在文本中出現(xiàn)的位置.近似模式匹配(approximate pattern matching, APM)作為最適合實際應(yīng)用的模式匹配變體，常用于人臉識別、基因匹配、文本處理、數(shù)據(jù)挖掘和計算生物學(xué)等領(lǐng)域.如在人臉識別中，當(dāng)光線、表情或位置不同時，我們提取的人臉圖像的特征數(shù)據(jù)也不同.因此，在與數(shù)據(jù)庫中存儲的特征模板進行匹配時，需要根據(jù)相似程度來判斷人臉的身份信息，而不是根據(jù)它們是否相同.

在安全兩方計算[1-2]中，互不信任的2個參與方希望共同計算關(guān)于他們隱私輸入的某些函數(shù)，而不會泄露除了函數(shù)輸出以外的其他任何信息，同時確保某些安全屬性，例如隱私性、正確性等.隨著人們隱私保護意識的不斷增強，安全模式匹配作為安全兩方計算中領(lǐng)域的一個典型問題，成為當(dāng)下的重要研究內(nèi)容.

現(xiàn)在考慮場景：某基因研究中心擁有一個RNA病毒庫，某研究人員持有一個未知病毒的RNA序列.研究人員希望確定病毒庫中是否存在與未知病毒相似的RNA序列，因為相似的2個RNA序列會存在部分相似的特征.然而，研究人員不愿向研究中心透露其正在研究的未知病毒的序列，而研究中心也不希望向研究人員透露其他無關(guān)RNA序列的信息.顯而易見，安全近似模式匹配可以很好地解決該場景中的問題.因此，安全近似匹配是至關(guān)重要且實用的，它既能實現(xiàn)近似匹配功能，又能保護雙方隱私信息的安全性.

本文主要考慮安全近似模式匹配場景：數(shù)據(jù)庫方持有長度為n的文本字符串t∈{0,1}n，用戶持有長度為m的模式字符串p∈{0,1}m，同時雙方共享某閾值τ.用戶希望僅自己知道與其模式相匹配的文本子串的位置(模式p與文本子串之間的漢明距離小于τ，即為匹配成功)，同時數(shù)據(jù)庫方不會獲得關(guān)于用戶模式的任何信息.而數(shù)據(jù)庫方希望用戶不會獲得關(guān)于其文本的其他額外信息.本文主要考慮半誠實敵手模型下的協(xié)議，即敵手嚴格遵循協(xié)議的執(zhí)行，但卻是“好奇”的，其試圖通過收到的信息以及所處的狀態(tài)推測出其他額外信息.

1 相關(guān)工作和主要工作

1.1 相關(guān)工作

據(jù)我們所知，首次在安全計算環(huán)境中考慮近似模式匹配問題的工作是Troncoso-Pastoriza等人[3]，他們提出了一種基于茫然自動機的隱私保護容錯DNA查詢協(xié)議.該協(xié)議能夠確定一方持有的描述導(dǎo)致疾病突變的短字符串是否存在于另一方擁有的DNA序列中.Gennaro等人[4]基于茫然自動機計算提出了安全計算近似模式匹配問題的有效協(xié)議，他們的協(xié)議首次在惡意敵手模型中實現(xiàn)完全模擬.

Hazay等人[5]基于Elgamal同態(tài)加密提出了惡意敵手模型下的安全近似模式匹配協(xié)議.協(xié)議雙方分別將他們的輸入分解為比特，并對每個比特進行加密.為了確定匹配，雙方使用Elgamal加密的同態(tài)性質(zhì)計算加密的漢明距離，并判斷這些漢明距離是否小于閾值τ.之后Hazay等人[6]改進了協(xié)議的漢明距離計算階段，將通信復(fù)雜度由O(nm)降低至O(nτ).然而，由于他們的協(xié)議主要使用同態(tài)加密技術(shù)，所以協(xié)議的計算復(fù)雜度一直是O(nm).

Vergnaud[7]通過采用一種新的快速傅里葉變化(fast Fourier transform, FFT)方法，研究了惡意敵手模型下的安全近似模式匹配協(xié)議.他們的協(xié)議依賴于Fischer等人[8]在1974年提出的一種著名的模式匹配技術(shù)，其中輸入被視為2個多項式的系數(shù)，它們的乘積通過使用FFT計算.

Yasuda等人[9]使用Somewhat同態(tài)加密的對稱密鑰變體方案設(shè)計了一個安全近似模式匹配協(xié)議，但是他們沒有證明協(xié)議的安全性.

Samadani等人[10]利用Shift-ADD算法[11]的特性進行安全近似模式匹配，他們的構(gòu)造在單邊模擬的惡意敵手模型中是安全的.最近，Zarezadeh等人[12]也基于Shift-ADD算法以及同態(tài)加密技術(shù)構(gòu)造了一個在惡意敵手模型中實現(xiàn)完全模擬的安全近似模式匹配協(xié)議.遺憾的是，協(xié)議[10,12]在近似模式匹配過程中會泄露漢明距離.若考慮不泄露漢明距離的情況，則需在密文狀態(tài)下比較漢明距離與給定閾值.

除了在標準模型下構(gòu)造的工作外，還有諸多工作在云輔助模型下考慮安全近似模式匹配問題，如魏曉超等人[13]基于茫然傳輸擴展(oblivious transfer extension, OT extension)技術(shù)以及秘密分享構(gòu)造了安全外包近似模式匹配協(xié)議，他們將重構(gòu)階段外包給誠實但好奇的云服務(wù)器，以降低參與方的計算負擔(dān).

1.2 本文的主要工作

本文基于茫然傳輸、同態(tài)加密以及茫然多項式計算技術(shù)構(gòu)造了一個安全、高效的近似模式匹配協(xié)議，協(xié)議在半誠實敵手模型下滿足安全性要求.

協(xié)議有2個參與方，分別是數(shù)據(jù)庫方D以及用戶U.其中，數(shù)據(jù)庫方提供文本信息，用戶提供模式信息.如圖1的系統(tǒng)模型所示，協(xié)議主要分為4個階段，分別是茫然傳輸階段、漢明距離計算階段、匹配階段以及輸出階段.系統(tǒng)需要保證用戶在不泄露其模式信息的前提下查詢其模式在數(shù)據(jù)庫方的文本中出現(xiàn)的位置信息.同時，系統(tǒng)也需要保證數(shù)據(jù)庫方文本的其他信息不被泄露.

Fig. 1 System model of secure approximate pattern matching圖1 安全近似模式匹配系統(tǒng)模型

本文的貢獻主要包括3個方面.

1) 首次基于茫然傳輸、加法同態(tài)加密、茫然多項式計算以及隱私等值比較技術(shù)給出了一個半誠實安全的近似模式匹配協(xié)議的高效構(gòu)造.協(xié)議的主要思想是：首先，通過茫然傳輸協(xié)議，用戶在無法獲得文本信息的情況下獲得盲化后的文本子串比特與對應(yīng)位置模式比特的異或值.其次，結(jié)合同態(tài)加密技術(shù)，可計算出盲化后的文本子串與模式之間的漢明距離.最后，利用茫然多項式計算以及隱私等值比較技術(shù)，就可以判斷漢明距離是否小于τ，并最終得到正確結(jié)果.

2) 與現(xiàn)有的安全近似模式匹配工作相比，我們的協(xié)議在計算復(fù)雜度方面更高效，其中協(xié)議的輪復(fù)雜度為O(1)，計算復(fù)雜度為O(nτ)，通信復(fù)雜度為O(nm).

3) 為了檢驗協(xié)議的高效性，我們進行了性能評估.實驗結(jié)果表明：當(dāng)模式長度為26、文本長度為212時，協(xié)議僅需10 s運行時間.

2 基本知識和安全定義

2.1 茫然傳輸及其擴展協(xié)議

茫然傳輸(oblivious transfer, OT)是密碼學(xué)中重要的基本原語之一，被廣泛應(yīng)用于安全計算領(lǐng)域.OT最早是由Rabin[14]提出的，在這種OT中，發(fā)送方向接收方發(fā)送一條消息，接收方能夠以1/2的概率收到消息.在OT執(zhí)行結(jié)束后，發(fā)送方不知道接收方是否收到了消息，而接收方可以確切地知道是否收到了消息.另一種比較實用的OT協(xié)議，稱為1-out-of-2 OT，它是由Even等人[15]提出的.在1-out-of-2 OT協(xié)議中，發(fā)送方每次向接收方發(fā)送2個有序消息(x0,x1).接收方輸入一個選擇比特σ，并根據(jù)自己的輸入得到輸出.在協(xié)議結(jié)束時，接收方僅獲得消息xσ，不會得知關(guān)于另一消息的信息，而發(fā)送方不會得知接收方最后獲得的是哪一個消息.

在具體的安全多方計算協(xié)議中，需要執(zhí)行的OT協(xié)議數(shù)量可能高達數(shù)百萬個.因此，OT協(xié)議的效率成為影響安全多方計算協(xié)議效率的重要因素.在這種情況下，Beaver[16]借鑒混合加密的思想，首先提出了茫然傳輸擴展技術(shù).OT擴展協(xié)議通過運行少量的基礎(chǔ)OT協(xié)議，再結(jié)合廉價的偽隨機替換操作，即可實現(xiàn)執(zhí)行大量OT協(xié)議的效果.然而，遺憾的是，這種構(gòu)造并不高效.之后，Ishai等人[17]提出了一種OT擴展協(xié)議，這是半誠實敵手模型中第1個高效的OT擴展協(xié)議.后續(xù)Kolesnikov等人[18]改進了Ishai等人的OT擴展方案，他們將1-out-of-2 OT擴展協(xié)議擴展為1-out-of-nOT擴展協(xié)議，同時提高了效率.Asharov等人[19]在標準模型下構(gòu)建了一種新的OT協(xié)議，并將其用于OT擴展技術(shù)，降低了計算和通信的復(fù)雜性.

當(dāng)前，基于OT擴展技術(shù)的協(xié)議較之于其他技術(shù)實現(xiàn)的協(xié)議更為高效，因而本文也將使用Ishai等人[17]的OT擴展技術(shù)來改進安全近似模式匹配協(xié)議的效率，協(xié)議描述如下：

協(xié)議1[17].

S輸入：m對有序消息(xj,0,xj,1)∈{0,1}l，1≤j≤m；

R輸入：m個選擇比特r=(r1,r2,…,rm)；

共同輸入：安全參數(shù)k；

諭言機：隨機諭言機H:[m]×{0,1}k→{0,1}l；

1)S隨機選擇s∈{0,1}k，R準備一個m×k的隨機比特矩陣T.

3)S將接收到的值形成m×k矩陣Q，其中qi=(si·r)⊕ti，qj=(rj·s)⊕tj.對于1≤j≤m，R發(fā)送(yj,0,yj,1)，其中yj,0=xj,0⊕H(j,qj)，yj,1=xj,1⊕H(j,qj⊕s).

4) 對于1≤j≤m，R輸出zj=yj,rj⊕H(j,tj).

2.2 加法同態(tài)加密

在一個公鑰加密方案(KeyGen,Enc,Dec)中，(pk,sk)是KeyGen(1k)的輸出，和分別是明文空間和密文空間.對任意m1,m2∈和c1,c2∈，其中m1=Dsk(c1)且m2=Dsk(c2)，若有式：{pk,c1,c1×c2}≡{pk,Encpk(m1),Encpk(m1+m2)}，則我們稱該公鑰加密方案是加法同態(tài)加密(additive homomorphic encryption, AHE)的.

2.3 茫然多項式計算

茫然多項式計算(oblivious polynomial evaluation, OPE)最早是由Naor等人[20]提出的.OPE是一個兩方協(xié)議，P0持有秘密多項式p(·)，而P1持有秘密元素x.OPE允許P1得到p(x)，但無法獲得多項式p(·)，同時P0無法得知P1持有的x.OPE常應(yīng)用于諸多密碼學(xué)方案中，如茫然關(guān)鍵字查找[21]、集合求交[22]等.

本文將使用趙永駿等人[23]所提及的茫然多項式計算方案，方案描述為：在OPE協(xié)議中，一方持有1個n階多項式p(·)，通過使用同態(tài)加密方案加密此n階多項式p(·)的系數(shù)a0,a1,…,an以隱藏其本身，并將這些加密系數(shù)Encpk(p(·))發(fā)送給持有明文的參與方.持有明文x的參與方可基于同態(tài)性質(zhì)Encpk(a0)×(Encpk(a1))x×(Encpk(a2))x2×…×(Encpk(an))xn來計算得到Encpk(p(x)).

對于協(xié)議1，就計算復(fù)雜度而言，我們主要考慮加密操作和模冪運算，因而協(xié)議1的計算復(fù)雜度為O(n).就通信復(fù)雜度而言，協(xié)議1僅存在發(fā)送加密多項式系數(shù)，因此通信復(fù)雜度為O(n).

2.4 隱私等值比較

隱私等值比較(private equality test, PEQT)允許發(fā)送方和接收方分別輸入字符串x0和x1，且接收方僅獲得0或1以表示x0與x1是否相等，但不會得知其他任何信息.功能函數(shù)FPEQT描述為：

功能函數(shù)FPEQT.

輸入：

1) 發(fā)送方輸入字符串x0∈{0,1}*；

2) 接收方輸入字符串x1∈{0,1}*.

輸出：

1) 如果x0=x1，接收方輸出1，否則輸出0；

2) 發(fā)送方無輸出.

當(dāng)PEQT協(xié)議首次被提出時，它依賴于復(fù)雜的公鑰操作，開銷很大.但Kolesnikov等人[24]的協(xié)議僅通過使用少量基礎(chǔ)OT協(xié)議以及一些對稱操作，就實現(xiàn)了大量PEQT協(xié)議的執(zhí)行效果.本文將使用Kolesnikov等人[24]的PEQT協(xié)議，但鑒于Kolesnikov等人僅描述了協(xié)議的主要思想且給出了關(guān)鍵模塊的構(gòu)造，因此我們給出協(xié)議具體描述為：

協(xié)議2[24].

S輸入：m個字符串u=(u1,u2,…,um)，其中ui∈{0,1}*;

R輸入：m個字符串r=(r1,r2,…,rm)，其中ri∈{0,1}*;

其他參數(shù)：

(κ,ε)-偽隨機碼函數(shù)簇C，輸出長度k=k(κ)；κ-漢明相關(guān)性魯棒Hash函數(shù)H:[m]×{0,1}k→{0,1}v；

1)S選擇一個隨機C←C，并將其發(fā)送給R.

2)S隨機選擇s←{0,1}k，si表示s的第i個比特.

3)R生成m×k矩陣T0，T1：

5) 對于每一個j∈[m]，S輸出偽隨機函數(shù)種子((C,s),(j,qj))，R輸出松弛偽隨機函數(shù)輸出(C,j,t0,j).

6) 對于每一個j∈[m]，S通過偽隨機函數(shù)種子計算其輸入u=(u1,u2,…,um)的偽隨機函數(shù)輸出，記為t2,j=qj⊕(C(uj)·s)，并將t2,j發(fā)送給R.

7) 對于每一個j∈[m]，R簡單比較t0,j與t2,j是否相等.若t0,j=t2,j，R輸出1，否則輸出0.

就計算復(fù)雜度而言，協(xié)議2主要通過執(zhí)行k次基礎(chǔ)OT協(xié)議，并結(jié)合一些Hash操作，實現(xiàn)了PEQT協(xié)議，因此協(xié)議2的計算復(fù)雜度為O(k).考慮通信復(fù)雜度，協(xié)議2實現(xiàn)m×k矩陣，因此通信復(fù)雜度為O(mk).

2.5 計算不可區(qū)分性

假設(shè)X={X(a,n)}a∈{0,1}*;n∈和Y={Y(a,n)}a∈{0,1}*;n∈是2個分布總體.對任意一個非均勻多項式時間算法D，如果存在一個可忽略函數(shù)negl(·)，對于每個a∈{0,1}*和每個n∈，不等式成立：

|Pr[D(X(a,n)=1)]|-
|Pr[D(Y(a,n)=1)]|≤negl(·),

則我們說這2個分布總體是計算不可區(qū)分的，表示為X≡Y.

2.6 安全性定義

本文主要考慮的安全模型是半誠實敵手下的安全兩方計算模型，并基于理想/現(xiàn)實模擬范式[25-26]給出形式化的安全性定義.敵手嚴格遵循協(xié)議，但是試圖通過觀察其收到的信息以及其所處的狀態(tài)來推測出其他額外信息.我們給出基于理想/現(xiàn)實模擬范式的形式化安全性定義.

定義1.令f:{0,1}*×{0,1}*→{0,1}*×{0,1}*是一個兩方函數(shù)，π是一個兩方現(xiàn)實協(xié)議.協(xié)議π在半誠實敵手的情況下安全計算f，如果對于真實模型中的每一個非均勻概率多項式時間敵手，在理想模型中就存在一個非均勻概率多項式時間模擬器，對于2個參與方的輸入x和y以及i∈{1，2}滿足:

{IDEALf,S(z),i(x,y,n)}x,y,z,n≡
{REALf,A(z),i(x,y,n)}x,y,z,n,

其中，x,y,z∈{0,1}*,n∈.

3 安全近似模式匹配協(xié)議

3.1 安全近似模式匹配功能函數(shù)

本文所考慮的安全近似模式匹配功能函數(shù)FAPM中主要涉及2個參與方，分別是數(shù)據(jù)庫方D和用戶U.其中數(shù)據(jù)庫方和用戶分別持有文本字符串t和模式字符串p.功能函數(shù)FAPM要求用戶U能夠得到其模式與數(shù)據(jù)庫方的文本字符串近似匹配的位置，從而實現(xiàn)模式匹配功能.當(dāng)文本子串與模式串之間的漢明距離小于閾值τ時，該子串與模式串即滿足近似匹配.

同時，功能函數(shù)FAPM要保證3種安全屬性：

1) 用戶U的模式信息對數(shù)據(jù)庫方是保密的.

2) 數(shù)據(jù)庫方D的文本信息對用戶是保密的.

3) 用戶U只有在匹配成功的情況下才能獲得相應(yīng)的位置信息，而當(dāng)匹配失敗時，不能得到關(guān)于文本t的任何信息.

下面我們給出功能函數(shù)FAPM的形式化描述：

功能函數(shù)FAPM.

輸入：

1) 數(shù)據(jù)庫方D輸入字符串t∈{0,1}n、整數(shù)m以及閾值τ；

2) 用戶U輸入字符串p∈{0,1}m、整數(shù)n以及閾值τ.

輸出：

1) 當(dāng)且僅當(dāng)文本t的第i個子串與模式p之間的漢明距離小于閾值τ時，用戶U輸出位置i；

2) 數(shù)據(jù)庫方D無輸出.

3.2 安全近似模式匹配協(xié)議構(gòu)造

本節(jié)我們給出了半誠實敵手模型下的安全高效的近似模式匹配協(xié)議構(gòu)造.協(xié)議主要基于茫然傳輸、同態(tài)加密、茫然多項式計算和隱私等值比較.通過茫然傳輸擴展協(xié)議，用戶能夠在不知道文本信息的情況下，獲得盲化后的模式p的每一比特與文本子串對應(yīng)的每一比特的異或值.這一步的思想主要源于宋祥福等人[27]的共享等值比較協(xié)議.通過同態(tài)加密計算，數(shù)據(jù)庫方可獲得盲化后的ti與模式p之間的漢明距離.通過茫然多項式計算與隱私等值比較，用戶可獲得其模式在數(shù)據(jù)庫方的文本中出現(xiàn)的位置.

安全近似模式匹配協(xié)議的流程大致分為4個階段：

1) 茫然傳輸階段.數(shù)據(jù)庫方將其選擇的隨機數(shù)嵌入到茫然傳輸擴展協(xié)議的輸入中，以達到盲化其文本的目的.通過茫然傳輸擴展協(xié)議，用戶可以獲得盲化后的模式p的每一比特與文本子串ti對應(yīng)的每一比特的異或值.

2) 漢明距離計算階段.用戶對盲化后的比特異或值進行計算，得到盲化后的ti與模式p之間的漢明距離.數(shù)據(jù)庫方對其選擇的隨機數(shù)進行求和運算，使用其公鑰加密后發(fā)送給用戶.用戶通過加法同態(tài)加密計算得到密文狀態(tài)下的漢明距離，盲化后將其發(fā)送給數(shù)據(jù)庫方解密.

3) 匹配階段.數(shù)據(jù)庫方和用戶通過茫然多項式計算和隱私等值比較判斷文本子串ti與模式p之間的漢明距離是否小于閾值τ.如果漢明距離小于閾值τ，用戶獲得輸出1，否則獲得輸出0.

4) 輸出階段.用戶根據(jù)輸出是否為1確定相應(yīng)子串是否匹配成功，最終輸出匹配位置.

在介紹協(xié)議之前，我們先介紹協(xié)議中用到的符號，如表1所示:

Table 1 Notations of Secure Approximate Pattern Matching Protocol表1 安全近似模式匹配協(xié)議符號含義

本文所構(gòu)造的協(xié)議具體描述如下：

協(xié)議3.安全近似模式匹配協(xié)議πAPM.

輸入：數(shù)據(jù)庫方D輸入字符串t∈{0,1}n、整數(shù)m以及閾值τ；用戶U輸入字符串p∈{0,1}m、整數(shù)n以及閾值τ；

輸出：當(dāng)且僅當(dāng)文本子串ti與模式p之間的漢明距離小于閾值τ時，用戶U輸出位置i.

協(xié)議：

3) 數(shù)據(jù)庫方D和用戶U通過茫然多項式計算和隱私等值比較判斷ri+Hi是否與ri,ri+1,ri+2,…,ri+τ-1中之一相等.若相等，則表明文本子串ti與模式p之間的漢明距離小于τ，即文本子串ti與模式p匹配.

4) 用戶U判定bi中哪些值為1，以此確定模式p在t中出現(xiàn)的位置.

① 若存在bi=1，表示文本子串ti和模式p匹配成功，則輸出i;

② 否則，輸出⊥，表示匹配失敗.

3.3 協(xié)議正確性

安全近似模式匹配協(xié)議的正確性是指在協(xié)議運行結(jié)束之后，用戶U得到正確的結(jié)果.具體而言，如果在數(shù)據(jù)庫方的文本t中存在與模式p近似匹配的子串，則用戶一定輸出該子串的起始位置，否則用戶輸出⊥，匹配失敗.

首先需要說明的是，通過茫然傳輸協(xié)議，用戶能夠獲得正確的盲化后的比特異或值.我們就2種情況分別進行說明：

其次需要說明的是，通過茫然多項式計算和隱私等值比較，用戶能夠得到正確的匹配結(jié)果.我們就2種情況分別進行闡述：

綜上所述，用戶U在匹配成功和失敗情況下均能輸出正確的結(jié)果，因此協(xié)議正確性滿足.

3.4 協(xié)議安全性

我們給出安全近似模式匹配協(xié)議的形式化安全證明：

定理1.假設(shè)茫然傳輸協(xié)議和隱私等值比較協(xié)議在半誠實敵手模型下是安全的，加密方案是CPA安全的，根據(jù)定義1，協(xié)議πAPM在半誠實敵手模型下能夠安全計算功能函數(shù)FAPM.

證明. 我們在(FOTE,FPEQT)-混合模型中證明協(xié)議πAPM的安全性，其中FOTE與FPEQT是理想功能函數(shù).我們分別對數(shù)據(jù)庫方D和用戶U被腐化2種情況進行證明.

1) 數(shù)據(jù)庫方D被腐化

數(shù)據(jù)庫方D的視圖：

假設(shè)數(shù)據(jù)庫方D被多項式時間敵手A腐化.我們構(gòu)建一個多項式時間模擬器SD，SD調(diào)用敵手的輸入輸出且扮演誠實方U的角色與敵手交互.模擬器的行為：

①SD模擬理想功能函數(shù)FOTE的執(zhí)行.

⑤SD模擬理想功能函數(shù)FPEQT的執(zhí)行.

我們可以得到模擬器SD的輸出：

2) 用戶U被腐化

用戶U的視圖：

假設(shè)用戶U被多項時間敵手A腐化.我們構(gòu)造一個多項式時間模擬器SU，SU調(diào)用敵手的輸入輸出并且扮演誠實方D的角色與敵手交互.模擬器SU的行為：

④SU模擬理想功能函數(shù)FPEQT的執(zhí)行，并將bi∈{0,1}發(fā)送給敵手A，其中協(xié)議輸出位置i對應(yīng)的bi為1，其余為0.

我們可以得到模擬器SU的輸出：

綜上所述，我們完成對定理1的證明.

證畢.

3.5 協(xié)議效率分析與比較

我們將就輪復(fù)雜度、計算復(fù)雜度和通信復(fù)雜度3方面對協(xié)議進行效率分析，并給出與相關(guān)工作的效率比較.

1) 輪復(fù)雜度.我們所構(gòu)造的安全近似模式匹配協(xié)議共需要9輪交互.其中，在茫然傳輸擴展協(xié)議中，需要進行2輪交互.此外，在漢明距離計算階段和匹配階段中，共需要4輪交互.注意，用戶U可以在1輪交互中將盲化后的漢明距離的密文以及多項式系數(shù)的密文發(fā)送給數(shù)據(jù)庫方D.最后，在輸出階段中，隱私等值比較協(xié)議需要3輪交互.

2) 計算復(fù)雜度.協(xié)議的計算復(fù)雜度主要涉及到對稱操作和非對稱操作.其中，對稱操作速度快、代價小，如Hash、異或等.而非對稱操作速度慢、代價大，如加密、解密、模冪運算等.因此，我們主要考慮通過非對稱操作的數(shù)量來衡量協(xié)議的計算復(fù)雜度.在安全近似模式匹配協(xié)議中，我們調(diào)用了1次茫然傳輸擴展協(xié)議、n-m+1次茫然多項式計算協(xié)議、1次隱私等值比較協(xié)議.在2.1節(jié)中，可知茫然傳輸擴展部分的計算復(fù)雜度為O(k)，其中k為基礎(chǔ)OT協(xié)議的數(shù)量且k?nm.在2.3節(jié)中，可知茫然多項式計算協(xié)議的計算復(fù)雜度與多項式的階數(shù)有關(guān).而本協(xié)議中多項式的階數(shù)為τ，所以茫然多項式計算部分的計算復(fù)雜度為O((n-m)τ).在2.4節(jié)中，可知隱私等值比較部分的計算復(fù)雜度也為O(k)，k為基礎(chǔ)OT的數(shù)量且k?nm.另外，在協(xié)議3的步驟2)中，所執(zhí)行的加密操作與解密操作的數(shù)量分別為3(n-m+1)和n-m+1.在協(xié)議3的步驟3)中茫然多項式計算結(jié)束后，所執(zhí)行的加密操作與解密操作的數(shù)量分別為n-m+1和n-m+1.相對于茫然多項式部分的計算復(fù)雜度來說，OT擴展協(xié)議和PEQT協(xié)議的計算復(fù)雜度是可忽略的.因此，安全近似模式匹配協(xié)議的計算復(fù)雜度為O((n-m)τ).考慮到實際情況中m的大小相對于n是可忽略的，所以我們協(xié)議的計算復(fù)雜度為O(nτ).

3) 通信復(fù)雜度.通信復(fù)雜度是指參與方之間發(fā)送和接收的信息數(shù).首先，在安全近似模式匹配協(xié)議中，執(zhí)行1次OT擴展協(xié)議需實現(xiàn)(n-m+1)×m矩陣效果，執(zhí)行1次隱私等值比較協(xié)議也需實現(xiàn)(n-m+1)×m矩陣效果，所以O(shè)T擴展與隱私等值比較部分的通信復(fù)雜度都為O(nm).在2.3節(jié)中，可知茫然多項式計算協(xié)議的通信復(fù)雜度與多項式的階數(shù)有關(guān).而本協(xié)議中調(diào)用n-m+1次茫然多項式計算協(xié)議，且多項式的階數(shù)為τ，所以茫然多項式計算部分的計算復(fù)雜度為O((n-m)τ).另外，在安全近似模式匹配協(xié)議(協(xié)議3)的步驟2)中，發(fā)送消息的數(shù)量為2(n-m+1).在安全近似模式匹配協(xié)議(協(xié)議3)的步驟3)中，茫然多項式計算結(jié)束后，發(fā)送消息的數(shù)量為2(n-m+1).考慮到上述情況，安全近似模式匹配協(xié)議的通信復(fù)雜度為O(nm).

表2給出了本文中安全近似模式匹配協(xié)議與相關(guān)工作中半誠實敵手模型的近似模式匹配協(xié)議的比較結(jié)果.具體地，我們從協(xié)議的輪復(fù)雜度、計算復(fù)雜度、通信復(fù)雜度3個方面對協(xié)議進行效率比較.其中，n和m分別是模式匹配協(xié)議中數(shù)據(jù)庫方與用戶的輸入長度，τ是給定閾值，λ是安全參數(shù).

Table 2 Efficiency Comparison of Protocols表2 協(xié)議效率比較

首先，我們構(gòu)造的協(xié)議同文獻[5-6]的協(xié)議一樣，只需要常數(shù)輪，優(yōu)于文獻[10]的協(xié)議的O(τ)輪.其次，文獻[5-6]的協(xié)議主要使用同態(tài)加密技術(shù)，考慮到同態(tài)加密技術(shù)的高昂代價，因而文獻[5-6]的協(xié)議的計算復(fù)雜度均為O(nm).文獻[10]的協(xié)議中加密操作的數(shù)量級為O(mτ)，模冪操作的數(shù)量級為O(nτ)，因此文獻[10]的協(xié)議的計算復(fù)雜度為O((n+m)τ).遺憾的是，文獻[10，12]的協(xié)議在近似模式匹配過程中會泄露漢明距離.若考慮不泄露漢明距離的情況，文獻[10，12]協(xié)議的計算復(fù)雜度和通信復(fù)雜度要比其所聲稱的更高.相較于文獻[5-6，10]的協(xié)議，我們的協(xié)議在不泄露漢明距離的情況下實現(xiàn)了安全近似模式匹配，且計算復(fù)雜度僅為O(nτ).最后，考慮通信復(fù)雜度，我們的協(xié)議同文獻[5-6，10]的協(xié)議相比較，通信復(fù)雜度較為接近.

4 性能評估

本節(jié)我們對安全近似模式匹配協(xié)議的性能進行評估.我們的協(xié)議是基于OT擴展、同態(tài)加密、茫然多項式計算以及PEQT構(gòu)造的.其中，在OT階段，我們使用OT擴展技術(shù)，只需要少量基礎(chǔ)OT協(xié)議和一些對稱操作就可以達到大量OT協(xié)議執(zhí)行的效果，極大地減少了OT協(xié)議的數(shù)量.而高效的PEQT協(xié)議也可以通過基礎(chǔ)OT協(xié)議和廉價的對稱操作實現(xiàn)許多PEQT協(xié)議執(zhí)行的效果.此外，Asharov等人[19]證明了OT擴展技術(shù)可以每秒執(zhí)行數(shù)百萬個OT實例，這是非常高效的.而加密、解密和模冪操作需要較長的執(zhí)行時間，因此，在本協(xié)議中，我們主要考慮加密、解密和模冪操作的執(zhí)行時間.

我們在運行Windows 10系統(tǒng)，使用Intel?CoreTMi5 CPU和16 GB RAM的個人計算機上進行我們的實驗.在本實驗中，我們使用隨機的二進制模式字符串和文本字符串.此外，我們使用Paillier加密系統(tǒng)來進行加密，其密鑰長度為2 048.

注意到，模式信息的長度記為m，文本信息的長度記為n，我們設(shè)置τ=0.5，即漢明距離需小于0.5 m.我們?nèi)∧Ｊ降拈L度分別為m=26,27,28,29,210，文本的長度分別為n=211,212,213,214，協(xié)議運行時間如表3所示.我們可以發(fā)現(xiàn)，當(dāng)模式長度為26、文本長度為212時，協(xié)議在10 s內(nèi)即可運行結(jié)束.

Table 3 Running Time of Different Settings at τ=0.5表3 τ=0.5時協(xié)議在不同設(shè)置下的運行時間

此外，我們又設(shè)置τ=0.9，模式長度m分別為26,27,28,29,210，文本長度n分別為211,212,213,214，并進行了實驗.為了便于觀察實驗結(jié)果，我們給出了τ=0.5與τ=0.9時實驗結(jié)果的折線圖，如圖2和圖3所示.我們發(fā)現(xiàn)，當(dāng)τ值由0.5增加到0.9，隨著文本長度與模式長度的增加，協(xié)議的運行時間的增長幅度越大.

Fig. 2 Running time of different settings at τ=0.5圖2 τ=0.5時協(xié)議在不同設(shè)置下的運行時間

Fig. 3 Running time of different settings at τ=0.9圖3 τ=0.9時協(xié)議在不同設(shè)置下的運行時間

5 結(jié)束語

本文主要考慮半誠實敵手模型下的高效安全近似模式匹配協(xié)議構(gòu)造.協(xié)議主要是基于茫然傳輸、同態(tài)加密、茫然多項式計算以及隱私等值比較技術(shù)設(shè)計構(gòu)造，需要常數(shù)輪交互，總體通信復(fù)雜度為O(nm)，計算復(fù)雜度為O(nτ)，其中n和m是數(shù)據(jù)庫方和用戶的輸入長度, τ是近似匹配協(xié)議設(shè)定的閾值.在將來的工作中，我們將研究更為高效的近似模式匹配協(xié)議構(gòu)造，并著重研究惡意敵手模型下安全模式匹配協(xié)議的構(gòu)造.