Skip to content
Book

Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders

Jun 2025 · Symposium on the Theory of Computing · 2 citations · 78 references
Computer Science

Abstract

We give a public key encryption scheme that is provably secure against poly-size adversaries, assuming nlogαn hardness of the standard planted clique conjecture, for any α ∈ (0,1), 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 encryption scheme answers an open question in a seminal work by Applebaum, Barak, and Wigderson [STOC’10].

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.