Metric Pseudoentropy: Characterizations and Applications

Abstract

Metric entropy is a computational variant of entropy, often used as a convenient substitute of HILL Entropy, slightly stronger and standard notion for entropy in cryptographic applications. In this paper we develop a general method to characterize metric-type computational variants of entropy, in a way depending only on properties of a chosen class of test functions (adversaries). As a consequence, we obtain a nice and elegant geometric interpretation of metric entropy. We apply these characterization to simplify and modularize proofs of some important results, in particular: (a) computational dense model theorem, (b) derivation of the improved version of Leftover Hash Lemma and (c) equivalence between unpredictability entropy and HILL entropy for short strings.

-

1.1

Introduction

Computational Entropy

Entropy. Entropy, as a measure of uncertainty or randomness, is a fundamen

tal notion in information-theory. The most known metric of entropy is Shannon Entropy [ 15 ]. For cryptographic applications such as extracting randomness, it is more convenient to work with so called min-entropy, which gives an upper bound on the probability that computationally unbounded adversary can guess a value sampled according to a given distribution. A slightly weaker but also very useful, especially in the context of hashing, is the notion of collision entropy which upperbounds the probability that two independent samples of a given distribution collide.

Defining computational variants of entropy. Computational analogues of entropy can be de ned in di erent ways. In any case, we need to formalize that a distribution has, from a computational point of view, the same of almost the same properties like a distribution having \true" information-theoretic entropy. This might be based on hardness of compressing-decompressing, hardness of prediction or hardness of distinguishing. In this paper we follow the last approach, which is most widely used. A good survey of di erent entropy notions and their properties can be found in [ 3 ] and [ 12 ]. We stress that, contrarily to the information-theoretic case, for computational entropy it's not only the amount of entropy that matters but also its quality is important. Computational Indistinguishability. Indistinguishability is a fundamental concept in computational complexity and cryptography. For two distributions X; Y taking values in the same space, a class D of [0; 1]-valued functions (refereed to as the \attackers class") and a parameter (refereed to as the \distinguishing advantage"), we say that X and Y are (D; )-indistinguishable if for all D 2 D we have j E D(X) E D(Y )j 6 . An attacker D can distinguish X and Y if E D(X) E D(Y ) > 0 or E D(X) E D(Y ) < 0, and the far from 0 this di erence is, the better \advantage" he achieves. Sometimes we want to de ne indistinguishability between two sets X and Y of probability distributions. We can formalize this by saying that no single adversary D can achieve bigger than 0 advantage for every pair (X; Y ) where X comes from X and Y comes from Y.

Since the expectation E D(X) can be thought as the scalar product of vectors

representing D and the distribution of X, the concept of indistinguishability is exactly the same concept as the idea of separating hyperplanes.

Computational Entropy. Having formalized the concept of \computational

closeness", one can de ne the \computational" entropy, called also pseudoentropy, of a distribution X by one of the following ways: (a) (stronger) X is computationally indistinguishable from a single distribution having required amount of information-theoretic entropy (min-entropy,

Shannon Entropy etc.)

(b) (weaker) is computationally indistinguishable from a set of all distributions having required amount of information-theoretic entropy.

Both approaches turn out to be useful. Setting the underlying informationtheoretic entropy measure to be the min-entropy, for case (a) we obtain the notion of HILL entropy [ 9 ] which directly generalizes the notion of pseudorandomness, whereas for case (b) we get the notion of the so called Metric Entropy [ 3 ]. Roughly speaking, with HILL entropy one generalizes most of informationtheoretic facts about entropy, into the computational setting. Metric entropy is commonly thought as a less intuitive and understood notion than HILL entropy. Quite surprisingly it has been proven to be technically more convenient in many problems. The typical approach is to work with metric entropy and to convert it to HILL entropy (which is possible with some loss in quality [ 3 ]). For example, the use of metric entropy simpli es and improves the proof of the computational variant of the dense model theorem [ 2 ], applicable in leakage-resilient cryptography [ 7 ]. Notions of pseudoentropy have found also important applications in general complexity theory, for example in [ 18 ] a HILL-like variant of

Shannon entropy is used to simplify the construction of a PRG from a one-way function. These two examples show also that the notion of pseudoentropy is a key ingredient of important or even breakthrough results and as such is worth of studying.

Worst Case Distributions. In problems which involve computational indistinguishability it is often convenient to know the distributions which makes the attacker's advantage maximal. This distribution is typically subjected to some entropy restrictions. In particular, one might ask the following question

Given D and X, what is the best (minimal) attacker advantage j j E D(X) E D(Y )j over all distributions Y of entropy as least k? Dj =

An answer to this question yields a bound on how (computationaly) close is X to the set of all distributions of entropy k. Such problems arises naturally where one uses HILL and Metric entropy, see for instance [3,5,18].

1.2

Our Results

Summary of our contribution. As mentioned, the concept of characterizing

the \worst case" distribution which optimizes the attacker advantage is very common, thought not always explicitly stated [ 2,3,5,14 ]. In this paper we give a uniform treatment of this idea and use to obtain characterizations for pseudoentropy and other interesting corollaries.

Characterizing Metric Pseudoentropy via Optimizing Attacker's Advantage. Using standard constrained optimization techniques, we develop a general method to characterize metric-type pseudoentropy. A characterization is based on explicitly calculating the distribution which minimizes the attacker's advantage, subject to entropy constraints. These characterizations could be used in studying properties of variants of pseudoentropy based on entropy di erent than min-entropy. In particular, they could be applied in studying the problem of comparing the amount of metric pseudoentropy against deterministic and randomized adversaries, or verifying the so called \chain rule". We also unify the de nitions of metric and HILL entropy in a nice geometric way. Applications: the power of pseudoentropy characterizations. Our technique leads to interesting corollaries besides the basic properties of pseudoentropy. From the characterization of metric pseudo-entropy we immediately obtain the computational Dense Model Theorem [ 2,7,14 ]. Extending our characterization into the conditional case when side information is available to the attacker, we reprove equivalence between unpredictability and indistinguishability based de nition of pseudoentropy for short strings [ 18 ]. Finally, from the characterization of collision-pseudoentropy we derive the improved Leftover Hash

Lemma 1. Our results show that metric entropy is a powerful tool which deserves the systematic study.

2

Preliminaries

Entropy notions. The min-entropy of a distribution X equlaolgs(PH1(X) = log(maxx Pr[X = x]). The collision entropy of X is H2(X) = x Pr[X = x]2). If there is side information Z, we de ne the average conditional min-entropy [ 6 ] of X given Z by He1(XjZ) = log(Ez Z maxx Pr[X = xjZ = z]).

Computational advantage. The advantage of an attacker D in distinugish

ing random variables X and Y , which take values in the same space, is de ned to be D(X; Y ) = E D(X) E D(Y ).

Computational Entropy. There is many ways to de ne computational analogues of entropy. We follow the most popular approach, which is based on the concept of computational indistinguishability.

De nition 1 (HILL Pseudoentropy [9]). Let X be a distribution with the

following property: there exists Y of min-entropy at least k such that for all circuits D of size at most s we have j D(X; Y )j 6 . Then we say that X has k bits of HILL min-entropy of quality (s; ) and denote by HH1ILL;(s; ) (X) > k. Remark 1 (HILL entropy against di erent circuits classes). It is known that for HILL entropy all kind of circuits: deterministic boolean, deterministic real valued and randomized boolean, are equivalent (for the same size s). That's why we can abbreviate the notation and omit declaring circuits type in De nition 1. De nition 2 (Metric Pseudoentropy [ 3 ]). Let X be a 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 min-entropy at least k such that j D(X; Y )j 6 . Then we say that X 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; ) (X) (respectively: HM1;det[0;1];(s; ) (X) and HM1;randf0;1g;(s; ) (X)).

De nitions of HILL and metric entropy for entropy notions di erent than minentropy, for instance collision entropy can be obtained by replacing min-entropy with collision entropy in De nition 1 and De nition 2.

Remark 2 (Metric Entropy against di erent circuits class). For metric minentropy, it does not matter if the deterministic circuits are boolean or real valued (see [ 12 ] and the errata of [ 3 ]). However, this is not true for the conditional case and does not extend to other entropy notions.

Computational Entropy - Side information. Sometimes we assume that information Z correlated to X might be available to an adversary.

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

distribution with the following property: there exists Y of average conditional min-entropy at least k given Z such that for all circuits D of size at most s we have j D(X; Z; 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 3 (HILL entropy against di erent circuits classes). Similarly to Remark

2, here all kinds of circuits: deterministic boolean, deterministic real valued and randomized boolean, are equivalent (for the same size s).

De nition 4 (Conditional Metric Pseudoentropy [2]). 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 average conditional min entropy at least k given Z such that j D(X; Z; 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)).

There is a variant of conditional pseudoentropy where (X; Z) is required to be computationally close to (Y; Z0) but Z0 is not necessarily the same as Z. This notion is called the \relaxed" HILL entropy [ 12 ] and denoted by HHILL rlx;(s; ) (X) (for metric variants HM rlx;detf0;1g;(s; ) (X) and HM rlx;det[0;1];(s; ) (X) ). Typically we want Z to be the same as Z01 but this relaxed notion is also useful [ 8,12 ]. It satis es the so called chain rule, a property desired in leakage-resilient cryptography, which doesn't hold for HILL entropy [ 11 ].

Relations between HILL and Metric Pseudoentropy. For any \reasonable" notion of (information-theoretic) entropy, metric and HILL variants are equivalent up to some loss in quality parameters s; .

Lemma 1 (HILL vs Metric Pseudoentropy, [3]). Let H be an entropy

notion which is concave2. Then for any n-bit random variable X we have

HHILL;(s0; 0) (X) > HM;det[0;1];(s; ) (X) where 2 (0; 1) is arbitrary, s0 = O s 2=n and 0 = for conditional pseudoentropy and relaxed pseudoentropy, with s0 = O s where m is the length of Z. + . The same is true

2 n+m 3

Characterizing Metric Pseudoentropy

In what follows we assume that H is a concave entropy notion (like min-entropy

or collision entropy), and that all distributions and distinguishers are over f0; 1gn. 3.1

Connections to Separating Hyperplanes

We start with the following simple observation, which gives a nice geometrical

formulation of the de nition of pseudo-entropy. We say that the sets X and Y of probability distributions are (D; )-indistinguishable if there exists no adversary D such that j E D(X) E D(Y )j > for all X 2 X and all Y 2 Y. It is easy to see that if X and Y are convex and if D is closed under complements (that is D 2 D implies 1 D 2 D) then this is equivalent to

There is no D 2 D such that: E D(X) E D(Y ) > for all X 2 X; Y 2 Y: 1 For instance, when Z represents information that adversary might have learned. 2 That is, a convex combination of distributions with entropy at least k is a distribution with entropy at least k. This assumption is ful lled for most notions, for example for all Renyi entropies which include min-entropy and collision entropy We can interpret the expectation E D(X) as the scalar product hD; PX i by identifying D and distributions of X with the vectors in R2n . Hence we can write the above condition as

There is no D 2 D such that: hD; PX PY i > for all X 2 X; Y 2 Y; which means that the distinguisher D is precisely a separating hyperplane. If D is a circuit class, X = fXg and Y = fY : H(Y ) > kg we obtain3

Corollary 1 (Alternative de nitions of metric and HILL entropy). Let

X be an n-bit random variable and let H be a concave entropy notion. Then

Y of entropy H at least k, (a) HHILL;(s; ) (X) > k i X is (D; )-indistinguishable from some Y of entropy

H at least k, where D is the class of boolean circuits4 of size s with n-inputs. (b) HM;detf0;1g;(s; ) (X) > k i X is (D; )-indistinguishable from the set of all where D is the class of all deterministic boolean circuits of size s with n-inputs (analogously for randomized and deterministic real valued circuits). 3.2

Reduction to Constrained Optimization

By the \geometric" view on pseudoentropy, given in Corollary 1, we obtain the following characterization of pseudoentropy.

Lemma 2 (Characterization of metric pseudoentropy). Let X and

H be as in Corollary 1. Then HM;detf0;1g;(s; ) (X) > k, respectively HM;det[0;1];(s; ) (X) > k if and only if for every boolean (respectively real valued) deterministic circuit D of size at most s we have where Y is optimal to the following optimization problem

E D(X) 6 E D(Y ) + ; maximize

Y s:t:

E D(Y ) H(Y ) > k : (1)

This results is useful if we can solve the optimization problem in Eqzatuib (1). In the next subsections we explain how to solve it in general and discuss the two concrete and simple cases: min-entropy and collision entropy.

3 We can assume that the class circuits of size at most s is closed under complements because every complement is of size at most s + 1. Formally we need to start with size s0 = s + 1 but we omit this negligible di erence 4 Randomized or deterministic- it makes no di erence

Maximizing Expectations Under Convex Constraints

We can characterize optimal solutions of [1] in terms of Lagrange multipliers.

Due to convexity, the characterization is both: necessary and su cient.

Lemma 3 (Maximizing expectation under convex constraints). Let f be a di erentiable convex real-valued function on Rd. Assume that a is a number such that minp f (p) < a where the minimum is over all probability vectors, and consider the following optimization program maximize

(pi)i

X Dipi

i 8> f (p) 6 a > >< pi 6 0 >> X pi = 1 > : i :

Then a feasible point p = p is optimal to [ 2 ] if and only if there exist 1 > 0; 2 > 0 and 3i 2 R for i = 1; : : : ; m such that the following relations hold

Di = 1(rf (p ))i 3i + 2 for i = 1; : : : ; m and the following complementary condition is satis ed: (2) (3) (4) pi

3i = 0

Proof. The Slater Constraint Quali cation holds, by the assumption on a, and

we have strong duality. In other words, the rst order Karush-Kuhn-Tucker condition is su cient and necessary [ 4 ]. The numbers 1; 2; 3i are exactly KKT multipliers for the convex program in Equation (2), and Equation (3) states that the gradient of the objective function is a combination of gradients of constraints.

The condition in Equation (4) means that we take only active constraints into

account. Finally, to the inequality constraints we assign non-negative multipliers which explains the requirement 1 > 0 and 3i > 0. tu

Remark 4. If f is not di erentiable, we replace the gradient of f in optimality conditions by the subdi erential of f , which always exists for a convex function.

3.4

Characterization of Metric Min Entropy

For H = H1 we obtain from Lemma 3 the following simple characterization of pseudoentropy based on min-entropy (see [ 3 ] for a restricted variant)

Theorem 1 (Characterization of metric min-entropy). Let X be an n-bit

r.v.. Then HM1;detf0;1g;(s; ) (X) > k, respectively HM1;det[0;1];(s; ) (X) > k if and only if for every boolean (respectively real valued) deterministic circuit D of size at most s with n inputs we have where Y is uniform over the set of 2k values of x which correspond to the biggest values of D(x).

Extending Lemma 3 by adding additional constraints, to cover the case of side information, we obtain the characterization of conditional metric entropy

Theorem 2 (Characterization of conditional metric min-entropy). Let

X and Z be, respectively, n and m-bit random variables. Then HM1;detf0;1g;(s; ) (X) > k (respectively HM1;det[0;1];(s; ) (X) > k) i for every boolean (respectively real valued) deterministic circuit D of size at most s on f0; 1gn+m we have

E D(X; Z) 6 E D(Y ; Z) + ; for Y such that Y jZ = z is uniform over the set fD(x; z) > t(z)g for every z, where the thresholds t(z) satisfy the following two conditions

E x Un

E max(D(x; z) t(z)) = const for all z

E [1=# fx : D(x; z) > t(z)g] 6 2 k 6 E [1=# fx : D(x; z) > t(z)g] : z Z 3.5

Characterization of Metric Collision Entropy

The characterization of the worst-case collision entropy distribution is slightly di erent. It is proportional to a distinguisher, after taking a threshold.

Theorem 3 (Characterization of metric collision entropy). Let X be an

n-bit r.v.. Then H2M;detf0;1g;(s; ) (X) > k, respectively H2M;det[0;1];(s; ) (X) > k if and only if for every boolean (respectively real valued) deterministic circuit D of size at most s with n inputs we have

E D(X) 6 E D(Y ) + ; where Y satis es

PY (x) = max(D(x) t; 0) for some t 2 R and > 0.

Remark 5. Note that t is a solution of E D0(U )2 = 2n k E D0(U ) 2 where D0(x) = max(D(x) t; 0) and = 2n E D0(U ). It follows that E D0(Y ) = 2n k E D0(U ) = E D0(U ) + pVarD0(U ) p2n k 1. 4 4.1

Applications

Computational Dense Model Theorem

We say that a distribution A is -dense in B if we have Pr[A = x] 6 Pr[B = x]= .

The Dense Model Theorem is the statement of the following form: if X is (s; )indistinguishable from the uniform distribution R and X0 is -dense in X, then

there exists a distribution R0 which is -dense in R and is (s0; 0)- indistinguishable from X0, where s0 and 0 depends as explicit functions on s and . In this sense, R is a dense \model" for X0. The dense model theorem was proved rst by Tao and Ziegler [ 17 ]. It's e cient versions5 have found important applications in complexity theory and cryptography [ 2,7,14 ], see also [ 16 ]. Below we recall a version with improved parameters, stated in language of pseudoentropy and called the \leakage lemma":

Theorem 4 (Leakage Lemma [2,7]). Let X be an n-bit random variable

HILL;(s; ) (X) > k and let Z be correlated with X. Then we have such that H1 HH1ILL;(s0; 0) (XjZ=z) > k0 where k0 = k log(1= Pr[Z = z]), s0 = O s 2=n and 0 = = Pr[Z = z] + , for any 2 (0; 1).

The lemma states that the amount of pseudoentropy due to leakage of t bits of information decreases roughly by t, hence its name. The original proof was simpli ed by the use of metric entropy [2]. We show how it can be simpli ed even further: just few lines using the basic facts about metric entropy!

Proof. If we can prove that

HM;detf0;1g;(s; = Pr[Z=z])) (XjZ=z) > HM;detf0;1g;(s; ) (X) 1 1 log(1= Pr[Z = z]) all boolean D of size at most s. From this we get then the result will follow by Lemma 1 and Remark 2. Note that by Theorem 1 for any X we have HM1;detf0;1g;(s; ) (X) > k if and only if E D(X) 6 j2Dkj + for

E D(XjZ=z) 6 E D(X)= Pr[Z = z] 6 jDj=2k Pr[Z = z] + = Pr[Z = z] for any D. Since the characterization is also su cient, the results follows. tu 4.2

Equivalence of HILL Entropy and Unpredictability Entropy for

Short Strings

Unpredictability entropy. The notion of unpredictability entropy is based

on the (assumed) hardness of guessing X given auxiliary information Z. More formally, we have HUnp;s(XjZ) > k if and only if no adversary of size at most s can predict X given Z better than with probability 2 k. For Z independent of X or of the relatively short length, this reduces to the min-entropy of X6.

Seperation from HILL entropy. If f is a one-way function, U is the uniform

distribution and X = U; Z = f (U ) then we see that XjZ has large amount of unpredictability. It is also easy to see that XjZ has almost no HILL entropy.

Equivalence for short strings. On the positive side, using metric entropy

and the characterization in Theorem 2, we reprove the following result of Vadhan and Zheng who established the equivalence when X is short7 5 With the loss at most poly(1= ) in s and . In the original proof the loss is exp(1= ) 6 Provided that s > 2mn so that the adversary can hardcore his best guess. 7 Logarithmically in the security parameter Theorem 5 ([ 18 ]). Suppose that X and Z are, respectively, n and m-bit random variables. Then HH1ILL;(s0; ) (XjZ) & HUnp;s(XjZ) with s0 = poly(2n;1= ) . s

The original proof is based on a result similar to Theorem 2 proved in a much more complicated way. We note that this part is a trivial consequence of KKT optimality conditions and also simplify the rest of the proof.

Proof (Sketch). We prove that HM1;det[0;1];(s0; ) (XjZ) < k implies HUnp;s(XjZ) < k. Suppose not, then we have E D(X; Z) E D(Y; Z) > for all Y such that He1(XjZ) > k. Let Y be the distribution which minimizes this expression, that is which maximizes E D(Y; Z). Let t(z) be as in Theorem 2 and denote D0(x; z) = max(D(x; z) t(z); 0) and let = Px D0(x; z) (according to Theorem 2 this sum does not depend on z). Consider the following predictor A:

On input z sample x according to the probability Pr[A(z) = x] = D0(x; z)= Note that Y jZ=z is uniform over the set fx : D0(x; z) > 0g. By Theorem 2 (the su ciency part) it follows that Y is also maximal for D. For every z we have E D0(Y jZ=z; z) = E D(Y jZ = z; z) t(z). We have also E D0(XjZ=z; z) > E D(XjZ=z; z) t(z) by the de nition of D0. This proves

E D0(X; Z)

E D0(Y; Z) > for all Y such that He1(XjZ) > k:

It is easy to observe that Pr [A(Z) = X] =

z Z

E D0(X; Z) > E z

E D0(Y jZ=z; z)

Px D0(x; z) > E 2 H1(Y jZ=z) z Z which is at least 2 k. The circuit D0(x; z) is of complexity 2m size(D), which is too big. However, if the domain of x is small, we can approximate the numbers t(z) given from relations in Theorem 2 (and even , from the second relation, for the uniform setting). Indeed, knowing that E max(D(U; z) t(z)) = , we estimate E max(D(U; z) t) for xed t and then nd a \right" value t = t(z) by the binary search. This way for every z we can approximate D0( ; z), and hence the distribution Pr[A(z) = x], up to a maximal error 2 k and with overwhelming probability 1 exp( poly(1= )), using poly(1= ) samples of D. On average over z we predict X with probability 2 k 2 k. tu

4.3 Improved Leftover Hash Lemma for Square-Secure Applications

In the key derivation problem we want to derive a secure m-bit key for some

application P from an imperfect source of randomness X. The generic approach is to use a randomness extractor. However, as implied by the RT-bounds [ 13 ], the min-entropy in X needs to be at least m + 2 log(1= ) if we want the derived key to be -secure. Fortunately, as shown by Barak et al. [ 1 ], for many cryptographic applications, one can reduce this loss by half, that is to L = log(1= ).

To this end, they introduce the class of square-secure applications, where the

squared advantage, over the uniform choice of keys, of every bounded attacker is small8. This class contains for example all unpredictability applications, stateless chosen plaintext attack secure encryption and weak pseudo-random functions.

The reduction of entropy loss follows by combining universal hashing with the following lemma

Lemma 4 ([ 1 ]). For a function D : f0; 1g` ! [ 1; 1] and X 2 f0; 1g` of collision entropy k we have

E D(X) 6 E D(U`) + pVarD(U`) p2` k 1: To see this, let WinA(r; h), for arbitrary attacker A 2 A, be the probability that A breaks the key r given in addition9 h and let DA(r; h) = WinA(r; h) 12 be its advantage. Let X be any n-bit random variable of min-entropy m + log(1= ). We apply a randomly chosen universal hash function10 H from n to m bits. It is easy to see that H(X); H is a distribution with collision entropy m+log jHj log(1+ ).

From the lemma it follows now that

E DA(H(X); H) 6 E DA(U; H) + pVarDA(U; H) p If we assume that maxh E DA(U; h) 6 (which means -security against A with the uniform key) and that maxh E DA(U; h)2 6 with = O ( ) (which means -square-security against A with the uniform key) then we achieve O( ) security for the extracted key, with entropy loss only log(1= ).

An alternative proof. We show that Theorem 3 implies Lemma 4. Indeed,

set k = ` and = 0 in Theorem 3. Let Y be the distribution of collision entropy at least k = ` which maximizes E D(Y ), and let t, and D0 be as in the characterization. Denote S = fx : D(x) > tg and let DjS be the restriction of D to the set S. Note that Y jS =d Y maximizes DjS and DjS (x) = D0jS (X) + t for every x 2 S. By Remark 5 we get E D(X) 6 E D(Y ) = E DjS (Y jS) = E DjS (US )+pVarDS (US ) q jSj2 k 1: We show that one can replace S by the f0; 1g` on the right hand side. This will follow by the following general lemma Lemma 5. Let X be a random variable, c > 1 be a constant and S be an event of probability P(S) > c 1. Then

E[XjS] + pVar[XjS] pcP(S) 1 6 E[X] + pVar[X] pc 1 (5) The proof follows by a few algebraic manipulations and is omitted. 8 Which essentially means that the probability that an attacker break the key is concentrated over keys 9 For the uniformly chosen key this doesn't help the adversary, at least in the nonuniform model 10 A family H functions from n to m bits is universal if Prh H[h(x) = h(x0)] = 2 m for x 6= x0

Some Further Applications

Lower bounds on square security. Using the characterization from

Theorem 3 one can derive some non-trivial lower bounds on square-security needed for key derivation. We discuss this problem in a separate paper.

References

1. Barak , B. , Dodis , Y. , Krawczyk , H. , Pereira , O. , Pietrzak , K. , Standaert , F.-X. , Yu , Y. : Leftover hash lemma, revisited . Cryptology ePrint Archive, Report 2011 /088 http://eprint. iacr.org/ ( 2011 )

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

3. Barak , B. , Shaltiel , R. , Wigderson , A. : Computational analogues of entropy . In: Arora, S. et al. (eds.) RANDOM-APPROX, Lecture Notes in Computer Science , vol. 2764 , pp. 200 { 215 , Springer ( 2003 )

4. Boyd , S. , Vandenberghe , L. : Convex optimization . Cambridge University Press, New York, NY, USA ( 2004 )

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

6. Dodis , Y. , Ostrovsky , R. , Reyzin , L. , Smith , A. : Fuzzy extractors: How to generate strong keys from biometrics and other noisy data . SIAM J. Comput . 38 , No. 1 , 97 { 139 ( 2008 )

7. Dziembowski , S. , Pietrzak , K. : Leakage-resilient cryptography in the standard model . IACR Cryptology ePrint Archive 2008 , p. 240 ( 2008 )

8. Gentry , C. , Wichs , D. : Separating succinct non-interactive argu- ments from all falsi able assumptions . Cryptology ePrint Archive, Report 2010 /610, http://eprint.iacr.org/ ( 2010 )

9. Hastad , J. , Impagliazzo , R. , Levin , L.A. , Luby , M.: A pseudorandom generator from any one-way function . SIAM J. Comput . 28 , No. 4 , 1364 { 1396 ( 1999 )

10. 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 (Berlin , Heidelberg), EUROCRYPT '07 , Springer-Verlag, pp. 169 { 186 ( 2007 )

11. Krenn , S. , Pietrzak , K. , Wadia , A. : A counterexample to the chain rule for conditional hill entropy . In: Sahai, A . (ed.) Theory of Cryptography, Lecture Notes in Computer Science , vol. 7785 , pp. 23 { 39 , Springer Berlin Heidelberg ( 2013 )

12. Reyzin , L.: Some notions of entropy for cryptography . In: Fehr, S . (ed.) Information Theoretic Security, Lecture Notes in Computer Science , vol. 6673 , pp. 138 { 142 , Springer Berlin Heidelberg ( 2011 )

13. Radhakrishnan , J. , Ta-Shma , A. : Bounds for dispersers, extractors, and depth-two superconcentrators . In SIAM JOURNAL ON DIS- CRETE MATHEMATICS 13 ( 2000 ), Metric Pseudoentropy: Characterizations and Applications 13 , ( 2000 )

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 (Washington, DC, USA), FOCS '08 , pp. 76 { 85 , IEEE Computer Society ( 2008 )

15. Shannon , C.E. : A mathematical theory of communication . In Bell system technical journal 27 ( 1948 )

16. Trevisan , L. , Tulsiani , M. , Vadhan , S. : Regularity, boosting, and e ciently simulating every high-entropy distribution . In Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity (Washington, DC), CCC '09 , pp. 126 { 136 , IEEE Computer Society ( 2009 )

17. Tao , T. , Ziegler , T. : The primes contain arbitrarily long polynomial progressions . In Acta Mathematica (English) , 201 : 2 , 213 { 305 ( 2008 )

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