2021/10/31 by Itai Dinur, Dinur, Itai, Nathan Keller +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Cryptographic Implementations and Security #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology
paper · pdf · doi:10.48550/arxiv.2111.00486
openalex publication_date 2021/10/31 · openalex created_date 2021/11/22 · openalex updated_date 2026/07/28
An average-case variant of the k-SUM conjecture asserts that finding k\nnumbers that sum to 0 in a list of r random numbers, each of the order rk,\ncannot be done in much less than r lceil k/2 rceil time. On the other\nhand, in the dense regime of parameters, where the list contains more numbers\nand many solutions exist, the complexity of finding one of them can be\nsignificantly improved by Wagner's k-tree algorithm. Such algorithms for\nk-SUM in the dense regime have many applications, notably in cryptanalysis.\n In this paper, assuming the average-case k-SUM conjecture, we prove that\nknown algorithms are essentially optimal for k= 3,4,5. For k>5, we prove\nthe optimality of the k-tree algorithm for a limited range of parameters. We\nalso prove similar results for k-XOR, where the sum is replaced with\nexclusive or.\n Our results are obtained by a self-reduction that, given an instance of\nk-SUM which has a few solutions, produces from it many instances in the dense\nregime. We solve each of these instances using the dense k-SUM oracle, and\nhope that a solution to a dense instance also solves the original problem. We\ndeal with potentially malicious oracles (that repeatedly output correlated\nuseless solutions) by an obfuscation process that adds noise to the dense\ninstances. Using discrete Fourier analysis, we show that the obfuscation\neliminates correlations among the oracle's solutions, even though its inputs\nare highly correlated.\n