Presentation 1997/9/12
On the Complexity of Languages Associated with Discrete Log Cryptosystems
Takaharu Oomi, Hiroki Shizuya, Takao Nishizeki,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Consider the function to a discrete log cryptosystem. Sakurai and Shizuya defined such functions for five typical cryptosystems including the Diffie-Hellman key exchange scheme, gave the reductions among them. Associating with each function, they also defined a language to be the set of any pairs of input and output, namely the graph of a function, and discussed the computational complexity. However, it remains open to give reductions among these languages. In this paper, we resolve this open question. We show that these languages are equivalent with respect to the expected polynomial-time Turing reducibility.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) discrete logarithm / cryptosystem / protocol / language / reduction
Paper # ISEC97-32
Date of Issue

Conference Information
Committee ISEC
Conference Date 1997/9/12(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) On the Complexity of Languages Associated with Discrete Log Cryptosystems
Sub Title (in English)
Keyword(1) discrete logarithm
Keyword(2) cryptosystem
Keyword(3) protocol
Keyword(4) language
Keyword(5) reduction
1st Author's Name Takaharu Oomi
1st Author's Affiliation Department of System Information Sciences, Graduate School of Information Sciences, Tohoku University()
2nd Author's Name Hiroki Shizuya
2nd Author's Affiliation Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University
3rd Author's Name Takao Nishizeki
3rd Author's Affiliation Department of System Information Sciences, Graduate School of Information Sciences, Tohoku University
Date 1997/9/12
Paper # ISEC97-32
Volume (vol) vol.97
Number (no) 252
Page pp.pp.-
#Pages 12
Date of Issue