An efficient solution to the millionaires' problem based on homomorphic encryption

Hsiao Ying Lin*, Wen-Guey Tzeng

*Corresponding author for this work

Research output: Contribution to journalConference article

107 Scopus citations


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.

Original languageEnglish
Pages (from-to)456-466
Number of pages11
JournalLecture Notes in Computer Science
StatePublished - 17 Oct 2005
EventThird International Conference on Applied Cryptography and Network Security, ACNS 2005 - New York, NY, United States
Duration: 7 Jun 200510 Jun 2005


  • Secure computation
  • The greater than problem
  • The socialist millionaires' problem homomorphic encryption

Fingerprint Dive into the research topics of 'An efficient solution to the millionaires' problem based on homomorphic encryption'. Together they form a unique fingerprint.

  • Cite this