@inproceedings{9fcce3c4ba7c47cb9f425c40747910f9,
title = "On the complexity of hyperelliptic discrete logarithm problem",
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.",
author = "Hiroki Shizuya and Toshiya Itoh and Kouichi Sakurai",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991 ; Conference date: 08-04-1991 Through 11-04-1991",
year = "1991",
doi = "10.1007/3-540-46416-6_29",
language = "English",
isbn = "9783540546207",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "337--351",
editor = "Davies, {Donald W.}",
booktitle = "Advances in Cryptology—EUROCRYPT 1991 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings",
address = "Germany",
}