GGM with preprocessing ⇒ DLOG

Free reduction · generic group model · CK18 · security loss: success probability $\epsilon =\tilde{O}(S{T}^2/N)$ for $S$ bits of advice and $T$ online queries

Statement

In the generic group model with preprocessing, let a generic DLOG algorithm in a group of prime order $N$ get $S$ bits of advice from an unbounded preprocessing phase and make $T$ online group-oracle queries. If it succeeds with probability $\epsilon$, then $S{T}^2=\tilde{\Omega }(\epsilon N)$, and the bound is tight up to logarithmic factors — CK18. The same techniques give lower bounds for CDH, DDH and the multiple-discrete-logarithm problem — CK18.

Notes

• Generic discrete-logarithm algorithms with precomputation that store $S=\tilde{O}(N^{1/3})$ bits and run online in time $T=\tilde{O}(N^{1/3})$, after a precomputation of about $N^{2/3}$ group operations, meet the bound at constant success probability — BL13a.
• CK18 also give new generic preprocessing attacks, on the multiple-discrete-logarithm problem and on distinguishing $(g,g^x,g^{x^2})$ from random, the latter far easier for generic preprocessing algorithms than DLOG — CK18.