{'fraction_non_alphanumeric': 0.04950622584800343, 'fraction_numerical': 0.01283812795191069, 'mean_word_length': 4.000214684413912, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A New Approximate Min-Max Theorem with Applications in Cryptography

We propose a novel proof technique that can be applied to attack a broad class of problems in computational complexity, when switching the order of universal and existential quantifiers is helpful. Our approach combines the standard min-max theorem and convex approximation techniques, offering quantitative improvements over the standard way of using min-max theorems as well as more concise and elegant proofs.


The Min-Max Theorem.
The celebrate von Neumann min-max theorem [Neu28] states that every finite, two-player, zero-sum game has an equilibrium in mixed strategies. That is, the maximum value of the minimum expected gain for one player is equal to the minimum value of the maximum expected loss for the other. Any zero-sum game can be represented as a payoff matrix where A(x, y) is the payoff in case when the X-player chooses strategy x ∈ X and the Y -player chooses strategy y ∈ Y , understood as a gain for the Xplayer and a loss of the Y -player. The basic moves x ∈ X, y ∈ Y are called pure strategies (think of one of 3 options in the rock-paper-scissors game). We allow the players to use randomized strategies, which are called mixed strategies (think of picking a random answer in the rock-paper-scissors game) represented formally as distributions p X (·), p Y (·) over X and Y respectively, and analyze the expected payoff E y∼pY ,x∼pX A(x, y) = y x p Y (y)p X (x)A(x, y).
If the player X goes first, she can guarantee her gain to be at least and when the player Y goes first he guarantees his lost to be at most where in both equations we used the fact that the second player always achieves the best response with some pure strategy. The min-max theorem guarantees that we have an equilibrium between the players.
Theorem (Min-Max Theorem [Neu28]). With the notation as above (and players using mixed strategies), we have under certain conditions imposed on the sets X, Y (for example both convex and compact subsets of a locally convex topological space) and the function f (for example continuity, convexity in y and concavity in x). The proofs typically use fixed point theorems. Min-Max theorems have a lot of applications in game theory, statistical decision theory, economy and theoretical computer science. In this paper we focus on applications in cryptography, and the simplest version will be enough for our discussion.

Switching the order of quantifiers by the min-max theorem
The min-max theorem may be used to change the order of quantifiers (minimization corresponds to the existential quantifier and maximization corresponds to the universal quantifier). A very good example is the classical hardcore lemma due to Impagliazzo [Imp95]. The lemma stated informally says that if for every algorithm A there exists a large set of inputs on which A fails to compute a fixed function f , then in fact there exists a large set of inputs on which every algorithm fails to compute f with probability close to 1 2 . This particular lemma falls into a broad class of results in complexity theory which can be proven using the min-max theorem. We explain this technique before giving more examples.
The general framework. Let A be a class of test functions (for example poly-size circuits) over a set of possible inputs I and C be a class of distributions over I satisfying certain desired properties (for example samplability, high density, high entropy etc.), and v be a payoff function quantifies how well A performs on the input X (for example, unpredictability or distinguishing advantage). Suppose that we want to prove the existence of a distribution with certain properties for which every algorithm has bad (or alternatively good) performance.
Dream Statement. There is a distribution over inputs (with some certain properties) such that every algorithm performs badly/well.
In many cases, it is much easier to prove a weaker version, which gives the existence of a distribution with desired properties but only for a chosen algorithm.
Weak Statement. For every algorithm there is a distribution over inputs (with some certain properties) such that it performs badly/well.
Note that this condition is considerably weaker. Indeed, we will see that in many applications proving the existence of a suitable distribution X for a fixed algorithm A is actually trivial. But the big question is whether Equation (2) implies Equation (1) Does the Weak Statement imply the Dream Statement? Suppose that Equation (2) holds. Can we conclude that Equation (1) also holds, with possibly somewhat weaker class A and a weaker parameter c?
Note that we allow for some loss in quality (a weaker class of algorithms or a weaker payoff). Indeed, if both sets C and A are convex the answer is trivially "yes", by the min-max theorem. However, in most applications the set A consists of efficient algorithms (circuits of a bounded size) and is not convex, because taking a mixed strategy corresponds to combining many algorithms by (possibly) inefficient sampling. For the same reason, the set C might not be convex. However, we might "embed" non-convex sets A and C into "almost" convex hulls of A ′ , C ′ which are (hopefully) still sufficiently good for our purpose, by taking moderately long mixed strategies, instead of arbitrarily long. Indeed, let where the conv operator denotes the convex hull. We get the following Approximate Min-Max Theorem If the condition (3) holds, then the Weak Statement implies the Dream Statement is true with A and C replaced by A ′ and C ′ .

Our contribution
Summary. This framework is well known (cf. [BSW03,RTTV08,TTV08,Hol05,VZ] to mention only some papers closely related to our cryptographic applications). What we offer, is a novel approximation technique. Previous works used to find A ′ and X ′ in convex hulls by a trivial Chernoff approximation argument. We observe that much better results are obtained with a carefully chosen convex approximation technique. Indeed, it turns out that in many cases the quantity |v(A, X) − v(A ′ , X ′ )| can be upper bounded by the Hölder Inequality which involves moments of A and X. These moments may be better estimated based on properties of the sets A and C which leads to quantitative improvements. We stress that the key component is the right choice of Hölder conjugates, that is the exponents for the corresponding L p , L q spaces.
Advantages and Applications of our framework. Using our technique we prove a whole bunch of results, reproving what is already known in a more clear and concise way, improving quantitative bounds, or obtaining new results. Details are given in Section 2.

Related Works.
The work of [VZ] provides a tool to derive good bounds for certain sets C, in the uniform settings. We stress that we consider only non-uniform adversaries here. In fact, our results can be probably made uniform by the use of constructive versions of auxiliary results on convex approximations we have applied (for example [DDGS97]

Applications
We briefly recall some basic notation and conventions. We say that two distributions X 1 , X 2 are (s, ǫ)-indistinguishable if for every A of size s we have

Impagliazzo Hardcore Lemma
Impagliazzo Hardcore Lemma. Suppose that are given a function f : {0, 1} n → {0, 1} that is mildly hard to predict by a class of circuits; for every circuit A from our class, A(x) and f (x) agree on at most, say, a 0.99 fraction of inputs x. This might happen when there is a set of noticeable size on which f is extremely hard to predict, meaning that there is (almost) no advantage over a random guess. This set could be as big as a 0.02 = 2(1 − 0.99) fraction of input.
Indeed, if f cannot be guessed better than with probability 1 2 on this set, then the probability that D agrees with f is at most 0.02 · 1 2 + 0.98 · 1 = 0.99. Quite surprisingly, this intuitive characterization is true. The first such result was proved by Impagliazzo [Imp95], with a sub-optimal hardcore density. An improved version with the optimal density of the hardcore set was found by Holenstein [Hol05]. Below we present the best possible result due to Klivans and Servedio, the lower bound was given in [LTW07].
Then for any δ ∈ (0, 1) there exists a event E of probability ǫ such that f is 1 − δ unpredictable under V |E by circuits of size s ′ = Ω sδ 2 / log(1/ǫ) , that is Our Contribution. We reprove Theorem 1 using the framework discussed in Section 1.3. Our approach has the following advantages over the related works: (a) It is derived from the standard min-max theorem. Previous proofs which achieve optimal parameters require involved iterative arguments [KS03,VZ]. (b) It is modular and much simpler than all alternative proofs. Indeed, the argument of Holenstein is non-optimal and involved. Also the argument given by Vadhan and Zheng depends on a non-trivial trick attributed to Nissan and Levy (which improves the hardcore density from ǫ 2 to ǫ) and the machinery is much heavier. Our approach does not require this trick and follows the most intuitive strategy: show that there is a hardcore for every fixed adversary and then switch the order of quantifiers. (c) We have identified the reason for non-optimality in previous proofs. Some authors even suggested that it might be impossible to get the tight parameters using the standard min-max theorem [VZ]. We show that this is not true. The problem is not with the standard min-max theorem but with an inadequate approximation argument in previous works, which do uniform approximation [Hol05].
A comparison is given below in Table 1.
Author Technique Hardcore Density Complexity Loss [Imp95] boosting (constructive approx.) Pr A sketch of proof. Assume without losing generality that f : and note that this definition makes sense also for circuits with real outputs. Let the property set C consists of conditional distributions of the form X = V |E where Pr [E] ǫ and E may vary 2 ; note that C is convex. Define A as the set of real-valued 3 circuits of size s, and let A ′ be the set of circuits of size s ′ = s δ −2 log(1/ǫ) . It is not hard to see that the assumption (4) implies Now we analyze what happens when we replace A by conv(A ′ ). We claim that To prove this, we show that the Hölder Inequality implies for A, A ′ and X ∈ C Setting ℓ = δ −2 log(1/ǫ) (so that A ∈ A), taking X = V |E which corresponds to A ′ according to Proposition 1, setting p = 2 log(1/ǫ) and putting this all together we get Proposition 5. This implies the following statement Proposition 3 ( Strong Statement ). For some X ∈ C we have v(X, A) δ for every A ∈ A ′ . which proves Theorem 1 (|v(X, A)| δ follows by considering A ′ closed under complements).
2.2 A (new) optimal hardcore lemma for metric pseudoentropy and applications to transformations.
Pseudoentropy notions extend classical information-theoretic entropy notions into computational settings. The following most widely used entropy notions capture what it means to be "computationally close" to a high entropy distribution.
Definition 1 (HILL Pseudoentropy [HILL99]). Let Y be a distribution with the following property: there exists Y ′ of min-entropy at least k such that for every A of size at most s we have Then we say that X has k bits of HILL entropy of quality (s, ǫ) and denote by H HILL s,ǫ (Y ) k. Definition 2 (Metric Pseudoentropy [BSW03]). Let Y be a distribution with the following property: for every A of size at most s there exists Y ′ of minentropy at least k such that we have | E A(Y ) − E Y ′ )| ǫ. Then we say that X has k bits of metric entropy of quality (s, ǫ) and denote by H Metric Pseudoentropy is an important research area, with applications in deterministic encryption, memory delegation [CKLR11], pseudorandom generators [HILL99,VZ]. Metric Pseudoentropy is much easier to deal with, and fortunately can be converted into HILL entropy with some loss in quality parameters (s, ǫ).
Our contribution. The following results shows that any distribution with metric pseudoentropy of 'moderate" quality has a kernel of HILL entropy with "strong" quality. We also conclude the optimal Metric-HILL transformation.
Theorem 2 (A HILL-pseudoentropy hardcore for metric pseudoentropy). Suppose that H Metric n − ∆ with s ′ = Ω(sδ 2 /(∆ + 1)) for every δ. In particular, H HILL s ′ ,ǫ+δ (Y ) n − ∆ One possible application of this fact is amplifying hardness of pseudoentropy with poor quality. Imagine that we have many independent samples X 1 , X 2 , . . . , X n from a distribution with a substantial entropy amount (∆ ≪ n) but of weak advantage ǫ = 0.99. We can use the result above to show that pseudoentropy in X 1 , X 2 , . . . , X n is roughly (1 − 0.99)(n − ∆) with good quality (see [Skob] for more details). Below we briefly compare this result with related works.
(a) Our result is far stronger than the classical result due to Barak et al. [BSW03] about the transformation. Not only we replace the factor n by ∆, but also show the existence of a hardcore in the intermediate step.

(b) This result unifies and improves our recent results [Skoa,Skob]. The corollary
H HILL s ′ ,ǫ+δ (Y ) n − ∆ was the same (and optimal) but the hardcore E was found with worse complexity s ′ = Ω(s · δ 2 /n). this set is convex. The payoff is defined as v(X, A) def = EA(Y ) − EA(X). It is easy to see 5 that we have (this paper) Proposition 4 ( Weak Statement ). ∀A ∈ A ∃X ∈ C v(X, A) 0.

Proposition 5 (Approximation Step). For every
To prove this, by the Hölder Inequality for any A, A ′ and X ∈ C we show for any p, q 1, 1 p + 1 q = 1 and the uniform distribution U . Now we argue that (a) E x←U 2 n P Y |E (x) q 1 q 2 ∆ p (by the extreme points technique).
for some A which is of complexity ℓ relative to A ′ (by standard facts on convex-approximation [DHA97]).
Setting ℓ = δ −2 (∆ + 1) (so that A ∈ A), taking X = X ′ |E which corresponds to A ′ according to Proposition 1, setting p = ∆ + 1 and putting this all together we get Proposition 5. This implies the following statement Proposition 6 ( Strong Statement ). ∃X ∈ C ∀A ∈ A ′ v(X, A) δ.
This directly implies Theorem 2 (as before, we consider A ′ closed under complements). More details can be found in Appendix D.

A (fixed) construction of a simulator for auxiliary inputs.
In [JP14] there is a theorem, which says that any short information Z about X can be efficienly simulated from X, Below we state the corrected version [Pie15].
This result is the key component in the simplified analysis of the EUROCRYPT'09 stream cipher construction. Using Theorem 3, as described in [JP14], one proves the resilience of the cipher (assuming bounded leakage in every round) and if the underlying weak PRF is (s, ǫ)-secure against two queries on random inputs. The cipher security (s ′ , ǫ ′ ) is related to (s, ǫ) by a polynomial loss in ǫ.
Our contribution. We describe a flaw in the proof and improve the corrected bound by a significant super polynomial factor. Below we briefly describe the significance of our result (a) Discovered flaws in the recent (TCC'14) analysis of the EUROCRYPT'09 stream cipher. The alternative bounds seem correct but are much weaker. In particular, we get no meaningful security with the AES used as a weak PRF in this construction 6 . This raises the problem of whether the cipher built on AES is secure or not. We would need a simulator with a loss of only O(ǫ −2 ) not ǫ −4 in complexity. (b) A simpler construction based on the min-max theorem. Based on the framework in Section 1.3 we give an alternative proof achieving the simulator complexity of O s · 2 2λ ǫ −4 ). The gain of 2 2λ over the original approach, which is a power of ǫ for recommended values of parameters [JP14], comes from the use of convex approximation techniques. Our proof is considerably simpler and quantitatively better than in [JP14] (in particular we don't need to use the min-max theorem twice depending on what is the value of the game). Also, it is much simpler than the alternative approach of Vadhan and Zheng [VZ], yet yields comparable results for small leakages (see Table 2). (c) A clear bound on the security level, in terms of the time-success ratio. We derive a clear formula which shows what fraction of the security of the original weak PRF is transformed into security of the stream cipher. This analysis shows that we are far from good and provable secure leakage-resilient stream ciphers as we lose over 5 6 of original security. For more details, see Table 2. In Table 2 we compare the strength of the simulator theorems in terms of implied security for this construction. To our knowledge, this is the first analysis of the time-success ratio for this technique. For more details we refer to Appendix E.
More on the flaws. In the claimed better bound O s · 2 3λ ǫ −2 there is a mistake on page 18 (eprint version), when the authors enforce a signed measure to be a probability measure by a mass shifting argument. The number M defined there is in fact a function of x and is hard to compute, whereas the original 6 The final bounds on the cipher security depends on the simulator complexity and are given by ǫ ′ = O √ 2 λ ǫ and s ′ = s · 2 −4λ ǫ ′4 . We can't prove then even very weak security ǫ ′ = 2 −32 having λ = 10 bits of leakage! Author Technique Simulator Complexity Implied Security [JP14] Standard Min-Max + L∞-approx. sh = s · 2 4λ ǫ −4 k ′ = k 6 − 5 6 λ [VZ] Complicated Boosting sh = s · 2 λ ǫ −2 + 2 λ ǫ −4 k ′ = k 6 − 1 3 λ this paper Standard Min-Max + Lp-approx. sh = s · 2 2λ ǫ −4 k ′ = k 6 − 1 2 λ Table 2: Security of the EUROCRYPT'09 stream cipher instantiated with a wPRF having 2 k keys and λ bits of leakage, obtained from different simulator results. Every attacker of size s succeeds with prob. at most s/2 k ′ . proof assumes that this is a constant independent of x. In the alternative bound O s · 2 3λ ǫ −2 a fixable flaw is a missing factor of 2 λ in the complexity (page 16 in the eprint version), which is because what is constructed in the proof is only a probability mass function, not yet a sampler [Pie15].
A sketch of the proof. Let A be the set of real-valued circuits of size s and let A ′ be the set of circuits of size s ′ = s · 2 −2λ ǫ 2 . Let C ′ consists of the distributions of the form X, h(X), where h is computable in size s · 2 λ ; this set is not convex. Let C be the set of all circuits of size s · 2 2λ ǫ −2 . The payoff is defined It is easy to see that we have Indeed, consider h + A which for every x outputs this value z for which A(x, z) = max A(x, ·) and h − A which for every x outputs this value z for which A(x, z) = min A(x, ·). Both are of complexity O 2 λ . Since we have E A(X, h − (X)) E A(X, Z) and E A(X, Z) E A(X, h + (X)), setting h ′ to be a distribution over we get v(h ′ , A) = 0 with some θ. In the next step we replace A ′ by conv(A ′ ).
This follows from the standard Chernoff Bound approximation argument 7 as Now we replace C ′ by conv C ′ . Here a more delicate approximation is required.

Proposition 9 ( Approximation 2). For every A and every
This follows because by the Hölder Inequality applied to p = q = 2 we obtain , 7 A can be viewed as a distribution on A ′ we simply pick ℓ independent samples {Ai}i and try to find an approximator of the form A ′ = 1 ℓ ℓ i=1 Ai. It deviates by more than ǫ at (x, z) with probability exp(−2ℓǫ 2 ). We combine this with the union bound. and by the standard results on convex approximation [DDGS97] the second factor is at most ℓ − 1 2 for some h of complexity ℓ with respect to C ′ . We put ℓ = 2 λ ǫ −2 . From the proven propositions we obtain the final result.

More Applications
For more applications we refer an interested reader to Appendix A. They include the optimal Dense Model Theorem, a better auxiliary input simulator for bounded-variance adversaries (new), and a proof that every high-conditional entropy source can be efficiently simulated (new, extending [TTV08]). Theorem 4 (Dense Model Theorem.). Let D ′ be a class of n-bit boolean functions, R be uniform over {0, 1} n , X be an n-bit random variable and let X ′ be δ-dense in X. If X and R are (D, ǫ)-indistinguishable then there exists a distribution R ′ which is δ-dense in R such that X ′ and R ′ are (D ′ , ǫ ′ )-indistinguishable, where ǫ ′ = (ǫ/δ) O(1) and D consists of all functions of the form g(D 1 , . . . , D ℓ ) where D i ∈ D ′ , ℓ = poly(1/δ, 1/ǫ) and g is some function.

A More Applications
Using our framework we can reprove the Dense Model Theorem with optimal parameters due to Zhang [Zha11]. The proof is very similar to the one in Theorem 2 so we omit the details; we note that we need the Hölder Inequality with p = 2 log(1/δ). A similar technique appears in [Skoa], though we do note use Metric pseudoentropy here.  This result is interesting in the context of recent improvements in key derivation, so called square security, where the second moment condition is widely used.

A.3 Simulating High Entropy Distribution with Auxiliary Information
From our framework we derive the following result, which is the extension of the theorem in [TTV08] into a conditional case (in the presence of auxiliary information). We stress that this result cannot be derived from the techniques used in [TTV08], because this approach will not preserve the same marginal distribution Z, when applied in the conditional setting.
Then there exists a distribution Y, Z such that (a) There is a circuit Sim of complexity O n(n + m)2 2∆ ǫ −5 and such that Here we show only how to simulate given a fixed distinguisher. The rest of the proof follows by the use of a convex approximation argument (with p = q = 2) and allows us to save a factor of 2 2∆ in the simulator complexity.
Proof (Proof of the weak statement). Let ∆ = n − k. By replacing ǫ with 2ǫ we can assume that D = j i=1 α i D i where α i = 1 − (i − 1)ǫ for i = 1, . . . , ⌈1/ǫ⌉ and D i are boolean such that 1 = i D i . Define and let M be the smallest number i such that d(i) 2 −∆ . Note that if we didn't care about computational efficiency then the best answer would be because then

D Proof of Theorem 2
To finish the proof it remains to justify the estimates and The first follows by noticing that the quantity is convex with respect to Y |E ∈ C. Thus, the maximum is attained at one of extreme points which is, in this case, a flat distribution. The second fact follows from Lemma 1.

E.1 Preliminaries
Weak pseudorandom functions, are indistinguishable from random functions, when queried on random inputs and fed with iniform secret key.
Definition 3 (Weak pseudorandom functions). A function F : {0, 1} k × {0, 1} n → {0, 1} m is an (ǫ, s, q)-secure weak PRF if its outputs on q random inputs are indistinguishable from random by any distinguisher of size s, that is where the probability is over the choice of the random X i ← {0, 1} n , the choice of a random key K ← {0, 1} k and R i ← {0, 1} m conditioned on R i = R j if X i = X j for some j < i.
Stream ciphers generate a keystream in a recursive manner. The security means that the output stream should be indistinguishable from uniform 9 .
A stream cipher SC is (ǫ, s, q)-secure if for all 1 i q, the random variable X i is (s, ǫ)-pseudorandom given X 1 , ..., X i−1 (the probability is also over the choice of the initial random key S 0 ).