Ohad Klein

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

2022

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 …