Paper 2019/501

Optimal Merging in Quantum k-xor and k-sum Algorithms

María Naya-Plasencia and André Schrottenloher

Abstract

The k-xor problem or Generalized Birthday Problem asks, given k lists of bit-strings, for a k-tuple among them XORing to 0. If the lists are unbounded, the best classical (exponential) time complexity has withstood since Wagner's CRYPTO 2002 paper, while many subsequent works have improved its memory complexity, given better time-memory tradeoffs, and logarithmic improvements. In this paper, we study quantum algorithms for several variants of the k-xor problem. When quantum oracle access is allowed, we improve over previous results of Grassi et al. for almost all values of k. We define a set of "merging trees" which represent strategies for quantum and classical merging in k-xor algorithms, and prove that our method is optimal among these. We provide, for the first time, quantum speedups when the lists can be queried only classically. We also extend our study to lists of limited size, up to the case where a single solution exists. We give quantum dissection algorithms that outperform the best known for many k, and apply to the multiple-encryption problem. Our complexities are confirmed by a Mixed Integer Linear Program that computes the best strategy for a given k-xor problem. All our algorithms apply when considering modular additions instead of bitwise XORs.