多方保密计算研究综述

李顺东， 郭奕旻， 巩林明

(陕西师范大学 计算机科学学院, 陕西 西安 710062)

多方保密计算研究综述

李顺东， 郭奕旻， 巩林明

(陕西师范大学 计算机科学学院, 陕西 西安 710062)

总结多方保密计算研究中使用的同态加密、单向散列函数、秘密共享与不经意传输等基本工具；概括保密的科学计算、保密的计算几何、保密的统计分析、保密的数据挖掘等研究内容与研究现状；介绍多方保密计算的安全性定义及有待进一步研究的问题。

密码学；多方保密计算；同态加密；不经意传输；模拟范例

多方保密计算(secure multi-party computation, SMC)是由姚期智教授提出的百万富翁(Millionaires’ problem)问题[1]延伸而来。多方保密计算协议是一种一般意义上的密码学协议，广义上说很多密码学协议如Diffie-Hellman密钥交换协议、数字签名协议、零知识证明协议、秘密共享协议、不经意传输协议等都是多方保密计算协议的特例[1-2]。多方保密计算在密码学与虚拟世界都有广泛的用途，特别是它将成为网络空间信息安全、隐私保护与云计算安全的一项关键技术。广泛的应用促使多方保密计算成为近几年国际密码学界的一个研究热点，Goldwasser曾预言[3]：“多方保密计算今天所处的地位正是公开密钥密码学10年前所处的地位，成为密码学领域里一个极端重要的工具；丰富的理论将使它成为计算领域必不可少的组成部分；它在现实中的应用才刚刚开始。”

Goldreich，Micali和Wigderson等[2,4]深入地研究了多方保密计算的理论问题，奠定了多方保密计算的理论基础。他们做出了两个方面的重要贡献：(1)通过把多方保密计算问题转化成智力游戏，提出了通用的多方保密计算问题协议；(2)设计了一个编译器，给定一个半诚实模型下保密计算f的协议π，该编译器能够编译并输出一个在恶意参与者模型下保密计算f的协议π′，实现了半诚实模型协议到恶意模型协议之间的机械化转化。这些工作的理论意义在于告诉我们任意的多方保密计算问题都是可以计算的，至少有很笨拙的解决方案。

但理论上的可解并不等于现实中的可解决，因为理论上可解没有考虑解决问题所需要的时间，理论上的可解的问题实际上可能需要数百个世纪才能从实际上解决，从实际使用的观点看这些问题实际是不可解的。所以理论上可解应当被看做是多方保密计算问题可解的理论证明。实际上的可解性要求能够给出问题的多项式时间算法,因此理论上证明多方保密计算问题的可解并不表示不再需要对这些问题进行研究，相反地，理论上的可解正是要告诉人们这些问题需要进行更深入的研究，根据实际问题的具体特点找出针对这些问题的高效解决方案。

受Goldwasser的预言与Goldreich的观点激励，密码学研究者广泛开展了各种多方保密计算问题的研究。这些问题可以归纳为几个大类:(1)保密的科学计算；(2)保密的统计分析；(3)保密的数据挖掘；(4)保密的计算几何；(5)其他多方保密计算问题。本文的目的不是要介绍各种多方保密计算问题的应用背景和具体的解决方案，而是介绍多方保密计算研究的通用工具、安全性证明方法、已经研究的各种问题并给出具体的参考文献(应用背景和解决方案可以从相应的参考文献中获得)和有待进一步研究的问题。期望对进行多方保密计算研究的科研人员有所帮助。

1 研究工具

研究多方保密计算需要用到的密码学知识很多，包括各种对称加密算法、各种公钥加密算法、不经意传输协议、单向散列函数等。除此之外还需要灵活运用所学到的各种数学知识。但与多方保密计算关系最为密切的知识主要包括同态加密算法、秘密共享协议、单向散列函数和不经意传输协议。

1.1 同态加密算法

同态加密算法(homomorphic encryption)是具有特殊性质的一种加密算法[5]，是构造多方保密计算最常用的一个模块。通常一个公钥加密方案ε由加密算法Encryptε、解密算法Decryptε和密钥产生算法KeyGenε组成。其中密钥产生算法KeyGenε是一个随机化的算法，给它提供一个安全参数，它会输出一个公钥sk和私钥pk。加密算法Encryptε利用公钥对提供的明文进行加密，输出密文。解密算法Decryptε利用私钥对输入的密文进行解密，恢复明文消息。如果(sk,pk)是由KeyGenε生成的，密文为

c=Encryptε，

那么明文

m=Decryptε。

一个同态加密方案除了上述三个算法之外，还有一个有效算法Evaluateε。给定一组密文

c=(c1,c2,…,ct)，

其中

ci=Encryptε(pk,mi),Evaluateε(pk,f,(c1,…,ct))=Encryptε(pk,f(m1,…,mt))，

也就是说Encryptε(pk,mi)不需要私钥，就可以从m1,…,mt的密文直接计算出f(m1,…,mt)的密文。

著名的RSA算法[6]的密钥生成算法KeyGenε为：给定安全参数k，KeyGenε生成两个k比特的素数p,q；计算n=pq；随机选择一个e使得

gcd(e,(p-1)(q-1))=1

作为公钥，计算一个满足

ed=1 mod (p-1)(q-1)

的d作为私钥。加密过程为

c=Encryptε(e,m)=mdmodn,Decryptε(d,c)=cdmodn。

RSA算法具有乘法同态性，因为

但是RSA是一个确定性的乘法同态加密算法，它对于选择明文攻击是不安全的，这一点影响了它在多方保密计算中的应用。

y=αkmodp,

以(α,y)作为公钥。加密m时选择一个随机数r，加密过程为

c=Encryptε(y,m)=(αrmodp,yrmodp)=(c1,c2),

解密过程为

ElGamal算法具有乘法同态性，因为

ElGamal加密方案是概率加密，所以广泛应用于多方保密计算。

Paillier加密方案[8]的密钥生成算法KeyGenε为：给定安全参数k，KeyGenε生成两个k比特的素数p,q；计算

n=pq，λ=lcm(p-1, 1-1);

计算一个g使得

gcd (L(gλmodn2),n)=1,

其中L(x)定义为

公钥为(g,n)，私钥为λ。加密m时选择一个随机数r，加密过程为

c=Encryptε(g,m)=gmrnmodn2,

解密过程为

Paillier算法具有加法同态性，因为

Paillier加密方案是概率加密，所以也广泛应用于多方保密计算。

1.2 单向散列函数

单向散列函数Hash()是解决多方保密计算问题的有力工具，有很多多方保密计算协议都是利用单向散列函数设计的。我们不讨论单向散列函数的定义，只讨论单向散列函数的性质，这是应用的关键。单向散列函数具有以下性质。

(1) 给定消息M，很容易计算h=Hash(M)。

(2) 给定h=Hash(M)，根据h计算其逆M=Hash-1(h)很难。

(3) 给定M，要找到另一个消息M′，使得Hash(M)=Hash(M′)很难。

(4) 找出两个随机的消息M,M′，使得Hash(M)=Hash(M′)很难。

(5) 给定任意长度的消息，其单向散列函数值的长度(比特数)|Hash(x)|都是相等的。

(6) 如果对x作微小的改变，即使只改变一个比特，Hash(x)的值也会发生惊人的改变。

单向散列函数值比特数的不同对单向散列函数的性质有很重要的影响。比如我们选择的长度为1，并选择二进制数表示，那么这样的函数值的值域就是{0,1}。随便找两个不同的自变量，它们的单向散列函数值都有可能相同，相同的概率为1/2。如果找三个不同的自变量，一定有两个自变量的函数值是相同的。

一般来说如果|Hash(x)|=l，则任意找两个自变量，它们的单向散列函数值相同的概率为2-l。因此在密码学应用中必须选择充分大的l，这个l一般要大于128。

不同的单向散列函数在设计时选择了不同的比特数值，比如MD4、MD5算法[9]选择的是128，而美国的安全散列标准(secure hash standard,SHS)[10]中选用的安全散列算法(secure hash algorithm, SHA)选用的是160位的长度。这样，我们任意找两个不同的自变量，它们的单向散列函数值相同的概率分别为2-128和2-160，这两个概率是那样的小，以至于我们可以认为这样的事情根本不可能发生。可以认为实际上不可能找到两个不同的消息生成相同的单向散列函数值，这样我们就可以将消息的单向散列函数值看作与消息是一一对应的(概率意义下)。在某些使用中我们就可以用单向散列函数值代表消息，因为是单向的，这样做并不会泄露相应的消息，却可以知道两个消息是否相同。

1.3 不经意传输协议

不经意传输(oblivious transfer)的概念是由Rabin[11]提出的。不经意传输解决这样的问题：Alice有k个消息，Bob想得到其中的一个，但不希望Alice知道他想得到哪一个；Alice希望Bob只能得到一个，而其他的消息一点都不泄露。不经意传输的有两种主要形式：1-out-of-2不经意传输与1-out-of-k。在1-out-of-2不经意传输中Alice有50%的机会将一个消息发送给Bob。发送的结果Bob可能得到了消息，也可能没有得到，Alice不知道结果。在1-out-of-k不经意传输中Alice有k个消息，Bob能得到一个消息，而对于得到的这个消息以外的其他消息则一无所知，Alice对于Bob得到哪个消息一无所知。1-out-of-k不经意传输又有两种情况，一种情况是Bob不能选择得到那个消息，另一种情况Bob可以选择想得到哪个消息。1-out-of-k不经意传输是1-out-of-2不经意传输的自然扩展。此外，还有k-out-of-n不经意传输。不经意传输是解决多方保密计算的主要工具，许多多方保密计算问题离开这个工具就没有解决办法。多方保密计算中用的一个重要的隐私保护技巧就是将秘密进行分割，所以常常需要用到秘密共享协议。

1.4 秘密共享

秘密共享就是利用适当的技术把一个秘密拆分成n个份额分发给n个人，任意多于t(t

2 研究领域

多方保密计算的研究领域非常广泛，凡是一项计算所需要的数据由多方持有，而多方都想保护自己数据的机密性，同时又有参与计算的动机，就需要多方保密计算。例如，若干个人想知道他们的工资的平均值(最高值)，而又不想让别人知道自己的工资数，这时就需要多方保密计算协议来解决。多方保密计算所研究的问题大体上可以分为以下几类。

2.1 保密的科学计算

保密的科学计算研究的问题有下面的几种。

(1) 保密比较两个数的大小问题[1]，也就是著名的百万富翁问题。

这个问题提出的最早，研究得也最充分，目前这个问题的解决方案有10多种[12-17]。有研究两个较小的自然数比较的；有研究两个大自然数比较的；有研究两个整数比较的，也有研究两个有理数比较的[18]。有基于公钥密码学的解决方案，也有基于对称密码学的解决方案。百万富翁问题的一个变形被称为社会主义百万富翁问题[19]，也就是比较两个数是否相等。这个问题的解决方案也有10多种[19-20]。

(2) 研究两个集合的关系问题，主要是计算两个集合的交集，两个集合的交集的势，判断两个集合是否相等[21-27]。

这个问题也有很多解决方案，其中最有代表性的方法是把集合的元素表示成多项式的根，再利用同态加密算法，把一个集合的元素保密地代入另一个集合的元素所构成的多项式，保密计算多项式的值来判断具体的一个集合的元素在不在另一个集合里，从而确定集合的交集。能够保密计算交集，就能够保密计算交集的势，但有时候我们只希望计算交集的势，而不希望泄露交集，这就需要设计另外的协议。当一个集合只有一个元素时，集合交集的保密计算问题就转化为保密计算一个元素属不属于另一个集合。

(3) 保密的向量计算问题[28-29]。

这个问题在保密的数据挖掘[31-31]中有广泛的应用，所以在保密数据挖掘的环境下进行了充分的研究。目前研究的问题主要是保密的向量点乘(scalar product)问题[32]。只涉及两个向量的点乘问题，又称为2DNF(disjunctive normal formula)问题[33]。这个问题也有许多解决方案，基本上都是利用同态加密和随机置换进行。

(4) 其他保密的科学计算问题。

这些问题包括保密的最小二乘估计问题[28]，保密的线性规划问题[28,34]，保密的多项式求值问题[35]等等。

2.2 保密的统计分析

统计分析是数据处理的主要活动，是科学研究中发现新知识的主要手段。当数据分析需要在一些机密的数据集上进行时，就需要采用多方保密计算技术。保密的统计分析是多方保密计算的一个实际应用，主要是因为在信息社会不同的主体拥有不同的数据，他们希望在这些数据的基础上进行一些各自都能受益的统计分析，但他们都不愿意将自己拥有的数据提供给其他人，这时就需要多方保密计算来帮助实施。

(2) 保密计算一组数据与另一组数据之间的相关系数(Correlation Coefficient)；保密计算一组数据与另一组数据之间的相关关系(线性回归分析Linear Regression Line)[36-37]；保密的方差计算。解决这一类问题需要用向量点乘协议、保密置换协议。相关系数的保密计算已经是保密统计分析中能解决的比较复杂的问题。更多的保密统计分析问题，比如说协方差、非线性回归、参数估计等现在都还没有办法解决。

2.3 保密的数据挖掘

保密数据挖掘(privacy-preserving data-mining)是数据挖掘中非常活跃的一个研究领域[30-31]。这里面研究的问题非常多，也很有实际意义。应用背景是：不同的实体收集了关于某些对象的不同属性值，某个实体需要利用这些属性值挖掘出关于这些数据的另外的属性值或者各种属性之间的规律，但拥有这些数据的实体因为数据的机密性问题，不愿意将数据直接提供给需要的实体。这里面研究的问题主要有下面一些。

(1) 数据的保密线性回归分析与保密分类[39-41]。

保密的线性回归分析与保密统计分析中的保密线性回归没有差别，只是在数据挖掘中也非常普遍。而保密分类在通常的统计分析中研究的很少。在保密数据挖掘中是指根据预先知道的分类标准，通过对反映一些对象属性的保密数据的保密计算，确定这些对象的某一子集与哪一类对象的属性相符，从而把这个子集的元素分到对应的类。

(2) 数据的保密聚类[42-43]。

聚类是将数据分类到不同的类或者簇的过程，使同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。保密的聚类其实也是分类，只是分类时分类的标准是已知的，可能分成多少类也是已知的，聚类时所要求划分的类是未知的，需要根据对象的属性值的分布，利用一定的规则确定分类的标准和分类数。而保密的聚类则是在保证数据机密的前提下进行聚类分析。

(3) 保密的关联规则分析。

关联规则挖掘是数据挖掘中的一个重要研究内容，关联规则挖掘完全是实用性的观点，只是挖掘规则而不是发现规律。通常是指从购物数据中挖掘出消费者购买的商品中，那些之间有关联关系，也就是说消费者在购买某种商品时通常还会购买哪种商品。这方面的文献有[44-45]。还有保密的决策树构建[46]。

保密的数据挖掘采用的技术有两类，一类是基于随机化扰动的方法[47-48]，另一类是基于密码学的方法[49]。基于随机扰动的方法是给所有数据加上一些符合某种统计特性的噪声，比如给一组数据加上服从标准正态分布的噪声数据。这样添加噪声后隐藏了原始的真实数据，但是不影响平均值的计算。这种方法尽管不会泄漏实际数据的全部信息，但实际上还是泄露了机密数据的大量信息，在需要保证数据机密的环境中，要进行保密的数据挖掘，唯一可以选择的方法就是基于密码学的方法，而基于密码学的方法主要是多方保密计算方法。

2.4 保密的计算几何

保密的计算几何[29]是多方保密计算的一个重要方面。这方面的研究问题来源于计算几何，研究成果的应用则包括计算几何、工程设计、化学工业等。主要问题有下面几类。

(1) 保密的点包含问题。

Alice有一个点P(x,y)，Bob有一个几何图形G(可以是一个凸多边形[29]、凹多边形[50]、圆形、椭圆形[51]、四面体或者任意形状[52])，他们两个想保密地判定P在不在G内。现在关于凸多边形、凹多边形、圆形、椭圆形、四面体的问题都有确定性的多方保密计算协议，而对于任意形状的图形则只有概率解决方法[53]。

(2) 保密的点线关系问题与相交问题[54-56]。

这一类问题主要是为了解决点包含问题而研究出的附带的解决方案。这类问题包括：一个点在不在一条直线上，一个点在不在一条曲线上，一个点在不在一条直线或者曲线的上方。两个几何图形是否相交。

(3) 其他多方保密计算几何问题。

包括范围搜索(range search)问题，距离最近的点对(closest pair)问题，最小的凸壳(convex hull)问题。

2.5 其他保密计算问题

多方保密计算是一个应用非常广泛的研究领域，除了密码学者外，其他领域的学者从自己领域的问题出发提出了许多交叉领域的研究问题，由于版面所限，本文对这些问题不做具体的介绍，只列出这些问题和参考文献，有兴趣的读者可以查阅有关的文献。这些问题包括

(1) 保密出版问题[57-58]；

(2) 数据保密多关键词排序问题；

(3) 保密的数据库查询[59]；

(4) 保密的入侵检测问题；

(5) 保密的数据选择问题；

(6) 保密的排序问题[60]；

(7) 保密的最短路径选择问题[28]；

(8) 保密的多项式插值问题。

3 安全性

多方保密计算的参与者有不同的类型，对于不同的参与者应该有不同的保证机密性的技术。如果参与者都是善意的，安全就容易保证；如果是恶意的参与者，安全就很难保证。不管什么条件下，多方保密计算都不能解决下面的问题：(1) 让一个不愿意参与的人参与多方保密计算；(2) 让任何参与者都输入真实的数据；(3) 让任何参与者都不中途退出。因此不要试图设计能够解决这些问题的多方保密计算协议。

3.1 理想多方保密计算协议

理想的多方保密计算协议需要一个绝对可信的第三者，称为Trent。假设Alice有机密数据x，Bob有机密数据y，他们要利用Trent保密地计算函数f(x,y)。协议如下。

(1) Alice把x发送给Trent；Bob将y发送给Trent。

(2) Trent计算f(x,y)。

(3) Trent将计算结果告诉Alice和Bob。

理想的多方保密计算协议是安全性最高的多方保密计算协议，也是最有威力的多方保密计算协议。所有多方保密计算协议的安全性都是通过与理想多方保密计算协议进行对比来评价的。如果一个实际的多方保密计算协议不比理想多方保密计算协议泄露更多的关于机密数据x,y的信息，我们就说这个多方保密计算协议是安全的。

但理想多方保密计算协议也有严重的实际问题：(1) 在网络环境中找到这样绝对可信的第三者是困难的；(2) 用可信的第三者是有代价的；(3) 在网络环境中，这样的一个可信的第三者可能成为网络的瓶颈。多方保密计算研究就是要研究不需要可信第三者的计算各种f(x,y)的协议。在多方保密计算研究中，往往假设参与者有两种类型，再针对这两种类型设计不同的协议。

3.2 半诚实模型下的安全性

半诚实的参与者模型是一个重要的模型，这是因为：(1) 实际的许多参与者都是半诚实的，所以对于半城实的参与者安全的多方保密计算协议实际上可以解决许多多方保密计算问题；(2) Goldreich曾设计过一个编译器，给编译器输入一个在对半诚实参与者安全的多方保密计算协议，该编译器能够编译输出一个对恶意参与者也安全的协议。另一方面，当人们研究恶意模型下安全的协议时，往往是先设计半诚实模型下安全的协议，然后研究恶意的参与者会如何攻击这样的协议，找到防止恶意攻击的方法并把防止的方法再添加到协议中，形成对恶意参与者安全的协议。所以研究半诚实模型下安全的协议有实际的意义。

半诚实参与者 许多论文所提方案的安全性均假设多方保密计算的参与者为半诚实的参与者。简单地说，所谓半诚实参与者是指参与者在协议执行过程中将不折不扣地执行协议，但他们也会保留计算的中间结果试图推导出其他参与者的输入。

隐私的模拟范例 直观上，如果对于任一个半诚实的参与者，他都可以直接从执行协议时自己的输入与协议的最终输出，通过单独模拟协议的执行过程而得到在执行协议过程中他所能得到的任何信息，这样的协议同理想的多方保密计算协议相比，没有更多的信息泄露，协议就是保密的。即能够保证输入的隐私性。简单地说，保密计算协议要求协议执行过程中参与者所观察到的内容仅用他自己的输入与输出就可以进行模拟。这就是多方保密计算保密性研究中常用的模拟范例。如果一个多方计算协议能够这样进行模拟，参与者就不能从协议的执行过程中得到除计算的结果之外任何有价值的信息，这样的多方计算过程就是保密的。下面把这样的直观感觉形式化。

一些记号 首先引入以下记号，假设双方计算的参加方分别为Alice和Bob。

• 设f=(f1,f2)是一个概率多项式时间函数，π表示计算f的双方计算协议。

•输入为(x,y)时，执行协议π以后，Alice(Bob)的输出结果记为

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

有关计算不可区分的详细论述请看文献[2]。要证明一个多方计算方案是保密的，就必须构造满足定义1的模拟器S1和S2。

模拟范例实际上是把实际的多方保密计算协议与理想的多方保密计算进行比较。因为即使借助于可信的第三者，Alice(Bob)在得到f1(x,y)(f2(x,y))后也可以计算出有关y(x)的一些信息。如果根据自己得到的函数值能够单独计算出的信息和实际执行协议所得到的信息是计算上不可区分的，我们就说实际的协议是安全的，因为它并没有泄漏比理想协议更多的、对于参与者计算另一方的输入有价值的信息。

3.3 双方与多方

多方保密计算有两种情况：(1) 只有两个参与者，这时的多方保密计算又称为双方保密计算；(2) 有三个以上的参与者(包括三个)，这时称为多方保密计算。

这两种情况一般都需要分开研究，因为每种情况都有独特的特征。有时候两方保密计算的协议比较好设计，有时候多方保密计算协议比较好设计。双方保密计算的协议通常都不能简单地推广到多方的情况；多方保密计算协议用于双方保密计算时通常不能保证安全。双方保密计算需要研究半诚实参与者，也需要研究恶意参与者，但不需要研究合谋；而多方保密计算不但需要研究半诚实参与者、恶意参与者，还要保证合谋情况下的安全。

3.4 恶意模型下的安全性

恶意参与者模型是主动攻击者的模型，恶意模型下安全的协议无疑具有更高的安全性。虽然理论上说有了半诚实模型下安全的多方保密计算协议，可以自动地得到在恶意模型下安全的多方保密计算协议，但这样得到的协议是低效的，因此往往需要针对具体的恶意参与者设计在恶意的参与者情况下也安全的多方保密计算协议。

恶意参与者安全的多方计算协议要求：在理想的使用可信的第三者的多方保密计算协议中得不到的信息，在我们所设计的协议中也无法得到。这样就保证了我们的协议和理想的多方保密计算协议一样安全。但习惯上往往是反过来说的，即所述为上述命题的逆否命题。

定义2(恶意参与者的保密性)[2]如果一个多方保密计算协议π中的任意恶意行为能够成功实施的话，在理想的多方保密计算协议Π中也能够成功实施这样的恶意行为。

4 有待研究的问题

(1) 保密的科学计算

这里面还没有解决的问题非常多，比如说保密计算

max(x1,…,xn), min(x1,…,xn),gcd(x1,…,xn), lcm(x1,…,xn)。

这些问题现在还没有好的解决方案。在集合的保密计算方面人们也进行了充分的研究，但是判断两个集合的并集、一个集合是不是另一个集合的子集这类问题也没有好的解决方案。一般的多方保密计算要求保密计算函数z=f(x,y)，其中x,y分别为不同的参与者所拥有。但现在只能计算最简单的函数，比如

等一些非常简单的函数，现在稍微复杂一点的还都不能计算，所以多方保密计算可以研究的问题还很多，但是这些问题的难度也比较大。

(2) 保密的统计分析

在保密的统计分析中，利用多方保密计算所能计算的统计量和统计结果是非常有限的，因而还有许多工作可做。如果有一天可以利用多方保密计算获得所有的统计量和所有希望的统计结果，那么现在各个实体所收集的保密数据都能够发挥应有的作用，将会给我们的社会带来巨大的数据效益与经济效益。

(3) 保密的数据挖掘

目前用多方保密计算技术来实现保密的数据挖掘存在的主要问题是：数据挖掘的数据集都是巨大的，数据极多，而多方保密计算都需要高强度(高复杂性)的计算，这两者综合作用的结果造成保密的数据挖掘效率极低，成本极高。而采用随机扰动的办法不能真正保证数据的机密。所以需要进行两方面的工作，一是设计高效的多方保密计算协议，尤其是基于对称密码学理论的协议；而是设法提高基于随机扰动方法的协议的安全水平。

(4) 保密的计算几何问题

保密的计算几何问题有很强的实际应用背景，但目前解决计算几何问题的多方保密计算协议需要的计算量都非常大，效率很低。所以保密的计算几何研究主要是探索新的计算几何问题，同时大力改进现有解决方案的效率，使有关的协议可以用于解决实际问题。

(5) 恶意模型下的多方保密计算协议

目前的研究成果集中在半诚实模型下的多方保密计算协议，这是有原因的。因为在实际工作中多数参与多方保密计算的人都是半诚实的，因此研究半诚实模型下的多方保密计算协议在许多情况下是比较简单的，也是符合实际的，也确实能够解决很多的实际问题。但毕竟我们不能限制多方保密计算协议只能用于半诚实的环境，如果将半诚实模型下安全的协议用于恶意模型，协议就不能保证安全，因此需要研究针对恶意参与者安全的多方保密计算协议。

(6) 多方保密计算的应用研究

目前虽然已经有多方保密计算的工业应用的成功案例[61-62]，但多方保密计算的应用研究总体上还很不充分。任何学科的发展都需要有关键的应用来推动，而多方保密计算的应用研究比较缺乏，因此探索多方保密计算的新用途是多方保密计算研究的一个重要方面。

5 结束语

本文总结了多方保密计算研究的现状，已经研究的问题，常用的多方保密计算协议的设计工具。分析了多方保密计算协议安全性的定义。指出了有待进一步研究的问题。

[1]YaoAC.Protocolsforsecurecomputations[C]//Proceedingsofthe23thIEEESymposiumonFoundationsofComputerScience.CALosAlamitos:IEEEComputerSocietyPress, 1982: 160-164.

[2]GoldreichO.FoundationsofCryptography:BasicApplications[M].London:CambridgeUniversityPress, 2004:599-764.

[3]GoldwasserS.Multi-partycomputations:Pastandpresent[C]//ProceedingsofthesixteenthannualACMsymposiumonPrinciplesofdistributedcomputing.NewYork:ACMPress, 1997: 21-24.

[4]GoldreichO,MicaliS,WigdersonA.HowtoplayANYmentalgame[C]//ProceedingsofthenineteenthannualACMconferenceonTheoryofcomputing.NewYork:ACMPress, 1987: 218-229.

[5]GentryC.Afullyhomomorphicencryptionscheme[D].CaliforniaStanford:StanfordUniversity, 2009.

[6]RivestRL,ShamirA,AdlemanL.Amethodforobtainingdigitalsignaturesandpublic-keycryptosystems[J].CommunicationsoftheACM, 1978, 21(2): 120-126.

[7]ElGamalT.Apublickeycryptosystemandasignatureschemebasedondiscretelogarithms[C]//ProceedingsofCrypto’ 85:LectureNoteinComputerScienceVol218.Berlin:Springer, 1985: 10-18.

[8]PaillierP.Public-keycryptosystemsbasedoncompositedegreeresiduosityclasses[C]//ProceedingsofEUROCRYPT’99:LectureNoteinComputerScienceVol1592.Berlin:Springer, 1999: 223-238.

[9]RivestR.TheMD5message-digestalgorithm[J/OL]. (1992-04-01)[2015-07-28].http://tools.ietf.org/html/rfc1321?ref=driverlayer.com.

[10]EastlakeD,JonesP.USsecurehashalgorithm1 (SHA1)[R/OL]. (2001-06-02)[2015-07-28].http://www.rfc-editor.org/rfc/rfc3174.txt.

[11]RabinMO.HowToExchangeSecretswithObliviousTransfer[R/OL].IACRCryptologyePrintArchive. (2005-12-12)[2015-07-28].https://eprint.iacr.org/2005/187.pdf.

[12]IoannidisI,GramaA.AnefficientprotocolforYao’smillionaires’problem[C]//Proceedingsofthe36thAnnualHawaiiInternationalConferenceonSystemScience.USAHawaii:IEEE, 2003: 6-10.

[13]LinHY,TzengWG.Anefficientsolutiontothemillionaires’problembasedonhomomorphicencryption[C]/Proceedingsofthe3rdInternationalConferenceonAppliedCryptographyandNetworkSecurity:LectureNoteinComputerScienceVol3531,Berlin:Springer, 2005: 456-466.

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

[15]LiSD,WangDS,DaiYQ,etal.SymmetriccryptographicsolutiontoYao’smillionaires’problemandanevaluationofsecuremultipartycomputations[J].InformationSciences, 2008, 178: 244-255.

[16]LiSD,DaiYQ,YouQY.Securemulti-partycomputationsolutiontoYao’smillionaires’problembasedonsetinclusion[J].ProgressinNaturalScience, 2005, 15(9): 851-856.

[17] 李顺东, 王道顺. 基于同态加密的高效多方保密计算[J]. 电子学报, 2013, 41(4): 798-803.

[18]LiSD,WangDS,DaiYQ.Symmetriccryptographicprotocolsforextendedmillionaires’problem[J].ScienceinChinaSeriesF:InformationSciences, 2009, 52(6): 974-982.

[19]BoudotF,SchoenmakersB,TraoreJ.Afairandefficientsolutiontothesocialistmillionaires’problem[J].DiscreteAppliedMathematics, 2001, 111(1): 23-36.

[20]FaginR,NaorM,WinklerP.Comparinginformationwithoutleakingit[J].CommunicationsoftheACM, 1996, 39(5): 77-85.

[21]FreedmanMJ,NissimK,PinkasB.Efficientprivatematchingandsetintersection[C]//ProceedingsofEUROCRYPT2004:LectureNoteinComputerScienceVol3027.Berlin:Springer, 2004: 1-19.

[22]HazayC,LindellY.Efficientprotocolsforsetintersectionandpatternmatchingwithsecurityagainstmaliciousandcovertadversaries[J].JournalofCryptology, 2010, 23(3): 422-456.

[23]DeCristofaroE,TsudikG.Practicalprivatesetintersectionprotocolswithlinearcomplexity[C]//Proceedingsof14thInternationalConferenceonFinancialCryptographyandDataSecurity:LectureNoteinComputerScienceVol6052.Berlin:Springer, 2010: 143-159.

[24]Dachman-SoledD,MalkinT,RaykovaM,etal.Efficientrobustprivatesetintersection[J].InternationalJournalofAppliedCryptography, 2012, 2(4): 289-303.

[25]KalyanasundaramB,SchintgerG.Theprobabilisticcommunicationcomplexityofsetintersection[J].SIAMJournalonDiscreteMathematics, 1992, 5(4): 545-557.

[26]LiSD,DaiYQ,WangDS,etal.Comparingtwosetswithoutdisclosingthem[J].ScienceinChinaSeriesF:InformationSciences, 2008, 51(9): 1231-1238.

[27]KissnerL,SongD.Privacy-preservingsetoperations[C]//Proceedingsof25thAnnualInternationalCryptologyConference:LectureNoteinComputerScienceVol3621.Berlin:Springer, 2005: 241-257.

[28]DuW,AtallahJ.Securemulti-partycomputationproblemsandtheirapplications:areviewandopenproblems[C]//Proceedingsofthe2001workshoponNewsecurityparadigms.NewYork:ACMPress, 2001: 13-22.

[29]AtallahJ,DuW.Securemulti-partycomputationalgeometry[C]//ProceedingsofInternationalWorkshoponAlgorithmsandDataStructures:LectureNotesinComputerScienceVol2125.Berlin:Springer, 2001: 165-179.

[30]GoethalsB,LaurS,LipmaaH,etal.Onprivatescalarproductcomputationforprivacy-preservingdatamining[C]//ProceedingsofInternationalConferenceonInformationSecurityandCryptology2004:LectureNotesinComputerScienceVol3506.Berlin:Springer, 2005: 104-120.

[31]AgrawalR,SrikantR.Privacy-preservingdatamining[C]//ProceedingsoftheACMSIGMODConferenceonManagementofData.NewYork:ACMPress, 2000, 29(2): 439-450.

[32]AmirbekyanA,Estivill-CastroV.Anewefficientprivacy-preservingscalarproductprotocol[C]//ProceedingsofthesixthAustralasianconferenceonDataminingandanalytics(Volume70).Sydney:AustralianComputerSocietypress, 2007: 209-214.

[33]BonehD,GohEJ,NissimK.Evaluating2-DNFformulasonciphertexts[C]//ProceedingsofSecondTheoryofcryptographyConference:LectureNoteinComputerScienceVol3378.Berlin:Springer, 2005: 325-341.

[34]MangasarianOL.Privacy-preservinglinearprogramming[J].OptimizationLetters, 2011, 5(1): 165-172.

[35]NaorM,PinkasB.Obliviouspolynomialevaluation[J].SIAMJournalonComputing, 2006, 35(5): 1254-1281.

[36]DuW,AtallahMJ.Privacy-preservingcooperativestatisticalanalysis[C]//Proceedingsofthe17thAnnualComputerSecurityApplicationsConference.Washington:IEEEComputerSociety, 2001: 102-110.

[37]DuW,HanYS,ChenS.Privacy-PreservingMultivariateStatisticalAnalysis:LinearRegressionandClassification[C]//ProceedingsoftheFourthSIAMInternationalConferenceonDataMining.Philadelphia:SIAM. 2004, 4: 222-233.

[38]DongR.SecureMultipartyComputation[D].BowlingGreen:BowlingGreenStateUniversity, 2009.

[39]ChenK,LiuL.Privacypreservingdataclassificationwithrotationperturbation[C]//ProceedingsoftheFifthIEEEInternationalConferenceonDataMining.Washington:IEEEComputerSociety, 2005: 589-592.

[40]ZhongZYS,WrightRN.Privacy-preservingclassificationofcustomerdatawithoutlossofaccuracy[C]//SIAMInternationalConferenceonDataMining(SDM).NewportBeach:SIAM, 2005.

[41]AmirbekyanA,Estivill-CastroV.Privacy-preservingregressionalgorithms[C]//Proceedingsofthe7thWSEASInternationalConferenceonsimulation,modelingandoptimization.StevensPoint:WorldScientificandEngineeringAcademyandSociety(WSEAS), 2007: 37-45.

[42]VaidyaJ,CliftonC.Privacy-preservingk-meansclusteringoververticallypartitioneddata[C]//ProceedingsoftheninthACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.NewYork:ACM, 2003: 206-215.

[43]HeW,LiuX,NguyenH,etal.Pda:Privacy-preservingdataaggregationinwirelesssensornetworks[C]//INFOCOM2007 26thIEEEInternationalConferenceonComputerCommunications.NewJersey:IEEE, 2007: 2045-2053.

[44]VaidyaJ,CliftonC.Privacypreservingassociationrulemininginverticallypartitioneddata[C]//ProceedingsoftheeighthACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.NewYork:ACM, 2002: 639-644.

[45]EvfimievskiA,SrikantR,AgrawalR,etal.Privacypreservingminingofassociationrules[J].InformationSystems, 2004, 29(4): 343-364.

[46]EmekiF,SahinOD,AgrawalD,etal.Privacypreservingdecisiontreelearningovermultipleparties[J].Data&KnowledgeEngineering, 2007, 63(2): 348-361.

[47]VaidyaJ,CliftonC.Privacy-preservingdatamining:Why,how,andwhen[J].IEEESecurity&Privacy, 2004, 2(6): 19-27.

[48]KarguptaH,DattaS,WangQ,etal.Ontheprivacypreservingpropertiesofrandomdataperturbationtechniques[C]//ProceedingsoftheThirdIEEEInternationalConferenceonDataMining.Washington:IEEEComputerSociety, 2003: 99-106.

[49]PinkasB.Cryptographictechniquesforprivacy-preservingdatamining[J].ACMSIGKDDExplorationsNewsletter, 2002, 4(2): 12-19.

[50]LiSD,WangDS,DaiYQ.AEfficientSecureMultipartyComputationalGeometry[J].ChineseJournalofElectronics, 2010, 19(2): 324-328.

[51]LiSD,DaiYQ.Securetwo-partycomputationalgeometry[J].JournalofComputerScienceandTechnology, 2005, 20(2): 258-263.

[52]LiSD,WuCY,WangDS,etal.Securemultipartycomputationofsolidgeometricproblemsandtheirapplications[J].InformationSciences, 2014, 282: 401-413.

[53] 李顺东，戴一奇.集合包含与几何包含问题的多方保密计算[J].计算机研究与发展，2005, 42(10): 1647-1653.

[54] 罗永龙，黄刘生，徐维江，等.一个保护私有信息的多边形相交判定协议[J]. 电子学报，2007, 35(4): 686-691.

[55] 刘文，罗守山，陈萍. 保护私有信息的点线关系判定协议及其应用[J]. 北京邮电大学学报，2008, 31(2): 72-75.

[56]LiuL,WuC,LiS.Twoprivacy-preservingprotocolsforpoint-curverelation[J].JournalofElectronics(China), 2012, 29(5): 422-430.

[57]LiT,LiN,ZhangJ,etal.Slicing:Anewapproachforprivacypreservingdatapublishing[J].IEEETransactionsonKnowledgeandDataEngineering, 2012, 24(3): 561-574.

[58]FungB,WangK,ChenR,etal.Privacy-preservingdatapublishing:Asurveyofrecentdevelopments[J].ACMComputingSurveys(CSUR), 2010, 42(4): 14.

[59]ChangYC,MitzenmacherM.Privacypreservingkeywordsearchesonremoteencrypteddata[C]//Proceedingsofthe3rdInternationalConferenceonAppliedCryptographyandNetworkSecurity:LectureNoteinComputerScienceVol3531.Berlin:Springer, 2005: 442-455.

[60]AggarwalG,MishraN,PinkasB.Securecomputationofthekth-rankedelement[C]//ProceedingsofEUROCRYPT2004:LectureNoteinComputerScienceVol3027.Berlin:Springer, 2004: 40-55.

[61]BogetoftP,ChristensenDL,DamgardI,etal.Securemultipartycomputationgoeslive[C]//Proceedingsofthe13thInternationalConferenceonFinancialCryptographyandDataSecurity:LectureNoteinComputerScienceVol5628.Berlin:Springer, 2009: 325-343.

[62]PinkasB,SchneiderT,SmartNP,etal.Securetwo-partycomputationispractical[C]//ProceedingsofASIACRYPT2009:LectureNoteinComputerScienceVol5912.Berlin:Springer, 2009: 250-267.

[责任编辑:瑞金]

Secure multiparty computation review

LI Shundong, GUO Yimin, GONG Linming

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

This paper first summarizes the basic primitives of secure multiparty computation including homomorphic encryption schemes, one-way hash functions, secret sharing and oblivious transfer, and then reviews the fields and the state of the art of secure multiparty scientific computation, secure multiparty computational geometry, privacy-preserving statistical analysis and privacy-preserving data-mining. Finally, it introduces the most acceptable security definition and the problems that need further studying.

cryptography, secure multiparty computation, homomorphic encryption, oblivious transfer, simulation paradigm

2015-05-18

国家自然科学基金资助项目(61272435,61070189)

李顺东(1963-)，男，博士，教授，博士生导师，从事密码学与信息安全、电子商务研究。E-mail: shundong@snnu.edu.cn 郭奕旻(1992-)，女，硕士研究生，研究方向为信息安全与密码学。E-mail: yiminguo@snnu.edu.cn

10.13682/j.issn.2095-6533.2015.05.001

TP309.7

A

2095-6533(2015)05-0001-10