模式匹配作为计算科学领域中的一个典型问题，其功能是确定模式在文本中出现的位置.近似模式匹配(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-n OT扩展协议，同时提高了效率.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.
2) 双方调用原语，其中S作为中的接收方，输入为s；R作为中的发送方，输入为(ti,r⊕ti)，1≤i≤k.
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).
注意，在协议1中，表示k个消息长度为m的1-out-of-2 OT协议.协议1通过执行k次基础OT协议，并结合一些Hash操作，实现了大量OT协议执行的效果.一般而言，执行128次基础OT协议就可以实现106个OT协议执行的效果.由于Hash操作属于对称操作，而我们主要考虑通过非对称操作(如加密、解密、模幂运算等)的数量来衡量协议的计算复杂度，因此协议1的计算复杂度主要考虑基础OT部分，为O(k).考虑通信复杂度，协议1实现m×k矩阵，因此通信复杂度为O(mk).
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：
对于每一个j∈[m]，选择t0,j←{0,1}k，设置t1,j=C(rj)⊕t0,j.
分别为矩阵T0，T1的第i列.
4) S和R调用理想
原语(同2.1节所述)：
S作为中的接收方，其输入为{si}i∈[k].R作为中的发送方，其输入为
输出
生成m×k矩阵Q，向量qi为矩阵Q的第i列，qj为矩阵Q的第j行.可知，
而qj=((t0,j⊕t1,j)·s)⊕t0,j，简化得qj=t0,j⊕(C(rj)·s).
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 安全近似模式匹配协议符号含义
符号描述(pk1,sk1)数据库方D的密钥对(pk2,sk2)用户U的密钥对n文本t的长度m模式p的长度τ给定阈值[m]1,2,…,mti文本t的第i个m长的子串tmi子串ti的第m位pm模式p的第m位αii∈[n-m+1],随机数之和βii∈[n-m+1],m次OT协议输出之和ti子串ti与模式p之间的汉明距离
本文所构造的协议具体描述如下：
协议3. 安全近似模式匹配协议πAPM.
输入：数据库方D输入字符串t∈{0,1}n、整数m以及阈值τ；用户U输入字符串p∈{0,1}m、整数n以及阈值τ；
输出：当且仅当文本子串ti与模式p之间的汉明距离小于阈值τ时，用户U输出位置i.
协议：
1) 数据库方D选择随机数
其中i∈[n-m+1]，λ为安全系数.对于文本子串
数据库方D和用户U执行OT扩展协议.其中，作为OT扩展协议的发送方, 数据库方D的输入为
作为OT扩展协议的接收方，用户U的输入为p1,p2,…,pm.协议执行结束后，用户U获得输出依次为
2) 数据库方D计算随机数之和，记为
用户U计算OT扩展协议的输出之和，记为
注意，
而
为文本子串ti与模式p之间的汉明距离，记为Hi.此外，数据库方D使用其公钥pk1加密αi并将密文发送给用户U.用户U选择随机数ri∈{0,1}λ，使用D的公钥pk1加密βi和ri，通过同态加密性质计算Epk1(ri)×Epk1(βi)/Epk1(αi)，而后将结果发送给数据库方D.数据库方D使用其私钥sk1解密得到ri+Hi.
3) 数据库方D和用户U通过茫然多项式计算和隐私等值比较判断ri+Hi是否与ri,ri+1,ri+2,…,ri+τ-1中之一相等.若相等，则表明文本子串ti与模式p之间的汉明距离小于τ，即文本子串ti与模式p匹配.
① 用户U选择随机数r′∈{0,1}λ、密钥K以及根为ri,ri+1,ri+2,…,ri+τ-1的多项式Pi(·)，计算多项式
之后，用户U使用其公钥pk2加密多项式
的系数，并将密文发送给数据库方D.
② 首先，数据库方D使用点ri+Hi对多项式进行茫然计算，得到结果
数据库方D选择随机数
并使用公钥pk2加密
得到
其次，数据库方D通过同态性质计算
得到
并发送给用户U.之后，用户U使用其私钥sk2解密密文得到
发送给数据库方D.最后，数据库方D通过其持有的
恢复
③ 数据库方D和用户U执行隐私等值比较协议.其中，数据库方D作为协议的发送方，其输入为
而用户U作为协议的接收方，其输入为K.协议结束之后，用户U获得输出bi∈{0,1}.
4) 用户U判定bi中哪些值为1，以此确定模式p在t中出现的位置.
① 若存在bi=1，表示文本子串ti和模式p匹配成功，则输出i;
② 否则，输出⊥，表示匹配失败.
3.3 协议正确性
安全近似模式匹配协议的正确性是指在协议运行结束之后，用户U得到正确的结果.具体而言，如果在数据库方的文本t中存在与模式p近似匹配的子串，则用户一定输出该子串的起始位置，否则用户输出⊥，匹配失败.
首先需要说明的是，通过茫然传输协议，用户能够获得正确的盲化后的比特异或值.我们就2种情况分别进行说明：
1) 当
时，数据库方的输入为
① 当选择比特pm=0时，用户通过茫然传输协议获得的结果为
而此时计算
的结果也为
因此，该情况下，用户通过茫然传输协议获得的结果是正确的.
② 当选择比特pm=1时，用户通过茫然传输协议获得的结果为
而此时计算的结果也为
因此，该情况下，用户通过茫然传输协议获得的结果也是正确的.
2) 当
时，数据库方的输入为
① 当选择比特pm=0时，用户通过茫然传输协议获得的结果为而此时计算的结果也为因此，该情况下，用户通过茫然传输协议获得的结果是正确的.
② 当选择比特pm=1时，用户通过茫然传输协议获得的结果为而此时计算的结果也为因此，该情况下，用户通过茫然传输协议获得的结果也是正确的.
其次需要说明的是，通过茫然多项式计算和隐私等值比较，用户能够得到正确的匹配结果.我们就2种情况分别进行阐述：
1) 如果文本t中存在m比特长的子串与模式p近似匹配，则该子串与模式p之间的汉明距离小于τ.假设子串
与模式p近似匹配，则Hi<τ，因而ri+Hi∈{ri,ri+1,…,ri+τ-1}.由于ri,ri+1,…,ri+τ-1是多项式Pi(·)的根，所以数据库方用ri+Hi茫然计算多项式
的结果一定是K.在隐私等值比较协议中，数据库方和用户的输入皆为K，则用户一定得到输出1，表示该文本子串与模式p匹配.
2) 若匹配失败，则表明文本中不存在m比特长的子串与模式p之间的汉明距离小于τ.假设子串tj与模式p不匹配，则Hj≥τ，因而rj+Hj∉{rj,rj+1,…,rj+τ-1}.因此，数据库方用rj+Hj茫然计算多项式的结果一定不是K.用户在隐私等值比较协议中获得的输出一定是0，这也就表明该文本子串与模式p匹配失败.
综上所述，用户U在匹配成功和失败情况下均能输出正确的结果，因此协议正确性满足.
3.4 协议安全性
在形式化证明安全近似模式匹配协议的安全性之前，我们先从直观上分析该协议的安全性.首先，鉴于茫然传输扩展协议是安全的，所以用户仅能够得到其选择的消息，且数据库方无法得知用户的选择比特.又因为每次选择的随机数是不同的，所以用户无法获得关于文本t的信息.如此，用户可以安全地获得盲化后的比特异或值.其次，数据库方使用其公钥加密αi并发送给用户，其目的是使得用户无法解密密文，因而无法得知αi，也无法计算文本子串ti与模式p之间的汉明距离.而用户使用随机数盲化汉明距离，目的是使得数据库方无法得知ti与模式p的汉明距离.值得注意的是，此处我们使用的随机数是不同的，因此用户无法得知关于汉明距离的信息.此外，用户将多项式的系数用自己的公钥加密后再发送给数据库方，如此数据库方无法解密恢复出多项式.数据库方在茫然计算多项式后，对结果进行盲化，如此，用户在解密时无法获得结果而数据库方可使用自己之前选择的随机数恢复出结果当且仅当ti与模式p之间的汉明距离小于τ时，茫然多项式计算的结果才会与K相等.最后，鉴于隐私等值比较在半诚实敌手模型下是安全的，因此用户仅能够在匹配时获得结果1.
我们给出安全近似模式匹配协议的形式化安全证明：
定理1. 假设茫然传输协议和隐私等值比较协议在半诚实敌手模型下是安全的，加密方案是CPA安全的，根据定义1，协议πAPM在半诚实敌手模型下能够安全计算功能函数FAPM.
证明. 我们在(FOTE,FPEQT)-混合模型中证明协议πAPM的安全性，其中FOTE与FPEQT是理想功能函数.我们分别对数据库方D和用户U被腐化2种情况进行证明.
1) 数据库方D被腐化
数据库方D的视图包括其接收到的来自用户U的消息：
以及来自FOTE与FPEQT的空输出.
数据库方D的视图：
Vie
={(t,m,τ),⊥,
假设数据库方D被多项式时间敌手A腐化.我们构建一个多项式时间模拟器SD，SD调用敌手的输入输出且扮演诚实方U的角色与敌手交互.模拟器的行为：
① SD模拟理想功能函数FOTE的执行.
② SD随机选择2个值
和Ri，而后计算
并将结果发送给敌手A.
③ SD用全零多项式
替代多项式
并用pk2加密全零多项式的系数，然后将密文发送给敌手A.
④ SD随机选择
并将
发送给敌手A.
⑤ SD模拟理想功能函数FPEQT的执行.
我们可以得到模拟器SD的输出：
Outpu
={(t,m,τ),⊥,
我们需要证明的是
首先，因为FOTE是理想功能函数，所以:
其次，由于
与Ri是SD随机选择的，所以敌手A无法区分
与Epk1(ri)×Epk1(βi)/Epk1(αi).再次，由于全零多项式的系数是使用pk2加密后发送给敌手A的，敌手无法解密密文，因而无法区分
与
此外，
由于
与
都是随机选择的，所以与
的分布对于敌手来说是不可区分的.最后，由于FPEQT是理想功能函数，所以
如此可以推出
得证.
2) 用户U被腐化
用户U的视图包括接收到的来自数据库方D的消息
以及FOTE与FPEQT的输出.
用户U的视图：
假设用户U被多项时间敌手A腐化.我们构造一个多项式时间模拟器SU，SU调用敌手的输入输出并且扮演诚实方D的角色与敌手交互.模拟器SU的行为：
① SU选择随机数
其中1≤i≤n-m+1.模拟器SU模拟理想功能函数FOTE，并将输出发送给敌手A.
② SU计算
然后将
发送给敌手A.
③ SU随机选择然后将
发送给敌手A.
④ SU模拟理想功能函数FPEQT的执行，并将bi∈{0,1}发送给敌手A，其中协议输出位置i对应的bi为1，其余为0.
我们可以得到模拟器SU的输出：
我们需要证明的是
首先，因为FOTE是理想功能函数，所以:
其次，由于
与αi都是随机数，所以敌手A无法区分
与Epk1(αi).再次，由于是SU随机选择的，所以
与
的分布对于敌手来说是不可区分的.最后，由于FPEQT是理想功能函数，所以
如此，
得证.
综上所述，我们完成对定理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]O(1) O(nm) O(nm)文献[6]O(1)O(nm)O(nτ)文献[10]O(τ)O((n+m)τ)O((n+m)τλ)本文协议O(1)O(nτ)O(nm)
首先，我们构造的协议同文献[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® CoreTM i5 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时协议在不同设置下的运行时间
m协议在不同设置下的运行时间∕sn=211n=212n=213n=214264.147.8216.0330.94277.05714.1830.6759.872811.7530.8752.50106.242919.8846.37120.65241.0321028.6787.33191.97425.59
注：m为模式长度；n为文本长度.
此外，我们又设置τ=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是数据库方和用户的输入长度, τ是近似匹配协议设定的阈值.在将来的工作中，我们将研究更为高效的近似模式匹配协议构造，并着重研究恶意敌手模型下安全模式匹配协议的构造.
[1]Yao A C. Protocols for secure computations[C] //Proc of the 23rd Annual Symp on Foundations of Computer Science (FOCS82). Los Alamitos, CA: IEEE Computer Society, 1982: 160-164
[2]Yao A C. How to generate and exchange secrets[C] //Proc of the 27th Annual Symp on Foundations of Computer Science (FOCS86). Los Alamitos, CA: IEEE Computer Society, 1986, 162-167
[3]Troncoso-Pastoriza J R, Katzenbeisser S, Celik M. Privacy preserving error resilient DNA searching through oblivious automata[C] //Proc of the 14th ACM Conf on Computer and Communications Security. New York: ACM, 2007: 519-528
[4]Gennaro R, Hazay C, Sorensen J S. Text search protocols with simulation based security[C] //Proc of the 13th Workshop on Public Key Cryptography. Berlin: Springer, 2010: 332-350
[5]Hazay C, Toft T. Computationally secure pattern matching in the presence of malicious adversaries[G] //LNCS 6477: Advances in Cryptology (ASIACRYPT 2010). Berlin: Springer, 2010: 195-212
[6]Hazay C, Toft T. Computationally secure pattern matching in the presence of malicious adversaries[J]. Journal of Cryptology, 2014, 27(2): 358-395
[7]Vergnaud D. Efficient and secure generalized pattern matching via fast Fourier transform[G] //LNCS 6737: Progress in Cryptology (AFRICACRYPT 2011). Berlin: Springer, 2011: 41-59
[8]Fischer M J, Paterson M S. String matching and other products[C] //Proc of the SIAM-AMS Complexity of Computation. New York: ACM, 1974: 113-125
[9]Yasuda M, Shimoyama T, Kogure J, et al. Secure pattern matching using somewhat homomorphic encryption[C] //Proc of the 5th ACM Workshop on Cloud Computing Security Workshop. New York: ACM, 2013: 65-76
[10]Samadani M H, Berenjkoob M, Blanton M. Secure pattern matching based on bit parallelism[J]. International Journal of Information Security, 2019, 18(3): 371-391
[11]Baeza-Yates R, Gonnet G H. A new approach to text searching[J]. Communications of the ACM, 1992, 35(10): 74-82
[12]Zarezadeh M, Mala H, Ladani B T. Efficient secure pattern matching with malicious adversaries[J/OL]. IEEE Transactions on Dependable and Secure Computing, 2020[2021-09-06]. https://doi.org/10.1109/TDSC.2020.3009595
[13]Wei Xiaochao, Zhao Minghao, Xu Qiuliang. Efficient and secure outsourced approximate pattern matching protocol[J]. Soft Computing, 2018, 22(4): 1175-1187
[14]Rabin M O. How to exchange secrets by oblivious transfer, TR-81[R]. Cambridge, MA: Harvard University, 1981
[15]Even S, Goldreich O, Lempel A. A randomized protocol for signing contracts[J]. Communications of the ACM, 1985, 28(6): 637-647
[16]Beaver D. Correlated pseudo randomness and the complexity of private computations[C] //Proc of the 28th Annual ACM Symp on Theory of Computing. New York: ACM, 1996: 479-488
[17]Ishai Y, Kilian J, Nissim K, et al. Extending oblivious transfers efficiently[G] //LNCS 2729: Advances in Cryptology (CRYPTO2003). Berlin: Springer, 2003: 145-161
[18]Kolesnikov V, Kumaresan R. Improved OT extension for transferring short secrets[C] //Proc of the 33rd Annual Cryptology Conf. Berlin: Springer, 2013: 54-70
[19]Asharov G, Lindell Y, Schneider T, et al. More efficient oblivious transfer and extensions for faster secure computation[C] //Proc of the 20th ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 535-548
[20]Naor M, Pinkas B. Oblivious transfer and polynomial evaluation[C] //Proc of the 31st Annual ACM Symp on Theory of Computing. New York: ACM, 1999: 245-254
[21]Freedman M J, Ishai Y, Pinkas B, et al. Keyword search and oblivious pseudorandom functions[C] //Proc of the 2nd Theory of Cryptography Conf. Berlin: Springer, 2005: 303-324
[22]Freedman M J, Nissim K, Pinkas B. Efficient private matching and set intersection[C] //Proc of the 21st Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2004: 1-19
[23]Zhao Yongjun, Chow S S M. Can you find the one for me?[C] //Proc of the 17th Workshop on Privacy in the Electronic Society. New York: ACM, 2018: 54-65
[24]Kolesnikov V, Kumaresan R, Rosulek M, et al. Efficient batched oblivious PRF with applications to private set intersection[C] //Proc of the 23rd ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2016: 818-829
[25]Hazay C, Lindell Y. Efficient Secure Two-party Protocols: Techniques and Constructions[M]. Berlin: Springer, 2010
[26]Goldreich O, Micali S, Wigderson A. How to play any mental game—A completeness theorem for protocols with honest majority[C] //Proc of the 19th ACM Symp on Theory of Computing. New York: ACM, 1987: 218-229
[27]Song Xiangfu, Gai Min, Zhao Shengnan, et al. Privacy-preserving statistics protocol for set-based computation[J]. Journal of Computer Research and Development, 2020, 57(10): 2221-2231 (in Chinese)(宋祥福, 盖敏, 赵圣楠, 等. 面向集合计算的隐私保护统计协议[J]. 计算机研究与发展, 2020, 57(10): 2221-2231)
