Verifiable Secret Sharing (VSS)
Verifiable secret sharing lets participants confirm their key shares are consistent without revealing the shared secret.
Key Takeaways
- Verifiable secret sharing extends Shamir's secret sharing by letting each participant independently verify that their key share is consistent with everyone else's, without revealing the underlying secret.
- Two main constructions exist: Feldman's VSS publishes commitments to polynomial coefficients using a generator, while Pedersen's VSS adds a second randomizing polynomial to make commitments information-theoretically hiding.
- VSS is essential for secure distributed key generation: without it, a malicious participant could distribute inconsistent shares that silently corrupt the group key.
What Is Verifiable Secret Sharing?
Verifiable secret sharing (VSS) is a cryptographic protocol that splits a secret into multiple shares distributed among participants, with the added property that each participant can verify their share is correct. In plain Shamir's secret sharing, a dealer creates a random polynomial of degree t-1 (where t is the threshold), sets the secret as the constant term, and hands each participant a point on that curve. Any t participants can reconstruct the secret via Lagrange interpolation, while fewer than t learn nothing about it.
The problem with plain Shamir sharing is trust: participants must blindly trust that the dealer gave everyone valid, consistent shares. A dishonest dealer could hand out garbage values or give different participants shares from different polynomials. When the group later tries to reconstruct the secret or use their shares in a threshold signature, the result would be corrupted with no way to identify what went wrong.
VSS solves this by requiring the dealer to publish cryptographic commitments alongside the shares. Each participant checks their share against these public commitments, and if the check passes, they know their share is consistent with every other valid share. The verification happens without revealing the secret itself.
How It Works
Both major VSS constructions build on Shamir's scheme and add a verification layer using commitment schemes. The dealer commits to the polynomial coefficients, and participants use these commitments to check their shares.
Feldman's VSS
Paul Feldman introduced the first practical VSS scheme in 1987. The dealer chooses a random polynomial f(x) = a₀ + a₁x + a₂x² + ... + aₜ₋₁xᵗ⁻¹, where a₀ is the secret. After distributing shares f(i) to each participant i, the dealer publishes commitments to every coefficient:
// Feldman VSS commitment generation
// g is a generator of a group where discrete log is hard
Commitments:
C₀ = g^a₀ (commitment to the secret)
C₁ = g^a₁ (commitment to first coefficient)
...
Cₜ₋₁ = g^aₜ₋₁
// Each participant i verifies their share sᵢ = f(i):
g^sᵢ ?= C₀ · C₁^i · C₂^(i²) · ... · Cₜ₋₁^(i^(t-1))
// Equivalently:
g^f(i) ?= ∏ₖ Cₖ^(i^k) for k = 0, 1, ..., t-1If the equation holds, participant i knows their share lies on the same polynomial defined by the commitments. Since the commitments are public, any participant whose share fails verification can prove the dealer cheated.
Feldman's scheme has one notable limitation: the commitment C₀ = g^a₀ reveals the public key corresponding to the secret. This is computationally hiding (breaking it requires solving the discrete logarithm problem), but it is not information-theoretically secure. An adversary with unlimited computational power could theoretically recover the secret from C₀.
Pedersen's VSS
Torben Pedersen improved on Feldman's design in 1991 by using Pedersen commitments, which are information-theoretically hiding. The dealer constructs two polynomials of the same degree: the secret polynomial f(x) and a random blinding polynomial r(x). Each participant receives both evaluations: f(i) and r(i).
// Pedersen VSS uses two generators g and h
// where nobody knows log_g(h)
Secret polynomial: f(x) = a₀ + a₁x + ... + aₜ₋₁x^(t-1)
Blinding polynomial: r(x) = b₀ + b₁x + ... + bₜ₋₁x^(t-1)
Commitments:
C₀ = g^a₀ · h^b₀
C₁ = g^a₁ · h^b₁
...
Cₜ₋₁ = g^aₜ₋₁ · h^bₜ₋₁
// Participant i verifies both shares (sᵢ, tᵢ):
g^sᵢ · h^tᵢ ?= ∏ₖ Cₖ^(i^k) for k = 0, 1, ..., t-1Because each commitment blends two independent values, it reveals no information about the secret coefficient, even to an adversary with unbounded computing power. The tradeoff is that binding (the guarantee that the dealer cannot change the committed value) relies on the computational hardness of computing log_g(h). This creates a duality with Feldman's scheme: Feldman offers computational hiding with information-theoretic binding, while Pedersen offers information-theoretic hiding with computational binding.
Verification and Complaint Resolution
When a participant's share fails verification, the protocol enters a complaint phase:
- The participant broadcasts a complaint identifying the dealer and revealing the share they received
- Other participants (or any observer) can check the revealed share against the public commitments
- If the complaint is valid (the share truly does not match the commitments), the dealer is identified as dishonest
- The protocol can either abort or exclude the malicious dealer, depending on the implementation
This complaint mechanism is what makes VSS robust against active adversaries. Without it, a corrupted dealer could silently sabotage the entire protocol.
VSS in Distributed Key Generation
The most important application of VSS today is in distributed key generation (DKG) protocols. In a DKG, there is no single trusted dealer: instead, every participant acts as a dealer simultaneously, running VSS to share their own contribution to the group key. The final key share for each participant is the sum of all the shares they received.
FROST's DKG uses a variant of Pedersen's DKG protocol, where each participant runs Feldman's VSS to distribute their secret contribution and publishes a Schnorr proof of knowledge to prevent rogue-key attacks. The protocol works in two rounds:
- Each participant generates a random polynomial, computes Feldman commitments to its coefficients, and broadcasts these commitments along with a Schnorr proof of knowledge of their secret value
- Each participant evaluates their polynomial at every other participant's index, sending the resulting share over a secure channel. Recipients verify each share against the broadcaster's published commitments
After both rounds, each participant sums all the verified shares they received to form their final key share. The group public key is the product of all participants' first commitments. Because every individual sharing was verifiable, participants can be confident that the resulting group key is well-formed and that their shares are consistent. This is what enables secure FROST signing later: any signing quorum of t participants can produce a valid threshold signature because their shares all lie on a consistent polynomial.
Use Cases
Threshold Wallets and Custody
Threshold signature schemes like FROST rely on VSS during key generation to ensure every signer holds a valid share. Without VSS, a corrupted participant in the DKG could distribute bad shares, leading to a group key that nobody can actually sign with. Bitcoin custody solutions, including FROST-based signing protocols used by platforms like Spark, depend on VSS to bootstrap trust among signers who may not know each other.
Secure Multi-Party Computation
Multi-party computation (MPC) protocols frequently use VSS as a building block. When multiple parties need to jointly compute a function over their private inputs, VSS ensures that the secret-shared inputs are well-formed. Any party that provides inconsistent shares can be detected and excluded before the computation proceeds.
Distributed Randomness
Protocols that generate unbiased, unpredictable randomness (such as distributed randomness beacons) use VSS to commit participants to their random contributions before revealing them. Each participant shares their random value via VSS, and the final random output is derived from all contributions. VSS prevents any participant from biasing the output by changing their contribution after seeing others' values.
Proactive Secret Sharing
In long-lived systems, shares can be periodically refreshed without changing the underlying secret. Each participant runs VSS to share a random value with constant term zero, and everyone adds the new shares to their existing ones. The result is a fresh set of shares for the same secret, invalidating any shares that may have been compromised in the previous period.
Risks and Considerations
Broadcast Channel Requirements
VSS protocols assume that commitments are broadcast consistently to all participants. If an adversary can show different commitments to different participants (an equivocation attack), verification breaks down. In practice, this means implementations need either a reliable broadcast channel or additional consistency checks, such as having participants compare the commitments they received.
Computational Assumptions
Both Feldman's and Pedersen's schemes rely on the hardness of the discrete logarithm problem for some security property. Feldman's scheme leaks the public key of the secret, which is acceptable for many applications but could be a concern where the public key itself must remain hidden. A quantum computer running Shor's algorithm would break the discrete log assumption, threatening the computational guarantees of both schemes.
Dealer Trust in Single-Dealer Settings
When VSS is run with a single dealer (rather than as part of a DKG where everyone is a dealer), participants can verify share consistency but cannot verify that the dealer actually used the intended secret. The dealer could share a random value instead of the agreed-upon secret, and participants would have no way to detect this. DKG protocols avoid this issue by eliminating the single dealer entirely.
Abort Identification
If a malicious participant distributes invalid shares, honest participants need a mechanism to identify and exclude the cheater. Some simplified VSS implementations abort entirely upon detecting a bad share rather than attempting abort identification and recovery. The choice between these approaches affects both the protocol's liveness guarantees and its complexity.
Communication Overhead
VSS adds overhead compared to plain secret sharing. In Feldman's scheme, the dealer must broadcast t group elements as commitments. In Pedersen's scheme, participants exchange twice as many shares (one for each polynomial). For large groups or low thresholds, this overhead is modest, but it scales with the number of participants and the threshold, which matters in latency-sensitive systems like Spark's signing rounds.
This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.