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. |