TY - JOUR

T1 - A Note on the Relationships among Certified Discrete Log Cryptosystems

AU - Chida, Eikoh

AU - Itoh, Toshiya

AU - Shizuya, Hiroki

PY - 2003/5

Y1 - 2003/5

N2 - 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.

AB - 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.

KW - Certified discrete logarithm problem

KW - Deterministic reducibility

KW - Order

KW - Primitive root

KW - Probabilistic reducibility

UR - http://www.scopus.com/inward/record.url?scp=0141903379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0141903379&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0141903379

VL - E86-A

SP - 1198

EP - 1202

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

SN - 0916-8508

IS - 5

ER -