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

6. One-Way Functions with Optimal Output Locality

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 Chap. 4 it was shown that, under relatively mild assumptions, there exist one-way functions (OWFs) in \(\mathbf {NC}^{0}_{4}\). This result is not far from optimal as there is no OWF in \(\mathbf {NC}^{0}_{2}\). In this chapter we partially close this gap by providing an evidence for the existence of OWF in \(\mathbf {NC}^{0}_{3}\). This is done in two steps: (1) we describe a new variant of randomized encoding that allows us to obtain a OWF in \(\mathbf {NC}^{0}_{3}\) from a “robust” OWF which remains hard to invert even when some information on the preimage x is leaked; (2) we show how to construct a robust OWF assuming that a random function of (arbitrarily large) constant locality is one-way. (A similar assumption was previously made by Goldreich in Electron. Colloq. Comput. Complex. 7:090, 2000.)

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 Computationally Private Randomizing Polynomials and Their Applications
Nächstes Kapitel On Pseudorandom Generators with Linear Stretch in NC 0
Fußnoten
1
More precisely, each input is connected to an output with probability d/n and so the expected degree is d.
 
2
Sample a matrix from ℳ a,b,p conditioned on the event that none of the columns is an all-zero column (a task which can be achieved efficiently by rejecting and resampling zero columns), and fail it if the resulting matrix has a row of weight larger than logn. To see that rejection happens with negligible probability, observe that for a fixed row, each column contributes 1 with probability p/(1−p) a =Θ(1/n), independently of the other columns, and therefore, by a Chernoff bound, the weight exceeds logn with negligible probability.
 
3
Another line of work studied the pseudorandomness of the collection. See Sect. 7.​6.
 
Literatur
6.
Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reason. 35(1–3), 51–72 (2005) MATHMathSciNet
27.
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. of 20th STOC, pp. 1–10 (1988)
38.
Bogdanov, A., Qiao, Y.: On the security of Goldreich’s one-way function. In: Proc. of 13th RANDOM, pp. 392–405 (2009)
39.
Bogdanov, A., Rosen, A.: Input locality and hardness amplification. In: Proc. of 8th TCC, pp. 1–18 (2011)
47.
Cook, J., Etesami, O., Miller, R., Trevisan, L.: Goldreich’s one-way function candidate and myopic backtracking algorithms. In: Proc. of 6th TCC, pp. 521–538 (2009). Full version in ECCC TR12-175
55.
Dinur, I., Finucane, H.: Cryptography with locality two. Unpublished manuscript (2011)
69.
Goldreich, O.: Candidate one-way functions based on expander graphs. Electron. Colloq. Comput. Complex. 7, 090 (2000)
70.
Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) CrossRef
90.
Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. In: Proc. of 30th FOCS, pp. 230–235 (1989)
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)
120.
144.
Yao, A.C.: Theory and application of trapdoor functions. In: Proc. of 23rd FOCS, pp. 80–91 (1982)
Metadaten
Titel
One-Way Functions with Optimal Output Locality
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_6