(57)【特許請求の範囲】
【請求項１】
群Ｇ０と、前記群Ｇ０と対応付けられた群Ｇｔと、群Ｇ＾０と、前記群Ｇ＾０と対応付けられた群Ｇ＾ｔと、前記群Ｇ０及び前記群Ｇ＾０とペアリング演算ｅ０によって対応付けられるとともに、前記群Ｇｔ及び前記群Ｇ＾ｔとペアリング演算ｅｔによって対応付けられた群ＧＴとを用いた暗号システムにおける暗号化装置であり、
前記群ＧＴの要素Ｘと前記群Ｇ＾ｔの要素Ｙ＾とであって、少なくともいずれかが生成元が鍵生成乱数によって変換されて生成された要素Ｘと要素Ｙ＾を用いて暗号文ｃｔを生成する暗号文生成部
を備え、
前記暗号文生成部は、
前記要素Ｘに暗号化乱数ζが設定された変換情報ｚに対して、メッセージｍを設定して前記暗号文ｃｔの要素である暗号要素ｃＴを生成する第１暗号要素生成部と、
前記要素Ｙ＾に対して前記暗号化乱数ζを設定して前記暗号文ｃｔの要素である暗号要素ｃを生成する第２暗号要素生成部と
を備える暗号化装置。
【請求項２】
前記第１暗号要素生成部は、数１に示す暗号要素ｃＴを生成し、
前記第２暗号要素生成部は、数２に示す暗号要素ｃを生成する
請求項１に記載の暗号化装置。
【数１】
0006625283.tif 000139
【数２】
0006625283.tif 000140
【請求項３】
前記暗号システムは、２以上の整数ｗに関して、ｔ＝１，．．．，ｗの各整数ｔについての前記群Ｇｔ及び前記群Ｇ＾ｔを用い、
前記暗号化装置は、さらに、
２以上ｗ以下の整数ｎに関してｊ＝１，．．．，ｎの各整数ｊについての属性ｘｊを、前記群Ｇ＾ｔのうちの異なる群に割り当てるＩＤ群割当部
を備え、
前記第２暗号要素生成部は、前記ＩＤ群割当部によってｊ＝１，．．．，ｎの各整数ｊについての属性ｘｊに割り当てられた群の要素に対して前記暗号化乱数ζを設定して前記暗号要素ｃを生成する
請求項１に記載の暗号化装置。
【請求項４】
前記暗号システムは、前記群Ｇｔ及び前記群Ｇ＾ｔとして、ｔ＝１，．．．，ｎの各整数ｔと、ι＝０，１の各整数ιとについての群Ｇｔ，ι及び群Ｇ＾ｔ，ιを用い、
前記ＩＤ群割当部は、ｊ＝１，．．．，ｎの各整数ｊについての前記属性ｘｊである識別子ＩＤ’ｊであって、０又は１である識別子ＩＤ’ｊを、ｔ＝ｊかつι＝ＩＤ’ｊの群Ｇ＾ｔ，ιに割り当て、
前記第１暗号要素生成部は、数３に示す暗号要素ｃＴを生成し、
前記第２暗号要素生成部は、数４に示す暗号要素ｃを生成する
請求項３に記載の暗号化装置。
【数３】
0006625283.tif 000141
【数４】
0006625283.tif 000142
【請求項５】
前記暗号システムは、前記群Ｇｔ及び前記群Ｇ＾ｔとして、ｄ＝ｗの整数ｄに関して、ｔ＝１，．．．，ｄの各整数ｔについての群Ｇｔ及び群Ｇ＾ｔを用い、
前記ＩＤ群割当部は、属性集合Γに含まれる属性ｘｔを、群Ｇ＾ｔに割り当て、
前記第１暗号要素生成部は、数５に示す暗号要素ｃＴを生成し、
前記第２暗号要素生成部は、数６に示す暗号要素ｃを生成する
請求項３に記載の暗号化装置。
【数５】
0006625283.tif 000143
【数６】
0006625283.tif 000144
【請求項６】
前記暗号システムは、前記群Ｇｔ及び前記群Ｇ＾ｔとして、ｄ＝ｗの整数ｄに関して、ｔ＝１，．．．，ｄの各整数ｔと、ｊ＝１，．．．，ｎの各整数ｊと、ι＝０，１の各整数ιとについての群Ｇｔ，ｊ，ι及び群Ｇ＾ｔ，ｊ，ιを用い、
前記ＩＤ群割当部は、属性集合Γに含まれる属性ｘｔを、群Ｇ＾ｔに割り当て、
前記第１暗号要素生成部は、数７に示す暗号要素ｃＴを生成し、
前記第２暗号要素生成部は、数８に示す暗号要素ｃを生成する
請求項３に記載の暗号化装置。
【数７】
0006625283.tif 000145
【数８】
0006625283.tif 000146
【請求項７】
前記暗号システムは、前記群Ｇｔ及び前記群Ｇ＾ｔとして、ｄ＝ｗの整数ｄに関して、ｔ＝１，．．．，ｄの各整数ｔと、ι＝０，１の各整数ιとについての群ＧＬｔ，ι及び群ＧＲｔ，ιと、群Ｇ＾Ｌｔ，ι及び群Ｇ＾Ｒｔ，ιとを用い、
前記ＩＤ群割当部は、１以上ｄ以下の整数Ｌに関して、ｊ＝１，．．．，Ｌの各整数ｊについての前記属性ｘｊである識別子ＩＤ’ｊであって、０又は１である識別子ＩＤ’ｊを、ｔ＝ｊかつι＝ＩＤ’ｊの群Ｇ＾Ｌｔ，ι及び群Ｇ＾Ｒｔ，ιに割り当て、
前記第１暗号要素生成部は、数９に示す暗号要素ｃＴを生成し、
前記第２暗号要素生成部は、数１０に示す暗号要素ｃを生成し、
請求項３に記載の暗号化装置。
【数９】
0006625283.tif 000147
【数１０】
0006625283.tif 000148
【請求項８】
群Ｇ０と、前記群Ｇ０と対応付けられた群Ｇｔと、群Ｇ＾０と、前記群Ｇ＾０と対応付けられた群Ｇ＾ｔと、前記群Ｇ０及び前記群Ｇ＾０とペアリング演算ｅ０によって対応付けられるとともに、前記群Ｇｔ及び前記群Ｇ＾ｔとペアリング演算ｅｔによって対応付けられた群ＧＴとを用いた暗号システムにおける復号装置であり、
前記群ＧＴの要素Ｘと前記群Ｇ＾ｔの要素Ｙ＾とであって、少なくともいずれかが生成元が鍵生成乱数によって変換されて生成された要素Ｘと要素Ｙ＾とを用いて生成された暗号文ｃｔであって、前記要素Ｘに暗号化乱数ζが設定された変換情報ｚに対して、メッセージｍが設定された暗号要素ｃＴと、前記要素Ｙ＾に対して前記暗号化乱数ζが設定された暗号要素ｃとを含む暗号文ｃｔを取得する暗号文取得部と、
前記鍵生成乱数によって変換された前記群Ｇｔの要素である鍵要素ｋを含む復号鍵ｓｋと、前記暗号要素ｃとから変換情報ｚ’を生成し、前記変換情報ｚ’と前記暗号要素ｃＴとからメッセージｍ’を生成する復号部と
を備える復号装置。
【請求項９】
前記暗号文取得部は、数１１に示す前記暗号要素ｃＴ及び前記暗号要素ｃを含む前記暗号文ｃｔを取得し、
前記復号部は、数１２に示すように、前記変換情報ｚ’を生成するとともに、前記メッセージｍ’を生成する
請求項８に記載の復号装置。
【数１１】
0006625283.tif 000149
【数１２】
0006625283.tif 000150
【請求項１０】
前記暗号システムは、２以上の整数ｗに関して、ｔ＝１，．．．，ｗの各整数ｔについての前記群Ｇｔ及び前記群Ｇ＾ｔを用い、
前記暗号要素ｃは、２以上ｗ以下の整数ｎに関してｊ＝１，．．．，ｎの各整数ｊについての属性ｘｊが前記群Ｇ＾ｔのうちの異なる群に割り当てられ、前記各整数ｊについての属性ｘｊが割り当てられた群の要素に対して前記暗号化乱数ζが設定されており、
前記鍵要素ｋは、前記整数ｎに関してｊ’＝１，．．．，ｎの各整数ｊ’についての属性ｘｊ’が前記群Ｇｔのうちの異なる群に割り当てられ、前記各整数ｊ’についての属性ｘｊ’が割り当てられた群の要素に対して前記暗号化乱数ζが設定されている
請求項８に記載の復号装置。
【請求項１１】
前記暗号システムは、前記群Ｇｔ及び前記群Ｇ＾ｔとして、ｔ＝１，．．．，ｎの各整数ｔと、ι＝０，１の各整数ιとについての群Ｇｔ，ι及び群Ｇ＾ｔ，ιを用い、
前記暗号文取得部は、数１３に示す前記暗号要素ｃＴ及び前記暗号要素ｃを含む前記暗号文ｃｔを取得し、
前記復号部は、数１４に示すように、前記変換情報ｚ’を生成するとともに、前記メッセージｍ’を生成する
請求項１０に記載の復号装置。
【数１３】
0006625283.tif 000151
【数１４】
0006625283.tif 000152
【請求項１２】
前記暗号システムは、前記群Ｇｔ及び前記群Ｇ＾ｔとして、ｄ＝ｗの整数ｄに関して、ｔ＝１，．．．，ｄの各整数ｔについての群Ｇｔ及び群Ｇ＾ｔを用い、
前記暗号文取得部は、数１５に示す前記暗号要素ｃＴ及び前記暗号要素ｃを含む前記暗号文ｃｔを取得し、
前記復号部は、数１６に示すように、前記変換情報ｚ’を生成するとともに、前記メッセージｍ’を生成する
請求項１０に記載の復号装置。
【数１５】
0006625283.tif 000153
【数１６】
0006625283.tif 000154
【請求項１３】
前記暗号システムは、前記群Ｇｔ及び前記群Ｇ＾ｔとして、ｄ＝ｗの整数ｄに関して、ｔ＝１，．．．，ｄの各整数ｔと、ｊ＝１，．．．，ｎの各整数ｊと、ι＝０，１の各整数ιとについての群Ｇｔ，ｊ，ι及び群Ｇ＾ｔ，ｊ，ιを用い、
前記暗号文取得部は、数１７に示す前記暗号要素ｃＴ及び前記暗号要素ｃを含む前記暗号文ｃｔを取得し、
前記復号部は、数１８に示すように、前記変換情報ｚ’を生成するとともに、前記メッセージｍ’を生成する
請求項１０に記載の復号装置。
【数１７】
0006625283.tif 000155
【数１８】
0006625283.tif 000156
【請求項１４】
前記暗号システムは、前記群Ｇｔ及び前記群Ｇ＾ｔとして、ｄ＝ｗの整数ｄに関して、ｔ＝１，．．．，ｄの各整数ｔと、ι＝０，１の各整数ιとについての群ＧＬｔ，ι及び群ＧＲｔ，ιと、群Ｇ＾Ｌｔ，ι及び群Ｇ＾Ｒｔ，ιとを用い、
前記暗号文取得部は、数１９に示す前記暗号要素ｃＴ及び前記暗号要素ｃを含む前記暗号文ｃｔを取得し、
前記復号部は、数２０に示すように、前記変換情報ｚ’を生成するとともに、前記メッセージｍ’を生成する
請求項１０に記載の復号装置。
【数１９】
0006625283.tif 000157
【数２０】
0006625283.tif 000158
【請求項１５】
群Ｇ０と、前記群Ｇ０と対応付けられた群Ｇｔと、群Ｇ＾０と、前記群Ｇ＾０と対応付けられた群Ｇ＾ｔと、前記群Ｇ０及び前記群Ｇ＾０とペアリング演算ｅ０によって対応付けられるとともに、前記群Ｇｔ及び前記群Ｇ＾ｔとペアリング演算ｅｔによって対応付けられた群ＧＴとを用いた暗号システムにおける暗号化方法であり、
前記群ＧＴの要素Ｘと前記群Ｇ＾ｔの要素Ｙ＾とであって、少なくともいずれかが生成元が鍵生成乱数によって変換されて生成された要素Ｘと要素Ｙ＾を用いて暗号文ｃｔを生成する暗号文生成工程
を備え、
前記暗号文生成工程は、
前記要素Ｘに対して暗号化乱数ζが設定された変換情報ｚに対して、メッセージｍを設定して前記暗号文ｃｔの要素である暗号要素ｃＴを生成する第１暗号要素生成工程と、
前記要素Ｙ＾に対して前記暗号化乱数ζを設定して前記暗号文ｃｔの要素である暗号要素ｃを生成する第２暗号要素生成工程と
を備える暗号化方法。
【請求項１６】
群Ｇ０と、前記群Ｇ０と対応付けられた群Ｇｔと、群Ｇ＾０と、前記群Ｇ＾０と対応付けられた群Ｇ＾ｔと、前記群Ｇ０及び前記群Ｇ＾０とペアリング演算ｅ０によって対応付けられるとともに、前記群Ｇｔ及び前記群Ｇ＾ｔとペアリング演算ｅｔによって対応付けられた群ＧＴとを用いた暗号システムにおける暗号化プログラムであり、
前記群ＧＴの要素Ｘと前記群Ｇ＾ｔの要素Ｙ＾とであって、少なくともいずれかが生成元が鍵生成乱数によって変換されて生成された要素Ｘと要素Ｙ＾を用いて暗号文ｃｔを生成する暗号文生成処理
をコンピュータに実行させ、
前記暗号文生成処理は、
前記要素Ｘに対して暗号化乱数ζが設定された変換情報ｚに対して、メッセージｍを設定して前記暗号文ｃｔの要素である暗号要素ｃＴを生成する第１暗号要素生成処理と、
前記要素Ｙ＾に対して前記暗号化乱数ζを設定して前記暗号文ｃｔの要素である暗号要素ｃを生成する第２暗号要素生成処理と
を含む暗号化プログラム。
【請求項１７】
群Ｇ０と、前記群Ｇ０と対応付けられた群Ｇｔと、群Ｇ＾０と、前記群Ｇ＾０と対応付けられた群Ｇ＾ｔと、前記群Ｇ０及び前記群Ｇ＾０とペアリング演算ｅ０によって対応付けられるとともに、前記群Ｇｔ及び前記群Ｇ＾ｔとペアリング演算ｅｔによって対応付けられた群ＧＴとを用いた暗号システムにおける復号方法であり、
前記群ＧＴの要素Ｘと前記群Ｇ＾ｔの要素Ｙ＾とであって、少なくともいずれかが生成元が鍵生成乱数によって変換されて生成された要素Ｘと要素Ｙ＾とを用いて生成された暗号文ｃｔであって、前記要素Ｘに暗号化乱数ζが設定された変換情報ｚに対して、メッセージｍが設定された暗号要素ｃＴと、前記要素Ｙ＾に対して前記暗号化乱数ζが設定された暗号要素ｃとを含む暗号文ｃｔを取得する暗号文取得工程と、
前記鍵生成乱数によって変換された前記群Ｇｔの要素である鍵要素ｋを含む復号鍵ｓｋと、前記暗号要素ｃとから変換情報ｚ’を生成し、前記変換情報ｚ’と前記暗号要素ｃＴとからメッセージｍ’を生成する復号工程と
を備える復号方法。
【請求項１８】
群Ｇ０と、前記群Ｇ０と対応付けられた群Ｇｔと、群Ｇ＾０と、前記群Ｇ＾０と対応付けられた群Ｇ＾ｔと、前記群Ｇ０及び前記群Ｇ＾０とペアリング演算ｅ０によって対応付けられるとともに、前記群Ｇｔ及び前記群Ｇ＾ｔとペアリング演算ｅｔによって対応付けられた群ＧＴとを用いた暗号システムにおける復号プログラムであり、
前記群ＧＴの要素Ｘと前記群Ｇ＾ｔの要素Ｙ＾とであって、少なくともいずれかが生成元が鍵生成乱数によって変換されて生成された要素Ｘと要素Ｙ＾とを用いて生成された暗号文ｃｔであって、前記要素Ｘに暗号化乱数ζが設定された変換情報ｚに対して、メッセージｍが設定された暗号要素ｃＴと、前記要素Ｙ＾に対して前記暗号化乱数ζが設定された暗号要素ｃとを含む暗号文ｃｔを取得する暗号文取得処理と、
前記鍵生成乱数によって変換された前記群Ｇｔの要素である鍵要素ｋを含む復号鍵ｓｋと、前記暗号要素ｃとから変換情報ｚ’を生成し、前記変換情報ｚ’と前記暗号要素ｃＴとからメッセージｍ’を生成する復号処理と
をコンピュータに実行させる復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、高い安全性を持つＩＤベース暗号（Ｉｄｅｎｔｉｔｙ  Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ，以下ＩＢＥ）方式と、高い安全性を持つ属性ベース暗号（Ａｔｔｒｉｂｕｔｅ  Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ，以下ＡＢＥ）方式との少なくともいずれかに関する。
【背景技術】
【０００２】
量子計算機の開発が、世界的に進められている。量子計算機に対しても安全性を維持できる暗号方式として、同種写像を用いた暗号の提案が行われている。非特許文献１には、Ｉｓｏｇ−ＤＢＤＨ仮定に基づいてプレチャレンジ量子安全性が示されていた部分的に耐量子性をもつ属性ベース暗号方式が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｋｏｓｈｉｂａ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｐａｉｒｉｎｇ  ｃｒｙｐｔｏｇｒａｐｈｙ  ｍｅｅｔｓ  ｉｓｏｇｅｎｙ：  Ａ  ｎｅｗ  ｆｒａｍｅｗｏｒｋ  ｏｆ  ｉｓｏｇｅｎｏｕｓ  ｐａｉｒｉｎｇ  ｇｒｏｕｐｓ．  ＩＡＣＲ  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ  ２０１６，  １１３８  （２０１６）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献１に記載された方式は、これまで広く使われてきたＤＢＤＨ仮定のようなペアリング系の問題困難性から安全性が証明できるかどうかは不明であった。一般に、同種写像問題は、耐量子性を示すなど、ペアリング系の問題より困難と認識されている一方、まだ困難性の検証が十分になされていないため、未知の攻撃発見が懸念されている。
この発明は、複数の問題困難性から安全性を示すことができる暗号方式を構成可能にすることを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る暗号化装置は、
群Ｇ０と、前記群Ｇ０と対応付けられた群Ｇｔと、群Ｇ＾０と、前記群Ｇ＾０と対応付けられた群Ｇ＾ｔと、前記群Ｇ０及び前記群Ｇ＾０とペアリング演算ｅ０によって対応付けられるとともに、前記群Ｇｔ及び前記群Ｇ＾ｔとペアリング演算ｅｔによって対応付けられた群ＧＴとを用いた暗号システムにおける暗号化装置であり、
前記群ＧＴの要素Ｘと前記群Ｇ＾ｔの要素Ｙ＾との生成要素を用いて暗号文ｃｔ’を生成する暗号文生成部であって、前記要素Ｘは前記群ＧＴの生成元が鍵生成乱数によって変換されて生成された、又は、前記要素Ｙ＾は前記群Ｇ＾ｔの生成元が鍵生成乱数によって変換されて生成された前記生成要素を用いて暗号文ｃｔ’を生成する暗号文生成部
を備え、
前記暗号文生成部は、
前記要素Ｘに対して暗号化乱数ζが設定された変換情報ｚに対して、メッセージｍを設定して前記暗号文ｃｔ’の要素である暗号要素ｃＴを生成する第１暗号要素生成部と、
前記要素Ｙ＾に対して前記暗号化乱数ζを設定して前記暗号文ｃｔ’の要素である暗号要素ｃを生成する第２暗号要素生成部と
を備える。
【発明の効果】
【０００６】
この発明では、対応付けが行われた複数の群を用いることにより、ある問題困難性から安全性を示すことを可能とすることができる。また、この発明では、鍵生成乱数によって変換されて生成された生成要素を用いて暗号文ｃｔＩＤ’を生成することにより、別の問題困難性から安全性を示すことを可能とすることができる。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１に係るＩＢＥ方式で用いられる同種ペアリンググループの説明図。
【図２】実施の形態１に係る暗号システム１の構成図。
【図３】実施の形態１に係る鍵生成装置１０の構成図。
【図４】実施の形態１に係る暗号化装置２０の構成図。
【図５】実施の形態１に係る復号装置３０の構成図。
【図６】実施の形態１に係るＳｅｔｕｐアルゴリズムのフローチャート。
【図７】実施の形態１に係るＩＰＧの説明図。
【図８】実施の形態１に係るＫｅｙＧｅｎアルゴリズムのフローチャート。
【図９】実施の形態１に係るＥｎｃアルゴリズムのフローチャート。
【図１０】実施の形態１に係るＤｅｃアルゴリズムのフローチャート。
【図１１】変形例１に係る鍵生成装置１０の構成図。
【図１２】変形例１に係る暗号化装置２０の構成図。
【図１３】変形例１に係る復号装置３０の構成図。
【図１４】実施の形態２に係るＩＤ群の性質の説明図。
【図１５】実施の形態２に係るＳｅｔｕｐアルゴリズムにおけるＩＤ群の説明図。
【図１６】実施の形態２に係るＫｅｙＧｅｎアルゴリズムにおけるＩＤ群の説明図。
【図１７】実施の形態２に係るＥｎｃアルゴリズムにおけるＩＤ群の説明図。
【図１８】実施の形態２に係るＤｅｃアルゴリズムにおけるＩＤ群の説明図。
【図１９】実施の形態２に係る鍵生成装置１０の構成図。
【図２０】実施の形態２に係る暗号化装置２０の構成図。
【図２１】実施の形態２に係るＳｅｔｕｐアルゴリズムのフローチャート。
【図２２】実施の形態２に係るＫｅｙＧｅｎアルゴリズムのフローチャート。
【図２３】実施の形態２に係るＥｎｃアルゴリズムのフローチャート。
【図２４】実施の形態３に係る暗号システム１の構成図。
【図２５】実施の形態５に係る暗号システム１の構成図。
【図２６】実施の形態５に係る鍵委譲装置４０の構成図。
【図２７】実施の形態５に係るＤｅｌｅｇａｔｅアルゴリズムのフローチャート。
【発明を実施するための形態】
【０００８】
実施の形態１．
実施の形態１では、高安全高効率なＩＢＥ方式を説明する。
【０００９】
＊＊＊表記の説明＊＊＊
以下の説明における記法について説明する。
なお、以下の説明では、数式中で変数の上に記載された記号等が、文中では変数の右上に示される。具体的には、記号“＾”及び記号“→”は、数式中では変数の上に記載されるが、文中では変数の右上に示される。例えば、数１０１は、文中ではＢ＾と記載される。
【数１０１】
0006625283.tif 000002
また、ベクトルを表す記号“→”が上付き文字に付される場合、記号“→”は上付文字に対する上付き文字で示されているものとする。つまり、ｇｙ→は、ｙ→がｇの上付き文字として示されていることを意味する。
【００１０】
Ａがランダムな変数または分布であるとき、数１０２は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０２において、ｙは乱数である。
【数１０２】
0006625283.tif 000003
Ａが集合であるとき、数１０３は、Ａからｙを一様に選択することを表す。つまり、数１０３において、ｙは一様乱数である。
【数１０３】
0006625283.tif 000004
数１０４、つまりＦｑは、位数ｑの有限体を示す。
【数１０４】
0006625283.tif 000005
０より大きい整数ｎについて、数１０５が成立するものとする。
【数１０５】
0006625283.tif 000006
数１０６は、数１０７に示す２つのベクトルｙ→とｖ→との数１０８に示す内積を表す。
【数１０６】
0006625283.tif 000007
【数１０７】
0006625283.tif 000008
【数１０８】
0006625283.tif 000009
数１０９に示す直積群Ｋの要素ｇ（ｒｅｓｐ．直積群Ｋ＾の要素ｇ＾）と、数１１０に示すベクトルｙとに対して、ｇｙ→は、数１１１に示す群要素を示す。
【数１０９】
0006625283.tif 000010
【数１１０】
0006625283.tif 000011
【数１１１】
0006625283.tif 000012
スカラーζ∈Ｆｑに対して、ｇζは、数１１２に示すスカラー累乗を示す。
【数１１２】
0006625283.tif 000013
上述した直積群Ｋ及び直積群Ｋ＾の要素ｇ：＝（ｇｉ）及び要素ｇ＾：＝（ｇ＾ｉ）に対して、ペアリングｅｉが数１１３に示す空間で定義されているなら、ペアリングｅＫは、数１１４のように定義される。
【数１１３】
0006625283.tif 000014
【数１１４】
0006625283.tif 000015
【００１１】
＊＊＊概念の説明＊＊＊
図１を参照して、実施の形態１に係るＩＢＥ方式で用いられる同種ペアリンググループ（以下、ＩＰＧ）について説明する。
【００１２】
ＩＰＧは、同種写像とペアリング演算とによって対応付けられた複数の群を有する。
具体的には、ＩＰＧは、群Ｇ０と、群Ｇ０と同種写像φｔによって対応付けられたｔ＝１，．．．，ｄの各群Ｇｔと、群Ｇ＾０と同種写像φｔによって対応付けられたｔ＝１，．．．，ｄの各群Ｇ＾ｔと、ｔ＝０，．．．，ｄの各群Ｇｔ及び群Ｇ＾ｔとペアリング演算ｅｔによって対応付られた群ＧＴとを有する。そして、ＩＰＧでは、要素が群Ｇ０×群Ｇ＾０からペアリング演算ｅ０で変換された場合と、ｔ＝１，．．．，ｄのいずれの整数ｔについての同種写像φｔによって群Ｇ０×群Ｇ＾０から群Ｇｔ×群Ｇ＾ｔに変換された上で、ペアリング演算ｅｔによって変換された場合とで、結果は等しくなる。
例えば、ｔ＝０，．．．，ｄの各整数ｔについての群Ｇｔ及び群Ｇ＾ｔは、異なる楕円曲線における群である。
【００１３】
より正確には、ＩＰＧは以下のように定義される。
ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，Ｎ）では、数１１５に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｍｓｋＩＰＧとのマスター鍵ペアがランダムに生成される。
【数１１５】
0006625283.tif 000016
ここで、（Ｇｔ，Ｇ＾ｔ，ｅｔ，ＧＴ）は、ペアリング演算ｅｔ：Ｇｔ×Ｇ＾ｔ→ＧＴと、トラップドア準同型写像φｔとを有する素数位数ｑの非対称ペアリング群である。トラップドア準同型写像φｔは、異なる楕円曲線の間の同種写像によって与えられた自然な同一性Ｇ＝Ｇ×１Ｇ＾及びＧ＾＝１Ｇ×Ｇ＾の下でのＧｔ＝φｔ（Ｇ０）及びＧ＾ｔ＝φｔ（Ｇ＾０）であるＧ０×Ｇ＾０からＧｔ×Ｇ＾ｔへの写像である。ｇｔ＝φｔ（ｇ０）∈Ｇｔ，ｇ＾ｔ＝φｔ（ｇ＾０）∈Ｇ＾ｔである。
ＩＰＧは、数１１６に示す両立性を有する。
【数１１６】
0006625283.tif 000017
ここで、ｇＴ＝ｅ０（ｇ０，ｇ＾０）≠１である。また、Ｇｔ≠Ｇ＾ｔである。
【００１４】
＊＊＊構成の説明＊＊＊
実施の形態１に係るＩＢＥ方式の構成を説明する。
ＩＢＥ方式は、Ｓｅｔｕｐアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｅｎｃアルゴリズムと、Ｄｅｃアルゴリズムとを備える。
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開パラメータｐｋと、マスター秘密鍵ｍｓｋとを出力する。
ＫｅｙＧｅｎアルゴリズムは、公開パラメータｐｋと、マスター秘密鍵ｍｓｋと、識別子ＩＤとを入力として、識別子ＩＤに対応した復号鍵ｓｋＩＤを出力する。
Ｅｎｃアルゴリズムは、公開パラメータｐｋと、メッセージ空間ｍｓｇにおけるメッセージｍと、識別子ＩＤ’とを入力として、暗号文ｃｔＩＤ’を出力する。
Ｄｅｃアルゴリズムは、公開パラメータｐｋと、識別子ＩＤに対応した復号鍵ｓｋＩＤと、識別子ＩＤ’の下で暗号化された暗号文ｃｔＩＤ’とを入力として、メッセージｍ’∈ｍｓｇ、又は、復号に失敗したことを示す識別情報⊥を出力する。
【００１５】
図２を参照して、実施の形態１に係る暗号システム１の構成を説明する。
暗号システム１は、鍵生成装置１０と、暗号化装置２０と、復号装置３０とを備える。鍵生成装置１０と、暗号化装置２０と、復号装置３０とは、伝送路を介して接続されている。伝送路は、具体例としては、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、又は、インターネットである。鍵生成装置１０と、暗号化装置２０と、復号装置３０とは、伝送路を介して通信可能である。
【００１６】
鍵生成装置１０は、セキュリティパラメータ１λを入力として、Ｓｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋと、マスター秘密鍵ｍｓｋとを生成する。また、鍵生成装置１０は、公開パラメータｐｋと、マスター秘密鍵ｍｓｋと、識別子ＩＤとを入力として、ＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＩＤを生成する。
鍵生成装置１０は、公開パラメータｐｋを公開し、復号鍵ｓｋＩＤを識別子ＩＤに対応する復号装置３０に出力する。鍵生成装置１０は、マスター秘密鍵ｍｓｋを保管する。
なお、Ｓｅｔｕｐアルゴリズムは、暗号システム１０のセットアップ時等に１度だけ実行されればよい。
【００１７】
暗号化装置２０は、公開パラメータｐｋと、メッセージｍと、識別子ＩＤ’とを入力として、Ｅｎｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を生成する。暗号化装置２０は、暗号文ｃｔＩＤ’を復号装置３０に出力する。
【００１８】
復号装置３０は、公開パラメータｐｋと、復号鍵ｓｋＩＤと、暗号文ｃｔＩＤ’とを入力として、Ｄｅｃアルゴリズムを実行して、メッセージｍ’、又は、復号に失敗したことを示す識別情報⊥を生成する。
【００１９】
図３を参照して、実施の形態１に係る鍵生成装置１０の構成を説明する。
鍵生成装置１０は、プロセッサ１１と、記憶装置１２と、入出力インタフェース１３とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２０】
鍵生成装置１０は、機能構成要素として、マスター鍵生成部１４と、復号鍵生成部１５と、鍵出力部１６とを備える。マスター鍵生成部１４と、復号鍵生成部１５と、鍵出力部１６との各部の機能はソフトウェアにより実現される。
記憶装置１２には、鍵生成装置１０の各部の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ１１により読み込まれ、プロセッサ１１によって実行される。これにより、鍵生成装置１０の各部の機能が実現される。
【００２１】
図４を参照して、実施の形態１に係る暗号化装置２０の構成を説明する。
暗号化装置２０は、プロセッサ２１と、記憶装置２２と、入出力インタフェース２３とのハードウェアを備える。プロセッサ２１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２２】
暗号化装置２０は、機能構成要素として、取得部２４と、暗号文生成部２５と、暗号文出力部２６とを備える。暗号文生成部２５は、変換情報生成部２５１と、第１暗号要素生成部２５２と、第２暗号要素生成部２５３とを備える。取得部２４と、暗号文生成部２５と、変換情報生成部２５１と、第１暗号要素生成部２５２と、第２暗号要素生成部２５３と、暗号文出力部２６との各部の機能はソフトウェアにより実現される。
記憶装置２２には、暗号化装置２０の各部の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ２１により読み込まれ、プロセッサ２１によって実行される。これにより、暗号化装置２０の各部の機能が実現される。
【００２３】
図５を参照して、実施の形態１に係る復号装置３０の構成を説明する。
復号装置３０は、プロセッサ３１と、記憶装置３２と、入出力インタフェース３３とのハードウェアを備える。プロセッサ３１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２４】
復号装置３０は、機能構成要素として、取得部３４と、復号部３５と、メッセージ出力部３６とを備える。取得部３４は、復号鍵取得部３４１と、暗号文取得部３４２とを備える。復号部３５は、変換情報生成部３５１と、メッセージ生成部３５２とを備える。取得部３４と、復号鍵取得部３４１と、暗号文取得部３４２と、復号部３５と、変換情報生成部３５１と、メッセージ生成部３５２と、メッセージ出力部３６との各部の機能はソフトウェアにより実現される。
記憶装置３２には、復号装置３０の各部の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ３１により読み込まれ、プロセッサ３１によって実行される。これにより、復号装置３０の各部の機能が実現される。
【００２５】
プロセッサ１１，２１，３１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ１１，２１，３１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００２６】
記憶装置１２，２２，３２は、具体例としては、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、記憶装置１２，２２，３２は、は、ＳＤ（Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤといった可搬記憶媒体であってもよい。
【００２７】
入出力インタフェース１３，２３，３３は、外部からデータの入力を受け付け、外部へデータを出力するためのインタフェースである。入出力インタフェース１３，２３，３３は、具体例としては、キーボードといった入力装置と、ディスプレイといった出力装置とを接続するＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＰＳ／２、ＨＤＭＩ（登録商標、Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）といったコネクタである。また、入出力インタフェース１３，２３，３３は、具体例としては、外部からネットワークを介してデータを送受信するＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）であってもよい。
【００２８】
プロセッサ１１によって実現される各部の機能の処理の結果を示す情報とデータと信号値と変数値は、記憶装置１２、又は、プロセッサ１１内のレジスタ又はキャッシュメモリに記憶される。同様に、プロセッサ２１によって実現される各部の機能の処理の結果を示す情報とデータと信号値と変数値は、記憶装置２２、又は、プロセッサ２１内のレジスタ又はキャッシュメモリに記憶される。同様に、プロセッサ３１によって実現される各部の機能の処理の結果を示す情報とデータと信号値と変数値は、記憶装置３２、又は、プロセッサ３１内のレジスタ又はキャッシュメモリに記憶される。
【００２９】
プロセッサ１１によって実現される各機能を実現するプログラムは、記憶装置１２に記憶されているとした。同様に、プロセッサ２１によって実現される各機能を実現するプログラムは、記憶装置２２に記憶されているとした。同様に、プロセッサ３１によって実現される各機能を実現するプログラムは、記憶装置３２に記憶されているとした。しかし、このプログラムは、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤといった可搬記憶媒体に記憶されてもよい。
【００３０】
図３では、プロセッサ１１は、１つだけ示されていた。しかし、鍵生成装置１０は、プロセッサ１１を代替する複数のプロセッサを備えていてもよい。これら複数のプロセッサは、鍵生成装置１０の各部の機能を実現するプログラムの実行を分担する。それぞれのプロセッサは、プロセッサ１１と同じように、プロセッシングを行うＩＣである。同様に、暗号化装置２０は、プロセッサ２１を代替する複数のプロセッサを備えていてもよい。また、復号装置３０は、プロセッサ３１を代替する複数のプロセッサを備えていてもよい。
【００３１】
＊＊＊動作の説明＊＊＊
図３から図１０を参照して、実施の形態１に係る暗号システム１の動作を説明する。
実施の形態１に係る暗号システム１の動作は、実施の形態１に係る暗号方法に相当する。また、実施の形態１に係る暗号システム１の動作は、実施の形態１に係る暗号プログラムの処理に相当する。
実施の形態１に係る鍵生成装置１０の動作は、実施の形態１に係る鍵生成方法に相当する。また、実施の形態１に係る鍵生成装置１０の動作は、実施の形態１に係る鍵生成プログラムの処理に相当する。
実施の形態１に係る暗号化装置２０の動作は、実施の形態１に係る暗号化方法に相当する。また、実施の形態１に係る暗号化装置２０の動作は、実施の形態１に係る暗号化プログラムの処理に相当する。
実施の形態１に係る復号装置３０の動作は、実施の形態１に係る復号方法に相当する。また、実施の形態１に係る復号装置３０の動作は、実施の形態１に係る復号プログラムの処理に相当する。
【００３２】
図３及び図６を参照して、実施の形態１に係るＳｅｔｕｐアルゴリズムを説明する。
Ｓｅｔｕｐアルゴリズムは、鍵生成装置１０によって実行される。
【００３３】
（ステップＳ１１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λの入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、ｄ＝１とを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）を実行して、数１１７に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｍｓｋＩＰＧとのマスター鍵ペアを生成する。
【数１１７】
0006625283.tif 000018
【００３４】
つまり、図７に示すように、実施の形態１では、ｔ＝０，１についての群Ｇｔ及び群Ｇ＾ｔとペアリング演算ｅｔと、群ＧＴと、同種写像φ１とが生成される。
なお、図７に示されるように、Ｇ０からＧ１への変換が“復号鍵生成（ＫｅｙＧｅｎ）”に、Ｇ０×Ｇ＾０からＧＴへの変換が“暗号化（Ｅｎｃ）”に、Ｇ１×Ｇ＾１からＧＴへの変換が“復号（Ｄｅｃ）”に大まかに対応している。
【００３５】
（ステップＳ１２：ハッシュ関数生成処理）
マスター鍵生成部１４は、識別子の空間である体Ｆｑの要素を、群Ｇ０の要素に変換するランダムなハッシュ関数Ｈを生成する。
【００３６】
（ステップＳ１３：鍵生成乱数生成処理）
マスター鍵生成部１４は、一様乱数である鍵生成乱数γを生成する。
【００３７】
（ステップＳ１４：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ１１で生成された公開パラメータｐｋＩＰＧと、ステップＳ１２で生成されたハッシュ関数Ｈとを用いて、公開パラメータｐｋ：＝（（Ｇｔ，Ｇ＾ｔ，ｅｔ）ｔ＝０，１，ｇ＾０’：＝ｇ＾０γ，ｇ＾１，ＧＴ，Ｈ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ１１で生成されたマスター秘密鍵ｍｓｋＩＰＧと、ステップＳ１３で生成された鍵生成乱数γとを用いて、マスター秘密鍵ｍｓｋ：＝（φ１，γ）を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｍｓｋを記憶装置１２に書き込む。
【００３８】
つまり、マスター鍵生成部１４は、数１１８に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１１８】
0006625283.tif 000019
【００３９】
図３及び図８を参照して、実施の形態１に係るＫｅｙＧｅｎアルゴリズムを説明する。
ＫｅｙＧｅｎアルゴリズムは、鍵生成装置１０によって実行される。
【００４０】
（ステップＳ２１：ＩＤ受付処理）
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋＩＤを使用するユーザの識別子ＩＤの入力を受け付ける。識別子ＩＤは、例えば、鍵生成装置１０の使用者によって入力装置を介して入力される。
【００４１】
（ステップＳ２２：鍵要素生成処理）
復号鍵生成部１５は、ステップＳ２１で受け付けられた識別子ＩＤを入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈを計算して、群Ｇ０の要素である要素ｈ０を生成する。
復号鍵生成部１５は、マスター秘密鍵ｍｓｋに含まれる同種写像φ１及び鍵生成乱数γで要素ｈ０を変換して、要素ｈ１を生成する。具体的には、復号鍵生成部１５は、数１１９に示すように、同種写像φ１及び鍵生成乱数γで要素ｈ０を変換して、鍵要素ｋである要素ｈ１を生成する。
【数１１９】
0006625283.tif 000020
つまり、要素ｈ１は、鍵生成乱数γで変換された群Ｇｔ（＝群Ｇ１）の要素である。
【００４２】
（ステップＳ２３：鍵出力処理）
鍵出力部１６は、ステップＳ２１で受け付けられた識別子ＩＤと、ステップＳ２２で生成された要素ｈ１とを含む復号鍵ｓｋＩＤを、入出力インタフェース１３を介して復号装置３０に出力する。この際、鍵出力部１６は、何らかの暗号方式で暗号化するといった方法により、復号鍵ｓｋＩＤが第三者に漏えいしないようにする。
【００４３】
つまり、復号鍵生成部１５は、数１２０に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＩＤを生成する。
【数１２０】
0006625283.tif 000021
【００４４】
図４及び図９を参照して、実施の形態１に係るＥｎｃアルゴリズムを説明する。
Ｅｎｃアルゴリズムは、暗号化装置２０によって実行される。
【００４５】
（ステップＳ３１：取得処理）
取得部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋを取得する。また、取得部２４は、暗号化対象のメッセージｍと、復号条件となる識別子ＩＤ’との入力を受け付ける。メッセージｍと識別子ＩＤ’とは、例えば、暗号化装置２０の使用者によって入力装置を介して入力される。
【００４６】
（ステップＳ３２：暗号文生成処理）
暗号文生成部２５は、ステップＳ３１で取得された公開パラメータｐｋ及び識別子ＩＤ’を用いて、暗号文ｃｔＩＤ’の要素を生成する。暗号文生成部２５は、群ＧＴの要素Ｘと群Ｇ＾ｔの要素Ｙ＾との生成要素を用いて暗号文ｃｔＩＤ’の要素を生成する。ここで、要素Ｘは、後述するｅ０（ｈ０，ｇ＾０’）のことであり、要素Ｙ＾は、公開パラメータｐｋに含まれるｇ＾１のことである。
暗号文生成処理は、ステップＳ３２１からステップＳ３２３の処理を含む。
【００４７】
（ステップＳ３２１：変換情報生成処理）
変換情報生成部２５１は、ステップＳ３１で受け付けられた識別子ＩＤ’を入力として、公開パラメータｐｋに含まれるハッシュ関数Ｈを計算して、群Ｇ０の要素である要素ｈ０を生成する。また、変換情報生成部２５１は、一様乱数である暗号化乱数ζを生成する。
変換情報生成部２５１は、要素ｈ０と、暗号化乱数ζとを用いて、数１２１に示すように、変換情報ｚを生成する。
【数１２１】
0006625283.tif 000022
つまり、変換情報生成部２５１は、群ＧＴの要素Ｘであるｅ０（ｈ０，ｇ＾０’）を、暗号化乱数ζを用いて変換して変換情報ｚを生成する。また、要素Ｘであるｅ０（ｈ０，ｇ＾０’）は、ｇ＾０’：＝ｇ＾０γを含んでいるため、群ＧＴの生成元（ｇ＾０）が鍵生成乱数γによって変換されて生成されている。
【００４８】
（ステップＳ３２２：第１暗号要素生成処理）
第１暗号要素生成部２５２は、数１２２に示すように、ステップＳ３２１で生成された変換情報ｚに対して、メッセージｍを設定して暗号文ｃｔＩＤ’の要素である暗号要素ｃＴを生成する。
【数１２２】
0006625283.tif 000023
【００４９】
（ステップＳ３２３：第２暗号要素生成処理）
第２暗号要素生成部２５３は、数１２３に示すように、要素Ｙ＾であるｇ＾１に対して暗号化乱数ζを設定して暗号文ｃｔＩＤ’の要素である暗号要素ｃを生成する。
【数１２３】
0006625283.tif 000024
【００５０】
（ステップＳ３３：暗号文出力処理）
暗号文出力部２６は、ステップＳ３１で受け付けられた識別子ＩＤ’と、ステップＳ３２で生成された暗号要素ｃＴ，ｃとを暗号要素とする暗号文ｃｔＩＤ’を、入出力インタフェース２３を介して復号装置３０に出力する。
【００５１】
つまり、暗号化装置２０は、数１２４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を生成する。
【数１２４】
0006625283.tif 000025
【００５２】
図５及び図１０を参照して、実施の形態１に係るＤｅｃアルゴリズムを説明する。
Ｄｅｃアルゴリズムは、復号装置３０によって実行される。
【００５３】
（ステップＳ４１：取得処理）
取得部３４は、入出力インタフェース３３を介して、鍵生成装置１０によって生成された公開パラメータｐｋ及び復号鍵ｓｋＩＤと、暗号化装置２０によって生成された暗号文ｃｔＩＤ’とを取得する。
取得処理は、ステップＳ４１１とステップＳ４１２との処理を含む。
【００５４】
（ステップＳ４１１：復号鍵取得処理）
復号鍵取得部３４１は、入出力インタフェース３３を介して、鍵生成装置１０によって生成された公開パラメータｐｋ及び復号鍵ｓｋＩＤを取得する。ここで、復号鍵ｓｋＩＤは、鍵生成乱数γで変換された群Ｇｔ（＝群Ｇ１）の要素である要素ｈ１を鍵要素ｋとして含む。
【００５５】
（ステップＳ４１２：暗号文取得処理）
暗号文取得部３４２は、暗号化装置２０によって生成された暗号文ｃｔＩＤ’を取得する。ここで、暗号文ｃｔＩＤ’は、暗号要素ｃＴと、暗号要素ｃとが含まれる。暗号要素ｃＴは、群ＧＴの生成元（ｅ０（ｈ０，ｇ＾０））が鍵生成乱数γによって変換されて生成された要素Ｘに対して暗号化乱数ζが設定された変換情報ｚに、メッセージｍが設定されている。暗号要素ｃは、要素Ｙ＾であるｇ＾１に対して暗号化乱数ζが設定されている。
【００５６】
（ステップＳ４２：復号判定処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＩＤに含まれる識別子ＩＤと、暗号文ｃｔＩＤ’に含まれる識別子ＩＤ’とが等しいか否かを判定する。これにより、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤで復号可能かが判定される。
復号部３５は、識別子ＩＤと識別子ＩＤ’とが等しいと判定された場合、つまり復号可能と判定された場合、処理をステップＳ４３に進め、そうでない場合、処理をステップＳ４５に進める。
【００５７】
（ステップＳ４３：復号処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＩＤにより、暗号文ｃｔＩＤ’を復号して、メッセージｍ’を生成する。
復号処理は、ステップＳ４３１とステップＳ４３２との処理を含む。
【００５８】
（ステップＳ４３１：変換情報生成処理）
変換情報生成部３５１は、ステップＳ４１１で取得された復号鍵ｓｋＩＤに含まれる要素ｈ１と、ステップＳ４１２で取得された暗号文ｃｔＩＤ’に含まれる暗号要素ｃとを用いて、数１２５に示すように、変換情報ｚ’を生成する。
【数１２５】
0006625283.tif 000026
ここで、数１２６であるため、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤが復号可能であれば、変換情報ｚ’と変換情報ｚとは同一になる。
【数１２６】
0006625283.tif 000027
【００５９】
（ステップＳ４３２：メッセージ生成処理）
メッセージ生成部３５２は、ステップＳ４３１で生成された変換情報ｚ’と、ステップＳ４１２で取得された暗号文ｃｔＩＤ’に含まれる暗号要素ｃＴとを用いて、数１２７に示すように、メッセージｍ’を生成する。
【数１２７】
0006625283.tif 000028
【００６０】
（ステップＳ４４：メッセージ出力処理）
メッセージ出力部３６は、ステップＳ４３で計算されたメッセージｍ’を、入出力インタフェース３３を介して出力する。
【００６１】
（ステップＳ４５：識別情報出力処理）
メッセージ出力部３６は、復号に失敗したことを示す識別情報⊥を、入出力インタフェース３３を介して出力する。
【００６２】
つまり、復号装置３０は、数１２８に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数１２８】
0006625283.tif 000029
【００６３】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る暗号システム１は、ＩＰＧを用いてＩＢＥ方式を実現する。ＩＰＧは、対応付けが行われた複数の群により構成される。そのため、複数の群の対応付けに使用された写像に基づく問題困難性から安全性を示すことを可能とすることができる。具体的には、ＩＰＧでは、群Ｇ０と、ｔ＝１，．．．，ｄの各群Ｇｔとの間と、群Ｇ＾０と、ｔ＝１，．．．，ｄの各群Ｇ＾ｔとの間とが同種写像φｔによって対応付けられている。これにより、同種写像問題困難性から安全性を示すことを可能とすることができる。
【００６４】
また、実施の形態１に係る暗号システム１は、鍵生成乱数γによって変換された生成要素である要素Ｘを用いて暗号文ｃｔＩＤ’を生成する。具体的には、暗号システム１は、要素Ｘであるｅ０（ｈ０，ｇ＾０’）を用いて暗号文ｃｔＩＤ’の要素である暗号要素ｃＴを生成する。要素Ｘであるｅ０（ｈ０，ｇ＾０’）は、群ＧＴの生成元（ｇ＾０）が鍵生成乱数γによって変換されて生成されている。これにより、ペアリング問題困難性から安全性を示すことを可能とすることができる。
【００６５】
＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、鍵生成装置１０、暗号化装置２０、復号装置３０の各部の機能がソフトウェアで実現された。変形例１として、鍵生成装置１０、暗号化装置２０、復号装置３０の各部の機能はハードウェアで実現されてもよい。この変形例１について、実施の形態１と異なる点を説明する。
【００６６】
図１１から図１３を参照して、変形例１に係る鍵生成装置１０、暗号化装置２０、復号装置３０の構成を説明する。
各部の機能がハードウェアで実現される場合、鍵生成装置１０、暗号化装置２０、復号装置３０は、プロセッサ１１，２１，３１と記憶装置１２，２２，３２とに代えて、電子回路１８，２８，３８を備える。電子回路１８，２８，３８は、鍵生成装置１０、暗号化装置２０、復号装置３０の各部の機能と、記憶装置１２，２２，３２の機能とを実現する専用の回路である。
【００６７】
電子回路１８，２８，３８は、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
鍵生成装置１０、暗号化装置２０、復号装置３０は、電子回路１８，２８，３８を代替する複数の電子回路を備えていてもよい。これら複数の電子回路により、全体として各部の機能が実現される。それぞれの電子回路は、電子回路１８，２８，３８と同じように、専用の回路である。
【００６８】
＜変形例２＞
変形例２として、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。つまり、鍵生成装置１０、暗号化装置２０、復号装置３０の各部のうち、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。
【００６９】
プロセッサ１１，２１，３１と記憶装置１２，２２，３２と電子回路１８，２８，３８とを、処理回路という。つまり、各部の機能は、処理回路により実現される。
【００７０】
実施の形態２．
実施の形態２では、高安全なベーシックＩＢＥ方式を説明する。
実施の形態２では、実施の形態１と同一の点については説明を省略し、異なる点を説明する。
【００７１】
＊＊＊キーテクニック＊＊＊
実施の形態２に係るＩＢＥ方式で用いられるキーテクニックを説明する。
従来ペアリングを用いて実現されたＩＢＥは、ただ一対のペアリング群Ｇ，Ｇ＾上に、秘密鍵及び暗号文をエンコードしていた。これに対して、実施の形態２に係るＩＢＥは、ＩＤ毎に異なる群ＧＩＤ，Ｇ＾ＩＤをそのＩＤに対応させる。これらの群ＧＩＤ，Ｇ＾ＩＤをＩＤ群と呼ぶ。
これにより、図１４に示す関係が成立する。図１４では、矢印は、“ｉｆ  ａｎｄ  ｏｎｌｙ  ｉｆ”を意味する。つまり、ＩＤ≠ＩＤ’である場合かつその場合に限り、ＧＩＤ≠ＧＩＤ’である。また、ＧＩＤ≠ＧＩＤ’である場合かつその場合に限り、Ｇ＾ＩＤ≠Ｇ＾ＩＤ’である。
【００７２】
図１５から図１８を参照して具体的に説明する。なお、以下の説明でＩＤｊが下付きで示されている場合には、このＩＤｊはＩＤｊを意味し、ＩＤ’ｊが下付きで示されている場合には、このＩＤ’ｊはＩＤ’ｊを意味する。
図１５に示すように、Ｓｅｔｕｐアルゴリズムでは、群Ｇｔとして、ｊ＝１，．．．，ｎの各整数ｊと、ι＝０，１の各整数ιとについての群Ｇｊ，ι及び群Ｇ＾ｊ，ιが生成される。つまり、２ｎ個の群Ｇｊ，ι及び２ｎ個の群Ｇ＾ｊ，ιが生成される。
図１６に示すように、ＫｅｙＧｅｎアルゴリズムでは、ｊ＝１，．．．，ｎの各整数ｊについてのＩＤｊの集合であるＩＤが入力される。ここで、ＩＤｊは、０又は１である。そして、ｊ＝１，．．．，ｎの各整数ｊについて、ＩＤｊに対して、群Ｇｊ，ＩＤｊが割り当てられる。ｊ＝１，．．．，ｎの各整数ｊについて、ＩＤｊに割り当てられた群Ｇｊ，ＩＤｊの直積がＩＤ群ＧＩＤである。つまり、ＩＤ＝０１．．．１０である場合には、ＩＤ群ＧＩＤ：＝Ｇ１，０×Ｇ２，１×・・・×Ｇｎ−１，１×Ｇｎ，０である。
図１７に示すように、Ｅｎｃアルゴリズムでは、ｊ＝１，．．．，ｎの各整数ｊについてのＩＤ’ｊの集合であるＩＤ’が入力される。ここで、ＩＤ’ｊは、０又は１である。そして、ｊ＝１，．．．，ｎの各整数ｊについて、ＩＤ’ｊに対して、群Ｇ＾ｊ，ＩＤ’ｊが割り当てられる。ｊ＝１，．．．，ｎの各整数ｊについて、ＩＤ’ｊに割り当てられた群Ｇ＾ｊ，ＩＤ’ｊの直積がＩＤ群Ｇ＾ＩＤ’である。つまり、ＩＤ’＝０１．．．１０である場合には、ＩＤ群Ｇ＾ＩＤ’：＝Ｇ＾１，０×Ｇ＾２，１×・・・×Ｇ＾ｎ−１，１×Ｇ＾ｎ，０である。
図１８に示すように、Ｄｅｃアルゴリズムでは、ｊ＝１，．．．，ｎの各整数ｊについて、ＩＤｊに割り当てられた群Ｇｊ，ＩＤｊの要素と、ＩＤ’ｊに割り当てられた群Ｇ＾ｊ、ＩＤ’ｊの要素とのペアリング演算の直積が計算される。このとき、ＩＤ＝ＩＤ’であれば、ｊ＝１，．．．，ｎの各整数ｊについての群Ｇｊ，ＩＤｊと群Ｇ＾ｊ，ＩＤ’ｊとが対応している。そのため、ｊ＝１，．．．，ｎの各整数ｊについてペアリング演算が計算された結果が群ＧＴの要素になる。しかし、ＩＤ≠ＩＤ’である場合には、ｊ＝１，．．．，ｎのうち少なくとも一部の整数ｊについての群Ｇｊ，ＩＤｊと群Ｇ＾ｊ，ＩＤ’ｊとが対応していない。そのため、ｊ＝１，．．．，ｎのうち少なくとも一部の整数ｊについてペアリング演算が計算された結果が群ＧＴの要素にならない。一部の整数ｊについてでもペアリング演算が計算された結果が群ＧＴの要素にならなければ、正しく復号することはできない。
【００７３】
＊＊＊構成の説明＊＊＊
図１９を参照して、実施の形態２に係る鍵生成装置１０の構成を説明する。
鍵生成装置１０は、機能構成要素としてＩＤ群割当部１７を備える点が図３に示す鍵生成装置１０と異なる。ＩＤ群割当部１７は、他の機能構成要素の機能と同様に、ソフトウェア又はハードウェアにより実現される。
【００７４】
図２０を参照して、実施の形態２に係る暗号化装置２０の構成を説明する。
暗号化装置２０は、機能構成要素としてＩＤ群割当部２７を備える点が図４に示す暗号化装置２０と異なる。ＩＤ群割当部２７は、他の機能構成要素の機能と同様に、ソフトウェア又はハードウェアにより実現される。
【００７５】
＊＊＊動作の説明＊＊＊
図５と、図１０と、図１９から図２３とを参照して、実施の形態２に係る暗号システム１の動作を説明する。実施の形態２についても、実施の形態１と同様に各動作は、各方法及び各プログラムの処理に相当する。
【００７６】
図１９及び図２１を参照して、実施の形態２に係るＳｅｔｕｐアルゴリズムを説明する。
（ステップＳ５１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λと、ＩＤのビット数である値ｎとの入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、ｄ＝２ｎとを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）を実行して、数１２９に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｍｓｋＩＰＧとのマスター鍵ペアを生成する。
【数１２９】
0006625283.tif 000030
【００７７】
（ステップＳ５２：秘密情報生成処理）
マスター鍵生成部１４は、一様乱数である秘密情報ｓ０を生成する。
マスター鍵生成部１４は、数１３０に示すように、群ＧＴの要素ｇＴに秘密情報ｓ０を設定して要素ｈＴを生成する。
【数１３０】
0006625283.tif 000031
【００７８】
（ステップＳ５３：鍵生成乱数生成処理）
マスター鍵生成部１４は、ｊ＝１，．．．，ｎの各整数ｊと、ι＝０，１の各整数ιとについて、一様乱数である鍵生成乱数τｊ，ιを生成する。
マスター鍵生成部１４は、ｊ＝１，．．．，ｎの各整数ｊと、ι＝０，１の各整数ιとについて、数１３１に示すように、群Ｇ＾ｊ，ιの要素ｇ＾ｊ，ιに、鍵生成乱数τｊ，ιを設定して要素ｈ＾ｊ，ιを生成する。
【数１３１】
0006625283.tif 000032
また、マスター鍵生成部１４は、ｊ＝１，．．．，ｎの各整数ｊと、ι＝０，１の各整数ιとについて、数１３２に示すように、群Ｇｊ，ιの要素ｇｊ，ιに、鍵生成乱数τｊ，ιの逆数１／τｊ，ιを設定して要素ｈｊ，ιを生成する。
【数１３２】
0006625283.tif 000033
【００７９】
（ステップＳ５４：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ５１で生成された公開パラメータｐｋＩＰＧと、ステップＳ５２で生成された要素ｈＴと、ステップＳ５３で生成された要素ｈ＾ｊ，ιとを用いて、公開パラメータｐｋ：＝（（Ｇｊ，ι，Ｇ＾ｊ，ι，ｈ＾ｊ，ι，ｅｊ，ι）ｊ∈［ｎ］，ι∈［０，１］，ＧＴ，ｈＴ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ５２で生成された秘密情報ｓ０と、ステップＳ５３で生成された要素ｈｊ，ιとを用いて、マスター秘密鍵ｍｓｋ：＝（ｓ０，（ｈｊ，ι）ｊ∈［ｎ］，ι∈［０，１］）を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｍｓｋを記憶装置１２に書き込む。
【００８０】
つまり、マスター鍵生成部１４は、数１３３に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１３３】
0006625283.tif 000034
【００８１】
図１９及び図２２を参照して、実施の形態２に係るＫｅｙＧｅｎアルゴリズムを説明する。
（ステップＳ６１：ＩＤ受付処理）
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋＩＤを使用するユーザの識別子ＩＤの入力を受け付ける。識別子ＩＤは、例えば、鍵生成装置１０の使用者によって入力装置を介して入力される。
上述した通り、識別子ＩＤ：＝（ＩＤｊ）ｊ＝１，．．．，ｎである。また、各ＩＤｊは、０又は１である。
【００８２】
（ステップＳ６２：ＩＤ群割当処理）
ＩＤ群割当部１７は、ｊ＝１，．．．，ｎの各整数ｊについてのＩＤｊを、群Ｇｔである群Ｇｊ，ιのうちの異なる群に割り当てる。具体的には、ＩＤ群割当部１７は、ｊ＝１，．．．，ｎの各整数ｊについてのＩＤｊを、群Ｇｊ，ＩＤｊに割り当てる。そして、ＩＤ群割当部１７は、ｊ＝１，．．．，ｎの各整数ｊについての群Ｇｊ，ＩＤｊの直積をＩＤ群ＧＩＤとする。つまり、ＩＤ群割当部１７は、数１３４に示すように、ＩＤ群ＧＩＤを生成する。
【数１３４】
0006625283.tif 000035
ＩＤ群割当部１７は、マスター秘密鍵ｍｓｋに含まれる要素ｈｊ，ιのうち、ＩＤ群ＧＩＤに含まれる要素ｈｊ，ιの集合を、要素ｈＩＤとして生成する。具体的には、ＩＤ群割当部１７は、数１３５に示すように、要素ｈＩＤを生成する。
【数１３５】
0006625283.tif 000036
【００８３】
（ステップＳ６３：分散情報生成処理）
復号鍵生成部１５は、数１３６に示すように、分散情報ｓ→をランダムに生成する。分散情報ｓ→は、秘密情報ｓ０を分散させた情報である。
【数１３６】
0006625283.tif 000037
【００８４】
（ステップＳ６４：鍵要素生成処理）
復号鍵生成部１５は、数１３７に示すように、ステップＳ６２で生成された要素ｈＩＤに、ステップＳ６３で生成された分散情報ｓ→を設定して、鍵要素ｋを生成する。
【数１３７】
0006625283.tif 000038
【００８５】
（ステップＳ６５：鍵出力処理）
鍵出力部１６は、ステップＳ６１で受け付けられた識別子ＩＤと、ステップＳ６４で生成された鍵要素ｋとを含む復号鍵ｓｋＩＤを、入出力インタフェース１３を介して復号装置３０に出力する。
【００８６】
つまり、復号鍵生成部１５は、数１３８に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＩＤを生成する。
【数１３８】
0006625283.tif 000039
【００８７】
図２０及び図２３を参照して、実施の形態２に係るＥｎｃアルゴリズムを説明する。
（ステップＳ７１：取得処理）
取得部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋを取得する。また、取得部２４は、暗号化対象のメッセージｍと、復号条件となる識別子ＩＤ’との入力を受け付ける。メッセージｍと識別子ＩＤ’とは、例えば、暗号化装置２０の使用者によって入力装置を介して入力される。
上述した通り、識別子ＩＤ’：＝（ＩＤ’ｊ）ｊ＝１，．．．，ｎである。また、各ＩＤ’ｊは、０又は１である。
【００８８】
（ステップＳ７２：ＩＤ群割当処理）
ＩＤ群割当部２７は、ｊ＝１，．．．，ｎの各整数ｊについてのＩＤ’ｊを、群Ｇ＾ｔである群Ｇ＾ｊ，ιのうちの異なる群に割り当てる。具体的には、ＩＤ群割当部１７は、ｊ＝１，．．．，ｎの各整数ｊについてのＩＤ’ｊを、群Ｇ＾ｊ，ＩＤ’ｊに割り当てる。そして、ＩＤ群割当部１７は、ｊ＝１，．．．，ｎの各整数ｊについての群Ｇ＾ｊ，ＩＤ’ｊの直積をＩＤ群Ｇ＾ＩＤとする。つまり、ＩＤ群割当部１７は、数１３９に示すように、ＩＤ群Ｇ＾ＩＤを生成する。
【数１３９】
0006625283.tif 000040
ＩＤ群割当部１７は、公開パラメータｐｋに含まれる要素ｈ＾ｊ，ιのうち、ＩＤ群Ｇ＾ＩＤに含まれる要素ｈ＾ｊ，ιの集合を、要素ｈ＾ＩＤとして生成する。具体的には、ＩＤ群割当部１７は、数１４０に示すように、要素ｈ＾ＩＤを生成する。
【数１４０】
0006625283.tif 000041
【００８９】
（ステップＳ７３：暗号文生成処理）
暗号文生成部２５は、ステップＳ７１で取得された公開パラメータｐｋと、ステップＳ７２で生成された要素ｈ＾ＩＤとを用いて、暗号文ｃｔＩＤ’の要素を生成する。暗号文生成部２５は、群ＧＴの要素Ｘと群Ｇ＾ｔの要素Ｙ＾との生成要素を用いて暗号文ｃｔＩＤ’の要素を生成する。ここで、要素Ｘは、公開パラメータｐｋに含まれる要素ｈＴのことであり、要素Ｙ＾は、ステップＳ７２で生成された要素ｈ＾ＩＤのことである。
暗号文生成処理は、ステップＳ７３１からステップＳ７３３の処理を含む。
【００９０】
（ステップＳ７３１：変換情報生成処理）
変換情報生成部２５１は、一様乱数である暗号化乱数ζを生成する。
変換情報生成部２５１は、要素ｈＴと、暗号化乱数ζとを用いて、数１４１に示すように、変換情報ｚを生成する。
【数１４１】
0006625283.tif 000042
【００９１】
（ステップＳ７３２：第１暗号要素生成処理）
第１暗号要素生成部２５２は、数１４２に示すように、ステップＳ７３１で生成された変換情報ｚに対して、メッセージｍを設定して暗号文ｃｔＩＤ’の要素である暗号要素ｃＴを生成する。
【数１４２】
0006625283.tif 000043
【００９２】
（ステップＳ７３３：第２暗号要素生成処理）
第２暗号要素生成部２５３は、数１４３に示すように、要素Ｙ＾である要素ｈ＾ＩＤに対して暗号化乱数ζを設定して暗号文ｃｔＩＤ’の要素である暗号要素ｃを生成する。
【数１４３】
0006625283.tif 000044
【００９３】
（ステップＳ７４：暗号文出力処理）
暗号文出力部２６は、ステップＳ７１で受け付けられた識別子ＩＤ’と、ステップＳ７３で生成された暗号要素ｃＴ，ｃとを暗号要素とする暗号文ｃｔＩＤ’を、入出力インタフェース２３を介して復号装置３０に出力する。
【００９４】
つまり、暗号化装置２０は、数１４４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を生成する。
【数１４４】
0006625283.tif 000045
【００９５】
図５及び図１０を参照して、実施の形態２に係るＤｅｃアルゴリズムを説明する。
ステップＳ４１とステップＳ４２との処理と、ステップＳ４４とステップＳ４５との処理とは、実施の形態１と同じである。
但し、復号鍵ｓｋＩＤは、要素ｈＩＤに分散情報ｓ→が設定された鍵要素ｋを含む。ここで、要素ｈＩＤは、要素ｈｊ，ιを用いて生成される。要素ｈｊ，ιは、群Ｇｊ，ιの要素ｇｊ，ιに、鍵生成乱数τｊ，ιの逆数１／τｊ，ιを設定してされる。したがって、復号鍵ｓｋＩＤは、鍵生成乱数τｊ，ιで変換された群Ｇｔ（＝群Ｇｊ，ι）の要素である鍵要素ｋを含む。
また、暗号文ｃｔＩＤ’は、暗号要素ｃＴと、暗号要素ｃとが含まれる。暗号要素ｃＴは、群ＧＴの生成元ｈＴである要素Ｘに対して暗号化乱数ζが設定された変換情報ｚに、メッセージｍが設定されている。暗号要素ｃは、群Ｇ＾ｔの生成元ｇ＾ｊ，ιが鍵生成乱数τｊ，ιによって変換された要素Ｙ＾である要素ｈ＾ＩＤに対して暗号化乱数ζが設定されている。
【００９６】
（ステップＳ４３：復号処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＩＤにより、暗号文ｃｔＩＤ’を復号して、メッセージｍ’を生成する。
復号処理は、ステップＳ４３１とステップＳ４３２との処理を含む。
【００９７】
（ステップＳ４３１：変換情報生成処理）
変換情報生成部３５１は、復号鍵ｓｋＩＤに含まれる要素ｋと、暗号文ｃｔＩＤ’に含まれる暗号要素ｃとを用いて、数１４５に示すように、変換情報ｚ’を生成する。
【数１４５】
0006625283.tif 000046
ここで、数１４６であるため、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤが復号可能であれば、変換情報ｚ’と変換情報ｚとは同一になる。
【数１４６】
0006625283.tif 000047
【００９８】
（ステップＳ４３２：メッセージ生成処理）
メッセージ生成部３５２は、ステップＳ４３１で生成された変換情報ｚ’と、暗号文ｃｔＩＤ’に含まれる暗号要素ｃＴとを用いて、数１４７に示すように、メッセージｍ’を生成する。
【数１４７】
0006625283.tif 000048
【００９９】
つまり、復号装置３０は、数１４８に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数１４８】
0006625283.tif 000049
【０１００】
＊＊＊実施の形態２の効果＊＊＊
以上のように、実施の形態２に係る暗号システム１は、実施の形態１に係る暗号システム１と同様に、ＩＰＧを用いてＩＢＥ方式を実現する。そのため、同種写像問題困難性から安全性を示すことを可能とすることができる。
また、実施の形態２に係る暗号システム１は、鍵生成乱数τｊ，ιによって変換された生成要素である要素Ｙ＾を用いて暗号文ｃｔＩＤ’を生成する。これにより、ペアリング問題困難性から安全性を示すことを可能とすることができる。
【０１０１】
実施の形態２に係る暗号システム１は、ＩＤ群ＧＩＤ，Ｇ＾ＩＤを用いる。これにより、識別子ＩＤと識別子ＩＤ’とが一致しない場合には、群ＧＩＤと群Ｇ＾ＩＤとが一致しない。そのため、復号ができない状態とすることができる。
【０１０２】
実施の形態２に係る暗号システム１では、ＫｅｙＧｅｎアルゴリズムと、Ｅｎｃアルゴリズムと、Ｄｅｃアルゴリズムとでは、同種写像φを用いていない。その結果、ハッシュ関数Ｈを用いる必要がない。
なお、ＫｅｙＧｅｎアルゴリズムと、Ｅｎｃアルゴリズムと、Ｄｅｃアルゴリズムとでは、同種写像φを用いていないため、図２１のステップＳ５１でＧｅｎＩＰＧアルゴリズムは、同種写像φｔを出力しなくてもよい。
【０１０３】
実施の形態３．
実施の形態３では、小さい属性集合のＡＢＥ方式を説明する。
実施の形態３では、実施の形態２と同一の点については説明を省略し、異なる点を説明する。
【０１０４】
実施の形態３では、復号鍵に復号条件であるポリシーが設定される鍵ポリシー型のＡＢＥ（以下、ＫＰ−ＡＢＥ）方式について説明する。なお、ＫＰ−ＡＢＥ方式を、暗号文にポリシーが設定される暗号文ポリシー型のＡＢＥ（以下、ＣＰ−ＡＢＥ）方式にＮａｏｒ変換といった方法により変換することも可能である。
【０１０５】
＊＊＊構成の説明＊＊＊
ＫＰ−ＡＢＥ方式は、Ｓｅｔｕｐアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｅｎｃアルゴリズムと、Ｄｅｃアルゴリズムとを備える。
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開パラメータｐｋと、マスター秘密鍵ｍｓｋとを出力する。
ＫｅｙＧｅｎアルゴリズムは、公開パラメータｐｋと、マスター秘密鍵ｍｓｋと、アクセスストラクチャＳ：＝（Ｍ，ρ）とを入力として、入力タグｔａｇ及びアクセスストラクチャＳに対応した復号鍵ｓｋＳを出力する。
Ｅｎｃアルゴリズムは、公開パラメータｐｋと、メッセージ空間ｍｓｇにおけるメッセージｍと、属性集合Γを入力として、暗号文ｃｔΓを出力する。
Ｄｅｃアルゴリズムは、公開パラメータｐｋと、アクセスストラクチャＳに対応した復号鍵ｓｋＳと、属性集合Γの下で暗号化された暗号文ｃｔΓとを入力として、メッセージｍ’∈ｍｓｇ、又は、復号に失敗したことを示す識別情報⊥を出力する。
【０１０６】
図２４を参照して、実施の形態３に係る暗号システム１の構成を説明する。
暗号システム１は、鍵生成装置１０と、暗号化装置２０と、復号装置３０とを備える。鍵生成装置１０と、暗号化装置２０と、復号装置３０とは、伝送路を介して接続されている。伝送路は、具体例としては、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、又は、インターネットである。鍵生成装置１０と、暗号化装置２０と、復号装置３０とは、伝送路を介して通信可能である。
【０１０７】
鍵生成装置１０は、セキュリティパラメータ１λを入力として、Ｓｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋと、マスター秘密鍵ｍｓｋとを生成する。また、鍵生成装置１０は、公開パラメータｐｋと、マスター秘密鍵ｍｓｋと、アクセスストラクチャＳ：＝（Ｍ，ρ）とを入力として、ＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成する。
鍵生成装置１０は、公開パラメータｐｋを公開し、復号鍵ｓｋＳをアクセスストラクチャＳに対応する復号装置３０に出力する。鍵生成装置１０は、マスター秘密鍵ｍｓｋを保管する。
【０１０８】
暗号化装置２０は、公開パラメータｐｋと、メッセージｍと、属性集合Γとを入力として、Ｅｎｃアルゴリズムを実行して、暗号文ｃｔΓを生成する。暗号化装置２０は、暗号文ｃｔΓを復号装置３０に出力する。
【０１０９】
復号装置３０は、公開パラメータｐｋと、復号鍵ｓｋＳと、暗号文ｃｔΓとを入力として、Ｄｅｃアルゴリズムを実行して、メッセージｍ’、又は、復号に失敗したことを示す識別情報⊥を生成する。
【０１１０】
＊＊＊概念の説明＊＊＊
実施の形態２に係るＡＢＥ方式で用いられる概念について説明する。
スパンプログラムについて説明する。スパンプログラムは既存の概念であるため、ここでは以下の説明で必要な範囲だけ簡単に説明する。
【０１１１】
体Ｆｑ上のスパンプログラムは、ラベル付けされた行列Ｓ：＝（Ｍ，ρ）である。ここで、行列Ｍは、体Ｆｑ上の（Ｌ行×ｒ列）の行列である。ラベルρは、｛（ｔ，ｖ），（ｔ’，ｖ’），．．．｝から属性に応じて行列Ｍの行に対して付されたラベルである。なお、各行が１つの属性にラベル付けされる。つまり、ρ：｛１，．．．，Ｌ｝→｛（ｔ，ｖ），（ｔ’，ｖ’），．．．｝である。
スパンプログラムは、以下の基準に従い、入力を受理又は拒絶する。Γを属性集合とする。つまり、Γ：＝｛（ｔｊ，ｘｊ）｝１≦ｊ≦ｄ’（ｘｊ∈Ｕｔｊ）である。１→∈ｓｐａｎ＜（Ｍｉ）ρ（ｉ）∈Γ＞の場合に限り、スパンプログラムＳは属性集合Γを受理する。スパンプログラムＳが属性集合Γを受理することを、Ｒ（Ｓ，Γ）＝１と表す。つまり、行列Ｍの行（Ｍｉ）ρ（ｉ）∈Γの線形結合によって全ての要素が１のベクトルが得られる場合に限り、スパンプログラムＳは属性集合Γを受理する。スパンプログラムＳをアクセスストラクチャと呼ぶ。
【０１１２】
＊＊＊動作の説明＊＊＊
図５と、図１０と、図１９から図２３とを参照して、実施の形態３に係る暗号システム１の動作を説明する。実施の形態３についても、実施の形態２と同様に各動作は、各方法及び各プログラムの処理に相当する。
【０１１３】
図１９及び図２１を参照して、実施の形態３に係るＳｅｔｕｐアルゴリズムを説明する。
（ステップＳ５１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λと、属性の最大数である値ｄとの入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、ｄとを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ）を実行して、数１４９に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｍｓｋＩＰＧとのマスター鍵ペアを生成する。
【数１４９】
0006625283.tif 000050
【０１１４】
（ステップＳ５２：秘密情報生成処理）
マスター鍵生成部１４は、一様乱数である秘密情報ｓ０を生成する。
マスター鍵生成部１４は、数１５０に示すように、群ＧＴの要素ｇＴに秘密情報ｓ０を設定して要素ｈＴを生成する。
【数１５０】
0006625283.tif 000051
【０１１５】
（ステップＳ５３：鍵生成乱数生成処理）
マスター鍵生成部１４は、ｔ∈［ｄ］の各整数ｔについて、一様乱数である鍵生成乱数τｔを生成する。
マスター鍵生成部１４は、ｔ∈［ｄ］の各整数ｔについて、数１５１に示すように、群Ｇ＾ｔの要素ｇ＾ｔに、鍵生成乱数τｔを設定して要素ｈ＾ｔを生成する。
【数１５１】
0006625283.tif 000052
また、マスター鍵生成部１４は、ｔ∈［ｄ］の各整数ｔについて、数１５２に示すように、群Ｇｔの要素ｇｔに、鍵生成乱数τｔの逆数１／τｔを設定して要素ｈｔを生成する。
【数１５２】
0006625283.tif 000053
【０１１６】
（ステップＳ５４：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ５１で生成された公開パラメータｐｋＩＰＧと、ステップＳ５２で生成された要素ｈＴと、ステップＳ５３で生成された要素ｈ＾ｔとを用いて、公開パラメータｐｋ：＝（（Ｇｔ，Ｇ＾ｔ，ｈ＾ｔ，ｅｔ）ｔ∈［ｄ］，ＧＴ，ｈＴ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ５２で生成された秘密情報ｓ０と、ステップＳ５３で生成された要素ｈｔとを用いて、マスター秘密鍵ｍｓｋ：＝（ｓ０，（ｈｔ）ｔ∈［ｄ］）を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｍｓｋを記憶装置１２に書き込む。
【０１１７】
つまり、マスター鍵生成部１４は、数１５３に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１５３】
0006625283.tif 000054
【０１１８】
図１９及び図２２を参照して、実施の形態３に係るＫｅｙＧｅｎアルゴリズムを説明する。
（ステップＳ６１：ＩＤ受付処理）
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋＳを使用するユーザのアクセスストラクチャＳ：＝（Ｍ，ρ）の入力を受け付ける。アクセスストラクチャＳは、復号鍵ｓｋＳで復号可能な範囲を示す情報である。
【０１１９】
（ステップＳ６２：ＩＤ群割当処理）
ＩＤ群割当部１７は、ｉ∈［Ｌ］の各整数ｉについて、ｔ＝ρ（ｉ）である群Ｇｔの直積をＩＤ群ＧＩＤとする。ＩＤ群割当部１７は、マスター秘密鍵ｍｓｋに含まれる要素ｈｔのうち、ＩＤ群ＧＩＤに含まれる要素ｈｔの集合を、要素ｈＩＤとして生成する。具体的には、ＩＤ群割当部１７は、数１５４に示すように、要素ｈＩＤを生成する。
【数１５４】
0006625283.tif 000055
【０１２０】
（ステップＳ６３：分散情報生成処理）
復号鍵生成部１５は、数１５５に示すように、分散情報ｓ→を生成する。
【数１５５】
0006625283.tif 000056
【０１２１】
（ステップＳ６４：鍵要素生成処理）
復号鍵生成部１５は、数１５６に示すように、ステップＳ６２で生成された要素ｈＩＤに、ステップＳ６３で生成された分散情報ｓ→を設定して、鍵要素ｋ：＝｛ｋｉ｝を生成する。
【数１５６】
0006625283.tif 000057
【０１２２】
（ステップＳ６５：鍵出力処理）
鍵出力部１６は、ステップＳ６１で受け付けられたアクセスストラクチャＳと、ステップＳ６４で生成された鍵要素ｋ：＝｛ｋｉ｝とを含む復号鍵ｓｋＳを、入出力インタフェース１３を介して復号装置３０に出力する。
【０１２３】
つまり、復号鍵生成部１５は、数１５７に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成する。
【数１５７】
0006625283.tif 000058
【０１２４】
図２０及び図２３を参照して、実施の形態３に係るＥｎｃアルゴリズムを説明する。
ステップＳ７３の処理は、実施の形態２と同じである。
（ステップＳ７１：取得処理）
取得部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋを取得する。また、取得部２４は、暗号化対象のメッセージｍと、復号条件となる属性集合Γとの入力を受け付ける。
【０１２５】
（ステップＳ７２：ＩＤ群割当処理）
ＩＤ群割当部２７は、ｔ∈Γの各整数ｔについて、群Ｇ＾ｔの直積をＩＤ群Ｇ＾ＩＤとする。ＩＤ群割当部１７は、公開パラメータｐｋに含まれる要素ｈ＾ｔのうち、ＩＤ群Ｇ＾ＩＤに含まれる要素ｈ＾ｔの集合を、要素ｈ＾ＩＤとして生成する。具体的には、ＩＤ群割当部１７は、数１５８に示すように、要素ｈ＾ＩＤを生成する。
【数１５８】
0006625283.tif 000059
【０１２６】
（ステップＳ７４：暗号文出力処理）
暗号文出力部２６は、ステップＳ７１で受け付けられた属性集合Γと、ステップＳ７３で生成された暗号要素ｃＴ，ｃ：＝｛ｃｔ：＝ｈ＾ｔζ｝とを暗号要素とする暗号文ｃｔΓを、入出力インタフェース２３を介して復号装置３０に出力する。
【０１２７】
つまり、暗号化装置２０は、数１５９に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔΓを生成する。
【数１５９】
0006625283.tif 000060
【０１２８】
図５及び図１０を参照して、実施の形態３に係るＤｅｃアルゴリズムを説明する。
ステップＳ４４とステップＳ４５との処理は、実施の形態２と同じである。
【０１２９】
（ステップＳ４１：取得処理）
取得部３４は、入出力インタフェース３３を介して、鍵生成装置１０によって生成された公開パラメータｐｋ及び復号鍵ｓｋＳと、暗号化装置２０によって生成された暗号文ｃｔΓとを取得する。
【０１３０】
（ステップＳ４１１：復号鍵取得処理）
復号鍵取得部３４１は、入出力インタフェース３３を介して、鍵生成装置１０によって生成された公開パラメータｐｋ及び復号鍵ｓｋＳを取得する。ここで、復号鍵ｓｋＳは、要素ｈＩＤに分散情報ｓ→が設定された鍵要素ｋ：＝｛ｋｉ｝を含む。つまり、実施の形態２と同様に、復号鍵ｓｋＳは、鍵生成乱数τｔで変換された群Ｇｔの要素である鍵要素ｋを含む。
【０１３１】
（ステップＳ４１２：暗号文取得処理）
暗号文取得部３４２は、暗号化装置２０によって生成された暗号文ｃｔΓを取得する。ここで、暗号文ｃｔΓは、暗号要素ｃＴと、暗号要素ｃ：＝｛ｃｔ｝とが含まれる。暗号要素ｃＴは、群ＧＴの生成元ｈＴである要素Ｘに対して暗号化乱数ζが設定された変換情報ｚに、メッセージｍが設定されている。暗号要素ｃは、群Ｇ＾ｔの生成元ｇ＾ｔが鍵生成乱数τｔによって変換された要素Ｙ＾である要素ｈ＾ＩＤに対して暗号化乱数ζが設定されている。
【０１３２】
（ステップＳ４２：復号判定処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＳに含まれるアクセスストラクチャＳが、暗号文ｃｔΓに含まれる属性集合Γを受理するか否かを判定する。これにより、暗号文ｃｔΓを復号鍵ｓｋＳで復号可能かが判定される。
復号部３５は、受理すると判定された場合、つまり復号可能と判定された場合、処理をステップＳ４３に進め、そうでない場合、処理をステップＳ４５に進める。
【０１３３】
（ステップＳ４３：復号処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＳにより、暗号文ｃｔΓを復号して、メッセージｍ’を生成する。
復号処理は、ステップＳ４３１とステップＳ４３２との処理を含む。
【０１３４】
（ステップＳ４３１：変換情報生成処理）
変換情報生成部３５１は、数１６０に示す補完係数σｉを計算する。
【数１６０】
0006625283.tif 000061
変換情報生成部３５１は、補完係数σｉと、復号鍵ｓｋＳに含まれる要素ｋと、暗号文ｃｔΓに含まれる暗号要素ｃとを用いて、数１６１に示すように、変換情報ｚ’を生成する。
【数１６１】
0006625283.tif 000062
ここで、数１６２であるため、暗号文ｃｔΓを復号鍵ｓｋＳが復号可能であれば、変換情報ｚ’と変換情報ｚとは同一になる。
【数１６２】
0006625283.tif 000063
【０１３５】
（ステップＳ４３２：メッセージ生成処理）
メッセージ生成部３５２は、ステップＳ４３１で生成された変換情報ｚ’と、暗号文ｃｔΓに含まれる暗号要素ｃＴとを用いて、数１６３に示すように、メッセージｍ’を生成する。
【数１６３】
0006625283.tif 000064
【０１３６】
つまり、復号装置３０は、数１６４に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数１６４】
0006625283.tif 000065
【０１３７】
＊＊＊実施の形態３の効果＊＊＊
以上のように、実施の形態３に係る暗号システム１は、ＩＰＧを用いてＡＢＥ方式を実現する。そのため、同種写像問題困難性から安全性を示すことを可能とすることができる。
また、実施の形態３に係る暗号システム１は、鍵生成乱数τｔによって変換された生成要素である要素Ｙ＾を用いて暗号文ｃｔΓを生成する。これにより、ペアリング問題困難性から安全性を示すことを可能とすることができる。
【０１３８】
実施の形態４．
実施の形態４では、大きい属性集合のＡＢＥ方式を説明する。
実施の形態４では、実施の形態３と同一の点については説明を省略し、異なる点を説明する。
【０１３９】
実施の形態３では、属性集合Γには属性ｔが含まれた。実施の形態４では、属性集合Γには、属性のカテゴリｔと、カテゴリｔについての属性ｘｔ：＝（ｘｔ，ｊ）∈｛０，１｝ｎが含まれる。
なお、以下の説明において、ｘｔが下付きで示されている場合には、このｘｔはｘｔを意味し、ｖｉが下付きで示されている場合には、このｖｉはｖｉを意味する。
【０１４０】
＊＊＊動作の説明＊＊＊
図５と、図１０と、図１９から図２３とを参照して、実施の形態４に係る暗号システム１の動作を説明する。実施の形態４についても、実施の形態３と同様に各動作は、各方法及び各プログラムの処理に相当する。
【０１４１】
図１９及び図２１を参照して、実施の形態４に係るＳｅｔｕｐアルゴリズムを説明する。
（ステップＳ５１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λと、属性の最大数である値ｄと、各カテゴリｔについてのビット数を表す値ｎとの入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、ｄと、ｎとを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，ｄ，ｎ）を実行して、数１６５に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｍｓｋＩＰＧとのマスター鍵ペアを生成する。
【数１６５】
0006625283.tif 000066
【０１４２】
（ステップＳ５２：秘密情報生成処理）
マスター鍵生成部１４は、一様乱数である秘密情報ｓ０を生成する。
マスター鍵生成部１４は、数１６６に示すように、群ＧＴの要素ｇＴに秘密情報ｓ０を設定して要素ｈＴを生成する。
【数１６６】
0006625283.tif 000067
【０１４３】
（ステップＳ５３：鍵生成乱数生成処理）
マスター鍵生成部１４は、ｔ∈［ｄ］とｊ∈［ｎ］とι∈［０，１］との各整数ｔ，ｊ，ιについて、一様乱数である鍵生成乱数τｔ，ｊ，ιを生成する。
マスター鍵生成部１４は、ｔ∈［ｄ］とｊ∈［ｎ］とι∈［０，１］との各整数ｔ，ｊ，ιについて、数１６７に示すように、群Ｇ＾ｔ，ｊ，ιの要素ｇ＾ｔ，ｊ，ιに、鍵生成乱数τｔ，ｊ，ιを設定して要素ｈ＾ｔ，ｊ，ιを生成する。
【数１６７】
0006625283.tif 000068
また、マスター鍵生成部１４は、ｔ∈［ｄ］とｊ∈［ｎ］とι∈［０，１］との各整数ｔ，ｊ，ιについて、数１６８に示すように、群Ｇｔ，ｊ，ιの要素ｇｔ，ｊ，ιに、鍵生成乱数τｔ，ｊ，ιの逆数１／τｔ，ｊ，ιを設定して要素ｈｔ，ｊ，ιを生成する。
【数１６８】
0006625283.tif 000069
【０１４４】
（ステップＳ５４：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ５１で生成された公開パラメータｐｋＩＰＧと、ステップＳ５２で生成された要素ｈＴと、ステップＳ５３で生成された要素ｈ＾ｔ，ｊ，ιとを用いて、公開パラメータｐｋ：＝（（Ｇｔ，ｊ，ι，Ｇ＾ｔ，ｊ，ι，ｈ＾ｔ，ｊ，ι，ｅｔ，ｊ，ι）ｔ∈［ｄ］，ｊ∈［ｎ］，ι∈［０，１］，ＧＴ，ｈＴ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ５２で生成された秘密情報ｓ０と、ステップＳ５３で生成された要素ｈｔ，ｊ，ιとを用いて、マスター秘密鍵ｍｓｋ：＝（ｓ０，（ｈｔ，ｊ，ι）ｔ∈［ｄ］，ｊ∈［ｎ］，ι∈［０，１］）を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｍｓｋを記憶装置１２に書き込む。
【０１４５】
つまり、マスター鍵生成部１４は、数１６９に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１６９】
0006625283.tif 000070
【０１４６】
図１９及び図２２を参照して、実施の形態４に係るＫｅｙＧｅｎアルゴリズムを説明する。
ステップＳ６１の処理は、実施の形態３と同じである。
【０１４７】
（ステップＳ６２：ＩＤ群割当処理）
ＩＤ群割当部１７は、ｉ∈［Ｌ］の各整数ｉについて、ρ（ｉ）＝（ｔ，ｖｉ：＝（ｖｉ，ｊ）∈｛０，１｝ｎ）である場合に、ｊ＝１，．．．，ｎの各整数ｊについての群Ｇｔ，ｊ，ｖｉの直積をＩＤ群Ｇｔ，ｖｉとする。なお、ＩＤ群Ｇｔ，ｖｉは、ｔ番目の基底群である。つまり、ＩＤ群割当部１７は、数１７０に示すように、ＩＤ群Ｇｔ，ｖｉを生成する。
【数１７０】
0006625283.tif 000071
ＩＤ群割当部１７は、マスター秘密鍵ｍｓｋに含まれる要素ｈｔ，ｊ，ιのうち、ＩＤ群Ｇｔ，ｖｉに含まれる要素ｈｔ，ｊ，ιの集合を、要素ｈｔ，ｖｉとして生成する。具体的には、ＩＤ群割当部１７は、数１７１に示すように、要素ｈｔ，ｖｉを生成する。
【数１７１】
0006625283.tif 000072
【０１４８】
（ステップＳ６３：分散情報生成処理）
復号鍵生成部１５は、ｉ∈［Ｌ］の各整数ｉについて、数１７２に示すように、分散情報ｓ→ｉを生成する。
【数１７２】
0006625283.tif 000073
【０１４９】
（ステップＳ６４：鍵要素生成処理）
復号鍵生成部１５は、数１７３に示すように、ステップＳ６２で生成された要素ｈｔ，ｖｉに、ステップＳ６３で生成された分散情報ｓ→ｉを設定して、鍵要素ｋｉを生成する。
【数１７３】
0006625283.tif 000074
【０１５０】
（ステップＳ６５：鍵出力処理）
鍵出力部１６は、ステップＳ６１で受け付けられたアクセスストラクチャＳと、ステップＳ６４で生成された鍵要素ｋ：＝｛ｋｉ｝とを含む復号鍵ｓｋＳを、入出力インタフェース１３を介して復号装置３０に出力する。
【０１５１】
つまり、復号鍵生成部１５は、数１７４に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成する。
【数１７４】
0006625283.tif 000075
【０１５２】
図２０及び図２３を参照して、実施の形態４に係るＥｎｃアルゴリズムを説明する。
ステップＳ７３とステップＳ７４との処理は、実施の形態２と同じである。
（ステップＳ７１：取得処理）
取得部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋを取得する。また、取得部２４は、暗号化対象のメッセージｍと、復号条件となる属性集合Γとの入力を受け付ける。
【０１５３】
（ステップＳ７２：ＩＤ群割当処理）
ＩＤ群割当部２７は、（ｔ，ｘｔ：＝（ｘｔ，ｊ）∈｛０，１｝ｎ）∈Γの各整数ｔについて、ｊ＝１，．．．，ｎの各整数ｊの群Ｇ＾ｔ，ｊ，ｘｔの直積をＩＤ群Ｇ＾ｔ，ｘｔとする。つまり、ＩＤ群割当部２７は、数１７５に示すように、ＩＤ群Ｇ＾ｔ，ｘｔを生成する。
【数１７５】
0006625283.tif 000076
ＩＤ群割当部１７は、公開パラメータｐｋに含まれる要素ｈ＾ｔ，ｊ，ｘｔのうち、ＩＤ群Ｇ＾ｔ，ｘｔに含まれる要素ｈ＾ｔ，ｊ，ｘｔの集合を、要素ｈ＾ｔ，ｘｔとして生成する。具体的には、ＩＤ群割当部１７は、数１７６に示すように、要素ｈ＾ｔ，ｘｔを生成する。
【数１７６】
0006625283.tif 000077
【０１５４】
（ステップＳ７３：暗号文生成処理）
暗号文生成部２５は、ステップＳ７１で取得された公開パラメータｐｋと、ステップＳ７２で生成された要素ｈ＾ｔ，ｘｔとを用いて、暗号文ｃｔΓの要素を生成する。暗号文生成部２５は、群ＧＴの要素Ｘと群Ｇ＾ｔ，ｘｔの要素Ｙ＾との生成要素を用いて暗号文ｃｔΓの要素を生成する。ここで、要素Ｘは、公開パラメータｐｋに含まれる要素ｈＴのことであり、要素Ｙ＾は、ステップＳ７２で生成された要素ｈ＾ｔ，ｘｔのことである。
暗号文生成処理は、ステップＳ７３１からステップＳ７３３の処理を含む。
【０１５５】
（ステップＳ７３１：変換情報生成処理）
変換情報生成部２５１は、一様乱数である暗号化乱数ζを生成する。
変換情報生成部２５１は、要素ｈＴと、暗号化乱数ζとを用いて、数１７７に示すように、変換情報ｚを生成する。
【数１７７】
0006625283.tif 000078
【０１５６】
（ステップＳ７３２：第１暗号要素生成処理）
第１暗号要素生成部２５２は、数１７８に示すように、ステップＳ７３１で生成された変換情報ｚに対して、メッセージｍを設定して暗号文ｃｔΓの要素である暗号要素ｃＴを生成する。
【数１７８】
0006625283.tif 000079
【０１５７】
（ステップＳ７３３：第２暗号要素生成処理）
第２暗号要素生成部２５３は、数１７９に示すように、（ｔ，ｘｔ：＝（ｘｔ，ｊ）∈｛０，１｝ｎ）∈Γの各整数ｔについて、要素Ｙ＾である要素ｈ＾ｔ，ｘｔに対して暗号化乱数ζを設定して暗号文ｃｔΓの要素である暗号要素ｃｔを生成する。
【数１７９】
0006625283.tif 000080
【０１５８】
（ステップＳ７４：暗号文出力処理）
暗号文出力部２６は、ステップＳ７１で受け付けられた属性集合Γと、ステップＳ７３で生成された暗号要素ｃＴ，ｃ：＝｛ｃｔ｝ｔ∈Γとを暗号要素とする暗号文ｃｔΓを、入出力インタフェース２３を介して復号装置３０に出力する。
【０１５９】
つまり、暗号化装置２０は、数１８０に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔΓを生成する。
【数１８０】
0006625283.tif 000081
【０１６０】
図５及び図１０を参照して、実施の形態４に係るＤｅｃアルゴリズムを説明する。
ステップＳ４１とステップＳ４２との処理と、ステップＳ４４とステップＳ４５との処理とは、実施の形態３と同じである。
但し、復号鍵ｓｋＳは、要素ｈｔ，ｖｉに分散情報ｓ→が設定された鍵要素ｋを含む。つまり、実施の形態３と同様に、復号鍵ｓｋＳは、鍵生成乱数τｔ，ｊ，ιで変換された群Ｇｔ，ｖｉの要素である鍵要素ｋ：＝｛ｋｉ｝を含む。
また、暗号文ｃｔΓは、暗号要素ｃＴと、暗号要素ｃとが含まれる。暗号要素ｃＴは、群ＧＴの生成元ｈＴである要素Ｘに対して暗号化乱数ζが設定された変換情報ｚに、メッセージｍが設定されている。暗号要素ｃは、群Ｇ＾ｔ，ｘｔの生成元ｇ＾ｔ，ｊ，ιが鍵生成乱数τｔ，ｊ，ιによって変換された要素Ｙ＾である要素ｈ＾ｔ，ｘｔに対して暗号化乱数ζが設定されている。
【０１６１】
（ステップＳ４３：復号処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＳにより、暗号文ｃｔΓを復号して、メッセージｍ’を生成する。
復号処理は、ステップＳ４３１とステップＳ４３２との処理を含む。
【０１６２】
（ステップＳ４３１：変換情報生成処理）
変換情報生成部３５１は、数１８１に示す補完係数σｉを計算する。
【数１８１】
0006625283.tif 000082
変換情報生成部３５１は、補完係数σｉと、復号鍵ｓｋＳに含まれる要素ｋ：＝｛ｋｉ｝と、暗号文ｃｔΓに含まれる暗号要素ｃ：＝｛ｃｔ｝とを用いて、数１８２に示すように、変換情報ｚ’を生成する。
【数１８２】
0006625283.tif 000083
ここで、数１８３であるため、暗号文ｃｔΓを復号鍵ｓｋＳが復号可能であれば、変換情報ｚ’と変換情報ｚとは同一になる。
【数１８３】
0006625283.tif 000084
【０１６３】
（ステップＳ４３２：メッセージ生成処理）
メッセージ生成部３５２は、ステップＳ４３１で生成された変換情報ｚ’と、暗号文ｃｔΓに含まれる暗号要素ｃＴとを用いて、数１８４に示すように、メッセージｍ’を生成する。
【数１８４】
0006625283.tif 000085
【０１６４】
つまり、復号装置３０は、数１８５に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数１８５】
0006625283.tif 000086
【０１６５】
＊＊＊実施の形態４の効果＊＊＊
以上のように、実施の形態４に係る暗号システム１は、ＩＰＧを用いてＡＢＥ方式を実現する。そのため、同種写像問題困難性から安全性を示すことを可能とすることができる。
また、実施の形態４に係る暗号システム１は、鍵生成乱数τｔ，ｊ，ιによって変換された生成要素である要素Ｙ＾を用いて暗号文ｃｔΓを生成する。これにより、ペアリング問題困難性から安全性を示すことを可能とすることができる。
【０１６６】
実施の形態５．
実施の形態５では、実施の形態２で説明したＩＢＥ方式に基づく、階層的なＩＢＥ（Ｈｉｅｒａｒｃｈｉｃａｌ  ＩＢＥ，以下ＨＩＢＥ）を説明する。
実施の形態５では、実施の形態２と同一の点については説明を省略し、異なる点を説明する。
【０１６７】
実施の形態５では、まず１ビットＨＩＢＥを説明し、次に１ビットＨＩＢＥを応用したｎ（ｎ≧１）ビットＨＩＢＥを説明する。
【０１６８】
＊＊＊構成の説明＊＊＊
ＨＩＢＥ方式は、Ｓｅｔｕｐアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｅｎｃアルゴリズムと、Ｄｅｃアルゴリズム、Ｄｅｌｅｇａｔｅアルゴリズムとを備える。
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータ１λを入力として、公開パラメータｐｋと、マスター秘密鍵ｍｓｋとを出力する。
ＫｅｙＧｅｎアルゴリズムは、公開パラメータｐｋと、マスター秘密鍵ｍｓｋと、識別子ＩＤとを入力として、識別子ＩＤに対応した復号鍵ｓｋＩＤを出力する。
Ｅｎｃアルゴリズムは、公開パラメータｐｋと、メッセージ空間ｍｓｇにおけるメッセージｍと、識別子ＩＤ’とを入力として、暗号文ｃｔＩＤ’を出力する。
Ｄｅｃアルゴリズムは、公開パラメータｐｋと、識別子ＩＤに対応した復号鍵ｓｋＩＤと、識別子ＩＤ’の下で暗号化された暗号文ｃｔＩＤ’とを入力として、メッセージｍ’∈ｍｓｇ、又は、復号に失敗したことを示す識別情報⊥を出力する。
Ｄｅｌｅｇａｔｅアルゴリズムは、公開パラメータｐｋと、長さＬの階層的な識別子ＩＤに対応した秘密鍵ｓｋＩＤと、Ｌ＋１番目のＩＤＬ＋１とを入力として、長さＬ＋１の階層的な識別子ＩＤ’：＝（ＩＤ，ＩＤＬ＋１）に対応した秘密鍵ｓｋＩＤ’、又は、鍵生成に失敗したことを示す識別情報⊥を出力する。
【０１６９】
図２５を参照して、実施の形態５に係る暗号システム１の構成を説明する。
暗号システム１は、鍵生成装置１０と、暗号化装置２０と、復号装置３０と、鍵委譲装置４０とを備える。鍵生成装置１０と、暗号化装置２０と、復号装置３０と、鍵委譲装置４０とは、伝送路を介して接続されている。
【０１７０】
鍵委譲装置４０は、公開パラメータｐｋと、長さＬの階層的な識別子ＩＤに対応した秘密鍵ｓｋＩＤと、Ｌ＋１番目のＩＤＬ＋１とを入力として、Ｄｅｌｅｇａｔｅアルゴリズムを実行して、長さＬ＋１の階層的な識別子ＩＤ’：＝（ＩＤ，ＩＤＬ＋１）に対応した秘密鍵ｓｋＩＤ’、又は、鍵生成に失敗したことを示す識別情報⊥を生成する。
【０１７１】
図２６を参照して、実施の形態５に係る鍵委譲装置４０の構成を説明する。
鍵委譲装置４０は、プロセッサ４１と、記憶装置４２と、入出力インタフェース４３とのハードウェアを備える。プロセッサ４１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【０１７２】
鍵委譲装置４０は、機能構成要素として、取得部４４と、ＩＤ群割当部４５と、下位鍵生成部４６と、下位鍵出力部４７とを備える。取得部４４と、ＩＤ群割当部４５と、下位鍵生成部４６と、下位鍵出力部４７との各部の機能はソフトウェアにより実現される。
記憶装置４２には、鍵委譲装置４０の各部の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ４１により読み込まれ、プロセッサ４１によって実行される。これにより、鍵委譲装置４０の各部の機能が実現される。
【０１７３】
＊＊＊動作の説明＊＊＊
図１９から図２３と、図２６と、図２７とを参照して、実施の形態５に係る暗号システム１の動作を説明する。実施の形態５についても、実施の形態２と同様に各動作は、各方法及び各プログラムの処理に相当する。また、実施の形態５に係る鍵委譲装置４０の動作は、実施の形態５に係る鍵委譲方法と、実施の形態５に係る鍵委譲プログラムの処理とに対応する。
なお、Ｄｅｃアルゴリズムは、実施の形態２と同じであるため、説明を省略する。
【０１７４】
まず、１ビットＨＩＢＥを説明する。
なお、以下の説明でＩＤｔが下付きで示されている場合には、このＩＤｔはＩＤｔを意味し、ＩＤ’ｔが下付きで示されている場合には、このＩＤ’ｔはＩＤ’ｔを意味する。
【０１７５】
図１９及び図２１を参照して、実施の形態５に係るＳｅｔｕｐアルゴリズムを説明する。
（ステップＳ５１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λと、階層数である値ｄ≧２との入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、２ｄとを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，２ｄ）を実行して、数１８６に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｍｓｋＩＰＧとのマスター鍵ペアを生成する。
【数１８６】
0006625283.tif 000087
【０１７６】
（ステップＳ５２：秘密情報生成処理）
マスター鍵生成部１４は、一様乱数である秘密情報ｓ０を生成する。
マスター鍵生成部１４は、数１８７に示すように、群ＧＴの要素ｇＴに秘密情報ｓ０を設定して要素ｈＴを生成する。
【数１８７】
0006625283.tif 000088
【０１７７】
（ステップＳ５３：鍵生成乱数生成処理）
マスター鍵生成部１４は、ｔ∈［ｄ］とι∈［０，１］の各整数ｔ，ιについて、一様乱数である鍵生成乱数τｔ，ιを生成する。
マスター鍵生成部１４は、ｔ∈［ｄ］とι∈［０，１］の各整数ｔ，ιについて、数１８８に示すように、群Ｇ＾ｔ，ιの要素ｇ＾ｔ，ιに、鍵生成乱数τｔ，ιを設定して要素ｈ＾ｔ，ιを生成する。
【数１８８】
0006625283.tif 000089
また、マスター鍵生成部１４は、ｔ∈［ｄ］とι∈［０，１］の各整数ｔ，ιについて、数１８９に示すように、群Ｇｔ，ιの要素ｇｔ，ιに、鍵生成乱数τｔ，ιを設定して要素ｈｔ，ιを生成する。
【数１８９】
0006625283.tif 000090
【０１７８】
（ステップＳ５４：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ５１で生成された公開パラメータｐｋＩＰＧと、ステップＳ５２で生成された要素ｈＴと、ステップＳ５３で生成された要素ｈ＾ｔ，ιと要素ｈｔ，ιとを用いて、公開パラメータｐｋ：＝（（Ｇｔ，ι，Ｇ＾ｔ，ι，ｈｔ，ι，ｈ＾ｔ，ι，ｅｔ，ι）ｔ∈［ｄ］，ι∈［０，１］，ＧＴ，ｈＴ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ５２で生成された秘密情報ｓ０を用いて、マスター秘密鍵ｍｓｋ：＝ｓ０を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｍｓｋを記憶装置１２に書き込む。
【０１７９】
つまり、マスター鍵生成部１４は、数１９０に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数１９０】
0006625283.tif 000091
【０１８０】
図１９及び図２２を参照して、実施の形態５に係るＫｅｙＧｅｎアルゴリズムを説明する。
（ステップＳ６１：ＩＤ受付処理）
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋＩＤを使用するユーザの識別子ＩＤの入力を受け付ける。識別子ＩＤは、例えば、鍵生成装置１０の使用者によって入力装置を介して入力される。
ここでは、識別子ＩＤ：＝（ＩＤｔ）ｔ∈［Ｌ］であるとする。Ｌ＜ｄである。また、各ＩＤｔは、０又は１である。
【０１８１】
（ステップＳ６２：ＩＤ群割当処理）
ＩＤ群割当部１７は、ｔ∈［Ｌ］の各整数ｔについてのＩＤｔを、群Ｇｔ，ＩＤｔに割り当てる。そして、ＩＤ群割当部１７は、ｔ∈［Ｌ］の各整数ｔについての群Ｇｔ，ＩＤｔの直積をＩＤ群ＧＩＤとする。つまり、ＩＤ群割当部１７は、数１９１に示すように、ＩＤ群ＧＩＤを生成する。
【数１９１】
0006625283.tif 000092
ＩＤ群割当部１７は、数１９２に示すように、要素ｈＩＤを生成する。
【数１９２】
0006625283.tif 000093
【０１８２】
（ステップＳ６３：分散情報生成処理）
復号鍵生成部１５は、数１９３に示すように、分散情報ｓ→を生成する。分散情報ｓ→は、秘密情報ｓ０を分散させた情報である。
【数１９３】
0006625283.tif 000094
【０１８３】
（ステップＳ６４：鍵要素生成処理）
復号鍵生成部１５は、数１９４に示すように、ステップＳ６２で生成された要素ｈＩＤに、ステップＳ６３で生成された分散情報ｓ→を設定して、鍵要素ｋを生成する。
【数１９４】
0006625283.tif 000095
【０１８４】
（ステップＳ６５：鍵出力処理）
鍵出力部１６は、ステップＳ６１で受け付けられた識別子ＩＤと、ステップＳ６４で生成された鍵要素ｋとを含む復号鍵ｓｋＩＤを、入出力インタフェース１３を介して復号装置３０に出力する。
【０１８５】
つまり、復号鍵生成部１５は、数１９５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＩＤを生成する。
【数１９５】
0006625283.tif 000096
【０１８６】
図２０及び図２３を参照して、実施の形態５に係るＥｎｃアルゴリズムを説明する。
（ステップＳ７１：取得処理）
取得部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋを取得する。また、取得部２４は、暗号化対象のメッセージｍと、復号条件となる識別子ＩＤ’との入力を受け付ける。メッセージｍと識別子ＩＤ’とは、例えば、暗号化装置２０の使用者によって入力装置を介して入力される。
ここでは、識別子ＩＤ’：＝（ＩＤ’ｔ）ｔ∈［Ｌ］であるとする。Ｌ＜ｄである。また、各ＩＤｔは、０又は１である。
【０１８７】
（ステップＳ７２：ＩＤ群割当処理）
ＩＤ群割当部２７は、ｔ∈［Ｌ］の各整数ｔについてのＩＤ’ｔを、群Ｇ＾ｔ，ＩＤｔに割り当てる。そして、ＩＤ群割当部２７は、ｔ∈［Ｌ］の各整数ｔについての群Ｇ＾ｔ，ＩＤ’ｔの直積をＩＤ群Ｇ＾ＩＤとする。つまり、ＩＤ群割当部２７は、数１９６に示すように、ＩＤ群Ｇ＾ＩＤを生成する。
【数１９６】
0006625283.tif 000097
ＩＤ群割当部２７は、数１９７に示すように、要素ｈ＾ＩＤを生成する。
【数１９７】
0006625283.tif 000098
【０１８８】
（ステップＳ７３：暗号文生成処理）
暗号文生成部２５は、ステップＳ７１で取得された公開パラメータｐｋと、ステップＳ７２で生成された要素ｈ＾ＩＤとを用いて、暗号文ｃｔＩＤ’の要素を生成する。暗号文生成部２５は、群ＧＴの要素Ｘと群Ｇ＾ｔの要素Ｙ＾との生成要素を用いて暗号文ｃｔＩＤ’の要素を生成する。ここで、要素Ｘは、公開パラメータｐｋに含まれる要素ｈＴのことであり、要素Ｙ＾は、ステップＳ７２で生成された要素ｈ＾ＩＤとのことである。
暗号文生成処理は、ステップＳ７３１からステップＳ７３３の処理を含む。
【０１８９】
（ステップＳ７３１：変換情報生成処理）
変換情報生成部２５１は、一様乱数である暗号化乱数ζを生成する。
変換情報生成部２５１は、要素ｈＴと、暗号化乱数ζとを用いて、数１９８に示すように、変換情報ｚを生成する。
【数１９８】
0006625283.tif 000099
【０１９０】
（ステップＳ７３２：第１暗号要素生成処理）
第１暗号要素生成部２５２は、数１９９に示すように、ステップＳ７３１で生成された変換情報ｚに対して、メッセージｍを設定して暗号文ｃｔＩＤ’の要素である暗号要素ｃＴを生成する。
【数１９９】
0006625283.tif 000100
【０１９１】
（ステップＳ７３３：第２暗号要素生成処理）
第２暗号要素生成部２５３は、数２００に示すように、要素Ｙ＾である要素ｈ＾ＩＤに対して暗号化乱数ζを設定して暗号文ｃｔＩＤ’の要素である暗号要素ｃを生成する。
【数２００】
0006625283.tif 000101
【０１９２】
（ステップＳ７４：暗号文出力処理）
暗号文出力部２６は、ステップＳ７１で受け付けられた識別子ＩＤ’と、ステップＳ７３で生成された暗号要素ｃＴ，ｃとを暗号要素とする暗号文ｃｔＩＤ’を、入出力インタフェース２３を介して復号装置３０に出力する。
【０１９３】
つまり、暗号化装置２０は、数２０１に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を生成する。
【数２０１】
0006625283.tif 000102
【０１９４】
図２６及び図２７を参照して、実施の形態５に係るＤｅｌｅｇａｔｅアルゴリズムを説明する。
Ｄｅｌｅｇａｔｅアルゴリズムは、鍵委譲装置４０によって実行される。
【０１９５】
（ステップＳ８１：取得処理）
取得部４４は、入出力インタフェース４３を介して、鍵生成装置１０によって生成された公開パラメータｐｋと、下位の鍵の生成対象である復号鍵ｓｋＩＤ：＝ｋを取得する。また、取得部４４は、入出力インタフェース４３を介して、復号鍵ｓｋＩＤの下位の復号鍵ｓｋＩＤ＊を使用するユーザの識別子ＩＤＬ＋１∈｛０，１｝の入力を受け付ける。
【０１９６】
（ステップＳ８２：ＩＤ群割当処理）
ＩＤ群割当部４５は、ＩＤ＊：＝（ＩＤ，ＩＤＬ＋１）とする。また、ＩＤ群割当部４５は、数２０２に示すように、ＩＤ群ＧＩＤ＊を生成する。
【数２０２】
0006625283.tif 000103
ＩＤ群割当部４５は、数２０３に示すように、要素ｋ＋と、要素ｈＩＤ＊とを生成する。
【数２０３】
0006625283.tif 000104
【０１９７】
（ステップＳ８３：分散情報生成処理）
下位鍵生成部４６は、数２０４に示すように、分散情報τ→’を生成する。
【数２０４】
0006625283.tif 000105
【０１９８】
（ステップＳ８４：鍵要素生成処理）
下位鍵生成部４６は、数２０５に示すように、ステップＳ８２で生成された要素ｈＩＤ＊に、ステップＳ８３で生成された分散情報τ→’を設定して、鍵要素ｋＩＤ＊を生成する。
【数２０５】
0006625283.tif 000106
【０１９９】
（ステップＳ８５：鍵出力処理）
下位鍵出力部４７は、識別子ＩＤ＊と、ステップＳ６４で生成された鍵要素ｋＩＤ＊とを含む下位の復号鍵ｓｋＩＤ＊を、入出力インタフェース１３を介して復号装置３０に出力する。
【０２００】
つまり、復号鍵生成部１５は、数２０６に示すＤｅｌｅｇａｔｅアルゴリズムを実行して、下位の復号鍵ｓｋＩＤ＊を生成する。
【数２０６】
0006625283.tif 000107
【０２０１】
次に、上述した１ビットＨＩＢＥを応用したｎ（ｎ≧１）ビットＨＩＢＥを説明する。
ｎビットＨＩＢＥ方式は、１ビットＨＩＢＥのＳｅｔｕｐアルゴリズムと、ＫｅｙＧｅｎアルゴリズムと、Ｅｎｃアルゴリズムと、Ｄｅｃアルゴリズム、Ｄｅｌｅｇａｔｅアルゴリズムとを用いて構成される。
【０２０２】
ｎビットＨＩＢＥ方式の説明では、上述した１ビットＨＩＢＥ方式のＳｅｔｕｐアルゴリズムを、ｏｂＨＩＢＥ＿Ｓｅｔｕｐと呼ぶ。また、１ビットＨＩＢＥ方式のＫｅｙＧｅｎアルゴリズムを、ｏｂＨＩＢＥ＿ＫｅｙＧｅｎと呼ぶ。１ビットＨＩＢＥ方式のＥｎｃアルゴリズムを、ｏｂＨＩＢＥ＿Ｅｎｃと呼ぶ。１ビットＨＩＢＥ方式のＤｅｃアルゴリズムを、ｏｂＨＩＢＥ＿Ｄｅｃと呼ぶ。１ビットＨＩＢＥ方式のＤｅｌｅｇａｔｅアルゴリズムを、ｏｂＨＩＢＥ＿Ｄｅｌｅｇａｔｅと呼ぶ。
これに対して、ｎビットＨＩＢＥ方式のＳｅｔｕｐアルゴリズムを、ｎｂＨＩＢＥ＿Ｓｅｔｕｐと呼ぶ。また、ｎビットＨＩＢＥ方式のＫｅｙＧｅｎアルゴリズムを、ｎｂＨＩＢＥ＿ＫｅｙＧｅｎと呼ぶ。ｎビットＨＩＢＥ方式のＥｎｃアルゴリズムを、ｎｂＨＩＢＥ＿Ｅｎｃと呼ぶ。ｎビットＨＩＢＥ方式のＤｅｃアルゴリズムを、ｎｂＨＩＢＥ＿Ｄｅｃと呼ぶ。ｎビットＨＩＢＥ方式のＤｅｌｅｇａｔｅアルゴリズムを、ｎｂＨＩＢＥ＿Ｄｅｌｅｇａｔｅと呼ぶ。
【０２０３】
ｎｂＨＩＢＥ＿Ｓｅｔｕｐを説明する。
マスター鍵生成部１４は、セキュリティパラメータ１λと、階層数である値ｄと、ビット数である値ｎとの入力を受け付ける。
マスター鍵生成部１４は、セキュリティパラメータ１λと、値ｄ×ｎとを入力として、ｏｂＨＩＢＥ＿Ｓｅｔｕｐを実行して、公開パラメータｐｋｏｂとマスター秘密鍵ｍｓｋｏｂとを生成する。マスター鍵生成部１４は、公開パラメータｐｋｏｂをｎビットＨＩＢＥ方式の公開パラメータｐｋとし、マスター秘密鍵ｍｓｋｏｂをｎビットＨＩＢＥ方式のマスター秘密鍵ｍｓｋとする。
つまり、マスター鍵生成部１４は、数２０７に示すｎｂＨＩＢＥ＿Ｓｅｔｕｐを実行して、マスター鍵ペアを生成する。
【数２０７】
0006625283.tif 000108
【０２０４】
ｎｂＨＩＢＥ＿ＫｅｙＧｅｎを説明する。
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋＩＤを使用するユーザの識別子ＩＤの入力を受け付ける。ここでは、識別子ＩＤ：＝（ＩＤｔ：＝（ＩＤｔ，ｊ））ｔ∈［Ｌ］，ｊ∈［ｎ］であるとする。Ｌ＜ｄである。また、各ＩＤｔ，ｊは、０又は１である。
ＩＤ＾：＝（ＩＤｔ，ｊ）ｔ∈［Ｌ］，ｊ∈［ｎ］は、階層数Ｌｎの階層的な１ビットの識別子として扱われる。復号鍵生成部１５は、ｎｂＨＩＢＥ＿Ｓｅｔｕｐで生成された公開パラメータｐｋ及びマスター秘密鍵ｍｓｋと、識別子ＩＤ＾とを入力として、ｏｂＨＩＢＥ＿ＫｅｙＧｅｎを実行して、復号鍵ｓｋＩＤを生成する。
つまり、復号鍵生成部１５は、数２０８に示すｎｂＨＩＢＥ＿ＫｅｙＧｅｎを実行して、復号鍵ｓｋＩＤを生成する。
【数２０８】
0006625283.tif 000109
【０２０５】
ｎｂＨＩＢＥ＿Ｅｎｃを説明する。
取得部２４は、入出力インタフェース２３を介して、公開パラメータｐｋを取得する。また、取得部２４は、暗号化対象のメッセージｍと、復号条件となる識別子ＩＤ’との入力を受け付ける。ここでは、識別子ＩＤ’：＝（ＩＤ’ｔ：＝（ＩＤ’ｔ，ｊ））ｔ∈［Ｌ］，ｊ∈［ｎ］であるとする。
ＩＤ’＊：＝（ＩＤ’ｔ，ｊ）ｔ∈［Ｌ］，ｊ∈［ｎ］は、階層数Ｌｎの階層的な１ビットの識別子として扱われる。暗号文生成部２５とＩＤ群割当部２７とは、公開パラメータｐｋと、メッセージｍと、識別子ＩＤ’＊とを入力として、ｏｂＨＩＢＥ＿Ｅｎｃを実行して、暗号文ｃｔＩＤ’を生成する。
【０２０６】
つまり、暗号化装置２０は、数２０９に示すｎｂＨＩＢＥ＿Ｅｎｃを実行して、暗号文ｃｔＩＤ’を生成する。
【数２０９】
0006625283.tif 000110
【０２０７】
ｎｂＨＩＢＥ＿Ｄｅｃを説明する。
取得部３４は、入出力インタフェース３３を介して、公開パラメータｐｋと、復号鍵ｓｋＩＤと、暗号文ｃｔＩＤ’とを取得する。
復号部３５は、公開パラメータｐｋと、復号鍵ｓｋＩＤのＩＤをＩＤ＊とした復号鍵ｓｋＩＤ＊と、暗号文ｃｔＩＤ’のＩＤ’をＩＤ’＊とした暗号文ｃｔＩＤ’＊とを入力として、ｏｂＨＩＢＥ＿Ｄｅｃを実行して、メッセージｍ’を生成する。
つまり、復号装置３０は、数２１０に示すｎｂＨＩＢＥ＿Ｄｅｃを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数２１０】
0006625283.tif 000111
【０２０８】
ｎｂＨＩＢＥ＿Ｄｅｌｅｇａｔｅを説明する。
取得部４４は、入出力インタフェース４３を介して、公開パラメータｐｋと、復号鍵ｓｋＩＤとを取得する。また、取得部４４は、入出力インタフェース４３を介して、識別子ＩＤＬ＋１∈｛０，１｝ｎの入力を受け付ける。
ＩＤ群割当部４５と下位鍵生成部４６とは、識別子ＩＤＬ＋１を（ＩＤＬ＋１，ｊ）ｊ∈［ｎ］とし、復号鍵ｓｋＩＤを復号鍵ｓｋ０とする。そして、ＩＤ群割当部４５と下位鍵生成部４６とは、ｊ∈［ｎ］の各整数ｊについて、公開パラメータｐｋと、復号鍵ｓｋｊ−１と、識別子ＩＤＬ＋１，ｊとを入力として、ｏｂＨＩＢＥ＿Ｄｅｌｅｇａｔｅを実行して、復号鍵ｓｋｊを生成する。そして、下位鍵出力部４７は、復号鍵ｓｋｎを下位の復号鍵ｓｋＩＤ’として出力する。
つまり、復号鍵生成部１５は、数２１１に示すｎｂＨＩＢＥ＿Ｄｅｌｅｇａｔｅを実行して、下位の復号鍵ｓｋＩＤ’を生成する。
【数２１１】
0006625283.tif 000112
【０２０９】
＊＊＊実施の形態５の効果＊＊＊
以上のように、実施の形態５に係る暗号システム１は、ＩＰＧを用いてＨＩＢＥ方式を実現する。そのため、同種写像問題困難性から安全性を示すことを可能とすることができる。
また、実施の形態５に係る暗号システム１は、鍵生成乱数τｊ，ιによって変換された生成要素である要素Ｙ＾を用いて暗号文ｃｔΓを生成する。これにより、ペアリング問題困難性から安全性を示すことを可能とすることができる。
【０２１０】
実施の形態６．
実施の形態６では、高安全なＢｏｎｅｈ−Ｂｏｙｅｎ型の１ビットＨＩＢＥを説明する。
実施の形態６では、実施の形態５と同一の点については説明を省略し、異なる点を説明する。
【０２１１】
＊＊＊動作の説明＊＊＊
図５と、図１０と、図１９から図２３と、図２６と、図２７とを参照して、実施の形態６に係る暗号システム１の動作を説明する。実施の形態６についても、実施の形態５と同様に各動作は、各方法及び各プログラムの処理に相当する。
【０２１２】
図１９及び図２１を参照して、実施の形態６に係るＳｅｔｕｐアルゴリズムを説明する。
（ステップＳ５１：ＩＰＧ生成処理）
マスター鍵生成部１４は、入出力インタフェース１３を介してセキュリティパラメータ１λと、階層数である値ｄ≧２との入力を受け付ける。マスター鍵生成部１４は、受け付けられたセキュリティパラメータ１λと、４ｄとを入力として、ＩＰＧ生成アルゴリズムＧｅｎＩＰＧ（１λ，４ｄ）を実行して、数２１２に示す公開パラメータｐｋＩＰＧとマスター秘密鍵ｍｓｋＩＰＧとのマスター鍵ペアを生成する。
【数２１２】
0006625283.tif 000113
【０２１３】
（ステップＳ５２：秘密情報生成処理）
マスター鍵生成部１４は、一様乱数である秘密情報π，τを生成する。
マスター鍵生成部１４は、数２１３に示すように、群ＧＴの要素ｇＴに秘密情報π，τを設定して要素ｈＴを生成する。
【数２１３】
0006625283.tif 000114
また、マスター鍵生成部１４は、ｔ∈［ｄ］とι∈［０，１］の各整数ｔ，ιについて、数２１４に示すように、秘密情報π，τを用いて、要素ｆＬｔ，ιと要素ｆ＾Ｒｔ，ιと要素ｕＬιとを生成する。
【数２１４】
0006625283.tif 000115
【０２１４】
（ステップＳ５３：鍵生成乱数生成処理）
マスター鍵生成部１４は、ｔ∈［ｄ］とι∈［０，１］の各整数ｔ，ιについて、一様乱数である鍵生成乱数σｔ，ιを生成する。
マスター鍵生成部１４は、ｔ∈［ｄ］とι∈［０，１］の各整数ｔ，ιについて、数２１５に示すように、群Ｇ＾Ｒｔ，ιの要素ｇ＾Ｒｔ，ιに、鍵生成乱数σｔ，ιを設定して要素ｈ＾Ｒｔ，ιを生成する。
【数２１５】
0006625283.tif 000116
また、マスター鍵生成部１４は、ｔ∈［ｄ］とι∈［０，１］の各整数ｔ，ιについて、数２１６に示すように、群ＧＬｔ，ιの要素ｇＬｔ，ιに、鍵生成乱数σｔ，ιを設定して要素ｈＬｔ，ιを生成する。
【数２１６】
0006625283.tif 000117
【０２１５】
（ステップＳ５４：マスター鍵生成処理）
マスター鍵生成部１４は、ステップＳ５１で生成された公開パラメータｐｋＩＰＧと、ステップＳ５２で生成された要素ｈＴと要素ｆＬｔ，ιと要素ｆ＾Ｒｔ，ιと要素ｕＬιと、ステップＳ５３で生成された要素ｈ＾Ｒｔ，ιと要素ｈＬｔ，ιとを用いて、公開パラメータｐｋ：＝（（（ＧＬｔ，ι，Ｇ＾Ｌｔ，ι，ｆＬｔ，ι，ｈＬｔ，ι，ｇ＾Ｌｔ，ι，ｅＬｔ，ι），（ＧＲｔ，ι，Ｇ＾Ｒｔ，ι，ｇＲｔ，ｆ＾Ｒｔ，ι，ｈ＾Ｒｔ，ι，ι，ｅＲｔ，ι））ｔ∈［ｄ］，ι∈［０，１］，ＧＴ，ｈＴ）を生成する。鍵出力部１６は、公開パラメータｐｋを入出力インタフェース１３を介して外部の公開用サーバ等へ出力することにより、公開パラメータｐｋを暗号化装置２０及び復号装置３０に出力する。
また、マスター鍵生成部１４は、ステップＳ５２で生成された要素ｕＬιを用いて、マスター秘密鍵ｍｓｋ：＝（要素ｕＬι）ι∈［０，１］を生成する。マスター鍵生成部１４は、生成されたマスター秘密鍵ｍｓｋを記憶装置１２に書き込む。
【０２１６】
つまり、マスター鍵生成部１４は、数２１７に示すＳｅｔｕｐアルゴリズムを実行して、マスター鍵ペアを生成する。
【数２１７】
0006625283.tif 000118
【０２１７】
図１９及び図２２を参照して、実施の形態６に係るＫｅｙＧｅｎアルゴリズムを説明する。
（ステップＳ６１：ＩＤ受付処理）
復号鍵生成部１５は、入出力インタフェース１３を介して、復号鍵ｓｋＩＤを使用するユーザの識別子ＩＤの入力を受け付ける。識別子ＩＤは、例えば、鍵生成装置１０の使用者によって入力装置を介して入力される。
ここでは、識別子ＩＤ：＝（ＩＤｔ）ｔ∈［Ｌ］であるとする。Ｌ＜ｄである。また、各ＩＤｔは、０又は１である。
【０２１８】
（ステップＳ６２：ＩＤ群割当処理）
ＩＤ群割当部１７は、ｔ∈［Ｌ］の各整数ｔについてのＩＤｔを、群ＧＬｔ，ＩＤｔ及び群ＧＲｔ，ＩＤｔに割り当てる。そして、ＩＤ群割当部１７は、ｔ∈［Ｌ］の各整数ｔについての群ＧＬｔ，ＩＤｔの直積をＩＤ群ＧＬＩＤとし、ｔ∈［Ｌ］の各整数ｔについての群ＧＲｔ，ＩＤｔの直積をＩＤ群ＧＲＩＤとする。つまり、ＩＤ群割当部１７は、数２１８に示すように、ＩＤ群ＧＬＩＤ及びＩＤ群ＧＲＩＤを生成する。
【数２１８】
0006625283.tif 000119
ＩＤ群割当部１７は、数２１９に示すように、要素ｇＬＩＤと要素ｆＬＩＤと要素ｈＬＩＤと要素ｇＲＩＤとを生成する。
【数２１９】
0006625283.tif 000120
【０２１９】
（ステップＳ６３：分散情報生成処理）
復号鍵生成部１５は、数２２０に示すように、分散情報τ→を生成する。
【数２２０】
0006625283.tif 000121
【０２２０】
（ステップＳ６４：鍵要素生成処理）
復号鍵生成部１５は、数２２１に示すように、ステップＳ６２で生成された要素ｇＬＩＤと要素ｆＬＩＤと要素ｈＬＩＤと要素ｇＲＩＤとに、ステップＳ６３で生成された分散情報τ→と、一様乱数ｒ→：＝（ｒｔ）ｔ∈［Ｌ］とを用いて、鍵要素ｋ：＝｛ｖＬＩＤ・ＦＬ（ＩＤ）ｒ→，（ｇＲＩＤ）｝を生成する。
【数２２１】
0006625283.tif 000122
【０２２１】
（ステップＳ６５：鍵出力処理）
鍵出力部１６は、ステップＳ６１で受け付けられた識別子ＩＤと、ステップＳ６４で生成された鍵要素ｋとを含む復号鍵ｓｋＩＤを、入出力インタフェース１３を介して復号装置３０に出力する。
【０２２２】
つまり、復号鍵生成部１５は、数２２２に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＩＤを生成する。
【数２２２】
0006625283.tif 000123
【０２２３】
図２０及び図２３を参照して、実施の形態６に係るＥｎｃアルゴリズムを説明する。
（ステップＳ７１：取得処理）
取得部２４は、入出力インタフェース２３を介して、鍵生成装置１０によって生成された公開パラメータｐｋを取得する。また、取得部２４は、暗号化対象のメッセージｍと、復号条件となる識別子ＩＤ’との入力を受け付ける。メッセージｍと識別子ＩＤ’とは、例えば、暗号化装置２０の使用者によって入力装置を介して入力される。
ここでは、識別子ＩＤ’：＝（ＩＤ’ｔ）ｔ∈［Ｌ］であるとする。Ｌ＜ｄである。また、各ＩＤ’ｔは、０又は１である。
【０２２４】
（ステップＳ７２：ＩＤ群割当処理）
ＩＤ群割当部２７は、ｔ∈［Ｌ］の各整数ｔについてのＩＤ’ｔを、群Ｇ＾Ｌｔ，ＩＤｔ及び群Ｇ＾Ｒｔ，ＩＤｔに割り当てる。そして、ＩＤ群割当部２７は、ｔ∈［Ｌ］の各整数ｔについての群Ｇ＾Ｌｔ，ＩＤ’ｔの直積をＩＤ群Ｇ＾ＬＩＤとし、ｔ∈［Ｌ］の各整数ｔについての群Ｇ＾Ｒｔ，ＩＤ’ｔの直積をＩＤ群Ｇ＾ＲＩＤとする。つまり、ＩＤ群割当部２７は、数２２３に示すように、ＩＤ群Ｇ＾ＬＩＤ及びＩＤ群Ｇ＾ＲＩＤを生成する。
【数２２３】
0006625283.tif 000124
ＩＤ群割当部２７は、数２２４に示すように、要素ｇ＾ＬＩＤと要素ｆ＾ＲＩＤと要素ｈ＾ＲＩＤとを生成する。
【数２２４】
0006625283.tif 000125
【０２２５】
（ステップＳ７３：暗号文生成処理）
暗号文生成部２５は、ステップＳ７１で取得された公開パラメータｐｋと、ステップＳ７２で生成された要素ｇ＾ＬＩＤと要素ｆ＾ＲＩＤと要素ｈ＾ＲＩＤとを用いて、暗号文ｃｔＩＤ’の要素を生成する。暗号文生成部２５は、群ＧＴの要素Ｘと群Ｇ＾ｔの要素Ｙ＾との生成要素を用いて暗号文ｃｔＩＤ’の要素を生成する。ここで、要素Ｘは、公開パラメータｐｋに含まれる要素ｈＴのことであり、要素Ｙ＾は、ステップＳ７２で生成された要素ｇ＾ＬＩＤと要素ｆ＾ＲＩＤと要素ｈ＾ＲＩＤとのことである。
暗号文生成処理は、ステップＳ７３１からステップＳ７３３の処理を含む。
【０２２６】
（ステップＳ７３１：変換情報生成処理）
変換情報生成部２５１は、一様乱数である暗号化乱数ζを生成する。
変換情報生成部２５１は、要素ｈＴと、暗号化乱数ζとを用いて、数２２５に示すように、変換情報ｚを生成する。
【数２２５】
0006625283.tif 000126
【０２２７】
（ステップＳ７３２：第１暗号要素生成処理）
第１暗号要素生成部２５２は、数２２６に示すように、ステップＳ７３１で生成された変換情報ｚに対して、メッセージｍを設定して暗号文ｃｔＩＤ’の要素である暗号要素ｃＴを生成する。
【数２２６】
0006625283.tif 000127
【０２２８】
（ステップＳ７３３：第２暗号要素生成処理）
第２暗号要素生成部２５３は、数２２７に示すように、要素Ｙ＾である要素ｇ＾ＬＩＤと要素ｆ＾ＲＩＤと要素ｈ＾ＲＩＤとに対して暗号化乱数ζを設定して暗号文ｃｔＩＤ’の要素である暗号要素ｃ：＝｛（ｇ＾ＬＩＤ）ζ，Ｆ＾Ｒ（ＩＤ）ζ｝を生成する。
【数２２７】
0006625283.tif 000128
【０２２９】
（ステップＳ７４：暗号文出力処理）
暗号文出力部２６は、ステップＳ７１で受け付けられた識別子ＩＤ’と、ステップＳ７３で生成された暗号要素ｃＴ，ｃとを暗号要素とする暗号文ｃｔＩＤ’を、入出力インタフェース２３を介して復号装置３０に出力する。
【０２３０】
つまり、暗号化装置２０は、数２２８に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を生成する。
【数２２８】
0006625283.tif 000129
【０２３１】
図５及び図１０を参照して、実施の形態６に係るＤｅｃアルゴリズムを説明する。
ステップＳ４１とステップＳ４２との処理と、ステップＳ４４とステップＳ４５との処理とは、実施の形態５と同じである。
【０２３２】
（ステップＳ４３：復号処理）
復号部３５は、ステップＳ４１で受け付けられた復号鍵ｓｋＩＤにより、暗号文ｃｔＩＤ’を復号して、メッセージｍ’を生成する。
復号処理は、ステップＳ４３１とステップＳ４３２との処理を含む。
【０２３３】
（ステップＳ４３１：変換情報生成処理）
変換情報生成部３５１は、復号鍵ｓｋＩＤに含まれる鍵要素ｋ：＝｛ｖＬＩＤ・ＦＬ（ＩＤ）ｒ→，（ｇＲＩＤ）｝と、暗号文ｃｔＩＤ’に含まれる暗号要素ｃ：＝｛（ｇ＾ＬＩＤ）ζ，Ｆ＾Ｒ（ＩＤ）ζ｝とを用いて、数２２９に示すように、変換情報ｚ’を生成する。ここで、ｋＬ：＝ＬＩＤ・ＦＬ（ＩＤ）ｒ→であり、ｋＲ：＝（ｇＲＩＤ）である。また、ｃＬ：＝（ｇ＾ＬＩＤ）ζであり、ｃＲ：＝Ｆ＾Ｒ（ＩＤ）ζである。
【数２２９】
0006625283.tif 000130
ここで、数２３０であるため、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤが復号可能であれば、変換情報ｚ’と変換情報ｚとは同一になる。
【数２３０】
0006625283.tif 000131
【０２３４】
（ステップＳ４３２：メッセージ生成処理）
メッセージ生成部３５２は、ステップＳ４３１で生成された変換情報ｚ’と、暗号文ｃｔＩＤ’に含まれる暗号要素ｃＴとを用いて、数２３１に示すように、メッセージｍ’を生成する。
【数２３１】
0006625283.tif 000132
【０２３５】
つまり、復号装置３０は、数２３２に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔＩＤ’を復号鍵ｓｋＩＤにより復号する。
【数２３２】
0006625283.tif 000133
【０２３６】
図２６及び図２７を参照して、実施の形態６に係るＤｅｌｅｇａｔｅアルゴリズムを説明する。
Ｄｅｌｅｇａｔｅアルゴリズムは、鍵委譲装置４０によって実行される。
【０２３７】
（ステップＳ８１：取得処理）
取得部４４は、入出力インタフェース４３を介して、鍵生成装置１０によって生成された公開パラメータｐｋと、下位の鍵の生成対象である復号鍵ｓｋＩＤ：＝（ＩＤ，ｋＬ，ｋＲ）を取得する。ここで、ｋＬ：＝ＬＩＤ・ＦＬ（ＩＤ）ｒ→であり、ｋＲ：＝（ｇＲＩＤ）である。また、取得部４４は、入出力インタフェース４３を介して、復号鍵ｓｋＩＤの下位の復号鍵ｓｋＩＤ’を使用するユーザの識別子ＩＤＬ＋１∈｛０，１｝の入力を受け付ける。
【０２３８】
（ステップＳ８２：ＩＤ群割当処理）
ＩＤ群割当部４５は、ＩＤ’：＝（ＩＤ，ＩＤＬ＋１）とする。また、ＩＤ群割当部４５は、数２３３に示すように、ＩＤ群ＧＬＩＤ’及びＩＤ群ＧＲＩＤ’を生成する。
【数２３３】
0006625283.tif 000134
ＩＤ群割当部４５は、数２３４に示すように、要素ｋ＋Ｌと、要素ｇＬＩＤ’と、要素ｋ＋Ｒと、要素ｇＲＩＤ’とを生成する。
【数２３４】
0006625283.tif 000135
【０２３９】
（ステップＳ８３：分散情報生成処理）
下位鍵生成部４６は、数２３５に示すように、分散情報τ→’を生成する。
【数２３５】
0006625283.tif 000136
【０２４０】
（ステップＳ８４：鍵要素生成処理）
下位鍵生成部４６は、数２３６に示すように、ステップＳ８２で生成された要素ｋ＋Ｌと、要素ｇＬＩＤ’と、要素ｋ＋Ｒと、要素ｇＲＩＤ’とに、ステップＳ８３で生成された分散情報τ→’と、一様乱数ｒ→’：＝（ｒ’ｔ）ｔ∈［Ｌ＋１］とを設定して、鍵要素ｋ：＝｛ｋＬ，ｋＲ｝を生成する。
【数２３６】
0006625283.tif 000137
【０２４１】
（ステップＳ８５：鍵出力処理）
下位鍵出力部４７は、識別子ＩＤ’と、ステップＳ８４で生成された鍵要素ｋとを含む下位の復号鍵ｓｋＩＤ’を、入出力インタフェース１３を介して復号装置３０に出力する。
【０２４２】
つまり、復号鍵生成部１５は、数２３７に示すＤｅｌｅｇａｔｅアルゴリズムを実行して、下位の復号鍵ｓｋＩＤ’を生成する。
【数２３７】
0006625283.tif 000138
【０２４３】
＊＊＊実施の形態６の効果＊＊＊
以上のように、実施の形態６に係る暗号システム１は、ＩＰＧを用いてＨＩＢＥ方式を実現する。そのため、同種写像問題困難性から安全性を示すことを可能とすることができる。
また、実施の形態６に係る暗号システム１は、鍵生成乱数σｊ，ιによって変換された生成要素である要素Ｙ＾を用いて暗号文ｃｔΓを生成する。これにより、ペアリング問題困難性から安全性を示すことを可能とすることができる。
【符号の説明】
【０２４４】
１  暗号システム、１０  鍵生成装置、１１  プロセッサ、１２  記憶装置、１３  入出力インタフェース、１４  マスター鍵生成部、１５  復号鍵生成部、１６  鍵出力部１６、１７  ＩＤ群割当部、１８  電子回路、２０  暗号化装置、２１  プロセッサ、２２  記憶装置、２３  入出力インタフェース、２４  取得部、２５  暗号文生成部、２６  暗号文出力部、２７  ＩＤ群割当部、２８  電子回路、３０  復号装置、３１  プロセッサ、３２  記憶装置、３３  入出力インタフェース、３４  取得部、３５  復号部、３６  メッセージ出力部、３８  電子回路、４０  鍵委譲装置、４１  プロセッサ、４２  記憶装置、４３  入出力インタフェース、４４  取得部、４５  ＩＤ群割当部、４６  下位鍵生成部、４７  下位鍵出力部、４８  電子回路。
【図１】
0006625283.tif 000159
【図２】
0006625283.tif 000160
【図３】
0006625283.tif 000161
【図４】
0006625283.tif 000162
【図５】
0006625283.tif 000163
【図６】
0006625283.tif 000164
【図７】
0006625283.tif 000165
【図８】
0006625283.tif 000166
【図９】
0006625283.tif 000167
【図１０】
0006625283.tif 000168
【図１１】
0006625283.tif 000169
【図１２】
0006625283.tif 000170
【図１３】
0006625283.tif 000171
【図１４】
0006625283.tif 000172
【図１５】
0006625283.tif 000173
【図１６】
0006625283.tif 000174
【図１７】
0006625283.tif 000175
【図１８】
0006625283.tif 000176
【図１９】
0006625283.tif 000177
【図２０】
0006625283.tif 000178
【図２１】
0006625283.tif 000179
【図２２】
0006625283.tif 000180
【図２３】
0006625283.tif 000181
【図２４】
0006625283.tif 000182
【図２５】
0006625283.tif 000183
【図２６】
0006625283.tif 000184
【図２７】
0006625283.tif 000185