(57)【特許請求の範囲】
【請求項１】
プロトコルＩＤであるPIDを所定のビット列とし、H1:{0,1}*→G、H2:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数として、G,GTをそれぞれ双線形写像e:G×G→GTを計算可能なg,gTを生成元とする群とし、Gの単位元を1Gとし、S0=1Gとし、マスタ公開鍵P0=g,Q0=P0s0∈Gとし、ID=(ID1,ID2,…,IDt-1)に対応する情報共有装置の秘密情報をst-1∈Zpとし、その情報共有装置の長期秘密鍵を(St-1,Q1,…,Qt-1)とし、その情報共有装置の下位の情報共有装置であってID’=(ID1,ID2,…,IDt-1,IDt)に対応する情報共有装置の長期秘密鍵を(St,Q1,…,Qt)とし、Pt=H1(ID1,ID2,…,IDt-1,IDt)とし、St=St-1Ptst-1,Qt=P0stとすることにより定まる、IDA=(IDA,1,…,IDA,α)に対応する情報共有装置ＵＡの長期秘密鍵を(SA,α,QA,1,…,QA,α)、IDB=(IDB,1,…,IDB,β)に対応する情報共有装置ＵＢの長期秘密鍵を(SB,β,QB,1,…,QB,β)として、
短期秘密鍵x~1,x~2∈Zpを生成する短期秘密鍵生成部と、x1=H2(SA,α,x~1)及びx2=H2(SA,α,x~2)を計算するハッシュ値計算部と、PB,i=H1(IDB,1,…,IDB,i)(1≦i≦β)として短期公開鍵epkIDB=(X0=P0x1,XB,2=PB,2x1,…,XB,β=PB,βx1,X0’=P0x2,XB,2’=PB,2x2,…,XB,β’=PB,βx2)を計算する短期公開鍵生成部と、上記短期公開鍵epkIDBを情報共有装置ＵＢに送信する送信部と、短期公開鍵epkIDAを上記情報共有装置ＵＢから受信する受信部と、第一共有秘密情報σ1=e(Q0,PB,1)x1を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’=e(Q0,PB,1)x2を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2=e(Y0,SA,α)/Πi=2αe(QA,i-1,YA,i)を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’=e(Y0’,SA,α)/Πi=2αe(QA,i-1,YA,i’)を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3=(Y0)x1を計算する第五秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y~1,y~2∈Zpを生成する短期秘密鍵生成部と、y1=H2(SB,β,y~1)及びy2=H2(SB,β,y~2)を計算するハッシュ値計算部と、PA,i=H1(IDA,1,…,IDA,i)(1≦i≦α)として短期公開鍵epkIDA=(Y0=P0y1,YA,2=PA,2y1,…,YA,α=PA,αy1,Y0’=P0y2,YA,2’=PA,2y2,…,YA,α’=PA,αy2)を計算する短期公開鍵生成部と、上記短期公開鍵epkIDAを上記情報共有装置ＵＡに送信する送信部と、短期公開鍵epkIDBを上記情報共有装置ＵＡから受信する受信部と、第一共有秘密情報σ1=e(X0,SB,β)/Πi=2βe(QB,i-1,XB,i)を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’=e(X0’,SB,β)/Πi=2βe(QB,i-1,XB,i’)を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2=e(Q0,PA,1)y1を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’=e(Q0,PA,1)y2を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3=(X0)y1を計算する第五秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項２】
請求項１の情報共有システムにおいて、
所定の正の整数をセキュリティパラメータkとして、
上記関数Fは、ハッシュ関数H:{0,1}*→{0,1}である、
情報共有システム。
【請求項３】
プロトコルＩＤであるPIDを所定のビット列とし、H1:{0,1}*→G、H2:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数として、G,GTをそれぞれ双線形写像e:G×G→GTを計算可能なg,gTを生成元とする群とし、Gの単位元を1Gとし、S0=1Gとし、マスタ公開鍵P0=g,Q0=P0s0∈Gとし、ID=(ID1,ID2,…,IDt-1)に対応する情報共有装置の秘密情報をst-1∈Zpとし、その情報共有装置の長期秘密鍵を(St-1,Q1,…,Qt-1)とし、その情報共有装置の下位の情報共有装置であってID’=(ID1,ID2,…,IDt-1,IDt)に対応する情報共有装置の長期秘密鍵を(St,Q1,…,Qt)とし、Pt=H1(ID1,ID2,…,IDt-1,IDt)とし、St=St-1Ptst-1,Qt=P0stとすることにより定まる、IDA=(IDA,1,…,IDA,α)に対応する情報共有装置ＵＡの長期秘密鍵を(SA,α,QA,1,…,QA,α)、IDB=(IDB,1,…,IDB,β)に対応する情報共有装置ＵＢの長期秘密鍵を(SB,β,QB,1,…,QB,β)として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x~1,x~2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡのハッシュ値計算部が、x1=H2(SA,α,x~1)及びx2=H2(SA,α,x~2)を計算するハッシュ値計算ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、PB,i=H1(IDB,1,…,IDB,i)(1≦i≦β)として短期公開鍵epkIDB=(X0=P0x1,XB,2=PB,2x1,…,XB,β=PB,βx1,X0’=P0x2,XB,2’=PB,2x2,…,XB,β’=PB,βx2)を計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵epkIDBを情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y~1,y~2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢのハッシュ値計算部が、y1=H2(SB,β,y~1)及びy2=H2(SB,β,y~2)を計算するハッシュ値計算ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、PA,i=H1(IDA,1,…,IDA,i)(1≦i≦α)として短期公開鍵epkIDA=(Y0=P0y1,YA,2=PA,2y1,…,YA,α=PA,αy1,Y0’=P0y2,YA,2’=PA,2y2,…,YA,α’=PA,αy2)を計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵epkIDAを上記情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵epkIDBを上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの第一共有秘密情報計算部が、第一共有秘密情報σ1=e(X0,SB,β)/Πi=2βe(QB,i-1,XB,i)を計算する第一共有秘密情報計算ステップと、
情報共有装置ＵＢの第二共有秘密情報計算部が、第二共有秘密情報σ1’=e(X0’,SB,β)/Πi=2βe(QB,i-1,XB,i’)を計算する第二共有秘密情報計算ステップと、
情報共有装置ＵＢの第三共有秘密情報計算部が、第三共有秘密情報σ2=e(Q0,PA,1)y1を計算する第三共有秘密情報計算ステップと、
情報共有装置ＵＢの第四共有秘密情報計算部が、第四共有秘密情報σ2’=e(Q0,PA,1)y2を計算する第四共有秘密情報計算ステップと、
情報共有装置ＵＢの第五共有秘密情報計算部が、第五秘密情報計算部σ3=(X0)y1を計算する第五秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算する共有情報生成ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵epkIDAを上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの第一共有秘密情報計算部が、第一共有秘密情報σ1=e(Q0,PB,1)x1を計算する第一共有秘密情報計算ステップと、
情報共有装置ＵＡの第二共有秘密情報計算部が、第二共有秘密情報σ1’=e(Q0,PB,1)x2を計算する第二共有秘密情報計算ステップと、
情報共有装置ＵＡの第三共有秘密情報計算部が、第三共有秘密情報σ2=e(Y0,SA,α)/Πi=2αe(QA,i-1,YA,i)を計算する第三共有秘密情報計算ステップと、
情報共有装置ＵＡの第四共有秘密情報計算部が、第四共有秘密情報σ2’=e(Y0’,SA,α)/Πi=2αe(QA,i-1,YA,i’)を計算する第四共有秘密情報計算ステップと、
情報共有装置ＵＡの第五共有秘密情報計算部が、第五秘密情報計算部σ3=(Y0)x1を計算する第五秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項４】
プロトコルＩＤであるPIDを所定のビット列とし、H1:{0,1}*→G、H2:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数として、G,GTをそれぞれ双線形写像e:G×G→GTを計算可能なg,gTを生成元とする群とし、Gの単位元を1Gとし、S0=1Gとし、マスタ公開鍵P0=g,Q0=P0s0∈Gとし、ID=(ID1,ID2,…,IDt-1)に対応する情報共有装置の秘密情報をst-1∈Zpとし、その情報共有装置の長期秘密鍵を(St-1,Q1,…,Qt-1)とし、その情報共有装置の下位の情報共有装置であってID’=(ID1,ID2,…,IDt-1,IDt)に対応する情報共有装置の長期秘密鍵を(St,Q1,…,Qt)とし、Pt=H1(ID1,ID2,…,IDt-1,IDt)とし、St=St-1Ptst-1,Qt=P0stとすることにより定まる、IDA=(IDA,1,…,IDA,α)に対応する情報共有装置ＵＡの長期秘密鍵を(SA,α,QA,1,…,QA,α)、IDB=(IDB,1,…,IDB,β)に対応する情報共有装置ＵＢの長期秘密鍵を(SB,β,QB,1,…,QB,β)として、
短期秘密鍵x~1,x~2∈Zpを生成する短期秘密鍵生成部と、
x1=H2(SA,α,x~1)及びx2=H2(SA,α,x~2)を計算するハッシュ値計算部と、PB,i=H1(IDB,1,…,IDB,i)(1≦i≦β)として短期公開鍵epkIDB=(X0=P0x1,XB,2=PB,2x1,…,XB,β=PB,βx1,X0’=P0x2,XB,2’=PB,2x2,…,XB,β’=PB,βx2)を計算する短期公開鍵生成部と、上記短期公開鍵epkIDBを情報共有装置ＵＢに送信する送信部と、短期公開鍵epkIDA=(Y0=P0y1,YA,2=PA,2y1,…,YA,α=PA,αy1,Y0’=P0y2,YA,2’=PA,2y2,…,YA,α’=PA,αy2)(PA,i=H1(IDA,1,…,IDA,i)(1≦i≦α)を上記情報共有装置ＵＢから受信する受信部と、第一共有秘密情報σ1=e(Q0,PB,1)x1を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’=e(Q0,PB,1)x2を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2=e(Y0,SA,α)/Πi=2αe(QA,i-1,YA,i)を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’=e(Y0’,SA,α)/Πi=2αe(QA,i-1,YA,i’)を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3=(Y0)x1を計算する第五秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算する共有情報生成部と、を含む情報共有装置ＵＡである情報共有装置。
【請求項５】
プロトコルＩＤであるPIDを所定のビット列とし、H1:{0,1}*→G、H2:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数として、G,GTをそれぞれ双線形写像e:G×G→GTを計算可能なg,gTを生成元とする群とし、Gの単位元を1Gとし、S0=1Gとし、マスタ公開鍵P0=g,Q0=P0s0∈Gとし、ID=(ID1,ID2,…,IDt-1)に対応する情報共有装置の秘密情報をst-1∈Zpとし、その情報共有装置の長期秘密鍵を(St-1,Q1,…,Qt-1)とし、その情報共有装置の下位の情報共有装置であってID’=(ID1,ID2,…,IDt-1,IDt)に対応する情報共有装置の長期秘密鍵を(St,Q1,…,Qt)とし、Pt=H1(ID1,ID2,…,IDt-1,IDt)とし、St=St-1Ptst-1,Qt=P0stとすることにより定まる、IDA=(IDA,1,…,IDA,α)に対応する情報共有装置ＵＡの長期秘密鍵を(SA,α,QA,1,…,QA,α)、IDB=(IDB,1,…,IDB,β)に対応する情報共有装置ＵＢの長期秘密鍵を(SB,β,QB,1,…,QB,β)として、
短期秘密鍵y~1,y~2∈Zpを生成する短期秘密鍵生成部と、y1=H2(SB,β,y~1)及びy2=H2(SB,β,y~2)を計算するハッシュ値計算部と、PA,i=H1(IDA,1,…,IDA,i)(1≦i≦α)として短期公開鍵epkIDA=(Y0=P0y1,YA,2=PA,2y1,…,YA,α=PA,αy1,Y0’=P0y2,YA,2’=PA,2y2,…,YA,α’=PA,αy2)を計算する短期公開鍵生成部と、上記短期公開鍵epkIDAを上記情報共有装置ＵＡに送信する送信部と、短期公開鍵epkIDB=(X0=P0x1,XB,2=PB,2x1,…,XB,β=PB,βx1,X0’=P0x2,XB,2’=PB,2x2,…,XB,β’=PB,βx2)(PB,i=H1(IDB,1,…,IDB,i)(1≦i≦β))を上記情報共有装置ＵＡから受信する受信部と、第一共有秘密情報σ1=e(X0,SB,β)/Πi=2βe(QB,i-1,XB,i)を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’=e(X0’,SB,β)/Πi=2βe(QB,i-1,XB,i’)を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2=e(Q0,PA,1)y1を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’=e(Q0,PA,1)y2を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3=(X0)y1を計算する第五秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算する共有情報生成部と、を含む情報共有装置ＵＢである情報共有装置。
【請求項６】
請求項４又は５の情報共有装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、二者間で同じ情報を共有するための技術に関する。
【背景技術】
【０００２】
二者間でセッション鍵等の情報を共有する技術として、以下のような階層型ＩＤ鍵交換方式が知られている（例えば、非特許文献１参照。）。
【０００３】
＜公開パラメータ＞PIDをプロトコルIDとし、プロトコル仕様に対応した固有のIDとする。セキュリティパラメータをkとする。pをkビット素数とし、G,GTをそれぞれ双線形写像e:G×G→GT を効率的に計算可能なg,gTを生成元とする群とする。H1:{0,1}*→G、H2:{0,1}*→Zp、H:{0,1}*→{0,1}kをハッシュ関数とする。
【０００４】
＜鍵生成＞鍵生成アルゴリズムは、一様ランダムにマスタ秘密鍵s0∈Zpを選び、S0=1Gを設定する。1GはGの単位元である。鍵生成アルゴリズムは、マスタ公開鍵P0=g及びQ0=P0s0を計算して公開する。
【０００５】
＜鍵抽出＞ID=(ID1,…,IDt-1)に対応するユーザ装置は初期化として、st-1∈Zpを一様ランダムに選び、秘密の状態情報として保持する。同様にして他のユーザのそれぞれも、秘密の状態情報としてZpの元を一様ランダムに選択して保持する。ID=(ID1,…,IDt-1)に対応するユーザは鍵抽出者として自分の長期秘密鍵(St-1,Q1,…,Qt-1)を用いて、そのユーザの下位のユーザであってID’=(ID1,…,IDt-1,IDt)に対応するユーザ向けに次のように長期秘密鍵(St,Q1,…,Qt-1,Qt)を生成する。ここで、Pt=H1(ID1,…,IDt-1,IDt)、St=St-1Ptst-1、Qt=P0stである。
【０００６】
＜鍵交換＞以下では、ユーザUAを鍵交換セッションのイニシエータとし、ユーザUBをレスポンダとする。ユーザUAはIDA=(IDA,1,…,IDA,α)に対応する長期秘密鍵を持ち、ユーザUBはIDB=(IDB,1,…,IDB,β)に対応する長期秘密鍵を持つとする。
【０００７】
１．ユーザUAはランダムに短期秘密鍵x~∈UZpを選ぶ。このとき、ユーザ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~∈UZpを選ぶ。このとき、ユーザ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は、共有秘密情報σ1,σ2,σ3をそれぞれ次のように計算する。
【００１０】
σ1=e(X0,SB,β)/Πi=2βe(QB,i-1,XB,i)
σ2=e(Q0,PA,1)y
σ3=(X0)y
その後、ユーザUBは、セッション鍵K=H(σ1,σ2,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算して出力し、セッションを終了する。
【００１１】
３．ユーザUAは、共有秘密情報σ1,σ2,σ3をそれぞれ次のように計算する。
【００１２】
σ1=e(Q0,PB,1)x
σ2=e(Y0,SA,α)/Πi=2αe(QA,i-1,YA,i)
σ3=(Y0)x
その後、ユーザUAは、セッション鍵K=H(σ1,σ2,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算して出力し、セッションを終了する。
【００１３】
共有秘密情報には次の関係があるため、ユーザUAが計算した共有秘密情報σ1,σ2,σ3はそれぞれユーザUBが計算した共有秘密情報σ1,σ2,σ3と一致する。
【００１４】
σ1=Πi=1βe(P0,PB,i)xsi-1/Πi=2βe(P0,PB,i)xsi-1=e(Q0,PB,1)x=e(P0,PB,1)s0x
σ2=Πi=1αe(P0,PA,i)ysi-1/Πi=2αe(P0,PA,i)ysi-1=e(Q0,PA,1)y=e(P0,PA,1)s0y
σ3=(X0)y=(Y0)x=P0xy
このようにして、同一の共有情報であるセッション鍵Kが共有される。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】Atsushi Fujioka, Koutarou Suzuki, Kazuki Yoneyama, “Hierarchical ID-Based Authenticated Key Exchange Resilient to Ephemeral Key Leakage”, IWSE 2010, LNCS 6434, pp.164-180, 2010
【発明の概要】
【発明が解決しようとする課題】
【００１６】
背景技術に記載した技術では、安全性を保証するためにいわゆるギャップ問題の難しさを仮定する必要がある。ギャップ問題とは、探索問題を解くために判定オラクルの利用を許した問題のことであり、一般にいわゆる探索問題よりも解きやすい問題となる。よって、ギャップ問題の難しさを仮定するよりも、探索問題の難しさを仮定した方が仮定を弱めることができるので望ましい。
【００１７】
この発明の課題は、探索問題の難しさを仮定することにより安全性が保証される情報共有システム、方法、装置及びプログラムを提供することである。
【課題を解決するための手段】
【００１８】
この発明の一態様による情報共有システムは、プロトコルＩＤであるPIDを所定のビット列とし、H1:{0,1}*→G、H2:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数として、G,GTをそれぞれ双線形写像e:G×G→GTを計算可能なg,gTを生成元とする群とし、Gの単位元を1Gとし、S0=1Gとし、マスタ公開鍵P0=g,Q0=P0s0∈Gとし、ID=(ID1,ID2,…,IDt-1)に対応する情報共有装置の秘密情報をst-1∈Zpとし、その情報共有装置の長期秘密鍵を(St-1,Q1,…,Qt-1)とし、その情報共有装置の下位の情報共有装置であってID’=(ID1,ID2,…,IDt-1,IDt)に対応する情報共有装置の長期秘密鍵を(St,Q1,…,Qt)とし、Pt=H1(ID1,ID2,…,IDt-1,IDt)とし、St=St-1Ptst-1,Qt=P0stとすることにより定まる、IDA=(IDA,1,…,IDA,α)に対応する情報共有装置ＵＡの長期秘密鍵を(SA,α,QA,1,…,QA,α)、IDB=(IDB,1,…,IDB,β)に対応する情報共有装置ＵＢの長期秘密鍵を(SB,β,QB,1,…,QB,β)として、短期秘密鍵x~1,x~2∈Zpを生成する短期秘密鍵生成部と、x1=H2(SA,α,x~1)及びx2=H2(SA,α,x~2)を計算するハッシュ値計算部と、PB,i=H1(IDB,1,…,IDB,i)(1≦i≦β)として短期公開鍵epkIDB=(X0=P0x1,XB,2=PB,2x1,…,XB,β=PB,βx1,X0’=P0x2,XB,2’=PB,2x2,…,XB,β’=PB,βx2)を計算する短期公開鍵生成部と、短期公開鍵epkIDBを情報共有装置ＵＢに送信する送信部と、短期公開鍵epkIDAを情報共有装置ＵＢから受信する受信部と、第一共有秘密情報σ1=e(Q0,PB,1)x1を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’=e(Q0,PB,1)x2を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2=e(Y0,SA,α)/Πi=2αe(QA,i-1,YA,i)を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’=e(Y0’,SA,α)/Πi=2αe(QA,i-1,YA,i’)を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3=(Y0)x1を計算する第五秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y~1,y~2∈Zpを生成する短期秘密鍵生成部と、y1=H2(SB,β,y~1)及びy2=H2(SB,β,y~2)を計算するハッシュ値計算部と、PA,i=H1(IDA,1,…,IDA,i)(1≦i≦α)として短期公開鍵epkIDA=(Y0=P0y1,YA,2=PA,2y1,…,YA,α=PA,αy1,Y0’=P0y2,YA,2’=PA,2y2,…,YA,α’=PA,αy2)を計算する短期公開鍵生成部と、短期公開鍵epkIDAを情報共有装置ＵＡに送信する送信部と、短期公開鍵epkIDBを情報共有装置ＵＡから受信する受信部と、第一共有秘密情報σ1=e(X0,SB,β)/Πi=2βe(QB,i-1,XB,i)を計算する第一共有秘密情報計算部と、第二共有秘密情報σ1’=e(X0’,SB,β)/Πi=2βe(QB,i-1,XB,i’)を計算する第二共有秘密情報計算部と、第三共有秘密情報σ2=e(Q0,PA,1)y1を計算する第三共有秘密情報計算部と、第四共有秘密情報σ2’=e(Q0,PA,1)y2を計算する第四共有秘密情報計算部と、第五秘密情報計算部σ3=(X0)y1を計算する第五秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【発明の効果】
【００１９】
探索問題の難しさを仮定することにより安全性を保証することができる。
【図面の簡単な説明】
【００２０】
【図１】実施形態の情報共有システムの構成を説明するためのブロック図。
【図２】実施形態の情報共有装置ＵＡの構成を説明するためのブロック図。
【図３】実施形態の情報共有装置ＵＢの構成を説明するためのブロック図。
【図４】実施形態の情報共有装置ＵＡの処理を説明するためのフローチャート。
【図５】実施形態の情報共有装置ＵＢの処理を説明するためのフローチャート。
【発明を実施するための形態】
【００２１】
以下、図面を参照してこの発明の一実施形態を説明する。
【００２２】
［アルゴリズム］
まず、この発明のアルゴリズムの例について説明する。
【００２３】
＜公開パラメータ＞PIDをプロトコルIDとし、プロトコル仕様に対応した固有のIDとする。すなわち、PIDはプロトコル仕様に応じた所定のビット列である。セキュリティパラメータをkとする。kは、所定の正の整数である。pをkビット素数とし、G,GTをそれぞれ双線形写像e:G×G→GTを効率的に計算可能なg,gTを生成元とする群とする。H1:{0,1}*→G、H2:{0,1}*→Zp、H:{0,1}*→{0,1}kをハッシュ関数とする。
【００２４】
＜鍵生成＞鍵生成アルゴリズムは、一様ランダムにマスタ秘密鍵s0∈Zpを選び、S0=1Gを設定する。1GはGの単位元である。鍵生成アルゴリズムは、マスタ公開鍵P0=g及びQ0=P0s0を計算して公開する。ここで、P0の右肩の「s0」は「s0」を意味する。このように、ある文字の上付きの文字及び数字の一部がその上付きの中で更に上付き又は下付きである場合がある点に留意する。同様に、ある文字の下付きの文字及び数字の一部がその下付きの中で更に上付き又は下付きである場合がある点に留意する。
【００２５】
＜鍵抽出＞ID=(ID1,…,IDt-1)に対応するユーザ装置は初期化として、st-1∈Zpを一様ランダムに選び、秘密の状態情報として保持する。同様にして他のユーザのそれぞれも、秘密の状態情報としてZpの元を一様ランダムに選択して保持する。ID=(ID1,…,IDt-1)に対応するユーザは鍵抽出者として自分の長期秘密鍵(St-1,Q1,…,Qt-1)を用いて、そのユーザの下位のユーザであってID’=(ID1,…,IDt-1,IDt)に対応するユーザ向けに次のように長期秘密鍵(St,Q1,…,Qt-1,Qt)を生成する。ここで、Pt=H1(ID1,…,IDt-1,IDt)、St=St-1Ptst-1、Qt=P0stである。
【００２６】
＜鍵交換＞以下では、ユーザUAを鍵交換セッションのイニシエータとし、ユーザUBをレスポンダとする。ユーザUAはIDA=(IDA,1,…,IDA,α)に対応する長期秘密鍵(SA,α,QA,1,…,QA,α)を持ち、ユーザUBはIDB=(IDB,1,…,IDB,β)に対応する長期秘密鍵(SB,β,QB,1,…,QB,β)を持つとする。
【００２７】
１．ユーザUAはランダムに短期秘密鍵x~1,x~2∈UZpを選ぶ。このとき、ユーザUAは、x1=H2(SA,α,x~1)及びx2=H2(SA,α,x~2)を計算し、短期公開鍵epkIDB=(X0=P0x1,XB,2=PB,2x1,…,XB,β=PB,βx1,X0’=P0x2,XB,2’=PB,2x2,…,XB,β’=PB,βx2)を計算する。ただし、PB,i=H1(IDB,1,…,IDB,i)(1≦i≦β)である。ユーザUAは、epkIDBをユーザUBに送る。
【００２８】
２．ユーザUBはランダムに短期秘密鍵y~1,y~2∈Zpを選ぶ。このとき、ユーザUBは、y1=H2(SB,β,y~1)及びy2=H2(SB,β,y~2)を計算し、短期公開鍵epkIDA=(Y0=P0y1,YA,2=PA,2y1,…,YA,α=PA,αy1,Y0’=P0y2,YA,2’=PA,2y2,…,YA,α’=PA,αy2)を計算する。ただし、PA,i=H1(IDA,1,…,IDA,i)(1≦i≦α)である。ユーザUBは、epkIDAをユーザUAに送る。
【００２９】
ユーザUBは、共有秘密情報σ1,σ2,σ3をそれぞれ次のように計算する。
【００３０】
σ1=e(X0,SB,β)/Πi=2βe(QB,i-1,XB,i)
σ1’=e(X0’,SB,β)/Πi=2βe(QB,i-1,XB,i’)
σ2=e(Q0,PA,1)y1
σ2’=e(Q0,PA,1)y2
σ3=(X0)y1
その後、ユーザUBは、セッション鍵K=H(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算して出力し、セッションを終了する。
【００３１】
３．ユーザUAは、共有秘密情報σ1，σ1’，σ2，σ2’，σ3をそれぞれ次のように計算する。
【００３２】
σ1=e(Q0,PB,1)x1
σ1’=e(Q0,PB,1)x2
σ2=e(Y0,SA,α)/Πi=2αe(QA,i-1,YA,i)
σ2’=e(Y0’,SA,α)/Πi=2αe(QA,i-1,YA,i’)
σ3=(Y0)x1
その後、ユーザUAは、セッション鍵K=H(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算して出力し、セッションを終了する。
【００３３】
共有秘密情報には次の関係があるため、ユーザUAが計算した共有秘密情報σ1,σ1’,σ2,σ2’,σ3はそれぞれユーザUBが計算した共有秘密情報σ1,σ1’,σ2,σ2’,σ3と一致する。
【００３４】
σ1=e(P0,Πi=1βPB,isi-1)x1/Πi=2βe(P0si-1,PB,ix1)=Πi=1βe(P0,PB,i)x1si-1/Πi=2βe(P0,PB,i)x1si-1=e(Q0,PB,1)x1=e(P0,PB,1)s0x1
σ1’=e(P0,Πi=1βPB,isi-1)x2/Πi=2βe(P0si-1,PB,ix2)=Πi=1βe(P0,PB,i)x2si-1/Πi=2βe(P0,PB,i)x2si-1=e(Q0,PB,1)x2=e(P0,PB,1)s0x2
σ2=e(P0,Πi=1αPA,isi-1)y1/Πi=2αe(P0si-1,PA,iy1)=Πi=1αe(P0,PA,i)y1si-1/Πi=2αe(P0,PA,i)y1si-1=e(Q0,PA,1)y1=e(P0,PA,1)s0y1
σ2’=e(P0,Πi=1αPA,isi-1)y2/Πi=2αe(P0si-1,PA,iy2)=Πi=1αe(P0,PA,i)y2si-1/Πi=2αe(P0,PA,i)y2si-1=e(Q0,PA,1)y2=e(P0,PA,1)s0y2
σ3=(X0)y1=(Y0)x1=P0x1y1
このようにして、同一の共有情報であるセッション鍵Kが共有される。
【００３５】
［実施形態］
次に、上記［アルゴリズム］の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。情報共有装置ＵＡが［アルゴリズム］の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが［アルゴリズム］の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【００３６】
情報共有の前に、［アルゴリズム］の＜鍵抽出＞の欄で説明した方法により、マスタ秘密鍵s0及びマスタ公開鍵P0=g及びQ0=P0s0等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。また、情報共有の前に、情報共有装置ＵＡ及び情報共有装置ＵＢには、［アルゴリズム］の＜鍵抽出＞の欄で説明した方法により、ID及び秘密の状態情報及び長期秘密鍵が予め定められ、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて下記に説明する計算が行われる。
【００３７】
情報共有装置ＵＡのIDを、IDA=(IDA,1,…,IDA,α)とする。αは正の整数である。このように、IDAはα個のIDAの断片IDA,1,…,IDA,αから構成される。［アルゴリズム］の＜鍵抽出＞の欄で説明した方法により定められた情報共有装置ＵＡの長期秘密鍵を(SA,α,QA,1,…,QA,α)とする。
【００３８】
情報共有装置ＵＢのIDを、IDB=(IDB,1,…,IDB,β)とする。βは正の整数である。このように、IDBはβ個のIDBの断片IDB,1,…,IDB,βから構成される。［アルゴリズム］の＜鍵抽出＞の欄で説明した方法により定められた情報共有装置ＵＢの長期秘密鍵を(SB,β,QB,1,…,QB,β)とする。
【００３９】
情報共有装置ＵＡ及び情報共有装置ＵＢによる自分より下位の情報共有装置（ユーザ）に対する鍵の抽出、すなわち長期秘密鍵の生成は、それぞれ図２，３の鍵抽出部１１２，２１２により行われる。
【００４０】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、ハッシュ値計算部１２、短期公開鍵生成部１３、送信部１４、受信部１５、第一共有秘密情報生成部１６、第二共有秘密情報生成部１７、第三共有秘密情報生成部１８、第四共有秘密情報生成部１９、第五共有秘密情報生成部１１０、共有情報生成部１１１、鍵抽出部１１２を例えば含む。
【００４１】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、ハッシュ値計算部２２、短期公開鍵生成部２３、送信部２４、受信部２５、第一共有秘密情報生成部２６、第二共有秘密情報生成部２７、第三共有秘密情報生成部２８、第四共有秘密情報生成部２９、第五共有秘密情報生成部２１０、共有情報生成部２１１、鍵抽出部２１２を例えば含む。
【００４２】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x~1,x~2∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに２つの元を選びそれぞれ短期秘密鍵y~1,y~2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵x~1,x~2は、ハッシュ値計算部１２に送信される。
【００４３】
情報共有装置ＵＡのハッシュ値計算部１２は、短期秘密鍵x~1,x~2及び長期秘密鍵の中のSA,αを用いて、ハッシュ値x1=H2(SA,α,x~1)及びx2=H2(SA,α,x~2)を計算する（ステップＡ２）。ハッシュ値x1は、短期公開鍵生成部１３、第一共有秘密情報生成部１６、第五共有秘密情報生成部１１０に送信される。ハッシュ値x2は、短期公開鍵生成部１３、第二共有秘密情報生成部１７に送信される。
【００４４】
情報共有装置ＵＡの短期公開鍵生成部１３は、短期公開鍵epkIDB=(X0=P0x1,XB,2=PB,2x1,…,XB,β=PB,βx1,X0’=P0x2,XB,2’=PB,2x2,…,XB,β’=PB,βx2)を計算する（ステップＡ３）。ここで、PB,i=H1(IDB,1,…,IDB,i)(1≦i≦β)とする。計算された短期公開鍵epkIDBは、送信部１４に送信される。
【００４５】
情報共有装置ＵＡの送信部１４は、短期公開鍵epkIDBを情報共有装置ＵＡに送信する（ステップＡ４）。
【００４６】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y~1,y~2∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに２つの元を選びそれぞれ短期秘密鍵y~1,y~2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵y~1,y~2は、ハッシュ値計算部２２に送信される。
【００４７】
情報共有装置ＵＢのハッシュ値計算部２２は、短期秘密鍵y~1,y~2及び長期秘密鍵の中のSB,βを用いて、ハッシュ値y1=H2(SB,β,y~1)及びy2=H2(SB,β,y~2)を計算する（ステップＢ２）。ハッシュ値y1は、短期公開鍵生成部２３、第三共有秘密情報生成部２８、第五共有秘密情報生成部２１０に送信される。ハッシュ値y2は、短期公開鍵生成部２３、第四共有秘密情報生成部２９に送信される。
【００４８】
情報共有装置ＵＢの短期公開鍵生成部２３は、短期公開鍵epkIDA=(Y0=P0y1,YA,2=PA,2y1,…,YA,α=PA,αy1,Y0’=P0y2,YA,2’=PA,2y2,…,YA,α’=PA,αy2)を計算する（ステップＢ３）。ここで、PA,i=H1(IDA,1,…,IDA,i)(1≦i≦α)とする。計算された短期公開鍵epkIDAは、送信部２４に送信される。
【００４９】
情報共有装置ＵＢの送信部２４は、短期公開鍵epkIDＡを情報共有装置ＵＢに送信する（ステップＢ４）。
【００５０】
情報共有装置ＵＢの受信部２５は、短期公開鍵epkIDBを情報共有装置ＵＡから受信する（ステップＢ５）。
【００５１】
情報共有装置ＵＢの第一共有秘密情報生成部２６は、第一共有秘密情報σ1=e(X0,SB,β)/Πi=2βe(QB,i-1,XB,i)を計算する（ステップＢ６）。計算された第一共有秘密情報σ1は、共有情報生成部２１１に送信される。
【００５２】
情報共有装置ＵＢの第二共有秘密情報生成部２７は、第二共有秘密情報σ1’=e(X0’,SB,β)/Πi=2βe(QB,i-1,XB,i’)を計算する（ステップＢ７）。計算された第二共有秘密情報σ1’は、共有情報生成部２１１に送信される。
【００５３】
情報共有装置ＵＢの第三共有秘密情報生成部２８は、第三共有秘密情報σ2=e(Q0,PA,1)y1を計算する（ステップＢ８）。計算された第三共有秘密情報σ2は、共有情報生成部２１１に送信される。
【００５４】
情報共有装置ＵＢの第四共有秘密情報生成部２９は、第四共有秘密情報σ2’=e(Q0,PA,1)y2を計算する（ステップＢ９）。計算された第四共有秘密情報σ2’は、共有情報生成部２１１に送信される。
【００５５】
情報共有装置ＵＢの第五共有秘密情報生成部２１０は、第五秘密情報計算部σ3=(X0)y1を計算する（ステップＢ１０）。計算された第五秘密情報計算部σ3は、共有情報生成部２１１に送信される。
【００５６】
情報共有装置ＵＢの共有情報生成部２１１は、H(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算して、その計算結果を共有情報とする（ステップＢ１１）。
【００５７】
情報共有装置ＵＡの受信部１５（図２）は、短期公開鍵epkIDAを情報共有装置ＵＡから受信する（ステップＡ５）。
【００５８】
情報共有装置ＵＡの第一共有秘密情報生成部１６は、第一共有秘密情報σ1=e(Q0,PB,1)x1を計算する（ステップＡ６）。計算された第一共有秘密情報σ1は、共有情報生成部１１１に送信される。
【００５９】
情報共有装置ＵＡの第二共有秘密情報生成部１７は、第二共有秘密情報σ1’=e(Q0,PB,1)x2を計算する（ステップＡ７）。計算された第二共有秘密情報σ1’は、共有情報生成部１１１に送信される。
【００６０】
情報共有装置ＵＡの第三共有秘密情報生成部１８は、第三共有秘密情報σ2=e(Y0,SA,α)/Πi=2αe(QA,i-1,YA,i)（ステップＡ８）。計算された第三共有秘密情報σ2は、共有情報生成部１１１に送信される。
【００６１】
情報共有装置ＵＡの第四共有秘密情報生成部１９は、第四共有秘密情報σ2’=e(Y0’,SA,α)/Πi=2αe(QA,i-1,YA,i’)を計算する（ステップＡ９）。計算された第四共有秘密情報σ2’は、共有情報生成部１１１に送信される。
【００６２】
情報共有装置ＵＡの第五共有秘密情報生成部１１０は、第五秘密情報計算部σ3=(Y0)x1を計算する（ステップＡ１０）。計算された第五秘密情報計算部σ3は、共有情報生成部１１１に送信される。
【００６３】
情報共有装置ＵＡの共有情報生成部１１１は、H(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算して、その計算結果を共有情報とする（ステップＡ１１）。この共有情報は、例えば認証鍵として用いられる。
【００６４】
このようにして、情報共有が行われる。
【００６５】
［変形例等］
情報共有装置ＵＡの各部間のデータのやり取りは直接行われてもよいし、記憶部１０を介して行われてもよい。同様に、情報共有装置ＵＢの各部間のデータのやり取りは直接行われてもよいし、記憶部２０を介して行われてもよい。
【００６６】
上記の例では、共有情報生成部１１１及び共有情報生成部２１１は、ハッシュ関数Hを用いたが、任意の予め定められた関数Fを用いて共有情報を求めてもよい。すなわち、共有情報生成部１１１及び共有情報生成部２１１は、F(σ1,σ1’,σ2,σ2’,σ3,PID,IDA,IDB,epkIDB,epkIDA)を計算して、その計算結果を共有情報としてもよい。
【００６７】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７０】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７１】
［安全性の証明］
このように、短期秘密鍵を二重化し、共有情報を計算するための共有秘密情報であって短期秘密鍵に由来する共有秘密情報を短期秘密鍵ごとに計算する。これにより、ギャップ問題の難しさを仮定することなく探索問題の難しさをのみを仮定することで安全性を証明することができる。以下、その安全性の証明の概要を説明する。
【００７２】
まず、探索問題（探索双線形Diffie-Hellman問題）及びギャップ問題（ギャップ双線形Diffie-Hellman問題）の定義を説明する。
【００７３】
探索双線形Diffie-Hellman問題：κをセキュリティパラメータとし、Pをκビット素数とする。Gをgを生成元とする位数pの巡回群とし、GTをgTを生成元とする巡回群とする。e:G×G→GTを双線形写像とする。双線形Diffie-Hellman関数BDH:G3→GTをBDH(gu,gv,gw)=gTuvwとして定義する。解答者Sは一様ランダムに選ばれたU=gu,V=gv,W=gw,∈Gを入力され、BDH(U,V,W)の出力を試みる。解答者Sのアドバンテージを次のように定義する。
【００７４】
ADVBDH(S)=Pr[U,V,W∈G,S(g,gT,U,V,)=BDH(U; V;W)]
ADVBDH(S)が無視できない確率であるとき、解答者Sは探索双線形Diffie-Hellman 問題を解いたという。
【００７５】
ギャップ双線形Diffie-Hellman 問題：κをセキュリティパラメータとし、pをκビット素数とする。Gをgを生成元とする位数pの巡回群とし、GTをgTを生成元とする巡回群とする。e:G×G→GTを双線形写像とする。双線形Diffie-Hellman関数BDH:G3→GTをBDH(gu,gv,gw)=gTuvwとして定義し、判定双線形Diffie-Hellman述語オラクルDBDH:G3×GT→{0,1}を(gu,gv,gw,gTr)を入力としuvw=r mod pが成り立つとき1を出力し、そうでなければ0を出力する関数として定義する。解答者Sは一様ランダムに選ばれたU=gu,V=gv,W=gw∈Gと判定双線形Diffie-Hellman 述語オラクルDBDH(・,・,・,・)へのアクセスを入力され、BDH(U,V,W)の出力を試みる。解答者Sのアドバンテージを次のように定義する。
【００７６】
ADVGBDH(S)=Pr[U,V,W∈G,SDBDH(・,・,・,・)(g,U,V,W)=BDH(U,V,W)]
ADVGBDH(S)が無視できない確率であるとき、解答者Sはギャップ双線形Diffie-Hellman問題を解いたという。
【００７７】
ギャップ問題は上記のように判定オラクルのヒント付きの探索問題とみなせるので、ギャップ問題の方が真に易しい。
【００７８】
情報共有方式の安全性証明を行う際は、「ギャップ問題、もしくは探索問題を解くことが難しいことを仮定すると、情報共有方式への攻撃者が存在しない」ことを示す必要がある。これは、対偶を取ることにより、「情報共有方式への攻撃者が存在すると仮定すると、問題を解く解答者を構成できる」ことを示すことと同値である。したがって、安全性証明では実際に攻撃者から解答者を構成する必要がある。そのためには解答者は攻撃者を実際の攻撃環境と見分けがつかないように動作させなければならない。
【００７９】
既存方式では、攻撃者が出力したσ1に対してσ1=e(PB,1,Q0)xとσ2=e(PA,1,Q0)yを解答者が検証し、結果に応じて動作を変えねばならない。しかし、解答者はxとyを知ることができないので、自分で上記の検証を行うことができない。よって、判定オラクルに(PB,1,Q0,X,σ1)と(PA,1,Q0,Y,σ2)を聞き、検証式が成り立つかどうかの答えをもらうことによって証明を行う。このためギャップ問題の難しさを仮定する必要がある。上記の情報共有方式では、双線形ペアリング関数を用いた方式の場合は、w2=s-rw1に対してZ1rZ2=e(X,Y)sの真理値がZ1=e(X,Y)w1∧Z2=e(X,Y)w2の真理値と一致することを利用して検証を行う。このテクニックは落とし戸試験と呼ばれる。実施例では、任意のsとrについて、解答者は証明中でx2=s-rx1,y2=s’-r’y1と設定することでσ1rσ1’=e(PB,1,Q0)sとσ2r’σ2’=e(PA,1,Q0)s’の落とし戸試験を行うことで、σ1=e(PB,1,Q0)x1,σ1’=e(PB,1,Q0)x2,σ2=e(PA,1,Q0)y1,σ2’=e(PA,1,Q0)y2の検証をy1とx1を知ること無しに行うことができる。σ1rσ1’=e(PB,1,Q0)sとσ2r’σ2’=e(PA,1,Q0)s’は解答者の持つ情報のみで検証できるため、判定オラクルは不要であり、ギャップ問題の難しさを仮定する必要が無くなる。
【符号の説明】
【００８０】
１０    記憶部
１１    短期秘密鍵生成部
１２    ハッシュ値計算部
１３    短期公開鍵生成部
１４    送信部
１５    受信部
１６    第一共有秘密情報生成部
１７    第二共有秘密情報生成部
１８    第三共有秘密情報生成部
１９    第四共有秘密情報生成部
１１０  第五共有秘密情報生成部
１１１  共有情報生成部
１１２  鍵抽出部
２０    記憶部
２１    短期秘密鍵生成部
２２    ハッシュ値計算部
２３    短期公開鍵生成部
２４    送信部
２５    受信部
２６    第一共有秘密情報生成部
２７    第二共有秘密情報生成部
２８    第三共有秘密情報生成部
２９    第四共有秘密情報生成部
２１０  第五共有秘密情報生成部
２１１  共有情報生成部
２１２  鍵抽出部
【図１】
0005512598.tif 000002
【図２】
0005512598.tif 000003
【図３】
0005512598.tif 000004
【図４】
0005512598.tif 000005
【図５】
0005512598.tif 000006