In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,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 \leq 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.

In this work, 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 suggest new applications to cryptography. Our contributions are summarized below.

Complexity. First we study the complexity of these problems in the sparse regime and show:
- Conditional Lower Bounds. Assuming established conjectures about the hardness of average-case (non-planted) $k$-SUM/$k$-XOR when $M = r^k$, we provide non-trivial lower bounds on the running time of algorithms for planted $k$-SUM when $r^k\leq M\leq r^{2k}$.
- Hardness Amplification. We show that for any $M \geq r^k$, if an algorithm running in time $T$ solves planted $k$-SUM/$k$-XOR with success probability $\Omega(1/\text{polylog}(r))$, then there is an algorithm running in time $\tilde{O}(T)$ that solves it with probability $(1-o(1))$. This in particular implies hardness amplification for 3-SUM over the integers, which was not previously known. Technically, our approach departs significantly from existing approaches to hardness amplification, and relies on the locality of the solution together with the group structure inherent in the problem.
- New Reductions and Algorithms. We provide reductions for $k$-SUM/$k$-XOR from search to decision, as well as worst-case and average-case reductions to the Subset Sum problem from $k$-SUM. Additionally, we present a new algorithm for average-case $k$-XOR that is faster than known worst-case algorithms at low densities.

Cryptography. We show that by additionally assuming mild hardness of $k$-XOR, we can construct Public Key Encryption (PKE) from a weaker variant of the Learning Parity with Noise (LPN) problem than was known before. In particular, such LPN hardness does not appear to imply PKE on its own -- this suggests that $k$-XOR/$k$-SUM can be used to bridge ``minicrypt'' and ``cryptomania'' in some cases, and may be applicable in other settings in cryptography.

Added new algorithms and reductions in collaboration with Shweta and Akhil, and substantially changed the presentation of the paper.

In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a set of $k$ numbers that sum to $0$ modulo $M$ (this set is called a ``solution''). In the related $k$-XOR problem, given $k$ uniformly random Boolean vectors of length $\log{M}$, the objective is to find a set of $k$ of them whose bitwise-XOR is the all-zero vector. Both of these problems have widespread applications in the study of fine-grained complexity and cryptanalysis.

The feasibility and complexity of these problems depends on the relative values of $k$, $r$, and $M$. The dense regime of $M \leq r^k$, where solutions exist with high probability, is quite well-understood and we have several non-trivial algorithms and hardness conjectures here. Much less is known about the sparse regime of $M\gg r^k$, where solutions are unlikely to exist. The best answers we have for many fundamental questions here are limited to whatever carries over from the dense or worst-case settings.

We study the planted $k$-SUM and $k$-XOR problems in the sparse regime. In these problems, a random solution is planted in a randomly generated instance and has to be recovered. As $M$ increases past $r^k$, these planted solutions tend to be the only solutions with increasing probability, potentially becoming easier to find. We show several results about the complexity and applications of these problems.

Conditional Lower Bounds: Assuming established conjectures about the hardness of average-case (non-planted) $k$-SUM when $M = r^k$, we show non-trivial lower bounds on the running time of algorithms for planted $k$-SUM when $r^k\leq M\leq r^{2k}$. We show the same for $k$-XOR as well.

Search-to-Decision Reduction: For any $M>r^k$, suppose there is an algorithm running in time $T$ that can distinguish between a random $k$-SUM instance and a random instance with a planted solution, with success probability $(1-o(1))$. Then, for the same $M$, there is an algorithm running in time $\widetilde{O}(T)$ that solves planted $k$-SUM with constant probability. The same holds for $k$-XOR as well.

Hardness Amplification: For any $M\geq r^k$, if an algorithm running in time $T$ solves planted $k$-XOR with success probability $\Omega(1/\text{polylog}(r))$, then there is an algorithm running in time $\widetilde{O}(T)$ that solves it with probability $(1-o(1))$. We show this by constructing a rapidly mixing random walk over $k$-XOR instances that preserves the planted solution.

Cryptography: For some $M \leq 2^{\mathrm{polylog}(r)}$, the hardness of the $k$-XOR problem can be used to construct Public-Key Encryption (PKE) assuming that the Learning Parity with Noise (LPN) problem over $n$-bit vectors with constant noise rate is hard for $2^{n^{0.01}}$-time algorithms. Previous constructions of PKE from LPN needed either a noise rate of $O(1/\sqrt{n})$, or hardness for $2^{n^{0.5}}$-time algorithms.

Algorithms: For any $M \geq 2^{r^2}$, there is a constant $c$ (independent of $k$) and an algorithm running in time $r^c$ that, for any $k$, solves planted $k$-SUM with success probability $\Omega(1/8^k)$. We get this by showing an average-case reduction from planted $k$-SUM to the Subset Sum problem. For $r^k \leq M \ll 2^{r^2}$, the best known algorithms are still the worst-case $k$-SUM algorithms running in time $r^{\lceil{k/2}\rceil-o(1)}$.