A Note on the Relationships among Certified Discrete Log Cryptosystems
スポンサーリンク
概要
- 論文の詳細を見る
The certified discrete logarithm problem modulo p prime is a discrete logarithm problem under the conditions that the complete factorization of p - 1 is given and by which the base g is certified to be a primitive root mod p. For the cryptosystems based on the intractability of certified discrete logarithm problem, Sakurai-Shizuya showed that breaking the Diffie-Hellman key exchange scheme reduces to breaking the Shamir 3-pass key transmission scheme with respect to the expected polynomial-time Turing reducibility. In this paper, we show that we can remove randomness from the reduction above, and replace the reducibility with the polynomial-time many-one. Since the converse reduction is known to hold with respect to the polynomial-time many-one reducibility, our result gives a stronger evidence for that the two schemes are completely equivalent as certified discrete log cryptosystems.
- 社団法人電子情報通信学会の論文
- 2003-05-01
著者
-
ITOH Toshiya
Global Scientific Information and Computing Center (GSIC), Tokyo Institute of Technology
-
Chida Eikoh
Department Of Electricalengineering Ichinoseki National College Of Technology
-
Itoh Toshiya
Global Scientific Information And Computing Center (gsic) Tokyo Institute Of Technology
-
Shizuya Hiroki
Information Synergy Center And The Graduate School Of Information Sciences Tohoku University
-
Shizuya Hiroki
Information Synergy Center And Graduate School Of Information Sciences Tohoku University
-
Chida Eikoh
Department Of Electrical And Computer Engineering Ichinoseki National College Of Technology
-
ITOH Toshiya
Global Scientific Information and Computing Center, Tokyo Institute of Technology
関連論文
- Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length
- Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length
- Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities(Discrete Mathematics and Its Applications)
- Approximation Algorithms for the Highway Problem under the Coupon Model
- Approximation Preserving Reductions among Item Pricing Problems
- Constructing Families of ε-Approximate k-Wise Independent Permutations(Discrete Mathematics and Its Applications)
- A Note on the Relationships among Certified Discrete Log Cryptosystems
- On the Strength of the Strong RSA Assumption
- On the Security of Girault Key Agreement Protocols against Active Attacks
- The Computational Difficulty of Solving Cryptographic Primitive Problems Related to the Discrete Logarithm Problem(Public Key Cryptography)(Cryptography and Information Security)
- Complexity Analysis of the Cryptographic Primitive Problems through Square-Root Exponent(Discrete Mathematics and Its Applications)
- Online Algorithms for Convex Case Capital Investment
- Improved Approximation Lower Bounds for TSP with Distances One and Two
- A Secure Structured Multisignature Scheme Based on a Non-commutative Ring Homomorphism
- Improved Lower Bounds for Competitive Ratio of Multi-Queue Switches in QoS Networks(Discrete Mathematics and Its Applications)