Fragen zu einfach zu berechnenden, aber schwer zu invertierenden Funktionen.
Ich habe in mehreren Artikeln gelesen, dass die Existenz von Einwegfunktionen weithin angenommen wird. Kann jemand Aufschluss darüber geben, warum dies der Fall ist? Welche Argumente haben wir für die Existenz von
Ist es möglich, einen CNF in einen anderen CNF Ψ ( C ) umzuwandeln, so dassCC\mathcal CΨ(C)Ψ(C)\Psi(\mathcal C) Die Funktion kann in Polynomzeit aus einem geheimen Zufallsparameter r berechnet werden .ΨΨ\Psirrr hat genau danneine Lösung,wenn C eine Lösung hat.Ψ(C)Ψ(C)\Psi(\mathcal C)CC\mathcal C...
Eine Funktion ist einseitig, wenn durch einen polynomiellen Zeitalgorithmus berechnet werden kann, jedoch für jeden randomisierten polynomiellen Zeitalgorithmus , f Af: { 0 , 1 }∗→ { 0 , 1 }∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^*fffEINAA Pr [ f( A ( f( x ) ) ) = f( x ) ] < 1 / p ( n...
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...
Es gibt einen alten Trick, um einen Algorithmus aufzuschreiben, der, wenn P = NP, SAT in Polynomialzeit löst. Im Wesentlichen listet man alle Polynom-Zeitmaschinen und Multi-Tasks darüber auf. Gibt es einen analogen Trick für Einwegfunktionen (oder auch Einweg-Falltürfunktionen)? Das heißt, können...
Sei π:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon \{0,1\}^* \to \{0,1\}^* eine Permutation. Beachten Sie, dass ππ\pi auf eine unendliche Domäne einwirkt, seine Beschreibung jedoch endlich sein kann. Mit Beschreibung meine ich ein Programm, das die Funktionalität von beschreibt ππ\pi. (Wie bei der...
Meine Frage betrifft die Gleichwertigkeit der Sicherheit verschiedener Kandidaten-Einwegfunktionen, die auf der Grundlage der Härte des Factorings konstruiert werden können. Angenommen, das Problem von FAKTORIERUNG: [Wenn für zufällige Primzahlen , finde , ]N=PQN=PQN = PQP,Q<2nP,Q<2nP, Q <...
Wenn OWFs existieren, ist eine statistisch bindende Bitbindung möglich. [1] Ist bekannt, dass bei Vorhandensein von OWFs eine perfekt bindende Bitbindung möglich ist? Wenn nein, gibt es eine bekannte Black-Box-Trennung zwischen ihnen? [1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem...
Kurz gesagt : Können wir unter der Annahme , dass Einwegpermutationen existieren, eine konstruieren, die keine Falltür hat? Mehr Info: Eine Einweg-Permutation ist eine Permutation die einfach zu berechnen, aber schwer zu invertieren ist ( eine formellere Definition finden Sie im...
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...
Gibt es eine Trap-Door-ähnliche Funktion, deren Codierungskomplexität die Polynomzeit und deren invertierende Komplexität (ohne geheimen Schlüssel) auch eine Polynomfunktion in der Eingabelänge mit (sagen wir, und ist bedingungslos nachweisbar durch )? Was bedeuten solche Funktionen, wenn...
Gibt es ein bedingtes Unmöglichkeitsergebnis oder ist die Frage völlig