(57)【特許請求の範囲】
【請求項１】
曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数をＦとして、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記埋め込み次数ｋに応じて前記整数変数χを用いて特定しておき、
前記ＣＰＵは、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、
Ｆを演算する演算手段と、
所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する演算手段と、
前記Ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算する演算手段と、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数１】
0005549018.tif 000108
として演算する演算手段と
を備えているペアリング演算装置。
【請求項２】
曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数をＦとして、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記埋め込み次数ｋに応じて前記整数変数χを用いて特定しておき、
前記電子計算機のＣＰＵを入力手段として機能させて、前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力するステップと、
前記電子計算機のＣＰＵを演算手段として機能させてＦを演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて前記Ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数２】
0005549018.tif 000109
として演算するステップと
を有するペアリング演算方法。
【請求項３】
曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数をＦとして、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記埋め込み次数ｋに応じて前記整数変数χを用いて特定しておき、
前記電子計算機のＣＰＵを、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、
Ｆを演算する演算手段、
所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値をそれぞれ演算する演算手段、
前記Ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算する演算手段、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数３】
0005549018.tif 000110
として演算する演算手段
として機能させるペアリング演算プログラムを記録した記録媒体。
【請求項４】
曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐＳをもつ有理点の集合、ＺＱをｐＱ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000111
として、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、前記整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
前記ＣＰＵは、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、
0005549018.tif 000112
を演算する第１演算手段と、
前記
0005549018.tif 000113
を演算する際に算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算手段と、
前記所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算手段と、
前記
0005549018.tif 000114
と、前記値を用いてｆ’χ，ｓ（Ｑ）を演算する第４演算手段と、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数４】
0005549018.tif 000115
として演算する第５演算手段と
を備えているペアリング演算装置。
【請求項５】
前記第２演算手段では、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）を順に既に得られた演算結果を用いてそれぞれ演算し、
前記第３演算手段では、
有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算し、
前記第４演算手段では、
【数５】
0005549018.tif 000116
として前記ｆ’χ，Ｓ（Ｑ）を演算する請求項４記載のペアリング演算装置。
【請求項６】
曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐＳをもつ有理点の集合、ＺＱをｐＱ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000117
として、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、前記整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
前記電子計算機のＣＰＵを入力手段として機能させて、前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力ステップと、
前記電子計算機のＣＰＵを第1演算手段として機能させて
0005549018.tif 000118
を演算する第１演算ステップと、
前記電子計算機のＣＰＵを第２演算手段として機能させて前記
0005549018.tif 000119
を演算する際に算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算ステップと、
前記電子計算機のＣＰＵを第３演算手段として機能させて前記所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算ステップと、
前記電子計算機のＣＰＵを第４演算手段として機能させて前記
0005549018.tif 000120
と、前記値を用いてｆ’χ，ｓ（Ｑ）を演算する第４演算ステップと、
前記電子計算機のＣＰＵを第５演算手段として機能させて前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数６】
0005549018.tif 000121
として演算する第５演算ステップと
を有するペアリング演算方法。
【請求項７】
前記第２演算スップでは、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）を順に既に得られた演算結果を用いてそれぞれ演算し、
前記第３演算ステップでは、
有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算し、
前記第４演算ステップでは、
【数７】
0005549018.tif 000122
として前記ｆ’χ，Ｓ（Ｑ）を演算する請求項６記載のペアリング演算方法。
【請求項８】
曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐＳをもつ有理点の集合、ＺＱをｐＱ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000123
として、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、前記整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
前記電子計算機のＣＰＵを、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、
0005549018.tif 000124
を演算する第１演算手段、
前記
0005549018.tif 000125
を演算する際に算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算手段、
前記所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算手段、
前記
0005549018.tif 000126
と、前記値を用いてf’χ,s(Q)を演算する第４演算手段、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数８】
0005549018.tif 000127
として演算する第５演算手段
として機能させるペアリング演算プログラムを記録した記録媒体。
【請求項９】
前記第２演算手段として機能する前記電子計算機のＣＰＵに、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）の演算を順に既に得られた演算結果を用いて実行させ、
前記第３演算手段として機能する前記電子計算機のＣＰＵに、
有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１の演算と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２の演算と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３の演算と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４の演算を実行させ、
前記第４演算手段として機能する前記電子計算機のＣＰＵに、
【数９】
0005549018.tif 000128
として前記ｆ’χ，Ｓ（Ｑ）の演算を実行させる請求項８記載のペアリング演算プログラムを記録した記録媒体。
【請求項１０】
曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐ３Ｓをもつ有理点の集合、ＺＱをｐ３Ｑ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000129
として、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、前記整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
前記ＣＰＵは、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、
0005549018.tif 000130
を演算する第１演算手段と、
有理点ｐ２（Ｓ）、ｐ２（ｐ３Ｓ）、（３χ＋１）Ｓ、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算手段と、
有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算手段と、
前記第１演算手段の演算結果と、前記第３演算手段の演算結果を用いて
【数１０】
0005549018.tif 000131
としてｆ’χ，ｓ（Ｑ）を演算する第４演算手段と、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数１１】
0005549018.tif 000132
として演算する第５演算手段と
を備えているペアリング演算装置。
【請求項１１】
曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐ３Ｓをもつ有理点の集合、ＺＱをｐ３Ｑ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000133
として、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、前記整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
前記電子計算機のＣＰＵを入力手段として機能させて、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力ステップと、
前記電子計算機のＣＰＵを第1演算手段として機能させて
0005549018.tif 000134
を演算する第１演算ステップと、
前記電子計算機のＣＰＵを第２演算手段として機能させて有理点ｐ２（Ｓ）、ｐ２（ｐ３Ｓ）、（３χ＋１）Ｓ、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算ステップと、
前記電子計算機のＣＰＵを第３演算手段として機能させて有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算ステップと、
前記電子計算機のＣＰＵを第４演算手段として機能させて前記ｆ’χ，Ｓ（Ｑ）と、前記値ｌ５、ｌ６、ｌ７、ｌ８、を用いて
【数１２】
0005549018.tif 000135
としてｆ’χ，ｓ（Ｑ）を演算する第４演算ステップと、
前記電子計算機のＣＰＵを第５演算手段として機能させて前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数１３】
0005549018.tif 000136
として演算する第５演算ステップと
を有するペアリング演算方法。
【請求項１２】
曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐ３Ｓをもつ有理点の集合、ＺＱをｐ３Ｑ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000137
として、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、前記整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
前記電子計算機のＣＰＵを、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、
0005549018.tif 000138
を演算する第１演算手段、
有理点ｐ２（Ｓ）、ｐ２（ｐ３Ｓ）、（３χ＋１）Ｓ、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算手段、
有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算手段、
前記ｆ’χ，Ｓ（Ｑ）と、前記値ｌ５、ｌ６、ｌ７、ｌ８を用いて
【数１４】
0005549018.tif 000139
としてｆ’χ，ｓ（Ｑ）を演算する第４演算手段、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数１５】
0005549018.tif 000140
として演算する第５演算手段
として機能させるペアリング演算プログラムを記録した記録媒体。
【請求項１３】
曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記埋め込み次数ｋに応じて前記整数変数χを用いて特定しておき、
前記ＣＰＵは、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、
ｆを演算する演算手段と、
所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する演算手段と、
前記ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算する演算手段と、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数１６】
0005549018.tif 000141
として演算する演算手段と
を備えているペアリング演算装置。
【請求項１４】
曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記埋め込み次数ｋに応じて前記整数変数χを用いて特定しておき、
前記電子計算機のＣＰＵを入力手段として機能させて、前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力するステップと、
前記電子計算機のＣＰＵを演算手段として機能させてｆを演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて前記ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数１７】
0005549018.tif 000142
として演算するステップと
を有するペアリング演算方法。
【請求項１５】
曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記埋め込み次数ｋに応じて前記整数変数χを用いて特定しておき、
前記電子計算機のＣＰＵを、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、
ｆを演算する演算手段、
所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値をそれぞれ演算する演算手段、
前記ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算する演算手段、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数１８】
0005549018.tif 000143
として演算する演算手段
として機能させるペアリング演算プログラムを記録した記録媒体。
【請求項１６】
曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ２χ，ｓ（Ｑ）として、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、前記整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
前記ＣＰＵは、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、
ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する第１演算手段と、
前記ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する際にそれぞれ算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算手段と、
前記所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算手段と、
前記ｆ２χ，ｓ（Ｑ）と、前記値を用いてｆ’χ，ｓ（Ｑ）を演算する第４演算手段と、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数１９】
0005549018.tif 000144
として演算する第５演算手段と
を備えているペアリング演算装置。
【請求項１７】
前記第２演算手段では、
有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）を順に既に得られた演算結果を用いてそれぞれ演算し、前記第３演算手段では、
有理点（２χ−１）Ｓ，−Ｓを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算し、
前記第４演算手段では前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１、ｌ２、ｌ３、ｌ４を用いて
【数２０】
0005549018.tif 000145
として前記ｆ’χ，Ｓ（Ｑ）を演算する請求項１６記載のペアリング演算装置。
【請求項１８】
曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ２χ，ｓ（Ｑ）として、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、前記整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
前記電子計算機のＣＰＵを入力手段として機能させて、前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力ステップと、
前記電子計算機のＣＰＵを第１演算手段として機能させてｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する第１演算ステップと、
前記電子計算機のＣＰＵを第２演算手段として機能させて前記ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）の演算の際にそれぞれ算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算ステップと、
前記電子計算機のＣＰＵを第３演算手段として機能させて前記所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算ステップと、
前記電子計算機のＣＰＵを第４演算手段として機能させて前記ｆ２χ，ｓ（Ｑ）と前記値を用いてｆ’χ，ｓ（Ｑ）を演算する第４演算ステップと、
前記電子計算機のＣＰＵを第５演算手段として機能させて前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数２１】
0005549018.tif 000146
として演算する第５演算ステップと
を有するペアリング演算方法。
【請求項１９】
前記第２演算ステップでは、
有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）を順に既に得られた演算結果を用いてそれぞれ演算し、
前記第３演算ステップでは、
有理点（２χ−１）Ｓ，−Ｓを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算し、
前記第４演算ステップでは前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１、ｌ２、ｌ３、ｌ４を用いて
【数２２】
0005549018.tif 000147
として前記ｆ’χ，Ｓ（Ｑ）を演算する請求項１８記載のペアリング演算方法。
【請求項２０】
曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ２χ，ｓ（Ｑ）として、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、前記整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
前記電子計算機のＣＰＵを、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、
ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する第１演算手段、
前記ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する際にそれぞれ算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算手段、
前記所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算手段、
前記ｆ２χ，ｓ（Ｑ）と、前記値を用いてｆ’χ，ｓ（Ｑ）を演算する第４演算手段、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数２３】
0005549018.tif 000148
として演算する第５演算手段
として機能させるペアリング演算プログラムを記録した記録媒体。
【請求項２１】
前記第２演算手段として機能する前記電子計算機のＣＰＵに、
有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）の演算を順に既に得られた演算結果を用いて実行させ、
前記第３演算手段として機能する前記電子計算機のＣＰＵに、
有理点（２χ−１）Ｓ，−Ｓを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１の演算と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２の演算と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３の演算と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４の演算を実行させ、
前記第４演算手段として機能する前記電子計算機のＣＰＵに前記有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１、ｌ２、ｌ３、ｌ４を用いて
【数２４】
0005549018.tif 000149
として前記ｆ’χ，Ｓ（Ｑ）を演算する請求項２０記載のペアリング演算プログラムを記録した記録媒体。
【請求項２２】
曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ３χ，ｓ（Ｑ）として、ペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算装置であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、前記整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
前記ＣＰＵは、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、
f3χ,ｓ(Q)および 
0005549018.tif 000150
を演算する第１演算手段と、
有理点ｐ２（Ｓ）、（３χ＋１）Ｓ、ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算手段と、
有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算手段と、
前記第１演算手段の演算結果と、前記第３演算手段の演算結果を用いて
【数２５】
0005549018.tif 000151
としてｆ’χ，ｓ（Ｑ）を演算する第４演算手段と、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数２６】
0005549018.tif 000152
として演算する第５演算手段と
を備えているペアリング演算装置。
【請求項２３】
曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ３χ，ｓ（Ｑ）として、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、前記整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
前記電子計算機のＣＰＵを入力手段として機能させて、前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力ステップと、
前記電子計算機のCPUを第1演算手段として機能させてf3χ,ｓ(Q)および 
0005549018.tif 000153
を演算する第１演算ステップと、
前記電子計算機のＣＰＵを第２演算手段として機能させて有理点ｐ２（Ｓ）、（３χ＋１）Ｓ、ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算ステップと、
前記電子計算機のＣＰＵを第３演算手段として機能させて有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算ステップと、
前記電子計算機のＣＰＵを第４演算手段として機能させて前記ｆ’χ，Ｓ（Ｑ）と、前記値ｌ５、ｌ６、ｌ７、ｌ８を用いて
【数２７】
0005549018.tif 000154
としてｆ’χ，ｓ（Ｑ）を演算する第４演算ステップと、
前記電子計算機のＣＰＵを第５演算手段として機能させて前記ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数２８】
0005549018.tif 000155
として演算する第５演算ステップと
を有するペアリング演算方法。
【請求項２４】
曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ３χ，ｓ（Ｑ）として、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、
位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、前記整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
前記電子計算機のＣＰＵを、
前記整数変数χと、前記有理点Ｓと、前記有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、
f3χ,ｓ(Q) および 
0005549018.tif 000156
を演算する第１演算手段、
有理点ｐ２（Ｓ）、（３χ＋１）Ｓ、ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算手段、
有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算手段、
前記ｆ３χ，ｓ（Ｑ）と、前記値ｌ５、ｌ６、ｌ７、ｌ８を用いて
【数２９】
0005549018.tif 000157
としてｆ’χ，ｓ（Ｑ）を演算する第４演算手段、
前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数３０】
0005549018.tif 000158
として演算する第５演算手段
として機能させるペアリング演算プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ペアリング演算を高速に実行可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
従来、個人ユーザがインターネットなどのネットワーク上において提供されている各種のサービスを利用する場合に、個人ユーザごとにあらかじめ設定されたＩＤ及びパスワード等を用いた認証手続きが要求されることがある。このような認証手続きは、一般的に、個人ユーザが正規のユーザであることを確認するためのものであって、認証手続きのための認証処理は認証サーバによって行われている。【０００３】
最近では、ディジタル署名技術を用いることにより、個々のデータ自体に個人ユーザに固有のディジタル署名データを付加して、個人ユーザが利用するデータが第三者によって改ざんされていないこと、あるいは第三者に漏洩していないことを保証可能として、秘匿性の高い情報もネットワーク上で安全に取扱い可能となってきている。【０００４】
一方、ディジタル署名では、認証サーバでの認証処理にともなって個人ユーザが特定されるため、認証処理のたびに認証サーバに個々の個人ユーザの履歴が情報として逐次蓄積されることとなっている。したがって、認証サーバには、個人ユーザがどのようなサイトにアクセスしたかとか、どのようなサービスを利用したかなどの個人情報が蓄積されることとなるために、個人情報保護の点からこれらの情報の漏洩が生じないように、十分な注意が払われている。【０００５】
このようなディタル署名を用いることによって生じる個人ユーザの履歴情報の蓄積を解消するために、ディジタル署名を拡張したディジタルグループ署名を用いることが提案されている。【０００６】
ディジタルグループ署名を用いた場合には、個人ユーザは、認証サーバに対して匿名で所定のグループに属していることのみを証明する署名データを送信し、認証サーバでは、受信した署名データから個人ユーザを特定することなく個人ユーザが所定のグループに属していることを認証している。したがって、認証サーバでは、グループに属さない個人ユーザによる不正利用を阻止する一方で、個人ユーザごとの履歴情報を蓄積することなく個人ユーザを認証している。【０００７】
このようなディジタルグループ署名における匿名認証には、ペアリング演算が用いられている。【０００８】
ペアリング演算は、２入力１出力の関数を用いた演算であって、たとえば、Ｓを素体Ｆｐ上の有理点、Ｑをｋ次拡大体Ｆｐｋ上の有理点として、２つの有理点ＳとＱを入力することにより拡大体Ｆ＊ｐｋの元ｚが出力されるものであって、しかも、有理点Ｓのａ倍と、有理点Ｑのｂ倍を入力した場合にｚのａｂ乗が算出されるという双線形性を利用して認証を行っている。ここで、「ｋ」は埋め込み次数であり、「Ｆ＊ｐｋ」は、数学における表記上、正しくは、
【数３１】
0005549018.tif 000002
であるが、表示の制限上、「Ｆ＊ｐｋ」と表示している。【０００９】
一般的に、有理点Ｓ、Ｑにはそれぞれ楕円曲線上の点が用いられ、このような楕円曲線上の点のペアリング演算は、ミラーのアルゴリズムを用いて演算するステップと、その演算結果に対してべき乗算を行うステップで構成されている。【００１０】
ディジタルグループ署名では、グループに所属する個人ユーザのアクセス権の認証処理を行う際に、アクセス権が失効している個人ユーザを除外するためのペアリング演算を行った後に所定の個人ユーザのペアリング演算を行って認証処理を行うことにより、個人ユーザごとのアクセス権の発行または失効の属性変更に柔軟に対応可能としている。【００１１】
したがって、たとえば、１０，０００人の個人ユーザで構成されるグループのディジタルグループ署名の場合、アクセス権が失効している個人ユーザが１００人いれば、１００回のペアリング演算が必要となっており、現時点での一般的な電子計算機による１回のペアリング演算に約０．１秒を要していることから、１００回のペアリング演算には約１０秒を要することとなってしまうため、実用上、個人ユーザの数が制限されることとなって、広く利用されるものとはなっていなかった。【００１２】
そこで、ペアリング演算の演算速度を向上させることによりディジタルグループ署名の実用性を向上させるために、たとえば、ペアリング演算として楕円曲線上で定義されるＴａｔｅペアリング演算法を用い、演算負荷を低減させて高速化を図る技術が提案されている（例えば、特許文献１参照。）。
【特許文献１】特開２００５−３１６２６７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、現在提案されているペアリング演算の高速化は未だに十分ではなく、さらなる高速化が求められていた。【００１４】
本発明者らは、このような現状に鑑み、ペアリング演算を高速化すべく研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１５】
本発明のペアリング演算装置は、請求項１に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数をＦとして、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、埋め込み次数ｋに応じて整数変数χを用いて特定しておき、  電子計算機のＣＰＵは、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、Ｆを演算する演算手段と、所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する演算手段と、前記Ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算する演算手段と、前記ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数３２】
0005549018.tif 000003
として演算する演算手段とを備えているものである。
【００１６】
また、本発明のペアリング演算方法は、請求項２に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数をＦとして、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、埋め込み次数ｋに応じて整数変数χを用いて特定しておき、電子計算機のＣＰＵを入力手段として機能させて、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力するステップと、電子計算機のＣＰＵを演算手段として機能させてＦを演算するステップと、電子計算機のＣＰＵを演算手段として機能させて所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて前記Ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて前記ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数３３】
0005549018.tif 000004
として演算するステップとを有するものである。
【００１７】
また、本発明の記録媒体に記録したペアリング演算プログラムは、請求項３に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数をＦとして、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、埋め込み次数ｋに応じて整数変数χを用いて特定しておき、電子計算機のＣＰＵを、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、Ｆを演算する演算手段、所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値をそれぞれ演算する演算手段、前記Ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算する演算手段、
前記ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数３４】
0005549018.tif 000005
として演算する演算手段として機能させるものである。
【００１８】
また、本発明のペアリング演算装置は、請求項４に記載したように、曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐＳをもつ有理点の集合、ＺＱをｐＱ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算さ
0005549018.tif 000006
リング演算装置であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、ＣＰＵは、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジ
0005549018.tif 000007
演算する際に算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算手段と、所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３
0005549018.tif 000008
χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数３５】
0005549018.tif 000009
として演算する第５演算手段とを備えているものである。【００１９】
さらに、前記第２演算手段では、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）を順に既に得られた演算結果を用いてそれぞれ演算し、第３演算手段では、有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算し、第４演算手段では、
【数３６】
0005549018.tif 000010
としてｆ’χ，Ｓ（Ｑ）を演算することにも特徴を有するものである。
【００２０】
また、本発明のペアリング演算方法は、請求項６に記載したように、曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐＳをもつ有理点の集合、ＺＱをｐＱ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリ
0005549018.tif 000011
算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、電子計算機のＣＰＵを入力手段として機能させて、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力ステップと、電子計
0005549018.tif 000012
に算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算ステップと、電子計算機のＣＰＵを第３演算手段として機能させて所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算ステップと、電子計算機のＣＰＵ
0005549018.tif 000013
４演算ステップと、電子計算機のＣＰＵを第５演算手段として機能させてｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数３７】
0005549018.tif 000014
として演算する第５演算ステップとを有するものである。【００２１】
さらに、第２演算ステップでは、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）を順に既に得られた演算結果を用いてそれぞれ演算し、第３演算ステップでは、有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算し、第４演算ステップでは、
【数３８】
0005549018.tif 000015
として前記ｆ’χ，Ｓ（Ｑ）を演算することにも特徴を有するものである。
【００２２】
また、本発明の記録媒体に記録したペアリング演算プログラムは、請求項８に記載したように、曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐＳをもつ有理点の集合、ＺＱをｐＱ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算さ
0005549018.tif 000016
演算させるペアリング演算プログラムであって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
電子計算機のＣＰＵを、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレ
0005549018.tif 000017
算する際に算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算手段、所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算
0005549018.tif 000018
いてペアリングｅ（Ｓ，Ｑ）を
【数３９】
0005549018.tif 000019
として演算する第５演算手段として機能させるものである。【００２３】
さらに、第２演算手段として機能する電子計算機のＣＰＵに、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）の演算を順に既に得られた演算結果を用いて実行させ、第３演算手段として機能する電子計算機のＣＰＵに、有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１の演算と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２の演算と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３の演算と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４の演算を実行させ、第４演算手段として機能する電子計算機のＣＰＵに、
【数４０】
0005549018.tif 000020
としてｆ’χ，Ｓ（Ｑ）の演算を実行させることにも特徴を有するものである。
【００２４】
また、本発明のペアリング演算装置は、請求項１０に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐ３Ｓをもつ有理点の集合、ＺＱをｐ３Ｑ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000021
として、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、ＣＰＵは、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、
0005549018.tif 000022
を演算する第１演算手段と、有理点ｐ２（Ｓ）、ｐ２（ｐ３Ｓ）、（３χ＋１）Ｓ、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算手段と、有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算手段と、第１演算手段の演算結果と、第３演算手段の演算結果を用いて
【数４１】
0005549018.tif 000023
としてｆ’χ，ｓ（Ｑ）を演算する第４演算手段と、ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数４２】
0005549018.tif 000024
として演算する第５演算手段とを備えているものである。
【００２５】
また、本発明のペアリング演算方法は、請求項１１に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐ３Ｓをもつ有理点の集合、ＺＱをｐ３Ｑ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000025
として、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、電子計算機のＣＰＵを入力手段として機能させて、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力ステップと、電子計算機のＣＰＵを第1演算手段として機能させて
0005549018.tif 000026
を演算する第１演算ステップと、電子計算機のＣＰＵを第２演算手段として機能させて有理点ｐ２（Ｓ）、ｐ２（ｐ３Ｓ）、（３χ＋１）Ｓ、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算ステップと、電子計算機のＣＰＵを第３演算手段として機能させて有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算ステップと、
電子計算機のＣＰＵを第4演算手段として機能させて
0005549018.tif 000027
と値ｌ５、ｌ６、ｌ７、ｌ８を用いて
【数４３】
0005549018.tif 000028
としてｆ’χ，ｓ（Ｑ）を演算する第４演算ステップと、電子計算機のＣＰＵを第５演算手段として機能させてｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数４４】
0005549018.tif 000029
として演算する第５演算ステップとを有するものである。
【００２６】
また、本発明の記録媒体に記録したペアリング演算プログラムは、請求項１２に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ＺＳをＳ、ｐ３Ｓをもつ有理点の集合、ＺＱをｐ３Ｑ、Ｑをもつ有理点の集合とし、マルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）を用いて計算される有理関数を
0005549018.tif 000030
として、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、電子計算機のＣＰＵを、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、
0005549018.tif 000031
を順に既に得られた演算結果を用いて演算する第１演算手段、有理点ｐ２（Ｓ）、ｐ２（ｐ３Ｓ）、（３χ＋１）Ｓ、（３χ＋１）ｐ３Ｓをそれぞれ演算する第２演算手段、有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算手段、第１演算手段の演算結果と、第３演算手段の演算結果を用いて
【数４５】
0005549018.tif 000032
としてｆ’χ，ｓ（Ｑ）を演算する第４演算手段、ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数４６】
0005549018.tif 000033
として演算する第５演算手段として機能させるものである。
【００２７】
また、本発明のペアリング演算装置では、請求項１３に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、埋め込み次数ｋに応じて整数変数χを用いて特定しておき、ＣＰＵは、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、ｆを演算する演算手段と、所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する演算手段と、前記ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算する演算手段と、前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数４７】
0005549018.tif 000034
として演算する演算手段とを備えているものである。
【００２８】
また、本発明のペアリング演算方法は、請求項１４に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、埋め込み次数ｋに応じて整数変数χを用いて特定しておき、電子計算機のＣＰＵを入力手段として機能させて、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力するステップと、電子計算機のＣＰＵを演算手段として機能させてｆを演算するステップと、電子計算機のＣＰＵを演算手段として機能させて所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて前記ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数４８】
0005549018.tif 000035
として演算するステップとを有するものである。
【００２９】
また、本発明の記録媒体に記録したペアリング演算プログラムは、請求項１５に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、埋め込み次数ｋに応じて整数変数χを用いて特定しておき、電子計算機のＣＰＵを、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、ｆを演算する演算手段、所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値をそれぞれ演算する演算手段、前記ｆと前記値を用いてｆ’χ，ｓ（Ｑ）を演算する演算手段、前記ｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数４９】
0005549018.tif 000036
として演算する演算手段として機能させるものである。
【００３０】
また、本発明のペアリング演算装置は、請求項１６に記載したように、曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ２χ，ｓ（Ｑ）として、ペアリングｅ（Ｓ，Ｑ）を演算するＣＰＵを備えたペアリング演算装置であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、ＣＰＵは、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する第１演算手段と、ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する際にそれぞれ算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算手段と、所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算手段と、前記ｆ２χ，ｓ（Ｑ）と、前記値を用いてｆ’χ，ｓ（Ｑ）を演算する第４演算手段と、前記ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数５０】
0005549018.tif 000037
として演算する第５演算手段とを備えているものである。【００３１】
さらに、第２演算手段では、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）を順に既に得られた演算結果を用いてそれぞれ演算し、第３演算手段では、有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４を求め、第４演算手段では有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１、ｌ２、ｌ３、ｌ４を用いて
【数５１】
0005549018.tif 000038
としてｆ’χ，Ｓ（Ｑ）を演算することにも特徴を有するものである。
【００３２】
また、本発明のペアリング演算方法は、請求項１８に記載したように、曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ２χ，ｓ（Ｑ）として、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
電子計算機のＣＰＵを入力手段として機能させて、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力ステップと、電子計算機のＣＰＵを第１演算手段として機能させてｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する第１演算ステップと、電子計算機のＣＰＵを第２演算手段として機能させてｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する際にそれぞれ算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算ステップと、電子計算機のＣＰＵを第３演算手段として機能させて所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算ステップと、電子計算機のＣＰＵを第４演算手段として機能させてｆ２χ，ｓ（Ｑ）と値を用いてｆ’χ，ｓ（Ｑ）を演算する第４演算ステップと、電子計算機のＣＰＵを第５演算手段として機能させてｆ’χ，ｓ（Ｑ）を用いて前記ペアリングｅ（Ｓ，Ｑ）を
【数５２】
0005549018.tif 000039
として演算する第５演算ステップとを有するものである。【００３３】
さらに、第２演算ステップでは、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）を順に既に得られた演算結果を用いてそれぞれ演算し、第３演算ステップでは、有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算し、第４演算ステップでは有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１、ｌ２、ｌ３、ｌ４を用いて
【数５３】
0005549018.tif 000040
としてｆ’χ，Ｓ（Ｑ）を演算することにも特徴を有するものである。
【００３４】
また、本発明の記録媒体に記録したペアリング演算プログラムは、請求項２０に記載したように、曲線の式がｙ２＝ｘ３＋ｂ，ｂ∈Ｆｐで与えられ、埋め込み次数が１２で、Ｆｐ１２を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ１２／（Ｆ＊ｐ１２）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ２χ，ｓ（Ｑ）として、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、前記整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
とし、整数変数χの標数ｐによる以下のようなｐ１０を用いた表現が
ｐ≡（２χ−１）ｐ１０＋２χ（ｍｏｄ  ｒ（χ））
であって、
電子計算機のＣＰＵを、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する第１演算手段、ｆ２χ，ｓ（Ｑ）およびｆ２χ，ｐｓ（Ｑ）を演算する際にそれぞれ算出された２χＳおよび２χｐＳを用いて所定の有理点を演算する第２演算手段、所定の有理点を通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値を演算する第３演算手段、ｆ２χ，ｓ（Ｑ）と、値を用いてｆ’χ，ｓ（Ｑ）を演算する第４演算手段、ｆ’２χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数５４】
0005549018.tif 000041
として演算する第５演算手段として機能させるものである。【００３５】
さらに、第２演算手段として機能する電子計算機のＣＰＵに、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）の演算を順に既に得られた演算結果を用いて実行させ、
第３演算手段として機能する前記電子計算機のＣＰＵに、有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１の演算と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２の演算と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３の演算と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４の演算を実行させ、第４演算手段として機能する電子計算機のＣＰＵに有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１、ｌ２、ｌ３、ｌ４を用いて
【数５５】
0005549018.tif 000042
としてｆ’χ，Ｓ（Ｑ）の演算を実行させることにも特徴を有するものである。
【００３６】
また、本発明のペアリング演算装置は、請求項２２記載したように、曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ３χ，ｓ（Ｑ）として、ペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算装置であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
電子計算機のＣＰＵは、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段と、ｆ’３χ，ｓ（Ｑ）および 
0005549018.tif 000043
を演算する第１演算手段と、有理点ｐ２（Ｓ）、（３χ＋１）Ｓ、ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算手段と、有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算手段と、第１演算手段の演算結果と、第３演算手段の演算結果を用いて
【数５６】
0005549018.tif 000044
としてｆ’χ，ｓ（Ｑ）を演算する第４演算手段と、ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数５７】
0005549018.tif 000045
として演算する第５演算手段とを備えているものである。
【００３７】
また、本発明のペアリング演算方法は、請求項２３に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ３χ，ｓ（Ｑ）として、ＣＰＵを備えた電子計算機でペアリングｅ（Ｓ，Ｑ）を演算するペアリング演算方法であって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
電子計算機のＣＰＵを入力手段として機能させて、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力ステップと、電子計算機のＣＰＵを第1演算手段として機能させてｆ’３χ，ｓ（Ｑ）および 
0005549018.tif 000046
を演算する第１演算ステップと、電子計算機のＣＰＵを第２演算手段として機能させて有理点ｐ２（Ｓ）、（３χ＋１）Ｓ、ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算ステップと、電子計算機のＣＰＵを第３演算手段として機能させて有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算ステップと、電子計算機のＣＰＵを第４演算手段として機能させてｆ３χ，Ｓ（Ｑ）と値ｌ５、ｌ６、ｌ７、ｌ８を用いて
【数５８】
0005549018.tif 000047
としてｆ’χ，ｓ（Ｑ）を演算する第４演算ステップと、電子計算機のＣＰＵを第５演算手段として機能させてｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数５９】
0005549018.tif 000048
として演算する第５演算ステップとを有するものである。
【００３８】
また、本発明の記録媒体に記録したペアリング演算プログラムは、請求項２４に記載したように、曲線の式がｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられ、埋め込み次数が８で、Ｆｐ８を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐ８／（Ｆ＊ｐ８）ｒ
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算される有理関数をｆ３χ，ｓ（Ｑ）として、ＣＰＵを備えた電子計算機にペアリングｅ（Ｓ，Ｑ）を演算させるペアリング演算プログラムであって、位数ｒと、フロベニウス自己準同形写像φｐのトレースｔを、整数変数χを用いて
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
とし、整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現が
ｐ３≡ｐ２＋３χ＋１（ｍｏｄ  ｒ（χ））
であって、
電子計算機のＣＰＵを、整数変数χと、有理点Ｓと、有理点Ｑをそれぞれ所定のレジスタに入力する入力手段、ｆ’３χ，ｓ（Ｑ）および 
0005549018.tif 000049
を演算する第１演算手段、有理点ｐ２（Ｓ）、（３χ＋１）Ｓ、ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓを順に既に得られた演算結果を用いてそれぞれ演算する第２演算手段、有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算する第３演算手段、ｆ３χ，Ｓ（Ｑ）と値ｌ５、ｌ６、ｌ７、ｌ８を用いて
【数６０】
0005549018.tif 000050
としてｆ’χ，ｓ（Ｑ）を演算する第４演算手段、ｆ’χ，ｓ（Ｑ）を用いてペアリングｅ（Ｓ，Ｑ）を
【数６１】
0005549018.tif 000051
として演算する第５演算手段として機能させるものである。
【発明の効果】
【００３９】
本発明によれば、ペアリング演算の際にミラーのアルゴリズムを用いて計算される有理関数を、整数変数χの関数とすることにより、有理関数の計算を高速に行うことができ、ペアリング演算を高速化することができる。
【図面の簡単な説明】
【００４０】
【図１】本発明の実施形態にかかるペアリング演算装置の概略構成図である。
【図２】本発明の実施形態にかかるＴｗｉｓｔｅｄ  Ｘａｔｅペアリング演算プログラムのフローチャートである。
【図３】有理関数ｆ２χ，Ｓ（Ｑ）を演算するためのフローチャートである。
【図４】本発明の実施形態にかかるＴｗｉｓｔｅｄ  Ｘａｔｅペアリング演算プログラムのフローチャートである。
【図５】本発明の実施形態にかかるＴｗｉｓｔｅｄ  Ｘａｔｅマルチペアリング演算プログラムのフローチャートである。
【図６】有理関数ｆ２χ，Ｚｓ（ＺＱ）を演算するためのフローチャートである。
【図７】本発明の実施形態にかかるＴｗｉｓｔｅｄ  Ｘａｔｅマルチペアリング演算プログラムのフローチャートである。
【図８】本発明の実施形態にかかるＴｗｉｓｔｅｄ  Ｘａｔｅペアリングにスレッド計算を適用した場合の計算フローである。
【発明を実施するための形態】
【００４１】
本発明のペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムでは、ペアリング演算におけるミラーのアルゴリズムを用いて有理関数を演算する第１のステップと、その演算結果に対してべき乗算を行う第２のステップのうち、第１のステップにおいて整数変数χを用いて有理関数を演算することにより、演算の高速化を図っているものである。
【００４２】
すなわち、従来のペアリング演算では、曲線の式がｙ２＝ｘ３＋ａｘ＋ｂ，ａ∈Ｆｐ，ｂ∈Ｆｐで与えられ、埋め込み次数がｋで、Ｆｐｋを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ［ｒ］とし、φｐをフロベニウス自己準同形写像として、
Ｇ１＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［１］），
Ｇ２＝Ｅ［ｒ］∩Ｋｅｒ（φｐ−［ｐ］）
により、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ１、Ｑ∈Ｇ２、所定の整数変数をχ、ミラーのアルゴリズムを用いて計算さ
0005549018.tif 000052
【数６２】
0005549018.tif 000053
として演算していた。これらは、Ｔｗｉｓｔｅｄ  Ａｔｅペアリングとして知られているものである。
【００４３】
これに対して、本発明者らは、楕円曲線の整数変数χを用いることにより、
ｅ：Ｇ１×Ｇ２→Ｆ＊ｐｋ／（Ｆ＊ｐｋ）ｒ
である非退化な双線形写像として高速に演算が可能な新たなペアリングを見出した。
このペアリングを「Ｔｗｉｓｔｅｄ  Ｘａｔｅペアリング」と呼ぶことにする。さらに、複数のペアリングの積を計算するマルチペアリング技術を適用してさらなる高速化を可能としている。このペアリングを「Ｔｗｉｓｔｅｄ  Ｘａｔｅマルチペアリング」と呼ぶことにする。すなわち、本発明のペアリング演算装置、ペアリング演算方法、ペアリング演算プログラムでは、Ｔｗｉｓｔｅｄ  Ｘａｔｅペアリング、Ｔｗｉｓｔｅｄ  Ｘａｔｅマルチペアリングを用いることにより、高速な演算を可能としているものである。
【００４４】
特に、ペアリング演算に用いられる楕円曲線は、埋め込み次数に応じてそれぞれペアリングフレンドリ曲線として知られており、例えば埋め込み次数が１２の場合には、位数ｒと、フロベニウス自己準同型写像φｐのトレースｔが、整数変数χを用いて
ｒ（χ）＝３６χ４−３６χ３＋１８χ２−６χ＋１，
ｔ（χ）＝６χ２＋１
となることが知られている。
【００４５】
また、埋め込み次数が８の場合には、
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１，
ｔ（χ）＝−９χ３−３χ２−２χ
が知られている。
【００４６】
以下において、代表して埋め込み次数１２の場合を説明する。したがって、上述したように
0005549018.tif 000054
である。
（式２）より、
0005549018.tif 000055
である。なお、標数ｐは
0005549018.tif 000056
であることを用いている。したがって、（式１）は
0005549018.tif 000057
（式５）の両辺を二乗することにより、次式が得られる。
0005549018.tif 000058
ここで、既に知られているｐ４＋１≡ｐ２（ｍｏｄ  ｒ）の関係式から、
0005549018.tif 000059
となり、（式７）の両辺に（ｐ２−１）−１を掛けることによって次式が得られる。
0005549018.tif 000060
ここで、（ｐ２−１）−１はｐ４−ｐ２＋１≡０（ｍｏｄ  ｒ）の関係式と、ｇｃｄ（ｐ４−ｐ２＋１，ｐ２−１）＝１に基づいて、以下のように得る。
0005549018.tif 000061
ｐ２≡ｐ４＋１（ｍｏｄ  ｒ）の関係式より、
0005549018.tif 000062
となり、（式３）およびｐ６≡−１（ｍｏｄ  ｒ）から
0005549018.tif 000063
となる。
【００４７】
0005549018.tif 000064
特に、（式３）より、
【数６３】
0005549018.tif 000065
である。ここで、Ｓ∈Ｇ１であり、Ｑ∈Ｇ２に対して
【数６４】
0005549018.tif 000066
である。また、有理関数は、
0005549018.tif 000067
の関係を有する。
なお、ｇａＳ，ｂＳ＝ｌａＳ，ｂＳ／ｖａＳ＋ｂＳであって、ｌａＳ，ｂＳは２つの有理点ａＳ，ｂＳを通る直線の値、ｖａＳ＋ｂＳは有理点ａＳ＋ｂＳの鉛直線の値である。埋め込み次数が偶数の場合には、ｖａＳ＋ｂＳの計算は省略できる。
（式１４ｃ）より、（式１２）は次のようになる。
【数６５】
0005549018.tif 000068
（式１１）を用いることにより、
【数６６】
0005549018.tif 000069
となる。さらに、（式１４ａ）および（式１４ｂ）より、次のようになる。
【数６７】
0005549018.tif 000070
また、（式１７）の
【数６８】
0005549018.tif 000071
は双線形を有していることから、（式１７）は次のように変形できる。
【数６９】
0005549018.tif 000072
ここで、本発明者らは、（式１９）の左辺は双線形性を有していることから、（式１９）の右辺も双線形性を有していることに思い至り、この（式１９）の右辺を新たな有理関数ｆ’χ，Ｓ（・）として用いることにより、ペアリングｅ（Ｓ，Ｑ）を
【数７０】
0005549018.tif 000073
として演算するＴｗｉｓｔｅｄ  Ｘａｔｅペアリングを知見するに至った。このＴｗｉｓｔｅｄ  Ｘａｔｅペアリングでは、ミラーのアルゴリズムを用いた演算において（ｔ−１）２ｍｏｄ  ｒよりも小さいサイズの整数変数χを用いてｆ２χ，Ｓ（Ｑ）およびｆ２χ，ｐＳ（Ｑ）を計算することによってｆ’χ，Ｓ（Ｑ）を高速に求めることができる。しかしながら、二つのミラーのアルゴリズムを用いた演算において使用する有理点がそれぞれ異なるため、通常は以下のように（式１９）を計算する。
Ｆ１，Ｆ２を次式で与えると、
【数７１】
0005549018.tif 000074
【数７２】
0005549018.tif 000075
（式１９）はＦ１及びＦ２を使ってｆ’χ，Ｓ＝Ｆ１ｐ・Ｆ２と表わせる。Ｆ２の計算に必要な有理点ｐＳはＦ１の計算過程で得られるため、最初にＦ１を計算し次にＦ２を計算する。この場合、ミラーのアルゴリズムの繰り返し回数は２［ｌｏｇ２χ］≒（１／２）［ｌｏｇ２ｒ］となる。
【００４８】
本発明の基本アイデアはｐＳを事前計算することにより、Ｆ１とＦ２を互いに独立な計算にすることである。これにより本発明のＴｗｉｓｔｅｄ  Ｘａｔｅペアリングでは並列化処理が実現可能である。具体的には、複数のミラーのアルゴリズム計算の並列化処理が可能なマルチペアリング、そして複数のコアを持つＣＰＵを使用できる環境であればスレッド計算を適用することができる。
【００４９】
＜スレッド計算の適用＞
ｐＳは（式１１）より、（１／４）［ｌｏｇ２ｒ］程度のスカラ倍算で高速に計算することができる。
ｐＳを事前に計算しておくことにより、Ｆ１とＦ２は互いに独立な計算となる。従って、コアを複数個持つＣＰＵを使用できる環境であればＦ１およびＦ２の計算をそれぞれ別のコアに割り当てることで並列計算が可能となる。図８にスレッド計算を適用した場合の計算フローを示す。この場合、（式２１）及び（式２２）により、ミラーのアルゴリズムの繰り返し回数は実質的に（１／４）［ｌｏｇ２ｒ］となる。
【００５０】
＜マルチペアリングの適用＞
さらに、（式１９）の右辺を変形すると、
【数７３】
0005549018.tif 000076
となる。（式２３）より、Ｔｗｉｓｔｅｄ  Ｘａｔｅペアリングの主たる計算はＡ＝ｆｐ２χ，Ｓ・ｆ２χ，ｐＳである。一般にＡを計算するためには、まず繰り返し回数が２χで与えられるミラーのアルゴリズムによってｆ２χ，Ｓを計算した後にｆ２χ，ｐＳを計算する。そして、これらの積を取ることによってＡを得る。なお、ｆｐ２χ，Ｓはフロベニウス自己準同型写像により、極めて少ない計算コストで得ることができる。したがって、繰り返し回数が（１／４）［ｌｏｇ２ｒ］で与えられるミラーのアルゴリズムを２回行っていることから、Ｔｗｉｓｔｅｄ  Ｘａｔｅペアリングのミラーのアルゴリズムによる処理の計算コストは（１／２）［ｌｏｇ２ｒ］で与えられる。
本発明は、一般にはミラーのアルゴリズムを独立に計算することによって得られるＡの計算をマルチペアリングに対するミラーのアルゴリズム（ＭＭＡ）によりＡを得ることに特徴を持つ。
次の関係式
【数７４】
0005549018.tif 000077
を用いるとＡは次式のようになる。
【数７５】
0005549018.tif 000078
このようにＡを与えることによってＡの計算は２個のペアリングの積を計算するマルチペアリングであると考えることができる。したがって、ＭＭＡを適用すると（式２３）は以下のように計算できる。
【数７６】
0005549018.tif 000079
0005549018.tif 000080
にそれぞれ次式を与えることによって得られる。
0005549018.tif 000081
このように計算することにより、ミラーのアルゴリズムにおけるＦｐ１２上の二乗算および楕円加算および楕円二倍算に必要となるＦｐ上の逆元計算の回数をミラーのアルゴリズムによる計算を独立に行う場合と比較して、１／２に削減することが可能となる。
なお、（式２７）および（式２８）より、Ａの計算にＭＭＡを適用するためには事前にｐＳおよびｐＱを計算する必要がある。ｐＳは（式１１）より、（１／４）［ｌｏｇ２ｒ］程度のスカラ倍算で高速に計算することができ、ｐＱはフロベニウス自己準同型写像により得られるため、本発明を適用するために必要となる計算コストはＭＭＡを適用することによって削減できた計算コストよりも極めて小さい。
【００５１】
ここまでは、埋め込み次数が１２の場合について説明してきたが、上述埋め込み次数が８の場合にも基本的に同様であるので詳細な説明は省略する。
【００５２】
以下において、埋め込み次数が１２の場合のＴｗｉｓｔｅｄ  Ｘａｔｅペアリングの実施形態について詳述する。なお、本実施形態では、ディジタルグループ署名を想定しており、所要の電子計算機で構成された認証サーバをペアリング演算装置としている。ただし、ペアリング演算装置は、認証サーバで構成する場合に限定されるものではなく、少なくともＣＰＵなどの演算手段を備えてペアリング演算が実行可能となった装置であれば、どのような装置であってもよい。
【００５３】
図１に示すように、認証サーバを構成する電子計算機１０は、演算処理を実行するＣＰＵ１１と、ペアリング演算プログラムなどの各種プログラム、及びペアリング演算プログラムで使用するデータなどを記憶したハードディスクなどの記憶装置１２と、ペアリング演算プログラムを展開して実行可能とするとともに、ペアリング演算プログラム実行にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置１３を備えている。図１中、１４はバスである。
【００５４】
また、電子計算機１０は、インターネットなどの電気通信回線２０に接続して、この電気通信回線２０に接続されたクライアント装置３０から送信されたディジタルグループ署名の署名データを受信可能としている。図１中、１５は電子計算機１０の入出力制御部である。
【００５５】
電子計算機１０では、クライアント装置３０からディジタルグループ署名の署名データが送信されると、送信された署名データをメモリ装置１３に一旦記憶し、ペアリング演算プログラムを起動して、ペアリング演算を実行している。
【００５６】
すなわち、電子計算機１０では、起動したペアリング演算プログラムによって、図２に示すフローチャートに基づいてペアリング演算を行い、ディジタルグループ署名を実現している。なお、ディジタルグループ署名における認証処理については詳説せず、認証処理におけるサブルーチン処理としてのペアリング演算についてのみ詳説する。
【００５７】
起動したペアリング演算プログラムによって、電子計算機１０では、ＣＰＵ１１を入力手段として機能させて、メモリ装置１３にあらかじめ記憶している整数変数χのデータと、有理点Ｓのデータ、及び署名データとしてメモリ装置１３に一旦記憶された有理点ＱのデータをＣＰＵ１１の内部に設けている所定のレジスタにそれぞれ入力している。（ステップＳ１）。
【００５８】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第１演算手段として機能させて、ミラーのアルゴリズムによって有理関数ｆ２χ，Ｓ（Ｑ）を演算しその演算結果をメモリ装置１３に記憶している。（ステップＳ２）。
【００５９】
この有理関数ｆ２χ，Ｓ（Ｑ）の演算は、具体的には図３に示すように実行している。特にステップＳ２では、有理関数ｆ２χ，Ｓ（Ｑ）の演算とともに２χＳの演算を行いその演算結果をメモリ装置１３に記憶している。
【００６０】
すなわち、まず、初期設定としてｆ←１、Ｔ←Ｓとするとともに整数変数２χを２進数表示とした場合のビット数をｉとしている（ステップＳ２１）。
【００６１】
次いで、ステップＳ２２で有理関数ｆ２χ，Ｓ（Ｑ）部分の所定の演算を行い、ステップＳ２３で２χＳ部分の所定の演算を行い、整数変数２χの低次から数えてｉ番目のビットの値ｕｉが「１」であるか「０」であるかを判定して（ステップＳ２４）、ｕｉ＝１の場合には、さらにステップＳ２５で有理関数ｆ２χ，Ｓ（Ｑ）部分の所定の演算を行い、ステップＳ２６で２χＳ部分の所定の演算を行っている。
【００６２】
次いで、ｉ≠１の場合に（ステップＳ２７）、ｉのデクリメントを行って（ステップＳ２８）、ステップＳ２２に戻り、ステップＳ２７においてｉ＝１となるまで繰り返すことにより、有理関数ｆ２χ，Ｓ（Ｑ）及び２χＳを演算し、その演算結果をメモリ装置１３にそれぞれ記憶している。
【００６３】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、メモリ装置１３に記憶された２χＳの値を読み出し、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）をそれぞれ演算し、各有理点の値をメモリ装置１３にそれぞれ記憶している。（ステップＳ３）。
【００６４】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第３演算手段として機能させて、ステップＳ３で得られた各有理点の値をメモリ装置１３からそれぞれ読み出し、有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２をそれぞれ演算し、ｌ１およびｌ２の値をメモリ装置１３にそれぞれ記憶している。（ステップＳ４）。
【００６５】
具体的には、ｌ＝ｌＡ，Ｂ（Ｑ）は、
λＡ，Ｂ←（ｙＢ−ｙＡ）／（ｘＢ−ｘＡ），
ｌＡ，Ｂ（Ｑ）←（ｘＱ−ｘＢ）λＡ，Ｂ−（ｙＱ−ｙＢ）
として演算している。
すなわち、ＣＰＵ１１は点Ａ、Ｂのｘｙ座標を用いて傾きλＡ，Ｂを演算し、その結果と点Ｑ、Ｂのｘｙ座標を用いてｌＡ，Ｂ（Ｑ）を演算しその結果をメモリ装置１３に記憶している。
【００６６】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて有理点ｐＳを演算している（ステップＳ５）。具体的には、ステップＳ２およびステップＳ３で得られた有理点の値をメモリ装置１３から読み出し、これらを用いて以下のように演算し、ｐＳの値をメモリ装置１３に記憶している。
ｐＳ＝ｐ１０（（２χ−１）Ｓ）＋２χＳ
【００６７】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第１演算手段として機能させてミラーのアルゴリズムによって有理関数ｆ２χ，ｐＳ（Ｑ）を演算しその演算結果をメモリ装置１３に記憶している。（ステップＳ６）。
【００６８】
この有理関数ｆ２χ，ｐＳ（Ｑ）の演算は、具体的には図３に示すように実行している。特にステップＳ６では、有理関数ｆ２χ，ｐＳ（Ｑ）の演算とともに２χｐＳの演算を行いその演算結果をメモリ装置１３に記憶している。
【００６９】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、メモリ装置１３に記憶された２χｐＳの値を読み出し、有理点−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）をそれぞれ演算し、各有理点の値をメモリ装置１３にそれぞれ記憶している。（ステップＳ７）。
【００７０】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第３演算手段として機能させて、ステップＳ７で得られた各有理点の値をメモリ装置１３からそれぞれ読み出し、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算しｌ３およびｌ４の値をメモリ装置１３にそれぞれ記憶している。（ステップＳ８）。
【００７１】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第４演算手段として機能させて、メモリ装置１３に記憶された第１演算手段での演算結果（ｆ２χ，Ｓ（Ｑ）およびｆ２χ，ｐＳ（Ｑ）の値）と、第３演算手段での演算結果（ｌ１、ｌ２およびｌ３、ｌ４の値）をメモリ装置１３からそれぞれ読み出し、
【数７７】
0005549018.tif 000082
となるｆ’χ，Ｓ（Ｑ）を演算して、その演算結果をメモリ装置１３に記憶している（ステップＳ９）。
【００７２】
具体的には、
ｉｎｐｕｔ：Ｓ∈Ｇ１，Ｑ∈Ｇ２，２χ，ｐ
ｏｕｔｐｕｔ：ｆ＝ｆ’χ，Ｓ（Ｑ）
ｐｒｏｃｅｄｕｒｅ：
0005549018.tif 000083
として演算している。
すなわち、ＣＰＵ１１は、メモリ装置１３を用いて上記手順の各演算を行いｆ’χ，Ｓ（Ｑ）を得てその値をメモリ装置１３に記憶している。具体的には、手順１でミラーのアルゴリズムによりｆ２χ，Ｓを求めその結果をＡに代入し、同時に得られた２χＳをＴ１に代入している。手順２及び３で有理点−Ｓ及び（２χ−１）Ｓを求めＴ２およびＴ３にそれぞれ代入している。手順４では前述したように埋め込み次数が偶数の場合にはＧＡ，ＢはｌＡ，Ｂとなるので有理点（２χ−１）Ｓ、−Ｓを通る直線における有理点Ｑの値ｌ１を求めてその結果をＢに代入している。手順５および６で（式２９）の（）内の｛｝部分を求めその結果をＢに代入している。手順７ではＢおよびＡの積を求めｆに代入している。手順８では有理点ｐ１０（（２χ−１）Ｓ）を求めその結果をＴ４に代入している。手順９では有理点ｐ１０（（２χ−１）Ｓ）、２χＳを通る直線における有理点Ｑの値ｌ２を求めその結果をＢに代入している。手順１０では、（式１１）の関係を用いて、ｐＳを求めその結果をＴ４に代入している。手順１１及び１２で（式２９）の（）部分を求めその結果をｆに代入している。手順１３ではミラーのアルゴリズムによりｆ２χ，ｐＳを求めその結果をＡに代入し、同時に得られた２χｐＳをＴ１に代入している。手順１４および１５で有理点−ｐＳおよび（２χ−１）ｐＳを求め、手順１６では、有理点（２χ−１）ｐＳ、−ｐＳを通る直線における有理点Ｑの値ｌ３を求めその結果をＢに代入している。手順１７、１８では上記（式２９）の（）の次の｛｝部分を求め、手順１９ではＣおよびＡの積を求めＣに代入している。手順２０では有理点ｐ１０（（２χ−１）Ｓ）を求めその結果をＴ４に代入している。手順２１では、有理点ｐ１０（（２χ−１）Ｓ）、２χｐＳを通る直線における有理点Ｑの値ｌ４を求めその結果をＢに代入している。手順２２および２３でｆ’χ，Ｓ（Ｑ）を求め、その結果をｆに代入している。
【００７３】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第５演算手段として機能させて、ステップＳ９で得られたｆ’χ，Ｓ（Ｑ）の値をメモリ装置１３から読み出し、ペアリングｅ（Ｓ，Ｑ）における最終べきのべき乗算を行いその演算結果をメモリ装置１３に記憶している（ステップＳ１０）。
【００７４】
具体的には、
0005549018.tif 000084
として演算し、ｆ’すなわちｅ（Ｓ，Ｑ）の値をメモリ装置１３に記憶している。
【００７５】
認証サーバを構成する電子計算機１０では、上述したようにして得られたペアリングの演算結果を用いて認証処理を行っている。
【００７６】
本実施形態では、埋め込み次数１２の場合について説明したが、請求項２２から請求項２４に記載した埋め込み次数８の場合でも、同様のアルゴリズムでＴｗｉｓｔｅｄ  Ｘａｔｅペアリングをより高速に演算できる。
【００７７】
つまり、埋め込み次数が８であって、
ｒ（χ）＝９χ４＋１２χ３＋８χ２＋４χ＋１
ｔ（χ）＝−９χ３−３χ２−２χ
の場合について説明する。この場合、整数変数χの標数ｐによる以下のようなｐ２およびｐ３を用いた表現は
ｐ３＝ｐ２＋３χ＋１
である。
【００７８】
この場合、有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、
有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、
有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、
有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８を用いることにより、
【数７８】
0005549018.tif 000085
となる。
【００７９】
埋め込み次数１２の場合と同様に、埋め込み次数８の場合でも、認証サーバでは、起動したペアリング演算プログラムによって、図４に示すフローチャートに基づいてペアリング演算を行っている。
【００８０】
起動したペアリング演算プログラムによって、電子計算機１０では、ＣＰＵ１１を入力手段として機能させて、メモリ装置１３にあらかじめ記憶している整数変数χのデータと、有理点Ｓのデータ、及び署名データとしてメモリ装置１３に一旦記憶された有理点ＱのデータをＣＰＵ１１の内部に設けている所定のレジスタにそれぞれ入力している。（ステップＴ１）。
【００８１】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第１演算手段として機能させて、ミラーのアルゴリズムによって有理関数ｆ３χ，Ｓ（Ｑ）を演算しその演算結果をメモリ装置１３に記憶している。（ステップＴ２）。このステップＴ２では、図３に示したフローチャートのステップＳ２１における２を底とする対数の真数が３χとなることおよびステップＳ２２における、１番目の式が
【数７９】
0005549018.tif 000086
となる以外は、図３に示したフローチャートと同じ演算処理を行っている。ここで、「ａ」は、ｙ２＝ｘ３＋ａｘ，ａ∈Ｆｐで与えられた楕円曲線における１次の係数である。
【００８２】
またステップＴ２でも有理関数ｆ３χ，Ｓ（Ｑ）とともに３χＳを演算しその演算結果をメモリ装置１３に記憶している。
【００８３】
有理関数ｆ３χ，Ｓ（Ｑ）及び３χＳの演算後、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、メモリ装置１３に記憶された３χＳの値を読み出し、有理点ｐ２（Ｓ）、（３χ＋１）Ｓ、をそれぞれ演算し各有理点の値をメモリ装置１３に記憶している。（ステップＴ３）。
【００８４】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第３演算手段として機能させて、ステップＴ３で得られた各有理点の値をメモリ装置１３から読み出し、有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６をそれぞれ演算し、ｌ５およびｌ６の値をメモリ装置１３にそれぞれ記憶している。（ステップＴ４）。
【００８５】
埋め込み次数が１２の場合と同様に、具体的には、ｌ＝ｌＡ，Ｂ（Ｑ）は、
λＡ，Ｂ←（ｙＢ−ｙＡ）／（ｘＢ−ｘＡ），
ｌＡ，Ｂ（Ｑ）←（ｘＱ−ｘＢ）λＡ，Ｂ−（ｙＱ−ｙＢ）
として演算している。
【００８６】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて有理点ｐ３Ｓを演算している（ステップＴ５）。具体的には、ステップＴ２およびステップＴ３で得られた有理点の値をメモリ装置１３から読み出し、以下のように演算して、ｐ３Ｓの値をメモリ装置１３に記憶している。
ｐ３Ｓ＝ｐ２Ｓ＋（３χ＋１）Ｓ
【００８７】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第
0005549018.tif 000087
演算しその演算結果をメモリ装置１３に記憶している。（ステップＴ６）。
【００８８】
0005549018.tif 000088
算結果をメモリ装置１３に記憶している。
【００８９】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、メモリ装置１３に記憶された３χｐ３Ｓの値を読み出し、有理点ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓ、をそれぞれ演算し各有理点の値をメモリ装置１３にそれぞれ記憶している。（ステップＴ７）。
【００９０】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第３演算手段として機能させて、ステップＴ７で得られた各有理点の値をメモリ装置１３からそれぞれ読み出し、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算しｌ７およびｌ８の値をメモリ装置１３に記憶している。（ステップＴ８）。
【００９１】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第４演算手段として機能させて、メモリ装置１３に記憶された第１演算手段での演算
0005549018.tif 000089
よびｌ７、ｌ８の値）をメモリ装置１３からそれぞれ読み出し、
【数８０】
0005549018.tif 000090
となるｆ’χ，Ｓ（Ｑ）を演算して、その演算結果をメモリ装置１３に記憶している（ステップＴ９）。
【００９２】
具体的には、
ｉｎｐｕｔ：Ｓ∈Ｇ１，Ｑ∈Ｇ２，３χ，ｐ
ｏｕｔｐｕｔ：ｆ＝ｆ’χ，Ｓ（Ｑ）
ｐｒｏｃｅｄｕｒｅ：
0005549018.tif 000091
として演算している。すなわち、ＣＰＵ１１は、メモリ装置１３を用いて上記手順の各演算を行いｆ’χ，Ｓ（Ｑ）を得てその値をメモリ装置１３に記憶している。具体的には、手順１ではミラーのアルゴリズムによりｆ３χ、Ｓを求めその結果をＡに代入するとともに、同時に得られた３χＳをＴ１に代入している。手順２では、有理点３χＳ、Ｓを通る直線における有理点Ｑの値ｌ５を求めその結果をＢに代入している。手順３および４では有理点（３χ＋１）Ｓおよびｐ２（Ｓ）を求めＴ２およびＴ３にそれぞれ代入している。手順５では、有理点ｐ２（Ｓ）、（３χ＋１）Ｓを通る直線における有理点Ｑの値ｌ６を求めその結果をＣに代入している。手順６では、Ａ、Ｂ及びＣの積をとり、上記（式３０）の（）内を求めその結果をｆに代入している。手順７では、ｐ３＝ｐ２＋３χ＋１の関係を用いてｐ３Ｓを求めその結果をＴ４に代入している。手順８では、ミラーのアルゴリズムにより
0005549018.tif 000092
を求めその結果をＡに代入するとともに同時に得られた３χｐ３ＳをＴ１に代入している。手順９では、有理点３χｐ３Ｓ、ｐ３Ｓを通る直線における有理点Ｑの値ｌ７を求めその結果をＢに代入している。手順１０および１１では、有理点（３χ＋１）ｐ３Ｓ、ｐ２（ｐ３Ｓ）を求めその結果をＴ２およびＴ３にそれぞれ代入している。手順１２では、有理点ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑの値ｌ８を求めその結果をＣに代入している。手順１３でｆ’χ、Ｓ（Ｑ）を求めその結果をｆに代入している。
【００９３】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第５演算手段として機能させて、ステップＴ９で得られたｆ’χ，Ｓ（Ｑ）の値をメモリ装置１３から読み出し、ペアリングｅ（Ｓ，Ｑ）における最終べきのべき乗算を行いその演算結果をメモリ装置１３に記憶している（ステップＴ１０）。
【００９４】
以下では、埋め込み次数が１２の場合のＴｗｉｓｔｅｄ  Ｘａｔｅマルチペアリングの実施形態について詳述する。Ｔｗｉｓｔｅｄ  Ｘａｔｅペアリングと共通する部分については説明を省略する。図５に基づいて、埋め込み次数が１２の場合のＴｗｉｓｔｅｄ  Ｘａｔｅマルチペアリングの演算について説明する。
【００９５】
起動したペアリング演算プログラムによって、電子計算機１０では、ＣＰＵ１１を入力手段として機能させて、メモリ装置１３にあらかじめ記憶している整数変数χのデータと、有理点Ｓのデータ、及び署名データとしてメモリ装置１３に一旦記憶された有理点ＱのデータをＣＰＵ１１の内部に設けている所定のレジスタにそれぞれ入力している。（ステップＵ１）。
【００９６】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、有理点ｐＳの演算を行い、ｐＳの値をメモリ装置１３に記憶している（ステップＵ２）。
【００９７】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、有理点ｐＱの演算を行い、ｐＱの値をメモリ装置１３に記憶している（ステップＵ３）。
【００９８】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第１演算手段として機能させて、マルチペアリングに対するミラーのアルゴリズムに
0005549018.tif 000093
る。（ステップＵ４）。
【００９９】
0005549018.tif 000094
算を行いその演算結果をメモリ装置１３にそれぞれ記憶している。
【０１００】
すなわち、まず、初期設定としてｆ←１、Ｔ１←Ｓ、Ｔ２←ｐＳとするとともに整数変数２χを２進数表示とした場合のビット数をｉとしている（ステップＵ４１）。
【０１０１】
0005549018.tif 000095
Ｕ４３で２χＳ及び２χｐＳ部分の所定の演算を行い、整数変数２χの低次から数えてｉ番目のビットの値ｕｉが「１」であるか「０」であるかを判定して（ステップＵ４４）、
0005549018.tif 000096
行い、ステップＵ４６で２χＳ及び２χｐＳ部分の所定の演算を行っている。
【０１０２】
次いで、ｉ≠１の場合に（ステップＵ４７）、ｉのデクリメントを行って（ステップＵ４８）、ステップＵ４２に戻り、ステップＵ４７においてｉ＝１となるまで繰り返すこと
0005549018.tif 000097
装置１３にそれぞれ記憶している。
【０１０３】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、メモリ装置１３に記憶された２χＳ及び２χｐＳの値を読み出し、有理点−Ｓ、（２χ−１）Ｓ、ｐ１０（（２χ−１）Ｓ）、−ｐＳ、（２χ−１）ｐＳ、ｐ１０（（２χ−１）ｐＳ）をそれぞれ演算し、各有理点の値をメモリ装置１３にそれぞれ記憶している。（ステップＵ５）。
【０１０４】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第３演算手段として機能させて、ステップＵ５で得られた各有理点の値をメモリ装置１３から読み出し、有理点（２χ−１）Ｓ，−Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ１と、有理点（２χ−１）ｐＳ，−ｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ２と、有理点ｐ１０（（２χ−１）Ｓ），２χＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ３と、有理点ｐ１０（（２χ−１）ｐＳ），２χｐＳを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ４をそれぞれ演算し、ｌ１、ｌ２、ｌ３およびｌ４の値をメモリ装置１３にそれぞれ記憶している。（ステップＵ６）。
【０１０５】
具体的には、ｌ＝ｌＡ，Ｂ（Ｑ）は、
λＡ，Ｂ←（ｙＢ−ｙＡ）／（ｘＢ−ｘＡ），
ｌＡ，Ｂ（Ｑ）←（ｘＱ−ｘＢ）λＡ，Ｂ−（ｙＱ−ｙＢ）
として演算している。
すなわち、ＣＰＵ１１は点Ａ、Ｂのｘｙ座標を用いて傾きλＡ，Ｂを演算し、その結果と点Ｑ、Ｂのｘｙ座標を用いてｌＡ，Ｂ（Ｑ）を演算しその結果をメモリ装置１３に記憶している。
【０１０６】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第４演算手段として機能させて、メモリ装置１３に記憶された第１演算手段での演算結果と（ステップＵ４）、第３演算手段での演算結果（ｌ１、ｌ２、ｌ３、およびｌ４の値）をメモリ装置１３から読み出し、
【数８１】
0005549018.tif 000098
となるｆ’χ，Ｓ（Ｑ）を演算して、その演算結果をメモリ装置１３に記憶している（ステップＵ７）。
【０１０７】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第５演算手段として機能させて、ステップＵ７で得られたｆ’χ，Ｓ（Ｑ）の値をメモリ装置１３から読み出し、ペアリングｅ（Ｓ，Ｑ）における最終べきのべき乗算を行い、その演算結果をメモリ装置１３に記憶している（ステップＵ８）。
【０１０８】
具体的には、
ｉｎｐｕｔ：ＺＳ＝｛Ｓ，ｐＳ∈Ｇ１｝，ＺＱ＝｛ｐＱ，Ｑ∈Ｇ２｝，２χ，ｐ
ｏｕｔｐｕｔ：ｆ＝ｆ’χ，Ｓ（Ｑ）
ｐｒｏｃｅｄｕｒｅ：
0005549018.tif 000099
として演算している。すなわち、ＣＰＵ１１は、メモリ装置１３を用いて上記手順の各演算を行いｆ’χ，Ｓ（Ｑ）を得てその値をメモリ装置１３に記憶している。
具体的には、手順１ではマルチペアリングに対するミラーのアルゴリズムにより
0005549018.tif 000100
を求めその結果をＡに代入するとともに、同時に得られた２χＳおよび２χｐＳをＴ１およびＴ２にそれぞれ代入している。手順２および３では、有理点−Ｓおよび（２χ−１）Ｓを求めＴ３およびＴ４にそれぞれ代入している。手順４では、有理点（２χ−１）Ｓ、−Ｓを通る直線における有理点Ｑの値ｌ１を求めその結果をＢに代入している。手順５および６では有理点−ｐＳおよび（２χ−１）ｐＳを求めＴ５およびＴ６にそれぞれ代入している。手順７では、有理点−ｐＳ、（２χ−１）ｐＳを通る直線における有理点Ｑの値ｌ２を求めその結果をＣに代入している。手順８では、Ｂのｐ乗とＣの積をとり、上記（式３１）の内側の｛｝内を求めその結果をｆに代入している。手順９では、上記（式３１）の外側の｛｝を求めその結果をｆに代入している。手順１０では、有理点ｐ１０（（２χ−１）Ｓ）を求めＴ３に代入している。手順１１では、有理点ｐ１０（（２χ−１）Ｓ）、２χＳを通る直線における有理点Ｑの値ｌ３を求めその結果をＢに代入している。手順１２では、有理点ｐ１０（（２χ−１）ｐＳ）を求めその結果をＴ５に代入している。手順１３では、有理点ｐ１０（（２χ−１）ｐＳ）、２χｐＳを通る直線における有理点Ｑの値ｌ４を求めその結果をＣに代入している。手順１４でＢのｐ乗およびＣの積を求め、手順１５で上記（式３１）の全体を求めその結果（ｆ’χ，Ｓ（Ｑ））をｆに代入している。
【０１０９】
本実施形態では、埋め込み次数１２の場合のＴｗｉｓｔｅｄ  Ｘａｔｅマルチペアリング演算について説明したが、埋め込み次数８の場合でも同様のアルゴリズムでＴｗｉｓｔｅｄ  Ｘａｔｅマルチペアリングをより高速に演算できる。Ｔｗｉｓｔｅｄ  Ｘａｔｅと共通する部分については説明を省略する。図７を用いて埋め込み次数が８の場合のマルチペアリング演算について説明する。
【０１１０】
起動したペアリング演算プログラムによって、電子計算機１０では、ＣＰＵ１１を入力手段として機能させて、メモリ装置１３にあらかじめ記憶している整数変数χのデータと、有理点Ｓのデータ、及び署名データとしてメモリ装置１３に一旦記憶された有理点ＱのデータをＣＰＵ１１の内部に設けている所定のレジスタにそれぞれ入力している。（ステップＶ１）。
【０１１１】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、有理点ｐ３Ｓの演算を行い、ｐ３Ｓの値をメモリ装置１３に記憶している。（ステップＶ２）。
【０１１２】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、有理点ｐ３Ｑの演算を行い、ｐ３Ｑの値をメモリ装置１３に記憶している。（ステップＶ３）。
【０１１３】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第１演算手段として機能させて、マルチペアリングに対するミラーのアルゴリズムに
0005549018.tif 000101
（ステップＶ４）。
このステップＶ４では、底を２とする対数の真数が３χ、ｐはすべてｐ３となる以外は図６で示したフローチャートと同じ演算処理を行っている。
【０１１４】
0005549018.tif 000102
の演算結果をメモリ装置１３にそれぞれ記憶している。
【０１１５】
0005549018.tif 000103
リング演算プログラムによってＣＰＵ１１を第２演算手段として機能させて、メモリ装置１３に記憶された３χＳ及び３χｐ３Ｓの値を読み出し、有理点ｐ２（Ｓ）、（３χ＋１）Ｓ、ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓをそれぞれ演算し、各有理点の値をメモリ装置１３に記憶している。（ステップＶ５）。
【０１１６】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第３演算手段として機能させて、ステップＶ５で得られた各有理点の値をメモリ装置１３から読み出し、有理点３χＳ，Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ５と、有理点ｐ２（Ｓ），（３χ＋１）Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ６と、有理点３χｐ３Ｓ，ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ７と、有理点ｐ２（ｐ３Ｓ），（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑ（ｘＱ，ｙＱ）の値ｌ８をそれぞれ演算し、ｌ５、ｌ６、ｌ７およびｌ８の値をメモリ装置１３にそれぞれ記憶している。（ステップＶ６）。
【０１１７】
埋め込み次数が１２の場合と同様に、具体的には、ｌ＝ｌＡ，Ｂ（Ｑ）は、
λＡ，Ｂ←（ｙＢ−ｙＡ）／（ｘＢ−ｘＡ），
ｌＡ，Ｂ（Ｑ）←（ｘＱ−ｘＢ）λＡ，Ｂ−（ｙＱ−ｙＢ）
として演算している。
【０１１８】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第４演算手段として機能させて、メモリ装置１３に記憶された第１演算手段での演算結果と、第３演算手段での演算結果（ｌ５、ｌ６、ｌ７、及びｌ８の値）をメモリ装置１３から読み出し
【数８２】
0005549018.tif 000104
となるｆ’χ，Ｓ（Ｑ）を演算し、その演算結果をメモリ装置１３に記憶している（ステップＶ７）。
【０１１９】
具体的には、
ｉｎｐｕｔ：ＺＳ＝｛Ｓ，ｐ３Ｓ∈Ｇ１｝，ＺＱ＝｛ｐ３Ｑ，Ｑ∈Ｇ２｝，３χ，ｐ
ｏｕｔｐｕｔ：ｆ＝ｆ’χ，Ｓ（Ｑ）
ｐｒｏｃｅｄｕｒｅ：
0005549018.tif 000105
0005549018.tif 000106
として演算している。すなわち、ＣＰＵ１１は、メモリ装置１３を用いて上記手順の各演算を行いｆ’χ，Ｓ（Ｑ）を得てその値をメモリ装置１３に記憶している。具体的には、手順１ではマルチペアリングに対するミラーのアルゴリズムにより
0005549018.tif 000107
を求めその結果をＡに代入するとともに、同時に得られた３χＳおよび３χｐ３ＳをＴ１およびＴ２にそれぞれ代入している。手順２では、有理点３χＳ、Ｓを通る直線における有理点Ｑの値ｌ５を求めその結果をＢに代入している。手順３および４では有理点（３χ＋１）Ｓおよびｐ２（Ｓ）を求めＴ３およびＴ４にそれぞれ代入している。手順５では、有理点ｐ２（Ｓ）、（３χ＋１）Ｓを通る直線における有理点Ｑの値ｌ６を求めその結果をＣに代入している。手順６では、Ｂ及びＣの積をとり、上記（式３２）の｛｝内を求めその結果をｆに代入している。手順７では、上記（式３２）の｛｝部分を求め、手順８では、上記（式３２）の｛｝部分までの結果を求めｆに代入している。手順９では、有理点３χｐ３Ｓ、ｐ３Ｓを通る直線における有理点Ｑの値ｌ７を求めその結果をＢに代入している。手順１０および１１では、有理点（３χ＋１）ｐ３Ｓ、ｐ２（ｐ３Ｓ）を求めその結果をそれぞれＴ３およびＴ４に代入している。手順１２では、有理点ｐ２（ｐ３Ｓ）、（３χ＋１）ｐ３Ｓを通る直線における有理点Ｑの値ｌ８を求めその結果をＣに代入している。手順１３でｆ’χ、Ｓ（Ｑ）を求めその結果をｆに代入している。
【０１２０】
次いで、電子計算機１０では、ペアリング演算プログラムによってＣＰＵ１１を第５演算手段として機能させて、ステップＶ７で得られたｆ’χ，Ｓ（Ｑ）の値をメモリ装置１３から読み出し、ペアリングｅ（Ｓ，Ｑ）における最終べきのべき乗算を行い、その演算結果をメモリ装置１３に記憶している（ステップＶ８）。
【０１２１】
なお、上述においては、各演算結果を記憶する記憶手段としてメモリ装置１３を用いることとしたが、ＣＰＵ１１の内部に設けているレジスタを上記記憶手段として用いるようにしてもよい。
【符号の説明】
【０１２２】
１０  電子計算機
１１  ＣＰＵ
１２  記憶装置
１３  メモリ装置
１４  バス
１５  入出力制御部
２０  電気通信回線
３０  クライアント装置
【図１】
0005549018.tif 000159
【図２】
0005549018.tif 000160
【図３】
0005549018.tif 000161
【図４】
0005549018.tif 000162
【図５】
0005549018.tif 000163
【図６】
0005549018.tif 000164
【図７】
0005549018.tif 000165
【図８】
0005549018.tif 000166