Faculty Recruiting

# Lower Bounds on Generic Discrete-logarithm Algorithms via Incompressibility Techniques

01 Mar
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)$.