Last time we have seen that tori are dual (via their group of characters) to lattices with a Galois action. In particular, the Weil descent torus corresponds to the permutation lattices . The action of the generator (the Frobenius) of the Galois group acts on the lattice by multiplication with .

An old result of Masuda (1955), using an even older lemma by Speiser (1919), asserts than whenever the character-lattice of a torus is a permutation-lattice, the torus is rational, that is, the function-field of the torus is purely trancendental

(recall from last time that the field on the right-hand side is the field of fractions of the -invariants of the group-algebra of the free Abelian group where the rank is equal to the dimension of the torus).

The basic observation made by Rubin and Silverberg was that the known results on crypto-compression could be reformulated in the language of algebraic tori as : the tori (LUC-system) and (CEILIDH-system) are rational! So, what about the next cryptographic challenges? Are the tori , etc. also rational varieties?

Recall that as a group, the -points of the torus , is the subgroup of corresponding to the most crypto-challenging cyclic subgroup of order where is the n-th cyclotomic polynomial. The character-lattice of this crypto-torus we call the crypto-lattice and it is

(again the action of the Frobenius is given by multiplication with ) and hence has rank , explaining that the torus has dimension and hence that we can at best expect a compression from -pits to -pits. Note that the lattice is no longer a permutation lattice, so we cannot use the Masuda-Speiser result to prove rationality of .

What have mathematicians proved on before it became a hot topic? Well, there is an old conjecture by V. E. Voskresenskii asserting that all should be rational! Unfortunately, he could prove this only when is a prime power. Further, he proved that for all , the lattice is at least stably-rational meaning that it is rational upto adding free parameters, that is

which, sadly, is only of cryptographic-use if is small (see below). A true rationality result on was proved by A.A. Klyashko : is rational whenever a product of two prime powers.But then, the first unknown case…

At Crypto 2004, Marten van Dijk and David Woodruff were able to use an explicit form of Voskresenskii stable rationality result to get an asymptotic optimal crypto-compression rate of , but their method was of little practical use in the , for what their method gave was a rational map

and the number of added parameters (32) is way too big to be of use.

But then, one can use century-old results on cyclotomic polynomials to get a much better bound, as was shown in the paper Practical cryptography in high dimensional tori by the collective group of all people working (openly) on tori-cryptography. The idea is that whenever q is a prime and a is an integer not divisible by q, then on the level of cyclotomic polynomials we have the identity

On the level of tori this equality implies (via the character-lattices) an ismorphism (with same assumptions)

whenever aq is not divisible by p. Apply this to the special case when then we get

and because we know that is a 2-dimensional rational torus we get, using Weil descent, a rational map

which can be used to get better crypto-compression than the CEILIDH-system!

This concludes what I know of the OPEN state of affairs in tori-cryptography. I’m sure ‘people in hiding’ know a lot more at the moment and, if not, I have a couple of ideas I’d love to check out. So, when I seem to have disappeared, you know what happened…

A classic Andre Weil-tale is his narrow escape from being shot as a Russian spy

The war was a disaster for Weil who was a conscientious objector and so wished to avoid military service. He fled to Finland, to visit Rolf Nevanlinna, as soon as war was declared. This was an attempt to avoid being forced into the army, but it was not a simple matter to escape from the war in Europe at this time. Weil was arrested in Finland and when letters in Russian were found in his room (they were actually from Pontryagin describing mathematical research) things looked pretty black. One day Nevanlinna was told that they were about to execute Weil as a spy, and he was able to persuade the authorities to deport Weil instead.

However, Weil’s wikipedia entry calls this a story too good to be true, and continues

In 1992, the Finnish mathematician Osmo Pekonen went to the archives to check the facts. Based on the documents, he established that Weil was not really going to be shot, even if he was under arrest, and that Nevanlinna probably didn’t do - and didn’t need to do - anything to save him. Pekonen published a paper on this with an afterword by Andre Weil himself. Nevanlinna’s motivation for concocting such a story of himself as the rescuer of a famous Jewish mathematician probably was the fact that he had been a Nazi sympathizer during the war. The story also appears in Nevanlinna’s autobiography, published in Finnish, but the dates don’t match with real events at all. It is true, however, that Nevanlinna housed Weil in the summer of 1939 at his summer residence Korkee at Lohja in Finland - and offered Hitler’s Mein Kampf as bedside reading.

This old spy-story gets a recent twist now that it turns out that Weil’s descent theory of tori has applications to cryptography. So far, I haven’t really defined what tori are, so let us start with some basics.

The simplest (and archetypical) example of an algebraic torus is the multiplicative group(scheme) over a finite field which is the affine variety

. that is, the points of are precisely the couples and so are in one-to-one correspondence with the non-zero elements of . The coordinate ring of this variety is the ring of Laurant polynomials and the fact that multiplication induces a group-structure on the points of the variety can be rephrased by saying that this coordinate ring is a Hopf algebra which is just the Hopf structure on the group-algebra . This is the first indication of a connection between tori defined over and lattices (that is free -modules with an action of the Galois group . In this correspondence, the multiplicative group scheme corresponds to with the trivial action.

Now take a field extension , is there an affine variety, defined over whose -points are precisely the invertible elements ? Sure! Just take the multiplicative group over and write the elements x and y as (and a similar expression for y with and write the defning equation out, also with respect to this basis and this will then give you the equations of the desired variety, which is usually denoted by and called the Weil restriction of scalars torus.

A concrete example? Take and write and , then the defining equation becomes

whence , the intersection of two quadratic hypersurfaces in 4-dimensional space.

Why do we call a _torus? Well, as with any variety defined over we can also look at its points over a field-extension, for example over the algebraic closure and then it is easy to see that

(n copies)

and such algebraic groups are called tori. (To understand terminology, the compact group corresponding to is , so a torus).

In fact, it is already the case that the points of the restriction of scalar torus are and therefore we call this field a splitting field of the torus.

This is the general definition of an algebraic torus : a torus T over is an affine group scheme over such that, if we extend scalars to the algebraic closure (and then it already holds for a finite extension) we get an isomorphism of affine group schemes

in which case we call T a torus of dimension n. Clearly, the Galois group acts on the left hand side in such a way that we recover as the orbit space for this action.

Hence, anther way to phrase this is to say that an algebraic torus is the Weil descent of an action of the Galois group on the algebraic group .

Of course we can also rephrase this is more algebraic terms by looking at the coordinate rings. The coordinate ring of the algebraic group is the group-algebra of the rank n lattice (the free Abelian group of rank n), that is, . Now the Galois group acts both on the field as on the lattice coming from the action of the Galois group on the extended torus . In fact, it is best to denote this specific action on by and call the character group of . Now, we recover the coordinate ring of the -torus as the ring of invariants

Hence, the restriction of scalars torus is an n-dimensional torus over and its corresponding character group is the free Abelian group of rank n which can be written as and where the action of the cyclic Galois group s such that the generator as as multiplication by . That is, in this case the character group is a permutation lattice meaning that the -module has a basis which is permuted under the action of the Galois group. Next time we will encounter more difficult tori sich as the crypto-torus .

We will see later that the cyclic subgroup is a 2-dimensional torus.

Take a finite set of polynomials and consider for every fieldextension the set of all k-tuples satisfying all these polynomials and call this set

Then, being a 2-dimensional torus roughly means that we can find a system of polynomials such that and over the algebraic closure we have and is a subgroup of this product group.

It is known that all 2-dimensional tori are rational. In particular, this means that we can write down maps defined by rational functions (fractions of polynomials) and which define a bijection between the points where f and j are defined (that is, possibly excluding zeroes of polynomials appearing in denumerators in the definition of the maps f or j). But then, we can use to map f to represent ‘most’ elements of by just 2 pits, exactly as in the XTR-system.

Making the rational maps f and j explicit and checking where they are ill-defined is precisely what Karl Rubin and Alice Silverberg did in their CEILIDH-system. The acronym CEILIDH (which they like us to pronounce as ‘cayley’) stands for Compact Efficient Improves on LUC, Improves on Diffie-Hellman…

A Cailidh is a Scots Gaelic word meaning ‘visit’ and stands for a ‘traditional Scottish gathering’.

Between 1997 and 2001 the Scottish ceilidh grew in popularity again amongst youths. Since then a subculture in some Scottish cities has evolved where some people attend ceilidhs on a regular basis and at the ceilidh they find out from the other dancers when and where the next ceilidh will be.
Privately organised ceilidhs are now extremely common, where bands are hired, usually for evening entertainment for a wedding, birthday party or other celebratory event. These bands vary in size, although are commonly made up of between 2 and 6 players. The appeal of the Scottish ceilidh is by no means limited to the younger generation, and dances vary in speed and complexity in order to accommodate most age groups and levels of ability.

Anyway, let us give the details of the Rubin-Silverberg approach. Take a large prime number p congruent to 2,6,7 or 11 modulo 13 and such that is again a prime number. Then, if is a 13-th root of unity we have that . Consider the elements

Then, for every define the map to by

and one can verify that this is indeed an element of provided we take

Conversely, for write using the basis , so and consequently write

with using the basis of . Okay, then the invers of iis the map given by

and it takes some effort to show that f and j are indeed each other inverses, that j is defined on all points of and that f is defined everywhere except at the two points . Therefore, as long as we avoid these two points in our Diffie-Hellman key exchange, we can perform it using just pits : I will send you allowing you to compute our shared key or from my data and your secret number b.

But, where’s the cat in all of this? Unfortunately, the cat is dead…

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’…¹ ).

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

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

and that the subgroup of order can be embedded in , that of order can be embedded in , that of order can be embedded in , BUT that the subgroup of order CANNOT be embedded in any for , or in other words, the subgroup is as hard as . So, let us take a generator of the subgroup of order and do the Diffie-Hellman trick with it in a modified manner.

Galois groups of finite fields are cyclic and generated by the Frobenius . In particular, the Galois group is cyclic of order three and consists of the auromorphisms , so the corresponding trace map is given by

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

Given any element we can compute the 3-element set and hence the characteristic polynomial

The first coefficient is the trace and the second and third coefficients are respectively and the norm . Now, if one can show that

and

That is, from knowing only we can compute the characteristic polynomial and hence recover the 3-element set !

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

but then you also know our shared key … Done!

1. I may even start to share their passion… [↩]

The main application of tori to cryptography is to exchange keys more efficiently while preserving the same security standards.

In the Diffie-Hellman key-exchange one interchanges elements of the finite field where is a prime-power of a large prime number . If we call an element of the prime field a pit (similar to bit when ) then we can measure transmssions in pits. An element requires N pits, for we can write the finite field as the quotient of ring of polynomials

modulo an irreducible polynomial of degree N. Hence, any can be written as a polynomial of degree , with all , so we can represent as N pits. Now, we are going to limit this number of pits (from to about where is the Euler totient function, that is the number of integers smaller than N and coprime to it) by restricting the elements to be transfered to a subgroup of the group of units of the finite field while not compromising on the security of the public key system (the large order of the basic element of which is a power).

To see that this is indeed possible, let us consider the easiest case (that of ) and keep the discussion tori-free (those of you who know more will realize that Hilbert’s Satz 90 is never too far away…). If then the order of the cyclic group is so in order to get a safe system let us choose the large prime number such that also tex/2=r[/tex] is a prime number.

Right, now define to be the subgroup of of order and let be a generator of it that we will use in the Diffie-Hellman exchange. Can we describe the element of (our torus in disguise)? Take a non-square element, then we can write and (here, ). But we claim that . Indeed, and from Fermat’s little theorem we deduce that

where the middle term is the Legendre symbol which is equal to -1 because d was a non-square modulo p. That is, we can then write as the algebraic variety of dimension one defined over and given by the equation

Because is of dimension one over we can hope that most of its elements can be represented by just one pit (instead of the two pits necessary to represent them as elements of ). This is indeed the case, for we have explicit maps (in geometric terms, these maps show that is a rational variety)

which has a well-defined invers on the complement of

From the right-hand description of one deduces that indeed we have that . Using this we can indeed compress the Diffie-Hellman exchange by a factor 2.

Instead of giving you the element computed using my secret number a, I’ll send you (using only one pit) the number . On this number, you can apply the j-function to recover and then compute the common key using your secret number b). Still, we didnt compromise on security because we used the most difficult elements around in . By going to higher dimensional tori one can even improve on the efficiency rate!