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:
CHA Dun, SU Jin-Hai, YAN Shao-Ge, YAN Xiao-Fang. Efficient Solution to Yao’s Millionaires’ Problem[J]. Computer Engineering, 2010, 36(14): 124-126.
查俊, 苏锦海, 闫少阁, 闫晓芳. 姚氏百万富翁问题的高效解决方案[J]. 计算机工程, 2010, 36(14): 124-126.