(57)【要約】  公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、セッション番号及び乱数が入力され、相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、乱数を用いて貢献乱数を生成し、貢献乱数により貢献データを生成し、貢献データを複数の相手装置に送付し、秘密鍵と公開鍵を用いて、複数の相手装置から受け取った貢献データの全てよりなる貢献データ集合に対する署名である貢献確認署名を生成し、貢献データ集合と貢献乱数とにより、補助データ及び補助データ正当性証明文を生成し、補助データ、補助データ正当性証明文及び貢献確認署名を、複数の相手装置に送付し、相手識別子集合及び相手公開鍵集合と、複数の相手装置から受け取ったデータからなる貢献確認署名集合、補助データ集合及び補助データ正当性証明文集合とより、補助データの正当性を検証し、複数の相手装置から受け取った貢献データ集合と補助データとにより共有鍵を生成する。
2008146547.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、セッション番号及び乱数が入力され、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成、出力する鍵交換装置であって、
前記乱数を用いて貢献乱数を生成する貢献乱数生成部と、
前記貢献乱数生成部にて生成された貢献乱数により貢献データを生成する貢献データ生成部と、
前記貢献データを前記複数の相手装置に送付する通信部と、
前記秘密鍵と前記公開鍵を用いて、前記複数の相手装置から前記通信部にて受け取った貢献データの全てよりなる貢献データ集合に対する署名である貢献確認署名を生成する署名部と、
前記貢献データ集合と前記貢献乱数とにより、補助データ及び補助データ正当性証明文を生成する証明可能補助データ生成部とを有し、
前記補助データ、前記補助データ正当性証明文及び前記貢献確認署名は、前記通信部により前記複数の相手装置に送付され、
前記相手識別子集合及び前記相手公開鍵集合と、前記複数の相手装置から前記通信部にて受け取ったデータからなる前記貢献確認署名集合、前記補助データ集合及び前記補助データ正当性証明文集合とより、前記補助データの正当性を検証する正当性検証部と、
前記複数の相手装置から前記通信部にて受け取った前記貢献データ集合と前記補助データとにより前記共有鍵を生成する鍵生成部とを有する鍵交換装置。
【請求項２】
請求項１に記載の鍵交換装置において、
同じ位数の群Ｇ，ＧTで、群Ｇに属する２つの要素から群ＧTへの双線形写像が存在する２つの群Ｇ，ＧTの計算手段を有し、
前記貢献データ及び前記補助データは群Ｇの元であって、
前記補助データ正当性証明文は空集合であって、
前記正当性検証部は、前記相手識別子集合及び前記相手公開鍵集合と、前記複数の相手装置から前記通信部にて受け取った前記貢献確認署名集合及び前記補助データ集合とより、前記補助データの正当性を検証することを特徴とする装置。
【請求項３】
請求項１または請求項２に記載の鍵交換装置において、
前記署名を生成するのに用いる署名方式が、アグリゲート署名であることを特徴とする鍵交換装置。
【請求項４】
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、セッション番号及び乱数が与えられ、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成、出力する鍵交換方法であって、
前記乱数を用いて貢献乱数を生成する処理と、
前記生成された貢献乱数により貢献データを生成する処理と、
前記貢献データを前記複数の相手装置に送付する処理と、
前記秘密鍵と前記公開鍵を用いて、前記複数の相手装置から受け取った貢献データの全てよりなる貢献データ集合に対する署名である貢献確認署名を生成する処理と、
前記貢献データ集合と前記貢献乱数とにより、補助データ及び補助データ正当性証明文を生成する処理と、
前記補助データ、前記補助データ正当性証明文及び前記貢献確認署名を、前記複数の相手装置に送付する処理と、
前記相手識別子集合及び前記相手公開鍵集合と、前記複数の相手装置から受け取ったデータからなる前記貢献確認署名集合、前記補助データ集合及び前記補助データ正当性証明文集合とより、前記補助データの正当性を検証する処理と、
前記複数の相手装置から受け取った前記貢献データ集合と前記補助データとにより前記共有鍵を生成する処理とを有する鍵交換方法。
【請求項５】
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、セッション番号及び乱数が入力され、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成、出力する鍵交換装置に、
前記乱数を用いて貢献乱数を生成する手順と、
前記生成された貢献乱数により貢献データを生成する手順と、
前記貢献データを前記複数の相手装置に送付する手順と、
前記秘密鍵と前記公開鍵を用いて、前記複数の相手装置から受け取った貢献データの全てよりなる貢献データ集合に対する署名である貢献確認署名を生成する手順と、
前記貢献データ集合と前記貢献乱数とにより、補助データ及び補助データ正当性証明文を生成する手順と、
前記補助データ、前記補助データ正当性証明文及び前記貢献確認署名を、前記複数の相手装置に送付する手順と、
前記相手識別子集合及び前記相手公開鍵集合と、前記複数の相手装置から受け取ったデータからなる前記貢献確認署名集合、前記補助データ集合及び前記補助データ正当性証明文集合とより、前記補助データの正当性を検証する手順と、
前記複数の相手装置から受け取った前記貢献データ集合と前記補助データとにより前記共有鍵を生成する手順とを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、互いに通信を行うことにより同一の鍵を交換可能な鍵交換装置及び鍵交換方法に関する。
【背景技術】
【０００２】
グループ鍵交換装置として、”Jonathan  Katz,  Ji  Sun  Shin:  Modeling  insider  attacks  on  group  key-exchange  protocols.  ACM  Conference  on  Computer  and  Communications  Security  2005:  180-189”に開示された方式がある。【０００３】
以下に、上記文献に開示された方式について説明する。【０００４】
まず、記法を示す。ｐを素数、ＧTを位数、ｑの巡回群とする。鍵を交換する装置の数をｎとし、それぞれの装置にｉで番号を振る。装置ｉを表す識別子をＵ［ｉ］とする。ＧはＧTの生成子とする。ｖ，ｗを無作為に選ばれた整数とする。Ｆ，Ｆ’を擬似乱数生成装置とする。【０００５】
図１は、鍵交換装置の一例を示す図である。【０００６】
本例におけるグループ鍵交換装置は図１に示すように、検証データ検証部３１１と、検証データ生成部３１２と、一時鍵生成部３１３と、補助データ生成部３１４と、貢献乱数生成部３１５と、貢献データ生成部３１６と、通信部３１７とから構成されている。【０００７】
上記のように構成された鍵交換装置３００（ｉ）においては、ｊ＝｛１，・・・，ｎ｝￥ｉのそれぞれの装置ｊに対応する識別子の集合である相手識別子集合３０１と、公開鍵ｐｋ［ｊ］の集合である相手公開鍵集合３０２が入力される。また、識別子３０３（Ｕ［ｉ］）と公開鍵３０４（ｐｋ［ｉ］）に対応する秘密鍵３０５（ｓｋ［ｉ］）も入力される。さらに、これから生成する鍵に固有のセッション番号３０６（ｓｉｄ）が入力される。【０００８】
鍵交換装置３００（ｉ）は、貢献乱数生成部３１５において、入力された乱数３０７を用いて貢献乱数３２４（ｒ［ｉ］∈Ｚ／ｑＺ）をランダムに生成する。【０００９】
そして、貢献データ生成部３１６において、貢献乱数生成部３１５にて生成された貢献乱数３２４（ｒ［ｉ］∈Ｚ／ｑＺ）を用いて貢献データ３２５（ｙ［ｉ］＝ｇr[i]）生成し、また、ｓｉｄ，１，Ｕ［ｉ］，ｙ［ｉ］に対する署名ｓｉｇ（ｉ，１）を生成する。そして、その他の（ｎ−１）個の装置に対して、（ｓｉｄ，１，Ｕ［ｉ］，ｙ［ｉ］，ｓｉｇ（ｉ，１））を通信部３１７から送付する。【００１０】
鍵交換装置３００（ｉ）は、ｊ＝｛１，・・・，ｎ｝￥ｉに関して、装置ｊが貢献データｙ［ｊ］を通信回線３０９を介して送付してくるのを通信部３１７にて待つ。【００１１】
全ての貢献データｙ［ｊ］が揃った貢献データ集合３２３となれば、鍵交換装置３００（ｉ）は各署名を検証する。【００１２】
次に、補助データ生成部３１４において、貢献データ集合３２３を用いて補助データ３２２（ｘ［ｉ］＝（ｙ［ｉ＋１］／ｙ［ｉ−１］）r[i]）を生成し、（ｓｉｄ，２，Ｕ［ｉ］，ｘ［ｉ］）に対する署名ｓｉｇ（ｉ，２）を生成する。【００１３】
そして、通信部３１７において、（ｓｉｄ，２，Ｕ［ｉ］，ｘ［ｉ］，ｓｉｇ（ｉ，２））をその他の（ｎ−１）個の装置に送付する。【００１４】
通信部３１７を介して全てのｘ［ｊ］が受信され、全てのｘ［ｊ］が揃った補助データ集合３２１となれば、鍵交換装置３００（ｉ）は各署名を検証する。【００１５】
次に、一時鍵生成部３１３において、ｋ［ｉ］＝（ｙ［ｉ−１］r[i]）n×［ｉ＋１］n×［ｉ＋２］n-1・・・×［ｎ］i+1×［１］i・・・×［ｉ−１］2×［ｉ］を生成する。【００１６】
次に、検証データ生成部３１２において、ａｃｋ［ｉ］＝Ｆ（ｋ［ｉ］，ｖ）を生成し、また、一時鍵生成部３１３において、共有鍵３０８（ｓｋ［ｉ］＝Ｆ’（ｋ［ｉ］，ｗ））を生成する。また、（ｓｉｄ［ｉ］，３，Ｕ［ｉ］，ａｃｋ［ｉ］）に対する署名ｓｉｇ（ｉ，３）を生成する。【００１７】
そして、通信部３１７において、（ｓｉｄ，３，Ｕ［ｉ］，ａｃｋ［ｉ］，ｓｉｇ（ｉ，３））をその他の（ｎ−１）個の装置に送付する。【００１８】
通信部３１７を介して全てのａｃｋ［ｊ］が受信され、全てのａｃｋ［ｊ］が揃ったならば、鍵交換装置３００（ｉ）は、検証データ検証部３１１において各署名を検証する。【００１９】
そして、検証データ検証部３１１において、全てのｊ＝｛１，・・・，ｎ｝￥ｉに関して、ａｃｋ［ｊ］＝ａｃｋ［ｉ］を確認した場合、一時鍵生成部３１３から共有鍵３０８（ｓｋ［ｉ］）を出力する。【００２０】
上述した技術においては、共有鍵を交換する際、各装置が他の全ての装置に対してデータを３回配布する必要がある。この全ての装置における全ての装置に対するデータの配布が完了しなければ次のステップに移ることができないため、このデータの配布に要する時間は、各データの計算に必要な時間に比べて著しく長くなる。ここで、対多数の通信は、その同期を取る処理等に多くの時間を費やすため、単純な暗号計算と比べて短時間で終了することは難しい。そのため、複数、特に、多数の装置間における鍵交換を迅速に行うためには、このようなデータの配布回数を削減する必要がある。
【発明の開示】
【００２１】
本発明は、複数の装置間にて鍵交換を迅速に行うことができる鍵交換装置を提供することを目的とする。
【００２２】
上記目的を達成するために本発明は、
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、セッション番号及び乱数が入力され、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成、出力する鍵交換装置であって、
前記乱数を用いて貢献乱数を生成する貢献乱数生成部と、
前記貢献乱数生成部にて生成された貢献乱数により貢献データを生成する貢献データ生成部と、
前記貢献データを前記複数の相手装置に送付する通信部と、
前記秘密鍵と前記公開鍵を用いて、前記複数の相手装置から前記通信部にて受け取った貢献データの全てよりなる貢献データ集合に対する署名である貢献確認署名を生成する署名部と、
前記貢献データ集合と前記貢献乱数とにより、補助データ及び補助データ正当性証明文を生成する証明可能補助データ生成部とを有し、
前記補助データ、前記補助データ正当性証明文及び前記貢献確認署名は、前記通信部により前記複数の相手装置に送付され、
前記相手識別子集合及び前記相手公開鍵集合と、前記複数の相手装置から前記通信部にて受け取ったデータからなる前記貢献確認署名集合、前記補助データ集合及び前記補助データ正当性証明文集合とより、前記補助データの正当性を検証する正当性検証部と、
前記複数の相手装置から前記通信部にて受け取った前記貢献データ集合と前記補助データとにより前記共有鍵を生成する鍵生成部とを有する。
【００２３】
本発明は、以上説明したように構成されているので、複数の装置間にて秘密の鍵を共有する場合に、互いにデータを配布する回数が従来よりも１回少ない２回で済むこととなり、より迅速な鍵の交換が可能になる。
【図面の簡単な説明】
【００２４】
【図１】鍵交換装置の一例を示す図である。
【図２】本発明の鍵交換装置の第１の実施の形態を示す図である。
【図３】本発明の鍵交換装置の第２の実施の形態を示す図である。
【発明を実施するための最良の形態】
【００２５】
以下に、本発明の実施の形態について図面を参照して説明する。【００２６】
（実施の形態で使われる記法）
ｐを素数、ＧとＧTを位数ｐの巡回群、ｅをＧ掛けるＧからＧTへの非縮退な双線形写像であるとする。ここで双線形であるとは、すべてのα，β∈Ｚ／ｑＺ及びｇ∈Ｇに対して、
ｅ（ｇα，ｇβ）＝ｅ（ｇ，ｇ）αβ
が成り立つことである。また、非縮退であるとは、ｇがＧの生成元であるとき、ｅ（ｇ，ｇ）が、ＧTの生成元となるということである。【００２７】
鍵を交換する装置の数をｎとし、それぞれの装置にｉで番号を振る。装置ｉを表す識別子をＵ［ｉ］とする。ｇ，ｈはＧTの生成子とする。【００２８】
（第１の実施の形態）
図２は、本発明の鍵交換装置の第１の実施の形態を示す図である。【００２９】
本形態における鍵交換装置は図２に示すように、入力部１１０と計算部１４０と出力部１２０と通信部１３０とから構成され、計算部１４０は、正当性検証部１４１と鍵生成部１４２と証明可能補助データ生成部１４３と署名部１４４と貢献乱数生成部１４５と貢献データ生成部１４６とを有している。【００３０】
入力部１１０は、相手識別子集合１０１、相手公開鍵集合１０２、識別子１０３、公開鍵１０４、秘密鍵１０５、セッション番号１０６及び乱数１０７が入力される。【００３１】
計算部１４０は、同じ位数の群Ｇ，ＧTで、群Ｇに属する２つの要素から群ＧTへの双線形写像が存在する二つの群Ｇ，ＧTの計算手段であって、入力部１１０を介して入力された相手識別子集合１０１、相手公開鍵集合１０２、識別子１０３、公開鍵１０４、秘密鍵１０５、セッション番号１０６及び乱数１０７、並びに通信部１３０にて受信されたデータを用いて共有鍵１０８を生成する。【００３２】
出力部１２０は、計算部１４０にて生成された共有鍵１０８を出力する。【００３３】
貢献乱数生成部１４５は、入力部１１０を介して入力された乱数１０７を用いて、貢献データ１５７を生成するための乱数である貢献乱数１５６を生成する。【００３４】
貢献データ生成部１４６は、貢献乱数生成部１４５にて生成された貢献乱数１５６より貢献データ１５７を生成する。【００３５】
署名部１４４は、入力部１１０を介して入力された秘密鍵１０５と公開鍵１０４を用いて、全ての相手装置から受け取った全ての貢献データよりなる貢献データ集合１５５に対する署名となる貢献確認署名１５３を生成する。【００３６】
証明可能補助データ生成部１４３は、貢献データ集合１５５と貢献乱数１５６とにより、補助データ１５４を生成する。【００３７】
正当性検証部１４１は、入力部１１０を介して入力された相手識別子集合１０１と相手公開鍵集合１０２と、通信部１３０を介して全ての相手装置から受け取ったデータからなる貢献確認署名集合１５１及び補助データ集合１５２とから、補助データの正当性を確認する。【００３８】
鍵生成装置１４２は、通信部１３０を介して全ての相手装置から受け取った貢献データ集合１５５及び補助データ集合１５２から共有鍵１０８を生成する。【００３９】
通信部１３０は、通信回線１０９を介して相手装置とデータ交換するためのものであって、貢献データ生成部１４６にて生成された貢献データ１５７と、証明可能補助データ生成部１４３にて生成された補助データ１５４と、署名部１４４にて生成された貢献確認署名１５３とを通信回線１０９を介して全ての相手装置に送付する。【００４０】
以下に、上記のように構成された鍵交換装置１００の動作について説明する。【００４１】
鍵交換装置１００（ｉ）のそれぞれには、ｊ＝｛１，・・・，ｎ｝￥ｉのそれぞれの装置ｊに対応する識別子Ｕ［ｊ］の集合である相手識別子集合１０１と、ｊ＝｛１，・・・，ｎ｝￥ｉのそれぞれの装置ｊに対応する公開鍵ｐｋ［ｊ］の集合である相手公開鍵集合１０２とが入力部１１０を介して入力される。また、自身の装置に対応する識別子１０３と、自身の公開鍵１０４（ｐｋ［ｉ］）と、この公開鍵１０４（ｐｋ［ｉ］）に対応する秘密鍵１０５（ｓｋ［ｉ］）も入力部１１０を介して入力される。さらに、これから生成される共有鍵１０８に固有のセッション番号１０６（ｓｉｄ）と乱数１０７が入力部１１０を介して入力される。【００４２】
鍵交換装置１００（ｉ）は、まず、貢献乱数生成部１４５において、入力部１１０を介して入力された乱数１０７を用いて、貢献データ１５７を生成するための乱数である貢献乱数１５６（ｒ［ｉ］∈Ｚ／ｑＺ）をランダムに生成する。【００４３】
次に、貢献データ生成部１４６において、貢献乱数生成部１４５にて生成された貢献乱数１５６から貢献データ１５７（ｙ［ｉ］＝ｇr[i]）を生成し、この貢献データ１５７（ｙ［ｉ］＝ｇr[i]）を通信部１３０において、その他の（ｎ−１）個の装置に送付する。【００４４】
鍵交換装置１００（ｉ）は、ｊ＝｛１，・・・，ｎ｝￥ｉに関して、装置ｊが貢献データｙ［ｊ］を送付してくるのを通信部１３０にて待つ。【００４５】
通信部１３０にて全ての装置からの貢献データｙ［ｊ］が受信され、全ての貢献データｙ［ｊ］が揃った貢献データ集合１５５となると、証明可能補助データ生成部１４３において、貢献データ集合１５５と貢献乱数１５６とにより補助データ１５４（ｘ［ｉ］＝（ｙ［ｉ＋１］／ｙ［ｉ−１］）r[i]）を生成し、また、署名部１４４において、入力部１１０を介して入力された秘密鍵１０５と公開鍵１０４を用いて、全ての相手装置から受け取った全ての貢献データよりなる貢献データ集合１５５（ｓｉｄ，ｙ［１］，・・・，ｙ［ｎ］）に対する署名である貢献確認署名１５３（ｓｉｇ）を生成する。【００４６】
そして、通信部１３０において、（ｓｉｄ，ｘ［ｉ］，ｓｉｇ）をその他の（ｎ−１）個の装置に送付する。【００４７】
通信部１３０にて全ての装置からの補助データｘ［ｊ］が受信され、全ての補助データｘ［ｊ］が揃った補助データ集合１５２となると、正当性検証部１４１において、入力部１１０を介して入力された相手識別子集合１０１と相手公開鍵集合１０２と、他の装置から送られてきて通信部１３０にて受信されたデータからなる貢献確認署名集合１５１及び補助データ集合１５２とから、貢献確認署名集合１５１の各署名を検証する。【００４８】
次に、鍵生成部１４２において、通信部１３０を介して全ての相手装置から受け取った貢献データ集合１５５及び補助データ集合１５２からｓｋ［ｉ］＝（ｙ［ｉ−１］r[i])n×［ｉ＋１］n×［ｉ＋２］n-1・・・×［ｎ］i+1×［１］i・・・×［ｉ−１］2×［ｉ］を生成する。【００４９】
そして、正当性検証部１４１において、ｅ（ｋ［ｉ］，ｇ）＝ｅ（ｙ［ｎ］，ｙ［１］）Πjn-1ｅ（ｙ［ｊ］，ｙ［ｊ＋１］）が成り立つことを確認し、成り立てば、鍵生成部１４２から共有鍵１０８（ｓｋ［ｉ］＝ｅ（ｇ，ｈ））を出力部１２０を介して出力する。【００５０】
（第２の実施の形態）
本形態は、第１の実施の形態とは異なり、Ｇに双線形写像が存在しないものとする。【００５１】
図３は、本発明の鍵交換装置の第２の実施の形態を示す図である。【００５２】
本形態における鍵交換装置は図３に示すように、入力部２１０と計算部２４０と出力部２２０と通信部２３０とから構成され、計算部２４０は、正当性検証部２４１と鍵生成部２４２と証明可能補助データ生成部２４３と署名部２４４と貢献乱数生成部２４５と貢献データ生成部２４６とを有している。【００５３】
入力部２１０は、相手識別子集合２０１、相手公開鍵集合２０２、識別子２０３、公開鍵２０４、秘密鍵２０５、セッション番号２０６及び乱数２０７が入力される。【００５４】
計算部２４０は、入力部２１０を介して入力された相手識別子集合２０１、相手公開鍵集合２０２、識別子２０３、公開鍵２０４、秘密鍵２０５、セッション番号２０６及び乱数２０７、並びに通信部２３０にて受信されたデータを用いて共有鍵２０８を生成する。【００５５】
出力部２２０は、計算部２４０にて生成された共有鍵２０８を出力する。【００５６】
貢献乱数生成部２４５は、入力部２１０を介して入力された乱数２０７を用いて、貢献データ２５７を生成するための乱数である貢献乱数２５６を生成する。【００５７】
貢献データ生成部２４６は、貢献乱数生成部２４５にて生成された貢献乱数２５６より貢献データ２５７を生成する。【００５８】
署名部２４４は、入力部２１０を介して入力された秘密鍵２０５と公開鍵２０４を用いて、全ての相手装置から受け取った全ての貢献データよりなる貢献データ集合２５５に対する署名となる貢献確認署名２５３を生成する。【００５９】
証明可能補助データ生成部２４３は、貢献データ集合２５５と貢献乱数２５６とにより、補助データ２５４及び補助データ正当性証明文２５９を生成する。【００６０】
正当性検証部２４１は、入力部２１０を介して入力された相手識別子集合２０１と相手公開鍵集合２０２と、通信部２３０を介して全ての相手装置から受け取ったデータからなる貢献確認署名集合２５１、補助データ集合２５２及び補助データ正当性証明文集合２５８とから、補助データの正当性を確認する。【００６１】
鍵生成装置２４２は、通信部２３０を介して全ての相手装置から受け取った貢献データ集合２５５及び補助データ集合２５２から共有鍵２０８を生成する。【００６２】
通信部２３０は、通信回線２０９を介して相手装置とデータ交換するためのものであって、貢献データ生成部２４６にて生成された貢献データ２５７と、証明可能補助データ生成部２４３にて生成された補助データ２５４及び補助データ正当性証明文２５９と、署名部２４４にて生成された貢献確認署名２５３とを通信回線２０９を介して全ての相手装置に送付する。【００６３】
以下に、上記のように構成された鍵交換装置２００の動作について説明する。【００６４】
鍵交換装置２００（ｉ）のそれぞれには、ｊ＝｛１，・・・，ｎ｝￥ｉのそれぞれの装置ｊに対応する識別子Ｕ［ｊ］の集合である相手識別子集合２０１と、ｊ＝｛１，・・・，ｎ｝￥ｉのそれぞれの装置ｊに対応する公開鍵ｐｋ［ｊ］の集合である相手公開鍵集合２０２とが入力部２１０を介して入力される。また、自身の装置に対応する識別子２０３と、自身の公開鍵２０４（ｐｋ［ｉ］）と、この公開鍵２０４（ｐｋ［ｉ］）に対応する秘密鍵２０５（ｓｋ［ｉ］）も入力部２１０を介して入力される。さらに、これから生成される共有鍵２０８に固有のセッション番号２０６（ｓｉｄ）と乱数２０７が入力部２１０を介して入力される。【００６５】
鍵交換装置２００（ｉ）は、まず、貢献乱数生成部２４５において、入力部２１０を介して入力された乱数２０７を用いて、貢献データ２５７を生成するための乱数である貢献乱数２５６（ｒ［ｉ］∈Ｚ／ｑＺ）をランダムに生成する。【００６６】
次に、貢献データ生成部２４６において、貢献乱数生成部２４５にて生成された貢献乱数２５６から貢献データ２５７（ｙ［ｉ］＝ｇr[i]）を生成し、この貢献データ１５７（ｙ［ｉ］＝ｇr[i]）を通信部２３０において、その他の（ｎ−１）個の装置に送付する。【００６７】
鍵交換装置２００（ｉ）は、ｊ＝｛１，・・・，ｎ｝￥ｉに関して、装置ｊが貢献データｙ［ｊ］を送付してくるのを通信部２３０にて待つ。【００６８】
通信部２３０にて全ての装置からの貢献データｙ［ｊ］が受信され、全ての貢献データｙ［ｊ］が揃った貢献データ集合２５５となると、証明可能補助データ生成部２４３において、貢献データ集合２５５と貢献乱数２５６とにより補助データ２５４（ｘ［ｉ］＝（ｙ［ｉ＋１］／ｙ［ｉ−１］）r[i]）を生成し、また、署名部２４４において、入力部２１０を介して入力された秘密鍵２０５と公開鍵２０４を用いて、全ての相手装置から受け取った全ての貢献データよりなる貢献データ集合２５５（ｓｉｄ，ｙ［１］，・・・，ｙ［ｎ］）に対する署名である貢献確認署名２５３（ｓｉｇ）を生成する。証明可能補助データ生成部２４３においては、ｘ［ｉ］がｙ［ｉ＋１］，ｙ［ｉ−１］，ｒ［ｉ］より正しく作られたことを、ｙ［ｉ＋１］，ｙ［ｉ−１］，ｙ［ｉ］，ｇのみを示して、非対話零知識で証明する。この証明文を、補助データ正当性証明文２５９（ｐｒｏｏｆ［ｉ］）とする。【００６９】
そして、通信部２３０において、（ｓｉｄ，ｐｒｏｏｆ［ｉ］，ｓｉｇ）をその他の（ｎ−１）個の装置に送付する。【００７０】
通信部２３０にて全ての装置からの補助データｘ［ｊ］が受信され、全ての補助データｘ［ｊ］が揃った補助データ集合２５２となると、正当性検証部２４１において、入力部２１０を介して入力された相手識別子集合２０１と相手公開鍵集合２０２と、他の装置から送られてきて通信部２３０にて受信されたデータからなる貢献確認署名集合２５１及び補助データ集合２５２とから、貢献確認署名集合２５１の各署名と、補助データ正当性証明文集合２５８の各補助データ正当性証明文（ｐｒｏｏｆ［ｊ］）を検証する。【００７１】
次に、鍵生成部２４２において、通信部２３０を介して全ての相手装置から受け取った貢献データ集合２５５及び補助データ集合２５２からｓｋ［ｉ］＝（ｙ［ｉ−１］r[i])n×［ｉ＋１］n×［ｉ＋２］n-1・・・×［ｎ］i+1×［１］i・・・×［ｉ−１］2×［ｉ］を生成する。【００７２】
そして、鍵生成部２４２から共有鍵２０８（ｓｋ［ｉ］＝ｅ（ｇ，ｈ））を出力部２２０を介して出力する。【００７３】
上述した２つの実施の形態においては、各装置が署名を生成する対象の文章が、全て同じである。このような場合、署名を、アグリゲート署名を用い、検証に必要な計算量を減らすことができる。【００７４】
なお、本発明においては、鍵交換装置内の処理は上述の専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを鍵交換装置にて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムを鍵交換装置に読み込ませ、実行するものであっても良い。鍵交換装置にて読取可能な記録媒体とは、フロッピーディスク、光磁気ディスク、ＤＶＤ、ＣＤなどの移設可能な記録媒体の他、鍵交換装置に内蔵されたＨＤＤ等を指す。この記録媒体に記録されたプログラムは、例えば、制御ブロックにて読み込まれ、制御ブロックの制御によって、上述したものと同様の処理が行われる。
【産業上の利用可能性】
【００７５】
複数の装置による鍵の交換は、ネットワーク上で多人数のユーザが会議を開く場合などに有効である。参加するメンバが確認でき、メンバ外のユーザが会議に参加したり、会議の内容を盗聴できないようにしたりするために、会議メンバで共有する秘密鍵を、本発明による鍵交換装置を用いて事前に決定することができる。【００７６】
以上、実施例を参照して本願発明を説明したが、本願発明は上記実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【００７７】
この出願は、２００７年５月２５日に出願された日本出願特願２００７−１３８９４０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2008146547.tif 000003
【図２】
2008146547.tif 000004
【図３】
2008146547.tif 000005
【手続補正書】
【提出日】平成20年10月10日(2008.10.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２
【補正方法】変更
【補正の内容】
【請求項２】
請求項１に記載の鍵交換装置において、
特に同じ位数の群Ｇ，ＧＴで、群Ｇに属する２つの要素から群ＧＴへの双線形写像が存在する２つの群Ｇ，ＧＴの計算手段を有し、
特に、前記貢献データ及び前記補助データは群Ｇの元であって、
前記補助データ正当性証明文は空集合であって、
前記正当性検証部は、各補助データが貢献データ集合より正しく生成されたことを、貢献データや補助データを入力として双線形写像を計算することで検証することを特徴とする鍵交換装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００２
【補正方法】変更
【補正の内容】
【０００２】
１，Ｕ［ｉ］，ｙ［ｉ］に対する署名ｓｉｇ（ｉ，１）を生成する。そして、その他の（ｎ−１）個の装置に対して、（ｓｉｄ，１，Ｕ［ｉ］，ｙ［ｉ］，ｓｉｇ（ｉ，１））を通信部３１７から送付する。
［００１０］
鍵交換装置３００（ｉ）は、ｊ＝｛１，・・・，ｎ｝￥ｉに関して、装置ｊが貢献データｙ［ｊ］を通信回線３０９を介して送付してくるのを通信部３１７にて待つ。
［００１１］
全ての貢献データｙ［ｊ］が揃った貢献データ集合３２３となれば、鍵交換装置３００（ｉ）は各署名を検証する。
［００１２］
次に、補助データ生成部３１４において、貢献データ集合３２３を用いて補助データ３２２（ｘ［ｉ］＝（ｙ［ｉ＋１］／ｙ［ｉ−１］）ｒ［ｉ］）を生成し、（ｓｉｄ，２，Ｕ［ｉ］，ｘ［ｉ］）に対する署名ｓｉｇ（ｉ，２）を生成する。
［００１３］
そして、通信部３１７において、（ｓｉｄ，２，Ｕ［ｉ］，ｘ［ｉ］，ｓｉｇ（ｉ，２））をその他の（ｎ−１）個の装置に送付する。
［００１４］
通信部３１７を介して全てのｘ［ｊ］が受信され、全てのｘ［ｊ］が揃った補助データ集合３２１となれば、鍵交換装置３００（ｉ）は各署名を検証する。
［００１５］
次に、一時鍵生成部３１３において、ｋ［ｉ］＝（ｙ［ｉ−１］ｒ［ｉ］）ｎｘ［ｉ＋１］ｎｘ［ｉ＋２］ｎ−１・・・ｘ［ｎ］ｉ＋１ｘ［１］ｉ・・・ｘ［ｉ−１］２ｘ［ｉ］を生成する。
［００１６］
次に、検証データ生成部３１２において、ａｃｋ［ｉ］＝Ｆ（ｋ［ｉ］，ｖ）を生成し、また、一時鍵生成部３１３において、共有鍵３０８（ｓｋ［ｉ］＝Ｆ’（ｋ［ｉ］，ｗ））を生成する。また、（ｓｉｄ［ｉ］，３，Ｕ［ｉ］，ａｃｋ［ｉ］）に対する署名ｓｉｇ（ｉ，３）を生成する。
［００１７］
そして、通信部３１７において、（ｓｉｄ，３，Ｕ［ｉ］，ａｃｋ［ｉ］，ｓｉｇ（ｉ，３））をその他の（ｎ−１）個の装置に送付する。
［００１８］
通信部３１７を介して全てのａｃｋ［ｊ］が受信され、全てのａｃｋ［ｊ］が揃ったならば、鍵交換装置３００（ｉ）は、検証データ検証部３１１において各署名を検証する。
［００１９］
そして、検証データ検証部３１１において、全てのｊ＝｛１，・・・，ｎ｝￥ｉに関して、ａｃｋ［ｊ］＝ａｃｋ［ｉ］を確認した場合、一時鍵生成部３１３から共有鍵３０８（ｓｋ［ｉ］）を出力する。
［００２０］
上述した技術においては、共有鍵を交換する際、各装置が他の全ての装置に対してデータを３回配布する必要がある。この全ての装置における全ての装置に対するデータの配布が完了しなければ次のステップに移ることができないため、このデータ
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
０を介して入力される。また、自身の装置に対応する識別子１０３と、自身の公開鍵１０４（ｐｋ［ｉ］）と、この公開鍵１０４（ｐｋ［ｉ］）に対応する秘密鍵１０５（ｓｋ［ｉ］）も入力部１１０を介して入力される。さらに、これから生成される共有鍵１０８に固有のセッション番号１０６（ｓｉｄ）と乱数１０７が入力部１１０を介して入力される。
［００４２］
鍵交換装置１００（ｉ）は、まず、貢献乱数生成部１４５において、入力部１１０を介して入力された乱数１０７を用いて、貢献データ１５７を生成するための乱数である貢献乱数１５６（ｒ［ｉ］∈Ｚ／ｑＺ）をランダムに生成する。
［００４３］
次に、貢献データ生成部１４６において、貢献乱数生成部１４５にて生成された貢献乱数１５６から貢献データ１５７（ｙ［ｉ］＝ｇｒ［ｉ］）を生成し、この貢献データ１５７（ｙ［ｉ］＝ｇｒ［ｉ］）を通信部１３０において、その他の（ｎ−１）個の装置に送付する。
［００４４］
鍵交換装置１００（ｉ）は、ｊ＝｛１，・・・，ｎ｝￥ｉに関して、装置ｊが貢献データｙ［ｊ］を送付してくるのを通信部１３０にて待つ。
［００４５］
通信部１３０にて全ての装置からの貢献データｙ［ｊ］が受信され、全ての貢献データｙ［ｊ］が揃った貢献データ集合１５５となると、証明可能補助データ生成部１４３において、貢献データ集合１５５と貢献乱数１５６とにより補助データ１５４（ｘ［ｉ］＝（ｙ［ｉ＋１］／ｙ［ｉ−１］）ｒ［ｉ］）を生成し、また、署名部１４４において、入力部１１０を介して入力された秘密鍵１０５と公開鍵１０４を用いて、全ての相手装置から受け取った全ての貢献データよりなる貢献データ集合１５５（ｓｉｄ，ｙ［１］，・・・，ｙ［ｎ］）に対する署名である貢献確認署名１５３（ｓｉｇ）を生成する。
［００４６］
そして、通信部１３０において、（ｓｉｄ，ｘ［ｉ］，ｓｉｇ）をその他の（ｎ−１）個の装置に送付する。
［００４７］
通信部１３０にて全ての装置からの補助データｘ［ｊ］が受信され、全ての補助データｘ［ｊ］が揃った補助データ集合１５２となると、正当性検証部１４１において、入力部１１０を介して入力された相手識別子集合１０１と相手公開鍵集合１０２と、他の装置から送られてきて通信部１３０にて受信されたデータからなる貢献確認署名集合１５１及び補助データ集合１５２とから、貢献確認署名集合１５１の各署名を検証する。
［００４８］
次に、鍵生成部１４２において、通信部１３０を介して全ての相手装置から受け取った貢献データ集合１５５及び補助データ集合１５２からｋ［ｉ］＝（ｙ［ｉ−１］ｒ［ｉ］）ｎｘ［ｉ＋１］ｎ
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
ｘ［ｉ＋２］ｎ−１・・・ｘ［ｎ］ｉ＋１ｘ［１］ｉ・・・ｘ［ｉ−１］２ｘ［ｉ］を生成する。
［００４９］
そして、正当性検証部１４１において、ｅ（ｋ［ｉ］，ｇ）＝ｅ（ｙ［ｎ］，ｙ［１］）Πｊｎ−１ｅ（ｙ［ｊ］，ｙ［ｊ＋１］）が成り立つことを確認し、成り立てば、鍵生成部１４２から共有鍵１０８（ｓｋ［ｉ］＝ｅ（ｇ，ｈ））を出力部１２０を介して出力する。
［００５０］
（第２の実施の形態）
本形態は、第１の実施の形態とは異なり、Ｇに双線形写像が存在しないものとする。
［００５１］
図３は、本発明の鍵交換装置の第２の実施の形態を示す図である。
［００５２］
本形態における鍵交換装置は図３に示すように、入力部２１０と計算部２４０と出力部２２０と通信部２３０とから構成され、計算部２４０は、正当性検証部２４１と鍵生成部２４２と証明可能補助データ生成部２４３と署名部２４４と貢献乱数生成部２４５と貢献データ生成部２４６とを有している。
［００５３］
入力部２１０は、相手識別子集合２０１、相手公開鍵集合２０２、識別子２０３、公開鍵２０４、秘密鍵２０５、セッション番号２０６及び乱数２０７が入力される。
［００５４］
計算部２４０は、入力部２１０を介して入力された相手識別子集合２０１、相手公開鍵集合２０２、識別子２０３、公開鍵２０４、秘密鍵２０５、セッション番号２０６及び乱数２０７、並びに通信部２３０にて受信されたデータを用いて共有鍵２０８を生成する。
［００５５］
出力部２２０は、計算部２４０にて生成された共有鍵２０８を出力する。
［００５６］
貢献乱数生成部２４５は、入力部２１０を介して入力された乱数２０７を用いて、貢献データ２５７を生成するための乱数である貢献乱数２５６を生成する。
［００５７］
貢献データ生成部２４６は、貢献乱数生成部２４５にて生成された貢献乱数２５６より貢献データ２５７を生成する。
［００５８］
署名部２４４は、入力部２１０を介して入力された秘密鍵２０５と公開鍵２０４を用いて、全ての相手装置から受け取った全ての貢献データよりなる貢献データ集合２５５に対する署名となる貢献確認署名２５３を生成する。
［００５９］
証明可能補助データ生成部２４３は、貢献データ集合２５５と貢献乱数２５６とにより、補助データ２５４及び補助データ正当性証明文２５９を生成する。
［００６０］
正当性検証部２４１は、入力部２１０を介して入力された相手識別子集合２０１と相手公開鍵集合２０２と、通信部２３０を介して全ての相手装置から受け取ったデータから
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
ｙ［ｉ−１］）ｒ［ｉ］）を生成し、また、署名部２４４において、入力部２１０を介して入力された秘密鍵２０５と公開鍵２０４を用いて、全ての相手装置から受け取った全ての貢献データよりなる貢献データ集合２５５（ｓｉｄ，ｙ［１］，・・・，ｙ［ｎ］）に対する署名である貢献確認署名２５３（ｓｉｇ）を生成する。証明可能補助データ生成部２４３においては、ｘ［ｉ］がｙ［ｉ＋１］，ｙ［ｉ−１］，ｒ［ｉ］より正しく作られたことを、ｙ［ｉ＋１］，ｙ［ｉ−１］，ｙ［ｉ］，ｇのみを示して、非対話零知識で証明する。この証明文を、補助データ正当性証明文２５９（ｐｒｏｏｆ［ｉ］）とする。
［００６９］
そして、通信部２３０において、（ｓｉｄ，ｐｒｏｏｆ［ｉ］，ｓｉｇ）をその他の（ｎ−１）個の装置に送付する。
［００７０］
通信部２３０にて全ての装置からの補助データｘ［ｊ］が受信され、全ての補助データｘ［ｊ］が揃った補助データ集合２５２となると、正当性検証部２４１において、入力部２１０を介して入力された相手識別子集合２０１と相手公開鍵集合２０２と、他の装置から送られてきて通信部２３０にて受信されたデータからなる貢献確認署名集合２５１及び補助データ集合２５２とから、貢献確認署名集合２５１の各署名と、補助データ正当性証明文集合２５８の各補助データ正当性証明文（ｐｒｏｏｆ［ｊ］）を検証する。
［００７１］
次に、鍵生成部２４２において、通信部２３０を介して全ての相手装置から受け取った貢献データ集合２５５及び補助データ集合２５２からｋ［ｉ］＝（ｙ［ｉ−１］ｒ［ｉ］）ｎｘ［ｉ＋１］ｎｘ［ｉ＋２］ｎ−１・・・ｘ［ｎ］ｉ＋１ｘ［１］ｉ・・・ｘ［ｉ−１］２ｘ［ｉ］を生成する。
［００７２］
そして、鍵生成部２４２から共有鍵２０８（ｓｋ［ｉ］＝ｅ（ｇ，ｈ））を出力部２２０を介して出力する。
［００７３］
上述した２つの実施の形態においては、各装置が署名を生成する対象の文章が、全て同じである。このような場合、署名を、アグリゲート署名を用い、検証に必要な計算量を減らすことができる。
［００７４］
なお、本発明においては、鍵交換装置内の処理は上述の専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを鍵交換装置にて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムを鍵交換装置に読み込ませ、実行するものであっても良い。鍵交換装置にて読取可能な記録媒体とは、フロッピーディスク、光磁気ディスク、ＤＶＤ、ＣＤなどの移設可能な記録媒体の他
【国際調査報告】
2008146547.tif 000006
2008146547.tif 000007
2008146547.tif 000008
2008146547.tif 000009
2008146547.tif 000010
2008146547.tif 000011