Fine-Grained Cryptography

on YouTube ↗54m

" summary

Focuses on cryptography against n^c adversaries and gives concrete constructions and limits: builds fine-grained one-way/PRG candidates from planted kSum / planted k-clique via a search-to-decision reduction based on Impagliazzo–Naor ideas, uses a k-sparse Goldreich–Levin step implemented with compressed‑sensing/expander matrices, and gets quasi‑linear recovery in k but incurs a 1/k loss. Shows Merkle‑puzzle style key agreement at roughly quadratic-time security and exhibits formal barriers to amplification and to noninteractive gaps beyond quadratic.

AI-written summary · about

" chapters (9)

1. 0:00Fine-grained cryptography intro
2. 3:17Adversarial models in crypto
3. 12:13Complexity and natural problems
4. 22:49Weak one-way functions
5. 25:31Pseudorandom generators
6. 33:10kSum search-to-decision
7. 43:24Public key crypto
8. 48:29Mixed regimes and PoW
9. 51:43Open questions

" related talks

• 42mUsing the Planted Clique Conjecture for Cryptography: Public-Key Encryption from...Riddhi Ghosal · Obfuscation
• 43mCode-based CryptographySimona Samardjiska · Post-Quantum Cryptography Conference Amsterdam 2023
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 08mCryptography from Ideal LatticesDamien Stehlé · The Mathematics of Modern Cryptography
• 10mCryptography 10 Years Later: Obfuscation, Proof Systems, and Secure ComputationAbhishek Jain · 9th Annual Simons Institute Industry Day
• 01h 02mLattices and the NIST PQ-crypto Standardization ProcessDamien Stehlé · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols
• 32mSymmetric Cryptanalysis IJunjie Cheng, Juan Grados · RSA Conference 2023