2022-03-27
Improved quantum algorithms for the k-XOR problem
Publication
Publication
The k-XOR problem can be generically formulated as the following: given many n-bit strings generated uniformly at random, find k distinct of them which XOR to zero. This generalizes collision search (two equal elements) to a k-tuple of inputs. This problem has become ubiquitous in cryptanalytic algorithms, including variants in which the XOR operation is replaced by a modular addition (k-SUM) or other non-commutative operations (e.g., the composition of permutations). The case where a single solution exists on average is of special importance. At EUROCRYPT 2020, Naya-Plasencia and Schrottenloher defined a class of quantum merging algorithms for the k-XOR problem, obtained by combining quantum search. They represented these algorithms by a set of merging trees and obtained the best ones through linear optimization of their parameters. In this paper, we give a simplified representation of merging trees that makes their analysis easier. We give better quantum algorithms for the Single-solution k-XOR problem by relaxing one of the previous constraints, and making use of quantum walks. Our algorithms subsume or improve over all previous quantum algorithms for Single-solution k-XOR. For example, we give an algorithm for 4-XOR (or 4-SUM) in quantum time O~ (2 7n/24).
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1007/978-3-030-99277-4_15 | |
| Lecture Notes in Computer Science | |
| Algebraic Methods for Stronger Crypto | |
| International Conference on Selected Areas in Cryptography | |
|
Schrottenloher, A. (2022). Improved quantum algorithms for the k-XOR problem. In Proceedings of the International Conference on Selected Areas in Cryptography (pp. 311–331). doi:10.1007/978-3-030-99277-4_15 |
|
