No algebraic reduction from DLOG to Schnorr signatures in the standard model

Conditional · assuming one-more Discrete Logarithm · PV05

Statement

If OMDL is hard, no efficient algebraic reduction turns a forger against Schnorr signatures into a DLOG solver in the standard model, where the hash function is fixed and the reduction cannot program it — PV05. A reduction is algebraic if a representation of every group element it outputs, over the group elements it has received, can be computed efficiently from its input and coins. The result holds already for forgers under key-only attack, which get a public key and a message and return a signature on it without making signing queries; such a forger is also an EUF-CMA forger, so reductions to EUF-CMA security are ruled out too. The same separation covers ElGamal-type signatures, DSA, ECDSA, KCDSA and GQ signatures — PV05.

Sketch

Given OMDL challenges $r_0,r_1,\dots ,r_n$, the meta-reduction runs the reduction on the DLOG instance $r_0$. When the reduction asks for a forgery on $m_i$ under ${\mathsf{pk}}_i$, the meta-reduction sets $R_i=r_i$ and $c_i=H(R_i\Vert m_i)$, and gets $s_i={\log }_g(r_i{\mathsf{pk}}_i^{c_i})$ from its DL oracle. Once the reduction outputs ${\log }_g{r}_0$, the representation of each ${\mathsf{pk}}_i$ over $g$, $r_0$ and the earlier $r_j$ gives, in order of $i$, ${\log }_g{\mathsf{pk}}_i$ and then ${\log }_g{r}_i=s_i-c_i{\log }_g{\mathsf{pk}}_i$: $n+1$ logarithms from $n$ oracle queries.

Notes

• The random-oracle reduction of PS96 programs the hash, which is outside this standard-model scope (DLOG ⇒ Schnorr signatures); restricting the forger instead of the reduction gives a tight reduction in the algebraic group model (DLOG ⇒ Schnorr signatures (tight, AGM)) — FPS20.
• In the random-oracle model, under OMDL, every algebraic reduction from DLOG loses a factor at least $\sqrt{q_h}$ for a forger making $q_h$ hash queries — PV05; the bound is $q_h^{2/3}$ in GBL08 and essentially $q_h$ in Seu12 (barrier).
• In the non-programmable random-oracle model, single-instance reductions from DLOG are ruled out under OMDL (barrier) — FF13.