非超特異型楕円曲線上の暗号系の新たな利点について

概要

論文の詳細を見る
We investigate the complexity of breaking cryptosystems of which security is based on the discrete logarithm problem. The cryptosystems considered in this paper are the Diffie-Hellman's key exchange scheme, the Bellare-Micali's non-interactive oblivious transfer scheme, the ElGamal's public-key cryptosystem, the Okamoto's conference-key sharing scheme, and the Shamir's 3-pass key-transmission scheme. We show the reductions among the problems of breaking these cryptosystems. Further, we show if the complete factorization of p-1 is given, i. e. if the discrete logarithm problem is a certified one, then these cryptosystems are equivalent w. r. t. expected polynomial-time functionally Turing reducibility. We finally show that if the underlying group is the Jacobian of an elliptic curve over Z_p with a prime order, then these cryptosystems are equivalent w. r. t. polynomial-time functionally many-to-one reducibility. This paper is a summary of [6],supplemented with a recent result on the Okamoto's scheme.
1995-03-27