(57)【特許請求の範囲】
【請求項１】
第一鍵交換装置と第二鍵交換装置とを含み、前記第一鍵交換装置と前記第二鍵交換装置との間で共通の共通鍵を共有する鍵交換システムであって、
秘密鍵dkAは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSAは、暗号文を公開鍵の情報無しで生成できる公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第一暗号文生成秘密鍵rSAは暗号文生成の乱数空間RSEからランダムに選択され、第一暗号文CTSAは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第一暗号文生成秘密鍵rSAが暗号化されて生成されるものであり、秘密鍵dkAと秘密鍵dkSAと第一暗号文生成秘密鍵rSAとを含む第一長期秘密鍵SSKAが、前記第一鍵交換装置以外の鍵交換装置に対して秘密にされ、前記秘密鍵dkAに対応する公開鍵ekAと前記秘密鍵dkSAに対応する公開鍵ekSAと第一暗号文CTSAとを含む第一長期公開鍵SPKAとが、前記第二鍵交換装置に対してアクセス可能にされるものとし、
秘密鍵dkBは前記鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSBは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第二暗号文生成秘密鍵rSBは暗号文生成の乱数空間RSEからランダムに選択され、第二暗号文CTSBは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第二暗号文生成秘密鍵rSBが暗号化されて生成されるものであり、秘密鍵dkBと秘密鍵dkSBと第二暗号文生成秘密鍵rSBとを含む第二長期秘密鍵SSKBを秘密にされ、前記秘密鍵dkBに対応する公開鍵ekBと前記秘密鍵dkSBに対応する公開鍵ekSBと第二暗号文CTSBとを含む第二長期公開鍵SPKBを前記第一鍵交換装置に対してアクセス可能にされるものとし、
前記第一鍵交換装置は、
暗号文生成の乱数空間RSEからランダムに第一暗号文生成アドホック秘密鍵rAを選択し、鍵生成の乱数空間RSGからランダムに第一鍵生成アドホック秘密鍵rTAを選択する第一秘密鍵選択部と、
前記第二鍵交換装置にアクセス可能に記憶される第二長期公開鍵SPKBに含まれる公開鍵ekBを用いて、前記鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第一暗号文生成アドホック秘密鍵rAを暗号化し、第一暗号文CTAと第一鍵KAとの組を生成する第一暗号化部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより、前記第一鍵生成アドホック秘密鍵rTAを用いて、公開鍵ekTと秘密鍵dkTとの組を生成する鍵生成部と、
前記秘密鍵dkAを用いて、前記鍵カプセル化メカニズムの復号アルゴリズムにより、前記第二鍵交換装置から受信する第二暗号文CTBを復号し、第二鍵KBを求める第一復号部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、前記秘密鍵dkTを用いて、前記第二鍵交換装置から受信する暗号文CTTを復号し、鍵KTを求める第二復号部と、
前記秘密鍵dkSAを用いて、前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、第二暗号文生成秘密鍵rSBが暗号化されて生成される第二暗号文CTSBを復号し、鍵KSを求める第三復号部と、
前記第一鍵KA、前記第二鍵KB、前記鍵KT及び前記鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第一パラメータ生成部と、
疑似ランダム関数Gにより、セッション識別子と、前記共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第一共通鍵生成部とを含み、
前記第二鍵交換装置は、
暗号文生成の乱数空間RSEからランダムに第二暗号文生成アドホック秘密鍵rBを選択し、暗号文生成の乱数空間RSEからランダムに第二鍵生成アドホック秘密鍵rTBを選択する第二秘密鍵選択部と、
前記公開鍵ekAを用いて、前記鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第二暗号文生成アドホック秘密鍵rBを暗号化し、第二暗号文CTBと第二鍵KBとの組を生成する第二暗号化部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより、前記第二鍵生成アドホック秘密鍵rTBを暗号化し、前記暗号文CTTを生成する第三暗号化部と、
前記秘密鍵dkBを用いて、前記鍵カプセル化メカニズムの復号アルゴリズムにより、前記第一暗号文CTAを復号し、第一鍵KAを求める第四復号部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、前記公開鍵ekTを用いて、前記暗号文CTT及び前記第二鍵生成アドホック秘密鍵rTBを暗号化し、鍵KTを生成する第四暗号化部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、前記公開鍵ekSAを用いて、前記第二暗号文CTSB及び前記第二暗号文生成秘密鍵rSBを暗号化し、鍵KSを生成する第五暗号化部と、
前記第一鍵KA、前記第二鍵KB、前記鍵KT及び前記鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第二パラメータ生成部と、
前記疑似ランダム関数Gにより、セッション識別子と、前記共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第二共通鍵生成部とを含む、
鍵交換システム。
【請求項２】
請求項１の鍵交換システムであって、
κをセキュリティパラメータ、FSを疑似ランダム関数の鍵空間、|FS|=κ、G:{0,1}*×FS→{0,1}κを疑似ランダム関数、KSをKEM鍵の空間、Saltをソルト空間、KDF:Salt×KS→FSをランダムに選んだ公開ソルトs∈Saltを用いる鍵導出関数、Ext:SS×KS→FSをランダムに選んだ公開シードs'を用いる強ランダム抽出器とし、
疑似ランダム関数G、鍵導出関数KDF及び公開ソルトs、または、強ランダム抽出器Ext及びシードs'を共通公開パラメータとし、
前記第一パラメータ生成部及び前記第二パラメータ生成部は、
K'1←KDF(s,KA)
K'2←KDF(s,KB)
K'3←KDF(s,KT)
K'4←KDF(s,KS)
または
K'1←Ext(s',KA)
K'2←Ext(s',KB)
K'3←Ext(s',KT)
K'4←Ext(s',KS)
により、前記共通鍵生成パラメータK'1、K'2、K'3及びK'4を求め、
前記第一共通鍵生成部及び前記第二共通鍵生成部は、UA及びUAをそれぞれ第一鍵交換装置及び第二鍵交換装置の操作者の識別子とし、セッション識別子ST=(UA,UB,SPKA,SPKB,CTA,ekT,CTB,CTT)を用いて、
【数１６】
0005945525.tif 000017
により、前記共通鍵SKを生成する、
鍵交換システム。
【請求項３】
請求項１または２の鍵交換システムであって、
前記鍵カプセル化メカニズムは、選択暗号文攻撃に対して識別不可能であり、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムは、選択平文攻撃に対して識別不可能である、
鍵交換システム。
【請求項４】
他の装置との間で共通の共通鍵を共有する鍵交換装置であって、
秘密鍵dkAは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSAは、暗号文を公開鍵の情報無しで生成できる公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第一暗号文生成秘密鍵rSAは暗号文生成の乱数空間RSEからランダムに選択され、第一暗号文CTSAは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第一暗号文生成秘密鍵rSAが暗号化されて生成されるものであり、秘密鍵dkAと秘密鍵dkSAと第一暗号文生成秘密鍵rSAとを含む第一長期秘密鍵SSKAが、前記鍵交換装置以外の鍵交換装置に対して秘密にされ、前記秘密鍵dkAに対応する公開鍵ekAと前記秘密鍵dkSAに対応する公開鍵ekSAと第一暗号文CTSAとを含む第一長期公開鍵SPKAとが、前記他の装置に対してアクセス可能にされるものとし、
秘密鍵dkBは前記鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSBは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第二暗号文生成秘密鍵rSBは暗号文生成の乱数空間RSEからランダムに選択され、第二暗号文CTSBは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第二暗号文生成秘密鍵rSBが暗号化されて生成されるものであり、秘密鍵dkBと秘密鍵dkSBと第二暗号文生成秘密鍵rSBとを含む第二長期秘密鍵SSKBを秘密にされ、前記秘密鍵dkBに対応する公開鍵ekBと前記秘密鍵dkSBに対応する公開鍵ekSBと第二暗号文CTSBとを含む第二長期公開鍵SPKBを前記鍵交換装置に対してアクセス可能にされるものとし、
暗号文生成の乱数空間RSEからランダムに第一暗号文生成アドホック秘密鍵rAを選択し、鍵生成の乱数空間RSGからランダムに第一鍵生成アドホック秘密鍵rTAを選択する第一秘密鍵選択部と、
前記他の装置にアクセス可能に記憶される第二長期公開鍵SPKBに含まれる公開鍵ekBを用いて、前記鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第一暗号文生成アドホック秘密鍵rAを暗号化し、第一暗号文CTAと第一鍵KAとの組を生成する第一暗号化部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより、前記第一鍵生成アドホック秘密鍵rTAを用いて、公開鍵ekTと秘密鍵dkTとの組を生成する鍵生成部と、
前記秘密鍵dkAを用いて、前記鍵カプセル化メカニズムの復号アルゴリズムにより、前記他の装置から受信する第二暗号文CTBを復号し、第二鍵KBを求める第一復号部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、前記秘密鍵dkTを用いて、前記他の装置から受信する暗号文CTTを復号し、鍵KTを求める第二復号部と、
前記秘密鍵dkSAを用いて、前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、第二暗号文生成秘密鍵rSBが暗号化されて生成される第二暗号文CTSBを復号し、鍵KSを求める第三復号部と、
前記第一鍵KA、前記第二鍵KB、前記鍵KT及び前記鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第一パラメータ生成部と、
疑似ランダム関数Gにより、セッション識別子と、前記共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第一共通鍵生成部とを含む、
鍵交換装置。
【請求項５】
他の装置との間で共通の共通鍵を共有する鍵交換装置であって、
秘密鍵dkAは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSAは、暗号文を公開鍵の情報無しで生成できる公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第一暗号文生成秘密鍵rSAは暗号文生成の乱数空間RSEからランダムに選択され、第一暗号文CTSAは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第一暗号文生成秘密鍵rSAが暗号化されて生成されるものであり、秘密鍵dkAと秘密鍵dkSAと第一暗号文生成秘密鍵rSAとを含む第一長期秘密鍵SSKAが、前記他の装置以外の鍵交換装置に対して秘密にされ、前記秘密鍵dkAに対応する公開鍵ekAと前記秘密鍵dkSAに対応する公開鍵ekSAと第一暗号文CTSAとを含む第一長期公開鍵SPKAとが、前記鍵交換装置に対してアクセス可能にされるものとし、
秘密鍵dkBは前記鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSBは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第二暗号文生成秘密鍵rSBは暗号文生成の乱数空間RSEからランダムに選択され、第二暗号文CTSBは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第二暗号文生成秘密鍵rSBが暗号化されて生成されるものであり、秘密鍵dkBと秘密鍵dkSBと第二暗号文生成秘密鍵rSBとを含む第二長期秘密鍵SSKBを秘密にされ、前記秘密鍵dkBに対応する公開鍵ekBと前記秘密鍵dkSBに対応する公開鍵ekSBと第二暗号文CTSBとを含む第二長期公開鍵SPKBを前記他の装置に対してアクセス可能にされるものとし、
暗号文生成の乱数空間RSEからランダムに第二暗号文生成アドホック秘密鍵rBを選択し、暗号文生成の乱数空間RSEからランダムに第二鍵生成アドホック秘密鍵rTBを選択する第二秘密鍵選択部と、
前記公開鍵ekAを用いて、前記鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第二暗号文生成アドホック秘密鍵rBを暗号化し、第二暗号文CTBと第二鍵KBとの組を生成する第二暗号化部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより、前記第二鍵生成アドホック秘密鍵rTBを暗号化し、前記暗号文CTTを生成する第三暗号化部と、
前記秘密鍵dkBを用いて、前記鍵カプセル化メカニズムの復号アルゴリズムにより、前記他の装置から受信する第一暗号文CTAを復号し、第一鍵KAを求める第四復号部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、前記他の装置から受信する公開鍵ekTを用いて、前記暗号文CTT及び前記第二鍵生成アドホック秘密鍵rTBを暗号化し、鍵KTを生成する第四暗号化部と、
前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、前記公開鍵ekSAを用いて、前記第二暗号文CTSB及び前記第二暗号文生成秘密鍵rSBを暗号化し、鍵KSを生成する第五暗号化部と、
前記第一鍵KA、前記第二鍵KB、前記鍵KT及び前記鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第二パラメータ生成部と、
前記疑似ランダム関数Gにより、セッション識別子と、前記共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第二共通鍵生成部とを含む、
鍵交換装置。
【請求項６】
第一鍵交換装置と第二鍵交換装置との間で共通の共通鍵を共有するための鍵交換方法であって、
秘密鍵dkAは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSAは、暗号文を公開鍵の情報無しで生成できる公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第一暗号文生成秘密鍵rSAは暗号文生成の乱数空間RSEからランダムに選択され、第一暗号文CTSAは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第一暗号文生成秘密鍵rSAが暗号化されて生成されるものであり、秘密鍵dkAと秘密鍵dkSAと第一暗号文生成秘密鍵rSAとを含む第一長期秘密鍵SSKAが、前記第一鍵交換装置以外の鍵交換装置に対して秘密にされ、前記秘密鍵dkAに対応する公開鍵ekAと前記秘密鍵dkSAに対応する公開鍵ekSAと第一暗号文CTSAとを含む第一長期公開鍵SPKAとが、前記第二鍵交換装置に対してアクセス可能にされるものとし、
秘密鍵dkBは前記鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSBは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第二暗号文生成秘密鍵rSBは暗号文生成の乱数空間RSEからランダムに選択され、第二暗号文CTSBは前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第二暗号文生成秘密鍵rSBが暗号化されて生成されるものであり、秘密鍵dkBと秘密鍵dkSBと第二暗号文生成秘密鍵rSBとを含む第二長期秘密鍵SSKBを秘密にされ、前記秘密鍵dkBに対応する公開鍵ekBと前記秘密鍵dkSBに対応する公開鍵ekSBと第二暗号文CTSBとを含む第二長期公開鍵SPKBを前記第一鍵交換装置に対してアクセス可能にされるものとし、
前記第一鍵交換装置が、暗号文生成の乱数空間RSEからランダムに第一暗号文生成アドホック秘密鍵rAを選択し、鍵生成の乱数空間RSGからランダムに第一鍵生成アドホック秘密鍵rTAを選択する第一秘密鍵選択ステップと、
前記第一鍵交換装置が、前記第二鍵交換装置にアクセス可能に記憶される第二長期公開鍵SPKBに含まれる公開鍵ekBを用いて、前記鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第一暗号文生成アドホック秘密鍵rAを暗号化し、第一暗号文CTAと第一鍵KAとの組を生成する第一暗号化ステップと、
前記第一鍵交換装置が、前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより、前記第一鍵生成アドホック秘密鍵rTAを用いて、公開鍵ekTと秘密鍵dkTとの組を生成する鍵生成ステップと、
前記第二鍵交換装置が、暗号文生成の乱数空間RSEからランダムに第二暗号文生成アドホック秘密鍵rBを選択し、暗号文生成の乱数空間RSEからランダムに第二鍵生成アドホック秘密鍵rTBを選択する第二秘密鍵選択ステップと、
前記第二鍵交換装置が、前記公開鍵ekAを用いて、前記鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第二暗号文生成アドホック秘密鍵rBを暗号化し、第二暗号文CTBと第二鍵KBとの組を生成する第二暗号化ステップと、
前記第二鍵交換装置が、前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより、前記第二鍵生成アドホック秘密鍵rTBを暗号化し、前記暗号文CTTを生成する第三暗号化ステップと、
前記第一鍵交換装置が、前記秘密鍵dkAを用いて、前記鍵カプセル化メカニズムの復号アルゴリズムにより、前記第二鍵交換装置から受信する第二暗号文CTBを復号し、第二鍵KBを求める第一復号ステップと、
前記第一鍵交換装置が、前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、前記秘密鍵dkTを用いて、前記第二鍵交換装置から受信する暗号文CTTを復号し、鍵KTを求める第二復号ステップと、
前記第一鍵交換装置が、前記秘密鍵dkSAを用いて、前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、第二暗号文生成秘密鍵rSBが暗号化されて生成される第二暗号文CTSBを復号し、鍵KSを求める第三復号ステップと、
前記第一鍵交換装置が、前記第一鍵KA、前記第二鍵KB、前記鍵KT及び前記鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第一パラメータ生成ステップと、
前記第一鍵交換装置が、疑似ランダム関数Gにより、セッション識別子と、前記共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第一共通鍵生成ステップと、
前記第二鍵交換装置が、前記秘密鍵dkBを用いて、前記鍵カプセル化メカニズムの復号アルゴリズムにより、前記第一暗号文CTAを復号し、第一鍵KAを求める第四復号ステップと、
前記第二鍵交換装置が、前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、前記公開鍵ekTを用いて、前記暗号文CTT及び前記第二鍵生成アドホック秘密鍵rTBを暗号化し、鍵KTを生成する第四暗号化ステップと、
前記第二鍵交換装置が、前記公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、前記公開鍵ekSAを用いて、前記第二暗号文CTSB及び前記第二暗号文生成秘密鍵rSBを暗号化し、鍵KSを生成する第五暗号化ステップと、
前記第二鍵交換装置が、前記第一鍵KA、前記第二鍵KB、前記鍵KT及び前記鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第二パラメータ生成ステップと、
前記第二鍵交換装置が、前記疑似ランダム関数Gにより、セッション識別子と、前記共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第二共通鍵生成ステップとを含む、
鍵交換方法。
【請求項７】
請求項５の鍵交換方法であって、
κをセキュリティパラメータ、FSを疑似ランダム関数の鍵空間、|FS|=κ、G:{0,1}*×FS→{0,1}κを疑似ランダム関数、KSをKEM鍵の空間、Saltをソルト空間、KDF:Salt×KS→FSをランダムに選んだ公開ソルトs∈Saltを用いる鍵導出関数、Ext:SS×KS→FSをランダムに選んだ公開シードs'を用いる強ランダム抽出器とし、
疑似ランダム関数G、鍵導出関数KDF及び公開ソルトs、または、強ランダム抽出器Ext及びシードs'を共通公開パラメータとし、
前記第一パラメータ生成ステップ及び前記第二パラメータ生成ステップは、
K'1←KDF(s,KA)
K'2←KDF(s,KB)
K'3←KDF(s,KT)
K'4←KDF(s,KS)
または
K'1←Ext(s',KA)
K'2←Ext(s',KB)
K'3←Ext(s',KT)
K'4←Ext(s',KS)
により、前記共通鍵生成パラメータK'1、K'2、K'3及びK'4を求め、
前記第一共通鍵生成ステップ及び前記第二共通鍵生成ステップは、UA及びUAをそれぞれ第一鍵交換装置及び第二鍵交換装置の操作者の識別子とし、セッション識別子ST=(UA,UB,SPKA,SPKB,CTA,ekT,CTB,CTT)を用いて、
【数１７】
0005945525.tif 000018
により、前記共通鍵SKを生成する、
鍵交換方法。
【請求項８】
請求項４または５の鍵交換装置として、コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に、二者間で共通の共通鍵を共有する鍵交換方式に関する。
【背景技術】
【０００２】
二者間で共通のセッション鍵を共有する鍵交換方式として、鍵カプセル化メカニズムに基づく鍵交換方式のFSXY方式が知られている（非特許文献１参照）。
【０００３】
以下、図１を用いて従来技術の概要を説明する。
[定義]
κをセキュリティパラメータとする。
【０００４】
F={Fκ:Domκ×FSκ→Rngκ}κを定義域{Domκ}κ、鍵空間{FSκ}κ、値域{Rngκ}κを持つ関数族とする。このとき、もし多項式時間の識別者Dに対して、関数族Fκと真性ランダム関数RFκ:Domκ→Rngκが見分けられなければ、F={Fκ}κを疑似ランダム関数と呼ぶ。
【０００５】
Ext:S×X→Yを有限シード空間S、有限定義域X、有限値域Yを持つ関数とする。このとき、もしH∞(DX)≧kとなるX上の任意分布DXに対して、Δ((US,Ext(US,DX)),(US,UY))≦neglが成り立つならば、Extを強ランダム抽出器と呼ぶ。ただし、kは予め定められた所定の値であり、例えば、k=κとする。H∞は最小エントロピーを表す。また、Δ（X,Y）は確率変数XとYの統計的距離を表す。統計的距離の詳細については非特許文献２を参照されたい。US,UX,UYはそれぞれS,X,Y上の一様分布を表し、|X|=n≧k、|Y|=k、|S|=dとする。neglは漸近的に無視できる程度に十分に小さな値である。|・|は集合・の長さ（言い換えると、集合・に含まれる元を表す際に必要となる情報量、例えば、対応するビット長）を表す。dは強ランダム抽出器Extに対して求められる安全性等により定まる所定の値である。
【０００６】
(KeyGen,EnCap,DeCap)を選択暗号文攻撃に対して識別不可能な鍵カプセル化メカニズム（「key encapsulation mechanism」、以下「KEM」ともいう）とする。KEMは、共通鍵暗号方式で用いる共通鍵を公開鍵暗号方式で暗号化し、二者間で鍵共有を行うためのメカニズムである。KEMについての詳細は非特許文献２を参照されたい。(wKeyGen,wEnCap,wDeCap)を選択平文攻撃に対して識別不可能な(「indistinguishable against chosen plaintext attacks 」、以下「IND-CPA」ともいう)KEMとする。なお、選択暗号文攻撃に対して識別不可能な(「indistinguishable against chosen ciphertext attacks 」、以下「IND-CCA」ともいう)KEMをIND-CCA secure KEMともいい、選択平文攻撃に対して識別不可能な(「indistinguishable against chosen plaintext attacks 」、以下「IND-CPA」ともいう)KEMをIND-CPA secure KEMともいう。
【０００７】
鍵生成アルゴリズムKeyGen及びwKeyGenは、セキュリティパラメータκとrg∈RSG（RSGは鍵生成の乱数空間）とを入力とし、公開鍵ekと秘密鍵dkとを出力する。
【０００８】
鍵カプセル化アルゴリズムEnCap及びwEnCapは、公開鍵ekとre∈RSE（RSEは鍵カプセル化の乱数空間）を入力とし、KEM鍵K∈KS（KSはKEM鍵空間）と暗号文CT∈CS（CSは暗号文空間）を出力する。
【０００９】
復号アルゴリズムDeCap及びwDeCapは秘密鍵dkと暗号文CT∈CSとを入力とし、KEM鍵K∈KSを出力する。
【００１０】
[共通公開パラメータ]
F:{0,1}*×FS→RSE、F':{0,1}*×FS→RSE、G:{0,1}*×FS→{0,1}κをそれぞれ疑似ランダム関数とする。ただし、FSは疑似ランダム関数の鍵空間（|FS|=κ）、RSEは鍵カプセル化アルゴリズムの乱数空間、RSGは鍵生成アルゴリズムの乱数空間とする。Ext:SS×KS→FSをランダムに選んだシードs∈SSを用いる強ランダム抽出器とする。ただし、SSをシード空間、KSをKEM鍵の空間とする。
疑似ランダム関数F、F'及びG、強ランダム抽出器Ext、並びに、シードsを共通公開パラメータとする（図１参照）。
【００１１】
[長期公開鍵と長期秘密鍵]
ユーザUIはランダムにσI∈FSとrI∈RSGを選び、鍵生成アルゴリズムより(ekI,dkI)←KeyGen(1κ,rI)を得る。UIの長期秘密鍵と長期公開鍵を((dkI,σI),ekI)とする。
【００１２】
[鍵交換]
ユーザUAは長期秘密鍵と長期公開鍵((dkA,σA),ekA)を持ち、ユーザUBは長期秘密鍵と長期公開鍵((dkB,σB),ekB)を持つ。
【００１３】
1.
ユーザUAはランダムにアドホック秘密鍵rA,r'A∈FSとrTA∈RSGを選び、暗号文CTAとKEM鍵KAとを次式により求める。
【数１】
0005945525.tif 000002
【００１４】
さらに、セキュリティパラメータκとアドホック秘密鍵rTAを入力として、公開鍵ekTと秘密鍵dkTとを次式により計算する。
(ekT,dkT)←wKeyGen(1κ,rTA)
【００１５】
ユーザUAは求めた(UA,UB,CTA,ekT)をユーザUBに送信する。ただし、
【数２】
0005945525.tif 000003
は、排他的論理和を表す。なお、UIはユーザの識別子であり、ユーザの名前やメールアドレス、鍵交換方式のために用意した文字を含む記号列等の識別子、ユーザの操作する端末の識別子であってもよい。要は、ユーザを特定するための識別子であれば、どのようなものでもよく、利用方法に応じて適宜設定すればよい。
【００１６】
2.
(UA,UB,CTA,ekT)を受け取ったら、ユーザUBはランダムにアドホック秘密鍵rB,r'B∈FSとrTB∈RSEをと選ぶ。次に、アドホック秘密鍵rB,r'B、長期秘密鍵(dkB,σB)を用いて次式により暗号文CTBとKEM鍵KBとを計算する。
【数３】
0005945525.tif 000004
【００１７】
さらに、ユーザUBは、アドホック秘密鍵rB,r'B、長期秘密鍵(dkB,σB)を用いて次式により暗号文CTBとKEM鍵KBとを計算する。
【数４】
0005945525.tif 000005
【００１８】
ユーザUBは、(UA,UB,CTB,CTT)をユーザUAに送信する。さらに、UBは、
【数５】
0005945525.tif 000006
を計算し、セッション識別子ST=(UA,UB,ekA,ekB,CTA,ekT,CTB,CTT)を用いて、セッション鍵
【数６】
0005945525.tif 000007
を導出する。セッション鍵SKの生成に係るセッションを終了し、その際の全てのセッション情報を削除する。
【００１９】
3.
ユーザUAは、(UA,UB,CTB,CTT)を受け取ったら、
【数７】
0005945525.tif 000008
を計算し、セッション識別子ST=(UA,UB,ekA,ekB,CTA,ekT,CTB,CTT)を用いて、セッション鍵
【数８】
0005945525.tif 000009
を導出する。セッション鍵SKの生成に係るセッションを終了し、その際の全てのセッション情報を削除する。
【００２０】
ユーザUA及びUBは、セッション鍵SKを用いて、データ暗号化し、安全に通信することができる。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】Fujioka, A., Suzuki, K., Xagawa, K., Yoneyama, K., "Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices", In:Public Key Cryptography 2012, 2012, pp.467-484.
【非特許文献２】D. Moriyama, R. Nishimaki, and T. Okamoto. “公開鍵暗号の数理” 共立出版, 2011.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
非特許文献１の従来技術には、セッションにおけるオンライン計算の一部を耐タンパモジュールの内部で行わなくてはならないという問題点がある。以下、具体的に問題点を述べる。
【００２３】
非特許文献１の従来技術は、各秘密情報の漏洩に強い。例えば、ユーザUAとUBのアドホック秘密鍵rA,r'A,rTA,rB,r'B,rTBが漏洩しても、長期秘密鍵(dkA,σA),(dkB,σB)が同時に漏洩しない限り、
【数９】
0005945525.tif 000010
の値が分からないため、セッション鍵SKの値に関する情報は一切漏れないことが証明できる。よって、アドホック秘密鍵rA,r'A,rTA,rB,r'B,rTBの生成を耐タンパモジュール（例：SIMカード）内ではなく、ホストマシン（例：スマートフォン）のメモリ上で行っても安全性が保証される。しかし、全ての計算をホストマシンで行うことはできない。ユーザUAは、
【数１０】
0005945525.tif 000011
を、ユーザUBは、
【数１１】
0005945525.tif 000012
を途中で計算する必要がある。もしこれらの値が漏洩した場合、この方式は安全ではない。よって、実装する場合にはこれらの値は耐タンパモジュール内で計算されなければならない。
【００２４】
しかし、一般に耐タンパモジュールは高コストなため、内蔵される計算資源が乏しく、頻繁にオンライン計算を行う環境では実行のボトルネックとなってしまう。よって、耐タンパモジュール内でオンライン計算を行うこと無く安全な方式が望ましい。
【００２５】
本発明は、耐タンパモジュール内でオンライン計算を行うこと無く安全な方式を用いる鍵交換システム、鍵交換装置、その方法、及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２６】
上記の課題を解決するために、本発明の第一の態様によれば、鍵交換システムは、第一鍵交換装置と第二鍵交換装置とを含み、第一鍵交換装置と第二鍵交換装置との間で共通の共通鍵を共有する。秘密鍵dkAは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSAは、暗号文を公開鍵の情報無しで生成できる公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第一暗号文生成秘密鍵rSAは暗号文生成の乱数空間RSEからランダムに選択され、第一暗号文CTSAは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第一暗号文生成秘密鍵rSAが暗号化されて生成されるものであり、秘密鍵dkAと秘密鍵dkSAと第一暗号文生成秘密鍵rSAとを含む第一長期秘密鍵SSKAが、第一鍵交換装置以外の鍵交換装置に対して秘密にされ、秘密鍵dkAに対応する公開鍵ekAと秘密鍵dkSAに対応する公開鍵ekSAと第一暗号文CTSAとを含む第一長期公開鍵SPKAとが、第二鍵交換装置に対してアクセス可能にされるものとし、秘密鍵dkBは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSBは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第二暗号文生成秘密鍵rSBは暗号文生成の乱数空間RSEからランダムに選択され、第二暗号文CTSBは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第二暗号文生成秘密鍵rSBが暗号化されて生成されるものであり、秘密鍵dkBと秘密鍵dkSBと第二暗号文生成秘密鍵rSBとを含む第二長期秘密鍵SSKBを秘密にされ、秘密鍵dkBに対応する公開鍵ekBと秘密鍵dkSBに対応する公開鍵ekSBと第二暗号文CTSBとを含む第二長期公開鍵SPKBを第一鍵交換装置に対してアクセス可能にされるものとする。第一鍵交換装置は、暗号文生成の乱数空間RSEからランダムに第一暗号文生成アドホック秘密鍵rAを選択し、鍵生成の乱数空間RSGからランダムに第一鍵生成アドホック秘密鍵rTAを選択する第一秘密鍵選択部と、第二鍵交換装置にアクセス可能に記憶される第二長期公開鍵SPKBに含まれる公開鍵ekBを用いて、鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第一暗号文生成アドホック秘密鍵rAを暗号化し、第一暗号文CTAと第一鍵KAとの組を生成する第一暗号化部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより、第一鍵生成アドホック秘密鍵rTAを用いて、公開鍵ekTと秘密鍵dkTとの組を生成する鍵生成部と、秘密鍵dkAを用いて、鍵カプセル化メカニズムの復号アルゴリズムにより、第二鍵交換装置から受信する第二暗号文CTBを復号し、第二鍵KBを求める第一復号部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、秘密鍵dkTを用いて、第二鍵交換装置から受信する暗号文CTTを復号し、鍵KTを求める第二復号部と、秘密鍵dkSAを用いて、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、第二暗号文生成秘密鍵rSBが暗号化されて生成される第二暗号文CTSBを復号し、鍵KSを求める第三復号部と、第一鍵KA、第二鍵KB、鍵KT及び鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第一パラメータ生成部と、疑似ランダム関数Gにより、セッション識別子と、共通鍵生成パラメータK'1、K'2、K'3��びK'4とを用いて共通鍵SKを生成する第一共通鍵生成部とを含む。第二鍵交換装置は、暗号文生成の乱数空間RSEからランダムに第二暗号文生成アドホック秘密鍵rBを選択し、暗号文生成の乱数空間RSEからランダムに第二鍵生成アドホック秘密鍵rTBを選択する第二秘密鍵選択部と、公開鍵ekAを用いて、鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第二暗号文生成アドホック秘密鍵rBを暗号化し、第二暗号文CTBと第二鍵KBとの組を生成する第二暗号化部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより、第二鍵生成アドホック秘密鍵rTBを暗号化し、暗号文CTTを生成する第三暗号化部と、秘密鍵dkBを用いて、鍵カプセル化メカニズムの復号アルゴリズムにより、第一暗号文CTAを復号し、第一鍵KAを求める第四復号部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、公開鍵ekTを用いて、暗号文CTT及び第二鍵生成アドホック秘密鍵rTBを暗号化し、鍵KTを生成する第四暗号化部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、公開鍵ekSAを用いて、第二暗号文CTSB及び第二暗号文生成秘密鍵rSBを暗号化し、鍵KSを生成する第五暗号化部と、第一鍵KA、第二鍵KB、鍵KT及び鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第二パラメータ生成部と、疑似ランダム関数Gにより、セッション識別子と、共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第二共通鍵生成部とを含む。
【００２７】
上記の課題を解決するために、本発明の他の態様によれば、鍵交換装置は、他の装置との間で共通の共通鍵を共有する。鍵交換装置は、秘密鍵dkAは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSAは、暗号文を公開鍵の情報無しで生成できる公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第一暗号文生成秘密鍵rSAは暗号文生成の乱数空間RSEからランダムに選択され、第一暗号文CTSAは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第一暗号文生成秘密鍵rSAが暗号化されて生成されるものであり、秘密鍵dkAと秘密鍵dkSAと第一暗号文生成秘密鍵rSAとを含む第一長期秘密鍵SSKAが、鍵交換装置以外の鍵交換装置に対して秘密にされ、秘密鍵dkAに対応する公開鍵ekAと秘密鍵dkSAに対応する公開鍵ekSAと第一暗号文CTSAとを含む第一長期公開鍵SPKAとが、他の装置に対してアクセス可能にされるものとし、秘密鍵dkBは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSBは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第二暗号文生成秘密鍵rSBは暗号文生成の乱数空間RSEからランダムに選択され、第二暗号文CTSBは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第二暗号文生成秘密鍵rSBが暗号化されて生成されるものであり、秘密鍵dkBと秘密鍵dkSBと第二暗号文生成秘密鍵rSBとを含む第二長期秘密鍵SSKBを秘密にされ、秘密鍵dkBに対応する公開鍵ekBと秘密鍵dkSBに対応する公開鍵ekSBと第二暗号文CTSBとを含む第二長期公開鍵SPKBを鍵交換装置に対してアクセス可能にされるものとする。鍵交換装置は、暗号文生成の乱数空間RSEからランダムに第一暗号文生成アドホック秘密鍵rAを選択し、鍵生成の乱数空間RSGからランダムに第一鍵生成アドホック秘密鍵rTAを選択する第一秘密鍵選択部と、他の装置にアクセス可能に記憶される第二長期公開鍵SPKBに含まれる公開鍵ekBを用いて、鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第一暗号文生成アドホック秘密鍵rAを暗号化し、第一暗号文CTAと第一鍵KAとの組を生成する第一暗号化部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより、第一鍵生成アドホック秘密鍵rTAを用いて、公開鍵ekTと秘密鍵dkTとの組を生成する鍵生成部と、秘密鍵dkAを用いて、鍵カプセル化メカニズムの復号アルゴリズムにより、他の装置から受信する第二暗号文CTBを復号し、第二鍵KBを求める第一復号部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、秘密鍵dkTを用いて、他の装置から受信する暗号文CTTを復号し、鍵KTを求める第二復号部と、秘密鍵dkSAを用いて、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、第二暗号文生成秘密鍵rSBが暗号化されて生成される第二暗号文CTSBを復号し、鍵KSを求める第三復号部と、第一鍵KA、第二鍵KB、鍵KT及び鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第一パラメータ生成部と、疑似ランダム関数Gにより、セッション識別子と、共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第一共通鍵生成部とを含む。
【００２８】
上記の課題を解決するために、本発明の他の態様によれば、鍵交換装置は、他の装置との間で共通の共通鍵を共有する。秘密鍵dkAは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSAは、暗号文を公開鍵の情報無しで生成できる公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第一暗号文生成秘密鍵rSAは暗号文生成の乱数空間RSEからランダムに選択され、第一暗号文CTSAは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第一暗号文生成秘密鍵rSAが暗号化されて生成されるものであり、秘密鍵dkAと秘密鍵dkSAと第一暗号文生成秘密鍵rSAとを含む第一長期秘密鍵SSKAが、他の装置以外の鍵交換装置に対して秘密にされ、秘密鍵dkAに対応する公開鍵ekAと秘密鍵dkSAに対応する公開鍵ekSAと第一暗号文CTSAとを含む第一長期公開鍵SPKAとが、鍵交換装置に対してアクセス可能にされるものとし、秘密鍵dkBは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSBは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第二暗号文生成秘密鍵rSBは暗号文生成の乱数空間RSEからランダムに選択され、第二暗号文CTSBは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第二暗号文生成秘密鍵rSBが暗号化されて生成されるものであり、秘密鍵dkBと秘密鍵dkSBと第二暗号文生成秘密鍵rSBとを含む第二長期秘密鍵SSKBを秘密にされ、秘密鍵dkBに対応する公開鍵ekBと秘密鍵dkSBに対応する公開鍵ekSBと第二暗号文CTSBとを含む第二長期公開鍵SPKBを他の装置に対してアクセス可能にされるものとする。鍵交換装置は、暗号文生成の乱数空間RSEからランダムに第二暗号文生成アドホック秘密鍵rBを選択し、暗号文生成の乱数空間RSEからランダムに第二鍵生成アドホック秘密鍵rTBを選択する第二秘密鍵選択部と、公開鍵ekAを用いて、鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第二暗号文生成アドホック秘密鍵rBを暗号化し、第二暗号文CTBと第二鍵KBとの組を生成する第二暗号化部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより、第二鍵生成アドホック秘密鍵rTBを暗号化し、暗号文CTTを生成する第三暗号化部と、秘密鍵dkBを用いて、鍵カプセル化メカニズムの復号アルゴリズムにより、他の装置から受信する第一暗号文CTAを復号し、第一鍵KAを求める第四復号部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、他の装置から受信する公開鍵ekTを用いて、暗号文CTT及び第二鍵生成アドホック秘密鍵rTBを暗号化し、鍵KTを生成する第四暗号化部と、公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、公開鍵ekSAを用いて、第二暗号文CTSB及び第二暗号文生成秘密鍵rSBを暗号化し、鍵KSを生成する第五暗号化部と、第一鍵KA、第二鍵KB、鍵KT及び鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第二パラメータ生成部と、疑似ランダム関数Gにより、セッション識別子と、共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第二共通鍵生成部とを含む。
【００２９】
上記の課題を解決するために、本発明の他の態様によれば、鍵交換方法は、第一鍵交換装置と第二鍵交換装置との間で共通の共通鍵を共有するためのものである。秘密鍵dkAは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSAは、暗号文を公開鍵の情報無しで生成できる公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第一暗号文生成秘密鍵rSAは暗号文生成の乱数空間RSEからランダムに選択され、第一暗号文CTSAは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第一暗号文生成秘密鍵rSAが暗号化されて生成されるものであり、秘密鍵dkAと秘密鍵dkSAと第一暗号文生成秘密鍵rSAとを含む第一長期秘密鍵SSKAが、第一鍵交換装置以外の鍵交換装置に対して秘密にされ、秘密鍵dkAに対応する公開鍵ekAと秘密鍵dkSAに対応する公開鍵ekSAと第一暗号文CTSAとを含む第一長期公開鍵SPKAとが、第二鍵交換装置に対してアクセス可能にされるものとし、秘密鍵dkBは鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、秘密鍵dkSBは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより生成され、第二暗号文生成秘密鍵rSBは暗号文生成の乱数空間RSEからランダムに選択され、第二暗号文CTSBは公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより第二暗号文生成秘密鍵rSBが暗号化されて生成されるものであり、秘密鍵dkBと秘密鍵dkSBと第二暗号文生成秘密鍵rSBとを含む第二長期秘密鍵SSKBを秘密にされ、秘密鍵dkBに対応する公開鍵ekBと秘密鍵dkSBに対応する公開鍵ekSBと第二暗号文CTSBとを含む第二長期公開鍵SPKBを第一鍵交換装置に対してアクセス可能にされるものとする。鍵交換方法は、第一鍵交換装置が、暗号文生成の乱数空間RSEからランダムに第一暗号文生成アドホック秘密鍵rAを選択し、鍵生成の乱数空間RSGからランダムに第一鍵生成アドホック秘密鍵rTAを選択する第一秘密鍵選択ステップと、第一鍵交換装置が、第二鍵交換装置にアクセス可能に記憶される第二長期公開鍵SPKBに含まれる公開鍵ekBを用いて、鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第一暗号文生成アドホック秘密鍵rAを暗号化し、第一暗号文CTAと第一鍵KAとの組を生成する第一暗号化ステップと、第一鍵交換装置が、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの鍵生成アルゴリズムにより、第一鍵生成アドホック秘密鍵rTAを用いて、公開鍵ekTと秘密鍵dkTとの組を生成する鍵生成ステップと、第二鍵交換装置が、暗号文生成の乱数空間RSEからランダムに第二暗号文生成アドホック秘密鍵rBを選択し、暗号文生成の乱数空間RSEからランダムに第二鍵生成アドホック秘密鍵rTBを選択する第二秘密鍵選択ステップと、第二鍵交換装置が、公開鍵ekAを用いて、鍵カプセル化メカニズムの鍵カプセル化アルゴリズムにより、第二暗号文生成アドホック秘密鍵rBを暗号化し、第二暗号文CTBと第二鍵KBとの組を生成する第二暗号化ステップと、第二鍵交換装置が、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの暗号文生成アルゴリズムにより、第二鍵生成アドホック秘密鍵rTBを暗号化し、暗号文CTTを生成する第三暗号化ステップと、第一鍵交換装置が、秘密鍵dkAを用いて、鍵カプセル化メカニズムの復号ア���ゴリズムにより、第二鍵交換装置から受信する第二暗号文CTBを復号し、第二鍵KBを求める第一復号ステップと、第一鍵交換装置が、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、秘密鍵dkTを用いて、第二鍵交換装置から受信する暗号文CTTを復号し、鍵KTを求める第二復号ステップと、第一鍵交換装置が、秘密鍵dkSAを用いて、公開鍵独立暗号文生成可能鍵カプセル化メカニズムの復号アルゴリズムにより、第二暗号文生成秘密鍵rSBが暗号化されて生成される第二暗号文CTSBを復号し、鍵KSを求める第三復号ステップと、第一鍵交換装置が、第一鍵KA、第二鍵KB、鍵KT及び鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第一パラメータ生成ステップと、第一鍵交換装置が、疑似ランダム関数Gにより、セッション識別子と、共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第一共通鍵生成ステップと、第二鍵交換装置が、秘密鍵dkBを用いて、鍵カプセル化メカニズムの復号アルゴリズムにより、第一暗号文CTAを復号し、第一鍵KAを求める第四復号ステップと、第二鍵交換装置が、公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、公開鍵ekTを用いて、暗号文CTT及び第二鍵生成アドホック秘密鍵rTBを暗号化し、鍵KTを生成する第四暗号化ステップと、第二鍵交換装置が、公開鍵独立暗号文生成可能鍵カプセル化メカニズムのKEM鍵生成アルゴリズムにより、公開鍵ekSAを用いて、第二暗号文CTSB及び第二暗号文生成秘密鍵rSBを暗号化し、鍵KSを生成する第五暗号化ステップと、第二鍵交換装置が、第一鍵KA、第二鍵KB、鍵KT及び鍵KSを用いて、共通鍵生成パラメータK'1、K'2、K'3及びK'4を求める第二パラメータ生成ステップと、第二鍵交換装置が、疑似ランダム関数Gにより、セッション識別子と、共通鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて共通鍵SKを生成する第二共通鍵生成ステップとを含む。
【発明の効果】
【００３０】
本発明によれば、耐タンパモジュール内でオンライン計算を行うこと無く安全な方式を実現することができるという効果を奏する。
【図面の簡単な説明】
【００３１】
【図１】FSXY方式の処理の概要を説明するための図。
【図２】鍵交換システムの構成例を示す図。
【図３】第一鍵交換装置の機能ブロック図。
【図４】第二鍵交換装置の機能ブロック図。
【図５】鍵交換システム１の処理フローの例を示す図。
【発明を実施するための形態】
【００３２】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。以下の説明において、テキスト中で使用する記号「^」、「~」、「−」等は、本来直前の文字の真上に記載されるべきものであるが、テキスト記法の制限により、当該文字の直後に記載する。式中においてはこれらの記号は本来の位置に記述している。また、ベクトルや行列の各要素単位で行われる処理は、特に断りが無い限り、そのベクトルやその行列の全ての要素に対して適用されるものとする。
【００３３】
＜第一実施形態＞
本実施形態では、特殊なKEM（公開鍵独立暗号文生成可能KEM：「KEM with public-key-independent-ciphertext」、以下「PKIC-KEM」ともいう）を用いることで、耐タンパモジュール内でオンライン計算を行うこと無く安全な方式を実現する。
【００３４】
PKIC-KEMとは、暗号文を公開鍵の情報無しで生成できるKEMのことである。本実施形態では、IND-CPA secure KEM(wKeyGen,wEnCap,wDeCap)をIND-CPA secure PKIC-KEM(wKeyGen,wEnCapC,wEnCapK,wDeCap)に置き換える。
【００３５】
IND-CPA secure PKIC-KEMの鍵生成アルゴリズムwKeyGenと復号アルゴリズムwDeCapとは、通常のIND-CPA secure KEMと同一である。
【００３６】
IND-CPA secure PKIC-KEMの暗号文生成アルゴリズムwEnCapCは鍵交換システムの公開パラメータとre∈RSE（RSEは暗号文生成の乱数空間）を入力とし、暗号文CT∈CS（CSは暗号文空間）を出力する。
【００３７】
IND-CPA secure PKIC-KEMのKEM鍵生成アルゴリズムwEnCapKは公開鍵ek、暗号文CT、乱数reを入力とし、KEM鍵K∈KS（KSはKEM鍵空間）を出力する。このようなPKIC-KEMとして、例えば、参考文献１に詳細な構成法の１つが記述されている。
[参考文献１]Taher El Gamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms",  IEEE Transactions on Information Theory, 1985, vol. IT-31, no. 4, pp. 469-472.
【００３８】
各ユーザUPは、PKIC-KEMを用いて(ekSP,dkSP)←wKeyGen(1κ,r')とCTSP←wEnCapC(rSP)を事前に生成する。FSXY方式の長期秘密鍵(dkP,σP)に代えて、(dkP,dkSP,rSP)を長期秘密鍵に設定し、FSXY方式の長期公開鍵ekPに加えて、(ekSP,CTSP)を長期公開鍵に設定する。
【００３９】
また、FSXY方式の鍵交換セッションにおいて(KA,KB,KT)を共有していたが、本実施形態では、KSも共有する。なお、ユーザUAはKS←wDeCapdk_SA(CTSB)、ユーザUBはKS←wEnCapKek_SA(CTSB;rSB)のように計算してKSを共有する。ここで、KSはお互いの長期秘密鍵(dkA,dkSA,rSA)、(dkB,dkSB,rSB)と長期公開鍵(ekA,ekSA,CTSA)、(ekB,ekSB,CTSB)だけに依存した情報であるため、アドホック秘密鍵rA,rTA,rB,rTBが漏洩しても影響がない。よって、FSXY方式のように
【数１２】
0005945525.tif 000013
を計算しなくても、安全性が証明できる。そのため、耐タンパモジュール内でのオンライン計算を行う必要がない。
【００４０】
本実施形態の鍵交換方式を以下に示す。
[準備]
κをセキュリティパラメータとする。KDF:Salt×X→Yを有限ソルト空間Salt、有限定義域X、有限値域Yを持つ関数とする。このとき、もしH∞(DX)≧κとなるX上の任意分布DXと任意の多項式時間攻撃者Aとに対して、|Pr[y∈RRng;1←A(y)]-Pr[x∈RDom;s∈RSalt;y←KDF(s,x);1←A(y)]|≦neglが成り立つならば、KDFを鍵導出関数と呼ぶ。ただし、A(・)は攻撃者Aに対してある値・を与えたときの出力を表す。つまり、上記式は、有限値域Yの元yを攻撃者Aに対して与えたときに、値域Rngからランダムに元yを選ぶ確率と、KDFの入力をソルトsと有限定義域Xの元xとして元yを出力し、有限値域Yの元yを攻撃者Aに対して与えたときに、有限ソルト空間Saltからランダムにソルトsを選び、定義域Domからランダムに元xを選ぶ確率との差が、漸近的に無視できる程度に十分小さな値以下であることを表している。ただし、|X|=n≧k、|Y|=k、|Salt|=dとする。dは鍵導出関数KDFに対して求められる安全性等により定まる所定の値である。
【００４１】
＜鍵交換システム１＞
図２は、鍵交換システム１の構成例を示す図である。鍵交換システム１は、第一鍵交換装置１０と第二鍵交換装置２０とサーバ３０とを含む。各装置は、通信回線を介して接続されている。第一鍵交換装置１０と前記第二鍵交換装置２０とは、その間で共通の共通鍵（この実施形態では、セッション鍵SK）を共有する。
【００４２】
図３は、第一鍵交換装置１０の機能ブロック図である。第一鍵交換装置１０は、第一記憶部１１と、第一秘密鍵選択部１２と、第一暗号化部１３と、鍵生成部１４と、第一復号部１５と、第二復号部１６と、第三復号部１７と、第一パラメータ生成部１８と、第一セッション鍵生成部１９とを含む。
【００４３】
図４は、第二鍵交換装置２０の機能ブロック図である。第二鍵交換装置２０は、第二記憶部２１と、第二秘密鍵選択部２２と、第二暗号化部２３と、第三暗号化部２４と、第四復号部２５と、第四暗号化部２６と、第五暗号化部２７、第二パラメータ生成部２８と、第二セッション鍵生成部２９とを含む。
【００４４】
図５は、鍵交換システム１の処理フローの例を示す図である。
【００４５】
[公開パラメータ]
サーバ３０は、疑似ランダム関数G、鍵導出関数KDF、公開ソルトsを公開パラメータとして、第一鍵交換装置１０と前記第二鍵交換装置２０とがアクセスできるように、図示しない記憶部に記憶しておく。
【００４６】
疑似ランダム関数Gは、次のように表される。G:{0,1}*×FS→{0,1}κ。ただし、FSは疑似ランダム関数の鍵空間（|FS|=κ）とする。鍵導出関数KDFは、ランダムに選んだ公開ソルトs∈Saltを用い、次のように表される。KDF:Salt×KS→FS。ただし、Saltをソルト空間、KSをKEM鍵の空間とする。
【００４７】
＜長期公開鍵と長期秘密鍵＞
ユーザUPはランダムにr,r'∈RRSGとrSP∈RRSEを選び、鍵生成アルゴリズムより(ekP,dkP)←KeyGen(1κ,r)と(ekSP,dkSP)←wKeyGen(1κ,r')、暗号文生成アルゴリズムによりCTSP←wEnCapC(rSP)を計算する。UPの長期秘密鍵を(dkP,dkSP,rSP)、長期公開鍵を(ekP,ekSP,CTSP)とする。
【００４８】
[鍵交換]
＜第一記憶部１１及び第二記憶部２１＞
ユーザUAの操作する第一鍵交換装置１０は、r,r'∈RRSGとrSA∈RRSEを選び、IND-CCA secure KEMの鍵生成アルゴリズムにより(ekA,dkA)←KeyGen(1κ,r)を生成し、IND-CPA secure PKIC-KEMの鍵生成アルゴリズムにより(ekSA,dkSA)←wKeyGen(1κ,r')を生成する。さらに、IND-CPA secure PKIC-KEMの暗号文生成アルゴリズムによりCTSA←wEnCaAC(rSA)を計算する。第一鍵交換装置１０は、(dkA,dkSA,rSA)を第一長期秘密鍵SSKAとして第一記憶部１１に秘密に記憶し、(ekA,ekSA,CTSA)を第一長期公開鍵SPKAとして、第一記憶部１１またはサーバ３０に、第二鍵交換装置２０がアクセスできるように、記憶する。
【００４９】
同様に、ユーザUBの操作する第二鍵交換装置２０は、第二長期秘密鍵SSKB:=(dkB,dkSB,rSB)を生成し、第二記憶部２１に秘密に記憶し、第二長期公開鍵SPKB:=(ekB,ekSB,CTSB)を生成し、第二記憶部２１またはサーバ３０に、第一鍵交換装置１０がアクセスできるように、記憶する。
【００５０】
［第一鍵交換装置１０の処理の流れ（図３及び５参照）］
＜第一秘密鍵選択部１２＞
第一秘密鍵選択部１２は、暗号文生成の乱数空間RSEからランダムに第一暗号文生成アドホック秘密鍵rAを選択し（rA∈RRSE）、鍵生成の乱数空間RSGからランダムに第一鍵生成アドホック秘密鍵rTAを選択する（ｓ１１、rTA∈RRSG）。第一秘密鍵選択部１２は、第一暗号文生成アドホック秘密鍵rAと第一鍵生成アドホック秘密鍵rTAとを、第一記憶部１１に秘密に記憶する。
【００５１】
＜第一暗号化部１３＞
第一暗号化部１３は、第二長期公開鍵SPKBに含まれる第二IND-CCA公開鍵ekBを第二鍵交換装置２０またはサーバ３０から受け取る。第一暗号化部１３は、第二IND-CCA公開鍵ekBを用いて、IND-CCA secure KEMにより、第一記憶部１１から取り出した第一暗号文生成アドホック秘密鍵rAを暗号化し、第一IND-CCA暗号文CTAと第一IND-CCA鍵KAとの組を生成する（ｓ１２、(CTA,KA)←EnCapek_B(rA)）。第一暗号化部１３は、第一IND-CCA鍵KAを第一記憶部１１に秘密に記憶する。なお、「秘密」とは、対象となる情報にアクセスするための正当性を有さないものに対してアクセスできないようにすることを意味する。
【００５２】
＜鍵生成部１４＞
鍵生成部１４は、第一鍵生成アドホック秘密鍵rTAを第一記憶部１１から取り出す。鍵生成部１４は、IND-CPA secure PKIC-KEMにより、第一鍵生成アドホック秘密鍵rTAを用いて、IND-CPA公開鍵ekTとIND-CPA秘密鍵dkTとの組を生成する（ｓ１３、(ekT,dkT)←wKeyGen(1κ,rTA)）。鍵生成部１４は、IND-CPA秘密鍵dkTを第一記憶部１１に秘密に記憶する。
【００５３】
第一鍵交換装置１０は、図示しない送信部を介して、(UA,UB,CTA,ekT)を第二鍵交換装置２０に送信する。
さらに、第一鍵交換装置１０は、図示しない受信部を介して、(UA,UB,CTB,CTT)を第二鍵交換装置２０から受信する。CTB,CTTの詳細については後述する。
【００５４】
＜第一復号部１５＞
第一復号部１５は、第一記憶部１１から第一IND-CCA秘密鍵dkAを取り出し、これを用いて、IND-CCA secure KEMにより、第二鍵交換装置２０から受信した第二IND-CCA暗号文CTBを復号し、第二IND-CCA鍵KBを求める（ｓ１４、KB←DeCapdk_A(CTB)）。
【００５５】
＜第二復号部１６＞
第二復号部１６は、IND-CPA secure PKIC-KEMにより、第一記憶部１１からIND-CPA秘密鍵dkTを取り出し、これを用いて、第二鍵交換装置２０から受信したIND-CPA暗号文CTTを復号し、IND-CPA鍵KTを求める（ｓ１５、KT←wDeCapdk_T(CTT)）。
【００５６】
＜第三復号部１７＞
第三復号部１７は、第二鍵交換装置２０またはサーバ３０から第二IND-CPA暗号文CTSB（公開パラメータ）を受け取る。第三復号部１７は、第一記憶部１１から第一IND-CPA秘密鍵dkSAを取り出し、これを用いて、IND-CPA secure PKIC-KEMにより、第二IND-CPA暗号文CTSBを復号し、IND-CPA鍵KSを求める（ｓ１６、KS←wDeCapdk_SA(CTSB)）。
【００５７】
＜第一パラメータ生成部１８＞
第一パラメータ生成部１８は、サーバ３０から鍵導出関数KDF及び公開ソルトs（公開パラメータ）を受け取る。第一パラメータ生成部１８は、第一暗号化部１３、第一復号部１５、第二復号部１６及び第三復号部１７からそれぞれ第一IND-CCA鍵KA、第二IND-CCA鍵KB、IND-CPA鍵KT及びIND-CPA鍵KSを受け取り、これらの値と、鍵導出関数KDF及び公開ソルトsとを用いて、次式により、セッション鍵生成パラメータK'1、K'2、K'3及びK'4を求める（ｓ１７）。
K'1←KDF(s,KA)
K'2←KDF(s,KB)
K'3←KDF(s,KT)
K'4←KDF(s,KS)
【００５８】
＜第一セッション鍵生成部１９＞
第一セッション鍵生成部１９は、疑似ランダム関数G（公開パラメータ）をサーバ３０から受け取る。第一セッション鍵生成部１９は、第一パラメータ生成部１８からセッション鍵生成パラメータK'1、K'2、K'3及びK'4を受け取り、疑似ランダム関数Gにより、セッション識別子ST=(UA,UB,SPKA,SPKB,CTA,ekT,CTB,CTT)と、セッション鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて、次式により、セッション鍵SKを生成する（ｓ１８）。
【数１３】
0005945525.tif 000014
第一鍵交換装置１０は、セッション鍵SKの生成に係るセッションを終了し、全てのセッション情報を削除する。
【００５９】
［第二鍵交換装置２０の処理の流れ（図４及び５参照）］
＜第二秘密鍵選択部２２＞
第二秘密鍵選択部２２は、暗号文生成の乱数空間RSEからランダムに第二暗号文生成アドホック秘密鍵rBを選択し（rB∈RRSE）、暗号文生成の乱数空間RSEからランダムに第二鍵生成アドホック秘密鍵rTBを選択する（ｓ２１、rTB∈RRSE）。第二秘密鍵選択部２２は、第二暗号文生成アドホック秘密鍵rBと第二鍵生成アドホック秘密鍵rTBとを、第二記憶部２１に秘密に記憶する。
【００６０】
＜第二暗号化部２３＞
第二暗号化部２３は、第一長期公開鍵SPKAに含まれる第一IND-CCA公開鍵ekAを第一鍵交換装置１０またはサーバ３０から受け取る。第二暗号化部２３は、第一IND-CCA公開鍵ekAを用いて、IND-CCA secure KEMにより、第二記憶部２１から取り出した第二暗号文生成アドホック秘密鍵rBを暗号化し、第二IND-CCA暗号文CTBと第二IND-CCA鍵KBとの組を生成する（ｓ２２、(CTB,KB)←EnCapek_A(rB)）。第二暗号化部は、第二IND-CCA鍵KBを第二記憶部２１に秘密に記憶する。
【００６１】
＜第三暗号化部２４＞
第三暗号化部２４は、第二鍵生成アドホック秘密鍵rTBを第二記憶部２１から取り出し、IND-CPA secure PKIC-KEMの暗号文生成アルゴリズムwEnCapCにより、取り出した第二鍵生成アドホック秘密鍵rTBを暗号化し、IND-CPA暗号文CTTを生成する（ｓ２３、CTT←wEnCapC(rTB)）。
【００６２】
第二鍵交換装置２０は、図示しない受信部を介して、(UA,UB,CTA,ekT)を第一鍵交換装置１０から受信する。
さらに、第二鍵交換装置２０は、図示しない送信部を介して、(UA,UB,CTB,CTT)を第一鍵交換装置１０に送信する。
【００６３】
＜第四復号部２５＞
第四復号部２５は、第二記憶部２１から第二IND-CCA秘密鍵dkBを取り出し、これを用いて、IND-CCA secure KEMにより、受信した(UA,UB,CTA,ekT)に含まれる第一IND-CCA暗号文CTAを復号し、第一IND-CCA鍵KAを求める（ｓ２４、KA←DeCapdk_B(CTA)）。
【００６４】
＜第四暗号化部２６＞
第四暗号化部２６は、第二鍵生成アドホック秘密鍵rTBを第二記憶部２１から取り出す。第四暗号化部２６は、IND-CPA secure PKIC-KEMのKEM鍵生成アルゴリズムwEnCapKにより、受信した(UA,UB,CTA,ekT)に含まれるIND-CPA公開鍵ekTを用いて、第三暗号化部２４で生成したIND-CPA暗号文CTT及び取り出した第二鍵生成アドホック秘密鍵rTBを暗号化し、IND-CPA鍵KTを生成する（ｓ２５、KT←wEnCapKek_T(CTT;rTB)）。
【００６５】
＜第五暗号化部２７＞
第五暗号化部２７は、サーバ３０または第一鍵交換装置１０から長期公開鍵SPKAに含まれる第一IND-CPA公開鍵ekSAを受け取る。第五暗号化部２７は、第二記憶部２１から第二長期秘密鍵SSKBに含まれる第二暗号文生成秘密鍵rSBを取り出し、IND-CPA secure PKIC-KEMのKEM鍵生成アルゴリズムwEnCapKにより、受け取った第一IND-CPA公開鍵ekSAを用いて、第二長期公開鍵SPKBに含まれる第二IND-CPA暗号文CTSB及び取り出した第二暗号文生成秘密鍵rSBを暗号化し、IND-CPA鍵KSを生成する（ｓ２６、KS←wEnCapKek_SA(CTSB,rSB)）。
【００６６】
＜第二パラメータ生成部２８＞
第二パラメータ生成部２８は、サーバ３０から鍵導出関数KDF及び公開ソルトs（公開パラメータ）を受け取る。第二パラメータ生成部２８は、第二暗号化部２３、第四復号部２５、第四暗号化部２６及び第五暗号化部２７からそれぞれ第二IND-CCA鍵KB、第一IND-CCA鍵KA、IND-CPA鍵KT及びIND-CPA鍵KSを受け取り、これらの値と、鍵導出関数KDF及び公開ソルトsとを用いて、次式により、セッション鍵生成パラメータK'1、K'2、K'3及びK'4を求める（ｓ２７）。
K'1←KDF(s,KA)
K'2←KDF(s,KB)
K'3←KDF(s,KT)
K'4←KDF(s,KS)
【００６７】
＜第二セッション鍵生成部２９＞
第二セッション鍵生成部２９は、疑似ランダム関数G（公開パラメータ）をサーバ３０から受け取る。第二セッション鍵生成部２９は、第二パラメータ生成部２８からセッション鍵生成パラメータK'1、K'2、K'3及びK'4を受け取り、疑似ランダム関数Gにより、セッション識別子ST=(UA,UB,SPKA,SPKB,CTA,ekT,CTB,CTT)と、セッション鍵生成パラメータK'1、K'2、K'3及びK'4とを用いて、次式により、セッション鍵SKを生成する（ｓ２８）。
【数１４】
0005945525.tif 000015
第二鍵交換装置２０は、セッション鍵SKの生成に係るセッションを終了し、全てのセッション情報を削除する。
【００６８】
＜効果＞
このような構成により、FSXY方式のように
【数１５】
0005945525.tif 000016
を計算しなくても、安全性が証明できる。そのため、耐タンパモジュール内でオンライン計算を行うこと無く安全な方式を実現することができる。また、なお、IND-CPA secure KEM(wKeyGen,wEnCap,wDeCap)をIND-CPA secure PKIC-KEM(wKeyGen,wEnCapC,wEnCapK,wDeCap)に置き換えることにより、FSXY方式では、ユーザUBは、ユーザUAから(UA,UB,CTA,ekT)を受信するまでセッション鍵SK生成のための処理（(UA,UB,CTB,CTT)を生成する処理）を開始することができないが、本実施形態では、ユーザUAの操作する第一鍵交換装置１０から(UA,UB,CTA,ekT)を受信する前に、第二鍵交換装置２０は(UA,UB,CTB,CTT)を生成することができる。よって、本実施形態の方式は、遅延に強い。
【００６９】
＜変形例＞
なお、本実施形態では、鍵カプセル化メカニズムとして、IND-CCA secure KEMを用いているが、必ずしも、選択暗号文攻撃に対して識別不可能でなく、また、公開鍵独立暗号文生成可能鍵カプセル化メカニズムとしてIND-CPA secure PKIC-KEMを用いているが、必ずしも、選択平文攻撃に対して識別不可能でなくとも、耐タンパモジュール内でオンライン計算を行うこと無く安全な方式を実現することができる。ただし、IND-CCA secure KEMとIND-CPA secure PKIC-KEMとを用いることで、数学的にも安全となる。
【００７０】
鍵導出関数KDFに代えて、強ランダム抽出器Ext及びシードsを公開パラメータとしてもよい。強ランダム抽出器Extは、ランダムに選んだシードs∈SSを用い、次のように表される。Ext:SS×KS→FS。ただし、SSをシード空間、KSをKEM鍵の空間とする。
【００７１】
本実施形態では、第一長期秘密鍵SSKA等及び第二長期秘密鍵SSKB等をそれぞれ第一記憶部１１及び第二記憶部２１に秘密に記憶しているが、必ずしも第一鍵交換装置１０及び第二鍵交換装置２０の内部に記憶する必要はなく、それぞれ第一鍵交換装置１０及び第二鍵交換装置２０以外の鍵交換装置に対して秘密にされていればよい。例えば、安全な通信回線を使ってサーバ３０に送信し、サーバ３０内部で記憶し、必要に応じて、安全な通信回線を使って取り出せばよい。
【００７２】
第一鍵交換装置１０の機能と第二鍵交換装置２０の機能とを一つの鍵交換装置上で実装し、その鍵交換装置を第一鍵交換装置１０として機能させてもよいし、第二鍵交換装置２０として機能させてもよい。その場合、第一記憶部１１と第二記憶部２１、第一秘密鍵選択部１２と第二秘密鍵選択部２２、第一暗号化部１３と第二暗号化部２３、第一パラメータ生成部１８と第二パラメータ生成部２８、第一セッション鍵生成部１９と第二セッション鍵生成部２９等は、同様の機能を有するため、入力及び出力を変えるだけでよく、共用することができる。
【００７３】
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００７４】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００７５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【００７７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７８】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005945525.tif 000019
【図２】
0005945525.tif 000020
【図３】
0005945525.tif 000021
【図４】
0005945525.tif 000022
【図５】
0005945525.tif 000023