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

Hsiao Ying Lin; Wen-Guey Tzeng

doi:10.1007/11496137_31

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

Hsiao Ying Lin^*, Wen-Guey Tzeng

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to journal › Conference article › peer-review

189 Scopus citations

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.

Original language	English
Pages (from-to)	456-466
Number of pages	11
Journal	Lecture Notes in Computer Science
Volume	3531
DOIs	https://doi.org/10.1007/11496137_31
State	Published - 2005
Event	Third International Conference on Applied Cryptography and Network Security, ACNS 2005 - New York, NY, United States Duration: 7 Jun 2005 → 10 Jun 2005

Keywords

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

Access to Document

10.1007/11496137_31

Cite this

@article{f22c0e1118924b9fa332ff5d044fe28e,

title = "An efficient solution to the millionaires' problem based on homomorphic encryption",

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.",

keywords = "Secure computation, The greater than problem, The socialist millionaires' problem homomorphic encryption",

author = "Lin, {Hsiao Ying} and Wen-Guey Tzeng",

year = "2005",

doi = "10.1007/11496137_31",

language = "English",

volume = "3531",

pages = "456--466",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "Third International Conference on Applied Cryptography and Network Security, ACNS 2005 ; Conference date: 07-06-2005 Through 10-06-2005",

}

TY - JOUR

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

AU - Lin, Hsiao Ying

AU - Tzeng, Wen-Guey

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - Secure computation

KW - The greater than problem

KW - The socialist millionaires' problem homomorphic encryption

UR - http://www.scopus.com/inward/record.url?scp=26444581774&partnerID=8YFLogxK

U2 - 10.1007/11496137_31

DO - 10.1007/11496137_31

M3 - Conference article

AN - SCOPUS:26444581774

SN - 0302-9743

VL - 3531

SP - 456

EP - 466

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - Third International Conference on Applied Cryptography and Network Security, ACNS 2005

Y2 - 7 June 2005 through 10 June 2005

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this