DLOG ⇒ Schnorr signatures

Fully-black-box reduction · random oracle model · via Fiat–Shamir · PS96 · security loss: factor $\Theta (q_H)$ in the time-to-success ratio for $q_H$ random-oracle queries

Statement

Schnorr signatures over a group of prime order $p$ — the Fiat–Shamir transform FS86 of the Schnorr identification protocol Sch91 — are EUF-CMA secure in the random-oracle model if DLOG is hard in the group — PS96.

Sketch

The reduction, given $\mathsf{pk}=g^x$, answers signing queries with the HVZK simulator (sample $c,s\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, set $R=g^s{\mathsf{pk}}^{-c}$, program $H(R\Vert m):=c$) and forks the forger: rerunning it on the same coins with $H$ reprogrammed from the query behind the forgery yields two forgeries $(R,c,s)$, $(R,c^{\prime },s^{\prime })$ with $c\ne c^{\prime }$, and $x=(s-s^{\prime })/(c-c^{\prime })\mathrm{mod}p$.

Notes

• In its exact-security form, 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 )$, and it extends to blind signatures — PS00.
• 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 (barrier) — Seu12; no tight generic reduction exists unless DLOG is easy (barrier) — FJS19. For algebraic forgers, the algebraic group model gives a tight reduction (DLOG ⇒ Schnorr signatures (tight, AGM)) — FPS20.
• If DLOG is 2-moment hard, meaning that every algorithm’s success probability is bounded in terms of the second moment of its running time, as in the generic group model, then every $t$-time forger making $q_H$ hash queries succeeds with probability at most $(q_H{t}^2/p{)}^{2/3}$, against $(q_H{t}^2/p{)}^{1/2}$ from earlier proofs — RS21.
• Under the circular discrete-logarithm assumption, a non-interactive, falsifiable variant of DLOG that holds in two idealized models, Schnorr signatures are EUF-CMA secure in the random-oracle model with a completely tight reduction — CFOS25.
• The reduction programs the random oracle. Under OMDL, no algebraic reduction from DLOG exists in the standard model (barrier) — PV05, and no single-instance reduction exists in the non-programmable random-oracle model (barrier) — FF13.
• Efficiency: signing costs one exponentiation and verification one two-base exponentiation, and a signature $(R,s)$ is a group element and a response in ${\mathbb{Z}}_p$, or a challenge and a response in ${\mathbb{Z}}_p$ in the equivalent $(c,s)$ form — standard.