徐 琳 魏曉超 蔡國(guó)鵬 王 皓 鄭志華

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

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

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

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

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

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

1.1 相關(guān)工作

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

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

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

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

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

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

1.2 本文的主要工作

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

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

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

本文的貢獻(xiàn)主要包括3個(gè)方面.

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

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

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

2 基本知識(shí)和安全定義

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

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

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

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

協(xié)議1[17].

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

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

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

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

1)S隨機(jī)選擇s∈{0,1}k，R準(zhǔn)備一個(gè)m×k的隨機(jī)比特矩陣T.

3)S將接收到的值形成m×k矩陣Q，其中qi=(si·r)⊕ti，qj=(rj·s)⊕tj.對(duì)于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) 對(duì)于1≤j≤m，R輸出zj=yj,rj⊕H(j,tj).

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

在一個(gè)公鑰加密方案(KeyGen,Enc,Dec)中，(pk,sk)是KeyGen(1k)的輸出，和分別是明文空間和密文空間.對(duì)任意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 茫然多項(xiàng)式計(jì)算

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

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

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

2.4 隱私等值比較

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

功能函數(shù)FPEQT.

輸入：

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

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

輸出：

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

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

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

協(xié)議2[24].

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

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

其他參數(shù)：

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

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

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

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

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

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

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

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

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

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

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

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

2.6 安全性定義

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

定義1.令f:{0,1}*×{0,1}*→{0,1}*×{0,1}*是一個(gè)兩方函數(shù)，π是一個(gè)兩方現(xiàn)實(shí)協(xié)議.協(xié)議π在半誠(chéng)實(shí)敵手的情況下安全計(jì)算f，如果對(duì)于真實(shí)模型中的每一個(gè)非均勻概率多項(xiàng)式時(shí)間敵手，在理想模型中就存在一個(gè)非均勻概率多項(xiàng)式時(shí)間模擬器，對(duì)于2個(gè)參與方的輸入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個(gè)參與方，分別是數(shù)據(jù)庫(kù)方D和用戶U.其中數(shù)據(jù)庫(kù)方和用戶分別持有文本字符串t和模式字符串p.功能函數(shù)FAPM要求用戶U能夠得到其模式與數(shù)據(jù)庫(kù)方的文本字符串近似匹配的位置，從而實(shí)現(xiàn)模式匹配功能.當(dāng)文本子串與模式串之間的漢明距離小于閾值τ時(shí)，該子串與模式串即滿足近似匹配.

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

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

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

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

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

功能函數(shù)FAPM.

輸入：

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

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

輸出：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

協(xié)議：

3) 數(shù)據(jù)庫(kù)方D和用戶U通過(guò)茫然多項(xiàng)式計(jì)算和隱私等值比較判斷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é)議運(yùn)行結(jié)束之后，用戶U得到正確的結(jié)果.具體而言，如果在數(shù)據(jù)庫(kù)方的文本t中存在與模式p近似匹配的子串，則用戶一定輸出該子串的起始位置，否則用戶輸出⊥，匹配失敗.

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

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

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

3.4 協(xié)議安全性

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

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

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

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

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

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

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

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

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

2) 用戶U被腐化

用戶U的視圖：

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

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

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

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

證畢.

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

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

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

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

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

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

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

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

4 性能評(píng)估

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

我們?cè)谶\(yùn)行Windows 10系統(tǒng)，使用Intel?CoreTMi5 CPU和16 GB RAM的個(gè)人計(jì)算機(jī)上進(jìn)行我們的實(shí)驗(yàn).在本實(shí)驗(yàn)中，我們使用隨機(jī)的二進(jìn)制模式字符串和文本字符串.此外，我們使用Paillier加密系統(tǒng)來(lái)進(jìn)行加密，其密鑰長(zhǎng)度為2 048.

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

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

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

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

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

5 結(jié)束語(yǔ)

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