CANARI – Cryptography ANalysis and ARIthmetic

Introduction

CANARI is a joint project-team between INRIA, CNRS and Université de Bordeaux. Our offices are located at Institut de Mathématiques de Bordeaux.

The media department of INRIA Bordeaux has made a short video in which some CANARI members present the team. There is also an even shorter version.

The Langlands programme

Various objects studied in post-quantum cryptology belong to a unified field, namely the Langlands programme, and it is beneficial to study them together in connection with analysis and algorithmic number theory. The foundations of the Langlands programme go back to the late 1960s; in 1983, a report by a panel of the American Mathematical Society summarised its scope as follows:

The unifying role of group symmetry in geometry, so penetratingly expounded by Felix Klein in his 1872 Erlanger Programm, has led to a century of progress. A worthy successor to the Erlanger Program seems to be Langlands' program to use infinite dimensional representations of Lie groups to illuminate number theory.

In its most arithmetic formulation it postulates deep relationships between objects of three apparently unrelated worlds: the automorphic world, the world of Galois representations, and the motivic world.

The automorphic world belongs to the realm of analysis and infinite-dimensional vector spaces: its main citizens are automorphic forms, which are certain smooth functions satisfying nice differential equations. The number theoretic content comes from the domains of these functions: They are defined on so-called arithmetic manifolds, of which many classical objects are special cases: modular curves, moduli spaces of abelian varieties, the space of Euclidean lattices of a given dimension, Arakelov class groups etc.

The world of Galois representations is about symmetry and algebra. The main citizen is the group of all symmetries of the field of all algebraic numbers, the absolute Galois group. Galois representations are linear actions of the absolute Galois group on finite-dimensional vector spaces over a field (complex numbers, p-adic numbers and finite fields are all important). They are like powerful microscopes that allow us to visualise a tiny portion of the Galois group as a group of geometric symmetries.

The motivic world is about geometry. Its main citizens are algebraic varieties, that is, sets of solutions of polynomial equations, and their associated cohomologies. Important examples are algebraic curves and abelian varieties. One can classify varieties by discrete, or cohomological, invariants such as dimension and genus. On some families of algebraic varieties, after fixing these discrete invariants, the family is classified by a continuous space which is itself an algebraic variety called a moduli space. Moduli spaces of curves and abelian varieties play a key role in number theory and in cryptography.

These worlds are tied together via the central notion of L-functions: generating series adapted to number theory. Each world has its own recipe to produce L-functions, and the Langlands programme asserts that the L-functions coming from the three worlds are the same; this has striking consequences as each origin then brings special properties to the other ones. A large portion of current research in number theory is placed in this context. Thus L-functions can be seen as bridges between these three worlds, and the main goal of the CANARI team is to give algorithms to construct these bridges in practice.

Objectives of CANARI

CANARI is a follow-up project to LFANT. The members of our team are algorithmic mathematicians. We study mathematics (number theory, algebraic and arithmetic geometry, analysis) from an algorithmic point of view. We try to convert deep and often ineffective theorems into algorithms, sometimes developing new insight on the underlying mathematics, and paving the way for more precise statements and/or conjectures. We also implement these algorithms, which raises new challenges, like controlling the precision loss and certifying the computed values. Finally, we publish these reference implementations as free software (both stand-alone and as part of other popular tools), which in turn have a major impact on the mathematical community by allowing all mathematicians to perform large-scale experiments with little programming effort and skills.

Our primary goals project are to design arithmetical solutions to manipulate the objects involved in the Langlands programme and to derive concrete applications, for instance to cryptology.

It is our strong conviction that the development of the algorithmic part of the Langlands programme might bring the first stones of the next generation of cryptographic systems. Indeed, so far progress in cryptography has always closely followed the evolution of research in number theory; there is no reason to assume that this would change in the future. To give a few examples: elliptic curves, pairings and isogenies were defined and used in number theory before their usage in cryptography; the concept of lattices originally stems from number theory too (Minkowski), and ideal lattices allow to speed up lattice based cryptography; the invention of LLL was originally for a deterministic polynomial time algorithm for the factorisation of polynomials with rational coefficients; the Cohen-Lenstra heuristics for class groups are used in imaginary quadratic order cryptography; arithmetic statistics can be used as heuristics for cryptanalysis. On top of this abstract argument, we notice that several constructions already involved in most modern protocols (including post-quantum cryptography and especially lattice-based cryptography) can be reinterpreted in the language of the Langlands programme. At a minimum, we believe that the Langlands programme will shed new light on these protocols.

Concretely, the project is organised around three axes. The goal of the first axis is to give a systematic computational treatment of objects from the Langlands programme, and to investigate algorithmic insight that can be gained by approching problems in computational number theory from the Langlands programme point of view. These algorithms are of two kinds: exact or of analytic, approximated nature (p-adic, real or complex). Hence, the second axis is concerned with the development of effective complex and p-adic analysis to handle the analytic objects that appear naturally. Finally, the new objects and computational problems will provide potential bases for next generation cryptosystems, and the third axis uses these new insights to analyse the security of post-quantum cryptography, build new cryptosystems and improve the existing ones and study their security.