2023-1348.pdf (914.13 kB)

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

Download (914.13 kB)
conference contribution
posted on 2024-04-08, 08:36 authored by Renas BachoRenas Bacho, Julian LossJulian Loss
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 λ, our result improves the communication complexity of the best known adaptively secure random beacon protocols to O(λn2) for synchronous networks with t < n/2 corruptions and partially synchronous networks with t < n/3 corruptions.



Meng W ; Jensen CD ; Cremers C ; Kirda E

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM Conference on Computer and Communications Security (CCS)



Page Range



Association for Computing Machinery (ACM)

Open Access Type

  • Not Open Access


@conference{Bacho:Loss:2023, title = "Adaptively Secure (Aggregatable) PVSS and Application to Distributed Randomness Beacons", author = "Bacho, Renas" AND "Loss, Julian", editor = "Meng, Weizhi" AND "Jensen, Christian Damsgaard" AND "Cremers, Cas" AND "Kirda, Engin", year = 2023, month = 11, journal = "CCS", pages = "1791--1804", publisher = "Association for Computing Machinery (ACM)", doi = "10.1145/3576915.3623106" }