Quantum algorithm for Discrete Gaussian Sampling

Sintesi Tecnica: Algoritmo Quantistico per il Campionamento Gaussiano Discreto

Enunciato del Problema
Il Campionamento Gaussiano Discreto (DGS) sui reticoli è un problema fondamentale nella crittografia basata su reticoli, fungendo da componente centrale sia per le primitive crittografiche (ad esempio, firme digitali "hash-and-sign") sia per la crittanalisi (ad esempio, la risoluzione del Problema del Vettore Più Breve, Learning with Errors (LWE) e Short Integer Solution (SIS)). Il compito consiste nel campionare un vettore del reticolo $x$ con probabilità proporzionale a $e^{-\pi\|x-c\|^2/\sigma^2}$. La difficoltà del campionamento aumenta al diminuire del parametro di larghezza $\sigma$, in particolare al di sotto del "parametro di smoothing".

Gli algoritmi classici esistenti affrontano compromessi significativi:

• Campionatore di Klein: Efficiente (tempo polinomiale) ma limitato a valori di $\sigma$ grandi, dipendenti dalla qualità della base di input.
• Catene di Markov Monte Carlo (MCMC) [49]: Funziona per qualsiasi $\sigma$ ma soffre di un'alta complessità temporale, che scala inversamente rispetto a un parametro $\Delta$ (relato al rapporto delle masse gaussiane), rendendolo esponenziale nel caso peggiore.
• Algoritmi a Memoria Esponenziale: Algoritmi come [3] possono campionare per qualsiasi $\sigma$ ma richiedono memoria esponenziale, rendendoli impraticabili per la crittanalisi.

Attualmente, nessun algoritmo quantistico noto offre un'accelerazione per questi metodi di campionamento senza fare affidamento su risorse irrealistiche come la RAM quantistica (qRAM) per la memoria esponenziale, oppure non riesce a migliorare la complessità asintotica dell'approccio MCMC.

Metodologia
Gli autori propongono un algoritmo quantistico per il DGS basato sul Campionamento di Rifiuto Quantistico [41]. La strategia centrale consiste nel trasformare uno stato quantistico preparato da una distribuzione nota in una distribuzione target tramite amplificazione dell'ampiezza.

1. Preparazione dello Stato Iniziale (Campionatore Quantistico di Klein): L'algoritmo inizia preparando uno stato quantistico corrispondente a una variante della distribuzione di Klein, $|q\rangle$. Ciò viene ottenuto adattando l'algoritmo classico di campionamento di Klein (Algoritmo 1) in un circuito quantistico (Algoritmo 2), come dettagliato in [11]. Questo passo costruisce una sovrapposizione di vettori del reticolo le cui ampiezze approssimano la distribuzione di Klein.
2. Trasduzione dell'Ampiezza: L'algoritmo impiega un'operazione unitaria per modificare le ampiezze dello stato $|q\rangle$. Calcola il rapporto tra la distribuzione gaussiana discreta target $D_{\Omega, \sigma}$ e la distribuzione di Klein iniziale $q$. Ciò comporta la stima delle masse gaussiane su intervalli finiti utilizzando tecniche di Kitaev e Webb [31] e de Boer [10].
3. Campionamento di Rifiuto Quantistico: Utilizzando il rapporto calcolato, l'algoritmo applica la trasduzione dell'ampiezza a un qubit ancilla. Lo stato viene quindi proiettato sullo spazio "accetta" utilizzando l'Amplificazione dell'Ampiezza Quantistica (QAA) [17]. Il numero di iterazioni richieste è proporzionale alla radice quadrata del rapporto di rifiuto $w = \max_x (D_2(x)/D_1(x))$.
4. Precisione e Approssimazione: L'algoritmo opera con stati di distribuzione approssimati $|D \pm 2^{-\nu}\rangle$. Gli autori vincolano rigorosamente la distanza di variazione totale tra lo stato di output e la distribuzione gaussiana discreta ideale, garantendo che l'errore sia trascurabile scegliendo parametri appropriati per la dimensione del dominio finito $M$ e la precisione $\nu$.

Contributi Chiave
Il documento presenta tre contributi principali:

1. Un'Accelerazione Quadratica nella Complessità del DGS: Gli autori dimostrano un algoritmo quantistico che campiona da una distribuzione gaussiana discreta con un'accelerazione quadratica asintotica rispetto all'algoritmo classico MCMC [49]. Mentre la complessità classica scala come $O(1/\Delta)$, la complessità quantistica scala come $O(1/\sqrt{\Delta})$, dove $\Delta$ rappresenta il rapporto delle masse gaussiane. Questa accelerazione è ottenuta senza richiedere memoria quantistica esponenziale, utilizzando solo qubit polinomiali (sebbene possa fare affidamento sulla qRAM per l'accesso alla memoria classica in scenari di attacco specifici).
2. Due Varianti di Attacchi Quantistici Duali su LWE: Gli autori applicano il loro campionatore al framework "moderno" di attacco duale su LWE [42], proponendo due versioni quantistiche distinte:
   • Variante 1 (con qRAM): Sostituisce il passo di campionamento MCMC classico nella prima fase dell'attacco con il campionatore quantistico. Ciò produce un'accelerazione quadratica nella fase di campionamento ma mantiene il requisito della qRAM nella seconda fase (distinguitore basato su FFT).
   • Variante 2 (senza qRAM): Un approccio innovativo che integra direttamente il campionatore quantistico nella seconda fase dell'attacco. Combinando il campionatore con un algoritmo di stima della media quantistica (Corollario 1), questa variante evita completamente la necessità di qRAM, richiedendo solo memoria classica e quantistica polinomiale. Sebbene abbia una complessità temporale più elevata rispetto alla Variante 1, offre un vantaggio distinto nei vincoli di memoria.
3. Accelerazione Quantistica per SIS: Gli autori applicano il loro campionatore all'algoritmo per la risoluzione del problema Short Integer Solution (SIS) per qualsiasi norma [12]. Quantizzando il passo di campionamento e applicando l'amplificazione dell'ampiezza per filtrare i vettori corti, raggiungono un'accelerazione quadratica rispetto alla controparte classica (escluso il passo di pre-elaborazione BKZ).

Risultati e Analisi della Complessità

• Complessità di Campionamento: Il campionatore quantistico proposto raggiunge un conteggio di porte di circa $\tilde{O}(mM(\nu + mM + m^2r)^2)$ e un conteggio di qubit di $\tilde{O}(m(\nu + mM + m^2r))$, dove $m$ è la dimensione del reticolo. La complessità è dominata dalla radice quadrata del costo MCMC classico.
• Attacchi Duali su LWE:
  • La variante basata su qRAM migliora la complessità dell'attacco di un fattore $\sqrt{\Delta}$ rispetto all'attacco basato su MCMC classico.
  • La variante senza qRAM fornisce un'alternativa efficiente in termini di memoria, scambiando tempo per l'eliminazione dei requisiti di memoria classica esponenziale.
• SIS su Dilithium: Il documento fornisce stime approssimative per la complessità quantistica dell'attacco al problema SIS nello schema di firma Dilithium. I risultati (Tabella 2) indicano che, sebbene l'attacco quantistico riduca significativamente la complessità temporale rispetto agli attacchi classici (ad esempio, riducendo $\log_2 T_{attack}$ da 202 a 146 per il Livello 2 NIST), la complessità rimane fortemente vincolata dal passo di pre-elaborazione di riduzione della base BKZ.

Significato e Affermazioni
Gli autori collocano questo lavoro come un'espansione della "cassetta degli attrezzi per la crittanalisi quantistica". Riconoscono esplicitamente che le accelerazioni asintotiche presentate potrebbero essere difficili da realizzare nella pratica a causa dei costi intrinseci del mantenimento della qRAM e della natura sequenziale della ricerca di Grover. Il documento non afferma di violare immediatamente standard specifici NIST, ma fornisce piuttosto limiti teorici e miglioramenti algoritmici.

Il significato risiede nel:

• Fornire la prima accelerazione quantistica nota per il Campionamento Gaussiano Discreto applicabile ai regimi di parametri utilizzati nella crittanalisi basata su reticoli.
• Dimostrare che le tecniche quantistiche possono essere adattate per ridurre i requisiti di memoria negli attacchi duali, offrendo una nuova dimensione (memoria vs. tempo) per i compromessi crittanalitici.
• Stabilire un quadro per la quantizzazione di algoritmi che si affidano al campionamento MCMC, potenzialmente applicabile ad altri problemi sui reticoli oltre LWE e SIS.

Gli autori concludono che, sebbene i dettagli dell'implementazione pratica (profondità, conteggi di porte non asintotici) siano lasciati a lavori futuri, i risultati teorici offrono una base rigorosa per comprendere la durezza quantistica dei problemi sui reticoli.