The Approximate k-List Problem

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