Sintesi Tecnica: Scoprire Strategie di Riduzione di Reticoli tramite Self-Play

Definizione del Problema

La riduzione di reticoli è un problema fondamentale nella matematica computazionale e nella crittografia, che sostiene la sicurezza degli schemi crittografici post-quantistici. L'algoritmo Lenstra-Lenstra-Lovász (LLL) è il metodo standard per la riduzione della base del reticolo in tempo polinomiale. Tuttavia, sebbene LLL garantisca un tempo di esecuzione e un limite specifici sulla lunghezza dei vettori, i suoi output sono spesso subottimali nella pratica, in particolare all'aumentare della dimensione del reticolo. L'algoritmo si basa su un'euristica artigianale, la condizione di Lovász, per decidere quando scambiare i vettori della base. Questa condizione assicura una diminuzione monotona di una funzione potenziale, ma non è necessariamente ottimale per ottenere la più forte possibile riduzione.

La sfida centrale affrontata in questo lavoro è se un approccio basato sui dati possa scoprire una politica di sequenziamento per le operazioni primitive di LLL (riduzione dimensionale e scambi adiacenti) che produca una qualità di riduzione strettamente superiore rispetto all'algoritmo classico, senza espandere lo spazio delle azioni per includere oracoli più complessi (come i risolutori esatti del problema del vettore più corto, SVP).

Metodologia: Delta-Star

Gli autori formulano la riduzione di reticoli come un processo decisionale di Markov (MDP) a singolo giocatore e impiegano un framework di Deep Reinforcement Learning (RL) aumentato da Monte Carlo Tree Search (MCTS).

1. Formulazione MDP

• Spazio degli Stati: Lo stato include la matrice della base corrente $B$, la sua ortogonalizzazione di Gram-Schmidt (GSO), i vettori e i coefficienti, la posizione del cursore $k$ (che indica la riga corrente in fase di elaborazione) e i passi rimanenti.
• Spazio delle Azioni: L'agente è limitato alle esatte azioni primitive dell'algoritmo LLL per garantire un confronto equo:
  • MOVEUP/MOVEDOWN: Regolazione della posizione del cursore.
  • SWAP: Scambio di righe adiacenti della base $b_k$ e $b_{k-1}$.
  • SIZEREDUCE: Sottrazione di multipli interi di righe precedenti per soddisfare la condizione di riduzione dimensionale ($|\mu_{j,k}| \le 1/2$).
• Funzione di Ricompensa: Una ricompensa normalizzata è definita sulla base della riduzione relativa nel log-metrica delle misure di qualità (Difetto di Ortogonalità $\delta$ e Potenziale LLL $\Phi$). Una ricompensa ibrida interpola tra questi due obiettivi.

2. MCTS a Orizzonte Adattivo

Gli autori introducono un nuovo meccanismo di MCTS a Orizzonte Adattivo per migliorare l'efficienza della ricerca:

• Predizione Multi-Step: La rete neurale predice una policy e un valore per un orizzonte di $H$ passi futuri simultaneamente.
• Espansione con Gate di Entropia: Invece di espandere l'albero un nodo alla volta, l'algoritmo percorre il percorso "greedy" predetto dalla rete. Ad ogni passo $k$, calcola l'entropia di Shannon $H[p(k)]$ della policy predetta.
  • Se l'entropia è bassa (alta confidenza), l'algoritmo percorre automaticamente il passo senza ramificazioni, ammortizzando i costi di inferenza.
  • Se l'entropia supera una soglia $\tau$ (indicando un vero punto decisionale), l'espansione si arresta e l'albero si ramifica in quel nodo.
• Questo meccanismo permette alla ricerca di saltare sequenze deterministiche e concentrare le risorse computazionali sui punti decisionali incerti.

3. Architettura della Rete Neurale

• Backbone: Una rete residua profonda (ResNet) con una finestra di lookback per catturare la storia temporale.
• Tensore di Osservazione: Codifica la base, la GSO, i coefficienti, il tempo rimanente e la posizione del cursore in un tensore a 5 canali.
• Testine (Heads): La rete produce una testa di policy (probabilità per $H$ passi) e una testa di valore (ritorni attesi per $H$ passi).
• Addestamento: Il modello è addestrato tramite self-play in stile AlphaZero, minimizzando la cross-entropy tra la policy predetta e i conteggi delle visite MCTS, e l'Errore Quadratico Medio tra i valori predetti e i ritorni dell'episodio.

4. Configurazione dell'Addestramento

L'agente, chiamato Delta-Star, è addestrato esclusivamente su piccoli reticoli $q$-ary con dimensione di base $n=8$ e modulo $q=251$. L'addestramento utilizza una pipeline distribuita con worker di self-play, server di inferenza e un learner centrale.

Risultati Chiave

1. Qualità di Riduzione Superiore

Delta-Star raggiunge un fattore Hermite radice ($\delta_0$) e un difetto di ortogonalità significativamente migliori rispetto all'algoritmo LLL classico attraverso varie dimensioni.

• Alla dimensione di addestramento ($n=8$), Delta-Star converge a un $\delta_0$ leggermente inferiore ($\approx 1.00657$) rispetto a LLL ($1.00660$).
• Fondamentalmente, il divario di prestazioni si amplia all'aumentare della dimensione. A $n=32$, Delta-Star raggiunge $\delta_0 = 1.0149$, superando LLL ($1.0171$) e avvicinandosi alla qualità di BKZ-$\beta$ ($1.0125$), nonostante non sia mai stato addestrato su dimensioni superiori a 8.

2. Generalizzazione Zero-Shot

Il modello dimostra una robusta generalizzazione zero-shot:

• Dimensione: Si generalizza a dimensioni non viste fino a $n=32$.
• Modulo: Si generalizza a moduli $q$ non visti nell'intervallo tra $\sim 20$ e $5000$.
• Ciò è ottenuto attraverso l'uso di tensori di osservazione $q$-normalizzati e pooling adattivo nell'architettura della rete.

3. Efficienza Algoritmica

Delta-Star richiede meno operazioni di riga primitive rispetto a LLL per raggiungere una qualità di riduzione comparabile o migliore.

• A $n=8$, utilizza solo il 55% delle operazioni di riga richieste da LLL.
• Ad dimensioni più elevate ($n=26, 32$), mantiene una traiettoria strettamente migliore durante tutto il processo di riduzione, convergendo più velocemente e verso uno stato finale migliore.
• Gli autori notano che, sebbene l'inferenza della rete neurale sia più lenta in termini di tempo di esecuzione (wall-clock time) rispetto a un'implementazione classica, la riduzione del numero di operazioni elementari indica una strategia sottostante più efficiente.

Significato e Rivendicazioni

Il documento sostiene di dimostrare che il deep reinforcement learning può scoprire strategie di riduzione strettamente superiori e generalizzabili interagendo con lo spazio delle azioni primitive di LLL.

• Oltre le Euristiche Artigianali: Il lavoro mostra che la rigida condizione di Lovász non è ottimale e che una policy appresa può navigare lo spazio degli stati in modo più efficace.
• Scalabilità: L'approccio sfida la nozione che le strategie di riduzione dei reticoli debbano essere riprogettate per diverse dimensioni, mostrando che un modello addestrato su istanze piccole può scalare a dimensioni significativamente più grandi e non viste.
• Scoperta di Algoritmi: Gli autori posizionano questo lavoro all'interno del paradigma della scoperta di algoritmi guidata dall'IA (simile ad AlphaTensor e AlphaDev), suggerendo che gli algoritmi fondamentali basati su euristiche nella matematica computazionale possono essere ottimizzati scoprendo percorsi decisionali ottimali tramite RL.
• Direzioni Future: Il documento conclude che i pesi della policy appresa codificano un algoritmo deterministico ed efficiente. Un obiettivo primario futuro è quello di estrarre e formalizzare questo algoritmo classico dalla rete neurale. Inoltre, la metodologia potrebbe essere estesa per migliorare gli algoritmi basati su blocchi come BKZ.

Gli autori rimangono modesti riguardo all'attuale implementazione, riconoscendo che la rete neurale è più lenta per operazione rispetto al codice classico, e sottolineano che il valore del lavoro risiede nel caratterizzare la struttura di una strategia di riduzione più efficiente piuttosto che nelle prestazioni di runtime immediate.