(57)【要約】  本発明の鍵交換装置（１００）は、乱数を用いて複数の貢献乱数を生成する貢献乱数生成部（１０２）と、複数の貢献乱数を用いて複数の貢献データを生成する貢献データ生成部（１１０）と、複数の貢献データの中から貢献データを指定する番号を選択する選択部（１０３）と、番号のコミットメントを生成するコミットメント生成部（１０４）と、番号の貢献乱数とコミットメントの開示情報とを保存する内部状態保存部（１２６）と、複数の貢献データとコミットメントとを複数の相手装置に送信する通信部（１２５）と、貢献データ集合と貢献乱数とを用いて、補助データを生成する補助データ生成部（１３４）と、を有し、補助データとコミットメントの開示情報とは、通信部（１２５）により複数の相手装置に送信され、貢献データ集合とコミットメントの開示情報と補助データと貢献乱数とを用いて、共有鍵を生成し出力する共有鍵生成部（１３９）と、を有する。
2009019932.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、および乱数が入力され、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成し出力する鍵交換装置であって、
前記乱数を用いて複数の貢献乱数を生成する貢献乱数生成部と、
前記複数の貢献乱数をそれぞれ用いて複数の貢献データを生成する貢献データ生成部と、
前記複数の貢献データの中から前記共有鍵の生成に用いる貢献データを指定する番号を選択する選択部と、
前記番号のコミットメントを生成するコミットメント生成部と、
前記番号の貢献乱数と前記コミットメントの開示情報とを内部状態として保存する内部状態保存部と、
前記複数の貢献データと前記コミットメントとを前記複数の相手装置に送信する通信部と、
前記複数の相手装置から前記通信部を介して受信した前記貢献データの全ての集合である貢献データ集合と、前記内部状態保存部に保存された前記貢献乱数と、を用いて、補助データを生成する補助データ生成部と、を有し、
前記補助データと前記コミットメントの開示情報とは、前記通信部により前記複数の相手装置に送信され、
前記複数の相手装置から前記通信部を介して受信した、前記貢献データ集合、前記コミットメントの開示情報、および前記補助データと、前記内部状態保存部に保存された前記貢献乱数と、を用いて、前記共有鍵を生成し出力する共有鍵生成部と、を有する、鍵交換装置。
【請求項２】
請求項１に記載の鍵交換装置において、
前記秘密鍵と前記公開鍵とを用いて、前記貢献データ集合に対する署名である同意確認署名を生成する署名部を有する、鍵交換装置。
【請求項３】
請求項２に記載の鍵交換装置において、
前記補助データ生成部は、前記貢献データ集合の中から２つの相手装置の貢献データを取り出し、一方の相手装置の複数の貢献データの１つと他方の相手装置の複数の貢献データの１つとの全ての組合せについて、前記補助データを生成し、
前記通信部は、前記補助データの全ての集合である補助データ集合と、前記同意確認署名と、前記コミットメントの開示情報と、を前記複数の相手装置に送信し、
前記相手識別子集合と、前記複数の相手装置から前記通信部を介して受信した前記貢献データ集合および前記補助データ集合と、を用いて、前記複数の相手装置から前記通信部を介して受信した前記補助データの正当性を検証する補助データ検証部と、
前記相手識別子集合および前記相手公開鍵集合と、前記複数の相手装置から前記通信部を介して受信した前記貢献データ集合と、を用いて、前記複数の相手装置から前記通信部を介して受信した前記同意確認署名の正当性を検証する署名検証部と、
前記相手識別子集合と、前記複数の相手装置から前記通信部を介して受信した前記貢献データ集合と、を用いて、前記複数の相手装置から前記通信部を介して受信した前記コミットメントの開示情報の正当性を検証する開示情報検証部と、を有し、
前記共有鍵生成部は、前記補助データ検証部、前記署名検証部、および前記開示情報検証部の全てで正当性が検証された場合に、前記共有鍵を生成し出力する、鍵交換装置。
【請求項４】
請求項３に記載の鍵交換装置において、
同じ位数の群Ｇ，ＧＴであって、群Ｇに属する２つの要素から群ＧＴへの双線形写像が存在する２つの群Ｇ，ＧＴの計算手段を有し、
前記貢献データおよび前記補助データは群Ｇの元であって、
前記補助データ検証部は、前記貢献データおよび前記補助データの双線形写像を用いて、前記補助データの正当性を検証する、鍵交換装置。
【請求項５】
請求項２から４のいずれか１項に記載の鍵交換装置において、
前記署名を生成するのに用いる署名方式がアグリゲート署名である、鍵交換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、互いに通信を行うことにより同一の鍵を交換可能な鍵交換装置に関する。
【背景技術】
【０００２】
鍵交換装置として、非特許文献１に開示された方式がある。【０００３】
以下に、非特許文献１に開示された方式を、非特許文献２に開示されたプロトコル（ｐｒｏｔｏｃｏｌ３）に適用することで実現される方式について、図１を参照して説明する。【０００４】
図１は、従来の鍵交換装置２００の一構成例を示す図である。【０００５】
まず、記法を説明する。【０００６】
ｐを素数、ＧＴを位数ｑの巡回群とする。鍵交換装置２００の数をｎとし、鍵交換装置２００のそれぞれにｉで番号を振る。鍵交換装置２００（ｉ）を表す識別子をＵ［ｉ］とする。ｇはＧＴの生成子とする。ｖ，ｗを無作為に選ばれた整数とする。Ｆ，Ｆ’を擬似乱数生成装置とする。【０００７】
次に、鍵交換装置２００の構成を説明する。【０００８】
図１に示すように、鍵交換装置２００は、検証データ生成部２０８と、一時鍵生成部２０９と、補助データ生成部２１６と、貢献乱数生成部２１９と、貢献データ生成部２２１と、通信部２２３と、検証データ検証部２２６と、を有している。【０００９】
上記のように構成された鍵交換装置２００（ｉ）においては、ｊ＝｛１，．．．，ｎ｝￥ｉのそれぞれの鍵交換装置２００（ｊ）の識別子の集合である相手識別子集合２０１と、鍵交換装置２００（ｊ）の公開鍵ｐｋ［ｊ］の集合である相手公開鍵集合２０２（ｐｉｄ）と、が入力される。また、自身の鍵交換装置２００（ｉ）の識別子２０３（Ｕ［ｉ］）および公開鍵２０４（ｐｋ［ｉ］）と、公開鍵２０４（ｐｋ［ｉ］）に対応する秘密鍵２０５（ｓｋ［ｉ］）と、が入力される。また、これから生成する共有鍵２２５（ｓｋ［ｉ］）に固有のセッション番号２０６（ｓｉｄ）が入力される。さらに、乱数２０７が入力される。【００１０】
まず、鍵交換装置２００（ｉ）は、貢献乱数生成部２１９において、乱数２０７を用いて、貢献乱数２２０（ｒ［ｉ］∈Ｚ／ｑＺ）をランダムに生成する。【００１１】
次に、鍵交換装置２００（ｉ）は、貢献データ生成部２２１において、貢献乱数生成部２１９にて生成された貢献乱数２２０（ｒ［ｉ］∈Ｚ／ｑＺ）を用いて、貢献データ２２２（ｙ［ｉ］＝ｇｒ［ｉ］）を生成し、また、ｓｉｄ，１，Ｕ［ｉ］，ｙ［ｉ］に対する署名ｓｉｇ（ｉ，１）を生成する。【００１２】
次に、鍵交換装置２００（ｉ）は、通信部２２３において、その他のｎ−１個の鍵交換装置２００（ｊ）に対して、（ｓｉｄ，１，Ｕ［ｉ］，ｙ［ｉ］，ｓｉｇ（ｉ，１））を送付する。【００１３】
鍵交換装置２００（ｉ）は、ｊ＝｛１，．．．，ｎ｝￥ｉの全ての鍵交換装置２００（ｊ）がｙ［ｊ］を通信回線２２４を介して送付してくるのを通信部２２３にて待つ。【００１４】
そして、全てのｙ［ｊ］が揃って貢献データ集合２１８となれば、鍵交換装置２００（ｉ）は、各署名を検証する。【００１５】
次に、鍵交換装置２００（ｉ）は、補助データ生成部２１６において、貢献データ集合２１８を用いて、補助データ２１５（ｘ［ｉ］＝（ｙ［ｉ＋１］／ｙ［ｉ−１］）ｒ［ｉ］）を生成し、また、（ｓｉｄ，２，Ｕ［ｉ］，ｘ［ｉ］）に対する署名ｓｉｇ（ｉ，２）を生成する。【００１６】
次に、鍵交換装置２００（ｉ）は、通信部２２３において、（ｓｉｄ，２，Ｕ［ｉ］，ｘ［ｉ］，ｓｉｇ（ｉ，２））を、その他のｎ−１個の鍵交換装置２００（ｊ）に送付する。【００１７】
そして、全てのｘ［ｊ］が揃って補助データ集合２１２となれば、鍵交換装置２００（ｉ）は、各署名を検証する。【００１８】
次に、鍵交換装置２００（ｉ）は、一時鍵生成部２０９において、ｋ［ｉ］＝（ｙ［ｉ−１］ｒ［ｉ］）ｎｘ［ｉ＋１］ｎｘ［ｉ＋２］ｎ−１．．．ｘ［ｎ］ｉ＋１ｘ［１］ｉ．．．ｘ［ｉ−１］２ｘ［ｉ］を生成する。【００１９】
次に、鍵交換装置２００（ｉ）は、検証データ生成部２０８において、ａｃｋ［ｉ］＝Ｆ（ｋ［ｉ］，ｖ）を生成し、また、一時鍵生成部２０９において、共有鍵２２５（ｓｋ［ｉ］＝Ｆ’（ｋ［ｉ］，ｗ））を生成する。また、鍵交換装置２００（ｉ）は、（ｓｉｄ［ｉ］，３，Ｕ［ｉ］，ａｃｋ［ｉ］）に対する署名ｓｉｇ（ｉ，３）を生成する。【００２０】
次に、鍵交換装置２００（ｉ）は、通信部２２３において、（ｓｉｄ，３，Ｕ［ｉ］，ａｃｋ［ｉ］，ｓｉｇ（ｉ，３））を、その他のｎ−１個の鍵交換装置２００（ｊ）に送付する。【００２１】
そして、全てのａｃｋ［ｊ］が揃ったならば、鍵交換装置２００（ｉ）は、検証データ検証部２２６において、各署名を検証する。【００２２】
その後、鍵交換装置２００（ｉ）は、検証データ検証部２２６において、全てのｊ＝｛１，．．．，ｎ｝￥ｉに関して、ａｃｋ［ｊ］＝ａｃｋ［ｉ］を確認すると、一時鍵生成部２０９において、共有鍵２２５（ｓｋ［ｉ］）を出力する。【００２３】
しかしながら、上述した図１の技術では、各鍵交換装置には、固有のセッション番号が入力されなければならない。そのためには、セッションに参加する鍵交換装置間で乱数等のデータを３回配布し合い、これらのデータを連結したものを固有のセッション番号とする等の処理が必要である。よって、全ての鍵交換装置による全体に対する配布が完了しなければ次のステップに移ることができない。ただし、この配布に要する時間は、各データの計算に必要な時間に比べて著しく長くなる。したがって、複数、特に、多数の鍵交換装置間における鍵交換を迅速に行うためには、このようなデータの配布処理を削減する必要がある。
【非特許文献１】Jonathan  Katz,  Ji  Sun  Shin:  Modeling  insider  attacks  on  group  key-exchange  protocols.  ACM  Conference  on  Computer  and  Communications  Security  2005:  180-189
【非特許文献２】Mike  Burmester,  Yvo  Desmedt:  A  secure  and  Efficient  Conference  Key  Distribuion  System:  275-285
【発明の開示】
【００２４】
そこで、本発明の目的は、上述した、複数の鍵交換装置間にて鍵交換を迅速に行うことができないという課題を解決する鍵交換装置を提供することにある。
【００２５】
上記目的を達成するために本発明の鍵交換装置は、
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、および乱数が入力され、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成し出力する鍵交換装置であって、
前記乱数を用いて複数の貢献乱数を生成する貢献乱数生成部と、
前記複数の貢献乱数をそれぞれ用いて複数の貢献データを生成する貢献データ生成部と、
前記複数の貢献データの中から前記共有鍵の生成に用いる貢献データを指定する番号を選択する選択部と、
前記番号のコミットメントを生成するコミットメント生成部と、
前記番号の貢献乱数と前記コミットメントの開示情報とを内部状態として保存する内部状態保存部と、
前記複数の貢献データと前記コミットメントとを前記複数の相手装置に送信する通信部と、
前記複数の相手装置から前記通信部を介して受信した前記貢献データの全ての集合である貢献データ集合と、前記内部状態保存部に保存された前記貢献乱数と、を用いて、補助データを生成する補助データ生成部と、を有し、
前記補助データと前記コミットメントの開示情報とは、前記通信部により前記複数の相手装置に送信され、
前記複数の相手装置から前記通信部を介して受信した、前記貢献データ集合、前記コミットメントの開示情報、および前記補助データと、前記内部状態保存部に保存された前記貢献乱数と、を用いて、前記共有鍵を生成し出力する共有鍵生成部と、を有することを特徴とする。
【００２６】
以上説明したように本発明によれば、複数の鍵交換装置間にて秘密の鍵を共有する場合に、互いにデータを配布する回数が従来よりも１回少ない２回で済むこととなり、より迅速な鍵の交換が可能になるという効果が得られる。
【図面の簡単な説明】
【００２７】
【図１】従来の鍵交換装置の一構成例を示す図である。
【図２】本実施形態の鍵交換装置の構成の一部を示す図である。
【図３】本実施形態の鍵交換装置の構成の部分を示す図である。
【図４】本実施形態の鍵交換装置の構成の部分を示す図である。
【発明を実施するための最良の形態】
【００２８】
以下に、本発明を実施するための最良の形態について図面を参照して説明する。【００２９】
図２〜図４はそれぞれ、本発明の一実施形態の鍵交換装置１００の構成の一部を示す図である。詳細には、図２は、貢献データとコミットメントの生成・通信を行う部分の構成を示し、また、図３は、補助データの生成・通信を行う部分の構成を示し、また、図４は、共有鍵の生成・出力を行う部分の構成を示している。【００３０】
［本実施形態で使われる記法］
ｐを素数、ＧとＧＴを位数ｐの巡回群、ｅをＧ×ＧからＧＴへの非縮退な双線形写像であるとする。【００３１】
ここで、双線形であるとは、すべてのα，β∈Ｚ／ｑＺ及びｇ∈Ｇに対して、ｅ（ｇα，ｇβ）＝ｅ（ｇ，ｇ）αβが成り立つことである。【００３２】
また、非縮退であるとは、ｇがＧの生成元であるとき、ｅ（ｇ，ｇ）が、ＧＴの生成元となることである。【００３３】
落とし戸付きコミットメント方式が準備されているとする。この方式のシステム変数をｔｐｒａｍ、落とし戸鍵をｔｄｒとする。この方式により、メッセージｍが与えられると、コミットメントｃｏｍと、コミットメントの開示情報ｄｅｃと、を生成することができる。ｄｅｃが与えられると、メッセージｍのコミットメントとしてｃｏｍを生成したことを検証することができる。一方、ｃｏｍ，ｍ’，ｄｅｃ，ｔｄｒが与えられると、ｃｏｍがｍ’のコミットメントであることを示すｄｅｃ’を生成することができる。【００３４】
鍵交換装置１００の数をｎとし、鍵交換装置１００のそれぞれにｉで番号を振る。鍵交換装置１００（ｉ）を表す識別子をＵ［ｉ］とする。ｇ，ｈはＧＴの生成子とする。【００３５】
［本実施形態の構成］
図２〜図４に示すように、鍵交換装置１００は、貢献乱数生成部１０２と、選択部１０３と、コミットメント生成部１０４と、貢献データ生成部１１０と、通信部１２５と、内部状態保存部１２６と、セッション番号生成部１３０と、署名部１３３と、補助データ生成部１３４と、署名検証部１３６と、開示情報検証部１３７と、補助データ検証部１３８と、共有鍵生成部１３９と、を有している。【００３６】
鍵交換装置１００は、乱数１０１、相手識別子集合１２０、相手公開鍵集合１２１、識別子１２２、公開鍵１２３、および秘密鍵１２４が入力され、相手識別子集合１２０に属する識別子で識別される他の鍵交換装置と通信を行い、共有鍵１３５を生成し出力するものである。【００３７】
貢献乱数生成部１０２は、乱数１０１を用いて、２個の貢献乱数１０５，１０６を生成し、また、貢献データ生成部１１０は、貢献乱数生成部１０２にて生成された２個の貢献乱数１０５，１０６をそれぞれ用いて、２個の貢献データ１１１，１１２を生成する。ここでは、貢献乱数と貢献データは、それぞれ２個ずつであるが、複数であれば何個でも良い。【００３８】
選択部１０３は、２個の貢献データ１１１，１１２の中から共有鍵１３５の生成に用いる貢献データを指定する番号１０７を選択する。【００３９】
コミットメント生成部１０４は、選択部１０３にて選択された番号１０７のコミットメント１０８と、その開示情報１０９と、を生成する。【００４０】
内部状態保存部１２６は、選択部１０３にて選択された番号１０７の貢献乱数１１４と、選択部１０３にて選択された番号１０７のコミットメント１０８の開示情報１１５と、を、内部状態として保存する。すなわち、内部状態保存部１２６は、選択部１０３にて選択された番号１０７以外の、その他の貢献乱数は消去することになる。【００４１】
通信部１２５は、貢献データ生成部１１０にて生成された２個の貢献データ１１１，１１２と、選択部１０３にて選択された番号１０７のコミットメント１１３と、を、通信回線１２７を介して、その他の鍵交換装置に送付する。【００４２】
また、通信部１２５は、通信回線１２７を介して、その他の鍵交換装置の貢献データとコミットメントを受信する。ここで、その他の鍵交換装置の貢献データの全ての集合を貢献データ集合と呼ぶ。【００４３】
署名部１３３は、公開鍵１２３と秘密鍵１２４とを用いて、その他の鍵交換装置の貢献データ集合に対する署名である同意確認署名１３２を生成する。なお、署名部１３３は、同意確認署名１３２を生成するための署名方式として、アグリゲート署名を用いる。【００４４】
補助データ生成部１３４は、その他の鍵交換装置の貢献データ集合と、内部状態保存部１２６に保存された貢献乱数と、を用いて、補助データを生成する。【００４５】
詳細には、補助データ生成部１３４は、貢献データ集合の中から、その他の２つの鍵交換装置の貢献データを取り出し、一方の鍵交換装置の２個の貢献データの１つと他方の鍵交換装置の２個の貢献データの１つとの全ての組合せについて、補助データを生成する。ここで、補助データの全ての集合を補助データ集合１２８と呼ぶ。【００４６】
通信部１２５は、補助データ生成部１３４にて生成された補助データ集合１２８と、内部状態保存部１２６に保存されたコミットメントの開示情報と、署名部１３３にて生成された同意確認署名１３２と、を、通信回線１２７を介して、その他の鍵交換装置に送付する。【００４７】
また、通信部１２５は、通信回線１２７を介して、その他の鍵交換装置の補助データ集合とコミットメントの開示情報と同意確認署名とを受信する。【００４８】
署名検証部１３６は、相手識別子集合１２０および相手公開鍵集合１２１と、その他の鍵交換装置の貢献データ集合と、を用いて、その他の鍵交換装置の同意確認署名の正当性を検証する。【００４９】
開示情報検証部１３７は、相手識別子集合１２０と、その他の鍵交換装置の貢献データ集合とを用いて、その他の鍵交換装置のコミットメントの開示情報の正当性を検証する。【００５０】
補助データ検証部１３８は、相手識別子集合１２０と、その他の鍵交換装置の貢献データ集合および補助データ集合と、を用いて、その他の鍵交換装置の補助データの正当性を検証する。【００５１】
共有鍵生成部１３９は、署名検証部１３６、開示情報検証部１３７、および補助データ検証部１３８の全てで正当性が検証された場合に、その他の鍵交換装置の貢献データ集合、コミットメントの開示情報、および補助データと、内部状態保存部１２６に保存された貢献乱数と、を用いて、共有鍵１３５を生成し出力する。【００５２】
なお、貢献乱数生成部１０２、選択部１０３、コミットメント生成部１０４、貢献データ生成部１１０、内部状態保存部１２６、セッション番号生成部１３０、署名部１３３、補助データ生成部１３４、署名検証部１３６、開示情報検証部１３７、補助データ検証部１３８、および共有鍵生成部１３９は、同じ位数の群Ｇ，ＧＴであって、群Ｇに属する２つの要素から群ＧＴへの双線形写像が存在する２つの群Ｇ，ＧＴの計算手段を構成している。また、貢献データおよび補助データは群Ｇの元である。【００５３】
このような前提の下、補助データ検証部１３８は、貢献データおよび補助データの双線形写像を用いて、補助データの正当性を検証する。【００５４】
以下に、上記のように構成された鍵交換装置１００の動作について説明する。【００５５】
鍵交換装置１００（ｉ）のそれぞれには、ｊ＝｛１，．．．，ｎ｝￥ｉのそれぞれの鍵交換装置１００（ｊ）の識別子Ｕ［ｊ］の集合である相手識別子集合１２０と、鍵交換装置１００（ｊ）の公開鍵ｐｋ［ｊ］の集合である相手公開鍵集合１２１（ｐｉｄ）と、が入力される。また、自身の鍵交換装置１００（ｉ）の識別子１２２および公開鍵１２３（ｐｋ［ｉ］）と、この公開鍵１２３（ｐｋ［ｉ］）に対応する秘密鍵１２４（ｓｋ［ｉ］）と、が入力される。さらに、乱数１０１が入力される。【００５６】
まず、鍵交換装置１００（ｉ）は、貢献乱数生成部１０２において、乱数１０１を用いて、２個の貢献乱数１０５，１０６（ｒ［ｉ，０］，ｒ［ｉ，１］∈Ｚ／ｑＺ）の組をランダムに生成する。【００５７】
次に、鍵交換装置１００（ｉ）は、貢献データ生成部１１０において、貢献乱数生成部１０２にて生成された２個の貢献乱数１０５，１０６（ｒ［ｉ，０］，ｒ［ｉ，１］∈Ｚ／ｑＺ）の組を用いて、２個の貢献データ１１１，１１２（ｙ［ｉ，０］＝ｇｒ［ｉ，０］，ｙ［ｉ，１］＝ｇｒ［ｉ］）の組を生成する。【００５８】
ここでは、貢献乱数と貢献データは、それぞれ２個ずつであるが、複数であれば何個でも良い。【００５９】
次に、鍵交換装置１００（ｉ）は、選択部１０３において、貢献データ生成部１１０にて生成された２個の貢献データの１つを指定する番号１０７（ｂ［ｉ］∈｛０，１｝）をランダムに選ぶ。【００６０】
次に、鍵交換装置１００（ｉ）は、コミットメント生成部１０４において、選択部１０３にて選択された番号１０７（ｂ［ｉ］）のコミットメント１０８（ｃｏｍ［ｉ］）と、その開示情報１０９（ｄｅｃ［ｉ］）を生成する。【００６１】
次に、鍵交換装置１００（ｉ）は、通信部１２５において、（Ｕ［ｉ］，ｐｉｄ，ｙ［ｉ，０］，ｙ［ｉ，１］．ｃｏｍ［ｉ］）を、相手識別子集合１２０に属する識別子で識別される他の鍵交換装置に送付する。【００６２】
また、鍵交換装置１００（ｉ）は、内部状態保存部１２６において、ｐｉｄ，ｙ［ｉ，０］，ｙ［ｉ，１］，ｃｏｍ［ｉ］，ｄｅｃ［ｉ］，ｂ［ｉ］，ｒ［ｉ，ｂ［ｉ］］を内部状態として保存する。【００６３】
鍵交換装置１００（ｉ）は、ｊ＝｛１，．．．，ｎ｝￥ｉのそれぞれの鍵交換装置１００（ｊ）が通信回線１２７を介してｐｉｄ，ｙ［ｊ，０］，ｙ［ｊ，１］．ｃｏｍ［ｊ］を送付してくるのを通信部１２５にて待つ。【００６４】
そして、全ての（ｐｉｄ，ｙ［ｉ，０］，ｙ［ｉ，１］．ｃｏｍ［ｉ］）が揃ったならば、鍵交換装置１００（ｉ）は、次の処理に進む。ここで、鍵交換装置１００（ｊ）からの貢献データ集合とコミットメントからなるデータ（ｐｉｄ，（ｙ［１，０］，ｙ［１，１］．ｃｏｍ［１］，ｙ［２，０］，ｙ［２，１］．ｃｏｍ［２］，．．．，ｙ［ｎ，０］，ｙ［ｎ，１］．ｃｏｍ［ｎ］））を、同意データ１１９と呼ぶ。【００６５】
次に、鍵交換装置１００（ｉ）は、補助データ生成部１３４において、同意データ１１９の中から２つの鍵交換装置１００（ｊ）（隣接装置１，２と呼ぶ）の貢献データを取り出し、隣接装置１，２の貢献データと内部状態保存部１２６内の貢献乱数を用いて、補助データ集合１２８（ｘ［ｉ，０，０］＝（ｙ［ｉ−１，０］／ｙ［ｉ＋１，０］）ｒ［ｉ，ｂ［ｉ］］，ｘ［ｉ，０，１］＝（ｙ［ｉ−１，０］／ｙ［ｉ＋１，１］）ｒ［ｉ，ｂ［ｉ］］，ｘ［ｉ，１，０］＝（ｙ［ｉ−１，１］／ｙ［ｉ＋１，０］）ｒ［ｉ，ｂ［ｉ］］，ｘ［ｉ，１，１］＝（ｙ［ｉ−１，１］／ｙ［ｉ＋１，１］）ｒ［ｉ，ｂ［ｉ］］）を生成する。【００６６】
次に、鍵交換装置１００（ｉ）は、隣接装置２の貢献データと、内部状態保存部１２６内の貢献乱数および開示情報と、を用いて、隣接貢献乱数データ１２９（ｚ［ｉ，０］＝ｅ（ｙ［ｉ＋１，０］，ｖ）ｒ［ｉ，ｂ［ｉ］］，ｚ［ｉ，１］＝ｅ（ｙ［ｉ＋１，１］，ｖ）ｒ［ｉ，ｂ［ｉ］］）を生成する。【００６７】
次に、鍵交換装置１００（ｉ）は、セッション番号生成部１３０において、同意データ１１９のハッシュ値（ｓｉｄ＝Ｈａｓｈ（ｐｉｄ，ｙ［１，０］，ｙ［１，１］，ｃｏｍ［１］，ｙ［２，０］，ｙ［２，１］，ｃｏｍ［２］，．．．，ｙ［ｎ，０］，ｙ［ｎ，１］，ｃｏｍ［ｎ］））を生成する。このハッシュ値をセッション番号１３１と呼ぶ。【００６８】
また、鍵交換装置１００（ｉ）は、署名部１３３において、公開鍵１２３と秘密鍵１２４を用いて、セッション番号１３１に対する署名である同意確認署名１３２（ｓｉｇ［ｉ］）を生成する。【００６９】
次に、鍵交換装置１００（ｉ）は、通信部１２５において、（Ｕ［ｉ］，ｓｉｄ，ｂ［ｉ］，ｄｅｃ［ｉ］，ｘ［ｉ，０，０］，ｘ［ｉ，０，１］，ｘ［ｉ，１，０］，ｘ［ｉ，１，１］，ｓｉｇ［ｉ］）を、相手識別子集合１２０に属する識別子で識別される他の鍵交換装置に送付する。【００７０】
また、鍵交換装置１００（ｉ）は、内部状態保存部１２６において、内部状態を、（ｓｉｄ，ｐｉｄ，（ｙ［１，０］，ｙ［１，１］，ｃｏｍ［１］，ｙ［２，０］，ｙ［２，１］，ｃｏｍ［２］，．．．，ｙ［ｎ，０］，ｙ［ｎ，１］，ｃｏｍ［ｎ］），ｂ［ｉ］，ｘ［ｉ，０，０］，ｘ［ｉ，０，１］，ｘ［ｉ，１，０］，ｘ［ｉ，１，１］，ｚ［ｉ，０］，ｚ［ｉ，１］）に更新する。【００７１】
鍵交換装置１００（ｉ）は、ｊ＝｛１，．．．，ｎ｝￥ｉのそれぞれの鍵交換装置１００（ｊ）が通信回線１２７を介して、（Ｕ［ｊ］，ｓｉｄ，ｂ［ｊ］，ｄｅｃ［ｊ］，ｘ［ｊ，０，０］，ｘ［ｊ，０，１］，ｘ［ｊ，１，０］，ｘ［ｊ，１，１］，ｓｉｇ［ｊ］）を送付してくるのを通信部１２５にて待つ。【００７２】
そして、全ての（Ｕ［ｊ］，ｓｉｄ，ｂ［ｊ］，ｄｅｃ［ｊ］，ｘ［ｊ，０，０］，ｘ［ｊ，０，１］，ｘ［ｊ，１，０］，ｘ［ｊ，１，１］，ｓｉｇ［ｊ］）が揃ったならば、鍵交換装置１００（ｉ）は、次の処理に進む。【００７３】
次に、鍵交換装置１００（ｉ）は、署名検証部１３６において、ｉを除く全てのｊに関して、相手公開鍵集合１２１を用いて、ｓｉｇ［ｊ］が、鍵交換装置１００（ｊ）によるｓｉｄに対する正当な署名であることを確認する。【００７４】
また、鍵交換装置１００（ｉ）は、ｉを除く全てのｊに関して、（ｙ［ｊ，ｂ［ｊ，ｂ［ｊ］］，ｘ［ｊ，ｂ［ｊ−１］，ｂ［ｊ＋１］］）がＧの要素であることを確認する。【００７５】
また、鍵交換装置１００（ｉ）は、開示情報検証部１３７において、ｉを除く全てのｊに関して、ｄｅｃ［ｊ］を用いて、ｃｏｍ［ｊ］がｂ［ｊ］のコミットメントであることを確認する。【００７６】
また、鍵交換装置１００（ｉ）は、補助データ検証部１３８において、ｉを除く全てのｊに関して、ｅ（ｘ［ｊ，ｂ［ｊ−１］，ｂ［ｊ＋１］］，ｇ）＝ｅ（ｙ［ｊ−１，ｂ［ｊ−１］］／ｙ［ｊ＋１，ｂ［ｊ＋１］］，ｙ［ｊ，ｂ［ｊ］］）が成り立つことを確認する。【００７７】
以上全てが成り立てば、鍵交換装置１００（ｉ）は、共有鍵生成部１３９において、共有鍵１３５（ｓｋ＝ｚ［ｉ，ｂ［ｉ＋１］］ｎｅ（Πｊ＝１ｎｘ［ｉ＋ｊ，ｂ［ｉ＋ｊ−１］，ｂ［ｉ＋ｊ＋１］］ｎ＋１−ｊ，ｖ）を生成する。【００７８】
その後、鍵交換装置１００（ｉ）は、（ｓｉｄ，ｐｉｄ，ｓｋ）を出力する。【００７９】
本実施形態の特徴として、各鍵交換装置１００（ｉ）が２つの貢献データｙ［ｉ，０］，ｙ［ｉ，１］を生成することが挙げられる。そして、本実施形態では、その他の全ての鍵交換装置１００（ｊ）から集められた２個の貢献データを含むデータを連結したものをセッション番号ｓｉｄとしている。【００８０】
これに対して、従来方式では、貢献データを１つしか生成せず、また、貢献データを連結したものをセッション番号とすることができない。そのため、余計なデータ配布フェーズが必要であった。従来方式で、貢献データを連結したものをセッション番号とすることができなかった理由は次の通りである。【００８１】
グループ鍵交換が安全であるためには、次のような条件を満たす必要がある。その条件とは、ある鍵交換の結果として生成された鍵が攻撃者に漏洩しても、問題となる鍵交換を行っている全ての鍵交換装置の、この鍵交換に関する内部状態が攻撃者に漏洩していないことである。【００８２】
上記条件で鍵交換が安全であることを示すには、この鍵交換に関する内部状態が漏洩せずとも鍵を推測できる攻撃者が存在したならば、その攻撃者に対し、解くことが難しいとされる何らかの問題が解けることを示す必要がある。そのためには、何らかの問題が与えられた時に、まず、この問題を構成するデータを、鍵交換の貢献データとして攻撃者に渡す。この場合、貢献乱数が分からないので、攻撃者に貢献データを渡した者も交換されるべき鍵が何か分からない。しかし、攻撃者が後に鍵を推測してきたら、その推測結果を基にして与えられた問題を解くのである。一方、問題を構成するデータを含まない貢献データに対応する貢献乱数は、攻撃者が要求すれば開示する必要がある（問題とは関係ないデータは、攻撃者に漏洩しても、安全性に影響を与えないという条件があるため）。【００８３】
ここで問題となるのは、攻撃者がどの鍵を攻撃するか分からないこと、また、どの貢献データの組から鍵を構成するか分からないことである。攻撃者は、各鍵交換装置を複数回起動させ、各鍵交換装置に貢献データを複数出力させ、その中の貢献データを適当に組み合わせて１つのセッションを決定し、そのセクションに対応する鍵を推測する。このような場合、問題を構成するデータを貢献データとして渡すには、攻撃者が選ぶ貢献データの組にピッタリとこのデータが含まれていなければならない。例えば、ｎ個の鍵交換装置がそれぞれｔ個の貢献データを生成する場合、貢献データの集合の選び方はｔｎ通りある。すると、問題を埋め込んだ貢献データの組合せが選ばれる確率は１／ｔｎになる。もし、ｎが少し大きくなれば、この確率は著しく低くなるため、貢献データに問題を埋め込んで攻撃者に解かせ得る確率は著しく低くなってしまう。【００８４】
ところが、本実施形態のように、２つの貢献データを生成する場合、一方の貢献データに問題を埋め込み、他方の貢献データを、貢献乱数を開示可能な貢献データとしておくことができる。これにより、攻撃者から貢献乱数の要求があれば、常に、鍵生成に使う予定であったと主張して、開示可能な貢献乱数を開示することができ、また、攻撃の対象となれば、問題を埋め込んだ貢献データを鍵生成に利用する予定であったと主張することができる。もちろん、本実施形態では、コミットメントを利用し、予め決められた貢献データしか鍵生成に使えないのだが、攻撃者を騙して問題を解かせるときは、落とし戸を使って、都合の良い方を使うのである。【００８５】
上述したように本実施形態によれば、複数の鍵交換装置で秘密の鍵を共有する場合に、互いにデータを配布する回数が２回で済む。しかも、鍵生成にあたり、予め固有のセッション番号を各鍵交換装置に入力する必要がない。このセッション番号を生成するためには、各鍵交換装置が他の鍵交換装置の全てにデータを配布して決定する必要がある。このような１対Ｎの通信は、同期を取ることなどに多くの時間を費やすため、短時間で終了することは、単純な暗号計算と比べて難しい。本実施形態では、この通信のフェーズを減らしているため、より効率的な鍵の交換が可能になる。実際、全体としては、従来よりも１回少ない２回だけデータ配布フェーズを要求している。【００８６】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されものではない。本願発明の構成や詳細には、本願発明の範囲内で当業者が理解し得る様々な変更をすることができる。【００８７】
本出願は、２００７年８月９日に出願された日本出願特願２００７−２０８１９７を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００８８】
複数の鍵交換装置による鍵交換は、ネットワーク上で多人数のユーザーが会議を開く場合などに有効である。メンバー外のユーザーが会議に参加したり、会議の内容を盗聴したりすることができないようにするために、会議メンバーで共有する秘密鍵を、本発明による鍵交換装置を用いて事前に決定することができる。
【図１】
2009019932.tif 000003
【図２】
2009019932.tif 000004
【図３】
2009019932.tif 000005
【図４】
2009019932.tif 000006
【手続補正書】
【提出日】平成20年10月22日(2008.10.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、および乱数が入力され、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成し出力する鍵交換装置であって、
前記乱数を用いて複数の貢献乱数を生成する貢献乱数生成部と、
前記複数の貢献乱数をそれぞれ用いて複数の貢献データを生成する貢献データ生成部と、
前記複数の貢献データの中から前記共有鍵の生成に用いる貢献データを指定する番号を選択する選択部と、
前記番号のコミットメントを生成するコミットメント生成部と、
前記番号の貢献乱数と前記コミットメントの開示情報とを内部状態として保存する内部状態保存部と、
前記複数の貢献データと前記コミットメントとを前記複数の相手装置に送信する通信部と、
前記複数の相手装置から前記通信部を介して受信した前記貢献データの全ての集合である貢献データ集合と、前記内部状態保存部に保存された前記貢献乱数と、を用いて、補助データを生成する補助データ生成部と、を有し、
前記補助データと前記コミットメントの開示情報とは、前記通信部により前記複数の相手装置に送信され、
前記複数の相手装置から前記通信部を介して受信した、前記貢献データ集合、前記コミットメントの開示情報、および前記補助データと、前記内部状態保存部に保存された前記貢献乱数と、を用いて、前記共有鍵を生成し出力する共有鍵生成部と、を有する、鍵交換装置。
【請求項２】
請求項１に記載の鍵交換装置において、
前記秘密鍵と前記公開鍵とを用いて、前記貢献データ集合に対する署名である同意確認署名を生成する署名部を有する、鍵交換装置。
【請求項３】
請求項２に記載の鍵交換装置において、
前記補助データ生成部は、前記貢献データ集合の中から２つの相手装置の貢献データを取り出し、一方の相手装置の複数の貢献データの１つと他方の相手装置の複数の貢献データの１つとの全ての組合せについて、前記補助データを生成し、
前記通信部は、前記補助データの全ての集合である補助データ集合と、前記同意確認署名と、前記コミットメントの開示情報と、を前記複数の相手装置に送信し、
前記相手識別子集合と、前記複数の相手装置から前記通信部を介して受信した前記貢献データ集合および前記補助データ集合と、を用いて、前記複数の相手装置から前記通信部を介して受信した前記補助データの正当性を検証する補助データ検証部と、
前記相手識別子集合および前記相手公開鍵集合と、前記複数の相手装置から前記通信部を介して受信した前記貢献データ集合と、を用いて、前記複数の相手装置から前記通信部を介して受信した前記同意確認署名の正当性を検証する署名検証部と、
前記相手識別子集合と、前記複数の相手装置から前記通信部を介して受信した前記貢献データ集合と、を用いて、前記複数の相手装置から前記通信部を介して受信した前記コミットメントの開示情報の正当性を検証する開示情報検証部と、を有し、
前記共有鍵生成部は、前記補助データ検証部、前記署名検証部、および前記開示情報検証部の全てで正当性が検証された場合に、前記共有鍵を生成し出力する、鍵交換装置。
【請求項４】
請求項３に記載の鍵交換装置において、
同じ位数の群Ｇ，ＧＴであって、群Ｇに属する２つの要素から群ＧＴへの双線形写像が存在する２つの群Ｇ，ＧＴの計算手段を有し、
前記貢献データおよび前記補助データは群Ｇの元であって、
前記補助データ検証部は、前記貢献データおよび前記補助データの双線形写像を用いて、前記補助データの正当性を検証する、鍵交換装置。
【請求項５】
請求項２から４のいずれか１項に記載の鍵交換装置において、
前記署名を生成するのに用いる署名方式がアグリゲート署名である、鍵交換装置。
【請求項６】
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、および乱数が入力され、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成し出力する鍵交換装置による鍵交換方法であって、
前記乱数を用いて複数の貢献乱数を生成する貢献乱数生成ステップと、
前記複数の貢献乱数をそれぞれ用いて複数の貢献データを生成する貢献データ生成ステップと、
前記複数の貢献データの中から前記共有鍵の生成に用いる貢献データを指定する番号を選択する選択ステップと、
前記番号のコミットメントを生成するコミットメント生成ステップと、
前記番号の貢献乱数と前記コミットメントの開示情報とを内部状態として保存する内部状態保存ステップと、
前記複数の貢献データと前記コミットメントとを前記複数の相手装置に送信する通信ステップと、
前記複数の相手装置から受信した前記貢献データの全ての集合である貢献データ集合と、前記内部状態保存ステップで保存された前記貢献乱数と、を用いて、補助データを生成する補助データ生成ステップと、を有し、
前記通信ステップでは、前記補助データと前記コミットメントの開示情報とを、前記複数の相手装置に送信し、
前記複数の相手装置から受信した、前記貢献データ集合、前記コミットメントの開示情報、および前記補助データと、前記内部状態保存ステップで保存された前記貢献乱数と、を用いて、前記共有鍵を生成し出力する共有鍵生成ステップをさらに有する、鍵交換方法。
【請求項７】
請求項６に記載の鍵交換方法において、
前記秘密鍵と前記公開鍵とを用いて、前記貢献データ集合に対する署名である同意確認署名を生成する署名ステップをさらに有する、鍵交換方法。
【請求項８】
請求項７に記載の鍵交換方法において、
前記補助データ生成ステップでは、前記貢献データ集合の中から２つの相手装置の貢献データを取り出し、一方の相手装置の複数の貢献データの１つと他方の相手装置の複数の貢献データの１つとの全ての組合せについて、前記補助データを生成し、
前記通信ステップでは、前記補助データの全ての集合である補助データ集合と、前記同意確認署名と、前記コミットメントの開示情報と、を前記複数の相手装置に送信し、
前記相手識別子集合と、前記複数の相手装置から受信した前記貢献データ集合および前記補助データ集合と、を用いて、前記複数の相手装置から受信した前記補助データの正当性を検証する補助データ検証ステップと、
前記相手識別子集合および前記相手公開鍵集合と、前記複数の相手装置から受信した前記貢献データ集合と、を用いて、前記複数の相手装置から受信した前記同意確認署名の正当性を検証する署名検証ステップと、
前記相手識別子集合と、前記複数の相手装置から受信した前記貢献データ集合と、を用いて、前記複数の相手装置から受信した前記コミットメントの開示情報の正当性を検証する開示情報検証ステップと、を有し、
前記共有鍵生成ステップでは、前記補助データ検証ステップ、前記署名検証ステップ、および前記開示情報検証ステップの全てで正当性が検証された場合に、前記共有鍵を生成し出力する、鍵交換方法。
【請求項９】
請求項８に記載の鍵交換方法において、
同じ位数の群Ｇ，ＧＴであって、群Ｇに属する２つの要素から群ＧＴへの双線形写像が存在する２つの群Ｇ，ＧＴを計算する計算ステップをさらに有し、
前記貢献データおよび前記補助データは群Ｇの元であって、
前記補助データ検証ステップでは、前記貢献データおよび前記補助データの双線形写像を用いて、前記補助データの正当性を検証する、鍵交換方法。
【請求項１０】
請求項７から９のいずれか１項に記載の鍵交換方法において、
前記署名を生成するのに用いる署名方式がアグリゲート署名である、鍵交換方法。
【請求項１１】
公開鍵、秘密鍵、識別子、相手公開鍵集合、相手識別子集合、および乱数が入力され、前記相手識別子集合に属する識別子で識別される複数の相手装置と通信を行い、共有鍵を生成し出力する鍵交換装置に、
前記乱数を用いて複数の貢献乱数を生成する貢献乱数生成手順と、
前記複数の貢献乱数をそれぞれ用いて複数の貢献データを生成する貢献データ生成手順と、
前記複数の貢献データの中から前記共有鍵の生成に用いる貢献データを指定する番号を選択する選択手順と、
前記番号のコミットメントを生成するコミットメント生成手順と、
前記番号の貢献乱数と前記コミットメントの開示情報とを内部状態として保存する内部状態保存手順と、
前記複数の貢献データと前記コミットメントとを前記複数の相手装置に送信する通信手順と、
前記複数の相手装置から受信した前記貢献データの全ての集合である貢献データ集合と、前記内部状態保存手順で保存された前記貢献乱数と、を用いて、補助データを生成する補助データ生成手順と、を実行させ、
前記通信手順では、前記補助データと前記コミットメントの開示情報とを、前記複数の相手装置に送信し、
前記鍵交換装置に、
前記複数の相手装置から受信した、前記貢献データ集合、前記コミットメントの開示情報、および前記補助データと、前記内部状態保存手順で保存された前記貢献乱数と、を用いて、前記共有鍵を生成し出力する共有鍵生成手順をさらに実行させる、プログラム。
【請求項１２】
請求項１１に記載のプログラムにおいて、
前記鍵交換装置に、
前記秘密鍵と前記公開鍵とを用いて、前記貢献データ集合に対する署名である同意確認署名を生成する署名手順をさらに実行させる、プログラム。
【請求項１３】
請求項１２に記載のプログラムにおいて、
前記補助データ生成手順では、前記貢献データ集合の中から２つの相手装置の貢献データを取り出し、一方の相手装置の複数の貢献データの１つと他方の相手装置の複数の貢献データの１つとの全ての組合せについて、前記補助データを生成し、
前記通信手順では、前記補助データの全ての集合である補助データ集合と、前記同意確認署名と、前記コミットメントの開示情報と、を前記複数の相手装置に送信し、
前記鍵交換装置に、
前記相手識別子集合と、前記複数の相手装置から受信した前記貢献データ集合および前記補助データ集合と、を用いて、前記複数の相手装置から受信した前記補助データの正当性を検証する補助データ検証手順と、
前記相手識別子集合および前記相手公開鍵集合と、前記複数の相手装置から受信した前記貢献データ集合と、を用いて、前記複数の相手装置から受信した前記同意確認署名の正当性を検証する署名検証手順と、
前記相手識別子集合と、前記複数の相手装置から受信した前記貢献データ集合と、を用いて、前記複数の相手装置から受信した前記コミットメントの開示情報の正当性を検証する開示情報検証手順と、をさらに実行させ、
前記共有鍵生成手順では、前記補助データ検証手順、前記署名検証手順、および前記開示情報検証手順の全てで正当性が検証された場合に、前記共有鍵を生成し出力する、プログラム。
【請求項１４】
請求項１３に記載のプログラムにおいて、
前記鍵交換装置に、
同じ位数の群Ｇ，ＧＴであって、群Ｇに属する２つの要素から群ＧＴへの双線形写像が存在する２つの群Ｇ，ＧＴを計算する計算手順をさらに実行させ、
前記貢献データおよび前記補助データは群Ｇの元であって、
前記補助データ検証手順では、前記貢献データおよび前記補助データの双線形写像を用いて、前記補助データの正当性を検証する、プログラム。
【請求項１５】
請求項１２から１４のいずれか１項に記載のプログラムにおいて、
前記署名を生成するのに用いる署名方式がアグリゲート署名である、プログラム。
【国際調査報告】
2009019932.tif 000007
2009019932.tif 000008
2009019932.tif 000009
2009019932.tif 000010