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

A.  A.  Kalele; V.  R.  Sule

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

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.

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

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Bilinear Diffe Hellman Problem pairing based schemes elliptic curve cryptography.
Contact author(s): vrs @ ee iitb ac in
History: 2005-10-10: last of 3 revisions; 2005-02-10: received; See all versions
Short URL: https://ia.cr/2005/030
License: CC BY

BibTeX

@misc{cryptoeprint:2005/030,
      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},
      url = {https://eprint.iacr.org/2005/030}
}