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

Efficient Solution to Yao's Millionaires' Problem

作　　者：查俊[1] 苏锦海[1] 闫少阁[1] 闫晓芳[1] 

机构地区：[1]解放军信息工程大学电子技术学院,郑州450004

出　　处：《计算机工程》2010年第14期124-126,共3页Computer Engineering

摘　　要：姚氏百万富翁问题是安全多方计算的典型问题,但已有解决方案多数存在效率低的问题。通过采用0编码与1编码,将百万富翁问题转换为集合交集问题,提出一种基于可交换加密函数的百万富翁问题高效解决方案,并进行了安全性证明。该方案无需复杂的模指数运算,加解密运算为O(n),通信轮数为4,整体性能优于其他方案。Yao＇s Millionaires＇ problem is a typical problem of secure multi-party computation,but most solutions are inefficient.Based on commutative encryption scheme,this paper proposes an efficient and secure solution to millionaires＇ problem,which reduces the problem to the setintersection problem by 0-encoding and 1-encoding for private inputs.Proof of security is followed.There is no complicated modular exponentiation in this solution which only needs O（n） encryption/decryption and 4 rounds of communication.It is more efficient than other solutions.

关 键 词：百万富翁问题 编码 交集 可交换加密 安全性 

分 类 号：TP305[自动化与计算机技术—计算机系统结构]