ABSTRACT

\nIn this talk\, I will present some recent wor
k on discrete-log algorithms that use preprocessing. In our model\, an adv
ersary 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 onlin
e phase\, the adversary's task is to use the preprocessed advice to quickl
y compute discrete logarithms in the group. Motivated by surprising recent
preprocessing attacks on the discrete-log problem\, we study the power an
d limits of such algorithms.

\n

\nIn particular\, we focus on gene
ric algorithms -- these are algorithms that operate in every cyclic group.
We show that any generic discrete-log algorithm with preprocessing that u
ses an S-bit advice string\, runs in online time T\, and succeeds with pro
bability \\epsilon in a group of prime order N must satisfy ST^2 = \\tilde
{\\Omega}(\\epsilon N).

\nUsing similar techniques\, we prove related l
ower bounds for the CDH\, DDH\, and multiple-discrete-log problems.

\n

\nFinally\, we demonstrate two new generic preprocessing attacks: on
e for the multiple-discrete-log problem and one for certain decisional-typ
e problems in groups. This latter result demonstrates that\, for generic a
lgorithms with preprocessing\, distinguishing tuples of the form (g\, g^x\
, g^(x^2)) from random is much easier than the discrete-log problem.

\n

\nThis talk is based on joint work with Dmitry Kogan.

\n

\nH
enry Corrigan-Gibbs is a PhD candidate at Stanford\, advised by Dan Boneh.
He builds systems for messaging\, data analysis\, and web browsing that p
rotect the private data and metadata of their users. For these research ef
forts\, Henry and his co-authors have received the Best Young Researcher P
aper Award at Eurocrypt 2018\, the 2016 Caspar Bowden Award for Outstandin
g Research in Privacy Enhancing Technologies\, and the 2015 IEEE Security
and Privacy Distinguished Paper Award.

\n