Es ist bekannt, dass die Existenz von Einwegfunktionen für einen Großteil der Kryptographie (digitale Signaturen, Pseudozufallsgeneratoren, Verschlüsselung mit privatem Schlüssel usw.) notwendig und ausreichend ist. Meine Frage ist: Was sind die komplexitätstheoretischen Konsequenzen der Existenz von Einwegfunktionen? OWFs implizieren beispielsweise, dass , und . Gibt es andere bekannte Konsequenzen? Bedeuten OWFs insbesondere, dass die Polynomhierarchie unendlich ist?
Ich hoffe, die Beziehung zwischen der Worst-Case- und der Average-Case-Härte besser verstehen zu können. Ich bin auch daran interessiert, dass Ergebnisse in die andere Richtung gehen (dh komplexitätstheoretische Ergebnisse, die OWFs implizieren würden).
cc.complexity-theory
reference-request
complexity-classes
cr.crypto-security
one-way-function
Thomas
quelle
quelle
Antworten:
Dies ist eine späte Antwort.
Um zu korrigieren, was Sie geschrieben haben: Die kryptografische Pseudozufälligkeit (die von OWFs erhalten wurde) reicht nicht aus, um "natürlich definierte" rechnerische Komplexitätsklassen zu derandomisieren. In einem alten Artikel (Anfang der 80er Jahre) zeigt Andrew Yao eine subexponentielle zeitliche Derandomisierung für RP usw. unter Verwendung dieser Objekte (übrigens ist dies unmittelbar), aber es ist keine stärkere Derandomisierung bekannt. Beachten Sie, dass kryptografische PRGs in Bezug auf die Narrleistung stärker sind als das, was Sie für die Derandomisierung benötigen, aber gleichzeitig in Bezug auf ihre Ausdehnung schwächer sind als ihre typischen komplexitätstheoretischen Analoga (dies folgt in der Reihenfolge der Quantifizierung in der Definition der PRGs).
Wie Sasho Nikolov erwähnte, gibt es viele Beispiele für PAC-Lernen. Schauen Sie sich einen sehr frühen Artikel von Kearns und Valiant über die Unmöglichkeit des Lernens von Formeln und Automaten an (folgen Sie in Google Scholar den Referenzen von dort). Auch die Komplexität von Beweisen durch Interpolation hat Konsequenzen - schauen Sie sich auch die frühen Arbeiten von Jan Krajicek und Pavel Pudlak an. Ich bin mir jedoch nicht sicher, ob Sie dies als komplexitätstheoretische Implikationen betrachten (aber ich tue es).
- Periklis
quelle
Die Ganzzahlfaktorisierung wird allgemein als der beste Kandidat für Einwegfunktionen angesehen und befindet sich in TFNP. Kollabiert die Polynomhierarchie aus der Zusammenfassung dieses Dokuments, wenn Funktionen invertierbar sind? Es ergibt ein relativiertes negatives Ergebnis, indem ein Orakel konstruiert wird, unter dem TFNP-Funktionen effizient berechenbar sind, die Polynom-Zeit-Hierarchie jedoch unendlich ist. Das Ergebnis ist jedoch nicht genau das, wonach Sie suchen.
quelle