Shor-Algorithmus für ECDLP — Q-Day-Preis-Einreichung

Quantenlöser für das Problem des diskreten Logarithmus auf elliptischen Kurven (ECDLP), entwickelt für den Q-Day Prize Challenge von Project Eleven. Ziel: Wiederherstellung von ECC-privaten Schlüsseln auf echter Quantenhardware unter Verwendung des Shor-Algorithmus.

• 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 den Ökosystemen .NET, Python, Rust und Cloud. Derzeit als Cloud-GTM-Spezialist tätig, mit Fokus auf Lösungsarchitektur und Vertriebstechnik.

Ansatz

Alle Herausforderungskurven 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. Bereite die Zählregister |j>, |k> in gleichmäßiger Superposition vor (Hadamard)
2. Berechne |j>|k>|jG + kQ> über 2t kontrollierte Punktadditionen (t = num_counting Qubits)
3. Messe das Punktregister, kollabiere es auf ein Gruppenelement R
4. Wende die inverse QFT auf die Zählregister an
5. Messe j, k und extrahiere d aus der Beziehung j + kd = r (mod n)

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

Oracle-Strategien

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

Verwendet für Kurven mit einer Gruppenordnung bis zu etwa 6 Bits. Implementiert in projecteleven.py.

Jede kontrollierte Punktaddition "add S" wird als eine 2^(n+1) x 2^(n+1) Permutationsmatrix dargestellt, die über qc.unitary() angewendet wird. Die Matrix kodiert die vollständige Gruppenaktion: Der obere linke Block ist die Identität (Kontrolle=0), der untere rechte Block permutiert Basiszustände gemäß der Abbildung P -> P+S (Kontrolle=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 Bits undurchführbar 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 bauen, wird jede "add S"-Permutation zykluszerlegt in Transpositionen. Jede Transposition (Tausch zweier Basiszustände |a> <-> |b>) wird implementiert mit:

1. CNOT-Reduktion – CNOTs von einem Pivot-Bit auf alle anderen abweichenden Bits, wodurch die Mehr-Bit-Differenz auf eine Ein-Bit-Differenz reduziert wird
2. Mehrfach kontrolliertes X – Ein MCX-Gatter auf dem Pivot-Bit, konditioniert darauf, dass alle anderen Bits dem Zielmuster entsprechen
3. Rückgängigmachen der CNOTs – 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, statt O(n^2) ohne Ancillas. Jede kontrollierte Addition wird als isolierter Unter-Schaltkreis gebaut und als ein einzelnes undurchsichtiges Gatter angehängt, wodurch quadratisches DAG-Wachstum 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 Quanten-Oracle (--oracle coordinate)

Verfügbar für Kurven bis ~6 Bits. Implementiert in quantum_oracle.py.

Anstatt Punkte als Gruppenindizes zu kodieren, enthält das Quantenregister tatsächliche (x, y)-Feldelementkoordinaten 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, was eine Permutation auf dem Koordinatenregister erzeugt. Diese Permutation wird mit derselben CNOT-Reduktions- + MCX-Infrastruktur wie Strategie 2 in Transpositionen zykluszerlegt.

• 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 Oracle (--oracle arithmetic)

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

Verwendet Koordinatenkodierung (wie Strategie 3) mit QFT-basierten modularen arithmetischen Primitiven als Bausteine auf dem Weg zur vollständig arithmetischen Punktaddition. Die Codebasis enthält getestete Implementierungen von:

• Beauregard modularem Addierer – QFT-basiert (target + constant) mod p mit korrekter Ancilla-Entberechnung
• Quanten-Quanten modularer Multiplikation – |a>|b>|0> -> |a>|b>|a*b mod p> via Shift-and-Add mit expliziter modularer Verdopplung, O(n^3) Gatter
• Modularer Inversen-Permutation – |x> -> |x^{-1} mod p> via Lookup-Tabellen-Transpositionen
• Kontrollierter Quanten-Quanten modularer Addition – Kontrolliert |a> -> |a + b mod p> mit Beauregard-Reduktion

Die arithmetischen Primitive erreichen eine Skalierung von O(n^3) pro Punktaddition gegenüber O(N*n) für den Permutationsansatz. Allerdings haben die QFT-basierten Operationen einen etwa 150x größeren konstanten Faktor, was den arithmetischen Ansatz erst für Kurven oberhalb einer Gruppenordnung von ~20 Bits effizienter macht. Für die aktuellen Herausforderungsgrößen (bis zu 12 Bits) bleibt der permutationsbasierte Addierer schneller und wird standardmäßig verwendet.

Strategie 5: Google Semiclassical Phase Estimation (--oracle google)

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

Ersetzt die zwei 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: Vorbereitung in |+>, Anwendung der kontrollierten Punktaddition, Phasenkorrektur basierend auf allen zuvor gemessenen Bits, dann Messung. Die dynamischen Schaltkreis-Primitive reset + if_test in Qiskit ermöglichen dies auf IBM-Quantenhardware.

Das Oracle für kontrollierte Punktadditionen wird an die vorhandene Infrastruktur delegiert (dichte unitäre für <= 6 Bits, effiziente Permutation für > 6 Bits), sodass die Qubit-Einsparungen ausschließlich aus der Eliminierung der Zählregister stammen.

Kurvengröße	Standard-Qubits	Semiclassical-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)