Using the Planted Clique Conjecture for Cryptography - Public-Key Encryption from Average-Case Hardness

Explore a groundbreaking approach to public-key encryption in this 42-minute conference talk that introduces a novel cryptographic construction based on the planted clique conjecture. Learn how this research extends the seminal work of Applebaum, Barak, and Wigderson from STOC'10 by presenting the first public-key encryption scheme that assumes hardness of the standard planted clique conjecture combined with a relatively mild hardness conjecture about noisy k-LIN over expanders. Discover how both conjectures correspond to natural average-case variants of NP-complete problems that have been studied for decades, with unconditional lower bounds supporting them across various restricted computational models. Understand the significance of this work in advancing cryptographic theory by demonstrating how problems that don't individually imply public-key encryption can be combined to create secure encryption schemes, opening new avenues for cryptographic constructions based on well-studied computational assumptions.