Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

Problematica
Il documento affronta la stima delle risorse per l'algoritmo di Shor applicato al calcolo dei logaritmi discreti su curve ellittiche (ECDL), una minaccia primaria per l'attuale crittografia a chiave pubblica. Sebbene i lavori recenti di Babbush et al. (arXiv 2026) abbiano dimostrato riduzioni significative nel numero di porte e qubit per la curva secp256k1, essi si sono basati su una prova a conoscenza zero per validare i propri risultati senza rivelare i circuiti quantistici logici sottostanti. Questa mancanza di trasparenza ostacola la riproducibilità e la verifica indipendente. Il presente articolo mira a fornire un'architettura di circuito quantistico logico completamente dettagliata e riproducibile che raggiunga un'efficienza comparabile a quella di Babbush et al., rivelando esplicitamente i principi di progettazione e i dettagli di implementazione.

Metodologia
Gli autori adottano un approccio top-down, partendo dalla struttura di alto livello dell'algoritmo di Shor e raffinando le componenti aritmetiche. Il nucleo dell'ottimizzazione risiede nell'implementazione dell'addizione di punti a finestra (windowed point addition) su curve ellittiche su campi primi.

1. Struttura di Alto Livello: L'algoritmo utilizza una trasformata di Fourier semiclassica con riciclo dei qubit per ridurre la moltiplicazione di punti $|u, v\rangle|0\rangle \to |u, v\rangle|[u]P + [v]Q\rangle$ a una sequenza di addizioni di punti a finestra. I punti sono rappresentati in coordinate affini.
2. Moltiplicazione Modulare In-Place: L'operazione più onerosa nell'addizione di punti è la moltiplicazione modulare in-place $|x, y\rangle \to |x, yx \pmod q|$. Gli autori adattano una tecnica tratta da [14] che scinde l'Algoritmo di Euclide Esteso (EEA) in due fasi distinte:
   • Algoritmo Euclideo (Forward): Invece di calcolare direttamente i coefficienti di Bézout, questa fase elabora gli input $(q, x)$ e produce un vettore di bit "garbage" che codifica la sequenza di operazioni (swap, sottrazioni, divisioni per 2). Ciò riduce la complessità dello spazio.
   • Ricostruzione di Bézout (Backward): Questa fase prende il vettore di bit garbage e applica le operazioni registrate a una coppia $(y, 0)$ per calcolare $|y, yx^{-1} \pmod q\rangle$. Eseguendo l'operazione in modo inverso o con input specifici, gli autori ottengono simultaneamente la moltiplicazione in-place e l'inversione.
3. Ottimizzazione Aritmetica:
   • Trade-off tra Spazio e Porte: Gli autori passano strategicamente tra l'addizionatore CDKM (basso spazio) e l'addizionatore Gidney (basso numero di porte, maggiore spazio) a seconda della disponibilità di qubit ancillari durante le diverse fasi dell'algoritmo.
   • Aritmetica Approssimata: Per ridurre il numero di porte, gli autori introducono circuiti di aritmetica approssimata. I confronti vengono eseguiti utilizzando solo i bit più significativi (MSB) anziché confronti a piena ampiezza. Ciò introduce una probabilità di errore, che viene gestita ottimizzando le costanti per garantire il successo su input casuali con alta probabilità (specificamente, probabilità di fallimento $\le 2^{-13.3}$).
   • Ottimizzazione Specifica per l'Istanza: Per la curva secp256k1, che utilizza un primo pseudo-Mersenne ($q = 2^{256} - 4294968273$), i circuiti di riduzione modulare sono ulteriormente semplificati. Gli autori sfruttano la piccola differenza $f$ nella forma $2^u - f$ per sostituire le costose sottrazioni modulari con semplici manipolazioni di bit e addizioni di $f$.

Contributi Chiave

• Architettura di Circuito Riproducibile: Il documento dettaglia il primo circuito quantistico logico completamente specificato per l'ECDL su secp256k1 che eguaglia le rivendicazioni di efficienza del lavoro opaco di Babbush et al. Il codice è implementato ed è disponibile tramite la libreria Qarton.
• Conteggi delle Risorse Ottimizzati: Gli autori presentano due varianti del circuito:
  • Ottimizzato per lo spazio: Utilizza circa $4.36n + O(\sqrt{n})$ qubit.
  • Ottimizzato per le porte: Utilizza circa $4.36n + O(\sqrt{n})$ qubit, ma riduce il numero di porte Toffoli.
• Variante Generica: Viene fornita una versione del circuito valida per qualsiasi campo primo, non solo per secp256k1, sebbene comporti un costo di porte leggermente superiore a causa della mancanza di ottimizzazioni pseudo-Mersenne.
• Analisi Dettagliata dei Costi: Il documento fornisce una suddivisionione granulare dei costi delle porte Toffoli, distinguendo tra la costruzione del GCD, la ricostruzione di Bézout e le componenti di aritmetica modulare.

Risultati
Gli autori riportano le seguenti stime di risorse per la curva secp256k1 (dove $n=256$):

• Conteggio Qubit:
  • Variante ottimizzata per lo spazio: 1.192 qubit (rispetto ai 1.175 di Babbush et al.).
  • Variante ottimizzata per le porte: 1.446 qubit (rispetto ai 1.425 di Babbush et al.).
  • Ciò rappresenta un lieve incremento di circa l'1,5% nel conteggio dei qubit.
• Conteggio Porte (Toffoli):
  • Variante ottimizzata per lo spazio: $2^{21.19}$ (circa $2,3 \times 10^6$).
  • Variante ottimizzata per le porte: $2^{20.83}$ (circa $1,8 \times 10^6$).
  • Ciò rappresenta una riduzione del 6,5% - 10% nel conteggio delle porte Toffoli rispetto a Babbush et al.
• Costo dell'Algoritmo Completo: Per l'algoritmo di Shor completo su secp256k1, la variante ottimizzata per le porte richiede circa $2^{25.78}$ porte Toffoli e 1.462 qubit. Questo è un miglioramento significativo rispetto al lavoro precedente di Litinski (arXiv 2023), che richiedeva circa $2^{27.57}$ porte Toffoli e il doppio dei qubit.

Significato
Il documento rivendica la propria importanza principalmente nell'ambito di riproducibilità e trasparenza. Fornendo l'architettura esplicita del circuito logico, gli autori permettono alla comunità crittografica di verificare le stime delle risorse per violare la crittografia a curve ellittiche, che prima erano nascoste dietro una prova a conoscenza zero. Il lavoro dimosta che un'efficienza simile o leggermente superiore può essere ottenuta attraverso scelte di progettazione esplicite, nello specifico la separazione dell'EEA in una fase di registrazione e una di ricostruzione, combinata con l'aritmetica approssimata. Gli autori notano che i loro circuiti non sono esatti e si affidano a un'alta probabilità di successo su input casuali, una proprietà condivisa con il lavoro che replicano. I risultati confermano che il costo per violare secp256k1 è inferiore a quanto stimato precedentemente da alcuni modelli di circuiti logici, rafforzando l'urgenza della migrazione post-quantistica.