Paper 2022/278
Incompressiblity and Next-Block Pseudoentropy
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
- Published elsewhere. Minor revision. ITCS
- Keywords
- incompressibilitynext-block pseudoentropysparse languages
- Contact author(s)
-
iftachh @ tauex tau ac il
noammaz @ gmail com
jadsilbak @ gmail com - History
- 2025-12-12: revised
- 2022-03-02: received
- See all versions
- Short URL
- https://ia.cr/2022/278
- License
-
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},
url = {https://eprint.iacr.org/2022/278}
}
