Wenn es sich um eine Einwegfunktion mit unterschiedlichem Eingang handelt, handelt es sich dann immer noch um eine Einwegfunktion?

Angenommen, ist eine Einwegfunktion. Was ist mit , wobei und ? $f(x)$ $h(x)=f(x_1) \, \oplus \,f(x_2)$ $x=x_1 || x_2$ $\lvert x_1 \rvert = \lvert x_2\rvert$

$\oplus$ ist eine exklusive Disjunktion (xor)
$||$ ist Verkettung
$|u|$ ist die Länge von $u$

cryptography one-way-functions Kate Green
quelle

warum ist eine frage ob

f (x_{1}) \oplus f (x_{2})

$f(x_1) \oplus f(x_2)$ ist einseitig unter der Annahme, dass

f

$f$ ist einseitig ein Duplikat der Frage, ob

f (x) \oplus x

$f(x) \oplus x$ ist Einbahnstraße, wenn

f

$f$ ist Einbahnstraße?

Sasho Nikolov

@SashoNikolov Ich stimme dir zu: Die Hypothesen sind ziemlich unterschiedlich. In solchen Fällen stimmen Sie bitte ab, um wieder zu öffnen.

Gilles 'SO - hör auf böse zu sein'

Wie definieren Sie

h (x)

$h(x)$ wann

| x |

$|x|$ ist ungerade?

Gilles 'SO - hör auf böse zu sein'

Ist

f (x)

$f(x)$ eine Einweg-Permutation auf

{0, 1}^{| x |}

$\{0,1\}^{|x|}$ oder ist es möglich, dass die Länge von

f (x_{1})

$f(x_1)$ und

f (x_{2})

$f(x_2)$ abweichen?

Frafl

@frafl wahrscheinlich spielt es keine Rolle.

Ran G.

Antworten:

Die Funktion $h$ kann nicht mehr in eine Richtung sein.

Wir konstruieren ein Gegenbeispiel - eine bestimmte Einbahnstraße $f$ wessen $h$ ist keine Einbahnstraße mehr - auf folgende Weise. Annehmen $g$ ist eine Einwegfunktion, die die Größe beibehält und definiert $f$ bei Eingabe $w=bx_1x_2$ auf die folgende Weise,

f (b x_{1} x_{2}) = {\begin{cases} g (x_{1}) x_{2} & b = 0 \\ x_{1} g (x_{2}) & b = 1 \end{cases}

$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$ (unter der Annahme

b \in {0, 1}

$b\in\{0,1\}$ und

| x_{1} | = | x_{2} |

$|x_1|=|x_2|$ .) Das ist leicht zu sehen

f

$f$ ist auch einseitig - um es zu invertieren, müssen Sie entweder invertieren

g

$g$ in der ersten Hälfte oder invertieren

g

$g$ in der zweiten Hälfte.

Jetzt zeigen wir, wie man invertiert $h$ . Angenommen, Sie sind gegeben $h(u,v)=Z$ schreiben wir es als $h(u,v)= z_1z_2$ mit $|z_1|=|z_2|=n$ . Dann ein mögliches Vorbild von $Z$ ist

u = 0 0^{n} ⟨ g (0^{n}) \oplus z_{2} ⟩

$u=0 \,0^n \,\langle g(0^n)\oplus z_2\rangle$

v = 1 ⟨ g (0^{n}) \oplus z_{1} ⟩ 0^{n}

$v=1 \, \langle g(0^n)\oplus z_1\rangle \, 0^n$

da $f(u) = g(0^n)\, \langle g(0^n)\oplus z_2\rangle$ und $f(v) = \langle g(0^n)\oplus z_1\rangle \, g(0^n)$ somit gibt ihr XOR genau $z_1\,z_2$ wie erforderlich.

Ran G.
quelle

Könnten Sie weitere Details zum Invertieren hinzufügen?

g

$g$ ? Einige gegeben

x

$x$ verketten Sie einen Zufall

x_{1}

$x_1$ oder

x_{2}

$x_2$ und dann berechnen

f^{- 1} (x x_{2})

$f^{-1}(xx_2)$ und / oder

f^{- 1} (x_{1} x)

$f^{-1}(x_1x)$ . Aber das Ergebnis könnte nachgeben

g^{- 1} (x_{1})

$g^{-1}(x_1)$ und

g^{- 1} (x_{2})

$g^{-1}(x_2)$ . Sie müssen sicherstellen, dass dies in vielen Fällen nicht der Fall ist. Angesichts der Tatsache, dass Sie zwei positive Beispiele benötigen, um ein negatives zu konstruieren, sollte dies möglich sein, aber es ist (für mich) nicht so offensichtlich, wie Sie behaupten.

Frafl

@frafl fragst du warum

f

$f$ ist ein Weg? Angenommen, Sie haben

A

$A$ das invertiert es und verwendet es, um zu invertieren

g (x)

$g(x)$ durch Abfragen

A

$A$ auf

g (x) g (x)

$g(x)g(x)$ .

Ran G.

@RanG: Wie offensichtlich

f^{- 1} (x x)

$f^{-1}(xx)$ . Vielen Dank!

Frafl