Verifiable Secret Sharing (VSS)

The dealer publishes a cryptographic commitment to the secret polynomial. This binding value allows any participant to verify that their received share is a valid evaluation of that specific polynomial without revealing the secret itself.

• Pedersen Commitments: Provide information-theoretic hiding and computational binding, often used in discrete log settings.
• Feldman's Scheme: Uses homomorphic properties of exponentiation to enable public verifiability, allowing any external party to check share validity.

Each participant can independently verify that their share is consistent with the dealer's public commitment. This prevents a dealer from distributing shares that lie on different polynomials, which would cause reconstruction to fail or produce an incorrect secret.

• Non-interactive verification: A participant checks a single equation using their share and the public commitment.
• Complaint resolution: If a share fails verification, the participant broadcasts a complaint, forcing the dealer to reveal the correct share publicly.

VSS guarantees that any qualified subset of shares (meeting the threshold) will reconstruct the same unique secret originally committed to by the dealer. This property is critical for distributed key generation and consensus protocols.

• Binding property: The dealer cannot later claim a different secret was shared.
• Deterministic recovery: Lagrange interpolation on any valid threshold set yields the identical secret.

VSS schemes offer different security guarantees depending on the underlying cryptographic assumptions.

• Information-theoretic VSS: Provides unconditional security against unbounded adversaries but typically requires private channels and a broadcast channel.
• Computational VSS: Relies on hardness assumptions like the discrete logarithm problem, enabling public verifiability and efficiency in asynchronous networks.

In real-world distributed networks, messages can be arbitrarily delayed. AVSS protocols ensure termination and correctness without relying on timing assumptions.

• Eventually completes: The protocol guarantees that all honest participants eventually output a consistent secret even under adversarial scheduling.
• Critical for blockchains: AVSS forms the backbone of Distributed Key Generation (DKG) in asynchronous consensus protocols like HoneyBadgerBFT.

VSS enables a proactive security model where shares are periodically refreshed without changing the underlying secret. This defends against mobile adversaries that slowly compromise participants over time.

• Share renewal: Participants jointly generate new random polynomials that sum to zero, adding the new shares to their existing ones.
• Old share invalidation: Compromised shares from previous epochs become useless, limiting the window of vulnerability.

The foundational primitive that VSS extends. A dealer splits a secret into multiple shares distributed among participants. Only a qualified subset (e.g., any t out of n parties) can reconstruct the original secret. Classic schemes like Shamir's Secret Sharing use polynomial interpolation, where the secret is the constant term of a random polynomial, and shares are points on that polynomial. Without verification, a malicious dealer can distribute inconsistent shares that yield different secrets or no secret at all—the exact vulnerability VSS was designed to eliminate.

A branch of cryptography where operations like decryption or digital signing require a minimum threshold of participants to collaborate. VSS is a critical building block for threshold systems, particularly in Distributed Key Generation (DKG) protocols. In a DKG, VSS ensures that each participant contributes to a shared public/private key pair without any single party ever knowing the full private key. This eliminates single points of failure and is fundamental to securing validator keys in proof-of-stake blockchains and distributed custody solutions.

A cryptographic primitive that allows a party to commit to a chosen value while keeping it hidden, with the ability to reveal it later. VSS relies on homomorphic commitments, such as Pedersen commitments, to bind the dealer to a consistent polynomial. The dealer publishes a commitment to the polynomial's coefficients. When a participant receives a share, they can verify it against the public commitment using the homomorphic property: the commitment to the share must equal the evaluation of the committed polynomial at the participant's index. This provides the 'verifiable' property without revealing the secret.

A protocol enabling a set of parties to jointly generate a cryptographic key pair without a trusted dealer. Each party runs a VSS instance to share a random secret. The final shared secret key is the sum of all valid, verified contributions. The corresponding public key is computed from the published commitments. DKG is essential for threshold signatures used in blockchain consensus mechanisms and for initializing secure multi-party computation clusters where no single node should ever hold a complete private key.

A cryptographic protocol enabling multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. VSS serves as a preprocessing primitive in many information-theoretic MPC protocols (e.g., BGW, CCD). In the SPDZ protocol family, VSS-like techniques are used to generate and distribute correlated randomness, such as Beaver triples, during an offline phase. This precomputation enables a highly efficient online phase where parties only need to broadcast masked values.

An extension of VSS designed for asynchronous networks where messages can be arbitrarily delayed and there is no global clock. In standard VSS, a dealer must wait for acknowledgments from participants. AVSS protocols guarantee termination and correctness even under these adversarial network conditions. This is critical for decentralized systems operating over the open internet, such as permissionless blockchains and geographically distributed MPC nodes, where timing assumptions cannot be reliably enforced.