Abstracts for Conference on "The Mathematics of Post-Quantum Cryptography"

I will define lattices and discuss some of their basic properties, including Minkowski’s theorem on lattice points in convex bodies. In the setting of algebraic number theory, I will explain how number rings and their ideals come with a natural embedding as lattices in Euclidean spaces.

In this talk, we first give an introduction to algebraic cryptanalysis, before looking into concrete applications to solving hard problems relevant for cryptography. The examples chosen for this talk are equivalence problems. Broadly, an equivalence problem considers two instances of the same mathematical object and asks if there exists a map between them that preserves some defined property. Two such problems will be looked at in detail.

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.

When studying proposed isogeny-based cryptosystems, several computational problems naturally appear: some are upper bounds for the security of the system (if one can solve the problem, then one can break the cryptosystem), some are lower bounds (if one can break the cryptosystem, then one can solve the problem). We would therefore like to understand the relative difficulty of these problems, ideally showing that they are all equivalent.