International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

An Efficient Solution to The Millionaires' Problem Based on Homomorphic Encryption

Authors:
Hsiao-Ying Lin
Wen-Guey Tzeng
Download:
URL: http://eprint.iacr.org/2005/043
Search ePrint
Search Google
Abstract: We proposed a two-round protocol for solving the Millionaires' Problem in the setting of semi-honest parties. Our protocol uses either multiplicative or additive homomorphic encryptions. Previously proposed protocols used additive or XOR homomorphic encryption schemes only. The computation and communication costs of our protocol are in the same asymptotic order as those of the other efficient protocols. Nevertheless, since multiplicative homomorphic encryption scheme is more efficient than an additive one practically, our construction saves computation time and communication bandwidth in practicality.
BibTeX
@misc{eprint-2005-12381,
  title={An Efficient Solution to The Millionaires' Problem Based on Homomorphic Encryption},
  booktitle={IACR Eprint archive},
  keywords={secure computation, the greater than problem, the socialist millionaires' problem, homomorphic encryption},
  url={http://eprint.iacr.org/2005/043},
  note={This work appears in ACNS 2005. lrain.cis92g@nctu.edu.tw 13200 received 17 Feb 2005, last revised 20 Feb 2006},
  author={Hsiao-Ying Lin and Wen-Guey Tzeng},
  year=2005
}