A STRUCTURAL COMPARISON OF THE COMPUTATIONAL DIFFICULTY OF BREAKING DISCRETE LOG CRYPTOSYSTEMS

The complexity of breaking cryptosystems of which security is based on the discrete logarithm problem is explored. The cryptosystems mainly discussed are the Diffie-Hellman key exchange scheme (DH), the Bellare -Micali noninteractive oblivious transfer scheme (BM), the ElGamal pub lic-key cryptosystem (EG), the Okamoto conference-key sharing scheme ( CONF), and the Shamir 3-pass key-transmission scheme (3 PASS). The obt ained relation among these cryptosystems is that3PASS less than or equ al to FP/m CONF less than or equal to FP/m EG = FP/m BM = FP/m DH, whe re less than or equal to FP/m denotes the polynomial-time functionally many-to-one reducibility, i.e., a function version of the less than o r equal to p/m-reducibility. We further give some condition in which t hese algorithms have equivalent difficulty. One of such conditions sug gest another advantage of the discrete logarithm associated with ordin ary elliptic curves.