Cycles of supersingular elliptic curves for pairing-based proof systems

In der digitalen Welt ist der Beweis, dass man ein Geheimnis kennt, ohne das Geheimnis selbst preiszugeben, ein mächtiges Werkzeug. Dies ist das Herz der modernen Kryptographie, wo „Beweissysteme“ einen Computer davon überzeugen können, dass eine Berechnung korrekt durchgeführt wurde, ohne dass er die gesamte Berechnung erneut ausführen muss. Damit diese Beweise in der realen Welt nützlich sind, müssen sie kurz und schnell zu überprüfen sein. Eine spezifische Art von Beweis, bekannt als „succinct non-interactive argument“, ist zu einem Eckpfeiler dieser Technologie geworden. Um diese Beweise noch leistungsfähiger zu machen, haben Forscher einen Weg entwickelt, sie zu stapeln, wodurch ein Beweis einen anderen verifizieren kann, was eine Vertrauenskette schafft, die unendlich wachsen kann. Dieser Prozess, genannt Rekursion, ist der Motor hinter einigen der fortschrittlichsten Technologien für Privatsphäre und Skalierbarkeit, die heute im Einsatz sind. Das Bauen dieser Ketten erfordert jedoch eine sehr spezifische Art von mathematischem Fundament: Paare von elliptischen Kurven, die wie Puzzleteile perfekt zusammenpassen. Jahrelang waren die einzigen bekannten Puzzleteile, die dieser Beschreibung entsprachen, selten, schwer zu finden und in ihrer Anzahl begrenzt, was einen Flaschenhals für diese Technologie darstellte.

Ein Team von Forschern hat nun einen neuen Weg entdeckt, um diese essenziellen Kurvenpaare zu generieren, was eine riesige, bisher unzugängliche Versorgung freischaltet. Sie fanden heraus, dass sie durch die Verwendung einer anderen Klasse mathematischer Objekte, genannt „supersinguläre Kurven“, eine unendliche Familie dieser Puzzleteil-Paare konstruieren können. Im Gegensatz zur bisherigen Methode, die auf einem engen Satz von Bedingungen beruhte, die das Finden neuer Paare zu einer Frage des Glücks und immenser Rechenleistung machte, funktioniert dieser neue Ansatz zuverlässig für fast jede gewählte Zahl. Die Forscher demonstrierten, dass sie diese neuen Zyklen bauen und sie mit anderen effizienten Kurven zu dem verbinden können, was sie „Lollipops“ nennen. Diese Strukturen ermöglichen es, dass die anfängliche, schwere Arbeit eines Beweises auf einem kleinen, schnellen Feld stattfindet, während das rekursive Stapeln auf dem größeren, sicheren Zyklus erfolgt. In einer praktischen Suche konstruierten sie erfolgreich achtzehn verschiedene Beispiele dieser neuen Strukturen, die als flexible und reichhaltige Ressource für die nächste Generation sicherer digitaler Systeme dienen.

Der Weg zu dieser Entdeckung begann mit einer Einschränkung der bestehenden Technologie. Der aktuelle Standard für diese rekursiven Beweissysteme beruht auf einer spezifischen Anordnung von zwei elliptischen Kurven, die oft als „Zyklus“ bezeichnet werden. In dieser Anordnung entspricht die Anzahl der Punkte auf der ersten Kurve der Größe des Feldes, das die zweite Kurve definiert, und umgekehrt. Dieses empfindliche Gleichgewicht ermöglicht es dem Beweis, nahtlos von einer Kurve zur anderen überzugehen. Über ein Jahrzehnt lang war der einzige bekannte Weg, solche Zyklen zu bauen, die Verwendung von „gewöhnlichen“ Kurven, eine Methode, die von Miyaji, Nakabayashi und Takano entwickelt wurde. Während diese Methode in der Theorie funktioniert, ist sie in der Praxis extrem spärlich. Das Finden eines neuen Paares erfordert das Lösen komplexer mathematischer Gleichungen, bei denen die Zahlen genau richtig sein müssen. Mit wachsenden Sicherheitsanforderungen sinkt die Wahrscheinlichkeit, zufällig auf ein gültiges Paar zu stoßen, gegen Null. Es ist, als versuche man, ein bestimmtes Sandkorn an einem Strand zu finden, das eine präzise Menge an Kriterien erfüllt; der Strand ist unendlich, aber die richtigen Körner sind verschwindend selten. Diese Knappheit zwang Entwickler dazu, entweder ältere, weniger sichere Parameter zu verwenden oder das Ideal der unbegrenzten Rekursion auf kürzere, begrenzte Ketten zu beschränken.

Die Forscher erkannten, dass der Engpass nicht das Konzept des Zyklus selbst war, sondern die spezifische Art der verwendeten Kurve. Sie wandten ihre Aufmerksamkeit den „supersingulären“ Kurven zu. Dies ist eine andere mathematische Variante, die, obwohl sie in der Standardkryptographie weniger verbreitet ist, einzigartige Eigenschaften besitzt, die sie ideal für diese spezifische Aufgabe machen. Der Kompromiss besteht darin, dass diese Kurven über etwas größere mathematische Felder definiert werden müssen, was einige Berechnungen etwas schwerfälliger macht. Der Vorteil ist jedoch überwältigend: Der neue Konstruktionsansatz funktioniert für fast jede gewählte Zahl, sofern sie einen grundlegenden Primzahltest besteht. Es ist nicht nötig, nach seltenen, glücklichen Zahlen zu suchen. Die Forscher zeigten, dass sie für jede gültige Zahl sofort ein funktionierendes Paar von supersingulären Kurven generieren können. Dies verwandelt das Problem von einer Schatzsuche in einen Herstellungsprozess. Anstatt nur einige wenige verstreute Beispiele zu finden, können sie nun eine unendliche Anzahl dieser Zyklen auf Abruf produzieren.

Um zu beweisen, dass dieses Konzept in der realen Welt funktioniert, verließ sich das Team nicht nur auf die Theorie; sie bauten eine Suchmaschine, um konkrete Beispiele zu finden. Sie begaben sich auf die Konstruktion dessen, was sie „Lollipops“ nennen. Stellen Sie sich einen Zuckerstiel vor, bei dem der Stab eine Kette von effizienten Kurven ist und der runde Teil oben der rekursive Zyklus. Der Stab ermöglicht es, dass der Beweis auf einem kleinen, schnellen Feld beginnt, was die ersten Schritte der Berechnung sehr schnell macht. Der runde Teil, der Zyklus, ermöglicht es, dass der Beweis ohne Limit gestapelt und rekursiv verifiziert werden kann. Die Forscher entwickelten einen Algorithmus, um diese Strukturen zu finden, indem sie ein spezifisches Typus von Zahlenrätsel lösten, das als Pell-Gleichung bekannt ist. Sie ließen diesen Algorithmus auf leistungsstarken Computern laufen und suchten durch Millionen von Möglichkeiten. Die Suche war erfolgreich. Sie fanden achtzehn verschiedene Beispiele dieser Lollipops, die in ihrer Größe variieren, um Sicherheitsstufen von 80 Bit bis hin zu 128 Bit und darüber hinaus zu unterstützen. Eines ihrer Beispiele, eine große Instanz mit einem 956-Bit-Feld, sprengte sogar die Grenzen des praktischen Interesses und zeigte, dass diese Strukturen skalierbar sind, um zukünftige Sicherheitsbedarfe zu decken.

Die Bedeutung dieser Erkenntnisse liegt in der Flexibilität, die sie Systemdesignern bieten. Mit der alten Methode waren Designer gezwungen, einen spezifischen, oft ineffizienten Satz von Parametern zu verwenden, weil keine anderen Optionen existierten. Wenn sie höhere Sicherheit wollten, mussten sie eine langsamere Performance oder kleinere Rekursionslimits akzeptieren. Mit den neuen supersingulären Zyklen können Designer Parameter wählen, die auf Geschwindigkeit optimiert sind, wie zum Beispiel Felder, in denen die Mathematik besonders schnell zu berechnen ist, oder Felder, die spezifische Eigenschaften für die Hardwarebeschleunigung besitzen. Sie können auch wählen, diese Zyklen mit anderen Arten von Kurven zu verbinden, die nicht „pairing-friendly“ sind, aber extrem effizient für die ersten Schritte eines Beweises sind. Diese Fähigkeit, Komponenten mischen und kombinieren zu können, um einen maßgeschneiderten „Lollipop“ für eine spezifische Anwendung zu erstellen, war mit der bisherigen Technologie unmöglich. Die Forscher merkten an, dass die neuen Kurven in einigen Teilen zwar etwas größer sind, die Fähigkeit, den Rest des Systems zu optimieren, und die schiere Fülle an verfügbaren Zyklen den Kompromiss jedoch lohnenswert machen.

Das Paper schließt mit der Betonung, dass dies ein konstruktiver Durchbruch ist. Die Forscher haben nicht nur bewiesen, dass diese Zyklen existieren, sondern auch die Werkzeuge bereitgestellt, um sie zu bauen, sowie einen Katalog von achtzehn funktionierenden Beispielen geliefert. Sie räumen ein, dass der nächste Schritt darin besteht, diese neuen Zyklen in tatsächlicher Software zu implementieren, um die genauen Leistungsgewinne zu messen, da die theoretischen Vorteile gegen die praktischen Kosten der größeren Felder abgewogen werden müssen. Doch die Tür steht nun offen. Die Knappheit, die einst das Wachstum rekursiver Beweissysteme einschränkte, wurde beseitigt. Durch den Wechsel von gewöhnlichen zu supersingulären Kurven haben die Forscher eine neue, unendliche Versorgung mit den mathematischen Bausteinen bereitgestellt, die benötigt werden, um die digitale Zukunft zu sichern, und ermöglichen so Beweissysteme, die nicht nur sicherer, sondern auch besser an die vielfältigen Bedürfnisse der realen Welt anpassbar sind.