Paper 2023/1934
More efficient comparison protocols for MPC
Abstract
In 1982, Yao introduced the problem of comparing two private values, thereby launching the study of protocols for secure multi-party computation (MPC). Since then, comparison protocols have undergone extensive study and found widespread applications. We survey state-of-the-art comparison protocols for an arbitrary number of parties, decompose them into smaller primitives and analyse their communication complexity under the usual assumption that the underlying MPC protocol does preprocessing and computes linear operations without communication. We then develop two new comparison protocols and explain why they are faster than similar protocols, including those that are commonly used in practice: they reduce the number of online multiplications, without increasing preprocessing or round complexity. More concretely, online bandwidth is reduced by more than half for the standard comparison protocols whose round complexity is logarithmic in the bit-length, whereas for constant round comparison protocols the reduction is two-thirds.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- MPCMultiparty ComputationSecure Comparison
- Contact author(s)
-
wicher malten @ nillion com
memo @ nillion com
miguel @ nillion com - History
- 2023-12-21: approved
- 2023-12-20: received
- See all versions
- Short URL
- https://ia.cr/2023/1934
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1934,
author = {Wicher Malten and Mehmet Ugurbil and Miguel de Vega},
title = {More efficient comparison protocols for {MPC}},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1934},
year = {2023},
url = {https://eprint.iacr.org/2023/1934}
}
