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