Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

A New Approximate Min-Max Theorem with Applications in Cryptography

verfasst von : Maciej Skórski

Erschienen in: Algorithms and Computation

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
Nächstes Kapitel Give Me Another One!
Fußnoten
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
Following related works [5, 14] we use circuits with real outputs for technical reasons.
 
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.
 
Literatur
1.
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)
2.
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) CrossRef
3.
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)
4.
Donahue, M.J., Darken, C., Gurvits, L., Sontag, E.: Rates of convex approximation in non-hilbert spaces. Constructive Approximation 13, 187–220 (1997)MathSciNetCrossRefMATH
5.
Fuller, B., O’Neill, A., Reyzin, L.: A unified approach to deterministic encryption (...). TCC 2012 (2012)
6.
Hastad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 1364–1396 (1999)MathSciNetCrossRefMATH
7.
Holenstein, T.: Key agreement from weak bit agreement. In: STOC 2005 (2005)
8.
Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: FOCS 36 (1995)
9.
Jetchev, D., Pietrzak, K.: How to fake auxiliary input. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 566–590. Springer, Heidelberg (2014) CrossRef
10.
Klivans, A.R., Servedio, R.A.: Boosting and hard-core set construction. Mach. Learn. 51(3), 217–238 (2003)CrossRefMATH
11.
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) CrossRef
12.
13.
Pietrzak, K.: Private communication, may (2015)
14.
Reingold, O., Trevisan, L., Tulsiani, M., Vadhan, S.: Dense subsets of pseudorandom sets. FOCS 2008 (2008)
15.
Skorski, M.: Metric pseudoentropy: Characterizations, transformations and applications. In: ICITS (2015)
16.
Skorski, M.: Nonuniform indistinguishability and unpredictability hardcore lemmas: new proofs and applications to pseudoentropy. In: ICITS (2015)
17.
Trevisan, L., Tulsiani, M., Vadhan, S.: Regularity, boosting, and efficiently simulating every high-entropy distribution. CCC 2009 (2008)
18.
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) CrossRef
Metadaten
Titel
A New Approximate Min-Max Theorem with Applications in Cryptography
verfasst von
Maciej Skórski
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Algorithms and Computation

Print ISBN: 978-3-662-48970-3

Electronic ISBN: 978-3-662-48971-0

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48971-0_55