Haben "One Way Functions" Anwendungen außerhalb von Crypto?

16

Eine Funktion ist einseitig, wenn durch einen polynomiellen Zeitalgorithmus berechnet werden kann, jedoch für jeden randomisierten polynomiellen Zeitalgorithmus , $f \colon \{0, 1\}^* \to \{0, 1\}^*$ $f$ $A$

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

für jedes Polynom und ausreichend großes unter der Annahme, dass einheitlich aus . Die Wahrscheinlichkeit wird über die Wahl von und die Zufälligkeit von . $p(n)$ $n$ $x$ $\{ 0, 1 \}^n$ $x$ $A$

Also ... haben "One Way Functions" Anwendungen außerhalb der Kryptographie? Wenn ja, welche?

cc.complexity-theory cr.crypto-security one-way-function Tarek Radwan
quelle

1

Ich habe Formeln in LaTeX-Form korrigiert, aber es scheint einen Fehler in MathJax zu geben, da die Vorschau der Gleichungen korrekt ist, aber der Fehler `Misplaced \` angezeigt wird. Ich denke, es wird bald korrigiert ...

MS Dousti

1

Für mich sieht das eher nach einem Fehler in SE aus. Aus irgendeinem Grund scheint es ein double- \ nicht als eine Escape-Sequenz zu erkennen, die ein single \ ausgeben sollte, das dann von MathJax verarbeitet wird.

Jukka Suomela

2

In der Post ist es , aber es benötigt eine zusätzliche schließende Klammer ")".

P r [f (A (f (x), 1^{n}) = x] < 1 / p (n)

$Pr[f(A(f(x),1^n)=x]<1/p(n)$

Oleksandr Bondarenko

2

@Sadeq und Jukka: Dies könnte zu einem kürzlich Fehler behoben in SE in Beziehung gesetzt werden: meta.math.stackexchange.com/questions/1115/...

Tsuyoshi Ito

@ Tsuyoshi: Danke für den informativen Kommentar!

MS Dousti

23

Einbahnstraßenfunktionen zeigen sich entscheidend im Ergebnis der natürlichen Beweise von Razborov-Rudich. Ich würde Schaltungsuntergrenzen nicht als Teil der "Kryptographie" betrachten, daher entspricht dies möglicherweise Ihren Kriterien.

mikero
quelle

11

Einwegfunktionen wurden auch in einigen Diskussionen über die Berman-Hartmanis-Isomorphismus-Vermutung erwähnt . Joseph und Young vermuteten, dass die Isomorphismus-Vermutung fehlschlägt, wenn Einwegfunktionen existieren (Einweg gegen deterministische Gegner, nicht gegen probabilistische, aber hoffentlich nahe genug für die Zwecke dieser Frage). John Rogers gab eine relativierte Welt an, in der die Joseph-Young-Vermutung fehlschlug (das heißt, in der Einwegfunktionen existieren, aber die Isomorphismus-Vermutung gilt). Aber meines Wissens ist die JY-Vermutung immer noch einer der wichtigsten technischen Beweise dafür, dass die Leute glauben, die Isomorphismus-Vermutung sei falsch (wenn sie das glauben).

Das Wesen der Idee von Joseph und Young ist , dass , wenn eine Einwegfunktion, dann ist - vollständig , aber „sollte nicht“ isomorph zu SAT sein. $f$ $f(SAT)$ $NP$

Joshua Grochow
quelle

8

Ja, eine Hash-Tabelle oder eine Hash-Karte erfordert eine Einwegfunktion. Auch die Duplikaterkennung (siehe dies und das ) kann mithilfe von Einwegfunktionen sehr effizient durchgeführt werden. In beiden Fällen sind "gute" (mit geringen Kollisionswahrscheinlichkeiten) Einwegfunktionen erforderlich, während die kryptografische Stärke normalerweise nicht erforderlich ist .

scharfer Zahn
quelle

Ja, Hash-Funktionen werden häufig für Hash-Tabellen verwendet.

Gamlor

2

Ihre Antwort ist nicht korrekt. Was für die Duplikaterkennung erforderlich ist, ist die Kollisionsbeständigkeit, die nicht gleichbedeutend mit der Einbahnstraße ist. Eine sorgfältige Definition der Einbahnstraße finden Sie in der Definition in der ursprünglichen Frage. Manchmal wird der Ausdruck "One-Way-Hash" lose als Synonym für kryptografische Hash-Funktion verwendet, was jedoch sehr irreführend ist, da in vielen Anwendungen nicht die "One-Way" -Eigenschaft wichtig ist, sondern die Kollisionsbeständigkeit ( B. bei doppelter Erkennung) oder Verhalten wie ein zufälliges Orakel (wie beim Hashing).

DW

6

Es gibt viele "kryptografische Härte" -Ergebnisse (nur Google diese Phrase) für Lernprobleme. Dies sind Härteergebnisse unter der Annahme, dass Einwegfunktionen existieren.

Dana Moshkovitz
quelle

4

Können Sie mir eine genaue Definition der "kryptografischen Härte" geben?

Tarek Radwan

1

Die Ergebnisse der Standardhärte gehen davon aus, dass P nicht gleich NP ist. Ist dies der Fall, nimmt das Problem Superpolynomzeit in Anspruch. Die Ergebnisse der "kryptografischen Härte" setzen etwas Stärkeres voraus: dass Einwegfunktionen existieren. Diese Annahme impliziert (und ist stärker als) die durchschnittliche Fallhärte einiger Probleme.

Dana Moshkovitz

5

Einwegfunktionen haben eine Anwendung in Kolmogorov-Komplexität:

$x$ $y$

$K^q(x, y) = K^q(x) + K^q(y|x) + O(\log n)$ $q$

Wenn Einwegfunktionen existieren, ist die polynomzeitbegrenzte Symmetrie der Informationskonjektion falsch.

L. Longpre und S. Mocas. Symmetrie von Informationen und Einwegfunktionen. Information Processing Letters, 46 (2): 95 {100, 1993

L. Longpre und O. Watanabe. Zur Symmetrie der Information und zur Umkehrbarkeit der Polynomzeit. Information and Computation, 121 (1): 14 {22, 1995

Mohammad Al-Turkistany
quelle

Haben "One Way Functions" Anwendungen außerhalb von Crypto?

Antworten: