Improved quantum algorithms for the k-XOR problem

DOI10.1007/978-3-030-99277-4_15MaRDI QIDQ6618596zbMATH OpenFDO

Authors André Schrottenloher

Publication date 14 October 2024

Full work available at URL https://doi.org/10.1007/978-3-030-99277-4_15

zbMATH Keywords

quantum algorithmsmerging algorithms\(k\)-XOR\(k\)-SUMbicomposite search

Mathematics Subject Classification ID

Cryptography (94A60) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1942427 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Adversary lower bound for the k-sum problem
• An algorithmic framework for the generalized birthday problem
• An efficient quantum collision search algorithm and implications on symmetric cryptography
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• How to record quantum queries, and applications to quantum indifferentiability
• Improved Generic Algorithms for Hard Knapsacks
• Improved classical and quantum algorithms for subset-sum
• Improved combinatorial algorithms for the inhomogeneous short integer solution problem
• New generic algorithms for hard knapsacks
• Optimal merging in quantum k-xor and k-sum algorithms
• Quantum Algorithms for Element Distinctness
• Quantum Walk Algorithm for Element Distinctness
• Quantum algorithms for the \(k\)-XOR problem
• Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
• Quantum algorithms for the subset-sum problem
• Quantum information set decoding algorithms
• Refinements of the k-tree Algorithm for the Generalized Birthday Problem
• Search via Quantum Walk
• The Knapsack Hash Function proposed at Crypto’89 can be broken
• The extended \(k\)-tree algorithm

Cited in

(3)

• Quantum algorithms for fast correlation attacks on LFSR-based stream ciphers
• Fine-grained complexity in a world without cryptography
• A novel algorithm for the k-XOR problem

This page was built for publication: Improved quantum algorithms for the k-XOR problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6618596)