A Note on the Relationships among Certified Discrete Log Cryptosystems

Eikoh CHIDA; Toshiya ITOH; Hiroki SHIZUYA

A Note on the Relationships among Certified Discrete Log Cryptosystems

Eikoh CHIDA, Toshiya ITOH, Hiroki SHIZUYA

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.5 pp.1198-1202

Publication Date: 2003/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Eikoh CHIDA, Toshiya ITOH, Hiroki SHIZUYA, "A Note on the Relationships among Certified Discrete Log Cryptosystems" in IEICE TRANSACTIONS on Fundamentals, vol. E86-A, no. 5, pp. 1198-1202, May 2003, doi: .
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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_1198/_p

Copy

@ARTICLE{e86-a_5_1198,
author={Eikoh CHIDA, Toshiya ITOH, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on the Relationships among Certified Discrete Log Cryptosystems},
year={2003},
volume={E86-A},
number={5},
pages={1198-1202},
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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - A Note on the Relationships among Certified Discrete Log Cryptosystems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1198
EP - 1202
AU - Eikoh CHIDA
AU - Toshiya ITOH
AU - Hiroki SHIZUYA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
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.
ER -