k-SUM in the Sparse Regime: Complexity and Applications

In the average-case k-SUM problem, given r integers chosen uniformly at random from \( \{ 0,\dots ,M-1 \}\) , the objective is to find a “solution” set of k numbers that sum to 0 modulo M. In the dense regime of \(M \le r^k\) , where solutions exist with high probability, the complexity of these problems is well understood. Much less is known in the sparse regime of \(M\gg r^k\) , where solutions are unlikely to exist. Motivated by applications to cryptography, we initiate the study of the sparse regime for k-SUM and its variant k-XOR, especially their planted versions, where a random solution is planted in a randomly generated instance and has to be recovered. We provide evidence for the hardness of these problems and show applications to constructing public-key encryption schemes. Our contributions are summarized below.