An Efficient Protocol for Private Comparison Problem

Wen Liu, Yongbin Wang, Zhengtao Jiang

Shimin Liu

Tushar Kanti Saha, Takeshi Koshiba

Thai-Hung Nguyen, Kok‐Seng Wong, Thomas Oikonomou

Private integer comparison has been an essential computation function for many applications, including online auction, credential identification, data mining, and joint bidding. In the setting of two-party computation, two parties with private inputs (x and y) want to jointly compare them without revealing the value of those inputs to others (also known as the Millionaires’ problem) while the output should ensure correctness and preserve data privacy. The private inputs only can be revealed if they are equal, i.e., x = y. Many related works have been proposed to solve the integer comparison problem in various settings, focusing on different properties such as round and computation complexity. Most solutions decompose integers into bitwise representation and then securely evaluate the function in a Boolean circuit on encrypted bits. However, this type of solution is costly (especially for large integers) as each bit requires encryption and decryption. In this paper, we transform the private integer comparison into a block comparison problem. In particular, we employ a block vectorization mechanism to encode the private inputs into blocks. We show the security of our two-party protocol in the semi-honest model. Also, we implement the protocol to demonstrate its efficiency using block vectorization mechanism and homomorphic encryption. The experimental result proves that our proposed solution achieves high efficiency, particularly for large integer comparisons.

Xin Liu, Shundong Li, Jian Liu +2 more

Private comparison is fundamental to secure multiparty computation. In this study, we propose novel protocols to privately determine [Formula: see text], or [Formula: see text] in one execution. First, a 0-1-vector encoding method is introduced to encode a number into a vector, and the Goldwasser-Micali encryption scheme is used to compare integers privately. Then, we propose a protocol by using a geometric method to compare rational numbers privately, and the protocol is information-theoretical secure. Using the simulation paradigm, we prove the privacy-preserving property of our protocols in the semi-honest model. The complexity analysis shows that our protocols are more efficient than previous solutions.

Geoffroy Couteau