Title: Lower Bounds on Generic Adversaries for the Discrete Logarithm Problem
Abstract: The discrete logarithm problem plays an important role in cryptography. The problem can be stated in the following way: given a generator g of a cyclic group G = Z_n, and an element g^x \in G, determine x. A generic algorithm for the discrete logarithm is one that works over any choice of n. We will take a look at some results by Shoup (Eurocrypt, 1997) that show any generic algorithm that solves the discrete logarithm problem on Z_n must perform at least \Omega(p^{1/2}) group operations, where p is the largest prime dividing n. Shoup's bound is tight because the baby-step giant-step algorithm achieves this runtime. We will also look at recent results by Corrigan-Gibbs and Kogan (Eurocrypt, 2017) that generalize Shoup's result to the context of adversaries with preprocessing.
To join this virtual meeting via Zoom, click here. This Zoom meeting requires a passcode. Email organizers Cameron Musco or Rik Sengupta if you need the Zoom passcode, or see emails on the seminars list.