Wagner's algorithm provably runs in subexponential time for SIS^

DOI10.1007/978-3-032-01855-7_12MaRDI QIDQ6864043zbMATH OpenFDO

Authors Léo Ducas, Lynn Engelberts

Publication date 4 February 2026

Full work available at URL https://doi.org/10.1007/978-3-032-01855-7_12

zbMATH Keywords

cryptanalysisdiscrete Gaussian samplinglattice-based cryptographyshort integer solution problem (SIS)Wagner's algorithm

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Cites work

• A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
• An efficient and parallel Gaussian sampler for lattices
• An improved BKW algorithm for LWE with applications to cryptography and lattices
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Classical hardness of learning with errors
• Coded-BKW with sieving
• Finding short integer solutions when the modulus is small
• Hardness of SIS and LWE with small parameters
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
• Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
• Lattice problems in NP ∩ coNP
• Lazy modulus switching for the BKW algorithm on LWE
• Limits on the hardness of lattice problems in \(\ell_{p}\) norms
• New bounds in some transference theorems in the geometry of numbers
• Noise-tolerant learning, the parity problem, and the statistical query model
• On Gaussian sampling, smoothing parameter and application to signatures
• On lattices, learning with errors, random linear codes, and cryptography
• On the asymptotic complexity of solving LWE
• Shorter hash-and-sign lattice-based signatures
• Solving the closest vector problem in 2ⁿ time -- the discrete Gaussian strikes again!
• Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
• Theory of Cryptography
• Trapdoors for hard lattices and new cryptographic constructions
• Wagner's algorithm provably runs in subexponential time for \(\mathrm{SIS}^\infty \)
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

Cited in

(1)

• Wagner's algorithm provably runs in subexponential time for \(\mathrm{SIS}^\infty \)

This page was built for publication: Wagner's algorithm provably runs in subexponential time for \(\mathrm{SIS}^\infty \)

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