On codes and learning with errors over function fields

DOI10.1007/978-3-031-15979-4_18MaRDI QIDQ6104346zbMATH OpenFDO

Authors Maxime Bombar, Alain Couvreur, Thomas Debris-Alazard

Publication date 28 June 2023

Published in Advances in Cryptology – CRYPTO 2022 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.13990

zbMATH Keywords

\textsf{LWE}Carlitz modulescode-based cryptographyfunction fieldssearch to decision reductions

Mathematics Subject Classification ID

Cryptography (94A60) Linear codes (general theory) (94B05)

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.

Recommendations

• Pseudorandomness of decoding, revisited: adapting OHCP to code-based cryptography
• On the ring-LWE and polynomial-LWE problems
• Reduction from sparse LPN to LPN, dual attack 3.0
• Lossy codes and a new variant of the learning-with-errors problem
• Learning with errors over rings. (Abstract)

Cites work

• A new identification scheme based on syndrome decoding
• A simple proof of Noether's theorem
• Algebraic Function Fields and Codes
• Algebraic geometry codes and some appliations
• An efficient pseudo-random generator provably as secure as syndrome decoding
• Decoding one out of many
• Efficient pseudorandom correlation generators from ring-LPN
• Efficient public key encryption based on ideal lattices (extended abstract)
• Explicit Class Field Theory for Rational Function Fields
• scientific article; zbMATH DE number 1716471 (Why is no real title available?)
• scientific article; zbMATH DE number 5529001 (Why is no real title available?)
• scientific article; zbMATH DE number 3771502 (Why is no real title available?)
• scientific article; zbMATH DE number 2081064 (Why is no real title available?)
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• Lapin: an efficient authentication protocol based on ring-LPN
• Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound
• Normalbasis bei Körpern ohne höhere Verzweigung.
• On ideal lattices and learning with errors over rings
• On lattices, learning with errors, random linear codes, and cryptography
• On the decoding of algebraic-geometric codes
• On the hardness of the NTRU problem
• On the ring-LWE and polynomial-LWE problems
• Pseudorandomness of ring-LWE for any ring and modulus
• Rational points on curves over finite fields. Theory and Applications
• Wave: a new family of trapdoor one-way preimage sampleable functions based on codes
• Worst-case to average-case reductions for module lattices
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

Cited in

(4)

• Correlated pseudorandomness from the hardness of quasi-abelian decoding
• Computing a group action from the class field theory of imaginary hyperelliptic function fields
• Pseudorandomness of decoding, revisited: adapting OHCP to code-based cryptography
• Algorithms for computing norms and characteristic polynomials on general Drinfeld modules

This page was built for publication: On codes and learning with errors over function fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6104346)