# Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy $k$-$\\mathsf{LIN}$ Over Expanders

DevFeed: [Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy $k$-$\\mathsf{LIN}$ Over Expanders](<https://devfeed.tech/articles/using-the-planted-clique-conjecture-for-cryptography-public-key-encryption-from-planted-clique-and-noisy-k-mathsf-lin-over-expanders-126966.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.11701>)

Author: Riddhi Ghosal, Isaac M Hair, Aayush Jain, Amit Sahai

Published: 2026-11-10T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Cryptography and Security](<https://devfeed.tech/sources/arxiv-cryptography-and-security.md>)

Topics: [Cryptography](<https://devfeed.tech/topics/cryptography.md>), [Encryption](<https://devfeed.tech/topics/encryption.md>)

Tags: [cryptography](<https://devfeed.tech/tags/cryptography.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [encryption](<https://devfeed.tech/tags/encryption.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [public-key](<https://devfeed.tech/tags/public-key.md>), [security](<https://devfeed.tech/tags/security.md>)

## AI overview

The work gives a public-key encryption scheme provably secure against polynomial-size adversaries, assuming planted clique remains hard at the stated n^{log^α n} level for any α in (0,1), together with a relatively mild hardness conjecture for noisy k-LIN over expanders. The latter conjecture is not known to yield public-key encryption by itself. The authors describe both assumptions as natural average-case variants of NP-complete problems, studied for decades and supported by unconditional lower bounds in restricted computational models. The construction answers an open question from Applebaum, Barak, and Wigderson (STOC 2010).

## Source excerpt

arXiv:2611.11701v1 Announce Type: new Abstract: We give a public key encryption scheme that is provably secure against poly-size adversaries, assuming $n^{\log^\alpha n}$ hardness of the standard planted clique conjecture, for any $\alpha \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. 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].