Cryptology ePrint Archive: Report 2005/043
An Efficient Solution to The Millionaires' Problem Based on Homomorphic Encryption
Hsiao-Ying Lin and Wen-Guey Tzeng
Abstract: We proposed a two-round protocol for solving the
Millionaires' Problem in the setting of semi-honest
Our protocol uses either multiplicative or additive
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.
Category / Keywords: secure computation, the greater than problem, the socialist millionaires' problem, homomorphic encryption
Publication Info: This work appears in ACNS 2005.
Date: received 17 Feb 2005, last revised 20 Feb 2006
Contact author: lrain cis92g at nctu edu tw
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20060221:010520 (All versions of this report)
Short URL: ia.cr/2005/043
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]