Public-key encryption from planted clique and noisy k-LIN
Original title: Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy $k$-$\mathsf{LIN}$ Over Expanders
The construction is secure against polynomial-size adversaries under two average-case conjectures and answers a STOC 2010 question.
The paper gives a public-key encryption scheme secure against polynomial-size adversaries. It assumes n to the power log-alpha-n hardness of planted clique for any alpha in (0,1), plus a milder hardness conjecture for noisy k-LIN over expanders. The second conjecture is not known to imply public-key encryption by itself. The scheme answers an open question from Applebaum, Barak, and Wigderson at STOC 2010.
Unconfirmed: Security is conditional on two conjectures that remain unproven.
- Both assumptions are average-case variants of NP-complete problems studied for decades.
- Unconditional lower bounds in restricted computation models are cited as support.
- Planted-clique hardness is assumed for every alpha between 0 and 1.
From the original article
1 min read at arxiv.orgWe give a public key encryption scheme that is provably secure against poly-size adversaries, assuming $n^{\log^αn}$ hardness of the standard planted clique conjecture, for any $α\in (0,1)$, and a relatively mild hardness conjecture about noisy $k\mbox{-}\mathsf{LIN}$ over expanders that is not known to imply public-key encryption on its own.
By Riddhi Ghosal · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.