Zero-Knowledge Proofs: Proving Without Revealing

The Overshare Problem in Aadhaar e-KYC

Suppose a food-delivery app needs to confirm you are 18 or older before unlocking its alcohol section, or IRCTC needs to confirm a passenger qualifies for a senior-citizen fare. Today, the standard way to do this in India runs through Aadhaar-based e-KYC. The app sends your Aadhaar number to UIDAI's servers, and the response comes back not as a single bit but as a full demographic packet: your name, your exact date of birth, your address, sometimes your photograph. The app asked a yes-or-no question ("is this person 18+?") and received an entire identity dossier in return. Every verification event multiplies the number of organisations holding a copy of your date of birth, your address, and a token that links back to your Aadhaar number, even though none of that was actually required to answer the question asked.

This mismatch, between what a verifier needs to know and what a prover is forced to reveal in order to convince them, is the exact gap that zero-knowledge proofs are built to close. A zero-knowledge proof lets a prover convince a verifier that a statement is true (here, "the person behind this request is over 18") while provably revealing nothing else, not the birth date, not any other fact that could be derived from the exchange beyond the truth of that single statement. This chapter builds the idea from first principles, using a real cryptographic protocol you can trace by hand, so that "reveals nothing else" stops being a slogan and becomes something you can verify with arithmetic.

What a Zero-Knowledge Proof Actually Promises

Formally, a zero-knowledge proof is an interactive protocol between two parties: a prover P, who holds a secret called a witness, and a verifier V, who wants to be convinced that P knows a witness satisfying some public statement, without learning the witness itself. The protocol must satisfy three properties simultaneously, and each one rules out a different way the system could fail.

Completeness. If the statement is true and the prover genuinely knows the witness, an honest prover following the protocol convinces an honest verifier with certainty (or, in some variants, with overwhelming probability). A correct proof should never be rejected.

Soundness. If the statement is false, or the prover does not actually know a valid witness, then no matter what strategy the prover uses, the probability of convincing the verifier is bounded and small (the soundness error), and that probability can be driven toward zero by repeating the protocol. A cheating prover should almost never get away with it.

Zero-knowledge. Whatever the verifier observes during the protocol (every commitment, challenge, and response exchanged) could have been produced by a simulator that does not know the witness at all. If a machine with no access to the secret can generate a transcript that is statistically indistinguishable from a real one, then the real transcript cannot have leaked anything about the secret beyond the fact that the statement is true. This is the property that turns "trust me" into something mathematically checkable, and it is also the property most students misjudge, which this chapter comes back to explicitly later.

Notice what zero-knowledge does not claim: it does not hide which statement is being proven (the age-verification app still learns "yes, over 18," it only fails to learn the birth date), and on its own it does not make the proof certain in a single round (soundness is usually probabilistic, not absolute). Keeping these boundaries precise is what separates a real understanding of the technique from a vague sense that "encryption makes it private."

The Discrete Logarithm: A Problem Easy to Check, Hard to Invert

To build an actual protocol, we need a mathematical relationship that is cheap to verify in one direction and expensive to reverse in the other. The classical choice for a first zero-knowledge proof is the discrete logarithm problem, which sits in modular arithmetic: arithmetic on remainders after division by a fixed number, the modulus.

Fix a prime p and a number g that generates the multiplicative group of integers modulo p, meaning the powers g¹, g², g³, … taken modulo p cycle through every nonzero remainder from 1 to p−1 before repeating. Such a g is called a primitive root, and the number of distinct powers before repetition, called the order of the group, is q = p−1.

Given g, p, and an exponent x, computing y = g^x mod p is fast: repeated squaring gets the answer in about log₂x multiplications. But given only g, p, and y, recovering x (the discrete logarithm of y base g) has no known efficient algorithm for a well-chosen large prime p. This one-way gap, easy forward, hard backward, is exactly the asymmetry a zero-knowledge proof of knowledge needs: the prover's secret is x, and the public statement is "I know the discrete log of y."

The Schnorr Identification Protocol

The Schnorr protocol proves knowledge of x such that y = g^x mod p, without ever transmitting x. It runs in exactly three moves, which is why cryptographers call this shape a Sigma protocol (the zigzag of the three arrows resembles the Greek letter Σ).

Move 1, commitment. The prover picks a fresh random number k in the range 0 to q−1, computes t = g^k mod p, and sends t to the verifier. k is thrown away after this proof session and never reused; it plays the role of a one-time mask.

Move 2, challenge. The verifier picks a random c in the range 0 to q−1 and sends it to the prover. Crucially, the verifier chooses c after seeing t, so the prover cannot have tailored t to a challenge they knew in advance.

Move 3, response. The prover computes s = (k + c·x) mod q and sends s.

The verifier accepts if and only if g^s mod p equals t · y^c mod p. The algebra behind why this equality holds for an honest prover is a single line: since y = g^x, we have t · y^c = g^k · g^{cx} = g^{k+cx} = g^s (the last step uses that exponents combine modulo the group order q, because g^q = 1). Nowhere in this exchange does x itself appear; only t, c, and s cross the wire, alongside the public value y.

Worked Example: Tracing Every Step

Take p = 23. Checking that g = 5 is a primitive root modulo 23 means confirming its powers cycle through all 22 nonzero remainders. Computing 5¹, 5², …, 5²² modulo 23 by repeated multiplication gives the sequence 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1, all 22 nonzero residues appearing exactly once before returning to 1. So g = 5 has order q = 22, confirmed.

Say the prover's secret witness is x = 6. The public key is y = g^x mod p = 5⁶ mod 23. Reading the sixth entry in the table above, y = 8. This y is published; anyone can look it up, the way a public key is published.

Now run the protocol. The prover draws a random nonce k = 3 and computes the commitment t = g^k mod p = 5³ mod 23 = 10 (third entry in the table), sending 10 to the verifier. The verifier draws a random challenge c = 4 and sends it back. The prover computes the response s = (k + c·x) mod q = (3 + 4×6) mod 22 = 27 mod 22 = 5, and sends 5.

The verifier now checks the equality independently. Left side: g^s mod p = 5⁵ mod 23 = 20 (fifth entry in the table). Right side: t · y^c mod p = 10 × 8⁴ mod 23. Computing 8² mod 23 = 64 mod 23 = 18, then 8⁴ = 18² mod 23 = 324 mod 23 = 2, so the right side is 10 × 2 mod 23 = 20. Both sides equal 20. The verifier accepts, having seen only the numbers 10, 4, and 5 (plus the public 8), never the witness 6.

The same computation, run in code with Python's built-in modular exponentiation, confirms the trace exactly:

p, g, q = 23, 5, 22      # q = p-1, the order of the group generated by g
x = 6                     # prover's secret witness (never transmitted)
y = pow(g, x, p)          # public key: y = g^x mod p, evaluates to 8

k = 3                     # fresh random nonce for this proof session
t = pow(g, k, p)          # commitment sent to the verifier, evaluates to 10

c = 4                     # verifier's random challenge

s = (k + c * x) % q       # prover's response, evaluates to 5

lhs = pow(g, s, p)                    # verifier recomputes g^s mod p
rhs = (t * pow(y, c, p)) % p          # verifier recomputes t * y^c mod p

print(y, t, s, lhs, rhs, lhs == rhs)

This prints 8 10 5 20 20 True, matching the hand trace at every value: public key 8, commitment 10, response 5, and both sides of the check equal to 20.

Reading the Interaction as a Diagram

The picture below lays out the same run of the protocol as three labeled messages crossing between two parties, with the witness boxed off on the prover's side and never crossing the line.

Why the Verifier Learns Nothing: The Simulator Argument

Completeness and the mechanics of the check are only half the story. The claim that the transcript is zero-knowledge needs its own argument, and it is worth making concrete rather than taking on faith.

The test is this: can a "simulator" that does not know x at all produce a transcript (t, c, s) that passes the exact same verification check, and whose values look like they came from a real run? If yes, then the real transcript cannot be leaking anything about x beyond the statement's truth, because a party with zero knowledge of x could have written the same thing down.

Here is the trick: instead of generating t first and deriving s from it, the simulator works backward. It picks the response s' and the challenge c' itself, both uniformly at random, and only then computes the commitment that makes the check pass: t' = g^{s'} · y^{-c'} mod p. Take s' = 15 and c' = 9. First, y^{-1} mod 23: since 8 × 3 = 24 ≡ 1 mod 23, the inverse of y = 8 is 3. Then y^{-9} = 3⁹ mod 23, which works out to 18. And g^{s'} = 5¹⁵ mod 23 = 19. So t' = 19 × 18 mod 23 = 342 mod 23 = 20.

Check it: does g^{s'} mod p equal t' · y^{c'} mod p? Left side is 19 (already computed). Right side: 8⁹ mod 23. Using 8⁴ = 2 from earlier, 8⁸ = 2² = 4, so 8⁹ = 4 × 8 = 32 mod 23 = 9. Right side is 20 × 9 mod 23 = 180 mod 23 = 19. It matches, 19 equals 19, and this transcript was built with zero knowledge of x = 6.

Why does this matter beyond being a neat algebraic trick? Because the equation g^s = t·y^c can be solved for t given any (s, c), the simulator can hit every valid triple that a real run could ever produce, and it does so with exactly the same probability distribution: in a real run, k is uniform, which makes t uniform and, for any fixed c, makes s uniform too (the map from k to s for fixed c, x is a bijection on the group). In the simulation, c' and s' are chosen uniformly and independently, and t' is derived to fit. Both processes produce the identical distribution over accepting triples. No verifier, however powerful, can tell from the transcript alone whether it came from someone who knew x = 6 or from a simulator that never saw it. That indistinguishability, not the mere fact that x was never typed onto the wire, is what "zero-knowledge" formally means.

From Interactive to Non-Interactive: Fiat-Shamir and zk-SNARKs

The Schnorr protocol above needs a live, interactive verifier to supply a fresh random challenge each time. That is workable for a login handshake but awkward for a blockchain transaction or a document signature, where there is no verifier standing by. The Fiat-Shamir transform removes the live verifier by replacing their random challenge with a hash of the commitment: c = H(t) for a cryptographic hash function H, computed by the prover itself. Because a well-built hash function behaves unpredictably, the prover cannot predict c before choosing t any better than a real random verifier would allow, so soundness survives the transformation, and the whole proof collapses to a single message the prover can post publicly. Applied to Schnorr's protocol, this produces the Schnorr signature scheme, an actual digital-signature standard, showing that "prove you know a secret" and "sign with a secret" are the same underlying idea viewed from two angles.

Modern systems push this idea much further with zk-SNARKs (succinct non-interactive arguments of knowledge), which apply the same commit-challenge-response skeleton to circuits representing arbitrary computations, not just a single discrete-log check, and compress the proof to a size that stays small and fast to verify no matter how large the underlying computation was. Zcash uses zk-SNARKs to let a shielded transaction prove "the sender had sufficient balance and the amounts balance out" without revealing the sender, receiver, or amount. Ethereum-ecosystem zk-rollups, including Polygon's zkEVM, use the same family of proofs to convince a base chain that a batch of thousands of transactions was executed correctly, without replaying every transaction on the base chain itself. Closer to the age-verification problem this chapter opened with, researchers working on India's digital-identity stack have proposed selective-disclosure schemes built on these same zero-knowledge techniques, aimed at letting a person prove a single derived fact from their Aadhaar record (over 18, resident of a given state, holder of a valid ration card) without handing over the underlying demographic data at all. That work is still an active research and policy area rather than a deployed production system, but it is aimed exactly at closing the overshare gap described at the start of this chapter.

A Common Misconception, Corrected

Students meeting this topic for the first time often read "zero-knowledge" as a claim about certainty: they assume it means the proof is airtight, impossible to fake, because "zero" sounds absolute. That gets the target of the word backward. Zero-knowledge describes how much the verifier learns about the witness, not how certain the verifier can be that the statement is true. The certainty side of the protocol is governed separately by soundness, and soundness in a single Sigma-protocol round is only probabilistic.

Go back to the worked example. A prover who does not know x could try to cheat by guessing the verifier's challenge in advance: pick a target challenge c', pick a random s', compute a matching commitment t' = g^{s'} y^{-c'} mod p exactly as the simulator did above, and send t' hoping the verifier happens to ask for that same c'. If the verifier's actual random challenge lands on c', the forged transcript passes; if not, the cheating prover is stuck (producing a valid s for a different challenge would require solving the discrete-log problem outright). With the challenge drawn uniformly from the 22 possible values in this example, the cheat succeeds with probability 1/22 ≈ 4.5%, which is not negligible at all. This is exactly why real deployments either repeat the protocol many independent times or, more commonly, draw the challenge from a much larger space (a 256-bit range instead of 22 values), driving the per-round cheating probability down to something astronomically small. "Zero-knowledge" and "soundness error shrinking toward zero" are two separate dials on the same protocol, tuned independently, and conflating them is the single most common misreading of this topic.

Active Recall

Attempt every question before reading the worked answers below.

1. State the three properties an interactive proof system must satisfy to count as a zero-knowledge proof, and describe in one sentence each what failing that property would look like.
2. Using p = 23, g = 5, if the prover's secret is x = 9 and the random nonce is k = 7, compute the commitment t = g^k mod p.
3. Continuing question 2, compute the public key y = g^x mod p.
4. The verifier sends challenge c = 6. Compute the prover's response s = (k + c·x) mod q, where q = 22.
5. Using your answers to questions 2 through 4, verify whether g^s mod p equals t · y^c mod p.
6. If the verifier's challenge is drawn uniformly from 22 possible values, what is the probability that a prover who does not know x successfully cheats in one round? What is the probability of cheating successfully in 5 independent rounds?

Worked answers.

1. Completeness: an honest prover with a genuine witness convinces an honest verifier (failing this means correct proofs get wrongly rejected). Soundness: a prover without a valid witness convinces the verifier only with small, boundable probability (failing this means false statements can be proven, which breaks the whole point of a proof system). Zero-knowledge: the verifier's view of the interaction could be reproduced by a simulator with no access to the witness (failing this means the "proof" is secretly also a disclosure).

2. t = 5⁷ mod 23 = 78125 mod 23 = 17.

3. y = 5⁹ mod 23 = 11.

4. s = (7 + 6×9) mod 22 = (7 + 54) mod 22 = 61 mod 22 = 17.

5. Left side: g^s mod p = 5¹⁷ mod 23 = 15. Right side: t · y^c mod p = 17 × 11⁶ mod 23. Computing 11² mod 23 = 121 mod 23 = 6, then 11⁴ = 6² mod 23 = 36 mod 23 = 13, then 11⁶ = 11⁴ × 11² = 13 × 6 mod 23 = 78 mod 23 = 9. Right side is 17 × 9 mod 23 = 153 mod 23 = 15. Both sides equal 15, so the verifier accepts.

6. One round: 1/22 ≈ 4.5%. Five independent rounds, assuming a fresh random challenge each time: (1/22)⁵ = 1 / 5,153,632 ≈ 1.94 × 10⁻⁷, roughly two chances in ten million.

Think About It

Think about this: How would you explain zero-knowledge proofs: proving without revealing to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind zero-knowledge proofs: proving without revealing, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.