The generalized birthday problem, or k-xor problem, has many applications in cryptography. Interestingly, there is a gap between its provable query complexity and its best known time complexity, obtained with Wagner’s algorithm. Quantum algorithms for this problem have been studied by Grassi et al. in 2018, with a similar gap remaining. In this work, we answer most of the open questions they left, thanks to a general unified framework (« merging trees ») of which the algorithms of Grassi et al. are all special cases.
Using Mixed Integer Linear Programming, we obtain the optimal time complexities for k-xor in this merging framework, and prove our observations for all values of k. Contrary to the classical case, where the complexity depends only on the biggest power of 2 included in k, Grassi and al. first observed an exponential quantum time separation between 2-xor and 3-xor. We extend this to all k and prove a separation between any pair of them in the quantum RAM model (also improving the case k = 3).
When the quantum space complexity (number of qubits) is limited to linear, we obtain quantum time speedups on the classical k-xor for half of the values of k, improving also all previously known results. We also study the parallelization of merging trees.
Finally, we extend this study to quantum multicollision search.