(57)【要約】【課題】  多項式べき乗演算装置で、多項式ｆ（ｘ）の引数ｘを用いることなく、指数となる多項式の項数よりも少ないデータ数で、多項式を指数とする元ｇの多項式べき乗演算結果ｇｆ（ｘ）を得ること。【解決手段】  多項式のｍ個の係数と、ｍ個よりも少ないｎ個のべき乗データと、各係数に対応する、ｎ個のべき乗データのうち適宜２つのべき乗データを示す対応テーブルとを記憶する記憶手段と、対応テーブルを参照して、各係数に対応するべき乗データを記憶手段から読み出す参照手段と、係数及び参照手段によって読み出された２つのべき乗データから、係数を指数とした射影ペアリングのべき乗を演算するべき乗射影ペアリング演算手段と、べき乗射影ペアリング演算手段によって得られる、各係数に対するべき乗射影ペアリング演算結果の積を演算して、この演算結果を多項式べき乗演算結果ｇｆ（ｘ）として出力する積演算手段とを備えた多項式べき乗演算装置とする。【選択図】  図１
2006201719.tif 000002
【特許請求の範囲】
【請求項１】
群の元ｇについて、ｍ個の項からなる多項式
【数１】
2006201719.tif 000048
を指数とした多項式べき乗演算結果ｇｆ（ｘ）を得る多項式べき乗演算装置において、
多項式ｆ（ｘ）のｍ個の係数ａ＿ｉ〔ｉ＝０、１、２、・・・、ｍ−１〕と、
ｎ個〔ｎ＜ｍとする。〕のべき乗データＰ＿ｗ〔ｗ＝０、１、２、・・・、ｎ−１；但しべき乗データＰ＿ｗは、Ｐ＿ｗ＝ｘｄ＿ｗＲを満たす。ここで、Ｒは、Ｅ［Ｌ］〔但しＥ［Ｌ］は、有限体上定義された楕円曲線Ｅ上におけるＬ等分点の集合であり、Ｌは素数とする。〕のフロベニウス写像φｓ〔ｓは正整数〕の非固有空間上における位数Ｌの巡回群の元であり、ｄ＿ｗは、ｎ個の指数構成値であって、多項式ｆ（ｘ）の項の各指数ｃ＿ｉとの間に
【数２】
2006201719.tif 000049
が成り立ち、ｘは、多項式ｆ（ｘ）の引数であり、ｘｄ＿ｗは、指数構成値ｄ＿ｗを指数とした引数ｘのべき乗であり、ｘｄ＿ｗＲは、元Ｒのｘｄ＿ｗ楕円スカラー倍である。〕と、
各係数ａ＿ｉに対応する、ｎ個のべき乗データＰ＿ｗのうち、指数ｃ＿ｉを構成する指数構成値ｄ＿ｊｉ、ｄ＿ｋｉから得られた２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉを示す対応テーブルと
を記憶する記憶手段と、
対応テーブルを参照して、各係数ａ＿ｉに対応するデータＰ＿ｊｉ、Ｐ＿ｋｉを記憶手段から読み出す参照手段と、
係数ａ＿ｉ及び参照手段によって読み出されたべき乗データＰ＿ｊｉ、Ｐ＿ｋｉから、係数ａ＿ｉを指数とした射影ペアリングｅ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）〔但し射影ペアリングｅ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）は、ペアリングｅＬ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）におけるいずれか一方の被演算子が線形変換Ψを施されたものとする。線形変換Ψは、Ｅ［Ｌ］から、フロベニウス写像φｓの固有値λｓに関する固有空間Ψ（Ｅ［Ｌ］）への準同型写像であって、Ψ＝const×（φｓ−λｓ）〔constは定数〕で定義される。また、上記元Ｒに対してｇ＝ｅ（Ｒ、Ｒ）とする。〕のべき乗を演算するべき乗射影ペアリング演算手段と、
べき乗射影ペアリング演算手段によって得られる、各係数ａ＿ｉに対するべき乗射影ペアリング演算結果の積
【数３】
2006201719.tif 000050
を演算して、この演算結果を多項式べき乗演算結果ｇｆ（ｘ）として出力する積演算手段と
を備えたことを特徴とする多項式べき乗演算装置。
【請求項２】
有限体上定義された楕円曲線Ｅが超特異楕円曲線であり、
元Ｒが、Ｅ［Ｌ］のフロベニウス写像φｓの固有空間上における位数Ｌの巡回群の元であり、
積演算手段における射影ペアリング（Ｐ＿ｊｉ、Ｐ＿ｋｉ）が、ペアリングｅＬ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）におけるいずれか一方の被演算子が線形変換Ψの逆演算を施されたものである
ことを特徴とする請求項１に記載の多項式べき乗演算装置。
【請求項３】
べき乗データ生成装置と請求項１に記載の多項式べき乗演算装置とが、少なくともべき乗データ生成装置から多項式べき乗演算装置にデータ送信可能に接続され、
べき乗データ生成装置は、
Ｅ［Ｌ］〔但しＥ［Ｌ］は、有限体上定義された楕円曲線Ｅ上におけるＬ等分点の集合であり、Ｌは素数とする。〕のフロベニウス写像φｓ〔ｓは正整数〕の非固有空間上における位数Ｌの巡回群の元Ｒと、ｎ個の指数構成値ｄ＿ｗ〔ｗ＝０、１、２、・・・、ｎ−１；指数構成値ｄ＿ｗは、多項式ｆ（ｘ）の各項の指数ｃ＿ｉ〔ｉ＝０、１、２、・・・、ｍ−１〕との間に
【数４】
2006201719.tif 000051
が成り立つものである。〕と、多項式ｆ（ｘ）の引数ｘとを記憶する記憶手段と、
記憶手段に記憶される元Ｒ、ｎ個の指数構成値ｄ＿ｗ及び引数ｘから、元Ｒと、各指数構成値ｄ＿ｗを指数とした引数ｘのべき乗ｘｄ＿ｗとの楕円スカラー倍演算Ｐ＿ｗ＝ｘｄ＿ｗＲを行い、この演算結果を出力するべき乗データ生成手段と、
少なくとも生成されたｎ個のべき乗データＰ＿ｗを、べき乗データ生成装置外部へ送信可能な通信手段とを備えるとし、
べき乗データ生成装置のべき乗データ生成手段において、ｎ個のべき乗データＰ＿ｗを生成し、
生成されたｎ個のべき乗データＰ＿ｗを、べき乗データ生成装置の通信手段によって上記多項式べき乗演算装置に送信し、
ｎ個のべき乗データＰ＿ｗを受信した上記多項式べき乗演算装置において、多項式べき乗演算結果ｇｆ（ｘ）を算出することを特徴とする多項式べき乗演算方法。
【請求項４】
べき乗データ生成装置と請求項２に記載の多項式べき乗演算装置とが、少なくともべき乗データ生成装置から多項式べき乗演算装置にデータ送信可能に接続され、
べき乗データ生成装置は、
Ｅ［Ｌ］〔但しＥ［Ｌ］は、有限体上定義された超特異楕円曲線Ｅ上におけるＬ等分点の集合であり、Ｌは素数とする。〕のフロベニウス写像φｓ〔ｓは正整数〕の固有空間上における位数Ｌの巡回群の元Ｒと、ｎ個の指数構成値ｄ＿ｗ〔ｗ＝０、１、２、・・・、ｎ−１；指数構成値ｄ＿ｗは、多項式ｆ（ｘ）の各項の指数ｃ＿ｉ〔ｉ＝０、１、２、・・・、ｍ−１〕との間に
【数５】
2006201719.tif 000052
が成り立つものである。〕と、多項式ｆ（ｘ）の引数ｘとを記憶する記憶手段と、
記憶手段に記憶される元Ｒ、ｎ個の指数構成値ｄ＿ｗ及び引数ｘから、元Ｒと、各指数構成値ｄ＿ｗを指数とした引数ｘのべき乗ｘｄ＿ｗとの楕円スカラー倍演算Ｐ＿ｗ＝ｘｄ＿ｗＲを行い、この演算結果を出力するべき乗データ生成手段と、
少なくとも生成されたｎ個のべき乗データＰ＿ｗを、べき乗データ生成装置外部へ送信可能な通信手段とを備えるとし、
べき乗データ生成装置のべき乗データ生成手段において、ｎ個のべき乗データＰ＿ｗを生成し、
生成されたｎ個のべき乗データＰ＿ｗを、べき乗データ生成装置の通信手段によって上記多項式べき乗演算装置に送信し、
ｎ個のべき乗データＰ＿ｗを受信した上記多項式べき乗演算装置において、多項式べき乗演算結果ｇｆ（ｘ）を算出することを特徴とする多項式べき乗演算方法。
【請求項５】
請求項１または請求項２に記載された多項式べき乗演算装置としてコンピュータを機能させるための多項式べき乗演算プログラム。
【請求項６】
請求項５に記載の多項式べき乗演算プログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多項式を指数としたべき乗演算を行う多項式べき乗演算技術に関する。特に、情報セキュリティ技術に係わる多項式べき乗演算技術に関する。
【背景技術】
【０００２】
ｍ個の項からなる多項式ｆ（ｘ）が、係数ａ＿ｉ〔但し、記号＿は下添え字であることを表し、ｉ＝０、１、２、・・・、ｍ−１とする。〕及びどの２つも等しくない指数ｃ＿ｉによって
【数６】
2006201719.tif 000003
と表されるとする。
【０００３】
さらに、二者Ａ、Ｂにおいて、Ａが多項式ｆ（ｘ）の係数ａ＿ｉを把握し、Ｂが多項式ｆ（ｘ）の引数ｘを把握し、指数ｃ＿ｉはＡ、Ｂ両者において把握されているとする。なお、ここで引数ｘとは、多項式ｆ（ｘ）の不定元（変数）から１つ選択されたものである。
【０００４】
この場合に、Ｂが引数ｘを明かさないで、ある離散対数問題の困難な群（例えば、乗法で定義された集合Ｚｐ〔０以上ｐ未満の整数集合で、ｐは素数とする。〕、位数が素数またはその冪である有限体、有限体上定義された楕円曲線上の点集合〔無限遠点が付加される。〕などがある。なお、この点集合は、射影幾何学的な加算が定義されてアーベル群を成す。）の元ｇについて、多項式ｆ（ｘ）を指数とした多項式べき乗ｇｆ（ｘ）をＡに演算させる方法は、次に示すものであった。
【０００５】
＜ステップ１＞
Ｂはｉ＝０からｉ＝ｍ−１まで
【数７】
2006201719.tif 000004
を求め、これらのデータｇ＿０、ｇ＿１、・・・、ｇ＿（ｍ−１）をＡに渡す。
＜ステップ２＞
Ａは、Ｂから受け取ったデータｇ＿０、ｇ＿１、・・・、ｇ＿（ｍ−１）及びＡが把握する多項式の係数ａ＿０、ａ＿１、・・・、ａ＿（ｍ−１）を用いて、各ｉについてａ＿ｉを指数としたｇ＿ｉのべき乗したものの積
【数８】
2006201719.tif 000005
を求める。これがｇｆ（ｘ）の値となる。
【０００６】
なぜなら、［数８］について、次式が成立するからである。
【数９】
2006201719.tif 000006
【０００７】
以上のように、Ｂが引数ｘを明かさないでＡに元ｇの多項式べき乗ｇｆ（ｘ）を演算させることは、例えば参考文献１に示されるようにグループ署名などの情報セキュリティ技術において利用される。グループ署名とは、グループに属している全てのグループメンバーが匿名で、グループを代表して署名することが可能な電子署名方式である。
（参考文献１）  Jan Camenisch and Markus Stadler、 “Efficient Group Signature Schemes for Large Groups”、 Advances in Cryptology -CRYPTO’97、 volume 1294 of Lecture Notes in Computer Sciences、 pp.410-424、 Springer Verlag、 1997.
【０００８】
しかしながら上記の方法では、例えば、ＡおよびＢがお互いに通信可能なネットワーク上において、ＢがＡに上記データを送信するような場合を考慮すると、ＢがＡに送信するデータｇ＿０、ｇ＿１、・・・、ｇ＿（ｍ−１）の数が多項式の項数ｍに比例しており、多項式の項数ｍが大きいときには、ＡＢ間で送信される必要なデータ数が増大してしまう。そして、データ量が大きい場合には、ＡＢ間における通信ネットワーク上の通信量が増大し、また、多項式べき乗演算に必要となるデータの記憶領域も大きく確保されなければならないものとなってしまう。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
そこで本発明は、以上の点に鑑みて、多項式ｆ（ｘ）の引数ｘを用いず、かつ、指数となる多項式ｆ（ｘ）の項数よりも少ないデータ数で、多項式ｆ（ｘ）を指数とする元ｇの多項式べき乗演算結果ｇｆ（ｘ）を得る多項式べき乗演算装置、多項式べき乗演算方法、並びに多項式べき乗演算装置をコンピュータ上で機能させる多項式べき乗演算プログラム及びその記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の多項式べき乗演算装置は、上記の問題点を解決するものとして、次のように構成される。即ち、群の元ｇについて、ｍ個の項からなる多項式
【数１０】
2006201719.tif 000007
を指数とした多項式べき乗演算結果ｇｆ（ｘ）を得る多項式べき乗演算装置であって、多項式ｆ（ｘ）のｍ個の係数ａ＿ｉ〔ｉ＝０、１、２、・・・、ｍ−１〕と、ｎ個〔ｎ＜ｍとする。〕のべき乗データＰ＿ｗ〔ｗ＝０、１、２、・・・、ｎ−１；但しべき乗データＰ＿ｗは、Ｐ＿ｗ＝ｘｄ＿ｗＲを満たす。ここで、Ｒは、Ｅ［Ｌ］〔但しＥ［Ｌ］は、有限体上定義された楕円曲線Ｅ上におけるＬ等分点の集合であり、Ｌは素数とする。〕のフロベニウス写像φｓ〔ｓは正整数〕の非固有空間上における位数Ｌの巡回群の元であり、ｄ＿ｗは、ｎ個の指数構成値であって、多項式ｆ（ｘ）の項の各指数ｃ＿ｉとの間に
【数１１】
2006201719.tif 000008
が成り立ち、ｘは、多項式ｆ（ｘ）の引数であり、ｘｄ＿ｗは、指数構成値ｄ＿ｗを指数とした引数ｘのべき乗であり、ｘｄ＿ｗＲは、元Ｒのｘｄ＿ｗ楕円スカラー倍である。〕と、各係数ａ＿ｉに対応する、ｎ個のべき乗データＰ＿ｗのうち、指数ｃ＿ｉを構成する指数構成値ｄ＿ｊｉ、ｄ＿ｋｉから得られた２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉを示す対応テーブルとを記憶する記憶手段と、対応テーブルを参照して、各係数ａ＿ｉに対応するデータＰ＿ｊｉ、Ｐ＿ｋｉを記憶手段から読み出す参照手段と、係数ａ＿ｉ及び参照手段によって読み出されたべき乗データＰ＿ｊｉ、Ｐ＿ｋｉから、係数ａ＿ｉを指数とした射影ペアリングｅ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）〔但し射影ペアリングｅ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）は、ペアリングｅＬ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）におけるいずれか一方の被演算子が線形変換Ψを施されたものとする。線形変換Ψは、Ｅ［Ｌ］から、フロベニウス写像φｓの固有値λｓに関する固有空間Ψ（Ｅ［Ｌ］）への準同型写像であって、Ψ＝const×（φｓ−λｓ）〔constは定数〕で定義される。また、上記元Ｒに対してｇ＝ｅ（Ｒ、Ｒ）とする。〕のべき乗を演算するべき乗射影ペアリング演算手段と、べき乗射影ペアリング演算手段によって得られる、各係数ａ＿ｉに対するべき乗射影ペアリング演算結果の積
【数１２】
2006201719.tif 000009
を演算して、この演算結果を多項式べき乗演算結果ｇｆ（ｘ）として出力する積演算手段とを備えたことを特徴とする。（この多項式べき乗演算装置を第１の多項式べき乗演算装置と呼ぶことにする。）。
【００１１】
この構成によれば、ｍ個の項からなる多項式ｆ（ｘ）を指数とした多項式べき乗演算結果ｇｆ（ｘ）は、多項式ｆ（ｘ）のｍ個の係数ａ＿０、ａ＿１、ａ＿２、・・・、ａ＿（ｍ−１）と、各係数ａ＿ｉに対応付けられた、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）うち適宜２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉの射影ペアリングｅ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）とのべき乗演算で得られたｍ個のべき乗射影ペアリング演算結果ｅ（Ｐ＿ｊ０、Ｐ＿ｋ０）ａ＿０、ｅ（Ｐ＿ｊ１、Ｐ＿ｋ１）ａ＿１、ｅ（Ｐ＿ｊ２、Ｐ＿ｋ２）ａ＿２、・・・、ｅ（Ｐ＿ｊｍ−１、Ｐ＿ｋｍ−１）ａ＿（ｍ−１）の積の演算結果として得られる。
【００１２】
また、上記多項式べき乗演算装置において、有限体上定義された楕円曲線Ｅが超特異楕円曲線であり、元Ｒが、Ｅ［Ｌ］のフロベニウス写像φｓの固有空間上における位数Ｌの巡回群の元であり、積演算手段における射影ペアリング（Ｐ＿ｊｉ、Ｐ＿ｋｉ）が、ペアリングｅＬ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）におけるいずれか一方の被演算子が線形変換Ψの逆演算を施されたものであるとしてもよい（この多項式べき乗演算装置を第２の多項式べき乗演算装置と呼ぶことにする。）。
【００１３】
有限体上定義された上記楕円曲線Ｅが超特異楕円曲線の場合、線形変換Ψの逆演算（これをｄｉｓということにする。）は、多項式時間で演算することが可能である。従って、射影ペアリングｅ（Ｒ１、Ｒ２）が、ペアリングｅＬ（Ｒ１、Ｒ２）におけるいずれか一方の被演算子が線形変換Ψの逆演算ｄｉｓを施されたものとしても、多項式べき乗演算装置で、計算量理論上効率的に多項式べき乗演算を行うことができる。また、楕円曲線が超特異楕円曲線の場合には、一般に楕円曲線上の点は乗法群の点の約１／２ないし１／６程度の（計算量理論上の）情報量となるので、より少ない情報量から所望の多項式べき乗演算結果を得ることができる。
【００１４】
さらに、本発明における多項式べき乗演算方法は、べき乗データ生成装置と第１の多項式べき乗演算装置とが、少なくともべき乗データ生成装置から第１の多項式べき乗演算装置にデータ送信可能に接続され、ここに、べき乗データ生成装置とは、Ｅ［Ｌ］〔但しＥ［Ｌ］は、有限体上定義された楕円曲線Ｅ上におけるＬ等分点の集合であり、Ｌは素数とする。〕のフロベニウス写像φｓ〔ｓは正整数〕の非固有空間上における位数Ｌの巡回群の元Ｒと、ｎ個の指数構成値ｄ＿ｗ〔ｗ＝０、１、２、・・・、ｎ−１；指数構成値ｄ＿ｗは、多項式ｆ（ｘ）の各項の指数ｃ＿ｉ〔ｉ＝０、１、２、・・・、ｍ−１〕との間に
【数１３】
2006201719.tif 000010
が成り立つものである。〕と、多項式ｆ（ｘ）の引数ｘとを記憶する記憶手段と、記憶手段に記憶される元Ｒ、ｎ個の指数構成値ｄ＿ｗ及び引数ｘから、元Ｒと、各指数構成値ｄ＿ｗを指数とした引数ｘのべき乗ｘｄ＿ｗとの楕円スカラー倍演算Ｐ＿ｗ＝ｘｄ＿ｗＲを行い、この演算結果を出力するべき乗データ生成手段と、少なくとも生成されたｎ個のべき乗データＰ＿ｗを、べき乗データ生成装置外部へ送信可能な通信手段とを備えるものとし、べき乗データ生成装置のべき乗データ生成手段においてｎ個のべき乗データＰ＿ｗを生成し、生成されたｎ個のべき乗データＰ＿ｗを、べき乗データ生成装置の通信手段によって第１の多項式べき乗演算装置に送信し、ｎ個のべき乗データＰ＿ｗを受信した第１の多項式べき乗演算装置において、多項式べき乗演算結果ｇｆ（ｘ）を算出することを特徴とするものである。
【００１５】
また、本発明の多項式べき乗演算方法としては、べき乗データ生成装置と第２の多項式べき乗演算装置とが、少なくともべき乗データ生成装置から多項式べき乗演算装置にデータ送信可能に接続され、ここに、べき乗データ生成装置とは、Ｅ［Ｌ］〔但しＥ［Ｌ］は、有限体上定義された超特異楕円曲線Ｅ上におけるＬ等分点の集合であり、Ｌは素数とする。〕のフロベニウス写像φｓ〔ｓは正整数〕の固有空間上における位数Ｌの巡回群の元Ｒと、ｎ個の指数構成値ｄ＿ｗ〔ｗ＝０、１、２、・・・、ｎ−１；指数構成値ｄ＿ｗは、多項式ｆ（ｘ）の各項の指数ｃ＿ｉ〔ｉ＝０、１、２、・・・、ｍ−１〕との間に
【数１４】
2006201719.tif 000011
が成り立つものである。〕と、多項式ｆ（ｘ）の引数ｘとを記憶する記憶手段と、記憶手段に記憶される元Ｒ、ｎ個の指数構成値ｄ＿ｗ及び引数ｘから、元Ｒと、各指数構成値ｄ＿ｗを指数とした引数ｘのべき乗ｘｄ＿ｗとの楕円スカラー倍演算Ｐ＿ｗ＝ｘｄ＿ｗＲを行い、この演算結果を出力するべき乗データ生成手段と、少なくとも生成されたｎ個のべき乗データＰ＿ｗを、べき乗データ生成装置外部へ送信可能な通信手段とを備えるものとし、べき乗データ生成装置のべき乗データ生成手段においてｎ個のべき乗データＰ＿ｗを生成し、生成されたｎ個のべき乗データＰ＿ｗを、べき乗データ生成装置の通信手段によって第２の多項式べき乗演算装置に送信し、ｎ個のべき乗データＰ＿ｗを受信した第２の多項式べき乗演算装置において、多項式べき乗演算結果ｇｆ（ｘ）を算出することを特徴とするものとしてもよい。
【００１６】
以上の多項式べき乗演算方法において、べき乗データ生成装置で生成されるｎ個のべき乗データＰ＿ｗは、多項式べき乗演算装置のべき乗射影ペアリング演算手段で演算される射影ペアリングに対応した元Ｒによって生成されるものである。即ち、射影ペアリングが、ペアリングにおけるいずれか一方の被演算子が線形変換Ψを施されたものである場合には、元Ｒは、有限体上定義された楕円曲線（超特異楕円曲線でも非超特異楕円曲線でもよい。）Ｅ上におけるＬ等分点の集合Ｅ［Ｌ］のフロベニウス写像φｓ〔ｓは正整数〕の非固有空間上における位数Ｌの巡回群の元とする。また、射影ペアリングが、ペアリングにおけるいずれか一方の被演算子が線形変換Ψの逆演算ｄｉｓを施されたものである場合には、元Ｒは、有限体上定義された超特異楕円曲線Ｅ上におけるＬ等分点の集合Ｅ［Ｌ］のフロベニウス写像φｓ〔ｓは正整数〕の固有空間上における位数Ｌの巡回群の元とする。
【００１７】
上述の多項式べき乗演算方法によれば、べき乗データ生成装置において生成されたｎ個のべき乗データＰ＿ｗを用いて、多項式べき乗演算装置で多項式べき乗演算結果ｇｆ（ｘ）が算出される。加えて、べき乗データ生成装置においてｎ個のべき乗データＰ＿ｗを生成する際に用いた多項式ｆ（ｘ）の引数ｘを用いることなく、多項式べき乗演算装置において多項式べき乗演算結果ｇｆ（ｘ）が算出される。とくに楕円曲線が超特異楕円曲線の場合には、一般に楕円曲線上の点は乗法群の点の約１／２ないし１／６程度の（計算量理論上の）情報量となるので、べき乗データ生成装置から多項式べき乗演算装置へ送られるべき乗データのデータ量を少なくすることができる。
【００１８】
また、上記多項式べき乗演算装置をコンピュータ上で機能させる多項式べき乗演算プログラムによって、コンピュータを多項式べき乗演算装置として作動処理させることができる。さらに、この多項式べき乗演算プログラムは、コンピュータによって読み取り可能な記録媒体に記録されるとしてもよい。
【発明の効果】
【００１９】
本発明の多項式べき乗演算装置によれば、多項式ｆ（ｘ）の引数ｘを用いることなく、多項式ｆ（ｘ）の項数（ｍ個）よりも少ない個数（ｎ個）のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を用いて、多項式ｆ（ｘ）を指数とした元ｇの多項式べき乗演算結果ｇｆ（ｘ）を得ることができる。
【００２０】
また、本発明の多項式べき乗演算方法によれば、べき乗データ生成装置で生成された多項式ｆ（ｘ）の項数ｍよりも少ないｎ個のべき乗データＰ＿０、Ｐ＿１、・・・、Ｐ＿（ｎ−１）を用いて、多項式べき乗演算結果ｇｆ（ｘ）を得ることができるとともに、べき乗データ生成装置においてべき乗データＰ＿０、Ｐ＿１、・・・、Ｐ＿（ｎ−１）を生成する際に用いた引数ｘを用いることなく、多項式べき乗演算装置において多項式べき乗演算結果ｇｆ（ｘ）を算出することができる。
【発明を実施するための最良の形態】
【００２１】
まず、本発明の装置・方法において上記構成をとる理論背景を説明する。その上で、本発明の装置・方法の実施形態を説明する。
＜理論背景＞
まず、体Ｋ上に定義された楕円曲線について説明する。
一般に、体Ｋ上に定義された楕円曲線とは、ａ１、ａ２、ａ３、ａ４、ａ６∈Ｋとして、等式
【数１５】
2006201719.tif 000012
を満たす点（ｘ、ｙ）の集合に無限遠点と呼ばれる特別な点Ｏを付加したものである。体Ｋ上に定義された楕円曲線上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線上の任意の１点に対して楕円逆元と呼ばれる単項演算−がそれぞれ有限回のＫの体演算により定義できる。また、以下の性質を持つことにより、体Ｋ上に定義された楕円曲線は楕円加算に関して群をなす。
【００２２】
［１］体Ｋ上に定義された楕円曲線上の任意の２点Ｒ１、Ｒ２に対して、Ｒ１＋Ｒ２は楕円曲線上の点である。
【００２３】
［２］体Ｋ上に定義された楕円曲線上の任意の３点Ｒ１、Ｒ２、Ｒ３に対して、Ｒ１＋（Ｒ２＋Ｒ３）＝（Ｒ１＋Ｒ２）＋Ｒ３が成り立つ（結合律）。
【００２４】
［３］無限遠点Ｏに関して、体Ｋ上に定義された楕円曲線上の任意の点Ｒ１に対して、Ｒ１＋Ｏ＝Ｏ＋Ｒ１＝Ｒ１が成り立つ（単位元の存在）。
【００２５】
［４］体Ｋ上に定義された楕円曲線上の任意の点Ｒ１に対して逆元（−Ｒ１）が存在してＲ１＋（−Ｒ１）＝（−Ｒ１）＋Ｒ１＝Ｏが成立する（逆元の存在）。
【００２６】
［５］体Ｋ上に定義された楕円曲線上の任意の２点Ｒ１、Ｒ２に対して、Ｒ１＋Ｒ２＝Ｒ２＋Ｒ１が成り立つ（交換律）。
【００２７】
体Ｋ上に定義された楕円曲線上の１点Ｒがあれば、楕円加算を用いて２Ｒ＝Ｒ＋Ｒとなる体Ｋ上に定義された楕円曲線上の点２Ｒを作ることができる。同様にして、３Ｒ＝２Ｒ＋Ｒなどとすることにより、任意の正整数ｈに対してｈＲを定義することができる。また、任意の正整数ｈに対して（−ｈ）Ｒ＝ｈ（−Ｒ）及び０Ｒ＝Ｏと定義すると、結局任意の整数ｈに対してｈＲを定義することができる。このように整数ｈと体Ｋ上に定義された楕円曲線上の点Ｒから点ｈＲを求めることを楕円スカラー倍と呼ぶ。また、二項演算−をＲ１−Ｒ２＝Ｒ１＋（−Ｒ２）として定義し、これを楕円減算と呼ぶ。
【００２８】
特に体Ｋが有限体であってＫ上の点、あるいは体Ｋの有限次拡大上の点Ｒが数１５に表される楕円曲線上の点であるとき、点Ｒは有限巡回群を生成し、これを用いて暗号系（例えば、楕円ＥｌＧａｍａｌ暗号）や署名系を構成することが可能になる。このような暗号系や署名系では、楕円加算や楕円スカラー倍が効率的に計算可能な楕円曲線を用いる。
【００２９】
ここでＬを素数とし、有限体上定義された楕円曲線Ｅ（以下、特に断りなく楕円曲線といえば、有限体上に定義された楕円曲線をいうものとする。）上の点Ｒのうち、ＬＲ＝Ｏを満たす点Ｒの集合をＥ［Ｌ］とする。そして、この点ＲをＬ等分点という。集合Ｅ［Ｌ］は以下の性質を有するので、集合Ｅ［Ｌ］は楕円加算を加法とし楕円スカラー倍をスカラー倍とするＺＬ上の線形空間である。
【００３０】
楕円加算に関しては、
［１］Ｅ［Ｌ］の任意の２点Ｒ１、Ｒ２に対して、楕円加算Ｒ１＋Ｒ２はＥ［Ｌ］上の点である。
【００３１】
［２］楕円加算の結合律は、Ｅ［Ｌ］でも成り立つ。
【００３２】
［３］楕円加算の交換律は、Ｅ［Ｌ］でも成り立つ。
【００３３】
［４］無限遠点ＯはＥ［Ｌ］上の点であり、Ｅ［Ｌ］上の任意の点Ｒ１に対して、Ｒ１＋Ｏ＝Ｏ＋Ｒ１＝Ｒ１が成り立つ。
【００３４】
［５］Ｅ［Ｌ］上の任意の点Ｒ１に対して逆元（−Ｒ１）はＥ［Ｌ］上に唯一存在する。
【００３５】
楕円スカラー倍に関しては、
［１］Ｅ［Ｌ］上の任意の点Ｒ１及び体ＺＬの任意の元ｈ１に対して、楕円スカラー倍ｈ１Ｒ１はＥ［Ｌ］上の点である。
【００３６】
［２］Ｅ［Ｌ］上の任意の点Ｒ１及び体ＺＬの任意の２元ｈ１、ｈ２に対して、（ｈ１＋ｈ２）Ｒ１＝ｈ１Ｒ１＋ｈ２Ｒ１が成り立つ。
【００３７】
［３］Ｅ［Ｌ］上の任意の２点Ｒ１、Ｒ２及び体ＺＬの任意の元ｈ１に対して、ｈ１（Ｒ１＋Ｒ２）＝ｈ１Ｒ１＋ｈ１Ｒ２が成り立つ。
【００３８】
［４］Ｅ［Ｌ］上の任意の点Ｒ１及び体ＺＬの任意の２元ｈ１、ｈ２に対して、（ｈ１ｈ２）Ｒ１＝ｈ１（ｈ２Ｒ１）が成り立つ。
【００３９】
［５］Ｅ［Ｌ］上の任意の点Ｒ１及び体ＺＬの任意の乗法単位元１に対して、１Ｒ１＝Ｒ１が成り立つ。
【００４０】
なお、点ＲがＥ［Ｌ］上の点であるという場合、点Ｒが集合Ｅ［Ｌ］に属するという側面から、Ｅ［Ｌ］の元Ｒと表現することもある。この明細書では、説明の都合として点Ｒと元Ｒという表現を適宜用いることにする。また、双方の表現で意味内容が格別異なるものではなく、本発明の本質には全く影響するものではない。
【００４１】
一般に、楕円曲線上の点のデータは、そのｘ座標が与えられれば、ｙ座標に関する２次式を解くことによって、２つの点に絞り込むことができる。従って、ｘ座標の他に、ｙの２つの解のうち、どちらであるかを決める１ｂｉｔの情報があれば、楕円曲線上の点のデータを一意に決めることができる。つまり、楕円曲線上の点を表現するのにｘ座標、ｙ座標の組み合わせによらなければならないものではなく、ｘ座標と、それに対応するｙ座標の符号（正または負）の組み合わせによっても、楕円曲線上の点は表現できる。この場合、楕円曲線上の点をｘ座標、ｙ座標のデータで表す情報量よりも少ない情報量で楕円曲線上の点を特定することができる。
【００４２】
次に、有限体のフロベニウス写像を説明する。
ここでｑを素数またはその冪とする。有限体ＧＦ（ｑｍ）上の元ｘを表現するのに、有限体ＧＦ（ｑ）上のｍ個の元の組ｘｉ（０≦ｉ＜ｍ）を用いることができる。ｍ個のｘｉ∈ＧＦ（ｑ）（０≦ｉ＜ｍ、記号∈はｘｉがＧＦ（ｑ）の元であることを表す。）の組をＧＦ（ｑｍ）上の元に対応させる代表的な方法は、ｍ個のαｉ∈ＧＦ（ｑｍ）（０≦ｉ＜ｍ）を使って、
【数１６】
2006201719.tif 000013
なる対応を取るものである。この時、αｉ∈ＧＦ（ｑｍ）（０≦ｉ＜ｍ）は、ＧＦ（ｑ）ｍとＧＦ（ｑｍ）とで１対１対応が取れるような特別な組み合わせであるとする。このような性質を持つαｉ∈ＧＦ（ｑｍ）（０≦ｉ＜ｍ）を基底と呼ぶ。
【００４３】
ところで二項定理によれば、
【数１７】
2006201719.tif 000014
である。右辺の各項の係数は二項係数と呼ばれる定数で、ｉ≠０かつｉ≠ｑの場合、必ずｑの倍数となる。α、β∈ＧＦ（ｑｍ）の時は、ｑの整数倍は０と同値であるから、
【数１８】
2006201719.tif 000015
が成り立つ。更に、ｃ∈ＧＦ（ｑ）なるｃに関して、ｃｑ＝ｃが成立する。
【００４４】
一般に、α１、α２、・・・、αｎを不定元とする任意のＧＦ（ｑ）係数有利式ｆ（α１、α２、・・・、αｎ）に対して、
【数１９】
2006201719.tif 000016
が成立する。従って、
【数２０】
2006201719.tif 000017
なる時、
【数２１】
2006201719.tif 000018
が成り立つ。そこで事前に
【数２２】
2006201719.tif 000019
なるｃｉｊ∈ＧＦ（ｑ）が求められていれば、
【数２３】
2006201719.tif 000020
によって、元の基底αｉを用いたｘｑの表現が得られる。即ち、ｘ∈ＧＦ（ｑｍ）を表現するベクトル（ｘｉ）に行列（ｃｉｊ）を掛けるだけでｘｑを表現するベクトルが得られる。
【００４５】
この演算コストは、一般には、ＧＦ（ｑｍ）上の乗算１回分の演算コストとほぼ等しい。また、行列（ｃｉｊ）ｎ（ｎ＝２、３、・・・）を事前に求めておけば、行列（ｃｉｊ）ｎを掛けるだけで、ｘｓ（但しｓ＝ｑｎとする。）を表現するベクトルを求めることができる。あるいは逆行列（ｃｉｊ）−１を事前に求めておけば、逆行列（ｃｉｊ）−１を掛けるだけでｘ１／ｑを表現するベクトルを得られる。従って、一般の整数ｎに対して、ｘｓの演算コストは一般にＧＦ（ｑｍ）上の乗算１回分の演算コストに等しくなる。さらに、行列（ｃｉｊ）が簡潔に表現できる特別な基底が存在し、この基底を採用した場合、ｘｓの演算コストはＧＦ（ｑｍ）上の乗算と比較して無視できるほどに小さいものとなる。
なお、ＧＦ（ｑｍ）上の元ｘからｘｑへの写像をフロベニウス写像と呼び、整数ｎに関して、ｘからｘｓへの写像をｑｎ乗フロベニウス写像と呼ぶ。
【００４６】
次に、楕円曲線のフロベニウス写像について説明する。
ｍを整数、ｑを素数またはその冪とする。有限体ＧＦ（ｑ）上に定義された楕円曲線
【数２４】
2006201719.tif 000021
（但し、ａ１、ａ２、ａ３、ａ４、ａ６∈ＧＦ（ｑ）とする。）上のＧＦ（ｑｍ）有理点Ｒに対して、
【数２５】
2006201719.tif 000022
なるφを楕円曲線のフロベニウス写像と呼ぶ。有限体のフロベニウス写像の［数１９］に示される性質により、点Ｒが楕円曲線Ｅ／ＧＦ（ｑ）上の点であるならば、点φＲも楕円曲線Ｅ／ＧＦ（ｑ）上の点である。一般に楕円曲線Ｅ／ＧＦ（ｑ）上の点の楕円加算及び楕円スカラー倍は、与えられる点の座標に関するＧＦ（ｑ）係有理写像で与えられる。従って、有限体のフロベニウス写像の［数１９］に示される性質から、下記の性質が成り立つので、フロベニウス写像φは線形空間Ｅ［Ｌ］の線形変換である。
【００４７】
［１］楕円曲線のフロベニウス写像は、Ｅ／ＧＦ（ｑ）上の自己準同型写像であり、φ（Ｒ１＋Ｒ２）＝（φＲ１）＋（φＲ２）が成り立つ。
【００４８】
［２］楕円スカラー倍と楕円曲線のフロベニウス写像は可換であり、φ（ｈＲ）＝ｈ（φＲ）が成り立つ。
【００４９】
［３］特に、Ｅ［Ｌ］上の点は楕円曲線のフロベニウス写像によってＥ［Ｌ］上の点に移る。つまり、∀Ｒ∈Ｅ［Ｌ］、Ｌ（φＲ）＝φ（ＬＲ）＝Ｏである（記号∀αは、任意のαを表す。）。
【００５０】
ｎを整数として、一般に楕円曲線のｑｎ乗フロベニウス写像φｎは、
【数２６】
2006201719.tif 000023
と定義されるが、上記の性質は、楕円曲線のｑｎ乗フロベニウス写像φｎでも同様に成立する。
【００５１】
次に、フロベニウス写像の固有空間と射影について説明する。
（参考文献２）  イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、鈴木治郎＝訳、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0、p112
【００５２】
参考文献２において示されるように、フロベニウス写像φは［数２４］で表される楕円曲線上の任意のＧＦ（ｑｍ）有理点Ｒに対して、
【数２７】
2006201719.tif 000024
を満たす（但しｔは、ｑ、ａ１、ａ２、ａ３、ａ４、ａ６によって一意に決定される整数である。）。フロベニウス写像φに関する多項式φ２−ｔφ＋ｑを特性多項式と呼ぶ。
【００５３】
ここで楕円曲線をＥ［Ｌ］（但しＬは素数とする。）に限定すると、楕円スカラー倍はＺＬで考えればよい。ＺＬ係数の特性多項式は分解体上で、
【数２８】
2006201719.tif 000025
と分解でき、λ１、λ２をフロベニウス写像φの固有値と呼ぶ。以下においては、λ１、λ２∈ＺＬでかつλ１≠λ２である場合を考える。線形空間であるＥ［Ｌ］の線形変換Ψλ１、Ψλ２（但し、添え字λ１及びλ２は、λ１及びλ２を表す。）を
【数２９】
2006201719.tif 000026
【数３０】
2006201719.tif 000027
と定義すると、任意のＥ［Ｌ］上の点Ｒに対して、
【数３１】
2006201719.tif 000028
【数３２】
2006201719.tif 000029
なるＥ［Ｌ］上の点Ｐ、Ｑが存在し、点Ｒは、
【数３３】
2006201719.tif 000030
と一意に分解できる。
【００５４】
線形空間Ｅ［Ｌ］の線形変換Ψλ１による像Ψλ１（Ｅ［Ｌ］）を、フロベニウス写像φの固有値λ１に関する固有空間と呼び、固有空間Ψλ１（Ｅ［Ｌ］）上の任意の点Ｐに関して、
【数３４】
2006201719.tif 000031
が成り立つ。Ｅ［Ｌ］から固有空間Ψλ１（Ｅ［Ｌ］）への準同型写像をΨλ１（Ｅ［Ｌ］）への射影と呼ぶ。線形変換Ψλ１は、Ψλ１（Ｅ［Ｌ］）への射影である。
【００５５】
同様に、線形空間Ｅ［Ｌ］の線形変換Ψλ２による像Ψλ２（Ｅ［Ｌ］）を、フロベニウス写像φの固有値λ２に関する固有空間と呼び、固有空間Ψλ２（Ｅ［Ｌ］）上の任意の点Ｑに関して、
【数３５】
2006201719.tif 000032
が成り立つ。Ｅ［Ｌ］から固有空間Ψλ２（Ｅ［Ｌ］）への準同型写像をΨλ２（Ｅ［Ｌ］）への射影と呼ぶ。線形変換Ψλ２は、Ψλ２（Ｅ［Ｌ］）への射影である。また、［数３３］に示される分解をフロベニウス写像φの固有空間に関する固有分解と呼ぶ。固有空間はそれぞれ、位数Ｌの巡回群となり、
【数３６】
2006201719.tif 000033
である。
【００５６】
一般に、ｑｎ乗フロベニウス写像φｎに関しても、Ｅ［Ｌ］に関するＺＬ係数の特性多項式
【数３７】
2006201719.tif 000034
（ｔｎは、ｔ、ｎ、ｑによって決まる整数）を考えることによって、上記と同様に、固有値、固有空間、固有分解、射影などを構成できる。そこで、フロベニウス写像φはｑｎ乗フロベニウス写像φｎ（ｎは１以上の整数）をいうものとする。
【００５７】
続いて、ペアリングについて説明する。
（参考文献３）  Alfred.J.Menezes、 ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS、 KLUWER ACADEMIC PUBLISHERS、 ISBN0-7923-9368-6、pp.61-81
【００５８】
μＬを楕円曲線の定義体Ｋの代数閉体上の乗法単位元１のＬ乗根の作る乗法群とする。このとき、参考文献３において示されるように、ペアリングｅＬとは、
【数３８】
2006201719.tif 000035
なる関数であり、次の性質を有する（［数３８］における記号→は線形写像を表す）。
【００５９】
［１］Ｅ［Ｌ］上の任意の点Ｒ１に対して、ｅＬ（Ｒ１、Ｒ１）＝１が成り立つ。
【００６０】
［２］Ｅ［Ｌ］上の任意の２点Ｒ１、Ｒ２に対して、ｅＬ（Ｒ１、Ｒ２）＝ｅＬ（Ｒ２、Ｒ１）−１が成り立つ。
【００６１】
［３］Ｅ［Ｌ］上の任意の３点Ｒ１、Ｒ２、Ｒ３に対して、ｅＬ（Ｒ１＋Ｒ２、Ｒ３）＝ｅＬ（Ｒ１、Ｒ３）ｅＬ（Ｒ２、Ｒ３）であり、ｅＬ（Ｒ１、Ｒ２＋Ｒ３）＝ｅＬ（Ｒ１、Ｒ２）ｅＬ（Ｒ１、Ｒ３）が成り立つ。
【００６２】
［４］Ｅ［Ｌ］上の任意の点Ｒ１に対して、ｅＬ（Ｒ１、Ｏ）＝１が成り立つ。
【００６３】
［５］Ｅ［Ｌ］上のある点Ｒ１がＥ［Ｌ］上の全ての点Ｒ２に対して、ｅＬ（Ｒ１、Ｒ２）＝１を満たすなら、Ｒ１＝Ｏが成り立つ。
【００６４】
なお、この明細書においてペアリングｅＬとは、例えば、参考文献３に示されるＷｅｉｌペアリングやＴａｔｅペアリングなどを挙げることができる。
【００６５】
次に、射影を用いた一方向性関数について説明する。
ここでＬが十分に大きい素数であるとして、Ｅ［Ｌ］に関して、フロベニウス写像φの固有値λ１、λ２がλ１、λ２∈ＺＬかつλ１≠λ２なる場合を考える。固有空間Ψλ１（Ｅ［Ｌ］）の任意の生成元Ｐ及び固有空間Ψλ２（Ｅ［Ｌ］）の任意の生成元Ｑを用いて、Ｅ［Ｌ］上の任意の点Ｒはｈ１、ｈ２∈ＺＬとして、
【数３９】
2006201719.tif 000036
と表される。点Ｒによって生成される巡回群〈Ｒ〉上の任意の点Ｒ1から固有空間Ψλ１（Ｅ［Ｌ］）あるいは固有空間Ψλ２（Ｅ［Ｌ］）への射影は、それぞれ［数３１］、［数３２］に従って、楕円加算、楕円逆元、楕円スカラー倍、フロベニウス写像を用いて効率的に演算できる。一方、ｈ１≠０かつｈ２≠０の時、Ｒ1の射影Ｐ1＝Ψλ１Ｒ1あるいはＱ1＝Ψλ２Ｒ1のいずれか一方からＲ1を求めることは、楕円曲線Ｅが特別な場合を除いて、一般には困難であるといえる。つまり、射影は一方向性を有する。そこでこの一方向性に関して、［数３１］、［数３２］などから、いずれか一方の固有値に対応する線形変換Ψを考えることができ、定数constを用いてΨ＝const×（φｎ−λｎ）と表せる。なお、射影の一方向性については次の性質がある。
【００６６】
［１］ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）（上記の特別な場合の楕円曲線ではないものである。）に関して、Ｅ（ＧＦ（ｑ））をＥ／ＧＦ（ｑ）のＧＦ（ｑ）有理点とし、Ｅ（ＧＦ（ｑｍ））をＥ／ＧＦ（ｑ）のＧＦ（ｑｍ）有理点とする。また、Ｌ｜＃Ｅ（ＧＦ（ｑ））かつＬ¬｜＃Ｅ（ＧＦ（ｑ））とし、Ｌ2｜＃Ｅ（ＧＦ（ｑｍ））とする。なお、記号｜は、Ａ｜Ｂと表記する場合にＡはＢを割り切ることを表し、記号¬｜は、Ａ¬｜Ｂと表記する場合にＡはＢを割り切らないことを表し、＃は位数を表す。このとき、例えばλ１＝１、λ２＝ｑ  ｍｏｄ  Ｌとすることができる。ここで、ｍがＬよりも十分に小さいとすると、効率的に演算できるペアリングｅＬが存在する（例えば、参考文献３参照）。
【００６７】
［２］ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）に関して、固有空間Ψλ１（Ｅ［Ｌ］）あるいは固有空間Ψλ２（Ｅ［Ｌ］）のいずれか一方から巡回群〈Ｒ〉への同型写像で単一の有理写像で記述できるものは存在しない。
【００６８】
［３］ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）に関して、十分に大きい素数位数部分群でのDiffie-Hellman判定問題を効率的に解決することは困難といえる。
【００６９】
［４］ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）に関して、Ｅ［Ｌ］上の無限遠点Ｏ以外の任意の点Ｒ1が生成する巡回群〈Ｒ1〉及びＥ［Ｌ］上の任意の点Ｒ2について、Ｒ2∈〈Ｒ1〉であるか否かは、ペアリングｅLを用いて効率的に判定できる。即ち、ペアリングｅＬ（Ｒ1、Ｒ2）の演算結果が単位元１になる場合、Ｒ2∈〈Ｒ1〉であるといえる。
【００７０】
一般に、Ｅ［Ｌ］上の同じ巡回群の２点Ｒ１、Ｒ２のペアリングｅＬ（Ｒ１、Ｒ２）は、ｅＬ（Ｒ１、Ｒ２）＝１となるので、この演算からは格別有意な情報を抽出することはできない。つまり、Ｅ［Ｌ］上の同じ巡回群の２点Ｒ１、Ｒ２及びａ、ｂ∈ＺＬに関して、
【数４０】
2006201719.tif 000037
となるので、同じ巡回群の２点におけるペアリング演算からはａ、ｂに対応した情報を得ることができない。
【００７１】
ペアリングｅＬ（Ｒ１、Ｒ２）から何らかの情報を得るためには、２点Ｒ１、Ｒ２は異なる巡回群に属するものである必要がある。そこで、Ｅ［Ｌ］のフロベニウス写像の固有空間ではない同じ巡回群の２点Ｒ１、Ｒ２について、そのいずれか一方の点に線形変換Ψを施し、このような２点を被演算子としたペアリングを射影ペアリングｅ（Ｒ１、Ｒ２）とする。即ち、ｅ（Ｒ１、Ｒ２）＝ｅＬ（Ｒ１、Ψ（Ｒ２））となる。射影ペアリングｅ（Ｒ１、Ｒ２）は、ｅ（Ｒ１、Ｒ２）＝ｅＬ（Ψ（Ｒ１）、Ｒ２）でもよい。これによって、ｅ（Ｒ１、Ｒ２）の演算でＥ［Ｌ］上の同じ巡回群に属する２点Ｒ１、Ｒ２から情報を得ることができることになる。
【００７２】
さらにこの場合、有限体上定義された楕円曲線は、超特異楕円曲線でも、非超特異楕円曲線でもよい。有限体ＧＦ（ｑ）〔ｑ＝ｐｍ、ｐ：素数〕上定義された楕円曲線Ｅ／ＧＦ（ｑ）において、＃Ｅ（ＧＦ（ｑ））を楕円曲線Ｅ／ＧＦ（ｑ）のＧＦ（ｑ）有理点の集合Ｅ（ＧＦ（ｑ））の位数とすると、トレースｔは、ｔ＝ｑ＋１−＃Ｅ（ＧＦ（ｑ））と表され、ｐ｜ｔが成り立つ場合に楕円曲線Ｅ／ＧＦ（ｑ）は超特異楕円曲線と呼ばれる。ｐ｜ｔが成り立たない場合の楕円曲線Ｅ／ＧＦ（ｑ）は非超特異楕円曲線と呼ばれる。記号ｐ｜ｔは、ｐがｔを割り切ることを表す。
【００７３】
また、楕円曲線Ｅ／ＧＦ（ｑ）が超特異楕円曲線の場合には、下記参考文献４に示されるように、線形変換Ψの逆演算ｄｉｓを多項式時間で演算することが可能であり、射影ペアリングｅ（Ｒ１、Ｒ２）をｅ（Ｒ１、Ｒ２）＝ｅＬ（ｄｉｓ（Ｒ１）、Ｒ２）と定義することによって、固有空間Ψ（Ｅ[Ｌ]）上の２点Ｒ１、Ｒ２から情報を得ることができる。なお、楕円曲線Ｅ／ＧＦ（ｑ）がアノマラス曲線（anomalous curve；即ち、ｑ＝ｐで＃Ｅ（ＧＦ（ｑ））＝ｐとなる場合の楕円曲線）の場合においても、線形変換Ψの逆演算ｄｉｓは多項式時間で演算可能であるから、射影ペアリングｅ（Ｒ１、Ｒ２）をｅ（Ｒ１、Ｒ２）＝ｅＬ（ｄｉｓ（Ｒ１）、Ｒ２）と定義することによって、固有空間Ψ（Ｅ[Ｌ]）上の２点Ｒ１、Ｒ２から情報を得ることができる。また、射影ペアリングｅ（Ｒ１、Ｒ２）は、ｅ（Ｒ１、Ｒ２）＝ｅＬ（Ψ（Ｒ１）、Ｒ２）と定義してもよい。
（参考文献４）  A.Joux and K.Nguyen、 “Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups”、
http://eprint.iacr.org/2001/003/
【００７４】
次に、射影ペアリングを用いた演算について説明する。
上記射影ペアリングｅ（Ｒ１、Ｒ２）には、同じ巡回群上の２点Ｒ１、Ｒ２及びａ、ｂ∈ＺＬに関して、
【数４１】
2006201719.tif 000038
という性質がある。この性質は、射影ペアリングｅ（Ｒ１、Ｒ２）がｅ（Ｒ１、Ｒ２）＝ｅＬ（Ψ（Ｒ１）、Ｒ２）と定義された場合なども同様である。
【００７５】
従って、Ｅ［Ｌ］上のフロベニウス写像の非固有空間上の点Ｒで生成される巡回群に関して、
【数４２】
2006201719.tif 000039
が成り立つ。ここでｇ＝ｅ（Ｒ、Ｒ）とおけば、
【数４３】
2006201719.tif 000040
と表すことができる。そこで、例えば（Ｐ０、Ｐ１、Ｐ２）＝（Ｒ、ｘＲ、ｘ２Ｒ）として、（Ｐ０、Ｐ１、Ｐ２）の３個のデータを準備すると、この３個のデータから適宜２つのデータを選んで射影ペアリングを演算することによって、
【数４４】
2006201719.tif 000041
という５個のデータｇｙ（ｙ＝ｘｓ、ｓ＝０、１、２、３、４）を得ることができる。つまり、予め準備したべき乗データＰｗ（ｗ＝０、１、２）の個数を超えてデータｇｙ（ｙ＝ｘｓ、ｓ＝０、１、２、３、４）を演算できることになる。ところで、上記例のｇｙの生成方法の場合には、
【数４５】
2006201719.tif 000042
のように、同じデータに対して２つの演算方法がある。この場合は、いずれか一方の射影ペアリング演算からデータｇｙ（ｙ＝ｘ２）を求めればよい。
【００７６】
同じ３個のデータであっても、例えば（Ｐ０、Ｐ１、Ｐ２）＝（Ｒ、ｘＲ、ｘ３Ｒ）として予め準備すれば、
【数４６】
2006201719.tif 000043
のように、より多く６個のデータｇｙ（ｙ＝ｘｓ、ｓ＝０、１、２、３、４、６）を演算できる。但し、この例でｇｙ（ｙ＝ｘ５）が演算できないように、演算できないデータｇｙが存在する場合がある。このような場合には、所望のデータｇｙが得られるように、べき乗データＰｗを準備する。この例の場合では、例えば、（Ｐ０、Ｐ１、Ｐ２、Ｐ３）＝（Ｒ、ｘＲ、ｘ３Ｒ、ｘ５Ｒ）として予め４個のデータを準備すればよい。
【００７７】
一般に、ｎ個のべき乗データＰ０、Ｐ１、・・・、Ｐｎ−１から作ることのできるデータｇｙの総数は、最大の場合で、ｎ個の要素から重複を許して２個組み合わせる組み合わせの総数ｎ（ｎ＋１）／２に等しい。換言すれば、所望のｍ個のデータｇｙは、データｇｙの個数（ｍ個）よりも少ない（具体的にはｍの平方根程度ないし半分程度の）ｎ個のべき乗データＰ０、Ｐ１、・・・、Ｐｎ−１から作ることできる。
【００７８】
以上の射影ペアリングの性質を用いて、多項式ｆ（ｘ）を指数とした、ある群の元ｇに対する多項式べき乗演算は次のようになる。なお、群の元ｇは、ｇ＝ｅ（Ｒ、Ｒ）を満たすものとする。換言すれば、射影ペアリングが、ペアリングにおけるいずれか一方の被演算子が線形変換Ψを施されたものである場合には、ｇ＝ｅ（Ｒ、Ｒ）となる元Ｒを、楕円曲線ＥのＬ等分点集合Ｅ［Ｌ］のフロベニウス写像の非固有空間上の元から選択する。また、射影ペアリングが、ペアリングにおけるいずれか一方の被演算子が線形変換Ψの逆演算ｄｉｓを施されたものである場合には、ｇ＝ｅ（Ｒ、Ｒ）となる元Ｒを、超特異楕円曲線ＥのＬ等分点集合Ｅ［Ｌ］のフロベニウス写像の固有空間上の元から選択する。
【００７９】
ｍ個の項からなる多項式ｆ（ｘ）が、係数ａ＿ｉ〔但し、ｉ＝０、１、２、・・・、ｍ−１とする。〕及び指数ｃ＿ｉによって
【数４７】
2006201719.tif 000044
と表されるとする。なお、同じ指数の複数の項は、その各項の係数の和を係数とした１つの項にまとめることができるから、ここでは、指数ｃ＿ｉはどの２つも等しくないとする。
【００８０】
二者Ａ、Ｂにおいて、Ｂは多項式ｆ（ｘ）の引数ｘと、ｇ＝ｅ（Ｒ、Ｒ）となる元Ｒと、ｎ個の指数構成値ｄ＿ｗ〔但し、ｗ＝０、１、２、・・・、ｎ−１とし、かつ、ｎ＜ｍとする。〕を把握している。ここで、指数構成値ｄ＿ｗは、多項式ｆ（ｘ）の各項の指数ｃ＿ｉとの間に
【数４８】
2006201719.tif 000045
が成り立つものである。また、ｎ個の指数構成値ｄ＿ｗは、べき乗データＰ＿ｗが重複して生成されることによるデータ数の増加を防ぐ観点から、どの２つも等しくないものとするのがよい。なお、引数ｘは、多項式ｆ（ｘ）の不定元（変数）から１つ選択されたものである。
【００８１】
一方Ａは、多項式ｆ（ｘ）の係数ａ＿ｉを把握している。またＡは、各係数ａ＿ｉに対応する、ｎ個のべき乗データＰ＿ｗのうち２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉ（べき乗データＰ＿ｊｉ、Ｐ＿ｋｉはそれぞれ、多項式ｆ（ｘ）における係数ａ＿ｉの項の指数ｃ＿ｉを構成する指数構成値ｄ＿ｊｉ、ｄ＿ｋｉから得られるものである。）を示す対応テーブルも把握している。より具体的には、係数ａ＿０に対応するべき乗データ（Ｐ＿ｊ０、Ｐ＿ｋ０）、係数ａ＿１に対応するべき乗データ（ｄ＿ｊ１、ｄ＿ｋ１）、係数ａ＿２に対応するべき乗データ（ｄ＿ｊ２、ｄ＿ｋ２）、・・・、係数ａ＿（ｍ−１）に対応するべき乗データ（ｄ＿ｊｍ−１、ｄ＿ｋｍ−１）を示すものである。そして、これらのｎ個の具体的なべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ（ｎ−１）の値はＢから与えられる。換言すれば、Ａは、多項式ｆ（ｘ）の各項の指数ｃ＿ｉ（ｍ個）を［数４８］に従って表すことのできる指数構成値ｄ＿ｗ（ｎ個；ｍ個よりも少ない個数である。）を用いたべき乗データＰ＿ｗ（ｎ個）をＢにおいて生成してもらうのである。
なお、係数ａ＿ｉ、引数ｘ、指数ｃ＿ｉ、指数構成値ｄ＿ｉはいずれも元ｇの位数を上限とする０以上の整数である。
【００８２】
このときＢは、ｇ＝ｅ（Ｒ、Ｒ）となる元Ｒを、指数構成値ｄ＿ｗを指数とした引数ｘのべき乗で楕円スカラー倍したべき乗データＰ＿ｗ＝ｘｄ＿ｗＲを求める。そしてＢは、ｎ個のべき乗データＰ＿０、Ｐ＿１、・・・、Ｐ＿（ｎ−１）及び対応テーブルをＡに渡す。
【００８３】
ｎ個のべき乗データＰ＿０、Ｐ＿１、・・・、Ｐ＿（ｎ−１）を受けたＡでは、係数ａ＿ｉに対応する２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉを示す上記対応テーブルに従って、各係数ａ＿ｉにつき、係数ａ＿ｉに対応する２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉの具体的な値を得ることとなる。そして、係数ａ＿ｉと、係数ａ＿ｉに対応する２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉとから、ａ＿ｉを指数とした射影ペアリングｅ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）のべき乗ｅ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）ａ＿ｉを演算する。さらに、このｍ個のべき乗射影ペアリング演算結果ｅ（Ｐ＿ｊ０、Ｐ＿ｋ０）ａ＿０、ｅ（Ｐ＿ｊ１、Ｐ＿ｋ１）ａ＿１、ｅ（Ｐ＿ｊ２、Ｐ＿ｋ２）ａ＿２、・・・、ｅ（Ｐ＿ｊｍ−１、Ｐ＿ｋｍ−１）ａ＿（ｍ−１）を掛け合わせる演算
【数４９】
2006201719.tif 000046
によって多項式べき乗演算結果ｇｆ（ｘ）を得る。
【００８４】
なぜなら、［数４９］について、次式が成立するからである。
【数５０】
2006201719.tif 000047
【００８５】
次に、本発明の実施の形態を、図面を参照して説明する。
なお、ここでは本実施形態の多項式べき乗演算装置の構成及び処理を順次説明し、次いで多項式べき乗演算装置を用いた多項式べき乗演算方法について説明する。
【００８６】
＜多項式べき乗演算装置＞
図１は、多項式べき乗演算装置（１）のハードウェア構成を例示した構成ブロック図である。図１に例示するように、多項式べき乗演算装置（１）は、キーボードなどが接続可能な入力部（１１）、液晶ディスプレイなどが接続可能な出力部（１２）、多項式べき乗演算装置（１）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（１３）、ＣＰＵ（Central Processing Unit）（１４）、メモリであるＲＡＭ（１５）、ＲＯＭ（１６）やハードディスクである外部記憶装置（１７）並びにこれらの入力部（１１）、出力部（１２）、通信部（１３）、ＣＰＵ（１４）、ＲＡＭ（１５）、ＲＯＭ（１６）、外部記憶装置（１７）間のデータのやり取りが可能なように接続するバス（１８）を有している。また必要に応じて、多項式べき乗演算装置（１）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【００８７】
多項式べき乗演算装置（１）の外部記憶装置（１７）には、多項式べき乗演算結果ｇｆ（ｘ）を得るためのプログラムが保存記憶され、このプログラムの処理において必要となるデータ及びプログラムの処理によって得られた値などを保存記憶するデータ格納領域（１７１）が確保されている。
【００８８】
より具体的には、外部記憶装置（１７）のデータ格納領域（１７１）には、ｍ個の係数ａ＿０、ａ＿１、ａ＿２、・・・、ａ＿（ｍ−１）と、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）と、各係数ａ＿ｉ（ｉ＝０、１、２、・・・、ｍ−１）に対応する、ｎ個のべき乗データＰ＿ｗ（ｗ＝０、１、２、・・・、ｎ−１）のうち、多項式ｆ（ｘ）における係数ａ＿ｉの項の指数ｃ＿ｉを構成する指数構成値ｄ＿ｊｉ、ｄ＿ｋｉから得られた２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉを示す対応テーブルが保存記憶される。
【００８９】
また、多項式べき乗演算結果ｇｆ（ｘ）を得るためのプログラムは、対応テーブルを参照して、各係数ａ＿ｉに対応する２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉを読み出す参照プログラム（１７２）、各係数について、係数とその係数に対応して読み出された２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉの射影ペアリングからべき乗射影ペアリングを演算するべき乗射影ペアリング演算プログラム（１７３）、ｍ個のべき乗射影ペアリング演算結果の積を演算する積演算プログラム（１７４）である。また、各係数について対応テーブルから対応するべき乗データを読み出し、べき乗射影ペアリングの演算を行うことなどを制御する制御プラグラム（１７５）がある。これらのプログラムが外部記憶装置（１７）に保存記憶される。さらに、これらのプログラムの処理によって得られる値は、外部記憶装置（１７）のデータ格納領域（１７１）に保存記憶される。
【００９０】
多項式べき乗演算装置（１）では、外部記憶装置（１７）に記憶されたプログラムとこのプログラムの処理に必要なデータが必要に応じてＲＡＭ（１５）に呼び出されて、順次ＣＰＵ（１４）で処理されることで、多項式べき乗演算結果ｇｆ（ｘ）を得る。
【００９１】
図２は、多項式べき乗演算装置（１）のＣＰＵ（１４）において上記所定のプログラムが処理されることにより、多項式べき乗演算結果ｇｆ（ｘ）が得られる処理機能を示す機能ブロック図である。図３は、多項式べき乗演算装置（１）において、多項式べき乗演算結果ｇｆ（ｘ）を得る演算処理を示すフローチャートである。
以下、多項式べき乗演算装置（１）において、多項式べき乗演算結果ｇｆ（ｘ）を得る演算処理の流れを順次説明する。
【００９２】
ｍ個の係数ａ＿０、ａ＿１、ａ＿２、・・・、ａ＿（ｍ−１）と、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）は、予めデータ格納領域（１７１）に保存記憶されている。ここでｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）は、有限体上定義された楕円曲線Ｅ（超特異楕円曲線でも非超特異楕円曲線でもよい。）におけるＬ等分点集合Ｅ［Ｌ］のフロベニウス写像φｓの非固有空間上における位数Ｌの巡回群の元Ｒから生成されるものとする。また、この実施形態において射影ペアリングｅ（Ｒ１、Ｒ２）は、ペアリングｅＬ（Ｒ１、Ψ（Ｒ２））とする（ペアリングｅＬ（Ψ（Ｒ１）、Ｒ２）でも演算処理結果は同じである。）。
【００９３】
また、各係数ａ＿ｉ（ｉ＝０、１、２、・・・、ｍ−１）に対応する、多項式ｆ（ｘ）における係数ａ＿ｉの項の指数ｃ＿ｉを構成する指数構成値ｄ＿ｊｉ、ｄ＿ｋｉから得られた２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉを示す対応テーブルも、予めデータ格納領域（１７１）保存記憶されている。
【００９４】
本実施形態における対応テーブルは、パラメータ係数対応テーブル（１９１）及びパラメータべき乗データ対応テーブル（１９２）から構成されるものとする。図４（ａ）に、パラメータ係数対応テーブル及びパラメータ係数対応テーブルに示されるアドレスの記憶領域に係数ａ＿ｉの値が格納されていることの関係を示す概念図を、図４（ｂ）に、パラメータべき乗データ対応テーブル及びパラメータべき乗データ対応テーブルに示されるアドレスの記憶領域にべき乗データＰ＿０、Ｐ＿１、・・・、Ｐ＿（ｎ−１）の値が格納されていることの関係を示す概念図を示す。ここでパラメータとは、下記に説明する制御部によってループ処理を実行する際のパラメータであり、説明の便宜から記号ｉ＝０、１、２、・・・、ｍ−１をもって表す。
【００９５】
パラメータ係数対応テーブル（１９１）は、パラメータｉに対応する、係数ａ＿ｉの記憶領域におけるアドレスが記録されたデータである。また、パラメータべき乗データ対応テーブル（１９２）は、パラメータｉ＝０に対応する２つのべき乗データＰ＿ｊ０、Ｐ＿ｋ０が記憶される領域のそれぞれのアドレスを、パラメータｉ＝１に対応する２つのべき乗データＰ＿ｊ１、Ｐ＿ｋ１が記憶される領域のそれぞれのアドレスを、パラメータｉ＝２に対応する２つのべき乗データＰ＿ｊ２、Ｐ＿ｋ２が記憶される領域のそれぞれのアドレスを、・・・、パラメータｉ＝ｍ−１に対応する２つのべき乗データＰ＿ｊｍ−１、Ｐ＿ｋｍ−１が記憶される領域のそれぞれのアドレスを記録したデータである（図４（ａ）及び図４（ｂ）に示すアドレスは例示である。）。
【００９６】
つまり、パラメータ係数対応テーブル（１９１）では、あるパラメータｉが１つ与えられた場合に、そのパラメータに対応した係数ａ＿ｉが記憶される領域のアドレスを得られるようになっており、パラメータべき乗データ対応テーブル（１９２）では、あるパラメータｉが１つ与えられた場合に、そのパラメータに対応した２つのべき乗データＰ＿ｊｉ、Ｐ＿ｋｉが記憶される領域のアドレスが記憶される領域のアドレスを得られるようになっている。そして、パラメータ係数対応テーブル（１９１）において指定されるアドレスそれぞれの記憶領域には各係数の値が記憶されており、パラメータべき乗データ対応テーブル（１９２）において指定されるアドレスそれぞれの記憶領域には各べき乗データの値が記憶されている。
このように、係数ａ＿ｉと２つのべき乗データ（Ｐ＿ｊｉ、Ｐ＿ｋｉ）とは、パラメータｉを介して対応付けられたものとなっている。
【００９７】
まず、予め外部記憶装置（１７）に記憶されている係数ａ＿０、ａ＿１、ａ＿２、・・・、ａ＿（ｍ−１）、べき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）、パラメータ係数対応テーブル、パラメータべき乗データ対応テーブルが、メモリ（ここではＲＡＭ（１５）とする。）上に読み込まれ、ＲＡＭ（１５）上の所定の格納領域に格納される。即ち、ｍ個の係数ａ＿０、ａ＿１、ａ＿２、・・・、ａ＿（ｍ−１）は、ＲＡＭ（１５）上の係数格納領域（１５３）に格納され、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）は、ＲＡＭ（１５）上のべき乗データ格納領域（１５４）に格納され、パラメータ係数対応テーブルは、ＲＡＭ（１５）上の対応テーブル格納領域（１５１）に格納され、パラメータべき乗データ対応テーブルは、ＲＡＭ（１５）上の対応テーブル格納領域（１５２）に格納される。
【００９８】
次いで、制御部（１４１）の制御の下、パラメータｉ＝０、１、２、・・・、ｍ−１について下記の処理を行う。なお、制御部（１４１）は、１つのパラメータについて所定の処理を終了すると、次のパラメータについて所定の処理を実行するループ処理を行うようになっている。本実施形態では、所定の処理をパラメータｉ＝０、ｉ＝１、ｉ＝２、・・・、ｉ＝ｍ−１の順序で実行する。
【００９９】
まず、参照部（１４２）は、制御部（１４１）の制御を受けて、パラメータｉ＝０の場合について（Ｓ１１）、このパラメータに対応する係数ａ＿０のアドレスをパラメータ係数対応テーブル格納領域（１５１）に格納されたパラメータ係数対応テーブル（１９１）を参照して取得する。参照部（１４２）は、取得したアドレスから、係数格納領域（１５３）に格納される係数ａ＿０を取得して、この係数ａ＿０をＲＡＭ（１５）上の抽出係数格納領域（１５５）に格納する（Ｓ１２）。
【０１００】
続いて、参照部（１４２）は、制御部（１４１）の制御を受けて、パラメータｉ＝０に対応する２つのべき乗データＰ＿ｊ０、Ｐ＿ｋ０のアドレスを、パラメータべき乗データ対応テーブル格納領域（１５２）に格納されたパラメータべき乗データ対応テーブル（１９２）を参照して取得する。参照部（１４２）は、取得したアドレスから、べき乗データ格納領域（１５４）に格納される２つのべき乗データＰ＿ｊ０、Ｐ＿ｋ０を取得して、この２つのべき乗データＰ＿ｊ０、Ｐ＿ｋ０をＲＡＭ（１５）上の抽出べき乗データ格納領域（１５６）に格納する（Ｓ１３）。
【０１０１】
続いて、べき乗射影ペアリング演算部（１４３）において、抽出係数格納領域（１５５）に格納される係数ａ＿０及び、抽出べき乗データ格納領域（１５６）に格納される２つのべき乗データＰ＿ｊ０、Ｐ＿ｋ０を読み出し、射影ペアリングｅ（Ｐ＿ｊ０、Ｐ＿ｋ０）のａ＿０を指数としたべき乗ｅ（Ｐ＿ｊ０、Ｐ＿ｋ０）ａ＿０を演算し、この演算結果をＲＡＭ（１５）上のべき乗射影ペアリング演算結果格納領域（１５７）に格納する（Ｓ１４）。
【０１０２】
次に、参照部（１４２）は、制御部（１４１）の制御を受けて、パラメータｉ＝１の場合について（Ｓ１５、Ｓ１６）、このパラメータに対応する係数ａ＿１のアドレスをパラメータ係数対応テーブル格納領域（１５１）に格納されたパラメータ係数対応テーブル（１９１）を参照して取得する。参照部（１４２）は、取得したアドレスから、係数格納領域（１５３）に格納される係数ａ＿１を取得して、この係数ａ＿１をＲＡＭ（１５）上の抽出係数格納領域（１５５）に上書き格納する（ここで上書き格納とは、所定の格納領域に既に格納されているデータを解放して、新しくデータを当該格納領域に格納することをいう。）（Ｓ１２）。
【０１０３】
続いて、参照部（１４２）は、制御部（１４１）の制御を受けて、パラメータｉ＝１に対応する２つのべき乗データＰ＿ｊ１、Ｐ＿ｋ１のアドレスを、パラメータべき乗データ対応テーブル格納領域（１５２）に格納されたパラメータべき乗データ対応テーブル（１９２）を参照して取得する。参照部（１４２）は、取得したアドレスから、べき乗データ格納領域（１５４）に格納される２つのべき乗データＰ＿ｊ１、Ｐ＿ｋ１を取得して、この２つのべき乗データＰ＿ｊ１、Ｐ＿ｋ１をＲＡＭ（１５）上の抽出べき乗データ格納領域（１５６）に上書き格納する（Ｓ１３）。
【０１０４】
続いて、べき乗射影ペアリング演算部（１４３）において、抽出係数格納領域（１５５）に格納される係数ａ＿１及び、抽出べき乗データ格納領域（１５６）に格納される２つのべき乗データＰ＿ｊ１、Ｐ＿ｋ１を読み出し、射影ペアリングｅ（Ｐ＿ｊ１、Ｐ＿ｋ１）のａ＿１を指数としたべき乗ｅ（Ｐ＿ｊ１、Ｐ＿ｋ１）ａ＿１を演算し、この演算結果をＲＡＭ（１５）上のべき乗射影ペアリング演算結果格納領域（１５７）に格納する（Ｓ１４）。
【０１０５】
爾後、制御部（１４１）の制御の下で、パラメータｉ＝２、３、・・・、ｍ−１についても同様の処理を繰り返す（Ｓ１４、Ｓ１５）。この処理が繰り返された結果、べき乗射影ペアリング演算結果格納領域（１５７）には、ｅ（Ｐ＿ｊ０、Ｐ＿ｋ０）ａ＿０、ｅ（Ｐ＿ｊ１、Ｐ＿ｋ１）ａ＿１、・・・、ｅ（Ｐ＿ｊｍ−１、Ｐ＿ｋｍ−１）ａ＿（ｍ−１）のｍ個のべき乗射影ペアリング演算結果が格納される。そこで、積演算部（１４４）において、べき乗射影ペアリング演算結果格納領域（１５７）からｅ（Ｐ＿ｊ０、Ｐ＿ｋ０）ａ＿０、ｅ（Ｐ＿ｊ１、Ｐ＿ｋ１）ａ＿１、・・・、ｅ（Ｐ＿ｊｍ−１、Ｐ＿ｋｍ−１）ａ＿（ｍ−１）のｍ個のべき乗射影ペアリング演算結果を読み出し、これらの積の演算を行い、この演算結果をＲＡＭ（１５）上の多項式べき乗演算結果格納領域（１５８）に格納する（Ｓ１７）。多項式べき乗演算結果格納領域（１５８）に格納される演算結果が多項式べき乗演算結果ｇｆ（ｘ）である。
【０１０６】
以上のようにしてＲＡＭ（１５）の多項式べき乗演算結果格納領域（１５８）に、多項式べき乗演算結果ｇｆ（ｘ）が格納されるが、さらに、多項式べき乗演算結果ｇｆ（ｘ）を、外部記憶装置（１７）のデータ格納領域（１７１）に書き込みを行って保存記憶する。
【０１０７】
上記の実施形態では、元Ｒが、有限体上定義された楕円曲線Ｅ（超特異楕円曲線でも非超特異楕円曲線でもよい。）におけるＬ等分点集合Ｅ［Ｌ］のフロベニウス写像φｓの非固有空間上における位数Ｌの巡回群の元であり、演算する射影ペアリングｅ（Ｒ１、Ｒ２）は、ペアリングｅＬ（Ｒ１、Ψ（Ｒ２））（あるいは、ペアリングｅＬ（Ψ（Ｒ１）、Ｒ２）であるとした。しかし元Ｒは、有限体上定義された超特異楕円曲線ＥにおけるＬ等分点集合Ｅ［Ｌ］のフロベニウス写像φｓの固有空間上における位数Ｌの巡回群の元としてもよく、この場合には、演算する射影ペアリングｅ（Ｒ１、Ｒ２）は、ペアリングｅＬ（ｄｉｓ（Ｒ１）、Ｒ２）（あるいは、ペアリングｅＬ（Ｒ１、ｄｉｓ（Ｒ２））である。）とすることができる。そして、この場合における多項式べき乗演算装置のハードウェア構成、多項式べき乗演算装置のＣＰＵにおいて所定のプログラムが処理されることによって多項式べき乗演算結果ｇｆ（ｘ）を得る処理機能、多項式べき乗演算装置において多項式べき乗演算結果ｇｆ（ｘ）を得る演算処理の処理手順は、上述した実施形態の場合と何ら異なるものではない。
【０１０８】
本発明である多項式べき乗演算装置は上述の実施の形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記多項式べき乗演算装置において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
また、上記多項式べき乗演算装置における処理機能をコンピュータによって実現する場合、多項式べき乗演算装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記多項式べき乗演算装置における処理機能がコンピュータ上で実現される。
【０１０９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１１０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、多項式べき乗演算装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１１３】
＜多項式べき乗演算方法＞
続いて、図８を参照して、上記の多項式べき乗演算装置（１）を利用した多項式べき乗演算方法の一例を説明する。
図８は、多項式べき乗演算装置（１）を利用した多項式べき乗演算方法の実施構成例を示す図である。
【０１１４】
図８に示す上記の多項式べき乗演算装置（１）を利用した多項式べき乗演算方法においては、多項式べき乗演算装置（１）とは別にべき乗データ生成装置（２）を用いる。
【０１１５】
べき乗データ生成装置（２）は、上述したｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を生成する装置である。
図５は、べき乗データ生成装置（２）のハードウェア構成を例示した構成ブロック図である。図５に例示するように、べき乗データ生成装置（２）は、キーボードなどが接続可能な入力部（２１）、液晶ディスプレイなどが接続可能な出力部（２２）、べき乗データ生成装置（２）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（２３）、ＣＰＵ（Central Processing Unit）（２４）、メモリであるＲＡＭ（２５）、ＲＯＭ（２６）やハードディスクである外部記憶装置（２７）並びにこれらの入力部（２１）、出力部（２２）、通信部（２３）、ＣＰＵ（２４）、ＲＡＭ（２５）、ＲＯＭ（２６）、外部記憶装置（２７）間のデータのやり取りが可能なように接続するバス（２８）を有している。また必要に応じて、べき乗データ生成装置（２）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【０１１６】
べき乗データ生成装置（２）の外部記憶装置（２７）には、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を生成するためのプログラムが保存記憶され、このプログラムの処理において必要となるデータ及びプログラムの処理によって得られた値などを保存記憶するデータ格納領域（２７１）が確保されている。
【０１１７】
より具体的には、外部記憶装置（２７）のデータ格納領域（２７１）には、ｎ個の指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）、元Ｒ、引数ｘが保存記憶される。また、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を生成するためのプログラムは、引数ｘのべき乗を演算する引数べき乗演算プログラム（２７２）、元Ｒの楕円スカラー倍を演算する楕円スカラー倍演算プログラム（２７３）である。
【０１１８】
また、各指数構成値について引数ｘのべき乗を演算し、この各演算結果で元Ｒを楕円スカラー倍演算することなどを制御する制御プラグラム（２７４）がある。これらのプログラムが外部記憶装置（２７）に保存記憶される。さらに、これらのプログラムの処理によって得られる値は、外部記憶装置（２７）のデータ格納領域（２７１）に保存記憶される。
【０１１９】
べき乗データ生成装置（２）では、外部記憶装置（２７）に記憶されたプログラムとこのプログラムの処理に必要なデータが必要に応じてＲＡＭ（２５）に呼び出されて、順次ＣＰＵ（２４）で処理されることで、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を生成する。
【０１２０】
図６は、べき乗データ生成装置（２）のＣＰＵ（２４）において上記所定のプログラムが処理されることにより、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を生成することを示す機能ブロック図である。図７は、べき乗データ生成装置（２）において、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を生成する演算処理を示すフローチャートである。
以下、べき乗データ生成装置（２）において、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を生成する演算処理の流れを順次説明する。
【０１２１】
元Ｒ、引数ｘ、ｎ個の指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）は、予め外部記憶装置（２７）のデータ格納領域（２７１）に保存記憶されている。
【０１２２】
まず、予め外部記憶装置（２７）に記憶されている元Ｒ、引数ｘ、ｎ個の指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）が、メモリ（ここではＲＡＭ（２５）とする。）上に読み込まれ、ＲＡＭ（２５）上の所定の格納領域に格納される。即ち、元Ｒは、ＲＡＭ（２５）上の元格納領域（２５３）に格納され、ｎ個の指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）は、ＲＡＭ（２５）上の指数構成値格納領域（２５２）に格納され、引数ｘは、ＲＡＭ（２５）上の引数格納領域（２５１）に格納される。
【０１２３】
次いで、制御部（２４１）の制御の下、各指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）について下記の処理を行う。なお、制御部（２４１）は、１つの指数構成値について所定の処理を終了すると、次の指数構成値について所定の処理を実行するループ処理を行うようになっている。従って、例えば、所定の処理を指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）の順序で実行することで、全ての指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）について所定の処理が実行されることになる。
【０１２４】
まず、引数べき乗部（２４２）は、制御部（２４１）の制御を受けて、指数構成値格納領域（２５２）から指数構成値ｄ＿０を読み出し（Ｓ２１）、引数格納領域（２５１）から読み出した引数ｘのべき乗ｘｄ＿０を演算し、この演算結果をべき乗引数格納領域（２５４）に格納する（Ｓ２２）。続いて、楕円スカラー倍演算部（２４３）は、制御部（２４１）の制御を受けて、べき乗引数格納領域（２５４）からべき乗演算結果ｘｄ＿０を読み出し、元格納領域（２５３）から読み出した元Ｒの楕円スカラー倍演算Ｐ＿０＝ｘｄ＿０Ｒを演算し、この演算結果をべき乗データ格納領域（２５５）に格納する（Ｓ２３）。
【０１２５】
続いて、引数べき乗部（２４２）は、制御部（２４１）の制御を受けて、指数構成値格納領域（２５２）から指数構成値ｄ＿１を読み出し（Ｓ２４、Ｓ２５）、引数格納領域（２５１）から読み出した引数ｘのべき乗ｘｄ＿１を演算し、この演算結果をべき乗引数格納領域（２５４）に格納する（Ｓ２３）。さらに、楕円スカラー倍演算部（２４３）は、制御部（２４１）の制御を受けて、べき乗引数格納領域（２５４）からべき乗演算結果ｘｄ＿１を読み出し、元格納領域（２５３）から読み出した元Ｒの楕円スカラー倍演算Ｐ＿１＝ｘｄ＿１Ｒを演算し、この演算結果をべき乗データ格納領域（２５５）に格納する（Ｓ２４）。
【０１２６】
爾後、制御部（２４１）の制御の下、指数構成値ｄ＿２、・・・、ｄ＿（ｎ−１）についても同様の処理を繰り返す（Ｓ２４、Ｓ２５）。この処理が繰り返された結果、べき乗データ格納領域（２５５）には、Ｐ＿０＝ｘｄ＿０Ｒ、Ｐ＿１＝ｘｄ＿１Ｒ、Ｐ＿２＝ｘｄ＿２Ｒ、・・・、Ｐ＿（ｎ−１）＝ｘｄ＿（ｎ−１）Ｒのｎ個のべき乗データが格納される。
【０１２７】
以上のようにしてＲＡＭ（２５）のべき乗データ格納領域（２５５）に、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）が格納されるが、さらに、ｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を、外部記憶装置（２７）のデータ格納領域（２７１）に書き込みを行って保存記憶する。
以上のようにして、べき乗データ生成装置（２）においてｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）が生成される。
【０１２８】
ところで、多項式べき乗演算装置（１）は、通信部（１３）に通信装置（例えば、同軸ケーブルや光ファイバなどの通信ケーブル）を接続することで外部（インターネットなどのネットワーク）と通信可能であり、べき乗データ生成装置（２）も、通信部（２３）に通信装置（例えば、同軸ケーブルや光ファイバなどの通信ケーブル）を接続することで外部（インターネットなどのネットワーク）と通信可能である。従って例えば、多項式べき乗演算装置（１）とべき乗データ生成装置（２）は、インターネットやＬＡＮ（Local Area Network）などのネットワーク（３）に通信可能に接続されることで、ネットワーク（３）を介して、べき乗データ生成装置（２）から多項式べき乗演算装置（１）へｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を送信することができる。
【０１２９】
このような構成において、べき乗データ生成装置（２）で生成されたｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を、べき乗データ生成装置（２）から多項式べき乗演算装置（１）に送信することによって、多項式べき乗演算装置（１）の記憶装置（１７）にｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を保存記憶することができる。
【０１３０】
多項式べき乗演算装置（１）では、以上のようにして記憶装置（１７）に保存記憶されたｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を用いて多項式べき乗演算結果ｇｆ（ｘ）を得ることができるが、その演算処理などは上述したとおりである。
【０１３１】
このような多項式べき乗演算方法によれば、べき乗データ生成装置（２）でｎ個のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿（ｎ−１）を生成するために用いた引数ｘを用いることなく、多項式べき乗演算装置（１）において多項式べき乗演算結果ｇｆ（ｘ）を得ることができる。
【０１３２】
上述のとおり、一般に、ｎ個のべき乗データＰ０、Ｐ１、・・・、Ｐｎ−１から選ばれる２つのべき乗データで作ることのできるデータ（つまり、多項式ｆ（ｘ）におけるべき乗項ｘｃ＿ｉを指数とする元ｇのべき乗の値である。）の総数は、最大の場合で、ｎ個の要素から重複を許して２個組み合わせる組み合わせの総数ｎ（ｎ＋１）／２に等しい。
【０１３３】
従って、例えば多項式ｆ（ｘ）の項数が５０５０個（ｍ＝５０５０）とすると、最小１００個（ｎ＝１００）のべき乗データＰ＿０、Ｐ＿１、Ｐ＿２、・・・、Ｐ＿１００から、多項式ｆ（ｘ）におけるべき乗項ｘｃ＿０、ｘｃ＿１、ｘｃ＿２、・・・、ｘｃ＿５０４９のそれぞれを指数とする元ｇのべき乗の値を求めることができる。ここで、一般に楕円曲線上の点が乗法群の点と同程度の情報量であることに鑑みると、べき乗データ生成装置（２）から多項式べき乗演算装置（１）に送信される１００個のべき乗データのデータ量は、従来技術において送信されていた５０５０個のべき乗データに比べて約１／５０に低減されたものとなっている。
【０１３４】
また、楕円曲線が超特異楕円曲線の場合には、一般に楕円曲線上の点は乗法群の点の約１／２ないし１／６程度の情報量となるので、ｍ＝５０５０の場合では、べき乗データ生成装置（２）から多項式べき乗演算装置（１）に送信される１００個のべき乗データのデータ量は、従来技術において送信されていた５０５０個のべき乗データに比べて約１／１００ないし１／３００程度に低減されたものとなる。
【０１３５】
なお、べき乗データ生成装置（２）で生成されるｎ個のべき乗データＰ＿ｗは、多項式べき乗演算装置（１）において演算される射影ペアリングに対応した元Ｒによって生成されるものである。つまり、多項式べき乗演算装置（１）において演算される射影ペアリングが、ペアリングにおけるいずれか一方の被演算子が線形変換Ψを施されたものである場合には、元Ｒは、有限体上定義された楕円曲線（超特異楕円曲線でも非超特異楕円曲線でもよい。）Ｅ上におけるＬ等分点の集合Ｅ［Ｌ］のフロベニウス写像φｓの非固有空間上における位数Ｌの巡回群の元とする。また、多項式べき乗演算装置（１）において演算される射影ペアリングが、ペアリングにおけるいずれか一方の被演算子が線形変換Ψの逆演算ｄｉｓを施されたものである場合には、元Ｒは、有限体上定義された超特異楕円曲線Ｅ上におけるＬ等分点の集合Ｅ［Ｌ］のフロベニウス写像φｓの固有空間上における位数Ｌの巡回群の元とする。
【０１３６】
上記実施形態では、ｎ個の指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）は、予め外部記憶装置（２７）のデータ格納領域（２７１）に保存記憶されているとした。しかし、このような実施形態に限定されるものではない。例えば、図示しない指数構成値登録サーバが、ネットワーク（３）にデータ通信可能に接続されているものとする。そして、この指数構成値登録サーバに、多項式べき乗演算装置（１）から予め［数４８］を満たすｎ個の指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）が送信されていて、その記憶装置にｎ個の指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）が保存記憶されているとする。そこで、べき乗データ生成装置（２）から指数構成値登録サーバにアクセスしてｎ個の指数構成値ｄ＿０、ｄ＿１、ｄ＿２、・・・、ｄ＿（ｎ−１）を取得し、この取得した指数構成値をべき乗データ生成装置（２）の記憶装置に保存記憶するとしてもよい。
【０１３７】
また、上記実施形態では、ｇ＝ｅ（Ｒ、Ｒ）なる元Ｒは、予め外部記憶装置（２７）のデータ格納領域（２７１）に保存記憶されているとした。しかし、このような実施形態に限定されるものではない。例えば、図示しない元登録サーバ（上記指数構成値登録サーバと同じでもよい。）が、ネットワーク（３）にデータ通信可能に接続されているものとする。そして、この元登録サーバに、多項式べき乗演算装置（１）から予めｇ＝ｅ（Ｒ、Ｒ）なる元Ｒが送信されていて、その記憶装置に元Ｒが保存記憶されているとする。そこで、べき乗データ生成装置（２）から元登録サーバにアクセスして元Ｒを取得し、この取得した元Ｒをべき乗データ生成装置（２）の記憶装置に保存記憶するとしてもよい。
【０１３８】
ところで、べき乗データ生成装置は上述の実施の形態に限定されるものではなく適宜変更が可能である。また、上記べき乗データ生成装置において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。また、上記べき乗データ生成装置における処理機能をコンピュータによって実現する場合、べき乗データ生成装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記べき乗データ生成装置における処理機能がコンピュータ上で実現される。
【０１３９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１４０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１４１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１４２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、べき乗データ生成装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１４３】
本発明の多項式べき乗演算装置及び多項式べき乗演算方法は、参考文献１に示されるようなグループ署名などの情報セキュリティ技術において利用できる。
【図面の簡単な説明】
【０１４４】
【図１】多項式べき乗演算装置（１）のハードウェア構成を例示した構成ブロック図。
【図２】多項式べき乗演算装置（１）において多項式べき乗演算結果ｇｆ（ｘ）が得られる処理機能を示す機能ブロック図。
【図３】多項式べき乗演算装置（１）において多項式べき乗演算結果ｇｆ（ｘ）を得る演算処理を示すフローチャート。
【図４（ａ）】パラメータ係数対応テーブル及びパラメータ係数対応テーブルに示されるアドレスの記憶領域に係数ａ＿ｉの値が格納されていることの関係を示す概念図。
【図４（ｂ）】パラメータべき乗データ対応テーブル及びパラメータべき乗データ対応テーブルに示されるアドレスの記憶領域にべき乗データの値が格納されていることの関係を示す概念図。
【図５】べき乗データ生成装置（２）のハードウェア構成を例示した構成ブロック図。
【図６】べき乗データ生成装置（２）においてべき乗データが得られる処理機能を示す機能ブロック図。
【図７】べき乗データ生成装置（２）においてべき乗データを得る演算処理を示すフローチャート。
【図８】多項式べき乗演算装置（１）を利用した多項式べき乗演算方法の実施構成例を示す図。
【符号の説明】
【０１４５】
１  多項式べき乗演算装置
２  べき乗データ生成装置
１４２  参照部
１４３  べき乗射影ペアリング演算部
１４４  積演算部
【図１】
2006201719.tif 000053
【図２】
2006201719.tif 000054
【図３】
2006201719.tif 000055
【図４（ａ）】
2006201719.tif 000056
【図４（ｂ）】
2006201719.tif 000057
【図５】
2006201719.tif 000058
【図６】
2006201719.tif 000059
【図７】
2006201719.tif 000060
【図８】
2006201719.tif 000061