Solving low-density subset sum problems
From MaRDI portal
Publication:3770433
DOI10.1145/2455.2461zbMath0632.94007OpenAlexW2150780437MaRDI QIDQ3770433
Jeffrey C. Lagarias, Andrew M. Odlyzko
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2455.2461
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Linear Diophantine equations (11D04)
Related Items (62)
On Lovász' lattice reduction and the nearest lattice point problem ⋮ Algorithms to construct Minkowski reduced and Hermite reduced lattice bases ⋮ Lattice basis reduction: Improved practical algorithms and solving subset sum problems ⋮ Distribution of Hermite's constant and the shortest vector in lattices of dimension two ⋮ A Summary of McEliece-Type Cryptosystems and their Security ⋮ Lattice Reduction for Modular Knapsack ⋮ Tightly secure signatures from lossy identification schemes ⋮ An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices ⋮ Low-density attack revisited ⋮ A knapsack-based probabilistic encryption scheme ⋮ The hardness of approximate optima in lattices, codes, and systems of linear equations ⋮ Lattice points in high-dimensional spheres ⋮ The existence of simple \(6\text{-}(14,7,4)\) designs ⋮ Safer parameters for the Chor-Rivest cryptosystem ⋮ On the IO-complexity and approximation languages ⋮ Balanced Integer Solutions of Linear Equations ⋮ Obfuscated fuzzy Hamming distance and conjunctions from subset product problems ⋮ Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations ⋮ A new fully polynomial time approximation scheme for the interval subset sum problem ⋮ 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 ⋮ From approximate to exact integer programming ⋮ New Definition of Density on Knapsack Cryptosystems ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ The optimal LLL algorithm is still polynomial in fixed dimension. ⋮ Simultaneous approximation problems of \(p\)-adic numbers and \(p\)-adic knapsack cryptosystems -- Alice in \(p\)-adic numberland ⋮ Hardness of approximating the closest vector problem with pre-processing ⋮ Automated simplification of large symbolic expressions ⋮ An improved balanced algorithm for the subset-sum problem ⋮ Improved combinatorial algorithms for the inhomogeneous short integer solution problem ⋮ An Improved Multi-set Algorithm for the Dense Subset Sum Problem ⋮ Lower bounds of shortest vector lengths in random NTRU lattices ⋮ Subset Sum Quantumly in 1.17 n . ⋮ Improved low-density subset sum algorithms ⋮ Non-standard approaches to integer programming ⋮ La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász ⋮ Unnamed Item ⋮ Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms ⋮ Non-injective knapsack public-key cryptosystems ⋮ Quadratic compact knapsack public-key cryptosystem ⋮ Solving exponential diophantine equations using lattice basis reduction algorithms ⋮ Finding Shortest Lattice Vectors in the Presence of Gaps ⋮ The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem ⋮ 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 ⋮ Predicting Lattice Reduction ⋮ \(k\)-SUM in the sparse regime: complexity and applications ⋮ Moment subset sums over finite fields ⋮ Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory ⋮ Generation of solved instances of Multiconstraint Knapsack problem and its applications to Private Key Cipher ⋮ Integer Sets with Distinct Subset-Sums ⋮ Public-Key Cryptographic Primitives Provably as Secure as Subset Sum ⋮ Tightly secure signature schemes from the LWE and subset sum assumptions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A polynomial-time algorithm for solving the hidden subset sum problem ⋮ Simultaneous reduction of a lattice basis and its reciprocal basis ⋮ Solving Low Density Knapsacks ⋮ A note on BDD problems with \(\lambda_2\)-gap ⋮ Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard ⋮ Search for combinatorial objects using lattice algorithms -- revisited
This page was built for publication: Solving low-density subset sum problems
