Mind the Gap? Not for SVP Hardness under ETH!

Titolo e Contesto

Il lavoro, intitolato "Mind the Gap? Not for SVP Hardness under ETH!", è stato scritto da Divesh Aggarwal, Rishav Gupta, Aditya Morolia e Chuanqi Zhang. L'articolo affronta la complessità computazionale dei problemi fondamentali sui reticoli (lattice problems) sotto l'ipotesi del tempo esponenziale (ETH - Exponential Time Hypothesis).

L'obiettivo principale è dimostrare la durezza (hardness) di approssimazione per problemi come il Closest Vector Problem (CVP), il Shortest Vector Problem (SVP) e il Bounded Distance Decoding (BDD) in norme $\ell_p$, senza fare affidamento sull'ipotesi più forte Gap-ETH, ma utilizzando solo l'ETH standard.

1. Il Problema e il Contesto Teorico

I problemi sui reticoli sono centrali nella crittografia post-quantistica e nella teoria della complessità.

• SVP (Shortest Vector Problem): Trovare il vettore non nullo più corto in un reticolo.
• CVP (Closest Vector Problem): Trovare il vettore del reticolo più vicino a un vettore target dato.
• BDD (Bounded Distance Decoding): Una variante di CVP dove il target è garantito essere molto vicino al reticolo.

Fino a questo lavoro, i risultati di durezza fine-grained (che escludono algoritmi sub-esponenziali $2^{o(n)}$) per questi problemi erano noti principalmente sotto l'ipotesi Gap-ETH (una versione rafforzata dell'ETH che assume la difficoltà di distinguere istanze soddisfacibili da quelle non soddisfacibili per problemi di soddisfacimento vincolare). L'ETH standard afferma solo che 3SAT non può essere risolto in tempo $2^{o(n)}$, ma non garantisce direttamente la durezza per le versioni con "gap" (approssimazione).

Il lavoro si basa su una recente svolta di Bitansky et al. [BHIRW24], che ha fornito una riduzione polinomiale da 3SAT alla versione con gap del problema MAXLIN (soddisfacimento di equazioni lineari su campi finiti). Questo implica che MAXLIN è ETH-hard.

2. Metodologia e Tecniche Chiave

Gli autori costruiscono una catena di riduzioni deterministiche e randomizzate per trasferire la durezza da MAXLIN ai problemi sui reticoli.

A. Da MAXLIN a CVP (Deterministico)

Per il CVP in norma $\ell_p$ (per ogni $p \in [1, \infty)$), gli autori forniscono una riduzione deterministica diretta da MAXLIN.

• Costruzione: Dato un'istanza di MAXLIN con matrice $M$ e vettore $v$, costruiscono una matrice del reticolo $B = [M \mid 2I_m]$ e un vettore target $t = v$.
• Meccanismo: L'aggiunta di $2I_m$ forza le distanze a essere calcolate modulo 2. Se l'istanza MAXLIN è un "SÌ" (molte equazioni soddisfatte), esiste un vettore del reticolo vicino a $t$. Se è un "NO" (poche equazioni soddisfatte), tutti i vettori del reticolo sono lontani da $t$ di un fattore $\gamma > 1$.
• Risultato: Si ottiene una riduzione Karp deterministica che stabilisce la durezza ETH per CVP$_{p,\gamma}$.

B. Da CVP a SVP (Randomizzato e Geometrico)

La contribuzione principale riguarda il SVP per $p \in (2, \infty)$. La riduzione da CVP a SVP è più complessa e richiede una proprietà geometrica nuova.

• Il Problema: Le riduzioni precedenti (es. Aggarwal & Stephens-Davidowitz [AS18]) usavano gadget basati su insiemi esatti (ExactSetCover) che non si adattavano direttamente alle istanze MAXLIN.
• La Soluzione (Gadget Densi Localmente): Gli autori dimostrano una nuova proprietà geometrica del reticolo intero $\mathbb{Z}^n$ nella norma $\ell_p$ per $p > 2$.
  • Dimostrano che il numero di vettori del reticolo vicini al vettore $\frac{1}{2}\mathbf{1}_n$ (tutti gli elementi uguali a 1/2) è esponenzialmente più grande del numero di vettori corti vicini all'origine.
  • Strumento Matematico: Questa proprietà è stabilita analizzando la funzione Theta $\Theta_p(\tau, t) = \sum_{z \in \mathbb{Z}} e^{-\tau |z-t|^p}$. Usano l'analisi di Fourier e la formula di somma di Poisson per dimostrare che esiste un $\tau > 0$ tale che $\Theta_p(\tau, 1/2) > \Theta_p(\tau, 0)$ per ogni $p > 2$. Questo implica che la "densità" dei punti attorno a $1/2$ supera quella attorno a 0.
• Riduzione Randomizzata: Utilizzando questo gadget, trasformano un'istanza di CVP in un'istanza di SVP. Applicano un algoritmo di sparsificazione del reticolo (lattice sparsification) per campionare un sottoreticolo casuale. Se l'istanza originale era un "SÌ", il sottoreticolo manterrà vettori corti con alta probabilità; se era un "NO", tutti i vettori corti verranno eliminati.

C. Da CVP a BDD

Gli autori migliorano le riduzioni esistenti da CVP a BDD (Bounded Distance Decoding).

• Dimostrano una riduzione decisionale-da-ricerca da CVP$_{p,\gamma}$ a BDD$_{p,\alpha}$ per qualsiasi $\alpha > \alpha^\ddagger_p$, dove $\alpha^\ddagger_p$ è una soglia calcolabile esplicitamente che dipende da $p$ (con $\alpha^\ddagger_p = 1$ per $p \in [1, 2]$ e $\alpha^\ddagger_p \to 1/2$ per $p \to \infty$).
• Questa riduzione è più semplice di quelle precedenti e funziona direttamente su istanze CVP costruite da MAXLIN, ottenendo risultati di durezza ETH per BDD.

3. Risultati Principali

I teoremi principali del lavoro sono:

1. Durezza ETH per CVP: Per ogni $p \in [1, \infty)$, esiste una costante $\gamma > 1$ tale che CVP$_{p,\gamma}$ non ammette algoritmi in tempo $2^{o(n)}$ a meno che l'ETH sia falsa.
2. Durezza ETH per SVP: Per ogni $p \in (2, \infty)$, esiste una costante $\gamma > 1$ tale che SVP$_{p,\gamma}$ non ammette algoritmi in tempo $2^{o(n)}$ (randomizzati) a meno che l'ETH randomizzata sia falsa.
   • Nota: Il caso $p=2$ rimane un problema aperto, sebbene la durezza per $p \in [1, 2)$ segua da tecniche di embedding delle norme.
3. Durezza ETH per BDD: Per ogni $p \in [1, \infty)$ e $\alpha > \alpha^\ddagger_p$, non esistono algoritmi in tempo $2^{o(n)}$ per BDD$_{p,\alpha}$ a meno che l'ETH randomizzata sia falsa.
4. Codici Lineari: Come corollario, si ottiene la durezza ETH per il problema della distanza minima (MDP) e il problema del vettore più vicino nei codici (NCP).

4. Significato e Impatto

• Colmare il divario tra ETH e Gap-ETH: Questo lavoro è significativo perché dimostra che risultati di durezza fine-grained precedentemente noti solo sotto l'assunzione forte di Gap-ETH possono essere ottenuti sotto l'assunzione più debole e standard di ETH. Questo rafforza la fiducia nella difficoltà intrinseca di questi problemi.
• Implicazioni Crittografiche: Poiché molti schemi crittografici post-quantistici (come quelli basati su LWE) si basano sulla durezza dei problemi sui reticoli, questi risultati forniscono garanzie teoriche più solide contro algoritmi sub-esponenziali, che potrebbero minacciare la sicurezza pratica di questi schemi.
• Nuovi Strumenti Matematici: La dimostrazione della proprietà di densità del reticolo intero per $p > 2$ tramite l'analisi della funzione Theta e la formula di Poisson rappresenta un contributo tecnico indipendente di valore, con potenziali applicazioni in altre aree della geometria dei numeri e della teoria dei reticoli.

In sintesi, il paper risolve un problema aperto importante nella complessità computazionale, fornendo prove robuste della durezza dei problemi fondamentali sui reticoli sotto ipotesi di complessità standard, e introduce nuove tecniche geometriche e analitiche per gestire le riduzioni tra questi problemi.