Improved classical and quantum algorithms for subset-sum
From MaRDI portal
Publication:2692398
DOI10.1007/978-3-030-64834-3_22OpenAlexW3013119683MaRDI QIDQ2692398
André Schrottenloher, Rémi Bricout, Xavier Bonnetain, Yixin Shen
Publication date: 21 March 2023
Full work available at URL: https://arxiv.org/abs/2002.05276
Related Items (8)
How to meet ternary LWE keys ⋮ MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications ⋮ Lattice Sieving via Quantum Random Walks ⋮ Finding many collisions via reusable quantum walks. Application to lattice sieving ⋮ New time-memory trade-offs for subset sum -- improving ISD in theory and practice ⋮ Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm ⋮ Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection ⋮ Quantum key search for ternary LWE
Cites Work
- Ternary Syndrome Decoding with large weight
- Finding shortest lattice vectors faster using quantum search
- Hidden shift quantum cryptanalysis and implications
- Quantum information set decoding algorithms
- Quantum search with variable times
- Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms
- Quantum security analysis of CSIDH
- Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes
- Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Search via Quantum Walk
- Improved Generic Algorithms for Hard Knapsacks
- Decoding Random Linear Codes in $\tilde{\mathcal{O}}(2^{0.054n})$
- The Double Dixie Cup Problem
- Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
- New Generic Algorithms for Hard Knapsacks
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- Computing Partitions with Applications to the Knapsack Problem
- Strengths and Weaknesses of Quantum Computing
- Quantum Algorithms for the Subset-Sum Problem
- The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound
- Quantum Walk Algorithm for Element Distinctness
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Improved classical and quantum algorithms for subset-sum
