the crypto lattice

By lieven

rationality & cryptography

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 $R_n=R^1_{\mathbb{F}_{p^n}/\mathbb{F}_p} \mathbb{G}_m$ corresponds to the permutation lattices $R_n^* = \mathbb{Z}[x]/(x^n-1)$ . The action of the generator $\sigma$ (the Frobenius) of the Galois group $Gal(\mathbb{F}_{p^n}/\mathbb{F}_p)$ 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 T^* of a torus is a permutation-lattice, the torus is rational, that is, the function-field of the torus $\mathbb{F}_p(T)$ is purely trancendental

$\mathbb{F}_p(y_1,\hdots,y_d) = \mathbb{F}_p(T) = (\mathbb{F}_{q^n}(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^* = \mathbb{Z} \oplus \hdots \oplus \mathbb{Z}$ 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 $T_{30}$ , $T_{210}$ etc. also rational varieties?

Recall that as a group, the $\mathbb{F}_p$ -points of the torus T_n , is the subgroup of $\mathbb{F}_{p^n}^*$ corresponding to the most crypto-challenging cyclic subgroup of order $\Phi_n(p)$ where $\Phi_n(x)$ is the n-th cyclotomic polynomial. The character-lattice of this crypto-torus T_n we call the crypto-lattice and it is

$T_n^* = \mathbb{Z}[x]/(\Phi_n(x))$

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

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

$\mathbb{F}_p(T_n)(z_1,\hdots,z_l) = \mathbb{F}_p(y_1,\hdots,y_{d+l})$

which, sadly, is only of cryptographic-use if is small (see below). A true rationality result on T_n was proved by A.A. Klyashko : T_n is rational whenever n=p^a.q^b a product of two prime powers.But then, $30=2 \times 3 \times 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/\phi(n)$ , but their method was of little practical use in the $T_{30}$ , for what their method gave was a rational map

$T_{30} \times \mathbb{A}^{32}_{\mathbb{F}_p} \rightarrow \mathbb{A}^{40}_{\mathbb{F}_p}$

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

$\Phi_{aq}(x) \Phi_a(x) = \Phi_a(x^q)$

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

$T_{aq}(\mathbb{F}_p) \times T_a(\mathbb{F}_p) \simeq (R^1_{\mathbb{F}_{p^q}/\mathbb{F}_p} T_a)(\mathbb{F}_p) = T_a(\mathbb{F}_{p^q})$

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

$T_{30}(\mathbb{F}_p) \times T_6(\mathbb{F}_p) \simeq R^1_{\mathbb{F}_{p^5}/\mathbb{F}_p} T_6(\mathbb{F}_p)$

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

$T_{30} \times \mathbb{A}^2_{\mathbb{F}_p} \rightarrow \mathbb{A}^{10}_{\mathbb{F}_p}$

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…

Previous in series

cryptography, Galois, lattices, rationality, tori

No comments
Posted in geometry
Written on Sat, 12 January 2008 at 12:07 pm
Tags: cryptography, Galois, lattices, rationality, tori
If you liked this post, then consider subscribing to our full RSS feed.

the crypto lattice

rationality & cryptography

Leave a Reply

Recent Posts

Recent Comments