Kann es eine Verschlüsselungsmethode geben, die auch mit Quantencomputern nicht geknackt werden kann?

Es ist bekannt, dass Quantencomputer in der Lage sind, eine breite Palette von kryptografischen Algorithmen in Polynomialzeit zu knacken , von denen vorher angenommen wurde, dass sie nur durch Ressourcen lösbar sind, die exponentiell mit der Bitgröße des Schlüssels ansteigen. Ein Beispiel dafür ist Shors Algorithmus .

Soweit ich weiß, fallen jedoch nicht alle Probleme in diese Kategorie. Auf harte Probleme zu machen für Quantencomputer , können wir lesen

Die Forscher haben einen Computeralgorithmus entwickelt, der Probleme nicht löst, sondern zur Bewertung von Quantencomputern erstellt.

Können wir noch einen neuen kryptografischen Algorithmus erwarten , der selbst mit einem Quantencomputer schwer zu knacken sein wird ? Zur Verdeutlichung: Die Frage bezieht sich speziell auf das Design neuer Algorithmen .

Der Titel Ihrer Frage fragt nach unlösbaren Techniken, auf die das One Time Pad (OTP) die richtige Antwort ist, wie in den anderen Antworten ausgeführt. Das OTP ist informationstheoretisch sicher, was bedeutet, dass die Rechenfähigkeiten eines Gegners nicht anwendbar sind, wenn es darum geht, die Nachricht zu finden.

Obwohl das OTP theoretisch vollkommen sicher ist , ist es in der modernen Kryptographie nur begrenzt einsetzbar. In der Praxis ist die erfolgreiche Anwendung äußerst schwierig .

Die wichtige Frage ist wirklich:

Können wir noch einen neuen kryptografischen Algorithmus erwarten, der selbst mit einem Quantencomputer schwer zu knacken sein wird?

Asymmetrische Kryptographie

Die asymmetrische Kryptografie umfasst Public-Key-Verschlüsselung (PKE), digitale Signaturen und Schlüsselvereinbarungsschemata. Diese Techniken sind von entscheidender Bedeutung, um die Probleme der Schlüsselverteilung und des Schlüsselmanagements zu lösen. Schlüsselverteilung und Schlüsselverwaltung sind nicht zu vernachlässigende Probleme. Sie verhindern weitgehend, dass das OTP in der Praxis verwendet werden kann. Das Internet, wie wir es heute kennen, würde ohne die Fähigkeit, einen gesicherten Kommunikationskanal aus einem unsicheren Kommunikationskanal zu erstellen, nicht funktionieren. Dies ist eines der Merkmale, die asymmetrische Algorithmen bieten.

Shors Algorithmus

Shors Algorithmus ist nützlich, um die Probleme der ganzzahligen Faktorisierung und der diskreten Logarithmen zu lösen. Diese beiden Probleme bilden die Grundlage für die Sicherheit weit verbreiteter Systeme wie RSA und Diffie-Hellman .

Das NIST prüft derzeit Einreichungen für Post-Quantum-Algorithmen - Algorithmen, die auf Problemen basieren, von denen angenommen wird, dass sie gegenüber Quantencomputern resistent sind. Diese Probleme umfassen:

• Gitterbasierte Probleme
  • Kürzestes Vektorproblem (SVP)
  • Nächstes Vektorproblem (CVP)
• Multivariate Gleichungen
  • Multivariate Polynomgleichungen
• Code-basierte Schemata
  • Basierend auf der Härte der Dekodierung linearer Codes
• Supersingular Isogeny Diffie-Hellman (SIDH)

Es sollte beachtet werden, dass klassische Algorithmen zur Lösung der oben genannten Probleme existieren können. Es ist nur so, dass die Laufzeit / Genauigkeit dieser Algorithmen für die Lösung großer Instanzen in der Praxis unzulässig ist. Diese Probleme scheinen nicht lösbar zu sein, wenn die Fähigkeit gegeben wird, das Problem der Ordnungsfindung zu lösen , was der Quantenteil von Shors Algorithmus tut.

Symmetrische Kryptographie

Der Algorithmus von Grover sorgt für eine quadratische Beschleunigung beim Durchsuchen einer unsortierten Liste. Dies ist effektiv das Problem, das einen symmetrischen Verschlüsselungsschlüssel brachial erzwingt.

Das Umgehen des Algorithmus von Grover ist im Vergleich zum Umgehen des Algorithmus von Shor relativ einfach: Verdoppeln Sie einfach die Größe Ihres symmetrischen Schlüssels . Ein 256-Bit-Schlüssel bietet einem Gegner, der den Grover-Algorithmus verwendet, einen Widerstand von 128 Bit gegen Brute Force.

Der Algorithmus von Grover kann auch für Hash-Funktionen verwendet werden . Die Lösung ist wiederum einfach: Verdoppeln Sie die Größe Ihrer Hash-Ausgabe (und die Kapazität, wenn Sie einen auf einer Schwammkonstruktion basierenden Hash verwenden ).

Ich nehme an, es gibt eine Art von Verschlüsselung, die mit Quantencomputern nicht geknackt werden kann: ein Einmal-Pad wie die Vigenère-Chiffre . Dies ist eine Chiffre mit einer Tastatur, die mindestens die Länge der codierten Zeichenfolge hat und nur einmal verwendet wird. Diese Chiffre ist selbst mit einem Quantencomputer nicht zu knacken.

Ich werde erklären, warum:

Nehmen wir an, unser Klartext ist ABCD. Der entsprechende Schlüssel könnte sein 1234. Wenn Sie es codieren, erhalten Sie XYZW. Jetzt können Sie verwenden 1234, um einen möglicherweise gültigen Satz abzurufen ABCDoder abzurufen.4678EFGH

Das Problem ist also, dass niemand entscheiden kann, ob Sie meinen ABCDoder nicht, EFGHohne Ihren Schlüssel zu kennen.

Der einzige Grund, warum diese Art der Verschlüsselung geknackt werden kann, ist, dass die Benutzer faul sind und einen Schlüssel zweimal verwenden. Und dann können Sie versuchen, es zu knacken. Andere Probleme sind, wie @peterh feststellte, dass One-Time-Pads die gemeinsame Nutzung eines geheimen Kanals erfordern

Ja, es gibt viele Vorschläge für postquantenkryptografische Algorithmen, die die von uns gewohnten kryptografischen Grundelemente enthalten (einschließlich asymmetrischer Verschlüsselung mit privaten und öffentlichen Schlüsseln).

Um die Antwort von Ella Rose weiterzuverfolgen: Die meisten heute verwendeten praktischen Verschlüsselungsverfahren (z. B. Diffie-Hellman, RSA, elliptische Kurve, gitterbasiert) konzentrieren sich auf die Schwierigkeit, das Problem der versteckten Untergruppen (HSP) zu lösen . Die ersten drei konzentrieren sich jedoch auf die HSP für abelsche Gruppen. Der HSP für abelsche Gruppen kann effizient durch die Quanten-Fourier-Transformation gelöst werden , die zB durch Shors Algorithmus implementiert wird. Sie sind daher anfällig für Angriffe durch einen Quantencomputer. Die meisten gitterbasierten Methoden hingegen drehen sich um das HSP für DiederGruppen, die nonabelian sind. Es wird nicht angenommen, dass Quantencomputer in der Lage sind, das nicht-labelianische HSP effizient zu lösen, daher sollten diese Algorithmen in der Lage sein, die Post-Quanten-Kryptographie zu implementieren.