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

10

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=PQP,Q<2nPQ

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 .]xxPQPQxPQ

kann als einseitig gezeigt werden.

Eine weitere mögliche Einwegfunktion ist

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

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.)xP,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=PQNAA=NAAP,QP,QAA[0,2n1]B[0,2n1]

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 .ABA,B<2nAB=ABABPQPQAN=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. .ABABPQAB

Gibt es einen anderen Ansatz, der funktioniert?

Omid Etesami
quelle
Können wir die Ausfallwahrscheinlichkeit von INT-FACT verringern, um exponentiell klein zu sein, und dann die Dichte der Primzahlen verwenden, um zu sagen, dass es bei den meisten Produkten von zwei Primzahlen nicht versagt?
Kaveh
2
Wenn wir INTEGER-MULT für alle Instanzen außer einem exponentiell kleinen Bruchteil der Instanzen invertieren könnten, wäre es in der Tat einfach, Produkte von Primzahlen zu FAKTORIEREN. Aber ich kenne keinen Weg, einen starken Wechselrichter von einem schwachen Wechselrichter zu bekommen.
Omid Etesami
1
Die (irgendwie) Umkehrung dieses Problem wurde bereits diskutiert hier .
MS Dousti

Antworten:

4

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 .AnccNnAAnnddN

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 findenAN N=PQRPQn/4Rn/2NPQRAn-bit-Ganzzahlen der Sonderform, da dieser Bruch die Erfolgswahrscheinlichkeit von von unten begrenzt.A

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

2k/ln(2k)2k1/ln(2k1)=Θ(2k/k)

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

Θ(2n/4/(n/4))2Θ(2n/2/(n/2))2n1=Θ(n3)

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 N.AAnnddN

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 . PQ.APQ

MS Dousti
quelle