Paper 2023/1348

Adaptively Secure (Aggregatable) PVSS and Application to Distributed Randomness Beacons

Renas Bacho, CISPA Helmholtz Center for Information Security, Universität des Saarlandes
Julian Loss, CISPA Helmholtz Center for Information Security
Abstract

Publicly Verifiable Secret Sharing (PVSS) is a fundamental primitive that allows to share a secret $S$ among $n$ parties via a publicly verifiable transcript $T$. Existing (efficient) PVSS are only proven secure against static adversaries who must choose who to corrupt ahead of a protocol execution. As a result, any protocol (e.g., a distributed randomness beacon) that builds on top of such a PVSS scheme inherits this limitation. To overcome this barrier, we revisit the security of PVSS under adaptive corruptions and show that, surprisingly, many protocols from the literature already achieve it in a meaningful way: - We propose a new security definition for aggregatable PVSS, i.e., schemes that allow to homomorphically combine multiple transcripts into one compact aggregate transcript $AT$ that shares the sum of their individual secrets. Our notion captures that if the secret shared by $AT$ contains at least one contribution from an honestly generated transcript, it should not be predictable. We then prove that several existing schemes satisfy this notion against adaptive corruptions in the algebraic group model. - To motivate our new notion, we show that it implies the adaptive security of two recent random beacon protocols, SPURT (S&P '22) and OptRand (NDSS '23), who build on top of aggregatable PVSS schemes satisfying our notion of unpredictability. For a security parameter $\lambda$, our result improves the communication complexity of the best known adaptively secure random beacon protocols to $O(\lambda n^2)$ for synchronous networks with $t<n/2$ corruptions and partially synchronous networks with $t<n/3$ corruptions.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACM CCS 2023
DOI
10.1145/3576915.3623106
Keywords
Adaptive SecurityRandomness BeaconAggregatable PVSSPairing-Based Cryptography
Contact author(s)
renas bacho @ cispa de
loss @ cispa de
History
2023-09-11: revised
2023-09-09: received
See all versions
Short URL
https://ia.cr/2023/1348
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1348,
      author = {Renas Bacho and Julian Loss},
      title = {Adaptively Secure (Aggregatable) {PVSS} and Application to Distributed Randomness Beacons},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1348},
      year = {2023},
      doi = {10.1145/3576915.3623106},
      url = {https://eprint.iacr.org/2023/1348}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.