| 講演名 | 2008-02-28 楕円曲線暗号におけるスカラー倍算の効率化に関する検討(情報通信基礎サブソサイエティ合同研究会) 寺嶋 直矢, 松嶋 智子, 足原 修, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 楕円曲線暗号では楕円曲線上のスカラー倍算の効率化が重要な課題となっている.これまでに有理点P,Qに対してP+Qおよび2Pの演算を基本に加算連鎖を導く幾つかの方法が研究されている.一方で,最近,比較的小さい整数λとμに対して,λP±μQを効率的に計算する方法が,Cietらや溝添らによって発表されている.本研究では,複数の基本演算が利用できる場合に,それぞれのコストを考慮した上で,任意の整数kに対してkPを最小のコストあるいはそれに近いコストで計算する加算連鎖を求める.最小コストの加算連鎖を探索するため,加算連鎖の木を生成する複数のプログラムを開発し,それらの結果をマージして,10^5(2^<18>)程度までの最小コストのスカラー倍算kPの加算連鎖パステーブルを作成した.また,最小コストとk値との関係について考察する.さらに,パステーブルで与えられる最大の整数k_ |
| 抄録(英) | Efficient elliptic curve arithmetic is crucial for cryptosystems based on elliptic curves. Such cryptosystems often require computing a scalar multiple kP of a base point P. Recently, some papers propose efficient algorithms to compute λP±μQ directly for small integers λ and μ from given points P and Q. We develop some programs to find the path with the minimum cost for each scalar multiplication kP under the condition that several operations of λP±μQ can be used with relatively small costs. We have construct the minimum-cost path table in which the maximum number of k (k_ |
| キーワード(和) | 楕円曲線暗号 / スカラー倍算 / 加算連鎖 / 木 / パステーブル |
| キーワード(英) | elliptic curves / scalar multiplication / addition chains / power tree / path table |
| 資料番号 | IT2007-41,ISEC2007-138,WBS2007-72 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2008/2/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 楕円曲線暗号におけるスカラー倍算の効率化に関する検討(情報通信基礎サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | A Study on Efficient Scalar Multiplication for Elliptic Curve Cryptosystems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 楕円曲線暗号 / elliptic curves |
| キーワード(2)（和/英） | スカラー倍算 / scalar multiplication |
| キーワード(3)（和/英） | 加算連鎖 / addition chains |
| キーワード(4)（和/英） | 木 / power tree |
| キーワード(5)（和/英） | パステーブル / path table |
| 第 1 著者 氏名（和/英） | 寺嶋 直矢 / Naoya TERASHIMA |
| 第 1 著者 所属（和/英） | 職業能力開発総合大学校情報システム工学科 Information Systems Engineering Dept., Polytechnic Univ. |
| 第 2 著者 氏名（和/英） | 松嶋 智子 / Tomoko K. MATSUSHIMA |
| 第 2 著者 所属（和/英） | 職業能力開発総合大学校情報システム工学科 Information Systems Engineering Dept., Polytechnic Univ. |
| 第 3 著者 氏名（和/英） | 足原 修 / Osamu ASHIHARA |
| 第 3 著者 所属（和/英） | 職業能力開発総合大学校情報システム工学科 Information Systems Engineering Dept., Polytechnic Univ. |
| 発表年月日 | 2008-02-28 |
| 資料番号 | IT2007-41,ISEC2007-138,WBS2007-72 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 498 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |