Fast Lattice Point Enumeration with Minimal Overhead

No abstract is available for this paper.

• Publication year

  2015

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2015-01-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973730.21
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing

  2015influential reference
• Estimating Key Sizes for High Dimensional Lattice-Based Systems

  2013cited by this paper
• Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

  2012cited by this paper
• BKZ 2.0: Better Lattice Security Estimates

  2011cited by this paper
• Lattice Enumeration Using Extreme Pruning

  2010cited by this paper
• A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations

  2010cited by this paper
• Faster exponential time algorithms for the shortest vector problem

  2010cited by this paper
• Finding short lattice vectors within mordell's inequality

  2008cited by this paper
• Predicting Lattice Reduction

  2008cited by this paper
• Improved Analysis of Kannan's Shortest Lattice Vector Algorithm

  2007cited by this paper
• Sampling methods for shortest vectors, closest vectors and successive minima

  2007cited by this paper
• On lattices, learning with errors, random linear codes, and cryptography

  2005cited by this paper
• Hardness of approximating the shortest vector problem in lattices

  2004cited by this paper
• Worst-case to average-case reductions based on Gaussian measures

  2004cited by this paper
• Closest point search in lattices

  2002cited by this paper
• A sieve algorithm for the shortest lattice vector problem

  2001cited by this paper
• A linear space algorithm for computing the hermite normal form

  2001cited by this paper
• Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors

  1999cited by this paper
• Generating hard instances of lattice problems (extended abstract)

  1996cited by this paper
• Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

  1995cited by this paper
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems

  1991cited by this paper
• A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms

  1987cited by this paper
• Computing a lattice basis from a system of generating vectors

  1987cited by this paper
• Minkowski's Convex Body Theorem and Integer Programming

  1987cited by this paper
• Algorithms to Construct Minkowski Reduced an Hermite Reduced Lattice Bases

  1985cited by this paper
• Improved methods for calculating vectors of short length in a lattice

  1985cited by this paper
• Improved algorithms for integer programming and related lattice problems

  1983cited by this paper
• Factoring polynomials with rational coefficients

  1982cited by this paper
• Improved Analysis of Kannan ’ s Shortest Lattice Vector Algorithm

  year unknowninfluential reference

• On Computing the Copositive Minimum and its Representatives

  2025cites this paper
• Scaling Lattice Sieves across Multiple Machines

  2025cites this paper
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

  2025cites this paper
• A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm

  2025cites this paper
• DiTRU: A Resurrection of NTRU over Dihedral Group

  2024cites this paper
• A Complete Analysis of the BKZ Lattice Reduction Algorithm

  2024cites this paper
• Giant Does NOT Mean Strong: Cryptanalysis of BQTRU

  2024cites this paper
• An ADMM based method for underdetermined box-constrained integer least squares problems

  2023cites this paper
• Structured (min,+)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\min ,+)$$\end{document}-convolution and its applic

  2023cites this paper
• A New Sieving Approach for Solving the HNP with One Bit of Nonce by Using Built-in Modulo Arithmetic

  2023cites this paper
• Individual discrete logarithm with sublattice reduction

  2023influential citation
• Predicting BKZ Z-Shapes on q-ary Lattices

  2022cites this paper
• Structured (min, +)-Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems

  2022cites this paper
• Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm

  2022cites this paper
• Revisiting the Concrete Hardness of SelfTargetMSIS in CRYSTALS-Dilithium

  2022cites this paper
• The Fine-Grained Hardness of Sparse Linear Regression

  2021cites this paper
• Post-Quantum Cryptosystems for Internet-of-Things: A Survey on Lattice-Based Algorithms

  2021cites this paper
• Dual lattice attacks for closest vector problems (with preprocessing)

  2021cites this paper
• On the Smallest Ratio Problem of Lattice Bases

  2021cites this paper
• Progress in Cryptology - AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings

  2020cites this paper
• Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

  2020cites this paper
• Scalable revocable identity-based signature over lattices in the standard model

  2020cites this paper
• Sieve, Enumerate, Slice, and Lift:

  2020cites this paper
• A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge

  2020cites this paper
• Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance

  2020cites this paper
• On post-processing in the quantum algorithm for computing short discrete logarithms

  2020cites this paper
• Faster Enumeration-based Lattice Reduction: Root Hermite Factor k^(1/(2k)) in Time k^(k/8 + o(k))

  2020cites this paper
• On Bounded Distance Decoding with Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem

  2020cites this paper
• Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes

  2020cites this paper
• Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

  2020cites this paper
• A refined analysis of the cost for solving LWE via uSVP

  2019cites this paper
• Approximate Voronoi cells for lattices, revisited

  2019cites this paper
• A Parallel Evolutionary Search for Shortest Vector Problem

  2019cites this paper
• Progress in Cryptology – AFRICACRYPT 2019: 11th International Conference on Cryptology in Africa, Rabat, Morocco, July 9–11, 2019, Proceedings

  2019cites this paper
• The General Sieve Kernel and New Records in Lattice Reduction

  2019cites this paper
• Finding Closest Lattice Vectors Using Approximate Voronoi Cells

  2019cites this paper
• SPACE-EFFICIENT CLASSICAL AND QUANTUM ALGORITHMS FOR THE SHORTEST

  2018cites this paper
• Shortest Vector from Lattice Sieving: a Few Dimensions for Free

  2018cites this paper
• Lower Bounds on Lattice Enumeration with Extreme Pruning

  2018cites this paper
• Cold Boot Attacks on Ring and Module LWE Keys Under the NTT

  2018cites this paper
• Estimated Cost for Solving Generalized Learning with Errors Problem via Embedding Techniques

  2018cites this paper
• On the Security of Lattice-Based Cryptography Against Lattice Reduction and Hybrid Attacks

  2018cites this paper
• Round 5 : Compact and Fast Post-Quantum Public-Key Encryption Draft Friday 30 th November , 2018

  2018cites this paper
• Exploiting mathematical structures in cryptography

  2018cites this paper
• Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem

  2018cites this paper
• On the Maximum Distance Sublattice Problem and Closest Vector Problem

  2018cites this paper
• Estimate all the {LWE, NTRU} schemes!

  2018cites this paper
• Optimizing curve-based cryptography

  2017cites this paper
• Quantum algorithms for computing short discrete logarithms and factoring RSA integers

  2017cites this paper
• On the Quantitative Hardness of CVP

  2017cites this paper
• Faster tuple lattice sieving using spherical locality-sensitive filters

  2017cites this paper
• Space-efficient classical and quantum algorithms for the shortest vector problem

  2017influential citation
• NTRU Prime: Reducing Attack Surface at Low Cost

  2017cites this paper
• Revisiting TESLA in the Quantum Random Oracle Model

  2017cites this paper
• Analysis of decreasing squared-sum of Gram–Schmidt lengths for short lattice vectors

  2017cites this paper
• Geometric and Dual Approaches to Cumulative Scheduling

  2017cites this paper
• On the Gaussian Measure Over Lattices

  2017cites this paper
• Post-Quantum Cryptography: 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings

  2017cites this paper
• Post-quantum Lattice-based Cryptography

  2016cites this paper
• Sieving for Closest Lattice Vectors (with Preprocessing)

  2016cites this paper
• Efficient (Ideal) Lattice Sieving Using Cross-Polytope LSH

  2016cites this paper
• Search problems in cryptography : from fingerprinting to lattice sieving

  2016cites this paper
• High performance algorithms for lattice-based cryptanalysis

  2016cites this paper
• Practical, Predictable Lattice Basis Reduction

  2016cites this paper
• On the concrete hardness of Learning with Errors

  2015cites this paper
• Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing

  2015cites this paper
• Solving the Closest Vector Problem in $2^n$ Time - The Discrete Gaussian Strikes Again!

  2015cites this paper
• Lattice Point Enumeration on Block Reduced Bases

  2015influential citation
• TESLA: Tightly-Secure Efficient Signatures from Standard Lattices

  2015cites this paper
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing

  2015cites this paper
• Assessing the Hardness of SVP Algorithms on Multi-core CPUs

  2014cites this paper
• Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing

  2014cites this paper
• A Fast Phase-based Enumeration Algorithm for SVP Challenge Through y y -Sparse Representations of Short Lattice Vectors

  2014cites this paper
• Assessing the hardness of SVP algorithms in the presence of CPUs and GPUs

  2014cites this paper
• Lattice Sparsification and the Approximate Closest Vector Problem

  2012cites this paper