"プロトコルIDであるPIDを所定のビット列とし、H101→G、H201→Zpをハッシュ関数とし、Fを予め定められた関数として、GGTをそれぞれ双線形写像eG×G→GTを計算可能なggTを生成元とする群とし、Gの単位元を1Gとし、S01Gとし、マスタ公開鍵P0gQ0P0s0∈Gとし、IDに対応する情報共有装置の秘密情報をst1∈Zpとし、その情報共有装置の長期秘密鍵をとし、その情報共有装置の下位の情報共有装置であってID’に対応する情報共有装置の長期秘密鍵をとし、PtH1とし、StSt1Ptst1QtP0stとすることにより定まる、IDAに対応する情報共有装置UAの長期秘密鍵を、IDBに対応する情報共有装置UBの長期秘密鍵をとして、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、x1H2及びx2H2を計算するハッシュ値計算部と、PBiH1として短期公開鍵epkIDBを計算する短期公開鍵生成部と、上記短期公開鍵epkIDBを情報共有装置UBに送信する送信部と、短期公開鍵epkIDAを上記情報共有装置UBから受信する受信部と、第一共有秘密情報σ1ex1を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’ex2を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2eΠi2αeを計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’eΠi2αeを計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3x1を計算する第五秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成部と、y1H2及びy2H2を計算するハッシュ値計算部と、PAiH1として短期公開鍵epkIDAを計算する短期公開鍵生成部と、上記短期公開鍵epkIDAを上記情報共有装置UAに送信する送信部と、短期公開鍵epkIDBを上記情報共有装置UAから受信する受信部と、第一共有秘密情報σ1eΠi2βeを計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’eΠi2βeを計算する第二共有秘密情報計算部と、第三共有秘密情報σ2ey1を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’ey2を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3y1を計算する第五秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む情報共有システム。請求項1の情報共有システムにおいて、所定の正の整数をセキュリティパラメータkとして、上記関数Fは、ハッシュ関数H01→01である、情報共有システム。プロトコルIDであるPIDを所定のビット列とし、H101→G、H201→Zpをハッシュ関数とし、Fを予め定められた関数として、GGTをそれぞれ双線形写像eG×G→GTを計算可能なggTを生成元とする群とし、Gの単位元を1Gとし、S01Gとし、マスタ公開鍵P0gQ0P0s0∈Gとし、IDに対応する情報共有装置の秘密情報をst1∈Zpとし、その情報共有装置の長期秘密鍵をとし、その情報共有装置の下位の情報共有装置であってID’に対応する情報共有装置の長期秘密鍵をとし、PtH1とし、StSt1Ptst1QtP0stとすることにより定まる、IDAに対応する情報共有装置UAの長期秘密鍵を、IDBに対応する情報共有装置UBの長期秘密鍵をとして、情報共有装置UAの短期秘密鍵生成部が、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UAのハッシュ値計算部が、x1H2及びx2H2を計算するハッシュ値計算ステップと、情報共有装置UAの短期公開鍵生成部が、PBiH1として短期公開鍵epkIDBを計算する短期公開鍵生成ステップと、情報共有装置UAの送信部が、上記短期公開鍵epkIDBを情報共有装置UBに送信する送信ステップと、情報共有装置UBの短期秘密鍵生成部が、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成ステップと、情報共有装置UBのハッシュ値計算部が、y1H2及びy2H2を計算するハッシュ値計算ステップと、情報共有装置UBの短期公開鍵生成部が、PAiH1として短期公開鍵epkIDAを計算する短期公開鍵生成ステップと、情報共有装置UBの送信部が、上記短期公開鍵epkIDAを上記情報共有装置UAに送信する送信ステップと、情報共有装置UBの受信部が、短期公開鍵epkIDBを上記情報共有装置UAから受信する受信ステップと、情報共有装置UBの第一共有秘密情報計算部が、第一共有秘密情報σ1eΠi2βeを計算する第一共有秘密情報計算ステップと、情報共有装置UBの第二共有秘密情報計算部が、第二共有秘密情報σ1’eΠi2βeを計算する第二共有秘密情報計算ステップと、情報共有装置UBの第三共有秘密情報計算部が、第三共有秘密情報σ2ey1を計算する第三共有秘密情報計算ステップと、情報共有装置UBの第四共有秘密情報計算部が、第四共有秘密情報σ2’ey2を計算する第四共有秘密情報計算ステップと、情報共有装置UBの第五共有秘密情報計算部が、第五秘密情報計算部σ3y1を計算する第五秘密情報計算ステップと、情報共有装置UBの共有情報生成部が、Fを計算する共有情報生成ステップと、情報共有装置UAの受信部が、短期公開鍵epkIDAを上記情報共有装置UBから受信する受信ステップと、情報共有装置UAの第一共有秘密情報計算部が、第一共有秘密情報σ1ex1を計算する第一共有秘密情報計算ステップと、情報共有装置UAの第二共有秘密情報計算部が、第二共有秘密情報σ1’ex2を計算する第二共有秘密情報計算ステップと、情報共有装置UAの第三共有秘密情報計算部が、第三共有秘密情報σ2eΠi2αeを計算する第三共有秘密情報計算ステップと、情報共有装置UAの第四共有秘密情報計算部が、第四共有秘密情報σ2’eΠi2αeを計算する第四共有秘密情報計算ステップと、情報共有装置UAの第五共有秘密情報計算部が、第五秘密情報計算部σ3x1を計算する第五秘密情報計算ステップと、情報共有装置UAの共有情報生成部が、Fを計算する共有情報生成ステップと、を含む情報共有方法。プロトコルIDであるPIDを所定のビット列とし、H101→G、H201→Zpをハッシュ関数とし、Fを予め定められた関数として、GGTをそれぞれ双線形写像eG×G→GTを計算可能なggTを生成元とする群とし、Gの単位元を1Gとし、S01Gとし、マスタ公開鍵P0gQ0P0s0∈Gとし、IDに対応する情報共有装置の秘密情報をst1∈Zpとし、その情報共有装置の長期秘密鍵をとし、その情報共有装置の下位の情報共有装置であってID’に対応する情報共有装置の長期秘密鍵をとし、PtH1とし、StSt1Ptst1QtP0stとすることにより定まる、IDAに対応する情報共有装置UAの長期秘密鍵を、IDBに対応する情報共有装置UBの長期秘密鍵をとして、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、x1H2及びx2H2を計算するハッシュ値計算部と、PBiH1として短期公開鍵epkIDBを計算する短期公開鍵生成部と、上記短期公開鍵epkIDBを情報共有装置UBに送信する送信部と、短期公開鍵epkIDAを上記情報共有装置UBから受信する受信部と、第一共有秘密情報σ1ex1を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’ex2を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2eΠi2αeを計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’eΠi2αeを計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3x1を計算する第五秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAである情報共有装置。プロトコルIDであるPIDを所定のビット列とし、H101→G、H201→Zpをハッシュ関数とし、Fを予め定められた関数として、GGTをそれぞれ双線形写像eG×G→GTを計算可能なggTを生成元とする群とし、Gの単位元を1Gとし、S01Gとし、マスタ公開鍵P0gQ0P0s0∈Gとし、IDに対応する情報共有装置の秘密情報をst1∈Zpとし、その情報共有装置の長期秘密鍵をとし、その情報共有装置の下位の情報共有装置であってID’に対応する情報共有装置の長期秘密鍵をとし、PtH1とし、StSt1Ptst1QtP0stとすることにより定まる、IDAに対応する情報共有装置UAの長期秘密鍵を、IDBに対応する情報共有装置UBの長期秘密鍵をとして、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成部と、y1H2及びy2H2を計算するハッシュ値計算部と、PAiH1として短期公開鍵epkIDAを計算する短期公開鍵生成部と、上記短期公開鍵epkIDAを上記情報共有装置UAに送信する送信部と、短期公開鍵epkIDBを上記情報共有装置UAから受信する受信部と、第一共有秘密情報σ1eΠi2βeを計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’eΠi2βeを計算する第二共有秘密情報計算部と、第三共有秘密情報σ2ey1を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’ey2を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3y1を計算する第五秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBである情報共有装置。請求項4又は5の情報共有装置の各部としてコンピュータを機能させるためのプログラム。背景技術に記載した技術では、安全性を保証するためにいわゆるギャップ問題の難しさを仮定する必要がある。ギャップ問題とは、探索問題を解くために判定オラクルの利用を許した問題のことであり、一般にいわゆる探索問題よりも解きやすい問題となる。よって、ギャップ問題の難しさを仮定するよりも、探索問題の難しさを仮定した方が仮定を弱めることができるので望ましい。この発明の課題は、探索問題の難しさを仮定することにより安全性が保証される情報共有システム、方法、装置及びプログラムを提供することである。この発明の一態様による情報共有システムは、プロトコルIDであるPIDを所定のビット列とし、H101→G、H201→Zpをハッシュ関数とし、Fを予め定められた関数として、GGTをそれぞれ双線形写像eG×G→GTを計算可能なggTを生成元とする群とし、Gの単位元を1Gとし、S01Gとし、マスタ公開鍵P0gQ0P0s0∈Gとし、IDに対応する情報共有装置の秘密情報をst1∈Zpとし、その情報共有装置の長期秘密鍵をとし、その情報共有装置の下位の情報共有装置であってID’に対応する情報共有装置の長期秘密鍵をとし、PtH1とし、StSt1Ptst1QtP0stとすることにより定まる、IDAに対応する情報共有装置UAの長期秘密鍵を、IDBに対応する情報共有装置UBの長期秘密鍵をとして、短期秘密鍵x1x2∈Zpを生成する短期秘密鍵生成部と、x1H2及びx2H2を計算するハッシュ値計算部と、PBiH1として短期公開鍵epkIDBを計算する短期公開鍵生成部と、短期公開鍵epkIDBを情報共有装置UBに送信する送信部と、短期公開鍵epkIDAを情報共有装置UBから受信する受信部と、第一共有秘密情報σ1ex1を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’ex2を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2eΠi2αeを計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’eΠi2αeを計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3x1を計算する第五秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UAと、短期秘密鍵y1y2∈Zpを生成する短期秘密鍵生成部と、y1H2及びy2H2を計算するハッシュ値計算部と、PAiH1として短期公開鍵epkIDAを計算する短期公開鍵生成部と、短期公開鍵epkIDAを情報共有装置UAに送信する送信部と、短期公開鍵epkIDBを情報共有装置UAから受信する受信部と、第一共有秘密情報σ1eΠi2βeを計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’eΠi2βeを計算する第二共有秘密情報計算部と、第三共有秘密情報σ2ey1を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’ey2を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3y1を計算する第五秘密情報計算部と、Fを計算する共有情報生成部と、を含む情報共有装置UBと、を含む。探索問題の難しさを仮定することにより安全性を保証することができる。以下、図面を参照してこの発明の一実施形態を説明する。[アルゴリズム]まず、この発明のアルゴリズムの例について説明する。<公開パラメータ>PIDをプロトコルIDとし、プロトコル仕様に対応した固有のIDとする。すなわち、PIDはプロトコル仕様に応じた所定のビット列である。セキュリティパラメータをkとする。kは、所定の正の整数である。pをkビット素数とし、GGTをそれぞれ双線形写像eG×G→GTを効率的に計算可能なggTを生成元とする群とする。H101→G、H201→Zp、H01→01kをハッシュ関数とする。<鍵生成>鍵生成アルゴリズムは、一様ランダムにマスタ秘密鍵s0∈Zpを選び、S01Gを設定する。1GはGの単位元である。鍵生成アルゴリズムは、マスタ公開鍵P0g及びQ0P0s0を計算して公開する。ここで、P0の右肩のs0はs0を意味する。このように、ある文字の上付きの文字及び数字の一部がその上付きの中で更に上付き又は下付きである場合がある点に留意する。同様に、ある文字の下付きの文字及び数字の一部がその下付きの中で更に上付き又は下付きである場合がある点に留意する。<鍵抽出>IDに対応するユーザ装置は初期化として、st1∈Zpを一様ランダムに選び、秘密の状態情報として保持する。同様にして他のユーザのそれぞれも、秘密の状態情報としてZpの元を一様ランダムに選択して保持する。IDに対応するユーザは鍵抽出者として自分の長期秘密鍵を用いて、そのユーザの下位のユーザであってID’に対応するユーザ向けに次のように長期秘密鍵を生成する。ここで、PtH1、StSt1Ptst1、QtP0stである。<鍵交換>以下では、ユーザUAを鍵交換セッションのイニシエータとし、ユーザUBをレスポンダとする。ユーザUAはIDAに対応する長期秘密鍵を持ち、ユーザUBはIDBに対応する長期秘密鍵を持つとする。1.ユーザUAはランダムに短期秘密鍵x1x2∈UZpを選ぶ。このとき、ユーザUAは、x1H2及びx2H2を計算し、短期公開鍵epkIDBを計算する。ただし、PBiH1である。ユーザUAは、epkIDBをユーザUBに送る。2.ユーザUBはランダムに短期秘密鍵y1y2∈Zpを選ぶ。このとき、ユーザUBは、y1H2及びy2H2を計算し、短期公開鍵epkIDAを計算する。ただし、PAiH1である。ユーザUBは、epkIDAをユーザUAに送る。ユーザUBは、共有秘密情報σ1σ2σ3をそれぞれ次のように計算する。σ1eΠi2βeσ1’eΠi2βeσ2ey1σ2’ey2σ3y1その後、ユーザUBは、セッション鍵KHを計算して出力し、セッションを終了する。3.ユーザUAは、共有秘密情報σ1,σ1’,σ2,σ2’,σ3をそれぞれ次のように計算する。σ1ex1σ1’ex2σ2eΠi2αeσ2’eΠi2αeσ3x1その後、ユーザUAは、セッション鍵KHを計算して出力し、セッションを終了する。共有秘密情報には次の関係があるため、ユーザUAが計算した共有秘密情報σ1σ1’σ2σ2’σ3はそれぞれユーザUBが計算した共有秘密情報σ1σ1’σ2σ2’σ3と一致する。σ1ex1Πi2βeΠi1βex1si1Πi2βex1si1ex1es0x1σ1’ex2Πi2βeΠi1βex2si1Πi2βex2si1ex2es0x2σ2ey1Πi2αeΠi1αey1si1Πi2αey1si1ey1es0y1σ2’ey2Πi2αeΠi1αey2si1Πi2αey2si1ey2es0y2σ3y1x1P0x1y1このようにして、同一の共有情報であるセッション鍵Kが共有される。[実施形態]次に、上記[アルゴリズム]の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図1に例示するように、情報共有装置UA及び情報共有装置UBから構成される。情報共有装置UAが[アルゴリズム]の欄で説明したユーザUAに対応し、情報共有装置UBが[アルゴリズム]の欄で説明したユーザUBに対応する。情報共有装置UAは図4に例示した処理を行い、情報共有装置UBは図5に例示した処理を行う。情報共有の前に、[アルゴリズム]の<鍵抽出>の欄で説明した方法により、マスタ秘密鍵s0及びマスタ公開鍵P0g及びQ0P0s0等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部10及び記憶部20に記憶されているものとする。また、情報共有の前に、情報共有装置UA及び情報共有装置UBには、[アルゴリズム]の<鍵抽出>の欄で説明した方法により、ID及び秘密の状態情報及び長期秘密鍵が予め定められ、必要に応じて記憶部10及び記憶部20に記憶されているものとする。これらの記憶部10及び20に記憶されたデータは、適宜読み出されて下記に説明する計算が行われる。情報共有装置UAのIDを、IDAとする。αは正の整数である。このように、IDAはα個のIDAの断片IDA1...IDAαから構成される。[アルゴリズム]の<鍵抽出>の欄で説明した方法により定められた情報共有装置UAの長期秘密鍵をとする。情報共有装置UBのIDを、IDBとする。βは正の整数である。このように、IDBはβ個のIDBの断片IDB1...IDBβから構成される。[アルゴリズム]の<鍵抽出>の欄で説明した方法により定められた情報共有装置UBの長期秘密鍵をとする。情報共有装置UA及び情報共有装置UBによる自分より下位の情報共有装置ユーザに対する鍵の抽出、すなわち長期秘密鍵の生成は、それぞれ図2,3の鍵抽出部112,212により行われる。情報共有装置UAは、図2に示すように、記憶部10、短期秘密鍵生成部11、ハッシュ値計算部12、短期公開鍵生成部13、送信部14、受信部15、第一共有秘密情報生成部16、第二共有秘密情報生成部17、第三共有秘密情報生成部18、第四共有秘密情報生成部19、第五共有秘密情報生成部110、共有情報生成部111、鍵抽出部112を例えば含む。情報共有装置UBは、図3に示すように、記憶部20、短期秘密鍵生成部21、ハッシュ値計算部22、短期公開鍵生成部23、送信部24、受信部25、第一共有秘密情報生成部26、第二共有秘密情報生成部27、第三共有秘密情報生成部28、第四共有秘密情報生成部29、第五共有秘密情報生成部210、共有情報生成部211、鍵抽出部212を例えば含む。情報共有装置UAの短期秘密鍵生成部11図2は、短期秘密鍵x1x2∈Zpを生成するステップA1。例えば、Zpの中から一様ランダムに2つの元を選びそれぞれ短期秘密鍵y1y2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵x1x2は、ハッシュ値計算部12に送信される。情報共有装置UAのハッシュ値計算部12は、短期秘密鍵x1x2及び長期秘密鍵の中のSAαを用いて、ハッシュ値x1H2及びx2H2を計算するステップA2。ハッシュ値x1は、短期公開鍵生成部13、第一共有秘密情報生成部16、第五共有秘密情報生成部110に送信される。ハッシュ値x2は、短期公開鍵生成部13、第二共有秘密情報生成部17に送信される。情報共有装置UAの短期公開鍵生成部13は、短期公開鍵epkIDBを計算するステップA3。ここで、PBiH1とする。計算された短期公開鍵epkIDBは、送信部14に送信される。情報共有装置UAの送信部14は、短期公開鍵epkIDBを情報共有装置UAに送信するステップA4。情報共有装置UBの短期秘密鍵生成部21図3は、短期秘密鍵y1y2∈Zpを生成するステップB1。例えば、Zpの中から一様ランダムに2つの元を選びそれぞれ短期秘密鍵y1y2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵y1y2は、ハッシュ値計算部22に送信される。情報共有装置UBのハッシュ値計算部22は、短期秘密鍵y1y2及び長期秘密鍵の中のSBβを用いて、ハッシュ値y1H2及びy2H2を計算するステップB2。ハッシュ値y1は、短期公開鍵生成部23、第三共有秘密情報生成部28、第五共有秘密情報生成部210に送信される。ハッシュ値y2は、短期公開鍵生成部23、第四共有秘密情報生成部29に送信される。情報共有装置UBの短期公開鍵生成部23は、短期公開鍵epkIDAを計算するステップB3。ここで、PAiH1とする。計算された短期公開鍵epkIDAは、送信部24に送信される。情報共有装置UBの送信部24は、短期公開鍵epkIDAを情報共有装置UBに送信するステップB4。情報共有装置UBの受信部25は、短期公開鍵epkIDBを情報共有装置UAから受信するステップB5。情報共有装置UBの第一共有秘密情報生成部26は、第一共有秘密情報σ1eΠi2βeを計算するステップB6。計算された第一共有秘密情報σ1は、共有情報生成部211に送信される。情報共有装置UBの第二共有秘密情報生成部27は、第二共有秘密情報σ1’eΠi2βeを計算するステップB7。計算された第二共有秘密情報σ1’は、共有情報生成部211に送信される。情報共有装置UBの第三共有秘密情報生成部28は、第三共有秘密情報σ2ey1を計算するステップB8。計算された第三共有秘密情報σ2は、共有情報生成部211に送信される。情報共有装置UBの第四共有秘密情報生成部29は、第四共有秘密情報σ2’ey2を計算するステップB9。計算された第四共有秘密情報σ2’は、共有情報生成部211に送信される。情報共有装置UBの第五共有秘密情報生成部210は、第五秘密情報計算部σ3y1を計算するステップB10。計算された第五秘密情報計算部σ3は、共有情報生成部211に送信される。情報共有装置UBの共有情報生成部211は、Hを計算して、その計算結果を共有情報とするステップB11。情報共有装置UAの受信部15図2は、短期公開鍵epkIDAを情報共有装置UAから受信するステップA5。情報共有装置UAの第一共有秘密情報生成部16は、第一共有秘密情報σ1ex1を計算するステップA6。計算された第一共有秘密情報σ1は、共有情報生成部111に送信される。情報共有装置UAの第二共有秘密情報生成部17は、第二共有秘密情報σ1’ex2を計算するステップA7。計算された第二共有秘密情報σ1’は、共有情報生成部111に送信される。情報共有装置UAの第三共有秘密情報生成部18は、第三共有秘密情報σ2eΠi2αeステップA8。計算された第三共有秘密情報σ2は、共有情報生成部111に送信される。情報共有装置UAの第四共有秘密情報生成部19は、第四共有秘密情報σ2’eΠi2αeを計算するステップA9。計算された第四共有秘密情報σ2’は、共有情報生成部111に送信される。情報共有装置UAの第五共有秘密情報生成部110は、第五秘密情報計算部σ3x1を計算するステップA10。計算された第五秘密情報計算部σ3は、共有情報生成部111に送信される。情報共有装置UAの共有情報生成部111は、Hを計算して、その計算結果を共有情報とするステップA11。この共有情報は、例えば認証鍵として用いられる。このようにして、情報共有が行われる。[変形例等]情報共有装置UAの各部間のデータのやり取りは直接行われてもよいし、記憶部10を介して行われてもよい。同様に、情報共有装置UBの各部間のデータのやり取りは直接行われてもよいし、記憶部20を介して行われてもよい。上記の例では、共有情報生成部111及び共有情報生成部211は、ハッシュ関数Hを用いたが、任意の予め定められた関数Fを用いて共有情報を求めてもよい。すなわち、共有情報生成部111及び共有情報生成部211は、Fを計算して、その計算結果を共有情報としてもよい。その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。[安全性の証明]このように、短期秘密鍵を二重化し、共有情報を計算するための共有秘密情報であって短期秘密鍵に由来する共有秘密情報を短期秘密鍵ごとに計算する。これにより、ギャップ問題の難しさを仮定することなく探索問題の難しさをのみを仮定することで安全性を証明することができる。以下、その安全性の証明の概要を説明する。まず、探索問題探索双線形DiffieHellman問題及びギャップ問題ギャップ双線形DiffieHellman問題の定義を説明する。探索双線形DiffieHellman問題:κをセキュリティパラメータとし、Pをκビット素数とする。Gをgを生成元とする位数pの巡回群とし、GTをgTを生成元とする巡回群とする。eG×G→GTを双線形写像とする。双線形DiffieHellman関数BDHG3→GTをBDHgTuvwとして定義する。解答者Sは一様ランダムに選ばれたUguVgvWgw∈Gを入力され、BDHの出力を試みる。解答者Sのアドバンテージを次のように定義する。ADVBDHPrUVW∈GSBDHADVBDHが無視できない確率であるとき、解答者Sは探索双線形DiffieHellman問題を解いたという。ギャップ双線形DiffieHellman問題:κをセキュリティパラメータとし、pをκビット素数とする。Gをgを生成元とする位数pの巡回群とし、GTをgTを生成元とする巡回群とする。eG×G→GTを双線形写像とする。双線形DiffieHellman関数BDHG3→GTをBDHgTuvwとして定義し、判定双線形DiffieHellman述語オラクルDBDHG3×GT→01をを入力としuvwrmodpが成り立つとき1を出力し、そうでなければ0を出力する関数として定義する。解答者Sは一様ランダムに選ばれたUguVgvWgw∈Gと判定双線形DiffieHellman述語オラクルDBDHへのアクセスを入力され、BDHの出力を試みる。解答者Sのアドバンテージを次のように定義する。ADVGBDHPrUVW∈GSDBDHBDHADVGBDHが無視できない確率であるとき、解答者Sはギャップ双線形DiffieHellman問題を解いたという。ギャップ問題は上記のように判定オラクルのヒント付きの探索問題とみなせるので、ギャップ問題の方が真に易しい。情報共有方式の安全性証明を行う際は、ギャップ問題、もしくは探索問題を解くことが難しいことを仮定すると、情報共有方式への攻撃者が存在しないことを示す必要がある。これは、対偶を取ることにより、情報共有方式への攻撃者が存在すると仮定すると、問題を解く解答者を構成できることを示すことと同値である。したがって、安全性証明では実際に攻撃者から解答者を構成する必要がある。そのためには解答者は攻撃者を実際の攻撃環境と見分けがつかないように動作させなければならない。既存方式では、攻撃者が出力したσ1に対してσ1exとσ2eyを解答者が検証し、結果に応じて動作を変えねばならない。しかし、解答者はxとyを知ることができないので、自分で上記の検証を行うことができない。よって、判定オラクルにとを聞き、検証式が成り立つかどうかの答えをもらうことによって証明を行う。このためギャップ問題の難しさを仮定する必要がある。上記の情報共有方式では、双線形ペアリング関数を用いた方式の場合は、w2srw1に対してZ1rZ2esの真理値がZ1ew1∧Z2ew2の真理値と一致することを利用して検証を行う。このテクニックは落とし戸試験と呼ばれる。実施例では、任意のsとrについて、解答者は証明中でx2srx1y2s’r’y1と設定することでσ1rσ1’esとσ2r’σ2’es’の落とし戸試験を行うことで、σ1ex1σ1’ex2σ2ey1σ2’ey2の検証をy1とx1を知ること無しに行うことができる。σ1rσ1’esとσ2r’σ2’es’は解答者の持つ情報のみで検証できるため、判定オラクルは不要であり、ギャップ問題の難しさを仮定する必要が無くなる。"