Structured GGM ⇒ DLOG

Free reduction · generic group model · CHW26 · security loss: time $\Omega (\min (\sqrt{p},1/\delta ))$

Statement

In the structured generic-group model, which extends Shoup’s GGM so that the adversary may exploit the group’s special structure on at most a $\delta$ fraction of group elements and is generic on the rest, every algorithm for DLOG in a group of prime order $p$ runs in time $\Omega \left(\min \left(\sqrt{p},1/\delta \right)\right)$ — CHW26. This gives tight subexponential lower bounds against index-calculus-style algorithms that exploit the multiplicative structure of smooth integers but are otherwise generic — CHW26.

Notes

• The bound is on running time, whereas Shoup’s generic DLOG bound counts group-operation queries — CHW26, Sho97.