Faculty Recruiting Support CICS

Theory Seminar: Nikki Sigurdson

22 Sep
Tuesday, 09/22/2020 4:00pm to 5:00pm
Virtual via Zoom
Theory Seminar
Speaker: Nikki Sigurdson

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.