| Title | : | Cryptographic applications of k-SUM |
| Speaker | : | Akhil Vanukuri (IITM) |
| Details | : | Wed, 15 May, 2024 11:00 AM @ SSB-334 |
| Abstract: | : | In the average-case k-SUM problem, given r integers chosen uniformly at random from {0, . . . , 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 ^{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. In this talk, we focus on the k-SUM problem in the sparse regime, especially one of the variants called the planted k-SUM, where a random solution is planted in a randomly generated instance and has to be recovered. We show that by assuming mild hardness of k-XOR (a variant of planted k-SUM problem), we can construct different cryptographic primitives such as Public Key Encryption (PKE), Somewhat Homomorphic Encryption (SHE), etc. We construct 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. Based on joint work with Shweta Agrawal, Sagnik Saha, Nikolaj I. Schwartzbach and Prashant Nalini Vasudevan. |
