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@rub de Available format(s): PDF | BibTeX Citation Version: 20170227:145435 (All versions of this report) Short URL: ia.cr/2017/182 Discussion forum: Show discussion | Start new discussion