Paper 2022/278

Incompressiblity and Next-Block Pseudoentropy

Iftach Haitner, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
incompressibilitynext-block pseudoentropysparse languages
Contact author(s)
noammaz @ gmail com
History
2022-03-02: received
Short URL
https://ia.cr/2022/278
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/278,
      author = {Iftach Haitner and Noam Mazor and Jad Silbak},
      title = {Incompressiblity and Next-Block Pseudoentropy},
      howpublished = {Cryptology ePrint Archive, Paper 2022/278},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/278}},
      url = {https://eprint.iacr.org/2022/278}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.