The Discrete-Logarithm Problem with Preprocessing

ABSTRACT
In this talk, I will present some recent work on 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.
 
In particular, we focus on generic algorithms -- these are algorithms that operate in every cyclic group. We show that any generic discrete-log algorithm with preprocessing that uses an S-bit advice string, runs in online time T, and succeeds with probability \epsilon in a group of prime order N must satisfy ST^2 = \tilde{\Omega}(\epsilon N).
Using similar techniques, we prove related lower bounds for the CDH, DDH, and multiple-discrete-log problems.
 
Finally, we demonstrate two new generic preprocessing attacks: one for the multiple-discrete-log problem and one for certain decisional-type problems in groups. This latter result demonstrates that, for generic algorithms with preprocessing, distinguishing tuples of the form (g, g^x, g^(x^2)) from random is much easier than the discrete-log problem.
 
This talk is based on joint work with Dmitry Kogan.
 
Henry Corrigan-Gibbs is a PhD candidate at Stanford, advised by Dan Boneh. He builds systems for messaging, data analysis, and web browsing that protect the private data and metadata of their users. For these research efforts, Henry and his co-authors have received the Best Young Researcher Paper Award at Eurocrypt 2018, the 2016 Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies, and the 2015 IEEE Security and Privacy Distinguished Paper Award.