Paper 2002/117

Diffie-Hellman Problems and Bilinear Maps

Jung Hee Cheon and Dong Hoon Lee

Abstract

We investigate relations among the discrete logarithm (DL) problem, the Diffie-Hellman (DH) problem and the bilinear Diffie-Hellman (BDH) problem when we have an efficient computable non-degenerate bilinear map $e:G\times G\to H$. Under a certain assumption on the order of $G$, we show that the DH problem on $$ implies the DH problem on $$, and both of them are equivalent to the BDH problem when $$ is {\it weak-invertible}. Moreover, we show that given the bilinear map $$ an injective homomorphism $$ enables us to solve the DH problem on $$ efficiently, which implies the non-existence a {\it self-bilinear} map $$ when the DH problem on $$ is hard. Finally we introduce a sequence of bilinear maps and its applications.