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 $\widetilde{\mathcal{O}}(2^{7n/24})$.
Category / Keywords: secret-key cryptography / Quantum algorithms, merging algorithms, k-XOR, k-SUM, bicomposite search. Original Publication (with major differences): SAC 2021 Date: received 26 Mar 2021, last revised 2 Sep 2021 Contact author: andre schrottenloher at m4x org Available format(s): PDF | BibTeX Citation Note: Full version of the paper. Version: 20210902:140408 (All versions of this report) Short URL: ia.cr/2021/407