Efficient Two-Party Integer Comparison With Block Vectorization Mechanism

Thai-Hung Nguyen, Kok-Seng Wong, Thomas OikonomouIEEE Access 2021 · OpenReview

Abstract

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 ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$y$ </tex-math></inline-formula> ) 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., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$x=y$ </tex-math></inline-formula> . 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.
BibTeX
@inproceedings{nguyen2021efficient,
  author = {Thai-Hung Nguyen and Kok-Seng Wong and Thomas Oikonomou},
  title = {{Efficient Two-Party Integer Comparison With Block Vectorization Mechanism}},
  booktitle = {IEEE Access},
  year = {2021},
  url = {https://openreview.net/forum?id=jVRcj0yH9-},
}

Loading related content...

Figure