@conference {634150,
title = {A uniform min-max theorem with applications in cryptography},
booktitle = {Ran Canetti and Juan Garay, editors, Advances in Cryptology{\textemdash}CRYPTO {\textquoteleft}13, Lecture Notes on Computer Science},
volume = {8042},
year = {2013},
pages = {93-110},
publisher = {Springer Verlag, Lecture Notes in Computer Science},
organization = {Springer Verlag, Lecture Notes in Computer Science},
abstract = {
Version History:\
Full version\ published on\ ECCC2013\ and\ IACR ePrint\ 2013.
We present a new, more constructive proof of von Neumann{\textquoteright}s Min-Max Theorem for two-player zero-sum game {\textemdash} specifically, an algorithm that builds a near-optimal mixed strategy for the second player from several best-responses of the second player to mixed strategies of the first player. The algorithm extends previous work of Freund and Schapire (Games and Economic Behavior {\textquoteright}99) with the advantage that the algorithm runs in poly\((n)\) time even when a pure strategy for the first player is a distribution chosen from a set of distributions over\ \(\{0,1\}^n\). This extension enables a number of additional applications in cryptography and complexity theory, often yielding uniform security versions of results that were previously only proved for nonuniform security (due to use of the non-constructive Min-Max Theorem).
We describe several applications, including a more modular and improved uniform version of Impagliazzo{\textquoteright}s Hardcore Theorem (FOCS {\textquoteright}95), showing impossibility of constructing succinct non-interactive arguments (SNARGs) via black-box reductions under uniform hardness assumptions (using techniques from Gentry and Wichs (STOC {\textquoteright}11) for the nonuniform setting), and efficiently simulating high entropy distributions within any sufficiently nice convex set (extending a result of Trevisan, Tulsiani and Vadhan (CCC {\textquoteright}09)).
},
url = {https://link.springer.com/chapter/10.1007/978-3-642-40041-4_6},
author = {Salil Vadhan and Colin Jia Zheng}
}