Paper 2005/030

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

A. A. Kalele and V. R. Sule


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.

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

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Bilinear Diffe Hellman Problempairing based schemeselliptic curve cryptography.
Contact author(s)
vrs @ ee iitb ac in
2005-10-10: last of 3 revisions
2005-02-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {A.  A.  Kalele and V.  R.  Sule},
      title = {Weak keys of the Diffie Hellman key exchange II : Pairing based schemes on elliptic curves.},
      howpublished = {Cryptology ePrint Archive, Paper 2005/030},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.