最大最小值的保密计算*
2020-09-12杨颜璟李顺东杜润萌
杨颜璟, 李顺东, 杜润萌
陕西师范大学 计算机科学学院, 西安710119
1 引言
随着互联网、云计算与大数据的迅速普及, 隐私泄露极易发生, 隐私保护变得十分迫切. 很多隐私保护问题都可以用安全多方计算方法解决, 因此安全多方计算成为信息社会隐私保护的关键技术. 如果借助可信的第三方, 安全多方计算问题很容易解决, 但在遍布整个世界的、复杂的互联网环境中, 找到一个所有参与者都信任的第三者并不容易, 因此需要设计安全多方计算协议保证私有信息不被泄露. 安全多方计算在保护私密数据隐私的前提下, 使得参与者能够最大限度地利用自己的私有数据进行保密合作计算, 充分发挥私有数据在社会、经济和科学技术领域的积极作用, 是实现合作保密计算的主要工具.
安全多方计算这一概念由图灵奖获得者姚期智教授在20 世纪80 年代以百万富翁问题引入[1]. 百万富翁问题是指分别拥有隐私数据x,y 的两个参与者, 保密判断x 是否大于y, 而不泄露x,y 的其他信息.由百万富翁问题发展而来的安全多方计算是指分别拥有隐私数据x1,x2,··· ,xn的n 个参与者联合计算f(x1,x2,··· ,xn) 的值, 计算完成之后, 每个参与者除了得到f(x1,x2,··· ,xn) 的值之外, 得不到关于隐私数据的其他任何信息. 后来, Goldreich, Micali 等人[2,3]对安全多方计算的理论进行深入研究, 证明在一定的条件下, 任意函数f(x1,x2,··· ,xn) 的安全多方计算都是可以实现的, 并且给出基于不经意传输的解决方案. 这样的通用解决方案有重要的理论意义, 奠定了安全多方计算的理论基础, 对于某些简单的安全双方计算问题, 基于电路的通用解决方案是有效的, 对于复杂的安全计算问题通用解决方案的效率并不理想, 而且把任意问题转化为电路计算问题也不是一个简单的问题, 因此针对具体问题提出具体的解决方案是安全多方计算研究的重要方面.
在隐私保护需要的推动下, 安全多方计算研究取得了丰硕的成果[4,5]. 密码学家研究了各个应用领域中出现的安全多方计算问题, 其中包括保密科学计算[6–8]、保密计算几何[9]、保密数据挖掘[10]等问题.计算一组隐私数据的最小值(最大值) 在保密的科学计算中是非常重要的, 可以保密地确定离散数据所处的区间. 理论上这个问题可以归约到百万富翁问题, 即通过两两比较求出最大值和最小值, 但其计算复杂性为O(n2), 其中n 为隐私数据个数. 1987 年, 文献[3] 使用算术电路解决百万富翁问题, 但计算复杂性和通信复杂性都与输入的规模呈线性关系, 只能比较两个较小的数. 2008 年, 文献[11] 将百万富翁问题归约到集合元素判定问题, 并设计了基于对称密码学的集合元素保密判定协议, 进而解决百万富翁问题, 提高了计算效率. 2013 年, 文献[12] 设计了一种新的算术编码方法, 以此解决比较两个私有数据大小的问题, 很大程度上降低协议的计算复杂性.
在安全多方计算中多次调用百万富翁协议求最大值和最小值不仅效率较低, 而且还会泄露两两数据之间的大小关系等信息; 若将该问题转化为排序问题, 在一定程度上可以提高效率, 但是这样做仍会泄露除最大值和最小值以外的其他信息. 最大值和最小值的安全多方计算要求所有参与者只能得到最大值和最小值而不能泄露其他任何信息. 这是解决最大值和最小值保密计算问题的关键所在. 文献[13–16] 利用编码方法解决了最大值和最小值的保密计算问题, 但是这些方法不能同时保密计算最大值和最小值.
同时计算一组隐私数据的最大最小值是一个新的保密科学计算问题, 目前还未见到该问题的解决方案. 如果用前述计算最大值和最小值的方法解决, 需要对同一组数进行两次编码, 并执行两次协议才能计算出最大值和最小值, 不仅计算复杂性与通信复杂性较高, 且存在泄露信息的可能性.
最大最小值的保密计算问题在信息安全实践中有重要的实际意义. 在日常生活中, 年龄、工资、成绩、产品规格的参数等数据都在较小的区间范围内, 因此保密地求出数据的阈值有很大的实际应用价值. 例如某求职者想要了解某公司的工资水平在该行业处于什么位置, 这就需要执行最大值和最小值保密计算协议来解决该问题. 除此之外, 最大最小值的保密计算问题还具有很重要的数学意义. 在求一些数据的平均值时, 需要除去该组数据的离群值(outlier) 以确保平均值的稳定性和准确性, 保密地计算出最大值和最小值对除去离群值有重大意义. 例如, 某些比赛现场中评委在打分时为了保证比赛的公平性, 需要去掉一个最高分和一个最低分后计算平均分, 在这个过程中打了最高分和打了最低分的评委的身份信息是保密的, 执行最大最小值的保密计算协议则可解决该问题.
范围查询问题同样具有很大的研究价值, 该问题出现在很多应用程序中, 包括地理信息系统, 数据库信息查询等. 在许多情况下, 数据库中包含了许多机密信息, 为了更好地提供范围查询服务, 保密地判断一个数据是否在一个区间内是很有必要的. 例如, 一个图形程序可能需要缩放一组数据(x,y) 以适应矩形显示屏或其他图形设备, 为此, 程序需要确定x 和y 的值是否在矩形所在位置的坐标范围内.
为了同时保密计算最大值和最小值, 本文提出一种新的将隐私数据编码为隐私数组的编码方法, 在此基础上利用同态加密算法可以同时保密计算最大值和最小值, 从而保密地确定离散数据的区间范围, 在避免信息泄露的同时提高效率. 本文设计了两个协议, 第一个协议可以抵抗解密密钥持有者不参与的合谋攻击; 第二个协议可以抵抗任意的合谋攻击. 并且进一步以此编码方案为基础解决了保密判断数据是否在某个区间的问题, 即保密的范围查询问题. 本文贡献主要如下:
(1) 提出了一种新的对隐私数据进行编码的方法, 进一步将这种编码方法与Paillier 加密算法结合设计了可以一次性计算一组保密数据的最大值和最小值的高效协议. 该协议可以抵抗解密密钥持有者不参与的合谋攻击.
(2) 设计了一种特殊的编码方法, 保证椭圆曲线密码系统对于明文具有加法同态性. 该编码方法对于充分利用椭圆曲线的同态性解决其他安全多方计算问题有重要的理论与实际意义. 进一步利用门限解密椭圆曲线密码系统设计了最大值和最小值的保密计算协议, 解密密钥由所有参与者共享,该协议能抵抗任意参与者的合谋攻击.
(3) 基于同样的编码方法, 设计了保密判定数据是否在区间内的协议. 用模拟范例证明了本文所设计方案的安全性, 并实际测试了协议的效率. 实验数据表明本文设计的协议是高效的.
2 预备知识
2.1 安全性定义
理想模型 假设存在一个所有参与者都信赖的第三方(Trusted Third Party, TTP). 在这种假设下安全多方计算的过程如下: 参与者Pi(i=1,··· ,n) 分别将拥有的隐私数据xi发送给TTP, TTP 自己计算函数f(x1,··· ,xn), 然后将结果分别发送给Pi.
因为参与者Pi(i = 1,··· ,n) 无法从可信的第三方中得到除f(x1,··· ,xn) 之外的任何信息, 所以理想模型下安全多方计算协议所具有的安全性是实际情况下任何一个保密计算函数f 的协议都难以达到的.理想模型下的协议虽然简单、安全, 但是在现实中所有参与者完全信任的TTP 不容易找到, 因此密码学的主要任务就是设计能够代替理想模型协议的密码学协议.
半诚实模型 在协议的执行过程中, 半诚实参与者[2]会完全严格地执行协议的每一步, 但是他们可能会保留执行协议过程中获取的信息, 并试图从这些信息推导出其他参与者的私有信息.
设参与者Pi(i = 1,··· ,n) 分别拥有私有数据xi, 他们执行协议π 保密地计算函数f(x1,··· ,xn).在计算过程中, 参与者获得的信息记为viewπi(X), 其中
Mji(j =1,··· ,t) 表示参与者Pi收到的第j 个信息, ri是参与者Pi选取的随机数. 那么对于P1,··· ,Pn中部分参与者构成的子集I ={Pi1,··· ,Pis}, 有
对于一个函数f, 如果存在概率多项式时间算法S, 使得
其中c≡表示其两边的对象计算不可区分, 则称协议π 安全地计算n 元函数f.
2.2 部分同态加密方案
部分同态加密算法是一种特殊的加密算法[17], 可以使我们在密文状态下对明文进行某种运算, 即直接对密文进行某种计算的结果, 等于对明文进行某种计算后再加密. 部分同态加密体制包括加法、乘法和异或同态加密, 其特殊性质在安全多方计算中有着重要应用, 本文设计的协议用到了加法同态性
基于此, 本文设计了基于Paillier 加密算法和椭圆曲线门限密码体制的安全多方计算协议.
2.2.1 Paillier 加密算法
Paillier 加密算法[18]的具体过程如下:
解密
假设密文
那么
因此该算法满足加法同态性质
Paillier 加密算法具有语义安全性, 即同一个明文可以加密成多个不同的密文, 这些密文都是计算不可区分的(即无法知道这些密文是不是同一个明文对应的密文).
2.2.2 椭圆曲线密码系统
椭圆曲线密码系统(Elliptic Curve Cryptography,ECC)是1985 年由Victor Miller 和Neal Koblitz共同提出的[19]. 在密码学中普遍采用的是有限域上的椭圆曲线, 其中最常用的是由下面方程定义的曲线
式(2) 中所有系数都是某一有限域GF(p) 中的元素(其中p 为一大素数).
设Ep(a,b) 表示方程(2) 所定义的椭圆曲线上的点{(x,y)|0 ≤x 首先取一大素数p 和两个参数a,b, 得到方程(2) 表达的椭圆曲线及其上面的点构成的Abel 群Ep(a,b). 取Ep(a,b) 的一个基点G(x1,y1), 要求G 的阶是一个非常大的素数(G 的阶是满足nG = O的最小正整数n). Ep(a,b) 和G 作为公开参数. 密钥生成 选择一小于p 的整数k 作为私钥, 并由K =kG 产生Ep(a,b) 上的一点作为公钥. 加密 将消息m 编码到Ep(a,b) 上一点M, 并随机选择正整数r, 计算密文 解密 使用私钥k 对密文(c1,c2) 进行解密运算, 计算过程如下 然后对明文编码点M 解码, 最终得到m. 同态性 设E(M1)=(M1+r1K,r1G),E(M2)=(M2+r2K,r2G), 那么 式(3) 表明椭圆曲线密码系统对于椭圆曲线上的点来说具有加法同态性. 如果能够设计一种线性编码方法, 使得椭圆曲线密码系统对于编码前的原始数据仍保持加法同态性, 这对于我们设计构造最大最小值的保密计算协议具有重要意义, 为此我们提出一种新的编码方法. 编码 假设选定了椭圆曲线的一个基点G, 任意给定一个正整数m, 可以将m 编码为mG. 解码给定一个消息的编码M =mG, 要解码得到消息m 需要计算椭圆曲线上的离散对数. 这个问题是困难的, 但是如果将消息限制在一个较小的范围内如m ∈{0,··· ,210}, 解码过程就可以避免计算离散对数. 我们可以制作一个乘法表T ={G,2G,3G,··· ,210G}, 要解码M 只需要反向查表即可. 这样的编码方法可使密码系统对于椭圆曲线上的点mG 的同态性转化为对于明文消息m 的同态性.这是因为明文m1,m2的编码为M1= m1G,M2= m2G, 根据式(3), 可得到E(m1G)+E(m2G) =E((m1+m2)G). 即不需要解密, 就可由m1G 和m2G 的密文直接计算得到(m1+m2)G 的密文(c1,c2).当然通过解密(c1,c2), 仅可得到(m1+m2)G, 进一步解码才能获得m1+m2. 由于椭圆曲线上离散对数问题的困难性, 无法直接由(m1+m2)G 解码获得m1+m2, 但当m1,m2的范围不太大时, 可以用上述查表法进行解码. 在可对抗合谋攻击的门限解密密码体系中[21,22], 公钥由n 个参与者联合生成, 解密密钥由这n 个参与者联合持有. 公钥可以直接用来加密消息, 但解密一个密文需要n 个参与者中一定数量人员合作才能完成. 在安全多方计算中, 总希望抵抗尽可能多参与者的合谋攻击, 因而需要朴素的门限密码体制, 即(n,n)门限密码体制, 具体过程如下. 密钥生成 选定一条椭圆曲线Ep(a,b) 及其上的一个基点G, 假设G 的阶是一个非常大的素数q.Ep(a,b) 和G 作为公开参数. 每个参与者Pi任意选择一个私钥ki 加密 首先将消息在椭圆曲线Ep(a,b) 上进行编码得到点M, 并随机选择正整数r(1 ≤r ≤q −1),通过加密运算得到(c1,c2)=(M +rK,rG). 解密 每个参与者Pi根据私钥ki计算kic2, 将计算结果发送给其他参与者, 然后所有参与者联合解密(c1,c2) 得到编码点M 本节, 我们利用Paillier 加密算法设计一个同时计算最大值与最小值的协议. 编码方法 假设所有参与者Pi(i = 1,··· ,n) 的私有数据xi∈{z1,z2,··· ,zl} = U(对于很多应用场景如涉及人的年龄、学生的成绩、人们的工资等, 集合U 是客观存在的), 其中z1< z2< ··· < zl且|U|=l. 参与者Pi(i=1,··· ,n) 首先按照下面的方法构造一个数组 其中 rij∈ZN为不等于0 的随机数. 依此方式, Pi拥有的秘密数据xi与数组Xi构成一一对应关系. 对得到的n 个数组X1,··· ,Xn求和, 即将这些数组的对应元素相加, 得到一个新的数组 例1 假设x1=4,x2=7,x3=2,x4=5, 令U ={1,2,3,4,5,6,7,8,9} 并构造表1. 显然, 按照数组Y 的顺序方向, 第一个不为0 的元素17 所在的位置在全集U 中对应的元素2 为最小值; 按照数组Y 的逆序方向, 第一个不为0 的元素39 所在的位置在全集U 中对应的元素7 为最大值. 事实1 对于n 个参与者拥有的数据x1,··· ,xn, 均按照方式(4) 构造数组Xi, 将数组Xi对应位置的元素相加, 得到一个新的数组: Y = (y1,··· ,yl). 按照数组Y 顺序方向, 当首次出现yi̸= 0 时,min{x1,··· ,xn}=zi; 按照数组Y 逆序方向, 当首次出现yj̸=0 时, max{x1,··· ,xn}=zj. 证明: 因为对于每个编码后得到的数组Xi(i = 1,··· ,n) 来说, xi在全集U 中所在的位置对应的元素为随机数rij, 其余位置对应的元素为0, 将数组Xi(i=1,··· ,n) 对应位置的元素进行相加得到数组Y, 相当于在全集中对最大值和最小值的位置进行标记, 第一个不等于0 的元素yi和最后一个(按照数组Y 逆序方向为第一个) 不等于0 的元素yj在数组Y 中所在的位置则为最大值和最小值在全集中所在的位置.上述事实是我们保密计算最大值和最小值的依据, 直接这样做没有保密性可言. 要实现最大最小值的保密计算需要在密文状态下对明文进行运算, 并分别从左向右解密得到最小值后再从右向左解密计算最大值. 而Paillier 加密算法和椭圆曲线密码系统均是加法同态算法, 可实现保密求和运算. U 1 2 3 4 5 6 7 8 9 X1 0 0 0 21 0 0 0 0 0 X2 0 0 0 0 0 0 39 0 0 X3 0 17 0 0 0 0 0 0 0 X4 0 0 0 0 16 0 0 0 0 Y 0 17 0 21 16 0 39 0 0 协议1 基本最大最小值保密计算方案(参与者之间有安全信道)输入: P1,··· ,Pn各自的秘密数据x1,··· ,xn. 输出: y =min{x1,··· ,xn};z =max{x1,··· ,xn}. (1) P1使用Paillier 加密算法产生私钥和公钥, 并公布公钥. (2) 所有参与者Pi(i = 1,··· ,n) 根据3.1 节式(4) 中构造数组的方法, 将私有数据xi转化为数组Xi, 其中 并使用公钥加密数组Xi得到密文序列 (3) 令C =(c1,··· ,cl)=(1,··· ,1). Pi(i=1,··· ,n −1) 依次计算 并把结果发送给Pi+1. Pn按照上述方法做同样的计算得到C =(c1,··· ,cl). (4) Pn将密文数组C 的元素从左向右依次逐个发送给P1, P1进行解密. 当解密得到第一个不等于0 的元素yi时, P1终止密文发送, 并令min{x1,··· ,xn} = zi; 然后Pn从右向左依次将C 的元素逐个发送给P1, P1解密得到第一个不等于0 的元素yj时终止密文发送, 并令max{x1,··· ,xn}=zj. (5) P1公布min{x1,··· ,xn},max{x1,··· ,xn}. 正确性分析 协议1 的正确性可由3.1 节中所述的事实1 得到保证. 安全性分析 在协议1 中, P1对数组C 中元素进行解密运算. 由于P1持有私钥能够解密, 协议1 能够抵抗没有P1参与的合谋攻击. 为了保证协议1 的安全性, 密文传输的过程需要建立在安全信道之上. 定理1 同时保密计算最大值与最小值的协议1 在半诚实模型下是安全的. 证明: 通过构造满足式(1)的模拟器S 来证明定理1, 分为以下三种情况: (1) P1不参与合谋, I = {P2,··· ,Pi−1,Pi+1,··· ,Pn} 要获得Pi保密数据的相关信息. S 的模拟过程如下: (a) 给定输入(I,XI,fI(X)), 即(I,XI,fI(X)) = (I,(x2,··· ,xi−1,xi+1,··· ,xn),fI(X)), 随机选择两个数据x′1∈{z1,z2,··· ,zl} = U 和x′i∈{z1,z2,··· ,zl} = U, 使得fI(X) = fI(X′), 在这里X′={x′1,x2,··· ,xi−1,x′i,xi+1,··· ,xn}. (b) 模拟器S 将X′中的每个数据x′i编码为数组X∗1,··· ,Xi−1,X∗i,Xi+1,··· ,Xn. 然后模拟器S利用公钥加密X∗1,··· ,Xi−1,X∗i,Xi+1,··· ,Xn, 得到 (c) 模拟器S 按照协议1 将密文数组中对应元素相乘, 得到数组C∗. 然后解密得到fI(X′). 在协议1 中 令 由于Paillier 加密算法是语义安全的, 对I 中参与者来说, 密文数组C 与C∗是计算不可区分的, 即Cc≡C∗. 又由于fI(X)=fI(X′), 故有 由此可知, 在情况(1) 下, 协议1 是安全的. (2) P1不参与合谋, I ⊂{P2,··· ,Pi−1,Pi+1,··· ,Pn} 要获得Pi保密数据的相关信息. 由情况(1) 可知, 当I = {P2,··· ,Pi−1,Pi+1,··· ,Pn} 时, 只有P1拥有私钥可以解密, 因此参与合谋方得不到私有数据x1和xi的相关信息. 那么当I ⊂{P2,··· ,Pi−1,Pi+1,··· ,Pn} 时, 同样因为只有P1拥有私钥可以解密, 所以参与合谋方得不到与x1、xi有关的信息. 即在最大合谋(攻击者) 结构参与合谋的情况下是安全的, 合谋者为其子集时也是安全的. (3) P1参与合谋, I ={P1,··· ,Pi−1,Pi+1,··· ,Pn} 要获得Pi保密数据的相关信息. 在此情况下, 由于P1拥有私钥可以解密, 且有n −1 个参与者参与合谋, 他们可以获知Pi的私有数据xi的相关信息. 如果参与合谋方利用可信的第三者同时保密计算最大值和最小值, 当xi是最大值或者最小值时会泄露数据xi的大小; 当xi不是最大值或者最小值时, 参与合谋方只能确定xi处于某个区间内. 因此这和使用可信第三者的安全性只有微小的差别. 由此可知, 协议1 可以抵抗解密密钥持有者不参与的所有合谋攻击. 上节提出了计算最大值和最小值的高效方案, 但是该方案只能抵抗没有P1参与的合谋攻击. 如果P1与Pn合谋, 就可以知道所有参与者的隐私数据集合(但不知道Pi和xi的对应关系), 这对于其他参与者是不公平的, 也是协议的安全弱点. 为了阻止P1参与的合谋攻击, 本部分我们应用椭圆曲线密码系统, 构造一个所有参与者联合解密的最大值和最小值保密计算方案, 其安全性更强. 协议2 各参与者地位平等的抗合谋的最大最小值保密计算方案 输入: P1,··· ,Pn各自的秘密数据x1,··· ,xn. 输出: y =min{x1,··· ,xn};z =max{x1,··· ,xn}. (1) P1,··· ,Pn商定一条椭圆曲线Ep(a,b) 及其上的一个生成元G(要求G 的阶L 足够大), 然后每个参与者Pi选择私钥ki,2 ≤ki≤L −1, 联合生成公钥(K,G) (2) 所有参与者Pi(i=1,··· ,n) 以方式(4) 将自己的数据转化为数组Xi, 其中 然后, Pi将数组Xi的每个元素编码成为椭圆曲线Ep(a,b) 上的点Mij=xijG, j ∈[1,l], 得到 并加密Mi的每个元素, 得到下面编码密文数组E(Mi), 并公布 (3) 所有参与者利用密文数组构成一个密文矩阵M 将矩阵M 每一列的元素相加, 得到一个新的密文数组 (4) 所有参与者联合对密文数组T 从左到右解密, 并对解密结果进行解码, 当得到第一个不等于0 的元素yi时停止计算, 则min{x1,··· ,xn} = zi; 然后他们转而从右向左解密, 并对解密结果进行解码, 当得到第一个不等于0 的yj时停止计算, 则max{x1,··· ,xn}=zj. 正确性分析 首先, 在协议第2 步中, 每个Pi将私有数据xi按照方式(4) 构造对应的长度为l 的数组Xi, 再将Xi中元素应用编码方式Mij= xijG 编码到椭圆曲线上并进行加密, 最终得到密文数组E(Mi). 所用编码方式保证了在应用椭圆曲线加密方案进行计算时对Xi中的元素也具有加法同态性. 协议的第3 步中, 参与者构造与编码矩阵相对应的密文矩阵M, 对M 中每一列所有元素求和, 根据加密算法的加法同态性, 可得出 协议的第4 步中, 所有参与者联合解密T, 以下是进行解密运算的过程 定理2 同时保密计算最大值与最小值的协议2 在半诚实模型下是安全的. 证明: 对于任意n −1 个参与者构成的合谋者集合是一个最大攻击(合谋) 者结构, 只要对此合谋者结构是安全的, 则对于其他任意合谋者集合都是安全的. 若要证明对于这个合谋者结构是安全的, 则需构造相应的模拟器S, 使得(1) 式成立. 由于各参与者地位的平等性, 不妨设P2,··· ,Pn试图通过合谋来获取P1的私密数据x1的有关信息, 分为以下两种情况: (1) I ={P2,··· ,Pn} 合谋要得到参与者P1的保密数据的相关信息, S 的模拟过程如下: (a) 给定输入(I,XI,fI(X)), 即(I,XI,fI(X)) = (I,(x2,··· ,xn),fI(X)), 随机选择一个数据x′1∈{z1,z2,··· ,zl}=U, 使得fI(X)=fI(X′), 在这里X′={x′1,x2,··· ,xn}. (b) 模拟器 S 将 X′中的每个数据 x′i按照方式 (4) 构造为数组 X∗1,X2,··· ,Xn, 再将所有数组元素编码到椭圆曲线上得到 n 个编码数组 M∗1,M2,··· ,Mn, 然后加密得到 n 个密文数组E(M∗1),E(M2),··· ,E(Mn). (c) 模拟器S 按照步骤3 将密文矩阵中对应元素相加, 得到新的密文数组T∗. 然后解密得到椭圆曲线上的点, 进一步解码得到fI(X′). 在协议2 中 令 因为概率公钥加密系统是语义安全的, 并且所有参与者合作才能正确解密(即使I 中的所有参与者合谋也无法解密任何密文),所以密文数组T 与T∗是计算不可区分的,即Tc≡T∗. 又由于fI(X)=fI(X′),故有 (2) I ⊂{P2,··· ,Pn} 合谋要得到P1保密数据的相关信息. 由情况(1) 可知, 当I = {P2,··· ,Pn} 时, 因为参与合谋方无法正确解密密文, 所以不能得到任何有关x1的信息. 那么当I ⊂{P2,··· ,Pn}, 参与合谋方同样也不能获得x1的相关信息(因为I 的任何子集能够得到的信息都不超过I 能够得到的信息). 因此在情况(2) 下, 协议2 也是安全的. 由此可知, 在半诚实模型下协议2 是安全的. 本节对上述两个最大最小值保密计算方案的效率进行分析比较. Paillier 加密算法加密一次需要进行2 次模指数运算, 解密一次需要进行1 次模指数运算. 椭圆曲线上的ElGamal 加密方案加密需要2 次椭圆曲线乘法运算, 解密需要1 次椭圆曲线乘法运算(椭圆曲线上的乘法运算对应于ElGamal 加密算法的模指数运算). 文中协议1,2 的性能分析见表2. 在协议1 中, 所有参与者都需要将数组中的每一个元素加密, n 个参与者需要进行2nl 次模指数运算,然后P1对密文数组C 进行解密, 如果最小值在数组Y 中按顺序方向处于第i 位, 最大值在数组Y 中按逆序方向处于第j 位, 则要进行i+j 次模指数运算. 因此协议1 总共做了2nl+i+j 次模指数运算. 协议2 中所有参与者对数组中的每一个元素进行加密, 需要进行2nl 次运算, 然后所有参与者对密文数组T 进行联合解密得到数组Y, 如果最小值在数组Y 中按顺序方向处于第i 位, 最大值在数组Y 中按逆序方向处于第j 位, 那么需要进行i+j 次解密运算. 因此协议2 的计算复杂性是O(nl). 衡量通信复杂度的指标一般为协议的通信轮数或者传送比特总数. 在安全多方计算中, 通常采用通信轮数衡量. 在协议1 中, Pi(i = 1,··· ,n −1) 将收到的密文数组E(Xi−1) 与自己拥有的E(Xi) 进行运算之后发送给Pi+1, 在这个过程中需要n −1 轮通信. 最终, Pn完成运算后将结果发送给P1解密, 如果最小值在数组Y 中按顺序方向处于第i 位, 最大值在数组Y 中按逆序方向处于第j 位, 则Pn需要向P1发送i+j 轮消息, 所以协议1 共需要n+i+j −1 轮通信. 在协议2 中, 所有参与者构造公钥需要1 轮通信. 加密过程公布E(Mi) 需要1 轮通信. 如果最小值在数组Y 中按顺序方向处于第i 位, 最大值在数组Y 中按逆序方向处于第j 位, 解密过程需要i+j 轮通信, 共需要i+j+2 轮通信. 性能 协议1 协议2计算复杂性 2nl+i+j O(nl)通信复杂性 n+i+j −1 i+j +2安全性 抵抗除P1 外的合谋攻击 抵抗合谋攻击 为了更清晰地展现方案的可行性和计算效率, 本文使用Java 语言编程测试了执行协议1, 协议2 所需要的时间. 实验测试环境: Windows XP 专业版32 位操作系统, CPU 为Intel(R) Core(TM) i3-2100 CPU @3.10 GHz, 内存是2.99 GB. 本文所做模拟实验均使用Java 语言在MyEclipse 上运行实现. 实验方法: 实验选取范围为0–100 的数据, 参与者人数分别设定为2, 4, 6, 8, 10. 为了保证数据的准确性, 本文进行10 次模拟实验测试, 然后对测试结果求平均值(仅考虑加密与解密过程所耗费的时间, 忽略密文传输所需的通信时间). 协议1 采用Paillier 加密算法, 设定素数大小为512 比特. 协议2 采用椭圆曲线密码系统, 其中参数p,a 和b 均取256 比特, 私钥长度最大限值取273 比特. 实验结果如图1 所示. 由图1 可知保密地同时求解最小值与最大值的执行时间随参与者人数增长而线性增加. 基于门限解密算法的最大最小值保密计算方案效率高于基于Paillier 加密算法的最大最小值保密计算方案. 一次计算一组隐私数据的最大最小值是一个新的保密科学计算问题, 目前该问题还未被研究. 现有的方法需要对同一组隐私数据进行编码的变换并重复调用协议才能分别求出最大值和最小值, 这样会使协议的计算效率较低. 文献[13] 利用编码和ElGamal 算法实现了最小值的保密计算. 如果要计算最大值, 需要变换编码方法后再次对数据进行编码, 然后调用协议. 如果全集的势为l, 最小值为y, 协议共需进行加密运算nl 次与解密运算y 次, 即进行模指数运算2(nl+y) 次. 若要同时保密计算最大值与最小值, 则需执行两次协议,显然, 本文所设计的协议计算效率更高. 文献[14] 所研究问题与文献[13] 类似. 文献[14] 使用保密替换的方法解决了最小值的保密计算问题.加密过程所有参与者最多共需要2nl 次模指数运算, 解密过程进行log p 次模指数运算(p 为GM 加密系统中的大素数私钥), 总共需要2nl+log p 次模指数运算. 若要实现最大值和最小值的保密计算, 同样需要变换编码方法并执行两次协议. 因此本文协议在计算效率上具有显著优势. 文献[15] 使用0-1 编码方案和NTRU 加密算法在云环境下保密计算最小值, 每位参与者需要l+1次模指数运算, 因此共需要n(l+1) 次模指数运算. 基于最大值问题和最小值问题的对称性, 改变全集的排序顺序和相应的编码方式后再次调用协议可实现最大值的保密计算. 本文通过一次编码保密计算最大值和最小值, 在提高计算效率的同时避免了不必要的信息泄露. 文献[16] 研究的问题是有一个数据收集者要利用分散用户的智能手机感知有关数据, 并以保密的形式获取这些数据的最小值. 平均每位用户需要进行2 log2M 次逐位异或运算, 3 log2M 次比较运算. 数据收集者需要进行(n −1)log2M 次逐位异或运算和log2M 次比较运算(其中用户私有数据的范围为[0,M −1]). 该解决方案假设有一个权威可以为所有参与者生成关键信息(等同于加密密钥), 并且未考虑权威和用户之间的合谋, 这将导致严重的安全问题. 本文考虑的是标准的安全多方计算场景, 没有可信的第三方, 仅凭借参与者之间的交互完成保密计算, 参与者之间可能合谋. 本文协议1、协议2 与文献[13–16] 的计算效率比较结果如表3 所示. 协议 计算复杂性 通信复杂性 执行协议次数协议1 2nl+i+j n+i+j −1 1协议2 O(nl) i+j +2 1文献[13] 2(nl+y) n+y −1 2文献[14] 2nl+log p n 2文献[15] n(l+1) 3n −1 2文献[16] O(n log2 M) log2 M 2 协议1 与协议2 解决了最大最小值的保密计算问题, 从而确定了离散数据所在的区间. 在本节中, 我们以协议1 使用的编码方案为基础, 进一步设计了保密判断隐私数据是否在隐私区间内的协议. 问题描述 假设Alice 拥有一个私密数据x, Bob 拥有一个私密区间[y1,y2], 他们希望判断Alice 的私有数据是否在Bob 的私有区间内, 而不泄露自己的信息. 基本原理 Alice 首先将私有数据x 按照3.1 节中的方式(4) 编码成一个数组X = {x1,x2,··· ,xl},假设区间左端的数据y1在全集U 中处于第k 位, 区间右端的数据y2在全集U 中处于第m 位, Bob 根据区间两端的数据y1和y2在全集U 中的排列位置, 做如下计算 上述事实是我们判断数据是否在区间内的依据, 我们选用具有加法同态性的Paillier 加密算法来加密数组, 使得加密后的0 和随机数r 在计算上不可区分, 从而实现保密地判断数据是否在区间内. 协议3 数据是否在区间内的保密判定方案 输入: Alice 的私有数据x, Bob 的私有区间[y1,y2]. 输出: 是否x ∈[y1,y2]. (1) Alice 使用Paillier 加密算法产生私钥和公钥, 并公布公钥. (2) Alice 以方式(4) 将自己的数据转化为数组X, 并用公钥将数组X 加密为E(X) 发送给Bob. (3) Bob 根据区间两端的数据y1和y2在全集U 中的位置, 利用加法同态性做如下计算 然后将E(V) 发送给Alice. (4) Alice 用私钥解密E(V) 得到V. 若V =r, 则数据x 在区间[y1,y2] 内; 若V =0, 则数据x 不在区间[y1,y2] 内. 正确性分析 协议3 的正确性可由6.1 节中所述的事实2 得到保证. 安全性分析 协议3 的安全性由Paillier 加密算法的语义安全性得以保证, 本文可通过构造满足式(1)的模拟器证明其安全性, 具体证明过程如下. 定理3 保密判定数据是否在区间内的协议3 在半诚实模型下是安全的. 由此可知, 协议3 在半诚实模型下是安全的. 在安全多方计算领域, 同时保密计算最大值和最小值问题是一个全新的问题, 在密码学理论与隐私保护实践中有重要的应用, 可以保密地确定离散数据所在的区间. 本文设计了一种新的编码方法, 并使用Paillier 加密算法, 椭圆曲线门限密码系统构造了两个保密计算最大值和最小值的安全而高效的协议, 进一步以此为基础构造了一个解决区间判定问题的协议. 本文提出的协议对于半诚实参与者都是安全的, 且在私有数据范围已知的情况下适用. 今后将进一步研究如何在私有数据范围未知的情形下, 进行最大值和最小值的保密计算, 以及提出适用于恶意模型的解决方案.
2.3 线性编码
2.4 门限解密
3 基于Paillier 算法的最大最小值保密计算协议
3.1 基本原理
3.2 具体协议
3.3 方案分析
4 基于门限解密的最大最小值保密计算协议
4.1 具体协议
4.2 方案分析
5 效率分析
5.1 计算复杂性分析
5.2 通信复杂性分析
5.3 实验数据分析
5.4 方案比较
6 保密判断数据是否在区间内
6.1 判断数据是否在区间内的保密计算方案
6.2 方案分析
7 结论
