Längenerhaltende Einwegfunktionen

Leider ist mein Hintergrund in Bezug auf die Komplexität der Berechnungen immer noch schwach, aber ich arbeite daran.

Soweit ich weiß, ist die Frage der Existenz von Einwegfunktionen auf diesem Gebiet sehr wichtig.

Angenommen, es gibt Einwegfunktionen. Wie kann gezeigt werden, dass es Einwegfunktionen gibt, die die Länge erhalten?

Wlog lassen $g$ Da es sich um eine starke Einwegfunktion handelt, werden wir nun eine längenerhaltende Oneway-Funktion erstellen $f$.

Schon seit $g$ Ist PPT durch Annahme berechenbar, gibt es ein Polynom $p$ st $|f(x)| \le p(|x|)$ für alle $x$ Definieren

$$g'(x) = g(x)||10^{p(|x|) - |g(x)|}$$ Diese Funktion hat immer $|g'(x)| = p(|x|)$. und ist trivial stark ein Weg.

Wir müssen jetzt zwingen $|x| = |f(x)|$.

Dies können wir tun, indem wir nehmen $p(|x|)$ Bits als Eingabe und nur nehmen $|x|$ davon berücksichtigt, dh

$f(x||y) = g'(x)$ zum $|y| = p(|x|) - |x| + 1$.

Starke Einbahnstraße von $f$ folgt aus der starken Einbahnstraße von $g'$.

Hätten $f$ nicht stark ein Weg gewesen, konnten wir einen PPT-Gegner von abfragen $f$ zum $z = f(y)$ erhalten $x = x_1 || \ldots || x_n$ zurück und versuche es für jeden $m \in [n]$ ob $g'(x_1||\ldots||x_m) = z$ und schließlich ein Vorbild von finden $z$ unter $g'$ in Polynomzeit mit nicht zu vernachlässigender Wahrscheinlichkeit. Widerspruch.

Sehen Sie hier den Original Beweis .