Cryptology ePrint Archive: Report 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.

Category / Keywords: nearest neighbor problem \and approximate matching \and $k$-list problem \and birthday problem \and collision search \and low weight polynomials

Original Publication (in the same form): IACR-TOSC-2017

Date: received 23 Feb 2017

Contact author: leif both at rub de, alex may at rub de

Available format(s): PDF | BibTeX Citation

Version: 20170227:145435 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]