einwegfunktionen



  • hallo

    ich hab mal aufgeschnappt, dass es nicht klar ist ob einwegfunktionen existieren oder nicht. sind nicht die lösungen aller np-schweren probleme einwegfunktionen?

    mfg



  • Nein, es ist ja nicht bekannt ob P=NP oder P!=NP gilt. Im letzteren Fall eigenen sich diese Probleme in der Tat. Sollte aber der erste Fall zutreffen, dann gibt es ggf. überhaupt keine Einwegfunktionen.



  • Was wäre z.B. mit:

    y=x mod 2y = x~mod~2

    Für unendliche viele Zahlen x, würde die Gleichung immer die Lösung 1 oder 0 haben. Man würde in die eine Richtung immer nur eine und in die andere unendlich viele Lösung erhalten.



  • Für manche wär das eine Einwegfunktion, weil sie so lange brauchen, sich zwischen den vielen möglichen Urbildern zu entscheiden (mich zum Beispiel), andere wählen ganz pragmatisch x = y.



  • Bashar schrieb:

    andere wählen ganz pragmatisch x = y.

    Das gilt aber auch nur für x={0;1} und das Ergebnis y={0;1}, ist auch das Ergebnis aller anderen Zahlen x.

    Wie sieht es mit Hash-Funktionen aus? Wenn ich endlich viele Blöcke logisch verknüpfe, kann ich aus dem Ergebnis nicht die einzelnen Blöcke wiederherstellen.



  • SLx64 schrieb:

    Was wäre z.B. mit:

    y=x mod 2y = x~mod~2

    Für unendliche viele Zahlen x, würde die Gleichung immer die Lösung 1 oder 0 haben. Man würde in die eine Richtung immer nur eine und in die andere unendlich viele Lösung erhalten.

    Dann lieber gleich
    y=0

    Aber ich fürchte, http://en.wikipedia.org/wiki/One-way_function#Theoretical_definition wird bei unseren beiden Versuchen gar nicht erfüllt.



  • SLx64 schrieb:

    Bashar schrieb:

    andere wählen ganz pragmatisch x = y.

    Das gilt aber auch nur für x={0;1} und das Ergebnis y={0;1}, ist auch das Ergebnis aller anderen Zahlen x.

    Und, wo ist das Problem? Ich hoffe, ich habe ungefähr verstanden, was du mir mitteilen willst, deine Notation und Grammatik machen das nicht ganz einfach.

    Wie sieht es mit Hash-Funktionen aus? Wenn ich endlich viele Blöcke logisch verknüpfe, kann ich aus dem Ergebnis nicht die einzelnen Blöcke wiederherstellen.

    Das ist auch nicht nötig.



  • Jester schrieb:

    Nein, es ist ja nicht bekannt ob P=NP oder P!=NP gilt. Im letzteren Fall eigenen sich diese Probleme in der Tat. Sollte aber der erste Fall zutreffen, dann gibt es ggf. überhaupt keine Einwegfunktionen.

    Was meinst Du in diesem Zusammenhang mit "ggf."? Koennte es trotzdem welche geben?



  • Gregor schrieb:

    Jester schrieb:

    Nein, es ist ja nicht bekannt ob P=NP oder P!=NP gilt. Im letzteren Fall eigenen sich diese Probleme in der Tat. Sollte aber der erste Fall zutreffen, dann gibt es ggf. überhaupt keine Einwegfunktionen.

    Was meinst Du in diesem Zusammenhang mit "ggf."? Koennte es trotzdem welche geben?

    Falls eine Einwegfunktion existiert, dann ist P != NP. Die Umkehrung gilt nicht.



  • Bashar schrieb:

    Und, wo ist das Problem?

    Naja, du hast für jeden x-Wert die Lösung 1 oder 0 und wenn das Ergebnis von y = x gleich den Ergebnissen von allen anderen x-Werten ist, weißt du im Endeffekt immer noch nicht, dass y = x ist. Der Sinn von Einwegfunktionen ist doch, dass man aus einem Wert y, keinen Wert x berechnen kann. Ich gehe deshalb davon aus, dass x nicht bekannt ist. Die Möglichkeit, dass y = x sein könnte, schließt in diesem Fall aber nicht aus, dass y != x ist.

    Bashar schrieb:

    Das ist auch nicht nötig.

    Gleiches Problem wie oben - warum ist es dann keine Einwegfunktion?



  • SLx64 schrieb:

    Bashar schrieb:

    Und, wo ist das Problem?

    Naja, du hast für jeden x-Wert die Lösung 1 oder 0 und wenn das Ergebnis von y = x gleich den Ergebnissen von allen anderen x-Werten ist, weißt du im Endeffekt immer noch nicht, dass y = x ist.

    Ich glaube, du willst darauf hinaus, dass deine Funktion jeweils viele x-Werte auf einen y-Wert abbildet. Konkret werden alle geraden x auf 0 und alle ungeraden auf 1 abgebildet. Seh ich das richtig? Und du meinst, deshalb wäre es keine Einwegfunktion? Falsch, es kommt nicht darauf an, das ursprüngliche x zu rekonstruieren (das geht in der Tat bei den meisten Funktionen nicht), sondern *irgendein* passendes x zu finden.



  • Bashar schrieb:

    deshalb wäre es keine Einwegfunktion? Falsch, es kommt nicht darauf an, das ursprüngliche x zu rekonstruieren (das geht in der Tat bei den meisten Funktionen nicht), sondern *irgendein* passendes x zu finden.

    Doch, genau deshalb wäre es für mich eine Einwegfunktion. Ich bin jetzt davon ausgegangen, dass man mit einer Einwegfunktion für jeden beliebigen y-Wert, keinen genauen x-Wert bestimmen kann.

    Wenn ich dich jetzt also richtig verstehe, darf es nicht möglich sein, eine beliebige Lösung für x zu finden? Für jeden Wert y, darf dann nur ein Wert x vorhanden sein und es darf keine Umkehrfunktion existieren?



  • SLx64 schrieb:

    Ich bin jetzt davon ausgegangen, dass man mit einer Einwegfunktion für jeden beliebigen y-Wert, keinen genauen x-Wert bestimmen kann.

    Man muss auch keinen genauen x-Wert bestimmen sondern irgend ein Urbild. Wenn für ein gegebenes f(x) effizient ein Urbild x' gefunden werden kann mit f(x) = f(x'), dann ist es keine Einwegfunktion.

    Einwegfunktion sind aber in allgemeinen heikel und man braucht dafür formale Definitionen. Siehe zum Beispiel Wikipedia, One-Way Functions unter Theoretical Definitions.



  • Damit haben sich natürlich auch die Hash-Funktionen erledigt.



  • SLx64 schrieb:

    Damit haben sich natürlich auch die Hash-Funktionen erledigt.

    Sehe ich nicht.



  • SLx64 schrieb:

    Damit haben sich natürlich auch die Hash-Funktionen erledigt.

    Was meinst du?



  • Was ich damit meine ist, dass auch bei einer Hash-Funktion unterschiedliche Nachrichten, den gleichen Wert besitzen können.



  • SLx64 schrieb:

    Was ich damit meine ist, dass auch bei einer Hash-Funktion unterschiedliche Nachrichten, den gleichen Wert besitzen können.

    Bei einer Einwegfunktion dürfen unterschiedliche Eingaben zur selben Ausgabe führen. Es muss nur genug unterschiedliche Ausgaben geben, daß man sie nicht mit hoher Wahrscheinlichkeit erraten kann, und man soll von einer Ausgabe nicht mit einem kleinen Progrämmchen auf eine Eingabe rückrechnen können, die diese Ausgabe erzeugen würde.



  • Okay, jetzt ist alles klar. ^^


Log in to reply