Incompressiblity and Next-Block Pseudoentropy
summary
A k-incompressible distribution provably has (k−2) bits of next-block pseudoentropy: the contrapositive builds an efficient compressor from any estimator with small KL divergence, so incompressibility forces high next-bit unpredictability. The proof uses the KL-hardness equivalence (Vadhan–Zheng), an arithmetic encoding (2-point-wise) compressor for the estimator-induced online distribution, and a KL-divergence accounting argument. As a corollary, any samplable X that is (H(X)+2)-incompressible yields one-way functions.
AI-written summary · about
chapters (12)
- 0:00Start
- 0:58Example: One-Time Pad
- 2:20Pseudorandom generator
- 6:42Pseudoentropy to Psedurandomness
- 10:26Computational Analogs of Entropy
- 23:31Incompressibility & One-Way Functions
- 28:16Some Preliminaries (and the proof)
- 29:51Compression Schemes
- 31:44KL Divergence
- 32:30Compressing Wrong Distributions
- 41:23Next-bit Estimation → Compression
- 44:23Uniform Incompressibility
related talks
21mIncompressiblity and Next-Block Pseudoentropy
48mOutput-Compressing Randomized Encodings and Applications
53mFoundations 1
47mHardness of LWE on General Entropic Distributions
41mReducibility and Statistical-Computational Gaps from Secret Leakage
36mBounded indistinguishability for simple sources
31mRandomness Extraction from Somewhat Dependent Sources
01h 17mCrypto + Meta-complexity 2