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