On the probability distribution of Diffie-Hellman secret keys for many users

Diffie-Hellmann key exchange is one of the most common methods for securely exchanging cryptographic keys over a public channel for the communication between two users. About twenty years ago this method was generalized for many users.

The security of DH key exchange has been studied by several mathematicians and computer scientists. For instance, the probability distribution of DH secret keys between two users was solved by Massey and Waldvogel in 1993 (see [MW]). In his book [S] Igor Shparlinski asked the following question (Question VII.22 in [S]):  Obtain analogues of the explicit formula (13.5) for the distribution of Diffie-Hellman secret key gx1x2…xn  which is used in multiparty communication.

The more general question (if one replaces the multiplicative group of a finite field by an arbitrary cyclic group of order N) was answered by a mathematician working at Tallinn University of Technology. Furthermore, the number of factorizations of  t  mod  N  was derived.

Contact: Alar Leibak, Department of Cybernetics, Tallinn University of Technology. E-mail: alar.leibak (at) ttu.ee

[MW] J. L. Massey and C. P. Waldvogel, The probability distribution of Diffie-Hellmann key, Advances in Cryptology-AUSCRYPT ’92,  Lecture Notes in Comp. Sci. 718, Springer, Berlin (1993), 492–504.

[S] I. Shparlinski, Cryptographic applications of analytic number theory: complexity lower bounds and pseudorandomness, Springer, 2003.

%d bloggers like this: