Reduzieren des Factorings von Hauptprodukten auf das Factoring von ganzzahligen Produkten (im Durchschnitt)

Meine Frage betrifft die Gleichwertigkeit der Sicherheit verschiedener Kandidaten-Einwegfunktionen, die auf der Grundlage der Härte des Factorings konstruiert werden können.

Angenommen, das Problem von

FAKTORIERUNG: [Wenn für zufällige Primzahlen , finde , ]$N = PQ$$P, Q < 2^n$$P$$Q$

kann nicht in Polynomzeit mit nicht zu vernachlässigender Wahrscheinlichkeit die Funktion gelöst werden

PRIME-MULT: [Verwenden Sie bei gegebener Bitfolge als Eingabe als Startwert , um zwei zufällige Primzahlen und zu erzeugen (wobei die Längen von , nur polynomiell kleiner als die Länge von ); dann ausgeben .]$x$$x$$P$$Q$$P$$Q$$x$$PQ$

kann als einseitig gezeigt werden.

Eine weitere mögliche Einwegfunktion ist

INTEGER-MULT: [Gegebene zufällige ganze Zahlen als Eingabe, Ausgabe .]$A, B < 2^n$$A B$

INTEGER-MULT hat den Vorteil, dass es im Vergleich zu PRIME-MULT einfacher zu definieren ist. (Beachten Sie insbesondere, dass in PRIME-MULT die Möglichkeit besteht (wenn auch glücklicherweise vernachlässigbar), dass der Keim keine , die Primzahlen sind.)$x$$P, Q$

Zumindest an zwei verschiedenen Stellen (Arora-Barak, Computational Complexity, Seite 177, Fußnote 2) und ( Vadhans Einführung in die Kryptographie-Vorlesungsunterlagen ) wird erwähnt, dass INTEGER-MULT unter der Annahme einer durchschnittlichen Faktorisierungshärte einseitig ist. Keiner dieser beiden gibt jedoch den Grund oder einen Hinweis für diese Tatsache an.

Die Frage ist also:

Wie können wir das Polynom-Time-Factoring von mit nicht vernachlässigbarer Wahrscheinlichkeit auf die Invertierung von INTEGER-MULT mit nicht vernachlässigbarer Wahrscheinlichkeit reduzieren?$N = PQ$

Hier ist ein möglicher Ansatz (der, wie wir sehen werden, NICHT funktioniert!): Wenn , multiplizieren Sie mit einer viel (wenn auch polynomiell) längeren zufälligen ganzen Zahl , um . Die Idee ist, dass so groß ist, dass es viele Primfaktoren mit einer Größe hat, die ungefähr gleich , so dass nicht unter den Primfaktoren von "hervorstechen" . Dann hat ungefähr die Verteilung einer gleichmäßig zufälligen ganzen Zahl in einem gegebenen Bereich (sagen wir ). Wählen Sie als nächstes zufällig die ganze Zahl aus demselben Bereich .$N = PQ$$N$$A'$$A = NA'$$A'$$P, Q$$P, Q$$A$$A$$[0,2^n-1]$$B$$[0,2^n-1]$

Wenn nun ein Wechselrichter für INTEGER-MULT bei gegebener mit einiger Wahrscheinlichkeit so dass , besteht die Hoffnung, dass einer von oder als a enthält Faktor und die andere enthält . Wenn dies der Fall war, können wir oder indem wir gcd von mit .$AB$$A', B' < 2^n$$A'B' = AB$$A'$$B'$$P$$Q$$P$$Q$$A'$$N = PQ$

Das Problem ist, dass der Wechselrichter die Primfaktoren trennen kann, indem er beispielsweise die kleinen Faktoren von in und die großen in , so dass und beide in oder beide in enden. .$AB$$A'$$B'$$P$$Q$$A'$$B'$

Gibt es einen anderen Ansatz, der funktioniert?

Dies ist keine wirkliche Antwort, wirft jedoch ein Licht auf die Schwierigkeit, solche Reduzierungen nachzuweisen.

Das Problem kann wie folgt zusammengefasst werden: Sei ein Algorithmus, der das INTEGER-MULT-Problem mit nicht zu vernachlässigender Wahrscheinlichkeit löst. Diese Wahrscheinlichkeit sei mindestens für eine Konstante (wenn die Größe der Eingabe ). Beweisen Sie, dass es einen PPT-Algorithmus (probabilistic polynomial-time) , der als Unterprogramm verwendet und eine Instanz des FACTORING-Problems der Größe mit einer Wahrscheinlichkeit von mindestens löst , für eine Konstante .$\mathcal{A}$$n^{-c}$$c \in \mathbb{N}$$n$$\mathcal{A}'$$\mathcal{A}$$n$$n^{-d}$$d \in \mathbb{N}$

Betrachten Sie einen Algorithmus , der das INTEGER-MULT-Problem genau dann löst, wenn der Eingang das Special von , wobei und Primzahlen der Größe und eine Primzahl der Größe ist und schlägt ansonsten fehl. Darüber hinaus gibt es bei Eingabe einer ganzen Zahl der obigen Form und . Wir zeigen zunächst, dass eine nicht zu vernachlässigende Wahrscheinlichkeit hat, das INTEGER-MULT-Problem zu lösen. Zu diesem Zweck reicht es aus, den Bruchteil von zu finden$\mathcal{A}^*$$N$ $N = PQR$$P$$Q$$n/4$$R$$n/2$$N$$PQ$$R$$\mathcal{A}^*$$n$-bit-Ganzzahlen der Sonderform, da dieser Bruch die Erfolgswahrscheinlichkeit von von unten begrenzt.$\mathcal{A}^*$

Nach dem Primzahlsatz beträgt die Anzahl der Primzahlen, deren Größe Bits beträgt:$k$

$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$

Daher ist der Anteil der Bit-Ganzzahlen der Sonderform:$n$

$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$

was in nicht zu vernachlässigen ist .$n$

Daher sollte man in der Lage sein, die Existenz eines PPT-Algorithmus zu beweisen , der als Unterprogramm verwendet und eine Instanz des FACTORING-Problems der Größe mit einer Wahrscheinlichkeit von mindestens löst für eine Konstante .A ∗ n n - d d∈$\mathcal{A}'$$\mathcal{A}^*$$n$$n^{-d}$$d \in \mathbb{N}$

IMHO scheint dies eine sehr schwierige Aufgabe zu sein, da nur (teilweise) Ganzzahlen der speziellen Form zerlegt und es keine Möglichkeit zu geben scheint, damit Ganzzahlen der Form zu zerlegen . P$\mathcal{A}^*$$PQ$