Capability-Adaptive Cryptanalysis with Reduced-Space Quantum Verification

Sintesi Tecnica: Criptanalisi Adattiva alle Capacità con Verifica Quantistica a Spazio Ridotto

Definizione del Problema
Il documento affronta la sfida fondamentale di integrare efficientemente l'evidenza criptanalitica classica con la verifica quantistica nella criptanalisi ibrida. Sebbene i sistemi a chiave simmetrica siano generalmente più resilienti agli avversari quantistici rispetto ai sistemi a chiave pubblica, la disponibilità di procedure di ricerca quantistica (specificamente l'algoritmo di Grover) altera il costo effettivo della verifica delle chiavi candidate. Tuttavia, la criptanalisi pratica raramente opera sull'intero spazio delle chiavi; al contrario, si basa su distinguitori statistici, osservazioni di leakage e riduzione guidata dai dati per vincolare l'insieme delle chiavi ammissibili prima della verifica finale. Gli autori identificano una lacuna nella letteratura esistente dove la criptanalisi statistica, la riduzione guidata dal leakage, la verifica quantistica e la selezione delle osservazioni sono tipicamente trattate come fasi isolate. Manca un framework unificato che combini sistematicamente il filtraggio adattivo, la selezione dell'attacco basata sulle capacità e la verifica quantistica a spazio ridotto per minimizzare l'overhead computazionale della ricerca quantistica finale.

Metodologia
Il framework proposto introduce un'architettura criptanalitica unificata e adattiva alle capacità che opera in tre fasi primarie:

1. Costruzione e Riduzione Unificata dello Spazio dei Candidati Classici:
   Il framework modella una primitiva a chiave simmetrica e costruisce un sottoinsieme iniziale di chiavi candidate ammissibili ($K_{cand}$) verificando esaustivamente la coerenza crittografica contro coppie osservate di testo in chiaro-testo cifrato. Questo spazio di base viene poi progressivamente ridotto attraverso tre meccania complementari:

   • Criptanalisi Lineare: Filtra i candidati basandosi sul bias statistico nelle approssimazioni lineari.
   • Criptanalisi Differenziale: Elimina le ipotesi incoerenti con le probabilità di propagazione differenziale osservate.
   • Analisi Guidata dal Leakage: Trattiene i candidati che mostrano una forte correlazione tra i vettori di leakage ipotetici e le tracce fisiche osservate (ad esempio, potenza o tempo).

   Fondamentalmente, il framework impiega predicati di attivazione adattivi alle capacità ($\chi_L, \chi_D, \chi_S$). Questi indicatori determinano dinamicamente se un modulo di riduzione specifico debba essere attivato in base alle risorse disponibili dall'avversario (ad esempio, accesso a testo in chiaro noto, capacità di testo in chiaro scelto o osservabilità del leakage). Se una capacità è assente, il corrispondente modulo viene saltato, preservando lo spazio di ricerca invece di filtrarlo erroneamente.

2. Verifica Quantistica a Spazio Ridotto:
   Una volta che le fasi di filtraggio classico producono uno spazio di candidati effettivo ($K_{eff}$), il framework attiva una fase di verifica quantistica solo se sono disponibili risorse computazionali quantistiche e la costruzione di un oracle reversibile. Invece di applicare l'algoritmo di Grover all'intero spazio delle chiavi ($2^k$), l'algoritmo opera esclusivamente sullo spazio ridotto ($N_{eff} = |K_{eff}|$).

   • Il numero di qubit richiesti è ridotto a $q = \lceil \log_2 N_{eff} \rceil$.
   • Il numero di iterazioni di Grover richieste è ridotto da $O(\sqrt{2^k})$ a $O(\sqrt{N_{eff}})$.
   • Gli autori forniscono un modello matematico formale, inclusa una formulazione Hamiltoniana, per interpretare il processo di verifica a spazio ridotto come una procedura di amplificazione dell'ampiezza fisicamente realizzabile.

3. Campionamento delle Osservazioni Assistito dal Quantum:
   Per affrontare potenziali bias nella selezione delle osservazioni, il framework propone l'uso di Generatori di Numeri Casuali Quantistici (QRNG) per guidare la selezione delle coppie testo in chiaro-testo cifrato, delle coppie differenziali e delle tracce di leakage. Ciò garantisce un campionamento non distorto per la stima statistica senza alterare la complessità asintotica della procedura criptanalitica.

Contributi Chiave

• Framework Ibrido Unificato: Il documento presenta un meccanismo strutturato che integra analisi lineare, differenziale e side-channel con la verifica quantistica in un unico flusso di lavoro, governato dalle specifiche capacità dell'avversario.
• Caratterizzazione Formale della Complessità: Gli autori sviluppano un modello matematico che dimostra come la contrazione adattiva dello spazio dei candidati riduca strettamente la complessità della verifica quantistica asintotica. Dimostrano che se almeno una fase di riduzione attivata elimina ipotesi non valide, il costo della verifica quantistica è strettamente inferiore rispetto a una ricerca su spazio completo.
• Orchestrazione Adattiva alle Capacità: L'introduzione di predicati di attivazione permette al framework di regolare dinamicamente la disponibilità dei vettori di attacco (ad esempio, se non sono disponibili tracce di side-channel, il modulo side-channel viene saltato), garantendo che l'attacco rimanga valido sotto diverse condizioni avversarie.
• Interpretazione Hamiltoniana: Viene introdotta una formulazione Hamiltoniana per fornire un'interpretazione fisica del processo di verifica a spazio ridotto, collegando gli operatori di oracle e diffusione a specifiche evoluzioni Hamiltoniane.

Risultati
Il framework è stato valutato utilizzando osservazioni criptanalitiche generate statisticamente per simulare un ambiente controllato:

• Contrazione dello Spazio dei Candidati: Partendo da uno spazio di ipotesi iniziale di 4.096 candidati, l'applicazione combinata dei filtri guidati da analisi lineare, differenziale e leakage (con le opportune soglie) ha ridotto lo spazio ammissibile a 13 ipotesi. Ciò rappresenta una riduzione del 99,683% dello spazio di ricerca.
• Efficienza della Verifica Quantistica: Di conseguenza, il requisito di verifica di Grover è sceso da 50 iterazioni (richieste per lo spazio completo di 4.096) a sole 2 iterazioni per lo spazio ridotto di 13. Ciò produce una riduzione di circa 25 volte dell'impegno di verifica.
• Probabilità di Successo: In una simulazione specifica con uno spazio ridotto di 8 candidati, l'amplificazione dell'ampiezza a spazio ridotto ha raggiunto una probabilità di successo dello stato target di circa il 94,53% dopo due iterazioni, dimostrando un'elevata efficienza nel concentrare la massa di probabilità sull'ipotesi corretta.

Significatività e Rivendicazioni
Il documento afferma che il filtraggio criptanalitico adattivo può ridurre sostanzialmente la complessità della verifica quantistica preservando l'ammissibilità criptanalitica. La significatività risiede nel fornire una base pratica per la criptanalisi ibrida consapevole delle capacità, dove la riduzione statistica classica e la ricerca quantistica non sono trattate come entità separate, ma come un processo coeso e mutuamente rinforzante. Riducendo lo spazio di ricerca prima dell'esecuzione quantistica, il framework mitiga le richieste di risorse dell'hardware quantistico, rendendo la ricerca quantistica a spazio ridotto un approccio più praticabile per l'analisi dei sistemi a chiave simmetrica. Gli autori posizionano questo lavoro come un passo verso modelli di attacco ibridi più efficienti e realistici che tengano conto sia dei limiti dei dati classici sia delle specifiche capacità degli avversari quantistici.