On the complexity of lattice problems with polynomial approximation factors

DOI10.1007/978-3-642-02295-1_15MaRDI QIDQ5188551zbMATH OpenOpenAlexFDO

Authors Oded Regev

Publication date 5 March 2010

Published in The LLL Algorithm (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02295-1_15

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the limits of nonapproximability of lattice problems
• Lattice problems in NP ∩ coNP
• scientific article; zbMATH DE number 1775382
• Hardness of approximating the shortest vector problem in lattices
• The hardness of approximate optima in lattices, codes, and systems of linear equations

Cited in

(11)

• Noisy polynomial interpolation modulo prime powers
• Post-quantum cryptography: lattice signatures
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• scientific article; zbMATH DE number 1775382 (Why is no real title available?)
• Identity-based blind signature from lattices
• Lattice equations and their solutions with complexity of polynomial class
• Hermite’s Constant and Lattice Algorithms
• Cryptographic functions from worst-case complexity assumptions
• On the quantum security of high-dimensional RSA protocol
• A quasi-polynomial time algorithm for the extrapolated dihedral coset problem over power-of-two moduli
• Distributional PAC-learning from Nisan's natural proofs

This page was built for publication: On the complexity of lattice problems with polynomial approximation factors

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