(57)【要約】【課題】従来の情報共有方式と同等の安全性を保ちつつ演算量がより小さい情報共有技術を提供する。【解決手段】第一情報共有装置の秘密情報生成部が第二情報共有装置から受信した交換情報Ｙ＝Ｇｙを用いて第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１及び第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２を生成する。第一情報共有装置の秘密情報合成部が第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する。第二情報共有装置の秘密情報生成部が第一情報共有装置から受信した交換情報Ｘ＝Ｇｘを用いて第一秘密情報Ｚ１＝（ＸＡ１）ｙ＋ｂ１及び第二秘密情報Ｚ２＝（ＸＡ２）ｙ＋ｂ２を生成する。第二情報共有装置の秘密情報合成部が第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する情報とする。【選択図】図４
2011061306.tif 000002
【特許請求の範囲】
【請求項１】
第一情報共有装置と第二情報共有装置との間で情報を共有する情報共有システムにおいて、
セキュリティパラメータｋを所定の正の整数とし、群＜Ｇ＞を生成元Ｇにより生成される巡回群とし、上記第一情報共有装置の秘密鍵ａ１，ａ２を２ｋビット以上の正の整数の乱数とし、上記第一情報共有装置の公開鍵Ａ１，Ａ２をＡ１＝Ｇａ１，Ａ２＝Ｇａ２とし、上記第二情報共有装置の秘密鍵ｂ１，ｂ２を２ｋビット以上の正の整数の乱数とし、上記第二情報共有装置の公開鍵Ｂ１，Ｂ２をＢ１＝Ｇｂ１，Ｂ２＝Ｇｂ２として、
上記第一情報共有装置は、
２ｋビット以上の正の整数の乱数ｘを生成する乱数生成部と、
上記乱数ｘを用いて交換情報Ｘ＝Ｇｘを生成する交換情報生成部と、
上記交換情報Ｘを上記第二情報共有装置に送信する送受信部と、
上記第二情報共有装置から受信した交換情報Ｙを用いて第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１及び第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２を生成する秘密情報生成部と、
上記第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する秘密情報合成部と、
を含み、
上記第二情報共有装置は、
２ｋビット以上の正の整数の乱数ｙを生成する乱数生成部と、
上記乱数ｙを用いて交換情報Ｙ＝Ｇｙを生成する交換情報生成部と、
上記交換情報Ｙを上記第一情報共有装置に送信する送受信部と、
上記第一情報共有装置から受信した交換情報Ｘを用いて第一秘密情報Ｚ１＝（ＸＡ１）ｙ＋ｂ１及び第二秘密情報Ｚ２＝（ＸＡ２）ｙ＋ｂ２を生成する秘密情報生成部と、
上記第一秘密情報Ｚ１及び上記第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する情報とする秘密情報合成部と、
を含む、
ことを特徴とする情報共有システム。
【請求項２】
請求項１に記載の情報共有システムにおいて、
上記第一情報共有装置の秘密情報生成部は第三秘密情報Ｚ３＝（ＹＢ１）ｙ＋ａ２及び第四秘密情報Ｚ４＝（ＹＢ２）ｙ＋ａ１を更に生成し、
上記第一情報共有装置の秘密情報合成部は、上記第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３及び第四秘密情報Ｚ４を予め定められた関数Ｈに入力した場合の出力値を計算し、
上記第二情報共有装置の秘密情報生成部は第三秘密情報Ｚ３＝（ＸＡ１）ｙ＋ｂ２及び第四秘密情報Ｚ４＝（ＸＡ２）ｙ＋ｂ１を更に生成し、
上記第二情報共有装置の秘密情報合成部は、上記第二情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３及び第四秘密情報Ｚ４を予め定められた関数Ｈに入力した場合の出力値を計算する、
ことを特徴とする情報共有システム。
【請求項３】
請求項１に記載の情報共有システムにおいて、
所定のビット列ＩＤＡを上記第一情報共有装置の識別子とし、所定のビット列ＩＤＢを上記第二情報共有装置の識別子として、
上記関数Ｈは、上記第一秘密情報Ｚ１、上記第二秘密情報Ｚ２、上記交換情報Ｘ、上記交換情報Ｙ、上記識別子ＩＤＡ及び上記識別子ＩＤＢを入力とするハッシュ関数であり、
上記第一情報共有装置の秘密情報合成部は、上記第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１、第二秘密情報Ｚ２、上記交換情報Ｘ、上記交換情報Ｙ、上記識別子ＩＤＡ及び上記識別子ＩＤＢを上記関数Ｈに入力した場合の出力値を計算する、
ことを特徴とする情報共有システム。
【請求項４】
請求項２に記載の情報共有システムにおいて、
所定のビット列ＩＤＡを上記第一情報共有装置の識別子とし、所定のビット列ＩＤＢを上記第二情報共有装置の識別子として、
上記関数Ｈは、上記第一秘密情報Ｚ１、上記第二秘密情報Ｚ２、上記第三秘密情報Ｚ３、上記第四秘密情報Ｚ４、上記交換情報Ｘ、上記交換情報Ｙ、上記識別子ＩＤＡ及び上記識別子ＩＤＢを入力とするハッシュ関数であり、
上記第一情報共有装置の秘密情報合成部は、上記第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３、第四秘密情報Ｚ４、上記交換情報Ｘ、上記交換情報Ｙ、上記識別子ＩＤＡ及び上記識別子ＩＤＢを上記関数Ｈに入力した場合の出力値を計算する、
ことを特徴とする情報共有システム。
【請求項５】
請求項２又は４に記載の情報共有システムにおいて、
上記第一情報共有装置の秘密情報生成部と上記第二情報共有装置の秘密情報生成部との少なくとも一方は、既に行った同じ底のべき乗算についての途中計算結果を再利用する、
ことを特徴とする情報共有システム。
【請求項６】
第一情報共有装置と第二情報共有装置との間で情報を共有する情報共有方法において、
セキュリティパラメータｋを所定の正の整数とし、群＜Ｇ＞を生成元Ｇにより生成される巡回群とし、上記第一情報共有装置の秘密鍵ａ１，ａ２を２ｋビット以上の正の整数の乱数とし、上記第一情報共有装置の公開鍵Ａ１，Ａ２をＡ１＝Ｇａ１，Ａ２＝Ｇａ２とし、上記第二情報共有装置の秘密鍵ｂ１，ｂ２を２ｋビット以上の正の整数の乱数とし、上記第二情報共有装置の公開鍵Ｂ１，Ｂ２をＢ１＝Ｇｂ１，Ｂ２＝Ｇｂ２として、
上記第一情報共有装置の乱数生成部が、２ｋビット以上の正の整数の乱数ｘを生成する乱数生成ステップと、
上記第一情報共有装置の交換情報生成部が、上記乱数ｘを用いて交換情報Ｘ＝Ｇｘを生成する交換情報生成ステップと、
上記第一情報共有装置の送受信部が、上記交換情報Ｘを上記第二情報共有装置に送信する送受信ステップと、
上記第一情報共有装置の秘密情報生成部が、上記第二情報共有装置から受信した交換情報Ｙを用いて第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１及び第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２を生成する秘密情報生成ステップと、
上記第一情報共有装置の秘密情報合成部が、上記第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する秘密情報合成ステップと、
上記第二情報共有装置の乱数生成部が、２ｋビット以上の正の整数の乱数ｙを生成する乱数生成ステップと、
上記第二情報共有装置の交換情報生成部が、上記乱数ｙを用いて交換情報Ｙ＝Ｇｙを生成する交換情報生成ステップと、
上記第二情報共有装置の送受信部が、上記交換情報Ｙを上記第一情報共有装置に送信する送受信ステップと、
上記第二情報共有装置の秘密情報生成部が、上記第一情報共有装置から受信した交換情報Ｘを用いて第一秘密情報Ｚ１＝（ＸＡ１）ｙ＋ｂ１及び第二秘密情報Ｚ２＝（ＸＡ２）ｙ＋ｂ２を生成する秘密情報生成ステップと、
上記第二情報共有装置の秘密情報合成部が、上記第一秘密情報Ｚ１及び上記第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する情報とする秘密情報合成ステップと、
を含むことを特徴とする情報共有方法。
【請求項７】
請求項６に記載の情報共有方法において、
上記第一情報共有装置の秘密情報生成ステップは、第三秘密情報Ｚ３＝（ＹＢ１）ｙ＋ａ２及び第四秘密情報Ｚ４＝（ＹＢ２）ｙ＋ａ１を更に生成し、
上記第一情報共有装置の秘密情報合成ステップは、上記第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３及び第四秘密情報Ｚ４を予め定められた関数Ｈに入力した場合の出力値を計算し、
上記第二情報共有装置の秘密情報生成ステップは、第三秘密情報Ｚ３＝（ＸＡ１）ｙ＋ｂ２及び第四秘密情報Ｚ４＝（ＸＡ２）ｙ＋ｂ１を更に生成し、
上記第二情報共有装置の秘密情報合成ステップは、上記第二情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３及び第四秘密情報Ｚ４を予め定められた関数Ｈに入力した場合の出力値を計算する、
ことを特徴とする情報共有方法。
【請求項８】
請求項７に記載の情報共有方法において、
上記第一情報共有装置の秘密情報生成ステップと上記第二情報共有装置の秘密情報生成ステップとの少なくとも一方は、既に行った同じ底のべき乗算についての途中計算結果を再利用する、
ことを特徴とする情報共有方法。
【請求項９】
第一情報共有装置と第二情報共有装置との間で情報を共有する第一情報共有装置としてコンピュータを機能させるための情報共有プログラムにおいて、
セキュリティパラメータｋを所定の正の整数とし、群＜Ｇ＞を生成元Ｇにより生成される巡回群とし、上記第一情報共有装置の秘密鍵ａ１，ａ２を２ｋビット以上の正の整数の乱数とし、上記第一情報共有装置の公開鍵Ａ１，Ａ２をＡ１＝Ｇａ１，Ａ２＝Ｇａ２とし、上記第二情報共有装置の秘密鍵ｂ１，ｂ２を２ｋビット以上の正の整数の乱数とし、上記第二情報共有装置の公開鍵Ｂ１，Ｂ２をＢ１＝Ｇｂ１，Ｂ２＝Ｇｂ２として、
上記第一情報共有装置は、
２ｋビット以上の正の整数の乱数ｘを生成する乱数生成部と、
上記乱数ｘを用いて交換情報Ｘ＝Ｇｘを生成する交換情報生成部と、
上記交換情報Ｘを上記第二情報共有装置に送信する送受信部と、
上記第二情報共有装置から受信した交換情報Ｙ＝Ｇｙ（ｙは乱数）を用いて第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１及び第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２を生成する秘密情報生成部と、
上記第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する秘密情報合成部と、
を含む、
ことを特徴とする情報共有プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号技術に関し、特に２つのエンティティ間で秘密鍵等の情報を共有する技術に関する。
【背景技術】
【０００２】
中間者攻撃に対して安全であり、ギャップＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題の困難性を仮定して安全性を証明可能である情報共有方式として、ＮＡＸＯＳ方式が知られている（例えば、非特許文献１参照。）。ＮＡＸＯＳ方式では、各情報共有装置は、群のべき乗算を４回行っていた。
【０００３】
また、中間者攻撃に対して安全で、かつ、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題の困難性を仮定して安全性を証明可能でありＮＡＸＯＳ方式よりも安全性が高い情報共有方式として、ＮＡＸＯＳ＋方式が知られている（例えば、非特許文献２参照。）。ＮＡＸＯＳ＋方式では、各情報共有装置は、群のべき乗算を５回行っていた。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】B. LaMacchia, K. Lauter, A. Mityagin, “Stronger Security of Authenticated Key Exchange”, ProveSec 2007, LNCS 4784, Springer Berlin, 2007
【非特許文献２】J. Lee, J. Park, “Authenticated Key Exchange Secure underthe Computational Diffie-Hellman Assumption”, Preprint, http://eprint.iacr.org/2008/344/
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来の情報共有方式は、中間者攻撃に対して安全であるが、演算量が大きいという課題がった。
【０００６】
この発明は、従来の情報共有方式と同等の安全性を保ちつつ演算量がより小さい情報共有システム、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
第一情報共有装置と第二情報共有装置との間で情報を共有する情報共有するために、セキュリティパラメータｋを所定の正の整数とし、群＜Ｇ＞を生成元Ｇにより生成される巡回群とし、第一情報共有装置の秘密鍵ａ１，ａ２を２ｋビット以上の正の整数の乱数とし、第一情報共有装置の公開鍵Ａ１，Ａ２をＡ１＝Ｇａ１，Ａ２＝Ｇａ２として、第二情報共有装置の秘密鍵ｂ１，ｂ２を２ｋビット以上の正の整数の乱数とし、第二情報共有装置の公開鍵Ｂ１，Ｂ２をＢ１＝Ｇｂ１，Ｂ２＝Ｇｂ２として、第一情報共有装置の乱数生成部が２ｋビット以上の正の整数の乱数ｘを生成する。第一情報共有装置の交換情報生成部が乱数ｘを用いて交換情報Ｘ＝Ｇｘを生成する。第一情報共有装置の送受信部が交換情報Ｘを第二情報共有装置に送信する。第一情報共有装置の秘密情報生成部が第二情報共有装置から受信した交換情報Ｙを用いて第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１及び第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２を生成する。第一情報共有装置の秘密情報合成部が第一情報共有装置の秘密情報生成部が生成した第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する。第二情報共有装置の乱数生成部が２ｋビット以上の正の整数の乱数ｙを生成する。第二情報共有装置の交換情報生成部が乱数ｙを用いて交換情報Ｙ＝Ｇｙを生成する。第二情報共有装置の送受信部が交換情報Ｙを第一情報共有装置に送信する。第二情報共有装置の秘密情報生成部が第一情報共有装置から受信した交換情報Ｘを用いて第一秘密情報Ｚ１＝（ＸＡ１）ｙ＋ｂ１及び第二秘密情報Ｚ２＝（ＸＡ２）ｙ＋ｂ２を生成する。第二情報共有装置の秘密情報合成部が第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算する情報とする。
【発明の効果】
【０００８】
第一情報共有装置及び第二情報共有装置のそれぞれが行うべき乗算の回数は、従来の情報共有方式におけるべき乗算の回数以下となるか、従来とべき乗算の回数が同じ場合にはべき乗算１回あたりの平均演算量を従来の情報共有方式よりも小さくすることができる。したがって、情報共有のための演算量が小さくなる。
【図面の簡単な説明】
【０００９】
【図１】情報共有システムの例の機能ブロック図。
【図２】第一情報共有装置の例の機能ブロック図。
【図３】第二情報共有装置の例の機能ブロック図。
【図４】第一実施形態の情報共有方法の例の流れ図。
【図５】第二実施形態の情報共有方法の例の流れ図。
【図６】バイナリ法によるべき乗算の流れ図。
【発明を実施するための形態】
【００１０】
以下、この発明の実施形態を詳細に説明する。
【００１１】
［第一実施形態］
この発明による情報共有システム及び方法は、図１に例示する第一情報共有装置Ａと第二情報共有装置Ｂとの間で情報Ｋを共有するものである。第一情報共有装置Ａと第二情報共有装置とは、通信内容の秘密が保たれるとは限らない通信路により接続されている。
【００１２】
第一情報共有装置Ａには任意のビット列である識別子ＩＤＡが与えられており、第二情報共有装置Ｂには任意のビット列である識別子ＩＤＢが与えられており、第一情報共有装置Ａ及び第二情報共有装置Ｂは互いの識別子を知っているとする。
【００１３】
セキュリティパラメータｋは、求めるセキュリティレベルに応じて適宜設定される正の整数である。群＜Ｇ＞は、Ｄｉｆｆｅ−Ｈｅｌｌｍａｎ問題が困難な巡回群で、生成元Ｇにより生成されるものとする。例えば楕円エルガマル暗号で用いられる群が好適である。Ｈは、所定の関数である。例えばＳＨＡ−２５６等のハッシュ関数である。
【００１４】
図２は第一情報共有装置Ａの例の機能ブロック図であり、図３は第二情報共有装置Ｂの例の機能ブロック図である。図４はこの実施形態の情報共有方法の処理の流れを示す図である。
【００１５】
まず、第一情報共有装置Ａは秘密鍵（ａ１，ａ２）及び公開鍵（Ａ１，Ａ２）を生成し（ステップａ１からステップａ３）、第二情報共有装置Ｂは秘密鍵（ｂ１，ｂ２）及び公開鍵（Ｂ１，Ｂ２）を生成する（ステップｂ１からステップｂ３）。これらのステップａ１からステップａ３、ステップｂ１からステップｂ３は、情報共有を行うための準備として事前に行っておく。
【００１６】
第一情報共有装置Ａの乱数生成部１２は、２ｋビット以上の乱数ａ１，ａ２を生成する（ステップａ１）。これらの乱数ａ１，ａ２は、第一情報共有装置Ａの秘密鍵であり、第一情報共有装置Ａの外部に漏れないように秘密に管理される。
【００１７】
公開鍵生成部１３は、乱数ａ１，ａ２を用いて、Ａ１＝Ｇａ１，Ａ２＝Ｇａ２で定義される公開鍵Ａ１，Ａ２を生成する（ステップａ２）。
【００１８】
送受信部１４は、公開鍵（Ａ１，Ａ２）を第二情報共有装置Ｂに送信する（ステップａ３）。
【００１９】
第二情報共有装置Ｂの乱数生成部２２は、２ｋビット以上の乱数ｂ１，ｂ２を生成する（ステップｂ１）。これらの乱数ｂ１，ｂ２は、第二情報共有装置Ｂの秘密鍵であり、第二情報共有装置Ｂの外部に漏れないように秘密に管理される。
【００２０】
公開鍵生成部２３は、乱数ｂ１，ｂ２を用いて、Ｂ１＝Ｇｂ１，Ｂ２＝Ｇｂ２で定義される公開鍵Ｂ１，Ｂ２を生成する（ステップｂ２）。
【００２１】
送受信部２４は、公開鍵（Ｂ１，Ｂ２）を第二情報共有装置Ａに送信する（ステップｂ３）。
【００２２】
第一情報共有装置Ａ及び第二情報共有装置Ｂは情報Ｋを共有するために、以下のステップＡ１からＡ６、Ｂ１からＢ６の処理を行う。
【００２３】
第一情報共有装置Ａの乱数生成部１２は、２ｋビット以上の乱数ｘを生成する（ステップＡ１）。生成された乱数ｘは、交換情報生成部１５及び秘密情報生成部１６に送られる。
【００２４】
交換情報生成部１５は、Ｘ＝Ｇｘで定義される交換情報Ｘを生成する（ステップＡ２）。生成された交換情報Ｘは、送受信部１４に送られる。
【００２５】
送受信部１４は、交換情報Ｘを第二情報共有装置Ｂに送信する（ステップＡ３）。第二情報共有装置Ｂの送受信部２４は、送られてきた交換情報Ｘが群＜Ｇ＞の元であるかどうかを判断し、群＜Ｇ＞の元でない場合には、情報Ｋを共有するための手続きを中止する。
【００２６】
第二情報共有装置Ｂの乱数生成部２２は、２ｋビット以上の乱数ｙを生成する（ステップＢ１）。生成された乱数ｙは、交換情報生成部２５及び秘密情報生成部２６に送られる。
【００２７】
交換情報生成部２５は、Ｙ＝Ｇｙで定義される交換情報Ｙを生成する（ステップＢ２）。生成された交換情報Ｙは、送受信部２４に送られる。
【００２８】
送受信部２４は、交換情報Ｙを第一情報共有装置Ａに送信する（ステップＢ３）。第一情報共有装置Ａは、送られてきた交換情報Ｙが群＜Ｇ＞の元であるかどうかを判断し、群＜Ｇ＞の元でない場合には、情報Ｋを共有するための手続きを中止する。
【００２９】
第一情報共有装置Ａの秘密情報生成部１６は、交換情報Ｙを用いてＺ１＝（ＹＢ１）ｘ＋ａ１で定義される第一秘密情報Ｚ１を生成する（ステップＡ４）。また、秘密情報生成部１６は、交換情報Ｙを用いてＺ２＝（ＹＢ２）ｘ＋ａ２で定義される第二秘密情報Ｚ２を生成する（ステップＡ５）。生成された第一秘密情報Ｚ１及び第二秘密情報Ｚ２は、秘密情報合成部１７に送られる。
【００３０】
秘密情報合成部１７は、第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算して、共有情報Ｋとする（ステップＡ６）。関数Ｈは、例えば第一秘密情報Ｚ１、第二秘密情報Ｚ２、交換情報Ｘ、交換情報Ｙ、識別子ＩＤＡ及び識別子ＩＤＢを入力とするハッシュ関数Ｈ（Ｚ１，Ｚ２，Ｘ，Ｙ，ＩＤＡ，ＩＤＢ）である。
【００３１】
第二情報共有装置Ｂの秘密情報生成部２６は、交換情報Ｘを用いてＺ１＝（ＸＡ１）ｙ＋ｂ１で定義される第一秘密情報Ｚ１を生成する（ステップＢ４）。また、秘密情報生成部２６は、交換情報Ｘを用いてＺ２＝（ＸＡ２）ｙ＋ｂ２で定義される第二秘密情報Ｚ２を生成する（ステップＢ５）。生成された第一秘密情報Ｚ１及び第二秘密情報Ｚ２は、秘密情報合成部２７に送られる。
【００３２】
秘密情報合成部２７は、第一秘密情報Ｚ１及び第二秘密情報Ｚ２を予め定められた関数Ｈに入力した場合の出力値を計算して、共有される情報Ｋとする（ステップＡ６）。関数Ｈは、例えば第一秘密情報Ｚ１、第二秘密情報Ｚ２、交換情報Ｘ、交換情報Ｙ、識別子ＩＤＡ及び識別子ＩＤＢを入力とするハッシュ関数Ｈ（Ｚ１，Ｚ２，Ｘ，Ｙ，ＩＤＡ，ＩＤＢ）である。第二情報共有装置Ｂの関数Ｈとして、第一情報共有装置Ａの関数Ｈと同じ関数を用いる。
【００３３】
第一情報共有装置Ａが生成する第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１と、第二情報共有装置Ｂが生成する第一秘密情報Ｚ１＝（ＸＡ１）ｙ＋ｂ１とは一致する。（ＹＢ１）ｘ＋ａ１＝（ＧｙＧｂ１）ｘ＋ａ１＝Ｇ（ｙ＋ｂ１）（ｘ＋ａ１）＝（ＧｘＧａ１）ｙ＋ｂ１＝（ＸＡ１）ｙ＋ｂ１であるためである。同様に、第一情報共有装置Ａが生成する第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２と、第二情報共有装置Ｂが生成する第二秘密情報Ｚ２＝（ＸＡ２）ｙ＋ｂ２とは一致する。このため、第一情報共有装置Ａが生成する情報Ｋと第二情報共有装置Ｂが生成する情報Ｋとは一致する。
【００３４】
第一実施形態の第一情報共有装置Ａ及び第二情報共有装置Ｂのそれぞれは群＜Ｇ＞のべき乗算を３回するだけで、情報Ｋを共有することができる。第一情報共有装置Ａを例に挙げて説明すると、第一情報共有装置Ａは、（１）交換情報Ｘ＝Ｇｘの計算（ステップＡ２）、（２）第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１の計算（ステップＡ４）、（３）第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２の計算（ステップＡ５）の３回のべき乗算をするだけで、情報Ｋを共有することができる。
【００３５】
このように、第一実施形態によれば、第一情報共有装置Ａ及び第二情報共有装置Ｂのそれぞれが行うべき乗算の回数（３回）は、従来の情報共有方式におけるべき乗算の回数（４回）以下となり、情報共有のための演算量が小さい。
【００３６】
なお、証明は省略するが、第一実施形態の情報共有システム及び情報共有方法の安全性は、ギャップＤｉｆｆｉｅ−Ｈｅｌｌｍａｎｎ問題の困難性を仮定して説明することができる。すなわち、第一実施形態の情報共有システムの安全性は、ＮＡＸＯＳ方式の安全性と同等である。
【００３７】
［第二実施形態］
第二実施形態の情報共有システム及び方法は、中間者攻撃に対して安全で、かつ、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題の困難性を仮定して安全性を証明可能であり第一実施形態よりも安全性が高く、ＮＡＸＯＳ＋方式と同等の安全性を保ちつつ演算量がより小さい情報共有システム、方法を提供するものである。以下、第一実施形態と異なる部分を説明し、同様の部分については重複説明を省略する。
【００３８】
第二実施形態の第一情報共有装置Ａ及び第二情報共有装置Ｂの機能ブロックは図２、図３に例示した第一実施形態の第一情報共有装置Ａ及び第二情報共有装置Ｂの機能ブロックと同じであるが、後述するように秘密情報生成部１６，２６、秘密情報合成部１７，２７の機能が異なる。
【００３９】
図５に、第二実施形態の情報共有方法の処理の流れを例示する。第一情報共有装置Ａは、第一実施形態と同様にステップａ１からステップａ３、ステップＡ１からＡ５の処理を行った後に、ステップＡ７及びステップＡ８の処理を行う。
【００４０】
すなわち、第一情報共有装置Ａの秘密情報生成部１６は、第一秘密情報Ｚ１及び第二秘密情報Ｚ２を生成すると共に、Ｚ３＝（ＹＢ１）ｘ＋ａ２で定義される第三秘密情報Ｚ３を生成し（ステップＡ７）、Ｚ４＝（ＹＢ２）ｘ＋ａ１で定義される第四秘密情報Ｚ４を生成する（ステップＡ８）。生成された第三秘密情報Ｚ３及び第四秘密情報Ｚ４は、秘密情報合成部１７に送られる。
【００４１】
秘密情報合成部１７は、第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３及び第四秘密情報Ｚ４を予め定められた関数Ｈに入力した場合の出力値を計算して、共有される情報Ｋとする（ステップＡ６）。関数Ｈは、例えば第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３、第四秘密情報Ｚ４、交換情報Ｘ、交換情報Ｙ、識別子ＩＤＡ及び識別子ＩＤＢを入力とするハッシュ関数Ｈ（Ｚ１，Ｚ２，Ｚ３，Ｚ４，Ｘ，Ｙ，ＩＤＡ，ＩＤＢ）である。
【００４２】
また、第二情報共有装置Ｂの秘密情報生成部２６は、第一秘密情報Ｚ１及び第二秘密情報Ｚ２を生成すると共に、Ｚ３＝（ＸＡ１）ｘ＋ｂ２で定義される第三秘密情報Ｚ３を生成し（ステップＢ７）、Ｚ４＝（ＸＡ２）ｘ＋ｂ１で定義される第四秘密情報Ｚ４を生成する（ステップＢ８）。生成された第三秘密情報Ｚ３及び第四秘密情報Ｚ４は、秘密情報合成部１７に送られる。
【００４３】
秘密情報合成部２７は、第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３及び第四秘密情報Ｚ４を予め定められた関数Ｈに入力した場合の出力値を計算して、共有される情報Ｋとする（ステップＢ６）。関数Ｈは、例えば第一秘密情報Ｚ１、第二秘密情報Ｚ２、第三秘密情報Ｚ３、第四秘密情報Ｚ４、交換情報Ｘ、交換情報Ｙ、識別子ＩＤＡ及び識別子ＩＤＢを入力とするハッシュ関数Ｈ（Ｚ１，Ｚ２，Ｚ３，Ｚ４，Ｘ，Ｙ，ＩＤＡ，ＩＤＢ）である。第二情報共有装置Ｂの関数Ｈとして、第一情報共有装置Ａの関数Ｈと同じ関数を用いる。
【００４４】
第二実施形態の第二情報共有装置Ａ及び第二情報共有装置Ｂのそれぞれは群＜Ｇ＞のべき乗算を５回するだけで、情報Ｋを共有することができる。第一情報共有装置Ａを例に挙げて説明すると、第一情報共有装置Ａは、（１）交換情報Ｘ＝Ｇｘの計算（ステップＡ２）、（２）第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１の計算（ステップＡ４）、（３）第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２の計算（ステップＡ５）、（４）第三秘密情報Ｚ３＝（ＹＢ１）ｙ＋ａ２の計算（ステップＡ７）、（５）第四秘密情報Ｚ４＝（ＹＢ２）ｙ＋ａ１の計算（ステップＡ８）の５回のべき乗算をして、情報Ｋを共有することができる。
【００４５】
第二実施形態のべき乗算の回数（５回）は、従来のＮＡＸＯＳ＋方式のべき乗算の回数（５回）と同じであるが、べき乗算１回あたりの平均演算量を従来のＮＡＸＯＳ＋方式よりも小さくすることができる。
【００４６】
具体的には、第二情報共有装置Ａ及び第二情報共有装置Ｂのそれぞれは、べき乗算をする際に既に行った同じ底のべき乗算についての途中計算結果を再利用することで、重複計算を省いてべき乗算１回あたりの平均演算量を小さくすることができる。
【００４７】
第一情報共有装置Ａを例に挙げて説明をすると、第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１と第三秘密情報Ｚ３＝（ＹＢ１）ｙ＋ａ２を計算するときに底がＹＢ１で共通しており、第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２と第四秘密情報Ｚ４＝（ＹＢ２）ｙ＋ａ１を計算するときに底がＹＢ２で共通している。したがって、第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１のべき乗算が既に行われている場合には、第三秘密情報Ｚ３＝（ＹＢ１）ｙ＋ａ２を計算するときに、第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１のべき乗算についての途中計算結果を再利用することで、第三秘密情報Ｚ３＝（ＹＢ１）ｙ＋ａ２の演算量を削減することができる。また、第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２のべき乗算が既に行われている場合には、第四秘密情報Ｚ４＝（ＹＢ２）ｙ＋ａ１を計算するときに、第二秘密情報Ｚ２＝（ＹＢ２）ｘ＋ａ２のべき乗算についての途中計算結果を再利用することで、第四秘密情報Ｚ４＝（ＹＢ２）ｙ＋ａ１の演算量を削減することができる。
【００４８】
以下、バイナリ法によりべき乗算をする場合の途中計算結果の再利用について説明をする。バイナリ法により底Ｑのｓ（＝ｓＩｓＩ−１…ｓ０）乗のべき乗算をする場合には、図６の流れ図の処理を行う。ｓＩｓＩ−１…ｓ０は整数ｓを二進数で表現したものであり、各ｓｉ（ｉ＝Ｉ，…，０）は０又は１である。
【００４９】
まず、ＲにＱを代入し、Ｔに１を代入し、ｉに０を代入して、各変数の初期化を行う（ステップＳ１）。
【００５０】
ｓｉが１であるかどうかを判断して（ステップＳ２）、ｓｉが１であればＴ×Ｒを演算してＴに代入する（ステップＳ３）。ｓｉが１でなければ、ステップＳ３の処理を行わずに、ステップＳ４の処理を行う。×は群＜Ｇ＞で定義された演算である。
【００５１】
Ｒ×Ｒを演算してＲに代入する（ステップＳ４）
ｉがＩであるかどうかを判断して（ステップＳ５）、ｉがＩであれば処理を終了する。Ｔが底Ｑのｓ（＝ｓＩｓＩ−１…ｓ０）乗のべき乗算の演算結果である。ｉがＩでなければ、ｉを１だけインクリメントして（ステップＳ６）、すなわちｉにｉ＋１を代入して、ステップＳ２に戻る。
【００５２】
第一情報共有装置Ａの秘密情報生成部１６が図６に例示したバイナリ法によりべき乗算を行う場合には、ステップＳ４のＲ×Ｒの計算結果を再利用することができる。ステップＳ４のＲ×Ｒの計算は、底Ｑのみに依存して指数ｓＩ…ｓ０に依存せず、底Ｑが同一であればＲ×Ｒの計算結果は同じであるためである。秘密情報生成部１６は、例えば、第一秘密情報Ｚ１＝（ＹＢ１）ｘ＋ａ１のべき乗算を行う際に生じたＲ×Ｒの計算結果を一時記憶部１６１に記憶しておく。そして、第三秘密情報Ｚ３＝（ＹＢ１）ｙ＋ａ２を計算するときに、ステップＳ４においてＲ×Ｒの演算を行う代わりに、一時記憶部１６１からＲ×Ｒの計算結果を読み込むことでＲ×Ｒの演算を省略する。
【００５３】
ステップＳ３におけるＴ×Ｒの演算量は約Ｉ／２であり、ステップＳ４におけるＲ×Ｒの演算量は約Ｉであることが知られている（例えば、参考文献１参照。）。したがって、初めて演算する底についての演算量は約３Ｉ／２（＝（Ｉ／２）＋Ｉ）であるが、その底と同じ底について再度べき乗算を行う場合にはステップＳ４のＲ×Ｒの演算を省くことにより演算量を約Ｉ／２にすることができる。
【００５４】
〔参考文献１〕A. Menezes, P. Oorschot, S. Vanstone, “Handbook of Applied Cryptography,”,Revised Reprint with Updates, CRC Press, 1997.
従来のＮＡＸＯＳ＋においては互いに異なる５つの底のべき乗算を行う必要があったため演算量は約１５Ｉ／２（＝５×（３Ｉ／２））となるのに対して、第二実施形態において５回のべき乗算のうち２回のべき乗算で既に行った同じ底のべき乗算についての途中計算結果を再利用することができるため演算量は約１１Ｉ／２（＝３×（３Ｉ／２）＋２×（Ｉ／２））となる。したがって、途中計算結果を再利用することにより、演算量を約７３％（＝（１１Ｉ／２）／（１５Ｉ／２））にすることができる。
【００５５】
上記の例ではバイナリ法によりべき乗算を行う場合を例に挙げて演算量の削減について説明をしたが、他の方法によりべき乗算を行う場合にも既に行った同じ底のべき乗算についての途中計算結果を再利用することで演算量を削減することができる。例えば参考文献２に記載された方法によりべき乗算を行う場合には、既に行った同じ底のべき乗算についての途中計算結果を再利用することで、ＮＡＸＯＳ＋方式と比較して演算量を約２／３にすることができる。
【００５６】
〔参考文献２〕David M’Raihi and Acm Press and David Naccache, “Batch Exponentiation: A Fast DLP-based Signature Generation Strategy”, 1966, ACM
なお、証明は省略するが、第二実施形態の情報共有システム及び情報共有方法の安全性は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎｎ問題の困難性を仮定して説明することができる。すなわち、第二実施形態の情報共有システムの安全性は、ＮＡＸＯＳ＋方式の安全性と同等である。
【００５７】
［変形例等］
図２，図３では、各部でデータが直接やり取りされているが、記憶部１１，２１を介してデータの受け渡しが行われてもよい。すなわち、各部で生成された又は受信したデータは記憶部１１，２１に記憶され、各部は記憶部１１，２１からそのデータを読み込んでもよい。
【００５８】
第一情報共有装置Ａ及び第二情報共有装置Ｂのそれぞれは、コンピュータによって実現することができる。この場合、各装置がそれぞれ有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置における各処理機能が、コンピュータ上で実現される。
【００５９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００６０】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【符号の説明】
【００６１】
Ａ     第一情報共有装置
Ｂ     第二情報共有装置
１１   記憶部
１２   乱数生成部
１３   公開鍵生成部
１４   送受信部
１５   交換情報生成部
１６   秘密情報生成部
１７   秘密情報合成部
２１   記憶部
２２   乱数生成部
２３   公開鍵生成部
２４   送受信部
２５   交換情報生成部
２６   秘密情報生成部
２７   秘密情報合成部
【図１】
2011061306.tif 000003
【図２】
2011061306.tif 000004
【図３】
2011061306.tif 000005
【図４】
2011061306.tif 000006
【図５】
2011061306.tif 000007
【図６】
2011061306.tif 000008