A Note on the Relationships among Certified Discrete Log Cryptosystems

Eikoh Chida, Toshiya Itoh, Hiroki Shizuya

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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 languageEnglish
Pages (from-to)1198-1202
Number of pages5
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number5
Publication statusPublished - 2003 May


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


Dive into the research topics of 'A Note on the Relationships among Certified Discrete Log Cryptosystems'. Together they form a unique fingerprint.

Cite this