Faster exponential time algorithms for the shortest vector problem

No abstract is available for this paper.

• Publication year

  2010

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2010-01-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973075.119
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Predicting Lattice Reduction

  2008cited by this paper
• Trapdoors for hard lattices and new cryptographic constructions

  2008cited by this paper
• Rigorous and Efficient Short Lattice Vectors Enumeration

  2008cited by this paper
• Lossy trapdoor functions and their applications

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

  2008cited by this paper
• Sieve algorithms for the shortest vector problem are practical

  2008influential reference
• Improved Analysis of Kannan's Shortest Lattice Vector Algorithm

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

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

  2004cited by this paper
• New lattice based cryptographic constructions

  2003cited by this paper
• Complexity of lattice problems - a cryptographic perspective

  2002cited by this paper
• Closest point search in lattices

  2002cited by this paper
• Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

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

  2001influential reference
• The Two Faces of Lattices in Cryptology

  2001cited by this paper
• Improving Lattice Based Cryptosystems Using the Hermite Normal Form

  2001cited by this paper
• Finding the closest lattice vector when it's unusually close

  2000cited by this paper
• Sphere packings, I

  1998cited by this paper
• NTRU: A Ring-Based Public Key Cryptosystem

  1998cited by this paper
• Factoring Polynomials with Rational Coeecients

  1998cited by this paper
• A public-key cryptosystem with worst-case/average-case equivalence

  1997cited by this paper
• Positive Applications of Lattices to Cryptography

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

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

  1991cited by this paper
• Sphere Packings, Lattices and Groups

  1990cited by this paper
• Book review: Annual Review of Computer Science. Ed. by J. F. Traub (Annual Reviews Inc.)

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

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

  1983influential reference
• Factoring polynomials with rational coefficients

  1982cited by this paper
• On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications

  1981cited by this paper

• Rank Syndrome Decoding Estimator - An Asymptotic and Concrete Analysis

  2026cites this paper
• Lower Bound on the Overlattice-Based Sieve Algorithm

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

  2025cites this paper
• A Quasi-polynomial Time Algorithm for the Extrapolated Dihedral Coset Problem over Power-of-Two Moduli

  2025cites this paper
• A Comprehensive Survey on Pre Versus Post Quantum Security Schemes for 5G-Enabled IoT Applications

  2025cites this paper
• Scaling Lattice Sieves across Multiple Machines

  2025cites this paper
• Quantum security analysis of Module-LWE PQC based on practical cost estimates

  2025cites this paper
• Predicting Module-Lattice Reduction

  2025cites this paper
• Fast Slicer for Batch-CVP: Making Lattice Hybrid Attacks Practical

  2025cites this paper
• TAPAS: Datasets for Learning the Learning with Errors Problem

  2025cites this paper
• An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

  2025cites this paper
• Iterative partition-search variational quantum algorithm for solving the shortest-vector problem

  2025cites this paper
• Accurate Score Prediction for Dual-Sieve Attacks

  2025cites this paper
• Sieving with Streaming Memory Access

  2025cites this paper
• Time Memory Trade-off For Enumeration

  2025cites this paper
• EagleSignV3 : A new secure variant of EagleSign signature over lattices

  2024cites this paper
• Pump-BSKZ: A Novel Sieve Algorithm to Solve Shortest Vector Problem

  2024cites this paper
• Does quantum lattice sieving require quantum RAM?

  2024cites this paper
• 2-D Information Encoding for Lattice-Based Encryption Scheme using Entropy Approach for Futuristic Applications

  2024cites this paper
• Analyzing Pump and jump BKZ algorithm using dynamical systems

  2024cites this paper
• Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors

  2024cites this paper
• Quantum sieving for code-based cryptanalysis and its limitations for ISD

  2024cites this paper
• A New Quantum Oracle Model for a Hybrid Quantum-Classical Attack on Post-Quantum Lattice-Based Cryptosystems

  2024cites this paper
• Spectral Guarantees for Adversarial Streaming PCA

  2024cites this paper
• BGJ15 Revisited: Sieving with Streamed Memory Access

  2024cites this paper
• New Results on the Remote Set Problem and Its Applications in Complexity Study

  2024cites this paper
• Attacking ECDSA with Nonce Leakage by Lattice Sieving: Bridging the Gap with Fourier Analysis-based Attacks

  2024cites this paper
• Formally verifying Kyber Episode V: Machine-checked IND-CCA security and correctness of ML-KEM in EasyCrypt

  2024cites this paper
• Quantum NV Sieve on Grover for Solving Shortest Vector Problem

  2024cites this paper
• Recursive lattice reduction - A framework for finding short lattice vectors

  2023cites this paper
• Post-Quantum Cryptosystems: Open Problems and Solutions. Lattice-Based Cryptosystems

  2023cites this paper
• SalsaPicante: A Machine Learning Attack on LWE with Binary Secrets

  2023cites this paper
• Improved Attacks on (EC)DSA with Nonce Leakage by Lattice Sieving with Predicate

  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
• Does the Dual-Sieve Attack on Learning with Errors even Work?

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

  2023cites this paper
• Estimates of Implementation Complexity for Quantum Cryptanalysis of Post-Quantum Lattice-Based Cryptosystems

  2023cites this paper
• New NTRU Records with Improved Lattice Bases

  2023cites this paper
• Finding Shortest Vector Using Quantum NV Sieve on Grover

  2023cites this paper
• Practical Improvements on BKZ Algorithm

  2023cites this paper
• InvGC: Robust Cross-Modal Retrieval by Inverse Graph Convolution

  2023cites this paper
• A Trade-off SVP-solving Strategy based on a Sharper pnj-BKZ Simulator

  2023cites this paper
• Provable Dual Attacks on Learning with Errors

  2023cites this paper
• Concrete Analysis of Quantum Lattice Enumeration

  2023cites this paper
• Classical and quantum 3 and 4-sieves to solve SVP with low memory

  2023cites this paper
• Upper bounds of complexity of quantum oracle for problem of finding shortest vector on integer lattice

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

  2022cites this paper
• ON PAIRWISE GAUSSIAN BASES AND LLL ALGORITHM FOR THREE DIMENSIONAL LATTICES

  2022cites this paper
• Improved Progressive BKZ with Lattice Sieving

  2022cites this paper
• SALSA: Attacking Lattice Cryptography with Transformers

  2022cites this paper
• Quantum algorithms for attacking hardness assumptions in classical and post‐quantum cryptography

  2022cites this paper
• Star-specific Key-homomorphic PRFs from Linear Regression and Extremal Set Theory

  2022cites this paper
• Approximate CVPp in time 20.802n

  2022cites this paper
• Analysis of the shortest vector problems with quantum annealing to search the excited states

  2022cites this paper
• Star-Specific Key-Homomorphic PRFs From Learning With Linear Regression

  2022cites this paper
• Several Improvements on BKZ Algorithm

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

  2022cites this paper
• HybridPKE: A forward-secure non-interactive quantum-safe hybrid key exchange scheme

  2022cites this paper
• The irreducible vectors of a lattice:

  2022influential citation
• AKAME: A post-quantum authenticated key-agreement and message encryption scheme based on ring-LWE

  2022cites this paper
• Advanced Lattice Sieving on GPUs, with Tensor Cores

  2021cites this paper
• A comprehensive review on collision-resistant hash functions on lattices

  2021cites this paper
• Just how hard are rotations of Z n ? Algorithms and cryptography with the simplest lattice

  2021cites this paper
• Lattice sieving via quantum random walks

  2021cites this paper
• Faster Rotation-Based Gauss Sieve for Solving the SVP on General Ideal Lattices

  2021influential citation
• Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing

  2021cites this paper
• Parallelization on Gauss Sieve Algorithm over Ideal Lattice

  2021influential citation
• Quantum Lattice Sieving

  2021cites this paper
• Sieving Algorithms for Exact SVP

  2021cites this paper
• Non-randomness of S-unit lattices

  2021cites this paper
• Improved Quantum Hypercone Locality Sensitive Filtering in Lattice Sieving

  2021cites this paper
• Approximate CVP in time 20.802 n - now in any norm!

  2021influential citation
• CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems

  2021cites this paper
• Efficient Implementations of Sieving and Enumeration Algorithms for Lattice-Based Cryptography

  2021influential citation
• A Lattice Reduction Algorithm Based on Sublattice BKZ

  2021cites this paper
• Fast Factoring Integers by SVP Algorithms

  2021cites this paper
• Predicting the Concrete Security of LWE Against the Dual Attack Using Binary Search

  2021cites this paper
• Lower bounds on lattice sieving and information set decoding

  2021cites this paper
• Experimental Verification of Estimated Block Size of BKZ Algorithm Against LWE

  2021cites this paper
• Techniques for Solving Shortest Vector Problem

  2021cites this paper
• Tight bounds on the expected number of holes in random point sets

  2021cites this paper
• LUSA: the HPC library for lattice-based cryptanalysis

  2020cites this paper
• On a Dual/Hybrid Approach to Small Secret LWE - A Dual/Enumeration Technique for Learning with Errors and Application to Security Estimates of FHE Schemes

  2020cites this paper
• Efficient Implementation of HashSieve Algorithm for Lattice-Based Cryptography

  2020cites this paper
• Computational aspects of lattices and their cryptographic applications

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

  2020cites this paper
• A Multiplatform Parallel Approach for Lattice Sieving Algorithms

  2020cites this paper
• Efficient Implementations of Gauss-Based Sieving Algorithms

  2020influential citation
• The Concrete Complexity of LWE without Gaussian Sampling

  2020influential citation
• A Lightweight Post-Quantum Lattice-Based RSA for Secure Communications

  2020cites this paper
• Optimized Voronoi-based algorithms for parallel shortest vector computations

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

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

  2020cites this paper
• Learning Strikes Again: The Case of the DRS Signature Scheme

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

  2020cites this paper
• Block Sieve Reduction: A New Random Sampling Reduction Algorithm Based on Sieve Algorithms

  2020cites this paper
• The nearest-colattice algorithm

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

  2020cites this paper
• The nearest-colattice algorithm

  2020cites this paper
• An Efficient Sieve Algorithm with Evolutionary Technique

  2020cites this paper