Verifiable Secret Sharing (VSS)

The defining property that distinguishes VSS from standard secret sharing. Each participant can independently verify that their share is consistent with a valid secret, without revealing the secret or their share to others. This is typically achieved through commitment schemes where the dealer broadcasts cryptographic commitments to the polynomial coefficients. Participants check their share against these commitments using a verification equation. If verification fails, the dealer is publicly identified as malicious.

An adversary controlling fewer than the threshold t shares learns absolutely nothing about the secret, even with unbounded computational power. This information-theoretic guarantee holds because any secret value is equally likely given the adversary's view. The polynomial used in Shamir-based VSS has degree t-1, meaning t points are required to uniquely determine it. With t-1 or fewer points, infinitely many polynomials of degree t-1 remain consistent with the observed shares.

Once the dealer publishes commitments to the polynomial coefficients, they are bound to a specific polynomial. They cannot later claim a different secret was shared. This property is computationally enforced through the hardness of discrete logarithm or factoring assumptions in most practical schemes. In Feldman VSS, the dealer broadcasts g^a_i for each coefficient a_i, where g is a group generator. Changing the polynomial would require breaking the discrete log assumption.

Any subset of t or more valid shares can reconstruct the secret, while any subset of size t-1 or fewer cannot. Reconstruction uses Lagrange interpolation over the verified shares. The threshold t is a configurable parameter balancing availability and security:

• Higher t: More shares required, stronger secrecy, lower availability
• Lower t: Fewer shares required, weaker secrecy, higher availability This trade-off is fundamental to designing VSS-based systems.

In publicly verifiable VSS schemes like Feldman VSS, any external party can verify the correctness of shares using only public information, without being a participant. This enables:

• Auditability: Third parties can confirm the dealer behaved honestly
• Non-interactive verification: Participants don't need to communicate with each other to check shares
• Dispute resolution: Public evidence of misbehavior that any observer can validate The trade-off is that public verifiability typically provides only computational secrecy rather than unconditional.

All valid shares lie on the same polynomial of degree t-1. This prevents a malicious dealer from distributing shares that reconstruct to different secrets depending on which subset of participants contributes. Consistency is enforced through the verification protocol: each share s_i must satisfy g^{s_i} = ∏_{j=0}^{t-1} (g^{a_j})^{i^j} in Feldman VSS. Without this property, a dealer could cause different reconstruction outcomes, undermining the protocol's reliability in applications like distributed key generation.

A cryptographic primitive allowing a dealer to commit to a secret value while keeping it hidden, with the ability to reveal it later. In VSS, commitments are broadcast alongside shares so participants can verify consistency without seeing others' shares.

• Pedersen Commitments: Provide information-theoretic hiding and computational binding
• Feldman's Scheme: Uses discrete log commitments for efficient public verification
• Binding Property: Ensures the dealer cannot change the secret after committing

The foundational threshold scheme that VSS extends. Encodes a secret as a polynomial of degree t-1, distributing points as shares. Reconstruction requires any t shares via Lagrange interpolation.

• Information-theoretic security: Fewer than t shares reveal nothing about the secret
• Dealer selects: A random polynomial where f(0) = secret
• Shares are: Points (i, f(i)) for i = 1, 2, ..., n

The resilience of a distributed system to arbitrary or malicious failures. VSS provides a critical building block for BFT protocols by ensuring that even a malicious dealer cannot distribute inconsistent shares that would prevent correct reconstruction.

• Byzantine Agreement: Requires consistent values across honest nodes
• VSS Role: Guarantees a unique, reconstructable secret exists
• Asynchronous VSS: Extends verification to networks without timing assumptions

A protocol where multiple parties jointly generate a public/private key pair without any single party knowing the full private key. VSS is the core primitive enabling DKG by allowing each participant to verifiably share a secret contribution.

• Threshold Signatures: Enabled by DKG for decentralized signing authority
• No Trusted Dealer: Every participant acts as a VSS dealer for their share
• Applications: Blockchain validators, threshold decryption services

A specific VSS construction that achieves computational security using discrete logarithm commitments. The dealer publishes g^a₀, g^a₁, ..., g^aₜ₋₁ where aᵢ are polynomial coefficients, allowing any participant to verify their share sᵢ by checking: g^sᵢ = ∏(g^aⱼ)^(i^j).

• Publicly Verifiable: Anyone can check share consistency
• Homomorphic: Supports addition of shared secrets
• Security: Relies on the hardness of the discrete log problem

A VSS scheme providing information-theoretic hiding by using a double commitment. The dealer commits to both the secret polynomial f(x) and a random blinding polynomial g(x), publishing g^f(0)h^g(0) as the combined commitment.

• Unconditional Privacy: Even computationally unbounded adversaries learn nothing
• Two-Polynomial Construction: Separates verification from secrecy
• Trade-off: Requires more communication than Feldman's scheme