Paper 2022/278 Original: eprint.iacr.org/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
- Preprint.
- History
- 2025-12-12: last updated
- 2022-03-02: published
- Short URL
- https://ia.cr/2022/278
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}