Quantum Algorithms for the $$k$$-xor Problem
| Autor: | Lorenzo Grassi, María Naya-Plasencia, André Schrottenloher |
|---|---|
| Přispěvatelé: | Institute of Applied Information Processing and Communications [Graz] (IAIK), Graz University of Technology [Graz] (TU Graz), Security, Cryptology and Transmissions (SECRET), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) |
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Quantum cryptanalysis Quantum algorithms Logarithm Computer science business.industry Xor problem 020206 networking & telecommunications Cryptography 0102 computer and information sciences 02 engineering and technology 3-xor 01 natural sciences Generalized birthday problem [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Amplitude amplification 010201 computation theory & mathematics K-xor 0202 electrical engineering electronic engineering information engineering Quantum algorithm List-merging algorithms business |
| Zdroj: | Advances in Cryptology – ASIACRYPT 2018-24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part I ASIACRYPT 2018-24th Annual International Conference on the Theory and Application of Cryptology and Information Security 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⟩ Lecture Notes in Computer Science Lecture Notes in Computer Science-Advances in Cryptology – ASIACRYPT 2018 Lecture Notes in Computer Science ISBN: 9783030033255 ASIACRYPT (1) |
| ISSN: | 0302-9743 1611-3349 |
| DOI: | 10.1007/978-3-030-03326-2_18 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|