Non-uniform attacks against pseudoentropy

Abstract: De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over

n

-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping

n - 1

to

n

bit strings), can be distinguished from the uniform distribution with advantage

e p s i l o n

by a circuit of size

O (2^{n} e p s i l o n^{2})

. We generalize this result, showing that a distribution which has less than

k

bits of min-entropy, can be distinguished from any distribution with

k

bits of

d e l t a

-smooth min-entropy with advantage

e p s i l o n

by a circuit of size

O (2^{k} e p s i l o n^{2} / d e l t a^{2})

. As a special case, this implies that any distribution with support at most

2^{k}

(e.g., the output of a pseudoentropy generator mapping

k

to

n

bit strings) can be distinguished from any given distribution with min-entropy

k + 1

with advantage

e p s i l o n

by a circuit of size

O (2^{k} e p s i l o n^{2})

. Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions.

Recommendations

Cited In (4)

This page was built for publication: Non-uniform attacks against pseudoentropy