Improved Quantum Algorithms for the k-XOR Problem

André Schrottenloher

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, 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 .

Note: Full version of the paper.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Major revision. SAC 2021
Keywords: Quantum algorithms merging algorithms k-XOR k-SUM bicomposite 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

BibTeX

@misc{cryptoeprint:2021/407,
      author = {André Schrottenloher},
      title = {Improved Quantum Algorithms for the k-{XOR} Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/407},
      year = {2021},
      url = {https://eprint.iacr.org/2021/407}
}