Séminaire de Théorie Algorithmique des Nombres

We present a new distinguisher for alternant and Goppa codes, whose complexity is subexponential in the error-correcting capability, hence better than that of generic decoding algorithms. Moreover it does not suffer from the strong regime limitations of the previous distinguishers or structure recovery algorithms: in particular, it applies to the codes used in the Classic McEliece candidate for postquantum cryptography standardization. The invariants that allow us to distinguish are graded Betti numbers of the homogeneous coordinate ring of a shortening of the dual code.

Since its introduction in 1978, this is the first time an analysis of the McEliece cryptosystem breaks the exponential barrier.

We consider the problem of finding the minimum of inhomogeneous Gaussian lattice sums: Given a lattice L in an n-dimensional Euclidean space V and a positive constant a, the goal is to find the points z in V that minimize the sum of the potential exp(-a ||x - z||^2) over all the points x in L.

By a result of Bétermin and Petrache from 2017 it is known that for steep potential energy functions (when a tends to infinity) the minimum in the limit goes to a deep hole of the lattice.

The goal of this talk is to strengthen this result for lattices with a lot of symmetries: We prove that the deep holes of root lattices are already the exact minimizers for all a>a0 for some finite a0. Moreover, we prove that such a stability result can only occur for lattices with strong algebraic structure.

After introducing the problem, we will discuss how to design and solve exactly an LP bound for spherical designs, which allows to prove that the deep holes are local minimizers.

The end of the argument follows from a covering argument involving a precise control of the parameters around the lattice points.

Joint work with C. Bachoc, F. Vallentin and M. Zimmermann

TBD

TBD