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

cryptosystemsknapsack problemlattice basis reductionsubset sum problem

Mathematics Subject Classification ID

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

Review text

[For the entire collection see Zbl 0756.00008.] Given positive integers \(a_ 1,\dots,a_ n\), \(s\) the knapsack or subset sum problem is to find \(e_ 1,\dots,e_ n\in\{0,1\}\) such that \(\sum_{i=1}^ n e_ i a_ i=s\). This is an NP-complete problem and therefore used in developing some cryptosystems; however almost all of these have been broken by now. There are algorithms e.g. by \textit{J. C. Lagarias} and \textit{A. M. Odlyzko} [J. ACM 32, 229--246 (1985; Zbl 0632.94007)] which show that almost all low-density sum problems can be solved in polynomial time. The density is defined by \(d=n/\log_ 2 \max_{1\leq i\leq n} a_ i\), and the interesting case for cryptosystems is \(d\leq 1\). The Lagarias-Odlyzko algorithm is useful only for \(d<0,6463\dots\), and in this paper a modification of the algorithm is given increasing the bound for \(d\) to 0,9408\dots\ .

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

(27)

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

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)