Paper 2002/113

A Note on the Bilinear Diffie-Hellman Assumption

Yacov Yacobi

Abstract

Abstract. The Bi-linear Diffie-Hellman (BDH) intractability assumption is required to establish the security of new Weil-pairing based cryptosystems. BDH is reducible to most of the older believed-to-be-hard discrete-log problems and DH problems, but there is no known reduction from any of those problems to BDH. Let the bilinear mapping be e:G1 X G1->G2, where G1 and G2 are cyclic groups. We show that a many-one reduction from any of the relevant problems to BDH has to include an efficient mapping \phi:G2 ->G1 where \phi(g^{x})=f(x)P. Here g, and P are generators of the corresponding cyclic groups. The function \phi must be used in the reduction either before or after the call to oracle BDH. We show that if f(x)=ax^n+b for any constants a,b,n, then \phi could be used as an oracle for a probabilistic polynomial time solution for Decision Diffie-Hellman in G2. Thus such a reduction is unlikely.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Identity Based Encryption; Weil pairing
Keywords
Bi-linear pairingID based cryptosystems
Contact author(s)
yacov @ microsoft com
History
2002-08-10: received
Short URL
https://ia.cr/2002/113
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/113,
      author = {Yacov Yacobi},
      title = {A Note on the Bilinear Diffie-Hellman Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2002/113},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/113}},
      url = {https://eprint.iacr.org/2002/113}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.