Paper 2021/407
Improved Quantum Algorithms for the k-XOR Problem
André Schrottenloher
Abstract
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. Applications include 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. The generic study of quantum algorithms k-XOR (and variants) was started by Grassi et al. (ASIACRYPT 2018), in the case where many solutions exist. At EUROCRYPT 2020, Naya-Plasencia and Schrottenloher defined a class of "quantum merging algorithms" 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 new, simplified representation of merging trees that makes their analysis easier. As a consequence, we improve the quantum time complexity of 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 generic algorithms for Single-solution k-XOR. For example, we give an algorithm for 4-XOR (or 4-SUM) in quantum time $\widetilde{\mathcal{O}}(2^{7n/24})$.
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Quantum algorithmsmerging algorithmsk-XORk-SUMbicomposite search.
- Contact author(s)
- andre schrottenloher @ m4x org
- History
- 2021-09-02: revised
- 2021-03-27: received
- See all versions
- Short URL
- https://ia.cr/2021/407
- License
-
CC BY