⚛️ quantum physics

Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

Questo articolo presenta un'implementazione di circuito quantistico ottimizzata per i qubit del cifrario ibrido leggero ARX-SPN GFSPX e ne valuta la sicurezza post-quantistica mediante un attacco di Grover parallelizzato, rivelando un costo quantistico totale di $1.12 \times 2^{159}$ porte che, sebbene al di sotto delle soglie di NIST Livello 1, dimostra una resistenza superiore rispetto ad altre progettazioni leggere.

Autori originali: Ibrahim Ulgen (Institute of Applied Mathematics, Middle East Technical University, Ankara/Türkiye, Department of Mathematics, Siirt University, Siirt/Türkiye), Hasan Ozgur Cildiroglu (Physics Departme

Pubblicato 2026-05-28

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Ibrahim Ulgen (Institute of Applied Mathematics, Middle East Technical University, Ankara/Türkiye, Department of Mathematics, Siirt University, Siirt/Türkiye), Hasan Ozgur Cildiroglu (Physics Department, Ankara University, Ankara/Türkiye), Oğuz Yayla (Institute of Applied Mathematics, Middle East Technical University, Ankara/Türkiye)

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di avere una serratura digitale molto speciale e leggera (chiamata GFSPX) progettata per proteggere i dati su dispositivi piccoli come sensori intelligenti o etichette RFID. Questa serratura è costruita per essere veloce e utilizzare pochissima energia, rendendola perfetta per l'"Internet delle Cose".

Tuttavia, sta emergendo un nuovo tipo di "super-strumento" chiamato Computer Quantistico. A differenza dei computer normali che controllano le chiavi una alla volta, un computer quantistico può controllare molte chiavi contemporaneamente, potenzialmente forzando queste serrature molto più velocemente. Questo articolo pone una domanda semplice: Se un computer quantistico tenta di violare questa specifica serratura, quanto sarà effettivamente difficile?

Ecco la sintesi delle loro scoperte utilizzando analogie di tutti i giorni:

1. Il Design della Serratura: Un Motore Ibrido

La serratura GFSPX non è costruita con un solo tipo di meccanismo. È un ibrido, come un'auto che utilizza sia un motore a benzina che un motore elettrico.

La Parte "Benzina" (ARX): Questa utilizza semplici operazioni matematiche (Addizione, Rotazione, XOR) che sono molto efficienti ma possono essere un po' lente nel diffondere le modifiche attraverso i dati.
La Parte "Elettrica" (SPN): Questa utilizza una complessa rete di sostituzione (come mescolare un mazzo di carte) che diffonde le modifiche molto rapidamente.
Il Risultato: Combinandole, la serratura è veloce ed efficiente. Gli autori hanno costruito una pianta digitale di questa serratura specificamente per un computer quantistico per vedere esattamente come funziona all'interno.

2. La Pianta Quantistica: Costruire il Circuito

Per testare la serratura, i ricercatori hanno dovuto costruire un "circuito quantistico". Pensa a questo come alla costruzione di una fabbrica in miniatura e reversibile dove ogni passaggio può essere annullato perfettamente (così nessuna informazione va persa).

La Sfida: I computer quantistici sono fragili. Non puoi semplicemente copiare i dati; devi essere molto attento con i "qubit" (i bit quantistici, come minuscole trottole).
La Soluzione: I ricercatori hanno ottimizzato il design per utilizzare il minor numero possibile di qubit (209 di essi). Hanno usato un trucco intelligente chiamato "sommatore a riporto ripple" per le parti matematiche, che è come una catena di montaggio molto efficiente che non spreca spazio.
L'Impronta: La pianta finale è compatta, richiedendo un "piano di fabbrica" di 209 qubit e un numero specifico di passaggi (porte) per eseguire una singola cifratura completa.

3. L'Attacco: La Ricerca "Grover"

Per violare la serratura, un computer quantistico utilizza l'Algoritmo di Grover.

L'Analogia: Immagina di avere una biblioteca gigantesca con $2^{128}$ $2^{128}$ libri (un numero così enorme che è difficile da comprendere) e solo un libro contiene la chiave corretta.
- Un computer normale è come un bibliotecario che controlla un libro alla volta. Ci vorrebbe un'eternità.
- Un computer quantistico è come un bibliotecario magico che può controllare molti libri simultaneamente. Trova il libro giusto in circa la radice quadrata del tempo.
La Trappola: Per assicurarsi che il computer quantistico non scelga il libro sbagliato (un "falso positivo"), i ricercatori hanno fatto controllare al computer tre serrature diverse (utilizzando tre diverse coppie di messaggi cifrati/decifrati) contemporaneamente. Se una chiave apre tutte e tre, è sicuramente quella giusta.

4. Il Verdetto: Forte, Ma Non "Post-Quantistico"

I ricercatori hanno calcolato il "costo" totale di questo attacco quantistico.

Il Costo: Hanno scoperto che violare la serratura richiederebbe una quantità enorme di potenza di calcolo, approssimativamente equivalente a $1.12 \times 2^{159}$ operazioni.
Lo Standard: Il National Institute of Standards and Technology (NIST) degli Stati Uniti ha fissato un "livello di sicurezza" per il futuro. Per essere considerata veramente sicura contro i computer quantistici (Livello 1 di sicurezza), una serratura deve avere un costo di almeno $2^{170}$ .
Il Risultato: La serratura GFSPX è sotto il livello di sicurezza. Non è abbastanza sicura per gli standard post-quantistici più rigorosi.
- Tuttavia, l'articolo nota che rispetto ad altre serrature leggere, GFSPX è in realtà una delle più difficili da violare. Si trova in un "punto dolce" dove è molto efficiente per dispositivi piccoli ma offre ancora una decente resistenza contro gli attacchi quantistici, anche se non supera il test di sicurezza più alto.

5. La Conclusione

L'articolo conclude che, sebbene questa serratura ibrida sia eccellente per i dispositivi attuali con risorse limitate, la dimensione della chiave di 128 bit è semplicemente troppo piccola per sopravvivere a un attacco quantistico determinato in futuro.

Il Compromesso: Puoi avere una serratura che è piccola e veloce (buona per i sensori di oggi), o una serratura che è enorme e lenta (buona per la sicurezza futura contro i quantistici), ma questo design specifico cerca di fare entrambe le cose e fallisce leggermente sul fronte della "sicurezza futura".
Consiglio Futuro: Per rendere questo design veramente immune ai quantistici, gli autori suggeriscono di rendere la chiave più lunga (come 192 o 256 bit) o di modificare le parti matematiche per renderle ancora più difficili da elaborare per i computer quantistici.

In sintesi: GFSPX è una serratura molto intelligente ed efficiente, più difficile da forzare rispetto alla maggior parte delle sue pari, ma non è abbastanza forte da resistere ai computer quantistici super potenti del futuro senza alcuni aggiornamenti.

Riepilogo Tecnico: Realizzazione di Circuito Quantistico e Crittanalisi di Grover del Cifratore Ibrido ARX-SPN GFSPX

Enunciato del Problema
L'emergere del calcolo quantistico sfida fondamentalmente la sicurezza delle primitive simmetriche a chiave classica. Mentre l'algoritmo di Shor minaccia la crittografia a chiave pubblica, l'algoritmo di Grover fornisce un miglioramento quadratico per la ricerca non strutturata, dimezzando efficacemente il margine di sicurezza delle costruzioni a chiave simmetrica. Di conseguenza, i cifrari a blocchi leggeri (BC), progettati per ambienti con risorse limitate come l'Internet delle Cose (IoT) e la RFID, richiedono una rigorosa rivalutazione della loro resilienza post-quantistica. Nello specifico, vi è la necessità di quantificare le risorse quantistiche richieste per lanciare un attacco di recupero della chiave su design ibridi che combinano i paradigmi Addition-Rotation-XOR (ARX) e Substitution-Permutation Network (SPN).

Metodologia
Gli autori presentano una realizzazione completa di circuito quantistico e una crittanalisi di Grover di GFSPX, un cifratore a blocchi leggero con un blocco dati di 64 bit e una chiave segreta di 128 bit. GFSPX utilizza una Struttura di Feistel Generalizzata (GFS) a 4 rami che integra due blocchi funzionali distinti: una funzione basata su ARX ( $F_1$ ) per la non linearità e una struttura SPN a 32 bit ( $F_2$ ) per una diffusione rapida.

La metodologia procede in tre fasi:

Realizzazione di Circuito Quantistico: La struttura classica di GFSPX è mappata in un circuito quantistico reversibile. Gli autori sfruttano la reversibilità intrinseca della rete di Feistel per minimizzare l'uso di qubit ancilla.
- $F_1$ (ARX): Implementata utilizzando un adder a propagazione di riporto compatto (RCA) basato sull'architettura di Cuccaro et al. Questo approccio minimizza il sovraccarico di qubit omettendo il bit di riporto finale per l'addizione modulare e utilizzando porte in-place Majority (MAJ) e UnMajority-and-Add (UMA).
- $F_2$ (SPN): Il livello S-box (basato su PRESENT) è sintetizzato utilizzando un insieme minimo di porte CNOT e Toffoli senza ancillae aggiuntive. Il livello di permutazione (livello P) è implementato tramite porte SWAP parallelizzabili per mantenere una bassa profondità del circuito.
- Schedulazione delle Chiavi: La schedulazione della chiave maestra a 128 bit è realizzata come un'evoluzione unitaria che coinvolge una rotazione ciclica sinistra di 113 bit, sostituzioni S-box e XOR con il contatore di round, ottimizzata per l'esecuzione in-place.
Stima delle Risorse: Il costo quantistico è calcolato utilizzando metriche di decomposizione standard (costo NOT e CNOT = 1, costo Toffoli = 6). L'analisi valuta sia un costo di base (escludendo il sovraccarico di instradamento SWAP) sia un limite superiore (decomponendo gli SWAP in tre CNOT).
Crittanalisi di Grover: Viene costruito un oracolo di Grover parallelizzato ( $U_f$ ) per valutare il cifratore contro attacchi di recupero della chiave. Per eliminare corrispondenze spurie nello spazio delle chiavi a 128 bit, l'oracolo utilizza tre coppie di testo in chiaro-cifrato ( $r=3$ ). La complessità dell'attacco è stimata moltiplicando le metriche delle risorse dell'oracolo per il numero ottimale di iterazioni di Grover ( $\approx \frac{\pi}{4}2^{64}$ ).

Contributi Chiave

Implementazione Quantistica Ottimizzata: Il documento fornisce un circuito quantistico ottimizzato per i qubit per GFSPX, raggiungendo un ingombro di 209 qubit. Il design raggiunge un costo quantistico di base di 32.498 porte con una profondità del circuito di 7.617.
Analisi dell'Architettura Ibrida: Lo studio dettaglia la distribuzione delle risorse di un design ibrido ARX-SPN, dimostrando che, sebbene il primitivo di addizione modulare domini il conteggio totale delle porte, i livelli di permutazione parallelizzati nel componente SPN aiutano a mantenere un rapporto porta-profondità competitivo.
Valutazione Quantitativa della Sicurezza: Gli autori costruiscono un oracolo di Grover utilizzando tre coppie di testo in chiaro-cifrato e calcolano il costo totale dell'attacco secondo il framework MAXDEPTH del NIST. L'analisi rivela un costo totale dell'attacco quantistico di circa $1.12 \times 2^{159}$ porte per $r=3$ .
Benchmark Comparativo: L'implementazione è confrontata con altri cifrari leggeri (ad esempio PRESENT, GIFT, SIMON, SPECK). GFSPX raggiunge il rapporto costo-profondità più basso (4,27) tra i design confrontati, indicando un'elevata efficienza di esecuzione parallela.

Risultati

Metriche delle Risorse: Il circuito completo GFSPX a 20 round richiede 209 qubit. Il costo di base è 32.498, salendo a 47.789 quando è incluso il sovraccarico di instradamento SWAP. La profondità del circuito è 7.617.
Complessità dell'Attacco: Il costo quantistico totale per un attacco di recupero della chiave è stimato a $1.12 \times 2^{159}$ (per $r=3$ ).
Classificazione della Sicurezza: Secondo il framework di Crittografia Post-Quantistica del NIST, la soglia di sicurezza di Livello 1 (equivalente ad AES-128) richiede un costo totale dell'attacco di almeno $2^{170}$ . Il costo stimato per GFSPX ( $2^{159}$ ) è inferiore a questa soglia.
Compromessi di Design: Sebbene GFSPX dimostri una maggiore resistenza agli attacchi quantistici rispetto a molti design puri SPN (che si raggruppano intorno a $2^{152}$ ), non soddisfa i criteri rigorosi di sicurezza di Livello 1 per una lunghezza di chiave di 128 bit. Il costo del design ibrido è fortemente influenzato dal componente ARX (addizione modulare), collocando il suo profilo di sicurezza più vicino a cifrari basati su ARX come SIMON e SPECK.

Significato
Il documento afferma che i suoi risultati forniscono intuizioni critiche sull'equilibrio tra efficienza hardware classica e resilienza quantistica per i design crittografici di prossima generazione. Lo studio evidenzia un compromesso fondamentale: mentre le costruzioni ibride ARX-SPN offrono prestazioni classiche robuste e una migliore resistenza quantistica rispetto ai design SPN puri, una lunghezza di chiave di 128 bit rimane strutturalmente insufficiente per raggiungere la sicurezza di Livello 1 del NIST contro avversari quantistici avanzati. Gli autori suggeriscono che la ricerca futura dovrebbe concentrarsi sull'estensione delle lunghezze delle chiavi (ad esempio, a 192 o 256 bit) o sull'ottimizzazione dei primitivi reversibili di addizione modulare per migliorare i margini di sicurezza. La metodologia stabilita in questo lavoro funge da quadro rigoroso per valutare altri design ibridi in ambienti con risorse limitate.