  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.
