The Discrete-Logarithm Problem with Preprocessing.
Henry Corrigan-Gibbs, Dmitry Kogan · IACR Cryptology ePrint Archive · 2017
This paper studies discrete-log algorithms that use preprocessing. In our model, an adversary may use a very large amount of precomputation to produce an “advice” string about a specific group (e.g., NIST P-256). In a subsequent online phase, the adversary’s task is to use the preprocessed advice to quickly compute discrete logarithms in the group. Motivated by surprising recent preprocessing attacks on the discrete-log problem, we study the power and limits of such algorithms.