"階層構造を有する組織内で第k階層kは2以上の特定の整数に属する特定ユーザのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDを用いる暗号システムにおいて、暗号化する平文データMを入力し、入力した平文データMを暗号化して平文暗号値C0を算出し、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンPを入力し、入力したパターンPに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、k個の階層に対応付けられたk個の鍵値Hを含むH鍵値群を含んだ公開鍵PKを入力し、入力した公開鍵PKに含まれるH鍵値群から前記ワイルドカード階層に対応付けられた鍵値Hをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値C0の復号に用いるワイルドカード暗号値C1を算出し、入力したパターンPに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、入力した公開鍵PKに含まれるH鍵値群から前記識別階層に対応付けられた鍵値Hを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値C0の復号に用いる識別暗号値C3を算出し、算出した平文暗号値C0とワイルドカード暗号値C1と識別暗号値C3とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Wを含む暗号文データCTを生成し、生成した暗号文データCTを出力する暗号化装置と、前記暗号文データCTと前記ユーザ識別子IDとを入力し、入力した暗号文データCTに含まれるワイルドカード階層値Wに基づいて入力したユーザ識別子IDから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と入力した暗号文データCTに含まれるワイルドカード暗号値C1と識別暗号値C3とを用いて入力した暗号文データCTに含まれる平文暗号値C0を復号し、前記平文暗号値C0を復号して得られる前記平文データMを出力する復号装置とを備えたことを特徴とする暗号システム。前記公開鍵PKは、k個の階層に対応付けられたk個の鍵値H’を含むH’鍵値群を含み、前記暗号化装置は、入力した公開鍵PKに含まれるH’鍵値群から前記ワイルドカード階層に対応付けられた鍵値H’を第2のワイルドカード鍵値として抽出し、抽出した第2のワイルドカード鍵値を用いて前記平文暗号値C0の復号に用いるワイルドカード暗号値C1’を算出し、入力した公開鍵PKに含まれるH’鍵値群から前記識別階層に対応付けられた鍵値H’を第2の識別鍵値として抽出し、抽出した第2の識別鍵値を用いて前記平文暗号値C0の復号に用いる識別暗号値C3’を算出し、算出したワイルドカード暗号値C1’と識別暗号値C3’とを含めて前記暗号文データCTを出力し、前記復号装置は、抽出したワイルドカード識別子と入力した暗号文データCTに含まれるワイルドカード暗号値C1と識別暗号値C3とワイルドカード暗号値C1’と識別暗号値C3’とを用いて入力した暗号文データCTに含まれる平文暗号値C0を復号することを特徴とする請求項1記載の暗号システム。前記暗号化装置は、さらに、特定の平文データMWを暗号化して平文暗号値CW0を算出し、前記暗号文データCTの検索に用いるキーワードKWを入力し、前記パターンPを含むと共に前記キーワードKWを第K1階層を識別する階層識別子として含むパターンPWを用いてワイルドカード暗号値CW1と識別暗号値CW3とを算出し、算出した平文暗号値CW0とワイルドカード暗号値CW1と識別暗号値CW3とを含んだ暗号文データCTWを前記暗号文データCTに対応付けて出力し、前記暗号システムは、さらに、前記ユーザ識別子IDと前記キーワードKWとを入力し、入力したユーザ識別子IDとキーワードKWとを用いて前記平文暗号値CW0の復号に用いる鍵値y0を算出し、算出した鍵値y0と前記ユーザ識別子IDとを含んだ検索クエリQKを生成し、生成した検索クエリQKを出力する検索クエリ生成装置と、複数の暗号文データCTと複数の暗号文データCTWとを対応付けて記憶する暗号文記憶部を有する検索装置とを備え、前記検索装置は、前記検索クエリQKと前記ワイルドカード階層値Wとを入力し、前記暗号文記憶部から暗号文データCTWを選択し、入力したワイルドカード階層値Wに基づいて入力した検索クエリQKに含まれるユーザ識別子IDから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と選択した暗号文データCTWに含まれるワイルドカード暗号値CW1と識別暗号値CW3と入力した検索クエリQKに含まれる鍵値y0とを用いて選択した暗号文データCTWに含まれる平文暗号値CW0を復号し、前記平文暗号値CW0を復号して得られた復号データが前記平文データMWと一致するか否かを判定し、前記復号データが前記平文データMWと一致した場合、選択した暗号文データCTWに対応する暗号文データCTを前記暗号文記憶部から取得し、取得した暗号文データCTを入力した検索クエリQKに対する検索結果として出力することを特徴とする請求項1記載の暗号システム。前記暗号化装置は、前記暗号文データCTのハッシュ値を前記平文データMWとして算出し、算出した平文データMWを暗号化して前記平文暗号値CW0を算出し、前記検索装置は、選択した暗号文データCTWに対応する暗号文データCTのハッシュ値を前記平文データMWとして算出し、前記復号データが算出した平文データMWと一致するか否かを判定することを特徴とする請求項3記載の暗号システム。前記暗号化装置は、前記平文データMWとして所定の検索定数を予め記憶し、予め記憶した検索定数を暗号化して前記平文暗号値CW0を算出し、前記検索装置は、前記平文データMWとして前記検索定数を予め記憶し、前記復号データが前記検索定数と一致するか否かを判定することを特徴とする請求項3記載の暗号システム。前記検索装置は、検索する権限が無いユーザのユーザ識別子IDを非検索識別子として記憶する非検索識別子記憶部を備え、前記検索装置は、入力した検索クエリQKに含まれるユーザ識別子IDと前記非検索識別子記憶部に記憶された非検索識別子とが一致するか否かを判定し、前記ユーザ識別子IDと前記非検索識別子とが一致する場合に前記検索結果を出力しないことを特徴とする請求項3記載の暗号システム。前記検索装置は、検索する権限が無いユーザが属する階層より上位の階層の階層識別子を非検索識別子として記憶する非検索識別子記憶部を備え、前記検索装置は、入力した検索クエリQKに含まれるユーザ識別子IDに前記非検索識別子記憶部に記憶された非検索識別子が含まれるか否かを判定し、前記ユーザ識別子IDに前記非検索識別子が含まれる場合に前記検索結果を出力しないことを特徴とする請求項3記載の暗号システム。前記ユーザ識別子IDは、前記特定のユーザの第1のユーザ識別子を第k階層を識別する階層識別子として含むと共に前記特定のユーザの第2のユーザ識別子を第k1階層を識別する階層識別子として含み、前記公開鍵PKに含まれるH鍵値群は、k1個の階層に対応付けられたk1個の鍵値Hを含み、前記パターンPは、第k階層と第k1階層との少なくともいずれかの階層のパターン値としてワイルドカード値を含むことを特徴とする請求項3記載の暗号システム。階層構造を有する組織内で第k階層kは2以上の特定の整数に属する特定ユーザのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDを用いる暗号システムの暗号処理方法において、暗号化装置が、暗号化する平文データMを入力し、入力した平文データMを暗号化して平文暗号値C0を算出し、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンPを入力し、入力したパターンPに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、k個の階層に対応付けられたk個の鍵値Hを含むH鍵値群を含んだ公開鍵PKを入力し、入力した公開鍵PKに含まれるH鍵値群から前記ワイルドカード階層に対応付けられた鍵値Hをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値C0の復号に用いるワイルドカード暗号値C1を算出し、入力したパターンPに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、入力した公開鍵PKに含まれるH鍵値群から前記識別階層に対応付けられた鍵値Hを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値C0の復号に用いる識別暗号値C3を算出し、算出した平文暗号値C0とワイルドカード暗号値C1と識別暗号値C3とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Wを含む暗号文データCTを出力し、復号化装置が、前記暗号文データCTと前記ユーザ識別子IDとを入力し、入力した暗号文データCTに含まれるワイルドカード階層値Wに基づいて入力したユーザ識別子IDから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と入力した暗号文データCTに含まれるワイルドカード暗号値C1と識別暗号値C3とを用いて入力した暗号文データCTに含まれる平文暗号値C0を復号し、前記平文暗号値C0を復号して得られる前記平文データMを出力することを特徴とする暗号システムの暗号処理方法。前記暗号化装置は、さらに、特定の平文データMWを暗号化して平文暗号値CW0を算出し、前記暗号文データCTの検索に用いるキーワードKWを入力し、前記パターンPを含むと共に前記キーワードKWを第K1階層を識別する階層識別子として含むパターンPWを用いてワイルドカード暗号値CW1と識別暗号値CW3とを算出し、算出した平文暗号値CW0とワイルドカード暗号値CW1と識別暗号値CW3とを含んだ暗号文データCTWを前記暗号文データCTに対応付けて出力し、検索クエリ生成装置が、前記ユーザ識別子IDと前記キーワードKWとを入力し、入力したユーザ識別子IDとキーワードKWとを用いて前記平文暗号値CW0の復号に用いる鍵値y0を算出し、算出した鍵値y0と前記ユーザ識別子IDとを含んだ検索クエリQKを出力し、検索装置が、複数の暗号文データCTと複数の暗号文データCTWとを対応付けて記憶する暗号文記憶部を有し、前記検索装置は、前記検索クエリQKと前記ワイルドカード階層値Wとを入力し、前記暗号文記憶部から暗号文データCTWを選択し、入力したワイルドカード階層値Wに基づいて入力した検索クエリQKに含まれるユーザ識別子IDから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と選択した暗号文データCTWに含まれるワイルドカード暗号値CW1と識別暗号値CW3と入力した検索クエリQKに含まれる鍵値y0とを用いて選択した暗号文データCTWに含まれる平文暗号値CW0を復号し、前記平文暗号値CW0を復号して得られた復号データが前記平文データMWと一致するか否かを判定し、前記復号データが前記平文データMWと一致した場合、選択した暗号文データCTWに対応する暗号文データCTを前記暗号文記憶部から取得し、取得した暗号文データCTを入力した検索クエリQKに対する検索結果として出力することを特徴とする請求項9記載の暗号システムの暗号処理方法。暗号化する平文データMを入力し、k個kは2以上の特定の整数の階層に対応付けられたk個の鍵値Hを含むH鍵値群を含んだ公開鍵PKを入力し、階層を識別する階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンPを入力する暗号化入力部と、前記暗号化入力部が入力した平文データMを暗号化して平文暗号値C0を算出し、前記暗号化入力部が入力したパターンPに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、前記暗号化入力部が入力した公開鍵PKに含まれるH鍵値群から前記ワイルドカード階層に対応付けられた鍵値Hをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値C0の復号に用いるワイルドカード暗号値C1を算出し、前記パターンPに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、前記公開鍵PKに含まれるH鍵値群から前記識別階層に対応付けられた鍵値Hを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値C0の復号に用いる識別暗号値C3を算出する暗号値算出部と、前記暗号値算出部により算出された平文暗号値C0とワイルドカード暗号値C1と識別暗号値C3とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Wを含む暗号文データCTを生成し、生成した暗号文データCTを出力する暗号文出力部とを備えたことを特徴とする暗号化装置。暗号化する平文データMを入力し、k個kは2以上の特定の整数の階層に対応付けられたk個の鍵値Hを含むH鍵値群を含んだ公開鍵PKを入力し、階層を識別する階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンPを入力する暗号化入力処理と、前記暗号化入力処理により入力された平文データMを暗号化して平文暗号値C0を算出し、前記暗号化入力処理により入力されたパターンPに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、前記暗号化入力処理により入力された公開鍵PKに含まれるH鍵値群から前記ワイルドカード階層に対応付けられた鍵値Hをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値C0の復号に用いるワイルドカード暗号値C1を算出し、前記パターンPに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、前記公開鍵PKに含まれるH鍵値群から前記識別階層に対応付けられた鍵値Hを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値C0の復号に用いる識別暗号値C3を算出する暗号値算出処理と、前記暗号値算出処理により算出された平文暗号値C0とワイルドカード暗号値C1と識別暗号値C3とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Wを含む暗号文データCTを生成し、生成した暗号文データCTを出力する暗号文出力処理とをコンピュータに実行させることを特徴とする暗号化プログラム。階層構造を有する組織内で第k階層kは2以上の特定の整数に属する特定ユーザのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDを用いる復号装置において、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンPを用いて生成された暗号文データCTであって平文データMを暗号化した平文暗号値C0と特定のワイルドカード暗号値C1と特定の識別暗号値C3とを含むと共に前記パターンPに含まれるパターン値がワイルドカード値である階層を示すワイルドカード階層値Wを含む暗号文データCTを入力し、前記ユーザ識別子IDを入力する復号入力部と、前記復号入力部が入力した暗号文データCTに基づいて、前記復号入力部が入力したユーザ識別子IDから前記ワイルドカード階層値Wによって示される階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と前記暗号文データCTに含まれるワイルドカード暗号値C1と識別暗号値C3とを用いて前記暗号文データCTに含まれる平文暗号値C0を復号し、前記平文暗号値C0を復号して得られる前記平文データMを出力する復号部とを備えたことを特徴とする復号装置。階層構造を有する組織内で第k階層kは2以上の特定の整数に属する特定ユーザのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDを用いる復号プログラムにおいて、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンPを用いて生成された暗号文データCTであって平文データMを暗号化した平文暗号値C0と特定のワイルドカード暗号値C1と特定の識別暗号値C3とを含むと共に前記パターンPに含まれるパターン値がワイルドカード値である階層を示すワイルドカード階層値Wを含む暗号文データCTを入力し、前記ユーザ識別子IDを入力する復号入力処理と、前記復号入力処理により入力された暗号文データCTに基づいて、前記復号入力処理により入力されたユーザ識別子IDから前記ワイルドカード階層値Wによって示される階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と前記暗号文データCTに含まれるワイルドカード暗号値C1と識別暗号値C3とを用いて前記暗号文データCTに含まれる平文暗号値C0を復号し、前記平文暗号値C0を復号して得られる前記平文データMを出力する復号処理とをコンピュータに実行させることを特徴とする復号プログラム。L個Lは2以上の特定の整数の階層を有する組織に属するユーザの公開鍵PKを生成するセットアップ装置において、素数pと素数qとの積nを位数とする巡回群Gであってn個の要素値を含む巡回群Gを算出し、算出した巡回群Gの一部を構成する部分群Gpであって素数pを位数とする部分群GpからL個の要素値をL個の階層に対応付けてL個の鍵値hとして選択し、前記部分群GpからL個の要素値をL個の階層に対応付けてL個の鍵値h’として選択し、算出した巡回群Gの一部を構成する部分群Gqであって素数qを位数とする部分群GqからL個の要素値をL個の階層に対応付けてL個の鍵値Rとして選択し、前記部分群GqからL個の要素値をL個の階層に対応付けてL個の鍵値R’として選択する要素値選択部と、前記要素値選択部により選択されたL個の鍵値hとL個の鍵値Rとを階層毎に乗算してL個の階層に対応付けられたL個の鍵値HをH鍵値群として算出し、前記要素値選択部により選択されたL個の鍵値h’とL個の鍵値R’とを階層毎に乗算してL個の階層に対応付けられたL個の鍵値H’をH’鍵値群として算出する公開鍵値算出部と、前記公開鍵値算出部により算出されたH鍵値群とH’鍵値群とを含んだ公開鍵PKを生成する公開鍵生成部とを備えたことを特徴とするセットアップ装置。L個Lは2以上の特定の整数の階層を有する組織に属するユーザの公開鍵PKを生成するセットアッププログラムにおいて、素数pと素数qとの積nを位数とする巡回群Gであってn個の要素値を含む巡回群Gを算出し、算出した巡回群Gの一部を構成する部分群Gpであって素数pを位数とする部分群GpからL個の要素値をL個の階層に対応付けてL個の鍵値hとして選択し、前記部分群GpからL個の要素値をL個の階層に対応付けてL個の鍵値h’として選択し、算出した巡回群Gの一部を構成する部分群Gqであって素数qを位数とする部分群GqからL個の要素値をL個の階層に対応付けてL個の鍵値Rとして選択し、前記部分群GqからL個の要素値をL個の階層に対応付けてL個の鍵値R’として選択する要素値選択処理と、前記要素値選択処理により選択されたL個の鍵値hとL個の鍵値Rとを階層毎に乗算してL個の階層に対応付けられたL個の鍵値HをH鍵値群として算出し、前記要素値選択処理により選択されたL個の鍵値h’とL個の鍵値R’とを階層毎に乗算してL個の階層に対応付けられたL個の鍵値H’をH’鍵値群として算出する公開鍵値算出処理と、前記公開鍵値算出処理により算出されたH鍵値群とH’鍵値群とを含んだ公開鍵PKを生成する公開鍵生成処理とをコンピュータに実行させることを特徴とするセットアッププログラム。階層構造を有する組織内で第k階層kは2以上の特定の整数に属する特定ユーザのユーザ秘密鍵SKを生成する鍵生成装置において、前記特定ユーザのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDを入力し、k個の階層に対応付けられたk個の鍵値hを含むh鍵値群とk個の階層に対応付けられたk個の鍵値h’を含むh’鍵値群とを含むマスタ秘密鍵MSKを入力する鍵生成入力部と、前記鍵生成入力部が入力したユーザ識別子IDとマスタ秘密鍵MSKとを用いて暗号文データCTの復号に用いる鍵値a0を算出するユーザ秘密鍵値算出部と、前記ユーザ秘密鍵値算出部により算出された鍵値a0を含んだユーザ秘密鍵SKを生成し、生成したユーザ秘密鍵SKを出力するユーザ秘密鍵生成部とを備えたことを特徴とする鍵生成装置。階層構造を有する組織内で第k階層kは2以上の特定の整数に属する特定ユーザのユーザ秘密鍵SKを生成する鍵生成プログラムにおいて、前記特定ユーザのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDを入力し、k個の階層に対応付けられたk個の鍵値hを含むh鍵値群とk個の階層に対応付けられたk個の鍵値h’を含むh’鍵値群とを含んだマスタ秘密鍵MSKを入力する鍵生成入力処理と、前記鍵生成入力処理により入力されたユーザ識別子IDとマスタ秘密鍵MSKとを用いて暗号文データCTの復号に用いる鍵値a0を算出するユーザ秘密鍵値算出処理と、前記ユーザ秘密鍵値算出処理により算出された鍵値a0を含んだユーザ秘密鍵SKを生成し、生成したユーザ秘密鍵SKを出力するユーザ秘密鍵生成処理とをコンピュータに実行させることを特徴とする鍵生成プログラム。階層構造を有する組織内で第k階層kは2以上の特定の整数に属するユーザjのユーザ秘密鍵SKjを生成する鍵委譲装置において、前記ユーザjのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDjを入力し、第k-1階層に属するユーザiのユーザ秘密鍵SKiであって暗号文データCTの復号に用いる鍵値a0を含んだユーザ秘密鍵SKiを入力する鍵委譲入力部と、前記鍵委譲入力部が入力したユーザ識別子IDjとユーザ秘密鍵SKiとを用いて前記暗号文データCTの復号に用いる鍵値x0を算出する委譲鍵値算出部と、前記委譲鍵値算出部により算出された鍵値x0を含んだユーザ秘密鍵SKjを生成し、生成したユーザ秘密鍵SKjを出力する委譲鍵生成部とを備えたことを特徴とする鍵委譲装置。階層構造を有する組織内で第k階層kは2以上の特定の整数に属するユーザjのユーザ秘密鍵SKjを生成する鍵委譲プログラムにおいて、前記ユーザjのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDjを入力し、第k-1階層に属するユーザiのユーザ秘密鍵SKiであって暗号文データCTの復号に用いる鍵値a0を含んだユーザ秘密鍵SKiを入力する鍵委譲入力処理と、前記鍵委譲入力処理により入力されたユーザ識別子IDjとユーザ秘密鍵SKiとを用いて前記暗号文データCTの復号に用いる鍵値x0を算出する委譲鍵値算出処理と、前記委譲鍵値算出処理により算出された鍵値x0を含んだユーザ秘密鍵SKjを生成し、生成したユーザ秘密鍵SKjを出力する委譲鍵生成処理とをコンピュータに実行させることを特徴とする鍵委譲プログラム。非特許文献2に記載のワイルドカード対応の匿名性階層型IDベース暗号方式は、復号演算で最も時間がかかるペアリング演算の回数が階層の高さに比例してしまうため、大企業や官公庁のように大きな階層を持つ組織では利用しづらい。ペアリング演算の回数が階層の高さに比例してしまうのは、階層の高さに比例した個数の要素が暗号文の構成要素として含まれており、復号時にその各々をペアリング演算しなければならないためである。また、非特許文献2に記載のワイルドカード対応の匿名性階層型IDベース暗号方式では、暗号化やユーザ秘密鍵の作成において対象となるユーザのユーザIDユーザ識別子を指定する際に、上位階層から順に漏れ無く要素を指定する必要がある。そのため、部課係などの階層を備える大規模な組織において、部直属のユーザのように、通常の階層構造から外れるユーザに対応することが出来なかった。つまり、対応可能な階層構造に制約があり、柔軟性が低いという課題があった。また、非特許文献2に記載のグループ共有型公開鍵秘匿検索方式は、ワイルドカード対応の匿名性階層型IDベース暗号方式と同様に、検索演算におけるペアリング演算の回数が階層数の高さに比例してしまうため、大企業や官公庁のように大きな階層を持つ組織では利用しづらい。また、非特許文献2にはワイルドカード対応の匿名性階層型IDベース暗号方式を用いてグループ共有型公開鍵秘匿検索方式を実現する方法は開示されていたが、グループ共有型公開鍵秘匿検索方式を実現するためのより一般的な方法は開示されていない。そのため、グループ共有型公開鍵秘匿検索方式を構成する際の選択肢が少ないという課題があった。また、非特許文献2にはグループ共有型公開鍵秘匿検索方式においてグループ内で暗号文を共有し、グループにメンバを加入させる方法が開示されているが、グループからメンバを脱退させる方法は開示されていない。また、加入脱退にかかわらずメンバ自体を失効させるための方法も開示されていない。そのため、異動や出向、あるいは退職があるような組織では利用しづらいという課題があった。本発明は、例えば、以下のようなことを目的とする。ワイルドカード対応の匿名性階層型IDベース暗号方式において、復号演算中のペアリング演算の回数が階層数に比例せず一定回数となるような方式を提供することを目的とする。また、グループ共有型公開鍵秘匿検索方式において、検索演算の中のペアリング演算の回数が階層数に比例せず一定回数となるような方式を提供することを目的とする。また、グループ共有型公開鍵秘匿検索方式を実現するためのより一般的な方法を提供することを目的とする。また、グループ共有型公開鍵秘匿検索方式において、グループからメンバを脱退する方法を提供することを目的とする。また、グループ共有型公開鍵秘匿検索方式においてメンバを失効させる方法を提供することを目的とする。本発明の暗号システムは、階層構造を有する組織内で第k階層kは2以上の特定の整数に属する特定ユーザのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDを用いる暗号システムである。前記暗号システムは、暗号化装置と復号装置とを備える。前記暗号化装置は、暗号化する平文データMを入力し、k個の階層に対応付けられたk個の鍵値Hを含むH鍵値群を含んだ公開鍵PKを入力し、入力した平文データMを暗号化して平文暗号値C0を算出し、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンPを入力し、入力したパターンPに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、入力した公開鍵PKに含まれるH鍵値群から前記ワイルドカード階層に対応付けられた鍵値Hをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値C0の復号に用いるワイルドカード暗号値C1を算出し、入力したパターンPに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、入力した公開鍵PKに含まれるH鍵値群から前記識別階層に対応付けられた鍵値Hを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値C0の復号に用いる識別暗号値C3を算出し、算出した平文暗号値C0とワイルドカード暗号値C1と識別暗号値C3とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Wを含む暗号文データCTを生成し、生成した暗号文データCTを出力する。前記復号装置は、前記暗号文データCTと前記ユーザ識別子IDとを入力し、入力した暗号文データCTに含まれるワイルドカード階層値Wに基づいて入力したユーザ識別子IDから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と入力した暗号文データCTに含まれるワイルドカード暗号値C1と識別暗号値C3とを用いて入力した暗号文データCTに含まれる平文暗号値C0を復号し、前記平文暗号値C0を復号して得られる前記平文データMを出力する。本発明によれば、例えば、ワイルドカード対応の匿名性階層型IDベース暗号方式において、復号演算中のペアリング演算の回数が階層数に比例せず一定回数になる。実施の形態1.ワイルドカード対応の匿名性階層型IDベース暗号方式の実現方法について説明する。図1は、実施の形態1における階層型IDベース暗号システム100の構成図である。実施の形態1における階層型IDベース暗号システム100の構成について、図1に基づいて説明する。階層型IDベース暗号システム100暗号システムの一例は、セットアップ装置200鍵生成装置の一例と復号装置300鍵委譲装置の一例と暗号化装置400とを備える。セットアップ装置200と復号装置300と暗号化装置400とは、それぞれにネットワークに接続し、互いに通信を行う。階層型IDベース暗号システム100には複数の復号装置300が存在し、セットアップ装置200と複数の復号装置300とはツリー状の階層構造を構成している。図1では、セットアップ装置200が階層構造の根第0階層を構成し、4台の復号装置300A-Dが2つの階層第1、2階層を構成している。復号装置300ABは第1階層を構成し、復号装置300CDは復号装置300Aを上位の復号装置300親装置として第2階層を構成している。但し、復号装置300の台数は2または3台であっても構わないし、5台以上であっても構わない。また、複数の復号装置300は3階層以上の階層を構成しても構わない。セットアップ装置200は、各復号装置300によって共通に使用される公開鍵PK公開鍵データを生成すると共に、第1階層の復号装置300毎にユーザ秘密鍵SKを生成する。セットアップ装置200は、第1階層に限らず第2階層以下の階層の復号装置300を対象にしてユーザ秘密鍵SKを生成しても構わない。暗号化装置400は、暗号化されていないデータ以下、平文データMというを暗号化し、暗号文データCTを生成する。復号装置300は、暗号化装置400によって生成された暗号文データCTを公開鍵PKと自己のユーザ秘密鍵SKとを用いて復号し、平文データMを生成する。また、復号装置300は、自己のユーザ秘密鍵SKを用いて下位の復号装置300子装置毎にユーザ秘密鍵SKを生成する。例えば、復号装置300Aは、自己のユーザ秘密鍵SKIDAを用いて、復号装置300C用のユーザ秘密鍵SKIDCと復号装置300D用のユーザ秘密鍵SKIDDとを生成する。図2は、実施の形態1における階層型IDベース暗号システム100の階層構造の一例を示す図である。階層型IDベース暗号システム100を適用するA社の階層構造について、図2に基づいて説明する。例えば、階層型IDベース暗号システム100は会社組織に適用することができる。ここで、A社には総務部、開発部、広報部などの部が存在し、部には人事課、経理課などの課が存在し、課には採用係、研修係などの係が存在しているものとする。この場合、部を第1階層、課を第2階層、係を第3階層として扱い、社員を第4階層として扱う。但し、社員はいずれかの係に配属されるものとは限らず、部または課に直属で配属されても構わない。図2では、田中さんが総務部の直属の社員である。そして、A社はセットアップ装置200と暗号化装置400とを所有する。また、各部は部長が使用する復号装置300を所有し、各課は課長が使用する復号装置300を所有し、各係は係長が使用する復号装置300を所有する。さらに、各社員は復号装置300を所有する。また、部長、課長、係長および社員それぞれユーザの一例には各自を識別するユーザ識別子IDを割り当てる。さらに、個人ユーザまたは部署階層毎に暗号処理用のデータパターンPを予め定義しておく。図3は、実施の形態1における階層型IDベース暗号システム100のユーザ識別子IDの一例を示す図である。階層型IDベース暗号システム100を適用するA社内のユーザ識別子IDについて、図3に基づいて説明する。ユーザ識別子IDは、階層数と同じ個数の要素識別子を含んだデータである。つまり、A社の階層数は4図2参照であるため、A社で使用するユーザ識別子IDには4つの要素が含まれる。図中において、φは不要な階層対応する情報が無い階層を意味する要素空欄値である。例えば、総務部長のユーザ識別子ID1は総務部、φ、φ、φであり、人事課長のユーザ識別子ID2は総務部、人事課、φ、φである。同様に、採用係長のユーザ識別子ID5は総務部、人事課、採用係、φであり、山田さんのユーザ識別子ID6は総務部、人事課、採用係、山田である。また、総務部直属の社員である田中さんのユーザ識別子ID8は総務部、φ、φ、田中となる。ユーザ識別子IDに含まれる要素は、数字、文字、記号またはそれらの組み合わせたものなど、自由に定めることができる。例えば、識別子総務部は文字列であっても構わないし、総務部に対応付けられた番号整数値であっても構わない。以下、ユーザ識別子IDに含まれる要素を階層識別子という。図4は、実施の形態1における階層型IDベース暗号システム100のパターンPの一例を示す図である。階層型IDベース暗号システム100を適用するA社内のパターンPについて、図4に基づいて説明する。パターンPは、階層数と同じ個数の要素識別子を含んだデータである。つまり、A社の階層数は4図2参照であるため、A社で使用するパターンPには4つの要素が含まれる。図中において、は当該部署または階層に属する任意の個人全てのユーザを意味する要素ワイルドカード値である。例えば、山田さん用のパターンP1は総務部、人事課、採用係、山田であり、人事課長用のパターンP4は総務部、人事課、φ、φであり、総務部直属の田中さん用のパターンP8は総務部、φ、φ、田中である。このように、個人用のパターンPはユーザ識別子IDと同一である図3参照。また、採用係に属する社員用のパターンP2は総務部、人事課、採用係、であり、総務部に属する課長用のパターンP5は総務部、、φ、φである。さらに、部長または課長用のパターンP6は、、φ、φであり、部長、課長、係長または社員用のパターンP7は、、、である。このように、個人用ではなく部署または階層用のパターンPにはが含まれる。以下、パターンPに含まれる要素をパターン値という。次に、階層型IDベース暗号システム100を構成する各装置図1参照について説明する。図5は、実施の形態1におけるセットアップ装置200の概要図である。実施の形態1におけるセットアップ装置200の概要について、図5に基づいて説明する。セットアップ装置200は、セットアップ処理部210と鍵生成処理部220とセットアップ記憶部290鍵生成記憶部の一例とを備える。セットアップ処理部210は、セキュリティパラメータλと階層数Lとを入力し、公開鍵PKとマスタ秘密鍵MSKとを生成し、生成した公開鍵PKとマスタ秘密鍵MSKとを出力する。鍵生成処理部220は、公開鍵PKとマスタ秘密鍵MSKとユーザiのユーザ識別子IDiとを入力し、ユーザiのユーザ秘密鍵SKIDiを生成し、生成したユーザiのユーザ秘密鍵SKIDiを出力する。セットアップ記憶部290は、セットアップ装置200で使用するデータを記憶する記憶部である。例えば、セキュリティパラメータλ、階層数L、公開鍵PK、マスタ秘密鍵MSK、ユーザ識別子IDi、ユーザ秘密鍵SKIDiは、セットアップ記憶部290に記憶されるデータの一例である。図6は、実施の形態1におけるセットアップ装置200の機能構成図である。実施の形態1におけるセットアップ装置200の機能構成について、図6に基づいて説明する。セットアップ装置200鍵生成装置の一例は、前述の通り、セットアップ処理部210と鍵生成処理部220とセットアップ記憶部290鍵生成記憶部の一例とを備える。セットアップ処理部210は、例えば、L個Lは2以上の特定の整数の階層を有する組織に属するユーザの公開鍵PKを生成する。セットアップ処理部210は、セットアップ入力部211、セットアップ前処理部212、公開鍵値算出部213、公開鍵生成部214、マスタ秘密鍵生成部215およびセットアップ出力部216を備える。セットアップ入力部211は、セットアップ入力処理を行う。例えば、セットアップ入力部211は、セキュリティパラメータλと階層数Lとを入力する。セットアップ前処理部212要素値選択部の一例は、セットアップ前処理要素値選択処理を含むを行う。例えば、セットアップ前処理部212は、セットアップ前処理において以下の処理を行う。セットアップ前処理部212は、セキュリティパラメータλに基づいて素数pと素数qとの積nを位数とする巡回群Gであってn個の要素値を含む巡回群Gを算出する。セットアップ前処理部212は、算出した巡回群Gの一部を構成する部分群Gpであって素数pを位数とする部分群GpからL個の要素値をL個の階層に対応付けてL個の鍵値hとして選択する。セットアップ前処理部212は、前記部分群GpからL個の要素値をL個の階層に対応付けてL個の鍵値h’として選択する。セットアップ前処理部212は、算出した巡回群Gの一部を構成する部分群Gqであって素数qを位数とする部分群GqからL個の要素値をL個の階層に対応付けてL個の鍵値Rとして選択する。セットアップ前処理部212は、前記部分群GqからL個の要素値をL個の階層に対応付けてL個の鍵値R’として選択する。公開鍵値算出部213は、公開鍵値算出処理を行う。例えば、公開鍵値算出部213は、公開鍵値算出処理において以下の処理を行う。公開鍵値算出部213は、セットアップ前処理部212により選択されたL個の鍵値hとL個の鍵値Rとを階層毎に乗算してL個の階層に対応付けられたL個の鍵値HをH鍵値群として算出する。公開鍵値算出部213は、セットアップ前処理部212により選択されたL個の鍵値h’とL個の鍵値R’とを階層毎に乗算してL個の階層に対応付けられたL個の鍵値H’をH’鍵値群として算出する。公開鍵生成部214は、公開鍵生成処理を行う。例えば、公開鍵生成部214は、公開鍵生成処理において以下の処理を行う。公開鍵生成部214は、公開鍵値算出部213により算出されたH鍵値群とH’鍵値群とを含んだ公開鍵PKを生成する。マスタ秘密鍵生成部215は、マスタ秘密鍵生成処理を行う。例えば、マスタ秘密鍵生成部215は、マスタ秘密鍵生成処理において以下の処理を行う。マスタ秘密鍵生成部215は、セットアップ前処理部212により選択されたL個の鍵値hをh鍵値群として含んだマスタ秘密鍵MSKを生成する。セットアップ出力部216は、セットアップ出力処理を行う。例えば、セットアップ出力部216は、公開鍵生成部214により生成された公開鍵PKとマスタ秘密鍵生成部215により生成されたマスタ秘密鍵MSKとを出力する。鍵生成処理部220は、例えば、階層構造を有する組織内で第k階層kは2以上の特定の整数に属する特定ユーザのユーザ秘密鍵SKを生成する。鍵生成処理部220は、鍵生成入力部221、鍵生成前処理部222、ユーザ秘密鍵値算出部223およびユーザ秘密鍵生成部224を備える。鍵生成入力部221は、鍵生成入力処理を行う。例えば、鍵生成入力部221は、鍵生成入力処理において以下の処理を行う。鍵生成入力部221は、特定ユーザのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDを入力する。鍵生成入力部221は、k個の階層に対応付けられたk個の鍵値hを含むh鍵値群とk個の階層に対応付けられたk個の鍵値h’を含むh’鍵値群とを含むマスタ秘密鍵MSKを入力する。鍵生成前処理部222は、鍵生成前処理を行う。例えば、鍵生成前処理部222は、ユーザ識別子IDに含まれる階層識別子が文字列である場合、階層識別子を文字列から整数値に変換する。ユーザ秘密鍵値算出部223は、ユーザ秘密鍵値算出処理を行う。例えば、ユーザ秘密鍵値算出部223は、ユーザ秘密鍵値算出処理において以下の処理を行う。ユーザ秘密鍵値算出部223は、鍵生成入力部221が入力したユーザ識別子IDとマスタ秘密鍵MSKとを用いて、暗号文データCTの復号に用いる鍵値a0を算出する。ユーザ秘密鍵生成部224は、ユーザ秘密鍵生成処理を行う。例えば、ユーザ秘密鍵生成部224は、ユーザ秘密鍵生成処理において以下の処理を行う。ユーザ秘密鍵生成部224は、ユーザ秘密鍵値算出部223により算出された鍵値a0を含んだユーザ秘密鍵SKを生成し、生成したユーザ秘密鍵SKを出力する。図7は、実施の形態1における復号装置300の概要図である。実施の形態1における復号装置300の概要について、図7に基づいて説明する。復号装置300は、復号処理部310と鍵委譲処理部320と復号記憶部390鍵委譲記憶部の一例とを備える。但し、最下層の復号装置300例えば、社員用の復号装置300には鍵委譲処理部320を備えなくても構わない。復号処理部310は、公開鍵PKとユーザiのユーザ秘密鍵SKIDiとユーザi用に生成された暗号文データCTとユーザiのユーザ識別子IDiとを入力し、暗号文データCTを復号して平文データMを生成し、生成した平文データMを出力する。鍵委譲処理部320は、公開鍵PKとユーザiのユーザ秘密鍵SKIDiとユーザiの一つ下の階層に属するユーザjのユーザ識別子IDjとを入力し、ユーザjの秘密鍵SKIDjを生成し、生成したユーザjの秘密鍵SKIDjを出力する。復号記憶部390は、復号装置300で使用するデータを記憶する記憶部である。例えば、公開鍵PK、ユーザ秘密鍵SKIDx、暗号文データCT、ユーザ識別子IDx、平文データMは、復号記憶部390に記憶されるデータの一例である。図8は、実施の形態1における復号装置300の機能構成図である。実施の形態1における復号装置300の機能構成について、図8に基づいて説明する。復号装置300鍵委譲装置の一例は、前述の通り、復号処理部310と鍵委譲処理部320と復号記憶部390鍵委譲記憶部の一例とを備える。復号処理部310は、復号入力部311、復号前処理部312および復号部313を備える。復号入力部311は、復号入力処理を行う。例えば、復号入力部311は、復号入力処理において以下の処理を行う。復号入力部311は、暗号文データCTとユーザ識別子IDとを入力する。暗号文CTは、平文データMを暗号化した平文暗号値C0と特定のワイルドカード暗号値C1と特定の識別暗号値C3とワイルドカード階層値Wとを含む。ワイルドカード階層値Wは、パターンPに含まれるパターン値がワイルドカード値である階層を示す。復号前処理部312は、復号前処理を行う。例えば、復号前処理部312は、ユーザ識別子IDに含まれる階層識別子が文字列である場合、階層識別子を文字列から整数値に変換する。復号部313は、復号処理を行う。例えば、復号部313は、復号処理において以下の処理を行う。復号部313は、復号入力部311が入力した暗号文データCTに基づいて、復号部313が入力したユーザ識別子IDから前記ワイルドカード階層値Wによって示される階層の階層識別子をワイルドカード識別子として抽出する。復号部313は、抽出したワイルドカード識別子と前記暗号文データCTに含まれるワイルドカード暗号値C1と識別暗号値C3とを用いて、前記暗号文データCTに含まれる平文暗号値C0を復号する。復号部313は、前記平文暗号値C0を復号して得られる前記平文データMを出力する。鍵委譲処理部320は、階層構造を有する組織内で第k階層kは2以上の特定の整数に属するユーザjのユーザ秘密鍵SKjを生成する。鍵委譲処理部320は、鍵委譲入力部321、鍵委譲前処理部322、委譲鍵値算出部323および委譲鍵生成部324を備える。鍵委譲入力部321は、鍵委譲入力処理を行う。例えば、鍵委譲入力部321は、鍵委譲入力処理において以下の処理を行う。鍵委譲入力部321は、ユーザjのユーザ識別子を第k階層を識別する階層識別子として含むと共に第1階層から第k-1階層までの階層を識別するk-1個の階層識別子を含むユーザ識別子IDjを入力する。鍵委譲入力部321は、第k-1階層に属するユーザiのユーザ秘密鍵SKiであって暗号文データCTの復号に用いる鍵値a0を含んだユーザ秘密鍵SKiを入力する。鍵委譲前処理部322は、鍵委譲前処理を行う。例えば、鍵委譲前処理部322は、ユーザ識別子IDに含まれる階層識別子が文字列である場合、階層識別子を文字列から整数値に変換する。委譲鍵値算出部323は、委譲鍵値算出処理を行う。例えば、委譲鍵値算出部323は、委譲鍵値算出処理において以下の処理を行う。委譲鍵値算出部323は、鍵委譲入力部321が入力したユーザ識別子IDjとユーザ秘密鍵SKiとを用いて、前記暗号文データCTの復号に用いる鍵値x0を算出する。委譲鍵生成部324は、委譲鍵生成処理を行う。例えば、委譲鍵生成部324は、委譲鍵生成処理において以下の処理を行う。委譲鍵生成部324は、委譲鍵値算出部323により算出された鍵値x0を含んだユーザ秘密鍵SKjを生成し、生成したユーザ秘密鍵SKjを出力する。図9は、実施の形態1における暗号化装置400の概要図である。実施の形態1における暗号化装置400の概要について、図9に基づいて説明する。暗号化装置400は、暗号処理部410と暗号化記憶部490とを備える。暗号処理部410は、公開鍵PKと個人または階層i用のパターンPiと平文データMとを入力し、平文データMを暗号化して個人または階層i用の暗号文データCTを生成し、生成した暗号文データCTを出力する。暗号化記憶部490は、暗号化装置400で使用するデータを記憶する記憶部である。例えば、公開鍵PK、パターンPi、平文データM、暗号文データCTは、暗号化記憶部490に記憶されるデータの一例である。図10は、実施の形態1における暗号化装置400の機能構成図である。実施の形態1における暗号化装置400の機能構成について、図10に基づいて説明する。暗号化装置400は、前述の通り、暗号処理部410と暗号化記憶部490とを備える。暗号処理部410は、暗号化入力部411、暗号化前処理部412、暗号値算出部413および暗号文生成部414を備える。暗号化入力部411は、暗号化入力処理を行う。例えば、暗号化入力部411は、暗号化入力処理において以下の処理を行う。暗号化入力部411は、暗号化する平文データMを入力する。暗号化入力部411は、k個kは2以上の特定の整数の階層に対応付けられたk個の鍵値Hを含むH鍵値群を含んだ公開鍵PKを入力する。暗号化入力部411は、階層を識別する階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンPを入力する。暗号化前処理部412は、暗号化前処理を行う。例えば、暗号化前処理部412は、パターンPに含まれるパターン値例えば、階層識別子が文字列である場合、パターン値を文字列から整数値に変換する。暗号値算出部413は、暗号値算出処理を行う。例えば、暗号値算出部413は、暗号値算出処理において以下の処理を行う。暗号値算出部413は、暗号化入力部411が入力した平文データMを暗号化して平文暗号値C0を算出する。暗号値算出部413は、暗号化入力部411が入力したパターンPに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定する。暗号値算出部413は、暗号化入力部411が入力した公開鍵PKに含まれるH鍵値群から前記ワイルドカード階層に対応付けられた鍵値Hをワイルドカード鍵値として抽出する。暗号値算出部413は、抽出したワイルドカード鍵値を用いて前記平文暗号値C0の復号に用いるワイルドカード暗号値C1を算出する。暗号値算出部413は、前記パターンPに基づいて前記パターン値が階層識別子である階層を識別階層として判定する。暗号値算出部413は、前記公開鍵PKに含まれるH鍵値群から前記識別階層に対応付けられた鍵値Hを識別鍵値として抽出する。暗号値算出部413は、抽出した識別鍵値を用いて前記平文暗号値C0の復号に用いる識別暗号値C3を算出する。暗号文生成部414は、暗号文生成処理を行う。例えば、暗号文生成部414は、暗号文生成処理において以下の処理を行う。暗号文生成部414は、暗号値算出部413により算出された平文暗号値C0とワイルドカード暗号値C1と識別暗号値C3とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Wを含む暗号文データCTを生成する。暗号文生成部414は、生成した暗号文データCTを出力する。次に、階層型IDベース暗号システム100を構成する各装置図1参照の処理方法について説明する。図11は、実施の形態1におけるセットアップ装置200によるセットアップ方法を示すフローチャートである。セットアップ装置200のセットアップ処理部210が実行するセットアップ方法の処理の流れについて、図11に基づいて説明する。S110において、セットアップ入力部211は、セキュリティパラメータλと階層数Lと入力装置またはセットアップ記憶部290から入力する。S110の後、S120に進む。S120において、セットアップ前処理部212は、セキュリティパラメータλに基づいて素数p、qを生成算出し、生成した素数p、qを乗算して合成数n=pqを算出する。セットアップ前処理部212は、算出した合成数nと所定の写像eと、S110で入力されたセキュリティパラメータλと階層数Lとに基づいて群G、GTを生成する。群G、GTは合成数nを位数とする巡回群であり、n個の要素値を含む。巡回群G、GTは加法群と乗法群とのどちらであっても構わない。以下、巡回群G、GTが乗法群であるものとして説明を続ける。写像eは2つの入力値から1つの出力値を得る関数であり、次の性質abを満たす。性質abを満たす写像eをペアリングという。ペアリングeは以下のように表すことができる。ペアリングeの演算をペアリング演算という。ペアリングeによって定義される群G、GTをペアリング群という。例えば、ペアリング群G、GTとして、楕円曲線上の有理点から成る群Gと有限体上の群GTとが挙げられる。群Gと群GTとのペアリングは対称ペアリングと非対称ペアリングとのどちらであっても構わない。以下、対称ペアリングを対象にして説明を続ける。非対称ペアリングを対象にする場合については、当業者であれば以下の説明から容易に理解し得ることである。素数p、qの生成方法は、例えば、非特許文献4に開示されている。ペアリング群G、GTの生成方法は、例えば、非特許文献3に開示されている。S120の後、S130に進む。S130において、セットアップ前処理部212は、群Gを用いて群Gの一部を構成する部分群Gpを生成する。部分群Gpは素数pを位数としてp個の要素値を含む要素値群である。セットアップ前処理部212は、式[SU1]に示すように、生成した部分群Gpから複数の要素値をランダムに選択する。S130の後、S131に進む。S131において、セットアップ前処理部212は、群Gを用いて群Gの一部を構成する部分群Gqを生成する。部分群Gqは素数qを位数としてq個の要素値を含む要素値群である。セットアップ前処理部212は、式[SU2]に示すように、生成した部分群Gqから複数の要素値をランダムに選択する。S131の後、S140に進む。S140において、公開鍵値算出部213は、S130で選択された複数の要素値とS131で選択された複数の要素値とを用いて複数の公開鍵値を算出する。以下に、複数の公開鍵値を算出する複数の算出式[SU3]を示す。S140の後、S150に進む。S150において、公開鍵生成部214は、S140で算出された複数の公開鍵値を含んだ公開鍵PKを生成する。以下に、公開鍵PKを表す式[SU4]を示す。S150の後、S160に進む。S160において、マスタ秘密鍵生成部215は、S130で選択された複数の要素値をマスタ秘密鍵値として含んだマスタ秘密鍵MSKを生成する。以下に、マスタ秘密鍵MSKを表す式[SU5]を示す。S160の後、S170に進む。S170において、セットアップ出力部216は、S150で生成された公開鍵PKとS160で生成されたマスタ秘密鍵MSKとをセットアップ記憶部290に記憶する。また、セットアップ出力部216は、システム全体で使用できるように公開鍵PKをシステムの共有サーバ図示省略に記憶する。但し、セットアップ出力部216は、公開鍵PKを各復号装置300および暗号化装置400に送信しても構わない。S170により、セットアップ方法の処理は終了する。図12は、実施の形態1におけるセットアップ装置200による鍵生成方法を示すフローチャートである。セットアップ装置200の鍵生成処理部220が実行する鍵生成方法の処理の流れについて、図12に基づいて説明する。S210において、鍵生成入力部221は、セットアップ処理部210により生成された公開鍵PKとマスタ秘密鍵MSKとをセットアップ記憶部290から入力する。鍵生成入力部221は、特定のユーザiに割り当てられたユーザ識別子IDiを入力装置またはセットアップ記憶部290から入力する。S210の後、S220に進む。S220において、鍵生成前処理部222は、ユーザ識別子IDiを構成する要素を整数値群Znに含まれるいずれかの整数値に変換する。整数値群Znは、0からn-1までの整数値で構成される群である。図11のS120で説明したように、nは素数pと素数qとの積であり、群Gの位数である。例えば、鍵生成前処理部222は、要素を表す2進数を10進数の整数値に変換する。鍵生成前処理部222は、得られた10進数の整数値を法nで剰余演算し、剰余値を整数値として求めてもよい。また、鍵生成前処理部222は、ハッシュ関数に要素を代入して整数値を得てもよい。また、要素と整数値とを対応付けた変換テーブルをセットアップ記憶部290に予め記憶しておき、鍵生成前処理部222が要素に対応する整数値をセットアップ記憶部290から取得しても構わない。但し、ユーザ識別子IDiを構成する全ての要素が整数値である場合、S220を実行する必要はない。また、ユーザ識別子IDiを構成する複数の要素のうち整数値で表す要素については、S220を実行しなくても構わない。S220の後、S230に進む。S230において、鍵生成前処理部222は、式[KG1]に示すように、整数値群Zn0からn-1の整数値から複数の整数値をランダムに選択する。但し、条件式[KG1-1]を満たさない場合、鍵生成前処理部222は複数の整数値を選択し直す。S230の後、S240に進む。S240において、鍵生成前処理部222は、ユーザ識別子IDiに含まれる複数の要素のうち空欄値φ以外の要素を判定する。さらに、鍵生成前処理部222は、空欄値φ以外の要素に対応する階層の番号を非空欄階層値Dとして判定する。以下、空欄値φ以外の要素に対応する階層を非空欄階層という。また、鍵生成前処理部222は、ユーザ識別子IDiに含まれる複数の要素のうち空欄値φを示す要素を判定し、空欄値φを示す要素に対応する階層の番号を空欄階層値Nとして判定する。以下、空欄値φを示す要素に対応する階層を空欄階層という。以下に、非空欄階層値Dを表す式[KG2]と空欄階層値Nを表す式[KG3]とを示す。例えば、図3に示した経理課長のユーザ識別子ID3総務部、経理課、φ、φの場合、非空欄階層値Dは1と2であり、空欄階層値Nは3と4である。また、田中さんのユーザ識別子ID8総務部、φ、φ、田中の場合、非空欄階層値Dは1と4であり、空欄階層値Nは2と3である。S240の後、S250に進む。S250において、ユーザ秘密鍵値算出部223は、マスタ秘密鍵MSKとユーザ識別子IDiとユーザ識別子IDiの非空欄階層値DとS230で選択された整数値とを用いて、複数の復号鍵値を算出する。ここで、ユーザiの属する階層の番号をKとする。以下に、複数の復号鍵値を算出する複数の算出式[KG4]を示す。S250の後、S251に進む。S251において、ユーザ秘密鍵値算出部223は、S250と同様に複数の撹乱鍵値Aを算出する。以下に、複数の撹乱鍵値Aを算出する複数の算出式[KG5]を示す。S251の後、S252に進む。S252において、ユーザ秘密鍵値算出部223は、S251と同様に複数の撹乱鍵値Bを算出する。以下に、複数の撹乱鍵値Bを算出する複数の算出式[KG6]を示す。S252の後、S260に進む。S260において、ユーザ秘密鍵生成部224は、S250で算出された複数の復号鍵値を含んだ復号鍵dkを生成する。さらに、ユーザ秘密鍵生成部224は、S251で算出された複数の撹乱鍵値AとS252で算出された複数の撹乱鍵値Bとを含んだ撹乱鍵rkを生成する。以下に、復号鍵dkを表す式[KG7]と撹乱鍵rkを表す式[KG8]とを示す。S260の後、S270に進む。S270において、ユーザ秘密鍵生成部224は、S260で生成した復号鍵dkと撹乱鍵rkとを用いてユーザiのユーザ秘密鍵SKを生成する。そして、ユーザ秘密鍵生成部224は、生成したユーザ秘密鍵SKを出力する。例えば、ユーザ秘密鍵生成部224は、生成したユーザ秘密鍵SKをユーザiの復号装置300へ送信する。以下に、ユーザiのユーザ秘密鍵SKを表す式[KG9]を示す。S270により、鍵生成方法の処理は終了する。ユーザ秘密鍵SKに含まれる復号鍵dkは、復号装置300が暗号文データCTの復号に用いるデータであり、ユーザ秘密鍵SKに含まれる撹乱鍵rkは、復号装置300が鍵委譲に用いるデータである。鍵委譲とは、復号装置300が自己のユーザ秘密鍵SKを用いて下位層に属するユーザのユーザ秘密鍵を生成する処理である。図13は、実施の形態1における復号装置300による鍵委譲方法を示すフローチャートである。復号装置300の鍵委譲処理部320が実行する鍵委譲方法の処理の流れについて、図13に基づいて説明する。S310において、鍵委譲入力部321は、公開鍵PKを入力装置、共有サーバ図示省略または復号記憶部390から入力する。鍵委譲入力部321は、ユーザiのユーザ秘密鍵SKIDiを入力装置または復号記憶部390から入力する。ユーザiは、例えば、この復号装置を使用するユーザである。鍵委譲入力部321は、ユーザjのユーザ識別子IDjを入力装置または復号記憶部390から入力する。ユーザjは、ユーザiの一つ下の階層に属するユーザあってユーザ秘密鍵の委譲先のユーザである。以下、ユーザj委譲先の属する階層の番号をkとし、ユーザiの属する階層の番号をk-1とする。S310の後、S320に進む。S320において、鍵委譲前処理部322は、ユーザ識別子IDjに含まれる要素Ikを整数値群Zn0からn-1の整数値に含まれるいずれかの整数値に変換する。要素Ikは、ユーザ識別子IDjに含まれる複数の要素のうちk番目の要素、つまり、ユーザj委譲先が属する第k階層に対応する要素である。変換方法は、S220図12参照と同様である。S320の後、S330に進む。S330において、鍵委譲前処理部322は、式[KT1]に示すように、整数値群Znから複数の整数値をランダムに選択する。但し、条件式[KT1-1]を満たさない場合、鍵委譲前処理部322は複数の整数値を選択し直す。S330の後、S340に進む。S340において、委譲鍵値算出部323は、ユーザ秘密鍵SKIDiに含まれるユーザiの復号鍵dkIDiとユーザjのユーザ識別子IDjに含まれる要素Ikとを用いて、複数の作業値aを算出する。以下に、複数の作業値aを算出する算出式[KT2]を示す。S340の後、S341に進む。S341において、委譲鍵値算出部323は、ユーザ秘密鍵SKIDiに含まれるユーザiの撹乱鍵rkIDiとユーザjのユーザ識別子IDjに含まれる要素Ikとを用いて、複数の作業値bを算出する。以下に、複数の作業値bを算出する算出式[KT3]を示す。S341の後、S342に進む。S342において、委譲鍵値算出部323は、S341と同様に複数の作業値cを算出する。以下に、複数の作業値cを算出する算出式[KT4]を示す。S342の後、S350に進む。S350において、委譲鍵値算出部323は、S340からS342で算出した作業値a-cとS330で選択された整数値とを用いて、複数の復号鍵値を算出する。以下に、複数の復号鍵値を算出する算出式[KT5]を示す。S350の後、S351に進む。S351において、委譲鍵値算出部323は、S341で算出した作業値bとS342で算出した作業値cとS330で選択された整数値とを用いて、複数の撹乱鍵値Aを算出する。以下に、複数の撹乱鍵値Aを算出する算出式[KT6]を示す。S351の後、S352に進む。S352において、委譲鍵値算出部323は、S351と同様に複数の撹乱鍵値Bを算出する。以下に、複数の撹乱鍵値Bを算出する算出式[KT7]を示す。S352の後、S360に進む。S360において、委譲鍵生成部324は、S350で算出された複数の復号鍵値を用いて、ユーザjの復号鍵dkIDjを生成する。さらに、委譲鍵生成部324は、S351で算出された複数の撹乱鍵値AとS352で算出された複数の撹乱鍵値Bとを用いて、撹乱鍵rkIDjを生成する。以下に、ユーザjの復号鍵dkIDjを表す式[KT8]とユーザjの撹乱鍵rkIDjを表す式[KT9]とを示す。S360の後、S370に進む。S370において、委譲鍵生成部324は、S360で生成した復号鍵dkIDjと撹乱鍵rkIDjとを用いてユーザjのユーザ秘密鍵SKIDjを生成し、生成したユーザ秘密鍵SKIDjを復号記憶部390に記憶する。また、委譲鍵生成部324は、生成したユーザ秘密鍵SKIDjを出力する。例えば、委譲鍵生成部324は、生成したユーザ秘密鍵SKIDjをユーザjの復号装置300へ送信する。以下に、ユーザjのユーザ秘密鍵SKIDjを表す式[KT10]を示す。S370により、鍵委譲方法の処理は終了する。但し、ユーザjの一つ下の階層に属するユーザj2のユーザ秘密鍵SKIDj2を生成する場合には、ユーザiをユーザjに置き換えると共にユーザjをユーザj2に置き換えて鍵委譲方法の処理S310-S370を繰り返す。図12で説明した鍵生成方法と図13で説明した鍵委譲方法とで見掛け上の処理は異なるが、鍵生成方法と鍵委譲方法とは同一ユーザについて同一のユーザ秘密鍵SKを生成することができる。そのため、鍵生成方法と鍵委譲方法とのいずれかを用いて、特定のユーザのユーザ秘密鍵SKを生成すればよい。図14は、実施の形態1における暗号化装置400による暗号化方法を示すフローチャートである。暗号化装置400の暗号処理部410が実行する暗号化方法の処理の流れについて、図14に基づいて説明する。S410において、暗号化入力部411は、公開鍵PKを入力装置、共有サーバ図示省略または復号記憶部390から入力する。暗号化入力部411は、ユーザi用のパターンPiを入力装置、共有サーバまたは復号記憶部390から入力する。ユーザiは、暗号文データCTを復号できる一人のユーザまたは複数のユーザを意味する。暗号化入力部411は、平文データMを入力装置または復号記憶部390から入力する。S410の後、S420に進む。S420において、暗号化前処理部412は、パターンPiに含まれる要素を整数値群Zn0からn-1の整数値に含まれるいずれかの整数値に変換する。変換方法は、S220図12参照と同様である。S420の後、S421に進む。S421において、暗号化前処理部412は、式[EN1]に示すように、整数値群Znから整数値ρをランダムに選択する。S421の後、S422に進む。S422において、暗号化前処理部412は、パターンPiに含まれる複数の要素のうちワイルドカード値を示す要素を判定する。さらに、暗号化前処理部412は、ワイルドカード値を示す要素に対応する階層の番号をワイルドカード階層値Wとして判定する。以下、ワイルドカード値を示す要素に対応する階層をワイルドカード階層という。また、暗号化前処理部412は、パターンPiに含まれる複数の要素のうち空欄値φを示す要素を判定し、空欄値φを示す要素に対応する階層の番号を空欄階層値Nとして判定する。以下、空欄値φを示す要素に対応する階層を空欄階層という。また、暗号化前処理部412は、パターンPiに含まれる複数の要素のうちワイルドカード値および空欄値φ以外の要素を判定し、ワイルドカード値および空欄値φ以外の要素に対応する階層の番号を識別階層値Dとして判定する。以下、ワイルドカード値および空欄値φ以外の要素に対応する階層を識別階層という。以下に、ワイルドカード階層値Wを表す式[EN2]と空欄階層値Nを表す式[EN3]と識別階層値Dを表す式[EN4]とを示す。例えば、図4に示したパターンP5総務部、、φ、φの場合、ワイルドカード階層値Wは2であり、空欄階層値Nは3と4であり、識別階層値Dは1である。また、パターンP8総務部、φ、φ、田中の場合、ワイルドカード階層値Wは無く、空欄階層値Nは2と3であり、識別階層値Dは1と4である。S422の後、S423に進む。S423において、暗号化前処理部412は、ワイルドカード階層値Wに基づいて整数値群Znから複数の整数値をランダムに選択し、選択した整数値毎に整数値を公開鍵PKに含まれる公開鍵値gqにべき乗する。この処理は、式[EN5]に示すように、素数qを位数とする群Gqから複数の要素値をランダムに選択することと等しい。S423の後、S430に進む。S430において、暗号値算出部413は、公開鍵PKとパターンPiと平文データMとS421で選択された整数値ρとS423で算出された複数の整数値とを用いて、複数の暗号値を算出する。以下に、複数の暗号値を算出する複数の算出式[EN6]を示す。S430の後、S440に進む。S440において、暗号文生成部414は、S422で判定されたワイルドカード階層値WとS430で算出された複数の暗号値とを用いてユーザi用の暗号文データCTを生成し、生成した暗号文データCTを暗号化記憶部490に記憶する。以下に、暗号文CTを表す式[EN7]を示す。また、暗号文生成部414は、生成した暗号文データCTを出力する。例えば、暗号文生成部414は、暗号文データCTを共有サーバ図示省略に記憶する。S440により、暗号化方法の処理は終了する。上記の暗号化方法において、平文データMはペアリング群GT図11のS120参照の要素であるものとする。但し、平文データMがペアリング群GTの要素でない場合、ハイブリッド暗号方式を用いればよい。ハイブリッド暗号方式において、平文データMはセッション鍵を用いて共通鍵暗号方式で暗号化する。そして、平文データMをセッション鍵に置き換えて上記暗号化方法の処理を実行する。図15は、実施の形態1における復号装置300による復号方法を示すフローチャートである。復号装置300の復号処理部310が実行する復号方法の処理の流れについて、図15に基づいて説明する。S510において、復号入力部311は、公開鍵PKと暗号文データCTとを入力装置、共有サーバ図示省略または復号記憶部390から入力する。復号入力部311は、ユーザiのユーザ秘密鍵SKIDiとユーザ識別子IDiとを入力装置または復号記憶部390から入力する。ユーザiは、暗号文データCTを復号するユーザであって、この復号装置300を使用するユーザである。S510の後、S520に進む。S520において、復号前処理部312は、ユーザ識別子IDiに含まれる要素を整数値群Zn0からn-1の整数値に含まれるいずれかの整数値に変換する。変換方法は、S220図12参照と同様である。S520の後、S521に進む。S521において、復号前処理部312は、ユーザ識別子IDiに基づいて非空欄階層値Dを判定する。判定方法は、S240図12参照と同様である。S521の後、S530に進む。S530において、復号部313は、暗号文データCTとユーザ識別子IDiとS521で判定した非空欄階層値Dとを用いて、複数の作業値を算出する。以下に、複数の作業値を算出する複数の算出式[DE1]を示す。S530の後、S540に進む。S540において、復号部313は、暗号文データCTとユーザ秘密鍵SKIDiと公開鍵PKに含まれる写像の関数eとS530で算出した複数の作業値とを用いて平文データMを算出する。以下に、平文データMを算出する算出式[DE2]を示す。復号部313は、算出した平文データMを出力する。例えば、復号部313は、平文データMを表示装置に表示する。S540により、復号方法は終了する。階層型IDベース暗号システム100において、平文データMの暗号化に使用されたパターンPに該当する正当なユーザであれば、自分のユーザ秘密鍵SKとユーザ識別子IDとを用いて暗号化データCTを復号することができる。パターンPに含まれる複数の要素pのうちユーザ識別子IDの非空欄階層≠φに対応する要素pjがユーザ識別子IDの要素Ijまたはワイルドカード値であり、復号処理図15のS530でワイルドカード値がユーザ識別子IDの要素Ijで焼き直しされるからである。一方、パターンPに該当するユーザ以外の不正なユーザは、自分のユーザ秘密鍵SKとユーザ識別子IDとを用いて暗号化データCTを復号することができない。復号処理でワイルドカード値が不正なユーザ識別子IDの要素Ijで焼き直しされるからである。以下に、暗号文データCTを復号して得られる平文データMと暗号化する前の平文データMとの関係式を示す。一行目の式は、上記式[DE2]図15のS540参照である。二行目の式は、一行目の右辺を上記式DE1図15のS530参照に基づいて展開した式である。三行目の式は、二行目の式を以下に示すペアリング群の性質1に基づいて展開した式である。四行目の式は、三行目の式の分母を分解した式である。そして、四行目の式の分母と分子とで共通項を消去することにより平文データMが得られる。以下に、ペアリング群の性質1を示す。階層型IDベース暗号システム100は、暗号文の匿名性を確保することができる。なお、ここでいう匿名性とは、非特許文献5のANON-sIDで定義されるような安全性のことをいう。言い換えれば、暗号文からワイルドカード箇所を除く要素pjすなわちユーザ識別子に関する情報が漏洩しないという性質である。また、暗号文の秘匿性を確保することができる。なお、ここでいう秘匿性とは、非特許文献5のIND-sIDで定義されるような安全性のことをいう。言い換えれば、暗号文から平文に関する情報が漏洩しないという性質である。上記の匿名性および秘匿性については、暗号分野で一般的なシミュレーションベースの安全性証明によって示される。その際の数論仮定は、非特許文献5に記載の仮定と同じである。当業者であればその安全性について理解でき、必要であれば安全性証明を再現できるものと考える。本実施の形態では対称ペアリングを用いて構成する方法を説明したが、これを非対称ペアリングを用いる構成に拡張することは、当業者であれば容易に理解し得ることである。本実施の形態によれば、ワイルドカード対応の匿名性階層型IDベース暗号方式を実現することができる。すなわち、階層内のある層に属する全てのユーザに対してユーザ毎に暗号文を生成する必要がなく、1つの暗号文を生成すればよい。これにより、暗号文のサイズ数を低減することができる。さらに、復号演算図15のS540参照において、ペアリングeの演算回数を階層数に比例した回数ではなく、一定回数具体的には3回にすることができる。これは、暗号文の構成要素の中で階層数に比例する要素を除去したためである。これにより、大企業や官公庁のように大きな階層を持つ組織においても高速な復号演算を実現することができる。さらに、中間の階層に対応付けてユーザ識別子に空欄φをおくことができる。これにより、図2に示した田中さんのように通常の階層構造から外れるようなユーザにも柔軟に対応することができる。つまり、特異な階層構造にも柔軟に対応できるという効果がある。実施の形態において、セットアップ装置200は、セットアップ装置セットアップ処理部210と鍵生成装置鍵生成処理部220とに分割しても構わない。また、復号装置300は、復号装置復号処理部310と鍵委譲装置鍵委譲処理部320とに分割しても構わない。図16は、実施の形態における階層型IDベース暗号システム100のハードウェア資源の一例を示す図である。図16において、セットアップ装置200、復号装置300、暗号化装置400および検索装置500実施の形態3参照は、CPU901CentralProcessingUnitを備えている。CPU901は、バス902を介してROM903、RAM904、通信ボード905、ディスプレイ装置911、キーボード912、マウス913、ドライブ装置914、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。ドライブ装置914は、FDFlexibleDiskDrive、CDCompactDisc、DVDDigitalVersatileDiscなどの記憶媒体を読み書きする装置である。通信ボード905は、有線または無線で、LANLocalAreaNetwork、インターネット、電話回線などの通信網に接続している。磁気ディスク装置920には、OS921オペレーティングシステム、プログラム群922、ファイル群923が記憶されている。プログラム群922には、実施の形態において~部として説明する機能を実行するプログラムが含まれる。プログラムは、CPU901により読み出され実行される。すなわち、プログラムは、~部としてコンピュータを機能させるものであり、また~部の手順や方法をコンピュータに実行させるものである。ファイル群923には、実施の形態において説明する~部で使用される各種データ入力、出力、判定結果、計算結果、処理結果などが含まれる。実施の形態において構成図およびフローチャートに含まれている矢印は主としてデータや信号の入出力を示す。実施の形態において~部として説明するものは~回路、~装置、~機器であってもよく、また~ステップ、~手順、~処理であってもよい。すなわち、~部として説明するものは、ファームウェア、ソフトウェア、ハードウェアまたはこれらの組み合わせのいずれで実装されても構わない。実施の形態2.合成数n=pqを位数とするペアリング群を用いる代わりに、素数pを位数とするペアリング群の直積を用いる形態について説明する。以下、実施の形態1と異なる事項について主に説明する。説明を省略する事項については実施の形態1と同様である。以下、合成数を位数とするペアリング群のことを合成数位数のペアリング群といい、素数を位数とするペアリング群のことを素数位数のペアリング群という。素数位数pのペアリング群非対称ペアリング群の直積から成る直積群は、式2-1で定義される。直積群の一部を構成する部分群は式2-2で定義される。ペアリングeは式2-3で定義される。上記の定義において性質2が成り立つ。この性質2は次のように確かめることができる。この性質2は、実施の形態1で説明した性質1と同等の性質である。したがって、素数位数pのペアリング群の直積を用いて、階層型IDベース暗号システム100を構成することができる。つまり、実施の形態1で説明した各群を以下のように上記の各群に置き換えることにより、階層型IDベース暗号システム100を構成することができる。ここでは、素数位数のペアリング群の直積を用いる場合の一例を示した。但し、合成数位数のペアリング群を素数位数のペアリング群に変換する変換方法を用いても構わない。このような変換方法は、例えば、非特許文献6に開示されている。本実施の形態によれば、合成数位数のペアリング群ではなく、素数位数のペアリング群を用いてワイルドカード対応の匿名性階層型IDベース暗号方式を実現することができる。通常、素数位数のペアリング群は合成数位数のペアリング群よりも小さいビットサイズで同等の安全性を実現できる。したがって、暗号文や秘密鍵のサイズを実施の形態1よりも小さくすることができる。また、ビットサイズが小さいほど群演算の時間は短縮される。つまり、演算速度を実施の形態1よりも向上させることができる。また、実施の形態1と同様に、復号演算で行うペアリング演算の回数を階層数に比例した回数ではなく、一定の回数にすることができる。実施の形態3.実施の形態1、2で説明したワイルドカード対応の匿名性階層型IDベース暗号方式を応用してグループ共有型公開鍵秘匿検索方式について説明する。以下、実施の形態1、2と異なる事項について主に説明する。説明を省略する事項については実施の形態1、2と同様である。図17は、実施の形態3における公開鍵秘匿検索システム110の構成図である。実施の形態3における公開鍵秘匿検索システム110の構成について、図17に基づいて説明する。公開鍵秘匿検索システム110は、実施の形態1で説明した階層型IDベース暗号システム100の構成図1参照に加えて、検索装置500を備える。検索装置500は、暗号化装置400により生成された複数の暗号文データCTを記憶した検索記憶部590暗号文記憶部の一例を備える。検索装置500は、検索クエリQKを入力し、入力した検索クエリQKを用いて検索記憶部590を検索し、検索クエリQKに該当する暗号文データCTを出力する。復号装置300は、検索装置500によって検索された暗号文データCTを復号し、平文データMを出力する。図18は、実施の形態3における復号装置300の概要図である。実施の形態3における復号装置300の概要について、図18に基づいて説明する。復号装置300は、実施の形態1で説明した構成図7参照に加えて、クエリ生成処理部330を備える。クエリ生成処理部330は、クエリ生成入力部、クエリ生成前処理部、クエリ鍵値算出部およびクエリ生成部図示省略を備える。クエリ生成処理部330は、公開鍵PKとユーザiのユーザ秘密鍵SKIDiとユーザiのユーザ識別子IDiとキーワードKWとを入力し、検索クエリQKIDi,KWを出力する。図19は、実施の形態3における検索装置500の概要図である。実施の形態3における検索装置500の概要について、図19に基づいて説明する。検索装置500は、検索処理部510と検索記憶部590とを備える。検索処理部510は、公開鍵PKと検索クエリQKIDi,KWとを入力し、検索記憶部590に記憶された暗号文データCTを検索し、検索クエリQKIDi,KWに該当する暗号文データCTを出力する。検索記憶部590は、検索装置500で使用するデータを記憶する記憶部である。公開鍵PK、検索クエリQKIDi,KW、暗号文データCTは検索記憶部590に記憶されるデータの一例である。図20は、実施の形態3における検索装置500の機能構成図である。実施の形態3における検索装置500の機能構成について、図20に基づいて説明する。検索装置500は、前述の通り、検索処理部510と検索記憶部590とを備える。検索記憶部590は、複数の暗号文データCTと複数の暗号文データCTWとを予め記憶する。暗号文データCTWは、暗号化装置400図10参照によって以下のように生成される。暗号値算出部413は、特定の平文データMWを暗号化して平文暗号値CW0を算出する。暗号化入力部411は、前記暗号文データCTの検索に用いるキーワードKWを入力する。暗号値算出部413は、前記パターンPを含むと共に前記キーワードKWを第K1階層を識別する階層識別子として含むパターンPWを用いてワイルドカード暗号値CW1と識別暗号値CW3とを算出する。暗号文生成部414は、算出された平文暗号値CW0とワイルドカード暗号値CW1と識別暗号値CW3とを含んだ暗号文データCTWを生成し、生成した暗号文データCTWを前記暗号文データCTに対応付けて出力する。図20に戻り、検索装置500の説明を続ける。検索処理部510は、検索クエリ入力部511と検索部512と検索結果出力部513とを備える。検索クエリ入力部511は、検索クエリ入力処理を行う。例えば、検索クエリ入力部511は、検索クエリQKとワイルドカード階層値Wとを入力する。検索クエリQKは、復号装置300図18参照によって以下のように生成される。クエリ生成処理部330のクエリ生成入力部図示省略は、前記ユーザ識別子IDと前記キーワードKWとを入力するクエリ生成入力。クエリ生成処理部330のクエリ鍵値算出部図示省略は、入力されたユーザ識別子IDとキーワードKWとを用いて前記平文暗号値CW0の復号に用いる鍵値aW0を算出するクエリ鍵値算出処理。クエリ生成処理部330のクエリ生成部図示省略は、算出された鍵値aW0と前記ユーザ識別子IDとを含んだ検索クエリQKを生成し、生成した検索クエリQKを出力する検索クエリ生成処理。図20に戻り、検索装置500の説明を続ける。検索部512は、検索記憶部590から暗号文データCTWを選択する。検索部512は、入力されたワイルドカード階層値Wに基づいて入力された検索クエリQKに含まれるユーザ識別子IDから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出する。検索部512は、抽出したワイルドカード識別子と選択した暗号文データCTWに含まれるワイルドカード暗号値CW1と識別暗号値CW3と入力された検索クエリQKに含まれる鍵値aW0とを用いて、選択した暗号文データCTWに含まれる平文暗号値CW0を復号する。検索部512は、前記平文暗号値CW0を復号して得られた復号データが前記平文データMWと一致するか否かを判定する。検索部512は、前記復号データが前記平文データMWと一致した場合、選択した暗号文データCTWに対応する暗号文データCTを検索記憶部590から取得する。検索結果出力部513は、取得された暗号文データCTを入力された検索クエリQKに対する検索結果として出力する。図21は、実施の形態3における階層型IDベース暗号システム100の階層構造の一例を示す図である。図22は、実施の形態3における階層型IDベース暗号システム100のパターンPWの一例を示す図である。図21に示すように階層構造にはキーワード用の階層第5階層が含まれ、図22に示すようにパターンPWにはパターンPと暗号文データCTの検索用のキーワードKWとが含まれる。図23は、実施の形態3における暗号化装置400による暗号化方法を示すフローチャートである。実施の形態3における暗号化方法の処理の流れについて、図23に基づいて説明する。S411において、暗号化入力部411は、S410図14参照と同様に、公開鍵PKとユーザi用のパターンPWiと平文データMとを入力する。S411の後、S420に進む。S420-S440において、暗号処理部410は、パターンPWiに含まれるパターンPiを用いてユーザi用の暗号文データCTを生成する図14参照。S440の後、S450に進む。S450において、暗号化前処理部412は、暗号文データCTを入力として所定のハッシュ関数hを計算し、暗号文データCTのハッシュ値hCTを算出する。ハッシュ値hCTは暗号文データCTを群GTの要素に写した値である。例えば、ハッシュ値hCTは、暗号文データCTをビット列として入力した場合のハッシュ関数SHA-1の出力値である。S450の後、S460に進む。S460-S480において、暗号処理部410は、S450で算出されたハッシュ値hCTを平文データMWとしてS420-S440と同様に、パターンPWiを用いてユーザi用の暗号文データCTWを生成する。このとき、キーワードKWに対応する階層は識別階層として扱う。S480の後、S490に進む。S490において、暗号文生成部414は、S440で生成した暗号文データCTとS480で生成した暗号文CTWとを含んだ暗号文データCTWを生成し、生成した暗号文データCTWを出力する。S490により、暗号化方法の処理は終了する。図24は、実施の形態3における復号装置300によるクエリ生成方法を示すフローチャートである。復号装置300のクエリ生成処理部330が実行するクエリ生成方法の処理の流れについて、図24に基づいて説明する。S610において、クエリ生成処理部330は、公開鍵PKとユーザiのユーザ秘密鍵SKIDiとユーザiのユーザ識別子IDiとキーワードKWとを入力する。S610の後、S620に進む。S620-S650において、クエリ生成処理部330は、ユーザ識別子IDiにキーワードKWを加えたデータをユーザjのユーザ識別子IDjとして扱い、鍵委譲処理部320と同様に図13のS320-S350参照、複数の復号鍵値を算出する。S650の後、S660に進む。S660において、クエリ生成処理部330は、ユーザiのユーザ識別子IDiとS650で算出した複数の復号鍵値とを含んだ検索クエリQKを生成し、生成した検索クエリQKを出力する。S660により、クエリ生成方法の処理は終了する。図25は、実施の形態3における検索装置500による検索方法を示すフローチャートである。検索装置500の検索処理部510が実行する検索方法の処理の流れについて、図25に基づいて説明する。S710において、検索クエリ入力部511は、検索クエリQKと公開鍵PKとを入力する。S710の後、S711に進む。S711において、検索クエリ入力部511は、検索記憶部590から未処理の暗号文データCTWを順番にまたはランダムに一つ選択する。S712の後、S720に進む。S720-S740において、検索部512は、公開鍵PKと検索クエリQKに含まれる復号鍵値と検索クエリQKに含まれるユーザ識別子IDiと暗号文データCTWに含まれる暗号文データCTWとを用いて、平文データMWを算出する。平文データMWの算出方法は、復号方法図15のS520-S540参照と同様である。S740の後、S750に進む。S750において、検索部512は、暗号文データCTWに含まれる暗号文データCTのハッシュ値hCTを算出する。ハッシュ値hCTの算出方法は、S450図23参照と同様である。S750の後、S760に進む。S760において、検索部512は、S740で算出した平文データMWとS750で算出したハッシュ値hCTとを比較する。平文データMWとハッシュ値hCTとが一致する場合YES、S770に進む。平文データMWとハッシュ値hCTとが一致しない場合NO、S711に戻る。S770において、検索部512は、暗号文データCTWに含まれる暗号文データCTを出力する。S770により、検索方法の処理は終了する。S770で出力された暗号文データCTは、実施の形態1で説明した復号方法図15参照により復号される。公開鍵秘匿検索システム110は、キーワードを秘匿したままキーワード検索を行うことができる。なぜならば、検索される暗号文が秘匿性に加えて匿名性を有しており、暗号文を見てもキーワードについて何ら情報を得ることが出来ないからである。また、ワイルドカードの使用に対応しているため、実施の形態1と同様にグループ内で暗号文を共有することができる。検索キーワードは複数設けても構わない。つまり、キーワードに対応する階層を複数設けても構わない。この場合、暗号文データCTWは検索キーワードと同じ数の暗号文データCTWを含み、少なくともいずれかの暗号文データCTWについてハッシュ値hCTが一致した場合に検索にヒットしたと判定し、暗号文データCTを出力する。但し、全ての暗号文データCTWについてハッシュ値hCTが一致した場合に検索にヒットしたと判定しても構わない。さらに、暗号文データCTWの順番、つまり、検索キーワードの階層順序が一致した場合に検索にヒットしたと判定しても構わない。暗号化処理図23参照および検索方法図25参照において、ハッシュ値hCTの代わりに検索定数例えば、定数0を平文データMWとして扱ってもよい。つまり、検索時に復号された値が検索定数と一致した場合に検索にヒットしたと判定する。これにより、暗号文データCTと暗号文データCTW暗号化キーワードとを一緒に保持しておく必要はなくなり、別々に管理しておくことができる。したがって、データ管理の柔軟性を向上させることができる。本実施の形態では、検索クエリに検索ユーザのユーザ識別子を含ませる構成とした。これは、検索時に暗号文の中のワイルドカードに対応する要素を検索ユーザのユーザ識別子で焼き直すためである。しかし、焼き直しを必要としない場合すなわち自分宛の暗号文のみを検索する場合には、検索クエリにユーザ識別子を含まない構成にしてもよい。このようにすれば、検索ユーザは検索装置に対して自らのユーザ識別子を隠したまま検索を依頼することができる。本実施の形態では、実施の形態1と同様に合成数位数のペアリング群を用いることもできるし、実施の形態2と同様に素数位数のペアリング群の直積を用いることもできる。また、より一般に、委譲可能な秘匿ベクトル暗号Delegatablehiddenvectorencryptionを用いてグループ共有型公開鍵秘匿検索を実現することもできる。ここで言う委譲可能な秘匿ベクトル暗号とは、IDベース暗号または属性ベース暗号などのいわゆる述語暗号Predicateencryptionまたは関数型暗号Functionalencryptionである。但し、委譲可能な秘匿ベクトル暗号は、鍵委譲の機能を備え、かつ暗号化のIDまたは属性としてワイルドカード相当の機能を備えているものとする。さらに、委譲可能な秘匿ベクトル暗号は、IDまたは属性の情報が暗号文から漏洩しない匿名性を備えているものとする。この具体的な実現方式には、例えば非特許文献7に記載のDelegatableHVEや、非特許文献8に記載のHierarchicalpredicateencryptionなどがある。それぞれの暗号方式によって具体的なアルゴリズムやパラメータ、あるいは根拠とする数論仮定は異なる。しかし、いずれの暗号方式も基本的には実施の形態1と同様にセットアップ手段、鍵生成手段、鍵委譲手段、暗号化手段および復号手段、またはそれらに類するものを含む構成となっている。このため、本実施の形態に開示した構成に準じた構成をとることにより、本実施の形態と同様にグループ共有型公開鍵秘匿検索を実現することができる。これは、当業者であれば容易に理解し得ることである。本実施の形態によれば、グループ共有型公開鍵秘匿検索を実現することができる。さらに、検索演算および復号演算検索にヒットした暗号文を復号する演算の中のペアリング演算の回数を階層数に比例せず一定回数具体的には3回にすることができる。これにより、大企業や官公庁のように大きな階層を持つ組織においても高速な検索および復号を実現することができる。さらに、実施の形態1と同様に、ユーザ秘密鍵の生成委譲においても、また暗号化においても、ユーザ識別子を指定する際に中間の階層部分に空欄をおくことができる。これによって、図21に示した田中さんのように通常の階層構造から外れるようなユーザにも柔軟に対応することができる。つまり、特異な階層構造にも柔軟に対応することができる。さらに、より一般に、委譲可能な秘匿ベクトル暗号を用いてグループ共有型公開鍵秘匿検索を実現することができる。これによって、グループ共有型公開鍵秘匿検索方式を実現するためのより一般的な方法を提供することができる。実施の形態4.検索可能なユーザを追加または削除する形態について説明する。以下、実施の形態3と異なる事項について主に説明する。説明を省略する事項については実施の形態3と同様である。まず、検索可能なユーザを追加する形態について説明する。検索可能なユーザを追加するには、追加するユーザにユーザ識別子IDを割り当てればよい。図26は、実施の形態4におけるユーザ識別子IDの一例を示す図である。例えば、採用係に高橋さんが新たに配属された場合、図26に示すように高橋さんのユーザ識別子ID9を生成する。採用係長は実施の形態1で説明した鍵委譲方法により高橋さんにユーザ秘密鍵SKを委譲し、高橋さんは委譲されたユーザ秘密鍵SKを用いて実施の形態3で説明したクエリ生成方法により検索クエリQKを生成する。また、人事課に査定係が新たに設けられた場合、図26に示すように査定係査定係長のユーザ識別子ID10を生成する。人事課長は査定係長にユーザ秘密鍵SKを委譲し、査定係長は委譲されたユーザ秘密鍵SKを用いて検索クエリを生成する。また、査定係長は委譲されたユーザ秘密鍵SKを用いて査定係の各社員にユーザ秘密鍵SKを委譲する。次に、検索可能なユーザを削除する形態について説明する。検索可能なユーザを削除するには、検索できないユーザのリスト削除者リストを作成すればよい。図27は、実施の形態4における削除者リストの一例を示す図である。例えば、図27に示すような削除者リストを検索装置500の検索記憶部590検索識別子記憶部の一例に記憶しておく。削除者リストは、検索できないユーザ検索権限が無いユーザのユーザ識別子ID非検索識別子の一覧を示す。例えば、採用係の山田さんが別の部署に異動になった場合、採用係長は山田さんのユーザ識別子ID13を検索装置500に入力し、削除者リストへの山田さんの登録を依頼する。検索装置500のユーザ管理部図示省略は、入力されたユーザ識別子ID13を図27に示すように削除者リストに追加することにより、削除者リストに山田さんを登録する。人事課の研修係が廃止になった場合、同様に、人事課長が削除者リストへの研修係の登録を依頼し、検索装置500のユーザ管理部が研修係のユーザ識別子ID37を図27に示すように削除者リストに追加する。また、山田さんが採用係に再び配属になった場合、採用係長は山田さんのユーザ識別子ID13を検索装置500に入力し、削除者リストからの消去を依頼する。検索装置500のユーザ管理部は、入力されたユーザ識別子ID13を削除者リストから消去する。人事課の研修係が復活した場合、同様に、人事課長が削除者リストからの消去を依頼し、検索装置500のユーザ管理部が研修係のユーザ識別子ID37を削除者リストから消去する。このとき、他人からの虚偽の依頼を防ぐため、依頼者の電子署名の入力を要求してもよい。検索装置500のユーザ管理部は入力された電子署名を従来の署名検証方法により検証し、電子署名が正しい場合に依頼を受け付ける。図28は、実施の形態4における検索装置500の検索方法を示すフローチャートである。実施の形態4における検索装置500の検索方法について、図28に基づいて説明する。実施の形態4では、実施の形態3で説明した処理図25参照に加えて、S712とS713とを実行する。S712において、検索クエリ入力部511は、検索クエリQKに含まれるユーザ識別子IDが削除者リストに含まれているか否かを判定する。つまり、検索クエリQKに含まれるユーザ識別子IDが削除者リストに含まれるユーザ識別子IDと一致するか否かを判定する。ユーザ識別子IDが削除者リストに含まれている場合YES、検索方法の処理を終了する。ユーザ識別子IDが削除者リストに含まれていない場合NO、S713に進む。例えば、検索クエリQKに山田さんのユーザ識別子ID13が含まれている場合、図23の削除者リストには山田さんのユーザ識別子ID13が含まれているため、検索方法の処理を終了する。この場合、山田さんは検索装置500を用いて検索を行うことができない。S713において、検索クエリ入力部511は、検索クエリQKに含まれるユーザ識別子IDより上位の階層のユーザ識別子IDが削除者リストに含まれているか否かを判定する。つまり、検索クエリQKに含まれるユーザ識別子IDが削除者リスト内のユーザ識別子IDを含んでいるか否かを判定する。ユーザ識別子IDより上位の階層のユーザ識別子が削除者リストに含まれている場合YES、検索方法の処理を終了する。ユーザ識別子IDより上位の階層のユーザ識別子が削除者リストに含まれていない場合NO、S711に進む。例えば、検索クエリQKに研修係の社員のユーザ識別子IDが含まれている場合、図23の削除者リストには研修係のユーザ識別子ID37が含まれているため、検索方法の処理を終了する。この場合、研修係の社員は検索装置500を用いて検索を行うことができない。ところで、削除者リストに含まれている山田さんが検索装置500に対して検索クエリを送る際、削除されていない別のユーザの名前を騙って検索依頼をする可能性もある。しかしその場合でも、山田さんは、採用係宛てあるいはそれより広範囲の人事課宛てや総務部宛て、全社員宛ても含むの暗号文を検索することができない。例えば、山田さんが佐藤さんの名前ユーザ識別子を使って検索依頼した場合、山田さんが属する採用係用のパターンP2は図22に示したように社員名の欄第4階層がワイルドカードになっているはずである。したがって、検索手順の中で、暗号文の各要素のうちワイルドカードに対応する要素の焼き直しが行われる。山田さんは佐藤氏の名前を使っているので、暗号文のワイルドカードは佐藤さんの名前で焼き直される。一方、山田さんが送った検索クエリの中に含まれている復号鍵dkは、山田さんの名前を使って委譲された鍵であり、名前に対応する箇所には山田さんの名前が含まれている。このように、焼き直しに使われる名前佐藤と復号鍵に含まれる名前山田とが異なるので、仮にキーワードが一致していても、検索にヒットすることはない。ここでは、社員名の欄がワイルドカードになっている場合で説明したが、それ以外の欄がワイルドカードになっている場合でも同様である。したがって、削除されていない別のユーザの名前を使って検索依頼をしても、暗号文を検索することができない。なお、これを逆手にとれば、削除者リストに山田さんが含まれていても、山田さん宛ての暗号文を検索することができる。なぜならば、山田さん用のパターン図22のパターンP1にはワイルドカードが含まれていないからである。このため、暗号文の焼き直しが発生せず、山田さんの復号鍵dkが有効に機能する。このようにするには、実施の形態3にも記載のように、山田さんの検索クエリの中にユーザ識別子IDを含まない構成にすればよい。本実施の形態は、実施の形態3と同様に、委譲可能な秘匿ベクトル暗号であればどの方式でも実現可能である。本実施の形態によれば、グループ階層に新たにユーザまたは下位グループを追加し、新たに追加したユーザまたは下位グループにキーワード検索を実行させることができる。また、グループからユーザまたは下位グループを削除して、そのグループに関連するキーワード検索をできないようにすることができる。したがって、ユーザやグループの追加および脱退に柔軟に対応することができる。実施の形態5.削除者リストに含まれるユーザが個人宛ての暗号文も検索できない形態について説明する。以下、実施の形態4と異なる事項について主に説明する。説明を省略する事項については実施の形態4と同様である。図29は、実施の形態5におけるユーザ識別子IDの一例を示す図である。図29に示すように、実施の形態5では社員ユーザの一例を対応付ける階層を複数設ける。例えば、山田さんのユーザ識別子ID6には第4階層と第5階層との2つの階層に山田が含まれている。つまり、社員層が二重化されている。図30は、実施の形態5におけるパターンPの一例を示す図である。図30に示すように、実施の形態5では社員を対応付けた複数の階層のうち少なくとも1つの階層にワイルドカード値を設定する。例えば、山田さん用のパターンP1には、第4階層の要素としてワイルドカード値が含まれている。これにより、ユーザの失効を実現することができる。なぜならば、そのユーザが検索できる暗号文には必ずワイルドカードが含まれ、検索クエリの中にユーザ識別子が必ず含まれるからである。また、実施の形態4で述べたように、他人の名前を使って検索クエリを出すことができないためである。したがって、削除者リストに名前が載れば、そのユーザは検索を行うことができなくなる。つまり、そのユーザの検索権限は失効する。本実施の形態において、社員層より上位の階層を失効させる場合には、その階層を多重化すればよい。また、予め、全ての階層を多重化してもおいてもよい。本実施の形態によれば、ユーザまたはグループを失効させ、キーワード検索をできないようにすることができる。したがって、ユーザやグループの失効に柔軟に対応することができる。"