Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from...
summary
Claims a concrete construction of public-key encryption from planted clique combined with a mild noisy k-LIN over expanders assumption, giving a scheme that is quasi-polynomial secure under planted clique hardness against slightly quasi‑poly adversaries. Key idea: a PPT sampler that maps graphs to trapdoor matrices turns Gn(1/2) (or planted Gn(1/2+n−δ)) into an expanding sparse matrix while preserving a compressing submatrix when a clique is present. Encryption is AS+E vs random, decryption solves a small linear system; parameters use polylog sparsity and inverse‑polylog error.
AI-written summary · about
chapters (11)
- 0:00Planted clique assumptions
- 5:19Combinatorial assumptions for crypto
- 7:47Public-key encryption history
- 9:58Sparse LPN and noisy k-lin
- 17:25New PKE construction overview
- 22:04Security proof and decryption
- 26:19Graphs to expanders
- 34:52Sparsifying dense graphs
- 38:01Randomized graph product
- 40:32Public transformation and research
- 41:34Open problems and conclusion
related talks
54mFine-Grained Cryptography
41mReducibility and Statistical-Computational Gaps from Secret Leakage
58mObfuscation 2
46mOptimal Broadcast Encryption and More from Evasive LWE
01h 07mLattices and Encrypted Computation
31mIdentity-Based Encryption
21mLattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE
38mPre-Constrained Encryption