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

Itai Dinur, Nathan Keller, Ohad Klein

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 le…