Lattice problems beyond polynomial time
From MaRDI portal
Cites work
- (Gap/S)ETH hardness of SVP
- A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
- A decade of lattice cryptography
- A hierarchy of polynomial time lattice basis reduction algorithms
- A note on the concrete hardness of the shortest independent vector in lattices
- Approximating CVP to within almost-polynomial factors is NP-hard
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
- Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
- Collision-free hashing from lattice problems
- Factoring polynomials with rational coefficients
- Finding short lattice vectors within Mordell's inequality
- Hardness of approximating the shortest vector problem in lattices
- Hardness of SIS and LWE with small parameters
- scientific article; zbMATH DE number 1775383 (Why is no real title available?)
- scientific article; zbMATH DE number 2196508 (Why is no real title available?)
- scientific article; zbMATH DE number 7768374 (Why is no real title available?)
- Hypercontractivity, sum-of-squares proofs, and their applications
- Inapproximability of the shortest vector problem: toward a deterministic reduction
- Lattice problems in NP ∩ coNP
- New bounds in some transference theorems in the geometry of numbers
- On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
- On lattices, learning with errors, random linear codes, and cryptography
- On the limits of nonapproximability of lattice problems
- Pseudorandomness of ring-LWE for any ring and modulus
- Public-key cryptosystems from the worst-case shortest vector problem
- Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
- Tensor-based hardness of the shortest vector problem to within almost polynomial factors
- The shortest vector in a lattice is hard to approximate to within some constant
- Trapdoors for hard lattices and new cryptographic constructions
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
Cited in
(3)
This page was built for publication: Lattice problems beyond polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499316)
