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
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, 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
