(57)【要約】【課題】遅延による影響を小さくし、強フォワード安全性を満たす。【解決手段】要求装置１０は、短期公開鍵ekAと短期秘密鍵dkAを求め、第１鍵KAと第１暗号文CTAを生成し、第１暗号文CTAと短期公開鍵ekAを応答装置２０へ送信する。応答装置２０は、第３暗号文CTB,2を生成し、第２暗号文CTB,1と第２鍵KB,1を生成し、第２暗号文CTB,1と第３暗号文CTB,2を要求装置１０へ送信する。要求装置１０は、第２鍵KB,1を生成し、第３鍵KB,2を生成し、第１鍵KAと第２鍵KB,1と第３鍵KB,2を用いてセッション鍵SKを生成する。応答装置２０は、第１鍵KAを生成し、第３鍵KB,2を生成し、第１鍵KAと第２鍵KB,1と第３鍵KB,2を用いてセッション鍵SKを生成する。【選択図】図１
2014050084.tif 000002
【特許請求の範囲】
【請求項１】
要求装置と応答装置との間でセッション鍵SKを共有する鍵交換システムであって、
前記要求装置は、
任意のサインクリプションの送信者鍵生成アルゴリズムSKeyGenにより生成された要求側送信者秘密鍵skASと、前記サインクリプションの受信者鍵生成アルゴリズムRKeyGenにより生成された要求側受信者秘密鍵skARとが記憶された要求側記憶部と、
鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの鍵生成アルゴリズムwKeyGenを用いて、短期公開鍵ekAと短期秘密鍵dkAを求める短期鍵対生成部と、
前記要求側送信者秘密鍵skASと、前記受信者鍵生成アルゴリズムRKeyGenにより生成された応答側受信者公開鍵pkBRと、前記短期公開鍵ekAとを入力として、前記サインクリプションのサインクリプションアルゴリズムSCを用いて、第１暗号文CTAと第１鍵KAを生成する第１暗号化部と、
前記第１暗号文CTAと前記短期公開鍵ekAを前記応答装置へ送信する要求側出力部と、
前記要求側受信者秘密鍵skARと、前記送信者鍵生成アルゴリズムSKeyGenにより生成された応答側送信者公開鍵pkBSと、前記応答装置から受信した第２暗号文CTB,1および第３暗号文CTB,2とを入力として、前記サインクリプションの復号アルゴリズムUSCを用いて、第２鍵KB,1を生成する第２鍵復号部と、
前記短期秘密鍵dkAと前記第３暗号文CTB,2とを入力として、前記鍵カプセル化メカニズムの復号アルゴリズムwDeCapを用いて、第３鍵KB,2を生成する第３鍵復号部と、
前記第１鍵KAと前記第２鍵KB,1と前記第３鍵KB,2を含むセッション識別子STを用いて、前記セッション鍵SKを生成する要求側セッション鍵生成部と、
を備え、
前記応答装置は、
前記送信者鍵生成アルゴリズムSKeyGenにより生成された応答側送信者秘密鍵skBSと、前記受信者鍵生成アルゴリズムRKeyGenにより生成された応答側受信者秘密鍵skBRとが記憶された応答側記憶部と、
前記鍵カプセル化メカニズムの暗号文生成アルゴリズムwEnCapCを用いて、前記第３暗号文CTB,2を生成する第３暗号化部と、
前記応答側送信者秘密鍵skBSと、前記受信者鍵生成アルゴリズムRKeyGenにより生成された要求側受信者公開鍵pkARと、前記第３暗号文CTB,2とを入力として、前記サインクリプションアルゴリズムSCを用いて、前記第２暗号文CTB,1と前記第２鍵KB,1を生成する第２暗号化部と、
前記第２暗号文CTB,1と前記第３暗号文CTB,2を前記要求装置へ送信する応答側出力部と、
前記応答側受信者秘密鍵skBRと、前記送信者鍵生成アルゴリズムSKeyGenにより生成された要求側送信者公開鍵pkASと、前記要求装置から受信した前記第１暗号文CTAおよび前記短期公開鍵ekAとを入力として、前記復号アルゴリズムUSCを用いて、前記第１鍵KAを生成する第１鍵復号部と、
前記短期公開鍵ekAと前記第３暗号文CTB,2とを入力として、前記鍵カプセル化メカニズムのカプセル化鍵生成アルゴリズムwEnCapKを用いて、前記第３鍵KB,2を生成する第３鍵生成部と、
前記第１鍵KAと前記第２鍵KB,1と前記第３鍵KB,2を含む前記セッション識別子STを用いて、前記セッション鍵SKを生成する応答側セッション鍵生成部と、
を備えることを特徴とする鍵交換システム。
【請求項２】
応答装置とセッション鍵SKを共有する要求装置であって、
任意のサインクリプションの送信者鍵生成アルゴリズムSKeyGenにより生成された要求側送信者秘密鍵skASと、前記サインクリプションの受信者鍵生成アルゴリズムRKeyGenにより生成された要求側受信者秘密鍵skARとが記憶された記憶部と、
鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの鍵生成アルゴリズムwKeyGenを用いて、短期公開鍵ekAと短期秘密鍵dkAを求める短期鍵対生成部と、
前記要求側送信者秘密鍵skASと、前記受信者鍵生成アルゴリズムRKeyGenにより生成された応答側受信者公開鍵pkBRと、前記短期公開鍵ekAとを入力として、前記サインクリプションのサインクリプションアルゴリズムSCを用いて、第１暗号文CTAと第１鍵KAを生成する第１暗号化部と、
前記第１暗号文CTAと前記短期公開鍵ekAを前記応答装置へ送信する出力部と、
前記要求側受信者秘密鍵skARと、前記送信者鍵生成アルゴリズムSKeyGenにより生成された応答側送信者公開鍵pkBSと、前記応答装置から受信した第２暗号文CTB,1および第３暗号文CTB,2とを入力として、前記サインクリプションの復号アルゴリズムUSCを用いて、第２鍵KB,1を生成する第２鍵復号部と、
前記短期秘密鍵dkAと、前記第３暗号文CTB,2とを入力として、前記鍵カプセル化メカニズムの復号アルゴリズムwDeCapを用いて、第３鍵KB,2を生成する第３鍵復号部と、
前記第１鍵KAと前記第２鍵KB,1と前記第３鍵KB,2を含むセッション識別子STを用いて、前記セッション鍵SKを生成するセッション鍵生成部と、
を備えることを特徴とする要求装置。
【請求項３】
要求装置とセッション鍵SKを共有する応答装置であって、
任意のサインクリプションの送信者鍵生成アルゴリズムSKeyGenにより生成された応答側送信者秘密鍵skBSと、前記サインクリプションの受信者鍵生成アルゴリズムRKeyGenにより生成された応答側受信者秘密鍵skBRとが記憶された記憶部と、
鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの暗号文生成アルゴリズムwEnCapCを用いて、第３暗号文CTB,2を生成する第３暗号化部と、
前記応答側送信者秘密鍵skBSと、前記受信者鍵生成アルゴリズムRKeyGenにより生成された要求側受信者公開鍵pkARと、前記第３暗号文CTB,2とを入力として、前記サインクリプションのサインクリプションアルゴリズムSCを用いて、第２暗号文CTB,1と第２鍵KB,1を生成する第２暗号化部と、
前記第２暗号文CTB,1と前記第３暗号文CTB,2を前記要求装置へ送信する出力部と、
前記応答側受信者秘密鍵skBRと、前記送信者鍵生成アルゴリズムSKeyGenにより生成された要求側送信者公開鍵pkASと、前記要求装置から受信した第１暗号文CTAおよび短期公開鍵ekAとを入力として、前記サインクリプションの復号アルゴリズムUSCを用いて、第１鍵KAを生成する第１鍵復号部と、
前記短期公開鍵ekAと前記第３暗号文CTB,2とを入力として、前記鍵カプセル化メカニズムのカプセル化鍵生成アルゴリズムwEnCapKを用いて、第３鍵KB,2を生成する第３鍵生成部と、
前記第１鍵KAと前記第２鍵KB,1と前記第３鍵KB,2を含むセッション識別子STを用いて、前記セッション鍵SKを生成するセッション鍵生成部と、
を備えることを特徴とする応答装置。
【請求項４】
要求装置と応答装置との間でセッション鍵SKを共有する鍵交換方法であって、
前記要求装置が、鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの鍵生成アルゴリズムwKeyGenを用いて、短期公開鍵ekAと短期秘密鍵dkAを求める短期鍵対生成ステップと、
前記要求装置が、任意のサインクリプションの送信者鍵生成アルゴリズムSKeyGenにより生成された要求側送信者秘密鍵skASと、前記サインクリプションの受信者鍵生成アルゴリズムRKeyGenにより生成された応答側受信者公開鍵pkBRと、前記短期公開鍵ekAとを入力として、前記サインクリプションのサインクリプションアルゴリズムSCを用いて、第１暗号文CTAと第１鍵KAを生成する第１暗号化ステップと、
前記要求装置が、前記第１暗号文CTAと前記短期公開鍵ekAを前記応答装置へ送信する要求側出力ステップと、
前記応答装置が、前記鍵カプセル化メカニズムの暗号文生成アルゴリズムwEnCapCを用いて、第３暗号文CTB,2を生成する第３暗号化ステップと、
前記応答装置が、前記送信者鍵生成アルゴリズムSKeyGenにより生成された応答側送信者秘密鍵skBSと、前記受信者鍵生成アルゴリズムRKeyGenにより生成された要求側受信者公開鍵pkARと、前記第３暗号文CTB,2とを入力として、前記サインクリプションアルゴリズムSCを用いて、第２暗号文CTB,1と第２鍵KB,1を生成する第２暗号化ステップと、
前記応答装置が、前記第２暗号文CTB,1と前記第３暗号文CTB,2を前記要求装置へ送信する応答側出力ステップと、
前記要求装置が、前記要求側受信者秘密鍵skARと、前記送信者鍵生成アルゴリズムSKeyGenにより生成された応答側送信者公開鍵pkBSと、前記応答装置から受信した前記第２暗号文CTB,1および前記第３暗号文CTB,2とを入力として、前記サインクリプションの復号アルゴリズムUSCを用いて、第２鍵KB,1を生成する第２鍵復号ステップと、
前記要求装置が、前記短期秘密鍵dkAと前記第３暗号文CTB,2とを入力として、前記鍵カプセル化メカニズムの復号アルゴリズムwDeCapを用いて、第３鍵KB,2を生成する第３鍵復号ステップと、
前記要求装置が、前記第１鍵KAと前記第２鍵KB,1と前記第３鍵KB,2を含むセッション識別子STを用いて、前記セッション鍵SKを生成する要求側セッション鍵生成ステップと、
前記応答装置が、前記応答側受信者秘密鍵skBRと、前記送信者鍵生成アルゴリズムSKeyGenにより生成された要求側送信者公開鍵pkASと、前記要求装置から受信した前記第１暗号文CTAおよび前記短期公開鍵ekAとを入力として、前記復号アルゴリズムUSCを用いて、前記第１鍵KAを生成する第１鍵復号ステップと、
前記応答装置が、前記短期公開鍵ekAと前記第３暗号文CTB,2とを入力として、前記鍵カプセル化メカニズムのカプセル化鍵生成アルゴリズムwEnCapKを用いて、前記第３鍵KB,2を生成する第３鍵生成ステップと、
前記応答装置が、前記第１鍵KAと前記第２鍵KB,1と前記第３鍵KB,2を含む前記セッション識別子STを用いて、前記セッション鍵SKを生成する応答側セッション鍵生成ステップと、
を含むことを特徴とする鍵交換方法。
【請求項５】
請求項２に記載の要求装置もしくは請求項３に記載の応答装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術の応用技術に関し、特に、装置間で共通のセッション鍵を共有する鍵交換技術に関する。
【背景技術】
【０００２】
従来の鍵交換技術に、鍵カプセル化メカニズムに基づく鍵交換方式がある。鍵カプセル化メカニズムに基づく鍵交換方式には、例えば、FSXY方式がある（非特許文献１参照）。以下に、非特許文献１に記載されているFSXY方式について詳細に説明する。
【０００３】
［FSXY方式の説明］
以下の説明では、要求装置と応答装置の間で共通のセッション鍵SKを共有するものとする。要求装置は識別子UAで特定され、応答装置は識別子UBで特定される。
＜準備＞
кをセキュリティパラメータとする。
【０００４】
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を強ランダム抽出器と呼ぶ。ただし、Δは統計距離、US,UX,UYはそれぞれS,X,Y上の一様分布、|X|=n≧k、|Y|=k、|S|=dとする。
【０００６】
(KeyGen,EnCap,DeCap)と(wKeyGen,wEnCap,wDeCap)をそれぞれ鍵カプセル化メカニズム(KEM、Key Encapsulation Mechanism)とする。鍵生成アルゴリズムKeyGen,wKeyGenはセキュリティパラメータкと乱数rg∈RSGを入力とし、公開鍵ekと秘密鍵dkを出力する。ただし、RSGは鍵生成の乱数空間である。鍵カプセル化アルゴリズムEnCap,wEnCapは公開鍵ekと乱数re∈RSEを入力とし、KEM鍵K∈KSと暗号文CT∈CSを出力する。ただし、RSEは鍵カプセル化の乱数空間、KSはKEM鍵空間、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鍵空間とする。
＜長期公開鍵と長期秘密鍵＞
要求装置はランダムにσA∈FSとrA∈RSGを選択し、鍵生成アルゴリズムKeyGenにより(ekA,1,dkA,1)←KeyGen(1к,rA)を得る。応答装置はランダムにσB∈FS、rB∈RSGを選択し、鍵生成アルゴリズムKeyGenにより(ekB,1,dkB,1)←KeyGen(1к,rB)を得る。要求装置の長期秘密鍵を(dkA,1,σA)、長期公開鍵を(ekA,1)、応答装置の長期秘密鍵を(dkB,1,σB)、長期公開鍵を(ekB,1)とする。
＜鍵交換＞
要求装置はランダムに短期秘密鍵rA,1∈FS、r’A,1∈FS、rA,2∈RSGを選び、式(1)(2)を計算する。
【０００７】
【数１】
2014050084.tif 000003
【０００８】
要求装置は第１送信情報(UA,UB,CTA,1,ekA,2)を生成し、応答装置へ送信する。ただし、UAは要求装置を示す識別子、UBは応答装置を示す識別子である。
【０００９】
応答装置は、要求装置からの第１送信情報(UA,UB,CTA,1,ekA,2)を受信すると、ランダムに短期秘密鍵rB,1∈FS、r’B,1∈FS、rB,2∈RSEを選び、式(3)(4)を計算する。
【００１０】
【数２】
2014050084.tif 000004
【００１１】
そして、応答装置は第２送信情報(UA,UB,CTB,1,CTB,2)を生成し、要求装置へ送信する。
【００１２】
続いて、応答装置は下記の式(5)〜(8)を計算し、セッション識別子ST=(UA,UB,ekA,1,ekB,1,CTA,1,ekA,2,CTB,1,CTB,2)を生成する。
【００１３】
【数３】
2014050084.tif 000005
【００１４】
そして、応答装置はセッション識別子ST=(UA,UB,ekA,1,ekB,1,CTA,1,ekA,2,CTB,1,CTB,2)を用いて下記の式(9)を計算し、セッション鍵SKを生成する。
【００１５】
【数４】
2014050084.tif 000006
【００１６】
最後に、応答装置はセッションを終了し、全てのセッション情報を削除する。
【００１７】
一方、要求装置は、応答装置からの第２送信情報(UA,UB,CTB,1,CTB,2)を受信すると、下記の式(10)〜(14)を計算し、セッション識別子ST=(UA,UB,ekA,1,ekB,1,CTA,1,ekA,2,CTB,1,CTB,2)を生成する。
【００１８】
【数５】
2014050084.tif 000007
【００１９】
そして、要求装置はセッション識別子ST=(UA,UB,ekA,1,ekB,1,CTA,1,ekA,2,CTB,1,CTB,2)を用いて下記の式(15)を計算し、セッション鍵SKを生成する。
【００２０】
【数６】
2014050084.tif 000008
【００２１】
最後に、要求装置はセッションを終了し、全てのセッション情報を削除する。
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】Fujioka, A., Suzuki, K., Xagawa, K., Yoneyama, K., “Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices.”, Public Key Cryptography 2012, pp.467-484.
【発明の概要】
【発明が解決しようとする課題】
【００２３】
上述のFSXY方式では、応答装置は、要求装置から短期公開鍵ekA,2を受信しないと鍵カプセル化アルゴリズムwEnCapを実行することができないため、二者間で処理の順番が厳密に守られなければいけない。そのため、送信装置から要求装置への情報送信に遅延が発生すると鍵交換の手順全体の所要時間が長くなるという問題がある。
【００２４】
また、上述のFSXY方式は強フォワード安全性を満たしていない。強フォワード安全性とは、ある攻撃者があるセッションに対して通信路上に介在しメッセージの改変などを行った上で、セッション鍵生成後に要求装置および応答装置の長期秘密鍵を得たとしても、セッション鍵の情報を得られないとする安全性である。FSXY方式では、例えば、攻撃者が要求装置の短期公開鍵ekA,2を用いて第２暗号文CTB,1と第３暗号文CTB,2を生成し、応答装置になりすまして要求装置に送信することができる。このとき攻撃者は自ら鍵カプセル化メカニズムwEnCapを実行したため第２鍵KB,1と第３鍵KB,2を知っている。セッション終了後に応答装置の長期秘密鍵dkB,1を得ることができれば第１暗号文CTA,1を復号して第１鍵KA,1を入手することができる。このように攻撃者はセッション鍵SKを入手することができるため、FSXY方式は強フォワード安全性を満たしていない。
【００２５】
この発明はこのような点に鑑みてなされたものであり、鍵交換手順の順番を入れ替えることが可能で遅延による影響を小さくすることができ、強フォワード安全性を満たす鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【００２６】
上記の課題を解決するために、この発明の鍵交換システムは、要求装置と応答装置との間でセッション鍵SKを共有する。要求装置は、要求側記憶部と短期鍵対生成部と第１暗号化部と要求側出力部と第２鍵復号部と第３鍵復号部と要求側セッション鍵生成部とを備える。応答装置は、応答側記憶部と第３暗号化部と第２暗号化部と応答側出力部と第１鍵復号部と第３鍵生成部と応答側セッション鍵生成部とを備える。要求側記憶部には、任意のサインクリプションの送信者鍵生成アルゴリズムSKeyGenにより生成された要求側送信者秘密鍵skASと、サインクリプションの受信者鍵生成アルゴリズムRKeyGenにより生成された要求側受信者秘密鍵skARとが記憶されている。応答側記憶部には、送信者鍵生成アルゴリズムSKeyGenにより生成された応答側送信者秘密鍵skBSと、受信者鍵生成アルゴリズムRKeyGenにより生成された応答側受信者秘密鍵skBRとが記憶されている。
【００２７】
要求装置の備える短期鍵対生成部は、鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの鍵生成アルゴリズムwKeyGenを用いて、短期公開鍵ekAと短期秘密鍵dkAを求める。要求装置の備える第１暗号化部は、要求側送信者秘密鍵skASと、受信者鍵生成アルゴリズムRKeyGenにより生成された応答側受信者公開鍵pkBRと、短期公開鍵ekAとを入力として、サインクリプションのサインクリプションアルゴリズムSCを用いて、第１暗号文CTAと第１鍵KAを生成する。要求装置の備える要求側出力部は、第１暗号文CTAと短期公開鍵ekAを応答装置へ送信する。
【００２８】
応答装置の備える第３暗号化部は、鍵カプセル化メカニズムの暗号文生成アルゴリズムwEnCapCを用いて、第３暗号文CTB,2を生成する。応答装置の備える第２暗号化部は、応答側送信者秘密鍵skBSと、受信者鍵生成アルゴリズムRKeyGenにより生成された要求側受信者公開鍵pkARと、第３暗号文CTB,2とを入力として、サインクリプションアルゴリズムSCを用いて、第２暗号文CTB,1と第２鍵KB,1を生成する。応答装置の備える応答側出力部は、第２暗号文CTB,1と第３暗号文CTB,2を要求装置へ送信する。
【００２９】
要求装置の備える第２鍵復号部は、要求側受信者秘密鍵skARと、送信者鍵生成アルゴリズムSKeyGenにより生成された応答側送信者公開鍵pkBSと、応答装置から受信した第２暗号文CTB,1および第３暗号文CTB,2とを入力として、サインクリプションの復号アルゴリズムUSCを用いて、第２鍵KB,1を生成する。要求装置の備える第３鍵復号部は、短期秘密鍵dkAと第３暗号文CTB,2とを入力として、鍵カプセル化メカニズムの復号アルゴリズムwDeCapを用いて、第３鍵KB,2を生成する。要求装置の備える要求側セッション鍵生成部は、第１鍵KAと第２鍵KB,1と第３鍵KB,2を含むセッション識別子STを用いて、セッション鍵SKを生成する。
【００３０】
応答装置の備える第１鍵復号部は、応答側受信者秘密鍵skBRと、送信者鍵生成アルゴリズムSKeyGenにより生成された要求側送信者公開鍵pkASと、要求装置から受信した第１暗号文CTAおよび短期公開鍵ekAとを入力として、復号アルゴリズムUSCを用いて、第１鍵KAを生成する。応答装置の備える第３鍵生成部は、短期公開鍵ekAと第３暗号文CTB,2とを入力として、鍵カプセル化メカニズムのカプセル化鍵生成アルゴリズムwEnCapKを用いて、第３鍵KB,2を生成する。応答装置の備える応答側セッション鍵生成部は、第１鍵KAと第２鍵KB,1と第３鍵KB,2を含むセッション識別子STを用いて、セッション鍵SKを生成する。
【発明の効果】
【００３１】
この発明の鍵交換技術によれば、要求装置からの情報を受信しなくとも応答装置の手順を並行して実行することができるため、遅延による影響を小さくすることができる。また、攻撃者は、応答装置の秘密鍵を知らなければ要求装置へ送信する情報を生成することができないため、強フォワード安全性を満たすことができる。
【図面の簡単な説明】
【００３２】
【図１】鍵交換システムの機能構成を例示する図である。
【図２】要求装置の機能構成を例示する図である。
【図３】応答装置の機能構成を例示する図である。
【図４】鍵交換方法の処理フローを例示する図である。
【図５】鍵交換方法の処理フローを例示する図である。
【発明を実施するための形態】
【００３３】
実施形態の説明に先立ち、この発明の基本的な考え方について説明する。
【００３４】
［発明のポイント］
この発明では、鍵生成と暗号文生成が独立な鍵カプセル化メカニズムとサインクリプションを用いることで、鍵交換手順の順番を入れ替えることが可能で遅延による影響を小さくすることができ、強フォワード安全性を満たす鍵交換技術を実現した。
【００３５】
＜鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの説明＞
鍵生成と暗号文生成が独立な鍵カプセル化メカニズムは、暗号文を公開鍵の情報無しで生成することができる鍵カプセル化メカニズムである。鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの詳細な構成方法は、例えば、「Taher El Gamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.”, CRYPTO 1984, pp.10-18, 1984.(参考文献１)」に記載されている。参考文献１に記載の鍵カプセル化メカニズムは、鍵生成アルゴリズムwKeyGen、暗号文生成アルゴリズムwEnCapC、カプセル化鍵生成アルゴリズムwEnCapK、復号アルゴリズムwDeCapからなる。鍵生成アルゴリズムwKeyGenと復号アルゴリズムwDeCapは、通常の鍵カプセル化メカニズムと同様である。暗号文生成アルゴリズムwEnCapCはシステム公開パラメータと乱数re∈RSEを入力とし、暗号文CT∈CSを出力する。ただし、RSEは暗号文生成の乱数空間、CSは暗号文空間である。カプセル化鍵生成アルゴリズムwEnCapKは公開鍵ekと暗号文CTと乱数reを入力とし、KEM鍵K∈KSを出力する。ただし、KSはKEM鍵空間である。
【００３６】
参考文献１に記載の鍵カプセル化メカニズムでは、暗号文生成アルゴリズムwEnCapCを、短期公開鍵ekA,2を受信する前に実行することができるため、応答装置が要求装置からの情報を受信する前に、応答装置から要求装置へ情報を送信することも可能である。すなわち、各装置は相手から受信する情報とは独立して情報を生成し送信することができるため、鍵交換手順の順番を入れ替えることが可能となる。これにより、仮に要求装置から応答装置への通信路に遅延が発生したとしても、応答装置は要求装置からの情報の受信を待つ必要がなく、遅延による影響を小さくすることができる。
【００３７】
＜サインクリプションの説明＞
サインクリプションは、暗号化と署名を同時に行う暗号方式である。暗号文生成の際に受信者の公開鍵と送信者の秘密鍵を必要とし、送信者の公開鍵と受信者の秘密鍵を用いることによって暗号文の正当性検証を行うことができる。サインクリプションの詳細な構成方法は、例えば、「Daiki Chiba, Takahiro Matsuda, Jacob C. N. Schuldt, Kanta Matsuura, “Efficient Generic Constructions of Signcryption with Insider Security in the Multi-user Setting.”, ACNS 2011, pp.220-237.（参考文献２）」に記載されている。参考文献２に記載のサインクリプションは、送信者鍵生成アルゴリズムSKeyGen、受信者鍵生成アルゴリズムRKeyGen、サインクリプションアルゴリズムSC、復号アルゴリズムUSCからなる。送信者鍵生成アルゴリズムSKeyGenは、セキュリティパラメータкと乱数rS∈RSSGを入力とし、送信者公開鍵pkSと送信者秘密鍵skSを出力する。ただし、RSSGは送信者鍵生成の乱数空間である。受信者鍵生成アルゴリズムRKeyGenは、セキュリティパラメータкと乱数rR∈RSRGを入力とし、受信者公開鍵pkRと受信者秘密鍵skRを出力する。ただし、RSRGは受信者鍵生成の乱数空間である。サインクリプションアルゴリズムSCは、送信者秘密鍵skSと受信者公開鍵pkRとメッセージmを入力とし、KEM鍵K∈KSと暗号文CT∈CSを出力する。上述の通り、KSはKEM鍵空間、CSは暗号文空間である。復号アルゴリズムUSCは、受信者秘密鍵skRと送信者公開鍵pkSとメッセージmと暗号文CTを入力とし、暗号文CTが正しければKEM鍵Kを出力する。暗号文CTが正しくない場合はエラー⊥を返す。
【００３８】
従来の鍵カプセル化メカニズム(KeyGen,EnCap,DeCap)の代わりにサインクリプション(SKeyGen,RKeyGen,SC,USC)を用いることにより、上述の強フォワード安全性を満たすことができる。すなわち、攻撃者が通信路上でメッセージの改変を行おうとしても、送信者秘密鍵skSを知らなければ正しい暗号文CTを生成することができず、正規の応答装置に成りすますことが不可能となるためである。
【００３９】
［実施形態］
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
＜構成＞
図１を参照して、この発明に係る鍵交換システム１の構成例を説明する。鍵交換システム１は、要求装置１０と応答装置２０を含む。要求装置１０と応答装置２０はネットワーク９０に接続される。ネットワーク９０は、接続される各装置が相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）などで構成することができる。
【００４０】
図２を参照して、鍵交換システム１に含まれる要求装置１０の構成例を説明する。要求装置１０は、制御部１０１、記憶部１０２、乱数選択部１１０、長期鍵対生成部１１５、短期乱数選択部１２０、短期鍵対生成部１２５、第１暗号化部１３０、出力部１３５、入力部１４０、第２鍵復号部１４５、第３鍵復号部１５０、セッション鍵生成部１５５を備える。要求装置１０は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。要求装置１０は制御部１０１の制御のもとで各処理を実行する。記憶部１０２は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、リレーショナルデータベースやキーバリューストアなどのミドルウェア、などにより構成することができる。
【００４１】
図３を参照して、鍵交換システム１に含まれる応答装置２０の構成例を説明する。応答装置２０は、制御部２０１、記憶部２０２、乱数選択部２１０、長期鍵対生成部２１５、短期乱数選択部２２０、第３暗号化部２２５、第２暗号化部２３０、出力部２３５、入力部２４０、第１鍵復号部２４５、第３鍵生成部２５０、セッション鍵生成部２５５を備える。応答装置２０は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。応答装置２０は制御部２０１の制御のもとで各処理を実行する。記憶部２０２は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、リレーショナルデータベースやキーバリューストアなどのミドルウェア、などにより構成することができる。
＜パラメータ＞
кをセキュリティパラメータとする。
【００４２】
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鍵空間とする。
＜長期公開鍵と長期秘密鍵＞
図４を参照して、鍵交換システム１が長期公開鍵と長期秘密鍵を生成する動作例について手続きの順に従って説明する。
【００４３】
要求装置１０の備える乱数選択部１１０は、ランダムにσA∈FS、rAS∈RSG、rAR∈RSGを選択する（Ｓ１１０）。乱数rAS,rARは長期鍵対生成部１１５へ入力される。長期鍵対生成部１１５は、サインクリプションの送信者鍵生成アルゴリズムSKeyGenにより送信者鍵(pkAS,skAS)←SKeyGen(1к,rAS)を得る（Ｓ１１６）。続いて、長期鍵対生成部１１５は、サインクリプションの受信者鍵生成アルゴリズムRKeyGenにより受信者鍵(pkAR,skAR)←RKeyGen(1к,rAR)を得る（Ｓ１１７）。そして、長期鍵対生成部１１５は、要求装置１０の長期秘密鍵を(skAS,skAR,σA)、長期公開鍵を(pkAS,pkAR)とする（Ｓ１１８）。生成された長期秘密鍵(skAS,skAR,σA)は記憶部１０２に記憶される。生成された長期公開鍵(pkAS,pkAR)は公開される。公開の方法は長期公開鍵(pkAS,pkAR)が応答装置２０から参照可能であればどのような方式であってもよい。例えば、要求装置１０から応答装置２０へあらかじめ長期公開鍵(pkAS,pkAR)を送信しておいてもよいし、別途用意する公開鍵基盤（PKI、Public Key Infrastructure）を用いて長期公開鍵(pkAS,pkAR)を公開してもよい。
【００４４】
応答装置２０の備える乱数選択部２１０は、ランダムにσB∈FS、rBS∈RSG、rBR∈RSGを選択する（Ｓ２１０）。乱数rBS,rBRは長期鍵対生成部２１５へ入力される。長期鍵対生成部２１５は、サインクリプションの送信者鍵生成アルゴリズムSKeyGenにより送信者鍵(pkBS,skBS)←SKeyGen(1к,rBS)を得る（Ｓ２１６）。続いて、長期鍵対生成部２１５は、サインクリプションの受信者鍵生成アルゴリズムRKeyGenにより受信者鍵(pkBR,skBR)←RKeyGen(1к,rBR)を得る（Ｓ２１７）。そして、長期鍵対生成部２１５は、応答装置２０の長期秘密鍵を(skBS,skBR,σB)、長期公開鍵を(pkBS,pkBR)とする（Ｓ２１８）。生成された長期秘密鍵(skBS,skBR,σB)は記憶部２０２に記憶される。生成された長期公開鍵(pkBS,pkBR)は公開される。公開の方法は長期公開鍵(pkBS,pkBR)が要求装置１０から参照可能であればどのような方式であってもよい。例えば、応答装置２０から要求装置１０へあらかじめ長期公開鍵(pkBS,pkBR)を送信しておいてもよいし、別途用意する公開鍵基盤（PKI、Public Key Infrastructure）を用いて長期公開鍵(pkBS,pkBR)を公開してもよい。
＜鍵交換＞
図４、５を参照して、鍵交換システム１の要求装置１０と応答装置２０とがセッション鍵SKを共有する動作例について手続きの順に従って説明する。図４と図５は一連の手順を表しており、図４の「Ａ１」は図５の「Ａ１」に処理が継続し、図４の「Ａ２」は図５の「Ａ２」に処理が継続することを表している。
【００４５】
要求装置１０の備える短期乱数選択部１２０は、ランダムに乱数rA,1∈FS、r’A,1∈FS、rA,2∈RSGを選択する（Ｓ１２０）。乱数rA,2は短期鍵対生成部１２５へ入力される。短期鍵対生成部１２５は、鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの鍵生成アルゴリズムwKeyGenを下記の式(16)のように計算し、短期公開鍵ekAと短期秘密鍵dkAを生成する（Ｓ１２５）。
【００４６】
【数７】
2014050084.tif 000009
【００４７】
乱数rA,1,r’A,1と短期公開鍵ekAは第１暗号化部１３０へ入力される。第１暗号化部１３０は、要求側送信者秘密鍵skASと応答側受信者公開鍵pkBRを用いて、短期公開鍵eKAをメッセージとみなして、サインクリプションのサインクリプションアルゴリズムSCを下記の式(17)のように計算し、第１暗号文CTAと第１鍵KAを生成する（Ｓ１３０）。
【００４８】
【数８】
2014050084.tif 000010
【００４９】
第１暗号文CTAと短期公開鍵ekAは出力部１３５へ入力される。出力部１３５は、第１送信情報(UA,UB,CTA,ekA)を生成し、応答装置２０へ送信する（Ｓ１３５）。上述の通り、UAは要求装置１０を示す識別子、UBは応答装置２０を示す識別子である。
【００５０】
応答装置２０の備える短期乱数選択部２２０は、ランダムに乱数rB,1∈FS、r’B,1∈FS、rB,2∈RSEを選択する（Ｓ２２０）。乱数rB,2は第３暗号化部２２５へ入力される。第３暗号化部２２５は、鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの暗号文生成アルゴリズムwEnCapCを下記の式(18)のように計算し、第３暗号文CTB,2を生成する（Ｓ２２５）。
【００５１】
【数９】
2014050084.tif 000011
【００５２】
乱数rB,1,r’B,1と第３暗号文CTB,2は第２暗号化部２３０へ入力される。第２暗号化部２３０は、応答側送信者秘密鍵skBSと要求側受信者公開鍵pkARを用いて、第３暗号文CTB,2をメッセージとみなして、サインクリプションのサインクリプションアルゴリズムSCを下記の式(19)のように計算し、第２暗号文CTB,1と第２鍵KB,1を生成する（Ｓ２３０）。
【００５３】
【数１０】
2014050084.tif 000012
【００５４】
第２暗号文CTB,1と第３暗号文CTB,2は出力部２３５へ入力される。出力部２３５は、第２送信情報(UA,UB,CTB,1,CTB,2)を生成し、要求装置１０へ送信する（Ｓ２３５）。上述の通り、UAは要求装置１０を示す識別子、UBは応答装置２０を示す識別子である。
【００５５】
応答装置２０の備える出力部２３５が送信した第２送信情報(UA,UB,CTB,1,CTB,2)は、要求装置１０の備える入力部１４０を介して要求装置１０へ入力される。
【００５６】
第２暗号文CTB,1と第３暗号文CTB,2は第２鍵復号部１４５へ入力される。第２鍵復号部１４５は、要求側受信者秘密鍵skARと応答側送信者公開鍵pkBSを用いて、第３暗号文CTB,2をメッセージとみなして、サインクリプションの復号アルゴリズムUSCを下記の式(20)のように計算し、第２鍵KB,1を生成する（Ｓ１４５）。
【００５７】
【数１１】
2014050084.tif 000013
【００５８】
第３暗号文CTB,2は第３鍵復号部１５０へ入力される。第３鍵復号部１５０は、短期秘密鍵dkAを用いて、鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの復号アルゴリズムwDeCapを下記の式(21)のように計算し、第３鍵KB,2を生成する（Ｓ１５０）。
【００５９】
【数１２】
2014050084.tif 000014
【００６０】
第１鍵KAと第２鍵KB,1と第３鍵KB,2はセッション鍵生成部１５５へ入力される。セッション鍵生成部１５５は、強ランダム抽出器Extを用いて下記の式(22)〜(24)を計算し、値K’1,K’2,K’3を生成する（Ｓ１５１，Ｓ１５２，Ｓ１５３）。
【００６１】
【数１３】
2014050084.tif 000015
【００６２】
次に、セッション鍵生成部１５５は、セッション識別子ST=(UA,UB,pkAS,pkAR,pkBS,pkBR,ekA,CTA,CTB,1,CTB,2)を生成する（Ｓ１５４）。そして、セッション識別子STを用いて下記の式(25)を計算することで、セッション鍵SKを生成する（Ｓ１５５）。
【００６３】
【数１４】
2014050084.tif 000016
【００６４】
最後に、要求装置１０はセッションを終了し、全てのセッション情報を削除する。
【００６５】
一方、要求装置１０の備える出力部１３５が送信した第１送信情報(UA,UB,CTA,ekA)は、応答装置２０の備える入力部２４０を介して応答装置２０へ入力される。
【００６６】
第１暗号文CTAと短期公開鍵ekAは第１鍵復号部２４５へ入力される。第１鍵復号部２４５は、応答側受信者秘密鍵skBRと要求側送信者公開鍵pkASを用いて、短期公開鍵eKAをメッセージとみなして、サインクリプションの復号アルゴリズムUSCを下記の式(26)のように計算し、第１鍵KAを生成する（Ｓ２４５）。
【００６７】
【数１５】
2014050084.tif 000017
【００６８】
乱数rB,2と第３暗号文CTB,2は第３鍵生成部２５０へ入力される。第３鍵生成部２５０は、短期公開鍵ekAを用いて、第３暗号文CTB,2をメッセージとみなして、鍵生成と暗号文生成が独立な鍵カプセル化メカニズムのカプセル化鍵生成アルゴリズムwEnCapKを下記の式(27)のように計算し、第３鍵KB,2を生成する（Ｓ２５０）。
【００６９】
【数１６】
2014050084.tif 000018
【００７０】
第１鍵KAと第２鍵KB,1と第３鍵KB,2はセッション鍵生成部２５５へ入力される。セッション鍵生成部２５５は、要求装置１０の備えるセッション鍵生成部１５５と同様に、強ランダム抽出器Extを用いて上記の式(22)〜(24)を計算し、値K’1,K’2,K’3を生成する（Ｓ２５１，Ｓ２５２，Ｓ２５３）。
【００７１】
次に、セッション鍵生成部２５５は、要求装置１０の備えるセッション鍵生成部１５５と同様に、セッション識別子ST=(UA,UB,pkAS,pkAR,pkBS,pkBR,ekA,CTA,CTB,1,CTB,2)を生成する（Ｓ２５４）。そして、セッション鍵生成部２５５は、要求装置１０の備えるセッション鍵生成部１５５と同様に、セッション識別子STを用いて上記の式(25)を計算することで、セッション鍵SKを生成する（Ｓ２５５）。
【００７２】
最後に、応答装置２０はセッションを終了し、全てのセッション情報を削除する。
【００７３】
＜効果＞
上記の通り、この発明の鍵交換技術によれば、応答装置２０は鍵生成と暗号文生成が独立な鍵カプセル化メカニズムの暗号文生成アルゴリズムwEnCapCにより要求装置１０へ送信する第３暗号文CTB,2を生成するため、要求装置１０から短期公開鍵ekAを受信しなくとも第２送信情報(UA,UB,CTB,1,CTB,2)を生成することができる。これにより、要求装置１０から応答装置２０への通信路に遅延が生じたとしても、その影響を小さくすることができる。
【００７４】
また、応答装置２０はサインクリプションのサインクリプションアルゴリズムSCにより要求装置１０へ送信する第２暗号文CTB,1を生成するため、攻撃者は、応答装置２０の送信者秘密鍵skBSを知らなければ第２送信情報(UA,UB,CTB,1,CTB,2)を生成することができない。これにより、攻撃者が応答装置２０に成りすますことができず、強フォワード安全性を満たすことができる。
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００７５】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００７６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００８０】
１  鍵交換システム
１０  要求装置
２０  応答装置
９０  ネットワーク
１０１  制御部
１０２  記憶部
１１０  乱数選択部
１１５  長期鍵対生成部
１２０  短期乱数選択部
１２５  短期鍵対生成部
１３０  第１暗号化部
１３５  出力部
１４０  入力部
１４５  第２鍵復号部
１５０  第３鍵復号部
１５５  セッション鍵生成部
２０１  制御部
２０２  記憶部
２１０  乱数選択部
２１５  長期鍵対生成部
２２０  短期乱数選択部
２２５  第３暗号化部
２３０  第２暗号化部
２３５  出力部
２４０  入力部
２４５  第１鍵復号部
２５０  第３鍵生成部
２５５  セッション鍵生成部
【図１】
2014050084.tif 000019
【図２】
2014050084.tif 000020
【図３】
2014050084.tif 000021
【図４】
2014050084.tif 000022
【図５】
2014050084.tif 000023