Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM

Sintesi Tecnica: Impossibilità di un Accordo di Chiave Perfettamente Completo a Molti Round nel QROM

Enunciato del Problema
Questo articolo affronta i limiti fondamentali dell'Accordo di Chiave Quantistica (QKA) all'interno del Modello di Oracolo Casuale Quantistico (QROM). Nello specifico, indaga se due parti, Alice e Bob, possano stabilire una chiave segreta condivisa con completezza perfetta (probabilità 1) utilizzando solo la comunicazione classica, eseguendo calcoli quantistici locali e formulando query quantistiche a un oracolo casuale. L'ambiente è il modello di Computazione Quantistica con Comunicazione Classica (QCCC). La questione centrale è se tali protocolli possano essere sicuri contro un eavesdropper passivo che osserva la trascrizione classica e ha accesso allo stesso oracolo, assumendo che il protocollo sia costruito da funzioni unidirezionali (OWF) quantisticamente sicure in modo black-box.

Lavori precedenti avevano stabilito separazioni per protocolli classici e casi quantistici specifici, ma rimanevano lacune per i protocolli QCCC generici a più round. In particolare, Austrin et al. (CRYPTO 22) hanno fornito un attacco a query polinomiali sotto una "Congettura di Compatibilità Polinomiale" non provata, mentre Li et al. (CRYPTO 26) hanno risolto il caso dei protocolli a due round in modo incondizionato. Questo articolo mira a colmare la lacuna per i protocolli a round arbitrari senza fare affidamento su congetture non provate.

Metodologia
Gli autori impiegano una combinazione di teoria della complessità delle query quantistiche, analisi polinomiale su funzioni booleane e complessità dell'albero di decisione per costruire un attacco incondizionato. La metodologia centrale procede come segue:

1. Fattorizzazione Polinomiale delle Probabilità della Trascrizione:
   Fissando la trascrizione classica completa $t$ e la tabella di verità dell'oracolo $z$, si dimostra che la probabilità che Alice e Bob producano chiavi specifiche $a$ e $b$ si fattorizza in $A_{t,a}(z) \cdot B_{t,b}(z)$. Qui, $A$ e $B$ sono funzioni non negative che rappresentano le probabilità di esecuzione locale di Alice e Bob, rispettivamente.

   • Utilizzando il metodo polinomiale quantistico (specificamente il Lemma 2.2 da [BBC+01]), gli autori limitano i gradi di queste funzioni: $\deg(A_{t,a}) \le 2q_A$ e $\deg(B_{t,b}) \le 2q_B$, dove $q_A$ e $q_B$ sono il numero di query quantistiche effettuate dalle parti oneste.

2. Supporti di Chiave Disgiunti tramite Completezza Perfetta:
   La condizione di completezza perfetta ($\text{Pr}[K_A = K_B] = 1]$) implica che per ogni trascrizione valida $t$ e oracolo $z$, il prodotto $A_{t,k}(z)B_{t,\ell}(z)$ deve essere zero per tutte le chiavi distinte $k \neq \ell$.

   • Definendo $C_{t,k}(z) = A_{t,k}(z)B_{t,k}(z)$, gli autori dimostrano che i supporti di questi polinomi sono a coppie disgiunti sul cubo booleano $\{0,1\}^N$.
   • Questa disgiunzione, combinata con il fatto che un polinomio multilineare non nullo di grado $d$ deve essere non nullo in almeno $2^{N-d}$ punti (Lemma 2.1), limita il numero di chiavi candidate $|K_t|$ a al massimo $2^d$, dove $d = 2(q_A + q_B)$.

3. Albero di Decisione per Polinomi Disgiunti:
   Il contributo tecnico critico è una procedura deterministica (Lemma 3.5) per identificare quale tra due polinomi a supporto disgiunto, $p$ e $q$, sia non nullo in uno specifico oracolo $z$, dato l'impegno che uno di essi sia non nullo.

   • La procedura utilizza un albero di decisione ricorsivo. In ogni fase, identifica un insieme di $O(d^3)$ bit dell'oracolo tali che interrogarli determini la risposta o riduca strettamente il grado di uno dei polinomi.
   • Questa riduzione si basa su una disuguaglianza di Markov discreta (Lemma 2.3) applicata a un polinomio $r$ derivato dalla differenza dei quadrati degli input.
   • Si dimostra che la profondità di questo albero di decisione è $O(d^4)$.

4. Strategia di Ricerca Binaria:
   L'eavesdropper esegue una ricerca binaria bilanciata sull'insieme delle chiavi candidate $K_t$ (dimensione $\le 2^d$). Ad ogni livello, l'insieme dei candidati viene diviso in due metà, e vengono formati le somme dei corrispondenti polinomi ($P$ e $Q$). Poiché i supporti sono disgiunti, esattamente uno di $P(z)$ o $Q(z)$ è non nullo. L'albero di decisione del punto 3 viene utilizzato per determinare quale metà contenga la chiave corretta.

   • Con al massimo $d$ livelli di ricerca binaria e $O(d^4)$ query per livello, la complessità totale delle query è $O(d^5)$.

Contributi Chiave e Risultati

• Impossibilità Incondizionata: Il documento prova che è impossibile costruire protocolli di accordo di chiave QCCC a round finiti e con completezza perfetta da funzioni unidirezionali (OWF) quantisticamente sicure in modo black-box nel QROM. Questo risultato è incondizionato, rimuovendo la "Congettura di Compatibilità Polinomiale" richiesta dai lavori precedenti [ACC+22].
• Limite della Complessità delle Query: Gli autori costruiscono un eavesdropper che recupera la chiave condivisa con probabilità 1 utilizzando $O((q_A + q_B)^5)$ query dell'oracolo classiche.
  • Questo limite è indipendente dal numero di round di comunicazione, dalla lunghezza della trascrizione, dalla lunghezza della chiave e dalla dimensione del dominio dell'oracolo.
  • Crucialmente, mentre le parti oneste possono utilizzare query in sovrapposizione, l'eavesdropper richiede solo query classiche.
• Generalizzazione: Il risultato generalizza i precedenti risultati sui protocolli a due round [LLLL26] a round arbitrari e permette alle parti di mantenere stati quantistici arbitrari tra le fasi di comunicazione, uno scenario non coperto dai precedenti risultati incondizionati.

Significato e Rivendicazioni
Il documento sostiene di fornire una risposta negativa definitiva alla sicurezza del QKA a molti round e con completezza perfetta nel QROM.

• Impatto Teorico: Stabilisce una netta separazione black-box tra funzioni unidirezionali quantisticamente sicure e l'accordo di chiave a completezza perfetta nell'ambiente QCCC.
• Avanzamento Metodologico: La prova introduce un uso innovativo della riduzione del grado polinomiale e della complessità dell'albero di decisione al problema del recupero della chiave, gestendo specificamente il caso in cui le parti oneste utilizzano la sovrapposizione quantistica ma l'attaccante è limitato a query classiche.
• Limitazioni: Gli autori dichiarano esplicitamente che la prova si basa sulla completezza perfetta. Estendere questo risultato a protocolli con completezza imperfetta (dove le parti potrebbero non concordare con una piccola probabilità) richiederebbe idee significativamente diverse e non è oggetto di questo lavoro.
• Attribuzione: Il documento nota che il nucleo della prova è stato scoperto da GPT-5.6 Sol Ultra in una singola conversazione, con gli autori umani responsabili della verifica, del raffinamento e dell'esposizione finale.

In sintesi, il documento dimostra che nel QROM, la combinazione di comunicazione classica e completezza perfetta è insufficiente a proteggere l'accordo di chiave da un eavesdropper classico efficiente, indipendentemente dal numero di round o dalla complessità dei calcoli quantistici locali.