logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

Rational Reconstruction, Lattices and the BIKE Cryptosystem

Michael Schaller

( University of Zürich )

Salle 285

26 novembre 2026 à 14:00

The rational reconstruction problem is an old problem that asks for a certain solution to a modular equation. If some constraints are satisfied, it can be solved using the extended Euclidean algorithm or via lattice reduction of a rank 2 lattice.

A similar question can be asked over a polynomial ring over a finite field. This problem is related to the secret key in the BIKE cryptosystem. Bardet, Dragoi, Luque, and Otmani used the extended Euclidean algorithm to recover some keys of the BIKE cryptosystem in polynomial time. However, the number of keys that can be recovered with their techniques is very small and a random key can only be recovered with negligible probability.

I will introduce lattices over polynomial rings and show that the authors essentially solve a shortest vector problem in a rank 2 lattice. Instead of finding a shortest vector I will use the lattice perspective to find the successive minima in polynomial time. However, the number of keys that can be recovered using these lattice techniques does not improve much on prior work.

I will highlight some of the challenges that have to be overcome if one wants to make further progress on cryptanalysis of BIKE using polynomial lattice techniques.