Skip to content →

Tag: Galois

ECSTR aka XTR

The one thing that makes it hard for an outsider to get through a crypto-paper is their shared passion for using nonsensical abbreviations. ECSTR stands for “Efficient Compact Subgroup Trace Representation” and we are fortunate that Arjen Lenstra and Eric Verheul shortened it in their paper The XTR public key system to just XTR. As both of them speak Dutch, they will know why Ive chosen a magpie-picture on the left… Btw. there is a nice MSRI-talk by Lenstra, starting off with a couple of jokes on what ECSTR is NOT meant to abbreviate (one of them being ‘Elliptic Curve Systems Too Risky’… (( I may even start to share their passion… )) ).

The XTR-system uses safety of Fp6 in the Diffie-Hellman key exchange while transmitting only 2=ϕ(6) pits. The first question one asks is : why the jump from N=2 from last time to N=6? Well, remember that (conjecturally) we want to use safety of Fq for q=pN while using only ϕ(N) pits. That is, we want to have Nlog(p) large (for safety) while at the same time ϕ(N)log(p) small (for efficiency). Thus, the most useful N’s to consider are those in the sequence

N=1, 2, 6=2.3, 30=2.3.5, 210=2,3,5,7, 

that is, the products of the first so many prime numbers. The number of elements of the cyclic group Fq is equal to

p61=(p1)(p+1)(p2+p+1)(p2p+1)

and that the subgroup of order p1 can be embedded in Fp, that of order p+1 can be embedded in Fp2, that of order p2+p+1 can be embedded in Fp3, BUT that the subgroup of order Φ6(p)=p2p+1 CANNOT be embedded in any Fpi for i=1,2,3, or in other words, the p2p+1 subgroup is as hard as Fp6. So, let us take a generator g of the subgroup T6 of order p2p+1 and do the Diffie-Hellman trick with it in a modified manner.

Galois groups of finite fields are cyclic and generated by the Frobenius xxp. In particular, the Galois group Gal(Fp6/Fp2)=C3 is cyclic of order three and consists of the auromorphisms 1=id,σ=(xxp2),σ2=(xxp4), so the corresponding trace map is given by

Tr : Fp6Fp2Tr(x)=x+xp2+xp4

So, how do we perform our key-exchange using my secret number a and yours b? Well, I’ll send you Tr(ga) and as this is an element of the quadratic extension Fp2 I’ll need just 2 pits instead of 6 and you will send me likewise Tr(gb). I claim that the common key we (and only we) can compute is Tr(gab). How does this work?

Given any element xT6Fp6 we can compute the 3-element set Cx=x,σ(x),σ(x2) and hence the characteristic polynomial
 (tx)(tσ(x))(tσ2(x))

=t3(x+σ(x)+σ2(x))t2+(xσ(x)+xσ2(x)+σ(x)σ2(x))txσ(x)σ2(x)

The first coefficient x+σ(x)+σ2(x) is the trace Tr(x) and the second and third coefficients are respectively Tr(xσ(x)) and the norm N(x). Now, if xT6 one can show that

Tr(xσ(x))=Tr(x)p and N(x)=1

That is, from knowing only Tr(x) we can compute the characteristic polynomial and hence recover the 3-element set h,σ(h),σ2(h)!

If I give you Tr(ga) you can compute from it the 3-set ga,σ(ga),σ2(ga) and raise them all the the b-th power (b being your secret number) to obtain

gab,σ(ga)b,σ2(ga)b=gab,σ(gab),σ2(gab)

but then you also know our shared key Tr(gab)=gab+σ(gab)+σ2(gab)… Done!

Leave a Comment

profinite groups survival guide

Even if you don’t know the formal definition of a profinte group, you know at least one example which explains the concept : the Galois group of the algebraic numbers Gal=Gal(Q/Q) aka the absolute Galois group. By definition it is the group of all Q-isomorphisms of the algebraic closure Q. Clearly, it is an object of fundamental importance for mathematics but in spite of this very little is known about it. For example, it obviously is an infinite group but, apart from the complex conjugation, try to give one (1!) other nontrivial element… On the other hand we know lots of finite quotients of Gal. For, take any finite Galois extension QK, then its Galois group GK=Gal(K/Q) is a finite group and there is a natural onto morphism πK : GalGK obtained by dividing out all K-automorphisms of Q. Moreover, all these projections fit together nicely. If we take a larger Galois extension KL then classical Galois theory tells us that there is a projection πLK : GLGK by dividing out the normal subgroup of all K-automorphisms of L and these finite maps are compatible with those from the absolute Galois group, that is, for all such finite Galois extensions, the diagram below is commutative

[tex]\xymatrix{Gal \ar[rr]^{\pi_L} \ar[rd]_{\pi_K} & & G_L \ar[ld]^{\pi_{LK}} \
& G_K &}[/tex]

By going to larger and larger finite Galois extensions L we get closer and closer to the algebraic closure Q and hence a better and better finite approximation GL of the absolute Galois group Gal. Still with me? Congratulations, you just rediscovered the notion of a profinite group! Indeed, the Galois group is the projective limit

Gal=lim GL

over all finite Galois extensions L/Q. If the term ‘projective limit’ scares you off, it just means that all the projections πKL coming from finite Galois theory are compatible with those coming from the big Galois group as before. That’s it : profinite groups are just projective limits of finite groups.

These groups come equipped with a natural topology : the Krull topology. Again, this notion is best clarified by considering the absolute Galois group. Now that we have Gal we would like to extend the classical Galois correspondence between subgroups and subfields QKQ and between normal subgroups and Galois subfields. For each finite Galois extension K/Q we have a normal subgroup of finite index, the kernel UK=Ker(πK) of the projection map above. Let us take the set of all UK as a fundamental system of neighborhoods of the identity element in Gal. This defines a topology on Gal and this is the Krull topology. As every open subgroup has finite index it is clear that this turns Gal into a compact topological group. Its purpose is that we can now extend the finite Galois correspondence to Krull’s Galois theorem :

There is a bijective lattice inverting Galois correspondence between the set of all closed subgroups of Gal and the set of all subfields QFQ. Finite field extensions correspond in this bijection to open subgroups and the usual normal subgroup and factor group correspondences hold!

So far we had a mysterious group such as Gal and reconstructed it from all its finite quotients as a projective limit. Now we can reverse the situation : suppose we have a wellknown group such as the modular group Γ=PSL2(Z), then we can look at the set of all its normal subgroups U of finite index. For each of those we have a quotient map to a finite group πU : ΓGU and clearly if UV we have a quotient map of finite groups πUV : GUGV compatible with the quotient maps from Γ

[tex]\xymatrix{\Gamma \ar[rr]^{\pi_U} \ar[rd]_{\pi_V} & & G_U \ar[ld]^{\pi_{UV}} \
& G_V &}[/tex]

For the family of finite groups GU and groupmorphisms πUV we can ask for the ‘best’ group mapping to each of the GU compatible with the groupmaps GUV. By ‘best’ we mean that any other group with this property will have a morphism to the best-one such that all quotient maps are compatible. This ‘best-one’ is called the projective limit

Γ^=lim GU

and as a profinite group it has again a Krull topology making it into a compact group. Because the modular group Γ had quotient maps to all the GU we know that there must be a groupmorphism to the best-one
ϕ : ΓΓ^ and therefore we call Γ^ the profinite compactification (or profinite completion) of the modular group.

A final remark about finite dimensional representations. Every continuous complex representation of a profinite group like the absolute Galois group GalGLn(C) has finite image and this is why they are of little use for people studying the Galois group as it conjecturally reduces the study of these representations to ‘just’ all representations of all finite groups. Instead they consider representations to other topological fields such as p-adic numbers GalGLn(Qp) and call these Galois representations.

For people interested in Grothendieck’s dessins d’enfants, however, continuous complex representations of the profinite compactification Γ^ is exactly their object of study and via the universal map ϕ : ΓΓ^ above we have an embedding

repc Γ^rep Γ

of them in all finite dimensional representations of the modular group (
and we have a similar map restricted to simple representations). I hope this clarifies a bit obscure terms in the previous post. If not, drop a comment.

Leave a Comment

Anabelian vs. Noncommutative Geometry

This is how my attention was drawn to what I have since termed
anabelian algebraic geometry, whose starting point was exactly a study
(limited for the moment to characteristic zero) of the action of absolute
Galois groups (particularly the groups Gal(K/K), where K is an extension of finite type of the prime field) on (profinite) geometric fundamental
groups of algebraic varieties (defined over K), and more particularly (breaking with a well-established tradition) fundamental groups which are very far
from abelian groups (and which for this reason I call anabelian). Among
these groups, and very close to the group π^0,3 , there is the profinite compactification of the modular group SL2(Z), whose quotient by its centre
{±1} contains the former as congruence subgroup mod 2, and can also be
interpreted as an oriented cartographic group, namely the one classifying triangulated oriented maps (i.e. those whose faces are all triangles or
monogons).

The above text is taken from Alexander Grothendieck‘s visionary text Sketch of a Programme. He was interested in the permutation representations of the modular group Γ=PSL2(Z) as they correspond via Belyi-maps and his own notion of dessins d’enfants to smooth projective curves defined over Q. One can now study the action of the absolute Galois group Gal(Q/Q) on these curves and their associated dessins. Because every permutation representation of Γ factors over a finite quotient this gives an action of the absolute Galois group as automorphisms on the profinite compactification

Γ^=lim Γ/N

where the limit is taken over all finite index normal subgroups NPSL2(Z). In this way one realizes the absolute Galois group as a subgroup of the outer automorphism group of the profinite group Γ^. As a profinite group is a compact topological group one should study its continuous finite dimensional representations which are precisely those factoring through a finite quotient. In the case of Γ^ the simple continuous representations simpc Γ^ are precisely the components of the permutation representations of the modular group. So in a sense, anabelian geometry is the study of these continuous simples together wirth the action of the absolute Galois group on it.

In noncommutative geometry we are interested in a related representation theoretic problem. We would love to know the simple finite dimensional representations simp Γ of the modular group as this would give us all simples of the three string braid group B3. So a natural question presents itself : how are these two ‘geometrical’ objects simpc Γ^ (anabelian) and simp Γ (noncommutative) related and can we use one to get information about the other?

This is all rather vague so far, so let us work out a trivial case to get some intuition. Consider the profinite completion of the infinite Abelian group

Z^=lim Z/nZ=pZ^p

As all simple representations of an Abelian group are one-dimensional and because all continuous ones factor through a finite quotient Z/nZ we see that in this case

simpc Z^=μ

is the set of all roots of unity. On the other hand, the simple representations of Z are also one-dimensional and are determined by the image of the generator so

simp Z=C0=C

Clearly we have an embedding μC and the roots of unity are even dense in the Zariski topology. This might look a bit strange at first because clearly all roots of unity lie on the unit circle which ‘should be’ their closure in the complex plane, but that’s because we have a real-analytic intuition. Remember that the Zariski topology of C is just the cofinite topology, so any closed set containing the infinitely many roots of unity should be the whole space!

Let me give a pedantic alternative proof of this (but one which makes it almost trivial that a similar result should be true for most profinite completions…). If c is the generator of Z then the different conjugacy classes are precisely the singletons cn. Now suppose that there is a polynomial a0+a1x++amxm vanishing on all the continuous simples of Z^ then this means that the dimensions of the character-spaces of all finite quotients Z/nZ should be bounded by m (for consider x as the character of c), which is clearly absurd.

Hence, whenever we have a finitely generated group G for which there is no bound on the number of irreducibles for finite quotients, then morally the continuous simple space for the profinite completion

simpc G^simp G

should be dense in the Zariski topology on the noncommutative space of simple finite dimensional representations of G. In particular, this should be the case for the modular group PSL2(Z).

There is just one tiny problem : unlike the case of Z for which this space is an ordinary (ie. commutative) affine variety C, what do we mean by the “Zariski topology” on the noncommutative space simp PSL2(Z) ? Next time we will clarify what this might be and show that indeed in this case the subset

simpc Γ^simp Γ

will be a Zariski closed subset!

Leave a Comment