GGM ⇒ OMDL

Free reduction · generic group model · BFP21

Statement

In the generic group model, OMDL holds in groups of prime order $p$: every generic algorithm that makes polynomially many group-oracle queries and at most $\ell$ discrete-logarithm oracle queries outputs the logarithms of all $\ell +1$ challenges with negligible probability — BFP21. The proof replaces the Schwartz–Zippel argument of earlier generic-group proofs, such as that of GGM ⇒ DLOG (Sho97), with a new argument, and an earlier claimed generic-group proof of OMDL is flawed — BFP21. The one-more computational Diffie–Hellman assumption also holds in the generic group model — BFP21.

Notes

• No Turing reduction bases OMDL on an assumption with an a priori bounded number of rounds unless that assumption is false (barrier) — Pas11.