Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir)

Random oracle model · via Fiat–Shamir · Sch91, FS86 · security loss: factor $\Theta (q_H)$ in the time-to-success ratio 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. With $H$ a random oracle, the scheme is EUF-CMA secure if DLOG is hard in the group — PS96.

Sketch

The reduction answers signing queries with the HVZK simulator, programming $H(R\Vert m):=c$; it runs the forger, rewinds it to the hash query behind the forgery’s challenge, and reprograms the random oracle from there. Two accepting transcripts $(R,c,s)$, $(R,c^{\prime },s^{\prime })$ with $c\ne c^{\prime }$ give $x=(s-s^{\prime })/(c-c^{\prime })\mathrm{mod}p$ (forking lemma).

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.
• The 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 — Seu12.
• The identification protocol is perfectly honest-verifier zero-knowledge unconditionally; DLOG underlies its impersonation resistance — standard.