Paper 2016/544

New Protocols for Secure Equality Test and Comparison

Geoffroy Couteau

Abstract

Protocols for securely comparing private values are among the most fundamental building blocks of multiparty computation. Introduced by Yao under the name millionaire's problem, they have found numerous applications in a variety of privacy-preserving protocols; however, due to their inherent non-arithmetic structure, existing construction often remain an important bottleneck in large-scale secure protocols. In this work, we introduce new protocols for securely computing the greater-than and the equality predicate between two parties. Our protocols rely solely on the existence of oblivious transfer, and are UC-secure against passive adversaries. Furthermore, our protocols are well suited for use in large-scale secure computation protocols, where secure comparisons (SC) and equality tests (ET) are commonly used as basic routines: they perform particularly well in an amortized setting, and can be preprocessed efficiently (they enjoy an extremely efficient, information-theoretic online phase). We perform a detailed comparison of our protocols to the state of the art, showing that they improve over the most practical existing solutions regarding both communication and computation, while matching the asymptotic efficiency of the best theoretical constructions.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Two-party computationSecure comparisonOblivious transfer
Contact author(s)
geoffroy couteau @ ens fr
History
2018-04-08: last of 7 revisions
2016-06-01: received
See all versions
Short URL
https://ia.cr/2016/544
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/544,
      author = {Geoffroy Couteau},
      title = {New Protocols for Secure Equality Test and Comparison},
      howpublished = {Cryptology ePrint Archive, Paper 2016/544},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/544}},
      url = {https://eprint.iacr.org/2016/544}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.