### Rabbit: Efficient Comparison for Secure Multi-Party Computation

Eleftheria Makri, Dragos Rotaru, 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).

Note: Minor typos fixed

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. Financial Cryptography and Data Security 2021 (FC 2021)
Keywords
Secure ComparisonMulti-party ComputationUnconditional SecurityDishonest Majority
Contact author(s)
emakri @ esat kuleuven be
dragos @ capeprivacy com
frederik vercauteren @ kuleuven be
swagh @ berkeley edu
History
2021-04-02: revised
See all versions
Short URL
https://ia.cr/2021/119

CC BY

BibTeX

@misc{cryptoeprint:2021/119,
author = {Eleftheria Makri and Dragos Rotaru and Frederik Vercauteren and Sameer Wagh},
title = {Rabbit: Efficient Comparison for Secure Multi-Party Computation},
howpublished = {Cryptology ePrint Archive, Paper 2021/119},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/119}},
url = {https://eprint.iacr.org/2021/119}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.