Malleability of transformations on the ciphertext in noisy Quantum public key encryption

Sintesi Tecnica: Malleabilità delle Trasformazioni sul Cifrato nella Crittografia a Chiave Pubblica Quantistica con Rumore

Enunciato del Problema
Questo articolo affronta la sfida di formulare rigorosamente la "sicurezza eterna" (everlasting security) per la Crittografia a Chiave Pubblica Quantistica (QPKE) e la Distribuzione di Chiavi Quantistiche (QKD) in presenza di rumore. Mentre il lavoro precedente di Malavolta e Walter [3] ha stabilito un framework per la sicurezza eterna in un contesto privo di rumore — dimostrando che la sicurezza può essere raggiunta dopo solo due round di interazione tra Alice e Bob — questo studio investiga come l'introduzione del rumore influenzi le soglie di sicurezza del protocollo. Nello specifico, il documento esplora la relazione tra la malleabilità delle trasformazioni del cifrato e la sicurezza del protocollo quando il rumore viene iniettato nelle operazioni crittografiche. Il problema centrale è quello di generalizzare la funzione di negligenza (che quantifica il vantaggio dell'avversario) dal caso ideale privo di rumore a un contesto rumoroso, utilizzando assunzioni riguardanti la malleabilità delle trasformazioni di testo in chiaro e di cifrato.

Metodologia
Gli autori impiegano una combinazione di Teoria dell'Informazione Quantistica e Crittografia Astratta per analizzare il protocollo QPKE-QKD rumoroso. La metodologia è strutturata attorno ai seguenti componenti chiave:

1. Iniezione di Rumore tramite Malleabilità: Il documento adatta il concetto di malleabilità, introdotto originariamente da Maurer e Tackmann [9] per confrontare i protocolli "autentica poi cripta" (authenticate then encrypt) e "cripta poi autentica" (encrypt then authenticate). Gli autori definiscono trasformazioni rumorose sullo spazio del testo in chiaro caratterizzate da tre probabilità di errore: errore di inoltro (forwarding error), errore di cancellazione (deleting error) ed errore di ricostruzione (reconstruction error). Questi errori vengono utilizzati per modellare l'impatto del rumore sul cifrato.
2. Distanza di Traccia e Gentle Measurement Lemma (GML): Uno strumento tecnico centrale è l'adattamento della Gentle Measurement Lemma dalla Teoria dell'Informazione Quantistica [18]. Gli autori utilizzano questo lemma per stabilire un limite superiore sulla distanza di traccia tra due stati quantistici (che rappresentano gli esperimenti reale e ideale) basandosi su un limite inferiore della traccia di un operatore specifico. Ciò consente di generalizzare la funzione di negligenza in presenza di rumore.
3. Macchine Noisy Quantum Polynomial-Time (NQPT): Il documento formalizza il contesto rumoroso definendo macchine Noisy Quantum Polynomial-Time (NQPT) e mappe Noisy Completely Positive Trace Preserving (CPTP). Questi oggetti sostituiscono i rispettivi controparti privi di rumore per modellare il comportamento di Alice, Bob ed Eve (l'avversaria) in condizioni di rumore.
4. Operatori di Proiezione e Decomposizione di Stato: L'analisi prevede la costruzione di operatori di proiezione rumorosi ($\tilde{\Pi}$) che incorporano termini di rumore (ad esempio, $|\sigma + \text{noise}\rangle$) nel normale operatore di proiezione $\Pi$ utilizzato nel protocollo QPKE-QKD privo di rumore. Gli autori derivano limiti superiori sulla distanza di traccia confrontando i rapporti tra operatori di proiezione privi di rumore e rumorosi, operazioni di traccia, e stati ket/bra.
5. Approccio Teorico delle Risorse: Il documento utilizza il framework teorico delle risorse da [9], definendo sicurezza e disponibilità in termini di indistinguibilità delle risorse costruite dai protocolli. Ciò include l'analisi della composizione dei protocolli e l'indistinguibilità di esperimenti ibridi.

Contributi Chiave

• Formalizzazione della Sicurezza Eterna Rumorosa: Il documento definisce la "sicurezza eterna" per un protocollo QPKE rumoroso (Definizione 37), stabilendo che la distanza di traccia tra esperimenti ibridi rumorosi è limitata da una funzione di negligenza dipendente dal parametro di sicurezza rumoroso $\lambda'$.
• Generalizzazione della Funzione di Negligenza: Gli autori derivano una relazione tra la distanza di traccia nel contesto rumoroso e la funzione di negligenza $NEGL(\lambda')$. Dimostrano che, sotto specifiche assunzioni sul rumore, la funzione di negligenza nel contesto rumoroso si relaziona a una soglia di sicurezza più elevata rispetto al caso privo di rumore.
• Limiti della Distanza di Traccia via GML: Un contributo tecnico primario è la derivazione di un limite superiore sulla distanza di traccia utilizzando la Gentle Measurement Lemma. Gli autori dimostrano che:
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  Ciò è ottenuto provando un limite inferiore sulla traccia di un operatore specifico che coinvolge la differenza tra stati rumorosi e privi di rumore ($\tilde{\rho} - \tau$).
• Assunzioni di Malleabilità: Il lavoro collega esplicitamente la sicurezza del protocollo alla malleabilità delle trasformazioni del cifrato. Esso quantifica come le probabilità di errore di inoltro, cancellazione e ricostruzione delle trasformazioni rumorose si relazionino al gap della soglia di sicurezza tra i protocolli privi di rumore ($\lambda$) e quelli rumorosi ($\lambda'$).
• Compromessi del Tempo di Esecuzione Computazionale: Il documento analizza i compromessi tra il tempo di esecuzione computazionale dei protocolli rumorosi e di quelli privi di rumore (codifica, decodifica e generazione di chiavi). Suggerisce che se il tempo di esecuzione del protocollo rumoroso è significativamente maggiore, il gap della soglia di sicurezza $\lambda' - \lambda$ scala in un modo specifico, potenzialmente correlato a funzioni esponenziali o polinomiali della differenza di runtime.

Risultati

• Teorema Principale: Il documento dimostra che per un protocollo QPKE-QKD rumoroso che soddisfa le condizioni di correttezza, la distanza di traccia tra gli esperimenti ibridi rumorosi (inizializzati con bit 0 e 1) è limitata dalla funzione di negligenza del parametro di sicurezza rumoroso:
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• Corollario sulle Funzioni di Vantaggio: Gli autori mostrano che le funzioni di vantaggio rumorose per diversi esperimenti ibridi ($\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$) sono tutte limitate dalla stessa funzione di negligenza $NEGL(\lambda')$, confermando la coerenza della definizione di sicurezza attraverso diversi setup sperimentali.
• Limite Inferiore sulla Traccia: Il documento fornisce una derivazione dettagliata mostrando che la traccia di un operatore specifico che coinvolge la differenza tra stati rumorosi e privi di rumore è limitata inferiormente da una costante per l'inverso della funzione di negligenza, il che è un prerequisito per l'applicazione della Gentle Measurement Lemma.

Significato e Rivendicazioni
Il documento sostiene di fornire un quadro matematico rigoroso per estendere la nozione di sicurezza eterna alla Crittografia a Chiave Pubblica Quantistica rumorosa. Adattando la Gentle Measurement Lemma, gli autori dimostrano che le garanzie di sicurezza del protocollo privo di rumore possono essere generalizzate al contesto rumoroso, a condizione che il rumore sia caratterizzato attraverso assunzioni di malleabilità sulle trasformazioni del cifrato.

Gli autori sottolineano che, sebbene l'introduzione del rumore porti generalmente a una soglia di sicurezza più elevata (implicando una garanzia di sicurezza potenzialmente più debole in termini del parametro $\lambda'$), i limiti derivati permettono un confronto quantitativo tra protocolli rumorosi e privi di rumore. Il lavoro è presentato come un passo teorico, osservando che, sebbene i requisiti per la sicurezza incondizionata ed eterna siano difficili da realizzare sperimentalmente, il framework proposto offre un punto di partenza prezioso per analizzare i limiti del calcolo quantistico rumoroso nei contesti crittografici. Il documento conclude suggerendo che i calcoli derivati per limitare la distanza di traccia potrebbero essere ulteriormente esaminati in contesti centrati su approcci di teoria dei giochi, pur non proponendo implementazioni sperimentali specifiche o applicazioni immediate oltre l'analisi teorica.