Was ist darüber bekannt, dass die Einwegfunktion auf der Annahme basiert ?

Wir können nicht hoffen, ein allgemeines Unmöglichkeitsergebnis zu beweisen, denn wenn Einwegfunktionen existieren (und wir glauben, dass sie existieren), folgt insbesondere, dass die Aussage "Wenn dann Einwegfunktionen existieren" wahr ist. $P \ne NP$

Wir können jedoch beweisen, dass bestimmte Beweisverfahren zu schwach sind, um diese Aussage zu beweisen. Insbesondere das folgende Papier von Akavia, Goldreich, Goldwasser und Moshkovitz beweist, dass diese Aussage nicht durch bestimmte Black-Box-Reduktionen (unter der Bedingung plausibler Annahmen) bewiesen werden kann:

http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html

Oder Meir
quelle

Was ist, wenn P! = NP und Einwegfunktionen nicht existieren, wie dies bei NP = coNP der Fall sein könnte?

Philip White

@PhilipWhite wir wären dann irgendwo zwischen Heuristica und Pessiland, denke ich: cseweb.ucsd.edu/~russell/average.ps

Sasho Nikolov

Wenn Sie die kryptografische Art der Einwegfunktion meinen (dh der Durchschnittsfall ist schwer zu invertieren), dann ist die Antwort von Or Meir großartig. Für die etwas einfachere Vorstellung der Worst-Case -Einwegfunktion - das heißt einer injektiven Funktion , die in der Polynomzeit berechenbar ist, für die es jedoch keinen deterministischen Polynomzeitalgorithmus so dass für alle im Bild von und sonst - es gibt eine genauere Antwort. Einwegfunktionen im schlimmsten Fall existieren nämlich genau dann, wenn . $f$ $g$ $f(g(y)) = y$ $y$ $f$ $g(y)=0$ $\mathsf{P} \neq \mathsf{UP}$

Für Einwegfunktionen im schlimmsten Fall Ihre Frage im Wesentlichen auf die Beziehung zwischen und . Diese Beziehung ist im Wesentlichen weit offen und es gibt Orakel in beide Richtungen. Einige Beziehungen für verwandte Fragen sind bekannt - nämlich Valiant-Vazirani ( ) und Hemaspaandra-Naik-Ogihara-Selman ( impliziert, dass zusammenbricht) - aber mir ist keine direkte, bedingungslose Beziehung bekannt, die sich mit und . $\mathsf{UP}$ $\mathsf{NP}$ $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$ $\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$ $\mathsf{PH}$ $\mathsf{NP}$ $\mathsf{UP}$

Joshua Grochow
quelle

Das ist eine ... seltsame Definition für Worst-Case-Onewayness. (Insbesondere impliziert dies Surjektivität.) Ich hätte erwartet, dass es die kryptografische Definition genauer .

$\:$

$\hspace{.38 in}$

$\hspace{1.63 in}$

@ RickyDemer: Hoppla, ich wollte keine Surjektivität implizieren. Fest.

Joshua Grochow

Wie ist beteiligt? (Betrachten Sie die Funktion, die durch das Senden von Paaren [SAT_instance, befriedigende_zuweisung] an ihre codierte SAT_instance und alles andere an etwas gegeben wird, das keine SAT-Instanz ist.)

UP

$\operatorname{UP}$

$\:$

$\;\;\;\;$

Nach einem Blick auf sciencedirect.com/science/article/pii/0304397585900854 scheint die Definition für eine Einwegfunktion im ungünstigsten Fall zu sein: 1)

f

$f$ ist eine Injektion, 2)

x

$x$ und

f (x)

$f(x)$ sind in ihrer Größe polynomisch verwandt, 3 ) ist polytime-berechenbar, 4) ist nicht polytime-berechenbar für alle im Bereich.

f (x)

$f(x)$

f^{- 1} (y)

$f^{-1}(y)$

y

$y$

Sasho Nikolov

@ RickyDemer: Wenn injektiv ist, ist der Bereich von - dh - eine Sprache in .

f

$f$

f

$f$

{x : (\exists y) [f (y) = x]}

$\{ x : (\exists y)[f(y)=x]\}$

U P

$\mathsf{UP}$

Joshua Grochow

Was ist darüber bekannt, dass die Einwegfunktion auf der Annahme basiert ?

Antworten: