同态加密的百万富翁问题高效解决方案

An Efficient Homomorphic Encryption Based Solution to Millionaires' Problem

安全多方计算问题由图灵奖得主姚期智于上世纪八十年代首先提出,现在已经成为密码学的一个重要研究方向.百万富翁问题是多方安全计算研究的热点问题之一,也是其他安全多方计算协议的基本构成模块,但现有的解决方案效率低下,因而会影响其他安全多方协议的效率.基于同态加密算法,通过对保密的数据进行0-1编码,设计了一个计算百万富翁问题的协议,并利用模拟范例对协议进行安全性证明.通过效率分析显示我们的方案是简单、高效的.最后利用这个新的协议作为基本模块,设计了一个保密数据查询问题的协议,并给出了应用实例.

Secure Multi-party Computation was first proposed by A. C. Yao in 1980s. Now,it is a new and important area of cryptography. The millionaires＇ problem is an important problem in secure multiparty computation and a basic building block of secure multiparty computation protocol. But known solutions are not efficient enough and thus affect the efficiency of many secure multiparty computation protocols. In this paper, we first propose a 0-1 encoding scheme to encode private numbers;then based the new encoding scheme and a homomorphic encryption scheme, we design a protocol for millionaires＇ problem and prove that the protocol is secure in the semi-honest model using the simulation paradigm. The performance analysis indicates that our protocol is simpler and more efficient than the others. Finally, we utilize this scheme to propose a solution to privacy-preserving data querying problem and show an example of its applications.