Einweg-Permutationen ohne Falltür

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 Einweg-Funktions-Tag-Wiki ). Wir betrachten normalerweise Familien der Einwegpermutation, , wobei jede eine Einwegpermutation ist, die auf eine endliche Domäne wirkt . Eine Falltür -Einwegpermutation ist wie oben definiert, außer dass es eine Falltürmenge und einen mehrzeitinvertierenden Algorithmus , so dass für alle , und $\pi$ $\pi = \{\pi_n\}_{n \in \mathbb{N}}$ $\pi_n$ $D_n$ $\{t_n\}_{n \in \mathbb{N}}$ $I$ $n$ $|t_n| \le {\rm poly}(n)$ $I$ kann invertieren, vorausgesetzt, es wird . $\pi_n$ $t_n$

Ich kenne Einweg-Permutationen, die so generiert werden, dass es unmöglich ist , die Falltür zu finden (die Falltür existiert jedoch). Ein Beispiel, das auf der RSA-Annahme basiert, wird hier gegeben . Die Frage ist,

Gibt es (Familien von) Einweg-Permutationen, die keine Falltür (Set) haben?

Edit: (Mehr Formalisierung)

Angenommen, es gibt eine Einwegpermutation mit (unendlicher) Domäne . Das heißt, es gibt einen probabilistischen Polynom-Zeit-Algorithmus (der bei Eingabe eine gewisse Verteilung über induziert ), so dass z ein beliebiger polynomialer Zeitgegner , ein beliebiger und alle ausreichend große ganze Zahl : $\pi$ $D \subseteq \{0,1\}^*$ $\mathcal{D}$ $1^n$ $D_n=\\{0,1\\}^n \cap D$ $\mathcal{A}$ $c>0$ $n$

$\Pr[x \leftarrow \mathcal{D}(1^n) \colon \quad \mathcal{A}(\pi(x))=x]<n^{-c}$

(Die Wahrscheinlichkeit wird über die internen Münzwürfe von $\mathcal{D}$ und $\mathcal{A}$ .)

Die Frage ist, ob wir eine Einwegpermutation konstruieren können , für die es einen probabilistischen Polynomzeitalgorithmus so dass für jede Familie von Schaltungen mit Polygröße , jedes und alle ausreichend große ganze Zahl : $\pi'$ $\mathcal{D}'$ $\mathcal{A}'=\{\mathcal{A}'_n\}_{n \in \mathbb{N}}$ $c>0$ $n$

$\Pr[x \leftarrow \mathcal{D}'(1^n) \colon \quad \mathcal{A}'_n(\pi'(x))=x]<n^{-c}$

(Die Wahrscheinlichkeit wird über die internen Münzwürfe von , da deterministisch ist.) $\mathcal{D}'$ $\mathcal{A}'$

cr.crypto-security one-way-function MS Dousti
quelle

Es hört sich so an, als ob Sie ein OWP wollen, das auch dann in eine Richtung bleibt, wenn Sie eine polynomielle Menge an Ratschlägen erhalten. Übrigens definieren wir normalerweise keine solchen OWP-Familien - siehe Goldreich Vol 1, Defs 2.4.4 und 2.4.5.

David Cash

@ David: Ja, ich weiß, dass es nicht die übliche Definition ist, aber ich fand, dass die formale Definition (die in Goldreichs Buch erscheint) zu lang für diese Diskussion ist.

MS Dousti

@Adeq: Fair genug, aber ich denke, dass die Änderung der Definitionen hier signifikant sein wird. Für das, was es wert ist, habe ich zuvor versucht, über eine ähnliche Art von Sicherheit (keine Falltüren) nachzudenken. Es schien eine gute Definition zu sein, eine unbegrenzte Verarbeitung des Familienindex zuzulassen, um vor dem Inversionsexperiment Ratschläge zu erhalten.

David Cash

@ David: Überprüfen Sie, ob der bearbeitete Teil die Notwendigkeit einer weiteren Formalisierung erfüllt.

MS Dousti

@Sadeq: Die Bestimmung, ob Falltür-Einwegpermutationen durch Einwegpermutationen impliziert werden oder nicht (obwohl nicht einmal klar ist, was letzteres bedeutet, da beide möglicherweise existieren könnten), ist eines der größten offenen Probleme in der Theorie der Kryptographie . Impagliazzo und Rudich ( cseweb.ucsd.edu/~russell/secret.ps ) haben bewiesen, dass dies mit Black-Box-Techniken nicht erreicht werden kann, und es ist nicht bekannt, dass aktuelle Techniken ihre Trennung umgehen.

Alon Rosen

Antworten:

Betrachten Sie die folgenden Fälle:

1) One-Way-Permutationen (OWP) existieren, Trapdoor-Permutationen (TDP) jedoch nicht (dh wir befinden uns in einer Variante von Impagliazzos " Minicrypt " -Welt ). In diesem Fall nehmen Sie einfach das OWP, das garantiert existiert, und Sie wissen, dass es keine Falltür hat.

2) Es gibt sowohl OWP als auch TDP. Hier haben Sie zwei Möglichkeiten:

(a) Jedes OWP hat einen Schlüsselerzeugungsalgorithmus G, der die "öffentliche" Beschreibung f der Funktion zusammen mit einer abgetasteten Falltür t ausgibt. Betrachten Sie in diesem Fall eine modifizierte Schlüsselgenerierung, die nur f ausgibt. Dies gibt Ihnen einen OWP, und außerdem ist es unmöglich, t gegebenes f zu finden (da Sie sonst eine effiziente Möglichkeit haben, f zu invertieren). Dies sollte auch für eine ungleichmäßige Variante gelten.

(b) Es gibt ein OWP f, so dass kein Algorithmus G sowohl f als auch t ausgeben kann, so dass t die Inversion von f (x) für ein zufälliges x ermöglicht. In diesem Fall ist f ein OWP ohne Falltür.

Einer der Kommentare im obigen Thread scheint darauf hinzudeuten, dass Sie sich tatsächlich fragen, ob die Existenz von OWP bekanntermaßen die Existenz von TDP impliziert. Es hat sich gezeigt , dass dies keine Black-Box-Konstruktionen / -Reduktionen enthält, und es ist im Allgemeinen offen (siehe meinen Kommentar im obigen Thread).

Alon Rosen
quelle

+1, danke. David hat sich sehr bemüht zu antworten, und ich bin ihm sehr dankbar; Aber das ist die Antwort auf das, was ich vorhatte.

MS Dousti

Ich dachte die Frage wäre: ist (a) möglich. Wenn jede OWP kryptografisch eine Falltür hat, können Sie niemandem vertrauen, der Ihnen eine OWP gibt, um die Falltür nicht zu kennen. Natürlich können Sie seine OWP nehmen und mit Ihrer eigenen OWP komponieren, für die nur Sie die Falltür kennen, und eine OWP erhalten, für die keine Partei die Falltür kennt.

Peter Shor

@ Peter: Ja. Die Komposition scheint den Job zu machen. Eine andere Möglichkeit besteht darin, eine ahnungslose Übertragung zu verwenden (die, wenn (a) gilt, bekanntermaßen existiert - modulo einige kleine Feinheiten). Mit OT können die Spieler ein sicheres 2-Parteien-Berechnungsprotokoll erstellen, mit dem einer von ihnen f lernen kann, ohne die Falltür zu lernen, und der andere nichts lernen kann. Aber Ihre Lösung ist in der Tat einfacher.

Alon Rosen

Ich kenne Konstruktionen aus allgemeinen Annahmen nicht, aber Sie können einen plausiblen Kandidaten für eine "Einwegpermutation ohne Falltür" erhalten, indem Sie diskretes log modulo a prime . Das heißt, sei ein primitives Wurzelmodulo und definiere . Dann ist eine Permutation auf den ganzen Zahlen zwischen und , und es wird allgemein angenommen, dass es sich um eine Einbahnstraße handelt. Für den Teil "keine Falltür" müssen Sie wahrscheinlich genau definieren, was das bedeutet, aber soweit ich weiß, haben wir keine Möglichkeit, Dinge so einzurichten, dass eine Inversion möglich ist. (Wenn wir das tun würden, hätte es alle möglichen coolen (positiven) Anwendungen in der Kryptographie!) $p$ $g$ $p$ $\pi(x) = g^x\!\mod p$ $\pi$ $1$ $p-1$

David Cash
quelle

+1. Danke für die Antwort. Sie nehmen die Härte des diskreten Protokolls gegenüber ungleichmäßigen Gegnern an. Meine Frage ist: Können wir unter der Annahme der bloßen Existenz von Einwegpermutationen eine konstruieren, die keine Falltür hat?

MS Dousti

@Sadeq: Bedeutet das Vorhandensein von Einwegpermutationen nicht die Härte des diskreten Logs, da P = NP ist?

Mohammad Alaggan

@Alaggan: Das glaube ich nicht. Es kann vorkommen, dass Einweg-Permutationen vorhanden sind, aber jemand hat einen effizienten Algorithmus zum Invertieren diskreter Protokolle entwickelt.

MS Dousti

@Adeq: Das ist, wenn P = BQP! = NP.

Mohammad Alaggan

@Sadeq: Richtig oder habe ich es falsch verstanden?

Mohammad Alaggan