Asynchronous YOSO a la Paillier

Ivan Bjerre Damgård; Simon Holmgaard Kamp; Julian Loss; Jesper Buus Nielsen

Paper 2025/128

Asynchronous YOSO a la Paillier

Ivan Bjerre Damgård, Aarhus University

Simon Holmgaard Kamp, Helmholtz Center for Information Security

Julian Loss, Helmholtz Center for Information Security

Jesper Buus Nielsen, Aarhus University

Abstract

We present the first complete adaptively secure asynchronous MPC protocol for the YOSO (You Speak Only Once) setting. In contrast to many previous MPC constructions in the YOSO model, we provide a full stack implementation that does MPC, role assignment and total order broadcast. Therefore, our construction is also the first to provide adaptively secure asynchronous total order broadcast and MPC that is sub-quadratic in the number of parties and does not require threshold fully homomorphic encryption. Instead, our protocols rely on threshold additively homomorphic Paillier encryption. Our total-order broadcast protocol has complexity optimal in the message length. This optimality also implies that the amortized complexity of handling a secure multiplication is linear in the number of parties.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Contact author(s): ivan @ cs au dk
simon kamp @ cispa de
lossjulian @ gmail com
jbn @ cs au dk
History: 2025-02-14: revised; 2025-01-27: received; See all versions
Short URL: https://ia.cr/2025/128
License: CC BY

BibTeX

@misc{cryptoeprint:2025/128,
      author = {Ivan Bjerre Damgård and Simon Holmgaard Kamp and Julian Loss and Jesper Buus Nielsen},
      title = {Asynchronous {YOSO} a la Paillier},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/128},
      year = {2025},
      url = {https://eprint.iacr.org/2025/128}
}