Welcome to the resource topic for 2017/182
Title:
The Approximate k-List Problem
Authors: Leif Both, 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.
ePrint: https://eprint.iacr.org/2017/182
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .