« Previous Post
Next Post »

key-compression

By lieven

rationality & cryptography

  1. tori & crypto : Diffie-Hellman or GCHQ?
  2. key-compression
  3. ECSTR aka XTR
  4. A cat called CEILIDH
  5. Weil descent
  6. the crypto lattice

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 + \hdots + a_N x^{N-1} with all a_i \in \mathbb{F}_p, so we can represent h=(a_1,a_2,\hdots,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[/tex] 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 = (\tfrac{d}{p}) \equiv d^{\tfrac{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!

Previous in series Next in series
, , , ,

2 comments
Posted in geometry
Written on Fri, 04 January 2008 at 3:13 pm
Tags: , , , ,
If you liked this post, then consider subscribing to our full RSS feed.

2 Responses to “key-compression”

  1. Michel Van den Bergh Says:
    January 4th, 2008 at 5:34 pm

    Perhaps you should point out that DH key exchange makes sense in ANY group for which the discrete logarithm problem is hard. One popular choice is the group of rational points on an elliptic curve (ECC). Another possible choice is apparently the group of rational points on a torus.

    Of course there are no groups for which the DL problem has been PROVED to be hard.

    Rationality is not really necessary for point compression (elliptic curves for example are not rational). It the above example you could send b and one bit indicatig whether we use the biggest or the smallest number among a or p-a where a is a square root of 1 db^2 in F. A similar trivial idea in the case of ECC has been patented by certicom.

    Michel

  2. ECSTR aka XTR | neverendingbooks Says:
    January 5th, 2008 at 3:00 pm

    [...] Table of contents for rationality & cryptographytori & crypto : Diffie-Hellman or GCHQ?key-compressionECSTR aka [...]

Leave a Reply

AWSOM Powered