Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy k-XOR Over Expanders

In this talk, we will introduce a new public key encryption assuming hardness of the standard planted clique conjecture, and a relatively mild hardness conjecture about noisy k-LIN over expanders that is not known to imply public-key encryption on its own. Both of our conjectures correspond to natural average-case variants of NP-complete problems and have been studied for multiple decades, with unconditional lower bounds supporting them in a variety of restricted models of computation. Our work extends the seminal work by Applebaum, Barak, and Wigderson [STOC'10] and gives the first such construction using the planted clique conjecture in the standard form.