最小の論理命令数でのGF(3) 上の加算によるη_<i>T</i>ペアリングの高速実装

• Item type: Journal(1)
• 公開日: 2009-11-15
• タイトル: 最小の論理命令数でのGF(3) 上の加算によるη_<i>T</i>ペアリングの高速実装
• タイトル / 言語: en
• タイトル: Faster Implementation ofη_<i>T</i> Pairing Using Minimum Number of Logical Instructions for GF(3)-addition
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 一般論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 公立はこだて未来大学大学院システム情報科学研究科
• 著者所属: NTT情報流通プラットフォーム研究所
• 著者所属: 公立はこだて未来大学大学院システム情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems Information Science, Future University-Hakodate
• 著者所属(英): en
• 著者所属(英): NTT Information Sharing Platform Laboratories
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems Information Science, Future University-Hakodate
• 著者名: 川原, 祐人; 青木, 和麻呂; 高木, 剛
• 著者名(英): Yuto, Kawahara; Kazumaro, Aoki; Tsuyoshi, Takagi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，IDベース暗号などのプロトコルが構築可能であることからペアリング暗号が注目され，それにともない，プロトコルの構築に用いるペアリング暗号を効率的に計算することが必要となっている．標数3のηT ペアリングは素体GF(3) = {0, 1, 2}上の演算を基に構成される．HarrisonらはGF(3) の元の2ビットを用いた2進数への自然なビット割当てと論理命令OR，XORを用いてGF(3) 上の加算を7命令で構成したが，7命令が最小の論理命令数であるかどうかは証明されていない．本稿では，GF(3) 上の加算を論理命令数で評価し，最小の論理命令数で命令列を構成するために命令列の全数探索を行った．探索実験より，任意の論理命令やビット割当てを用いても5命令以下でGF(3) 上の加算を構成できず，またHarrisonらとは異なるビット割当てを用いて6命令でGF(3) 上の加算を構成した．さらにHarrisonらとは異なるビット割当てによる6命令のGF(3) 上の加算を用いてηT ペアリングの高速実装を行った．128-bitセキュリティと見積もられているGF(3509) 上のηT ペアリングの計算時間はAMD Opteron（2.2GHz）上で16.3 msecであり，従来の7命令でのGF(3) 上の加算を用いた場合と比較し約7%高速となった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently, pairing-based cryptosystems have attracted much attention in cryptography, since pairing-based cryptosystems can provide many novel applications such as ID-based cryptosystems. Then pairing-based cryptosystems are required to efficiently compute. TheηT pairing in characteristic three is implemented by arithmetic in GF(3) = {0, 1, 2}. Harrison, et al. reported an efficient implementation of the GF(3)-addition by using seven logical instructions (consisting of OR and XOR) with the two-bit encoding. It has not yet been proven whether seven is the minimum number of logical instructions for the GF(3)-addition. In this paper, we search the instruction sequences exhaustively for constructing the GF(3)-addition with the minimum number of logical instructions. In our experiment, we construct many implementations of the GF(3)-addition using only six logical instructions with different encodings. We then prove that there is no implementation of the GF(3)-addition using five logical instructions with any encoding of GF(3) by two bits. Moreover, we apply the new GF(3)-additions to an efficient software implementation of theηT pairing. The running time of theηT pairing over GF(3509), that is considered to be realized as 128-bit security, using the new GF(3)-addition with the encoding which is different from Harrison, et al. is 16.3 milliseconds on an AMD Opteron (2.2-GHz) processor. This is approximately 7% faster than the implementation using the previous GF(3)-addition with seven logical instructions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 50, 号 11, p. 2717-2726, 発行日 2009-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764