On the complexity of computing discrete logarithms over algebraic tori

Shuji Isobe; Eisuke Koizumi; Yuji Nishigaki; Hiroki Shizuya

doi:10.1007/978-3-642-10433-6_29

On the complexity of computing discrete logarithms over algebraic tori

Shuji Isobe, Eisuke Koizumi, Yuji Nishigaki, Hiroki Shizuya

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper studies the complexity of computing discrete logarithms over algebraic tori. We show that the order certified version of the discrete logarithm over general finite fields (OCDL, in symbols) reduces to the discrete logarithm over algebraic tori (TDL, in symbols) with respect to the polynomial-time Turing reducibility. This reduction means that if the integer factorization can be computed in polynomial time, then TDL is equivalent to the discrete logarithm DL over general finite fields with respect to the Turing reducibility.

Original language	English
Title of host publication	Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings
Pages	433-442
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-10433-6_29
Publication status	Published - 2009 Dec 14
Event	8th International Conference on Cryptology and Network Security, CANS 2009 - Kanazawa, Japan Duration: 2009 Dec 12 → 2009 Dec 14

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5888 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	8th International Conference on Cryptology and Network Security, CANS 2009
Country/Territory	Japan
City	Kanazawa
Period	09/12/12 → 09/12/14

Keywords

Algebraic tori
Order certified discrete logarithms
Turing reduction

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-10433-6_29

Cite this

Isobe, S., Koizumi, E., Nishigaki, Y., & Shizuya, H. (2009). On the complexity of computing discrete logarithms over algebraic tori. In Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings (pp. 433-442). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5888 LNCS). https://doi.org/10.1007/978-3-642-10433-6_29

On the complexity of computing discrete logarithms over algebraic tori. / Isobe, Shuji ; Koizumi, Eisuke; Nishigaki, Yuji et al.
Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. 2009. p. 433-442 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5888 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Isobe, S , Koizumi, E, Nishigaki, Y & Shizuya, H 2009, On the complexity of computing discrete logarithms over algebraic tori. in Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5888 LNCS, pp. 433-442, 8th International Conference on Cryptology and Network Security, CANS 2009, Kanazawa, Japan, 09/12/12. https://doi.org/10.1007/978-3-642-10433-6_29

Isobe S , Koizumi E, Nishigaki Y, Shizuya H. On the complexity of computing discrete logarithms over algebraic tori. In Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. 2009. p. 433-442. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-10433-6_29

Isobe, Shuji ; Koizumi, Eisuke ; Nishigaki, Yuji et al. / On the complexity of computing discrete logarithms over algebraic tori. Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. 2009. pp. 433-442 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{81d6a2b0f04145089a2b28b2ca5676b9,

title = "On the complexity of computing discrete logarithms over algebraic tori",

abstract = "This paper studies the complexity of computing discrete logarithms over algebraic tori. We show that the order certified version of the discrete logarithm over general finite fields (OCDL, in symbols) reduces to the discrete logarithm over algebraic tori (TDL, in symbols) with respect to the polynomial-time Turing reducibility. This reduction means that if the integer factorization can be computed in polynomial time, then TDL is equivalent to the discrete logarithm DL over general finite fields with respect to the Turing reducibility.",

keywords = "Algebraic tori, Order certified discrete logarithms, Turing reduction",

author = "Shuji Isobe and Eisuke Koizumi and Yuji Nishigaki and Hiroki Shizuya",

year = "2009",

month = dec,

day = "14",

doi = "10.1007/978-3-642-10433-6_29",

language = "English",

isbn = "3642104320",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "433--442",

booktitle = "Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings",

note = "8th International Conference on Cryptology and Network Security, CANS 2009 ; Conference date: 12-12-2009 Through 14-12-2009",

}

TY - GEN

T1 - On the complexity of computing discrete logarithms over algebraic tori

AU - Isobe, Shuji

AU - Koizumi, Eisuke

AU - Nishigaki, Yuji

AU - Shizuya, Hiroki

PY - 2009/12/14

Y1 - 2009/12/14

N2 - This paper studies the complexity of computing discrete logarithms over algebraic tori. We show that the order certified version of the discrete logarithm over general finite fields (OCDL, in symbols) reduces to the discrete logarithm over algebraic tori (TDL, in symbols) with respect to the polynomial-time Turing reducibility. This reduction means that if the integer factorization can be computed in polynomial time, then TDL is equivalent to the discrete logarithm DL over general finite fields with respect to the Turing reducibility.

AB - This paper studies the complexity of computing discrete logarithms over algebraic tori. We show that the order certified version of the discrete logarithm over general finite fields (OCDL, in symbols) reduces to the discrete logarithm over algebraic tori (TDL, in symbols) with respect to the polynomial-time Turing reducibility. This reduction means that if the integer factorization can be computed in polynomial time, then TDL is equivalent to the discrete logarithm DL over general finite fields with respect to the Turing reducibility.

KW - Algebraic tori

KW - Order certified discrete logarithms

KW - Turing reduction

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

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

U2 - 10.1007/978-3-642-10433-6_29

DO - 10.1007/978-3-642-10433-6_29

M3 - Conference contribution

AN - SCOPUS:71549149987

SN - 3642104320

SN - 9783642104329

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 433

EP - 442

BT - Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings

T2 - 8th International Conference on Cryptology and Network Security, CANS 2009

Y2 - 12 December 2009 through 14 December 2009

ER -

On the complexity of computing discrete logarithms over algebraic tori

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this