[Resource Topic] 2021/119: Rabbit: Efficient Comparison for Secure Multi-Party Computation

Welcome to the resource topic for 2021/119

Rabbit: Efficient Comparison for Secure Multi-Party Computation

Authors: Eleftheria Makri, Dragos Rotaru, Frederik Vercauteren, Sameer Wagh


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

ePrint: https://eprint.iacr.org/2021/119

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .