Algebraic Geometry and Algebraic Coding Theory for Cryptography – Manta

This proposition will study error correcting codes built using
algebraic geometry and number theory, and their applications in
cryptography, multi-party computation, and complexity theory. Indeed,
many new questions are naturally raised in these application domains,
and we claim that these questions actually involve deep mathematics.

Thus the problems that we will study in algebraic coding theory are
those which have natural applications in the above domains (computer
science, public-key cryptography and multi-party computation), and our
approach will be to systematic reformulate these questions in terms of
algebraic geometry. The standard, simple mathematical notions used in
the domains (polynomials, finite fields) will be replaced by their
abstract equivalent in algebraic geometry.

We structure ourselves in three tasks, which are simple to identify
with each task corresponding to a single partner: "computing" for the
multiplicative properties of codes (25% of the activity), "decoding"
for new decoding problems and their applications in complexity
theory), and finally "geometry", for studying more families of codes,
and the related mathematical problems in algebraic geometry (50%).

Our "computing" tasks has applications in multi-party computation,
algebraic complexity, cryptanalsyis of McEliece's cryptosystem. The
point is to study the properties of codes under component-wise
multiplication. These considerations have been introduced by
Chudnovsky and Chudnovsky in 1988 to study the bilinear complexity of
multiplication in finite fields, but now we see that this topic
presents many other applications, as said above. The multiplicative
properties can also nicely be studied using methods from additive
number theory.

The "decoding" task deals with non standard questions in decoding
algebraic codes: list-decoding, locally decodable codes, decoding of
related codes built on varieties related by morphisms, subfield
subcodes. There has been many breakthroughs in list decodable codes,
for instance the so-called folded Reed-Solomon codes. Yet their
generalization to higher genus curves have only been partially
explored. Similarly, the notion of locally decodable codes naturally
relies on the construction of codes in varieties of dimension larger
than one, yet only the affine space has been studied in a standard
way. It is the spirit of our proposal to consider rich and interesting
varieties for constructing and decoding algebraic codes.

Our third task "geometry" study new research directions per se in
algebraic geometry and coding theory: codes built over higher
dimensionnal varieties, families of codes, rationnaly connected
varieties. This tasks will systematically reinforce the links between
algebraic geometry over finite fields and algebraic coding theory, but
also will lead to interesting mathematical basic research.

Our rather large group, gather mathematicians in algebraic geometry,
number theory, additive number theory, as well as coding theorists and
cryptographers.

Our three tasks are actually intwined, yet the variety of topics in
manta is rather broad. So we will organize two (open) French speaking
retreats the first two years, gathering all manta participants. The
last year (2018), we will organize an international summer school for
young researchers to explain these new applications areas and the use
of algebraic geometry in algebraic coding theory. This summer school
can be seen as somewhat preparatory to the 2019 AGCT workshop.

We plan to collect lecture notes from the Summer school, and publish
them in a sustainable way.

Furthermore, non Parisian members of manta will come to Paris to
participate in the Telecom or INRIA Saclay already existing regular
seminars.