Deterministic and Efficient Ideal Arithmetic via Two-Element Representations

Sintesi Tecnica: Rappresentazione Deterministica ed Efficiente di Ideali tramite Rappresentazioni a Due Elementi

Enunciato del Problema
Nella teoria computazionale dei numeri e nella crittografia post-quantistica (specificamente nel problema Ring Learning-With-Errors, o RLWE), l'aritmetica degli ideali efficiente è essenziale. Sebbene sia un fatto teorico noto che ogni ideale frazionario in un campo numerico $K$ possa essere generato da due elementi sul suo anello degli interi $\mathcal{O}_K$, trovare una tale rappresentazione è computazionalmente impegnativo. Gli algoritmi esistenti sono o probabilistici o impraticabili per input di dimensioni crittografiche a causa della loro dipendenza dalla costosa fattorizzazione dei primi dei norme degli ideali o del discriminante del polinomio definente. Inoltre, determinare se un ideale sia principale (generato da un singolo elemento) rimane un problema aperto senza un algoritmo efficiente noto.

Il problema specifico affrontato è: dato un ideale in $\mathcal{O}_K$ definito da un insieme di generatori (spesso derivati da una base $\mathbb{Z}$ o da una tupla $(N, a(\alpha), b(\alpha))$ dove $N$ è un intero composto grande), trovare due elementi $M, c(\alpha)$ tali che l'ideale sia generato da $M\mathcal{O}_K + c(\alpha)\mathcal{O}_K$. Gli autori si concentrano sul caso difficile in cui $N$ è un numero composto grande privo di piccoli fattori primi, rendendo la fattorizzazione intrattabile.

Metodologia
Il documento propone un algoritmo deterministico in tempo polinomiale che evita la fattorizzazione in ideali primi e la casualità. L'approccio è diviso in tre fasi, basandosi fortemente sull'aritmetica dei polinomi su $\mathbb{Z}/N\mathbb{Z}$ e su una versione generalizzata del criterio di Dedekind.

1. Fase 1: Fattorizzazione e Normalizzazione dell'Ideale
   L'algoritmo tenta di ridurre l'ideale di input $(N, a(\alpha), b(\alpha))$ utilizzando un algoritmo di tipo Euclide su polinomi su $\mathbb{Z}/N\mathbb{Z}$.

   • Se i coefficienti principali sono unità in $\mathbb{Z}/N\mathbb{Z}$, l'algoritmo calcola il massimo comun divisore (MCD) dei polinomi, riducendo l'ideale a una forma a due elementi $(N, c(\alpha))$.
   • Se viene incontrato un divisore dello zero non banale (indicando che $N$ è composto), l'algoritmo fattorizza $N$ in componenti coprime e processa ricorsivamente i relativi ideali.
   • Per i casi in cui $N$ è una potenza perfetta ($N = N_0^e$), l'algoritmo gestisce un caso degenero eseguendo l'algoritmo di Euclide per produrre un ideale della forma $(N^e, a_1(x), N d_1(x), \dots)$. Successivamente, utilizza il polinomio definente $f(x)$ per garantire che $a_1(x)$ sia un fattore di $f(x)$ modulo $N$.
   • L'output di questa fase è un prodotto di ideali in "forme speciali": o semplici ideali a due elementi $(N_i, a_i(\alpha))$ o ideali con una struttura specifica che coinvolge potenze di $N$ e molteplici generatori.

2. Fase 2: Gestione delle Forme Speciali e Moltiplicazione
   Questa fase affronta gli ideali della forma $(N^e, a(\alpha), N I)$ dove $N$ non è una potenza perfetta.

   • Criterio di Dedekind Generalizzato: Un contributo tecnico chiave è un criterio di Dedekind generalizzato (Lemma 5 e Teorema 3). Questo permette all'algoritmo di trovare un polinomio monico $\tilde{a}(x)$ tale che $f(x) = \tilde{f}_1(x)N + \tilde{a}(x)A(x)$ con specifiche condizioni di coprimalità $(\tilde{a}(x), \tilde{f}_1(x), N) = 1$.
   • Divisione e Moltiplicazione di Ideali: Utilizzando questa forma, l'algoritmo costruisce un elemento $\bar{a}(\alpha)$ tale che $\tilde{a}(\alpha)\bar{a}(\alpha) \equiv N \pmod{N^s}$. Questa proprietà consente la divisione efficiente degli ideali e la moltiplicazione degli ideali in rappresentazione a due elementi. Specificamente, dimostra che $(N, \tilde{a}_1(\alpha))(N, \tilde{a}_2(\alpha)) = (N^2, \tilde{a}_1(\alpha)\tilde{a}_2(\alpha))$, a condizione che i generatori soddisfino il criterio di Dedekind generalizzato.
   • L'algoritmo riduce iterativamente gli ideali complessi in prodotti di semplici ideali a due elementi $(N_i, \tilde{a}_i(\alpha))$.

3. Fase 3: Ricomposizione tramite il Teorema Cinese del Resto
   Una volta che l'ideale di input è stato fattorizzato in un prodotto di ideali a due elementi pairwise coprimi $(N_i, a_i(\alpha))$, l'algoritmo utilizza il Teorema Cinese del Resto (Lemma 2) per moltiplicarli nuovamente in una singola rappresentazione a due elementi $(M, c(\alpha))$.

Contributi Chiave

• Algoritmo Deterministico in Tempo Polinomiale: Il documento presenta il primo algoritmo deterministico per trovare una rappresentazione a due elementi per gli ideali in campi monogeni (e campi non monogeni dove la norma dell'ideale è coprima con l'indice $[\mathcal{O}_K : \mathbb{Z}[x]/(f)]$) senza richiedere la fattorizzazione in primi della norma.
• Criterio di Dedekind Generalizzato: Gli autori introducono una versione generalizzata del criterio di Dedekind che funziona per moduli composti $N$. Ciò consente l'identificazione di generatori polinomiali idonei che facilitano l'efficace moltiplicazione e divisione degli ideali senza conoscere i fattori primi di $N$.
• Gestione dei Moduli Composti: A differenza dei metodi precedenti (ad es. Pohst-Zassenhaus) che si basano sulla fattorizzazione in primi, questo metodo gestisce direttamente $N$ composto. Dimostra che trovare i fattori di $N$ non è necessario e, anzi, rallenta il processo se l'obiettivo è semplicemente trovare la rappresentazione.
• Efficienza: L'algoritmo sostituisce le costose operazioni su matrici integrali (reticoli) con l'aritmetica sui polinomi, riducendo significativamente la complessità di spazio e di tempo per input di grandi dimensioni.

Risultati e Complessità
Il risultato principale (Teorema 1) afferma che per un campo monogeno di grado $n$, il problema della rappresentazione a due elementi può essere risolto in tempo $\text{poly}(n, \log N)$.

• Quando $N$ è privo di quadrati (square-free), la complessità è $O(n^2 \log N \cdot \omega(N))$, dove $\omega(N)$ è il numero di fattori primi distinti di $N$. Poiché $\omega(N)$ è mediamente $\log \log N$, la complessità è comparabile agli algoritmi probabilistici ma è deterministica.
• L'algoritmo è pratico per polinomi monogeni, che includono i polinomi ciclotomici ampiamente utilizzati nella crittografia basata su reticoli (ad es. NewHope, Crystals-Kyber).
• Se l'algoritmo fallisce nel produrre una rappresentazione, fornisce un certificato che il campo non è monogeno (o che la condizione dell'indice non è soddisfatta).

Significatività e Rivendicazioni
Il documento sostiene di aver risolto una di lunga data inefficienza nell'aritmetica degli ideali rimuovendo la dipendenza dalla fattorizzazione in primi e dalla casualità.

• Rilevanza Crittografica: Il lavoro supporta direttamente l'implementazione di schemi crittografici post-quantistici basati su reticoli di ideali, in particolare quelli che utilizzano campi ciclotomici.
• Avanzamento Teorico: Generalizza l'algoritmo di Pohst-Zassenhaus (limitato alle norme prime) a interi composti arbitrari.
• Modestia: Gli autori osservano che, sebbene l'algoritmo funzioni per tutti gli ideali in campi monogeni, estenderlo a campi non monogeni richiede che la norma dell'ideale sia coprima con l'indice. Identificano inoltre un problema aperto: trovare una rappresentazione polinomiale monogena per un dato campo numerico in tempo polinomiale, il che è attualmente ostacolato dai divisori inessenziali del discriminante. Il documento non pretende di risolvere il problema generale dell'ideale principale o di fattorizzare grandi interi, bensì di aggirare questi problemi difficili per il compito specifico della rappresentazione degli ideali.