Skip to content →

the crypto lattice

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 Rn=RFpn/Fp1Gm corresponds to the permutation lattices Rn=Z[x]/(xn1). The action of the generator σ (the Frobenius) of the Galois group Gal(Fpn/Fp) acts on the lattice by multiplication with x.

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

Fp(y1,,yd)=Fp(T)=(Fqn(T))Gal

(recall from last time that the field on the right-hand side is the field of fractions of the Gal-invariants of the group-algebra of the free Abelian group T=ZZ where the rank is equal to the dimension d 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 T2 (LUC-system) and T6 (CEILIDH-system) are rational! So, what about the next cryptographic challenges? Are the tori T30, T210 etc. also rational varieties?

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

Tn=Z[x]/(Φn(x))

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

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

Fp(Tn)(z1,,zl)=Fp(y1,,yd+l)

which, sadly, is only of cryptographic-use if l is small (see below). A true rationality result on Tn was proved by A.A. Klyashko : Tn is rational whenever n=pa.qb a product of two prime powers.But then, 30=2×3×5 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 n/ϕ(n), but their method was of little practical use in the T30, for what their method gave was a rational map

T30×AFp32AFp40

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

Φaq(x)Φa(x)=Φa(xq)

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

Taq(Fp)×Ta(Fp)(RFpq/Fp1Ta)(Fp)=Ta(Fpq)

whenever aq is not divisible by p. Apply this to the special case when q=5,a=6 then we get

T30(Fp)×T6(Fp)RFp5/Fp1T6(Fp)

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

T30×AFp2AFp10

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…

Published in featured

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *