## Abstract

The certified discrete logarithm problem modulo p prime is a discrete logarithm problem under the conditions that the complete factorization of p-1 is given and by which the base g is certified to be a primitive root mod p. For the cryptosystems based on the intractability of certified discrete logarithm problem, Sakurai-Shizuya showed that breaking the Diffie-Hellman key exchange scheme reduces to breaking the Shamir 3-pass key transmission scheme with respect to the expected polynomial-time Turing reducibility. In this paper, we show that we can remove randomness from the reduction above, and replace the reducibility with the polynomial-time many-one. Since the converse reduction is known to hold with respect to the polynomial-time many-one reducibility, our result gives a stronger evidence for that the two schemes are completely equivalent as certified discrete log cryptosystems.

Original language | English |
---|---|

Pages (from-to) | 1198-1202 |

Number of pages | 5 |

Journal | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |

Volume | E86-A |

Issue number | 5 |

Publication status | Published - 2003 May |

## Keywords

- Certified discrete logarithm problem
- Deterministic reducibility
- Order
- Primitive root
- Probabilistic reducibility