(57)【特許請求の範囲】
【請求項１】
数１に示す次数ｄの円分多項式Φｋ（ｘ）と多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）とを用いて表される多項式ｒ（ｘ）＝Φｋ（Ｔ（ｘ））／ｈ２（ｘ）と多項式ｐ（ｘ）＝ｈ１（ｘ）ｒ（ｘ）＋Ｔ（ｘ）と多項式ｔ（ｘ）＝Ｔ（ｘ）＋１と、埋め込み次数ｋとで表される楕円曲線におけるペアリング演算の最終べき計算部分について、多項式Φｋ（ｐ（ｘ））により指数部分をイージーパートとハードパートとに分解する分解部と、
前記分解部によって分解されて得られた前記ハードパートを、ｉ＝０，．．．，ｄ−１の各整数ｉについての多項式ｐ（ｘ）ｉ乗と、λｄ−１（ｘ）＝ｃｄであるλｄ−１（ｘ）乗と、ｉ＝１，．．．，ｄ−２の各整数ｉについてのλｉ＝Ｔ（ｘ）λｉ＋１（ｘ）＋ｃｉ＋１であるλｉ乗と、ｈ１（ｘ）乗と、ｈ２（ｘ）乗と、乗算及び逆元算の少なくともいずれかとを用いて計算するべき計算部と
を備える最終べき計算装置。
【数１】
0006929491.tif 000024
【請求項２】
前記べき計算部は、ｉ＝１，．．．，ｄ−２の各整数ｉについてのλｉ乗を計算する場合に、計算済のλｉ＋１乗の結果を用いる
請求項１に記載の最終べき計算装置。
【請求項３】
前記べき計算部は、数２を計算することにより、前記ハードパートを計算する
請求項１又は２に記載の最終べき計算装置。
【数２】
0006929491.tif 000025
【請求項４】
前記多項式ｔ（ｘ）は、１次線形である
請求項１から３までのいずれか１項に記載の最終べき計算装置。
【請求項５】
前記多項式ｔ（ｘ）＝ｘ＋１である
請求項４に記載の最終べき計算装置。
【請求項６】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝１／３Φ９（ｘ）＝１／３（ｘ６＋ｘ３＋１）であり、前記多項式ｐ（ｘ）＝（ｘ−１）２ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項７】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝Φ１２（ｘ）＝ｘ４−ｘ２＋１であり、前記多項式ｐ（ｘ）＝１／３（ｘ−１）２ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項８】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝Φ１２（ｘ）＝ｘ４−ｘ２＋１であり、前記多項式ｐ（ｘ）＝１／４（ｘ−１）２（ｘ２＋１）ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項９】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝Φ１５（ｘ）＝ｘ８−ｘ７＋ｘ５−ｘ４＋ｘ３−ｘ＋１であり、前記多項式ｐ（ｘ）＝１／３（ｘ−１）２（ｘ２＋ｘ＋１）ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項１０】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝Φ２４（ｘ）＝ｘ８−ｘ４＋１であり、前記多項式ｐ（ｘ）＝１／３（ｘ−１）２ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項１１】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝１／３Φ２７（ｘ）＝１／３（ｘ１８＋ｘ９＋１）であり、前記多項式ｐ（ｘ）＝（ｘ−１）２ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項１２】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝Φ２８（ｘ）＝ｘ１２−ｘ１０＋ｘ８−ｘ６＋ｘ４−ｘ２＋１であり、前記多項式ｐ（ｘ）＝１／３（ｘ−１）２（ｘ２＋１）ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項１３】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝Φ２８（ｘ）＝ｘ１２−ｘ１０＋ｘ８−ｘ６＋ｘ４−ｘ２＋１であり、前記多項式ｐ（ｘ）＝１／４（ｘ−１）２（ｘ２＋１）ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項１４】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝Φ４２（ｘ）＝ｘ１２＋ｘ１１−ｘ９−ｘ８＋ｘ６−ｘ４−ｘ３＋ｘ＋１であり、前記多項式ｐ（ｘ）＝１／３（ｘ−１）２（ｘ２−ｘ＋１）ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項１５】
前記多項式ｔ（ｘ）＝ｘ＋１であり、前記多項式ｒ（ｘ）＝Φ４８（ｘ）＝ｘ１６−ｘ８＋１であり、前記多項式ｐ（ｘ）＝１／３（ｘ−１）２ｒ（ｘ）＋ｘである
請求項１から５までのいずれか１項に記載の最終べき計算装置。
【請求項１６】
前記イージーパートは、ｐ（ｘ）のべき乗によって表される部分であり、前記ハードパートは、ｘのべき乗によって表される部分である
請求項１から１５までのいずれか１項に記載の最終べき計算装置。
【請求項１７】
請求項１から１６までのいずれか１項に記載の最終べき計算装置と、
前記ペアリング演算のＭｉｌｌｅｒ関数を計算するＭｉｌｌｅｒ関数計算部と
を備えるペアリング演算装置。
【請求項１８】
前記べき計算部は、前記Ｍｉｌｌｅｒ関数計算部によって計算された結果である関数値に対して、前記イージーパートのべき乗計算と、前記ハードパートのべき乗計算とを行い、前記ペアリング演算の結果を計算する
請求項１７に記載のペアリング演算装置。
【請求項１９】
請求項１７又は１８に記載のペアリング演算装置によって計算された前記ペアリング演算の結果を用いて、暗号処理を行う暗号処理装置。
【請求項２０】
最終べき計算装置の分解部が、数３に示す次数ｄの円分多項式Φｋ（ｘ）と多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）とを用いて表される多項式ｒ（ｘ）＝Φｋ（Ｔ（ｘ））／ｈ２（ｘ）と多項式ｐ（ｘ）＝ｈ１（ｘ）ｒ（ｘ）＋Ｔ（ｘ）と多項式ｔ（ｘ）＝Ｔ（ｘ）＋１と、埋め込み次数ｋとで表される楕円曲線におけるペアリング演算の最終べき計算部分について、多項式Φｋ（ｐ（ｘ））により指数部分をイージーパートとハードパートとに分解し、
前記最終べき計算装置のべき計算部が、前記ハードパートを、ｉ＝０，．．．，ｄ−１の各整数ｉについての多項式ｐ（ｘ）ｉ乗と、λｄ−１（ｘ）＝ｃｄであるλｄ−１（ｘ）乗と、ｉ＝１，．．．，ｄ−２の各整数ｉについてのλｉ＝Ｔ（ｘ）λｉ＋１（ｘ）＋ｃｉ＋１であるλｉ乗と、ｈ１（ｘ）乗と、ｈ２（ｘ）乗と、乗算及び逆元算の少なくともいずれかとを用いて計算する最終べき計算方法。
【数３】
0006929491.tif 000026
【請求項２１】
数４に示す次数ｄの円分多項式Φｋ（ｘ）と多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）とを用いて表される多項式ｒ（ｘ）＝Φｋ（Ｔ（ｘ））／ｈ２（ｘ）と多項式ｐ（ｘ）＝ｈ１（ｘ）ｒ（ｘ）＋Ｔ（ｘ）と多項式ｔ（ｘ）＝Ｔ（ｘ）＋１と、埋め込み次数ｋとで表される楕円曲線におけるペアリング演算の最終べき計算部分について、多項式Φｋ（ｐ（ｘ））により指数部分をイージーパートとハードパートとに分解する分解処理と、
前記分解処理によって分解されて得られた前記ハードパートを、ｉ＝０，．．．，ｄ−１の各整数ｉについての多項式ｐ（ｘ）ｉ乗と、λｄ−１（ｘ）＝ｃｄであるλｄ−１（ｘ）乗と、ｉ＝１，．．．，ｄ−２の各整数ｉについてのλｉ＝Ｔ（ｘ）λｉ＋１（ｘ）＋ｃｉ＋１であるλｉ乗と、ｈ１（ｘ）乗と、ｈ２（ｘ）乗と、乗算及び逆元算の少なくともいずれかとを用いて計算するべき計算処理と
を行う最終べき計算装置としてコンピュータを機能させる最終べき計算プログラム。
【数４】
0006929491.tif 000027
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、ペアリング演算における最終べきの計算技術に関する。
【背景技術】
【０００２】
ペアリング演算は、関数型暗号及び秘匿検索といった暗号方式の内部で処理される楕円曲線を用いた演算である。ペアリング演算の効率的な計算に適した楕円曲線をペアリングフレンドリ曲線という。これまで１２８ビット安全性相当のペアリングフレンドリ曲線としてＢＮ（Ｂａｒｒｅｔ−Ｎａｅｈｒｉｇ）曲線が知られていた。しかし２０１６年頃から、安全性の見直しが行われ、ＢＬＳ（Ｂａｒｒｅｔｏ−Ｌｙｎｎ−Ｓｃｏｔｔ）曲線及びＫＳＳ（Ｋａｃｈｉｓａ−Ｓｃｈａｅｆｅｒ−Ｓｃｏｔｔ）曲線など、様々なペアリングフレンドリ曲線を用いたペアリング演算への関心が高まってきている。【０００３】
ペアリング演算は、大きく分けてＭｉｌｌｅｒ関数の計算と最終べきの計算とに分けられる。Ｍｉｌｌｅｒ関数の計算と最終べきの計算とのどちらも複雑な計算過程を要し、関数型暗号及び秘匿検索といった暗号方式全体の計算量に大きな影響を与えている。【０００４】
非特許文献１，２には、数多くあるペアリングフレンドリ曲線の中でもペアリング演算全体の効率がよいとされているＢＬＳ曲線について記載されている。非特許文献１，２には、埋め込み次数ｋとしてｋ＝２４，２７，４２，４８のＢＬＳ曲線におけるペアリング演算について記載されている。また、特許文献１及び非特許文献２には、ＫＳＳ曲線について記載されている。いずれの文献でも、Ｍｉｌｌｅｒ関数の計算量よりも最終べきの計算量が大きいという結果が示されている。【０００５】
ペアリングフレンドリ曲線は、多項式ｒ（ｘ）と、多項式ｐ（ｘ）と、多項式ｔ（ｘ）と、埋め込み次数ｋと、整数Ｄと、整数ｕとで決まる楕円曲線である。多項式ｒ（ｘ）と、多項式ｐ（ｘ）と、多項式ｔ（ｘ）とは、埋め込み次数ｋに応じて異なる形をしている。
埋め込み次数ｋのペアリングフレンドリ曲線Ｅはｐ＝ｐ（ｘ）個の要素からなる有限体Ｆｐ上で定義される楕円曲線である。ｒ＝ｒ（ｘ）は、楕円曲線Ｅの部分群Ｅ（Ｆｐ）の位数を割る最大素数である。ｔ＝ｔ（ｘ）は、楕円曲線Ｅのトレースである。【０００６】
楕円曲線Ｅ上のペアリング演算は、楕円曲線Ｅ上のある２点Ｐ，Ｑを入力とし、Ｍｉｌｌｅｒ関数と呼ばれる有理関数ｆを計算した後、（ｐ（ｘ）ｋ−１）／ｒ（ｘ）乗して計算される。つまり、楕円曲線Ｅ上のペアリング演算は、数１１により計算される。
【数１１】
0006929491.tif 000002
【０００７】
非特許文献３には、最終べきの計算を効率的に行うため、多項式Φｋ（ｐ（ｘ））を用いて指数部分（ｐ（ｘ）ｋ−１）／ｒ（ｘ）をイージーパートとハードパートとに分解して計算することが記載されている。
イージーパートのべき乗計算は、高速なｐ（ｘ）ｉ乗を用いて効率的に計算可能である。ハードパートのべき乗計算では、数１２に示すようにハードパートの指数部分がｐ（ｘ）ｉの線形和に変換され、各係数λｉ（ｘ）によるべき乗が計算される。
【数１２】
0006929491.tif 000003
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１８−２０５５１１号公報
【非特許文献】
【０００９】
【非特許文献１】Ｘ．Ｚｈａｎｇ，  Ｄ．Ｌｉｎ，  “Ａｎａｌｙｓｉｓ  ｏｆ  Ｏｐｔｉｍｕｍ  Ｐａｉｒｉｎｇ  Ｐｒｏｄｕｃｔｓ  ａｔ  Ｈｉｇｈ  Ｓｅｃｕｒｉｔｙ  Ｌｅｖｅｌｓ”，  ＩＮＤＯＣＲＹＰＴ  ２０１２，ｐ．４１２〜４３０
【非特許文献２】Ｙ．Ｋｉｙｏｍｕｒａ，  Ａ．Ｉｎｏｕｅ，Ｙ．Ｋａｗａｈａｒａ，Ｍ．Ｙａｓｕｄａ，Ｔ．Ｔａｋａｇｉ，Ｔ．Ｋｏｂａｙａｓｈｉ，  “Ｓｅｃｕｒｅ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｐａｉｒｉｎｇ  ａｔ  ２５６−Ｂｉｔ  Ｓｅｃｕｒｉｔｙ  Ｌｅｂｅｌ”，ＡＣＮＳ２０１７，ｐ．５９〜７９
【非特許文献３】Ｍ．Ｓｃｏｔｔ，Ｎ．Ｂｅｎｇｅｒ，Ｍ．Ｃｈａｒｌｅｍａｇｎｅ，“Ｏｎ  ｔｈｅ  Ｆｉｎａｌ  Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  ｆｏｒ  Ｃａｌｃｕｌａｔｉｎｇ  Ｐａｉｒｉｎｇｓ  ｏｎ  Ｏｒｄｉｎａｒｙ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ”，Ｐａｉｒｉｎｇ  ２００９，ｐ．７８〜８８
【発明の概要】
【発明が解決しようとする課題】
【００１０】
最終べきを計算するために必要なハードパートの各λｉ（ｘ）は、楕円曲線の多項式パラメータに大きく依存する。そのため、ハードパートを効率的に計算する汎用的な方法がない。楕円曲線によっては、ハードパートの効率的な計算方法が未知である。また、ハードパートの効率的な計算方法が既知の場合であっても、楕円曲線毎にハードパートを計算する手段を事前に備えておく必要がある。
本開示は、ペアリング演算における最終べきを効率的に計算可能にすることを目的とする。
【課題を解決するための手段】
【００１１】
本開示に係る最終べき計算装置は、
数１に示す次数ｄの円分多項式Φｋ（ｘ）と多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）とを用いて表される多項式ｒ（ｘ）＝Φｋ（Ｔ（ｘ））／ｈ２（ｘ）と多項式ｐ（ｘ）＝ｈ１（ｘ）ｒ（ｘ）＋Ｔ（ｘ）と多項式ｔ（ｘ）＝Ｔ（ｘ）＋１と、埋め込み次数ｋとで表される楕円曲線におけるペアリング演算の最終べき計算部分について、多項式Φｋ（ｐ（ｘ））により指数部分をイージーパートとハードパートとに分解する分解部と、
前記分解部によって分解されて得られた前記ハードパートを、ｉ＝０，．．．，ｄ−１の各整数ｉについての多項式ｐ（ｘ）ｉ乗と、λｄ−１（ｘ）＝ｃｄであるλｄ−１（ｘ）乗と、ｉ＝１，．．．，ｄ−２の各整数ｉについてのλｉ＝Ｔ（ｘ）λｉ＋１（ｘ）＋ｃｉ＋１であるλｉ乗と、ｈ１（ｘ）乗と、ｈ２（ｘ）乗と、乗算及び逆元算の少なくともいずれかとを用いて計算するべき計算部と
を備える。
【数１】
0006929491.tif 000004
【発明の効果】
【００１２】
本開示では、多くの楕円曲線に対応する効率的な最終べきの計算が可能になる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態１に係る最終べき計算装置１０の構成図。
【図２】実施の形態１に係る指数（ｐ（ｘ）ｋ−１）／ｒ（ｘ）をイージーパートとハードパートとに分解する処理の説明図。
【図３】実施の形態１に係る最終べき計算装置１０の全体的な動作を示すフローチャート。
【図４】実施の形態１に係るべき簡単化処理のフローチャート。
【図５】実施の形態１に係るべき計算処理のフローチャート。
【図６】変形例１に係る最終べき計算装置１０の構成図。
【図７】変形例３に係るペアリング演算装置３０の構成図。
【図８】実施の形態２に係る暗号処理装置４０の構成図。
【図９】実施の形態２に係る暗号処理装置４０の動作を示すフローチャート。
【発明を実施するための形態】
【００１４】
実施の形態１．
＊＊＊表記の説明＊＊＊
本文及び図面では、“＾”を用いてべき乗を表す場合がある。具体例としては、ａ＾ｂは、ａｂを表す。
【００１５】
＊＊＊構成の説明＊＊＊
図１を参照して、実施の形態１に係る最終べき計算装置１０の構成を説明する。
最終べき計算装置１０は、コンピュータである。
最終べき計算装置１０は、プロセッサ１１と、メモリ１２と、ストレージ１３と、通信インタフェース１４とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１６】
プロセッサ１１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ１１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００１７】
メモリ１２は、データを一時的に記憶する記憶装置である。メモリ１２は、具体例としては、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００１８】
ストレージ１３は、データを保管する記憶装置である。ストレージ１３は、具体例としては、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、ストレージ１３は、ＳＤ（登録商標，Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ，登録商標）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）といった可搬記録媒体であってもよい。
【００１９】
通信インタフェース１４は、外部の装置と通信するためのインタフェースである。通信インタフェース１４は、具体例としては、Ｅｔｈｅｒｎｅｔ（登録商標）、ＵＳＢあｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＨＤＭＩ（登録商標，Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）のポートである。
【００２０】
最終べき計算装置１０は、機能構成要素として、べき簡単化部２１と、べき計算部２２とを備える。べき簡単化部２１は、分解部２１１と、生成部２１２とを備える。最終べき計算装置１０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ１３には、最終べき計算装置１０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ１１によりメモリ１２に読み込まれ、プロセッサ１１によって実行される。これにより、最終べき計算装置１０の各機能構成要素の機能が実現される。
【００２１】
図１では、プロセッサ１１は、１つだけ示されていた。しかし、プロセッサ１１は、複数であってもよく、複数のプロセッサ１１が、各機能を実現するプログラムを連携して実行してもよい。
【００２２】
＊＊＊動作の説明＊＊＊
図２から図５を参照して、実施の形態１に係る最終べき計算装置１０の動作を説明する。
実施の形態１に係る最終べき計算装置１０の動作手順は、実施の形態１に係る最終べき計算方法に相当する。また、実施の形態１に係る最終べき計算装置１０の動作を実現するプログラムは、実施の形態１に係る最終べき計算プログラムに相当する。
【００２３】
実施の形態１では、文献“［ＦＳＴ１０］  Ｄ．Ｆｒｅｅｍａｎ，  Ｍ．Ｓｃｏｔｔ  ａｎｄ  Ｅ．Ｔｅｓｋｅ，  “Ａ  Ｔａｘｏｎｏｍｙ  ｏｆ  Ｐａｉｒｉｎｇ−Ｆｒｉｅｎｄｌｙ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ”，  Ｊ．Ｃｒｙｐｔｏｌ．  （２０１０）  ２３：２２４−２８０．”で定義された楕円曲線族によってパラメータ付けされる曲線を用いる。
上記文献で定義された楕円曲線族によってパラメータ付けされる曲線は、多項式ｒ（ｘ）と、多項式ｐ（ｘ）と、多項式ｔ（ｘ）と、埋め込み次数ｋと、変数ｘに代入される整数ｕとで決まる楕円曲線である。この楕円曲線Ｅは、素数ｐ＝ｐ（ｘ）個の要素からなる有限体Ｆｐ上で定義される楕円曲線である。ｒ＝ｒ（ｘ）は、楕円曲線Ｅの部分群Ｅ（Ｆｐ）の位数を割る最大素数である。また、ｔ＝ｔ（ｘ）は、楕円曲線Ｅのトレースである。実施の形態１では、楕円曲線Ｅのトレースである多項式ｔ（ｘ）は、１次線形である。具体例としては、実施の形態１では、楕円曲線Ｅのトレースである多項式ｔ（ｘ）＝ｘ＋１である。
【００２４】
楕円曲線Ｅ上のペアリング演算は、楕円曲線Ｅ上のある２点Ｐ，Ｑを入力とし、Ｍｉｌｌｅｒ関数と呼ばれる有理関数をＰで評価したｆを計算した後、ｆを（ｐ（ｘ）ｋ−１）／ｒ（ｘ）乗して計算される。前半のｆの計算をＭｉｌｌｅｒ  ｌｏｏｐの計算、後半のべき乗演算を最終べきの計算という。
【００２５】
最終べきの計算では、図２に示すように、多項式Φｋ（ｐ（ｘ））を用いて指数（ｐ（ｘ）ｋ−１）／ｒ（ｘ）がイージーパートとハードパートとに分解される。イージーパートのべき乗計算は、高速なｐ（ｘ）ｉ乗を用いて効率的に計算可能である。一方、ハードパートのべき乗計算は、ｘ乗（ｕ乗）を複数回実行する必要があり、計算量が多い。このため、ハードパートの効率的な計算方法が最終べきの効率化に必要となる。
【００２６】
楕円曲線族によってパラメータ付けされる曲線のパラメータである多項式ｐ（ｘ）と多項式ｒ（ｘ）と多項式ｔ（ｘ）とは、数１３に示すように、ある多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）とを用いて表記できる。
【数１３】
0006929491.tif 000005
このとき、数１４に示すように、ハードパートはＴ（ｘ）乗と、ｈ１（ｘ）乗と、ｈ２（ｘ）乗と、乗算及び逆元算の少なくともいずれかとを用いて計算できる。
【数１４】
0006929491.tif 000006
ここで、実用的な楕円曲線の埋め込み次数ｋは小さいため、円分多項式Φｋ（ｘ）の各係数ｃｉは−１，０，１の何れかである。
【００２７】
図３を参照して、実施の形態１に係る最終べき計算装置１０の全体的な動作を説明する。
（ステップＳ１１：べき簡単化処理）
べき簡単化部２１の分解部２１１は、最終べき計算部分における指数部分である（ｐ（ｘ）ｋ−１）／ｒ（ｘ）について、イージーパートとハードパートとに分解する。イージーパートは、ｐ（ｘ）のべき乗によって表される部分である。ハードパートは、ｐ（ｘ）及びｘのべき乗（ｕのべき乗）によって表される部分である。
べき簡単化部２１の生成部２１２は、ハードパートを計算するために必要な多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）と整数ａとを、多項式ｐ（ｘ）と多項式ｒ（ｘ）と多項式ｔ（ｘ）と埋め込み次数ｋとから計算する。
ここで、整数ａは、正の整数であって、ａｈ１（ｘ）及びａｈ２（ｘ）の全ての係数が整数となるような、最小かつ非零の整数である。多項式ｈ１（ｘ）と多項式ｈ２（ｘ）との少なくともいずれかの係数に分数が現れることがあるため、ここでは、後述する処理において、整数ａを乗じて多項式ｈ１（ｘ）及び多項式ｈ２（ｘ）から係数の分母を削除する。
【００２８】
（ステップＳ１２：べき計算処理）
べき計算部２２は、Ｍｉｌｌｅｒ  ｌｏｏｐで計算された有理関数ｆに対して、ステップＳ１１で得られたイージーパートのべき乗計算を行い、さらにステップＳ１１で得られた多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）と整数ａとを用いてハードパートのべき乗計算を行う。これにより、数１５に示す最終べきが計算される。
【数１５】
0006929491.tif 000007
ペアリング演算を整数ａ乗した結果が計算されるのは、後述する処理において、多項式ｈ１（ｘ）及び多項式ｈ２（ｘ）に整数ａを乗じているためである。
【００２９】
図４を参照して、実施の形態１に係るべき簡単化処理を説明する。
ステップＳ２１では、べき簡単化部２１は、楕円曲線Ｅについての埋め込み次数ｋと多項式ｒ（ｘ）と多項式ｐ（ｘ）と多項式ｔ（ｘ）とを取得する。
ステップＳ２２では、分解部２１１は、（ｐ（ｘ）ｋ−１）／ｒ（ｘ）の因数Ａ１（ｘ）を計算する。因数Ａ１（ｘ）は、図２に示すイージーパートの全体である。分解部２１１は、因数Ａ１（ｘ）をメモリ１２に書き込む。
【００３０】
ステップＳ２３からステップＳ２６では、生成部２１２は、ハードパートのべき乗算に必要な多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）と整数ａとを、数１３の条件を用いて生成する。
ステップＳ２３では、生成部２１２は、Ｔ（ｘ）＝ｔ（ｘ）−１として、多項式Ｔ（ｘ）を生成してメモリ１２に書き込む。
ステップＳ２４では、生成部２１２は、ｈ１（ｘ）＝（ｐ（ｘ）−Ｔ（ｘ））／ｒ（ｘ）として、多項式ｈ１（ｘ）を生成してメモリ１２に書き込む。
ステップＳ２５では、生成部２１２は、ｈ２（ｘ）＝ｒ（ｘ）／Φｋ（Ｔ（ｘ））として、多項式ｈ２（ｘ）を生成してメモリ１２に書き込む。
ステップＳ２６では、生成部２１２は、整数ａを計算する。整数ａは、正の整数であって、ａｈ１（ｘ）及びａｈ２（ｘ）の係数が全て整数となるような最小かつ非零の整数である。第２生成部２２２は、生成した整数ａをメモリ１２に書き込む。
【００３１】
図５を参照して、実施の形態１に係るべき計算処理を説明する。
ステップＳ３１では、べき計算部２２は、整数ｕと、Ｍｉｌｌｅｒ  ｌｏｏｐで計算された値ｆと、べき簡単化処理で生成された因数Ａ１（ｘ）と多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）と整数ａとをメモリ１２から読み出す。なお、以下の説明では、多項式の変数ｘを用いた表記とするが、実際には変数ｘに整数ｕが代入されて計算が行われる。
【００３２】
ステップＳ３２では、べき計算部２２は、値ｆを底とし、因数Ａ１（ｘ）をべき指数とするべき乗算を計算して、値Ａ＝ｆ＾｛Ａ１（ｘ）｝を生成する。つまり、べき計算部２２は、数１６により値Ａを計算する。
【数１６】
0006929491.tif 000008
【００３３】
ステップＳ３３では、べき計算部２２は、値Ａを底とし、数１４のｐ（ｘ）ｉの線形和をべき指数とするべき乗算を計算して、値Ｃを生成する。つまり、べき計算部２２は、数１７により値Ｃを計算する。
【数１７】
0006929491.tif 000009
【００３４】
ステップＳ３４では、べき計算部２２は、値Ｃを底とし、ａｈ１（ｘ）をべき指数とするべき乗算を計算して、値Ｄを生成する。つまり、べき計算部２２は、数１８により値Ｄを計算する。
【数１８】
0006929491.tif 000010
【００３５】
ステップＳ３５では、べき計算部２２は、値Ａを底とし、ａｈ２（ｘ）をべき指数とするべき乗算を計算して、値Ｅを生成する。つまり、べき計算部２２は、数１９により値Ｅを計算する。
【数１９】
0006929491.tif 000011
【００３６】
ステップＳ３６では、べき計算部２２は、値Ｄと値Ｅとの積を計算して値Ｆを生成する。値Ｆは、数１５に示すペアリング演算の結果である。つまり、ステップＳ３３からステップＳ３６でべき計算部２２は、数１４に従い、Ｔ（ｘ）乗と、ｈ１（ｘ）乗と、ｈ２（ｘ）乗と、乗算及び逆元算の少なくともいずれかとを用いて、ハードパートのべき乗算を計算する。
【００３７】
ステップＳ３３における値Ｃの計算処理を説明する。
ステップＳ３３１では、べき計算部２２は、インデックスｉをｉ＝ｄ−１として初期化する。
ステップＳ３３２では、べき計算部２２は、値Ｃ及び値Ｂを１に初期化する。
ステップＳ３３３では、べき計算部２２は、値Ｂを底とし、Ｔ（ｘ）をべき指数とするべき乗算を計算する。また、べき計算部２２は、値Ａを底とし、ｃｉ＋１をべき指数とするべき乗算を計算する。そして、べき計算部２２は、計算された２つの値の積を計算して、値Ｂを更新する。つまり、べき計算部２２は、数２０により得られた値を、値Ｂに上書きする。
【数２０】
0006929491.tif 000012
ここで、実用的な楕円曲線の埋め込み次数ｋは小さいため、円分多項式Φｋ（ｘ）の各係数ｃｉは−１，０，１の何れかである。そのため、ステップＳ３３３における底Ａのべき乗算は実際には必要なく、値Ａの乗算又は逆元Ａ−１の乗算で十分である。逆元Ａ−１はステップＳ３３３で計算してもよいし、事前に計算して使いまわすようにしてもよい。
【００３８】
ステップＳ３３４では、べき計算部２２は、値Ｂを底とし、ｐ（ｘ）ｉをべき指数とするべき乗算を計算し、さらに値Ｃとの積を計算して値Ｃを更新する。つまり、べき計算部２２は、数２１により得られた値を、値Ｃに上書きする。
【数２１】
0006929491.tif 000013
ステップＳ３３５では、べき計算部２２は、インデックスｉを１減じる。
ステップＳ３３６では、べき計算部２２は、インデックスｉが０以上であるか否かを判定する。べき計算部２２は、インデックスｉが０以上である場合には、処理をステップＳ３３３に戻す。一方、べき計算部２２は、インデックスｉが０未満である場合には、処理をステップＳ３４に進める。つまり、べき計算部２２は、インデックスｉ＝ｄ−１，ｄ−２，．．．，１，０に対して順にステップＳ３３３及びステップＳ３３４の処理を実行し、値Ｃ及び値Ｂを更新する。
【００３９】
ステップＳ３３によって計算される値Ｃは、数１７に示すべき乗算の結果である。
【００４０】
次に、具体的な曲線の例を説明する。
＜例１：ＢＬＳ−９＞
曲線がＢＬＳ−９の場合について説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝１／３Φ９（ｘ）＝１／３（ｘ６＋ｘ３＋１）であり、多項式ｐ（ｘ）＝（ｘ−１）２ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝（ｘ−１）２であり、多項式ｈ２（ｘ）＝３である。そのため、指数部分は数２２のように分解される。
【数２２】
0006929491.tif 000014
ここで、λ５（ｘ）＝１、λ４（ｘ）＝ｘλ５（ｘ）、λ３（ｘ）＝ｘλ４（ｘ）、λ２（ｘ）＝ｘλ３（ｘ）＋１、λ１（ｘ）＝ｘλ２（ｘ）、λ０（ｘ）＝ｘλ１（ｘ）である。
【００４１】
＜例２：ＢＬＳ−１２＞
曲線がＢＬＳ−１２の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝Φ１２（ｘ）＝ｘ４−ｘ２＋１であり、多項式ｐ（ｘ）＝１／３（ｘ−１）２ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝１／３（ｘ−１）２であり、多項式ｈ２（ｘ）＝１である。そのため、指数部分は数２３のように分解される。
【数２３】
0006929491.tif 000015
ここで、λ３（ｘ）＝１、λ２（ｘ）＝ｘλ３（ｘ）、λ１（ｘ）＝ｘλ２（ｘ）−１、λ０（ｘ）＝ｘλ１（ｘ）である。
【００４２】
＜例３：ｋ＝１２＞
曲線の埋め込み次数ｋ＝１２（ＢＬＳ曲線でない）の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝Φ１２（ｘ）＝ｘ４−ｘ２＋１であり、多項式ｐ（ｘ）＝１／４（ｘ−１）２（ｘ２＋１）ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝１／４（ｘ−１）２（ｘ２＋１）であり、多項式ｈ２（ｘ）＝１である。そのため、指数部分は数２４のように分解される。
【数２４】
0006929491.tif 000016
ここで、λ３（ｘ）＝１、λ２（ｘ）＝ｘλ３（ｘ）、λ１（ｘ）＝ｘλ２（ｘ）−１、λ０（ｘ）＝ｘλ１（ｘ）である。
【００４３】
＜例４：ＢＬＳ−１５＞
曲線がＢＬＳ−１５の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝Φ１５（ｘ）＝ｘ８−ｘ７＋ｘ５−ｘ４＋ｘ３−ｘ＋１であり、多項式ｐ（ｘ）＝１／３（ｘ−１）２（ｘ２＋ｘ＋１）ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝１／３（ｘ−１）２（ｘ２＋ｘ＋１）であり、多項式ｈ２（ｘ）＝１である。そのため、指数部分は数２５のように分解される。
【数２５】
0006929491.tif 000017
ここで、λ７（ｘ）＝１、λ６（ｘ）＝ｘλ７（ｘ）−１、λ５（ｘ）＝ｘλ６（ｘ）、λ４（ｘ）＝ｘλ５（ｘ）＋１、λ３（ｘ）＝ｘλ４（ｘ）−１、λ２（ｘ）＝ｘλ３（ｘ）＋１、λ１（ｘ）＝ｘλ２（ｘ）、λ０（ｘ）＝ｘλ１（ｘ）−１である。
【００４４】
＜例５：ＢＬＳ−２４＞
曲線がＢＬＳ−２４の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝Φ２４（ｘ）＝ｘ８−ｘ４＋１であり、多項式ｐ（ｘ）＝１／３（ｘ−１）２ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝１／３（ｘ−１）２であり、多項式ｈ２（ｘ）＝１である。そのため、指数部分は数２６のように分解される。
【数２６】
0006929491.tif 000018
ここで、λ７（ｘ）＝１、λ６（ｘ）＝ｘλ７（ｘ）、λ５（ｘ）＝ｘλ６（ｘ）、λ４（ｘ）＝ｘλ５（ｘ）、λ３（ｘ）＝ｘλ４（ｘ）−１、λ２（ｘ）＝ｘλ３（ｘ）、λ１（ｘ）＝ｘλ２（ｘ）、λ０（ｘ）＝ｘλ１（ｘ）である。
【００４５】
＜例６：ＢＬＳ−２７＞
曲線がＢＬＳ−２７の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝１／３Φ２７（ｘ）＝１／３（ｘ１８＋ｘ９＋１）であり、多項式ｐ（ｘ）＝（ｘ−１）２ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝（ｘ−１）２であり、多項式ｈ２（ｘ）＝３である。そのため、指数部分は数２７のように分解される。
【数２７】
0006929491.tif 000019
ここで、λ１７（ｘ）＝１、λ１６（ｘ）＝ｘλ１７（ｘ）、λ１５（ｘ）＝ｘλ１６（ｘ）、λ１４（ｘ）＝ｘλ１５（ｘ）、λ１３（ｘ）＝ｘλ１４（ｘ）、λ１２（ｘ）＝ｘλ１３（ｘ）、λ１１（ｘ）＝ｘλ１２（ｘ）、λ１０（ｘ）＝ｘλ１１（ｘ）、λ９（ｘ）＝ｘλ１０（ｘ）、λ８（ｘ）＝ｘλ９（ｘ）＋１、λ７（ｘ）＝ｘλ８（ｘ）、λ６（ｘ）＝ｘλ７（ｘ）、λ５（ｘ）＝ｘλ６（ｘ）、λ４（ｘ）＝ｘλ５（ｘ）、λ３（ｘ）＝ｘλ４（ｘ）、λ２（ｘ）＝ｘλ３（ｘ）、λ１（ｘ）＝ｘλ２（ｘ）、λ０（ｘ）＝ｘλ１（ｘ）である。
【００４６】
＜例７：ＢＬＳ−２８＞
曲線がＢＬＳ−２８の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝Φ２８（ｘ）＝ｘ１２−ｘ１０＋ｘ８−ｘ６＋ｘ４−ｘ２＋１であり、多項式ｐ（ｘ）＝１／３（ｘ−１）２（ｘ２＋１）ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝１／３（ｘ−１）２（ｘ２＋１）であり、多項式ｈ２（ｘ）＝１である。そのため、指数部分は数２８のように分解される。
【数２８】
0006929491.tif 000020
ここで、λ１１（ｘ）＝１、λ１０（ｘ）＝ｘλ１１（ｘ）、λ９（ｘ）＝ｘλ１０（ｘ）−１、λ８（ｘ）＝ｘλ９（ｘ）、λ７（ｘ）＝ｘλ８（ｘ）＋１、λ６（ｘ）＝ｘλ７（ｘ）、λ５（ｘ）＝ｘλ６（ｘ）−１、λ４（ｘ）＝ｘλ５（ｘ）、λ３（ｘ）＝ｘλ４（ｘ）＋１、λ２（ｘ）＝ｘλ３（ｘ）、λ１（ｘ）＝ｘλ２（ｘ）−１、λ０（ｘ）＝ｘλ１（ｘ）である。
【００４７】
＜例８：ｋ＝２８＞
曲線の埋め込み次数ｋ＝２８（ＢＬＳ曲線でない）の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝Φ２８（ｘ）＝ｘ１２−ｘ１０＋ｘ８−ｘ６＋ｘ４−ｘ２＋１であり、多項式ｐ（ｘ）＝１／４（ｘ−１）２（ｘ２＋１）ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝１／４（ｘ−１）２（ｘ２＋１）であり、多項式ｈ２（ｘ）＝１である。そのため、指数部分は数２９のように分解される。
【数２９】
0006929491.tif 000021
ここで、λ１１（ｘ）＝１、λ１０（ｘ）＝ｘλ１１（ｘ）、λ９（ｘ）＝ｘλ１０（ｘ）−１、λ８（ｘ）＝ｘλ９（ｘ）、λ７（ｘ）＝ｘλ８（ｘ）＋１、λ６（ｘ）＝ｘλ７（ｘ）、λ５（ｘ）＝ｘλ６（ｘ）−１、λ４（ｘ）＝ｘλ５（ｘ）、λ３（ｘ）＝ｘλ４（ｘ）＋１、λ２（ｘ）＝ｘλ３（ｘ）、λ１（ｘ）＝ｘλ２（ｘ）−１、λ０（ｘ）＝ｘλ１（ｘ）である。
【００４８】
＜例９：ＢＬＳ−４２＞
曲線がＢＬＳ−４２の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝Φ４２（ｘ）＝ｘ１２＋ｘ１１−ｘ９−ｘ８＋ｘ６−ｘ４−ｘ３＋ｘ＋１であり、多項式ｐ（ｘ）＝１／３（ｘ−１）２（ｘ２−ｘ＋１）ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝１／３（ｘ−１）２（ｘ２−ｘ＋１）であり、多項式ｈ２（ｘ）＝１である。そのため、指数部分は数３０のように分解される。
【数３０】
0006929491.tif 000022
ここで、λ１１（ｘ）＝１、λ１０（ｘ）＝ｘλ１１（ｘ）＋１、λ９（ｘ）＝ｘλ１０（ｘ）、λ８（ｘ）＝ｘλ９（ｘ）−１、λ７（ｘ）＝ｘλ８（ｘ）−１、λ６（ｘ）＝ｘλ７（ｘ）、λ５（ｘ）＝ｘλ６（ｘ）＋１、λ４（ｘ）＝ｘλ５（ｘ）、λ３（ｘ）＝ｘλ４（ｘ）−１、λ２（ｘ）＝ｘλ３（ｘ）−１、λ１（ｘ）＝ｘλ２（ｘ）、λ０（ｘ）＝ｘλ１（ｘ）＋１である。
【００４９】
＜例１０：ＢＬＳ−４８＞
曲線がＢＬＳ−４８の例を説明する。
この場合には、多項式ｔ（ｘ）＝ｘ＋１であり、多項式ｒ（ｘ）＝Φ４８（ｘ）＝ｘ１６−ｘ８＋１であり、多項式ｐ（ｘ）＝１／３（ｘ−１）２ｒ（ｘ）＋ｘである。したがって、多項式Ｔ（ｘ）＝ｘであり、多項式ｈ１（ｘ）＝１／３（ｘ−１）２であり、多項式ｈ２（ｘ）＝１である。そのため、指数部分は数３１のように分解される。
【数３１】
0006929491.tif 000023
ここで、λ１５（ｘ）＝１、λ１４（ｘ）＝ｘλ１５（ｘ）、λ１３（ｘ）＝ｘλ１４（ｘ）、λ１２（ｘ）＝ｘλ１３（ｘ）、λ１１（ｘ）＝ｘλ１２（ｘ）、λ１０（ｘ）＝ｘλ１１（ｘ）、λ９（ｘ）＝ｘλ１０（ｘ）、λ８（ｘ）＝ｘλ９（ｘ）、λ７（ｘ）＝ｘλ８（ｘ）−１、λ６（ｘ）＝ｘλ７（ｘ）、λ５（ｘ）＝ｘλ６（ｘ）、λ４（ｘ）＝ｘλ５（ｘ）、λ３（ｘ）＝ｘλ４（ｘ）、λ２（ｘ）＝ｘλ３（ｘ）、λ１（ｘ）＝ｘλ２（ｘ）、λ０（ｘ）＝ｘλ１（ｘ）である。
【００５０】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る最終べき計算装置１０は、多項式Φｋ（ｐ（ｘ））により指数部分をイージーパートとハードパートとに分解し、ハードパートをＴ（ｘ）乗と、ｈ１（ｘ）乗と、ｈ２（ｘ）乗と、乗算及び逆元算の少なくともいずれかとを用いて計算する。これにより、ペアリング演算を効率的に計算可能になる。
【００５１】
特に、実施の形態１に係る最終べき計算装置１０は、ハードパートを数１４に基づき多項式ｐ（ｘ）ｉの線形和に変換する。これにより、多くの楕円曲線に関して、ペアリング演算を効率的に計算可能になる。
具体的には、ハードパートを数１４に基づき多項式ｐ（ｘ）ｉの線形和に変換することにより、ｐ（ｘ）のべき乗算の数が少し増える代わりに、ｘのべき乗算の数が大幅に少なくなる。ｐ（ｘ）のべき乗算の計算量に比べ、ｘのべき乗算の計算量は、非常に多いことが知られている。そのため、実施の形態１に係る最終べき計算装置１０は、ハードパートを数１４に基づき多項式ｐ（ｘ）ｉの線形和に変換することにより、ペアリング演算を効率的に計算可能である。
より具体的には、従来研究されてきたＢＬＳ−９，１２，１５，２４，２７，４８曲線といったトレースがｔ（ｘ）＝ｘ＋１である代表的な楕円曲線族に対して、特に最終べき計算の計算効率を向上させることが可能である。
【００５２】
＊＊＊他の構成＊＊＊
【００５３】
＜変形例１＞
実施の形態１では、各機能構成要素がソフトウェアで実現された。しかし、変形例１として、各機能構成要素はハードウェアで実現されてもよい。この変形例１について、実施の形態１と異なる点を説明する。
【００５４】
図６を参照して、変形例１に係る最終べき計算装置１０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、最終べき計算装置１０は、プロセッサ１１とメモリ１２とストレージ１３とに代えて、電子回路１５を備える。電子回路１５は、各機能構成要素と、メモリ１２と、ストレージ１３との機能とを実現する専用の回路である。
【００５５】
電子回路１５としては、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
各機能構成要素を１つの電子回路１５で実現してもよいし、各機能構成要素を複数の電子回路１５に分散させて実現してもよい。
【００５６】
＜変形例２＞
変形例２として、一部の各機能構成要素がハードウェアで実現され、他の各機能構成要素がソフトウェアで実現されてもよい。
【００５７】
プロセッサ１１とメモリ１２とストレージ１３と電子回路１５とを処理回路という。つまり、各機能構成要素の機能は、処理回路により実現される。
【００５８】
＜変形例３＞
実施の形態１では、Ｍｉｌｌｅｒ  ｌｏｏｐで計算された値ｆを取得して、最終べきの計算だけを行う最終べき計算装置１０を説明した。実施の形態１で説明した最終べき計算装置１０に、Ｍｉｌｌｅｒ  ｌｏｏｐの計算を行う機能を加えて、ペアリング演算を行うペアリング演算装置３０を構成してもよい。
【００５９】
図７を参照して、変形例３に係るペアリング演算装置３０の構成を説明する。
ペアリング演算装置３０は、最終べき計算装置１０が備える機能構成要素に加えて、Ｍｉｌｌｅｒ関数計算部３１を備える。Ｍｉｌｌｅｒ関数計算部３１は、最終べき計算装置１０が備える機能構成要素と同様に、ソフトウェア又はハードウェアによって実現される。Ｍｉｌｌｅｒ関数計算部３１は、Ｍｉｌｌｅｒ  ｌｏｏｐの計算を行う。
【００６０】
この場合には、図５のステップＳ３１では、べき計算部２２は、Ｍｉｌｌｅｒ関数計算部３１によって計算された値ｆを取得する。
【００６１】
＜変形例４＞
実施の形態１では、多項式ｈ１（ｘ）及び多項式ｈ２（ｘ）から係数の分母を削除するために、整数ａが計算された。実施の形態１では、多項式ｈ１（ｘ）及び多項式ｈ２（ｘ）の係数に分数がない場合には、整数ａとして１が計算されることになる。しかし、多項式ｈ１（ｘ）及び多項式ｈ２（ｘ）の係数に分数がない場合には、整数ａを計算しなくてもよい。そして、この場合には、べき簡単化処理及びべき計算処理において整数ａを乗じる必要はない。
【００６２】
実施の形態２．
実施の形態１では、ペアリング演算の最終べきの計算方法について説明した。実施の形態２では、実施の形態１で計算されたペアリング演算の結果を用いた処理について説明する。実施の形態２では、実施の形態１と異なる点を説明し、同一の点については説明を省略する。
【００６３】
＊＊＊構成の説明＊＊＊
図８を参照して、実施の形態２に係る暗号処理装置４０の構成を説明する。
暗号処理装置４０は、実施の形態１に係る最終べき計算装置１０が備える機能構成要素に加え、暗号処理部４１を備える。暗号処理部４１は、最終べき計算装置１０が備える機能構成要素と同様に、ソフトウェア又はハードウェアによって実現される。
【００６４】
＊＊＊動作の説明＊＊＊
図９を参照して、実施の形態２に係る暗号処理装置４０の動作を説明する。
実施の形態２に係る暗号処理装置４０の動作手順は、実施の形態２に係る暗号処理方法に相当する。また、実施の形態２に係る暗号処理装置４０の動作を実現するプログラムは、実施の形態２に係る暗号処理プログラムに相当する。
【００６５】
（ステップＳ４１：ペアリング演算処理）
実施の形態１に係る最終べき計算装置１０が備える機能構成要素によって、ペアリング演算の結果が計算される。ペアリング演算の結果はメモリ１２に書き込まれる。
【００６６】
（ステップＳ４２：暗号処理）
暗号処理部４１は、ステップＳ４１で得られたペアリング演算の結果を用いて、暗号処理を行う。暗号処理は、暗号化処理と、復号処理と、署名処理と、検証処理といった暗号プリミティブの処理である。
暗号化処理は、データを第三者から秘匿するために、平文状態のデータを暗号文に変換する処理である。復号処理は、暗号化処理により変換された暗号文を平文状態のデータに変換する処理である。署名処理は、データの改ざん検出とデータの出所確認との少なくともいずれかのための署名を生成する処理である。検証処理は、署名処理で生成された署名によりデータの改ざん検出とデータの出所確認との少なくともいずれかをする処理である。
【００６７】
例えば、暗号処理部４１は、暗号文の要素と復号鍵の要素とを入力とするペアリング演算の結果を用いて、暗号文を復号したメッセージを生成することが考えられる。
【００６８】
＊＊＊実施の形態２の効果＊＊＊
以上のように、実施の形態２に係る暗号処理装置４０は、実施の形態１に係る最終べき計算装置１０の機能構成要素を用いて暗号処理を実現する。実施の形態１に係る最終べき計算装置１０は、ペアリング演算を効率的に計算可能である。そのため、実施の形態２に係る暗号処理装置４０は、効率的に暗号処理を実施可能である。
【００６９】
＊＊＊他の構成＊＊＊
＜変形例５＞
実施の形態２では、暗号処理装置４０は、実施の形態１に係る最終べき計算装置１０が備える機能構成要素に加え、暗号処理部４１を備えた。しかし、暗号処理装置４０は、変形例３で説明したペアリング演算装置３０が備える機能構成要素に加え、暗号処理部４１を備えてもよい。
【００７０】
以上、本開示の実施の形態及び変形例について説明した。これらの実施の形態及び変形例のうち、いくつかを組み合わせて実施してもよい。また、いずれか１つ又はいくつかを部分的に実施してもよい。なお、本開示は、以上の実施の形態及び変形例に限定されるものではなく、必要に応じて種々の変更が可能である。
【符号の説明】
【００７１】
１０  最終べき計算装置、１１  プロセッサ、１２  メモリ、１３  ストレージ、１４  通信インタフェース、１５  電子回路、２１  べき簡単化部、２１１  分解部、２１２  生成部、２２  べき計算部、３０  ペアリング演算装置、３１  Ｍｉｌｌｅｒ関数計算部、４０  暗号処理装置、４１  暗号処理部。
【要約】
分解部（２１１）は、次数ｄの円分多項式Φｋ（ｘ）と多項式Ｔ（ｘ）と多項式ｈ１（ｘ）と多項式ｈ２（ｘ）とを用いて表される多項式ｒ（ｘ）＝Φｋ（Ｔ（ｘ））／ｈ２（ｘ）と多項式ｐ（ｘ）＝ｈ１（ｘ）ｒ（ｘ）＋Ｔ（ｘ）と多項式ｔ（ｘ）＝Ｔ（ｘ）＋１と、埋め込み次数ｋとで表される楕円曲線におけるペアリング演算の最終べき計算部分について、多項式Φｋ（ｐ（ｘ））により指数部分をイージーパートとハードパートとに分解する。べき計算部（２２）は、ハードパートを、ｉ＝０，．．．，ｄ−１の各整数ｉについての多項式ｐ（ｘ）ｉ乗と、λｄ−１（ｘ）＝ｃｄであるλｄ−１（ｘ）乗と、ｉ＝１，．．．，ｄ−２の各整数ｉについてのλｉ＝Ｔ（ｘ）λｉ＋１（ｘ）＋ｃｉ＋１であるλｉ乗と、ｈ１（ｘ）乗と、ｈ２（ｘ）乗と、乗算と、逆元算とを用いて計算する。【図１】
0006929491.tif 000028
【図２】
0006929491.tif 000029
【図３】
0006929491.tif 000030
【図４】
0006929491.tif 000031
【図５】
0006929491.tif 000032
【図６】
0006929491.tif 000033
【図７】
0006929491.tif 000034
【図８】
0006929491.tif 000035
【図９】
0006929491.tif 000036