The Discrete-Logarithm Problem with Preprocessing
Host
Albert Kwon
CSAIL, MIT
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).
Our lower bound, which is tight up to logarithmic factors, uses a
synthesis of incompressibility techniques and classic methods for
generic-group lower bounds. We apply our techniques to 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.
BIO
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.
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).
Our lower bound, which is tight up to logarithmic factors, uses a
synthesis of incompressibility techniques and classic methods for
generic-group lower bounds. We apply our techniques to 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.
BIO
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.