(57)【要約】【課題】大きい標数の拡大体上での対称ペアリングを高速に演算する。【解決手段】pは6を法として5と合同な素数であり、nは1以上の整数であり、q=p2nであり、bは有限体Fqの元であり、Ebは有限体Fq上の一次項の係数が0であり定数項がbである楕円曲線であり、P:=(xP,yP),Q:=(xQ,yQ)は楕円曲線Eb上の点であり、点P,Qのx,y座標xP,yP,xQ,yQはいずれも有限体Fqの元であり、r’は点P,Qの位数であり、uは有限体Fq^3の元であり、u6=b-(p-1)であり、ιは点(x,y)を点(u2xp,u3yp)へ移す写像である。ペアリング演算装置１は、点Qを写像ιにより点Q’へ移し、xP2+xPxQ’+xQ’2を計算しながら、値fを求めるMiller演算部１２と、値fの(q3-1)/r’乗を計算して値e(P,Q)を出力するべき乗演算部１３とを有する。【選択図】図１
2014164176.tif 000002
【特許請求の範囲】
【請求項１】
^はべき乗を表し、x・は点・のx座標であり、y・は点・のy座標であり、F・は・を位数とする有限体であり、pは6を法として5と合同な素数であり、nは1以上の整数であり、q=p2nであり、bは有限体Fqの元であり、Ebは有限体Fq上の一次項の係数が0であり定数項がbである楕円曲線であり、P:=(xP,yP),Q:=(xQ,yQ)は楕円曲線Eb上の点であり、点P,Qのx,y座標xP,yP,xQ,yQはいずれも有限体Fqの元であり、r’は点P,Qの位数であり、uは有限体Fq^3の元であり、u6=b-(p-1)であり、ιは点(x,y)を点(u2xp,u3yp)へ移す写像であり、
前記点Qを前記写像ιにより点Q’へ移し、xP2+xPxQ’+xQ’2を計算しながら、値fを求めるMiller演算部と、
前記値fの(q3-1)/r’乗を計算して値e(P,Q)を出力するべき乗演算部と、
を有するペアリング演算装置。
【請求項２】
請求項１に記載のペアリング演算装置であって、
rは前記楕円曲線Ebの有理点のなす群の群位数であり、cは1以上の整数であり、r=cr’であり、
前記べき乗演算部は、(q3-1)/r’を(p2n-1)とpのべき乗の加減算で表される項とcとの乗算に変形し、前記値e(P,Q)を計算する
ことを特徴とするペアリング演算装置。
【請求項３】
請求項１または２に記載のペアリング演算装置であって、
ψ・は・乗フロベニウス写像であり、rは前記楕円曲線Ebの有理点のなす群の群位数であり、cは1以上の整数であり、r=cr’であり、
前記べき乗演算部は、次式により前記値e(P,Q)を計算する
【数１２】
2014164176.tif 000015
ことを特徴とするペアリング演算装置。
【請求項４】
請求項１から３のいずれかに記載のペアリング演算装置であって、
tはトレースであり、T=t-1であり、LはTのビット長であり、
前記Miller演算部は、前記点Qを前記写像ιにより点Q’へ移し、点Vに前記点Pを代入し、前記値fに1を代入し、前記Tを二進展開して値s0,…,sL-1を求め、i=L-2とし、点Vの接線に点Q’を代入した値をgとし、xP2+xPxQ’+xQ’2をhとし、f2・g・hを計算して前記値fを更新し、si=1ならば、前記点Vと前記点Pを通る直線に前記Q’を代入した値で前記gを更新し、前記点Vに前記点Pを加えて前記点Vを更新し、xP2+xPxQ’+xQ’2を計算して前記hを更新し、f・g・hを計算して前記値fを更新し、i-1を計算して前記iを更新し、i<0であれば前記値fを出力する
ことを特徴とするペアリング演算装置。
【請求項５】
請求項１から３のいずれかに記載のペアリング演算装置であって、
Kは前記位数r’のビット長であり、
前記Miller演算部は、前記点Qを前記写像ιにより点Q’へ移し、点Vに前記点Pを代入し、前記値fに1を代入し、前記位数r’を二進展開して値s0,…,sK-1を求め、i=K-2とし、点Vの接線に点Q’を代入した値をgとし、xP2+xPxQ’+xQ’2をhとし、f2・g・hを計算して前記値fを更新し、si=1ならば、前記点Vと前記点Pを通る直線に前記Q’を代入した値で前記gを更新し、前記点Vに前記点Pを加えて前記点Vを更新し、xP2+xPxQ’+xQ’2を計算して前記hを更新し、f・g・hを計算して前記値fを更新し、i-1を計算して前記iを更新し、i<0であれば前記値fを出力する
ことを特徴とするペアリング演算装置。
【請求項６】
^はべき乗を表し、x・は点・のx座標であり、y・は点・のy座標であり、F・は・を位数とする有限体であり、pは6を法として5と合同な素数であり、nは1以上の整数であり、q=p2nであり、bは有限体Fqの元であり、Ebは有限体Fq上の一次項の係数が0であり定数項がbである楕円曲線であり、P:=(xP,yP),Q:=(xQ,yQ)は楕円曲線Eb上の点であり、点P,Qのx,y座標xP,yP,xQ,yQはいずれも有限体Fqの元であり、r’は点P,Qの位数であり、uは有限体Fq^3の元であり、u6=b-(p-1)であり、ιは点(x,y)を点(u2xp,u3yp)へ移す写像であり、
Miller演算部が、前記点Qを前記写像ιにより点Q’へ移し、xP2+xPxQ’+xQ’2を計算しながら、値fを求めるMiller演算ステップと、
べき乗演算部が、前記値fの(q3-1)/r’乗を計算して値e(P,Q)を出力するべき乗演算ステップと、
を含むペアリング演算方法。
【請求項７】
請求項１から５のいずれかに記載のペアリング演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関し、特に、ペアリング暗号を実現するペアリング演算技術に関する。
【背景技術】
【０００２】
従来からペアリングと呼ばれる双線形写像を用いた公開鍵暗号技術が提案されている。このような暗号方式はペアリング暗号と呼ばれる。
【０００３】
暗号分野で用いられる双線形写像は、ある種の楕円曲線上の二点に定義されるペアリング演算を行うための関数である。G1,G2,GTを群、Frは素数rを位数とする有限体として、G1×G2→GTの双線形写像eは以下の性質を満たす。
＜双線型性＞任意のg∈G1,h∈G2および任意のa,b∈Frに対して、e(ag,bh)=e(g,h)abが成立する。
＜非退化性＞任意のg∈G1に対しe(g,y)=1Tであればy=12、同様に任意のh∈G2に対しe(x,h)=1Tであればx=11である。ここで、11,12,1TはそれぞれG1,G2,GTの単位元である。
＜計算可能性＞任意のg∈G1,h∈G2に対して、e(g,h)を多項式時間で計算可能である。
【０００４】
特にG1=G2の時のペアリングを対称ペアリングと呼ぶ。
【０００５】
双線形写像の具体例としては、例えば、Weilペアリング、Tateペアリング、ηTペアリング、Ateペアリングなどが提案されている。
【０００６】
超特異楕円曲線（supersingular楕円曲線）で定義体の標数が2または3の場合に、ηTペアリングあるいはAteペアリングを用いて対称ペアリングを高速に計算できることが知られている。ηTペアリングについての詳細は非特許文献１に記載されている。Ateペアリングについての詳細は非特許文献２に記載されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】P.S.L.M. Barreto, S. Galbraith, C. OhEigeartaigh, and M. Scott, “Efficient pairing computation on supersingular abelian varieties”, Designs, Codes and Cryptography, Vol. 42, No. 3, pp. 239-271, Springer, 2007.
【非特許文献２】F. Hess, N.P. Smart, and F. Vercauteren, “The Eta pairing revisited”, IEEE Transaction on Information Theory, Vol. 52, No. 10, pp. 4595-4602, October 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
標数が2や3の有限体を用いたペアリング暗号については、有限体上の離散対数問題の困難性がやや弱いことが以前から指摘されている。そのため、大きい標数pの有限体上の楕円曲線を用いた対称ペアリングの必要性が高まっている。
【０００９】
この発明の目的は、大きい標数の拡大体上での対称ペアリングを高速に演算することができるペアリング演算技術を提供することである。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、この発明のペアリング演算装置はMiller演算部とべき乗演算部とを有する。
【００１１】
この発明では、^はべき乗を表し、x・は点・のx座標であり、y・は点・のy座標であり、F・は・を位数とする有限体であり、pは6を法として5と合同な素数であり、nは1以上の整数であり、q=p2nであり、bは有限体Fqの元であり、Ebは有限体Fq上の一次項の係数が0であり定数項がbである楕円曲線であり、P:=(xP,yP),Q:=(xQ,yQ)は楕円曲線Eb上の点であり、点P,Qのx,y座標xP,yP,xQ,yQはいずれも有限体Fqの元であり、r’は点P,Qの位数であり、uは有限体Fq^3の元であり、u6=b-(p-1)であり、ιは点(x,y)を点(u2xp,u3yp)へ移す写像である。
【００１２】
Miller演算部は、点Qを写像ιにより点Q’へ移し、xP2+xPxQ’+xQ’2を計算しながら、値fを求める。べき乗演算部は、値fの(q3-1)/r’乗を計算して値e(P,Q)を出力する。
【発明の効果】
【００１３】
この発明のペアリング演算技術によれば、大きい標数の拡大体上での対称ペアリングを高速に演算することができる
【図面の簡単な説明】
【００１４】
【図１】ペアリング演算装置の機能構成を例示する図。
【図２】Millerのアルゴリズムの処理フローを例示する図。
【図３】最終べき乗の処理フローを例示する図。
【発明を実施するための形態】
【００１５】
実施形態の説明に先立って、この明細書で用いる表記方法およびこの発明の基本的な考え方を説明する。
【００１６】
［表記方法］
上付き添字はべき乗を表す。例えば、abはaのb乗である。
【００１７】
^はべき乗を表す。例えば、a^bはaのb乗である。
【００１８】
|・|は絶対値記号である。
【００１９】
x・は点・のx座標である。y・は点・のy座標である。例えば、点Pのx座標はxPであり、点Pのy座標はyPである。
【００２０】
F・は素数・を位数とする有限体である。例えば、Fqはqを位数とする有限体である。
【００２１】
［発明の概略］
＜基本的なアイデア＞
定義体の標数が大きい素数pの場合、超特異楕円曲線（supersingular楕円曲線）には、定義体が素体の場合と拡大体の場合の二通りがある。定義体が素体の場合はηTペアリングあるいはAteペアリングを適用できても効果が全くなく、既存方法のTateペアリングとほぼ同等の計算時間である。定義体が拡大体の場合については、今のところ報告が知られていない。
【００２２】
そこで、この発明のペアリング演算技術では大きい標数pの拡大体上の超特異楕円曲線に対する対称ペアリングを高速に計算する技術を導入する。大きい標数pの拡大体Fq上の超特異楕円曲線Eb/Fqを式(1)に示す。
【００２３】
【数１】
2014164176.tif 000003
【００２４】
一般的に楕円曲線はa,bを有限体Fq上の任意の元としてY2=X3+aX+bの形で表されるが、この発明の楕円曲線Eb/Fqは一次項の係数aが0であることが特徴である。以降の説明ではこのような形の楕円曲線をY2=X3+b型の楕円曲線と呼ぶ。
【００２５】
式(1)の楕円曲線Eb/Fq自体は、以前よりペアリングを計算しやすい楕円曲線の一つとして知られてはいたが、現在までペアリング暗号の実装に用いられていなかった。その理由としては、この楕円曲線Eb/Fqは埋込み次数と呼ばれる量が奇数3であるため、標数が2や3の有限体上での超特異楕円曲線では適用できたηTペアリングが適用できないという問題が挙げられる。また、埋込み次数が偶数である楕円曲線上のペアリング演算で用いられる分母消去という技術を用いることができないという問題もあった。しかし、後述する通り、このような楕円曲線でAteペアリングや分母消去を実現できることを発見した。
【００２６】
＜楕円曲線の特徴と設定パラメータの形＞
楕円曲線Eb/Fqは埋込み次数kの値が3である。この楕円曲線のFq有理点がなす群の群位数r、有限体の位数q、そしてトレースと呼ばれる量tの間には、式(2)に示す関係がある。
【００２７】
【数２】
2014164176.tif 000004
【００２８】
ここで、zは整数であり、特に素数または素数のべきの形である。
【００２９】
式(2)は、nを自然数として、式(3)で表わされることが知られている。
【００３０】
【数３】
2014164176.tif 000005
【００３１】
つまりzを素数とすればz2nを位数とする有限体Fz^2n上の楕円曲線Eb/Fz^2nを考えることが可能である。以後の説明では、zを標数pとする。つまりq=p2nである。
【００３２】
式(3)についての詳細は「P. Duan, S.Cui, and C.W. Chan, “Effective polynomial families for generating more pairing-friendly elliptic curve”, Cryptology ePrint Archive, Report 2005/236, 2005.（参考文献１）」を参照されたい。
【００３３】
＜適用するペアリング＞
ηTペアリングを適用するには有限体の埋込み次数kが偶数でなければならない。上述のように有限体Fq上の楕円曲線Eb/Fqは埋込み次数kが3であるためηTペアリングは適用できない。一方、Ateペアリングは埋込み次数に対する制限がないため、有限体Fq上の楕円曲線Eb/Fqに対して適用できる。また、AteペアリングはTateペアリングと比較して計算量が少なくなるためペアリング演算を高速にする効果がある。具体的には、Ateペアリングの計算量はTateペアリングの計算量の約半分と見積もられる。その理由は、ペアリングを計算する標準的なアルゴリズム「Millerのアルゴリズム」を用いたときに繰り返される特定の反復操作の回数が、rをペアリングの入出力の群の位数としてlog2(r)であるのに対し、Ateペアリングを適用したときの回数は、tをトレースと呼ばれる量としてlog2|t-1|となるからである。Millerのアルゴリズムについての詳細は「V.S. Miller, “Short programs for functions on curves”, [online], 1986, インターネット<URL:http://crypto.stanford.edu/miller/miller.pdf>（参考文献２）」または「V.S. Miller, “The Weil pairing and its efficient calculation”, Journal of Cryptology, Vol. 17, No. 4, pp. 235-261, 2004.（参考文献３）」を参照されたい。
【００３４】
また、対称ペアリングを超特異楕円曲線上で計算する際にディストーション写像（distortion map）が必要となるが、楕円曲線Ebについては以下の事実が知られている。
（補題１：ディストーション写像の存在）uをu6=b-(p-1)であり、q3を位数とする有限体Fq^3内の解とする。このとき、式(4)は楕円曲線Eb上のディストーション写像ιを与える。
【００３５】
【数４】
2014164176.tif 000006
【００３６】
なお、uは入力には依存しない量であり、楕円曲線Eb/Fqにより定まる。したがって、事前にuを計算し記憶しておくことが可能である。
【００３７】
補題１の詳細は「E. Verheul, “Evidence that XTR is more secure than supersingular elliptic curve cryptosystems”, Journal of Cryptology, Vol. 17, No. 4, pp. 277-296, 2004.（参考文献４）」を参照されたい。
【００３８】
＜適用可能な補助テクニック＞
ペアリング高速計算に有用なテクニックである「分母消去」も実現可能である。通常ペアリングの実装で用いられる楕円曲線の多くは偶数の埋込み次数を持つが、この楕円曲線Rb/Fqは埋込み次数kが3であり、通常の分母消去をそのままでは用いることができない。しかし、Y2=X3+b型の楕円曲線の特性を利用した以下の方法を用いることが可能である。計算により直ちに示される以下の補題を用いる。
（補題２）Y2=X3+b型楕円曲線に対して以下の式(5)が成り立つ。ここで、xPは点Pのx座標、yPは点Pのy座標、xQは点Qのx座標、yQは点Qのy座標を表す。
【００３９】
【数５】
2014164176.tif 000007
【００４０】
補題２の詳細は「X. Lin, C.-A. Zhao, F. Zhang and Y. Wang, “Computing the Ate Pairing on Elliptic Curves with Embedding Degree k = 9”,IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E91-A, No. 9, pp. 2387-2393, 2008.（参考文献５）」を参照されたい。
【００４１】
式(5)の右辺の分母(yP+yQ)(yP-yQ)は、後述するペアリング計算の後半ステップ「最終べき乗」を施すと1になるため、ペアリング計算の前半ステップ「Millerのアルゴリズム」を実行する際には無視することが許される。したがって、補題２を実際に適用する際には、分子のxP2+xPxQ+xQ2だけを計算すればよい。
【００４２】
［実施形態］
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００４３】
＜構成＞
図１を参照して、実施形態のペアリング演算装置１の構成例を説明する。ペアリング演算装置１は、制御部１０１、メモリ１０２、入力部１１、Miller演算部１２、べき乗演算部１３、出力部１４を有する。ペアリング演算装置１は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。ペアリング演算装置１は制御部１０１の制御のもとで各処理を実行する。ペアリング演算装置１に入力されたデータや各処理で得られたデータはメモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００４４】
＜条件＞
この実施形態では以下の条件を満たさなければならない。
・有限体の標数pは6を法として5と合同な素数でなければならない。
・楕円曲線の式はE/b:Y2=X3+b型で、bは有限体Fp^2nの元でなければならない。
・ペアリング演算装置１への入力は、楕円曲線Eb上の2点P,Qである。点P,Qは、以下の条件を満たさなければならない。(1)点P,Qのx,y座標がp2nを位数とする有限体Fp^2nの元である。(2)点P,Qの位数がr’である。
・ペアリング演算装置１からの出力は、ペアリング値e(P,Q)である。具体的には、p6nを位数とする有限体Fp^6nの非ゼロの元であり、その乗法に関する位数がr’である。
【００４５】
＜Millerのアルゴリズム＞
図２を参照して、この実施形態のMillerのアルゴリズムの動作例を説明する。
（ステップS1-1）入力部１１からMiller演算部１２へ整数T=t-1、楕円曲線Eb上の有理点P，Q∈Eb(Fq)が入力される。ここでtはトレースである。
（ステップS1-2）点Qに上述の補題１を利用して点Pと交わりを持たない点Q’=ι(Q)∈Eb(Fq^3)を式(6)のように計算する。ここで、xQは点Qのx座標、yQは点Qのy座標を表す。
【００４６】
【数６】
2014164176.tif 000008
【００４７】
（ステップS1-3）点Vに点Pを代入する。値fに1を代入する。
（ステップS1-4）Tを二進展開し式(7)を満たす値s0,…,sL-1を得る。ここで、LはTのビット長である。
【００４８】
【数７】
2014164176.tif 000009
【００４９】
（ステップS1-5）値iにL-2を代入する。
（ステップS1-6）lV,Vに点Q’を代入した値を計算し値gとする。ここで、lV,Vは点Vの接線である。
（ステップS1-7）点Vの２倍点を計算し点Vとする。
（ステップS1-8）νV(Q’)=xP-xQの逆元を上記式(5)に従って計算し値hとする。ここで、νVは点Vを通る垂線である。補題２に示す通り式(5)の右辺の分母は後述の最終べき乗処理で1になるため、h=xP2+xPxQ+xQ2だけを計算すればよい。
（ステップS1-9）f2・g・hを計算し値fとする。
（ステップS1-10）si=1が成り立つか検証する。もしsi=1ならば（ステップS1-11）〜（ステップS1-14）を実行する。もしsi≠1ならば（ステップS1-15）へ進む。
（ステップS1-11）lV,Pに点Q’を代入した値を計算し値gとする。ここで、lV,Pは点V，Pを通る直線である。
（ステップS1-12）点Vに点Pを加え点Vとする。
（ステップS1-13）νV(Q’)=xP-xQの逆元を上記式(5)に従って計算し値hとする。ここで、νVは点Vを通る垂線である。（ステップS1-8）と同様に、ここでもh=xP2+xPxQ+xQ2だけを計算すればよい。
（ステップS1-14）f・g・hを計算し値fとする。
（ステップS1-15）i=i-1を実行する。
（ステップS1-16）i<0が成り立つか検証する。i<0ならば（ステップS1-17）へ進む。i≧0ならば（ステップS1-6）へ戻る。
（ステップS1-17）Miller演算部１２はべき乗演算部１３へ値fを出力する。
【００５０】
以下にMillerのアルゴリズムの実装の一例を示す。下記のアルゴリズムは上記の説明と完全に対応するものではなく、実装上の簡略化などが行われている。記載上の相違があれば適宜読み替えられたい。
【表１】
2014164176.tif 000010
【００５１】
この実施形態ではAteペアリングを計算する場合を例示しているが、Tateペアリングを計算することも可能である。以下にTateペアリングを計算する場合の変更点を説明する。なお、Ateペアリングの場合と同様のステップについては説明を省略する。
（ステップS1-1）入力部１１からMiller演算部１２へ楕円曲線Eb上の有理点P，Q∈Eb(Fq)が入力される。すなわち整数Tは入力されない。
（ステップS1-4）点P，Qの位数r’を二進展開し式(8)を満たす値s0,…,sK-1を得る。ここで、Kはr’のビット長である。
【００５２】
【数８】
2014164176.tif 000011
【００５３】
（ステップS1-5）値iにK-2を代入する。
【００５４】
＜最終べき乗＞
最終べき乗とは、Millerのアルゴリズムの出力fを(qk-1)/r’回乗じる処理である。上述の通り楕円曲線Eb/Fqの埋込次数kは3であるため、この実施形態では(q3-1)/r’乗を計算すればよい。rは楕円曲線EbのFq有理点の群位数、r’は楕円曲線Eb上の有理点P，Qの位数を表し、r=p2-p+1=cr’の関係が成り立つ。ここで、cは1以上の整数である。
【００５５】
楕円曲線Ebの特徴を利用することで最終べき乗の指数部分を式(9)のように変形できる。
【００５６】
【数９】
2014164176.tif 000012
【００５７】
ここで、p乗フロベニウス写像ψpを考えるとf∈Fq^3の最終べき乗は、式(10)のように計算できる。
【００５８】
【数１０】
2014164176.tif 000013
【００５９】
フロベニウス写像ψp^nはp乗フロベニウス写像ψpをn回（nは整数）適用する演算であり、ψp(x)=xpである。
【００６０】
図３を参照して、べき乗演算部１３の実行する最終べき乗処理の動作例を説明する。
（ステップS2-1）Miller演算部１２の出力する値fがべき乗演算部１３へ入力される。値fはq3を位数とする有限体Fq^3の元である。
（ステップS2-2）値fのp2乗フロベニウス写像ψp^2(f)を計算し値m1とする。
（ステップS2-3）値fの逆元m-1を計算し値m2とする。
（ステップS2-4）値m1と値m2を乗じ値uとする。
（ステップS2-5）値uのp2乗フロベニウス写像ψp^2(u)を計算し値u1とする。
（ステップS2-6）値uのp乗フロベニウス写像ψp(u)を計算し値u2とする。
（ステップS2-7）u1とu2とuを乗じ値νとする。
（ステップS2-8）べき乗演算部１３はνcを点P,Qのペアリング値e(P,Q)として、出力部１４を介して出力する。
【００６１】
上記のアルゴリズムはq=p2の場合、つまりn=1の場合であるが、q=p2nであるときも有効である。具体的には式(11)のように計算できる。
【００６２】
【数１１】
2014164176.tif 000014
【００６３】
このように、q=p2nであるときは、(p2n-1)とpのべき乗の加減算で表される項と1以上の整数cとの乗算に変形して考えればよい。
【００６４】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６５】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００６６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７０】
１  ペアリング演算装置
１１  入力部
１２  Miller演算部
１３  べき乗演算部
１４  出力部
１０１  制御部
１０２  メモリ
【図１】
2014164176.tif 000016
【図２】
2014164176.tif 000017
【図３】
2014164176.tif 000018