(57)【特許請求の範囲】
【請求項１】
情報共有装置Ａ及び情報共有装置Ｂで情報を共有する情報共有システムにおいて、
セキュリティパラメータｋは正の整数であり、
上記情報共有装置Ａは、
第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする合成秘密鍵生成部と、
長期公開鍵ｐｋ１Ｂ及び上記合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する暗号化部と、
第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｓｋ２Ａ及び公開鍵ｐｋ２Ａを生成する鍵生成部と、
上記第一交換情報Ｃ１Ａ及び上記公開鍵ｐｋ２Ａを上記情報共有装置Ｂに送信する送信部と、
第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを上記情報共有装置Ｂから受信する受信部と、
長期公開鍵ｐｋ１Ａ、上記長期秘密鍵ｓｋ１Ａ及び第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する第一復号部と、
上記公開鍵ｐｋ２Ａ、上記長期秘密鍵ｓｋ２Ａ及び上記第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する第二復号部と、
上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記長期公開鍵ｐｋ１Ａ、長期公開鍵ｐｋ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｐｋ２Ａ、上記第一交換情報Ｃ１Ｂ、上記第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成部と、
を含み、
上記情報共有装置Ｂは、
上記第一交換情報Ｃ１Ａ及び上記公開鍵ｐｋ２Ａを上記情報共有装置Ａから受信する受信部と、
第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ｂを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする合成秘密鍵生成部と、
上記長期公開鍵ｐｋ１Ａ及び上記合成秘密鍵ｒ１Ｂを用いて、上記暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する第一暗号化部と、
上記公開鍵ｐｋ２Ａ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋを用いて、上記暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する第二暗号化部と、
上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを上記情報共有装置Ａに送信する送信部と、
上記長期公開鍵ｐｋ１Ｂ、上記長期秘密鍵ｓｋ１Ｂ及び第一交換情報Ｃ１Ａを用いて、上記復号化アルゴリズムＤｅＣａｐにより、上記第一共有情報Ｋ１Ａを生成する復号部と、
上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記長期公開鍵ｐｋ１Ａ、上記長期公開鍵ｐｋ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｐｋ２Ａ、上記第一交換情報Ｃ１Ｂ、上記第二交換情報Ｃ２Ｂを上記情報生成関数に入力したときの出力値を計算する情報生成部と、
を含む、
情報共有システム。
【請求項２】
請求項１の情報共有システムにおいて、
｛０，１｝＊をそれぞれ０又は１である任意の個数のビットから構成されるビット列であるとし、｛０，１｝ｋをそれぞれ０又は１であるｋ個のビットから構成されるビット列であるとして、
上記合成鍵生成関数は、ハッシュ関数Ｇ：｛０，１｝＊→｛０，１｝ｋであり、
上記情報生成関数は、ハッシュ関数Ｈ：｛０，１｝＊→｛０，１｝ｋである、
情報共有システム。
【請求項３】
請求項１の情報共有システムにおいて、
長期秘密鍵ｔＡをｔＡ∈｛０，１｝ｋ、短期秘密鍵ｓ’１Ａをｓ’１Ａ∈｛０，１｝ｋ、ＰＲＦ１及びＰＲＦ２を擬似ランダム関数、ｘｏｒを排他的論理和として、上記情報共有装置Ａの合成秘密鍵生成部の合成鍵生成関数は、ＰＲＦ１（ｔＡ，ｒ’１Ａ）ｘｏｒＰＲＦ２（ｓ’１Ａ，ｔＡ）であり、
長期秘密鍵ｔＢをｔＢ∈｛０，１｝ｋ、短期秘密鍵ｓ’１Ｂをｓ’１Ｂ∈｛０，１｝ｋとして、上記情報共有装置Ｂの合成秘密鍵生成部の合成鍵生成関数は、ＰＲＦ１（ｔＢ，ｒ’１Ｂ）ｘｏｒＰＲＦ２（ｓ’１Ｂ，ｔＢ）であり、
Ｅｘｔをランダムネスエクストラクタ、ＰＲＦ３を擬似ランダム関数、ｓｉｄ＝｛ｐｋ１Ａ，ｐｋ１Ｂ，Ｃ１Ａ，ｐｋ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ｝、Ｌ１Ａ＝Ｅｘｔ（Ｋ１Ａ）、Ｌ１Ｂ＝Ｅｘｔ（Ｋ１Ｂ）、Ｌ２Ｂ＝Ｅｘｔ（Ｋ２Ｂ）として、上記情報生成関数は、ＰＲＦ３（Ｌ１Ａ，ｓｉｄ）ｘｏｒＰＲＦ３（Ｌ１Ｂ，ｓｉｄ）ｘｏｒＰＲＦ３（Ｌ２Ｂ，ｓｉｄ）である、
情報共有システム。
【請求項４】
情報共有装置Ａ及び情報共有装置Ｂで情報を共有する情報共有システムにおいて、
セキュリティパラメータｋは正の整数であり、
上記情報共有装置Ａは、
第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び第一長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする合成秘密鍵生成部と、
マスタ公開鍵ｍｐｋ１、情報共有装置Ｂの識別子であるＩＤ１Ｂ∈｛０，１｝ｋ及び上記合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する暗号化部と、
第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｍｓｋ２Ａ及び公開鍵ｍｐｋ２Ａを生成する鍵生成部と、
上記情報共有装置Ａの第二の識別子であるＩＤ２Ａ∈｛０，１｝ｋを選択するＩＤ選択部と、
上記秘密鍵ｍｓｋ２Ａ、上記公開鍵ｍｐｋ２Ａ及び上記ＩＤ２Ａを用いて、所定の鍵導出アルゴリズムＫｅｙＤｅｒにより、第二長期秘密鍵ｓｋ２Ａを生成する鍵導出部と、
上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ及び上記ＩＤ２Ａを上記情報共有装置Ｂに送信する送信部と、
第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを上記情報共有装置Ｂから受信する受信部と、
情報共有装置Ａの公開鍵ｍｐｋ１Ａ、情報共有装置Ａの第一の識別子であるＩＤ１Ａ、上記第一長期秘密鍵ｓｋ１Ａ及び上記第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する第一復号部と、
上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第二長期秘密鍵ｓｋ２Ａ及び上記第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する第二復号部と、
上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記ＩＤ１Ａ、上記ＩＤ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成部と、
を含み、
上記情報共有装置Ｂは、
上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ及び上記ＩＤ２Ａを上記情報共有装置Ａから受信する受信部と、
第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ｂを上記合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする合成秘密鍵生成部と、
情報共有装置Ａの公開鍵ｍｐｋ１Ａ、上記ＩＤ１Ａ及び上記合成秘密鍵ｒ１Ｂを用いて、上記暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する第一暗号化部と、
上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋを用いて、上記暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する第二暗号化部と、
上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを上記情報共有装置Ａに送信する送信部と、
情報共有装置Ｂの公開鍵ｍｐｋ１Ｂ、上記ＩＤ１Ｂ、上記第一長期秘密鍵ｓｋ１Ｂ及び第一交換情報Ｃ１Ａを用いて、上記復号化アルゴリズムＤｅＣａｐにより、上記第一共有情報Ｋ１Ａを生成する復号部と、
上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記ＩＤ１Ａ、上記ＩＤ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを上記情報生成関数に入力したときの出力値を計算する情報生成部と、
を含む、
情報共有システム。
【請求項５】
請求項４の情報共有システムにおいて、
｛０，１｝＊をそれぞれ０又は１である任意の個数のビットから構成されるビット列であるとし、｛０，１｝ｋをそれぞれ０又は１であるｋ個のビットから構成されるビット列であるとして、
上記合成鍵生成関数は、ハッシュ関数Ｇ：｛０，１｝＊→｛０，１｝ｋであり、
上記情報生成関数は、ハッシュ関数Ｈ：｛０，１｝＊→｛０，１｝ｋである、
情報共有システム。
【請求項６】
請求項４の情報共有システムにおいて、
上記情報共有装置Ａの合成秘密鍵生成部の合成鍵生成関数は、長期秘密鍵ｔＡをｔＡ∈｛０，１｝ｋ、短期秘密鍵ｓ’１Ａをｓ’１Ａ∈｛０，１｝ｋ、ＰＲＦ１及びＰＲＦ２を擬似ランダム関数、ｘｏｒを排他的論理和として、ＰＲＦ１（ｔＡ，ｒ’１Ａ）ｘｏｒＰＲＦ２（ｓ’１Ａ，ｔＡ）であり、
上記情報共有装置Ｂの合成秘密鍵生成部の合成鍵生成関数は、長期秘密鍵ｔＢをｔＢ∈｛０，１｝ｋ、短期秘密鍵ｓ’１Ｂをｓ’１Ｂ∈｛０，１｝ｋとして、ＰＲＦ１（ｔＢ，ｒ’１Ｂ）ｘｏｒＰＲＦ２（ｓ’１Ｂ，ｔＢ）であり、
Ｅｘｔをランダムネスエクストラクタ、ＰＲＦ３を擬似ランダム関数、ｓｉｄ＝｛ＩＤ１Ａ，ＩＤ１Ｂ，Ｃ１Ａ，ｍｐｋ２Ａ，ＩＤ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ，｝、Ｌ１Ａ＝Ｅｘｔ（Ｋ１Ａ）、Ｌ１Ｂ＝Ｅｘｔ（Ｋ１Ｂ）、Ｌ２Ｂ＝Ｅｘｔ（Ｋ２Ｂ）として、上記情報生成関数は、ＰＲＦ３（Ｌ１Ａ，ｓｉｄ）ｘｏｒＰＲＦ３（Ｌ１Ｂ，ｓｉｄ）ｘｏｒＰＲＦ３（Ｌ２Ｂ，ｓｉｄ）である、
情報共有システム。
【請求項７】
情報共有装置Ａ及び情報共有装置Ｂで情報を共有する情報共有方法において、
セキュリティパラメータｋは正の整数であり、
上記情報共有装置Ａが、第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする合成秘密鍵生成ステップと、
上記情報共有装置Ａが、長期公開鍵ｐｋ１Ｂ及び上記合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する暗号化ステップと、
上記情報共有装置Ａが、第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｓｋ２Ａ及び公開鍵ｐｋ２Ａを生成する鍵生成ステップと、
上記情報共有装置Ａが、上記第一交換情報Ｃ１Ａ及び上記公開鍵ｐｋ２Ａを上記情報共有装置Ｂに送信する送信ステップと、
上記情報共有装置Ｂが、上記第一交換情報Ｃ１Ａ及び上記公開鍵ｐｋ２Ａを上記情報共有装置Ａから受信する受信ステップと、
上記情報共有装置Ｂが、第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ｂを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする合成秘密鍵生成ステップと、
上記情報共有装置Ｂが、上記長期公開鍵ｐｋ１Ａ及び上記合成秘密鍵ｒ１Ｂを用いて、上記暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する第一暗号化ステップと、
上記情報共有装置Ｂが、上記公開鍵ｐｋ２Ａ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋを用いて、上記暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する第二暗号化ステップと、
上記情報共有装置Ｂが、上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを上記情報共有装置Ａに送信する送信ステップと、
上記情報共有装置Ａが、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを上記情報共有装置Ｂから受信する受信ステップと、
上記情報共有装置Ａが、長期公開鍵ｐｋ１Ａ、上記長期秘密鍵ｓｋ１Ａ及び第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する第一復号ステップと、
上記情報共有装置Ａが、上記公開鍵ｐｋ２Ａ、上記長期秘密鍵ｓｋ２Ａ及び上記第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する第二復号ステップと、
上記情報共有装置Ａが、上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記長期公開鍵ｐｋ１Ａ、上記長期公開鍵ｐｋ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｐｋ２Ａ、上記第一交換情報Ｃ１Ｂ、上記第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成ステップと、
上記情報共有装置Ｂが、上記長期公開鍵ｐｋ１Ｂ、上記長期秘密鍵ｓｋ１Ｂ及び第一交換情報Ｃ１Ａを用いて、上記復号化アルゴリズムＤｅＣａｐにより、上記第一共有情報Ｋ１Ａを生成する復号ステップと、
上記情報共有装置Ｂが、上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記長期公開鍵ｐｋ１Ａ、上記長期公開鍵ｐｋ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｐｋ２Ａ、上記第一交換情報Ｃ１Ｂ、上記第二交換情報Ｃ２Ｂを上記情報生成関数に入力したときの出力値を計算する情報生成ステップと、を含む、
情報共有方法。
【請求項８】
情報共有装置Ａ及び情報共有装置Ｂで情報を共有する情報共有方法において、
セキュリティパラメータｋは正の整数であり、
上記情報共有装置Ａが、第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び第一長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする合成秘密鍵生成ステップと、
上記情報共有装置Ａが、マスタ公開鍵ｍｐｋ１、情報共有装置Ｂの識別子であるＩＤ１Ｂ∈｛０，１｝ｋ及び上記合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する暗号化ステップと、
上記情報共有装置Ａが、第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｍｓｋ２Ａ及び公開鍵ｍｐｋ２Ａを生成する鍵生成ステップと、
上記情報共有装置Ａが、上記情報共有装置Ａの第二の識別子であるＩＤ２Ａ∈｛０，１｝ｋを選択するＩＤ選択ステップと、
上記情報共有装置Ａが、上記秘密鍵ｍｓｋ２Ａ、上記公開鍵ｍｐｋ２Ａ及び上記ＩＤ２Ａを用いて、所定の鍵導出アルゴリズムＫｅｙＤｅｒにより、第二長期秘密鍵ｓｋ２Ａを生成する鍵導出ステップと、
上記情報共有装置Ａが、上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ及び上記ＩＤ２Ａを上記情報共有装置Ｂに送信する送信ステップと、
上記情報共有装置Ｂが、上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ及び上記ＩＤ２Ａを上記情報共有装置Ａから受信する受信ステップと、
上記情報共有装置Ｂが、第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ｂを上記合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする合成秘密鍵生成ステップと、
上記情報共有装置Ｂが、情報共有装置Ａの公開鍵ｍｐｋ１Ａ、上記ＩＤ１Ａ及び上記合成秘密鍵ｒ１Ｂを用いて、上記暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する第一暗号化ステップと、
上記情報共有装置Ｂが、上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋを用いて、上記暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する第二暗号化ステップと、
上記情報共有装置Ｂが、上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを上記情報共有装置Ａに送信する送信ステップと、
上記情報共有装置Ａが、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを上記情報共有装置Ｂから受信する受信ステップと、
上記情報共有装置Ａが、情報共有装置Ａの公開鍵ｍｐｋ１Ａ、情報共有装置Ａの第一の識別子であるＩＤ１Ａ、上記第一長期秘密鍵ｓｋ１Ａ及び上記第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する第一復号ステップと、
上記情報共有装置Ａが、上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第二長期秘密鍵ｓｋ２Ａ及び上記第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する第二復号ステップと、
上記情報共有装置Ａが、上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記ＩＤ１Ａ、上記ＩＤ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成ステップと、
上記情報共有装置Ｂが、情報共有装置Ｂの公開鍵ｍｐｋ１Ｂ、上記ＩＤ１Ｂ、上記第一長期秘密鍵ｓｋ１Ｂ及び第一交換情報Ｃ１Ａを用いて、上記復号化アルゴリズムＤｅＣａｐにより、上記第一共有情報Ｋ１Ａを生成する復号ステップと、
上記情報共有装置Ｂが、上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記ＩＤ１Ａ、上記ＩＤ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを上記情報生成関数に入力したときの出力値を計算する情報生成ステップと、を含む、
情報共有方法。
【請求項９】
他の情報共有装置と情報を共有する情報共有装置において、
セキュリティパラメータｋは正の整数であり、
第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする合成秘密鍵生成部と、
長期公開鍵ｐｋ１Ｂ及び上記合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する暗号化部と、
第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｓｋ２Ａ及び公開鍵ｐｋ２Ａを生成する鍵生成部と、
上記第一交換情報Ｃ１Ａ及び上記公開鍵ｐｋ２Ａを上記他の情報共有装置に送信する送信部と、
第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを上記他の情報共有装置から受信する受信部と、
長期公開鍵ｐｋ１Ａ、上記長期秘密鍵ｓｋ１Ａ及び第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する第一復号部と、
上記公開鍵ｐｋ２Ａ、上記長期秘密鍵ｓｋ２Ａ及び上記第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する第二復号部と、
上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記長期公開鍵ｐｋ１Ａ、長期公開鍵ｐｋ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｐｋ２Ａ、上記第一交換情報Ｃ１Ｂ、上記第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成部と、を含む、
情報共有装置。
【請求項１０】
他の情報共有装置と情報を共有する情報共有装置において、
セキュリティパラメータｋは正の整数であり、
第一交換情報Ｃ１Ａ及び公開鍵ｐｋ２Ａを上記他の情報共有装置から受信する受信部と、
第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ｂを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする合成秘密鍵生成部と、
長期公開鍵ｐｋ１Ａ及び上記合成秘密鍵ｒ１Ｂを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する第一暗号化部と、
上記公開鍵ｐｋ２Ａ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する第二暗号化部と、
上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを上記他の情報共有装置に送信する送信部と、
上記長期公開鍵ｐｋ１Ｂ、上記長期秘密鍵ｓｋ１Ｂ及び上記第一交換情報Ｃ１Ａを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ａを生成する復号部と、
上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記長期公開鍵ｐｋ１Ａ、上記長期公開鍵ｐｋ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｐｋ２Ａ、上記第一交換情報Ｃ１Ｂ、上記第二交換情報Ｃ２Ｂを上記情報生成関数に入力したときの出力値を計算する情報生成部と、を含む、
情報共有装置
【請求項１１】
他の情報共有装置と情報を共有する情報共有装置において、
セキュリティパラメータｋは正の整数であり、
第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び第一長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする合成秘密鍵生成部と、
マスタ公開鍵ｍｐｋ１、上記他の情報共有装置の識別子であるＩＤ１Ｂ∈｛０，１｝ｋ及び上記合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する暗号化部と、
第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｍｓｋ２Ａ及び公開鍵ｍｐｋ２Ａを生成する鍵生成部と、
上記情報共有装置の第二の識別子であるＩＤ２Ａ∈｛０，１｝ｋを選択するＩＤ選択部と、
上記秘密鍵ｍｓｋ２Ａ、上記公開鍵ｍｐｋ２Ａ及び上記ＩＤ２Ａを用いて、所定の鍵導出アルゴリズムＫｅｙＤｅｒにより、第二長期秘密鍵ｓｋ２Ａを生成する鍵導出部と、
上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ及び上記ＩＤ２Ａを上記他の情報共有装置に送信する送信部と、
第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを上記他の情報共有装置から受信する受信部と、
上記情報共有装置の公開鍵ｍｐｋ１Ａ、上記情報共有装置の第一の識別子であるＩＤ１Ａ、上記第一長期秘密鍵ｓｋ１Ａ及び上記第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する第一復号部と、
上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第二長期秘密鍵ｓｋ２Ａ及び上記第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する第二復号部と、
上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記ＩＤ１Ａ、上記ＩＤ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成部と、を含む、
情報共有装置。
【請求項１２】
他の情報共有装置と情報を共有する情報共有装置において、
セキュリティパラメータｋは正の整数であり、
第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ及び上記他の情報共有装置の第二の識別子であるＩＤ２Ａを上記他の情報共有装置から受信する受信部と、
第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ｂを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする合成秘密鍵生成部と、
上記他の情報共有装置の公開鍵ｍｐｋ１Ａ、上記他の情報共有装置の第一の識別子であるＩＤ１Ａ及び上記合成秘密鍵ｒ１Ｂを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する第一暗号化部と、
上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する第二暗号化部と、
上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを上記他の情報共有装置に送信する送信部と、
上記情報共有装置の公開鍵ｍｐｋ１Ｂ、上記の情報共有装置の識別子であるＩＤ１Ｂ、上記第一長期秘密鍵ｓｋ１Ｂ及び上記第一交換情報Ｃ１Ａを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、上記第一共有情報Ｋ１Ａを生成する復号部と、
上記第一共有情報Ｋ１Ａ、上記第一共有情報Ｋ１Ｂ、上記第二共有情報Ｋ２Ｂ、上記ＩＤ１Ａ、上記ＩＤ１Ｂ、上記第一交換情報Ｃ１Ａ、上記公開鍵ｍｐｋ２Ａ、上記ＩＤ２Ａ、上記第一交換情報Ｃ１Ｂ及び上記第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成部と、を含む、
情報共有装置。
【請求項１３】
請求項９から１２の何れかの情報共有装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術の応用技術、特に２つの装置でセッション鍵等の情報を共有する技術に関する。
【背景技術】
【０００２】
情報共有方式として、例えば非特許文献１に記載されている、Ｋｅｙ  Ｅｎｃａｐｓｕｌａｔｉｏｎ  Ｍｅｃｈａｎｉｓｍ（ＫＥＭ）を用いたＢＣＧＰ方式が知られている。
【０００３】
このＢＣＧＰ方式については、いわゆるＣＫ−ｍｏｄｅｌでの安全性が示されている。ＣＫ−ｍｏｄｅｌについては、非特許文献２を参照のこと。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Colin Boyd, Yvonne Cliff, Juan Manuel Gonz´alez Nieto, Kenneth G.Paterson, “Efficient One-Round Key Exchange in the Standard Model.”, ACISP 2008 p.69-83
【非特許文献２】Ran Canetti and Hugo Krawczyk, “Analysis of key-exchange protocols and their use for building secure channels.”, EUROCRYPT 2001, p.453-474, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１に記載されているＢＣＧＰ方式については、短期秘密鍵の漏洩を許すいわゆるｅＣＫ−ｍｏｄｅｌで攻撃することができる。このため、このＢＣＧＰ方式は、乱数生成器の脆弱性などにより短期秘密鍵の漏洩が起こる場合に必ずしも安全ではない。
【０００６】
この発明の課題は、短期秘密鍵の漏洩を許すいわゆるｅＣＫ−ｍｏｄｅｌでも安全性を保つことができる情報提供システム、方法、情報共有装置及びそのプログラムを提供することである。
【０００７】
なお、ｅＣＫ−ｍｏｄｅｌについては、参考文献１を参照のこと。
【０００８】
［参考文献１］Brian~A. LaMacchia, Kristin Lauter, and Anton Mityagin, “Stronger security of authenticated key exchange.”, ProvSec 2007, p.1-16. 2007.
【課題を解決するための手段】
【０００９】
この発明の１つの態様である情報共有システムは、情報共有装置Ａ及び情報共有装置Ｂで情報を共有する。セキュリティパラメータｋは正の整数である。情報共有装置Ａは、第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする合成秘密鍵生成部と、長期公開鍵ｐｋ１Ｂ及び合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する暗号化部と、第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｓｋ２Ａ及び公開鍵ｐｋ２Ａを生成する鍵生成部と、第一交換情報Ｃ１Ａ及び公開鍵ｐｋ２Ａを情報共有装置Ｂに送信する送信部と、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報共有装置Ｂから受信する受信部と、長期公開鍵ｐｋ１Ａ、長期秘密鍵ｓｋ１Ａ及び第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する第一復号部と、公開鍵ｐｋ２Ａ、長期秘密鍵ｓｋ２Ａ及び第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する第二復号部と、第一共有情報Ｋ１Ａ、第一共有情報Ｋ１Ｂ、第二共有情報Ｋ２Ｂ、長期公開鍵ｐｋ１Ａ、長期公開鍵ｐｋ１Ｂ、第一交換情報Ｃ１Ａ、公開鍵ｐｋ２Ａ、第一交換情報Ｃ１Ｂ、第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成部と、を含む。情報共有装置Ｂは、第一交換情報Ｃ１Ａ及び公開鍵ｐｋ２Ａを情報共有装置Ａから受信する受信部と、第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ｂを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする合成秘密鍵生成部と、長期公開鍵ｐｋ１Ａ及び合成秘密鍵ｒ１Ｂを用いて、暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する第一暗号化部と、公開鍵ｐｋ２Ａ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋを用いて、暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する第二暗号化部と、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報共有装置Ａに送信する送信部と、長期公開鍵ｐｋ１Ｂ、長期秘密鍵ｓｋ１Ｂ及び第一交換情報Ｃ１Ａを用いて、復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ａを生成する復号部と、第一共有情報Ｋ１Ａ、第一共有情報Ｋ１Ｂ、第二共有情報Ｋ２Ｂ、長期公開鍵ｐｋ１Ａ、長期公開鍵ｐｋ１Ｂ、第一交換情報Ｃ１Ａ、公開鍵ｐｋ２Ａ、第一交換情報Ｃ１Ｂ、第二交換情報Ｃ２Ｂを情報生成関数に入力したときの出力値を計算する情報生成部と、を備える。
【００１０】
この発明の他の１つの態様である情報共有システムは、情報共有装置Ａ及び情報共有装置Ｂで情報を共有する。セキュリティパラメータｋは正の整数である。情報共有装置Ａは、第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び第一長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする合成秘密鍵生成部と、マスタ公開鍵ｍｐｋ１、情報共有装置Ｂの識別子であるＩＤ１Ｂ∈｛０，１｝ｋ及び合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する暗号化部と、第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｍｓｋ２Ａ及び公開鍵ｍｐｋ２Ａを生成する鍵生成部と、情報共有装置Ａの第二の識別子であるＩＤ２Ａ∈｛０，１｝ｋを選択するＩＤ選択部と、秘密鍵ｍｓｋ２Ａ、公開鍵ｍｐｋ２Ａ及びＩＤ２Ａを用いて、所定の鍵導出アルゴリズムＫｅｙＤｅｒにより、第二長期秘密鍵ｓｋ２Ａを生成する鍵導出部と、第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ及びＩＤ２Ａを情報共有装置Ｂに送信する送信部と、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報共有装置Ｂから受信する受信部と、情報共有装置Ａの公開鍵ｍｐｋ１Ａ、情報共有装置Ａの第一の識別子であるＩＤ１Ａ、第一長期秘密鍵ｓｋ１Ａ及び第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する第一復号部と、公開鍵ｐｋ２Ａ、ＩＤ２Ａ、第二長期秘密鍵ｓｋ２Ａ及び第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する第二復号部と、第一共有情報Ｋ１Ａ、第一共有情報Ｋ１Ｂ、第二共有情報Ｋ２Ｂ、ＩＤ１Ａ、ＩＤ１Ｂ、第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ、ＩＤ２Ａ、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する情報生成部と、を含む。情報共有装置Ｂは、第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ及びＩＤ２Ａを情報共有装置Ａからに受信する受信部と、第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び長期秘密鍵ｓｋ１Ｂを合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする合成秘密鍵生成部と、情報共有装置Ａの公開鍵ｍｐｋ１Ａ、ＩＤ１Ａ及び合成秘密鍵ｒ１Ｂを用いて、暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する第一暗号化部と、公開鍵ｍｐｋ２Ａ、ＩＤ２Ａ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋを用いて、暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する第二暗号化部と、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報共有装置Ａに送信する送信部と、情報共有装置Ｂの公開鍵ｍｐｋ１Ｂ、ＩＤ１Ｂ、第一長期秘密鍵ｓｋ１Ｂ及び第一交換情報Ｃ１Ａを用いて、復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ａを生成する復号部と、第一共有情報Ｋ１Ａ、第一共有情報Ｋ１Ｂ、第二共有情報Ｋ２Ｂ、ＩＤ１Ａ、ＩＤ１Ｂ、第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ、ＩＤ２Ａ、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報生成関数に入力したときの出力値を計算する情報生成部と、を含む。
【発明の効果】
【００１１】
短期秘密鍵及び長期秘密鍵を用いて生成した合成秘密鍵を用いて情報の共有を行うことにより、短期秘密鍵の漏洩を許すいわゆるｅＣＫ−ｍｏｄｅｌでも安全性を保つことができる。
【図面の簡単な説明】
【００１２】
【図１】情報共有システムの構成の例を説明するためのブロック図。
【図２】第一実施形態及び第二実施形態の情報共有装置Ａの例を説明するためのブロック図。
【図３】第一実施形態及び第二実施形態の情報共有装置Ｂの例を説明するためのブロック図。
【図４】第三実施形態及び第四実施形態の情報共有装置Ａの例を説明するためのブロック図。
【図５】第三実施形態及び第四実施形態の情報共有装置Ｂの例を説明するためのブロック図。
【図６】第一実施形態及び第二実施形態の情報共有方法の例を説明するためのフローチャート。
【図７】第一実施形態及び第三実施形態の情報共有方法の例を説明するためのフローチャート。
【発明を実施するための形態】
【００１３】
以下、図面を参照してこの発明の実施形態を説明する。
【００１４】
［第一実施形態］
第一実施形態のＫＥＭを用いた情報共有システム、方法を以下に示す。
【００１５】
＜アルゴリズム＞
まず、次のようにＫＥＭの各アルゴリズムが定まっているとする。
ＫｅｙＧｅｎ（ｒ）→（ｓｋ，ｐｋ）は、ＫＥＭの鍵生成アルゴリズム。
ＥｎＣａｐ（ｐｋ，ｒ’）→（Ｃ，Ｋ）は、ＫＥＭの暗号化アルゴリズム。
ＤｅＣａｐ（ｐｋ，ｓｋ，Ｃ）→Ｋは、ＫＥＭの復号化アルゴリズム。
【００１６】
＜公開パラメータ＞
Ｈ：｛０，１｝＊→｛０，１｝ｋと、Ｇ：｛０，１｝＊→｛０，１｝ｋとをハッシュ関数とする。｛０，１｝ｘは、それぞれ０又は１であるｘ個のビットから構成されるビット列を意味する。＊は任意の数を意味する。すなわち、｛０，１｝＊は、任意の長さのビット列を意味する。ｋは、所定の正の整数であり、セキュリティパラメータである。
【００１７】
ここで、ハッシュ関数の引数が２以上ありこれらの引数をカンマ「，」で区切った場合には、これらの引数を所定の順序でビット結合したビット列をそのハッシュ関数に入力することを意味する。すなわち、例えば、情報共有装置Ａにおいて計算されるＧ（ｒ’１Ａ，ｓｋ１Ａ）＝Ｇ（ｒ’１Ａ||ｓｋ１Ａ）である。また、ビット結合する引数の順序は、各ハッシュ関数において同じであるとする。すなわち、情報共有装置Ａ及び情報共有装置Ｂにおいて、ビット結合をする所定の順序は同じである。つまり、この場合、情報共有装置Ｂにおいて計算されるＧ（ｒ’１Ｂ，ｓｋ１Ｂ）は、Ｇ（ｒ’１Ｂ||ｓｋ１Ｂ）となる。これは、ハッシュ関数Ｈについても同様である。
【００１８】
各情報共有装置ｉ（ｉ＝Ａ，Ｂ）は、ｒｉ∈｛０，１｝ｋをランダムに選択し、鍵生成ＫｅｙＧｅｎ（ｒｉ）→（ｓｋ１ｉ，ｐｋ１ｉ）を行い、ｓｋ１ｉを長期秘密鍵として秘密に保持し、ｐｋ１ｉを長期公開鍵として公開する。
【００１９】
＜情報交換＞
長期公開鍵ｐｋ１Ａ及び長期秘密鍵ｓｋ１Ａを持つ情報共有装置Ａと、長期公開鍵ｐｋ１Ｂ及び長期秘密鍵ｓｋ１Ｂを持つ情報共有装置Ｂとは、以下のようにして交換情報を交換して、情報Ｋを共有する。
【００２０】
１．情報共有装置Ａの処理
情報共有装置Ａは、第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋをランダムに選び、Ｇ（ｒ’１Ａ，ｓｋ１Ａ）＝ｒ１Ａ∈｛０，１｝ｋを計算する。
情報共有装置Ａは、ＥｎＣａｐ（ｐｋ１Ｂ，ｒ１Ａ）→（Ｃ１Ａ，Ｋ１Ａ）を計算し、ＫｅｙＧｅｎ（ｒ２Ａ）→（ｓｋ２Ａ，ｐｋ２Ａ）を計算する。
情報共有装置Ａは、（Ｃ１Ａ，ｐｋ２Ａ）を情報共有装置Ｂに送信する。
【００２１】
２．情報共有装置Ｂの処理
情報共有装置Ｂは、（Ｃ１Ａ，ｐｋ２Ａ）を受信する。
【００２２】
情報共有装置Ｂは、短期秘密鍵ｒ’１Ｂ，ｒ２Ｂ∈｛０，１｝ｋをランダムに選び、Ｇ（ｒ’１Ｂ，ｓｋ１Ｂ）＝ｒ１Ｂ∈｛０，１｝ｋを計算する。
情報共有装置Ｂは、ＥｎＣａｐ（ｐｋ１Ａ，ｒ１Ｂ）→（Ｃ１Ｂ，Ｋ１Ｂ）を計算し、ＥｎＣａｐ（ｐｋ２Ａ，ｒ２Ｂ）→（Ｃ２Ｂ，Ｋ２Ｂ）を計算する。
情報共有装置Ｂは、（Ｃ１Ｂ，Ｃ２Ｂ）を情報共有装置Ａに送信する。
情報共有装置Ｂは、ＤｅＣａｐ（ｐｋ１Ｂ，ｓｋ１Ｂ，Ｃ１Ａ）→Ｋ１Ａを計算する。
情報共有装置Ｂは、共有情報Ｋ＝Ｈ（Ｋ１Ａ，Ｋ１Ｂ，Ｋ２Ｂ，ｓｉｄ），ｓｉｄ＝（ｐｋ１Ａ，ｐｋ１Ｂ，Ｃ１Ａ，ｐｋ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ）を計算する。共有情報Ｋは、例えば共有鍵として用いられる。
【００２３】
３．情報共有装置Ａの処理
情報共有装置Ａは、（Ｃ１Ｂ，Ｃ２Ｂ）を受信する。
情報共有装置Ａは、ＤｅＣａｐ（ｐｋ１Ａ，ｓｋ１Ａ，Ｃ１Ｂ）→Ｋ１Ｂを計算し、ＤｅＣａｐ（ｐｋ２Ａ，ｓｋ２Ａ，Ｃ２Ｂ）→Ｋ２Ｂを計算する。
情報共有装置Ａは、共有情報Ｋ＝Ｈ（Ｋ１Ａ，Ｋ１Ｂ，Ｋ２Ｂ，ｓｉｄ），ｓｉｄ＝（ｐｋ１Ａ，ｐｋ１Ｂ，Ｃ１Ａ，ｐｋ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ）を計算する。共有情報Ｋは、例えば共有鍵として用いられる。
【００２４】
＜装置＞
公開パラメータ及び情報交換の欄で示した処理は、例えば図１から図３に示された情報共有装置Ａ及び情報共有装置Ｂにより実行される。
【００２５】
第一実施形態の情報共有装置は、図１に示すように、情報共有装置Ａ及び情報共有装置Ｂを例えば備える。
【００２６】
情報共有装置Ａは、図２に示すように、記憶部Ａ０、乱数生成部Ａ１、長期鍵生成部Ａ２、短期秘密鍵生成部Ａ３、合成秘密鍵生成部Ａ４、暗号化部Ａ５、鍵生成部Ａ６、送信部Ａ７、受信部Ａ８、第一復号部Ａ９、第二復号部Ａ１０、情報生成部Ａ１１を例えば備える。
【００２７】
情報共有装置Ｂは、図３に示すように、記憶部Ｂ０、乱数生成部Ｂ１、長期鍵生成部Ｂ２、短期秘密鍵生成部Ｂ３、合成秘密鍵生成部Ｂ４、第一暗号化部Ｂ５、第二暗号化部Ｂ６、送信部Ｂ７、受信部Ｂ８、復号部Ｂ９、情報生成部Ｂ１０を例えば備える。
【００２８】
情報共有方法の処理の流れの例を図６に示す。
【００２９】
情報共有装置Ａの乱数生成部Ａ１は、乱数ｒＡ∈｛０，１｝ｋを生成する（ステップＳＡ１）。生成された乱数ｒＡは、長期鍵生成部Ａ２に送信される。
【００３０】
長期鍵生成部Ａ２は、鍵生成ＫｅｙＧｅｎ（ｒＡ）→（ｓｋ１Ａ，ｐｋ１Ａ）を行い（ステップＳＡ２）、ｓｋ１Ａを長期秘密鍵として秘密に保持し、ｐｋ１Ａを長期公開鍵として公開する。長期秘密鍵ｓｋ１Ａは、合成秘密鍵生成部Ａ４及び第一復号部Ａ９に送信される。長期公開鍵ｐｋ１Ａは、第一復号部Ａ９及び情報生成部Ａ１１に送信される。
【００３１】
短期秘密鍵生成部Ａ３は、第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋをランダムに選択する（ステップＳＡ３）。選択された第一短期秘密鍵ｒ’１Ａは、合成秘密鍵生成部Ａ４に送信される。選択された第二短期秘密鍵ｒ２Ａは、鍵生成部Ａ６に送信される。
【００３２】
合成秘密鍵生成部Ａ４は、第一短期秘密鍵ｒ’１Ａ及び長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする（ステップＳＡ４）。ここで、所定の合成鍵生成関数は、例えばハッシュ関数Ｇ（ｒ’１Ａ，ｓｋ１Ａ）である。合成秘密鍵ｒ１Ａは、暗号化部Ａ５に送信される。
【００３３】
暗号化部Ａ５は、長期公開鍵ｐｋ１Ｂ及び合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する（ステップＳＡ５）。生成された第一交換情報Ｃ１Ａは、送信部Ａ７及び情報生成部Ａ１１に送信される。生成された第一共有情報Ｋ１Ａは、情報生成部Ａ１１に送信される。
【００３４】
鍵生成部Ａ６は、第二短期秘密鍵ｒ２Ａを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｓｋ２Ａ及び公開鍵ｐｋ２Ａを生成する（ステップＳＡ６）。生成された秘密鍵ｓｋ２Ａは、第二復号部Ａ１０に送信される。生成された公開鍵ｐｋ２Ａは、送信部Ａ７、第二復号部Ａ１０及び情報生成部Ａ１１に送信される。
【００３５】
送信部Ａ７は、第一交換情報Ｃ１Ａ及び公開鍵ｐｋ２Ａを情報共有装置Ｂに送信する（ステップＳＡ７）。
【００３６】
受信部Ａ８は、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報共有装置Ｂから受信する（ステップＳＡ８）。第一交換情報Ｃ１Ｂは、第一復号部Ａ９及び情報生成部Ａ１１に送信される。第二交換情報Ｃ２Ｂは、第二復号部Ａ１０及び情報生成部Ａ１１に送信される。
【００３７】
第一復号部Ａ９は、長期公開鍵ｐｋ１Ａ、長期秘密鍵ｓｋ１Ａ及び第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する（ステップＳＡ９）。生成された第一共有情報Ｋ１Ｂは、情報生成部Ａ１１に送信される。
【００３８】
第二復号部Ａ１０は、公開鍵ｐｋ２Ａ、長期秘密鍵ｓｋ２Ａ及び第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する（ステップＳＡ１０）。生成された第二共有情報Ｋ２Ｂは、情報生成部Ａ１１に送信される。
【００３９】
情報生成部Ａ１１は、第一共有情報Ｋ１Ａ、第一共有情報Ｋ１Ｂ、第二共有情報Ｋ２Ｂ、長期公開鍵ｐｋ１Ａ、長期公開鍵ｐｋ１Ｂ、第一交換情報Ｃ１Ａ、公開鍵ｐｋ２Ａ、第一交換情報Ｃ１Ｂ、第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する（ステップＳＡ１１）。所定の情報生成関数は、例えばハッシュ関数Ｈである。この場合、情報生成部Ａ１１が計算する出力値は、Ｈ（Ｋ１Ａ，Ｋ１Ｂ，Ｋ２Ｂ，ｐｋ１Ａ，ｐｋ１Ｂ，Ｃ１Ａ，ｐｋ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ）となる。この出力値が、共有の対象となる共有情報Ｋとなる。
【００４０】
情報共有装置Ｂの受信部Ｂ８（図３）は、第一交換情報Ｃ１Ａ及び公開鍵ｐｋ２Ａを受信する（ステップＳＢ８）。第一交換情報Ｃ１Ａは、復号部Ｂ９に送信される。公開鍵ｐｋ２Ａは、第二暗号化部Ｂ６に送信される。
【００４１】
乱数生成部Ｂ１は、乱数ｒＢ∈｛０，１｝ｋを生成する（ステップＳＢ１）。生成された乱数ｒＢは、長期鍵生成部Ｂ２に送信される。
【００４２】
長期鍵生成部Ｂ２は、鍵生成ＫｅｙＧｅｎ（ｒＢ）→（ｓｋ１Ｂ，ｐｋ１Ｂ）を行い（ステップＳＢ２）、ｓｋ１Ｂを長期秘密鍵として秘密に保持し、ｐｋ１Ｂを長期公開鍵として公開する。長期秘密鍵ｓｋ１Ｂは、合成秘密鍵生成部Ｂ４及び復号部Ｂ９に送信される。長期公開鍵ｐｋ１Ｂは、復号部Ｂ９及び情報生成部Ｂ１０に送信される。
【００４３】
短期秘密鍵生成部Ｂ３は、第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋをランダムに選択する（ステップＳＢ３）。選択された第一短期秘密鍵ｒ’１Ｂは、合成秘密鍵生成部Ｂ４に送信される。選択された第二短期秘密鍵ｒ２Ｂは、第二暗号化部Ｂ６に送信される。
【００４４】
合成秘密鍵生成部Ｂ４は、第一短期秘密鍵ｒ’１Ｂ及び長期秘密鍵ｓｋ１Ｂを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする（ステップＳＢ４）。ここで、所定の合成鍵生成関数は、合成秘密鍵生成部Ａ４が用いた合成鍵生成関数と同じ関数であり、例えばハッシュ関数Ｇ（ｒ’１Ｂ，ｓｋ１Ｂ）である。合成秘密鍵ｒ１Ｂは、第一暗号化部Ｂ５に送信される。
【００４５】
第一暗号化部Ｂ５は、長期公開鍵ｐｋ１Ａ及び合成秘密鍵ｒ１Ｂを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する（ステップＳＢ５）。生成された第一交換情報Ｃ１Ｂは、送信部Ｂ７及び情報生成部Ｂ１０に送信される。生成された第一共有情報Ｋ１Ｂは、情報生成部Ｂ１０に送信される。
【００４６】
第二暗号化部Ｂ６は、公開鍵ｐｋ２Ａ及び第二短期秘密鍵ｒ２Ｂを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する（ステップＳＢ６）。生成された第二交換情報Ｃ２Ｂは、送信部Ｂ７及び情報生成部Ｂ１０に送信される。生成された第二共有情報Ｋ２Ｂは、情報生成部Ｂ１０に送信される。
【００４７】
送信部Ｂ７は、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報共有装置Ａに送信する（ステップＳＢ７）。
【００４８】
復号部Ｂ９は、長期公開鍵ｐｋ１Ｂ、長期秘密鍵ｓｋ１Ｂ及び第一交換情報Ｃ１Ａを用いて、復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ａを生成する。生成された第一共有情報Ｋ１Ａは、情報生成部Ｂ１０に送信される。
【００４９】
情報生成部Ｂ１０は、第一共有情報Ｋ１Ａ、第一共有情報Ｋ１Ｂ、第二共有情報Ｋ２Ｂ、長期公開鍵ｐｋ１Ａ、長期公開鍵ｐｋ１Ｂ、第一交換情報Ｃ１Ａ、公開鍵ｐｋ２Ａ、第一交換情報Ｃ１Ｂ、第二交換情報Ｃ２Ｂを情報生成関数に入力したときの出力値を計算する。この情報生成関数は、情報共有装置Ａの情報生成部Ａ１１が用いる情報生成関数と同じ関数であり、例えばハッシュ関数Ｈである。この場合、情報生成部Ｂ１０が計算する出力値は、Ｈ（Ｋ１Ａ，Ｋ１Ｂ，Ｋ２Ｂ，ｐｋ１Ａ，ｐｋ１Ｂ，Ｃ１Ａ，ｐｋ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ）となる。この出力値が、共有の対象となる共有情報Ｋとなる。
【００５０】
［第二実施形態］
第二実施形態は、以下の部分において第一実施形態と異なる。以下では、第一実施形態と異なる部分を中心に説明をし、第一実施形態と同様の部分については重複説明を省略する。
【００５１】
ステップＳＡ１において、乱数生成部Ａ１は、長期秘密鍵ｔＡ∈｛０，１｝ｋを更に生成する。生成された長期秘密鍵ｔＡは、合成秘密鍵生成部Ａ４に送信される。
【００５２】
また、ステップＳＡ３において、短期秘密鍵生成部Ａ３は、短期秘密鍵ｓ’１Ａ∈｛０，１｝ｋを更に生成する。生成された短期秘密鍵ｓ’１Ａ∈は、合成秘密鍵生成部Ａ４に送信される。
【００５３】
また、ステップＳＡ４において合成秘密鍵生成部Ａ４は、ＰＲＦ１（ｔＡ，ｒ’１Ａ）ｘｏｒＰＲＦ２（ｓ’１Ａ，ｔＡ）を計算して、合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする。ここで、ＰＲＦ１及びＰＲＦ２はｋ個のビットから構成されるビット列｛０，１｝ｋを出力する擬似ランダム関数、ｘｏｒはビットごとの排他的論理和である。すなわち、第二実施形態においては、合成秘密鍵生成部Ａ４が用いる合成鍵生成関数は、ＰＲＦ１（ｔＡ，ｒ’１Ａ）ｘｏｒＰＲＦ２（ｓ’１Ａ，ｔＡ）となる。擬似ランダム関数は、例えば第一引数を鍵として用いる。
【００５４】
また、ステップＳＢ１において、乱数生成部Ｂ１は、長期秘密鍵ｔＢ∈｛０，１｝ｋを更に生成する。生成された長期秘密鍵ｔＢは、合成秘密鍵生成部Ｂ４に送信される。
【００５５】
また、ステップＳＢ３において、短期秘密鍵生成部Ｂ３は、短期秘密鍵ｓ’１Ｂ∈｛０，１｝ｋを更に生成する。生成された短期秘密鍵ｓ’１Ｂ∈は、合成秘密鍵生成部Ｂ４に送信される。
【００５６】
また、ステップＳＢ４において合成秘密鍵生成部Ｂ４は、ＰＲＦ１（ｔＢ，ｒ’１Ｂ）ｘｏｒＰＲＦ２（ｓ’１Ｂ，ｔＢ）を計算して、合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする。すなわち、第二実施形態においては、合成秘密鍵生成部Ｂ４が用いる合成鍵生成関数は、ＰＲＦ１（ｔＢ，ｒ’１Ｂ）ｘｏｒＰＲＦ２（ｓ’１Ｂ，ｔＢ）となる。
【００５７】
さらに、ステップＳＡ１１及びステップＳＢ１０において、情報生成部Ａ１１及び情報生成部Ｂ１０が用いる情報生成関数は、ＰＲＦ３（Ｌ１Ａ，ｓｉｄ）ｘｏｒＰＲＦ３（Ｌ１Ｂ，ｓｉｄ）ｘｏｒＰＲＦ３（Ｌ２Ｂ，ｓｉｄ）である。ここで、Ｅｘｔはランダムネスエクストラクタ、ＰＲＦ３は擬似ランダム関数、ｓｉｄ＝｛ｐｋ１Ａ，ｐｋ１Ｂ，Ｃ１Ａ，ｐｋ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ｝、Ｌ１Ａ＝Ｅｘｔ（Ｋ１Ａ）、Ｌ１Ｂ＝Ｅｘｔ（Ｋ１Ｂ）、Ｌ２Ｂ＝Ｅｘｔ（Ｋ２Ｂ）である。ランダムネスエクストラクタＥｘｔは、任意の分布の入力に対して一様の分布を持つ出力値を出力する関数である。
【００５８】
このようにすることにより、第二実施形態では、ランダムオラクルモデルを仮定せずに安全性を示すことができる。
【００５９】
［第三実施形態］
第三実施形態は、ＩＤ−ｂａｓｅ  ＫＥＭを用いた情報共有を行うものである。
【００６０】
第三実施形態のＩＤ−ｂａｓｅ  ＫＥＭを用いた情報共有システム、方法を以下に示す。
【００６１】
なお、第一実施形態のｐｋ１Ａが、第三実施形態のｍｐｋ１及びＩＤ１Ａに対応する。また、第一実施形態のｐｋ２Ａが、第三実施形態のｍｐｋ２Ａ及びＩＤ２Ａに対応する。さらに、第一実施形態のｐｋ１Ｂが、第三実施形態のｍｐｋ１及びＩＤ１Ｂに対応する。これ以外の技術的特徴は、第一実施形態と第三実施形態において同様である。
【００６２】
＜アルゴリズム＞
まず、次のようにＫＥＭの各アルゴリズムが定まっているとする。
ＫｅｙＧｅｎ（ｒ）→（ｍｓｋ，ｍｐｋ）は、ＩＤ−ｂａｓｅ  ＫＥＭのマスタ鍵生成アルゴリズム。
ＫｅｙＤｅｒ（ｍｓｋ，ｍｐｋ，ＩＤ）→ｓｋは、ＩＤ−ｂａｓｅ  ＫＥＭの鍵導出アルゴリズム。
ＥｎＣａｐ（ｍｐｋ，ＩＤ，ｒ’）→（Ｃ，Ｋ）は、ＩＤ−ｂａｓｅ  ＫＥＭの暗号化アルゴリズム。
ＤｅＣａｐ（ｍｐｋ，ＩＤ，ｓｋ，Ｃ）→Ｋは、ＩＤ−ｂａｓｅ  ＫＥＭの復号化アルゴリズム。
【００６３】
＜公開パラメータ＞
Ｈ：｛０，１｝＊→｛０，１｝ｋと、Ｇ：｛０，１｝＊→｛０，１｝ｋとをハッシュ関数とする。｛０，１｝ｘは、それぞれ０又は１であるｘ個のビットから構成されるビット列を意味する。＊は任意の数を意味する。すなわち、｛０，１｝＊は、任意の長さのビット列を意味する。ｋは、所定の正の整数であり、セキュリティパラメータである。
【００６４】
ここで、ハッシュ関数の引数が２以上ありこれらの引数をカンマ「，」で区切った場合には、これらの引数を所定の順序でビット結合したビット列をそのハッシュ関数に入力することを意味する。すなわち、例えば、情報共有装置Ａにおいて計算されるＧ（ｒ’１Ａ，ｓｋ１Ａ）＝Ｇ（ｒ’１Ａ||ｓｋ１Ａ）である。また、ビット結合する引数の順序は、各ハッシュ関数において同じであるとする。すなわち、情報共有装置Ａ及び情報共有装置Ｂにおいて、ビット結合をする所定の順序は同じである。つまり、この場合、情報共有装置Ｂにおいて計算されるＧ（ｒ’１Ｂ，ｓｋ１Ｂ）は、Ｇ（ｒ’１Ｂ||ｓｋ１Ｂ）となる。これは、ハッシュ関数Ｈについても同様である。
【００６５】
例えば図１に破線で示したマスタ鍵生成装置３が、ｒ∈｛０，１｝ｋをランダムに選択し、マスタ鍵生成ＫｅｙＧｅｎ（ｒ）→（ｍｓｋ１，ｍｐｋ１）を行い、ｍｓｋ１をマスタ秘密鍵として秘密に保持し、ｍｐｋ１をマスタ公開鍵として公開する。
【００６６】
＜鍵導出＞
例えば図１に破線で示した鍵導出装置４が、ｉ＝Ａ，Ｂとして、情報共有装置ｉの識別子ＩＤ１ｉ∈｛０，１｝＊に対して、ＫｅｙＤｅｒ（ｍｓｋ１，ｍｐｋ１，ＩＤ１ｉ）→ｓｋ１ｉを計算し、長期秘密鍵ｓｋ１ｉを情報共有装置ｉに秘密裡に送付する。鍵導出装置４は、マスタ鍵生成装置３であってもよい。
【００６７】
＜情報交換＞
識別子ＩＤ１Ａ及び長期秘密鍵ｓｋ１Ａを持つ情報共有装置Ａと、識別子ＩＤ１Ｂ及び長期秘密鍵ｓｋ１Ｂを持つ情報共有装置Ｂとは、以下のようにして交換情報を交換して、情報Ｋを共有する。
【００６８】
１．情報共有装置Ａの処理
情報共有装置Ａは、第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋをランダムに選び、Ｇ（ｒ’１Ａ，ｓｋ１Ａ）＝ｒ１Ａ∈｛０，１｝ｋを計算する。
情報共有装置Ａは、ＥｎＣａｐ（ｍｐｋ１，ＩＤ１Ｂ，ｒ１Ａ）→（Ｃ１Ａ，Ｋ１Ａ）を計算し、ＫｅｙＧｅｎ（ｒ２Ａ）→（ｍｓｋ２Ａ，ｍｐｋ２Ａ）を計算する。
情報共有装置Ａは、識別子ＩＤ２Ａ∈｛０，１｝＊をランダムに選ぶ。
情報共有装置Ａは、ＫｅｙＤｅｒ（ｍｓｋ２Ａ，ｍｐｋ２Ａ，ＩＤ２Ａ）→ｓｋ２Ａを計算する。
情報共有装置Ａは、（Ｃ１Ａ，ｍｐｋ２Ａ，ＩＤ２Ａ）を情報共有装置Ｂに送信する。
【００６９】
２．情報共有装置Ｂの処理
情報共有装置Ｂは、（Ｃ１Ａ，ｍｐｋ２Ａ，ＩＤ２Ａ）を受信する。
情報共有装置Ｂは、短期秘密鍵ｒ’１Ｂ，ｒ２Ｂ∈｛０，１｝ｋをランダムに選び、Ｇ（ｒ’１Ｂ，ｓｋ１Ｂ）＝ｒ１Ｂ∈｛０，１｝ｋを計算する。
情報共有装置Ｂは、ＥｎＣａｐ（ｍｐｋ１Ａ，ＩＤ１Ａ，ｒ１Ｂ）→（Ｃ１Ｂ，Ｋ１Ｂ）を計算し、ＥｎＣａｐ（ｍｐｋ２Ａ，ＩＤ２Ａ，ｒ２Ｂ）→（Ｃ２Ｂ，Ｋ２Ｂ）を計算する。
情報共有装置Ｂは、（Ｃ１Ｂ，Ｃ２Ｂ）を情報共有装置Ａに送信する。
情報共有装置Ｂは、ＤｅＣａｐ（ｍｐｋ１Ｂ，ＩＤ１Ｂ，ｓｋ１Ｂ，Ｃ１Ａ）→Ｋ１Ａを計算する。
情報共有装置Ｂは、共有情報Ｋ＝Ｈ（Ｋ１Ａ，Ｋ１Ｂ，Ｋ２Ｂ，ｓｉｄ），ｓｉｄ＝（ＩＤ１Ａ，ＩＤ１Ｂ，Ｃ１Ａ，ｍｐｋ２Ａ，ＩＤ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ）を計算する。共有情報Ｋは、例えば共有鍵として用いられる。
【００７０】
３．情報共有装置Ａの処理
情報共有装置Ａは、（Ｃ１Ｂ，Ｃ２Ｂ）を受信する。
情報共有装置Ａは、ＤｅＣａｐ（ｍｐｋ１Ａ，ＩＤ１Ａ，ｓｋ１Ａ，Ｃ１Ｂ）→Ｋ１Ｂを計算し、ＤｅＣａｐ（ｍｐｋ２Ａ，ＩＤ２Ａ，ｓｋ２Ａ，Ｃ２Ｂ）→Ｋ２Ｂを計算する。
情報共有装置Ａは、共有情報Ｋ＝Ｈ（Ｋ１Ａ，Ｋ１Ｂ，Ｋ２Ｂ，ｓｉｄ），ｓｉｄ＝（ＩＤ１Ａ，ＩＤ１Ｂ，Ｃ１Ａ，ｍｐｋ２Ａ，ＩＤ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ）を計算する。共有情報Ｋは、例えば共有鍵として用いられる。
【００７１】
＜装置＞
公開パラメータ及び情報交換の欄で示した処理は、例えば図１，図４，図５に示された情報共有装置Ａ及び情報共有装置Ｂにより実行される。
【００７２】
第三実施形態の情報共有システムは、情報共有装置Ａ及び情報共有装置Ｂに加えて、図１に破線で示されたマスタ鍵生成装置３及び鍵導出装置４を更に備える。
【００７３】
情報共有装置Ａは、図４に示すように、記憶部Ａ０、短期秘密鍵生成部Ａ３、合成秘密鍵生成部Ａ４、暗号化部Ａ５、鍵生成部Ａ６、送信部Ａ７、受信部Ａ８、第一復号部Ａ９、第二復号部Ａ１０、情報生成部Ａ１１、ＩＤ選択部Ａ１２、鍵導出部Ａ１３を例えば備える。
【００７４】
情報共有装置Ｂは、図５に示すように、記憶部Ｂ０、短期秘密鍵生成部Ｂ３、合成秘密鍵生成部Ｂ４、第一暗号化部Ｂ５、第二暗号化部Ｂ６、送信部Ｂ７、受信部Ｂ８、復号部Ｂ９、情報生成部Ｂ１０を例えば備える。
【００７５】
情報共有方法の処理の流れの例を図７に示す。
【００７６】
短期秘密鍵生成部Ａ３は、第一短期秘密鍵ｒ’１Ａ∈｛０，１｝ｋ及び第二短期秘密鍵ｒ２Ａ∈｛０，１｝ｋをランダムに選択する（ステップＳＡ３）。選択された第一短期秘密鍵ｒ’１Ａは、合成秘密鍵生成部Ａ４に送信される。選択された第二短期秘密鍵ｒ２Ａは、鍵生成部Ａ６に送信される。
【００７７】
合成秘密鍵生成部Ａ４は、第一短期秘密鍵ｒ’１Ａ及び第一長期秘密鍵ｓｋ１Ａを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする（ステップＳＡ４）。ここで、所定の合成鍵生成関数は、例えばハッシュ関数Ｇ（ｒ’１Ａ，ｓｋ１Ａ）である。合成秘密鍵ｒ１Ａは、暗号化部Ａ５に送信される。
【００７８】
暗号化部Ａ５は、マスタ公開鍵ｍｐｋ１、情報共有装置Ｂの識別子であるＩＤ１Ｂ∈｛０，１｝ｋ及び上記合成秘密鍵ｒ１Ａを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ａ及び第一共有情報Ｋ１Ａを生成する（ステップＳＡ５）。生成された第一交換情報Ｃ１Ａは、送信部Ａ７及び情報生成部Ａ１１に送信される。生成された第一共有情報Ｋ１Ａは、情報生成部Ａ１１に送信される。
【００７９】
鍵生成部Ａ６が、第二短期秘密鍵ｒ２Ａを用いて、所定の鍵生成アルゴリズムＫｅｙＧｅｎにより、秘密鍵ｍｓｋ２Ａ及び公開鍵ｍｐｋ２Ａを生成する（ステップＳＡ６）。生成された秘密鍵ｍｓｋ２Ａは、第二復号部Ａ１０及び鍵導出部Ａ１３に送信される。生成された公開鍵ｍｐｋ２Ａは、送信部Ａ７、第二復号部Ａ１０、情報生成部Ａ１１及び鍵導出部Ａ１３に送信される。
【００８０】
ＩＤ選択部Ａ１２は、情報共有装置Ａの第二の識別子であるＩＤ２Ａ∈｛０，１｝ｋを選択する（ステップＳＡ１２）。選択されたＩＤ２Ａは、送信部Ａ７及び鍵導出部Ａ１３に送信される。
【００８１】
鍵導出部Ａ１３は、秘密鍵ｍｓｋ２Ａ、公開鍵ｍｐｋ２Ａ及びＩＤ２Ａを用いて、所定の鍵導出アルゴリズムＫｅｙＤｅｒにより、第二長期秘密鍵ｓｋ２Ａを生成する（ステップＳＡ１３）。第二長期秘密鍵は、第二復号部Ａ１０に送信される。
【００８２】
送信部Ａ７は、第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ及びＩＤ２Ａを情報共有装置Ｂに送信する（ステップＳＡ７）。
【００８３】
受信部Ａ８は、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報共有装置Ｂから受信する（ステップＳＡ８）。第一交換情報Ｃ１Ｂは、第一復号部Ａ９及び情報生成部Ａ１１に送信される。第二交換情報Ｃ２Ｂは、第二復号部Ａ１０及び情報生成部Ａ１１に送信される。
【００８４】
第一復号部Ａ９は、マスタ公開鍵ｍｐｋ１、ＩＤ１Ａ、第一長期秘密鍵ｓｋ１Ａ及び第一交換情報Ｃ１Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ｂを生成する（ステップＳＡ９）。生成された第一共有情報Ｋ１Ｂは、情報生成部Ａ１１に送信される。
【００８５】
第二復号部Ａ１０は、公開鍵ｐｋ２Ａ、ＩＤ２Ａ、第二長期秘密鍵ｓｋ２Ａ及び第二交換情報Ｃ２Ｂを用いて、所定の復号化アルゴリズムＤｅＣａｐにより、第二共有情報Ｋ２Ｂを生成する（ステップＳＡ１０）。生成された第二共有情報Ｋ２Ｂは、情報生成部Ａ１１に送信される。
【００８６】
情報生成部Ａ１１は、第一共有情報Ｋ１Ａ、第一共有情報Ｋ１Ｂ、第二共有情報Ｋ２Ｂ、ＩＤ１Ａ、ＩＤ１Ｂ、第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ、ＩＤ２Ａ、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを所定の情報生成関数に入力したときの出力値を計算する（ステップＳＡ１１）。所定の情報生成関数は、例えばハッシュ関数Ｈである。この場合、情報生成部Ａ１１が計算する出力値は、Ｈ（Ｋ１Ａ，Ｋ１Ｂ，Ｋ２Ｂ，ＩＤ１Ａ，ＩＤ１Ｂ，Ｃ１Ａ，ｍｐｋ２Ａ，ＩＤ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ）となる。この出力値が、共有の対象となる共有情報Ｋとなる。
【００８７】
情報共有装置Ｂの受信部Ｂ８（図５）は、第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ及びＩＤ２Ａを受信する（ステップＳＢ８）。第一交換情報Ｃ１Ａは、復号部Ｂ９に送信される。公開鍵ｍｐｋ２Ａは、第二暗号化部Ｂ６に送信される。
【００８８】
短期秘密鍵生成部Ｂ３は、第一短期秘密鍵ｒ’１Ｂ∈｛０，１｝ｋ及び第二短期秘密鍵ｒ２Ｂ∈｛０，１｝ｋをランダムに選択する（ステップＳＢ３）。選択された第一短期秘密鍵ｒ’１Ｂは、合成秘密鍵生成部Ｂ４に送信される。選択された第二短期秘密鍵ｒ２Ｂは、第二暗号化部Ｂ６に送信される。
【００８９】
合成秘密鍵生成部Ｂ４は、第一短期秘密鍵ｒ’１Ｂ及び長期秘密鍵ｓｋ１Ｂを所定の合成鍵生成関数に入力したときの出力値を合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする（ステップＳＢ４）。ここで、所定の合成鍵生成関数は、例えばハッシュ関数Ｇ（ｒ’１Ｂ，ｓｋ１Ｂ）である。合成秘密鍵ｒ１Ｂは、第一暗号化部Ｂ５に送信される。
【００９０】
第一暗号化部Ｂ５は、マスタ公開鍵ｍｐｋ１、ＩＤ１Ａ及び合成秘密鍵ｒ１Ｂを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第一交換情報Ｃ１Ｂ及び第一共有情報Ｋ１Ｂを生成する（ステップＳＢ５）。生成された第一交換情報Ｃ１Ｂは、送信部Ｂ７及び情報生成部Ｂ１０に送信される。生成された第一共有情報Ｋ１Ｂは、情報生成部Ｂ１０に送信される。
【００９１】
第二暗号化部Ｂ６は、公開鍵ｍｐｋ２Ａ、ＩＤ２Ａ及び第二短期秘密鍵ｒ２Ｂｋを用いて、所定の暗号化アルゴリズムＥｎＣａｐにより、第二交換情報Ｃ２Ｂ及び第二共有情報Ｋ２Ｂを生成する（ステップＳＢ６）。生成された第二交換情報Ｃ２Ｂは、送信部Ｂ７及び情報生成部Ｂ１０に送信される。生成された第二共有情報Ｋ２Ｂは、情報生成部Ｂ１０に送信される。
【００９２】
送信部Ｂ７は、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報共有装置Ａに送信する（ステップＳＢ７）。
【００９３】
復号部Ｂ９は、マスタ公開鍵ｍｐｋ１、ＩＤ１Ｂ、第一長期秘密鍵ｓｋ１Ｂ及び第一交換情報Ｃ１Ａを用いて、復号化アルゴリズムＤｅＣａｐにより、第一共有情報Ｋ１Ａを生成する。生成された第一共有情報Ｋ１Ａは、情報生成部Ｂ１０に送信される。
【００９４】
情報生成部Ｂ１０は、第一共有情報Ｋ１Ａ、第一共有情報Ｋ１Ｂ、第二共有情報Ｋ２Ｂ、ＩＤ１Ａ、ＩＤ１Ｂ、第一交換情報Ｃ１Ａ、公開鍵ｍｐｋ２Ａ、ＩＤ２Ａ、第一交換情報Ｃ１Ｂ及び第二交換情報Ｃ２Ｂを情報生成関数に入力したときの出力値を計算する。この情報生成関数は、情報共有装置Ａの情報生成部Ａ１１が用いる情報生成関数と同じ関数であり、例えばハッシュ関数Ｈである。この場合、情報生成部Ｂ１０が計算する出力値は、Ｈ（Ｋ１Ａ，Ｋ１Ｂ，Ｋ２Ｂ，ＩＤ１Ａ，ＩＤ１Ｂ，Ｃ１Ａ，ｍｐｋ２Ａ，ＩＤ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ）となる。この出力値が、共有の対象となる共有情報Ｋとなる。
【００９５】
［第四実施形態］
第四実施形態は、以下の部分において第三実施形態と異なる。以下では、第三実施形態と異なる部分を中心に説明をし、第三実施形態と同様の部分については重複説明を省略する。
【００９６】
鍵導出装置４（図１）は、更に長期秘密鍵ｔＡ∈｛０，１｝ｋをランダムに生成する。生成された長期秘密鍵ｔＡは、情報共有装置Ａの合成秘密鍵生成部Ａ４に秘密裡に送信される。
【００９７】
また、ステップＳＡ３において、短期秘密鍵生成部Ａ３は、短期秘密鍵ｓ’１Ａ∈｛０，１｝ｋを更に生成する。生成された短期秘密鍵ｓ’１Ａ∈は、合成秘密鍵生成部Ａ４に送信される。
【００９８】
また、ステップＳＡ４において合成秘密鍵生成部Ａ４は、ＰＲＦ１（ｔＡ，ｒ’１Ａ）ｘｏｒＰＲＦ２（ｓ’１Ａ，ｔＡ）を計算して、合成秘密鍵ｒ１Ａ∈｛０，１｝ｋとする。ここで、ＰＲＦ１及びＰＲＦ２はｋ個のビットから構成されるビット列｛０，１｝ｋを出力する擬似ランダム関数、ｘｏｒはビットごとの排他的論理和である。すなわち、第四実施形態においては、合成秘密鍵生成部Ａ４が用いる合成鍵生成関数は、ＰＲＦ１（ｔＡ，ｒ’１Ａ）ｘｏｒＰＲＦ２（ｓ’１Ａ，ｔＡ）となる。擬似ランダム関数は、例えば第一引数を鍵として用いる。
【００９９】
また、鍵導出装置４は、更に長期秘密鍵ｔＢ∈｛０，１｝ｋをランダムに生成する。生成された長期秘密鍵ｔＢは、情報共有装置Ｂの合成秘密鍵生成部Ｂ４に秘密裡に送信される。
【０１００】
また、ステップＳＢ３において、短期秘密鍵生成部Ｂ３は、短期秘密鍵ｓ’１Ｂ∈｛０，１｝ｋを更に生成する。生成された短期秘密鍵ｓ’１Ｂ∈は、合成秘密鍵生成部Ｂ４に送信される。
【０１０１】
また、ステップＳＢ４において合成秘密鍵生成部Ｂ４は、ＰＲＦ１（ｔＢ，ｒ’１Ｂ）ｘｏｒＰＲＦ２（ｓ’１Ｂ，ｔＢ）を計算して、合成秘密鍵ｒ１Ｂ∈｛０，１｝ｋとする。すなわち、第四実施形態においては、合成秘密鍵生成部Ｂ４が用いる合成鍵生成関数は、ＰＲＦ１（ｔＢ，ｒ’１Ｂ）ｘｏｒＰＲＦ２（ｓ’１Ｂ，ｔＢ）となる。
【０１０２】
さらに、ステップＳＡ１１及びステップＳＢ１０において、情報生成部Ａ１１及び情報生成部Ｂ１０が用いる情報生成関数は、ＰＲＦ３（Ｌ１Ａ，ｓｉｄ）ｘｏｒＰＲＦ３（Ｌ１Ｂ，ｓｉｄ）ｘｏｒＰＲＦ３（Ｌ２Ｂ，ｓｉｄ）である。ここで、Ｅｘｔはランダムネスエクストラクタ、ＰＲＦ３は擬似ランダム関数、ｓｉｄ＝｛ｐｋ１Ａ，ｐｋ１Ｂ，Ｃ１Ａ，ｐｋ２Ａ，Ｃ１Ｂ，Ｃ２Ｂ｝、Ｌ１Ａ＝Ｅｘｔ（Ｋ１Ａ）、Ｌ１Ｂ＝Ｅｘｔ（Ｋ１Ｂ）、Ｌ２Ｂ＝Ｅｘｔ（Ｋ２Ｂ）である。ランダムネスエクストラクタＥｘｔは、任意の分布の入力に対して一様の分布を持つ出力値を出力する関数である。
【０１０３】
このようにすることにより、第四実施形態では、ランダムオラクルモデルを仮定せずに安全性を示すことができる。
【０１０４】
［他の変形例］
情報共有装置Ａの各部間における情報のやり取りは、記憶部Ａ０を介して行われてもよい。同様に、情報共有装置Ｂの各部間における情報のやり取りは、記憶部Ｂ０を介して行われてもよい。
【０１０５】
情報共有装置Ａをコンピュータによって実現する場合、情報共有装置Ａの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、情報共有装置Ａの各部の処理機能がコンピュータ上で実現される。
【０１０６】
同様に、情報共有装置Ｂをコンピュータによって実現する場合、情報共有装置Ｂの各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、情報共有装置Ｂの各部の処理機能がコンピュータ上で実現される。
【０１０７】
これらのプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０８】
この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【０１０９】
３      マスタ鍵生成装置
４      鍵導出装置
Ａ      情報共有装置
Ａ０    記憶部
Ａ１    乱数生成部
Ａ２    長期鍵生成部
Ａ３    短期秘密鍵生成部
Ａ４    合成秘密鍵生成部
Ａ５    暗号化部
Ａ６    鍵生成部
Ａ７    送信部
Ａ８    受信部
Ａ９    第一復号部
Ａ１０  第二復号部
Ａ１１  情報生成部
Ａ１２  ＩＤ選択部
Ａ１３  鍵導出部
Ｂ      情報共有装置
Ｂ０    記憶部
Ｂ１    乱数生成部
Ｂ２    長期鍵生成部
Ｂ３    短期秘密鍵生成部
Ｂ４    合成秘密鍵生成部
Ｂ５    第一暗号化部
Ｂ６    第二暗号化部
Ｂ７    送信部
Ｂ８    受信部
Ｂ９    復号部
Ｂ１０  情報生成部
【図１】
0005506650.tif 000002
【図２】
0005506650.tif 000003
【図３】
0005506650.tif 000004
【図４】
0005506650.tif 000005
【図５】
0005506650.tif 000006
【図６】
0005506650.tif 000007
【図７】
0005506650.tif 000008