Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders
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. Bot...