ペアリング演算装置及び方法
【課題】Tateペアリング及びηTペアリングの両方に対処可能な小規模な回路構成を実現する。
【解決手段】有限体GF上の楕円曲線上の点Qから、写像ψの逆写像ψ-1(Q)を算出する第1回路、楕円曲線上の点Qと第1回路の出力とのいずれかを出力する第1選択回路、楕円曲線上の点P及び第1選択回路の出力に対して、ηTペアリングの値を算出するペアリング計算回路と、ペアリング計算回路の出力に対して、有限体における3MT2／Ｌ乗演算を実施する第2回路、ペアリング計算回路の出力と第2回路の出力とのいずれかを出力する第2選択回路と、Tateペアリングの計算結果を出力する場合には第1選択回路に第1回路の出力をペアリング計算回路に出力させ且つ第2選択回路に第2回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第1選択回路に楕円曲線上の点Qを出力させ且つ第2選択回路にペアリング計算回路の出力を出力させる制御回路とを有する。
【解決手段】有限体GF上の楕円曲線上の点Qから、写像ψの逆写像ψ-1(Q)を算出する第1回路、楕円曲線上の点Qと第1回路の出力とのいずれかを出力する第1選択回路、楕円曲線上の点P及び第1選択回路の出力に対して、ηTペアリングの値を算出するペアリング計算回路と、ペアリング計算回路の出力に対して、有限体における3MT2／Ｌ乗演算を実施する第2回路、ペアリング計算回路の出力と第2回路の出力とのいずれかを出力する第2選択回路と、Tateペアリングの計算結果を出力する場合には第1選択回路に第1回路の出力をペアリング計算回路に出力させ且つ第2選択回路に第2回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第1選択回路に楕円曲線上の点Qを出力させ且つ第2選択回路にペアリング計算回路の出力を出力させる制御回路とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、有限体における楕円曲線上のペアリング演算技術に関する。
【背景技術】
【０００２】
情報通信技術で広く用いられる技術の１つとして、暗号化のための鍵を公開する公開鍵暗号の技術が知られている。公開鍵暗号とは、暗号化と復号化とで一対の異なる鍵を用いる暗号である。公開鍵暗号の技術は、鍵の管理が煩雑であることや特定のグループのみが解読可能となるブロードキャスト暗号が未整備であるといった問題がある。近年、これらの問題を解決する手法として、ペアリングを用いた暗号（以下、ペアリング暗号と呼ぶ）が注目されている。ペアリング暗号では、ＩＤを公開鍵とするＩＤベース暗号、ブロードキャスト暗号、アグリゲート（aggregate）署名などを実現できる。しかし、暗号技術として使用されているペアリングは複数あり、現在暗号で使用するペアリングの標準化は進んでいない。
【０００３】
ペアリング暗号では楕円曲線上のペアリングと呼ばれる演算を使用する。まず、楕円曲線について説明する。ｐを素数、ｍを自然数とすると、要素数ｑ＝ｐmの有限体ＧＦ（ｑ）上の楕円曲線Ｅとは、
Ｅ：ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6
を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる点∞を加えた集合のことである。無限遠点∞を０と表すこともある。ここで、ａ1、ａ2、ａ3、ａ4、ａ6、ｘ及びｙは有限体ＧＦ（ｑ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式（すなわち、アファイン座標）で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現できない唯一の点である。このように、アファイン座標では無限遠点以外の点はＧＦ（ｑ）の２つの要素の組として表される。楕円曲線Ｅ上の点の間には点の加算と呼ばれる演算が可能であり、ＧＦ（ｑ）における加減乗除の組み合わせによって計算される。
【０００４】
ペアリングとは２入力１出力関数で、３つの群Ｇ1，Ｇ2，Ｇ3に対して、写像ｅ：Ｇ1×Ｇ2−＞Ｇ3で以下の性質を満たすものをいう。
（１）ｅ(au+bv，x) ＝ａ・ｅ(ｕ，ｘ) ＋ｂ・ｅ(ｖ，ｘ)
（２）ｅ(u，cx+dz) ＝ｃ・ｅ(ｕ，ｘ) ＋ｄ・ｅ(ｕ，ｚ)
【０００５】
暗号技術として使用されるペアリングの例として以下のものがある。
（ａ）Weilペアリング
（ｂ）Ｔａｔｅペアリング
（ｃ）ηTペアリング
（ｄ）Ateペアリング、Twisted Ateペアリングなど
【０００６】
ここで、ＴａｔｅペアリングとηTペアリングについて説明する。まず、楕円曲線上のＴａｔｅペアリングについて説明する。次の式で定義される有限体ＧＦ（３3）上の楕円曲線を考える。
Ｅ：ｙ2＝ｘ3−ｘ＋ｂ
（但し、ｂ＝−１又は１とする）
【０００７】
Ｔａｔｅペアリングは、楕円曲線Ｅ上の２点Ｐ，Ｑに関して、ある値を返す関数ｅ（Ｐ，Ｑ）である。また、ηTペアリングは、Ｔａｔｅペアリングをより高速計算可能に改良したペアリングである。
【０００８】
なお、ηTペアリングとＴａｔｅペアリングには、以下の式（１）のような関係がある。
(ηT(Ｐ，Ｑ)M)^{3T2}＝ｅ(Ｐ，ψ(Ｑ))L （１）
【０００９】
ここで、Ｍ、Ｔ、Ｌ及び写像ψは以下のように定義される。
Ｍ＝(36m−１)／(３m＋ｂ３{(m+1)/2}＋１)
Ｔ＝−ｂ３{(m+1)/2}−１
Ｌ＝−ｂ３{(m+3)/2}
ψ(x,y) ＝(ρ−ｘ，σｙ) (但し、σ，ρはσ2＝−１，ρ3＝ρ＋ｂを満たす元)
【００１０】
ＴａｔｅペアリングとηTペアリングの間に成り立つ式（１）を変形して、以下のような式に変形されることも知られている。
ｅ(Ｐ，ψ(Ｑ))＝(ηT（Ｐ，Ｑ）M)^{3T2/L} （２）
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００８−２０６５３号公報
【特許文献２】特開平７−２６１６６２号公報
【非特許文献】
【００１２】
【非特許文献１】岡本栄司、岡本健、金山直樹、「ペアリングに関する最近の研究動向」，Fundamentals Review, Vol. 1, No. 1，pp.51-60, 2007/07
【発明の概要】
【発明が解決しようとする課題】
【００１３】
従来、個別にペアリングのハードウエア化について検討が行われている。しかしながら、暗号技術として使用されているペアリングは複数あり、現在暗号で使用するペアリングの標準化が進んでいない。そのため、小規模の回路で複数のペアリング演算を実施することが望まれている。
【００１４】
従って、本技術の目的は、ＴａｔｅペアリングとηTペアリングとを小規模な回路で実現するための技術を提供することである。
【課題を解決するための手段】
【００１５】
第１の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する第１の選択回路と、（Ｃ）楕円曲線上の点Ｐ及び第１の選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、（Ｄ）ηTペアリング計算回路の出力に対して、有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTペアリング計算回路の出力と第２の回路の出力とのいずれかを出力する第２の選択回路と、（Ｆ）Ｔａｔｅペアリングの計算結果を出力する場合には第１の選択回路に第１の回路の出力をηTペアリング計算回路に出力させ且つ第２の選択回路に第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第１の選択回路に楕円曲線上の点Ｑを出力させ且つ第２の選択回路にηTペアリング計算回路の出力を出力させる制御回路とを有する。
【００１６】
第２の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する第１の選択回路と、（Ｃ）楕円曲線上の点Ｐ及び第１の選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路と、（Ｆ）第２の回路の出力と第３の回路の出力とのいずれかを出力する第２の選択回路と、（Ｇ）Ｔａｔｅペアリングの計算結果を出力する場合には第１の選択回路に第１の回路の出力をηTkペアリング計算回路に出力させ且つ第２の選択回路に第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第１の選択回路に楕円曲線上の点Ｑを出力させ且つ第２の選択回路に第３の回路の出力を出力させる制御回路とを有する。
【００１７】
第３の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路と、（Ｅ）Ｔａｔｅペアリングの計算結果を出力する場合には選択回路に第１の回路の出力をηTkペアリング計算回路に出力させ且つべき乗演算回路に有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施させ、ηTペアリングの計算結果を出力する場合には選択回路に楕円曲線上の点Ｑを出力させ且つべき乗演算回路に１／ｋ乗演算を実施させる制御回路とを有する。
【発明の効果】
【００１８】
ＴａｔｅペアリングとηTペアリングとを小規模な回路で実現できるようになる。
【図面の簡単な説明】
【００１９】
【図１】図１は、第１の実施の形態に係るペアリング演算装置の回路構成例を示す図である。
【図２】図２は、第１の実施の形態に係るηTペアリング計算部の回路構成例を示す図である。
【図３】図３は、第１の実施の形態においてＴａｔｅペアリング計算を実施する場合の処理フローを示す図である。
【図４】図４は、第１の実施の形態においてηTペアリング計算を実施する際の処理フローを示す図である。
【図５】図５は、第２の実施の形態に係るペアリング演算装置の回路構成例を示す図である。
【図６】図６は、第２の実施の形態に係るηTkペアリング計算部の回路構成例を示す図である。
【図７】図７は、第２の実施の形態においてＴａｔｅペアリング計算を実施する場合の処理フローを示す図である。
【図８】図８は、第２の実施の形態においてηTペアリング計算を実施する際の処理フローを示す図である。
【図９】図９は、第３の実施の形態に係るペアリング演算装置の回路構成例を示す図である。
【図１０】図１０は、第３の実施の形態においてＴａｔｅペアリング計算を実施する場合の処理フローを示す図である。
【図１１】図１１は、第３の実施の形態においてηTペアリング計算を実施する際の処理フローを示す図である。
【図１２】図１２は、実施の形態間の効果比較表を示す図である。
【図１３】図１３は、ＩＣカードの一例を示す図である。
【発明を実施するための形態】
【００２０】
［実施の形態１］
本技術の第１の実施の形態では、上で述べた式（２）に基づいた回路構成を採用する。なお、このような回路構成については公開されたものはない。
【００２１】
本実施の形態に係るペアリング演算装置１００の回路構成図を図１に示す。本ペアリング演算装置１００は、レジスタＱと、レジスタＰと、ψ-1（Ｑ）演算部１０１と、セレクタ１０２と、ηTペアリング計算部１０３と、｛３ＭＴ2／Ｌ｝乗演算部１０５と、セレクタ１０６と、レジスタ１０７と、制御部１０４とを有する。
【００２２】
レジスタＱは、有限体ＧＦ（３3）における楕円曲線Ｅ：ｙ2＝ｘ3−ｘ＋ｂ（但し、ｂ＝−１又は１とする）上の点Ｑ（ｘq，ｙq）の値を格納するレジスタであり、ψ-1（Ｑ）演算部１０１及びセレクタ１０２に接続されている。レジスタＰは、上で述べた楕円曲線上の点Ｐ（ｘp，ｙp）の値を格納するレジスタであり、ηTペアリング計算部１０３に接続されている。
【００２３】
ψ-1（Ｑ）演算部１０１は、点Ｑに対して、写像ψ(x,y) ＝(ρ−ｘ，σｙ) (但し、σ，ρはσ2＝−１，ρ3＝ρ＋ｂを満たす元)の逆写像ψ-1（Ｑ）を計算する回路であり、セレクタ１０２に接続されている。なお、ψ-1（Ｑ）＝（ρ-ｘq，σ-1ｙq）となる。
【００２４】
セレクタ１０２には、ψ-1（Ｑ）演算部１０１からの出力とレジスタＱからの値とが入力されており、セレクタ１０２は、選択信号の値に応じていずれかをηTペアリング計算部１０３に出力する。本実施の形態では、選択信号「０」が入力された場合にはレジスタＱからの値を出力し、選択信号「１」が入力された場合にはψ-1（Ｑ）演算部１０１からの出力を出力する。
【００２５】
ηTペアリング計算部１０３は、レジスタＰからの出力とセレクタ１０２からの出力とを用いて、ηTペアリング計算を実施する回路であり、｛３ＭＴ2／Ｌ｝乗演算部１０５とセレクタ１０６とに接続されている。ηTペアリング計算部１０３により実施される演算は、例えば以下のような演算である。なお、Ｐ＝（ｘp，ｙp）及びＱ＝（ｘq，ｙq）を処理する場合を示している。
【００２６】
【数１】
【００２７】
｛３ＭＴ2／Ｌ｝乗演算部１０５は、ηTペアリング計算部１０３の出力を、上で述べた有限体において｛３ＭＴ2／Ｌ｝乗する演算を行う回路であり、セレクタ１０６に接続されている。ここで、Ｍ、Ｔ及びＬは以下のように定義される。
Ｍ＝(36m−１)／(３m＋ｂ３{(m+1)/2}＋１)
Ｔ＝−ｂ３{(m+1)/2}−１
Ｌ＝−ｂ３{(m+3)/2}
【００２８】
これらの値については外部からｍ及びｂの値が与えられてレジスタなどに保持しておき、実際の演算時に算出するようにしてもよいし、最終的なＭ、Ｔ及びＬの値をｍ及びｂから事前に演算した後にレジスタなどに保持しておくようにしてもよい。
【００２９】
なお、有限体におけるべき乗演算については、よく知られたいずれの方法でも良い。
【００３０】
セレクタ１０６には、｛３ＭＴ2／Ｌ｝乗演算部１０５からの出力とηTペアリング計算部１０３からの出力とが入力されており、セレクタ１０６は、選択信号「０」が入力された場合にはηTペアリング計算部１０３からの出力を出力し、選択信号「１」が入力された場合には｛３ＭＴ2／Ｌ｝乗演算部１０５からの出力を出力する。セレクタ１０６の出力は、レジスタ１０７に接続されている。レジスタ１０７には、Ｔａｔｅペアリングの値ｅ（Ｐ，Ｑ）又はηTペアリングの値ηT（Ｐ，Ｑ）が格納される。
【００３１】
制御部１０４は、セレクタ１０２及び１０６に接続されており、外部からηTペアリングの値の算出を指示された場合には、選択信号「０」を出力し、外部からＴａｔｅペアリングの値の算出を指示された場合には、選択信号「１」を出力する。
【００３２】
ηTペアリング計算部１０３の構成例を図２に示す。ηTペアリング計算部１０３は、セレクタ１０２からの出力を格納するレジスタｘ1及びｙ1と、レジスタＰに格納されている点Ｐの値を格納するレジスタｘ2及びｙ2と、有限体上の加算及び乗算を行う加算・乗算回路１０３１と、有限体上の三乗演算を行う３乗計算回路１０３２と、有限体上の１／３乗計算を行う１／３乗計算回路１０３３と、出力値を格納するレジスタｆとを有する。加算・乗算回路１０３１と３乗計算回路１０３２と１／３乗計算回路１０３３とは、上で述べたアルゴリズムを実施する際に用いられる。
【００３３】
次に、図１のペアリング演算装置１００の動作を図３及び図４を用いて説明する。まず、Ｔａｔｅペアリングの計算を指示された場合の処理を図３を用いて説明する。この場合、制御部１０４は、選択信号「１」をセレクタ１０２及び１０６に出力する（ステップＳ１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTペアリング計算部１０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部１０１及びセレクタ１０２に入力する（ステップＳ３）。
【００３４】
そして、ψ-1（Ｑ）演算部１０１は、楕円曲線上の点Ｑに対してψ-1（Ｑ）を計算し、セレクタ１０２に出力する（ステップＳ５）。セレクタ１０２では、制御部１０４から選択信号「１」が入力されているので、ψ-1（Ｑ）演算部１０１の出力をηTペアリング計算部１０３に出力する。
【００３５】
ηTペアリング計算部１０３は、セレクタ１０２からの出力ψ-1（Ｑ）とレジスタＰからの値とから、ｚ＝ηT(Ｐ，ψ-1)を計算し、セレクタ１０６及び｛３ＭＴ2／Ｌ｝乗演算部１０５に出力する（ステップＳ７）。
【００３６】
｛３ＭＴ2／Ｌ｝乗演算部１０５は、ηTペアリング計算部１０３からの出力ｚの｛３ＭＴ2／Ｌ｝乗演算を実施して、演算結果をセレクタ１０６に出力する（ステップＳ９）。
【００３７】
セレクタ１０６は、選択信号「１」が入力されているので、｛３ＭＴ2／Ｌ｝乗演算部１０５の出力ｅ（Ｐ，Ｑ）＝ｚ^｛３ＭＴ2／Ｌ｝を出力し、レジスタ１０７に格納する（ステップＳ１１）。
【００３８】
一方、ηTペアリングの計算を指示された場合の処理を図４を用いて説明する。この場合、制御部１０４は、選択信号「０」をセレクタ１０２及び１０６に出力する（ステップＳ２１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTペアリング計算部１０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部１０１及びセレクタ１０２に入力する（ステップＳ２３）。セレクタ１０２は、選択信号「０」に応じて、レジスタＱからの出力値（点Ｑの値）をそのままηTペアリング計算部１０３に出力する。
【００３９】
そして、ηTペアリング計算部１０３は、セレクタ１０２からの出力である点Ｑの値とレジスタＰからの出力値（点Ｐの値）とから、ｚ＝ηT(Ｐ，Ｑ)を計算し、セレクタ１０６及び｛３ＭＴ2／Ｌ｝乗演算部１０５に出力する（ステップＳ２５）。
【００４０】
セレクタ１０６は、選択信号「０」に応じて、ηTペアリング計算部１０３からの出力ηT（Ｐ，Ｑ）をηTペアリングの値として出力し、レジスタ１０７に格納する（ステップＳ２７）。
【００４１】
以上のように、ηTペアリング計算部１０３をηTペアリングの計算及びＴａｔｅペアリングの計算で共用するので、回路規模を小さくしつつ、２つのペアリングに対処できるようなペアリング演算装置１００が得られる。
【００４２】
［実施の形態２］
図２に示したように、第１の実施の形態におけるηTペアリング計算部１０３は、１／３乗計算回路１０３３を含むため、処理時間がかかるという問題がある。そこで、ηTペアリングのｋ（＝３（ｍ＋１）／２）乗であるηTkペアリング計算を実施することによって、１／３乗演算を除去する。なお、余分にｋ乗しているので、１／ｋ乗演算を追加すると共に｛３ＭＴ2／Ｌ｝乗を｛３ＭＴ2／（Ｌｋ）｝乗に変更する。ηTペアリング計算の中で１／３乗演算を行うよりも１／ｋ乗演算を実施する方が高速に演算できるので、全体としても演算の高速化が可能となる。
【００４３】
図５に、本実施の形態に係るペアリング演算装置２００の回路構成を示す。本ペアリング演算装置２００は、レジスタＱと、レジスタＰと、ψ-1（Ｑ）演算部２０１と、セレクタ２０２と、ηTkペアリング計算部２０３と、｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５と、セレクタ２０６と、レジスタ２０７と、制御部２０４と、｛１／ｋ｝乗演算部２０８とを有する。
【００４４】
レジスタＱは、有限体ＧＦ（３3）における楕円曲線Ｅ：ｙ2＝ｘ3−ｘ＋ｂ（但し、ｂ＝−１又は１とする）上の点Ｑ（ｘq，ｙq）の値を格納するレジスタであり、ψ-1（Ｑ）演算部２０１及びセレクタ２０２に接続されている。レジスタＰは、上で述べた楕円曲線上の点Ｐ（ｘp，ｙp）の値を格納するレジスタであり、ηTkペアリング計算部２０３に接続されている。
【００４５】
ψ-1（Ｑ）演算部２０１は、点Ｑに対して、写像ψ(x,y) ＝(ρ−ｘ，σｙ) (但し、σ，ρはσ2＝−１，ρ3＝ρ＋ｂを満たす元)の逆写像ψ-1（Ｑ）を計算する回路であり、セレクタ２０２に接続されている。なお、ψ-1（Ｑ）＝（ρ-ｘq，σ-1ｙq）となる。
【００４６】
セレクタ２０２には、ψ-1（Ｑ）演算部２０１からの出力とレジスタＱからの値とが入力されており、セレクタ２０２は、選択信号の値に応じていずれかをηTkペアリング計算部２０３に出力する。本実施の形態では、選択信号「０」が入力された場合にはレジスタＱからの値を出力し、選択信号「１」が入力された場合にはψ-1（Ｑ）演算部２０１からの出力を出力する。
【００４７】
ηTkペアリング計算部２０３は、レジスタＰからの出力とセレクタ２０２からの出力とを用いて、ηTkペアリング計算を実施する回路であり、｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５と｛１／ｋ｝乗演算部２０８とに接続されている。ηTkペアリング計算部２０３により実施される演算は、例えば以下のような演算である。なお、Ｐ＝（ｘp，ｙp）及びＱ＝（ｘq，ｙq）を処理する場合を示している。
【００４８】
【数２】
【００４９】
｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５は、ηTkペアリング計算部２０３の出力を、上で述べた有限体において｛３ＭＴ2／（Ｌｋ）｝乗する演算を行う回路であり、セレクタ２０６に接続されている。Ｍ、Ｔ及びＬは第１の実施の形態と同じである。ｋも、上で述べたように、ｋ＝３（ｍ＋１）／２である。
【００５０】
これらの値については外部からｍ及びｂの値が与えられてレジスタなどに保持しておき、実際の演算時に算出するようにしてもよいし、最終的なＭ、Ｔ及びＬの値をｍ及びｂから事前に演算した後にレジスタなどに保持しておくようにしてもよい。
【００５１】
また、｛１／ｋ｝乗演算部２０８は、ηTkペアリング計算部２０３の出力を、上で述べた有限体において｛１／ｋ｝乗する演算を行う回路であり、セレクタ２０６に接続されている。１／ｋについても、ｍ又はｋをレジスタに保持しておくようにしておき演算時に１／ｋを算出するようにしても良いし、最終的な値｛１／ｋ｝を事前に算出後にレジスタなどに保持しておくようにしても良い。
【００５２】
有限体におけるべき乗演算については、第１の実施の形態と同じように、よく知られた方法で実施可能である。
【００５３】
セレクタ２０６には、｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５からの出力と｛１／ｋ｝乗演算部２０８からの出力とが入力されており、セレクタ２０６は、選択信号「０」が入力された場合には｛１／ｋ｝乗演算部２０８からの出力を出力し、選択信号「１」が入力された場合には｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５からの出力をレジスタ２０７に出力する。セレクタ２０６の出力は、レジスタ２０７に接続されている。レジスタ２０７には、Ｔａｔｅペアリングの値ｅ（Ｐ，Ｑ）又はηTペアリングの値ηT（Ｐ，Ｑ）が格納される。
【００５４】
制御部２０４は、セレクタ２０２及び２０６に接続されており、外部からηTペアリングの値の算出を指示された場合には、選択信号「０」を出力し、外部からＴａｔｅペアリングの値の算出を指示された場合には、選択信号「１」を出力する。
【００５５】
ηTkペアリング計算部２０３の構成例を図６に示す。ηTkペアリング計算部２０３は、セレクタ２０２からの出力値を格納するレジスタｘ1及びｙ1と、レジスタＰに格納されている点Ｐの値を格納するレジスタｘ2及びｙ2と、有限体上の加算及び乗算を行う加算・乗算回路２０３１と、有限体上の三乗演算を行う３乗計算回路２０３２と、出力値を格納するレジスタｆとを有する。加算・乗算回路２０３１と３乗計算回路２０３２とは、上で述べたアルゴリズムを実施する際に用いられる。この図からも分かるように、ηTkペアリング計算部２０３には、１／３乗計算回路１０３３は含まれておらず、その分処理速度も速くなる。
【００５６】
次に、図５のペアリング演算装置２００の動作を図７及び図８を用いて説明する。まず、Ｔａｔｅペアリングの計算を指示された場合の処理を図７を用いて説明する。この場合、制御部２０４は、選択信号「１」をセレクタ２０２及び２０６に出力する（ステップＳ３１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTkペアリング計算部２０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部２０１及びセレクタ２０２に入力する（ステップＳ３３）。
【００５７】
そして、ψ-1（Ｑ）演算部２０１は、楕円曲線上の点Ｑに対してψ-1（Ｑ）を計算し、セレクタ２０２に出力する（ステップＳ３５）。セレクタ２０２では、制御部２０４から選択信号「１」が入力されているので、ψ-1（Ｑ）演算部２０１の出力をηTkペアリング計算部２０３に出力する。
【００５８】
ηTkペアリング計算部２０３は、セレクタ２０２からの出力ψ-1（Ｑ）とレジスタＰからの値とから、ｚ＝ηT(Ｐ，ψ-1)kを計算し、｛１／ｋ｝乗演算部２０８及び｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５に出力する（ステップＳ３７）。
【００５９】
｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５は、ηTkペアリング計算部２０３からの出力ｚの｛３ＭＴ2／（Ｌｋ）｝乗演算を実施して、セレクタ２０６に出力する（ステップＳ３９）。
【００６０】
セレクタ２０６は、選択信号「１」が入力されているので、｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５の出力ｅ（Ｐ，Ｑ）＝ｚ^｛３ＭＴ2／（Ｌｋ）｝を出力し、レジスタ２０７に格納する（ステップＳ４１）。
【００６１】
一方、ηTペアリングの計算を指示された場合の処理を図８を用いて説明する。この場合、制御部２０４は、選択信号「０」をセレクタ２０２及び２０６に出力する（ステップＳ５１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTkペアリング計算部２０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部２０１及びセレクタ２０２に入力する（ステップＳ５３）。セレクタ２０２は、選択信号「０」に応じて、レジスタＱからの出力値（点Ｑの値）をそのままηTkペアリング計算部２０３に出力する。
【００６２】
そして、ηTkペアリング計算部２０３は、セレクタ２０２からの出力である点Ｑの値とレジスタＰからの出力値（点Ｐの値）とから、ｚ＝ηT(Ｐ，Ｑ)kを計算し、｛１／ｋ｝乗演算部２０８及び｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５に出力する（ステップＳ５５）。
【００６３】
｛１／ｋ｝乗演算部２０８は、ηTkペアリング計算部２０３から入力されたｚ＝ηT(Ｐ，Ｑ)kの１／ｋ乗であるｚ1/kを計算して、セレクタ２０６に出力する（ステップＳ５７）。
【００６４】
セレクタ２０６は、選択信号「０」に応じて、｛１／ｋ｝乗演算部２０８からの出力ηT（Ｐ，Ｑ）（＝ｚ1/k）をηTペアリングの値として出力し、レジスタ１０７に格納する（ステップＳ５９）。
【００６５】
以上のように、ηTkペアリング計算部２０３をηTペアリング計算部１０３の代わりに導入することによって、全体の処理が高速化される。なお、図２と図６との比較からして、回路規模については第１の実施の形態とほぼ同じになっている。
【００６６】
［実施の形態３］
第２の実施の形態では、ηTkペアリング計算部２０３を導入する代わりに、｛１／ｋ｝乗演算部２０８を導入している。しかし、べき乗演算は、そもそも｛３ＭＴ2／Ｌ｝乗演算部１０５が設けられていた。そこで、｛１／ｋ｝乗演算部２０８及び｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５とを統合してｓ乗演算部を導入してｓの値を切り替えることによって、回路の共通化により全体の回路規模を小さくする。
【００６７】
図９に、本実施の形態に係るペアリング演算装置３００の回路構成を示す。本ペアリング演算装置３００は、レジスタＱと、レジスタＰと、ψ-1（Ｑ）演算部３０１と、セレクタ３０２と、ηTkペアリング計算部３０３と、ｓ乗演算部３０８と、セレクタ３０６と、最終結果を格納するレジスタ３０７と、制御部３０４と、｛１／ｋ｝の値を格納するレジスタ３０９と、｛３ＭＴ2／（Ｌｋ）｝の値を格納するレジスタ３１０とを有する。
【００６８】
レジスタＱは、有限体ＧＦ（３3）における楕円曲線Ｅ：ｙ2＝ｘ3−ｘ＋ｂ（但し、ｂ＝−１又は１とする）上の点Ｑ（ｘq，ｙq）の値を格納するレジスタであり、ψ-1（Ｑ）演算部３０１及びセレクタ３０２に接続されている。レジスタＰは、上で述べた楕円曲線上の点Ｐ（ｘp，ｙp）の値を格納するレジスタであり、ηTkペアリング計算部３０３に接続されている。
【００６９】
ψ-1（Ｑ）演算部３０１は、点Ｑに対して、写像ψ(x,y) ＝(ρ−ｘ，σｙ) (但し、σ，ρはσ2＝−１，ρ3＝ρ＋ｂを満たす元)の逆写像ψ-1（Ｑ）を計算する回路であり、セレクタ３０２に接続されている。なお、ψ-1（Ｑ）＝（ρ-ｘq，σ-1ｙq）となる。
【００７０】
セレクタ３０２には、ψ-1（Ｑ）演算部３０１からの出力とレジスタＱからの値とが入力されており、セレクタ３０２は、選択信号の値に応じていずれかをηTkペアリング計算部３０３に出力する。本実施の形態でも、選択信号「０」が入力された場合にはレジスタＱからの値を出力し、選択信号「１」が入力された場合にはψ-1（Ｑ）演算部３０１からの出力を出力する。
【００７１】
ηTkペアリング計算部３０３は、レジスタＰからの出力とセレクタ３０２からの出力とを用いて、ηTkペアリング計算を実施する回路であり、ｓ乗演算部３０８に接続されている。ηTkペアリング計算部３０３により実施される演算は、第２の実施の形態で示したものと同じである。
【００７２】
レジスタ３０９とレジスタ３１０とはセレクタ３０６に接続されており、セレクタ３０６の出力はｓ乗演算部３０８に接続されている。セレクタ３０６は、選択信号の値に応じていずれかをｓ乗演算部３０８に出力する。本実施の形態では、選択信号「０」が入力された場合にはレジスタ３０９からの値をｓ乗演算部３０８に出力し、選択信号「１」が入力された場合にはレジスタ３１０からの値をｓ乗演算部３０８に出力する。
【００７３】
ｓ乗演算部３０８は、ηTkペアリング計算部３０３の出力ｚを、有限体においてｓ（ｓはセレクタ３０６の出力値）乗する演算を実施する回路であり、レジスタ３０７に接続されている。ｓ乗演算部３０８は、演算結果をレジスタ３０７に格納する。なお、有限体におけるべき乗演算については、よく知られた演算であるからここでは詳しく述べない。
【００７４】
制御部３０４は、セレクタ３０２及び３０６に接続されており、外部からηTペアリングの値の算出を指示された場合には、選択信号「０」を出力し、外部からＴａｔｅペアリングの値の算出を指示された場合には、選択信号「１」を出力する。
【００７５】
次に、図１０及び図１１を用いてペアリング演算装置３００の動作を説明する。
【００７６】
まず、Ｔａｔｅペアリングの計算を指示された場合の処理を図１０を用いて説明する。この場合、制御部３０４は、選択信号「１」をセレクタ３０２及び３０６に出力する（ステップＳ６１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTkペアリング計算部３０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部３０１及びセレクタ３０２に入力する（ステップＳ６３）。
【００７７】
そして、ψ-1（Ｑ）演算部３０１は、楕円曲線上の点Ｑに対してψ-1（Ｑ）を計算し、セレクタ３０２に出力する（ステップＳ６５）。セレクタ３０２では、制御部３０４から選択信号「１」が入力されているので、ψ-1（Ｑ）演算部３０１の出力をηTkペアリング計算部３０３に出力する。
【００７８】
ηTkペアリング計算部２０３は、セレクタ３０２からの出力ψ-1（Ｑ）とレジスタＰからの値とから、ｚ＝ηT(Ｐ，ψ-1)kを計算し、ｓ乗演算部３０８に出力する（ステップＳ６７）。
【００７９】
また、セレクタ３０６は、制御部３０４からの選択信号「１」に応じて、レジスタ３１０からの値｛３ＭＴ2／（Ｌｋ）｝をｓ乗演算部３０８に出力する。
【００８０】
ｓ乗演算部３０８は、ηTkペアリング計算部２０３からの出力ｚに対して、セレクタ３０６からのｓ＝｛３ＭＴ2／（Ｌｋ）｝に応じてｓ乗演算を実施して、ｚ＾｛３ＭＴ2／（Ｌｋ）｝を算出する（ステップＳ６９）。そして、ｓ乗演算部３０８は、演算結果ｚ＾｛３ＭＴ2／（Ｌｋ）｝を、Ｔａｔｅペアリングの結果ｅ（Ｐ，Ｑ）＝ｚ^｛３ＭＴ2／（Ｌｋ）｝として、レジスタ３０７に出力して格納する（ステップＳ７１）。
【００８１】
一方、ηTペアリングの計算を指示された場合の処理を図１１を用いて説明する。この場合、制御部３０４は、選択信号「０」をセレクタ３０２及び３０６に出力する（ステップＳ８１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTkペアリング計算部３０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部３０１及びセレクタ３０２に入力する（ステップＳ８３）。セレクタ３０２は、選択信号「０」に応じて、レジスタＱからの出力値（点Ｑの値）をそのままηTkペアリング計算部３０３に出力する。
【００８２】
そして、ηTkペアリング計算部３０３は、セレクタ３０２からの出力である点Ｑの値とレジスタＰからの出力値（点Ｐからの値）とから、ｚ＝ηT(Ｐ，Ｑ)kを計算し、ｓ乗演算部３０８に出力する（ステップＳ８５）。
【００８３】
また、セレクタ３０６は、制御部３０４からの選択信号「０」に応じて、レジスタ３０９からの値｛１／ｋ｝をｓ乗演算部３０８に出力する。
【００８４】
ｓ乗演算部３０８は、ηTkペアリング計算部３０３からの出力ｚに対して、セレクタ３０６からのｓ＝｛１／ｋ｝に応じてｓ乗演算を実施して、ｚ＾｛１／ｋ｝を算出する（ステップＳ８７）。そして、ｓ乗演算部３０８は、演算結果ｚ＾｛１／ｋ｝を、ηTペアリングの値としてレジスタ３０７に出力して格納する（ステップＳ８９）。
【００８５】
以上のように、べき乗演算を共通の回路で実施することによって小さな回路規模で２つのペアリングの演算が可能となる。
【００８６】
図１２に３つの実施の形態の処理速度及び回路規模の比較表を示す。なお、図１２は、第１の実施の形態を基準とした比較表を表している。これを見ると、第２の実施の形態は、第１の実施の形態ではＴａｔｅペアリング計算時には１５％程度の処理の高速化が可能となっている。また、第３の実施の形態は、さらに回路規模も第１の実施の形態に比して１５％程度削減できる。なお、第１の実施の形態は、ηTペアリング計算部１０３を共用しているので、従来に比してその分回路規模は削減できている。
【００８７】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、ペアリング演算装置は、例えば図１３に示すようなＩＣカードに含まれる半導体チップ上に実装される場合もあれば、パーソナルコンピュータやサーバその他のコンピュータに実装される場合もある。ＩＣカードのような小型の装置に実装する場合には、上で述べたような回路規模の削減が大きく寄与する。
【００８８】
べき乗算、ηTペアリング計算やηTkペアリング計算については、さらに高速なアルゴリズムが存在する場合には、それらを採用することも可能である。
【００８９】
以上述べた本実施の形態をまとめると、以下のようになる。
【００９０】
第１の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する第１の選択回路と、（Ｃ）楕円曲線上の点Ｐ及び第１の選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、（Ｄ）ηTペアリング計算回路の出力に対して、有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTペアリング計算回路の出力と第２の回路の出力とのいずれかを出力する第２の選択回路と、（Ｆ）Ｔａｔｅペアリングの計算結果を出力する場合には第１の選択回路に第１の回路の出力をηTペアリング計算回路に出力させ且つ第２の選択回路に第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第１の選択回路に楕円曲線上の点Ｑを出力させ且つ第２の選択回路にηTペアリング計算回路の出力を出力させる制御回路とを有する。
【００９１】
このような回路を採用することによって、ηTペアリング計算回路を共用することによって、ηTペアリングとＴａｔｅペアリングのいずれもに対応するペアリング演算装置の回路規模を削減することができるようになる。
【００９２】
第２の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する第１の選択回路と、（Ｃ）楕円曲線上の点Ｐ及び第１の選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路と、（Ｆ）第２の回路の出力と第３の回路の出力とのいずれかを出力する第２の選択回路と、（Ｇ）Ｔａｔｅペアリングの計算結果を出力する場合には第１の選択回路に第１の回路の出力をηTkペアリング計算回路に出力させ且つ第２の選択回路に第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第１の選択回路に楕円曲線上の点Ｑを出力させ且つ第２の選択回路に第３の回路の出力を出力させる制御回路とを有する。
【００９３】
ηTkペアリング計算回路を導入することによって、処理高速化を阻害する１／３乗演算を除去して、処理速度を向上させることができるようになる。
【００９４】
第３の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路と、（Ｅ）Ｔａｔｅペアリングの計算結果を出力する場合には選択回路に第１の回路の出力をηTkペアリング計算回路に出力させ且つべき乗演算回路に有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施させ、ηTペアリングの計算結果を出力する場合には選択回路に楕円曲線上の点Ｑを出力させ且つべき乗演算回路に１／ｋ乗演算を実施させる制御回路とを有する。
【００９５】
さらに、べき乗演算回路を導入することによって、さらに回路の共用が可能となり、回路規模を削減することができる。
【００９６】
また、第４の態様に係るペアリング演算方法は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、（Ｄ）ηTペアリング計算回路の出力に対して、有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路とを有するペアリング演算装置により実行される。そして、本ペアリング演算方法は、（α）Ｔａｔｅペアリングの値を算出する場合には、第１の回路が前記楕円曲線上の点Ｑから逆写像ψ-1（Ｑ）を算出し、選択回路が第１の回路の出力をηTペアリング計算回路に出力し、ηTペアリング計算回路が第１の回路の出力及び楕円曲線上の点Ｐに対してηTペアリングの値を算出して第２の回路に出力し、第２の回路がηTペアリング計算回路の出力の有限体における３ＭＴ2／Ｌ乗演算を実施して出力するステップと、（β）ηTペアリングの値を算出する場合には、選択回路が楕円曲線上の点ＱをηTペアリング計算回路に出力し、ηTペアリング計算回路が楕円曲線上の点Ｐ及び点Ｑに対して前記ηTペアリングの値を算出して出力するステップとを含む。
【００９７】
小規模な回路構成にて２つのペアリングの演算が可能となる。
【００９８】
また、第５の態様に係るペアリング演算方法は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路とを有するペアリング演算装置により実行される。そして、本ペアリング演算方法は、（α）Ｔａｔｅペアリングの値を算出する場合には、第１の回路が楕円曲線上の点Ｑから逆写像ψ-1（Ｑ）を算出し、選択回路が第１の回路の出力をηTkペアリング計算回路に出力し、ηTkペアリング計算回路が第１の回路の出力及び楕円曲線上の点Ｐに対してηTkペアリングの値を算出して第２の回路に出力し、第２の回路がηTkペアリング計算回路の出力の有限体における３ＭＴ2／Ｌｋ乗演算を実施して出力するステップと、（β）ηTペアリングの値を算出する場合には、選択回路が楕円曲線上の点ＱをηTkペアリング計算回路に出力し、ηTkペアリング計算回路が楕円曲線上の点Ｐ及び点Ｑに対してηTkペアリングの値を算出して第３の回路に出力し、第３の回路がηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップとを含む。
【００９９】
さらに処理速度も高速化することができるようになる。
【０１００】
さらに、第６の態様に係るペアリング演算方法は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路とを有するペアリング演算装置により実行される。そして、ペアリング演算方法は、（α）Ｔａｔｅペアリングの値を算出する場合には、第１の回路が楕円曲線上の点Ｑから逆写像ψ-1（Ｑ）を算出し、選択回路が第１の回路の出力をηTkペアリング計算回路に出力し、ηTkペアリング計算回路が第１の回路の出力及び楕円曲線上の点Ｐに対してηTkペアリングの値を算出してべき乗演算回路に出力し、べき乗演算回路がηTkペアリング計算回路の出力の有限体における３ＭＴ2／（Ｌｋ）乗演算を実施して出力するステップと、（β）ηTペアリングの値を算出する場合には、選択回路が楕円曲線上の点ＱをηTkペアリング計算回路に出力し、ηTkペアリング計算回路が楕円曲線上の点Ｐ及び点Ｑに対してηTkペアリングの値を算出してべき乗演算回路に出力し、べき乗演算回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップとを含む。
【０１０１】
さらに小規模な回路構成にて２つのペアリングの演算を実施することができるようになる。
【０１０２】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１０３】
（付記１）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する第１の選択回路と、
前記楕円曲線上の点Ｐ及び前記第１の選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、
前記ηTペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、
前記ηTペアリング計算回路の出力と前記第２の回路の出力とのいずれかを出力する第２の選択回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記第１の選択回路に前記第１の回路の出力を前記ηTペアリング計算回路に出力させ且つ前記第２の選択回路に前記第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には前記第１の選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記第２の選択回路に前記ηTペアリング計算回路の出力を出力させる制御回路と、
を有するペアリング演算装置。
【０１０４】
（付記２）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する第１の選択回路と、
前記楕円曲線上の点Ｐ及び前記第１の選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、
前記ηTkペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、
前記ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路と、
前記第２の回路の出力と前記第３の回路の出力とのいずれかを出力する第２の選択回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記第１の選択回路に前記第１の回路の出力を前記ηTkペアリング計算回路に出力させ且つ前記第２の選択回路に前記第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には前記第１の選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記第２の選択回路に前記第３の回路の出力を出力させる制御回路と、
を有するペアリング演算装置。
【０１０５】
（付記３）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、
前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、
前記ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記選択回路に前記第１の回路の出力を前記ηTkペアリング計算回路に出力させ且つ前記べき乗演算回路に前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施させ、ηTペアリングの計算結果を出力する場合には前記選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記べき乗演算回路に１／ｋ乗演算を実施させる制御回路と、
を有するペアリング演算装置。
【０１０６】
（付記４）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、前記ηTペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTペアリング計算回路に出力し、前記ηTペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTペアリングの値を算出して前記第２の回路に出力し、前記第２の回路が前記ηTペアリング計算回路の出力の前記有限体における３ＭＴ2／Ｌ乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTペアリング計算回路に出力し、前記ηTペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTペアリングの値を算出して出力するステップと、
を含むペアリング演算方法。
【０１０７】
（付記５）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、前記ηTkペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、前記ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTkペアリングの値を算出して前記第２の回路に出力し、前記第２の回路が前記ηTkペアリング計算回路の出力の前記有限体における３ＭＴ2／Ｌｋ乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTkペアリングの値を算出して前記第３の回路に出力し、前記第３の回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップと、
を含むペアリング演算方法。
【０１０８】
（付記６）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、前記ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTkペアリングの値を算出して前記べき乗演算回路に出力し、前記べき乗演算回路が前記ηTkペアリング計算回路の出力の前記有限体における３ＭＴ2／（Ｌｋ）乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTkペアリングの値を算出して前記べき乗演算回路に出力し、前記べき乗演算回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップと、
を含むペアリング演算方法。
【符号の説明】
【０１０９】
１０１，２０１，３０１ ψ-1（Ｑ）演算部
１０２，１０６，２０２，２０６，３０２，３０６ セレクタ
１０３ ηTペアリング計算部
２０３，３０３ ηTkペアリング計算部
１０４，２０４，３０４ 制御部
１０７，２０７，３０７ レジスタ
２０８ ｛１／ｋ｝乗演算部
３０８ ｓ乗演算部 ３０９，３１０ レジスタ
【技術分野】
【０００１】
本技術は、有限体における楕円曲線上のペアリング演算技術に関する。
【背景技術】
【０００２】
情報通信技術で広く用いられる技術の１つとして、暗号化のための鍵を公開する公開鍵暗号の技術が知られている。公開鍵暗号とは、暗号化と復号化とで一対の異なる鍵を用いる暗号である。公開鍵暗号の技術は、鍵の管理が煩雑であることや特定のグループのみが解読可能となるブロードキャスト暗号が未整備であるといった問題がある。近年、これらの問題を解決する手法として、ペアリングを用いた暗号（以下、ペアリング暗号と呼ぶ）が注目されている。ペアリング暗号では、ＩＤを公開鍵とするＩＤベース暗号、ブロードキャスト暗号、アグリゲート（aggregate）署名などを実現できる。しかし、暗号技術として使用されているペアリングは複数あり、現在暗号で使用するペアリングの標準化は進んでいない。
【０００３】
ペアリング暗号では楕円曲線上のペアリングと呼ばれる演算を使用する。まず、楕円曲線について説明する。ｐを素数、ｍを自然数とすると、要素数ｑ＝ｐmの有限体ＧＦ（ｑ）上の楕円曲線Ｅとは、
Ｅ：ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6
を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる点∞を加えた集合のことである。無限遠点∞を０と表すこともある。ここで、ａ1、ａ2、ａ3、ａ4、ａ6、ｘ及びｙは有限体ＧＦ（ｑ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式（すなわち、アファイン座標）で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現できない唯一の点である。このように、アファイン座標では無限遠点以外の点はＧＦ（ｑ）の２つの要素の組として表される。楕円曲線Ｅ上の点の間には点の加算と呼ばれる演算が可能であり、ＧＦ（ｑ）における加減乗除の組み合わせによって計算される。
【０００４】
ペアリングとは２入力１出力関数で、３つの群Ｇ1，Ｇ2，Ｇ3に対して、写像ｅ：Ｇ1×Ｇ2−＞Ｇ3で以下の性質を満たすものをいう。
（１）ｅ(au+bv，x) ＝ａ・ｅ(ｕ，ｘ) ＋ｂ・ｅ(ｖ，ｘ)
（２）ｅ(u，cx+dz) ＝ｃ・ｅ(ｕ，ｘ) ＋ｄ・ｅ(ｕ，ｚ)
【０００５】
暗号技術として使用されるペアリングの例として以下のものがある。
（ａ）Weilペアリング
（ｂ）Ｔａｔｅペアリング
（ｃ）ηTペアリング
（ｄ）Ateペアリング、Twisted Ateペアリングなど
【０００６】
ここで、ＴａｔｅペアリングとηTペアリングについて説明する。まず、楕円曲線上のＴａｔｅペアリングについて説明する。次の式で定義される有限体ＧＦ（３3）上の楕円曲線を考える。
Ｅ：ｙ2＝ｘ3−ｘ＋ｂ
（但し、ｂ＝−１又は１とする）
【０００７】
Ｔａｔｅペアリングは、楕円曲線Ｅ上の２点Ｐ，Ｑに関して、ある値を返す関数ｅ（Ｐ，Ｑ）である。また、ηTペアリングは、Ｔａｔｅペアリングをより高速計算可能に改良したペアリングである。
【０００８】
なお、ηTペアリングとＴａｔｅペアリングには、以下の式（１）のような関係がある。
(ηT(Ｐ，Ｑ)M)^{3T2}＝ｅ(Ｐ，ψ(Ｑ))L （１）
【０００９】
ここで、Ｍ、Ｔ、Ｌ及び写像ψは以下のように定義される。
Ｍ＝(36m−１)／(３m＋ｂ３{(m+1)/2}＋１)
Ｔ＝−ｂ３{(m+1)/2}−１
Ｌ＝−ｂ３{(m+3)/2}
ψ(x,y) ＝(ρ−ｘ，σｙ) (但し、σ，ρはσ2＝−１，ρ3＝ρ＋ｂを満たす元)
【００１０】
ＴａｔｅペアリングとηTペアリングの間に成り立つ式（１）を変形して、以下のような式に変形されることも知られている。
ｅ(Ｐ，ψ(Ｑ))＝(ηT（Ｐ，Ｑ）M)^{3T2/L} （２）
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００８−２０６５３号公報
【特許文献２】特開平７−２６１６６２号公報
【非特許文献】
【００１２】
【非特許文献１】岡本栄司、岡本健、金山直樹、「ペアリングに関する最近の研究動向」，Fundamentals Review, Vol. 1, No. 1，pp.51-60, 2007/07
【発明の概要】
【発明が解決しようとする課題】
【００１３】
従来、個別にペアリングのハードウエア化について検討が行われている。しかしながら、暗号技術として使用されているペアリングは複数あり、現在暗号で使用するペアリングの標準化が進んでいない。そのため、小規模の回路で複数のペアリング演算を実施することが望まれている。
【００１４】
従って、本技術の目的は、ＴａｔｅペアリングとηTペアリングとを小規模な回路で実現するための技術を提供することである。
【課題を解決するための手段】
【００１５】
第１の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する第１の選択回路と、（Ｃ）楕円曲線上の点Ｐ及び第１の選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、（Ｄ）ηTペアリング計算回路の出力に対して、有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTペアリング計算回路の出力と第２の回路の出力とのいずれかを出力する第２の選択回路と、（Ｆ）Ｔａｔｅペアリングの計算結果を出力する場合には第１の選択回路に第１の回路の出力をηTペアリング計算回路に出力させ且つ第２の選択回路に第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第１の選択回路に楕円曲線上の点Ｑを出力させ且つ第２の選択回路にηTペアリング計算回路の出力を出力させる制御回路とを有する。
【００１６】
第２の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する第１の選択回路と、（Ｃ）楕円曲線上の点Ｐ及び第１の選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路と、（Ｆ）第２の回路の出力と第３の回路の出力とのいずれかを出力する第２の選択回路と、（Ｇ）Ｔａｔｅペアリングの計算結果を出力する場合には第１の選択回路に第１の回路の出力をηTkペアリング計算回路に出力させ且つ第２の選択回路に第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第１の選択回路に楕円曲線上の点Ｑを出力させ且つ第２の選択回路に第３の回路の出力を出力させる制御回路とを有する。
【００１７】
第３の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路と、（Ｅ）Ｔａｔｅペアリングの計算結果を出力する場合には選択回路に第１の回路の出力をηTkペアリング計算回路に出力させ且つべき乗演算回路に有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施させ、ηTペアリングの計算結果を出力する場合には選択回路に楕円曲線上の点Ｑを出力させ且つべき乗演算回路に１／ｋ乗演算を実施させる制御回路とを有する。
【発明の効果】
【００１８】
ＴａｔｅペアリングとηTペアリングとを小規模な回路で実現できるようになる。
【図面の簡単な説明】
【００１９】
【図１】図１は、第１の実施の形態に係るペアリング演算装置の回路構成例を示す図である。
【図２】図２は、第１の実施の形態に係るηTペアリング計算部の回路構成例を示す図である。
【図３】図３は、第１の実施の形態においてＴａｔｅペアリング計算を実施する場合の処理フローを示す図である。
【図４】図４は、第１の実施の形態においてηTペアリング計算を実施する際の処理フローを示す図である。
【図５】図５は、第２の実施の形態に係るペアリング演算装置の回路構成例を示す図である。
【図６】図６は、第２の実施の形態に係るηTkペアリング計算部の回路構成例を示す図である。
【図７】図７は、第２の実施の形態においてＴａｔｅペアリング計算を実施する場合の処理フローを示す図である。
【図８】図８は、第２の実施の形態においてηTペアリング計算を実施する際の処理フローを示す図である。
【図９】図９は、第３の実施の形態に係るペアリング演算装置の回路構成例を示す図である。
【図１０】図１０は、第３の実施の形態においてＴａｔｅペアリング計算を実施する場合の処理フローを示す図である。
【図１１】図１１は、第３の実施の形態においてηTペアリング計算を実施する際の処理フローを示す図である。
【図１２】図１２は、実施の形態間の効果比較表を示す図である。
【図１３】図１３は、ＩＣカードの一例を示す図である。
【発明を実施するための形態】
【００２０】
［実施の形態１］
本技術の第１の実施の形態では、上で述べた式（２）に基づいた回路構成を採用する。なお、このような回路構成については公開されたものはない。
【００２１】
本実施の形態に係るペアリング演算装置１００の回路構成図を図１に示す。本ペアリング演算装置１００は、レジスタＱと、レジスタＰと、ψ-1（Ｑ）演算部１０１と、セレクタ１０２と、ηTペアリング計算部１０３と、｛３ＭＴ2／Ｌ｝乗演算部１０５と、セレクタ１０６と、レジスタ１０７と、制御部１０４とを有する。
【００２２】
レジスタＱは、有限体ＧＦ（３3）における楕円曲線Ｅ：ｙ2＝ｘ3−ｘ＋ｂ（但し、ｂ＝−１又は１とする）上の点Ｑ（ｘq，ｙq）の値を格納するレジスタであり、ψ-1（Ｑ）演算部１０１及びセレクタ１０２に接続されている。レジスタＰは、上で述べた楕円曲線上の点Ｐ（ｘp，ｙp）の値を格納するレジスタであり、ηTペアリング計算部１０３に接続されている。
【００２３】
ψ-1（Ｑ）演算部１０１は、点Ｑに対して、写像ψ(x,y) ＝(ρ−ｘ，σｙ) (但し、σ，ρはσ2＝−１，ρ3＝ρ＋ｂを満たす元)の逆写像ψ-1（Ｑ）を計算する回路であり、セレクタ１０２に接続されている。なお、ψ-1（Ｑ）＝（ρ-ｘq，σ-1ｙq）となる。
【００２４】
セレクタ１０２には、ψ-1（Ｑ）演算部１０１からの出力とレジスタＱからの値とが入力されており、セレクタ１０２は、選択信号の値に応じていずれかをηTペアリング計算部１０３に出力する。本実施の形態では、選択信号「０」が入力された場合にはレジスタＱからの値を出力し、選択信号「１」が入力された場合にはψ-1（Ｑ）演算部１０１からの出力を出力する。
【００２５】
ηTペアリング計算部１０３は、レジスタＰからの出力とセレクタ１０２からの出力とを用いて、ηTペアリング計算を実施する回路であり、｛３ＭＴ2／Ｌ｝乗演算部１０５とセレクタ１０６とに接続されている。ηTペアリング計算部１０３により実施される演算は、例えば以下のような演算である。なお、Ｐ＝（ｘp，ｙp）及びＱ＝（ｘq，ｙq）を処理する場合を示している。
【００２６】
【数１】
【００２７】
｛３ＭＴ2／Ｌ｝乗演算部１０５は、ηTペアリング計算部１０３の出力を、上で述べた有限体において｛３ＭＴ2／Ｌ｝乗する演算を行う回路であり、セレクタ１０６に接続されている。ここで、Ｍ、Ｔ及びＬは以下のように定義される。
Ｍ＝(36m−１)／(３m＋ｂ３{(m+1)/2}＋１)
Ｔ＝−ｂ３{(m+1)/2}−１
Ｌ＝−ｂ３{(m+3)/2}
【００２８】
これらの値については外部からｍ及びｂの値が与えられてレジスタなどに保持しておき、実際の演算時に算出するようにしてもよいし、最終的なＭ、Ｔ及びＬの値をｍ及びｂから事前に演算した後にレジスタなどに保持しておくようにしてもよい。
【００２９】
なお、有限体におけるべき乗演算については、よく知られたいずれの方法でも良い。
【００３０】
セレクタ１０６には、｛３ＭＴ2／Ｌ｝乗演算部１０５からの出力とηTペアリング計算部１０３からの出力とが入力されており、セレクタ１０６は、選択信号「０」が入力された場合にはηTペアリング計算部１０３からの出力を出力し、選択信号「１」が入力された場合には｛３ＭＴ2／Ｌ｝乗演算部１０５からの出力を出力する。セレクタ１０６の出力は、レジスタ１０７に接続されている。レジスタ１０７には、Ｔａｔｅペアリングの値ｅ（Ｐ，Ｑ）又はηTペアリングの値ηT（Ｐ，Ｑ）が格納される。
【００３１】
制御部１０４は、セレクタ１０２及び１０６に接続されており、外部からηTペアリングの値の算出を指示された場合には、選択信号「０」を出力し、外部からＴａｔｅペアリングの値の算出を指示された場合には、選択信号「１」を出力する。
【００３２】
ηTペアリング計算部１０３の構成例を図２に示す。ηTペアリング計算部１０３は、セレクタ１０２からの出力を格納するレジスタｘ1及びｙ1と、レジスタＰに格納されている点Ｐの値を格納するレジスタｘ2及びｙ2と、有限体上の加算及び乗算を行う加算・乗算回路１０３１と、有限体上の三乗演算を行う３乗計算回路１０３２と、有限体上の１／３乗計算を行う１／３乗計算回路１０３３と、出力値を格納するレジスタｆとを有する。加算・乗算回路１０３１と３乗計算回路１０３２と１／３乗計算回路１０３３とは、上で述べたアルゴリズムを実施する際に用いられる。
【００３３】
次に、図１のペアリング演算装置１００の動作を図３及び図４を用いて説明する。まず、Ｔａｔｅペアリングの計算を指示された場合の処理を図３を用いて説明する。この場合、制御部１０４は、選択信号「１」をセレクタ１０２及び１０６に出力する（ステップＳ１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTペアリング計算部１０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部１０１及びセレクタ１０２に入力する（ステップＳ３）。
【００３４】
そして、ψ-1（Ｑ）演算部１０１は、楕円曲線上の点Ｑに対してψ-1（Ｑ）を計算し、セレクタ１０２に出力する（ステップＳ５）。セレクタ１０２では、制御部１０４から選択信号「１」が入力されているので、ψ-1（Ｑ）演算部１０１の出力をηTペアリング計算部１０３に出力する。
【００３５】
ηTペアリング計算部１０３は、セレクタ１０２からの出力ψ-1（Ｑ）とレジスタＰからの値とから、ｚ＝ηT(Ｐ，ψ-1)を計算し、セレクタ１０６及び｛３ＭＴ2／Ｌ｝乗演算部１０５に出力する（ステップＳ７）。
【００３６】
｛３ＭＴ2／Ｌ｝乗演算部１０５は、ηTペアリング計算部１０３からの出力ｚの｛３ＭＴ2／Ｌ｝乗演算を実施して、演算結果をセレクタ１０６に出力する（ステップＳ９）。
【００３７】
セレクタ１０６は、選択信号「１」が入力されているので、｛３ＭＴ2／Ｌ｝乗演算部１０５の出力ｅ（Ｐ，Ｑ）＝ｚ^｛３ＭＴ2／Ｌ｝を出力し、レジスタ１０７に格納する（ステップＳ１１）。
【００３８】
一方、ηTペアリングの計算を指示された場合の処理を図４を用いて説明する。この場合、制御部１０４は、選択信号「０」をセレクタ１０２及び１０６に出力する（ステップＳ２１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTペアリング計算部１０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部１０１及びセレクタ１０２に入力する（ステップＳ２３）。セレクタ１０２は、選択信号「０」に応じて、レジスタＱからの出力値（点Ｑの値）をそのままηTペアリング計算部１０３に出力する。
【００３９】
そして、ηTペアリング計算部１０３は、セレクタ１０２からの出力である点Ｑの値とレジスタＰからの出力値（点Ｐの値）とから、ｚ＝ηT(Ｐ，Ｑ)を計算し、セレクタ１０６及び｛３ＭＴ2／Ｌ｝乗演算部１０５に出力する（ステップＳ２５）。
【００４０】
セレクタ１０６は、選択信号「０」に応じて、ηTペアリング計算部１０３からの出力ηT（Ｐ，Ｑ）をηTペアリングの値として出力し、レジスタ１０７に格納する（ステップＳ２７）。
【００４１】
以上のように、ηTペアリング計算部１０３をηTペアリングの計算及びＴａｔｅペアリングの計算で共用するので、回路規模を小さくしつつ、２つのペアリングに対処できるようなペアリング演算装置１００が得られる。
【００４２】
［実施の形態２］
図２に示したように、第１の実施の形態におけるηTペアリング計算部１０３は、１／３乗計算回路１０３３を含むため、処理時間がかかるという問題がある。そこで、ηTペアリングのｋ（＝３（ｍ＋１）／２）乗であるηTkペアリング計算を実施することによって、１／３乗演算を除去する。なお、余分にｋ乗しているので、１／ｋ乗演算を追加すると共に｛３ＭＴ2／Ｌ｝乗を｛３ＭＴ2／（Ｌｋ）｝乗に変更する。ηTペアリング計算の中で１／３乗演算を行うよりも１／ｋ乗演算を実施する方が高速に演算できるので、全体としても演算の高速化が可能となる。
【００４３】
図５に、本実施の形態に係るペアリング演算装置２００の回路構成を示す。本ペアリング演算装置２００は、レジスタＱと、レジスタＰと、ψ-1（Ｑ）演算部２０１と、セレクタ２０２と、ηTkペアリング計算部２０３と、｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５と、セレクタ２０６と、レジスタ２０７と、制御部２０４と、｛１／ｋ｝乗演算部２０８とを有する。
【００４４】
レジスタＱは、有限体ＧＦ（３3）における楕円曲線Ｅ：ｙ2＝ｘ3−ｘ＋ｂ（但し、ｂ＝−１又は１とする）上の点Ｑ（ｘq，ｙq）の値を格納するレジスタであり、ψ-1（Ｑ）演算部２０１及びセレクタ２０２に接続されている。レジスタＰは、上で述べた楕円曲線上の点Ｐ（ｘp，ｙp）の値を格納するレジスタであり、ηTkペアリング計算部２０３に接続されている。
【００４５】
ψ-1（Ｑ）演算部２０１は、点Ｑに対して、写像ψ(x,y) ＝(ρ−ｘ，σｙ) (但し、σ，ρはσ2＝−１，ρ3＝ρ＋ｂを満たす元)の逆写像ψ-1（Ｑ）を計算する回路であり、セレクタ２０２に接続されている。なお、ψ-1（Ｑ）＝（ρ-ｘq，σ-1ｙq）となる。
【００４６】
セレクタ２０２には、ψ-1（Ｑ）演算部２０１からの出力とレジスタＱからの値とが入力されており、セレクタ２０２は、選択信号の値に応じていずれかをηTkペアリング計算部２０３に出力する。本実施の形態では、選択信号「０」が入力された場合にはレジスタＱからの値を出力し、選択信号「１」が入力された場合にはψ-1（Ｑ）演算部２０１からの出力を出力する。
【００４７】
ηTkペアリング計算部２０３は、レジスタＰからの出力とセレクタ２０２からの出力とを用いて、ηTkペアリング計算を実施する回路であり、｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５と｛１／ｋ｝乗演算部２０８とに接続されている。ηTkペアリング計算部２０３により実施される演算は、例えば以下のような演算である。なお、Ｐ＝（ｘp，ｙp）及びＱ＝（ｘq，ｙq）を処理する場合を示している。
【００４８】
【数２】
【００４９】
｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５は、ηTkペアリング計算部２０３の出力を、上で述べた有限体において｛３ＭＴ2／（Ｌｋ）｝乗する演算を行う回路であり、セレクタ２０６に接続されている。Ｍ、Ｔ及びＬは第１の実施の形態と同じである。ｋも、上で述べたように、ｋ＝３（ｍ＋１）／２である。
【００５０】
これらの値については外部からｍ及びｂの値が与えられてレジスタなどに保持しておき、実際の演算時に算出するようにしてもよいし、最終的なＭ、Ｔ及びＬの値をｍ及びｂから事前に演算した後にレジスタなどに保持しておくようにしてもよい。
【００５１】
また、｛１／ｋ｝乗演算部２０８は、ηTkペアリング計算部２０３の出力を、上で述べた有限体において｛１／ｋ｝乗する演算を行う回路であり、セレクタ２０６に接続されている。１／ｋについても、ｍ又はｋをレジスタに保持しておくようにしておき演算時に１／ｋを算出するようにしても良いし、最終的な値｛１／ｋ｝を事前に算出後にレジスタなどに保持しておくようにしても良い。
【００５２】
有限体におけるべき乗演算については、第１の実施の形態と同じように、よく知られた方法で実施可能である。
【００５３】
セレクタ２０６には、｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５からの出力と｛１／ｋ｝乗演算部２０８からの出力とが入力されており、セレクタ２０６は、選択信号「０」が入力された場合には｛１／ｋ｝乗演算部２０８からの出力を出力し、選択信号「１」が入力された場合には｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５からの出力をレジスタ２０７に出力する。セレクタ２０６の出力は、レジスタ２０７に接続されている。レジスタ２０７には、Ｔａｔｅペアリングの値ｅ（Ｐ，Ｑ）又はηTペアリングの値ηT（Ｐ，Ｑ）が格納される。
【００５４】
制御部２０４は、セレクタ２０２及び２０６に接続されており、外部からηTペアリングの値の算出を指示された場合には、選択信号「０」を出力し、外部からＴａｔｅペアリングの値の算出を指示された場合には、選択信号「１」を出力する。
【００５５】
ηTkペアリング計算部２０３の構成例を図６に示す。ηTkペアリング計算部２０３は、セレクタ２０２からの出力値を格納するレジスタｘ1及びｙ1と、レジスタＰに格納されている点Ｐの値を格納するレジスタｘ2及びｙ2と、有限体上の加算及び乗算を行う加算・乗算回路２０３１と、有限体上の三乗演算を行う３乗計算回路２０３２と、出力値を格納するレジスタｆとを有する。加算・乗算回路２０３１と３乗計算回路２０３２とは、上で述べたアルゴリズムを実施する際に用いられる。この図からも分かるように、ηTkペアリング計算部２０３には、１／３乗計算回路１０３３は含まれておらず、その分処理速度も速くなる。
【００５６】
次に、図５のペアリング演算装置２００の動作を図７及び図８を用いて説明する。まず、Ｔａｔｅペアリングの計算を指示された場合の処理を図７を用いて説明する。この場合、制御部２０４は、選択信号「１」をセレクタ２０２及び２０６に出力する（ステップＳ３１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTkペアリング計算部２０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部２０１及びセレクタ２０２に入力する（ステップＳ３３）。
【００５７】
そして、ψ-1（Ｑ）演算部２０１は、楕円曲線上の点Ｑに対してψ-1（Ｑ）を計算し、セレクタ２０２に出力する（ステップＳ３５）。セレクタ２０２では、制御部２０４から選択信号「１」が入力されているので、ψ-1（Ｑ）演算部２０１の出力をηTkペアリング計算部２０３に出力する。
【００５８】
ηTkペアリング計算部２０３は、セレクタ２０２からの出力ψ-1（Ｑ）とレジスタＰからの値とから、ｚ＝ηT(Ｐ，ψ-1)kを計算し、｛１／ｋ｝乗演算部２０８及び｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５に出力する（ステップＳ３７）。
【００５９】
｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５は、ηTkペアリング計算部２０３からの出力ｚの｛３ＭＴ2／（Ｌｋ）｝乗演算を実施して、セレクタ２０６に出力する（ステップＳ３９）。
【００６０】
セレクタ２０６は、選択信号「１」が入力されているので、｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５の出力ｅ（Ｐ，Ｑ）＝ｚ^｛３ＭＴ2／（Ｌｋ）｝を出力し、レジスタ２０７に格納する（ステップＳ４１）。
【００６１】
一方、ηTペアリングの計算を指示された場合の処理を図８を用いて説明する。この場合、制御部２０４は、選択信号「０」をセレクタ２０２及び２０６に出力する（ステップＳ５１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTkペアリング計算部２０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部２０１及びセレクタ２０２に入力する（ステップＳ５３）。セレクタ２０２は、選択信号「０」に応じて、レジスタＱからの出力値（点Ｑの値）をそのままηTkペアリング計算部２０３に出力する。
【００６２】
そして、ηTkペアリング計算部２０３は、セレクタ２０２からの出力である点Ｑの値とレジスタＰからの出力値（点Ｐの値）とから、ｚ＝ηT(Ｐ，Ｑ)kを計算し、｛１／ｋ｝乗演算部２０８及び｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５に出力する（ステップＳ５５）。
【００６３】
｛１／ｋ｝乗演算部２０８は、ηTkペアリング計算部２０３から入力されたｚ＝ηT(Ｐ，Ｑ)kの１／ｋ乗であるｚ1/kを計算して、セレクタ２０６に出力する（ステップＳ５７）。
【００６４】
セレクタ２０６は、選択信号「０」に応じて、｛１／ｋ｝乗演算部２０８からの出力ηT（Ｐ，Ｑ）（＝ｚ1/k）をηTペアリングの値として出力し、レジスタ１０７に格納する（ステップＳ５９）。
【００６５】
以上のように、ηTkペアリング計算部２０３をηTペアリング計算部１０３の代わりに導入することによって、全体の処理が高速化される。なお、図２と図６との比較からして、回路規模については第１の実施の形態とほぼ同じになっている。
【００６６】
［実施の形態３］
第２の実施の形態では、ηTkペアリング計算部２０３を導入する代わりに、｛１／ｋ｝乗演算部２０８を導入している。しかし、べき乗演算は、そもそも｛３ＭＴ2／Ｌ｝乗演算部１０５が設けられていた。そこで、｛１／ｋ｝乗演算部２０８及び｛３ＭＴ2／（Ｌｋ）｝乗演算部２０５とを統合してｓ乗演算部を導入してｓの値を切り替えることによって、回路の共通化により全体の回路規模を小さくする。
【００６７】
図９に、本実施の形態に係るペアリング演算装置３００の回路構成を示す。本ペアリング演算装置３００は、レジスタＱと、レジスタＰと、ψ-1（Ｑ）演算部３０１と、セレクタ３０２と、ηTkペアリング計算部３０３と、ｓ乗演算部３０８と、セレクタ３０６と、最終結果を格納するレジスタ３０７と、制御部３０４と、｛１／ｋ｝の値を格納するレジスタ３０９と、｛３ＭＴ2／（Ｌｋ）｝の値を格納するレジスタ３１０とを有する。
【００６８】
レジスタＱは、有限体ＧＦ（３3）における楕円曲線Ｅ：ｙ2＝ｘ3−ｘ＋ｂ（但し、ｂ＝−１又は１とする）上の点Ｑ（ｘq，ｙq）の値を格納するレジスタであり、ψ-1（Ｑ）演算部３０１及びセレクタ３０２に接続されている。レジスタＰは、上で述べた楕円曲線上の点Ｐ（ｘp，ｙp）の値を格納するレジスタであり、ηTkペアリング計算部３０３に接続されている。
【００６９】
ψ-1（Ｑ）演算部３０１は、点Ｑに対して、写像ψ(x,y) ＝(ρ−ｘ，σｙ) (但し、σ，ρはσ2＝−１，ρ3＝ρ＋ｂを満たす元)の逆写像ψ-1（Ｑ）を計算する回路であり、セレクタ３０２に接続されている。なお、ψ-1（Ｑ）＝（ρ-ｘq，σ-1ｙq）となる。
【００７０】
セレクタ３０２には、ψ-1（Ｑ）演算部３０１からの出力とレジスタＱからの値とが入力されており、セレクタ３０２は、選択信号の値に応じていずれかをηTkペアリング計算部３０３に出力する。本実施の形態でも、選択信号「０」が入力された場合にはレジスタＱからの値を出力し、選択信号「１」が入力された場合にはψ-1（Ｑ）演算部３０１からの出力を出力する。
【００７１】
ηTkペアリング計算部３０３は、レジスタＰからの出力とセレクタ３０２からの出力とを用いて、ηTkペアリング計算を実施する回路であり、ｓ乗演算部３０８に接続されている。ηTkペアリング計算部３０３により実施される演算は、第２の実施の形態で示したものと同じである。
【００７２】
レジスタ３０９とレジスタ３１０とはセレクタ３０６に接続されており、セレクタ３０６の出力はｓ乗演算部３０８に接続されている。セレクタ３０６は、選択信号の値に応じていずれかをｓ乗演算部３０８に出力する。本実施の形態では、選択信号「０」が入力された場合にはレジスタ３０９からの値をｓ乗演算部３０８に出力し、選択信号「１」が入力された場合にはレジスタ３１０からの値をｓ乗演算部３０８に出力する。
【００７３】
ｓ乗演算部３０８は、ηTkペアリング計算部３０３の出力ｚを、有限体においてｓ（ｓはセレクタ３０６の出力値）乗する演算を実施する回路であり、レジスタ３０７に接続されている。ｓ乗演算部３０８は、演算結果をレジスタ３０７に格納する。なお、有限体におけるべき乗演算については、よく知られた演算であるからここでは詳しく述べない。
【００７４】
制御部３０４は、セレクタ３０２及び３０６に接続されており、外部からηTペアリングの値の算出を指示された場合には、選択信号「０」を出力し、外部からＴａｔｅペアリングの値の算出を指示された場合には、選択信号「１」を出力する。
【００７５】
次に、図１０及び図１１を用いてペアリング演算装置３００の動作を説明する。
【００７６】
まず、Ｔａｔｅペアリングの計算を指示された場合の処理を図１０を用いて説明する。この場合、制御部３０４は、選択信号「１」をセレクタ３０２及び３０６に出力する（ステップＳ６１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTkペアリング計算部３０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部３０１及びセレクタ３０２に入力する（ステップＳ６３）。
【００７７】
そして、ψ-1（Ｑ）演算部３０１は、楕円曲線上の点Ｑに対してψ-1（Ｑ）を計算し、セレクタ３０２に出力する（ステップＳ６５）。セレクタ３０２では、制御部３０４から選択信号「１」が入力されているので、ψ-1（Ｑ）演算部３０１の出力をηTkペアリング計算部３０３に出力する。
【００７８】
ηTkペアリング計算部２０３は、セレクタ３０２からの出力ψ-1（Ｑ）とレジスタＰからの値とから、ｚ＝ηT(Ｐ，ψ-1)kを計算し、ｓ乗演算部３０８に出力する（ステップＳ６７）。
【００７９】
また、セレクタ３０６は、制御部３０４からの選択信号「１」に応じて、レジスタ３１０からの値｛３ＭＴ2／（Ｌｋ）｝をｓ乗演算部３０８に出力する。
【００８０】
ｓ乗演算部３０８は、ηTkペアリング計算部２０３からの出力ｚに対して、セレクタ３０６からのｓ＝｛３ＭＴ2／（Ｌｋ）｝に応じてｓ乗演算を実施して、ｚ＾｛３ＭＴ2／（Ｌｋ）｝を算出する（ステップＳ６９）。そして、ｓ乗演算部３０８は、演算結果ｚ＾｛３ＭＴ2／（Ｌｋ）｝を、Ｔａｔｅペアリングの結果ｅ（Ｐ，Ｑ）＝ｚ^｛３ＭＴ2／（Ｌｋ）｝として、レジスタ３０７に出力して格納する（ステップＳ７１）。
【００８１】
一方、ηTペアリングの計算を指示された場合の処理を図１１を用いて説明する。この場合、制御部３０４は、選択信号「０」をセレクタ３０２及び３０６に出力する（ステップＳ８１）。また、上で述べた楕円曲線上の点Ｐの値を、レジスタＰからηTkペアリング計算部３０３に入力し、点Ｑの値をレジスタＱからψ-1（Ｑ）演算部３０１及びセレクタ３０２に入力する（ステップＳ８３）。セレクタ３０２は、選択信号「０」に応じて、レジスタＱからの出力値（点Ｑの値）をそのままηTkペアリング計算部３０３に出力する。
【００８２】
そして、ηTkペアリング計算部３０３は、セレクタ３０２からの出力である点Ｑの値とレジスタＰからの出力値（点Ｐからの値）とから、ｚ＝ηT(Ｐ，Ｑ)kを計算し、ｓ乗演算部３０８に出力する（ステップＳ８５）。
【００８３】
また、セレクタ３０６は、制御部３０４からの選択信号「０」に応じて、レジスタ３０９からの値｛１／ｋ｝をｓ乗演算部３０８に出力する。
【００８４】
ｓ乗演算部３０８は、ηTkペアリング計算部３０３からの出力ｚに対して、セレクタ３０６からのｓ＝｛１／ｋ｝に応じてｓ乗演算を実施して、ｚ＾｛１／ｋ｝を算出する（ステップＳ８７）。そして、ｓ乗演算部３０８は、演算結果ｚ＾｛１／ｋ｝を、ηTペアリングの値としてレジスタ３０７に出力して格納する（ステップＳ８９）。
【００８５】
以上のように、べき乗演算を共通の回路で実施することによって小さな回路規模で２つのペアリングの演算が可能となる。
【００８６】
図１２に３つの実施の形態の処理速度及び回路規模の比較表を示す。なお、図１２は、第１の実施の形態を基準とした比較表を表している。これを見ると、第２の実施の形態は、第１の実施の形態ではＴａｔｅペアリング計算時には１５％程度の処理の高速化が可能となっている。また、第３の実施の形態は、さらに回路規模も第１の実施の形態に比して１５％程度削減できる。なお、第１の実施の形態は、ηTペアリング計算部１０３を共用しているので、従来に比してその分回路規模は削減できている。
【００８７】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、ペアリング演算装置は、例えば図１３に示すようなＩＣカードに含まれる半導体チップ上に実装される場合もあれば、パーソナルコンピュータやサーバその他のコンピュータに実装される場合もある。ＩＣカードのような小型の装置に実装する場合には、上で述べたような回路規模の削減が大きく寄与する。
【００８８】
べき乗算、ηTペアリング計算やηTkペアリング計算については、さらに高速なアルゴリズムが存在する場合には、それらを採用することも可能である。
【００８９】
以上述べた本実施の形態をまとめると、以下のようになる。
【００９０】
第１の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する第１の選択回路と、（Ｃ）楕円曲線上の点Ｐ及び第１の選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、（Ｄ）ηTペアリング計算回路の出力に対して、有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTペアリング計算回路の出力と第２の回路の出力とのいずれかを出力する第２の選択回路と、（Ｆ）Ｔａｔｅペアリングの計算結果を出力する場合には第１の選択回路に第１の回路の出力をηTペアリング計算回路に出力させ且つ第２の選択回路に第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第１の選択回路に楕円曲線上の点Ｑを出力させ且つ第２の選択回路にηTペアリング計算回路の出力を出力させる制御回路とを有する。
【００９１】
このような回路を採用することによって、ηTペアリング計算回路を共用することによって、ηTペアリングとＴａｔｅペアリングのいずれもに対応するペアリング演算装置の回路規模を削減することができるようになる。
【００９２】
第２の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する第１の選択回路と、（Ｃ）楕円曲線上の点Ｐ及び第１の選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路と、（Ｆ）第２の回路の出力と第３の回路の出力とのいずれかを出力する第２の選択回路と、（Ｇ）Ｔａｔｅペアリングの計算結果を出力する場合には第１の選択回路に第１の回路の出力をηTkペアリング計算回路に出力させ且つ第２の選択回路に第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には第１の選択回路に楕円曲線上の点Ｑを出力させ且つ第２の選択回路に第３の回路の出力を出力させる制御回路とを有する。
【００９３】
ηTkペアリング計算回路を導入することによって、処理高速化を阻害する１／３乗演算を除去して、処理速度を向上させることができるようになる。
【００９４】
第３の態様に係るペアリング演算装置は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路と、（Ｅ）Ｔａｔｅペアリングの計算結果を出力する場合には選択回路に第１の回路の出力をηTkペアリング計算回路に出力させ且つべき乗演算回路に有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施させ、ηTペアリングの計算結果を出力する場合には選択回路に楕円曲線上の点Ｑを出力させ且つべき乗演算回路に１／ｋ乗演算を実施させる制御回路とを有する。
【００９５】
さらに、べき乗演算回路を導入することによって、さらに回路の共用が可能となり、回路規模を削減することができる。
【００９６】
また、第４の態様に係るペアリング演算方法は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、（Ｄ）ηTペアリング計算回路の出力に対して、有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路とを有するペアリング演算装置により実行される。そして、本ペアリング演算方法は、（α）Ｔａｔｅペアリングの値を算出する場合には、第１の回路が前記楕円曲線上の点Ｑから逆写像ψ-1（Ｑ）を算出し、選択回路が第１の回路の出力をηTペアリング計算回路に出力し、ηTペアリング計算回路が第１の回路の出力及び楕円曲線上の点Ｐに対してηTペアリングの値を算出して第２の回路に出力し、第２の回路がηTペアリング計算回路の出力の有限体における３ＭＴ2／Ｌ乗演算を実施して出力するステップと、（β）ηTペアリングの値を算出する場合には、選択回路が楕円曲線上の点ＱをηTペアリング計算回路に出力し、ηTペアリング計算回路が楕円曲線上の点Ｐ及び点Ｑに対して前記ηTペアリングの値を算出して出力するステップとを含む。
【００９７】
小規模な回路構成にて２つのペアリングの演算が可能となる。
【００９８】
また、第５の態様に係るペアリング演算方法は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、（Ｅ）ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路とを有するペアリング演算装置により実行される。そして、本ペアリング演算方法は、（α）Ｔａｔｅペアリングの値を算出する場合には、第１の回路が楕円曲線上の点Ｑから逆写像ψ-1（Ｑ）を算出し、選択回路が第１の回路の出力をηTkペアリング計算回路に出力し、ηTkペアリング計算回路が第１の回路の出力及び楕円曲線上の点Ｐに対してηTkペアリングの値を算出して第２の回路に出力し、第２の回路がηTkペアリング計算回路の出力の有限体における３ＭＴ2／Ｌｋ乗演算を実施して出力するステップと、（β）ηTペアリングの値を算出する場合には、選択回路が楕円曲線上の点ＱをηTkペアリング計算回路に出力し、ηTkペアリング計算回路が楕円曲線上の点Ｐ及び点Ｑに対してηTkペアリングの値を算出して第３の回路に出力し、第３の回路がηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップとを含む。
【００９９】
さらに処理速度も高速化することができるようになる。
【０１００】
さらに、第６の態様に係るペアリング演算方法は、（Ａ）有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、（Ｂ）楕円曲線上の点Ｑと第１の回路の出力とのいずれかを出力する選択回路と、（Ｃ）楕円曲線上の点Ｐ及び選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、（Ｄ）ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路とを有するペアリング演算装置により実行される。そして、ペアリング演算方法は、（α）Ｔａｔｅペアリングの値を算出する場合には、第１の回路が楕円曲線上の点Ｑから逆写像ψ-1（Ｑ）を算出し、選択回路が第１の回路の出力をηTkペアリング計算回路に出力し、ηTkペアリング計算回路が第１の回路の出力及び楕円曲線上の点Ｐに対してηTkペアリングの値を算出してべき乗演算回路に出力し、べき乗演算回路がηTkペアリング計算回路の出力の有限体における３ＭＴ2／（Ｌｋ）乗演算を実施して出力するステップと、（β）ηTペアリングの値を算出する場合には、選択回路が楕円曲線上の点ＱをηTkペアリング計算回路に出力し、ηTkペアリング計算回路が楕円曲線上の点Ｐ及び点Ｑに対してηTkペアリングの値を算出してべき乗演算回路に出力し、べき乗演算回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップとを含む。
【０１０１】
さらに小規模な回路構成にて２つのペアリングの演算を実施することができるようになる。
【０１０２】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１０３】
（付記１）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する第１の選択回路と、
前記楕円曲線上の点Ｐ及び前記第１の選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、
前記ηTペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、
前記ηTペアリング計算回路の出力と前記第２の回路の出力とのいずれかを出力する第２の選択回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記第１の選択回路に前記第１の回路の出力を前記ηTペアリング計算回路に出力させ且つ前記第２の選択回路に前記第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には前記第１の選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記第２の選択回路に前記ηTペアリング計算回路の出力を出力させる制御回路と、
を有するペアリング演算装置。
【０１０４】
（付記２）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する第１の選択回路と、
前記楕円曲線上の点Ｐ及び前記第１の選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、
前記ηTkペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、
前記ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路と、
前記第２の回路の出力と前記第３の回路の出力とのいずれかを出力する第２の選択回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記第１の選択回路に前記第１の回路の出力を前記ηTkペアリング計算回路に出力させ且つ前記第２の選択回路に前記第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には前記第１の選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記第２の選択回路に前記第３の回路の出力を出力させる制御回路と、
を有するペアリング演算装置。
【０１０５】
（付記３）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、
前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、
前記ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記選択回路に前記第１の回路の出力を前記ηTkペアリング計算回路に出力させ且つ前記べき乗演算回路に前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施させ、ηTペアリングの計算結果を出力する場合には前記選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記べき乗演算回路に１／ｋ乗演算を実施させる制御回路と、
を有するペアリング演算装置。
【０１０６】
（付記４）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、前記ηTペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTペアリング計算回路に出力し、前記ηTペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTペアリングの値を算出して前記第２の回路に出力し、前記第２の回路が前記ηTペアリング計算回路の出力の前記有限体における３ＭＴ2／Ｌ乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTペアリング計算回路に出力し、前記ηTペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTペアリングの値を算出して出力するステップと、
を含むペアリング演算方法。
【０１０７】
（付記５）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、前記ηTkペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、前記ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTkペアリングの値を算出して前記第２の回路に出力し、前記第２の回路が前記ηTkペアリング計算回路の出力の前記有限体における３ＭＴ2／Ｌｋ乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTkペアリングの値を算出して前記第３の回路に出力し、前記第３の回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップと、
を含むペアリング演算方法。
【０１０８】
（付記６）
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、前記ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTkペアリングの値を算出して前記べき乗演算回路に出力し、前記べき乗演算回路が前記ηTkペアリング計算回路の出力の前記有限体における３ＭＴ2／（Ｌｋ）乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTkペアリングの値を算出して前記べき乗演算回路に出力し、前記べき乗演算回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップと、
を含むペアリング演算方法。
【符号の説明】
【０１０９】
１０１，２０１，３０１ ψ-1（Ｑ）演算部
１０２，１０６，２０２，２０６，３０２，３０６ セレクタ
１０３ ηTペアリング計算部
２０３，３０３ ηTkペアリング計算部
１０４，２０４，３０４ 制御部
１０７，２０７，３０７ レジスタ
２０８ ｛１／ｋ｝乗演算部
３０８ ｓ乗演算部 ３０９，３１０ レジスタ
【特許請求の範囲】
【請求項１】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する第１の選択回路と、
前記楕円曲線上の点Ｐ及び前記第１の選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、
前記ηTペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、
前記ηTペアリング計算回路の出力と前記第２の回路の出力とのいずれかを出力する第２の選択回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記第１の選択回路に前記第１の回路の出力を前記ηTペアリング計算回路に出力させ且つ前記第２の選択回路に前記第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には前記第１の選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記第２の選択回路に前記ηTペアリング計算回路の出力を出力させる制御回路と、
を有するペアリング演算装置。
【請求項２】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する第１の選択回路と、
前記楕円曲線上の点Ｐ及び前記第１の選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、
前記ηTkペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、
前記ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路と、
前記第２の回路の出力と前記第３の回路の出力とのいずれかを出力する第２の選択回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記第１の選択回路に前記第１の回路の出力を前記ηTkペアリング計算回路に出力させ且つ前記第２の選択回路に前記第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には前記第１の選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記第２の選択回路に前記第３の回路の出力を出力させる制御回路と、
を有するペアリング演算装置。
【請求項３】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、
前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、
前記ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記選択回路に前記第１の回路の出力を前記ηTkペアリング計算回路に出力させ且つ前記べき乗演算回路に前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施させ、ηTペアリングの計算結果を出力する場合には前記選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記べき乗演算回路に１／ｋ乗演算を実施させる制御回路と、
を有するペアリング演算装置。
【請求項４】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、前記ηTペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTペアリング計算回路に出力し、前記ηTペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTペアリングの値を算出して前記第２の回路に出力し、前記第２の回路が前記ηTペアリング計算回路の出力の前記有限体における３ＭＴ2／Ｌ乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTペアリング計算回路に出力し、前記ηTペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTペアリングの値を算出して出力するステップと、
を含むペアリング演算方法。
【請求項５】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、前記ηTkペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、前記ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTkペアリングの値を算出して前記第２の回路に出力し、前記第２の回路が前記ηTkペアリング計算回路の出力の前記有限体における３ＭＴ2／Ｌｋ乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTkペアリングの値を算出して前記第３の回路に出力し、前記第３の回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップと、
を含むペアリング演算方法。
【請求項６】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、前記ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTkペアリングの値を算出して前記べき乗演算回路に出力し、前記べき乗演算回路が前記ηTkペアリング計算回路の出力の前記有限体における３ＭＴ2／（Ｌｋ）乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTkペアリングの値を算出して前記べき乗演算回路に出力し、前記べき乗演算回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップと、
を含むペアリング演算方法。
【請求項１】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する第１の選択回路と、
前記楕円曲線上の点Ｐ及び前記第１の選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、
前記ηTペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、
前記ηTペアリング計算回路の出力と前記第２の回路の出力とのいずれかを出力する第２の選択回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記第１の選択回路に前記第１の回路の出力を前記ηTペアリング計算回路に出力させ且つ前記第２の選択回路に前記第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には前記第１の選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記第２の選択回路に前記ηTペアリング計算回路の出力を出力させる制御回路と、
を有するペアリング演算装置。
【請求項２】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する第１の選択回路と、
前記楕円曲線上の点Ｐ及び前記第１の選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、
前記ηTkペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、
前記ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路と、
前記第２の回路の出力と前記第３の回路の出力とのいずれかを出力する第２の選択回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記第１の選択回路に前記第１の回路の出力を前記ηTkペアリング計算回路に出力させ且つ前記第２の選択回路に前記第２の回路の出力を出力させ、ηTペアリングの計算結果を出力する場合には前記第１の選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記第２の選択回路に前記第３の回路の出力を出力させる制御回路と、
を有するペアリング演算装置。
【請求項３】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、
前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、
前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、
前記ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路と、
Ｔａｔｅペアリングの計算結果を出力する場合には前記選択回路に前記第１の回路の出力を前記ηTkペアリング計算回路に出力させ且つ前記べき乗演算回路に前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施させ、ηTペアリングの計算結果を出力する場合には前記選択回路に前記楕円曲線上の点Ｑを出力させ且つ前記べき乗演算回路に１／ｋ乗演算を実施させる制御回路と、
を有するペアリング演算装置。
【請求項４】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値を算出するηTペアリング計算回路と、前記ηTペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／Ｌ（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTペアリング計算回路に出力し、前記ηTペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTペアリングの値を算出して前記第２の回路に出力し、前記第２の回路が前記ηTペアリング計算回路の出力の前記有限体における３ＭＴ2／Ｌ乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTペアリング計算回路に出力し、前記ηTペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTペアリングの値を算出して出力するステップと、
を含むペアリング演算方法。
【請求項５】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、前記ηTkペアリング計算回路の出力に対して、前記有限体における３ＭＴ2／（Ｌｋ）（Ｍ＝（３6m−１）／（３m＋ｂ３{(m+1)/2}＋１），Ｔ＝−ｂ３{(m+1)/2}−１，Ｌ＝−ｂ３{(m+3)/2}）乗演算を実施する第２の回路と、前記ηTkペアリング計算回路の出力の１／ｋ乗を算出する第３の回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTkペアリングの値を算出して前記第２の回路に出力し、前記第２の回路が前記ηTkペアリング計算回路の出力の前記有限体における３ＭＴ2／Ｌｋ乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTkペアリングの値を算出して前記第３の回路に出力し、前記第３の回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップと、
を含むペアリング演算方法。
【請求項６】
有限体ＧＦ（３m）における楕円曲線ｙ2＝ｘ3−ｘ＋ｂ上の点Ｑから、所定の写像ψの逆写像ψ-1（Ｑ）を算出する第１の回路と、前記楕円曲線上の点Ｑと前記第１の回路の出力とのいずれかを出力する選択回路と、前記楕円曲線上の点Ｐ及び前記選択回路の出力に対して、ηTペアリングの値のｋ（ｋ＝３（ｍ＋１）／２）乗を算出するηTkペアリング計算回路と、前記ηTkペアリング計算回路の出力に対して、指定されたべき乗算を実施するべき乗演算回路とを有するペアリング演算装置により実行されるペアリング演算方法であって、
Ｔａｔｅペアリングの値を算出する場合には、前記第１の回路が前記楕円曲線上の点Ｑから前記逆写像ψ-1（Ｑ）を算出し、前記選択回路が前記第１の回路の出力を前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記第１の回路の出力及び前記楕円曲線上の点Ｐに対して前記ηTkペアリングの値を算出して前記べき乗演算回路に出力し、前記べき乗演算回路が前記ηTkペアリング計算回路の出力の前記有限体における３ＭＴ2／（Ｌｋ）乗演算を実施して出力するステップと、
ηTペアリングの値を算出する場合には、前記選択回路が前記楕円曲線上の点Ｑを前記ηTkペアリング計算回路に出力し、前記ηTkペアリング計算回路が前記楕円曲線上の点Ｐ及び点Ｑに対して前記ηTkペアリングの値を算出して前記べき乗演算回路に出力し、前記べき乗演算回路が前記ηTkペアリング計算回路の出力の１／ｋ乗を算出して出力するステップと、
を含むペアリング演算方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１１−１５００９６（Ｐ２０１１−１５００９６Ａ）
【公開日】平成２３年８月４日（２０１１．８．４）
【国際特許分類】
【出願番号】特願２０１０−１０５５９（Ｐ２０１０−１０５５９）
【出願日】平成２２年１月２１日（２０１０．１．２１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年８月４日（２０１１．８．４）
【国際特許分類】
【出願日】平成２２年１月２１日（２０１０．１．２１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]