Abstract
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 full version of this paper is available online at http://arxiv.org/abs/1506.06633.
M. Skórski—This work was partly supported by the WELCOME/2010-4/2 grant founded within the framework of the EU Innovative Economy Operational Programme.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We consider \(\{-1,1\}\) outputs for technical convenience. Equivalently we could state the problem for \(\{0,1\}\).
- 2.
We can think of measures M such that \(M(\cdot )\leqslant \mathbf {P}_V(\cdot )\) and \(\sum _x M(x) \geqslant \epsilon \). Every \(X\in \mathcal {C}\) can be written as \(\mathbf {P}_X(\cdot ) = M(\cdot )/\sum _{x}M(x)\) for one of these measures M.
- 3.
- 4.
That is, \(\textsc {A}\) is a convex combination of \(\ell \) members of \(\textsc {A}'\).
- 5.
This is trivial for boolean \(\textsc {A}\) and somewhat more tricky for real-valued \(\textsc {A}\). A short proof is given implicitly in [5].
- 6.
The final bounds on the cipher security depends on the simulator complexity and are given by \(\epsilon ' = O\left( \sqrt{2^{\lambda }\epsilon }\right) \) and \(s'=s\cdot 2^{-4\lambda }\epsilon '^{4}\). We can’t prove then even very weak security \(\epsilon ' = 2^{-32}\) having \(\lambda =10\) bits of leakage!.
- 7.
A can be viewed as a distribution on \(\mathcal {A}'\) we simply pick \(\ell \) independent samples \(\{\textsc {A}_i\}_i\) and try to find an approximator of the form \(\textsc {A}'=\frac{1}{\ell }\sum _{i=1}^{\ell } \textsc {A}_{i} \). It deviates by more than \(\epsilon \) at (x, z) with probability \(\exp (-2\ell \epsilon ^2)\). We combine this with the union bound.
References
Barak, B., Shaltiel, R., Wigderson, A.: Computational analogues of entropy. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 200–215. Springer, Heidelberg (2003)
Chung, K.-M., Kalai, Y.T., Liu, F.-H., Raz, R.: Memory delegation. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 151–168. Springer, Heidelberg (2011)
Docampo, D., Hush, D.R., Abdallah, C.T.: Constructive function approximation: theory and practice. In: Intelligent Methods in Signal Processing and Communications. Birkhauser Boston Inc. (1997)
Donahue, M.J., Darken, C., Gurvits, L., Sontag, E.: Rates of convex approximation in non-hilbert spaces. Constructive Approximation 13, 187–220 (1997)
Fuller, B., O’Neill, A., Reyzin, L.: A unified approach to deterministic encryption (...). TCC 2012 (2012)
Hastad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 1364–1396 (1999)
Holenstein, T.: Key agreement from weak bit agreement. In: STOC 2005 (2005)
Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: FOCS 36 (1995)
Jetchev, D., Pietrzak, K.: How to fake auxiliary input. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 566–590. Springer, Heidelberg (2014)
Klivans, A.R., Servedio, R.A.: Boosting and hard-core set construction. Mach. Learn. 51(3), 217–238 (2003)
Lu, C.-J., Tsai, S.-C., Wu, H.-L.: On the complexity of hard-core set constructions. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 183–194. Springer, Heidelberg (2007)
Neumann, J.: Zur theorie der gesellschaftsspiele. Math. Ann. 100, 295–320 (1928)
Pietrzak, K.: Private communication, may (2015)
Reingold, O., Trevisan, L., Tulsiani, M., Vadhan, S.: Dense subsets of pseudorandom sets. FOCS 2008 (2008)
Skorski, M.: Metric pseudoentropy: Characterizations, transformations and applications. In: ICITS (2015)
Skorski, M.: Nonuniform indistinguishability and unpredictability hardcore lemmas: new proofs and applications to pseudoentropy. In: ICITS (2015)
Trevisan, L., Tulsiani, M., Vadhan, S.: Regularity, boosting, and efficiently simulating every high-entropy distribution. CCC 2009 (2008)
Vadhan, S., Zheng, C.J.: A uniform min-max theorem with applications in cryptography. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 93–110. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Skórski, M. (2015). A New Approximate Min-Max Theorem with Applications in Cryptography. In: Elbassioni, K., Makino, K. (eds) Algorithms and Computation. ISAAC 2015. Lecture Notes in Computer Science(), vol 9472. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48971-0_55
Download citation
DOI: https://doi.org/10.1007/978-3-662-48971-0_55
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48970-3
Online ISBN: 978-3-662-48971-0
eBook Packages: Computer ScienceComputer Science (R0)