Deriving Indistinguishability from Unpredictability: Tools and Applications in Pseudorandomness

Abstract

Proving that a distribution P is “close to uniform” is an integral part of many problems in pseudorandomness, and is often defined either in terms of indistinguishability—no algorithm (possibly required to be efficient) should be able to distinguish between P and the uniform distribution, or unpredictability—the distribution P should have high entropy, or be unpredictable by any (efficient) algorithm. In most cases, the application will require the former type of guarantee, although the latter can sometimes be easier to reason about. In this thesis, we develop tools to relate these notions, and apply information-theoretic reasoning to problems in complexity theory and cryptography: • We extend the definition of randomness extractors to allow the error to be measured in terms of an arbitrary distance measure, and extend the connection between extractors and averaging samplers (Zuckerman, Rand. Struct. Alg.‘97) to an arbitrary family ℱ of test functions and the integral probability metric defined by ℱ. Using this connection, we show that extractors for the Kullback–Leibler (KL) divergence are subgaussian samplers as defined by Błasiok (SODA‘18). By showing that KL extractors exist with essentially the same parameters as standard extractors (explicitly and non-explicitly), we construct the first explicit subgaussian samplers matching the best known constructions of averaging samplers for [0, 1]-bounded functions in the parameter regime where the approximation error ε and failure probability δ are subconstant. • We introduce hardness in relative entropy, a new notion of hardness for search problems which on the one hand is satisfied by all one-way functions and on the other hand implies both next-block pseudoentropy and inaccessible entropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively, thereby shedding light on the apparent “duality” between them. • We show that the moment generating function of the KL divergence between the empirical distribution of n independent samples from a distribution P over a finite alphabet of size k (i.e. a multinomial distribution) and P itself is no more than that of a gamma distribution with shape k − 1 and rate n. The resulting exponential concentration inequality becomes meaningful (less than 1) when the divergence ε is larger than (k − 1)/n, whereas the standard method of types bound requires ε > 1/n · log(n+k−1 choose k−1) ≥ (k − 1)/n · log(1 + n/(k − 1)), thus saving a factor of order log(n/k) in the standard regime of parameters where n ≫ k. • We systematically study the relationship between f-divergences and integral probability metrics (IPMs) from the perspective of convex duality. Starting from a tight variational representation of the f-divergence, we derive a generalization of the moment generating function, which we show exactly characterizes the best lower bound of the f-divergence as a function of a given IPM. Using this characterization, we obtain new bounds while also recovering in a unified manner well-known results, such as Hoeffding’s lemma, Pinsker’s inequality and its extension to subgaussian functions, and the Hammersley–Chapman–Robbins bound. The variational representation also allows us to prove new results on topological properties of the divergence which may be of independent interest.