(57)【要約】【課題】長期秘密鍵が漏洩したとしても、暗号鍵を取得することができない鍵交換技術を提供する。【解決手段】鍵交換サーバ装置が通信装置の認証鍵を生成する認証鍵生成ステップと、通信装置が認証鍵を取得する認証鍵受信ステップと、通信装置がRiを生成する第１鍵生成ステップと、鍵交換サーバ装置が(sid, Rα, Rβ)を通信装置へ送信するセッションID生成ステップと、通信装置がsid, Rα, Rβから第２鍵を生成する第２鍵生成ステップと、鍵交換サーバ装置が第２鍵を用いてT'iを生成し、あわせて第１共通鍵を生成する第１共通鍵生成ステップと、鍵交換サーバ装置が鍵導出関数を用いて認証鍵から新しい認証鍵を生成する認証鍵更新ステップと、通信装置が第１共通鍵を用いて第２共通鍵とセッション鍵を生成するセッション鍵生成ステップと、通信装置が鍵導出関数を用いて認証鍵から新しい認証鍵を生成する認証鍵更新ステップとを含む。【選択図】図６
2019125956.tif 000002
【特許請求の範囲】
【請求項１】
nを2以上の整数、α, βを次式で定義される値とし、
【数１４】
2019125956.tif 000016
鍵交換サーバ装置Sとn台の通信装置Ui(i=1, …, n)を含む鍵交換システムが実行する鍵交換方法であって、
U1を前記通信装置U1, …, Unから選択された1台の代表通信装置、timeoを現在時刻、IDを通信装置を表す述語変数、TFmをタイムフレームを表す述語変数とし、
前記鍵交換サーバ装置Sの記録部には、長期秘密鍵SSKs=(msk, stS, st'S)（ただし、mskは属性ベース暗号のマスター秘密鍵、stS、st'Sはそれぞれ秘密ストリング）が記録されており、
前記通信装置Ui(i=1, …, n)の記録部には、長期秘密鍵SSKi=(ski, sti, st'i)（ただし、skiは前記通信装置Uiの公開鍵暗号の秘密鍵、sti、st'iはそれぞれ秘密ストリング）が記録されており、
前記鍵交換サーバ装置Sが、i=1, …, nについて、属性をAi=(Ui, timeo)として、属性ベース暗号の鍵導出アルゴリズムにより、属性ベース暗号の公開パラメータParamsと前記マスター秘密鍵mskを用いて、前記通信装置Uiの属性秘密鍵uskiを生成し、メッセージ認証子の鍵生成アルゴリズムにより、前記通信装置UiのMAC鍵mki0を認証鍵として生成し、公開鍵暗号の暗号化アルゴリズムにより、前記通信装置Uiの長期公開鍵SPKi=pki（ただし、pkiは前記通信装置Uiの公開鍵暗号の公開鍵）を用いて、前記属性秘密鍵uskiおよび前記認証鍵mki0を暗号化し、暗号文CTiを生成し、前記暗号文CTiを前記通信装置Ui（i∈{1, …, n}）へ送信する認証鍵生成ステップと、
前記通信装置Ui(i=1, …, n)が、公開鍵暗号の復号アルゴリズムにより、前記秘密鍵skiを用いて、前記暗号文CTiを復号し、前記属性秘密鍵uskiと前記認証鍵mki0を取得する認証鍵受信ステップと、
前記通信装置Ui(i=1, …, n)が、ねじれ擬似ランダム関数により前記秘密ストリングsti, st'iを用いてri, ki, siを生成し、第１鍵Ri=gr_iおよびci=gk_ihs_iを生成し、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mki0を用いて、前記Ri, ciから認証タグti1を生成し、(Ri, ci, ti1)を前記鍵交換サーバ装置Sへ送信する第１鍵生成ステップと、
前記鍵交換サーバ装置Sが、i=1, …, nについて、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mki0と前記Ri, ciを用いて、前記認証タグti1を検証する第１鍵受信ステップと、
前記鍵交換サーバ装置Sが、衝突困難ハッシュ関数により、前記c1, …, cnを用いてセッションID sidを生成し、i=1, …, nについて、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mki0を用いて、前記sid, Rα, Rβから認証タグti2を生成し、(sid, Rα, Rβ, ti2)を前記通信装置Ui（i∈{1, …, n}）へ送信するセッションID生成ステップと、
前記通信装置Ui（i∈{2, …, n}）が、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mki0と前記sid, Rα, Rβを用いて、前記認証タグti2を検証し、前記認証タグti2が正当である場合、擬似ランダム関数により前記sid, Rαr_iを用いてKilを生成し、擬似ランダム関数により前記sid, Rβr_iを用いてKirを生成し、前記Kilと前記Kirとの排他的論理和により第２鍵Tiを生成し、
前記代表通信装置U1が、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mk10と前記sid, Rn, R2を用いて、前記認証タグt12を検証し、前記認証タグt12が正当である場合、擬似ランダム関数により前記sid, Rnr_1を用いてK1lを生成し、擬似ランダム関数により前記sid, R2r_1を用いてK1rを生成し、前記K1lと前記K1rとの排他的論理和により第２鍵T1を生成し、前記K1lとk1||s1との排他的論理和によりT'を生成する第２鍵生成ステップと、
前記通信装置Ui（i∈{2, …, n}）が、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mki0を用いて、前記Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sidから認証タグti3を生成し、(ki, si, Ti, ti3)を前記鍵交換サーバ装置Sへ送信し、
前記代表通信装置U1が、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mk10を用いて、前記R1, c1, Rn, R2, T1, T', U1, sidから認証タグt13を生成し、(T1, T', t13)を前記鍵交換サーバ装置Sへ送信する第２鍵送信ステップと、
前記鍵交換サーバ装置Sが、i=2, …, nについて、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mki0と前記Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sidを用いて、前記認証タグti3を検証し、i=1について、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mk10と前記R1, c1, Rn, R2, T1, T', U1, sidを用いて、前記認証タグt13を検証する第２鍵受信ステップと、
前記鍵交換サーバ装置Sが、ねじれ擬似ランダム関数により、前記秘密ストリングstS, st'Sを用いて、kS, 第１共通鍵K1を生成し、前記k2, …, kn, ksの排他的論理和により、k'を生成し、i=2, …, nについて、前記T1, …, Ti-1の排他的論理和により、T'iを生成し、i=1, …, nについて、条件Pi=(ID=Ui)∧(timeo∈TFm)として、属性ベース暗号の暗号化アルゴリズムにより、前記公開パラメータParamsを用いて、前記第１共通鍵K1を暗号化して、暗号文CT'iを生成する第１共通鍵生成ステップと、
前記鍵交換サーバ装置Sが、i=2, …, nについて、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mki0を用いて、前記Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'iから認証タグti4を生成し、(c1, k', T'i, T', CT'i, ti4)を前記通信装置Uiへ送信し、i=1について、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mk10を用いて、前記R1, c1, Rn, R2, T1, T', U1, sid, k', CT'1から認証タグt14を生成し、(k', CT'1, t14)を前記代表通信装置U1へ送信する第１共通鍵送信ステップと、
認証鍵更新情報μi(i=1, …, n)を前記鍵交換サーバ装置Sと前記通信装置Uiの間で既に共有されている情報であるとし、
前記鍵交換サーバ装置Sが、i=1, …, nについて、鍵導出関数により、前記認証鍵mki0と前記認証鍵更新情報μi、または、前記認証鍵mki0から新しい認証鍵mki1を生成する認証鍵更新ステップと、
前記通信装置Ui（i∈{2, …, n}）が、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mki0と前記Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'iを用いて、前記認証タグti4を検証し、前記認証タグti4が正当である場合、前記T'iと前記Kilとの排他的論理和によりK1lを生成し、前記T'と前記K1lとの排他的論理和によりk1||s1を生成し、属性ベース暗号の復号アルゴリズムにより、前記属性秘密鍵uskiを用いて、前記暗号文CT'iから第１共通鍵K1を復号し、
前記代表通信装置U1が、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mk10と前記R1, c1, Rn, R2, T1, T', U1, sid, k', CT'1を用いて、前記認証タグt14を検証し、前記認証タグti4が正当である場合、属性ベース暗号の復号アルゴリズムにより、前記属性秘密鍵uskiを用いて、前記暗号文CT'1から第１共通鍵K1を復号する第１共通鍵受信ステップと、
前記通信装置Ui（i∈{1, …, n}）が、擬似ランダム関数により前記セッションID sidおよび前記k'と前記k1との排他的論理和を用いて生成した値により、第２共通鍵K2を生成し、擬似ランダム関数により前記sid, K1を用いて生成した値と疑似ランダム関数により前記sid, K2を用いて生成した値の排他的論理和により、セッション鍵SKを生成するセッション鍵生成ステップと、
前記通信装置Ui（i∈{1, …, n}）が、鍵導出関数により、前記認証鍵mki0と前記認証鍵更新情報μi、または、前記認証鍵mki0から新しい認証鍵mki1を生成する認証鍵更新ステップと
を含む鍵交換方法。
【請求項２】
nを2以上の整数、α, βを次式で定義される値とし、
【数１５】
2019125956.tif 000017
鍵交換サーバ装置Sとn台の通信装置Ui(i=1, …, n)を含む鍵交換システムが実行する鍵交換方法であって、
U1を前記通信装置U1, …, Unから選択された1台の代表通信装置、timeoを現在時刻、IDを通信装置を表す述語変数、TFmをタイムフレームを表す述語変数とし、
前記鍵交換サーバ装置Sの記録部には、長期秘密鍵SSKs=(msk, stS, st'S)（ただし、mskは属性ベース暗号のマスター秘密鍵、stS、st'Sはそれぞれ秘密ストリング）が記録されており、
前記通信装置Ui(i=1, …, n)の記録部には、長期秘密鍵SSKi=(ski, sti, st'i)（ただし、skiは前記通信装置Uiの公開鍵暗号の秘密鍵、sti、st'iはそれぞれ秘密ストリング）が記録されており、
前記鍵交換サーバ装置Sが、i=1, …, nについて、属性をAi=(Ui, timeo)として、属性ベース暗号の鍵導出アルゴリズムにより、属性ベース暗号の公開パラメータParamsと前記マスター秘密鍵mskを用いて、前記通信装置Uiの属性秘密鍵uskiを生成し、メッセージ認証子の鍵生成アルゴリズムにより、前記通信装置UiのMAC鍵mki0を認証鍵として生成し、公開鍵暗号の暗号化アルゴリズムにより、前記通信装置Uiの長期公開鍵SPKi=pki（ただし、pkiは前記通信装置Uiの公開鍵暗号の公開鍵）を用いて、前記属性秘密鍵uskiおよび前記認証鍵mki0を暗号化し、暗号文CTiを生成し、前記暗号文CTiを前記通信装置Ui（i∈{1, …, n}）へ送信する認証鍵生成ステップと、
前記通信装置Ui(i=1, …, n)が、公開鍵暗号の復号アルゴリズムにより、前記秘密鍵skiを用いて、前記暗号文CTiを復号し、前記属性秘密鍵uskiと前記認証鍵mki0を取得する認証鍵受信ステップと、
前記通信装置Ui(i=1, …, n)が、ねじれ擬似ランダム関数により前記秘密ストリングsti, st'iを用いてri, ki, siを生成し、第１鍵Ri=gr_iおよびci=gk_ihs_iを生成し、 (Ri, ci)を前記鍵交換サーバ装置Sへ送信する第１鍵生成ステップと、
前記鍵交換サーバ装置Sが、衝突困難ハッシュ関数により、前記c1, …, cnを用いてセッションID sidを生成し、(sid, Rα, Rβ)を前記通信装置Ui（i∈{1, …, n}）へ送信するセッションID生成ステップと、
前記通信装置Ui（i∈{2, …, n}）が、擬似ランダム関数により前記sid, Rαr_iを用いてKilを生成し、擬似ランダム関数により前記sid, Rβr_iを用いてKirを生成し、前記Kilと前記Kirとの排他的論理和により第２鍵Tiを生成し、
前記代表通信装置U1が、擬似ランダム関数により前記sid, Rnr_1を用いてK1lを生成し、擬似ランダム関数により前記sid, R2r_1を用いてK1rを生成し、前記K1lと前記K1rとの排他的論理和により第２鍵T1を生成し、前記K1lとk1||s1との排他的論理和によりT'を生成する第２鍵生成ステップと、
前記通信装置Ui（i∈{2, …, n}）が、(ki, si, Ti)を前記鍵交換サーバ装置Sへ送信し、
前記代表通信装置U1が、(T1, T')を前記鍵交換サーバ装置Sへ送信する第２鍵送信ステップと、
前記鍵交換サーバ装置Sが、ねじれ擬似ランダム関数により、前記秘密ストリングstS, st'Sを用いて、kS, 第１共通鍵K1を生成し、前記k2, …, kn, ksの排他的論理和により、k'を生成し、i=2, …, nについて、前記T1, …, Ti-1の排他的論理和により、T'iを生成し、i=1, …, nについて、条件Pi=(ID=Ui)∧(timeo∈TFm)として、属性ベース暗号の暗号化アルゴリズムにより、前記公開パラメータParamsを用いて、前記第１共通鍵K1を暗号化して、暗号文CT'iを生成する第１共通鍵生成ステップと、
前記鍵交換サーバ装置Sが、i=2, …, nについて、(c1, k', T'i, T', CT'i)を前記通信装置Uiへ送信し、i=1について、(k', CT'1)を前記代表通信装置U1へ送信する第１共通鍵送信ステップと、
認証鍵更新情報μi(i=1, …, n)を前記鍵交換サーバ装置Sと前記通信装置Uiの間で既に共有されている情報であるとし、
前記鍵交換サーバ装置Sが、i=1, …, nについて、鍵導出関数により、前記認証鍵mki0と前記認証鍵更新情報μi、または、前記認証鍵mki0から新しい認証鍵mki1を生成する認証鍵更新ステップと、
前記通信装置Ui（i∈{2, …, n}）が、前記T'iと前記Kilとの排他的論理和によりK1lを生成し、前記T'と前記K1lとの排他的論理和によりk1||s1を生成し、属性ベース暗号の復号アルゴリズムにより、前記属性秘密鍵uskiを用いて、前記暗号文CT'iから第１共通鍵K1を復号し、
前記代表通信装置U1が、属性ベース暗号の復号アルゴリズムにより、前記属性秘密鍵uskiを用いて、前記暗号文CT'1から第１共通鍵K1を復号する第１共通鍵受信ステップと、
前記通信装置Ui（i∈{1, …, n}）が、擬似ランダム関数により前記セッションID sidおよび前記k'と前記k1との排他的論理和を用いて生成した値により、第２共通鍵K2を生成し、擬似ランダム関数により前記sid, K1を用いて生成した値と疑似ランダム関数により前記sid, K2を用いて生成した値の排他的論理和により、セッション鍵SKを生成するセッション鍵生成ステップと、
前記通信装置Ui（i∈{1, …, n}）が、鍵導出関数により、前記認証鍵mki0と前記認証鍵更新情報μi、または、前記認証鍵mki0から新しい認証鍵mki1を生成する認証鍵更新ステップと
を含む鍵交換方法。
【請求項３】
請求項１または２に記載の鍵交換方法を実行する鍵交換システム。
【請求項４】
請求項１または２に記載の鍵交換方法を実行する鍵交換システムに含まれる鍵交換サーバ装置。
【請求項５】
請求項１または２に記載の鍵交換方法を実行する鍵交換システムに含まれる通信装置。
【請求項６】
請求項１または２に記載の鍵交換方法を実行する鍵交換システムに含まれる鍵交換サーバ装置または通信装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティ技術の応用に関し、特にグループを形成する複数の通信装置が暗号鍵を共有する鍵交換技術に関する。
【背景技術】
【０００２】
現在、チャットアプリケーションの中には、その通信内容をエンドツーエンド暗号化するものがある。エンドツーエンド暗号化により、ユーザはチャットアプリケーションサーバに通信内容を知られることなくチャットを行うことができる。
【０００３】
多人数のユーザが参加するグループチャットでは、グループに通信装置が新たに参加する、グループから既存の通信装置が離脱する等、参加している通信装置が動的に変わる場合がある。このような場合でも、エンドツーエンド暗号化に使用する鍵（以下、暗号鍵という）の交換を効率的に行えるプロトコルとして動的多者間鍵交換プロトコル（DMKD(Dynamic Multi-Cast Key Distribution)プロトコル）が存在する。代表的なDMKDプロトコルとして、Y16プロトコルと呼ばれるものがある（非特許文献１）。
【０００４】
DMKDプロトコルは、以下の特徴を有する。
（１）ネットワーク構成は、鍵交換サーバ装置を中心としたスター型である。
（２）鍵交換システムは、鍵交換サーバ装置と通信装置から構成される。鍵交換サーバ装置と通信装置は、それぞれ鍵交換に際して長期間使用する秘密鍵（以下、長期秘密鍵という）と１回の鍵交換にのみ使用する秘密鍵（以下、短期秘密鍵という）を保持する。鍵交換の結果、通信装置は暗号鍵を取得することできるが、鍵交換サーバ装置は暗号鍵を取得することができない。
（３）DMKDプロトコルには、基本となる３つのフェーズ｛Dist, Join, Leave｝がある。これらのフェーズを実行することをセッションと呼ぶ。Dist（鍵配送）フェーズでは、新しいグループが生成され、グループに参加する通信装置間で暗号鍵の交換が行われる。Join（追加）フェーズでは、既存のグループに新たな通信装置が加わり、当該グループで鍵交換が行われる。Leave（離脱）フェーズでは、既存のグループから参加済みの通信装置が離脱し、当該グループで鍵交換が行われる。
（４）DMKDプロトコルには、タイムフレーム（TF）と呼ばれる所定の期間が定められており、当該所定の期間が経過し、次のタイムフレームTFに変わると、再度グループで鍵交換が行われる。この暗号鍵を更新するフェーズをUpdate（更新）フェーズという。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】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, Nanjing, China, pp. 207-226, Nov. 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
鍵交換サーバ装置への不正アクセスによる情報漏洩、通信装置のマルウェア感染による情報漏洩のように、秘密鍵が漏洩する危険性は依然存在している。DMKDプロトコルでは鍵交換サーバ装置や通信装置が長期秘密鍵を安全に保持する必要があるが、保持期間が長期に及ぶがゆえ、上記リスクにより長期秘密鍵が漏洩してしまう可能性がある。
【０００７】
秘密鍵の漏洩に対しては、当該鍵を失効させ、新たな鍵を再発行するという対策を取り得る。しかし、不正アクセスやマルウェア感染の例では、秘密鍵の漏洩にサーバ管理者やユーザが気づかず、秘密鍵が漏洩している状態が長きに渡り続く場合もある。したがって、たとえ、秘密鍵が漏洩した状態になったとしても、通信装置間の通信の安全性が確保されることが重要になる。
【０００８】
DMKDプロトコルでは、鍵交換サーバ装置や通信装置は、自身が保持する長期秘密鍵を用いて鍵交換時のユーザ認証やサーバ認証に必要な鍵（以下、認証鍵という）を共有する。この認証鍵を攻撃者が取得してしまうと、攻撃者は正当な利用者になりすまして鍵交換に参加することができる。したがって、長期秘密鍵が攻撃者に取得されてしまうと、攻撃者は認証鍵を得ることができ、認証鍵を使って鍵交換に加わり、暗号鍵を取得できてしまう。暗号鍵が取得されてしまうと、例えばチャットアプリケーションでの暗号化されたチャット内容が攻撃者に知られてしまう。
【０００９】
以下、具体例としてY16プロトコルでの攻撃について説明する。Y16プロトコルでは、タイムフレームTFが変わるごとに、鍵交換サーバ装置が公開鍵暗号の一種である属性ベース暗号アルゴリズムにおけるユーザの属性秘密鍵（鍵交換サーバ装置の長期秘密鍵から生成される鍵）とメッセージ認証子アルゴリズムにおけるMAC鍵を生成し、通信装置の公開鍵暗号アルゴリズムにおける公開鍵を用いて、属性秘密鍵とMAC鍵を暗号化して当該通信装置に送信する。Y16プロトコルでは、ユーザの属性秘密鍵とMAC鍵が認証鍵に相当する。
【００１０】
暗号化された属性秘密鍵とMAC鍵を受信した通信装置は、公開鍵暗号アルゴリズムにおける秘密鍵（通信装置の長期秘密鍵に相当する鍵）を用いて、属性秘密鍵とMAC鍵を取得し、暗号鍵を生成するのに必要な情報を取得したり、鍵交換サーバ装置に送信する情報に認証タグを付加したりする。
【００１１】
鍵交換サーバ装置は、認証タグにより通信装置を認証する。したがって、通信装置の長期秘密鍵が攻撃者に取得されれば、MAC鍵が取得できるため、攻撃者は正当なユーザになりすまして鍵交換に参加できてしまう。これにより、攻撃者は暗号鍵を取得できるため、暗号化されたチャット内容を見ることができてしまう。
【００１２】
一方、通信装置は、正しい属性秘密鍵を生成できるか否かにより鍵交換サーバ装置を認証する。したがって、鍵交換サーバ装置の長期秘密鍵が攻撃者に取得されれば、ユーザの属性秘密鍵が作成できるため、攻撃者は鍵交換サーバ装置になりすますことができる。鍵交換サーバ装置は交換対象となる暗号鍵を直接知ることはできないが、鍵交換サーバ装置はグループに参加する通信装置を決定することができるため、攻撃者が利用する通信装置をグループに参加させることができる。これにより、攻撃者は暗号鍵を知ることができるため、暗号化されたチャット内容を見ることができてしまう。
【００１３】
そこで本発明では、長期秘密鍵が漏洩したとしても、暗号鍵を取得することができない鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の一態様は、nを2以上の整数、α, βを次式で定義される値とし、
【００１５】
【数１】
2019125956.tif 000003
【００１６】
鍵交換サーバ装置Sとn台の通信装置Ui(i=1, …, n)を含む鍵交換システムが実行する鍵交換方法であって、U1を前記通信装置U1, …, Unから選択された1台の代表通信装置、timeoを現在時刻、IDを通信装置を表す述語変数、TFmをタイムフレームを表す述語変数とし、前記鍵交換サーバ装置Sの記録部には、長期秘密鍵SSKs=(msk, stS, st'S)（ただし、mskは属性ベース暗号のマスター秘密鍵、stS、st'Sはそれぞれ秘密ストリング）が記録されており、前記通信装置Ui(i=1, …, n)の記録部には、長期秘密鍵SSKi=(ski, sti, st'i)（ただし、skiは前記通信装置Uiの公開鍵暗号の秘密鍵、sti、st'iはそれぞれ秘密ストリング）が記録されており、前記鍵交換サーバ装置Sが、i=1, …, nについて、属性をAi=(Ui, timeo)として、属性ベース暗号の鍵導出アルゴリズムにより、属性ベース暗号の公開パラメータParamsと前記マスター秘密鍵mskを用いて、前記通信装置Uiの属性秘密鍵uskiを生成し、メッセージ認証子の鍵生成アルゴリズムにより、前記通信装置UiのMAC鍵mki0を認証鍵として生成し、公開鍵暗号の暗号化アルゴリズムにより、前記通信装置Uiの長期公開鍵SPKi=pki（ただし、pkiは前記通信装置Uiの公開鍵暗号の公開鍵）を用いて、前記属性秘密鍵uskiおよび前記認証鍵mki0を暗号化し、暗号文CTiを生成し、前記暗号文CTiを前記通信装置Ui（i∈{1, …, n}）へ送信する認証鍵生成ステップと、前記通信装置Ui(i=1, …, n)が、公開鍵暗号の復号アルゴリズムにより、前記秘密鍵skiを用いて、前記暗号文CTiを復号し、前記属性秘密鍵uskiと前記認証鍵mki0を取得する認証鍵受信ステップと、前記通信装置Ui(i=1, …, n)が、ねじれ擬似ランダム関数により前記秘密ストリングsti, st'iを用いてri, ki, siを生成し、第１鍵Ri=gr_iおよびci=gk_ihs_iを生成し、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mki0を用いて、前記Ri, ciから認証タグti1を生成し、(Ri, ci, ti1)を前記鍵交換サーバ装置Sへ送信する第１鍵生成ステップと、前記鍵交換サーバ装置Sが、i=1, …, nについて、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mki0と前記Ri, ciを用いて、前記認証タグti1を検証する第１鍵受信ステップと、前記鍵交換サーバ装置Sが、衝突困難ハッシュ関数により、前記c1, …, cnを用いてセッションID sidを生成し、i=1, …, nについて、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mki0を用いて、前記sid, Rα, Rβから認証タグti2を生成し、(sid, Rα, Rβ, ti2)を前記通信装置Ui（i∈{1, …, n}）へ送信するセッションID生成ステップと、前記通信装置Ui（i∈{2, …, n}）が、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mki0と前記sid, Rα, Rβを用いて、前記認証タグti2を検証し、前記認証タグti2が正当である場合、擬似ランダム関数により前記sid, Rαr_iを用いてKilを生成し、擬似ランダム関数により前記sid, Rβr_iを用いてKirを生成し、前記Kilと前記Kirとの排他的論理和により第２鍵Tiを生成し、前記代表通信装置U1が、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mk10と前記sid, Rn, R2を用いて、前記認証タグt12を検証し、前記認証タグt12が正当である場合、擬似ランダム関数により前記sid, Rnr_1を用いてK1lを生成し、擬似ランダム関数により前記sid, R2r_1を用いてK1rを生成し、前記K1lと前記K1rとの排他的論理和により第２鍵T1を生成し、前記K1lとk1||s1との排他的論理和によりT'を生成する第２鍵生成ステップと、前記通信装置Ui（i∈{2, …, n}）が、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mki0を用いて、前記Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sidから認証タグti3を生成し、(ki, si, Ti, ti3)を前記鍵交換サーバ装置Sへ送信し、前記代表通信装置U1が、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mk10を用いて、前記R1, c1, Rn, R2, T1, T', U1, sidから認証タグt13を生成し、(T1, T', t13)を前記鍵交換サーバ装置Sへ送信する第２鍵送信ステップと、前記鍵交換サーバ装置Sが、i=2, …, nについて、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mki0と前記Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sidを用いて、前記認証タグti3を検証し、i=1について、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mk10と前記R1, c1, Rn, R2, T1, T', U1, sidを用いて、前記認証タグt13を検証する第２鍵受信ステップと、前記鍵交換サーバ装置Sが、ねじれ擬似ランダム関数により、前記秘密ストリングstS, st'Sを用いて、kS, 第１共通鍵K1を生成し、前記k2, …, kn, ksの排他的論理和により、k'を生成し、i=2, …, nについて、前記T1, …, Ti-1の排他的論理和により、T'iを生成し、i=1, …, nについて、条件Pi=(ID=Ui)∧(timeo∈TFm)として、属性ベース暗号の暗号化アルゴリズムにより、前記公開パラメータParamsを用いて、前記第１共通鍵K1を暗号化して、暗号文CT'iを生成する第１共通鍵生成ステップと、前記鍵交換サーバ装置Sが、i=2, …, nについて、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mki0を用いて、前記Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'iから認証タグti4を生成し、(c1, k', T'i, T', CT'i, ti4)を前記通信装置Uiへ送信し、i=1について、メッセージ認証子のタグ生成アルゴリズムにより、前記認証鍵mk10を用いて、前記R1, c1, Rn, R2, T1, T', U1, sid, k', CT'1から認証タグt14を生成し、(k', CT'1, t14)を前記代表通信装置U1へ送信する第１共通鍵送信ステップと、認証鍵更新情報μi(i=1, …, n)を前記鍵交換サーバ装置Sと前記通信装置Uiの間で既に共有されている情報であるとし、前記鍵交換サーバ装置Sが、i=1, …, nについて、鍵導出関数により、前記認証鍵mki0と前記認証鍵更新情報μi、または、前記認証鍵mki0から新しい認証鍵mki1を生成する認証鍵更新ステップと、前記通信装置Ui（i∈{2, …, n}）が、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mki0と前記Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'iを用いて、前記認証タグti4を検証し、前記認証タグti4が正当である場合、前記T'iと前記Kilとの排他的論理和によりK1lを生成し、前記T'と前記K1lとの排他的論理和によりk1||s1を生成し、属性ベース暗号の復号アルゴリズムにより、前記属性秘密鍵uskiを用いて、前記暗号文CT'iから第１共通鍵K1を復号し、前記代表通信装置U1が、メッセージ認証子の検証アルゴリズムにより、前記認証鍵mk10と前記R1, c1, Rn, R2, T1, T', U1, sid, k', CT'1を用いて、前記認証タグt14を検証し、前記認証タグti4が正当である場合、属性ベース暗号の復号アルゴリズムにより、前記属性秘密鍵uskiを用いて、前記暗号文CT'1から第１共通鍵K1を復号する第１共通鍵受信ステップと、前記通信装置Ui（i∈{1, …, n}）が、擬似ランダム関数により前記セッションID sidおよび前記k'と前記k1との排他的論理和を用いて生成した値により、第２共通鍵K2を生成し、擬似ランダム関数により前記sid, K1を用いて生成した値と疑似ランダム関数により前記sid, K2を用いて生成した値の排他的論理和により、セッション鍵SKを生成するセッション鍵生成ステップと、前記通信装置Ui（i∈{1, …, n}）が、鍵導出関数により、前記認証鍵mki0と前記認証鍵更新情報μi、または、前記認証鍵mki0から新しい認証鍵mki1を生成する認証鍵更新ステップとを含む。
【００１７】
本発明の一態様は、nを2以上の整数、α, βを次式で定義される値とし、
【００１８】
【数２】
2019125956.tif 000004
【００１９】
鍵交換サーバ装置Sとn台の通信装置Ui(i=1, …, n)を含む鍵交換システムが実行する鍵交換方法であって、U1を前記通信装置U1, …, Unから選択された1台の代表通信装置、timeoを現在時刻、IDを通信装置を表す述語変数、TFmをタイムフレームを表す述語変数とし、前記鍵交換サーバ装置Sの記録部には、長期秘密鍵SSKs=(msk, stS, st'S)（ただし、mskは属性ベース暗号のマスター秘密鍵、stS、st'Sはそれぞれ秘密ストリング）が記録されており、前記通信装置Ui(i=1, …, n)の記録部には、長期秘密鍵SSKi=(ski, sti, st'i)（ただし、skiは前記通信装置Uiの公開鍵暗号の秘密鍵、sti、st'iはそれぞれ秘密ストリング）が記録されており、前記鍵交換サーバ装置Sが、i=1, …, nについて、属性をAi=(Ui, timeo)として、属性ベース暗号の鍵導出アルゴリズムにより、属性ベース暗号の公開パラメータParamsと前記マスター秘密鍵mskを用いて、前記通信装置Uiの属性秘密鍵uskiを生成し、メッセージ認証子の鍵生成アルゴリズムにより、前記通信装置UiのMAC鍵mki0を認証鍵として生成し、公開鍵暗号の暗号化アルゴリズムにより、前記通信装置Uiの長期公開鍵SPKi=pki（ただし、pkiは前記通信装置Uiの公開鍵暗号の公開鍵）を用いて、前記属性秘密鍵uskiおよび前記認証鍵mki0を暗号化し、暗号文CTiを生成し、前記暗号文CTiを前記通信装置Ui（i∈{1, …, n}）へ送信する認証鍵生成ステップと、前記通信装置Ui(i=1, …, n)が、公開鍵暗号の復号アルゴリズムにより、前記秘密鍵skiを用いて、前記暗号文CTiを復号し、前記属性秘密鍵uskiと前記認証鍵mki0を取得する認証鍵受信ステップと、前記通信装置Ui(i=1, …, n)が、ねじれ擬似ランダム関数により前記秘密ストリングsti, st'iを用いてri, ki, siを生成し、第１鍵Ri=gr_iおよびci=gk_ihs_iを生成し、 (Ri, ci)を前記鍵交換サーバ装置Sへ送信する第１鍵生成ステップと、前記鍵交換サーバ装置Sが、衝突困難ハッシュ関数により、前記c1, …, cnを用いてセッションID sidを生成し、(sid, Rα, Rβ)を前記通信装置Ui（i∈{1, …, n}）へ送信するセッションID生成ステップと、前記通信装置Ui（i∈{2, …, n}）が、擬似ランダム関数により前記sid, Rαr_iを用いてKilを生成し、擬似ランダム関数により前記sid, Rβr_iを用いてKirを生成し、前記Kilと前記Kirとの排他的論理和により第２鍵Tiを生成し、前記代表通信装置U1が、擬似ランダム関数により前記sid, Rnr_1を用いてK1lを生成し、擬似ランダム関数により前記sid, R2r_1を用いてK1rを生成し、前記K1lと前記K1rとの排他的論理和により第２鍵T1を生成し、前記K1lとk1||s1との排他的論理和によりT'を生成する第２鍵生成ステップと、前記通信装置Ui（i∈{2, …, n}）が、(ki, si, Ti)を前記鍵交換サーバ装置Sへ送信し、前記代表通信装置U1が、(T1, T')を前記鍵交換サーバ装置Sへ送信する第２鍵送信ステップと、前記鍵交換サーバ装置Sが、ねじれ擬似ランダム関数により、前記秘密ストリングstS, st'Sを用いて、kS, 第１共通鍵K1を生成し、前記k2, …, kn, ksの排他的論理和により、k'を生成し、i=2, …, nについて、前記T1, …, Ti-1の排他的論理和により、T'iを生成し、i=1, …, nについて、条件Pi=(ID=Ui)∧(timeo∈TFm)として、属性ベース暗号の暗号化アルゴリズムにより、前記公開パラメータParamsを用いて、前記第１共通鍵K1を暗号化して、暗号文CT'iを生成する第１共通鍵生成ステップと、前記鍵交換サーバ装置Sが、i=2, …, nについて、(c1, k', T'i, T', CT'i)を前記通信装置Uiへ送信し、i=1について、(k', CT'1)を前記代表通信装置U1へ送信する第１共通鍵送信ステップと、認証鍵更新情報μi(i=1, …, n)を前記鍵交換サーバ装置Sと前記通信装置Uiの間で既に共有されている情報であるとし、前記鍵交換サーバ装置Sが、i=1, …, nについて、鍵導出関数により、前記認証鍵mki0と前記認証鍵更新情報μi、または、前記認証鍵mki0から新しい認証鍵mki1を生成する認証鍵更新ステップと、前記通信装置Ui（i∈{2, …, n}）が、前記T'iと前記Kilとの排他的論理和によりK1lを生成し、前記T'と前記K1lとの排他的論理和によりk1||s1を生成し、属性ベース暗号の復号アルゴリズムにより、前記属性秘密鍵uskiを用いて、前記暗号文CT'iから第１共通鍵K1を復号し、前記代表通信装置U1が、属性ベース暗号の復号アルゴリズムにより、前記属性秘密鍵uskiを用いて、前記暗号文CT'1から第１共通鍵K1を復号する第１共通鍵受信ステップと、前記通信装置Ui（i∈{1, …, n}）が、擬似ランダム関数により前記セッションID sidおよび前記k'と前記k1との排他的論理和を用いて生成した値により、第２共通鍵K2を生成し、擬似ランダム関数により前記sid, K1を用いて生成した値と疑似ランダム関数により前記sid, K2を用いて生成した値の排他的論理和により、セッション鍵SKを生成するセッション鍵生成ステップと、前記通信装置Ui（i∈{1, …, n}）が、鍵導出関数により、前記認証鍵mki0と前記認証鍵更新情報μi、または、前記認証鍵mki0から新しい認証鍵mki1を生成する認証鍵更新ステップとを含む。
【発明の効果】
【００２０】
本発明によれば、長期秘密鍵が漏洩したとしても、暗号鍵を取得することができない鍵交換を実現することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】鍵交換システム１０の構成の一例を示すブロック図。
【図２】鍵交換サーバ装置１００の構成の一例を示すブロック図。
【図３】通信装置２００の構成の一例を示すブロック図。
【図４】鍵交換サーバ装置１００におけるセットアップ処理の一例を示す図。
【図５】通信装置２００におけるセットアップ処理の一例を示す図。
【図６】鍵配送処理の一例を示す図。
【図７】ステップＳ１１５の詳細を示す図。
【発明を実施するための形態】
【００２２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２３】
＜表記法・用語＞
実施形態の説明に先立って、この明細書における表記法や用語について説明する。
【００２４】
^（キャレット）は上付き添字を表す。例えば、xy^zはyzがxに対する上付き添字であり、xy^zはyzがxに対する下付き添字であることを表す。また、_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
【００２５】
集合Sから要素xを一様ランダムに取り出すことを、x∈RSと表記する。
【００２６】
pを素数とし、Gを位数pの巡回群とする。また、g, hを群Gの生成元とする。
【００２７】
Zを整数の集合とし、Zpを素数pに対する剰余類環とする。
【００２８】
κ（∈Z）をセキュリティパラメータとする。Kspaceκ={0, 1}κをκビットの鍵空間とする。また、{0, 1}*を長さが任意のビット列の集合とする。
【００２９】
|・|は値・のビット長とする。
【００３０】
［タイムフレーム(Time Frame)］
ある時間区間をtとし、タイムフレームTFm(m=1, 2, …)をTFm:={time(m-1)t+1, …, timemt}とする（ただし、tは1以上の整数）。また、現在時刻timeoに対して、timeo∈TFmとするとき、TFmをタイムフレームを表す述語変数と呼ぶ。
【００３１】
［公開鍵暗号］
公開鍵暗号PKEをPKE=(Gen, Enc, Dec)とする。鍵生成アルゴリズムGenは1κを入力とし、公開鍵pkと秘密鍵skのペアを出力する。つまり、(pk, sk)←Gen(1κ)である。このとき、平文空間Mpkが定まり、平文空間Mpkにはpkが含まれているものとする。特に平文空間Mpkの指定がない場合はMpk:={0, 1}κとする。暗号化アルゴリズムEncは公開鍵pkと平文m∈Mpkを入力とし、暗号文CTを出力する。つまり、CT←Encpk(m)である。復号アルゴリズムDecは秘密鍵skと暗号文CTを入力とし、平文mを出力する。つまり、m←Decsk(CT)である。なお、復号に失敗した場合は、平文mの代わりに復号失敗を表す記号である⊥を出力する。具体的な構成例として、RSA-OAEP(Optimal Asymmetric Encryption Padding)がある。
【００３２】
［擬似ランダム関数］
RFκ:={f|f:{0, 1}κ×Kspaceκ→{0,1}κ}をランダム関数の族、関数f∈RRFκをランダム関数とする。擬似ランダム関数とは、以下の条件を満たす、シードs∈{0, 1}κをインデックスとする関数族{Fs}sに属する関数Fs:{0, 1}κ×Kspaceκ→{0, 1}κのことである。
（条件１）入力xが与えられたとき多項式時間でFs(x)が計算可能である。
（条件２）任意の確率多項式時間アルゴリズムDに対して、ランダム関数fの出力、擬似ランダム関数Fsの出力のいずれかが与えられたとしても、アルゴリズムDによりどちらの関数から出力された値であるかを識別できる確率は無視できるほど小さい。
【００３３】
具体的な構成例として、Blum-Micaliの擬似乱数生成器を用いて擬似ランダム関数を構成する、Goldreich-Goldwasser-Micaliの擬似ランダム関数がある（参考非特許文献１）。
（参考非特許文献１：O. Goldreich, S. Goldwasser, and S. Micali, “How to Construct Random Functions”, Journal of the ACM, vol.33, Issue 4, pp.792-807, 1986.）
【００３４】
［ねじれ擬似ランダム関数］
ねじれ擬似ランダム関数tPRF:{0, 1}κ×Kspaceκ×Kspaceκ×{0, 1}κ→Rngκ（ただし、Rngκは関数の値域）は、擬似ランダム関数Fsと排他的論理和を用いて次式のように構成される。
【００３５】
【数３】
2019125956.tif 000005
【００３６】
ただし、a,b'∈{0, 1}κ, a', b∈Kspaceκである。
【００３７】
なお、ねじれ擬似ランダム関数tPRFは、以下の条件を満たす。
（条件）任意の確率多項式時間アルゴリズムDに対して、ランダム関数fの出力、ねじれ擬似ランダム関数tPRFの出力のいずれかが与えられたとしても、アルゴリズムDによりどちらの関数から出力された値であるかを識別できる確率は無視できるほど小さい。
【００３８】
［衝突困難ハッシュ関数］
衝突困難ハッシュ関数TCR:{0, 1}*→{0, 1}κとは、以下の条件を満たすハッシュ関数のことである。
（条件）任意の多項式時間アルゴリズムAに対して、{0, 1}*からランダムに選んだxを与えても、アルゴリズムAがx≠x'でTCR(x)=TCR(x')となるx'を見つけることが困難である。
【００３９】
具体的な構成例として、SHA256がある。
【００４０】
［属性ベース暗号］
属性ベース暗号ABEをABE=(Setup, Der, AEnc, ADec)とする。セットアップアルゴリズムSetupは1κと属性を定義する情報attを入力とし、公開パラメータParamsとマスター秘密鍵mskを出力する。つまり、(Params,  msk)←Setup(1κ, att)である。鍵導出アルゴリズムDerは公開パラメータParamsとマスター秘密鍵mskと属性Aiを入力とし、ユーザUiの属性秘密鍵uskiを出力する。つまり、uski←Der(Params, msk, Ai)である。暗号化アルゴリズムAEncは公開パラメータParamsと条件Pと平文mを入力とし、暗号文CTを出力する。つまり、CT←AEnc(Params, P, m)である。復号アルゴリズムADecは公開パラメータParamsとユーザUiの属性秘密鍵uskiと暗号文CTを入力とし、Ai∈Pの場合は平文mを出力する。つまり、m←ADec(Params, uski, CT)である。なお、Ai∈Pでない場合は記号⊥を出力する。具体的な構成例として、インテリジェント暗号がある（参考非特許文献２）。
（参考非特許文献２：“インテリジェント暗号”，［online］，［平成２９年１２月２０日検索］，インターネット<URL: http://www.seclab.ecl.ntt.co.jp/project/data-security/intelligent-crypto.html>）
【００４１】
［メッセージ認証子］
メッセージ認証子MACをMAC=(MGen, Tag, Ver)とする。MAC鍵生成アルゴリズムMGenは1κを入力とし、MAC鍵mkを出力する（ただし、|mk|≧κとする）。つまり、mk←MGen(1κ)である。タグ生成アルゴリズムTagはMAC鍵mkと平文m∈{0,1}*を入力とし、認証タグtを出力する。つまり、t←Tagmk(m)である。検証アルゴリズムVerはMAC鍵mkと平文m∈{0,1}*と認証タグtを入力とし、認証タグtが正しければ1を、正しくなければ0を出力する。つまり、1←Vermk(m, t)（認証タグtが正しい場合）または0←Vermk(m, t)（認証タグtが正しくない場合）である。具体的な構成として、HMACがある（参考非特許文献４）。
（参考非特許文献４：F. Song and A. Yun, “Quantum Security of NMAC and Related Constructions PRF Domain Extension Against Quantum Attacks”, CRYPTO 2017, LNCS 10402, pp.283-309, 2017.）
【００４２】
［鍵導出関数(Key Derivation Function)］
鍵集合Kk, Kdに対して、関数KDF:Kk×Kd→Kkを鍵導出関数と定義する。ここでは、鍵導出関数KDFは、以下の条件を満たすものとする。
（条件）任意の多項式時間アルゴリズムDに対して、アルゴリズムDによりKDFの出力と鍵集合Kkから一様ランダムに選択した鍵とが区別できる確率は無視できるほど小さい。
【００４３】
具体的な構成例として、ハッシュ関数を利用して構成したものがある。
【００４４】
＜第一実施形態＞
【００４５】
［システム構成］
鍵交換システム１０は、図１に例示するように、鍵交換サーバ装置１００およびN（≧2）台の通信装置２００1, …, ２００Nを含む。この実施形態では、鍵交換サーバ装置１００および通信装置２００1, …, ２００Nはそれぞれ通信網９００へ接続される。通信網９００は、鍵交換サーバ装置１００が通信装置２００1, …, ２００Nそれぞれと通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網である。この実施形態では、通信装置２００1, …, ２００N同士は通信できなくともよい。通信網９００は安全が確保された通信路である必要はなく、例えばインターネットなどを用いることができる。
【００４６】
鍵交換サーバ装置１００は、図２に例示するように、セットアップ部１０１、秘密ストリング生成部１０２、長期鍵生成部１０３、認証鍵生成部１１１、第１鍵受信部１１２、セッションID生成部１１３、第２鍵受信部１１４、第１共通鍵生成部１１５、第１共通鍵送信部１１６、認証鍵更新部１１７、記録部１９０を含む。記録部１９０は、鍵交換サーバ装置１００の処理に必要な情報を適宜記録する構成部である。
【００４７】
通信装置２００は、図３に例示するように、公開鍵生成部２０１、秘密ストリング生成部２０２、長期鍵生成部２０３、認証鍵受信部２１１、第１鍵生成部２１２、セッションID受信部２１３、第２鍵生成部２１４、第２鍵送信部２１５、第１共通鍵受信部２１６、セッション鍵生成部２１７、秘密情報管理部２１８、認証鍵更新部２１９、記録部２９０を含む。記録部２９０は、通信装置２００の処理に必要な情報を適宜記録する構成部である。
【００４８】
この鍵交換サーバ装置１００および通信装置２００1, …, ２００Nが、図４、図５、図６、図７に例示する各ステップの処理を行うことにより実施形態の鍵交換方法が実現される。
【００４９】
鍵交換サーバ装置１００および通信装置２００1, …, ２００Nは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。各装置は、例えば、中央演算処理装置の制御のもとで各処理を実行する。各装置に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。各装置が備える各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００５０】
鍵交換サーバ装置１００が備える記録部１９０および通信装置２００1, …, ２００Nが備える記録部２９０は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。各記録部は秘密情報を記憶するため、耐タンパ性を有する記憶装置（例えば、SIMカードなど）であることが望ましい。
【００５１】
［セットアップ処理］
図４及び図５を参照して、実施形態の鍵交換方法におけるセットアップ処理手続きを説明する。
【００５２】
以降の説明では、以下のように記号を定義する。Sは鍵交換サーバ装置１００を示し、Ui（i∈{1, …, N}）はN台の通信装置２００1, …, ２００Nを示すものとする。Gを素数位数pの巡回群とする。g, hをそれぞれ群Gの生成元とする。F: {0, 1}κ×G→Zp2、F': {0, 1}κ×Zp→Kspaceκ、F'': {0, 1}κ×Kspaceκ→{0, 1}κ、F''': {0, 1}κ×Kspaceκ→Zpを擬似ランダム関数とする。tPRF: {0, 1}κ×Kspaceκ×Kspaceκ×{0, 1}κ→Zp、tPRF': {0, 1}κ×Kspaceκ×Kspaceκ×{0, 1}κ→Kspaceκをねじれ擬似ランダム関数とする。TCR:{0, 1}*→{0, 1}κを衝突困難ハッシュ関数とする。KDF: {0, 1}*×{0, 1}κ→{0, 1}*を鍵導出関数とする。
【００５３】
まず、鍵交換サーバ装置Sのセットアップ処理について説明する（図４参照）。
【００５４】
ステップＳ１０１において、鍵交換サーバ装置Sのセットアップ部１０１は、属性ベース暗号ABEのセットアップアルゴリズムSetupにより公開パラメータParamsおよびマスター秘密鍵mskを生成する（(Params, msk)←Setup(1κ, att)）。
【００５５】
ステップＳ１０２において、鍵交換サーバ装置Sの秘密ストリング生成部１０２は、秘密ストリング(stS, st'S) (stS∈RKspaceκ, st'S∈R{0, 1}κ)を生成する。
【００５６】
ステップＳ１０３において、鍵交換サーバ装置Sの長期鍵生成部１０３は、長期秘密鍵SSKs=(msk, stS, st'S)、長期公開鍵SPKs=(Params, p, G, g, h, TCR, tPRF, tPRF', F, F', F'', F''')を生成する。長期鍵生成部１０３は、長期秘密鍵SSKs、長期公開鍵SPKsを記録部１９０に記録する。また、長期鍵生成部１０３は、長期公開鍵SPKsを通信装置U1, …, UNへ送信する。
【００５７】
次に、通信装置Ui（i∈{1, …, N}）のセットアップ処理について説明する（図５参照）。
【００５８】
ステップＳ２０１において、通信装置Uiの公開鍵生成部２０１は、公開鍵暗号PKEの鍵生成アルゴリズムGenにより通信装置Uiの公開鍵pkiおよび秘密鍵skiのペアを生成する（(pki, ski)←Gen(1κ)）。
【００５９】
ステップＳ２０２において、通信装置Uiの秘密ストリング生成部２０２は、秘密ストリング(sti, st'i) (sti∈RKspaceκ、st'i∈{0, 1}κ)を生成する。
【００６０】
ステップＳ２０３において、通信装置Uiの長期鍵生成部２０３は、長期秘密鍵SSKi=(ski, sti, st'i)、長期公開鍵SPKi=pkiを生成する。長期鍵生成部２０３は、長期秘密鍵SSKi、長期公開鍵SPKiを記録部２９０に記録する。また、長期鍵生成部２０３は、長期公開鍵SPKiを鍵交換サーバ装置Sへ送信する。
【００６１】
［鍵配送処理］
図６及び図７を参照して、実施形態の鍵交換方法における鍵配送処理手続きを説明する。この処理は、DMKDプロトコルにおけるDist（鍵配送）フェーズでの処理に対応するものである。
【００６２】
以下では、N台の通信装置２００1, …, ２００Nのうち任意のn（2≦n≦N）台の通信装置Ui（i∈{1, …, n}）がセッション鍵SKの共有を行うものとする。S, Uiを各アルゴリズムの入力とする場合、各装置を一意に特定する識別子を表すものとする。
【００６３】
ステップＳ１１１において、鍵交換サーバ装置Sの認証鍵生成部１１１は、通信装置Ui（i∈{1, …, n}）がセッションを開始したときに、そのセッションが通信装置UiのタイムフレームTFmにおける最初のセッションだった場合、現在時刻をtimeo∈TFmとし、属性をAi=(Ui, timeo)として、属性ベース暗号ABEの鍵導出アルゴリズムDerにより、通信装置Uiの属性秘密鍵uski←Der(Params, msk, Ai)を生成する。また、認証鍵生成部１１１は、メッセージ認証子MACの鍵生成アルゴリズムMGenにより、通信装置UiのMAC鍵mki0←MGen(1κ)を認証鍵として生成する。認証鍵生成部１１１は、認証鍵mki0を記録部１９０に記録する。そして、認証鍵生成部１１１は、公開鍵暗号PKEの暗号化アルゴリズムEncにより、通信装置Uiの長期公開鍵SPKi=pkiを用いて属性秘密鍵uskiおよび認証鍵mki0を暗号化し、暗号文CTi←Encpk_i(uski, mki0)を生成する。認証鍵生成部１１１は、暗号文CTiを通信装置Ui（i∈{1, …, n}）へ送信する。
【００６４】
ステップＳ２１１において、通信装置Ui（i∈{1, …, n}）の認証鍵受信部２１１は、公開鍵暗号PKEの復号アルゴリズムDecにより、通信装置Uiの秘密鍵skiを用いて鍵交換サーバ装置Sから受信した暗号文CTiを復号し、属性秘密鍵および認証鍵(uski, mki0)←Decsk_i(CTi)を取得する。認証鍵受信部２１１は、属性秘密鍵uskiおよび認証鍵mki0を記録部２９０へ記録する。
【００６５】
ステップＳ２１２において、通信装置Ui（i∈{1, …, n}）の第１鍵生成部２１２は、~ri∈R{0, 1}κ, ~r'i∈RKspaceκ, ~ki∈R{0, 1}κ, ~k'i∈RKspaceκ, ~si∈R{0, 1}κ, ~s'i∈RKspaceκを生成し、短期秘密鍵ESKi=(~ri, ~r'i, ~ki, ~k'i, ~si, ~s'i)を生成し、短期秘密鍵ESKiを記録部２９０に記録する。第１鍵生成部２１２は、ねじれ擬似ランダム関数tPRFにより、ri=tPRF(~ri, ~r'i, sti, st'i), ki=tPRF(~ki, ~k'i, sti, st'i), si=tPRF(~si, ~s'i, sti, st'i)を生成する。また、第１鍵生成部２１２は、第１鍵Ri=gr_i, ci=gk_ihs_iを生成する。第１鍵生成部２１２は、メッセージ認証子MACのタグ生成アルゴリズムTagにより、認証鍵mki0を用いてRi, ciから認証タグti1=Tagmk_i^0(Ri, ci)を生成する。そして、第１鍵生成部２１２は、(Ri, ci, ti1)を鍵交換サーバ装置Sへ送信する。
【００６６】
ステップＳ１１２において、鍵交換サーバ装置Sの第１鍵受信部１１２は、通信装置Uiから(Ri, ci, ti1)を受信する。このとき、第１鍵受信部１１２は、すべての通信装置U1, …, Unから(R1, c1, t11), …, (Rn, cn, tn1)を受信するまで待機する。第１鍵受信部１１２は、メッセージ認証子MACの検証アルゴリズムVerにより、通信装置Uiの認証鍵mki0を用いて、Vermk_i~0(Ri, ci, ti1)を計算し、認証タグti1を検証する。認証タグti1が正当(ti1=1)でなければ、第１鍵受信部１１２は、処理を終了する。
【００６７】
ステップＳ１１３において、鍵交換サーバ装置SのセッションID生成部１１３は、衝突困難ハッシュ関数TCRにより、通信装置U1, …, Unから受信したc1, …, cnを用いて、sid=TCR(c1, …, cn)をセッションIDとして生成する。また、n台の通信装置U1, …, Unから1台の通信装置を代表者として選択する。代表者の選択方法は任意であり、例えば、予め定めておいた優先順位が最も高い通信装置を選択するのでよい。ここでは、通信装置U1が選択されたものとし、U1を代表通信装置と呼ぶ。また、代表通信装置U1以外のn-1台の通信装置Ui（i∈{2, …, n}）を一般通信装置と呼ぶ。セッションID生成部１１３は、i=1, …, nについて、メッセージ認証子MACのタグ生成アルゴリズムTagにより、認証鍵mki0を用いて認証タグti2=Tagmk_i^0(sid, Rα, Rβ)を生成し、(sid, Rα, Rβ, ti2)を通信装置Ui（i∈{1, …, n}）へ送信する。ただし、α, βは次式により定義される。
【００６８】
【数４】
2019125956.tif 000006
【００６９】
また、鍵交換サーバ装置Sは通信装置U1が代表通信装置であることを通信装置U1に通知する。
【００７０】
ステップＳ２１３において、通信装置Ui（i∈{1, …, n}）のセッションID受信部２１３は、鍵交換サーバ装置Sから(sid, Rα, Rβ, ti2)を受信する。通信装置Uiは、(sid, Rα, Rβ, ti2)を受け取り次第、以降の処理を実行する。i=2, …, nの場合、すなわち通信装置Uiが一般通信装置Uiであれば、ステップＳ２１４iへ処理を進める。i=1の場合、すなわち通信装置Uiが代表通信装置U1であれば、ステップＳ２１４1へ処理を進める。
【００７１】
ステップＳ２１４iにおいて、一般通信装置Ui（i∈{2, …, n}）の第２鍵生成部２１４は、メッセージ認証子MACの検証アルゴリズムVerにより、認証鍵mki0を用いて、Vermk_i~0(sid, Rα, Rβ, ti2) を計算し、認証タグti2を検証する。認証タグti2が正当(ti2=1)でなければ、第２鍵生成部２１４は、処理を終了する。認証タグti2が正当である場合、第２鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rαr_i)を用いてKilを生成し、擬似ランダム関数Fにより(sid, Rβr_i)を用いてKirを生成し、KilとKirとの排他的論理和により第２鍵Tiを生成する。
【００７２】
【数５】
2019125956.tif 000007
【００７３】
ステップＳ２１５iにおいて、一般通信装置Ui（i∈{2, …, n}）の第２鍵送信部２１５は、メッセージ認証子MACのタグ生成アルゴリズムTagにより、認証鍵mki0を用いて、認証タグti3=Tagmk_i^0(Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sid)を生成する。第２鍵送信部２１５は、(ki, si, Ti, ti3)を鍵交換サーバ装置Sへ送信する。
【００７４】
ステップＳ２１４1において、代表通信装置U1の第２鍵生成部２１４は、メッセージ認証子MACの検証アルゴリズムVerにより、認証鍵mk10を用いて、Vermk_1~0(sid, Rn, R2, t12) を計算し、認証タグti2を検証する。認証タグt12が正当(t12=1)でなければ、第２鍵生成部２１４は、処理を終了する。認証タグt12が正当である場合、第２鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rnr_1)を用いてK1lを生成し、擬似ランダム関数Fにより(sid, R2r_1)を用いてK1rを生成し、K1lとK1rとの排他的論理和により第２鍵T1を生成し、K1lとk1||s1との排他的論理和によりT'を生成する。ただし、||は連結演算子である。
【００７５】
【数６】
2019125956.tif 000008
【００７６】
ステップＳ２１５1において、代表通信装置U1の第２鍵送信部２１５は、メッセージ認証子MACのタグ生成アルゴリズムTagにより、認証鍵mk10を用いて、認証タグt13=Tagmk_1^0(R1, c1, Rn, R2, T1, T', U1, sid)を生成する。第２鍵送信部２１５は、(T1, T', t13)を鍵交換サーバ装置Sへ送信する。
【００７７】
ステップＳ１１４iにおいて、鍵交換サーバ装置Sの第２鍵受信部１１４は、i=2, …, nについて、一般通信装置Uiから(ki, si, Ti, ti3)を受信し、メッセージ認証子MACの検証アルゴリズムVerにより、一般通信装置Uiの認証鍵mki0を用いて、Vermk_i^0(Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sid, ti3) を計算し、認証タグti3を検証する。認証タグti3が正当(ti3=1)でなければ、第２鍵受信部１１４は、処理を終了する。
【００７８】
ステップＳ１１４1において、鍵交換サーバ装置Sの第２鍵受信部１１４は、代表通信装置U1から(T1, T', t13)を受信し、メッセージ認証子MACの検証アルゴリズムVerにより、代表通信装置U1の認証鍵mk10を用いて、Vermk_1^0(R1, c1, Rn, R2, T1, T', U1, sid, t13) を計算し、認証タグti3を検証する。認証タグt13が正当(t13=1)でなければ、第２鍵受信部１１４は、処理を終了する。
【００７９】
ステップＳ１１５ａにおいて、鍵交換サーバ装置Sの第１共通鍵生成部１１５は、~kS∈R{0, 1}κ,~k'S∈RKspaceκ, ~K1∈R{0, 1}κ, ~K'1∈RKspaceκを生成し、ねじれ擬似ランダム関数tPRFにより、kS=tPRF(~kS, ~k'S, stS, st'S), 第１共通鍵K1=tPRF(~K1, ~K'1, stS, st'S)を生成する。また、第１共通鍵生成部１１５は、次式のように、k2, …, kn, ksの排他的論理和により、k'を生成する。
【００８０】
【数７】
2019125956.tif 000009
【００８１】
ステップＳ１１５ｂにおいて、鍵交換サーバ装置Sの第１共通鍵生成部１１５は、i=2, …, nについて、次式のように、T1, …, Ti-1の排他的論理和により、T'iを生成する。
【００８２】
【数８】
2019125956.tif 000010
【００８３】
ステップＳ１１５ｃにおいて、鍵交換サーバ装置Sの第１共通鍵生成部１１５は、i=1, …, nについて、条件Pi=(ID=Ui)∧(timeo∈TFm)として、属性ベース暗号ABEの暗号化アルゴリズムAEncにより第１共通鍵K1を暗号化して、暗号文CT'i←AEnc(Params, Pi, K1)を生成する。ここで、IDは通信装置を表す述語変数である。
【００８４】
ステップＳ１１６iにおいて、鍵交換サーバ装置Sの第１共通鍵送信部１１６は、i=2, …, nについて、メッセージ認証子MACのタグ生成アルゴリズムTagにより、一般通信装置Uiの認証鍵mki0を用いて、認証タグti4=Tagmk_i^0(Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'i)を生成する。第１共通鍵送信部１１６は、(c1, k', T'i, T', CT'i, ti4)を一般通信装置Uiへ送信する。
【００８５】
ステップＳ１１６1において、鍵交換サーバ装置Sの第１共通鍵送信部１１６は、メッセージ認証子MACのタグ生成アルゴリズムTagにより、代表通信装置U1の認証鍵mk10を用いて、認証タグt14=Tagmk_1^0(R1, c1, Rn, R2, T1, T', U1, sid, k', CT'1)を生成する。第１共通鍵送信部１１６は、(k', CT'1, t14)を代表通信装置U1へ送信する。
【００８６】
ステップＳ１１７において、鍵交換サーバ装置Sの認証鍵更新部１１７は、i=1, …, nについて、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0, sid）を生成する。また、認証鍵更新部１１７は、認証鍵mki0を記録部１９０から削除し、新しい認証鍵mki1を記録部１９０に記録する。
【００８７】
ステップＳ２１６iにおいて、一般通信装置Ui（i∈{2, …, n}）の第１共通鍵受信部２１６は、鍵交換サーバ装置Sから(c1, k', T'i, T', CT'i, ti4)を受信し、メッセージ認証子MACの検証アルゴリズムVerにより、一般通信装置Uiの認証鍵mki0を用いて、Vermk_i^0(Ri, ci, Rα, Rβ, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'i, ti4) を計算し、認証タグti4を検証する。認証タグti4が正当(ti4=1)でなければ、第１共通鍵受信部２１６は、処理を終了する。認証タグti4が正当である場合、第１共通鍵受信部２１６は、次式のように、T'iとKilとの排他的論理和によりK1lを生成し、T'とK1lとの排他的論理和によりk1||s1を生成する。
【００８８】
【数９】
2019125956.tif 000011
【００８９】
また、第１共通鍵受信部２１６は、属性ベース暗号ABEの復号アルゴリズムADecにより、通信装置Uiの属性秘密鍵uskiを用いて、第１共通鍵K1←ADecusk_i(CT'i, Pi)を復号する。
【００９０】
ステップＳ２１６1において、代表通信装置U1の第１共通鍵受信部２１６は、鍵交換サーバ装置Sから(k', CT'1, t14)を受信し、メッセージ認証子MACの検証アルゴリズムVerにより、代表通信装置U1の認証鍵mk10を用いて、Vermk_1^0(R1, c1, Rn, R2, T1, T', U1, sid, k', CT'1, t14) を計算し、認証タグt4を検証する。認証タグt14が正当(ti4=1)でなければ、第１共通鍵受信部２１６は、処理を終了する。第１共通鍵受信部２１６は、属性ベース暗号ABEの復号アルゴリズムADecにより、代表通信装置U1の属性秘密鍵usk1を用いて、第１共通鍵K1←ADecusk_1(CT'1, P1)を復号する。
【００９１】
ステップＳ２１７において、通信装置Ui（i∈{1, …, n}）のセッション鍵生成部２１７は、次式のように、擬似ランダム関数F'によりセッションID sidおよびk'とk1との排他的論理和を用いて生成した値により、第２共通鍵K2を生成する。
【００９２】
【数１０】
2019125956.tif 000012
【００９３】
そして、セッション鍵生成部２１７は、次式のように、擬似ランダム関数F"により(sid, K1)を用いて生成した値と疑似ランダム関数F"により(sid, K2)を用いて生成した値の排他的論理和により、セッション鍵SKを生成する。
【００９４】
【数１１】
2019125956.tif 000013
【００９５】
なお、通信装置Ui（i∈{1, …, n}）で共有される第１共通鍵K1、第２共通鍵K2、セッション鍵SKをそれぞれ暗号鍵ともいう。
【００９６】
ステップＳ２１８iにおいて、一般通信装置Ui（i∈{2, …, n}）の秘密情報管理部２１８は、次式により秘密情報Hil、Hir、rを生成し、記録部２９０に記録する。
【００９７】
【数１２】
2019125956.tif 000014
【００９８】
ステップＳ２１８1において、代表通信装置U1の秘密情報管理部２１８は、次式により秘密情報Hil、Hir、rを生成し、記録部２９０に記録する。
【００９９】
【数１３】
2019125956.tif 000015
【０１００】
ステップＳ２１９において、通信装置Ui（i∈{1, …, n}）の認証鍵更新部２１９は、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0, sid）を生成する。また、認証鍵更新部２１９は、認証鍵mki0を記録部２９０から削除し、新しい認証鍵mki1を記録部２９０に記録する。
【０１０１】
本実施形態の発明によれば、長期秘密鍵が漏洩したとしても、暗号鍵を取得することができない鍵交換を実現することが可能となる。
【０１０２】
本実施形態の発明によれば、あるセッションで暗号鍵を交換するためには、直近で更新された認証鍵が必要になる。しかし、直近で更新された認証鍵を取得するためには、その１つ前に更新された認証鍵が必要である。したがって、１番目の認証鍵が安全に交換されている場合、長期秘密鍵が漏洩しても攻撃者は認証鍵を取得することができない。これにより、攻撃者が長期秘密鍵を取得したとしてもなりすましにより暗号鍵を取得することはできない。
【０１０３】
ここでは、DMKDプロトコルにおけるDist（鍵配送）フェーズでの処理に対応する処理手続きについて説明したが、Join（追加）フェーズ、Leave（離脱）フェーズ、Update（更新）フェーズでの処理に対応する処理手続きについても同様である。つまり、鍵交換を安全に実行するためには、いずれかのフェーズが起こる度に、鍵導出関数KDFを用いて、認証鍵を新しく生成するようにすればよい。以下、詳細に説明する。
【０１０４】
現在グループに参加している通信装置及び鍵交換サーバ装置が保持している認証鍵をmkik（kは1以上の整数）とする。例えば、グループが生成され初めて暗号鍵が共有された直後の認証鍵はmki1である（つまり、k=1）。いずれかのフェーズが起こり、暗号鍵が共有されたら、鍵導出関数KDFを用いて、認証鍵mkikと当該セッションのセッションIDであるsidk+1から認証鍵mkik+1←KDF(mkik, sid k+1）を生成する。各装置は、認証鍵mkikを記録部から削除し、新しい認証鍵mkik+1を記録部に記録する。
【０１０５】
＜変形例＞
メッセージ認証子MACを用いたインテグリティを保証する処理、つまり、Ｓ２１２における認証タグti1の生成処理とＳ１１２における認証タグti1の検証処理、Ｓ１１３における認証タグti2の生成処理とＳ２１３における認証タグti2の検証処理、Ｓ２１５における認証タグti3の生成処理とＳ１１４における認証タグti3の検証処理、Ｓ１１６における認証タグti4の生成処理とＳ２１６における認証タグti4の検証処理については省略してもよい。
【０１０６】
＜変形例２＞
また、通信装置Uiは、Ｓ２１７において、擬似ランダム関数を用いてsidから２つの鍵、つまり、第２共通鍵K2とセッション鍵SKを生成し、この２つの鍵を通信装置Uiの間で共有するようにしているが、第２共通鍵K2のみを生成し、共有するようにしてもよい。
【０１０７】
＜変形例３＞
Ｓ１１７及びＳ２１９における認証鍵更新処理では、現時点の認証鍵とセッションIDを鍵導出関数の入力として新しい認証鍵を生成しているが、鍵導出関数の入力として、セッションIDの代わりに以下のデータのいずれかを用いてもよい。
（１）Ｓ２１２及びＳ１１２における処理により共有されるRiまたはci
この場合、鍵導出関数として、KDF: {0, 1}*×G→{0, 1}*を用いればよい。したがって、鍵交換サーバ装置Sの認証鍵更新部１１７は、i=1, …, nについて、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0, Ri）（またはmki1←KDF(mki0, ci）)を生成する。また、通信装置Ui（i∈{1, …, n}）の認証鍵更新部２１９は、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0, Ri）（またはmki1←KDF(mki0, ci）)を生成する。
（２）Ｓ２１５及びＳ１１４における処理により共有されるTi
この場合、鍵導出関数として、KDF: {0, 1}*×Zp2→{0, 1}*を用いればよい。したがって、鍵交換サーバ装置Sの認証鍵更新部１１７は、i=1, …, nについて、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0, Ti）を生成する。また、通信装置Ui（i∈{1, …, n}）の認証鍵更新部２１９は、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0, Ti）を生成する。
（３）Ｓ１１５及びＳ２１６における処理により共有される第１共通鍵K1
この場合、鍵導出関数として、KDF: {0, 1}*×Zp→{0, 1}*を用いればよい。したがって、鍵交換サーバ装置Sの認証鍵更新部１１７は、i=1, …, nについて、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0, K1）を生成する。また、通信装置Ui（i∈{1, …, n}）の認証鍵更新部２１９は、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0, K1）を生成する。
【０１０８】
認証鍵の更新に用いるsid、Ri、ci、Ti、K1のことを認証鍵更新情報μi(i=1, …, n)という。なお、ここに挙げたsid、Ri、ci、Ti、K1のように、鍵交換サーバ装置Sと通信装置Uiの間で既に共有されている情報を認証鍵更新情報μiとすることができる。鍵交換サーバ装置Sと通信装置Uiの間で既に共有されている情報とは、鍵交換サーバ装置SによるＳ１１６、通信装置UiによるＳ２１６の処理までに鍵交換サーバ装置Sと通信装置Uiの間で共有される情報のことである。
【０１０９】
＜変形例４＞
鍵導出関数の定義に用いる鍵集合Kdについて、Kd=φ（ただし、φは空集合）としてもよい。つまり、KDF: {0, 1}*→{0, 1}*とする。この場合、Ｓ１１７及びＳ２１９における認証鍵更新処理は以下のようになる。鍵交換サーバ装置Sの認証鍵更新部１１７は、i=1, …, nについて、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0）を生成する。また、通信装置Ui（i∈{1, …, n}）の認証鍵更新部２１９は、鍵導出関数KDFにより、認証鍵mki0から新しい認証鍵mki1←KDF(mki0）を生成する。
【０１１０】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０１１１】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【０１１２】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【０１１３】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１１４】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０１１５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１１６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019125956.tif 000018
【図２】
2019125956.tif 000019
【図３】
2019125956.tif 000020
【図４】
2019125956.tif 000021
【図５】
2019125956.tif 000022
【図６】
2019125956.tif 000023
【図７】
2019125956.tif 000024