字符串匹配的保密计算*

张凯鑫， 杨 晨， 李顺东

陕西师范大学 计算机科学学院， 西安 710119

1 引言

在大数据的时代， 越来越多的服务和产品是围绕用户数据(隐私) 建立的. 这样虽然带来了个性化的服务， 提高了服务质量和精度， 但是在数据收集、使用以及公布的过程中， 用户隐私可能暴露， 隐私保护尤为重要. 安全多方计算[1](secure multiparty computation， SMC) 是密码学的一个重要分支， 旨在解决一组互不信任的参与方之间保护隐私的协同计算问题， 为数据需求方提供不泄露原始数据前提下的多方协同计算能力. 在整个计算协议执行过程中， 用户对个人数据始终拥有控制权， 只有计算逻辑是公开的， 计算参与方只需参与计算协议， 无需依赖第三方就能完成数据计算， 并且参与各方拿到计算结果后也无法推断出原始数据.

在密码学与信息安全、计算科学领域中， 安全多方计算有着举足轻重的作用， 是信息社会隐私保护的核心技术， 主要包括保密的科学计算问题[2-6]、保密的计算几何问题[7，8]、保密的统计分析问题、保密的数据挖掘问题[9]， 以及其他安全多方计算问题.

虽然人们研究解决了很多安全多方计算问题， 但这些方案的效率都亟待提高.

目前， 有关字符串计算问题的研究有明文下对字符串匹配算法的改进[10-13]、字符串的近似匹配[14-16]、基于Bloom Filter 的字符串匹配[17-20]、字符串相等[21]等问题. 含通配符的字符串匹配一般用于找出一系列具有相同组成成分的字符串， 即可以找到具有相似结构的字符串， 在生物序列分析、关键词搜索、数据库查询等领域具有重要作用. 例如， 公司想要统计所有员工中姓张的人数， 可以输入SQL 语句select COUNT(id) from people where name =‘张*’ (通配符‘*’ 可以表示任意长度的字符串)，那么张三、张明明、张叶奈珞等人都会被统计. 我们主要研究两个问题: 字符串模式匹配和含通配符的字符串匹配问题.

在文本处理中， 关键字匹配是一个十分常用且重要的功能. 关键字称为模式串P， 在文本T中寻找模式串P出现的所有位置， 解决这种问题的算法叫做字符串模式匹配算法. 现有关于字符串模式匹配的安全多方计算方案有: 文献[21] 将每个字符编码成其ASCII 码的对应二进制数， 用ElGamal 加密算法进行加密计算， 其平均计算复杂性较高; 文献[22] 采用somewhat homomorphic encryption (SHE) 方案和新的数据包装技术， 将二进制数据封装成环空间上的单一密文， 通过计算密文的多个海明距离来判断字符串是否匹配. 该协议虽然提高了效率， 但其只能进行单一的模式匹配(即模式串只能在文本中出现一次). 文献[23] 在恶意模型下设计了字符串模式匹配协议， 本文在半诚实模型下设计协议， 模型不一样. 文献[24]中的协议2 利用Goldwasser-Micali 同态加密算法下设计了字符串模式匹配协议， 将每个字符用其ASCII对应的二进制数异或来进行计算， 其计算复杂性相对较高. 文献[24] 中的协议4 采用了对称密码学算法来进行字符串模式匹配问题的计算， 没有进行任何加密解密操作.

含通配符的字符串匹配问题是对字符串模式匹配问题的扩展. 字符串模式匹配中的模式串P是完整的， 均由字符组成. 而含通配符的字符串匹配， 相当于把模式串P中某些位置的元素用通配符代替， 该通配符可以代表不同数量的不同字母， 相当于是对完整模式串的泛化. 含通配符的字符串匹配问题广泛应用于文件搜索、数据库、正则表达式等领域. 早在20 世纪70 年代， Fischer 等首先在字符串匹配问题中引入通配符[25]这一概念. 在安全计算中， 大多数早期的工作都处理没有通配符[22，26]或只有一个通配符[27，28]的模式. 到目前为止， 我们观察到具有单个通配符的字符串匹配问题是文献[28] 提出的， 但其是在恶意模型下提出的且只适用于单个通配符的问题. 文献[17] 基于加密的Bloom Filter 设计了字符串匹配协议， 文献[18-20] 是在云计算下基于Bloom Filter 构建的字符串匹配协议， 而Bloom Filter 的一个显著缺点是误判的概率是不可忽略的. 这些基于Bloom Filter 的通配符加密方案以不可忽略的概率向用户返回假结果. 文献[29] 采用SHE 加密算法和新的数据包装计算， 将字符串包装成多项式来进行加密计算， 但SHE 的安全性依赖于Ring LWE 问题， 且只能实现有限次的乘法， 其适用性没有Paillier 强.

上述关于含通配符的字符串匹配协议存在的问题总结如下:

(1) 文献[17-20] : 基于Bloom Filter 的加密方案存在一定概率的误判， 不能实现精确的字符串匹配;

(2) 文献[28]: 在恶意模型下只能实现含单个通配符的字符串匹配， 通配符的数量受限使用不灵活;

(3) 文献[29]: 基于SHE 的加密算法设计协议， 但SHE 的安全性依赖于Ring LWE 问题， 且只能实现有限次的乘法， 适用性受限.

为了解决以上出现的问题， 本文在半诚实模型下利用Paillier 公钥加密算法和一种新的编码方法保密判断含通配符的字符串匹配问题， 能够实现含通配符字符串的精确匹配， 且方案使用不受限制. 协议中通配符的使用灵活， 通配符的数量和位置是任意的.

本文的主要贡献如下:

(1) 设计了一种新的编码方法来处理字符串匹配问题， 将每个参与者的保密数据隐藏在向量中， 这种编码方法可以为其他安全多方计算问题提供一种新的途径.

(2) 利用本文设计的编码方法和Paillier 同态加密算法设计了字符串模式匹配的保密判定协议和含通配符的字符串保密匹配协议， 这些协议对半诚实参与者是安全的.

(3) 现有的含通配符的加密方案中， 通配符仅代表单个字符. 本文通配符可以表示任意数量的字符，并且可以位于字符串的任意位置.

(4) 大部分现有的含通配符的加密方案是基于Bloom Filter 构造的， 会出现一定概率的误判. 本文设计的方案能够保证字符串的精确匹配.

2 预备知识

2.1 安全性定义

双方计算. 双方计算是一个将随机输入对映射为输出对的随机计算过程， 可表示成如下的函数形式:

其中f=(f1，f2). 函数f为输入对(x，y) 和输出对(f1(x，y)，f2(x，y)) 之间的映射， (f1(x，y)，f2(x，y) 为随机变量， 其变化范围为一对字符串)， 于是函数f又可记作:

半诚实参与者[30]. 在半诚实模型中要求所有的参与者都是半诚实的. 所谓半诚实参与者是指在协议执行过程中按照协议要求履行协议， 但他们可能会将协议执行过程中获得的信息记录下来， 在执行完协议后试图根据记录的信息推算出其他参与者的输入信息. 本文假设协议的所有参与者都是半诚实的.

模拟范例[30]. 模拟范例在安全性证明中被广泛使用， 相对于其他安全性证明方法， 它可以简便地模拟参与者执行协议的过程.

模拟范例的原理: 如果半诚实参与者用自己的输入和输出进行模拟所得的消息序列与实际过程得到的消息序列不可区分， 则协议是保密的. 如果一个多方计算协议可以进行这样的模拟， 参与者就不能从协议的执行过程中得到其他人的任何信息.

一些记号[30]. 假设参与者是Alice 和Bob.

2.2 Paillier 同态加密系统

3 字符串模式匹配的保密判定协议

问题描述. 字符串模式匹配是判断一个字符串是否为另一个字符串的子串问题. Alice 拥有字符串SA， 长度为n， Bob 拥有字符串SB， 长度为m(m ≤n)， 双方想知道SB是否为SA的子字符串， 且不泄露SA，SB的任何信息.

方案思想. 在字符串SA中挑选第一个字符及与其相邻的m-1 个字符， 组成长度为m的子字符串s1，s1与SB中相同索引下的两个字符用加法同态算法来判断是否相等. 若两个字符相等， 则计算结果为0， 因此判断字符串s1与SB是否相等一共需要进行m次比较. 如果m次比较结果都是0， 说明子字符串s1与SB是相等的， 我们称上述操作为一次循环计算. 第i次循环计算是在字符串SA中挑选第i个字符及与其后面的m-1 个字符， 组成长度为m的字符串si， 字符串si与字符串SB进行计算. 若判断字符串SB是否为字符串SA的子字符串， 共进行n-m+1 次循环计算. 如果n-m+1 次循环计算结果中至少有一次结果全为0， 说明字符串SB是字符串SA的子串. 长度为n的字符串SA有n-m+1个长度为m的子字符串， 因此判断字符串SB是否为字符串SA的子串归约为SA的n-m+1 个子串中至少有一个与SB相等问题. 本文首先将保密的字符串编码成一个向量， 向量元素由字符在全集中对应的两位十进制数表示， 在加法同态性的基础上设计一个高效的协议.

例1 Alice 拥有字符串SA= acdec， 字符c在全集中位于第3 位， 两位十进制表示为13， 其他字符也进行同样的编码， 生成向量A=(11，13，14，15，13)， 并发送给Bob.

(1) Bob 拥有字符串SB=ac， 按照上述的编码方法得到向量B=(11，13).

3.1 具体协议

协议1 保密判断字符串SB 是否为字符串SA 的子串输入: Alice、Bob 各自的私密字符串SA = a1a2···an， SB = b1b2···bm.输出: P(SA，SB).(1) (G，D，E) 是Paillier 同态加密方案， τ 是设定的安全参数， Alice 运行G(τ) 生成同态加密的公私钥对(pk，sk)，Alice 向Bob 公布生成的公钥pk.(2) Alice 根据编码方法构造SA 对应的向量A = (a′1，a′2，··· ，a′n)， 并用公钥pk 加密得到向量E(A) = (E(a′1)，E(a′2)，··· ，E(a′n))， Alice 将E(A) 发送给Bob.(3) Bob 根据SB 和集合U 按照上述编码方法得到向量B = (b′1，b′2，··· ，b′m)， 用Alice 的公钥加密得到:E(B) =(E(b′1)， E(b′2)，···， E(b′m)).(4) Bob 随机选择s ∈{0，1} 和随机数rij， 对每个i ∈[1，n-m+1]) 计算如下:∏m E(wi) =■■ ■i+j-1)*E(N -b′j))rij， s = 0，∏m j=1(E(N -a′j=1(E(a′i+j-1)*E(b′j))rij， s = 1.(5) Bob 经过n-m+1 次循环计算后得到E(W) = {E(w1)，E(w2)，··· ，E(wn-m+1)}， 将E(W) 中的分量进行随机置换， 置换后仍记为E(W) (因为W 为集合， 置换后仍为集合)， 并将E(W) 发送给Alice.(6) Alice 用自己的私钥对E(W) 解密得到集合W， 如果集合W 中至少有一个为0 的元素， 那么输出P(SA， SB) = 0，此时字符串SB 是SA 的子字符串; 否则， 输出P(SA，SB) = 1， 此时字符串SB 不是SA 的子串.

3.2 协议的正确性

定理1 协议1 能正确判断保密字符串SB是否为SA的子串.

这样计算结果E(W) ={E(w1)，E(w2)，···，E(wn-m+1)}中只要解密结果中有一个为0， 就说明字符串SB是字符串SA的子串; 反之， 则不是.

3.3 协议的安全性

定理2 保密判断字符串SB是否为SA的子串的协议1 是安全的.证明: 在半诚实模型下， 通过构造模拟器S1和S2使式(1) 和(2) 成立来证明本定理. 在协议1 中

其中，SA、SB是Alice 和Bob 的输入，r1是Alice 加密时所选择的随机数集合，E(W) 是Bob 根据字符串SB通过循环移动从SA中抽取对应位置进行计算所得结果构造的集合， 然后将集合中元素置换后发送给Alice 的结果，r2是由Bob 加密时所选择的随机数和计算时所选随机数组成的集合，E(A) 是Alice 发送给Bob 的密文信息，f1(SA，SB)，f2(SA，SB) 分别是Alice、Bob 收到的输出结果.

4 含通配符的字符串匹配

问题描述: Alice 拥有字符串SA， Bob 拥有含通配符的字符串SB， Bob 知道SB中通配符的个数和每个通配符所代表字符的个数. 换句话说，SB中已知字符所处的位置是确定的. 双方想知道含通配符的字符串SB和SA是否匹配， 且不泄露SA，SB的任何信息. 例如:SA= sunday，SB= sun*y，SB中的通配符代表2 个字符， 则字符s，u，n，y分别位于SB的第一、二、三、六的位置， 与SA中对应字符所处的位置一样， 则称SA和SB是匹配的. 本文首先将保密的数据编码成一个向量， 向量元素是由对应字符在全集中对应位置的两位十进制数表示， 在加法同态性的基础上设计一个简单、高效的协议.

例2 Alice 有字符串SA=privacy， 按照协议1 编码方式将其编码成向量A=(26，28，19，32，11，13，35)， 并发送给Bob.

(1) Bob 有含通配符的字符串SB=*ri*cy， Bob 知道第一个通配符代表一个字符， 第二个通配符代表2 个字符， 他根据已知字符r，i，c，y生成对应向量B=(28，19，13，35).

(2) Bob 根据SB中已知字符所在位置为第二、三、六和七的位置， 在向量A中挑选第二、三、六和七位置所对应的元素得到向量A′=(28，19，13，35).

(3) Bob 将向量B和向量A′中对应元素相减， 得到向量T=(0，0，0，0)， 并将向量T中元素相加得到total. 如果total=0， 则两字符串匹配; 反之， 则不匹配.该方法适应通配符在任意位置的关键字匹配问题:

*vacy，pri*，pri*cy，p*va*，*ri*cy，*va*，p*va*y.

4.1 具体协议

协议2 含通配符的字符串保密匹配协议输入: Alice、Bob 各自的私密字符串SA = a1a2···an， SB = b1b2···bm.输出: P(SA，SB).(1) (G，D，E) 是Paillier 同态加密方案， τ 是设定的安全参数， Alice 运行G(τ) 生成同态加密的公私钥对， Alice 向Bob公布生成的公钥.(2) Alice 调用协议1 的编码方法生成向量A = (a′1，a′2，··· ，a′n)， 加密向量A 得E(A) = (E(a′1)，E(a′2)，··· ，E(a′n))并将E(A) 发送给Bob.(3) Bob 调用协议1 的编码方法生成向量B = (b′1，b′2，··· ，b′m)， 用Alice 的公钥加密得到E(B) = (E(b′1)，E(b′2)，··· ，E(b′m)).(4) Bob 根据SB 中已知字符的位置， 在E(A) 中挑选对应的元素得到向量E(ˆA) = (E(a′i)，E(a′i+1)，··· ，E(a′i+m-1)) = (E(ˆa1)，E(ˆa2)，··· ，E( ˆam)). Bob 选择随机数ri(1 ≤i ≤m)，计算如下:E(total) =m∏(E(ˆai)*E(N -b′i))ri，i=1将E(total) 发送给Alice.(5) Alice 用自己的私钥对E(total) 解密得到total， 如果total = 0， 那么输出P(SA，SB) = 0， 字符串SA 和字符串SB匹配; 否则， 输出P(SA，SB) = 1.

4.2 协议的正确性

定理3 协议2 能正确判断保密含通配符的字符串SB与字符串SA是否匹配.

因此， 若total=0， 则含通配符的字符串SB和字符串SA匹配; 反之， 含通配符的字符串SB与字符串SA不匹配.

4.3 协议的安全性

定理4 保密判断含通配符的字符串SB与字符串SA是否匹配的协议2 是安全的.证明: 在半诚实模型下， 通过构造模拟器S1和S2使式(1) 和(2) 成立来证明本定理. 在协议2 中

由于E(A)是Alice 加密的，Bob 没有私钥，根据加密算法的语义安全性，对于Bob 来说E(A)c≡

5 效率分析

5.1 计算复杂性分析

(1) 判断字符串模式匹配时， 文献[21] 基于ElGamal 加密算法， 文献[24] 协议2 基于Goldwasser-Micali 加密算法， 且都调用了BMH 算法， 与本文协议1 均为公钥加密系统. 文献[22] 采用SHE 和新的数据包装技术实现单一模式串匹配(即模式串只能在文本中出现一次)， 文献[24] 协议4 基于对称密码算法， 只能实现单一模式串匹配， 本文协议1 可以实现多模式串匹配. 文献[23] 在恶意模型下， 本文协议1 在半诚实模型下， 效率没有可比性. 因此， 本文协议1 只与文献[21] 和文献[24] 协议2 做对比.

(2) 判断含通配符的字符串匹配问题时， 文献[28] 在恶意模型下只能实现单个通配符的匹配， 本文协议2 在半诚实模型下可以实现多个通配符的匹配. 文献[17-20] 基于Bloom Filter 只能实现字符串的近似匹配， 本文协议2 能实现字符串的精确匹配. 文献[29] 基于SHE 进行字符串匹配， 但SHE 的安全性依赖于Ring LWE 问题， 且只能实现有限次的乘法， 其适用性没有本文协议2 采用的Paillier 加密系统强. 因此， 本文协议2 不与上述方案做对比.

5.2 通信效率分析

衡量通信复杂度的指标用协议交换信息的比特数， 或用通信轮数， 在安全多方计算研究中通常用轮数.

(1) 判断字符串模式匹配时， 文献[21] 需要mn2+mn轮， 文献[24] 协议2 需要2mn轮， 本文协议1 需要2 轮通信. 如表1 所示.

表1 判断字符串模式匹配方案计算复杂性与通信复杂性的比较Table 1 Comparison of some solutions to string matching

(2) 判断含通配符的字符串匹配时， 本文需要2 轮通信. 如表2 所示.

表2 判断含通配符字符串匹配方案计算复杂性与通信复杂性Table 2 String matching with wildcards

5.3 实验数据分析

实验测试环境: Windows7 64 位操作系统， 处理器是Intel(R) Core(TM) i5-5200U CPU @2.2 GHz，内存是4.00 GB， 在PyCharm 2020.1 (Professional Edition) 用python 语言运行实现.

实验方法: 在判断字符串模式匹配时， 文献[21] 和文献[24] 协议2 都采用了同态加密算法， 所以我们通过模拟实验来测试文献[21]、文献[24] 协议2 和本文协议1 所用的时间， 通过比较协议执行的时间来比较效率. 本实验以字符串SA和字符串SB为例， 设定字符串SA的长度为n=26， 字符串SB的长度m依次取1， 2，···， 20， 针对每一个m均进行1000 次模拟实验测试， 统计协议执行时间的平均值(忽略协议中的预处理时间). 文献[21] 基于ElGamal 加密算法设计的协议， 文献[24] 的协议2 基于GM 加密算法设计的协议， 本文协议1 基于Paillier 加密算法设计的协议， 因此进行实验时我们采取ElGamal 加密算法、Goldwasser-Micali 加密算法和Paillier 加密算法的模数均为1024 比特， 选取随机数长度为64 比特.图1 为文献[21]、文献[24] 协议2 和本文协议1 字符串模式匹配的执行时间随模式串字符个数增长的变化规律.

图1 当模数为1024 bit， n=26 时字符串模式匹配的执行时间随m 增长的变化规律Figure 1 Execution time of string pattern matching with m， when n = 26， modulus is 1024 bit

在判断含通配符的字符串匹配时， 我们进行本文协议2 的实验. 本实验以字符串SA和含通配符的字符串SB为例， 设定字符串SA的长度为n=26， 字符串SB的长度m(不包含通配符的个数) 依次取1，2，···， 20， 针对每一个m均进行1000 次模拟实验测试， 统计协议执行时间的平均值(忽略协议中的预处理时间). 实验所选取的Paillier 加密算法的模数为1024 比特， 选取随机数长度为64 比特. 图2 为本文协议2 字符串模式匹配的执行时间随m增长的变化规律.

图2 当模数为1024 bit， n=26 时含通配符字符串匹配的执行时间随m 增长的变化规律Figure 2 Execution time of string with wildcards with m， when n = 26， modulus is 1024 bit

从图1 协议执行时间可看出， 随着模式串长度m的增加， 本文协议1 的计算复杂度比文献[21] 和文献[24] 协议2 有明显的降低， 因此本文所设计的协议是高效的.

6 结论

字符串匹配问题是安全多方计算的常见问题之一， 具有重要的研究意义和研究背景. 含通配符的字符串匹配可以用于数据处理、数据压缩、词频统计、生物序列分析、SQL 语句查询、信息检索等多种应用中. 本文首先设计了一种新的编码方法， 并结合Paillier 加法同态加密算法， 在半诚实模型下设计了字符串模式的保密匹配协议和含通配符的字符串保密匹配协议. 现有的字符串匹配协议， 大多只能实现字符串的近似匹配、明文情况下的字符串匹配算法、明文情况下的精确匹配和云计算下基于Bloom Filter 的字符串匹配. 本文所设计的协议可以实现在同态加密下的精确匹配， 时间复杂度和效率都比较低. 下一步我们将进一步研究云计算下更高效的含通配符的字符串匹配协议.