Asynchronous Verifiable Secret Sharing

Summary

Asynchronous Verifiable Secret Sharing (AVSS) is a Secret Sharing protocol that provides verifiability in an asynchronous network, where messages can be delayed arbitrarily and there are no timing assumptions. A dealer shares a secret among $n$ parties such that (1) shareholders can verify their shares are consistent, (2) the protocol terminates despite asynchrony, and (3) a corrupted dealer cannot cause honest parties to reconstruct different values.

First introduced by Canetti and Rabin [1] as a building block for asynchronous Byzantine agreement. The formalization below follows Cachin et al. [2].

Formal Definition

An $n$-player protocol $(\mathsf{Sh}, \mathsf{Rec})$ is $(1 - ε)$-correct, $t$-resilient AVSS if the following hold for every $t$-adversary, where the dealer's input is $s \in S$ for some finite globally known set $S$:

Completion. With probability $1 - \epsilon$:

If the dealer is uncorrupted throughout $\mathsf{Sh}$, then all uncorrupted players eventually output "sharing succeeded."
If some uncorrupted player outputs "sharing succeeded," then all uncorrupted players eventually output "sharing succeeded."
If the uncorrupted players output "sharing succeeded" and all uncorrupted players have "start running $\mathsf{Rec}$" on their input tapes, then all uncorrupted players eventually complete both $\mathsf{Sh}$ and $\mathsf{Rec}$.

Correctness. Once some uncorrupted player outputs "sharing succeeded," there exists a fixed value $r$ such that with probability $1 - \epsilon$:

Each uncorrupted player outputs $r$ upon completion of $\mathsf{Rec}$ (i.e., $r$ is the reconstructed secret).
If the dealer is uncorrupted throughout $\mathsf{Sh}$, then $r = s$.

Secrecy. Let $\mathsf{VIEW}(s)$ denote the random variable over the random inputs of the players describing the adversary's view of an execution of $\mathsf{Sh}$ where the dealer has input $s$. If the dealer is uncorrupted throughout, then the distribution of $\mathsf{VIEW}(s)$ is the same for all values $s \in S$.

Thresholds

Low-threshold AVSS

The reconstruction threshold $t_r$ satisfies $t_r = t + 1$ (i.e., $t + 1$ shares suffice to reconstruct), where $t < n/3$ is the corruption threshold. This means $n - t$ honest parties always hold enough shares to reconstruct, which simplifies protocol design. Most early AVSS constructions (e.g., [2]) are low-threshold.

High-threshold AVSS

The reconstruction threshold $t_r$ satisfies $t_r = n - t$ (i.e., all $n - t$ honest parties are needed). This provides stronger secrecy since the adversary corrupting $t$ parties learns nothing even though it holds $t$ shares, since $t < t_r = n - t$. High-threshold AVSS is needed for applications like threshold signatures and DKG where stronger secrecy is required.

The challenge: in the asynchronous setting, the dealer can only wait for $n - t$ responses. With high threshold $t_r = n - t$, the $t$ parties that didn't respond might include honest-but-slow parties whose shares are needed for reconstruction. Techniques to address this include:

Bivariate polynomials: parties that received shares can help recover shares for slow parties [3].
Dual-threshold schemes: use a bivariate polynomial $\phi(x,y)$ of degree $p$ in $x$ and $t$ in $y$, with $p - t + 1$ secrets packed along the $x$-axis. The protocol supports two reconstruction modes: full reconstruction of all secrets requires $p + 1$ parties (high threshold), while reconstruction of a single secret requires only $t + 1$ parties (low threshold) [4].
Elastic thresholds: allow the reconstruction threshold to vary between $t + 1$ and $n - t$ [5].

Constructions

Bivariate polynomial-based

Uses a Bivariate polynomial based secret sharing $f(x,y)$ of degree $k - 1$ in each variable with $f(0,0) = s$. Each party receives both a row $f(i, y)$ and a column $f(x, i)$. Cross-checking works because both slices evaluate to the same point $f(i, j)$. Two variants:

Information-theoretic (BGW) [6]: synchronous setting. Verification via a complaint round: parties publicly expose inconsistencies, and if $\leq t$ complaints, the $t + 1$ satisfied honest parties uniquely determine $f$. Achieves unconditional security.
Computational (Cachin et al.) [2]: asynchronous setting. See detailed description below.

Cachin et al.'s AVSS protocol

The Bivariate polynomial based secret sharing secret sharing scheme assumes a trusted dealer and synchronous communication. Cachin et al. extend it to the asynchronous setting using two additional tools: Pedersen commitments and Bracha's reliable broadcast.

Pedersen commitments for verification
The core problem: how does a party verify that its row and column polynomials are consistent with everyone else's, without seeing anyone else's shares?

The dealer publishes a commitment matrix $\mathbf{C}$, where:

\[C_{jl} = g^{f_{jl}} h^{f'_{jl}} \quad \text{for } j, l \in [0, k-1]\]

Here $f$ is the bivariate polynomial encoding the secret, $f'$ is a second random polynomial (for hiding), and $g, h$ are generators of a group where discrete log is hard (with $\log_g h$ unknown to all parties).

Each party $P_i$ can verify its row polynomial $r_i(y) = f(i, y)$ against $\mathbf{C}$ by checking:

\[g^{r_i(l)} h^{r'_i(l)} = \prod_{j=0}^{k-1} (C_{jl})^{i^j} \quad \text{for each } l\]

This works because $\prod_j C_{jl}^{i^j} = \prod_j g^{f_{jl} i^j} h^{f'_{jl} i^j} = g^{\sum_j f_{jl} i^j} h^{\sum_j f'_{jl} i^j} = g^{f(i, \omega^l)} h^{f'(i, \omega^l)}$.

Key properties of Pedersen commitments:
- Perfectly hiding: $C_{00} = g^s h^{s'}$ reveals nothing about $s$, because for any $\tilde{s}$ there exists a unique $\tilde{s}'$ with $C_{00} = g^{\tilde{s}} h^{\tilde{s}'}$. This gives unconditional privacy.
- Computationally binding: finding two openings $(s, s')$ and $(\tilde{s}, \tilde{s}')$ for the same commitment requires computing $\log_g h$. This gives computational correctness.
Degree enforcement via commitments

The commitment matrix $\mathbf{C}$ has dimensions $k \times k$ (for degree $k - 1$). A party verifies that its row polynomial has degree $\leq k - 1$ by checking it against $\mathbf{C}$. A higher-degree polynomial would require a larger commitment matrix, so the fixed size of $\mathbf{C}$ enforces the degree bound.
Bracha's reliable broadcast for agreement
In the asynchronous setting, the dealer sends $\mathbf{C}$ along with each party's shares. The parties use Bracha's three-phase broadcast to agree on $\mathbf{C}$:
1. send: the dealer sends $\mathbf{C}$, row $r_i$, and column $c_i$ to each party $P_i$.
2. echo: upon receiving a valid send message, $P_i$ sends an echo message to all parties containing $\mathbf{C}$ and the cross-check values $r_i(j), c_i(j)$ for each $P_j$.
3. ready: upon receiving $\lceil \frac{n+t+1}{2} \rceil$ valid echo messages with the same $\mathbf{C}$, $P_i$ interpolates its row and column from the received points and sends a ready message.
4. completion: upon receiving $k + t$ valid ready messages with the same $\mathbf{C}$, $P_i$ completes the sharing.
Lemma (Cachin et al.): if two honest servers send ready messages, they agree on the same $\mathbf{C}$. This ensures all honest parties commit to the same polynomial.
Security properties
- Correctness (computational): relies on the binding property of Pedersen commitments. If two honest parties reconstruct different values, one can compute $\log_g h$, contradicting the discrete log assumption.
- Privacy (unconditional): relies on the perfect hiding of Pedersen commitments. For any $\tilde{s}$, there exist polynomials $\tilde{f}, \tilde{f}'$ consistent with the adversary's view (rows, columns, and $\mathbf{C}$) such that $\tilde{f}(0,0) = \tilde{s}$.
- Resilience: $n > 3t$ (optimal for asynchronous protocols).
- Complexity: $O(n^2)$ messages, $O(\kappa n^3)$ communication.

Polynomial commitment-based

Replace the bivariate polynomial with a univariate polynomial plus a polynomial commitment (e.g., KZG [7]). The dealer commits to the sharing polynomial and broadcasts the commitment. Each party verifies its share against the commitment without pairwise cross-checks, reducing communication. Backes et al. [8] achieve $O(\kappa n^2)$ communication. This shifts from information-theoretic to computational security.

Erasure coding-based

Use erasure codes to encode shares so that any $n - t$ encoded fragments suffice to recover the polynomial. Combined with hash-based verification (Merkle trees), this avoids expensive public-key operations per share. Used by Yurek et al. [9] (hbACSS) for efficient batched sharing.

Optimistic AVSS

Assumes a common-case where the dealer is honest and the network is well-behaved. In the optimistic path, the protocol terminates in fewer rounds and with lower communication (e.g., 2 rounds). Falls back to a pessimistic path when faults are detected. Shrestha et al. [10] apply optimistic reliable broadcast to build optimistic AVSS.

Variants

Asynchronous Complete Secret Sharing (ACSS): strengthens AVSS by additionally requiring that every honest party eventually outputs a share, even if the dealer is corrupt (the protocol "completes" with some well-defined secret). Used as the main building block in ADKG protocols [9].
Long-message AVSS: standard AVSS shares a single field element. Long-message AVSS shares a secret of size $\ell \gg \kappa$ (e.g., a large file or batch of secrets) with amortized communication cost $O(n \ell + n^2 \kappa)$ rather than $O(n \ell \kappa)$ from running $\ell / \kappa$ independent instances.
Batched AVSS: multiple dealers share secrets concurrently; communication is amortized across instances. Groth and Shoup [11] use super-invertible matrices for efficient batching.

Bounds

Requires $n \geq 3t + 1$ (optimal resilience for asynchronous protocols with $t$ Byzantine faults), matching the bound for asynchronous Byzantine agreement [6].
Communication lower bound: $\Omega(n^2 \kappa)$ for sharing a single $κ$-bit secret, since each of the $n$ parties must receive $\Omega(n \kappa)$ bits to guarantee reconstruction despite $t$ faults.
Cachin et al. [2]: $O(n^3 \kappa)$ communication (bivariate polynomial with Pedersen commitments, computational security).
Backes et al. [8]: $O(n^2 \kappa)$ communication (polynomial commitments, computational security).
AlHaddad et al. [3]: $O(n^2 \kappa)$ communication for high-threshold AVSS.

Applications

Asynchronous Byzantine agreement [1] – AVSS was originally introduced as a building block for constant-expected-time asynchronous BA with optimal resilience $t < n/3$.
Asynchronous distributed key generation (ADKG) – generating a shared public key without a trusted dealer in an asynchronous network [12].
Proactive secret sharing and proactive cryptosystems – periodically refreshing shares in an asynchronous network so that an adversary must corrupt $t$ parties within a single epoch [2].
Asynchronous random beacons – producing unpredictable, bias-resistant randomness in asynchronous protocols.

References

[1] Ran Canetti, and Tal Rabin. 1993. “Fast asynchronous Byzantine agreement with optimal resilience.” https://dl.acm.org/doi/10.1145/167088.167105.

[2] Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, and Reto Strobl. 2002. “Asynchronous verifiable secret sharing and proactive cryptosystems.” http://portal.acm.org/citation.cfm?doid=586110.586124.

[3] Nicolas AlHaddad, Mayank Varia, and Haibin Zhang. 2021. “High-Threshold AVSS with Optimal Communication Complexity.” https://link.springer.com/10.1007/978-3-662-64331-0_25.

[4] Nicolas Alhaddad, Mayank Varia, and Ziling Yang. 2024. “Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications.” https://eprint.iacr.org/2024/326.

[5] Junming Li, Zhi Lu, Renfei Shen, Yuanqing Feng, and Songfeng Lu. 2024. “Asynchronous Verifiable Secret Sharing with Elastic Thresholds and Distributed Key Generation.” https://eprint.iacr.org/2024/1463.

[6] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. “Completeness theorems for non-cryptographic fault-tolerant distributed computation.” https://dl.acm.org/doi/10.1145/62212.62213.

[7] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. 2010. “Constant-Size Commitments to Polynomials and Their Applications.” http://link.springer.com/10.1007/978-3-642-17373-8_11.

[8] Michael Backes, Amit Datta, and Aniket Kate. 2013. “Asynchronous Computational VSS with Reduced Communication Complexity.” http://link.springer.com/10.1007/978-3-642-36095-4_17.

[9] Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, and Andrew Miller. 2021. “hbACSS: How to Robustly Share Many Secrets.”

[10] Nibesh Shrestha, Qianyu Yu, Aniket Kate, Giuliano Losa, Kartik Nayak, and Xuechao Wang. 2025. “Optimistic, Signature-Free Reliable Broadcast and Its Applications.” http://arxiv.org/abs/2505.02761.

[11] Jens Groth, and Victor Shoup. 2023. “Fast batched asynchronous distributed key generation.” https://eprint.iacr.org/2023/1175.

[12] Eleftherios Kokoris Kogias, Dahlia Malkhi, and Alexander Spiegelman. 2020. “Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.” https://dl.acm.org/doi/10.1145/3372297.3423364.