No tight generic reduction from DLOG to Schnorr signatures

Conditional · assuming DLOG in prime-order groups · FJS19

Statement

There is no tight generic reduction from DLOG to the security of Schnorr signatures in the random-oracle model unless DLOG is easy, and the same holds for any natural non-interactive computational problem defined over the group, such as CDH or DDH. A reduction is generic if it does not depend on the representation of the group elements. The meta-reduction turns any such reduction into an efficient solver for the problem, without OMDL or any other further assumption — FJS19.

Notes

• The same technique rules out every generic reduction, tight or not, from such problems to Schnorr signatures in the non-programmable random-oracle model — FJS19.
• Unlike the bounds of PV05 and Seu12 (barrier), this result does not rest on OMDL — FJS19.
• The journal version corrects the proof of the conference version FJS14 and states the result for non-interactive problems — FJS19.
• A tight reduction from DLOG exists for algebraic forgers in the algebraic group model (DLOG ⇒ Schnorr signatures (tight, AGM)) — FPS20.