CryptoDB
$k$-SUM in the Sparse Regime: Complexity and Applications
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2024 |
| Abstract: | 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 <= 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 >> 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. Complexity: 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 <= M <= 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/polylog(r)), then there is an algorithm running in time Otilde(T) that solves it with probability (1-o(1)). This enables us to use even relatively mild hardness of k-SUM/k-XOR in our cryptographic constructions. Our primary technical contribution is the proof of this result, which departs significantly from existing approaches to hardness amplification. - 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. Applications: 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. We are optimistic that this technique will find other applications in cryptography |
BibTeX
@inproceedings{crypto-2024-34309,
title={$k$-SUM in the Sparse Regime: Complexity and Applications},
publisher={Springer-Verlag},
author={Shweta Agrawal and Sagnik Saha and Nikolaj I. Schwartzbach and Akhil Vanukuri and Prashant Nalini Vasudevan},
year=2024
}