Sintesi Tecnica: Complessità della Risoluzione di Sistemi di Equazioni dello Stesso Grado

Enunciato del Problema

La sicurezza di numerosi schemi crittografici, in particolare nella crittografia multivariata e nei contesti post-quantum, si basa sulla difficoltà computazionale di risolvere sistemi di equazioni polinomiali multivariate su campi finiti. La complessità della risoluzione di tali sistemi tramite metodi di base di Gröbner è governata principalmente dal grado di regolarità ($d_{reg}$) e dal grado di risoluzione (solving degree). Sebbene il grado di regolarità fornisca un limite superiore alla complessità dei calcoli della base di Gröbner, esso è spesso difficile da calcolare o stimare per sistemi di dimensioni crittografiche.

La pratica comune si affida all'assunzione euristica che i sistemi siano semiregolari (o crittograficamente semiregolari), il che fornisce formule esplicite per il grado di regolarità. Tuttavia, tale assunzione non è sempre valida; esistono scelte di parametri e campi in cui non esiste una sequenza semiregolare. Di conseguenza, vi è la necessità di limiti superiori provati, non euristici, sul grado di regolarità e sul grado di risoluzione che si applichino a sistemi in cui il grado di regolarità è finito, senza fare affidamento sull'assunzione di semiregolarità.

Metodologia

Gli autori approcciano il problema utilizzando strumenti dell'algebra commutativa, concentrandosi specificamente su sistemi in cui l'ideale generato dalle parti di grado massimo dei polinomi contiene una sequenza regolare di $n$ polinomi in un dato grado $D$.

1. Framework: Il documento considera un sistema $F = \{f_1, \dots, f_m\}$ di $m$ polinomi in $n$ variabili su un campo $F$. L'analisi assume che le parti di grado massimo $f_1^{top}, \dots, f_m^{top}$ siano linearmente indipendenti e che il sistema sia regolare nel grado $D$ (ovvero l'ideale generato dalle parti di grado massimo contiene una sequenza regolare di $n$ polinomi di grado $D$).
2. Riduzione agli Ideali LPP: Per limitare la regolarità di Castelnuovo-Mumford (che equivale al grado di regolarità quando questo è finito), gli autori utilizzano la Congettura di Eisenbud-Green-Harris (EGH). Questa congettura postula che, tra tutti gli ideali omogenei che contengono una sequenza regolare di gradi specifici, l'ideale Lex-Plus-Powers (LPP) possieda la regolarità massima.
3. Analisi Combinatoria: Gli autori costruiscono specifici ideali LPP associati ai parametri dati ($n, m, D$). Analizzando la struttura di questi ideali sotto l'ordine lessicografico, determinano la regolarità dell'ideale LPP, che funge da limite superiore per la regolarità del sistema originale (condizionatamente alla Congettura EGH).
4. Equazioni di Campo: La metodologia viene estesa a sistemi aumentati dalle equazioni di campo ($x_i^q - x_i$), il che è fondamentale per i sistemi su campi finiti $\mathbb{F}_q$, in particolare quando il grado delle equazioni $D$ è maggiore o uguale alla dimensione del campo $q$.

Contributi Chiave e Risultati

1. Limiti Superiori per Sistemi Regolari nel Grado $D$ (Senza Equazioni di Campo)

Il Teorema 23 fornisce un limite superiore netto per il grado di regolarità di un sistema di $m$ equazioni di grado $D$ in $n$ variabili, assumendo che il sistema sia regolare nel grado $D$.

• Il limite dipende dal numero di equazioni ($m$), dalle variabili ($n$) e dal grado ($D$).
• La formula prevede l'identificazione di interi unici $k$ e $t$ tali che $m-n$ ricada in un intervallo specifico definito da somme combinatorie ($\sigma_{k,t}$).
• Il limite risultante è: $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$.
• Questo limite è stretto (sharp) per tutti i valori di $m, n, D$ ed è raggiunto da sistemi in cui le parti di grado massimo formano un particolare ideale LPP.

Il Corollario 27 traduce questo risultato in un limite superiore sul grado di risoluzione per algoriti mutanti:
$$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$$

2. Limiti Superiori per Sistemi con Equazioni di Campo

Il documento affronta il caso in cui le equazioni di campo vengono aggiunte al sistema, operazione essenziale quando $D \ge q$.

• Proposizione 31: Per sistemi molto sovradeterminati (dove $m$ eccede la dimensione dello spazio dei polinomi modulo le equazioni di campo), il grado di regolarità è esattamente $D$.
• Teorema 33: Per sistemi in cui $q \le D \le n(q-1)$ e le parti di grado massimo sono linearmente indipendenti modulo le equazioni di campo, gli autori forniscono un limite superiore sul grado di regolarità.
  • Il limite è derivato dall'analisi della posizione del $m$-esimo monomio nell'ordinamento lessicografico dei monomi di grado $D$ modulo $(x_1^q, \dots, x_n^q)$.
  • Il limite è espresso in termini di $B = q - t + (n - k)(q - 1)$, dove $k$ e $t$ sono determinati dall'intervallo contenente $m$.
  • A seconda di specifiche condizioni riguardanti $m, D$ e $t$, il limite è $B$ oppure $B-1$.

Il Corollario 34 specializza questi risultati per i sistemi binari ($q=2$), fornendo formule semplificate per il grado di regolarità e il grado di risoluzione per sistemi di grado $D$ su $\mathbb{F}_2$.

3. Applicazione a Schemi Specifici

Gli autori applicano i loro limiti a schemi crittografici concreti:

• Cubic Simple Matrix: Derivano un limite provato $d_{reg} \le 2n - 1$, che rappresenta il primo limite provato per questo sistema, ponendosi in contrasto con le precedenti stime euristiche.
• Unbalanced Oil and Vinegar (UOV): I limiti sono applicati a sistemi UOV su $\mathbb{F}_2$, dimostrando come si comporti il grado di regolarità quando vengono incluse le equazioni di campo.

Significato e Rivendicazioni

Il documento rivendica la sua importanza principalmente nel fornire limiti provati e non euristici sulla complessità della risoluzione di sistemi polinomiali.

• Affidabilità: A differenza delle stime basate sull'assunzione di semiregolarità (che può fallire per determinati parametri), questi limiti valgono per qualsiasi sistema in cui il grado di regolarità sia finito e il sistema sia regolare in un dato grado.
• Generalità: I risultati si applicano a sistemi su campi arbitrari e coprono entrambi i casi, con e senza equazioni di campo.
• Nitidezza (Sharpness): I limiti sono descritti come "stretti" (sharp), il che significa che sono raggiunti da sistemi specifici (ideali LPP), offrendo una stima realistica del caso peggiore per l'analisi della sicurezza.
• Limitazioni: Gli autori riconoscono esplicitamente che i loro limiti sono generalmente meno stretti (ovvero più alti) rispetto a quelli ottenuti sotto l'euristica della semiregolarità. Tuttavia, sostengono che questo compromesso sia necessario per evitare assunzioni non provate, in particolare in scenari in cui non esistono sequenze semiregolari.

Il lavoro non propone nuovi algoritmi o implementazioni sperimentali, ma stabilisce i limiti teorici della complessità degli esistenti metodi di base di Gröbner (sia standard che mutanti) per una vasta classe di sistemi polinomiali rilevanti per la crittografia.