An Improved Low-Density Subset Sum Algorithm

DOI10.1007/3-540-46416-6_4MaRDI QIDQ4037449zbMATH OpenOpenAlexFDO

Authors B. A. LaMacchia, Matthijs J. Coster, Andrew Odlyzko, Claus Peter Schnorr

Publication date 18 May 1993

Published in Advances in Cryptology — EUROCRYPT ’91 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46416-6_4

zbMATH Keywords

knapsack problemcryptosystemslattice basis reductionsubset sum problem

Mathematics Subject Classification ID

Cryptography (94A60) Boolean programming (90C09) Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• Solving low-density subset sum problems
• Improved low-density subset sum algorithms
• scientific article; zbMATH DE number 4074814
• Low-density attack revisited
• Solving low density knapsacks

Cited in

(26)

• Dense subset sum may be the hardest
• Some results on an encryption method using subset-sums of pseudo-recursive sequences
• Solving low density knapsacks
• Search for combinatorial objects using lattice algorithms -- revisited
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• Solving low-density subset sum problems
• Simultaneous reduction of a lattice basis and its reciprocal basis
• LLL-solver
• An Improved Multi-set Algorithm for the Dense Subset Sum Problem
• Cryptanalysis of a knapsack-based probabilistic encryption scheme
• Too many hints -- when LLL breaks LWE
• Subset Sum Quantumly in 1.17 n .
• A low-space algorithm for the subset-sum problem on GPU
• Low-density attack revisited
• Distribution of Hermite's constant and the shortest vector in lattices of dimension two
• scientific article; zbMATH DE number 4074814 (Why is no real title available?)
• \(k\)-SUM in the sparse regime: complexity and applications
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• A knapsack-based probabilistic encryption scheme
• scientific article; zbMATH DE number 3880121 (Why is no real title available?)
• Improved low-density subset sum algorithms
• Modification of the Lagarias-Odlyzko method for solving the generalized knapsack problem and the systems of knapsack problems
• Faster algorithm for solving hard knapsacks for moderate message length
• The hardness of solving subset sum with preprocessing
• New Definition of Density on Knapsack Cryptosystems
• Preimage selective trapdoor function: how to repair an easy problem

This page was built for publication: An Improved Low-Density Subset Sum Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4037449)