Adaptively Secure (Aggregatable) PVSS from Standard Assumptions

Publicly verifiable secret sharing (PVSS) is a fundamental primitive in threshold cryptography that allows a dealer to share a secret $S$ among a set of $n$ parties via a publicly verifiable transcript. Any subset of $t+1$ parties can then use their individual shares to reconstruct the full secret $S$, whereas $t$ or fewer shares give no information about $S$. As such, the secret $S$ remains hidden from an adversary that corrupts up to $t$ parties. Recently, Bacho and Loss (CCS 2023) gave the first proof of any PVSS scheme under an adaptive adversary. However, their security proof relies on strong and non-standard assumptions such as the algebraic group model (AGM) and the hardness of the one-more discrete logarithm (OMDL) problem. In particular, any protocol (e.g., distributed randomness beacon or distributed key generation) that makes use of a PVSS scheme either inherits these limitations or is not provably adaptively secure.

In this work, we present for the first time an adaptively secure PVSS scheme from well-established assumptions. In more detail, we provide two PVSS schemes with different properties. Our first scheme works over any pairing-free cyclic group and its security relies on the decisional Diffie-Hellman (DDH) assumption. Our second scheme works over an asymmetric pairing group, its security relies on the DDH and the co-computational Diffie-Hellman (co-CDH) assumption, and has the particularly valuable feature of aggregatability, which allows the aggregation of multiple PVSS transcripts into a single transcript while preserving verifiability. Notably, both our schemes are highly efficient, non-interactive, and work in the established plain public key model. These properties along with their provable adaptive security make them suitable candidates as building block in higher-level distributed protocols that aim to minimize communication.