Algoritmo di Shor per ECDLP — Sottomissione per il Q-Day Prize

Risolutore quantistico per il Problema del Logaritmo Discreto su Curve Ellittiche (ECDLP), sviluppato per la Q-Day Prize Challenge da Project Eleven. Obiettivo: recuperare chiavi private ECC su hardware quantistico reale usando l'algoritmo di Shor.

• Autore: Giancarlo Lelli
• Contatto: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• Background: Tecnologo con oltre 10 anni di esperienza in software enterprise, architettura full-stack e sviluppo cloud-native. Formazione in informatica con esperienza pratica su ecosistemi .NET, Python, Rust e Cloud. Attualmente lavora come Cloud GTM Specialist focalizzato su architettura di soluzioni e vendite tecniche.

Approccio

Tutte le curve della sfida usano y^2 = x^3 + 7 su F_p (a = 0, b = 7), corrispondente alla famiglia secp256k1. Il risolutore implementa la variante a due registri dell'algoritmo di Shor per ECDLP:

1. Preparare i registri di conteggio |j>, |k> in sovrapposizione uniforme (Hadamard)
2. Calcolare |j>|k>|jG + kQ> tramite 2t addizioni di punti controllate (t = num_qubit_conteggio)
3. Misurare il registro del punto, collassandolo in un elemento R del gruppo
4. Applicare la QFT inversa ai registri di conteggio
5. Misurare j, k ed estrarre d dalla relazione j + kd = r (mod n)

La chiave privata d viene recuperata raccogliendo multipli campioni (j, k) che soddisfano la stessa relazione lineare modulo l'ordine del gruppo n. Il risolutore supporta sei strategie di oracle per le addizioni di punti controllate, selezionate automaticamente in base alla dimensione della curva o manualmente tramite --oracle.

Strategie Oracle

Strategia 1: Unitario Denso (predefinita per n_bit <= 6)

Utilizzato per curve con ordine del gruppo fino a ~6 bit. Implementato in projecteleven.py.

Ogni addizione di punto controllata "add S" è rappresentata come una matrice di permutazione 2^(n+1) x 2^(n+1) applicata tramite qc.unitary(). La matrice codifica l'intera azione di gruppo: il blocco in alto a sinistra è identità (controllo=0), il blocco in basso a destra permuta gli stati base secondo la mappa P -> P+S (controllo=1).

• Codifica: Indice di gruppo (0..n-1)
• Memoria: O(2^{2n}) per matrice
• Qubit: 2t + n (due registri di conteggio + registro del punto)
• Limitazione: La decomposizione unitaria di Qiskit è O(4^n), rendendola impraticabile oltre ~6 bit

Strategia 2: Permutazione Efficiente (predefinita per n_bit > 6)

Utilizzato per curve più grandi. Implementato in quantum_arithmetic.py.

Invece di costruire matrici dense, ogni permutazione "add S" viene scomposta in cicli di trasposizioni. Ogni trasposizione (scambio di due stati base |a> <-> |b>) è implementata con:

1. Riduzione CNOT -- CNOT dal bit pivot a tutti gli altri bit differenti, riducendo la differenza multi-bit a una differenza a singolo bit
2. X multi-controllata -- Una porta MCX sul bit pivot, condizionata da tutti gli altri bit che corrispondono al pattern target
3. Annullamento CNOT -- Passo inverso del punto 1 per ripristinare i bit non pivot

L'MCX utilizza decomposizione a catena V con (n-2) qubit ancilla dedicati, ottenendo O(n) porte Toffoli per MCX invece di O(n^2) senza ancilla. Ogni addizione controllata è costruita come un sottocircuito isolato e aggiunta come un'unica porta opaca, evitando la crescita quadratica del DAG in Qiskit.

• Codifica: Indice di gruppo (0..n-1)
• Memoria: O(N) per addizione (N = ordine del gruppo)
• Qubit: 2t + n + (n-2) ancilla
• Porte per addizione: O(N * n)

Strategia 3: Oracle a Coordinate Quantistico (--oracle coordinate)

Disponibile per curve fino a ~6 bit. Implementato in quantum_oracle.py.

Invece di codificare i punti come indici di gruppo, il registro quantistico contiene le coordinate effettive (x, y) come elementi del campo in binario più un flag di identità. Il layout del registro del punto è:

• x_reg: f_bit qubit (f_bit = ceil(log2(p)))
• y_reg: f_bit qubit
• id_flag: 1 qubit (1 = punto all'infinito)

Ogni "add S" controllata viene calcolata dalla formula di addizione EC su tutte le codifiche valide delle coordinate, producendo una permutazione sul registro delle coordinate. Questa permutazione viene scomposta in cicli di trasposizioni usando la stessa infrastruttura di riduzione CNOT + MCX della Strategia 2.

• Codifica: Coordinate (x, y, id_flag)
• Qubit: 2t + 2f_bit + 1 + max(0, 2f_bit - 1) ancilla
• Porte per addizione: O(N * f_bit)

Strategia 4: Oracle Aritmetico (--oracle arithmetic)

Framework per addizione di punti a scala polinomiale. Implementato in quantum_oracle.py e quantum_arithmetic.py.

Utilizza la codifica delle coordinate (come la Strategia 3) con primitive aritmetiche modulari basate su QFT come elementi costitutivi verso un'addizione di punti completamente aritmetica. Il codice include implementazioni testate di:

• Addizionatore modulare di Beauregard -- Basato su QFT (target + costante) mod p con decomputo appropriato delle ancilla
• Moltiplicatore modulare quantistico-quantistico -- |a>|b>|0> -> |a>|b>|a*b mod p> tramite shift-and-add con raddoppio modulare esplicito, porte O(n^3)
• Permutazione di inversa modulare -- |x> -> |x^{-1} mod p> tramite trasposizioni di tabella di lookup
• Addizione modulare controllata quantistico-quantistica -- Controllata |a> -> |a + b mod p> con riduzione di Beauregard

Le primitive aritmetiche raggiungono una scala O(n^3) per addizione di punto rispetto a O(N*n) per l'approccio a permutazione. Tuttavia, le operazioni basate su QFT hanno un fattore costante ~150x maggiore, rendendo l'approccio aritmetico più efficiente solo per curve con ordine del gruppo superiore a ~20 bit. Per le dimensioni attuali delle sfide (fino a 12 bit), l'addizionatore basato su permutazione rimane più veloce ed è usato per default.

Strategia 5: Stima di Fase Semiclassica di Google (--oracle google)

Implementato in google_semiclassical.py. Ispirato dalla tecnica di stima di fase semiclassica con riciclo di qubit di Griffiths & Niu (1996), applicata su larga scala in Babbush et al. (2026) per stime di risorse ECDLP su secp256k1. L'articolo di Babbush et al. è stato pubblicato il 30 marzo 2026.

Sostituisce i due registri di conteggio multi-qubit (j, k) e la QFT inversa bulk con due singoli qubit riciclati e correzioni di fase condizionate classicamente. Ogni bit del registro di conteggio viene elaborato sequenzialmente: preparato in |+>, applicata addizione di punto controllata, correzione di fase basata su tutti i bit precedentemente misurati, quindi misura. Le primitive di circuito dinamico reset + if_test in Qiskit lo rendono possibile su hardware IBM Quantum.

L'oracolo per le addizioni di punto controllate è delegato all'infrastruttura esistente (unitario denso per <= 6 bit, permutazione efficiente per > 6 bit), quindi il risparmio di qubit deriva interamente dall'eliminazione dei registri di conteggio.

Dimensione curva	Qubit standard	Qubit semiclassici	Risparmio	Verificato su hardware
4-bit (n=7)	11	5	55%	Sì
6-bit (n=31)	17	7	59%	Sì
7-bit (n=79)	26 + anc	14	46%	Sì
8-bit (n=139)	25 + anc	10 + anc	60%	No (overhead sync QPU)
10-bit (n=547)	31 + anc	12 + anc	61%	No (overhead sync QPU)