(57)【要約】【課題】幅広い述語を許容しつつ、安全性を高くすることが可能な述語暗号方式を実現可能にする。【解決手段】暗号化装置２０は、双対ベクトル空間における双対基底である基底Ｂ及び基底Ｂ＊のうちの基底Ｂに、属性ベクトルと、ＡＢＰ（Ａｒｉｔｈｍｅｔｉｃ  Ｂｒａｎｃｈｉｎｇ  Ｐｒｏｇｒａｍｓ）の述語ベクトルとの一方を設定して暗号文を生成する。鍵生成装置３０は、基底Ｂ＊に、属性ベクトルと述語ベクトルとの他方を設定して復号鍵を生成する。復号装置４０は、暗号化装置２０によって生成された暗号文と、鍵生成装置３０によって生成された復号鍵とについてペアリング演算を行うことにより、暗号文を復号する。【選択図】図１
2020056960.tif 000002
【特許請求の範囲】
【請求項１】
双対ベクトル空間における双対基底である基底Ｂ及び基底Ｂ＊のうちの基底Ｂに、属性ベクトルと、ＡＢＰ（Ａｒｉｔｈｍｅｔｉｃ  Ｂｒａｎｃｈｉｎｇ  Ｐｒｏｇｒａｍｓ）の述語ベクトルとの一方が設定された暗号文を取得する暗号文取得部と、
前記基底Ｂ＊に、前記属性ベクトルと前記述語ベクトルとの他方が設定された復号鍵を取得する復号鍵取得部と、
前記暗号文取得部によって取得された前記暗号文と、前記復号鍵取得部によって取得された前記復号鍵とについてペアリング演算を行うことにより、前記暗号文を復号する復号部と
を備える復号装置。
【請求項２】
前記述語ベクトルの要素は、関数ｆを計算するＡＢＰを表す行列表現Ｌと、最後の行の要素が１である行列との積によって得られた要素である
請求項１に記載の復号装置。
【請求項３】
前記復号部は、
前記行列表現Ｌの最後の列の要素の余因子を計算する余因子計算部と、
前記暗号文と前記復号鍵とについてペアリング演算を行うことにより演算値を計算するペアリング演算部と、
前記余因子計算部によって計算された前記余因子と、前記ペアリング演算部によって計算された前記演算値とから、前記暗号文を復号して得られる出力値を計算する出力値計算部と
を備える請求項２に記載の復号装置。
【請求項４】
前記出力値計算部は、前記内積と前記余因子とから、前記関数ｆに前記属性ベクトルを入力した値を計算して、計算された値により前記出力値を計算する
請求項３に記載の復号装置。
【請求項５】
前記暗号文取得部は、数１に示す暗号文ＣＴを取得し、
前記復号鍵取得部は、数２に示す復号鍵ＳＫ（ｆ）を取得し、
前記ペアリング演算部は、数３に示すようにペアリング演算を行うことにより、前記演算値Λ’ｊ，Λｊを計算し、
前記出力値計算部は、数４に示すように値Λを計算して、前記値Λの値に応じて出力値を計算する
請求項４に記載の復号装置。
【数１】
2020056960.tif 000090
【数２】
2020056960.tif 000091
【数３】
2020056960.tif 000092
【数４】
2020056960.tif 000093
【請求項６】
前記暗号文取得部は、数５に示す暗号文ＣＴを取得し、
前記復号鍵取得部は、数６に示す復号鍵ＳＫ（ｆ）を取得し、
前記ペアリング演算部は、数７に示すようにペアリング演算を行うことにより、前記演算値Λ’０，Λ’ｊ，Λｊを計算し、
前記出力値計算部は、数８に示すように値Λを計算して、前記値ΛΛ’０を前記出力値として計算する
請求項４に記載の復号装置。
【数５】
2020056960.tif 000094
【数６】
2020056960.tif 000095
【数７】
2020056960.tif 000096
【数８】
2020056960.tif 000097
【請求項７】
双対ベクトル空間における双対基底である基底Ｂ及び基底Ｂ＊のうちの基底Ｂに、属性ベクトルと、ＡＢＰ（Ａｒｉｔｈｍｅｔｉｃ  Ｂｒａｎｃｈｉｎｇ  Ｐｒｏｇｒａｍｓ）の述語ベクトルとの一方を設定して暗号文を生成する暗号化装置と、
前記基底Ｂ＊に、前記属性ベクトルと前記述語ベクトルとの他方を設定して復号鍵を生成する鍵生成装置と、
前記暗号化装置によって生成された前記暗号文と、前記鍵生成装置によって生成された前記復号鍵とについてペアリング演算を行うことにより、前記暗号文を復号する復号装置と
を備える暗号システム。
【請求項８】
暗号文取得部が、双対ベクトル空間における双対基底である基底Ｂ及び基底Ｂ＊のうちの基底Ｂに、属性ベクトルと、ＡＢＰ（Ａｒｉｔｈｍｅｔｉｃ  Ｂｒａｎｃｈｉｎｇ  Ｐｒｏｇｒａｍｓ）の述語ベクトルとの一方が設定された暗号文を取得し、
復号鍵取得部が、前記基底Ｂ＊に、前記属性ベクトルと前記述語ベクトルとの他方が設定された復号鍵を取得し、
復号部が、前記暗号文取得部によって取得された前記暗号文と、前記復号鍵取得部によって取得された前記復号鍵とについてペアリング演算を行うことにより、前記暗号文を復号する復号方法。
【請求項９】
暗号文取得部が、双対ベクトル空間における双対基底である基底Ｂ及び基底Ｂ＊のうちの基底Ｂに、属性ベクトルと、ＡＢＰ（Ａｒｉｔｈｍｅｔｉｃ  Ｂｒａｎｃｈｉｎｇ  Ｐｒｏｇｒａｍｓ）の述語ベクトルとの一方が設定された暗号文を取得する暗号文取得処理と、
復号鍵取得部が、前記基底Ｂ＊に、前記属性ベクトルと前記述語ベクトルとの他方が設定された復号鍵を取得する復号鍵取得処理と、
復号部が、前記暗号文取得処理によって取得された前記暗号文と、前記復号鍵取得処理によって取得された前記復号鍵とについてペアリング演算を行うことにより、前記暗号文を復号する復号処理と
を行う復号装置としてコンピュータを機能させる復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、述語暗号に関する。
【背景技術】
【０００２】
非特許文献１には、ＡＢＰ（Ａｒｉｔｈｍｅｔｉｃ  Ｂｒａｎｃｈｉｎｇ  Ｐｒｏｇｒａｍｓ）の述語を用いた述語暗号方式が記載されている。この述語暗号方式は、幅広い述語を許容する方式である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｗｅｅ，  Ｈ．：  Ａｔｔｒｉｂｕｔｅ−ｈｉｄｉｎｇ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｉｎ  ｂｉｌｉｎｅａｒ  ｇｒｏｕｐｓ，  ｒｅｖｉｓｉｔｅｄ．  Ｉｎ：Ｔｈｅｏｒｙ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｃｏｎｆｅｒｅｎｃｅ−ＴＣＣ  ２０１７．  ｐｐ．  ２０６−２３３．  Ｓｐｒｉｎｇｅｒ  （２０１７）
【非特許文献２】Ｉｓｈａｉ，  Ｙ．，  Ｋｕｓｈｉｌｅｖｉｔｚ，  Ｅ．：  Ｐｅｒｆｅｃｔ  ｃｏｎｓｔａｎｔ−ｒｏｕｎｄ  ｓｅｃｕｒｅ  ｃｏｍｐｕｔａｔｉｏｎ  ｖｉａ  ｐｅｒｆｅｃｔ  ｒａｎｄｏｍｉｚｉｎｇ  ｐｏｌｙｎｏｍｉａｌｓ．  Ｉｎ：  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｌｌｏｑｕｉｕｍ  ｏｎ  Ａｕｔｏｍａｔａ，  Ｌａｎｇｕａｇｅｓ，ａｎｄ  Ｐｒｏｇｒａｍｍｉｎｇ−ＩＣＡＬＰ  ２００２．  ｐｐ．  ２４４−２５６．  Ｓｐｒｉｎｇｅｒ  （２００２）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に記載された述語暗号方式の安全性は、現実的な適応的安全性でなかった。そのため、この述語暗号方式は、実際に使用された場合に安全性が保たれるかどうかが懸念されていた。
この発明は、非特許文献１に記載された述語暗号方式と同様に幅広い述語を許容しつつ、安全性を高くすることが可能な述語暗号方式を実現可能にすることを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る復号装置は、
双対ベクトル空間における双対基底である基底Ｂ及び基底Ｂ＊のうちの基底Ｂに、属性ベクトルと、ＡＢＰ（Ａｒｉｔｈｍｅｔｉｃ  Ｂｒａｎｃｈｉｎｇ  Ｐｒｏｇｒａｍｓ）の述語ベクトルとの一方が設定された暗号文を取得する暗号文取得部と、
前記基底Ｂ＊に、前記属性ベクトルと前記述語ベクトルとの他方が設定された復号鍵を取得する復号鍵取得部と、
前記暗号文取得部によって取得された前記暗号文と、前記復号鍵取得部によって取得された前記復号鍵とについてペアリング演算を行うことにより、前記暗号文を復号する復号部と
を備える。
【発明の効果】
【０００６】
この発明では、双対ベクトル空間における双対基底である基底Ｂに属性ベクトルとＡＢＰの述語ベクトルとの一方が設定された暗号文と、基底Ｂ＊に他方が設定された復号鍵とについてペアリング演算が行われ、暗号文が復号される。これにより、幅広い述語を許容しつつ、安全性を高くすることが可能な述語暗号方式を実現することが可能になる。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１に係る暗号システム１の構成図。
【図２】実施の形態１に係るセットアップ装置２０の構成図。
【図３】実施の形態１に係る暗号化装置２０の構成図。
【図４】実施の形態１に係る鍵生成装置３０の構成図。
【図５】実施の形態１に係る復号装置４０の構成図。
【図６】実施の形態１に係るセットアップ装置１０の動作を示すフローチャート。
【図７】実施の形態１に係る暗号化装置２０の動作を示すフローチャート。
【図８】実施の形態１に係る鍵生成装置３０の動作を示すフローチャート。
【図９】実施の形態１に係るＰＧＢ計算処理を示すフローチャート。
【図１０】実施の形態１に係る復号装置４０の動作を示すフローチャート。
【図１１】実施の形態１に係る復号処理を示すフローチャート。
【図１２】変形例３に係るセットアップ装置１０の構成図。
【図１３】変形例３に係る暗号化装置２０の構成図。
【図１４】変形例３に係る鍵生成装置３０の構成図。
【図１５】変形例３に係る復号装置４０の構成図。
【発明を実施するための形態】
【０００８】
実施の形態１．
＊＊＊表記＊＊＊
以下の説明で用いる表記を説明する。
数１０１は、セキュリティパラメータを示し、１λは、単進符号のエンコーディングを表す。
【数１０１】
2020056960.tif 000003
【０００９】
数１０２は、ｑを法とする有限体を示す。数１０２は、体Ｆｑ又は単にＦｑと記載される。
【数１０２】
2020056960.tif 000004
【００１０】
数１０３に対して、数１０４とする。
【数１０３】
2020056960.tif 000005
【数１０４】
2020056960.tif 000006
【００１１】
数１０５は、集合Ｚから要素ｚを一様にサンプリングする処理を示す。
【数１０５】
2020056960.tif 000007
＃Ｚは、集合Ｚのサイズ又は濃度を示す。
【００１２】
確率的アルゴリズムＵに対して、Π＝Ｕ（Θ；Φ）は、ランダムテープの内容Φを伴う入力ΘにおけるアルゴリズムＵの出力を示す。ここで、数１０６は、一様なランダムテープを伴う入力ΘにおけるアルゴリズムＵの出力分布からΠをサンプリング処理を示す。
【数１０６】
2020056960.tif 000008
確定的アルゴリズムＶに対して、Π＝Ｖ（Θ）は、入力ΘにおけるアルゴリズムＶの出力を示す。
【００１３】
アルゴリズムは、内容から明らかな場合には、入力として明示されていない場合であっても、セキュリティパラメータλの単進符号表現１λが入力として与えられるものとする。
【００１４】
数１０７に対して、数１０８は、数１０９に示すベクトルを示す。また、数１０８は、ｖ→と記載される。
【数１０７】
2020056960.tif 000009
【数１０８】
2020056960.tif 000010
【数１０９】
2020056960.tif 000011
【００１５】
体Ｆｑｄにおける全てが０のベクトルは、数１１０のように記載される。
【数１１０】
2020056960.tif 000012
【００１６】
数１１１に示す２つのベクトル対して、数１１２は、ベクトルｖ→とベクトルｗ→との内積を示す。つまり、数１１２は、数１１３を示す。
【数１１１】
2020056960.tif 000013
【数１１２】
2020056960.tif 000014
【数１１３】
2020056960.tif 000015
【００１７】
数１１４は、乗法巡回群を示す。数１１４は、群Ｇ又は単にＧと記載される。
【数１１４】
2020056960.tif 000016
群Ｇと、群Ｇの生成元ｇとに対して、ｖは群要素のｄ次元ベクトルを示す。つまり、数１１５である。
【数１１５】
2020056960.tif 000017
【００１８】
数１１６は、数１１７に示す群要素のｄ次元ベクトルを示す。ここで、数１１８は、群Ｇの単位元を示す。
【数１１６】
2020056960.tif 000018
【数１１７】
2020056960.tif 000019
【数１１８】
2020056960.tif 000020
【００１９】
Ｍ＝（ｍｉ，ｋ）は、成分ｍｉ，ｋ∈Ｆｑを有する行列を示す。ＭＴは、行列Ｍの転置行列を示す。ｄｅｔ（Ｍ）は、行列Ｍの行列式を示す。行列の記載において、Ｉは、単位行列を示し、０は、ゼロ行列を示す。ＧＬ（ｄ，Ｆｑ）は、Ｆｑｄ×ｄにおける全てのｄ×ｄの可逆行列の集合を示す。
【００２０】
＊＊＊準備＊＊＊
以下の説明で用いられる用語の定義等を説明する。
【００２１】
実施の形態１では、ＡＢＰの述語と、内積述語とを包含する（ＡＢＰ〇ＩＰ）述語を用いたＰＨＰＥ（Ｐａｒｔｉａｌｌｙ−Ｈｉｄｉｎｇ  Ｐｒｅｄｉｃａｔｅ  Ｅｎｃｒｙｐｔｉｏｎ）方式を説明する。
【００２２】
＜ＰＨＰＥ＞
ＰＨＰＥは、属性の一部が秘密にされるＰＥ（Ｐｒｅｄｉｃａｔｅ  Ｅｎｃｒｙｐｔｉｏｎ）である。以下の説明では、属性ベクトルｘ→と属性ベクトルｚ→とが与えられ、属性ベクトルｘ→は公開される公開属性ベクトルであり、属性ベクトルｚ→は秘密にされる秘密属性ベクトルである。
【００２３】
＜ＡＢＰ＞
ＢＰ（Ｂｒａｎｃｈｉｎｇ  Ｐｒｏｇｒａｍ）Γは、数１１９に示す５つの要素によって定義される。
【数１１９】
2020056960.tif 000021
数１２０は頂点の集合を示し、数１２１は辺の集合を示す。数１２０は、単にＶと記載され、数１２１は、単にＥと記載される。
【数１２０】
2020056960.tif 000022
【数１２１】
2020056960.tif 000023
（Ｖ，Ｅ）は、有効非巡回グラフである。Ｖ０，Ｖ１∈Ｖは、それぞれソースとシンクと呼ばれる特別な頂点である。φは、Ｅにおける辺に対するラベリング関数である。
【００２４】
有限体ＦｑにおけるＡＢＰΓは、数１２２に示す関数ｆを計算する。
【数１２２】
2020056960.tif 000024
ここで、Ｅにおける各辺に割り当てられるラベリング関数φは、Ｆｑにおける係数を伴う１つの変数の１次式、又は、Ｆｑにおける定数である。ｐを、ＡＢＰΓにおけるソースＶ０からシンクＶ１への全てのパスの集合とする。ある入力ｖ→＝（ｖ１，．．．，ｖｄ）∈ＦｑｄにおけるＡＢＰΓによって計算される関数ｆの出力は、数１２３に示すように定義される。
【数１２３】
2020056960.tif 000025
数１２４は、ｖ→に対する関数φ（Ｅ）の評価値を示す。
【数１２４】
2020056960.tif 000026
【００２５】
非特許文献２には、次の内容が示されている。
関数ｆを計算するＡＢＰΓ＝（Ｖ，Ｅ，Ｖ０，Ｖ１，φ）が与えられた場合、入力ｖ→∈ＦｑｄをＦｑにおける（＃Ｖ−１）×（＃Ｖ−１）の行列Ｌ（ｖ→）にマッピングする関数Ｌを効率的かつ決定的に計算することが可能である。また、以下の（１）から（３）が成立する。
（１）ｄｅｔ（Ｌ（ｖ→））＝ｆ（ｖ→）である。
（２）（Ｌ（ｖ→））の各成分は、Ｆｑにおける係数を伴う１つの変数ｖｉ（ｉ∈［ｄ］）の１次式、又は、Ｆｑにおける定数である。
（３）（Ｌ（ｖ→））は、第２対角、つまり主対角のすぐ下の対角には、−１だけを含み、第２対角の下には０だけを含む。
具体的には、行列Ｌは、行列ＡΓ−Ｉから、Ｖ０に対応する列と、Ｖ１に対応する行とを取り除くことによって得られる。ここで、行列ＡΓは、Γに対する隣接行列である。Ｉは単位行列である。
【００２６】
ここで、ブーリアン方式と、ブーリアンブランチングプログラムと、算術方式とをＡＢＰに変換する線形時間アルゴリズムが存在する。
【００２７】
＜関数族Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰ＞
関数族Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰは、実施の形態１に係るＰＨＰＥ方式でサポートされる関数族である。
関数族Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰは、素数ｑと、自然数ｎ’，ｎとによってパラメータ化され、数１２５に示す関数ｆを含む。
【数１２５】
2020056960.tif 000027
関数ｆは、ζ∈Ｆｑと、（ｘ→，ｚ→）∈Ｆｑｎ’×Ｆｑｎとに対して、ｆ（ｘ→，ζｚ→）＝ζｆ（ｘ→，ｚ→）である。
【００２８】
ＡＢＰΓによって実現される関数ｆは、以下のように構築される。
まず、ＡＢＰ｛Γｊ｝ｊ∈［ｎ］の全てのソース頂点は、１つに併合される。そして、併合された１つの頂点が、ＡＢＰΓのソース頂点になる。次に、ＡＢＰΓに対する新たなシンク頂点が生成される。ｊ∈［ｎ］の各整数ｊについて、ＡＢＰΓｊのシンク頂点から新たなシンク頂点に向かって、ｚｊでラベル付けされた有向辺によって接続される。ここで、関数ｆを計算するＡＢＰΓのサイズは、ｍ＋ｎ＋１である。１は、ＡＢＰΓのシンク頂点に対応する。ｎは、シンク頂点へ向けられた辺の数に対応する。ｍは、ＡＢＰΓの他の頂点に対応する。
ＡＢＰΓは、各頂点が１次のラベルを有する１つの出力辺のみを有するＡＢＰΓ’に修正される。具体的には、ＡＢＰΓにおける各辺Ｅが１とφ（Ｅ）とでラベル付けされた辺のペアに置き換えられることによって、ＡＢＰΓがＡＢＰΓ’に修正される。φは、ＡＢＰΓのラベリング関数である。ＡＢＰΓ’のサイズも、ｍ＋ｎ＋１である。
【００２９】
＜ＡＢＰ〇ＩＰ述語＞
ＡＢＰ〇ＩＰ述語族ＲＡＢＰ〇ＩＰは、数１２６に示す通りである。
【数１２６】
2020056960.tif 000028
つまり、関数ｆにベクトルｘ→及びベクトルｚ→を入力すると０になる場合に、関数ｆと、ベクトルｘ→及びベクトルｚ→とを入力するとＡＢＰ〇ＩＰ述語族ＲＡＢＰ〇ＩＰは１を出力する。一方、関数ｆにベクトルｘ→及びベクトルｚ→を入力すると０にならない場合に、関数ｆと、ベクトルｘ→及びベクトルｚ→とを入力するとＡＢＰ〇ＩＰ述語族ＲＡＢＰ〇ＩＰは０を出力する。
【００３０】
＜ＰＧＢ（Ｐａｒｔｉａｌ  ＧａｒＢｌｉｇ）アルゴリズム＞
ＰＧＢアルゴリズム（ＰＧＢ（ｆ；ｒ→））は、関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰを入力として、ランダム性ｒ→∈Ｆｑｍ＋ｎ−１を用いて、関数ρ：［ｍ］→［ｎ’］を伴う定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）∈Ｆｑｎ×（Ｆｑ２）ｍを出力する確率的多項式時間アルゴリズムである。ｘ→∈Ｆｑｎ’とｚ→∈Ｆｑｎとともに、この定数は、ｎ＋ｍ個の割当値（｛ｚｊ＋σｊ｝ｊ∈［ｎ］，｛αｊ’ｚρ（ｊ’）＋γｊ’｝ｊ’∈［ｍ］）を特定する。
ここで、ｍ＋ｎ＋１は、関数ｆを計算するＡＢＰの頂点の数であり、ρは、関数ｆから確定的に導出される。
【００３１】
ＰＧＢアルゴリズムは、以下の（１）から（３）の性質を有する。
（１）線形性：固定された関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰに対して、ＰＧＢ（ｆ；・）は、Ｆｑにおけるランダム性を有する線形な関数を計算する。
（２）再構築：関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰと、ｘ→∈Ｆｑｎ’とを入力として、係数の集合（｛Ωｊ｝ｊ∈［ｎ］，｛Ω’ｊ’｝ｊ’∈［ｍ］）∈Ｆｑｎ×Ｆｑｎ’を出力する確定的多項式時間アルゴリズムＲＥＣが存在する。この係数の集合は、ｆ（ｘ→，ｚ→）を復元するために、ＰＧＢ（ｆ）の出力と、ｘ→及びｚ→∈Ｆｑｎとの結合によって計算された割当値の集合と合わせて用いられる。
（３）秘匿性：全ての関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰと、ｘ→∈Ｆｑｎ’と、ｚ→∈Ｆｑｎとに対して、関数ｆと、ｘ→と、ｆ（ｘ→，ｚ→）とを入力とし、出力が割当値に対して一様に分布する確率的多項式時間アルゴリズムＳＩＭが存在する。割当値は、一様にランダムなｒ→に対するＰＧＢ（ｆ；ｒ→）の出力とｘ→及びｚ→との結合によって計算される。
【００３２】
＜双線形群＞
数１２７に示す双線形群であるｐａｒａｍＧは、素数ｑと、位数ｑの乗法巡回群Ｇ１，Ｇ２，ＧＴと、群Ｇ１の生成元ｇ１と、群Ｇ２の生成元ｇ２と、数１２８に示す双線形写像ｅとを備える。
【数１２７】
2020056960.tif 000029
【数１２８】
2020056960.tif 000030
【００３３】
双線形写像ｅは、以下の双線形性と非退化性との２つの性質を有する。
（双線形性）
数１２９が成立する。
【数１２９】
2020056960.tif 000031
（非退化性）
数１３０が成立する。ここで、数１３１は、群ＧＴの単位元である。
【数１３０】
2020056960.tif 000032
【数１３１】
2020056960.tif 000033
【００３４】
以下の説明では、ＧＢＰＧ（）を双線形群の生成アルゴリズムとする。つまり、ＧＢＰＧは、ｐａｒａｍＧを生成するアルゴリズムである。
【００３５】
＜双対ペアリングベクトル空間（以下、ＤＰＶＳ）＞
数１３２に示すＤＰＶＳであるｐａｒａｍＶは、双線形群であるｐａｒａｍＧの直積によって構成される。ｐａｒａｍＶは、素数ｑと、要素毎に定義されたベクトル加算及びスカラー乗法の下でのｔ∈［２］についてのＦｑ上のｄ次元ベクトル空間Ｖｔ＝Ｇｔｄと、ｔ∈［２］についてのベクトル空間Ｖｔの数１３３に示す標準基底Ａｔと、数１３４に示すペアリング演算ｅとを備える。
【数１３２】
2020056960.tif 000034
【数１３３】
2020056960.tif 000035
【数１３４】
2020056960.tif 000036
【００３６】
ｐａｒａｍＶにおける写像ｅは、以下の双線形性と非退化性との２つの性質を有する。
（双線形性）
数１３５が成立する。
【数１３５】
2020056960.tif 000037
（非退化性）
数１３６が成立する。
【数１３６】
2020056960.tif 000038
【００３７】
数１３７に示すベクトル空間Ｖｔの基底Ｗと、ベクトルｖ→∈Ｆｑｄとに対して、数１３８は、基底Ｗの要素とベクトルｖ→の要素との線形結合によって構成されるベクトル空間Ｖｔのベクトルを示す。つまり、数１３８は、数１３９を示す。
【数１３７】
2020056960.tif 000039
【数１３８】
2020056960.tif 000040
【数１３９】
2020056960.tif 000041
【００３８】
ベクトルｖ∈Ｖｔと、行列Ｍ＝（ｍｉ，ｋ）∈Ｆｑｄ×ｄとに対して、ｖＭは、数１４０に示すｄ次元ベクトルを示す。
【数１４０】
2020056960.tif 000042
【００３９】
以下の説明では、ＧＤＰＶＳ（１λ，ｄ）をＤＰＶＳの生成アルゴリズムとする。つまり、ＧＤＰＶＳは、単進符号のエンコーディングがされたセキュリティパラメータ１λと、次元を示す自然数ｄとを入力として、ｐａｒａｍＶを生成するアルゴリズムである。
【００４０】
＊＊＊構成の説明＊＊＊
＜ＰＨＰＥの構成＞
実施の形態１では、ＫＰ（Ｋｅｙ−Ｐｏｌｉｃｙ）−ＰＨＰＥ方式を説明する。ＫＰは、復号鍵にアクセスコントロールのための情報が設定されるという意味である。
特に、実施の形態１では、属性のみモードのＫＰ−ＰＨＰＥ方式を説明する。属性のみモードとは、暗号文にペイロードが含まれないという意味である。つまり、属性のみモードとは、暗号文には、暗号化対象のメッセージが含まれていないという意味である。なお、属性のみモードのＫＰ−ＰＨＰＥ方式を、暗号文にペイロードを含む形態のＫＰ−ＰＨＰＥ方式に変形する方法は当業者にとって明らかであり、容易に実現可能である。
【００４１】
ＫＰ−ＰＨＰＥ方式は、ＰＨＰＥ．Ｓｅｔｕｐアルゴリズムと、ＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムと、ＰＨＰＥ．ＫｅｙＧｅｎアルゴリズムと、ＰＨＰＥ．Ｄｅｃｒｙｐｔアルゴリズムとを含む。
【００４２】
ＰＨＰＥ．Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλと、公開属性ベクトルの長さｎ’と、秘密属性ベクトルの長さｎとを入力として、公開パラメータＭＰＫとマスター秘密鍵ＭＳＫとを出力する。
【００４３】
ＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムは、公開パラメータＭＰＫと、公開属性ベクトルｘ→∈Ｆｑｎ’と、秘密属性ベクトルｚ→∈Ｆｑｎとを入力として、暗号文ＣＴを出力する。
【００４４】
ＰＨＰＥ．ＫｅｙＧｅｎアルゴリズムは、公開パラメータＭＰＫと、マスター秘密鍵ＭＳＫと、関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰとを入力として、復号鍵ＳＫ（ｆ）を出力する。
【００４５】
ＰＨＰＥ．Ｄｅｃｒｙｐｔアルゴリズムは、公開パラメータＭＰＫと、関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰに対する復号鍵ＳＫ（ｆ）と、暗号文ＣＴとを入力として、１又は０を出力する。
【００４６】
＜暗号システム１の構成＞
図１を参照して、実施の形態１に係る暗号システム１の構成を説明する。
暗号システム１は、セットアップ装置１０と、暗号化装置２０と、鍵生成装置３０と、復号装置４０とを備える。セットアップ装置１０と、暗号化装置２０と、鍵生成装置３０と、復号装置４０とは、コンピュータである。セットアップ装置１０と、暗号化装置２０と、鍵生成装置３０と、復号装置４０とは、ネットワークを介して接続されている。
【００４７】
図２を参照して、実施の形態１に係るセットアップ装置２０の構成を説明する。
セットアップ装置１０は、ＰＨＰＥ．Ｓｅｔｕｐアルゴリズムを実行するコンピュータである。
セットアップ装置１０は、プロセッサ１１と、メモリ１２と、ストレージ１３と、通信インタフェース１４とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００４８】
セットアップ装置１０は、機能構成要素として、受付部１１１と、マスター鍵生成部１１２と、送信部１１３とを備える。セットアップ装置１０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ１３には、セットアップ装置１０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ１１によりメモリ１２に読み込まれ、プロセッサ１１によって実行される。これにより、セットアップ装置１０の各機能構成要素の機能が実現される。
【００４９】
図３を参照して、実施の形態１に係る暗号化装置２０の構成を説明する。
暗号化装置２０は、ＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムを実行するコンピュータである。
暗号化装置２０は、プロセッサ２１と、メモリ２２と、ストレージ２３と、通信インタフェース２４とのハードウェアを備える。プロセッサ２１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００５０】
暗号化装置２０は、機能構成要素として、マスター鍵取得部２１１と、ベクトル取得部２１２と、暗号化部２１３と、送信部２１４とを備える。暗号化装置２０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ２３には、暗号化装置２０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ２１によりメモリ２２に読み込まれ、プロセッサ２１によって実行される。これにより、暗号化装置２０の各機能構成要素の機能が実現される。
【００５１】
図４を参照して、実施の形態１に係る鍵生成装置３０の構成を説明する。
鍵生成装置３０は、ＰＨＰＥ．ＫｅｙＧｅｎアルゴリズムを実行するコンピュータである。
鍵生成装置３０は、プロセッサ３１と、メモリ３２と、ストレージ３３と、通信インタフェース３４とのハードウェアを備える。プロセッサ３１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００５２】
鍵生成装置３０は、機能構成要素として、マスター鍵取得部３１１と、関数取得部３１２と、ＰＧＢ計算部３１３と、鍵生成部３１４と、送信部３１５とを備える。鍵生成装置３０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ３３には、鍵生成装置３０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ３１によりメモリ３２に読み込まれ、プロセッサ３１によって実行される。これにより、鍵生成装置３０の各機能構成要素の機能が実現される。
【００５３】
図５を参照して、実施の形態１に係る復号装置４０の構成を説明する。
復号装置４０は、ＰＨＰＥ．Ｄｅｃｒｙｐｔアルゴリズムを実行するコンピュータである。
復号装置４０は、プロセッサ４１と、メモリ４２と、ストレージ４３と、通信インタフェース４４とのハードウェアを備える。プロセッサ４１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００５４】
復号装置４０は、機能構成要素として、マスター鍵取得部４１１と、暗号文取得部４１２と、復号鍵取得部４１３と、復号部４１４とを備える。復号部４１４は、余因子計算部４１５と、ペアリング演算部４１６と、出力値計算部４１７とを備える。復号装置４０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ４３には、復号装置４０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ４１によりメモリ４２に読み込まれ、プロセッサ４１によって実行される。これにより、復号装置４０の各機能構成要素の機能が実現される。
【００５５】
プロセッサ１１，２１，３１，４１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ１１，２１，３１，４１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００５６】
メモリ１２，２２，３２，４２は、データを一時的に記憶する記憶装置である。メモリ１２，２２，３２，４２は、具体例としては、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００５７】
ストレージ１３，２３，３３，４３は、データを保管する記憶装置である。ストレージ１３，２３，３３，４３は、具体例としては、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、ストレージ１３，２３，３３，４３は、ＳＤ（登録商標，Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ，登録商標）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）といった可搬記録媒体であってもよい。
【００５８】
通信インタフェース１４，２４，３４，４４は、外部の装置と通信するためのインタフェースである。通信インタフェース１４，２４，３４，４４は、具体例としては、Ｅｔｈｅｒｎｅｔ（登録商標）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＨＤＭＩ（登録商標，Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）のポートである。
【００５９】
図２では、プロセッサ１１は、１つだけ示されていた。しかし、プロセッサ１１は、複数であってもよく、複数のプロセッサ１１が、各機能を実現するプログラムを連携して実行してもよい。同様に、プロセッサ２１，３１，４１は、複数であってもよく、複数のプロセッサ２１，３１，４１が、各機能を実現するプログラムを連携して実行してもよい。
【００６０】
図６から図１１を参照して、実施の形態１に係る暗号システム１の動作を説明する。
実施の形態１に係る暗号システム１の動作は、実施の形態１に係る暗号方法に相当する。また、実施の形態１に係る暗号システム１の動作は、実施の形態１に係る暗号プログラムの処理に相当する。
【００６１】
図６を参照して、実施の形態１に係るセットアップ装置１０の動作を説明する。
実施の形態１に係るセットアップ装置１０の動作は、実施の形態１に係るセットアップ方法に相当する。また、実施の形態１に係るセットアップ装置１０の動作は、実施の形態１に係るセットアッププログラムの処理に相当する。
【００６２】
（ステップＳ１１：受付処理）
受付部１１１は、セキュリティパラメータλと、公開属性ベクトルの長さｎ’と、秘密属性ベクトルの長さｎとの入力を受け付ける。公開属性ベクトルの長さｎ’と、秘密属性ベクトルの長さｎとは、いずれも１以上の整数である。
具体的には、受付部１１１は、通信インタフェース１４を介して、セットアップ装置１０のユーザによって入力されたセキュリティパラメータ１λを受け付ける。受付部１１１は、セキュリティパラメータ１λをメモリ１２に書き込む。
【００６３】
（ステップＳ１２：基底生成処理）
マスター鍵生成部１１２は、ステップＳ１１で受付されたセキュリティパラメータλと、公開属性ベクトルの長さｎ’と、秘密属性ベクトルの長さｎとを入力として、ｐａｒａｍｓ及び正規直交な双対基底｛Ｂι，Ｂ＊ι｝ι∈［ｎ’＋ｎ］を生成する。
具体的には、マスター鍵生成部１１２は、セキュリティパラメータλと、公開属性ベクトルの長さｎ’と、秘密属性ベクトルの長さｎとメモリ１２から読み出す。マスター鍵生成部１１２は、Ｎ＝ｎ’＋ｎ、ｄ０＝０、ｄ１，．．．，ｄＮ＝９として、数１４１に示すアルゴリズムＧＯＢを実行して、ｐａｒａｍｓ及び双対基底｛Ｂι，Ｂ＊ι｝ι∈［ｎ’＋ｎ］を生成する。マスター鍵生成部１１２は、ｐａｒａｍｓ及び双対基底｛Ｂι，Ｂ＊ι｝ι∈［ｎ’＋ｎ］をメモリ１２に書き込む。
【数１４１】
2020056960.tif 000043
【００６４】
（ステップＳ１３：マスター鍵生成処理）
マスター鍵生成部１１２は、ステップＳ１２で生成されたｐａｒａｍｓ及び双対基底｛Ｂι，Ｂ＊ι｝ι∈［ｎ’＋ｎ］から、公開パラメータＭＰＫ及びマスター秘密鍵ＭＳＫを生成する。
具体的には、マスター鍵生成部１１２は、ｐａｒａｍｓ及び双対基底｛Ｂι，Ｂ＊ι｝ι∈［ｎ’＋ｎ］をメモリ１２から読み出す。マスター鍵生成部１１２は、数１４２に示すように、ι∈［ｎ’＋ｎ］の各整数ιについて、部分基底Ｂ＾ι及び部分基底Ｂ＾＊ιを生成する。
【数１４２】
2020056960.tif 000044
マスター鍵生成部１１２は、ｐａｒａｍｓ及びι∈［ｎ’＋ｎ］の各整数ιについての部分基底Ｂ＾ιを公開パラメータＭＰＫとして設定する。また、マスター鍵生成部１１２は、ι∈［ｎ’＋ｎ］の各整数ιについての部分基底Ｂ＾＊ιをマスター秘密鍵ＭＳＫとして設定する。マスター鍵生成部１１２は、公開パラメータＭＰＫ及びマスター秘密鍵ＭＳＫをメモリ１２に書き込む。
【００６５】
（ステップＳ１４：送信処理）
送信部１１３は、ステップＳ１３で生成された公開パラメータＭＰＫを公開する。具体的には、送信部１１３は、公開パラメータＭＰＫをメモリ１２から読み出す。送信部１１３は、公開パラメータＭＰＫを公開用のサーバに送信するといった方法により、公開する。これにより、暗号化装置２０と鍵生成装置３０と復号装置４０とは、公開パラメータＭＰＫを取得可能になる。
送信部１１３は、ステップＳ１３で生成されたマスター秘密鍵ＭＳＫを鍵生成装置３０に秘密裡に送信する。具体的には、送信部１１３は、メモリ１２からマスター秘密鍵ＭＳＫを読み出す。送信部１１３は、マスター秘密鍵ＭＳＫを、既存の暗号化方式で暗号化した上で鍵生成装置３０に送信する。
【００６６】
つまり、セットアップ装置１０は、数１４３に示すＰＨＰＥ．Ｓｅｔｕｐアルゴリズムを実行する。
【数１４３】
2020056960.tif 000045
【００６７】
図７を参照して、実施の形態１に係る暗号化装置２０の動作を説明する。
実施の形態１に係る暗号化装置２０の動作は、実施の形態１に係る暗号化方法に相当する。また、実施の形態１に係る暗号化装置２０の動作は、実施の形態１に係る暗号化プログラムの処理に相当する。
【００６８】
（ステップＳ２１：マスター鍵取得処理）
マスター鍵取得部２１１は、セットアップ装置１０によって生成された公開パラメータＭＰＫを取得する。
具体的には、マスター鍵取得部２１１は、通信インタフェース２４を介して、公開された公開パラメータＭＰＫを取得する。マスター鍵取得部２１１は、公開パラメータＭＰＫをメモリ２２に書き込む。
【００６９】
（ステップＳ２２：ベクトル取得処理）
ベクトル取得部２１２は、公開属性ベクトルｘ→∈Ｆｑｎ’及び秘密属性ベクトルｚ→∈Ｆｑｎを取得する。
具体的には、ベクトル取得部２１２は、通信インタフェース２４を介して、暗号化装置２０のユーザによって入力された公開属性ベクトルｘ→及び秘密属性ベクトルｚ→を取得する。ベクトル取得部２１２は、公開属性ベクトルｘ→及び秘密属性ベクトルｚ→をメモリ２２に書き込む。
【００７０】
（ステップＳ２３：暗号化処理）
暗号化部２１３は、ステップＳ２１で取得された公開パラメータＭＰＫと、ステップＳ２２で取得された公開属性ベクトルｘ→及び秘密属性ベクトルｚ→とを用いて、暗号文ＣＴを生成する。
具体的には、暗号化部２１３は、以下のように暗号文ＣＴを生成する。
まず、暗号化部２１３は、数１４４に示すように、値ωをサンプリングする。
【数１４４】
2020056960.tif 000046
次に、暗号化部２１３は、数１４５に示すように、ι’∈［ｎ’］の各整数ι’について、値φ’ι’をサンプリングし、要素ｃ’（ι’）を生成する。
【数１４５】
2020056960.tif 000047
また、暗号化部２１３は、数１４６に示すように、ι∈［ｎ］の各整数ιについて、値φιをサンプリングし、要素ｃ（ι）を生成する。
【数１４６】
2020056960.tif 000048
そして、暗号化部２１３は、公開属性ベクトルｘ→と、ι’∈［ｎ’］の各整数ι’についての要素ｃ’（ι’）と、ι∈［ｎ］の各整数ιについての要素ｃ（ι）とを暗号文ＣＴとして設定する。暗号化部２１３は、暗号文ＣＴをメモリ２２に書き込む。
【００７１】
実施の形態１では、暗号文ＣＴは、双対ベクトル空間における双対基底である基底Ｂ及び基底Ｂ＊のうちの基底Ｂに、公開属性ベクトルｘ→が設定された要素ｃ’（ι’）と、秘密属性ベクトルｚ→が設定された要素ｃ（ι）とを含む。
【００７２】
（ステップＳ２４：送信処理）
送信部２１４は、ステップＳ２３で生成された暗号文ＣＴを復号装置４０に送信する。
具体的には、送信部２１４は、暗号文ＣＴをメモリ２２から読み出す。送信部２１４は、通信インタフェース２４を介して、暗号文ＣＴを復号装置４０に送信する。
【００７３】
つまり、暗号化装置２０は、数１４７に示すＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムを実行する。
【数１４７】
2020056960.tif 000049
【００７４】
図８を参照して、実施の形態１に係る鍵生成装置３０の動作を説明する。
実施の形態１に係る鍵生成装置３０の動作は、実施の形態１に係る鍵生成方法に相当する。また、実施の形態１に係る鍵生成装置３０の動作は、実施の形態１に係る鍵生成プログラムの処理に相当する。
【００７５】
（ステップＳ３１：マスター鍵取得処理）
マスター鍵取得部３１１は、セットアップ装置１０によって生成された公開パラメータＭＰＫ及びマスター秘密鍵ＭＳＫを取得する。
具体的には、マスター鍵取得部３１１は、通信インタフェース３４を介して、公開された公開パラメータＭＰＫを取得するとともに、セットアップ装置１０によって送信されたマスター秘密鍵ＭＳＫを取得する。マスター鍵取得部３１１は、公開パラメータＭＰＫ及びマスター秘密鍵ＭＳＫをメモリ３２に書き込む。
【００７６】
（ステップＳ３２：関数取得処理）
関数取得部３１２は、関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰを取得する。
具体的には、関数取得部３１２は、通信インタフェース３４を介して、鍵生成装置３０のユーザによって入力された関数ｆを取得する。関数取得部３１２は、関数ｆをメモリ３２に書き込む。
【００７７】
（ステップＳ３３：ＰＧＢ計算処理）
ＰＧＢ計算部３１３は、数１４８に示すように、ステップＳ３２で取得された関数ｆを入力として、ＰＧＢアルゴリズムを実行することにより、割当値を特定するための定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）∈Ｆｑｎ×（Ｆｑ２）ｍと、関数ρ：［ｍ］→［ｎ’］とを計算する。
【数１４８】
2020056960.tif 000050
【００７８】
図９を参照して、実施の形態１に係るＰＧＢ計算処理を説明する。
（ステップＳ３３１：行列表現Ｌ生成処理）
Γ’は、関数ｆを計算するＡＢＰを示すとする。ＡＢＰΓ’は、ｍ＋ｎ＋１個の頂点を有しており、変数ｚｊは、シンク頂点への入力辺にのみ設定される。そして、どの頂点も１つの出力辺のみを有している。
そこで、ＰＧＢ計算部３１３は、ＡＢＰΓ’を示す行列表現Ｌ∈Ｆｑ（ｍ＋ｎ）×（ｍ＋ｎ）を計算する。上述した通り、行列Ｌは、行列ＡΓ’−Ｉから、Ｖ０に対応する列と、Ｖ１に対応する行とを取り除くことによって得られる。ここで、行列ＡΓは、Γに対する隣接行列である。Ｉは単位行列である。
すると、以下の（１）から（４）が成立する。
（１）全ての（ｘ→，ｚ→）∈Ｆｑｎ’×Ｆｑｎに対して、ｄｅｔ（Ｌ（ｘ→，ｚ→））＝ｆ（ｘ→，ｚ→）である。
（２）ｊ’∈［ｍ］の各整数ｊ’に対して、行列表現Ｌのｊ’行の成分は、Ｆｑにおける係数を伴う１つの変数ｘι’（ι’∈［ｎ’］）の１次式、又は、Ｆｑにおける定数である。
（３）行列表現Ｌは、第２対角には−１だけを含み、第２対角の下には０だけを含む。
（４）行列表現Ｌの最後の列は、（０，．．．，０，ｚ１，．．．，ｚｎ）である。
【００７９】
（ステップＳ３３２：関数ρ生成処理）
ＰＧＢ計算部３１３は、ｊ’∈［ｍ］の各整数ｊ’について、行列表現Ｌのｊ’行に変数ｘι’が含まれるなら、ρ（ｊ’）＝ι’と設定することにより、関数ρ：［ｍ］→［ｎ’］を生成する。定数計算部３１３は、関数ρをメモリ３２に書き込む。
【００８０】
（ステップＳ３３３：定数計算処理）
ＰＧＢ計算部３１３は、数１４９に示すように、ベクトルｒ→を選択する。
【数１４９】
2020056960.tif 000051
ＰＧＢ計算部３１３は、ステップＳ３３１で生成された行列表現Ｌと、ベクトルｒ→とを用いて、数１５０に示すように、定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）∈Ｆｑｎ×（Ｆｑ２）ｍを計算する。
【数１５０】
2020056960.tif 000052
これにより、定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）が生成される。定数計算部３１３は、定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）をメモリ３２に書き込む。この定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）をＡＢＰの述語ベクトルと呼ぶ。
【００８１】
（ステップＳ３４：鍵生成処理）
鍵生成部３１４は、ステップＳ３１で取得された公開パラメータＭＰＫ及びマスター秘密鍵ＭＳＫと、ステップＳ３２で取得された関数ｆと、ステップＳ３３で生成された定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）とを用いて、復号鍵ＳＫ（ｆ）を生成する。
具体的には、鍵生成部３１４は、以下のように復号鍵ＳＫ（ｆ）を生成する。
まず、鍵生成部３１４は、数１５１に示すように、値ζをサンプリングする。
【数１５１】
2020056960.tif 000053
次に、鍵生成部３１４は、数１５２に示すように、ｊ’∈［ｍ］の各整数ｊ’について、κ→’（ｊ’）をサンプリングし、要素ｋ’（ｊ’）を生成する。
【数１５２】
2020056960.tif 000054
また、鍵生成部３１４は、数１５３に示すように、ｊ∈［ｎ］の各整数ｊについて、κ→（ｊ）をサンプリングし、要素ｋ（ｊ）を生成する。
【数１５３】
2020056960.tif 000055
そして、鍵生成部３１４は、関数ｆと、ｊ’∈［ｍ］の各整数ｊ’についての要素ｋ’（ｊ’）と、ｊ∈［ｎ］の各整数ｊについての要素ｋ（ｊ）とを復号鍵ＳＫ（ｆ）として設定する。鍵生成部３１４は、復号鍵ＳＫ（ｆ）をメモリ３２に書き込む。
【００８２】
実施の形態１では、復号鍵ＳＫ（ｆ）は、双対ベクトル空間における双対基底である基底Ｂ及び基底Ｂ＊のうちの基底Ｂ＊に、ＡＢＰの述語ベクトルが設定された要素ｋ’（ｊ’）及び要素ｋ（ｊ）を含む。
【００８３】
（ステップＳ３５：送信処理）
送信部３１５は、ステップＳ３４で生成された復号鍵ＳＫ（ｆ）を秘密裡に復号装置４０に送信する。
具体的には、送信部３１５は、復号鍵ＳＫ（ｆ）をメモリ３２から読み出す。送信部３１５は、復号鍵ＳＫ（ｆ）を既存の暗号化方式で暗号化した上で、通信インタフェース３４を介して復号装置４０に送信する。
【００８４】
つまり、鍵生成装置３０は、数１５４に示すＰＨＰＥ．ＫｅｙＧｅｎアルゴリズムを実行する。
【数１５４】
2020056960.tif 000056
【００８５】
図１０を参照して、実施の形態１に係る復号装置４０の動作を説明する。
実施の形態１に係る復号装置４０の動作は、実施の形態１に係る復号方法に相当する。また、実施の形態１に係る復号装置４０の動作は、実施の形態１に係る復号プログラムの処理に相当する。
【００８６】
（ステップＳ４１：公開鍵取得処理）
マスター鍵取得部４１１は、セットアップ装置１０によって生成された公開パラメータＭＰＫを取得する。
具体的には、マスター鍵取得部４１１は、通信インタフェース４４を介して、公開された公開パラメータＭＰＫを取得する。マスター鍵取得部４１１は、公開パラメータＭＰＫをメモリ４２に書き込む。
【００８７】
（ステップＳ４２：暗号文取得処理）
暗号文取得部４１２は、暗号化装置２０によって生成された暗号文ＣＴを取得する。
具体的には、暗号文取得部４１２は、通信インタフェース４４を介して、暗号化装置２０によって送信された暗号文ＣＴを取得する。暗号文取得部４１２は、暗号文ＣＴをメモリ４２に書き込む。
【００８８】
（ステップＳ４３：復号鍵取得処理）
復号鍵取得部４１３は、鍵生成装置３０によって生成された復号鍵ＳＫ（ｆ）を取得する。
具体的には、復号鍵取得部４１３は、通信インタフェース４４を介して、鍵生成装置３０によって送信された復号鍵ＳＫ（ｆ）を取得する。復号鍵取得部４１３は、復号鍵ＳＫ（ｆ）をメモリ４２に書き込む。
【００８９】
（ステップＳ４４：復号処理）
復号部４１４は、ステップＳ４２で取得された暗号文ＣＴと、ステップＳ４３で取得された復号鍵ＳＫ（ｆ）とについてペアリング演算を行うことにより、暗号文ＣＴを復号する。
【００９０】
図１１を参照して、実施の形態１に係る復号処理を説明する。
（ステップＳ４４１：余因子計算処理）
余因子計算部４１５は、数１５５に示すように、復号鍵ＳＫ（ｆ）に含まれる関数ｆと、暗号文ＣＴに含まれる公開属性ベクトルｘ→とを入力として、ＲＥＣアルゴリズムを実行することにより、係数の集合（（｛Ωｊ｝ｊ∈［ｎ］，｛Ω’ｊ’｝ｊ’∈［ｍ］）∈Ｆｑｎ×Ｆｑｎ’を計算する。
【数１５５】
2020056960.tif 000057
具体的には、余因子計算部４１５は、図９のステップＳ３３１からステップＳ３３２の処理と同様に、関数ｆの行列表現Ｌ及び関数ρを生成する。そして、余因子計算部４１５は、行列表現Ｌの最後の列の要素の余因子を計算する。余因子計算部４１５は、計算された余因子を成分の順に係数の集合（（｛Ωｊ｝ｊ∈［ｎ］，｛Ω’ｊ’｝ｊ’∈［ｍ］）として設定する。ここで、行列表現Ｌの初めのｍ＋ｎ−１列は、変数｛ｘι’｝ι’∈［ｎ’］しか含まない。そのため、余因子は、公開属性ベクトルｘ→を用いて計算可能である。
余因子計算部４１５は、係数の集合（（｛Ωｊ｝ｊ∈［ｎ］，｛Ω’ｊ’｝ｊ’∈［ｍ］）をメモリ４２に書き込む。
【００９１】
（ステップＳ４４２：ペアリング演算処理）
ペアリング演算部４１６は、数１５６に示すように、ｊ’∈［ｍ］の各整数ｊ’について、要素ｃ’（ρ（ｊ’））と、要素ｋ’（ｊ’）とについてペアリング演算を行い、演算値Λ’ｊ’を計算する。ここで、関数ρは、ステップＳ４４１で生成された関数である。
【数１５６】
2020056960.tif 000058
また、ペアリング演算部４１６は、数１５７に示すように、ｊ∈［ｎ］の各整数ｊについて、要素ｃ（ｊ）と、要素ｋ（ｊ）とについてペアリング演算を行い、演算値Λｊを計算する。
【数１５７】
2020056960.tif 000059
ペアリング演算部４１６は、演算値Λ’ｊ’及び演算値Λｊをメモリ４２に書き込む。
【００９２】
（ステップＳ４４３：出力値計算処理）
出力値計算部４１７は、ステップＳ４４１で計算された係数の集合（（｛Ωｊ｝ｊ∈［ｎ］，｛Ω’ｊ’｝ｊ’∈［ｍ］）と、ステップＳ４４２で計算された演算値Λ’ｊ’及び演算値Λｊとをメモリ４２から読み出す。出力値計算部４１７は、数１５８に示すように、演算値Λを計算する。
【数１５８】
2020056960.tif 000060
出力値計算部４１７は、Λが群ＧＴの単位元である場合には出力値として１を出力し、そうでない場合には出力値として０を出力する。
【００９３】
つまり、復号装置４０は、数１５９に示すＰＨＰＥ．Ｄｅｃｒｙｐｔアルゴリズムを実行する。
【数１５９】
2020056960.tif 000061
【００９４】
ここで、演算値Λ’ｊ’及び演算値Λｊは、数１６０に示す通りである。
【数１６０】
2020056960.tif 000062
そして、演算値Λは、数１６１に示す通りである。
【数１６１】
2020056960.tif 000063
そのため、ω＝０又はζ＝０の場合を除いて、ＲＡＢＰ〇ＩＰ（ｆ，（ｘ→，ｚ→））＝１、つまりｆ（ｘ→，ｚ→）＝０なら、数１６２になり、ＲＡＢＰ〇ＩＰ（ｆ，（ｘ→，ｚ→））≠１、つまりｆ（ｘ→，ｚ→）≠０なら、数１６３になる。
【数１６２】
2020056960.tif 000064
【数１６３】
2020056960.tif 000065
【００９５】
数１６１のようになる理由を説明する。
数１６４に示すように、どのようなｚ→に対しても、係数の集合（（｛Ωｊ｝ｊ∈［ｎ］，｛Ω’ｊ’｝ｊ’∈［ｍ］）と、（｛ｚｊ＋σｊ｝ｊ∈［ｎ］，｛αｊ’ｚρ（ｊ’）＋γｊ’｝ｊ’∈［ｍ］）を連接して、ｆ（ｘ→，ｚ→）を計算することができる。
【数１６４】
2020056960.tif 000066
ここで、数１６４は、ｄｅｔ（Ｌ’（ｘ→，ｚ→））を計算することに対応している。行列表現Ｌ’は、行列表現Ｌの最後の列を数１６５に置き換えて得られた行列表現である。
【数１６５】
2020056960.tif 000067
そのため、数１６６が成立し、数１６４が成立することが分かる。
【数１６６】
2020056960.tif 000068
ここで、ｒ→＝（ｒ１，．．．，ｒｍ＋ｎ−１）∈Ｆｑｍ＋ｎ−１は、定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）を生成する際にＰＢＧによって用いられたランダム性である。
そして、数１６７が成立する。
【数１６７】
2020056960.tif 000069
なぜなら、最後の列の初めのｍ個の成分は０であるため、数１６８である。
【数１６８】
2020056960.tif 000070
したがって、数１６９である。
【数１６９】
2020056960.tif 000071
【００９６】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る暗号システム１は、双対ベクトル空間における双対基底である基底Ｂに属性ベクトルが設定された暗号文と、基底Ｂ＊にＡＢＰの述語ベクトルが設定された復号鍵とについてペアリング演算が行われ、暗号文が復号される。これにより、幅広い述語を許容しつつ、安全性を高くすることが可能な述語暗号方式を実現することが可能になる。
【００９７】
＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、ＫＰ−ＰＨＰＥ方式を説明した。実施の形態１で説明したＫＰ−ＰＨＰＥ方式をＣＰ（Ｃｉｐｈｅｒ−Ｐｏｌｉｃｙ）−ＰＨＰＥ方式に変換することができる。ＣＰは、暗号文にアクセスコントロールのための情報が設定されるという意味である。実施の形態１でのアクセスコントロールのための情報は、関数ｆ及び定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）である。
そこで、ＣＰ−ＰＨＰＥ方式の場合には、ＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムにおいて、関数ｆを入力として、ＰＧＢアルゴリズムが実行され、定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）が生成される。ＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムにおいて、実施の形態１における要素ｋ’（ｊ’）及び要素ｋ（ｊ）に相当する定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）を設定した要素ｃ’（ｊ’）及び要素ｃ（ｊ）が生成される。そして、関数ｆと、要素ｃ’（ｊ’）及び要素ｃ（ｊ）とが暗号文ＣＴとして設定される。
また、ＣＰ−ＰＨＰＥ方式の場合には、ＰＨＰＥ．ＫｅｙＧｅｎアルゴリズムにおいて、実施の形態１における要素ｃ’（ι’）に相当する公開属性ベクトルｘ→が設定された要素ｋ’（ι’）と、実施の形態１における要素ｃ（ι）に相当する秘密属性ベクトルｚ→が設定された要素ｋ（ι）とが生成される。そして、公開属性ベクトルｘ→と、要素ｋ’（ι’）及び要素ｋ（ι）が復号鍵ＳＫ（ｆ）として設定される。
【００９８】
＜変形例２＞
実施の形態１では、ι∈［ｎ’＋ｎ］の各整数ιについて、基底Ｂι及び基底Ｂ＊ιを生成した。そして、公開属性ベクトルｘ→及び秘密属性ベクトルｚ→の要素毎に異なる基底を用いた。しかし、インデックス付けの技法を用いることにより、基底Ｂ及び基底Ｂ＊の１つの双対基底だけを用いて、ＰＨＰＥ方式を実現することが可能である。これにより、Ｕｎｂｏｕｎｄｅｄ化することが可能である。
具体的には、例えば、基底Ｂ及び基底Ｂ＊の次元が２次元追加される。そして、追加された２次元を用いて、暗号文ＣＴの要素ｃ’（ι’）及び要素ｃ（ι）と、復号鍵ＳＫ（ｆ）の要素ｋ’（ｊ’）及び要素ｋ（ｊ）とに、公開属性ベクトルｘ→及び秘密属性ベクトルｚ→の要素に応じたインデックスが設定される。この際、暗号文ＣＴの要素ｃ’（ι’）及び要素ｃ（ι）と、復号鍵ＳＫ（ｆ）の要素ｋ’（ｊ’）及び要素ｋ（ｊ）とには、ペアリング演算が行われた場合に追加した２次元の値が０になるように、インデックスが設定される。
【００９９】
＜変形例３＞
実施の形態１では、各機能構成要素がソフトウェアで実現された。しかし、変形例３として、各機能構成要素はハードウェアで実現されてもよい。この変形例３について、実施の形態１と異なる点を説明する。
【０１００】
図１２を参照して、変形例３に係るセットアップ装置１０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、セットアップ装置１０は、プロセッサ１１とメモリ１２とストレージ１３とに代えて、電子回路１５を備える。電子回路１５は、各機能構成要素と、メモリ１２と、ストレージ１３との機能とを実現する専用の回路である。
【０１０１】
図１３を参照して、変形例３に係る暗号化装置２０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、暗号化装置２０は、プロセッサ２１とメモリ２２とストレージ２３とに代えて、電子回路２５を備える。電子回路２５は、各機能構成要素と、メモリ２２と、ストレージ２３との機能とを実現する専用の回路である。
【０１０２】
図１４を参照して、変形例３に係る鍵生成装置３０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、鍵生成装置３０は、プロセッサ３１とメモリ３２とストレージ３３とに代えて、電子回路３５を備える。電子回路３５は、各機能構成要素と、メモリ３２と、ストレージ３３との機能とを実現する専用の回路である。
【０１０３】
図１５を参照して、変形例３に係る復号装置４０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、復号装置４０は、プロセッサ４１とメモリ４２とストレージ４３とに代えて、電子回路４５を備える。電子回路４５は、各機能構成要素と、メモリ４２と、ストレージ４３との機能とを実現する専用の回路である。
【０１０４】
電子回路１５，２５，３５，４５としては、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
各機能構成要素を１つの電子回路１５，２５，３５，４５で実現してもよいし、各機能構成要素を複数の電子回路１５，２５，３５，４５に分散させて実現してもよい。
【０１０５】
＜変形例４＞
変形例４として、一部の各機能構成要素がハードウェアで実現され、他の各機能構成要素がソフトウェアで実現されてもよい。
【０１０６】
プロセッサ１１，２１，３１，４１とメモリ１２，２２，３２，４２とストレージ１３，２３，３３，４３と電子回路１５，２５，３５，４５とを処理回路という。つまり、各機能構成要素の機能は、処理回路により実現される。
【０１０７】
実施の形態２．
実施の形態２では、実施の形態１で説明したＰＨＰＥ方式を変換したＫＥＭ（Ｋｅｙ−Ｅｎｃａｐｓｕｌａｔｉｏｎ  Ｍｅｃｈａｎｉｓｍ）方式を説明する。実施の形態２では、実施の形態１と異なる点を説明し、同一の点については説明を省略する。
【０１０８】
＊＊＊構成の説明＊＊＊
＜ＫＥＭ  ｖｅｒｓｉｏｎ  ＰＨＰＥの構成＞
実施の形態２では、ＫＥＭ  ｖｅｒｓｉｏｎ  ＫＰ−ＰＨＰＥ方式を説明する。
ＫＥＭ  ｖｅｒｓｉｏｎ  ＫＰ−ＰＨＰＥ方式は、ＰＨＰＥ．Ｓｅｔｕｐアルゴリズムと、ＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムと、ＰＨＰＥ．ＫｅｙＧｅｎアルゴリズムと、ＰＨＰＥ．Ｄｅｃｒｙｐｔアルゴリズムとを含む。
【０１０９】
ＰＨＰＥ．Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλと、公開属性ベクトルの長さｎ’と、秘密属性ベクトルの長さｎとを入力として、公開パラメータＭＰＫとマスター秘密鍵ＭＳＫとを出力する。
【０１１０】
ＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムは、公開パラメータＭＰＫと、公開属性ベクトルｘ→∈Ｆｑｎ’と、秘密属性ベクトルｚ→∈Ｆｑｎとを入力として、暗号文ＣＴと、セッション鍵ＫＥＭとを出力する。
【０１１１】
ＰＨＰＥ．ＫｅｙＧｅｎアルゴリズムは、公開パラメータＭＰＫと、マスター秘密鍵ＭＳＫと、関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰとを入力として、復号鍵ＳＫ（ｆ）を出力する。
【０１１２】
ＰＨＰＥ．Ｄｅｃｒｙｐｔアルゴリズムは、公開パラメータＭＰＫと、関数ｆ∈Ｆ（ｑ，ｎ’，ｎ）ＡＢＰ〇ＩＰ及び関数ｆに対する復号鍵ＳＫ（ｆ）のペアと、公開属性ベクトルｘ→及び公開属性ベクトルｘ→に関する暗号文ＣＴのペアとを入力として、セッション鍵ＫＥＹ〜を出力する。
【０１１３】
＊＊＊動作の説明＊＊＊
図６から図１１を参照して、実施の形態２に係る暗号システム１の動作を説明する。
実施の形態２に係る暗号システム１の動作は、実施の形態２に係る暗号方法に相当する。また、実施の形態２に係る暗号システム１の動作は、実施の形態２に係る暗号プログラムの処理に相当する。
【０１１４】
図６を参照して、実施の形態２に係るセットアップ装置１０の動作を説明する。
実施の形態２に係るセットアップ装置１０の動作は、実施の形態２に係るセットアップ方法に相当する。また、実施の形態２に係るセットアップ装置１０の動作は、実施の形態２に係るセットアッププログラムの処理に相当する。
【０１１５】
ステップＳ１１とステップＳ１４との処理は、実施の形態１と同じである。
【０１１６】
（ステップＳ１２：基底生成処理）
マスター鍵生成部１１２は、ステップＳ１１で受付されたセキュリティパラメータλと、公開属性ベクトルの長さｎ’と、秘密属性ベクトルの長さｎとを入力として、ｐａｒａｍｓ及び正規直交な双対基底｛Ｂι，Ｂ＊ι｝ι∈［０，ｎ’＋ｎ］を生成する。
具体的には、マスター鍵生成部１１２は、Ｎ＝ｎ’＋ｎ＋１、ｄ０＝６、ｄ１，．．．，ｄＮ＝９として、実施の形態１と同じアルゴリズムＧＯＢを実行して、ｐａｒａｍｓ及び双対基底｛Ｂι，Ｂ＊ι｝ι∈［ｎ’＋ｎ］を生成する。Ｎ＝ｎ’＋ｎ＋１、ｄ０＝６としている点が実施の形態１と異なる。
【０１１７】
（ステップＳ１３：マスター鍵生成処理）
マスター鍵生成部１１２は、ステップＳ１２で生成されたｐａｒａｍｓ及び双対基底｛Ｂι，Ｂ＊ι｝ι∈［０，ｎ’＋ｎ］から、公開パラメータＭＰＫ及びマスター秘密鍵ＭＳＫを生成する。
具体的には、マスター鍵生成部１１２は、数１７０に示すように、部分基底Ｂ＾０及び部分基底Ｂ＾＊０を生成するとともに、数１７１に示すように、ι∈［ｎ’＋ｎ］の各整数ιについて、部分基底Ｂ＾ι及び部分基底Ｂ＾＊ιを生成する。
【数１７０】
2020056960.tif 000072
【数１７１】
2020056960.tif 000073
マスター鍵生成部１１２は、ｐａｒａｍｓ及びι∈［０，ｎ’＋ｎ］の各整数ιについての部分基底Ｂ＾ιを公開パラメータＭＰＫとして設定する。また、マスター鍵生成部１１２は、ι∈［０，ｎ’＋ｎ］の各整数ιについての部分基底Ｂ＾＊ιをマスター秘密鍵ＭＳＫとして設定する。
【０１１８】
つまり、セットアップ装置１０は、数１７２に示すＰＨＰＥ．Ｓｅｔｕｐアルゴリズムを実行する。
【数１７２】
2020056960.tif 000074
【０１１９】
図７を参照して、実施の形態２に係る暗号化装置２０の動作を説明する。
実施の形態２に係る暗号化装置２０の動作は、実施の形態２に係る暗号化方法に相当する。また、実施の形態２に係る暗号化装置２０の動作は、実施の形態２に係る暗号化プログラムの処理に相当する。
【０１２０】
ステップＳ２３以外の処理は、実施の形態１と同じである。
【０１２１】
（ステップＳ２３：暗号化処理）
暗号化部２１３は、ステップＳ２１で取得された公開パラメータＭＰＫと、ステップＳ２２で取得された公開属性ベクトルｘ→及び秘密属性ベクトルｚ→とを用いて、暗号文ＣＴを生成する。
具体的には、暗号化部２１３は、以下のように暗号文ＣＴを生成する。
まず、暗号化部２１３は、数１７３に示すように、値ω，ξ，φ’０をサンプリングする。
【数１７３】
2020056960.tif 000075
次に、暗号化部２１３は、数１７４に示すように、要素ｃ’（０）を生成する。
【数１７４】
2020056960.tif 000076
また、暗号化部２１３は、ｇＴξをセッション鍵ＫＥＭとして設定する。さらに、暗号化部２１３は、実施の形態１と同様に、ι’∈［ｎ’］の各整数ι’について要素ｃ’（ι’）を生成し、ι∈［ｎ］の各整数ιについて要素ｃ（ι）を生成する。
そして、暗号化部２１３は、公開属性ベクトルｘ→と、要素ｃ’（０）と、ι’∈［ｎ’］の各整数ι’についての要素ｃ’（ι’）と、ι∈［ｎ］の各整数ιについての要素ｃ（ι）とを暗号文ＣＴとして設定する。
【０１２２】
つまり、暗号化装置２０は、数１７５に示すＰＨＰＥ．Ｅｎｃｒｙｐｔアルゴリズムを実行する。
【数１７５】
2020056960.tif 000077
【０１２３】
図８を参照して、実施の形態２に係る鍵生成装置３０の動作を説明する。
実施の形態２に係る鍵生成装置３０の動作は、実施の形態２に係る鍵生成方法に相当する。また、実施の形態２に係る鍵生成装置３０の動作は、実施の形態２に係る鍵生成プログラムの処理に相当する。
【０１２４】
ステップＳ３４以外の処理は、実施の形態１と同じである。
【０１２５】
（ステップＳ３４：鍵生成処理）
鍵生成部３１４は、ステップＳ３１で取得された公開パラメータＭＰＫ及びマスター秘密鍵ＭＳＫと、ステップＳ３２で取得された関数ｆと、ステップＳ３３で生成された定数の集合（｛σｊ｝ｊ∈［ｎ］，｛αｊ’，γｊ’｝ｊ’∈［ｍ］）とを用いて、復号鍵ＳＫ（ｆ）を生成する。
具体的には、鍵生成部３１４は、以下のように復号鍵ＳＫ（ｆ）を生成する。
まず、鍵生成部３１４は、数１７６に示すように、値ｒ０，κ’０，ζをサンプリングする。
【数１７６】
2020056960.tif 000078
次に、鍵生成部３１４は、数１７７に示すように、要素ｋ’（０）を生成する。
【数１７７】
2020056960.tif 000079
また、鍵生成部３１４は、ｊ’∈［ｍ］の各整数ｊ’について数１７８に示すように要素ｋ’（ｊ’）を生成し、ｊ∈［ｎ］の各整数ｊについて数１７９に示すように要素ｋ（ｊ）を生成する。
【数１７８】
2020056960.tif 000080
【数１７９】
2020056960.tif 000081
そして、鍵生成部３１４は、関数ｆと、ｊ’∈［ｍ］の各整数ｊ’についての要素β’ｊ’と、ｊ∈［ｎ］の各整数ｊについての要素βｊと、要素ｋ’（０）と、ｊ’∈［ｍ］の各整数ｊ’についての要素ｋ’（ｊ’）と、ｊ∈［ｎ］の各整数ｊについての要素ｋ（ｊ）とを復号鍵ＳＫ（ｆ）として設定する。
【０１２６】
つまり、鍵生成装置３０は、数１８０に示すＰＨＰＥ．ＫｅｙＧｅｎアルゴリズムを実行する。
【数１８０】
2020056960.tif 000082
【０１２７】
図１０を参照して、実施の形態２に係る復号装置４０の動作を説明する。
実施の形態２に係る復号装置４０の動作は、実施の形態２に係る復号方法に相当する。また、実施の形態２に係る復号装置４０の動作は、実施の形態２に係る復号プログラムの処理に相当する。
【０１２８】
ステップＳ４４以外の処理は、実施の形態１と同じである。
【０１２９】
（ステップＳ４４：復号処理）
復号部４１４は、ステップＳ４２で取得された暗号文ＣＴと、ステップＳ４３で取得された復号鍵ＳＫ（ｆ）とについてペアリング演算を行うことにより、暗号文ＣＴを復号する。
【０１３０】
図１１を参照して、実施の形態１に係る復号処理を説明する。
ステップＳ４４１の処理は、実施の形態１と同じである。
【０１３１】
（ステップＳ４４２：ペアリング演算処理）
ペアリング演算部４１６は、数１８１に示すように、要素ｃ’（０）と、要素ｋ’（０）とについてペアリング演算を行い、演算値Λ’０を計算する。
【数１８１】
2020056960.tif 000083
また、ペアリング演算部４１６は、実施の形態１と同様に、ｊ’∈［ｍ］の各整数ｊ’について演算値Λ’ｊ’を計算し、ｊ∈［ｎ］の各整数ｊについて演算値Λｊを計算する。
ペアリング演算部４１６は、演算値Λ’０と演算値Λ’ｊ’と演算値Λｊとをメモリ４２に書き込む。
【０１３２】
（ステップＳ４４３：出力値計算処理）
出力値計算部４１７は、ステップＳ４４１で計算された係数の集合（（｛Ωｊ｝ｊ∈［ｎ］，｛Ω’ｊ’｝ｊ’∈［ｍ］）と、ステップＳ４４２で計算された演算値Λ’０と演算値Λ’ｊ’と演算値Λｊとをメモリ４２から読み出す。出力値計算部４１７は、数１８２に示すように、演算値Λを計算する。
【数１８２】
2020056960.tif 000084
出力値計算部４１７は、数１８３に示すように、セッション鍵ＫＥＭ〜を計算する。
【数１８３】
2020056960.tif 000085
【０１３３】
つまり、復号装置４０は、数１８４に示すＰＨＰＥ．Ｄｅｃｒｙｐｔアルゴリズムを実行する。
【数１８４】
2020056960.tif 000086
【０１３４】
ここで、演算値Λ’０と演算値Λ’ｊ’と演算値Λｊとは、数１８５に示す通りである。
【数１８５】
2020056960.tif 000087
そして、演算値Λは、数１８６に示す通りである。
【数１８６】
2020056960.tif 000088
そのため、ＲＡＢＰ〇ＩＰ（ｆ，（ｘ→，ｚ→））＝１、つまりｆ（ｘ→，ｚ→）＝０なら、数１８７になる。
【数１８７】
2020056960.tif 000089
したがって、ＫＥＭ〜＝ｇＴξ＝ＫＥＭになる。なお、ＲＡＢＰ〇ＩＰ（ｆ，（ｘ→，ｚ→））≠１、つまりｆ（ｘ→，ｚ→）≠０なら、数１８７にならないので、ＫＥＭ〜≠ｇＴξ＝ＫＥＭになる。
【０１３５】
＊＊＊実施の形態２の効果＊＊＊
以上のように、実施の形態２に係る暗号システム１は、実施の形態１で説明したＰＨＰＥ方式を変換してＫＥＭ方式を実現する。これにより、幅広い述語を許容しつつ、安全性を高くすることが可能なＫＥＭ方式を実現することが可能になる。
【０１３６】
＊＊＊他の構成＊＊＊
＜変形例５＞
実施の形態２では、ＫＰ−ＰＨＰＥ方式を変換してＫＥＭ方式を構成した。同様の変形を加えることにより、変形例１で説明したＣＰ−ＰＨＰＥ方式を変換してＫＥＭ方式を構成することも可能である。
【０１３７】
＜変形例６＞
実施の形態２で説明したＫＥＭ方式についても、変形例２で説明したように、インデックス付けの技法を用いることにより、基底Ｂ及び基底Ｂ＊の１つの双対基底だけを用いて実現することが可能である。
【符号の説明】
【０１３８】
１  暗号システム、１０  セットアップ装置、１１  プロセッサ、１２  メモリ、１３  ストレージ、１４  通信インタフェース、１５  電子回路、１１１  受付部、１１２  マスター鍵生成部、１１３  送信部、２０  暗号化装置、２１  プロセッサ、２２  メモリ、２３  ストレージ、２４  通信インタフェース、２５  電子回路、２１１  マスター鍵取得部、２１２  ベクトル取得部、２１３  暗号化部、２１４  送信部、３０  鍵生成装置、３１  プロセッサ、３２  メモリ、３３  ストレージ、３４  通信インタフェース、３５  電子回路、３１１  マスター鍵取得部、３１２  関数取得部、３１３  定数計算部、３１４  鍵生成部、３１５  送信部、４０  復号装置、４１  プロセッサ、４２  メモリ、４３  ストレージ、４４  通信インタフェース、４５  電子回路、４１１  マスター鍵取得部、４１２  暗号文取得部、４１３  復号鍵取得部、４１４  復号部、４１５  余因子計算部、４１６  ペアリング演算部、４１７  出力値計算部。
【図１】
2020056960.tif 000098
【図２】
2020056960.tif 000099
【図３】
2020056960.tif 000100
【図４】
2020056960.tif 000101
【図５】
2020056960.tif 000102
【図６】
2020056960.tif 000103
【図７】
2020056960.tif 000104
【図８】
2020056960.tif 000105
【図９】
2020056960.tif 000106
【図１０】
2020056960.tif 000107
【図１１】
2020056960.tif 000108
【図１２】
2020056960.tif 000109
【図１３】
2020056960.tif 000110
【図１４】
2020056960.tif 000111
【図１５】
2020056960.tif 000112