BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:The Discrete-Logarithm Problem with Preprocessing
DTSTART:20180614T101500
DTEND:20180614T120000
DTSTAMP:20260410T034210Z
UID:ff488349f5b24facc3fc76c531c5fabd1719d28230c1b732f5cd9263
CATEGORIES:Conferences - Seminars
DESCRIPTION:Henry Corrigan-Gibbs\, Stanford University\nABSTRACT\nIn 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 discret
 e-log problem\, we study the power and limits of such algorithms.\n \nIn 
 particular\, we focus on generic algorithms -- these are algorithms that o
 perate in every cyclic group. We show that any generic discrete-log algori
 thm with preprocessing that uses an S-bit advice string\, runs in online t
 ime T\, and succeeds with probability \\epsilon in a group of prime order 
 N must satisfy ST^2 = \\tilde{\\Omega}(\\epsilon N).\nUsing similar techni
 ques\, we prove related lower bounds for the CDH\, DDH\, and multiple-disc
 rete-log problems.\n \nFinally\, we demonstrate two new generic preproces
 sing attacks: one for the multiple-discrete-log problem and one for certai
 n decisional-type problems in groups. This latter result demonstrates that
 \, for generic algorithms with preprocessing\, distinguishing tuples of th
 e form (g\, g^x\, g^(x^2)) from random is much easier than the discrete-lo
 g 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 
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR