ECSTR aka XTR

By lieven

rationality & cryptography

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’…¹ ).

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,~\hdots$

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 $\mahbb{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 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 and yours ? 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!

Previous in series Next in series

I may even start to share their passion… [↩]

cryptography, Galois, groups, lattices, rationality, tori

1 comment
Posted in geometry
Written on Sat, 05 January 2008 at 3:00 pm
Tags: cryptography, Galois, groups, lattices, rationality, tori
If you liked this post, then consider subscribing to our full RSS feed.

One Response to “ECSTR aka XTR”

A cat called CEILIDH | neverendingbooks Says:
January 7th, 2008 at 9:23 am
[...] for rationality & cryptography tori & crypto : Diffie-Hellman or GCHQ? key-compression ECSTR aka XTRA cat called [...]

ECSTR aka XTR

rationality & cryptography

One Response to “ECSTR aka XTR”

Leave a Reply

Recent Posts

Recent Comments