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, and an element $g^x$, determine $x$. We will consider this problem in the context where algorithms are generic, probabilistic, and have preprocessing power. A generic algorithm for the discrete-log problem is one that can operate over any cyclic group. We will take a look at an interesting incompressibility technique used by Corrigan-Gibbs and Kogan (Eurocrypt, 2018) to prove 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)$.
The CICS Theory Seminar is online, free and open to the public. If you are interested in giving a talk, please email Professor Immerman or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.