Paper 2021/119
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
Metadata
- Available format(s)
-
PDF
- 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
- 2021-02-05: received
- See all versions
- Short URL
- https://ia.cr/2021/119
- License
-
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}
}
