💻 computer science

Quantum Key Search Algorithms under Side-channel Attack

Questo articolo propone un algoritmo di ricerca della chiave quantistica migliorato che sfrutta le distribuzioni di errore indotte da attacchi side-channel per ottenere un incremento di velocità super-quadratico rispetto ai metodi classici e supera gli approcci quantistici esistenti come quello di Glaser, affrontando al contempo le sfide della preparazione dello stato di input attraverso un'implementazione efficiente dello stato di Dicke.

Autori originali: Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

Pubblicato 2026-08-12

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Yunteng Yang, Jianhong Shi, Hailong Zhang, Hongwei Li, Xiangqun Fu, Yonghui Yang, Yubing Zhu, Yanyang Zhou

Articolo originale sotto licenza CC BY 4.0 (https://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 cercare di scassinare la combinazione di una cassaforte gigante e tecnologicamente avanzata. In il mondo della sicurezza digitale, questo "lucchetto" è una chiave crittografica: una lunga stringa di 0 e 1 che protegge i tuoi messaggi, i tuoi conti bancari e i tuoi segreti. Per decenni, l'unico modo per aprire questa cassaforte era provare ogni singola combinazione possibile, una alla volta, finché non si era fortunati. È come provare ogni chiave su un enorme portachiavi; se ci sono un miliardo di chiavi, potresti doverne provare mezzo miliardo prima di trovare quella giusta. Questo è il modo "classico" di fare le cose, ed è lento.

Poi, gli scienziati hanno scoperto uno strumento magico chiamato "computer quantistico". Pensalo non come una calcolatrice più veloce, ma come un mago che può guardare molte chiavi contemporaneamente. Usando un trucco famoso chiamato algoritmo di Grover, questo mago può trovare la chiave giusta molto più velocemente del vecchio metodo—riducendo il tempo da un miliardo di tentativi a circa trentamila. Ma ecco il colpo di scena: e se non dovessi partire da zero? E se un ladro subdolo avesse già sbirciato nella cassaforte e ottenuto una versione rumorosa, sfocata della chiave? Forse ha visto che la chiave era "per lo più" 101010, ma alcuni bit erano confusi. Questo è chiamato "attacco side-channel". È come trovare un'impronta digitale sulla cassaforte che ti dà un indizio, anche se non è perfetto. La grande domanda per gli scienziati è: possiamo usare questi indizi rumorosi per rendere il mago quantistico ancora più intelligente e veloce?

Questo articolo, scritto da un team di ricercatori della Information Engineering University, si addentra proprio in questo scenario. Chiedono: se un attaccante ha una chiave rumorosa con alcuni errori (come una foto sfocata della soluzione), come possiamo usare i computer quantistici per trovare la chiave reale più velocemente che mai?

I ricercatori hanno prima esaminato come un computer normale gestirebbe questa situazione. Si sono resi conto che se sai che la chiave è "per lo più" corretta, non dovresti indovinare a caso. Invece, dovresti iniziare indovinando la chiave che assomiglia esattamente a quella rumorosa, poi indovinare le chiavi che hanno solo un piccolo errore, poi due errori, e così via. È come cercare in una biblioteca partendo dai libri che somigliano di più a quello che stai cercando, invece di entrare e prendere libri dal fondo della stanza. Hanno calcolato esattamente quanti tentativi richiederebbe questo metodo classico "intelligente".

Successivamente, hanno costruito un nuovo algoritmo quantistico per fare la stessa cosa, ma con il potere della meccanica quantistica. Hanno notato che i precedenti metodi quantistici cercavano di dividere lo spazio di ricerca in blocchi che crescevano in dimensione secondo un modello geometrico (1, poi 10, poi 100). Tuttavia, i ricercatori hanno scoperto che gli indizi della "chiave rumorosa" creano in realtà un modello specifico basato su quanti bit sono errati (la distanza di Hamming). Invezione di usare un modello geometrico, hanno deciso di raggruppare le chiavi in base a quanti errori hanno: un gruppo per le chiavi con 0 errori, un gruppo per le chiavi con 1 errore, un gruppo per le chiavi con 2 errori, e così via.

Hanno progettato una strategia in cui il computer quantistico affronta questi gruppi uno alla volta, partendo dal gruppo che è più probabile contenga la risposta. Per far sì che questo funzioni, hanno dovuto risolvere un problema complicato: come preparare il computer quantistico per guardare solo le chiavi con, ad esempio, esattamente 3 errori, senza sprecare tempo su tutte le altre. Hanno risolto questo problema utilizzando uno stato quantistico speciale chiamato "stato di Dicke". Puoi pensare allo stato di Dicke come a un mazzo di carte perfettamente organizzato dove ogni carta ha esattamente lo stesso numero di cuori rossi. Una volta ottenuto questo stato organizzato, possono facilmente capovolgere le carte per farle corrispondere alla chiave rumorosa che hanno. Questa preparazione è efficiente e non richiede attrezzature extra o disordinate.

Quando hanno eseguito delle simulazioni per testare il loro nuovo metodo, i risultati sono stati impressionanti. Hanno usato una chiave a 256 bit (una chiave molto lunga e sicura) con un tasso di errore minimo dell'1% (il che significa che la chiave rumorosa era corretta al 99%).

Un computer classico standard avrebbe avuto bisogno di circa $2^{256}$ tentativi se non avesse avuto indizi.
Con l'indizio rumoroso, un computer classico intelligente richiederebbe ancora circa $2^{62.29}$ tentativi.
Il loro nuovo algoritmo quantistico, tuttavia, ha richiesto solo circa $2^{19.77}$ tentativi.

Questo significa che il loro metodo quantistico è significativamente più veloce del metodo classico intelligente. Hanno calcolato un "fattore di accelerazione" di 3.15, che è superiore al 2.73 ottenuto dai metodi precedenti (come quelli di Glaser). In parole semplici, il loro mago quantistico non sta solo guardando più chiavi contemporaneamente; sta guardando le chiavi giuste per prime, grazie al modo specifico in cui hanno organizzato la ricerca.

L'articolo argomenta anche esplicitamente contro l'uso della vecchia strategia dei blocchi a crescita geometrica (come l'algoritmo di Montanaro) per questo specifico tipo di problema della chiave rumorosa. Dimostrano che, poiché gli errori seguono una specifica "distribuzione di Bernoulli" (un modello di flip casuali), l'approccio geometrico non è il più efficiente. Il loro approccio basato sulla "distanza di Hamming", che raggruppa le chiavi per l'esatto numero di errori, è un migliore adattamento alla realtà.

In sintimento, questa ricerca suggerisce che combinando gli "indizi sfocati" degli attacchi side-channel con una strategia di ricerca quantistica sapientemente organizzata, possiamo scardinare le chiavi molto più velocemente di prima. Sebbene questi risultati siano attualmente basati su simulazioni e prove matematiche piuttosto che su un computer quantistico fisico che esegue il codice, la matematica mostra una via chiara verso una ricerca di chiavi quantistica super veloce che supera sia il vecchio modo di indovinare che i precedenti tentativi quantistici. Il team conclude che questo metodo non è solo teoricamente solido, ma anche praticamente realizzabile da costruire, poiché la preparazione dello "stato di Dicke" che hanno proposto può essere fatta con un numero gestibile di passaggi e senza bisogno di hardware extra e complessi.

Riepilogo Tecnico: Algoritmi di Ricerca di Chiavi Quantistiche sotto Attacco Side-channel

Definizione del Problema
Questa ricerca affronta il problema della ricerca di chiavi in algoritmi crittografici quando un attaccante possiede una chiave rumorosa derivata da attacchi side-channel (SCA). In questo scenario, l'attaccante ottiene una chiave $Y$ che differisce dalla vera chiave target $k^*$ per un certo numero di inversioni di bit (distanza di Hamming). La distribuzione di probabilità dello spazio delle chiavi non è uniforme; segue invece una distribuzione di Bernoulli $n$ -fold determinata dal tasso di errore dei bit (BER), $\alpha$ . La sfida consiste nel ricercare efficientemente questo spazio di chiavi non uniforme per trovare $k^*$ , sfruttando l'informazione a priori fornita dalla chiave rumorosa. Mentre la ricerca classica brute-force richiede $O(N)$ query e l'algoritmo standard di Grover offre $O(\sqrt{N})$ , nessuno dei due sfrutta appieno la specifica struttura della distribuzione di Bernoulli indotta dagli SCA. Inoltre, gli approcci quantistici esistenti, come l'algoritmo di Montanaro, incontrano difficoltà nella preparazione degli stati di sovrapposizione iniziali specifici richiesti per i blocchi di chiavi con uguali probabilità a posteriori.

Metodologia
Gli autori propongono un framework completo che spazia dalla modellazione teorica, alla progettazione dell'algoritmo, fino alla preparazione dello stato:

Modellazione Probabilistica: Lo studio modella la distribuzione dello spazio delle chiavi assumendo inversioni di bit indipendenti e identicamente distribuite (i.i.d.) con probabilità $\alpha$ . Utilizzando il teorema di Bayes, si dimostra che la probabilità a posteriori di una chiave candidata dipende esclusivamente dalla sua distanza di Hamming $d$ dalla chiave rumorosa $Y$ . Ciò stabilisce che le chiavi con la stessa distanza di Hamming condividono la stessa probabilità a posteriori.
Baseline Classica: Viene derivato un algoritmo di ricerca delle chiavi classico che attraversa le chiavi candidate in ordine decrescente di probabilità a posteriori (ovvero partendo dalla distanza di Hamming $d=0$ fino a $d=n$ ). La complessità attesa delle query $G_c$ è calcolata rigorosamente in base alla distribuzione binomiale delle chiavi candidate a ogni distanza.
Algoritmo Quantistico Migliorato:
- Strategia di Partizione: A differenza dell'algoritmo di Montanaro, che partiziona lo spazio delle chiavi in blocchi a crescita geometrica $\{1, c, c^2, \dots\}$ , questo articolo propone di partizionare lo spazio delle chiavi in $(n+1)$ blocchi $\{R_0, R_1, \dots, R_n\}$ basati strettamente sulla distanza di Hamming $d$ . Ogni blocco $R_d$ contiene tutte le $\binom{n}{d}$ chiavi candidate con esattamente $d$ errori di bit.
- Esecuzione della Ricerca: L'algoritmo itera attraverso questi blocchi in ordine di probabilità decrescente (distanza $d$ crescente). Per ogni blocco $R_d$ , prepara una sovrapposizione uniforme delle chiavi in quel blocco e applica l'algoritmo di Grover.
- Analisi della Complessità: La complessità di query quantistica $G_q$ viene derivata sommando i costi della ricerca di Grover su ogni blocco, pesati dalla probabilità che la chiave target risieda in quel blocco.
Preparazione dello Stato Iniziale: Per affrontare la difficoltà di preparare lo specifico stato di sovrapposizione per ogni blocco $R_d$ $R_{d}$ , gli autori stabiliscono un'equivalenza tra lo stato della chiave candidata e lo stato di Dicke $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ . Dimostrano che la sovrapposizione uniforme delle chiavi alla distanza di Hamming $d$ $d$ da $Y$ $Y$ può essere generata applicando un prodotto tensoriale di porte Pauli-X ( $X^{\otimes Y}$ $X^{\otimes Y}$ ) allo stato di Dicke $|D^n_d\rangle$ $∣ D_{d}^{n} ⟩$ .
- Implementazione: Lo stato di Dicke viene preparato utilizzando un circuito a profondità ridotta "divide-and-conquer" (basato sul lavoro di Bärtschi ed Eidenbenz) che non richiede qubit ausiliari. Lo stato finale si ottiene applicando $O(d)$ porte X basate sulla chiave rumorosa $Y$ .

Contributi Chiave

Derivazione Teorica: Il documento fornisce una derivazione rigorosa della complessità computazionale sia per la ricerca di chiavi classica che per quella quantistica in condizioni di attacco side-channel, modellando specificamente la distribuzione di Bernoulli $n$ -fold.
Miglioramento Algoritmico: Introduce un algoritmo di ricerca di chiavi quantistiche migliorato che utilizza una strategia di partizione dei blocchi basata sulla distanza di Hamming. Si dimostra che questa strategia è più coerente con la reale distribuzione delle chiavi negli scenari SCA rispetto alla partizione geometrica utilizzata nell'algoritmo di Montanaro.
Soluzione per la Preparazione dello Stato: Il lavoro risolve l'imbuto della preparazione dello stato di input trasformando il problema nella preparazione dello stato di Dicke. Dimostra che lo stato richiesto può essere generato con $O(nd)$ porte CNOT e una profondità del circuito ridotta ( $O(d \log \frac{n}{d})$ per la topologia ion trap o $O(\sqrt{nd})$ per la topologia superconducting) senza qubit ausiliari.

Risultati
I risultati delle simulazioni per una chiave crittografica a 256 bit con un tasso di errore dei bit (BER) dell'1% ( $\alpha = 0.01$ ) dimostrano guadagni significativi nelle prestazioni:

Riduzione della Complessità: La complessità delle query per l'algoritmo classico in condizioni SCA scende da $2^{256}$ (senza SCA) a $2^{62.29}$ . L'algoritmo quantistico proposto riduce ulteriormente questo valore a $2^{19.77}$ .
Fattore di Accelerazione (Speedup): L'algoritmo quantistico proposto ottiene un fattore di accelerazione di 3.15 rispetto all'algoritmo classico in condizioni SCA. Questo è confrontato con un fattore di accelerazione di 2.73 riportato da Glaser et al. (che hanno analizzato l'algoritmo di Montanaro) nelle stesse condizioni. Gli autori osservano che la loro efficienza di ricerca è potenziata del 15.38% rispetto all'efficienza ottenuta dall'algoritmo a crescita geometrica di Montanaro proposto in [9].
Confronto con i Limiti: Il documento afferma che la complessità di query quantistica derivata ( $2^{19.77}$ ) è più precisa e più stretta dei limiti superiore/inferiore ( $2^{21.59}$ e $2^{17.59}$ ) stimati da Glaser per l'algoritmo di Montanaro in questo specifico scenario di distribuzione.
Efficienza delle Risorse: Il piano di preparazione dello stato è dimostrato essere fattibile per circuiti a breve profondità, con conteggi specifici delle risorse forniti per $n=256$ e $d=4$ (ad esempio, 1024 porte CNOT, 0 qubit ancilla).

Significatività
Il documento afferma che la sua ricerca fornisce una soluzione a catena completa, dalla analisi teorica all'implementazione pratica, per la crittanalisi quantistica sotto attacchi side-channel. Sfruttando la struttura specifica del rumore side-channel (distribuzione di Bernoulli), l'algoritmo proposto ottiene un accelerazione super-quadratica rispetto ai controparti classici, superando precedenti adattamenti della ricerca quantistica come quello di Montanaro. La capacità di preparare gli stati iniziali necessari utilizzando circuiti a breve profondità e senza qubit ausiliari affronta una barriera critica per l'implementazione pratica della ricerca di chiavi quantistiche. Gli autori asseriscono che questi risultati offrono una stima della complessità più accurata e una strategia di ricerca più efficiente per scenari in cui è disponibile un'informazione a priori sotto forma di chiave rumorosa. Il lavoro futuro è identificato nell'esplorare l'integrazione di questo algoritmo con cifrari specifici (AES, SM4) e nell'analizzare l'impatto del rumore quantistico.

Riepilogo Tecnico: Algoritmi di Ricerca di Chiavi Quantistiche sotto Attacco Side-channel

Articoli simili