DLOG ⇒ Schnorr signatures

Fully-black-box reduction · random oracle model · via Fiat–Shamir · Sch91, FS86, 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 — Seu12.
• 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.