Paper 2015/384

Condensed Unpredictability

Maciej Skorski, Alexander Golovnev, and Krzysztof Pietrzak

Abstract

We consider the task of deriving a key with high HILL entropy (i.e., being computationally indistinguishable from a key with high min-entropy) from an unpredictable source. Previous to this work, the only known way to transform unpredictability into a key that was $$ indistinguishable from having min-entropy was via pseudorandomness, for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent limitation that from a source with $$ bits of unpredictability entropy one can derive a key of length (and thus HILL entropy) at most $$ bits. In many settings, e.g. when dealing with biometric data, such a $$ bit entropy loss in not an option. Our main technical contribution is a theorem that states that in the high entropy regime, unpredictability implies HILL entropy. Concretely, any variable $$ with $$ bits of unpredictability entropy has the same amount of so called metric entropy (against real-valued, deterministic distinguishers), which is known to imply the same amount of HILL entropy. The loss in circuit size in this argument is exponential in the entropy gap $$, and thus this result only applies for small $$ (i.e., where the size of distinguishers considered is exponential in $$). To overcome the above restriction, we investigate if it's possible to first ``condense'' unpredictability entropy and make the entropy gap small. We show that any source with $$ bits of unpredictability can be condensed into a source of length $$ with $$ bits of unpredictability entropy. Our condenser simply ``abuses" the GL construction and derives a $$ bit key from a source with $$ bits of unpredicatibily. The original GL theorem implies nothing when extracting that many bits, but we show that in this regime, GL still behaves like a ``condenser" for unpredictability. This result comes with two caveats (1) the loss in circuit size is exponential in $$ and (2) we require that the source we start with has \emph{no} HILL entropy (equivalently, one can efficiently check if a guess is correct). We leave it as an intriguing open problem to overcome these restrictions or to prove they're inherent.

Note: The paper accepted to ICALP 2015.