電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2007-12-19 14:15
2冪算における直接計算法を用いたマルチスカラー倍算の効率性評価
山田尚志高木 剛公立はこだて未来大)・櫻井幸一九大
技報オンラインサービス実施中
抄録 (和) 楕円曲線に基づくデジタル署名アルゴリズム(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

研究会情報
研究会 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.)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2007-12-19 14:15:00 
発表時間 25 
申込先研究会 ISEC 
資料番号 IEICE-ISEC2007-121 
巻番号(vol) IEICE-107 
号番号(no) no.397 
ページ範囲 pp.59-66 
ページ数 IEICE-8 
発行日 IEICE-ISEC-2007-12-12 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会