(57)【要約】【課題】パラメータΦが設定された暗号化鍵ｅｋをパラメータΨが設定された復号鍵ｄｋで復号する場合に、関係Ｒ（Φ，Ψ）が成立する場合に限り、復号鍵ｄｋは暗号化鍵ｅｋで暗号化された暗号文を復号することができる関数型暗号方式において、関係Ｒとして表現できる範囲を広くすることを目的とする。【解決手段】暗号システム１０は、多項式ｄ（ｘ）と複数の多項式Ｄｉ（ｘ）と述語情報とを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文とし、他方を復号鍵とする。復号装置３００は、述語情報と属性情報とに基づき、複数の多項式Ｄｉ（ｘ）から少なくとも一部の多項式Ｄｉ（ｘ）を選択し、選択した多項式Ｄｉ（ｘ）に係数Δｉを掛けた多項式ΔｉＤｉ（ｘ）に基づき構成される多項式を、多項式ｄ（ｘ）で割り切れるようにする係数Δｉを計算する。復号装置３００は、計算した係数Δｉに基づき、前記暗号文を復号する。【選択図】図３
2014029415.tif 000002
【特許請求の範囲】
【請求項１】
２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文として生成する暗号化装置と、
前記第１情報と前記第２情報とのうちの他方を復号鍵とし、前記２次スパンプログラムが前記属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号装置と
を備えることを特徴とする暗号システム。
【請求項２】
前記第１情報は、前記２次スパンプログラムとして、多項式ｄ（ｘ）と複数の多項式Ｄｉ（ｘ）と述語情報とを含み、
前記復号装置は、
前記第１情報に含まれる述語情報と、前記第２情報に含まれる属性情報とに基づき、前記複数の多項式Ｄｉ（ｘ）から少なくとも一部の多項式Ｄｉ（ｘ）を選択する多項式選択部と、
前記多項式選択部が選択した多項式Ｄｉ（ｘ）に係数Δｉを掛けた多項式ΔｉＤｉ（ｘ）に基づき構成される多項式を、前記多項式ｄ（ｘ）で割り切れるようにする係数Δｉを計算する係数計算部と、
前記係数計算部が計算した係数Δｉに基づき、前記暗号文を復号する復号部と
を備えることを特徴とする請求項１に記載の暗号システム。
【請求項３】
前記複数の多項式Ｄｉ（ｘ）は、ｉ＝０，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての多項式ａｉ（ｘ）及び多項式ｂｉ（ｘ）であり、
前記多項式選択部は、前記属性情報と前記述語情報とに基づき、ｉ＝１，．．．，Ｌのうち一部の整数ｉの集合Ｉを選択することにより、多項式ａ０（ｘ）及び多項式ｂ０（ｘ）と、前記集合Ｉに含まれる整数ｉについての多項式ａｉ（ｘ）及び多項式ｂｉ（ｘ）とを選択し、
前記係数計算部は、（ａ０（ｘ）＋Σｉ∈Ｉαｉａｉ（ｘ））・（ｂ０（ｘ）＋Σｉ∈Ｉβｉｂｉ（ｘ））を前記多項式ｄ（ｘ）で割り切れるようにする係数αｉ及び係数βｉを前記係数Δｉとして計算する
ことを特徴とする請求項２に記載の暗号システム。
【請求項４】
前記多項式ｄ（ｘ）は、τ＝１，．．．，ｍ（ｍは１以上の整数）の多項式ｄτ（ｘ）ｆτに因数分解され、
前記係数計算部は、Πτ＝１ｍｄτ（ｘ）κτが（ａ０（ｘ）＋Σｉ∈Ｉαｉａｉ（ｘ））を割り切るようにするとともに、Πτ＝１ｍｄτ（ｘ）ｆτ−κτが（ｂ０（ｘ）＋Σｉ∈Ｉβｉｂｉ（ｘ））を割り切るようにする係数αｉ及び係数βｉと、次数κτとを計算し、
前記復号部は、前記係数αｉ及び前記係数βｉと、前記次数κτとに基づき、前記暗号文を復号する
ことを特徴とする請求項３に記載の暗号システム。
【請求項５】
前記属性情報は、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の少なくとも一部の整数ｔについての属性ベクトルｘ→ｔを含み、
前記述語情報は、ｉ＝１，．．．，Ｌの各整数ｉについての識別子ｔと述語ベクトルｖ→ｉとの組（ｔ，ｖ→ｉ）を含み、
前記多項式選択部は、ｉ＝１，．．．，Ｌの各整数ｉについての前記組（ｔ，ｖ→ｉ）について、その組の述語ベクトルｖ→ｉとその組の識別情報ｔについての属性ベクトルｘ→ｔとの内積が０となるか否かにより、整数ｉを前記集合Ｉに含めるか否かを判定する
ことを特徴とする請求項３又は４に記載の暗号システム。
【請求項６】
前記組（ｔ，ｖ→ｉ）は、肯定形と否定形とのいずれかに対応付けられており、
前記多項式選択部は、前記組（ｔ，ｖ→ｉ）が肯定形に対応付けられている場合、前記内積が０となるなら、整数ｉを前記集合Ｉに含め、前記組（ｔ，ｖ→ｉ）が否定形に対応付けられている場合、前記内積が０とならないなら、整数ｉを前記集合Ｉに含める
ことを特徴とする請求項５に記載の暗号システム。
【請求項７】
前記多項式ｄ（ｘ）は、τ＝１，．．．，ｍ（ｍは１以上の整数）の多項式ｄτ（ｘ）ｆτに因数分解され、
前記第１情報は、多項式ｄτ（ｘ）ｆτ毎に、その多項式ｄτ（ｘ）ｆτによって得られる情報が設定された要素を含み、
前記復号部は、前記係数Δｉと前記要素とに基づき、前記暗号文を復号する
ことを特徴とする請求項２から６までのいずれかに記載の暗号システム。
【請求項８】
前記第１情報は、多項式ｄτ（ｘ）ｆτ毎に、κ＝０，．．．，ｆτの各整数κと、ｉ＝０，．．．，Ｌの各整数ｉとについて、多項式ｄτ（ｘ）κで多項式ａｉ（ｘ）を割った余りを設定した要素と、多項式ｄτ（ｘ）ｆτ−κで多項式ｂｉ（ｘ）を割った余りを設定した要素とを含む
ことを特徴とする請求項７に記載の暗号システム。
【請求項９】
前記第１情報は、多項式ｄτ（ｘ）ｆτ毎に、所定の値γを代入した値を設定した要素を含む
ことを特徴とする請求項７に記載の暗号システム。
【請求項１０】
前記復号部は、前記係数Δｉに基づき、前記要素について所定の演算を行うことにより、前記多項式ｄτ（ｘ）ｆτによって得られる情報を０にして、前記暗号文を復号する
ことを特徴とする請求項７から９までのいずれかに記載の暗号システム。
【請求項１１】
暗号化装置が、２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文として生成する暗号化工程と、
復号装置が、前記第１情報と前記第２情報とのうちの他方を復号鍵とし、前記２次スパンプログラムが前記属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号工程と
を備えることを特徴とする暗号方法。
【請求項１２】
２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文として生成する暗号化処理と、
前記第１情報と前記第２情報とのうちの他方を復号鍵とし、前記２次スパンプログラムが前記属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号処理と
をコンピュータに実行させることを特徴とする暗号プログラム。
【請求項１３】
２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文とし、他方を復号鍵として取得する情報取得部と、
前記情報取得部が取得した第１情報に含まれる２次スパンプログラムが第２情報に含まれる属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号部と
を備えることを特徴とする復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、２次スパンプログラムの考えを利用した関数型暗号方式に関する。
【背景技術】
【０００２】
関数型暗号方式は、暗号化鍵ｅｋと、復号鍵ｄｋとの間の関係をより高度化し、より柔軟にした暗号方式である。
関数型暗号方式において、暗号化鍵ｅｋと復号鍵ｄｋとには、それぞれ、パラメータΦとパラメータΨとが設定される。そして、関係Ｒ（Φ，Ψ）が成立する場合に限り、復号鍵ｄｋは暗号化鍵ｅｋで暗号化された暗号文を復号することができる。
【０００３】
非特許文献３には、関数型暗号方式についての記載がある。
【０００４】
非特許文献６には、２次スパンプログラムについての記載がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｖｅｃｔｏｒ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ．  Ｉｎ：  Ｇａｌｂｒａｉｔｈ，  Ｓ．Ｄ．，  Ｐａｔｅｒｓｏｎ，  Ｋ．Ｇ．  （ｅｄｓ．）  Ｐａｉｒｉｎｇ  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ５２０９，  ｐｐ．  ５７−７４，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００８）
【非特許文献２】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｈｉｅｒａｒｃｈｉｃａｌ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｉｎｎｅｒ−ｐｒｏｄｕｃｔｓ，  Ｉｎ：  ＡＳＩＡＣＲＹＰＴ  ２００９，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００９）
【非特許文献３】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｆｕｌｌｙ  ｓｅｃｕｒｅ  ｆｕｎｃｔｉｏｎａｌ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｇｅｎｅｒａｌ  ｒｅｌａｔｉｏｎｓ  ｆｒｏｍ  ｔｈｅ  ｄｅｃｉｓｉｏｎａｌ  ｌｉｎｅａｒ  ａｓｓｕｍｐｔｉｏｎ．  Ｉｎ：  Ｒａｂｉｎ，  Ｔ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２０１０．  ＬＮＣＳ，  ｖｏｌ．  ６２２３，  ｐｐ．  １９１−２０８．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１０）．  Ｆｕｌｌ  ｖｅｒｓｉｏｎ  ｉｓ  ａｖａｉｌａｂｌｅ  ａｔ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１０／５６３
【非特許文献４】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｅｆｆｉｃｉｅｎｔ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｏｒ  ｎｏｎ−ｍｏｎｏｔｏｎｅ  ｐｒｅｄｉｃａｔｅｓ  ｉｎ  ｔｈｅ  ｓｔａｎｄａｒｄ  ｍｏｄｅｌ，  Ｉｎ：  ＰＫＣ  ２０１１，  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１１）
【非特許文献５】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｓｉｇｎａｔｕｒｅｓ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１１／７０１
【非特許文献６】Ｒｏｓａｒｉｏ  Ｇｅｎｎａｒｏ  ａｎｄ  Ｃｒａｉｇ  Ｇｅｎｔｒｙ  ａｎｄ  Ｂｒｙａｎ  Ｐａｒｎｏ  ａｎｄ  Ｍａｒｉａｎａ  Ｒａｙｋｏｖａ：  Ｑｕａｄｒａｔｉｃ  Ｓｐａｎ  Ｐｒｏｇｒａｍｓ  ａｎｄ  Ｓｕｃｃｉｎｃｔ  ＮＩＺＫｓ  ｗｉｔｈｏｕｔ  ＰＣＰｓ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１２／２１５
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献３に記載された関数型暗号方式は、１次スパンプログラムを利用した方式である。この関数型暗号方式では、関係Ｒとして表現できる範囲に限界がある。
この発明は、２次スパンプログラムの考えを利用することにより、関係Ｒとして表現できる範囲を広くすることが可能な関数型暗号方式を提供することを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係る暗号システムは、
２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文として生成する暗号化装置と、
前記第１情報と前記第２情報とのうちの他方を復号鍵とし、前記２次スパンプログラムが前記属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号装置と
を備えることを特徴とする。
【発明の効果】
【０００８】
この発明に係る暗号システムでは、２次スパンプログラムの考えを利用することにより、関係Ｒとして表現できる範囲が理想化された範囲とすることが可能である。
【図面の簡単な説明】
【０００９】
【図１】２次スパンプログラムの説明図。
【図２】部分集合Ｉｕの説明図。
【図３】ＫＰ−ＦＥ方式を実行する暗号システム１０の構成図。
【図４】ＣＰ−ＦＥ方式を実行する暗号システム１０の構成図。
【図５】実施の形態２に係る鍵生成装置１００の構成図。
【図６】実施の形態２に係る暗号化装置２００の構成図。
【図７】実施の形態２に係る復号装置３００の構成図。
【図８】実施の形態２に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図９】実施の形態２に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図１０】実施の形態２に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図１１】実施の形態２に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図１２】実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図１３】鍵生成装置１００、暗号化装置２００、復号装置３００のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【００１０】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するＣＰＵ９１１等である。記憶装置は後述するＲＯＭ９１３、ＲＡＭ９１４、磁気ディスク９２０等である。通信装置は後述する通信ボード９１５等である。入力装置は後述するキーボード９０２、通信ボード９１５等である。つまり、処理装置、記憶装置、通信装置、入力装置はハードウェアである。
【００１１】
以下の説明における記法について説明する。
Ａがランダムな変数または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
2014029415.tif 000003
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
2014029415.tif 000004
数１０３は、ｙがｚにより定義された集合であること、又はｙがｚを代入された集合であることを表す。
【数１０３】
2014029415.tif 000005
ａが定数であるとき、数１０４は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数１０４】
2014029415.tif 000006
数１０５、つまりＦｑは、位数ｑの有限体を示す。
【数１０５】
2014029415.tif 000007
ベクトル表記は、有限体Ｆｑにおけるベクトル表示を表す。つまり、数１０６である。
【数１０６】
2014029415.tif 000008
数１０７は、数１０８に示す２つのベクトルｘ→とｖ→との数１０９に示す内積を表す。
【数１０７】
2014029415.tif 000009
【数１０８】
2014029415.tif 000010
【数１０９】
2014029415.tif 000011
ＸＴは、行列Ｘの転置行列を表す。
ｂｉ（ｉ＝１，．．．，ｎ）が空間Ｖのベクトルの要素であるとき、つまり、数１１０であるとき、数１１１は、数１１２によって生成される部分空間を表す。
【数１１０】
2014029415.tif 000012
【数１１１】
2014029415.tif 000013
【数１１２】
2014029415.tif 000014
数１１３に示す基底Ｂと基底Ｂ＊とに対して、数１１４である。
【数１１３】
2014029415.tif 000015
【数１１４】
2014029415.tif 000016
【００１２】
また、以下の説明において、“Ｖｔ”が下付き又は上付きで示されている場合、このＶｔはＶｔを意味する。同様に、“δｉ，ｊ”が上付きで示されている場合、このδｉ，ｊは、δｉ，ｊを意味する。同様に、“ｆτ”、“κτ”が上付きで示されている場合、このｆτは、ｆτを意味し、このκτはκτを意味する。
また、ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。
【００１３】
また、以下の説明において、暗号処理は、鍵生成処理、暗号化処理、復号処理を含む。
【００１４】
実施の形態１．
この実施の形態では、２次スパンプログラムを用いた関数型暗号方式の基礎となる概念と、２次スパンプログラムを用いた関数型暗号方式の概要とを説明する。
第１に、関数型暗号方式を実現するための空間である「双対ペアリングベクトル空間（Ｄｕａｌ  Ｐａｉｒｉｎｇ  Ｖｅｃｔｏｒ  Ｓｐａｃｅｓ，ＤＰＶＳ）」という豊かな数学的構造を有する空間を説明する。
第２に、関数型暗号方式を実現するための概念を説明する。ここでは、「２次スパンプログラム」、「属性情報の等号と２次スパンプログラム」、「秘密分散方式」について説明する。
第３に、２次スパンプログラムを用いた関数型暗号方式の概要について説明する。
【００１５】
＜第１．双対ペアリングベクトル空間＞
まず、対称双線形ペアリング群について説明する。
対称双線形ペアリング群（ｑ，Ｇ，ＧＴ，ｇ，ｅ）は、素数ｑと、位数ｑの巡回加法群Ｇと、位数ｑの巡回乗法群ＧＴと、ｇ≠０∈Ｇと、多項式時間で計算可能な非退化双線形ペアリング（Ｎｏｎｄｅｇｅｎｅｒａｔｅ  Ｂｉｌｉｎｅａｒ  Ｐａｉｒｉｎｇ）ｅ：Ｇ×Ｇ→ＧＴとの組である。非退化双線形ペアリングは、ｅ（ｓｇ，ｔｇ）＝ｅ（ｇ，ｇ）ｓｔであり、ｅ（ｇ，ｇ）≠１である。
以下の説明において、Ｇｂｐｇを、１λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を出力するアルゴリズムとする。
【００１６】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、対称双線形ペアリング群（ｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ））の直積によって構成することができる。双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、素数ｑ、数１１５に示すＦｑ上のＮ次元ベクトル空間Ｖ、位数ｑの巡回群ＧＴ、空間Ｖの標準基底Ａ：＝（ａ１，．．．，ａＮ）の組であり、以下の演算（１）（２）を有する。ここで、ａｉは、数１１６に示す通りである。
【数１１５】
2014029415.tif 000017
【数１１６】
2014029415.tif 000018
【００１７】
演算（１）：非退化双線形ペアリング
空間Ｖにおけるペアリングは、数１１７によって定義される。
【数１１７】
2014029415.tif 000019
これは、非退化双線形である。つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）ｓｔであり、全てのｙ∈Ｖに対して、ｅ（ｘ，ｙ）＝１の場合、ｘ＝０である。また、全てのｉとｊとに対して、ｅ（ａｉ，ａｊ）＝ｅ（ｇ，ｇ）δｉ，ｊである。ここで、ｉ＝ｊであれば、δｉ，ｊ＝１であり、ｉ≠ｊであれば、δｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈ＧＴである。
【００１８】
演算（２）：ディストーション写像
数１１８に示す空間Ｖにおける線形変換φｉ，ｊは、数１１９を行うことができる。
【数１１８】
2014029415.tif 000020
【数１１９】
2014029415.tif 000021
ここで、線形変換φｉ，ｊをディストーション写像と呼ぶ。
【００１９】
以下の説明において、Ｇｄｐｖｓを、１λ（λ∈自然数）、Ｎ∈自然数、双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を入力として、セキュリティパラメータがλであり、Ｎ次元の空間Ｖとする双対ペアリングベクトル空間のパラメータｐａｒａｍＶ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）の値を出力するアルゴリズムとする。
【００２０】
なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【００２１】
＜第２．関数型暗号を実現するための概念＞
＜第２−１．２次スパンプログラム＞
図１は、２次スパンプログラムの説明図である。
体Ｆｑにおける２次スパンプログラムは、２つの多項式の集合Ａ＝｛ａｉ（ｘ）｜ｉ∈｛０，．．．，Ｌ｝｝及び集合Ｂ＝｛ｂｉ（ｘ）｜ｉ∈｛０，．．．，Ｌ｝｝と、目標多項式ｄ（ｘ）とを含む。また、２次スパンプログラムは、集合Ｉ：＝｛１，．．．，Ｌ｝のラベルρを含む。全てのラベルρi（ｉ＝１，．．．，Ｌ）は、｛ｐ０，ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝のいずれか１つのリテラルへ対応付けられる。つまり、ρ：Ｉ→｛ｐ０，ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝である。
【００２２】
入力ｕ：＝（ｕ１，．．．，ｕｎ）∈｛０，１｝ｎに対して、ｊ＝１，．．．，ｎの各整数ｊについて、Ｔ（ｐｊ）：＝ｕｊ及びＴ（¬ｐｊ）：＝¬ｕｊにより、リテラルの真理値Ｔが設定される。また、どんな入力ｕに対しても、ｐ０の真理値Ｔは１が設定される。つまり、Ｔ（ｐ０）：＝１である。
集合Ｉの部分集合Ｉｕは、入力ｕにより１が設定されたラベルの要素から構成される。つまり、Ｉｕ：＝｛ｉ∈Ｉ｜Ｔ（ｐ（ｉ）＝１）｝である。又は、Ｉｕ：＝｛ｉ∈Ｉ｜［ρ（ｉ）＝ｐｊ∧ｕｊ＝１］∨［ρ（ｉ）＝¬ｐｊ∧ｕｊ＝０］∨［ρ（ｉ）＝ｐ０］｝である。
【００２３】
図２は、部分集合Ｉｕの説明図である。
なお、図２では、ｎ＝７，Ｌ＝６としている。また、図２において、ラベルρは、ρ１が¬ｐ２に、ρ２がｐ１に、ρ３がｐ４に、ρ４が¬ｐ５に、ρ５が¬ｐ３に、ρ６がｐ５にそれぞれ対応付けられているとする。
ここで、入力ｕ：＝（ｕ１，．．．，ｕ７）∈｛０，１｝７が、ｕ１＝１，ｕ２＝０，ｕ３＝１，ｕ４＝０，ｕ５＝０，ｕ６＝１，ｕ７＝１であるとする。この場合、部分集合Ｉｕは、破線で囲んだリテラル（ｐ１，ｐ３，ｐ６，ｐ７，¬ｐ２，¬ｐ４，¬ｐ５）に対応付けられているラベルρｉの要素ｉから構成される。つまり、部分集合Ｉｕは、ラベルρ１，ρ２，ρ４の要素ｉから構成され、部分集合Ｉｕ：＝｛ｉ＝１，２，４｝である。
【００２４】
２次スパンプログラムは、目標多項式ｄ（ｘ）が数１２０を割り切るような体ＦｑＬにおける（α１，．．．，αＬ）及び（β１，．．．，βＬ）の組であって、部分集合Ｉｕに含まれない全てのｉに対してαｉ＝０＝βｉである（α１，．．．，αＬ）及び（β１，．．．，βＬ）の組が存在する場合に限り、入力ｕ∈｛０，１｝ｎを受理する（又は、部分集合Ｉｕを受理する）。そして、２次スパンプログラムは、他の場合には、入力ｕ∈｛０，１｝ｎを拒絶する。
【数１２０】
2014029415.tif 000022
つまり、２次スパンプログラムは、目標多項式ｄ（ｘ）が数１２１を割り切るようなｉ∈Ｉｕについてのαｉ及びβｉの組が存在する場合に限り、入力ｕ∈｛０，１｝ｎを受理する。
【数１２１】
2014029415.tif 000023
そして、２次スパンプログラムが入力ｕ∈｛０，１｝ｎを受理する場合、ｉ∈Ｉｕについてのαｉ及びβｉの組を、多項式時間で計算することが可能である（非特許文献６参照）。
【００２５】
図２に示す例であれば、２次スパンプログラムは、目標多項式ｄ（ｘ）が数１２２を割り切るようなｉ∈Ｉｕ：＝｛ｉ＝１，２，４｝についてのαｉ及びβｉの組が存在する場合に限り、入力ｕ∈｛０，１｝ｎを受理する。
【数１２２】
2014029415.tif 000024
【００２６】
＜第２−２．属性の内積と２次スパンプログラム＞
Ｕｔ（ｔ＝１，．．．，ｄでありＵｔ⊂｛０，１｝＊）は、部分全集合（ｓｕｂ−ｕｎｉｖｅｒｓｅ）であり、属性の集合である。そして、Ｕｔは、それぞれ部分全集合の識別情報（ｔ）と、ｎ次元ベクトルで表された属性情報（ｖ→）とを含む。つまり、Ｕｔは、（ｔ，ｖ→）である。ここで、ｔ∈｛１，．．．，ｄ｝であり、ｖ→∈Ｆｑｎである。
【００２７】
Ｕｔ＝（ｔ，ｖ→）をｐとする。つまり、ｐ＝（ｔ，ｖ→）である。ｐｊ：＝（ｔ，ｖ→ｊ）（ｊ＝１，．．．，ｎ；ｔ∈｛１，．．．，ｄ｝）による２次スパンプログラムＱ：＝（Ａ，Ｂ，ｄ（ｘ），ρ）における、部分集合Ｉｕの決定方法について説明する。
アクセスストラクチャＳを、ｐ０及び｛ｐｊ：＝（ｔ，ｖ→ｊ）｝ｊ＝１，．．．，ｎを伴う２次スパンプログラムＱ：＝（Ａ，Ｂ，ｄ（ｘ），ρ）とする。つまり、ρ：｛１，．．．，Ｌ｝→｛ｐ０，（ｔ，ｖ→１），．．．，（ｔ，ｖ→ｎ），¬（ｔ，ｖ→１），．．．，¬（ｔ，ｖ→ｎ）｝である。また、Γを属性集合とする。つまり、Γ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎ，１≦ｔ≦ｄ｝である。ここで、ｔは、｛１，．．．，ｄ｝の部分集合であって、全インデックスである必要はない。
属性集合ΓがアクセスストラクチャＳに与えられると、｛ｐ０，ｐ１，．．．，ｐｎ，¬ｐ１，．．．，¬ｐｎ｝のリテラルの真理値Ｔは次のように決定される。ｐｊ＝（ｔ，ｖ→ｊ）かつ（ｔ，ｘ→ｔ）∈Γかつｖ→ｊ・ｘ→ｔ＝０である場合に限り、Ｔ（ｐｊ）：＝１になる。ｐｊ＝¬（ｔ，ｖ→ｊ）かつ（ｔ，ｘ→ｊ）∈Γかつｖ→ｊ・ｘ→ｔ≠０である場合に限り、Ｔ（¬ｐｊ）：＝１になる。Ｔ（ｐ０）：＝１になる。他の場合には、真理値Ｔは０になる。
そして、Ｉｕ（＝Ｉ（ρ，Γ））：＝｛ｉ∈Ｉ｜Ｔ（ρ（ｉ））＝１｝、つまり、Ｉ（ρ，Γ）：＝｛ｉ∈Ｉ｜［ρ（ｉ）＝（ｔ，ｖ→ｊ）∧（ｔ，ｘ→ｔ）∈Γ∧（ｖ→ｊ・ｘ→ｔ）＝０］∨［ρ（ｉ）＝¬（ｔ，ｖ→ｊ）∧（ｔ，ｘ→ｊ）∈Γ∧ｖ→ｊ・ｘ→ｔ≠０］∨［ρ（ｉ）＝ｐ０］｝とする。
【００２８】
＜第３．関数型暗号方式の概要＞
復号鍵と暗号文との一方に上述したアクセスストラクチャＳを持たせ、他方に属性集合Γを持たせることにより、関数型暗号方式を構成する。
【００２９】
アクセスストラクチャＳを復号鍵に持たせた関数型暗号方式をＫｅｙ−Ｐｏｌｉｃｙ関数型暗号（ＫＰ−ＦＥ）方式と呼び、アクセスストラクチャＳを暗号文に持たせた暗号方式をＣｉｐｈｅｒｔｅｘｔ−Ｐｏｌｉｃｙ関数型暗号（ＣＰ−ＦＥ）方式と呼ぶ。
ＫＰ−ＦＥ方式及びＣＰ−ＦＥ方式の構成と、各方式を実行する暗号システム１０の構成とを説明する。
【００３０】
＜第３−１．ＫＰ−ＦＥ方式＞
ＫＰ−ＦＥ方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、アクセスストラクチャＳと、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、復号鍵ｓｋＳを出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、メッセージｍｓｇと、属性の集合であるΓ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎ，１≦ｔ≦ｄ｝と、公開パラメータｐｋとを入力として、暗号文ｃｔΓを出力する確率的アルゴリズムである。
（Ｄｅｃ）
Ｄｅｃアルゴリズムは、属性の集合であるΓの下で暗号化された暗号文ｃｔΓと、アクセスストラクチャＳに対する復号鍵ｓｋＳと、公開パラメータｐｋとを入力として、メッセージｍｓｇ、又は、識別情報⊥を出力するアルゴリズムである。
【００３１】
図３は、ＫＰ−ＦＥ方式を実行する暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００を備える。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、アクセスストラクチャＳを入力としてＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成して復号装置３００へ秘密裡に配布する。
暗号化装置２００は、メッセージｍｓｇと、属性の集合Γと、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔΓを生成する。暗号化装置２００は、生成した暗号文ｃｔΓを復号装置３００へ送信する。
復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋＳと、暗号文ｃｔΓとを入力としてＤｅｃアルゴリズムを実行して、メッセージｍｓｇ又は識別情報⊥を出力する。
【００３２】
＜第３−２．ＣＰ−ＦＥ方式＞
ＣＰ−ＦＥ方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、属性の集合であるΓ：＝｛（ｔ，ｘ→ｔ）｜ｘ→ｔ∈Ｆｑｎ，１≦ｔ≦ｄ｝と、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、復号鍵ｓｋΓを出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、メッセージｍｓｇと、アクセスストラクチャＳと、公開パラメータｐｋとを入力として、暗号文ｃｔＳを出力する確率的アルゴリズムである。
（Ｄｅｃ）
Ｄｅｃアルゴリズムは、アクセスストラクチャＳの下で暗号化された暗号文ｃｔＳと、属性の集合であるΓに対する復号鍵ｓｋΓと、公開パラメータｐｋとを入力として、メッセージｍｓｇ、又は、識別情報⊥を出力するアルゴリズムである。
【００３３】
図４は、ＣＰ−ＦＥ方式を実行する暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００を備える。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、属性の集合Γを入力としてＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋΓを生成して復号装置３００へ秘密裡に配布する。
暗号化装置２００は、メッセージｍｓｇと、アクセスストラクチャＳと、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔＳを生成する。暗号化装置２００は、生成した暗号文ｃｔＳを復号装置３００へ送信する。
復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋΓと、暗号文ｃｔＳとを入力としてＤｅｃアルゴリズムを実行して、メッセージｍｓｇ又は識別情報⊥を出力する。
【００３４】
ＫＰ−ＦＥ方式及びＣＰ−ＦＥ方式のどちらにおいても、Ｄｅｃアルゴリズムでは、アクセスストラクチャＳと属性集合Γとに基づき、上述した方法により、部分集合Ｉ（ρ，Γ）を選択し、さらに係数（α１，．．．，αＬ）及び係数（β１，．．．，βＬ）を特定する。そして、部分集合Ｉ（ρ，Γ）と係数（α１，．．．，αＬ）及び係数（β１，．．．，βＬ）とに基づき、暗号文ｃｔΓ（又はｃｔＳ）を復号してメッセージｍｓｇを計算する。
【００３５】
なお、Ｓｅｔｕｐアルゴリズムは、通常、システムのセットアップ時に１度だけ実行される。ＫｅｙＧｅｎアルゴリズムは、ユーザの復号鍵を生成する度に実行される。Ｅｎｃアルゴリズムは、メッセージｍｓｇを暗号化する度に実行される。Ｄｅｃアルゴリズムは、暗号文を復号する度に実行される。
【００３６】
実施の形態１に係る暗号システム１０では、２次スパンプログラムに基づくアクセスストラクチャＳを用いて関数型暗号方式を構成する。これにより、関係Ｒとして表現できる範囲を理想化された範囲とすることが可能となる。
【００３７】
実施の形態２．
実施の形態２では、２次スパンプログラムを用いた関数型暗号方式の構成例について説明する。
ここでは、ＫＰ−ＦＥ方式を例として説明する。
【００３８】
図５は、実施の形態２に係る鍵生成装置１００の構成図である。図６は、実施の形態２に係る暗号化装置２００の構成図である。図７は、実施の形態２に係る復号装置３００の構成図である。
図８と図９とは、鍵生成装置１００の動作を示すフローチャートである。図８はＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図９はＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図１０は、暗号化装置２００の動作を示すフローチャートであり、Ｅｎｃアルゴリズムの処理を示すフローチャートである。図１１は、復号装置３００の動作を示すフローチャートであり、Ｄｅｃアルゴリズムの処理を示すフローチャートである。
【００３９】
鍵生成装置１００の機能と動作とについて説明する。
鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵配布部１５０を備える。また、復号鍵生成部１４０は、秘密情報生成部１４１、鍵要素生成部１４２を備える。
【００４０】
図８に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：正規直交基底生成ステップ）
マスター鍵生成部１１０は、処理装置により、数１２３を計算して、パラメータｐａｒａｍと、基底Ｂ０及び基底Ｂ＊０と、基底Ｂｔ及び基底Ｂ＊ｔとを生成する。
【数１２３】
2014029415.tif 000025
【００４１】
つまり、マスター鍵生成部１１０は以下の処理を実行する。
（１）マスター鍵生成部１１０は、入力装置により、セキュリティパラメータλ（１λ）を入力する。
（２）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλを入力としてアルゴリズムＧｂｐｇを実行して、双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を生成する。
（３）マスター鍵生成部１１０は、処理装置により、乱数ψを生成する。
（４）マスター鍵生成部１１０は、Ｎ０にｎ０＋ｕ０＋ｗ０＋ｚ０を設定し、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の各整数ｔについて、Ｎｔにｎｔ＋ｕｔ＋ｗｔ＋ｚｔを設定する。ここで、ｎ０は２ｍｆｍａｘ＋１であり、ｎｔは２ｍｆｍａｘｋｍａｘ＋ｎである。ｍは、目標多項式ｄ（ｘ）を因数分解した場合の因数の数である。ｆｍａｘは、目標多項式ｄ（ｘ）を因数分解した場合の因数の次数の最大値（後述するｆτの最大値）である。ｋｍａｘは、１つの識別情報ｔに対応付けられるラベルρの個数の最大値である。ｎは１以上の整数であり、ｕ０，ｗ０，ｚ０，ｕｔ，ｗｔ，ｚｔはそれぞれ０以上の整数である。
【００４２】
続いて、マスター鍵生成部１１０は、ｔ＝０，．．．，ｄの各整数ｔについて以下の（５）から（９）までの処理を実行する。
（５）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλと、（４）で設定したＮｔと、（２）で生成したｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値とを入力としてアルゴリズムＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶｔ：＝（ｑ，Ｖｔ，ＧＴ，Ａｔ，ｅ）の値を生成する。
（６）マスター鍵生成部１１０は、処理装置により、（４）で設定したＮｔと、Ｆｑとを入力として、線形変換Ｘｔ：＝（χｔ，ｉ，ｊ）ｉ，ｊをランダムに生成する。なお、ＧＬは、Ｇｅｎｅｒａｌ  Ｌｉｎｅａｒの略である。つまり、ＧＬは、一般線形群であり、行列式が０でない正方行列の集合であり、乗法に関し群である。また、（χｔ，ｉ，ｊ）ｉ，ｊは、行列χｔ，ｉ，ｊの添え字ｉ，ｊに関する行列という意味であり、ここでは、ｉ，ｊ＝１，．．．，Ｎｔである。
（７）マスター鍵生成部１１０は、処理装置により、乱数ψと線形変換Ｘｔとに基づき、Ｘ＊ｔ：＝（νｔ，ｉ，ｊ）ｉ，ｊ：＝ψ・（ＸｔＴ）−１を生成する。なお、（νｔ，ｉ，ｊ）ｉ，ｊも（χｔ，ｉ，ｊ）ｉ，ｊと同様に、行列νｔ，ｉ，ｊの添え字ｉ，ｊに関する行列という意味であり、ここでは、ｉ，ｊ＝１，．．．，Ｎｔである。
（８）マスター鍵生成部１１０は、処理装置により、（６）で生成した線形変換Ｘｔに基づき、（５）で生成した標準基底Ａｔから基底Ｂｔを生成する。なお、ｘ→ｔ，ｉとは、線形変換Ｘｔのｉ行目を示す。
（９）マスター鍵生成部１１０は、処理装置により、（７）で生成した線形変換Ｘ＊ｔに基づき、（５）で生成した標準基底Ａｔから基底Ｂ＊ｔを生成する。なお、ｖ→ｔ，ｉとは、線形変換Ｘ＊ｔのｉ行目を示す。
（１０）マスター鍵生成部１１０は、処理装置により、ｇＴにｅ（ｇ，ｇ）ψを設定する。また、マスター鍵生成部１１０は、ｐａｒａｍに（５）で生成した｛ｐａｒａｍＶｔ｝ｔ＝０，．．．，ｄと、ｇＴとを設定する。
【００４３】
すなわち、（Ｓ１０１）で、マスター鍵生成部１１０は、数１２４に示すアルゴリズムＧｏｂを実行して、ｐａｒａｍと、基底Ｂ０及び基底Ｂ＊０と、基底Ｂｔ及び基底Ｂ＊ｔとを生成する。
【数１２４】
2014029415.tif 000026
【００４４】
（Ｓ１０２：公開パラメータ生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ０の部分基底Ｂ＾０と、基底Ｂｔの部分基底Ｂ＾ｔとを数１２５に示すように生成する。
【数１２５】
2014029415.tif 000027
マスター鍵生成部１１０は、生成した部分基底Ｂ＾０及び部分基底Ｂ＾ｔと、（Ｓ１０１）で入力されたセキュリティパラメータλと、（Ｓ１０１）で生成したｐａｒａｍとを合わせて、公開パラメータｐｋとする。
【００４５】
（Ｓ１０３：マスター鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ＊０の部分基底Ｂ＾＊０と、基底Ｂ＊ｔの部分基底Ｂ＾＊ｔとを数１２６に示すように生成する。
【数１２６】
2014029415.tif 000028
マスター鍵生成部１１０は、生成した部分基底Ｂ＾＊０と部分基底Ｂ＾＊ｔとをマスター鍵ｓｋとする。
【００４６】
（Ｓ１０４：マスター鍵記憶ステップ）
マスター鍵記憶部１２０は、（Ｓ１０２）で生成した公開パラメータｐｋを記憶装置に記憶する。また、マスター鍵記憶部１２０は、（Ｓ１０３）で生成したマスター鍵ｓｋを記憶装置に記憶する。
【００４７】
つまり、（Ｓ１０１）から（Ｓ１０３）において、鍵生成装置１００は、数１２７に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ１０４）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【数１２７】
2014029415.tif 000029
【００４８】
図９に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ２０１：情報入力ステップ）
情報入力部１３０は、入力装置により、上述したアクセスストラクチャＳ：＝（Ａ，Ｂ，ｄ（ｘ），ρ）を入力する。なお、ρは、例えば、復号鍵ｓｋＳの使用者の属性情報が設定されている。また、アクセスストラクチャＳに含まれる目標多項式ｄ（ｘ）は、数１２８に示すように、τ＝１，．．．，ｍのｍ個の因数ｄτ（ｘ）ｆτに因数分解可能である。
【数１２８】
2014029415.tif 000030
【００４９】
（Ｓ２０２：秘密情報π生成ステップ）
秘密情報生成部１４１は、処理装置により、秘密情報πτ，κ，０及び秘密情報πτ，κ，１を数１２９に示すように生成する。
【数１２９】
2014029415.tif 000031
【００５０】
（Ｓ２０３：秘密情報χ生成ステップ）
秘密情報生成部１４１は、処理装置により、秘密情報χτ，κ，０及び秘密情報χτ，κ，１を数１３０に示すように生成する。
【数１３０】
2014029415.tif 000032
【００５１】
（Ｓ２０４：秘密情報ｓ生成ステップ）
秘密情報生成部１４１は、処理装置により、秘密情報ｓ０（τ，κ，０）及び秘密情報ｓ０（τ，κ，１）と、秘密情報ｓｉ（τ，κ，０）及び秘密情報ｓｉ（τ，κ，１）とを数１３１に示すように生成する。
【数１３１】
2014029415.tif 000033
【００５２】
（Ｓ２０５：鍵要素生成ステップ）
鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆτの各整数κと、ι＝０，１の各整数ιとについて、復号鍵ｓｋＳの要素ｋ＊０（τ，κ，ι）を数１３２に示すように生成する。
【数１３２】
2014029415.tif 000034
なお、上述したように、数１１３に示す基底Ｂと基底Ｂ＊とに対して、数１１４である。したがって、数１３２は、基底Ｂ＊０の基底ベクトルｂ＊０，１の係数としてｓ０（τ，κ，ι）＋πτ，κ，ιを設定し、基底ベクトルｂ＊０，１＋１，．．．，ｂ＊０，１＋ｎ０の係数としてｅ→０（τ，κ，ι）を設定し、基底ベクトルｂ＊０，ｎ０＋１，．．．，ｂ＊０，ｎ０＋ｕ０の係数として０を設定し、基底ベクトルｂ＊０，ｎ０＋ｕ０＋１，．．．，ｂ＊０，ｎ０＋ｕ０＋ｗ０の係数としてη０，１（τ，κ，ι），．．．，η０，ｗ０（τ，κ，ι）を設定し、基底ベクトルｂ＊０，ｎ０＋ｕ０＋ｗ０＋１，．．．，ｂ＊０，ｎ０＋ｕ０＋ｗ０＋ｚ０の係数として０を設定することを意味する。ここで、ｎ０，ｕ０，ｗ０，ｚ０はそれぞれｎ０，ｕ０，ｗ０，ｚ０のことである。
また、ｅ→０（τ，κ，ι）は、１つの基底ベクトルの係数として１が設定され、他の基底ベクトルの係数として０が設定された２ｍｆｍａｘ次元のベクトルであって、係数として１が設定される基底ベクトルが（τ，κ，ι）毎に異なるベクトルである。同様に、ｅ→ｉ（τ，κ，ι）は、１つの基底ベクトルの係数として１が設定され、他の基底ベクトルの係数として０が設定された２ｍｆｍａｘｋｍａｘ次元のベクトルであって、係数として１が設定される基底ベクトルが（τ，κ，ι）毎に異なるベクトルである。
また、ｅ→１は、基底ベクトルｂ＊ｔ，１の係数として１が設定され、他の基底ベクトルの係数として０が設定されたｎ次元のベクトルである。
鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆτの各整数κと、ι＝０，１の各整数ιと、ｉ＝１，．．．，Ｌの各整数ｉとについて、復号鍵ｓｋＳの要素ｋ＊ｉ（τ，κ，ι）を数１３３に示すように生成する。
【数１３３】
2014029415.tif 000035
【００５３】
（Ｓ２０６：鍵配布ステップ）
鍵配布部１５０は、（Ｓ２０１）で入力したアクセスストラクチャＳと、（Ｓ２０５）で生成されたｋ＊０（τ，κ，ι），ｋ＊１（τ，κ，ι），．．．，ｋ＊Ｌ（τ，κ，ι）とを要素とする復号鍵ｓｋＳを、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋＳは、他の方法により復号装置３００へ配布されてもよい。
【００５４】
つまり、（Ｓ２０１）から（Ｓ２０５）において、鍵生成装置１００は、数１３４から数１３５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成する。そして、（Ｓ２０６）で、鍵生成装置１００は、生成した復号鍵ｓｋＳを復号装置３００へ配布する。
【数１３４】
2014029415.tif 000036
【数１３５】
2014029415.tif 000037
【００５５】
暗号化装置２００の機能と動作とについて説明する。
暗号化装置２００は、公開パラメータ取得部２１０、情報入力部２２０、暗号化データ生成部２３０、データ送信部２４０を備える。
【００５６】
図１０に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ３０１：公開パラメータ取得ステップ）
公開パラメータ取得部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００５７】
（Ｓ３０２：情報入力ステップ）
情報入力部２２０は、入力装置により、復号装置３００へ送信するメッセージｍｓｇを入力する。また、情報入力部２２０は、入力装置により、属性の集合Γ：＝｛（ｔ，ｘ→ｔ：＝（ｘｔ，１，．．．，ｘｔ，ｎ∈Ｆｑｎ））｜１≦ｔ≦ｄ｝を入力する。なお、ｔは、１以上ｄ以下の全ての整数ではなく、１以上ｄ以下の少なくとも一部の整数であってもよい。また、属性の集合Γは、例えば、復号可能なユーザの属性情報が設定されている。
【００５８】
（Ｓ３０３：暗号要素生成ステップ）
暗号化データ生成部２３０は、処理装置により、暗号文ｃｔΓの要素ｃ０を数１３６に示すように生成する。
【数１３６】
2014029415.tif 000038
暗号化データ生成部２３０は、処理装置により、属性情報Γに含まれる各整数ｔについて、暗号文ｃｔΓの要素ｃｔを数１３７に示すように生成する。
【数１３７】
2014029415.tif 000039
暗号化データ生成部２３０は、処理装置により、暗号文ｃｔΓの要素ｃｄ＋１を数１３８に示すように生成する。
【数１３８】
2014029415.tif 000040
【００５９】
（Ｓ３０４：データ送信ステップ）
データ送信部２４０は、（Ｓ３０２）で入力した属性の集合Γと、（Ｓ３０３）で生成されたｃ０，ｃｔ，ｃｄ＋１とを要素とする暗号文ｃｔΓを、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔΓは、他の方法により復号装置３００へ送信されてもよい。
【００６０】
つまり、（Ｓ３０１）から（Ｓ３０３）において、暗号化装置２００は、数１３９に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔΓを生成する。そして、（Ｓ３０４）で、暗号化装置２００は生成した暗号文ｃｔΓを復号装置３００へ送信する。
【数１３９】
2014029415.tif 000041
【００６１】
復号装置３００の機能と動作とについて説明する。
復号装置３００は、情報取得部３１０、スパンプログラム計算部３２０、補完係数計算部３３０、復号部３４０を備える。また、情報取得部３１０は、復号鍵取得部３１１、暗号文取得部３１２を備える。また、補完係数計算部３３０は、多項式選択部３３１、係数計算部３３２を備える。また、復号部３４０は、ペアリング演算部３４１、メッセージ計算部３４２を備える。
【００６２】
図１１に基づき、Ｄｅｃアルゴリズムの処理について説明する。
（Ｓ４０１：復号鍵取得ステップ）
復号鍵取得部３１１は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から配布された復号鍵ｓｋＳ：＝（Ｓ，ｋ＊０（τ，κ，ι），ｋ＊１（τ，κ，ι），．．．，ｋ＊Ｌ（τ，κ，ι））を取得する。また、復号鍵取得部３１１は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００６３】
（Ｓ４０２：暗号文取得ステップ）
暗号文取得部３１２は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔΓ：＝（Γ，ｃ０，ｃｔ，ｃｄ＋１）を取得する。
【００６４】
（Ｓ４０３：スパンプログラム計算ステップ）
スパンプログラム計算部３２０は、処理装置により、（Ｓ４０１）で取得した復号鍵ｓｋＳに含まれるアクセスストラクチャＳが、（Ｓ４０２）で取得した暗号文ｃｔΓに含まれるΓを受理するか否かを判定する。アクセスストラクチャＳがΓを受理するか否かの判定方法は、「実施の形態１における第２−１．２次スパンプログラム」で説明した通りである。
スパンプログラム計算部３２０は、アクセスストラクチャＳがΓを受理する場合（Ｓ４０３で受理）、処理を（Ｓ４０４）へ進める。一方、アクセスストラクチャＳがΓを拒絶する場合（Ｓ４０３で拒絶）、暗号文ｃｔΓを復号鍵ｓｋＳで復号できないとして処理を終了する。
【００６５】
（Ｓ４０４：多項式選択ステップ）
補完係数計算部３３０の多項式選択部３３１は、処理装置により、Ｉ（ρ，Γ）⊆｛１，．．．，Ｌ｝を計算する。Ｉ（ρ，Γ）の計算方法は、「実施の形態１の第２−２．属性の内積と２次スパンプログラム」で説明した通りである。
【００６６】
（Ｓ４０５：係数計算ステップ）
補完係数計算部３３０の係数計算部３３２は、処理装置により、数１４０となる係数（α１，．．．，αＬ）と、係数（β１，．．．，βＬ）と、次数（κ１，．．．，κｍ）とを計算する。係数（α１，．．．，αＬ）と、係数（β１，．．．，βＬ）と、次数（κ１，．．．，κｍ）との計算方法は、どのような方法でもよく、例えば総当たり法により計算してもよい。
【数１４０】
2014029415.tif 000042
ここで、Ｉ（ρ，Γ）に含まれない全てのｉについては、αｉ＝０＝βｉである。
【００６７】
（Ｓ４０６：ペアリング演算ステップ）
復号部３４０のペアリング演算部３４１は、処理装置により、数１４１を計算して、セッション鍵Ｋτ，０，Ｋτ，１を生成する。
【数１４１】
2014029415.tif 000043
【００６８】
（Ｓ４０７：メッセージ計算ステップ）
復号部３４０のメッセージ計算部３４２は、処理装置により、数１４２を計算して、メッセージｍｓｇ’（＝ｍｓｇ）を生成する。
【数１４２】
2014029415.tif 000044
なお、数１４３に示すように、数１４１を計算することによりｇＴζが得られる。そのため、数１４２を計算することにより、メッセージｍｓｇ’（＝ｍｓｇ）を得られる。
【数１４３】
2014029415.tif 000045
【００６９】
つまり、（Ｓ４０１）から（Ｓ４０７）において、復号装置３００は、数１４４に示すＤｅｃアルゴリズムを実行して、メッセージｍｓｇ’（＝ｍｓｇ）を生成する。
【数１４４】
2014029415.tif 000046
【００７０】
以上のように、実施の形態２に係る暗号システム１０では、２次スパンプログラムを利用した関数型暗号方式を実現する。
２次スパンプログラムを利用することにより、関係Ｒとして表現できる範囲が広い。
【００７１】
特に、実施の形態２に係る暗号システム１０では、目標多項式ｄ（ｘ）を因数分解した多項式ｄτ（ｘ）ｆτ毎に、多項式ｄτ（ｘ）κで多項式ａｉ（ｘ）を割った余りを設定した要素と、多項式ｄτ（ｘ）ｆτ−κで多項式ｂｉ（ｘ）を割った余りを設定した要素とを、鍵要素ｋ＊０（τ，κ，ι），ｋ＊１（τ，κ，ι），．．．，ｋ＊Ｌ（τ，κ，ι）とする。また、各鍵要素ｋ＊０（τ，κ，ι）に、秘密情報πと秘密情報χとを分散させて設定する。そして、係数α，βを用いて、鍵要素と暗号要素とのペアリング演算をすることにより、各鍵要素に設定された余りを０にし、秘密情報πを０にし、秘密情報χを１にすることにより、暗号文からセッション鍵Ｋτ，０，Ｋτ，１を抽出する。これにより、２次スパンプログラムを利用した関数型暗号方式を実現する。
【００７２】
なお、上記説明では、ＫＰ−ＦＥ方式について説明した。しかし、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズム、Ｄｅｃアルゴリズムをそれぞれ数１４５から数１４８に示すようにすることにより、ＣＰ−ＦＥ方式とすることも可能である。なお、Ｓｅｔｕｐアルゴリズムは、ＫＰ−ＦＥ方式とＣＰ−ＦＥ方式とで同じである。
【数１４５】
2014029415.tif 000047
【数１４６】
2014029415.tif 000048
【数１４７】
2014029415.tif 000049
【数１４８】
2014029415.tif 000050
【００７３】
また、上記説明では、関数型暗号方式について説明した。しかし、Ｓｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズム、Ｄｅｃアルゴリズムをそれぞれ数１４９から数１５３に示すようにすることにより、属性ベース暗号方式とすることも可能である。なお、属性ベース暗号方式の場合、Ｓｅｔｕｐアルゴリズムにおいて、ｎｔは２ｍｆｍａｘｋｍａｘ＋２である。
【数１４９】
2014029415.tif 000051
【数１５０】
2014029415.tif 000052
【数１５１】
2014029415.tif 000053
【数１５２】
2014029415.tif 000054
【数１５３】
2014029415.tif 000055
同様に、数１４５から数１４８に示すＣＰ−ＦＥ方式を属性ベース暗号方式に変更することも可能である。
【００７４】
また、上記説明では、Ｎ０にｎ０＋ｕ０＋ｗ０＋ｚ０を設定し、Ｎｔにｎｔ＋ｕｔ＋ｗｔ＋ｚｔを設定した。ここで、例えば、ｕ０＝ｎ０，ｗ０＝ｎ０，ｚ０＝２として、Ｎ０にｎ０＋ｎ０＋ｎ０＋２＝３ｎ０＋２とし、ｕｔ＝ｎｔ，ｗｔ＝ｎｔ，ｚｔ＝１として、Ｎｔにｎｔ＋ｎｔ＋ｎｔ＋１＝３ｎｔ＋１としてもよい。
【００７５】
実施の形態３．
実施の形態３では、実施の形態２で説明した関数型暗号方式に比べ、基底の数が多くなる代わりに、各基底の次元数が少ない関数型暗号方式を説明する。
実施の形態３では、実施の形態２に係る暗号システム１０と異なる部分を中心に説明する。
【００７６】
実施の形態３に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、図５〜図７に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同じである。
実施の形態３に係るＤｅｃアルゴリズムの処理については、実施の形態２に係るＤｅｃアルゴリズムの処理と同じであるため、ここでは、実施の形態３に係るＳｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムの処理について説明する。
実施の形態３に係るＳｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムの処理の流れは、図８〜図１０に示す実施の形態２に係るＳｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムの処理の流れと同じである。
【００７７】
図８に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：正規直交基底生成ステップ）
（１）〜（３）の処理は、実施の形態２と同じである。
（４）マスター鍵生成部１１０は、Ｎ０にｎ０＋ｕ０＋ｗ０＋ｚ０を設定し、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の各整数ｔについて、Ｎｔにｎｔ＋ｕｔ＋ｗｔ＋ｚｔを設定する。ここで、ｎ０は１であり、ｎｔはｎである。ｎは１以上の整数であり、ｕ０，ｗ０，ｚ０，ｕｔ，ｗｔ，ｚｔはそれぞれ０以上の整数である。
続いて、マスター鍵生成部１１０は、τ＝１，．．．，ｍ、κ＝０，．．．，ｆτ、ι＝０，１、ｔ＝０，．．．，ｄの各整数τ、κ、ι、ｔについて（５）から（９）までの処理を実行する。
（５）の処理は、実施の形態２と同じである。
（６）マスター鍵生成部１１０は、実施の形態２と同様に、線形変換Ｘｔ（τ，κ，ι）：＝（χｔ，ｉ，ｊ（τ，κ，ι））ｉ，ｊをランダムに生成する。
（７）マスター鍵生成部１１０は、実施の形態２と同様に、Ｘ＊ｔ（τ，κ，ι）：＝（νｔ，ｉ，ｊ（τ，κ，ι））ｉ，ｊ：＝ψ・（Ｘｔ（τ，κ，ι）Ｔ）−１を生成する。
（８）マスター鍵生成部１１０は、実施の形態２と同様に、（６）で生成した線形変換Ｘｔ（τ，κ，ι）に基づき、（５）で生成した標準基底Ａｔから基底Ｂｔ（τ，κ，ι）を生成する。
（９）マスター鍵生成部１１０は、実施の形態２と同様に、（７）で生成した線形変換Ｘ＊ｔ（τ，κ，ι）に基づき、（５）で生成した標準基底Ａｔから基底Ｂ＊ｔ（τ，κ，ι）を生成する。
（１０）の処理は、実施の形態２と同じである。
【００７８】
（Ｓ１０２：公開パラメータ生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ０（τ，κ，ι）の部分基底Ｂ＾０（τ，κ，ι）と、基底Ｂｔ（τ，κ，ι）の部分基底Ｂ＾ｔ（τ，κ，ι）とを数１５４に示すように生成する。
【数１５４】
2014029415.tif 000056
マスター鍵生成部１１０は、生成した部分基底Ｂ＾０（τ，κ，ι）及び部分基底Ｂ＾ｔ（τ，κ，ι）と、（Ｓ１０１）で入力されたセキュリティパラメータλと、（Ｓ１０１）で生成したｐａｒａｍとを合わせて、公開パラメータｐｋとする。
【００７９】
（Ｓ１０３：マスター鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ＊０（τ，κ，ι）の部分基底Ｂ＾＊０（τ，κ，ι）と、基底Ｂ＊ｔ（τ，κ，ι）の部分基底Ｂ＾＊ｔ（τ，κ，ι）とを数１５５に示すように生成する。
【数１５５】
2014029415.tif 000057
マスター鍵生成部１１０は、生成した部分基底Ｂ＾＊０（τ，κ，ι）と部分基底Ｂ＾＊ｔ（τ，κ，ι）とをマスター鍵ｓｋとする。
【００８０】
（Ｓ１０４）の処理は、実施の形態２と同じである。
【００８１】
つまり、（Ｓ１０１）から（Ｓ１０３）において、鍵生成装置１００は、数１５６に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ１０４）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。
【数１５６】
2014029415.tif 000058
【００８２】
図９に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ２０１）から（Ｓ２０４）までと、（Ｓ２０６）との処理は、実施の形態２と同じである。
【００８３】
（Ｓ２０５：鍵要素生成ステップ）
鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆτの各整数κと、ι＝０，１の各整数ιとについて、復号鍵ｓｋＳの要素ｋ＊０（τ，κ，ι）を数１５７に示すように生成する。
【数１５７】
2014029415.tif 000059
鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆτの各整数κと、ι＝０，１の各整数ιと、ｉ＝１，．．．，Ｌの各整数ｉとについて、復号鍵ｓｋＳの要素ｋ＊ｉ（τ，κ，ι）を数１５８に示すように生成する。
【数１５８】
2014029415.tif 000060
【００８４】
つまり、（Ｓ２０１）から（Ｓ２０５）において、鍵生成装置１００は、数１５９から数１６０に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成する。そして、（Ｓ２０６）で、鍵生成装置１００は、生成した復号鍵ｓｋＳを復号装置３００へ配布する。
【数１５９】
2014029415.tif 000061
【数１６０】
2014029415.tif 000062
【００８５】
図１０に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ３０１）から（Ｓ３０２）までと、（Ｓ３０４）との処理は、実施の形態２と同じである。
【００８６】
（Ｓ３０３：暗号要素生成ステップ）
暗号化データ生成部２３０は、処理装置により、暗号文ｃｔΓの要素ｃ０（τ，κ，ι）を数１６１に示すように生成する。
【数１６１】
2014029415.tif 000063
暗号化データ生成部２３０は、処理装置により、属性情報Γに含まれる各整数ｔについて、暗号文ｃｔΓの要素ｃｔ（τ，κ，ι）を数１６２に示すように生成する。
【数１６２】
2014029415.tif 000064
暗号化データ生成部２３０は、処理装置により、暗号文ｃｔΓの要素ｃｄ＋１を数１６３に示すように生成する。
【数１６３】
2014029415.tif 000065
【００８７】
つまり、（Ｓ３０１）から（Ｓ３０３）において、暗号化装置２００は、数１６４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔΓを生成する。そして、（Ｓ３０４）で、暗号化装置２００は生成した暗号文ｃｔΓを復号装置３００へ送信する。
【数１６４】
2014029415.tif 000066
【００８８】
以上のように、実施の形態３に係る暗号システム１０は、実施の形態２で説明した関数型暗号方式に比べ、基底の数が多くなる代わりに、各基底の次元数が少ない関数型暗号方式を実現する。
【００８９】
なお、上記説明では、ＫＰ−ＦＥ方式について説明した。しかし、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムをそれぞれ数１６５から数１６７に示すようにすることにより、ＣＰ−ＦＥ方式とすることも可能である。なお、Ｓｅｔｕｐアルゴリズムは、ＫＰ−ＦＥ方式とＣＰ−ＦＥ方式とで同じである。また、Ｄｅｃアルゴリズムは、数１４８に示すＤｅｃアルゴリズムと同じである。
【数１６５】
2014029415.tif 000067
【数１６６】
2014029415.tif 000068
【数１６７】
2014029415.tif 000069
【００９０】
また、上記説明では、関数型暗号方式について説明した。しかし、Ｓｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムをそれぞれ数１６８から数１７１に示すようにすることにより、属性ベース暗号方式とすることも可能である。なお、属性ベース暗号方式の場合、Ｓｅｔｕｐアルゴリズムにおいて、ｎｔは２である。Ｄｅｃアルゴリズムは、数１５３に示すＤｅｃアルゴリズムと同じである。
【数１６８】
2014029415.tif 000070
【数１６９】
2014029415.tif 000071
【数１７０】
2014029415.tif 000072
【数１７１】
2014029415.tif 000073
同様に、数１６５から数１６７に示すＣＰ−ＦＥ方式を属性ベース暗号方式に変更することも可能である。
【００９１】
また、上記説明では、Ｎ０にｎ０＋ｕ０＋ｗ０＋ｚ０を設定し、Ｎｔにｎｔ＋ｕｔ＋ｗｔ＋ｚｔを設定した。ここで、例えば、ｕ０＝ｎ０，ｗ０＝ｎ０，ｚ０＝２として、Ｎ０にｎ０＋ｎ０＋ｎ０＋２＝３ｎ０＋２（ｎ０＝１のため、Ｎ０＝５）とし、ｕｔ＝ｎｔ，ｗｔ＝ｎｔ，ｚｔ＝１として、Ｎｔにｎｔ＋ｎｔ＋ｎｔ＋１＝３ｎｔ＋１としてもよい。
【００９２】
実施の形態４．
実施の形態２，３では、目標多項式ｄ（ｘ）を因数分解した多項式ｄτ（ｘ）ｆτ毎に、多項式ｄτ（ｘ）κで多項式ａｉ（ｘ）を割った余りを設定した要素と、多項式ｄτ（ｘ）ｆτ−κで多項式ｂｉ（ｘ）を割った余りを設定した要素とを、鍵要素とした。
実施の形態４では、目標多項式ｄ（ｘ）を因数分解した多項式ｄτ（ｘ）ｆτ毎に、多項式ｄτ（ｘ）κに乱数値γを代入した要素と、多項式ｄτ（ｘ）ｆτ−κに乱数値γを代入した要素とを、鍵要素とする。
【００９３】
実施の形態４に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、図５〜図７に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同じである。
実施の形態４に係るＳｅｔｕｐアルゴリズム、Ｅｎｃアルゴリズムは、実施の形態２に係るＳｅｔｕｐアルゴリズム、Ｅｎｃアルゴリズムと同じである。
実施の形態４に係るＤｅｃアルゴリズムの処理の流れは、図１１に示す実施の形態２に係るＤｅｃアルゴリズムの処理の流れと同じである。
図１２は、実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。
【００９４】
図１２に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ５０１）から（Ｓ５０３）までの処理は、図９に示す（Ｓ２０１）から（Ｓ２０３）までの処理と同じであり、（Ｓ５０５）の処理は、図９に示す（Ｓ２０６）との処理と同じである。
【００９５】
（Ｓ５０４：鍵要素生成ステップ）
鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆτの各整数κと、ι＝０，１の各整数ιと、ｊ＝１，．．．，μ＋１の各整数ｊとについて、復号鍵ｓｋＳの要素ｋ＊０，ｊ（τ，κ，ι）と要素ｋ＊０，μ＋１（τ，κ，ι）とを数１７２に示すように生成する。
【数１７２】
2014029415.tif 000074
鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆτの各整数κと、ι＝０，１の各整数ιと、ｉ＝１，．．．，Ｌの各整数ｉとについて、復号鍵ｓｋＳの要素ｋ＊ｉ（τ，κ，ι）を数１７３に示すように生成する。
【数１７３】
2014029415.tif 000075
ここで、ｅ→０，ｊ（τ，κ，ι）（ｊ＝１，．．．，μ＋１）は、１つの基底ベクトルの係数として１が設定され、他の基底ベクトルの係数として０が設定された２ｍｆｍａｘ次元のベクトルであって、係数として１が設定される基底ベクトルが（τ，κ，ι）毎に異なるベクトルである。
【００９６】
つまり、（Ｓ５０１）から（Ｓ５０４）において、鍵生成装置１００は、数１７４から数１７５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋＳを生成する。そして、（Ｓ５０５）で、鍵生成装置１００は、生成した復号鍵ｓｋＳを復号装置３００へ配布する。
【数１７４】
2014029415.tif 000076
【数１７５】
2014029415.tif 000077
【００９７】
図１１に基づき、Ｄｅｃアルゴリズムの処理について説明する。
（Ｓ４０１）から（Ｓ４０４）までの処理は、実施の形態２と同じである。
【００９８】
（Ｓ４０５：係数計算ステップ）
補完係数計算部３３０の係数計算部３３２は、処理装置により、数１７６となる係数（α１，．．．，αＬ）と、係数（β１，．．．，βＬ）と、次数κとを計算する。
【数１７６】
2014029415.tif 000078
ここで、Ｉ（ρ，Γ）に含まれない全てのｉについては、αｉ＝０＝βｉである。また、τ＝１，．．．，ｍ及びι＝０，１の全ての整数τ，ιについてｈτ，κ，ι（ｘ）：＝ｈτ，κ，ι，０＋ｈτ，κ，ι，１ｘ＋・・・＋ｈτ，κ，ι，μｘμである。
【００９９】
（Ｓ４０６：ペアリング演算ステップ）
復号部３４０のペアリング演算部３４１は、処理装置により、数１７７を計算して、セッション鍵Ｋτ，０，Ｋτ，１を生成する。
【数１７７】
2014029415.tif 000079
【０１００】
（Ｓ４０７：メッセージ計算ステップ）
メッセージ計算部３４２は、処理装置により、数１７８を計算して、メッセージｍｓｇ’（＝ｍｓｇ）を生成する。
【数１７８】
2014029415.tif 000080
なお、数１７９に示すように、数１７７を計算することによりｇＴζが得られる。そのため、数１７８を計算することにより、メッセージｍｓｇ’（＝ｍｓｇ）を得られる。
【数１７９】
2014029415.tif 000081
【０１０１】
つまり、（Ｓ４０１）から（Ｓ４０７）において、復号装置３００は、数１８０に示すＤｅｃアルゴリズムを実行して、メッセージｍｓｇ’（＝ｍｓｇ）を生成する。
【数１８０】
2014029415.tif 000082
【０１０２】
以上のように、実施の形態４に係る暗号システム１０は、多項式ｄτ（ｘ）κに乱数値γを代入した要素と、多項式ｄτ（ｘ）ｆτ−κに乱数値γを代入した要素とを、鍵要素として関数型暗号方式を実現する。
【０１０３】
なお、上記説明では、ＫＰ−ＦＥ方式について説明した。しかし、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズム、Ｄｅｃアルゴリズムをそれぞれ数１８１から数１８４に示すようにすることにより、ＣＰ−ＦＥ方式とすることも可能である。なお、Ｓｅｔｕｐアルゴリズムは、ＫＰ−ＦＥ方式とＣＰ−ＦＥ方式とで同じである。
【数１８１】
2014029415.tif 000083
【数１８２】
2014029415.tif 000084
【数１８３】
2014029415.tif 000085
【数１８４】
2014029415.tif 000086
【０１０４】
また、関数型暗号方式について説明した。しかし、ＫｅｙＧｅｎアルゴリズム、Ｄｅｃアルゴリズムをそれぞれ数１８５から数１８７に示すようにすることにより、属性ベース暗号方式とすることも可能である。なお、属性ベース暗号方式の場合、Ｓｅｔｕｐアルゴリズムにおいて、ｎｔは２ｍｆｍａｘｋｍａｘ＋２である。また、Ｓｅｔｕｐアルゴリズムは、数１４９に示すＳｅｔｕｐアルゴリズムと同じであり、Ｅｎｃアルゴリズムは、数１５２に示すＥｎｃアルゴリズムと同じである。
【数１８５】
2014029415.tif 000087
【数１８６】
2014029415.tif 000088
【数１８７】
2014029415.tif 000089
同様の変更を行うことにより、数１８１から数１８４に示すＣＰ−ＦＥ方式を属性ベース暗号方式に変更することも可能である。
【０１０５】
また、上記説明では、Ｎ０にｎ０＋ｕ０＋ｗ０＋ｚ０を設定し、Ｎｔにｎｔ＋ｕｔ＋ｗｔ＋ｚｔを設定した。ここで、例えば、ｕ０＝ｎ０，ｗ０＝ｎ０，ｚ０＝２として、Ｎ０にｎ０＋ｎ０＋ｎ０＋２＝３ｎ０＋２とし、ｕｔ＝ｎｔ，ｗｔ＝ｎｔ，ｚｔ＝２として、Ｎｔにｎｔ＋ｎｔ＋ｎｔ＋２＝３ｎｔ＋２としてもよい。
【０１０６】
また、上記説明では、実施の形態２に係る関数型暗号方式と同様に、復号鍵や暗号文が長くなる代わりに、基底の数が少ない関数型暗号方式とした。しかし、実施の形態３，４に係る関数型暗号方式に基づき、実施の形態４に係る関数型暗号方式を、実施の形態３に係る関数型暗号方式と同様に、基底の数が多くなる代わりに、各基底の次元数が少ない関数型暗号方式に容易に変形できる。
【０１０７】
また、以上の実施の形態では、ＫＰ−ＦＥ方式とＣＰ−ＦＥ方式とについて説明した。しかし、非特許文献４に記載されたＵｎｉｆｉｅｄ−Ｐｏｌｉｃｙ  ＦＥ（ＵＰ−ＦＥ）方式も、ＫＰ−ＦＥ方式とＣＰ−ＦＥ方式とから容易に構成することができる。
【０１０８】
実施の形態５．
以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。実施の形態５では、双対加群において暗号処理を実現する方法について説明する。
【０１０９】
つまり、以上の実施の形態では、素数位数ｑの巡回群において暗号プリミティブの処理を実現した。しかし、合成数Ｍを用いて数１８８のように環Ｒを表した場合、環Ｒを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数１８８】
2014029415.tif 000090
【０１１０】
以上の実施の形態で説明したアルゴリズムにおけるＦｑをＲに変更すれば、双対加群における暗号プリミティブの処理を実現することができる。
【０１１１】
なお、以上の実施の形態において、安全性の証明の観点から、ｉ＝１，．．．，Ｌの各整数ｉについてのρ（ｉ）は、それぞれ異なる識別情報ｔについての肯定形の組（ｔ，ｖ→）又は否定形の組¬（ｔ，ｖ→）であると限定してもよい。
言い替えると、ρ（ｉ）＝（ｔ，ｖ→）又はρ（ｉ）＝¬（ｔ，ｖ→）である場合に、関数ρ~を、ρ~（ｉ）＝ｔである｛１，．．．，Ｌ｝→｛１，．．．ｄ｝の写像であるとする。この場合、ρ~が単射であると限定してもよい。なお、ρ（ｉ）は、上述したアクセスストラクチャＳ：＝（Ｍ，ρ（ｉ））のρ（ｉ）である。
【０１１２】
次に、実施の形態における暗号処理システム１０（鍵生成装置１００、暗号化装置２００、復号装置３００）のハードウェア構成について説明する。
図１３は、鍵生成装置１００、暗号化装置２００、復号装置３００のハードウェア構成の一例を示す図である。
図１３に示すように、鍵生成装置１００、暗号化装置２００、復号装置３００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。
【０１１３】
ＲＯＭ９１３、磁気ディスク装置９２０は、不揮発性メモリの一例である。ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３とＲＡＭ９１４と磁気ディスク装置９２０とは、記憶装置（メモリ）の一例である。また、キーボード９０２、通信ボード９１５は、入力装置の一例である。また、通信ボード９１５は、通信装置の一例である。さらに、ＬＣＤ９０１は、表示装置の一例である。
【０１１４】
磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【０１１５】
プログラム群９２３には、上記の説明において「マスター鍵生成部１１０」、「マスター鍵記憶部１２０」、「情報入力部１３０」、「復号鍵生成部１４０」、「鍵配布部１５０」、「公開パラメータ取得部２１０」、「情報入力部２２０」、「暗号化データ生成部２３０」、「データ送信部２４０」、「情報取得部３１０」、「スパンプログラム計算部３２０」、「補完係数計算部３３０」、「復号部３４０」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、上記の説明において「公開パラメータｐｋ」、「マスター秘密鍵ｓｋ」、「復号鍵ｓｋＳ，ｓｋΓ」、「暗号文ｃｔΓ，ｃｔＳ」、「アクセスストラクチャＳ」、「属性情報」、「メッセージｍｓｇ」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【０１１６】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【０１１７】
１００  鍵生成装置、１１０  マスター鍵生成部、１２０  マスター鍵記憶部、１３０  情報入力部、１４０  復号鍵生成部、１４１  秘密情報生成部、１４２  鍵要素生成部、１５０  鍵配布部、２００  暗号化装置、２１０  公開パラメータ取得部、２２０  情報入力部、２３０  暗号化データ生成部、２４０  データ送信部、３００  復号装置、３１１  復号鍵取得部、３１２  暗号文取得部、３２０  スパンプログラム計算部、３３０  補完係数計算部、３３１  多項式選択部、３３２  係数計算部、３４０  復号部、３４１  ペアリング演算部、３４２  メッセージ計算部。
【図１】
2014029415.tif 000091
【図２】
2014029415.tif 000092
【図３】
2014029415.tif 000093
【図４】
2014029415.tif 000094
【図５】
2014029415.tif 000095
【図６】
2014029415.tif 000096
【図７】
2014029415.tif 000097
【図８】
2014029415.tif 000098
【図９】
2014029415.tif 000099
【図１０】
2014029415.tif 000100
【図１１】
2014029415.tif 000101
【図１２】
2014029415.tif 000102
【図１３】
2014029415.tif 000103