An Improved Low-Density Subset Sum Algorithm

DOI10.1007/3-540-46416-6_4zbMATH Open0774.11075OpenAlexW2069842959MaRDI QIDQ4037449FDOQ4037449

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

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

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)

Cited In (26)

• 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
• Too many hints -- when LLL breaks LWE
• Cryptanalysis of a knapsack-based probabilistic encryption scheme
• 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
• Title not available (Why is that?)
• \(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
• Title not available (Why is that?)
• Modification of the Lagarias-Odlyzko method for solving the generalized knapsack problem and the systems of knapsack problems
• Improved low-density subset sum algorithms
• 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
• Some results on an encryption method using subset-sums of pseudo-recursive sequences
• Dense subset sum may be the hardest
• Preimage selective trapdoor function: how to repair an easy problem
• Solving low density knapsacks

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)