On the Complexity of Lattice Problems with Polynomial Approximation Factors

DOI10.1007/978-3-642-02295-1_15zbMath1237.68102OpenAlexW1662048MaRDI QIDQ5188551

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

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

Related Items

Post-quantum cryptography: lattice signatures, Identity-based blind signature from lattices, Hermite’s Constant and Lattice Algorithms, Cryptographic Functions from Worst-Case Complexity Assumptions, Noisy polynomial interpolation modulo prime powers, Unnamed Item