ECSTR aka XTR

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=\varphi (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 $\varphi (N)$ pits. That is, we want to have $Nlog(p)$ large (for safety) while at the same time $\varphi (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,\dots$

that is, the products of the first so many prime numbers. The number of elements of the cyclic group ${\mathbb{F}}_q^{\ast }$ 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^{\ast }$, that of order $p+1$ can be embedded in ${\mathbb{F}}_{p^2}^{\ast }$, that of order $p^2+p+1$ can be embedded in ${\mathbb{F}}_{p^3}^{\ast }$, BUT that the subgroup of order ${\mathrm{\Phi }}_6(p)=p^2-p+1$ CANNOT be embedded in any ${\mathbb{F}}_{p^i}^{\ast }$ for $i=1,2,3$, or in other words, the $p^2-p+1$ subgroup is as hard as ${\mathbb{F}}_{p^6}^{\ast }$. 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}\to {\mathbb{F}}_{p^2}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}^{\ast }$ 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!