TY - GEN
T1 - On Codes and Learning with Errors over Function Fields
AU - Bombar, Maxime
AU - Couvreur, Alain
AU - Debris-Alazard, Thomas
N1 - Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022/1/1
Y1 - 2022/1/1
N2 - 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 multiparty computation and to an authentication protocol.
AB - 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 multiparty computation and to an authentication protocol.
KW - Carlitz modules
KW - Code-based cryptography
KW - Function fields
KW - LWE
KW - Search to decision reductions
U2 - 10.1007/978-3-031-15979-4_18
DO - 10.1007/978-3-031-15979-4_18
M3 - Conference contribution
AN - SCOPUS:85141658644
SN - 9783031159787
T3 - Lecture Notes in Computer Science
SP - 513
EP - 540
BT - Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
A2 - Dodis, Yevgeniy
A2 - Shrimpton, Thomas
PB - Springer Science and Business Media Deutschland GmbH
T2 - 42nd Annual International Cryptology Conference, CRYPTO 2022
Y2 - 15 August 2022 through 18 August 2022
ER -