集合间基本操作的多方保密计算

亢 佳，杨晓艺，刘 新

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

集合间基本操作的多方保密计算

亢 佳，杨晓艺，刘 新

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

多方保密计算是近年来国际密码学界研究的热点问题。集合是科学研究中一个非常重要的概念，其在数学领域具有无可比拟的特殊重要性。现实生活中的许多问题可以转化成集合之间的基本操作问题来解决。对集合间的保密操作，如保密地计算集合交集、并集是多方保密计算中的一个重要方面，在保密的数据挖掘，保密的数据库查询等方面有重要的意义，在现实生活中也有广泛的应用前景和实用价值。为了解决集合之间基本操作的保密问题，提出了基于Paillier加法同态加密算法的安全两数差平方计算协议和求解集合交集的保密协议，并设计了基于百万富翁协议的求解集合并集的保密协议。理论分析表明，基于Paillier加法同态加密算法的安全两数差平方计算协议以及求解集合交集与并集的保密协议具有较好的正确性和安全性。

多方保密计算；集合交集；集合并集；加法同态

0 引 言

多方保密计算是近年来国际密码学界的一个研究热点[1-5]，在计算科学中占有重要地位。多方保密计算问题由Yao[6]最先提出，Goldreich等[7]对其进行了深入研究，推动多方保密计算理论的发展。

许多学者致力于研究具有实际应用背景的多方保密计算问题以及它们的解决方案，所研究的问题包括比较两个数的大小[8-11]、保密的数据挖掘[12]、比较两条信息是否相同[13]、保密的数据库查询、保密拍卖[14]、保密的统计分析、保密的计算几何[15-18]等。

集合是科学研究中一个非常重要的概念，其在数学领域具有无可比拟的特殊重要性。现实生活中的许多问题可以利用集合间的基本操作问题来解决。保密的对集合间的操作是多方保密计算中的一个重要方面，在保密的数据挖掘、保密的数据库查询等方面有重要意义，同时在现实生活中也有很高的实用价值。目前已有的关于集合间基本操作的研究有保密地求两个集合的交集、并集，集合成员的保密判定问题等。

保密地求集合间的几种基本操作等问题在现实生活中具有重要意义。例如：2个护肤品旗舰店想掌握他们顾客的消费趋势，也就是他们想得到顾客在旗舰店1买高端护肤品S1同时在旗舰店2买中端护肤品S2的可能性。但是两个旗舰店为了保护顾客的隐私，同时又不想泄露自己的销售情况，都不愿把自己的详细信息告诉对方。在这种情况下，就需要用到保密地求集合交集的协议[19]。

为此，提出了基于加法同态性加密方案的安全两数差平方计算协议，并该协议的基础上提出求解集合交集的保密协议以及基于百万富翁协议的求解集合并集保密协议，同时进行了安全性和正确性分析。

1 预备知识

1.1 可交换的加密方案

对于一个加密方案E，如果EKp(EKq(x))=EKq(EKp(x)),其中EKp(x)表示利用密钥Kp对x进行加密，则称方案E为可交换的加密方案[20]。定义二元谓词如下:

更具体地说，如果一个加密方案满足如下性质，则称其为可交换的加密方案[20]。

(1)加密得到的结果与加密时所使用密钥的顺序无关。

(2)不同的明文经过加密后所得到的密文也不相同。

(3)某一明文m1和对应的密文Ep(m1)(但不泄露密钥p)，对于另外任一明文m2，攻击者不能在多项式时间内对m2进行加密或对Ep(m2)进行解密。

1.2 比较两数相等的协议

Alice有一个私有数据x，Bob有一个私有数据y，他们都想保密地确定x和y是否相等且不泄露x和y的信息。E是一个可交换加密方案,Alice有密钥Kp，Bob有密钥Kq。比较两数相等的解决方案[20]如下：

(1)Alice计算EKp(x),Bob计算EKq(y)。

(2)Alice和Bob交换EKp(x)和EKq(y)。

(3)Alice计算EKp(EKq(y))，Bob计算

EKq(EKp(x))。

(4)Alice和Bob交换EKp(EKq(y))和EKq(EKp(x))，如果EKp(EKq(y))=EKq(EKp(x))，则输出1，否则输出0。

1.3 同态加密方案

同态加密方案是一种特殊的公钥加密方案[21],其概念是文献[22]提出的。同态加密的特殊性质使得能够直接对密文进行运算来代替对明文的运算，从而取得同样的效果，这样不影响明文的保密性。简单来说，对密文的计算等价于明文计算之后再加密。同态加密方案在云计算和多方保密计算中发挥着重要的作用。

目前存在许多同态加密方案,如RSA公钥加密方案、ElGamal加密方案、Paillier加密方案、Goldwasser加密方案等。运用Paillier加密方案的加法同态性[23]，即满足EK(x)⊗EK(y)=EK(x+y)，从加法同态性还可以得到E(x)m=E(mx)。

1.4 安全性定义

半诚实参与者[24]：各个参与者在协议执行过程中不会泄露信息或欺骗，也不会中途退出协议，完全严格按照协议的规定执行协议的每一步。但是他们可能会通过协议执行过程中自己所得到的信息来试图推断其他有用的相关信息。

大部分研究多方保密计算的文献均假设多方保密计算的参与者为半诚实参与者，这是因为只要能够设计出在半诚实参与者模型下保密计算f的协议π，就可以通过位承诺方法将π转换成恶意攻击者参与的模型下保密计算f的协议。在这个转换协议中，一个恶意的参与者将被迫按照半诚实的参与者行事，否则会被发现。简单地说，半诚实参与者在协议执行过程中将不折不扣地执行协议，但他们可能会保留计算的中间结果试图推导出其他参与者的输入。

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

(1)

(2)

2 多方保密计算方案

2.1 安全两数差平方计算协议

问题描述：Alice有一个实数x，Bob有一个实数y。Alice希望保密地得到s，Bob希望保密地得到w，且满足s=w+(x-y)2。具体步骤如下：

(1)Alice与Bob共同协商一个具有加法同态性的加密方案E。Alice选定公私密钥对(PK,SK)，并且将公钥PK告诉Bob，私钥SK保密。

(2)Alice选定非零随机数r1，用公钥PK加密r1x并把E(r1x)，r1发送给Bob。

(3)Bob选择随机数r2,r3，计算并把t1,t2发送给Alice。

t1=E(r1x)y⊕E(r2)=E(r1xy+r2)

(3)

t2=E(r1y2)⊕E(r3)=E(r1y2+r3)

(4)

(4)Alice用私钥SK解密t1,t2，得到s1,s2,并计算s。

s1=D(t1)=D(E(r1xy+r2))=r1xy+r2

(5)

s2=D(t2)=D(E(r1y2+r3))=r1y2+r3

(6)

s=s2-2s1+r1x2=r1(x2+y2-2xy)+r3-2r2

(7)

(5)Bob计算w=r3-2r2。

协议正确性分析：

根据加法同态加密方案的性质，可知E(r1x)y⊕E(r2)=E(r1xy+r2)，E(r1y2)⊕E(r3)=E(r1y2+r3)。

在Alice解密后得到s，s=s2-2s1+r1x2=r1(x2+y2-2xy)+r3-2r2，此时w=r3-2r2=s-r1(x2+y2-2xy)。因此，该安全两数差平方计算协议是正确的。

协议安全性分析：

在步骤2中，Alice与Bob虽然出现了信息交换，但是由于Bob不知道解密的私钥，不会推测出x的值，所以不会有信息泄漏；步骤4中，虽然Alice拥有解密的私钥，但是随机数r2,r3仅有Bob知道，Alice不会由s推测出(x-y)2以及y的值。由此可知，该安全两数差平方计算协议在半诚实模型下是安全的。

2.2 求集合交集的多方保密计算方案

问题描述：Alice拥有一个集合A={a1,a2,…,am}，Bob拥有一个集合B={b1,b2,…,bn}，他们想保密地判定集合A和集合B是否相交，并求得交集I。

协议一设计：

输入：参与方Alice拥有一个私有集合A={a1,a2,…,am}，Bob拥有一个私有集合B={b1,b2,…,bn}。

输出：两个集合的交集I。

1)设置I=∅。

2)对于集合A和集合B中的每个元素，Alice和Bob分别做以下工作：

(1)Alice和Bob分别调用安全两数差平方协议，保密地计算(ai-bj)2。计算完成后，Alice得到sij，Bob得到wij。

(2)Alice和Bob调用比较两数相等协议判断是否sij=wij。如果相等，则记录相应的ai，I∪{ai}。

协议一正确性分析：如果ai=bj，那么sij=wij，由此可知协议正确。

协议一安全性分析：协议一的安全性基于安全两数差平方协议的安全性，证明过程不再赘述。

协议二设计：

输入：参与方Alice拥有一个私有集合A={a1,a2,…,am}，Bob拥有一个私有集合B={b1,b2,…,bn}。

输出：两个集合的交集I。

步骤：

(1)Alice与Bob协商一个可交换的加密方案E。Alice选取密钥KA，Bob选取密钥KB。

(2)Alice利用密钥KA对A={a1,a2,…,am}进行加密，经过计算得到集合EKA(A)={EKA(a1),EKA(a2),…,EKA(am)}，并将集合EKA(A)全部发送给Bob。

(3)Bob利用密钥KB加密EKA(A)，经过计算得到集合EKB(EKA(A))={EKB(EKA(a1)),EKB(EKA(a2)),…,EKB(EKA(am))}。

(4)Bob以EKB(EKA(A))集合中的元素构造一个函数：

f(x)=[x-EKB(EKA(a1))]×[x-EKB(EKA(a2))]× …×[x-EKB(EKA(am))]

(8)

(5)Bob利用密钥KB对B={b1,b2,…,bn}进行加密，经过计算得到集合EKB(B)={EKB(b1),EKB(b2),…,EKB(bn)}，并将集合EKB(B)发送给Alice。

(6)Alice利用密钥KA加密EKB(B)，经过计算得到集合EKA(EKB(B))={EKA(EKB(b1)),EKA(EKB(b2)),…,EKA(EKB(bn))}，并将结果发送给Bob。

(7)对于i∈{1,2,…,n}，Bob判断是否f(EKA(EKB(bi)))=0，若等于0，则Bob可判定bi∈I。

(8)Bob把得到的I发送给Alice。

协议二安全性分析：Alice用自己的密钥对A={a1,a2,…,am}和EKB(B)进行加密，Bob用自己的密钥对B={b1,b2,…,bn}和EKA(A)进行加密，此时在半诚实模型下忽略信息泄露的问题。虽然整个协议中出现双方信息交互的过程，但是由于不知道私钥，不存在信息泄露。所以协议二是安全的。

2.3 求集合并集的多方保密计算方案

问题描述：Alice拥有一个集合A={a1,a2,…,am}，Bob拥有一个集合B={b1,b2,…,bn}，他们想保密地求集合A和B的并集J=A∪B，而不泄露集合A和B的任何私有信息。

协议三设计：

输出：两个集合的并集J=A∪B。

步骤：

在协议执行之前，Alice和Bob共同商定有限域U中元素的一种大小关系，使得U中的每一个元素对应一个特定的整数编码。

(3)Alice与Bob调用百万富翁协议[26]比较mA和mB，协议结束后，Alice将得到的比较结果发送给Bob。

(4)如果mA>mB，那么Alice将mA从集合A中去除，并将mA放入集合J中；如果mA

重复步骤(2)～(4)，直到集合A或者集合B中没有元素为止。

协议三正确性分析：通过调用百万富翁协议可知是否mA>mB，从而Alice和Bob可以从集合A和集合B中找到编码值最大的元素，通过循环，即可将集合A和集合B中的元素不重复地放入到集合J中，所以协议三是正确的。

协议三安全性分析：基于所调用的百万富翁协议的安全性[21]，所以协议三是安全的。

协议三复杂性分析：协议三的计算复杂性主要来自于协议第3步，在协议执行过程中百万富翁协议的执行次数为O(n)。所以协议三与以前的协议相比，计算复杂性有了一定程度的降低。

3 结束语

保密地求解集合的交集与并集对现实生活的实际意义越来越重要。为此，提出了基于具有加法同态性加密方案的安全两数差平方协议、保密判断集合交集的协议以及基于百万富翁协议求解集合并集的保密协议，并对协议的正确性和安全性进行了分析。目前，相关的研究都是基于半诚实模型的，对于多方保密计算的研究与应用有重要的理论意义。应该看到，恶意模型的安全性更高，更具有实际应用的前景，实现恶意模型下的集合操作将是今后的研究方向。

[1] Goldwasser S. Multi party computations: past and present[C]//Proceedings of the sixteenth annual ACM symposium on principles of distributed computing.[s.l.]:ACM,1997:1-6.

[2] Goldreich O.Secure multi-party computation(working draft)[EB/OL].2002.http://www.wisdom.weizmann.ac.il home oded public-html foc.html.

[3] Freedman M J,Nissim K,Pinkas B.Efficient private matching and set intersection[C]//Advances in cryptology.Berlin:Springer,2004:1-19.

[4] Lynn B, Prabhakaran M,Sahai A.Positive results and techniques for obfuscation[C]//Advances in cryptology.Berlin:Springer,2004:20-39.

[5] Aggarwal G,Mishra N,Pinkas B.Secure computation of the k th-ranked element[C]//Advances in cryptology.Berlin:Springer,2004:40-55.

[6] Yao A.Protocols for secure computations[C]//23rd annual symposium on foundations of computer science.[s.l.]:IEEE,1982:160-164.

[7] Goldreich O,Micali S,Wigderson A.How to play any mental game[C]//Proceedings of the nineteenth annual ACM symposium on theory of computing.[s.l.]:ACM,1987:218-229.

[8] Lin H Y,Tzeng W G.An efficient solution to the millionaires’ problem based on homomorphic encryption[C]//International conference on applied cryptography and network security.[s.l.]:[s.n.],2005:456-466.

[9] Li Shundong,Wang Daoshun.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.

[10] Sheikh R,Mishra D K,Kumar B.Secure multiparty computation: from millionaires problem to anonymizer[J].Information Security Journal:A Global Perspective,2011,20(1):25-33.

[11] Grigoriev D,Shpilrain V.Yao's millionaires' problem and decoy-based public key encryption by classical physics[J].International Journal of Foundations of Computer Science,2014,25(4):409-417.

[12] Lindell Y,Pinkas B.Privacy preserving data mining[J].Journal of Cryptology,2002,15(3):177-206.

[13] Fagin R,Naor M,Winkler P.Comparing information without leaking it[J].Communications of the ACM,1996,39(5):77-85.

[14] Cachin C.Efficient private bidding and auctions with an oblivious third party[C]//Proceedings of the 6th ACM conference on computer and communications security.[s.l.]:ACM,1999:120-127.

[15] Atallah M J,Du W.Secure multi-party computational geometry[C]//Workshop on algorithms and data structures.[s.l.]:[s.n.],2001:165-179.

[16] Du W,Atallah M J.Secure multi-party computation problems and their applications:a review and open problems[C]//Proceedings of the 2001 workshop on new security paradigms.[s.l.]:ACM,2001:13-22.

[17] Li Shundong,Wu Chunying,Wang Daoshun,et al.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401-413.

[18] Li Shundong,Wu Chunying,Wang Daoshun,et al.A secure multi-party computation solution to intersection problems of sets and rectangles[J].Progress in Natural Science,2006,16(5):538-545.

[19] 郑 强.不同模型下若干安全多方计算问题的研究[D].北京:北京邮电大学,2010.

[20] 李顺东,王道顺,戴一奇,等.两个集合相等的多方保密计算[J].中国科学:信息科学,2009,39(3):305-310.

[21] Frederick R.Core concept:homomorphic encryption[J].Proceedings of the National Academy of Sciences,2015,112(28):8515-8516.

[22] Rivest R L,Adleman L,Dertouzos M L.On data banks and privacy homomorphisms[J].Foundations of Secure Computation,1978,4(11):169-180.

[23] Wu J H,Zhang P,Shi X B.Research of MA protection based on addition-multiplication homomorphism and composite function technology[J].Journal of Chinese Computer Systems,2012,33(10):2223-2226.

[24] Li Shundong,Wang Daoshun,Dai Yiqi.Efficient secure multiparty computational geometry[J].Chinese Journal of Electronics,2010,19(2):324-328.

[25] Goldreich O.Foundations of cryptography:volume 2,basic applications[M].[s.l.]:Cambridge University Press,2004.

[26] 李顺东,戴一奇,游启友.姚氏百万富翁问题的高效解决方案[J].电子学报,2005,33(5):769-773.

Secure Multi-party Computation of Basic Operation among Sets

KANG Jia，YANG Xiao-yi，LIU Xin

(School of Computer Science,Shaanxi Normal University,Xi’an 710119,China)

Secure multi-party computation is a focus in international cryptographic community study in recent years.The set is a very important concept in scientific research and has an unparalleled special importance in the field of mathematics.Many problems in real life can be solved by using basic operation between sets.The private operation of sets is an important aspect on secure multi-party computation,such as problem of privately determining whether two sets are intersecting and of set union.The secure multi-party computation for basic operation between sets has most important significance on private data mining and confidential database query and also has broad application perspectives and practical value at the same time in real life.In order to solve the problems of set operation,a protocol about two difference square calculation based on the addition homomorphism of Paillier encryption algorithm is presented,which is employed to privately determine whether two sets are intersecting and designed to solve the set union problems depended on Yao's Millionaires' Problem.The theoretical analysis shows that the they have both high accuracy and safety.

secure multi-party computation;set intersection;set union;addition homomorphism

2016-09-20

2016-12-21 网络出版时间：2017-07-05

中央高校基本科研业务费专项(GK201504017)；包头市科技计划项目(2014S2004-2-1-15)

亢 佳(1992-)，女，硕士研究生，通讯作者，研究方向为密码学与信息安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1652.066.html

TP31

A

1673-629X(2017)08-0110-05

10.3969/j.issn.1673-629X.2017.08.023