Cryptology ePrint Archive: Report 2005/030

Weak keys of the Diffie Hellman key exchange II : Pairing based schemes on elliptic curves.

A. A. Kalele and V. R. Sule

Abstract: This paper develops a cryptanalysis of the pairing based Diffie Hellman (DH) key exchange schemes which have found important applications as in the tripartite exchange scheme proposed in \cite{joux}. The analysis of \emph{weak keys} of the standard DH scheme proposed in \cite{kas1} is applied to show existence of weak sessions for tripartite schemes over super-singular curves. It is shown that for such sessions the associated Bilinear Diffie Hellman Problem (BDHP) is solvable in polynomial time, without computing the private keys i.e. without solving the discrete logarithms. Similar applications of the analysis to Decisional Diffie Hellman Problem (DDHP)and the Identity Based DH scheme (IBS) are also developed. The tripartite key exchange scheme is analyzed in detail and it is shown that the number of weak keys increases in this scheme as compared to the standard two party DH scheme. It is shown that the random choice of private keys by the users independent of each other's knowledge is insecure in these schemes. Algorithms are suggested for checking weakness of private keys based on an order of selection. A modified tripartite key exchange scheme is presented in which detection of weak keys is incorporated.

Category / Keywords: Bilinear Diffe Hellman Problem, pairing based schemes, elliptic curve cryptography.

Date: received 7 Feb 2005, last revised 9 Oct 2005

Contact author: vrs at ee iitb ac in

Available format(s): PDF | BibTeX Citation

Note: This is a revision of the previous report 2005/030. This forms the second part of the report 2005/024.

Version: 20051010:052739 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]