Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

Diese Arbeit präsentiert eine detaillierte quantenlogische Schaltungsarchitektur für optimierte Punktadditionen auf elliptischen Kurven über Primkörpern, die im Vergleich zu den auf Zero-Knowledge-Beweisen basierenden Ergebnissen von Babbush et al. für secp256k1 eine Reduktion der Toffoli-Gatter-Anzahl um 6,5 % bis 10 % erreicht, während sie lediglich einen marginalen Anstieg des Qubit-Verbrauchs um 1,5 % zur Folge hat.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, ein sehr komplexes Schloss zu knacken. Seit Jahrzehnten wissen Mathematiker, dass eine spezielle Art von „Super-Schlüssel“ (ein Quantencomputer) dieses Schloss fast augenblicklich öffnen und die Sicherheit der meisten Internetverschlüsselungen brechen könnte. Dies ist als Shor-Algorithmus bekannt.

Das Problem ist jedoch, dass der Bau eines solchen Super-Schlüssels unglaublich teuer und schwierig ist. Er erfordert eine enorme Menge an „magischer Energie“ (Quantenressourcen), um zu funktionieren. Das Ziel dieser Arbeit ist es, eine kleinere, effizientere Version dieses Schlüssels zu entwickeln.

Hier ist die Aufschlüsselung dessen, was der Autor, André Schrottenloher, erreicht hat, erklärt durch Alltagsanalogien.

1. Das große Problem: Der schwere Rucksack

Denen Shor-Algorithmus wie beim Wandern auf einen Berg zu stellen, ist so, als müsste man einen schweren Rucksack voller Vorräte (Quantenbits oder „Qubits“) tragen. Um den Gipfel zu erreichen (den Code zu knacken), müssen Sie diesen Rucksack tragen.

• Frühere Versuche: Andere Forscher haben kürzlich einen sehr effizienten Rucksack gebaut, der leichter war als je zuvor. Sie hielten ihre Blaupausen jedoch geheim und nutzten einen „magischen Trick“ (einen Zero-Knowledge-Beweis), um alle davon zu überzeugen, dass der Rucksack leicht sei, ohne ihnen zu zeigen, wie er hergestellt wurde.
• Das Ziel dieser Arbeit: Der Autor wollte einen Rucksack bauen, der genauso leicht ist wie der geheime, aber mit vollständig offenen Blaupausen, damit jeder die Arbeit überprüfen kann.

2. Die Kernaufgabe: Punkte auf einer Kurve hinzufügen

Die Hauptaufgabe des Algorithmus besteht darin, eine spezifische mathematische Operation namens „Punktaddition“ auf einer elliptischen Kurve durchzuführen.

• Die Analogie: Stellen Sie sich vor, Sie gehen auf einem riesigen, gekrümmten Trampolin spazieren. Sie müssen basierend auf einer Reihe von Regeln von einem Ort zum anderen springen. Diesen Sprung perfekt auszuführen, ist schwer.
• Der Engpass: Der schwierigste Teil des Sprungs ist ein spezieller Zug namens „In-Place-Multiplikation“. Es ist, als würde man versuchen, zwei Zahlen miteinander zu multiplizieren, während man nur den Platz nutzen darf, auf dem man gerade steht, ohne zusätzlichen Platz für Notizen zu haben.

3. Die Lösung: Der „Zwei-Schritt-Tanz“

Um das „Kein-Notizpapier-Problem“ zu lösen, wandte der Autor eine clevere Zwei-Schritt-Strategie an (basierend auf einer Methode namens dem erweiterten euklidischen Algorithmus):

• Schritt 1: Das Speicherband (Die Züge aufzeichnen)
  Anstatt die Mathematik direkt durchzuführen und das Ergebnis zu behalten, zeichnet der Computer zuerst einfach nur auf, welche Züge er gemacht hätte, auf einem langen Band aus Bits. Er erledigt die schwere Arbeit noch nicht; er schreibt lediglich die Anweisungen auf. Dieses Band ist überraschend kurz.
• Schritt 2: Die Rekonstruktion (Das Abspielen der Züge)
  Sobald das Band geschrieben ist, spielt der Computer es rückwärts ab. Er nutzt die Anweisungen auf dem Band, um die eigentliche Mathematik mit den Zahlen durchzuführen.
• Warum das hilft: Durch die Trennung von „Planung“ und „Ausführung“ spart der Computer eine enorme Menge an Platz. Es ist, als würde man ein Rezept auf einen Klebezettel schreiben, bevor man mit dem Kochen beginnt, damit man nicht alle Zutaten gleichzeitig in den Händen halten muss.

4. Die Abkürzung: Die „Pseudo-Mersenne“-Primzahl

Die Arbeit konzentriert sich auf eine spezielle Art von Schloss namens secp256k1 (verwendet von Bitcoin). Dieses Schloss hat eine spezielle Form.

• Die Analogie: Stellen Sie sich vor, ein generisches Schloss ist ein perfektes Quadrat. Aber das Bitcoin-Schloss ist ein Quadrat, bei dem eine kleine Ecke abgeschnitten wurde.
• Die Optimierung: Weil die Ecke abgeschnitten ist, ist die Mathematik, die zum Öffnen erforderlich ist, etwas einfacher. Der Autor entwarf spezielle Werkzeuge, die diese „abgeschnittene Ecke“ ausnutzen, um unnötige Schritte zu überspringen.
  • Für ein generisches Schloss (jede beliebige Primzahl) sind die Werkzeuge standardisiert und etwas schwerer.
  • Für das Bitcoin-Schloss (secp256k1) sind die Werkzeuge gestrafft und leichter, weil sie genau wissen, wo die Ecke fehlt.

5. Die Ergebnisse: Ein etwas leichterer Rucksack

Der Autor baute die vollständige „Blaupause“ für diesen neuen Rucksack und testete sie.

• Platz (Qubits): Der neue Rucksack ist etwa 1,5 % schwerer als der geheime Rucksack der anderen Forscher. Das ist ein winziges Opfer.
• Energie (Gates): Der neue Rucksack ist jedoch in Bezug auf die benötigte Energie (Toffoli-Gates) 6,5 % bis 10 % effizienter.
• Zuverlässigkeit: Der Autor hat bewiesen, dass dieser Rucksack genauso zuverlässig funktioniert wie der geheime. Wenn man ihn mit zufälligen Eingaben verwendet, funktioniert er fast jedes Mal, genau wie die geheime Version.

Zusammenfassung

Einfach ausgedrückt sagt diese Arbeit: „Wir haben herausgefunden, wie man den Quantencomputer baut, der benötigt wird, um moderne Verschlüsselungen zu knacken. Wir haben nicht nur geraten; wir haben die genauen Anweisungen aufgeschrieben. Unsere Version ist zwar etwas größer in der Größe, verbraucht aber weniger Energie beim Betrieb als die vorherige ‚geheime‘ Version, und wir haben bewiesen, dass sie sowohl für generische Schlösser als auch für das spezifische Schloss von Bitcoin funktioniert.“

Der Autor betont, dass dies ein logisches Design ist (die theoretische Blaupause). Das bedeutet nicht, dass wir es heute bauen können, aber es sagt uns genau, wie viel „magische Energie“ wir benötigen werden, wenn Quantencomputer schließlich leistungs genug sind, um dies zu versuchen.

Technische Zusammenfassung

Problemstellung
Die Arbeit befasst sich mit der Ressourcenabschätzung von Shors Algorithmus zur Berechnung des elliptischen Kurven-Diskreten-Logarithmus (ECDL), einer primären Bedrohung für die heutige Public-Key-Kryptographie. Während jüngere Arbeiten von Babbush et al. (arXiv 2026) signifikante Reduktionen der Gate- und Qubit-Anzahl für die Kurve secp256k1 demonstrierten, stützten sie sich auf einen Zero-Knowledge-Beweis, um ihre Ergebnisse zu validieren, ohne die zugrunde liegenden logischen Quantenschaltkreise offenzulegen. Dieser Mangel an Transparenz erschwert die Reproduzierbarkeit und unabhängige Verifizierung. Die vorliegende Arbeit zielt darauf ab, eine vollständig detaillierte, reproduzierbare logische Quantenschaltkreisarchitektur bereitzustellen, die eine vergleichbare Effizienz wie die Arbeit von Babbush et al. erreicht und gleichzeitig die Designprinzipien sowie Implementierungsdetails explizit offenlegt.

Methodik
Die Autoren verwenden einen Top-Down-Ansatz, beginnend bei der High-Level-Struktur von Shors Algorithmus und verfeinernd die arithmetischen Komponenten. Der Kern der Optimierung liegt in der Implementierung der Fenstergesteuerten Punktaddition (windowed point addition) auf elliptischen Kurven über Primkörpern.

1. High-Level-Struktur: Der Algorithmus nutzt eine semiklassische Fourier-Transformation mit Qubit-Recycling, um die Punktmultiplikation $|u, v\rangle|0\rangle \to |u, v\rangle|[u]P + [v]Q\rangle$ in eine Sequenz von fenstergesteuerten Punktadditionen zu zerlegen. Punkte werden in affinen Koordinaten dargestellt.
2. Modulare In-Place-Multiplikation: Die kostspieligste Operation bei der Punktaddition ist die In-Place-modulare Multiplikation $|x, y\rangle \to |x, yx \pmod q|$. Die Autoren adaptieren eine Technik aus [14], die den erweiterten euklidischen Algorithmus (EEA) in zwei distinkte Phasen entkoppelt:
   • Euklidischer Algorithmus (Vorwärtsphase): Anstatt Bézout-Koeffizienten direkt zu berechnen, verarbeitet diese Phase die Eingaben $(q, x)$ und gibt einen „Garbage“-Bitvektor aus, der die Sequenz der Operationen (Swaps, Subtraktionen, Divisionen durch 2) kodiert. Dies reduziert die Komplexität des Speicherplatzes.
   • Bézout-Rekonstruktion (Rückwärtsphase): Diese Phase nimmt den Garbage-Bitvektor und wendet die aufgezeichneten Operationen auf ein Paar $(y, 0)$ an, um $|y, yx^{-1} \pmod q\rangle$ zu berechnen. Durch das Rückwärtslaufen oder die Verwendung spezifischer Eingaben erreichen die Autoren gleichzeitig In-Place-Multiplikation und Inversion.
3. Arithmetische Optimierung:
   • Trade-offs zwischen Speicherplatz und Gates: Die Autoren wechseln strategisch zwischen dem CDKM-Adder (geringer Platzbedarf) und dem Gidney-Adder (geringere Gate-Anzahl, höherer Platzbedarf), abhängig von der Verfügbarkeit von Ancilla-Qubits während der verschiedenen Stadien des Algorithmus.
   • Approximative Arithmetik: Um die Gate-Anzahl zu reduzieren, führen die Autoren approximative Arithmetikschaltkreise ein. Vergleiche werden unter Verwendung nur der höchstwertigen Bits (MSBs) statt vollständiger Breitenvergleiche durchgeführt. Dies führt eine Fehlerrate ein, die durch die Optimierung von Konstanten verwaltet wird, um eine hohe Erfolgswahrscheinlichkeit auf Zufallseingaben sicherzustellen (speziell eine Fehlerrate $\le 2^{-13.3}$).
   • Instanzspezifische Optimierung: Für die secp256k1-Kurve, die einen Pseudo-Mersenne-Primzahl verwendet ($q = 2^{256} - 4294968273$), werden die modularen Reduktionsschaltkreise weiter vereinfacht. Die Autoren nutzen den kleinen Unterschied $f$ in der Form $2^u - f$, um teure modulare Subtraktionen durch einfache Bit-Manipulationen und Additionen von $f$ zu ersetzen.

Zentrale Beiträge

• Reproduzierbare Schaltkreisarchitektur: Die Arbeit beschreibt den ersten vollständig spezifizierten logischen Quantenschaltkreis für ECDL auf secp256k1, der die Effizienzansprüche der intransparenten Arbeit von Babbush et al. erfüllt. Der Code ist implementiert und über die Qarton-Bibliothek verfügbar.
• Optimierte Ressourcen-Anzahlen: Die Autoren präsentieren zwei Varianten des Schaltkreises:
  • Platzoptimiert: Verwendet etwa $4.36n + O(\sqrt{n})$ Qubits.
  • Gate-optimiert: Verwendet etwa $4.36n + O(\sqrt{n})$ Qubits, reduziert jedoch die Anzahl der Toffoli-Gates.
• Generische Variante: Eine Version des Schaltkreises wird bereitgestellt, die für jeden Primkörper gültig ist, nicht nur für secp256k1, wenngleich sie aufgrund des Fehlens von Pseudo-Mersenne-Optimierungen eine etwas höhere Gate-Kosten verursacht.
• Detaillierte Kostenanalyse: Die Arbeit liefert eine granulare Aufschlüsselung der Toffoli-Gate-Kosten, wobei zwischen der GCD-Konstruktion, der Bézout-Rekonstruktion und den modularen Arithmetik-Komponenten unterschieden wird.

Ergebnisse
Die Autoren berichten die folgenden Ressourcen-Schätzungen für die Kurve secp256k1 (wobei $n=256$):

• Qubit-Anzahl:
  • Platzoptimierte Variante: 1.192 Qubits (im Vergleich zu 1.175 bei Babbush et al.).
  • Gate-optimierte Variante: 1.446 Qubits (im Vergleich zu 1.425 bei Babbush et al.).
  • Dies entspricht einer leichten Erhöhung der Qubit-Anzahl um etwa 1,5 %.
• Gate-Anzahl (Toffolis):
  • Platzoptimierte Variante: $2^{21.19}$ (ca. $2,3 \times 10^6$).
  • Gate-optimierte Variante: $2^{20.83}$ (ca. $1,8 \times 10^6$).
  • Dies stellt eine Reduktion der Toffoli-Gate-Anzahl um 6,5 % bis 10 % gegenüber Babbush et al. dar.
• Gesamtalgorithmus-Kosten: Für den vollständigen Shor-Algorithmus auf secp256k1 benötigt die gate-optimierte Variante etwa $2^{25.78}$ Toffoli-Gates und 1.462 Qubits. Dies ist eine signifikante Verbesserung gegenüber der vorherigen Arbeit von Litinski (arXiv 2023), die etwa $2^{27.57}$ Toffoli-Gates und doppelt so viele Qubits erforderte.

Bedeutung
Die Arbeit beansprucht ihre Bedeutung primär im Bereich der Reproduzierbarkeit und Transparenz. Durch die Bereitstellung der expliziten logischen Schaltkreisarchitektur ermöglichen die Autoren der kryptographischen Gemeinschaft, die Ressourcen-Schätzungen zum Brechen der elliptischen Kurven-Kryptographie zu verifizieren, die zuvor hinter einem Zero-Knowledge-Beweis verborgen waren. Die Arbeit zeigt, dass eine ähnliche oder leicht verbesserte Effizienz durch explizite Designentscheidungen erreicht werden kann, insbesondere durch die Trennung des EEA in eine Aufzeichnungsphase und eine Rekonstruktionsphase in Kombination mit approximativer Arithmetik. Die Autoren merken an, dass ihre Schaltkreise nicht exakt sind und auf einer hohen Erfolgswahrscheinlichkeit auf Zufallseingaben beruhen – eine Eigenschaft, die sie mit der Arbeit teilen, die sie replizieren. Die Ergebnisse bestätigen, dass die Kosten für das Brechen von secp256k1 niedriger sind als zuvor von einigen logischen Schaltkreismodellen geschätzt, was die Dringlichkeit der Post-Quanten-Migration unterstreicht.