Limits on the hardness of lattice problems in \(\ell_{p}\) norms
From MaRDI portal
Publication:937206
DOI10.1007/s00037-008-0251-3zbMath1149.68039OpenAlexW2181114408MaRDI QIDQ937206
Publication date: 20 August 2008
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-008-0251-3
Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)
Related Items
On the hardness of module-LWE with binary secret ⋮ PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ On the smoothing parameter and last minimum of random orthogonal lattices ⋮ New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors ⋮ On the hardness of module learning with errors with short distributions ⋮ Hardness of \(k\)-LWE and applications in traitor tracing ⋮ A polynomial time algorithm for GapCVPP in \(l_1\) norm ⋮ Lattice signature with efficient protocols, application to anonymous credentials ⋮ Entropic hardness of Module-LWE from module-NTRU ⋮ STP-LWE: A variant of learning with error for a flexible encryption ⋮ The Reductions for the Approximating Covering Radius Problem ⋮ On a certain class of positive definite functions and measures on locally compact abelian groups and inner-product spaces ⋮ Provably Secure NTRU Instances over Prime Cyclotomic Rings ⋮ Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems ⋮ A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic ⋮ Mixing time and eigenvalues of the abelian sandpile Markov chain ⋮ Worst-case to average-case reductions for module lattices ⋮ The remote set problem on lattices
