Paper 2021/1460
FineGrained Cryptanalysis: Tight Conditional Bounds for Dense kSUM and kXOR
Itai Dinur, Nathan Keller, and Ohad Klein
Abstract
An averagecase 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 algorithms for $k$SUM in the dense regime have many applications, notably in cryptanalysis. In this paper, assuming the averagecase $k$SUM conjecture, we prove that known algorithms are essentially optimal for $k= 3,4,5$. For $k>5$, we prove the optimality of the $k$tree algorithm for a limited range of parameters. We also prove similar results for $k$XOR, where the sum is replaced with exclusive or. Our results are obtained by a selfreduction that, given an instance of $k$SUM which has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense $k$SUM oracle, and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle's solutions, even though its inputs are highly correlated.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Major revision.FOCS 2021
 Keywords
 cryptanalysisfinegrained cryptographylower boundskSUMkXORWagner's algorithmgeneralized birthday problemdiscrete Fourier analysis
 Contact author(s)

dinuri @ cs bgu ac il
nathan keller27 @ gmail com  History
 20211106: received
 Short URL
 https://ia.cr/2021/1460
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1460, author = {Itai Dinur and Nathan Keller and Ohad Klein}, title = {FineGrained Cryptanalysis: Tight Conditional Bounds for Dense kSUM and kXOR}, howpublished = {Cryptology ePrint Archive, Paper 2021/1460}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1460}}, url = {https://eprint.iacr.org/2021/1460} }