Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir)

Random oracle model · via Fiat–Shamir · AABN02 · security loss: advantage loss factor about $q_H$ for $q_H$ random-oracle queries

Statement

The Schnorr signature scheme is the Fiat–Shamir transform of the Schnorr identification protocol. For a generator $g$ of a group of prime order $p$ and key pair $(\mathsf{sk},\mathsf{pk})=(x,g^x)$, signing $m$ samples $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ and outputs $(R,s)$ with $R=g^r$, $c=H(R\Vert m)$, $s=r+cx\mathrm{mod}p$; verification checks $g^s=R\cdot {\mathsf{pk}}^c$. The signature is an accepting transcript whose challenge is the hash — Sch91, FS86. The Schnorr protocol’s commitments are uniform in the group, so it is non-trivial, and with $H$ a random oracle the Fiat–Shamir transform of a non-trivial identification scheme secure against impersonation under passive attack is EUF-CMA secure; hence Schnorr signatures are EUF-CMA secure in the random-oracle model whenever the Schnorr identification protocol is secure against passive impersonation — AABN02. A direct proof from DLOG goes through the forking lemma (DLOG ⇒ Schnorr signatures) — PS96.

Sketch

The impersonator guesses which random-oracle query $(R,m)$ the forgery will use, sends that query’s commitment $R$ to the honest verifier, and answers the query with the verifier’s challenge. It answers signing queries with transcripts from its passive-attack oracle, programming $H(R\Vert m):=c$ for each transcript $(R,c,s)$, and replays the forgery’s response, losing a factor about $q_H$ for the guess.

Notes

• The forking lemma turns a forger with success probability $\epsilon$, running time $T$ and $q_H$ random-oracle queries into a DLOG solver of expected running time $O(q_{H}T/\epsilon )$ — PS96.
• That loss is essentially optimal: under OMDL, every algebraic reduction from DLOG to Schnorr forgery in the random-oracle model loses a factor close to $q_H$ in the time-to-success ratio (barrier) — Seu12.
• The identification protocol is perfectly honest-verifier zero-knowledge unconditionally; DLOG underlies its impersonation resistance — standard.