We will see later that the cyclic subgroup T6⊂F∗p6 is a 2-dimensional torus.
Take a finite set of polynomials fi(x1,…,xk)∈Fp[x1,…,xk] and consider for every fieldextension Fp⊂Fq the set of all k-tuples satisfying all these polynomials and call this set
X(Fq)=(a1,…,ak)∈Fkq : fi(a1,…,ak)=0 ∀i
Then, T6 being a 2-dimensional torus roughly means that we can find a system of polynomials such that
T6=X(Fp) and over the algebraic closure ¯Fp we have X(¯Fp)=¯F∗pׯF∗p and T6 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 : T6→Fp×Fp and j : Fp×Fp→T6 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 T6 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 Φ6(p)=p2−p+1 is again a prime number. Then, if ζ is a 13-th root of unity we have that Fp12=Fp(ζ). Consider the elements
{z=ζ+ζ−1y=ζ+ζ−1+ζ5+ζ−5
Then, for every (u,v)∈Fp×Fp define the map j to T6 by
j(u,v)=r−s√13r+s√13∈T6
and one can verify that this is indeed an element of T6 provided we take
{r=(3(u2+v2)+7uv+34u+18v+40)y2+26uy−(21u(3+v)+9(u2+v2)+28v+42)s=3(u2+v2)+7uv+21u+18v+14
Conversely, for t∈T6 write t=a+b√13 using the basis Fp6=Fp31⊕Fp3√13, so a,b∈Fp3 and consequently write
1+ab=wy2+u(y+y22)+v
with u,v,w∈Fp using the basis y2.y+y22,1 of Fp3/Fp. Okay, then the invers of j iis the map f : T6→Fp×Fp given by
f(t)=(uw+1,v−3w+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 Fp×Fp and that f is defined everywhere except at the two points
1,−2z5+6z3−4z−1⊂T6. Therefore, as long as we avoid these two points in our Diffie-Hellman key exchange, we can perform it using just 2=ϕ(6) pits : I will send you f(ga) allowing you to compute our shared key f(gab) or gab from my data and your secret number b.
But, where’s the cat in all of this? Unfortunately, the cat is dead…
One Comment