09e-fiat-shamir-transform.ipynb

Kernel: SageMath 10.5

The Fiat-Shamir Transform

Module 09e | Commitments and Sigma Protocols

Can a prover create a convincing proof entirely alone, with no verifier in sight?

Motivating Question: Schnorr's protocol (09d) lets Alice prove she knows a secret $x$ to Bob. But it requires real-time interaction: Bob must be online to send a random challenge, and Alice must respond immediately. Can Alice create a proof offline that anyone can verify later, without any back-and-forth?

The answer is yes, and the technique that makes it possible, the Fiat-Shamir transform, is one of the most important ideas in modern cryptography.

Objectives

By the end of this notebook you will be able to:

1. Explain why interactive proofs are impractical for many real-world applications

2. Apply the Fiat-Shamir transform to convert an interactive sigma protocol into a non-interactive proof

3. Construct and verify Schnorr signatures as a direct application of Fiat-Shamir

4. Articulate the Random Oracle Model and its role in the security argument

5. Recognize Fiat-Shamir as the bridge from sigma protocols to SNARKs, signatures, and beyond

Prerequisites

• Completion of The Schnorr Protocol, especially the 3-move structure (commit $R$, challenge $c$, response $s$)

• Familiarity with cryptographic hash functions (the idea that $H$ maps arbitrary data to a fixed-size, unpredictable output)

The Problem: Interaction Is Expensive

Recall the interactive Schnorr protocol from notebook 09d:

1. Prover picks random $k$, sends commitment $R = g^k$

2. Verifier sends random challenge $c \xleftarrow{$} \mathbb{Z}_q$

3. Prover sends response $s = k + c \cdot x \pmod{q}$

4. Verifier checks $g^s = R \cdot y^c$

This works beautifully, but it requires the verifier to be online and engaged at the exact moment of proof. Consider these scenarios:

• Digital signatures: Alice wants to sign a document that anyone can verify, anytime, without Alice being present.

• Blockchain transactions: A proof must be verified by thousands of nodes, not just one interactive partner.

• SNARKs: A prover generates a proof once; it's verified many times by many parties.

In all these cases, interaction is a deal-breaker. We need non-interactive proofs.

The Key Insight: Let a Hash Be the Verifier

The verifier's only job in the Schnorr protocol is to produce a random challenge $c$ after seeing the commitment $R$. The ordering matters: the prover must commit to $R$ before seeing $c$, otherwise they could cheat.

Fiat and Shamir's brilliant idea (1986): replace the verifier with a hash function.

$$c = H(g, \; y, \; R)$$

The prover computes $c$ themselves by hashing the public parameters and their own commitment. If $H$ is a "good" hash function (modeled as a random oracle), then:

• The challenge $c$ is deterministic given $R$, the prover can compute it alone

• But $c$ is unpredictable before choosing $R$, the prover cannot "work backwards" from a desired $c$ to find $R$

• This simulates an honest verifier who picks $c$ at random after seeing $R$

The full non-interactive protocol becomes:

1. Pick random $k$, compute $R = g^k$

2. Compute $c = H(g, y, R)$

3. Compute $s = k + c \cdot x \pmod{q}$

4. Output proof $\pi = (R, s)$

Anyone can verify by recomputing $c = H(g, y, R)$ and checking $g^s = R \cdot y^c$.

Common mistake: "Fiat-Shamir just removes the verifier." It's more subtle than that: the hash replaces the verifier, and it enforces the crucial ordering constraint. A cheating prover who tries to pick $c$ first and then find a matching $R$ would need to invert the hash function, which is computationally infeasible. The hash commits the prover to $R$ before they "see" $c$, even though they compute both.

Setup: Working in a Prime-Order Group

Let's set up a cyclic group of prime order $q$ inside $\mathbb{Z}_p^*$, just as we did in 09d. We'll also define a hash function that maps to $\mathbb{Z}_q$.

import hashlib

# --- Group setup: subgroup of Z_p* of prime order q ---
# We need p = k*q + 1 for some k, where q is prime
q = next_prime(2^128)          # 128-bit prime order (security parameter)
k = 2
while not is_prime(k * q + 1):
    k += 1
p = k * q + 1                  # safe-ish prime

Zp = Zmod(p)
Zq = Zmod(q)

# Find generator g of the order-q subgroup
g_candidate = Zp(2)
g = g_candidate ^ k            # g has order q in Z_p*
assert g != 1 and g^q == 1     # sanity check

print(f'Prime p ({p.nbits()} bits): {p}')
print(f'Order q ({q.nbits()} bits): {q}')
print(f'Generator g: {g}')
print(f'g^q mod p = {g^q}  (confirms order q)')

def hash_to_Zq(*args):
    """
    Hash arbitrary inputs to an element of Z_q.
    This is our 'random oracle', it takes any combination of
    group elements and messages and returns a challenge in Z_q.
    """
    h = hashlib.sha256()
    for arg in args:
        h.update(str(arg).encode())
    # Convert hash digest to an integer mod q
    return Zq(int(h.hexdigest(), 16))

# Quick test: hash some values
print(f'H("hello")     = {hash_to_Zq("hello")}')
print(f'H("hello", g)  = {hash_to_Zq("hello", g)}')
print(f'H(g, g^2)      = {hash_to_Zq(g, g^2)}')
print(f'\nSmall change -> completely different output:')
print(f'H("hello1") = {hash_to_Zq("hello1")}')
print(f'H("hello2") = {hash_to_Zq("hello2")}')

Step 1: Interactive Schnorr (Recap)

Before applying Fiat-Shamir, let's run the interactive Schnorr protocol one more time so the transformation is crystal clear.

# --- Prover's secret and public key ---
x = Zq.random_element()        # secret key
y = g ^ Integer(x)             # public key y = g^x
print(f'Secret x: {x}')
print(f'Public y = g^x: {y}')

# --- INTERACTIVE Schnorr protocol ---
# Step 1: Prover commits
k = Zq.random_element()        # random nonce
R = g ^ Integer(k)             # commitment
print(f'\n--- INTERACTIVE PROTOCOL ---')
print(f'Prover sends R = g^k: {R}')

# Step 2: Verifier challenges (verifier picks random c)
c = Zq.random_element()        # VERIFIER's random challenge
print(f'Verifier sends c: {c}')

# Step 3: Prover responds
s = k + c * x                  # response (in Z_q)
print(f'Prover sends s = k + c*x: {s}')

# Step 4: Verifier checks
lhs = g ^ Integer(s)
rhs = R * y ^ Integer(c)
print(f'\nVerifier checks: g^s == R * y^c')
print(f'  g^s     = {lhs}')
print(f'  R * y^c = {rhs}')
print(f'  Valid: {lhs == rhs}')

Notice the bottleneck: Step 2 requires a live verifier sending a random $c$. The Fiat-Shamir transform eliminates exactly this step.

Step 2: The Fiat-Shamir Transform

We replace the verifier's random challenge with:

$$c = H(g, \; y, \; R)$$

Now the prover computes everything alone. The proof is the pair $(R, s)$.

def fiat_shamir_prove(g, y, x, q):
    """
    Non-interactive proof of knowledge of x such that y = g^x.
    Returns proof (R, s).
    """
    k = Zq.random_element()         # random nonce
    R = g ^ Integer(k)              # commitment
    c = hash_to_Zq(g, y, R)         # <-- THE FIAT-SHAMIR STEP: hash replaces verifier
    s = k + c * x                   # response
    return (R, s)

def fiat_shamir_verify(g, y, R, s):
    """
    Verify a non-interactive proof (R, s) that someone knows x with y = g^x.
    Returns True if valid.
    """
    c = hash_to_Zq(g, y, R)         # recompute the challenge from public data
    lhs = g ^ Integer(s)
    rhs = R * y ^ Integer(c)
    return lhs == rhs

# --- Generate proof (prover works ALONE) ---
R, s = fiat_shamir_prove(g, y, x, q)
print('=== NON-INTERACTIVE PROOF ===')
print(f'Public key y: {y}')
print(f'Proof R: {R}')
print(f'Proof s: {s}')

# --- Verify proof (anyone can do this, anytime) ---
valid = fiat_shamir_verify(g, y, R, s)
print(f'\nVerification result: {valid}')

Checkpoint: Look carefully at the fiat_shamir_prove function. It has the exact same three computations as the interactive protocol ($R = g^k$, $c$, $s = k + cx$). The only difference is where $c$ comes from. In the interactive version, $c$ is received from the verifier. Here, $c = H(g, y, R)$ is computed by the prover.

The verifier in fiat_shamir_verify never needs to talk to the prover. They just recompute $c$ from the proof and check the equation. The proof is self-contained.

Why Can't a Cheating Prover Forge a Proof?

Let's think about what a cheating prover (who does NOT know $x$) would need to do.

Cheat attempt 1: Choose $c$ first, then find matching $R$.

In the interactive protocol, the simulator (from 09d) works backwards: pick $s$ and $c$ first, then compute $R = g^s \cdot y^{-c}$. This produces a valid-looking transcript. But with Fiat-Shamir, the challenge is $c = H(g, y, R)$. So the cheater would need to find $R$ such that $H(g, y, R) = c$, inverting the hash function! This is infeasible.

Cheat attempt 2: Choose $R$ first, get $c$, then find $s$.

After choosing $R$ and computing $c = H(g, y, R)$, the cheater needs $s$ with $g^s = R \cdot y^c$. Without knowing $x$, this means solving a discrete log. Also infeasible.

The hash function traps the cheater: no matter which order they try, one step requires solving a hard problem.

# Let's watch a cheater fail!
# A prover who does NOT know x tries to create a valid proof.

print('=== CHEATER\'S ATTEMPT ===')
print('The cheater knows g, y but NOT x.\n')

# Attempt: pick s randomly, try to find R that makes everything consistent
s_fake = Zq.random_element()
c_desired = Zq.random_element()  # cheater wants this challenge

# Compute R that would be consistent with s_fake and c_desired
R_fake = g ^ Integer(s_fake) * y ^ Integer(-c_desired)
print(f'Cheater picks s = {s_fake}')
print(f'Cheater wants c = {c_desired}')
print(f'Cheater computes R = g^s * y^(-c) = {R_fake}')

# But the actual challenge is determined by the hash!
c_actual = hash_to_Zq(g, y, R_fake)
print(f'\nActual challenge c = H(g, y, R) = {c_actual}')
print(f'Desired challenge c             = {c_desired}')
print(f'Match? {c_actual == c_desired}')

# Verification will fail
valid = fiat_shamir_verify(g, y, R_fake, s_fake)
print(f'\nVerification of fake proof: {valid}')

From Proofs to Signatures: Adding a Message

Here's where Fiat-Shamir gets even more powerful. If we include a message $m$ in the hash:

$$c = H(g, \; y, \; R, \; m)$$

then the proof becomes bound to that message. The result is a digital signature scheme:

• Key generation: secret $x$, public $y = g^x$

• Sign: pick random $k$, compute $R = g^k$, $c = H(g, y, R, m)$, $s = k + cx$. Signature: $(R, s)$

• Verify: recompute $c = H(g, y, R, m)$, check $g^s = R \cdot y^c$

This is exactly the Schnorr signature scheme, the basis of EdDSA/Ed25519, used in SSH keys, TLS, and cryptocurrency.

The signature proves: "The holder of the secret key corresponding to $y$ endorses message $m$." No interaction needed.

def schnorr_keygen():
    """Generate a Schnorr key pair."""
    x = Zq.random_element()         # secret key
    y = g ^ Integer(x)              # public key
    return x, y

def schnorr_sign(x, message):
    """
    Sign a message using Schnorr signature (= Fiat-Shamir on Schnorr protocol + message).
    Returns signature (R, s).
    """
    k = Zq.random_element()                     # random nonce
    R = g ^ Integer(k)                          # commitment
    c = hash_to_Zq(g, y, R, message)            # challenge includes the message!
    s = k + c * x                               # response
    return (R, s)

def schnorr_verify(y, message, R, s):
    """
    Verify a Schnorr signature (R, s) on a message.
    Returns True if the signature is valid.
    """
    c = hash_to_Zq(g, y, R, message)            # recompute challenge
    return g ^ Integer(s) == R * y ^ Integer(c)

# --- Demo: sign and verify a message ---
x_signer, y_signer = schnorr_keygen()
message = "Transfer 10 BTC to Alice"

R_sig, s_sig = schnorr_sign(x_signer, message)

print('=== SCHNORR SIGNATURE ===')
print(f'Message: "{message}"')
print(f'Public key y: {y_signer}')
print(f'Signature R:  {R_sig}')
print(f'Signature s:  {s_sig}')
print(f'\nSignature valid: {schnorr_verify(y_signer, message, R_sig, s_sig)}')

# --- Signatures bind to the message: tampering is detected ---
print('=== SIGNATURE BINDING ===')
print(f'Original message: "{message}"')
print(f'Signature valid for original: {schnorr_verify(y_signer, message, R_sig, s_sig)}')

tampered = "Transfer 1000 BTC to Mallory"
print(f'\nTampered message: "{tampered}"')
print(f'Signature valid for tampered: {schnorr_verify(y_signer, tampered, R_sig, s_sig)}')

# Also fails with a different public key (non-repudiation)
_, y_other = schnorr_keygen()
print(f'\nSignature valid for different key: {schnorr_verify(y_other, message, R_sig, s_sig)}')

print('\n--> The signature is bound to BOTH the message and the signer.')

Checkpoint: Sign and verify by hand. Before running the next cell, work through this small example on paper or in your head.

Let $p = 23$, $q = 11$, $g = 4$ (which has order 11 mod 23). Secret key $x = 7$, so $y = 4^7 \bmod 23$.

1. Compute $y$.

2. Choose nonce $k = 3$. Compute $R = g^k \bmod p$.

3. Suppose $c = H(g, y, R, m) = 5$ (just pretend the hash gave us 5).

4. Compute $s = k + c \cdot x \pmod{q}$.

5. Verify: check that $g^s \equiv R \cdot y^c \pmod{p}$.

# Hand-calculation verification with small numbers
p_small, q_small = 23, 11
g_small = Mod(4, p_small)
assert g_small^q_small == 1  # g has order q

x_small = 7
y_small = g_small ^ x_small
print(f'y = g^x = 4^7 mod 23 = {y_small}')

k_small = 3
R_small = g_small ^ k_small
print(f'R = g^k = 4^3 mod 23 = {R_small}')

c_small = Mod(5, q_small)  # pretend hash gave us 5
s_small = Mod(k_small + 5 * x_small, q_small)
print(f's = k + c*x = 3 + 5*7 = 38 mod 11 = {s_small}')

# Verify
lhs_small = g_small ^ Integer(s_small)
rhs_small = R_small * y_small ^ Integer(c_small)
print(f'\nVerification:')
print(f'  g^s     = 4^{s_small} mod 23 = {lhs_small}')
print(f'  R * y^c = {R_small} * {y_small}^5 mod 23 = {R_small} * {y_small^5} = {rhs_small}')
print(f'  Match: {lhs_small == rhs_small}')

The Random Oracle Model

Why does Fiat-Shamir work? The security proof relies on a powerful assumption called the Random Oracle Model (ROM).

A random oracle is an idealized hash function with these properties:

1. Deterministic: The same input always gives the same output.

2. Uniformly random: For any new input, the output is uniformly random in the output space.

3. Independent: Knowing $H(x_1), H(x_2), \ldots$ gives no information about $H(x')$ for any new $x'$.

Under the ROM, the hash output $c = H(g, y, R)$ is indistinguishable from a truly random challenge, exactly what the honest verifier would have sent. This means:

• The prover cannot predict $c$ before committing to $R$ (since $H$ is "random" on new inputs)

• The prover cannot find two different $R$ values giving the same $c$ (collision resistance)

• The security of the interactive protocol transfers to the non-interactive version

In practice, we use SHA-256 or SHA-3 as the hash function. These are not true random oracles (no real function can be), but they are close enough that Fiat-Shamir-based schemes have been secure for decades.

# Demonstrating "random oracle" behavior of SHA-256:
# Small changes in input produce completely unpredictable output changes

print('Hash outputs for sequential R values:')
print('(If H were predictable, these would show a pattern.)\n')

base = Integer(g)
for i in range(8):
    R_test = Zp(base + i)
    c_test = hash_to_Zq(g, y, R_test)
    # Show last 16 hex digits for readability
    c_hex = hex(Integer(c_test))[-16:]
    print(f'  R = g+{i}: c = ...{c_hex}')

print('\n--> No visible pattern. Each output looks independent and random.')
print('    This is the "random oracle" property in action.')

Common mistake: "The Random Oracle Model means we assume SHA-256 is perfect." Not quite. The ROM is a proof technique: we prove security assuming an ideal hash, then instantiate with a real hash like SHA-256. This is a heuristic, there exist (artificial) schemes that are secure in the ROM but broken with any real hash function. In practice, Fiat-Shamir with SHA-256 has an excellent track record, but the distinction between the model and reality is important for theory.

Side-by-Side: Interactive vs. Non-Interactive

Let's run both protocols on the same secret and compare.

# Same key pair for both
x_demo = Zq.random_element()
y_demo = g ^ Integer(x_demo)

print('INTERACTIVE SCHNORR'.center(60))

# Interactive: requires 3 messages between prover and verifier
k1 = Zq.random_element()
R1 = g ^ Integer(k1)
print(f'  Prover  --> Verifier:  R = {str(R1)[:40]}...')
c1 = Zq.random_element()       # verifier picks random challenge
print(f'  Verifier --> Prover:   c = {c1}')
s1 = k1 + c1 * x_demo
print(f'  Prover  --> Verifier:  s = {s1}')
check1 = g ^ Integer(s1) == R1 * y_demo ^ Integer(c1)
print(f'  Verifier checks: {check1}')
print(f'  Messages exchanged: 3 (requires live interaction)\n')

print('NON-INTERACTIVE (FIAT-SHAMIR)'.center(60))

# Non-interactive: prover works alone, publishes proof
k2 = Zq.random_element()
R2 = g ^ Integer(k2)
c2 = hash_to_Zq(g, y_demo, R2)   # hash replaces verifier
s2 = k2 + c2 * x_demo
print(f'  Prover computes R = {str(R2)[:40]}...')
print(f'  Prover computes c = H(g,y,R) = {c2}')
print(f'  Prover computes s = {s2}')
print(f'  Prover publishes proof: (R, s)\n')

# Anyone verifies, anytime
c2_check = hash_to_Zq(g, y_demo, R2)
check2 = g ^ Integer(s2) == R2 * y_demo ^ Integer(c2_check)
print(f'  Any verifier recomputes c = H(g,y,R) = {c2_check}')
print(f'  Any verifier checks: {check2}')
print(f'  Messages exchanged: 0 (no interaction needed!)')

Caveats and Practical Considerations

Fiat-Shamir is powerful but comes with important caveats:

1. Nonce reuse is catastrophic. If the prover ever uses the same $k$ for two different signatures on messages $m_1$ and $m_2$, the secret key $x$ can be extracted:

• Same $R$ means same $k$ was used

• Two equations: $s_1 = k + c_1 x$ and $s_2 = k + c_2 x$

• Subtract: $s_1 - s_2 = (c_1 - c_2) x$, so $x = (s_1 - s_2) / (c_1 - c_2)$

This is how Sony's PS3 ECDSA key was broken in 2010, they used a fixed $k$ for every signature!

2. Hash function must include all public parameters. Omitting $g$ or $y$ from the hash can create subtle vulnerabilities.

3. The Random Oracle Model is a heuristic. While Fiat-Shamir works well in practice, there are theoretical separations between the ROM and the real world.

# DANGER: Nonce reuse breaks everything!
# Let's demonstrate the PS3-style attack.

x_victim = Zq.random_element()
y_victim = g ^ Integer(x_victim)

# Victim signs two different messages with the SAME nonce k
k_reused = Zq.random_element()    # FATAL MISTAKE: same k for both!
R_reused = g ^ Integer(k_reused)  # same R for both signatures

m1, m2 = "message one", "message two"
c1 = hash_to_Zq(g, y_victim, R_reused, m1)
c2 = hash_to_Zq(g, y_victim, R_reused, m2)
s1 = k_reused + c1 * x_victim
s2 = k_reused + c2 * x_victim

print('=== NONCE REUSE ATTACK ===')
print(f'Attacker observes two signatures with same R:')
print(f'  sig1: R = {str(R_reused)[:30]}..., s1 = {s1}, c1 = {c1}')
print(f'  sig2: R = {str(R_reused)[:30]}..., s2 = {s2}, c2 = {c2}')

# Attacker extracts the secret key!
x_recovered = (s1 - s2) / (c1 - c2)   # simple algebra in Z_q
print(f'\nAttacker computes x = (s1-s2)/(c1-c2) = {x_recovered}')
print(f'Actual secret key x                    = {x_victim}')
print(f'Keys match: {x_recovered == x_victim}')
print(f'\n--> SECRET KEY COMPLETELY COMPROMISED from just two signatures!')

Exercises

Exercise 1 (Worked)

Implement the Fiat-Shamir transform for a modified Schnorr protocol that proves knowledge of $x$ such that $y = g^x$, but uses a different group. Work with $p = 467$, $q = 233$, $g = 4$ (which has order 233 mod 467). Sign the message $m =$ "Exercise 1" with secret key $x = 42$.

Steps:

1. Compute the public key $y = g^x \bmod p$

2. Choose nonce $k = 100$, compute $R = g^k \bmod p$

3. Compute challenge $c = H(g, y, R, m) \bmod q$

4. Compute response $s = k + c \cdot x \bmod q$

5. Verify the signature $(R, s)$

# Exercise 1: Worked solution
p1, q1 = 467, 233
g1 = Mod(4, p1)
assert g1^q1 == 1, "g does not have order q"

# Step 1: Key generation
x1 = 42
y1 = g1 ^ x1
print(f'Public key y = g^42 mod 467 = {y1}')

# Step 2: Commitment
k1_ex = 100
R1_ex = g1 ^ k1_ex
print(f'Commitment R = g^100 mod 467 = {R1_ex}')

# Step 3: Fiat-Shamir challenge
Zq1 = Zmod(q1)

def hash_to_Zq1(*args):
    h = hashlib.sha256()
    for arg in args:
        h.update(str(arg).encode())
    return Zq1(int(h.hexdigest(), 16))

m1 = "Exercise 1"
c1_ex = hash_to_Zq1(g1, y1, R1_ex, m1)
print(f'Challenge c = H(g, y, R, m) mod 233 = {c1_ex}')

# Step 4: Response
s1_ex = Zq1(k1_ex + Integer(c1_ex) * x1)
print(f'Response s = k + c*x mod 233 = {s1_ex}')

# Step 5: Verification
c1_verify = hash_to_Zq1(g1, y1, R1_ex, m1)
lhs1 = g1 ^ Integer(s1_ex)
rhs1 = R1_ex * y1 ^ Integer(c1_verify)
print(f'\nVerification:')
print(f'  g^s     = {lhs1}')
print(f'  R * y^c = {rhs1}')
print(f'  Valid: {lhs1 == rhs1}')

Exercise 2 (Guided)

Demonstrate the nonce reuse attack on the small group from Exercise 1. Use the same $p = 467$, $q = 233$, $g = 4$, $x = 42$.

1. Sign two different messages $m_1 =$ "Transfer 5 coins" and $m_2 =$ "Transfer 50 coins" using the same nonce $k = 77$.

2. Recover the secret key $x$ from the two signatures.

3. Verify your recovered $x$ matches the original.

Hint: From $s_1 = k + c_1 x$ and $s_2 = k + c_2 x$, subtract to eliminate $k$.

# Exercise 2: Fill in the TODOs
# Use p1, q1, g1, Zq1, hash_to_Zq1, x1, y1 from Exercise 1

k_bad = Zq1(77)  # SAME nonce for both signatures (the fatal mistake)
R_bad = g1 ^ Integer(k_bad)

msg1 = "Transfer 5 coins"
msg2 = "Transfer 50 coins"

# TODO: Sign msg1, compute c1, s1
# c1 = hash_to_Zq1(...)
# s1 = ...

# TODO: Sign msg2, compute c2, s2
# c2 = hash_to_Zq1(...)
# s2 = ...

# TODO: Recover x from the two signatures
# x_recovered = (s1 - s2) / (c1 - c2)  # in Z_q

# TODO: Verify your recovered x matches the original
# print(f'Recovered x: {x_recovered}')
# print(f'Original x:  {x1}')
# print(f'Match: {x_recovered == Zq1(x1)}')

Exercise 3 (Independent)

Implement a batch verification system. Given a list of 5 signed messages (all from the same signer), verify all signatures and report which are valid. Then:

1. Generate a key pair and sign 5 different messages.

2. Tamper with one of the messages (change its text but keep the original signature).

3. Run your batch verifier and confirm it catches the tampered signature.

4. Time the verification: how long does it take to verify 5 signatures vs. 50 vs. 500?

Use the full-size group ($p$, $q$, $g$) from the main setup, not the small Exercise 1 group.

# Exercise 3: Your code here

Summary

Concept	Key idea
The core idea	Replace the verifier's random challenge with a hash: $c = H(g, y, R)$. The prover computes everything alone, and anyone can verify later
Schnorr signatures	The direct result of applying Fiat-Shamir to the interactive Schnorr protocol, with the message included in the hash
Random Oracle Model	The security argument treats the hash as an ideal random function that prevents the prover from cheating the challenge
Nonce reuse is fatal	Using the same random $k$ twice leaks the secret key via simple algebra

Crypto foreshadowing: The Fiat-Shamir transform is not limited to Schnorr. It applies to any sigma protocol (and more general interactive proofs). This is the engine behind:

• Ed25519 / EdDSA, the dominant signature scheme in modern systems (SSH, TLS, crypto wallets)

• SNARKs (Module 10), Fiat-Shamir converts interactive SNARK verification into a single non-interactive proof

• STARKs (Module 10), built entirely on Fiat-Shamir applied to the FRI protocol

• Every non-interactive zero-knowledge proof you'll encounter in practice

What you've learned in this notebook is the single most important bridge between the theory of sigma protocols and the practice of modern cryptographic systems.