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

7

Angenommen, ist eine Einwegfunktion. Was ist mit , wobei und ?f(x)h(x)=f(x1)f(x2)x=x1||x2|x1|=|x2|

  • ist eine exklusive Disjunktion (xor)
  • ||ist Verkettung
  • |u|ist die Länge vonu
Kate Green
quelle
warum ist eine frage ob f(x1)f(x2) ist einseitig unter der Annahme, dass f ist einseitig ein Duplikat der Frage, ob f(x)x ist Einbahnstraße, wenn fist 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) wann |x|ist ungerade?
Gilles 'SO - hör auf böse zu sein'
Ist f(x) eine Einweg-Permutation auf {0,1}|x| oder ist es möglich, dass die Länge von f(x1) und f(x2)abweichen?
Frafl
@frafl wahrscheinlich spielt es keine Rolle.
Ran G.

Antworten:

9

Die Funktion h kann nicht mehr in eine Richtung sein.

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

f(bx1x2)={g(x1)x2b=0x1g(x2)b=1
(unter der Annahme b{0,1} und |x1|=|x2|.) Das ist leicht zu sehen f ist auch einseitig - um es zu invertieren, müssen Sie entweder invertieren g in der ersten Hälfte oder invertieren g in der zweiten Hälfte.

Jetzt zeigen wir, wie man invertiert h. Angenommen, Sie sind gegebenh(u,v)=Zschreiben wir es als h(u,v)=z1z2 mit |z1|=|z2|=n. Dann ein mögliches Vorbild vonZ ist

u=00ng(0n)z2
v=1g(0n)z10n

da f(u)=g(0n)g(0n)z2 und f(v)=g(0n)z1g(0n) somit gibt ihr XOR genau z1z2 wie erforderlich.

Ran G.
quelle
Könnten Sie weitere Details zum Invertieren hinzufügen? G? Einige gegebenxverketten Sie einen Zufall x1 oder x2 und dann berechnen f- -1(xx2) und / oder f1(x1x). Aber das Ergebnis könnte nachgebeng1(x1) und g1(x2). 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 fist ein Weg? Angenommen, Sie habenA das invertiert es und verwendet es, um zu invertieren g(x) durch Abfragen A auf g(x)g(x).
Ran G.
@RanG: Wie offensichtlich f1(xx). Vielen Dank!
Frafl