第43 卷第 9 期计 算 机 学 报 Vol. 43 No. 92020 年9 月CHINESE JOURNAL OF COMPUTERS Sep. 2020收稿日期：2019-09-16；在线发布日期：2020-02-07. 本课题得到国家自然科学基金面上项目（61272435）资助. 李顺东(通信作者)，博士，教授，博士生导师，中国计算机学会（CCF）会员，主要研究领域为密码学与信息安全. E-mail: shundong@snnu.edu.cn. 张萌雨，硕士研究生, 主要研究方向为密码学与信息安全.盲百万富翁问题的高效解决方案李顺东 张萌雨(陕西师范大学计算机科学学院西安 710119)摘 要安全多方计算是密码学研究的一个重要领域，也是国际密码学研究的热点之一. 百万富翁问题是第一个安全多方计算问题，它研究的是Alice 和Bob 各拥有一个私有数据x、y，保密比较x、y 大小的问题. 研究人员提出了许多解决方案，并在其基础上拓展出了许多新的问题. 本文对百万富翁问题进行了新的拓展，提出这样的问题: Alice、Bob、Carol 和Dove 各拥有保密数据x、y、u、v，他们要保密判定x+y 和u+v 的大小关系，但是都不愿意泄露自己的保密数据. 在此情况下，没有人知道x+y、u+v 的具体数值. 我们称这个问题为盲百万富翁问题，其具有重要的理论与实际意义. 为解决此问题，我们利用概率加密算法的性质和移位寄存器的思想设计了新的保密移位添加方法. 然后在半诚实模型下设计了参与者为三方、四方和n 方的三个不同盲百万富翁问题的解决方案，并应用模拟范例证明了方案的安全性，可以抵抗任意的合谋攻击. 最后，对协议进行了效率分析和实验测试，理论分析和实验结果都表明本文的协议是高效的、实用的. 保密移位添加方法不仅可用于解决本文的盲百万富翁问题，还可以作为基础模块去解决其它安全多方计算问题. 盲百万富翁问题也为安全多方计算提供了新的研究思路.关键词 安全多方计算；百万富翁问题；盲百万富翁问题；概率加密中图法分类号 TP309 DOI 号 10.11897/SP.J.1016.2020.01755An Efficient Solution to the Blind Millionaires¢ ProblemLI Shun-Dong ZHANG Meng-Yu(School of Computer Science, Shaanxi Normal University, Xi’an 710119)Abstract The study of secure multi-party computation started in 1986, by Andrew Yao, and quicklybecame an extremely active area of research in academic circles and a hot topic of internationalcryptographic community. The millionaires¢ problem is the first secure multiparty computation problem andthe most fundamental one in secure scientific computing. It studies how two parties, Alice and Bob withprivate numbers x and y, respectively to jointly determine which of x and y is bigger without disclosing anyother information. It is an important building block of many other secure multiparty computation protocols.The researchers proposed many effective solutions to the millionaires¢ problem and generalized a series ofnew secure multiparty computation problems including private maximum and minimum computation,secure vector dominance, secure sorting, and so on. The existing protocols only work when the participantsknow the plaintext of the private data, but in some scenarios, the protocol of millionaires¢ problem may beused as a sub-protocol. In this case, the participants may not know the private data which are in the form ofciphertext, and therefore, no existing protocol works. How to address millionaires¢ problem when theprivate data is not known. This problem has not been investigated in literature. This paper extendsmillionaires¢ problem in a new direction. We propose the following problem: Alice, Bob, Carol, and Dovehave private numbers x, y, u and v, respectively and they want to determine the relation between x+y and1756 计算 机 学 报 2020年u+v without disclosing x, y, u, v. No party knows the value of x+y, u+v in this scenario. We call thisproblem the blind millionaires¢ problem. It is of important theoretical and practical significance but cannotbe solved or cannot be well solved using the existing solutions. It is necessary to design specific protocolsfor this problem. To solve this problem, we first use the randomization property of probabilistic encryptionalgorithm to securely substitute some ciphertexts. Then, we use secure substitution and the idea of shiftregister to propose a secret shift adding method. This method can be used to securely add, subtract andmultiply on ciphertexts on the condition that the plaintext space is small. Based on the secret shift addingmethod, combining with threshold decryption probabilistic cryptosystem, we design secure comparisonprotocols for three comparing problems in small plaintext space. The participants of the three protocols are3, 4 and n. Second, we use the simulation paradigm to prove that these protocols are secure in thesemi-honest model. These protocols can resist collusion attack of n-1 parties. With different encodingmethod, different protocol is appropriate for different problem it solves. We analyzed and compared ourprotocols with the most similar literature we can find. We also tested the execution time of the protocols.Both theoretical analysis and experimental results show that the protocol proposed in this paper is efficientand practical. Furthermore, the secret shift adding method can also be used as a basic building block tosolve other secure multiparty computation problems. And the questions raised in this paper also provide anew research direction for the readers.Keywords secure multiparty computation; millionaires' problem; blind millionaires' problem; probabilisticencryption1 引言1982 年Andrew Yao 在文献[1]中首次提出百万富翁问题，这标志着安全多方计算的诞生. 安全多方计算（Secure Multi-party Computation, SMC）也称为安全计算、多方计算或保密计算，是密码学的一个关键领域. 安全多方计算被认为是各种现实隐私保护问题的实际解决方案，特别是那些只需要共享秘密且各方之间没有太多交互的问题，例如分布式投票、私人竞标和拍卖、共享签名或解密功能以及私人信息检索[2]等.Goldreich 等人[3, 4]对安全多方计算进行了深入的研究，并给出了适用于所有安全多方计算问题的通用解决方案. 多年来，通用安全多方协议的概念成为孕育具体问题协议的沃土. 但通用方案在求解具体的安全多方计算问题时，仅是一个问题可解的理论性证明，目前还不具有实际的可行性，原因有以下两点：一方面，除简单的布尔运算外，将一般计算问题转化成电路计算的转化复杂性很高；另一方面，使用通用方案解决一般的实际问题所需要的存储和计算都太多，效率太低. 随着通用解决方案的不断改进和优化，未来通用解决方案也可能用于解决一些实际问题，但目前解决实际问题的主要途径是针对实际应用提出具体高效的解决方案.所谓百万富翁问题是指百万富翁Alice 和Bob分别拥有财富x、y，他们想要保密判定x 和y 的大小关系. 这是第一个安全多方计算问题，也是保密科学计算[1],[5-11]研究中的一个最基础的问题. 研究人员提出了许多高效的解决方案[1],[12-20]. 文献[1,4]的方案只能比较两个数的大小，无法判定两个数是否相等. 秦静等人在文献[12]中基于Φ 隐藏假设和同态加密体制的语义安全性假设，给出了一个高效安全的无信息泄漏的比较相等协议；Luo 等人在文献[13]中利用计算几何中的叉积协议和同态加密体制设计了一个高效的秘密比较方案，该方案能够一次有效地判定数据的大小或相等关系；文献[14]应用算术编码的方法解决两方秘密比较问题，大大降低了协议的计算复杂度. 但文献[12-14]只适用于两方参与者，且参与者仅持有单个数据的情形. 文献[15-17]巧用0-1 编码方法给出了判断两个数据大小关系的高效解决方案. Li 等人在文献[18]中使用三角性面积公式解决了有理数比较大小的问题. 文献[20]提出了一种使用现实中纸牌进行数据大小关系判定的协议，但是其适用于计算机不可使用的情况.百万富翁问题不仅是最基本的安全多方计算问9 期李顺东等：盲百万富翁问题的高效解决方案 1757题，还是解决其他安全多方计算问题的基础. 其还可以派生出许多其它重要的可以用于解决许多实际应用的问题. 这些派生问题包括: 参与者人数不变，但每个参与者持有的数据是隐私向量的安全向量优势问题[21]；多个参与者保密计算其隐私数据的最大（小）值问题[11]、计算平均值问题、计算第k 个最大（小）值问题和多个保密数据排序问题[22, 23]等.目前研究百万富翁问题的解决方案仅适用这样的场景: 参与者知道被比较的隐私数据. 但有的时候需要在参与者只知道隐私数据密文的情况下保密比较得出相应的明文数据的大小关系. 我们称这种情况下的比较问题为盲百万富翁问题，此类问题具有更广泛的应用背景和实际意义，例如下面的问题都属于盲百万富翁问题.1. A 公司计划建一座大楼，B、C 两家公司分别负责大楼建设和后期装修. A 公司的预算资金为a，B、C 两家公司的建设费用分别为b、c. 在正式达成合作前，任何一方都不想泄露自己的建设费用. 要在不泄露各方建设费用的情况下，判断这三家单位有没有可能达成建设协议，就需要保密判定a 是否大于b+c. 这个问题可以抽象为在知道x 不知道y的情况下，保密判定x 和y 的大小关系.2. 在某次大型商业招标活动中，A 和B、C 和D 分别达成协议合作竞标. 其中，A、B、C、D 分别计划出资金额为a、b、c、d. 他们都希望中标，但在中标前每一方都不想让任何一方(包括合作方和招标方)获知自己的报价. 这就需要在不知道a+b和 c+d 的情况下（泄露a + b对于 A，B 来说就是泄露了a，b），保密判定a+b 和c+d 的大小关系. 这个问题可以抽象为在不知道x 和y 的情况下，保密判定x 和y 的大小关系.3. 有A、B 两个备选方案， n 个人想要在不泄露自己对哪个方案偏好的情况下调查这两个方案哪个更受欢迎. 记参与者Pi 对方案A的喜爱程度为 xi ，对方案 B 的喜爱程度为 yi . 在这个场景下需要参与者在不知道å xi 和å yi 的情况下，保密判定å xi 和å yi 的大小关系. 这个问题同样可以抽象为在不知道x 和y 的情况下，保密判定x 和y 的大小关系.这三个盲百万富翁问题与百万富翁问题既有相同之处，又有不同之处. 相同之处是本质上都是保密比较x 和y 的大小.不同之处在于: (1)在百万富翁问题中有两个参与者属于双方安全计算，在盲百万富翁问题中有两个以上的参与者属于安全多方计算；(2) 在百万富翁问题中，两个参与者分别持有要比较的隐私数据x 和y 的明文. 而盲百万富翁问题逻辑上可以划分为两个子问题: 求和问题和密文比较大小问题. 参与者在合作求得 xi 和的密文E(å xi ) 以及 yi 和的密文 E(å yi ) 后，保密比较E(å xi ) 和 E(å yi ) 得到 å xi 和 å yi 的大小关系. 即在盲百万富翁问题中，所有参与者持有的都是要比较的隐私数据å xi 和å yi 的密文. 也正因为存在上述的两个本质上的区别，所以现有的百万富翁问题的解决方案都不能用于解决盲百万富翁问题.密文比较大小这一问题鲜有研究. 目前我们仅知道文献[24]中的SLT 协议（Secure Less than Protocol）使用Paillier 公钥系统的性质解决了该问题.又由于Paillier 公钥系统具有加法同态性，可以解决求和问题. 所以，可以以文献[24]的SLT 协议为基础构造盲百万富翁问题的解决方案. 但使用文献[24]所实现的解决方案存在两个方面的缺陷: 首先，Paillier 公钥系统难于构建门限密码系统，且即使构建了门限解密，由于存在一个密钥的分发者，使得协议的参与者之间不平等，只要分发者参与合谋，其他参与者的安全性就无法得到保证；其次，使用Paillier 公钥系统的性质解决有严格的条件限制，其要求 x, y, x - y, (x - y) × r < N 2 . 其中，随机数 r 是保护x-y 的值不泄露的关键，但由于r 是随机数，所以(x - y) × r < N 2这一条件限制很难得到保证，进而在实际使用中可能会出现错误或信息泄露.综上所述，现有的研究都不能或者不能很好地解决本文所提出的盲百万富翁问题，所以需要针对这一具体问题提出高效的解决方案.为了解决该问题，本文设计了一种新的保密移位添加方法. 在该方法的基础上提出了三个不同类型盲百万富翁问题的解决方案，这三个方案适用于不同的应用场景，每一个方案都是实用和高效的，都不需要调用其它协议. 由于方案不需要加密系统具有任何同态性，所以可以选用效率高的概率加密系统实现.本文的主要贡献如下：(1) 对百万富翁问题进行推广，提出了新的盲百万富翁问题，该问题具有重要的理论与实际意义.(2) 利用移位寄存器的思想和概率加密的性质提出了一种新的保密移位添加方法，该方法可以用于实现小数据的加减运算，可以作为一种新的安全多方计算方法去解决许多问题.(3) 使用新的方法解决了盲百万富翁问题，并用模拟范例证明了协议在半诚实模型下是安全的，可以抵抗任意数量的合谋攻击.(4) 对协议进行了效率分析和实验验证，理论1758 计算 机 学 报 2020年分析和实验结果都表明本文方案是高效的.2 预备知识2.1 安全性定义半诚实模型: 半诚实参与者[4]在协议执行过程中完全按照协议要求诚实地执行协议，但有可能会记录协议执行过程中所收集到的信息，并试图根据收集到的信息推算其他参与者的私有信息. 如果所有参与者都是半诚实的，则称这样的模型为半诚实模型. 本文所设计的协议都是半诚实模型下的安全多方计算协议.设有 n 个参与者 P1,L, Pn ，分别拥有私密数据x1,L, xn ,记 X = (x1,L, xn ) . 他们利用协议P 保密地计算 f (X ) = ( f1(X ),L, fn (X )) ，其中 fi (X )(iÎ[n] ={1,L,n}) 为参与者 Pi 得到的输出结果. 在协议执行过程中， Pi 得到的信息序列记为( ) ( 1 t )viewi X xi ri Mi Mi P = , , ,L, ,其中， j ( 1 )Mi j = ,L,t 表示 Pi 收到的第 j 个信息. 对于部分参与者构成的子集1 { }I Pi Pis = ,L, Í{P1,L, Pn}，记1 ( ) ( ( ) ( )) viewI X I viewi X viewis X P = , P ,L, P .定义 1(半诚实参与者的安全性[4]). 在参与者都是半诚实的情况下，如果存在概率多项式时间算法S，使得对于任意的1 { }I Pi Pis = ,L, Í{P1, L, Pn}，均有下式成立:1 ({0 1} )({0 1} ){ ( ( )) ( ))}{ ( )}nsni i I XcI XS I x x f Xview X**Î ,PÎ ,, , , ,ºL(1)其中cº表示计算上不可区分，则称协议P 保密地计算了n元函数 f (X ) .如果对于任意n -1个参与者构成的集合 I，都存在满足(1)式的S ，则称协议P 能够抵抗任意数量的合谋攻击.半诚实模型是非常重要的一个研究模型. 一方面， 许多实际的参与者都是半诚实的， 且按照Goldreich 的通用转化方法，可以将在半诚实参与者条件下保密计算函数f 的协议P 转化为在恶意参与者条件下也能保密计算 f 的协议P¢，新协议可以迫使恶意参与者以半诚实方式执行协议. 另一方面，对恶意模型的研究可以建立在对半诚实模型研究的基础上，通过分析恶意参与者可能存在的恶意行为，将阻止恶意行为的方法添加到协议中，从而使新协议对恶意参与者也是安全的. 基于上述两点可知，研究半诚实模型下安全的协议是具有实际意义的.2.2 加密系统2.2.1 概率加密在给定明文和密钥的前提下，确定性加密方案总是产生相同的密文，这样在明文空间较小的应用中很容易受到选择明文攻击，例如经典的RSA 加密系统. 针对确定性加密方案的这一缺陷，Shafi Goldwasser和Silvio Micali 在文献[25]中首次提出了概率加密的概念，并给出了第一个可证明安全的概率公钥加密方案. 常用的概率加密算法包括ElGamal、Paillier 和随机预言机模型下的各种结构.概率加密在加密算法中加入了随机数，因此加密相同的消息时，只要选取不同的随机数就会产生不同的密文. 实际上，为了保持语义安全，即隐藏有关明文的全部信息，加密算法必须是概率性的. 可以将概率公钥加密算法的加密过程简单表达为c¬ Encrypte ( pk,m, r).其中， c 为m 的密文,e 表示公钥加密方案, pk 为公钥， m 为明文消息， r 为随机数.2.2.2 门限解密门限解密[26, 27]是抵抗合谋攻击的一个重要工具. 为了保证每个参与者数据的私有性，使协议能够抵抗任意数量的合谋攻击，就需要朴素的(n, n)门限密码系统: n 个参与者联合生成公钥，解密密钥由这n 个参与者联合持有. 加密消息直接使用公钥，但解密需要n 个参与者合作才能完成，少于n 个人时得不到明文的任何信息. 下面以ElGamal 公钥系统[28]为例构造门限密码系统如下:联合生成密钥： n 个参与者选取ElGamal 公钥系统的参数 g, p . 每个参与者 Pi 选取各自的私钥ki ，并计算 kihi = g mod p . 所有参与者联合持有私钥1nsk = åi= ki ，联合生成公钥 pk :11niin kiih h mod p g = mod p== = .åÕ加密：对于明文消息 m，参与者 Pi 随机选取一个随机数r ，按照下式计算密文c .c = (u,v) = (mhr mod p, gr mod p).联合解密：参与者计算 ki modwi = v p 并公布.进一步计算可得明文消息m.11mod .niim u w p-== é ù êë úûÕ2.2.3 密文的自盲性密文的自盲性[29](Self-Blinding)也称为密文的重随机化，是指给定明文m 的一个密文，任何人不9 期李顺东等：盲百万富翁问题的高效解决方案 1759需解密就可以把它转换为m 的另一个密文. 值得注意的是，重随机化后的密文 E¢(m) 与调用加密算法所得的密文 E(m)在计算上是不可区分的. 如何对密文进行重随机化与所选择的加密方案有关，下面以ElGamal 公钥系统为例. 对消息m进行重随机化，选择随机正整数r1，计算(u¢,v¢) = (uhr1 , vgr1 ) = (mhr+r1 mod p, gr+r1 mod p).简单来说，在原有密文 E(m)的基础上乘上 E(1)即可实现对原有密文的重随机化，这是因为ElGamal 公钥系统具有乘法同态性，即 E(m) × E(1) = E(m×1) =E¢(m) . 下文所提到重随机化操作均由上述计算过程实现，并以 E¢(m)代表重随机化后的 E(m) .本文所设计的协议需要加密系统同时具有概率加密、门限解密和密文的自盲性这三个性质，为了便于后续对协议的描述和分析，下文将统一以门限解密的ElGamal 公钥系统为例进行描述.3 三方盲百万富翁问题的解决方案3.1 协议的基本原理问题描述 1. 假设Alice、Bob 和Carol 各自拥有一个私有数据 x, y,z . 其中1≤x, y, z≤m . Alice和Bob 为互不信任的合作方. 他们三人希望联合进行保密比较得出 x + y 和 z 之间的大小关系，但又不愿意泄露任何有关自己私有数据的信息.编码方法 1. 由问题描述 1 可知，数据 x, y, z 的取值范围为[1,m]，则2≤x + y≤2m ,即 x, y, z, x + y均在1 到2m之间. 所以，可以使用如下编码方法将x, x + y 转化为一个与其唯一对应的 2m维向量. 以x为例，将其转化为向量 A = (a1,L, a2m )，a1到a2m依次代表1 到2m之间的所有整数，其中，小于x 的数所对应的分量为1，等于x 的数所对应的分量为2，大于x 的数所对应的分量为3，即12 ;3ii xa i xi x, < ; ìï = , = íïî , > .姞柸姞柸姞柸原理描述1. Alice 首先使用编码方法1 构造一个2m维向量 A = (a1,L, a2m )，其中向量的前 x -1个分量为 1，第 x个分量为 2，后2m- x个分量为 3. x编码为1 1 1 22(1, , 1 2 3 , , 3 )x x x mm x- +-=L L14L243 142L43x-1了了A , ,Bob 根据自己的私有数据y 的值将向量A 右移y 位去掉A 的后y 个分量. 然后，在第一个分量前添加y 个为1 的分量，即1 1 1 22(1, , 1 2 3 , , 3 )- + -- -L L14L243 14L243x-1了了, ,x x x m ym x y¯{1 1 1 1 22(1, ,1, 1, , 1 2 3 , , 3 )y y x y x y x y my m x y+ + - + + +- -L L LL 14L243 142L43了x-1了了, ,¯1 1 1 2y-1 2(1, , 1 2 3 , ,3)x y x y x y mx mx y+ - + + ++ - -L L1L4243 142L43了了, ,经过移位添加操作后的向量分量总数仍为 2m个，但为 1 的分量数为 x + y -1个，即求得了 x + y .为了叙述方便，将表示 x + y 的向量记为 C，则1 1 1 2y-1 2(1, , 1 2 3 , , 3 ).x y x y x y mx mx y+ - + + ++ - -=L L1L4243 142L43了了C , ,Carol 根据自己私有数据z 的值，选择向量C 的第 z 个分量. 如果该分量为 1，则表示 x + y > z；如果该分量为 2，则表示 x + y = z；如果该分量为 3，则表示 x + y < z .以上所述即为本文判断 x + y 和 z 大小关系的原理，它还可以用于解决 x + y - z 是否大于 0 的问题，但需要使用加密算法实现协议的保密性. 由于此方法不涉及任何同态性，利用具有自盲性的概率加密算法本身所具有的性质即可保证协议的安全性.为了便于描述，定义判断数据 x + y 和 z 大小关系的二元谓词如下:1( ) 23x y zP x y z x y zx y z, + > ; ìï + , = , + = ; íïî , + < .例 1. 设 x = 2, y = 3, z = 4，选取m = 6 . Alice 按照编码方法1 构造向量A 如下：10= (1, 2,31,34,34,34,32,34,3,43,433,3).了ABob 将向量A 右移3 位去掉A 的后3 个分量后，在第一个分量前添加 3 个为 1 的分量，得到 x + y 的和向量C.= (1{,1,1,1,2,31,34,43,23,43,343,3).4了7了CCarol 选择向量C 的第4 个分量，该分量为1，可得 x + y > z . 事实上， x + y = 5显然大于 z = 4.3.2 协议设计协议 1. 三方盲百万富翁问题的解决方案.输入: Alice、Bob、Carol 分别输入数据 x, y, z .输出: P(x + y, z) .准备: Alice、Bob、Carol 首先选取ElGamal 公钥系统的公开参数g，p，然后分别选择各自的私钥1760 计算 机 学 报 2020年ki ，联合生成公钥:3131.iikiih h mod p g = mod p== =åÕ1. Alice 使用编码方法1 将数据x 转化为向量A = (a1,L, a2m )，加密 A 发送给 Bob，即将E(A) = (E(a1),L, E(a2m )).发送给 Bob.2. 设 y = j，Bob 将 E (A)右移 j位去掉后 j位密文，重随机化后在密文 E¢(a1 )前添加 j个 1 的密文，得到 x + y 的密文. 记 x + y = c ，Bob 将 E (C)发送给 Carol. E (C)每个分量的计算过程如下所示：FOR i=1 TO 2mIF i≤ j( ) (1) i E c ¬ EEISE( ) ( ) i i j E c E a- ¬ ¢END3. 设 z = s，Carol 选择 E(C)的第s个分量，记为 E(q) = (u,v) .4. Alice、Bob、Carol 分别计算 kiwi = v mod p 并公布，然后进一步计算解密得到3 11i mod .iq u w p-== é ù êë úûÕ如果q = 1，则表示 x + y > z；如果q = 2，则表示 x + y = z；如果q = 3，则表示 x + y < z .3.3 方案分析正确性分析 本文协议 1 解决的是判断 x + y 和z 大小关系的问题. 根据编码方法1 可知，求得的x + y 的编码 C 一共有2m个分量，c1到c2m依次代表1 到2m之间的所有整数，小于 x + y 的数所对应的分量为 1，等于 x + y 的数所对应的分量为 2，大于 x + y的数所对应的分量为 3. 1≤z≤m ，C 中第 z 个分量表示 z . 如果该分量为 1，表示 x + y > z；如果该分量为 2，表示 x + y = z ；如果该分量为 3，表示x + y < z . 下面对求解 x + y 的编码 C 的正确性进行详细证明.命题1. 使用移位添加方法能够由x 的编码A得到正确的 x + y 的编码 C.1 1 1 21 2(1, , 1 2 3 , , 3 ),x x x mx mx- +- -=L L14L243 142L43了了A , ,1 1 1 21 2(1, , 1 2 3 , , 3 ).x y x y x y mx y m x y+ - + + ++ - - -=L L1L4243 142L43了了C , ,下面用数学归纳法证明这个命题.证明. (1) 当 y = 1时，x + y = x +1，将 A 右移位1 位去掉A 的最后一个分量后，在第一个分量前添加一个为1 的分量，可得1 1 1 2 1 1 1 1 2 11 2 1 2 1(1, , 1 2 3 , , 3 ) (1, , 1 2 3 , , 3 )x x x m x x x mx mx x m x- + - + -- - - - -= ®L L L L14L243 142L43 14L243 14L243呏穗侩了了了了A , , , ,{ {1 1 2 1 2 2 1 1 2 21 2 1 2 1(1,1, ,1 2 3 , , 3 ) (1, ,1 2 3 , , 3 )x x x m x x x mx m x x m x+ + + +- - - - -® =L L L LL 142L43 L 142L43湗勼了 了 了 了, , , ,1 1 1 1 21 2(1, , 1 2 3 , , 3 ) .y x y x y x y mx y m x y= + - + + ++ - - -Û =L L1L4243 142L43了了, , C(2) 设当 y = k(1≤k≤m-1) 时， x + y = x + k ，将A 右移位k 位去掉A 的后k 个分量后，在第一个分量前添加k 个为 1 的分量，记所求的编码为 Ax+k .1 1 1 2 1 1 1 21 2 1 2(1, , 1 2 3, ,3) (1, , 1 2 3, , 3 )x x x m k x x x m kx mx x m x k- + - + -- - - - -= ®L L L L14L243 142L43 14L243 14L243呏穗侩了了了了A , , , ,{1 1 1 1 1 21 2(1, ,1, 1 , , 1 2 3 , , 3 )k k x k x k x k mx mx k+ + - + + +- - -®L L LL 14L243 142L43湗勼k了了了, ,1 1 1 21 2=(1, , 1 2 3 , , 3 ) .x k x k x k mx kx k m x k+ - + + +++ - - -=L L1L4243 142L43了了, , A则当 y = k +1时， x + y = x + k +1，将 Ax+k 右移去掉 Ax+k的最后一个分量后，在第一个分量前添加添加1 个为1 的分量，可得1 1 1 21 2=(1, , 1 2 3 , , 3 )x k x k x k mx kx k m x k+ - + + +++ - - -L L1L4243 142L43了了A , ,1 1 1 2 11 2 1(1, , 1 2 3 , , 3 )x k x k x k mx k m x k+ - + + -+ - - - -®L L1L4243 14L243呏穗侩了了, ,1 1 2 1 2 21 2 1(1,1, , 1 2 3 , , 3 )x k x k x k mx k m x k+ + + + ++ - - - -®L L14L243 142L43湗勼了了, ,1 1 2 22 1(1, , 1 2 3 , , 3 )x k x k x k mx k m x k+ + + + ++ - - -=L L14L243 142L43了了, ,1 1 1 1 21 2(1, , 1 2 3 , , 3 ) .y k x y x y x y mx y m x y= + + - + + ++ - - -Û =L L1L4243 142L43了了, , C综上所述，使用移位添加方法可以由x 的编码A正确求解 x + y 的编码 C.证毕.安全性分析 协议1 的安全性是基于门限解密的ElGamal 公钥系统安全性的.在计算过程中，Alice、Bob 和Carol 三个人收或发的消息都是密文.Alice 仅发送编码的密文消息，Bob 和Carol 两人无法通过所收到的密文获知任何的额外信息，原因有以下两点: 首先，协议1 是门限解密的，每个人都只拥有私钥的一部分，只要有一个人不参与解密，就无法获知有关密文的任何信息. 其次，ElGamal9 期李顺东等：盲百万富翁问题的高效解决方案 1761公钥系统是语义安全的，随机数和密文是计算不可区分的. 在解密过程中，Alice、Bob 和Carol 分别计算并公布了 ki modwi = v p . 私钥ki 的安全性基于离散对数假设，不存在多项式时间算法A 在接受输入(wi ,v, p)后可以输出ki . 因此，在协议的整个执行过程中，Alice、Bob 和Carol 的数据x、y、z 都是完全保密的. 协议1 是使用(3,3) 门限密码系统实现的，可以抵抗任意2 个参与者的合谋攻击. 下面我们使用模拟范例对协议进行详细证明.定理1. 协议1 在半诚实模型下是安全的，且可以抵抗任意数量的合谋攻击.证明. (1) 在Alice 不参与合谋的情况下I = {Bob,Carol}, X = {x, y, z},f (X ) = fI (X ) = P(x + y, z),({0 1} )2 32 3{ ( )}( () ()){ , , , ( ), , , ( ), ( )}.I X nIview XI view X view XI y r E z r E f X*PÎ ,= , P , P= A C给定输入 (I, ( y, z), fI (X )) , S 随机选择 1≤x¢≤m使得( ) ( ) ( )( ) ( ) ( )IIf X f x yz Px yzf X f xyz Px yz¢ = ¢, , = ¢ + ,= = , , = + , ,用 x¢、y、z 进行模拟，模拟器S 工作过程如下：首先，S 按照协议要求构造向量 A¢ ,{1 1 1 21 2(1, ,1 2 3, ,3 ).x x x mx m x¢- ¢ ¢+¢- - ¢¢ =L LL 14L243了了A , ,加密 A¢得到E(A¢) = (E(a1¢),L, E(a2¢m )).然后， S 根据y 的值按照协议要求进行保密移位添加和重随机化操作，得到E(C¢) = (E(c1¢),L, E(c2¢m )).最后， S 根据 z 的值选取 E(C¢) 中对应分量E(q¢)，解密 E(q¢)得到fI (X ¢) = fI (x¢, y, z) = P(x¢ + y, z).令2 3( ( ) ( )){ ( ) ( ) ( )}IIS I y z f XI y r E z r E f X, , ,= , , , A¢ , , , C¢ , ¢ .因为ElGamal 公钥系统是语义安全的概率加密方案，所以 E(A)与 E(A¢)、E(C)与 E(C¢)在计算上是不可区分的. 又因为 fI (X ) = fI (X ¢)，以及其他所有参数都是相等的，所以({0 1} ) ({0 1} ) { ( ( ) ( ))} n { ( )} ncI X I X S I y z f X * view X *PÎ , Î , , , , º ,因此，协议1 对于x 是安全的.(2) 由于Alice 和Bob(或Carol)合谋的证明可以由(1)中的证明类似模拟得到，所以下面我们仅给出证明的思路. 由于ElGamal 公钥系统是语义安全的，所以参与者在协议过程中所得的2m 个密文与2m 个随机数是计算不可区分的. 所获得的view 与用满足谓词P(x+y,z)的任意一组输入进行模拟所得到的信息序列也是计算不可区分的. 所以很容易得出结论: 在Bob 或Carol 不参与合谋的情况下，协议1 也是安全的，即协议对Bob(或Carol)的数据y(或z)也是安全的.综上所述，协议1 对于半诚实参与者是安全的，且可以抵抗任意数量的合谋攻击.证毕.4 四方盲百万富翁问题的解决方案4.1 协议的基本原理问题描述 2. 假设有四个参与者Alice、Bob、Carol、Dove，他们各拥有一个私有数据 x、y、u、 v .其中1≤x, y,u,v≤m . Alice 和 Bob、Carol 和 Dove分别为两组互不信任的合作方. 他们四人希望联合进行保密比较得出x+y 和u+v 之间的大小关系，但又不愿意泄露任何有关自己私有数据的信息.编码方法2. 由问题描述2可知，数据 x, y,u,v的取值范围为 [1,m] ，则 2≤x + y≤2m , 2 -m≤x +y - u≤2m-1，即 x, x + y, x + y - u在-m到2m之间.所以，可将 x, x + y, x + y - u 转化为一个与其唯一对应的3m+1维向量，向量的第 1 维到第3m+1维依次代表 -m 到 2m 之间的所有整数. 其中，小于x, x + y, x + y - u的数所对应的分量为 1，等于 x, x +y, x + y - u的数所对应的分量为 2，大于 x, x + y, x +y - u 的数所对应的分量为 3.又由于1≤v≤m，在下文原理描述 2 中 Dove根据v进行分量选择时，不会使用到-m到-1之间的数所对应的分量，所以可将向量维数减至2m+1维. 以 x为例，将其转化为向量 A = (a1,L,a2m+1 )，a1到a2m+1依次代表 0 到2m之间的所有整数，其中，小于x 的数所对应的分量为1，等于x 的数所对应的分量为2，大于x 的数所对应的分量为3，即1 12 13 1ii xa i xi x, < + ; ìï = , = + ; íïî , > + .姞柸姞柸姞柸原理描述 2. 因为 x + y > u + v Û x + y - u > v，所以可以将判断 x + y 和u + v 大小关系的问题转化为判断 x + y - u 和 v大小关系的问题. 具体的求解原理如下所述：1762 计算 机 学 报 2020年Alice首先使用编码方法 2构造一个2m+1维向量 A = (a1,L, a2m+1)，其中向量的前 x个分量为 1，第 x +1个分量为 2，后2m- x个分量为 3. x编码为0 1 1 22(1, , 1 2 3 , , 3 )x x x mx mx- +-=L L14L243 142L43了了A , ,Bob 根据自己私有数据y 的值将向量A右移y位去掉A 的后y 个分量. 然后，在第一个分量前添加y 个为1 的分量，即0 1 1 22(1, , 1 2 3 , , 3 )x x x m yx mx y- + -- -L L14L243 14L243了了, ,¯0 1 1 1 22(1, ,1,1, , 1 2 3 , ,3)y y x y x y x y my x m x y- + - + + +- -L L L14L243 14L243 142L43了了了, ,¯0 1 1 2+y 2(1, , 1 2 3 , , 3 )x y x y x y mx mx y+ - + + +- -L L1L4243 142L43了了, ,经 过 移 位 添 加 操 作 后 的 向 量 分 量 总 数 仍 为2m+1个，但为1的分量数为 x + y 个，即求得了 x + y .为了叙述方便，将表示 x + y 的向量记为C ，则0 1 1 2+y 2(1, , 1 2 3 , , 3 ).x y x y x y mx mx y+ - + + +- -=L L1L4243 142L43了了C , ,Carol 根据自己私有数据u 的值将向量C 左移u 位去掉C 的前u 个分量. 然后，在最后一个分量后添加u 个为3 的分量，即1 1 22(1, , 1 2 3 , , 3 )u x y x y x y mx y u m x y+ - + + ++ - - -L L1L4243 142L43了了, ,¯0 1 1 2 2 1 22(1, , 1 2 3 , , 3 , 3 , , 3 )x y u x y u x y u m u m u mx y u m x y u+ - - + - + - + - - ++ - - -L L L1L4243 1442L443 142L43了了了, ,¯0 1 1 22(1, , 1 2 3 , , 3 )x y u x y u x y u mx y u m x y u+ - - + - + - ++ - - - +L L1L4243 1442L443了了, ,经 过 移 位 添 加 操 作 后 的 向 量 分 量 总 数 仍 为2m+1个，但为 1 的分量数为 x + y - u 个，即求得了x + y - u .为了叙述方便，将表示 x + y - u 的向量记为D ，则0 1 1 22(1, , 1 2 3 , , 3 ).x y u x y u x y u mx y u m x y u+ - - + - + - ++ - - - +=L L1L4243 1442L443了了D , ,Dove 根据自己私有数据v 的值，选择向量D 的第 v +1个分量. 如果所选分量为 1，表示 x + y -u > v ，即 x + y > u + v ；如果所选分量为 2，表示x + y - u = v ，即 x + y = u + v；如果所选分量为 3，表示 x + y - u < v ，即 x + y < u + v .以上所述即为本文判断 x + y 和u + v 大小关系的原理，其还可以用于判定 x - u与v - y之间的大小关系，以及其它类似的四方数据做加减运算的比较问题，但需要使用加密系统实现协议的保密.由于此方法不涉及任何同态性，利用具有自盲性的概率加密算法本身所具有的性质即可保证协议的安全性.为了便于描述，定义判断数据 x + y 和u + v 大小关系的二元谓词如下：1( ) 23x y u vP x y u v x y u vx y u v, + > + ; ìï + , + = , + = + ; íïî , + < + .例 2. 设 x = 2, y = 3,u = 5,v = 1，选取m = 6 . Alice按照编码方法2 构造向量A 如下：{2 10= (1,1,2,31,34,34,34,32,34,3,43,433,3).了了ABob 将向量A 右移3 位去掉A 的后3 个分量后，在第一个分量前添加 3 个为 1 的分量，得到 x + y 的和向量C :5 7= (114,1,21,413,1,2,31,34,43,23,43,343,3).了了CCarol 将向量C 左移5 位去掉C 的前5 个分量后，在最后一个分量后添加5 个为3 的分量，得到x + y - u 的和向量 D :12= (2,31,34,34,3,434,32,34,3,43,43,343,3).了DDove 选择向量D 的第2 个分量，该分量为3，可得 x + y < u + v . 事实上， x + y = 5 显然小于 u +v = 6 .4.2 协议设计协议 2. 四方盲百万富翁问题的解决方案.输入: Alice、Bob、Carol、Dove 分别输入数据x, y, u,v .输出: P(x + y,u + v) .准备: Alice 、Bob 、Carol 、Dove 首先选取ElGamal 公钥系统的公开参数g，p，然后分别选择各自的私钥ki ，联合生成公钥：4141.iikiih h mod p g = mod p== =åÕ1. Alice 使用编码方法2 将数据x 转化为向量A = (a1,L, a2m+1)，加密 A发送给 Bob，即将1 2 1 ( ) ( ( ) ( )) m E E a E a+ A = ,L, .发送给 Bob.2. 设 y = j，Bob 将 E (A)右移 j 位去掉后 j 个密文，重随机化后在密文 E¢(a1 )前添加 j 个 1 的密9 期李顺东等：盲百万富翁问题的高效解决方案 1763文，得到 x + y 的密文. 记 x + y = c ，Bob 将 E (C)发送给 Carol. E (C)每个分量的计算过程如下所示：FOR i=1 TO 2m+1IF i≤ jE(ci )¬ E(1)EISEE(ci ) E (ai- j ) ¬ ¢END3. 设u = t ，Carol 将 E (C)左移t 位去掉前t 个密文，重随机化后在密文 E (c2m+1) ¢ 后添加t 个3 的密文，得到 x + y - u 的密文.记 x + y - u = d ，Bob 将E (D)发送给 Dove. E (D) 每个分量的计算过程如下所示：FOR i=1 TO 2m+1IF i≤2m- t +1E(di ) E (ct+i ) ¬ ¢EISEE(di )¬ E(3)END4. 设v = q，Dove 选择 E(D)的第q +1个分量，记为 E(s) = (u, v) .5. Alice、Bob、Carol、Dove 分别计算 kiwi = vmod p 并公布，然后进一步计算解密得到4 11i mod .is u w p-== é ù êë úûÕ如果s = 1，表示 x + y > u + v；如果s = 2，表示x + y = u + v；如果s = 3，表示 x + y < u + v.4.3 方案分析正确性分析 本文协议 2 解决的是判断 x + y 和u + v 大小关系的问题. 由原理描述 2 可知，本文将其转化为判断 x + y - u 和 v大小关系的问题进行解决.使用移位添加方法由 x的编码 A求解 x + y - u 的编码D 的正确性证明与3.3 节正确性分析中所给出的证明类似，这里不再详细描述. 根据编码方法2可知，求得的 x + y - u 的编码 D 一共有 2m+1个分量，d1到d2m+1依次代表 0 到2m之间的所有整数，小于 x + y - u 的数所对应的分量为 1，等于 x + y - u的数所对应的分量为 2，大于 x + y - u的数所对应的分量为 3. 1≤v≤m，D中第v +1个分量代表v . 如果该分量为 1，表示 x + y > u + v；如果该分量为 2，表示 x + y = u + v ；如果该分量为 3，表示 x + y <u + v .安全性分析协议 2 的安全性是基于门限解密的ElGamal 公钥系统的安全性的. 在计算过程中，Alice、Bob、Carol 和Dove 四个人收或发的消息都处在密文状态下. Alice 仅发送编码的密文消息，Bob、Carol 和Dove 三人无法通过所收到的密文获知任何的额外信息，原因与前面对协议1 的分析相同. 协议2 是使用(4,4) 门限密码系统实现的，可以抵抗任意3 个参与者的合谋攻击. 因为与协议1 的证明过程类似，所以下面不再详细加以证明,只给出证明的思路.定理2. 协议2 在半诚实模型下是安全的，且可以抵抗任意数量的合谋攻击.由于 ElGamal 公钥系统是语义安全的，所以参与者在协议过程中所得的 2m+1个密文与 2m+1个随机数是计算不可区分的. 进而其所获得的view 与用满足谓词 P(x + y,u + v)的任意一组输入进行模拟所得到的信息序列也是计算不可区分的. 所以，可以很容易的得出结论: 协议2 对Alice、Bob、Carol和Dove 的数据x、y、u、v 是安全的.5 N 盲百万富翁问题的解决方案5.1 协议的基本原理问题描述 3. 假设有n个参与者 P1,L, Pn，他们每个人拥有两个保密数据 xi、yi，其中 xi , yi Î{0,1} .他们希望合作判定1nåi= xi , 1nåi= yi 之间的大小关系，且不泄露任何其它信息.编码方法 3. 由问题描述 3 可知，数据 xi , yi的取值为 0 或 1，则 j 1 j 1 ( 1, ,- j≤åi= xi -åi= yi ≤ j j = Ln -1)，即 j 1( )( 1, , 1)åi= xi - yi j = L n - 均在 -n 到 n 之间. 进而，可以使用如下编码方法将 j 1( )åi= xi - yi 转化为一个与其唯一对应的2n +1维向量. 以 x1 - y1为例，将其转化为向量 A = (a1,L, a2n+1)，a1到a2n+1依次代表-n到n之间的所有整数. 其中，小于 x1 - y1的数所对应的分量为 1，等于 x1 - y1的数所对应的分量为 2，大于 x1 - y1的数所对应的分量为 3，即1 11 11 11 12 13 1ii n x ya i n x yi n x y, < + - + ; ìï = , = + - + ; íïî , > + - + .姞柸姞柸姞柸原理描述3. 因为11 1 1 ( n n ni xi i yi i xi -å = > å = Û å = -yi ) > yn - xn，所以可以将判断 1nåi= xi 和 1nåi= yi 大小关系的问题转化为判断11 ( ) ni xi yi -å = - 与 yn - xn 大小关系的问题. 具体的求解原理如下所述:P1首先使用编码方法 3 构造一个2n +1维向量A = (a1,L, a2n+1)，其中向量的前n + x1 - y1个分量为1，第n + x1 - y1 +1个分量为 2，后n - x1 + y1个分量为 3. x1 - y1编码为1764 计算 机 学 报 2020年1 1 1 1 1 11 1 1 11 11 ( 1 , , 1 2 3 , ,3)n x y x y x y nn x y n x y- - - - - ++ - - +=L L14L243 142L43了了A , ,若要比较 x1 + x2 + x3 和 y1 + y2 + y3 之间的大小关系，首先，P2根据 x2 - y2的值对 A1进行相应的左移 (x2 - y2 < 0)或右移 (x2 - y2 > 0) 操作得到 x1 + x2-( y1 + y2 )的密文向量 A2 (注: 当 x2 - y2 = 0时，不进行操作).不失一般性地假设x2 - y2 > 0，具体的操作如下：P2根据 x2 - y2的值将向量 A1右移 x2 - y2位去掉 A1的后 x2 - y2个分量，然后，在第一个分量前添加 x2 - y2个为 1 的分量，即1 1 1 1 1 1 2 21 1 1 1 2 21 1( 1 , , 1 2 3 , , 3 )n x y x y x y n x yn x y n x y x y- - - - - + - ++ - - + +L L14L243 144L2443了- 了, ,¯2 2 1 1 2 2 1 1 2 22 2 1 1 1 1 2 21 1 1(1, , 1 ,1, , 1 2 3 , ,3)n n x y x y x y x y x y nx y 个 n x y 个 n x y -x +y 个, ,- - + - - - + - - - + - +- + - - +L L L14L42443 1L442443 144244L3¯1 1 2 2 1 1 2 2 1 1 2 21 2 1 2 1 2 1 21 1( 1 , , 1 2 3 , ,3)n x y x y x y x y x y x y nn x x y y n x x y y- - + - - - + - - + - ++ + - - - - + +L L14L4424443 144244L3了了, ,经过移位添加操作后的向量分量总数仍为2n +1个，但为 1 的分量数为n + (x1 + x2 - ( y1 + y2 ))个，即求得了 x1 + x2 - ( y1 + y2 ) . 为了叙述方便，将表示 x1 + x2 - ( y1 + y2 ) 的向量记为 A2 .P3根据 y3 - x3的值选择向量 A2的对应分量即可 得 出 x1 + x2 + x3 和 y1 + y2 + y3 之 间 的 大 小 关系. y3 - x3 Î{-1,0,1}，A2中第n +1+ y3 - x3个分量代表 y3 - x3 . 如果该分量为 1，可得 x1 + x2 - ( y1 +y2 ) > y3 - x3，即 x1 + x2 + x3 > y1 + y2 + y3；如果该分量为 2，可得 x1 + x2 - ( y1 + y2 ) = y3 - x3 ，即 x1 +x2 + x3 = y1 + y2 + y3；如果该分量为 3，可得 x1 + x2-( y1 + y2 ) < y3 - x3，即 x1 + x2 + x3 < y1 + y2 + y3 .依次类推，想要比较 x1 +L+ xi 和 y1 +L+ yi 之间的大小关系，只需要参与者 Pj ( jÎ{2,L,i -1})按照要求进行相应的移位添加操作后，将 Aj 发送给Pj+1 . 最后，由 Pi 根据 yi - xi的值选择向量 Ai-1的对应分量即可得出1iå j= x j 和 1iå j= y j 之间的大小关系.以上所述即为本文判断1nåi= xi 和 1nåi= yi 大小关系的原理，但还需要使用加密算法实现协议的保密性. 由于此方法不涉及任何同态性，利用具有自盲性的概率加密算法本身所具有的性质即可保证协议的安全性.为了便于描述，令 n 1 , n 1U = åi= xi V = åi= yi . 定义判断数据U 和V 大小关系的二元谓词如下：1( ) 23U VP U V U VU V, > ; ìï , = , = ; íïî , < .例 3. 选 取 n = 4 ,设 x1 = 1, y1 = 1, x2 = 1, y2 = 0,x3 = 0, y3 = 1, x4 = 0, y4 = 0 . P1按照编码方法 3 构造向量 A1如下:1 = (1{,1,1,1,2,31,32,33,3).4了4了Ax2 - y2 = 1 > 0，P2先将向量 A1右移 1 位去掉 A1的最后一个分量. 然后，在第一个分量前添加1 个为 1 的分量，得到 x1 + x1 - ( y1 + y2 )的和向量 A2 :2 = (114,1,21,413,1,2,3{,3,3).5了 3了Ax3 - y3 = -1 < 0， P3先将向量 A2左移 1 位去掉A2的第一个分量. 然后，在最后一个分量后添加 1个为 3 的分量，得到 x1 + x2 + x3 - ( y1 + y2 + y3 )的和向量 A3 :3 = (1{,1,1,1,2,31,32,33,3).4了4了Ax4 - y4 = 0，则 P4选择向量 A3的第 5 个分量，该分量为2，可得4 4åi=1 xi = åi=1 yi . 事实上， 4åi=1 xi =4åi=1 yi = 2 .5.2 协议设计协议 3. N 方盲百万富翁问题的解决方案.输入: n个参与者 Pi 分别输入各自的保密数据xi , yi .输出: P(U,V) .准备: P1,L, Pn首先选取 ElGamal 公钥系统的公开参数 g，p，每个参与者 Pi 选择各自的私钥ki ，联合生成公钥:11.niin kiih h mod p g = mod p== =åÕ1. P1使用编码方法 3 将数据 x1 - y1转化为向量A1 = (a11,L,a1(2n+1) )，加密 A1发送给 P2，即将( ) 1 11 1 2 1 ( ) ( ( ) ( )) n E E a E a+ A = ,L, .发送给 P2 .2. 对于每个 jÎ[2,n -1]，参与者 Pj操作如下：设 x j - y j = k(k > 0)，则 Pj将 E(Aj-1)右移 k 位去掉后k 个密文，重随机化后在密文 E (a( j-1)1) ¢ 前添加k 个1 的密文，得到表示( ) 1jåi= xi - yi 的密文向量Aj ， Pj将 E(Aj ) 发送给 Pj+1 . E(Aj ) 每个分量的计算过程如下所示:FOR i=1 TO 2n+1IF i≤kE(a ji )¬ E(1)9 期李顺东等：盲百万富翁问题的高效解决方案 1765EISEE(a ji ) E (a( j-1)(i-k ) ) ¬ ¢END3. Pn选择 E(An ) 的第n +1+ yn - xn 个分量，记为 E(q) = (u, v) .4. n个参与者 P1,L, Pn分别计算 kiwi = v mod p并公布，然后进一步计算得到得到11mod .niiq u w p-== é ù êë úûÕ如果q = 1，则表示U > V ，即 1 1n nåi= xi > åi= yi ；如果 q = 2 ，则表示U = V ，即 1 1n nåi= xi = åi= yi ；如果q = 3，则表示U < V ，即 1 1n nåi= xi < åi= yi .5.3 方案分析正确性分析 本文协议3 解决的是判断1nåi= xi和1nåi= yi 大小关系的问题.由原理描述 3 可知，本文将该问题转化为判断11 ( ) ni xi yi -å = - 与 yn - xn 大小关系的问题进行解决. 使用移位添加方法由 x1 - y1的编码 A1求解 11 ( ) ni xi yi -å = - 编码 An-1的正确性证明与3.3 节正确性分析中所给出的证明类似，这里不再详细描述. 根据编码方法3 可知，求得的11 ( ni xi -å = --yi ) 的编码 An-1 一共有 2n +1 个分量, a(n-1)1 到a(n-1)(2n+1)依次代表 -n 到 n 之间的所有整数，小于11 ( ) ni xi yi -å = - 的数所对应的分量为 1,等于 11 ( ni xi -å = -yi )的数所对应的分量为 2，大于 11 ( ) ni xi yi -å = - 的数所对应的分量为 3. yn - xn Î{-1,0,1}，An-1中第n +1+ yn - xn个分量代表 yn - xn . 若该分量为 1，表示1 1n nåi= xi > åi= yi ；若该分量为 2，表示 1nåi= xi =1nåi= yi ；若该分量为 3，表示 1 1n nåi= xi < åi= yi .安全性分析 协议3 的安全性是基于门限解密的ElGamal 公钥系统的安全性的. 在计算过程中, P1,L, Pn收或发的消息都处在密文状态下. P1仅发送编码的密文消息， P2 ,L, Pn无法通过所收到的密文获知任何的额外信息，原因与协议1 的原因相同. 协议 3 是使用(n, n)门限密码系统实现的，可以抵抗任意n -1个参与者的合谋攻击. 因为证明过程与协议1 类似，所以这里不再详细加以证明，只给出定理的描述.定理3. 协议3 在半诚实模型下是安全的，且可以抵抗任意数量的合谋攻击.6 效率分析与比较文献[24]中的子协议SLT 协议解决的是密文比较大小问题，又由于其使用的是Paillier 公钥系统，可以使用加法同态性解决求和问题，是我们已知最接近本文所研究的盲百万富翁问题的文献，故本文将其作为重要的参考与所设计的协议进行比较分析.本节中我们首先对协议1、协议2 和协议3 的效率进行详细分析，然后将本文的协议3 与使用文献[24]的SLT 协议所实现的解决方案进行全面比较.6.1 协议效率分析在对一个方案进行效率分析时，一般从计算复杂性和通信复杂性两个角度出发.在衡量计算复杂性时，因为模指数运算的复杂性比其他运算的复杂性高很多（例如: 用比特复杂性来衡量，模指数运算的计算复杂性为O(lg3 n)，运用欧几里得扩展算法求逆的计算复杂性为O(lg2 n)），所以我们通常忽略协议执行中所需的其他计算开销，只考虑计算代价最高的模指数运算次数.计算复杂性 协议1 所涉及的数据范围在1 到2m之间. 三个参与者合作产生公钥共需要3 次模指数运算. 加密过程中三个参与者最多需要8m 次模指数运算，解密过程需要3 次模指数运算. 所以，协议 1 最多需要8m+ 6次模指数运算.协议2 所涉及的数据范围在0 到2m之间. 四个参与者合作产生公钥共需要4 次模指数运算. 加密过程中四个参与者最多需要12m+ 6次模指数运算，解密过程需要4 次模指数运算. 所以，协议2 最多需要12m+14次模指数运算.协议 3 所涉及的数据范围在-n到n之间. n个参与者合作产生公钥共需要n 次模指数运算. 加密过程中n个参与者最多需要4n2 - 2n - 2次模指数运算，解密过程需要2n 次模指数运算. 所以，协议3最多需要4n2 + n - 2次模指数运算.研究人员通常使用通信次数或交换信息的比特数衡量通信复杂性，但随着计算机技术的不断发展，一次交换信息的比特数不再是限制通信的重要指标.因此，现在通常使用通信次数来衡量通信复杂性.通信复杂性 在协议1 中，三个参与者共同构造公钥、加密过程和解密过程各需要3 次通信，所以共需要9 次通信；在协议2 中,四个参与者共同构造公钥、加密过程和解密过程各需要4 次通信，所以共需要12 次通信；在协议3 中，n 个参与者共同构造公钥、加密过程和解密过程各需要n 次通信，所以共需要3n 次通信.与文献[24]的比较 文献[24]中的SLT 协议可以解决两个密文比较大小的问题，但难于构造抵抗合谋攻击的协议，而本文的协议3 能够抵抗合谋攻击.由于不同安全级别的协议不具备可比性，所以本文1766 计算 机 学 报 2020年的协议 3 也不考虑合谋攻击. 当不考虑合谋攻击时，协议3 只需要加密系统具有概率加密和密文的自盲性这两个性质，使用Goldwasser-Micali(GM)公钥系统即可实现协议3. 为了便于描述，我们将使用文献[24]的SLT 协议所实现的盲百万富翁问题的解决方案命名为ESLT 协议(Extended Secure Less thanProtocol).设定两个协议中参与者人数为n. 使用GM 公钥系统实现协议3 时，需要对编码方法3 进行微小的调整. 具体地，以 x1 - y1为例，将其转化为向量A = (a1,L, a2n+1)，其中1 11 10 1i 1 1i n x yai n x yì , + - + ;= íî , > + - + .姞柸≤姞柸在ESLT 协议中，参与者首先利用Paillier 公钥系统的加法同态性求得 ( n 1 )E åi= xi 和 ( 1 ) nE åi= yi ，然后调用SLT 协议比较 ( n 1 )E åi= xi 和 ( 1 ) nE åi= yi 的大小得出1nåi= xi 和 1nåi= yi 的大小关系.因为GM 公钥系统加解密进行模乘运算，Paillier 公钥系统加解密进行模指数运算. 模乘运算的复杂性远远低于模指数运算的复杂性，当有模指数运算时，模乘运算的复杂性可以忽略不计. 所以，本文所设计的协议3 比ESLT 协议的计算复杂性低.通信复杂性方面，本文的协议3 与ESLT 协议所需的通信次数都为n 次.综上所述，与ESLT 协议相比本文所设计的协议3 效率更高. 具体的计算复杂性和通信复杂性的比较如表1 所示.表1 计算复杂性和通信复杂性的比较模指数运算 模乘运算 通信次数协议 3 - 4n2 - 2n - 2 + log p nESLT 协议 2n +1 n -1 n6.2 实验数据分析为了更直观、清晰地展现本文所设计方案的效率以及与文献[24]的比较情况，本文使用Java 语言编程进行了两个模拟实验.实验测试环境 Windows 10 家庭版，64 位操作系统，Intel(R)Core(TM)i5-6600 处理器 CPU @ 3.31GHz，8.00GB 内存，用Java 语言在MyEclipse 上运行实现. 本文所做模拟实验均在此环境下进行.实验1 测试本文所设计协议的实际可行性，实验中每个参与者所持有的数据为100 到1000 以内的整数，设定协议 3 中的参与者人数n = 25 . 忽略预处理时间，使用门限解密的ElGamal 公钥系统进行模拟.实验2 比较在参与者不合谋情况下协议3 与ESLT 协议的效率，设定参与者人数为 nÎ{3, 4,L,15} . 为使实验数据更准确，对n 的每个参数进行1000 次模拟测试，计算协议执行时间的算术平均值.忽略预处理时间，协议3 使用GM 公钥系统进行模拟，ESLT 协议使用Paillier 公钥系统进行模拟.实验结果 实验1 结果如图1 所示. 由图1 可知，协议的执行时间随数据范围增长基本上呈线性增加. 值得注意的是，在此次实验中，三个协议使用的都是门限解密的ElGamal 公钥系统，如果选用效率更高的门限解密系统，协议的效率会更高.实验2 结果如图2 所示. 由图2 可得，协议3比ESLT 协议的效率高.坚1 厫谊1、2、3 拃袨晒限雫旌揊荟坐壺闛盠吴卲訠忧坚2 厫谊3 哨ESLT 厫谊拃袨晒限雫吞乪聡伖旌壺闛盠吴卲訠忧7 结 论本文首先对百万富翁问题进行了拓展，提出了新的安全多方计算问题: 盲百万富翁问题. 为了解决该问题，我们利用概率加密方案的性质和移位寄存器的思想设计了新的保密移位添加方法. 然后，结合适当的编码方法构造了三个不同的盲百万富翁问题的解决方案. 三个协议在半诚实模型下都是安9 期李顺东等：盲百万富翁问题的高效解决方案 1767全的，可以抵抗任意数量的合谋攻击. 今后我们将在本文研究的基础上考虑更高效、更普遍的解决方案，并尝试设计恶意模型下盲百万富翁问题的解决方案.参 考 文 献[1] Yao A C. Protocols for secure computations//Proceedings of the23th IEEE Annual Symposium on Foundations of ComputerScience. Chicago, USA, 1982: 160-164[2] Orlandi C. Is multiparty computation any good in practice?//Proceedings of the IEEE International Conference on Acoustics,Speech, and Signal Processing. Prague, Czech Republic, 2011:5848-5851[3] Goldreich O, Micali S, Wigderson A. How to play any mentalgame//Proceedings of the Nineteenth Annual ACM Conferenceon Theory of Computing. New York, USA, 1987: 218-229[4] Goldreich O. The fundamental of cryptography: basicapplications. London, UK: Cambridge University Press, 2004[5] Fagin R, Naor M, Winklery P. Comparing informationwithout leaking it. Communications of the ACM, 1996, 39(5):77-85[6] Freedman M J, Nissim K, Pinkas B. Efficient private matchingand set intersection//Proceedings of the Annual InternationalConference on the Theory and Applications of CryptographicTechniques. Interlaken, Switzerland, 2004: 1-19[7] Kissner L, Song D. Privacy-preserving set operations//Proceedings of the 25th Annual International CryptologyConference. California, USA, 2005: 241-257[8] Beimel A, Gabizon A, Ishai Y, et al. Non-interactive securemultiparty computation//Proceedings of the 34th Annual CryptologyConference. California, USA, 2014: 387-404[9] Dou J W, Gong L M, Li S D, et al. Efficient private subsetcomputation. Security and Communication Networks, 2016,9(18): 5965-5976[10] Samanthula B K, Jiang W. Secure multiset intersectioncardinality and its application to Jaccard coefficient. IEEETransactions on Dependable and Secure Computing, 2016, 13(5):591-604[11] Yang X Y, Li S D, Kang J. Private substitution and itsapplications in private scientific computation. Chinese Journal ofComputers, 2018, 425(5): 166-176 (in Chinese)(杨晓艺, 李顺东, 亢佳. 保密替换及其在保密科学计算中的应用. 计算机学报, 2018, 425(5): 166-176)[12] Qin J, Zhang Z F, Feng D G, et al. A protocol of comparinginformation without leaking. Journal of Software, 2004, 15(3):421-427(in Chinese)(秦静, 张振峰, 冯登国, 等. 无信息泄漏的比较协议. 软件学报, 2004, 15(3): 421-427)[13] Luo Y, Huang L, Yang W, et al. An efficient protocol for privatecomparison problem. Chinese Journal of Electronics, 2009,18(2): 205- 209[14] Zhong H, Tian L, Shi R．An efficient and fair private comparisonprotocol based on range encoding．Journal of ComputationalInformation Systems, 2013, 9(1): 231-240[15] Lin H Y, Tzeng W G. An efficient solution to the millionaires'problem based on homomorphic encryption//Proceedings of thethird International Conference. New York, USA, 2005: 456–466[16] Li S D, Wang D S. Efficient secure multiparty computation basedon homomorphic encryption. Chinese Journal of Electronics,2013, 41 (4): 798-803(in Chinese)(李顺东, 王道顺. 基于同态加密的高效多方保密计算. 电子学报, 2013, 41(4): 798-803)[17] Liu M, Nanda P, Zhang X, et al. Asymmetric commutative encryptionscheme based efficient solution to the millionaires'problem//Proceedings of the 17th IEEE International ConferenceOn Trust, Security And Privacy In Computing AndCommunications. New York, USA, 2018: 990-995[18] Li S D, Guo Y M, Zhou S F, et al. Efficient protocols for thegeneral millionaires' problem. Chinese Journal of Electronics,2017, 26(4): 696-702[19] Bessonov M, Grigoriev D, Shpilrain V. Probabilistic solution ofYao's millionaires' problem. IACR Cryptology ePrint Archive,2017, 2017: 1129[20] Hibiki O, Yoshifumi M. Efficient card-based cryptographicprotocols for the millionaires' problem using private inputoperations//Proceedings of the 13th Asia Joint Conference onInformation Security. Guilin, China, 2018: 23-28[21] Atallah M J, Du W. Secure multi-party computationalgeometry//Proceedings of the 7th International Workshop.Providence, USA, 2001: 165-179[22] Liu W, Luo S S, Wang Y B, et al. A protocol of securemulti-party multi-data ranking and its application in privacypreserving sequential pattern mining//Proceedings of the FourthInternational Joint Conference on Computational Sciences andOptimization. Yunnan, China, 2011: 272-275[23] Li S D, Kang J, Yang X Y, et al. Secure multiparty characterssorting. Chinese Journal of Computers, 2018(5): 1173-1188(inChinese)(李顺东, 亢佳, 杨晓艺, 等. 多个字符排序的安全多方计算.计算机学报, 2018(5): 1173-1188)[24] Liu X, Choo R, Deng R, et al. Efficient and privacy-preservingoutsourced calculation of rational numbers. IEEE Transactionson Dependable and Secure Computing, 2018, 15(1): 27-39[25] Goldwasser S, Micali S. Probabilistic encryption. Journal ofComputer and System Sciences, 1984, 28(2): 270-299[26] Desmedt Y, Frankel Y. Threshold cryptosystems//Proceedings ofthe 9th Annual International Cryptology Conference. California,USA, 1989: 307-315[27] Long Y, Chen K, Mao X. New constructions of dynamicthreshold cryptosystem. Journal of Shanghai Jiaotong University(Science), 2014, 19(4): 431-435[28] Gamal T E. A public key cryptosystem and a signature schemebased on discrete logarithms. IEEE Transactions on InformationTheory, 1985, 31(4): 469-472[29] Paillier P. Public-key cryptosystems based on compositedegree residuosity classes//Proceedings of the AnnualInternational Conference on the Theory and Applications ofCryptographic Techniques. Prague, Czech Republic, 1999:223-2381768 计算 机 学 报 2020年LI Shun-Dong, Ph.D., professor, Ph.D.supervisor. His main research interestsinclude modern cryptography and informationsecurity.ZHANG Meng-Yu, M.S. candidate. Her main researchinterests include modern cryptography and informationsecurity.BackgroundDiffie and Hellman's paper, New Directions inCryptography, opens up the study of public key cryptography.Since then, researchers have proposed many researchdirections based on public key cryptography. Among them,SMC is a key area of public key cryptography, and its goal isto enable participants to perform joint computing whileensuring that participants input privately.The millionaires' problem is the first problem in securemultiparty computation and a fundamental problem insecure scientific computing. It studies how two parties,Alice and Bob with private numbers x and y, respectively todetermine which one is bigger without disclosing any otherinformation. The researchers propose many effectivesolutions and generalize a series of new secure multipartycomputing problems, such as: secure vector dominanceproblem, maximum (minimum) value problem, sortingproblem, and so on. This paper presents a new extendedmillionaires' problem: Alice, Bob, Carol, and Dave have privatenumbers x, y, u and v respectively and they want to determinethe relation between x+y and u+v without disclo- sing x, y, u, v.No party knows the value of x+y, u+v in this scenario. We callthis problem the blind millionaires' problem, which has wideapplication in business cooperation, evaluation system and soon. It is of important theoretical and practical significance.At present, there is no research based on this problem.To solve this problem, we first propose a method namedsecret shifts adding method. This method can be used toprivately add, subtract and multiply in small domain. Thereis no limit to the number of participants, and furthercomputation can be made. Based on the secret shift addingmethod, combining with threshold decryption probabilisticcryptosystem and appropriate encoding scheme, we designsecure comparison protocols for three comparing problemsin small domain. The first protocol applies to threeparticipants for joint computation, each of which haspositive integers. Addition and comparison are implementedin the protocol. The second protocol applies to thejoint computation of four participants, each of which owns apositive integer. Addition, subtraction and comparison areimplemented in the protocol. The third protocol applies tothe joint computation of multiple participants, each of whichhas two data points of 0 or 1. Addition, subtraction, andcomparison are implemented in the protocol. All threeprotocols can correctly output the computing results withoutdisclosing the participant's private data.The blind millionaires' problem is a new problemfirst proposed and solved in this paper. We have beenconducting research in SMC for more than ten years andcontinue to study. Our work is supported by the NationalNatural Science Foundation of China (No. 61272435).