Cryptology ePrint Archive: Report 2021/1594

On the Bottleneck Complexity of MPC with Correlated Randomness

Claudio Orlandi and 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.

Category / Keywords: cryptographic protocols / Bottleneck complexity, abelian programs, garbled circuits, additively homomorphic encryption

Original Publication (in the same form): IACR-PKC-2022

Date: received 5 Dec 2021

Contact author: divya at cs au dk, orlandi at cs au dk, peter scholl at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20211206:035457 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]