Improved low-density subset sum algorithms
From MaRDI portal
Publication:1207335
DOI10.1007/BF01201999zbMath0768.11049OpenAlexW1968182591MaRDI QIDQ1207335
Antoine Joux, Matthijs J. Coster, B. A. LaMacchia, Jacques Stern, Claus Peter Schnorr, Andrew M. Odlyzko
Publication date: 1 April 1993
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01201999
latticeslattice basis reductionsubset sum algorithmsknapsack cryptosystemsLagarias-Odlyzko algorithm
Related Items
The inapproximability of lattice and coding problems with preprocessing, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Lattice Reduction for Modular Knapsack, An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices, Low-density attack revisited, Safer parameters for the Chor-Rivest cryptosystem, A semantically secure public key cryptoscheme using bit-pair shadows, A provably secure non-iterative hash function resisting birthday attack, A New Non-Merkle-Damgård Structural Hash Function with Provable Security, A Public Key Cryptoscheme Using Bit-Pairs with Provable Semantical Security, Balanced Integer Solutions of Linear Equations, Obfuscated fuzzy Hamming distance and conjunctions from subset product problems, A pseudorandom number generator based on worst-case lattice problems, A new fully polynomial time approximation scheme for the interval subset sum problem, Lattice-based algorithms for number partitioning in the hard phase, Finding shortest lattice vectors faster using quantum search, Solving low-density multiple subset sum problems with SVP oracle, Generalization of the subset sum problem and cubic forms, New Definition of Density on Knapsack Cryptosystems, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach, Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection, Block Reduced Lattice Bases and Successive Minima, Improved broadcast attacks against subset sum problems via lattice oracle, A public key cryptosystem based on three new provable problems, Simultaneous approximation problems of \(p\)-adic numbers and \(p\)-adic knapsack cryptosystems -- Alice in \(p\)-adic numberland, An improved balanced algorithm for the subset-sum problem, Improved combinatorial algorithms for the inhomogeneous short integer solution problem, Preimage selective trapdoor function: how to repair an easy problem, An Improved Multi-set Algorithm for the Dense Subset Sum Problem, Lower bounds of shortest vector lengths in random NTRU lattices, The projection games conjecture and the hardness of approximation of Super-SAT and related problems, Solving market split problems with heuristical lattice reduction, Non-standard approaches to integer programming, Unnamed Item, Non-injective knapsack public-key cryptosystems, Quadratic compact knapsack public-key cryptosystem, Koblitz curve cryptosystems, Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits, Asymptotic granularity reduction and its application, Unnamed Item, Finding Shortest Lattice Vectors in the Presence of Gaps, Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme, Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Tightly secure signature schemes from the LWE and subset sum assumptions, Unnamed Item, Unnamed Item, Analysis of PSLQ, an integer relation finding algorithm, A polynomial-time algorithm for solving the hidden subset sum problem, A note on BDD problems with \(\lambda_2\)-gap, Search for combinatorial objects using lattice algorithms -- revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- Simultaneous reduction of a lattice basis and its reciprocal basis
- Lattice points in high-dimensional spheres
- Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
- On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
- Solving low-density subset sum problems
- A knapsack-type public key cryptosystem based on arithmetic in finite fields
- An Improved Low-Density Subset Sum Algorithm
- Succinct Certificates for Almost All Subset Sum Problems
- A more efficient algorithm for lattice basis reduction
- Cryptanalysis: a survey of recent results
