Skip to content โ†’

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 Fq where q=pN is a prime-power of a large prime number p. If we call an element of the prime field Fp a pit (similar to bit when p=2) then we can measure transmssions in pits. An element hโˆˆFq requires N pits, for we can write the finite field as the quotient of ring of polynomials Fp[x]

Fq=Fp[x](f(x))

modulo an _irreducible_ polynomial f(x) of degree N. Hence, any hโˆˆFq can be written as a polynomial of degree <N,
h=a1+a2x+โ€ฆ+aNxNโˆ’1
with all aiโˆˆFp, so we can represent h=(a1,a2,โ€ฆ,aN) as N pits. Now, we are going to limit this number of pits (from N to about ฯ•(N) where ฯ• 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 Fqโˆ— while not compromising on the security of the public key system (the large order of the basic element gโˆˆFqโˆ— 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=p2 then the order of the cyclic group Fqโˆ— is p2โˆ’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 $ is a prime number.

Right, now define T2 to be the subgroup of Fqโˆ— 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 T2 (our torus in disguise)? Take dโˆˆFpโˆ— a non-square element, then we can write
Fq=Fp(d) and T2=a+bd : (a+bd)p+1=1 (here, a,bโˆˆFp). But we claim that
 (a+bd)p=aโˆ’bd. Indeed, ap=a,bp=b and from Fermatโ€™s little theorem we deduce that

โˆ’1=(dp)โ‰กdpโˆ’12 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 T2 as the algebraic variety of dimension one defined over Fp and given by the equation

T2=a+bdโˆˆFqโˆ— โˆฃ (a,b)โˆˆF2 : a2โˆ’db2=1

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

j : Fpโ†’T2  j(a)=a+daโˆ’d=a2+da2โˆ’d+2aa2โˆ’dd

which has a well-defined invers on the complement of 1,โˆ’1

f : T2โ€“1,โˆ’1โ†’Fp  f(a+bd)=1+ab

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 gaโˆˆT2 computed using my secret number a, Iโ€™ll send you (using only one pit) the number f(ga)โˆˆFp. On this number, you can apply the j-function to recover ga and then compute the common key  (ga)b=gab using your secret number b). Still, we didnt compromise on security because we used the most difficult elements around in Fqโˆ—. By going to higher dimensional tori one can even improve on the efficiency rate!

Published in featured

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *