Welcome to the resource topic for 2023/1867
Title:
Different Flavours of HILL Pseudoentropy and Yao Incompressibility Entropy
Authors: Pihla Karanko
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.
ePrint: https://eprint.iacr.org/2023/1867
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .