Paper 2024/1666

Computationally Efficient Asynchronous MPC with Linear Communication and Low Additive Overhead

Akhil Bandarupalli, Purdue University
Xiaoyu Ji, Tsinghua University
Aniket Kate, Purdue University & Supra Research
Chen-Da Liu-Zhang, Lucerne University of Applied Sciences and Arts & Web3 Foundation
Yifan Song, Tsinghua University and Shanghai Qi Zhi Institute
Abstract

We explore the setting of asynchronous multi-party computation (AMPC) with optimal resilience n=3t+1, and develop an efficient protocol that optimizes both communication and computation. The recent work by Goyal, Liu-Zhang, and Song [Crypto' 24] was the first to achieve AMPC with amortized linear communication cost without using computationally heavy public-key cryptography. However, its additive communication overhead renders it impractical for most real-world applications. It is possible to reduce the communication overhead significantly by leveraging cryptographic tools such as %random oracle hash, homomorphic commitments, public-key cryptography, or zero-knowledge proofs; however, the corresponding AMPC protocols introduce computation overhead of public-key cryptographic operations that become bottleneck as grows. Overall, achieving AMPC with linear communication complexity, low additive communication overhead, and low computation overhead remains an open challenge. In this work, we resolve this efficiency challenge by utilizing the random oracle model. By relying solely on computationally efficient primitives such as random oracle hash and symmetric-key cryptography, our protocol is not only efficient in terms of computation and communication overhead but also post-quantum secure. For a circuit with multiplication gates, our protocol achieves communication per multiplication gate with an additive overhead of communication. In terms of computation, our protocol only introduces an additive overhead of hash computations independent of the circuit size.

Note: Update to full paper

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
AsynchronousSecure Multi-party ComputationSecret SharingLightweight Cryptography
Contact author(s)
abandaru @ purdue edu
jixy23 @ mails tsinghua edu cn
aniket @ purdue edu
chen-da liuzhang @ hslu ch
yfsong @ mail tsinghua edu cn
History
2025-02-26: last of 2 revisions
2024-10-15: received
See all versions
Short URL
https://ia.cr/2024/1666
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1666,
      author = {Akhil Bandarupalli and Xiaoyu Ji and Aniket Kate and Chen-Da Liu-Zhang and Yifan Song},
      title = {Computationally Efficient Asynchronous {MPC} with Linear Communication and Low Additive Overhead},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1666},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1666}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.