RICERCA ITALIANA     

Programma di ricerca

Gruppi, Algebre di Lie, Crittografia

Università di riferimento

Università degli Studi di TRENTO - MATEMATICA - ()

Responsabile dell'Unità di ricerca

Andrea Caranti

Descrizione

ALGEBRE DI LIE NARROW

Buona parte del nostro lavoro recente ed attuale in quest'area di
ricerca consiste nell'identificazione di varie classe di algebre di
Lie thin mediante certi invarianti, che passiamo a descrivere
sommariamente. Come spiegato nella "Base di partenza", l'invariante
pricipale e' il grado k in cui si presenta il secondo
diamante. Lasciando da parte i casi k=3 e 5, questo suddivide le
algebre di Lie thin nelle due classi corrispondenti a k=q e k=2q-1,
ove q e' una potenza della caratteristica p. Piu' in generale sono
invarianti i gradi in cui si presentano i diamanti. Questi invarianti
possono essere raffinati assegnando a ogni diamante tranne il primo un
"tipo", che puo' essere un elemento del campo, o
infinito. Tralasciando qualche sottigliezza, fra cui la possibilita'
di considerare come diamanti "falsi" certe componenti di dimensione
uno, i gradi dei diamanti e i loro tipi determinano un'algebra di Lie
thin a meno di isomorfismi.


Algebre di Lie thin con secondo diamante in grado q

In effetti in diversi casi i gradi e i tipi di un numero limitato dei
primi diamanti sono sufficienti per determinare l'algebra a meno di
isomorfismi. Un esempio e' quello di [CM04], ove si mostra che le
algebre di Lie thin con secondo diamante in grado q (che allora deve
essere necessariamente di tipo -1) e terzo diamante di tipo finito in
grado 2q-1 sono univocamente determinate da questi dati, e sono
periodiche. Vi sono alcuni sottocasi che dipendono dal tipo del terzo
diamante. In [C97, C99, C98, A99, AMAZ] si sono realizzate costruzioni
esplicite di queste algebre di Lie thin come algebre loop di certe
algebre di Lie di dimensione finita, rispetto a opportune
gradazioni. Nell'ultimo lavoro citato, che tratta il caso in cui il
tipo del terzo diamante non sta nel campo primo, abbiamo fatto uso di
deformazioni per stabilirne una connessione con le algebre del lavoro
precedente. Siamo convinti che tecniche di deformazione giocheranno un
ruolo nella classificazione delle algebre di Lie thin, che vediamo
come nostro obbiettivo primario, per quanto distante. Le algebre di
Lie thin con secondo diamante di grado q e terzo diamante di tipo
infinito sono al momento oggetto di studio comune di Avitabile, Jurman
e Mattarei.

Algebre di Lie thin con secondo diamante in grado 2q-1

Risultati simili sono stati ottenuti per le algebre con secondo
diamante in grado 2q-1. In particolare in [CM99] abbiamo dimostrato
l'unicita' dell'algebra con secondo diamante di grado 2q-1, di tipo
finito fissato. Quest'algebra e' stata poi costruita in [CM05] come
algebra loop di una certa algebra di dimensione finita (una "algebra
di Block", di dimensione una potenza di p, meno uno) rispetto a una
gradazione opportuna. In [AM05] abbiamo costruito algebre di Lie thin
con secondo diamante in grado 2q-1, e diamanti sia di tipo finito che
di tipo infinito, di nuovo come algebre loop dello stesso
genere. Sulla scorta delle proprieta' strutturali delle algebre di Lie
thin costruite in [AM05], abbiamo intrapreso in [AviMat:diamonds] lo
studio delle possibili combinazioni di gradi e tipi dei diamanti nelel
algebre di Lie thin con diamanti sia di tipo finito che di tipo
infinito. Piu' precisamente dimostriamo che sotto certe ipotesi
tecniche il numero di diamanti di tipo infinito fra due diamanti di
tipo finito e una potenza di p, meno uno, proprio come succede per le
algebre di Lie thin di [AM05].

Verso una classificazione delle algebre di Lie thin

Una teoria generale delle algebre di Lie thin richiede una estensione
a questa classe di molti argomenti della teoria delle algebre di
classe massimale, sviluppati in [CMN, CN00,
Jurman:maximal-class]. Sfortunatamente gia' alcuni fatti di base di
quella teoria diventano parecchio piu' complicati in questo contesto
piu' generale. In [Mattarei:chain-lengths] diamo dimostrazioni piu'
semplici e concettuali di due risultati fondamentali di [CMN]: (a) il
primo costituente di un'algebra di Lie graduata di classe massimale ha
lunghezza 2q, ove q e' una potenza della caratteristica p; (b) le
lunghezze dei costituenti hanno la forma 2q o 2q-p^s per qualche s. la
stessa strategia fornisce una dimostrazione semplificata del (piu'
complicato) analogo di (a) per le algebre di Lie thin, cioe'
l'affermazione che il secondo diamante compare in grado 3, 5, q o
2q-1. Siamo anche in grado di dimostrare un analogo di (b) per algebre
di Lie thin con secondo diamante in grado 2q-1: le differenze fra i
gradi di due diamanti consecutivi sono della forma 2q-1 o 2q-p^s-1 per
qualche s. Stiamo lavorando a un analogo di (b) per le algebre di Lie
thin con secondo diamante in grado q.

L'informazione parziale ottenuta in [Mattarei:chain-lengths] sulla
posizione dei diamanti in un'algebra di Lie thin con secondo diamante
in grado 2q-1 viene completata in [Mattarei:deformations], ove
mostriamo che, partendo da una qualsiasi algebra di Lie thin con
secondo diamante in grado 2q-1, se ne puo' costruire un'altra con
diamanti negli stessi gradi, ma tutti di tipo infinito. Dato che
secondo [CM99] queste ultime algebre di Lie thin sono in
corrispondenza biunivoca con una certa sottoclasse delle algebre di
Lie graduate di classe massimale, ne segue che le posizioni dei
diamanti nelle algebre di Lie thin, con secondo diamante in grado
2q-1, sono completamente controllate dalla teoria delle algebre di Lie
graduate di classe massimale. La relazione fra l'algebra di Lie thin
originale e quella con tutti i diamanti di tipo infinito puo' esere
espressa in termini di deformazioni. Pensiamo che lo studio di queste
deformazioni possa costituire il passo finale in una classificazione
delle algebre di Lie thin con secondo diamante in grado 2q-1.

DERIVAZIONI NONSINGOLARI

In [Mattarei:odd] abbiamo esteso al caso di caratteristica dispari i
risultati ottenuti in [Mev] in caratteristica due mediante strumenti
di geometria algebrica, cioe' la stima di Weil sul numero di punti su
una curva algebrica su un campo finito. Il risultato principale dice
piu' o meno che ogni divisore n di p^k-1 tale che n^{2p} >=
(p-1)^{2}.p^{k(2p-1)} e' una soluzione dei due problemi equivalenti
descritti nella "Base di partenza". Una dimostrazione rigorosa di
questo fatto richiede di calcolare il genere di una certa curva
algebrica definita da p-1 equazioni, e un'applicazione dei risultati
di Weil.

Questi risultati suggeriscono che gli ordini delle derivazioni non
singolari delle algebra di Lie non nilpotenti possano sottrarsi a una
classificazione semplice, ma ci sono altri problemi riguardanti le
derivazioni non singolari che vale la pena studiare. E' del tutto
naturale chiedersi se si possono ottenere risultati simili sugli
ordini delle derivazioni non singolari delle algebre di Lie non
risolubili. Appare ragionevole pensare che qui si possano presentare
solo i multipli di p^k-1 per k>1. Come conseguenza della
classificazione delle algebre di Lie graduate di classe massimale data
in [CN00] e [Jurman-maximal], questo e' certamente vero sotto la
condizione aggiuntiva (e piuttosto restrittiva) che la derivazione
permuti ciclicamente le componenti di un'opportuna graduazione. Una
conferma viene anche dai risultati di Benkart, Kostrikin and Kuznetsov
in [BKK95] che si basano sulla classificazione delle algebre di Lie
semplici modulari in caratteristica maggiore di 7. Alcune tecniche
sviluppate nel corso del lavoro sulle algebre di Lie graduate di
classe massimale offrono qualche speranza che sia possibile attaccare
quetso problema in modo diretto. L'ostacolo principale e'
rappresentato dal fatto che qui, a differenza del caso delle algebre
non nilpotenti gia' discusso, manca una traduzione di questo problema in
un problema di teoria dei numeri. La ragione e' che manca una
caratterizzazione "locale" della risolubilita' di un'algebra di Lie in
caratteristica positiva, che giochi lo stesso ruolo del teorema di
Engel per la nilpotenza. (Si noti che secondo il teorema di Lie si
puo' dimostrare la risolubilita' di un'algebra di Lie in
caratteristica zero mostrando che la sottoalgebra derivata e'
nilpotente - si puo' usare il teorema di Engel. In caratteristica
positiva, invece, la sottoalgebra derivata non e' necessariamente
nilpotente. Il fatto che il teorema di Lie non valga in caratteristica
positiva e' la ragione alla base di molte delle difficolta' nella
classificazione delle algebre di Lie semplici modulari.)

CALCOLARE CON GLI ANELLI DI LIE FINITAMENTE PRESENTATI

Lo scopo di questa parte del progetto e' di sviluppare algoritmi per
il calcolo con anelli di Lie finitamente presentati, e di implementarli
in sistemi di computer algebra che siano in grado di lavorare
adeguatamente con gruppi ed algebre, quali GAP ([GAP, 2006]) e Magma ([Magma,
2005]). Questo permettera' l'accesso ai nostri algoritmi a una vasta
comunita' scientifica. Inoltre le implementazioni saranno di uso
immediato, dato che questi sistemi offrono funzionalita'
intercorrelate per gruppi ed algebre.

Nella letteratura sono presenti due approcci al calcolo con gli anelli
di Lie finitamente presentati. In [HNV, 1990] e [S, 1997] vengono dati
algoritmi per il calcolo con quozienti nilpotenti di anelli di Lie
fintamente presentati, algoritmi che sono analoghi al "nilpotent
quotient algorithm" per i gruppi. Il passo fondamentale in questi
algoritmi consiste nel partire da una base dell'anello di Lie modulo
il k-esimo termine della serie centrale discendente, ed estenderla a
una base dell'anello di Lie modulo il (k+1)-esimo termine. La ricerca
che proponiamo seguira' un approccio diverso, che consiste nel
lavorare all'interno dell'anello di Lie libero. Intendiamo sviluppare
tecniche simili a quelle delle basi di Groebner per lavorare con gli
ideali negli anelli di Lie liberi, e costruire in questo modo un
algoritmo in grado di calcolare una base di un anello di Lie
finitamente presentato. Questo approccio ha due vantaggi
principali. Da un lato offre una maggiore flessibilita', il che
dovrebbe dar luogo a un algoritmo molto piu' efficiente e trasparente
quando le relazioni non sono omogenee. In effetti l'algoritmo di [HNV,
1990] funziona solo con relazioni omogenee, e l'implementazione
dell'algoritmo di [S, 1997] e' anch'essa in grado di trattare solo
relazioni omogenee. D'altro canto i nostri metodi sono in grado di
trattare anche anelli di Lie non nilpotenti, a differenza degli
algoritmi di [HNV, 1990], [S, 1997].

Una volta sviluppati e implementati questi algoritmi, intendiamo
studiare gli anelli di Lie che soddisano una identita' di Engel. Gli
anelli di Lie che corrispondono ai gruppi di Burnside soddisfano una
idnentita' di questo tipo, , ma sono stati finora studiati solo in
caratteristica fissata. Studiando le conseguenze delle identita' di
Engel sugli interi sara' possibile vedere quello che succede
contemporaneamente in tutte le caratteristiche.

ALGEBRA E CRITTOGRAFIA

Imprimitivita'

Andrea Caranti, Francesca Dalla Volta (Milano-Bicocca) and
Massimiliano Sala (UC Cork, Ireland) hanno lavorato al problema di
Paterson citato nella "Base di partenza". Contiamo di ottenere un
risultato ragionevolmente soddisfacente, che consiste di due
parti. Nella prima, dovremmo ottenere condizioni naturali sui
componenti di un crittosistema che garantiscano che esso non ha
trapdoors basate sull'imprimitivita'. Nella seconda parte dovremmo
essere in grado di mostrare che queste condizioni possano essere
verificate in modo semplice e naturale per i crittosistemi piu'
comuni. Per AES, ad esempio, la condizione segue dal rislutato di
mattarei [Mat06] citato nella "Base di partenza". In effetti Mattarei
ha affrontato questo problema proprio sulla base del lavoro che stiamo
descrivendo.

Inversione e indentita' di Hua

Una versione semplificata dell'identita' di Hua [Hua] puo' essere
formulata nel modo seguente, che e' piu' che sufficiente per i nostri
scopi. Siano x, a elementi di un campo finito E di caratteristica due,
con x, a, x+a diversi da zero. Allora

(x + a)^{-1} + x^{-1} = (a^{-1} x^{2} + x)^{-1}.

Dato che siamo in caratteristica due, la funzione che porta x in
a^{-1} x^{2} + x (per a fissato) e' lineare. Questo fatto e' sfruttato
implicitamente in [DR06]. Il termine di sinistra dell'equazione qui
sopra e' chiamato un differenziale, e sfruttato nella cosiddetta
crittanalisi differenziale. Ora Daemen e Rijmen notano che una volta
fissato a, al variare di x in E gli elementi (x + a)^{-1} + x^{-1}
descrivono l'inverso di un sottospazio, meno lo zero. Partendo da
questo fatto, ottengono una analisi dettagliata dei differenziali di
AES su due rounds. Intendiamo esplorare se l'affermazione piu' precisa
fornita dall'identita' di Hua ci permetta di migliorare questa
analisi.

Intendiamo anche rivedere i risultati di [CHZ] sulla base
dell'identita' di Hua. In questo lavoro si studiano le cosiddette
caratteristiche di propagazione dell'inversione e delle sue derivate,
che sono di nuovo le differenze (x + a)^{-1} + x^{-1}. Contiamo di
migliorare questi risultati, o comunque di riottenerli in un modo
piu' semplice, e magari piu' trasparente.

Relazioni con problemi puramente algebrici

Va sottolineato come lavorando a questioni crittografiche quali quelle
sopra descritte sia inevitabile considerare anche problemi puramente
algebrici. Un esempio e' il lavoro di Mattarei [Mat06] gia' citato. Un
altro e' [CDVS], che e' originato da una questione correlata al
problema dell'imprimitivita' gia' discusso. In questo lavoro si
descrivono i sottogruppi abeliani regolari del gruppo affine, in
termini delle strutture di algebra comutativa che si possono imporre
sullo spazio vettoriale soggiacente, in modo che l'anello risultante
coincida con il suo radicale di Jacobson. Ci aspettiamo che ulteriori
lavori di algebra pura, in particolare in teoria dei gruppi,
scaturiscano naturalmente dai nostri studi crittografici.

APPLICAZIONI DELLA TEORIA DEI CARATTERI ALLO STUDIO DI CURVE DI FERMAT
SU CAMPI FINITI

Una curva di Fermat e' definita dall'equazione ax^n+by^n=z^n in
coordinate proiettive. La stima di Weil, valida per ogni curva non
singolare, fornisce limiti superiori ed inferiori per il numero di
punti razionali di una curva di Fermat su un campo finito. E' noto da
alcuni decenni che una forma debole della stima di Weil puo' essere
dimostrata utilizzando la teoria dei caratteri di certi gruppi
finiti. In [Mattarei:Fermat] abbiamo mostrato come un raffinamento di
questo metodo permetta di dimostrare la stima di Weil vera e propria
per questo tipo di curve.

In anni recenti, diversi autori hanno usato tecniche piuttosto
sofisticate di geometria algebrica per fornire limiti migliori di
quelli di Weil per le curve di Fermat, quando n e' grande rispetto
all'ordine del campo. Una panoramica e un confronto di questi metodi
sono dati in [Mattarei:Garcia-Voloch], dove si ottengono anche alcuni
leggeri miglioramenti. Contiamo di studiare se i metodi della teoria
dei caratteri, che hanno certamente margini di miglioramento, possano
dare ulteriori contributi in questa direzione.