New Generic Algorithms for Hard Knapsacks

DOI10.1007/978-3-642-13190-5_12zbMath1280.94069OpenAlexW1856875316MaRDI QIDQ3563838

N. A. Howgrave-Graham, Antoine Joux

Publication date: 1 June 2010

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

Full work available at URL: https://doi.org/10.1007/978-3-642-13190-5_12

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (34)

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 ⋮ How to find ternary LWE keys using locality sensitive hashing ⋮ Generalization of the Ball-Collision Algorithm ⋮ The Modular Subset-Sum Problem and the size of deletion correcting codes ⋮ Refined cryptanalysis of the GPRS ciphers GEA-1 and GEA-2 ⋮ McEliece needs a break -- solving McEliece-1284 and quasi-cyclic-2918 with modern ISD ⋮ Time-Memory Tradeoffs for Large-Weight Syndrome Decoding in Ternary Codes ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ New time-memory trade-offs for subset sum -- improving ISD in theory and practice ⋮ Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection ⋮ Information set decoding for Lee-metric codes using restricted balls ⋮ 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 ⋮ A low-memory algorithm for finding short product representations in finite groups. ⋮ Cryptanalysis of the Knapsack Generator ⋮ Subset Sum Quantumly in 1.17 n . ⋮ An algorithmic framework for the generalized birthday problem ⋮ TinyKeys: a new approach to efficient multi-party computation ⋮ Generalization of BJMM-ISD Using May-Ozerov Nearest Neighbor Algorithm over an Arbitrary Finite Field $$\mathbb {F}_q$$ ⋮ 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 ⋮ Two-round \(n\)-out-of-\(n\) and multi-signatures and trapdoor commitment from lattices ⋮ Two-round \(n\)-out-of-\(n\) and multi-signatures and trapdoor commitment from lattices ⋮ Constructing Carmichael numbers through improved subset-product algorithms ⋮ Quantum key search for ternary LWE ⋮ A practical adaptive key recovery attack on the LGM (GSW-like) cryptosystem

Uses Software

• SWIFFT

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