Non uniform attacks against pseudoentropy

Download
OA IST-2017-893-v1+1_LIPIcs-ICALP-2017-39.pdf 601.00 KB [Published Version]

Conference Paper | Published | English

Scopus indexed

Corresponding author has ISTA affiliation

Department
Series Title
LIPIcs
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.
Publishing Year
Date Published
2017-07-01
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume
80
Article Number
39
Conference
ICALP: Automata, Languages and Programming
Conference Location
Warsaw, Poland
Conference Date
2017-07-10 – 2017-07-14
ISSN
IST-REx-ID
697
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
e95618a001692f1af2d68f5fde43bc1f


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar