文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 姚氏百万富翁问题的高效解决方案
侵权投诉

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

姚氏百万富翁问题是安全多方计算的典型问题,但已有解决方案多数存在效率低的问题。通过采用0编码与1编码,将百万富翁问题转换为集合交集问题,提出一种基于可交换加密函数的百万富翁问题高效解决方案,并进行了安全性证明。该方案无需复杂的模指数运算,加解密运算为O(n),通信轮数为4,整体性能优于其他方案。

第 3卷第 l期 6 4 1 . 36

计

算

机

工

程

21年 7 00月 J l 0 0 uy 2 1

No.4 1

Co put rEng ne r ng m e i ei

安全技术

文章编号: oo 32( l)—02—0 10— 4 2 0 4 1 3文献标识 A 8o 1 4 码:

中圈分类号I P0 35 T

姚氏百万富翁问题的高效解决方案 查俊,苏锦海,闫少阁,闫晓芳 (放军信息工程大学电子技术学院,郑州 4 0 0 )解 50 4

摘

要:氏百万富翁问题是安全多方计算的典型问题,但已有解决方案多数存在效率低的问题。姚通过采用 0编码与 1编码,百万富翁将

问题转换为集合交集问题,提出一种基于可交换加密函数的百万富翁问题高效解决方案,并进行了安全性证明。该方案无需复杂的模指数 运算,加解密运算为 D() n,通信轮数为 4,整体性能优于其他方案。

关奠词:百万富翁问题;编码;交集;可交换加密;安全性

Ef c e l i n t o’ ilo ie’ o e i f i ntSo uto oYa SM li na r s Pr blm ZHA u, U i - a, J n S J n h i YAN ha— e Y S o g, AN a - n Xi o f g a ( s t t o l t nc e h oo y P A I fr t nE g n eig U iest, h n z o 5 0 4 I t ue f e r i T c n lg, L o mai n ie r nv ri Z e g h u 0 0 ) ni E co n o n y 4

[ src]Y oSMiin i s po lm i atpcl rbe o euemutpr o uain b tmotslt n r nfcet B sdo Abta t a’ lo ar’ rbe s i o l l e y ap m fscr l—at c mp tt, u s oui saeie i . ae n i y o o i n c mmu a i ee c y t n s h me t sp p r o o e n e c e ta d s c r o u i n t l o a r s p o l m, ih r du e h r b e t e s t o t t n r p i c e, hi a e p s sa f in n e u e s l t o mi i n ie’ r b e wh c e c st ep o l m o t e v o pr i o l h i tr e t n

p o e b - n o i g a d 1 e c d n o rv t n u s Pr o fs c rt sf lo d n e s c i r blm y 0 e c d n n - n o i g f rp i ae i p t o fo u i i o l we Th r sn o l a e d lre p n n i t n o e y e ei o c mp i t d mo u a x o e tai c o i i o u i n wh c n y n e s0 )e c y to/ e r p i n a d 4 r u d fc mmu i a i n ti mo e e ce t a t e o u i n . n t ss l t i h o l e d h o n r p i n d c y to n o n so o n c t I s o r f i n n o rs l t s i h t h o

[ ywod]miini spo lm;n o ig stit scin c mmuaieecy t n sc ry Ke r s loar’rbe ec dn;e— e et;o l e nr o tt nrpi;eui v o t

‘

1概述 姚氏百万富翁问题…由 A de .a n rw CY o于 18年首次提 92 出。 a给出了一个趣味性的例子:个争强好胜的富翁 A i Yo 2 le c

百万富翁问题是一个典型的双方安全计算问题,其数学描述如下:参与方 A i l e和 B b分别具有秘密输入 X和 Y, c o

和B b o在街头相遇,如何在不暴露各自财富的前提下比较出 谁更富有?经过文献[] 2的研究,百万富翁问题已经发展成为现代密码学中一个非常活跃的研究领域,即安全多方计算 ( e ueMut p ryC mp tt n S C) S c r l— at o uai, M i o。

双方协同计算以下函数: m =

用于解决该问题的协议万需要满足以下要求:

文献【就百万富翁问题给出了一个解决方案, 1】但效率非常低,计算复杂性为输入规模的指数函数,用于比较 2个较大的数时不实用;文献[】 2利用算术电路解决了一般意义上的

() 1参与方 A i l e和 B b c o均形式化为概率多项式时间的图灵机,且都为半诚实的。也就是说 Al e和 B b在协议的执 i c o行过程中将完全执行协议,但是他们也会保留中间计算结果, 试图推导出对方的输入。 () 2正确性:协议 1执行完以后,Ale返回 1当且仅当/"

i c >。

安全多方计算问题,将其应用于百万富翁问题,计算及通信成本均与输入规模呈线性关系;文献[】 3直接针对百万富翁问题,提出了一个基于茫然传输( biiu rnfrO ) O l o s ase, T的解决 v T 方案,利用简单的异或运算成功地解决了该问题;还有一些

() l e的保密性: ie有 X或。≠ ) 3A i c Al拥 c ’对于 B b来 o说是不可区分的。 ()o的保密性:除了 X最终的结果 fx),Ale 4B b和 (,, ) i c

学者将同态加密的思想应用于百万富翁问题,也取得了很好的研究成果。 本文利用 0编码与 1编码,将百万富翁问题转换为集合

的交集问题,提出一种基于可交换加密函数的百万富翁问题

不能得到任何信息。 22安全性定义 .安全多方计算中的安全性证明采用了一个特殊的方法,

解决方案,其计算及通信复杂度明显降低。同时对该方案的 安全性进行了理论证明。

它通过定义一个理想模型,用理想模型仿真现实协议,如果

2预备知识 2数学模型 . 1安全多方计算是一种分布式协议。在这个协议中,设 P={ , } n,…,是个参与者集合,们想要共同“全地”他安

现实协议能被理想模型所仿真,且输出结果具有不可区分性, 那么现实协议就是安全的。 为了方便地给出半诚实模型下的安全性定义,首先引入下列符号。假设协议的参与方分别为 A i l e和 B b c o。Ale和 i c B b要计算的函数为 f:,{,÷f,{, o ( 1×0l卜 0} 0l 0 J} 1 x r。函数 作者筒介:查俊(96 )男, 18-,硕士研究生,主研方向:保密通信; Em i hz ̄ n 6. m -al ah u@13 o :c c

计算某个给定的有,输入和 n个输出的函数 z个

fJ,…,=(。 )其中,函数,的 n个输入 (而, ) y,, q Y…,, X,2 分别由 n参与者,,,秘密地掌握而不被 l, X…,个 …

苏锦海,教授;闰少阁、闫晓芳,硕士研究生

他人知道,在计算结束后,,…,分别得到输出 只, 一

收稿日期:20—22 091. 2

1一 24

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

第1页

你可能喜欢

  • 酒店无线网络覆盖
  • 问题的解决
  • 公共自行车
  • 数学建模解题方法
  • 富人的28个理财习惯
  • 亿万富翁
  • 白手起家
  • 十四个很准的心理暗示

热门文档

相关文档

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

    姚氏百万富翁问题的高效解决方案_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 姚氏百万富翁问题的高效解决方案_理学_高等教育_教育专区。维普资讯 ...

  • 乘法同态加密的百万富翁协议的改进

    百万富翁问题的解决方案已经成为许多安全多方计算问题解决方案的一个基本模块,给出...姚氏百万富翁问题的高效解决方 案 [J]. 计算机工程,2010 ,14:124-126. 责任...

  • 半诚实模型下公平高效的安全两方比较协议

    如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处...[7] 李顺东, 戴一奇, 游启友.姚氏百万富翁问题的高效解决方案[J].电 子...

  • 利用RSA 密码体制解决安全多方多数据排序问题

    我们提出了一个基于 RSA 同态密码体制的解决安全多方多数据排序问题 的方案 , ...姚氏百万富翁问题的高效解决 [ 12 ] R Agrawal , A Evfimievski , R Srikant...

  • 密码学实验期中考试实验报告

    学院数学系信息与计算科学专业 2.1 整体算法: 以姚氏百万富翁问题(N=2)的...五、代码 /***GMP、RSA加密 姚氏百万富翁解决方案的实现***/ #include <iostream...

  • 安全计算研究综述—陈林—1938217(修改)

    “姚氏百万富翁问题” 提出了安全多方计算的概念[4]...在陈良的《半诚实模型下公平高效的安全两方比较协议...寻找特殊领域的安全多方计算问题及其解决方案是值 得...

  • 公平的基于RSA的安全多方排序问题的研究

    提出了半诚实模型下多方安全排 序问题的解决方案。 ...Cachin 在文献[3]中提出了更为高效的百万富翁协议...排序问题实际上是姚氏百万富翁问题的一个推广问题。...

  • 密钥共享体制与安全多方计算

    最早是由 A.Yao〔11〕于1982 年通过姚氏百万富翁问题提出了安全两 方计算问题...在处理安全多方计 算时, 我们采取完全不同的途径。 首先构造一个理想方案, 它...

  • 秘密比较

    ? 姚氏百万富翁问题研究现状 1982年,姚氏百万富翁协议,O(2n) ①不可信第三方...协议五:基于同态加密的百万富翁问题高效解决方案 ? 协议思想:对保密输入进行0...

  • 阶段报告(表格 模板)

    姚氏百万富翁问题 ... 错误!未定义书签。 错误!未定义...基于自定义函数的百万富翁的高效解决方案[50] ... 错误!未定义书签。 错误!未定义书签。 3.1.4 3...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email