This meeting – on Friday 2 October 2020 – is aimed at non-lattice approaches to post-quantum cryptography. It will consist of several talks on related topics, with a format aimed at encouraging interaction.
Rank metric codes are codes on matrices, where the distance is the so-called rank metric (the rank of the difference between two matrices). These codes have notably been proposed in several post-quantum, code-based, cryptosystems. In this talk, we will review some of the main properties and results on those codes, including: how they can be viewed as codes on matrices or on vectors, the class of optimal Gabidulin codes and maximum rank-distance (MRD) codes in general, their proposed applications to data storage and network coding, and the use of skew-polynomial rings. We will also indicate which areas of that theory are still under development.
The security of many cryptographic protocols in use today relies on the computational hardness of mathematical problems such as integer factorization. These problems can be solved using quantum computers, and therefore most of our security infrastructures will become completely insecure once quantum computers are built. Post-quantum cryptography aims at developing security protocols that will remain secure even after quantum computers are built. The biggest security agencies in the world including GCHQ and the NSA have recommended a move towards post-quantum protocols, and the new generation of cryptographic standards will aim at post-quantum security. In this talk I will discuss isogeny-based cryptography, a particular family of protocols that are considered for post-quantum security. Isogeny-based protocols have appealing properties including the shortest key sizes among post-quantum cryptography candidates, practical constructions for key exchange and signature, and a clear mathematical elegance.
In the last decade, rank metric code-based cryptography has proved to be a powerful alternative to traditional code-based cryptography based on the Hamming metric. Rank metric analogues of the NTRU cryptosystem have been proposed for instance and this thread of research has led to a sequence of proposals to the NIST post-quantum competition, such as for instance Ouroboros-R and RQC, whose security relies solely on decoding codes in rank metric with a ring structure similar to those used in lattice-based cryptography.
Decoding in rank metric has been shown to be at least as hard as decoding in Hamming metric, however it remains to assess precisely its difficulty. For some time it has been thought that combinatorial decoding techniques were the most efficient ones and all the parameters of the schemes submitted to the NIST competition were based on that belief. However, recently it has turned out that carefully devised algebraic decoding techniques can outperform combinatorial techniques and that the parameters of the rank metric submissions to the NIST had to be adapted to take these attacks into account. A good conclusion can be found in the second round report of the NIST PQC competition. It says: “Despite the development of algebraic attacks, NIST believes rank-based cryptography should continue to be researched. The rank metric cryptosystems offer a nice alternative to traditional hamming metric codes with comparable bandwidth.”
In this talk I will review what rank metric codes have to offer in code based cryptography, compare the rank metric schemes with the Hamming based schemes and I will also explain the basic ideas underlying the new algebraic attacks (which have also some consequences on certain multivariate schemes based on the MinRank problem).
Everyone is welcome.