Start Over

On the Bottleneck Complexity of MPC with Correlated Randomness

Authors :: Orlandi, Claudio
Ravi, Divya
Scholl, Peter
Hanaoka, Goichiro
Shikata, Junji
Watanabe, Yohei
Source :: Orlandi, C, Ravi, D & Scholl, P 2022, On the Bottleneck Complexity of MPC with Correlated Randomness . in G Hanaoka, J Shikata & Y Watanabe (eds), Public-Key Cryptography – PKC 2022 : 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8–11, 2022, Proceedings, Part I . Springer, Cham, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13177 LNCS, pp. 194-220, 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2022, Virtual, Online, 08/03/2022 . https://doi.org/10.1007/978-3-030-97121-2_8
Publication Year :: 2022
Publisher :: Springer, 2022.
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.

Subjects :: Computer Science::Cryptography and Security

Details

Language :: English
Database :: OpenAIRE
Journal :: Orlandi, C, Ravi, D & Scholl, P 2022, On the Bottleneck Complexity of MPC with Correlated Randomness . in G Hanaoka, J Shikata & Y Watanabe (eds), Public-Key Cryptography – PKC 2022 : 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8–11, 2022, Proceedings, Part I . Springer, Cham, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13177 LNCS, pp. 194-220, 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2022, Virtual, Online, 08/03/2022 . https://doi.org/10.1007/978-3-030-97121-2_8
Accession number :: edsair.pure.au.......ac5685a77d5605e5c26fc8d9ed029e53
Full Text :: https://doi.org/10.1007/978-3-030-97121-2_8