Quadratic modelings of syndrome decoding

DOI10.1007/978-3-031-86599-2_2MaRDI QIDQ6969315zbMATH OpenFDO

Authors Alessio Caminata, Ryann Cartor, Alessio Meneghetti, Rocco Mora, Alex Pellegrini

Publication date 20 June 2025

Full work available at URL https://doi.org/10.1007/978-3-031-86599-2_2

zbMATH Keywords

code-based cryptographycryptanalysisGröbner basismultivariate cryptographysyndrome decoding

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60) Theory of error-correcting codes and error-detecting codes (94B99)

Cites work

• A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
• A new efficient algorithm for computing Gröbner bases (F₄)
• An algebraic attack on rank metric code-based cryptosystems
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Converting bases with the Gröbner walk
• Decoding linear codes with high error rate and its impact for LPN security
• Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
• Decoding random linear codes in \(\tilde{\mathcal{O}}(2^{0.054n})\)
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• scientific article; zbMATH DE number 4112524 (Why is no real title available?)
• scientific article; zbMATH DE number 607286 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• Improvements of algebraic attacks for solving the rank decoding and MinRank problems
• On computing nearest neighbors with applications to decoding of binary linear codes
• On the equivalence of two post-quantum cryptographic families
• On the inherent intractability of certain coding problems (Corresp.)
• On the walk
• Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases
• Reduction from sparse LPN to LPN, dual attack 3.0
• Security bounds for the design of code-based cryptosystems
• Semi-regular sequences and other random systems of equations
• Smaller decoding exponents: ball-collision decoding
• Solving degree and degree of regularity for polynomial systems over a finite field
• Solving degree, last fall degree, and related invariants
• Solving multivariate polynomial systems and an invariant from commutative algebra
• Statistical decoding 2.0: reducing decoding to LPN
• Syndrome Decoding Estimator
• Two decoding algorithms for linear codes

This page was built for publication: Quadratic modelings of syndrome decoding

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