Skip to Main content Skip to Navigation
Conference papers

Quantum Algorithms for the k-xor Problem

Abstract : The k-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms proposed by Wagner more than fifteen years ago remain the best known classical algorithms for solving them, when disregarding logarithmic factors. In this paper we study these problems in the quantum setting, when considering that the elements are created by querying a random function (or k random functions) H : {0, 1} n → {0, 1} n. We consider two scenarios: in one we are able to use a limited amount of quantum memory (i.e. a number O(n) of qubits, the same as the one needed by Grover's search algorithm), and in the other we consider that the algorithm can use an exponential amount of qubits. Our newly proposed algorithms are of general interest. In both settings, they provide the best known quantum time complexities. In particular, we are able to considerately improve the 3-xor algorithm: with limited qubits, we reach a complexity considerably better than what is currently possible for quantum collision search. Furthermore, when having access to exponential amounts of quantum memory, we can take this complexity below O(2 n/3), the well-known lower bound of quantum collision search, clearly improving the best known quantum time complexity also in this setting. We illustrate the importance of these results with some cryptographic applications.
Document type :
Conference papers
Complete list of metadatas

Cited literature [52 references]  Display  Hide  Download
Contributor : André Schrottenloher <>
Submitted on : Monday, October 15, 2018 - 5:18:51 PM
Last modification on : Monday, March 4, 2019 - 11:08:22 AM
Long-term archiving on: : Wednesday, January 16, 2019 - 4:02:11 PM


Files produced by the author(s)




Lorenzo Grassi, María Naya-Plasencia, André Schrottenloher. Quantum Algorithms for the k-xor Problem. ASIACRYPT 2018 - 24th Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec 2018, Brisbane, Australia. pp.527-559, ⟨10.1007/978-3-030-03326-2_18⟩. ⟨hal-01896036⟩



Record views


Files downloads