(57)【要約】【課題】ペアリング演算を効率的に行う。【解決手段】KSS曲線におけるペアリング演算の最終べきを計算するための複数のパラメータλiを入力する入力手順と、入力した前記複数のパラメータλiのうちの所定のパラメータλsを因数分解及び平方完成することで第１のパラメータA及び第２のパラメータBを算出する第１の算出手順と、算出した前記第１のパラメータA及び／又は前記第２のパラメータBを用いて表される第３のパラメータλ´(s-1)/2及び第４のパラメータλ´sを算出する第２の算出手順と、前記複数のパラメータλiのうち、添え字iが所定の範囲内であるパラメータλiを、算出した前記第３のパラメータλ´(s-1)/2と、前記第４のパラメータλ´sとの線形和で表されるパラメータに変換する変換手順と、をコンピュータが実行する。【選択図】図１
2018205511.tif 000002
【特許請求の範囲】
【請求項１】
KSS曲線におけるペアリング演算の最終べきを計算するための複数のパラメータλiを入力する入力手順と、
入力した前記複数のパラメータλiのうちの所定のパラメータλsを因数分解及び平方完成することで第１のパラメータA及び第２のパラメータBを算出する第１の算出手順と、
算出した前記第１のパラメータA及び／又は前記第２のパラメータBを用いて表される第３のパラメータλ´(s-1)/2及び第４のパラメータλ´sを算出する第２の算出手順と、
前記複数のパラメータλiのうち、添え字iが所定の範囲内であるパラメータλiを、算出した前記第３のパラメータλ´(s-1)/2と、前記第４のパラメータλ´sとの線形和で表されるパラメータに変換する変換手順と、
をコンピュータが実行するパラメータ変換方法。
【請求項２】
前記第１の算出手順は、
前記パラメータλsを因数分解し、該因数分解後の式を平方完成することで前記第２のパラメータBを算出した上で、該第２のパラメータBと、λ(s-1)/2の係数比較により算出される第５のパラメータTとで表される前記第１のパラメータAを算出する、ことを特徴とする請求項１に記載のパラメータ変換方法。
【請求項３】
KSS曲線におけるペアリング演算の最終べきを計算するための複数のパラメータλiを入力する入力部と、
入力した前記複数のパラメータλiのうちの所定のパラメータλsを因数分解及び平方完成することで第１のパラメータA及び第２のパラメータBを算出する第１の算出部と、
算出した前記第１のパラメータA及び／又は前記第２のパラメータBを用いて表される第３のパラメータλ´(s-1)/2及び第４のパラメータλ´sを算出する第２の算出部と、
前記複数のパラメータλiのうち、添え字iが所定の範囲内であるパラメータλiを、算出した前記第３のパラメータλ´(s-1)/2と、前記第４のパラメータλ´sとの線形和で表されるパラメータに変換する変換部と、
を有するパラメータ変換装置。
【請求項４】
KSS曲線におけるペアリング演算の最終べきを計算するための複数のパラメータλiを入力する入力手順と、
入力した前記複数のパラメータλiのうちの所定のパラメータλsを因数分解及び平方完成することで第１のパラメータA及び第２のパラメータBを算出する第１の算出手順と、
算出した前記第１のパラメータA及び／又は前記第２のパラメータBを用いて表される第３のパラメータλ´(s-1)/2及び第４のパラメータλ´sを算出する第２の算出手順と、
前記複数のパラメータλiのうち、添え字iが所定の範囲内であるパラメータλiを、算出した前記第３のパラメータλ´(s-1)/2と、前記第４のパラメータλ´sとの線形和で表されるパラメータに変換する変換手順と、
をコンピュータに実行させるパラメータ変換プログラム。
【請求項５】
KSS曲線におけるペアリング演算の最終べきの指数部分を第１の指数部分と第２の指数部分とに分解する分解手順と、
前記第２の指数部分に対応する前記最終べきを計算するための複数のパラメータλiのうちの所定のパラメータλsを因数分解及び平方完成することで第１のパラメータA及び第２のパラメータBを算出する第１の算出手順と、
算出した前記第１のパラメータA及び／又は前記第２のパラメータBを用いて表される第３のパラメータλ´(s-1)/2及び第４のパラメータλ´sを算出する第２の算出手順と、
前記複数のパラメータλiのうち、添え字iが所定の範囲内であるパラメータλiを、算出した前記第３のパラメータλ´(s-1)/2と、前記第４のパラメータλ´sとの線形和で表されるパラメータに変換する変換手順と、
前記ペアリング演算のMiller Loopを計算する第１の計算手順と、
前記第１の計算手順による計算結果を用いて、前記第１の指数部分に対応する前記最終べきを計算する第２の計算手順と、
変換された複数のパラメータλiと、前記第２の計算手順による計算結果とを用いて、前記第２の指数部分に対応する前記最終べきを計算する第３の計算手順と、
をコンピュータが実行するペアリング演算方法。
【請求項６】
前記第１の算出手順は、
前記パラメータλsを因数分解し、該因数分解後の式を平方完成することで前記第２のパラメータBを算出した上で、該第２のパラメータBと、λ(s-1)/2の係数比較により算出される第５のパラメータTとで表される前記第１のパラメータAを算出する、ことを特徴とする請求項５に記載のペアリング演算方法。
【請求項７】
KSS曲線におけるペアリング演算の最終べきの指数部分を第１の指数部分と第２の指数部分とに分解する分解部と、
前記第２の指数部分に対応する前記最終べきを計算するための複数のパラメータλiのうちの所定のパラメータλsを因数分解及び平方完成することで第１のパラメータA及び第２のパラメータBを算出する第１の算出部と、
算出した前記第１のパラメータA及び／又は前記第２のパラメータBを用いて表される第３のパラメータλ´(s-1)/2及び第４のパラメータλ´sを算出する第２の算出部と、
前記複数のパラメータλiのうち、添え字iが所定の範囲内であるパラメータλiを、算出した前記第３のパラメータλ´(s-1)/2と、前記第４のパラメータλ´sとの線形和で表されるパラメータに変換する変換部と、
前記ペアリング演算のMiller Loopを計算する第１の計算部と、
前記第１の計算部による計算結果を用いて、前記第１の指数部分に対応する前記最終べきを計算する第２の計算部と、
変換された複数のパラメータλiと、前記第２の計算部による計算結果とを用いて、前記第２の指数部分に対応する前記最終べきを計算する第３の計算部と、
を有するペアリング演算装置。
【請求項８】
KSS曲線におけるペアリング演算の最終べきの指数部分を第１の指数部分と第２の指数部分とに分解する分解手順と、
前記第２の指数部分に対応する前記最終べきを計算するための複数のパラメータλiのうちの所定のパラメータλsを因数分解及び平方完成することで第１のパラメータA及び第２のパラメータBを算出する第１の算出手順と、
算出した前記第１のパラメータA及び／又は前記第２のパラメータBを用いて表される第３のパラメータλ´(s-1)/2及び第４のパラメータλ´sを算出する第２の算出手順と、
前記複数のパラメータλiのうち、添え字iが所定の範囲内であるパラメータλiを、算出した前記第３のパラメータλ´(s-1)/2と、前記第４のパラメータλ´sとの線形和で表されるパラメータに変換する変換手順と、
前記ペアリング演算のMiller Loopを計算する第１の計算手順と、
前記第１の計算手順による計算結果を用いて、前記第１の指数部分に対応する前記最終べきを計算する第２の計算手順と、
変換された複数のパラメータλiと、前記第２の計算手順による計算結果とを用いて、前記第２の指数部分に対応する前記最終べきを計算する第３の計算手順と、
をコンピュータに実行させるペアリング演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パラメータ変換方法、パラメータ変換装置、パラメータ変換プログラム、ペアリング演算方法、ペアリング演算装置、及びペアリング演算プログラムに関する。
【背景技術】
【０００２】
楕円曲線上のペアリングが持つ双線形性によって、ＩＤベース暗号や関数型暗号等の暗号方式が提案されている。また、近年では、Apache Milagro（incubating）でのOSS（Open-source software）によるオープンな開発や、IETF（Internet Engineering Task Force）での標準化がされる等、ペアリング暗号を実社会で利用するための活動が行われている。
【０００３】
ペアリング暗号を実際のシステムとして実現するためには、ペアリング演算を効率的に行うことが重要である。ペアリング演算は、Miller Loopの計算と、最終べきの計算との２つの部分から構成されており、これらの計算コストを削減することで、効率的な演算を行えることが知られている。また、ペアリングを計算するための楕円曲線をKachisa-Schaefer-Scott（KSS）曲線とした場合、最終べき部分の計算コストが大きいことが知られている。
【０００４】
KSS曲線Eは、ある整数x、素数p=p(x)及びr=r(x)、埋め込み次数k等のパラメータを持つことが知られている。整数x、素数p及びr、埋め込み次数k、KSS曲線Eに対して、G1及びG2を位数rの楕円曲線
【０００５】
【数１】
2018205511.tif 000003
上の部分群とし、G3を有限体
【０００６】
【数２】
2018205511.tif 000004
上の位数rの部分群とする。また、fx,Qを有理関数とする。このとき、G1、G2、G3に対して、ペアリングeは、以下の数３で定義される。
【０００７】
【数３】
2018205511.tif 000005
ここで、ペアリング演算
【０００８】
【数４】
2018205511.tif 000006
は、Miller Loop fx,Q(P)の計算と、最終べき
【０００９】
【数５】
2018205511.tif 000007
の計算との２つのステップで計算される。
【００１０】
Miller Loopの計算は、既知のMillerアルゴリズムを用いて計算することができる。一方で、最終べき
【００１１】
【数６】
2018205511.tif 000008
の計算は、円多項式Φkを用いて、指数部分を以下の数７のように分解することで効率的に計算できることが知られている（非特許文献１）。
【００１２】
【数７】
2018205511.tif 000009
easy partである
【００１３】
【数８】
2018205511.tif 000010
の計算は、
【００１４】
【数９】
2018205511.tif 000011
上の共役演算及び逆元算が１回と、フロベニウス計算及び乗算が数回とで計算できる。このため、easy partは、hard partと比較して計算コストが非常に小さく、最終べき全体の計算コストにほぼ影響がないことが知られている。
【００１５】
そして、hard partを計算するには、まず、Φk(p(x))/r(x)を以下の数１０のように変形する。ただし、cは正の整数、φ(k)をオイラー関数として、s=φ(k)-1とする。
【００１６】
【数１０】
2018205511.tif 000012
ここで、d=deg(p(x))、s´=s-1に対して、λiは、以下の数１１のように表現することができる。ただし、ai,j、bi,j、ciは整数とする。
【００１７】
【数１１】
2018205511.tif 000013
したがって、λiに対して、hard partは、以下の数１２により計算することができる。これにより、最終べきが計算される。
【００１８】
【数１２】
2018205511.tif 000014
このとき、KSS-16曲線（すなわち、埋め込み次数k=16であるKSS曲線）の場合は、λiを簡約化した結果が知られている（非特許文献２）。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】M. Scott, N. Benger and M. Charlemagne, "On the Final Exponentiation for Calcu-lating Pairings on Ordinary Elliptic Curves", Pairing 2009, LNCS 5671, pp.78-88,2009.
【非特許文献２】X. Zhang and D. Lin, "Analysis of Optimum Pairing Products at High Security Levels", INDOCRYPT 2012, LNCS 7668, pp.412-430, 2012.
【発明の概要】
【発明が解決しようとする課題】
【００２０】
しかしながら、KSS-16曲線以外の曲線では、λiの各係数を簡約化することができなかった。言い換えれば、KSS曲線一般では、λiの各係数を簡約化することができなかった。
【００２１】
このため、KSS曲線一般では、ペアリング演算における最終べきの計算コストを削減することができなかった。
【００２２】
本発明の実施の形態は、上記の点に鑑みてなされたもので、ペアリング演算を効率的に行うことを目的とする。
【課題を解決するための手段】
【００２３】
上記課題を解決するため、KSS曲線におけるペアリング演算の最終べきを計算するための複数のパラメータλiを入力する入力手順と、入力した前記複数のパラメータλiのうちの所定のパラメータλsを因数分解及び平方完成することで第１のパラメータA及び第２のパラメータBを算出する第１の算出手順と、算出した前記第１のパラメータA及び／又は前記第２のパラメータBを用いて表される第３のパラメータλ´(s-1)/2及び第４のパラメータλ´sを算出する第２の算出手順と、前記複数のパラメータλiのうち、添え字iが所定の範囲内であるパラメータλiを、算出した前記第３のパラメータλ´(s-1)/2と、前記第４のパラメータλ´sとの線形和で表されるパラメータに変換する変換手順と、をコンピュータが実行する。
【発明の効果】
【００２４】
ペアリング演算を効率的に行うことができる。
【図面の簡単な説明】
【００２５】
【図１】本発明の実施の形態におけるペアリング演算装置の全体構成の一例を示す図である。
【図２】本発明の実施の形態におけるペアリング演算装置のハードウェア構成の一例を示す図である。
【図３】本発明の実施の形態におけるペアリング演算処理の一例を示すフローチャートである。
【図４】本発明の実施の形態における簡約化処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００２６】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００２７】
＜ペアリング演算装置１０の全体構成＞
まず、本発明の実施の形態におけるペアリング演算装置１０の全体構成について、図１を参照しながら説明する。図１は、本発明の実施の形態におけるペアリング演算装置１０の全体構成の一例を示す図である。
【００２８】
図１に示すペアリング演算装置１０は、ペアリング暗号におけるペアリング演算を行うコンピュータである。ペアリング演算装置１０は、入力部１０１と、Miller Loop計算部１０２と、最終べき計算部１０３と、簡約化部１０４と、出力部１０５とを有する。これらの各部は、ペアリング演算装置１０にインストールされた１以上のプログラムが、後述するCPU１６に実行させる処理により実現される。
【００２９】
入力部１０１は、ペアリング演算に用いられるパラメータを入力する。以降では、入力部１０１により入力されるパラメータを「入力パラメータ」と表す。入力パラメータとしては、例えば、素数p及びr、埋め込み次数k、整数x等が挙げられる。すなわち、入力パラメータとしては、例えば、「E. J. Kachisa, E. F. Schaefer and M. Scott, "Constructing Brezing-Weng pairingfriendly elliptic curves using elements in the cyclotomic eld", Pairing 2008, LNCS5209, pp.126-135, 2008.」に開示されている各パラメータが挙げられる。また、入力パラメータとしては、例えば、楕円曲線上の２点P及びQ等も挙げられる。
【００３０】
入力部１０１により入力された入力パラメータは、Miller Loop計算部１０２に出力される。
【００３１】
Miller Loop計算部１０２は、Miller Loop fx,Q(P)を計算する。Miller Loopは、例えば、「V. S. Miller, "The Weil Pairing, and Its Efficient Calculation," Journal of Cryptol-ogy, vol. 17, pp. 235-261, 2004.」に開示されているMillerアルゴリズムを用いて計算することができる。Miller Loop計算部１０２により計算された計算結果は、最終べき計算部１０３に出力される。
【００３２】
最終べき計算部１０３は、上記の数５で示した最終べきを計算する。最終べき計算部１０３は、上記の数７に示したように、最終べきをeasy partと、hard partとに分解した上で、上記の数１２により、最終べきを計算する。このとき、最終べき計算部１０３は、簡約化部１０４により簡約化されたλiを用いて、上記の数１２により、最終べきを計算する。最終べき計算部１０３により計算された計算結果は、出力部１０５に出力される。
【００３３】
簡約化部１０４により簡約化されたλiを用いることで、最終べき計算部１０３は、KSS曲線一般に対して、最終べきを効率的に計算することができるようになる。すなわち、最終べき計算部１０３は、ペアリング演算における最終べきを効率的に計算することができるようになる。
【００３４】
簡約化部１０４は、上記の数１２を計算するためのパラメータであるλiを簡約化する。言い換えれば、簡約化部１０４は、上記の数１２を計算するためのパラメータλiを、簡約化されたλiに変換する。簡約化部１０４により簡約化されたλiは、最終べき計算部１０３に出力される。
【００３５】
出力部１０５は、ペアリング演算の演算結果（すなわち、最終べき計算部１０３の計算結果）を出力する。出力部１０５による出力先としては、例えば、ペアリング暗号を利用するプログラムや他の装置等が挙げられる。
【００３６】
なお、図１に示すペアリング演算装置１０の構成は一例であって、他の構成であっても良い。例えば、ペアリング演算装置１０は、複数台のコンピュータで構成されていても良い。
【００３７】
＜ペアリング演算装置１０のハードウェア構成＞
次に、本発明の実施の形態におけるペアリング演算装置１０のハードウェア構成について、図２を参照しながら説明する。図２は、本発明の実施の形態におけるペアリング演算装置１０のハードウェア構成の一例を示す図である。
【００３８】
図２に示すペアリング演算装置１０は、入力装置１１と、表示装置１２と、外部I/F１３と、RAM（Random Access Memory）１４と、ROM（Read Only Memory）１５と、CPU（Central Processing Unit）１６と、通信I/F１７と、補助記憶装置１８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００３９】
入力装置１１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置１２は、例えばディスプレイ等であり、ペアリング演算装置１０の処理結果を表示する。
【００４０】
外部I/F１３は、外部装置とのインタフェースである。外部装置には、記録媒体１３ａ等がある。ペアリング演算装置１０は、外部I/F１３を介して、記録媒体１３ａ等の読み取りや書き込みを行うことができる。記録媒体１３ａには、本実施形態を実現するプログラム等が記録されていても良い。
【００４１】
記録媒体１３ａには、例えば、フレキシブルディスク、CD（Compact Disc）、DVD（Digital Versatile Disk）、SDメモリカード（Secure Digital memory card）、USB（Universal Serial Bus）メモリカード等がある。
【００４２】
RAM１４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ROM１５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ROM１５には、例えば、OS（Operating System）設定やネットワーク設定等が格納されている。
【００４３】
CPU１６は、ROM１５や補助記憶装置１８等からプログラムやデータをRAM１４上に読み出して処理を実行する演算装置である。
【００４４】
通信I/F１７は、ペアリング演算装置１０をネットワークに接続するためのインタフェースである。本実施形態を実現するプログラム等は、通信I/F１７を介して、所定のサーバ等から取得（ダウンロード）されても良い。
【００４５】
補助記憶装置１８は、例えばHDD（Hard Disk Drive）やSSD（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置１８に格納されているプログラムやデータには、例えば、OS、当該OS上において各種機能を実現するアプリケーションプログラム、本実施形態を実現するプログラム等がある。
【００４６】
本発明の実施の形態におけるペアリング演算装置１０は、図２に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。
【００４７】
＜ペアリング演算処理＞
以降では、本発明の実施形態におけるペアリング演算装置１０が実行するペアリング演算処理について、図３を参照しながら説明する。図３は、本発明の実施の形態におけるペアリング演算処理の一例を示すフローチャートである。
【００４８】
まず、入力部１０１は、ペアリング演算に用いられる入力パラメータを入力する（ステップＳ１）。
【００４９】
次に、最終べき計算部１０３は、最終べきをeasy partと、hard partとに分解した上で、hard partを計算するためのλiを算出する（ステップＳ２）。すなわち、最終べき計算部１０３は、上記の数１１に示すλiを算出する。
【００５０】
次に、簡約化部１０４は、最終べき計算部１０３により算出されたλiを簡約化する（ステップＳ３）。すなわち、簡約化部１０４は、最終べきを計算するためのパラメータλiを、簡約化されたλiに変換する。なお、本ステップにおける簡約化処理の詳細については後述する。
【００５１】
次に、Miller Loop計算部１０２は、入力部１０１により入力された入力パラメータを用いて、Miller Loop fx,Q(P)を計算する（ステップＳ４）。
【００５２】
次に、最終べき計算部１０３は、簡約化部１０４により簡約化されたλiを用いて、上記の数１２により、最終べきを計算する（ステップＳ５）。
【００５３】
次に、出力部１０５は、ペアリング演算の演算結果e(P,Q)を出力する（ステップＳ６）。すなわち、出力部１０５は、最終べき計算部１０３の計算結果を出力する。
【００５４】
以上のように、本発明の実施の形態におけるペアリング演算装置１０は、簡約化部１０４により簡約化されたλiを用いることで、KSS曲線一般に対して、最終べきを効率的に計算することができるようになる。したがって、本発明の実施の形態におけるペアリング演算装置１０によれば、効率的なペアリング演算を行うことができるようになる。
【００５５】
＜簡約化処理＞
次に、上記のステップＳ３における処理（最終べきの計算に用いられるλiを簡約化する処理）について、図４を参照しながら説明する。図４は、本発明の実施の形態における簡約化処理の一例を示すフローチャートである。
【００５６】
まず、簡約化部１０４は、以下の数１３によりλsを因数分解する（ステップＳ１１）。
【００５７】
【数１３】
2018205511.tif 000015
次に、簡約化部１０４は、因数分解後の２次式x2+(bs,1/bs,0)x+(bs,2/bs,0)を平方完成させて、平方完成後の２次式をB=(x-α)2+βとする（ステップＳ１２）。
【００５８】
次に、簡約化部１０４は、A=xd/2-2・B+Tとする（ステップＳ１３）。
【００５９】
次に、簡約化部１０４は、s´=s-1として、λs´/2を、
【００６０】
【数１４】
2018205511.tif 000016
とおく（ステップＳ１４）。
【００６１】
次に、簡約化部１０４は、以下の数１５により係数比較を行ってTを求める（ステップＳ１５）。これにより、上記のAの式が決まる。
【００６２】
【数１５】
2018205511.tif 000017
次に、簡約化部１０４は、A及びBを用いて、上記の数１１に示すλiを以下の数１６のように書き直す（ステップＳ１６）。ただし、ui=gcd(ai,0, bi,0)、vi=ai,0/ui、wi=bi,0/ui、bs,0=ge・hとする。
【００６３】
【数１６】
2018205511.tif 000018
次に、簡約化部１０４は、λ´iを以下の数１７で定義する（ステップＳ１７）。
【００６４】
【数１７】
2018205511.tif 000019
次に、簡約化部１０４は、1≦i≦s´/2及びs´/2+2≦i≦s´の各λ´iのvi・x・A+wi・Bを以下の数１８のように、λ´s´/2とλ´sとの線形和で表現する（ステップＳ１８）。
【００６５】
【数１８】
2018205511.tif 000020
次に、簡約化部１０４は、1≦i≦s´/2のときのλiを、λ´s´/2とλ´sとを用いて、以下の数１９のように表現する（ステップＳ１９）。
【００６６】
【数１９】
2018205511.tif 000021
次に、簡約化部１０４は、s´/2+2≦i≦s´のときのλiを、λ´s´/2とλ´sとを用いて、以下の数２０のように表現する（ステップＳ２０）。
【００６７】
【数２０】
2018205511.tif 000022
次に、簡約化部１０４は、i=s´/2+1のときのλiをγ=ci/Tを用いて、以下の数２１のように表現する（ステップＳ２１）。
【００６８】
【数２１】
2018205511.tif 000023
次に、簡約化部１０４は、i=0のときのλ´iを整数η及びζを用いて、以下の数２２のように表現する（ステップＳ２２）。
【００６９】
【数２２】
2018205511.tif 000024
ここで、η及びζは、以下の数２３に示す連立方程式の解となる整数である。
【００７０】
【数２３】
2018205511.tif 000025
以上により、最終べきを計算するためのパラメータλiが、λ´iを用いて以下の数２４のように簡約化するこができる。すなわち、1≦i≦s´/2及びs´/2+2≦i≦s´におけるλiを、λ´s´/2とλ´sとの線形和で表現することで簡約化することができる。
【００７１】
【数２４】
2018205511.tif 000026
以上のように、本発明の実施の形態におけるペアリング演算装置１０は、KSS曲線一般に対して、最終べきを計算するためのパラメータλiを簡約化することができる。このため、本発明の実施の形態におけるペアリング演算装置１０は、KSS曲線一般に対して、上記の数１２に示すhard partの計算コストを削減させることができる。
【００７２】
したがって、本発明の実施の形態におけるペアリング演算装置１０によれば、KSS曲線一般に対して、最終べきにおけるhard partの計算を効率化させることができ、ペアリング演算を効率的に行うことができるようになる。
【００７３】
＜実施例及び効果＞
次に、KSS曲線として、埋め込み次数k=36の場合における実施列及び効果について説明する。埋め込み次数k=36のときのKSS曲線の入力パラメータは、以下の数２５に示す通りであることが知られている。
【００７４】
【数２５】
2018205511.tif 000027
また、このとき、deg(p(x))、φ(k)及びsは、以下の数２６に示す通りである。
【００７５】
【数２６】
2018205511.tif 000028
このとき、上記の数７に示す最終べきの指数部分の分解は、以下の数２７に示す通りとなる。
【００７６】
【数２７】
2018205511.tif 000029
hard partは、c=111として、
【００７７】
【数２８】
2018205511.tif 000030
とした場合、各λiは、以下の数２９に示す通りである。
【００７８】
【数２９】
2018205511.tif 000031
このとき、上記の数２９に示すλiを簡約化部１０４により簡約化すると、以下の数３０に示す通りとなる。
【００７９】
【数３０】
2018205511.tif 000032
全てのiに対して、
【００８０】
【数３１】
2018205511.tif 000033
を計算するためには、簡約化する前は約１０００ビット分に相当するべき乗計算が必要であったが、簡約化することで約２００ビット分に相当するべき乗計算に削減することができる。このため、ペアリング演算の計算時間を削減することができる。このように、本発明では、例えば、k=16より高い埋め込み次数k=36を持つKSS曲線でも簡約化することができる。
【００８１】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【００８２】
１０        ペアリング演算装置
１０１      入力部
１０２      Miller Loop計算部
１０３      最終べき計算部
１０４      簡約化部
１０５      出力部
【図１】
2018205511.tif 000034
【図２】
2018205511.tif 000035
【図３】
2018205511.tif 000036
【図４】
2018205511.tif 000037