ペアリング計算や楕円スカラー倍計算に適した準同型写像を持つ楕円曲線の生成について

摘要

本研究では，ペアリング計算やスカラー倍計算に適した準同型写像を持つ楕円曲線の生成方法を提案する.特殊な準同型写像を持つ楕円曲線の上での高速スカラー倍計算法が2001年にGallantらによって提案され，その後，その考えを応用したペアリング高速計算法が2005年にScottが提案された.これらの方法はペアリング暗号の実用化に向けて有望なものと考えられる.そこで，この方法が適用できる，すなわち特殊な準同型写像を持つ楕円曲線の探索方法が次の問題となる.特殊な準同型写像を持つ楕円曲線の具体的な生成法として髙島によるものがある.その方法で生成される楕円曲線は，ρ値と呼ばれる曲線の位数rと有限体の位数qのサイズ比で定義される量が2以上となる.これは，その中で用いられているCocks-Pinch法を用いていることによる.本研究では，ρ値が2よりも小さくなるような楕円曲線で特殊な準同型写像を持つものの生成法について検討する.%In the present paper, we proposed a method for generating elliptic curves having endomorphisms suitable for computing pairings and scalar multiplication. In 2001, Gallant et al.proposed a novel method for computing scalar multiplication over elliptic curves which have efficient computable endomorphisms. In 2005, Scott proposed an efficient method for computing pairings over such elliptic curves. Their results are very useful for construct of pairing-based cryptosystems. Takashima proposed a method for genarating elliptic curves over F_q having efficient computable endomorphisms. He uses the Cocks-Pinch method for generating elliptic curves and the ρ-values, defined by the ratio the size of the group order r and that of q, of elliptic curves generated by his method are larger than 2. In the present paper, we proposed a method for generating elliptic curves having endomorphisms and ρ-values smaller than 2.