| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-03-05 16:10 楕円離散対数問題を解く確率的アルゴリズムに関する研究 足原 修・相良佳孝・櫻木伸英・○松嶋智子（職能開発大）  IT2009-129 ISEC2009-137 WBS2009-108 |
|
| 抄録 | （和） | 一般的な楕円曲線上の離散対数問題に対する確率的な解法を提案する．この方式は，多数の乱数$H_i \in \{0,1,\cdots, g-1\} \; (i=1,2,\cdots,m)$に対して$Q+[H_i]P$を計算し，それらの点を$X$座標の値でソートすることで，$X$座標が等しく $H_i \ne H_j$となる$Q+[H_i]P$と$Q+[H_j]P$のペアを探し，$2K_{secret}+H_i+H_j \equiv 0 \pmod{g}$から$K_{secret}$を求める.ただし，$Q = [K_{secret}]P$とし，$g$を点$P$の位数とする．本論文では，確率1/2以上で解を求めることができる乱数の数$m$が$\sqrt{g}$以下であることを示す．さらに，この解法を拡張して， 計算量を少し増やすことで記憶領域のサイズを小さくする方式や，複数の計算機で効率的に並列処理を行う方式を示す． |
| （英） | In this paper a probabilistic algorithm to solve the ECDLP is presented. This scheme uses the symmetry of the elliptic curve, and can be applied to a wide class of elliptic curves. In the proposed scheme a large number of random integers $H_i \in \{0,1,\cdots, g-1\} \; (i=1,2,\cdots)$ are generated to calculate the points $Q+[H_i]P \; (i=1,2,\cdots)$, where $Q = [K_{secret}]P$ and $g$ is the order of the point $P$. Then, the scheme tries to find a pair of points $Q+[H_i]P$ and $Q+[H_j]P$ whose $X$-coordinates are the same value but $H_i \ne H_j$, i.e., one in the pair is the inverse of the other. If such a pair is found, the secret $K_{secret}$ can be calculated by $2K_{secret}+H_i+H_j \equiv 0 \pmod{g}$. We investigate the probability to find such a pair among $m$ random points on an elliptic curve. The probability of finding one or more pairs would be 1/2 when $m$ is of the order of $\sqrt{g}$. Furthermore, we discuss the techniques to reduce the size of disk storage and to parallelize the operation with multiple computers. It is also shown that the proposed algorithm can be extended to solve the usual discrete logarithm problem (DLP). |
|
| キーワード | （和） | 楕円曲線暗号 / 楕円離散対数問題 / ECDLP / DLP / 公開鍵暗号 / / / |
| （英） | ECDLP / elliptic curve / discrete logarithm problem / public key cryptography / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 445, ISEC2009-137, pp. 373-380, 2010年3月. | |
| 資料番号 | ISEC2009-137 | |
| 発行日 | 2010-02-25 (IT, ISEC, WBS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IT2009-129 ISEC2009-137 WBS2009-108 |
|
| 研究会情報 | |
| 研究会 | IT ISEC WBS |
| 開催期間 | 2010-03-04 - 2010-03-05 |
| 開催地（和） | 信州大学長野(工学)キャンパス |
| 開催地（英） | Nagano-Engineering Campus, Shinshu University |
| テーマ（和） | 一般：情報通信基礎サブソサイエティ合同研究会 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2010-03-IT-ISEC-WBS |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 楕円離散対数問題を解く確率的アルゴリズムに関する研究 |
| サブタイトル（和） | |
| タイトル（英） | A study on the probabilistic algorithm to solve the elliptic curve discrete logarithm problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 楕円曲線暗号 / ECDLP |
| キーワード(2)（和/英） | 楕円離散対数問題 / elliptic curve |
| キーワード(3)（和/英） | ECDLP / discrete logarithm problem |
| キーワード(4)（和/英） | DLP / public key cryptography |
| キーワード(5)（和/英） | 公開鍵暗号 / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 足原 修 / Osamu Ashihara / アシハラ オサム |
| 第1著者 所属（和/英） | 職業能力開発総合大学校 (略称： 職能開発大) Polytechnic University (略称： Polytechnic Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 相良 佳孝 / Yoshitaka Sagara / サガラ ヨシタカ |
| 第2著者 所属（和/英） | 職業能力開発総合大学校 (略称： 職能開発大) Polytechnic University (略称： Polytechnic Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 櫻木 伸英 / Nobuhide Sakuragi / サクラギ ノブヒデ |
| 第3著者 所属（和/英） | 職業能力開発総合大学校 (略称： 職能開発大) Polytechnic University (略称： Polytechnic Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 松嶋 智子 / Tomoko K. Matsushima / マツシマ トモコ |
| 第4著者 所属（和/英） | 職業能力開発総合大学校 (略称： 職能開発大) Polytechnic University (略称： Polytechnic Univ.) |
| 講演者 | 第4著者 |
| 発表日時 | 2010-03-05 16:10:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | IT2009-129, ISEC2009-137, WBS2009-108 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.444(IT), no.445(ISEC), no.446(WBS) |
| ページ範囲 | pp.373-380 |
| ページ数 | 8 |
| 発行日 | 2010-02-25 (IT, ISEC, WBS) |
[研究会発表申込システムのトップページに戻る]