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 (50)
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
This page was built for publication: Improved low-density subset sum algorithms
