Schnorr Zero-Knowledge Proofs for Sender Authentication

Tessera authenticates a sender to a recipient with a Schnorr zero-knowledge proof made non-interactive via theFiat–Shamir transform. This post explains the math, why the proof reveals nothing about the secret key, why the transform is secure in the random oracle model, and why Tessera chose Schnorr over the obvious alternatives (ECDSA, Bulletproofs, zk-SNARKs).

The setting

The sender holds a secret key x ∈ Z_q and publishes a public key Y = x · G on the secp256k1 curve. To authenticate a message m to a recipient, the sender must convince the recipient that they know x — without revealing xand without sending Y in the clear (sending Ywould leak the sender's identity to a network observer). Theblinded pseudonym solves the second problem (seethe dedicated post); this post focuses on the proof itself.

Schnorr: the interactive protocol

The interactive Schnorr identification protocol is a three-move Σ-protocol. The prover (sender) wants to convince the verifier (recipient) that they know x such that Y = x · G.

1. Commit. The prover picks a random noncek ∈ Z_q and sends R = k · G to the verifier.
2. Challenge. The verifier sends a random challengec ∈ Z_q.
3. Response. The prover sendss = k + c · x mod q.

The verifier checks s · G = R + c · Y. If the equality holds, the prover almost certainly knows x: with high probabilitys can only satisfy the check if it was computed usingx.

Why it is zero-knowledge

The transcript (R, c, s) can be simulated without knowingx: pick s, c uniformly at random, computeR = s · G − c · Y. The simulated transcript has the same distribution as a real one, so the verifier learns nothing aboutx beyond the fact that the prover knows it. Formally, this ishonest-verifier zero-knowledge (HVZK).

Special soundness

If a prover can answer two different challenges c₁, c₂ on the same commitment R, thens₁ − s₂ = (c₁ − c₂) · x, sox = (s₁ − s₂) / (c₁ − c₂). A single commitment with two accepting responses extracts the secret. This is thespecial soundness property that gives soundness.

The Fiat–Shamir transform

The interactive protocol needs a round trip for the challenge. To make it non-interactive, Fiat–Shamir replaces the verifier's challenge with a hash of the prover's commitment and the message:

c = H(R ‖ Y' ‖ m)  mod q

where Y' is the (blinded) public key used in this delivery and m is the message being authenticated. The verifier recomputes c from the same inputs and checkss · G = R + c · Y'. The proof is now a single pair(R, s) — about 64 bytes on secp256k1.

Security follows in the random oracle model (ROM): the hash is modelled as a truly random function, so a cheating prover cannot pick R to engineer a favourable c. The standard theorem lifts HVZK + special soundness to NIZK soundness under the Fiat– Shamir transform.

Unforgeability: the forking lemma

The signature/proof (R, s) on message m isexistentially unforgeable under chosen-message attack (EUF-CMA) assuming the discrete logarithm problem is hard in the curve group. The argument is the forking lemma:

• Run a forger that produces a valid proof (R, s) with challenge c = H(R ‖ Y' ‖ m).
• Rewind the forger to just before the hash query and answer with a different challenge c' for the same R.
• If the forger succeeds again, you have two accepting responsess, s' on the same R, from whichx = (s − s') / (c − c') is extracted.

So any efficient forger yields an efficient discrete-log solver. Under DLog hardness, no such forger exists. Tessera'sbench_security.py harness (experiment E6) confirms this empirically: across tamper, swap-key, forge, and replay attacks with 5000 trials each, the verifier's false-accept rate (FAR) and false-reject rate (FRR) are both 0/0.

Why Schnorr (and not ECDSA, Bulletproofs, or zk-SNARKs)

Schnorr wins on three axes that matter for Tessera: no trusted setup (SNARKs need a ceremony), compact proofs(Bulletproofs are 10× larger and slower), and transparent security (DLog is well-studied; SNARK assumptions are newer). ECDSA would authenticate but is not zero-knowledge — it sendsY in the clear, defeating the metadata-privacy goal.

Code example

from tessera.crypto import ZKProver, ZKVerifier

prover = ZKProver(secret_key=x)            # x ∈ Z_q
proof = prover.prove(blinded_pubkey=Y_prime, message=m)
# proof = (R, s)  — 64 bytes

verifier = ZKVerifier()
ok = verifier.verify(blinded_pubkey=Y_prime, message=m, proof=proof)
assert ok  # EUF-CMA under DLog

Benchmark numbers

From experiment E1 (bench_crypto.py), single-threaded on a laptop:

• Proof generation: ~0.85 ms
• Proof verification: ~13 ms
• Proof size: 64 bytes (R ‖ s, compressed)
• AES-GCM encrypt (256-bit, 1 KB payload): ~0.02 ms
• FAR / FRR (5000 trials × 4 attack classes): 0 / 0

The proof is fast enough to generate on every delivery, small enough to fit inside a single network packet, and cryptographically tight enough that the verifier never accepts a forgery. Combined with per-recipient blinding (next post) and DP cover traffic, this is the authentication half of Tessera.

Continue with Per-Recipient Blinded Pseudonyms to see how the verifier authenticates without ever seeing Y on the wire.