On the Complexity of the Discrete Logarithm for a General Finite Group (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• GDL is the language whose membership problem is polynomial-time Turing equivalent to the discrete logarithm problem for a general finite group G. This paper gives a characterization of GDL from. the viewpoint of computational complexity theory. It is shown that GDL∈NP∩co-AM, assuming that G is in NP∩co-NP, and that the group law operation of G can be executed in polynomial time of the element size. Furthermore, as a natural probabilistic extension, the complexity of GDL is investigated under the assumption that the group law operation is executed in an expected polynomial time of the element size. In this case, it is shown that GDL∈MA∩co-AM if G∈MA∩co-MA. As a consequence, we show that GDL is not NP-complete unless the polynomial time hierarchy collapses to the second level.

• 社団法人電子情報通信学会の論文
• 1996-01-25

著者

• SAKURAI Kouichi

  Department of Computer Science and Communication Engineering, Kyushu University

• Sakurai Kouichi

  Department Of Computer Science And Communication Engineering Kyushu University

• Sakurai Kouichi

  Department Of Computer Science And Communication Engineering Faculty Of Information Science And Elec

• Shizuya Hiroki

  Education Center For Information Processing Tohoku University

• Shizuya Hiroki

  Education Center For Information Processing And Graduate School Of Information Sciences Tohoku Unive

• OKAMOTO Tatsuaki

  NTT Communications and Information Processing Laboratories

• Sakurai Kouichi

  Department Of Applied Science Faculty Of Engineering 36 Kyushu University

関連論文

• Reliable Key Distribution Scheme for Lossy Channels
• On Non-Pseudorandomness from Block Ciphers with Provable Immunity Against Linear Cryptanalysis (Special Section on Cryptography and Information Security)
• Password-Authenticated Key Exchange for Multi-Party with Different Passwords Using a Constant Number of Rounds
• Password-Authenticated Key Exchange for Multi-Party with Different Passwords Using a Constant Number of Rounds
• Password-Authenticated Key Exchange for Multi-Party with Different Passwords Using a Constant Number of Rounds
• A reliability analysis based scheduling algorithm in heterogeneous system
• A Flexible User-centric Resource Scheduling Algorithm
• Analysis and Comparison of Crytographic Techniques in E-voting and E-auction
• 1-out-of-L E-voting System with Efficient Computational Complexity Based on r-th Residue Encryption
• Reliable Key Distribution Scheme for Lossy Channels
• D-031 Preserving Integrity and Confidentiality of a Directed Acyclic Graph Model of Provenance
• Private Data Clustering based on Secure Approximation
• Analysis and Design for Private Message Board Systems
• A Note on AM Languages Outside NP ⋃ co-NP (Special Section on Cryptography and Information Security)
• A Note on the Complexity of Breaking Okamoto-Tanaka ID-Based Key Exchange Seheme (Special Section on Cryptography and Information Security)
• Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)
• On the Complexity of the Discrete Logarithm for a General Finite Group (Special Section on Cryptography and Information Security)
• On the Σ^b_1-Definability of Integer Factoring
• Improved Subset Difference Method with Ternary Tree
• Towards a Fairness Multimedia Transmission Using Layered-Based Multicast Protocol
• On the Security of the Okamoto-Tanaka ID-Based Key Exchange Scheme against Active Attacks
• On the Vulnerability of Exponent Recodings for the Exponentiation against Side Channel Attacks(Tamper-Resistance)(Cryptography and Information Security)
• Proposal and Analysis of a Distributed Online Certificate Status Protocol with Low Communication Cost(Application)(Cryptography and Information Security)
• Analysis and Design for Private Message Board Systems (Applications) (Cryptography and Information Security)
• Special Section on Discrete Mathematics and Its Applications
• Securing Provenance of Distributed Processes in an Untrusted Environment
• Equivalence problem and automorphisms of some abelian branched coverings of the Riemann sphere

もっと見る 閉じる

スポンサーリンク