key-compression

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 where is a prime-power of a large prime number . If we call an element of the prime field a pit (similar to bit when ) then we can measure transmssions in pits. An element requires N pits, for we can write the finite field as the quotient of ring of polynomials

modulo an irreducible polynomial of degree N. Hence, any can be written as a polynomial of degree , with all , so we can represent as N pits. Now, we are going to limit this number of pits (from to about where is the Euler totient function, that is the number of integers smaller than N and coprime to it) by restricting the elements to be transfered to a subgroup of the group of units of the finite field while not compromising on the security of the public key system (the large order of the basic element of which is a power).

To see that this is indeed possible, let us consider the easiest case (that of ) 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 then the order of the cyclic group is so in order to get a safe system let us choose the large prime number such that also tex/2=r[/tex] is a prime number.

Right, now define to be the subgroup of of order and let be a generator of it that we will use in the Diffie-Hellman exchange. Can we describe the element of (our torus in disguise)? Take a non-square element, then we can write and (here, ). But we claim that . Indeed, and from Fermat’s little theorem we deduce that

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 as the algebraic variety of dimension one defined over and given by the equation

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

which has a well-defined invers on the complement of

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

Instead of giving you the element computed using my secret number a, I’ll send you (using only one pit) the number . On this number, you can apply the j-function to recover and then compute the common key using your secret number b). Still, we didnt compromise on security because we used the most difficult elements around in . By going to higher dimensional tori one can even improve on the efficiency rate!

Previous in series

Next in series