Cryptology ePrint Archive: Report 2021/119

Rabbit: Efficient Comparison for Secure Multi-Party Computation

Eleftheria Makri and Dragos Rotaru and Frederik Vercauteren and Sameer Wagh

Abstract: Secure comparison has been a fundamental challenge in privacy-preserving computation, since its inception as the Yao's millionaires' problem (FOCS 1982). In this work, we present a novel construction for general n-party private comparison, secure against an active adversary, in the dishonest majority setting. For the case of comparisons over fields, our protocol is more efficient than the best prior work (edaBits: Crypto 2020), with ~1.5x better throughput in most adversarial settings, over 2.3x better throughput in particular in the passive, honest majority setting, and lower communication. Our comparisons crucially eliminate the need for bounded inputs as well as the need for statistical security that prior works require. An important consequence of removing this "slack" (a gap between the bit-length of the input and the MPC representation) is that multi-party computation (MPC) protocols can be run in a field of smaller size, reducing the overhead incurred by privacy-preserving computations. We achieve this novel construction using the commutative nature of addition over rings and fields. This makes the protocol both simple to implement and highly efficient and we provide an implementation in MP-SPDZ (CCS 2020).

Category / Keywords: cryptographic protocols / Secure Comparison, Multi-party Computation, Unconditional Security, Dishonest Majority

Original Publication (in the same form): Financial Cryptography and Data Security 2021 (FC 2021)

Date: received 1 Feb 2021, last revised 1 Apr 2021

Contact author: emakri at esat kuleuven be, dragos at capeprivacy com, frederik vercauteren at kuleuven be, swagh at berkeley edu

Available format(s): PDF | BibTeX Citation

Note: Minor typos fixed

Version: 20210402:024720 (All versions of this report)

Short URL: ia.cr/2021/119


[ Cryptology ePrint archive ]