Simultaneous Approximation for Lattice-Based Cryptography

1. Il Problema e il Contesto

La crittografia basata su reticoli (lattice-based cryptography) è emersa come una delle soluzioni più promettenti per la sicurezza post-quantistica, offrendo riduzioni dal caso medio al caso peggiore e capacità di omomorfismo. Tuttavia, le implementazioni naive richiedono chiavi pubbliche di grandi dimensioni.
Per ridurre la dimensione delle chiavi, sono stati introdotti i reticoli ideali (ideal lattices), che permettono una rappresentazione più compatta. Tuttavia, i reticoli ideali presentano vulnerabilità note (ad esempio, algoritmi che trovano vettori corti con fattori di approssimazione migliori rispetto ai reticoli generici) e non offrono la stessa garanzia di sicurezza "caso medio-caso peggiore" dei reticoli generali.

L'obiettivo di questo lavoro è studiare una nuova classe di reticoli, chiamati Reticoli di Approssimazione Simultanea (SA - Simultaneous Approximation), per determinare se possono offrire chiavi più piccole mantenendo la stessa durezza computazionale dei problemi sui reticoli generali.

2. Metodologia e Definizioni

L'autrice definisce i reticoli SA come reticoli di dimensione $n$ generati dalle colonne della matrice identità $I_n$ e da un vettore $x \in \mathbb{Q}^n$. Questo permette di descrivere un reticolo SA con $n+1$ interi, invece dei $n^2$ necessari per un reticolo generico.

Vengono definiti tre nuovi problemi specifici per i reticoli SA, che corrispondono alle versioni approssimate dei classici problemi sui reticoli:

1. SAP ($\gamma$): Problema di Approssimazione Simultanea (corrisponde a SVP - Shortest Vector Problem). Trovare un intero $b_0$ tale che la parte frazionaria $\{b_0 x\}$ sia un vettore corto.
2. SIAP ($\gamma$): Problema di Approssimazione di Vettori Indipendenti Brevi (corrisponde a SIVP - Shortest Independent Vector Problem). Trovare $n$ interi $b_1, \dots, b_n$ tali che i vettori $\{b_i x\}$ siano linearmente indipendenti e corti.
3. CAP ($\gamma$): Problema di Approssimazione più Vicina (corrisponde a CVP - Closest Vector Problem). Trovare un intero $b_0$ tale che $\{b_0 x - t\}$ sia vicino a un vettore target $t$.

L'Algoritmo Chiave (Algoritmo 1):
Il cuore della metodologia è un algoritmo deterministico che approssima un reticolo generico $L = M\mathbb{Z}^n$ con un reticolo SA.

• Idea: Costruire una matrice $\tilde{M}$ tale che le colonne di $M\tilde{M}$ e un vettore $M\tilde{M}x$ generino lo stesso reticolo $L$.
• Tecnica: Si utilizza una combinazione lineare della matrice aggiunta di $M$ e una matrice di perturbazione $A$ con interi piccoli. L'algoritmo modifica iterativamente gli elementi di $A$ per garantire che certi minori della matrice risultante siano coprimi (usando il Lemma 2.1 e la funzione di Jacobsthal). Questo garantisce che la struttura del reticolo sia preservata mentre si trasforma la base in una forma SA.

3. Contributi Chiave

A. Riduzioni Deterministiche e Preservazione della Durezza

L'autrice presenta riduzioni deterministiche in tempo polinomiale e spazio polinomiale dai problemi generali SVP, SIVP e CVP alle loro controparti nei reticoli SA (rispettivamente SAP, SIAP, CAP).

• Teorema 1.1: Gli algoritmi 2, 3 e 4 sono riduzioni che preservano la dimensione e il "gap" (fattore di approssimazione $\gamma$).
• Implicazione: Poiché i problemi generali sono ridotti a quelli sui reticoli SA, risolvere i problemi sui reticoli SA è almeno tanto difficile quanto risolvere i problemi sui reticoli generici. Questo dimostra che i reticoli SA sono candidati sicuri per la crittografia, a differenza dei reticoli ideali che hanno mostrato debolezze.

B. Ottimizzazione dell'Inflazione Interi (Integer Inflation)

Un fattore critico per la dimensione delle chiavi è l'"inflazione intera", ovvero quanto crescono i numeri interi durante la trasformazione da un reticolo generico a uno SA.

• Miglioramento: Il lavoro precedente di Martin (2020) aveva un'inflazione di ordine $O(n^4 \log(nk))$. VanLandingham riduce questo limite a $O(n^2 \log(nk))$.
• Ottimalità: Nella Sezione 3.4, viene dimostrato che questo limite è ottimale. Un'inflazione sub-quadratica porterebbe a un'approssimazione sub-esponenziale per i vettori più corti, il che violerebbe le ipotesi di sicurezza standard. Pertanto, il limite ottenuto è il migliore possibile senza compromettere la sicurezza.

C. Complessità Computazionale

Le riduzioni sono eseguite in tempo polinomiale, specificamente $O(n^5 \log^3(nk))$ operazioni intere (Teorema 3.11), rendendo la trasformazione fattibile per scopi crittografici.

4. Risultati Principali

1. Teorema di Durezza (NP-Hardness):

   • SIAP e CAP sono NP-difficili per qualsiasi costante $\gamma$ sotto le norme $\ell_1, \ell_2, \ell_\infty$.
   • SAP è NP-difficile sotto la norma $\ell_\infty$ per qualsiasi $\gamma$, e sotto riduzioni randomizzate per $\ell_1$ e $\ell_2$ con $\gamma < 2$ e $\gamma < 2^{1/2}$ rispettivamente.
   • Questo conferma che i problemi sui reticoli SA ereditano la durezza computazionale dei problemi sui reticoli generici.

2. Preservazione del Gap:
   Le riduzioni dimostrano che se esiste un algoritmo efficiente per risolvere SAP, SIAP o CAP con un certo fattore di approssimazione, allora esisterebbe un algoritmo efficiente per risolvere SVP, SIVP o CVP con lo stesso fattore.

3. Analisi Statistica:
   L'analisi sperimentale mostra che le perturbazioni necessarie per rendere coprimi gli elementi sono molto piccole in media (spesso 0 o 1), suggerendo che il caso peggiore teorico è raro e che l'efficienza pratica potrebbe essere ancora migliore.

5. Significato e Implicazioni per la Crittografia

• Nuova Base per la Crittografia: Questo lavoro stabilisce i reticoli SA come una nuova classe di strutture matematiche promettenti per la crittografia basata su reticoli. Offrono il potenziale per chiavi pubbliche più piccole (grazie alla rappresentazione compatta di $n+1$ interi) senza sacrificare la sicurezza teorica garantita dalle riduzioni dal caso peggiore.
• Superamento dei Limiti dei Reticoli Ideali: A differenza dei reticoli ideali, che hanno mostrato vulnerabilità strutturali, i reticoli SA sono dimostrati essere "tanto duri" quanto i reticoli generici.
• Efficienza Pratica: La riduzione dell'inflazione intera da $O(n^4)$ a $O(n^2)$ è cruciale. Poiché la dimensione della chiave crittografica dipende direttamente dalla grandezza dei numeri interi utilizzati, questa ottimizzazione rende i sistemi basati su reticoli SA molto più pratici per l'implementazione reale rispetto alle riduzioni precedenti.

In sintesi, il paper di VanLandingham fornisce un fondamento teorico solido per l'uso dei reticoli di Approssimazione Simultanea nella crittografia post-quantistica, dimostrando che è possibile ottenere una compressione delle chiavi mantenendo la massima sicurezza computazionale nota.