Paper 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 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.
Metadata
- Available format(s)
-
PDF
PS
- Publication info
- Published elsewhere. This work appears in ACNS 2005.
- Keywords
- secure computationthe greater than problemthe socialist millionaires' problemhomomorphic encryption
- Contact author(s)
- lrain cis92g @ nctu edu tw
- History
- 2006-02-21: revised
- 2005-02-21: received
- See all versions
- Short URL
- https://ia.cr/2005/043
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/043,
author = {Hsiao-Ying Lin and Wen-Guey Tzeng},
title = {An Efficient Solution to The Millionaires' Problem Based on Homomorphic Encryption},
howpublished = {Cryptology {ePrint} Archive, Paper 2005/043},
year = {2005},
url = {https://eprint.iacr.org/2005/043}
}
