On the Complexity of Hyperelliptic Discrete Logarithm Problem

Hiroki SHIZUYA; Toshiya ITOH; Kouichi SAKURAI

On the Complexity of Hyperelliptic Discrete Logarithm Problem

Hiroki SHIZUYA, Toshiya ITOH, Kouichi SAKURAI

Full Text Views

0

Cite this

Summary :

We give a characterization for the intractability of hyperelliptic discrete logarithm problem from a viewpoint of computational complexity theory. It is shown that the language of which complexity is equivalent to that of the hyperelliptic discrete logarithm problem is in NP co-AM, and that especially for elliptic curves, the corresponding language is in NP co-NP. It should be noted here that the language of which complexity is equivalent to that of the discrete logarithm problem defined over the multiplicative group of a finite field is also characterized as in NP co-NP.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.8 pp.2129-2135

Publication Date: 1991/08/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Cryptography and Information Security)

Category

Authors

Hiroki SHIZUYA
Toshiya ITOH
Kouichi SAKURAI

Keyword

Cite this

Copy

Hiroki SHIZUYA, Toshiya ITOH, Kouichi SAKURAI, "On the Complexity of Hyperelliptic Discrete Logarithm Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E74-A, no. 8, pp. 2129-2135, August 1991, doi: .
Abstract: We give a characterization for the intractability of hyperelliptic discrete logarithm problem from a viewpoint of computational complexity theory. It is shown that the language of which complexity is equivalent to that of the hyperelliptic discrete logarithm problem is in NP co-AM, and that especially for elliptic curves, the corresponding language is in NP co-NP. It should be noted here that the language of which complexity is equivalent to that of the discrete logarithm problem defined over the multiplicative group of a finite field is also characterized as in NP co-NP.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_8_2129/_p

Copy

@ARTICLE{e74-a_8_2129,
author={Hiroki SHIZUYA, Toshiya ITOH, Kouichi SAKURAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Complexity of Hyperelliptic Discrete Logarithm Problem},
year={1991},
volume={E74-A},
number={8},
pages={2129-2135},
abstract={We give a characterization for the intractability of hyperelliptic discrete logarithm problem from a viewpoint of computational complexity theory. It is shown that the language of which complexity is equivalent to that of the hyperelliptic discrete logarithm problem is in NP co-AM, and that especially for elliptic curves, the corresponding language is in NP co-NP. It should be noted here that the language of which complexity is equivalent to that of the discrete logarithm problem defined over the multiplicative group of a finite field is also characterized as in NP co-NP.},
keywords={},
doi={},
ISSN={},
month={August},}

Copy

TY - JOUR
TI - On the Complexity of Hyperelliptic Discrete Logarithm Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2129
EP - 2135
AU - Hiroki SHIZUYA
AU - Toshiya ITOH
AU - Kouichi SAKURAI
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 1991
AB - We give a characterization for the intractability of hyperelliptic discrete logarithm problem from a viewpoint of computational complexity theory. It is shown that the language of which complexity is equivalent to that of the hyperelliptic discrete logarithm problem is in NP co-AM, and that especially for elliptic curves, the corresponding language is in NP co-NP. It should be noted here that the language of which complexity is equivalent to that of the discrete logarithm problem defined over the multiplicative group of a finite field is also characterized as in NP co-NP.
ER -