RICERCA ITALIANA     

Groups, Lie Algebras, Criptography

Università degli Studi de L'Aquila

Abstract

In our previous work we have started the classification project for just infinite pro-p-groups, and we have shown that a similar project of classification makes sense also for just infinite dimensional modular graded Lie algebras. The classification of a crucial class of graded Lie algebras, i.e. the thin Lie algebras, has been carried on by one of our units with continuous progress.
As a consequence of our growing interaction with other international leading groups of researchers, and of the natural evolution of our research interests, we have recently opened entirely new perspectives for these lines of research.

At the same time our group has acquired a new researcher (de Graaf). This acquisition reinforces the line of research that refers to the study of Lie algebras, and stresses the computational aspect. Note that computational experiments have always had an important role in our work. Indeed, we use the evidence of computer constructions of algebraic objects as a guideline for our theoretical research work. At the same time, in some occasions we have produced original contributions to existing packages for algebraic computation. We also intend to emphasize this second aspect, with a particular attention to parallel computing (collaboration with the University of St. Andrews for production of GAP libraries).

Both units have started studying problems in cryptography. Looking at the more recent literature on the subject, it appears that there is considerable space for work by algebraists. This goes in both directions: one can apply algebraic tools to gain a deeper understanding of relevant cryptographic questions; and conversely problems in cryptography suggest algebraic questions that can be studied for their own sake. One of the goals of this project is to bring together the work both units have been doing in this field, continuing a long-standing tradition of collaboration.

This research program is therefore twofold: on the one hand we want to boost our activity on pro-p-groups and Lie algebras, in the light of the new ideas; on the other hand we want to reserve the greatest attention to our new research themes, in order to increase our productivity in those areas.
In this delicate double task project we believe the long experience of strict collaboration and productive interaction between our two units to be our most reliable credential. <<<

Principal Investigator

Carlo Maria Scoppola Università degli Studi de L'AQUILA

Research Objectives

The aim of this research program is twofold.
On the one hand, we want to boost our activity on the research topics we studied in the last few years, i.e. just infinite pro-p-groups and graded Lie algebras, in the light of the new ideas and perspectives recently opened as an effect of the expansion of our network of international collaborations.
On the other hand we have extended our research interests, obtaining results on new topics, like algebraic questions related to cryptography, and computation in Lie algebras.
We want to reinforce our commitment on these new research lines. <<<

Timescale

24 months

National and international background

(This item is necessarily the join of the two corresponding items on forms B. For the convenience of the reader, we mark each part of this item with the number of the Unit).

The construction of a graded Lie ring associated to a filtration of a pro-p-group (the direct sum of the quotients of the filtration endowed with the Lie structure that is inherited from the commutation structure of the group) dates back to classical work of Magnus, Zassenhaus and Lazard.

In our past work we have applied this construction frequently. Our main interest, when we started some years ago, was centered on the class of thin (pro-p)-groups, i.e. (topologically) 2-generated (pro-)p-groups in which every (open) normal subgroup lies, in the lattice of (open) normal subgroups, between two consecutive terms of the lower central series. In [CMNS], [CMN], [M99], [GMSjgt] thin (pro-)p-groups were studied.

Thinness can also be defined as a property of the associated Lie ring, which indeed turns out to be a Lie algebra over a finite field, graded over the positive integers and generated by its component of degree 1.

JUST INFINITE PRO-p-GROUPS AND GRADED LIE ALGEBRAS (I)

Some time after the completion of the proof of the well known coclass conjectures (see [S94a] and [L]), a more refined classification project for pro-p-groups was proposed ([KLP], and then, with more details, [LM]). This project focuses on just infinite (JI for short) pro-p-groups, i.e. pro-p-groups in which all nontrivial closed subgroups are open, and is based on parameters like e.g. the width (the rank of the lower central factors) and obliquity (the supremum of the logarithm of the index of any term of the lower central series over its intersection with all the open normal subgroups not contained in it).

The notions of width and obliquity, as long as other notions, e.g the one of being just infinite, are rather easily adapted to the graded Lie algebra context.

As a matter of fact, our thin pro-p-groups are the pro-p-groups of width 2 and obliquity 0. The property of having finite obliquity (for short: FO) has indeed been shown to be equivalent, both for pro-p-groups [CC] and for graded Lie algebras [GM], to the property of having all open normal subgroups (homogeneous ideals) trapped between two terms of the lower central series whose indices differ by a fixed integer. A group having this property is said to be normally constrained (resp. ideally constrained in the case of Lie algebras).

In [GM] the general case of the classification was started for Lie algebras, with a characterization in the soluble case. In [GMS] the concept of periodicity (for short: P) was introduced for Lie algebras, as the existence of a graded homomorphism of positive degree of a suitable homogeneous ideal in the algebra itself. A characterization of JI periodic Lie algebras was given, as subalgebras of some Kac-Moody algebras. Furthermore, it was shown that for graded Lie algebras, P implies FO.

A definition of periodicity has been recently given [Mp] also for groups (a periodic map for a just infinite pro-p-group G is a map p from an open normal subgroup M of G into G such that p(M) is a subgroup of G, and such that the counterimage under p of any normal open subgroup N of G contained in p(M) is a normal open subgroup of G of index smaller than the index of N), with a proof of the periodicity of all pro-p-groups of finite rank, soluble and insoluble. In turn, it was shown that periodicity implies condition FO [Mp]. In case of soluble and analytic just infinite pro-p-groups the periodic map can be chosen to be the p-th power map. There are however other groups that are not analytic on any profinite ring that we expect to be periodic looking at their associated Lie algebra. The algebra associated to the Nottingham group has a periodic structure being a "loop algebra of a finite-dimensional algebra". Recently Ershov proved that The Nottingham group is finitely presented [E05], while it is known that the associated Lie algebra has a central extension that is finitely presented.

On the Lie algebra side, recently in [DP] a construction for the algebra associated to the wreath product of a group having algebra L with a cyclic group of order p was given. A generalization of this construction provides an algebra w^n acting on an irreducible module V(n) such that any absolutely irreducible finite dimensional nilpotent Lie algebra can be seen as a linear subalgebra of w^n in its action on V(n), for some n. This embedding statement is the Lie analog of a well known result of Volvacev [V] and is promising for applications to the problem of the classification of soluble just infinite Lie algebras.

NARROW LIE ALGEBRAS (II)

A thin algebra is an infinite-dimensional Lie algebra graded over the positive integers, generated by the component of degree one, of width two and obliquity zero, and which is not of maximal class, that is it has at least one further diamond (i.e. a homogeneous component of dimension two) besides the component of degree one. According to [CMNS, CM99, AJ] the second diamond of a thin Lie algebra L over a field of positive characteristic p can only occur in degree s = 3, 5, q, or 2q-1, where q is a power di p. All of these cases do occur.

Confining ourselves to the modular cases, they involve simple modular Lie algebras of Cartan type, which have no finite-dimensional analogues in characteristic zero: a broad variety of thin Lie algebras, both with second diamond in degree q and with second diamond in degree 2q-1, can be obtained as loop algebras of finite-dimensional simple modular Lie algebras (such as Zassenhaus algebras or various types of Hamiltonian algebras) with respect to suitable gradings. By their very construction these algebras have a periodic structure; for the purpose of the present discussion we may and will take "being loop algebras of finite-dimensional algebras" as a definition for "being periodic".

Not all thin Lie algebras are periodic [CM99], but in many cases limited assumptions on the structure of a thin Lie algebra L up to a certain degree imply that the algebra has a periodic structure and is uniquely determined. This type of result is obtained by exhibiting a finite presentation for a central extension of L (while L itself is usually not finitely presentable), which we refer to informally here as a "nearly" finite presentation for L. One then proves that the algebra is a loop algebra of a finite-dimensional algebra and to identify the latter and its appropriate grading.

NONSINGULAR DERIVATIONS (II)

Nonsingular derivation of a Lie algebra play an important role in various investigations. The classical relationship between Lie groups and their Lie algebras suggests that nonsingular derivations of Lie algebras should bear a resemblance with regular (i.e. without fixed points) automorphisms of a group or of a Lie algebra. In fact, this is the case, and an extensive bibliography exists concerning regular automorphisms, see e.g. [K].

As it is the case with regular automorphisms, the existence of a nonsingular derivation of Lie algebra restricts its structure considerably: for a finite-dimensional Lie algebra in characteristic zero it forces nilpotency. This classical result of Jacobson [J] fails in positive characteristic, where even (finite-dimensional, as we shall tacitly assume from now on) simple Lie algebras can admit nonsingular derivations. (See [BKK] for a classification.) A weak version of Jacobson's result survives in the modular case: a Lie algebra in characteristic p which admits a nonsingular derivation of order dividing p-1 is necessarily nilpotent. This is an easy application of Engel's theorem along the lines of Jacobson's proof, but has tremendous consequences: the truth of the coclass conjectures of C.R. Leedham-Green and M.F Newman for pro-p groups [LN], proved in [SZ92] and [S94a] depends on this fact in an essential way.

The analogous conjectures for modular Lie algebras do not hold because of the existence of nonsingular derivations for certain simple Lie algebras: for all k&gt;1 there exist finite-dimensional simple Lie algebras of characteristic p which have nonsingular derivations of order p^k-1, namely certain algebras discovered by Albert and Frank (referred to today as Block algebras); these were used by Shalev in [S94b] to construct the first examples of non-soluble graded Lie algebras of maximal class. All graded Lie algebras of maximal class generated by the homogeneous component of degree one (in odd characteristic) were then constructed in [CMN] and classified in [CN], and the algebras of Albert and Frank played an important role in the construction.

Prompted by these results, Shalev asked in [S99]

Problem 1: Which are the possible orders n of nonsingular derivations of finite-dimensional non-nilpotent Lie algebras of characteristic p?

He showed that the solutions n of Problem 1 are also solutions of

Problem 2: For which numbers n is there an element a in the algebraic closure of the field of p elements F_p, such that (a+b)^n=1 for all b in F_p?

It was shown in [M02] that the two problems are actually equivalent, by explicitly constructing a soluble, non nilpotent, Lie algebra of characteristic p with a nonsingular derivation of order n, for any n which is an admissible number for Problem 2.
(for further details see form B of Unit II)

COMPUTING WITH FINITELY-PRESENTED LIE RINGS (II)

Here we mention two examples of subject areas where Lie rings are heavily used. The first of these concerns Burnside groups. Kostrikin has proved that there is a largest finite group B(d,p) with d generators and prime exponent p. However, for all but a few values of d and p, it is still an open problem what the order of the group is. Now the Lie ring L(d,p) associated to B(d,p) has the same nilpotency class, and order as the group B(d,p). In [HNV] a computer program is used to study Lie rings that have L(d,p) as a homomorphic image. This way an upper bound for the order of B(3,5) is obtained. In [NV], also using computer calculations, upper bounds for the order and nilpotency class of B(2,7) are obtained.

Another application of Lie rings to the theory of p-groups is the classification of groups of order p^6 and p^7 in [NOV] and [OV]. Here a correspondence between Lie rings and p-groups is established. Furthermore techniques are developed for classifying the former, yielding also a classification of the latter. In both these subject areas the Lie rings that are studied are given by a presentation by means of generators and relations. It is therefore of great interest to have algorithms, along with implementations of them, to compute a basis of a Lie ring given in that way.

ALGEBRA AND CRYPTOGRAPHY

(II)

According to Shannon's dictum [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."

In today's terminology, a (block) cryptosystem is a collection of permutations of a certain finite set. (Usually plaintexts [what Shannon calls messages] and ciphertexts [cryptograms] are elements of the same set, which is typically a finite-dimensional vector space over the field F with two elements.) These permutations are indexed by a key.

In most cryptosystems, these transformations are obtained by iterating a certain simple map, called a round function. If the group of permutations generated by the round functions is small, then the cryptosystem is vulnerable [KRS]. Some attention has been dedicated in the literature to showing that the group generated by the round functions of the most popular cryptosystems is not small, but coincides with the full symmetric group, or with the alternating group. In [CDV] we solved this problem for the cryptosystem PGM proposed by Magliveras.

Paterson [P] has studied the possibility of building trapdoors into cryptosystems by having the above group acting imprimitively. A system of imprimitivity (block system) may act as insider information, that makes it easier to decode messages without the knowledge of the key.

Rijndael [DR02], which has been adopted as the Advanced Encryption Standard (AES), is a good example of the application of subtle algebraic techniques in the construction of modern cryptosystems. In many current cryptosystems, a round function will consist of several elementary transformations, all of which, with one exception, will be linear (or affine). The only non-affine transformation is called an S-box. Its structure plays a very important role in the security of the system, in particular with respect to differential cryptanalysis.

In AES the S-box consists in the inversion on the field di ordine 2^8. (To be more precise, the S-box is the 2^{8}-1 power, i.e. it evaluates to the inverse on non-zero elements, and to zero on zero.)

Now Sandro Mattarei [M06] has studied the additive subgroups of fields that are closed under inversion, using Hua's identity [Hua]. In the special case of a finite field of characteristic two, the result is simply that such a subgroup is a subfield. (More general results have been obtained in [GGSZ].)

(I)

NTRU [www.ntru.com] is a probabilistic public key cryptosystem. A message is coded as a truncated polynomial, i.e. an element of the ring R=Z[x]/(x^n-1). Encryption and decryption are based on calculation in R mod p and q, where p and q are relatively prime integers. There are two interesting attacks to this cryptosystem. One is designed to recover the private key from the public key and is known as the lattice attack, the other one is the wrap error attack that tries to recover information on the private key whenever decryption errors occur. In Tommi Meskanen's PhD dissertation [Mphd] several known attacks, including the previous ones, are described.

The lattice attack tries to solve a "shortest vector problem" (SVP for short) in a Lattice that is related to the public key. In practice there is an evidence of the fact that this problem has a "faster" solution whenever the volume of the lattice increases or the length of the shortest vector in the lattice decrease. The SVP tends to become more difficult to solve as soon as the dimension of the lattice becomes large.

The wrap error attack relies on the probabilistic nature of the encoding. Decoding may fail and knowing this fact an attacker can gain information on the private key. A possible correction to this problem can be a better choice of the involved parameters. <<<