The complexity of algebraic algorithms for LWE

DOI10.1007/978-3-031-58734-4_13MaRDI QIDQ6637336zbMATH OpenFDO

Authors Matthias Johann Steiner

Publication date 13 November 2024

Full work available at URL https://doi.org/10.1007/978-3-031-58734-4_13

zbMATH Keywords

Gröbner basesLWELWE with hints

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Cryptography (94A60)

Recommendations

• On the asymptotic complexity of solving LWE
• On the concrete hardness of learning with errors
• On the complexity of the BKW algorithm on LWE
• Better algorithms for LWE and LWR
• Solving multivariate polynomial systems and an invariant from commutative algebra

Cites work

• A criterion for detecting m-regularity
• A new efficient algorithm for computing Gröbner bases (F₄)
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• An inequality for Hilbert series of graded algebras.
• Bounds for entropy and divergence for distributions over a two-element set
• Classical hardness of learning with errors
• Elements of Information Theory
• Generic sequences of polynomials
• scientific article; zbMATH DE number 3857249 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• Ideals, Varieties, and Algorithms
• LWE with side information: attacks and concrete security estimation
• New Algorithms for Learning in Presence of Errors
• On lattices, learning with errors, random linear codes, and cryptography
• On the concrete hardness of learning with errors
• On the hardness of learning with errors with binary secrets
• Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases
• Public-key cryptosystems from the worst-case shortest vector problem
• Revisiting security estimation for LWE with hints from a geometric perspective
• Revisiting the hardness of binary error LWE
• 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
• Some results and questions on Castelnuovo-Mumford regularity
• The Geometry of Syzygies

Cited in

(3)

• Refined attack on LWE with hints: constructing lattice via Gaussian elimination
• On the soundness of algebraic attacks against code-based assumptions
• Fast slicer for Batch-CVP: making lattice hybrid attacks practical

This page was built for publication: The complexity of algebraic algorithms for LWE

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