Folgen des Factorings in P?

Es ist nicht bekannt, dass Factoring NP-vollständig ist. Diese Frage bezog sich auf die Konsequenzen einer NP-vollständigen Faktorisierung. Seltsamerweise fragte niemand nach den Konsequenzen, wenn Factoring in P ist (vielleicht, weil eine solche Frage trivial ist).

Meine Fragen sind also:

Was wären die theoretischen Konsequenzen von Factoring in P? Wie würde sich eine solche Tatsache auf das Gesamtbild der Komplexitätsklassen auswirken?
Welche praktischen Konsequenzen hätte Factoring in P? Bitte sagen Sie nicht, dass Bankgeschäfte in Gefahr sein könnten, ich kenne diese unbedeutende Konsequenz bereits.

cc.complexity-theory cr.crypto-security conditional-results factoring Giorgio Camerani
quelle

Ich habe vor ein paar Tagen eine ähnliche Frage gestellt: "Was ist die Potenz von P mit einem ganzzahligen Faktorisierungsorakel?" cstheory.stackexchange.com/questions/4765/…

Marzio De Biasi

Ebenfalls verwandt: Welche Konsequenzen hat die NP-Vollständigkeit des Factorings?

Kaveh

@Kaveh, die Frage ist bereits mit dieser verknüpft.

Peter Taylor

Antworten:

Es gibt so gut wie keine komplexitätstheoretischen Konsequenzen, wenn Factoring in P ist. Dies bedeutet, dass es keine guten Gründe dafür gibt, dass Factoring hart ist, außer dass es bisher noch niemand geknackt hat.

Polynomial-Time-Factoring würde es ermöglichen, Quadratwurzeln über (und auch über eine viel allgemeinere Klasse von Ringen) zu ziehen und Polynomial-Time-Algorithmen für eine Reihe anderer zahlentheoretischer Probleme zu liefern, für die der Engpass besteht Der Algorithmus ist derzeit Factoring. $Z_n$

Was die praktischen Konsequenzen angeht, sind Bankgeschäfte wahrscheinlich kein so großes Problem - sobald bekannt war, dass Factoring in P enthalten ist, würden die Banken auf ein anderes System umsteigen, was wahrscheinlich nur kurze Verzögerungen verursacht umgesetzt. Die Dekodierung vergangener Bankgeschäfte würde den Banken wahrscheinlich keine ernsthaften Probleme bereiten. Ein viel ernsteres Problem ist, dass die gesamte Kommunikation, die zuvor von RSA geschützt wurde, jetzt in Gefahr ist, gelesen zu werden.

Peter Shor
quelle

Etwas abseits des Themas, aber as soon as it was known that factoring was in P, the banks would switch to some other systemgrößtenteils Wunschdenken. Im Dezember entdeckte ich, dass ein Unternehmen, das nur Kreditkartendaten verarbeitet, eine Variante von Vigenère mit einem Schlüssel verwendet, der kürzer ist als einige bekannte Klartextläufe. Schlimmer noch, der technische Direktor des Unternehmens würde mir nicht glauben, dass es unsicher ist, bis ich ihm einen Angriffscode geschickt habe. MD5 wird, obwohl es allgemein als defekt eingestuft wird, immer noch stark im Bankgeschäft eingesetzt.

Peter Taylor

@PeterTaylor, sobald bekannt war, dass es sich bei Factoring um P handelt, würden die Banken auf ein anderes System umsteigen. "Mit dem derzeit günstigen Preis für Flash-Speicher ist es durchaus möglich, eine One-Time-Pad-Lösung für P zu erstellen Banken, Benutzer gingen von Zeit zu Zeit zu einem Geldautomaten, um zusätzliche zufällige Bytes herunterzuladen. RSA ist nur billiger und einfacher.

Flávio Botelho

Starke symmetrische Chiffren sind kein Ersatz für asymmetrische Chiffren, obwohl sie für bestimmte Aufgaben ausreichen. Sie haben das Problem, dass Sie digitale Signaturen usw. nicht verwenden können.

Joe Fitzsimons

Tatsächlich können Sie digitale Signaturen mit symmetrischen Chiffren haben! Es ist nur viel umständlicher und Sie benötigen ein viel größeres Vertrauen in die vertrauenswürdige dritte Partei. Lesen Sie die Kapitel 11.6 und 11.7 des Handbuchs für Angewandte Kryptographie.

Flávio Botelho

@Flavio: Aber Nicht-Ablehnung funktioniert nicht auf die gleiche Weise, oder?

Joe Fitzsimons

RSA ist eines der wichtigsten Verschlüsselungs- / Signaturschemata, das bei FACTORING in P nicht funktioniert. Es gibt jedoch noch viel mehr. Einige (aber nicht alle) von ihnen basieren auf der Annahme, dass die Unterscheidung von Quadraten und Nichtquadraten modulo einer zusammengesetzten Zahl schwierig ist :

Und viele andere Schemata. Beachten Sie jedoch, dass Schemata, die auf der Härte des diskreten Protokolls basieren (z. B. das Diffie-Helmann-Protokoll oder das Elgamal-Verschlüsselungs- / Signaturschema ), weiterhin sicher sind.

MS Dousti
quelle

Es scheint mir sehr wahrscheinlich, dass, wenn Factoring in P ist, das Problem des diskreten Protokolls auch so ist. Mit Sicherheit ist das Gegenteil der Fall.

Joe Fitzsimons

@ Joe: Ich habe die gleichen Gefühle, aber gibt es Beweise oder mathematische Beweise?

MS Dousti

a^{p q} \equiv a^{p + q - 1} (mod p q)

$a^{pq} \equiv a^{p+q-1}~(\mbox{mod } pq)$

c_{a} = \log_{N} (a^{N} mod N)

$c_a = \log_N(a^N \mbox{mod }N)$

p = x + y

$p = x + y$

q = x - y

$q = x - y$

x = \frac{c_{a} + 1}{2}

$x = \frac{c_a + 1}{2}$

y = \sqrt{x^{2} - N}

$y = \sqrt{x^2 - N}$

@ Joe: Sehr interessant! Ihr Kommentar hat mich dazu motiviert, näher darauf einzugehen, und Eric Bach stellte fest, dass "das Lösen des diskreten Logarithmusproblems für einen zusammengesetzten Modul genauso schwierig ist wie das Zerlegen und Lösen von Modulo-Primzahlen ".

MS Dousti

Gitterbasierte Krypto sollte jedoch hoffentlich sicher bleiben.

Antimon

$P$

Mohammad Al-Turkistany
quelle