  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 \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.
  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))$.
  - 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, as well as a new algorithm for
average-case $k$-XOR 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.
