(57)【要約】【課題】ランダムオラクルを必要とせず拡張性が高い。【解決手段】鍵交換システムＡは鍵生成装置１と階層化されたN台の通信装置２1,…,２Nを含む。鍵生成装置１はマスタ秘密鍵及び公開パラメータを生成し、マスタ秘密鍵を用いて長期秘密鍵を生成する。通信装置２nはアドホック秘密鍵を生成し、アドホック秘密鍵を用いて擬似乱数を生成し、擬似乱数を用いて署名鍵及び検証鍵を生成する。通信装置２nは長期秘密鍵と擬似乱数を用いて暗号文を生成し、暗号文に対して署名鍵を用いて署名をしてアドホック公開鍵を生成する。通信装置２nは他の通信装置からアドホック公開鍵を受信すると署名を検証する。検証が完了すると、暗号文、長期秘密鍵及び擬似乱数を用いて秘密情報を生成し、秘密情報を擬似ランダム関数の入力としてセッション鍵を生成する。【選択図】図１
2014220669.tif 000002
【特許請求の範囲】
【請求項１】
鍵生成装置とL階層に階層化された複数の通信装置を含む鍵交換システムであって、
^はべき乗を表し、・は乗算を表し、Zpは素数pを法とする剰余環とし、G,GTは双線形ペアリング関数e:G×G→GTを効率的に計算可能な群とし、gは群Gの生成元とし、Fke、Fgen、Fsig及びFkdfは擬似ランダム関数とし、FSは擬似ランダム関数の鍵空間とし、Genは任意の使いきり署名方式の署名鍵生成アルゴリズムとし、Signは上記使いきり署名方式の署名生成アルゴリズムとし、Verは上記使いきり署名方式の署名検証アルゴリズムとし、
上記鍵生成装置は、
値zを環Zpから選択し、値g1=gzを計算し、値g2,g3,g4,h1,…,hLを群Gから選択するパラメータ生成部と、
マスタ秘密鍵MSK=g2zを計算するマスタ秘密鍵生成部と、
第i階層に属する通信装置の長期秘密鍵SSKiを、値rを環Zpから選択し、値w1,w2,w3,w4,w5,w6を上記鍵空間FSから選択し、u0=MSK・(h1^ID1…hi^IDi・g3)r、u1=gr、u2=g4rを計算し、SSKi=(u0,u1,u2,hi+1r,…,hLr,w1,w2,w3,w4,w5,w6)として生成する長期秘密鍵生成部と、
を含み、
上記通信装置は、
第α階層に属し識別情報ID=（ID1,…,IDα）が設定されており、第β階層に属し識別情報ID'=（ID'1,…,ID'β）が設定された上記通信装置とセッション鍵SKを共有するものとして、
値eskke,esk'ke,eskgen,esk'gen,esksig,esk'sigを上記鍵空間FSから選択するアドホック秘密鍵生成部と、
上記擬似ランダム関数Fke(w1,eskke)の出力と上記擬似ランダム関数Fke(esk'ke,w2)の出力との排他的論理和を計算して擬似乱数sを生成し、上記擬似ランダム関数Fgen(w3,eskgen)の出力と上記擬似ランダム関数Fgen(esk'gen,w4)の出力との排他的論理和を計算して擬似乱数randgenを生成し、上記擬似ランダム関数Fsig(w5,esksig)の出力と上記擬似ランダム関数Fsig(esk'sig,w6)の出力との排他的論理和を計算して擬似乱数randsigを生成する擬似乱数生成部と、
上記擬似乱数randgenを用いて上記鍵生成アルゴリズムGenを実行し、署名鍵skと検証鍵vkを生成する署名鍵生成部と、
値gのs乗を計算して暗号文C1を生成し、(h1^ID'1…hβ^ID'β・g4vk・g3)sを計算して暗号文C2を生成する暗号文生成部と、
上記暗号文C1及び上記暗号文C2を入力として上記擬似乱数randsig及び上記署名鍵skを用いて上記署名アルゴリズムSignを実行して署名σを生成し、上記暗号文C1、上記暗号文C2、署名σ及び検証鍵vkを含むアドホック公開鍵EPKを生成するアドホック公開鍵生成部と、
上記識別情報ID'が設定された通信装置から暗号文C'1、暗号文C'2、署名σ'及び検証鍵vk'を含むアドホック公開鍵EPK'を受信すると、上記暗号文C'1、上記暗号文C'2及び上記署名σ'を入力として上記検証鍵vk'を用いて上記検証アルゴリズムVerを実行し、上記アドホック公開鍵EPK'を検証するアドホック公開鍵検証部と、
e(g1,g2)sを計算して秘密情報σ1を生成し、e(C'1,u0・u2vk')/e(C'2,u1)を計算して秘密情報σ2を生成し、e(C'1,g3)sを計算して秘密情報σ3を生成する秘密情報生成部と、
識別情報ID、識別情報ID'、アドホック公開鍵EPK及びアドホック公開鍵EPK'に基づいてセッション識別情報STを生成し、上記秘密情報σ1及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力と上記秘密情報σ2及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力と上記秘密情報σ3及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力との排他的論理和を計算し、上記セッション鍵SKを生成するセッション鍵生成部と、
を含む鍵交換システム。
【請求項２】
請求項１に記載の鍵交換システムであって、
上記通信装置は、
長期秘密鍵SSK=（u0,u1,u2,vi,…,vL,w1,w2,w3,w4,w5,w6）を持つとして、値r'を環Zpから選択し、値w'1,w'2,w'3,w'4,w'5,w'6を上記鍵空間FSから選択し、長期秘密鍵SSK'を次式により生成する長期秘密鍵生成部と、
【数３３】
2014220669.tif 000035
をさらに含む
鍵交換システム。
【請求項３】
^はべき乗を表し、・は乗算を表し、Zpは素数pを法とする剰余環とし、G,GTは双線形ペアリング関数e:G×G→GTを効率的に計算可能な群とし、gは群Gの生成元とし、FSは擬似ランダム関数の鍵空間とし、
値zを環Zpから選択し、値g1=gzを計算し、値g2,g3,g4,h1,…,hLを群Gから選択するパラメータ生成部と、
マスタ秘密鍵MSK=g2zを計算するマスタ秘密鍵生成部と、
第i階層に属する通信装置の長期秘密鍵SSKiを、値rを環Zpから選択し、値w1,w2,w3,w4,w5,w6を上記鍵空間FSから選択し、u0=MSK・(h1^ID1…hi^IDi・g3)r、u1=gr、u2=g4rを計算し、SSKi=(u0,u1,u2,hi+1r,…,hLr,w1,w2,w3,w4,w5,w6)として生成する長期秘密鍵生成部と、
を含む鍵生成装置。
【請求項４】
L階層に階層化された複数の通信装置において、第α階層に属し識別情報ID=（ID1,…,IDα）が設定されており、第β階層に属し識別情報ID'=（ID'1,…,ID'β）が設定された上記通信装置とセッション鍵SKを共有する通信装置であって、
^はべき乗を表し、・は乗算を表し、Zpは素数pを法とする剰余環とし、G,GTは双線形ペアリング関数e:G×G→GTを効率的に計算可能な群とし、gは群Gの生成元とし、Fke、Fgen、Fsig及びFkdfは擬似ランダム関数とし、FSは擬似ランダム関数の鍵空間とし、Genは任意の使いきり署名方式の署名鍵生成アルゴリズムとし、Signは上記使いきり署名方式の署名生成アルゴリズムとし、Verは上記使いきり署名方式の署名検証アルゴリズムとし、
値zは環Zpから選択された乱数であり、値g1=gzであり、値g2,g3,g4,h1,…,hLは群Gから選択された乱数であり、マスタ秘密鍵MSK=g2zであり、値rを環Zpから選択された乱数であり、値w1,w2,w3,w4,w5,w6は上記鍵空間FSから選択された乱数であり、第i階層に属する上記通信装置の長期秘密鍵SSKiはu0=MSK・(h1^ID1…hi^IDi・g3)r、u1=gr、u2=g4rとしてSSKi=(u0,u1,u2,hi+1r,…,hLr,w1,w2,w3,w4,w5,w6)であり、
値eskke,esk'ke,eskgen,esk'gen,esksig,esk'sigを上記鍵空間FSから選択するアドホック秘密鍵生成部と、
上記擬似ランダム関数Fke(w1,eskke)の出力と上記擬似ランダム関数Fke(esk'ke,w2)の出力との排他的論理和を計算して擬似乱数sを生成し、上記擬似ランダム関数Fgen(w3,eskgen)の出力と上記擬似ランダム関数Fgen(esk'gen,w4)の出力との排他的論理和を計算して擬似乱数randgenを生成し、上記擬似ランダム関数Fsig(w5,esksig)の出力と上記擬似ランダム関数Fsig(esk'sig,w6)の出力との排他的論理和を計算して擬似乱数randsigを生成する擬似乱数生成部と、
上記擬似乱数randgenを用いて上記鍵生成アルゴリズムGenを実行し、署名鍵skと検証鍵vkを生成する署名鍵生成部と、
値gのs乗を計算して暗号文C1を生成し、(h1^ID'1…hβ^ID'β・g4vk・g3)sを計算して暗号文C2を生成する暗号文生成部と、
上記暗号文C1及び上記暗号文C2を入力として上記擬似乱数randsig及び上記署名鍵skを用いて上記署名アルゴリズムSignを実行して署名σを生成し、上記暗号文C1、上記暗号文C2、上記署名σ及び上記検証鍵vkを含むアドホック公開鍵EPKを生成するアドホック公開鍵生成部と、
上記識別情報ID'が設定された通信装置から暗号文C'1、暗号文C'2、署名σ'及び検証鍵vk'を含むアドホック公開鍵EPK'を受信すると、上記暗号文C'1、上記暗号文C'2及び上記署名σ'を入力として上記検証鍵vk'を用いて上記検証アルゴリズムVerを実行し、上記アドホック公開鍵EPK'を検証するアドホック公開鍵検証部と、
e(g1,g2)sを計算して秘密情報σ1を生成し、e(C'1,u0・u2vk')/e(C'2,u1)を計算して秘密情報σ2を生成し、e(C'1,g3)sを計算して秘密情報σ3を生成する秘密情報生成部と、
識別情報ID、識別情報ID'、アドホック公開鍵EPK及びアドホック公開鍵EPK'に基づいてセッション識別情報STを生成し、上記秘密情報σ1及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力と上記秘密情報σ2及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力と上記秘密情報σ3及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力との排他的論理和を計算し、上記セッション鍵SKを生成するセッション鍵生成部と、
を含む通信装置。
【請求項５】
L階層に階層化された複数の通信装置において、第α階層に属し識別情報ID=（ID1,…,IDα）が設定された上記通信装置と、第β階層に属し識別情報ID'=（ID'1,…,ID'β）が設定された上記通信装置とがセッション鍵SKを共有する鍵交換方法であって、
^はべき乗を表し、・は乗算を表し、Zpは素数pを法とする剰余環とし、G,GTは双線形ペアリング関数e:G×G→GTを効率的に計算可能な群とし、gは群Gの生成元とし、Fke、Fgen、Fsig及びFkdfは擬似ランダム関数とし、FSは擬似ランダム関数の鍵空間とし、Genは任意の使いきり署名方式の署名鍵生成アルゴリズムとし、Signは上記使いきり署名方式の署名生成アルゴリズムとし、Verは上記使いきり署名方式の署名検証アルゴリズムとし、
パラメータ生成部が、値zを環Zpから選択し、値g1=gzを計算し、値g2,g3,g4,h1,…,hLを群Gから選択するパラメータ生成ステップと、
マスタ秘密鍵生成部が、マスタ秘密鍵MSK=g2zを計算するマスタ秘密鍵生成ステップと、
長期秘密鍵生成部が、第i階層に属する通信装置の長期秘密鍵SSKiを、値rを環Zpから選択し、値w1,w2,w3,w4,w5,w6を上記鍵空間FSから選択し、u0=MSK・(h1^ID1…hi^IDi・g3)r、u1=gr、u2=g4rを計算し、SSKi=(MSK・(h1^ID1…hi^IDi・g3)r,gr,g4r,hi+1r,…,hLr,w1,w2,w3,w4,w5,w6)として生成する長期秘密鍵生成ステップと、
アドホック秘密鍵生成部が、値eskke,esk'ke,eskgen,esk'gen,esksig,esk'sigを上記鍵空間FSから選択するアドホック秘密鍵生成ステップと、
擬似乱数生成部が、上記擬似ランダム関数Fke(w1,eskke)の出力と上記擬似ランダム関数Fke(esk'ke,w2)の出力との排他的論理和を計算して擬似乱数sを生成し、上記擬似ランダム関数Fgen(w3,eskgen)の出力と上記擬似ランダム関数Fgen(esk'gen,w4)の出力との排他的論理和を計算して擬似乱数randgenを生成し、上記擬似ランダム関数Fsig(w5,esksig)の出力と上記擬似ランダム関数Fsig(esk'sig,w6)の出力との排他的論理和を計算して擬似乱数randsigを生成する擬似乱数生成ステップと、
署名鍵生成部が、上記擬似乱数randgenを用いて上記鍵生成アルゴリズムGenを実行し、署名鍵skと検証鍵vkを生成する署名鍵生成ステップと、
暗号文生成部が、値gのs乗を計算して暗号文C1を生成し、(h1^ID'1…hβ^ID'β・g4vk・g3)sを計算して暗号文C2を生成する暗号文生成ステップと、
アドホック公開鍵生成部が、上記暗号文C1及び上記暗号文C2を入力として上記擬似乱数randsig及び上記署名鍵skを用いて上記署名アルゴリズムSignを実行して署名σを生成し、上記暗号文C1、上記暗号文C2、上記署名σ及び上記検証鍵vkを含むアドホック公開鍵EPKを生成するアドホック公開鍵生成部と、
アドホック公開鍵検証部が、上記識別情報ID'が設定された通信装置から暗号文C'1、暗号文C'2、署名σ'及び検証鍵vk'を含むアドホック公開鍵EPK'を受信すると、上記暗号文C'1、上記暗号文C'2及び上記署名σ'を入力として上記検証鍵vk'を用いて上記検証アルゴリズムVerを実行し、上記アドホック公開鍵EPK'を検証するアドホック公開鍵検証ステップと、
秘密情報生成部が、e(g1,g2)sを計算して秘密情報σ1を生成し、e(C'1,u0・u2vk')/e(C'2,u1)を計算して秘密情報σ2を生成し、e(C'1,g3)sを計算して秘密情報σ3を生成する秘密情報生成ステップと、
セッション鍵生成部が、識別情報ID、識別情報ID'、アドホック公開鍵EPK及びアドホック公開鍵EPK'に基づいてセッション識別情報STを生成し、上記秘密情報σ1及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力と上記秘密情報σ2及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力と上記秘密情報σ3及び上記セッション識別情報STを入力とする上記擬似ランダム関数Fkdfの出力との排他的論理和を計算し、上記セッション鍵SKを生成するセッション鍵生成ステップと、
を含む鍵交換方法。
【請求項６】
請求項３に記載の鍵生成装置または請求項４に記載の通信装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関し、特に、二者間で共通のセッション鍵を共有する鍵交換技術に関する。
【背景技術】
【０００２】
従来の鍵交換技術には、階層型IDベース暗号方式を応用した階層型ID認証鍵交換方式がある。非特許文献１には、秘密鍵漏洩に強い階層型ID認証鍵交換方式であるFSY方式が記載されている。
【０００３】
以下、FSY方式について説明する。
【０００４】
〔公開パラメータ〕
PIDをプロトコルIDとし、プロトコル仕様に対応した固有のIDとする。セキュリティパラメータをкとする。pをkビットの素数とし、G,GTを双線形ペアリング関数e:G×G→GTを効率的に計算可能な群とする。g,gTをそれぞれ群G,GTの生成元とする。Zpをpを法とする剰余環とする。H1:{0,1}*→G、H2:{0,1}*→Zp及びH:{0,1}*→{0,1}кをハッシュ関数とする。
【０００５】
〔鍵生成処理〕
FSY方式の鍵生成アルゴリズムは、一様ランダムにマスタ秘密鍵s0∈Zpを選び、S0=1G（∈G）を設定する。ただし、1Gは群Gの単位元である。また、鍵生成アルゴリズムはマスタ公開鍵P0=g（∈G）、Q0=P0^s0（∈G）を計算して公開する。ここで、^はべき乗を表す。
【０００６】
〔鍵抽出処理〕
鍵交換方式の各ユーザは識別情報（ID1,…,IDt-1）に対応するものとする。各ユーザは初期化処理として、st-1∈Zpを一様ランダムに選び、秘密の状態情報として保持する。識別情報ID=（ID1,…,IDt-1）を設定されたユーザは鍵抽出者として自分の長期秘密鍵（St-1,Q1,…,Qt-1）を用いて、識別情報ID’=（ID1,…,IDt）を設定された下位のユーザ向けに次のように長期秘密鍵（St,Q1,…,Qt）を生成する。まず、鍵抽出者はPt=H1(ID1,…,IDt)（∈G）、St=St-1Pt^st-1、Qt=P0^stを計算する。続いて、鍵抽出者は下位のユーザの長期秘密鍵として（St,Q1,…,Qt）を出力する。
【０００７】
〔鍵交換処理〕
ここでは、ユーザUAを鍵交換セッションのイニシエータとし、ユーザUBをレスポンダとする。ユーザUAは第α階層に属し、識別情報IDA=（IDA,1,…,IDA,α）に対応する長期秘密鍵（SA,α,QA,1,…,QA,α）を持つ。ユーザUBは第β階層に属し、識別情報IDB=（IDB,1,…,IDB,β）に対応する長期秘密鍵（SB,β,QB,1,…,QB,β）を持つ。
【０００８】
まず、ユーザUAは一様ランダムにアドホック秘密鍵~x∈Zpを選ぶ。このとき、ユーザUAはx=H2(SA,α,~x)を計算し、アドホック公開鍵epkIDB=（X0=P0x,XB,2=PB,2x,…,XB,β=PB,βx）を計算する。ただし、PB,i=H1(IDB,1,…,IDB,i)（1≦i<β）である。ユーザUAはアドホック公開鍵epkIDBをユーザUBに送る。
【０００９】
一方、ユーザUBは一様ランダムにアドホック秘密鍵~y∈Zpを選ぶ。このとき、ユーザUBはy=H2(SB,β,~y)を計算し、アドホック公開鍵epkIDA=（Y0=P0y,YA,2=PA,2y,…,YA,α=PA,αy）を計算する。ただし、PA,i=H1(IDA,1,…,IDA,i)（1≦i<α）である。ユーザUBはアドホック公開鍵epkIDAをユーザUAに送る。
【００１０】
続いて、ユーザUBは共有秘密情報σB,1,σB,2,σB,3を次のように計算する。
【００１１】
【数１】
2014220669.tif 000003
【００１２】
さらに、ユーザUBはセッション鍵K=H(σB,1,σB,2,σB,3,PID,IDA,IDB,epkIDB,epkIDA)を求める。ユーザUBはセッション鍵Kを出力し、処理を終了する。
【００１３】
一方、ユーザUAは共有秘密情報σA,1,σA,2,σA,3を次のように計算する。
【００１４】
【数２】
2014220669.tif 000004
【００１５】
さらに、ユーザUAはセッション鍵K=H(σA,1,σA,2,σA,3,PID,IDA,IDB,epkIDB,epkIDA)を求める。ユーザUAはセッション鍵Kを出力し、処理を終了する。
【００１６】
ユーザUAが計算する共有秘密情報σA,1,σA,2,σA,3とユーザUBが計算する共有秘密情報σB,1,σB,2,σB,3はそれぞれ等しいため、ユーザUA及びユーザUBは同一のセッション鍵Kを得ることができる。
【００１７】
共有秘密情報σA,1と共有秘密情報σB,1とが等しいことを以下に示す。
【００１８】
【数３】
2014220669.tif 000005
【００１９】
共有秘密情報σA,2と共有秘密情報σB,2とが等しいことを以下に示す。
【００２０】
【数４】
2014220669.tif 000006
【００２１】
共有秘密情報σA,3と共有秘密情報σB,3とが等しいことを以下に示す。
【００２２】
【数５】
2014220669.tif 000007
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】Atsushi Fujioka, Koutarou Suzuki, Kazuki Yoneyama, “Hierarchical ID-Based Authenticated Key Exchange Resilient to Ephemeral Key Leakage.”, IEICE Transactions 94-A(6), pp. 1306-1317, 2011.
【発明の概要】
【発明が解決しようとする課題】
【００２４】
非特許文献１に記載された従来技術では、安全性を保証するためにハッシュ関数が理想的に安全なランダムオラクルでなければならないという問題がある。しかし、ランダムオラクルは現実のハッシュ関数を用いては実現できないことが知られている。よって、ランダムオラクルを仮定せずに安全性証明が付く方式であることが望ましい。
【００２５】
また、非特許文献１に記載された従来技術では各ユーザは階層の深さ（上述の説明ではα及びβ）に依存した個数の要素を送受信する必要があり、鍵交換システムに参加するユーザ数が大規模になると通信量が爆発的に増加する。また、共有秘密情報を求める際に負荷の重いペアリング計算を実行するが、その計算回数も同様に階層の深さに比例しているため、鍵交換システムに参加するユーザ数が大規模になると計算量も爆発的に増加する。よって、通信量やペアリング計算回数が階層の深さに依存しない拡張性の高い方式が望ましい。
【００２６】
この発明は、ランダムオラクルを仮定しなくても安全性が保証され、計算量や通信量が階層の深さに依存せず拡張性が高い鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【００２７】
上記の課題を解決するために、この発明の一態様による鍵交換システムは、鍵生成装置とL階層に階層化された複数の通信装置を含む。以下では、^はべき乗を表し、・は乗算を表し、Zpは素数pを法とする剰余環とし、G,GTは双線形ペアリング関数e:G×G→GTを効率的に計算可能な群とし、gは群Gの生成元とし、Fke、Fgen、Fsig及びFkdfは擬似ランダム関数とし、FSは擬似ランダム関数の鍵空間とし、Genは任意の使いきり署名方式の署名鍵生成アルゴリズムとし、Signは任意の使いきり署名方式の署名生成アルゴリズムとし、Verは任意の使いきり署名方式の署名検証アルゴリズムとする。鍵生成装置は、値zを環Zpから選択し、値g1=gzを計算し、値g2,g3,g4,h1,…,hLを群Gから選択するパラメータ生成部と、マスタ秘密鍵MSK=g2zを計算するマスタ秘密鍵生成部と、第i階層に属する通信装置の長期秘密鍵SSKiを、値rを環Zpから選択し、値w1,w2,w3,w4,w5,w6を鍵空間FSから選択し、u0=MSK・(h1^ID1…hi^IDi・g3)r、u1=gr、u2=g4rを計算し、SSKi=(u0,u1,u2,hi+1r,…,hLr,w1,w2,w3,w4,w5,w6)として生成する長期秘密鍵生成部と、を含む。
【００２８】
通信装置は、第α階層に属し識別情報ID=（ID1,…,IDα）が設定されており、第β階層に属し識別情報ID'=（ID'1,…,ID'β）が設定された通信装置とセッション鍵SKを共有するものとする。通信装置は、値eskke,esk'ke,eskgen,esk'gen,esksig,esk'sigを鍵空間FSから選択するアドホック秘密鍵生成部と、擬似ランダム関数Fke(w1,eskke)の出力と擬似ランダム関数Fke(esk'ke,w2)の出力との排他的論理和を計算して擬似乱数sを生成し、擬似ランダム関数Fgen(w3,eskgen)の出力と擬似ランダム関数Fgen(esk'gen,w4)の出力との排他的論理和を計算して擬似乱数randgenを生成し、擬似ランダム関数Fsig(w5,esksig)の出力と擬似ランダム関数Fsig(esk'sig,w6)の出力との排他的論理和を計算して擬似乱数randsigを生成する擬似乱数生成部と、擬似乱数randgenを用いて鍵生成アルゴリズムGenを実行し、署名鍵skと検証鍵vkを生成する署名鍵生成部と、値gのs乗を計算して暗号文C1を生成し、(h1^ID'1…hβ^ID'β・g4vk・g3)sを計算して暗号文C2を生成する暗号文生成部と、暗号文C1及び暗号文C2を入力として擬似乱数randsig及び署名鍵skを用いて署名アルゴリズムSignを実行し、署名σを生成し、暗号文C1、暗号文C2、署名σ及び検証鍵vkを含むアドホック公開鍵EPKを生成するアドホック公開鍵生成部と、識別情報ID'が設定された通信装置から暗号文C'1、暗号文C'2、署名σ'及び検証鍵vk'を含むアドホック公開鍵EPK'を受信すると、暗号文C'1、暗号文C'2及び署名σ'を入力として検証鍵vk'を用いて検証アルゴリズムVerを実行し、アドホック公開鍵EPK'を検証するアドホック公開鍵検証部と、e(g1,g2)sを計算して秘密情報σ1を生成し、e(C'1,u0・u2vk')/e(C'2,u1)を計算して秘密情報σ2を生成し、e(C'1,g3)sを計算して秘密情報σ3を生成する秘密情報生成部と、識別情報ID、識別情報ID'、アドホック公開鍵EPK及びアドホック公開鍵EPK'に基づいてセッション識別情報STを生成し、秘密情報σ1及びセッション識別情報STを入力とする擬似ランダム関数Fkdfの出力と秘密情報σ2及びセッション識別情報STを入力とする擬似ランダム関数Fkdfの出力と秘密情報σ3及びセッション識別情報STを入力とする擬似ランダム関数Fkdfの出力との排他的論理和を計算し、セッション鍵SKを生成するセッション鍵生成部と、を含む。
【発明の効果】
【００２９】
この発明の鍵交換技術は、ランダムオラクルを仮定しなくても安全性証明が付き、通信装置の階層が深くなっても計算量や通信量が一定であるため拡張性が高い。
【図面の簡単な説明】
【００３０】
【図１】鍵交換システムの機能構成を例示する図である。
【図２】鍵生成装置の機能構成を例示する図である。
【図３】通信装置の機能構成を例示する図である。
【図４】鍵生成方法の処理フローを例示する図である。
【図５】鍵交換方法の処理フローを例示する図である。
【図６】鍵交換方法の処理フローを例示する図である。
【発明を実施するための形態】
【００３１】
この発明では、ランダムオラクルの代わりに擬似ランダム関数と強ランダム抽出器もしくは鍵導出関数を用いることで、ランダムオラクルを仮定すること無しに安全な方式を実現した。また、この方式では暗号文の長さとペアリング演算の計算回数が階層の深さに依存しない階層型IDベース暗号を部品として用いることにより、通信量やペアリング計算回数が階層の深さに依存せず、拡張性が高い。
【００３２】
従来技術ではセッション鍵の導出にランダムオラクルを用いていたが、この発明では強ランダム抽出器もしくは鍵導出関数で共有情報の分布をならし、その値を擬似ランダム関数の鍵とすることで出力をセッション鍵とする。このようにセッション鍵を導出する処理を変更したために、ランダムオラクルを必要としない。この手法は「Colin Boyd, Yvonne Cliff, Juan Manuel Gonzalez Nieto, Kenneth G. Paterson, “Efficient One-Round Key Exchange in the Standard Model”, ACISP 2008, pp. 69-83」などに記載されている。
【００３３】
また、この発明ではBoneh-Boyen-Goh階層型IDベース暗号（以下、BBG-HIBEと略す。）を用いて、通信量とペアリング演算の計算回数を定数にしている。具体的には、BBG-HIBE暗号の暗号文を交換し、復号したメッセージからセッション鍵を生成するようにした。また、使いきり署名を用いて暗号文に署名をすることにより、メッセージの改ざんを検知することができる。BBG-HIBEの構成法は、「Dan Boneh, Xavier Boyen, Eu-Jin Goh, “Hierarchical Identity Based Encryption with Constant Size Ciphertext”, EUROCRYPT 2005, pp. 440-456」に詳細に記載されている。
【００３４】
［実施形態］
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００３５】
〔構成〕
図１を参照して、実施形態の鍵交換システムＡの機能構成の一例を説明する。鍵交換システムＡは、鍵生成装置１及びN（≧2）台の通信装置２1,…,２Nを含む。鍵生成装置１及びN台の通信装置２1,…,２Nはネットワーク９に接続される。ネットワーク９は、鍵生成装置１とN台の通信装置２1,…,２Nそれぞれとが相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、鍵生成装置１とN台の通信装置２1,…,２Nそれぞれとは必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、鍵生成装置１が出力する情報をＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からいずれかの通信装置２n（n=1,…,N）へオフラインで入力するように構成してもよい。その他の装置間でのデータの入出力も同様であるので、具体的な説明は省略する。
【００３６】
N台の通信装置２1,…,２Nはそれぞれ識別情報ID1,…,IDNが割り当てられている。通信装置２1,…,２NはL階層に階層化されており、その階層構造は識別情報ID1,…,IDNにより表現される。例えば、第i階層の通信装置２n（1≦n≦N）に識別情報IDn=（ID1,ID2,…,IDi）が設定されているとすると、第i+1階層の通信装置２m（1≦m≦N、m≠n）には識別情報IDm=（ID1,ID2,…,IDi,IDi+1）が設定される。このように下位の階層に属する通信装置の識別情報の中に上位の階層に属するいずれかの通信装置の識別情報を含むことで階層構造が表現される。
【００３７】
図２を参照して、鍵交換システムＡに含まれる鍵生成装置１の機能構成の一例を説明する。鍵生成装置１は、パラメータ生成部１０、マスタ秘密鍵生成部１２、長期秘密鍵生成部１４、制御部１０１、メモリ１０２及び記憶部１０３を含む。鍵生成装置１は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。鍵生成装置１は制御部１０１の制御のもとで各処理を実行する。鍵生成装置１に入力されたデータや各処理で得られたデータはメモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。記憶部１０３は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００３８】
図３を参照して、鍵交換システムＡに含まれる通信装置２n（n=1,…,N）の機能構成の一例を説明する。通信装置２nは、アドホック秘密鍵生成部２０n、擬似乱数生成部２２n、署名鍵生成部２４n、暗号文生成部２６n、アドホック公開鍵生成部２８n、アドホック公開鍵検証部３０n、秘密情報生成部３２n、セッション鍵生成部３４n、制御部２０１n、メモリ２０２n及び記憶部２０３nを含む。通信装置２nは、さらに長期秘密鍵生成部３６nを含んでもよい。通信装置２nは、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。通信装置２nは制御部２０１nの制御のもとで各処理を実行する。通信装置２nに入力されたデータや各処理で得られたデータはメモリ２０２nに格納され、メモリ２０２nに格納されたデータは必要に応じて読み出されて他の処理に利用される。記憶部２０３nは、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００３９】
〔定義〕
以下に、実施形態で使用する記号の定義をする。кを正の整数のセキュリティパラメータとする。pをкビットの素数とする。G,GTをそれぞれ双線形ペアリング関数e:G×G→GTを効率的に計算可能な群とする。gを群Gの生成元とし、gT=e(g,g)とする。Zpをpを法とする剰余環とする。Lを鍵交換システムにおける階層の深さの最大値とする。
【００４０】
（Gen,Sign,Ver）を検証鍵が環Zpの要素となるような使いきり署名アルゴリズムとする。Genは署名鍵及び検証鍵を生成する署名鍵生成アルゴリズムである。Signは使いきり署名を生成する署名生成アルゴリズムである。Verは使いきり署名を検証する署名検証アルゴリズムである。この発明では任意の使いきり署名アルゴリズムを適用することができる。例えば、「Payman Mohassel, “One-Time Signatures and Chameleon Hash Functions.” Selected Areas in Cryptography 2010, pp. 302-319」に効率的な使いきり署名の構成方法が記載されている。
【００４１】
Fke:{0,1}*×FS→Zp*、Fgen:{0,1}*×FS→RSgen、Fsig:{0,1}*×FS→RSsig、Fkdf:{0,1}*×FS→{0,1}кを擬似ランダム関数とする。ただし、FSは擬似ランダム関数の鍵空間、RSgenは署名鍵生成アルゴリズムGenの乱数空間、RSsigは署名生成アルゴリズムSignの乱数空間とする。
【００４２】
〔公開パラメータ〕
図４を参照して、鍵交換システムＡが実行する公開パラメータ生成処理及び長期秘密鍵抽出処理の動作例を、実際に行われる手続きの順に従って説明する。
【００４３】
ステップＳ１０において、鍵生成装置１に含まれるパラメータ生成部１０は、値zを環Zp*から一様ランダムに選び、値g1=gzを計算し、値g2,g3,g4,h1,…hLを群Gから一様ランダムに選ぶ。続いて、パラメータ生成部１０は、公開パラメータParams=（Fke,Fgen,Fsig,Fkdf,G,GT,g,gT,g1,g2,g3,g4,h1,…hL）を生成する。
【００４４】
ステップＳ１２において、鍵生成装置１に含まれるマスタ秘密鍵生成部１２は、値g2のz乗を計算して、マスタ秘密鍵MSK=g2zを生成する。
【００４５】
〔鍵抽出処理〕
ステップＳ１４において、鍵生成装置１に含まれる長期秘密鍵生成部１４は、i=1,…,Nについて、識別情報ID=（ID1,…,IDi）を持つ通信装置２iに対して長期秘密鍵を発行する。具体的には、長期秘密鍵生成部１４は、まず、値rを環Zpから一様ランダムに選び、値w1,w2,w3,w4,w5,w6を擬似乱数空間FSから一様ランダムに選ぶ。続いて、長期秘密鍵生成部１４は、識別情報ID、値r,w1,w2,w3,w4,w5,w6、マスタ秘密鍵MSK及び公開パラメータParamsを用いて、識別情報ID=（ID1,…,IDi）に対応する長期秘密鍵SSKIDを以下のように生成する。
【００４６】
【数６】
2014220669.tif 000008
【００４７】
上位の階層（第i-1階層）に属する通信装置２mが下位の階層（第i階層）に属する通信装置２nに対して長期秘密鍵の抽出を行うように構成することもできる。この場合には、各通信装置２n（n=1,…,N）が長期秘密鍵生成部３６nを含むように構成する。例えば、上位の通信装置２mが識別情報ID’=（ID1,…,IDi-1）を持ち、その長期秘密鍵がSSKID’=（u0,u1,u2,vi,…,vL,w1,w2,w3,w4,w5,w6）であるとする。通信装置２mに含まれる長期公開鍵生成部３６mは、まず、値r’を環Zpから一様ランダムに選び、値w’1,w’2,w’3,w’4,w’5,w’6を擬似乱数空間FSから一様ランダムに選ぶ。続いて、長期秘密鍵生成部３６mは、識別情報ID’、値r’,w’1,w’2,w’3,w’4,w’5,w’6、長期秘密鍵SSKID’及び公開パラメータParamsを用いて、識別情報ID=（ID1,…,IDi）に対応する長期秘密鍵SSKIDを以下のように生成する。
【００４８】
【数７】
2014220669.tif 000009
【００４９】
いずれの方法で長期秘密鍵SSKIDを生成した場合であったとしても、生成した長期秘密鍵SSKIDは秘密裏に識別情報ID=（ID1,…,IDi）を持つ第i階層に属する通信装置２nに搬送される。長期秘密鍵SSKIDの搬送方法は、例えば、ＵＳＢメモリのような可搬型記憶媒体によりオフラインで行なってもよいし、ネットワーク９上に確立される暗号化された通信経路を用いてオンラインで行なってもよい。
【００５０】
ステップＳ２０３nにおいて、通信装置２nは、オフラインもしくはオンラインで入力された長期秘密鍵SSKIDを記憶部２０３nへ記憶する。
【００５１】
〔鍵交換処理〕
図５、図６を参照して、鍵交換システム１に含まれる二台の通信装置がセッション鍵を共有する処理フローの一例を説明する。図５の符号A1、B1は図６の符号A1、B1へ処理が継続することを表している。まず、図５を参照して処理フローの前半部分を説明する。
【００５２】
この例では、第α階層に属する識別情報IDA=（IDA,1,…,IDA,α）が割り当てられた通信装置２Aと、第β階層に属する識別情報IDB=（IDB,1,…,IDB,β）が割り当てられた通信装置２Bとの間で共通のセッション鍵SKを共有する。通信装置２Aは識別情報IDAに対応する長期秘密鍵SSKIDA=（uA,0,uA,1,uA,2,vA,α+1,…vA,L,wA,1,wA,2,wA,3,wA,4,wA,5,wA,6）を持ち、通信装置２Bは識別情報IDBに対応する長期秘密鍵SSKIDB=（uB,0,uB,1,uB,2,vB,β+1,…vB,L,wB,1,wB,2,wB,3,wB,4,wB,5,wB,6）を持つものとする。
【００５３】
ステップＳ２０Aにおいて、通信装置２Aに含まれるアドホック秘密鍵生成部２０Aは、擬似乱数空間FSから値eskA,ke,esk’A,ke,eskA,gen,esk’A,gen,eskA,sig,esk’A,sigを一様ランダムに選択し、アドホック秘密鍵ESKA=（eskA,ke,esk’A,ke,eskA,gen,esk’A,gen,eskA,sig,esk’A,sig）を生成する。
【００５４】
ステップＳ２２Aにおいて、通信装置２Aに含まれる擬似乱数生成部２２Aは、アドホック秘密鍵ESKAと公開パラメータParamsを用いて、次式により、擬似乱数sA、擬似乱数randA,gen及び擬似乱数randA,sigを計算する。
【００５５】
【数８】
2014220669.tif 000010
【００５６】
ステップＳ２４Aにおいて、通信装置２Aに含まれる署名鍵生成部２４Aは、次式により、擬似乱数randA,genを入力として署名鍵生成アルゴリズムGenを実行し、使いきり署名の署名鍵skA及び検証鍵vkAを生成する。
【００５７】
【数９】
2014220669.tif 000011
【００５８】
ステップＳ２６１Aにおいて、通信装置２Aに含まれる暗号文生成部２６Aは、群Gの生成元gと擬似乱数sAを用いて、次式により、暗号文CA,1を生成する。
【００５９】
【数１０】
2014220669.tif 000012
【００６０】
ステップＳ２６２Aにおいて、暗号文生成部２６Aは、鍵交換相手である通信装置２Bの識別情報ID=（IDB,1,…,IDB,β）、擬似乱数sA、検証鍵vkA及び公開パラメータParamsを用いて、次式により、暗号文CA,2を生成する。
【００６１】
【数１１】
2014220669.tif 000013
【００６２】
ステップＳ２８１Aにおいて、通信装置２Aに含まれるアドホック公開鍵生成部２８Aは、次式により、暗号文CA,1及び暗号文CA,2を入力として擬似乱数randA,sig及び署名鍵skAを用いて署名生成アルゴリズムSignを実行し、使いきり署名の署名σAを生成する。
【００６３】
【数１２】
2014220669.tif 000014
【００６４】
ステップＳ２８２Aにおいて、アドホック公開鍵生成部２８Aは、暗号文CA,1、暗号文CA,2、署名σA及び検証鍵vkAを用いて、アドホック公開鍵EPKA=（CA,1,CA,2,σA,vkA）を生成する。そして、アドホック公開鍵EPKA、通信装置２Aの識別情報IDA及び通信装置２Bの識別情報IDBを組として通信装置２Bへ送信する。
【００６５】
ステップＳ２０Bにおいて、通信装置２Bに含まれるアドホック秘密鍵生成部２０Bは、アドホック秘密鍵生成部２０Aと同様に、擬似乱数空間FSから値eskB,ke,esk’B,ke,eskB,gen,esk’B,gen,eskB,sig,esk’B,sigを一様ランダムに選び、アドホック秘密鍵ESKB=（eskB,ke,esk’B,ke,eskB,gen,esk’B,gen,eskB,sig,esk’B,sig）を生成する。
【００６６】
ステップＳ２２Bにおいて、通信装置２Bに含まれる擬似乱数生成部２２Bは、擬似乱数生成部２２Aと同様に、アドホック秘密鍵ESKBと公開パラメータParamsを用いて、次式により、擬似乱数sB、擬似乱数randB,gen及び擬似乱数randB,sigを計算する。
【００６７】
【数１３】
2014220669.tif 000015
【００６８】
ステップＳ２４Bにおいて、通信装置２Bに含まれる署名鍵生成部２４Bは、署名鍵生成部２４Aと同様に、次式により、擬似乱数randB,genを入力として署名鍵生成アルゴリズムGenを実行し、使いきり署名の署名鍵skB及び検証鍵vkBを生成する。
【００６９】
【数１４】
2014220669.tif 000016
【００７０】
ステップＳ２６１Bにおいて、通信装置２Bに含まれる暗号文生成部２６Bは、暗号文生成部２６Aと同様に、群Gの生成元gと擬似乱数sBを用いて、次式により、暗号文CB,1を生成する。
【００７１】
【数１５】
2014220669.tif 000017
【００７２】
ステップＳ２６２Bにおいて、暗号文生成部２６Bは、暗号文生成部２６Aと同様に、鍵交換相手である通信装置２Aの識別情報ID=（IDA,1,…,IDA,α）、擬似乱数sB、検証鍵vkB及び公開パラメータParamsを用いて、次式により、暗号文CB,2を生成する。
【００７３】
【数１６】
2014220669.tif 000018
【００７４】
ステップＳ２８１Bにおいて、通信装置２Bに含まれるアドホック公開鍵生成部２８Bは、アドホック公開鍵生成部２８Aと同様に、次式により、暗号文CB,1及び暗号文CB,2を入力として擬似乱数randB,sig及び署名鍵skBを用いて署名生成アルゴリズムSignを実行し、使いきり署名の署名σBを生成する。
【００７５】
【数１７】
2014220669.tif 000019
【００７６】
ステップＳ２８２Bにおいて、アドホック公開鍵生成部２８Bは、アドホック公開鍵生成部２８Aと同様に、暗号文CB,1、暗号文CB,2、署名σB及び検証鍵vkBを用いて、アドホック公開鍵EPKB=（CB,1,CB,2,σB,vkB）を生成する。そして、アドホック公開鍵EPKB、通信装置２Bの識別情報IDB及び通信装置２Aの識別情報IDAを組として通信装置２Aへ送信する。
【００７７】
次に、図６を参照して処理フローの後半部分を説明する。
【００７８】
ステップＳ３０Aにおいて、通信装置２Aが通信装置２Bからアドホック公開鍵EPKB、識別情報IDB及び識別情報IDAを受信すると、通信装置２Aに含まれるアドホック公開鍵検証部３０Aは、暗号文CB,1、暗号文CB,2及び署名σBを入力として検証鍵vkBを用いて署名検証アルゴリズムVerを実行し、次式が成り立つか否かを検証する。
【００７９】
【数１８】
2014220669.tif 000020
【００８０】
アドホック公開鍵検証部３０Aは、前式が成り立たない場合には、処理を中断してセッションを停止する。前式が成り立つ場合には、ステップＳ３２１A以降の処理を続行する。
【００８１】
ステップＳ３２１Aにおいて、通信装置２Aに含まれる秘密情報生成部３２Aは、アドホック秘密鍵ESKA及び公開パラメータParamsを用いて、次式により、擬似乱数sAを生成する。
【００８２】
【数１９】
2014220669.tif 000021
【００８３】
続いて、秘密情報生成部３２Aは、擬似乱数sA及び公開パラメータParamsを用いて、次式により、秘密情報σA,1を生成する。
【００８４】
【数２０】
2014220669.tif 000022
【００８５】
ステップＳ３２２Aにおいて、秘密情報生成部３２Aは、長期秘密鍵SSKA、暗号文CB,1、暗号文CB,2及び検証鍵vkBを用いて、次式により、秘密情報σA,2を生成する。
【００８６】
【数２１】
2014220669.tif 000023
【００８７】
ステップＳ３２３Aにおいて、秘密情報生成部３２Aは、暗号文CB,1、擬似乱数sA及び公開パラメータParamsを用いて、次式により、秘密情報σA,3を生成する。
【００８８】
【数２２】
2014220669.tif 000024
【００８９】
ステップＳ３４Aにおいて、通信装置２Aに含まれるセッション鍵生成部３４Aは、まず、識別情報IDA、識別情報IDB、アドホック公開鍵EPKA及びアドホック公開鍵EPKBを用いて、セッション識別情報ST=（IDA,IDB,EPKA,EPKB）を生成する。続いて、セッション鍵生成部３４Aは、秘密情報σA,1、秘密情報σA,2、秘密情報σA,3及びセッション識別情報STを用いて、次式により、セッション鍵SKを生成する。
【００９０】
【数２３】
2014220669.tif 000025
【００９１】
ステップＳ３０Bにおいて、通信装置２Bが通信装置２Aからアドホック公開鍵EPKA、識別情報IDA及び識別情報IDBを受信すると、通信装置２Bに含まれるアドホック公開鍵検証部３０Bは、アドホック公開鍵検証部３０Aと同様に、暗号文CA,1、暗号文CA,2及び署名σAを入力として検証鍵vkAを用いて署名検証アルゴリズムVerを実行し、次式が成り立つか否かを検証する。
【００９２】
【数２４】
2014220669.tif 000026
【００９３】
アドホック公開鍵検証部３０Bは、前式が成り立たない場合には、処理を中断してセッションを停止する。前式が成り立つ場合には、ステップＳ３２１B以降の処理を続行する。
【００９４】
ステップＳ３２１Bにおいて、通信装置２Bに含まれる秘密情報生成部３２Bは、秘密情報生成部３２Aと同様に、アドホック秘密鍵ESKB及び公開パラメータParamsを用いて、次式により、擬似乱数sBを生成する。
【００９５】
【数２５】
2014220669.tif 000027
【００９６】
続いて、秘密情報生成部３２Bは、長期秘密鍵SSKB、暗号文CA,1、暗号文CA,2及び検証鍵vkAを用いて、次式により、秘密情報σB,1を生成する。
【００９７】
【数２６】
2014220669.tif 000028
【００９８】
ステップＳ３２２Bにおいて、秘密情報生成部３２Bは、擬似乱数sB及び公開パラメータParamsを用いて、次式により、秘密情報σB,2を生成する。
【００９９】
【数２７】
2014220669.tif 000029
【０１００】
ステップＳ３２３Bにおいて、秘密情報生成部３２Bは、秘密情報生成部３２Aと同様に、暗号文CA,1、擬似乱数sB及び公開パラメータParamsを用いて、次式により、秘密情報σB,3を生成する。
【０１０１】
【数２８】
2014220669.tif 000030
【０１０２】
ステップＳ３４Bにおいて、通信装置２Bに含まれるセッション鍵生成部３４Bは、セッション鍵生成部３４Aと同様に、識別情報IDA、識別情報IDB、アドホック公開鍵EPKA及びアドホック公開鍵EPKBを用いて、セッション識別情報ST=（IDA,IDB,EPKA,EPKB）を生成する。続いて、セッション鍵生成部３４Bは、秘密情報σB,1、秘密情報σB,2、秘密情報σB,3及びセッション識別情報STを用いて、次式により、セッション鍵SKを生成する。
【０１０３】
【数２９】
2014220669.tif 000031
【０１０４】
秘密情報生成部３２Aが計算する秘密情報σA,1,σA,2,σA,3と秘密情報生成部３２Bが計算する秘密情報σB,1,σB,2,σB,3とはそれぞれ等しいため、通信装置２A及び通信装置２Bは同一のセッション鍵SKを得ることができる。
【０１０５】
秘密情報σA,1と秘密情報σB,1とが等しいことを以下に示す。
【０１０６】
【数３０】
2014220669.tif 000032
【０１０７】
秘密情報σA,2と秘密情報σB,2とが等しいことを以下に示す。
【０１０８】
【数３１】
2014220669.tif 000033
【０１０９】
秘密情報σA,3と秘密情報σB,3とが等しいことを以下に示す。
【０１１０】
【数３２】
2014220669.tif 000034
【０１１１】
実施形態の鍵交換システム１では、セッション鍵生成部３４が、擬似ランダム関数と強ランダム抽出器を用いてセッション鍵SKを生成する。これにより、非特許文献１に記載された従来技術のようにランダムオラクルを仮定すること無しに安全な方式を実現した。
【０１１２】
また、実施形態の鍵交換システム１では、アドホック公開鍵EPKの長さが階層の深さに依存しない。また、秘密情報生成部３２が計算するペアリング演算は階層の深さに関係なく計４回に固定されている。このように、非特許文献１に記載された従来技術のように通信量やペアリング計算回数が階層の深さに依存しないため、拡張性が高い。
【０１１３】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１１４】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１１５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１１９】
Ａ  鍵交換システム
１  鍵生成装置
２  通信装置
９  ネットワーク
１０  パラメータ生成部
１２  マスタ秘密鍵生成部
１４  長期秘密鍵生成部
２０  アドホック秘密鍵生成部
２２  擬似乱数生成部
２４  署名鍵生成部
２６  暗号文生成部
２８  アドホック公開鍵生成部
３０  アドホック公開鍵検証部
３２  秘密情報生成部
３４  セッション鍵生成部
３６  長期秘密鍵生成部
【図１】
2014220669.tif 000036
【図２】
2014220669.tif 000037
【図３】
2014220669.tif 000038
【図４】
2014220669.tif 000039
【図５】
2014220669.tif 000040
【図６】
2014220669.tif 000041