| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-12-19 14:15 2冪算における直接計算法を用いたマルチスカラー倍算の効率性評価 ○山田尚志・高木 剛（公立はこだて未来大）・櫻井幸一（九大）  ISEC2007-121 |
|
| 抄録 | （和） | 楕円曲線に基づくデジタル署名アルゴリズム（ECDSA）を使った署名検証において最も時間を要する演算は，2つのスカラーを用いるマルチスカラー倍算である． マルチスカラー倍算において，予備計算を必要とせずに高速に計算するクラスとして，Interleave法とNAF(IL-NAF)，Interleave法とMOF(IL-MOF)が知られている．IL-NAF/MOFを用いたマルチスカラー倍算では，連続する零桁（ゼロラン）の長さによってマルチスカラー倍算の効率性が評価できるため，IL-NAF/MOFのゼロランの長さ（ゼロラン長）の解析は重要である．本稿では，Markov鎖を用いた桁の分布解析からゼロランの平均長と発生確率を理論的に解析した．IL-NAFの平均ゼロラン長は$3$，IL-MOFの平均ゼロラン長は$256/85$となる．また，ゼロランの分布確率の解析をマルチスカラー倍算の計算量の見積りに適用し，$2^{k}P$直接計算法を用いた計算方式が2倍算を繰り返し計算する方式よりも$4.7\sim 4.8\%$高速になることを証明した． |
| （英） | The most time consuming operation to verify a signature with the elliptic curve digital signature algorithm (ECDSA) is a multi-scalar multiplication with two scalars. The Interleave method with NAF (IL-NAF) and the Interleave method with MOF (IL-MOF) are efficient methods for the multi-scalar multiplications without any pre-computations. We have to the estimate the length of the consecutive zero digits (zero-run) for efficiency analysis of multi-scalar multiplications using the IL-NAF/MOF. In this paper, we consider the appearance probability of the zero-runs and their average zero-run length using the markov chain. We present asymptotic length of the consecutive zero digits (zero-run length) of IL-NAF/MOF for randomly chosen $n$ bit two scalars. Indeed, the average zero-run length of the IL-NAF and IL-MOF is asymptotically 3 and 256/85, respectively. Moreover, we apply the appearance probability of zero-runs to the speed estimation of multi-scalar multiplications using the direct computation method. We prove that the IL-NAF/MOF using direct computation method can achieve $4.7\sim 4.8\%$ faster computation than the standard IL-NAF/MOF with iterated doubling. |
|
| キーワード | （和） | マルチスカラー倍算 / Interleave法 / IL-NAF / IL-MOF / / / / |
| （英） | multi-scalar multiplication / interleave method / IL-NAF / IL-MOF / / / / | |
| 文献情報 | 信学技報, vol. 107, no. 397, ISEC2007-121, pp. 59-66, 2007年12月. | |
| 資料番号 | ISEC2007-121 | |
| 発行日 | 2007-12-12 (ISEC) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2007-121 |
|
| 研究会情報 | |
| 研究会 | ISEC |
| 開催期間 | 2007-12-19 - 2007-12-19 |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2007-12-ISEC |
| 本文の言語 | 日本語 |
| タイトル（和） | 2冪算における直接計算法を用いたマルチスカラー倍算の効率性評価 |
| サブタイトル（和） | |
| タイトル（英） | Efficiency Analysis of Multi-Scalar Multiplications using Direct Computation Methods |
| サブタイトル（英） | |
| キーワード(1)（和/英） | マルチスカラー倍算 / multi-scalar multiplication |
| キーワード(2)（和/英） | Interleave法 / interleave method |
| キーワード(3)（和/英） | IL-NAF / IL-NAF |
| キーワード(4)（和/英） | IL-MOF / IL-MOF |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 山田 尚志 / Hisashi Yamada / ヤマダ ヒサシ |
| 第1著者 所属（和/英） | 公立はこだて未来大学 (略称： 公立はこだて未来大) Future University-Hakodate (略称： FUN) |
| 第2著者 氏名（和/英/ヨミ） | 高木 剛 / Tsuyoshi Takagi / タカギ ツヨシ |
| 第2著者 所属（和/英） | 公立はこだて未来大学 (略称： 公立はこだて未来大) Future University-Hakodate (略称： FUN) |
| 第3著者 氏名（和/英/ヨミ） | 櫻井 幸一 / Kouichi Sakurai / サクライ コウイチ |
| 第3著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-12-19 14:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2007-121 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.397 |
| ページ範囲 | pp.59-66 |
| ページ数 | 8 |
| 発行日 | 2007-12-12 (ISEC) |
[研究会発表申込システムのトップページに戻る]