Improved Generic Algorithms for Hard Knapsacks

DOI10.1007/978-3-642-20465-4_21zbMath1281.94014OpenAlexW2159641801MaRDI QIDQ3003392

Jean-Sébastien Coron, Antoine Joux, Anja Becker

Publication date: 27 May 2011

Published in: Advances in Cryptology – EUROCRYPT 2011 (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.298.6716

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Related Items (28)

The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound ⋮ How to meet ternary LWE keys ⋮ MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications ⋮ Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory ⋮ Tightly secure signatures from lossy identification schemes ⋮ How to find ternary LWE keys using locality sensitive hashing ⋮ A new approach for finding low-weight polynomial multiples ⋮ New time-memory trade-offs for subset sum -- improving ISD in theory and practice ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Finding low-weight polynomial multiples using the rho method ⋮ Improved classical and quantum algorithms for subset-sum ⋮ Unnamed Item ⋮ Integer factorization as subset-sum problem ⋮ Improved combinatorial algorithms for the inhomogeneous short integer solution problem ⋮ Subset Sum Quantumly in 1.17 n . ⋮ An algorithmic framework for the generalized birthday problem ⋮ Efficient dissection of bicomposite problems with cryptanalytic applications ⋮ Unnamed Item ⋮ Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation? ⋮ 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 ⋮ Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory ⋮ Tightly secure signature schemes from the LWE and subset sum assumptions ⋮ A sieve algorithm based on overlattices ⋮ Quantum key search for ternary LWE ⋮ A practical adaptive key recovery attack on the LGM (GSW-like) cryptosystem ⋮ Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms ⋮ Quantum security analysis of CSIDH

This page was built for publication: Improved Generic Algorithms for Hard Knapsacks