Paper 2025/474

Black-Box Constant-Round Secure 2PC with Succinct Communication

Michele Ciampi, University of Edinburgh
Ankit Kumar Misra, University of California, Los Angeles
Rafail Ostrovsky, University of California, Los Angeles
Akash Shah, University of California, Los Angeles
Abstract

The most fundamental performance metrics of secure multi-party computation (MPC) protocols are related to the number of messages the parties exchange (i.e., round complexity), the size of these messages (i.e., communication complexity), and the overall computational resources required to execute the protocol (i.e., computational complexity). Another quality metric of MPC protocols is related to the black-box or non-black-box use of the underlying cryptographic primitives. Indeed, the design of black-box MPC protocols, other than being of theoretical interest, usually can lead to protocols that have better computational complexity. In this work, we aim to optimize the round and communication complexity of black-box secure multi-party computation in the plain model, by designing a constant-round two-party computation protocol in the malicious setting, whose communication complexity is only polylogarithmic in the size of the function being evaluated. We successfully design such a protocol, having only black-box access to fully homomorphic encryption, trapdoor permutations, and hash functions. To the best of our knowledge, our protocol is the first to make black-box use of standard cryptographic primitives while achieving almost asymptotically optimal communication and round complexity.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2025
Keywords
Two-party ComputationBlackbox
Contact author(s)
micheleciampi1990 @ gmail com
ankitkmisra @ g ucla edu
rafail @ cs ucla edu
akashshah08 @ g ucla edu
History
2025-03-14: approved
2025-03-12: received
See all versions
Short URL
https://ia.cr/2025/474
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/474,
      author = {Michele Ciampi and Ankit Kumar Misra and Rafail Ostrovsky and Akash Shah},
      title = {Black-Box Constant-Round Secure {2PC} with Succinct Communication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/474},
      year = {2025},
      url = {https://eprint.iacr.org/2025/474}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.