A structural comparison of the computational difficulty of breaking discrete log cryptosystems

Kouichi Sakurai, Hiroki Shizuya

研究成果: ジャーナルへの寄稿学術誌査読

22 被引用数 (Scopus)

抄録

The complexity of breaking cryptosystems of which security is based on the discrete logarithm problem is explored. The cryptosystems mainly discussed are the Diffie-Hellman key exchange scheme (DH), the Bellare-Micali noninteractive oblivious transfer scheme (EM), the ElGamal public-key cryptosystem (EG), the Okamoto conference-key sharing scheme (CONF), and the Shamir 3-pass key-transmission scheme (3PASS). The obtained relation among these cryptosystems is that 3 PASS < CONF < EG =£" BM s DH, where <JJdenotes the polynomial-time functionally many-to-one reducibility, i.e., a function version of the <£ -reducibility. We further give some condition in which these algorithms have equivalent difficulty. One of such conditions suggest another advantage of the discrete logarithm associated with ordinary elliptic curves.

本文言語英語
ページ(範囲)29-43
ページ数15
ジャーナルJournal of Cryptology
11
1
DOI
出版ステータス出版済み - 1998

!!!All Science Journal Classification (ASJC) codes

  • ソフトウェア
  • コンピュータ サイエンスの応用
  • 応用数学

フィンガープリント

「A structural comparison of the computational difficulty of breaking discrete log cryptosystems」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル