Paper 2023/1867
Different Flavours of HILL Pseudoentropy and Yao Incompressibility Entropy
Abstract
There are two popular ways to measure computational entropy in cryptography: (HILL) pseudoentropy and (Yao) incompressibility entropy. Both of these computational entropy notions are based on a natural intuition. - A random variable $X$ has $k$ bits of pseudoentropy if there exists a random variable $Y$ that has $k$ bits 'real' entropy and $Y$ is computationally indistinguishable from $X$. - A random variable $X$ has $k$ bits of incompressibility entropy if $X$ cannot be efficiently compressed to less than $k$ bits. It is also intuitive, that if a random variable has high pseudoentropy, then it should also have high incompressibility entropy, because a high-entropy distribution cannot be compressed. However, the above intuitions are not precise. Does 'real entropy' refer to Shannon entropy or min-entropy? What kind of correctness do we require from the compressor algorithm? Different papers use slightly different variations of both pseudoentropy and incompressibility entropy. In this note we study these subtle differences and see how they affect the parameters in the implication that pseudoentropy implies incompressibility.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- HILL pseudoentropyYao incompressibility entropycomputational entropy
- Contact author(s)
- pihla karanko @ aalto fi
- History
- 2023-12-06: approved
- 2023-12-05: received
- See all versions
- Short URL
- https://ia.cr/2023/1867
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1867,
author = {Pihla Karanko},
title = {Different Flavours of HILL Pseudoentropy and Yao Incompressibility Entropy},
howpublished = {Cryptology ePrint Archive, Paper 2023/1867},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1867}},
url = {https://eprint.iacr.org/2023/1867}
}
