Incompressibility and Next-Block Pseudoentropy

Explore the concept of incompressibility and its relationship to next-block pseudoentropy in this 47-minute lecture by Iftach Haitner from Tel Aviv University. Delve into the connection between k-incompressible distributions and cryptographic hardness assumptions. Learn how a k-incompressible distribution possesses (k-2) bits of next-block pseudoentropy, a refined notion of pseudoentropy. Discover the implications of this relationship for the existence of one-way functions, particularly when a samplable distribution X is (H(X) + 2)-incompressible. Gain insights into the ongoing research aimed at better understanding these computational analogs of entropy and their significance in cryptography.

Incompressiblity and Next-Block Pseudoentropy