Skip to content →

Category: featured

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

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

key-compression

Published January 4, 2008 by lievenlb

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 $\mathbb{F}_q $ where $q=p^N $ is a prime-power of a large prime number $p $. If we call an element of the prime field $\mathbb{F}_p $ a pit (similar to bit when $p=2 $) then we can measure transmssions in pits. An element $h \in \mathbb{F}_q $ requires N pits, for we can write the finite field as the quotient of ring of polynomials $\mathbb{F}_p[x] $

$\mathbb{F}_q = \frac{\mathbb{F}_p[x]}{(f(x))} $

modulo an _irreducible_ polynomial $f(x) $ of degree N. Hence, any $h \in \mathbb{F}_q $ can be written as a polynomial of degree $< N $,
$h = a_1 + a_2 x + \ldots + a_N x^{N-1} $
with all $a_i \in \mathbb{F}_p $, so we can represent $h=(a_1,a_2,\ldots,a_N) $ as N pits. Now, we are going to limit this number of pits (from $N $ to about $\phi(N) $ where $\phi $ is the Euler totient function, that is the number of integers smaller than N and coprime to it) by restricting the elements $h $ to be transfered to a subgroup of the group of units of the finite field $\mathbb{F}_q^* $ while not compromising on the security of the public key system (the large order of the basic element $g \in \mathbb{F}_q^* $ of which $h $ is a power).

To see that this is indeed possible, let us consider the easiest case (that of $N=2 $) 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 $q=p^2 $ then the order of the cyclic group $\mathbb{F}_q^* $ is $p^2-1 = (p-1)(p+1) $ so in order to get a safe system let us choose the large prime number $p $ such that also tex/2=r $ is a prime number.

Right, now define $T_2 $ to be the subgroup of $\mathbb{F}_q^* $ of order $p+1 $ and let $g $ be a generator of it that we will use in the Diffie-Hellman exchange. Can we describe the element of $T_2 $ (our torus in disguise)? Take $d \in \mathbb{F}_p^* $ a non-square element, then we can write
$\mathbb{F}_q = \mathbb{F}_p(\sqrt{d}) $ and $T_2 = { a+b\sqrt{d}~:~(a+b\sqrt{d})^{p+1}=1 } $ (here, $a,b \in \mathbb{F}_p $). But we claim that
$~(a+b\sqrt{d})^p = a -b \sqrt{d} $. Indeed, $a^p=a,b^p=b $ and from Fermat’s little theorem we deduce that

$ -1 = (\frac{d}{p}) \equiv d^{\frac{p-1}{2}}~mod(p) $

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 $T_2 $ as the algebraic variety of dimension one defined over $\mathbb{F}_p $ and given by the equation

$T_2 = { a+b\sqrt{d} \in \mathbb{F}_q^*~\mid~(a,b) \in \mathbb{F}^2~:~a^2-db^2=1 } $

Because $T_2 $ is of dimension one over $\mathbb{F}_p $ 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 $\mathbb{F}_q $). This is indeed the case, for we have explicit maps (in geometric terms, these maps show that $T_2 $ is a rational variety)

$j~:~\mathbb{F}_p \rightarrow T_2~\quad~j(a) = \frac{a+\sqrt{d}}{a-\sqrt{d}}=\frac{a^2+d}{a^2-d}+\frac{2a}{a^2-d}\sqrt{d} $

which has a well-defined invers on the complement of ${ 1,-1 } $

$f~:~T_2 – { 1,-1 } \rightarrow \mathbb{F}_p~\quad~f(a+b\sqrt{d}) = \frac{1+a}{b} $

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

Instead of giving you the element $g^a \in T_2 $ computed using my secret number a, I’ll send you (using only one pit) the number $f(g^a) \in \mathbb{F}_p $. On this number, you can apply the j-function to recover $g^a $ and then compute the common key $~(g^a)^b = g^{ab} $ using your secret number b). Still, we didnt compromise on security because we used the most difficult elements around in $\mathbb{F}_q^* $. By going to higher dimensional tori one can even improve on the efficiency rate!

3 Comments