No fully-black-box reduction from bounded-round assumptions to OMDL

Unconditional · against fully-black-box reductions · Pas11

Statement

Consider an intractability assumption given by a possibly unbounded challenger that interacts with the adversary in an a priori fixed polynomial number of rounds (bounded-round assumptions). If a Turing reduction, which uses the adversary only as an oracle, proves OMDL hard from such an assumption, then the assumption is false — Pas11. This follows from one theorem, which also covers the security of the Schnorr identification scheme and of commitments secure under adaptive selective decommitment: Turing reductions cannot base the security of constant-round, sequentially witness-hiding, special-sound protocols for unique-witness relations on such assumptions, even when the protocol uses the assumption in a non-black-box way — Pas11.

Notes

• DLOG is a 2-round assumption, so no Turing reduction bases OMDL on DLOG unless DLOG is easy, although OMDL implies DLOG (OMDL ⇒ Prime-order DLOG) — Pas11.
• OMDL holds in the generic group model (GGM ⇒ OMDL) — BFP21.
• For algebraic reductions, there are separations within the hierarchy of one-more problems (OMDL, one-more RSA inversion) — BMV08.