Shor-Algorithmus für ECDLP — Q-Day-Preisbeitrag

Quanten-Löser für das Diskrete-Logarithmus-Problem elliptischer Kurven (ECDLP), entwickelt für die Q-Day-Preis-Challenge von Project Eleven. Ziel: ECC-Private-Keys auf echter Quantenhardware mithilfe des Shor-Algorithmus wiederherstellen.

• Autor: Giancarlo Lelli
• Kontakt: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• Hintergrund: Technologieführer mit über 10 Jahren Erfahrung in Unternehmenssoftware, Full-Stack-Architektur und Cloud-nativer Entwicklung. Hintergrund in Informatik mit praktischer Erfahrung in .NET, Python, Rust und Cloud-Ökosystemen. Derzeit als Cloud-GTM-Spezialist tätig, mit Schwerpunkt auf Lösungsarchitektur und Vertriebstechnik.

Ansatz

Alle Challenge-Kurven verwenden y^2 = x^3 + 7 über F_p (a = 0, b = 7), entsprechend der secp256k1-Familie. Der Löser implementiert die Zwei-Register-Variante des Shor-Algorithmus für ECDLP:

1. Vorbereiten der Zählregister |j>, |k> in gleichmäßiger Superposition (Hadamard)
2. Berechnen von |j>|k>|jG + kQ> mittels 2t kontrollierten Punktadditionen (t = Anzahl der Zähl-Qubits)
3. Messen des Punktregisters, das auf ein Gruppenelement R kollabiert
4. Anwenden der inversen QFT auf die Zählregister
5. Messen von j, k und Extrahieren von d aus der Beziehung j + kd = r (mod n)

Der private Schlüssel d wird durch Sammeln mehrerer (j, k)-Stichproben wiedergewonnen, die dieselbe lineare Beziehung modulo der Gruppenordnung n erfüllen. Der Löser unterstützt sechs Orakelstrategien für die kontrollierten Punktadditionen, die je nach Kurvengröße automatisch oder manuell über --oracle ausgewählt werden.

Orakelstrategien

Strategie 1: Dichte unitäre Matrix (Standard für n_bits <= 6)

Verwendet für Kurven mit Gruppenordnung bis ca. 6 Bit. Implementiert in projecteleven.py.

Jede kontrollierte Punktaddition "Add S" wird als 2^(n+1) x 2^(n+1)-Permutationsmatrix dargestellt, die mittels qc.unitary() angewendet wird. Die Matrix kodiert die vollständige Gruppenaktion: der obere linke Block ist die Identität (Steuerung=0), der untere rechte Block permutiert Basiszustände gemäß der Abbildung P -> P+S (Steuerung=1).

• Kodierung: Gruppenindex (0..n-1)
• Speicher: O(2^{2n}) pro Matrix
• Qubits: 2t + n (zwei Zählregister + Punktregister)
• Einschränkung: Qiskits unitäre Zerlegung ist O(4^n), was dies jenseits von ~6 Bit unpraktikabel macht

Strategie 2: Effiziente Permutationszerlegung (Standard für n_bits > 6)

Verwendet für größere Kurven. Implementiert in quantum_arithmetic.py.

Anstatt dichte Matrizen zu erstellen, wird jede "Add S"-Permutation in Transpositionen zyklisch zerlegt. Jede Transposition (Vertauschung zweier Basiszustände |a> <-> |b>) wird implementiert mit:

1. CNOT-Reduktion – CNOTs von einem Pivot-Bit zu allen anderen abweichenden Bits, wodurch die Mehrbit-Differenz auf eine Ein-Bit-Differenz reduziert wird
2. Multi-kontrolliertes X – Ein MCX-Gatter auf dem Pivot-Bit, konditioniert darauf, dass alle anderen Bits dem Zielmuster entsprechen
3. CNOTs rückgängig machen – Schritt 1 umkehren, um die Nicht-Pivot-Bits wiederherzustellen

Das MCX verwendet eine V-Ketten-Zerlegung mit (n-2) dedizierten Ancilla-Qubits, was O(n) Toffoli-Gatter pro MCX ergibt anstelle von O(n^2) ohne Ancillas. Jede kontrollierte Addition wird als isolierter Subschaltkreis aufgebaut und als einzelnes undurchsichtiges Gatter angehängt, wodurch ein quadratisches Wachstum des DAG in Qiskit vermieden wird.

• Kodierung: Gruppenindex (0..n-1)
• Speicher: O(N) pro Addition (N = Gruppenordnung)
• Qubits: 2t + n + (n-2) Ancillas
• Gatter pro Addition: O(N * n)

Strategie 3: Koordinatenbasiertes Quantenorakel (--oracle coordinate)

Verfügbar für Kurven bis ca. 6 Bit. Implementiert in quantum_oracle.py.

Anstatt Punkte als Gruppenindizes zu kodieren, hält das Quantenregister tatsächliche (x, y)-Feld-Element-Koordinaten in Binärform plus ein Identitäts-Flag. Das Punktregister-Layout ist:

• x_reg: f_bits Qubits (f_bits = ceil(log2(p)))
• y_reg: f_bits Qubits
• id_flag: 1 Qubit (1 = Punkt im Unendlichen)

Jede kontrollierte "Add S" wird aus der EC-Additionsformel über alle gültigen Koordinatenkodierungen berechnet und erzeugt eine Permutation auf dem Koordinatenregister. Diese Permutation wird mit derselben CNOT-Reduktions- + MCX-Infrastruktur wie Strategie 2 in Transpositionen zerlegt.

• Kodierung: (x, y, id_flag)-Koordinaten
• Qubits: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) Ancillas
• Gatter pro Addition: O(N * f_bits)

Strategie 4: Arithmetisches Orakel (--oracle arithmetic)

Framework für polynomiell skalierende Punktaddition. Implementiert in quantum_oracle.py und quantum_arithmetic.py.

Verwendet Koordinatenkodierung (wie Strategie 3) mit QFT-basierten modularen arithmetischen Primitiven als Bausteine für eine vollständig arithmetische Punktaddition. Die Codebasis enthält getestete Implementierungen von:

• Beauregard-Modular-Adder – QFT-basiert (target + constant) mod p mit ordnungsgemäßer Ancilla-Entberechnung
• Quanten-Quanten-Modular-Multiplikation – |a>|b>|0> -> |a>|b>|a*b mod p> mittels Shift-and-Add mit expliziter modularer Verdopplung, O(n^3) Gatter
• Modulare Inverse-Permutation – |x> -> |x^{-1} mod p> mittels Lookup-Tabellen-Transpositionen
• Kontrollierte Quanten-Quanten-Modular-Add – Kontrolliertes |a> -> |a + b mod p> mit Beauregard-Reduktion

Die arithmetischen Primitiven erreichen O(n^3)-Skalierung pro Punktaddition im Vergleich zu O(N*n) für den Permutationsansatz. Die QFT-basierten Operationen haben jedoch einen ~150x größeren konstanten Faktor, wodurch der arithmetische Ansatz nur für Kurven mit mehr als ~20-Bit-Gruppenordnung effizienter wird. Für aktuelle Challenge-Größen (bis zu 12 Bit) bleibt der permutionsbasierte Addierer schneller und wird standardmäßig verwendet.

Strategie 5: Google Semiklassische Phasenschätzung (--oracle google)

Implementiert in google_semiclassical.py. Inspiriert von der Qubit-Recycling-Phasenschätzungstechnik von Griffiths & Niu (1996), angewandt im großen Maßstab in Babbush et al. (2026) für secp256k1 ECDLP-Ressourcenabschätzungen. Das Papier von Babbush et al. wurde am 30. März 2026 veröffentlicht.

Ersetzt die beiden Multi-Qubit-Zählregister (j, k) und die Bulk-Inverse-QFT durch zwei einzelne recycelte Qubits und klassisch konditionierte Phasenkorrekturen. Jedes Bit des Zählregisters wird sequentiell verarbeitet: in |+> vorbereiten, kontrollierte Punktaddition anwenden, Phase basierend auf allen zuvor gemessenen Bits korrigieren, dann messen. Die reset- und if_test-Dynamic-Circuit-Primitive in Qiskit ermöglichen dies auf IBM Quantum-Hardware.

Das Orakel für kontrollierte Punktadditionen wird an die bestehende Infrastruktur delegiert (dichte unitäre für <= 6 Bit, effiziente Permutation für > 6 Bit), sodass die Qubit-Einsparungen vollständig aus der Eliminierung der Zählregister stammen.

Kurvengröße	Standard-Qubits	Semiklassische Qubits	Einsparung	Hardware-verifiziert
4-Bit (n=7)	11	5	55%	Ja
6-Bit (n=31)	17	7	59%	Ja
7-Bit (n=79)	26 + Anc	14	46%	Ja
8-Bit (n=139)	25 + Anc	10 + Anc	60%	Nein (QPU-Sync-Overhead)
10-Bit (n=547)	31 + Anc	12 + Anc	61%	Nein (QPU-Sync-Overhead)

• Kodierung: Wie zugrunde liegende Strategie (Gruppenindex)
• Qubits: 2 + n_bits + Ancillas (vs. 2t + n_bits + Ancillas)
• Abwägung: Erfordert dynamische Schaltungen (Mid-Circuit-Messung, Reset, klassisch konditionierte Gatter). Funktioniert auf IBM Heron r2 bis zu 7 Bit; bei 8 Bit+ übersteigt der klassische Feedback-Synchronisations-Overhead das QPU-Zeitbudget