International Association
for Cryptologic Research

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

In this work, we introduce the sparse LWE assumption, an assumption that draws inspiration from both Learning with Errors (Regev JACM 10) and Sparse Learning Parity with Noise (Alekhnovich FOCS 02). Exactly like LWE, this assumption posits indistinguishability of $(\mathbf{A}, \mathbf{s}\mathbf{A}+\mathbf{e} \mod p)$ from $(\mathbf{A}, \mathbf{u})$ for a random $\mathbf{u}$ where the secret $\mathbf{s}$, and the error vector $\mathbf{e}$ is generated exactly as in LWE. However, exactly like sparse LPN the coefficient matrix $\mathbf{A}$ is chosen randomly from $\mathbb{Z}^{n\times m}_{p}$ so that each column has Hamming weight exactly $k$ for some small $k$. We study the problem in the regime where $k$ is a constant or polylogarithmic. The primary motivation for proposing this assumption is efficiency. Compared to LWE, the samples can be computed and stored with roughly $O(n/k)$ factor improvement in efficiency. Our results can be summarized as: \begin{itemize} \item {\bf Foundations:} We show several properties of sparse LWE samples, including: 1) The hardness of LWE/LPN with dimension $k$ implies the hardness of sparse LWE/LPN with sparsity $k$ and arbitrary dimension $n \geq k$. 2) When the number of samples $m=\Omega(n \log p)$, length of the shortest vector of a lattice spanned by rows of a random sparse matrix is large, close to that of a random dense matrix of the same dimension (up to a small constant factor). 3) Trapdoors with small polynomial norm exist for random sparse matrices with dimension $n \times m = O(n \log p)$. 4) Efficient algorithms for sampling such matrices together with trapdoors when the dimension is $n \times m = \tilde{O}(n^2)$. \item {\bf Cryptanalysis:} We examine the suite of algorithms that have been used to break LWE and sparse LPN. While naively many of the attacks that apply to LWE do not exploit sparsity, we consider natural extensions that make use of sparsity. We propose a model to capture all these attacks. Using this model we suggest heuristics on how to identify concrete parameters. Our initial cryptanalysis suggests that concretely sparse LWE with a modest $k$ and slightly bigger dimension than LWE will satisfy similar level of security as LWE with similar parameters. \item {\bf Applications:} We show that the hardness of sparse LWE implies very efficient homomorphic encryption schemes for low degree computations. We obtain the first secret key Linearly Homomorphic Encryption (LHE) schemes with {\em slightly super-constant}, or even {\em constant}, overhead, which further has applications to private information retrieval, private set intersection, etc. We also obtain secret key homomorphic encryption for arbitrary constant-degree polynomials with slightly super-constant, or constant, overhead. \end{itemize} We stress that our results are preliminary. However, our results make a strong case for further investigation of sparse LWE.