I couldn’t believe my eyes. I was watching an episode of numb3rs, ‘undercurrents’ to be precise, and there it was, circled in the middle of the blackboard, CEILIDH, together with some of the key-exchange maps around it…

Only, the plot doesn’t involve any tori-crypto… okay, there is an I-Ching-coded-tattoo which turns out to be a telephone number, but that’s all. Still, this couldn’t just be a coincidence. Googling for ‘ ceilidh+numbers‘ gives as top hit the pdf-file of an article Alice in NUMB3Rland written by … Alice Silverberg (of the Rubin-Silverberg paper starting tori-cryptography). Alice turns out to be one of the unpaid consultants to the series. The 2-page article gives some insight into how ’some math’ gets into the script

Typically, Andy emails a draft of the script to the consultants. The FBI plot is already in place, and the writers want mathematics to go with it. The placeholder “math” in the draft is often nonsense or jargon; the sort of things people with no mathematical background might find by Googling, and think was real math. Since there’s often no mathematics that makes sense in those parts of the script, the best the consultants can do is replace jargon that makes us cringe a lot with jargon that makes us cringe a little.
From then on, it’s the Telephone Game. The consultants email Andy our suggestions (”replace ‘our discrete universes’ with ‘our disjoint universes’”; “replace the nonsensical ‘we’ve tried everything -a full frequency analysis, a Vignere deconstruction- we even checked for a Lucas sequence’ with the slightly less nonsensical ‘It’s much too short to try any cryptanalysis on. If it were longer we could try frequency analyses, or try to guess what kind of cryptosystem it is and use a specialized technique. For example, if it were a long enough Vigenere cipher we could try a Kasiski test or an index-of-coincidence analysis’). Andy chooses about a quarter of my sugges- tions and forwards his interpretation of them to the writers and producers. The script gets changed, and then the actors ad lib something completely dif- ferent (’disjointed universes’: cute, but loses the mathematical allusion; ‘Kasiski exam’ : I didn’t mean that kind of ‘test’).

She ends her article with :

I have mixed feelings about NUMB3RS. I still have concerns about the violence, the depiction of women, and the pretense that the math is accurate. However, if NUMB3RS could interest people in the power of mathematics enough for society to greater value and support mathematics teaching, learning, and research, and motivate more students to learnthat would be a positive step.

Further, there is a whole blog dedicated to some of the maths featuring in NUMB3RS, the numb3rs blog. And it was the first time I had to take a screenshot of a DVD, something usually off limits to the grab.app, but there is a simple hack to do it…

You may not have noticed, but the really hard work was done behind the scenes, resurrecting about 300 old posts (some of them hidden by giving them ‘private’-status). Ive only deleted about 10 posts with little or no content and am sorry I’ve self-destructed about 20-30 hectic posts over the years by pressing the ‘delete post’ button. I would have liked to reread them after all the angry mails Ive received. But, as Ive defended myself at the time, and as I continue to do today, a blog only records feelings at a specific moment. Often, the issue is closed for me once Ive put my frustrations in a post, and then Ill forget all about it. Sadly, the gossip-circuit in noncommutative circles is a lot, a lot, slower than my mood swings, so by the time people complain it’s no longer an issue for me and I tend to delete the post altogether. A blog really is a sort of diary. For example, it only struck me now, rereading the posts of the end of 2006, beginning of 2007, how depressed I must have been at the time. Fortunately, life has improved, somewhat… Still, after all these reminiscences, the real issue is : what comes next?

Some of you may have noticed that I’ve closed the open series on tori-cryptography and on superpotentials in a rather abrupt manner. It took me that long to realize that none of you is waiting for this kind of posts. You’re thinking : if he really wants to show off, let him do his damned thing on the arXiv, a couple of days a year, at worst, and then we can then safely ignore it, like we do with most papers. Isnt’t that true? Of course it is…

So, what are you waiting for? Here’s what I believe to be a sensible thing to try out. Over the last 4 years I must have posted well over 50 times what I believe noncommutative geometry is all about, so if you still don’t know, please consult the archive, I fear I can only repeat myself. Probably, it is more worthwhile to reach out to other approaches to noncommutative geometry, trying to figure out what, if anything, they are after, without becoming a new-age convert (’connes-vert’, I’d say). The top-left picture may give you an inkling of what I’m after… Besides, Im supposed to run a ‘capita selecta’ course for third year Bachelors and Ive chosen to read with them the book The music of the primes and to expand on the mathematics hinted only at in the book. So, I’ll totally immerse myself in Connes’ project to solve the Riemann-hypothesis in the upcoming months.

Again, rereading old posts, it strikes me how much effort I’ve put into trying to check whether technology can genuinely help mathematicians to do what they want to do more efficiently (all post categorized as iMath). I plan some series of posts re-exploring these ideas. The first series will be about the overhyped Web-2 thing of social-bookmarking. So, in the next weeks I’ll go undercover and check out which socialsites are best for mathematicians (in particular, noncommutative geometers) to embrace…

Apart from these, admittedly vague, plans I am as always open for suggestions you might have. So, please drop a comment..

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…