Tutte Colloquium - Daniel Panario

Title: Probabilistic root finding in code-based cryptography

Abstract: Factorization of polynomials over finite fields, and the particular subproblem of finding roots of polynomials, have many applications in diverse areas such as computer algebra, cryptography and coding theory, among many others. In practice, fast factorization algorithms are probabilistic.One area where root-finding algorithms have been recently used is code-based post-quantum cryptography (PQC). These algorithms are required in some code-based cryptosystems present in the NIST PQC standardization process, like Classical McEliece and HQC (Hamming Quasi-Cyclic). However, the root finding methods used in these systems are deterministic (exhaustive search and additive FFT algorithm, respectively).

Probabilistic algorithms for finding roots of polynomials have not been, so far, applied to code-based cryptography. One obstacle is their non-constant execution time, since runtime variations can be exploited by side channel attack techniques. In this work we aim at a constant-time approach to probabilistic root-finding algorithms so cryptosystems can benefit from these algorithms' efficiency, especially when considering larger parameters. 

We provide countermeasures that prevent the execution time of a probabilistic root-finding algorithm to depend on the degree of the input polynomial and makes it dependent only on the cryptosystem parameters. We compare the performance of our proposal to other root-finding algorithms already used in code-based cryptography and related works. We also show that our countermeasure can be applied to other root-finding algorithms successfully. In general, our method is faster than a variant of the Berlekamp Trace Algorithm, the exhaustive algorithm in Classic McEliece and the additive Fast Fourier Transform algorithm for plausible parameters with slightly larger finite fields than the currently being used.