WO2014021102A1

WO2014021102A1 - 暗号システム、暗号方法、暗号プログラム及び復号装置

Info

Publication number: WO2014021102A1
Application number: PCT/JP2013/069368
Authority: WO
Inventors: 克幸高島; 岡本　龍明
Original assignee: Mitsubishi Electric Corp; Nippon Telegraph and Telephone Corp
Current assignee: Mitsubishi Electric Corp; NTT Inc
Priority date: 2012-07-31
Filing date: 2013-07-17
Publication date: 2014-02-06
Anticipated expiration: 2015-01-31
Also published as: US9413531B2; ES2645463T3; KR101606317B1; JP5814880B2; CN104620305A; JP2014029415A; EP2881930B1; KR20150015518A; CN104620305B; EP2881930A4; EP2881930A1; US20150098566A1

Abstract

　パラメータΦが設定された暗号化鍵ｅｋをパラメータΨが設定された復号鍵ｄｋで復号する場合に、関係Ｒ（Φ，Ψ）が成立する場合に限り、復号鍵ｄｋは暗号化鍵ｅｋで暗号化された暗号文を復号することができる関数型暗号方式において、関係Ｒとして表現できる範囲を広くすることを目的とする。暗号システム１０は、多項式ｄ（ｘ）と複数の多項式Ｄ_ｉ（ｘ）と述語情報とを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文とし、他方を復号鍵とする。復号装置３００は、述語情報と属性情報とに基づき、複数の多項式Ｄ_ｉ（ｘ）から少なくとも一部の多項式Ｄ_ｉ（ｘ）を選択し、選択した多項式Ｄ_ｉ（ｘ）に係数Δ_ｉを掛けた多項式Δ_ｉＤ_ｉ（ｘ）に基づき構成される多項式を、多項式ｄ（ｘ）で割り切れるようにする係数Δ_ｉを計算する。復号装置３００は、計算した係数Δ_ｉに基づき、前記暗号文を復号する。

Description

暗号システム、暗号方法、暗号プログラム及び復号装置

　この発明は、２次スパンプログラムの考えを利用した関数型暗号方式に関する。

　関数型暗号方式は、暗号化鍵ｅｋと、復号鍵ｄｋとの間の関係をより高度化し、より柔軟にした暗号方式である。
　関数型暗号方式において、暗号化鍵ｅｋと復号鍵ｄｋとには、それぞれ、パラメータΦとパラメータΨとが設定される。そして、関係Ｒ（Φ，Ψ）が成立する場合に限り、復号鍵ｄｋは暗号化鍵ｅｋで暗号化された暗号文を復号することができる。

　非特許文献３には、関数型暗号方式についての記載がある。

　非特許文献６には、２次スパンプログラムについての記載がある。

Ｏｋａｍｏｔｏ，　Ｔ．，　Ｔａｋａｓｈｉｍａ，　Ｋ．：　Ｈｏｍｏｍｏｒｐｈｉｃ　ｅｎｃｒｙｐｔｉｏｎ　ａｎｄ　ｓｉｇｎａｔｕｒｅｓ　ｆｒｏｍ　ｖｅｃｔｏｒ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ．　Ｉｎ：　Ｇａｌｂｒａｉｔｈ，　Ｓ．Ｄ．，　Ｐａｔｅｒｓｏｎ，　Ｋ．Ｇ．　（ｅｄｓ．）　Ｐａｉｒｉｎｇ　２００８．　ＬＮＣＳ，　ｖｏｌ．　５２０９，　ｐｐ．　５７－７４，　Ｓｐｒｉｎｇｅｒ　Ｈｅｉｄｅｌｂｅｒｇ　（２００８）Ｏｋａｍｏｔｏ，　Ｔ．，　Ｔａｋａｓｈｉｍａ，　Ｋ．：　Ｈｉｅｒａｒｃｈｉｃａｌ　ｐｒｅｄｉｃａｔｅ　ｅｎｃｒｙｐｔｉｏｎ　ｆｏｒ　ｉｎｎｅｒ－ｐｒｏｄｕｃｔｓ，　Ｉｎ：　ＡＳＩＡＣＲＹＰＴ　２００９，　Ｓｐｒｉｎｇｅｒ　Ｈｅｉｄｅｌｂｅｒｇ　（２００９）Ｏｋａｍｏｔｏ，　Ｔ．，　Ｔａｋａｓｈｉｍａ，　Ｋ．：　Ｆｕｌｌｙ　ｓｅｃｕｒｅ　ｆｕｎｃｔｉｏｎａｌ　ｅｎｃｒｙｐｔｉｏｎ　ｗｉｔｈ　ｇｅｎｅｒａｌ　ｒｅｌａｔｉｏｎｓ　ｆｒｏｍ　ｔｈｅ　ｄｅｃｉｓｉｏｎａｌ　ｌｉｎｅａｒ　ａｓｓｕｍｐｔｉｏｎ．　Ｉｎ：　Ｒａｂｉｎ，　Ｔ．　（ｅｄ．）　ＣＲＹＰＴＯ　２０１０．　ＬＮＣＳ，　ｖｏｌ．　６２２３，　ｐｐ．　１９１－２０８．　Ｓｐｒｉｎｇｅｒ　Ｈｅｉｄｅｌｂｅｒｇ　（２０１０）．　Ｆｕｌｌ　ｖｅｒｓｉｏｎ　ｉｓ　ａｖａｉｌａｂｌｅ　ａｔ　ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１０／５６３Ｏｋａｍｏｔｏ，　Ｔ．，　Ｔａｋａｓｈｉｍａ，　Ｋ．：　Ｅｆｆｉｃｉｅｎｔ　ａｔｔｒｉｂｕｔｅ－ｂａｓｅｄ　ｓｉｇｎａｔｕｒｅｓ　ｆｏｒ　ｎｏｎ－ｍｏｎｏｔｏｎｅ　ｐｒｅｄｉｃａｔｅｓ　ｉｎ　ｔｈｅ　ｓｔａｎｄａｒｄ　ｍｏｄｅｌ，　Ｉｎ：　ＰＫＣ　２０１１，　Ｓｐｒｉｎｇｅｒ　Ｈｅｉｄｅｌｂｅｒｇ　（２０１１）Ｏｋａｍｏｔｏ，　Ｔ．，　Ｔａｋａｓｈｉｍａ，　Ｋ．：Ｄｅｃｅｎｔｒａｌｉｚｅｄ　Ａｔｔｒｉｂｕｔｅ－Ｂａｓｅｄ　Ｓｉｇｎａｔｕｒｅｓ　ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１１／７０１Ｒｏｓａｒｉｏ　Ｇｅｎｎａｒｏ　ａｎｄ　Ｃｒａｉｇ　Ｇｅｎｔｒｙ　ａｎｄ　Ｂｒｙａｎ　Ｐａｒｎｏ　ａｎｄ　Ｍａｒｉａｎａ　Ｒａｙｋｏｖａ：　Ｑｕａｄｒａｔｉｃ　Ｓｐａｎ　Ｐｒｏｇｒａｍｓ　ａｎｄ　Ｓｕｃｃｉｎｃｔ　ＮＩＺＫｓ　ｗｉｔｈｏｕｔ　ＰＣＰｓ　ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１２／２１５

　非特許文献３に記載された関数型暗号方式は、１次スパンプログラムを利用した方式である。この関数型暗号方式では、関係Ｒとして表現できる範囲に限界がある。
　この発明は、２次スパンプログラムの考えを利用することにより、関係Ｒとして表現できる範囲を広くすることが可能な関数型暗号方式を提供することを目的とする。

　この発明に係る暗号システムは、
　２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文として生成する暗号化装置と、
　前記第１情報と前記第２情報とのうちの他方を復号鍵とし、前記２次スパンプログラムが前記属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号装置と
を備えることを特徴とする。

　この発明に係る暗号システムでは、２次スパンプログラムの考えを利用することにより、関係Ｒとして表現できる範囲が理想化された範囲とすることが可能である。

２次スパンプログラムの説明図。部分集合Ｉ_ｕの説明図。ＫＰ－ＦＥ方式を実行する暗号システム１０の構成図。ＣＰ－ＦＥ方式を実行する暗号システム１０の構成図。実施の形態２に係る鍵生成装置１００の構成図。実施の形態２に係る暗号化装置２００の構成図。実施の形態２に係る復号装置３００の構成図。実施の形態２に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。実施の形態２に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。実施の形態２に係るＥｎｃアルゴリズムの処理を示すフローチャート。実施の形態２に係るＤｅｃアルゴリズムの処理を示すフローチャート。実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。鍵生成装置１００、暗号化装置２００、復号装置３００のハードウェア構成の一例を示す図。

　以下、図に基づき、発明の実施の形態を説明する。
　以下の説明において、処理装置は後述するＣＰＵ９１１等である。記憶装置は後述するＲＯＭ９１３、ＲＡＭ９１４、磁気ディスク９２０等である。通信装置は後述する通信ボード９１５等である。入力装置は後述するキーボード９０２、通信ボード９１５等である。つまり、処理装置、記憶装置、通信装置、入力装置はハードウェアである。

　以下の説明における記法について説明する。
　Ａがランダムな変数または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。

　Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。

　数１０３は、ｙがｚにより定義された集合であること、又はｙがｚを代入された集合であることを表す。

　ａが定数であるとき、数１０４は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。

　数１０５、つまりＦ_ｑは、位数ｑの有限体を示す。

　ベクトル表記は、有限体Ｆ_ｑにおけるベクトル表示を表す。つまり、数１０６である。

　数１０７は、数１０８に示す２つのベクトルｘ^→とｖ^→との数１０９に示す内積を表す。

　Ｘ^Ｔは、行列Ｘの転置行列を表す。
　ｂ_ｉ（ｉ＝１，．．．，ｎ）が空間Ｖのベクトルの要素であるとき、つまり、数１１０であるとき、数１１１は、数１１２によって生成される部分空間を表す。

　数１１３に示す基底Ｂと基底Ｂ^＊とに対して、数１１４である。

　また、以下の説明において、“Ｖｔ”が下付き又は上付きで示されている場合、このＶｔはＶ_ｔを意味する。同様に、“δｉ，ｊ”が上付きで示されている場合、このδｉ，ｊは、δ_ｉ，ｊを意味する。同様に、“ｆτ”、“κτ”が上付きで示されている場合、このｆτは、ｆ_τを意味し、このκτはκ_τを意味する。
　また、ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。

　また、以下の説明において、暗号処理は、鍵生成処理、暗号化処理、復号処理を含む。

　実施の形態１．
　この実施の形態では、２次スパンプログラムを用いた関数型暗号方式の基礎となる概念と、２次スパンプログラムを用いた関数型暗号方式の概要とを説明する。
　第１に、関数型暗号方式を実現するための空間である「双対ペアリングベクトル空間（Ｄｕａｌ　Ｐａｉｒｉｎｇ　Ｖｅｃｔｏｒ　Ｓｐａｃｅｓ，ＤＰＶＳ）」という豊かな数学的構造を有する空間を説明する。
　第２に、関数型暗号方式を実現するための概念を説明する。ここでは、「２次スパンプログラム」、「属性情報の等号と２次スパンプログラム」、「秘密分散方式」について説明する。
　第３に、２次スパンプログラムを用いた関数型暗号方式の概要について説明する。

　＜第１．双対ペアリングベクトル空間＞
　まず、対称双線形ペアリング群について説明する。
　対称双線形ペアリング群（ｑ，Ｇ，Ｇ^Ｔ，ｇ，ｅ）は、素数ｑと、位数ｑの巡回加法群Ｇと、位数ｑの巡回乗法群Ｇ^Ｔと、ｇ≠０∈Ｇと、多項式時間で計算可能な非退化双線形ペアリング（Ｎｏｎｄｅｇｅｎｅｒａｔｅ　Ｂｉｌｉｎｅａｒ　Ｐａｉｒｉｎｇ）ｅ：Ｇ×Ｇ→Ｇ_Ｔとの組である。非退化双線形ペアリングは、ｅ（ｓｇ，ｔｇ）＝ｅ（ｇ，ｇ）^ｓｔであり、ｅ（ｇ，ｇ）≠１である。
　以下の説明において、Ｇ_ｂｐｇを、１^λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータｐａｒａｍ_Ｇ：＝（ｑ，Ｇ，Ｇ_Ｔ，ｇ，ｅ）の値を出力するアルゴリズムとする。

　次に、双対ペアリングベクトル空間について説明する。
　双対ペアリングベクトル空間（ｑ，Ｖ，Ｇ_Ｔ，Ａ，ｅ）は、対称双線形ペアリング群（ｐａｒａｍ_Ｇ：＝（ｑ，Ｇ，Ｇ_Ｔ，ｇ，ｅ））の直積によって構成することができる。双対ペアリングベクトル空間（ｑ，Ｖ，Ｇ_Ｔ，Ａ，ｅ）は、素数ｑ、数１１５に示すＦ_ｑ上のＮ次元ベクトル空間Ｖ、位数ｑの巡回群Ｇ_Ｔ、空間Ｖの標準基底Ａ：＝（ａ_１，．．．，ａ_Ｎ）の組であり、以下の演算（１）（２）を有する。ここで、ａ_ｉは、数１１６に示す通りである。

　演算（１）：非退化双線形ペアリング
　空間Ｖにおけるペアリングは、数１１７によって定義される。

　これは、非退化双線形である。つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）^ｓｔであり、全てのｙ∈Ｖに対して、ｅ（ｘ，ｙ）＝１の場合、ｘ＝０である。また、全てのｉとｊとに対して、ｅ（ａ_ｉ，ａ_ｊ）＝ｅ（ｇ，ｇ）^δｉ，ｊである。ここで、ｉ＝ｊであれば、δ_ｉ，ｊ＝１であり、ｉ≠ｊであれば、δ_ｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈Ｇ_Ｔである。

　演算（２）：ディストーション写像
　数１１８に示す空間Ｖにおける線形変換φ_ｉ，ｊは、数１１９を行うことができる。

　ここで、線形変換φ_ｉ，ｊをディストーション写像と呼ぶ。

　以下の説明において、Ｇ_ｄｐｖｓを、１^λ（λ∈自然数）、Ｎ∈自然数、双線形ペアリング群のパラメータｐａｒａｍ_Ｇ：＝（ｑ，Ｇ，Ｇ_Ｔ，ｇ，ｅ）の値を入力として、セキュリティパラメータがλであり、Ｎ次元の空間Ｖとする双対ペアリングベクトル空間のパラメータｐａｒａｍ_Ｖ：＝（ｑ，Ｖ，Ｇ_Ｔ，Ａ，ｅ）の値を出力するアルゴリズムとする。

　なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。

　＜第２．関数型暗号を実現するための概念＞
　＜第２－１．２次スパンプログラム＞
　図１は、２次スパンプログラムの説明図である。
　体Ｆ_ｑにおける２次スパンプログラムは、２つの多項式の集合Ａ＝｛ａ_ｉ（ｘ）｜ｉ∈｛０，．．．，Ｌ｝｝及び集合Ｂ＝｛ｂ_ｉ（ｘ）｜ｉ∈｛０，．．．，Ｌ｝｝と、目標多項式ｄ（ｘ）とを含む。また、２次スパンプログラムは、集合Ｉ：＝｛１，．．．，Ｌ｝のラベルρを含む。全てのラベルρ_i（ｉ＝１，．．．，Ｌ）は、｛ｐ_０，ｐ_１，．．．，ｐ_ｎ，￢ｐ_１，．．．，￢ｐ_ｎ｝のいずれか１つのリテラルへ対応付けられる。つまり、ρ：Ｉ→｛ｐ_０，ｐ_１，．．．，ｐ_ｎ，￢ｐ_１，．．．，￢ｐ_ｎ｝である。

　入力ｕ：＝（ｕ_１，．．．，ｕ_ｎ）∈｛０，１｝^ｎに対して、ｊ＝１，．．．，ｎの各整数ｊについて、Ｔ（ｐ_ｊ）：＝ｕ_ｊ及びＴ（￢ｐ_ｊ）：＝￢ｕ_ｊにより、リテラルの真理値Ｔが設定される。また、どんな入力ｕに対しても、ｐ_０の真理値Ｔは１が設定される。つまり、Ｔ（ｐ_０）：＝１である。
　集合Ｉの部分集合Ｉ_ｕは、入力ｕにより１が設定されたラベルの要素から構成される。つまり、Ｉ_ｕ：＝｛ｉ∈Ｉ｜Ｔ（ｐ（ｉ）＝１）｝である。又は、Ｉ_ｕ：＝｛ｉ∈Ｉ｜［ρ（ｉ）＝ｐ_ｊ∧ｕ_ｊ＝１］∨［ρ（ｉ）＝￢ｐ_ｊ∧ｕ_ｊ＝０］∨［ρ（ｉ）＝ｐ_０］｝である。

　図２は、部分集合Ｉ_ｕの説明図である。
　なお、図２では、ｎ＝７，Ｌ＝６としている。また、図２において、ラベルρは、ρ_１が￢ｐ_２に、ρ_２がｐ_１に、ρ_３がｐ_４に、ρ_４が￢ｐ_５に、ρ_５が￢ｐ_３に、ρ_６がｐ_５にそれぞれ対応付けられているとする。
　ここで、入力ｕ：＝（ｕ_１，．．．，ｕ_７）∈｛０，１｝^７が、ｕ_１＝１，ｕ_２＝０，ｕ_３＝１，ｕ_４＝０，ｕ_５＝０，ｕ_６＝１，ｕ_７＝１であるとする。この場合、部分集合Ｉ_ｕは、破線で囲んだリテラル（ｐ_１，ｐ_３，ｐ_６，ｐ_７，￢ｐ_２，￢ｐ_４，￢ｐ_５）に対応付けられているラベルρ_ｉの要素ｉから構成される。つまり、部分集合Ｉ_ｕは、ラベルρ_１，ρ_２，ρ_４の要素ｉから構成され、部分集合Ｉ_ｕ：＝｛ｉ＝１，２，４｝である。

　２次スパンプログラムは、目標多項式ｄ（ｘ）が数１２０を割り切るような体Ｆ_ｑ ^Ｌにおける（α_１，．．．，α_Ｌ）及び（β_１，．．．，β_Ｌ）の組であって、部分集合Ｉ_ｕに含まれない全てのｉに対してα_ｉ＝０＝β_ｉである（α_１，．．．，α_Ｌ）及び（β_１，．．．，β_Ｌ）の組が存在する場合に限り、入力ｕ∈｛０，１｝^ｎを受理する（又は、部分集合Ｉ_ｕを受理する）。そして、２次スパンプログラムは、他の場合には、入力ｕ∈｛０，１｝^ｎを拒絶する。

　つまり、２次スパンプログラムは、目標多項式ｄ（ｘ）が数１２１を割り切るようなｉ∈Ｉ_ｕについてのα_ｉ及びβ_ｉの組が存在する場合に限り、入力ｕ∈｛０，１｝^ｎを受理する。

　そして、２次スパンプログラムが入力ｕ∈｛０，１｝^ｎを受理する場合、ｉ∈Ｉ_ｕについてのα_ｉ及びβ_ｉの組を、多項式時間で計算することが可能である（非特許文献６参照）。

　図２に示す例であれば、２次スパンプログラムは、目標多項式ｄ（ｘ）が数１２２を割り切るようなｉ∈Ｉ_ｕ：＝｛ｉ＝１，２，４｝についてのα_ｉ及びβ_ｉの組が存在する場合に限り、入力ｕ∈｛０，１｝^ｎを受理する。

　＜第２－２．属性の内積と２次スパンプログラム＞
　Ｕ_ｔ（ｔ＝１，．．．，ｄでありＵ_ｔ⊂｛０，１｝^＊）は、部分全集合（ｓｕｂ－ｕｎｉｖｅｒｓｅ）であり、属性の集合である。そして、Ｕ_ｔは、それぞれ部分全集合の識別情報（ｔ）と、ｎ次元ベクトルで表された属性情報（ｖ^→）とを含む。つまり、Ｕ_ｔは、（ｔ，ｖ^→）である。ここで、ｔ∈｛１，．．．，ｄ｝であり、ｖ^→∈Ｆ_ｑ ^ｎである。

　Ｕ_ｔ＝（ｔ，ｖ^→）をｐとする。つまり、ｐ＝（ｔ，ｖ^→）である。ｐ_ｊ：＝（ｔ，ｖ^→ _ｊ）（ｊ＝１，．．．，ｎ；ｔ∈｛１，．．．，ｄ｝）による２次スパンプログラムＱ：＝（Ａ，Ｂ，ｄ（ｘ），ρ）における、部分集合Ｉ_ｕの決定方法について説明する。
　アクセスストラクチャＳを、ｐ_０及び｛ｐ_ｊ：＝（ｔ，ｖ^→ _ｊ）｝_{ｊ＝１，．．．，ｎ}を伴う２次スパンプログラムＱ：＝（Ａ，Ｂ，ｄ（ｘ），ρ）とする。つまり、ρ：｛１，．．．，Ｌ｝→｛ｐ_０，（ｔ，ｖ^→ _１），．．．，（ｔ，ｖ^→ _ｎ），￢（ｔ，ｖ^→ _１），．．．，￢（ｔ，ｖ^→ _ｎ）｝である。また、Γを属性集合とする。つまり、Γ：＝｛（ｔ，ｘ^→ _ｔ）｜ｘ^→ _ｔ∈Ｆ_ｑ ^ｎ，１≦ｔ≦ｄ｝である。ここで、ｔは、｛１，．．．，ｄ｝の部分集合であって、全インデックスである必要はない。
　属性集合ΓがアクセスストラクチャＳに与えられると、｛ｐ_０，ｐ_１，．．．，ｐ_ｎ，￢ｐ_１，．．．，￢ｐ_ｎ｝のリテラルの真理値Ｔは次のように決定される。ｐ_ｊ＝（ｔ，ｖ^→ _ｊ）かつ（ｔ，ｘ^→ _ｔ）∈Γかつｖ^→ _ｊ・ｘ^→ _ｔ＝０である場合に限り、Ｔ（ｐ_ｊ）：＝１になる。ｐ_ｊ＝￢（ｔ，ｖ^→ _ｊ）かつ（ｔ，ｘ^→ _ｊ）∈Γかつｖ^→ _ｊ・ｘ^→ _ｔ≠０である場合に限り、Ｔ（￢ｐ_ｊ）：＝１になる。Ｔ（ｐ_０）：＝１になる。他の場合には、真理値Ｔは０になる。
　そして、Ｉ_ｕ（＝Ｉ_{（ρ，Γ）}）：＝｛ｉ∈Ｉ｜Ｔ（ρ（ｉ））＝１｝、つまり、Ｉ_{（ρ，Γ）}：＝｛ｉ∈Ｉ｜［ρ（ｉ）＝（ｔ，ｖ^→ _ｊ）∧（ｔ，ｘ^→ _ｔ）∈Γ∧（ｖ^→ _ｊ・ｘ^→ _ｔ）＝０］∨［ρ（ｉ）＝￢（ｔ，ｖ^→ _ｊ）∧（ｔ，ｘ^→ _ｊ）∈Γ∧ｖ^→ _ｊ・ｘ^→ _ｔ≠０］∨［ρ（ｉ）＝ｐ_０］｝とする。

　＜第３．関数型暗号方式の概要＞
　復号鍵と暗号文との一方に上述したアクセスストラクチャＳを持たせ、他方に属性集合Γを持たせることにより、関数型暗号方式を構成する。

　アクセスストラクチャＳを復号鍵に持たせた関数型暗号方式をＫｅｙ－Ｐｏｌｉｃｙ関数型暗号（ＫＰ－ＦＥ）方式と呼び、アクセスストラクチャＳを暗号文に持たせた暗号方式をＣｉｐｈｅｒｔｅｘｔ－Ｐｏｌｉｃｙ関数型暗号（ＣＰ－ＦＥ）方式と呼ぶ。
　ＫＰ－ＦＥ方式及びＣＰ－ＦＥ方式の構成と、各方式を実行する暗号システム１０の構成とを説明する。

　＜第３－１．ＫＰ－ＦＥ方式＞
　ＫＰ－ＦＥ方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
　（Ｓｅｔｕｐ）
　Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
　（ＫｅｙＧｅｎ）
　ＫｅｙＧｅｎアルゴリズムは、アクセスストラクチャＳと、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、復号鍵ｓｋ_Ｓを出力する確率的アルゴリズムである。
　（Ｅｎｃ）
　Ｅｎｃアルゴリズムは、メッセージｍｓｇと、属性の集合であるΓ：＝｛（ｔ，ｘ^→ _ｔ）｜ｘ^→ _ｔ∈Ｆ_ｑ ^ｎ，１≦ｔ≦ｄ｝と、公開パラメータｐｋとを入力として、暗号文ｃｔ_Γを出力する確率的アルゴリズムである。
　（Ｄｅｃ）
　Ｄｅｃアルゴリズムは、属性の集合であるΓの下で暗号化された暗号文ｃｔ_Γと、アクセスストラクチャＳに対する復号鍵ｓｋ_Ｓと、公開パラメータｐｋとを入力として、メッセージｍｓｇ、又は、識別情報⊥を出力するアルゴリズムである。

　図３は、ＫＰ－ＦＥ方式を実行する暗号システム１０の構成図である。
　暗号システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００を備える。
　鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、アクセスストラクチャＳを入力としてＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋ_Ｓを生成して復号装置３００へ秘密裡に配布する。
　暗号化装置２００は、メッセージｍｓｇと、属性の集合Γと、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔ_Γを生成する。暗号化装置２００は、生成した暗号文ｃｔ_Γを復号装置３００へ送信する。
　復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋ_Ｓと、暗号文ｃｔ_Γとを入力としてＤｅｃアルゴリズムを実行して、メッセージｍｓｇ又は識別情報⊥を出力する。

　＜第３－２．ＣＰ－ＦＥ方式＞
　ＣＰ－ＦＥ方式は、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
　（Ｓｅｔｕｐ）
　Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター鍵ｓｋとを出力する確率的アルゴリズムである。
　（ＫｅｙＧｅｎ）
　ＫｅｙＧｅｎアルゴリズムは、属性の集合であるΓ：＝｛（ｔ，ｘ^→ _ｔ）｜ｘ^→ _ｔ∈Ｆ_ｑ ^ｎ，１≦ｔ≦ｄ｝と、公開パラメータｐｋと、マスター鍵ｓｋとを入力として、復号鍵ｓｋ_Γを出力する確率的アルゴリズムである。
　（Ｅｎｃ）
　Ｅｎｃアルゴリズムは、メッセージｍｓｇと、アクセスストラクチャＳと、公開パラメータｐｋとを入力として、暗号文ｃｔ_Ｓを出力する確率的アルゴリズムである。
　（Ｄｅｃ）
　Ｄｅｃアルゴリズムは、アクセスストラクチャＳの下で暗号化された暗号文ｃｔ_Ｓと、属性の集合であるΓに対する復号鍵ｓｋ_Γと、公開パラメータｐｋとを入力として、メッセージｍｓｇ、又は、識別情報⊥を出力するアルゴリズムである。

　図４は、ＣＰ－ＦＥ方式を実行する暗号システム１０の構成図である。
　暗号システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００を備える。
　鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、属性の集合Γを入力としてＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋ_Γを生成して復号装置３００へ秘密裡に配布する。
　暗号化装置２００は、メッセージｍｓｇと、アクセスストラクチャＳと、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔ_Ｓを生成する。暗号化装置２００は、生成した暗号文ｃｔ_Ｓを復号装置３００へ送信する。
　復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋ_Γと、暗号文ｃｔ_Ｓとを入力としてＤｅｃアルゴリズムを実行して、メッセージｍｓｇ又は識別情報⊥を出力する。

　ＫＰ－ＦＥ方式及びＣＰ－ＦＥ方式のどちらにおいても、Ｄｅｃアルゴリズムでは、アクセスストラクチャＳと属性集合Γとに基づき、上述した方法により、部分集合Ｉ_{（ρ，Γ）}を選択し、さらに係数（α_１，．．．，α_Ｌ）及び係数（β_１，．．．，β_Ｌ）を特定する。そして、部分集合Ｉ_{（ρ，Γ）}と係数（α_１，．．．，α_Ｌ）及び係数（β_１，．．．，β_Ｌ）とに基づき、暗号文ｃｔ_Γ（又はｃｔ_Ｓ）を復号してメッセージｍｓｇを計算する。

　なお、Ｓｅｔｕｐアルゴリズムは、通常、システムのセットアップ時に１度だけ実行される。ＫｅｙＧｅｎアルゴリズムは、ユーザの復号鍵を生成する度に実行される。Ｅｎｃアルゴリズムは、メッセージｍｓｇを暗号化する度に実行される。Ｄｅｃアルゴリズムは、暗号文を復号する度に実行される。

　実施の形態１に係る暗号システム１０では、２次スパンプログラムに基づくアクセスストラクチャＳを用いて関数型暗号方式を構成する。これにより、関係Ｒとして表現できる範囲を理想化された範囲とすることが可能となる。

　実施の形態２．
　実施の形態２では、２次スパンプログラムを用いた関数型暗号方式の構成例について説明する。
　ここでは、ＫＰ－ＦＥ方式を例として説明する。

　図５は、実施の形態２に係る鍵生成装置１００の構成図である。図６は、実施の形態２に係る暗号化装置２００の構成図である。図７は、実施の形態２に係る復号装置３００の構成図である。
　図８と図９とは、鍵生成装置１００の動作を示すフローチャートである。図８はＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図９はＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図１０は、暗号化装置２００の動作を示すフローチャートであり、Ｅｎｃアルゴリズムの処理を示すフローチャートである。図１１は、復号装置３００の動作を示すフローチャートであり、Ｄｅｃアルゴリズムの処理を示すフローチャートである。

　鍵生成装置１００の機能と動作とについて説明する。
　鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵配布部１５０を備える。また、復号鍵生成部１４０は、秘密情報生成部１４１、鍵要素生成部１４２を備える。

　図８に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
　（Ｓ１０１：正規直交基底生成ステップ）
　マスター鍵生成部１１０は、処理装置により、数１２３を計算して、パラメータｐａｒａｍと、基底Ｂ_０及び基底Ｂ^＊ _０と、基底Ｂ_ｔ及び基底Ｂ^＊ _ｔとを生成する。

　つまり、マスター鍵生成部１１０は以下の処理を実行する。
　（１）マスター鍵生成部１１０は、入力装置により、セキュリティパラメータλ（１^λ）を入力する。
　（２）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλを入力としてアルゴリズムＧ_ｂｐｇを実行して、双線形ペアリング群のパラメータｐａｒａｍ_Ｇ：＝（ｑ，Ｇ，Ｇ_Ｔ，ｇ，ｅ）の値を生成する。
　（３）マスター鍵生成部１１０は、処理装置により、乱数ψを生成する。
　（４）マスター鍵生成部１１０は、Ｎ_０にｎ_０＋ｕ_０＋ｗ_０＋ｚ_０を設定し、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の各整数ｔについて、Ｎ_ｔにｎ_ｔ＋ｕ_ｔ＋ｗ_ｔ＋ｚ_ｔを設定する。ここで、ｎ_０は２ｍｆ_ｍａｘ＋１であり、ｎ_ｔは２ｍｆ_ｍａｘｋ_ｍａｘ＋ｎである。ｍは、目標多項式ｄ（ｘ）を因数分解した場合の因数の数である。ｆ_ｍａｘは、目標多項式ｄ（ｘ）を因数分解した場合の因数の次数の最大値（後述するｆ_τの最大値）である。ｋ_ｍａｘは、１つの識別情報ｔに対応付けられるラベルρの個数の最大値である。ｎは１以上の整数であり、ｕ_０，ｗ_０，ｚ_０，ｕ_ｔ，ｗ_ｔ，ｚ_ｔはそれぞれ０以上の整数である。

　続いて、マスター鍵生成部１１０は、ｔ＝０，．．．，ｄの各整数ｔについて以下の（５）から（９）までの処理を実行する。
　（５）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλと、（４）で設定したＮ_ｔと、（２）で生成したｐａｒａｍ_Ｇ：＝（ｑ，Ｇ，Ｇ_Ｔ，ｇ，ｅ）の値とを入力としてアルゴリズムＧ_ｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍ_Ｖｔ：＝（ｑ，Ｖ_ｔ，Ｇ_Ｔ，Ａ_ｔ，ｅ）の値を生成する。
　（６）マスター鍵生成部１１０は、処理装置により、（４）で設定したＮ_ｔと、Ｆ_ｑとを入力として、線形変換Ｘ_ｔ：＝（χ_{ｔ，ｉ，ｊ}）_ｉ，ｊをランダムに生成する。なお、ＧＬは、Ｇｅｎｅｒａｌ　Ｌｉｎｅａｒの略である。つまり、ＧＬは、一般線形群であり、行列式が０でない正方行列の集合であり、乗法に関し群である。また、（χ_{ｔ，ｉ，ｊ}）_ｉ，ｊは、行列χ_{ｔ，ｉ，ｊ}の添え字ｉ，ｊに関する行列という意味であり、ここでは、ｉ，ｊ＝１，．．．，Ｎ_ｔである。
　（７）マスター鍵生成部１１０は、処理装置により、乱数ψと線形変換Ｘ_ｔとに基づき、Ｘ^＊ _ｔ：＝（ν_{ｔ，ｉ，ｊ}）_ｉ，ｊ：＝ψ・（Ｘ_ｔ ^Ｔ）^－１を生成する。なお、（ν_{ｔ，ｉ，ｊ}）_ｉ，ｊも（χ_{ｔ，ｉ，ｊ}）_ｉ，ｊと同様に、行列ν_{ｔ，ｉ，ｊ}の添え字ｉ，ｊに関する行列という意味であり、ここでは、ｉ，ｊ＝１，．．．，Ｎ_ｔである。
　（８）マスター鍵生成部１１０は、処理装置により、（６）で生成した線形変換Ｘ_ｔに基づき、（５）で生成した標準基底Ａ_ｔから基底Ｂ_ｔを生成する。なお、ｘ^→ _ｔ，ｉとは、線形変換Ｘ_ｔのｉ行目を示す。
　（９）マスター鍵生成部１１０は、処理装置により、（７）で生成した線形変換Ｘ^＊ _ｔに基づき、（５）で生成した標準基底Ａ_ｔから基底Ｂ^＊ _ｔを生成する。なお、ｖ^→ _ｔ，ｉとは、線形変換Ｘ^＊ _ｔのｉ行目を示す。
　（１０）マスター鍵生成部１１０は、処理装置により、ｇ_Ｔにｅ（ｇ，ｇ）^ψを設定する。また、マスター鍵生成部１１０は、ｐａｒａｍに（５）で生成した｛ｐａｒａｍ_Ｖｔ｝_{ｔ＝０，．．．，ｄ}と、ｇ_Ｔとを設定する。

　すなわち、（Ｓ１０１）で、マスター鍵生成部１１０は、数１２４に示すアルゴリズムＧ_ｏｂを実行して、ｐａｒａｍと、基底Ｂ_０及び基底Ｂ^＊ _０と、基底Ｂ_ｔ及び基底Ｂ^＊ _ｔとを生成する。

　（Ｓ１０２：公開パラメータ生成ステップ）
　マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ_０の部分基底Ｂ＾_０と、基底Ｂ_ｔの部分基底Ｂ＾_ｔとを数１２５に示すように生成する。

　マスター鍵生成部１１０は、生成した部分基底Ｂ＾_０及び部分基底Ｂ＾_ｔと、（Ｓ１０１）で入力されたセキュリティパラメータλと、（Ｓ１０１）で生成したｐａｒａｍとを合わせて、公開パラメータｐｋとする。

　（Ｓ１０３：マスター鍵生成ステップ）
　マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ^＊ _０の部分基底Ｂ＾^＊ _０と、基底Ｂ^＊ _ｔの部分基底Ｂ＾^＊ _ｔとを数１２６に示すように生成する。

　マスター鍵生成部１１０は、生成した部分基底Ｂ＾^＊ _０と部分基底Ｂ＾^＊ _ｔとをマスター鍵ｓｋとする。

　（Ｓ１０４：マスター鍵記憶ステップ）
　マスター鍵記憶部１２０は、（Ｓ１０２）で生成した公開パラメータｐｋを記憶装置に記憶する。また、マスター鍵記憶部１２０は、（Ｓ１０３）で生成したマスター鍵ｓｋを記憶装置に記憶する。

　つまり、（Ｓ１０１）から（Ｓ１０３）において、鍵生成装置１００は、数１２７に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ１０４）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。
　なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。

　図９に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
　（Ｓ２０１：情報入力ステップ）
　情報入力部１３０は、入力装置により、上述したアクセスストラクチャＳ：＝（Ａ，Ｂ，ｄ（ｘ），ρ）を入力する。なお、ρは、例えば、復号鍵ｓｋ_Ｓの使用者の属性情報が設定されている。また、アクセスストラクチャＳに含まれる目標多項式ｄ（ｘ）は、数１２８に示すように、τ＝１，．．．，ｍのｍ個の因数ｄ_τ（ｘ）^ｆτに因数分解可能である。

　（Ｓ２０２：秘密情報π生成ステップ）
　秘密情報生成部１４１は、処理装置により、秘密情報π_{τ，κ，０}及び秘密情報π_{τ，κ，１}を数１２９に示すように生成する。

　（Ｓ２０３：秘密情報χ生成ステップ）
　秘密情報生成部１４１は、処理装置により、秘密情報χ_{τ，κ，０}及び秘密情報χ_{τ，κ，１}を数１３０に示すように生成する。

　（Ｓ２０４：秘密情報ｓ生成ステップ）
　秘密情報生成部１４１は、処理装置により、秘密情報ｓ_０ ^{（τ，κ，０）}及び秘密情報ｓ_０ ^{（τ，κ，１）}と、秘密情報ｓ_ｉ ^{（τ，κ，０）}及び秘密情報ｓ_ｉ ^{（τ，κ，１）}とを数１３１に示すように生成する。

　（Ｓ２０５：鍵要素生成ステップ）
　鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆ_τの各整数κと、ι＝０，１の各整数ιとについて、復号鍵ｓｋ_Ｓの要素ｋ^＊ _０ ^{（τ，κ，ι）}を数１３２に示すように生成する。

　なお、上述したように、数１１３に示す基底Ｂと基底Ｂ^＊とに対して、数１１４である。したがって、数１３２は、基底Ｂ^＊ _０の基底ベクトルｂ^＊ _０，１の係数としてｓ_０ ^{（τ，κ，ι）}＋π_τ，κ，ιを設定し、基底ベクトルｂ^＊ _{０，１＋１}，．．．，ｂ^＊ _{０，１＋ｎ０}の係数としてｅ^→ _０ ^{（τ，κ，ι）}を設定し、基底ベクトルｂ^＊ _{０，ｎ０＋１}，．．．，ｂ^＊ _{０，ｎ０＋ｕ０}の係数として０を設定し、基底ベクトルｂ^＊ _{０，ｎ０＋ｕ０＋１}，．．．，ｂ^＊ _{０，ｎ０＋ｕ０＋ｗ０}の係数としてη_０，１ ^{（τ，κ，ι）}，．．．，η_０，ｗ０ ^{（τ，κ，ι）}を設定し、基底ベクトルｂ^＊ _{０，ｎ０＋ｕ０＋ｗ０＋１}，．．．，ｂ^＊ _{０，ｎ０＋ｕ０＋ｗ０＋ｚ０}の係数として０を設定することを意味する。ここで、ｎ０，ｕ０，ｗ０，ｚ０はそれぞれｎ_０，ｕ_０，ｗ_０，ｚ_０のことである。
　また、ｅ^→ _０ ^{（τ，κ，ι）}は、１つの基底ベクトルの係数として１が設定され、他の基底ベクトルの係数として０が設定された２ｍｆ_ｍａｘ次元のベクトルであって、係数として１が設定される基底ベクトルが（τ，κ，ι）毎に異なるベクトルである。同様に、ｅ^→ _ｉ ^{（τ，κ，ι）}は、１つの基底ベクトルの係数として１が設定され、他の基底ベクトルの係数として０が設定された２ｍｆ_ｍａｘｋ_ｍａｘ次元のベクトルであって、係数として１が設定される基底ベクトルが（τ，κ，ι）毎に異なるベクトルである。
　また、ｅ^→ _１は、基底ベクトルｂ^＊ _ｔ，１の係数として１が設定され、他の基底ベクトルの係数として０が設定されたｎ次元のベクトルである。
　鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆ_τの各整数κと、ι＝０，１の各整数ιと、ｉ＝１，．．．，Ｌの各整数ｉとについて、復号鍵ｓｋ_Ｓの要素ｋ^＊ _ｉ ^{（τ，κ，ι）}を数１３３に示すように生成する。

　（Ｓ２０６：鍵配布ステップ）
　鍵配布部１５０は、（Ｓ２０１）で入力したアクセスストラクチャＳと、（Ｓ２０５）で生成されたｋ^＊ _０ ^{（τ，κ，ι）}，ｋ^＊ _１ ^{（τ，κ，ι）}，．．．，ｋ^＊ _Ｌ ^{（τ，κ，ι）}とを要素とする復号鍵ｓｋ_Ｓを、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋ_Ｓは、他の方法により復号装置３００へ配布されてもよい。

　つまり、（Ｓ２０１）から（Ｓ２０５）において、鍵生成装置１００は、数１３４から数１３５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋ_Ｓを生成する。そして、（Ｓ２０６）で、鍵生成装置１００は、生成した復号鍵ｓｋ_Ｓを復号装置３００へ配布する。

　暗号化装置２００の機能と動作とについて説明する。
　暗号化装置２００は、公開パラメータ取得部２１０、情報入力部２２０、暗号化データ生成部２３０、データ送信部２４０を備える。

　図１０に基づき、Ｅｎｃアルゴリズムの処理について説明する。
　（Ｓ３０１：公開パラメータ取得ステップ）
　公開パラメータ取得部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを取得する。

　（Ｓ３０２：情報入力ステップ）
　情報入力部２２０は、入力装置により、復号装置３００へ送信するメッセージｍｓｇを入力する。また、情報入力部２２０は、入力装置により、属性の集合Γ：＝｛（ｔ，ｘ^→ _ｔ：＝（ｘ_ｔ，１，．．．，ｘ_ｔ，ｎ∈Ｆ_ｑ ^ｎ））｜１≦ｔ≦ｄ｝を入力する。なお、ｔは、１以上ｄ以下の全ての整数ではなく、１以上ｄ以下の少なくとも一部の整数であってもよい。また、属性の集合Γは、例えば、復号可能なユーザの属性情報が設定されている。

　（Ｓ３０３：暗号要素生成ステップ）
　暗号化データ生成部２３０は、処理装置により、暗号文ｃｔ_Γの要素ｃ_０を数１３６に示すように生成する。

　暗号化データ生成部２３０は、処理装置により、属性情報Γに含まれる各整数ｔについて、暗号文ｃｔ_Γの要素ｃ_ｔを数１３７に示すように生成する。

　暗号化データ生成部２３０は、処理装置により、暗号文ｃｔ_Γの要素ｃ_ｄ＋１を数１３８に示すように生成する。

　（Ｓ３０４：データ送信ステップ）
　データ送信部２４０は、（Ｓ３０２）で入力した属性の集合Γと、（Ｓ３０３）で生成されたｃ_０，ｃ_ｔ，ｃ_ｄ＋１とを要素とする暗号文ｃｔ_Γを、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔ_Γは、他の方法により復号装置３００へ送信されてもよい。

　つまり、（Ｓ３０１）から（Ｓ３０３）において、暗号化装置２００は、数１３９に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔ_Γを生成する。そして、（Ｓ３０４）で、暗号化装置２００は生成した暗号文ｃｔ_Γを復号装置３００へ送信する。

　復号装置３００の機能と動作とについて説明する。
　復号装置３００は、情報取得部３１０、スパンプログラム計算部３２０、補完係数計算部３３０、復号部３４０を備える。また、情報取得部３１０は、復号鍵取得部３１１、暗号文取得部３１２を備える。また、補完係数計算部３３０は、多項式選択部３３１、係数計算部３３２を備える。また、復号部３４０は、ペアリング演算部３４１、メッセージ計算部３４２を備える。

　図１１に基づき、Ｄｅｃアルゴリズムの処理について説明する。
　（Ｓ４０１：復号鍵取得ステップ）
　復号鍵取得部３１１は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から配布された復号鍵ｓｋ_Ｓ：＝（Ｓ，ｋ^＊ _０ ^{（τ，κ，ι）}，ｋ^＊ _１ ^{（τ，κ，ι）}，．．．，ｋ^＊ _Ｌ ^{（τ，κ，ι）}）を取得する。また、復号鍵取得部３１１は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。

　（Ｓ４０２：暗号文取得ステップ）
　暗号文取得部３１２は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔ_Γ：＝（Γ，ｃ_０，ｃ_ｔ，ｃ_ｄ＋１）を取得する。

　（Ｓ４０３：スパンプログラム計算ステップ）
　スパンプログラム計算部３２０は、処理装置により、（Ｓ４０１）で取得した復号鍵ｓｋ_Ｓに含まれるアクセスストラクチャＳが、（Ｓ４０２）で取得した暗号文ｃｔ_Γに含まれるΓを受理するか否かを判定する。アクセスストラクチャＳがΓを受理するか否かの判定方法は、「実施の形態１における第２－１．２次スパンプログラム」で説明した通りである。
　スパンプログラム計算部３２０は、アクセスストラクチャＳがΓを受理する場合（Ｓ４０３で受理）、処理を（Ｓ４０４）へ進める。一方、アクセスストラクチャＳがΓを拒絶する場合（Ｓ４０３で拒絶）、暗号文ｃｔ_Γを復号鍵ｓｋ_Ｓで復号できないとして処理を終了する。

　（Ｓ４０４：多項式選択ステップ）
　補完係数計算部３３０の多項式選択部３３１は、処理装置により、Ｉ_{（ρ，Γ）}⊆｛１，．．．，Ｌ｝を計算する。Ｉ_{（ρ，Γ）}の計算方法は、「実施の形態１の第２－２．属性の内積と２次スパンプログラム」で説明した通りである。

　（Ｓ４０５：係数計算ステップ）
　補完係数計算部３３０の係数計算部３３２は、処理装置により、数１４０となる係数（α_１，．．．，α_Ｌ）と、係数（β_１，．．．，β_Ｌ）と、次数（κ_１，．．．，κ_ｍ）とを計算する。係数（α_１，．．．，α_Ｌ）と、係数（β_１，．．．，β_Ｌ）と、次数（κ_１，．．．，κ_ｍ）との計算方法は、どのような方法でもよく、例えば総当たり法により計算してもよい。

　ここで、Ｉ_{（ρ，Γ）}に含まれない全てのｉについては、α_ｉ＝０＝β_ｉである。

　（Ｓ４０６：ペアリング演算ステップ）
　復号部３４０のペアリング演算部３４１は、処理装置により、数１４１を計算して、セッション鍵Ｋ_τ，０，Ｋ_τ，１を生成する。

　（Ｓ４０７：メッセージ計算ステップ）
　復号部３４０のメッセージ計算部３４２は、処理装置により、数１４２を計算して、メッセージｍｓｇ’（＝ｍｓｇ）を生成する。

　なお、数１４３に示すように、数１４１を計算することによりｇ_Ｔ ^ζが得られる。そのため、数１４２を計算することにより、メッセージｍｓｇ’（＝ｍｓｇ）を得られる。

　つまり、（Ｓ４０１）から（Ｓ４０７）において、復号装置３００は、数１４４に示すＤｅｃアルゴリズムを実行して、メッセージｍｓｇ’（＝ｍｓｇ）を生成する。

　以上のように、実施の形態２に係る暗号システム１０では、２次スパンプログラムを利用した関数型暗号方式を実現する。
　２次スパンプログラムを利用することにより、関係Ｒとして表現できる範囲が広い。

　特に、実施の形態２に係る暗号システム１０では、目標多項式ｄ（ｘ）を因数分解した多項式ｄ_τ（ｘ）^ｆτ毎に、多項式ｄ_τ（ｘ）^κで多項式ａ_ｉ（ｘ）を割った余りを設定した要素と、多項式ｄ_τ（ｘ）^ｆτ－κで多項式ｂ_ｉ（ｘ）を割った余りを設定した要素とを、鍵要素ｋ^＊ _０ ^{（τ，κ，ι）}，ｋ^＊ _１ ^{（τ，κ，ι）}，．．．，ｋ^＊ _Ｌ ^{（τ，κ，ι）}とする。また、各鍵要素ｋ^＊ _０ ^{（τ，κ，ι）}に、秘密情報πと秘密情報χとを分散させて設定する。そして、係数α，βを用いて、鍵要素と暗号要素とのペアリング演算をすることにより、各鍵要素に設定された余りを０にし、秘密情報πを０にし、秘密情報χを１にすることにより、暗号文からセッション鍵Ｋ_τ，０，Ｋ_τ，１を抽出する。これにより、２次スパンプログラムを利用した関数型暗号方式を実現する。

　なお、上記説明では、ＫＰ－ＦＥ方式について説明した。しかし、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズム、Ｄｅｃアルゴリズムをそれぞれ数１４５から数１４８に示すようにすることにより、ＣＰ－ＦＥ方式とすることも可能である。なお、Ｓｅｔｕｐアルゴリズムは、ＫＰ－ＦＥ方式とＣＰ－ＦＥ方式とで同じである。

　また、上記説明では、関数型暗号方式について説明した。しかし、Ｓｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズム、Ｄｅｃアルゴリズムをそれぞれ数１４９から数１５３に示すようにすることにより、属性ベース暗号方式とすることも可能である。なお、属性ベース暗号方式の場合、Ｓｅｔｕｐアルゴリズムにおいて、ｎ_ｔは２ｍｆ_ｍａｘｋ_ｍａｘ＋２である。

　同様に、数１４５から数１４８に示すＣＰ－ＦＥ方式を属性ベース暗号方式に変更することも可能である。

　また、上記説明では、Ｎ_０にｎ_０＋ｕ_０＋ｗ_０＋ｚ_０を設定し、Ｎ_ｔにｎ_ｔ＋ｕ_ｔ＋ｗ_ｔ＋ｚ_ｔを設定した。ここで、例えば、ｕ_０＝ｎ_０，ｗ_０＝ｎ_０，ｚ_０＝２として、Ｎ_０にｎ_０＋ｎ_０＋ｎ_０＋２＝３ｎ_０＋２とし、ｕ_ｔ＝ｎ_ｔ，ｗ_ｔ＝ｎ_ｔ，ｚ_ｔ＝１として、Ｎ_ｔにｎ_ｔ＋ｎ_ｔ＋ｎ_ｔ＋１＝３ｎ_ｔ＋１としてもよい。

　実施の形態３．
　実施の形態３では、実施の形態２で説明した関数型暗号方式に比べ、基底の数が多くなる代わりに、各基底の次元数が少ない関数型暗号方式を説明する。
　実施の形態３では、実施の形態２に係る暗号システム１０と異なる部分を中心に説明する。

　実施の形態３に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、図５～図７に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同じである。
　実施の形態３に係るＤｅｃアルゴリズムの処理については、実施の形態２に係るＤｅｃアルゴリズムの処理と同じであるため、ここでは、実施の形態３に係るＳｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムの処理について説明する。
　実施の形態３に係るＳｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムの処理の流れは、図８～図１０に示す実施の形態２に係るＳｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムの処理の流れと同じである。

　図８に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
　（Ｓ１０１：正規直交基底生成ステップ）
　（１）～（３）の処理は、実施の形態２と同じである。
　（４）マスター鍵生成部１１０は、Ｎ_０にｎ_０＋ｕ_０＋ｗ_０＋ｚ_０を設定し、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の各整数ｔについて、Ｎ_ｔにｎ_ｔ＋ｕ_ｔ＋ｗ_ｔ＋ｚ_ｔを設定する。ここで、ｎ_０は１であり、ｎ_ｔはｎである。ｎは１以上の整数であり、ｕ_０，ｗ_０，ｚ_０，ｕ_ｔ，ｗ_ｔ，ｚ_ｔはそれぞれ０以上の整数である。
　続いて、マスター鍵生成部１１０は、τ＝１，．．．，ｍ、κ＝０，．．．，ｆ_τ、ι＝０，１、ｔ＝０，．．．，ｄの各整数τ、κ、ι、ｔについて（５）から（９）までの処理を実行する。
　（５）の処理は、実施の形態２と同じである。
　（６）マスター鍵生成部１１０は、実施の形態２と同様に、線形変換Ｘ_ｔ ^{（τ，κ，ι）}：＝（χ_{ｔ，ｉ，ｊ} ^{（τ，κ，ι）}）_ｉ，ｊをランダムに生成する。
　（７）マスター鍵生成部１１０は、実施の形態２と同様に、Ｘ^＊ _ｔ ^{（τ，κ，ι）}：＝（ν_{ｔ，ｉ，ｊ} ^{（τ，κ，ι）}）_ｉ，ｊ：＝ψ・（Ｘ_ｔ ^{（τ，κ，ι）Ｔ}）^－１を生成する。
　（８）マスター鍵生成部１１０は、実施の形態２と同様に、（６）で生成した線形変換Ｘ_ｔ ^{（τ，κ，ι）}に基づき、（５）で生成した標準基底Ａ_ｔから基底Ｂ_ｔ ^{（τ，κ，ι）}を生成する。
　（９）マスター鍵生成部１１０は、実施の形態２と同様に、（７）で生成した線形変換Ｘ^＊ _ｔ ^{（τ，κ，ι）}に基づき、（５）で生成した標準基底Ａ_ｔから基底Ｂ^＊ _ｔ ^{（τ，κ，ι）}を生成する。
　（１０）の処理は、実施の形態２と同じである。

　（Ｓ１０２：公開パラメータ生成ステップ）
　マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ_０ ^{（τ，κ，ι）}の部分基底Ｂ＾_０ ^{（τ，κ，ι）}と、基底Ｂ_ｔ ^{（τ，κ，ι）}の部分基底Ｂ＾_ｔ ^{（τ，κ，ι）}とを数１５４に示すように生成する。

　マスター鍵生成部１１０は、生成した部分基底Ｂ＾_０ ^{（τ，κ，ι）}及び部分基底Ｂ＾_ｔ ^{（τ，κ，ι）}と、（Ｓ１０１）で入力されたセキュリティパラメータλと、（Ｓ１０１）で生成したｐａｒａｍとを合わせて、公開パラメータｐｋとする。

　（Ｓ１０３：マスター鍵生成ステップ）
　マスター鍵生成部１１０は、処理装置により、（Ｓ１０１）で生成した基底Ｂ^＊ _０ ^{（τ，κ，ι）}の部分基底Ｂ＾^＊ _０ ^{（τ，κ，ι）}と、基底Ｂ^＊ _ｔ ^{（τ，κ，ι）}の部分基底Ｂ＾^＊ _ｔ ^{（τ，κ，ι）}とを数１５５に示すように生成する。

　マスター鍵生成部１１０は、生成した部分基底Ｂ＾^＊ _０ ^{（τ，κ，ι）}と部分基底Ｂ＾^＊ _ｔ ^{（τ，κ，ι）}とをマスター鍵ｓｋとする。

　（Ｓ１０４）の処理は、実施の形態２と同じである。

　つまり、（Ｓ１０１）から（Ｓ１０３）において、鍵生成装置１００は、数１５６に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター鍵ｓｋとを生成する。そして、（Ｓ１０４）で、鍵生成装置１００は、生成した公開パラメータｐｋとマスター鍵ｓｋとを記憶装置に記憶する。

　図９に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
　（Ｓ２０１）から（Ｓ２０４）までと、（Ｓ２０６）との処理は、実施の形態２と同じである。

　（Ｓ２０５：鍵要素生成ステップ）
　鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆ_τの各整数κと、ι＝０，１の各整数ιとについて、復号鍵ｓｋ_Ｓの要素ｋ^＊ _０ ^{（τ，κ，ι）}を数１５７に示すように生成する。

　鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆ_τの各整数κと、ι＝０，１の各整数ιと、ｉ＝１，．．．，Ｌの各整数ｉとについて、復号鍵ｓｋ_Ｓの要素ｋ^＊ _ｉ ^{（τ，κ，ι）}を数１５８に示すように生成する。

　つまり、（Ｓ２０１）から（Ｓ２０５）において、鍵生成装置１００は、数１５９から数１６０に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋ_Ｓを生成する。そして、（Ｓ２０６）で、鍵生成装置１００は、生成した復号鍵ｓｋ_Ｓを復号装置３００へ配布する。

　図１０に基づき、Ｅｎｃアルゴリズムの処理について説明する。
　（Ｓ３０１）から（Ｓ３０２）までと、（Ｓ３０４）との処理は、実施の形態２と同じである。

　（Ｓ３０３：暗号要素生成ステップ）
　暗号化データ生成部２３０は、処理装置により、暗号文ｃｔ_Γの要素ｃ_０ ^{（τ，κ，ι）}を数１６１に示すように生成する。

　暗号化データ生成部２３０は、処理装置により、属性情報Γに含まれる各整数ｔについて、暗号文ｃｔ_Γの要素ｃ_ｔ ^{（τ，κ，ι）}を数１６２に示すように生成する。

　暗号化データ生成部２３０は、処理装置により、暗号文ｃｔ_Γの要素ｃ_ｄ＋１を数１６３に示すように生成する。

　つまり、（Ｓ３０１）から（Ｓ３０３）において、暗号化装置２００は、数１６４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔ_Γを生成する。そして、（Ｓ３０４）で、暗号化装置２００は生成した暗号文ｃｔ_Γを復号装置３００へ送信する。

　以上のように、実施の形態３に係る暗号システム１０は、実施の形態２で説明した関数型暗号方式に比べ、基底の数が多くなる代わりに、各基底の次元数が少ない関数型暗号方式を実現する。

　なお、上記説明では、ＫＰ－ＦＥ方式について説明した。しかし、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムをそれぞれ数１６５から数１６７に示すようにすることにより、ＣＰ－ＦＥ方式とすることも可能である。なお、Ｓｅｔｕｐアルゴリズムは、ＫＰ－ＦＥ方式とＣＰ－ＦＥ方式とで同じである。また、Ｄｅｃアルゴリズムは、数１４８に示すＤｅｃアルゴリズムと同じである。

　また、上記説明では、関数型暗号方式について説明した。しかし、Ｓｅｔｕｐアルゴリズム、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズムをそれぞれ数１６８から数１７１に示すようにすることにより、属性ベース暗号方式とすることも可能である。なお、属性ベース暗号方式の場合、Ｓｅｔｕｐアルゴリズムにおいて、ｎ_ｔは２である。Ｄｅｃアルゴリズムは、数１５３に示すＤｅｃアルゴリズムと同じである。

　同様に、数１６５から数１６７に示すＣＰ－ＦＥ方式を属性ベース暗号方式に変更することも可能である。

　また、上記説明では、Ｎ_０にｎ_０＋ｕ_０＋ｗ_０＋ｚ_０を設定し、Ｎ_ｔにｎ_ｔ＋ｕ_ｔ＋ｗ_ｔ＋ｚ_ｔを設定した。ここで、例えば、ｕ_０＝ｎ_０，ｗ_０＝ｎ_０，ｚ_０＝２として、Ｎ_０にｎ_０＋ｎ_０＋ｎ_０＋２＝３ｎ_０＋２（ｎ_０＝１のため、Ｎ_０＝５）とし、ｕ_ｔ＝ｎ_ｔ，ｗ_ｔ＝ｎ_ｔ，ｚ_ｔ＝１として、Ｎ_ｔにｎ_ｔ＋ｎ_ｔ＋ｎ_ｔ＋１＝３ｎ_ｔ＋１としてもよい。

　実施の形態４．
　実施の形態２，３では、目標多項式ｄ（ｘ）を因数分解した多項式ｄ_τ（ｘ）^ｆτ毎に、多項式ｄ_τ（ｘ）^κで多項式ａ_ｉ（ｘ）を割った余りを設定した要素と、多項式ｄ_τ（ｘ）^ｆτ－κで多項式ｂ_ｉ（ｘ）を割った余りを設定した要素とを、鍵要素とした。
　実施の形態４では、目標多項式ｄ（ｘ）を因数分解した多項式ｄ_τ（ｘ）^ｆτ毎に、多項式ｄ_τ（ｘ）^κに乱数値γを代入した要素と、多項式ｄ_τ（ｘ）^ｆτ－κに乱数値γを代入した要素とを、鍵要素とする。

　実施の形態４に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、図５～図７に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同じである。
　実施の形態４に係るＳｅｔｕｐアルゴリズム、Ｅｎｃアルゴリズムは、実施の形態２に係るＳｅｔｕｐアルゴリズム、Ｅｎｃアルゴリズムと同じである。
　実施の形態４に係るＤｅｃアルゴリズムの処理の流れは、図１１に示す実施の形態２に係るＤｅｃアルゴリズムの処理の流れと同じである。
　図１２は、実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。

　図１２に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
　（Ｓ５０１）から（Ｓ５０３）までの処理は、図９に示す（Ｓ２０１）から（Ｓ２０３）までの処理と同じであり、（Ｓ５０５）の処理は、図９に示す（Ｓ２０６）との処理と同じである。

　（Ｓ５０４：鍵要素生成ステップ）
　鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆ_τの各整数κと、ι＝０，１の各整数ιと、ｊ＝１，．．．，μ＋１の各整数ｊとについて、復号鍵ｓｋ_Ｓの要素ｋ^＊ _０，ｊ ^{（τ，κ，ι）}と要素ｋ^＊ _{０，μ＋１} ^{（τ，κ，ι）}とを数１７２に示すように生成する。

　鍵要素生成部１４２は、処理装置により、τ＝１，．．．，ｍの各整数τと、κ＝０，．．．，ｆ_τの各整数κと、ι＝０，１の各整数ιと、ｉ＝１，．．．，Ｌの各整数ｉとについて、復号鍵ｓｋ_Ｓの要素ｋ^＊ _ｉ ^{（τ，κ，ι）}を数１７３に示すように生成する。

　ここで、ｅ^→ _０，ｊ ^{（τ，κ，ι）}（ｊ＝１，．．．，μ＋１）は、１つの基底ベクトルの係数として１が設定され、他の基底ベクトルの係数として０が設定された２ｍｆ_ｍａｘ次元のベクトルであって、係数として１が設定される基底ベクトルが（τ，κ，ι）毎に異なるベクトルである。

　つまり、（Ｓ５０１）から（Ｓ５０４）において、鍵生成装置１００は、数１７４から数１７５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋ_Ｓを生成する。そして、（Ｓ５０５）で、鍵生成装置１００は、生成した復号鍵ｓｋ_Ｓを復号装置３００へ配布する。

　図１１に基づき、Ｄｅｃアルゴリズムの処理について説明する。
　（Ｓ４０１）から（Ｓ４０４）までの処理は、実施の形態２と同じである。

　（Ｓ４０５：係数計算ステップ）
　補完係数計算部３３０の係数計算部３３２は、処理装置により、数１７６となる係数（α_１，．．．，α_Ｌ）と、係数（β_１，．．．，β_Ｌ）と、次数κとを計算する。

　ここで、Ｉ_{（ρ，Γ）}に含まれない全てのｉについては、α_ｉ＝０＝β_ｉである。また、τ＝１，．．．，ｍ及びι＝０，１の全ての整数τ，ιについてｈ_τ，κ，ι（ｘ）：＝ｈ_{τ，κ，ι，０}＋ｈ_{τ，κ，ι，１}ｘ＋・・・＋ｈ_{τ，κ，ι，μ}ｘ^μである。

　（Ｓ４０６：ペアリング演算ステップ）
　復号部３４０のペアリング演算部３４１は、処理装置により、数１７７を計算して、セッション鍵Ｋ_τ，０，Ｋ_τ，１を生成する。

　（Ｓ４０７：メッセージ計算ステップ）
　メッセージ計算部３４２は、処理装置により、数１７８を計算して、メッセージｍｓｇ’（＝ｍｓｇ）を生成する。

　なお、数１７９に示すように、数１７７を計算することによりｇ_Ｔ ^ζが得られる。そのため、数１７８を計算することにより、メッセージｍｓｇ’（＝ｍｓｇ）を得られる。

　つまり、（Ｓ４０１）から（Ｓ４０７）において、復号装置３００は、数１８０に示すＤｅｃアルゴリズムを実行して、メッセージｍｓｇ’（＝ｍｓｇ）を生成する。

　以上のように、実施の形態４に係る暗号システム１０は、多項式ｄ_τ（ｘ）^κに乱数値γを代入した要素と、多項式ｄ_τ（ｘ）^ｆτ－κに乱数値γを代入した要素とを、鍵要素として関数型暗号方式を実現する。

　なお、上記説明では、ＫＰ－ＦＥ方式について説明した。しかし、ＫｅｙＧｅｎアルゴリズム、Ｅｎｃアルゴリズム、Ｄｅｃアルゴリズムをそれぞれ数１８１から数１８４に示すようにすることにより、ＣＰ－ＦＥ方式とすることも可能である。なお、Ｓｅｔｕｐアルゴリズムは、ＫＰ－ＦＥ方式とＣＰ－ＦＥ方式とで同じである。

　また、関数型暗号方式について説明した。しかし、ＫｅｙＧｅｎアルゴリズム、Ｄｅｃアルゴリズムをそれぞれ数１８５から数１８７に示すようにすることにより、属性ベース暗号方式とすることも可能である。なお、属性ベース暗号方式の場合、Ｓｅｔｕｐアルゴリズムにおいて、ｎ_ｔは２ｍｆ_ｍａｘｋ_ｍａｘ＋２である。また、Ｓｅｔｕｐアルゴリズムは、数１４９に示すＳｅｔｕｐアルゴリズムと同じであり、Ｅｎｃアルゴリズムは、数１５２に示すＥｎｃアルゴリズムと同じである。

　同様の変更を行うことにより、数１８１から数１８４に示すＣＰ－ＦＥ方式を属性ベース暗号方式に変更することも可能である。

　また、上記説明では、Ｎ_０にｎ_０＋ｕ_０＋ｗ_０＋ｚ_０を設定し、Ｎ_ｔにｎ_ｔ＋ｕ_ｔ＋ｗ_ｔ＋ｚ_ｔを設定した。ここで、例えば、ｕ_０＝ｎ_０，ｗ_０＝ｎ_０，ｚ_０＝２として、Ｎ_０にｎ_０＋ｎ_０＋ｎ_０＋２＝３ｎ_０＋２とし、ｕ_ｔ＝ｎ_ｔ，ｗ_ｔ＝ｎ_ｔ，ｚ_ｔ＝２として、Ｎ_ｔにｎ_ｔ＋ｎ_ｔ＋ｎ_ｔ＋２＝３ｎ_ｔ＋２としてもよい。

　また、上記説明では、実施の形態２に係る関数型暗号方式と同様に、復号鍵や暗号文が長くなる代わりに、基底の数が少ない関数型暗号方式とした。しかし、実施の形態３，４に係る関数型暗号方式に基づき、実施の形態４に係る関数型暗号方式を、実施の形態３に係る関数型暗号方式と同様に、基底の数が多くなる代わりに、各基底の次元数が少ない関数型暗号方式に容易に変形できる。

　また、以上の実施の形態では、ＫＰ－ＦＥ方式とＣＰ－ＦＥ方式とについて説明した。しかし、非特許文献４に記載されたＵｎｉｆｉｅｄ－Ｐｏｌｉｃｙ　ＦＥ（ＵＰ－ＦＥ）方式も、ＫＰ－ＦＥ方式とＣＰ－ＦＥ方式とから容易に構成することができる。

　実施の形態５．
　以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。実施の形態５では、双対加群において暗号処理を実現する方法について説明する。

　つまり、以上の実施の形態では、素数位数ｑの巡回群において暗号プリミティブの処理を実現した。しかし、合成数Ｍを用いて数１８８のように環Ｒを表した場合、環Ｒを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。

　以上の実施の形態で説明したアルゴリズムにおけるＦ_ｑをＲに変更すれば、双対加群における暗号プリミティブの処理を実現することができる。

　なお、以上の実施の形態において、安全性の証明の観点から、ｉ＝１，．．．，Ｌの各整数ｉについてのρ（ｉ）は、それぞれ異なる識別情報ｔについての肯定形の組（ｔ，ｖ^→）又は否定形の組￢（ｔ，ｖ^→）であると限定してもよい。
　言い替えると、ρ（ｉ）＝（ｔ，ｖ^→）又はρ（ｉ）＝￢（ｔ，ｖ^→）である場合に、関数ρ~を、ρ~（ｉ）＝ｔである｛１，．．．，Ｌ｝→｛１，．．．ｄ｝の写像であるとする。この場合、ρ~が単射であると限定してもよい。なお、ρ（ｉ）は、上述したアクセスストラクチャＳ：＝（Ｍ，ρ（ｉ））のρ（ｉ）である。

　次に、実施の形態における暗号処理システム１０（鍵生成装置１００、暗号化装置２００、復号装置３００）のハードウェア構成について説明する。
　図１３は、鍵生成装置１００、暗号化装置２００、復号装置３００のハードウェア構成の一例を示す図である。
　図１３に示すように、鍵生成装置１００、暗号化装置２００、復号装置３００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ　Ｃｒｙｓｔａｌ　Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。

　ＲＯＭ９１３、磁気ディスク装置９２０は、不揮発性メモリの一例である。ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３とＲＡＭ９１４と磁気ディスク装置９２０とは、記憶装置（メモリ）の一例である。また、キーボード９０２、通信ボード９１５は、入力装置の一例である。また、通信ボード９１５は、通信装置の一例である。さらに、ＬＣＤ９０１は、表示装置の一例である。

　磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。

　プログラム群９２３には、上記の説明において「マスター鍵生成部１１０」、「マスター鍵記憶部１２０」、「情報入力部１３０」、「復号鍵生成部１４０」、「鍵配布部１５０」、「公開パラメータ取得部２１０」、「情報入力部２２０」、「暗号化データ生成部２３０」、「データ送信部２４０」、「情報取得部３１０」、「スパンプログラム計算部３２０」、「補完係数計算部３３０」、「復号部３４０」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
　ファイル群９２４には、上記の説明において「公開パラメータｐｋ」、「マスター秘密鍵ｓｋ」、「復号鍵ｓｋ_Ｓ，ｓｋ_Γ」、「暗号文ｃｔ_Γ，ｃｔ_Ｓ」、「アクセスストラクチャＳ」、「属性情報」、「メッセージｍｓｇ」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。

　また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
　また、上記の説明において「～部」として説明するものは、「～回路」、「～装置」、「～機器」、「～手段」、「～機能」であってもよく、また、「～ステップ」、「～手順」、「～処理」であってもよい。また、「～装置」として説明するものは、「～回路」、「～機器」、「～手段」、「～機能」であってもよく、また、「～ステップ」、「～手順」、「～処理」であってもよい。さらに、「～処理」として説明するものは「～ステップ」であっても構わない。すなわち、「～部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「～部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「～部」の手順や方法をコンピュータ等に実行させるものである。

　１００　鍵生成装置、１１０　マスター鍵生成部、１２０　マスター鍵記憶部、１３０　情報入力部、１４０　復号鍵生成部、１４１　秘密情報生成部、１４２　鍵要素生成部、１５０　鍵配布部、２００　暗号化装置、２１０　公開パラメータ取得部、２２０　情報入力部、２３０　暗号化データ生成部、２４０　データ送信部、３００　復号装置、３１１　復号鍵取得部、３１２　暗号文取得部、３２０　スパンプログラム計算部、３３０　補完係数計算部、３３１　多項式選択部、３３２　係数計算部、３４０　復号部、３４１　ペアリング演算部、３４２　メッセージ計算部。

Claims

　２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文として生成する暗号化装置と、
　前記第１情報と前記第２情報とのうちの他方を復号鍵とし、前記２次スパンプログラムが前記属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号装置と
を備えることを特徴とする暗号システム。
　前記第１情報は、前記２次スパンプログラムとして、多項式ｄ（ｘ）と複数の多項式Ｄ_ｉ（ｘ）と述語情報とを含み、
　前記復号装置は、
　前記第１情報に含まれる述語情報と、前記第２情報に含まれる属性情報とに基づき、前記複数の多項式Ｄ_ｉ（ｘ）から少なくとも一部の多項式Ｄ_ｉ（ｘ）を選択する多項式選択部と、
　前記多項式選択部が選択した多項式Ｄ_ｉ（ｘ）に係数Δ_ｉを掛けた多項式Δ_ｉＤ_ｉ（ｘ）に基づき構成される多項式を、前記多項式ｄ（ｘ）で割り切れるようにする係数Δ_ｉを計算する係数計算部と、
　前記係数計算部が計算した係数Δ_ｉに基づき、前記暗号文を復号する復号部と
を備えることを特徴とする請求項１に記載の暗号システム。
　前記複数の多項式Ｄ_ｉ（ｘ）は、ｉ＝０，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての多項式ａ_ｉ（ｘ）及び多項式ｂ_ｉ（ｘ）であり、
　前記多項式選択部は、前記属性情報と前記述語情報とに基づき、ｉ＝１，．．．，Ｌのうち一部の整数ｉの集合Ｉを選択することにより、多項式ａ_０（ｘ）及び多項式ｂ_０（ｘ）と、前記集合Ｉに含まれる整数ｉについての多項式ａ_ｉ（ｘ）及び多項式ｂ_ｉ（ｘ）とを選択し、
　前記係数計算部は、（ａ_０（ｘ）＋Σ_ｉ∈Ｉα_ｉａ_ｉ（ｘ））・（ｂ_０（ｘ）＋Σ_ｉ∈Ｉβ_ｉｂ_ｉ（ｘ））を前記多項式ｄ（ｘ）で割り切れるようにする係数α_ｉ及び係数β_ｉを前記係数Δ_ｉとして計算する
ことを特徴とする請求項２に記載の暗号システム。
　前記多項式ｄ（ｘ）は、τ＝１，．．．，ｍ（ｍは１以上の整数）の多項式ｄ_τ（ｘ）^ｆτに因数分解され、
　前記係数計算部は、Π_τ＝１ ^ｍｄ_τ（ｘ）^κτが（ａ_０（ｘ）＋Σ_ｉ∈Ｉα_ｉａ_ｉ（ｘ））を割り切るようにするとともに、Π_τ＝１ ^ｍｄ_τ（ｘ）^ｆτ－κτが（ｂ_０（ｘ）＋Σ_ｉ∈Ｉβ_ｉｂ_ｉ（ｘ））を割り切るようにする係数α_ｉ及び係数β_ｉと、次数κ_τとを計算し、
　前記復号部は、前記係数α_ｉ及び前記係数β_ｉと、前記次数κ_τとに基づき、前記暗号文を復号する
ことを特徴とする請求項３に記載の暗号システム。
　前記属性情報は、ｔ＝１，．．．，ｄ（ｄは１以上の整数）の少なくとも一部の整数ｔについての属性ベクトルｘ^→ _ｔを含み、
　前記述語情報は、ｉ＝１，．．．，Ｌの各整数ｉについての識別子ｔと述語ベクトルｖ^→ _ｉとの組（ｔ，ｖ^→ _ｉ）を含み、
　前記多項式選択部は、ｉ＝１，．．．，Ｌの各整数ｉについての前記組（ｔ，ｖ^→ _ｉ）について、その組の述語ベクトルｖ^→ _ｉとその組の識別情報ｔについての属性ベクトルｘ^→ _ｔとの内積が０となるか否かにより、整数ｉを前記集合Ｉに含めるか否かを判定する
ことを特徴とする請求項３又は４に記載の暗号システム。
　前記組（ｔ，ｖ^→ _ｉ）は、肯定形と否定形とのいずれかに対応付けられており、
　前記多項式選択部は、前記組（ｔ，ｖ^→ _ｉ）が肯定形に対応付けられている場合、前記内積が０となるなら、整数ｉを前記集合Ｉに含め、前記組（ｔ，ｖ^→ _ｉ）が否定形に対応付けられている場合、前記内積が０とならないなら、整数ｉを前記集合Ｉに含める
ことを特徴とする請求項５に記載の暗号システム。
　前記多項式ｄ（ｘ）は、τ＝１，．．．，ｍ（ｍは１以上の整数）の多項式ｄ_τ（ｘ）^ｆτに因数分解され、
　前記第１情報は、多項式ｄ_τ（ｘ）^ｆτ毎に、その多項式ｄ_τ（ｘ）^ｆτによって得られる情報が設定された要素を含み、
　前記復号部は、前記係数Δ_ｉと前記要素とに基づき、前記暗号文を復号する
ことを特徴とする請求項２から６までのいずれかに記載の暗号システム。
　前記第１情報は、多項式ｄ_τ（ｘ）^ｆτ毎に、κ＝０，．．．，ｆ_τの各整数κと、ｉ＝０，．．．，Ｌの各整数ｉとについて、多項式ｄ_τ（ｘ）^κで多項式ａ_ｉ（ｘ）を割った余りを設定した要素と、多項式ｄ_τ（ｘ）^ｆτ－κで多項式ｂ_ｉ（ｘ）を割った余りを設定した要素とを含む
ことを特徴とする請求項７に記載の暗号システム。
　前記第１情報は、多項式ｄ_τ（ｘ）^ｆτ毎に、所定の値γを代入した値を設定した要素を含む
ことを特徴とする請求項７に記載の暗号システム。
　前記復号部は、前記係数Δ_ｉに基づき、前記要素について所定の演算を行うことにより、前記多項式ｄ_τ（ｘ）^ｆτによって得られる情報を０にして、前記暗号文を復号する
ことを特徴とする請求項７から９までのいずれかに記載の暗号システム。
　暗号化装置が、２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文として生成する暗号化工程と、
　復号装置が、前記第１情報と前記第２情報とのうちの他方を復号鍵とし、前記２次スパンプログラムが前記属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号工程と
を備えることを特徴とする暗号方法。
　２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文として生成する暗号化処理と、
　前記第１情報と前記第２情報とのうちの他方を復号鍵とし、前記２次スパンプログラムが前記属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号処理と
をコンピュータに実行させることを特徴とする暗号プログラム。
　２次スパンプログラムを含む第１情報と、属性情報を含む第２情報とのうちの一方を暗号文とし、他方を復号鍵として取得する情報取得部と、
　前記情報取得部が取得した第１情報に含まれる２次スパンプログラムが第２情報に含まれる属性情報を受理する場合に前記２次スパンプログラムと前記属性情報とから得られる情報に基づき、前記暗号文を復号する復号部と
を備えることを特徴とする復号装置。