Hallo Habr. Kürzlich kündigte NIST auf seiner Website den Beginn der dritten Phase der Standardisierung der Post-Quanten-Kryptographie an . 3 Kandidaten für die digitale Signatur und 4 Kandidaten für die asymmetrische Verschlüsselung wurden an die dritte Stufe übergeben. 8 alternative Kandidaten wurden ebenfalls vorgestellt. Ich dachte, dass die Chabrowiten an dieser Veranstaltung interessiert sein würden. Weitere Details unter dem Schnitt.
Ein bisschen Geschichte
Die Idee des Quantencomputers wurde erstmals in den frühen 1980er Jahren vorgeschlagen, um komplexe quantenmechanische Systeme zu simulieren. Es stellte sich bald heraus, dass Quantencomputer für andere Probleme, wie das Faktorisieren von Zahlen und diskreten Logarithmen in einer Gruppe von Punkten auf einer elliptischen Kurve, eine enorme Beschleunigung bieten könnten.
Dies ist zu einem bedeutenden Problem für die Kryptographie geworden, da die Sicherheit gängiger standardisierter Systeme von der Komplexität der Lösung dieser Probleme abhängt.
Trotzdem blieb Quantencomputing lange Zeit nur eine schöne Abstraktion, die technisch nicht realisierbar war. Vor kurzem wurde die Möglichkeit zur Erstellung von Quantencomputern überarbeitet, und dies hat NIST veranlasst, 2016 einen offenen Wettbewerb zur Schaffung neuer Post-Quanten-Standards zu starten. Insbesondere ist NIST daran interessiert, neue Standards für die Verschlüsselung mit öffentlichen Schlüsseln und digitale Signaturen zu schaffen.
69 Teams aus aller Welt haben sich für die Teilnahme am Wettbewerb beworben. Dieses Thema wurde ausführlich behandelt und es gab sogar Beiträge zu Habré. Von den vorgeschlagenen Programmen gingen nur 26 in die zweite Phase über. Und jetzt, am 22. Juli 2020, wurden die Finalisten der zweiten Phase bekannt gegeben, die weitergingen. Es gibt nur noch 4 Kandidaten für die asymmetrische Verschlüsselung und 3 Kandidaten für die digitale Signatur.
Kandidaten, die die dritte Stufe erreicht haben
Die Kandidaten für einen neuen Standard für digitale Post-Quanten-Signaturen sind also:
- CRYSTALS-DILITHIUM - Vertreter der Gitterkryptographie . Es basiert auf der Fiat-Shamir-Schaltung mit Unterbrechungen. Die Kryptoanalyse reduziert sich auf die Lösung der Probleme Module-LWE und Module-SIS. Es hat eine gute Leistung und kann effektiv auf Geräten mit geringen Ressourcen implementiert werden. NIST forderte die Autoren auf, eine Reihe systemweiter Parameter für Sicherheitsstufe 5 hinzuzufügen.
- FALCON — . GPV. SIS NTRU-. . , , .
- Rainbow — . UOV. . - , .
NIST CRYSTALS-DILITHIUM FALCON . , . Rainbow.
:
- Classic McEliece — . 1979 . , . - , Rainbow .
- CRYSTALS-KYBER — . Module-LWE. -. , NIST , Module-LWE — .
- NTRU — . NTRUEncryt, 20 . NTRU, Module-LWE ( ) , .
- SABER — . MLWR (Module-LWE,
). -, CRYSTALS-KYBER.
, — . NIST , (CRYSTALS-KYBER, NTRU, SABER) .
NIST 8 , , .
:
- SPHINCS+ Picnic — . SPHINCS+ -, Picnic NIZK . . , .
- GeMSS — Rainbow, HFE, UOV. . Rainbow.
:
- BIKE — . .
- FrodoKEM — . LWE, Module-LWE ( ). \.
- HQC — . . \.
- NTRU Prime — . .
- SIKE — ( ), . .
In den letzten vier Jahren hat NIST vorgeschlagene Post-Quanten-Schaltkreise aus der ganzen Welt analysiert. Unter den vorgeschlagenen Schemata nehmen Gitterschemata die beherrschende Stellung ein. Aber sie erfordern (wie andere Bereiche auch) detailliertere Studien. NIST plant, in den nächsten 3 Jahren eine detaillierte Analyse der verbleibenden Kandidaten durchzuführen.
Es ist erwähnenswert, dass es weltweit bereits standardisierte Gitterschemata gibt: eins , zwei . Es ist also höchstwahrscheinlich die Kryptographie auf Gittern, die in den kommenden Jahren die üblichen RSA und ECDSA zunehmend verdrängen wird. Gleichzeitig werden andere Lösungen in hochspezialisierten Bereichen beliebt sein.