TR-165: Key Exchange Using Chebychev Polynomials

Abstract

The well-known Diffie-Hellman protocol for key exchange LDin6] allows two parties to agree on a secret key without the key being sent along an insecure communication channel. This protocol is a special case of the following general scheme which allows two parties A and B to agree on an element of a key space K. Let F = {Fml m=0,1,2, …. } and G = {Gnl n=0,1,2, …. } be two families of functions defined on K having the property that for all m, n we have the equality F (Fn(x))=Fn(Fm(x)). Initially A and B agree on an element a E K which may be made public. Next, A chooses a private integer m and sends Fm(<X) to B while B chooses a private integer n and sends Gn(<X) to A Finally A computes Fm(G0(a)) while B computes G (Fm(<X)); by the assumption on F and G these two results are equal and serve as their common key. In all the examples given in this paper F = G and we shall assume this from now on; it would however be interesting to have examples where Ft= G. In the original Diffie­Hellman scheme F and G were each the set of functions {x-nm mod p, m=O, 1,2,3 … } (where pis prime) and K was the field Zp of integers modulo p. In [Rue88l F and G consisted of the functional powers of some function p(x). The condition that members of F commute with one another under functional composition is a very restrictive one. However there is another family of polynomials which commute under composition:- the Chebychev polynomials. Indeed it is readily seen that, if T 0 (x) = cos(m arccos x ), we have
Tm(T 0(x)) = cos(m arccos (cos (n arccos x )) = cos(mn arccos x) = T1110(x)
A basic recurrence, following from properties of the cosine function, relating the Chebychev polynomials is Tn+1(a) – 2a T0(a) + T0_1(<X) = 0