(57)【特許請求の範囲】
【請求項１】
２つの情報が互いに対応している場合に一方の情報が設定された暗号文を他方の情報が設定された復号鍵により復号可能な暗号方式における代理人再暗号機能を実現する暗号システムであり、
互いに対応する属性情報ｘ０，ｖ０のうちの一方が設定された暗号文ｃｔ０を出力する暗号化装置と、
前記属性情報ｘ０，ｖ０のうちの他方が設定された復号鍵ｋ＊を取得し、取得した復号鍵ｋ＊に変換情報ｒ１を乗じた復号鍵ｋ＊ｒｋ０と、互いに対応する属性情報ｘ１，ｖ１のうちの一方が設定されて前記変換情報ｒ１が暗号化された暗号文ｃｔ’１とを含む再暗号化鍵ｒｋ１を出力する再暗号化鍵生成装置と、
前記暗号文ｃｔ０と前記復号鍵ｋ＊ｒｋ０とのペアリング演算を計算して生成されたセッション鍵Ｋ’０と、前記暗号文ｃｔ’１とを含む再暗号文ｃｔ１を出力する再暗号化装置とを備えることを特徴とする暗号システム。
【請求項２】
前記暗号システムは、さらに、
前記属性情報ｘ１，ｖ１のうちの他方が設定された復号鍵ｋ＊’を取得し、取得した復号鍵ｋ＊’と前記暗号文ｃｔ’１とのペアリング演算を計算して前記変換情報ｒ１を生成し、生成した変換情報ｒ１と前記セッション鍵Ｋ’０とからメッセージｍを生成する再暗号文復号装置
を備えることを特徴とする請求項１に記載の暗号システム。
【請求項３】
前記再暗号文復号装置は、前記復号鍵ｋ＊’を変換情報ｒ２で変換した復号鍵ｋ＊ｒｋ１と、互いに対応する属性情報ｘ２，ｖ２のうちの一方が設定されて前記変換情報ｒ２が暗号化された暗号文ｃｔ’２とを含む再暗号化鍵ｒｋ２を出力し、
前記再暗号化装置は、前記再暗号文ｃｔ１と前記復号鍵ｋ＊ｒｋ１とのペアリング演算を計算して生成されたセッション鍵Ｋ’１と、前記暗号文ｃｔ’２とを含む再暗号文ｃｔ２を出力する
ことを特徴とする請求項２に記載の暗号システム。
【請求項４】
前記暗号化装置は、数１に示す暗号文ｃｔ０を出力し、
前記再暗号化鍵生成装置は、数２に示す復号鍵ｋ＊を取得し、数３に示す復号鍵ｋ＊ｒｋ０と、数４に示す暗号文ｃｔ’１とを含む再暗号化鍵ｒｋ１を出力し、
前記再暗号化装置は、数５に示すセッション鍵Ｋ’０を含む再暗号文ｃｔ１を出力することを特徴とする請求項１から３のいずれか１項に記載の暗号システム。
【数１】
0006053966.tif 000104
【数２】
0006053966.tif 000105
【数３】
0006053966.tif 000106
【数４】
0006053966.tif 000107
【数５】
0006053966.tif 000108
【請求項５】
前記暗号化装置は、数６に示す暗号文ｃｔ０を出力し、
前記再暗号化鍵生成装置は、数７に示す復号鍵ｋ＊を取得し、数８に示す復号鍵ｋ＊ｒｋ０と、数９に示す暗号文ｃｔ’１とを含む再暗号化鍵ｒｋ１を出力し、
前記再暗号化装置は、数１０に示すセッション鍵Ｋ’ ０を含む再暗号文ｃｔ１を出力
する
ことを特徴とする請求項１から３のいずれか１項に記載の暗号システム。
【数６】
0006053966.tif 000109
【数７】
0006053966.tif 000110
【数８】
0006053966.tif 000111
【数９】
0006053966.tif 000112
【数１０】
0006053966.tif 000113
【請求項６】
前記暗号化装置は、数１１に示す暗号文ｃｔ０を出力し、
前記再暗号化鍵生成装置は、数１２に示す復号鍵ｋ＊を取得し、数１３に示す復号鍵ｋ＊ｒｋ０と、数１４に示す暗号文ｃｔ’１とを含む再暗号化鍵ｒｋ１を出力し、
前記再暗号化装置は、数１５に示すセッション鍵Ｋ’ ０を含む再暗号文ｃｔ１を出力
する
ことを特徴とする請求項１から３のいずれか１項に記載の暗号システム。
【数１１】
0006053966.tif 000114
【数１２】
0006053966.tif 000115
【数１３】
0006053966.tif 000116
【数１４】
0006053966.tif 000117
【数１５】
0006053966.tif 000118
【請求項７】
前記暗号化装置は、数１６に示す暗号文ｃｔ０を出力し、
前記再暗号化鍵生成装置は、数１７に示す復号鍵ｋ＊を取得し、数１８に示す復号鍵ｋ＊ｒｋ０と、数１９に示す暗号文ｃｔ’１とを含む再暗号化鍵ｒｋ１を出力し、
前記再暗号化装置は、数２０に示すセッション鍵Ｋ’ ０を含む再暗号文ｃｔ１を出力
する
ことを特徴とする請求項１から３のいずれか１項に記載の暗号システム。
【数１６】
0006053966.tif 000119
【数１７】
0006053966.tif 000120
【数１８】
0006053966.tif 000121
【数１９】
0006053966.tif 000122
【数２０】
0006053966.tif 000123
【請求項８】
２つの情報が互いに対応している場合に一方の情報が設定された暗号文を他方の情報が設定された復号鍵により復号可能な暗号方式における代理人再暗号機能を実現する暗号システムにおける再暗号化装置であり、
互いに対応する属性情報ｘ０，ｖ０のうちの一方が設定された暗号文ｃｔ０を取得する暗号文取得部と、
前記属性情報ｘ０，ｖ０のうちの他方が設定された復号鍵ｋ＊に変換情報ｒ１を乗じた復号鍵ｋ＊ｒｋ０と、互いに対応する属性情報ｘ１，ｖ１のうちの一方が設定されて前記変換情報ｒ１が暗号化された暗号文ｃｔ’１とを含む再暗号化鍵ｒｋ１を取得する再暗号化鍵取得部と、
前記暗号文ｃｔ０と前記復号鍵ｋ＊ｒｋ０とのペアリング演算を計算して生成されたセッション鍵Ｋ’０と、前記暗号文ｃｔ’１とを含む再暗号文ｃｔ１を出力する再暗号文出力部と
を備えることを特徴とする再暗号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、関数型暗号における代理人再暗号化（Ｆｕｎｃｔｉｏｎａｌ  Ｐｒｏｘｙ  Ｒｅ−Ｅｎｃｒｙｐｔｉｏｎ、ＦＰＲＥ）方式に関するものである。
【背景技術】
【０００２】
代理人再暗号化（Ｐｒｏｘｙ  Ｒｅ−Ｅｎｃｒｙｐｔｉｏｎ，ＰＲＥ）は、暗号文を復号することなく、暗号文の復号権限を他者に委譲するシステムである。非特許文献１には、ＩＤベース暗号におけるＰＲＥ（Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  ＰＲＥ，ＩＢＰＲＥ）方式に関する記載がある。非特許文献２には、属性ベース暗号におけるＰＲＥ（Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  ＰＲＥ，ＡＢＰＲＥ）方式に関する記載がある。非特許文献２記載されたＰＲＥ方式では、論理積と否定とからなる属性のみを暗号文に指定することができる。【０００３】
特許文献１には、関数型暗号（Ｆｕｎｃｔｉｏｎａｌ  Ｅｎｃｒｙｐｔｉｏｎ，ＦＥ）方式に関する記載がある。非特許文献３には、ＦＰＲＥ方式に関する記載がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１２−１３３２１４号公報
【非特許文献】
【０００５】
【非特許文献１】Ｍ．Ｇｒｅｅｎ，  ａｎｄ  Ｇ．  Ａｔｅｎｉｅｓｅ，  Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｐｒｏｘｙ  Ｒｅ−ｅｎｃｒｙｐｔｉｏｎ．  Ｉｎ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｎｅｔｗｏｒｋ  Ｓｅｃｕｒｉｔｙ．  ｖｏｌｕｍｅ  ４５２１  ｏｆ  ＬＮＣＳ，  ｐｐ  ２８８−３０６  ，  ２００７．
【非特許文献２】Ｘｉａｏｈｕｉ  Ｌｉａｎｇ，  Ｚｈｅｎｆｕ  Ｃａｏ，  Ｈｕａｎｇ  Ｌｉｎ，  Ｊｕｎ  Ｓｈａｏ．  Ａｔｔｒｉｂｕｔｅ  ｂａｓｅｄ  ｐｒｏｘｙ  ｒｅ−ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｄｅｌｅｇａｔｉｎｇ  ｃａｐａｂｉｌｉｔｉｅｓ．  ＡＳＩＡＣＣＳ  ２００９  ｐｐ．２７６−２８６．
【非特許文献３】Ｙｕｔａｋａ  ｋａｗａｉ  ａｎｄ  Ｋａｔｕｙｕｋｉ  Ｔａｋａｓｈｉｍａ，  Ｆｕｌｌｙ−Ａｎｏｎｙｍｏｕｓ  Ｆｕｎｃｔｉｏｎａｌ  Ｐｒｏｘｙ−Ｒｅ−Ｅｎｃｒｙｐｔｉｏｎ．  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ：  Ｒｅｐｏｒｔ  ２０１３／３１８
【非特許文献４】Ｒ．  Ｃａｎｅｔｔｉ  ａｎｄ  Ｓ．  Ｈｏｈｅｎｂｅｒｇｅｒ．  Ｃｈｏｓｅｎ−Ｃｉｐｈｅｒｔｅｘｔ  Ｓｅｃｕｒｅ  Ｐｒｏｘｙ  Ｒｅ−ｅｎｃｒｙｐｔｉｏｎ．  Ｉｎ  ＡＣＭＣＣＳ  ２００７．
【非特許文献５】Ｏｋａｍｏｔｏ，  Ｔ  Ｔａｋａｓｈｉｍａ，  Ｋ．：Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｓｉｇｎａｔｕｒｅｓ．ｅＰｒｉｎｔ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１１／７０１
【非特許文献６】Ｏｋａｍｏｔｏ，  Ｔ  Ｔａｋａｓｈｉｍａ，  Ｋ．：Ｆｕｌｌｙ  Ｓｅｃｕｒｅ  Ｕｎｂｏｕｎｄｅｄ  Ｉｎｎｅｒ−Ｐｒｏｄｕｃｔ  ａｎｄ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ．ｅＰｒｉｎｔ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１２／６７１
【非特許文献７】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ａｃｈｉｅｖｉｎｇ  Ｓｈｏｒｔ  Ｃｉｐｈｅｒｔｅｘｔｓ  ｏｒ  Ｓｈｏｒｔ  Ｓｅｃｒｅｔ−Ｋｅｙｓ  ｆｏｒ  Ａｄａｐｔｉｖｅｌｙ  Ｓｅｃｕｒｅ  Ｇｅｎｅｒａｌ  Ｉｎｎｅｒ−Ｐｒｏｄｕｃｔ  Ｅｎｃｒｙｐｔｉｏｎ．  ＣＡＮＳ  ２０１１，  ＬＮＣＳ，  ｖｏｌ．  ７０９２，  ｐｐ．  １３８−１５９  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１１）．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献３に記載されたＦＰＲＥ方式では、暗号化アルゴリズムにより作成されるオリジナル暗号文を再暗号化すると、暗号文のサイズが３倍になる。再暗号文をさらに再暗号化すると、さらに暗号文のサイズが３倍になる。つまり、ｎ回再暗号化を実行すると、オリジナル暗号文と比べて暗号文サイズは、３ｎ倍となり、再暗号化回数に対して指数関数的に暗号文のサイズが増加してしまう。
この発明は、再暗号化に伴う暗号文のサイズの増加量を抑えたＦＰＲＥ方式を実現することを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係る暗号システムは、
２つの情報が互いに対応している場合に一方の情報が設定された暗号文を他方の情報が設定された復号鍵により復号可能な暗号方式における代理人再暗号機能を実現する暗号システムであり、
互いに対応する属性情報ｘ０，ｖ０のうちの一方が設定された暗号文ｃｔ０を出力する暗号化装置と、
前記属性情報ｘ０，ｖ０のうちの他方が設定された復号鍵ｋ＊を取得し、取得した復号鍵ｋ＊を変換情報ｒ１で変換した復号鍵ｋ＊ｒｋ０と、互いに対応する属性情報ｘ１，ｖ１のうちの一方が設定されて前記変換情報ｒ１が暗号化された暗号文ｃｔ’１とを含む再暗号化鍵ｒｋ１を出力する再暗号化鍵生成装置と、
前記暗号文ｃｔ０を前記復号鍵ｋ＊ｒｋ０で復号したセッション鍵Ｋ’０と、前記暗号文ｃｔ’１とを含む再暗号文ｃｔ１を出力する再暗号化装置と
を備えることを特徴とする。
【発明の効果】
【０００８】
この発明に係る暗号システムでは、変換情報で変換した復号鍵で暗号文を復号したセッション鍵と、転送先の利用者が復号可能となるように変換情報を暗号化した暗号文とを再暗号文ｃｔ１としている。これにより、再暗号化に伴う暗号文のサイズの増加量を抑えることができる。
【図面の簡単な説明】
【０００９】
【図１】行列Ｍ＾の説明図。
【図２】行列Ｍδの説明図。
【図３】ｓ０の説明図。
【図４】ｓ→Ｔの説明図。
【図５】ＣＰ−ＦＰＲＥ方式を実行する暗号システム１０の構成図。
【図６】鍵生成装置１００の機能を示す機能ブロック図。
【図７】暗号化装置２００の機能を示す機能ブロック図。
【図８】復号装置３００の機能を示す機能ブロック図。
【図９】再暗号化装置４００の機能を示す機能ブロック図。
【図１０】再暗号文復号装置５００の機能を示す機能ブロック図。
【図１１】Ｓｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１２】ＫＧアルゴリズムの処理を示すフローチャート。
【図１３】Ｅｎｃアルゴリズムの処理を示すフローチャート。
【図１４】ＲＫＧアルゴリズムの処理を示すフローチャート。
【図１５】ＲＥｎｃアルゴリズムの処理を示すフローチャート。
【図１６】Ｄｅｃ１アルゴリズムの処理を示すフローチャート。
【図１７】Ｄｅｃ２アルゴリズムの処理を示すフローチャート。
【図１８】Ｓｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１９】ＫＰ−ＦＰＲＥ方式を実行する暗号システム１０の構成図。
【図２０】鍵生成装置１００の機能を示す機能ブロック図。
【図２１】暗号化装置２００の機能を示す機能ブロック図。
【図２２】復号装置３００の機能を示す機能ブロック図。
【図２３】再暗号化装置４００の機能を示す機能ブロック図。
【図２４】再暗号文復号装置５００の機能を示す機能ブロック図。
【図２５】ＫＧアルゴリズムの処理を示すフローチャート。
【図２６】Ｅｎｃアルゴリズムの処理を示すフローチャート。
【図２７】ＲＫＧアルゴリズムの処理を示すフローチャート。
【図２８】ＲＥｎｃアルゴリズムの処理を示すフローチャート。
【図２９】Ｄｅｃ１アルゴリズムの処理を示すフローチャート。
【図３０】Ｄｅｃ２アルゴリズムの処理を示すフローチャート。
【図３１】実施の形態１〜４に示した暗号システム１０の各装置のハードウェア構成の例を示す図。
【発明を実施するための形態】
【００１０】
以下の説明における記法について説明する。
Ａがランダムな変数または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
0006053966.tif 000002
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
0006053966.tif 000003
数１０３は、ｙにｚが設定されたこと、ｙがｚにより定義されたこと、又はｙがｚを代入されたことを表す。
【数１０３】
0006053966.tif 000004
ａが定数であるとき、数１０４は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数１０４】
0006053966.tif 000005
数１０５、つまりＦｑは、位数ｑの有限体を示す。
【数１０５】
0006053966.tif 000006
ベクトル表記は、有限体Ｆｑにおけるベクトル表示を表す。つまり、数１０６である。
【数１０６】
0006053966.tif 000007
数１０７は、数１０８に示す２つのベクトルｘ→とｖ→との数１０９に示す内積を表す。
【数１０７】
0006053966.tif 000008
【数１０８】
0006053966.tif 000009
【数１０９】
0006053966.tif 000010
ＸＴは、行列Ｘの転置行列を表す。
数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１である。
【数１１０】
0006053966.tif 000011
【数１１１】
0006053966.tif 000012
ｅ→ｊは、数１１２に示す正規基底ベクトルを示す。
【数１１２】
0006053966.tif 000013
【００１１】
また、以下の説明において、Ｖｔ，ｎｔ，ｗｔ，ｚｔ，ｎｕ，ｗｕ，ｚｕが下付き又は上付きで示されている場合、このＶｔ，ｎｔ，ｗｔ，ｚｔ，ｎｕ，ｗｕ，ｚｕはＶｔ，ｎｔ，ｗｔ，ｚｔ，ｎｕ，ｗｕ，ｚｕを意味する。同様に、δｉ，ｊが上付きで示されている場合、このδｉ，ｊは、δｉ，ｊを意味する。同様に、φｊが上付きで示されている場合、このφｊは、φｊを意味する。
また、ベクトルを意味する→が下付き文字又は上付き文字に付されている場合、この→は下付き文字又は上付き文字に上付きで付されていることを意味する。
【００１２】
実施の形態１．
この実施の形態では、ＦＰＲＥ方式を実現する基礎となる概念を説明した上で、この実施の形態に係るＦＰＲＥ方式の構成について説明する。
第１に、ＦＰＲＥについて簡単に説明する。
第２に、ＦＰＲＥ方式を実現するための空間である双対ペアリングベクトル空間（Ｄｕａｌ  Ｐａｉｒｉｎｇ  Ｖｅｃｔｏｒ  Ｓｐａｃｅｓ，ＤＰＶＳ）という豊かな数学的構造を有する空間を説明する。
第３に、ＦＰＲＥ方式を実現するための概念を説明する。ここでは、スパンプログラム、属性ベクトルの内積とアクセス構造、秘密分散方式（秘密共有方式）について説明する。
第４に、この実施の形態に係るＦＰＲＥ方式を説明する。この実施の形態では、暗号文ポリシーのＦＰＲＥ方式（Ｃｉｐｈｅｒｔｅｘｔ−Ｐｏｌｉｃｙ  ＦＰＲＥ，ＣＰ−ＦＰＲＥ）方式について説明する。そこで、まず、ＣＰ−ＦＰＲＥ方式の基本構成について説明する。次に、このＣＰ−ＦＰＲＥ方式を実現する暗号システム１０の基本構成について説明する。そして、この実施の形態に係るＣＰ−ＦＰＲＥ方式、及び、暗号システム１０について詳細に説明する。
【００１３】
＜第１．ＦＰＲＥ＞
ＦＰＲＥは、暗号化鍵（ｅｋ）と、復号鍵（ｄｋ）と、再暗号化鍵（ｒｋ）の関係をより高度化し、柔軟にした代理人再暗号化方式である。
【００１４】
ＦＰＲＥは、以下の２つの特徴を持つ。
１つ目に、暗号化鍵と復号鍵とは、それぞれ属性情報ｘと属性情報ｖとが設定されている。そして、関係Ｒに対して、Ｒ（ｘ、ｖ）が成立する場合に限り、復号鍵ｄｋｖは暗号化鍵ｅｋｘで暗号化された暗号文を復号することができる。
２つ目に、暗号化鍵と復号鍵とに属性情報ｘと属性情報ｖとがそれぞれ設定されていることに加え、再暗号化鍵は２つの属性情報（ｘ’，ｖ）が設定されている。そして、Ｒ（ｘ，ｖ）が成立する場合に限り、再暗号化鍵ｒｋ（ｘ’，ｖ）は、暗号化鍵ｅｋｘで暗号化された暗号文を、Ｒ（ｘ’、ｖ’）が成立する復号鍵ｄｋｖ’で復号可能な暗号文、つまり暗号化鍵ｅｋｘ’で暗号化された暗号文に変更することができる。
【００１５】
関係Ｒが等号関係である場合、つまり、ｘ＝ｖである場合に限りＲ（ｘ，ｖ）が成立する場合、ＰＲＥ方式はＩＤＰＲＥである。
【００１６】
ＩＤＰＲＥよりも一般化されたＰＲＥとして、ＡＢＰＲＥがある。ＡＢＰＲＥでは、暗号化鍵と復号鍵とに設定される属性情報が属性情報の組である。例えば、暗号化鍵と復号鍵とに設定される属性情報が、それぞれ、Ｘ：＝（ｘ１，．．．，ｘｄ）と、Ｖ：＝（ｖ１，．．．，ｖｄ）とである。
属性情報のコンポーネントについて、コンポーネント毎の等号関係（例えば、｛ｘｔ＝ｖｔ｝ｔ∈｛１，．．．，ｄ｝）がアクセスストラクチャＳに入力される。そして、アクセスストラクチャＳが入力を受理した場合にのみ、Ｒ（Ｘ，Ｖ）が成立する。つまり、暗号化鍵で暗号化された暗号文を復号鍵で復号することができる。非特許文献２では、アクセスストラクチャＳが暗号文に埋め込まれている暗号文ポリシーのＰＲＥ方式を提案している。その際のアクセスストラクチャは、論理積と否定のみで構成される構造である。
【００１７】
暗号文の転送機能が存在しない、つまり再暗号化鍵が存在しない、通常のＦＥがある。ＦＥでは、再暗号化鍵、再暗号化処理は存在せず、暗号化鍵と復号鍵とは、それぞれ、属性情報ｘと属性情報ｖとが設定されている。そして、関係Ｒに対してＲ（ｘ，ｖ）が成立する場合に限り、復号鍵ｄｋｖ：＝（ｄｋ，ｖ）は暗号化鍵ｅｋｘ：＝（ｅｋ，ｘ）で暗号化された暗号文を復号することができる。
【００１８】
＜第２．双対ペアリングベクトル空間＞
まず、対称双線形ペアリング群について説明する。
対称双線形ペアリング群（ｑ，Ｇ，ＧＴ，ｇ，ｅ）は、素数ｑと、位数ｑの巡回加法群Ｇと、位数ｑの巡回乗法群ＧＴと、ｇ≠０∈Ｇと、多項式時間で計算可能な非退化双線形ペアリング（Ｎｏｎｄｅｇｅｎｅｒａｔｅ  Ｂｉｌｉｎｅａｒ  Ｐａｉｒｉｎｇ）ｅ：Ｇ×Ｇ→ＧＴとの組である。非退化双線形ペアリングは、ｅ（ｓｇ，ｔｇ）＝ｅ（ｇ，ｇ）ｓｔであり、ｅ（ｇ，ｇ）≠１である。
以下の説明において、Ｇｂｐｇを、１λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を出力するアルゴリズムとする。
【００１９】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、対称双線形ペアリング群（ｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ））の直積によって構成することができる。双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、素数ｑ、数１１３に示すＦｑ上のＮ次元ベクトル空間Ｖ、位数ｑの巡回群ＧＴ、空間Ｖの標準基底Ａ：＝（ａ１，．．．，ａＮ）の組であり、以下の演算（１）（２）を有する。ここで、ａｉは、数１１４に示す通りである。
【数１１３】
0006053966.tif 000014
【数１１４】
0006053966.tif 000015
【００２０】
演算（１）：非退化双線形ペアリング
空間Ｖにおけるペアリングは、数１１５によって定義される。
【数１１５】
0006053966.tif 000016
これは、非退化双線形である。つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）ｓｔであり、全てのｙ∈Ｖに対して、ｅ（ｘ，ｙ）＝１の場合、ｘ＝０である。また、全てのｉとｊとに対して、ｅ（ａｉ，ａｊ）＝ｅ（ｇ，ｇ）δｉ，ｊである。ここで、ｉ＝ｊであれば、δｉ，ｊ＝１であり、ｉ≠ｊであれば、δｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈ＧＴである。
【００２１】
演算（２）：ディストーション写像
数１１６に示す空間Ｖにおける線形変換φｉ，ｊは、数１１７を行うことができる。
【数１１６】
0006053966.tif 000017
【数１１７】
0006053966.tif 000018
ここで、線形変換φｉ，ｊをディストーション写像と呼ぶ。
【００２２】
以下の説明において、Ｇｄｐｖｓを、１λ（λ∈自然数）、Ｎ∈自然数、双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を入力として、セキュリティパラメータがλであり、Ｎ次元の空間Ｖとする双対ペアリングベクトル空間のパラメータｐａｒａｍＶ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）の値を出力するアルゴリズムとする。
【００２３】
なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【００２４】
＜第３．ＦＰＲＥ方式を実現するための概念＞
＜第３−１．スパンプログラム＞
図１は、行列Ｍ＾の説明図である。
｛ｐ１，．．．，ｐｎ｝を変数の集合とする。Ｍ＾：＝（Ｍ，ρ）は、ラベル付けされた行列である。ここで、行列Ｍは、Ｆｑ上の（Ｌ行×ｒ列）の行列である。また、ρは、行列Ｍの各行に付されたラベルであり、｛ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝のいずれか１つのリテラルへ対応付けられる。なお、Ｍの全ての行に付されたラベルρi（ｉ＝１，．．．，Ｌ）がいずれか１つのリテラルへ対応付けられる。つまり、ρ：｛１，．．．，Ｌ｝→｛ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝である。
【００２５】
全ての入力列δ∈｛０，１｝ｎに対して、行列Ｍの部分行列Ｍδは定義される。行列Ｍδは、入力列δによってラベルρに値“１”が対応付けられた行列Ｍの行から構成される部分行列である。つまり、行列Ｍδは、δｉ＝１であるようなｐｉに対応付けられた行列Ｍの行と、δｉ＝０であるような¬ｐｉに対応付けられた行列Ｍの行とからなる部分行列である。
図２は、行列Ｍδの説明図である。なお、図２では、ｎ＝７，Ｌ＝６，ｒ＝５としている。つまり、変数の集合は、｛ｐ１，．．．，ｐ７｝であり、行列Ｍは（６行×５列）の行列である。また、図２において、ラベルρは、ρ１が¬ｐ２に、ρ２がｐ１に、ρ３がｐ４に、ρ４が¬ｐ５に、ρ５が¬ｐ３に、ρ６がｐ５にそれぞれ対応付けられているとする。
ここで、入力列δ∈｛０，１｝７が、δ１＝１，δ２＝０，δ３＝１，δ４＝０，δ５＝０，δ６＝１，δ７＝１であるとする。この場合、破線で囲んだリテラル（ｐ１，ｐ３，ｐ６，ｐ７，¬ｐ２，¬ｐ４，¬ｐ５）に対応付けられている行列Ｍの行からなる部分行列が行列Ｍδである。つまり、行列Ｍの１行目（Ｍ１），２行目（Ｍ２），４行目（Ｍ４）からなる部分行列が行列Ｍδである。
【００２６】
言い替えると、写像γ：｛１，．．．，Ｌ｝→｛０，１｝が、［ρ（ｊ）＝ｐｉ］∧［δｉ＝１］又は［ρ（ｊ）＝¬ｐｉ］∧［δｉ＝０］である場合、γ（ｊ）＝１であり、他の場合、γ（ｊ）＝０であるとする。この場合に、Ｍδ：＝（Ｍｊ）γ（ｊ）＝１である。ここで、Ｍｊは、行列Ｍのｊ番目の行である。
つまり、図２では、写像γ（ｊ）＝１（ｊ＝１，２，４）であり、写像γ（ｊ）＝０（ｊ＝３，５，６）である。したがって、（Ｍｊ）γ（ｊ）＝１は、Ｍ１，Ｍ２，Ｍ４であり、行列Ｍδである。
すなわち、写像γ（ｊ）の値が“０”であるか“１”であるかによって、行列Ｍのｊ番目の行が行列Ｍδに含まれるか否かが決定される。
【００２７】
１→∈ｓｐａｎ＜Ｍδ＞である場合に限り、スパンプログラムＭ＾は入力列δを受理し、他の場合には入力列δを拒絶する。つまり、入力列δによって行列Ｍ＾から得られる行列Ｍδの行を線形結合して１→が得られる場合に限り、スパンプログラムＭ＾は入力列δを受理する。なお、１→とは、各要素が値“１”である行ベクトルである。
例えば、図２の例であれば、行列Ｍの１，２，４行目からなる行列Ｍδの各行を線形結合して１→が得られる場合に限り、スパンプログラムＭ＾は入力列δを受理する。つまり、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となるα１，α２，α４が存在する場合には、スパンプログラムＭ＾は入力列δを受理する。
【００２８】
ここで、ラベルρが正のリテラル｛ｐ１，．．．，ｐｎ｝にのみ対応付けられている場合、スパンプログラムはモノトーンと呼ばれる。一方、ラベルρがリテラル｛ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝に対応付けられている場合、スパンプログラムはノンモノトーンと呼ばれる。ここでは、スパンプログラムはノンモノトーンとする。そして、ノンモノトーンスパンプログラムを用いて、アクセスストラクチャ（ノンモノトーンアクセスストラクチャ）を構成する。アクセスストラクチャとは、簡単に言うと暗号へのアクセス制御を行うものである。つまり、暗号文を復号できるか否かの制御を行うものである。
詳しくは後述するが、スパンプログラムがモノトーンではなく、ノンモノトーンであることにより、スパンプログラムを利用して構成するＦＰＲＥ方式の利用範囲が広がる。
【００２９】
＜第３−２．属性情報の内積とアクセスストラクチャ＞
ここでは、属性情報の内積を用いて上述した写像γ（ｊ）を計算する。つまり、属性情報の内積を用いて、行列Ｍのどの行を行列Ｍδに含めるかを決定する。
【００３０】
Ｕｔ（ｔ＝１，．．．，ｄでありＵｔ⊂｛０，１｝＊）は、部分全集合（ｓｕｂ−ｕｎｉｖｅｒｓｅ）であり、属性の集合である。そして、Ｕｔは、それぞれ部分全集合の識別情報（ｔ）と、ｎ次元ベクトル（ｖ→）とを含む。つまり、Ｕｔは、（ｔ，ｖ→）である。ここで、ｔ∈｛１，．．．，ｄ｝であり、ｖ→∈Ｆｑｎである。
【００３１】
Ｕｔ：＝（ｔ，ｖ→）をスパンプログラムＭ＾：＝（Ｍ，ρ）における変数ｐとする。つまり、ｐ：＝（ｔ，ｖ→）である。そして、変数（ｐ：＝（ｔ，ｖ→），（ｔ，ｖ’→），．．．）としたスパンプログラムＭ＾：＝（Ｍ，ρ）をアクセスストラクチャＳとする。
つまり、アクセスストラクチャＳ：＝（Ｍ，ρ）であり、ρ：｛１，．．．，Ｌ｝→｛（ｔ，ｖ→），（ｔ，ｖ’→），．．．，¬（ｔ，ｖ→），¬（ｔ，ｖ’→），．．．｝である。
【００３２】
次に、Γを属性の集合とする。つまり、Γ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎ，１≦ｔ≦ｄ｝である。
アクセスストラクチャＳにΓが与えられた場合、スパンプログラムＭ＾：＝（Ｍ，ρ）に対する写像γ：｛１，．．．，Ｌ｝→｛０，１｝は、以下のように定義される。ｉ＝１，．．．，Ｌの各整数ｉについて、［ρ（ｉ）＝（ｔ，ｖ→ｉ）］∧［（ｔ，ｘ→ｔ）∈Γ］∧［ｖ→ｉ・ｘ→ｔ＝０］、又は、［ρ（ｉ）＝¬（ｔ，ｖ→ｉ）］∧［（ｔ，ｘ→ｔ）∈Γ］∧［ｖ→ｉ・ｘ→ｔ≠０］である場合、γ（ｊ）＝１であり、他の場合、γ（ｊ）＝０とする。
つまり、属性情報ｖ→とｘ→との内積に基づき、写像γが計算される。そして、上述したように、写像γにより、行列Ｍのどの行を行列Ｍδに含めるかが決定される。すなわち、属性情報ｖ→とｘ→との内積により、行列Ｍのどの行を行列Ｍδに含めるかが決定され、１→∈ｓｐａｎ＜（Ｍｉ）γ（ｉ）＝１＞である場合に限り、アクセスストラクチャＳ：＝（Ｍ，ρ）はΓを受理する。
【００３３】
＜第３−３．秘密分散方式＞
アクセスストラクチャＳ：＝（Ｍ，ρ）に対する秘密分散方式について説明する。
なお、秘密分散方式とは、秘密情報を分散させ、意味のない分散情報にすることである。例えば、秘密情報ｓを１０個に分散させ、１０個の分散情報を生成する。ここで、１０個の分散情報それぞれは、秘密情報ｓの情報を有していない。したがって、ある１個の分散情報を手に入れても秘密情報ｓに関して何ら情報を得ることはできない。一方、１０個の分散情報を全て手に入れれば、秘密情報ｓを復元できる。
また、１０個の分散情報を全て手に入れなくても、一部だけ（例えば、８個）手に入れれば秘密情報ｓを復元できる秘密分散方式もある。このように、１０個の分散情報のうち８個で秘密情報ｓを復元できる場合を、８−ｏｕｔ−ｏｆ−１０と呼ぶ。つまり、ｎ個の分散情報のうちｔ個で秘密情報ｓを復元できる場合を、ｔ−ｏｕｔ−ｏｆ−ｎと呼ぶ。このｔを閾値と呼ぶ。
また、ｄ１，．．．，ｄ１０の１０個の分散情報を生成した場合に、ｄ１，．．．，ｄ８までの８個の分散情報であれば秘密情報ｓを復元できるが、ｄ３，．．．，ｄ１０までの８個の分散情報であれば秘密情報ｓを復元できないというような秘密分散方式もある。つまり、手に入れた分散情報の数だけでなく、分散情報の組合せに応じて秘密情報ｓを復元できるか否かを制御する秘密分散方式もある。
【００３４】
図３は、ｓ０の説明図である。図４は、ｓ→Ｔの説明図である。
行列Ｍを（Ｌ行×ｒ列）の行列とする。ｆ→Ｔを数１１８に示す列ベクトルとする。
【数１１８】
0006053966.tif 000019
数１１９に示すｓ０を共有される秘密情報とする。
【数１１９】
0006053966.tif 000020
また、数１２０に示すｓ→Ｔをｓ０のＬ個の分散情報のベクトルとする。
【数１２０】
0006053966.tif 000021
そして、分散情報ｓｉをρ（ｉ）に属するものとする。
【００３５】
アクセスストラクチャＳ：＝（Ｍ，ρ）がΓを受理する場合、つまりγ：｛１，．．．，Ｌ｝→｛０，１｝について１→∈ｓｐａｎ＜（Ｍｉ）γ（ｉ）＝１＞である場合、Ｉ⊆｛ｉ∈｛１，．．．，Ｌ｝｜γ（ｉ）-＝１｝である定数｛αｉ∈Ｆｑ｜ｉ∈Ｉ｝が存在する。
これは、図２の例で、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となるα１，α２，α４が存在する場合には、スパンプログラムＭ＾は入力列δを受理すると説明したことからも明らかである。つまり、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となるα１，α２，α４が存在する場合には、スパンプログラムＭ＾が入力列δを受理するのであれば、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となるα１，α２，α４が存在する。
そして、数１２１である。
【数１２１】
0006053966.tif 000022
なお、定数｛αｉ｝は、行列Ｍのサイズにおける多項式時間で計算可能である。
【００３６】
以下の実施の形態に係るＦＰＲＥ方式は、上述したように、スパンプログラムに内積述語と秘密分散方式とを適用してアクセスストラクチャを構成する。そのため、スパンプログラムにおける行列Ｍや、内積述語における属性情報ｘ及び属性情報ｖ（述語情報）を設計することにより、アクセス制御を自由に設計することができる。つまり、非常に高い自由度でアクセス制御の設計を行うことができる。なお、行列Ｍの設計は、秘密分散方式の閾値等の条件設計に相当する。
例えば、上述した属性ベース暗号方式は、以下の実施の形態に係るＦＰＲＥ方式におけるアクセスストラクチャにおいて、内積述語の設計をある条件に限定した場合に相当する。つまり、以下の実施の形態に係るＦＰＲＥ方式におけるアクセスストラクチャに比べ、属性ベース暗号方式におけるアクセスストラクチャは、内積述語における属性情報ｘ及び属性情報ｖ（述語情報）の設計の自由度がない分、アクセス制御の設計の自由度が低い。なお、具体的には、属性ベース暗号方式は、属性情報｛ｘ→ｔ｝ｔ∈｛１，．．．，ｄ｝と｛ｖ→ｔ｝ｔ∈｛１，．．．，ｄ｝とを、等号関係に対する２次元ベクトル、例えばｘ→ｔ：＝（１，ｘｔ）とｖ→ｔ：＝（ｖｔ，−１）とに限定した場合に相当する。
また、内積述語暗号方式におけるＰＲＥは、以下の実施の形態に係るＦＰＲＥ方式におけるアクセスストラクチャにおいて、スパンプログラムにおける行列Ｍの設計をある条件に限定した場合に相当する。つまり、以下の実施の形態に係るＦＰＲＥ方式におけるアクセスストラクチャに比べ、内積述語暗号方式におけるアクセスストラクチャは、スパンプログラムにおける行列Ｍの設計の自由度がない分、アクセス制御の設計の自由度が低い。なお、具体的には、内積述語暗号方式は、秘密分散方式を１−ｏｕｔ−ｏｆ−１（あるいは、ｄ−ｏｕｔ−ｏｆ−ｄ）に限定した場合である。
【００３７】
特に、以下の実施の形態に係るＦＰＲＥ方式におけるアクセスストラクチャは、ノンモノトーンスパンプログラムを用いたノンモノトーンアクセスストラクチャを構成する。そのため、アクセス制御の設計の自由度がより高くなる。
具体的には、ノンモノトーンスパンプログラムには、否定形のリテラル（¬ｐ）を含むため、否定形の条件を設定できる。例えば、第１会社には、Ａ部とＢ部とＣ部とＤ部との４つの部署があったとする。ここで、第１会社のＢ部以外の部署の属するユーザにのみアクセス可能（復号可能）というアクセス制御をしたいとする。この場合に、否定形の条件の設定ができないとすると、「第１会社のＡ部とＣ部とＤ部とのいずれかに属すること」という条件を設定する必要がある。一方、否定形の条件の設定ができるとすると、「第１会社の社員であって、Ｂ部以外に属すること」という条件を設定することができる。つまり、否定形の条件が設定できることで、自然な条件設定が可能となる。なお、ここでは部署の数が少ないが、部署の数が多い場合等は非常に有効であることが分かる。
【００３８】
＜第４．ＦＰＲＥ方式の基本構成＞
＜第４−１．ＣＰ−ＦＰＲＥ方式の基本構成＞
ＣＰ−ＦＰＲＥ方式の構成を簡単に説明する。なお、ＣＰ（暗号文ポリシー）とは、暗号文にＰｏｌｉｃｙが埋め込まれること、つまりアクセスストラクチャが埋め込まれることを意味する。
【００３９】
ＣＰ−ＦＰＲＥ方式は、Ｓｅｔｕｐ、ＫＧ、Ｅｎｃ、ＲＫＧ、ＲＥｎｃ、Ｄｅｃ１、Ｄｅｃ２の７つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλと、属性のフォーマットｎ→：＝（ｄ；ｎ１，．．．，ｎｄ；ｕ１，．．．，ｕｄ；ｚ１，．．．，ｚｄ）と、再暗号化回数の上限値を示す値Ｑとを入力として、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫＧ）
ＫＧアルゴリズムは、属性集合Γ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎｔ，１≦ｔ≦ｄ｝と、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、復号鍵ｓｋΓを出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、メッセージｍと、アクセスストラクチャＳ＝（Ｍ，ρ）と、公開パラメータｐｋとを入力として、暗号文ｃｔｎＳを出力する確率的アルゴリズムである。
（ＲＫＧ）
ＲＫＧアルゴリズムは、復号鍵ｓｋΓと、アクセスストラクチャＳ’：＝（Ｍ’，ρ’）と、公開パラメータｐｋと、再暗号化する暗号文ｃｔｎＳが再暗号化された回数を示す値ｎとを入力として、再暗号化鍵ｒｋｎΓ．Ｓ’を出力する確率的アルゴリズムである。
（ＲＥｎｃ）
ＲＥｎｃアルゴリズムは、暗号文ｃｔｎＳと、再暗号化鍵ｒｋｎΓ．Ｓ’と、公開パラメータｐｋとを入力として、再暗号文ｃｔｎ＋１Ｓ’を出力する確率的アルゴリズムである。
（Ｄｅｃ１）
Ｄｅｃ１アルゴリズムは、再暗号文ｃｔｎＳ’と、復号鍵ｓｋΓ’と、公開パラメータｐｋとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。
（Ｄｅｃ２）
Ｄｅｃ２アルゴリズムは、暗号文ｃｔｎＳ（ｃｔ０Ｓ）と、復号鍵ｓｋΓと、公開パラメータｐｋとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。
【００４０】
＜第４−２．暗号システム１０＞
ＣＰ−ＦＰＲＥ方式のアルゴリズムを実行する暗号システム１０について説明する。
図５は、ＣＰ−ＦＰＲＥ方式を実行する暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００（再暗号化鍵生成装置）、再暗号化装置４００、再暗号文復号装置５００（再暗号化鍵生成装置）を備える。
【００４１】
鍵生成装置１００は、セキュリティパラメータλと、属性のフォーマットｎ→：＝（ｄ；ｎ１，．．．，ｎｄ；ｕ１，．．．，ｕｄ；ｚ１，．．．，ｚｄ）と、値Ｑとを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。
そして、鍵生成装置１００は、公開パラメータｐｋを公開する。また、鍵生成装置１００は、属性集合Γを入力としてＫＧアルゴリズムを実行して、復号鍵ｓｋΓを生成して復号装置３００へ秘密裏に送信する。また、鍵生成装置１００は、属性集合Γ’を入力としてＫＧアルゴリズムを実行して、復号鍵ｓｋΓ’を生成して再暗号文復号装置５００へ秘密裏に送信する。
【００４２】
暗号化装置２００は、メッセージｍと、アクセスストラクチャＳと、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔｎＳを生成する。暗号化装置２００は、暗号文ｃｔｎＳを再暗号化装置４００へ送信する。
【００４３】
復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋΓと、アクセスストラクチャＳ’と、値ｎとを入力としてＲＫＧアルゴリズムを実行して、再暗号化鍵ｒｋｎΓ．Ｓ’を生成する。復号装置３００は、再暗号化鍵ｒｋｎΓ．Ｓ’を再暗号化装置に秘密裏に送信する。
また、復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋΓと、暗号文ｃｔｎＳ（ｃｔ０Ｓ）とを入力としてＤｅｃ２アルゴリズムを実行して、メッセージｍ又は識別情報⊥を出力する。
【００４４】
再暗号化装置４００は、公開パラメータｐｋと、再暗号化鍵ｒｋｎΓ．Ｓ’と、暗号文ｃｔｎＳとを入力として、ＲＥｎｃアルゴリズムを実行して、再暗号文ｃｔｎ＋１Ｓ’を生成する。再暗号化装置４００は、再暗号文ｃｔｎ＋１Ｓ’を再暗号文復号装置５００へ送信する。
【００４５】
再暗号文復号装置５００は、公開パラメータｐｋと、復号鍵ｓｋΓ’と、再暗号文ｃｔｎ＋１Ｓ’とを入力として、Ｄｅｃ１アルゴリズムを実行して、メッセージｍ又は識別情報⊥を出力する。
【００４６】
＜第４−４．ＣＰ−ＦＰＲＥ方式及び暗号システム１０の詳細＞
図６から図１７に基づき、ＣＰ−ＦＰＲＥ方式、及び、ＣＰ−ＦＰＲＥ方式を実行する暗号システム１０の機能と動作とについて説明する。
図６は、鍵生成装置１００の機能を示す機能ブロック図である。図７は、暗号化装置２００の機能を示す機能ブロック図である。図８は、復号装置３００の機能を示す機能ブロック図である。図９は、再暗号化装置４００の機能を示す機能ブロック図である。図１０は、再暗号文復号装置５００の機能を示す機能ブロック図である。
図１１と図１２とは、鍵生成装置１００の動作を示すフローチャートである。なお、図１１はＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図１２はＫＧアルゴリズムの処理を示すフローチャートである。図１３は、暗号化装置２００の動作を示すフローチャートであり、Ｅｎｃアルゴリズムの処理を示すフローチャートである。図１４は、復号装置３００の動作を示すフローチャートであり、ＲＫＧアルゴリズムの処理を示すフローチャートである。図１５は、再暗号化装置４００の動作を示すフローチャートであり、ＲＥｎｃアルゴリズムの処理を示すフローチャートである。図１６は、再暗号文復号装置５００の動作を示すフローチャートであり、Ｄｅｃ１アルゴリズムの処理を示すフローチャートである。図１７は、復号装置３００の動作を示すフローチャートであり、Ｄｅｃ２アルゴリズムの処理を示すフローチャートである。
【００４７】
鍵生成装置１００の機能と動作とについて説明する。
図６に示すように、鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵送信部１５０（鍵出力部）を備える。また、復号鍵生成部１４０は、乱数生成部１４１、復号鍵ｋ＊生成部１４２を備える。
【００４８】
まず、図１１に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：初期設定ステップ）
マスター鍵生成部１１０は、初期設定を実行する。
具体的には、マスター鍵生成部１１０は、以下の（１）から（３）までの処理を実行する。
【００４９】
（１）マスター鍵生成部１１０は、入力装置により、セキュリティパラメータλ（１λ）と、属性のフォーマットｎ→：＝（ｄ；ｎ１，．．．，ｎｄ；ｗ１，．．．，ｗｄ；ｚ１，．．．，ｚｄ）とを入力する。ここで、ｄは１以上の整数であり、ｔ＝１，．．．，ｄの各整数ｔについて、ｎｔは１以上の整数でありｗｔ，ｚｔは０以上の整数である。
【００５０】
（２）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλを入力としてアルゴリズムＧｂｐｇを実行して、双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を生成する。
【００５１】
（３）マスター鍵生成部１１０は、Ｎ０に５を設定し、ｔ＝１，．．．，ｄの各整数ｔについてＮｔにｎｔ＋ｗｔ＋ｚｔ＋１を設定する。
【００５２】
（Ｓ１０２：再暗号化回数入力ステップ）
マスター鍵生成部１１０は、入力装置により、再暗号化回数の上限を示す値Ｑを入力する。値Ｑは、１以上の整数である。
【００５３】
マスター鍵生成部１１０は、以下のＳ１０３からＳ１０５までの処理をｊ＝０，．．．，Ｑまで繰り返し、実行する。
【００５４】
（Ｓ１０３：正規直交基底生成ステップ）
マスター鍵生成部１１０は、処理装置により、ｔ＝０，．．．，ｄの各整数ｔについて、数１２２を計算して、パラメータｐａｒａｍｎ→と、基底Ｂ０．ｊ及び基底Ｂ＊０．ｊと、基底Ｂｔ．ｊ及び基底Ｂ＊ｔ．ｊとを生成する。
【数１２２】
0006053966.tif 000023
【００５５】
つまり、マスター鍵生成部１１０は以下の処理を実行する。
（１）マスター鍵生成部１１０は、乱数ψｊを生成する。また、マスター鍵生成部１１０は、ｅ（Ｇ，Ｇ）ψｊをｇＴ．ｊに設定する。
【００５６】
ｔ＝０，．．．，ｄの各整数ｔについて、（２）から（５）の処理を実行する。
（２）マスター鍵生成部１１０は、セキュリティパラメータλと、Ｎｔと、ｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値とを入力としてアルゴリズムＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶｔ：＝（ｑ，Ｖｔ，ＧＴ，Ａｔ，ｅ）の値を生成する。
【００５７】
（３）マスター鍵生成部１１０は、Ｎｔと、Ｆｑとを入力として、線形変換Ｘｔ：＝（χｔ，ｉ，ｊ’）ｉ，ｊ’をランダムに生成する。なお、ＧＬは、Ｇｅｎｅｒａｌ  Ｌｉｎｅａｒの略である。つまり、ＧＬは、一般線形群であり、行列式が０でない正方行列の集合であり、乗法に関し群である。また、（χｔ，ｉ，ｊ’）ｉ，ｊ’は、行列χｔ，ｉ，ｊ’の添え字ｉ，ｊ’に関する行列という意味である。ここでは、（χｔ，ｉ，ｊ’）ｉ，ｊ’ではｉ，ｊ’＝１，．．．，Ｎｔである。
【００５８】
（４）マスター鍵生成部１１０は、乱数ψと線形変換Ｘｔとに基づき、（νｔ，ｉ，ｊ’）ｉ，ｊ’：＝ψ・（ＸｔＴ）−１を生成する。なお、（νｔ，ｉ，ｊ’）ｉ，ｊ’も（χｔ，ｉ，ｊ’）ｉ，ｊ’と同様に、行列νｔ，ｉ，ｊ’の添え字ｉ，ｊ’に関する行列という意味である。ここでは、（νｔ，ｉ，ｊ’）ｉ，ｊ’ではｉ，ｊ’＝１，．．．，Ｎｔである。
【００５９】
（５）マスター鍵生成部１１０は、（３）で生成した線形変換Ｘｔに基づき、（２）で生成した標準基底Ａｔから基底Ｂｔ．ｊを生成する。マスター鍵生成部１１０は、（４）で生成した（νｔ，ｉ，ｊ’）ｉ，ｊ’に基づき、（２）で生成した標準基底Ａｔから基底Ｂ＊ｔ．ｊを生成する。
【００６０】
（６）マスター鍵生成部１１０は、ｐａｒａｍｎ→．ｊに（１）で生成したｇＴ．ｊと（２）で生成した｛ｐａｒａｍＶｔ｝ｔ＝０，．．．，ｄとを設定する。
【００６１】
（Ｓ１０４：公開パラメータ生成ステップ）
マスター鍵生成部１１０は、処理装置により、基底Ｂ０．ｊの部分基底Ｂ＾０．ｊと、基底Ｂｔ．ｊの部分基底Ｂ＾ｔ．ｊと、基底Ｂ＊０．ｊの部分基底Ｂ＾＊０．ｊと、基底Ｂ＊ｔ．ｊの部分基底Ｂ＾＊ｔ．ｊとを数１２３に示すように生成する。
【数１２３】
0006053966.tif 000024
マスター鍵生成部１１０は、セキュリティパラメータλと、ｐａｒａｍｎ→．ｊと、部分基底Ｂ＾０．ｊ，Ｂ＾ｔ．ｊ，Ｂ＾＊０．ｊ，Ｂ＾＊ｔ．ｊとを公開パラメータｐｋとする。
【００６２】
（Ｓ１０５：マスター鍵生成ステップ）
マスター鍵生成部１１０は、基底ベクトルｂ＊０．ｊ．１をマスター鍵ｓｋとする。
【００６３】
（Ｓ１０６：マスター鍵記憶ステップ）
マスター鍵記憶部１２０は、（Ｓ１０４）で生成した公開パラメータｐｋを記憶装置に記憶する。また、マスター鍵記憶部１２０は、（Ｓ１０５）で生成したマスター鍵ｓｋを記憶装置に記憶する。
【００６４】
つまり、（Ｓ１０１）から（Ｓ１０５）において、鍵生成装置１００は、数１２４に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ１０６）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００、復号装置３００、再暗号化装置４００、再暗号文復号装置５００が取得可能な状態にされる。
【数１２４】
0006053966.tif 000025
【００６５】
次に、図１２に基づき、ＫＧアルゴリズムの処理について説明する。
（Ｓ２０１：情報入力ステップ）
情報入力部１３０は、入力装置により、属性集合Γ：＝｛（ｔ，ｘ→ｔ：＝（ｘｔ，１，．．．，ｘｔ，ｎｔ∈Ｆｑｎｔ＼｛０→｝））｜１≦ｔ≦ｄ｝を入力する。なお、ｔは、１以上ｄ以下の全ての整数ではなく、１以上ｄ以下の少なくとも一部の整数であってもよい。また、属性集合Γは、例えば、復号鍵ｓｋΓの使用者の属性情報が設定されている。
【００６６】
（Ｓ２０２：乱数生成ステップ）
乱数生成部１４１は、処理装置により、乱数を数１２５に示すように生成する。
【数１２５】
0006053966.tif 000026
【００６７】
（Ｓ２０３：復号鍵ｋ＊生成ステップ）
復号鍵ｋ＊生成部１４２は、処理装置により、ｊ＝０，．．．，Ｑの各整数ｊについて、復号鍵ｋ＊０，ｊを数１２６に示すように生成する。
【数１２６】
0006053966.tif 000027
なお、数１１０に示す基底Ｂと基底Ｂ＊とに対して数１１１である。そのため、数１２６は、基底Ｂ＊０の基底ベクトルｂ＊０．ｊ．１の係数として１が設定され、基底ベクトルｂ＊０．ｊ．２の係数としてδｊが設定され、基底ベクトルｂ＊０．ｊ．３の係数として０が設定され、基底ベクトルｂ＊０．ｊ．４の係数としてφ０．ｊが設定され、基底ベクトルｂ＊０．ｊ．５の係数として０が設定されることを意味する。
【００６８】
また、復号鍵ｋ＊生成部１４２は、処理装置により、属性集合Γに含まれる各整数ｔとｊ＝０，．．．，Ｑの各整数ｊとについて、復号鍵ｋ＊ｔ．ｊを数１２７に示すように生成する。
【数１２７】
0006053966.tif 000028
なお、数１２７は、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ．ｊ．１，．．．，ｂ＊ｔ．ｊ．ｎｔの係数としてδｊｘｔ．１，．．．，δｊｘｔ．ｎｔが設定され、基底ベクトルｂ＊ｔ．ｊ．ｎｔ＋１，．．．，ｂ＊ｔ．ｊ．ｎｔ＋ｗｔの係数として０が設定され、基底ベクトルｂ＊ｔ．ｊ．ｎｔ＋ｗｔ＋１，．．．，ｂ＊ｔ．ｊ．ｎｔ＋ｗｔ＋ｚｔの係数としてφｔ．ｊ．１，．．．，φｔ．ｊ．ｚｔが設定され、基底ベクトルｂ＊ｔ．ｊ．ｎｔ＋ｗｔ＋ｚｔ＋１の係数として０が設定されることを意味する。
【００６９】
（Ｓ２０４：鍵送信ステップ）
鍵送信部１５０は、属性集合Γと、復号鍵ｋ＊０．ｊ，ｋ＊ｔ．ｊとを要素とする復号鍵ｓｋΓを、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ送信する。もちろん、復号鍵ｓｋΓは、他の方法により復号装置３００へ送信されてもよい。
【００７０】
つまり、（Ｓ２０１）から（Ｓ２０３）において、鍵生成装置１００は、数１２８に示すＫＧアルゴリズムを実行して、復号鍵ｓｋΓを生成する。そして、（Ｓ２０４）で、鍵生成装置１００は、復号鍵ｓｋΓを復号装置３００へ送信する。
【数１２８】
0006053966.tif 000029
【００７１】
なお、鍵生成装置１００は、（Ｓ２０１）において、復号鍵ｓｋΓ’の使用者の属性情報が設定された属性集合Γ’：＝｛（ｔ，ｘ’→ｔ：＝（ｘ’ｔ，１，．．．，ｘ’ｔ，ｎｔ∈Ｆｑｎｔ＼｛０→｝））｜１≦ｔ≦ｄ｝を入力して、ＫＧアルゴリズムを実行して、復号鍵ｓｋΓ’を生成する。そして、鍵生成装置１００は、復号鍵ｓｋΓ’：＝（Γ’，｛ｋ’＊０．ｊ，｛ｋ’＊ｔ．ｊ｝（ｔ，ｘ→ｔ）∈Γ’｝ｊ＝０，．．．，Ｑ）を再暗号文復号装置５００へ送信する。
【００７２】
暗号化装置２００の機能と動作とについて説明する。
図７に示すように、暗号化装置２００は、公開パラメータ受信部２１０、情報入力部２２０、暗号化部２３０、暗号文送信部２４０（暗号文出力部）を備える。また、暗号化部２３０は、ｆベクトル生成部２３１、ｓベクトル生成部２３２、乱数生成部２３３、暗号文ｃ生成部２３４を備える。
【００７３】
図１３に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ３０１：公開パラメータ受信ステップ）
公開パラメータ受信部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【００７４】
（Ｓ３０２：情報入力ステップ）
情報入力部２２０は、入力装置により、アクセスストラクチャＳ：＝（Ｍ，ρ）を入力する。なお、アクセスストラクチャＳは、実現したいシステムの条件に応じて設定されるものである。また、アクセスストラクチャＳのρは、例えば、暗号文ｃｔ０Ｓを復号可能なユーザの属性情報が設定されている。ここで、ρ（ｉ）＝（ｔ，ｖ→ｉ：＝（ｖｉ，１，．．．，ｖｉ，ｎｔ）∈Ｆｑｎｔ＼｛０→｝）（ｖｉ，ｎｔ≠０）である。なお、ＭはＬ行ｒ列の行列である。
また、情報入力部２２０は、入力装置により、復号装置３００へ送信するメッセージｍを入力する。
また、情報入力部２２０は、入力装置により、再暗号化回数ｎを入力する。ここで入力される再暗号化回数ｎは、通常であれば０となり、後述するＲＫＧアルゴリズムでＥｎｃアルゴリズムを呼び出した場合には、ＲＫＧアルゴリズムで指定された値となる。
【００７５】
（Ｓ３０３：ｆベクトル生成ステップ）
ｆベクトル生成部２３１は、処理装置により、ベクトルｆ→を数１２９に示すように生成する。
【数１２９】
0006053966.tif 000030
【００７６】
（Ｓ３０４：ｓベクトル生成ステップ）
ｓベクトル生成部２３２は、処理装置により、ベクトルｓ→Ｔを数１３０に示すように生成する。
【数１３０】
0006053966.tif 000031
また、ｓベクトル生成部２３２は、処理装置により、値ｓ０を数１３１に示すように生成する。
【数１３１】
0006053966.tif 000032
【００７７】
（Ｓ３０５：乱数生成ステップ）
乱数生成部２３３は、処理装置により、乱数を数１３２に示すように生成する。
【数１３２】
0006053966.tif 000033
【００７８】
（Ｓ３０６：暗号文ｃ生成ステップ）
暗号文ｃ生成部２３４は、処理装置により、暗号文ｃ０．ｎを数１３３に示すように生成する。
【数１３３】
0006053966.tif 000034
【００７９】
また、暗号文ｃ生成部２３４は、処理装置により、ｉ＝１，．．．，Ｌの各整数ｉについて、暗号文ｃｉ．ｎを数１３４に示すように生成する。
【数１３４】
0006053966.tif 000035
【００８０】
また、暗号文ｃ生成部２３４は、処理装置により、暗号文ｃＴ．ｎを数１３５に示すように生成する。
【数１３５】
0006053966.tif 000036
【００８１】
（Ｓ３０７：暗号文送信ステップ）
暗号文送信部２４０は、アクセスストラクチャＳと、暗号文ｃ０．ｎ，ｃ１．ｎ，．．．，ｃＬ．ｎ，ｃＴ．ｎと、再暗号化回数ｎとを要素とする暗号文ｃｔｎＳを、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｎＳは、他の方法により復号装置３００へ送信されてもよい。
【００８２】
つまり、（Ｓ３０１）から（Ｓ３０６）において、暗号化装置２００は、数１３６に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｎＳを生成する。そして、（Ｓ３０７）で、暗号化装置２００は生成した暗号文ｃｔｎＳを復号装置３００へ送信する。
【数１３６】
0006053966.tif 000037
【００８３】
復号装置３００の機能と動作とについて説明する。
図８に示すように、復号装置３００は、復号鍵受信部３１０（復号鍵取得部）、情報入力部３２０、再暗号化鍵生成部３３０、再暗号化鍵送信部３４０（再暗号化鍵出力部）、暗号文受信部３５０、スパンプログラム計算部３６０、補完係数計算部３７０、ペアリング演算部３８０、メッセージ計算部３９０を備える。また、再暗号化鍵生成部３３０は、乱数生成部３３１、暗号化部３３２、復号鍵ｋ＊ｒｋ生成部３３３を備える。
【００８４】
ここでは、図１４に基づき、ＲＫＧアルゴリズムの処理について説明する。Ｄｅｃ２アルゴリズムについては後述する。
【００８５】
（Ｓ４０１：復号鍵受信ステップ）
復号鍵受信部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信された復号鍵ｓｋΓを受信する。また、復号鍵受信部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【００８６】
（Ｓ４０２：情報入力ステップ）
情報入力部３２０は、入力装置により、アクセスストラクチャＳ’：＝（Ｍ’，ρ’）を入力する。なお、アクセスストラクチャＳ’は、実現したいシステムの条件に応じて設定されるものである。また、アクセスストラクチャＳ’のρ’は、例えば、再暗号文ｃｔｎ＋１Ｓ’を復号可能なユーザの属性情報が設定されている。ここで、ρ’（ｉ）＝（ｔ，ｖ→’ｉ：＝（ｖ’ｉ，１，．．．，ｖ’ｉ，ｎｔ）∈Ｆｑｎｔ＼｛０→｝）（ｖ’ｉ，ｎｔ≠０）である。
また、情報入力部３２０は、入力装置により、再暗号化回数ｎを入力する。ここで入力される再暗号化回数ｎは、何回再暗号化された暗号文を再暗号化するための再暗号化鍵を生成するかを示す。つまり、１度も再暗号化されていない暗号文ｃｔ０Ｓを再暗号化するための再暗号化鍵を生成する場合には、再暗号化回数ｎとして０が入力される。また、１度再暗号化された暗号文ｃｔ１Ｓを再暗号化するための再暗号化鍵を生成する場合には、再暗号化回数ｎとして１が入力される。
【００８７】
（Ｓ４０３：乱数生成ステップ）
乱数生成部３３１は、処理装置により、乱数を数１３７に示すように生成する。
【数１３７】
0006053966.tif 000038
【００８８】
（Ｓ４０４：乱数暗号化ステップ）
暗号化部３３２は、処理装置により、乱数ｒｎ＋１（変換情報）を数１３８に示すように暗号化して、暗号文ｃｔ’ｎ＋１Ｓ’を生成する。ここで、関数Ｅｎ＋１はＦｑからＧＴ．ｎ＋１へのエンコード関数である。
【数１３８】
0006053966.tif 000039
【００８９】
（Ｓ４０５：復号鍵ｋ＊ｒｋ生成ステップ）
復号鍵ｋ＊ｒｋ生成部３３３は、処理装置により、復号鍵ｋ＊ｒｋ０．ｎを数１３９に示すように生成する。
【数１３９】
0006053966.tif 000040
【００９０】
また、復号鍵ｋ＊ｒｋ生成部３３３は、処理装置により、属性集合Γに含まれる各整数ｔについて、復号鍵ｋ＊ｒｋｔ．ｎを数１４０に示すように生成する。
【数１４０】
0006053966.tif 000041
【００９１】
（Ｓ４０６：鍵送信ステップ）
再暗号化鍵送信部３４０は、属性集合Γと、アクセスストラクチャＳ’と、復号鍵ｋ＊ｒｋ０．ｎ，ｋ＊ｒｋｔ．ｎと、暗号文ｃｔ’ｎ＋１Ｓ’と、再暗号化回数ｎ（ここでは、（Ｓ４０２）で入力された値）とを要素とする再暗号化鍵ｒｋｎΓ，Ｓ’を、例えば通信装置によりネットワークを介して秘密裡に再暗号化装置４００へ送信する。もちろん、再暗号化鍵ｒｋｎΓ，Ｓ’は、他の方法により再暗号化装置４００へ送信されてもよい。
【００９２】
つまり、（Ｓ４０１）から（Ｓ４０５）において、復号装置３００は、数１４１に示すＲＫＧアルゴリズムを実行して、再暗号化鍵ｒｋｎΓ，Ｓ’を生成する。そして、（Ｓ４０６）で、復号装置３００は生成した再暗号化鍵ｒｋｎΓ，Ｓ’を再暗号化装置４００へ送信する。
【数１４１】
0006053966.tif 000042
【００９３】
再暗号化装置４００の機能と動作とについて説明する。
図９に示すように、再暗号化装置４００は、公開パラメータ受信部４１０、暗号文受信部４２０（暗号文取得部）、再暗号化鍵受信部４３０（再暗号化鍵取得部）、スパンプログラム計算部４４０、補間係数計算部４５０、ペアリング演算部４６０、再暗号文送信部４７０（再暗号文出力部）を備える。
【００９４】
図１５に基づき、ＲＥｎｃアルゴリズムの処理について説明する。
（Ｓ５０１：公開パラメータ受信ステップ）
公開パラメータ受信部４１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【００９５】
（Ｓ５０２：暗号文受信ステップ）
暗号文受信部４２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔｎＳを受信する。
【００９６】
（Ｓ５０３：再暗号化鍵受信ステップ）
再暗号化鍵受信部４３０は、例えば、通信装置によりネットワークを介して、復号装置３００から送信された再暗号化鍵ｒｋｎΓ，Ｓ’を受信する。
【００９７】
（Ｓ５０４：スパンプログラム計算ステップ）
スパンプログラム計算部４４０は、処理装置により、暗号文ｃｔｎＳに含まれるアクセスストラクチャＳが、再暗号化鍵ｒｋｎΓ，Ｓ’に含まれるΓを受理するか否かを判定する。アクセスストラクチャＳがΓを受理するか否かの判定方法は、実施の形態１における「第３．ＦＰＲＥを実現するための概念」で説明した通りである。
スパンプログラム計算部４４０は、アクセスストラクチャＳがΓを受理する場合（Ｓ５０４で受理）、処理を（Ｓ５０５）へ進める。一方、アクセスストラクチャＳがΓを拒絶する場合（Ｓ５０４で拒絶）、処理を終了する。
【００９８】
（Ｓ５０５：補間係数計算ステップ）
補間係数計算部４５０は、処理装置により、数１４２となるＩと、定数（補完係数）｛αｉ｝ｉ∈Ｉとを計算する。
【数１４２】
0006053966.tif 000043
【００９９】
（Ｓ５０６：ペアリング演算ステップ）
ペアリング演算部４６０は、処理装置により、数１４３を計算して、セッション鍵Ｋ’ｎを生成する。
【数１４３】
0006053966.tif 000044
【０１００】
（Ｓ５０７：再暗号文送信ステップ）
再暗号文送信部４７０は、セッション鍵Ｋ’ｎと、暗号文ｃＴ．ｎと、アクセスストラクチャＳ’と、暗号文ｃｔ’ｎ＋１Ｓ’と、再暗号化回数ｎ＋１（ここでは、（Ｓ５０２）で受信した暗号文ｃｔｎＳに含まれる再暗号化回数ｎ、あるいは、（Ｓ５０３）で受信した再暗号化鍵ｒｋｎΓ，Ｓ’に含まれる再暗号化回数ｎに１を加えた値）とを要素とする再暗号文ｃｔｎ＋１Ｓ’を、例えば通信装置によりネットワークを介して秘密裡に再暗号文復号装置５００へ送信する。もちろん、再暗号文ｃｔｎ＋１Ｓ’は、他の方法により再暗号文復号装置５００へ送信されてもよい。
【０１０１】
なお、ここでは、暗号化装置２００が出力した暗号文ｃｔｎＳ（ｃｔ０Ｓ）を再暗号化する場合を想定して説明した。しかし、再暗号化装置４００が出力した再暗号文ｃｔｎ＋１Ｓ’を、さらに再暗号化することも可能である。
この場合、（Ｓ５０２）で暗号文受信部４２０は、暗号化装置２００が出力した暗号文ｃｔｎＳに代えて、再暗号化装置４００が出力した再暗号文ｃｔｎ＋１Ｓ’を暗号文ｃｔｎＳとして取得する。なお、暗号文ｃｔｎ＋１Ｓ’には、アクセスストラクチャＳ’が要素として含まれているが、このアクセスストラクチャＳ’を便宜的にアクセスストラクチャＳと読み替える。また、暗号文ｃｔｎ＋１Ｓ’では、再暗号化回数がｎ＋１となっているが、この再暗号化回数を便宜的にｎと読み替える。
そして、（Ｓ５０７）で再暗号文送信部４７０は、上記要素に加え、（Ｓ５０２）で取得した暗号文ｃｔｎＳに含まれていた要素（セッション鍵｛Ｋ’ｊ｝ｊ＝１，．．．，ｎ、及び、暗号文｛ｃＴ．ｊ｝ｊ＝０，．．．，ｎ−１）を要素とする再暗号文ｃｔｎ＋１Ｓ’を再暗号文復号装置５００へ送信する。
他の処理は、上述した通りである。
【０１０２】
つまり、（Ｓ５０１）から（Ｓ５０６）において、再暗号化装置４００は、数１４４に示すＲＥｎｃアルゴリズムを実行して、再暗号文ｃｔｎ＋１Ｓ’を生成する。そして、（Ｓ５０７）で、再暗号化装置４００は生成した再暗号文ｃｔｎ＋１Ｓ’を再暗号文復号装置５００へ送信する。
【数１４４】
0006053966.tif 000045
【０１０３】
なお、（Ｓ５０２）で受信した暗号文ｃｔｎＳに含まれる再暗号化回数ｎと、（Ｓ５０３）で受信した再暗号化鍵ｒｋｎΓ，Ｓ’に含まれる再暗号化回数ｎとが不一致の場合、再暗号化することはできない。
【０１０４】
再暗号文復号装置５００の機能と動作とについて説明する。
図１０に示すように、再暗号文復号装置５００は、復号鍵受信部５１０、暗号文受信部５２０、スパンプログラム計算部５３０、補完係数計算部５４０、ペアリング演算部５５０、乱数計算部５６０、メッセージ計算部５７０を備える。
【０１０５】
図１６に基づき、Ｄｅｃ１アルゴリズムの処理について説明する。
（Ｓ６０１：復号鍵受信ステップ）
復号鍵受信部５１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信された復号鍵ｓｋΓ’を受信する。また、復号鍵受信部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【０１０６】
（Ｓ６０２：暗号文受信ステップ）
暗号文受信部５２０は、例えば、通信装置によりネットワークを介して、再暗号化装置４００が送信した再暗号文ｃｔｎＳ’を受信する。
なお、ＲＥｎｃアルゴリズムでは、再暗号文ｃｔｎ＋１Ｓ’を出力するとしていたが、ここでは、再暗号文ｃｔｎＳ’と表記を変更している。つまり、再暗号化鍵ｒｋｎΓ，Ｓ’（ ｒｋ０Γ，Ｓ’）で再暗号化回数０（ｎ＝０）の暗号文ｃｔｎＳ（ｃｔ０Ｓ）を再暗号化して再暗号文ｃｔｎ＋１Ｓ（ｃｔ０＋１Ｓ）を生成した場合、ここでは、この再暗号文ｃｔｎ＋１Ｓ（ｃｔ０＋１Ｓ）を再暗号文ｃｔｎＳ（ｃｔ１Ｓ）と表記している。
【０１０７】
（Ｓ６０３：スパンプログラム計算ステップ）
スパンプログラム計算部５３０は、処理装置により、再暗号文ｃｔｎＳ’に含まれるアクセスストラクチャＳ’が、復号鍵ｓｋΓ’に含まれるΓ’を受理するか否かを判定する。アクセスストラクチャＳ’がΓ’を受理するか否かの判定方法は、実施の形態１における「第３．ＦＰＲＥを実現するための概念」で説明した通りである。
スパンプログラム計算部５３０は、アクセスストラクチャＳ’がΓ’を受理する場合（Ｓ６０３で受理）、処理を（Ｓ６０４）へ進める。一方、アクセスストラクチャＳ’がΓ’を拒絶する場合（Ｓ６０３で拒絶）、処理を終了する。
【０１０８】
（Ｓ６０４：補完係数計算ステップ）
補完係数計算部５４０は、処理装置により、数１４５となるＩと、定数（補完係数）｛αｉ｝ｉ∈Ｉとを計算する。
【数１４５】
0006053966.tif 000046
【０１０９】
（Ｓ６０５：ペアリング演算ステップ）
ペアリング演算部５５０は、処理装置により、数１４６を計算して、セッション鍵Ｋ’ｎを生成する。
【数１４６】
0006053966.tif 000047
【０１１０】
（Ｓ６０６：乱数計算ステップ）
乱数計算部５６０は、処理装置により、数１４７を計算して、乱数ｒｎを生成する。
【数１４７】
0006053966.tif 000048
さらに、ｎが２以上の場合には、乱数計算部５６０は、処理装置により、ｊ＝ｎ−１，．．．，１の各整数ｊについて順に、数１４８を計算して、乱数ｒ１を生成する。
【数１４８】
0006053966.tif 000049
【０１１１】
（Ｓ６０７：メッセージ計算ステップ）
メッセージ計算部５７０は、処理装置により、ｍ＝ｃＴ．０／（Ｋ’０）ｒ１を計算して、メッセージｍを生成する。ここで、ｒ１は、乱数ｒ１のことを意味する。
【０１１２】
つまり、（Ｓ６０１）から（Ｓ６０７）において、再暗号文復号装置５００は、数１４９に示すＤｅｃ１アルゴリズムを実行して、メッセージｍを生成する。
【数１４９】
0006053966.tif 000050
【０１１３】
図１７に基づき、Ｄｅｃ２アルゴリズムの処理について説明する。
（Ｓ７０１：復号鍵受信ステップ）
復号鍵受信部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信された復号鍵ｓｋΓを受信する。また、復号鍵受信部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【０１１４】
（Ｓ７０２：暗号文受信ステップ）
暗号文受信部３５０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔｎＳ（ｃｔ０Ｓ）を受信する。
【０１１５】
（Ｓ７０３：スパンプログラム計算ステップ）
スパンプログラム計算部３６０は、処理装置により、暗号文ｃｔＳに含まれるアクセスストラクチャＳが、復号鍵ｓｋΓに含まれるΓを受理するか否かを判定する。アクセスストラクチャＳがΓを受理するか否かの判定方法は、実施の形態１における「第３．ＦＰＲＥを実現するための概念」で説明した通りである。
スパンプログラム計算部３６０は、アクセスストラクチャＳがΓを受理する場合（Ｓ７０３で受理）、処理を（Ｓ７０４）へ進める。一方、アクセスストラクチャＳがΓを拒絶する場合（Ｓ７０３で拒絶）、処理を終了する。
【０１１６】
（Ｓ７０４：補完係数計算ステップ）
補完係数計算部３７０は、処理装置により、数１５０となるＩと、定数（補完係数）｛αｉ｝ｉ∈Ｉとを計算する。
【数１５０】
0006053966.tif 000051
【０１１７】
（Ｓ７０５：ペアリング演算ステップ）
ペアリング演算部３８０は、処理装置により、数１５１を計算して、セッション鍵Ｋ０を生成する。
【数１５１】
0006053966.tif 000052
【０１１８】
（Ｓ７０６：メッセージ計算ステップ）
メッセージ計算部３９０は、処理装置により、ｍ＝ｃＴ．０／Ｋ０を計算して、メッセージｍを生成する。
【０１１９】
つまり、（Ｓ７０１）から（Ｓ７０６）において、復号装置３００は、数１５２に示すＤｅｃ２アルゴリズムを実行して、メッセージｍを生成する。
【数１５２】
0006053966.tif 000053
【０１２０】
以上のように、実施の形態１に係る暗号システム１０は、ＣＰ−ＦＰＲＥ方式を実現する。そのため、１つの再暗号化鍵で、様々な種類のユーザの集合に暗号文を転送することができるようになる。
【０１２１】
特に、実施の形態１に係る暗号システム１０では、１度の再暗号化により、暗号文のサイズが、定数サイズの要素分だけが増加する。そのため、ｎ回の再暗号化を実行しても、暗号文のサイズは、再暗号化の実行回数ｎに対して多項式倍の要素が増加するだけである。これは、従来ＦＰＲＥ方式に比べて非常に効率的であり、ＦＰＲＥ方式をより幅広く用いることが可能となる。
【０１２２】
なお、上記説明では、復号装置３００が再暗号化鍵生成装置を兼ねており、復号装置３００がＤｅｃ２アルゴリズムだけでなく、ＲＫＧアルゴリズムも実行するとした。しかし、再暗号文ｃｔｎＳ’をさらに再暗号化する場合の再暗号化鍵は、再暗号文復号装置５００が再暗号化鍵生成装置としてＲＫＧアルゴリズムを実行して生成する。したがって、この場合、復号装置３００が備える機能構成のうちＲＫＧアルゴリズムを実行するのに必要な機能構成を再暗号文復号装置５００も備える。
また、復号装置３００（や再暗号文復号装置５００）と、再暗号化鍵生成装置とを別の装置としてもよい。この場合、復号装置３００は、Ｄｅｃ２アルゴリズムを実行し、再暗号化鍵生成装置は、ＲＫＧアルゴリズムを実行する。したがって、この場合、復号装置３００は、Ｄｅｃ２アルゴリズムを実行するのに必要な機能構成を備え、再暗号化鍵生成装置は、ＲＫＧアルゴリズムを実行するのに必要な機能構成を備える。
【０１２３】
また、上記説明では、Ｎｔにｎｔ＋ｗｔ＋ｚｔ＋１を設定した。しかし、Ｎｔにｎｔ＋ｗｔ＋ｚｔ＋βｔを設定してもよい。ここで、βｔは０以上の整数である。
また、上記説明では、Ｎ０に５を設定した。しかし、Ｎ０に１＋１＋ｗ０＋ｚ０＋β０を設定してもよい。ここで、ｗ０，ｚ０，β０は０以上の整数である。
【０１２４】
実施の形態２．
実施の形態１で説明したＦＰＲＥ方式では、Ｓｅｔｕｐアルゴリズムにおいて、再暗号化回数の上限値を示す値Ｑを入力し、ｊ＝１，．．．，Ｑの各整数ｊについてそれぞれ異なる基底Ｂｔ．ｊ及び基底Ｂ＊ｔ．ｊを生成していた。そのため、再暗号化回数の上限値を大きくするほど、公開パラメータのサイズが大きくなり、暗号処理の効率が悪くなってしまった。
実施の形態２では、インデックス付けの技法を用いることにより、再暗号化回数の上限値をなくすとともに、再暗号化回数の上限値によらず公開パラメータのサイズを一定にしたＦＰＲＥ方式について説明する。
【０１２５】
実施の形態２では、実施の形態１と同じ部分については説明を省略し、実施の形態１と異なる部分について説明する。
【０１２６】
暗号システム１０の構成は、図５に示す実施の形態１に係る暗号システム１０の構成と同じである。但し、Ｓｅｔｕｐアルゴリズムにおいて、値Ｑを入力する必要はない。また、暗号システム１０を構成する各装置の構成は、図６から図１０に示す実施の形態１に係る各装置の構成と同じである。
【０１２７】
図１８は、Ｓｅｔｕｐアルゴリズムの処理を示すフローチャートである。他のアルゴリズムの処理の流れは、図１２から図１７に示す各アルゴリズムの処理の流れと同じである。ＲＥｎｃアルゴリズムとＤｅｃ２アルゴリズムとは、処理の内容も実施の形態１と同じである。
【０１２８】
図１８に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ８０１：正規直交基底生成ステップ）
マスター鍵生成部１１０は、処理装置により、数１５３を計算して、パラメータｐａｒａｍｎ→と、基底Ｂ０及び基底Ｂ＊０と、基底Ｂｔ及び基底Ｂ＊ｔとを生成する。
【数１５３】
0006053966.tif 000054
【０１２９】
（Ｓ８０２：公開パラメータ生成ステップ）
マスター鍵生成部１１０は、処理装置により、基底Ｂ０の部分基底Ｂ＾０と、基底Ｂｔの部分基底Ｂ＾ｔと、基底Ｂ＊０の部分基底Ｂ＾＊０と、基底Ｂ＊ｔの部分基底Ｂ＾＊ｔとを数１５４に示すように生成する。
【数１５４】
0006053966.tif 000055
マスター鍵生成部１１０は、セキュリティパラメータλと、ｐａｒａｍｎ→と、部分基底Ｂ＾０，Ｂ＾ｔ，Ｂ＾＊０，Ｂ＾＊ｔとを合わせて、公開パラメータｐｋとする。
【０１３０】
（Ｓ８０３：マスター鍵生成ステップ）
マスター鍵生成部１１０は、基底ベクトルｂ＊０．１をマスター鍵ｓｋとする。
【０１３１】
（Ｓ８０４：マスター鍵記憶ステップ）
マスター鍵記憶部１２０は、（Ｓ８０２）で生成した公開パラメータｐｋを記憶装置に記憶する。また、マスター鍵記憶部１２０は、（Ｓ８０３）で生成したマスター鍵ｓｋを記憶装置に記憶する。
【０１３２】
つまり、（Ｓ８０１）から（Ｓ８０３）において、鍵生成装置１００は、数１５５に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ８０４）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。
【数１５５】
0006053966.tif 000056
【０１３３】
図１２に基づき、ＫＧアルゴリズムの処理について説明する。
（Ｓ２０１）の処理は、実施の形態１と同じである。
【０１３４】
（Ｓ２０２：乱数生成ステップ）
乱数生成部１４１は、処理装置により、乱数を数１５６に示すように生成する。
【数１５６】
0006053966.tif 000057
【０１３５】
（Ｓ２０３：復号鍵ｋ＊生成ステップ）
復号鍵ｋ＊生成部１４２は、処理装置により、復号鍵ｋ＊０を数１５７に示すように生成する。
【数１５７】
0006053966.tif 000058
【０１３６】
また、復号鍵ｋ＊生成部１４２は、処理装置により、属性集合Γに含まれる各整数ｔについて、復号鍵ｋ＊ｔを数１５８に示すように生成する。
【数１５８】
0006053966.tif 000059
【０１３７】
（Ｓ２０４：鍵送信ステップ）
鍵送信部１５０は、属性集合Γと、復号鍵ｋ＊０，ｋ＊ｔとを要素とする復号鍵ｓｋΓを、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ送信する。
【０１３８】
つまり、（Ｓ２０１）から（Ｓ２０３）において、鍵生成装置１００は、数１５９に示すＫＧアルゴリズムを実行して、復号鍵ｓｋΓを生成する。そして、（Ｓ２０４）で、鍵生成装置１００は、復号鍵ｓｋΓを復号装置３００へ送信する。
【数１５９】
0006053966.tif 000060
【０１３９】
図１３に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ３０１）から（Ｓ３０４）と、（Ｓ３０７）との処理は、実施の形態１と同じである。
【０１４０】
（Ｓ３０５：乱数生成ステップ）
乱数生成部２３３は、処理装置により、乱数を数１６０に示すように生成する。
【数１６０】
0006053966.tif 000061
【０１４１】
（Ｓ３０６：暗号文ｃ生成ステップ）
暗号文ｃ生成部２３４は、処理装置により、暗号文ｃ０．ｎを数１６１に示すように生成する。
【数１６１】
0006053966.tif 000062
【０１４２】
また、暗号文ｃ生成部２３４は、ｉ＝１，．．．，Ｌの各整数ｉについて、暗号文ｃｉ．ｎを数１６２に示すように生成する。
【数１６２】
0006053966.tif 000063
【０１４３】
また、暗号文ｃ生成部２３４は、処理装置により、暗号文ｃＴ．ｎを数１６３に示すように生成する。
【数１６３】
0006053966.tif 000064
【０１４４】
つまり、（Ｓ３０１）から（Ｓ３０６）において、暗号化装置２００は、数１６４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｎＳを生成する。そして、（Ｓ３０７）で、暗号化装置２００は生成した暗号文ｃｔｎＳを復号装置３００へ送信する。
【数１６４】
0006053966.tif 000065
【０１４５】
図１４に基づき、ＲＫＧアルゴリズムの処理について説明する。
（Ｓ４０１）から（Ｓ４０２）と、（Ｓ４０４）と、（Ｓ４０６）との処理は、実施の形態１と同じである。
【０１４６】
（Ｓ４０３：乱数生成ステップ）
乱数生成部３３１は、処理装置により、乱数を数１６５に示すように生成する。
【数１６５】
0006053966.tif 000066
【０１４７】
（Ｓ４０５：復号鍵ｋ＊ｒｋ生成ステップ）
復号鍵ｋ＊ｒｋ生成部３３３は、処理装置により、復号鍵ｋ＊ｒｋ０．ｎを数１６６に示すように生成する。
【数１６６】
0006053966.tif 000067
【０１４８】
また、復号鍵ｋ＊ｒｋ生成部３３３は、属性集合Γに含まれる各整数ｔについて、復号鍵ｋ＊ｒｋｔ．ｎを数１６７に示すように生成する。
【数１６７】
0006053966.tif 000068
【０１４９】
つまり、（Ｓ４０１）から（Ｓ４０５）において、復号装置３００は、数１６８に示すＲＫＧアルゴリズムを実行して、再暗号化鍵ｒｋｎΓ，Ｓ’を生成する。そして、（Ｓ４０６）で、復号装置３００は生成した再暗号化鍵ｒｋｎΓ，Ｓ’を再暗号化装置４００へ送信する。
【数１６８】
0006053966.tif 000069
【０１５０】
図１６に基づき、Ｄｅｃ１アルゴリズムの処理について説明する。
（Ｓ６０１）から（Ｓ６０４）と、（Ｓ６０６）から（Ｓ６０７）との処理は、実施の形態１と同じである。
【０１５１】
（Ｓ６０５：ペアリング演算ステップ）
ペアリング演算部５５０は、処理装置により、数１６９を計算して、セッション鍵Ｋｎを生成する。
【数１６９】
0006053966.tif 000070
【０１５２】
つまり、（Ｓ６０１）から（Ｓ６０７）において、再暗号文復号装置５００は、数１７０に示すＤｅｃ１アルゴリズムを実行して、メッセージｍを生成する。
【数１７０】
0006053966.tif 000071
【０１５３】
以上のように、実施の形態２に係る暗号システム１０は、暗号文ｃｉ．０の先頭２つの基底ベクトルにインデックスμｎ（ｎ，−１）を設定し、復号鍵ｋ＊ｒｋｔ．ｎの先頭２つの基底ベクトルにインデックスσｎ（１，ｎ）を埋め込んだ。これにより、再暗号化する度に、異なる基底を用いず、同じ基底を用いて再暗号化することを可能にした。
その結果、再暗号化回数の上限値を設定する必要がなくなった。また、再暗号化回数の上限値によらず、公開パラメータのサイズを一定にすることができる。
【０１５４】
なお、インデックスを設定した部分については、内積した結果が０となればよい。そのため、上記説明では、先頭２つの基底ベクトルの２次元にインデックスを設定したが、これに限らず、３次元以上にインデックスを設定してもよい。また、インデックスとして設定する値についても上記説明のものに限らず、他の値であってもよい。
【０１５５】
実施の形態３．
実施の形態１では、ＣＰ−ＦＰＲＥ方式について説明した。実施の形態３では、鍵ポリシーのＦＰＲＥ方式（Ｋｅｙ−Ｐｏｌｉｃｙ  ＦＰＲＥ，ＫＰ−ＦＰＲＥ）方式について説明する。
【０１５６】
実施の形態３では、実施の形態１と同じ部分については説明を省略し、実施の形態１と異なる部分について説明する。
【０１５７】
まず、ＫＰ−ＦＰＲＥ方式の基本構成について説明する。次に、このＫＰ−ＦＰＲＥ方式を実現する暗号システム１０の基本構成について説明する。そして、この実施の形態に係るＫＰ−ＦＰＲＥ方式、及び、暗号システム１０について詳細に説明する。
【０１５８】
ＫＰ−ＦＰＲＥ方式の構成を簡単に説明する。なお、ＫＰ（鍵ポリシー）とは、鍵にＰｏｌｉｃｙが埋め込まれること、つまりアクセスストラクチャが埋め込まれることを意味する。
【０１５９】
＜第１−１．ＫＰ−ＦＰＲＥ方式の基本構成＞
ＫＰ−ＦＰＲＥ方式は、Ｓｅｔｕｐ、ＫＧ、Ｅｎｃ、ＲＫＧ、ＲＥｎｃ、Ｄｅｃ１、Ｄｅｃ２の７つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλと、属性のフォーマットｎ→：＝（ｄ；ｎ１，．．．，ｎｄ；ｗ１，．．．，ｗｄ；ｚ１，．．．，ｚｄ）と、再暗号化回数の上限値を示す値Ｑとを入力として、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫＧ）
ＫＧアルゴリズムは、アクセスストラクチャＳ＝（Ｍ，ρ）と、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、復号鍵ｓｋＳを出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、メッセージｍと、属性集合Γ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎｔ，１≦ｔ≦ｄ｝と、公開パラメータｐｋとを入力として、暗号文ｃｔｎΓを出力する確率的アルゴリズムである。
（ＲＫＧ）
ＲＫＧアルゴリズムは、復号鍵ｓｋＳと、属性集合Γ’：＝｛（ｔ，ｘ’→ｔ）｜ｘ’→ｔ∈Ｆｑｎｔ，１≦ｔ≦ｄ｝と、公開パラメータｐｋとを入力として、再暗号化鍵ｒｋｎＳ，Γ’を出力する確率的アルゴリズムである。
（ＲＥｎｃ）
ＲＥｎｃアルゴリズムは、暗号文ｃｔｎΓと、再暗号化鍵ｒｋｎＳ，Γ’と、公開パラメータｐｋとを入力として、再暗号文ｃｔｎ＋１Γ’を出力する確率的アルゴリズムである。
（Ｄｅｃ１）
Ｄｅｃ１アルゴリズムは、再暗号文ｃｔｎΓ’と、復号鍵ｓｋＳ’と、公開パラメータｐｋとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。
（Ｄｅｃ２）
Ｄｅｃ２アルゴリズムは、暗号文ｃｔｎΓ（ｃｔ０Γ）と、復号鍵ｓｋＳと、公開パラメータｐｋとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。
【０１６０】
＜第１−２．暗号システム１０＞
ＫＰ−ＦＰＲＥ方式のアルゴリズムを実行する暗号システム１０について説明する。
図１９は、ＫＰ−ＦＰＲＥ方式を実行する暗号システム１０の構成図である。
暗号システム１０は、図５に示す暗号システム１０と同様に、鍵生成装置１００、暗号化装置２００、復号装置３００（再暗号化鍵生成装置）、再暗号化装置４００、再暗号文復号装置５００（再暗号化鍵生成装置）を備える。
【０１６１】
鍵生成装置１００は、セキュリティパラメータλと、属性のフォーマットｎ→：＝（ｄ；ｎ１，．．．，ｎｄ；ｗ１，．．．，ｗｄ；ｚ１，．．．，ｚｄ）と、値Ｑを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。
そして、鍵生成装置１００は、公開パラメータｐｋを公開する。また、鍵生成装置１００は、アクセスストラクチャＳを入力としてＫＧアルゴリズムを実行して、復号鍵ｓｋＳを生成して復号装置３００へ秘密裏に送信する。また、鍵生成装置１００は、アクセスストラクチャＳ’を入力としてＫＧアルゴリズムを実行して、復号鍵ｓｋＳ’を生成して再暗号文復号装置５００へ秘密裏に送信する。
【０１６２】
暗号化装置２００は、メッセージｍと、属性集合Γと、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔｎΓを生成する。暗号化装置２００は、暗号文ｃｔｎΓを再暗号化装置４００へ送信する。
【０１６３】
復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋＳと、属性集合Γ’と、値ｎとを入力としてＲＫＧアルゴリズムを実行して、再暗号化鍵ｒｋｎＳ，Γ’を生成する。復号装置３００は、再暗号化鍵ｒｋｎＳ，Γ’を再暗号化装置４００に秘密裏に送信する。
また、復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋＳと、暗号文ｃｔｎΓ（ｃｔ０Γ）とを入力としてＤｅｃ２アルゴリズムを実行して、メッセージｍ又は識別情報⊥を出力する。
【０１６４】
再暗号化装置４００は、公開パラメータｐｋと、再暗号化鍵ｒｋｎＳ，Γ’と、暗号文ｃｔｎΓとを入力として、ＲＥｎｃアルゴリズムを実行して、再暗号文ｃｔｎ＋１Γ’を生成する。再暗号化装置４００は、再暗号文ｃｔｎ＋１Γ’を再暗号文復号装置５００へ送信する。
【０１６５】
再暗号文復号装置５００は、公開パラメータｐｋと、復号鍵ｓｋＳ’と、再暗号文ｒｃｔｎ＋１Γ’とを入力として、Ｄｅｃ１アルゴリズムを実行して、メッセージｍ又は識別情報⊥を出力する。
【０１６６】
＜第１−４．ＫＰ−ＦＰＲＥ方式及び暗号システム１０の詳細＞
図２０から図３０に基づき、ＫＰ−ＦＰＲＥ方式、及び、ＫＰ−ＦＰＲＥ方式を実行する暗号システム１０の機能と動作とについて説明する。
図２０は、鍵生成装置１００の機能を示す機能ブロック図である。図２１は、暗号化装置２００の機能を示す機能ブロック図である。図２２は、復号装置３００の機能を示す機能ブロック図である。図２３は、再暗号化装置４００の機能を示す機能ブロック図である。図２４は、再暗号文復号装置５００の機能を示す機能ブロック図である。
図２５は、鍵生成装置１００の動作を示すフローチャートであり、ＫＧアルゴリズムの処理を示すフローチャートである。図２６は、暗号化装置２００の動作を示すフローチャートであり、Ｅｎｃアルゴリズムの処理を示すフローチャートである。図２７は、復号装置３００の動作を示すフローチャートであり、ＲＫＧアルゴリズムの処理を示すフローチャートである。図２８は、再暗号化装置４００の動作を示すフローチャートであり、ＲＥｎｃアルゴリズムの処理を示すフローチャートである。図２９は、再暗号文復号装置５００の動作を示すフローチャートであり、Ｄｅｃ１アルゴリズムの処理を示すフローチャートである。図３０は、復号装置３００の動作を示すフローチャートであり、Ｄｅｃ２アルゴリズムの処理を示すフローチャートである。
【０１６７】
鍵生成装置１００の機能と動作とについて説明する。
図２０に示すように、鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵送信部１５０（鍵出力部）を備える。また、復号鍵生成部１４０は、乱数生成部１４１、復号鍵ｋ＊生成部１４２、ｆベクトル生成部１４３、ｓベクトル生成部１４４を備える。
【０１６８】
Ｓｅｔｕｐアルゴリズムの処理は、実施の形態１で説明したＳｅｔｕｐアルゴリズムの処理と基本的に同じであるため、説明を省略する。但し、基底Ｂ＾０、基底Ｂ＾ｔ、基底Ｂ＊＾０、基底Ｂ＊＾ｔに含める基底ベクトルが実施の形態１とは異なる。
【０１６９】
鍵生成装置１００は、数１７１に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。
【数１７１】
0006053966.tif 000072
【０１７０】
図２５に基づき、ＫＧアルゴリズムの処理について説明する。
（Ｓ９０１：情報入力ステップ）
情報入力部１３０は、入力装置により、アクセスストラクチャＳ：＝（Ｍ，ρ）を入力する。なお、アクセスストラクチャＳの行列Ｍは、実現したいシステムの条件に応じて設定されるものである。また、アクセスストラクチャＳのρは、例えば、復号鍵ｓｋＳの使用者の属性情報が設定されている。ここで、ρ（ｉ）＝（ｔ，ｖ→ｉ：＝（ｖｉ．１，．．．，ｖｉ．ｎｔ）∈Ｆｑｎｔ＼｛０→｝）（ｖｉ，ｎｔ≠０）である。
【０１７１】
（Ｓ９０２：ｆベクトル生成ステップ）
ｆベクトル生成部１４３は、処理装置により、ベクトルｆ→を数１７２に示すように生成する。
【数１７２】
0006053966.tif 000073
【０１７２】
（Ｓ９０３：ｓベクトル生成ステップ）
ｓベクトル生成部１４４は、処理装置により、ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔを数１７３に示すように生成する。
【数１７３】
0006053966.tif 000074
また、ｓベクトル生成部１４４は、処理装置により、値ｓ０を数１７４に示すように生成する。
【数１７４】
0006053966.tif 000075
【０１７３】
（Ｓ９０４：乱数生成ステップ）
乱数生成部１４１は、処理装置により、乱数を数１７５に示すように生成する。
【数１７５】
0006053966.tif 000076
【０１７４】
（Ｓ９０５：復号鍵ｋ＊生成ステップ）
復号鍵ｋ＊生成部１４２は、処理装置により、ｊ＝０，．．．，Ｑの各整数ｊについて、復号鍵ｋ＊０．ｊを数１７６に示すように生成する。
【数１７６】
0006053966.tif 000077
【０１７５】
また、復号鍵ｋ＊生成部１４２は、処理装置により、ｉ＝１，．．．，Ｌの各整数ｉとｊ＝０，．．．，Ｑの各整数ｊとについて、復号鍵ｋ＊ｉ．ｊを数１７７に示すように生成する。
【数１７７】
0006053966.tif 000078
【０１７６】
（Ｓ９０６：鍵送信ステップ）
鍵送信部１５０は、アクセスストラクチャＳと、復号鍵ｋ＊０．ｊ，ｋ＊ｉ．ｊとを要素とする復号鍵ｓｋＳを、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ送信する。もちろん、復号鍵ｓｋＳは、他の方法により復号装置３００へ送信されてもよい。
【０１７７】
つまり、（Ｓ９０１）から（Ｓ９０５）において、鍵生成装置１００は、数１７８に示すＫＧアルゴリズムを実行して、復号鍵ｓｋＳを生成する。そして、（Ｓ９０６）で、鍵生成装置１００は、生成した復号鍵ｓｋＳを復号装置３００へ送信する。
【数１７８】
0006053966.tif 000079
【０１７８】
なお、鍵生成装置１００は、（Ｓ９０１）において、復号鍵ｓｋＳ’の使用者の属性情報が設定されたアクセスストラクチャＳ’：＝（Ｍ’，ρ’）を入力して、ＫＧアルゴリズムを実行して、復号鍵ｓｋＳ’を生成する。そして、復号鍵ｓｋＳ’：＝（Ｓ’，ｋ’＊０，ｋ’＊ｉ）を再暗号文復号装置５００へ送信する。ここで、ρ’（ｉ）＝（ｔ，ｖ→’ｉ：＝（ｖ’ｉ．１，．．．，ｖ’ｉ．ｎｔ）∈Ｆｑｎｔ＼｛０→｝）（ｖ’ｉ，ｎｔ≠０）である。
【０１７９】
暗号化装置２００の機能と動作とについて説明する。
図２１に示すように、暗号化装置２００は、公開パラメータ受信部２１０、情報入力部２２０、暗号化部２３０、暗号文送信部２４０（暗号文出力部）を備える。また、暗号化部２３０は、乱数生成部２３３、暗号文ｃ生成部２３４を備える。
【０１８０】
図２６に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ１００１：公開パラメータ受信ステップ）
公開パラメータ受信部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【０１８１】
（Ｓ１００２：情報入力ステップ）
情報入力部２２０は、入力装置により、属性集合Γ：＝｛（ｔ，ｘ→ｔ：＝（ｘｔ．１，．．．，ｘｔ．ｎｔ∈Ｆｑｎｔ））｜１≦ｔ≦ｄ｝を入力する。なお、ｔは、１以上ｄ以下の全ての整数ではなく、１以上ｄ以下の少なくとも一部の整数であってもよい。また、属性集合Γは、例えば、復号可能なユーザの属性情報が設定されている。
また、情報入力部２２０は、入力装置により、復号装置３００へ送信するメッセージｍを入力する。
また、情報入力部２２０は、入力装置により、再暗号化回数ｎを入力する。ここで入力される再暗号化回数ｎは、通常であれば０となり、後述するＲＫＧアルゴリズムでＥｎｃアルゴリズムを呼び出した場合には、ＲＫＧアルゴリズムで指定された値となる。
【０１８２】
（Ｓ１００３：乱数生成ステップ）
乱数生成部２３３は、処理装置により、乱数を数１７９に示すように生成する。
【数１７９】
0006053966.tif 000080
【０１８３】
（Ｓ１００４：暗号文ｃ生成ステップ）
暗号文ｃ生成部２３４は、処理装置により、暗号文ｃ０．ｎを数１８０に示すように生成する。
【数１８０】
0006053966.tif 000081
【０１８４】
また、暗号文ｃ生成部２３４は、処理装置により、属性情報Γに含まれる各整数ｔについて、暗号文ｃｔ．ｎを数１８１に示すように生成する。
【数１８１】
0006053966.tif 000082
【０１８５】
また、暗号文ｃ生成部２３４は、処理装置により、暗号文ｃＴ．ｎを数１８２に示すように生成する。
【数１８２】
0006053966.tif 000083
【０１８６】
（Ｓ１００５：暗号文送信ステップ）
暗号文送信部２４０は、属性集合Γと、暗号文ｃ０．ｎ，ｃｔ．ｎ，ｃＴ．ｎとを要素とする暗号文ｃｔｎΓを、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｎΓは、他の方法により復号装置３００へ送信されてもよい。
【０１８７】
つまり、（Ｓ１００１）から（Ｓ１００４）において、暗号化装置２００は、数１８３に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｎΓを生成する。そして、（Ｓ１００５）で、暗号化装置２００は生成した暗号文ｃｔｎΓを復号装置３００へ送信する。
【数１８３】
0006053966.tif 000084
【０１８８】
復号装置３００の機能と動作とについて説明する。
図２２に示すように、復号装置３００は、復号鍵受信部３１０、情報入力部３２０、再暗号化鍵生成部３３０、再暗号化鍵送信部３４０（再暗号化鍵出力部）、暗号文受信部３５０、スパンプログラム計算部３６０、補完係数計算部３７０、ペアリング演算部３８０、メッセージ計算部３９０を備える。また、再暗号化鍵生成部３３０は、乱数生成部３３１、暗号化部３３２、復号鍵ｋ＊ｒｋ生成部３３３を備える。
【０１８９】
ここでは、図２７に基づき、ＲＫＧアルゴリズムの処理について説明する。Ｄｅｃ２アルゴリズムについては後述する。
【０１９０】
（Ｓ１１０１：復号鍵受信ステップ）
復号鍵受信部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信された復号鍵ｓｋＳを受信する。また、復号鍵受信部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【０１９１】
（Ｓ１１０２：情報入力ステップ）
情報入力部３２０は、入力装置により、属性集合Γ’：＝｛（ｔ，ｘ’→ｔ：＝（ｘ’ｔ．１，．．．，ｘ’ｔ．ｎｔ∈Ｆｑｎｔ＼｛０→｝））｜１≦ｔ≦ｄ｝を入力する。なお、ｔは、１以上ｄ以下の全ての整数ではなく、１以上ｄ以下の少なくとも一部の整数であってもよい。また、属性集合Γ’は、例えば、再暗号文ｃｔｎ＋１Γ’を復号可能なユーザの属性情報が設定されている。
また、情報入力部３２０は、入力装置により、再暗号化回数ｎを入力する。ここで入力される再暗号化回数ｎは、何回再暗号化された暗号文を再暗号化するための再暗号化鍵を生成するかを示す。
【０１９２】
（Ｓ１１０３：乱数生成ステップ）
乱数生成部３３１は、処理装置により、乱数を数１８４に示すように生成する。
【数１８４】
0006053966.tif 000085
【０１９３】
（Ｓ１１０４：乱数暗号化ステップ）
暗号化部３３２は、処理装置により、乱数ｒｎ＋１（変換情報）を数１８５に示すように暗号化して、暗号文ｃｔ’ｎ＋１Γ’を生成する。ここで、関数Ｅｎ＋１はＦｑからＧＴ．ｎ＋１へのエンコード関数である。
【数１８５】
0006053966.tif 000086
【０１９４】
（Ｓ１１０５：復号鍵ｋ＊ｒｋ生成ステップ）
復号鍵ｋ＊ｒｋ生成部３３３は、処理装置により、復号鍵ｋ＊ｒｋ０．ｎを数１８６に示すように生成する。
【数１８６】
0006053966.tif 000087
【０１９５】
また、復号鍵ｋ＊ｒｋ生成部３３３は、処理装置により、ｉ＝１，．．．，Ｌの各整数ｉについて、復号鍵ｋ＊ｒｋｉ．ｎを数１８７に示すように生成する。
【数１８７】
0006053966.tif 000088
【０１９６】
（Ｓ１１０６：鍵送信ステップ）
再暗号化鍵送信部３４０は、アクセスストラクチャＳと、属性集合Γ’と、復号鍵ｋ＊ｒｋ０．ｎ，ｋ＊ｒｋｉ．ｎと、暗号文ｃｔ’ｎ＋１Γ’と、再暗号化回数ｎ（ここでは、（Ｓ１１０２）で入力された値）とを要素とする再暗号化鍵ｒｋｎＳ，Γ’を、例えば通信装置によりネットワークを介して秘密裡に再暗号化装置４００へ送信する。もちろん、再暗号化鍵ｒｋｎＳ，Γ’は、他の方法により再暗号化装置４００へ送信されてもよい。
【０１９７】
つまり、（Ｓ１１０１）から（Ｓ１１０５）において、復号装置３００は、数１８８に示すＲＫＧアルゴリズムを実行して、再暗号化鍵ｒｋｎＳ，Γ’を生成する。そして、（Ｓ１１０６）で、復号装置３００は生成した再暗号化鍵ｒｋｎＳ，Γ’を再暗号化装置４００へ送信する。
【数１８８】
0006053966.tif 000089
【０１９８】
再暗号化装置４００の機能と動作とについて説明する。
図２３に示すように、再暗号化装置４００は、公開パラメータ受信部４１０、暗号文受信部４２０、再暗号化鍵受信部４３０、スパンプログラム計算部４４０、補間係数計算部４５０、ペアリング演算部４６０、再暗号文送信部４７０（再暗号文出力部）を備える。
【０１９９】
図２８に基づき、ＲＥｎｃアルゴリズムの処理について説明する。
（Ｓ１２０１：公開パラメータ受信ステップ）
公開パラメータ受信部４１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【０２００】
（Ｓ１２０２：暗号文受信ステップ）
暗号文受信部４２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔｎΓ（ｃｔ０Γ）を受信する。
【０２０１】
（Ｓ１２０３：再暗号化鍵受信ステップ）
再暗号化鍵受信部４３０は、例えば、通信装置によりネットワークを介して、復号装置３００から送信された再暗号化鍵ｒｋｎＳ，Γ’を受信する。
【０２０２】
（Ｓ１２０４：スパンプログラム計算ステップ）
スパンプログラム計算部４４０は、処理装置により、再暗号化鍵ｒｋｎＳ，Γ’に含まれるアクセスストラクチャＳが、暗号文ｃｔｎΓに含まれるΓを受理するか否かを判定する。アクセスストラクチャＳがΓを受理するか否かの判定方法は、実施の形態１における「第３．ＦＰＲＥを実現するための概念」で説明した通りである。
スパンプログラム計算部４４０は、アクセスストラクチャＳがΓを受理する場合（Ｓ１２０４で受理）、処理を（Ｓ１２０５）へ進める。一方、アクセスストラクチャＳがΓを拒絶する場合（Ｓ１２０４で拒絶）、処理を終了する。
【０２０３】
（Ｓ１２０５：補間係数計算ステップ）
補間係数計算部４５０は、処理装置により、数１８９となるＩと、定数（補完係数）｛αｉ｝ｉ∈Ｉとを計算する。
【数１８９】
0006053966.tif 000090
【０２０４】
（Ｓ１２０６：ペアリング演算ステップ）
ペアリング演算部４６０は、処理装置により、数１９０を計算して、セッション鍵Ｋ’ｎを生成する。
【数１９０】
0006053966.tif 000091
【０２０５】
（Ｓ１２０７：再暗号文送信ステップ）
再暗号文送信部４７０は、セッション鍵Ｋ’ｎと、暗号文ｃＴ．ｎと、属性集合Γ’と、暗号文ｃｔ’ｎ＋１Γ’と、再暗号化回数ｎ＋１（ここでは、（Ｓ１２０２）で受信した暗号文ｃｔｎΓに含まれる再暗号化回数ｎ、あるいは、（Ｓ１２０３）で受信した再暗号化鍵ｒｋｎＳ，Γ’に含まれる再暗号化回数ｎに１を加えた値）とを要素とする再暗号文ｃｔｎ＋１Γ’を、例えば通信装置によりネットワークを介して秘密裡に再暗号文復号装置５００へ送信する。もちろん、再暗号文ｃｔｎ＋１Γ’は、他の方法により再暗号文復号装置５００へ送信されてもよい。
【０２０６】
なお、ここでは、暗号化装置２００が出力した暗号文ｃｔｎΓを再暗号化する場合を想定して説明した。しかし、再暗号化装置４００が出力した再暗号文ｃｔｎ＋１Γ’を、さらに再暗号化することも可能である。
この場合、（Ｓ１２０２）で暗号文受信部４２０は、暗号化装置２００が出力した暗号文ｃｔ０Γに代えて、再暗号化装置４００が出力した再暗号文ｃｔｎ＋１Γ’を暗号文ｃｔｎΓとして取得する。なお、暗号文ｃｔｎ＋１Γ’には、属性集合Γ’が要素として含まれているが、この属性集合Γ’を便宜的に属性集合Γと読み替える。また、暗号文ｃｔｎ＋１Γ’では、再暗号化回数がｎ＋１となっているが、この再暗号化回数を便宜的にｎと読み替える。
そして、（Ｓ１２０７）で再暗号文送信部４７０は、上記要素に加え、（Ｓ１２０２）で取得した暗号文ｃｔｎΓに含まれていた要素（セッション鍵｛Ｋ’ｊ｝ｊ＝１，．．．，ｎ、及び、暗号文｛ｃＴ．ｊ｝ｊ＝０，．．．，ｎ−１）を要素とする再暗号文ｃｔｎ＋１Γ’を再暗号文復号装置５００へ送信する。
他の処理は、上述した通りである。
【０２０７】
つまり、（Ｓ１２０１）から（Ｓ１２０６）において、再暗号化装置４００は、数１９１に示すＲＥｎｃアルゴリズムを実行して、再暗号文ｃｔｎ＋１Γ’を生成する。そして、（Ｓ１２０７）で、再暗号化装置４００は生成した再暗号文ｃｔｎ＋１Γ’を再暗号文復号装置５００へ送信する。
【数１９１】
0006053966.tif 000092
【０２０８】
なお、（Ｓ１２０２）で受信した暗号文ｃｔｎΓに含まれる再暗号化回数ｎと、（Ｓ１２０３）で受信した再暗号化鍵ｒｋｎＳ，Γ’に含まれる再暗号化回数ｎとが不一致の場合、再暗号化することはできない。
【０２０９】
再暗号文復号装置５００の機能と動作とについて説明する。
図２４に示すように、再暗号文復号装置５００は、復号鍵受信部５１０、暗号文受信部５２０、スパンプログラム計算部５３０、補完係数計算部５４０、ペアリング演算部５５０、乱数計算部５６０、メッセージ計算部５７０を備える。
【０２１０】
図２９に基づき、Ｄｅｃ１アルゴリズムの処理について説明する。
（Ｓ１３０１：復号鍵受信ステップ）
復号鍵受信部５１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信された復号鍵ｓｋＳ’を受信する。また、復号鍵受信部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【０２１１】
（Ｓ１３０２：暗号文受信ステップ）
暗号文受信部５２０は、例えば、通信装置によりネットワークを介して、再暗号化装置４００が送信した再暗号文ｃｔｎΓ’を受信する。
なお、ＲＥｎｃアルゴリズムでは、再暗号文ｃｔｎ＋１Γ’を出力するとしていたが、ここでは、再暗号文ｃｔｎΓ’と表記を変更している。
【０２１２】
（Ｓ１３０３：スパンプログラム計算ステップ）
スパンプログラム計算部５３０は、処理装置により、復号鍵ｓｋＳ’に含まれるアクセスストラクチャＳ’が、再暗号文ｃｔｎΓ’に含まれるΓ’を受理するか否かを判定する。アクセスストラクチャＳ’がΓ’を受理するか否かの判定方法は、実施の形態１における「第３．ＦＰＲＥを実現するための概念」で説明した通りである。
スパンプログラム計算部５３０は、アクセスストラクチャＳ’がΓ’を受理する場合（Ｓ１３０３で受理）、処理を（Ｓ１３０４）へ進める。一方、アクセスストラクチャＳ’がΓ’を拒絶する場合（Ｓ１３０３で拒絶）、処理を終了する。
【０２１３】
（Ｓ１３０４：補完係数計算ステップ）
補完係数計算部５４０は、処理装置により、数１９２となるＩと、定数（補完係数）｛αｉ｝ｉ∈Ｉとを計算する。
【数１９２】
0006053966.tif 000093
【０２１４】
（Ｓ１３０５：ペアリング演算ステップ）
ペアリング演算部５５０は、処理装置により、数１９３を計算して、セッション鍵Ｋ’ｎを生成する。
【数１９３】
0006053966.tif 000094
【０２１５】
（Ｓ１３０６）から（Ｓ１３０７）の処理は、図１６に示す実施の形態１の（Ｓ６０６）から（Ｓ６０７）の処理と同じである。
【０２１６】
つまり、（Ｓ１３０１）から（Ｓ１３０７）において、再暗号文復号装置５００は、数１９４に示すＤｅｃ１アルゴリズムを実行して、メッセージｍを生成する。
【数１９４】
0006053966.tif 000095
【０２１７】
図３０に基づき、Ｄｅｃ２アルゴリズムの処理について説明する。
（Ｓ１４０１：復号鍵受信ステップ）
復号鍵受信部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信された復号鍵ｓｋＳを受信する。また、復号鍵受信部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを受信する。
【０２１８】
（Ｓ１４０２：暗号文受信ステップ）
暗号文受信部３５０は、例えば、通信装置によりネットワークを介して、再暗号化装置４００が送信した暗号文ｃｔ０Γを受信する。
【０２１９】
（Ｓ１４０３：スパンプログラム計算ステップ）
スパンプログラム計算部３６０は、処理装置により、復号鍵ｓｋＳに含まれるアクセスストラクチャＳが、暗号文ｃｔΓに含まれるΓを受理するか否かを判定する。アクセスストラクチャＳがΓを受理するか否かの判定方法は、実施の形態１における「第３．ＦＰＲＥを実現するための概念」で説明した通りである。
スパンプログラム計算部３６０は、アクセスストラクチャＳがΓを受理する場合（Ｓ１４０３で受理）、処理を（Ｓ１４０４）へ進める。一方、アクセスストラクチャＳがΓを拒絶する場合（Ｓ１４０３で拒絶）、処理を終了する。
【０２２０】
（Ｓ１４０４：補完係数計算ステップ）
補完係数計算部３７０は、処理装置により、数１９５となるＩと、定数（補完係数）｛αｉ｝ｉ∈Ｉとを計算する。
【数１９５】
0006053966.tif 000096
【０２２１】
（Ｓ１４０５：ペアリング演算ステップ）
ペアリング演算部３８０は、処理装置により、数１９６を計算して、セッション鍵Ｋ０を生成する。
【数１９６】
0006053966.tif 000097
【０２２２】
（Ｓ１４０６：メッセージ計算ステップ）
メッセージ計算部３９０は、処理装置により、ｍ＝ｃＴ．０／Ｋ０を計算して、メッセージｍを生成する。
【０２２３】
つまり、（Ｓ１４０１）から（Ｓ１４０６）において、復号装置３００は、数１９７に示すＤｅｃ２アルゴリズムを実行して、メッセージｍを生成する。
【数１９７】
0006053966.tif 000098
【０２２４】
以上のように、実施の形態３に係る暗号システム１０は、ＫＰ−ＦＰＲＥ方式を実現する。そのため、１つの再暗号化鍵で、様々な種類のユーザの集合に暗号文を転送することができるようになる。
【０２２５】
なお、実施の形態２では、実施の形態１で説明したＣＰ−ＦＰＲＥ方式に対して、インデックス付けの技法を用いた方式について説明した。そして、実施の形態２では、再暗号化回数の上限値をなくすとともに、再暗号化回数の上限値によらず公開パラメータのサイズを一定にしたＣＰ−ＦＰＲＥ方式を実現した。
同様に、実施の形態３で説明したＫＰ−ＦＰＲＥ方式に対しても、数１９８から数２０１に示すように、インデックス付けの技法を用いることができる。なお、ＲＫＧアルゴリズムとＲＥｎｃアルゴリズムとＤｅｃ２アルゴリズムとは、処理の内容も上述したＫＰ−ＦＰＲＥ方式と同じである。
これにより、再暗号化回数の上限値をなくすとともに、再暗号化回数の上限値によらず公開パラメータのサイズを一定にしたＫＰ−ＦＰＲＥ方式を実現できる。
【数１９８】
0006053966.tif 000099
【数１９９】
0006053966.tif 000100
【数２００】
0006053966.tif 000101
【数２０１】
0006053966.tif 000102
【０２２６】
実施の形態４．
以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。実施の形態４では、双対加群において暗号処理を実現する方法について説明する。
【０２２７】
つまり、以上の実施の形態では、素数位数ｑの巡回群において暗号処理を実現した。しかし、合成数Ｍを用いて数２０２のように環Ｒを表した場合、環Ｒを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数２０２】
0006053966.tif 000103
【０２２８】
以上の実施の形態で説明したアルゴリズムにおけるＦｑをＲに変更すれば、双対加群における暗号処理を実現することができる。
【０２２９】
なお、以上の実施の形態では、ＦＥによりメッセージを暗号化して宛先へ送信する場合を想定して、再暗号化装置４００が暗号文を再暗号化して、暗号文の宛先を変更することについて説明した。
ＦＥは、メッセージを暗号化して宛先へ送信する機能だけでなく、暗号文を復号することなく検索可能にする検索可能暗号を実現することも可能である。ＦＥにより検索可能暗号を実現した場合に、以上の実施の形態で説明したアルゴリズムにより、設定された検索キーワードを変更することが可能である。
以上の実施の形態では、暗号文に設定する属性情報が復号可能なユーザを指定していた。そして、属性情報を変更することにより、暗号文の宛先を変更した。ＦＥにより検索可能暗号を実現する場合、暗号文に設定する属性情報の一部が、検索可能なユーザを指定し、残りの属性情報の一部が、検索キーワードを指定する。そこで、以上の実施の形態で説明したアルゴリズムを利用して、属性情報のうち、検索キーワードを指定した部分を変更することにより、設定された検索キーワードを変更することが可能である。
【０２３０】
また、以上の実施の形態では、１台の鍵生成装置１００が復号鍵を生成するとした。しかし、以上の実施の形態のアルゴリズムを、非特許文献５に記載された分散多管理者の方式と組み合わせて、複数の鍵生成装置１００により１つの復号鍵が生成されるようにすることも可能である。
【０２３１】
また、以上の実施の形態では、属性のカテゴリを追加する場合（属性のフォーマットｎ→におけるｄの値を増やす場合）、公開パラメータを再発行する必要があった。しかし、以上の実施の形態のアルゴリズムを、非特許文献６に記載されたＵｎｂｏｕｎｄｅｄの方式と組み合わせて、公開パラメータを再発行することなく、属性のカテゴリを追加できるようにすることも可能である。
【０２３２】
また、以上の実施の形態では、内積暗号に用いるベクトルの長さをＮとすると、公開パラメータやマスター秘密鍵のサイズはＮ２に比例し、ユーザへ与える復号鍵の生成や暗号化の処理にＮ２に比例する時間がかかる。しかし、以上の実施の形態のアルゴリズムを、非特許文献７に記載された方式と組み合わせて、公開パラメータやマスター秘密鍵のサイズを小さくするとともに、ユーザへ与える復号鍵の生成の処理や暗号化の処理にかかる時間を短くすることも可能である。
【０２３３】
また、以上の実施の形態では、鍵や暗号文を送信先の装置へ送信するとした。しかし、これに代えて、鍵や暗号文をＣＤやＤＶＤ等の記憶媒体に出力して、送信先の装置が記憶媒体を読み込むようにしてもよい。したがって、送信を出力、受信を取得と読み替えてもよい。
【０２３４】
なお、以上の実施の形態において、安全性の証明の観点から、ｉ＝１，．．．，Ｌの各整数ｉについてのρ（ｉ）は、それぞれ異なる識別情報ｔについての肯定形の組（ｔ，ｖ→）又は否定形の組¬（ｔ，ｖ→）であると限定してもよい。
言い替えると、ρ（ｉ）＝（ｔ，ｖ→）又はρ（ｉ）＝¬（ｔ，ｖ→）である場合に、関数ρ~を、ρ~（ｉ）＝ｔである｛１，．．．，Ｌ｝→｛１，．．．ｄ｝の写像であるとする。この場合、ρ~が単射であると限定してもよい。なお、ρ（ｉ）は、上述したアクセスストラクチャＳ：＝（Ｍ，ρ（ｉ））のρ（ｉ）である。
【０２３５】
図３１は、実施の形態１〜４に示した暗号システム１０の各装置（鍵生成装置１００、暗号化装置２００、復号装置３００、再暗号化装置４００、再暗号文復号装置５００）のハードウェア構成の例を示す図である。
暗号システム１０の各装置はコンピュータであり、暗号システム１０の各装置の各要素をプログラムで実現することができる。
暗号システム１０の各装置のハードウェア構成としては、バスに、演算装置９０１、外部記憶装置９０２、主記憶装置９０３、通信装置９０４、入出力装置９０５が接続されている。
【０２３６】
演算装置９０１は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等である。外部記憶装置９０２は、例えばＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やフラッシュメモリ、ハードディスク装置等である。主記憶装置９０３は、例えばＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等である。通信装置９０４は、例えば通信ボード等である。入出力装置９０５は、例えばマウス、キーボード、ディスプレイ装置等である。
【０２３７】
プログラムは、通常は外部記憶装置９０２に記憶されており、主記憶装置９０３にロードされた状態で、順次演算装置９０１に読み込まれ、実行される。
プログラムは、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵送信部１５０、公開パラメータ受信部２１０、情報入力部２２０、暗号化部２３０、暗号文送信部２４０、復号鍵受信部３１０、情報入力部３２０、再暗号化鍵生成部３３０、再暗号化鍵送信部３４０、暗号文受信部３５０、スパンプログラム計算部３６０、補完係数計算部３７０、ペアリング演算部３８０、メッセージ計算部３９０、公開パラメータ受信部４１０、暗号文受信部４２０、再暗号化鍵受信部４３０、スパンプログラム計算部４４０、補間係数計算部４５０、ペアリング演算部４６０、再暗号文送信部４７０、復号鍵受信部５１０、暗号文受信部５２０、スパンプログラム計算部５３０、補完係数計算部５４０、ペアリング演算部５５０、乱数計算部５６０、メッセージ計算部５７０として説明している機能を実現するプログラムである。
更に、外部記憶装置９０２にはオペレーティングシステム（ＯＳ）も記憶されており、ＯＳの少なくとも一部が主記憶装置９０３にロードされ、演算装置９０１はＯＳを実行しながら、上記プログラムを実行する。
また、実施の形態１〜５の説明において、「公開パラメータｐｋ」、「マスター秘密鍵ｓｋ」、「復号鍵ｓｋＳ，ｓｋΓ」、「暗号文ｃｔｎΓ，ｃｔｎＳ」、「再暗号化鍵ｒｋｎΓ，Ｓ’，ｒｋｎＳ，Γ’」、「再暗号文ｃｔｎＳ’，ｃｔｎΓ’」、「アクセスストラクチャＳ，Ｓ’」、「属性集合Γ，Γ」、「メッセージｍ」等として説明している情報やデータや信号値や変数値が主記憶装置９０３にファイルとして記憶されている。
【０２３８】
なお、図３１の構成は、あくまでも暗号システム１０の各装置のハードウェア構成の一例を示すものであり、暗号システム１０の各装置のハードウェア構成は図３１に記載の構成に限らず、他の構成であってもよい。
【符号の説明】
【０２３９】
１０  暗号システム、１００  鍵生成装置、１１０  マスター鍵生成部、１２０  マスター鍵記憶部、１３０  情報入力部、１４０  復号鍵生成部、１４１  乱数生成部、１４２  復号鍵ｋ＊生成部、１４３  ｆベクトル生成部、１４４  ｓベクトル生成部、１５０  鍵送信部、２００  暗号化装置、２１０  公開パラメータ受信部、２２０  情報入力部、２３０  暗号化部、２３１  ｆベクトル生成部、２３２  ｓベクトル生成部、２３３  乱数生成部、２３４  暗号文ｃ生成部、２４０  暗号文送信部、３００  復号装置、３１０  復号鍵受信部、３２０  情報入力部、３３０  再暗号化鍵生成部、３３１  乱数生成部、３３２  暗号化部、３３３  復号鍵ｋ＊ｒｋ生成部、３４０  再暗号化鍵送信部、３５０  暗号文受信部、３６０  スパンプログラム計算部、３７０  補完係数計算部、３８０  ペアリング演算部、３９０  メッセージ計算部、４００  再暗号化装置、４１０  公開パラメータ受信部、４２０  暗号文受信部、４３０  再暗号化鍵受信部、４４０  スパンプログラム計算部、４５０  補間係数計算部、４６０  ペアリング演算部、４７０  再暗号文送信部、５００  再暗号文復号装置、５１０  復号鍵受信部、５２０  暗号文受信部、５３０  スパンプログラム計算部、５４０  補完係数計算部、５５０  ペアリング演算部、５６０  乱数計算部、５７０  メッセージ計算部。
【図１】
0006053966.tif 000124
【図２】
0006053966.tif 000125
【図３】
0006053966.tif 000126
【図４】
0006053966.tif 000127
【図５】
0006053966.tif 000128
【図６】
0006053966.tif 000129
【図７】
0006053966.tif 000130
【図８】
0006053966.tif 000131
【図９】
0006053966.tif 000132
【図１０】
0006053966.tif 000133
【図１１】
0006053966.tif 000134
【図１２】
0006053966.tif 000135
【図１３】
0006053966.tif 000136
【図１４】
0006053966.tif 000137
【図１５】
0006053966.tif 000138
【図１６】
0006053966.tif 000139
【図１７】
0006053966.tif 000140
【図１８】
0006053966.tif 000141
【図１９】
0006053966.tif 000142
【図２０】
0006053966.tif 000143
【図２１】
0006053966.tif 000144
【図２２】
0006053966.tif 000145
【図２３】
0006053966.tif 000146
【図２４】
0006053966.tif 000147
【図２５】
0006053966.tif 000148
【図２６】
0006053966.tif 000149
【図２７】
0006053966.tif 000150
【図２８】
0006053966.tif 000151
【図２９】
0006053966.tif 000152
【図３０】
0006053966.tif 000153
【図３１】
0006053966.tif 000154