(57)【要約】【課題】効率的にペアリングを演算する。【解決手段】ECDBL演算部３は、アルゴリズムECDBLを演算し、点(X1, Y1, Z1)を楕円曲線E上で二倍算した点(X3, Y3, Z3)および値Λn, λdを得る。DBL演算部４は、L←yPZ12Z3+(-xPΛnZ12+(ΛnX1-Y1λd)), f←f2・Lを演算する。ECADD演算部５は、アルゴリズムECADDを演算し、点(X1, Y1, Z1)と点(XQ, YQ, 1)とを楕円曲線E上で加算した点(X3, Y3, Z3)および値Λn, λdを得る。ADD演算部６は、L←yPZ3+(-xPΛn+(ΛnXQ-YQZ3)), f←f・Lを演算する。最終冪演算部７は、f(p^k-1)/rを演算する。【選択図】図１
2018146903.tif 000002
【特許請求の範囲】
【請求項１】
p, rを素数とし、kを埋め込み次数とし、dを正の整数とし、Eを楕円曲線とし、Fpを位数pの有限体とし、Fp^(k/d)を位数pk/dの有限体とし、Fp^kを位数pkの有限体とし、G1を楕円曲線E(Fp)上の位数rの部分群とし、G2を楕円曲線E(Fp^(k/d))上の位数rの部分群とし、G3を有限体Fp^k上の位数rの部分群とし、eをG1×G2→G3のペアリングとし、
ECDBLを楕円曲線上の一点を入力とし、当該点を楕円曲線上で二倍算した点、および、値Λn∈Fp^(k/d), λd∈Fpを出力とする、Compressed Jacobian座標系を用いて楕円曲線上の二倍算を演算するアルゴリズムとし、
ECADDを楕円曲線上の二点を入力とし、当該二点を楕円曲線上で加算した点、および、値Λn∈Fp^(k/d), λd∈Fpを出力とする、Compressed Jacobian座標系を用いて楕円曲線上の加算を演算するアルゴリズムとし、
楕円曲線E(Fp)上の点P=(xP, yP)と楕円曲線E(Fp^(k/d))上の点Q=(XQ, YQ)とのペアリングe(P, Q)を演算するペアリング演算装置であって、
値fに1を、点(X1, Y1, Z1)に点(XQ, YQ, 1)を代入する初期化部と、
点(X1, Y1, Z1)を入力として上記アルゴリズムECDBLを演算し、点(X1, Y1, Z1)を楕円曲線E上で二倍算した点(X3, Y3, Z3)および上記値Λn, λdを得る楕円二倍算部と、
上記値f, Λn, λd, Z3, 点(xP, yP), (X1, Y1, Z1)を用いて、L←yPZ12Z3+(-xPΛnZ12+(ΛnX1-Y1λd)), f←f2・Lを演算し、点(X3, Y3, Z3)を点(X1, Y1, Z1)に代入する二倍算部と、
点(X1, Y1, Z1), (XQ, YQ, 1)を入力として上記アルゴリズムECADDを演算し、点(X1, Y1, Z1)と点(XQ, YQ, 1)とを楕円曲線E上で加算した点(X3, Y3, Z3)および上記値Λn, λdを得る楕円加算部と、
上記値f, Λn, Z3, 点(xP, yP), (XQ, YQ, 1)を用いて、L←yPZ3+(-xPΛn+(ΛnXQ-YQZ3)), f←f・Lを演算し、点(X3, Y3, Z3)を点(X1, Y1, Z1)に代入する加算部と、
f(p^k-1)/rを演算する最終冪演算部と、
を含むペアリング演算装置。
【請求項２】
p, rを素数とし、kを埋め込み次数とし、dを正の整数とし、Eを楕円曲線とし、Fpを位数pの有限体とし、Fp^(k/d)を位数pk/dの有限体とし、Fp^kを位数pkの有限体とし、G1を楕円曲線E(Fp)上の位数rの部分群とし、G2を楕円曲線E(Fp^(k/d))上の位数rの部分群とし、G3を有限体Fp^k上の位数rの部分群とし、eをG1×G2→G3のペアリングとし、
ECDBLを楕円曲線上の一点を入力とし、当該点を楕円曲線上で二倍算した点、および、楕円曲線上の二倍算を演算する過程で計算される値Λn∈Fp^(k/d), λd∈Fpを出力とする、Compressed Jacobian座標系を用いて楕円曲線上の二倍算を演算するアルゴリズムとし、
ECADDを楕円曲線上の二点を入力とし、当該二点を楕円曲線上で加算した点、および、楕円曲線上の加算を演算する過程で計算される値Λn∈Fp^(k/d), λd∈Fpを出力とする、Compressed Jacobian座標系を用いて楕円曲線上の加算を演算するアルゴリズムとし、
初期化部と楕円二倍算部と二倍算部と楕円加算部と加算部と最終冪演算部とを含むペアリング演算装置が、楕円曲線E(Fp)上の点P=(xP, yP)と楕円曲線E(Fp^(k/d))上の点Q=(XQ, YQ)とのペアリングe(P, Q)を演算するペアリング演算方法であって、
初期化部が、値fに1を、点(X1, Y1, Z1)に点(XQ, YQ, 1)を代入し、
楕円二倍算部が、点(X1, Y1, Z1)を入力として上記アルゴリズムECDBLを演算し、点(X1, Y1, Z1)を楕円曲線E上で二倍算した点(X3, Y3, Z3)および上記値Λn, λdを得、
二倍算部が、上記値f, Λn, λd, Z3, 点(xP, yP), (X1, Y1, Z1)を用いて、L←yPZ12Z3+(-xPΛnZ12+(ΛnX1-Y1λd)), f←f2・Lを演算し、点(X3, Y3, Z3)を点(X1, Y1, Z1)に代入し、
楕円加算部が、点(X1, Y1, Z1), (XQ, YQ, 1)を入力として上記アルゴリズムECADDを演算し、点(X1, Y1, Z1)と点(XQ, YQ, 1)とを楕円曲線E上で加算した点(X3, Y3, Z3)および上記値Λn, λdを得、
加算部が、上記値f, Λn, Z3, 点(xP, yP), (XQ, YQ, 1)を用いて、L←yPZ3+(-xPΛn+(ΛnXQ-YQZ3)), f←f・Lを演算し、点(X3, Y3, Z3)を点(X1, Y1, Z1)に代入し、
最終冪演算部が、f(p^k-1)/rを演算する、
ペアリング演算方法。
【請求項３】
請求項１に記載のペアリング演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報通信分野におけるペアリングを用いた暗号技術に関し、特に、ペアリングを効率的に演算する技術に関する。
【背景技術】
【０００２】
近年、楕円曲線上のペアリングが持つ双線形性によって、IDベース暗号（非特許文献１参照）や属性ベース暗号（非特許文献２参照）、関数型暗号（非特許文献３参照）などの高機能な暗号方式が提案されている。このようなペアリングを用いた暗号方式は、ペアリング暗号とも呼ばれる。近年では、Apache Milagro (incubating)（非特許文献４参照）でのオープンソースソフトウェア（OSS: Open Source Software）による開発や、インターネット技術タスクフォース（IETF: Internet Engineering Task Force）による標準化（非特許文献５、６参照）など、ペアリング暗号を実社会で利用するための活動が行われている。
【０００３】
楕円曲線上のペアリングは、Millerによって提案されたミラーアルゴリズム（Miller's Algorithm、非特許文献７参照）を用いて演算することができる。ミラーアルゴリズムでは、楕円曲線上の二点を通る直線または一点を通る接線であるＬ関数を構成する必要がある。Ｌ関数を構成する方法としては、Affine座標系／Jacobian座標系を用いた楕円曲線上の二倍算／加算において、演算途中で計算される傾きを用いて構成する方法が知られている（非特許文献８参照）。Affine座標系では逆元算を用い、Jacobian座標系では逆元算を用いないことが特徴であるため、計算機の乗算と逆元算の演算時間の比に応じて、これらの座標系を使い分ける。Affine座標系／Jacobian座標系以外の座標系には、Compressed Jacobian座標系（非特許文献９参照）があるが、この座標系を用いてＬ関数を構成する方法は知られていない。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D. Boneh and M. Franklin, "Identity-Based Encryption from the Weil Pairing", CRYPTO 2001, LNCS 2139, pp. 213-229, 2001.
【非特許文献２】A. Sahai and B. Waters, "Identity-Based Encryption", EUROCRYPT 2005, LNCS 3494, pp. 457-473, 2005.
【非特許文献３】T. Okamoto and K. Takashima, "Fully secure functional encryption with general relations from the decisional linear assumption", CRYPTO 2010, LNCS 6223, pp. 191-208, 2010.
【非特許文献４】Apache Software Foundation、"MILAGRO"、［online］、［平成29年2月22日検索］、インターネット<URL: https://milagro.apache.org/>
【非特許文献５】RFC5091, "Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems", 2007.
【非特許文献６】RFC6508, "Sakai-Kasahara Key Encryption (SAKKE)", 2012.
【非特許文献７】V. S. Miller, "The Weil Pairing, and Its Efficient Calculation", Journal of Cryptology, vol. 17, pp. 235-261, 2004.
【非特許文献８】S. Chatterjee, P. Sarkar and R. Barua, "Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields", ICISC 2004, LNCS 3506, pp. 168-181, 2005.
【非特許文献９】F. Hoshino, T. Kobayashi and K. Aoki, "Compressed Jacobian Coordinates for OEF", VIETCRYPT 2006, LNCS 4341, pp. 147-156, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ペアリング暗号を実際のシステムとして実現するためには、ペアリング演算を効率的に行うことが重要である。計算機の性能によっては、Compressed Jacobian座標系を用いた楕円曲線上の二倍算／加算が他の座標系よりも高速に演算できる場合がある。しかしながら、Compressed Jacobian座標系を用いてペアリング演算に必要なＬ関数を構成する方法は知られていなかった。
【０００６】
この発明の目的は、上記のような点に鑑みて、Compressed Jacobian座標系を用いてペアリング演算に必要なＬ関数を構成し、効率的にペアリングを演算することができる技術を実現することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明のペアリング演算装置は、p, rを素数とし、kを埋め込み次数とし、dを正の整数とし、Eを楕円曲線とし、Fpを位数pの有限体とし、Fp^(k/d)を位数pk/dの有限体とし、Fp^kを位数pkの有限体とし、G1を楕円曲線E(Fp)上の位数rの部分群とし、G2を楕円曲線E(Fp^(k/d))上の位数rの部分群とし、G3を有限体Fp^k上の位数rの部分群とし、eをG1×G2→G3のペアリングとし、ECDBLを楕円曲線上の一点を入力とし、当該点を楕円曲線上で二倍算した点、および、楕円曲線上の二倍算を演算する過程で計算される値Λn∈Fp^(k/d), λd∈Fpを出力とする、Compressed Jacobian座標系を用いて楕円曲線上の二倍算を演算するアルゴリズムとし、ECADDを楕円曲線上の二点を入力とし、当該二点を楕円曲線上で加算した点、および、楕円曲線上の加算を演算する過程で計算される値Λn∈Fp^(k/d), λd∈Fpを出力とする、Compressed Jacobian座標系を用いて楕円曲線上の加算を演算するアルゴリズムとし、楕円曲線E(Fp)上の点P=(xP, yP)と楕円曲線E(Fp^(k/d))上の点Q=(XQ, YQ)とのペアリングe(P, Q)を演算するペアリング演算装置であって、値fに1を、点(X1, Y1, Z1)に点(XQ, YQ, 1)を代入する初期化部と、点(X1, Y1, Z1)を入力としてアルゴリズムECDBLを演算し、点(X1, Y1, Z1)を楕円曲線E上で二倍算した点(X3, Y3, Z3)および値Λn, λdを得る楕円二倍算部と、値f, Λn, λd, Z3, 点(xP, yP), (X1, Y1, Z1)を用いて、L←yPZ12Z3+(-xPΛnZ12+(ΛnX1-Y1λd)), f←f2・Lを演算し、点(X3, Y3, Z3)を点(X1, Y1, Z1)に代入する二倍算部と、点(X1, Y1, Z1), (XQ, YQ, 1)を入力としてアルゴリズムECADDを演算し、点(X1, Y1, Z1)と点(XQ, YQ, 1)とを楕円曲線E上で加算した点(X3, Y3, Z3)および上記値Λn, λdを得る楕円加算部と、値f, Λn, Z3, 点(xP, yP), (XQ, YQ, 1)を用いて、L←yPZ3+(-xPΛn+(ΛnXQ-YQZ3)), f←f・Lを演算し、点(X3, Y3, Z3)を点(X1, Y1, Z1)に代入する加算部と、f(p^k-1)/rを演算する最終冪演算部と、を含む。
【発明の効果】
【０００８】
この発明によれば、Compressed Jacobian座標系を用いてペアリング演算に必要なＬ関数を構成し、効率的にペアリングを演算することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、ペアリング演算装置の機能構成を例示する図である。
【図２】図２は、ペアリング演算方法の処理手続きを例示する図である。
【発明を実施するための形態】
【００１０】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１１】
本明細書中で使用する、上付き添え字または下付き添え字の中で使用する記号「^」は、直後の文字を上付き添え字とすることを表す。例えば、f(p^k-1)/rは、fを(pk-1)/r乗することを表している。数式中においてはこれらの記号は本来の記法、すなわち上付き添え字の中での上付き添え字で記述する。例えば、f(p^k-1)/rは、次式のように記述する。
【００１２】
【数１】
2018146903.tif 000003
【００１３】
［準備］
実施形態の説明の前に、本明細書で用いる用語の概要を説明する。
【００１４】
＜ペアリング＞
p, rを素数とする。kを埋め込み次数とする。dを正の整数とする。Eを楕円曲線とする。Fpを位数pの有限体とする。Fp^(k/d)を位数pk/dの有限体とする。Fp^kを位数pkの有限体とする。G1を楕円曲線E(Fp)上の位数rの部分群とする。G2を楕円曲線E(Fp^(k/d))上の位数rの部分群とする。G3を有限体Fp^k上の位数rの部分群とする。fr,Qを有理関数とする。
【００１５】
群G1, G2, G3に対して、ペアリングeを次のように定義する。
【００１６】
【数２】
2018146903.tif 000004
【００１７】
＜ミラーアルゴリズム＞
上記の有理関数fr,Qは、上記非特許文献７に記載されているミラーアルゴリズムを用いて演算することができる。ミラーアルゴリズムをAlgorithm 1に示す。
【００１８】
【数３】
2018146903.tif 000005
【００１９】
ミラーアルゴリズムのステップ３では、楕円曲線上の二倍算を演算する。ミラーアルゴリズムのステップ７では、楕円曲線上の加算を演算する。上述のとおり、楕円曲線上の演算を行う座標系には、Affine座標系、Jacobian座標系、Compressed Jacobian座標系の３つが知られている。以下、各座標系について説明する。なお、mはある正の整数である。
【００２０】
＜Affine座標系＞
Affine座標系は、下記参考文献１の79-82ページに詳しく記載されている。有限体Fp^m上で定義されるAffine座標系における楕円曲線EAは、4a3+27b2≠0を満たすa, b∈Fp^mに対して、式（１）のとおり表現できる。
【００２１】
【数４】
2018146903.tif 000006
【００２２】
楕円曲線EA上の点は、(x, y)∈Fp^m×Fp^mと表現できる。Affine座標系では、この表現を用いて楕円曲線EA上の二倍算／加算を行う。
【００２３】
〔参考文献１〕D. R. Hankerson, A. J. Menezes and S. A. Vanstone, "Guide to Elliptic Curve Cryptography", Springer, 2004.
【００２４】
＜Jacobian座標系＞
Jacobian座標系は、上記参考文献１の86-89ページに詳しく記載されている。有限体Fp^m上で定義されるJacobian座標系における楕円曲線EJは、X∈Fp^m, Y∈Fp^m, Z∈Fp^mに対して、上記式（１）を(x, y)=(X/Z2, Y/Z3)と置き換えることで、式（２）のとおり表現できる。
【００２５】
【数５】
2018146903.tif 000007
【００２６】
楕円曲線EJ上の点は、(X, Y, Z)∈Fp^m×Fp^m×Fp^mと表現できる。Jacobian座標系では、この表現を用いて楕円曲線EJ上の二倍算／加算を行う。
【００２７】
＜Compressed Jacobian座標系＞
Compressed Jacobian座標系は、上記非特許文献９に詳しく記載されている。有限体Fp^m上で定義されるCompressed Jacobian座標系における楕円曲線EcomJは、X∈Fp^m, Y∈Fp^m, z∈Fpに対して、上記式（１）を(x, y)=(X/z2, Y/z3)と置き換えることで、式（３）のとおり表現できる。
【００２８】
【数６】
2018146903.tif 000008
【００２９】
楕円曲線EcomJ上の点は、(X, Y, z)∈Fp^m×Fp^m×Fpと表現できる。Compressed Jacobian座標系では、この表現を用いて楕円曲線EcomJ上の二倍算／加算を行う。
【００３０】
＜Ｌ関数＞
ミラーアルゴリズムのステップ４およびステップ８で用いられるＬ関数（LT,T(P), LT,Q(P)）は、P=(xP, yP)∈G1, T=(xT, yT)∈G2, T'=(xT', yT')∈G2を通る直線の傾きλ∈Fp^mに対して、式（４）のとおり表現できる。
【００３１】
【数７】
2018146903.tif 000009
【００３２】
Ｌ関数を演算するためには、ミラーアルゴリズムのステップ３およびステップ７で楕円曲線上の二倍算／加算を演算する中で計算される値λを用いる。Affine座標系、Jacobian座標系を用いた効率的なＬ関数の構成方法は知られているが、Compressed Jacobian座標系を用いた効率的なＬ関数の構成方法は知られていない。
【００３３】
＜本発明によるミラーアルゴリズム＞
本発明によるCompressed Jacobian座標系を用いる楕円曲線上の二倍算／加算を用いたミラーアルゴリズムをAlgorithm 2に示す。
【００３４】
【数８】
2018146903.tif 000010
【００３５】
ステップ３で実行するECDBLは、非特許文献９において提案されている、Compressed Jacobian座標系を用いて楕円曲線上の二倍算を演算するアルゴリズムである。アルゴリズムECDBLは、楕円曲線E上の一点を入力とし、当該点を楕円曲線E上で二倍した点、および、楕円曲線E上の二倍算を演算する過程で計算される値Λn∈Fp^(k/d), λd∈Fpを出力する。
【００３６】
ステップ７で実行するECADDは、非特許文献９において提案されている、Compressed Jacobian座標系を用いて楕円曲線上の加算を演算するアルゴリズムである。アルゴリズムECADDは、楕円曲線E上の二点を入力とし、当該二点を楕円曲線E上で加算した点、および、楕円曲線E上の加算を演算する過程で計算される値Λn∈Fp^(k/d), λd∈Fpを出力する。
【００３７】
ステップ４で実行するDBLは、値fと、ECDBLの出力する値Λn, λdと、点P(xP, yP), 点(X1, Y1, Z1)と、点(X3, Y3, Z3)のZ座標である値Z3とを入力とし、更新された値fを出力する。アルゴリズムDBLをAlgorithm 3に示す。
【００３８】
【数９】
2018146903.tif 000011
【００３９】
ステップ８で実行するADDは、値fと、ECADDの出力する値Λnと、点P(xP, yP), 点(XQ, YQ, 1)と、点(X3, Y3, Z3)のZ座標である値Z3とを入力とし、更新された値fを出力する。アルゴリズムADDをAlgorithm 4に示す。
【００４０】
【数１０】
2018146903.tif 000012
【００４１】
［実施形態］
実施形態のペアリング演算装置１０は、図１に示すように、入力部１、初期化部２、ECDBL演算部３（楕円二倍算部とも呼ぶ）、DBL演算部４（二倍算部とも呼ぶ）、ECADD演算部５（楕円加算部とも呼ぶ）、ADD演算部６（加算部とも呼ぶ）、最終冪演算部７、および出力部８を備える。このペアリング演算装置１０が後述する各ステップの処理を行うことにより実施形態のペアリング演算方法が実現される。
【００４２】
ペアリング演算装置１０は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。ペアリング演算装置１０は、例えば、中央演算処理装置の制御のもとで各処理を実行する。ペアリング演算装置１０に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。また、ペアリング演算装置１０の各処理部の少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００４３】
図２を参照して、実施形態のペアリング演算方法の処理手続きを説明する。
【００４４】
ステップＳ１において、入力部１へ楕円曲線E上の二点P=(xP, yP)∈G1, Q=(XQ, YQ)∈G2、および群G1, G2の位数である素数rが入力される。なお、位数rは、式（５）に示すように、二進表現で入力されるものとする。
【００４５】
【数１１】
2018146903.tif 000013
【００４６】
ステップＳ２において、初期化部２は、値fに1を代入し、Compressed Jacobian座標系の点(X1, Y1, Z1)に点(XQ, YQ, 1)を代入する。また、インデックスjをn-2に初期化する。nは、式（５）に示すとおり、位数rを二進表現とした際の桁数である。
【００４７】
ステップＳ３において、ECDBL演算部３は、点(X1, Y1, Z1)を入力としてアルゴリズムECDBLを演算し、点(X1, Y1, Z1)を楕円曲線E上で二倍算した点(X3, Y3, Z3)、および、楕円曲線上の二倍算を演算する過程で計算される値Λn, λdを得る。
【００４８】
ステップＳ４において、DBL演算部４は、値f, Λn, λd, 点P(xP, yP), (X1, Y1, Z1), および点(X3, Y3, Z3)のZ座標である値Z3を入力としてアルゴリズムDBLを演算し、値fを更新する。また、DBL演算部４は、点(X3, Y3, Z3)を点(X1, Y1, Z1)に代入する。
【００４９】
ステップＳ５において、rjが1と等しいか否かを判定する。rj=1の場合（YES）、ステップＳ６、Ｓ７を実行する。rj≠1の場合（NO）、ステップＳ６、Ｓ７を実行せず、ステップＳ８へ処理を進める。
【００５０】
ステップＳ６において、ECADD演算部５は、点(X1, Y1, Z1), (XQ, YQ, 1)を入力としてアルゴリズムECADDを演算し、点(X1, Y1, Z1)と点(XQ, YQ, 1)とを楕円曲線E上で加算した点(X3, Y3, Z3)、および、楕円曲線上の加算を演算する過程で計算される値Λn, λdを得る。
【００５１】
ステップＳ７において、ADD演算部６は、値f, Λn, 点P(xP, yP), (XQ, YQ, 1), および点(X3, Y3, Z3)のZ座標である値Z3を入力としてアルゴリズムADDを演算し、値fを更新する。また、ADD演算部６は、点(X3, Y3, Z3)を点(X1, Y1, Z1)に代入する。
【００５２】
ステップＳ８において、インデックスjが0を超えているか否かを判定する。j>0の場合（YES）、ステップＳ９においてj←j-1を計算し、すなわち、インデックスjをデクリメントし、ステップＳ３〜Ｓ８の処理を再度実行する。j≦0の場合（NO）、ステップＳ１０へ処理を進める。
【００５３】
ステップＳ１０において、最終冪演算部７は、式（６）を計算し、ペアリング演算結果e(P, Q)を得る。
【００５４】
【数１２】
2018146903.tif 000014
【００５５】
ステップＳ１１において、出力部８は、ペアリング演算結果e(P, Q)を出力する。
【００５６】
［実験結果］
本発明の効果を実証するために、従来のミラーアルゴリズム（Algorithm 1）を用いたときの演算コストと、本発明によるミラーアルゴリズム（Algorithm 2）を用いたときの演算コストを比較した。以下では、Mを乗算の演算時間、Sを二倍算の演算時間、Iを逆元算の演算時間として、S=M, I=8Mとなる計算機を用いて、下記参考文献２に記載されたパラメータを用いてペアリングを演算する場合の高速化率を説明する。
【００５７】
〔参考文献２〕D. Aranha, K. Karabina, P. Longa, C. Gebotys and J. Lopez, "Faster Explicit Formulas for Computing Pairings over Ordinary Curves," EUROCRYPT 2011, LNCS 6632, pp. 48-68, 2011.
【００５８】
参考文献２に記載されたパラメータは、以下のとおりである。
【００５９】
【数１３】
2018146903.tif 000015
【００６０】
このとき、ω=|6z+2|とし、ある関数gに対するペアリングは、以下のように表される。
【００６１】
【数１４】
2018146903.tif 000016
【００６２】
なお、上述のミラーアルゴリズムではrを入力としてrを二進表現とした際の桁数だけループしていたが、この実験ではループ回数をωに削減する一般的なテクニックを用いた。このテクニックは従来のミラーアルゴリズムでも本発明のミラーアルゴリズムでも同様に適用できるため、実験結果へは影響しない。
【００６３】
Jacobian座標系で従来のミラーアルゴリズム（Algorithm 1）を用いてfω,Q(P)を演算すると、7164Mの演算時間が必要であった（Mは乗算一回の演算時間）。本発明によるミラーアルゴリズム（Algorithm 2）を用いてfω,Q(P)を演算すると、6940Mの演算時間が必要であった。したがって、本発明によるミラーアルゴリズムを用いると、演算時間を3.2％削減できることがわかった。
【００６４】
以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６５】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００６６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６７】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７０】
１０  ペアリング演算装置
１  入力部
２  初期化部
３  ECDBL演算部
４  DBL演算部
５  ECADD演算部
６  ADD演算部
７  最終冪演算部
８  出力部
【図１】
2018146903.tif 000017
【図２】
2018146903.tif 000018