Paper 2019/501

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

María Naya-Plasencia and André Schrottenloher

Abstract

The k-xor or Generalized Birthday Problem aims at finding, given k lists of bit-strings, 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. If the lists are bounded (of the same size) and such that there is a single solution, the dissection algorithms of Dinur et al. (CRYPTO 2012) improve the memory usage over a simple meet-in-the-middle. In this paper, we study quantum algorithms for the k-xor problem. With unbounded lists and quantum access, we improve previous work by Grassi et al. (ASIACRYPT 2018) for almost all k. Next, we extend our study to lists of any size and with classical access only. We define a set of ``merging trees'' which represent the best known strategies for quantum and classical merging in k-xor algorithms, and prove that our method is optimal among these. 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 also when considering modular additions instead of bitwise xors. This framework enables us to give new improved quantum k-xor algorithms for all k and list sizes. Applications include the subset-sum problem, LPN with limited memory and the multiple-encryption problem.

Note: The code was modified and the paper now links to the new version.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
DOI
10.1007/978-3-030-45724-2_11
Keywords
generalized birthday problemquantum cryptanalysislist-merging algorithmsk-list problemsmultiple encryptionMILP
Contact author(s)
andre schrottenloher @ m4x org
maria naya_plasencia @ inria fr
History
2021-12-09: last of 2 revisions
2019-05-20: received
See all versions
Short URL
https://ia.cr/2019/501
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/501,
      author = {María Naya-Plasencia and André Schrottenloher},
      title = {Optimal Merging in Quantum k-xor and k-sum Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2019/501},
      year = {2019},
      doi = {10.1007/978-3-030-45724-2_11},
      note = {\url{https://eprint.iacr.org/2019/501}},
      url = {https://eprint.iacr.org/2019/501}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.