Paper 2022/269

ON CODES AND LEARNING WITH ERRORS OVER FUNCTION FIELDS

Maxime Bombar, Alain Couvreur, and Thomas Debris-Alazard

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
Code-based cryptographySearch to decision reductionsLWEFunction fieldsCarlitz modules
Contact author(s)
maxime bombar @ inria fr
History
2022-03-02: received
Short URL
https://ia.cr/2022/269
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/269,
      author = {Maxime Bombar and Alain Couvreur and Thomas Debris-Alazard},
      title = {ON CODES AND LEARNING WITH ERRORS OVER FUNCTION FIELDS},
      howpublished = {Cryptology ePrint Archive, Paper 2022/269},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/269}},
      url = {https://eprint.iacr.org/2022/269}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.