软件学报  2018, Vol. 29 Issue (7): 1893-1908   PDF    
基于字符串排序的高效保密数据库查询
李顺东1, 亢佳1, 杨晓艺1, 窦家维2     
1. 陕西师范大学 计算机科学学院, 陕西 西安 710062;
2. 陕西师范大学 数学与信息科学学院, 陕西 西安 710062
摘要: 安全多方计算是近年来国际密码学界研究的热点问题之一,是信息社会隐私保护的核心技术.保密地将字符串按照字典序排序问题是一个全新的安全多方计算问题,在信息安全领域有重要的实际意义和广泛的应用前景.它不仅可以提高保密数据库查询的效率,还可以解决大数据情况下的百万富翁问题.为了保密地判断两个字符串按照字典序排序的位置关系,首先设计了一种新的编码方法和一种基于ElGamal加密算法的云外包计算下的同态加密方案,在此基础上提出了一个高效、简单的协议,并对协议进行了正确性和安全性分析,同时给出了协议计算复杂性和通信复杂性的理论分析与实验验证.最后将保密的字符串排序问题协议应用于解决百万富翁问题,从根本上解决了大数据情况下的百万富翁问题.
关键词: 密码学     安全多方计算     字符串排序     数据库保密查询     同态加密     百万富翁问题    
String Sorting Based Efficient Secure Database Query
LI Shun-Dong1, KANG Jia1, YANG Xiao-Yi1, DOU Jia-Wei2     
1. School of Computer Science, Shaanxi Normal University, Xi'an 710062, China;
2. School of Mathmatics and Information Science, Shaanxi Normal University, Xi'an 710062, China
Foundation item: National Natural Science Foundation of China (61272435)
Abstract: Secure multiparty computation is a research focus in the international cryptographic community and a pivotal privacy preserving technology in cyberspaces. Privacy-Preserving lexicographical string sorting, as a completely new problem of secure multi-party computation, has important practical significance and broad application prospects in information security. It can not only improve the efficiency of secure database query but also solve the millionaires' problem in the case that the numbers to be compared are very large. In this study, to privately determine the lexicographical order of two private strings, an encoding scheme is first proposed to encode private numbers, then based on a homomorphic encryption algorithm supported by cloud computing outsourcing, a simple and efficient protocol is developed. Furthermore, a proof is provided to shoe that this protocol is secure in the semi-honest model, and its correctness is also analyzed. At the same time, the computational complexities and communication complexities of the protocol are analyzed, and the efficiency of the protocol on a PC is demonstrated. Finally, as a fundamental solution, the scheme is applied to solve the millionaires' problem in the case that the numbers to be compared are very large.
Key words: cryptography     secure multi-party computation     string sorting     secure database query     homomorphic encryption     millionaires' problem    

在现代社会, 信息与人们的生活密切相关, 无处不在.人们的衣食住行, 人与人之间的沟通交往, 企业的经营管理...都需要信息, 社会的发展也依赖于信息.数据库作为现代信息系统的核心部分, 存储和管理大量的重要信息, 通过数据库查询的方式能够帮助人们快捷、准确、全面地获取所需信息.数据库包含了大量敏感信息, 特别是政府部门和个人的敏感信息, 如用户个人信息、政府要员人事资料和其他关键信息资源, 这些重要信息在进行数据库查询的时候很容易泄露.所以, 如何保密地查询数据库并获得所需要的信息非常关键.

所谓保密的数据库查询就是在数据库查询过程中, 数据库不知道用户查询的是哪一条信息, 同时用户只能得到自己需要的查询结果, 而不知道数据库中的其他信息.例如:情报工作者为了得到某一政府要员的个人资料, 想要查询政府机关所拥有的数据库, 要查的政府要员属于敏感信息, 不能泄露给政府机关, 同时, 对于情报工作者不查询的记录数据库应该尽可能防止信息的泄露.保密的数据库查询问题是安全多方计算在数据库中的重要应用, 在安全多方计算领域中有着广阔的应用前景和实用价值.

然而, 现有的数据库保密查询方法虽然能够有效地保护用户和数据库的隐私信息, 但却存在花费高、效率低、查准率低的情况.因为现在的保密查询基本原理是将要查询的记录与数据库中的所有记录都进行加密, 然后利用查询记录的密文与数据库中所有记录的密文进行有关的查询操作.所以, 当数据库的记录很多时, 保密查询的计算复杂性很高, 查询效率很低.如何能从数据库中更加快速、准确地查询到保密数据呢?在提到的例子中:情报工作者获得一份名单(名单保密, 只有自己知道), 需要到保密数据库中查询名单上人物的详细资料, 数据库管理员选择数据库中间的一条保密记录m与名单上的一个名字n进行比对.如果名单上名字n排序在保密记录m之前, 那么直接让这个名字n与数据库中m之前的记录进行比较; 如果名单上名字n排序在保密记录m之后, 那么直接让名字n与数据库中m之后的记录进行比较.以此类推, 直到查询到的记录很少时, 调用现有的保密查询协议进行查询, 可以大大提高效率, 而且不泄露私密信息.用这种“二分法”来进行保密数据的查询, 效率将会大大提高.所以, 如何确定名单上名字n和数据库中记录m的排序关系将是提高效率的关键.上述保密高效查询问题的关键是设计出高效的字符串保密排序协议.本文的主要工作就是设计这样的协议.

安全多方计算(secure multi-party computation, 简称SMC)作为隐私保护和信息安全的关键技术, 已成为国内外密码学界的研究热点之一[1-8].安全多方计算保证在不泄露参与者私有数据的前提下, 使这些私有数据能够被参与者利用, 并进行保密的合作计算, 从而使人们能够最大限度地利用私有数据, 而不破坏数据的保密性.安全多方计算问题由Yao[9]首先提出, Goldreich[10]等人对其进行了深入的研究, 形成了安全多方计算问题的理论基础[11-13], 推动了安全多方计算的发展.

安全多方计算研究在计算科学中占有重要的地位.很多学者致力于安全多方计算问题的研究, 提出了各种安全多方计算问题及其解决方案.所研究问题的方向可以总结为以下几类:(1)保密的科学计算问题[14-23]; (2) 保密的计算几何问题[24-27]; (3)保密的求集合交集、并集问题; (4)保密的数据挖掘问题[28]; (5)保密的数据库查询问题; (6)其他安全多方计算问题.

保密的排序问题是保密比较大小问题的自然推广, 与保密比较大小问题一样都是保密的科学计算中的重要问题, 已经得到了很多研究, 但是目前对保密的排序问题方面的研究仍然处于初始阶段, 仅限于数据的比较, 例如保密地判断两个字符串按照字典序排序的位置问题还未得以研究.字符串保密排序问题是一个新的安全多方计算问题, 具体可以描述为将两个参与者分别拥有的字符串按照字典序保密排序, 而不泄露关于双方字符串的任何信息.保密判断两个字符串的排序关系对日常生活中问题的解决有着很大的实用意义, 不仅可以提高数据库查询的效率, 更是在保密的基因测序、基因序列匹配、网络安全、拍卖、招标等方面有着广泛的应用前景.根据字符串保密排序的含义可知, 字符串保密排序问题是百万富翁问题的推广.理论上比较两个数的大小和字符串排序本质相同, 因此可以用百万富翁问题协议解决字符串排序问题, 但也存在一些问题需要解决.例如, 假设用01, 02, …, 26表示字母a, b, …, z, 如果按照字典排序, 字符串d应该排在ab的后面, 但如果用百万富翁协议来比较04和0102, 显然, 04应该排在前面.只有两个字符串的长度相同时才能比较, 或者把两个字符串填充成同样长度, 但这样会增加计算量, 也会泄露一些信息.目前百万富翁问题的研究情况如下.

最早由Yao在文献[9]中应用电路解决了百万富翁问题, 但该方案的计算复杂性和通信复杂性都很高.当要比较的两个数范围很大时, 需要重复调用协议, 效率极低.文献[14, 15]中设计了基于不经意传输的百万富翁协议, 不仅需要并行调用多次不经意传输, 而且不能一次性解决大范围数据情况下的百万富翁问题, 需要多次重复调用基本协议, 计算复杂性高.文献[16]设计新的0-1编码方案, 将百万富翁问题归约到向量的部分标量积的计算, 然后利用Paillier加法同态加密体制, 构造了一个高效的百万富翁协议.在假定保密输入且$|U| = m$的情况下, 该协议的计算复杂性为O(m).但是该协议也必须通过多次调用基本协议来分段解决大数据情况下的百万富翁问题, 而且该协议只能判断两个保密数的关系是大于还是小于等于, 不能完全区分小于和等于的关系.文献[17-20]没有考虑算法的简洁性和通用性, 同样也存在重复多次调用协议来解决大范围数据的比较大小问题.Li等人[21, 22]设计了基于对称密码的不采用模指数运算的百万富翁协议, 将百万富翁问题转化成一个集合包含问题, 极大地降低了协议的时间复杂度, 但是该协议仅仅适用于所比较的两个数相差不是很大(都属于同一个范围较小的全集内)的情况.当两个数范围比较大时, 无法进行有效的比较.文献[23]虽然可以解决大数据情况下的百万富翁问题, 但是协议是将所要比较的保密数统一成相同位数的二进制数, 然后再利用新的0-1编码, 借助ElGamal加密算法, 将百万富翁问题归约到一个集合相交问题, 从而使其得到解决.整个过程计算复杂性仍然较高, 而且无法完全区分小于和等于的关系.

综上所述, 现有的协议在保密比较两个大数据大小时, 可能会出现以下情形:(1)不能直接比较大范围数据, 需要重复多次调用协议, 导致计算复杂性很高.(2)即使没有数据长度的限制, 也不能完全区分数据小于等于的关系.所以, 目前尚未有保密比较两个大数据大小问题的高效解决方案.字符串的排序与两个数大小的比较不完全等价, 如果将两个要进行比较的字符串转化成数字, 一般都是很大的数字, 而且在比较时必须把转化成的数字通过在低位补零使两个数字位数相同(否则将无法比较), 然后才能调用百万富翁问题协议来解决.这个过程进一步增加了计算复杂性而且泄露了一些信息.如果能够直接解决字符串的排序问题, 也就可以解决大数字的百万富翁问题.所以研究字符串保密排序问题显得很有意义.

本文主要研究两个字符串保密排序的问题, 首先设计了一种新的编码方式, 利用这种编码可以将字符串的排序问题转化成集合元素判定问题(集合中是否存在元素1, 2, 随机数), 提出了一个高效的保密判断字符串排序的协议, 这个协议实现过程的主要计算可以借助于云服务器来完成.并且在此基础上设计了可以一次性解决大范围数据情况下的百万富翁问题的协议, 该协议不需要多次重复调用基本协议, 同时也能够完全区分两个数的3种关系.

本文贡献主要如下:

(1) 针对字符串排序问题设计了一种全新的编码方法, 该编码方法将字符串的排序问题转化成集合元素判定问题(集合中是否存在元素1, 2, 随机数), 也为解决大数据情况下的百万富翁问题提供了新思路, 达到了简化问题、降低计算复杂性的目的.

(2) 针对我们的问题提出了将主要ElGamal加密运算外包给云服务器的方案, 此加密方案在预处理阶段由云服务器计算Ri=(grimod p, hri mod p), 加密时通过对Ri执行几次简单的模乘运算, 避免了原ElGamal加密算法加密过程中复杂的模指数运算.

(3) 基于云外包计算下的同态加密方案和创新编码方法, 设计了保密地判断两个字符串位置关系的协议, 并对其协议的安全性和正确性进行证明.

(4) 在保密地判断两个字符串按照字典序排序位置关系协议的基础上, 提出了保密解决大数据情况下的百万富翁问题的协议.同时, 利用字符串保密排序协议提出的将保密的字符串构造为编码表的方法, 也解决了字符串模式匹配的问题, 扩大了安全多方计算的研究领域和实际应用范围.

本文第1节介绍我们提出的协议中需要用到的预备知识和安全性定义.第2节基于一种新的编码方法和一种将ElGamal加密运算外包给云服务器的方法设计具体的协议解决字符串保密排序问题, 并对协议的正确性和安全性进行分析, 同时利用模拟实验对协议的复杂性和效率进行分析.第3节提出保密解决大数据情况下的百万富翁问题的协议和保密地判断字符串模式匹配问题的协议, 并对协议进行效率分析.第4节对文章进行总结.

1 预备知识 1.1 ElGamal同态加密方案

同态加密的概念在文献[29]中被首次提出, 其保证在不影响明文数据机密性的情况下, 直接对密文进行某些运算来代替对明文的运算取得同样的效果.简单来说, 对密文的计算等价于明文计算之后再加密.

ElGamal公钥密码体制[30]是1985年7月由ElGamal发明的, 它是建立在有限乘法群上的离散对数问题的困难性假设基础之上的一种公钥密码体制.该密码体制至今仍被认为是一个安全性能较好的公钥密码体制, 目前它被广泛应用于许多密码协议中.

ElGamal算法[30]描述如下.

公开参数.首先选取大素数p, 并取g是乘法群$Z_p^* = \left\{ {1,...,p - 1} \right\}$的一个生成元.

密钥生成.随机选取整数$d{\text{: }}0 < d < p - 1,$并计算$h = {g^d}\,{\text{mod}}\,p.$这里, pg是公开参数, h是公钥, d是私钥.

加密.对明文$m \in Z_p^ * ,$随机选取整数$r:0 < r < p - 1,$计算

${c_1} = {g^r}\,{\text{mod}}\,p{\text{, }}{c_2} = m{h^r}\,{\text{mod}}\,p,$

得到密文c=(c1, c2).

解密.对密文$c = ({c_1},{c_2}) \in Z_p^ * \times Z_p^ * ,$用私钥d解密得到明文为

$m = {c_2}{(c_1^d)^{ - 1}}\,{\text{mod}}\,p.$

本文所设计的安全多方计算协议采用了ElGamal乘法同态加密算法, 该算法是概率加密算法, 具有语义安全性.假设密文

$E({m_1}) = ({g^{{r_1}}}{\text{,}}{m_1}{h^{{r_1}}}),$
$E({m_2}) = ({g^{{r_2}}}{\text{,}}{m_2}{h^{{r_2}}}),$

那么,

$E({m_1}{m_2}) = ({g^{{r_3}}}{\text{,}}{m_1}{m_2}{h^{{r_3}}}){\text{,}}$
$E({m_1}) \otimes E({m_2}) = ({g^{{r_1} + {r_2}}}{\text{,}}{m_1}{m_2}{h^{{r_1} + {r_2}}}) = ({g^{{r_3}}}{\text{,}}{m_1}{m_2}{h^{{r_3}}}) = E({m_1}{m_2}).$

该算法满足如下性质:

$E({m_1}) \otimes E({m_2}) = E({m_1}{m_2}).$
1.2 安全性定义

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

$f{\text{:}}{\{ 0,1\} ^ * } \times {\{ 0,1\} ^ * } \to {\{ 0,1\} ^ * } \times {\{ 0,1\} ^ * },$

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

$ f\left( x,y \right)=\left( {{f}_{1}}\left( x,y \right),{{f}_{2}}\left( x,y \right) \right). $

理想保密计算协议.理想保密计算协议是假设有一个值得信赖的第三方(trusted third party, 简称TTP), 无论什么情况, 都绝不会泄露信息和恶意传递虚假信息.因此在可信第三方存在的情况下, Alice和Bob分别将自己的私有数据xy告诉TTP, TTP计算f(x, y), 然后将结果分别告诉Alice和Bob, 而不泄露任何其他私有信息.由于Alice和Bob无法从协议中获得除f(x, y)以外的其他信息, 所以该协议是安全性最高的双方保密计算协议, 被称为“理想协议”.任何计算f(x, y)的实际双方保密计算协议的安全性都无法超出这个理想协议.

半诚实参与者[31].所谓半诚实参与者就是各参与者执行协议的每一步都是完全严格按照协议的规定, 并且其在协议执行过程当中不会中途退出协议, 也不会欺骗和泄露信息, 但是它们可能会试图通过分析和利用协议执行过程中自己所得到的信息来推断额外的信息.

假设本文协议中所有参与者都是半诚实参与者, 并且提出的所有安全多方计算协议和安全性均对其适用.到目前为止, 大多数研究建立在半诚实模型上, 这是因为研究半诚实模型下的安全多方计算是研究恶意模型下安全多方计算的基础, 只要能够设计出在半诚实参与者模型下保密计算函数f的协议π, 就可以通过文献[31]中利用比特承诺和零知识证明理论设计的编译器将π转换成恶意攻击者参与的模型下保密计算f的协议.在转换后的协议中, 一个恶意的参与者将被迫按照半诚实的参与者行事, 否则将会被发现.在研究恶意模型下安全协议时, 人们总是从半诚实参与者模型入手, 找到防止恶意攻击的方法后, 将其添加到协议中, 最终形成恶意模型下的安全协议.

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

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

一些记号[31].假设参与保密计算的双方分别为Alice和Bob.

f(x, y)=(f1(x, y), f2(x, y))代表概率多项式时间函数, π表示计算f的协议.

假设协议执行过程中输入为(x, y), Alice得到的消息序列记为$view_1^\pi (x{\text{,}}y)$$(x,{r^1}{\text{,}}m_1^1{\text{,}}...{\text{,}}m_t^1),$其中, r1表示Alice独立的硬币抛掷结果(即Alice选定的随机数), $m_i^1$表示Alice第i次收到的信息; 执行协议后, Alice得到的输出结果记为$output_1^\pi (x{\text{,}}y).$Bob得到的信息序列, 输出结果也可以用类似的内容来定义.

如果有多个参与方, 在执行协议的过程中任意参与方i得到的信息序列记为$view_i^\pi (x{\text{,}}y)$$(x{\text{,}}{r^i}{\text{,}}m_1^i{\text{,}}...{\text{,}}m_t^i),$其中, ri表示第i个参与方独立的硬币抛掷结果; $m_j^i$表示第i个参与方第j次收到的信息, 执行协议以后, 第i个参与方得到的输出结果记为$output_i^\pi (x{\text{,}}y).$

定义1(半诚实参与者的保密性)[31].对于一个函数f, 如果存在概率多项式时间算法S1S2(有时称这样的多项式时间算法为模拟器), 使得

$ {\{ {S_1}(x{\text{,}}{f_1}(x{\text{,}}y)){\text{,}}{f_2}(x{\text{,}}y)\} _{x,y}}\mathop \equiv \limits^c \,{\{ view_1^\pi (x{\text{,}}y){\text{,}}output_2^\pi (x{\text{,}}y)\} _{x,y}} $ (1)
$ {\{ {f_1}(x{\text{,}}y){\text{,}}{S_2}(y{\text{,}}{f_2}(x{\text{,}}y))\} _{x,y}}\mathop \equiv \limits^c {\{ output_1^\pi (x{\text{,}}y){\text{,}}view_2^\pi (x{\text{,}}y)\} _{x,y}} $ (2)

式中, $\mathop \equiv \limits^c \,$表示计算上不可区分, 则认为保密地计算f.要证明一个多方计算方案是保密的, 就必须构造满足式(1)和式(2)的模拟器S1S2.

2 安全多方计算方案 2.1 两个字符串排序问题的高效解决方案

问题描述:Alice有一个字符串A=a1an, Bob有一个字符串B=b1bm.在不泄露任何AB信息的情况下判断AB的按照字典序排序的位置关系.这就是字符串排序的安全多方计算问题.

方案的思想:两个字符串排序的问题即为判断两个字符串按照字典序排序位置关系的问题.要判断两个字符串按照字典序排序位置关系, 首先要判断两个字符串相对应每个字符的位置关系(即判断aibi的位置关系).如果同一位置的两个字符相同(即ai=bi), 那么接着比较下一个位置的字符关系.如果同一位置的字符不同, 那么相应字符在前的字符串排在另一个字符串之前, 相应字符在后的字符串排在另一个字符串之后.本文将保密的数据通过一种编码方式表示在一个表格中(表格中的数据由1, 2和随机数ri构成), 并在乘法同态的基础上设计了一个简单、高效的协议.

通过编码方式表示保密数据:在此方案中, 假设字典的字母表为U={u1, u2, …, ut}且满足u1 < u2 < … < ut.在字符串AB中均有${a_i}{\text{,}}{b_j} \in U,$${a_i} = {u_l}{\text{,}}{b_j} = {u_k}(1 \leqslant l{\text{,}}k \leqslant t).$其中, lk表示字符aibjU中的位置, 且l=(ai)ord, k=(bj)ord.Alice根据aiU将字符串A表示成一个n×t的表格T.表格T中的元素T[r][c](其中, r代表表格行号且对应字符串A中字符ai的下标, c代表表格列号且0 < ct)按如下规则表示:

$ T[r][c]=\left\{ \begin{align} &2\text{,} &如果c<l \\ &1\text{,} &如果c=l \\ &{{r}_{rc}} &如果c>l \end{align} \right., $

其中, rrc为除1和2之外的随机数, 0 < cn, 0 < ct.

例如:本文假设字母表U为26个英文字母表, 字符串A=bactr, 字符串B=cab.那么按照编码方式可以将字符串A表示为表 1(第1个字符b在字母表U中是第l=(a1)ord=(b)ord=2位, 那么得到的表格第1行第l列的值为1, 第l列之前的值都为2, 第l列之后的值为随机数r1c(c > l).其他字符按照同样的规则表示到表格T中).

Table 1 Coding table constructed by using bactr 表 1 利用bactr构造的编码表

Alice将表格T发送给Bob.Bob根据字符串B中每个字符在字典集中的位置对应地从表格T中取出$T[1][{({b_1})_{{\text{ord}}}}],T[2][{({b_2})_{{\text{ord}}}}],T[3][{({b_3})_{{\text{ord}}}}]{\text{,}}$并计算

${s_1} = T[1][{({b_1})_{{\text{ord}}}}]{\text{,}}$
${s_2} = T[1][{({b_1})_{{\text{ord}}}}] \times T[2][{({b_2})_{{\text{ord}}}}]{\text{,}}$
${s_3} = T[1][{({b_1})_{{\text{ord}}}}] \times T[2][{({b_2})_{{\text{ord}}}}] \times T[3][{({b_3})_{{\text{ord}}}}].$

Bob利用计算结果构造一个集合$S = \{ {s_1}{\text{,}}{s_2}{\text{,}}{s_3}\} = \{ {r_{13}}{\text{,}}{r_{13}} \times 1{\text{,}}{r_{13}} \times 1 \times 2\} ,$其中, ${s_j} = \prod\nolimits_{i = 1}^j \,T[i][{({b_i})_{{\text{ord}}}}].$

事实1.字符串B排在字符串A之前当且仅当集合S中出现2.字符串B排在字符串A之后当且仅当集合S中元素值没有出现2且不都为1;如果集合S中所有元素值均为1, 那么字符串B为字符串A的子串(A=B可以认为AB的子串, 也可以看作BA的子串).

证明:先证明事实的第1部分.

$ \Rightarrow $如果B排在A之前, 一定存在一个$j(1 \leqslant j \leqslant m)$满足${a_1} = {b_1}{\text{,}}...{\text{,}}{a_{j - 1}} = {b_{j - 1}}{\text{,}}{({a_j})_{{\text{ord}}}} > {({b_j})_{{\text{ord}}}},$不需要考虑bj+1, …, bmaj+1, …, am的排列关系, 因而,

${s_1} = 1, \ldots ,{s_{j - 1}} = 1,{\text{ }}{s_j} = \prod\limits_{i = 1}^j \,T[i][{({b_i})_{{\text{ord}}}}] = 2.$

$ \Leftarrow $如果S中出现一个2, 假设${s_j} = \prod\nolimits_{i = 1}^j \,T[i][{({b_i})_{{\text{ord}}}}] = 2$是第1次出现的2.根据表的构造原则, 这意味着${s_1} = 1, \ldots ,{s_{j - 1}} = 1,$${b_1}, \ldots ,{b_{j - 1}}$${a_1}, \ldots ,{a_{j - 1}}$相同, 而bj排在aj的前面.因而B排在A的前面, 不需要再考虑bj后面的字符和aj后面的字符的排列关系.

下面证明事实的第2部分.

$ \Rightarrow $如果B排在A之后, 一定存在一个$j(1 \leqslant j \leqslant m)$满足${a_1} = {b_1}, \ldots ,{a_{j - 1}} = {b_{j - 1}},{({a_j})_{{\text{ord}}}} < {({b_j})_{{\text{ord}}}},$不需要考虑bj+1, …, bmaj+1, …, am的排列关系, 因而,

${s_1} = 1, \ldots ,{s_{j - 1}} = 1,{\text{ }}{s_j} = \prod\limits_{i = 1}^j \,T[i][{({b_i})_{{\text{ord}}}}] = r.$

其中, r是一个不等于1和2的随机数.因为${s_{j + 1}}, \ldots ,{s_m}$中都包含sj这个因子, 所以都是随机数.故集合S中没有出现2, 且都不为1.

$ \Leftarrow $如果S中没有出现2, 而且都不为1.假设${s_j} = \prod\nolimits_{i = 1}^j \,T[i][{({b_i})_{{\text{ord}}}}] = r$是第1次出现不等于1的元素.根据表的构造原则, 这意味着${s_1} = 1, \ldots ,{s_{j - 1}} = 1,$${b_1}, \ldots ,{b_{j - 1}}$${a_1}, \ldots ,{a_{j - 1}}$相同, 而bj排在aj的后面.因而B排在A的后面, 不需要再考虑bj后面的字符和aj后面的字符的排列关系.

对于第3种情况, 因为是从第1个字符开始计算的, 如果BA的子串, 那么A至少和B一样长, 在这种情况下, B排在A的前面.

根据这个事实, Alice和Bob可以通过集合S中的元素值判断字符串AB的按照字典序排序的位置关系, 但因为用明文形式的编码表没有保密性可言, 所以不能用明文的表完成这项任务, 而且还有一些细节问题需要处理.因为我们需要的计算是保密的乘法运算, 所以需要用ElGamal乘法同态加密算法, 同时, 为了提高算法的加密效率, 我们设计了以下将加密计算外包给云来完成的方案E.

2.2 云外包计算下的同态加密方案

密钥生成.首先选取大素数p, 并取g是乘法群$Z_p^* = \{ 1,...,p - 1\} $的一个生成元.随机选取整数$d:0 < d<p-1,$并计算h=gd mod p.这里, pg是公开参数, h是公钥, d是私钥.

云外包模指数运算.云服务器随机选择${r_1},{r_2},...,{r_k} \in Z_p^*(k \leqslant p),$计算足够多的${R_i} = ({R_{i1}},{R_{i2}}),$其中,

${R_{i1}} = {g^{{r_i}}}\,{\text{mod}} \,p{\text{, }}{R_{i2}} = {h^{{r_i}}}\,{\text{mod}} \,p,$

并将它们存储在集合R中.上述过程可以在预处理阶段完成.

加密.从云服务器上下载R, 随机选择集合R中的某些元素进行一定次数的模乘运算就可以得到grmod phr mod p.本文中以进行一次模乘运算为例来说明.例如:从R上随机选择2个元素, 记作${{R}_{i}},{{R}_{j}}\in R(1\le i,j\le k),$计算

${R_\alpha } = ({R_{\alpha 1}},{R_{\alpha 2}}) = {R_i} \cdot {R_j}\,{\text{mod}} \,p,$
${c_1} = {R_{\alpha 1}}{\text{, }}{c_2} = m{R_{\alpha 2}},$

得到密文c=(c1, c2).

解密.对密文$c = ({c_1},{c_2}) \in Z_p^* \times Z_p^*,$用私钥d解密得到明文为

$m = {c_2}{(c_1^d)^{ - 1}}\,{\text{mod}} \,p.$
2.3 具体协议

为方便表达, 定义如下谓词:

$ P(A,B)=\left\{ \begin{matrix} {1,} & {字符串B为字符串A的子串\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \\ {0,} & {字符串B按照字典序排列位于字符串A之前} \\ {2,} & {字符串B按照字典序排列位于字符串A之后} \\ \end{matrix} \right.. $

协议1.保密地判断两个字符串按照字典序排序的位置.

输入:Alice拥有的保密的字符串A=a1an, Bob拥有的保密的字符串B=b1bm.

输出:P(A, B).

假设整个字母表为U={u1, u2, …, ut}且满足u1 < u2 < … < ut.在字符串AB中, ${a_i},{b_j} \in U,$${a_i} = {u_l},{b_j} = {u_k}$(1≤l, kt).其中, lk表示字符aibjU中的位置, 且l=(ai)ord, k=(bi)ord.

(1) Alice利用加密方案E的密钥生成算法生成公私密钥对(PK, SK), 并且将公钥PK告诉Bob, 私钥SK保密.

(2) 云服务器随机选择${r_1},{r_2}, \ldots ,{r_k} \in Z_p^ * (k \leqslant p),$计算足够多的${R_i} = ({R_{i1}},{R_{i2}}),$其中,

${R_{i1}} = {g^{{r_i}}}\,{\text{mod}}\,p,\;\;{R_{i2}} = {h^{{r_i}}}\,{\text{mod}}\,p,$

并将它们存储在集合R中.Alice从云服务器上下载R, 利用集合R中的某些元素通过适量的模乘运算得到

${R_\alpha } = ({R_{\alpha 1}},{R_{\alpha 2}}).$

(3) Alice根据aiU将字符串A加密并表示成一个n×t的表格T.表格T表示规则如下:

$ T[r][c]=\left\{ \begin{align} &E(2),&如果c < l \\ &E(1),& 如果c=l \\ &{{r}_{rc}},&如果c > l \end{align} \right., $

其中, 加密的每个E(1)和E(2)所需要的Rα都不相同(即加密每个1, 2时, Alice利用集合R中的某些元素所做的模乘运算次数不同), rrc为除1和2之外的随机数, 0 < rn, 0 < ct.

将字符串A中所有字符均按照规则放入表格T中后, 为了不泄露字符串A的长度n, 在表格的末尾随机插入p(1 < pn)行除1和2以外的随机数得到(n+pt表格T′, 并将表格T′发送给Bob.

(4) Bob根据字符串B中每个字符在字典集中的位置对应地从表格T′中取出相应的数据, 并计算

$E({s_1}) = T'[1][{({b_1})_{{\text{ord}}}}],$
$\begin{matrix} E({{s}_{2}})={T}'[1][{{({{b}_{1}})}_{\text{ord}}}]\times {T}'[2][{{({{b}_{2}})}_{\text{ord}}}], \\ \vdots \\ \end{matrix}$
$E({s_m}) = T'[1][{({b_1})_{{\text{ord}}}}] \times ... \times T'[j][{({b_j})_{{\text{ord}}}}] \times T'[m][{({b_m})_{{\text{ord}}}}].$

(5) Bob利用计算结果构造一个集合:

$S = \{ E({s_1}),E({s_2}), \ldots ,E({s_m})\} .$

为了不泄露字符串B的长度m, 且当B排在A的前面时也不泄露B中有几个字符排在A的相应字符之前(比如, 如果A=cde, B=abc, Bob计算的集合中将会出现2, 4, 8.这样直接发送给Alice的话, Alice将会知道Bob的字符串有3个字符, 而且知道这3个字符都在A的相应字符之前.出现2k就说明有k个字符排在A的相应字符之前, 而这一点是应该避免的).在集合S中随机选取q(1 < q < m)个元素值(q对于Alice保密), 对于选取的每一个元素${s_k}(k \in 1, \ldots ,m)$再随机选取一个数$l \in 1, \ldots ,m,$计算$s_k^l,$利用概率加密的性质进行再随机化, 并将它们随机插入到集合S中, 得到集合

$S' = \{ E({s_1}),E({s_2}), \ldots ,E({s_m}),E({s_{m + 1}}),E({s_{m + 2}}), \ldots ,E({s_{m + q}})\} .$

最后将集合$S'$中元素整体做随机置换, 将得到的结果$\Pi (S')$发送给Alice.

(6) Alice用私钥解密$\Pi (S'),$如果解密结果$D(\Pi (S'))$中出现2, 输出P(A, B)=0;如果解密结果不出现2且不都为1, 输出P(A, B)=2;如果解密结果均为1, 输出P(A, B)=1.

2.4 协议1安全性分析

加密方案E安全性分析1.

协议1利用加密方案E加密时计算Rα=Ri·Rj mod p不会降低协议的安全性.因为R虽然是公开的, 但是R中的元素和这些元素需要进行的模乘运算都是随机的, 所以Rα=(Rα1, Rα2)与(gr mod p, hr mod p)是等效的, 因此任何敌手由R计算Rα的困难性与破解ElGamal加密算法的困难性是等价的.综上所述, 加密方案E将计算Ri=(Ri1, Ri2)外包给云服务器执行从语义安全角度来讲是安全的.

定理1.保密地判断两个字符串按照字典序排序的位置的协议1是安全的.

证明:通过构造使上述(1)和(2)成立的模拟器S1S2证明本定理.

在协议1中,

$view_1^\pi (A,B) = \{ A,T',\Pi (S'),D(\Pi (S')),P(A,B)\} ,$
${f_1}(A,B) = {f_2}(A,B) = output_1^\pi (A,B) = output_2^\pi (A,B) = P(A,B),$

其中, A, B是Alice和Bob的输入, T′是Alice用公钥PK加密字符串A并将其表示在表格中的形式.$\Pi (S')$是Bob先根据字符串B从表格中抽取数据, 然后将经过计算的结果构造集合, 并将集合中元素置换后发送给Alice的结果.$D(\Pi (S'))$是Alice解密$\Pi (S')$后得到的结果.

首先构造模拟器S1来模拟$view_1^\pi (A,B),$S1的模拟过程如下.

(1) 接受输入$(A,{f_1}(A,B)),$根据${f_1}(A,B)$的值, 选定字符串B′, 使${f_1}(A,B') = {f_1}(A,B),$$B' = {b'_1} \ldots {b'_m}.$S1根据字符串B′中每个字符在字典集中的位置对应地从表格T′中取出相应的数据并做计算, 通过添加, 置换得到集合$\Pi (S')'.$

(2) S1用私钥解密$\Pi (S')'$得到解密结果$D(\Pi (S')').$通过判断解密结果$D(\Pi (S')')$中是否出现2来判断字符串按照字典序排序的位置.令:

${S_1}(A,{f_1}(A,B)) = \{ A,T',\Pi (S')',D(\Pi (S')'),P(A,B)\} ,$

因为

$\Pi (S')\mathop \equiv \limits^c \,\Pi (S')',D(\Pi (S'))\mathop \equiv \limits^c \,D(\Pi (S')'),$

所以

$\{ {S_1}(A,P(A,B)),{f_2}(A,B)\} \mathop \equiv \limits^c \{ view_1^\pi (A,B),output_2^\pi (A,B)\} .$

类似地, 还可以构造S2, 使

$\{ {f_1}(A,B),{S_2}(B,{f_2}(A,B))\} \mathop \equiv \limits^c \,\{ output_1^\pi (A,B),view_2^\pi (A,B)\} .$

加密方案E安全性分析2.

在安全多方计算方案中, 如何衡量协议的安全性是非常复杂的问题.我们通常借助Goldreich提出的模拟范例来模拟参与者执行协议的过程, 从而对协议进行安全性证明.但是, 通过构造模拟器的方式只能证明协议是安全的, 而不能对协议的安全性水平加以区别.所以我们通过在执行协议过程中参与者私有信息的泄漏量来衡量方案的安全性水平.

一些符号的定义如下:

(1) P(A)表示Bob在没有执行任何安全多方计算协议之前获得的关于字符串A的先验概率.

(2) P(B)表示Alice在没有执行任何安全多方计算协议之前获得的关于字符串B的先验概率.

(3) $P\left( {B\left| {{f_1}\left( {A,B} \right)} \right.} \right)$表示Alice通过执行理想协议得到输出结果f1(A, B)的条件下获得的关于字符串B的条件

概率.

(4) $P\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right)$表示Bob通过执行理想协议得到输出结果f2(A, B)的条件下获得的关于字符串A的条件概率.

(5) ${P_\pi }\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right)$表示Bob在执行协议π后得到输出结果f2(A, B)的条件下获得的关于字符串A的条件概率.

(6) ${P_\pi }\left( {B\left| {{f_1}\left( {A,B} \right)} \right.} \right)$表示Alice在执行协议π后得到输出结果f1(A, B)的条件下获得的关于字符串B的条件概率.

因为理想协议是最安全的协议, 其他协议的安全性和信息泄露都不可能优于理想协议, 一种语言中一个固定长度的字符串的先验概率是不变的, 我们可以用理想协议作为标准衡量其他协议的安全性和信息泄漏量, 用理想协议的条件概率和实际协议的条件概率的比值$P\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right)$${P_\pi }\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right)$刻画实际协议与理想协议相比是不是泄露了更多的信息, 比值越接近于1说明实际协议泄露的信息越少, 越接近于0说明实际协议泄露的信息越多.

定义2.对于计算多项式时间函数f的协议π, 如果满足以下条件:

${P_\pi }\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right){\text{ = }}P\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right),$
${P_\pi }\left( {B\left| {{f_1}\left( {A,B} \right)} \right.} \right){\text{ = }}P\left( {B\left| {{f_1}\left( {A,B} \right)} \right.} \right),$

则认为保密地计算f的协议π与理想协议是等价的, 信息泄露最少.

也可以利用信息熵的变化来衡量信息泄露.假设字符串A分布在集合{A1, A2, …, An}上, 且出现的概率为P(A=A1), P(A=A2), …, P(A=An), 则字符串A的信息熵为

$H(A) = - \sum {P\left( {A = {A_i}} \right)} \times \log {\kern 1pt} P(A = {A_i}).$

执行理想协议并得到f2(A, B)后, 关于A的信息熵为

$H\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right) = - \sum {P\left( {A = {A_i}\left| {{f_2}\left( {A,B} \right)} \right.} \right)} \times \log P\left( {A = {A_i}\left| {{f_2}\left( {A,B} \right)} \right.} \right).$

类似地, 可以定义得到f1(A, B)后, 关于B的信息熵, 以及执行实际协议π之后关于A, B的条件信息熵.

同样得到的关于A, B的信息越多, 信息熵的减少就越多.显然, 理想协议执行后信息熵的减少是最少的, 其他协议信息熵的减少都不会少于理想协议.因此, 我们可以用比值${{{H_\pi }\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right)} / {H\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right)}}$衡量协议的信息泄露量.

定义3.对于计算多项式时间函数f的协议π, 如果满足以下条件:

${H_\pi }\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right){\text{ = }}H\left( {A\left| {{f_2}\left( {A,B} \right)} \right.} \right),$
${H_\pi }\left( {B\left| {{f_1}\left( {A,B} \right)} \right.} \right){\text{ = }}H\left( {B\left| {{f_1}\left( {A,B} \right)} \right.} \right),$

则认为保密地计算f的协议π与理想协议是等价的.

本文中, 我们用条件概率来度量协议中Bob的信息泄漏量.首先以拥有单个字符的字符串的保密排序为例分析协议的信息泄露量(本文协议记为π).

假设字母表为$U = \{ a,b,...,z\} ,A = d,{\kern 1pt} B = m.$A, BU上均匀分布(实际上不是均匀分布的, 但分析方法相同, 只是分析的计算过程稍微复杂一些).在这样的假设条件下, 在保密计算前, 关于A, B的先验概率都是1/26, 即P(A)=P(B)=1/26执行协议后Bob知道字符串A排在字符串B的前面, 除此之外没有更多的信息, 只能假设A在{a, b, c, d, e, f, g, h, i, j, k, l}上均匀分布, 因此

${P_\pi }(A|{f_2}(A,B)) = 1/12 = 1/({(B)_{{\text{ord}}}} - 1).$

类似地, 可以计算${P_\pi }(B|{f_1}(A,B)) = 1/22 = 1/(26 - {(A)_{{\text{ord}}}}).$简单的分析计算可知, $P(A|{f_2}(A,B)) = 1/12,$$P(B|$ ${f_1}(A,B)) = 1/22.$所以有:

${P_\pi }(A|{f_2}(A,B))/P(A|{f_2}(A,B)) = 1,{\text{ }}{P_\pi }(B|{f_1}(A,B))/P(B|{f_1}(A,B)) = 1.$

其他情况下, 无论是A排在字符串B的后面, 或是A排在字符串B的同样位置, 简单的分析都可以得出同样的结论.因此我们的协议所导致的信息泄露和理想协议的信息泄露一样, 这部分信息泄露完全是函数f(A, B)的信息泄露, 这是无法避免的.

当字符串是多个字符而不是单个字符时, 用排列组合的乘法原理也可以计算相应的条件概率, 只是计算更复杂一些.经过分析可以得出如下结论, 我们的协议和理想协议是等价的, 泄露的信息量也和理想协议相同, 都达到了最少的信息泄露.

2.5 协议1正确性分析

(1) 协议1在保密字符的加密过程中将计算Ri=(Ril, Ri2)外包给云, 不会影响最终的解密结果, 随机变量Rα可以在解密运算中被成功消除.因为

${R_i} = ({R_{i1}}{\text{,}}{R_{i2}}) = ({g^{{r_i}}}\,{\text{mod}} \,p{\text{,}}{h^{{r_i}}}\,{\text{mod}} \,p),$
${R_j} = ({R_{j1}}{\text{,}}{R_{j2}}) = ({g^{{r_j}}}\,{\text{mod}} \,p{\text{,}}{h^{{r_j}}}\,{\text{mod}} \,p).$

所以可以得到

$\begin{align} & {{R}_{\alpha }}=({{R}_{\alpha 1}},{{R}_{\alpha 2}}) \\ & \ \ \ \ \ ={{R}_{i}}\cdot {{R}_{j}}\,{\text{mod}} \,p \\ & \ \ \ \ \ =({{R}_{i1}}\cdot {{R}_{j1}},{{R}_{i2}}\cdot {{R}_{j2}}) \\ & \ \ \ \ \ =({{g}^{{{r}_{i}}}}\cdot {{g}^{{{r}_{j}}}}\,{\text{mod}} \,p,{{h}^{{{r}_{i}}}}\cdot {{h}^{{{r}_{j}}}}\,{\text{mod}} \,p) \\ & \ \ \ \ \ =({{g}^{{{r}_{i}}+{{r}_{j}}}}\,{\text{mod}} \,p,{{h}^{{{r}_{i}}+{{r}_{j}}}}\,{\text{mod}} \,p) \\ & \ \ \ \ \ =({{g}^{r}}\,{\text{mod}} \,p,{{h}^{r}}\,{\text{mod}} \,p). \\ \end{align}$

因此, 将计算Ri=(Ril, Ri2)外包给云服务器执行并不会影响解密结果.

(2) Alice按照新的编码方式将字符串A表示在表格T′中, 按照协议1将Bob构造的集合$\Pi (S')$解密, 如果解密的集合$D(\Pi (S'))$中出现2, 则说明Bob按照字符串B, 从表格T′中所取的字符至少有一个是排在字符串A中字符的前面, 只有这样, 在解密后的集合$D(\Pi (S'))$中才会出现2.同理, 如果解密的集合$D(\Pi (S'))$中不出现2且不均为1, 则说明Bob按照字符串B, 从表格T′中所取的字符至少有一个是排在字符串A中字符的后面.如果解密的集合$D(\Pi (S'))$中均为1, 那么字符串B为字符串A的子串.

因此协议1能够正确地判断字符串AB按照字典序排序的位置关系.

2.6 性能分析

目前没有任何关于保密地判断两个字符串按照字典序排序位置关系的协议, 因此在本节只对协议1进行效率分析和实验验证.本文的协议是用同态加密算法解决字符串按照字典序顺序排序的问题, 基本运算都是模乘运算.

计算复杂性分析.本文在协议1中利用同态加密方案E计算Ri=(Ril, Ri2)是在预处理阶段由云服务器完成的, 在加密过程中, 只需通过对Ri执行一定次数的模乘运算(Rα=Ri·Rj mod p), 就可以秘密地得到gr mod phr mod p, 而不需要再做复杂的模指数运算.如果忽略预处理时间, 用方案E加密1次只需要进行1次乘法运算和1次模乘运算.Alice用加密方案E最多加密nt次, 解密m次.加密1次需要1次模乘运算, 解密1次需要lg p次模乘运算, 故协议1的计算复杂性为mlg p+nt次模乘运算.

通信复杂性分析.衡量通信复杂度的指标一般用协议交换信息的比特数, 或者用通信轮数, 在安全多方计算研究中通常用轮数.本文中协议1需要进行3轮通信.

2.7 实验数据分析

实验测试环境.Windows 10 64位操作系统, 处理器是Intel(R)Core(TM)i5-6600 CPU @3.30GHz, 内存是8.00GB, 用Java语言在MyEclipse上运行实现.本文所做模拟实验均在此环境下进行.

实验方法.我们通过模拟实验来测试本文执行协议1所用时间, 可通过协议执行的时间来验证方案的效率.本实验以字符串A和字符串B为例, 设定字符串A的字符个数n=20, 字符串B的字符个数分别为m=1, 2, …, 20, 对m的每个设定值进行1 000次模拟实验测试, 忽略协议中的预处理时间, 统计协议执行时间的平均值.图 1描述了判断字符串排序的执行时间随字符串字符个数增长的变化规律.

Fig. 1 The execution time of the string sort increases with the number of characters in the string 图 1 字符串排序的执行时间随字符串字符个数增长的变化规律

3 应用

本节我们将利用保密地判断两个字符串位置关系的协议来解决大数据情况下的百万富翁问题和保密地判断字符串模式匹配问题.

3.1 大数据情况下的百万富翁问题

问题描述:Alice拥有大数据x, Bob拥有大数据y.双方想在不泄露任何xy信息的情况下知道xy的大小关系.

我们可以将大整数xy看成是用十进制表示的特殊类型的字符串, 那么就可以将保密地判断大整数xy的大小问题转化成保密的字符串排序问题, 即通过判断字符串的位置关系来确定xy的大小关系.假设Alice和Bob协商将大整数xy表示成n位的十进制数, 不足的位数分别用0补齐(此处为高位补0).如:大整数$x = x' = {x_1}{x_2} \ldots {x_n},$大整数$y = y' = {y_1}{y_2} \ldots {y_n}.$

由事实1可知:根据集合S中的元素值可判断字符串A和字符串B的位置关系, 于是有:如果$x' < y',$那么通过调用协议1得到的集合S中的元素值没有出现2且不都为1.如果$x' = y',$那么集合S中所有元素值均为1.如果$x' > y',$那么集合S中出现2.

为方便表达, 定义如下谓词:

$P(A,B) = \left\{ \begin{aligned} & 1,\;\;{\text{ }}x = y \\ & 0,\;\;x > y \\ & 2,\;\;x < y \\ \end{aligned} \right..$

协议2.大数据情况下的百万富翁问题.

输入:Alice输入私有数据x, Bob输入私有数据y.

输出:P(A, B).

(1) 假设Alice和Bob协商将大整数xy表示成n位的十进制数, 不足的位数分别用0补齐.如:大整数$x = x' = {x_1}{x_2}...{x_n},$大整数$y = y' = {y_1}{y_2}...{y_n}.$

(2) Alice和Bob调用协议1, 根据解密结果$D(\Pi (S'))$中的值来判断两个大整数xy的大小关系.如果$D(\Pi (S'))$中所有的元素值均为1, 输出P(A, B)=1, 此时大整数x=y; 如果$D(\Pi (S'))$中元素值出现2, 输出P(A, B)=0, 此时大整数x > y; 如果$D(\Pi (S'))$中的元素值没有出现2且不都为1, 输出P(A, B)=2, 此时大整数x > y.

协议效率分析.

在协议2中最多需要nlg p次模乘运算(n为机密数据的长度), Alice和Bob之间需要进行3轮通信.

文献[23]和本文的方案都可以一次性解决大数据情况下的百万富翁问题, 而不需要重复调用多次基本协议, 同时都对保密数据进行了编码.忽略方案中随机数选择的计算开销和双方准备阶段的计算开销, 且将两个方案中的模都统一为p进行比较分析.

表 2可知, 本文协议2的通信复杂性和文献[23]的通信复杂性一样, 计算复杂性低于文献[23]的计算复杂性.当两个很大的数据比较大小时, p为固定数值, log p不会随着n的变化而线性增大.当n的取值很大时, 本文中协议2的计算速率比文献[23]快5倍多.在适用范围方面, 文献[23]不能完全判断两个保密数的小于和等于关系, 而本文的协议2不仅解决了两个数比较大小的问题, 也能区分两个数是否相等的问题.

Table 2 The efficiency of the protocol 2 表 2 协议2性能分析与比较

实验数据分析.

实验方法.我们通过模拟实验来测试本文协议2和文献[23]中协议所用时间, 可通过协议执行的时间来验证方案的效率.本实验假定数A和数B长度为n, n的变化范围为20, 21, …, 40, 对n的每个设定值进行1 000次模拟实验测试, 忽略协议中的预处理时间, 统计协议执行时间的平均值.图 2描述了大数据情况下百万富翁协议的执行时间随机密数据长度增长的变化规律.

Fig. 2 The execution time of the millionaires' problem increases with the number of characters in the string 图 2 大数据情况下百万富翁协议的执行时间随字符串字符个数增长的变化规律

协议2的安全性依赖于保密地判断两个字符串位置关系协议的安全性, 应用证明定理1所用的方法很容易证明协议2的安全性, 本文在这里省略证明过程.

3.2 保密地判断字符串模式匹配问题

问题描述:Alice有一个字符串(文本串)$A = {a_1} \ldots {a_n},$Bob有一个字符串(模式串)$B = {b_1} \ldots {b_m}(m \leqslant n).$在不泄露任何AB私有信息的情况下判断A中是否存在一个子串与B相等, 也就是说, 在字符串A中找到一个子串${S_i} = $ ${a_i}{a_{i + 1}} \ldots {a_{i + m - 1}},$使Si=B.

利用协议1这种将保密的字符串构造为编码表的方法, 适当地作处理就可以解决字符串模式匹配的问题.Alice根据字符串A利用文章前面提到的编码规则构造表格T′.根据字符串B中每个字符在字典集中的位置, Bob对应地从表格T′中第1行开始取值(直到第n-m+1行为止), 并将取值相乘得到结果E(Si), 记作集合$W = \{ {w_1},{w_2}, \ldots ,{w_{n + m - 1}}\} = \{ E({s_1}),E({s_2}), \ldots ,E({s_{n + m - 1}})\} .$Alice解密, 如果集合W中出现1, 则说明字符串A中存在子串与字符串B相等.

为方便表达, 定义如下谓词:

$ P(A,B)=\left\{ \begin{matrix} {1,} & {字符串A和字符串B匹配\ \ } \\ {0,} & {字符串A和字符串B不匹配} \\ \end{matrix} \right.. $

协议3.保密地判断两个字符串是否模式匹配.

输入:Alice拥有保密的字符串A=a1a2an, Bob拥有保密的字符串$B = {b_1}{b_2} \ldots {b_m}(m \leqslant n).$

输出:P(A, B).

(1) 令i=1.

(2) Alice调用协议1编码保密数据的方法构造表格T′, Bob根据字符串B中每个字符在字典集中的位置对应地从表格T′中取出相应的数据, 并计算

$E({s_i}) = T'[i][{({b_1})_{{\text{ord}}}}] \times \ldots \times T'[j][{({b_j})_{{\text{ord}}}}] \times T'[m + i - 1][{({b_m})_{{\text{ord}}}}].$

(3) 令i=i+1.Bob循环执行以上第(2)步, 直到i=n-m+1为止.

(4) Bob将循环得到的结果E(si)记为$W = \{ {w_1},{w_2}, \ldots ,{w_{n + m - 1}}\} = \{ E({s_1}),E({s_2}), \ldots ,E({s_{n + m - 1}})\} .$为了不泄露字符串A中有几个子串和字符串B相等, 再在W中随机选取z个元素值, 将它们随机插入到W中, 得到集合$W' = \{ {w_1},$ ${w_2}, \ldots ,{w_{n + m - 1}},{w_{n + m}},{w_{n + m + 1}}, \ldots ,{w_{n + m - 1 + z}}\} ,$最后将集合W′中元素做置换, 将得到的结果$\psi (W')$发送给Alice.

(5) Alice根据解密结果$D(\psi (W'))$中的值来判断两个字符串是否模式匹配.如果$D(\psi (W'))$中元素值出现1, 则输出P(A, B)=1, 此时字符串A中存在一个子串${S_i} = {a_i}{a_{i + 1}} \ldots {a_{i + m - 1}},$使得Si=B; 否则, 输出P(A, B)=0.

协议效率分析.

本节将与2010年的文献[32]中所提出的同样使用ElGamal同态加密算法和新的保密数据编码方法解决字符串匹配问题的协议作比较.忽略方案中随机数选择的计算开销和双方准备阶段的计算开销, 对两个方案进行对比.

表 3中, n为字符串A的字符个数, m为字符串B的字符个数, k为字符串AB每个字符对应的ASCII值的二进制位数, p为大素数.mn(4nk+1)lg p表示执行文献[32]中协议需要进行的模乘次数.由表 3可知, 本文协议3的计算复杂性远小于文献[32], 而且文献[32]的通信复杂性和字符串A, B的长度有关, 会随着字符串长度的增加而越来越大, 本文协议3的通信复杂性为定值, 远低于文献[32].

Table 3 The efficiency of the protocol 3 表 3 协议3性能分析与比较

实验数据分析.

实验方法.我们通过模拟实验来测试本文协议3和文献[32]协议所用的时间, 可通过协议执行的时间来验证方案的效率.本实验以字符串A和字符串B为例, 设定字符串A的字符个数为26, 字符串B的字符个数分别为m=1, 2, …, 20, 对m的每个设定值进行1 000次模拟实验测试, 忽略协议中的预处理时间, 统计协议执行时间的平均值.图 3描述了字符串模式匹配的执行时间随模式串字符个数增长的变化规律.

Fig. 3 The execution time of the string matching problem increases with the number of characters in the string 图 3 字符串模式匹配的执行时间随模式串字符个数增长的变化规律

协议3的安全性可以应用证明定理1所用的方法, 本文在这里省略证明过程.

4 结论

字符串排序问题是安全多方计算中新的研究问题, 具有重要的研究意义和应用前景.本文基于一种新的编码方式和一种云外包计算下的同态加密方案设计了两个字符串保密排序的安全多方计算协议, 并利用模拟器证明了方案的安全性, 同时将保密的字符串排序协议应用于解决大数据情况下的百万富翁问题和保密地判断字符串模式匹配问题.本文研究的问题都是基于半诚实模型的, 对于安全多方计算的研究与应用有重要的理论意义, 但恶意模型的安全性更高、更具有实际意义, 所以如何实现恶意模型下的字符串保密排序问题是我们今后研究的问题.

参考文献
[1]
Goldwasser S. Multi party computations: Past and present. In: Proc. of the 16th Annual ACM Symp. on Principles of Distributed Computing. ACM, 1997. 1-6.
[2]
Goldreich O. Secure multi-party computation. Manuscript, Preliminary Version, 1998: 86–97. http://en.cnki.com.cn/Article_en/CJFDTotal-TXBM201401051.htm
[3]
Freedman MJ, Nissim K, Pinkas B. Efficient private matching and set intersection. In: Proc. of the Int'l Conf. on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer-Verlag, 2004. 1-19.
[4]
Lynn B, Prabhakaran M, Sahai A. Positive results and techniques for obfuscation. In: Advances in Cryptology-EUROCRYPT 2004. Berlin, Heidelberg: Springer-Verlag, 2004. 20-39.
[5]
Aggarwal G, Mishra N, Pinkas B. Secure computation of the k th-ranked element. In: Advances in Cryptology-EUROCRYPT 2004. Berlin, Heidelberg: Springer-Verlag, 2004, 3027: 40-55.
[6]
Fitzi M, Holenstein T, Wullschleger J. Multi-Party computation with hybrid security. In: Advances in Cryptology-EUROCRYPT 2004. Berlin, Heidelberg: Springer-Verlag, 2004, 4: 419-438.
[7]
Ishai Y, Kushilevitz E. On the hardness of information-theoretic multiparty computation. In: Advances in Cryptology-EUROCRYPT 2004. Berlin, Heidelberg: Springer-Verlag, 2004, 3027: 439-455.
[8]
Golle P, Juels A. Dining cryptographers revisited. In: Advances in Cryptology-Eurocrypt 2004. Berlin, Heidelberg: Springer-Verlag, 2004, 3027: 456-473.
[9]
Yao AC. Protocols for secure computations. In: Proc. of the 23rd Annual Symp. on Foundations of Computer Science. IEEE, 1982. 160-164.
[10]
Goldreich O, Micali S, Wigderson A. How to play any mental game. In: Proc. of the 19th Annual ACM Symp. on Theory of Computing. ACM, 1987. 218-229.
[11]
Yasin S, Haseeb K, Qureshi RJ. Cryptography based e-commerce security:A review. Int'l Journal of Computer Science Issues, 2012, 9(2): 132–137. http://www.oalib.com/paper/2647718
[12]
Sharma R. Review paper on cryptography. Int'l Journal of Research, 2015, 2(5): 141–142. http://internationaljournalofresearch.org/index.php/ijr/article/view/1944
[13]
Kumar SN. Review on network security and cryptography. Int'l Trans. of Electrical and Computer Engineers System, 2015, 3(1): 1-11.
[14]
Ioannidis I, Grama A. An efficient protocol for Yao's millionaires' problem. In: Proc. of the 36th Annual Hawaii Int'l Conf. on System Sciences. IEEE, 2003. 6-9.
[15]
Li SD, Dai YQ, You QY. Efficient solution to Yao's millionaires' problem. Dianzi Xuebao (Acta Electronica Sinica), 2005, 33(5): 769–773(in Chinese with English abstract). http://doi.wanfangdata.com.cn/10.3969/j.issn.1000-3428.2010.14.045
[16]
Li SD, Wang DS. Efficient secure multiparty computation based on homomorphic encryption. Dianzi Xuebao (Acta Electronica Sinica), 2013, 41(4): 798–803(in Chinese with English abstract). http://www.cqvip.com/QK/90131X/201304/45765418.html
[17]
Sheikh R, Mishra DK, Kumar B. Secure multiparty computation:From millionaires problem to anonymizer. Information Security Journal:A Global Perspective, 2011, 20(1): 25–33. [doi:10.1080/19393555.2010.544701]
[18]
Grigoriev D, Shpilrain V. Yao's millionaires' problem and decoy-based public key encryption by classical physics. Int'l Journal of Foundations of Computer Science, 2014, 25(4): 409–417. [doi:10.1142/S0129054114400036]
[19]
Karimian AN. Efficient non-interactive secure two-party computation for equality and comparison[Ph. D. Thesis]. University of Calgary, 2015.
[20]
Lipmaa H, Toft T. Secure equality and greater-than tests with sublinear online complexity. In: Proc. of the Int'l Colloquium on Automata, Languages, and Programming. Berlin, Heidelberg: Springer-Verlag, 2013. 645-656.
[21]
Li SD, Wang DS, Dai YQ, et al. Symmetric cryptographic solution to Yao's millionaires' problem and an evaluation of secure multiparty computations. Information Sciences, 2008, 178(1): 244–255. [doi:10.1016/j.ins.2007.07.015]
[22]
Li SD, Wang DS, Dai YQ. Symmetric cryptographic protocols for extended millionaires' problem. Science in China Series F:Information Sciences, 2009, 52(6): 974–982. [doi:10.1007/s11432-009-0109-6]
[23]
Lin HY, Tzeng WG. An efficient solution to the millionaires' problem based on homomorphic encryption. In: Proc. of the Int'l Conf. on Applied Cryptography and Network Security. Berlin, Heidelberg: Springer-Verlag, 2005. 456-466.
[24]
Atallah MJ, Du W. Secure multi-party computational geometry. In: Proc. of the Workshop on Algorithms and Data Structures. Berlin, Heidelberg: Springer-Verlag, 2001. 165-179.
[25]
Du W, Atallah MJ. Secure multi-party computation problems and their applications: A review and open problems. In: Proc. of the 2001 Workshop on New Security Paradigms. ACM, 2001. 13-22.
[26]
Li SD, Wu CY, Wang DS, et al. Secure multiparty computation of solid geometric problems and their applications. Information Sciences, 2014, 282: 401–413. [doi:10.1016/j.ins.2014.04.004]
[27]
Li SD, Wang DS, Dai YQ. A secure multi-party computation solution to intersection problems of sets and rectangles. Progress in Natural Science, 2006, 16(5): 538–545. [doi:10.1080/10020070612330032]
[28]
Lindell Y, Pinkas B. Privacy preserving data mining. Journal of Cryptology, 2002, 15(3): 177–206. [doi:10.1007/s00145-001-0019-2]
[29]
Rivest RL, Adleman L, Dertouzos ML. On data banks and privacy homomorphisms. Foundations of Secure Computation, 1978, 4(11): 169–180. http://www.ams.org/mathscinet-getitem?mr=521254
[30]
Xu MZ, You L. Information Security and Cryptology. Beijing: Tsinghua University Press, 2007: 96-98.
[31]
Goldreich O. Foundations of Cryptography:Volume 2, Basic Applications. London: Cambridge University Press, 2004: 599-764.
[32]
Luo Y, Shi L, Zhang C, et al. Privacy-Preserving protocols for string matching. In: Proc. of the 4th Int'l Conf. on Network and System Security (NSS). IEEE, 2010. 481-485.
[15]
李顺东, 戴一奇, 游启友. 姚氏百万富翁问题的高效解决方案. 电子学报, 2005, 33(5): 769–773. http://doi.wanfangdata.com.cn/10.3969/j.issn.1000-3428.2010.14.045
[16]
李顺东, 王道顺. 基于同态加密的高效多方保密计算. 电子学报, 2013, 41(4): 798–803. http://www.cqvip.com/QK/90131X/201304/45765418.html
[30]
徐茂智, 游林. 信息安全与密码学. 北京: 清华大学出版社, 2007: 96-98.