A hierarchy of polynomial time lattice basis reduction algorithms

DOI10.1016/0304-3975(87)90064-8zbMath0642.10030DBLPjournals/tcs/Schnorr87OpenAlexW1989510734WikidataQ57567987 ScholiaQ57567987MaRDI QIDQ1101500

Claus Peter Schnorr

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90064-8

zbMATH Keywords

shortest lattice vector computational number theory Korkine-Zolotareff reduction Lenstra, Lenstra, Lovász reduction polynomial time lattice basis reduction algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items (only showing first 100 items - show all)

Meta-heuristic approaches to solve shortest lattice vector problem ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ A Tale of Three Signatures: Practical Attack of ECDSA with wNAF ⋮ Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes ⋮ Attacking RSA with a Composed Decryption Exponent Using Unravelled Linearization ⋮ Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm ⋮ Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation ⋮ Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing ⋮ Targeted Homomorphic Attribute-Based Encryption ⋮ On the Security of OSIDH ⋮ Cloud-Assisted LLL: A Secure and Efficient Outsourcing Algorithm for Approximate Shortest Vector Problem ⋮ NTRU Fatigue: How Stretched is Overstretched? ⋮ Finding many collisions via reusable quantum walks. Application to lattice sieving ⋮ Fiat-Shamir signatures based on module-NTRU ⋮ Homomorphic encryption: a mathematical survey ⋮ Subfield attacks on HSVP in ideal lattices ⋮ Log-$\mathcal{S}$-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP ⋮ On module unique-SVP and NTRU ⋮ Block Reduced Lattice Bases and Successive Minima ⋮ On the hardness of the NTRU problem ⋮ A sharper lower bound on Rankin's constant ⋮ Algebraic Cryptanalysis of CTRU Cryptosystem ⋮ The curious case of the half-half Bitcoin ECDSA nonces ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ Explicit Hard Instances of the Shortest Vector Problem ⋮ Deterministic compression with uncertain priors ⋮ Sieve algorithms for the shortest vector problem are practical ⋮ Thrackles: An Improved Upper Bound ⋮ Testers and their applications ⋮ On the automorphism groups of strongly regular graphs I ⋮ Faster private release of marginals on small databases ⋮ Mechanism design in large games ⋮ Redrawing the boundaries on purchasing data from privacy-sensitive individuals ⋮ Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems ⋮ Complexity of approximating CSP with balance / hard constraints ⋮ Integer feasibility of random polytopes ⋮ Multireference alignment using semidefinite programming ⋮ Partial tests, universal tests and decomposability ⋮ High dimensional expanders and property testing ⋮ Parameterized testability ⋮ Direct sum fails for zero error average communication ⋮ Rational arguments ⋮ Lattice-Based Fault Attacks Against ECMQV ⋮ On a Waring’s problem for integral quadratic and Hermitian forms ⋮ On a quadratic Waring's problem with congruence conditions ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Lattice Reformulation Cuts ⋮ On the Bit Security of Elliptic Curve Diffie–Hellman ⋮ Revisiting Lattice Attacks on Overstretched NTRU Parameters ⋮ Short Stickelberger Class Relations and Application to Ideal-SVP ⋮ La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász ⋮ Bounding the sum of square roots via lattice reduction ⋮ Improved Rounding for Spline Coefficients and Knots ⋮ Symplectic Lattice Reduction and NTRU ⋮ Hermite’s Constant and Lattice Algorithms ⋮ LLL: A Tool for Effective Diophantine Approximation ⋮ The Geometry of Provable Security: Some Proofs of Security in Which Lattices Make a Surprise Appearance ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ The truth behind the myth of the folk theorem ⋮ Rigorous and Efficient Short Lattice Vectors Enumeration ⋮ Expanders with respect to Hadamard spaces and random graphs ⋮ Provable lattice reduction of $$\mathbb {Z}^n$$ with blocksize n/2 ⋮ Limits of local algorithms over sparse random graphs ⋮ A Digital Signature Scheme Based on CVP ∞ ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ Predicting Lattice Reduction ⋮ Quantum algorithms for algebraic problems ⋮ 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 ⋮ Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle ⋮ A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic ⋮ Hermite reduction and a Waring’s problem for integral quadratic forms over number fields ⋮ Pseudorandom Functions: Three Decades Later ⋮ On Lovász' lattice reduction and the nearest lattice point problem ⋮ Dual lattice attacks for closest vector problems (with preprocessing) ⋮ Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Towards faster polynomial-time lattice reduction ⋮ Column basis reduction and decomposable knapsack problems ⋮ Lattice basis reduction: Improved practical algorithms and solving subset sum problems ⋮ Lattice-based fault attacks on deterministic signature schemes of ECDSA and EdDSA ⋮ Fiat-Shamir and correlation intractability from strong KDM-secure encryption ⋮ Approximate CVP in time $2^{0.802 n}$ -- now in any norm! ⋮ Segment LLL reduction of lattice bases using modular arithmetic ⋮ On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography ⋮ Simultaneously good bases of a lattice and its reciprocal lattice ⋮ A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Sharper bounds on four lattice constants ⋮ Lattice Point Enumeration on Block Reduced Bases ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Solving low-density multiple subset sum problems with SVP oracle ⋮ Correcting noisy exponentiation black-boxes modulo a prime ⋮ Self-dual DeepBKZ for finding short lattice vectors ⋮ Characterizing overstretched NTRU attacks ⋮ A polynomial algorithm for minimizing discrete convic functions in fixed dimension ⋮ Sparse recovery with integrality constraints ⋮ On the modular inversion hidden number problem

Cites Work

This page was built for publication: A hierarchy of polynomial time lattice basis reduction algorithms