(57)【特許請求の範囲】
【請求項１】
nを2以上の整数とし、kを1以上の整数とし、||を連結演算子とし、Sを鍵配送装置とし、Ui(i=1, …, n+k)をn+k台の通信装置とし、通信装置U1, …, Unにより確立されたセッションに通信装置Un+1, …, Un+kが新たに参加する際の鍵交換方法であって、
U1を上記通信装置U1, Un, Un+1, …, Un+kから選択された1台の代表通信装置とし、
上記鍵配送装置Sの記憶部に、上記鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sが記憶されており、
上記通信装置Ui(i=1, …, n+k)の記憶部に、上記通信装置Uiの公開鍵暗号の秘密鍵skiおよび秘密ストリングsti, st'iが記憶されており、
さらに、上記通信装置U1, …, Unの記憶部に、上記通信装置U1, …, Unにより確立されたセッションで生成された情報rが記憶されており、
上記通信装置Ui(i=1, n, …, n+k)が、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてri, ki, siを生成し、Ri=griおよびci=gkihsiを計算し、(Ri, ci)を上記鍵配送装置Sへ送信し、上記通信装置Ui(i=2, …, n-1)が、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてki, siを生成し、ci=gkihsiを計算し、ciを上記鍵配送装置Sへ送信する第一鍵生成ステップと、
上記鍵配送装置Sが、ターゲット衝突困難ハッシュ関数によりc1, …, cn+kを用いてsidを生成し、i=1, 2について(sid, Ri-1)を、i=3, …, n-2についてsidを、i=n-1, nについて(sid, Ri+1)を、i=n+1, …, n+kについて(sid, Ri-1, Ri+1)を上記通信装置Uiへ送信する（ただし、R0=Rn+K ,Rn+k+1=R1とする）セッションID生成ステップと、
上記代表通信装置U1が、擬似ランダム関数により(sid, Rn+kr1)を用いてK1lを生成し、擬似ランダム関数により(sid, gr1r)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、上記通信装置U2が、擬似ランダム関数により(sid, R1r)を用いてK2lを生成し、擬似ランダム関数により(sid, gr)を用いてK2rを生成し、K2lとK2rとの排他的論理和によりT2を計算し、(k2, s2, T2)を上記鍵配送装置Sへ送信し、上記通信装置Ui (i=3, …, n-2)が、(ki, si)を上記鍵配送装置Sへ送信し、上記通信装置Un-1が、擬似ランダム関数により(sid, gr)を用いてKn-1lを生成し、擬似ランダム関数により(sid, Rnr)を用いてKn-1rを生成し、Kn-1lとKn-1rとの排他的論理和によりTn-1を計算し、(kn-1, sn-1, Tn-1)を上記鍵配送装置Sへ送信し、上記通信装置Unが、擬似ランダム関数により(sid, Rnr)を用いてKnlを生成し、擬似ランダム関数により(sid, Rn+1rn)を用いてKnrを生成し、KnlとKnrとの排他的論理和によりTnを計算し、(kn, sn, Tn)を上記鍵配送装置Sへ送信し、上記通信装置Ui(i=n+1, …, n+k)が、擬似ランダム関数により(sid, Ri-1ri)を用いてKilを生成し、擬似ランダム関数により(sid, Ri+1ri)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信する第二鍵生成ステップと、
上記鍵配送装置Sが、ねじれ擬似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、k2, …, kn+k, ksの排他的論理和によりk'を計算し、i=2, …, n+kについてT1, …, Ti-1（ただし、i=3, …, n-1についてTiを空とする）の排他的論理和によりT'iを計算し、k'を上記代表通信装置U1へ送信し、(k', T'i, T')を上記通信装置Ui(i=2, …, n+k)へ送信する第三鍵生成ステップと、
上記通信装置Ui(i=2, n, …, n+k)が、T'iとKilとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算し、上記通信装置Ui(i=3, …, n-1)が、T'iとgrとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算する第一セッション鍵生成ステップと、
上記通信装置Ui(i=1, …, n+k)が、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成する第二セッション鍵生成ステップと、
を含む鍵交換方法。
【請求項２】
請求項１に記載の鍵交換方法であって、
timeを現在時刻とし、IDを上記通信装置を表す述語変数とし、TFを上記通信装置のタイムフレームを表す述語変数とし、
上記鍵配送装置Sの記憶部に、関数暗号のマスタ秘密鍵mskと、上記通信装置U1, …, Unにより確立されたセッションで生成された共通鍵K1がさらに記憶されており、
上記鍵配送装置Sが、i=1, …, n+kについて属性をAi=(Ui, time)として関数暗号の鍵導出アルゴリズムにより上記マスタ秘密鍵mskを用いてユーザ秘密鍵uskiを生成し、公開鍵暗号の暗号化アルゴリズムにより上記通信装置Uiの公開鍵pkiを用いて上記ユーザ秘密鍵uskiを暗号化して暗号文CTiを生成するユーザ鍵送信ステップと、
上記通信装置Ui(i=1, …, n+k)が、公開鍵暗号の復号アルゴリズムにより上記秘密鍵skiを用いて上記暗号文CTiを復号して上記ユーザ秘密鍵uskiを得るユーザ鍵受信ステップと、
をさらに含み、
上記第三鍵生成ステップは、通信装置U1, …,Unにより確立されたセッションからタイムフレームが変更されていた場合は、ねじれ擬似ランダム関数により上記秘密ストリングstS, st'Sを用いて共通鍵K1を生成し、通信装置U1, …,Unにより確立されたセッションからタイムフレームが変更されていない場合は、上記鍵配送装置Sの記憶部に記憶した共通鍵K1を読出し、i=1, …, n+kについてアクセス構造をPi=(ID=Ui)∧(time∈TF)として関数暗号の暗号化アルゴリズムにより上記共通鍵K1を暗号化して暗号文CT'iを生成するものであり、
上記第二セッション鍵生成ステップは、関数暗号の復号アルゴリズムにより上記ユーザ秘密鍵uskiを用いて上記暗号文CT'iを復号して上記共通鍵K1を得、擬似ランダム関数により(sid, K1)を用いて生成した値と擬似ランダム関数により(sid, K2)を用いて生成した値との排他的論理和によりセッション鍵SKを計算するものである、
鍵交換方法。
【請求項３】
請求項２に記載の鍵交換方法であって、
上記ユーザ鍵送信ステップは、メッセージ認証コードの鍵生成アルゴリズムによりMAC鍵mkiを生成し、公開鍵暗号の暗号化アルゴリズムにより上記通信装置Uiの公開鍵pkiを用いて上記ユーザ秘密鍵uskiおよび上記MAC鍵mkiを暗号化して上記暗号文CTiを生成するものであり、
上記ユーザ鍵受信ステップは、公開鍵暗号の復号アルゴリズムにより上記秘密鍵skiを用いて上記暗号文CTiを復号して上記ユーザ秘密鍵uskiおよび上記MAC鍵mkiを得るものであり、
上記代表通信装置U1が、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mk1およびR1, c1, Rn+k, T1, T', U1, sidを用いて認証タグσ1を生成し、上記通信装置U2が、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mk2およびc2, R1, k2, s2, T2, U2, sidを用いて認証タグσ2を生成し、上記通信装置Ui(i=3, …, n-2)が、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびci, ki, si, Ui, sidを用いて認証タグσiを生成し、上記通信装置Un-1が、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkn-1およびcn-1, Rn, kn-1, sn-1, Tn-1, Un-1, sidを用いて認証タグσn-1を生成し、上記通信装置Unが、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mknおよびRn, cn, Rn+1, kn, sn, Tn, Un, sidを用いて認証タグσnを生成し、上記通信装置Ui(i=n+1, …, n+k)が、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびRi, ci, Ri-1, Ri+1, ki, si, Ti, Ui, sidを用いて認証タグσiを生成する第一認証タグ生成ステップと、
上記鍵配送装置Sが、上記代表通信装置U1から(T1, T', σ1)を、上記通信装置Ui(i=2, n-1, …, n+k)から(ki, si, Ti, σi)を、上記通信装置Ui(i=3, …, n-2)から(ki, si, σi)を受信し、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mki(i=1, …, n+k)を用いて上記認証タグσiを検証し、i=2, …, n+kについてci=gkihsiが成り立つか否かを検証する第一認証タグ検証ステップと、
上記鍵配送装置Sが、i=1についてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mk1およびR1, c1, Rn+k, T1, T', U1, sid, k', CT'1を用いて認証タグσ'1を生成し、i=2についてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mk2およびc2, R1, k2, s2, T2, U2, sid, c1, k', T'2, T', CT'2を用いて認証タグσ'2を生成し、i=3, …, n-2についてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびci, ki, si, Ui, sid, c1, k', T'i, T', CT'iを用いて認証タグσ'iを生成し、i=n-1についてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkn-1およびcn-1, Rn, kn-1, sn-1, Tn-1, Un-1, sid, c1, k', T'n-1, T', CT'n-1を用いて認証タグσ'n-1を生成し、i=nについてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mknおよびRn, cn, Rn+1, kn, sn, Tn, Un, sid, c1, k', T'n, T', CT'nを用いて認証タグσ'nを生成し、i=n+1, …, n+kについてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびRi, ci, Ri-1, Ri+1, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'iを用いて認証タグσ'iを生成する第二認証タグ生成ステップと、
上記代表通信装置U1が、上記鍵配送装置Sから(k', CT'1, σ'1)を受信し、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mk1を用いて上記認証タグσ'1を検証し、上記通信装置Ui (i=2, …, n+k) が、上記鍵配送装置Sから(c1, k', T'i, T', CT'i, σ'i)を受信し、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mkiを用いて上記認証タグσ'iを検証し、c1=gk1hs1が成り立つか否かを検証する第二認証タグ検証ステップと、
をさらに含む鍵交換方法。
【請求項４】
nを2以上の整数とし、kを1以上の整数とし、||を連結演算子とし、
鍵配送装置Sとn+k台の通信装置Ui(i=1, …, n+k)とを含む鍵交換システムであって、
U1を上記通信装置U1, Un, Un+1, …, Un+kから選択された1台の代表通信装置とし、
上記鍵配送装置Sは、
上記鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sを記憶する記憶部と、
上記通信装置Ui(i=1, n, …, n+k)から(Ri, ci)を、上記通信装置Ui(i=2, …, n-1)からciを受信し、ターゲット衝突困難ハッシュ関数によりc1, …, cn+kを用いてsidを生成し、i=1, 2について(sid, Ri-1)を、i=3, …, n-2についてsidを、i=n-1, nについて(sid, Ri+1)を、i= n+1, …, n+kについて(sid, Ri-1, Ri+1)を上記通信装置Uiへ送信する（ただし、R0=Rn+K ,Rn+k+1=R1とする）セッションID生成部と、
上記代表通信装置U1から(T1, T')を、上記通信装置Ui (i=2 ,n-1 ,…, n+k)から(ki, si, Ti)を、上記通信装置Ui (i=3, …, n-2)から(ki, si)を受信し、ねじれ擬似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、k2, …, kn+k, ksの排他的論理和によりk'を計算し、i=2, …, n+kについてT1, …, Ti-1（ただし、i=3, …, n-1についてTiを空とする）の排他的論理和によりT'iを計算し、k'を上記代表通信装置U1へ、(k', T'i, T')を上記通信装置Ui(i=2, …, n+k)へ送信する第三鍵生成部と、
を含み、
上記通信装置Ui(i=1, …, n+k)は、
上記通信装置Uiの公開鍵暗号の秘密鍵skiおよび秘密ストリングsti, st'iを記憶し、i=1, …, nについては上記通信装置U1, …, Unにより確立されたセッションで生成された情報rをさらに記憶する記憶部と、
i=1, n, …, n+kについて、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてri, ki, siを生成し、Ri=griおよびci=gkihsiを計算し、(Ri, ci)を上記鍵配送装置Sへ送信し、i=2, …, n-1について、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてki, siを生成し、ci=gkihsiを計算し、ciを上記鍵配送装置Sへ送信する第一鍵生成部と、
i=1について、上記鍵配送装置Sから(sid, Rn+k)を受信し、擬似ランダム関数により(sid, Rn+kr1)を用いてK1lを生成し、擬似ランダム関数により(sid, gr1r)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、i=2について、上記鍵配送装置Sから(sid, R1)を受信し、擬似ランダム関数により(sid, R1r)を用いてK2lを生成し、擬似ランダム関数により(sid, gr)を用いてK2rを生成し、K2lとK2rとの排他的論理和によりT2を計算し、(k2, s2, T2)を上記鍵配送装置Sへ送信し、i=3, …, n-2について、上記鍵配送装置Sからsidを受信し、(ki, si)を上記鍵配送装置Sへ送信し、i=n-1について、上記鍵配送装置Sから(sid, Rn)を受信し、擬似ランダム関数により(sid, gr)を用いてKn-1lを生成し、擬似ランダム関数により(sid, Rnr)を用いてKn-1rを生成し、Kn-1lとKn-1rとの排他的論理和によりTn-1を計算し、(kn-1, sn-1, Tn-1)を上記鍵配送装置Sへ送信し、i=nについて、上記鍵配送装置Sから(sid, Rn+1)を受信し、擬似ランダム関数により(sid, Rnr)を用いてKnlを生成し、擬似ランダム関数により(sid, Rn+1rn)を用いてKnrを生成し、KnlとKnrとの排他的論理和によりTnを計算し、(kn, sn, Tn)を上記鍵配送装置Sへ送信し、i=n+1, …, n+kについて、上記鍵配送装置Sから(sid, Ri-1, Ri+1)を受信し、擬似ランダム関数により(sid, Ri-1ri)を用いてKilを生成し、擬似ランダム関数により(sid, Ri+1ri)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信する第二鍵生成部と、
i=1については上記鍵配送装置Sからk'を受信し、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成し、i=2, n, …, n+k については上記鍵配送装置Sから (k', T'i, T')を受信し、T'iとKilとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算し、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成し、i=3, …, n-1については上記鍵配送装置Sから (k', T'i, T')を受信し、T'iとgrとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算し、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成するセッション鍵生成部と、
を含む鍵交換システム。
【請求項５】
nを2以上の整数とし、||を連結演算子とし、Sを鍵配送装置とし、Ui(i=1, …, n)をn台の通信装置とし、R={Uj1, …, Ujm}を{U1, …, Un}の部分集合とし、N={Uj1-1, Uj1+1, …, Ujm-1, Ujm+1}を{U1, …, Un}の部分集合とし、通信装置U1, …, Unにより確立されたセッションから通信装置Uj1, …, Ujm が離脱する際の鍵交換方法であって、
U1(∈N)をNから選択された1台の代表通信装置とし、
上記鍵配送装置Sの記憶部に、上記鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sが記憶されており、
上記通信装置Ui(i=1, …, n)の記憶部に、上記通信装置Uiの公開鍵暗号の秘密鍵skiおよび秘密ストリングsti, st'iと、上記通信装置U1, …, Unにより確立されたセッションで生成された情報Hil、Hirが記憶されており、
上記通信装置Ui(∈N)が、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてri, ki, siを生成し、Ri=griおよびci=gkihsiを計算し、(Ri, ci)を上記鍵配送装置Sへ送信し、上記通信装置Ui(∈({U1, …, Un}-R)-N)が、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてki, siを生成し、ci=gkihsiを計算し、ciを上記鍵配送装置Sへ送信する第一鍵生成ステップと、
上記鍵配送装置Sが、ターゲット衝突困難ハッシュ関数により{ci|iはUi∈{U1, …, Un}-Rを満たす}を用いてsidを生成し、Ui∈NかつUi+1∈Rとなるiについて(sid, Rj)を（ただし、jはUj∈Nかつj>iを満たす最小の添え字とする）、Ui∈NかつUi-1∈Rとなるiについて(sid, Rj')を（ただし、j'はUj'∈Nかつj'<iを満たす最大の添え字とする）、Ui∈({U1, …, Un}-R)-N となるiについてsidを上記通信装置Uiへ送信するセッションID生成ステップと、
上記代表通信装置U1は、Uj=U3かつUj'=Un-1が成り立つ場合、擬似ランダム関数により(sid, Rn-1r1)を用いてK1lを生成し、擬似ランダム関数により(sid, R3r1)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、Uj'=Un-1かつU2∈Nが成り立つ場合、擬似ランダム関数により(sid, Rn-1r1)を用いてK1lを生成し、擬似ランダム関数により(sid, H1r)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、Uj=U3かつUn∈Nが成り立つ場合、擬似ランダム関数により(sid, H1l)を用いてK1lを生成し、擬似ランダム関数により(sid, R3r1)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、上記通信装置Ui （iはUi∈NかつUi+1∈Rを満たす（ただし、iは1ではない））は、擬似ランダム関数により(sid, Hil)を用いてKilを生成し、擬似ランダム関数により(sid, Rj ri)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信し、上記通信装置Ui（iはUi∈NかつUi-1∈Rを満たす（ただし、iは1ではない））は、擬似ランダム関数により(sid, Rj'ri)を用いてKilを生成し、擬似ランダム関数により(sid, Hir)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信し、上記通信装置Ui（iはUi∈({U1, …, Un}-R)-Nを満たす（ただし、iは1ではない））は、擬似ランダム関数により(sid, Hil)を用いてKilを生成し、擬似ランダム関数により(sid, Hir)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信する第二鍵生成ステップと、
上記鍵配送装置Sが、ねじれ擬似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、{ki|iはUi∈({U1, …, Un}-R)- {U1}を満たす}とksの排他的論理和によりk'を計算し、Ui∈{U1, …, Un}-Rを満たすiについてT1, …, Tj,…, Ti-1（ただし、Uj∈RとなるjについてはTjを空とする）の排他的論理和によりT'iを計算し、k'を上記代表通信装置U1へ送信し、(k', T'i, T')を上記通信装置Ui(∈({U1, …, Un}-R)- {U1})へ送信する第三鍵生成ステップと、
上記通信装置Ui(∈({U1, …, Un}-R)- {U1})が、T'iとKilとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算する第一セッション鍵生成ステップと、
上記通信装置Ui(∈({U1, …, Un}-R))が、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成する第二セッション鍵生成ステップと、
を含む鍵交換方法。
【請求項６】
請求項５に記載の鍵交換方法であって、
timeを現在時刻とし、IDを上記通信装置を表す述語変数とし、TFを上記通信装置のタイムフレームを表す述語変数とし、
上記鍵配送装置Sの記憶部に、関数暗号のマスタ秘密鍵mskと、上記通信装置U1, …, Unにより確立されたセッションで生成された共通鍵K1がさらに記憶されており、
上記鍵配送装置Sが、Ui∈{U1, …, Un}-Rを満たすiについて属性をAi=(Ui, time)として関数暗号の鍵導出アルゴリズムにより上記マスタ秘密鍵mskを用いてユーザ秘密鍵uskiを生成し、公開鍵暗号の暗号化アルゴリズムにより上記通信装置Uiの公開鍵pkiを用いて上記ユーザ秘密鍵uskiを暗号化して暗号文CTiを生成するユーザ鍵送信ステップと、
上記通信装置Uiが、公開鍵暗号の復号アルゴリズムにより上記秘密鍵skiを用いて上記暗号文CTiを復号して上記ユーザ秘密鍵uskiを得るユーザ鍵受信ステップと、
をさらに含み、
上記第三鍵生成ステップは、通信装置U1, …,Unにより確立されたセッションからタイムフレームが変更されていた場合は、ねじれ擬似ランダム関数により上記秘密ストリングstS, st'Sを用いて共通鍵K1を生成し、通信装置U1, …,Unにより確立されたセッションからタイムフレームが変更されていない場合は、上記鍵配送装置Sの記憶部に記憶した共通鍵K1を読出し、Ui∈{U1, …, Un}-Rを満たすiについてアクセス構造をPi=(ID=Ui)∧(time∈TF)として関数暗号の暗号化アルゴリズムにより上記共通鍵K1を暗号化して暗号文CT'iを生成するものであり、
上記第二セッション鍵生成ステップは、関数暗号の復号アルゴリズムにより上記ユーザ秘密鍵uskiを用いて上記暗号文CT'iを復号して上記共通鍵K1を得、擬似ランダム関数により(sid, K1)を用いて生成した値と擬似ランダム関数により(sid, K2)を用いて生成した値との排他的論理和によりセッション鍵SKを計算するものである、
鍵交換方法。
【請求項７】
請求項６に記載の鍵交換方法であって、
上記ユーザ鍵送信ステップは、メッセージ認証コードの鍵生成アルゴリズムによりMAC鍵mkiを生成し、公開鍵暗号の暗号化アルゴリズムにより上記通信装置Uiの公開鍵pkiを用いて上記ユーザ秘密鍵uskiおよび上記MAC鍵mkiを暗号化して上記暗号文CTiを生成するものであり、
上記ユーザ鍵受信ステップは、公開鍵暗号の復号アルゴリズムにより上記秘密鍵skiを用いて上記暗号文CTiを復号して上記ユーザ秘密鍵uskiおよび上記MAC鍵mkiを得るものであり、
上記代表通信装置U1が、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mk1およびR1, c1, (R3, Rn-1), T1, T', U1, sidを用いて認証タグσ1を生成し、上記通信装置Ui（iはUi∈NかつUi+1∈Rを満たす）、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびRi, ci, Rj, ki, si, Ti, Ui, sidを用いて認証タグσiを生成し、上記通信装置Ui(iはUi∈NかつUi-1∈Rを満たす)が、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびRi, ci, Rj', ki, si, Ti, Ui, sidを用いて認証タグσiを生成し、上記通信装置U i(iはUi∈({U1, …, Un}-R)-Nを満たす)が、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびci, ki, si, Ti, Ui, sidを用いて認証タグσiを生成する第一認証タグ生成ステップと、
上記鍵配送装置Sが、上記代表通信装置U1から(T1, T', σ1)を、上記通信装置Ui(∈({U1, …, Un}-R)- {U1})から(ki, si, Ti, σi)を受信し、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mki(iはUi∈{U1, …, Un}-Rを満たす)を用いて上記認証タグσiを検証し、Ui∈({U1, …, Un}-R)- {U1}を満たすiについてci=gkihsiが成り立つか否かを検証する第一認証タグ検証ステップと、
上記鍵配送装置Sが、i=1についてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mk1およびR1, c1, (R3, Rn-1), T1, T', U1, sid, k', CT'1を用いて認証タグσ'1を生成し、Ui∈NかつUi+1∈R を満たすiについてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびRi, ci, Rj, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'iを用いて認証タグσ'iを生成し、Ui∈NかつUi-1∈R を満たすiについてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkiおよびRi, ci, Rj', ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'iを用いて認証タグσ'iを生成し、Ui∈({U1, …, Un}-R)-N を満たすiについてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkn-1およびci, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'iを用いて認証タグσ'n-1を生成する第二認証タグ生成ステップと、
上記代表通信装置U1が、上記鍵配送装置Sから(k', CT'1, σ'1)を受信し、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mk1を用いて上記認証タグσ'1を検証し、上記通信装置Ui (∈({U1, …, Un}-R)- {U1}) が、上記鍵配送装置Sから(c1, k', T'i, T', CT'i, σ'i)を受信し、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mkiを用いて上記認証タグσ'iを検証し、c1=gk1hs1が成り立つか否かを検証する第二認証タグ検証ステップと、
をさらに含む鍵交換方法。
【請求項８】
nを2以上の整数とし、||を連結演算子とし、
鍵配送装置Sとn台の通信装置Ui(i=1, …, n)とを含む鍵交換システムであって、
R={Uj1, …, Ujm}を{U1, …, Un}の部分集合とし、N={Uj1-1, Uj1+1, …, Ujm-1, Ujm+1}を{U1, …, Un}の部分集合とし、U1(∈N)をNから選択された1台の代表通信装置とし、
上記鍵配送装置Sは、
上記鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sを記憶する記憶部と、
上記通信装置Ui(∈N)から(Ri, ci)を、上記通信装置Ui(∈({U1, …, Un}-R)-N)からciを受信し、ターゲット衝突困難ハッシュ関数により{ci|iはUi∈{U1, …, Un}-Rを満たす}を用いてsidを生成し、Ui∈NかつUi+1∈Rとなるiについて(sid, Rj)を（ただし、jはUj∈Nかつj>iを満たす最小の添え字とする）、Ui∈NかつUi-1∈Rとなるiについて(sid, Rj')を（ただし、j'はUj'∈Nかつj'<iを満たす最大の添え字とする）、Ui∈({U1, …, Un}-R)-N となるiについてsidを上記通信装置Uiへ送信するセッションID生成部と、
上記代表通信装置U1から(T1, T')を、上記通信装置Ui (∈({U1, …, Un}-R)- {U1})から(ki, si, Ti)を受信し、ねじれ擬似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、{ki|iはUi∈({U1, …, Un}-R)- {U1}を満たす}とksの排他的論理和によりk'を計算し、Ui∈{U1, …, Un}-Rを満たすiについてT1, …, Tj,…, Ti-1（ただし、Uj∈RとなるjについてはTjを空とする）の排他的論理和によりT'iを計算し、k'を上記代表通信装置U1へ、(k', T'i, T')を上記通信装置Ui(∈({U1, …, Un}-R)- {U1})へ送信する第三鍵生成部と、
を含み、
上記通信装置Ui(∈{U1, …, Un}-R)は、
上記通信装置Uiの公開鍵暗号の秘密鍵skiおよび秘密ストリングsti, st'iと、上記通信装置U1, …, Unにより確立されたセッションで生成された情報Hil、Hirを記憶する記憶部と、
Ui∈Nを満たすiについて、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてri, ki, siを生成し、Ri=griおよびci=gkihsiを計算し、(Ri, ci)を上記鍵配送装置Sへ送信し、Ui∈({U1, …, Un}-R)-Nを満たすiについて、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてki, siを生成し、ci=gkihsiを計算し、ciを上記鍵配送装置Sへ送信する第一鍵生成部と、
i=1について、Uj=U3かつUj'=Un-1が成り立つ場合、上記鍵配送装置Sから(sid, R3, Rn-1)を受信し、擬似ランダム関数により(sid, Rn-1r1)を用いてK1lを生成し、擬似ランダム関数により(sid, R3r1)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、Uj'=Un-1かつU2∈Nが成り立つ場合、上記鍵配送装置Sから(sid, Rn-1)を受信し、擬似ランダム関数により(sid, Rn-1r1)を用いてK1lを生成し、擬似ランダム関数により(sid, H1r)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、Uj=U3かつUn∈Nが成り立つ場合、上記鍵配送装置Sから(sid, R3)を受信し、擬似ランダム関数により(sid, H1l)を用いてK1lを生成し、擬似ランダム関数により(sid, R3r1)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、上記通信装置Ui（iはUi∈NかつUi+1∈Rを満たす（ただし、iは1ではない））は、上記鍵配送装置Sから(sid, Rj)を受信し、擬似ランダム関数により(sid, Hil)を用いてKilを生成し、擬似ランダム関数により(sid, Rjri)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信し、上記通信装置Ui（iはUi∈NかつUi-1∈Rを満たす（ただし、iは1ではない））は、上記鍵配送装置Sから(sid, Rj')を受信し、擬似ランダム関数により(sid, Rj'ri)を用いてKilを生成し、擬似ランダム関数により(sid, Hir)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信し、上記通信装置Ui（iはUi∈({U1, …, Un}-R)-Nを満たす（ただし、iは1ではない））は、上記鍵配送装置Sからsidを受信し、擬似ランダム関数により(sid, Hil)を用いてKilを生成し、擬似ランダム関数により(sid, Hir)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信する第二鍵生成部と、
i=1については上記鍵配送装置Sからk'を受信し、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成し、Ui∈({U1, …, Un}-R)- {U1}を満たすiについては上記鍵配送装置Sから (k', T'i, T')を受信し、T'iとKilとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算し、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成するセッション鍵生成部と、
を含む鍵交換システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は情報セキュリティ技術の応用に関し、特に、グループを形成する複数のユーザが共通鍵を共有する鍵交換技術に関する。
【背景技術】
【０００２】
従来からグループを形成する複数のユーザが共通鍵を共有する鍵交換技術が提案されている（例えば、非特許文献１、２参照）。非特許文献１には、そのような鍵交換技術を実現する情報システムのアーキテクチャが記載されている。非特許文献２には、そのような鍵交換技術のアルゴリズムが記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Suvo Mittra, “Iolus: a framework for scalable secure multicasting”, SIGCOMM '97, pp. 277-288
【非特許文献２】“Scalable Multicast Key Distribution”、［online］、［平成28年3月4日検索］、インターネット<URL:https://tools.ietf.org/html/rfc1949>
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１、２に記載の従来技術では、予め共通鍵を共有するユーザを登録しておく必要があるため、動的なメンバ変更を許しながら複数のユーザが共通鍵を共有することはできない。また、ユーザ数をnとして、全体として鍵交換に必要な計算量はO(log n)となるため、ユーザ数の増大に従って鍵交換の計算量が増えるという問題がある。
【０００５】
この発明の目的は、このような点に鑑みて、動的なメンバ変更を許しながら複数のユーザが共通鍵を共有することができ、鍵交換に必要な計算量を低減することができる鍵交換技術を提供することである。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、この発明の鍵交換方法は、nを2以上の整数とし、kを1以上の整数とし、||を連結演算子とし、Sを鍵配送装置とし、Ui(i=1, …, n+k)をn+k台の通信装置とし、通信装置U1, …, Unにより確立されたセッションに通信装置Un+1, …, Un+kが新たに参加する際の鍵交換方法であって、U1を上記通信装置U1, Un, Un+1, …, Un+kから選択された1台の代表通信装置とし、上記鍵配送装置Sの記憶部に、上記鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sが記憶されており、上記通信装置Ui(i=1, …, n+k)の記憶部に、上記通信装置Uiの公開鍵暗号の秘密鍵skiおよび秘密ストリングsti, st'iが記憶されており、さらに、上記通信装置U1, …, Unの記憶部に、上記通信装置U1, …, Unにより確立されたセッションで生成された情報rが記憶されており、上記通信装置Ui(i=1, n, …, n+k)が、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてri, ki, siを生成し、Ri=griおよびci=gkihsiを計算し、(Ri, ci)を上記鍵配送装置Sへ送信し、上記通信装置Ui(i=2, …, n-1)が、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてki, siを生成し、ci=gkihsiを計算し、ciを上記鍵配送装置Sへ送信する第一鍵生成ステップと、上記鍵配送装置Sが、ターゲット衝突困難ハッシュ関数によりc1, …, cn+kを用いてsidを生成し、i=1, 2について(sid, Ri-1)を、i=3, …, n-2についてsidを、i=n-1, nについて(sid, Ri+1)を、i=n+1, …, n+kについて(sid, Ri-1, Ri+1)を上記通信装置Uiへ送信する（ただし、R0=Rn+K,Rn+k+1=R1とする）セッションID生成ステップと、上記代表通信装置U1が、擬似ランダム関数により(sid, Rn+kr1)を用いてK1lを生成し、擬似ランダム関数により(sid, gr1r)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、上記通信装置U2が、擬似ランダム関数により(sid, R1r)を用いてK2lを生成し、擬似ランダム関数により(sid, gr)を用いてK2rを生成し、K2lとK2rとの排他的論理和によりT2を計算し、(k2, s2, T2)を上記鍵配送装置Sへ送信し、上記通信装置Ui (i=3, …, n-2)が、(ki, si)を上記鍵配送装置Sへ送信し、上記通信装置Un-1が、擬似ランダム関数により(sid, gr)を用いてKn-1lを生成し、擬似ランダム関数により(sid, Rnr)を用いてKn-1rを生成し、Kn-1lとKn-1rとの排他的論理和によりTn-1を計算し、(kn-1, sn-1, Tn-1)を上記鍵配送装置Sへ送信し、上記通信装置Unが、擬似ランダム関数により(sid, Rnr)を用いてKnlを生成し、擬似ランダム関数により(sid, Rn+1rn)を用いてKnrを生成し、KnlとKnrとの排他的論理和によりTnを計算し、(kn, sn, Tn)を上記鍵配送装置Sへ送信し、上記通信装置Ui(i=n+1, …, n+k)が、擬似ランダム関数により(sid, Ri-1ri)を用いてKilを生成し、擬似ランダム関数により(sid, Ri+1ri)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信する第二鍵生成ステップと、上記鍵配送装置Sが、ねじれ擬似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、k2, …, kn+k, ksの排他的論理和によりk'を計算し、i=2, …, n+kについてT1, …, Ti-1（ただし、i=3, …, n-1についてTiを空とする）の排他的論理和によりT'iを計算し、k'を上記代表通信装置U1へ送信し、(k', T'i, T')を上記通信装置Ui(i=2, …, n+k)へ送信する第三鍵生成ステップと、上記通信装置Ui(i=2, n, …, n+k)が、T'iとKil���の排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算し、上記通信装置Ui(i=3, …, n-1)が、T'iとgrとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算する第一セッション鍵生成ステップと、上記通信装置Ui(i=1, …, n+k)が、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成する第二セッション鍵生成ステップと、を含む。
【０００７】
また、この発明の鍵交換方法は、nを2以上の整数とし、||を連結演算子とし、Sを鍵配送装置とし、Ui(i=1, …, n)をn台の通信装置とし、R={Uj1, …, Ujm}を{U1, …, Un}の部分集合とし、N={Uj1-1, Uj1+1, …, Ujm-1, Ujm+1}を{U1, …, Un}の部分集合とし、通信装置U1, …, Unにより確立されたセッションから通信装置Uj1, …, Ujm が離脱する際の鍵交換方法であって、U1(∈N)をNから選択された1台の代表通信装置とし、上記鍵配送装置Sの記憶部に、上記鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sが記憶されており、上記通信装置Ui(i=1, …, n)の記憶部に、上記通信装置Uiの公開鍵暗号の秘密鍵skiおよび秘密ストリングsti, st'iと、上記通信装置U1, …, Unにより確立されたセッションで生成された情報Hil、Hirが記憶されており、上記通信装置Ui(∈N)が、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてri, ki, siを生成し、Ri=griおよびci=gkihsiを計算し、(Ri, ci)を上記鍵配送装置Sへ送信し、上記通信装置Ui(∈({U1, …, Un}-R)-N)が、ねじれ擬似ランダム関数により上記秘密ストリングsti, st'iを用いてki, siを生成し、ci=gkihsiを計算し、ciを上記鍵配送装置Sへ送信する第一鍵生成ステップと、上記鍵配送装置Sが、ターゲット衝突困難ハッシュ関数により{ci|iはUi∈{U1, …, Un}-Rを満たす}を用いてsidを生成し、Ui∈NかつUi+1∈Rとなるiについて(sid, Rj)を（ただし、jはUj∈Nかつj>iを満たす最小の添え字とする）、Ui∈NかつUi-1∈Rとなるiについて(sid, Rj')を（ただし、j'はUj'∈Nかつj'<iを満たす最大の添え字とする）、Ui∈({U1, …, Un}-R)-N となるiについてsidを上記通信装置Uiへ送信するセッションID生成ステップと、上記代表通信装置U1は、Uj=U3かつUj'=Un-1が成り立つ場合、擬似ランダム関数により(sid, Rn-1r1)を用いてK1lを生成し、擬似ランダム関数により(sid, R3r1)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、Uj'=Un-1かつU2∈Nが成り立つ場合、擬似ランダム関数により(sid, Rn-1r1)を用いてK1lを生成し、擬似ランダム関数により(sid, H1r)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、Uj=U3かつUn∈Nが成り立つ場合、擬似ランダム関数により(sid, H1l)を用いてK1lを生成し、擬似ランダム関数により(sid, R3r1)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算し、(T1, T')を上記鍵配送装置Sへ送信し、上記通信装置Ui （iはUi∈NかつUi+1∈Rを満たす（ただし、iは1ではない））は、擬似ランダム関数により(sid, Hil)を用いてKilを生成し、擬似ランダム関数により(sid, Rj ri)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信し、上記通信装置Ui（iはUi∈NかつUi-1∈Rを満たす（ただし、iは1ではない））は、擬似ランダム関数により(sid, Rj'ri)を用いてKilを生成し、擬似ランダム関数により(sid, Hir)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信し、上記通信装置Ui（iはUi∈({U1, …, Un}-R)-Nを満たす（ただし、iは1ではない））は、擬似ランダム関数により(sid, Hil)を用いてKilを生成し、擬似ランダム関数により(sid, Hir)を用いてKirを生成し��KilとKirとの排他的論理和によりTiを計算し、(ki, si, Ti)を上記鍵配送装置Sへ送信する第二鍵生成ステップと、上記鍵配送装置Sが、ねじれ擬似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、{ki|iはUi∈({U1, …, Un}-R)- {U1}を満たす}とksの排他的論理和によりk'を計算し、Ui∈{U1, …, Un}-Rを満たすiについてT1, …, Tj,…, Ti-1（ただし、Uj∈RとなるjについてはTjを空とする）の排他的論理和によりT'iを計算し、k'を上記代表通信装置U1へ送信し、(k', T'i, T')を上記通信装置Ui(∈({U1, …, Un}-R)- {U1})へ送信する第三鍵生成ステップと、上記通信装置Ui(∈({U1, …, Un}-R)- {U1})が、T'iとKilとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算する第一セッション鍵生成ステップと、上記通信装置Ui(∈({U1, …, Un}-R))が、擬似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成する第二セッション鍵生成ステップと、を含む。
【発明の効果】
【０００８】
この発明によれば、動的なメンバ変更を許しながら複数のユーザが共通鍵を共有することができる。鍵交換に必要な計算量が、ユーザ数の定数回、すなわちO(1)となり、従来よりも削減されている。
【図面の簡単な説明】
【０００９】
【図１】図１は、鍵交換システムの機能構成を例示する図である。
【図２】図２（Ａ）は、鍵配送装置の機能構成を例示する図である。図２（Ｂ）は、通信装置の機能構成を例示する図である。
【図３】図３は、鍵交換方法の処理フローを例示する図である。
【図４】図４は、鍵交換方法の処理フローを例示する図である。
【図５】図５は、ユーザ追加時の鍵交換方法の処理フローを例示する図である。
【図６】図６は、ユーザ削除時の鍵交換方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１０】
実施形態の説明に先立って、この明細書における表記方法について説明する。
ある集合Setについて、Setから要素mをランダムに選ぶことを、m∈RSetと表記する。
あるアルゴリズムALGについて、入力xと乱数rに対してALGがyを出力することを、y←ALG(x;r)と表記する。なお、ALGが確定的アルゴリズムの場合は、乱数rは空である。
|・|は値・のビット長とする。
кをセキュリティパラメータとする。
【００１１】
F={Fк: Domк×FSк→Rngк}кを定義域{Domк}к、鍵空間{FSк}к、値域{Rngк}кを持つ関数族とする。このとき、もし任意の多項式時間の識別者Dに対して、関数Fкと真正ランダム関数RFк: Domк→Rngкが見分けられなければ、F={Fк}кを擬似ランダム関数族と呼ぶ。擬似ランダム関数の具体例は、例えば、下記参考文献１に記載されている。
〔参考文献１〕O.ゴールドライヒ著、「現代暗号・確率的証明・擬似乱数」、シュプリンガー・フェアラーク東京、2001年
【００１２】
H={Hк: Domк→Rngк}кを定義域{Domк}к、値域{Rngк}кを持つハッシュ関数族とする。このとき、もし任意の多項式時間の攻撃者Aに対して、x∈RDomкを与えた上でHк(x)=Hк(x')となるようなx'(≠x)を見つけられなければ、H={Hк}кをターゲット衝突困難ハッシュ関数族と呼ぶ。ターゲット衝突困難ハッシュ関数の具体例は、例えば、下記参考文献２に記載されている。
〔参考文献２〕J.A.ブーフマン著、「暗号理論入門  原書第3版」、丸善出版、2007年
【００１３】
公開鍵暗号アルゴリズムを(Gen, Enc, Dec)とする。鍵生成アルゴリズムGenはセキュリティパラメータкを入力とし、公開鍵pkと秘密鍵skを出力する。暗号化アルゴリズムEncは公開鍵pkと平文mを入力とし、暗号文CTを出力する。復号アルゴリズムDecは秘密鍵skと暗号文CTを入力とし、平文mを出力する。公開鍵暗号アルゴリズムの具体例は、例えば、上記参考文献２に記載されている。
【００１４】
メッセージ認証コードアルゴリズムを(MGen, Tag, Ver)とする。MAC鍵生成アルゴリズムMGenはセキュリティパラメータкを入力とし、MAC鍵mkを出力する。タグ生成アルゴリズムTagはMAC鍵mkと平文mを入力とし、認証タグσを出力する。検証アルゴリズムVerはMAC鍵mkと平文mと認証タグσを入力とし、認証タグσが正しければ1を、正しくなければ0を出力する。メッセージ認証コードアルゴリズムの具体例は、例えば、上記参考文献２に記載されている。
【００１５】
関数暗号アルゴリズムを(Setup, Der, FEnc, FDec)とする。セットアップアルゴリズムSetupはセキュリティパラメータкを入力とし、マスタ秘密鍵mskと公開パラメータParamsを出力する。鍵導出アルゴリズムDerは公開パラメータParamsとマスタ秘密鍵mskと属性Aを入力とし、ユーザ秘密鍵uskを出力する。暗号化アルゴリズムFEncは公開パラメータParamsとアクセス構造Pと平文mを入力とし、暗号文CTを出力する。復号アルゴリズムFDecはユーザ秘密鍵uskと暗号文CTを入力とし、属性Aがアクセス構造Pを満たすならば平文mを出力する。関数暗号アルゴリズムの具体例は、例えば、下記参考文献３に記載されている。
〔参考文献３〕D. Boneh, A. Sahai, and B. Waters, “Functional encryption: definitions and challenges”, TCC, Lecture Notes in Computer Science, vol. 6597, pp. 253-273, 2011.
【００１６】
関数tPRF: {0, 1}к×FSк×{0, 1}к×FSк→Rngкをねじれ擬似ランダム関数と呼び、擬似ランダム関数Fкを用いて、
【００１７】
【数１】
0006497747.tif 000002
【００１８】
と定義する。ただし、a, b'∈{0, 1}кであり、a', b∈FSкである。ねじれ擬似ランダム関数の具体例は、例えば、下記参考文献４に記載されている。
〔参考文献４〕Kazuki Yoneyama, “One-Round Authenticated Key Exchange with Strong Forward Secrecy in the Standard Model against Constrained Adversary”, IEICE Transactions, vol. E96-A, no. 6, pp. 1124-1138, 2013.
【００１９】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２０】
＜システム構成＞
実施形態の鍵交換システムは、図１に例示するように、鍵配送装置１およびN（≧2）台の通信装置２1, …, ２Nを含む。この実施形態では、鍵配送装置１および通信装置２1, …, ２Nはそれぞれ通信網３へ接続される。通信網３は、鍵配送装置１が通信装置２1, …, ２Nそれぞれと通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網である。この実施形態では、通信装置２1, …, ２N同士は通信できなくともよい。通信網３は安全が確保された通信路である必要はなく、例えばインターネットなどを用いることができる。
【００２１】
鍵配送装置１は、図２（Ａ）に例示するように、記憶部１００、セットアップ部１０１、公開鍵生成部１０２、秘密ストリング生成部１０３、ユーザ鍵送信部１１１、セッション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の生成元とする。H: {0, 1}*→{0, 1}кをターゲット衝突困難ハッシュ関数とする。tPRF: {0, 1}к×FSк×{0, 1}к×FSк→Zp、tPRF': {0, 1}к×FSк×{0, 1}к×FSк→FSкをねじれ擬似ランダム関数とする。F: {0, 1}к×G→Zp2、F': {0, 1}к×Zp→FSк、F": {0, 1}к×FSк→{0, 1}кを擬似ランダム関数とする。
【００２６】
ステップＳ１０１において、鍵配送装置Sのセットアップ部１０１は、関数暗号のセットアップアルゴリズムSetupにより公開パラメータParamsおよびマスタ秘密鍵mskを生成する。セットアップ部１０１は、公開パラメータParamsを通信装置U1, …, UNそれぞれへ送信する。マスタ秘密鍵mskは記憶部１００へ記憶される。
【００２７】
ステップＳ１０２において、鍵配送装置Sの公開鍵生成部１０２は、公開鍵暗号の鍵生成アルゴリズムGenにより、鍵配送装置Sの公開鍵pkSおよび秘密鍵skSのペアを生成する。鍵配送装置Sの公開鍵pkSは、例えば公開鍵基盤等を用いて公開される。鍵配送装置Sの秘密鍵skSは記憶部１００へ記憶される。
【００２８】
ステップＳ２０２において、通信装置Uiの公開鍵生成部２０２は、公開鍵暗号の鍵生成アルゴリズムGenにより、通信装置Uiの公開鍵pkiおよび秘密鍵skiのペアを生成する。通信装置Uiの公開鍵pkiは、例えば公開鍵基盤等を用いて公開される。通信装置Uiの秘密鍵skiは記憶部２００へ記憶される。
【００２９】
ステップＳ１０３において、鍵配送装置Sの秘密ストリング生成部１０３は、ねじれ擬似ランダム関数で用いる秘密ストリング(stS, st'S)をstS∈RFSк、st'S∈{0, 1}кとして生成する。秘密ストリング(stS, st'S)は記憶部１００へ記憶される。
【００３０】
ステップＳ２０３において、通信装置Uiの秘密ストリング生成部２０３は、ねじれ擬似ランダム関数で用いる秘密ストリング(sti, st'i)をsti∈RFSк、st'i∈{0, 1}кとして生成する。秘密ストリング(sti, st'i)は記憶部２００へ記憶される。
【００３１】
ステップＳ１０４において、鍵配送装置Sは、各通信装置U1, …, UNの公開鍵pk1, …, pkNを例えば公開鍵基盤等から取得し、記憶部１００へ記憶する。
【００３２】
ステップＳ２０４において、通信装置Uiは、鍵配送装置Sの公開鍵pkSを例えば公開鍵基盤等から取得し、記憶部２００へ記憶する。また、鍵配送装置Sから受信した公開パラメータParamsを記憶部２００へ記憶する。
【００３３】
＜セッション鍵配送＞
図４を参照して、実施形態の鍵交換方法におけるセッション鍵配送の処理手続きを説明する。
【００３４】
以下では、N台の通信装置２1, …, ２Nのうち任意のn（≦N）台の通信装置Ui（i∈{1, …, n}）がセッション鍵SKの共有を行うものとする。S, Uiを各アルゴリズムの入力とする場合、各装置を一意に特定する識別子を表すものとする。
【００３５】
ステップＳ１１１において、鍵配送装置Sのユーザ鍵送信部１１１は、通信装置Uiがセッションを開始したときに、そのセッションが通信装置UiのタイムフレームTFにおける最初のセッションだった場合、現在時刻をtimeとし、属性をAi=(Ui, time)として、関数暗号の鍵導出アルゴリズムDerにより、通信装置Uiのユーザ秘密鍵uski←Der(Params, msk, Ai)を生成する。また、メッセージ認証コードの鍵生成アルゴリズムMGenにより、通信装置UiのMAC鍵mki←MGenを生成する。そして、公開鍵暗号の暗号化アルゴリズムEncにより、通信装置Uiの公開鍵pkiを用いてユーザ秘密鍵uskiおよびMAC鍵mkiを暗号化し、暗号文CTi←Encpki(uski, mki)を生成する。ユーザ鍵送信部１１１は、暗号文CTiを通信装置Uiへそれぞれ送信する。
【００３６】
ステップＳ２１１において、通信装置Uiのユーザ鍵受信部２１１は、公開鍵暗号の復号アルゴリズムDecにより、通信装置Uiの秘密鍵skiを用いて鍵配送装置Sから受信した暗号文CTiを復号し、ユーザ秘密鍵およびMAC鍵(uski, mki)←Decski(CTi)を得る。ユーザ鍵受信部２１１は、ユーザ秘密鍵uskiおよびMAC鍵mkiを記憶部２００へ記憶する。
【００３７】
ステップＳ２１２において、通信装置Uiの擬似ランダム関数部２１２は、~ri∈R{0, 1}к, ~r'i∈RFSк, ~ki∈R{0, 1}к, ~k'i∈RFSк, ~si∈R{0, 1}к, ~s'i∈RFSкを生成し、ねじれ擬似ランダム関数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=gri, ci=gkihsiを計算する。そして、擬似ランダム関数部２１２は、(Ri, ci)を鍵配送装置Sへ送信する。
【００３８】
ステップＳ１１２において、鍵配送装置Sは、通信装置Uiから(Ri, ci)を受信する。このとき、すべての通信装置U1, …, Unから(R1, c1), …, (Rn, cn)を受信するまで待機する。
【００３９】
ステップＳ１１３において、鍵配送装置SのセッションID生成部１１３は、ターゲット衝突困難ハッシュ関数Hにより、通信装置U1, …, Unから受信したc1, …, cnを用いて、sid=H(c1, …, cn)を生成する。また、n台の通信装置U1, …, Unから1台の通信装置を代表者として選択する。代表者の選択方法は任意であり、例えば、予め定めておいた優先順位が最も高い通信装置を選択してもよいし、直近でセッションを開始した通信装置を選択してもよい。ここでは、通信装置U1が選択されたものとし、U1を代表通信装置と呼ぶ。また、代表通信装置U1以外のn-1台の通信装置Uj（j∈{2, …, n}）を一般通信装置と呼ぶ。セッションID生成部１１３は、次式のようにα, βを計算し、(sid, Rα, Rβ)を通信装置Uiへそれぞれ送信する。
【００４０】
【数２】
0006497747.tif 000003
【００４１】
ステップＳ２１３において、通信装置Uiは、鍵配送装置Sから(sid, Rα, Rβ)をそれぞれ受信する。通信装置Uiは、(sid, Rα, Rβ)を受け取り次第、以降の処理を実行する。i=2, …, nの場合、すなわち通信装置Uiが通信装置Uj（i=j）であれば、ステップＳ２１４jへ処理を進める。i=1の場合、すなわち通信装置Uiが代表通信装置U1であれば、ステップＳ２１４1へ処理を進める。
【００４２】
ステップＳ２１４jにおいて、一般通信装置Ujの第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rαrj)を用いてKjlを生成し、擬似ランダム関数Fにより(sid, Rβrj)を用いてKjrを生成し、KjlとKjrとの排他的論理和によりTjを計算する。
【００４３】
【数３】
0006497747.tif 000004
【００４４】
ステップＳ２１５jにおいて、一般通信装置Ujの認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mkjを用いて、認証タグσj=Tagmkj(Rj, cj, Rα, Rβ, kj, sj, Tj, Uj, sid)を生成する。認証タグ生成部２１５は、(kj, sj, Tj, σj)を鍵配送装置Sへ送信する。
【００４５】
ステップＳ２１４1において、代表通信装置U1の第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rnr1)を用いてK1lを生成し、K1lとk1||s1との排他的論理和によりT1を計算する。ただし、||は連結演算子である。
【００４６】
【数４】
0006497747.tif 000005
【００４７】
ステップＳ２１５1において、代表通信装置U1の認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mk1を用いて、認証タグσ1=Tagmk1(R1, c1, Rn, R2, T1, U1, sid)を生成する。認証タグ生成部２１５は、(T1, σ1)を鍵配送装置Sへ送信する。
【００４８】
ステップＳ１１４jにおいて、鍵配送装置Sの認証タグ検証部１１４は、j=2, …, nについて、一般通信装置Ujから(kj, sj, Tj, σj)を受信し、メッセージ認証コードの検証アルゴリズムVerにより、一般通信装置UjのMAC鍵mkjを用いて、Vermkj(Rj, cj, Rα, Rβ, kj, sj, Tj, Uj, sid, σj)を検証する。認証タグσjが正当でなければ一般通信装置Ujのセッションを終了する。また、j=2, …, nについて、cj=gkjhsjが成り立つか否かを検証する。成り立たなければ一般通信装置Ujのセッションを終了する。
【００４９】
ステップＳ１１４1において、鍵配送装置Sの認証タグ検証部１１４は、代表通信装置U1から(T1, σ1)を受信し、メッセージ認証コードの検証アルゴリズムVerにより、代表通信装置U1のMAC鍵mk1を用いて、Vermk1(R1, c1, Rn, R2, T1, U1, sid, σ1)を検証する。認証タグσ1が正当でなければ代表通信装置U1のセッションを終了する。
【００５０】
ステップＳ１１５ａにおいて、鍵配送装置Sの第三鍵生成部１１５は、~kS∈R{0, 1}к, ~k'S∈RFSк, ~K1∈R{0, 1}к, ~K'1∈RFSкを生成し、ねじれ擬似ランダム関数tPRFにより、kS=tPRF(~kS, ~k'S, stS, st'S), K1=tPRF(~K1, ~K'1, stS, st'S)を計算する。また、次式により、k'を計算する。
【００５１】
【数５】
0006497747.tif 000006
【００５２】
ステップＳ１１５ｂにおいて、鍵配送装置Sの第三鍵生成部１１５は、j=2, …, nについて、次式により、T'jを計算する。
【００５３】
【数６】
0006497747.tif 000007
【００５４】
ステップＳ１１５ｃにおいて、鍵配送装置Sの第三鍵生成部１１５は、i=1, …, nについて、アクセス構造Pi=(ID=Ui)∧(time∈TF)として、関数暗号の暗号化アルゴリズムFEncにより共通鍵K1を暗号化して、暗号文CT'i=FEnc(Params, Pi, K1)を生成する。ここで、IDは通信装置を表す述語変数であり、TFは通信装置のタイムフレームを表す述語変数である。
【００５５】
ステップＳ１１６ｉにおいて、鍵配送装置Sの認証タグ生成部１１６は、j=2, …, nについて、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置UjのMAC鍵mkjを用いて認証タグσ'j=Tagmkj(Rj, cj, Rα, Rβ, kj, sj, Tj, Uj, sid, c1, k', T'j, T1, CT'j)を生成する。認証タグ生成部１１６は、(c1, k', T'j, T1, CT'j, σ'j)を一般通信装置Ujへ送信する。
【００５６】
ステップＳ１１６1において、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、代表通信装置U1のMAC鍵mk1を用いて、認証タグσ'1=Tagmk1(R1, c1, Rn, R2, T1, U1, sid, k', CT'1)を生成する。認証タグ生成部１１６は、(k', CT'1, σ'1)を代表通信装置U1へ送信する。
【００５７】
ステップＳ２１６jにおいて、一般通信装置Ujの認証タグ検証部２１６は、鍵配送装置Sから(c1, k', T'j, T1, CT'j, σ'j)を受信し、メッセージ認証コードの検証アルゴリズムVerにより、一般通信装置UjのMAC鍵mkjを用いて、Vermkj(Rj, cj, Rα, Rβ, kj, sj, Tj, Uj, sid, c1, k', T'j, T1, CT'j, σ'j)を検証する。認証タグσ'jが正当でなければ一般通信装置Ujのセッションを終了する。また、次式のように、T'jとKjrとの排他的論理和によりKjlを計算し、T1とKjlとの排他的論理和によりk1||s1を計算する。
【００５８】
【数７】
0006497747.tif 000008
【００５９】
そして、c1=gk1hs1が成り立つか否かを検証する。成り立たなければ一般通信装置Ujのセッションを終了する。
【００６０】
ステップＳ２１６1において、代表通信装置U1の認証タグ検証部２１６は、鍵配送装置Sから(k', CT'1, σ'1)を受信し、メッセージ認証コードの検証アルゴリズムVerにより、代表通信装置U1のMAC鍵mk1を用いて、Vermk1(R1, c1, Rn, R2, T1, U1, sid, k', CT'1, σ'1)を検証する。認証タグσ'1が正当でなければ代表通信装置U1のセッションを終了する。
【００６１】
ステップＳ２１７において、通信装置Uiのセッション鍵生成部２１７は、関数暗号の復号アルゴリズムFDecにより、通信装置Uiのユーザ秘密鍵uskiを用いて、共通鍵K1←FDecuski(CT'i, Pi)を復号する。また、次式のように、擬似ランダム関数F'により共通鍵K2を計算する。
【００６２】
【数８】
0006497747.tif 000009
【００６３】
そして、次式のように、擬似ランダム関数F"によりセッション鍵SKを計算する。
【００６４】
【数９】
0006497747.tif 000010
【００６５】
上記のように構成することにより、この発明の鍵交換技術によれば、従来のように事前に鍵交換を行うユーザの情報を登録しておく必要がなく、動的なメンバ変更を許しながら複数のユーザが共通鍵を共有することができる。また、従来は鍵交換に必要な全体の計算量がユーザ数をnとしてO(log n)となるが、この発明によればユーザ数の定数回、すなわちO(1)となるため、従来よりも少ない計算量で鍵交換ができる。
【００６６】
以下では、ユーザ追加時及びユーザ削除時の鍵交換方法の処理手続きについて説明する。通信装置Ui（i∈{1, …, n}）でセッション鍵SKの共有が済んでいるものとする。鍵交換処理終了時（Ｓ２１７の後）に、ユーザ追加・ユーザ削除のために用いる秘密情報を各通信装置Uiは記憶部２００に記憶する。代表通信装置U1は、次式で計算される秘密情報H1l、H1r、rを記憶部２００に記憶する。
【００６７】
【数１０】
0006497747.tif 000011
【００６８】
ここで、F''': {0, 1}к×FSк→Zpを擬似ランダム関数とする。
【００６９】
一般通信装置Ui（i∈{2, …, n}）は、次式で計算される秘密情報Hil、Hir、rを記憶部２００に記憶する。
【００７０】
【数１１】
0006497747.tif 000012
【００７１】
＜ユーザ追加＞
通信装置U1, …, Unにより確立されたセッションに通信装置Un+1, …, Un+kが新たに参加するものとする（ｋは１以上の整数、ｎ＋ｋはＮ以下の整数）。以下、i∈{1, …, n+k}とする。
【００７２】
ステップＳ３１１において、鍵配送装置Sのユーザ鍵送信部１１１は、通信装置Ui(i=1, …, n+k)がセッションを開始したときに、そのセッションが通信装置UiのタイムフレームTF'における最初のセッションだった場合、現在時刻をtimeとし、属性をAi=(Ui, time)として、関数暗号の鍵導出アルゴリズムDerにより、通信装置Uiのユーザ秘密鍵uski←Der(Params, msk, Ai)を生成する。また、メッセージ認証コードの鍵生成アルゴリズムMGenにより、通信装置UiのMAC鍵mki←MGenを生成する。そして、公開鍵暗号の暗号化アルゴリズムEncにより、通信装置Uiの公開鍵pkiを用いてユーザ秘密鍵uskiおよびMAC鍵mkiを暗号化し、暗号文CTi←Encpki(uski, mki)を生成する。ユーザ鍵送信部１１１は、暗号文CTiを通信装置Uiへそれぞれ送信する。
【００７３】
また、通信装置U1, …,Unにより確立されたセッションからタイムフレームが変更されていた場合、つまり、TF'とTFが等しくない場合、鍵配送装置Sは、~K1∈R{0, 1}к, ~K'1∈RFSкを生成し、ねじれ擬似ランダム関数tPRF'により、K1=tPRF'(~K1, ~K'1, stS, st'S)を計算する。なお、K1の計算は、後述するステップＳ３１５ａにおいて鍵配送装置Sの第三鍵生成部１１５が行うのでよい。
【００７４】
ステップＳ４１１において、通信装置Uiのユーザ鍵受信部２１１は、公開鍵暗号の復号アルゴリズムDecにより、通信装置Uiの秘密鍵skiを用いて鍵配送装置Sから受信した暗号文CTiを復号し、ユーザ秘密鍵およびMAC鍵(uski, mki)←Decski(CTi)を得る。ユーザ鍵受信部２１１は、ユーザ秘密鍵uskiおよびMAC鍵mkiを記憶部２００へ記憶する。
【００７５】
ステップＳ４１２において、i∈{1}∪[n, n+k]の場合、通信装置Uiの擬似ランダム関数部２１２は、~ri∈R{0, 1}к, ~r'i∈RFSк, ~ki∈R{0, 1}к, ~k'i∈RFSк, ~si∈R{0, 1}к, ~s'i∈RFSкを生成し、ねじれ擬似ランダム関数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=gri, ci=gkihsiを計算する。そして、擬似ランダム関数部２１２は、(Ri, ci)を鍵配送装置Sへ送信する。
【００７６】
i∈[2, n-1]の場合、通信装置Uiの擬似ランダム関数部２１２は、~ki∈R{0, 1}к, ~k'i∈RFSк, ~si∈R{0, 1}к, ~s'i∈RFSкを生成し、ねじれ擬似ランダム関数tPRFにより、ki=tPRF(~ki, ~k'i, sti, st'i), si=tPRF(~si, ~s'i, sti, st'i)を計算する。また、ci=gkihsiを計算する。そして、擬似ランダム関数部２１２は、ciを鍵配送装置Sへ送信する。
【００７７】
ステップＳ３１２において、鍵配送装置Sは、通信装置Uiから(Ri, ci)またはciを受信する。このとき、すべての通信装置U1, …, Un+kから(R1, c1), c2,…, cn-1, (Rn, cn) ,…, (Rn+k, cn+k)を受信するまで待機する。
【００７８】
ステップＳ３１３において、鍵配送装置SのセッションID生成部１１３は、ターゲット衝突困難ハッシュ関数Hにより、通信装置U1, …, Un+kから受信したc1, …, cn+kを用いて、sid=H(c1, …, cn+k)を生成する。また、k+2台の通信装置U1, Un , Un+1 ,…, Un+kから1台の通信装置を代表者として選択する。ここでは、通信装置U1が選択されたものとし、U1を代表通信装置と呼ぶ。また、代表通信装置U1以外のn+k-1台の通信装置Ui（i∈{2, …, n+k}）を一般通信装置と呼ぶ。セッションID生成部１１３は、i∈[n+1, n+k]の場合、(sid, Ri-1, Ri+1)を通信装置Uiへそれぞれ送信する（ただし、Rn+k+1=R1とする）。また、i∈[1, 2]の場合、(sid, Ri-1)を通信装置Uiへそれぞれ送信する（ただし、R0=Rn+Kとする）。i∈[3, n-2]の場合、sidを通信装置Uiへそれぞれ送信する。i∈[n-1, n]の場合、(sid, Ri+1)を通信装置Uiへそれぞれ送信する。また、鍵配送装置Sは、U1には代表者であることを通知しておく。
【００７９】
ステップＳ４１３において、通信装置Uiは、鍵配送装置Sから(sid, Ri-1, Ri+1)、(sid, Ri-1)、sid、(sid, Ri+1)のいずれかをそれぞれ受信する。通信装置Uiは、(sid, Ri-1, Ri+1)、(sid, Ri-1)、sid、(sid, Ri+1)のいずれかを受け取り次第、以降の処理（具体的には、ステップＳ４１４とステップＳ４１５）を実行する。この処理は、i=1の場合、i=2の場合、i∈[3, n-2]の場合、i=n-1の場合、i=nの場合、i∈[n+1, n+k]の場合の６つに場合分けして実行される。ただし、i∈[3, n-2]の場合、ステップＳ４１４ではなにも処理しない。つまり、通信装置Uiは、sidを受け取り次第、ステップＳ４１５の処理を実行する。
【００８０】
i=1の場合、ステップＳ４１４において、代表通信装置U1の第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rn+kr1)を用いてK1lを生成し、擬似ランダム関数Fにより(sid, gr1r)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算する。ただし、||は連結演算子である。
【００８１】
【数１２】
0006497747.tif 000013
【００８２】
ステップＳ４１５において、代表通信装置U1の認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mk1を用いて、認証タグσ1=Tagmk1(R1, c1, Rn+k, T1, T', U1, sid)を生成する。認証タグ生成部２１５は、(T1, T', σ1)を鍵配送装置Sへ送信する。
【００８３】
i=2の場合、ステップＳ４１４において、通信装置U2の第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, R1r)を用いてK2lを生成し、擬似ランダム関数Fにより(sid, gr)を用いてK2rを生成し、K2lとK2rとの排他的論理和によりT2を計算する。
【００８４】
【数１３】
0006497747.tif 000014
【００８５】
ステップＳ４１５において、通信装置U2の認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mk2を用いて、認証タグσ2=Tagmk2(c2, R1, k2, s2, T2, U2, sid)を生成する。認証タグ生成部２１５は、(k2, s2, T2, σ2)を鍵配送装置Sへ送信する。
【００８６】
i∈[3, n-2]の場合、ステップＳ４１５において、通信装置Uiの認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mkiを用いて、認証タグσi=Tagmki(ci, ki, si, Ui, sid)を生成する。認証タグ生成部２１５は、(ki, si, σi)を鍵配送装置Sへ送信する。
【００８７】
i=n-1の場合、ステップＳ４１４において、通信装置Un-1の第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, gr)を用いてKn-1lを生成し、擬似ランダム関数Fにより(sid, Rnr)を用いてKn-1rを生成し、Kn-1lとKn-1rとの排他的論理和によりTn-1を計算する。
【００８８】
【数１４】
0006497747.tif 000015
【００８９】
ステップＳ４１５において、通信装置Un-1の認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mkn-1を用いて、認証タグσn-1=Tagmkn-1(cn-1, Rn, kn-1, sn-1, Tn-1, Un-1, sid)を生成する。認証タグ生成部２１５は、(kn-1, sn-1, Tn-1, σn-1)を鍵配送装置Sへ送信する。
【００９０】
i=nの場合、ステップＳ４１４において、通信装置Unの第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rnr)を用いてKnlを生成し、擬似ランダム関数Fにより(sid, Rn+1rn)を用いてKnrを生成し、KnlとKnrとの排他的論理和によりTnを計算する。
【００９１】
【数１５】
0006497747.tif 000016
【００９２】
ステップＳ４１５において、通信装置Unの認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mknを用いて、認証タグσn=Tagmkn(Rn, cn, Rn+1, kn, sn, Tn, Un, sid)を生成する。認証タグ生成部２１５は、(kn, sn, Tn, σn)を鍵配送装置Sへ送信する。
【００９３】
i∈[n+1, n+k]の場合、ステップＳ４１４において、通信装置Uiの第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Ri-1ri)を用いてKilを生成し、擬似ランダム関数Fにより(sid, Ri+1ri)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算する。
【００９４】
【数１６】
0006497747.tif 000017
【００９５】
ステップＳ４１５において、通信装置Uiの認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mkiを用いて、認証タグσi=Tagmki(Ri, ci, Ri-1, Ri+1, ki, si, Ti, Ui, sid)を生成する。認証タグ生成部２１５は、(ki, si, Ti, σi)を鍵配送装置Sへ送信する。
【００９６】
ステップＳ３１４において、鍵配送装置Sの認証タグ検証部１１４は、代表通信装置U1から(T1, T', σ1)を受信し、i=2, n-1, …, n+kについて、一般通信装置Uiから(ki, si, Ti, σi)を受信し、i=3, …, n-2について、一般通信装置Uiから(ki, si, σi)を受信し、メッセージ認証コードの検証アルゴリズムVerにより検証する。認証タグσi (i=1, …, n+k) が正当でなければ通信装置Uiのセッションを終了する。また、i=2, …, n+kについて、ci=gkihsiが成り立つか否かを検証する。成り立たなければ一般通信装置Uiのセッションを終了する。
【００９７】
ステップＳ３１５ａにおいて、鍵配送装置Sの第三鍵生成部１１５は、~kS∈R{0, 1}к, ~k'S∈RFSкを生成し、ねじれ擬似ランダム関数tPRFにより、kS=tPRF(~kS, ~k'S, stS, st'S)を計算する。また、次式により、k'を計算する。
【００９８】
【数１７】
0006497747.tif 000018
【００９９】
ステップＳ３１５ｂにおいて、鍵配送装置Sの第三鍵生成部１１５は、i=2, …, n+kについて、次式により、T'iを計算する。
【０１００】
【数１８】
0006497747.tif 000019
【０１０１】
ただし、i=3, …, n-1について、Tiを空とする。したがって、T3'=…=Tn-1'となる。
【０１０２】
ステップＳ３１５ｃにおいて、鍵配送装置Sの第三鍵生成部１１５は、i=1, …, n+kについて、アクセス構造Pi=(ID=Ui)∧(time∈TF)として、関数暗号の暗号化アルゴリズムFEncにより共通鍵K1を暗号化して、暗号文CT'i=FEnc(Params, Pi, K1)を生成する。ここで、IDは通信装置を表す述語変数であり、TFは通信装置のタイムフレームを表す述語変数である。
【０１０３】
ステップＳ３１６において、鍵配送装置Sは認証タグを生成し、通信装置Uiに送信する。この処理は、i=1の場合、i=2の場合、i∈[3, n-2]の場合、i=n-1の場合、i=nの場合、i∈[n+1, n+k]の場合の６つに場合分けして実行される。
【０１０４】
i=1の場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、代表通信装置U1のMAC鍵mk1を用いて、認証タグσ'1=Tagmk1(R1, c1, Rn+k, T1, T', U1, sid, k', CT'1)を生成する。認証タグ生成部１１６は、(k', CT'1, σ'1)を代表通信装置U1へ送信する。
【０１０５】
i=2の場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置U2のMAC鍵mk2を用いて認証タグσ'2=Tagmk2(c2, R1, k2, s2, T2, U2, sid, c1, k', T'2, T', CT'2)を生成する。認証タグ生成部１１６は、(c1, k', T'2, T', CT'2, σ'2)を一般通信装置U2へ送信する。
【０１０６】
i∈[3, n-2]の場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置UiのMAC鍵mkiを用いて認証タグσ'i= Tagmki(ci, ki, si, Ui, sid, c1, k', T'i, T', CT'i)を生成する。認証タグ生成部１１６は、(c1, k', T'i, T', CT'i, σ'i)を一般通信装置Uiへ送信する。
【０１０７】
i=n-1の場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置Un-1のMAC鍵mkn-1を用いて認証タグσ'n-1= Tagmkn-1(cn-1, Rn, kn-1, sn-1, Tn-1, Un-1, sid, c1, k', T'n-1, T', CT'n-1)を生成する。認証タグ生成部１１６は、(c1, k', T'n-1, T', CT'n-1, σ'n-1)を一般通信装置Un-1へ送信する。
【０１０８】
i=nの場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置UnのMAC鍵mknを用いて認証タグσ'n=Tagmkn(Rn, cn, Rn+1, kn, sn, Tn, Un, sid, c1, k', T'n, T', CT'n)を生成する。認証タグ生成部１１６は、(c1, k', T'n, T', CT'n, σ'n)を一般通信装置Unへ送信する。
【０１０９】
i∈[n+1, n+k]の場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置UiのMAC鍵mkiを用いて認証タグσ'i= Tagmki(Ri, ci, Ri-1, Ri+1, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'i)を生成する。認証タグ生成部１１６は、(c1, k', T'i, T', CT'i, σ'i)を一般通信装置Uiへ送信する。
【０１１０】
ステップＳ４１６において、i∈[2, n+k]の場合、一般通信装置Uiの認証タグ検証部２１６は、鍵配送装置Sから(c1, k', T'i, T', CT'i, σ'i)を受信し、メッセージ認証コードの検証アルゴリズムVerにより、検証する。認証タグσ'iが正当でなければ一般通信装置Uiのセッションを終了する。また、i=2, n, …, n+kについては、T'iとKilとの排他的論理和によりK1lを計算し、i=3, …, n-1については、T'iとgrとの排他的論理和によりK1lを計算する。
【０１１１】
【数１９】
0006497747.tif 000020
【０１１２】
さらに、T'とK1lとの排他的論理和によりk1||s1を計算する。
【０１１３】
【数２０】
0006497747.tif 000021
【０１１４】
そして、c1=gk1hs1が成り立つか否かを検証する。成り立たなければ一般通信装置Uiのセッションを終了する。
【０１１５】
i=1の場合、代表通信装置U1の認証タグ検証部２１６は、鍵配送装置Sから(k', CT'1, σ'1)を受信し、メッセージ認証コードの検証アルゴリズムVerにより、検証する。認証タグσ'1が正当でなければ代表通信装置U1のセッションを終了する。
【０１１６】
ステップＳ４１７において、通信装置Uiのセッション鍵生成部２１７は、関数暗号の復号アルゴリズムFDecにより、通信装置Uiのユーザ秘密鍵uskiを用いて、共通鍵K1←FDecuski(CT'i, Pi)を復号する。また、次式のように、擬似ランダム関数F'により共通鍵K2を計算する。
【０１１７】
【数２１】
0006497747.tif 000022
【０１１８】
そして、次式のように、擬似ランダム関数F"によりセッション鍵SKを計算する。
【０１１９】
【数２２】
0006497747.tif 000023
【０１２０】
最後に、ユーザ追加・ユーザ削除のために用いる秘密情報を通信装置Ui(i=1, …, n)は更新する。また、通信装置Ui(i=n+1, …, n+k) は新たに記憶部２００に記憶する。代表通信装置U1は、次式で計算される秘密情報H1l、rで記憶部２００に記憶しているものを更新する。
【０１２１】
【数２３】
0006497747.tif 000024
【０１２２】
通信装置Ui(i=2, …, n-1)は、次式で計算される秘密情報rで記憶部２００に記憶しているものを更新する。
【０１２３】
【数２４】
0006497747.tif 000025
【０１２４】
通信装置Unは、次式で計算される秘密情報Hnr、rで記憶部２００に記憶しているものを更新する。
【０１２５】
【数２５】
0006497747.tif 000026
【０１２６】
通信装置Ui(i=n+1, …, n+k) は、次式で計算される秘密情報Hil、Hir、rを記憶部２００に記憶する。
【０１２７】
【数２６】
0006497747.tif 000027
【０１２８】
上記のように構成することにより、この発明の鍵交換技術によれば、従来のように事前に鍵交換を行うユーザの情報を登録しておく必要がなく、ユーザ追加時にも効率的に共通鍵を共有することができる。具体的には、鍵交換に必要な全体の計算量はユーザ数の定数回、すなわちO(1)となる。
【０１２９】
＜ユーザ削除＞
通信装置U1, …, Unにより確立されたセッションから通信装置Uj1, …, Ujm が離脱するものとする。以下、R={Uj1, …, Ujm}とする。また、N={Uj1-1, Uj1+1, …, Ujm-1, Ujm+1}とする。したがって、R、Nはいずれも{U1, …, Un}の部分集合となる。
【０１３０】
なお、U1∈Nとしても一般性を失わない。そこで、U1∈Nを仮定する。
【０１３１】
ステップＳ５１１において、鍵配送装置Sのユーザ鍵送信部１１１は、通信装置Ui(i∈{1, …, n}-R)がセッションを開始したときに、そのセッションが通信装置UiのタイムフレームTF'における最初のセッションだった場合、現在時刻をtimeとし、属性をAi=(Ui, time)として、関数暗号の鍵導出アルゴリズムDerにより、通信装置Uiのユーザ秘密鍵uski←Der(Params, msk, Ai)を生成する。また、メッセージ認証コードの鍵生成アルゴリズムMGenにより、通信装置UiのMAC鍵mki←MGenを生成する。そして、公開鍵暗号の暗号化アルゴリズムEncにより、通信装置Uiの公開鍵pkiを用いてユーザ秘密鍵uskiおよびMAC鍵mkiを暗号化し、暗号文CTi←Encpki(uski, mki)を生成する。ユーザ鍵送信部１１１は、暗号文CTiを通信装置Uiへそれぞれ送信する。
【０１３２】
また、通信装置U1, …, Unにより確立されたセッションからタイムフレームが変更されていた場合、つまり、TF'とTFが等しくない場合、鍵配送装置Sは、~K1∈R{0, 1}к, ~K'1∈RFSкを生成し、ねじれ擬似ランダム関数tPRF'により、K1=tPRF'(~K1, ~K'1, stS, st'S)を計算する。なお、K1の計算は、後述するステップＳ５１５ａにおいて鍵配送装置Sの第三鍵生成部１１５が行うのでよい。
【０１３３】
ステップＳ６１１において、通信装置Uiのユーザ鍵受信部２１１は、公開鍵暗号の復号アルゴリズムDecにより、通信装置Uiの秘密鍵skiを用いて鍵配送装置Sから受信した暗号文CTiを復号し、ユーザ秘密鍵およびMAC鍵(uski, mki)←Decski(CTi)を得る。ユーザ鍵受信部２１１は、ユーザ秘密鍵uskiおよびMAC鍵mkiを記憶部２００へ記憶する。
【０１３４】
ステップＳ６１２において、Ui∈Nの場合、通信装置Uiの擬似ランダム関数部２１２は、~ri∈R{0, 1}к, ~r'i∈RFSк, ~ki∈R{0, 1}к, ~k'i∈RFSк, ~si∈R{0, 1}к, ~s'i∈RFSкを生成し、ねじれ擬似ランダム関数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=gri, ci=gkihsiを計算する。そして、擬似ランダム関数部２１２は、(Ri, ci)を鍵配送装置Sへ送信する。
【０１３５】
Ui∈({U1, …, Un}-R)-Nの場合、通信装置Uiの擬似ランダム関数部２１２は、~ki∈R{0, 1}к, ~k'i∈RFSк, ~si∈R{0, 1}к, ~s'i∈RFSкを生成し、ねじれ擬似ランダム関数tPRFにより、ki=tPRF(~ki, ~k'i, sti, st'i), si=tPRF(~si, ~s'i, sti, st'i)を計算する。また、ci=gkihsiを計算する。そして、擬似ランダム関数部２１２は、ciを鍵配送装置Sへ送信する。
【０１３６】
ステップＳ５１２において、鍵配送装置Sは、通信装置Ui∈Nから(Ri, ci)を、通信装置Ui ∈({U1, …, Un}-R)-Nからまたはciを受信する。このとき、すべての通信装置Uiから(Ri, ci)またはciを受信するまで待機する。
【０１３７】
ステップＳ５１３において、鍵配送装置SのセッションID生成部１１３は、ターゲット衝突困難ハッシュ関数Hにより、通信装置Ui∈{U1, …, Un}-Rから受信した{ci}を用いて、sid=H({ci})を生成する。また、通信装置Ui∈Nから1台の通信装置を代表者として選択する。ここでは、通信装置U1が選択されたものとし、U1を代表通信装置と呼ぶ。また、代表通信装置U1以外のn-1-m台の通信装置Ui∈{U2, …, Un}-Rを一般通信装置と呼ぶ。セッションID生成部１１３は、Ui∈NかつUi+1∈Rとなるiについては、(sid, Rj)を通信装置Uiへそれぞれ送信する（ただし、jはUj∈Nかつj>iを満たす最小の添え字とする）。また、Ui∈NかつUi-1∈Rとなるiについては、(sid, Rj')を通信装置Uiへそれぞれ送信する（ただし、j'はUj'∈Nかつj'<iを満たす最大の添え字とする）。Ui∈({U1, …, Un}-R)-Nの場合、sidを通信装置Uiへそれぞれ送信する。また、鍵配送装置Sは、U1には代表者であることを通知しておく。
【０１３８】
ステップＳ６１３において、通信装置Uiは、鍵配送装置Sから(sid, Rj)、(sid, Rj')、sidのいずれかをそれぞれ受信する。通信装置Uiは、(sid, Rj)、(sid, Rj')、sidのいずれかを受け取り次第、以降の処理（具体的には、ステップＳ６１４とステップＳ６１５）を実行する。この処理は、i=1の場合、Ui∈NかつUi+1∈Rを満たすi（iは1でない）の場合、Ui∈NかつUi-1∈Rを満たすi（iは1でない）の場合、Ui∈({U1, …, Un}-R)-Nを満たすi（iは1でない）の場合の４つに場合分けして実行される。さらに、i=1の場合については、３つに場合分けして実行される。
【０１３９】
i=1の場合、ステップＳ６１４において、Uj=U3かつUj'=Un-1か、Uj'=Un-1かつU2∈Nか、Uj= U3かつUn∈Nのいずれかが成り立つ。Uj=U3かつUj'=Un-1が成り立つとき、代表通信装置U1の第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rn-1r1)を用いてK1lを生成し、擬似ランダム関数Fにより(sid, R3r1)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算する。ただし、||は連結演算子である。
【０１４０】
【数２７】
0006497747.tif 000028
【０１４１】
Uj'=Un-1かつU2∈Nが成り立つとき、代表通信装置U1の第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rn-1r1)を用いてK1lを生成し、擬似ランダム関数Fにより(sid, H1r)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算する。ただし、||は連結演算子である。
【０１４２】
【数２８】
0006497747.tif 000029
【０１４３】
Uj=U3かつUn∈Nが成り立つとき、代表通信装置U1の第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, H1l)を用いてK1lを生成し、擬似ランダム関数Fにより(sid, R3r1)を用いてK1rを生成し、K1lとK1rとの排他的論理和によりT1を計算し、K1lとk1||s1との排他的論理和によりT'を計算する。ただし、||は連結演算子である。
【０１４４】
【数２９】
0006497747.tif 000030
【０１４５】
ステップＳ６１５において、代表通信装置U1の認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mk1を用いて、認証タグσ1=Tagmk1(R1, c1, (R3, Rn-1), T1, T', U1, sid)を生成する。認証タグ生成部２１５は、(T1, T', σ1)を鍵配送装置Sへ送信する。
【０１４６】
Ui∈NかつUi+1∈Rとなるi（iは1でない）については、ステップＳ６１４において、通信装置Uiの第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Hil)を用いてKilを生成し、擬似ランダム関数Fにより(sid, Rjri)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算する。
【０１４７】
【数３０】
0006497747.tif 000031
【０１４８】
ステップＳ６１５において、通信装置Uiの認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mkiを用いて、認証タグσi=Tagmki(Ri, ci, Rj, ki, si, Ti, Ui, sid)を生成する。認証タグ生成部２１５は、(ki, si, Ti, σi)を鍵配送装置Sへ送信する。
【０１４９】
Ui∈NかつUi-1∈Rとなるi（iは1でない）については、ステップＳ６１４において、通信装置Uiの第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Rj'ri)を用いてKilを生成し、擬似ランダム関数Fにより(sid, Hir)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算する。
【０１５０】
【数３１】
0006497747.tif 000032
【０１５１】
ステップＳ６１５において、通信装置Uiの認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mkiを用いて、認証タグσi=Tagmki(Ri, ci, Rj', ki, si, Ti, Ui, sid)を生成する。認証タグ生成部２１５は、(ki, si, Ti, σi)を鍵配送装置Sへ送信する。
【０１５２】
Ui∈({U1, …, Un}-R)-Nとなるi（iは1でない）については、ステップＳ６１４において、通信装置Uiの第二鍵生成部２１４は、次式のように、擬似ランダム関数Fにより(sid, Hil)を用いてKilを生成し、擬似ランダム関数Fにより(sid, Hir)を用いてKirを生成し、KilとKirとの排他的論理和によりTiを計算する。
【０１５３】
【数３２】
0006497747.tif 000033
【０１５４】
ステップＳ６１５において、通信装置Uiの認証タグ生成部２１５は、メッセージ認証コードのタグ生成アルゴリズムTagにより、MAC鍵mkiを用いて、認証タグσi=Tagmki(ci, ki, si, Ti, Ui, sid)を生成する。認証タグ生成部２１５は、(ki, si, Ti, σi)を鍵配送装置Sへ送信する。
【０１５５】
ステップＳ５１４において、鍵配送装置Sの認証タグ検証部１１４は、代表通信装置U1から(T1, T', σ1)を受信し、それ以外の一般通信装置Ui、つまり、Ui∈({U1, …, Un}-R)- {U1}から(ki, si, Ti, σi)を受信し、メッセージ認証コードの検証アルゴリズムVerにより検証する。認証タグσiが正当でなければ通信装置Uiのセッションを終了する。また、Ui∈({U1, …, Un}-R)- {U1}の場合、ci=gkihsiが成り立つか否かを検証する。成り立たなければ一般通信装置Uiのセッションを終了する。
【０１５６】
ステップＳ５１５ａにおいて、鍵配送装置Sの第三鍵生成部１１５は、~kS∈R{0, 1}к, ~k'S∈RFSкを生成し、ねじれ擬似ランダム関数tPRFにより、kS=tPRF(~kS, ~k'S, stS, st'S)を計算する。Ui∈({U1, …, Un}-R)- {U1}となるiに対して、次式により、k'を計算する。
【０１５７】
【数３３】
0006497747.tif 000034
【０１５８】
ステップＳ５１５ｂにおいて、鍵配送装置Sの第三鍵生成部１１５は、Ui∈{U1, …, Un}-Rの場合、次式により、T'iを計算する。
【０１５９】
【数３４】
0006497747.tif 000035
【０１６０】
ただし、Uj∈RとなるjについてはTjを空とする。
【０１６１】
ステップＳ５１５ｃにおいて、鍵配送装置Sの第三鍵生成部１１５は、Ui∈{U1, …, Un}-Rとなるiについて、アクセス構造Pi=(ID=Ui)∧(time∈TF)として、関数暗号の暗号化アルゴリズムFEncにより共通鍵K1を暗号化して、暗号文CT'i=FEnc(Params, Pi, K1)を生成する。ここで、IDは通信装置を表す述語変数であり、TFは通信装置のタイムフレームを表す述語変数である。
【０１６２】
ステップＳ５１６において、鍵配送装置Sは認証タグを生成し、通信装置Uiに送信する。この処理は、i=1の場合、Ui∈NかつUi+1∈Rを満たすiの場合、Ui∈NかつUi-1∈Rを満たすiの場合、Ui∈({U1, …, Un}-R)-Nを満たすiの場合の４つに場合分けして実行される。
【０１６３】
i=1の場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、代表通信装置U1のMAC鍵mk1を用いて、認証タグσ'1=Tagmk1(R1, c1, (R3, Rn-1), T1, T', U1, sid, k', CT'1)を生成する。認証タグ生成部１１６は、(k', CT'1, σ'1)を代表通信装置U1へ送信する。
【０１６４】
Ui∈NかつUi+1∈Rとなるiの場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置UiのMAC鍵mkiを用いて認証タグσ'i=Tagmki(Ri, ci, Rj, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'i)を生成する。認証タグ生成部１１６は、(c1, k', T'i, T', CT'i, σ'i)を一般通信装置Uiへ送信する。
【０１６５】
Ui∈NかつUi-1∈Rとなるiの場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置UiのMAC鍵mkiを用いて認証タグσ'i=Tagmki(Ri, ci, Rj', ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'i)を生成する。認証タグ生成部１１６は、(c1, k', T'i, T', CT'i, σ'i)を一般通信装置Uiへ送信する。
【０１６６】
Ui∈({U1, …, Un}-R)-Nとなるiの場合、鍵配送装置Sの認証タグ生成部１１６は、メッセージ認証コードのタグ生成アルゴリズムTagにより、一般通信装置UiのMAC鍵mkiを用いて認証タグσ'i=Tagmki(ci, ki, si, Ti, Ui, sid, c1, k', T'i, T', CT'i)を生成する。認証タグ生成部１１６は、(c1, k', T'i, T', CT'i, σ'i)を一般通信装置Uiへ送信する。
【０１６７】
ステップＳ６１６において、Ui∈({U1, …, Un}-R)- {U1}となるiについて、一般通信装置Uiの認証タグ検証部２１６は、鍵配送装置Sから(c1, k', T'i, T', CT'i, σ'i)を受信し、メッセージ認証コードの検証アルゴリズムVerにより、検証する。認証タグσ'iが正当でなければ一般通信装置Uiのセッションを終了する。また、次式のように、T'iとKilとの排他的論理和によりK1lを計算し、T'とK1lとの排他的論理和によりk1||s1を計算する。
【０１６８】
【数３５】
0006497747.tif 000036
【０１６９】
そして、c1=gk1hs1が成り立つか否かを検証する。成り立たなければ一般通信装置Uiのセッションを終了する。
【０１７０】
i=1の場合、代表通信装置U1の認証タグ検証部２１６は、鍵配送装置Sから(k', CT'1, σ'1)を受信し、メッセージ認証コードの検証アルゴリズムVerにより、検証する。認証タグσ'1が正当でなければ代表通信装置U1のセッションを終了する。
【０１７１】
ステップＳ６１７において、通信装置Uiのセッション鍵生成部２１７は、関数暗号の復号アルゴリズムFDecにより、通信装置Uiのユーザ秘密鍵uskiを用いて、共通鍵K1←FDecuski(CT'i, Pi)を復号する。また、次式のように、擬似ランダム関数F'により共通鍵K2を計算する。
【０１７２】
【数３６】
0006497747.tif 000037
【０１７３】
そして、次式のように、擬似ランダム関数F"によりセッション鍵SKを計算する。
【０１７４】
【数３７】
0006497747.tif 000038
【０１７５】
最後に、ユーザ追加・ユーザ削除のために用いる秘密情報を通信装置Ui∈{U1, …, Un}-Rは更新する。通信装置Uiは、次式で計算される秘密情報rで記憶部２００に記憶しているものを更新する。
【０１７６】
【数３８】
0006497747.tif 000039
【０１７７】
また、代表通信装置U1は、次式で計算される秘密情報H1r(U2∈Rの場合)、H1l(Un∈Rの場合)で記憶部２００に記憶しているものを更新する。
【０１７８】
【数３９】
0006497747.tif 000040
【０１７９】
Ui∈NかつUi+1∈Rを満たすiについて、通信装置Uiは、次式で計算される秘密情報Hirで記憶部２００に記憶しているものを更新する。
【０１８０】
【数４０】
0006497747.tif 000041
【０１８１】
Ui∈NかつUi-1∈Rを満たすiについて、通信装置Uiは、次式で計算される秘密情報Hilで記憶部２００に記憶しているものを更新する。
【０１８２】
【数４１】
0006497747.tif 000042
【０１８３】
上記のように構成することにより、この発明の鍵交換技術によれば、従来のように事前に鍵交換を行うユーザの情報を登録しておく必要がなく、ユーザ削除時にも効率的に共通鍵を共有することができる。具体的には、鍵交換に必要な全体の計算量はユーザ数の定数回、すなわちO(1)となる。
【０１８４】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１８５】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１８６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１８７】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１８８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１８９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１９０】
１  鍵配送装置
２  通信装置
３  通信網
１００  記憶部
１０１  セットアップ部
１０２  公開鍵生成部
１０３  秘密ストリング生成部
１１１  ユーザ鍵送信部
１１３  セッションID生成部
１１４  認証タグ検証部
１１５  第三鍵生成部
１１６  認証タグ生成部
２００  記憶部
２０２  公開鍵生成部
２０３  秘密ストリング生成部
２１１  ユーザ鍵受信部
２１２  第一鍵生成部
２１４  第二鍵生成部
２１５  認証タグ生成部
２１６  認証タグ検証部
２１７  セッション鍵生成部
【図１】
0006497747.tif 000043
【図２】
0006497747.tif 000044
【図３】
0006497747.tif 000045
【図４】
0006497747.tif 000046
【図５】
0006497747.tif 000047
【図６】
0006497747.tif 000048