No single-instance reduction from DLOG to Schnorr signatures in the non-programmable ROM

Conditional · assuming one-more Discrete Logarithm · FF13

Statement

If OMDL is hard, no single-instance reduction proves the unforgeability of Schnorr signatures from DLOG in the non-programmable random-oracle model, in which the random oracle is external: the reduction may observe the forger’s queries but cannot program the answers — FF13. A single-instance reduction may perform arbitrary computation but runs only one instance of the forger, which it may reset.

Notes

• A meta-reduction ruling out reductions that run several forger instances would itself yield an attack on the strong unforgeability of Schnorr signatures, a meta-meta-reduction, so the technique is unlikely to extend beyond single-instance reductions — FF13.
• Every generic reduction from DLOG to Schnorr signatures in the non-programmable random-oracle model is ruled out unless DLOG is easy, without OMDL — FJS19.
• The forking-lemma reduction programs the random oracle, which is outside the non-programmable model (DLOG ⇒ Schnorr signatures) — PS96.