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

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

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

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

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

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

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

1 相關工作和主要工作

1.1 相關工作

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

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

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

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

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

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

1.2 本文的主要工作

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

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

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

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

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

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

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

2 基本知識和安全定義

2.1 茫然傳輸及其擴展協議

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

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

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

協議1[17].

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

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

共同輸入：安全參數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發送(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 加法同態加密

在一個公鑰加密方案(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)}，則我們稱該公鑰加密方案是加法同態加密(additive homomorphic encryption, AHE)的.

2.3 茫然多項式計算

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

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

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

2.4 隱私等值比較

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

功能函數FPEQT.

輸入：

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

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

輸出：

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

2) 發送方無輸出.

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

協議2[24].

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

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

其他參數：

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

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

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

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

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

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

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

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

2.5 計算不可區分性

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

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

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

2.6 安全性定義

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

定義1.令f:{0,1}*×{0,1}*→{0,1}*×{0,1}*是一個兩方函數，π是一個兩方現實協議.協議π在半誠實敵手的情況下安全計算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 安全近似模式匹配協議

3.1 安全近似模式匹配功能函數

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

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

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

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

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

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

功能函數FAPM.

輸入：

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

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

輸出：

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

2) 數據庫方D無輸出.

3.2 安全近似模式匹配協議構造

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

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

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

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

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

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

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

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

本文所構造的協議具體描述如下：

協議3.安全近似模式匹配協議πAPM.

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

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

協議：

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

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

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

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

3.3 協議正確性

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

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

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

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

3.4 協議安全性

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

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

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

1) 數據庫方D被腐化

數據庫方D的視圖：

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

①SD模擬理想功能函數FOTE的執行.

⑤SD模擬理想功能函數FPEQT的執行.

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

2) 用戶U被腐化

用戶U的視圖：

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

④SU模擬理想功能函數FPEQT的執行，并將bi∈{0,1}發送給敵手A，其中協議輸出位置i對應的bi為1，其余為0.

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

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

證畢.

3.5 協議效率分析與比較

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

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

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

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

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

Table 2 Efficiency Comparison of Protocols表2 協議效率比較

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

4 性能評估

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

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

注意到，模式信息的長度記為m，文本信息的長度記為n，我們設置τ=0.5，即漢明距離需小于0.5 m.我們取模式的長度分別為m=26,27,28,29,210，文本的長度分別為n=211,212,213,214，協議運行時間如表3所示.我們可以發現，當模式長度為26、文本長度為212時，協議在10 s內即可運行結束.

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

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

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

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

5 結束語

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