Cryptology ePrint Archive: Report 2022/278

Incompressiblity and Next-Block Pseudoentropy

Iftach Haitner and Noam Mazor and Jad Silbak

Abstract: A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear.

We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k−2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) + 2)-incompressible, implies the existence of one-way functions.

Category / Keywords: foundations / incompressibility; next-block pseudoentropy; sparse languages

Date: received 1 Mar 2022

Contact author: noammaz at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20220302:142226 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]