平成24年3月 先端暗号フロンティアセミナー アブストラクト

高木 剛
題名: 合成数位数のTateペアリングの効率的な計算方法 発フレームワークFairyRing
アブストラクト: 合成数位数ペアリングを利用した新たな暗号プロトコルが提案されて いる. ペアリングの計算にはMiller's Algorithmが用いられ, その計 算量はMillerループの回数に依存する. 小林らにより,予備計算を 用いたWindow法ベースのMiller's Algorithmの高速化法が提案された. さらに, 楕円曲線上のスカラー倍算を高速化する手法として, 2進展開 と3進展開を組み合わせたWindow Hybrid Binary-Ternary Form(w-HBTF) が知られている. 本稿では, w-HBTFを用いて, Window法ベースの効率的 なMiller's Algorithmを提案する. 1024ビットの合成数位数ペアリン グをJava言語によりPC上で実装したところ, 幅w=54のw-HBTFを用いた 提案方式は,幅6のwNAFを用いたMiller's Algorithmよりも約8%高速に 計算することができた.

The 4th Meeting for Cryptology Frontier Group Abstract


Tsuyoshi Takagi
Title: Efficient Algorithm for Tate Pairing of Composite Order
Abstract: A lot of important cryptographic schemes are based on pairings of composite order. Miller's algorithm is used to compute pairings, and the time taken to compute the pairings depends on the cost of calculating the Miller loop. Kobayashi et al. proposed an efficient algorithm for computing Miller's algorithm by using a window method, called Window Miller's algorithm.We can compute scalar multiplication of points on elliptic curves by using a window hybrid binary-ternary form (w-HBTF). In this paper, we propose a Miller's algorithm that uses w-HBTF to compute Tate pairing efficiently by combining the w-HBTF with window Miller's algorithm. From our experiments of 1024-bit composite order N on a PC using JAVA, the proposed algorithm with w=54 was about 8% faster than the Window Miller's algorithm using wNAF of w=6.

[Back ]