Paper 2017/182

The Approximate $k$-List Problem

Leif Both and Alexander May

Abstract

We study a generalization of the $k$-list problem, also known as the Generalized Birthday problem. In the $k$-list problem, one starts with $k$ lists of binary vectors and has to find a set of vectors -- one from each list -- that sum to the all-zero target vector. In our generalized {\em Approximate $k$-list problem}, one has to find a set of vectors that sum to a vector of small Hamming weight $\omega$. Thus, we relax the condition on the target vector and allow for some error positions. This in turn helps us to significantly reduce the size of the starting lists, which determines the memory consumption, and the running time as a function of $\omega$. For $\omega = 0$, our algorithm achieves the original $k$-list run-time/memory consumption, whereas for $\omega = \frac n 2 $ it has polynomial complexity. As in the $k$-list case, our Approximate $k$-list algorithm is defined for all $k=2^m, m>1$. Surprisingly, we also find an Approximate 3-list algorithm that improves in the run-time exponent compared to its 2-list counterpart for all $0< \omega < \frac n 2$. To the best of our knowledge this is the first such improvement of some variant of the notoriously hard 3-list problem. As an application of our algorithm we compute small weight multiples of a given polynomial with more flexible degree than with Wagner's algorithm from Crypto 2002 and with smaller memory consumption than with Minder and Sinclair's algorithm from SODA 2009.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TOSC 2017
Contact author(s)
leif both @ rub de
alex may @ rub de
History
2017-02-27: received
Short URL
https://ia.cr/2017/182
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/182,
      author = {Leif Both and Alexander May},
      title = {The Approximate $k$-List Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2017/182},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/182}},
      url = {https://eprint.iacr.org/2017/182}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.