各種楕円曲線におけるECDLPの強度に関する考察

• 小寺, 健太

• 宮地, 充子

• 鄭, 振牟

抄録

楕円曲線暗号の安全性は楕円曲線状の離散対数問題（ECDLP）の難しさを根拠としている．現時点で最も強力なECDLPの解読手法は，一般的な離散対数問題に対する解読手法として知られるPollardのρ法であり，指数関数時間を要する．しかし近年，SemaevやGaudly，DiemらによりECDLPに対する指数計算法が提案され，ある条件下においてECDLPを準指数時間で解読できることを示した．本論文では，Weierstrass，Hessian，Montgomery，Edwardsといった各種楕円曲線上のECDLPに対する指数計算法に注目する．互いに同型写像を持つ各種曲線においてECDLPの解読時間の違いを実験的に確認し，その原因について検討する．

The security of elliptic curve cryptography is closely related to the complexity of solving the elliptic curve discrete logarithm problem (ECDLP). Today, the best practical attacks against general ECDLP are generic discrete logarithm algorithms such as Pollard's rho method, which takes an exponential time. Recently, there is a line of research on index calculus algorithms for ECDLP started by Semaev, Gaudry, and Diem. Under certain heuristic assumptions, such algorithms could lead to subexponential attacks to ECDLP in some cases. In this paper, we investigate the complexity of solving ECDLP for elliptic curves in various forms---including Hessian, Montgomery, (twisted) Edwards, and Weierstrass using index calculus algorithms. We will provide some insights and empirical evidence showing an affirmative answer in this paper.

収録刊行物

• コンピュータセキュリティシンポジウム2017論文集

  コンピュータセキュリティシンポジウム2017論文集 2017 (2), 2017-10-16

キーワード

• 楕円曲線暗号，ECDLP，指数計算法

詳細情報

• CRID: 1050011097170102656
• NII論文ID: 170000176467
• Web Site: http://id.nii.ac.jp/1001/00187233/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles