Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 40 ยท Protocols and Practice

Secret Sharing and Zero-Knowledge Basics

Split a secret so any k of n shares recover it with Shamir's scheme, then prove you know a key without revealing it using a Schnorr zero-knowledge proof.

So far, cryptography has been about hiding data and checking who sent it. This lesson introduces two ideas that do something different, and a little surprising.

Secret sharing answers: "How can five people hold a key so that any three of them can open the vault together, but two of them learn nothing at all?" Zero-knowledge proofs answer: "How can I convince you that I know a secret, such as the private key for a public key, without telling you anything about the secret itself?"

Both ideas are far older than the cryptocurrency systems that made them famous, and both can be understood with arithmetic you already know from modular arithmetic and discrete logarithms.

Shamir's secret sharing

Adi Shamir's 1979 scheme rests on a fact from school geometry: two points determine a line, three points determine a parabola, and in general k points determine a polynomial of degree k - 1. One point alone says nothing about a line.

To split a secret s so that any k of n shares are enough:

  1. Work modulo a prime p larger than the secret.
  2. Choose a random polynomial of degree k - 1 whose constant term is the secret: f(x) = s + a1*x + a2*x^2 + ... + a(k-1)*x^(k-1). The other coefficients are random.
  3. Give person i the share (i, f(i)) for i = 1, 2, ..., n. (Never use x = 0; that is the secret.)

To recover, any k people combine their points with Lagrange interpolation and evaluate the polynomial at x = 0. With fewer than k shares, an infinite family of polynomials still fits, and every possible secret is equally likely. That is information-theoretic security: it holds even against an attacker with unlimited computing power, just like the one-time pad.

flowchart LR
    S["Secret s"] --> P["Random polynomial<br/>f(0) = s, degree k-1"]
    P --> A["Share 1: (1, f(1))"]
    P --> B["Share 2: (2, f(2))"]
    P --> C["Share 3: (3, f(3))"]
    P --> D["Share 4: (4, f(4))"]
    P --> E["Share 5: (5, f(5))"]
    A & B & C --> R["Any 3 shares:<br/>interpolate, read f(0)"]

A 3-of-5 scheme: the secret is the polynomial's value at zero; any three of the five points rebuild it.

Python Split and recover a secret (3 of 5)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Any three shares work, in any order. Two shares give a number that is simply wrong. The next example shows why two shares give no information. Using the same two shares, we pretend the secret is some other value and ask: is there a polynomial of degree 2 passing through all three points? There always is, whatever value we pick. So two shares are consistent with every possible secret.

Python Two shares fit every possible secret

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Practical notes

  • Shares are as large as the secret. Splitting a big file this way is wasteful; instead, encrypt the file with a random key and share the key.
  • Shamir gives secrecy, not integrity. A dishonest participant can submit a wrong share and silently corrupt the result. Verifiable secret sharing schemes add checks. The person who splits the secret (the dealer) must also be trusted.
  • Randomness matters. The polynomial coefficients must come from a secure source; predictable coefficients break the guarantee.
  • Real uses. Secret-management servers split their unseal key into shares held by different operators. Organizations split root signing keys for ceremonies, and some wallets split recovery phrases. Always test recovery before you depend on it.

Proving knowledge without revealing it

Imagine a website that wants to know that you own a private key. The obvious way is to have you send the key, which is the one thing you must never do. Signing a challenge works, but the signature is evidence you could pass to someone else. A zero-knowledge proof is a protocol where the verifier becomes convinced that the statement is true, yet learns nothing beyond that fact.

A proof system needs three properties:

  • Completeness. An honest prover with the secret always convinces the verifier.
  • Soundness. A prover who does not know the secret almost never convinces the verifier.
  • Zero knowledge. The verifier learns nothing else. Formally, the transcript could have been produced by someone who knows nothing, so it carries no information about the secret.

The Schnorr protocol

The statement to prove is: "I know x such that y = g^x mod p." Here y is a public key, and x is the private key (the discrete logarithm). The group is the same kind of setting as in Diffie-Hellman: a prime p, a prime q dividing p - 1, and an element g of order q.

The protocol has three moves:

  1. Commit. The prover picks a random r and sends t = g^r mod p.
  2. Challenge. The verifier sends a random number c.
  3. Response. The prover answers s = r + c*x mod q.

The verifier accepts if g^s == t * y^c (mod p). This is true for an honest prover because g^s = g^(r + c*x) = g^r * (g^x)^c = t * y^c.

sequenceDiagram
    participant P as Prover (knows x)
    participant V as Verifier (knows y = g^x)
    P->>V: t = g^r (commitment)
    V->>P: c (random challenge)
    P->>V: s = r + c*x mod q
    Note over V: accept if g^s = t * y^c

Three moves. The random r hides x inside s, so s alone reveals nothing.

Why does the verifier learn nothing? Because r is random, s = r + c*x is itself uniformly random. Why can the prover not cheat? If they could answer two different challenges for the same commitment, then subtracting the two responses would give x directly, so an impostor who has not done the work can only prepare for one challenge.

Python The Schnorr protocol, including a forged transcript

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two checks are the heart of the idea. An impostor can be ready for exactly one challenge, so with a challenge drawn from q possibilities (about 2^127), they are caught almost surely. And since anyone can create accepting transcripts after the fact, a recorded transcript is worthless as evidence: only a live interaction with a fresh random challenge convinces the verifier.

From interaction to signatures: Fiat-Shamir

Requiring a live verifier is inconvenient. The Fiat-Shamir transform removes the interaction: the prover computes the challenge themselves as a hash of the commitment (and of any message to bind): c = H(g, y, t, message). Because a hash is unpredictable, the prover cannot choose the challenge to suit them, which is what the verifier's randomness did before.

Include a message in the hash and you have a Schnorr signature; it is the same family as the DSA-style scheme in the digital signatures lesson, and Ed25519 is a refined version of this idea. Proofs without interaction are the foundation of the much larger systems (zk-SNARKs and zk-STARKs) that prove statements about whole programs.

Python A non-interactive proof bound to a message

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Binding the message and the context (site name, time, session) into the hash is what stops an attacker from replaying a proof somewhere else.

Where these ideas are used

  • Secret sharing: unsealing secret stores, splitting master keys between officers, backup of high-value keys, and building blocks of threshold cryptography, where a key is used without ever being assembled in one place.
  • Zero knowledge: proving possession of a key (as above), anonymous credentials ("I am over 18" without a birth date), private transactions, and proving that a computation was done correctly without redoing it.
  • Caution. Real zero-knowledge systems are subtle. Use well-reviewed libraries and protocols, never hand-rolled ones.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a 3-of-5 Shamir scheme, what does the polynomial look like?

    A threshold of k needs a polynomial of degree k - 1, so degree 2 here. The secret is the value at x = 0, which is the constant term.
  2. 2. An attacker holds two shares of a 3-of-5 scheme. What can they learn about the secret?

    For any guessed secret there is exactly one degree-2 polynomial through it and the two shares, so all secrets are equally likely. The security does not depend on computing power.
  3. 3. What are the three moves of the Schnorr protocol?

    The prover commits to a random value, the verifier replies with a random challenge, and the prover answers with a value that combines both with the secret.
  4. 4. Why can a recorded Schnorr transcript not convince a third party?

    That ability to simulate is exactly what zero knowledge means: the transcript reveals nothing, so it also proves nothing to someone who did not take part live.
  5. 5. What does the Fiat-Shamir transform do?

    Since the hash output cannot be predicted by the prover, it plays the role of the verifier's random challenge. Adding a message to the hash gives a signature.

Summary

  • Shamir's scheme hides a secret as the constant term of a random degree k - 1 polynomial; any k shares recover it by interpolation, and fewer reveal nothing, even to unbounded attackers.
  • Shares give no integrity, and the dealer must be trusted; share a key, not a large file.
  • A zero-knowledge proof convinces without revealing: it needs completeness, soundness and zero knowledge.
  • The Schnorr protocol proves knowledge of a discrete logarithm in three moves: commit t = g^r, challenge c, response s = r + c*x, checked by g^s = t * y^c.
  • Fiat-Shamir replaces the challenge with a hash; including a message gives a signature. Use reviewed libraries for real systems.

Next: Post-Quantum Cryptography, which asks what happens to all of this when quantum computers arrive.