| 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 | |