Questions: Secret Sharing

Question 1

In Shamir's (3,5) scheme, the secret is the constant term of a random degree-2 polynomial p(x) = s + a1*x + a2*x^2 over a finite field. Why do exactly 3 points determine s, but 2 points reveal nothing?

Model answer: A degree-2 polynomial has 3 coefficients: s, a1, a2. Three points on the polynomial give three linear equations in three unknowns, which has a unique solution — determining all coefficients including s. Two points give two equations in three unknowns — for every possible value of s, there exists a polynomial consistent with the two known points. Since a1 and a2 were chosen uniformly at random, every value of s is equally likely given any two shares. This is information-theoretic security: no computational power helps.

The key insight is that the random coefficients a1, a2, ... provide 'degrees of freedom' that mask s when fewer than t points are known. With t-1 points, there is exactly one free parameter, and it ranges over all field elements, making s uniformly distributed over the field regardless of its actual value. This is perfect secrecy for the secret, not just computational security.

Question 2

Shamir's secret sharing provides information-theoretic security (perfect secrecy) for the secret. What assumption does it NOT require?

• A. A finite field large enough to hold the secret
• B. Any computational hardness assumption — Shamir's scheme is unconditionally secure against adversaries with unlimited computing power, as long as fewer than t shares are compromised. This contrasts with most cryptographic schemes that rely on assumptions like factoring or LWE being hard
• C. Honest behavior from the share dealer
• D. A secure channel for distributing shares

Answer: (B)

Shamir's scheme achieves perfect secrecy in the information-theoretic sense: t-1 shares are statistically independent of the secret. No amount of computation changes this — it follows from the algebra of polynomial interpolation. This makes secret sharing one of the few cryptographic tools with unconditional security. The scheme does require secure channels for share distribution (otherwise an eavesdropper could collect shares) and an honest dealer (or verifiable secret sharing to protect against a dishonest dealer).

Question 3

An organization uses (3,5) secret sharing to protect a master encryption key. Two of the five shareholders collude and share their shares. What do they learn about the key?

• A. They learn approximately 2/5 of the key's bits
• B. They learn nothing — with only 2 of the required 3 shares, the key remains perfectly hidden. Every possible key value is equally consistent with their two shares
• C. They learn the key but cannot prove it to others
• D. They learn the key only if they also know the polynomial's degree

Answer: (B)

This is the essential security guarantee: t-1 shares are statistically independent of the secret. For any two shares and any candidate secret value, there exists exactly one degree-2 polynomial consistent with all three constraints. Since the polynomial's random coefficients are unknown, every secret value is equally likely. The colluding pair learns literally nothing — not a single bit of information — about the key.

Question 4

Verifiable secret sharing (VSS) extends Shamir's scheme to protect against a dishonest dealer who distributes inconsistent shares. Why is this important?

Model answer: In basic Shamir's scheme, the dealer could give some parties shares from one polynomial and other parties shares from a different polynomial — or shares that don't lie on any single polynomial at all. When parties try to reconstruct, they either get the wrong secret or fail entirely. VSS lets each party verify that their share is consistent with a committed polynomial, without revealing the secret or other shares. Feldman's VSS publishes commitments g^{a_i} for each coefficient; Pedersen's VSS uses Pedersen commitments for information-theoretic hiding. VSS is essential in MPC protocols where the dealer may be adversarial.

VSS transforms secret sharing from a protocol that requires a trusted dealer into one that works with a potentially malicious dealer. This is crucial for MPC: in the BGW protocol, each party acts as a dealer for their own input. Without VSS, a malicious party could send inconsistent shares and corrupt the computation.

Question 5

Secret sharing can be used to build a simple (t, n) threshold signature scheme where t of n parties must cooperate to sign, but no individual party can sign alone.

• T. True
• F. False

Answer: True

The signing key is shared using (t, n) Shamir sharing. To sign, t parties each compute a 'partial signature' using their share and combine the partial signatures to produce a full signature. No individual party ever sees the full signing key. Threshold ECDSA and threshold Schnorr signatures implement this for standard signature schemes. This is used in cryptocurrency custody (multi-sig wallets), certificate authority key protection, and organizational signing policies where multiple approvers are required.