A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
type: Item
instance of: scholarly article
title: A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
DOI: 10.1007/978-3-030-77870-5_17
author: Divesh Aggarwal
author: Zeyong Li
author: Noah Stephens-Davidowitz
publication date: 2021-12-08T00:00:00Z
full work available at URL: https://arxiv.org/abs/2007.09556
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 7440589
MaRDI profile type: Publication
OpenAlex ID: W3175089488
cites work: Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
cites work: A sieve algorithm for the shortest lattice vector problem
cites work: Slide reduction, revisited -- filling the gaps in SVP approximation
cites work: The probabilistic method
cites work: Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
cites work: New directions in nearest neighbor searching with applications to lattice sieving
cites work: A sieve algorithm based on overlattices
cites work: Classical hardness of learning with errors
cites work: Shortest vector from lattice sieving: a few dimensions for free
cites work: Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems
cites work: Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
cites work: Q3549702
cites work: Trapdoors for hard lattices and new cryptographic constructions
cites work: Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
cites work: Factoring polynomials with rational coefficients
cites work: Approximating the densest sublattice from Rankin's inequality
cites work: Q3745276
cites work: Hardness of SIS and LWE with Small Parameters
cites work: Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
cites work: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
cites work: Practical, Predictable Lattice Basis Reduction
cites work: Sieve algorithms for the shortest vector problem are practical
cites work: A decade of lattice cryptography
cites work: On lattices, learning with errors, random linear codes, and cryptography
cites work: A reverse Minkowski theorem
cites work: A hierarchy of polynomial time lattice basis reduction algorithms
cites work: Lattice basis reduction: Improved practical algorithms and solving subset sum problems
cites work: An Inequality for Gaussians on Lattices
cites work: Finding Shortest Lattice Vectors in the Presence of Gaps
description: scientific article; zbMATH DE number 7440589