| 講演名 | 2007-12-19 2冪算における直接計算法を用いたマルチスカラー倍算の効率性評価 山田 尚志, 高木 剛, 櫻井 幸一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 楕円曲線に基づくデジタル署名アルゴリズム(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^kP直接計算法を用いた計算方式が2倍算を繰り返し計算する方式よりも4.7～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～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 |
| 資料番号 | ISEC2007-121 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2007/12/12(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2冪算における直接計算法を用いたマルチスカラー倍算の効率性評価 |
| サブタイトル（和） | |
| タイトル（英） | Efficiency Analysis of Multi-Scalar Multiplication using Direct Computation Method |
| サブタイトル（和） | |
| キーワード(1)（和/英） | マルチスカラー倍算 / multi-scalar multiplication |
| キーワード(2)（和/英） | Interleave法 / interleave method |
| キーワード(3)（和/英） | IL-NAF / IL-NAF |
| キーワード(4)（和/英） | IL-MOF / IL-MOF |
| 第 1 著者 氏名（和/英） | 山田 尚志 / Hisashi YAMADA |
| 第 1 著者 所属（和/英） | 公立はこだて未来大学システム情報科学研究科 Future University-Hakodate |
| 第 2 著者 氏名（和/英） | 高木 剛 / Tsuyoshi TAKAGI |
| 第 2 著者 所属（和/英） | 公立はこだて未来大学システム情報科学研究科 Future University-Hakodate |
| 第 3 著者 氏名（和/英） | 櫻井 幸一 / Kouichi SAKURAI |
| 第 3 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Kyushu University |
| 発表年月日 | 2007-12-19 |
| 資料番号 | ISEC2007-121 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 397 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |