随着机器学习、人工智能、物联网等理论技术的不断深入和发展，人们的生活和工作方式有了很大的改变.这其中，各种智能设备所构建的智能环境深刻影响着人们的生活甚至思维方式.比如人们使用智能手环监测生命体征、使用智能驾驶模式开车出行、使用智能门锁进行身份认证等.在带给人类便利和辅助的同时，智能环境也出现诸多必须引起重视的问题和隐患：1)智能系统在获取个人数据的同时必然存在隐私泄露[1-2]问题，因此保障用户的数据隐私性势必会成为研究的热门;2)在智能环境中用户的设备大多数是资源有限的，即不能支持大规模的计算和通信任务，因此就要求所设计的算法或协议必须是轻量级的，这样才能满足资源受限设备的工作条件.本文即从上述2个需求出发，考虑在智能场景中设计安全、高效的模式匹配协议，以满足当下更多智能设备的实际需求.
模式匹配协议是一个典型的安全两方计算协议，其考虑2个参与方，即数据库方和用户方，持有模式信息的用户期望查询其模式在数据库方的数据中存在的信息(比如是否存在、存在位置等).考虑隐私性，用户在查询过程中不希望将自己的模式信息暴露给对方，此外还希望仅有自己知道匹配的结果.而数据库方出于经济或竞争等原因，也不希望将自己所持有的数据信息告知用户，这也正是我们设计安全的模式匹配协议的初衷和目标.安全模式匹配协议在诸多领域有着广泛的应用，比如基因匹配、人脸识别、病毒检测等.以计算机病毒检测为例，一般的杀毒软件公司拥有自己强大的病毒库，当用户怀疑自己的手机或电脑中毒后，便会通过杀毒软件检测并与病毒库中的病毒信息进行匹配，最终决定是否删除或接受某些可疑文件.通过这种方式，用户的数据隐私势必要遭到威胁，杀毒软件公司在提供病毒扫描服务过程中有可能会窥测到用户其他私密的个人信息.因此，通过设计安全的模式匹配协议，可以实现在保护用户数据文件隐私的前提下完成病毒查杀的目的.
除了考虑安全性，智能环境中资源受限设备的效率问题也是另一个亟需解决的问题.当前，云计算为用户的数据存储和计算提供了极大的便利，用户可以将本地数据以某种安全的形式上传至云服务器，并委托云服务器计算，从而达到减轻本地计算负担的效果.因此在各种智能环境应用场景中引入云服务器进行辅助计算的思想，对于资源受限设备而言无疑是一种有效的途径.
下面我们详细论述一下云辅助安全多方计算及安全模式匹配协议的相关工作.
1 相关工作和主要工作
1.1 相关工作
1) 云辅助安全多方计算.安全多方计算[3-4](secure multi-party computation, SMPC)考虑在分布式场景中多个参与方使用各自的私有输入，安全计算某个功能函数并各自得到输出.几乎所有的密码学协议均可以使用安全多方计算模型来刻画.模式匹配协议作为一个具体的安全两方计算问题，也需要在两方模型下构造协议并证明.传统的SMPC场景中并不存在外部服务器，因此参与方的计算量通常都与所计算的函数相关.随着云计算的兴起，将云辅助的概念引入多方计算场景，对于提高部分参与方的效率有着很大的益处.云辅助安全多方计算的概念最早是由Kamara等人[5-6]提出，他们在标准安全多方计算模型中引入一个或多个外部服务器，用以承担部分参与方实体的计算任务，从而减少参与方的计算量，使得安全协议的效率得以提高.相关文献[7-12]针对基于Yao混乱电路的安全多方计算通用协议，给出诸多基于云辅助的高效协议构造，这些云辅助的安全协议较之于标准模型下的协议有很大的效率提升，尤其适用于某些资源受限设备存在的计算场景.
此外，还有诸多工作在云辅助模型下考虑某些具体问题的安全计算.比如隐私集合求交[13-15]、茫然传输[16]等.
2) 安全模式匹配协议.安全模式匹配协议是一个具体的安全两方计算问题，其主要涉及数据库方和模式方2个参与方.其中，数据库方有一个文本t，模式方拥有一个模式p并希望查询该模式在t中是否出现或出现的位置信息.与此同时，要保证模式信息和匹配结果对数据库方是保密的，且数据库的文本对于模式方也是未知的(除了部分匹配成功的信息).自2007年Troncoso-Pastoriza等人[17]最先考虑该协议并基于茫然自动机求值问题构造协议以来，有诸多工作基于不同的密码工具和技术给出安全高效的构造.比如Hazay等人[18-19]使用茫然伪随机计算在隐蔽敌手和恶意敌手模型下实现隐私集合求交和模式匹配协议的高效设计.Katz等人[20]则基于Yao混乱电路给出更一般化的构造，即将模式匹配问题转化成等价电路并结合其它密码学工具实现安全的模式匹配，他们的协议可以很好地应用于隐私DNA匹配问题中.魏晓超等人[21]基于秘密分享和茫然传输给出另一种构造方式，使用茫然传输(oblivious transfer, OT)扩展技术可以极大地提高协议效率.
除了标准的模式匹配问题，近年来针对近似模式匹配[18-19,22-23]、带通配符模式匹配[18-19,24-29]和云辅助模式匹配[30-32]等功能性扩展问题的研究越来越引起国内外学者的研究.这些问题的研究更加符合一些实际的应用场景，比如基因匹配等需要使用近似模式匹配，带通配符模式匹配可以实现批量数据的查询.而云辅助模式匹配则是针对云辅助加密数据的匹配，更符合当前云计算的背景.
1.2 本文的主要工作
本文首次在云辅助计算模型下研究安全模式匹配协议，旨在设计出可以满足智能环境中资源受限设备的安全协议.如图1中的系统模型所示，数据提供商和用户作为传统两方模式匹配协议中的2个参与方，分别提供数据库信息和模式信息.除此之外，我还引入2个独立的外部云服务器，其目的是辅助用户并承担其复杂的计算任务，从而提高用户的效率.整个系统需要保证用户在不泄露模式信息(数据供应商和云服务器均不获取模式信息)的前提下查询其模式在数据供应商的数据库中出现的位置信息.
Fig. 1 The system model of two-cloud-assisted pattern matching
图1 双服务器辅助模式匹配系统模型
考虑这样一个场景，数据供应方是杀毒软件企业，其拥有大规模的计算机病毒库，而手机用户希望在不泄露文件隐私的前提下实现本地的病毒检测.鉴于手机用户的计算资源受限，不可能与病毒库执行大量的交互和操作，因此可以考虑引入云服务器来承担手机用户的计算任务，而用户仅需要知道最终的检测结果即可.鉴于云服务器的不可信性，手机用户不希望将自己的文件信息以及最终的检测结果暴露给云服务器或杀毒软件企业，因此需要采取措施保障这些信息的隐私性.此外，病毒库作为杀毒企业的隐私和资产因其重要性也必须受到保护，因此，所设计协议还需要保障病毒库的信息不被泄露.对于以上各种安全需求，我们将在云辅助安全两方计算模型中给出形式化的定义.
本文的贡献主要包含3个方面：
1) 首次在云辅助模型下研究安全模式匹配协议的高效构造，将模式持有方的计算外包至云服务器，所设计的协议适用于当前智能环境中资源受限的设备，比如手机等移动终端.此外，我们在双服务器模型下给出了云辅助模式匹配协议功能函数的形式化描述.
2) 基于云辅助模式匹配协议功能函数的特性，我们基于0-秘密分享方案和茫然传输协议给出协议的具体构造.协议基本思想主要是使用0-秘密分享份额和随机数表示一个位值，并结合OT协议将匹配问题等价转化为0值的重构.为了减轻模式持有方的计算开销，我们将模式信息盲化之后分享至2个独立的云服务器.因此，原本应当在数据库端和模式端执行的OT协议也转移到数据库端和云服务器之间.通过这种方式，云服务器取代了模式端的主要工作，这使得模式端的计算代价大大减少，其仅需要做一些简单的异或操作，避免了OT协议中复杂的公钥操作.假设云服务器和参与方是不合谋的，协议在半诚实敌手模型下是安全的.
3) 双服务器辅助的安全模式匹配协议需要参与方之间执行4轮交互，模式端(即资源受限设备)仅需要执行少量异或操作.使用OT扩展技术，可以将数据库端和云服务器之间的OT协议数目从O(nm)降至O(k)，其中n和m分别是数据库和模式的长度，k是OT扩展协议的基础OT数，k≪nm.
2 基本知识和安全定义
2.1 茫然传输及其扩展协议
茫然传输(OT)协议作为密码学中的基础原语，自1981年Rabin[33]提出之后，广泛应用于安全多方计算、隐私集合求交、茫然伪随机函数计算等诸多密码学协议中.传统的1-out-of-2茫然传输协议
涉及发送方和接收方2个参与方，其中发送方输入一个有序数对(x0,x1)，接收方输入一个位值σ∈(0,1)，协议结束后接收方仅能获得xσ这一个值.与此同时，协议需要保证发送方不知道接收方选择的哪一个值，而接收方也不知道其没有选择的值x1-σ的任何信息.茫然传输协议的功能函数FOT描述为：
FOT功能函数
输入：
① 发送方输入2个有序值(x0,x1)∈{0，1}*；
② 接收方输入一个选择位σ∈(0,1).
输出：
① 接收方输出xσ；
② 发送方无输出.
OT协议可以基于各种不同的困难问题构造而来，且其本身仅涉及少量的模幂运算，具有很高的效率.然而，作为工具运用到其他密码学协议中时，往往需要数以万计的OT协议，因此所有OT协议的效率往往成为影响其它密码协议的瓶颈问题.鉴于此，Ishai等人[34]在2003年提出了OT扩展(oblivious transfer extension)技术，其可以运用较少量的OT协议实现大量OT的传输效果.比如可以使用128个基础OT加上一些快速的对称密钥操作，实现106这么多OT协议的传输效果.因此对于提升使用大量OT的密码协议的效率，OT扩展技术起到至关重要的作用.当前，基于OT扩展的隐私集合求交、茫然伪随机计算等协议较之于其它实现技术有着更好的效率.本文也将使用OT扩展技术来改进云辅助模式匹配协议的效率.
2.2 计算不可区分性
假设2个分布总体X={X(a,n)}a∈{0,1}*;n∈N和Y={Y(a,n)}a∈{0,1}*;n∈N是计算不可区分的，表示为X≡Y，则对任意一个非均匀多项式时间算法D总存在一个可忽略函数μ(·)，对于每个a∈{0,1}*和每个n∈N，有不等式成立：
|Pr[D(X(a,n)=1)]-
Pr[D(Y(a,n)=1)]|≤μ(n).
2.3 安全性定义
本文的协议主要在云辅助安全两方计算模型下考虑其安全性.该模型最早由Kamara等人[5-6]提出，其在标准的安全两方计算场景中引入一个或多个云服务器辅助参与方完成计算.此外，他们还基于理想
现实模拟范式给出形式化的安全性定义.然而，鉴于该模型规定云服务器与参与方之间不能合谋，因此上述安全性定义较之于标准安全两方计算的理想现实模拟范式有所弱化，即只要求达到参与方“部分模拟”的程度即可.我们考虑的敌手主要是半诚实的，要求他们严格执行协议，但是允许其通过所窥探的消息推测出其他额外信息.此外，我们还假设需要2个云服务器的存在，且要求云服务器之间、云服务器和参与方之间、参与方之间是不能合谋的，这也正是Kamara等人[5-6]提出的云辅助安全两方计算模型的基本假设.
首先我们描述部分理想现实模拟范式中的现实和理想世界执行过程和输出表示.
现实世界执行.现实协议包含2个参与方实体和2个云服务器.每个参与方拥有自己的输入信息，而云服务器没有输入.假设每个敌手仅能腐化一个参与方且不与其他敌手合谋.令OUTj表示所有诚实方的输出，OUTi表示被腐化方在协议中的视图，则用{REALi(n,x,y;r,z)}={OUTj: j∈H}∪OUTi表示协议π的第i个部分输出，其中H表示所有诚实方的集合.
理想世界执行.理想世界中假设存在一个可信第三方，所有参与方将输入发送给可信第三方并得到相应的输出信息.同上所述，令OUTj表示所有诚实方从可信第三方得到的输出信息，OUTi表示被腐化方自己的确定输出，则理想世界执行中的第i个部分输出可以表示为
{IDEALi(n,x,y;r,z)}=
{OUTj: j∈H}∪OUTi，
其中，H表示所有诚实方的集合.
下面我们给出云辅助安全两方计算的安全性定义：
定义1. 令f:{0,1}*×{0,1}*→{0,1}*是一个双输入单输出的功能函数，π是一个真实协议.若协议π在双服务器辅助模型下安全计算f，当且仅当，针对现实世界中每个非均匀概率多项式时间敌手(A1,A2,A3,A4)，总存在理想世界中的非均匀概率多项式模拟器{Simi}i∈[4]，对于2个参与方的输入x和y，以及随机带r和辅助输 z，以及i∈[4]满足：
{IDEALi(n,x,y;r,z)}n∈N≡
{REALi(n,x,y;r,z)}n∈N，
其中，参与方的输入x,y∈{0,1}*，S=(S1 S2 S3 S4)，Si=Simi(Ai)，r=(r1,r2,r3,r4)，n∈N是安全参数.
3 安全云辅助模式匹配协议
3.1 安全云辅助模式匹配功能函数
本文所考虑的云辅助符模式匹配功能函数FCPM中主要涉及4个参与方数据供应商DP、用户U以及2个云服务器C1和C2，其中是DP和U分别持有数据库t和模式信息p，而云服务器C1和C2作为辅助参与方代替用户承担大量的计算任务，从而减少用户的计算代价.尤其是在当前智能环境中，用户往往都是具有受限计算能力的设备，将大量计算任务外包至云服务器无疑能提高用户的效率，同时不影响用户享受智能场景带来的便利.功能函数FCPM要求在云服务器的辅助下，用户U能得到它的模式在数据供应商DP的数据库中出现的位置信息，从而实现匹配的功能.
我们给出功能函数FCPM的形式化描述：
FCPM功能函数
输入：
① 数据供应商DP输入长度为n的二进制字符串t及整数m；
② 用户U输入长度为m的二进制字符串p以及整数n；
③ 云服务器C1和C2无输入.
输出：
① 用户U输出模式p在 t中出现的位置；
② 数据供应商DP和云服务器均无输出.
与此同时，功能函数FCPM要保证3个安全属性：1)用户U的模式信息对于数据供应商和云服务器均是保密的；2)数据供应商的数据信息对于云服务器是保密的；3)用户U仅在匹配成功的情况下才能得到相应的位置信息，而当匹配失败时，并不能得到关于数据供应商的数据的任何信息.
3.2 双服务器模型下的安全模式匹配协议构造
在本节中，我们在双服务器辅助模型下给出一个安全高效的云辅助模式匹配协议构造.协议的基本框架和思想主要源于Wei等人[21]基于OT和秘密分享方案构造的安全模式匹配协议.与之不同的是，我们引入了2个独立的云服务器来降低资源受限用户(如手机等移动智能设备)的计算开销，从而使得协议更适用于当前的各种智能场景.此外，我们使用的秘密分享方案是一种特殊的0-秘密分享，即选取一定数量的随机数使其异或值为0，这些随机数即为分享份额.这种秘密分享方案更为简单，仅涉及到异或操作，因此更加高效.
协议的流程大致分为3个阶段：
1) 输入盲化阶段.用户和数据供应商使用相同的随机置换来改变各自的输入值，这里的随机置换可以是用户选择之后发给数据供应商，也可以是提前共享的.之后，用户将盲化后的模式信息分成等长的2部分，并分别发送给2个云服务器C1和C2.这样每个云服务器就获得了部分盲化后的模式信息.
2) 茫然传输阶段.茫然传输协议主要是在数据供应商和云服务器之间进行的，其中数据供应商作为发送方，2个云服务器分别扮演接收方的角色.首先，数据供应商根据其随机置换后的输入值，使用0-秘密分享方案表示每一个位信息.具体地，使用一个有序数对来表示输入的每一个位值，这个数对中包含一个合法的0-秘密分享份额和一个随机数.具体的顺序取决于位是0或是1.之后，数据供应商和云服务器执行OT协议，其中数据供应商作为发送方输入生成好的有序数对，云服务器作为接收方输入接收到的部分盲化模式信息.最终2个云服务器分别接收到输出，并针对每一个子串计算一个异或值发送给用户.
3) 用户输出阶段.用户计算从2个云服务器接收到的数值的异或值，并根据异或值是否为0确定相应子串是否匹配成功，最终输出结果.
协议具体表述为：
协议1. 安全云辅助模式匹配协议πCPM.
输入：数据供应商DP输入一个长度为n的二进制字符串t和一个整数m，用户U输入一个长度为m的二进制字符串(模式)p和一个整数n，云服务器C1和C2没有输入；
输出：用户U输出模式p在 t中出现的位置.
协议：
步骤1. 用户U随机选择一个长度为m的二进制字符串r计算p′= p⊕r，并将p′作为置换后的新模式发送给云辅助服务器(即选择一个随机置换来盲化初始的模式p).具体地，用户U将p′的前
m2
个位发送给云服务器C1，并将余下的位值发送给云服务器C2.通过这一步操作，用户将盲化后的模式“分享”至2个独立的云服务器中.
步骤2. 此外，用户U将所使用的随机二进制串r发送给数据供应商DP，目的是让数据供应商使用r针对t中的每一个m位长的子串做同样的盲化操作(随机串r也可以是U和DP提前共享的信息).
步骤3. 数据供应商DP使用秘密分享技术来表示每一个盲化后的m位长子串.核心技术是使用一对数值来表示 m位长子串的每个位值，这对数值需要满足其中之一是合法的0-秘密分享份额，另一个是一个随机值，且合法的秘密分享份额在数对中的位置要与该位值信息对应(即如果位为0，则合法份额在第1位；若位为1，则合法份额在第2位).具体表示方法为：
① 对于t中每一个m位长子串
其中1≤i≤n-m+1，DP首先随机选择m个值(si，1，si，2，…，si,m)满足si，1⊕si，2⊕…⊕si,m= 0，其中每个数值的长度为某统计学安全参数s.
② 此外，UD为每一个si, j选择另一个等长的随机数
并使用si, j和
组成的有序数对来表示ti的第j位
其中i是字串ti的下标值，j是ti中的第j个位下标值.具体地，假设
表示该位的值，以上数对的顺序应当是
反之若
则以上数对顺序应为
其中si, j是满足异或值为0的合法分享份额，而是一个随机值.
因为数据供应商的输入是n位长的字符串t，其中包含n-m+1个m位长的子串，因此DP需要对每一个字串均做上述操作，即共生成m(n-m+1)个有序数对.这些根据子串生成的有序数对会被用于为后序茫然传输协议中，作为发送方(即数据供应商)的输入信息.
步骤4. 数据供应商DP分别和云服务器C1，C2运行1-out-of-2茫然传输协议.其中DP作为OT协议中的发送方，其输入为步骤3中构造的有序数对.而云服务器C1,C2作为OT协议中的接收方，其输入是从用户那里接收到的盲化后的部分模式信息.注意到，每个云服务器的输入长度为m的一半，因此数据供应商分别使用对应于字串的前一半有序数对和后一半有序数对与C1和C2执行OT协议.OT协议执行完成以后，作为接收方的云服务器C1和C2分别得到有序数对si, j和中的某一个值，具体得到哪一个则根据其掌握的部分模式信息.然后，针对每一个m位长子串，C1和C2分别使用接收到的这些值作异或操作，生成n-m+1个异或值.假设C1生成的异或值分别是
生成的异或值分别是
则C1和C2分别将它们按照顺序发送给用户U.
步骤5. 用户U计算
并判定其中哪些值为0.最终确定模式p是否在t中出现的位置，具体地：
① 若存在
其表示t中第i个位置开始的m位长字串和模式匹配成功，则输出i;
② 否则输出⊥，表示匹配失败.
3.3 协议正确性
协议1的正确性意味着在协议成功运行之后，用户U最终一定得到正确的结果.具体而言，如果在数据供应商的数据t中存在与模式串相等的子串，则用户一定会输出相同子串开始的位置；反之，若t中无相同子串，则用户输出⊥表示匹配失败.首先需要说明的是，用户U和数据供应商DP使用相同的置换信息对其各自的输入作了相同的处理，因此如果存在子串和模式串相同，则置换之后的值依然相等，因此并不影响匹配的正确性.我们以上2种情况分别阐述，以此说明协议的正确性：
① 如果数据供应商的输入t中至少存在一个m位长的子串与模式p相等，则用户必然输出该子串的起始下标.假设子串
和模式p相等，则通过相同置换之后的2个字符串依然相等.因此，在数据供应商和2个云服务器之间执行的OT协议中，作为接收方的云服务器接收到的全都是有序数对中的合法分享份额.当用户U最终接收到这些值并计算其异或值之后，必然会出现结果为0这一事实，并最终输出i作为匹配成功的子串下标值.
② 如果匹配失败，则表明t中所有n-m+1个m位长子串均与模式p不相等.不失一般性，考虑从t中第1个位开始的m位长子串，则其中必然存在至少一个位信息与模式p中相对应的比特信息不同，不妨设该位置为j，即tj≠pj.因此，在茫然传输协议中，在第j个位置上云服务器C1或C2得到的一定是某个随机数，而不是数据供应商选择的对于0值的合法秘密分享份额.这样，用户U最终求得的异或值必然不是0，而是某个随机的结果.这也就表明该子串与模式匹配失败.
综上所述，用户U在匹配成功和失败情况下均能输出正确的结果，因此协议正确性满足.
3.4 协议安全性
在给出协议安全性的形式化证明之前，我们先从直观上分析一下上述协议的安全性.首先我们假设云服务器之间、以及云服务器与参与方之间是不能合谋的，这一假设就保证了用户的模式信息对于数据提供商以及云服务器是保密的.这其中的关键点就在于用户将随机置换和最终的盲化结果分别发送给数据供应商和云服务器，只要假设他们不合谋，用户的输入隐私性就会得以保证.此外，云服务器的不合谋也使得用户的输出隐私性得到保障.因为如果2个云服务器共享最终得到的异或值，通过判断结果是否为0就可以推断出匹配的结果.再考虑数据供应商的输入隐私问题，鉴于OT协议的安全性，云服务器和用户仅能在匹配成功的情况下得到相应的子串相等信息.而对于那些匹配不成功的子串，任何信息都不会泄露.下面我们根据安全性定义1给出上述云辅助模式匹配协议的形式化安全性证明：
定理1. 假设茫然传输协议在半诚实敌手模型下是安全的，且2个云服务器之间以及云服务器与参与方之间是不合谋的，则根据定义1，协议πCPM在云辅助安全两方计算模型下针对半诚实敌手安全计算功能函数FCPM.
证明. 我们在双服务器辅助的安全两方计算模型下证明上述协议的安全性.需要强调的是，我们使用混合模型的证明机制，即云辅助模式匹配协议中使用到的茫然传输协议由理想功能函数FOT实现.假设协议中涉及到的4个参与方DP,U,C1和C2分别被4个相互独立的现实敌手A1,A2,A3和A4控制，则我们构造4个独立的理想世界模拟器S1,S2,S3和S4，执行模拟过程：
1) 模拟器S1按照以下步骤模拟腐化DP的现实敌手A1：S1调用敌手A1的输入t，m和n并将这些值发送给计算功能函数FCPM的可信第三方.之后模拟器S1模拟OT协议的执行，扮演诚实接收方C1和C2分别发送一个长度为m2和m-m2的随机二进制串给功能函数FOT.最后，模拟器S1输出敌手A1的输出，并终止模拟.根据定义1的安全性定义，需证明理想世界模拟和现实世界协议中的第1个部分输出是计算不可区分的，即证明成立：
{IDEAL1(n,x,y;r,z)}n∈N ≡
{REAL1(n,x,y;r,z)}n∈N.
从协议πCPM中可以看出敌手A1在协议中的视图主要包含在OT协议中从云服务器那里接收到的值.而模拟器在模拟的过程中并不知道这些值是什么，因此选择了2个随机二进制串作为接收方的输入.这也是理想世界模拟过程与现实协议执行中唯一的差别.鉴于我们所使用的OT协议针对半诚实敌手是安全的，因此发送方(即模拟器)对于接收方(即云服务器)的输入是计算不可区分的.这一安全特性就保证了模拟器S1的模拟过程与真实协议执行是不可区分的.
2) 模拟器S2按照以下步骤模拟腐化用户U的现实敌手A2：S2调用敌手A2的输入p，m和n并发送给计算功能函数FCPM的可信第三方.之后模拟器S2从可信第三方那里得到输出信息(即匹配的结果).不失一般性，假设S2得到的输出是下标集合(i1,i2,…,ir)，即在t中从这些下标开始的m位长子串和模式p相同.之后，模拟器按照如下方式生成其从云服务器那里接收到的消息：1)对于下标集合的任一个索引ij，模拟器随机选择2个长度为s的二进制串
和
且满足
对于下标集合之外的索引，模拟器随机选择2个k位长的字符串且需要保证它们的异或值不为0.最后模拟器输出敌手A2的输出并终止.同上我们需要证明成立：
{IDEAL2(n,x,y;r,z)}n∈N ≡
{REAL2(n,x,y;r,z)}n∈N.
以上2个分布的唯一区别是模拟器随机选择了本应从云服务器那里接收到的信息，而在现实协议中敌手是直接从云服务器处接收到这些值.但是，因为模拟器知道最终的匹配结果，因此它随机选取的这些值和敌手接收到的值所能推导出的信息是等价的.换言之，针对匹配成功的情况，最终2个值的异或值为0；反之如果匹配失败，则2个值的异或值是随机的.因此，上述模拟过程和现实协议计算不可区分.
3) 模拟器S3按照以下步骤模拟腐化云服务器C1的现实敌手A3：模拟器随机选择一个m2位长的字符串，并模拟功能函数FOT.具体地，模拟器扮演OT中发送方(即数据供应商)的身份，随机生成所有的m(n-m+1)个有序数对作为发送方的输入.最后，S3输出A3的输出并终止模拟.我们知道云服务器C1是没有输入输出的，且其在协议中的视图主要包含从用户U处接收到的部分盲化后的模式值，以及在OT协议中的视图.鉴于OT协议的安全性，模拟器随机选择发送方的输入值对于敌手而言是不可区分的，因此分布也是计算不可区分的：
{IDEAL3(n,x,y;r,z)}n∈N ≡
{REAL3(n,x,y;r,z)}n∈N.
4) 模拟器S4模拟腐化云服务器C2的现实敌手A4，情况同上.
综上所述，我们完成对定理1的证明.
3.5 协议效率分析与比较
协议的效率一般从轮复杂度、计算复杂度和通信复杂度3方面考虑.下面我们就这3方面作具体阐述，并与相关工作进行效率比较.
1) 轮复杂度.我们所构造的双服务器辅助模式匹配协议共需要4轮交互.其中在第1轮中，用户将盲化后的模式信息拆分并发送给云服务器，此外，还需将盲化使用的随机置换发送给数据库端.之后的第2轮和第3轮主要体现在OT协议中，因为半诚实模型下的OT协议是一个2轮协议.协议的第4轮中云服务器分别将计算后的数值发送给用户，用户计算并最终得到输出.
2) 计算复杂度.协议的计算复杂度指的是参与方本地的计算量，主要涉及到对称操作(如Hash，异或等)和非对称操作(如模幂运算)，其中对称操作速度快，而非对称操作速度慢、代价大，因此经常用非对称操作的数量来衡量整个协议的计算复杂度.从协议描述中可以看出，资源受限的用户仅针对其输入模式做简单的异或操作.而复杂的非对称操作主要集中在数据库端和云服务器之间执行的OT协议中.假设用户的模式长度为m，数据库端的输入长度为n，则需要对所有的n-m+1个子串分别执行m次OT协议，因此所需OT协议的总数目为n(n-m+1).我们可以使用OT扩展技术减少OT协议的数目，即仅需要执行k次基础OT的数目，并结合一些Hash操作，就能实现上述大量OT的效果.这里的k为安全参数，一般而言，执行128次基础OT便可以实现106个OT协议的效果.
3) 通信复杂度.通信复杂度指的是参与方之间发送和接收的信息数.首先考虑资源受限的用户，其共发送m位的模式信息给云服务器，并从云服务器那里接收到2(n-m+1)个字符串(即生成0-秘密分享的份额或某一随机数，长度为选定的某个安全参数s).此外，在OT协议中，每一次OT执行中接收方和发送方共需要发送4个群元素(各自发送2个)，因此所有的OT协议共需要交换O(nm)个数量级的群元素.
在表1中我们给出文中所构造协议与相关模式匹配协议的比较结果.具体的，我们从协议的轮数、计算复杂度、通信复杂度以及协议模型4个方面对协议进行效率比较.其中计算复杂度和通信复杂度均分为用户量和协议总量2个部分，以此来说明我们协议中用户的优势.此外，表1中n和m分别是模式匹配协议中2个参与方的输入长度，k是使用OT扩展协议的基础OT数目.
首先，从协议模型来看，文献[19,21]均在标准模型下设计协议，而我们的协议是在2个云服务器辅助模型下构造的，适用于资源受限设备存在的智能环境.考虑协议轮数，协议[19]考虑恶意敌手，因此需要6轮交互，而协议[21]和我们的协议均考虑半诚实敌手，因此轮数有所减少，但是均为常数轮.关于协议的计算复杂度，我们从用户和协议总体的计算量2方面进行分析.因为引入了外部云服务器，因此我们协议中的用户仅需要计算少量的XOR操作，而其它协议中的用户(即模式方)均需要执行OT协议，因此需要计算大量的模幂运算.假设，n和m分别是模式匹配协议中2个参与方的输入长度，协议[19]需要计算O(nm)数量级的模幂运算，而协议[21]使用OT扩展技术可以将计算量降至O(k)数量级(k是OT扩展协议的基础OT数目，远小于nm).从协议整体计算复杂度而言，因为我们的协议也基于OT扩展技术，因此计算复杂度与协议[21]一样均为O(k).最后，考虑协议的通信复杂度(即发送群元素的数量)，所有协议的总体通信量均为O(nm).但是，我们协议中的用户仅需要O(n-m)数量级的通信复杂度，因此更适用于手机等资源受限设备存在的智能环境应用中.
Table 1 Efficiency Comparison
表1 协议效率比较
ProtocolsRoundsComputationComplexity (User)ComputationComplexity (Overall)CommunicationComplexity(User)CommunicationComplexity(Overall)Cloud-assistedRef [19]6O(nm)O(nm)O(nm)O(nm)×Ref [21]2O(k)O(k)O(nm)O(nm)×Ours4only XORO(k)O(n-m)O(nm)√
Notes：√ means the protocol is in the cloud-assisted model; × means the protocol is in the standard model.
4 结束语
本文主要考虑适用于智能环境下的安全模式匹配协议设计，首次在云辅助安全两方计算模型下构造了一个高效的模式匹配协议.我们在传统模式匹配协议中引入2个独立的云服务器承担参与方的部分计算任务，从而使得智能环境中某些资源受限设备的效率得以提升.协议主要基于茫然传输和0-秘密分享技术，假设云服务器和用户之间是不合谋的，则我们的协议在半诚实敌手模型下是安全的.协议共需要4轮交互，总体通信复杂度为O(nm)，通过使用OT扩展技术其计算复杂度可以由O(nm)降至O(k)，其中n和m是参与方的输入长度，k≪nm是基础OT的数量.考虑资源受限的用户端，其仅需要执行少量的XOR操作，且仅需要O(n-m)数量级的通信量，因此协议非常适用于手机等之类的设备.
[1]Zhang Yuqing, Zhou Wei, Peng Anni. Survey of Internet of things security[J]. Journal of Computer Research and Development, 2017, 54(10): 2130-2143 (in Chinese)
(张玉清, 周威, 彭安妮. 物联网安全综述[J]. 计算机研究与发展, 2017, 54(10): 2130-2143)
[2] Wang Jice, Li Yilian, Jia Yan, et al. Survey of smart home security[J]. Journal of Computer Research and Development, 2018, 55(10): 2111-2124 (in Chinese)
(王基策, 李意莲, 贾岩, 等. 智能家居安全综述[J]. 计算机研究与发展, 2018, 55(10): 2111-2124)
[3]Yao A C. Protocols for secure computations[C] 
Proc of the 23rd Annual Symp on Foundations of Computer Science (FOCS82). Piscataway, NJ: IEEE, 1982: 160-164
[4]Yao A C. How to generate and exchange secrets[C] Proc of the 27th Annual Symp on Foundations of Computer Science (FOCS86). Piscataway, NJ: IEEE, 1986: 162-167
[5]Kamara S, Mohassel P, Raykova M. Outsourcing multi-party computation[OL]. [2017-08-25]. https:eprint.iacr.org2011272.pdf
[6]Kamara S, Mohassel P, Riva B. Salus: A system for server-aided secure function evaluation[C] Proc of the 19th ACM Conf on Computer and Communications Security. New York: ACM, 2012: 797-808
[7]Carter H, Mood B, Traynor P, et al. Secure outsourced garbled circuit evaluation for mobile devices[J]. Journal of Computer Security, 2016, 24(2): 137-180
[8]Carter H, Lever C, Traynor P. Whitewash: Outsourcing garbled circuit generation for mobile devices[C] Proc of the 30th Annual Computer Security Applications Conf. New York: ACM, 2014: 266-275
[9]Mood B, Gupta D, Butler K, et al. Reuse it or lose it: More efficient secure computation through reuse of encrypted values[C] Proc of the 2014 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2014: 582-59
[10]Jakobsen T P, Nielsen J B, Orlandi C. A framework for outsourcing of secure computation[C] Proc of the 6th Edition of the ACM Workshop on Cloud Computing Security. New York: ACM, 2014: 81-92
[11]Kerschbaum F. Oblivious outsourcing of garbled circuit generation[C] Proc of the 30th Annual ACM Symp on Applied Computing. New York: ACM, 2015: 2134-2140
[12]Jiang Han, Xu Qiuliang. Secure multiparty computation in cloud computing[J]. Journal of Computer Research and Development, 2016, 53(10): 2152-2162 (in Chinese)
(蒋瀚, 徐秋亮. 基于云计算服务的安全多方计算[J]. 计算机研究与发展, 2016, 53(10): 2152-2162)
[13]Kerschbaum F. Collusion-resistant outsourcing of private set intersection[C] Proc of the 27th Annual ACM Symp on Applied Computing. New York: ACM, 2012: 1451-1456
[14]Kerschbaum F. Outsourced private set intersection using homomorphic encryption[C] Proc of the 7th ACM Symp on Information, Computer and Communications Security. New York: ACM, 2012: 85-86
[15]Liu Fang, Ng W K, Zhang Wei, et al. Encrypted set intersection protocol for outsourced datasets[C] Proc of the 2014 IEEE Int Conf on Cloud Engineering (IC2E). Piscataway, NJ: IEEE, 2014: 135-140
[16]Wei Xiaochao, Zhao Chuan, Jiang Han, et al. Practical server-aided k-out-of-n oblivious transfer protocol[G] LNCS 9663: Green, Pervasive and Cloud Computing, 2016. Berlin: Springer, 2016: 261-277
[17]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
[18]Hazay C, Lindell Y. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries[G] LNCS 4948: Theory of Cryptography. Berlin: Springer, 2008: 155-175
[19]Hazay C, Toft T. Computationally secure pattern matching in the presence of malicious adversaries[J]. Journal of Cryptology, 2014, 27(2): 358-395
[20]Katz J, Malka L. Secure text processing with applications to private DNA matching[C] Proc of the 17th ACM Conf on Computer and Communications Security. New York: ACM, 2010: 485-492
[21]Wei Xiaochao, Zhao Minghao, Xu Qiuliang. Efficient and secure outsourced approximate pattern matching protocol[J]. Soft Computing, 2018, 22(4): 1175-1187
[22]Jarrous A, Pinkas B. Secure hamming distance based computation and its applications[G] LNCS 5536: Applied Cryptography and Network Security. Berlin: Springer, 2009: 107-124
[23]Vergnaud D. Efficient and secure generalized pattern matching via fast fourier transform[G] LNCS 6737: Progress in Cryptology (AFRICACRYPT 2011). Berlin: Springer, 2011: 41-58
[24]Baron J, El Defrawy K, Minkovich K, et al. 5pm: Secure pattern matching[G] LNCS 7485: Security and Cryptography for Networks. Berlin: Springer, 2012: 222-240
[25]Yasuda M, Shimoyama T, Kogure J, et al. Secure pattern matching using somewhat homomorphic encryption[C] Proc of the 2013 ACM Workshop on Cloud Computing Security Workshop. New York: ACM, 2013: 65-76
[26]Yasuda M, Shimoyama T, Kogure J, et al. Privacy-preserving wildcards pattern matching using symmetric somewhat homomorphic encryption[G] LNCS 8544: Information Security and Privacy. Berlin: Springer, 2014: 338-353
[27]Saha T K, Koshiba T. An enhancement of privacy-preserving wildcards pattern matching[G] LNCS 10128: Foundations and Practice of Security. Berlin: Springer, 2016: 145-160
[28]Kolesnikov V, Rosulek M, Trieu Ni. SWiM: Secure wildcard pattern matching from OT extension[OL]. [2017-07-26]. https:eprint.iacr.org20171150.pdf
[29]Darivandpour J, Atallah M J. Efficient and secure pattern matching with wildcards using lightweight cryptography[J]. Computers & Security, 2018. [2019-06-01]. https:doi.org10.1016j.cose.2018.01.004
[30]Faust S, Hazay C, Venturi D. Outsourced pattern matching[G] LNCS 7966: Automata, Languages, and Programming. Berlin: Springer, 2013: 545-556
[31]Chase M, Shen E. Substring-searchable symmetric encryption[J]. Proceedings on Privacy Enhancing Technologies, 2015, 2015(2): 263-281
[32]Wang Dongsheng, Jia Xiaohua, Wang Cong, et al. Generalized pattern matching string search on encrypted data in cloud systems[C] Proc of 2015 IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2015: 2101-2109
[33]Rabin M O. How to exchange secrets by oblivious transfer, TR-81[R]. Cambridge, MA: Harvard University, 1981
[34]Ishai Y, Kilian J, Nissim K, et al. Extending oblivious transfers efficiently[G] LNCS 2729: Advances in Cryptology (CRYPTO2003). Berlin: Springer, 2003: 145-161
06
