Tag: Galois

ECSTR aka XTR

Published January 5, 2008 by lieven

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 $F_{p^{6}}$ 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 $F_{q}$ for $q = p^{N}$ while using only $ϕ (N)$ pits. That is, we want to have $N l o g (p)$ large (for safety) while at the same time $ϕ (N) l o g (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, \dots$

that is, the products of the first so many prime numbers. The number of elements of the cyclic group $F_{q}^{*}$ is equal to

$p^{6} - 1 = (p - 1) (p + 1) (p^{2} + p + 1) (p^{2} - p + 1)$

and that the subgroup of order $p - 1$ can be embedded in $F_{p}^{*}$ , that of order $p + 1$ can be embedded in $F_{p^{2}}^{*}$ , that of order $p^{2} + p + 1$ can be embedded in $F_{p^{3}}^{*}$ , BUT that the subgroup of order $Φ_{6} (p) = p^{2} - p + 1$ CANNOT be embedded in any $F_{p^{i}}^{*}$ for $i = 1, 2, 3$ , or in other words, the $p^{2} - p + 1$ subgroup is as hard as $F_{p^{6}}^{*}$ . So, let us take a generator $g$ of the subgroup $T_{6}$ of order $p^{2} - p + 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 $x \mapsto x^{p}$ . In particular, the Galois group $G a l (F_{p^{6}} / F_{p^{2}}) = C_{3}$ is cyclic of order three and consists of the auromorphisms $1 = i d, σ = (x \mapsto x^{p^{2}}), σ^{2} = (x \mapsto x^{p^{4}})$ , so the corresponding trace map is given by

$T r : F_{p^{6}} \to F_{p^{2}} T r (x) = x + x^{p^{2}} + x^{p^{4}}$

So, how do we perform our key-exchange using my secret number $a$ and yours $b$ ? Well, I’ll send you $T r (g^{a})$ and as this is an element of the quadratic extension $F_{p^{2}}$ I’ll need just 2 pits instead of 6 and you will send me likewise $T r (g^{b})$ . I claim that the common key we (and only we) can compute is $T r (g^{a b})$ . How does this work?

Given any element $x \in T_{6} \subset F_{p^{6}}^{*}$ we can compute the 3-element set $C_{x} = x, σ (x), σ (x^{2})$ and hence the characteristic polynomial
$(t - x) (t - σ (x)) (t - σ^{2} (x))$

$= t^{3} - (x + σ (x) + σ^{2} (x)) t^{2} + (x σ (x) + x σ^{2} (x) + σ (x) σ^{2} (x)) t - x σ (x) σ^{2} (x)$

The first coefficient $x + σ (x) + σ^{2} (x)$ is the trace $T r (x)$ and the second and third coefficients are respectively $T r (x σ (x))$ and the norm $N (x)$ . Now, if $x \in T_{6}$ one can show that

$T r (x σ (x)) = T r (x)^{p}$ and $N (x) = 1$

That is, from knowing only $T r (x)$ we can compute the characteristic polynomial and hence recover the 3-element set $h, σ (h), σ^{2} (h)$ !

If I give you $T r (g^{a})$ you can compute from it the 3-set $g^{a}, σ (g^{a}), σ^{2} (g^{a})$ and raise them all the the b-th power (b being your secret number) to obtain

$g^{a b}, σ (g^{a})^{b}, σ^{2} (g^{a})^{b} = g^{a b}, σ (g^{a b}), σ^{2} (g^{a b})$

but then you also know our shared key $T r (g^{a b}) = g^{a b} + σ (g^{a b}) + σ^{2} (g^{a b})$ … Done!

profinite groups survival guide

Published December 14, 2007 by lieven

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 $G a l = G a l (\overset{―}{Q} / Q)$ aka the absolute Galois group. By definition it is the group of all $Q$ -isomorphisms of the algebraic closure $\overset{―}{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 $G a l$ . For, take any finite Galois extension $Q \subset K$ , then its Galois group $G_{K} = G a l (K / Q)$ is a finite group and there is a natural onto morphism $π_{K} : G a l \to G_{K}$ obtained by dividing out all $K$ -automorphisms of $\overset{―}{Q}$ . Moreover, all these projections fit together nicely. If we take a larger Galois extension $K \subset L$ then classical Galois theory tells us that there is a projection $π_{L K} : G_{L} \to G_{K}$ 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 $\overset{―}{Q}$ and hence a better and better finite approximation $G_{L}$ of the absolute Galois group $G a l$ . Still with me? Congratulations, you just rediscovered the notion of a profinite group! Indeed, the Galois group is the projective limit

$G a l = \underset{\leftarrow}{l i m} G_{L}$

over all finite Galois extensions $L / Q$ . If the term ‘projective limit’ scares you off, it just means that all the projections $π_{K L}$ 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 $G a l$ we would like to extend the classical Galois correspondence between subgroups and subfields $Q \subset K \subset \overset{―}{Q}$ and between normal subgroups and Galois subfields. For each finite Galois extension $K / Q$ we have a normal subgroup of finite index, the kernel $U_{K} = K e r (π_{K})$ of the projection map above. Let us take the set of all $U_{K}$ as a fundamental system of neighborhoods of the identity element in $G a l$ . This defines a topology on $G a l$ and this is the Krull topology. As every open subgroup has finite index it is clear that this turns $G a l$ 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 $G a l$ and the set of all subfields $Q \subset F \subset \overset{―}{Q}$ . 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 $G a l$ 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 $Γ = P S L_{2} (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} : Γ \to G_{U}$ and clearly if $U \subset V$ we have a quotient map of finite groups $π_{U V} : G_{U} \to G_{V}$ 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 $G_{U}$ and groupmorphisms $π_{U V}$ we can ask for the ‘best’ group mapping to each of the $G_{U}$ compatible with the groupmaps $G_{U V}$ . 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

$\hat{Γ} = \underset{\leftarrow}{l i m} G_{U}$

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 $G_{U}$ we know that there must be a groupmorphism to the best-one
$ϕ : Γ \to \hat{Γ}$ and therefore we call $\hat{Γ}$ 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 $G a l \to G L_{n} (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 $G a l \to G L_{n} (Q_{p})$ and call these Galois representations.

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

${rep}_{c} \hat{Γ} \to 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.

Anabelian vs. Noncommutative Geometry

Published December 12, 2007 by lieven

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 $G a l (\overset{―}{K} / K)$ , where K is an extension of finite type of the prime field) on (profinite) 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 ${\hat{π}}_{0, 3}$ , there is the profinite compactification of the modular group $S L_{2} (Z)$ , whose quotient by its centre
${\pm 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 $Γ = P S L_{2} (Z)$ as they correspond via Belyi-maps and his own notion of dessins d’enfants to smooth projective curves defined over $\overset{―}{Q}$ . One can now study the action of the absolute Galois group $G a l (\overset{―}{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

$\hat{Γ} = \underset{\leftarrow}{l i m} Γ / N$

where the limit is taken over all finite index normal subgroups $N ◃ P S L_{2} (Z)$ . In this way one realizes the absolute Galois group as a subgroup of the outer automorphism group of the profinite group $\hat{Γ}$ . 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 $\hat{Γ}$ the simple continuous representations ${simp}_{c} \hat{Γ}$ 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 $B_{3}$ . So a natural question presents itself : how are these two ‘geometrical’ objects ${simp}_{c} \hat{Γ}$ (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

$\hat{Z} = \underset{\leftarrow}{l i m} Z / n Z = \prod_{p} {\hat{Z}}_{p}$

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

${simp}_{c} \hat{Z} = μ_{\infty}$

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 = C - 0 = C^{*}$

Clearly we have an embedding $μ_{\infty} \subset 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 $c^{n}$ . Now suppose that there is a polynomial $a_{0} + a_{1} x + \dots + a_{m} x^{m}$ vanishing on all the continuous simples of $\hat{Z}$ then this means that the dimensions of the character-spaces of all finite quotients $Z / n Z$ 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

${simp}_{c} \hat{G} \subset 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 $P S L_{2} (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 P S L_{2} (Z)$ ? Next time we will clarify what this might be and show that indeed in this case the subset

${simp}_{c} \hat{Γ} \subset simp Γ$

will be a Zariski closed subset!