💻 computer science

Quantum Cryptanalysis on IBM Quantum Hardware: Extending Even--Mansour Period Recovery from $N=4$ to $N=10$

Questo articolo presenta una dimostrazione autentica e non compilata su hardware quantistico reale di IBM di una criptanalisi quantistica fedele ai testi di manualistica utilizzando l'algoritmo di Simon per recuperare periodi nascosti per strutture di cifrari Even-Mansour e Feistel fino a dimensioni record (N=10), fornendo al contempo un benchmark completo di cinque attacchi attraverso quattro paradigmi di cifrari simmetrici con esplicite avvertenze riguardanti il loro ambito, la dipendenza dalla mitigazione degli errori e la mancanza di minaccia per la crittografia moderna su larga scala.

Autori originali: Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

Pubblicato 2026-07-22

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Taebong Kim, Youngsik Hong, Minsik Kim, Sunyoung Choi, Jaewon Jang, Junghoon Shin, Minseo Kim

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

Immaginate un mondo in cui i codici segreti non sono solo chiusi in una cassaforte, ma nascosti all'interno di un labirinto attraverso il quale solo un fantasma può camminare. Questo è il regno della crittanalisi quantistica, un ramo della scienza in cui i ricercatori utilizzano le strane e inquietanti regole della fisica quantistica per testare quanto siano davvero resistenti le nostre serrature digitali. Per capire questo, bisogna conoscere tre cose semplici. Primo, i "cifrari simmetrici" sono come una chiave singola che chiude e apre un baule del tesoro; se hai la chiave, puoi aprirlo, ma se non ce l'hai, rimani bloccato. Secondo, i "computer quantistici" sono macchine speciali che possono provare molti percorsi in un labirinto contemporaneamente, a differenza dei computer normali che devono provare un percorso, poi un altro, poi un altro ancora. Infine, c'è un trucco famoso chiamato "algoritmo di Simon", che è come un detective super intelligente capace di trovare un modello nascosto in un caos disordinato molto più velocemente di un detective regolare, ma solo se il caos ha una struttura ripetitiva molto specifica.

Perché tutto questo è importante? Perché se un computer quantistico può trovare questi modelli facilmente, le chiavi segrete che proteggono i nostri conti bancari, i nostri messaggi e i segreti nazionali potrebbero essere violati. Ma ecco il punto: costruire un computer quantistico abbastanza grande e silenzioso da poterlo fare davvero è incredibilmente difficile. Attualmente sono molto rumorosi, come cercare di sentire un sussurro in un concerto rock. Questo articolo parla di un team di ricercatori che ha cercato di insegnare a un vero computer quantistico rumoroso come trovare questi modelli nascosti nei codici segreti, spingendo i limiti di ciò che è attualmente possibile nel mondo reale.

L'articolo: Un detective quantistico su un palcoscenico rumoroso

I ricercatori, lavorando con un vero computer quantistico realizzato da IBM (nello specifico il chip "ibm_kingston"), hanno deciso di giocare a un gioco di "trovare il modello nascosto". Si sono concentrati su un tipo specifico di struttura di codice segreto chiamato cifrario Even-Mansour. Immaginate questo cifrario come una macchina che prende un numero segreto (la chiave) e rimescola un messaggio. L'obiettivo dell'attacco è trovare il "periodo" — un ritmo ripetitivo nascosto nel modo in cui la macchina rimescola i dati. Se trovate il ritmo, potete capire la chiave segreta.

In passato, gli scienziati erano riusciti a farlo solo su hardware reale per versioni del codice molto piccole e semplici (dove il numero segreto era lungo solo 4 bit). Questo team voleva vedere quanto lontano potessero spingere la macchina reale. Sono riusciti a trovare con successo il ritmo nascosto per una versione in cui il numero segreto era lungo 10 bit. Questo potrebbe non sembrarvi molto, ma nel mondo dell'hardware quantistico, passare da 4 a 10 è un salto enorme. È come passare dal bilanciarsi su un piede solo al correre una maratona su una fune tesa.

Non si sono fermati lì. Hanno testato le loro abilità da detective anche su altri tipi di strutture di codice:

Il Feistel a 3 round: Una struttura utilizzata in codici più vecchi (come il famoso DES). Hanno trovato con successo il ritmo nascosto per dimensioni di blocco di 6 e 8.
Bernstein-Vazirani: Un puzzle lineare più semplice. Hanno trovato un segreto a 16 bit in una singola domanda (query), esattamente come promesso dalla matematica.
Ricerca di Grover: Hanno testato un metodo per la ricerca di chiavi non strutturate, dimostrando che il computer quantistico poteva trovare una chiave in circa 13 passaggi, quando un computer normale ne avrebbe necessari 256.

Il controllo della realtà: Com'è andata?

Questa è la parte più importante della storia, e la parte in cui gli autori sono molto, molto onesti. Sebbene abbiano trovato i modelli, non hanno violato il codice in un modo che permetterebbe loro di rubare il vostro conto bancario oggi.

Per i puzzle più grandi (dove il segreto era di 6 bit o più), il computer quantistico è diventato un po' "rumoroso" e confuso. Non ha indicato immediatamente l'unica risposta corretta. Invece, ha fornito una lista dei principali candidati. I ricercatori hanno poi usato un computer normale per controllare i primi 16, 32, 64 o 128 candidati dalla lista quantistica. La vera chiave segreta si trovava solitamente molto in alto in quella lista (spesso entro i primi 63 candidati), il che è molto meglio che indovinare casualmente.

Gli autori sono molto chiari: questo non è ancora un "vantaggio quantistico".

Nessuna soluzione magica: Non hanno violato le versioni complete e reali di codici famosi come AES o RSA. Hanno violato solo versioni semplificate e ridotte delle strutture.
Niente super-velocità: Per i puzzle più grandi, il computer quantistico non ha risolto tutto da solo. Ha ristretto l'elenco dei sospettati, ma un computer normale ha dovuto comunque svolgere il lavoro finale. Il vantaggio di velocità che hanno visto riguardava il numero di domande poste, non il tempo totale impiegato per violare il codice.
Rumore vs Perfezione: Hanno utilizzato la "mitigazione dell'errore" (un modo elegante per dire che hanno pulito i dati rumorosi) piuttosto che la "correzione dell'errore" (che corregge gli errori perfettamente). Ciò significa che i loro risultati sono impressionanti per la tecnologia odierna, ma non sono la soluzione finale e perfetta.

Il quadro generale

Il team ha anche eseguito una massiccia simulazione su un supercomputer per vedere fin dove si potesse arrivare se avessero avuto macchine perfette e prive di rumore. Hanno scoperto che, sebbene un computer quantistico possa teoricamente gestire questi puzzle facilmente, un computer normale finirebbe la memoria cercando di simulare un computer quantistico con soli 25 qubit (le unità di informazione quantistica di base). Un puzzle leggermente più grande richiederebbe 4,5 petabyte di memoria — più di quanto la maggior parte dei data center possieda!

Quindi, qual è la conclusione? Questo articolo è un "record mondiale" per quanto grande una struttura di codice segreto un vero computer quantistico rumoroso sia riuscito ad analizzare con successo. Dimostra che la matematica funziona sull'hardware reale, anche se l'hardware è ancora un po' instabile. È una prova di concetto che dice: "Possiamo farlo, ma abbiamo bisogno di macchine migliori e più silenziose prima di poter effettivamente violare i segreti del mondo reale". Gli autori hanno reso pubblici il loro codice e i loro dati affinché chiunque possa verificare il loro lavoro, assicurando che questa non sia solo un'affermazione, ma un passo avanti riproducibile nella corsa tra i computer quantistici e i codici segreti.

Sintesi Tecnica: Criptanalisi Quantistica su Hardware IBM Quantum

Definizione del Problema

La ricerca teorica ha stabilito da tempo che specifiche strutture di cifrari simmetrici, come il cifrario Even–Mansour e le reti Feistel a 3 round, possono essere ridotte a problemi a periodo nascosto risolvibili tramite l'algoritmo di Simon. Tuttavia, esiste un divario significativo tra queste riduzioni teoriche ed esecuzioni pratiche su dispositivi quantistici a scala intermedia rumorosa (NISQ). Prima di questo lavoro, le dimostrazioni su hardware reale di tali recuperi di chiavi erano limitate a parametri di sicurezza molto piccoli (specificamente $N=4$ ) a causa del rumore del dispositivo e della mancanza di correzione degli errori tollerante ai guasti (fault-tolerant). La sfida consiste nell'estendere tali attacchi a dimensioni di struttura più grandi ( $N > 4$ ) su hardware reale mantenendo un'integrità algoritmica "genuina" — ovvero, i circuiti devono implementare le effettive mappe cifrate senza scorciatoie di traslazione che renderebbero banale la ricerca.

Metodologia

Gli autori hanno eseguito una criptanalisi quantistica "genuina, non compilata e fedele al testo originale" sul processore IBM ibm_kingston (generazione Heron) utilizzando il framework Qiskit. La metodologia è caratterizzata dai seguenti componenti:

Ambito Algoritmico: Lo studio prende di mira quattro paradigmi di progettazione di cifrari simmetrici:
1. Struttura Lineare: Algoritmo di Bernstein–Vazirani (singola query).
2. Ricerca Non Strutturata: Algoritmo di Grover applicato a una ricerca di chiave SPN (Substitution-Permutation Network) ridotta.
3. Problemi a Periodo Nascosto: Algoritmo di Simon applicato a:
  - Cifrario Even–Mansour.
  - Falsificazione CBC-MAC.
  - Costruzione Feistel a 3 round (famiglia DES).
Strategia di Esecuzione:
- Hardware Reale: Gli esperimenti hanno utilizzato uno stack completo di mitigazione dell'errore di lettura (inclusi calibrazione, de-coupling dinamico e twirling) piuttosto che la correzione degli errori fault-tolerant.
- Approccio Ibrido per $N > 5$ : Per le istanze Even–Mansour in cui il rumore impediva un recupero "rank-1" pulito, gli autori hanno impiegato un ibrido di restringimento quantistico + verifica classica. Il circuito quantistico ha generato una lista ristretta di candidati con il ranking più alto (ad esempio, i primi 16 o 128), che sono stati poi verificati classicamente.
- Validazione: Tutti i risultati sull'hardware sono stati validati incrociati contro chiavi di controllo indipendenti per garantire che i periodi recuperati non fossero artefatti di specifiche selezioni di chiavi.
- Simulazione: È stato condotto un benchmark breadth-first utilizzando simulazione di stato vettoriale genuina (su hardware NVIDIA B200) fino al limite di memoria classica di 25 qubit per validare i circuiti non compilati.

Risultati Chiave

1. Estensione della Frontiera su Hardware Reale

Il documento riporta il recupero del periodo nascosto di Even–Mansour fino al parametro di sicurezza $N = 10$ su hardware reale.

$N = 5$ : Raggiunto un recupero rank-1 pulito (Simon differenziale) dove la chiave vera era il candidato principale.
$N = 6$ a $N = 10$ : Raggiunto tramite l'approccio ibrido. Sebbene la chiave vera non fosse sempre l'unico output principale a causa del rumore, il suo rango seguiva il limite di compleanno (birthday bound) ( $2^{n/2}$ ), rimanendo di ordini di grandezza al di sotto dell'aspettativa casuale ( $2^{n-1}$ ).
Confronto: Questo supera la dimensione più grande precedentemente riportata su hardware reale di $N = 4$ .

2. Recupero di Strutture Feistel e Lineari

Feistel a 3 Round: Ha recuperato chiaramente il periodo per blocchi di dimensione 6 e 8 (rank-1, esatto) su hardware reale. Un'istanza di blocco-10 a 21 qubit è stata verificata in simulazione e sottoposta all'hardware.
Bernstein–Vazirani: Ha estratto con successo un segreto lineare a 16 bit in una singola query su hardware reale.

3. Separazione della Complessità

Lo studio dimostra la separazione teorica della complessità di query:

Attacchi basati su Simon: Complessità di query classica esponenziale ( $2^{n/2}$ ) vs. query quantistiche polinomiali ( $\Theta(n)$ ).
Attacchi basati su Grover: Accelerazione quadratica (ad esempio, recuperare una chiave a 8 bit in $\approx 13$ iterazioni rispetto a 256 valutazioni classiche).

Significato e Rivendicazioni

Gli autori inquadrano esplicitamente i loro contributi con un focus su onestà e riproducibilità, evitando di sopravvalutare il "vantaggio quantistico".

Dimostrazione su Hardware Reale: Il contributo primario è la dimostrazione di una genuina criptanalisi quantistica su hardware reale a dimensioni di struttura record ( $N=10$ per Even–Mansour), colmando il divario tra riduzioni teoriche ed esecuzione fisica.
Ampiezza di Copertura: Il lavoro fornisce un benchmark completo attraverso quattro distinti paradigmi crittografici (Lineare, Non Strutturato, Periodo Nascosto) e cinque attacchi specifici, tutti validati fino al limite di simulazione classica.
Nessun Vantaggio Quantistico End-to-End: Il documento dichiara esplicitamente che questi attacchi non costituiscono un vantaggio quantistico rispetto ai metodi classici in termini di costo end-to-end. Gli attacchi seguono asintoticamente il limite di compleanno, il che significa che il ritrovamento di collisioni classico raggiunge una scalabilità comparabile. La separazione riguarda strettamente la complessità di query per il distinguere, non il costo computazionale totale.
Limitazioni dell'Ambito:
- Gli attacchi prendono di mira costruzioni ridotte o strutturate (Even–Mansour, Feistel a 3 round, SPN ridotta), non AES, RSA o DES a 16 round completi.
- I risultati si basano sulla mitigazione dell'errore, non sulla correzione degli errori fault-tolerant.
- Il modello di oracle Q2 (quantum-query) è assunto, sebbene gli autori ne riconoscano i limiti pratici e notino che le riduzioni offline-Simon possono rilassare alcune assunzioni verso Q1.

In sintesi, questo articolo funge da benchmark rigoroso e riproducibile di algoritmi quantistici genuini su hardware NISQ, dimostrando che, sebbene i dispositivi attuali non possano rompere i moderni cifrari su scala completa, possono eseguire con successo complesse riduzioni criptanalitiche su primitive strutturate a dimensioni precedentemente irraggiungibili su hardware reale.