On the limits of nonapproximability of lattice problems
From MaRDI portal
Publication:1577010
DOI10.1006/jcss.1999.1686zbMath0961.68122OpenAlexW2169690324MaRDI QIDQ1577010
Shafi Goldwasser, Oded Goldreich
Publication date: 28 May 2001
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/4ce0ddd4ae207912b608e55631e7988b85a03cf3
Related Items
On basing search SIVP on \(\mathbf{NP}\)-hardness, Improved hardness results for unique shortest vector problem, Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!, Toward non-interactive zero-knowledge proofs for NP from LWE, On the asymptotic complexity of solving LWE, Classical reduction of gap SVP to LWE: a concrete security analysis, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Mathematics of computation through the lens of linear equations and lattices, Explicit Hard Instances of the Shortest Vector Problem, ON HIGHER ARTHUR-MERLIN CLASSES, The Reductions for the Approximating Covering Radius Problem, The projection games conjecture and the hardness of approximation of Super-SAT and related problems, Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms, Unnamed Item, Asymptotically Efficient Lattice-Based Digital Signatures, General Properties of Quantum Zero-Knowledge Proofs, Algorithmic Problems for Metrics on Permutation Groups, Cryptographic Assumptions: A Position Paper, Sampling methods for shortest vectors, closest vectors and successive minima, Public-coin statistical zero-knowledge batch verification against malicious verifiers, Quantum Hardness of Learning Shallow Classical Circuits, The remote set problem on lattices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
- Probabilistic encryption
- On Lovász' lattice reduction and the nearest lattice point problem
- A hierarchy of polynomial time lattice basis reduction algorithms
- Dual vectors and lower bounds for the nearest lattice point problem
- Does co-NP have short interactive proofs ?
- Factoring polynomials with rational coefficients
- Geometric algorithms and combinatorial optimization
- A relation of primal--dual lattices and the complexity of shortest lattice vector problem
- New bounds in some transference theorems in the geometry of numbers
- Randomness in interactive proofs
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Integer Programming with a Fixed Number of Variables
- The complexity of promise problems with applications to public-key cryptography
- An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information
- Complexity Measures for Public-Key Cryptosystems
- The Knowledge Complexity of Interactive Proof Systems
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
