09d-schnorr-protocol.ipynb

Kernel: SageMath 10.5

The Schnorr Protocol

Module 09d | 09-commitments-sigma-protocols

The most important sigma protocol: completeness, special soundness, honest-verifier zero-knowledge

From Framework to Concrete Protocol

In 09c, we studied the abstract structure of sigma protocols: three moves (commit, challenge, response), and three properties every sigma protocol must satisfy (completeness, special soundness, HVZK). That was the framework, the blueprint.

Now we instantiate it. The Schnorr protocol (1989) is the single most important sigma protocol in cryptography. It is:

• The foundation of Schnorr signatures (standardized in EdDSA / Ed25519)

• The core of Bitcoin's Taproot upgrade (BIP 340)

• The building block for zero-knowledge proofs in SNARKs and bulletproofs

• The textbook example every cryptographer learns first

If you understand Schnorr deeply, you understand the DNA of modern zero-knowledge cryptography.

The Motivating Question

Alice knows $x$ such that $y = g^x \pmod{p}$. She wants to PROVE she knows $x$ to Bob WITHOUT revealing $x$. Not even a single bit. Can she?

Think about how strange this is. Alice must convince Bob she knows a secret, yet Bob must learn absolutely nothing about what that secret is. It sounds impossible, like proving you know the combination to a safe without ever touching the dial.

Schnorr showed it is not only possible, but elegant. Three messages. Three properties. One beautiful protocol.

Setup: The Schnorr Group

We work in a prime-order subgroup of $\mathbb{Z}_p^*$:

• Choose a large prime $p$ and a prime $q$ such that $q \mid (p-1)$

• Pick a generator $g$ of the unique order-$q$ subgroup of $\mathbb{Z}_p^*$

• The secret key is $x \in \{1, \ldots, q-1\}$

• The public key is $y = g^x \pmod{p}$

We use a prime-order subgroup (not all of $\mathbb{Z}_p^*$) because we need every non-identity element to be a generator, and we need clean modular arithmetic in the exponent (mod $q$).

# --- Schnorr Group Setup ---
# We construct a safe prime setup: p = 2q + 1 where both p and q are prime.
# This gives us a prime-order subgroup of order q inside Z_p^*.

# For teaching, we use small primes so you can verify by hand.
# In practice, q would be ~256 bits.

def schnorr_group_setup(bits=20):
    """Generate Schnorr group parameters (p, q, g)."""
    while True:
        q = random_prime(2^bits, lbound=2^(bits-1))
        p = 2 * q + 1
        if is_prime(p):
            break
    # Find generator of order-q subgroup: pick random h, compute g = h^2 mod p
    # Since p = 2q+1, the order of Z_p^* is 2q.
    # h^2 has order q (unless h^2 = 1, which we skip).
    while True:
        h = randint(2, p - 2)
        g = power_mod(h, 2, p)
        if g != 1:
            break
    return p, q, g

p, q, g = schnorr_group_setup(bits=20)
print(f"Prime p = {p}")
print(f"Prime q = {q}  (subgroup order)")
print(f"Generator g = {g}")
print(f"\nVerification: g^q mod p = {power_mod(g, q, p)}  (should be 1)")
print(f"g != 1: {g != 1}  (g is not the identity)")

# --- Key Generation ---
# Alice picks a secret key x and publishes y = g^x mod p

x = randint(1, q - 1)          # Alice's SECRET key
y = power_mod(g, x, p)         # Alice's PUBLIC key

print(f"Alice's secret key: x = {x}")
print(f"Alice's public key: y = g^x mod p = {y}")
print(f"\nAnyone can see y, but computing x from y requires solving")
print(f"the discrete logarithm problem, believed to be hard.")

The Schnorr Protocol: Three Moves

Recall the sigma protocol skeleton from 09c: Commit $\to$ Challenge $\to$ Response. Here is Schnorr's instantiation:

Step	Who	What	Detail
1. Commit	Prover $\to$ Verifier	Send $R$	Pick random $k \in \{1, \ldots, q-1\}$, compute $R = g^k \bmod p$
2. Challenge	Verifier $\to$ Prover	Send $c$	Pick random $c \in \{0, \ldots, q-1\}$
3. Response	Prover $\to$ Verifier	Send $s$	Compute $s = k + c \cdot x \pmod{q}$

Verification: The verifier accepts if and only if $g^s \equiv R \cdot y^c \pmod{p}$.

That is the entire protocol. Three messages. One equation to check.

# --- The Schnorr Protocol: Full Implementation ---

def schnorr_prover_commit(p, q, g):
    """Step 1: Prover picks random nonce k, sends R = g^k."""
    k = randint(1, q - 1)
    R = power_mod(g, k, p)
    return k, R

def schnorr_verifier_challenge(q):
    """Step 2: Verifier picks random challenge c."""
    c = randint(0, q - 1)
    return c

def schnorr_prover_respond(k, c, x, q):
    """Step 3: Prover computes s = k + c*x mod q."""
    s = (k + c * x) % q
    return s

def schnorr_verify(p, q, g, y, R, c, s):
    """Verifier checks: g^s == R * y^c mod p."""
    lhs = power_mod(g, s, p)
    rhs = (R * power_mod(y, c, p)) % p
    return lhs == rhs

print("Protocol functions defined. Let's run it!")

# --- Full Interactive Protocol Simulation ---
# Alice (prover) proves to Bob (verifier) that she knows x such that y = g^x

print("  SCHNORR IDENTIFICATION PROTOCOL")
print(f"\nPublic parameters: p={p}, q={q}, g={g}")
print(f"Alice's public key: y = {y}")
print()

# Step 1: Alice commits
k, R = schnorr_prover_commit(p, q, g)
print(f"Step 1 (Alice -> Bob):  R = g^k mod p = {R}")
print(f"        [Alice's secret nonce: k = {k}]")
print()

# Step 2: Bob challenges
c = schnorr_verifier_challenge(q)
print(f"Step 2 (Bob -> Alice):  c = {c}")
print()

# Step 3: Alice responds
s = schnorr_prover_respond(k, c, x, q)
print(f"Step 3 (Alice -> Bob):  s = k + c*x mod q = {s}")
print()

# Verification
result = schnorr_verify(p, q, g, y, R, c, s)
print(f"Bob verifies: g^s mod p = {power_mod(g, s, p)}")
print(f"              R * y^c mod p = {(R * power_mod(y, c, p)) % p}")
print(f"              Equal? {result}")
print()
print(f"Bob's verdict: {'ACCEPT. Alice proved knowledge of x!' if result else 'REJECT'}")

Why Does Verification Work?

Let's trace the algebra step by step. The verifier checks whether $g^s \equiv R \cdot y^c \pmod{p}$.

Substituting $s = k + cx \pmod{q}$ and $R = g^k$, $y = g^x$:

$$g^s = g^{k + cx} = g^k \cdot g^{cx} = g^k \cdot (g^x)^c = R \cdot y^c \quad \checkmark$$

Each step uses a basic exponent rule. The key insight is that the response $s$ encodes both the nonce $k$ and the secret $x$, but the verification equation lets the verifier check consistency without separating them.

Misconception alert: "The prover sends $s = k + cx$, which contains $x$, so the verifier learns $x$." No! The value $s$ alone reveals nothing about $x$ because the nonce $k$ is unknown to the verifier. Think of it as a one-time pad for the secret: $k$ perfectly masks $cx$, just as a one-time pad key masks a message. Without $k$, the verifier cannot disentangle $x$ from $s$.

Checkpoint: Verify by Hand

Before running the next cell, take the values of $R$, $c$, $s$, $g$, $y$, $p$ from the protocol run above and verify the equation $g^s \equiv R \cdot y^c \pmod{p}$ by hand (or with a calculator). Does it check out?

Property 1: Completeness

Completeness says: if the prover is honest (really knows $x$), the verifier always accepts.

We proved this algebraically above. Let's also verify it experimentally, run the protocol 1000 times and confirm every execution succeeds.

# --- Completeness: Honest prover ALWAYS convinces the verifier ---

num_trials = 1000
all_accepted = True

for _ in range(num_trials):
    k_trial, R_trial = schnorr_prover_commit(p, q, g)
    c_trial = schnorr_verifier_challenge(q)
    s_trial = schnorr_prover_respond(k_trial, c_trial, x, q)
    if not schnorr_verify(p, q, g, y, R_trial, c_trial, s_trial):
        all_accepted = False
        break

print(f"Ran {num_trials} honest protocol executions.")
print(f"All accepted? {all_accepted}")
print()
print("Completeness holds: an honest prover is NEVER rejected.")
print("This is not surprising, it follows directly from the algebra.")
print("But it's a sanity check that our implementation is correct.")

Property 2: Special Soundness

Special soundness says: given two accepting transcripts $(R, c_1, s_1)$ and $(R, c_2, s_2)$ with the same commitment $R$ but different challenges $c_1 \neq c_2$, we can extract the secret $x$.

Here's the extraction. From the two transcripts:

$$s_1 = k + c_1 x \pmod{q}$$$$s_2 = k + c_2 x \pmod{q}$$

Subtract:

$$s_1 - s_2 = (c_1 - c_2) \cdot x \pmod{q}$$

Since $q$ is prime and $c_1 \neq c_2$, the value $(c_1 - c_2)$ is invertible mod $q$:

$$x = \frac{s_1 - s_2}{c_1 - c_2} \pmod{q}$$

This means: a cheating prover who doesn't know $x$ cannot answer two different challenges for the same $R$. If they could, we could extract $x$, contradicting the assumption that they don't know it.

# --- Special Soundness: Extract x from two transcripts ---

# Simulate: Alice proves with the SAME nonce k but gets two different challenges.
# (In real life this should never happen, each proof uses a fresh k.)

k_fixed, R_fixed = schnorr_prover_commit(p, q, g)

# First challenge and response
c1 = schnorr_verifier_challenge(q)
s1 = schnorr_prover_respond(k_fixed, c1, x, q)

# Second challenge (different from c1) and response, SAME R
c2 = c1
while c2 == c1:
    c2 = schnorr_verifier_challenge(q)
s2 = schnorr_prover_respond(k_fixed, c2, x, q)

# Both transcripts are valid
assert schnorr_verify(p, q, g, y, R_fixed, c1, s1)
assert schnorr_verify(p, q, g, y, R_fixed, c2, s2)

print(f"Transcript 1: (R={R_fixed}, c={c1}, s={s1})")
print(f"Transcript 2: (R={R_fixed}, c={c2}, s={s2})")
print(f"Both verify: True")
print()

# Extract the secret!
x_extracted = ((s1 - s2) * inverse_mod(c1 - c2, q)) % q

print(f"Extracted secret: x = (s1 - s2) / (c1 - c2) mod q = {x_extracted}")
print(f"Actual secret:    x = {x}")
print(f"Match? {x_extracted == x}")
print()
print("Special soundness DEMONSTRATED: two transcripts with the same R")
print("are enough to recover the secret key completely.")

What Special Soundness Really Means

Special soundness is the security guarantee for the verifier. It tells Bob:

"If Alice can answer my challenge for a given $R$, she must know $x$, because if she could answer two different challenges, I could extract $x$ myself."

A cheating prover who doesn't know $x$ can guess the challenge in advance and construct a single valid response (with probability $1/q$), but she cannot answer two challenges for the same $R$. This is why the challenge must be truly random and unpredictable.

Property 3: Honest-Verifier Zero-Knowledge (HVZK)

HVZK says: the verifier learns nothing from the protocol beyond the fact that Alice knows $x$. Formally, there exists a simulator that can produce transcripts $(R, c, s)$ that are indistinguishable from real transcripts, without knowing $x$.

The Simulator

The simulator works backwards:

1. Pick random $s \in \{0, \ldots, q-1\}$ and random $c \in \{0, \ldots, q-1\}$

2. Compute $R = g^s \cdot y^{-c} \pmod{p}$

3. Output the transcript $(R, c, s)$

Why this works: By construction, $g^s = g^s$ and $R \cdot y^c = g^s \cdot y^{-c} \cdot y^c = g^s$. So the verification equation $g^s = R \cdot y^c$ holds!

The simulator never touches $x$. It only uses the public key $y$. Yet it produces perfectly valid transcripts. This means the transcript itself carries zero information about $x$, because someone without $x$ can produce equally valid ones.

# --- HVZK Simulator: Generate valid transcripts WITHOUT knowing x ---

def schnorr_simulator(p, q, g, y):
    """
    Simulate a Schnorr transcript (R, c, s) using only the PUBLIC key y.
    The simulator does NOT know the secret x.
    """
    s = randint(0, q - 1)
    c = randint(0, q - 1)
    # R = g^s * y^(-c) mod p
    R = (power_mod(g, s, p) * power_mod(y, -c, p)) % p
    return R, c, s

print("Generating 5 SIMULATED transcripts (no knowledge of x):")
for i in range(5):
    R_sim, c_sim, s_sim = schnorr_simulator(p, q, g, y)
    valid = schnorr_verify(p, q, g, y, R_sim, c_sim, s_sim)
    print(f"  Transcript {i+1}: R={R_sim}, c={c_sim}, s={s_sim}  |  Valid? {valid}")

print()
print("Every simulated transcript is VALID, yet the simulator never knew x.")
print("This proves the protocol is zero-knowledge: the transcript alone")
print("carries no information about x.")

Checkpoint: Simulated vs. Real

Look at the simulated transcripts above. Can you tell them apart from the real transcript we generated earlier? You should not be able to, that is the whole point. If you could distinguish them, the protocol would leak information about $x$.

The distributions are identical:

• In a real transcript, $c$ and $s$ are both uniformly random (since $k$ is random, $s = k + cx$ is uniform mod $q$), and $R$ is determined by them.

• In a simulated transcript, $c$ and $s$ are chosen uniformly at random, and $R$ is determined by them.

• Same distribution.

Statistical Comparison: Real vs. Simulated

Let's go further and compare the distributions of $s$ values in real vs. simulated transcripts. Both should be uniform over $\{0, \ldots, q-1\}$.

# --- Compare distributions of real vs. simulated transcripts ---
import collections

# Use a small group for visible histogram
# Find a small safe prime
q_small = 23  # prime
p_small = 2 * q_small + 1  # 47, which is prime
assert is_prime(p_small) and is_prime(q_small)

# Find generator of order-q_small subgroup of Z_{47}^*
g_small = None
for h in range(2, p_small):
    candidate = power_mod(h, 2, p_small)
    if candidate != 1 and power_mod(candidate, q_small, p_small) == 1:
        g_small = candidate
        break

x_small = randint(1, q_small - 1)
y_small = power_mod(g_small, x_small, p_small)

N = 5000

# Collect s values from real transcripts
real_s = []
for _ in range(N):
    k_t, R_t = schnorr_prover_commit(p_small, q_small, g_small)
    c_t = schnorr_verifier_challenge(q_small)
    s_t = schnorr_prover_respond(k_t, c_t, x_small, q_small)
    real_s.append(s_t)

# Collect s values from simulated transcripts
sim_s = []
for _ in range(N):
    _, c_t, s_t = schnorr_simulator(p_small, q_small, g_small, y_small)
    sim_s.append(s_t)

# Count frequencies
real_counts = collections.Counter(real_s)
sim_counts = collections.Counter(sim_s)

print(f"Distribution of s values (mod {q_small}), {N} samples each:")
print("s  Real  Simulated  Expected")expected = N / q_small
for sv in range(q_small):
    print(f"{sv}  {real_counts.get(sv, 0)}  {sim_counts.get(sv, 0)}  {expected:>10.1f}")

print(f"\nBoth distributions are approximately uniform over {{0, ..., {q_small-1}}}.")
print("You cannot distinguish real from simulated, zero knowledge holds.")

Critical Security Requirement: Fresh Nonces

The nonce $k$ MUST be chosen uniformly at random and MUST be fresh for every protocol execution. If the same $k$ is ever used twice, the secret $x$ is immediately recoverable.

Suppose Alice uses the same $k$ (and hence the same $R = g^k$) in two different proofs with challenges $c_1, c_2$:

$$s_1 = k + c_1 x, \quad s_2 = k + c_2 x$$

Then $x = (s_1 - s_2)(c_1 - c_2)^{-1} \bmod q$. This is exactly the special soundness extractor, but now an eavesdropper can run it!

Crypto Foreshadowing: This is EXACTLY what happened in the 2010 PlayStation 3 hack. Sony used ECDSA (which has the same nonce structure as Schnorr) but used a fixed nonce $k$ for every signature. The hacker group fail0verflow extracted Sony's private signing key from two signatures, broke PS3 code signing entirely, and enabled homebrew software on every PS3. The same vulnerability has leaked Bitcoin private keys when wallet software reused nonces.

# --- DANGER: Nonce Reuse Attack ---
# If Alice reuses k, an eavesdropper can extract x.

print("  NONCE REUSE ATTACK DEMONSTRATION")
print()

# Alice reuses the same nonce k for two proofs
k_reused = randint(1, q - 1)
R_reused = power_mod(g, k_reused, p)

# Two different challenges from the verifier (or from two different sessions)
c_a = randint(1, q - 1)
c_b = c_a
while c_b == c_a:
    c_b = randint(1, q - 1)

s_a = (k_reused + c_a * x) % q
s_b = (k_reused + c_b * x) % q

print(f"Proof 1: (R={R_reused}, c={c_a}, s={s_a})")
print(f"Proof 2: (R={R_reused}, c={c_b}, s={s_b})")
print(f"Same R? {True}  <-- FATAL: nonce was reused!")
print()

# Eavesdropper extracts x
x_stolen = ((s_a - s_b) * inverse_mod(c_a - c_b, q)) % q

print(f"Eavesdropper computes: x = (s1-s2)/(c1-c2) mod q = {x_stolen}")
print(f"Alice's actual secret: x = {x}")
print(f"Secret recovered? {x_stolen == x}")
print()
print("LESSON: Never reuse a nonce. Ever. One reuse = total key compromise.")

---

Exercises

Three exercises following the worked $\to$ guided $\to$ independent pattern.

Exercise 1: Verify a Schnorr Proof by Hand (Fully Worked)

Problem: Given the following small Schnorr group and transcript, verify the proof step by step.

• $p = 23$, $q = 11$, $g = 4$ (which has order 11 mod 23)

• Public key: $y = 13$

• Transcript: $R = 9$, $c = 3$, $s = 7$

Task: Check whether $g^s \equiv R \cdot y^c \pmod{p}$.

# --- Exercise 1: FULLY WORKED SOLUTION ---

p1, q1, g1 = 23, 11, 4
y1 = 13
R1, c1_ex, s1_ex = 9, 3, 7

# Step 1: Verify g has order q mod p
print("Step 1: Verify group parameters")
print(f"  g^q mod p = {power_mod(g1, q1, p1)}  (should be 1)")
print()

# Step 2: Compute left-hand side: g^s mod p
lhs = power_mod(g1, s1_ex, p1)
print(f"Step 2: Compute LHS")
print(f"  g^s mod p = 4^7 mod 23")
print(f"  4^1 = 4")
print(f"  4^2 = 16")
print(f"  4^4 = 16^2 = 256 mod 23 = 256 - 11*23 = 256 - 253 = 3")
print(f"  4^7 = 4^4 * 4^2 * 4^1 = 3 * 16 * 4 = 192 mod 23 = 192 - 8*23 = 192 - 184 = 8")
print(f"  g^s mod p = {lhs}")
print()

# Step 3: Compute right-hand side: R * y^c mod p
yc = power_mod(y1, c1_ex, p1)
rhs = (R1 * yc) % p1
print(f"Step 3: Compute RHS")
print(f"  y^c mod p = 13^3 mod 23 = 2197 mod 23 = {yc}")
print(f"  R * y^c mod p = 9 * {yc} mod 23 = {9 * yc} mod 23 = {rhs}")
print()

# Step 4: Compare
print(f"Step 4: Compare")
print(f"  LHS = {lhs}")
print(f"  RHS = {rhs}")
print(f"  Equal? {lhs == rhs}")
print()
if lhs == rhs:
    print("  The proof VERIFIES. The prover knows x such that y = g^x.")
else:
    print("  The proof FAILS. Either the transcript is invalid or the prover doesn't know x.")

Exercise 2: Build a Simulator (Guided)

Problem: Using the same small group ($p=23$, $q=11$, $g=4$, $y=13$), write a simulator that produces a valid Schnorr transcript without knowing the secret $x$.

Hints:

1. Pick any $s \in \{0, \ldots, 10\}$ and any $c \in \{0, \ldots, 10\}$

2. Compute $R = g^s \cdot y^{-c} \bmod p$. Remember that $y^{-c} \bmod p$ is the modular inverse: power_mod(y, -c, p)

3. Verify that $(R, c, s)$ passes the verification equation

Fill in the code below.

# --- Exercise 2: Build a Simulator (fill in the blanks) ---

p2, q2, g2, y2 = 23, 11, 4, 13

# Step 1: Pick random s and c
s2_sim = randint(0, q2 - 1)
c2_sim = randint(0, q2 - 1)

# Step 2: Compute R = ???  (FILL THIS IN)
# R2_sim = ...

# Step 3: Verify the transcript
# assert schnorr_verify(p2, q2, g2, y2, R2_sim, c2_sim, s2_sim)
# print(f"Simulated transcript: R={R2_sim}, c={c2_sim}, s={s2_sim}")
# print(f"Valid? {schnorr_verify(p2, q2, g2, y2, R2_sim, c2_sim, s2_sim)}")
# print("Success! You built a simulator without knowing x.")

Exercise 3: Extract the Secret from Nonce Reuse (Independent)

Problem: An eavesdropper observes two Schnorr proof transcripts that share the same commitment $R$. The parameters are $p=47$, $q=23$, $g=4$ (order 23 mod 47).

Transcript	$R$	$c$	$s$
1	17	5	19
2	17	14	8

Extract the secret key $x$. Then verify your answer by checking that $y = g^x \bmod p$ matches the public key implied by the transcripts.

Hint: the extraction formula is $x = (s_1 - s_2)(c_1 - c_2)^{-1} \bmod q$.

# --- Exercise 3: Extract the secret (write your solution here) ---

p3, q3, g3 = 47, 23, 4
R3 = 17
c3_1, s3_1 = 5, 19
c3_2, s3_2 = 14, 8

# Your code here:
# x3 = ...
# y3 = power_mod(g3, x3, p3)
# print(f"Extracted secret: x = {x3}")
# print(f"Public key: y = g^x mod p = {y3}")
# Verify both transcripts:
# print(f"Transcript 1 valid? {schnorr_verify(p3, q3, g3, y3, R3, c3_1, s3_1)}")
# print(f"Transcript 2 valid? {schnorr_verify(p3, q3, g3, y3, R3, c3_2, s3_2)}")

---

The Big Picture: Three Properties Working Together

Let's step back and see how the three properties combine to make the Schnorr protocol useful:

Property	What it guarantees	Who benefits
Completeness	An honest prover always convinces the verifier	Prover (Alice)
Special Soundness	A cheating prover cannot fool the verifier	Verifier (Bob)
HVZK	The verifier learns nothing about $x$	Prover (Alice)

Together, these three properties achieve the seemingly impossible: Alice proves she knows $x$ (soundness), Bob is convinced (completeness), and yet Bob learns nothing about $x$ (zero-knowledge).

# --- All Three Properties in One Demonstration ---

print("  ALL THREE PROPERTIES OF SCHNORR")

#. Completeness --
print("\n[1] COMPLETENESS: Honest prover always accepted")
successes = 0
for _ in range(100):
    kt, Rt = schnorr_prover_commit(p, q, g)
    ct = schnorr_verifier_challenge(q)
    st = schnorr_prover_respond(kt, ct, x, q)
    if schnorr_verify(p, q, g, y, Rt, ct, st):
        successes += 1
print(f"    100/100 accepted? {successes == 100}")

#. Special Soundness --
print("\n[2] SPECIAL SOUNDNESS: Two transcripts => extract x")
k_ss, R_ss = schnorr_prover_commit(p, q, g)
c_ss1 = randint(1, q-1)
c_ss2 = c_ss1
while c_ss2 == c_ss1:
    c_ss2 = randint(1, q-1)
s_ss1 = schnorr_prover_respond(k_ss, c_ss1, x, q)
s_ss2 = schnorr_prover_respond(k_ss, c_ss2, x, q)
x_ss = ((s_ss1 - s_ss2) * inverse_mod(c_ss1 - c_ss2, q)) % q
print(f"    Extracted x = {x_ss}, actual x = {x}, match? {x_ss == x}")

#. HVZK --
print("\n[3] HVZK: Simulator produces valid transcripts without x")
for i in range(3):
    R_hv, c_hv, s_hv = schnorr_simulator(p, q, g, y)
    print(f"    Simulated transcript {i+1}: valid? {schnorr_verify(p, q, g, y, R_hv, c_hv, s_hv)}")

print("\nAll three properties verified.")

Bonus: What Happens if a Cheating Prover Tries?

Suppose Eve does NOT know $x$, but she tries to pass the Schnorr protocol anyway. She has two strategies:

1. Guess the challenge in advance: Pick $c^*$, compute a valid response for that specific $c^*$. This works with probability $1/q$, negligible for cryptographic $q$.

2. Try to compute $s$ after receiving $c$: She knows $R$ (she chose it) and $c$ (from the verifier), but computing $s = k + cx \bmod q$ requires knowing $x$. Without $x$, she's stuck.

Let's see strategy 1 in action.

# --- Cheating Prover: Guess-the-challenge strategy ---

def cheating_prover_attempt(p, q, g, y):
    """
    Eve doesn't know x. She guesses the challenge c* in advance
    and constructs (R, s) that would verify for c*.
    But the verifier picks c at random, if c != c*, she fails.
    """
    # Eve guesses the challenge
    c_guess = randint(0, q - 1)

    # She picks random s and computes R = g^s * y^(-c_guess)
    s_cheat = randint(0, q - 1)
    R_cheat = (power_mod(g, s_cheat, p) * power_mod(y, -c_guess, p)) % p

    # The verifier sends the ACTUAL challenge
    c_actual = schnorr_verifier_challenge(q)

    # Eve sends her pre-computed s (she can't change it now)
    # Verification: g^s == R * y^c_actual ?
    accepted = schnorr_verify(p, q, g, y, R_cheat, c_actual, s_cheat)

    return accepted, (c_guess == c_actual)

# Run many cheating attempts
num_attempts = 10000
num_fooled = sum(1 for _ in range(num_attempts) if cheating_prover_attempt(p, q, g, y)[0])

print(f"Cheating prover attempts: {num_attempts}")
print(f"Times she fooled the verifier: {num_fooled}")
print(f"Success rate: {num_fooled}/{num_attempts} = {num_fooled/num_attempts:.6f}")
print(f"Expected: 1/q = 1/{q} = {1/q:.6f}")
print()
print(f"With a 256-bit q, the cheating probability would be 1/2^256, negligible.")

Looking Ahead

The Schnorr protocol as presented here is interactive: Alice and Bob must exchange messages in real time. This is fine for identification ("prove you're Alice"), but it limits applications.

In the next notebook (09e), we will see the Fiat-Shamir transform: replace the verifier's random challenge with a hash $c = H(R \| m)$. This converts the interactive Schnorr protocol into:

• Schnorr signatures (non-interactive proofs of knowledge, attached to a message $m$)

• NIZKs (non-interactive zero-knowledge proofs)

This is the bridge from identification to digital signatures, and from interactive proofs to the proof systems used in blockchains.

Summary

Concept	Key idea
The protocol	Prover sends $R = g^k$, receives challenge $c$, responds with $s = k + cx \bmod q$. Verifier checks $g^s = R \cdot y^c$
Completeness	The algebra guarantees honest provers always pass: $g^{k+cx} = g^k \cdot (g^x)^c = R \cdot y^c$
Special soundness	Two transcripts with the same $R$ let anyone extract $x = (s_1 - s_2)/(c_1 - c_2) \bmod q$. A cheating prover cannot answer two challenges
HVZK	A simulator picks $s, c$ at random, computes $R = g^s y^{-c}$, and produces valid transcripts without knowing $x$. Real and simulated transcripts have identical distributions
Nonce discipline	Reusing $k$ is catastrophic, allowing immediate extraction of $x$ by any eavesdropper. This is the same vulnerability that broke PS3 code signing

Next: The Fiat-Shamir Transform, turning interactive proofs into signatures.