An Improved Transformation between HILL and Metric Conditional Pseudoentropy

Abstract

HILL Entropy and Metric Entropy are generalizations of the information-theoretic notion of min-entropy to the setting where an adversary is computationally bounded. The notion of HILL Entropy appeared in the breakthrough construction of a PRG from any one-way function, and has become the most important and most widely used de nition of computational entropy. In turn, Metric Entropy which is de ned as a relaxation of HILL Entropy, has been proven to be much easier to handle, in particular in the context of computational generalizations of the Dense Model Theorem. Fortunately, Metric Entropy can be converted, with some loss in quality, to HILL Entropy as shown by Barak, Shaltiel and Wigderson. In this paper we improve their result, slightly reducing the loss in quality of entropy. Interestingly, our bound is independent of size of the probability space in comparison to the result of Barak et al. Our approach is based on the theory of convex approximation in Lp-spaces.

-

1.1

Introduction

Computational Entropy

The Idea of Computational Entropy. The notion of entropy, as a measure of randomness, is a fundamental concept in information-theory. The need for computational versions of entropy comes from the fact that security de nitions based on classical information theoretic entropy notions are quite often too strong for \practical" purposes, where resources of adversaries are limited. The distribution which is not perfectly random might look random from the computational point of view, when nding the real di erence is simply ine cient. The metrics used to quantify the amount and quality of pseudorandomness are commonly called computational entropies.

HILL Entropy and Metric Entropy. The most popular approach of extending information-theoretic notions of entropy into computational case, is based on the notion of computational indistinguishability. We discuss it brie y below.

Given a class of boolean functions D and a parameter we say that two n-bit random variables X and Y are (D; )-indistinguishable if no function D from the class D can distinguish X and Y with the advantage better than . Formally E D(X) If D is the class of all circuits of size at most t we slightly abbreviate this notation and say that X and Y are (s; ) indistinguishable.

In theoretical computer science and especially in cryptography the most popular notion of entropy is the min-entropy (in contrast to information-theory where one uses extensively the Shannon entropy), because it measures randomness in terms of \hardness" of predictability. The min entropy of X given (possibly) Z is at least 2 k if one cannot predict X given Z = z, on average1 over z, better than with probability 2 k. Formally, for X and Z one de nes the average min-entropy [ 4 ] of X given Z as follows

He1 (XjZ) > k i

E hmax Pr[X = xjZ = z]i 6 2 k: z Z x Based on the concept of indistinguishability and min-entropy, one de nes computational HILL entropy [ 10 ] of X as the maximum amount of min-entropy in a random variable Y (taking values in the same set X) which is indistinguishable from X. This idea was extended to the conditional case (the presence of side information) by [ 11 ]. We can state the de nition as follows: HH1ILL;(s; ) (XjZ) > k if and only if there exists Y jointly distributed with Z of average min-entropy (given Z) at least k such that j E D(X; Z) E D(Y; Z)j 6 for all circuits D of size at most s.

Note that this captures the standard notion of pseudorandom distribution (for k = n). By switching the order of quanti ers and restricting to deterministic circuits one obtains a slightly weaker version, called computational metric entropy [ 1, 5 ]

HM1;det[0;1];(s; ) (XjZ) > k i for every deterministic [0; 1]-valued circuits D of size at most s there exists Y jointly distributed with Z of average min-entropy (given Z) at least k such that j E D(X; Z) E D(Y; Z)j 6 . In both de nitions the parameters s; quantify the quality of pseudorandomness: the bigger s and the smaller , the higher quality is. Metric entropy is known to be equivalent to HILL entropy with the same amount and some loss in quality parameters [ 1, 2 ]. There are very good reasons to introduce and study metricentropy: quite often it is much easier to prove a statement for metric-entropy and then pass to the HILL version. Actually, this strategy is unavoidable for the standard proof technique which uses the min-max theorem to switch the order of players in a game. Therefore, many facts on HILL entropy uses metric entropy explicitly or implicitly [ 1, 2, 5, 7, 14, 17 ]. Perhaps the most spectacular example is the e cient version of the Dense Model Theorem [ 5,14 ], being the key ingredient of the famous result of Tao and Ziegler on primes in arithmetic progressions [ 16 ]. The e cient version, which found many interesting applications in complexity 1 Sometimes one uses the stronger notion, called the worst-case min-entropy, when we require the same upper bound on guessing probability for every auxiliary input z, not only on average. theory, was originally proved using the idea of metric computational entropy in [ 14 ] and independently in [ 5 ]. A much simpler proof with signi cant improvements in quality was given in [ 6 ].

Conversions between HILL and metric entropy. The following result states that metric and HILL computational entropy are equivalent up to some loss in quality

Theorem 1 (Transformation between Metric and HILL Computational

Entropy [ 1 ]). Let X and Z be, respectively, n-bit and m-bit correlated random variables. Then where s0 = O s

HHILL;(s0; 0) (XjZ) > HM;det[0;1];(s; ) (XjZ) 2=(n + m) and 0 = + for arbitrary 2 (0; 1).

Remark 1. Since we have HHILL;(s; ) (XjZ) 6 HM;det[0;1];(s; ) (XjZ), the conversion in the other direction is lossless. 1.2

Our Contribution

Our result. We improve Theorem 1 of Barak, Shaltiel and Widgerson in the following way:

Theorem 2 (Dimension-independent transformation between metric

and HILL entropy). For any n-bit random variable X and a correlated random variable Z we have

HHILL;(s0; 0) (XjZ) > HM;det[0;1];(s; ) (XjZ) where and

2 (0; 1) is an arbitrary parameter, s0 = O s = n k.

In comparison to Theorem 1 we replace the factor n + m by + 1. Our result shows that the conversion does not depended on the dimension of the domain of X and Z but only on the entropy de ciency . While this does not o er signi cant improvement in the asymptotic setting, it might be of some interest in case when m is much longer than n (see for instance equivalence between HILL and unpredictability entropy of X given Z for short X [ 17 ]) or when the de ciency is very small. We also remark that our result automatically improves the best known parameters for the e cient dense model theorem by the factor of n.

Our techniques. Our results might be interesting because of the novel proof technique: instead of using Cherno Bounds for approximating convex hulls with uniformly small error as in [ 1 ], we show that it is enough to do the approximation with respect to the p-th norm induced by some appropriately chosen measure, and optimize the value of p. There is a lot of research focused on achieving better rates of convex approximations in Lp-spaces for some restricted class of functions. In case of the metric-to-HILL transformation (or similar result) it might be possible to obtain some further improvements for restricting classes of adversaries. 2=( + 1) , 0 = +

Organization of the Paper

In Section 2 we explain basic notions and provide necessary de nitions. The proof of our main technical result together with an improved Metric-to-HILL transformation appears in Section 3. In Section 4 we demonstrate a simple application: a slight improvement over the best known parameters for the Dense Model Theorem. 2

Preliminaries

Probabilities, measures and integrals. By X or PX we denote the probability mass function (distribution) of X, that is X (x) = PX (x) = Pr[X = x] for all x. A measure on a nite set is a function : ! R+ [ f0g. For notation convenience, we use the signs of sums and integrals interchangeably. The integral of a function D on E with respect to a measure is de ned as RE Dd = Px2E D(x) (x). For the integral over the entire domain we omit the subscript E.

Lp spaces. Given a nite set and a measure on one de nes the p-th norm of a real-valued function D de ned on as kDkp = R Dd Convex combinations. Given a set of real-valued functions C de ned on the same domain, by convt(C) we denote the set of all convex combinations of length at most t of members of C. That is, Ct = ( t

X i=1

i=1 Computational Entropy notions.

t iDi : X i = 1; i > 0 for i = 1; : : : ; t; Di 2 C for i = 1; : : : ; t )

De nition 1 (Conditional HILL Pseudoentropy [11]). Let X; Z be a joint

distribution with the following property: there exists Y of conditional min-entropy at least k given Z such that for all circuits D of size at most s we have j E D(X; Z)

E D(Y; Z)j 6 . Then we say that X given Z has k bits of HILL min-entropy of quality (s; ) and denote by HH1ILL;(s; ) (XjZ) > k.

Remark 2 (HILL entropy against di erent circuits classes). For conditional HILL entropy all kinds of circuits: deterministic boolean, deterministic real valued and randomized boolean (for the same size s), are equivalent [ 6 ].

De nition 2 (Conditional Metric Pseudoentropy [ 5 ]). Let X; Z be a joint distribution with the following property: for every deterministic boolean (respectively: deterministic real valued or boolean randomized) circuit D of size at most s there exists Y of (conditional min entropy at least k given Z such that j E D(X; Z; Y; Z) E D(Y; Z)j 6 . Then we say that X given Z has k bits of deterministic (respectively: deterministic real valued or boolean randomized) metric min-entropy of quality (s; ) and denote by HM1;detf0;1g;(s; ) (XjZ) (respectively: HM1;det[0;1];(s; ) (XjZ) and HM1;randf0;1g;(s; ) (XjZ)).

Main Result

In this section we prove our main technical result which inmediately implies Theorem 2.

Lemma 1 (Approximating long convex combinations with respect to high-min-entropy distributions.). Let X be an n-bit random variable, be

Z be a correlated m-bit random variable, and let C be a class of [0; 1]-valued function on f0; 1gn f0; 1gm. Let D 2 conv(C). Then for ` = 49(n + 1 k)= 2 there exists D` 2 conv`(C) such that and simultaneously

E jD(X)

D`(X)j 6 E jD(X)

D`(Y )j 6 for every distribution Y jointly distributed with Z such that H1(Y jZ) > k. Corollary 1. Lemma 1 implies Theorem 2 Proof (of Corollary 1). If HH1ILL;(s0; 0) (XjZ) < k then for every Y satisfying He1 (Y jZ) > k we nd D of size at most s0 such that j E D(X; Z) E D(Y; Z)j > 0. Replacing D by Dc of necessary we can assume that E D(X; Z) E D(Y; Z) > for some D of size s0 + 1. By applying the min-max theorem we get that there exists a convex combination D0 of circuits of size at most s0 + 1 such that E D(X; Z)

E D(Y; Z) > 0 8Y : He1 (Y jZ) > k That combination might be very long. But applying Lemma 1 we can approximate it by a combination D0 of at most O (n + 1 k)= 2 circuits of size s0 + 1 in such a way that the expectations with respect to X; Z and Y; Z di ers at most by =2. This way we obtain

E D0(X; Z)

E D0(Y; Z) > 0 2 =2 8Y : He1 (Y jZ) > k which nishes the proof.

Now we prove our main approximation result Proof (of Lemma 1). Consider the space of all functions on f0; 1gn+m. We start by the following trivial observation Claim 1. It su ces to show that for some D0 2 conv`(C) we have R jD d( X + Y ) 6 for all Y such that He1 (Y jZ) > k.

By applying the Holder Inequality, we immediately get Claim 2. For every functions D; D0 and every p; q > 1 such that p1 + 1q = 1 we have

Z jD (1) (2)

tu D0j (3) Now we give estimates on both factors on the right hand side of Equation (3). Claim 3. If q 2 [1; 2] then for any Y such that He1 (Y jZ) > k we have q

6 6 2q 1

X;Z

Y;Z q + q ! Y;Z q q 6 = =

Z Z Z

Z

Y ;Z q

d YZ=z

U q d U

d Z 2(q 1)(n H1 (Y jZ=z) d Z = 2(q 1)n Z 2 (q 1) H1 (Y jZ=z)d Z Y;Z q q

Z 6 2(q 1)n 2 H1 (Y jZ=z)d Z

q 1 6 2(q 1)n 2 He1 (Y jZ) q 1 = 2(q 1)(n k)

X;Z q <

Z 1d = 2 To bound the second term note that the functional q convex as a function of Y;Z (being a composition of an a ne function and the p-th norm). Therefore, the maximum among all distributions Y; Z satisfying He1 (Y jZ) > k, which form a convex set, is attained at an extreme point. This means that the maximum is attained for a distribution (Y ; Z) such that the distribution Y jZ=z is at for every z and the conditional min-entropy of Y given Z is exactly k. Since (x; z) = U (x) Z (z) and Y ;Z (x; z) = Y jZ=z (x) Z (z) we obtain Y;Z !

X;Z+ Y;Z We shall estimate two terms in Equation (4) separately. Since X;Z (x; z) + U;Z (x; z) = (x; z) for all x; z we have X;Z (x; z) < By applying the Jensen Inequality to the function u ! uq 1 (which is concave by the assumption on q) we get (4) (5) (6)

is (7) Plugin Equation (7) and Equation (6) into Equation (5) yields 6 2q 1 2 + 2(q 1)(n k)

= 2q + 2(q 1)(n+1 k): Claim 4. Suppose that p > 2. Then for any D 2 conv(C) and ` > 1 there exists D` 2 conv`(D) such that kD D`kp < 1:74pp=`.

Proof. The proof relies on the following approximation result on rates of convex approximation, which generalizes the famous Maurey-Johnes-Barron Theorem. Lemma 2 (Convex approximation in Lp spaces [ 3 ]). Let E be an Lp space with 1 6 p < +1. Suppose that S E, f 2 conv(S) and let K > 0 be such that for all g 2 S we have kg f kp 6 K. Then for any ` we have

min s2conv`(S) k f skp 6

KCp `1 1t where t = min(2; p) and Cp = 1 if 1 6 p 6 2, Cp = p2[ ((p + 1)=2)=p ]1=p for 2 < p < +1.

Remark 3. The constant Cp can be estimated using the following approximation for the gamma function [ 12 ], valid for x > 1: p (x=e)xp2x + 0:33 <

(x + 1) < p (x=e)xp2x + 0:36 From this we nd that Cp < 0:87pp for all p > 2.

The claim follows by setting E to be the space of [0; 1]-valued functions on f0; 1gn f0; 1gm and K = R 1d = 2. tu By Claim 3 and Claim 4 combined with Claim 2 and Claim 1 it su ces to nd p > 2 (which automatically ensures q 2 [1; 2]) and ` such that If k > n 1 then we put p = q = 2. Then it su ces to ensure that 1:74p2=`(22 + 22)1=2 6 which is equivalent to 6:96p` 6 . Suppose that k 6 n 1. By the inequality (a+b)r 6 ar +br valid for a; b > 0 and 0 < r 6 1, we see that it su ces if 1:74pp=` 2 + 2(n+1 k)=p) 6 . For p = n + 1 k we obtain 6:96p` 6 . This nishes the proof.

Application to the Dense Model Theorem

Dense Model Theorem. Given a pair of two distributions W and V over the same nite domain we say that W is -dense in V if and only if Pr[W = x] 6 Pr[V = x]= 2. The dense model theorem [ 16 ], specialized to the boolean case, can be formulated as follows: Theorem 3 (Dense Model Theorem.). Let D0 be a class of n-bit boolean functions, R be uniform over f0; 1gn, X be an n-bit random variable and let X0 be -dense in X. If X and R are (D; )-indistinguishable then there exists a distribution R0 which is -dense in R such that X0 and R0 are (D0; 0)-indistinguishable, where 0 = ( = )O(1) and D consists of all functions of the form g(D1; : : : ; D`) where Di 2 D0, ` = poly(1= ; 1= ) and g is some function.

Informally, this statement reads as follows: if a distribution X0 is dense in a pseudorandom distribution X, then X0 must be indistinguishable from a distribution dense in the uniform distribution. Note that the indistinguishability parameters for X0 are worse than for X: to achieve (D0; 0)-indistinguishably we need to start with smaller than 0 and a class D su ciently more complicated than D0. Note also that for the statement to be computationally meaningful we need g to be e cient.

Applications of the Dense Model Theorem. E cient versions of the Dense Model Theorem have found applications in di erential privacy [ 13 ], pseudoentropy and leakage-resilient cryptography [ 2, 5 ], graph decompositions [ 14 ], and further applications in additive combinatorics [ 9 ]. We refer the reader to [ 15 ] for a survey.

Comparison of different formulations. Below we compare the di erent versions of the Dense Model Theorem. Note that an equivalent statement in language of pseudoentropy was given in [ 5 ]. Below we show how to derive from our Lemma 1 a version of the Dense Model Theorem where n was replaced by log(1= ), which is typically much smaller. Corollary 2. Dense Model Theorem (Theorem 3) holds with 0 = O( = ), g being a linear threshold and ` = O(log(1= )=( = )2. 2 The term \ -dense" comes from the fact that V can be written as a convex combination of W with weight and some other distribution with weight 1 Proof. We show how to reduce the formulation of the Dense Model Theorem to the statement about HILL entropy. We start by the following observation: Claim 5. X0 is -dense in X if and only if X0 can be written as XjA for some event A of probability .

Proof. of Claim Consider a random variable A 2 f0; 1g jointly distributed with X as follows: Pr[X = x; A = 1] = Pr[X0]. By the assumption on X and X0 we have Pr[X = x; A = 1] 6 1 and thus this distribution is well de ned, in particular we have Pr[A = 1] = and Pr[XjA = 1] = Pr[X0]. In the other hand if we have X0 =d XjA then Pr[X0 = x] = Pr[X = x; A]= Pr[A] 6 Pr[X = x] 6 Pr[X = x]= Pr[A] and hence X0 is Pr[A]-dense in X. tu The second fact we need is the so called leakage lemma for metric-entropy Lemma 3 ( [ 7 ], reformulated). Let X be a random variable, A be an event of probability , and let D be a class of [0; 1]-valued functions. Suppose that there exists D such that E D(XjA) E D(Y ) > 0 for all Y of min-entropy at least k log(1= Pr[A]) and 0 = = Pr[A]. Then there exists a a function D0 being a threshold of some D 2 D (or its complement) such that E D0(X) E D0(Y ) > . The name \leakage lemma" is due to the fact that this implies HM1;det[0;1];s; ) (XjA) > HM1;D;s0 = Pr[A]) (X) log(1= Pr[A]) for s0 s. Now we are ready to give the proof. Suppose contrary, that the Dense Model Theorem is not true with the claimed parameters. Then for some event A of probability , some 0 and every distribution Y of min-entropy n log(1= ) (which is equivalent to be -dense in the uniform distribution) there exists D 2 D or D 2 1 D 2 D such that

E D(XjA)

E D(Y ) > 0 By applying a min-max theorem we get that there exists a long convex combination D of functions from D [ (1 D) such that

E D(XjA)

E D(Y ) > 0

8Y : H1 (Y ) > n log(1= ): Now we use our Lemma 1, with the class D [ (1 D) and replaced by 0=3 to approximate D by a convex combination D0 of length ` = O log(1= )= 02 . Then we get

E D0(XjA)

E D0(Y ) > 0

8Y : H1 (Y ) > n log(1= ): Note that D0 is a linear threshold of ` functions from D. By Lemma 3 we replace D0 by D00 which is again a linear threshold of ` functions from D and satis es E D00(X)

E D00(Y ) > 0 8Y : H1 (Y ) > n: Hence, we get a contradiction. tu

Conclusion

In this paper we improve the transformation between conditional Metric and HILL entropy by replacing the dimension factor by the entropy de ciency. This result immediately translates into a slightly improved version of the Dense Model Theorem. An interesting question is the problem of nding complexity lower bounds for that transformation.

References

1. Barak , B. , Shaltiel , R. , Wigderson , A. : Computational Analogues of Entropy . In: Arora, S. et al. (eds.) RANDOM-APPROX. pp. 200 - 215 , Springer ( 2003 )

2. Chung , K.-M., Kalai , Y.T. , Liu , F.-H. , Raz , R. : Memory Delegation. Cryptology ePrint Archive, Report 2011 /273, http://eprint.iacr.org/ ( 2011 )

3. Donahue , M.J. , Darken , C. , Gurvits , L. , Sontag , E.: Rates of convex approximation in non-hilbert spaces . In: Constructive Approximation , vol. 13 : 2 , pp. 187 - 220 , Springer-Verlag ( 1997 )

4. Dodis , Y. , Ostrovsky , R. , Reyzin , L. , Smith , A. : Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data . In: SIAM J. Comput. (March 2008 ), vol. 38 : 1 , pp. 97 { 139 , Society for Industrial and Applied Mathematics, http://dx.doi.org/10.1137/060651380 ( 2008 )

5. Dziembowski , S. , Pietrzak , K. : Leakage-Resilient Cryptography in the Standard Model . IACR Cryptology ePrint Archive , vol. 2008 , http://eprint.iacr.org/ 2008 /240 ( 2008 )

6. Fuller , B. , Reyzin , L. : Computational Entropy and Information Leakage . Cryptology ePrint Archive, Report 2012 /466, http://eprint.iacr.org/ ( 2012 )

7. Fuller , B. , Reyzin , L. : A uni ed approach to deterministic encryption: New constructions and a connection to computational entropy . TCC 2012 , vol. 7194 of LNCS, pp. 582 { 599 , Springer ( 2012 )

8. Gowers , W.T.: Decompositions, approximate structure, transference, and the Hahn-Banach theorem . ArXiv e-prints, http://adsabs.harvard.edu/abs/ 2008arXiv0811.3103G ( 2008 )

9. Gowers , W.T., Wolf , J.: Linear Forms and Higher-Degree Uniformity for Functions On Fpn . Geometric and Functional Analysis , vol. 21 : 1 , pp. 36 - 69 , SP Birkhuser Verlag Basel ( 2011 )

10. Hastad , J. , Impagliazzo , R. , Levin , L.A. , Luby , M.: A Pseudorandom Generator from any One-way Function . SIAM J. Comput. , vol. 28 : 4 , pp. 1364 - 1396 ( 1999 )

11. Hsiao , Ch .-Y., Lu , Ch.-J., Reyzin , L. : Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility . In: Proceedings of the 26th annual international conference on Advances in Cryptology (Berling , Heidelberg), EUROCRYPT '07 , pp. 169 - 186 , Springer-Verlag ( 2007 )

12. Mortici , Chr.: On Gospers formula for the gamma function . Journal of Mathematical Inequalities , vol. 5 : 4 , 611 - 614 ( 2011 )

13. Mironov , I. , Pandey , O. , Reingold , O. , Vadhan , S. : Computational Di erential Privacy . In: Proceedings of the 29th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '09 , pp. 126 - 142 , Springer-Verlag ( 2009 )

14. Reingold , O. , Trevisan , L. , Tulsiani , M. , Vadhan , S. : Dense Subsets of Pseudorandom Sets . In: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science , FOCS ' 08 , 76 - 85 , IEEE Computer Society, http://dx.doi.org/10.1109/FOCS. 2008 . 38 ( 2008 )

15. Trevisan , L. : Dense Model Theorems and Their Applications . In: Proceedings of the 8th Conference on Theory of Cryptography , TCC' 11 , 55 - 57 , Springer-Verlag ( 2011 )

16. Tao , T. , Ziegler , T. : The primes contain arbitrarily long polynomial progressions . Acta Mathematica , vol. 201 : 2 , pp. 213 - 305 , Springer Netherlands ( 2008 )

17. Vadhan , S. , Zheng , C.J.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions . In: Proceedings of the 44th symposium on Theory of Computing , STOC ' 12 , 817 - 836 , ACM, New York, USA ( 2012 )