Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR

arXiv:2111.00486v2 Announce Type: replace
Abstract: An average-case variant of the $k$-SUM conjecture asserts that finding $k$ numbers that sum to 0 in a list of $r$ random numbers, each of the order $r^k$, cannot be done in much less than $r^{\lceil k/2 \rceil}$ time. On the other hand, in the dense regime of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner's $k$-tree algorithm. Such …

arxiv case cryptanalysis cs.cc cs.cr list numbers order random random numbers xor