情報共有システム、方法、装置及びプログラム
【課題】ギャップ問題ではなく探索問題の難しさを仮定することにより安全性が保証される情報共有システム、方法、装置及びプログラムを提供する。
【解決手段】長期秘密鍵又は短期秘密鍵を二重化し、共有情報を計算するための共有秘密情報であって長期秘密鍵又は短期秘密鍵に由来する共有秘密情報を短期秘密鍵ごとに計算する。これにより、ギャップ問題の難しさを仮定することなく探索問題の難しさをのみを仮定することで安全性を証明することができる。
【解決手段】長期秘密鍵又は短期秘密鍵を二重化し、共有情報を計算するための共有秘密情報であって長期秘密鍵又は短期秘密鍵に由来する共有秘密情報を短期秘密鍵ごとに計算する。これにより、ギャップ問題の難しさを仮定することなく探索問題の難しさをのみを仮定することで安全性を証明することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、二者間で同じ情報を共有するための技術に関する。
【背景技術】
【０００２】
二者間でセッション鍵等の情報を共有する技術として、以下のようなＨＭＱＶ、ＮＡＸＯＳが知られている。ＨＭＱＶの詳細については非特許文献１、ＮＡＸＯＳの詳細については非特許文献２を参照のこと。
【０００３】
『ＨＭＱＶ方式』
ＨＭＱＶは、次のような方式である。ＨＭＱＶの概要を図６に示す。
【０００４】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、H:{0,1}*→ZpとH’:{0,1}*→{0,1}kをハッシュ関数とする。
【０００５】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵A=gaを公開する。同様にユーザUBに対して、長期秘密鍵b∈Zpを計算し、長期公開鍵B=gbを公開する。
【０００６】
＜鍵交換＞長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有鍵Kを共有する。
【０００７】
１．ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、短期公開鍵をX=gxとし、ユーザUBに送る。
【０００８】
２．ユーザUBは、Xを受信し、短期秘密鍵y∈Zpをランダムに選び、短期公開鍵をY=gyとし、ユーザUAに送る。
【０００９】
ユーザUBは、d=H(X,UB)、e=H(Y,UA)、σ=(XAd)y+ebを計算し、共有鍵K=H’(σ)を得る。
【００１０】
３．ユーザUAは、Yを受信し、d=H(X,UB)、e=H(Y,UA)、σ=(YBe)x+daを計算し、共有鍵K=H’(σ)を得る。
【００１１】
共有秘密情報は両方のユーザが計算した
σ=(XAd)y+eb=(YBe)x+da=g(x+da)(y+eb)
から得られるので、両者で計算した共有鍵Kは一致する。
【００１２】
このようにして、同一の共有情報である共有鍵Kが共有される。
【００１３】
『ＮＡＸＯＳ方式』
ＮＡＸＯＳは、次のような方式である。ＮＡＸＯＳの概要を図７に示す。
【００１４】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、H:{0,1}→ZpとH’:{0,1}→{0,1}kをハッシュ関数とする。
【００１５】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵A=gaを公開する。同様にユーザUBに対して、長期秘密鍵b∈Zpを計算し、長期公開鍵B=gbを公開する。
【００１６】
＜鍵交換＞長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有鍵Kを共有する。
【００１７】
１．ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、x~=H(x,a)を計算し、短期公開鍵をX=gx~とし、ユーザUBに送る。
【００１８】
２．ユーザUBは、Xを受信し、短期秘密鍵y∈Zpをランダムに選び、y~=H(y,b)を計算し、短期公開鍵をY=gy~とし、ユーザUAに送る。
【００１９】
ユーザUBは、σ1=Ay~、σ2=Xb、σ3=Xy~を計算し、共有鍵K=H’(σ1,σ2,σ3,UA,UB)を得る。
【００２０】
３．ユーザUAは、Yを受信し、σ1=Ya、σ2=Bx~、σ3=Yx~を計算し、共有鍵K=H’(σ1,σ2,σ3,UA,UB)を得る。
【００２１】
共有秘密情報は両方のユーザが計算した
σ1=gy~a,σ2=gx~b,σ3=gx~y~
から得られるので、両者で計算した共有鍵Kは一致する。
【００２２】
このようにして、同一の共有情報である共有鍵Kが共有される。
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】Hugo Krawczyk, “HMQV: A High-Performance Secure Diffie-Hellman Protocol”, CRYPTO2005
【非特許文献２】Brian LaMacchia, Kristin Lauter, Anton Mityagin, “Stronger Security of Authenticated Key Exchange”, ProvSec2007
【発明の概要】
【発明が解決しようとする課題】
【００２４】
背景技術に記載した技術では、安全性を保証するためにいわゆるギャップ問題の難しさを仮定する必要がある。ギャップ問題とは、探索問題を解くために判定オラクルの利用を許した問題のことであり、一般にいわゆる探索問題よりも解きやすい問題となる。よって、ギャップ問題の難しさを仮定するよりも、探索問題の難しさを仮定した方が仮定を弱めることができるので望ましい。
【００２５】
この発明の課題は、探索問題の難しさを仮定することにより安全性が保証される情報共有システム、方法、装置及びプログラムを提供することである。
【課題を解決するための手段】
【００２６】
この発明の一態様による情報共有システムは、nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di,eiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵として、短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX=gxを計算する短期公開鍵生成部と、短期公開鍵Xを情報共有装置ＵＢに送信する送信部と、短期公開鍵Yを情報共有装置ＵＢから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY=gyを計算する短期公開鍵生成部と、短期公開鍵Yを情報共有装置ＵＡに送信する送信部と、短期公開鍵Xを情報共有装置ＵＡから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【００２７】
この発明の一態様による情報共有システムは、nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di1,di2,ei1,ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gaを情報共有装置ＵＢの長期公開鍵として、短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX1=gx1,X2=gx2を計算する短期公開鍵生成部と、短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY1=gy1,Y2=gy2を計算する短期公開鍵生成部と、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を情報共有装置ＵＡから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【００２８】
この発明の一態様による情報共有システムは、H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBは情報共有装置ＵＢに対応する所定の値とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、x~1=H(x,a1),x~2=H(x,a2)を計算するハッシュ値計算部と、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する受信部と、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、y~1=H(y,b1),y~2=H(y,b2)を計算するハッシュ値計算部と、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成部と、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を情報共有装置ＵＡから受信する受信部と、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【００２９】
この発明の一態様による情報共有システムは、H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gbを情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、x~1=H(x1,a)、x~2=H(x2,a)を計算するハッシュ値計算部と、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する受信部と、σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成部と、y~1=H(y1,b)、y~2=H(y2,b)を計算するハッシュ値計算部と、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成部と、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を情報共有装置ＵＡから受信する受信部と、σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【発明の効果】
【００３０】
探索問題の難しさを仮定して安全性を保証することができる。
【図面の簡単な説明】
【００３１】
【図１】情報共有システムの構成を説明するためのブロック図。
【図２】情報共有装置ＵＡの構成を説明するためのブロック図。
【図３】情報共有装置ＵＢの構成を説明するためのブロック図。
【図４】情報共有装置ＵＡの処理を説明するためのフローチャート。
【図５】情報共有装置ＵＢの処理を説明するためのフローチャート。
【図６】従来のＨＭＱＶの概要を説明するための図。
【図７】長期鍵二重化ＨＭＱＶの概要を説明するための図。
【図８】短期鍵二重化ＨＭＱＶの概要を説明するための図。
【図９】従来のＮＡＸＯＳの概要を説明するための図。
【図１０】長期鍵二重化ＮＡＸＯＳの概要を説明するための図。
【図１１】短期鍵二重化ＮＡＸＯＳの概要を説明するための図。
【発明を実施するための形態】
【００３２】
以下、図面を参照してこの発明の一実施形態を説明する。
【００３３】
［第一実施形態］
まず、第一実施形態のアルゴリズムである長期鍵二重化ＨＭＱＶについて説明する。
【００３４】
『長期鍵二重化ＨＭＱＶ』
長期鍵二重化ＨＭＱＶは、次のような方式である。長期鍵二重化ＨＭＱＶの概要を図７に示す。
【００３５】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、Hi:{0,1}*→Zp及びH’:{0,1}*→{0,1}kをハッシュ関数とする。kは、セキュリティパラメータであり正の整数である。また、1≦i≦nでありnは正の整数である。
【００３６】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a1,a2∈Zpを計算し、長期公開鍵A1=ga1,A2=ga2を公開する。
【００３７】
ga1の右肩の「a1」は「a1」を意味する。このように、この明細書、特許請求の範囲及び図面において、ある文字の上付きの文字及び数字の一部がその上付きの中で更に上付き又は下付きである場合がある点に留意する。同様に、ある文字の下付きの文字及び数字の一部がその下付きの中で更に上付き又は下付きである場合がある点に留意する。
【００３８】
鍵生成者は、同様にユーザUBに対して、長期秘密鍵b1,b2∈Zpを計算し、長期公開鍵B1=gb1,B2=gb2を公開する。
【００３９】
＜鍵交換＞長期秘密鍵a1,a2をもつユーザUAと、長期秘密鍵b1,b2をもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。
【００４０】
１．ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、短期公開鍵をX=gxとし、ユーザUBに送る。
【００４１】
２．ユーザUBは、Xを受信し、短期秘密鍵y∈Zpをランダムに選び、短期公開鍵をY=gyとし、ユーザUAに送る。
【００４２】
ユーザUBは、1≦i≦nについて、di=Hi(X,UB)、ei=Hi(Y,UA)、σi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算し、共有情報K=H’(σ11,σ11’, σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を得る。ただし、nは正の整数。diとeiは、di=Hi(X,UB)、ei=Hi(Y,UA)以外の事前に定められた定数であっても良い。
【００４３】
３．ユーザUAは、Yを受信し、1≦i≦nについて、di=Hi(X,UB)、ei=Hi(Y,UA)、σi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算し、共有情報K=H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を得る。diとeiは、di=Hi(X,UB)、ei=Hi(Y,UA)以外の事前に定められた定数であっても良い。
【００４４】
共有秘密情報は両方のユーザが計算した
σi1=g(x+dia1)(y+eib1),σi1’=g(x+dia1)(y+eib2),σi2=g(x+dia2)(y+eib1),σi2’=g(x+dia2)(y+eib2)
から得られるので、両者で計算した共有情報Kは一致する。
【００４５】
次に、上記『長期鍵二重化ＨＭＱＶ』の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。
【００４６】
情報共有装置ＵＡが『長期鍵二重化ＨＭＱＶ』の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが『長期鍵二重化ＨＭＱＶ』の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【００４７】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、短期公開鍵生成部１２、送信部１３、受信部１４、共有秘密情報生成部１５、共有情報生成部１６を例えば含む。
【００４８】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、短期公開鍵生成部２２、送信部２３、受信部２４、共有秘密情報生成部２５、共有情報生成部２６を例えば含む。
【００４９】
情報共有の前に、ハッシュ関数Hi、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。
【００５０】
また、情報共有の前に、情報共有装置ＵＡには、長期秘密鍵a1,a2及び長期公開鍵A1,A2が予め定められ、必要に応じて記憶部１０に記憶されているものとする。同様に、情報共有の前に、情報共有装置ＵＢには、長期秘密鍵b1,b2及び長期公開鍵B1,B2が予め定められ、必要に応じて記憶部１０に記憶されているものとする。長期秘密鍵a1,a2,b1,b2及び長期公開鍵A1,A2,B1,B2の計算は、鍵生成装置３（図１）により行われる。
【００５１】
これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。
【００５２】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵xとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵xは、短期公開鍵生成部１２に送信される。
【００５３】
情報共有装置ＵＡの短期公開鍵生成部１２は、短期秘密鍵xを用いて短期公開鍵X=gxを計算する（ステップＡ２）。短期公開鍵Xは、共有秘密情報生成部１５及び送信部１３に送信される。
【００５４】
情報共有装置ＵＡの送信部１３は、短期公開鍵Xを情報共有装置ＵＢに送信する（ステップＡ３）。
【００５５】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵yとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、短期公開鍵生成部２２に送信される。
【００５６】
情報共有装置ＵＢの短期公開鍵生成部２２は、短期秘密鍵yを用いて短期公開鍵Y=gyを計算する（ステップＢ２）。短期公開鍵Yは、共有秘密情報生成部２５及び送信部２３に送信される。
【００５７】
情報共有装置ＵＢの送信部２３は、短期公開鍵Yを情報共有装置ＵＡに送信する（ステップＢ４）。
【００５８】
情報共有装置ＵＢの受信部２４は、短期公開鍵Xを情報共有装置ＵＡから受信する（ステップＢ５）。
【００５９】
情報共有装置ＵＢの共有秘密情報生成部２５は、1≦i≦nのそれぞれのiについての共有秘密情報σi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算する（ステップＢ６）。すなわち、計4n個の共有秘密情報σ11，σ11’,σ21，σ21’,…σ1n，σ1n’,σ2n，σ2n’を計算する。計算された共有秘密情報は、共有情報生成部２６に送信される。
【００６０】
ここで、di及びeiは、所定の定数である。例えば、di=Hi(X,UB),ei=Hi(Y,UA)である。第一実施形態の情報共有装置ＵＢは、補助情報di=Hi(X,UB)、ei=Hi(Y,UA)を計算する補助情報生成部２８を有していても良い。
【００６１】
情報共有装置ＵＢの共有情報生成部２６は、H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算して、その計算結果を共有情報Kとする（ステップＢ７）。この共有情報Kは、例えば認証鍵として用いられる。
【００６２】
情報共有装置ＵＡの受信部１４（図２）は、短期公開鍵Yを情報共有装置ＵＢから受信する（ステップＡ４）。
【００６３】
情報共有装置ＵＡの共有秘密情報生成部１５は、1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する（ステップＡ５）。すなわち、計4n個の共有秘密情報σ11，σ11’,σ21，σ21’,…σ1n，σ1n’,σ2n，σ2n’を計算する。計算された共有秘密情報は、共有情報生成部１６に送信される。
【００６４】
ここで、di及びeiは、所定の定数である。例えば、di=Hi(X,UB),ei=Hi(Y,UA)である。第一実施形態の情報共有装置ＵＡは、補助情報di=Hi(X,UB)、ei=Hi(Y,UA)を計算する補助情報生成部１８を有していても良い。
【００６５】
情報共有装置ＵＡの共有情報生成部１６は、H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算して、その計算結果を共有情報Kとする（ステップＡ６）。この共有情報Kは、例えば認証鍵として用いられる。
【００６６】
このようにして、情報共有が行われる。
【００６７】
［第二実施形態］
まず、第二実施形態のアルゴリズムである長期鍵二重化ＨＭＱＶについて説明する。
【００６８】
『短期鍵二重化ＨＭＱＶ』
短期鍵二重化ＨＭＱＶは、次のような方式である。短期鍵二重化ＨＭＱＶの概要を図８に示す。
【００６９】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、Hi:{0,1}*→Zp及びH’:{0,1}*→{0,1}kをハッシュ関数とする。kは、セキュリティパラメータであり正の整数である。また、1≦i≦nでありnは正の整数である。
【００７０】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵A=gaを公開する。
【００７１】
＜鍵交換＞長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。
【００７２】
１．ユーザUAは、短期秘密鍵x1,x2∈Zpをランダムに選び、短期公開鍵をX1=gx1,X2=gx2とし、ユーザUBに送る。
【００７３】
２．ユーザUBは、X1,X2を受信し、短期秘密鍵y1,y2∈Zpをランダムに選び、短期公開鍵をY1=gy1,Y2=gy2とし、ユーザUAに送る。
【００７４】
ユーザUBは、1≦i≦nについて、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)、σi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算し、共有情報K=H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を得る。ただし、nは正の整数。di1,di2,ei1,ei2は、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)以外の事前に定められた定数であっても良い。
【００７５】
３．ユーザUAは、Y1,Y2を受信し、1≦i≦nについて、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)、σi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算し、共有鍵K=H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を得る。ただし、nは正の整数。di1,di2,ei1,ei2は、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)以外の事前に定められた定数であっても良い。
【００７６】
共有秘密情報は両方のユーザが計算した
σi1=g(x1+di1a)(y1+ei1b),σi1’=g(x1+di1a)(y2+ei2b),σi2=g(x2+di2a)(y1+ei1b),σi2’=g(x2+di2a)(y2+ei2b)
から得られるので、両者で計算した共有情報Kは一致する。
【００７７】
次に、上記『短期鍵二重化ＨＭＱＶ』の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。
【００７８】
情報共有装置ＵＡが『短期鍵二重化ＨＭＱＶ』の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが『短期鍵二重化ＨＭＱＶ』の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【００７９】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、短期公開鍵生成部１２、送信部１３、受信部１４、共有秘密情報生成部１５、共有情報生成部１６を例えば含む。
【００８０】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、短期公開鍵生成部２２、送信部２３、受信部２４、共有秘密情報生成部２５、共有情報生成部２６を例えば含む。
【００８１】
情報共有の前に、ハッシュ関数Hi、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。
【００８２】
また、情報共有の前に、情報共有装置ＵＡには、長期秘密鍵a及び長期公開鍵Aが予め定められ、必要に応じて記憶部１０に記憶されているものとする。同様に、情報共有の前に、情報共有装置ＵＢには、長期秘密鍵b及び長期公開鍵Bが予め定められ、必要に応じて記憶部１０に記憶されているものとする。長期秘密鍵a,b及び長期公開鍵A,Bの計算は、鍵生成装置３（図１）により行われる。
【００８３】
これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。
【００８４】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x1,x2∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに２つの元を選びそれぞれ短期秘密鍵x1,x2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵x1,x2は、短期公開鍵生成部１２に送信される。
【００８５】
情報共有装置ＵＡの短期公開鍵生成部１２は、短期秘密鍵x1,x2を用いて短期公開鍵X1=gx1,X2=gx2を計算する（ステップＡ２）。短期公開鍵X1,X2は、共有秘密情報生成部１５及び送信部１３に送信される。
【００８６】
情報共有装置ＵＡの送信部１３は、短期公開鍵X1,X2を情報共有装置ＵＢに送信する（ステップＡ３）。
【００８７】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y1,y2∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに２つの元を選びそれぞれ短期秘密鍵y1,y2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、短期公開鍵生成部２２に送信される。
【００８８】
情報共有装置ＵＢの短期公開鍵生成部２２は、短期秘密鍵y1,y2を用いて短期公開鍵Y1=gy1,Y2=gy2を計算する（ステップＢ２）。短期公開鍵Y1=gy1,Y2=gy2は、共有秘密情報生成部２５及び送信部２３に送信される。
【００８９】
情報共有装置ＵＢの送信部２３は、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する（ステップＢ４）。
【００９０】
情報共有装置ＵＢの受信部２４は、短期公開鍵X1,X2を情報共有装置ＵＡから受信する（ステップＢ５）。
【００９１】
情報共有装置ＵＢの共有秘密情報生成部２５は、1≦i≦nのそれぞれのiについての共有秘密情報σi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算する（ステップＢ６）。すなわち、計4n個の共有秘密情報σ11，σ11’,σ21，σ21’,…σ1n，σ1n’,σ2n，σ2n’を計算する。計算された共有秘密情報は、共有情報生成部２６に送信される。
【００９２】
ここで、di1,di2,ei1,ei2は、所定の定数である。例えば、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)である。第二実施形態の情報共有装置ＵＢは、補助情報di=Hi(X,UB)、ei=Hi(Y,UA)を計算する補助情報生成部２８を有していても良い。
【００９３】
情報共有装置ＵＢの共有情報生成部２６は、H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算して、その計算結果を共有情報Kとする（ステップＢ７）。この共有情報Kは、例えば認証鍵として用いられる。
【００９４】
情報共有装置ＵＡの受信部１４（図２）は、短期公開鍵Yを情報共有装置ＵＢから受信する（ステップＡ４）。
【００９５】
情報共有装置ＵＡの共有秘密情報生成部１５は、1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する（ステップＡ５）。すなわち、計4n個の共有秘密情報σ11，σ11’,σ21，σ21’,…σ1n，σ1n’,σ2n，σ2n’を計算する。計算された共有秘密情報は、共有情報生成部１６に送信される。
【００９６】
ここで、di1,di2,ei1,ei2は、所定の定数である。例えば、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)である。第二実施形態の情報共有装置ＵＡは、補助情報di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)を計算する補助情報生成部１８を有していても良い。
【００９７】
情報共有装置ＵＡの共有情報生成部１６は、H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算して、その計算結果を共有情報Kとする（ステップＡ６）。この共有情報Kは、例えば認証鍵として用いられる。
【００９８】
このようにして、情報共有が行われる。
【００９９】
［第三実施形態］
まず、第三実施形態のアルゴリズムである長期鍵二重化ＮＡＸＯＳについて説明する。
【０１００】
『長期鍵二重化ＮＡＸＯＳ』
長期鍵二重化ＮＡＸＯＳは、次のような方式である。長期鍵二重化ＮＡＸＯＳの概要を図９に示す。
【０１０１】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、H:{0,1}*→Zp及びH’:{0,1}*→{0,1}kをハッシュ関数とする。
【０１０２】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a1,a2∈Zpを計算し、長期公開鍵A1=ga1,A2=ga2を公開する。鍵生成者は、同様にユーザUBに対して、長期秘密鍵b1,b2∈Zpを計算し、長期公開鍵B1=gb1,B2=gb2を公開する。
【０１０３】
＜鍵交換＞長期秘密鍵a1,a2をもつユーザUAと、長期秘密鍵b1,b2をもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。
【０１０４】
１．ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、x~1=H(x,a1),x~2=H(x,a2)を計算し、短期公開鍵をX1=gx~1,X2=gx~2とし、ユーザUBに送る。
【０１０５】
２．ユーザUBは、X1,X2を受信し、短期秘密鍵y∈Zpをランダムに選び、y~1=H(y,b1), y~2=H(y,b2)を計算し、短期公開鍵をY1=gy~1,Y2=gy~2とし、ユーザUAに送る。
【０１０６】
ユーザUBは、σ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算し、K=H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を得る。
【０１０７】
UAは、ユーザUA（情報共有装置ＵＡ）に対応する所定の値である。同様に、UBは、ユーザUB（情報共有装置ＵＢ）に対応する所定の値である。
【０１０８】
３．ユーザUAは、Yを受信し、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算し、共有情報K=H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を得る。
【０１０９】
共有秘密情報は両方のユーザが計算した
σ1=gy~1a1,σ1’=gy~1a2,σ2=gy~2a1,σ2’=gy~2a2,σ3=gx~1b1,σ3’=gx~1b2,σ4=gx~2b1,σ4’=gx~2b2,σ5=gx~1y~1,σ5’=gx~1y~2,σ6=gx~2y~1,σ6’=gx~2y~2から得られるので、両者で計算した共有鍵K は一致する。
【０１１０】
次に、上記『長期鍵二重化ＮＡＸＯＳ』の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。
【０１１１】
情報共有装置ＵＡが『長期鍵二重化ＮＡＸＯＳ』の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが『長期鍵二重化ＮＡＸＯＳ』の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【０１１２】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、短期公開鍵生成部１２、送信部１３、受信部１４、共有秘密情報生成部１５、共有情報生成部１６、破線で示したハッシュ値計算部１７を例えば含む。
【０１１３】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、短期公開鍵生成部２２、送信部２３、受信部２４、共有秘密情報生成部２５、共有情報生成部２６、破線で示したハッシュ値計算部２７を例えば含む。
【０１１４】
情報共有の前に、ハッシュ関数H、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。
【０１１５】
また、情報共有の前に、情報共有装置ＵＡには、長期秘密鍵a1,a2及び長期公開鍵A1,A2が予め定められ、必要に応じて記憶部１０に記憶されているものとする。同様に、情報共有の前に、情報共有装置ＵＢには、長期秘密鍵b1,b2及び長期公開鍵B1,B2が予め定められ、必要に応じて記憶部１０に記憶されているものとする。長期秘密鍵a1,a2,b1,b2及び長期公開鍵A1,A2,B1,B2の計算は、鍵生成装置３（図１）により行われる。
【０１１６】
これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。
【０１１７】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵xとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵xは、ハッシュ値計算部１７に送信される。
【０１１８】
情報共有装置ＵＡのハッシュ値計算部１７は、x~1=H(x,a1),x~2=H(x,a2)を計算する（ステップＡ７）。計算されたハッシュ値x~1,x~2は、短期公開鍵生成部１２及び共有秘密情報生成部１５に送信される。
【０１１９】
情報共有装置ＵＡの短期公開鍵生成部１２は、計算されたハッシュ値x~1,x~2をそれぞれ用いて短期公開鍵X1=gx~1,X2=gx~2を計算する（ステップＡ２）。短期公開鍵X1,X2は、共有秘密情報生成部１５及び送信部１３に送信される。
【０１２０】
情報共有装置ＵＡの送信部１３は、短期公開鍵X1,X2を情報共有装置ＵＢに送信する（ステップＡ３）。
【０１２１】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵yとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、ハッシュ値計算部２７に送信される。
【０１２２】
情報共有装置ＵＢのハッシュ値計算部２７は、y~1=H(y,b1),y~2=H(y,b2)を計算する。計算されたハッシュ値y~1,y~2は、短期公開鍵生成部２２及び共有秘密情報生成部２５に送信される。
【０１２３】
情報共有装置ＵＢの短期公開鍵生成部２２は、ハッシュ値y~1,y~2をそれぞれ用いて短期公開鍵Y1=gy~1,Y2=gy~2を計算する（ステップＢ７）。短期公開鍵Y1,Y2は、共有秘密情報生成部２５及び送信部２３に送信される。
【０１２４】
情報共有装置ＵＢの送信部２３は、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する（ステップＢ４）。
【０１２５】
情報共有装置ＵＢの受信部２４は、短期公開鍵X1,X2を情報共有装置ＵＡから受信する（ステップＢ５）。
【０１２６】
情報共有装置ＵＢの共有秘密情報生成部２５は、１２個の共有秘密情報σ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算する（ステップＢ６）。計算された共有秘密情報は、共有情報生成部２６に送信される。
【０１２７】
情報共有装置ＵＢの共有情報生成部２６は、H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算して、その計算結果を共有情報Kとする（ステップＢ７）。この共有情報Kは、例えば認証鍵として用いられる。
【０１２８】
情報共有装置ＵＡの受信部１４（図２）は、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する（ステップＡ４）。
【０１２９】
情報共有装置ＵＡの共有秘密情報生成部１５は、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する（ステップＡ５）。計算された共有秘密情報は、共有情報生成部１６に送信される。
【０１３０】
情報共有装置ＵＡの共有情報生成部１６は、H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算して、その計算結果を共有情報Kとする（ステップＡ６）。この共有情報Kは、例えば認証鍵として用いられる。
【０１３１】
このようにして、情報共有が行われる。
【０１３２】
［第四実施形態］
まず、第四実施形態のアルゴリズムである短期鍵二重化ＮＡＸＯＳについて説明する。
【０１３３】
『短期鍵二重化ＮＡＸＯＳ』
短期鍵二重化ＮＡＸＯＳは、次のような方式である。短期鍵二重化ＮＡＸＯＳの概要を図１０に示す。
【０１３４】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、H:{0,1}*→Zp及びH’:{0,1}*→{0,1}kをハッシュ関数とする。
【０１３５】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵A=gaを公開する。同様に、鍵生成者は、ユーザUBに対して、長期秘密鍵b∈Zpを計算し、長期公開鍵B=gbを公開する。
【０１３６】
＜鍵交換＞長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。
【０１３７】
１．ユーザUAは、短期秘密鍵x1,x2∈Zpをランダムに選び、x~1=H(x1,a)、x~2=H(x2,a)を計算し、短期公開鍵をX1=gx~1,X2=gx~2とし、ユーザUBに送る。
【０１３８】
２．ユーザUBは、X1,X2を受信し、短期秘密鍵y1,y2∈Zpをランダムに選び、y~1=H(y1,b)、y~2=H(y2,b)を計算し、短期公開鍵をY1=gy~1,Y2=gy~2とし、ユーザUAに送る。
【０１３９】
ユーザUBは、σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算し、共有情報K=H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を得る。
【０１４０】
UAは、ユーザUA（情報共有装置ＵＡ）に対応する所定の値である。同様に、UBは、ユーザUB（情報共有装置ＵＢ）に対応する所定の値である。
【０１４１】
３．ユーザUAは、Y1,Y2を受信し、σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算し、共有情報K=H′(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を得る。
【０１４２】
共有秘密情報は両方のユーザが計算した
σ1=gy~1a,σ1’=gy~2a,σ2=gx~1b,σ2’=gx~2b,σ3=gx~1y~1,σ3’=gx~2y~1,σ4=gx~1y~2,σ4’=gx~2y~2
から得られるので、両者で計算した共有情報Kは一致する。
【０１４３】
次に、上記『短期鍵二重化ＮＡＸＯＳ』の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。
【０１４４】
情報共有装置ＵＡが『短期鍵二重化ＮＡＸＯＳ』の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが『短期鍵二重化ＮＡＸＯＳ』の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【０１４５】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、短期公開鍵生成部１２、送信部１３、受信部１４、共有秘密情報生成部１５、共有情報生成部１６、破線で示したハッシュ値計算部１７を例えば含む。
【０１４６】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、短期公開鍵生成部２２、送信部２３、受信部２４、共有秘密情報生成部２５、共有情報生成部２６、破線で示したハッシュ値計算部２７を例えば含む。
【０１４７】
情報共有の前に、ハッシュ関数H、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。
【０１４８】
また、情報共有の前に、情報共有装置ＵＡには、長期秘密鍵a及び長期公開鍵Aが予め定められ、必要に応じて記憶部１０に記憶されているものとする。同様に、情報共有の前に、情報共有装置ＵＢには、長期秘密鍵b及び長期公開鍵Bが予め定められ、必要に応じて記憶部１０に記憶されているものとする。長期秘密鍵a,b及び長期公開鍵A,Bの計算は、鍵生成装置３（図１）により行われる。
【０１４９】
これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。
【０１５０】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x1,x2∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに２つの元を選びそれぞれ短期秘密鍵x1,x2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵x1,x2は、ハッシュ値計算部１７に送信される。
【０１５１】
情報共有装置ＵＡのハッシュ値計算部１７は、x~1=H(x1,a),x~2=H(x2,a)を計算する（ステップＡ７）。計算されたハッシュ値x~1,x~2は、短期公開鍵生成部１２及び共有秘密情報生成部１５に送信される。
【０１５２】
情報共有装置ＵＡの短期公開鍵生成部１２は、計算されたハッシュ値x~1,x~2をそれぞれ用いて短期公開鍵X1=gx~1,X2=gx~2を計算する（ステップＡ２）。短期公開鍵X1,X2は、共有秘密情報生成部１５及び送信部１３に送信される。
【０１５３】
情報共有装置ＵＡの送信部１３は、短期公開鍵X1,X2を情報共有装置ＵＢに送信する（ステップＡ３）。
【０１５４】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y1,y2∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに２つの元を選び短期秘密鍵y1,y2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵y1,y2は、ハッシュ値計算部２７に送信される。
【０１５５】
情報共有装置ＵＢのハッシュ値計算部２７は、y~1=H(y1,b),y~2=H(y2,b)を計算する。計算されたハッシュ値y~1,y~2は、短期公開鍵生成部２２及び共有秘密情報生成部２５に送信される。
【０１５６】
情報共有装置ＵＢの短期公開鍵生成部２２は、ハッシュ値y~1,y~2をそれぞれ用いて短期公開鍵Y1=gy~1,Y2=gy~2を計算する（ステップＢ７）。短期公開鍵Y1,Y2は、共有秘密情報生成部２５及び送信部２３に送信される。
【０１５７】
情報共有装置ＵＢの送信部２３は、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する（ステップＢ４）。
【０１５８】
情報共有装置ＵＢの受信部２４は、短期公開鍵X1,X2を情報共有装置ＵＡから受信する（ステップＢ５）。
【０１５９】
情報共有装置ＵＢの共有秘密情報生成部２５は、計８個の共有秘密情報σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算する（ステップＢ６）。計算された共有秘密情報は、共有情報生成部２６に送信される。
【０１６０】
情報共有装置ＵＢの共有情報生成部２６は、H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算して、その計算結果を共有情報Kとする（ステップＢ７）。この共有情報Kは、例えば認証鍵として用いられる。
【０１６１】
情報共有装置ＵＡの受信部１４（図２）は、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する（ステップＡ４）。
【０１６２】
情報共有装置ＵＡの共有秘密情報生成部１５は、σ1=Y1a~1、σ1’=Y1a~2、σ2=Y2a~1、σ2’=Y2a~2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する（ステップＡ５）。計算された共有秘密情報は、共有情報生成部１６に送信される。
【０１６３】
情報共有装置ＵＡの共有情報生成部１６は、H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算して、その計算結果を共有情報Kとする（ステップＡ６）。この共有情報Kは、例えば認証鍵として用いられる。
【０１６４】
このようにして、情報共有が行われる。
【０１６５】
［変形例等］
情報共有装置ＵＡの各部間のデータのやり取りは直接行われてもよいし、記憶部１０を介して行われてもよい。同様に、情報共有装置ＵＢの各部間のデータのやり取りは直接行われてもよいし、記憶部２０を介して行われてもよい。
【０１６６】
上記の例では、共有情報生成部１６及び共有情報生成部２６は、ハッシュ関数H’を用いたが、任意の予め定められた関数Fを用いて共有情報を求めてもよい。すなわち、第一実施形態及び第二実施形態においてはF(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算してその計算結果を共有情報kとしても良いし、第三実施形態においてはF(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算してその計算結果を共有情報kとしても良いし、第四実施形態においては、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算してその計算結果を共有情報kとしても良い。
【０１６７】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１６８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１６９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１７０】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１７１】
［安全性の証明］
このように、長期秘密鍵又は短期秘密鍵を二重化し、共有情報を計算するための共有秘密情報であって長期秘密鍵又は短期秘密鍵に由来する共有秘密情報を短期秘密鍵ごとに計算する。これにより、ギャップ問題の難しさを仮定することなく探索問題の難しさをのみを仮定することで安全性を証明することができる。以下、その安全性の証明の概要を説明する。
【０１７２】
まず、探索問題（探索Diffie-Hellman問題）及びギャップ問題（ギャップDiffie-Hellman問題）の定義を説明する。
【０１７３】
探索Diffie-Hellman問題：κをセキュリティパラメータとし、pをκビット素数とする。Gをgを生成元とする位数pの巡回群とする。Diffie-Hellman関数CDH:G2→GをCDH(gu,gv)=guvとして定義し、判定Diffie-Hellman述語オラクルDDH:G3→{0,1}を(gu,gv,gw)を入力としuv=w mod pが成り立つとき1を出力し、そうでなければ0を出力する関数として定義する。
【０１７４】
解答者Sは、一様ランダムに選ばれたU=gu,V=gv∈Gと判定Diffie-Hellman述語オラクルDDH(・,・,・)へのアクセスを入力され、CDH(U,V)の出力を試みる。解答者Sのアドバンテージを次のように定義する。
【０１７５】
ADVGDH(S)=Pr[U,V∈G,SDDH(・,・,・)(g,U,V)=CDH(U,V)],
ADVGDH(S)が無視できない確率であるとき、解答者SはギャップDiffie-Hellman問題を解いたという。
【０１７６】
ギャップ問題は上記のように判定オラクルのヒント付きの探索問題とみなせるので、ギャップ問題の方が真に易しい。
【０１７７】
鍵交換方式（情報共有方式）の安全性証明を行う際は、「ギャップ問題、もしくは探索問題を解くことが難しいことを仮定すると、情報共有方式への攻撃者が存在しない」ことを示す必要がある。これは、対偶を取ることにより、「情報共有方式への攻撃者が存在すると仮定すると、問題を解く解答者を構成できる」ことを示すことと同値である。従って、安全性証明では実際に攻撃者から解答者を構成する必要がある。そのためには解答者は攻撃者を実際の攻撃環境と見分けがつかないように動作させなければならない。
【０１７８】
HMQVでは、攻撃者が出力したσに対してσ=(XAd)y+ebを解答者が検証し、結果に応じて動作を変えねばならない。しかし、解答者はyとbを知ることができないので、自分で上記の検証を行うことができない。よって、判定オラクルに(XAd,YBe,σ)を聞き、検証式が成り立つかどうかの答えをもらうことによって証明を行う。このためギャップ問題の難しさを仮定する必要がある。
【０１７９】
一方、第一実施形態の『長期鍵二重化HMQV』では、任意のsとrについて、解答者は証明中でa2=s-ra1と設定することでσ1=(XA1d)y+eb1、σ1’=(XA1d)y+eb2、σ2=(XA2d)y+eb1、σ2’=(XA2d)y+eb2の検証をyとb1,b2を知ること無しに行うことができる。具体的には、σ1rσ2=(YB1e)sの真理値がσ1=(XA1d)y+eb1∧σ2=(XA2d)y+eb1の真理値と一致することを利用して検証を行う。このテクニックは落とし戸試験と呼ばれる。
【０１８０】
σ1rσ2=(YB1e)sは解答者の持つ情報のみで検証できるため、判定オラクルは不要であり、ギャップ問題の難しさを仮定する必要が無くなる。同様に、σ1’rσ2’=(YB2e)sの落とし戸試験を行うことで、σ1’=(XA1d)y+eb2∧σ2’=(XA2d)y+eb2の検証を行うことができる。
【０１８１】
第二実施形態の『短期鍵二重化HMQV』でも同様に、シミュレータは証明中でx2=s-rx1と設定し、σ1rσ2=(Y1Be1)sとσ1’rσ2’=(Y2Be2)sの落とし戸試験を行うことによって、判定オラクル無しでσ1=(X1Ad1)y1+e1b、σ1’=(X1Ad1)y2+e2b、σ2=(X2Ad2)y1+e1b、σ2’=(X2Ad2)y2+e2bの検証を行うことができる。
【０１８２】
第三実施形態の『長期鍵二重化NAXOS』でも同様に、シミュレータは証明中でa2=s-ra1、およびx~2=s’-r’x~1と設定し、σ1rσ1’=Y1s、σ2rσ2’=Y2s、σ5r’σ5’=Y1s′、σ6r’σ6’=Y2s’の落とし戸試験を行うことによって、判定オラクル無しでσ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ5=Y1x~1、σ5’=Y1x~2、σ6=Y2x~1、σ6’=Y2x~2の検証を行うことができる。
【０１８３】
第四実施形態の『短期鍵二重化NAXOS』でも同様に、シミュレータは証明中でx~2=s-rx~1と設定し、σ1rσ1’=As、σ2rσ2’=Bs、σ3rσ3’=Y1s、σ4rσ4’=Y2sの落とし戸試験を行うことによって、判定オラクル無しでσ1=Ay~1、σ1’=Ay~2、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2の検証を行うことができる。
【符号の説明】
【０１８４】
ＵＡ 情報共有装置
１０ 記憶部
１１ 短期秘密鍵生成部
１２ 短期公開鍵生成部
１３ 送信部
１４ 受信部
１５ 共有秘密情報生成部
１６ 共有情報生成部
１７ ハッシュ値計算部
１８ 補助情報生成部
ＵＢ 情報共有装置
２０ 記憶部
２１ 短期秘密鍵生成部
２２ 短期公開鍵生成部
２３ 送信部
２４ 受信部
２５ 共有秘密情報生成部
２６ 共有情報生成部
２７ ハッシュ値計算部
２８ 補助情報生成部
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、二者間で同じ情報を共有するための技術に関する。
【背景技術】
【０００２】
二者間でセッション鍵等の情報を共有する技術として、以下のようなＨＭＱＶ、ＮＡＸＯＳが知られている。ＨＭＱＶの詳細については非特許文献１、ＮＡＸＯＳの詳細については非特許文献２を参照のこと。
【０００３】
『ＨＭＱＶ方式』
ＨＭＱＶは、次のような方式である。ＨＭＱＶの概要を図６に示す。
【０００４】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、H:{0,1}*→ZpとH’:{0,1}*→{0,1}kをハッシュ関数とする。
【０００５】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵A=gaを公開する。同様にユーザUBに対して、長期秘密鍵b∈Zpを計算し、長期公開鍵B=gbを公開する。
【０００６】
＜鍵交換＞長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有鍵Kを共有する。
【０００７】
１．ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、短期公開鍵をX=gxとし、ユーザUBに送る。
【０００８】
２．ユーザUBは、Xを受信し、短期秘密鍵y∈Zpをランダムに選び、短期公開鍵をY=gyとし、ユーザUAに送る。
【０００９】
ユーザUBは、d=H(X,UB)、e=H(Y,UA)、σ=(XAd)y+ebを計算し、共有鍵K=H’(σ)を得る。
【００１０】
３．ユーザUAは、Yを受信し、d=H(X,UB)、e=H(Y,UA)、σ=(YBe)x+daを計算し、共有鍵K=H’(σ)を得る。
【００１１】
共有秘密情報は両方のユーザが計算した
σ=(XAd)y+eb=(YBe)x+da=g(x+da)(y+eb)
から得られるので、両者で計算した共有鍵Kは一致する。
【００１２】
このようにして、同一の共有情報である共有鍵Kが共有される。
【００１３】
『ＮＡＸＯＳ方式』
ＮＡＸＯＳは、次のような方式である。ＮＡＸＯＳの概要を図７に示す。
【００１４】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、H:{0,1}→ZpとH’:{0,1}→{0,1}kをハッシュ関数とする。
【００１５】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵A=gaを公開する。同様にユーザUBに対して、長期秘密鍵b∈Zpを計算し、長期公開鍵B=gbを公開する。
【００１６】
＜鍵交換＞長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有鍵Kを共有する。
【００１７】
１．ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、x~=H(x,a)を計算し、短期公開鍵をX=gx~とし、ユーザUBに送る。
【００１８】
２．ユーザUBは、Xを受信し、短期秘密鍵y∈Zpをランダムに選び、y~=H(y,b)を計算し、短期公開鍵をY=gy~とし、ユーザUAに送る。
【００１９】
ユーザUBは、σ1=Ay~、σ2=Xb、σ3=Xy~を計算し、共有鍵K=H’(σ1,σ2,σ3,UA,UB)を得る。
【００２０】
３．ユーザUAは、Yを受信し、σ1=Ya、σ2=Bx~、σ3=Yx~を計算し、共有鍵K=H’(σ1,σ2,σ3,UA,UB)を得る。
【００２１】
共有秘密情報は両方のユーザが計算した
σ1=gy~a,σ2=gx~b,σ3=gx~y~
から得られるので、両者で計算した共有鍵Kは一致する。
【００２２】
このようにして、同一の共有情報である共有鍵Kが共有される。
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】Hugo Krawczyk, “HMQV: A High-Performance Secure Diffie-Hellman Protocol”, CRYPTO2005
【非特許文献２】Brian LaMacchia, Kristin Lauter, Anton Mityagin, “Stronger Security of Authenticated Key Exchange”, ProvSec2007
【発明の概要】
【発明が解決しようとする課題】
【００２４】
背景技術に記載した技術では、安全性を保証するためにいわゆるギャップ問題の難しさを仮定する必要がある。ギャップ問題とは、探索問題を解くために判定オラクルの利用を許した問題のことであり、一般にいわゆる探索問題よりも解きやすい問題となる。よって、ギャップ問題の難しさを仮定するよりも、探索問題の難しさを仮定した方が仮定を弱めることができるので望ましい。
【００２５】
この発明の課題は、探索問題の難しさを仮定することにより安全性が保証される情報共有システム、方法、装置及びプログラムを提供することである。
【課題を解決するための手段】
【００２６】
この発明の一態様による情報共有システムは、nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di,eiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵として、短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX=gxを計算する短期公開鍵生成部と、短期公開鍵Xを情報共有装置ＵＢに送信する送信部と、短期公開鍵Yを情報共有装置ＵＢから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY=gyを計算する短期公開鍵生成部と、短期公開鍵Yを情報共有装置ＵＡに送信する送信部と、短期公開鍵Xを情報共有装置ＵＡから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【００２７】
この発明の一態様による情報共有システムは、nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di1,di2,ei1,ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gaを情報共有装置ＵＢの長期公開鍵として、短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX1=gx1,X2=gx2を計算する短期公開鍵生成部と、短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY1=gy1,Y2=gy2を計算する短期公開鍵生成部と、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を情報共有装置ＵＡから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【００２８】
この発明の一態様による情報共有システムは、H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBは情報共有装置ＵＢに対応する所定の値とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、x~1=H(x,a1),x~2=H(x,a2)を計算するハッシュ値計算部と、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する受信部と、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、y~1=H(y,b1),y~2=H(y,b2)を計算するハッシュ値計算部と、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成部と、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を情報共有装置ＵＡから受信する受信部と、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【００２９】
この発明の一態様による情報共有システムは、H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gbを情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、x~1=H(x1,a)、x~2=H(x2,a)を計算するハッシュ値計算部と、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する受信部と、σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成部と、y~1=H(y1,b)、y~2=H(y2,b)を計算するハッシュ値計算部と、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成部と、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を情報共有装置ＵＡから受信する受信部と、σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、を含む。
【発明の効果】
【００３０】
探索問題の難しさを仮定して安全性を保証することができる。
【図面の簡単な説明】
【００３１】
【図１】情報共有システムの構成を説明するためのブロック図。
【図２】情報共有装置ＵＡの構成を説明するためのブロック図。
【図３】情報共有装置ＵＢの構成を説明するためのブロック図。
【図４】情報共有装置ＵＡの処理を説明するためのフローチャート。
【図５】情報共有装置ＵＢの処理を説明するためのフローチャート。
【図６】従来のＨＭＱＶの概要を説明するための図。
【図７】長期鍵二重化ＨＭＱＶの概要を説明するための図。
【図８】短期鍵二重化ＨＭＱＶの概要を説明するための図。
【図９】従来のＮＡＸＯＳの概要を説明するための図。
【図１０】長期鍵二重化ＮＡＸＯＳの概要を説明するための図。
【図１１】短期鍵二重化ＮＡＸＯＳの概要を説明するための図。
【発明を実施するための形態】
【００３２】
以下、図面を参照してこの発明の一実施形態を説明する。
【００３３】
［第一実施形態］
まず、第一実施形態のアルゴリズムである長期鍵二重化ＨＭＱＶについて説明する。
【００３４】
『長期鍵二重化ＨＭＱＶ』
長期鍵二重化ＨＭＱＶは、次のような方式である。長期鍵二重化ＨＭＱＶの概要を図７に示す。
【００３５】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、Hi:{0,1}*→Zp及びH’:{0,1}*→{0,1}kをハッシュ関数とする。kは、セキュリティパラメータであり正の整数である。また、1≦i≦nでありnは正の整数である。
【００３６】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a1,a2∈Zpを計算し、長期公開鍵A1=ga1,A2=ga2を公開する。
【００３７】
ga1の右肩の「a1」は「a1」を意味する。このように、この明細書、特許請求の範囲及び図面において、ある文字の上付きの文字及び数字の一部がその上付きの中で更に上付き又は下付きである場合がある点に留意する。同様に、ある文字の下付きの文字及び数字の一部がその下付きの中で更に上付き又は下付きである場合がある点に留意する。
【００３８】
鍵生成者は、同様にユーザUBに対して、長期秘密鍵b1,b2∈Zpを計算し、長期公開鍵B1=gb1,B2=gb2を公開する。
【００３９】
＜鍵交換＞長期秘密鍵a1,a2をもつユーザUAと、長期秘密鍵b1,b2をもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。
【００４０】
１．ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、短期公開鍵をX=gxとし、ユーザUBに送る。
【００４１】
２．ユーザUBは、Xを受信し、短期秘密鍵y∈Zpをランダムに選び、短期公開鍵をY=gyとし、ユーザUAに送る。
【００４２】
ユーザUBは、1≦i≦nについて、di=Hi(X,UB)、ei=Hi(Y,UA)、σi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算し、共有情報K=H’(σ11,σ11’, σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を得る。ただし、nは正の整数。diとeiは、di=Hi(X,UB)、ei=Hi(Y,UA)以外の事前に定められた定数であっても良い。
【００４３】
３．ユーザUAは、Yを受信し、1≦i≦nについて、di=Hi(X,UB)、ei=Hi(Y,UA)、σi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算し、共有情報K=H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を得る。diとeiは、di=Hi(X,UB)、ei=Hi(Y,UA)以外の事前に定められた定数であっても良い。
【００４４】
共有秘密情報は両方のユーザが計算した
σi1=g(x+dia1)(y+eib1),σi1’=g(x+dia1)(y+eib2),σi2=g(x+dia2)(y+eib1),σi2’=g(x+dia2)(y+eib2)
から得られるので、両者で計算した共有情報Kは一致する。
【００４５】
次に、上記『長期鍵二重化ＨＭＱＶ』の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。
【００４６】
情報共有装置ＵＡが『長期鍵二重化ＨＭＱＶ』の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが『長期鍵二重化ＨＭＱＶ』の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【００４７】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、短期公開鍵生成部１２、送信部１３、受信部１４、共有秘密情報生成部１５、共有情報生成部１６を例えば含む。
【００４８】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、短期公開鍵生成部２２、送信部２３、受信部２４、共有秘密情報生成部２５、共有情報生成部２６を例えば含む。
【００４９】
情報共有の前に、ハッシュ関数Hi、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。
【００５０】
また、情報共有の前に、情報共有装置ＵＡには、長期秘密鍵a1,a2及び長期公開鍵A1,A2が予め定められ、必要に応じて記憶部１０に記憶されているものとする。同様に、情報共有の前に、情報共有装置ＵＢには、長期秘密鍵b1,b2及び長期公開鍵B1,B2が予め定められ、必要に応じて記憶部１０に記憶されているものとする。長期秘密鍵a1,a2,b1,b2及び長期公開鍵A1,A2,B1,B2の計算は、鍵生成装置３（図１）により行われる。
【００５１】
これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。
【００５２】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵xとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵xは、短期公開鍵生成部１２に送信される。
【００５３】
情報共有装置ＵＡの短期公開鍵生成部１２は、短期秘密鍵xを用いて短期公開鍵X=gxを計算する（ステップＡ２）。短期公開鍵Xは、共有秘密情報生成部１５及び送信部１３に送信される。
【００５４】
情報共有装置ＵＡの送信部１３は、短期公開鍵Xを情報共有装置ＵＢに送信する（ステップＡ３）。
【００５５】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵yとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、短期公開鍵生成部２２に送信される。
【００５６】
情報共有装置ＵＢの短期公開鍵生成部２２は、短期秘密鍵yを用いて短期公開鍵Y=gyを計算する（ステップＢ２）。短期公開鍵Yは、共有秘密情報生成部２５及び送信部２３に送信される。
【００５７】
情報共有装置ＵＢの送信部２３は、短期公開鍵Yを情報共有装置ＵＡに送信する（ステップＢ４）。
【００５８】
情報共有装置ＵＢの受信部２４は、短期公開鍵Xを情報共有装置ＵＡから受信する（ステップＢ５）。
【００５９】
情報共有装置ＵＢの共有秘密情報生成部２５は、1≦i≦nのそれぞれのiについての共有秘密情報σi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算する（ステップＢ６）。すなわち、計4n個の共有秘密情報σ11，σ11’,σ21，σ21’,…σ1n，σ1n’,σ2n，σ2n’を計算する。計算された共有秘密情報は、共有情報生成部２６に送信される。
【００６０】
ここで、di及びeiは、所定の定数である。例えば、di=Hi(X,UB),ei=Hi(Y,UA)である。第一実施形態の情報共有装置ＵＢは、補助情報di=Hi(X,UB)、ei=Hi(Y,UA)を計算する補助情報生成部２８を有していても良い。
【００６１】
情報共有装置ＵＢの共有情報生成部２６は、H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算して、その計算結果を共有情報Kとする（ステップＢ７）。この共有情報Kは、例えば認証鍵として用いられる。
【００６２】
情報共有装置ＵＡの受信部１４（図２）は、短期公開鍵Yを情報共有装置ＵＢから受信する（ステップＡ４）。
【００６３】
情報共有装置ＵＡの共有秘密情報生成部１５は、1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する（ステップＡ５）。すなわち、計4n個の共有秘密情報σ11，σ11’,σ21，σ21’,…σ1n，σ1n’,σ2n，σ2n’を計算する。計算された共有秘密情報は、共有情報生成部１６に送信される。
【００６４】
ここで、di及びeiは、所定の定数である。例えば、di=Hi(X,UB),ei=Hi(Y,UA)である。第一実施形態の情報共有装置ＵＡは、補助情報di=Hi(X,UB)、ei=Hi(Y,UA)を計算する補助情報生成部１８を有していても良い。
【００６５】
情報共有装置ＵＡの共有情報生成部１６は、H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算して、その計算結果を共有情報Kとする（ステップＡ６）。この共有情報Kは、例えば認証鍵として用いられる。
【００６６】
このようにして、情報共有が行われる。
【００６７】
［第二実施形態］
まず、第二実施形態のアルゴリズムである長期鍵二重化ＨＭＱＶについて説明する。
【００６８】
『短期鍵二重化ＨＭＱＶ』
短期鍵二重化ＨＭＱＶは、次のような方式である。短期鍵二重化ＨＭＱＶの概要を図８に示す。
【００６９】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、Hi:{0,1}*→Zp及びH’:{0,1}*→{0,1}kをハッシュ関数とする。kは、セキュリティパラメータであり正の整数である。また、1≦i≦nでありnは正の整数である。
【００７０】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵A=gaを公開する。
【００７１】
＜鍵交換＞長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。
【００７２】
１．ユーザUAは、短期秘密鍵x1,x2∈Zpをランダムに選び、短期公開鍵をX1=gx1,X2=gx2とし、ユーザUBに送る。
【００７３】
２．ユーザUBは、X1,X2を受信し、短期秘密鍵y1,y2∈Zpをランダムに選び、短期公開鍵をY1=gy1,Y2=gy2とし、ユーザUAに送る。
【００７４】
ユーザUBは、1≦i≦nについて、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)、σi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算し、共有情報K=H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を得る。ただし、nは正の整数。di1,di2,ei1,ei2は、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)以外の事前に定められた定数であっても良い。
【００７５】
３．ユーザUAは、Y1,Y2を受信し、1≦i≦nについて、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)、σi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算し、共有鍵K=H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を得る。ただし、nは正の整数。di1,di2,ei1,ei2は、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)以外の事前に定められた定数であっても良い。
【００７６】
共有秘密情報は両方のユーザが計算した
σi1=g(x1+di1a)(y1+ei1b),σi1’=g(x1+di1a)(y2+ei2b),σi2=g(x2+di2a)(y1+ei1b),σi2’=g(x2+di2a)(y2+ei2b)
から得られるので、両者で計算した共有情報Kは一致する。
【００７７】
次に、上記『短期鍵二重化ＨＭＱＶ』の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。
【００７８】
情報共有装置ＵＡが『短期鍵二重化ＨＭＱＶ』の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが『短期鍵二重化ＨＭＱＶ』の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【００７９】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、短期公開鍵生成部１２、送信部１３、受信部１４、共有秘密情報生成部１５、共有情報生成部１６を例えば含む。
【００８０】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、短期公開鍵生成部２２、送信部２３、受信部２４、共有秘密情報生成部２５、共有情報生成部２６を例えば含む。
【００８１】
情報共有の前に、ハッシュ関数Hi、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。
【００８２】
また、情報共有の前に、情報共有装置ＵＡには、長期秘密鍵a及び長期公開鍵Aが予め定められ、必要に応じて記憶部１０に記憶されているものとする。同様に、情報共有の前に、情報共有装置ＵＢには、長期秘密鍵b及び長期公開鍵Bが予め定められ、必要に応じて記憶部１０に記憶されているものとする。長期秘密鍵a,b及び長期公開鍵A,Bの計算は、鍵生成装置３（図１）により行われる。
【００８３】
これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。
【００８４】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x1,x2∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに２つの元を選びそれぞれ短期秘密鍵x1,x2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵x1,x2は、短期公開鍵生成部１２に送信される。
【００８５】
情報共有装置ＵＡの短期公開鍵生成部１２は、短期秘密鍵x1,x2を用いて短期公開鍵X1=gx1,X2=gx2を計算する（ステップＡ２）。短期公開鍵X1,X2は、共有秘密情報生成部１５及び送信部１３に送信される。
【００８６】
情報共有装置ＵＡの送信部１３は、短期公開鍵X1,X2を情報共有装置ＵＢに送信する（ステップＡ３）。
【００８７】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y1,y2∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに２つの元を選びそれぞれ短期秘密鍵y1,y2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、短期公開鍵生成部２２に送信される。
【００８８】
情報共有装置ＵＢの短期公開鍵生成部２２は、短期秘密鍵y1,y2を用いて短期公開鍵Y1=gy1,Y2=gy2を計算する（ステップＢ２）。短期公開鍵Y1=gy1,Y2=gy2は、共有秘密情報生成部２５及び送信部２３に送信される。
【００８９】
情報共有装置ＵＢの送信部２３は、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する（ステップＢ４）。
【００９０】
情報共有装置ＵＢの受信部２４は、短期公開鍵X1,X2を情報共有装置ＵＡから受信する（ステップＢ５）。
【００９１】
情報共有装置ＵＢの共有秘密情報生成部２５は、1≦i≦nのそれぞれのiについての共有秘密情報σi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算する（ステップＢ６）。すなわち、計4n個の共有秘密情報σ11，σ11’,σ21，σ21’,…σ1n，σ1n’,σ2n，σ2n’を計算する。計算された共有秘密情報は、共有情報生成部２６に送信される。
【００９２】
ここで、di1,di2,ei1,ei2は、所定の定数である。例えば、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)である。第二実施形態の情報共有装置ＵＢは、補助情報di=Hi(X,UB)、ei=Hi(Y,UA)を計算する補助情報生成部２８を有していても良い。
【００９３】
情報共有装置ＵＢの共有情報生成部２６は、H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算して、その計算結果を共有情報Kとする（ステップＢ７）。この共有情報Kは、例えば認証鍵として用いられる。
【００９４】
情報共有装置ＵＡの受信部１４（図２）は、短期公開鍵Yを情報共有装置ＵＢから受信する（ステップＡ４）。
【００９５】
情報共有装置ＵＡの共有秘密情報生成部１５は、1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する（ステップＡ５）。すなわち、計4n個の共有秘密情報σ11，σ11’,σ21，σ21’,…σ1n，σ1n’,σ2n，σ2n’を計算する。計算された共有秘密情報は、共有情報生成部１６に送信される。
【００９６】
ここで、di1,di2,ei1,ei2は、所定の定数である。例えば、di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)である。第二実施形態の情報共有装置ＵＡは、補助情報di1=Hi(X1,UB)、di2=Hi(X2,UB)、ei1=Hi(Y1,UA)、ei2=Hi(Y2,UA)を計算する補助情報生成部１８を有していても良い。
【００９７】
情報共有装置ＵＡの共有情報生成部１６は、H’(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算して、その計算結果を共有情報Kとする（ステップＡ６）。この共有情報Kは、例えば認証鍵として用いられる。
【００９８】
このようにして、情報共有が行われる。
【００９９】
［第三実施形態］
まず、第三実施形態のアルゴリズムである長期鍵二重化ＮＡＸＯＳについて説明する。
【０１００】
『長期鍵二重化ＮＡＸＯＳ』
長期鍵二重化ＮＡＸＯＳは、次のような方式である。長期鍵二重化ＮＡＸＯＳの概要を図９に示す。
【０１０１】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、H:{0,1}*→Zp及びH’:{0,1}*→{0,1}kをハッシュ関数とする。
【０１０２】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a1,a2∈Zpを計算し、長期公開鍵A1=ga1,A2=ga2を公開する。鍵生成者は、同様にユーザUBに対して、長期秘密鍵b1,b2∈Zpを計算し、長期公開鍵B1=gb1,B2=gb2を公開する。
【０１０３】
＜鍵交換＞長期秘密鍵a1,a2をもつユーザUAと、長期秘密鍵b1,b2をもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。共有情報Kは、例えば共有鍵として用いられる。
【０１０４】
１．ユーザUAは、短期秘密鍵x∈Zpをランダムに選び、x~1=H(x,a1),x~2=H(x,a2)を計算し、短期公開鍵をX1=gx~1,X2=gx~2とし、ユーザUBに送る。
【０１０５】
２．ユーザUBは、X1,X2を受信し、短期秘密鍵y∈Zpをランダムに選び、y~1=H(y,b1), y~2=H(y,b2)を計算し、短期公開鍵をY1=gy~1,Y2=gy~2とし、ユーザUAに送る。
【０１０６】
ユーザUBは、σ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算し、K=H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を得る。
【０１０７】
UAは、ユーザUA（情報共有装置ＵＡ）に対応する所定の値である。同様に、UBは、ユーザUB（情報共有装置ＵＢ）に対応する所定の値である。
【０１０８】
３．ユーザUAは、Yを受信し、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算し、共有情報K=H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を得る。
【０１０９】
共有秘密情報は両方のユーザが計算した
σ1=gy~1a1,σ1’=gy~1a2,σ2=gy~2a1,σ2’=gy~2a2,σ3=gx~1b1,σ3’=gx~1b2,σ4=gx~2b1,σ4’=gx~2b2,σ5=gx~1y~1,σ5’=gx~1y~2,σ6=gx~2y~1,σ6’=gx~2y~2から得られるので、両者で計算した共有鍵K は一致する。
【０１１０】
次に、上記『長期鍵二重化ＮＡＸＯＳ』の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。
【０１１１】
情報共有装置ＵＡが『長期鍵二重化ＮＡＸＯＳ』の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが『長期鍵二重化ＮＡＸＯＳ』の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【０１１２】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、短期公開鍵生成部１２、送信部１３、受信部１４、共有秘密情報生成部１５、共有情報生成部１６、破線で示したハッシュ値計算部１７を例えば含む。
【０１１３】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、短期公開鍵生成部２２、送信部２３、受信部２４、共有秘密情報生成部２５、共有情報生成部２６、破線で示したハッシュ値計算部２７を例えば含む。
【０１１４】
情報共有の前に、ハッシュ関数H、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。
【０１１５】
また、情報共有の前に、情報共有装置ＵＡには、長期秘密鍵a1,a2及び長期公開鍵A1,A2が予め定められ、必要に応じて記憶部１０に記憶されているものとする。同様に、情報共有の前に、情報共有装置ＵＢには、長期秘密鍵b1,b2及び長期公開鍵B1,B2が予め定められ、必要に応じて記憶部１０に記憶されているものとする。長期秘密鍵a1,a2,b1,b2及び長期公開鍵A1,A2,B1,B2の計算は、鍵生成装置３（図１）により行われる。
【０１１６】
これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。
【０１１７】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵xとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵xは、ハッシュ値計算部１７に送信される。
【０１１８】
情報共有装置ＵＡのハッシュ値計算部１７は、x~1=H(x,a1),x~2=H(x,a2)を計算する（ステップＡ７）。計算されたハッシュ値x~1,x~2は、短期公開鍵生成部１２及び共有秘密情報生成部１５に送信される。
【０１１９】
情報共有装置ＵＡの短期公開鍵生成部１２は、計算されたハッシュ値x~1,x~2をそれぞれ用いて短期公開鍵X1=gx~1,X2=gx~2を計算する（ステップＡ２）。短期公開鍵X1,X2は、共有秘密情報生成部１５及び送信部１３に送信される。
【０１２０】
情報共有装置ＵＡの送信部１３は、短期公開鍵X1,X2を情報共有装置ＵＢに送信する（ステップＡ３）。
【０１２１】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに元を選び短期秘密鍵yとする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵yは、ハッシュ値計算部２７に送信される。
【０１２２】
情報共有装置ＵＢのハッシュ値計算部２７は、y~1=H(y,b1),y~2=H(y,b2)を計算する。計算されたハッシュ値y~1,y~2は、短期公開鍵生成部２２及び共有秘密情報生成部２５に送信される。
【０１２３】
情報共有装置ＵＢの短期公開鍵生成部２２は、ハッシュ値y~1,y~2をそれぞれ用いて短期公開鍵Y1=gy~1,Y2=gy~2を計算する（ステップＢ７）。短期公開鍵Y1,Y2は、共有秘密情報生成部２５及び送信部２３に送信される。
【０１２４】
情報共有装置ＵＢの送信部２３は、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する（ステップＢ４）。
【０１２５】
情報共有装置ＵＢの受信部２４は、短期公開鍵X1,X2を情報共有装置ＵＡから受信する（ステップＢ５）。
【０１２６】
情報共有装置ＵＢの共有秘密情報生成部２５は、１２個の共有秘密情報σ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算する（ステップＢ６）。計算された共有秘密情報は、共有情報生成部２６に送信される。
【０１２７】
情報共有装置ＵＢの共有情報生成部２６は、H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算して、その計算結果を共有情報Kとする（ステップＢ７）。この共有情報Kは、例えば認証鍵として用いられる。
【０１２８】
情報共有装置ＵＡの受信部１４（図２）は、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する（ステップＡ４）。
【０１２９】
情報共有装置ＵＡの共有秘密情報生成部１５は、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する（ステップＡ５）。計算された共有秘密情報は、共有情報生成部１６に送信される。
【０１３０】
情報共有装置ＵＡの共有情報生成部１６は、H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算して、その計算結果を共有情報Kとする（ステップＡ６）。この共有情報Kは、例えば認証鍵として用いられる。
【０１３１】
このようにして、情報共有が行われる。
【０１３２】
［第四実施形態］
まず、第四実施形態のアルゴリズムである短期鍵二重化ＮＡＸＯＳについて説明する。
【０１３３】
『短期鍵二重化ＮＡＸＯＳ』
短期鍵二重化ＮＡＸＯＳは、次のような方式である。短期鍵二重化ＮＡＸＯＳの概要を図１０に示す。
【０１３４】
＜公開パラメータ＞Gをkbitの素数位数pの巡回群、gをGの生成元、H:{0,1}*→Zp及びH’:{0,1}*→{0,1}kをハッシュ関数とする。
【０１３５】
＜鍵生成＞鍵生成者は、ユーザUAに対して、長期秘密鍵a∈Zpを計算し、長期公開鍵A=gaを公開する。同様に、鍵生成者は、ユーザUBに対して、長期秘密鍵b∈Zpを計算し、長期公開鍵B=gbを公開する。
【０１３６】
＜鍵交換＞長期秘密鍵aをもつユーザUAと、長期秘密鍵bをもつユーザUBは、以下のようにして認証鍵交換を行い共有情報Kを共有する。
【０１３７】
１．ユーザUAは、短期秘密鍵x1,x2∈Zpをランダムに選び、x~1=H(x1,a)、x~2=H(x2,a)を計算し、短期公開鍵をX1=gx~1,X2=gx~2とし、ユーザUBに送る。
【０１３８】
２．ユーザUBは、X1,X2を受信し、短期秘密鍵y1,y2∈Zpをランダムに選び、y~1=H(y1,b)、y~2=H(y2,b)を計算し、短期公開鍵をY1=gy~1,Y2=gy~2とし、ユーザUAに送る。
【０１３９】
ユーザUBは、σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算し、共有情報K=H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を得る。
【０１４０】
UAは、ユーザUA（情報共有装置ＵＡ）に対応する所定の値である。同様に、UBは、ユーザUB（情報共有装置ＵＢ）に対応する所定の値である。
【０１４１】
３．ユーザUAは、Y1,Y2を受信し、σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算し、共有情報K=H′(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を得る。
【０１４２】
共有秘密情報は両方のユーザが計算した
σ1=gy~1a,σ1’=gy~2a,σ2=gx~1b,σ2’=gx~2b,σ3=gx~1y~1,σ3’=gx~2y~1,σ4=gx~1y~2,σ4’=gx~2y~2
から得られるので、両者で計算した共有情報Kは一致する。
【０１４３】
次に、上記『短期鍵二重化ＮＡＸＯＳ』の欄で説明したアルゴリズムを実行する情報共有システムの一例を説明する。この情報共有システムは、図１に例示するように、情報共有装置ＵＡ及び情報共有装置ＵＢから構成される。
【０１４４】
情報共有装置ＵＡが『短期鍵二重化ＮＡＸＯＳ』の欄で説明したユーザＵＡに対応し、情報共有装置ＵＢが『短期鍵二重化ＮＡＸＯＳ』の欄で説明したユーザＵＢに対応する。情報共有装置ＵＡは図４に例示した処理を行い、情報共有装置ＵＢは図５に例示した処理を行う。
【０１４５】
情報共有装置ＵＡは、図２に示すように、記憶部１０、短期秘密鍵生成部１１、短期公開鍵生成部１２、送信部１３、受信部１４、共有秘密情報生成部１５、共有情報生成部１６、破線で示したハッシュ値計算部１７を例えば含む。
【０１４６】
情報共有装置ＵＢは、図３に示すように、記憶部２０、短期秘密鍵生成部２１、短期公開鍵生成部２２、送信部２３、受信部２４、共有秘密情報生成部２５、共有情報生成部２６、破線で示したハッシュ値計算部２７を例えば含む。
【０１４７】
情報共有の前に、ハッシュ関数H、セキュリティパラメータk、群G及び生成元g等の情報共有のために必要なパラメータが設定され、必要に応じて記憶部１０及び記憶部２０に記憶されているものとする。
【０１４８】
また、情報共有の前に、情報共有装置ＵＡには、長期秘密鍵a及び長期公開鍵Aが予め定められ、必要に応じて記憶部１０に記憶されているものとする。同様に、情報共有の前に、情報共有装置ＵＢには、長期秘密鍵b及び長期公開鍵Bが予め定められ、必要に応じて記憶部１０に記憶されているものとする。長期秘密鍵a,b及び長期公開鍵A,Bの計算は、鍵生成装置３（図１）により行われる。
【０１４９】
これらの記憶部１０及び２０に記憶されたデータは、適宜読み出されて以下に説明する計算が行われる。
【０１５０】
情報共有装置ＵＡの短期秘密鍵生成部１１（図２）は、短期秘密鍵x1,x2∈Zpを生成する（ステップＡ１）。例えば、Zpの中から一様ランダムに２つの元を選びそれぞれ短期秘密鍵x1,x2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵x1,x2は、ハッシュ値計算部１７に送信される。
【０１５１】
情報共有装置ＵＡのハッシュ値計算部１７は、x~1=H(x1,a),x~2=H(x2,a)を計算する（ステップＡ７）。計算されたハッシュ値x~1,x~2は、短期公開鍵生成部１２及び共有秘密情報生成部１５に送信される。
【０１５２】
情報共有装置ＵＡの短期公開鍵生成部１２は、計算されたハッシュ値x~1,x~2をそれぞれ用いて短期公開鍵X1=gx~1,X2=gx~2を計算する（ステップＡ２）。短期公開鍵X1,X2は、共有秘密情報生成部１５及び送信部１３に送信される。
【０１５３】
情報共有装置ＵＡの送信部１３は、短期公開鍵X1,X2を情報共有装置ＵＢに送信する（ステップＡ３）。
【０１５４】
情報共有装置ＵＢの短期秘密鍵生成部２１（図３）は、短期秘密鍵y1,y2∈Zpを生成する（ステップＢ１）。例えば、Zpの中から一様ランダムに２つの元を選び短期秘密鍵y1,y2とする。求める安全性のレベルが高くない場合には、一様ランダムに選択する必要はない。生成された短期秘密鍵y1,y2は、ハッシュ値計算部２７に送信される。
【０１５５】
情報共有装置ＵＢのハッシュ値計算部２７は、y~1=H(y1,b),y~2=H(y2,b)を計算する。計算されたハッシュ値y~1,y~2は、短期公開鍵生成部２２及び共有秘密情報生成部２５に送信される。
【０１５６】
情報共有装置ＵＢの短期公開鍵生成部２２は、ハッシュ値y~1,y~2をそれぞれ用いて短期公開鍵Y1=gy~1,Y2=gy~2を計算する（ステップＢ７）。短期公開鍵Y1,Y2は、共有秘密情報生成部２５及び送信部２３に送信される。
【０１５７】
情報共有装置ＵＢの送信部２３は、短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する（ステップＢ４）。
【０１５８】
情報共有装置ＵＢの受信部２４は、短期公開鍵X1,X2を情報共有装置ＵＡから受信する（ステップＢ５）。
【０１５９】
情報共有装置ＵＢの共有秘密情報生成部２５は、計８個の共有秘密情報σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算する（ステップＢ６）。計算された共有秘密情報は、共有情報生成部２６に送信される。
【０１６０】
情報共有装置ＵＢの共有情報生成部２６は、H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算して、その計算結果を共有情報Kとする（ステップＢ７）。この共有情報Kは、例えば認証鍵として用いられる。
【０１６１】
情報共有装置ＵＡの受信部１４（図２）は、短期公開鍵Y1,Y2を情報共有装置ＵＢから受信する（ステップＡ４）。
【０１６２】
情報共有装置ＵＡの共有秘密情報生成部１５は、σ1=Y1a~1、σ1’=Y1a~2、σ2=Y2a~1、σ2’=Y2a~2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する（ステップＡ５）。計算された共有秘密情報は、共有情報生成部１６に送信される。
【０１６３】
情報共有装置ＵＡの共有情報生成部１６は、H’(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算して、その計算結果を共有情報Kとする（ステップＡ６）。この共有情報Kは、例えば認証鍵として用いられる。
【０１６４】
このようにして、情報共有が行われる。
【０１６５】
［変形例等］
情報共有装置ＵＡの各部間のデータのやり取りは直接行われてもよいし、記憶部１０を介して行われてもよい。同様に、情報共有装置ＵＢの各部間のデータのやり取りは直接行われてもよいし、記憶部２０を介して行われてもよい。
【０１６６】
上記の例では、共有情報生成部１６及び共有情報生成部２６は、ハッシュ関数H’を用いたが、任意の予め定められた関数Fを用いて共有情報を求めてもよい。すなわち、第一実施形態及び第二実施形態においてはF(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算してその計算結果を共有情報kとしても良いし、第三実施形態においてはF(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算してその計算結果を共有情報kとしても良いし、第四実施形態においては、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算してその計算結果を共有情報kとしても良い。
【０１６７】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１６８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１６９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１７０】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１７１】
［安全性の証明］
このように、長期秘密鍵又は短期秘密鍵を二重化し、共有情報を計算するための共有秘密情報であって長期秘密鍵又は短期秘密鍵に由来する共有秘密情報を短期秘密鍵ごとに計算する。これにより、ギャップ問題の難しさを仮定することなく探索問題の難しさをのみを仮定することで安全性を証明することができる。以下、その安全性の証明の概要を説明する。
【０１７２】
まず、探索問題（探索Diffie-Hellman問題）及びギャップ問題（ギャップDiffie-Hellman問題）の定義を説明する。
【０１７３】
探索Diffie-Hellman問題：κをセキュリティパラメータとし、pをκビット素数とする。Gをgを生成元とする位数pの巡回群とする。Diffie-Hellman関数CDH:G2→GをCDH(gu,gv)=guvとして定義し、判定Diffie-Hellman述語オラクルDDH:G3→{0,1}を(gu,gv,gw)を入力としuv=w mod pが成り立つとき1を出力し、そうでなければ0を出力する関数として定義する。
【０１７４】
解答者Sは、一様ランダムに選ばれたU=gu,V=gv∈Gと判定Diffie-Hellman述語オラクルDDH(・,・,・)へのアクセスを入力され、CDH(U,V)の出力を試みる。解答者Sのアドバンテージを次のように定義する。
【０１７５】
ADVGDH(S)=Pr[U,V∈G,SDDH(・,・,・)(g,U,V)=CDH(U,V)],
ADVGDH(S)が無視できない確率であるとき、解答者SはギャップDiffie-Hellman問題を解いたという。
【０１７６】
ギャップ問題は上記のように判定オラクルのヒント付きの探索問題とみなせるので、ギャップ問題の方が真に易しい。
【０１７７】
鍵交換方式（情報共有方式）の安全性証明を行う際は、「ギャップ問題、もしくは探索問題を解くことが難しいことを仮定すると、情報共有方式への攻撃者が存在しない」ことを示す必要がある。これは、対偶を取ることにより、「情報共有方式への攻撃者が存在すると仮定すると、問題を解く解答者を構成できる」ことを示すことと同値である。従って、安全性証明では実際に攻撃者から解答者を構成する必要がある。そのためには解答者は攻撃者を実際の攻撃環境と見分けがつかないように動作させなければならない。
【０１７８】
HMQVでは、攻撃者が出力したσに対してσ=(XAd)y+ebを解答者が検証し、結果に応じて動作を変えねばならない。しかし、解答者はyとbを知ることができないので、自分で上記の検証を行うことができない。よって、判定オラクルに(XAd,YBe,σ)を聞き、検証式が成り立つかどうかの答えをもらうことによって証明を行う。このためギャップ問題の難しさを仮定する必要がある。
【０１７９】
一方、第一実施形態の『長期鍵二重化HMQV』では、任意のsとrについて、解答者は証明中でa2=s-ra1と設定することでσ1=(XA1d)y+eb1、σ1’=(XA1d)y+eb2、σ2=(XA2d)y+eb1、σ2’=(XA2d)y+eb2の検証をyとb1,b2を知ること無しに行うことができる。具体的には、σ1rσ2=(YB1e)sの真理値がσ1=(XA1d)y+eb1∧σ2=(XA2d)y+eb1の真理値と一致することを利用して検証を行う。このテクニックは落とし戸試験と呼ばれる。
【０１８０】
σ1rσ2=(YB1e)sは解答者の持つ情報のみで検証できるため、判定オラクルは不要であり、ギャップ問題の難しさを仮定する必要が無くなる。同様に、σ1’rσ2’=(YB2e)sの落とし戸試験を行うことで、σ1’=(XA1d)y+eb2∧σ2’=(XA2d)y+eb2の検証を行うことができる。
【０１８１】
第二実施形態の『短期鍵二重化HMQV』でも同様に、シミュレータは証明中でx2=s-rx1と設定し、σ1rσ2=(Y1Be1)sとσ1’rσ2’=(Y2Be2)sの落とし戸試験を行うことによって、判定オラクル無しでσ1=(X1Ad1)y1+e1b、σ1’=(X1Ad1)y2+e2b、σ2=(X2Ad2)y1+e1b、σ2’=(X2Ad2)y2+e2bの検証を行うことができる。
【０１８２】
第三実施形態の『長期鍵二重化NAXOS』でも同様に、シミュレータは証明中でa2=s-ra1、およびx~2=s’-r’x~1と設定し、σ1rσ1’=Y1s、σ2rσ2’=Y2s、σ5r’σ5’=Y1s′、σ6r’σ6’=Y2s’の落とし戸試験を行うことによって、判定オラクル無しでσ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ5=Y1x~1、σ5’=Y1x~2、σ6=Y2x~1、σ6’=Y2x~2の検証を行うことができる。
【０１８３】
第四実施形態の『短期鍵二重化NAXOS』でも同様に、シミュレータは証明中でx~2=s-rx~1と設定し、σ1rσ1’=As、σ2rσ2’=Bs、σ3rσ3’=Y1s、σ4rσ4’=Y2sの落とし戸試験を行うことによって、判定オラクル無しでσ1=Ay~1、σ1’=Ay~2、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2の検証を行うことができる。
【符号の説明】
【０１８４】
ＵＡ 情報共有装置
１０ 記憶部
１１ 短期秘密鍵生成部
１２ 短期公開鍵生成部
１３ 送信部
１４ 受信部
１５ 共有秘密情報生成部
１６ 共有情報生成部
１７ ハッシュ値計算部
１８ 補助情報生成部
ＵＢ 情報共有装置
２０ 記憶部
２１ 短期秘密鍵生成部
２２ 短期公開鍵生成部
２３ 送信部
２４ 受信部
２５ 共有秘密情報生成部
２６ 共有情報生成部
２７ ハッシュ値計算部
２８ 補助情報生成部
【特許請求の範囲】
【請求項１】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di,eiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX=gxを計算する短期公開鍵生成部と、上記短期公開鍵Xを情報共有装置ＵＢに送信する送信部と、短期公開鍵Yを上記情報共有装置ＵＢから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY=gyを計算する短期公開鍵生成部と、上記短期公開鍵Yを情報共有装置ＵＡに送信する送信部と、短期公開鍵Xを上記情報共有装置ＵＡから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項２】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di1,di2,ei1,ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gaを情報共有装置ＵＢの長期公開鍵として、
短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX1=gx1,X2=gx2を計算する短期公開鍵生成部と、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY1=gy1,Y2=gy2を計算する短期公開鍵生成部と、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項３】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、x~1=H(x,a1),x~2=H(x,a2)を計算するハッシュ値計算部と、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、y~1=H(y,b1),y~2=H(y,b2)を計算するハッシュ値計算部と、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成部と、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信部と、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項４】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gbを情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、x~1=H(x1,a)、x~2=H(x2,a)を計算するハッシュ値計算部と、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成部と、y~1=H(y1,b)、y~2=H(y2,b)を計算するハッシュ値計算部と、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成部と、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信部と、σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項５】
請求項１の情報共有システムにおいて、
UAを上記情報共有装置ＵＡに対応する所定の値とし、UBを上記情報共有装置ＵＢに対応する所定の値として、
上記di=Hi(X,UB)であり、上記ei=Hi(Y,UA)である、
情報共有システム。
【請求項６】
請求項２の情報共有システムにおいて、
UAを上記情報共有装置ＵＡに対応する所定の値とし、UBを上記情報共有装置ＵＢに対応する所定の値として、
上記di1=Hi(X1,UB)であり、上記di2=Hi(X2,UB)であり、上記ei1=Hi(Y1,UA)であり、上記ei2=Hi(Y2,UA)である、
情報共有システム。
【請求項７】
請求項１から６の情報共有システムにおいて、
上記関数Fは、ハッシュ関数H’:{0,1}*→{0,1}である、
情報共有システム。
【請求項８】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di,eiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、短期公開鍵をX=gxを計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵Xを情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵Yを上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、短期公開鍵をY=gyを計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵Yを情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵Xを上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項９】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di1,di2,ei1,ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gaを情報共有装置ＵＢの長期公開鍵として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、短期公開鍵をX1=gx1,X2=gx2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する共有秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、短期公開鍵をY1=gy1,Y2=gy2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算する共有秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項１０】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡのハッシュ値計算部が、x~1=H(x,a1),x~2=H(x,a2)を計算するハッシュ値計算ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの共有秘密情報計算部が、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢのハッシュ値計算部が、y~1=H(y,b1),y~2=H(y,b2)を計算するハッシュ値計算ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの共有秘密情報計算部が、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項１１】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gbを情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡのハッシュ値計算部が、x~1=H(x1,a)、x~2=H(x2,a)を計算するハッシュ値計算ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの共有秘密情報計算部が、σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算する共有情報生成ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢのハッシュ値計算部が、y~1=H(y1,b)、y~2=H(y2,b)を計算するハッシュ値計算ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの共有秘密情報計算部が、σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項１２】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di,eiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、
短期公開鍵をX=gxを計算する短期公開鍵生成部と、
上記短期公開鍵Xを情報共有装置ＵＢに送信する送信部と、
短期公開鍵Yを上記情報共有装置ＵＢから受信する受信部と、
1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する共有秘密情報計算部と、
F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、
を含む情報共有装置ＵＡである情報共有装置。
【請求項１３】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di1,di2,ei1,ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gaを情報共有装置ＵＢの長期公開鍵として、
短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、
短期公開鍵をX1=gx1,X2=gx2を計算する短期公開鍵生成部と、
上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、
短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、
1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する共有秘密情報計算部と、
F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、
を含む情報共有装置ＵＡである情報共有装置。
【請求項１４】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、
x~1=H(x,a1),x~2=H(x,a2)を計算するハッシュ値計算部と、
短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、
上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、
短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、
σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する共有秘密情報計算部と、
F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、
を含む情報共有装置ＵＡである情報共有装置。。
【請求項１５】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gbを情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、
x~1=H(x1,a)、x~2=H(x2,a)を計算するハッシュ値計算部と、
短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、
上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、
短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、
σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算する共有秘密情報計算部と、
F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算する共有情報生成部と、
を含む情報共有装置ＵＡである情報共有装置。
【請求項１６】
請求項１２から１５の何れかに記載の情報共有装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di,eiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX=gxを計算する短期公開鍵生成部と、上記短期公開鍵Xを情報共有装置ＵＢに送信する送信部と、短期公開鍵Yを上記情報共有装置ＵＢから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY=gyを計算する短期公開鍵生成部と、上記短期公開鍵Yを情報共有装置ＵＡに送信する送信部と、短期公開鍵Xを上記情報共有装置ＵＡから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項２】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di1,di2,ei1,ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gaを情報共有装置ＵＢの長期公開鍵として、
短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をX1=gx1,X2=gx2を計算する短期公開鍵生成部と、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成部と、短期公開鍵をY1=gy1,Y2=gy2を計算する短期公開鍵生成部と、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信部と、1≦i≦nのそれぞれのiについてのσi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算する共有秘密情報計算部と、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項３】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、x~1=H(x,a1),x~2=H(x,a2)を計算するハッシュ値計算部と、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y∈Zpを生成する短期秘密鍵生成部と、y~1=H(y,b1),y~2=H(y,b2)を計算するハッシュ値計算部と、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成部と、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信部と、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項４】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gbを情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、x~1=H(x1,a)、x~2=H(x2,a)を計算するハッシュ値計算部と、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＡと、
短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成部と、y~1=H(y1,b)、y~2=H(y2,b)を計算するハッシュ値計算部と、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成部と、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信部と、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信部と、σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算する共有秘密情報計算部と、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、を含む情報共有装置ＵＢと、
を含む情報共有システム。
【請求項５】
請求項１の情報共有システムにおいて、
UAを上記情報共有装置ＵＡに対応する所定の値とし、UBを上記情報共有装置ＵＢに対応する所定の値として、
上記di=Hi(X,UB)であり、上記ei=Hi(Y,UA)である、
情報共有システム。
【請求項６】
請求項２の情報共有システムにおいて、
UAを上記情報共有装置ＵＡに対応する所定の値とし、UBを上記情報共有装置ＵＢに対応する所定の値として、
上記di1=Hi(X1,UB)であり、上記di2=Hi(X2,UB)であり、上記ei1=Hi(Y1,UA)であり、上記ei2=Hi(Y2,UA)である、
情報共有システム。
【請求項７】
請求項１から６の情報共有システムにおいて、
上記関数Fは、ハッシュ関数H’:{0,1}*→{0,1}である、
情報共有システム。
【請求項８】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di,eiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、短期公開鍵をX=gxを計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵Xを情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵Yを上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、短期公開鍵をY=gyを計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵Yを情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵Xを上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1=(XA1di)y+eib1、σi1’=(XA1di)y+eib2、σi2=(XA2di)y+eib1、σi2’=(XA2di)y+eib2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項９】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di1,di2,ei1,ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gaを情報共有装置ＵＢの長期公開鍵として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、短期公開鍵をX1=gx1,X2=gx2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する共有秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、短期公開鍵をY1=gy1,Y2=gy2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの共有秘密情報計算部が、1≦i≦nのそれぞれのiについてのσi1=(X1Adi1)y1+ei1b、σi1’=(X1Adi1)y2+ei2b、σi2=(X2Adi2)y1+ei1b、σi2’=(X2Adi2)y2+ei2bを計算する共有秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項１０】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡのハッシュ値計算部が、x~1=H(x,a1),x~2=H(x,a2)を計算するハッシュ値計算ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの共有秘密情報計算部が、σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢのハッシュ値計算部が、y~1=H(y,b1),y~2=H(y,b2)を計算するハッシュ値計算ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの共有秘密情報計算部が、nを正の整数とし、1≦i≦nのそれぞれのiについてのσ1=A1y~1、σ1’=A2y~1、σ2=A1y~2、σ2’=A2y~2、σ3=X1b1、σ3’=X2b1、σ4=X1b2、σ4’=X2b2、σ5=X1y~1、σ5’=X1y~2、σ6=X2y~1、σ6’=X2y~2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項１１】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gbを情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
情報共有装置ＵＡの短期秘密鍵生成部が、短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＡのハッシュ値計算部が、x~1=H(x1,a)、x~2=H(x2,a)を計算するハッシュ値計算ステップと、
情報共有装置ＵＡの短期公開鍵生成部が、短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＡの送信部が、上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信ステップと、
情報共有装置ＵＡの受信部が、短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信ステップと、
情報共有装置ＵＡの共有秘密情報計算部が、σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＡの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算する共有情報生成ステップと、
情報共有装置ＵＢの短期秘密鍵生成部が、短期秘密鍵y1,y2∈Zpを生成する短期秘密鍵生成ステップと、
情報共有装置ＵＢのハッシュ値計算部が、y~1=H(y1,b)、y~2=H(y2,b)を計算するハッシュ値計算ステップと、
情報共有装置ＵＢの短期公開鍵生成部が、短期公開鍵Y1=gy~1,Y2=gy~2を計算する短期公開鍵生成ステップと、
情報共有装置ＵＢの送信部が、上記短期公開鍵Y1,Y2を情報共有装置ＵＡに送信する送信ステップと、
情報共有装置ＵＢの受信部が、短期公開鍵X1,X2を上記情報共有装置ＵＡから受信する受信ステップと、
情報共有装置ＵＢの共有秘密情報計算部が、σ1=Ay~1、σ1’=Ay~2、σ2=X1b、σ2’=X2b、σ3=X1y~1、σ3’=X2y~1、σ4=X1y~2、σ4’=X2y~2を計算する共有秘密情報計算ステップと、
情報共有装置ＵＢの共有情報生成部が、F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成ステップと、
を含む情報共有方法。
【請求項１２】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di,eiを所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、
短期公開鍵をX=gxを計算する短期公開鍵生成部と、
上記短期公開鍵Xを情報共有装置ＵＢに送信する送信部と、
短期公開鍵Yを上記情報共有装置ＵＢから受信する受信部と、
1≦i≦nのそれぞれのiについてのσi1=(YB1ei)x+dia1、σi1’=(YB2ei)x+dia1、σi2=(YB1ei)x+dia2、σi2’=(YB2ei)x+dia2を計算する共有秘密情報計算部と、
F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、
を含む情報共有装置ＵＡである情報共有装置。
【請求項１３】
nを正の整数とし、1≦i≦nとし、Hi:{0,1}*→Zpをハッシュ関数とし、di1,di2,ei1,ei2を所定の定数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gaを情報共有装置ＵＢの長期公開鍵として、
短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、
短期公開鍵をX1=gx1,X2=gx2を計算する短期公開鍵生成部と、
上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、
短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、
1≦i≦nのそれぞれのiについてのσi1=(Y1Bei1)x1+di1a、σi1’=(Y2Bei2)x1+di1a、σi2=(Y1Bei1)x2+di2a、σi2’=(Y2Bei2)x2+di2aを計算する共有秘密情報計算部と、
F(σ11,σ11’,σ12,σ12’,…,σn1,σn1’,σn2,σn2’)を計算する共有情報生成部と、
を含む情報共有装置ＵＡである情報共有装置。
【請求項１４】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a1,a2∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A1=ga1,A2=ga2を情報共有装置ＵＡの長期公開鍵とし、b1,b2∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B1=gb1,B2=gb2を情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x∈Zpを生成する短期秘密鍵生成部と、
x~1=H(x,a1),x~2=H(x,a2)を計算するハッシュ値計算部と、
短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、
上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、
短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、
σ1=Y1a1、σ1’=Y1a2、σ2=Y2a1、σ2’=Y2a2、σ3=B1x~1、σ3’=B1x~2、σ4=B2x~1、σ4’=B2x~2、σ5=Y1x~1、σ5’=Y2x~1、σ6=Y1x~2、σ6’=Y2x~2を計算する共有秘密情報計算部と、
F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,σ5,σ5’,σ6,σ6’,UA,UB)を計算する共有情報生成部と、
を含む情報共有装置ＵＡである情報共有装置。。
【請求項１５】
H:{0,1}*→Zpをハッシュ関数とし、Fを予め定められた関数とし、セキュリティパラメータkを正の整数とし、Gをkbitの素数位数pの巡回群、gをGの生成元とし、a∈Zpを情報共有装置ＵＡの長期秘密鍵とし、A=gaを情報共有装置ＵＡの長期公開鍵とし、b∈Zpを情報共有装置ＵＢの長期秘密鍵とし、B=gbを情報共有装置ＵＢの長期公開鍵とし、UAを情報共有装置ＵＡに対応する所定の値とし、UBを情報共有装置ＵＢに対応する所定の値として、
短期秘密鍵x1,x2∈Zpを生成する短期秘密鍵生成部と、
x~1=H(x1,a)、x~2=H(x2,a)を計算するハッシュ値計算部と、
短期公開鍵X1=gx~1,X2=gx~2を計算する短期公開鍵生成部と、
上記短期公開鍵X1,X2を情報共有装置ＵＢに送信する送信部と、
短期公開鍵Y1,Y2を上記情報共有装置ＵＢから受信する受信部と、
σ1=Y1a、σ1’=Y2a、σ2=Bx~1、σ2’=Bx~2、σ3=Y1x~1、σ3’=Y1x~2、σ4=Y2x~1、σ4’=Y2x~2を計算する共有秘密情報計算部と、
F(σ1,σ1’,σ2,σ2’,σ3,σ3’,σ4,σ4’,UA,UB)を計算する共有情報生成部と、
を含む情報共有装置ＵＡである情報共有装置。
【請求項１６】
請求項１２から１５の何れかに記載の情報共有装置の各部としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−２４９０５４（Ｐ２０１２−２４９０５４Ａ）
【公開日】平成２４年１２月１３日（２０１２．１２．１３）
【国際特許分類】
【出願番号】特願２０１１−１１８８２２（Ｐ２０１１−１１８８２２）
【出願日】平成２３年５月２７日（２０１１．５．２７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１２月１３日（２０１２．１２．１３）
【国際特許分類】
【出願日】平成２３年５月２７日（２０１１．５．２７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]