RICERCA ITALIANA     

Gruppi, Algebre di Lie, Crittografia

Università degli Studi de L'Aquila

Abstract

Nel nostro lavoro precedente abbiamo iniziato un progetto di classificazione per i pro-p-gruppi, e abbiamo mostrato che un progetto di classificazione simile ha senso anche per le algebre di Lie modulari just infinite.
La classificazione di una classe cruciale di algebre di Lie graduate, quelle thin, è stata portata avanti da una delle nostre unità in questi anni, con continui progressi.
Come conseguenza della crescente interazione con altri gruppi di ricerca internazionali, e come naturale evoluzione dei nostri interessi di ricerca, abbiamo recentemente aperto prospettive radicalmente nuove su questo tema di ricerca.

Le due unità hanno cominciato a occuparsi di problemi di crittografia. Uno sguardo alla letteratura recente del settore mostra un considerevole spazio per le tecniche algebriche.
L'interazione si svolge nelle due direzioni: l'uso di strumenti algebrici fornisce una migliore comprensione delle problematiche crittografiche, che a loro volta suggeriscono questioni algebriche di interesse indipendente. Uno degli scopi di questo progetto è confrontare e coordinare il lavoro delle due unità in questo settore, continuando così una lunga tradizione di collaborazione.

Allo stesso tempo il nostro gruppo ha acquisito un nuovo ricercatore (de Graaf). Questa acquisizione rinforza la linea di ricerca che si riferisce allo studio delle algebre di Lie, accentuandone l'aspetto computazionale.
Gli esperimenti computazionali hanno sempre avuto un ruolo importante nel nostro lavoro: utilizziamo l'evidenza sperimentale ottenuta mediante le costruzioni con il calcolatore come guida per il nostro lavoro di ricerca. Allo stesso tempo abbiamo fornito, in alcuni casi, contributi originali per i programmi di calcolo algebrico esistenti. Intendiamo anche enfatizzare questo secondo aspetto, con particolare attenzione al calcolo parallelo (collaborazione con l'università di St. Andrews per la produzione di librerie GAP).

Questo programma di ricerca ha quindi due obiettivi fondamentali: da una parte vogliamo portare avanti con rinnovata lena, alla luce delle nuove idee, la nostra attività sui pro-p-gruppi e le algebre di Lie; dall'altra vogliamo dedicare grande attenzione ai nuovi temi di ricerca, per incrementare la nostra produttività in quei settori.
In questo crediamo che la nostra lunga esperienza di stretta e produttiva collaborazione risulterà preziosa.
Crediamo che questa esperienza sia la migliore garanzia di successo del nostro progetto. <<<

Coordinatore Scientifico del Programma di Ricerca

Carlo Maria Scoppola Università degli Studi de L'AQUILA

Obiettivo del Programma di Ricerca

Lo scopo di questo programma di ricerca è duplice: da una parte vogliamo sviluppare la nostra attività nei temi che abbiamo studiato negli ultimi anni, cioè i pro-p-gruppi e le algebre di Lie graduate, alla luce delle nuove prospettive apertesi come effetto dell'espansione dei nostri contatti internazionali; dall'altra, poiche' abbiamo cominciato ad estendere i nostri interessi e la nostra attività di ricerca lavorando a nuovi temi, quali alcuni aspetti algebrici in crittografia e la computazione nelle algebre di Lie, vogliamo rafforzare il nostro impegno su questi nuovi argomenti. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

(Questo punto e' necessariamente l'unione dei due punti corrispondenti sui moduli B. Per chiarezza indichiamo, per ciascun argomento, l'unita' al quale si riferisce)

La costruzione di un anello di Lie graduato associato ad una filtrazione di un pro-p-gruppo (la somma diretta dei quozienti della filtrazione dotata della struttura di Lie ereditata dalla struttura di commutazione del gruppo) risale a classici lavori di Magnus, Zassenhaus e Lazard.

Il nostro precedente lavoro mostra frequenti applicazioni di questa costruzione. Il nostro interesse principale, quando affrontammo questo filone di ricerca qualche anno fa, era centrato sui (pro-)p-gruppi thin, cioè (pro-)p-gruppi (topologicamente) 2-generati in cui ogni sottogruppo normale (aperto) giace, nel reticolo dei sottogruppi normali (aperti), tra due termini consecutivi della serie centrale discendente. In [CMNS], [CMN], [M99], [GMSjgt] sono studiati i (pro-)p-gruppi thin.

La proprietà di essere thin può anche essere definita come una proprietà dell'anello di Lie associato, che risulta essere in questo caso un'algebra di Lie su un campo finito, graduata sui naturali e generata dalla sua componente di grado 1.

PRO-p-GRUPPI JUST INFINITE E ALGEBRE DI LIE GRADUATE (I)

Alcuni anni dopo il completamento della dimostrazione delle celebri congetture sulla coclasse (si vedano [S94a], [L]), in [KLP], e poi con più dettagli in [LM], veniva proposto un progetto di classificazione ancora più fine per i pro-p-gruppi. Questo progetto, relativo ai pro-p-gruppi just infinite (in cui cioè tutti i sottogruppi non banali chiusi risultano essere aperti, in breve JI) è basato su parametri tra cui l'ampiezza (il rango dei fattori della serie centrale discendente) e l'obliquità (il supremo del logaritmo dell'indice di ogni termine della serie centrale discendente sulla sua intersezione con tutti i sottogruppi normali aperti in esso non contenuti).

Presto ci accorgemmo che le nozioni di ampiezza e l'obliquità, insieme ad altre nozioni gruppali correlate, potevano essere facilmente adattate al contesto delle algebre di Lie graduate.

Di fatto i nostri gruppi thin sono proprio i pro-p-gruppi di ampiezza 2 e obliquità 0, cioè il "primo passo" del nuovo progetto di classificazione. La proprietà di avere obliquità finita (d'ora in poi abbreviata in FO) è infatti equivalente, sia per i pro-p-gruppi [CC] che per le algebre di Lie [GM], alla proprietà di avere tutti i sottogruppi normali aperti (tutti gli ideali omogenei) giacenti, nel reticolo dei sottogruppi normali aperti (degli ideali omogenei), tra due termini della serie centrale discendente i cui indici differiscono per una quantità fissata. Un gruppo con questa proprietà viene detto normalmente costretto, e analogamente un'algebra con questa proprietà viene detta idealmente costretta.

In [GM] il caso generale della classificazione è stato affrontato per le algebre di Lie, con una caratterizzazione nel caso risolubile. In [GMS] è stato introdotto, per le algebre di Lie, il concetto di periodicità (abbr.: P), in termini di esistenza di un omomorfismo graduato di grado positivo di un opportuno ideale omogeneo nell'algebra stessa. Si è fornita una caratterizzazione delle algebre JI periodiche come sottoalgebre di certe algebre di Kac-Moody. Inoltre, si è mostrato che, per le algebre di Lie graduate, P implica FO.

Una definizione di periodicità è stata recentemente data [Mp] anche per i pro-p-gruppi (una mappa periodica p è una mappa da un sottogruppo normale aperto M del gruppo G in G stesso tale che p(M) sia un sottogruppo di G, e che la controimmagine sotto p di ogni sottogruppo normale aperto N di G contenuto in p(M) sia un sottogruppo normale aperto di G di indice strettamente minore dell'indice di N). Si è mostrato che i pro-p-gruppi di rango finito, risolubili e non, sono periodici. Inoltre, si è mostrato [Mp] che i pro-p-gruppi periodici hanno la proprietà FO. Si deve qui osservare che una dimostrazione della finitezza dell'obliquità dei gruppi di rango finito, che vale però solo nel caso non risolubile, è apparsa in [KLP], sulla base di metodi completamente diversi. Nel caso dei pro-p-gruppi infiniti just infinite la mappa p-esima potenza fornisce una periodicità. Esistono d'altra parte altri gruppi, non analitici rispetto ad alcun anello profinito, che mostrano però l'esistenza di una periodicità, almeno per quanto riguarda l'algebra di Lie associata. L'algebra associata al gruppo di Nottingham, ad esempio, essendo un'algebra loop di un'algebra finito dimensionale, ha struttura periodica. Recentemente Ershov ha mostrato che il gruppo di Nottingham è finitamente presentato [E05], mentre è noto che la sua algebra di Lie ha un'estensione centrale finitamente presentata. Ershov ha anche costruito una famiglia di sottogruppi del gruppo di Nottingham che non sono analitici, ma sono deformazioni di SL(2, K[[t]]). Anche questi gruppi mostrano una periodicità nell'algebra di Lie.

Dalla parte delle algebre di Lie graduate, recentemente in [DP] è stata data una costruzione dell'algebra associata al prodotto intrecciato di un pro-p-gruppo con algebra di Lie assegnata con il gruppo di ordine p. Una generalizzazione di questa costruzione fornisce un'algebra w^n che agisce su un modulo irriducibile V(n) in modo che ogni algebra di Lie nilpotente di dimensione finita e assolutamente irriducibile risulti essere una sottoalgebra lineare di w^n nella sua azione su V(n), per un opportuno n. Questa immersione è analoga a quella fornita per i gruppi da un ben noto risultato di Volvacev [V], e lascia sperare applicazioni al problema della classificazione delle algebre di Lie risolubili just-infinite.

ALGEBRE DI LIE NARROW (II)

Un'algebra di Lie di dimensione infinita si dice thin se è graduata sugli interi positivi, è generata dalla componente di grado 1, ha ampiezza 2 e obliquità zero, e non è di classe massimale, ovvero ha almeno un altro diamante (cioè una componente omogenea di dimensione 2) oltre al primo. Secondo [CMNS, CM99, AJ], il secondo diamante di un'algebra thin su un campo di caratteristica positiva p si può solo presentare in grado 3, 5, q o 2q-1, ove q è una potenza di p. Tutti questi casi si presentano effettivamente.

Nel caso modulare, queste algebre sono legate ad algebre di Lie semplici modulari di tipo Cartan, che non hanno analoghi di dimensione finita in caratteristica zero: un'ampia varietà di algebre thin, sia con secondo diamante in grado q che in grado 2q-1, si possono ottenere come algebre loop di algebre di Lie semplici modulari (quali le algebre di Zassenhaus, o vari tipi di algebre Hamiltoniane) rispetto ad opportune gradazioni. Per costruzione, queste algebre hanno una struttura periodica; qui anzi definiamo un'algebra come periodica quando è un'algebra loop di un'algebra di dimensione finita.

Non tutte le algebre thin sono periodiche [CM99], ma in molti casi è sufficiente assumere poche condizioni sulla struttura di un'algebra thin L fino a un certo grado, per poterne dedurre che essa è univocamente determinata, e ha una struttura periodica. Questo tipo di risultati si ottiene esibendo una presentazione finita per un'opportuna estensione centrale di L (mentre L stessa non è in genere finitamente presentabile), oggetto a cui ci riferiamo informalmente come una presentazione "quasi" finita di L. Si mostra poi che l'algebra è una loop algebra di un'algebra di dimensione finita; quest'ultima viene identificata insieme a una sua opportuna graduazione.

DERIVAZIONI NONSINGOLARI (II)

Le derivazioni nonsingolari di un'algebra di Lie giocano un ruolo importante in diverse ricerche. La classica relazione fra gruppi e algebre di Lie suggerisce che la derivazioni nonsingolari di un'algebra debbano somigliare agli automorfismi regolari (cioè senza punti fissi) di un gruppo o di un'algebra. Questo è proprio il caso, ed esiste una vasta bibliografia sugli automorfismi regolari, vedi p.es. [K].

Come per gli automorfismi regolari, il fatto che un'algebra di Lie ammetta una derivazione nonsingolare ne restringe notevolmente la struttura: per un'algebra di dimensione infinita in caratteristica zero implica addirittura la nilpotenza. Questo classico risultato di Jacobson [J] non vale in caratteristica positiva, dove persino le algebre semplici (di dimensione finita, come assumeremo tacitamente d'ora in poi) possono avere derivazioni nonsingolari. (Si veda [BKK] per una classificazione.) Una versione debole del risultato di Jacobson permane nel caso modulare: un'algebra di Lie in caratteristica p, che ammetta una derivazione nonsingolare di ordine che divida p-1, è necessariamente nilpotente. Questa è una semplice applicazione del teorema di Engel, secondo il modello della dimostrazione di Jacobson, ma ha notevolissime conseguenze: la validità delle congetture sulla coclasse di Leedham-Green e Newman [LN] per i pro-p gruppi, provata in [L] e [S94a] dipende in modo essenziale da questo fatto.

Le analoghe congetture per algebre di Lie modulari non valgono perché esistono algebre semplici che hanno derivazioni nonsingolari: per ogni k&gt;1 ci sono algebre di Lie semplici di dimensione finita in caratteristica p che hanno derivazioni nonsingolari di ordine p^k-1, e cioè certe algebre scoperte da Albert e Frank (che oggi vanno sotto il nome di algebre di Block); queste sono le algebre usate da Shalev [S94b] per costruire i primi esempi di algebre graduate di classe massimale non risolubili. Tutte le algebre di Lie di classe massimale generate dalla componente di grado 1, in caratteristica dispari, sono state costruite in [CMN] e classificate in [CN], e le algebre di Albert e Frank hanno giocato un ruolo importante in questa costruzione.

Sulla base di questi risultati, Shalev ha proposto in [S99]

Problema 1: Quali sono i possibili ordini n delle derivazioni nonsingolari delle algebre di Lie non nilpotenti, di dimensione finita in caratteristica p?

Shalev ha mostrato che le soluzioni n del Problema 1 sono anche soluzioni del

Problema 2; Per quali n esiste un elemento a nella chiusura algebrica del campo F_p con p elementi, tale che (a+b)^n=1 per tutti i b in F_p?

Si è mostrato in [M02] che i due problemi sono in realtà equivalenti, costruendo esplicitamente un'algebra di Lie risolubile, non nilpotente con una derivazione nonsingolare di ordine n, per ogni n che sia ammissibile secondo il Problema 2.
(Per ulteriori dettagli si veda il modulo B della Unità II)

CALCOLARE CON GLI ANELLI DI LIE FINITAMENTE PRESENTATI (II)

Gli anelli di Lie sono largamente usati per trattare i gruppi di Burnside. Kostrikin ha mostrato che c'è un gruppo finito B(d,p) che è il più grande fra tutti quelli con d generatori ed esponente un primo p. È ancora un problema aperto quale ne sia l'ordine. Ora l'anello di Lie L(d,p) associato a B(d,p) ha la stessa classe di nilpotenza e lo stesso ordine del gruppo. In [HNV] è stato usato un programma per studiare gli anelli di Lie che hanno L(d,p) come immagine omomorfa, ottenendo così un limite superiore per B(3,5). In [NV], sempre usando il calcolatore, si sono ottenuti limiti superiori per l'ordine e la classe di nilpotenza di B(2,7).

Un'altra applicazione degli anelli di Lie alla teoria dei p-gruppi è la classificazione dei gruppi di ordine p^6 e p^7, ottenuta in [NOV] e [OV] stabilendo una opportuna corrispondenza fra gruppi e anelli di Lie, e sviluppando tecniche per classificare questi ultimi, ottenendo così una classificazione dei gruppi. In entrambe queste aree gli anelli di Lie vengono dati mediante generatori e relazioni, ed è quindi di grande interesse avere algoritmi, e relative implementazioni, per calcolare una base di un anello di Lie dato in questo modo.

ALGEBRA E CRITTOGRAFIA

(II)

Secondo Shannon [Sha]

"A secrecy system is defined abstractly as a set of transformations of one space (the set of possible messages) into a second space (the set of possible cryptograms). Each particular transformation of the set corresponds to enciphering with a particular key. The transformations are supposed reversible (non-singular) so that unique deciphering is possible when the key is known."

Nella terminologia attuale, un crittosistema (a blocchi) è una collezione di permutazioni di un certo insieme finito. (In genere i plaintexts [quelli che Shannon chiama messaggi] e i ciphertexts [crittogrammi] sono elementi di uno stesso spazio vettoriale di dimensione finita sul campo F con 2 elementi.) Queste permutazioni sono indicizzate da una chiave.

Nella maggior parte dei crittosistemi queste trasformazioni sono ottenute mediante l'iterazione di una funzione molto semplice, detta funzione di round. Se il gruppo di permutazioni generato da queste funzioni di round è piccolo, allora il crittosistema è vulnerabile [KRS]. C'è una certa letteratura dedicata a mostrare che il gruppo generato dalle funzioni di round dei crittosistemi più popolari non è piccolo, ma coincide anzi con il gruppo simmetrico, o quello alterno. In [CDV] abbiamo risolto questo problema per il crittosistema PGM proposto da Magliveras.

Paterson [P] ha studiato la possibilità di costruire crittosistemi che contengano una trapdoor, basata sul fatto che il gruppo sopra descritto agisce imprimitivamente. Un sistema di imprimitività (sistema di blocchi) puo svolgere la funzione di una informazione da "insider", che rende più facile decrittare i messaggi anche senza conoscere la chiave.

Rijndael [DR02], che è stato adottato come Advanced Encryption Standard (AES), è un buon esempio di applicazione di sottili tecniche algebriche nella costruzione dei moderni crittosistemi; in molti di essi una funzione di round consiste di diverse trasformazioni elementari, che sono tutte affini tranne una, che viene detta S-box. La sua struttura gioca un ruolo estremamente importante per la sicurezza del sistema, in particolare nei riguardi della crittanalisi differenziale.

In AES la S-box consiste nell'inversione sul campo di ordine 2^8. (Per essere precisi, è la potenza 2^{8}-1, ovvero manda gli elementi non nulli nel loro inverso, e lo zero in zero.)

A questo proposito, Sandro Mattarei ha studiato [M06] i sottogruppi additivi dei campi che sono chiusi rispetto all'inversione, usando l'identità di Hua [Hua]. Nel caso speciale di un campo finito di caratteristica 2, il risultato è semplicemente che un tale sottogruppo è un sottocampo. (Risultati più generali sono stati ottenuti in [GGSZ].)

(I)

NTRU [www.ntru.com] è un crittosistema a chiave pubblica di tipo probabilistico. Un messaggio viene codificato come un polinomio troncato: un elemento dell'anello R=Z[x]/(x^n-1). Gli algoritmi di codifica e decodifica sono basati su calcoli in R ridotti modulo p e q, dove p e q son interi primi tra loro. Ci sono due attacchi interessanti a questo crittosistema. Il primo, che tenta di calcolare la chiave privata a partire da quella pubblica è noto come attacco al reticolo, il secondo è l'attacco sugli errori di avvolgimento, che tenta di ricavare informazioni sulla chiave privata nei casi in cui la decifratura del testo cifrato fallisca. Questi ed altri tipi di attacco sono ampiamente discussi in dettaglio ad esempio nella tesi di dottorato di Tommi Meskanen [Mphd].

L'attacco al reticolo tenta di risolvere un problema di "vettore di minima lunghezza" (in breve SVP) in un reticolo legato alla chiave pubblica. In pratica vi è un'evidenza computazionale del fatto che il problema SVP ha una soluzione più rapida quando il volume della regione fondamentale del reticolo aumenta o la lunghezza del più corto vettore diminuisce. Il problema SVP diventa più difficile da risolvere quando la dimensione del reticolo diventa grande.

L'attacco sugli errori di avvolgimento si basa sulla natura probabilistica della codifica. La decodifica non sempre va a buon fine ed un attaccante può sfruttare questo fatto per ottenere informazioni sulla chiave privata. Questo tipo di attacco può essere reso meno efficace con una scelta opportuna dei parametri del sistema. <<<