Schnorr Identification and Signatures
Stub. Schnorr's identification protocol (prove knowledge of a discrete log interactively, in three moves) and its honest-verifier zero-knowledge property; the Fiat-Shamir-style transformation from identification protocols to signatures in general, a full security analysis of the resulting Schnorr signature scheme (against repeated-impersonation-style attacks), a concrete optimized implementation, and ECDSA as the deployed case study.
Corresponds to Chapter 19.1–19.3, entirely new territory — our existing signature coverage (digital-signatures-and-pki) is RSA/hash- based, not discrete-log-based. Schnorr’s identification protocol is the prototype: the prover commits to a random group element, the verifier sends a random challenge, and the prover responds with a value only someone who knows the discrete log could compute correctly — three moves, and provably honest-verifier zero-knowledge (a simulator can produce transcripts indistinguishable from real ones, without knowing the secret, given it gets to choose the challenge). Turning this into a signature scheme (replace the verifier’s random challenge with a hash of the commitment and the message — an instance of the general transformation developed fully in sigma-protocols-and-the-fiat-shamir-transform) gives the Schnorr signature, whose security against a general class of impersonation attacks is analyzed in detail, together with a concrete, optimized implementation. ECDSA (the elliptic-curve variant actually deployed in TLS, Bitcoin, and elsewhere) is covered as the real-world case study.
Outline (TODO — flesh out each)
- Schnorr’s identification protocol
- Honest-verifier zero knowledge; security against eavesdropping
- From identification protocols to signatures
- Repeated impersonation attacks — a useful abstraction
- Security analysis of Schnorr signatures
- A concrete implementation and an optimization
- Case study: ECDSA signatures