姚氏百万富翁问题的高效解决方案.pdfVIP

维普资讯 第5期 电 子 学 报 v01．33 No．5 2O05年5月 ACTA 眦 CIRoN10 0 May 2O05 姚氏百万富翁问题的高效解决方案 李顺东，戴一奇，游启友 (清华大学计算机科学与技术系，北京 100(184) 摘 要：姚氏百万富翁问题解决方案已经成为许多多方必威体育官网网址计算问题解决方案的一个基本模块，但现有的解决 方案效率低下，因而影响到其他多方必威体育官网网址计算方案的效率．本文利用长度函数与不经意传输设计了一个高效的解决方 案，新方案同原有方案相比，计算复杂性明显降低． 关键词： 百万富翁问题；多方必威体育官网网址计算；不经意传输；计算复杂性 中图分类号： TN918．2 文献标识码： A 文章编号： 0372-2112(2(X)5)05-0769-05 AnEfficientSolutiontoYao’SMillionaires’Problem uShun—dong，DM Yi—qi，YOUQi—you ( 加鲥 of SdmweandTeduudogy，Tsn／ghua ， 100084，Chn／a) Ab ： rI1leprotocolsforYao’sMillionaires’problem havebeenbuildingblocksofsolutionstomanyseCUli~multi—party 伽衄 I 加 pmblen~．Butknown solutionsarenotefficiente肿u and thusaffecthte efficiency ofmany secul~multi—party computationprotocols．Inthispaper，weconsllalctanew efficientsolutiontomillionaires’problem basedonlengthfunctionand oblivioustranKfer．G嘲叩哪耐 wiht knownsolutions，ollr1 oslutionhasmuchlesscorrq~tationalcompl~ty． KeywO代b： millionairesproblem；securemulti—partycomputation；oblivioustransfer；computationalcomplexity 能够给出问题的多项式时间的算法，理论解决方案并没有给 1 引言 出这样的多项式时间算法．因此O．Goldreich指出L4J：理论上 姚氏百万富翁问题首先由华裔计算机科学家、图灵奖获 证明多方必威体育官网网址计算问题的可解并不表示不再需要对这些问题 得者姚启智教授提出…1．在文献[1]中，姚提出了这样一个问 进行研究，相反，应用这类没有任何具体信息的一般条件下导 题：两个百万富翁Alice和Bob想知道他们两个谁更富有，但 出的解决方案来解决具体的多方必威体育官网网址计算问题可能是不实际 他们都不想让对方知道 自己财富的任何信息，这就是百万富 的；基于效率的原因，对于具体的问题需要研究具体的解决方 翁问题．文献E2]给出了这个问题的一些实际应用，假设Alice 案．具体问题中给出的信息可能使得解决方案的效率大大提 希望向Bob购买一些商品，但她愿意支付的最高金额为 元； 高． Bob希望的最低卖出价为Y元．Alice与Bob都非常希望知道 百万富翁问题解决方案已经成为许多多方必威体育官网网址计算问题 与Y那个大，如果 Y，他们就可以开始讨价还价；如果