AN EFFICIENT HOMOMORPHIC ENCRYPTION BASED SOLUTION TO MILLIONAIRES’ PROBLEM
HUIRU CHENG *
College of Science, North China University of Technology, Beijing 100144, P. R. China.
*Author to whom correspondence should be addressed.
Abstract
Secure multi-party computation is an important research direction of international cryptography in recent years. The millionaires’ problem studied in this paper is the most basic and important problem of secure multi-party computation. The essence is to compare the size of two data confidentially. But most of the existing solutions are inefficient, and most of them don't do a good job of judging if the two data are equal. In order to design a protocol of the millionaires’ problem that is simple, efficient and meticulous distinction between the size of two numbers or equal relationship, this paper firstly proposes a new method based on 0-1 coding to encode the encrypted data. This method and the homomorphic encryption algorithm are used to design a protocol to solve the millionaires’ problem. The efficiency analysis shows that the protocol is simple and efficient. Finally, based on the new protocol, an efficient protocol is designed to calculate the number of intersections problem.
Keywords: Secure multi-party computation, millionaires’ problem, homomorphic encryption, number of set intersections