POKEx: Performance analysis of POKE-key exchange and SIDH-variants

Stellen Sie sich das Internet als eine riesige, geschäftige Stadt vor, in der jeder geheime Briefe an einander sendet. Um diese Briefe vor Dieben zu schützen, verwenden wir „Schlösser“ namens Verschlüsselung. Jahrzehntelang waren die besten Schlösser aus mathematischen Problemen gefertigt, die auf einem Weg leicht zu lösen, aber in die entgegengesetzte Richtung unglaublich schwer rückgängig zu machen sind, wie das Mischen von Farben. Experten sind jedoch besorgt, dass superstarke Computer (genannt Quantencomputer) in der Zukunft in der Lage sein werden, diese Schlösser sofort zu knacken, wodurch unsere Geheimnisse weit offen lägen. Um dies zu verhindern, entwickeln Forscher neue Schlösser, die auf einem seltsamen und wunderschönen Zweig der Mathematik namens „Isogenien“ basieren. Denken Sie bei Isogenien an eine spezielle Art von Brücke, die verschiedene Formen (mathematische Kurven) miteinander verbindet. Das Geheimnis des Schlosses ist der spezifische Pfad, den man über die Brücke nimmt. Lange Zeit war das populärste Brückendesign namens SIDH. Es war berühmt dafür, dass die Schlösser winzig und schnell waren, was es zu einem Top-Kandidaten für den Schutz unserer digitalen Zukunft machte.

Doch dann, im Jahr 2023, entdeckte ein Paar Forscher einen cleveren Trick, um die SIDH-Brücke zu knacken. Sie fanden heraus, dass die Brückenkonstrukteure versehentlich eine Karte des Pfades sichtbar gelassen hatten, die für jeden einsehbar war, sodass man die geheime Route in Sekundenschnelle herausfinden konnte. Dies war ein schwerer Schlag, da es bedeutete, dass das vielversprechendste „quantensichere“ Schloss tatsächlich gebrochen war. Seitdem versuchen Wissenschaftler verzweifelt, neue Brücken zu bauen, die die Karte besser verbergen. Einige versuchten, die Karte mit einer Decke abzudecken (Maskierung), während andere versuchten, die Brücke aus anderen Materialien zu bauen. Die große Frage blieb: Können wir eine Brücke bauen, die sowohl unknackbar als auch schnell genug ist, um in der realen Welt genutzt zu werden?

Dieses Papier mit dem Titel „POKEx“ tritt in diese chaotische Baustelle ein, um ein neues, glänzendes Brückendesign namens POKÉ zu testen. Die Autoren, Hyeonhak Kim und Suhri Kim, entschieden sich, die POKÉ-Verschlüsselungsmethode in ein vollständiges Schlüsselaustausch-System (das sie POKEx nennen) zu verwandeln und es gegen die anderen Top-Kontender anzutreten zu lassen, die versuchen, die gebrochene SIDH-Brücke zu reparieren. Sie haben nicht nur geraten; sie bauten funktionierende Versionen dieser Systeme und maßen deren Zeit auf einem leistungsstarken Computer. Ihr Hauptergebnis ist, dass POKEx derzeit die schnellste und effizienteste aller isogeniebasierten Brücken ist. In ihren Tests war es etwa 21 Mal schneller als die nächstbeste Alternative (terSIDH) und fast 65 Mal schneller als ein anderes populäres Design (CSIDH). Obwohl es immer noch langsamer ist als einige andere Arten von quantensicheren Schlössern, macht seine Geschwindigkeit und winzige Größe es zu einem sehr vielversprechenden Kandidaten für die Zukunft, der einen Weg bietet, unsere digitalen Geheimnisse zu schützen, ohne das Internet auszubremsen.

Die Geschichte der gebrochenen Brücke und der neuen Lösung

Um zu verstehen, warum dieses Papier wichtig ist, müssen wir zuerst das „Brückenproblem“ betrachten. In der Welt der Kryptografie ist ein „Schlüsselaustausch“ wie zwei Personen, die sich auf ein geheimes Passwort einigen, ohne es jemals laut auszusprechen. Lange Zeit war das SIDH-System der Star der Szene. Es verwendete supersinguläre elliptische Kurven – denken Sie an diese als komplexe, gewundene Formen in einem mathematischen Universum. Die Magie von SIDH lag darin, dass es „Torsionspunkte“ verwendete – das sind wie spezifische Orientierungspunkte auf diesen Kurven –, um die Brücke zu bauen. Das System war so effizient, dass es kleine Schlüssel (das digitale Äquivalent eines winzigen, leichten Schlosses) hatte und sehr schnell war.

Das SIDH-Brückendesign hatte jedoch einen fatalen Fehler. Um die Brücke zu bauen, musste das System einige Informationen über die Orientierungspunkte (Torsionspunkte) veröffentlichen, die es verwendete. Im Jahr 2023 fanden Castryck und Decru einen Weg, diese veröffentlichten Orientierungspunkte kombiniert mit einem cleveren mathematischen Trick namens „Kani’s Glue-and-Split“ zu nutzen, um den geheimen Pfad zu rekonstruieren. Es war, als hätte man eine Spur aus Brotkrumen hinterlassen, die direkt zum Schatz führt. Sobald dieser Angriff entdeckt wurde, galt SIDH als gebrochen und wurde von der Liste der Kandidaten für die Sicherheit des Internets gestrichen.

Das Rennen zur Reparatur der Brücke

Nach dem Fall von SIDH gab die Kryptografie-Gemeinschaft nicht auf. Sie begannen, neue Brücken zu bauen, um es zu ersetken. Einige versuchten, die Orientierungspunkte zu verbergen, indem sie sie mit zufälligem Rauschen bedeckten (eine Methode namens M-SIDH). Andere versuchten, die Form der Brücke komplett zu ändern, indem sie „künstliche Orientierung“ (terSIDH) verwendeten. Es gab auch CSIDH, eine andere Art von Brücke, die nicht von demselben Angriff betroffen war, aber ihre eigenen Geschwindigkeitskomplikationen hatte.

Das Problem war, dass diese neuen Brücken entweder zu langsam oder zu groß waren. Das Abdecken der Orientierungspunkte mit Rauschen erforderte viel größere Zahlen, um sicher zu bleiben, was die Schlösser schwerfällig und langsam in der Anwendung machte. Das Ändern der Brückenform (terSIDH) half zwar, aber es gab immer noch Schwankungen in der Geschwindigkeit, die gefährlich sein konnten. Die Gemeinschaft benötigte eine Lösung, die sowohl sicher als auch schnell ist.

Hier kommt POKEx: Der Geschwindigkeitsdämon

Hier tritt der neue Held des Papers, POKEx, auf den Plan. POKEx basiert auf einem Schema namens POKÉ, das kürzlich von Basso und Maino vorgeschlagen wurde. Die Autoren dieses Papers nahmen POKÉ und verwandelten es in ein vollständiges Schlüsselaustausch-System, inklusive aller notwendigen Schritte, um Schlüssel zu generieren und Geheimnisse sicher auszutauschen.

Das Geheimrezept von POKEx ist die Art und Weise, wie es mit den „Orientierungspunkten“ umgeht. Anstatt nur eindimensionale Pfade wie das alte SIDH zu verwenden, nutzt POKEx eine „zweidimensionale Repräsentation“. Stellen Sie sich vor, Sie versuchen, einen Fluss zu überqueren. SIDH war wie das Gehen auf einem einzelnen Brett. Wenn jemand sah, wo Sie auftraten, konnte er Ihren Pfad bestimmen. POKEx hingegen ist wie das Gehen auf einem Gitter aus Brettern, auf dem Sie sich gleichzeitig in zwei Richtungen bewegen können. Dies macht den Pfad viel schwerer zu erraten. Darüber hinaus verwendet POKEx eine spezielle Art von mathematischem Feld (eine Primzahl der Form $2^a3^b5^c-1$), die sehr schnelle Berechnungen ermöglicht, im Gegensatz zu den anderen neuen Brücken, die viel größere, langsamere Zahlen verwenden mussten.

Das große Duell: Was die Zahlen sagen

Die Autoren haben nicht nur über POKEx gesprochen; sie haben es getestet. Sie entwickelten eine Software, um PokEx neben den anderen Top-Kontendern: M-SIDH, terSIDH und CSIDH laufen zu lassen. Sie setzten sie alle auf das gleiche Sicherheitsniveau (NIST Security Level 1, der Standard zum Schutz streng geheimer Regierungsdaten) und maßen die Zeit, die für den Austausch eines Schlüssels benötigt wurde.

Die Ergebnisse waren beeindruckend.

• M-SIDH war das langsamste der Gruppe und benötigte fast 190 Sekunden für das, was POKEx in einem Bruchteil einer Sekunde erledigte. Die Autoren merkten an, dass dies M-SIDH für den praktischen Einsatz unbrauchbar macht.
• terSIDH war viel schneller als M-SIDH, dauerte aber immer noch etwa 6,5 Sekunden.
• CSIDH benötigte etwa 20 Sekunden.
• POKEx hingegen schloss den Job in nur 306,95 Millisekunden (etwa 0,3 Sekunden) ab.

Um dies in Perspektive zu setzen: POKEx war 21,21 Mal schneller als terSIDH und 64,97 Mal schneller als CSIDH. Dies macht POKEx zum aktuellen Champion des isogeniebasierten Schlüsselaustauschs.

Ist es perfekt?

Das Papier ist vorsichtig damit, dies als „perfekte“ Lösung zu bezeichnen. Obwohl POKEx das Schnellste unter den Isogenie-Brücken ist, ist es immer noch viel langsamer als andere Arten von quantensicheren Schlössern, wie etwa ML-KEM (das im Test nur 0,10 Millisekunden benötigte). Die Autoren weisen jedoch auf einen entscheidenden Kompromiss hin. ML-KEM ist schnell, aber seine „Schlösser“ (Public Keys und Ciphertexts) sind riesig und nehmen viel Platz im Internet ein. POKEx hingegen hat sehr kleine Schlüssel (nur 324 Bytes für den Public Key), was bedeutet, dass es weniger Bandbreite verbraucht. In einer Welt, in der Internetgeschwindigkeit und Datenlimits wichtig sind, ist diese geringe Größe ein massiver Vorteil.

Das Fazit

Dieses Papier zeigt, dass obwohl die alte SIDH-Brücke gebrochen ist, der Weg zu einer neuen, sicheren Brücke offen steht. POKEx ist derzeit der vielversprechendste Kandidat in der Isogenie-Familie und bietet eine seltene Kombination aus hoher Geschwindigkeit und geringer Größe. Es beweist, dass wir quantenresistente Schlösser bauen können, die unser digitales Leben nicht ausbremsen. Während es noch Arbeit benötigt, um bei der Geschwindigkeit anderer quantensicherer Methoden aufzuschließen, deutet seine Effizienz darauf hin, dass es ein wichtiges Werkzeug werden könnte, um unser zukünftiges Internet sicher zu halten – insbesondere in Situationen, in denen das Sparen von Datenspeicherplatz genauso wichtig ist wie das Sparen von Zeit.