修士論文の和文要旨

修士論文の和文要旨
大学院
電気通信学研究科
氏
論
名樋口
文
題
敬士
博士前期課程
情報通信工学専攻
学籍番号 0430037
目 Pairing計算に適した楕円曲線の構成法
要
旨
ID-based暗号系やshort signatureなどで，有限体F q 上で定義された楕円曲線上
のpairingを用いた暗号プロトコルが提案されている．Pairingを用いた暗号の安
全性は，楕円曲線E(F q )の位数 r の部分群G上での楕円離散対数問題（ECDLP）と
有限体乗法群内で，1の r 乗根からなる部分群μ上での離散対数問題(DLP)に帰着
できる．現在のところECDLP，DLPは，それぞれlog r ≧ 160, log q k ≧1024を満
たしているならば計算量的に困難である．
楕円曲線をランダムに生成した場合，埋め込み次数 k は高い確率で非常に大き
な値をとることが知られている．k が非常に大きい値のとき，pairingを用いた暗
号プロトコルを実装する上で，有限体乗法群上の演算が困難となる．そのため，
一般的に埋め込み次数が小さいほうが実装上はよい．
Pairingを用いたプロトコルでは，小さい埋め込み次数をもつsupersingular曲
線が用いられることが多い．しかし，supersingular曲線は，埋め込み次数によっ
て，標数などに制限が存在し，それが問題となる．そのためsupersingular曲線で
はない，小さな埋め込み次数を持つ楕円曲線が必要である．
Supersingular曲線ではない，小さい埋め込み次数をもつ楕円曲線の生成法が研
究されている．既存の生成法として，MNT法とBLS法が知られている．MNT法，BLS
法は，楕円曲線の生成法のひとつCM法に基づいて楕円曲線を生成する．楕円曲線
の有理点群E(F q )の位数 r をもつ部分群をGとおき，ρ = log q／log rとおく．
MNT法は，埋め込み次数が3, 4, 6のみに適用でき，ρ∼1の楕円曲線を生成する．
BLS法は，任意の埋め込み次数に対して適用でき，一般ρ>2の楕円曲線を生成する．
Pairingを用いたshort signatureにおいては，ρ∼1であることが重要である．
本研究では，Blömer-May法を用いて，埋め込み次数5, 7をもちρ∼1となる楕円曲
線の構成について考察した．その結果，Blömer-May法を用いた方法では，目的の
楕円曲線を生成するのは難しいことがわかった．

Download Report