(57)【要約】【課題】１つの鍵生成装置の情報が分かっても端末になりすませないようにする。【解決手段】本発明のＩＤベース認証鍵交換システムは、２つ以上の鍵生成装置と端末Ａと端末Ｂを有する。鍵生成装置は、マスタ鍵生成部と秘密鍵生成部を備える。端末Ａは、鍵生成部Ａと鍵交換部Ａを備える。鍵生成部Ａは、０以上ｑ未満の整数である秘密鍵ｘＡを生成し、秘密鍵Ｓ１，Ａを計算し、０以上ｑ未満の整数である秘密鍵ｘＡ’を生成し、公開鍵Ｘ２，ＡをＸ２，Ａ＝ｇ２＾ｘＡ’のように計算し、公開鍵Ｘ２，Ａを公開する。鍵交換部Ａは、σ１，Ａ，σ２，Ａ，σ３，Ａの計算を含む所定の計算で、端末Ｂとの共有鍵Ｋを求める。端末Ｂは、鍵生成部Ｂと鍵交換部Ｂを備え、σ１，Ｂ，σ２，Ｂ，σ３，Ｂの計算を含む所定の計算で、端末Ｂとの共有鍵Ｋを求める。【選択図】図１
2018116231.tif 000002
【特許請求の範囲】
【請求項１】
２つ以上の鍵生成装置と端末Ａと端末Ｂを有するＩＤベース認証鍵交換システムであって、
κはセキュリティパラメータ、Ｇ１，Ｇ２，ＧＴは位数がκビット長の素数ｑの巡回群、ｇ１は群Ｇ１の生成元、ｇ２は群Ｇ２の生成元、ｇＴは群ＧＴの生成元、ｅはＧ１×Ｇ２→ＧＴのペアリングを示す記号、ｇ１，ｇ２，ｇＴはｇＴ＝ｅ（ｇ１，ｇ２）を満足し、ｉは１または２、Ｈｉは任意長の０と１で表現されたビット列を群Ｇｉの元に写像するハッシュ関数、Ｍは２以上のあらかじめ定めた整数、Ｎは１以上のあらかじめ定めた整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、端末Ａは識別子としてＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）を有し、端末Ｂは識別子としてＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）を有し、鍵生成装置ＫＡ，ｍはＩＤＡ，ｍに対応付けられた前記２つ以上の鍵生成装置の中の１つ、鍵生成装置ＫＢ，ｎはＩＤＢ，ｎに対応付けられた前記２つ以上の鍵生成装置の中の１つ、鍵生成装置ＫＡ，１，…，ＫＡ，Ｍの中には互いに異なる鍵生成装置が含まれており、＾はべき乗を示す記号、Ｘ２，Ａは前記端末Ａの公開鍵、Ｘ２，Ｂは前記端末Ｂの公開鍵、Ｈ１（ＩＤＡ，ｍ）とＨ１（ＩＤＢ，ｎ）は公開された情報とし、
前記２つ以上の鍵生成装置のそれぞれは、
１からＭまでのすべてのｍについて、鍵生成装置ＫＡ，ｍに該当するときは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＡ，ｍを生成し、マスタ公開鍵Ｚ２，Ａ，ｍをＺ２，Ａ，ｍ＝ｇ２＾ｚＡ，ｍのように計算し、マスタ公開鍵Ｚ２，Ａ，ｍを公開し、１からＮまでのすべてのｎについて、鍵生成装置ＫＢ，ｎに該当するときは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＢ，ｎを生成し、マスタ公開鍵Ｚ２，Ｂ，ｎをＺ２，Ｂ，ｎ＝ｇ２＾ｚＢ，ｎのように計算し、マスタ公開鍵Ｚ２，Ｂ，ｎを公開するマスタ鍵生成部と、
１からＭまでのすべてのｍについて、鍵生成装置ＫＡ，ｍに該当するときは、秘密鍵Ｓ１，Ａ，ｍをＳ１，Ａ，ｍ＝Ｈ１（ＩＤＡ，ｍ）＾ｚＡ，ｍのように計算し、端末Ａに送信し、１からＮまでのすべてのｎについて、鍵生成装置ＫＢ，ｎに該当するときは、秘密鍵Ｓ１，Ｂ，ｎをＳ１，Ｂ，ｎ＝Ｈ１（ＩＤＢ，ｎ）＾ｚＢ，ｎのように計算し、端末Ｂに送信する秘密鍵生成部と、
を備え、
前記端末Ａは、
０以上ｑ未満の整数である秘密鍵ｘＡを生成し、秘密鍵Ｓ１，Ａを
【数１９】
2018116231.tif 000021
のように計算し、秘密鍵ｘＡと秘密鍵Ｓ１，Ａを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＡ’を計算し、公開鍵Ｘ２，ＡをＸ２，Ａ＝ｇ２＾ｘＡ’のように計算し、公開鍵Ｘ２，Ａを公開する鍵生成部Ａと、
【数２０】
2018116231.tif 000022
および公開鍵Ｘ２，Ｂと秘密鍵ｘＡ’とから計算されるσ３，Ａの計算を含む所定の計算で、端末Ｂとの共有鍵Ｋを求める鍵交換部Ａ
を備え、
前記端末Ｂは、
０以上ｑ未満の整数である秘密鍵ｘＢを生成し、秘密鍵Ｓ１，Ｂを
【数２１】
2018116231.tif 000023
のように計算し、秘密鍵ｘＢと秘密鍵Ｓ１，Ｂを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＢ’を計算し、公開鍵Ｘ２，ＢをＸ２，Ｂ＝ｇ２＾ｘＢ’のように計算し、公開鍵Ｘ２，Ｂを公開する鍵生成部Ｂと、
【数２２】
2018116231.tif 000024
および公開鍵Ｘ２，Ａと秘密鍵ｘＢ’とから計算されるσ３，Ｂの計算を含む所定の計算で、端末Ａとの共有鍵Ｋを求める鍵交換部Ｂ
を備え、
前記σ３，Ａと前記σ３，Ｂは、
【数２３】
2018116231.tif 000025
または、
【数２４】
2018116231.tif 000026
のように計算される
ＩＤベース認証鍵交換システム。
【請求項２】
１つ以上の鍵生成装置を用いて他の端末との共有鍵を求める端末であって、
κはセキュリティパラメータ、Ｇ１，Ｇ２，ＧＴは位数がκビット長の素数ｑの巡回群、ｇ１は群Ｇ１の生成元、ｇ２は群Ｇ２の生成元、ｇＴは群ＧＴの生成元、ｅはＧ１×Ｇ２→ＧＴのペアリングを示す記号、ｇ１，ｇ２，ｇＴはｇＴ＝ｅ（ｇ１，ｇ２）を満足し、ｉは１または２、Ｈｉは任意長の０と１で表現されたビット列を群Ｇｉの元に写像するハッシュ関数、Ｍは２以上のあらかじめ定めた整数、Ｎは１以上のあらかじめ定めた整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、当該端末は識別子としてＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）を有し、前記他の端末は識別子としてＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）を有し、鍵生成装置ＫＡ，ｍはＩＤＡ，ｍに対応付けられた前記２つ以上の鍵生成装置の中の１つ、鍵生成装置ＫＡ，１，…，ＫＡ，Ｍの中には互いに異なる鍵生成装置が含まれており、＾はべき乗を示す記号、Ｘ２，Ａは当該端末の公開鍵、Ｘ２，Ｂは前記他の端末の公開鍵、Ｈ１（ＩＤＡ，ｍ）とＨ１（ＩＤＢ，ｎ）は公開された情報とし、
鍵生成装置ＫＡ，ｍは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＡ，ｍを生成し、マスタ公開鍵Ｚ２，Ａ，ｍをＺ２，Ａ，ｍ＝ｇ２＾ｚＡ，ｍのように計算し、マスタ公開鍵Ｚ２，Ａ，ｍを公開し、秘密鍵Ｓ１，Ａ，ｍをＳ１，Ａ，ｍ＝Ｈ１（ＩＤＡ，ｍ）＾ｚＡ，ｍのように計算し、端末Ａに送信するとし、
当該端末は、
０以上ｑ未満の整数である秘密鍵ｘＡを生成し、秘密鍵Ｓ１，Ａを
【数２５】
2018116231.tif 000027
のように計算し、秘密鍵ｘＡと秘密鍵Ｓ１，Ａを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＡ’を計算し、公開鍵Ｘ２，ＡをＸ２，Ａ＝ｇ２＾ｘＡ’のように計算し、公開鍵Ｘ２，Ａを公開する鍵生成部と、
【数２６】
2018116231.tif 000028
および
【数２７】
2018116231.tif 000029
のあらかじめ定められた一方を含む所定の計算で、前記他の端末との共有鍵Ｋを求める鍵交換部
を備えた端末。
【請求項３】
請求項２記載の端末であって、
Ｈｑは任意長の０と１で表現されたビット列を０以上ｑ未満の整数に写像するハッシュ関数、｜を０と１で表現されたビット列をつなげることを示す記号とし、
前記鍵生成部は、ｘＡ’＝Ｈｑ（ｘＡ｜Ｓ１，Ａ）のように計算することで前記秘密鍵ｘＡ’を計算する
ことを特徴とする端末。
【請求項４】
請求項２または３記載の端末であって、
Ｈは任意長の０と１で表現されたビット列をκビット長の０と１で表現されたビット列に写像するハッシュ関数、｜を０と１で表現されたビット列をつなげることを示す記号とし、
前記鍵交換部は、Ｋ＝Ｈ（σ１，Ａ｜σ２，Ａ｜σ３，Ａ）のように前記共有鍵Ｋを計算する
ことを特徴とする端末。
【請求項５】
請求項２または３記載の端末であって、
Ｈは任意長の０と１で表現されたビット列をκビット長の０と１で表現されたビット列に写像するハッシュ関数とし、
前記鍵交換部の前記のあらかじめ定められた一方を含む所定の計算は、
【数２８】
2018116231.tif 000030
を含む所定の計算であって、
前記鍵交換部は、σＡ＝σ１，Ａσ２，Ａσ３，Ａを計算し、Ｋ＝Ｈ（σＡ）のように前記共有鍵Ｋを計算する
ことを特徴とする端末。
【請求項６】
２つ以上の鍵生成装置と端末Ａと端末Ｂを有するＩＤベース認証鍵交換システムで実行するＩＤベース認証鍵交換方法であって、
κはセキュリティパラメータ、Ｇ１，Ｇ２，ＧＴは位数がκビット長の素数ｑの巡回群、ｇ１は群Ｇ１の生成元、ｇ２は群Ｇ２の生成元、ｇＴは群ＧＴの生成元、ｅはＧ１×Ｇ２→ＧＴのペアリングを示す記号、ｇ１，ｇ２，ｇＴはｇＴ＝ｅ（ｇ１，ｇ２）を満足し、ｉは１または２、Ｈｉは任意長の０と１で表現されたビット列を群Ｇｉの元に写像するハッシュ関数、Ｍは２以上のあらかじめ定めた整数、Ｎは１以上のあらかじめ定めた整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、端末Ａは識別子としてＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）を有し、端末Ｂは識別子としてＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）を有し、鍵生成装置ＫＡ，ｍはＩＤＡ，ｍに対応付けられた前記２つ以上の鍵生成装置の中の１つ、鍵生成装置ＫＢ，ｎはＩＤＢ，ｎに対応付けられた前記２つ以上の鍵生成装置の中の１つ、鍵生成装置ＫＡ，１，…，ＫＡ，Ｍの中には互いに異なる鍵生成装置が含まれており、＾はべき乗を示す記号、Ｘ２，Ａは前記端末Ａの公開鍵、Ｘ２，Ｂは前記端末Ｂの公開鍵、Ｈ１（ＩＤＡ，ｍ）とＨ１（ＩＤＢ，ｎ）は公開された情報とし、
前記２つ以上の鍵生成装置のそれぞれは、
１からＭまでのすべてのｍについて、鍵生成装置ＫＡ，ｍに該当するときは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＡ，ｍを生成し、マスタ公開鍵Ｚ２，Ａ，ｍをＺ２，Ａ，ｍ＝ｇ２＾ｚＡ，ｍのように計算し、マスタ公開鍵Ｚ２，Ａ，ｍを公開し、１からＮまでのすべてのｎについて、鍵生成装置ＫＢ，ｎに該当するときは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＢ，ｎを生成し、マスタ公開鍵Ｚ２，Ｂ，ｎをＺ２，Ｂ，ｎ＝ｇ２＾ｚＢ，ｎのように計算し、マスタ公開鍵Ｚ２，Ｂ，ｎを公開するマスタ鍵生成ステップと、
１からＭまでのすべてのｍについて、鍵生成装置ＫＡ，ｍに該当するときは、秘密鍵Ｓ１，Ａ，ｍをＳ１，Ａ，ｍ＝Ｈ１（ＩＤＡ，ｍ）＾ｚＡ，ｍのように計算し、端末Ａに送信し、１からＮまでのすべてのｎについて、鍵生成装置ＫＢ，ｎに該当するときは、秘密鍵Ｓ１，Ｂ，ｎをＳ１，Ｂ，ｎ＝Ｈ１（ＩＤＢ，ｎ）＾ｚＢ，ｎのように計算し、端末Ｂに送信する秘密鍵生成ステップと、
を実行し、
前記端末Ａは、
０以上ｑ未満の整数である秘密鍵ｘＡを生成し、秘密鍵Ｓ１，Ａを
【数２９】
2018116231.tif 000031
のように計算し、秘密鍵ｘＡと秘密鍵Ｓ１，Ａを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＡ’を計算し、公開鍵Ｘ２，ＡをＸ２，Ａ＝ｇ２＾ｘＡ’のように計算し、公開鍵Ｘ２，Ａを公開する鍵生成Ａステップと、
【数３０】
2018116231.tif 000032
および公開鍵Ｘ２，Ｂと秘密鍵ｘＡ’とから計算されるσ３，Ａの計算を含む所定の計算で、端末Ｂとの共有鍵Ｋを求める鍵交換Ａステップ
を実行し、
前記端末Ｂは、
０以上ｑ未満の整数である秘密鍵ｘＢを生成し、秘密鍵Ｓ１，Ｂを
【数３１】
2018116231.tif 000033
のように計算し、秘密鍵ｘＢと秘密鍵Ｓ１，Ｂを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＢ’を計算し、公開鍵Ｘ２，ＢをＸ２，Ｂ＝ｇ２＾ｘＢ’のように計算し、公開鍵Ｘ２，Ｂを公開する鍵生成Ｂステップと、
【数３２】
2018116231.tif 000034
および公開鍵Ｘ２，Ａと秘密鍵ｘＢ’とから計算されるσ３，Ｂの計算を含む所定の計算で、端末Ａとの共有鍵Ｋを求める鍵交換Ｂステップ
を実行し、
前記σ３，Ａと前記σ３，Ｂは、
【数３３】
2018116231.tif 000035
または、
【数３４】
2018116231.tif 000036
のように計算される
ＩＤベース認証鍵交換方法。
【請求項７】
請求項２から５のいずれかの端末としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、安全に共有鍵を交換するためのＩＤベース認証鍵交換システム、端末、ＩＤベース認証鍵交換方法、プログラムに関する。
【背景技術】
【０００２】
多くの暗号通信では、正しい相手かどうかを認証して鍵交換を行い、その後に共有したセッション鍵を用いた共通鍵暗号方式で暗号・復号の機能を利用している。その認証と鍵交換を同時に行う認証鍵交換と呼ばれる技術があり、認証された鍵が交換できる。認証鍵交換では短期鍵と長期鍵の二種類を用い、それぞれに対して秘密鍵と公開鍵が存在する。認証鍵交換の方式として、非特許文献１のＣＣＳ、非特許文献２，３のＦＳＵや非特許文献４の認証鍵交換方式が提案されている。ＦＳＵは認証鍵交換の方式であり、秘密鍵の漏洩に対して最も強い安全性のｅＣＫモデル安全性を満足することが証明されている暗号方式である。具体的にｅＣＫモデル安全性とは、認証鍵交換のための秘密鍵には短期秘密鍵と長期秘密鍵の２種類があり、発信者と受信者の秘密鍵のどの非自明な秘密鍵の組み合わせの漏洩（例えば、発信者の短期秘密鍵と受信者の短期秘密鍵の漏洩）に対しても、交換されるセッションの漏洩が無いことである。非特許文献４の認証及び鍵交換方式は発信者及び受信者の長期秘密鍵を生成する鍵生成装置が異なる場合のｅＣＫモデル安全性を満足する方式である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Chen, L., Cheng, Z., Smart, N.P.“Identity-based key agreement protocols from pairings”, Int. J. Inf. Security 6(4), 213―241 (2007).
【非特許文献２】A. Fujioka, F. Hoshino, T. Kobayashi, et. al.“id-eCK Secure ID-Based Authenticated Key Exchange on Symmetric and Asymmetric Pairing”, IEICE Transactions 96-A(6): 1139―1155 (2013).
【非特許文献３】B. Ustaoglu“Integrating identity-based and certicate-based authenticated key exchange protocols”, Int J Inf Secur 10(4): 201―212 (2011).
【非特許文献４】A. Fujioka,“One-Round Exposure-Resilient Identity-Based Authenticated Key Agreement with Multiple Private Key Generator”, Mycrypto 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来のＴＬＳ（Transport Layer Security）などの証明書ベースの認証鍵交換の場合は、クライアントの端末同士は、別々の認証局から発行された証明書をもとに認証鍵を交換できた。しかしながら、ＩＤベース認証鍵交換方式のＦＳＵは、同一の鍵生成装置（ＫＧＣ：Key Generate Center）が発行した秘密鍵を持つ端末同士でなければ通信できないという課題がある。非特許文献４の技術はこの課題を解決しているが、秘密鍵を生成した鍵生成装置自身が端末になりすますことができた。また、鍵生成装置からマスタ秘密鍵が漏洩した場合にはマスタ秘密鍵の情報を保有する装置であれば、端末になりすますことができた。
【０００５】
本発明は、少なくとも一方の端末については、１つの鍵生成装置の情報が分かっても端末になりすませないようにすることを目的とする。
【課題を解決するための手段】
【０００６】
本発明のＩＤベース認証鍵交換システムは、２つ以上の鍵生成装置と端末Ａと端末Ｂを有する。κはセキュリティパラメータ、Ｇ１，Ｇ２，ＧＴは位数がκビット長の素数ｑの巡回群、ｇ１は群Ｇ１の生成元、ｇ２は群Ｇ２の生成元、ｇＴは群ＧＴの生成元、ｅはＧ１×Ｇ２→ＧＴのペアリングを示す記号、ｇ１，ｇ２，ｇＴはｇＴ＝ｅ（ｇ１，ｇ２）を満足し、ｉは１または２、Ｈｉは任意長の０と１で表現されたビット列を群Ｇｉの元に写像するハッシュ関数、Ｍは２以上のあらかじめ定めた整数、Ｎは１以上のあらかじめ定めた整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、端末Ａは識別子としてＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）を有し、端末Ｂは識別子としてＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）を有し、鍵生成装置ＫＡ，ｍはＩＤＡ，ｍに対応付けられた前記２つ以上の鍵生成装置の中の１つ、鍵生成装置ＫＢ，ｎはＩＤＢ，ｎに対応付けられた前記２つ以上の鍵生成装置の中の１つ、鍵生成装置ＫＡ，１，…，ＫＡ，Ｍの中には互いに異なる鍵生成装置が含まれており、＾はべき乗を示す記号、Ｘ２，Ａは前記端末Ａの公開鍵、Ｘ２，Ｂは前記端末Ｂの公開鍵、Ｈ１（ＩＤＡ，ｍ）とＨ１（ＩＤＢ，ｎ）は公開された情報とする。
【０００７】
鍵生成装置は、マスタ鍵生成部と秘密鍵生成部を備える。マスタ鍵生成部は、鍵生成装置ＫＡ，ｍに該当するときは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＡ，ｍを生成し、マスタ公開鍵Ｚ２，Ａ，ｍをＺ２，Ａ，ｍ＝ｇ２＾ｚＡ，ｍのように計算し、マスタ公開鍵Ｚ２，Ａ，ｍを公開する。マスタ鍵生成部は、鍵生成装置ＫＢ，ｎに該当するときは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＢ，ｎを生成し、マスタ公開鍵Ｚ２，Ｂ，ｎをＺ２，Ｂ，ｎ＝ｇ２＾ｚＢ，ｎのように計算し、マスタ公開鍵Ｚ２，Ｂ，ｎを公開する。秘密鍵生成部は、鍵生成装置ＫＡ，ｍに該当するときは、秘密鍵Ｓ１，Ａ，ｍをＳ１，Ａ，ｍ＝Ｈ１（ＩＤＡ，ｍ）＾ｚＡ，ｍのように計算し、端末Ａに送信する。秘密鍵生成部は、鍵生成装置ＫＢ，ｎに該当するときは、秘密鍵Ｓ１，Ｂ，ｎをＳ１，Ｂ，ｎ＝Ｈ１（ＩＤＢ，ｎ）＾ｚＢ，ｎのように計算し、端末Ｂに送信する。
【０００８】
端末Ａは、鍵生成部Ａと鍵交換部Ａを備える。鍵生成部Ａは、０以上ｑ未満の整数である秘密鍵ｘＡを生成し、秘密鍵Ｓ１，Ａを
【０００９】
【数１】
2018116231.tif 000003
【００１０】
のように計算し、秘密鍵ｘＡと秘密鍵Ｓ１，Ａを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＡ’を計算し、公開鍵Ｘ２，ＡをＸ２，Ａ＝ｇ２＾ｘＡ’のように計算し、公開鍵Ｘ２，Ａを公開する。鍵交換部Ａは、
【００１１】
【数２】
2018116231.tif 000004
【００１２】
および公開鍵Ｘ２，Ｂと秘密鍵ｘＡ’とから計算されるσ３，Ａの計算を含む所定の計算で、端末Ｂとの共有鍵Ｋを求める。
【００１３】
端末Ｂは、鍵生成部Ｂと鍵交換部Ｂを備える。鍵生成部Ｂは、０以上ｑ未満の整数である秘密鍵ｘＢを生成し、秘密鍵Ｓ１，Ｂを
【００１４】
【数３】
2018116231.tif 000005
【００１５】
のように計算し、秘密鍵ｘＢと秘密鍵Ｓ１，Ｂを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＢ’を生成し、公開鍵Ｘ２，ＢをＸ２，Ｂ＝ｇ２＾ｘＢ’のように計算し、公開鍵Ｘ２，Ｂを公開する。鍵交換部Ｂは、
【００１６】
【数４】
2018116231.tif 000006
【００１７】
および公開鍵Ｘ２，Ａと秘密鍵ｘＢ’とから計算されるσ３，Ｂの計算を含む所定の計算で、端末Ａとの共有鍵Ｋを求める。
【００１８】
σ３，Ａとσ３，Ｂは、
【００１９】
【数５】
2018116231.tif 000007
または、
【００２０】
【数６】
2018116231.tif 000008
【００２１】
のように計算される。
【発明の効果】
【００２２】
本発明のＩＤベース認証鍵交換システムによれば、少なくとも一方の端末については、２つ以上の鍵生成装置から秘密鍵を受信して処理を行うので、１つの鍵生成装置の情報が分かってもその端末にはなりすませない。
【図面の簡単な説明】
【００２３】
【図１】ＩＤベース認証鍵交換システムの構成例を示す図。
【図２】本発明のＩＤベース認証鍵交換システムの処理フローの中の主に鍵生成装置の処理フローを示す図。
【図３】本発明の端末の処理フローを示す図。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２５】
図１にＩＤベース認証鍵交換システムの構成例を示す。この説明では、端末２００Ａは複数の識別子を有し、端末２００Ｂは１つだけの識別子を有することも、複数の識別子を有することもあることを前提に説明する。実際には、複数の識別子を有する端末を端末２００Ａと考えればよい。図２に本発明のＩＤベース認証鍵交換システムの処理フローの中の主に鍵生成装置の処理フローを示す。図３に本発明の端末の処理フローを示す。本発明のＩＤベース認証鍵交換システムは、ネットワーク９００を介して接続されている２つ以上の鍵生成装置１００１，…，１００Ｋ（Ｋは２以上の整数）と２つ以上の端末を有する。
【００２６】
κはセキュリティパラメータ、Ｇ１，Ｇ２，ＧＴは位数がκビット長の素数ｑの巡回群、ｇ１は群Ｇ１の生成元、ｇ２は群Ｇ２の生成元、ｇＴは群ＧＴの生成元、ｅはＧ１×Ｇ２→ＧＴのペアリングを示す記号、ｇ１，ｇ２，ｇＴはｇＴ＝ｅ（ｇ１，ｇ２）を満足し、ｉは１または２、Ｈｉは任意長の０と１で表現されたビット列を群Ｇｉの元に写像するハッシュ関数、Ｈｑは任意長の０と１で表現されたビット列を０以上ｑ未満の整数に写像するハッシュ関数、Ｈは任意長の０と１で表現されたビット列をκビット長の０と１で表現されたビット列に写像するハッシュ関数、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数、Ｍは２以上のあらかじめ定めた整数、Ｎは１以上のあらかじめ定めた整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、端末２００Ａは識別子としてＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）を有し、端末２００Ｂは識別子としてＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）を有し、鍵生成装置１００Ａ，ｍはＩＤＡ，ｍに対応付けられた２つ以上の鍵生成装置の中の１つ、鍵生成装置１００Ｂ，ｎはＩＤＢ，ｎに対応付けられた２つ以上の鍵生成装置の中の１つ、鍵生成装置ＫＡ，１，…，ＫＡ，Ｍの中には互いに異なる鍵生成装置が含まれており、＾はべき乗を示す記号、｜を０と１で表現されたビット列をつなげることを示す記号、Ｘ２，Ａは前記端末Ａの公開鍵、Ｘ２，Ｂは前記端末Ｂの公開鍵とする。「鍵生成装置１００Ａ，ｍはＩＤＡ，ｍに対応付けられた２つ以上の鍵生成装置の中の１つ」とは、「鍵生成装置１００Ａ，ｍ」は鍵生成装置１００１，…，１００Ｋの中のいずれか１つが、ＩＤＡ，ｍに対応つけられていることを意味している。「対応つける」方法としては、あらかじめ定める方法でもいいし、端末２００Ａがランダムに選ぶ方法でもよい。また、サービスごとにＩＤＡ，ｍに対応付ける鍵生成装置を変えてもよい。「鍵生成装置１００Ｂ」も同様である。鍵生成装置ＫＡ，１，…，ＫＡ，Ｍのすべてが同一の鍵生成装置であることは除くが、鍵生成装置１００Ａ，１，…，１００Ａ，Ｍと鍵生成装置１００Ｂ，１，…，１００Ｂ，Ｎの中に同一の鍵生成装置となる場合があってもよい。つまり、添え字の「Ａ，ｍ」と「Ｂ，ｎ」は１〜Ｋのいずれかの整数である。なお、鍵生成装置１００Ａ，１，…，１００Ａ，Ｍと鍵生成装置１００Ｂ，１，…，１００Ｂ，Ｎとをできるだけ異なる装置にすれば、鍵生成装置のマスタ秘密鍵の漏えいが生じた場合のセキュリティ上のリスクを低減できる。
【００２７】
端末２００ＡはＩＤＡ，１，…，ＩＤＡ，Ｍのハッシュ情報Ｈ１（ＩＤＡ，１），…，Ｈ１（ＩＤＡ，Ｍ）を公開する（Ｓ２１０Ａ）。端末２００ＢはＩＤＢ，１，…，ＩＤＢ，Ｎのハッシュ情報Ｈ１（ＩＤＢ，１），…，Ｈ１（ＩＤＢ，Ｎ）を公開する（Ｓ２１０Ｂ）。「公開する」とは、何らかの方法でだれでも入手できる状態にすることを意味し、例えば、特定のサーバなどにアクセスすることでだれでもダウンロードできる状態にする方法などがある。なお、「ハッシュ情報Ｈ１（ＩＤＡ，ｍ）」は、識別子ＩＤＡ，ｍのハッシュ値であるＨ１（ＩＤＡ，ｍ）自体でもよいし、ハッシュ関数Ｈ１が既に公開されている場合は、識別子ＩＤＡ，ｍ自体を公開してもよい。
【００２８】
鍵生成装置１００ｋは、マスタ鍵生成部１１０ｋと秘密鍵生成部１２０ｋを備える。鍵生成装置１００Ａ，ｍに該当するときは、マスタ鍵生成部１１０Ａ，ｍは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＡを生成し、マスタ公開鍵Ｚ２，Ａ，ｍをＺ２，Ａ，ｍ＝ｇ２＾ｚＡ，ｍのように計算し（Ｓ１１１Ａ，ｍ）、マスタ公開鍵Ｚ２，Ａ，ｍを公開する（Ｓ１１２Ａ，ｍ）。この処理をｍ＝１，…，Ｍに対して行う。鍵生成装置１００Ｂ，ｎに該当するときは、マスタ鍵生成部１１０Ｂ，ｎは、０以上ｑ未満の整数であるマスタ秘密鍵ｚＢ，ｎを生成し、マスタ公開鍵Ｚ２，Ｂ，ｎをＺ２，Ｂ，ｎ＝ｇ２＾ｚＢ，ｎのように計算し（Ｓ１１１Ｂ，ｎ）、マスタ公開鍵Ｚ２，Ｂ，ｎを公開する（Ｓ１１２Ｂ，ｎ）。この処理をｎ＝１，…，Ｎに対して行う。
【００２９】
鍵生成装置１００Ａ，ｍに該当するときは、秘密鍵生成部１２０Ａ，ｍは、秘密鍵Ｓ１，Ａ，ｍをＳ１，Ａ，ｍ＝Ｈ１（ＩＤＡ，ｍ）＾ｚＡ，ｍのように計算し（Ｓ１２１Ａ，ｍ）、端末２００Ａに送信する（Ｓ１２２Ａ，ｍ）。この処理をｍ＝１，…，Ｍに対して行う。鍵生成装置１００Ｂ，ｎに該当するときは、秘密鍵生成部１２０Ｂ，ｎは、秘密鍵Ｓ１，Ｂ，ｎをＳ１，Ｂ，ｎ＝Ｈ１（ＩＤＢ，ｎ）＾ｚＢ，ｎのように計算し（Ｓ１２１Ｂ，ｎ）、端末Ｂに送信する（Ｓ１２２Ｂ，ｎ）。この処理をｎ＝１，…，Ｎに対して行う。
【００３０】
端末２００Ａは、鍵生成部２１０Ａと鍵交換部２２０Ａを備える。鍵生成部２１０Ａは、０以上ｑ未満の整数である秘密鍵ｘＡを生成し、秘密鍵Ｓ１，Ａを
【００３１】
【数７】
2018116231.tif 000009
【００３２】
のように計算し、秘密鍵ｘＡと秘密鍵Ｓ１，Ａを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＡ’を計算し、公開鍵Ｘ２，ＡをＸ２，Ａ＝ｇ２＾ｘＡ’のように計算し（Ｓ２１３Ａ）、公開鍵Ｘ２，Ａを公開する（Ｓ２１２Ａ）。「あらかじめ定めた方法」としては、例えば、ｘＡ’＝Ｈｑ（ｘＡ｜Ｓ１，Ａ）のように計算することで秘密鍵ｘＡ’を計算すればよい。
【００３３】
鍵交換部２２０Ａは、
【００３４】
【数８】
2018116231.tif 000010
【００３５】
および公開鍵Ｘ２，Ｂと秘密鍵ｘＡ’とから計算されるσ３，Ａの計算を含む所定の計算で、端末２００Ｂとの共有鍵Ｋを求める（Ｓ２２１Ａ）。「所定の計算」については後述する。
【００３６】
端末２００Ｂも、鍵生成部２１０Ｂと鍵交換部２２０Ｂを備える。鍵生成部２１０Ｂは、０以上ｑ未満の整数である秘密鍵ｘＢを生成し、秘密鍵Ｓ１，Ｂを
【００３７】
【数９】
2018116231.tif 000011
【００３８】
のように計算し、秘密鍵ｘＢと秘密鍵Ｓ１，Ｂを用いてあらかじめ定めた方法で０以上ｑ未満の整数である秘密鍵ｘＢ’を生成し、公開鍵Ｘ２，ＢをＸ２，Ｂ＝ｇ２＾ｘＢ’のように計算し（Ｓ２１３Ｂ）、公開鍵Ｘ２，Ｂを公開する（Ｓ２１２Ｂ）。「あらかじめえ定めた方法」としては、例えば、ｘＢ’＝Ｈｑ（ｘＢ｜Ｓ１，Ｂ）のように計算することで秘密鍵ｘＢ’を計算すればよい。
【００３９】
鍵交換部２２０Ｂは、
【００４０】
【数１０】
2018116231.tif 000012
【００４１】
および公開鍵Ｘ２，Ａと秘密鍵ｘＢ’とから計算されるσ３，Ｂの計算を含む所定の計算で、端末Ａとの共有鍵Ｋを求める（Ｓ２２１Ｂ）。なお、正しい処理が行われていれば、
【００４２】
【数１１】
2018116231.tif 000013
【００４３】
【数１２】
2018116231.tif 000014
【００４４】
となるので、σ１，Ａ＝σ１，Ｂ、σ２，Ａ＝σ２，Ｂである。
【００４５】
「所定の計算」として、以下に３つの例を説明するが、σ３，Ａ＝σ３，Ｂとなり、同一の共有鍵Ｋを求められる範囲であれば、これらに限定する必要はない。第１の例では、鍵交換部２２０Ａはσ３，Ａを、
【００４６】
【数１３】
2018116231.tif 000015
【００４７】
のように計算し、共有鍵ＫをＫ＝Ｈ（σ１，Ａ｜σ２，Ａ｜σ３，Ａ）のように共有鍵Ｋを計算する。その際、Ｈに対する入力として、その他の変数を加えてもよい。そして、鍵交換部２２０Ｂはσ３，Ｂを、
【００４８】
【数１４】
2018116231.tif 000016
【００４９】
のように計算し、共有鍵ＫをＫ＝Ｈ（σ１，Ｂ｜σ２，Ｂ｜σ３，Ｂ）のように共有鍵Ｋを計算する。なお、正しい処理が行われていれば、
【００５０】
【数１５】
2018116231.tif 000017
【００５１】
となるので、σ３，Ａ＝σ３，Ｂである。したがって、端末２００Ａと端末２００Ｂは共有鍵Ｋを共有できる。
【００５２】
「所定の計算」の第２の例では、鍵交換部２２０Ａはσ３，Ａを、
【００５３】
【数１６】
2018116231.tif 000018
【００５４】
のように計算し、共有鍵ＫをＫ＝Ｈ（σ１，Ａ｜σ２，Ａ｜σ３，Ａ）のように共有鍵Ｋを計算する。その際、Ｈに対する入力として、その他の変数を加えてもよい。そして、鍵交換部２２０Ｂはσ３，Ｂを、
【００５５】
【数１７】
2018116231.tif 000019
【００５６】
のように計算し、共有鍵ＫをＫ＝Ｈ（σ１，Ｂ｜σ２，Ｂ｜σ３，Ｂ）のように共有鍵Ｋを計算する。なお、正しい処理が行われていれば、
【００５７】
【数１８】
2018116231.tif 000020
【００５８】
となるので、σ３，Ａ＝σ３，Ｂである。したがって、端末２００Ａと端末２００Ｂは共有鍵Ｋを共有できる。
【００５９】
「所定の計算」の第３の例では、鍵交換部２２０Ａはσ３，Ａを第２の例と同じように計算し、共有鍵ＫをＫ＝Ｈ（σ１，Ａσ２，Ａσ３，Ａ）のように共有鍵Ｋを計算する。その際、Ｈに対する入力として、その他の変数を加えてもよい。鍵交換部２２０Ｂはσ３，Ｂを第２の例と同じように計算し、共有鍵ＫをＫ＝Ｈ（σ１，Ｂσ２，Ｂσ３，Ｂ）のように共有鍵Ｋを計算する。正しい処理が行われていれば、端末２００Ａと端末２００Ｂは共有鍵Ｋを共有できる。
【００６０】
上述の処理では、Ｎも２以上であればＡとＢを入れ替えても同じ処理となる。したがって、識別子を２つ以上持つ１つの端末の視点で見たときには、常にその端末自体を端末２００Ａとし、鍵交換をする他の端末を端末２００Ｂと扱えばよい。つまり、本発明のすべての端末は、端末２００Ａとして機能すればよい。
【００６１】
本発明のＩＤベース認証鍵交換システムによれば、端末２００Ａは２つ以上の鍵生成装置から秘密鍵を受信して処理を行うので、１つの鍵生成装置の情報が分かっても端末２００Ａにはなりすませない。つまり、１つの鍵生成装置だけでは端末２００Ａになりすますことはできない。また、１つの鍵生成装置からマスタ秘密鍵が漏洩した場合でも、その情報だけでは、端末２００Ａになりすますことはできない。また、２つの端末２００Ａと２００Bに対して２つの非自明な情報の組（秘密鍵Ｓ１，Ａと秘密鍵ｘＡ）と（秘密鍵Ｓ１，Bと秘密鍵ｘB）がある。そのうち(Ｓ１，ＡとＳ１，B）及び(Ｓ１，ＡとｘB）及び(ｘＡとＳ１，B）及び(ｘＡとｘB)のどの秘密鍵の組み合わせの漏洩が起きても、攻撃者はσ１，Ａ（又はσ１，Ｂ），σ２，Ａ（又はσ２，Ｂ），σ３，Ａ（又はσ３，Ｂ）のすべては計算できない。よって、従来のＦＳＵと同様にｅＣＫモデル安全性が確保できている。
【００６２】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００６８】
１００  鍵生成装置
１１０  マスタ鍵生成部
１２０  秘密鍵生成部
２００  端末
２１０  鍵生成部
２２０  鍵交換部
９００  ネットワーク
【図１】
2018116231.tif 000037
【図２】
2018116231.tif 000038
【図３】
2018116231.tif 000039