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:
Introduction Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

3. Randomized Encoding of Functions

verfasst von : Benny Applebaum

Erschienen in: Cryptography in Constant Parallel Time

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

In this chapter we formally introduce our notion of randomized encoding which will be used as a central tool in subsequent chapters. In Sect. 3.1 we introduce several variants of randomized encoding and in Sect. 3.2 we prove some of their useful properties. Finally, in Sect. 3.3 we discuss other aspects and limitations of randomized encoding such as the necessity of randomness, the expressive power of encoding in NC 0, and the lowest output locality which is sufficient to encode all functions.

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 Preliminaries and Definitions
Nächstes Kapitel Cryptography in NC 0
Fußnoten
1
We restrict the decoder to be deterministic for simplicity. This restriction does not compromise generality, in the sense that one can transform a randomized decoder to a deterministic one by incorporating the coins of the former in the encoding itself.
 
2
This can be generally explained by viewing each slice of the padded function \(\hat{f}'\) (i.e., its restriction to inputs of some fixed length) as a perfect randomized encoding of a corresponding slice of \(\hat{f}\).
 
3
We also note that if CREN≠SREN then there exist two polynomial-time constructible ensembles which are computationally indistinguishable but not statistically close. In [67] it is shown that such ensembles implies the existence of infinitely often OWF, i.e., a polynomial-time computable function which is hard to invert for infinitely many input lengths (see [70, Definition 4.5.4] for a formal definition).
 
4
The encoding itself should still be computable in (polynomial-time) uniform NC 0.
 
5
In fact, this is a specific instance of the statistical difference problem which was shown to be complete for the class SZK [129].
 
Literatur
2.
Aiello, W., Hastad, J.: Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci. 42, 327–345 (1991) CrossRefMATHMathSciNet
9.
Applebaum, B.: Randomly encoding functions: a new cryptographic paradigm (invited talk). In: ICITS, pp. 25–31 (2011)
25.
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: Proc. of 22nd STOC, pp. 503–513 (1990)
40.
Boppana, R.B., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25, 127–132 (1987) CrossRefMATH
63.
Fortnow, L.: The complexity of perfect zero-knowledge (extended abstract). In: Proc. of 19th STOC, pp. 204–209 (1987)
67.
70.
Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) CrossRef
81.
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989). Preliminary version in STOC 1985 CrossRefMATHMathSciNet
92.
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: Proc. of 41st FOCS, pp. 294–304 (2000)
129.
Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. J. ACM 50(2), 196–249 (2003). Preliminary version in FOCS 1997 MathSciNet
146.
Metadaten
Titel
Randomized Encoding of Functions
verfasst von
Benny Applebaum
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
Buch
Cryptography in Constant Parallel Time

Print ISBN: 978-3-642-17366-0

Electronic ISBN: 978-3-642-17367-7

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-642-17367-7_3