# CANARI – Cryptography ANalysis and ARIthmetic

## Introduction

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.