中国科学:信息科学2011年第41卷第7期:789–797
doc.guandang.net
论文排序问题的安全多方计算协议
唐春明xy ,石桂花x,姚正安z
x广州大学数学与信息科学学院,广州510006
y中国科学院软件研究所信息安全国家重点实验室,北京100080
z中山大学数学与计算科学学院,广州510275
*通信作者.E-mail:ctang@gzhu.edu.cn
收稿日期:2010–03–12;接受日期:2010–10–19
国家自然科学基金(批准号:10871222)资助项目
摘要为某些特殊问题构造有效的安全多方计算协议是多方计算研究领域的一个重要分支.文中使用密钥共享方案为排序问题构造了一个有效的安全多方计算协议,该协议在n个参与者中至多只有t个不诚实者,若t (n 1)/2,则它在被动攻击下是完全安全的;若t<n/3时,它在主动攻击下是完全安全的.排序问题的最简单形式就是“百万富翁”问题.
关键词安全多方计算排序问题密钥分享
1引言
假设两个人各自拥有一个数据,他们希望在没有泄露自己数据任何信息的前提下双方能共同知道谁拥有的数据大,即双方都不知道对方数据的任何信息但是能知道谁的数据大.Yao[1]首先将该类问题描述为“百万富翁”问题,并提出了一个解决方法,从而开辟了安全多方计算这一研究领域.自从Yao提出解决“百万富翁”问题的协议以后,许多类似的协议被提出[2 10],特别在文献[10]中,提出了利用计算几何设计的能够判断任意两个正实数之间的大小或相等关系的协议,而且该协议只需要常数轮.
Yao在文献[1]中为“百万富翁”问题构造了一个有效的协议,但缺乏安全性证明.Lindell和Pinkas在文献[11]中最早给出了Yao协议的安全性证明,但他们的协议(包括Yao的协议)都是假设参与者是半诚实的(即协议参与者按照预定的协议步骤执行).还有一种参与者,也许不按照协议的预定步骤执行,它可能篡改数据,更可能停止协议的执行,这种参与者在安全多方计算领域中被称为恶意的参与者.如果参与者是恶意的,那么在文献[1,11]中的协议就无法安全实现.为了保证在有恶意参与者也能安全实现解决“百万富翁”问题的协议,Goldreich等[12]使用零知识证明协议实现了它,并且,还使用零知识证明为任意概率函数(有n 2个输入)构造了安全多方计算协议.正是他们的这些里程碑工作,给安全多方计算提供了更广阔的应用空间,从而吸引了更多的研究者来从事这方面的研究.
然而,Goldreich等[12]提出的协议使用了零知识证明协议,因此只有在特殊单向函数存在等密码学假设下才能实现,也就是说,所有参与者的计算能力是有限的,因此得到的协议只能是计算安全的,即如果某参与者具有无限的计算能力,那么协议不再安全.另外,Goldreich等人提出的协议的实用性引用格式:唐春明,石桂花,姚正安.排序问题的安全多方计算协议.中国科学:信息科学,2011,41:789–797
排序问题的安全多方计算协... 9页 免费喜欢此文档的还喜欢 安全多方计算协议的研究与... 4页 免费 安全多方计算的应用研究 5页 免费 Mix-Match安全多方计算的...
排序问题的多方保密计算协议_专业资料。为了解决多方参与的保密排序问题,提出了基于保密排序的隐私保护解决方案.该方案首先假设多方保密计算的参与者为半诚实的,即参与...
http://www.paper.edu.cn 公平的基于 RSA 的安全多方排序问题的研究浦明松 ...根据上述方法,本文利用 RSA 提出了一种解决安全多方计算的协议。本 -12 http:...
半诚实模型下安全多方排序问题的研究_三年级数学_数学_小学教育_教育专区。精品资料...最早由 A. Yao [1 ] 提出了一个重要的安全多方计算协议 ——— 百万富 ...
集合成员判定问题的安全多方计算解决方案_数学_自然科学_专业资料。Journal of Computer...相关文档推荐 暂无相关推荐文档 2014 Baidu 使用百度前必读 文库协议...
基于E1Gamal同态密码体制给出了一个解决百万富翁问题的扩展问题的协议——安全多方多数据排序协议。并使用安全多方计算的对安全性的定义,在半诚实模型下,对协议的正确...
是一般安全多方计算协议的研究,另一 部分是针对特定问题的安全多方计算协议的研究...(MixNetwork:MN),将每个逻辑表加密、随机排序,然后将混合后的逻辑 表(混合加密...
在分布式网络环境下, 实现多方参与的安全协同计算是安全多方计算的核心研究问题。现有的大多数网 络安全应用协议都可以规约为一个特定安全多方计算协议,因此安全多方...
37 5 No. May 2009 利用 RSA 密码体制解决安全多方多数据排序问题邱 1 ,2 ...密码学安全 : 若协议只能抵抗具有多项式时间计 算能力的攻击者 , 则称其为...
热门文档