It is a long standing open problem in code-based cryptography to find search to decision reductions for structured versions of the decoding problem (e.g. for quasi-cyclic codes). Such results in the lattice-based setting have been carried out using number fields: Polynomial-LWE, Ring-LWE, Module-LWE ...
In this talk, I will present a function field analogue of the LWE problem. This new framework leads to another point of view on structured codes, strengthening the connections between lattice-based and code-based cryptography.
This framework can be instantiated with function field analogues of the cyclotomic number fields, namely Carlitz extensions, leading to the first search to decision reductions on various structured versions of the decoding problem, and 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.
Maxime is a PhD student at LIX (Laboratoire d'Informatique de l'École Polytechnique) & Inria, France. He is interested in the hardness of various problems related to algebraically structured codes (either in the Hamming or the rank metric).