A sieve algorithm for the shortest lattice vector problem
From MaRDI portal
Publication:5176018
DOI10.1145/380752.380857zbMath1323.68561OpenAlexW2050689197MaRDI QIDQ5176018
Ravi Kumar, D. Sivakumar, Miklós Ajtai
Publication date: 27 February 2015
Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/380752.380857
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Approximation algorithms (68W25) Randomized algorithms (68W20) Arithmetic codes (94B40)
Related Items (92)
Meta-heuristic approaches to solve shortest lattice vector problem ⋮ Lattice-based key exchange on small integer solution problem ⋮ Dual lattice attacks for closest vector problems (with preprocessing) ⋮ Untraceability of Partial Blind and Blind Signature Schemes ⋮ Lower bounds on lattice sieving and information set decoding ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Covering convex bodies and the closest vector problem ⋮ Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation ⋮ Probability method for cryptanalysis of general multivariate modular linear equation ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ Scalable revocable identity-based signature over lattices in the standard model ⋮ A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Lattice Point Enumeration on Block Reduced Bases ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method ⋮ Computing sparse multiples of polynomials ⋮ Sieve algorithms for some orthogonal integer lattices ⋮ From approximate to exact integer programming ⋮ On the asymptotic complexity of solving LWE ⋮ Greedy algorithm computing Minkowski reduced lattice bases with quadratic bit complexity of input vectors ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Estimating the hidden overheads in the BDGL lattice sieving algorithm ⋮ Lattice-based public key cryptosystems invoking linear mapping mask ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ On fluxes in the \(1^9\) Landau-Ginzburg model ⋮ Lattice-based cryptography: a survey ⋮ On lattice-based algebraic feedback shift registers synthesis for multisequences ⋮ Estimating quantum speedups for lattice sieves ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ The extended \(k\)-tree algorithm ⋮ Fast heuristic algorithms for computing relations in the class group of a quadratic order, with applications to isogeny evaluation ⋮ An improved method for predicting truncated multiple recursive generators with unknown parameters ⋮ Gauss Sieve Algorithm on GPUs ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ Explicit Hard Instances of the Shortest Vector Problem ⋮ Jug measuring: algorithms and complexity ⋮ A randomized sieving algorithm for approximate integer programming ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Approximate short vectors in ideal lattices of \(\mathbb{Q}(\zeta_{p^e})\) with precomputation of \({\mathrm {Cl}}(\mathcal{O}_K)\) ⋮ Pseudorandom functions in NC class from the standard LWE assumption ⋮ Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors ⋮ FPT-algorithms for some problems related to integer programming ⋮ Improved Algorithms for the Approximate k-List Problem in Euclidean Norm ⋮ Fast LLL-type lattice reduction ⋮ Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms ⋮ Short Bases of Lattices over Number Fields ⋮ Predicting nonlinear pseudorandom number generators ⋮ (Leveled) Fully Homomorphic Encryption without Bootstrapping ⋮ Hermite’s Constant and Lattice Algorithms ⋮ LLL: A Tool for Effective Diophantine Approximation ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ Cryptanalysis of General Lu-Lee Type Systems ⋮ Rigorous and Efficient Short Lattice Vectors Enumeration ⋮ Unnamed Item ⋮ Finding Shortest Lattice Vectors in the Presence of Gaps ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Lattice-Based Identification Schemes Secure Under Active Attacks ⋮ A Digital Signature Scheme Based on CVP ∞ ⋮ Asymptotically Efficient Lattice-Based Digital Signatures ⋮ Algorithmic Problems for Metrics on Permutation Groups ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Noisy polynomial interpolation modulo prime powers ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding ⋮ Predicting Lattice Reduction ⋮ Better Key Sizes (and Attacks) for LWE-Based Encryption ⋮ Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits ⋮ Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices ⋮ A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge ⋮ On compact representations of Voronoi cells of lattices ⋮ Sampling methods for shortest vectors, closest vectors and successive minima ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle ⋮ The randomized slicer for CVPP: sharper, faster, smaller, batchier ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Advanced lattice sieving on GPUs, with tensor cores ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ How (Not) to Instantiate Ring-LWE ⋮ A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices ⋮ Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms ⋮ On the complexity of the discrete logarithm and Diffie-Hellman problems ⋮ Noisy Chinese remaindering in the Lee norm ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation ⋮ Security of most significant bits of \(g^{x^{2}}\). ⋮ Improved lattice enumeration algorithms by primal and dual reordering methods ⋮ The remote set problem on lattices
Cites Work
This page was built for publication: A sieve algorithm for the shortest lattice vector problem
