(57)【要約】  動的なメンバ変更を許しながら複数のユーザが共通鍵を共有し、鍵交換に必要な計算量を低減する。第一鍵生成部２１２がねじれ疑似ランダム関数を用いてRi, ciを計算する。セッションID生成部１１３がターゲット衝突困難ハッシュ関数によりsidを生成し、(sid, Rα, Rβ)を通信装置Uiへ送信する。代表通信装置U1の第二鍵生成部２１４が疑似ランダム関数を用いてT1を計算する。一般通信装置Ujの第二鍵生成部２１４が疑似ランダム関数を用いてTjを計算する。第三鍵生成部１１５がねじれ疑似ランダム関数を用いてk'を計算し、各jについてT'jを計算する。一般通信装置Ujのセッション鍵生成部２１７がKjl, k1を計算する。セッション鍵生成部２１７が疑似ランダム関数により共通鍵K2を生成する。
2016199507.tif 000002
【特許請求の範囲】
【請求項１】
nを2以上の整数とし、iを1からnまでの各整数とし、jを2からnまでの各整数とし、Sを鍵配送装置とし、Uiをn台の通信装置とし、U1を上記通信装置Uiから選択された1台の代表通信装置とし、Ujを上記通信装置Uiから上記代表通信装置U1を除いたn-1台の一般通信装置とし、||を連結演算子とし、α, βを次式で定義される整数とし、
【数１１】
2016199507.tif 000013
上記鍵配送装置Sの記憶部に、上記鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sが記憶されており、
上記通信装置Uiの記憶部に、上記通信装置Uiの公開鍵暗号の秘密鍵skiおよび秘密ストリングsti, st'iが記憶されており、
上記通信装置Uiが、ねじれ疑似ランダム関数により上記秘密ストリングsti, st'iを用いてri, ki, siを生成し、Ri=griおよびci=gkihsiを計算し、(Ri, ci)を上記鍵配送装置Sへ送信する第一鍵生成ステップと、
上記鍵配送装置Sが、ターゲット衝突困難ハッシュ関数によりc1, …, cnを用いてsidを生成し、各iについて(sid, Rα, Rβ)を上記通信装置Uiへ送信するセッションID生成ステップと、
上記代表通信装置U1が、疑似ランダム関数により(sid, Rnr1)を用いてK1lを生成し、K1lとk1||s1との排他的論理和によりT1を計算し、T1を上記鍵配送装置Sへ送信する代表第二鍵生成ステップと、
上記一般通信装置Ujが、疑似ランダム関数により(sid, Rαrj)を用いてKjlを生成し、疑似ランダム関数により(sid, Rβrj)を用いてKjrを生成し、KjlとKjrとの排他的論理和によりTjを計算し、(kj, sj, Tj)を上記鍵配送装置Sへ送信する一般第二鍵生成ステップと、
上記鍵配送装置Sが、ねじれ疑似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、k2, …, kn, ksの排他的論理和によりk'を計算し、各jについてT1, …, Tj-1の排他的論理和によりT'jを計算し、k'を上記代表通信装置U1へ送信し、(k', T'j, T1)を上記一般通信装置Ujへ送信する第三鍵生成ステップと、
上記一般通信装置Ujが、T'jとKjrとの排他的論理和によりKjlを計算し、T1とKjlとの排他的論理和によりk1||s1を計算する第一セッション鍵生成ステップと、
上記通信装置Uiが、疑似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成する第二セッション鍵生成ステップと、
を含む鍵交換方法。
【請求項２】
請求項１に記載の鍵交換方法であって、
timeを現在時刻とし、IDを上記通信装置を表す述語変数とし、TFを上記通信装置のタイムフレームを表す述語変数とし、
上記鍵配送装置Sの記憶部に、関数暗号のマスタ秘密鍵mskがさらに記憶されており、
上記鍵配送装置Sが、各iについて属性をAi=(Ui, time)として関数暗号の鍵導出アルゴリズムにより上記マスタ秘密鍵mskを用いてユーザ秘密鍵uskiを生成し、公開鍵暗号の暗号化アルゴリズムにより上記通信装置Uiの公開鍵pkiを用いて上記ユーザ秘密鍵uskiを暗号化して暗号文CTiを生成するユーザ鍵送信ステップと、
上記通信装置Uiが、公開鍵暗号の復号アルゴリズムにより上記秘密鍵skiを用いて上記暗号文CTiを復号して上記ユーザ秘密鍵uskiを得るユーザ鍵受信ステップと、
をさらに含み、
上記第三鍵生成ステップは、ねじれ疑似ランダム関数により上記秘密ストリングstS, st'Sを用いて共通鍵K1を生成し、各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, Rn, R2, T1, U1, sidを用いて認証タグσ1を生成する代表第一認証タグ生成ステップと、
上記一般通信装置Ujが、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkjおよびRj, cj, Rα, Rβ, kj, sj, Tj, Uj ,sidを用いて認証タグσjを生成する一般第一認証タグ生成ステップと、
上記鍵配送装置Sが、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mk1およびR1, c1, Rn, R2, T1, U1, sidを用いて上記認証タグσ1を検証し、各jについてメッセージ認証コードの検証アルゴリズムにより上記MAC鍵mkjおよびRj, cj, Rα, Rβ, kj, sj, Tj, Uj ,sidを用いて上記認証タグσjを検証し、cj=gkjhsjが成り立つか否かを検証する第一認証タグ検証ステップと、
上記鍵配送装置Sが、メッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mk1およびR1, c1, Rn, R2, T1, U1, sid, k', CT'1を用いて認証タグσ'1を生成し、各jについてメッセージ認証コードのタグ生成アルゴリズムにより上記MAC鍵mkjおよびRj, cj, Rα, Rβ, kj, sj, Tj, Uj, sid, c1, k', T'j, T1, CT'jを用いて認証タグσ'jを生成する第二認証タグ生成ステップと、
上記代表通信装置U1が、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mk1およびR1, c1, Rn, R2, T1, U1, sid, k', CT'1を用いて上記認証タグσ'1を検証する代表第二認証タグ検証ステップと、
上記一般通信装置Ujが、メッセージ認証コードの検証アルゴリズムにより上記MAC鍵mkjおよびRj, cj, Rα, Rβ, kj, sj, Tj, Uj, sid, c1, k', T'j, T1, CT'jを用いて上記認証タグσ'jを検証し、T'jとKjlとの排他的論理和によりK1lを計算し、T1とK1lとの排他的論理和によりk1||s1を求め、c1=gk1hs1が成り立つか否かを検証する一般第二認証タグ検証ステップと、
をさらに含む鍵交換方法。
【請求項４】
nを2以上の整数とし、iを1からnまでの各整数とし、jを2からnまでの各整数とし、||を連結演算子とし、α, βを次式で定義される整数とし、
【数１２】
2016199507.tif 000014
鍵配送装置Sとn台の通信装置Uiとを含み、上記通信装置Uiは代表通信装置U1とn-1台の一般通信装置Ujとからなる鍵交換システムであって、
上記鍵配送装置Sは、
上記鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sを記憶する記憶部と、
各iについて上記通信装置Uiから(Ri, ci)を受信し、ターゲット衝突困難ハッシュ関数によりc1, …, cnを用いてsidを生成し、各iについて(sid, Rα, Rβ)を上記通信装置Uiへ送信するセッションID生成部と、
上記代表通信装置U1からT1を受信し、各jについて上記一般通信装置Ujから(kj, sj, Tj)を受信し、ねじれ疑似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、k2, …, kn, ksの排他的論理和によりk'を計算し、各jについてT1, …, Tj-1の排他的論理和によりT'jを計算し、k'を上記代表通信装置U1へ送信し、(k', T'j, T1)を上記一般通信装置Ujへ送信する第三鍵生成部と、
を含み、
上記代表通信装置U1は、
上記代表通信装置U1の公開鍵暗号の秘密鍵sk1および秘密ストリングst1, st'1を記憶する記憶部と、
ねじれ疑似ランダム関数により上記秘密ストリングst1, st'1を用いてr1, k1, s1を生成し、R1=gr1およびc1=gk1hs1を計算し、(R1, c1)を上記鍵配送装置Sへ送信する第一鍵生成部と、
上記鍵配送装置Sから(sid, Rn, R2)を受信し、疑似ランダム関数により(sid, Rnr1)を用いてK1lを生成し、K1lとk1||s1との排他的論理和によりT1を計算し、T1を上記鍵配送装置Sへ送信する第二鍵生成部と、
上記鍵配送装置Sからk'を受信し、疑似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成するセッション鍵生成部と、
を含み、
上記一般通信装置Ujは、
上記一般通信装置Ujの公開鍵暗号の秘密鍵skjおよび秘密ストリングstj, st'jを記憶する記憶部と、
ねじれ疑似ランダム関数により上記秘密ストリングstj, st'jを用いてrj, kj, sjを生成し、Rj=grjおよびcj=gkjhsjを計算し、(Rj, cj)を上記鍵配送装置Sへ送信する第一鍵生成部と、
上記鍵配送装置Sから(sid, Rα, Rβ)を受信し、疑似ランダム関数により(sid, Rαrj)を用いてKjlを生成し、疑似ランダム関数により(sid, Rβrj)を用いてKjrを生成し、KjlとKjrとの排他的論理和によりTjを計算し、(kj, sj, Tj)を上記鍵配送装置Sへ送信する第二鍵生成部と、
上記鍵配送装置Sから(k', T'j, T1)を受信し、T'jとKjrとの排他的論理和によりKjlを計算し、T1とKjlとの排他的論理和によりk1||s1を計算し、疑似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて上記共通鍵K2を生成するセッション鍵生成部と、
を含む鍵交換システム。
【請求項５】
nを2以上の整数とし、iを1からnまでの各整数とし、jを2からnまでの各整数とし、α, βを次式で定義される整数とし、
【数１３】
2016199507.tif 000015
公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sを記憶する記憶部と、
各iについて通信装置Uiから(Ri, ci)を受信し、ターゲット衝突困難ハッシュ関数によりc1, …, cnを用いてsidを生成し、各iについて(sid, Rα, Rβ)を上記通信装置Uiへ送信するセッションID生成部と、
代表通信装置U1からT1を受信し、各jについて一般通信装置Ujから(kj, sj, Tj)を受信し、ねじれ疑似ランダム関数により上記秘密ストリングstS, st'Sを用いてksを生成し、k2, …, kn, ksの排他的論理和によりk'を計算し、各jについてT1, …, Tj-1の排他的論理和によりT'jを計算し、k'を上記代表通信装置U1へ送信し、(k', T'j, T1)を上記一般通信装置Ujへ送信する第三鍵生成部と、
を含む鍵配送装置。
【請求項６】
nを2以上の整数とし、||を連結演算子とし、
公開鍵暗号の秘密鍵sk1および秘密ストリングst1, st'1を記憶する記憶部と、
ねじれ疑似ランダム関数により上記秘密ストリングst1, st'1を用いてr1, k1, s1を生成し、R1=gr1およびc1=gk1hs1を計算し、(R1, c1)を鍵配送装置Sへ送信する第一鍵生成部と、
上記鍵配送装置Sから(sid, Rn, R2)を受信し、疑似ランダム関数により(sid, Rnr1)を用いてK1lを生成し、K1lとk1||s1との排他的論理和によりT1を計算し、T1を上記鍵配送装置Sへ送信する第二鍵生成部と、
上記鍵配送装置Sからk'を受信し、疑似ランダム関数によりsidおよびk'とk1との排他的論理和を用いて共通鍵K2を生成するセッション鍵生成部と、
を含む通信装置。
【請求項７】
nを2以上の整数とし、jを2以上n以下の整数とし、||を連結演算子とし、α, βを次式で定義される整数とし、
【数１４】
2016199507.tif 000016
公開鍵暗号の秘密鍵skjおよび秘密ストリングstj, st'jを記憶する記憶部と、
ねじれ疑似ランダム関数により上記秘密ストリングstj, st'jを用いてrj, kj, sjを生成し、Rj=grjおよびcj=gkjhsjを計算し、(Rj, cj)を鍵配送装置Sへ送信する第一鍵生成部と、
上記鍵配送装置Sから(sid, Rα, Rβ)を受信し、疑似ランダム関数により(sid, Rαrj)を用いてKjlを生成し、疑似ランダム関数により(sid, Rβrj)を用いてKjrを生成し、KjlとKjrとの排他的論理和によりTjを計算し、(kj, sj, Tj)を上記鍵配送装置Sへ送信する第二鍵生成部と、
上記鍵配送装置Sから(k', T'j, T1)を受信し、T'jとKjrとの排他的論理和によりKjlを計算し、T1とKjlとの排他的論理和により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］、［平成27年6月5日検索］、インターネット<URL:https://tools.ietf.org/html/rfc1949>
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１、２に記載の従来技術では、予め共通鍵を共有するユーザを登録しておく必要があるため、動的なメンバ変更を許しながら複数のユーザが共通鍵を共有することはできない。また、ユーザ数をnとして、全体として鍵交換に必要な計算量はO(log n)となるため、ユーザ数の増大に従って鍵交換の計算量が増えるという問題がある。【０００５】
この発明の目的は、このような点に鑑みて、動的なメンバ変更を許しながら複数のユーザが共通鍵を共有することができ、鍵交換に必要な計算量を低減することができる鍵交換技術を提供することである。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、この発明の鍵交換方法は、nを2以上の整数とし、iを1からnまでの各整数とし、jを2からnまでの各整数とし、Sを鍵配送装置とし、Uiをn台の通信装置とし、U1をn台の通信装置Uiから選択された1台の代表通信装置とし、Ujをn台の通信装置Uiから代表通信装置U1を除いたn-1台の一般通信装置とし、||を連結演算子とし、α, βを次式で定義される整数とし、【０００７】
【数１】
2016199507.tif 000003
【０００８】
鍵配送装置Sの記憶部に、鍵配送装置Sの公開鍵暗号の秘密鍵skSおよび秘密ストリングstS, st'Sが記憶されており、通信装置Uiの記憶部に、通信装置Uiの公開鍵暗号の秘密鍵skiおよび秘密ストリングsti, st'iが記憶されており、通信装置Uiが、ねじれ疑似ランダム関数により秘密ストリングsti, st'iを用いてri, ki, siを生成し、Ri=griおよびci=gkihsiを計算し、(Ri, ci)を鍵配送装置Sへ送信する第一鍵生成ステップと、鍵配送装置Sが、ターゲット衝突困難ハッシュ関数によりc1, …, cnを用いてsidを生成し、各iについて(sid, Rα, Rβ)を通信装置Uiへ送信するセッションID生成ステップと、代表通信装置U1が、疑似ランダム関数により(sid, Rnr1)を用いてK1lを生成し、K1lとk1||s1との排他的論理和によりT1を計算し、T1を鍵配送装置Sへ送信する代表第二鍵生成ステップと、一般通信装置Ujが、疑似ランダム関数により(sid, Rαrj)を用いてKjlを生成し、疑似ランダム関数により(sid, Rβrj)を用いてKjrを生成し、KjlとKjrとの排他的論理和によりTjを計算し、(kj, sj, Tj)を鍵配送装置Sへ送信する一般第二鍵生成ステップと、鍵配送装置Sが、ねじれ疑似ランダム関数により秘密ストリングstS, st'Sを用いてksを生成し、k2, …, kn, ksの排他的論理和によりk'を計算し、各jについてT1, …, Tj-1の排他的論理和によりT'jを計算し、k'を代表通信装置U1へ送信し、(k', T'j, T1)を一般通信装置Ujへ送信する第三鍵生成ステップと、一般通信装置Ujが、T'jとKjrとの排他的論理和によりKjlを計算し、T1とKjlとの排他的論理和によりk1||s1を計算する第一セッション鍵生成ステップと、通信装置Uiが、疑似ランダム関数により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кを用いて、
【数２】
2016199507.tif 000004
と定義する。ただし、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へそれぞれ送信する。
【数３】
2016199507.tif 000005
【００４３】
ステップＳ２１３において、通信装置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を計算する。
【数４】
2016199507.tif 000006
【００４５】
ステップＳ２１５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を計算する。ただし、||は連結演算子である。
【数５】
2016199507.tif 000007
【００４７】
ステップＳ２１５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'を計算する。
【数６】
2016199507.tif 000008
【００５１】
ステップＳ１１５ｂにおいて、鍵配送装置Sの第三鍵生成部１１５は、j=2, …, nについて、次式により、T'jを計算する。
【数７】
2016199507.tif 000009
【００５２】
ステップＳ１１５ｃにおいて、鍵配送装置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を計算する。
【数８】
2016199507.tif 000010
【００５６】
そして、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を計算する。
【数９】
2016199507.tif 000011
【００５９】
そして、次式のように、疑似ランダム関数F"によりセッション鍵SKを計算する。
【数１０】
2016199507.tif 000012
【００６０】
上記のように構成することにより、この発明の鍵交換技術によれば、従来のように事前に鍵交換を行うユーザの情報を登録しておく必要がなく、動的なメンバ変更を許しながら複数のユーザが共通鍵を共有することができる。また、従来は鍵交換に必要な全体の計算量がユーザ数をnとしてO(log n)となるが、この発明によればユーザ数の定数回、すなわちO(1)となるため、従来よりも少ない計算量で鍵交換ができる。
【００６１】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６２】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００６３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６４】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2016199507.tif 000017
【図２】
2016199507.tif 000018
【図３】
2016199507.tif 000019
【図４】
2016199507.tif 000020
【手続補正書】
【提出日】平成29年12月6日(2017.12.6)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
関数tPRF: {0, 1}к×FSк×{0, 1}к×FSк→Rngкをねじれ疑似ランダム関数と呼び、疑似ランダム関数Fкを用いて、
【数２】
2016199507.tif 000021
と定義する。ただし、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.
【国際調査報告】
2016199507.tif 000022
2016199507.tif 000023