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.
Category / Keywords: cryptographic protocols / Two-party computation, Secure comparison, Oblivious transfer Date: received 31 May 2016, last revised 8 Apr 2018 Contact author: geoffroy couteau at ens fr Available format(s): PDF | BibTeX Citation Version: 20180408:164842 (All versions of this report) Short URL: ia.cr/2016/544 Discussion forum: Show discussion | Start new discussion