Skip to content →

neverendingbooks Posts

A cat called CEILIDH

Published January 7, 2008 by lievenlb

We will see later that the cyclic subgroup $T_6 \subset \mathbb{F}_{p^6}^* $ is a 2-dimensional torus.

Take a finite set of polynomials $f_i(x_1,\ldots,x_k) \in \mathbb{F}_p[x_1,\ldots,x_k] $ and consider for every fieldextension $\mathbb{F}_p \subset \mathbb{F}_q $ the set of all k-tuples satisfying all these polynomials and call this set

$X(\mathbb{F}_q) = { (a_1,\ldots,a_k) \in \mathbb{F}_q^k~:~f_i(a_1,\ldots,a_k) = 0~\forall i } $

Then, $T_6 $ being a 2-dimensional torus roughly means that we can find a system of polynomials such that
$T_6 = X(\mathbb{F}_p) $ and over the algebraic closure $\overline{\mathbb{F}}_p $ we have $X(\overline{\mathbb{F}}_p) = \overline{\mathbb{F}}_p^* \times \overline{\mathbb{F}}_p^* $ and $T_6 $ 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) $f~:~T_6 \rightarrow \mathbb{F}_p \times \mathbb{F}_p $ and $j~:~\mathbb{F}_p \times \mathbb{F}_p \rightarrow T_6 $ 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 $T_6 $ 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 $\Phi_6(p)=p^2-p+1 $ is again a prime number. Then, if $\zeta $ is a 13-th root of unity we have that $\mathbb{F}_{p^{12}} = \mathbb{F}_p(\zeta) $. Consider the elements

$\begin{cases} z = \zeta + \zeta^{-1} \\ y = \zeta+\zeta^{-1}+\zeta^5+\zeta^{-5} \end{cases} $

Then, for every $~(u,v) \in \mathbb{F}_p \times \mathbb{F}_p $ define the map $j $ to $T_6 $ by

$j(u,v) = \frac{r-s \sqrt{13}}{r+s \sqrt{13}} \in T_6 $

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

$\begin{cases} r = (3(u^2+v^2)+7uv+34u+18v+40)y^2+26uy-(21u(3+v)+9(u^2+v^2)+28v+42) \\
s = 3(u^2+v^2)+7uv+21u+18v+14 \end{cases} $

Conversely, for $t \in T_6 $ write $t=a + b \sqrt{13} $ using the basis $\mathbb{F}_{p^6} = \mathbb{F}_{p^3}1 \oplus \mathbb{F}_{p^3} \sqrt{13} $, so $a,b \in \mathbb{F}_{p^3} $ and consequently write

$\frac{1+a}{b} = w y^2 + u (y + \frac{y^2}{2}) + v $

with $u,v,w \in \mathbb{F}_p $ using the basis ${ y^2.y+\frac{y^2}{2},1 } $ of $\mathbb{F}_{p^3}/\mathbb{F}_p $. Okay, then the invers of $j $ iis the map $f~:~T_6 \rightarrow \mathbb{F}_p \times \mathbb{F}_p $ given by

$f(t) = (\frac{u}{w+1},\frac{v-3}{w+1}) $

and it takes some effort to show that f and j are indeed each other inverses, that j is defined on all points of $\mathbb{F}_p \times \mathbb{F}_p $ and that f is defined everywhere except at the two points
${ 1,-2z^5+6z^3-4z-1 } \subset T_6 $. Therefore, as long as we avoid these two points in our Diffie-Hellman key exchange, we can perform it using just $2=\phi(6) $ pits : I will send you $f(g^a) $ allowing you to compute our shared key $f(g^{ab}) $ or $g^{ab} $ from my data and your secret number b.

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

One Comment

sobering-up

Published January 5, 2008 by lievenlb

Kea’s post reminded me to have a look at my search terms (the things people type into search engines to get redirected here). Quite a sobering experience…

Via Google Analytics I learn that 49,51% of traffic comes from Search Engines (compared to 26,17% from Referring Sites and 24,32% from direct hits) so I should take Search Terms more seriously! Above you can find the top-25.

On 1. there is neverendingbooks. Well, some people seem to remember the blog-name, but require google to remember the URL (neverendingbooks.org)…, okay, fair enough. But from then on… all search terms are iTouch related! The first ‘other’ term is puzzle m at 24. and believe me things do not improve afterwards. Here the only non-Touch related search terms in the top 100 :

  • neverendingbooks.org (40)
  • “puzzle m” (42)
  • moonshine mathematics (79)
  • necklace algebra (80)
  • “calabi-yau algebra (90)
  • “dessin d enfant” (91)
  • “lieven le bruyn” (95)
  • Mathieu group + M(13) (97)
  • 13 points 5 lines puzzle (98)
  • 15 itouch sliding puzzle (99)

the last one is really touching (sic). Is there anybody out there still interested in the mathematics, or should I turn this blog into a yaib (yet another iTouch blog) ???

4 Comments

ECSTR aka XTR

Published January 5, 2008 by lievenlb

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 $\mathbb{F}_{p^6} $ in the Diffie-Hellman key exchange while transmitting only $2=\phi(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 $\mathbb{F}_q $ for $q=p^N $ while using only $\phi(N) $ pits. That is, we want to have $N log(p) $ large (for safety) while at the same time $\phi(N) log(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,~\ldots $

that is, the products of the first so many prime numbers. The number of elements of the cyclic group $\mathbb{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 $\mathbb{F}_p^* $, that of order $p+1 $ can be embedded in $\mathbb{F}_{p^2}^* $, that of order $p^2+p+1 $ can be embedded in $\mathbb{F}_{p^3}^* $, BUT that the subgroup of order $\Phi_6(p)=p^2-p+1 $ CANNOT be embedded in any $\mathbb{F}_{p^i}^* $ for $i = 1,2,3 $, or in other words, the $p^2-p+1 $ subgroup is as hard as $\mathbb{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 $Gal(\mathbb{F}_{p^6}/\mathbb{F}_{p^2}) = C_3 $ is cyclic of order three and consists of the auromorphisms ${ 1=id, \sigma = (x \mapsto x^{p^2}), \sigma^2 = (x \mapsto x^{p^4}) } $, so the corresponding trace map is given by

$Tr~:~\mathbb{F}_{p^6} \rightarrow \mathbb{F}_{p^2} \qquad Tr(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 $Tr(g^a) $ and as this is an element of the quadratic extension $\mathbb{F}_{p^2} $ I’ll need just 2 pits instead of 6 and you will send me likewise $Tr(g^b) $. I claim that the common key we (and only we) can compute is $Tr(g^{ab}) $. How does this work?

Given any element $x \in T_6 \subset \mathbb{F}_{p^6}^* $ we can compute the 3-element set $C_x = { x,\sigma(x),\sigma(x^2) } $ and hence the characteristic polynomial
$~(t-x)(t-\sigma(x))(t-\sigma^2(x)) $

$ = t^3 – (x+\sigma(x)+\sigma^2(x))t^2 + (x \sigma(x)+ x\sigma^2(x)+\sigma(x)\sigma^2(x))t – x \sigma(x)\sigma^2(x) $

The first coefficient $x+\sigma(x)+\sigma^2(x) $ is the trace $Tr(x) $ and the second and third coefficients are respectively $Tr(x \sigma(x)) $ and the norm $N(x) $. Now, if $x \in T_6 $ one can show that

$Tr(x \sigma(x)) = Tr(x)^p $ and $N(x)=1 $

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

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

${ g^{ab},\sigma(g^a)^b,\sigma^2(g^a)^b } = { g^{ab},\sigma(g^{ab}),\sigma^2(g^{ab}) } $

but then you also know our shared key $Tr(g^{ab}) = g^{ab}+\sigma(g^{ab})+\sigma^2(g^{ab}) $… Done!

One Comment