DLOG ⇒ Schnorr signatures (tight, AGM)

Algebraic group model + random oracle model · FPS20 · security loss: tight: the DLOG solver has essentially the forger’s running time and advantage

Statement

In the algebraic group model, with the hash modeled as a random oracle, EUF-CMA security of Schnorr signatures reduces tightly to DLOG in the group: every algebraic forger yields a DLOG solver with essentially the same running time and advantage, and the reduction runs the forger once, without rewinding — FPS20.

Sketch

The reduction embeds the DLOG instance as $\mathsf{pk}$ and answers signing queries with the HVZK simulator, programming $H$. An algebraic forger outputs, with each group element it outputs or queries to $H$, a representation over the elements it has received; substituting $R_i=g^{s_i}{\mathsf{pk}}^{-c_i}$ for the simulated commitments turns it into $R^{\ast }=g^a{\mathsf{pk}}^b$, fixed before $c^{\ast }=H(R^{\ast }\Vert m^{\ast })$ is sampled. A valid forgery $g^{s^{\ast }}=R^{\ast }{\mathsf{pk}}^{c^{\ast }}$ then gives ${\log }_g\mathsf{pk}=(s^{\ast }-a)/(b+c^{\ast })\mathrm{mod}p$ unless $c^{\ast }=-b$, which happens with probability $1/p$ per hash query.

Notes

• The theorem covers only algebraic forgers, whereas the lower bounds for algebraic reductions in the random-oracle model (Seu12) and for generic reductions (FJS19) concern reductions that work for every forger, so they do not apply — FPS20.
• Without the algebraic group model, the forking-lemma reduction from DLOG loses a factor about $q_H$ in the time-to-success ratio (DLOG ⇒ Schnorr signatures) — PS96.
• Hardness in the algebraic group model need not transfer to the generic group model under the standard formalizations (No reduction from AGM to GGM) — KZ22.