2026-07-21T19:38:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7473 2024-03-06T10:40:20Z ddc:004 open_access

Non-Uniform Attacks Against Pseudoentropy Pietrzak, Krzysztof Skorski, Maciej pseudoentropy non-uniform attacks 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 Krzysztof Pietrzak and Maciej Skorski 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.39 urn:nbn:de:0030-drops-74738 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.39 eng https://creativecommons.org/licenses/by/3.0/legalcode