Paper 2024/1268
Improved YOSO Randomness Generation with Worst-Case Corruptions
Abstract
We study the problem of generating public unbiased randomness in a distributed manner within the recent You Only Speak Once (YOSO) framework for stateless multiparty computation, introduced by Gentry et al. in CRYPTO 2021. Such protocols are resilient to adaptive denial-of-service attacks and are, by their stateless nature, especially attractive in permissionless environments. While most works in the YOSO setting focus on independent random corruptions, we consider YOSO protocols with worst-case corruptions, a model introduced by Nielsen et al. in CRYPTO 2022. Prior work on YOSO public randomness generation with worst-case corruptions designed information-theoretic protocols for $t$ corruptions with either $n=6t+1$ or $n=5t$ roles, depending on the adversarial network model. However, a major drawback of these protocols is that their communication and computational complexities scale exponentially with $t$. In this work, we complement prior inefficient results by presenting and analyzing simple and efficient protocols for YOSO public randomness generation secure against worst-case corruptions in the computational setting. Our first protocol is based on publicly verifiable secret sharing and uses $n=3t+2$ roles. Since this first protocol requires setup and somewhat heavy cryptographic machinery, we also provide a second lighter protocol based on ElGamal commitments and verifiable secret sharing which uses $n=5t+4$ or $n=4t+4$ roles depending on the underlying network model. We demonstrate the practicality of our second protocol by showing experimental evaluations, significantly improving over prior proposed solutions for worst-case corruptions, especially in terms of transmitted data size.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. Financial Cryptography and Data Security 2024
- Keywords
- randomness generationyosoworst-case corruptions
- Contact author(s)
-
chen-da liuzhang @ hslu ch
elisawem @ andrew cmu edu
jribeiro @ tecnico ulisboa pt
psoni @ cs utah edu
aravind thyagarajan @ sydney edu au - History
- 2024-08-15: revised
- 2024-08-09: received
- See all versions
- Short URL
- https://ia.cr/2024/1268
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1268, author = {Chen-Da Liu-Zhang and Elisaweta Masserova and João Ribeiro and Pratik Soni and Sri AravindaKrishnan Thyagarajan}, title = {Improved {YOSO} Randomness Generation with Worst-Case Corruptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1268}, year = {2024}, url = {https://eprint.iacr.org/2024/1268} }