OMDL ⇒ Prime-order DLOG

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

If OMDL is hard for a group generator $\mathsf{GrGen}$, then DLOG is hard in prime-order groups for $\mathsf{GrGen}$, with the same advantage — folklore.

Sketch

Given $\ell +1$ challenges, the reduction queries the DL oracle on $X_1,\dots ,X_{\ell }$ and runs the DLOG solver on $X_{\ell +1}$. With $\ell =0$, the OMDL game is the DLOG game.

Notes

• No Turing reduction proves the converse unless DLOG is easy: DLOG is a 2-round assumption, and a reduction that bases OMDL on such an assumption, using the OMDL adversary only as an oracle, yields an efficient algorithm breaking the assumption (barrier) — Pas11.
• Within the hierarchy of one-more problems (OMDL, one-more RSA inversion) there are separations for algebraic reductions; in particular, the unforgeability of Chaum’s RSA blind signatures is unlikely to be provable from RSA alone — BMV08.