TY - CHAP
T1 - Practical and Secure Solutions for Integer Comparison
T2 - Public Key Cryptography – PKC 2007
Y1 - 2007
A1 - Garay, Juan
A1 - Schoenmakers, Berry
A1 - Villegas, José
ED - Okamoto, Tatsuaki
ED - Wang, Xiaoyun
KW - homomorphic encryption
KW - Millionaires’ problem
KW - secure multi-party computation
AB - Yao’s classical millionaires’ problem is about securely determining whether x > y, given two input values x,y, which are held as private inputs by two parties, respectively. The output x > y becomes known to both parties. In this paper, we consider a variant of Yao’s problem in which the inputs x,y as well as the output bit x > y are encrypted. Referring to the framework of secure n-party computation based on threshold homomorphic cryptosystems as put forth by Cramer, Damgård, and Nielsen at Eurocrypt 2001, we develop solutions for integer comparison, which take as input two lists of encrypted bits representing x and y, respectively, and produce an encrypted bit indicating whether x > y as output. Secure integer comparison is an important building block for applications such as secure auctions. In this paper, our focus is on the two-party case, although most of our results extend to the multi-party case. We propose new logarithmic-round and constant-round protocols for this setting, which achieve simultaneously very low communication and computational complexities. We analyze the protocols in detail and show that our solutions compare favorably to other known solutions.
JF - Public Key Cryptography – PKC 2007
T3 - Lecture Notes in Computer Science
PB - Springer Berlin Heidelberg
VL - 4450
SN - 978-3-540-71676-1
UR - http://dx.doi.org/10.1007/978-3-540-71677-8_22
ER -