講演名 | 2006-07-20 Tateペアリングの効率的なアルゴリズム 白勢 政明, 高木 剛, 岡本 栄司, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | Tateペアリングを高速に計算する方法として,Duursma-Leeアルゴリズムとその改良版であるηTペアリングがある.これらのアルゴリズムは,(1)ある有限体での計算,(2)6次拡大体での計算,(3)もとの有限体でのべき乗計算と値の更新,の3ステップからなる.ηTペアリングのアルゴリズムでは,(3)の部分において3乗根を計算する必要がある.本稿では,(3)の部分を改良しi番目のループでは各値が改良前のアルゴリズムの3^i乗となるようにすることで,3乗根の計算を必要としないηTペアリングのアルゴリズムを提案する.また,Diffie-Hellmanペアの検証には2つのペアリングの計算が必要であるが,2つのペアリングを同時に計算し(2)の部分を改良することで,計算量が削減された検証アルゴリズムを提案する.提案方式は従来方式と比較して30~40%の高速化が達成できる. |
抄録(英) | Duursma-Lee algorithm and its variant (ηT pairing) can efficiently compute Tate pairing over supersingular curves with small characteristic. The algorithms consist of three main steps: (1) computations in a finite field. (2) computations hi the extension field of degree 6, (3) exponentiation calculation in the base field. We have to compute relatively slow cube roots in step (3). This paper proposes some novel algorithms for computing ηT pairing without cube root. The proposed algorithms compute 3^i-th power for each value in the i-th loop in step (3), and thus the cube roots are removed (but we obtain the pairing value powered by 3^k for some k). Moreover we propose some efficient algorithms in which two pairings are computed simultaneously and the part of (2) is improved. The proposed algorithms enable to enhance the speed for verifying a Diffie-Hellman pair. We can achieve 30~40% faster computation comparing with the previously known methods. |
キーワード(和) | Tateペアリング / _<ηT>ペアリング / Diffie-Hellmanペア |
キーワード(英) | Tate pairing / _<ηT> pairing Diffie-Henman pair |
資料番号 | ISEC2006-12,SITE2006-9 |
発行日 |
研究会情報 | |
研究会 | ISEC |
---|---|
開催期間 | 2006/7/13(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Information Security (ISEC) |
---|---|
本文の言語 | JPN |
タイトル(和) | Tateペアリングの効率的なアルゴリズム |
サブタイトル(和) | |
タイトル(英) | Efficient Algorithm for Tate Pairing |
サブタイトル(和) | |
キーワード(1)(和/英) | Tateペアリング / Tate pairing |
キーワード(2)(和/英) | _<ηT>ペアリング / _<ηT> pairing Diffie-Henman pair |
キーワード(3)(和/英) | Diffie-Hellmanペア |
第 1 著者 氏名(和/英) | 白勢 政明 / Masaaki SHIRASE |
第 1 著者 所属(和/英) | 公立はこだて未来大学情報アーキテクチャ学科 Future University-Hakodate School of Systems Information Science |
第 2 著者 氏名(和/英) | 高木 剛 / Tsuyoshi TAKAGI |
第 2 著者 所属(和/英) | 公立はこだて未来大学情報アーキテクチャ学科 Future University-Hakodate School of Systems Information Science |
第 3 著者 氏名(和/英) | 岡本 栄司 / Eiji OKAMOTO |
第 3 著者 所属(和/英) | 筑波大学システム情報工学研究科 Graduate School of Systems and Information Engineering, University of Tsukuba |
発表年月日 | 2006-07-20 |
資料番号 | ISEC2006-12,SITE2006-9 |
巻番号(vol) | vol.106 |
号番号(no) | 175 |
ページ範囲 | pp.- |
ページ数 | 8 |
発行日 |