Einwegfunktionen in Bezug auf verschiedene Ressourcengrenzen

13

Informell werden Einwegfunktionen in Bezug auf PTIME-Algorithmen definiert. Sie sind in der Polynomzeit berechenbar, aber in der Durchschnittspolynomzeit nicht invertierbar. Die Existenz solcher Funktionen ist ein wichtiges offenes Problem in der theoretischen Informatik.

Ich interessiere mich für Einwegfunktionen (nicht unbedingt für kryptografische Anwendungen), die in Bezug auf verschiedene Ressourcengrenzen definiert sind. Solche Ressourcengrenzen können LOGSPACE oder beschränkter Nichtdeterminismus sein.

Gibt es ein (natürliches) Kandidatenproblem, das in Bezug auf LOGSPACE-Algorithmen einseitig ist? Gibt es ein (natürliches) Kandidatenproblem, das in Bezug auf nichtdeterministische lineare Zeitalgorithmen ( ) einseitig ist ?NTIME (n)

Mir geht es gut mit der Worst-Case-Härte der Invertierbarkeit in Bezug auf die oben genannten Ressourcengrenzen.

Mohammad Al-Turkistany
quelle
Haben Sie eprint.iacr.org/2013/001.pdf gesehen ? Das Thema dieses Artikels mag für Sie relevant sein oder nicht, aber die Techniken in dem Artikel (oder vielleicht sogar die Zitate) können zu etwas Nützlichem führen.
Daniel Apon
Die Zusammenfassung hilft nicht, aber danke für Ihre Hilfe.
Mohammad Al-Turkistany
Na ja - ich hoffe die neue Antwort tut es trotzdem. :)
Daniel Apon
Ja, das tut es :)
Mohammad Al-Turkistany

Antworten:

11

In Bezug auf den Protokollbereich: Mehrere mögliche Einwegfunktionen sind im Protokollbereich oder darunter berechenbar (und angeblich auch gegen zeitlich versetzte Gegner sicher). Sie können mehrere Hinweise finden, zum Beispiel in der Kryptographie in NC 0-0 Papier.

Zwei spezifische Beispiele sind:

Ganzzahlmultiplikation (es gibt einige Feinheiten für Standard-OWF, aber wenn Sie sich nur für den schlimmsten Fall interessieren, ist dies ausreichend)

Die Impagliazzo-Naor Kandidaten basierend auf Subset-sum: .f(ein1,...,einn,S): =(ein1,...,einn,ichSeinichmod2n)

Manu
quelle
Danke Emanuele. Dies beantwortet den Fall Logspace. Könnten Sie der Vollständigkeit halber einige dieser Funktionen in Ihrer Antwort auflisten?
Mohammad Al-Turkistany
Ich habe zwei Beispiele hinzugefügt.
Manu
Vielen Dank Emanuele. Gibt es eine Einsicht, die die Härte der Invertierung dieser Funktionen (durch LOGSPACE-Algorithmen) erklärt?
Mohammad Al-Turkistany