No tight algebraic reduction from DLOG to Schnorr signatures in the ROM

Conditional · assuming one-more Discrete Logarithm · Seu12

Statement

If OMDL is hard, every algebraic reduction in the random-oracle model that turns a forger against Schnorr signatures into a DLOG solver loses a factor $f({\epsilon }_F)q_h$ in its time-to-success ratio, where the forger makes $q_h$ random-oracle queries and succeeds with probability ${\epsilon }_F$, and $f$ is close to $1$ as long as ${\epsilon }_F$ is noticeably smaller than $1$. For algebraic reductions whose cost is measured by expected time and expected number of queries, the loss is $\Omega (q_h)$, independent of ${\epsilon }_F$ — Seu12. The forking-lemma reduction of PS96, which loses $O(q_h)$, is therefore essentially optimal among algebraic reductions. The result extends to Schnorr-type signatures from other one-way group homomorphisms, such as Guillou–Quisquater signatures — Seu12.

Notes

• Earlier OMDL-conditional lower bounds for algebraic random-oracle reductions are $\sqrt{q_h}$ — PV05 — and $q_h^{2/3}$ — GBL08.
• Restricting the forger rather than the reduction to be algebraic gives a tight reduction from DLOG (DLOG ⇒ Schnorr signatures (tight, AGM)) — FPS20.
• Without assuming OMDL, no tight generic reduction exists unless DLOG is easy (barrier) — FJS19.
• The bound concerns reductions from DLOG. Schnorr signatures are tightly secure in the random-oracle model under the circular discrete-logarithm assumption, a non-interactive, falsifiable variant of DLOG that holds in two idealized models — CFOS25.