On Codes and Learning With Errors over Function Fields
This work addresses a foundational challenge in code-based cryptography, offering new reductions that could enhance security protocols, though it builds incrementally on lattice-based methods.
The paper tackles the open problem of search-to-decision reductions for structured linear codes by proposing a function field version of the Learning With Errors (LWE) problem, leading to the first such reduction for structured codes and applications in cryptography.
It is a long standing open problem to find search to decision reductions for structured versions of the decoding problem of linear codes. Such results in the lattice-based setting have been carried out using number fields: Polynomial-LWE, Ring-LWE, Module-LWE and so on. We propose a function field version of the LWE problem. This new framework leads to another point of view on structured codes, e.g. quasi-cyclic codes, strengthening the connection between lattice-based and code-based cryptography. In particular, we obtain the first search to decision reduction for structured codes. Following the historical constructions in lattice-based cryptography, we instantiate our construction with function fields analogues of cyclotomic 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.