(57)【要約】  鍵交換装置は、i≠sとし、jを鍵交換の回数とし、kを0以上jより小さい整数の何れかとし、当該鍵交換装置の秘密鍵とは異なる情報である共有秘密情報mkikが記憶される共有秘密鍵記憶部と、共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加部と、外部から鍵交換情報es及び鍵交換情報esに対応する認証情報σsを受け取り、上記共有秘密情報mkikを用いて上記認証情報σsを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証部とを含み、上記共有秘密情報mkikは、鍵交換の生成過程で利用する値である。
2019093478.tif 000002
【特許請求の範囲】
【請求項１】
鍵交換装置であって、
i≠sとし、jを鍵交換の回数とし、kを0以上jより小さい整数の何れかとし、
当該鍵交換装置の秘密鍵とは異なる情報である共有秘密情報mkikが記憶される共有秘密鍵記憶部と、
共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加部と、
外部から鍵交換情報es及び鍵交換情報esに対応する認証情報σsを受け取り、上記共有秘密情報mkikを用いて上記認証情報σsを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証部とを含み、
上記共有秘密情報mkikは、鍵交換の生成過程で利用する値である、
鍵交換装置。
【請求項２】
請求項１の鍵交換装置であって、
当該鍵交換装置の秘密鍵が記憶される記憶部と、
鍵交換の過程で生成される関連情報xと上記秘密鍵と上記共有秘密情報mkikとを用いて、共有秘密情報mkijを求める共有秘密鍵共有部とを含む、
鍵交換装置。
【請求項３】
請求項１または請求項２の鍵交換装置であって、
上記共有秘密情報は、MAC鍵、または、AES鍵であり、
外部から鍵交換情報esを受け取る際、及び、鍵交換情報eiを外部へ出力する際に、KY Protocolに基づき処理を行う、
鍵交換装置。
【請求項４】
鍵交換サーバ装置とn台の鍵交換装置iとを含む鍵交換システムであって、
i≠sとし、i=1,2,…,nとし、jを鍵交換の回数とし、kを0以上jより小さい整数の何れかとし、
上記鍵交換装置iは、
当該鍵交換装置iの秘密鍵とは異なる情報である共有秘密情報mkikが記憶される共有秘密鍵記憶部と、
共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加部と、
外部から鍵交換情報es_i及び鍵交換情報es_iに対応する認証情報σs_iを受け取り、上記共有秘密情報mkikを用いて上記認証情報σs_iを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証部とを含み、
上記鍵交換サーバ装置は、当該鍵交換サーバ装置の秘密鍵とは異なる情報である共有秘密情報mk1k,…,mknkが記憶される第二共有秘密鍵記憶部と、
共有秘密情報mk1k,…,mknkを用いて、外部へ出力する鍵交換情報es_1,…,es_nに対して認証及び改ざんを検知する認証情報σs_1,…,σs_nを生成する第二認証情報付加部と、
外部から鍵交換情報e1,…,en及び鍵交換情報e1,…,enにそれぞれ対応する認証情報σ1,…,σnを受け取り、上記共有秘密情報mk1k,…,mknkを用いて上記認証情報σ1,…,σnをそれぞれ検証し、検証に失敗した場合、失敗した鍵交換装置との鍵交換を停止する第二認証情報検証部とを含む、
鍵交換システム。
【請求項５】
請求項４の鍵交換システムであって、
上記共有秘密情報は、MAC鍵、または、AES鍵であり、
外部から鍵交換情報e1,…,enを受け取る際、及び、鍵交換情報es_1,…,es_nを外部へ出力する際に、KY Protocolに基づき処理を行う、
鍵交換システム。
【請求項６】
鍵交換装置を用いる鍵交換方法であって、
i≠sとし、jを鍵交換の回数とし、kを0以上jより小さい整数の何れかとし、
上記鍵交換装置の共有秘密鍵記憶部には、上記鍵交換装置の秘密鍵とは異なる情報である共有秘密情報mkikが記憶されるものとし、
上記鍵交換装置が、共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加ステップと、
上記鍵交換装置が、外部から鍵交換情報es及び鍵交換情報esに対応する認証情報σsを受け取り、上記共有秘密情報mkikを用いて上記認証情報σsを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証ステップとを含む、
鍵交換方法。
【請求項７】
鍵交換サーバ装置とn台の鍵交換装置iとを用いる鍵交換方法であって、
i≠sとし、i=1,2,…,nとし、jを鍵交換の回数とし、kを0以上jより小さい整数の何れかとし、
上記鍵交換装置iの共有秘密鍵記憶部には、上記鍵交換装置iの秘密鍵とは異なる情報である共有秘密情報mkikが記憶されるものとし、上記鍵交換サーバ装置の共有秘密鍵記憶部には、当該鍵交換サーバ装置の秘密鍵とは異なる情報である共有秘密情報mk1k,…,mknkが記憶されるものとし、
上記鍵交換サーバ装置と上記n台の鍵交換装置iとの間でそれぞれ共有秘密情報mkikを共有する初回共有秘密鍵共有ステップと、
上記鍵交換装置iが、共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加ステップと、
上記鍵交換サーバ装置が、外部から鍵交換情報e1,…,en及び鍵交換情報e1,…,enにそれぞれ対応する認証情報σ1,…,σnを受け取り、上記共有秘密情報mk1k,…,mknkを用いて上記認証情報σ1,…,σnをそれぞれ検証し、検証に失敗した場合、失敗した鍵交換装置との鍵交換を停止する第二認証情報検証ステップと、
上記鍵交換サーバ装置が、共有秘密情報mk1k,…,mknkを用いて、外部へ出力する鍵交換情報es_1,…,es_nに対して認証及び改ざんを検知する認証情報σs_1,…,σs_nを生成する第二認証情報付加ステップと、
上記鍵交換装置iが、外部から鍵交換情報es_i及び鍵交換情報es_iに対応する認証情報σs_iを受け取り、上記共有秘密情報mkikを用いて上記認証情報σs_iを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証ステップとを含む、
鍵交換方法。
【請求項８】
請求項１から請求項３の何れかの鍵交換装置として、コンピュータを機能させるための鍵交換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報通信分野における鍵交換技術で、他の通信装置と通信する通信装置、通信装置が実行する通信システムに関するものである。
【背景技術】
【０００２】
複数装置の間で暗号化等に使用する同一の鍵（セッション鍵）を共有する技術に鍵交換プロトコルがある。鍵交換プロトコルの中には、長期的に使用する秘密鍵（長期秘密鍵）を用いてセッション鍵を交換するものがある。【０００３】
その一例として、Two-round Dynamic Multi-Cast Key Distribution Protocol（以下KY Protocolともいう、非特許文献１参照）がある。KY Protocolを利用すれば、ユーザの動的な変更（通話やメッセージグループへの参加や退出等）に合わせて効率的に再度セッション鍵の交換が可能である。そして、KY Protocolには、いくらユーザ数が増加しても各ユーザの鍵交換に必要なコスト（計算コストや通信コスト等）は一定であるといった特徴がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】K. Yoneyama, R. Yoshida, Y. Kawahara, T. Kobayashi, H. Fuji,and T. Yamamoto: "Multi-cast Key Distribution: Scalable, Dynamic and Provably Secure Construction", Proc. of ProvSec 2016, pp. 207-226, Nanjing, China, Nov. 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
長期秘密鍵を使用して鍵交換を行うプロトコルでは、長期秘密鍵が攻撃者に漏洩した後に、攻撃者が漏洩した装置になりすまし、鍵交換に加わる攻撃が可能になる場合がある。すると、鍵交換技術における長期秘密鍵漏洩後になりすましによりセッション鍵が漏洩する。【０００６】
例えば、KY Protocolでも長期秘密鍵が漏洩した後に攻撃者はセッション鍵を取得することができる。KY Protocolはサーバを中心として複数のユーザがサーバと通信を行うスター型のネットワークを使用している。鍵交換に際して、ユーザとサーバはそれぞれ長期秘密鍵と短期秘密鍵を使用して、ユーザ間でセッション鍵の交換をする。しかし、長期秘密鍵は不揮発メモリ上に長期間保管して使用される。そのため、長期秘密鍵は攻撃者に漏洩しないように安全に保管する必要が生じる。KY Protocolの安全性に関しては、以下の特徴がある。
１．Ephemeral Key Exposure Resilience：ユーザの短期秘密鍵が漏洩しても漏洩前のセッション鍵は安全である
２．Time-based Backward Secrecy：あるセッション鍵の前後のセッション鍵が漏洩してもあるセッション鍵自体を推測することはできない
３．Strong Server Key Forward Secrecy：ユーザやサーバの長期秘密鍵が漏洩しても漏洩前にセッションコンプリートしたセッション鍵は安全である【０００７】
上記の３．のようにKY Protocolでは長期秘密鍵が漏洩しても、漏洩前のセッションで共有されたセッション鍵の情報は漏れない。しかし、長期秘密鍵が漏洩した後に行われるセッションで共有されたセッション鍵は攻撃者の手に渡る可能性がある。具体的にはサーバの長期秘密鍵が漏洩した際、攻撃者はサーバに成りすまして鍵交換に参加することができる。攻撃者がサーバに成りすました後、ユーザ間でセッションが行われる際に秘密裏に攻撃者が鍵交換に加わることで攻撃者にもセッション鍵が共有される。また、ユーザの長期秘密鍵が漏洩した場合は、攻撃者はユーザに成りすまし、セッションに参加することができるため、セッション鍵が攻撃者に共有される。【０００８】
このように実際に鍵交換プロトコルには長期秘密鍵が攻撃者に漏洩した後に攻撃者によってセッション鍵が取得されるプロトコルが存在する。現状、サーバやユーザ端末等への侵入によって、情報が漏洩するケースは容易に考えられる。このような問題を防ぐためには、サーバやユーザが長期秘密鍵を漏洩しないように安全に保管する必要がある。安全な保管は、サーバやユーザの負担となる。【０００９】
本発明は、長期鍵漏洩後のセッション鍵の推測を防ぐことができる鍵交換装置、鍵交換システム、鍵交換方法、鍵交換プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、本発明の一態様によれば、鍵交換装置は、i≠sとし、jを鍵交換の回数とし、kを0以上jより小さい整数の何れかとし、当該鍵交換装置の秘密鍵とは異なる情報である共有秘密情報mkikが記憶される共有秘密鍵記憶部と、共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加部と、外部から鍵交換情報es及び鍵交換情報esに対応する認証情報σsを受け取り、上記共有秘密情報mkikを用いて上記認証情報σsを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証部とを含み、上記共有秘密情報mkikは、鍵交換の生成過程で利用する値である。【００１１】
上記の課題を解決するために、本発明の他の態様によれば、鍵交換システムは、鍵交換サーバ装置とn台の鍵交換装置iとを含む。i≠sとし、i=1,2,…,nとし、jを鍵交換の回数とし、kを0以上jより小さい整数の何れかとし、鍵交換装置iは、当該鍵交換装置iの秘密鍵とは異なる情報である共有秘密情報mkikが記憶される共有秘密鍵記憶部と、共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加部と、外部から鍵交換情報es_i及び鍵交換情報es_iに対応する認証情報σs_iを受け取り、上記共有秘密情報mkikを用いて上記認証情報σs_iを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証部とを含む。鍵交換サーバ装置は、当該鍵交換サーバ装置の秘密鍵とは異なる情報である共有秘密情報mk1k,…,mknkが記憶される第二共有秘密鍵記憶部と、共有秘密情報mk1k,…,mknkを用いて、外部へ出力する鍵交換情報es_1,…,es_nに対して認証及び改ざんを検知する認証情報σs_1,…,σs_nを生成する第二認証情報付加部と、外部から鍵交換情報e1,…,en及び鍵交換情報e1,…,enにそれぞれ対応する認証情報σ1,…,σnを受け取り、上記共有秘密情報mk1k,…,mknkを用いて上記認証情報σ1,…,σnをそれぞれ検証し、検証に失敗した場合、失敗した鍵交換装置との鍵交換を停止する第二認証情報検証部とを含む。【００１２】
上記の課題を解決するために、本発明の他の態様によれば、鍵交換方法は鍵交換装置を用いる。i≠sとし、kを0以上の整数の何れかとし、鍵交換装置の共有秘密鍵記憶部には、鍵交換装置の秘密鍵とは異なる情報である共有秘密情報mkikが記憶されるものとし、鍵交換装置が、共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加ステップと、鍵交換装置が、外部から鍵交換情報es及び鍵交換情報esに対応する認証情報σsを受け取り、上記共有秘密情報mkikを用いて上記認証情報σsを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証ステップとを含む。【００１３】
上記の課題を解決するために、本発明の他の態様によれば、鍵交換方法は鍵交換サーバ装置とn台の鍵交換装置iとを用いる。i≠sとし、i=1,2,…,nとし、kを0以上の整数の何れかとし、鍵交換装置iの共有秘密鍵記憶部には、鍵交換装置iの秘密鍵とは異なる情報である共有秘密情報mkikが記憶されるものとし、鍵交換サーバ装置の共有秘密鍵記憶部には、当該鍵交換サーバ装置の秘密鍵とは異なる情報である共有秘密情報mk1k,…,mknkが記憶されるものとし、鍵交換サーバ装置とn台の鍵交換装置iとの間でそれぞれ共有秘密情報mkikを共有する初回共有秘密鍵共有ステップと、鍵交換装置iが、共有秘密情報mkikを用いて、外部へ出力する鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成する認証情報付加ステップと、鍵交換サーバ装置が、外部から鍵交換情報e1,…,en及び鍵交換情報e1,…,enにそれぞれ対応する認証情報σ1,…,σnを受け取り、上記共有秘密情報mk1k,…,mknkを用いて上記認証情報σ1,…,σnをそれぞれ検証し、検証に失敗した場合、失敗した鍵交換装置との鍵交換を停止する第二認証情報検証ステップと、鍵交換サーバ装置が、共有秘密情報mk1k,…,mknkを用いて、外部へ出力する鍵交換情報es_1,…,es_nに対して認証及び改ざんを検知する認証情報σs_1,…,σs_nを生成する第二認証情報付加ステップと、鍵交換装置iが、外部から鍵交換情報es_i及び鍵交換情報es_iに対応する認証情報σs_iを受け取り、上記共有秘密情報mkikを用いて上記認証情報σs_iを検証し、検証に失敗した場合、鍵交換を停止する認証情報検証ステップとを含む。
【発明の効果】
【００１４】
本発明によれば、長期鍵漏洩後のセッション鍵の推測を防ぐことができるという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】第一実施形態に係る鍵交換システムの構成図。
【図２】第一実施形態に係る鍵交換装置の機能ブロック図。
【図３】第一実施形態に係る鍵交換サーバ装置の機能ブロック図。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について、説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。以下の説明において、テキスト中で使用する記号「^」「~」等は、本来直前の文字の真上に記載されるべきものであるが、テキスト記法の制限により、当該文字の直後に記載する。式中においてはこれらの記号は本来の位置に記述している。また、ベクトルや行列の各要素単位で行われる処理は、特に断りが無い限り、そのベクトルやその行列の全ての要素に対して適用されるものとする。
【００１７】
＜第一実施形態のポイント＞
第一実施形態では、攻撃者がユーザやサーバに成りすますことを防ぐために、以前のセッション鍵の交換の過程で使用した情報（共有秘密情報=MAC鍵）と長期秘密鍵の二つの情報を用いた認証を行う鍵交換プロトコルを提案する。
【００１８】
本実施形態では、共有秘密情報固定方式について説明する。
【００１９】
本実施形態では、既存の鍵交換プロトコルに対して、以下のステップを鍵交換ステップの前に加える。
【００２０】
（初回共有秘密鍵共有ステップ）
鍵交換装置と鍵交換の相手の鍵交換装置は、認証に使える長期秘密鍵を所有していない場合のみ自身の長期秘密鍵SSKと長期公開鍵SPKを作成し、SSKを保存し、PKI等の技術を使用し改ざんを防止しながらSPKの交換を行う。そして、鍵交換装置と鍵交換の相手の鍵交換装置は、自身の長期秘密鍵SSKを利用してなりすましや改ざんを防止する情報を付け足しながら、鍵共有を行い、初回共有秘密鍵mki0を共有、保存する。
【００２１】
次に、既存の鍵交換アルゴリズムの鍵交換装置間の送受信時に以下の様にステップを修正する。
【００２２】
（鍵交換の送受信時ステップ）
鍵交換装置２００−ｉと鍵交換の相手の鍵交換装置２００−ｍの間でj回目の鍵交換を行うとする。その際に、各鍵交換装置は、情報送信時には、各鍵交換装置間で必要な情報に対して、j回目以前の共有秘密鍵mkik(0≦k<j)を使用して、なりすましと改ざん検知のための情報を付け足してから送信する。各鍵交換装置は、情報受信時には、最初になりすましと検知のための情報を共有秘密鍵mkikを使用してチェックし、正しくなければ鍵交換アルゴリズムを停止し、正しいときに鍵交換アルゴリズムを継続する。
【００２３】
なお、本実施形態では、前提として、初回共有秘密鍵共有ステップ時は攻撃者の関与なしに正しくアルゴリズムを終える事ができるとする。鍵交換の送受信時ステップとして、鍵交換装置と鍵交換の相手の鍵交換装置は、その間で送信する情報に対して、自身のSSKとj回目以前の共有秘密鍵mkikを使ってなりすましと改ざんを防止するための情報を付け加える。すると、長期秘密鍵が漏洩しても、共有秘密鍵mkikは安全に保管されているため、鍵交換を行う際の各通信のなりすましと改ざん検知のための情報を攻撃者は偽造する事ができない。これにより、鍵交換装置と鍵交換の相手の鍵交換装置は、攻撃者によるなりすましを防ぐ事ができる。従って、長期秘密鍵の漏洩によりセッション鍵が漏洩するという課題を解決する事ができる。
【００２４】
＜表記法＞
以下に、本実施形態で使用する記号の表記法を説明する。
U:={u1,u2,…uN}  グループに所属するユーザの集合
u:={u1,u2,…un|ui∈U}  鍵交換に参加するユーザの集合。なお、グループに所属するユーザの全部または一部が鍵交換に参加するものとする。よって、n≦Nである。
(ski,pki)  uiの秘密鍵と公開鍵
(sks,pks)  サーバの秘密鍵と公開鍵
mkij  uiとサーバの間で共有されるj回目の共有秘密鍵(本実施形態ではセキュリティパラメータkのメッセージ認証子（MAC）の鍵)
p  素数
G  位数pの有限巡回群
g,h  Gの生成元
κ  セキュリティパラメータ
Kspaceκ  κビットの鍵空間
TCR:{0,1}*→{0,1}κ  標的衝突困難ハッシュ関数
tPRF:{0,1}κ×Kspaceκ×Kspaceκ×{0,1}κ→ Z p  ねじれ疑似ランダム関数(参考文献１参照)
tPRF’:{0,1}κ×Kspaceκ×Kspaceκ×{0,1}κ→ Zp  ねじれ擬似ランダム関数
F:{0,1}κ×G→ Zp2  疑似ランダム関数
F':{0,1}κ×Zp→ Kspaceκ   擬似ランダム関数
F'':{0,1}κ×Kspaceκ→{0,1}κ  疑似ランダム関数
F''':{0,1}κ×Kspaceκ→Z p  擬似ランダム関数
TFti:={timeti_1,timeti_2,…,timeti_tn}  特定区間の時間の集合（Time Frame）、ti=1,2,…,fn
TF:={TF1,TF2,…,TFfn}  Time Frameの集合
PRF: {0,1}*→{0,1}κ  擬似ランダム関数
(参考文献１) Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa, and Kazuki Yoneyama. "Strongly secure authenticated key exchange from factoring, codes, and lattices". Des. Codes Cryptography, 76(3):469-504, 2015.
【００２５】
＜第一実施形態＞
図１は第一実施形態に係る鍵交換システムの構成図を示す。
【００２６】
鍵交換システムは、鍵交換サーバ装置１００と、n台の鍵交換装置２００−ｉとを含む。各装置は、通信回線等を介して接続されており、相互に通信可能とする。i=1,2,…,nとする。
【００２７】
鍵交換サーバ装置１００及びn台の鍵交換装置２００−ｉはそれぞれ、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。鍵交換サーバ装置１００及びn台の鍵交換装置２００−ｉはそれぞれ、例えば、中央演算処理装置の制御のもとで各処理を実行する。鍵交換サーバ装置１００及びn台の鍵交換装置２００−ｉに入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。鍵交換サーバ装置１００及びn台の鍵交換装置２００−ｉの各処理部はそれぞれ、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。鍵交換サーバ装置１００及びn台の鍵交換装置２００−ｉがそれぞれ備える各記憶部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００２８】
図２は鍵交換サーバ装置１００の機能ブロック図を示す。鍵交換サーバ装置１００は、秘密鍵記憶部１０１、共有秘密鍵記憶部１０２、鍵交換アルゴリズム部１０３、認証情報検証部１０４、認証情報付加部１０５、共有秘密鍵共有部１０６とを含む。まず、各部の処理概要を説明する。
【００２９】
＜秘密鍵記憶部１０１＞
秘密鍵記憶部１０１には、鍵交換サーバ装置１００の秘密鍵が記憶される。
【００３０】
＜共有秘密鍵記憶部１０２＞
共有秘密鍵記憶部１０２には、鍵交換サーバ装置１００の秘密鍵とは異なる情報であり、鍵交換装置２００−ｉとの間で共有可能な共有秘密情報mk1k-1,…,mknk-1が記憶される。本実施形態では、共有秘密情報を固定とするため、k-1=0とする。
【００３１】
＜鍵交換アルゴリズム部１０３＞
鍵交換アルゴリズム部１０３は、外部(鍵交換装置２００−ｉ)からの鍵交換情報e1,…,enを入力として受け入れ、鍵交換の途中に生成される関連情報xを共有秘密鍵共有部１０６へ出力し、鍵交換に必要な鍵交換情報es_1,…,es_nを外部(鍵交換装置２００−ｉ)へ出力する。
【００３２】
＜認証情報検証部１０４＞
認証情報検証部１０４は、外部(鍵交換装置２００−ｉ)からの認証情報σ1,…,σnを入力とし、それぞれ共有秘密情報mk1k-1,…,mknk-1を使用して認証情報σ1,…,σnを検証する。認証情報検証部１０４は、検証に失敗した場合、失敗した鍵交換装置との鍵交換アルゴリズムを停止させる。
【００３３】
＜認証情報付加部１０５＞
認証情報付加部１０５は、鍵交換アルゴリズム部１０３が出力した鍵交換情報es_1,…,es_nを入力とし、それぞれ共有秘密情報mk1k-1,…,mknk-1を使用して鍵交換情報es_1,…,es_nに対して認証及び改ざんを検知する認証情報σs_1,…,σs_nを生成し、鍵交換アルゴリズム部１０３へ送信する。
【００３４】
＜共有秘密鍵共有部１０６＞
共有秘密鍵共有部１０６は、鍵交換アルゴリズム部１０３の鍵交換が出力する上記関連情報xを入力とし、秘密鍵と共有秘密情報mk1k-1,…,mknk-1を使用して、共有秘密情報mk1k,…,mknkを求め、共有秘密鍵記憶部１０２に保存する。
【００３５】
次に鍵交換装置２００−ｉについて説明する。
【００３６】
図３は、鍵交換装置２００−ｉの機能ブロック図を示す。n台の鍵交換装置２００−ｉはそれぞれ、秘密鍵記憶部２０１、共有秘密鍵記憶部２０２、鍵交換アルゴリズム部２０３、認証情報検証部２０４、認証情報付加部２０５、共有秘密鍵共有部２０６とを含む。まず、各部の処理概要を説明する。
【００３７】
＜秘密鍵記憶部２０１＞
秘密鍵記憶部２０１には、鍵交換装置２００−ｉの秘密鍵が記憶される。
【００３８】
＜共有秘密鍵記憶部２０２＞
共有秘密鍵記憶部２０２には、鍵交換装置２００−ｉの秘密鍵とは異なる情報であり、鍵交換サーバ装置１００との間で共有可能な共有秘密情報mkikが記憶される。
【００３９】
＜鍵交換アルゴリズム部２０３＞
鍵交換アルゴリズム部２０３は、外部(鍵交換サーバ装置１００)からの鍵交換情報es_iを入力として受け入れ、鍵交換の途中に生成される関連情報xを共有秘密鍵共有部２０６へ出力し、鍵交換に必要な鍵交換情報eiを外部(鍵交換サーバ装置１００)へ出力する。
【００４０】
＜認証情報検証部２０４＞
認証情報検証部２０４は、外部(鍵交換サーバ装置１００)からの認証情報σs_iを入力とし、それぞれ共有秘密情報mkik-1を使用して鍵交換アルゴリズム部２０３の認証情報σs_iを検証する。認証情報検証部２０４は、検証に失敗した場合、鍵交換サーバ装置１００との鍵交換アルゴリズムを停止させる。
【００４１】
＜認証情報付加部２０５＞
認証情報付加部２０５は、鍵交換アルゴリズム部２０３が出力した鍵交換情報eiを入力とし、共有秘密情報mkik-1を使用して鍵交換アルゴリズム部２０３の鍵交換情報eiに対して認証及び改ざんを検知する認証情報σiを生成し、鍵交換アルゴリズム部２０３へ送信する。
【００４２】
＜共有秘密鍵共有部２０６＞
共有秘密鍵共有部２０６は、鍵交換アルゴリズム部２０３の鍵交換の途中に生成される関連情報xを入力とし、秘密鍵と共有秘密情報mkik-1を使用して、共有秘密情報mk1k,…,mknkを求め、鍵交換装置２００−ｉの共有秘密鍵記憶部２０２に保存する。
【００４３】
以下、処理の流れに沿って、各部の処理内容を説明する。
【００４４】
第一実施形態では、KY Protocolをベースとした応用プロトコルを提案する。KY Protocol同様、本応用プロトコルは｛Setup, Dist, Join, Leave, Update｝の5つのフェーズで構成される。｛Join, Leave, Update｝フェーズについても同様の適応が可能であるが、SetupとDistフェーズのみ記載する。また、本応用プロトコルでは、サーバSとユーザu:={u1,u2,…un|ui∈U}の間で鍵交換が行われるとし、PKIベースのKY Protocolを記述する。
【００４５】
本応用プロトコルは、初回共有秘密鍵共有ステップと共有秘密鍵更新ステップでは、長期秘密鍵としてRSA暗号の秘密鍵を、共有秘密鍵としてMAC鍵を用いる。本応用プロトコルは、共有秘密鍵共有時はRSA暗号の署名を用いて認証及び改ざん検知を行い、DH鍵共有で鍵を共有する。なお、本発明はRSA暗号の署名以外にも、DSAやECDSA等、認証及び改ざん検知に使用される一般的な署名技術を利用する事が可能であり、DH鍵共有も同様に一般的な鍵交換技術を利用する事が可能である。
【００４６】
本実施形態では、共有秘密情報固定方式を採用するため、j回目の鍵交換の送受信時ステップにおいて初回共有秘密鍵mki0を使ってMACのタグを付加して認証及び改ざん防止を行う。ただし、共有秘密情報固定方式を採用し、1つ以上前の共有秘密鍵のMAC鍵mkikを使ってMACのタグを付加して認証及び改ざん防止を行ってもよい。なお、kは0以上jより小さい整数の何れかであり、鍵交換の相手との間で予めkをどのような値にするかを決定しておけばよい。
【００４７】
従来のKY ProtocolではDistの最初にMAC鍵を作り、Distの一部通信に対してMACのタグを生成する。本実施形態では、MAC鍵を共有秘密鍵として使用しているため、これを使用しないでプロトコルを構成する。他にも、Round1とRound2のユーザの同一性を確認するコミットメントCi=gk_ihs_iや各ユーザが代表ユーザ(本実施形態ではユーザu1を代表ユーザとしている)のkiやsiを持っているかを確認するコミットメントC1=gk_1hs_1も使用しないで構成する。なお、上付き添え字及び上付き添え字において、A_BはABを、A^BはABを意味する。また、集合Sから一様ランダムに集合Sの元xを取り出す事を意味する記号として、x∈RSと表記する。
【００４８】
・Setup:
1.  各ユーザuiの利用する鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、kをセキュリティパラメータとして、公開鍵暗号方式(Gen,Enc,Dec)の鍵生成アルゴリズムGenを用いて、公開鍵暗号方式の秘密鍵ski、公開鍵pkiを生成する((ski,pki)←Gen(1k))。さらに、鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、kをセキュリティパラメータとして、ランダムビット列からなる秘密情報(sti,st'i)を生成する（sti∈RKspaceκ、st'i∈R{0,1}k）。
【００４９】
鍵交換アルゴリズム部２０３は、(ski,sti,st'i)を長期秘密鍵SSKiとして秘密鍵記憶部２０１に保存し、PKIなどの公開鍵pkiとユーザを紐付ける技術を用いて、pkiを長期公開鍵SPKiとして鍵交換サーバ装置１００に公開する。
2.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、kをセキュリティパラメータとして、属性情報Aiを定義するために使われる情報attを用いて、属性ベース暗号の秘密鍵生成(Params,msk)←Setup(1k、att)を行う。鍵交換アルゴリズム部１０３は、kをセキュリティパラメータとして、公開鍵暗号方式(Gen,Enc,Dec)の鍵生成アルゴリズムGenを用いて、公開鍵暗号方式の秘密鍵sks、公開鍵pksを生成する((sks,pks)←Gen(1k))。さらに、鍵交換アルゴリズム部１０３は、kをセキュリティパラメータとして、ランダムビット列からなる秘密情報(sts,st's)を生成する（sts∈RKspaceκ、st's∈R{0,1}k）。
【００５０】
鍵交換アルゴリズム部１０３は、(msk,sks,sts,st's)を長期秘密鍵SSKsとして秘密鍵記憶部１０１に保存し、PKIなどの公開鍵pksとユーザを紐付ける技術を用いて、(Params,p,G,g,h,TCR,tPRF,tPRF',F,F',F'',F''',pks)を長期公開鍵SPKsとして図示しない記憶部に保存し、各鍵交換装置２００−ｉに公開する。
【００５１】
・初回共有秘密鍵共有ステップ：
1.  各鍵交換装置２００−ｉの共有秘密鍵共有部２０６は、長期公開鍵SPKsを取得し、長期公開鍵SPKsに含まれるgを用いて、乱数aiとga_iを作成する。共有秘密鍵共有部２０６は、秘密鍵記憶部２０１から秘密鍵skiを取り出し、秘密鍵skiを用いて、署名アルゴリズムSigにより、署名σi0を作成し(σi0←Sigsk_i(ga_i))、鍵交換アルゴリズム部２０３に署名データを渡す。鍵交換アルゴリズム部２０３が鍵交換サーバ装置１００に(ga_i、σi0)を送信する。
2.  鍵交換サーバ装置１００の共有秘密鍵共有部１０６は、鍵交換アルゴリズム部１０３を経由して(ga_i,σi0)を受け取り、検証アルゴリズムVerを用いて、署名σi0を検証する(1 or ⊥←Verpk_i(ga_i,σi0))。共有秘密鍵共有部１０６は、検証に失敗した場合(⊥が出力された場合)、鍵交換アルゴリズムを停止する。共有秘密鍵共有部１０６は、検証に成功した場合(1が出力された場合)、長期公開鍵SPKsに含まれるgを用いて、乱数bとgbを作成する。共有秘密鍵共有部１０６は、秘密鍵記憶部１０１から秘密鍵sksを取り出し、秘密鍵sksを用いて、署名アルゴリズムSigにより、署名σs0を作成し(σs0←Sigsk_s(gb))、鍵交換アルゴリズム部１０３を経由して各鍵交換装置２００−ｉに(gb,σs0)を送信する。さらに、共有秘密鍵共有部１０６は、各鍵交換装置２００−ｉから受け取ったga_iと作成した乱数bとを用いてga_ibを作成し、MAC鍵を生成するアルゴリズムMGenを用いて、mki0←MGen(ga_ib)を作成する。共有秘密鍵共有部１０６は、mki0(ただしi=1,2,…,n)を共有秘密鍵として共有秘密鍵記憶部１０２に保存する。
3.  各鍵交換装置２００−ｉの共有秘密鍵共有部２０６は、鍵交換アルゴリズム部２０３を経由して(gb,σs0)を受け取り、長期公開鍵SPKsに含まれるpksと検証アルゴリズムVerを用いて、署名σs0を検証する(1 or ⊥←Verpk_s(gb,σs0))。共有秘密鍵共有部２０６は、検証に失敗した場合(⊥が出力された場合)、鍵交換アルゴリズムを停止する。共有秘密鍵共有部２０６は、検証に成功した場合(1が出力された場合)、鍵交換装置２００−ｉが生成した乱数aiと鍵交換サーバ装置１００から受け取ったgbとを用いてga_ibを作成し、MAC鍵を生成するアルゴリズムMGenを用いて、mki0←MGen(ga_ib)を作成する。共有秘密鍵共有部２０６は、mki0(ここでは、ｉは鍵交換装置２００−ｉに対応する1つの値)を共有秘密鍵として共有秘密鍵記憶部２０２に保存する。
【００５２】
ここまでの処理により、鍵交換サーバ装置１００と鍵交換装置２００−ｉとが共有秘密鍵mki0を共有する。
【００５３】
・Dist:
(State Update at New Time Frame)
特定のTFtiにはじめてセッションを行う鍵交換装置２００−ｉは鍵交換サーバ装置１００と以下のプロセスを行う。
1.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、鍵交換装置２００−ｉから接続要求があった場合、その現在時刻に対応する特定区間の時間timejiとユーザの識別子uiからAi=(ui,timeji)を作成し、属性情報とする。ただし、特定区間の時間timejiを含む特定区間の時間の集合をTFji:={timeji_1,timeji_2,…,time ji_tn}とすると、jiはji_1,ji_2,…,ji_tnのうちの現在時刻に対応する値である。鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、属性ベース暗号の暗号化アルゴリズムであり、ユーザの属性情報に対応する鍵を生成するアルゴリズムDerを用いて、Params、msk、Aiからユーザの属性秘密鍵uskiを生成する(uski←Der(Params,msk,Ai))。さらに、鍵交換アルゴリズム部１０３は、鍵交換装置２００−ｉの公開鍵pkiを取得し、公開鍵pkiを用いて公開鍵暗号方式の暗号化アルゴリズムEncによりuskiを暗号化し(CTi←Encpk_i(uski))、暗号文CTiを鍵交換装置２００−ｉに送信する。ここでは、i=1,2,…,nである。
2.  各鍵交換装置２００−ｉは、暗号文CTiを受け取り、秘密鍵記憶部２０１から秘密鍵skiを取り出し、公開鍵暗号方式の復号アルゴリズムDecにより暗号文CTiを復号し(uski←Decsk_i(CTi))、属性秘密鍵uskiを図示しない記憶部stateiに保存する。
【００５４】
（Round1 for Users）
1.  各鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、r~i∈R {0,1}k、r~'i∈RKspaceκ、k~i∈R {0,1}k、k~'i∈R Kspaceκ、s~i∈R {0,1}k、s~'i∈R Kspaceκを作成し、図示しない記憶部ESKiに保存する。そして、鍵交換アルゴリズム部２０３は、ri=tPRF(r~i,r~'i,sti,st'i)、ki=tPRF(k~i,k~'i,sti,st'i)、si=tPRF(s~i,s~'i,sti,st'i)を生成する。さらに、鍵交換アルゴリズム部２０３は、Ri=gr_i、Ci=gk_ihs_iを作成する。
2.  各鍵交換装置２００−ｉの認証情報付加部２０５は、共有秘密鍵mkij-1を共有秘密鍵記憶部２０２から取り出し、署名アルゴリズムTagにより、作成したRiとCiとから署名σi1を次式により計算する。
σi1=Tag_(mkij-1)(Ri,Ci)
鍵交換アルゴリズム部２０３は（Ri,Ci,σi1）を鍵交換サーバ装置１００に送付する。ただし、Tag_(mkij-1)は
【００５５】
【数１】
2019093478.tif 000003
【００５６】
を意味する。また、本実施形態では、共有秘密鍵固定方式を採用しているため、mkij-1=mki0である。なお、RiとCiを鍵交換情報ともいい、署名σi1を認証情報ともいう。
【００５７】
（Round1 for Server）
1.  鍵交換サーバ装置１００の認証情報検証部１０４は、鍵交換アルゴリズム部１０３を経由して各鍵交換装置２００−ｉから（Ri,Ci,σi1）を取得し、共有秘密鍵mkij-1を共有秘密鍵記憶部２０２から取り出し、検証アルゴリズムVerにより、次式により検証を行う。Ver_(mkij-1)(Ri,Ci,σi1)
認証情報検証部１０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部１０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。ただし、Ver_(mkij-1)は
【００５８】
【数２】
2019093478.tif 000004
【００５９】
を意味する。
2.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、各鍵交換装置２００−ｉから（Ri,Ci,σi1）を取得し、sid=TCR(C1,…,Cn)を計算し、代表ユーザを一人選ぶ。本実施形態ではユーザu1を代表ユーザとする。認証情報付加部１０５は、sidとR1,…,Rnを用いて署名アルゴリズムTagにより、
σsev_i1=Tag_(mkij-1)(sid,Ri-1,Ri+1)
を計算し、鍵交換アルゴリズム部１０３を経由して各鍵交換装置２００−ｉへ（sid,Ri-1,Ri+1,σsev_i1）を送付し、代表ユーザに対しては代表ユーザである事も伝える。
【００６０】
（Round2 for Users）
1.  i∈[1,n]である鍵交換装置２００−ｉの認証情報検証部２０４は、（sid,Ri-1,Ri+1,σsev_i1）を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mkij-1)(sid,Ri-1,Ri+1,σsev_i1)
認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。なお、sid,Ri-1,Ri+1を外部(鍵交換サーバ装置１００)からの鍵交換情報ともいい、σsev_i1を認証情報ともいう。
2.  i∈[2,n]である鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、Ki(l)=F(sid,Ri-1r_i)、Ki(r)=F(sid,Ri+1r_i)、Ti=Ki(l) xor Ki(r)を計算する。ただし、xorは
【００６１】
【数３】
2019093478.tif 000005
【００６２】
を意味する。認証情報付加部２０５は署名アルゴリズムTagを用いて署名σi2を計算し(σi2=Tag_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid))、鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００に対して、(ki,si,Ti,σi2)を送信する。
3.  代表ユーザであるユーザu1の鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、K1(l)=F(sid,Rnr_1)、K1(r)=F(sid,R2r_1)、T1=K1(l) xor K1(r)、T'=K1(l) xor (k1||s1)を計算する。認証情報付加部２０５は署名アルゴリズムTagを用いて署名σ12を計算し(σ12=Tag_(mk1j-1)(R1,c1,Rn,R2,T1,T',U1,sid))、鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００に対して、(T1,T',σ12)を送信する。
【００６３】
（Round2 for Server）
1.  鍵交換サーバ装置１００の認証情報検証部１０４は、鍵交換アルゴリズム部１０３を経由してi∈[2,n]である鍵交換装置２００−ｉから(ki,si,Ti,σi2)を取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,σi2)
認証情報検証部１０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部１０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  鍵交換サーバ装置１００の認証情報検証部１０４は、鍵交換アルゴリズム部１０３を経由して代表ユーザであるユーザu1の鍵交換装置２００−１から(T1,T',σ12)を取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mk1j-1)(R1,c1,Rn,R2,T1,T',U1,sid,σ12)
認証情報検証部１０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部１０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
3.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、kS~∈R {0,1}k、kS~'∈R Kspaceκ、K1~∈R {0,1}k、K1~'∈R Kspaceκを生成し、kS=tPRF(kS~,kS~',sts,st's)とK1=tPRF(K1~,K1~',sts,st's)とk'=( xor2≦i≦n ki) xor ksを計算する。
4.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、i∈[2,n]である鍵交換装置２００−ｉに対してTi'=( xor1≦j≦i-1 Tj)を計算する。
5.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、i∈[1,n]である鍵交換装置２００−ｉに対して、Pi:=(ID=Ui)∧(time∈TF)、CTi'=AEnc(Params,Pi,K1)を計算する。ただし、AEncは属性ベース暗号の暗号化アルゴリズムである。
6.  鍵交換サーバ装置１００の認証情報付加部１０５は、i∈[2,n]である鍵交換装置２００−ｉに対して、署名アルゴリズムTagを用いて、次式により署名σi2を計算する。
σi2=Tag_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,c1,k',Ti',T',CTi')
次に、認証情報付加部１０５は、(c1,k',T'i,T',CTi',σi2)を鍵交換アルゴリズム部１０３を経由しi∈[2,n]である鍵交換装置２００−ｉに送信する。
7.  鍵交換サーバ装置１００の認証情報付加部１０５は、代表ユーザであるユーザu1の鍵交換装置２００−１に対して、署名アルゴリズムTagを用いて、次式により署名σ12を計算する。
σ12=Tag_(mkij-1)(R1,c1,Rn,R2,T1,T',U1,sid,k',CT'1)
次に、認証情報付加部１０５は、鍵交換アルゴリズム部１０３を経由して(k',CT1',σ12)を鍵交換装置２００−１に送信する。
【００６４】
（Session Key Generation and Post Computation）
1.  i∈[2,n]である鍵交換装置２００−ｉの認証情報検証部２０４は、(c1,k',sid,T'i,T',CTi',σi2）を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,c1,k',Ti',T',CTi',σi2)
認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、K1(l)=T'ixor Ki(l)とk1||s1=T' xor K1(l)を計算し、属性ベース暗号の復号アルゴリズムADecにより、暗号文CT'iを次式により復号する。
K1←ADecusk_i(CT'i,Pi)
【００６５】
さらに、鍵交換アルゴリズム部２０３は、K2=F'(sid,k' xor k1)を計算し、セッション鍵SKをSK=F''(sid,K1) xor F''(sid,K2)により求める。
3.  i∈[2,n]である鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、sid、Hi(l)=Ri-1r_i、Hi(r)=Ri+1r_i、r=F'''(sid,K1) xor F'''(sid,K2)を図示しない記憶部stateiに保存する。
4.  代表ユーザであるユーザu1の鍵交換装置２００−１の認証情報検証部２０４は、(k',CT1',σ12)を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mk1j-1)(R1,c1,Rn,R2,T1,T',U1,sid,k',CT'1,σ12)
認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
5.  鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、属性ベース暗号の復号アルゴリズムADecにより、暗号文CT'1を次式により復号する。
K1←ADecusk_1(CT'1,P1)
【００６６】
さらに、鍵交換アルゴリズム部２０３は、K2=F'(sid, k' xor k1)を計算し、セッション鍵SKをSK=F''(sid,K1) xor F''(sid,K2)により求める。
6.  鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、sid、H1(l)=Rnr_i、H1(r)=R2r_i、r=F'''(sid,K1) xor F'''(sid,K2)を図示しない記憶部state1に保存する。
【００６７】
＜効果＞
以上の構成により、鍵交換サーバ装置に対してセッション鍵SKを秘匿したまま鍵交換装置間で鍵交換装置はセッション鍵SKを共有することができ、共有秘密情報=MAC鍵と長期秘密鍵の二つの情報を用いた認証を行い、長期鍵漏洩後のセッション鍵の推測を防ぐことができる。サーバやユーザの長期秘密鍵が情報漏洩しても、共有秘密鍵が漏洩していなければ、攻撃者によるセッション鍵の交換を防ぐことができる。
【００６８】
例えば、共有秘密情報を耐タンパ領域(サーバのHSMやスマートフォンのSIM等)に保存し、使用することが考えられる。共有秘密情報をMAC鍵等の鍵サイズが小さく計算コストの小さい情報とすることで、限られた耐タンパ領域を有効に利用することができる。
【００６９】
＜変形例＞
本実施形態では、鍵交換の相手が鍵交換サーバ装置の場合について、つまり、鍵交換装置と鍵交換サーバ装置との間での鍵交換について説明したが、鍵交換装置と鍵交換装置との間での鍵交換において本発明を適用してもよい。ある鍵交換装置が本実施形態の鍵交換装置として機能し、他の鍵交換装置が本実施形態の鍵交換サーバ装置として機能するように構成すればよい。
【００７０】
＜第二実施形態のポイント＞
第一実施形態と異なる部分を中心に説明する。
【００７１】
本実施形態では、上記の第一実施形態の共有秘密鍵部分をMAC鍵(mkij-1)ではなくAESの鍵(keyij-1)とし、各通信に付加する情報を署名σiではなくAESによる暗号文c'iとして送信し、復号に失敗した場合に鍵交換アルゴリズムを停止する。
【００７２】
＜第二実施形態＞
・Setup:
1.  各ユーザuiの利用する鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、kをセキュリティパラメータとして、公開鍵暗号方式(Gen,Enc,Dec)の鍵生成アルゴリズムGenを用いて、公開鍵暗号方式の秘密鍵ski、公開鍵pkiを生成する((ski,pki)←Gen(1k))。さらに、鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、kをセキュリティパラメータとして、ランダムビット列からなる秘密情報(sti,st'i)を生成する（sti∈RKspaceκ、st'i∈R{0,1}k）。
【００７３】
鍵交換アルゴリズム部２０３は、(ski,sti,st'i)を長期秘密鍵SSKiとして秘密鍵記憶部２０１に保存し、PKIなどの公開鍵pkiとユーザを紐付ける技術を用いて、pkiを長期公開鍵SPKiとして鍵交換サーバ装置１００に公開する。
2.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、kをセキュリティパラメータとして、属性情報Aiを定義するために使われる情報attを用いて、属性ベース暗号の秘密鍵生成(Params,msk)←Setup(1k、att)を行う。鍵交換アルゴリズム部１０３は、kをセキュリティパラメータとして、公開鍵暗号方式(Gen,Enc,Dec)の鍵生成アルゴリズムGenを用いて、公開鍵暗号方式の秘密鍵sks、公開鍵pksを生成する((sks,pks)←Gen(1k))。さらに、鍵交換アルゴリズム部１０３は、kをセキュリティパラメータとして、ランダムビット列からなる秘密情報(sts,st's)を生成する（sts∈RKspaceκ、st's∈R{0,1}k）。
【００７４】
鍵交換アルゴリズム部１０３は、(msk,sks,sts,st's)を長期秘密鍵SSKsとして秘密鍵記憶部１０１に保存し、PKIなどの公開鍵pksとユーザを紐付ける技術を用いて、(Params,p,G,g,h,TCR,tPRF,tPRF',F,F',F'',F''',pks)を長期公開鍵SPKsとして図示しない記憶部に保存し、各鍵交換装置２００−ｉに公開する。
【００７５】
・初回共有秘密鍵共有ステップ：
1.  各鍵交換装置２００−ｉの共有秘密鍵共有部２０６は、長期公開鍵SPKsを取得し、長期公開鍵SPKsに含まれるgを用いて、乱数aiとga_iを作成する。共有秘密鍵共有部２０６は、秘密鍵記憶部２０１から秘密鍵skiを取り出し、秘密鍵skiを用いて、署名アルゴリズムSigにより、署名σi0を作成し(σi0←Sigsk_i(ga_i))、鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００に(ga_i、σi0)を送信する。
2.  鍵交換サーバ装置１００の共有秘密鍵共有部１０６は、鍵交換アルゴリズム部１０３を経由して(ga_i,σi0)を受け取り、検証アルゴリズムVerを用いて、署名σi0を検証する(1 or ⊥←Verpk_i(ga_i,σi0))。共有秘密鍵共有部１０６は、検証に失敗した場合(⊥が出力された場合)、鍵交換アルゴリズムを停止する。共有秘密鍵共有部１０６は、検証に成功した場合(1が出力された場合)、長期公開鍵SPKsに含まれるgを用いて、乱数bとgbを作成する。共有秘密鍵共有部１０６は、秘密鍵記憶部１０１から秘密鍵sksを取り出し、秘密鍵sksを用いて、署名アルゴリズムSigにより、署名σsを作成し(σs←Sigsk_s(gb))、鍵交換アルゴリズム部１０３を経由して各鍵交換装置２００−ｉに(gb,σs)を送信する。さらに、共有秘密鍵共有部１０６は、各鍵交換装置２００−ｉから受け取ったga_iと作成した乱数bとを用いてga_ibを作成し、AES鍵を生成するアルゴリズムKeyGenを用いて、keyi0←KeyGen(ga_ib)を作成する。共有秘密鍵共有部１０６は、keyi0(ただしi=1,2,…,n)を共有秘密鍵として共有秘密鍵記憶部１０２に保存する。
3.  各鍵交換装置２００−ｉの共有秘密鍵共有部２０６は、(gb,σs0)を受け取り、長期公開鍵SPKsに含まれるpksと検証アルゴリズムVerを用いて、署名σs0を検証する(1 or ⊥←Verpk_s(gb,σs0))。共有秘密鍵共有部２０６は、検証に失敗した場合(⊥が出力された場合)、鍵交換アルゴリズムを停止する。共有秘密鍵共有部２０６は、検証に成功した場合(1が出力された場合)、鍵交換装置２００−ｉが生成した乱数aiと鍵交換サーバ装置１００から受け取ったgbとを用いてga_ibを作成し、AESの鍵を生成するアルゴリズムKeyGenを用いて、keyi0←KeyGen(ga_ib)を作成する。共有秘密鍵共有部２０６は、keyi0(ここでは、ｉは鍵交換装置２００−ｉに対応する1つの値)を共有秘密鍵として共有秘密鍵記憶部２０２に保存する。
【００７６】
ここまでの処理により、鍵交換サーバ装置１００と鍵交換装置２００−ｉとが共有秘密鍵keyi0を共有する。
【００７７】
・Dist:
(State Update at New Time Frame)
特定のTFtiにはじめてセッションを行う鍵交換装置２００−ｉは鍵交換サーバ装置１００と以下のプロセスを行う。
1.  鍵交換サーバ装置１００の鍵交換アルゴリズム部２０３は、鍵交換装置２００−ｉから接続要求があった場合、その現在時刻に対応する特定区間の時間timejiとユーザの識別子uiからAi=(ui,timeji)を作成し、属性情報とする。ただし、特定区間の時間timejiを含む特定区間の時間の集合をTFji:={timeji_1,timeji_2,…,time ji_tn}とすると、jiはji_1,ji_2,…,ji_tnのうちの現在時刻に対応する値である。鍵交換サーバ装置１００の鍵交換アルゴリズム部２０３は、属性ベース暗号の暗号化アルゴリズムであり、ユーザの属性情報に対応する鍵を生成するアルゴリズムDerを用いて、Params、msk、Aiからユーザの属性秘密鍵uskiを生成する(uski←Der(Params,msk,Ai))。さらに、鍵交換アルゴリズム部２０３は、鍵交換装置２００−ｉの公開鍵pkiを取得し、公開鍵pkiを用いて公開鍵暗号方式の暗号化アルゴリズムEncによりuskiを暗号化し(CTi←Encpk_i(uski))、暗号文CTiを鍵交換装置２００−ｉに送信する。ここでは、i=1,2,…,nである。
2.  各鍵交換装置２００−ｉは、暗号文CTiを受け取り、秘密鍵記憶部２０１から秘密鍵skiを取り出し、公開鍵暗号方式の復号アルゴリズムDecにより暗号文CTiを復号し(uski←Decsk_i(CTi))、属性秘密鍵uskiを図示しない記憶部stateiに保存する。
【００７８】
（Round1 for Users）
1.  各鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、r~i∈R{0,1}k、r~'i∈RKspaceκ、k~i∈R{0,1}k、k~'i∈RKspaceκ、s~i∈R{0,1}k、s~'i∈RKspaceκを作成し、図示しない記憶部ESKiに保存する。そして、認証情報付加部２０５は、ri=tPRF(r~i,r~'i,sti,st'i)、ki=tPRF(k~i,k~'i,sti,st'i)、si=tPRF(s~i,s~'i,sti,st'i)を生成する。さらに、認証情報付加部２０５は、Ri=gr_i、Ci=gk_ihs_iを作成する。
2.  各鍵交換装置２００−ｉの認証情報付加部２０５は、共有秘密鍵keyij-1を共有秘密鍵記憶部２０２から取り出し、公開鍵暗号方式の暗号化アルゴリズムEncにより、作成したRiとCiとから暗号文ci1を次式により計算する。
ci1=Enc_(keyij-1)(Ri,Ci)
認証情報付加部２０５は、（Ri,Ci,ci1）を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００に送付する。ただし、Enc_(keyij-1)は
【００７９】
【数４】
2019093478.tif 000006
【００８０】
を意味する。また、本実施形態では、共有秘密鍵固定方式を採用しているため、keyij-1=keyi0である。
【００８１】
（Round1 for Server）
1.  鍵交換サーバ装置１００の認証情報検証部１０４は、鍵交換アルゴリズム部１０３を経由して各鍵交換装置２００−ｉから（Ri,Ci,ci1）を取得し、共有秘密鍵keyij-1を共有秘密鍵記憶部２０２から取り出し、公開鍵暗号方式の暗号化アルゴリズムEncにより、
Enc_(keyij-1)(Ri,Ci)
を計算し、計算結果がci1と等しいかを検証する。認証情報検証部１０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部１０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  鍵交換サーバ装置１００の鍵交換アルゴリズム部1０３は、各鍵交換装置２００−ｉから（Ri,Ci,ci1）を取得し、sid=TCR(C1,…,Cn)を計算し、代表ユーザを一人選ぶ。本実施形態ではユーザu1を代表ユーザとする。認証情報付加部１０５は、sidとR1,…,Rnを用いて公開鍵暗号方式の暗号化アルゴリズムEncにより、
csev_i1=Enc_(keyij-1)(sid,Ri-1,Ri+1)
を計算し、鍵交換アルゴリズム部１０３を経由して各鍵交換装置２００−ｉへ（sid,Ri-1,Ri+1,csev_i1）を送付する。鍵交換アルゴリズム部１０３はその際、代表ユーザに対しては代表ユーザである事も伝える。
【００８２】
（Round2 for Users）
1.  i∈[1,n]である鍵交換装置２００−ｉの認証情報検証部２０４は、鍵交換アルゴリズム部２０３を経由して（sid,Ri-1,Ri+1,csev_i1）を鍵交換サーバ装置１００から取得し、公開鍵暗号方式の暗号化アルゴリズムEncにより、
Enc_(keyij-1)(sid,Ri-1,Ri+1)
を計算し、計算結果がcsev_i1と等しいかを検証する。
認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  i∈[2,n]である鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、Ki(l)=F(sid,Ri-1r_i)、Ki(r)=F(sid,Ri+1r_i)、Ti=Ki(l) xor Ki(r)を計算し、公開鍵暗号方式の暗号化アルゴリズムEncを用いて
ci2=Enc_(keyij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid)
を計算し、鍵交換サーバ装置１００に対して、鍵交換アルゴリズム部２０３を経由して(ki,si,Ti,ci2)を送信する。
3.  代表ユーザであるユーザu1の鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、K1(l)=F(sid,Rnr_1)、K1(r)=F(sid,R2r_1)、T1=K1(l) xor K1(r)、T'=K1(l) xor (k1||s1)を計算し、公開鍵暗号方式の暗号化アルゴリズムEncを用いて
c12=Enc_(key1j-1)(R1,c1,Rn,R2,T1,T',U1,sid)
を計算し、鍵交換サーバ装置１００に対して、鍵交換アルゴリズム部２０３を経由して(T1,T',c12)を送信する。
【００８３】
（Round2 for Server）
1.  鍵交換サーバ装置１００の認証情報検証部１０４は、鍵交換アルゴリズム部１０３を経由してi∈[2,n]である鍵交換装置２００−ｉから(ki,si,Ti,ci2)を取得し、公開鍵暗号方式の暗号化アルゴリズムEncにより、
Enc_(keyij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid)
を計算し、計算結果がci2と等しいかを検証する。認証情報検証部１０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部１０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  鍵交換サーバ装置１００の認証情報検証部１０４は、鍵交換アルゴリズム部１０３を経由して代表ユーザであるユーザu1の鍵交換装置２００−１から(T1,T',c12)を取得し、公開鍵暗号方式の暗号化アルゴリズムEncにより、
Enc_(key1j-1)(R1,c1,Rn,R2,T1,T',U1,sid)
を計算し、計算結果がc12と等しいかを検証する。認証情報検証部１０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部１０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
3.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、kS~∈R{0,1}k、kS~'∈RKspaceκ、K1~∈R{0,1}k、K1~'∈RKspaceκを生成し、kS=tPRF(kS~,kS~',sts,st's)とK1=tPRF(K1~,K1~',sts,st's)とk'=( xor2≦i≦n ki) xor ksを計算する。
4.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、i∈[2,n]である鍵交換装置２００−ｉに対してTi'=( xor1≦j≦i-1 Tj)を計算する。
5.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、i∈[1,n]である鍵交換装置２００−ｉに対して、Pi:=(ID=Ui)∧(time∈TF)、CTi'=AEnc(Params,Pi,K1)を計算する。
6.  鍵交換サーバ装置１００の認証情報付加部１０５は、i∈[2,n]である鍵交換装置２００−ｉに対して、公開鍵暗号方式の暗号化アルゴリズムEncにより、
csev_i2=Enc_(keyij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,c1,k',Ti',T',CTi')
を計算し、(c1,k',T'i,T',CTi',csev_i2)を鍵交換アルゴリズム部１０３を経由してi∈[2,n]である鍵交換装置２００−ｉに送信する。
7.  鍵交換サーバ装置１００の認証情報付加部１０５は、代表ユーザであるユーザu1の鍵交換装置２００−１に対して、公開鍵暗号方式の暗号化アルゴリズムEncにより、
csev_12=Enc_(keyij-1)(R1,c1,Rn,R2,T1,T',U1,sid,k',CT'1)
を計算し、鍵交換アルゴリズム部１０３を経由して(k',CT1',csev_12)を鍵交換装置２００−１に送信する。
【００８４】
（Session Key Generation and Post Computation）
1.  i∈[2,n]である鍵交換装置２００−ｉの認証情報検証部２０４は、(c1,k',sid,T'i,T',CTi',csev_i2）を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から取得し、公開鍵暗号方式の暗号化アルゴリズムEncにより、
Enc_(keyij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,c1,k',Ti',T',CTi')
を計算し、計算結果がcsev_i2と等しいかを検証する。認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、K1(l)=T'ixor Ki(l)とk1||s1=T' xor K1(l)を計算し、属性ベース暗号の復号アルゴリズムADecにより、暗号文CT'iを次式により復号する。
K1←ADecusk_i(CT'i,Pi)
【００８５】
さらに、鍵交換アルゴリズム部２０３は、K2=F'(sid,k' xor k1)を計算し、セッション鍵SKをSK=F''(sid,K1) xor F''(sid,K2)により求める。
3.  i∈[2,n]である鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、sid、Hi(l)=Ri-1r_i、Hi(r)=Ri+1r_i、r=F'''(sid,K1) xor F'''(sid,K2)を図示しない記憶部stateiに保存する。
4.  代表ユーザであるユーザu1の鍵交換装置２００−１の認証情報検証部２０４は、(k',CT1',csev_12)を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から取得し、公開鍵暗号方式の暗号化アルゴリズムEncにより、
Enc_(key1j-1)(R1,c1,Rn,R2,T1,T',U1,sid,k',CT'1)
を計算し、計算結果がcsev_12と等しいかを検証する。認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
5.  鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、属性ベース暗号の復号アルゴリズムADecにより、暗号文CT'1を次式により復号する。
K1←ADecusk_1(CT'1,P1)
【００８６】
さらに、鍵交換アルゴリズム部２０３は、K2=F'(sid,k' xor k1)を計算し、セッション鍵SKをSK=F''(sid,K1) xor F''(sid,K2)により求める。
6.  鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、sid、H1(l)=Rnr_i、H1(r)=R2r_i、r=F'''(sid,K1) xor F'''(sid,K2)を図示しない記憶部stateiに保存する。
【００８７】
＜効果＞
このような構成とすることで、第一実施形態と同様の効果を得ることができる。
【００８８】
＜第三実施形態のポイント＞
第一実施形態と異なる部分を中心に説明する。
【００８９】
第三実施形態では、共有秘密鍵更新方式を採用する。共有秘密鍵更新方式では、共有秘密鍵固定方式のステップに加えて、鍵交換アルゴリズムがセッション鍵を共有する前に以下のステップも挟む。
【００９０】
共有秘密鍵更新ステップ：
j回目のセッション鍵が交換される前に、鍵交換装置２００−ｉと鍵交換の相手の鍵交換装置２００−ｍの間で、鍵交換装置２００−ｉと鍵交換の相手の鍵交換装置２００−ｍが、自身の長期秘密鍵SSKとj回目以前(つまりk<j)の共有秘密鍵keyikを使用して、鍵共有を行い、j回目の共有秘密鍵keyijを共有する。その際の通信において、鍵交換装置２００−ｉと鍵交換の相手の鍵交換装置２００−ｍは、自身の長期秘密鍵SSKとj回目以前(つまりk<j)の共有秘密鍵keyikを利用してなりすましや改ざんを防止するための情報を付け加えながら共有する。共有後は、鍵交換装置２００−ｉと鍵交換の相手の鍵交換装置２００−ｍは、新しい共有秘密鍵keyijを保存する。
【００９１】
＜第三実施形態＞
第一実施形態と第三実施形態は、setup、初回共有秘密鍵共有ステップ、（Round2 for Users）、（Round2 for Server）及び（Session Key Generation and Post Computation）における処理内容が異なる。異なる部分を中心に説明する。
【００９２】
・Setup:
第三実施形態では、属性ベース暗号を用いない実施例で記述する。なお、本明細書で記述されるすべての実施形態は属性ベース暗号を用いても用いなくても構成可能である。
1.  各ユーザuiの利用する鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、kをセキュリティパラメータとして、公開鍵暗号方式(Gen,Enc,Dec)の鍵生成アルゴリズムGenを用いて、公開鍵暗号方式の秘密鍵ski、公開鍵pkiを生成する((ski,pki)←Gen(1k))。さらに、鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、kをセキュリティパラメータとして、ランダムビット列からなる秘密情報(sti,st'i)を生成する（sti∈RKspaceκ、st'i∈R{0,1}k）。
【００９３】
鍵交換アルゴリズム部２０３は、(ski,sti,st'i)を長期秘密鍵SSKiとして秘密鍵記憶部２０１に保存し、PKIなどの公開鍵pkiとユーザを紐付ける技術を用いて、pkiを長期公開鍵SPKiとして鍵交換サーバ装置１００に公開する。
2.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、kをセキュリティパラメータとして、公開鍵暗号方式(Gen,Enc,Dec)の鍵生成アルゴリズムGenを用いて、公開鍵暗号方式の秘密鍵sks、公開鍵pksを生成する((sks,pks)←Gen(1k))。さらに、鍵交換アルゴリズム部１０３は、kをセキュリティパラメータとして、ランダムビット列からなる秘密情報(sts,st's)を生成する（sts∈RKspaceκ、st's∈R{0,1}k）。
【００９４】
鍵交換アルゴリズム部１０３は、(sks,sts,st's)を長期秘密鍵SSKsとして秘密鍵記憶部１０１に保存し、PKIなどの公開鍵pksとユーザを紐付ける技術を用いて、(p,G,g,h,TCR,tPRF,tPRF',F,F',F'',F''',pks)を長期公開鍵SPKsとして図示しない記憶部に保存し、各鍵交換装置２００−ｉに公開する。
【００９５】
・初回共有秘密鍵共有ステップ：
1.  各鍵交換装置２００−ｉの共有秘密鍵共有部２０６は、長期公開鍵SPKsを取得し、長期公開鍵SPKsに含まれるtPRFを用いて、a~i∈R{0,1}κ、a~i'∈RKspaceκ、ai=tPRF(a~i,a~i',sti,st'i)により、aiを求め、(a~i,a~i')を図示しない記憶部ESKiに保存し、ga_iを作成する。共有秘密鍵共有部２０６は、秘密鍵記憶部２０１から秘密鍵skiを取り出し、秘密鍵skiを用いて、署名アルゴリズムSigにより、署名σi0を作成し(σi0←Sigsk_i(ga_i))、鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００に(ga_i、σi0)を送信する。
2.  鍵交換サーバ装置１００の共有秘密鍵共有部１０６は、(ga_i,σi0)を受け取り、検証アルゴリズムVerを用いて、署名σi0を検証する(1 or ⊥←Verpk_i(ga_i,σi0))。共有秘密鍵共有部１０６は、検証に失敗した場合(⊥が出力された場合)、鍵交換アルゴリズムを停止する。共有秘密鍵共有部１０６は、検証に成功した場合(1が出力された場合)、鍵交換アルゴリズムを継続する。
【００９６】
共有秘密鍵共有部１０６は、各鍵交換装置２００−ｉに対して、tPRFを用いて、b~i∈R{0,1}κ、b~i'∈RKspaceκ、bi=tPRF(b~i,b~i',sts,st's)により、biを求め、(b~i,b~i')を図示しない記憶部ESKsに保存し、gb_iを作成する。
【００９７】
共有秘密鍵共有部１０６は、秘密鍵記憶部１０１から秘密鍵sksを取り出し、秘密鍵sksを用いて、署名アルゴリズムSigにより、署名σs0を作成し(σs0←Sigsk_s(gb_i))、鍵交換アルゴリズム部１０３を経由して各鍵交換装置２００−ｉに(gb_i,σs0)を送信する。さらに、共有秘密鍵共有部１０６は、各鍵交換装置２００−ｉから受け取ったga_iと作成した乱数biとを用いてga_ib_iを作成し、MAC鍵を生成するアルゴリズムMGenを用いて、mki0←MGen(ga_ib_i)を作成する。共有秘密鍵共有部１０６は、mki0(ただしi=1,2,…,n)を共有秘密鍵として共有秘密鍵記憶部１０２に保存する。
3.  各鍵交換装置２００−ｉの共有秘密鍵共有部２０６は、(gb_i,σs0)を受け取り、長期公開鍵SPKsに含まれるpksと検証アルゴリズムVerを用いて、署名σs0を検証する(1 or ⊥←Verpk_s(gb_i,σi0))。共有秘密鍵共有部２０６は、検証に失敗した場合(⊥が出力された場合)、鍵交換アルゴリズムを停止する。共有秘密鍵共有部２０６は、検証に成功した場合(1が出力された場合)、鍵交換装置２００−ｉが生成したaiと鍵交換サーバ装置１００から受け取ったgb_iとを用いてga_ib_iを作成し、MAC鍵を生成するアルゴリズムMGenを用いて、mki0←MGen(ga_ib_i)を作成する。共有秘密鍵共有部２０６は、mki0(ここでは、ｉは鍵交換装置２００−ｉに対応する1つの値)を共有秘密鍵として共有秘密鍵記憶部２０２に保存する。
【００９８】
ここまでの処理により、鍵交換サーバ装置１００と鍵交換装置２００−ｉとが共有秘密鍵mki0を共有する。
【００９９】
（Round2 for Users）
1.  i∈[1,n]である鍵交換装置２００−ｉの認証情報検証部２０４は、（sid,Ri-1,Ri+1,σsev_i1）を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mkij-1)(sid,Ri-1,Ri+1,σsev_i1)
認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  i∈[2,n]である鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、Ki(l)=F(sid,Ri-1r_i)、Ki(r)=F(sid,Ri+1r_i)、Ti=Ki(l) xor Ki(r)を計算する。共有秘密鍵共有部２０６は、さらに、d~i∈R{0,1}κ、d~i'∈RKspaceκ、di=tPRF(d~i,d~i',sti,st'i)により、diを求め、(d~i,d~i')を図示しない記憶部ESKiに保存し、gd_iを作成する。共有秘密鍵共有部２０６は、署名アルゴリズムTagを用いて署名σi2を計算し(σi2=Tag_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,gd_i))、鍵交換サーバ装置１００に対して、鍵交換アルゴリズム部２０３を経由して(ki,si,Ti,gd_i,σi2)を送信する。
3.  代表ユーザであるユーザu1の鍵交換アルゴリズム部２０３は、K1(l)=F(sid,Rnr_i)、K1(r)=F(sid,R2r_i)、T1=K1(l) xor K1(r)、T'=K1(l) xor (k1||s1)を計算する。共有秘密鍵共有部２０６は、さらに、d~1∈R{0,1}κ、d~1'∈RKspaceκ、d1=tPRF(d~1,d~1',st1,st'1)により、d1を求め、(d~1,d~1')を図示しない記憶部ESK1に保存し、gd_1を作成する。共有秘密鍵共有部２０６は、署名アルゴリズムTagを用いて署名σi2を計算し(σi2=Tag_(mk1j-1)(R1,c1,Rn,R2,T1,T',U1,sid,gd_1))、鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００に対して、(Ti,T',gd_1,σi2)を送信する。
【０１００】
（Round2 for Server）
1.  鍵交換サーバ装置１００の認証情報検証部１０４は、鍵交換アルゴリズム部１０３を経由してi∈[2,n]である鍵交換装置２００−ｉから(ki,si,Ti,gd_i,σi2)を取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,gd_i,σi2)
認証情報検証部１０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部１０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  鍵交換サーバ装置１００の認証情報検証部１０４は、鍵交換アルゴリズム部１０３を経由して代表ユーザであるユーザu1の鍵交換装置２００−１から(ki,si,Ti,gd_1,σi2)を取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mkij-1)(ki,si,Ti,gd_1,σi2)
認証情報検証部１０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部１０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
3.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、kS~∈R{0,1}*、kS~'∈RKspaceκ、K1~∈R{0,1}*、K1~'∈RKspaceκを生成し、kS=tPRF(kS~,kS~',sts,st's)とK1=tPRF(K1~,K1~',sts,st's)とk'=( xor2≦i≦n ki) xor ksを計算する。
4.  共有秘密鍵共有部１０６は、e~i∈R{0,1}κ、e~i'∈RKspaceκ、ei=tPRF(e~i,e~i',sti,st'i)により、eiを求め、(e~i,e~i')を図示しない記憶部ESKsに保存し、ge_iを作成する。さらに、共有秘密鍵共有部１０６は、各鍵交換装置２００−ｉから受け取ったgd_iと作成したge_iとを用いてgd_ie_iを作成し、MAC鍵を生成するアルゴリズムMGenを用いて、mki1←MGen(gd_ie_i)を作成する。共有秘密鍵共有部１０６は、mki1(ただしi=1,2,…,n)を共有秘密鍵として共有秘密鍵記憶部１０２に保存し、mki0を削除する。
5.  鍵交換サーバ装置１００の鍵交換アルゴリズム部１０３は、i∈[2,n]である鍵交換装置２００−ｉに対してTi'=( xor1≦j≦i-1 Tj)を計算する。
6.  鍵交換サーバ装置１００の認証情報付加部１０５は、i∈[2,n]である鍵交換装置２００−ｉに対して、署名アルゴリズムTagを用いて、次式により署名σi2を計算する。
σi2=Tag_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,c1,k',Ti',T',ge_i)
さらに、認証情報付加部１０５は、(c1,k',sid,T'i,T',ge_i,σi2)を鍵交換アルゴリズム部１０３を経由してi∈[2,n]である鍵交換装置２００−ｉに送信する。
7.  鍵交換サーバ装置１００の認証情報付加部１０５は、代表ユーザであるユーザu1の鍵交換装置２００−１に対して、署名アルゴリズムTagを用いて、次式により署名σi2を計算する。
σ12=Tag_(mkij-1)(R1,c1,Rn,R2,T1,T',U1,sid,k',ge_1)
さらに、認証情報付加部１０５は、(k',ge_1,σ12)を鍵交換アルゴリズム部１０３を経由して鍵交換装置２００−１に送信する。
【０１０１】
（Session Key Generation and Post Computation）
1.  i∈[2,n]である鍵交換装置２００−ｉの認証情報検証部２０４は、(c1,k',sid,T'i,T',ge_i,σi2）を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,c1,k',Ti',T',ge_i,σi2)
認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、K1(l)=T'ixor Ki(l)とk1||s1=T' xor K1(l)を計算し、K1=F'(sid,k' xor k1)を計算する。
【０１０２】
さらに、鍵交換アルゴリズム部２０３は、セッション鍵SKをSK=F''(sid,K1)により求める。
3.  i∈[2,n]である鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、sid、Hi(l)=Ri-1r_i、Hi(r)=Ri+1r_i、r=F'''(sid,K1) xor F'''(sid,K2)を図示しない記憶部stateiに保存する。
【０１０３】
さらに、共有秘密鍵共有部２０６は、鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から受け取ったge_iとRound2 for Usersで作成したgd_iとを用いてgd_ie_iを作成し、MAC鍵を生成するアルゴリズムMGenを用いて、mki1←MGen(gd_ie_i)を作成する。共有秘密鍵共有部２０６は、mki1(ただしi=1,2,…,n)を共有秘密鍵として共有秘密鍵記憶部２０２に保存し、mki0を削除する。
4.  代表ユーザであるユーザu1の鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、(k',ge_1,σ12)を鍵交換サーバ装置１００から取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mk1j-1)(R1,c1,Rn,R2,T1,T',U1,sid,k',ge_1,σ12)
鍵交換アルゴリズム部２０３は、検証に失敗したら鍵交換アルゴリズムを停止する。鍵交換アルゴリズム部２０３は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
5.  鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、K1=F'(sid,k' xor k1)を計算する。さらに、鍵交換アルゴリズム部２０３は、セッション鍵SKをSK=F''(sid,K1)により求める。
6.  鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、sid、H1(l)=Rnr_i、H1(r)=R2r_i、r=F'''(sid,K1) xor F'''(sid,K2)を図示しない記憶部stateiに保存する。
【０１０４】
さらに、共有秘密鍵共有部２０６は、鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から受け取ったge_iとRound2 for Usersで作成したgd_iとを用いてgd_ie_iを作成し、MAC鍵を生成するアルゴリズムMGenを用いて、mki1←MGen(gd_ie_i)を作成する。共有秘密鍵共有部２０６は、mki1(ただしi=1,2,…,n)を共有秘密鍵として共有秘密鍵記憶部２０２に保存し、mki0を削除する。
【０１０５】
＜効果＞
このような構成により、第一実施形態と同様の効果を得ることができる。さらに、共有秘密鍵を更新することでより安全性を高めることができる。
【０１０６】
＜変形例＞
なお、本実施形態では、mki0←MGen(ga_ib_i)、mki1←MGen(gd_ie_i)として、共有秘密鍵を求めているが、seed←TCR(ga_ib_i)、mki0←MGen(seed)、seed←TCR(gd_ie_i)、mki1←MGen(seed)として共有秘密鍵を求めてもよい。
【０１０７】
本実施形態では、共有秘密鍵mki1について説明しているが、セッションj毎に共有秘密鍵mkijを更新してもよい。更新時には、1つ前の共有秘密鍵mkij-1だけでなく、1つ以上前の共有秘密鍵mkik(0<k<j)を用いることができる。なお、kの値は鍵交換の相手と何らかの方法で予め特定しておけばよい。
【０１０８】
＜第四実施形態のポイント＞
第三実施形態と異なる部分を中心に説明する。
第四実施形態では、共有秘密鍵更新方式を採用する。
ただし、第三実施形態とは異なり、共有秘密鍵の更新は毎回DH鍵更新を行うのではなく、前回のセッションの共有秘密鍵と関連情報を擬似ランダム関数の入力に入れ、出力された値を更新された共有秘密鍵とする。
なお、第四実施形態では、関連情報を該当セッションで共有されたセッション鍵とする。
＜第四実施形態＞
第三実施形態と第四実施形態は、（Round2 for Users）、（Round2 for Server）及び（Session Key Generation and Post Computation）における処理内容が異なる。異なる部分を中心に説明する。（Round2 for Users）と（Round2 for Server）は、第二実施形態の（Round2 for Users）と（Round2 for Server）それぞれと同様である。
（Session Key Generation and Post Computation）は以下の処理を行う。なお、mki0を第三実施形態と同じ初回共有秘密鍵共有ステップを実施する事で鍵交換サーバ装置１００と鍵交換装置２００−iの間で交換している事とする。
（Session Key Generation and Post Computation）
1.  i∈[2,n]である鍵交換装置２００−ｉの認証情報検証部２０４は、(c1,k',sid,T'i,T',σi2）を鍵交換アルゴリズム部２０３を経由して鍵交換サーバ装置１００から取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mkij-1)(Ri,ci,Ri-1,Ri+1,ki,si,Ti,Ui,sid,c1,k',Ti',T',σi2)
認証情報検証部２０４は、検証に失敗したら鍵交換アルゴリズムを停止する。認証情報検証部２０４は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
2.  鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、K1(l)=T'ixor Ki(l)とk1||s1=T' xor K1(l)を計算し、K1=F'(sid,k' xor k1)を計算する。
さらに、鍵交換アルゴリズム部２０３は、セッション鍵SKをSK=F''(sid,K1)により求める。
3.  i∈[2,n]である鍵交換装置２００−ｉの鍵交換アルゴリズム部２０３は、sid、Hi(l)=Ri-1r_i、Hi(r)=Ri+1r_i、r=F'''(sid,K1) xor F'''(sid,K2)を図示しない記憶部stateiに保存する。
さらに、共有秘密鍵共有部２０６は、鍵交換アルゴリズム部２０３を経由してSKとmki0を擬似ランダム関数PRFに入力し、mki1←PRF(SK,mki0)を作成する。共有秘密鍵共有部２０６は、mki1(ただしi=1,2,…,n)を共有秘密鍵として共有秘密鍵記憶部２０２に保存し、mki0を削除する。
4.  代表ユーザであるユーザu1の鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、(k',σ12)を鍵交換サーバ装置１００から取得し、検証アルゴリズムVerにより、次式により検証を行う。
Ver_(mk1j-1)(R1,c1,Rn,R2,T1,T',U1,sid,k',σ12)
鍵交換アルゴリズム部２０３は、検証に失敗したら鍵交換アルゴリズムを停止する。鍵交換アルゴリズム部２０３は、検証に成功した場合のみ、鍵交換アルゴリズムを継続する。
5.  鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、K1=F'(sid,k' xor k1)を計算する。さらに、鍵交換アルゴリズム部２０３は、セッション鍵SKをSK=F''(sid,K1)により求める。
6.  鍵交換装置２００−１の鍵交換アルゴリズム部２０３は、sid、H1(l)=Rnr_i、H1(r)=R2r_i、r=F'''(sid,K1) xor F'''(sid,K2)を図示しない記憶部stateiに保存する。
さらに、共有秘密鍵共有部２０６は、鍵交換アルゴリズム部２０３を経由してSKとmki0を擬似ランダム関数PRFに入力し、mki1←PRF(SK, mki0)を作成する。共有秘密鍵共有部２０６は、mki1(ただしi=1,2,…,n)を共有秘密鍵として共有秘密鍵記憶部２０２に保存し、mki0を削除する。
これ以後、上記のアルゴリズムに従って、再度DistやJoin、Leave、Updateを実施する度に、その際に共有されるセッション鍵SKv（v∈N  を鍵交換を実施した回数とする）をもちいて、（Session Key Generation and Post Computation）フェーズでmkiv←PRF(SK, mkiv-1)を行い、共有秘密鍵の更新を行う。
＜効果＞
このような構成により、第三実施形態と同様の効果を得ることができる。
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【０１０９】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１１０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【０１１２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１３】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019093478.tif 000007
【図２】
2019093478.tif 000008
【図３】
2019093478.tif 000009
【国際調査報告】
2019093478.tif 000010
2019093478.tif 000011
2019093478.tif 000012
2019093478.tif 000013