Conditional Computational Entropy, or
Toward Separating Pseudoentropy from Compressibility

by Chun-Yuan Hsiao, Chi-Jen Lu, and Leonid Reyzin

We study conditional computational entropy: the amount of randomness a distribution appears to have to a computationally bounded observer who is given some correlated information. By considering conditional versions of HILL entropy (based on indistinguishability from truly random distributions) and Yao entropy (based on incompressibility), we obtain:

This work appears in Advances in Cryptology -- Eurocrypt 2007, Moni Naor, editor, Lecture Notes in Computer Science 4515, Springer, 2007, pages 169-186. © IACR.