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.

• Codifica: Come la strategia sottostante (indice di gruppo)
• Qubit: 2 + n_bit + ancillae (vs 2t + n_bit + ancillae)
• Compromesso: Richiede circuiti dinamici (misura a metà circuito, reset, porte condizionate classicamente). Funziona su IBM Heron r2 fino a 7 bit; a 8 bit+ l'overhead di sincronizzazione del feedback classico supera il budget di tempo QPU

Strategia 6: Addizione Modulare Ripple-Carry (--oracle ripple)

Implementato in ripple_carry_shor.py. Utilizza addizionatori ripple-carry CDKM (Cuccaro et al. 2004) per le addizioni di punto controllate, sostituendo sia le matrici unitarie dense che i circuiti di trasposizione scomposti in cicli.

Nella codifica a indice di gruppo, il punto P = kG è rappresentato dal suo indice k nel gruppo ciclico. Aggiungere S = sG diventa addizione modulare della costante classica s (mod n). L'intuizione chiave: ogni addizione di punto controllata si riduce a una singola addizione modulare controllata di una costante nota, implementata tramite CDKMRippleCarryAdder e IntegerComparator di Qiskit.

L'oracolo consiste in 2m addizioni modulari controllate (m per registro di conteggio), dove ogni addizione modulare controllata esegue:

1. Carica costante nel registro ancilla tramite CX dal qubit di controllo
2. Half-adder CDKM per aggiungere ancilla all'accumulatore (solo porte nearest-neighbor)
3. Comparatore intero per rilevare overflow (acc >= n)
4. Sottrazione condizionale di n tramite addizione controllata dal flag di 2^m1 - n
5. Decomputo del flag tramite sonda basata sul riporto

Nella costruzione del circuito non viene utilizzata alcuna conoscenza della chiave privata d. Gli indici di gruppo per le potenze di G sono calcolati come 2^i mod n (pubblici). Gli indici di gruppo per le potenze di Q sono derivati dall'enumerazione pubblica del gruppo ciclico generato da G — il punto Q viene cercato in questa enumerazione.

• Codifica: Indice di gruppo (0..n-1)
• Qubit: 4m + 5 dove m = ceil(log2(n))
• Porte per addizione: Operazioni CDKM O(m), ciascuna con porte CX O(m)
• Scala totale CX: O(m^3)
• Mappatura hardware: CDKM utilizza solo porte nearest-neighbor, dando ~1x overhead di instradamento sulla topologia heavy-hex di IBM (vs 26-33x per addizionatori basati su QFT)

Confronto

Primitive Aritmetiche QFT

Il codice include elementi costitutivi aritmetici modulari basati su QFT (addizionatori Beauregard/Draper, moltiplicazione modulare quantistico-quantistica, inversa/negazione modulare) come base per una codifica delle coordinate completamente aritmetica a 256 bit. Queste primitive sono state verificate corrette tramite simulazione Statevector per primi fino a p=13.

Risultati

Recuperate con successo chiavi private su hardware IBM Quantum per curve di sfida fino a 17 bit:

Tutte le esecuzioni sono state effettuate sul piano open-instance di IBM Quantum, che concede 10 minuti di calcolo quantistico gratuito al mese. I log completi delle esecuzioni sono nella cartella executions/.

La strategia ripple-carry (Strategia 6) ha permesso un grande salto: da 10 bit (40 qubit, 2M porte) a 17 bit (69 qubit, 112K porte) — un aumento della dimensione della chiave di 7 bit con una riduzione di 18x del conteggio delle porte a due qubit. La struttura di porte nearest-neighbor dell'addizionatore CDKM si mappa efficientemente sulla topologia heavy-hex di IBM, mantenendo l'overhead di instradamento vicino a 1x.

Stima di Fase Semiclassica: Circuiti Dinamici su Hardware IBM

La strategia semiclassica (--oracle google) ha recuperato con successo chiavi a 4 bit, 6 bit e 7 bit utilizzando circuiti dinamici (reset a metà circuito, porte p condizionate classicamente tramite if_test) su processori IBM Heron r2. A 7 bit, il circuito utilizza solo 14 qubit (contro 26 per l'approccio standard a permutazione) producendo conteggi di porte 2Q comparabili dopo la trasposizione.

A 8 bit e oltre, l'approccio semiclassico diventa impraticabile sull'attuale hardware IBM. Sebbene if_else e reset siano supportati su Heron r2 (confermato tramite ispezione del backend target), ogni punto di feedback classico richiede una sincronizzazione completa della QPU — tutti i 156 qubit fisici devono rimanere inattivi mentre il controller classico elabora la condizionale per i ~16 qubit attivi. Con ~295K porte CZ distribuite su 16+ punti di feedback, l'overhead di esecuzione per shot fa superare il budget di tempo QPU. L'approccio standard a permutazione, che esegue lo stesso conteggio di porte come un singolo batch continuo senza circuiti dinamici, completa con successo a questa scala.

Una troncamento approssimato della QFT (parametro max_corrections) riduce il numero di blocchi if_else da O(n^2) a O(n) trattenendo solo le correzioni di fase più vicine k per passo di misura (angoli oltre k contribuiscono < pi/2^{k+1}, sotto il pavimento del rumore hardware). Con max_corrections=1, il circuito a 8 bit ha 16 blocchi if_else — ancora sufficienti a causare timeout su hardware IBM a questo conteggio di porte.

Analisi del Rumore e della Fedeltà

Fedeltà Stimata del Circuito

Assumendo una fedeltà tipica delle porte a due qubit (CX) di IBM Quantum di ~99.5%, la fedeltà stimata del circuito diminuisce esponenzialmente con il conteggio delle porte:

La fedeltà del circuito è calcolata come F ≈ (0.995)^{conteggio_CX}. Per tutto oltre i 4 bit, la fedeltà stimata è astronomicamente piccola — la distribuzione di output è prevalentemente rumore.

Perché Funziona Comunque

Per 8 bit e oltre, ogni shot produce una stringa di bit quasi unica (8.128 risultati unici su 8.192 shot a 8 bit; tutti 20.000 unici a 16 bit e 17 bit). L'output è indistinguibile da un campionamento casuale uniforme a livello di stringa di bit. Eppure l'algoritmo recupera ancora la chiave privata corretta.

L'intuizione chiave è che il post-processing di Shor è robusto al rumore in un modo in cui l'analisi grezza delle stringhe di bit non lo è. Ogni shot produce una tripla di misura (j, k, r). L'estrazione calcola d_cand = (r - j) · k^{-1} mod n e verifica tramite d_cand · G == Q. Solo il vero d supera la verifica EC, quindi anche un singolo candidato corretto tra migliaia di shot rumorosi è sufficiente.

Una tripla puramente casuale (j, k, r) produce il d_cand corretto con probabilità ~1/n. Con S shot, il numero atteso di hit verificati dal solo rumore è ~S/n. A 17 bit (n=65.173, S=20.000), questo dà ~0,3 hit attesi dal rumore — qualsiasi recupero riuscito a questa scala fornisce evidenza di segnale quantistico oltre il pavimento di rumore classico.

Per le curve più piccole dove shot >> n (es., 10 bit con n=547 e 1.024 shot), il pavimento di rumore è ~1.024/547 ≈ 1,9 voti per candidato. Anche una manciata di shot con segnale spinge il d corretto sopra il pavimento di rumore. Questo spiega come l'algoritmo abbia successo nonostante fedeltà del circuito che sembrerebbero rendere il calcolo impossibile.

Segnale Quantistico vs Rumore Classico

A scala giocattolo, il passo di verifica dell'estrazione (d_cand * G == Q) agisce come un filtro che accetta solo il vero d. Ciò significa che anche triple puramente casuali (j, k, r) produrranno candidati validi a un tasso di circa shots / n per esecuzione. Quando shots >> n, il solo rumore casuale può recuperare d con alta probabilità.

Per testare se il circuito quantistico contribuisce con segnale oltre questo pavimento di rumore classico, abbiamo eseguito la sfida a 6 bit (n=31) con solo 8 shot (ben al di sotto dell'ordine del gruppo) 10 volte su ibm_kingston:

Risultato: 4/10 successi (40%) rispetto a una linea di base del rumore classico di ~20% (calcolata tramite simulazione Monte Carlo: 8 stringhe di bit casuali con (r-j)*k_inv mod 31 filtrate tramite verifica). Test binomiale a una coda: P(X >= 4 | n=10, p=0,20) = 0,121, indicando un miglioramento di 2x rispetto al pavimento di rumore. Sebbene non statisticamente significativo singolarmente a p < 0,05 (che richiederebbe 5+ successi), il tasso osservato è coerente con un segnale quantistico che contribuisce approssimativamente 1-2 coppie (j, k) valide aggiuntive per esecuzione oltre quanto fornito dal caso.

Questo risultato si colloca tra il pavimento di rumore classico e il regime teorico di vantaggio quantistico. A dimensioni di curva maggiori dove n >> shots, la linea di base del rumore scende sotto l'1% e qualsiasi recupero riuscito della chiave diventa forte evidenza di calcolo quantistico.

Avvio Rapido```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### Come eseguire

È necessario un account [IBM Quantum](https://quantum.ibm.com/). Inserisci il tuo token API al primo avvio e verrà salvato localmente:```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

Opzioni da riga di comando

Struttura del progetto```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## Riferimenti

- P. Shor, ["Algorithms for Quantum Computation: Discrete Logarithms and Factoring"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["Circuit for Shor's algorithm using 2n+3 qubits"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["A new quantum ripple-carry addition circuit"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["Quantum resource estimates for computing elliptic curve discrete logarithms"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["Semiclassical Fourier Transform for Quantum Computation"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush et al., ["Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## Licenza

Questo progetto è una sottomissione al Q-Day Prize Challenge rilasciata sotto [MIT LICENSE](https://github.com/giancarlolelli/quantum/blob/HEAD/LICENSE)