Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms

DOI10.1007/978-3-030-45724-2_11zbMath1489.81021OpenAlexW2941126499MaRDI QIDQ2119016

André Schrottenloher, María Naya-Plasencia

Publication date: 23 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-45724-2_11

zbMATH Keywords

LPNMILPquantum cryptanalysisgeneralized birthday problemsubset-summultiple encryption\(k\)-list problemsapproximate \(k\)-list problemlist-merging algorithms

Mathematics Subject Classification ID

Quantum computation (81P68) Cryptography (94A60) Approximation to limiting values (summation of series, etc.) (40A25) Numerical summation of series (65B10) Quantum coding (general) (81P70) Quantum cryptography (quantum-theoretic aspects) (81P94) Quantum gates (81P65)

Related Items (9)

Low-gate quantum golden collision finding ⋮ Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions ⋮ Syndrome Decoding Estimator ⋮ Triangulating rebound attack on AES-like hashing ⋮ Synthesizing quantum circuits of AES with lower \(T\)-depth and less qubits ⋮ Quantum time/memory/data tradeoff attacks ⋮ Automatic classical and quantum rebound attacks on AES-like hashing by exploiting related-key differentials ⋮ Improved classical and quantum algorithms for subset-sum ⋮ Attacks on beyond-birthday-bound MACs in the quantum setting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The extended \(k\)-tree algorithm
• Quantum algorithms for the \(k\)-XOR problem
• Decoding linear codes with high error rate and its impact for LPN security
• Quantum multicollision-finding algorithm
• An efficient quantum collision search algorithm and implications on symmetric cryptography
• Improved combinatorial algorithms for the inhomogeneous short integer solution problem
• Dissection-BKW
• An algorithmic framework for the generalized birthday problem
• Refinements of the k-tree Algorithm for the Generalized Birthday Problem
• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Adversary lower bound for the k-sum problem
• Search via Quantum Walk
• Improved Generic Algorithms for Hard Knapsacks
• Квантовые атаки на итерационные блочные шифры
• Quantum lower bounds for the collision and the element distinctness problems
• FSBday
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• The Knapsack Hash Function proposed at Crypto’89 can be broken
• Strengths and Weaknesses of Quantum Computing
• Quantum Algorithms for the Subset-Sum Problem
• Quantum Walk Algorithm for Element Distinctness
• Quantum cryptanalysis of hash and claw-free functions
• Noise-tolerant learning, the parity problem, and the statistical query model

This page was built for publication: Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms