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.