排序问题的安全多方计算协议

《排序问题的安全多方计算协议》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国科学:信息科学2011年第41卷第7期:789{797www.scichina.cominfo.scichina.com论文排序问题的安全多方计算协议¬•¤¬®唐春明,石桂花,姚正安¬广州大学数学与信息科学学院,广州510006•中国科学院软件研究所信息安全国家重点实验室,北京100080®中山大学数学与计算科学学院,广州510275*通信作者.E-mail:ctang@gzhu.edu.cn收稿日期:2010{03{12;接受日期:2010{10{19国家自然科学基金(批准号:10871222)资助项目摘要为某些特殊问题构造有效的安全多方计算协议是多方计算研究领域的

2、一个重要分支.文中使用密钥共享方案为排序问题构造了一个有效的安全多方计算协议,该协议在n个参与者中至多只有t个不诚实者,若t6(n¡1)=2,则它在被动攻击下是完全安全的;若t

3、百万富翁"问题的协议以后,许多类似的协议被提出[2¡10],特别在文献[10]中,提出了利用计算几何设计的能够判断任意两个正实数之间的大小或相等关系的协议,而且该协议只需要常数轮.Yao在文献[1]中为百万富翁"问题构造了一个有效的协议,但缺乏安全性证明.Lindell和Pinkas在文献[11]中最早给出了Yao协议的安全性证明,但他们的协议(包括Yao的协议)都是假设参与者是半诚实的(即协议参与者按照预定的协议步骤执行).还有一种参与者,也许不按照协议的预定步骤执行,它可能篡改数据,更可能停止协议的执行,这种参与者在安全多方计算领域中被称为恶意的参与者.如果参与者

4、是恶意的,那么在文献[1,11]中的协议就无法安全实现.为了保证在有恶意参与者也能安全实现解决百万富翁"问题的协议,Goldreich等[12]使用零知识证明协议实现了它,并且,还使用零知识证明为任意概率函数(有n>2个输入)构造了安全多方计算协议.正是他们的这些里程碑工作,给安全多方计算提供了更广阔的应用空间,从而吸引了更多的研究者来从事这方面的研究.然而,Goldreich等[12]提出的协议使用了零知识证明协议,因此只有在特殊单向函数存在等密码学假设下才能实现,也就是说,所有参与者的计算能力是有限的,因此得到的协议只能是计算安全的,即如果某参与者具有无限的计算能力

5、,那么协议不再安全.另外,Goldreich等人提出的协议的实用性引用格式:唐春明,石桂花,姚正安.排序问题的安全多方计算协议.中国科学:信息科学,2011,41:789{797唐春明等:排序问题的安全多方计算协议非常小,因为它们是基于通讯复杂性很高的零知识证明协议、茫然传输协议、以及位承诺协议.除此之外,恶意参与者的数量t不能是任意的,Goldreich的协议在恶意参与者的情形下是安全多方计算协议的前提是t

6、协议,也就是说,即使参与者计算能力无界,该协议仍然是安全的.他们的协议适合于任意的概率函数,但要保证协议是安全的,若参与者是半诚实的,那么半诚实的参与者数量t

7、模型不一样,或要求协议所具有的性质不一样.而且,所有的这些协议差不多都只是理论上能实现,而要把它们付诸于实践,还有很多困难需要解决.另外,也不可能存在某个安全多方计算的模型能适合所有的问题.因此为不同的问题构造有效的安全多方计算协议便成为多方计算领域的一个重要研究内容.百万富翁"问题(或秘密数据比较问题)一个很自然的推广就是在n>2个数中寻找一个最大(或最小)的数,这样的推广显然是很有现实和理论意义的.理论意义在于,若能解决推广的问题,则百万富翁问题也能解决.现实意义就更多,比如在电子投标中,每个投标者(投标者总数>2)都不