Non uniform attacks against pseudoentropy
LIPIcs
Pietrzak, Krzysztof Z
Skórski, Maciej
ddc:005
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.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2017
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.ista.ac.at/record/697
https://research-explorer.ista.ac.at/download/697/4701
Pietrzak KZ, Skórski M. Non uniform attacks against pseudoentropy. In: Vol 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2017.39">10.4230/LIPIcs.ICALP.2017.39</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.ICALP.2017.39
info:eu-repo/semantics/altIdentifier/issn/18688969
info:eu-repo/grantAgreement/EC/H2020/682815
https://creativecommons.org/licenses/by/4.0/
info:eu-repo/semantics/openAccess