Title: On codes, and Learning with Errors over Function Fields
Abstract: In cryptography, one can often define two versions of a hard problem:
A computational version, or search version, that asks to compute something
(e.g. a discrete logarithm, a prime factor), and a decisional version, that asks to
distinguish between some specific probability distribution and the uniform.
More often, the search problem can be shown computationally hard, but the decision
version might be more difficult to handle. Informally, the hardness of the decision
version means that the distribution is pseudorandom.
In code-based cryptography, one natural search version is the decoding problem,
which has been shown to be equivalent to the decision version in the case of purely
random codes. However, it is a long standing problem to find a search to decision
reduction for structured versions of the decoding problem (e.g. the decoding of
quasi-cyclic codes). In the lattice-based setting though, such reductions have been
carried out using number fields for structured versions of the Learning With Errors
problem: Ring-LWE, Module-LWE and so on.
In this talk I will present a function field version of the LWE problem. This new
framework leads to another point of view on structured codes, strengthening the
connection between lattice-based and code-based cryptography. In particular,
it permits to obtain the first search to decision reduction for structured codes.
The framework can be instantiated with function fields analogue of the cyclotomic
number fields, namely Carlitz extensions, leading to search to decision reductions
on various versions of Ring-LPN, which have applications to secure multi party
computation, and to an authentication protocol.
This is a joint work with Alain Couvreur and Thomas Debris-Alazard.
