Paper 2021/1594
On the Bottleneck Complexity of MPC with Correlated Randomness
Claudio Orlandi, Divya Ravi, and Peter Scholl
Abstract
At ICALP 2018, Boyle et al. introduced the notion of the bottleneck complexity of a secure multi-party computation (MPC) protocol. This measures the maximum communication complexity of any one party in the protocol, aiming to improve load-balancing among the parties. In this work, we study the bottleneck complexity of MPC in the preprocessing model, where parties are given correlated randomness ahead of time. We present two constructions of bottleneck-efficient MPC protocols, whose bottleneck complexity is independent of the number of parties: 1. A protocol for computing abelian programs, based only on one-way functions. 2. A protocol for selection functions, based on any linearly homomorphic encryption scheme. Compared with previous bottleneck-efficient constructions, our protocols can be based on a wider range of assumptions, and avoid the use of fully homomorphic encryption.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published by the IACR in PKC 2022
- Keywords
- Bottleneck complexityabelian programsgarbled circuitsadditively homomorphic encryption
- Contact author(s)
-
divya @ cs au dk
orlandi @ cs au dk
peter scholl @ cs au dk - History
- 2021-12-06: received
- Short URL
- https://ia.cr/2021/1594
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1594,
author = {Claudio Orlandi and Divya Ravi and Peter Scholl},
title = {On the Bottleneck Complexity of MPC with Correlated Randomness},
howpublished = {Cryptology ePrint Archive, Paper 2021/1594},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1594}},
url = {https://eprint.iacr.org/2021/1594}
}
