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

Riddhi Ghosal; Isaac M. Hair; Aayush Jain; Amit Sahai

Paper 2025/1501

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

Riddhi Ghosal, University of California, Los Angeles

Isaac M. Hair

, UCLA, University of California, Santa Barbara

Aayush Jain, Carnegie Mellon University

Amit Sahai, University of California, Los Angeles

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].

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. STOC 2025
DOI: 10.1145/3717823.3718306
Keywords: Planted Clique k-LIN PKE Expander Graphs
Contact author(s): riddhi @ cs ucla edu
hair @ ucsb edu
aayushja @ andrew cmu edu
sahai @ cs ucla edu
History: 2025-08-28: approved; 2025-08-20: received; See all versions
Short URL: https://ia.cr/2025/1501
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1501,
      author = {Riddhi Ghosal and Isaac M. Hair and Aayush Jain and Amit Sahai},
      title = {Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy $k$-$\mathsf{{LIN}}$ Over Expanders},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1501},
      year = {2025},
      doi = {10.1145/3717823.3718306},
      url = {https://eprint.iacr.org/2025/1501}
}