Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering ›› 2010, Vol. 36 ›› Issue (14): 124-126. doi: 10.3969/j.issn.1000-3428.2010.14.045

• Networks and Communications • Previous Articles     Next Articles

Efficient Solution to Yao’s Millionaires’ Problem

ZHA Jun, SU Jin-hai, YAN Shao-ge, YAN Xiao-fang   

  1. (Institute of Electronic Technology, PLA Information Engineering University, Zhengzhou 450004)
  • Online:2010-07-20 Published:2010-07-20

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

查 俊,苏锦海,闫少阁,闫晓芳   

  1. (解放军信息工程大学电子技术学院,郑州 450004)
  • 作者简介:查 俊(1986-),男,硕士研究生,主研方向:保密通信;苏锦海,教授;闫少阁、闫晓芳,硕士研究生

Abstract: 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 set- intersection 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.

Key words: millionaires’ problem, encoding, set-intersection, commutative encryption, security

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

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

CLC Number: