Séminaire de Théorie Algorithmique des Nombres

The McEliece scheme enjoys small ciphertexts, but suffers from a large public key. To reduce sizes, many attempts have been made to instantiate the McEliece scheme with rank metric Gabidulin codes instead of Hamming metric Goppa codes. However they were all broken due to the strong Fqm-linear structure of Gabidulin codes. In the present work, we suggest a new masking of Gabidulin codes. Our masking consists in computing a matrix version of the rank metric vector code C, then in breaking the Fqm-linearity by concatenating a number of rows and columns to the matrix code version of C, before applying an isometry for matrix codes, i.e. right and left multiplications by fixed random matrices. The security of the schemes relies on the MinRank problem to decrypt a ciphertext, and the structural security of the scheme relies on the new EGMC-Indistinguishability problem that we introduce and that we study in detail. In this talk, we will present our main structural attack that consists in recovering the masked linearity over the extension field which has been lost during the masking process. Overall, we obtain a very appealing trade-off between the size of the ciphertext and the size of the public key. For 128 bits of security we propose parameters ranging from ciphertexts of size 65 B (and public keys of size 98kB) to ciphertexts of size 138B (and public keys of size 41 kB).

The period matrix of a smooth complex projective variety encodes the isomorphism between its singular homology and its algebraic De Rham cohomology. Numerical approximations with sufficient precision of the entries of the period matrix may be used to study transcendental properties of varieties. Such numbers also arise in the Birch and Swinnerton-Dyer conjecture, as well as its generalisations in higher dimensions, such as the Deligne conjecture. Approximations of the periods can be obtained from an effective description of the homology of the variety, which itself can be obtained from the monodromy representation associated to a generic fibration. We will describe these methods and show how they can be used to generate numerical evidence of the Deligne conjecture for certain Calabi-Yau threefolds.

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