Unifying Computational Entropies via Kullback–Leibler Divergence

Abstract

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. Thus, hardness in relative entropy unifies the latter two notions of computational entropy and sheds light on the apparent “duality” between them. Additionally, it yields a more modular and illuminating proof that one-way functions imply next-block inaccessible entropy, similar in structure to the proof that one-way functions imply next-block pseudoentropy (Vadhan and Zheng, STOC ‘12).

R. Agrawal—Supported by the Department of Defense (DoD) through the National Defense Science & Engineering Graduate Fellowship (NDSEG) Program.

Y.-H. Chen—Supported by NSF grant CCF-1763299.

T. Horel—Supported in part by the National Science Foundation under grants CAREER IIS-1149662, CNS-1237235 and CCF-1763299, by the Office of Naval Research under grants YIP N00014-14-1-0485 and N00014-17-1-2131, and by a Google Research Award.

S. Vadhan—Supported by NSF grant CCF-1763299.

A Missing Proofs

Lemma A.1

For all $t \ge 1$, $f:x\mapsto \frac{x}{1-(1-x)^t}$ is convex over [0, 1].

Proof

We instead show convexity of $\tilde{f}:x\mapsto f(1-x)$. A straightforward computation gives:

$$\begin{aligned} \tilde{f}''(x) = \frac{x^{t-2}t\big (t(1-x)(x^t+1) - (1+x)(1-x^t)\big )}{(1-x^t)^3} \end{aligned}$$

so that it suffices to show the non-negativity of $g(x) = t(1-x)(x^t+1) - (1+x)(1-x^t)$ over [0, 1]. The function g has second derivative $t(1-x)(t^2-1)x^{t-2}$, which is non-negative when $x\in [0, 1]$, and thus the first derivative $g'$ is non-decreasing. Also, the first derivative at 1 is equal to zero, so that $g'$ is non-positive over [0, 1] and hence g is non-increasing over this interval. Since $g(1) = 0$, this implies that g is non-negative over [0, 1] and f is convex as desired.

Theorem A.2

(Theorem 3.11 restated). Let $\varPi$ be a binary relation and let (Y, W) be pair of random variables supported on $\varPi$. If $(\varPi , Y)$ is $(t, \varepsilon )$-hard, then $(\varPi , Y, W)$ is $(t', \varDelta ')$ witness hard in relative entropy and $(t', \varDelta '')$ witness hard in $\delta$-min relative entropy for every $\delta \in [0,1]$ where $t' = \varOmega (t)$, $\varDelta ' = \log (1/\varepsilon )$ and $\varDelta '' = \log (\delta /\varepsilon )$.

Proof

We proceed similarly to the proof of Theorem 3.5. Let be a pair of algorithms with $\mathsf {\widetilde{G}}= (\mathsf {\widetilde{G}}_1, \mathsf {\widetilde{G}}_\mathsf {w})$ a two-block generator supported on $\varPi$. Define the linear-time oracle algorithm . Then

The witness hardness in relative entropy then follows by applying Jensen’s inequality (since $2^{-x}$ is convex) and the witness hardness in $\delta$-min relative entropy follows by Markov’s inequality by considering the event that the sample relative entropy is smaller than $\varDelta$ (this event has density at least $\delta$).