(57)【特許請求の範囲】
【請求項１】
G1,G2,GTを素数位数qの群とし、gを群G1の生成元とし、hを群G2の生成元とし、xをqを法とする剰余環Zqの元とし、タイプIのペアリング演算はG1×G1→GTの双線形写像であり、タイプIIIのペアリング演算はG1×G2→GTの双線形写像であり、
少なくとも一つのタイプIのペアリング演算を含むプログラムを入力とし、上記プログラムの演算過程で用いられる群G1上の変数X=gxに対して群G2上で対応する変数X~=hxを生成する二重化部と、
上記プログラムに含まれる上記群G1上の変数を用いる群演算について、上記群G2上の変数を用いる群演算を生成する群演算変換部と、
上記プログラムに含まれる二つの上記群G1上の変数を入力とするタイプIのペアリング演算を、上記群G1上の変数及び上記群G2上の変数を入力とするタイプIIIのペアリング演算へ変換するペアリング演算変換部と、
上記プログラムに含まれる上記群G1上の変数と上記群G2上の変数との等価性検査を上記群G1上の変数及び群G2の生成元を入力とするタイプIIIのペアリング演算と上記群G2上の変数及び群G1の生成元を入力とするタイプIIIのペアリング演算とを用いた等式に変換する等価性検査変換部と、
を含むプログラム変換装置。
【請求項２】
請求項１に記載のプログラム変換装置であって、
上記二重化部は、
上記プログラムを入力とし、上記群G1上の変数をノードとして表し、上記プログラムに含まれるタイプIのペアリング演算をペアリングノードとして表し、上記プログラムに含まれる群演算について演算対象のノード同士を演算への入出力を表すエッジにより接続し、上記プログラムに含まれるタイプIのペアリング演算について演算対象の各ノードとペアリングノードとを上記エッジにより接続することで、上記プログラムの構造を表す方向性グラフに変換するグラフ構築部と、
上記ペアリングノードに接続するいずれかのエッジを選択し、上記選択したエッジに接続するノードを先頭ノードとして、上記先頭ノードへ上記エッジの連鎖により連なる一連のノードからなるサブグラフに基づいて、上記群G1上の変数を表すノードを複製して上記群G2上の変数を表すノードを生成し、上記サブグラフと等しい構造となるように上記群G2上の変数を表すノードを上記エッジにより接続することで、上記サブグラフを複製するサブグラフ複製部と、
上記選択したエッジを上記先頭ノードに対応する上記群G2上の変数を表すノードへ接続するエッジ切替部と、
上記方向性グラフ中に他のノードへの出力を表すエッジを持たないノードが存在すれば、当該ノードへ上記エッジの連鎖により連なる一連のノードからなるサブグラフを削除するサブグラフ削除部と、
を含むプログラム変換装置。
【請求項３】
請求項１または２に記載のプログラム変換装置であって、
gを群G1の生成元とし、hを群G2の生成元とし、Aを群G1の群要素とし、Bを群G2の群要素とし、eを上記タイプIIIのペアリング演算とし、
上記等価性検査変換部は、上記プログラムに含まれる等価性検査A=Bを次式に置き換えるものである
【数５】
0005980178.tif 000006
プログラム変換装置。
【請求項４】
二重化部と群演算変換部とペアリング演算変換部と等価性検査変換部とを含むプログラム変換装置が実行するプログラム変換方法であって、
G1,G2,GTを素数位数qの群とし、gを群G1の生成元とし、hを群G2の生成元とし、xをqを法とする剰余環Zqの元とし、タイプIのペアリング演算はG1×G1→GTの双線形写像であり、タイプIIIのペアリング演算はG1×G2→GTの双線形写像であり、
上記二重化部が、少なくとも一つのタイプIのペアリング演算を含むプログラムを入力とし、上記プログラムの演算過程で用いられる群G1上の変数X=gxに対して群G2上で対応する変数X~=hxを生成する二重化ステップと、
上記群演算変換部が、上記プログラムに含まれる上記群G1上の変数を用いる群演算について、上記群G2上の変数を用いる群演算を生成する群演算変換ステップと、
上記ペアリング演算変換部が、上記プログラムに含まれる二つの上記群G1上の変数を入力とするタイプIのペアリング演算を、上記群G1上の変数及び上記群G2上の変数を入力とするタイプIIIのペアリング演算へ変換するペアリング演算変換ステップと、
上記等価性検査変換部が、上記プログラムに含まれる上記群G1上の変数と上記群G2上の変数との等価性検査を上記群G1上の変数及び群G2の生成元を入力とするタイプIIIのペアリング演算と上記群G2上の変数及び群G1の生成元を入力とするタイプIIIのペアリング演算とを用いた等式に変換する等価性検査変換ステップと、
を含むプログラム変換方法。
【請求項５】
請求項４に記載のプログラム変換方法であって、
上記二重化部は、グラフ構築部とサブグラフ複製部とエッジ切替部とサブグラフ削除部とを含むものであり、
上記二重化ステップは、
上記グラフ構築部が、上記プログラムを入力とし、上記群G1上の変数をノードとして表し、上記プログラムに含まれるタイプIのペアリング演算をペアリングノードとして表し、上記プログラムに含まれる群演算について演算対象のノード同士を演算への入出力を表すエッジにより接続し、上記プログラムに含まれるタイプIのペアリング演算について演算対象の各ノードとペアリングノードとを上記エッジにより接続することで、上記プログラムの構造を表す方向性グラフに変換するグラフ構築ステップと、
上記サブグラフ複製部が、上記ペアリングノードに接続するいずれかのエッジを選択し、上記選択したエッジに接続するノードを先頭ノードとして、上記先頭ノードへ上記エッジの連鎖により連なる一連のノードからなるサブグラフに基づいて、上記群G1上の変数を表すノードを複製して上記群G2上の変数を表すノードを生成し、上記サブグラフと等しい構造となるように上記群G2上の変数を表すノードを上記エッジにより接続することで、上記サブグラフを複製するサブグラフ複製ステップと、
上記エッジ切替部が、上記選択したエッジを上記先頭ノードに対応する上記群G2上の変数を表すノードへ接続するエッジ切替ステップと、
上記サブグラフ削除部が、上記方向性グラフ中に他のノードへの出力を表すエッジを持たないノードが存在すれば、当該ノードへ上記エッジの連鎖により連なる一連のノードからなるサブグラフを削除するサブグラフ削除ステップと、
を含むプログラム変換方法。
【請求項６】
請求項４または５に記載のプログラム変換方法であって、
gを群G1の生成元とし、hを群G2の生成元とし、Aを群G1の群要素とし、Bを群G2の群要素とし、eを上記タイプIIIのペアリング演算とし、
上記等価性検査変換ステップは、上記プログラムに含まれる等価性検査A=Bを次式に置き換えるものである
【数６】
0005980178.tif 000007
プログラム変換方法。
【請求項７】
請求項１から３のいずれかに記載のプログラム変換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ある楕円曲線を利用するペアリング群上のプログラムを異なる楕円曲線を利用するペアリング群上のプログラムへ変換する技術に関する。
【背景技術】
【０００２】
近年、ペアリングと呼ばれる双線形写像を用いた様々な暗号プリミティブが提案されている。暗号分野で用いられる双線形写像は、ある種の楕円曲線上の二点に定義されるペアリング演算を行うための関数である。具体的には、G1,G2,GTを素数位数qの群とし、e:G1×G2→GTを効率的に計算可能であり、任意の生成元g∈G1、h∈G2及び任意のa,b∈Zqに対して、e(ga,hb)=e(g,h)ab、e(g,h)≠1となる性質を持つ写像である。このような群の集合λq=(G1,G2,GT)をペアリング群と呼ぶ。
【０００３】
このとき、定数Ai,Ci∈G1、Bi,Di∈G2、dij∈Zqおよび変数Yi∈G1,Xi∈G2からなる式(1)の等式を変数Xi,Yiに関するペアリング積の等式と呼ぶ。特に、変数が一方の群にのみ現れる場合を線形の式と呼び、それ以外の場合を非線形の式と呼ぶ。
【０００４】
【数１】
0005980178.tif 000002
【０００５】
G1=G2であるペアリング群をタイプIのペアリング群と呼ぶ。タイプIのペアリング群では、特にG1とG2とを区別せず、単にGと表記する。例えば、非特許文献１には、タイプIのペアリング群を用いるIDベース暗号方式が記載されている。
【０００６】
一方、G1≠G2であって、ランダムに選んだ非ゼロのa,b∈Zqに対して、ga∈G1からaの値を知らずにha∈G2を求めること、及び、hb∈G2からbの値を知らずにgb∈G1を求めることがどちらも困難であるとき、そのペアリング群をタイプIIIのペアリング群と呼ぶ。ここで、Zqはqを位数とする剰余環である。例えば、非特許文献２には、タイプIIIのペアリング群を用いるIDベース暗号方式及び署名方式が記載されている。
【０００７】
タイプIのペアリング群は、方式の表記が容易であり、群要素がどちらの群に属しているかを勘案する必要が無いという特徴を持つ。それ故、署名やゼロ知識証明、公開鍵暗号などの様々な暗号プリミティブを複数組み合わせる暗号プロトコルの構成に便利である。しかし、タイプIのペアリング群は特殊な楕円曲線を利用するため、安全性に劣る。実際、タイプIの群GTにおける離散対数問題の解法が進展している。
【０００８】
タイプIIIのペアリング群は群G1と群G2の間に効率的な写像がないため、群要素がどちらの群に属しているかを常に考慮しなければならない。そのため、方式の表記や設計に特別の配慮が必要である。しかし、タイプIIIのペアリング群はより一般的な構造であり、安全性に優れていると考えられている。そのため、同じ安全性パラメータの上ではタイプIのペアリング群よりもタイプIIIのペアリング群の方が群要素のビット表現を短くすることができるという特徴を持つ。
【０００９】
あるペアリング群上の暗号方式を異なるペアリング群上の暗号方式に変換する技術が提案されている。例えば、非特許文献３や非特許文献４には、合成数位数のペアリング群で構成された暗号方式を、素数位数のペアリング群で構成された暗号方式へ変換する方法が記載されている。しかしながら、タイプIのペアリング群上の暗号方式からタイプIIIのペアリング群上の暗号方式へ変換する方式は提案されていない。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Brent Waters, “Efficient Identity-Based Encryption Without Random Oracles”, Advances in Cryptology - EUROCRYPT 2005, Lecture Notes in Computer Science, vol. 3494, pp. 114-127, 2005.
【非特許文献２】Jie Chen, Hoon Wei Lim, San Ling, Huaxiong Wang, Hoeteck Wee, “Shorter IBE and Signatures via Asymmetric Pairings”, Pairing-Based Cryptography - Pairing 2012, Lecture Notes in Computer Science, vol. 7708, pp. 122-140, 2013.
【非特許文献３】Allison Lewko, “Tools for Simulating Features of Composite Order Bilinear Groups in the Prime Order Setting”, Advances in Cryptology - EUROCRYPT 2012, Vol. 7237, pp. 318-335, 2012.
【非特許文献４】David Mandell Freeman, “Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups”, Advances in Cryptology - EUROCRYPT 2010, Vol. 6110, pp. 44-61, 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
タイプIのペアリング群において設計、記述された方式（プリミティブやプロトコル）は、必ずしもタイプIIIのペアリング群で直接的には動作しない。
【００１２】
簡単な例として、タイプIのペアリング群上の方式Aを考える。方式Aは、群要素X∈G1に対してe(X,X)なるペアリング演算を含むとする。タイプIではG1=G2であるため、この演算は実行できる。しかし、方式AをタイプIIIのペアリング群を使って実装しようとすると、群要素X∈G1に対応するX~∈G2を求めることができないため、ペアリング演算e(X,X)に相当する演算を実行することができない。別の例として、タイプIのペアリング群上の方式Aが、群要素X,Yに対してe(X,Y)なるペアリング演算及びZ←X・Yなる群演算（ここでは・を群演算と考える）を含むとする。タイプIにおいてはこれらの演算はいずれも実行可能である。タイプIIIの場合、ペアリング演算e(X,Y)が計算できるためにはX∈G1、Y∈G2とすればよいが、そうすると群演算X・Yを計算することができなくなる。逆に、群演算X・Yが計算できるようにするには、XとYの両方をG1（またはG2）の群要素とすればよいが、そうするとペアリング演算e(X,Y)を計算できない。したがって、タイプIのペアリング群上の方式AをタイプIIIのペアリング群で直接実装することはできない。
【００１３】
上記は方式中の演算に関して説明しているが、方式の安全性証明中の演算においても同様のことが言える。例えば、ある方式の証明中にe(X,X)なるペアリング演算が行われている場合、その方式自体がe(X,X)なるペアリング演算を利用しておらずタイプIIIのペアリング群において動作可能であっても、安全性証明が成り立たないためタイプIIIにおける実装の安全性は保証されない。
【００１４】
この発明の目的は、タイプIのペアリング群上で動作して安全性が証明された方式をタイプIIIのペアリング群上で動作する方式へ変換することである。
【課題を解決するための手段】
【００１５】
上記の課題を解決するために、この発明のプログラム変換装置は、二重化部と群演算変換部とペアリング演算変換部と等価性検査変換部とを含む。この発明では、G1,G2,GTを素数位数qの群とし、gを群G1の生成元とし、hを群G2の生成元とし、xをqを法とする剰余環Zqの元とし、タイプIのペアリング演算はG1×G1→GTの双線形写像であり、タイプIIIのペアリング演算はG1×G2→GTの双線形写像である。二重化部は、少なくとも一つのタイプIのペアリング演算を含むプログラムを入力とし、プログラムの演算過程で用いられる群G1上の変数X=gxに対して群G2上で対応する変数X~=hxを生成する。群演算変換部は、プログラムに含まれる上記群G1上の変数を用いる群演算について、上記群G2上の変数を用いる群演算を生成する。ペアリング演算変換部は、プログラムに含まれる二つの群G1上の変数を入力とするタイプIのペアリング演算を、群G1上の変数及び群G2上の変数を入力とするタイプIIIのペアリング演算へ変換する。等価性検査変換部は、プログラムに含まれる群G1上の変数と群G2上の変数との等価性検査を群G1上の変数及び群G2の生成元を入力とするタイプIIIのペアリング演算と群G2上の変数及び群G1の生成元を入力とするタイプIIIのペアリング演算とを用いた等式に変換する。
【発明の効果】
【００１６】
この発明によれば、表記が簡易で設計に特段の注意を必要としないタイプIのペアリング群でアルゴリズムを記述し、それを効率の良いタイプIIIのペアリング群で実装することが可能になる。これにより、タイプIのペアリング群において、実装や記述を大きく変更することなく安全性を向上できる。
【図面の簡単な説明】
【００１７】
【図１】図１は、プログラム変換装置の機能構成を例示する図である。
【図２】図２は、プログラム変換方法の処理フローを例示する図である。
【図３】図３は、方向性グラフの状態を例示する図である。
【図４】図４は、方向性グラフの状態を例示する図である。
【図５】図５は、方向性グラフの状態を例示する図である。
【図６】図６は、方向性グラフの状態を例示する図である。
【図７】図７は、方向性グラフの状態を例示する図である。
【発明を実施するための形態】
【００１８】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１９】
［実施形態］
図１を参照して、実施形態に係るプログラム変換装置の機能構成の一例を説明する。実施形態に係るプログラム変換装置１は、二重化部１０、変換部２０、制御部１０１及びメモリ１０２を含む。二重化部１０は、グラフ構築部１２、サブグラフ複製部１４、エッジ切替部１６及びサブグラフ削除部１８を含む。変換部２０は、群演算変換部２２、ペアリング演算変換部２４及び等価性検査変換部２６を含む。プログラム変換装置１は、例えば、中央演算処理装置（Central Processing Unit、CPU）、主記憶装置（Random Access Memory、RAM）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。プログラム変換装置１は、例えば、制御部１０１の制御のもとで各処理を実行する。プログラム変換装置１に入力されたデータや各処理で得られたデータは、例えば、メモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２０】
図２を参照して、プログラム変換方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００２１】
プログラム変換装置１は、タイプIのペアリング群上で動作し安全性が証明された方式Aを実装したプログラムαを入力とし、タイプIIIのペアリング群上で動作し安全性が保証できる方式A’を実装したプログラムα’を出力する。
【００２２】
ある方式Aの安全性は帰着と呼ばれるアルゴリズムの集合が存在することによって示されているものとする。なお、方式A自体もアルゴリズムの集合である。方式Aとその帰着アルゴリズム（以下、これらのアルゴリズムを単にアルゴリズムAと呼ぶ）において、タイプIのペアリング群の群要素に関する演算は、群への所属検査、同一群の群要素同士の比較（以下、等価性検査と呼ぶこともある）、群演算及びペアリング演算に限るものとする。
【００２３】
ステップＳ１０において、二重化部１０は、入力されたタイプIのペアリング群上のプログラムαから方向性グラフTを生成し、方向性グラフTをタイプIIIで動作できるように変換した方向性グラフT’を出力する。方向性グラフT’は変換部２０へ入力される。以下、二重化部１０の処理をより詳細に説明する。
【００２４】
ステップＳ１２において、グラフ構築部１２は、タイプIのペアリング群上のプログラムαを入力とし、プログラムαに基づいて方向性グラフTを生成する。まず、グラフ構築部１２はアルゴリズムAの群演算全体を方向性グラフによって表現する。アルゴリズムAの記述において、入力、出力、途中結果として現れる各群要素には固有のラベルが与えられるものとする。このラベルを変数と呼ぶ。方向性グラフでは、アルゴリズムが扱うすべての変数がノードに割り当てられ、群演算が行われる変数が割り当てられたノードからその結果を格納する変数のノードにエッジを持つ。ペアリング演算については、固有のラベルを持つノード（以下、ペアリングノードと呼ぶ）により表される。ペアリングノードは、ペアリング演算へ入力される変数が割り当てられた二つのノードに向かうエッジを持つ。入力エッジを持たないノードを入力ノードと呼び、入力ノードに割り当てられた変数を入力変数と呼ぶ。ディジタル署名方式を例に考えると、典型的には、入力ノードには署名対象のメッセージ及び帰着の対象となる困難性問題のインスタンスが割り当てられる。こうしてプログラムαから生成された方向性グラフをTで表す。方向性グラフTはいくつかの分離したグラフで構成されている場合もある。
【００２５】
図３に方向性グラフTの一例を示す。図３の例では、ノードは実線の円で描かれ、ペアリングノードは一点鎖線の円で描かれている。群演算を表すエッジは実線の矢印であり、矢印の方向は演算対象のノードから演算結果のノードへ向かう。ペアリング演算を表すエッジは一点鎖線の矢印であり、矢印の方向はペアリングノードから演算対象のノードへ向かう。図３に示すように、方向性グラフTに表されたアルゴリズムAには、X3←X1・X2なる群演算、X4←X2・X3なる群演算、X6←X2・X5なる群演算、X8←X6・X7なる群演算、X3←Y1・Y2なる群演算及びe(X4,X8)なるペアリング演算が含まれている。方向性グラフTにおいて、入力ノードは、ノードX1,X2,X5,X7,Y1,Y2である。
【００２６】
方向性グラフTに含まれるノードXに対して、「Xのサブグラフ」とはノードXに到達するパスを持つすべてのノード（ただし、ペアリングノードを除く）とそのエッジからなるグラフを指す。図３の例では、「X8のサブグラフ」は点線で囲った部分、すなわちノードX2,X5,X6,X7,X8と各ノードを接続するエッジから構成されるグラフである。
【００２７】
ノードXのサブグラフは群演算の連鎖によるノードXの生成を意味するので、サブグラフに含まれる変数はタイプIIIにおいて同一の群に所属する必要がある。一方、タイプIIIのペアリング演算は異なる群に所属する変数に対して行うため、同じサブグラフに含まれる二つのノードがペアリングノードを介して接続されている場合、そのアルゴリズムはタイプIIIでは動作しない。図３の例では、ノードX2は、ペアリングノードPX4,X8に繋がるノードX4のサブグラフ及びノードX8のサブグラフいずれにも含まれるため、この方向性グラフTに表されたアルゴリズムAはタイプIIIのペアリング群上では動作しないことがわかる。
【００２８】
ステップＳ１４において、サブグラフ複製部１４は、ペアリングノードに接続されるエッジのいずれかを選択し、そのエッジに繋がるノードのサブグラフを複製する。すなわち、アルゴリズムAがペアリング演算e(X,Y)を計算するとき、X,Yいずれかのノードを選び（以下では、Xが選択されたものとする）、選ばれたノードXのサブグラフを複製する。複製したサブグラフに含まれるノードには異なる変数名を与える。例えば、複製したノードには元の変数名に「~」（チルダ）を付けた記号を変数名として与える。先行する上記の処理によって既にチルダ付きの変数名が付いたノードを持つグラフが存在している場合、そのグラフとマージする。このように複製したノードを複製ノードと呼ぶ。以降の説明では、群G1に属するノードをノードXと表し、ノードXに対応する複製ノードを複製ノードX~と表す場合がある。
【００２９】
図４にサブグラフ複製部１４がサブグラフを複製した後の方向性グラフTの一例を示す。図４の例では、複製ノードは破線の円で描かれている。この例ではペアリングノードPX4,X8の二つのエッジのうちノードX8に繋がるエッジを選択し、ノードX8のサブグラフを複製している。具体的には、ノードX2,X5,X6,X7,X8を複製して複製ノードX~2,X~5,X~6,X~7,X~8を生成している。
【００３０】
ステップＳ１６において、エッジ切替部１６は、ペアリングノードからノードXに向かっていたエッジを複製ノードX~につなぎ替える。図５にエッジ切替部１６がペアリングノードのエッジを切り替えた後の方向性グラフTの一例を示す。この例ではペアリングノードPX4,X8の二つのエッジのうちノードX8に繋がっていたエッジを複製ノードX~8へつなぎ替えている。
【００３１】
ステップＳ１８において、サブグラフ削除部１８は、他のグラフと連結していないサブグラフが発生しているかどうかを確認し、そのサブグラフ全体を削除する。図６にサブグラフ削除部１８が削除すべきサブグラフを特定したときの方向性グラフTの一例を示す。この例では、ペアリングノードPX4,X8のエッジが切り離されたノードX8のサブグラフに含まれるノードのうち他のノードへ入力されることがなくなったノードX5,X6,X7,X8を削除すべきサブグラフとして選択している。こうして選択したサブグラフを削除した状態の方向性グラフTの一例を図７に示す。
【００３２】
二重化部１０は、ステップＳ１４からステップＳ１８の処理を、方向性グラフTに含まれるすべてのペアリングノードに対して行う。結果として得られたグラフ全体を方向性グラフT’として出力する。
【００３３】
ステップＳ１４において方向性グラフTに含まれるペアリングノードのうちどのペアリングノードから処理を行うか、及び、ステップＳ１６においてペアリングノードに繋がる二つのエッジのうちどちらのエッジを選択するかについては、いくつかの方法が考えられる。最終的に得られる方向性グラフT’が小さくなるように選択を行えば、変換された後のアルゴリズムA’の効率が良くなるため望ましいが、この発明ではどのような基準で選択しても構わない。
【００３４】
ステップＳ２０において、変換部２０は、入力された方向性グラフT’に基づいて、プログラムαに含まれるタイプIのペアリング群上の各演算をタイプIIIのペアリング群上の演算に変換し、タイプIIIのペアリング群上のプログラムα’を出力する。以下、変換部２０の処理をより詳細に説明する。
【００３５】
ステップＳ２２において、群演算変換部２２は、入力された方向性グラフT’に基づいて、プログラムαに含まれるノードXに対するタイプIのペアリング群上の群演算について、対応する複製ノードX~に対するタイプIIIのペアリング群上の群演算を生成する。図７の例に群演算変換部２２の処理を適用すると、X~6←X~2・X~5なる群演算、X~8←X~6・X~7なる群演算を生成することになる。
【００３６】
ステップＳ２４において、ペアリング演算変換部２４は、入力された方向性グラフT’に基づいて、プログラムαに含まれるノードXを入力とするタイプIのペアリング演算について、ノードX及びノードX~を入力とするタイプIIIのペアリング演算に変換する。図７の例にペアリング演算変換部２４の処理を適用すると、e(X4,X8)なるペアリング演算をe(X4,X~8)なるペアリング演算に変換することになる。
【００３７】
ステップＳ２６において、等価性検査変換部２６は、ノードXと複製ノードX~との等価性検査を、ノードX及び複製ノードX~を入力とするタイプIIIのペアリング演算を用いた等式に変換する。具体的には、gを群G1の生成元、hを群G2の生成元、Aを群G1の要素、Bを群G2の要素として、A=Bの等価性検査は以下の式(2)に置き換えればよい。
【００３８】
【数２】
0005980178.tif 000003
【００３９】
a,b∈Zqとして、Aはgaと表すことができ、Bはhbと表すことができる。したがって、式(2)は以下の式(3)のように表すことができる。
【００４０】
【数３】
0005980178.tif 000004
【００４１】
式(3)はペアリング演算の性質から式(4)のように変形できる。
【００４２】
【数４】
0005980178.tif 000005
【００４３】
したがって、等価性検査変換部２６は、異なる群G1,G2に属する群要素A∈G1とB∈G2との比較を、同じ剰余環Zqに属する値a,b∈Zqの比較に変換していると言える。
【００４４】
このようにして、この発明のプログラム変換技術は、タイプIのペアリング群上のプログラムαを、タイプIIIのペアリング群上のプログラムα’へ変換する。タイプIのペアリング群はベースとなる群が一つしかないため記述が簡易でアルゴリズムの設計に格段の注意を必要としないが、特殊な群のため安全性に劣る場合がある。一方、タイプIIIのペアリング群はベースとなる群が二つあるため記述がやや複雑でアルゴリズムの設計には注意を要するが、より一般的な群のため安全性は良いとされている。
【００４５】
ただし、タイプIのペアリング群のために設計されたアルゴリズムは、タイプIIIのペアリング群においては、入力の群要素を二つある群にどのように振り分けたとしても動作しない場合があることには注意を要する。この発明の目的は、タイプIのペアリング群のために設計されたアルゴリズムをタイプIIIのペアリング群で動作するように群要素と演算を追加する手段を提供することにある。この発明の提供すべき場面は、そのアルゴリズムに要求される安全性などの特性を鑑みて決定すればよい。
【００４６】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４７】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５２】
１  プログラム変換装置
１０  二重化部
１２  グラフ構築部
１４  サブグラフ複製部
１６  エッジ切替部
１８  サブグラフ削除部
２０  変換部
２２  群演算変換部
２４  ペアリング演算変換部
２６  等価性検査変換部
１０１  制御部
１０２  メモリ
【図１】
0005980178.tif 000008
【図２】
0005980178.tif 000009
【図３】
0005980178.tif 000010
【図４】
0005980178.tif 000011
【図５】
0005980178.tif 000012
【図６】
0005980178.tif 000013
【図７】
0005980178.tif 000014