(57)【要約】      （修正有）【課題】ミラー関数演算および最終冪乗演算のコストを小さくするペアリング演算装置を提供する。【解決手段】ペアリング演算装置１０は、有限体上に定義される所定の楕円曲線上の２点Ｐ，Ｑを入力し、有限体の拡大体の元であるペアリング値を出力する。ペアリング演算装置は、ミラー関数演算部２０と、最終冪乗部３０とを備える。ミラー関数演算部は、所定のペアリング方式に基づくミラー関数を演算する。最終冪乗部は、拡大体の元に対してミラー関数のループパラメータに基づき定まる値を冪乗する演算を含む。【選択図】図１
2015022167.tif 000002
【特許請求の範囲】
【請求項１】
有限体上に定義される所定の楕円曲線上の２点を入力し、前記有限体の拡大体の元であるペアリング値を出力するペアリング演算装置であって、
所定のペアリング方式に基づくミラー関数を演算するミラー関数演算部と、
前記拡大体の元に対して前記ミラー関数のループパラメータに基づき定まる値を冪乗する演算を含む最終冪乗部と、
を備えるペアリング演算装置。
【請求項２】
前記ミラー関数のループパラメータに基づき定まる値は、前記ミラー関数のループパラメータである
請求項１に記載のペアリング演算装置。
【請求項３】
前記ミラー関数のループパラメータに基づき定まる値は、前記ミラー関数のループパラメータを、前記ミラー関数のループパラメータの約数で除算した値である
請求項１に記載のペアリング演算装置。
【請求項４】
前記ミラー関数のループパラメータに基づき定まる値は、前記ミラー関数のループパラメータに対して、２ｌ（ｌは整数）を乗算した値である
請求項１に記載のペアリング演算装置。
【請求項５】
前記ミラー関数のループパラメータに基づき定まる値は、前記ミラー関数のループパラメータに対して、整数を加減算した値である
請求項１に記載のペアリング演算装置。
【請求項６】
前記ミラー関数のループパラメータは、符号付き２進展開をした２進表現におけるハミングウエイトが最小となる値である
請求項１に記載のペアリング演算装置。
【請求項７】
前記ペアリング演算装置は、標数ｐの有限体上に定義される位数ｒの所定の楕円曲線上の２点Ｐ，Ｑを入力し、前記有限体のｋ次拡大体の元であるペアリング値を出力するものであって、
Φｋ（ｐ）をｋ次円分多項式とし、Ａを２以上の整数とした場合、前記最終冪乗部は、前記ミラー関数演算部による演算結果に対して、（ｐｋ／２−１）・｛（ｐｋ／２＋１）／Φｋ（ｐ）｝・｛ＡΦｋ（ｐ）／ｒ｝を冪乗する
請求項１に記載のペアリング演算装置。
【請求項８】
前記最終冪乗部は、前記｛ＡΦｋ（ｐ）／ｒ｝を冪指数とした冪乗演算をする冪乗部を有し、
前記冪乗部は、
前記ミラー関数のループパラメータを冪指数とした冪乗演算を含む所定の式により複数の基数を算出する基数算出部と、
前記複数の基数のそれぞれに１以上の整数を冪乗した結果を全て乗算する式を、ベクトル性加算鎖を用いて演算するベクトル性加算鎖演算部と、
を含む請求項７に記載のペアリング演算装置。
【請求項９】
前記ミラー関数演算部は、Ｏｐｔｉｍａｌ  ａｔｅペアリングに基づくミラー関数を演算する
請求項１に記載のペアリング演算装置。
【請求項１０】
前記所定の楕円曲線は、ＢＮ曲線である
請求項１に記載のペアリング演算装置。
【請求項１１】
前記ミラー関数演算部は、Ｏｐｔｉｍａｌ  ａｔｅペアリングに基づくミラー関数を演算し、
前記所定の楕円曲線は、ＢＮ曲線であり、
前記ＢＮ曲線は、前記ｋ次拡大体の埋め込み次数ｋが１２であり、前記標数ｐが３６ｘ４＋３６ｘ３＋２４ｘ２＋６ｘ＋１であり、前記位数ｒが３６ｘ４＋３６ｘ３＋１８ｘ２＋６ｘ＋１であり、
前記ミラー関数のループパラメータｃは、６ｘ＋２である
請求項８に記載のペアリング演算装置。
【請求項１２】
前記ミラー関数演算部は、２進数で表現した位数ｒの桁数が下記表のｃｅｉｌ（ｌｏｇ  ｒ）の欄の何れかの値の場合、前記ミラー関数のループパラメータを下記表のｃの欄の対応する値とする
請求項１１に記載のペアリング演算装置。
【表１】
2015022167.tif 000042
【請求項１３】
前記所定の楕円曲線は、Ｆｒｅｅｍａｎ曲線である
請求項１に記載のペアリング演算装置。
【請求項１４】
前記ミラー関数演算部は、Ｏｐｔｉｍａｌ  ａｔｅペアリングに基づくミラー関数を演算し、
前記所定の楕円曲線は、Ｆｒｅｅｍａｎ曲線であり、
前記Ｆｒｅｅｍａｎ曲線は、前記ｋ次拡大体の埋め込み次数ｋが１０であり、前記標数ｐが２５ｘ４＋２５ｘ３＋２５ｘ２＋１０ｘ＋３であり、前記位数ｒが２５ｘ４＋２５ｘ３＋１５ｘ２＋５ｘ＋１であり、
前記ミラー関数のループパラメータｃは、−５ｘ−１である
請求項８に記載のペアリング演算装置。
【請求項１５】
前記ミラー関数演算部は、２進数で表現した位数ｒの桁数が下記表のｃｅｉｌ（ｌｏｇ  ｒ）の欄の何れかの値の場合、前記ミラー関数のループパラメータを下記表のｃの欄の対応する値とする
請求項１４に記載のペアリング演算装置。
【表２】
2015022167.tif 000043
【請求項１６】
有限体上に定義される所定の楕円曲線上の２点を入力し、前記有限体の拡大体の元であるペアリング値を出力するペアリング演算方法であって、
所定のペアリング方式に基づくミラー関数を演算するミラー関数演算ステップと、
前記拡大体の元に対して前記ミラー関数のループパラメータに基づき定まる値を冪乗する演算を含む最終冪乗ステップと、
を含むペアリング演算方法。
【請求項１７】
コンピュータに、有限体上に定義される所定の楕円曲線上の２点を入力し、前記有限体の拡大体の元であるペアリング値を出力するペアリング演算を実行させるプログラムであって、
前記コンピュータに、
所定のペアリング方式に基づくミラー関数を演算するミラー関数演算ステップと、
前記拡大体の元に対して前記ミラー関数のループパラメータに基づき定まる値を冪乗する演算を含む最終冪乗ステップと、
を実行させるプログラム。
【請求項１８】
標数ｐの有限体上に定義される位数ｒの所定の楕円曲線上の２点を入力し、前記有限体のｋ次拡大体の元であるペアリング値を出力するペアリング演算装置であって、
所定のペアリング方式に基づくミラー関数を演算するミラー関数演算部と、
前記ミラー関数演算部の演算結果に対して、｛Ａ（ｐｋ−１）／ｒ｝乗（Ａは２以上の整数）を演算する最終冪乗部と、
を備えるペアリング演算装置。
【請求項１９】
前記所定のペアリング方式は、Ｏｐｔｉｍａｌ  ａｔｅペアリングである
請求項１８に記載のペアリング演算装置。
【請求項２０】
標数ｐの有限体上に定義される位数ｒの所定の楕円曲線上の２点を入力し、前記有限体のｋ次拡大体の元であるペアリング値を出力するペアリング演算方法であって、
所定のペアリング方式に基づくミラー関数を演算するミラー関数演算ステップと、
前記ミラー関数演算ステップの演算結果に対して、｛Ａ（ｐｋ−１）／ｒ｝乗（Ａは２以上の整数）を演算する冪乗演算ステップと、
を含むペアリング演算方法。
【請求項２１】
コンピュータに、標数ｐの有限体上に定義される位数ｒの所定の楕円曲線上の２点を入力し、前記有限体のｋ次拡大体の元であるペアリング値を出力するペアリング演算を実行させるプログラムであって、
前記コンピュータに、
所定のペアリング方式に基づくミラー関数を演算するミラー関数演算ステップと、
前記ミラー関数演算ステップの演算結果に対して、｛Ａ（ｐｋ−１）／ｒ｝乗（Ａは２以上の整数）を演算する冪乗演算ステップと、
を実行させるプログラム。
【請求項２２】
標数ｐの有限体上に定義される位数ｒのＢＮ曲線上の２点を入力し、前記有限体のｋ次拡大体の元であるペアリング値を出力するペアリング演算装置であって、
Ｏｐｔｉｍａｌ  ａｔｅペアリングに基づくミラー関数を演算するミラー関数演算部と、
前記ミラー関数演算部による演算結果を冪乗する最終冪乗部と、
を備え、
前記ＢＮ曲線は、前記ｋ次拡大体の埋め込み次数ｋが１２であり、前記標数ｐが３６ｘ４＋３６ｘ３＋２４ｘ２＋６ｘ＋１であり、前記位数ｒが３６ｘ４＋３６ｘ３＋１８ｘ２＋６ｘ＋１であり、
前記ミラー関数演算部は、２進数で表現した位数ｒの桁数が下記表のｃｅｉｌ（ｌｏｇ  ｒ）の欄の何れかの値の場合、前記ミラー関数のループパラメータを下記表のｃの欄の対応する値とする
ペアリング演算装置。
【表３】
2015022167.tif 000044
【請求項２３】
標数ｐの有限体上に定義される位数ｒのＦｒｅｅｍａｎ曲線上の２点を入力し、前記有限体のｋ次拡大体の元であるペアリング値を出力するペアリング演算装置であって、
Ｏｐｔｉｍａｌ  ａｔｅペアリングに基づくミラー関数を演算するミラー関数演算部と、
前記ミラー関数演算部による演算結果を冪乗する最終冪乗部と、
を備え、
前記Ｆｒｅｅｍａｎ曲線は、前記ｋ次拡大体の埋め込み次数ｋが１０であり、前記標数ｐが２５ｘ４＋２５ｘ３＋２５ｘ２＋１０ｘ＋３であり、前記位数ｒが２５ｘ４＋２５ｘ３＋１５ｘ２＋５ｘ＋１であり、
前記ミラー関数演算部は、２進数で表現した位数ｒの桁数が下記表のｃｅｉｌ（ｌｏｇ  ｒ）の欄の何れかの値の場合、前記ミラー関数のループパラメータを下記表のｃの欄の対応する値とする
ペアリング演算装置。
【表４】
2015022167.tif 000045
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ペアリング演算装置、方法およびプログラムに関する。
【背景技術】
【０００２】
ペアリングベース暗号は、ペアリングと呼ばれる数学的な写像を用いる暗号である。ペアリング演算は処理が重い。従って、ペアリング演算を高速化して、ペアリングベース暗号の適用範囲を拡大することが望まれる。
【０００３】
ペアリング演算は、ミラー関数ステップと、最終冪乗ステップとを含む。最終冪乗ステップでは、固定の冪指数による有限体上の冪乗が演算される。冪指数に応じた加算鎖を予め決めておき、この加算鎖に従って冪乗を演算する方法が知られている。この方法では、楕円曲線を生成するためのパラメータｘのハミングウエイトを小さくするほど、最終冪乗ステップの演算コストを小さくすることができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】M.  Scott,  N.  Benger,  M.  Charlemagne,  L.  J.  D.  Perez  and  E.  J.  Kachisa，  ”On  the  Final  Exponentiation  for  Calculating  Pairings  on  Ordinary  Elliptic  Curves”，  Pairing-Based  Cryptography-Pairing  2009,  Springer  (2009),  LNCS  5671，  pp.  78-88.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、ペアリングベース暗号の処理の中には、複数のペアリング演算が含まれる。複数のペアリング演算を含む場合、複数の最終冪乗ステップをまとめて演算することができる。しかし、複数のミラー関数ステップをまとめて演算することは困難である。従って、ペアリングベース暗号の処理の中に複数のペアリング演算が含まれる場合、処理の全体の演算コストを小さくするためには、ミラー関数ステップの演算コストを小さくすることが重要となる。
【０００６】
ミラー関数ステップの演算コストは、ミラー関数のループパラメータのハミングウエイトが小さいほど、小さくなる。しかし、ミラー関数のループパラメータのハミングウエイトを小さくすると、パラメータｘのハミングウエイトが大きくなり、逆に最終冪乗ステップの演算コストが増大してしまう可能性が高い。このため、ミラー関数ステップの演算コストと最終冪乗ステップの演算コストの両者をともに小さくすることは難しかった。
【課題を解決するための手段】
【０００７】
実施形態のペアリング演算装置は、有限体上に定義される所定の楕円曲線上の２点を入力し、前記有限体の拡大体の元であるペアリング値を出力する。ペアリング演算装置は、ミラー関数演算部と、最終冪乗部とを備える。ミラー関数演算部は、所定のペアリング方式に基づくミラー関数を演算する。最終冪乗部は、前記拡大体の元に対して前記ミラー関数のループパラメータに基づき定まる値を冪乗する演算を含む。
【図面の簡単な説明】
【０００８】
【図１】ペアリング演算装置の構成図。
【図２】ミラーアルゴリズムを示す図。
【図３】ミラー関数のループパラメータを表す多項式を示す図。
【図４】最終冪乗部の構成図。
【図５】｛ＡΦｋ（ｐ）／ｒ｝の冪乗演算をする第３冪乗部の構成図。
【図６】ベクトル性加算鎖を実行するためのアルゴリズムを示す図。
【図７】ペアリング演算装置のハードウェア構成図。
【発明を実施するための形態】
【０００９】
（全体構成）
図１は、本実施形態のペアリング演算装置１０の構成を示すブロック図である。ペアリング演算装置１０は、例えば、ショート署名、三者間鍵共有およびＩＤベース暗号等のペアリングベース暗号処理に用いられる。
【００１０】
ペアリング演算装置１０は、標数ｐの有限体上に定義される位数ｒの所定の楕円曲線上の２点Ｐ，Ｑを入力する。そして、ペアリング演算装置１０は、有限体のｋ次拡大体の元であるペアリング値を出力する。より具体的には、ペアリング演算装置１０は、下記の式（１１）を演算し、演算結果をペアリング値として出力する。
【数１】
2015022167.tif 000003
【００１１】
式（１１）において、ｆは、所定のペアリング方式に基づいたミラー関数を含む演算を表す。所定のペアリング方式が例えばＴａｔｅペアリングの場合には、ｆは、ミラー関数ｆｒ，Ｐ（Ｑ）の演算を表す。所定のペアリング方式が例えばＡｔｅペアリングの場合には、ｆは、ミラー関数ｆｐ  ｍｏｄ  ｒ，Ｑ（Ｐ）の演算を表す。定のペアリング方式が例えばＯｐｔｉｍａｌ  ａｔｅペアリングの場合には、ｆは、ミラー関数ｆｃ，Ｑ（Ｐ）の演算結果に補正項ｇＱ（Ｐ）を掛けた値を表す。また、式（１１）において、Ａは、１以上の整数を表す。なお、Ａ＝１の場合、ペアリング演算装置１０が出力するペアリング値は、従来のペアリング演算の演算結果と同一となる。Ａの値の詳細については後述する。
【００１２】
ペアリング演算装置１０は、ミラー関数演算部２０と、最終冪乗部３０とを備える。
【００１３】
ミラー関数演算部２０は、所定の楕円曲線上の２点Ｐ，Ｑを入力する。そして、ミラー関数演算部２０は、所定のペアリング方式に基づくミラー関数を含む演算をして、有限体のｋ次拡大体の元を演算結果として出力する。本実施形態においては、ミラー関数演算部２０は、Ｏｐｔｉｍａｌ  ａｔｅペアリングに基づくミラー関数ｆｃ，Ｑ（Ｐ）を演算して、補正項ｇＱ（Ｐ）を掛けて出力する。ミラー関数演算部２０は、ＴａｔｅペアリングおよびＡｔｅペアリング等の他のペアリング方式に基づくミラー関数を演算してもよい。
【００１４】
最終冪乗部３０は、ミラー関数演算部２０による演算結果である有限体のｋ次拡大体の元に対して、Ａ（ｐｋ−１）／ｒを冪指数とする冪乗演算をする。ここで、最終冪乗部３０は、拡大体の元に対してミラー関数のループパラメータに基づき定まる値を冪乗する演算を含む。ミラー関数のループパラメータに基づき定まる値は、一例として、ミラー関数のループパラメータである。また、ミラー関数のループパラメータに基づき定まる値は、一例として、ミラー関数のループパラメータを、ミラー関数のループパラメータの約数で除算した値である。また、ミラー関数のループパラメータに基づき定まる値は、ミラー関数のループパラメータに対して、２ｌ（ｌは整数）を乗算した値である。また、ミラー関数のループパラメータに基づき定まる値は、ミラー関数のループパラメータに対して、整数を加減算した値である。なお、最終冪乗部３０の詳細については後述する。
【００１５】
本実施形態においては、ペアリング演算装置１０は、楕円曲線として、ＢＮ曲線またはＦｒｅｅｍａｎ曲線を用いる。ペアリング演算装置１０は、ＢＮ曲線およびＦｒｅｅｍａｎ曲線以外の楕円曲線を用いてもよい。
【００１６】
本実施形態においてペアリング演算装置１０が用いるＢＮ曲線の方程式は、Ｙ２＝Ｘ３＋ｂである。また、ＢＮ曲線は、拡大次数ｋが１２である。拡大次数は、埋め込み次数ともいう。
【００１７】
また、ＢＮ曲線は、有限体である定義体の標数ｐが、下記の式（１２）のｘの多項式により定まる。また、ＢＮ曲線は、位数ｒが、下記の式（１３）のｘの多項式により定まる。なお、ｘは、ｐ、ｒをともに素数とするように定められる１以上の整数である。
【数２】
2015022167.tif 000004
【００１８】
また、ＢＮ曲線は、ρ＝ｃｅｉｌ（ｌｏｇ  ｐ）／ｃｅｉｌ（ｌｏｇ  ｒ）＝１である。なお、ｌｏｇ  Ｘは、底が２のＸの対数を表す。また、ｃｅｉｌ（Ｘ）は、Ｘの小数点以下の値を切り上げる演算を表す。また、後述のｆｌｏｏｒ（Ｘ）は、Ｘの小数点以下の値を切り捨てる演算を表す。
【００１９】
従って、ρ＝１とは、ｐを２進数で表現した場合の桁数と、ｒを２進数で表現した場合の桁数とが同一であることを意味する。
【００２０】
本実施形態においてペアリング演算装置１０が用いるＦｒｅｅｍａｎ曲線は、拡大次数ｋが１０である。また、Ｆｒｅｅｍａｎ曲線は、有限体である定義体の標数ｐが、下記の式（１４）のｘの多項式により定まる。また、Ｆｒｅｅｍａｎ曲線は、位数ｒが、下記の式（１５）のｘの多項式により定まる。
【数３】
2015022167.tif 000005
【００２１】
また、Ｆｒｅｅｍａｎ曲線は、ρ＝ｃｅｉｌ（ｌｏｇ  ｐ）／ｃｅｉｌ（ｌｏｇ  ｒ）＝１である。
【００２２】
（ミラー関数演算部２０）
図２は、ミラー関数演算部２０で実行されるミラーアルゴリズムを示す。ミラー関数演算部２０は、図２に示すミラーアルゴリズムを実行して、ミラー関数を演算する。
【００２３】
“Ｉｎｐｕｔ：”のステップにおいて、ミラー関数演算部２０は、群Ｇ１に含まれるＰ、群Ｇ２に含まれるＱ、および、符号付き２進展開で表されたｒを入力する。ｒは、ミラー関数のループパラメータと呼ばれる。ｒｉは、符号付き２進展開で表されたｒにおけるｉ桁目の値を示す。符号付き２進展開については後述する。
【００２４】
“Ｏｕｔｐｕｔ：”のステップにおいて、ミラー関数演算部２０は、ｆｒ，Ｐ（Ｑ）を出力する。ミラー関数演算部２０は、“１：”〜“１０：”のステップの実行が完了した後に、“Ｏｕｔｐｕｔ：”のステップを実行する。
【００２５】
“２：”〜“９：”のステップにおいて、最終冪乗部３０は、符号付き２進表現で表されたｒの最上位桁から最下位桁まで桁毎にループ処理を実行する。なお、ｉは、処理対象となっている桁数を表す。
【００２６】
“２：”〜“９：”のループ内における“４：”のステップにおいて、ミラー関数演算部２０は、ｒｉが１の場合には“５：”のステップの処理を行い、ｒｉが−１の場合には“７：”のステップの処理を行い、ｒｉが０の場合には、“５：”のステップと“７：”のステップの処理を飛ばして次の処理に進むという条件判断を実行している。
【００２７】
そして、“２：”〜“９：”のループ処理が完了すると、“１０：”のステップにおいて、ミラー関数演算部２０は、ｆの値を返して処理を終了する。
【００２８】
ここで、ミラー関数のループパラメータｃ（＝ｒ）は、符号付き２進展開をした２進表現におけるハミングウエイト（符号付きハミングウエイト）が最小となる値に予め設定される。即ち、ミラー関数演算部２０は、符号付きハミングウエイトが最小となるように予め設定されたミラー関数のループパラメータｃを用いて、ミラー関数を演算する。なお、ミラー関数のループパラメータｃは、符号付きハミングウエイトが最小に近い値であってもよい。
【００２９】
符号付き２進展開とは、整数ａを、下記の式（１６）に示すように、２進数の桁の重みに対応する値（２０、２１、２２、２３…等の２のｉ乗）に係数ａｉを乗算した値の総和の式に展開することをいう。
【数４】
2015022167.tif 000006
【００３０】
なお、ｉは、０以上の整数である。２進数の桁の重みに対応する値は、同一値が重複して用いられない。
【００３１】
そして、式（１６）において、係数ａｉは、−１、０、１の何れかの値である。
【００３２】
符号付きハイミングウエイトとは、このように符号付き２進展開をした整数における、非０の項の個数（即ち、係数ａｉが−１または１の項の個数）を表す。
【００３３】
ミラー関数演算部２０は、整数であるｒをこのような符号付き２進展開をした２進数を、ミラーアルゴリズムのループパラメータｃとして入力する。このため、ミラー関数演算部２０は、ステップ“４：”の条件判断でｒｉが１であると判断される桁数とステップ“６：”の条件判断でｒｉが−１であると判断される桁数の合計を最小または最小に近い値とすることができる。これにより、ミラー関数演算部２０は、ステップ“５：”の実行回数とステップ“７：”の実行回数の合計を最小または最小に近い回数することができる。この結果、ミラー関数演算部２０は、ミラー関数の演算コストを小さくすることができる。
【００３４】
図３は、Ｔａｔｅペアリング、ＡｔｅペアリングおよびＯｐｔｉｍａｌ  ａｔｅペアリングのそれぞれのミラー関数のループパラメータをｘで表す多項式を示す。
【００３５】
ミラー関数演算部２０は、Ｏｐｔｉｍａｌ  ａｔｅペアリングの他、例えばＴａｔｅペアリングまたはＡｔｅペアリングでミラー関数を演算してもよい。
【００３６】
ＴａｔｅペアリングでＢＮ曲線を用いる場合、ミラー関数のループパラメータｃ（＝ｒ）は、３６ｘ４＋３６ｘ３＋２４ｘ２＋６ｘ＋１である。また、ＴａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、ミラー関数のループパラメータｃ（＝ｒ）は、２５ｘ４＋２５ｘ３＋２５ｘ２＋１０ｘ＋３である。
【００３７】
ＡｔｅペアリングでＢＮ曲線を用いる場合、ミラー関数のループパラメータｃ（＝ｐ  ｍｏｄ  ｒ）は、６ｘ２である。また、ＡｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、ミラー関数のループパラメータｃ（＝ｐ  ｍｏｄ  ｒ）は、１０ｘ２＋５ｘ＋２である。
【００３８】
そして、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、ミラー関数のループパラメータｃは、６ｘ＋２である。また、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、ミラー関数のループパラメータｃは、−５ｘ−１である。
【００３９】
ここで、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、位数ｒの２進数の桁数を２２４桁〜２８７桁とすると、ｃの符号付きハミングウエイトの最小値は、３となる。位数ｒの２進数の桁数が２２４桁〜２８７桁のそれぞれの場合に、標数ｐおよび位数ｒのそれぞれが素数となり、且つ、符号付きハミングウエイトが最小である３となるような、ミラー関数のループパラメータｃを探索すると、下記の表１に示す通りとなる。
【表１】
2015022167.tif 000007
【００４０】
そこで、ミラー関数演算部２０は、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合であって、２進数で表現した位数ｒの桁数が表１のｃｅｉｌ（ｌｏｇ  ｒ）の欄の何れかの値の場合には、ミラー関数のループパラメータを表１のｃ（＝６ｘ＋２）の欄の対応する値とする。これにより、ミラー関数演算部２０によれば、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合に、ミラー関数の演算コストを最小とすることができる。なお、表１の“ｐ  ｍｏｄ  ４”は、ｐを４で除算した余りを表す。
【００４１】
また、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、位数ｒの２進数の桁数を２２４桁〜２８８桁とすると、ｒの符号付きハミングウエイトの最小値は、４となる。位数ｒの２進数の桁数が２２４桁〜２８８桁のそれぞれの場合に、標数ｐおよび位数ｒのそれぞれが素数となり、且つ、符号付きハミングウエイトが最小である４となるような、ミラー関数のループパラメータｃを探索すると、下記の表２に示す通りとなる。
【表２】
2015022167.tif 000008
【００４２】
そこで、ミラー関数演算部２０は、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合であって、２進数で表現した位数ｒの桁数が表２のｃｅｉｌ（ｌｏｇ  ｒ）の欄の何れかの値の場合には、ミラー関数のループパラメータを表２のｃ（＝−５ｘ−１）の欄の対応する値とする。これにより、ミラー関数演算部２０によれば、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合に、ミラー関数の演算コストを最小とすることができる。なお、表２の“ｐ  ｍｏｄ  ４”は、ｐを４で除算した余りを表す。
【００４３】
（最終冪乗部３０）
図４は、最終冪乗部３０の構成を示すブロック図である。最終冪乗部３０は、ミラー関数演算部２０による演算結果である有限体のｋ次拡大体の元に対して、Ａ（ｐｋ−１）／ｒを冪指数とする冪乗演算をする。
【００４４】
最終冪乗部３０は、冪指数Ａ（ｐｋ−１）／ｒを、下記の式（２１）に示すように、３つの部分に分けて演算する。なお、Φｋ（ｐ）は、ｐのｋ次円分多項式である。
【数５】
2015022167.tif 000009
【００４５】
具体的には、最終冪乗部３０は、第１冪乗部３１と、第２冪乗部３２と、第３冪乗部３３とを有する。第１冪乗部３１は、（ｐｋ／２−１）を冪指数とした冪乗演算をする。第２冪乗部３２は、｛（ｐｋ／２＋１）／Φｋ（ｐ）｝を冪指数とした冪乗演算をする。第３冪乗部３３は、｛ＡΦｋ（ｐ）／ｒ｝を冪指数とした冪乗演算とする。
【００４６】
第１冪乗部３１、第２冪乗部３２および第３冪乗部３３は、直列に接続される。第１冪乗部３１、第２冪乗部３２および第３冪乗部３３は、どのような順で接続されてもよい。
【００４７】
第１冪乗部３１、第２冪乗部３２および第３冪乗部３３のうち先頭の冪乗部は、ミラー関数演算部２０による演算結果を入力する。また、２番目および最後の冪乗部は、前段の演算結果に対して冪乗演算をする。そして、最後の冪乗部は、最終的な冪乗演算の結果を出力する。
【００４８】
図５は、｛ＡΦｋ（ｐ）／ｒ｝の冪乗演算をする第３冪乗部３３の構成を示すブロック図である。
【００４９】
第３冪乗部３３は、記憶部４１と、基数算出部４２と、ベクトル性加算鎖演算部４３とを含む。記憶部４１は、ミラー関数のループパラメータｃを予め記憶する。
【００５０】
基数算出部４２は、前段から入力したｋ次拡大体の元ｆに対して、所定の式を演算して、複数個の基数ｙ０、ｙ１、…、ｙｊ（ｊは１以上の整数）を出力する。所定の式には、記憶部４１に記憶されたミラー関数のループパラメータｃを冪指数として、入力したｋ次拡大体の元ｆに対して冪乗をする演算を含む。なお、基数算出部４２が演算する式については詳細を後述する。
【００５１】
ベクトル性加算鎖演算部４３は、基数算出部４２から複数の基数ｙ０、ｙ１、…、ｙｊを入力する。ベクトル性加算鎖演算部４３は、入力した複数の基数ｙ０、ｙ１、…、ｙｊのそれぞれに１以上の整数を冪乗した結果を全て乗算する式を、ベクトル性加算鎖を用いて演算する。具体的には、ベクトル性加算鎖演算部４３は、下記の式（２２）をベクトル性加算鎖を用いて演算する。
【数６】
2015022167.tif 000010
【００５２】
Ｂ０、Ｂ１、…、Ｂｉは、１以上の予め定められた整数である。そして、ベクトル性加算鎖演算部４３は、ベクトル性加算鎖の実行結果を、元ｆに対する、｛ＡΦｋ（ｐ）／ｒ｝の冪乗演算の結果として出力する。なお、ベクトル性加算鎖演算部４３が演算する式については詳細を後述する。
【００５３】
（ＢＮ曲線）
つぎに、具体的にＯｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合の基数算出部４２およびベクトル性加算鎖演算部４３が演算する式について説明する。
【００５４】
ＢＮ曲線の埋め込み次数ｋは１２であるので、ｋ次円分多項式Φｋ（ｐ）は、下記の式（２３）となる。
【数７】
2015022167.tif 000011
【００５５】
式（２３）をｒで除算すると、下記の式（２４）となる。
【数８】
2015022167.tif 000012
【００５６】
ＢＮ曲線のｐおよびｒは、式（１２）および式（１３）に示したように、ｘの多項式で表される。式（２４）に対して式（１２）および式（１３）を代入して整理すると、下記の式（２５）に変形される。
【数９】
2015022167.tif 000013
【００５７】
式（２５）のλ０、λ１、λ２、λ３は、下記の式（２６）の通りである。
【数１０】
2015022167.tif 000014
【００５８】
ここで、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、ｃ＝６ｘ＋２である。そこで、式（２６）のλ０、λ１、λ２、λ３を、ミラー関数のループパラメータｃを変数とした式に変換すると、下記の式（２７）となる。
【数１１】
2015022167.tif 000015
【００５９】
冪指数を整数とするために、式（２７）のλ０、λ１、λ２、λ３を６倍する。そして、６倍したλ０、λ１、λ２、λ３を用いた演算式で、拡大体の元ｆを冪乗した式は、下記の式（２８）となる。
【数１２】
2015022167.tif 000016
【００６０】
式（２８）のｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６は、下記の式（２９）に示す通りである。
【数１３】
2015022167.tif 000017
【００６１】
以上のように、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、基数ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６は、式（２９）に示す値となる。すなわち、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、基数算出部４２は、式（２９）を演算して、基数ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６を出力する。
【００６２】
なお、式（２９）には、元ｆに対してミラー関数のループパラメータｃを冪乗する冪乗演算ｆｃが含まれる。
【００６３】
また、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、ベクトル性加算鎖演算部４３は、式（２８）をベクトル性加算鎖を用いて演算する。例えば、ベクトル性加算鎖演算部４３は、図６に示すアルゴリズムを実行することにより、式（２８）を演算することができる。
【００６４】
なお、ベクトル性加算鎖のアルゴリズムは、複数の基数のそれぞれの冪指数の加算鎖に基づき定まる。ベクトル性加算鎖のアルゴリズムの生成方法については、例えば、非特許文献（Roberto  M.  Avanzi,  etc.  ,  “Handbook  of  Elliptic  and  Hyperelliptic  Curve  Cryptography”，Chapman  &  Hall/CRC  Taylor  &  Francis  Group，2006，  PP.157-159）に記載されている。
【００６５】
つぎに、式（２８）および式（２９）を演算した場合のコストを算出する。１２次拡大体の元の平方算のコストをＳｔとする。また、１２次拡大体の元の乗算コストをＭ１２とする。また、この場合、１２次拡大体の元に対するｃの冪乗コストは、ｆｌｏｏｒ（ｌｏｇ  ｃ）×Ｓｔ＋｛ＨＷ（ｃ）−１｝×Ｍ１２と表せる。ＨＷ（ｃ）は、ｃの符号付きハミングウエイトである。なお、逆元の演算コストは０とする。
【００６６】
式（２８）をベクトル性加算鎖で演算した場合、５回の平方算と、９回の乗算とが発生する。また、式（２９）を演算した場合、３回のｃの冪乗と、５回の乗算とが発生する。従って、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合の｛ＡΦｋ（ｐ）／ｒ｝の冪乗の演算コストは、下記の式（３０）となる。
【数１４】
2015022167.tif 000018
【００６７】
式（３０）から、｛ＡΦｋ（ｐ）／ｒ｝の演算コストは、ミラー関数のループパラメータｃの符号付きハミングウエイトが小さいほど、小さくなることがわかる。ミラー関数のループパラメータｃの符号付きハミングウエイトは、ミラー関数演算部２０で最小または最小に近い値に設定されている。従って、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、｛ＡΦｋ（ｐ）／ｒ｝の演算コストは、小さいといえる。
【００６８】
このように、最終冪乗部３０は、ｋ次拡大体の元に対してミラー関数のループパラメータｃを冪乗する演算（ｆｃ）を含んだ式を演算する。従って、最終冪乗部３０は、｛ＡΦｋ（ｐ）／ｒ｝の冪乗を小さいコストで演算することができる。
【００６９】
なお、式（２８）では、冪指数が、通常のペアリング演算で用いる冪指数Φｋ（ｐ）／ｒに対して６倍となっている。この６倍は、第３冪乗部３３の冪指数の“ＡΦｋ（ｐ）／ｒ”におけるＡに該当する。このように、ペアリング演算装置１０は、最終冪乗部３０での冪指数が、通常のペアリング演算と比較してＡ倍（例えば２以上の整数）となる。しかし、冪指数がＡ倍となったペアリング演算結果も、双線形性および非退化性等のペアリングの性質を満たす。従って、ペアリング演算装置１０は、ペアリングベース暗号の処理に用いられることができる。
【００７０】
（Ｆｒｅｅｍａｎ曲線）
つぎに、具体的にＯｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合の基数算出部４２およびベクトル性加算鎖演算部４３が演算する式について説明する。
【００７１】
Ｆｒｅｅｍａｎ曲線の埋め込み次数ｋは１０であるので、ｋ次円分多項式Φｋ（ｐ）は、下記の式（３１）となる。
【数１５】
2015022167.tif 000019
【００７２】
式（３１）をｒで除算すると、下記の式（３２）となる。
【数１６】
2015022167.tif 000020
【００７３】
Ｆｒｅｅｍａｎ曲線のｐおよびｒは、式（１４）および式（１５）に示したように、ｘの多項式で表される。式（３２）に対して式（１４）および式（１５）を代入して整理すると、下記の式（３３）に変形される。
【数１７】
2015022167.tif 000021
【００７４】
式（３３）のλ０、λ１、λ２、λ３は、下記の式（３４）の通りである。
【数１８】
2015022167.tif 000022
【００７５】
ここで、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、ｃ＝−５ｘ−１である。そこで、式（３４）のλ０、λ１、λ２、λ３を、ミラー関数のループパラメータｃを変数とした式に変換すると、下記の式（３５）となる。
【数１９】
2015022167.tif 000023
【００７６】
冪指数を整数とするために、式（３５）のλ０、λ１、λ２、λ３を５倍する。そして、５倍したλ０、λ１、λ２、λ３を用いた演算式で、拡大体の元ｆを冪乗した式は、下記の式（３６）となる。
【数２０】
2015022167.tif 000024
【００７７】
式（３６）のｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６は、下記の式（３７）に示す通りである。
【数２１】
2015022167.tif 000025
【００７８】
以上のように、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、基数ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６は、式（３７）に示す値となる。すなわち、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、基数算出部４２は、式（３７）を演算して、基数ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６を出力する。なお、式（３７）には、元ｆに対するミラー関数のループパラメータｃの冪乗演算が含まれる。
【００７９】
また、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、ベクトル性加算鎖演算部４３は、式（３６）をベクトル性加算鎖を用いて演算する。
【００８０】
つぎに、式（３６）および式（３７）を演算した場合のコストを算出する。１０次拡大体の元の平方算のコストをＳ１０とする。また、１０次拡大体の元の乗算コストをＭ１０とする。また、この場合、１０次拡大体の元に対するｃの冪乗コストは、ｆｌｏｏｒ（ｌｏｇ  ｃ）×Ｓ１０＋｛ＨＷ（ｃ）−１｝×Ｍ１０と表せる。なお、逆元の演算コストは０とする。
【００８１】
式（３６）をベクトル性加算鎖で演算した場合、３回の平方算と、１０回の乗算とが発生する。また、式（３７）を演算した場合、３回のｃの冪乗と、３回の乗算とが発生する。従って、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合の｛ＡΦｋ（ｐ）／ｒ｝の冪乗の演算コストは、下記の式（３８）となる。
【数２２】
2015022167.tif 000026
【００８２】
式（３８）から、｛ＡΦｋ（ｐ）／ｒ｝の演算コストは、ミラー関数のループパラメータｃの符号付きハミングウエイトが小さいほど、小さくなることがわかる。ミラー関数のループパラメータｃの符号付きハミングウエイトは、ミラー関数演算部２０で最小または最小に近い値に設定されている。従って、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合、｛ＡΦｋ（ｐ）／ｒ｝の演算コストは、小さいといえる。このように、最終冪乗部３０は、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＦｒｅｅｍａｎ曲線を用いる場合にも、｛ＡΦｋ（ｐ）／ｒ｝の冪乗を小さいコストで演算することができる。
【００８３】
なお、式（３６）では、冪指数が、通常のペアリング演算で用いる冪指数Φｋ（ｐ）／ｒに対して５倍となっている。この５倍は、第３冪乗部３３の冪指数の“ＡΦｋ（ｐ）／ｒ”におけるＡに該当する。
【００８４】
（変形例１）
式（２７）および式（３５）では、λ０、λ１、λ２、λ３の変数を、ｘから“ｃ”に置き換える変数変換をしていた。これに代えて、λ０、λ１、λ２、λ３の変数を、ｘからｈに置き換える変数変換をしてもよい。
【００８５】
ここで、ｈは、ミラー関数のループパラメータｃを変数とした式ｈ（ｃ）に基づき定まる値であり、例えばｃに対して整数を加算、減算、乗算または除算した値である。
【００８６】
例えば、ｈは、ミラー関数のループパラメータｃを、ミラー関数のループパラメータｃの約数で除算した値である。また、ｈは、ミラー関数のループパラメータｃに対して、２ｌ（ｌは整数）を乗算した値である。また、ｈは、ミラー関数のループパラメータｃに対して、整数を加減算した値である。
【００８７】
ＢＮ曲線の場合に、ｈが、ｃを２で除算した値である例について説明する。この場合、ｈは、下記の式（４１）となる。
【数２３】
2015022167.tif 000027
【００８８】
式（２６）のλ０、λ１、λ２、λ３をｈを変数とした式に変換すると、下記の式（４２）となる。
【数２４】
2015022167.tif 000028
【００８９】
冪指数を整数とするために、式（４２）のλ０、λ１、λ２、λ３を３倍する。そして、３倍したλ０、λ１、λ２、λ３を用いた演算式で、拡大体の元ｆを冪乗した式は、下記の式（４３）となる。
【数２５】
2015022167.tif 000029
【００９０】
式（４３）のｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６、ｙ７は、下記の式（４４）に示す通りである。
【数２６】
2015022167.tif 000030
【００９１】
すなわち、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、基数算出部４２は、ミラー関数のループパラメータｃに基づく値ｈの冪乗演算を含む式（４４）を演算して、基数ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６、ｙ７を出力してもよい。そして、この場合、ベクトル性加算鎖演算部４３は、式（４３）をベクトル性加算鎖を用いて演算する。
【００９２】
式（４３）および式（４４）を演算した場合のコストを算出する。式（４３）をベクトル性加算鎖で演算した場合、５回の平方算と、１０回の乗算とが発生する。また、式（４４）を演算した場合、３回のｈの冪乗と、４回の乗算とが発生する。従って、｛３Φｋ（ｐ）／ｒ｝の冪乗の演算コストは、下記の式（４５）となる。
【数２７】
2015022167.tif 000031
【００９３】
ここで、式（３０）で示したＣｏｓｔ＿１と、式（４５）で示したＣｏｓｔ＿３とを比較する。ｃ＝６ｘ＋２、ｈ＝３ｘ＋１の場合、ｆｌｏｏｒ（ｌｏｇ  ｃ）＝｛ｆｌｏｏｒ（ｌｏｇ  ｈ）｝＋１、および、ＨＷ（ｃ）＝ＨＷ（ｈ）となる。
【００９４】
従って、Ｃｏｓｔ＿１−Ｃｏｓｔ＿３＝３Ｓｔとなる。すなわち、ｈ＝３ｘ＋１の場合の方が、ｈ＝６ｘ＋２の場合よりも、最終冪乗部３０は｛ＡΦｋ（ｐ）／ｒ｝の冪乗を小さいコストで演算することができる。
【００９５】
（変形例２）
つぎに、ＢＮ曲線の場合に、ｈが、ｃを２ｌで除算した値（即ち、ｃに２−ｌを乗算した値）である例について説明する。なお、ｌは、１以上の整数である。この場合、ｈは、下記の式（５１）となる。
【数２８】
2015022167.tif 000032
【００９６】
式（２６）のλ０、λ１、λ２、λ３をｈを変数とした式に変換すると、下記の式（５２）となる。
【数２９】
2015022167.tif 000033
【００９７】
冪指数を整数とするために、式（５２）のλ０、λ１、λ２、λ３を３倍する。そして、３倍したλ０、λ１、λ２、λ３を用いた演算式で、拡大体の元ｆを冪乗した式は、下記の式（５３）となる。
【数３０】
2015022167.tif 000034
【００９８】
式（５３）のｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６、ｙ７、ｙ８、ｙ９は、下記の式（５４）に示す通りである。
【数３１】
2015022167.tif 000035
【００９９】
すなわち、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、基数算出部４２は、ミラー関数のループパラメータｃに基づく値ｈの冪乗演算を含む式（５４）を演算して、基数ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６、ｙ７、ｙ８、ｙ９を出力してもよい。そして、この場合、ベクトル性加算鎖演算部４３は、式（５３）をベクトル性加算鎖を用いて演算する。
【０１００】
ｌ＝１０の場合に、式（５３）および式（５４）を演算した場合のコストを算出する。式（５３）をベクトル性加算鎖で演算した場合、２８回の平方算と、１７回の乗算とが発生する。また、式（５４）を演算した場合、３回のｈの冪乗と、２回の乗算とが発生する。従って、｛３Φｋ（ｐ）／ｒ｝の冪乗の演算コストは、下記の式（５５）となる。
【数３２】
2015022167.tif 000036
【０１０１】
ここで、式（３０）で示したＣｏｓｔ＿１と、式（５５）で示したＣｏｓｔ＿４とを比較する。ｃ＝６ｘ＋２、ｈ＝（６ｘ＋２）／２１０の場合、ｆｌｏｏｒ（ｌｏｇ  ｃ）＝｛ｆｌｏｏｒ（ｌｏｇ  ｈ）｝＋１０、および、ＨＷ（ｃ）＝ＨＷ（ｈ）となる。
【０１０２】
従って、Ｃｏｓｔ＿１−Ｃｏｓｔ＿４＝７Ｓｔ−５Ｍ１２となる。従って、ｈ＝（６ｘ＋２）／２１０の場合の方が、ｈ＝６ｘ＋２の場合よりも、最終冪乗部３０は｛ＡΦｋ（ｐ）／ｒ｝の冪乗を小さいコストで演算することができる場合がある。
【０１０３】
（変形例３）
ＢＮ曲線の場合に、ｈが、ｃから１を減算した値である例について説明する。この場合、ｈは、下記の式（６１）となる。
【数３３】
2015022167.tif 000037
【０１０４】
式（２６）のλ０、λ１、λ２、λ３をｈを変数とした式に変換すると、下記の式（６２）となる。
【数３４】
2015022167.tif 000038
【０１０５】
冪指数を整数とするために、式（６２）のλ０、λ１、λ２、λ３を６倍する。そして、６倍したλ０、λ１、λ２、λ３を用いた演算式で、拡大体の元ｆを冪乗した式は、下記の式（６３）となる。
【数３５】
2015022167.tif 000039
【０１０６】
式（６３）のｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６は、下記の式（６４）に示す通りである。
【数３６】
2015022167.tif 000040
【０１０７】
すなわち、Ｏｐｔｉｍａｌ  ａｔｅペアリングでＢＮ曲線を用いる場合、基数算出部４２は、ミラー関数のループパラメータｃに基づく値ｈの冪乗演算を含む式（６４）を演算して、基数ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５、ｙ６を出力してもよい。そして、この場合、ベクトル性加算鎖演算部４３は、式（６３）をベクトル性加算鎖を用いて演算する。
【０１０８】
式（６３）および式（６４）を演算した場合のコストを算出する。式（６３）をベクトル性加算鎖で演算した場合、２回の平方算と、１１回の乗算とが発生する。また、式（６４）を演算した場合、３回のｈの冪乗と、４回の乗算とが発生する。従って、｛６Φｋ（ｐ）／ｒ｝の冪乗の演算コストは、下記の式（６５）となる。
【数３７】
2015022167.tif 000041
【０１０９】
ここで、式（３０）で示したＣｏｓｔ＿１と、式（６５）で示したＣｏｓｔ＿５とを比較する。ｃ＝６ｘ＋２、ｈ＝６ｘ＋１の場合、ｆｌｏｏｒ（ｌｏｇ  ｃ）＝ｆｌｏｏｒ（ｌｏｇ  ｈ）、および、ＨＷ（ｃ）＝ＨＷ（ｈ）−１となる。
【０１１０】
従って、Ｃｏｓｔ＿１−Ｃｏｓｔ＿５＝３Ｓｔ−４Ｍ１２となる。すなわち、ｈ＝６ｘ＋１の場合は、ｈ＝６ｘ＋２の場合よりも、最終冪乗部３０は、｛ＡΦｋ（ｐ）／ｒ｝の冪乗にかかるコストが大きいものの、従来手法と比べると小さいコストで演算することができる。
【０１１１】
以上のように、本実施形態に係るペアリング演算装置１０によれば、最終冪乗部３０が、ｋ次拡大体の元に対してミラー関数のループパラメータｃに基づき定まる値ｈを冪乗する演算（ｆｈ）を含んだ式を演算する。これにより、ペアリング演算装置１０によれば、ミラー関数のループパラメータｃの符号付きハミングウエイトを小さくすることにより、ミラー関数演算のコストを小さくするとともに、最終冪乗の演算コストを小さくすることができる。
【０１１２】
（ハードウェア構成）
図７は、実施形態に係るペアリング演算装置１０のハードウェア構成の一例を示す図である。実施形態に係るペアリング演算装置１０は、ＣＰＵ１０１などの制御装置と、ＲＯＭ（Read  Only  Memory）１０２やＲＡＭ（Random  Access  Memory）１０３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ１０４と、各部を接続するバスを備えている。
【０１１３】
実施形態に係るペアリング演算装置１０で実行されるプログラムは、ＲＯＭ１０２等に予め組み込まれて提供される。
【０１１４】
実施形態に係るペアリング演算装置１０で実行されるプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact  Disk  Read  Only  Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact  Disk  Recordable）、ＤＶＤ（Digital  Versatile  Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供されるように構成してもよい。
【０１１５】
さらに、実施形態に係るペアリング演算装置１０で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、実施形態に係るペアリング演算装置１０で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１１６】
実施形態に係るペアリング演算装置１０で実行されるプログラムは、コンピュータを上述したペアリング演算装置１０の各部（ミラー関数演算部２０および最終冪乗部３０）として機能させうる。なお、これらの各部は、一部または全部がハードウェアにより構成されていてもよい。このコンピュータは、ＣＰＵ１０１がコンピュータ読取可能な記憶媒体からプログラムを主記憶装置上に読み出して実行することができる。
【０１１７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１１８】
１０  ペアリング演算装置
２０  ミラー関数演算部
３０  最終冪乗部
３１  第１冪乗部
３２  第２冪乗部
３３  第３冪乗部
４１  記憶部
４２  基数算出部
４３  ベクトル性加算鎖演算部
【図１】
2015022167.tif 000046
【図２】
2015022167.tif 000047
【図３】
2015022167.tif 000048
【図４】
2015022167.tif 000049
【図５】
2015022167.tif 000050
【図６】
2015022167.tif 000051
【図７】
2015022167.tif 000052