Name
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 epsilon by a circuit of size O( 2^n epsilon^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 delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^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 epsilon by a circuit of size O(2^k epsilon^2).Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.ICALP.2017.39 | ICALP |
DocType | Volume | Citations |
Conference | abs/1704.08678 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Krzysztof Pietrzak | 1 | 1513 | 72.60 |
| Maciej Skorski | 2 | 12 | 15.13 |