(57)【要約】  ワイルドカード対応の匿名性階層型ＩＤベース暗号方式において、ペアリング演算の回数を一定回数にすることを目的とする。ユーザ識別子ＩＤとパターンＰとを用いる。ユーザ識別子ＩＤは、ｋ個の階層識別子を含む。パターンＰは、階層識別子とワイルドカード値と空欄値とのいずれかを階層毎に含む。暗号化装置４００は、ワイルドカード値の階層に対応する鍵値Ｈとパターン値の階層に対応する鍵値Ｈとを公開鍵ＰＫから抽出し、暗号値Ｃ１と暗号値Ｃ３とを算出し、平文暗号値Ｃ０と暗号値Ｃ１と暗号値Ｃ３とを含む暗号文データＣＴを出力する。復号装置３００は、ユーザ識別子ＩＤからワイルドカード値に対応する階層の階層識別子を抽出し、抽出した階層識別子と暗号文データＣＴに含まれる暗号値Ｃ１と暗号値Ｃ３とを用いて暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、平文データＭを出力する。
2012098649.tif 000002
【特許請求の範囲】
【請求項１】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる暗号システムにおいて、
暗号化する平文データＭを入力し、入力した平文データＭを暗号化して平文暗号値Ｃ０を算出し、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力し、入力したパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、ｋ個の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、入力したパターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出し、算出した平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを生成し、生成した暗号文データＣＴを出力する暗号化装置と、
前記暗号文データＣＴと前記ユーザ識別子ＩＤとを入力し、入力した暗号文データＣＴに含まれるワイルドカード階層値Ｗに基づいて入力したユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と入力した暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて入力した暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する復号装置と
を備えたことを特徴とする暗号システム。
【請求項２】
前記公開鍵ＰＫは、ｋ個の階層に対応付けられたｋ個の鍵値Ｈ’を含むＨ’鍵値群を含み、
前記暗号化装置は、入力した公開鍵ＰＫに含まれるＨ’鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈ’を第２のワイルドカード鍵値として抽出し、抽出した第２のワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１’を算出し、入力した公開鍵ＰＫに含まれるＨ’鍵値群から前記識別階層に対応付けられた鍵値Ｈ’を第２の識別鍵値として抽出し、抽出した第２の識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３’を算出し、算出したワイルドカード暗号値Ｃ１’と識別暗号値Ｃ３’とを含めて前記暗号文データＣＴを出力し、
前記復号装置は、抽出したワイルドカード識別子と入力した暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とワイルドカード暗号値Ｃ１’と識別暗号値Ｃ３’とを用いて入力した暗号文データＣＴに含まれる平文暗号値Ｃ０を復号する
ことを特徴とする請求項１記載の暗号システム。
【請求項３】
前記暗号化装置は、さらに、特定の平文データＭＷを暗号化して平文暗号値ＣＷ０を算出し、前記暗号文データＣＴの検索に用いるキーワードＫＷを入力し、前記パターンＰを含むと共に前記キーワードＫＷを第Ｋ＋１階層を識別する階層識別子として含むパターンＰＷを用いてワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを算出し、算出した平文暗号値ＣＷ０とワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを含んだ暗号文データＣＴＷを前記暗号文データＣＴに対応付けて出力し、
前記暗号システムは、さらに、
前記ユーザ識別子ＩＤと前記キーワードＫＷとを入力し、入力したユーザ識別子ＩＤとキーワードＫＷとを用いて前記平文暗号値ＣＷ０の復号に用いる鍵値ｙ０を算出し、算出した鍵値ｙ０と前記ユーザ識別子ＩＤとを含んだ検索クエリＱＫを生成し、生成した検索クエリＱＫを出力する検索クエリ生成装置と、
複数の暗号文データＣＴと複数の暗号文データＣＴＷとを対応付けて記憶する暗号文記憶部を有する検索装置とを備え、
前記検索装置は、前記検索クエリＱＫと前記ワイルドカード階層値Ｗとを入力し、前記暗号文記憶部から暗号文データＣＴＷを選択し、入力したワイルドカード階層値Ｗに基づいて入力した検索クエリＱＫに含まれるユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と選択した暗号文データＣＴＷに含まれるワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３と入力した検索クエリＱＫに含まれる鍵値ｙ０とを用いて選択した暗号文データＣＴＷに含まれる平文暗号値ＣＷ０を復号し、前記平文暗号値ＣＷ０を復号して得られた復号データが前記平文データＭＷと一致するか否かを判定し、前記復号データが前記平文データＭＷと一致した場合、選択した暗号文データＣＴＷに対応する暗号文データＣＴを前記暗号文記憶部から取得し、取得した暗号文データＣＴを入力した検索クエリＱＫに対する検索結果として出力する
ことを特徴とする請求項１記載の暗号システム。
【請求項４】
前記暗号化装置は、前記暗号文データＣＴのハッシュ値を前記平文データＭＷとして算出し、算出した平文データＭＷを暗号化して前記平文暗号値ＣＷ０を算出し、
前記検索装置は、選択した暗号文データＣＴＷに対応する暗号文データＣＴのハッシュ値を前記平文データＭＷとして算出し、前記復号データが算出した平文データＭＷと一致するか否かを判定する
ことを特徴とする請求項３記載の暗号システム。
【請求項５】
前記暗号化装置は、前記平文データＭＷとして所定の検索定数を予め記憶し、予め記憶した検索定数を暗号化して前記平文暗号値ＣＷ０を算出し、
前記検索装置は、前記平文データＭＷとして前記検索定数を予め記憶し、前記復号データが前記検索定数と一致するか否かを判定する
ことを特徴とする請求項３記載の暗号システム。
【請求項６】
前記検索装置は、検索する権限が無いユーザのユーザ識別子ＩＤを非検索識別子として記憶する非検索識別子記憶部を備え、
前記検索装置は、入力した検索クエリＱＫに含まれるユーザ識別子ＩＤと前記非検索識別子記憶部に記憶された非検索識別子とが一致するか否かを判定し、前記ユーザ識別子ＩＤと前記非検索識別子とが一致する場合に前記検索結果を出力しない
ことを特徴とする請求項３記載の暗号システム。
【請求項７】
前記検索装置は、検索する権限が無いユーザが属する階層より上位の階層の階層識別子を非検索識別子として記憶する非検索識別子記憶部を備え、
前記検索装置は、入力した検索クエリＱＫに含まれるユーザ識別子ＩＤに前記非検索識別子記憶部に記憶された非検索識別子が含まれるか否かを判定し、前記ユーザ識別子ＩＤに前記非検索識別子が含まれる場合に前記検索結果を出力しない
ことを特徴とする請求項３記載の暗号システム。
【請求項８】
前記ユーザ識別子ＩＤは、前記特定のユーザの第１のユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に前記特定のユーザの第２のユーザ識別子を第ｋ＋１階層を識別する階層識別子として含み、
前記公開鍵ＰＫに含まれるＨ鍵値群は、ｋ＋１個の階層に対応付けられたｋ＋１個の鍵値Ｈを含み、
前記パターンＰは、第ｋ階層と第ｋ＋１階層との少なくともいずれかの階層のパターン値としてワイルドカード値を含む
ことを特徴とする請求項３記載の暗号システム。
【請求項９】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる暗号システムの暗号処理方法において、
暗号化装置が、暗号化する平文データＭを入力し、入力した平文データＭを暗号化して平文暗号値Ｃ０を算出し、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力し、入力したパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、ｋ個の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、入力したパターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出し、算出した平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを出力し、
復号化装置が、前記暗号文データＣＴと前記ユーザ識別子ＩＤとを入力し、入力した暗号文データＣＴに含まれるワイルドカード階層値Ｗに基づいて入力したユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と入力した暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて入力した暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する
ことを特徴とする暗号システムの暗号処理方法。
【請求項１０】
前記暗号化装置は、さらに、特定の平文データＭＷを暗号化して平文暗号値ＣＷ０を算出し、前記暗号文データＣＴの検索に用いるキーワードＫＷを入力し、前記パターンＰを含むと共に前記キーワードＫＷを第Ｋ＋１階層を識別する階層識別子として含むパターンＰＷを用いてワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを算出し、算出した平文暗号値ＣＷ０とワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを含んだ暗号文データＣＴＷを前記暗号文データＣＴに対応付けて出力し、
検索クエリ生成装置が、前記ユーザ識別子ＩＤと前記キーワードＫＷとを入力し、入力したユーザ識別子ＩＤとキーワードＫＷとを用いて前記平文暗号値ＣＷ０の復号に用いる鍵値ｙ０を算出し、算出した鍵値ｙ０と前記ユーザ識別子ＩＤとを含んだ検索クエリＱＫを出力し、
検索装置が、複数の暗号文データＣＴと複数の暗号文データＣＴＷとを対応付けて記憶する暗号文記憶部を有し、
前記検索装置は、前記検索クエリＱＫと前記ワイルドカード階層値Ｗとを入力し、前記暗号文記憶部から暗号文データＣＴＷを選択し、入力したワイルドカード階層値Ｗに基づいて入力した検索クエリＱＫに含まれるユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と選択した暗号文データＣＴＷに含まれるワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３と入力した検索クエリＱＫに含まれる鍵値ｙ０とを用いて選択した暗号文データＣＴＷに含まれる平文暗号値ＣＷ０を復号し、前記平文暗号値ＣＷ０を復号して得られた復号データが前記平文データＭＷと一致するか否かを判定し、前記復号データが前記平文データＭＷと一致した場合、選択した暗号文データＣＴＷに対応する暗号文データＣＴを前記暗号文記憶部から取得し、取得した暗号文データＣＴを入力した検索クエリＱＫに対する検索結果として出力する
ことを特徴とする請求項９記載の暗号システムの暗号処理方法。
【請求項１１】
暗号化する平文データＭを入力し、ｋ個（ｋは２以上の特定の整数）の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、階層を識別する階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力する暗号化入力部と、
前記暗号化入力部が入力した平文データＭを暗号化して平文暗号値Ｃ０を算出し、前記暗号化入力部が入力したパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、前記暗号化入力部が入力した公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、前記パターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、前記公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出する暗号値算出部と、
前記暗号値算出部により算出された平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを生成し、生成した暗号文データＣＴを出力する暗号文出力部と
を備えたことを特徴とする暗号化装置。
【請求項１２】
暗号化する平文データＭを入力し、ｋ個（ｋは２以上の特定の整数）の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、階層を識別する階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力する暗号化入力処理と、
前記暗号化入力処理により入力された平文データＭを暗号化して平文暗号値Ｃ０を算出し、前記暗号化入力処理により入力されたパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、前記暗号化入力処理により入力された公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、前記パターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、前記公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出する暗号値算出処理と、
前記暗号値算出処理により算出された平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを生成し、生成した暗号文データＣＴを出力する暗号文出力処理と
をコンピュータに実行させることを特徴とする暗号化プログラム。
【請求項１３】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる復号装置において、
階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを用いて生成された暗号文データＣＴであって平文データＭを暗号化した平文暗号値Ｃ０と特定のワイルドカード暗号値Ｃ１と特定の識別暗号値Ｃ３とを含むと共に前記パターンＰに含まれるパターン値がワイルドカード値である階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを入力し、前記ユーザ識別子ＩＤを入力する復号入力部と、
前記復号入力部が入力した暗号文データＣＴに基づいて、前記復号入力部が入力したユーザ識別子ＩＤから前記ワイルドカード階層値Ｗによって示される階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と前記暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて前記暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する復号部と
を備えたことを特徴とする復号装置。
【請求項１４】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる復号プログラムにおいて、
階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを用いて生成された暗号文データＣＴであって平文データＭを暗号化した平文暗号値Ｃ０と特定のワイルドカード暗号値Ｃ１と特定の識別暗号値Ｃ３とを含むと共に前記パターンＰに含まれるパターン値がワイルドカード値である階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを入力し、前記ユーザ識別子ＩＤを入力する復号入力処理と、
前記復号入力処理により入力された暗号文データＣＴに基づいて、前記復号入力処理により入力されたユーザ識別子ＩＤから前記ワイルドカード階層値Ｗによって示される階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と前記暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて前記暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する復号処理と
をコンピュータに実行させることを特徴とする復号プログラム。
【請求項１５】
Ｌ個（Ｌは２以上の特定の整数）の階層を有する組織に属するユーザの公開鍵ＰＫを生成するセットアップ装置において、
素数ｐと素数ｑとの積ｎを位数とする巡回群Ｇであってｎ個の要素値を含む巡回群Ｇを算出し、算出した巡回群Ｇの一部を構成する部分群Ｇｐであって素数ｐを位数とする部分群ＧｐからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値ｈとして選択し、前記部分群ＧｐからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値ｈ’として選択し、算出した巡回群Ｇの一部を構成する部分群Ｇｑであって素数ｑを位数とする部分群ＧｑからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値Ｒとして選択し、前記部分群ＧｑからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値Ｒ’として選択する要素値選択部と、
前記要素値選択部により選択されたＬ個の鍵値ｈとＬ個の鍵値Ｒとを階層毎に乗算してＬ個の階層に対応付けられたＬ個の鍵値ＨをＨ鍵値群として算出し、前記要素値選択部により選択されたＬ個の鍵値ｈ’とＬ個の鍵値Ｒ’とを階層毎に乗算してＬ個の階層に対応付けられたＬ個の鍵値Ｈ’をＨ’鍵値群として算出する公開鍵値算出部と、
前記公開鍵値算出部により算出されたＨ鍵値群とＨ’鍵値群とを含んだ公開鍵ＰＫを生成する公開鍵生成部と
を備えたことを特徴とするセットアップ装置。
【請求項１６】
Ｌ個（Ｌは２以上の特定の整数）の階層を有する組織に属するユーザの公開鍵ＰＫを生成するセットアッププログラムにおいて、
素数ｐと素数ｑとの積ｎを位数とする巡回群Ｇであってｎ個の要素値を含む巡回群Ｇを算出し、算出した巡回群Ｇの一部を構成する部分群Ｇｐであって素数ｐを位数とする部分群ＧｐからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値ｈとして選択し、前記部分群ＧｐからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値ｈ’として選択し、算出した巡回群Ｇの一部を構成する部分群Ｇｑであって素数ｑを位数とする部分群ＧｑからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値Ｒとして選択し、前記部分群ＧｑからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値Ｒ’として選択する要素値選択処理と、
前記要素値選択処理により選択されたＬ個の鍵値ｈとＬ個の鍵値Ｒとを階層毎に乗算してＬ個の階層に対応付けられたＬ個の鍵値ＨをＨ鍵値群として算出し、前記要素値選択処理により選択されたＬ個の鍵値ｈ’とＬ個の鍵値Ｒ’とを階層毎に乗算してＬ個の階層に対応付けられたＬ個の鍵値Ｈ’をＨ’鍵値群として算出する公開鍵値算出処理と、
前記公開鍵値算出処理により算出されたＨ鍵値群とＨ’鍵値群とを含んだ公開鍵ＰＫを生成する公開鍵生成処理と
をコンピュータに実行させることを特徴とするセットアッププログラム。
【請求項１７】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ秘密鍵ＳＫを生成する鍵生成装置において、
前記特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを入力し、ｋ個の階層に対応付けられたｋ個の鍵値ｈを含むｈ鍵値群とｋ個の階層に対応付けられたｋ個の鍵値ｈ’を含むｈ’鍵値群とを含むマスタ秘密鍵ＭＳＫを入力する鍵生成入力部と、
前記鍵生成入力部が入力したユーザ識別子ＩＤとマスタ秘密鍵ＭＳＫとを用いて暗号文データＣＴの復号に用いる鍵値ａ０を算出するユーザ秘密鍵値算出部と、
前記ユーザ秘密鍵値算出部により算出された鍵値ａ０を含んだユーザ秘密鍵ＳＫを生成し、生成したユーザ秘密鍵ＳＫを出力するユーザ秘密鍵生成部と
を備えたことを特徴とする鍵生成装置。
【請求項１８】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ秘密鍵ＳＫを生成する鍵生成プログラムにおいて、
前記特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを入力し、ｋ個の階層に対応付けられたｋ個の鍵値ｈを含むｈ鍵値群とｋ個の階層に対応付けられたｋ個の鍵値ｈ’を含むｈ’鍵値群とを含んだマスタ秘密鍵ＭＳＫを入力する鍵生成入力処理と、
前記鍵生成入力処理により入力されたユーザ識別子ＩＤとマスタ秘密鍵ＭＳＫとを用いて暗号文データＣＴの復号に用いる鍵値ａ０を算出するユーザ秘密鍵値算出処理と、
前記ユーザ秘密鍵値算出処理により算出された鍵値ａ０を含んだユーザ秘密鍵ＳＫを生成し、生成したユーザ秘密鍵ＳＫを出力するユーザ秘密鍵生成処理と
をコンピュータに実行させることを特徴とする鍵生成プログラム。
【請求項１９】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属するユーザｊのユーザ秘密鍵ＳＫｊを生成する鍵委譲装置において、
前記ユーザｊのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤｊを入力し、第ｋ−１階層に属するユーザｉのユーザ秘密鍵ＳＫｉであって暗号文データＣＴの復号に用いる鍵値ａ０を含んだユーザ秘密鍵ＳＫｉを入力する鍵委譲入力部と、
前記鍵委譲入力部が入力したユーザ識別子ＩＤｊとユーザ秘密鍵ＳＫｉとを用いて前記暗号文データＣＴの復号に用いる鍵値ｘ０を算出する委譲鍵値算出部と、
前記委譲鍵値算出部により算出された鍵値ｘ０を含んだユーザ秘密鍵ＳＫｊを生成し、生成したユーザ秘密鍵ＳＫｊを出力する委譲鍵生成部と
を備えたことを特徴とする鍵委譲装置。
【請求項２０】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属するユーザｊのユーザ秘密鍵ＳＫｊを生成する鍵委譲プログラムにおいて、
前記ユーザｊのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤｊを入力し、第ｋ−１階層に属するユーザｉのユーザ秘密鍵ＳＫｉであって暗号文データＣＴの復号に用いる鍵値ａ０を含んだユーザ秘密鍵ＳＫｉを入力する鍵委譲入力処理と、
前記鍵委譲入力処理により入力されたユーザ識別子ＩＤｊとユーザ秘密鍵ＳＫｉとを用いて前記暗号文データＣＴの復号に用いる鍵値ｘ０を算出する委譲鍵値算出処理と、
前記委譲鍵値算出処理により算出された鍵値ｘ０を含んだユーザ秘密鍵ＳＫｊを生成し、生成したユーザ秘密鍵ＳＫｊを出力する委譲鍵生成処理と
をコンピュータに実行させることを特徴とする鍵委譲プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、暗号システム、暗号システムの暗号処理方法、暗号化装置、暗号化プログラム、復号装置、復号プログラム、セットアップ装置、セットアッププログラム、鍵生成装置、鍵生成プログラム、鍵委譲装置および鍵委譲プログラムに関するものである。
【背景技術】
【０００２】
公開鍵暗号の技術分野の一つとして階層型ＩＤベース暗号について多く実現方式が知られており、それぞれ実現方式は様々な特徴を有している。
その中で、暗号文に匿名性を持たせることのできる匿名性階層型ＩＤベース暗号方式がいくつか知られている（例えば特許文献１、非特許文献１）。
匿名性とは、暗号文を見ても、どのＩＤ宛ての暗号文であるかがわからないという性質である。【０００３】
階層型ＩＤベース暗号の使われ方によっては、匿名性が必要不可欠な性質となる場合がある。
例えば、インターネットの掲示板やファイルサーバを利用して、階層型ＩＤベース暗号の暗号文をある特定のユーザに送る場合を考える。
ここで、宛先を知られることがまずい場合（例えば合併前の会社同士のやりとりであって、やりとりをしていること自体を知られることがまずい場合）には、匿名性のない方式を使用することはできない。
なぜならば、暗号文が解析されることで宛先が漏洩してしまうからである。
したがって、このような場合には匿名性が必要不可欠となる。【０００４】
また、階層型ＩＤベース暗号は秘匿検索へも応用できることが知られている。秘匿検索とは、暗号化したままキーワード検索する技術であり、検索可能暗号とも言う。
この場合にも匿名性が必要不可欠である。なぜならば、ＩＤベース暗号におけるＩＤが秘匿検索におけるキーワードに対応しており、匿名性がない（すなわちＩＤが漏洩する）こととキーワードが漏洩することとが対応するからである。【０００５】
上述のとおり、暗号文に匿名性を持たせることのできる匿名性階層型ＩＤベース暗号方式がいくつか知られている（例えば特許文献１、非特許文献１）。
しかし、これらの方式では、同一内容の暗号文を複数の宛先ＩＤに対して作成する場合、ＩＤ数分の暗号文を作成しなければならず、暗号文の個数が増大してしまう。
そこで、発展方式として、１個の暗号文で同一階層に属するユーザ全員宛てに送ることのできる「ワイルドカード対応の匿名性階層型ＩＤベース暗号方式」が知られている（非特許文献２）。【０００６】
また、「ワイルドカード対応の階層型ＩＤベース暗号方式」を公開鍵型の秘匿検索の分野に応用することで、「グループ共有型公開鍵秘匿検索方式」を実現できることが知られている（非特許文献２）。
「グループ共有型公開鍵秘匿検索方式」では、１個の暗号文をグループ内で共有することができ、グループ内の各ユーザが自分の秘密鍵を使って暗号文に対する検索用クエリを作成することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１０−１６１５２３号公報
【非特許文献】
【０００８】
【非特許文献１】Ｘａｖｉｅｒ  Ｂｏｙｅｎ  ａｎｄ  Ｂｒｅｎｔ  Ｗａｔｅｒｓ，  “Ａｎｏｎｙｍｏｕｓ  ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  （ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ），”  Ｃｒｙｐｔｏ  ２００６，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ４１１７，  ｐｐ．  ２９０−−３０７，  ２００６．
【非特許文献２】Ｍｉｔｓｕｈｉｒｏ  Ｈａｔｔｏｒｉ，  Ｔａｋｕｍｉ  Ｍｏｒｉ，  Ｔａｋａｓｈｉ  Ｉｔｏ，  Ｎｏｒｉ  Ｍａｔｓｕｄａ，  Ｔａｋｅｓｈｉ  Ｙｏｎｅｄａ，  ａｎｄ  Ｋａｚｕｏ  Ｏｈｔａ，  “Ａｎｏｎｙｍｏｕｓ  ＨＩＢＥ  ｗｉｔｈ  ｗｉｌｄｃａｒｄｓ  ａｎｄ  ｉｔｓ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｓｅｃｕｒｅ  ｋｅｙｗｏｒｄ  ｓｅａｒｃｈ  ｆｏｒ  ｇｒｏｕｐ−ｏｒｉｅｎｔｅｄ  ｍｕｌｔｉ−ｕｓｅｒ  ｓｙｓｔｅｍ，”  ＳＣＩＳ  ２０１０，  ２０１０．
【非特許文献３】Ｄａｎ  Ｂｏｎｅｈ，  Ｅｕ−Ｊｉｎ  Ｇｏｈ，  ａｎｄ  Ｋｏｂｂｉ  Ｎｉｓｓｉｍ，  “Ｅｖａｌｕａｔｉｎｇ  ２−ＤＮＦ  ｆｏｒｍｕｌａｓ  ｏｎ  ｃｉｐｈｅｒｔｅｘｔｓ，”  Ｔｈｅｏｒｙ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｃｏｎｆｅｒｅｎｃｅ，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ３３７８，  ｐｐ．  ３２５−３４１，  ２００５．
【非特許文献４】Ａｌｆｒｅｄ  Ｊ．  Ｍｅｎｅｚｅｓ，  Ｐａｕｌ  Ｃ．  ｖａｎ  Ｏｏｒｓｃｈｏｔ，  ａｎｄ  Ｓｃｏｔｔ  Ａ．  Ｖａｎｓｔｏｎｅ，  “Ｈａｎｄｂｏｏｋ  ｏｆ  ａｐｐｌｉｅｄ  ｃｒｙｐｔｏｇｒａｐｈｙ，”  ４．４  Ｐｒｉｍｅ  ｎｕｍｂｅｒ  ｇｅｎｅｒａｔｉｏｎ，  ＣＲＣ  Ｐｒｅｓｓ，  ｐｐ．  １４５−１５４，  １９９６．
【非特許文献５】Ｊａｅ  Ｈｏｎｇ  Ｓｅｏ，  Ｔｅｔｓｕｔａｒｏ  Ｋｏｂａｙａｓｈｉ，  Ｍｉｙａｋｏ  Ｏｈｋｕｂｏ，  ａｎｄ  Ｋｏｕｔａｒｏｕ  Ｓｕｚｕｋｉ，  “Ａｎｏｎｙｍｏｕｓ  ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｃｏｎｓｔａｎｔ  ｓｉｚｅ  ｃｉｐｈｅｒｔｅｘｔｓ，”  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ５４４３，  ｐｐ．  ２１５−２３４，  ２００９．
【非特許文献６】Ｄａｖｉｄ  Ｍａｎｄｅｌｌ  Ｆｒｅｅｍａｎ，  “Ｃｏｎｖｅｒｔｉｎｇ  ｐａｉｒｉｎｇ−ｂａｓｅｄ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ｆｒｏｍ  ｃｏｍｐｏｓｉｔｅ−ｏｒｄｅｒ  ｇｒｏｕｐｓ  ｔｏ  ｐｒｉｍｅ−ｏｒｄｅｒ  ｇｒｏｕｐｓ，”  Ｅｕｒｏｃｒｙｐｔ  ２０１０，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ６１１０，  ｐｐ．  ４４−６１，  ２０１０．
【非特許文献７】Ｅｌａｉｎｅ  Ｓｈｉ  ａｎｄ  Ｂｒｅｎｔ  Ｗａｔｅｒｓ，  “Ｄｅｌｅｇａｔｉｎｇ  ｃａｐａｂｉｌｉｔｉｅｓ  ｉｎ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｓｙｓｔｅｍｓ，”  ＩＣＡＬＰ  ２００８，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ５１２６，  ｐｐ．  ５６０−５７８，  ２００８．
【非特許文献８】Ｔａｔｓｕａｋｉ  Ｏｋａｍｏｔｏ  ａｎｄ  Ｋａｔｓｕｙｕｋｉ  Ｔａｋａｓｈｉｍａ，  “Ｈｉｅｒａｒｃｈｉｃａｌ  ｐｒｅｄｉｃａｔｅ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｉｎｎｅｒ−ｐｒｏｄｕｃｔｓ，”  Ａｓｉａｃｒｙｐｔ  ２００９，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  ５９１２，  ｐｐ．  ２１４−２３１，  ２００９．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献２に記載の「ワイルドカード対応の匿名性階層型ＩＤベース暗号方式」は、復号演算で最も時間がかかるペアリング演算の回数が階層の高さに比例してしまうため、大企業や官公庁のように大きな階層を持つ組織では利用しづらい。
ペアリング演算の回数が階層の高さに比例してしまうのは、階層の高さに比例した個数の要素が暗号文の構成要素として含まれており、復号時にその各々をペアリング演算しなければならないためである。【００１０】
また、非特許文献２に記載の「ワイルドカード対応の匿名性階層型ＩＤベース暗号方式」では、暗号化やユーザ秘密鍵の作成において対象となるユーザのユーザＩＤ（ユーザ識別子）を指定する際に、上位階層から順に漏れ無く要素を指定する必要がある。
そのため、部・課・係などの階層を備える大規模な組織において、部直属のユーザのように、通常の階層構造から外れるユーザに対応することが出来なかった。
つまり、対応可能な階層構造に制約があり、柔軟性が低いという課題があった。【００１１】
また、非特許文献２に記載の「グループ共有型公開鍵秘匿検索方式」は、「ワイルドカード対応の匿名性階層型ＩＤベース暗号方式」と同様に、検索演算におけるペアリング演算の回数が階層数の高さに比例してしまうため、大企業や官公庁のように大きな階層を持つ組織では利用しづらい。【００１２】
また、非特許文献２には「ワイルドカード対応の匿名性階層型ＩＤベース暗号方式」を用いて「グループ共有型公開鍵秘匿検索方式」を実現する方法は開示されていたが、「グループ共有型公開鍵秘匿検索方式」を実現するためのより一般的な方法は開示されていない。
そのため、「グループ共有型公開鍵秘匿検索方式」を構成する際の選択肢が少ないという課題があった。【００１３】
また、非特許文献２には「グループ共有型公開鍵秘匿検索方式」においてグループ内で暗号文を共有し、グループにメンバを加入させる方法が開示されているが、グループからメンバを脱退させる方法は開示されていない。また、加入・脱退にかかわらずメンバ自体を失効させるための方法も開示されていない。
そのため、異動や出向、あるいは退職があるような組織では利用しづらいという課題があった。【００１４】
本発明は、例えば、以下のようなことを目的とする。【００１５】
ワイルドカード対応の匿名性階層型ＩＤベース暗号方式において、復号演算中のペアリング演算の回数が階層数に比例せず一定回数となるような方式を提供することを目的とする。【００１６】
また、グループ共有型公開鍵秘匿検索方式において、検索演算の中のペアリング演算の回数が階層数に比例せず一定回数となるような方式を提供することを目的とする。【００１７】
また、グループ共有型公開鍵秘匿検索方式を実現するためのより一般的な方法を提供することを目的とする。【００１８】
また、グループ共有型公開鍵秘匿検索方式において、グループからメンバを脱退する方法を提供することを目的とする。【００１９】
また、グループ共有型公開鍵秘匿検索方式においてメンバを失効させる方法を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明の暗号システムは、階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる暗号システムである。
前記暗号システムは、暗号化装置と復号装置とを備える。
前記暗号化装置は、暗号化する平文データＭを入力し、ｋ個の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、入力した平文データＭを暗号化して平文暗号値Ｃ０を算出し、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力し、入力したパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、入力したパターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出し、算出した平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを生成し、生成した暗号文データＣＴを出力する。
前記復号装置は、前記暗号文データＣＴと前記ユーザ識別子ＩＤとを入力し、入力した暗号文データＣＴに含まれるワイルドカード階層値Ｗに基づいて入力したユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と入力した暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて入力した暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する。
【発明の効果】
【００２１】
本発明によれば、例えば、ワイルドカード対応の匿名性階層型ＩＤベース暗号方式において、復号演算中のペアリング演算の回数が階層数に比例せず一定回数になる。
【図面の簡単な説明】
【００２２】
【図１】実施の形態１における階層型ＩＤベース暗号システム１００の構成図。
【図２】実施の形態１における階層型ＩＤベース暗号システム１００の階層構造の一例を示す図。
【図３】実施の形態１における階層型ＩＤベース暗号システム１００のユーザ識別子ＩＤの一例を示す図。
【図４】実施の形態１における階層型ＩＤベース暗号システム１００のパターンＰの一例を示す図。
【図５】実施の形態１におけるセットアップ装置２００の概要図。
【図６】実施の形態１におけるセットアップ装置２００の機能構成図。
【図７】実施の形態１における復号装置３００の概要図。
【図８】実施の形態１における復号装置３００の機能構成図。
【図９】実施の形態１における暗号化装置４００の概要図。
【図１０】実施の形態１における暗号化装置４００の機能構成図。
【図１１】実施の形態１におけるセットアップ装置２００によるセットアップ方法を示すフローチャート。
【図１２】実施の形態１におけるセットアップ装置２００による鍵生成方法を示すフローチャート。
【図１３】実施の形態１における復号装置３００による鍵委譲方法を示すフローチャート。
【図１４】実施の形態１における暗号化装置４００による暗号化方法を示すフローチャート。
【図１５】実施の形態１における復号装置３００による復号方法を示すフローチャート。
【図１６】実施の形態における階層型ＩＤベース暗号システム１００のハードウェア資源の一例を示す図。
【図１７】実施の形態３における公開鍵秘匿検索システム１１０の構成図。
【図１８】実施の形態３における復号装置３００の概要図。
【図１９】実施の形態３における検索装置５００の概要図。
【図２０】実施の形態３における検索装置５００の機能構成図。
【図２１】実施の形態３における階層型ＩＤベース暗号システム１００の階層構造の一例を示す図。
【図２２】実施の形態３における階層型ＩＤベース暗号システム１００のパターンＰＷの一例を示す図。
【図２３】実施の形態３における暗号化装置４００による暗号化方法を示すフローチャート。
【図２４】実施の形態３における復号装置３００によるクエリ生成方法を示すフローチャート。
【図２５】実施の形態３における検索装置５００による検索方法を示すフローチャート。
【図２６】実施の形態４におけるユーザ識別子ＩＤの一例を示す図。
【図２７】実施の形態４における削除者リストの一例を示す図。
【図２８】実施の形態４における検索装置５００の検索方法を示すフローチャート。
【図２９】実施の形態５におけるユーザ識別子ＩＤの一例を示す図。
【図３０】実施の形態５におけるパターンＰの一例を示す図。
【発明を実施するための形態】
【００２３】
実施の形態１．
「ワイルドカード対応の匿名性階層型ＩＤベース暗号方式」の実現方法について説明する。
【００２４】
図１は、実施の形態１における階層型ＩＤベース暗号システム１００の構成図である。
実施の形態１における階層型ＩＤベース暗号システム１００の構成について、図１に基づいて説明する。
【００２５】
階層型ＩＤベース暗号システム１００（暗号システムの一例）は、セットアップ装置２００（鍵生成装置の一例）と復号装置３００（鍵委譲装置の一例）と暗号化装置４００とを備える。
セットアップ装置２００と復号装置３００と暗号化装置４００とは、それぞれにネットワークに接続し、互いに通信を行う。
【００２６】
階層型ＩＤベース暗号システム１００には複数の復号装置３００が存在し、セットアップ装置２００と複数の復号装置３００とはツリー状の階層構造を構成している。
図１では、セットアップ装置２００が階層構造の根（第０階層）を構成し、４台の復号装置３００Ａ−Ｄが２つの階層（第１、２階層）を構成している。
復号装置３００Ａ・Ｂは第１階層を構成し、復号装置３００Ｃ・Ｄは復号装置３００Ａを上位の復号装置３００（親装置）として第２階層を構成している。
但し、復号装置３００の台数は２または３台であっても構わないし、５台以上であっても構わない。
また、複数の復号装置３００は３階層以上の階層を構成しても構わない。
【００２７】
セットアップ装置２００は、各復号装置３００によって共通に使用される公開鍵ＰＫ（公開鍵データ）を生成すると共に、第１階層の復号装置３００毎にユーザ秘密鍵ＳＫを生成する。
セットアップ装置２００は、第１階層に限らず第２階層以下の階層の復号装置３００を対象にしてユーザ秘密鍵ＳＫを生成しても構わない。
【００２８】
暗号化装置４００は、暗号化されていないデータ（以下、「平文データＭ」という）を暗号化し、暗号文データＣＴを生成する。
【００２９】
復号装置３００は、暗号化装置４００によって生成された暗号文データＣＴを公開鍵ＰＫと自己のユーザ秘密鍵ＳＫとを用いて復号し、平文データＭを生成する。
【００３０】
また、復号装置３００は、自己のユーザ秘密鍵ＳＫを用いて下位の復号装置３００（子装置）毎にユーザ秘密鍵ＳＫを生成する。
例えば、復号装置３００Ａは、自己のユーザ秘密鍵ＳＫ（ＩＤＡ）を用いて、復号装置３００Ｃ用のユーザ秘密鍵ＳＫ（ＩＤＣ）と復号装置３００Ｄ用のユーザ秘密鍵ＳＫ（ＩＤＤ）とを生成する。
【００３１】
図２は、実施の形態１における階層型ＩＤベース暗号システム１００の階層構造の一例を示す図である。
階層型ＩＤベース暗号システム１００を適用するＡ社の階層構造について、図２に基づいて説明する。
【００３２】
例えば、階層型ＩＤベース暗号システム１００は会社組織に適用することができる。
ここで、Ａ社には総務部、開発部、広報部などの「部」が存在し、「部」には人事課、経理課などの「課」が存在し、「課」には採用係、研修係などの「係」が存在しているものとする。
この場合、「部」を第１階層、「課」を第２階層、「係」を第３階層として扱い、社員を第４階層として扱う。但し、社員はいずれかの「係」に配属されるものとは限らず、「部」または「課」に直属で配属されても構わない。図２では、田中さんが総務部の直属の社員である。
【００３３】
そして、Ａ社はセットアップ装置２００と暗号化装置４００とを所有する。
また、各「部」は部長が使用する復号装置３００を所有し、各「課」は課長が使用する復号装置３００を所有し、各「係」は係長が使用する復号装置３００を所有する。
さらに、各社員は復号装置３００を所有する。
【００３４】
また、部長、課長、係長および社員（それぞれユーザの一例）には各自を識別する「ユーザ識別子ＩＤ」を割り当てる。
さらに、個人（ユーザ）または部署（階層）毎に暗号処理用のデータ「パターンＰ」を予め定義しておく。
【００３５】
図３は、実施の形態１における階層型ＩＤベース暗号システム１００のユーザ識別子ＩＤの一例を示す図である。
階層型ＩＤベース暗号システム１００を適用するＡ社内のユーザ識別子ＩＤについて、図３に基づいて説明する。
【００３６】
ユーザ識別子ＩＤは、階層数と同じ個数の要素（識別子）を含んだデータである。
つまり、Ａ社の階層数は「４」（図２参照）であるため、Ａ社で使用するユーザ識別子ＩＤには４つの要素が含まれる。
【００３７】
図中において、「φ」は不要な階層（対応する情報が無い階層）を意味する要素（空欄値）である。
【００３８】
例えば、総務部長のユーザ識別子ＩＤ１は（総務部、φ、φ、φ）であり、人事課長のユーザ識別子ＩＤ２は（総務部、人事課、φ、φ）である。
同様に、採用係長のユーザ識別子ＩＤ５は（総務部、人事課、採用係、φ）であり、山田さんのユーザ識別子ＩＤ６は（総務部、人事課、採用係、山田）である。
また、総務部直属の社員である田中さんのユーザ識別子ＩＤ８は（総務部、φ、φ、田中）となる。
【００３９】
ユーザ識別子ＩＤに含まれる要素は、数字、文字、記号またはそれらの組み合わせたものなど、自由に定めることができる。
例えば、識別子“総務部”は文字列であっても構わないし、総務部に対応付けられた番号（整数値）であっても構わない。
【００４０】
以下、ユーザ識別子ＩＤに含まれる要素を「階層識別子」という。
【００４１】
図４は、実施の形態１における階層型ＩＤベース暗号システム１００のパターンＰの一例を示す図である。
階層型ＩＤベース暗号システム１００を適用するＡ社内のパターンＰについて、図４に基づいて説明する。
【００４２】
パターンＰは、階層数と同じ個数の要素（識別子）を含んだデータである。
つまり、Ａ社の階層数は「４」（図２参照）であるため、Ａ社で使用するパターンＰには４つの要素が含まれる。
【００４３】
図中において、「＊」は当該部署または階層に属する任意の個人（全てのユーザ）を意味する要素（ワイルドカード値）である。
【００４４】
例えば、山田さん用のパターンＰ１は（総務部、人事課、採用係、山田）であり、人事課長用のパターンＰ４は（総務部、人事課、φ、φ）であり、総務部直属の田中さん用のパターンＰ８は（総務部、φ、φ、田中）である。
このように、個人用のパターンＰはユーザ識別子ＩＤと同一である（図３参照）。
【００４５】
また、採用係に属する社員用のパターンＰ２は（総務部、人事課、採用係、＊）であり、総務部に属する課長用のパターンＰ５は（総務部、＊、φ、φ）である。
さらに、部長または課長用のパターンＰ６は（＊、＊、φ、φ）であり、部長、課長、係長または社員用のパターンＰ７は（＊、＊、＊、＊）である。
このように、個人用ではなく部署または階層用のパターンＰには「＊」が含まれる。
【００４６】
以下、パターンＰに含まれる要素を「パターン値」という。
【００４７】
次に、階層型ＩＤベース暗号システム１００を構成する各装置（図１参照）について説明する。
【００４８】
図５は、実施の形態１におけるセットアップ装置２００の概要図である。
実施の形態１におけるセットアップ装置２００の概要について、図５に基づいて説明する。
【００４９】
セットアップ装置２００は、セットアップ処理部２１０と鍵生成処理部２２０とセットアップ記憶部２９０（鍵生成記憶部の一例）とを備える。
【００５０】
セットアップ処理部２１０は、セキュリティパラメータλと階層数Ｌとを入力し、公開鍵ＰＫとマスタ秘密鍵ＭＳＫとを生成し、生成した公開鍵ＰＫとマスタ秘密鍵ＭＳＫとを出力する。
【００５１】
鍵生成処理部２２０は、公開鍵ＰＫとマスタ秘密鍵ＭＳＫとユーザｉのユーザ識別子ＩＤｉとを入力し、ユーザｉのユーザ秘密鍵ＳＫ（ＩＤｉ）を生成し、生成したユーザｉのユーザ秘密鍵ＳＫ（ＩＤｉ）を出力する。
【００５２】
セットアップ記憶部２９０は、セットアップ装置２００で使用するデータを記憶する記憶部である。
例えば、セキュリティパラメータλ、階層数Ｌ、公開鍵ＰＫ、マスタ秘密鍵ＭＳＫ、ユーザ識別子ＩＤｉ、ユーザ秘密鍵ＳＫ（ＩＤｉ）は、セットアップ記憶部２９０に記憶されるデータの一例である。
【００５３】
図６は、実施の形態１におけるセットアップ装置２００の機能構成図である。
実施の形態１におけるセットアップ装置２００の機能構成について、図６に基づいて説明する。
【００５４】
セットアップ装置２００（鍵生成装置の一例）は、前述の通り、セットアップ処理部２１０と鍵生成処理部２２０とセットアップ記憶部２９０（鍵生成記憶部の一例）とを備える。
【００５５】
セットアップ処理部２１０は、例えば、Ｌ個（Ｌは２以上の特定の整数）の階層を有する組織に属するユーザの公開鍵ＰＫを生成する。
【００５６】
セットアップ処理部２１０は、セットアップ入力部２１１、セットアップ前処理部２１２、公開鍵値算出部２１３、公開鍵生成部２１４、マスタ秘密鍵生成部２１５およびセットアップ出力部２１６を備える。
【００５７】
セットアップ入力部２１１は、セットアップ入力処理を行う。
例えば、セットアップ入力部２１１は、セキュリティパラメータλと階層数Ｌとを入力する。
【００５８】
セットアップ前処理部２１２（要素値選択部の一例）は、セットアップ前処理（要素値選択処理を含む）を行う。
例えば、セットアップ前処理部２１２は、セットアップ前処理において以下の処理を行う。
【００５９】
セットアップ前処理部２１２は、セキュリティパラメータλに基づいて素数ｐと素数ｑとの積ｎを位数とする巡回群Ｇであってｎ個の要素値を含む巡回群Ｇを算出する。
セットアップ前処理部２１２は、算出した巡回群Ｇの一部を構成する部分群Ｇｐであって素数ｐを位数とする部分群ＧｐからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値ｈとして選択する。
セットアップ前処理部２１２は、前記部分群ＧｐからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値ｈ’として選択する。
セットアップ前処理部２１２は、算出した巡回群Ｇの一部を構成する部分群Ｇｑであって素数ｑを位数とする部分群ＧｑからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値Ｒとして選択する。
セットアップ前処理部２１２は、前記部分群ＧｑからＬ個の要素値をＬ個の階層に対応付けてＬ個の鍵値Ｒ’として選択する。
【００６０】
公開鍵値算出部２１３は、公開鍵値算出処理を行う。
例えば、公開鍵値算出部２１３は、公開鍵値算出処理において以下の処理を行う。
【００６１】
公開鍵値算出部２１３は、セットアップ前処理部２１２により選択されたＬ個の鍵値ｈとＬ個の鍵値Ｒとを階層毎に乗算してＬ個の階層に対応付けられたＬ個の鍵値ＨをＨ鍵値群として算出する。
公開鍵値算出部２１３は、セットアップ前処理部２１２により選択されたＬ個の鍵値ｈ’とＬ個の鍵値Ｒ’とを階層毎に乗算してＬ個の階層に対応付けられたＬ個の鍵値Ｈ’をＨ’鍵値群として算出する。
【００６２】
公開鍵生成部２１４は、公開鍵生成処理を行う。
例えば、公開鍵生成部２１４は、公開鍵生成処理において以下の処理を行う。
【００６３】
公開鍵生成部２１４は、公開鍵値算出部２１３により算出されたＨ鍵値群とＨ’鍵値群とを含んだ公開鍵ＰＫを生成する。
【００６４】
マスタ秘密鍵生成部２１５は、マスタ秘密鍵生成処理を行う。
例えば、マスタ秘密鍵生成部２１５は、マスタ秘密鍵生成処理において以下の処理を行う。
【００６５】
マスタ秘密鍵生成部２１５は、セットアップ前処理部２１２により選択されたＬ個の鍵値ｈをｈ鍵値群として含んだマスタ秘密鍵ＭＳＫを生成する。
【００６６】
セットアップ出力部２１６は、セットアップ出力処理を行う。
例えば、セットアップ出力部２１６は、公開鍵生成部２１４により生成された公開鍵ＰＫとマスタ秘密鍵生成部２１５により生成されたマスタ秘密鍵ＭＳＫとを出力する。
【００６７】
鍵生成処理部２２０は、例えば、階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ秘密鍵ＳＫを生成する。
【００６８】
鍵生成処理部２２０は、鍵生成入力部２２１、鍵生成前処理部２２２、ユーザ秘密鍵値算出部２２３およびユーザ秘密鍵生成部２２４を備える。
【００６９】
鍵生成入力部２２１は、鍵生成入力処理を行う。
例えば、鍵生成入力部２２１は、鍵生成入力処理において以下の処理を行う。
【００７０】
鍵生成入力部２２１は、特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを入力する。
鍵生成入力部２２１は、ｋ個の階層に対応付けられたｋ個の鍵値ｈを含むｈ鍵値群とｋ個の階層に対応付けられたｋ個の鍵値ｈ’を含むｈ’鍵値群とを含むマスタ秘密鍵ＭＳＫを入力する。
【００７１】
鍵生成前処理部２２２は、鍵生成前処理を行う。
例えば、鍵生成前処理部２２２は、ユーザ識別子ＩＤに含まれる階層識別子が文字列である場合、階層識別子を文字列から整数値に変換する。
【００７２】
ユーザ秘密鍵値算出部２２３は、ユーザ秘密鍵値算出処理を行う。
例えば、ユーザ秘密鍵値算出部２２３は、ユーザ秘密鍵値算出処理において以下の処理を行う。
【００７３】
ユーザ秘密鍵値算出部２２３は、鍵生成入力部２２１が入力したユーザ識別子ＩＤとマスタ秘密鍵ＭＳＫとを用いて、暗号文データＣＴの復号に用いる鍵値ａ０を算出する。
【００７４】
ユーザ秘密鍵生成部２２４は、ユーザ秘密鍵生成処理を行う。
例えば、ユーザ秘密鍵生成部２２４は、ユーザ秘密鍵生成処理において以下の処理を行う。
【００７５】
ユーザ秘密鍵生成部２２４は、ユーザ秘密鍵値算出部２２３により算出された鍵値ａ０を含んだユーザ秘密鍵ＳＫを生成し、生成したユーザ秘密鍵ＳＫを出力する。
【００７６】
図７は、実施の形態１における復号装置３００の概要図である。
実施の形態１における復号装置３００の概要について、図７に基づいて説明する。
【００７７】
復号装置３００は、復号処理部３１０と鍵委譲処理部３２０と復号記憶部３９０（鍵委譲記憶部の一例）とを備える。
但し、最下層の復号装置３００（例えば、社員用の復号装置３００）には鍵委譲処理部３２０を備えなくても構わない。
【００７８】
復号処理部３１０は、公開鍵ＰＫとユーザｉのユーザ秘密鍵ＳＫ（ＩＤｉ）とユーザｉ用に生成された暗号文データＣＴとユーザｉのユーザ識別子ＩＤｉとを入力し、暗号文データＣＴを復号して平文データＭを生成し、生成した平文データＭを出力する。
【００７９】
鍵委譲処理部３２０は、公開鍵ＰＫとユーザｉのユーザ秘密鍵ＳＫ（ＩＤｉ）とユーザｉの一つ下の階層に属するユーザｊのユーザ識別子ＩＤｊとを入力し、ユーザｊの秘密鍵ＳＫ（ＩＤｊ）を生成し、生成したユーザｊの秘密鍵ＳＫ（ＩＤｊ）を出力する。
【００８０】
復号記憶部３９０は、復号装置３００で使用するデータを記憶する記憶部である。
例えば、公開鍵ＰＫ、ユーザ秘密鍵ＳＫ（ＩＤｘ）、暗号文データＣＴ、ユーザ識別子ＩＤｘ、平文データＭは、復号記憶部３９０に記憶されるデータの一例である。
【００８１】
図８は、実施の形態１における復号装置３００の機能構成図である。
実施の形態１における復号装置３００の機能構成について、図８に基づいて説明する。
【００８２】
復号装置３００（鍵委譲装置の一例）は、前述の通り、復号処理部３１０と鍵委譲処理部３２０と復号記憶部３９０（鍵委譲記憶部の一例）とを備える。
【００８３】
復号処理部３１０は、復号入力部３１１、復号前処理部３１２および復号部３１３を備える。
【００８４】
復号入力部３１１は、復号入力処理を行う。
例えば、復号入力部３１１は、復号入力処理において以下の処理を行う。
【００８５】
復号入力部３１１は、暗号文データＣＴとユーザ識別子ＩＤとを入力する。
暗号文ＣＴは、平文データＭを暗号化した平文暗号値Ｃ０と特定のワイルドカード暗号値Ｃ１と特定の識別暗号値Ｃ３とワイルドカード階層値Ｗとを含む。ワイルドカード階層値Ｗは、パターンＰに含まれるパターン値がワイルドカード値である階層を示す。
【００８６】
復号前処理部３１２は、復号前処理を行う。
例えば、復号前処理部３１２は、ユーザ識別子ＩＤに含まれる階層識別子が文字列である場合、階層識別子を文字列から整数値に変換する。
【００８７】
復号部３１３は、復号処理を行う。
例えば、復号部３１３は、復号処理において以下の処理を行う。
【００８８】
復号部３１３は、復号入力部３１１が入力した暗号文データＣＴに基づいて、復号部３１３が入力したユーザ識別子ＩＤから前記ワイルドカード階層値Ｗによって示される階層の階層識別子をワイルドカード識別子として抽出する。
復号部３１３は、抽出したワイルドカード識別子と前記暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて、前記暗号文データＣＴに含まれる平文暗号値Ｃ０を復号する。
復号部３１３は、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する。
【００８９】
鍵委譲処理部３２０は、階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属するユーザｊのユーザ秘密鍵ＳＫｊを生成する。
【００９０】
鍵委譲処理部３２０は、鍵委譲入力部３２１、鍵委譲前処理部３２２、委譲鍵値算出部３２３および委譲鍵生成部３２４を備える。
【００９１】
鍵委譲入力部３２１は、鍵委譲入力処理を行う。
例えば、鍵委譲入力部３２１は、鍵委譲入力処理において以下の処理を行う。
【００９２】
鍵委譲入力部３２１は、ユーザｊのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤｊを入力する。
鍵委譲入力部３２１は、第ｋ−１階層に属するユーザｉのユーザ秘密鍵ＳＫｉであって暗号文データＣＴの復号に用いる鍵値ａ０を含んだユーザ秘密鍵ＳＫｉを入力する。
【００９３】
鍵委譲前処理部３２２は、鍵委譲前処理を行う。
例えば、鍵委譲前処理部３２２は、ユーザ識別子ＩＤに含まれる階層識別子が文字列である場合、階層識別子を文字列から整数値に変換する。
【００９４】
委譲鍵値算出部３２３は、委譲鍵値算出処理を行う。
例えば、委譲鍵値算出部３２３は、委譲鍵値算出処理において以下の処理を行う。
【００９５】
委譲鍵値算出部３２３は、鍵委譲入力部３２１が入力したユーザ識別子ＩＤｊとユーザ秘密鍵ＳＫｉとを用いて、前記暗号文データＣＴの復号に用いる鍵値ｘ０を算出する。
【００９６】
委譲鍵生成部３２４は、委譲鍵生成処理を行う。
例えば、委譲鍵生成部３２４は、委譲鍵生成処理において以下の処理を行う。
【００９７】
委譲鍵生成部３２４は、委譲鍵値算出部３２３により算出された鍵値ｘ０を含んだユーザ秘密鍵ＳＫｊを生成し、生成したユーザ秘密鍵ＳＫｊを出力する。
【００９８】
図９は、実施の形態１における暗号化装置４００の概要図である。
実施の形態１における暗号化装置４００の概要について、図９に基づいて説明する。
【００９９】
暗号化装置４００は、暗号処理部４１０と暗号化記憶部４９０とを備える。
【０１００】
暗号処理部４１０は、公開鍵ＰＫと（個人または）階層ｉ用のパターンＰｉと平文データＭとを入力し、平文データＭを暗号化して（個人または）階層ｉ用の暗号文データＣＴを生成し、生成した暗号文データＣＴを出力する。
【０１０１】
暗号化記憶部４９０は、暗号化装置４００で使用するデータを記憶する記憶部である。
例えば、公開鍵ＰＫ、パターンＰｉ、平文データＭ、暗号文データＣＴは、暗号化記憶部４９０に記憶されるデータの一例である。
【０１０２】
図１０は、実施の形態１における暗号化装置４００の機能構成図である。
実施の形態１における暗号化装置４００の機能構成について、図１０に基づいて説明する。
【０１０３】
暗号化装置４００は、前述の通り、暗号処理部４１０と暗号化記憶部４９０とを備える。
【０１０４】
暗号処理部４１０は、暗号化入力部４１１、暗号化前処理部４１２、暗号値算出部４１３および暗号文生成部４１４を備える。
【０１０５】
暗号化入力部４１１は、暗号化入力処理を行う。
例えば、暗号化入力部４１１は、暗号化入力処理において以下の処理を行う。
【０１０６】
暗号化入力部４１１は、暗号化する平文データＭを入力する。
暗号化入力部４１１は、ｋ個（ｋは２以上の特定の整数）の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力する。
暗号化入力部４１１は、階層を識別する階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力する。
【０１０７】
暗号化前処理部４１２は、暗号化前処理を行う。
例えば、暗号化前処理部４１２は、パターンＰに含まれるパターン値（例えば、階層識別子）が文字列である場合、パターン値を文字列から整数値に変換する。
【０１０８】
暗号値算出部４１３は、暗号値算出処理を行う。
例えば、暗号値算出部４１３は、暗号値算出処理において以下の処理を行う。
【０１０９】
暗号値算出部４１３は、暗号化入力部４１１が入力した平文データＭを暗号化して平文暗号値Ｃ０を算出する。
暗号値算出部４１３は、暗号化入力部４１１が入力したパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定する。
暗号値算出部４１３は、暗号化入力部４１１が入力した公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出する。
暗号値算出部４１３は、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出する。
暗号値算出部４１３は、前記パターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定する。
暗号値算出部４１３は、前記公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出する。
暗号値算出部４１３は、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出する。
【０１１０】
暗号文生成部４１４は、暗号文生成処理を行う。
例えば、暗号文生成部４１４は、暗号文生成処理において以下の処理を行う。
【０１１１】
暗号文生成部４１４は、暗号値算出部４１３により算出された平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを生成する。
暗号文生成部４１４は、生成した暗号文データＣＴを出力する。
【０１１２】
次に、階層型ＩＤベース暗号システム１００を構成する各装置（図１参照）の処理方法について説明する。
【０１１３】
図１１は、実施の形態１におけるセットアップ装置２００によるセットアップ方法を示すフローチャートである。
セットアップ装置２００のセットアップ処理部２１０が実行するセットアップ方法の処理の流れについて、図１１に基づいて説明する。
【０１１４】
Ｓ１１０において、セットアップ入力部２１１は、セキュリティパラメータλと階層数Ｌと入力装置またはセットアップ記憶部２９０から入力する。
Ｓ１１０の後、Ｓ１２０に進む。
【０１１５】
Ｓ１２０において、セットアップ前処理部２１２は、セキュリティパラメータλに基づいて素数ｐ、ｑを生成（算出）し、生成した素数ｐ、ｑを乗算して合成数ｎ（＝ｐｑ）を算出する。
セットアップ前処理部２１２は、算出した合成数ｎと所定の写像ｅと、Ｓ１１０で入力されたセキュリティパラメータλと階層数Ｌとに基づいて群Ｇ、ＧＴを生成する。
【０１１６】
群Ｇ、ＧＴは合成数ｎを位数とする巡回群であり、ｎ個の要素値を含む。巡回群Ｇ、ＧＴは加法群と乗法群とのどちらであっても構わない。以下、巡回群Ｇ、ＧＴが乗法群であるものとして説明を続ける。
【０１１７】
写像ｅは２つの入力値から１つの出力値を得る関数であり、次の性質（ａ）（ｂ）を満たす。
【０１１８】
【数１】
2012098649.tif 000003
【０１１９】
性質（ａ）（ｂ）を満たす写像ｅをペアリングという。ペアリングｅは以下のように表すことができる。
【０１２０】
【数２】
2012098649.tif 000004
【０１２１】
ペアリングｅの演算を「ペアリング演算」という。
ペアリングｅによって定義される群Ｇ、ＧＴを「ペアリング群」という。
例えば、ペアリング群Ｇ、ＧＴとして、楕円曲線上の有理点から成る群Ｇと有限体上の群ＧＴとが挙げられる。
群Ｇと群ＧＴとのペアリングは対称ペアリングと非対称ペアリングとのどちらであっても構わない。以下、対称ペアリングを対象にして説明を続ける。非対称ペアリングを対象にする場合については、当業者であれば以下の説明から容易に理解し得ることである。
【０１２２】
素数ｐ、ｑの生成方法は、例えば、非特許文献４に開示されている。
ペアリング群Ｇ、ＧＴの生成方法は、例えば、非特許文献３に開示されている。
【０１２３】
Ｓ１２０の後、Ｓ１３０に進む。
【０１２４】
Ｓ１３０において、セットアップ前処理部２１２は、群Ｇを用いて群Ｇの一部を構成する部分群Ｇｐを生成する。部分群Ｇｐは素数ｐを位数としてｐ個の要素値を含む要素値群である。
セットアップ前処理部２１２は、式［ＳＵ１］に示すように、生成した部分群Ｇｐから複数の要素値をランダムに選択する。
【０１２５】
【数３】
2012098649.tif 000005
【０１２６】
Ｓ１３０の後、Ｓ１３１に進む。
【０１２７】
Ｓ１３１において、セットアップ前処理部２１２は、群Ｇを用いて群Ｇの一部を構成する部分群Ｇｑを生成する。部分群Ｇｑは素数ｑを位数としてｑ個の要素値を含む要素値群である。
セットアップ前処理部２１２は、式［ＳＵ２］に示すように、生成した部分群Ｇｑから複数の要素値をランダムに選択する。
【０１２８】
【数４】
2012098649.tif 000006
【０１２９】
Ｓ１３１の後、Ｓ１４０に進む。
【０１３０】
Ｓ１４０において、公開鍵値算出部２１３は、Ｓ１３０で選択された複数の要素値とＳ１３１で選択された複数の要素値とを用いて複数の公開鍵値を算出する。
以下に、複数の公開鍵値を算出する複数の算出式［ＳＵ３］を示す。
【０１３１】
【数５】
2012098649.tif 000007
【０１３２】
Ｓ１４０の後、Ｓ１５０に進む。
【０１３３】
Ｓ１５０において、公開鍵生成部２１４は、Ｓ１４０で算出された複数の公開鍵値を含んだ公開鍵ＰＫを生成する。
以下に、公開鍵ＰＫを表す式［ＳＵ４］を示す。
【０１３４】
【数６】
2012098649.tif 000008
【０１３５】
Ｓ１５０の後、Ｓ１６０に進む。
【０１３６】
Ｓ１６０において、マスタ秘密鍵生成部２１５は、Ｓ１３０で選択された複数の要素値をマスタ秘密鍵値として含んだマスタ秘密鍵ＭＳＫを生成する。
以下に、マスタ秘密鍵ＭＳＫを表す式［ＳＵ５］を示す。
【０１３７】
【数７】
2012098649.tif 000009
【０１３８】
Ｓ１６０の後、Ｓ１７０に進む。
【０１３９】
Ｓ１７０において、セットアップ出力部２１６は、Ｓ１５０で生成された公開鍵ＰＫとＳ１６０で生成されたマスタ秘密鍵ＭＳＫとをセットアップ記憶部２９０に記憶する。
また、セットアップ出力部２１６は、システム全体で使用できるように公開鍵ＰＫをシステムの共有サーバ（図示省略）に記憶する。但し、セットアップ出力部２１６は、公開鍵ＰＫを各復号装置３００および暗号化装置４００に送信しても構わない。
Ｓ１７０により、セットアップ方法の処理は終了する。
【０１４０】
図１２は、実施の形態１におけるセットアップ装置２００による鍵生成方法を示すフローチャートである。
セットアップ装置２００の鍵生成処理部２２０が実行する鍵生成方法の処理の流れについて、図１２に基づいて説明する。
【０１４１】
Ｓ２１０において、鍵生成入力部２２１は、セットアップ処理部２１０により生成された公開鍵ＰＫとマスタ秘密鍵ＭＳＫとをセットアップ記憶部２９０から入力する。
鍵生成入力部２２１は、特定のユーザｉに割り当てられたユーザ識別子ＩＤｉを入力装置またはセットアップ記憶部２９０から入力する。
Ｓ２１０の後、Ｓ２２０に進む。
【０１４２】
Ｓ２２０において、鍵生成前処理部２２２は、ユーザ識別子ＩＤｉを構成する要素を整数値群Ｚｎに含まれるいずれかの整数値に変換する。整数値群Ｚｎは、０からｎ−１までの整数値で構成される群である。図１１のＳ１２０で説明したように、ｎは素数ｐと素数ｑとの積であり、群Ｇの位数である。
【０１４３】
例えば、鍵生成前処理部２２２は、要素を表す２進数を１０進数の整数値に変換する。鍵生成前処理部２２２は、得られた１０進数の整数値を法ｎで剰余演算し、剰余値を整数値として求めてもよい。
また、鍵生成前処理部２２２は、ハッシュ関数に要素を代入して整数値を得てもよい。
また、要素と整数値とを対応付けた変換テーブルをセットアップ記憶部２９０に予め記憶しておき、鍵生成前処理部２２２が要素に対応する整数値をセットアップ記憶部２９０から取得しても構わない。
【０１４４】
但し、ユーザ識別子ＩＤｉを構成する全ての要素が整数値である場合、Ｓ２２０を実行する必要はない。また、ユーザ識別子ＩＤｉを構成する複数の要素のうち整数値で表す要素については、Ｓ２２０を実行しなくても構わない。
【０１４５】
Ｓ２２０の後、Ｓ２３０に進む。
【０１４６】
Ｓ２３０において、鍵生成前処理部２２２は、式［ＫＧ１］に示すように、整数値群Ｚｎ（０からｎ−１の整数値）から複数の整数値をランダムに選択する。
但し、条件式［ＫＧ１−１］を満たさない場合、鍵生成前処理部２２２は複数の整数値を選択し直す。
【０１４７】
【数８】
2012098649.tif 000010
【０１４８】
Ｓ２３０の後、Ｓ２４０に進む。
【０１４９】
Ｓ２４０において、鍵生成前処理部２２２は、ユーザ識別子ＩＤｉに含まれる複数の要素のうち空欄値「φ」以外の要素を判定する。
さらに、鍵生成前処理部２２２は、空欄値「φ」以外の要素に対応する階層の番号を「非空欄階層値Ｄ」として判定する。以下、空欄値「φ」以外の要素に対応する階層を「非空欄階層」という。
また、鍵生成前処理部２２２は、ユーザ識別子ＩＤｉに含まれる複数の要素のうち空欄値「φ」を示す要素を判定し、空欄値「φ」を示す要素に対応する階層の番号を「空欄階層値Ｎ」として判定する。以下、空欄値「φ」を示す要素に対応する階層を「空欄階層」という。
以下に、非空欄階層値Ｄを表す式［ＫＧ２］と空欄階層値Ｎを表す式［ＫＧ３］とを示す。
【０１５０】
【数９】
2012098649.tif 000011
【０１５１】
例えば、図３に示した経理課長のユーザ識別子ＩＤ３（総務部、経理課、φ、φ）の場合、非空欄階層値Ｄは「１」と「２」であり、空欄階層値Ｎは「３」と「４」である。
また、田中さんのユーザ識別子ＩＤ８（総務部、φ、φ、田中）の場合、非空欄階層値Ｄは「１」と「４」であり、空欄階層値Ｎは「２」と「３」である。
【０１５２】
Ｓ２４０の後、Ｓ２５０に進む。
【０１５３】
Ｓ２５０において、ユーザ秘密鍵値算出部２２３は、マスタ秘密鍵ＭＳＫとユーザ識別子ＩＤｉとユーザ識別子ＩＤｉの非空欄階層値ＤとＳ２３０で選択された整数値とを用いて、複数の復号鍵値を算出する。
ここで、ユーザｉの属する階層の番号を「Ｋ」とする。
以下に、複数の復号鍵値を算出する複数の算出式［ＫＧ４］を示す。
【０１５４】
【数１０】
2012098649.tif 000012
【０１５５】
Ｓ２５０の後、Ｓ２５１に進む。
【０１５６】
Ｓ２５１において、ユーザ秘密鍵値算出部２２３は、Ｓ２５０と同様に複数の撹乱鍵値（Ａ）を算出する。
以下に、複数の撹乱鍵値（Ａ）を算出する複数の算出式［ＫＧ５］を示す。
【０１５７】
【数１１】
2012098649.tif 000013
【０１５８】
Ｓ２５１の後、Ｓ２５２に進む。
【０１５９】
Ｓ２５２において、ユーザ秘密鍵値算出部２２３は、Ｓ２５１と同様に複数の撹乱鍵値（Ｂ）を算出する。
以下に、複数の撹乱鍵値（Ｂ）を算出する複数の算出式［ＫＧ６］を示す。
【０１６０】
【数１２】
2012098649.tif 000014
【０１６１】
Ｓ２５２の後、Ｓ２６０に進む。
【０１６２】
Ｓ２６０において、ユーザ秘密鍵生成部２２４は、Ｓ２５０で算出された複数の復号鍵値を含んだ復号鍵ｄｋを生成する。
さらに、ユーザ秘密鍵生成部２２４は、Ｓ２５１で算出された複数の撹乱鍵値（Ａ）とＳ２５２で算出された複数の撹乱鍵値（Ｂ）とを含んだ撹乱鍵ｒｋを生成する。
以下に、復号鍵ｄｋを表す式［ＫＧ７］と撹乱鍵ｒｋを表す式［ＫＧ８］とを示す。
【０１６３】
【数１３】
2012098649.tif 000015
【０１６４】
Ｓ２６０の後、Ｓ２７０に進む。
【０１６５】
Ｓ２７０において、ユーザ秘密鍵生成部２２４は、Ｓ２６０で生成した復号鍵ｄｋと撹乱鍵ｒｋとを用いてユーザｉのユーザ秘密鍵ＳＫを生成する。
そして、ユーザ秘密鍵生成部２２４は、生成したユーザ秘密鍵ＳＫを出力する。例えば、ユーザ秘密鍵生成部２２４は、生成したユーザ秘密鍵ＳＫをユーザｉの復号装置３００へ送信する。
以下に、ユーザｉのユーザ秘密鍵ＳＫを表す式［ＫＧ９］を示す。
【０１６６】
【数１４】
2012098649.tif 000016
【０１６７】
Ｓ２７０により、鍵生成方法の処理は終了する。
【０１６８】
ユーザ秘密鍵ＳＫに含まれる復号鍵ｄｋは、復号装置３００が暗号文データＣＴの復号に用いるデータであり、ユーザ秘密鍵ＳＫに含まれる撹乱鍵ｒｋは、復号装置３００が鍵委譲に用いるデータである。
鍵委譲とは、復号装置３００が自己のユーザ秘密鍵ＳＫを用いて下位層に属するユーザのユーザ秘密鍵を生成する処理である。
【０１６９】
図１３は、実施の形態１における復号装置３００による鍵委譲方法を示すフローチャートである。
復号装置３００の鍵委譲処理部３２０が実行する鍵委譲方法の処理の流れについて、図１３に基づいて説明する。
【０１７０】
Ｓ３１０において、鍵委譲入力部３２１は、公開鍵ＰＫを入力装置、共有サーバ（図示省略）または復号記憶部３９０から入力する。
鍵委譲入力部３２１は、ユーザｉのユーザ秘密鍵ＳＫ（ＩＤｉ）を入力装置または復号記憶部３９０から入力する。ユーザｉは、例えば、この復号装置を使用するユーザである。
鍵委譲入力部３２１は、ユーザｊのユーザ識別子ＩＤｊを入力装置または復号記憶部３９０から入力する。ユーザｊは、ユーザｉの一つ下の階層に属するユーザあってユーザ秘密鍵の委譲先のユーザである。
以下、ユーザｊ（委譲先）の属する階層の番号を「ｋ」とし、ユーザｉの属する階層の番号を「ｋ−１」とする。
Ｓ３１０の後、Ｓ３２０に進む。
【０１７１】
Ｓ３２０において、鍵委譲前処理部３２２は、ユーザ識別子ＩＤｊに含まれる要素Ｉｋを整数値群Ｚｎ（０からｎ−１の整数値）に含まれるいずれかの整数値に変換する。
要素Ｉｋは、ユーザ識別子ＩＤｊに含まれる複数の要素のうちｋ番目の要素、つまり、ユーザｊ（委譲先）が属する第ｋ階層に対応する要素である。
変換方法は、Ｓ２２０（図１２参照）と同様である。
Ｓ３２０の後、Ｓ３３０に進む。
【０１７２】
Ｓ３３０において、鍵委譲前処理部３２２は、式［ＫＴ１］に示すように、整数値群Ｚｎから複数の整数値をランダムに選択する。
但し、条件式［ＫＴ１−１］を満たさない場合、鍵委譲前処理部３２２は複数の整数値を選択し直す。
【０１７３】
【数１５】
2012098649.tif 000017
【０１７４】
Ｓ３３０の後、Ｓ３４０に進む。
【０１７５】
Ｓ３４０において、委譲鍵値算出部３２３は、ユーザ秘密鍵ＳＫ（ＩＤｉ）に含まれるユーザｉの復号鍵ｄｋ（ＩＤｉ）とユーザｊのユーザ識別子ＩＤｊに含まれる要素Ｉｋとを用いて、複数の作業値（ａ）を算出する。
以下に、複数の作業値（ａ）を算出する算出式［ＫＴ２］を示す。
【０１７６】
【数１６】
2012098649.tif 000018
【０１７７】
Ｓ３４０の後、Ｓ３４１に進む。
【０１７８】
Ｓ３４１において、委譲鍵値算出部３２３は、ユーザ秘密鍵ＳＫ（ＩＤｉ）に含まれるユーザｉの撹乱鍵ｒｋ（ＩＤｉ）とユーザｊのユーザ識別子ＩＤｊに含まれる要素Ｉｋとを用いて、複数の作業値（ｂ）を算出する。
以下に、複数の作業値（ｂ）を算出する算出式［ＫＴ３］を示す。
【０１７９】
【数１７】
2012098649.tif 000019
【０１８０】
Ｓ３４１の後、Ｓ３４２に進む。
【０１８１】
Ｓ３４２において、委譲鍵値算出部３２３は、Ｓ３４１と同様に複数の作業値（ｃ）を算出する。
以下に、複数の作業値（ｃ）を算出する算出式［ＫＴ４］を示す。
【０１８２】
【数１８】
2012098649.tif 000020
【０１８３】
Ｓ３４２の後、Ｓ３５０に進む。
【０１８４】
Ｓ３５０において、委譲鍵値算出部３２３は、Ｓ３４０からＳ３４２で算出した作業値（ａ）−（ｃ）とＳ３３０で選択された整数値とを用いて、複数の復号鍵値を算出する。
以下に、複数の復号鍵値を算出する算出式［ＫＴ５］を示す。
【０１８５】
【数１９】
2012098649.tif 000021
【０１８６】
Ｓ３５０の後、Ｓ３５１に進む。
【０１８７】
Ｓ３５１において、委譲鍵値算出部３２３は、Ｓ３４１で算出した作業値（ｂ）とＳ３４２で算出した作業値（ｃ）とＳ３３０で選択された整数値とを用いて、複数の撹乱鍵値（Ａ）を算出する。
以下に、複数の撹乱鍵値（Ａ）を算出する算出式［ＫＴ６］を示す。
【０１８８】
【数２０】
2012098649.tif 000022
【０１８９】
Ｓ３５１の後、Ｓ３５２に進む。
【０１９０】
Ｓ３５２において、委譲鍵値算出部３２３は、Ｓ３５１と同様に複数の撹乱鍵値（Ｂ）を算出する。
以下に、複数の撹乱鍵値（Ｂ）を算出する算出式［ＫＴ７］を示す。
【０１９１】
【数２１】
2012098649.tif 000023
【０１９２】
Ｓ３５２の後、Ｓ３６０に進む。
【０１９３】
Ｓ３６０において、委譲鍵生成部３２４は、Ｓ３５０で算出された複数の復号鍵値を用いて、ユーザｊの復号鍵ｄｋ（ＩＤｊ）を生成する。
さらに、委譲鍵生成部３２４は、Ｓ３５１で算出された複数の撹乱鍵値（Ａ）とＳ３５２で算出された複数の撹乱鍵値（Ｂ）とを用いて、撹乱鍵ｒｋ（ＩＤｊ）を生成する。
以下に、ユーザｊの復号鍵ｄｋ（ＩＤｊ）を表す式［ＫＴ８］とユーザｊの撹乱鍵ｒｋ（ＩＤｊ）を表す式［ＫＴ９］とを示す。
【０１９４】
【数２２】
2012098649.tif 000024
【０１９５】
Ｓ３６０の後、Ｓ３７０に進む。
【０１９６】
Ｓ３７０において、委譲鍵生成部３２４は、Ｓ３６０で生成した復号鍵ｄｋ（ＩＤｊ）と撹乱鍵ｒｋ（ＩＤｊ）とを用いてユーザｊのユーザ秘密鍵ＳＫ（ＩＤｊ）を生成し、生成したユーザ秘密鍵ＳＫ（ＩＤｊ）を復号記憶部３９０に記憶する。
また、委譲鍵生成部３２４は、生成したユーザ秘密鍵ＳＫ（ＩＤｊ）を出力する。例えば、委譲鍵生成部３２４は、生成したユーザ秘密鍵ＳＫ（ＩＤｊ）をユーザｊの復号装置３００へ送信する。
以下に、ユーザｊのユーザ秘密鍵ＳＫ（ＩＤｊ）を表す式［ＫＴ１０］を示す。
【０１９７】
【数２３】
2012098649.tif 000025
【０１９８】
Ｓ３７０により、鍵委譲方法の処理は終了する。
但し、ユーザｊの一つ下の階層に属するユーザｊ２のユーザ秘密鍵ＳＫ（ＩＤｊ２）を生成する場合には、ユーザｉをユーザｊに置き換えると共にユーザｊをユーザｊ２に置き換えて鍵委譲方法の処理（Ｓ３１０−Ｓ３７０）を繰り返す。
【０１９９】
図１２で説明した鍵生成方法と図１３で説明した鍵委譲方法とで見掛け上の処理は異なるが、鍵生成方法と鍵委譲方法とは同一ユーザについて同一のユーザ秘密鍵ＳＫを生成することができる。
そのため、鍵生成方法と鍵委譲方法とのいずれかを用いて、特定のユーザのユーザ秘密鍵ＳＫを生成すればよい。
【０２００】
図１４は、実施の形態１における暗号化装置４００による暗号化方法を示すフローチャートである。
暗号化装置４００の暗号処理部４１０が実行する暗号化方法の処理の流れについて、図１４に基づいて説明する。
【０２０１】
Ｓ４１０において、暗号化入力部４１１は、公開鍵ＰＫを入力装置、共有サーバ（図示省略）または復号記憶部３９０から入力する。
暗号化入力部４１１は、ユーザｉ用のパターンＰｉを入力装置、共有サーバまたは復号記憶部３９０から入力する。ユーザｉは、暗号文データＣＴを復号できる一人のユーザまたは複数のユーザを意味する。
暗号化入力部４１１は、平文データＭを入力装置または復号記憶部３９０から入力する。
Ｓ４１０の後、Ｓ４２０に進む。
【０２０２】
Ｓ４２０において、暗号化前処理部４１２は、パターンＰｉに含まれる要素を整数値群Ｚｎ（０からｎ−１の整数値）に含まれるいずれかの整数値に変換する。
変換方法は、Ｓ２２０（図１２参照）と同様である。
Ｓ４２０の後、Ｓ４２１に進む。
【０２０３】
Ｓ４２１において、暗号化前処理部４１２は、式［ＥＮ１］に示すように、整数値群Ｚｎから整数値ρをランダムに選択する。
【０２０４】
【数２４】
2012098649.tif 000026
【０２０５】
Ｓ４２１の後、Ｓ４２２に進む。
【０２０６】
Ｓ４２２において、暗号化前処理部４１２は、パターンＰｉに含まれる複数の要素のうちワイルドカード値「＊」を示す要素を判定する。
さらに、暗号化前処理部４１２は、ワイルドカード値「＊」を示す要素に対応する階層の番号を「ワイルドカード階層値Ｗ」として判定する。以下、ワイルドカード値「＊」を示す要素に対応する階層を「ワイルドカード階層」という。
また、暗号化前処理部４１２は、パターンＰｉに含まれる複数の要素のうち空欄値「φ」を示す要素を判定し、空欄値「φ」を示す要素に対応する階層の番号を「空欄階層値Ｎ」として判定する。以下、空欄値「φ」を示す要素に対応する階層を「空欄階層」という。
また、暗号化前処理部４１２は、パターンＰｉに含まれる複数の要素のうちワイルドカード値「＊」および空欄値「φ」以外の要素を判定し、ワイルドカード値「＊」および空欄値「φ」以外の要素に対応する階層の番号を「識別階層値Ｄ」として判定する。以下、ワイルドカード値「＊」および空欄値「φ」以外の要素に対応する階層を「識別階層」という。
以下に、ワイルドカード階層値Ｗを表す式［ＥＮ２］と空欄階層値Ｎを表す式［ＥＮ３］と識別階層値Ｄを表す式［ＥＮ４］とを示す。
【０２０７】
【数２５】
2012098649.tif 000027
【０２０８】
例えば、図４に示したパターンＰ５（総務部、＊、φ、φ）の場合、ワイルドカード階層値Ｗは「２」であり、空欄階層値Ｎは「３」と「４」であり、識別階層値Ｄは「１」である。
また、パターンＰ８（総務部、φ、φ、田中）の場合、ワイルドカード階層値Ｗは無く、空欄階層値Ｎは「２」と「３」であり、識別階層値Ｄは「１」と「４」である。
【０２０９】
Ｓ４２２の後、Ｓ４２３に進む。
【０２１０】
Ｓ４２３において、暗号化前処理部４１２は、ワイルドカード階層値Ｗに基づいて整数値群Ｚｎから複数の整数値をランダムに選択し、選択した整数値毎に整数値を公開鍵ＰＫに含まれる公開鍵値ｇｑにべき乗する。
この処理は、式［ＥＮ５］に示すように、素数ｑを位数とする群Ｇｑから複数の要素値をランダムに選択することと等しい。
【０２１１】
【数２６】
2012098649.tif 000028
【０２１２】
Ｓ４２３の後、Ｓ４３０に進む。
【０２１３】
Ｓ４３０において、暗号値算出部４１３は、公開鍵ＰＫとパターンＰｉと平文データＭとＳ４２１で選択された整数値ρとＳ４２３で算出された複数の整数値とを用いて、複数の暗号値を算出する。
以下に、複数の暗号値を算出する複数の算出式［ＥＮ６］を示す。
【０２１４】
【数２７】
2012098649.tif 000029
【０２１５】
Ｓ４３０の後、Ｓ４４０に進む。
【０２１６】
Ｓ４４０において、暗号文生成部４１４は、Ｓ４２２で判定されたワイルドカード階層値ＷとＳ４３０で算出された複数の暗号値とを用いてユーザｉ用の暗号文データＣＴを生成し、生成した暗号文データＣＴを暗号化記憶部４９０に記憶する。
以下に、暗号文ＣＴを表す式［ＥＮ７］を示す。
【０２１７】
【数２８】
2012098649.tif 000030
【０２１８】
また、暗号文生成部４１４は、生成した暗号文データＣＴを出力する。例えば、暗号文生成部４１４は、暗号文データＣＴを共有サーバ（図示省略）に記憶する。
Ｓ４４０により、暗号化方法の処理は終了する。
【０２１９】
上記の暗号化方法において、平文データＭはペアリング群ＧＴ（図１１のＳ１２０参照）の要素であるものとする。
但し、平文データＭがペアリング群ＧＴの要素でない場合、ハイブリッド暗号方式を用いればよい。ハイブリッド暗号方式において、平文データＭはセッション鍵を用いて共通鍵暗号方式で暗号化する。そして、平文データＭをセッション鍵に置き換えて上記暗号化方法の処理を実行する。
【０２２０】
図１５は、実施の形態１における復号装置３００による復号方法を示すフローチャートである。
復号装置３００の復号処理部３１０が実行する復号方法の処理の流れについて、図１５に基づいて説明する。
【０２２１】
Ｓ５１０において、復号入力部３１１は、公開鍵ＰＫと暗号文データＣＴとを入力装置、共有サーバ（図示省略）または復号記憶部３９０から入力する。
復号入力部３１１は、ユーザｉのユーザ秘密鍵ＳＫ（ＩＤｉ）とユーザ識別子ＩＤｉとを入力装置または復号記憶部３９０から入力する。ユーザｉは、暗号文データＣＴを復号するユーザであって、この復号装置３００を使用するユーザである。
Ｓ５１０の後、Ｓ５２０に進む。
【０２２２】
Ｓ５２０において、復号前処理部３１２は、ユーザ識別子ＩＤｉに含まれる要素を整数値群Ｚｎ（０からｎ−１の整数値）に含まれるいずれかの整数値に変換する。
変換方法は、Ｓ２２０（図１２参照）と同様である。
Ｓ５２０の後、Ｓ５２１に進む。
【０２２３】
Ｓ５２１において、復号前処理部３１２は、ユーザ識別子ＩＤｉに基づいて非空欄階層値Ｄを判定する。
判定方法は、Ｓ２４０（図１２参照）と同様である。
Ｓ５２１の後、Ｓ５３０に進む。
【０２２４】
Ｓ５３０において、復号部３１３は、暗号文データＣＴとユーザ識別子ＩＤｉとＳ５２１で判定した非空欄階層値Ｄとを用いて、複数の作業値を算出する。
以下に、複数の作業値を算出する複数の算出式［ＤＥ１］を示す。
【０２２５】
【数２９】
2012098649.tif 000031
【０２２６】
Ｓ５３０の後、Ｓ５４０に進む。
【０２２７】
Ｓ５４０において、復号部３１３は、暗号文データＣＴとユーザ秘密鍵ＳＫ（ＩＤｉ）と公開鍵ＰＫに含まれる写像の関数ｅとＳ５３０で算出した複数の作業値とを用いて平文データＭを算出する。
以下に、平文データＭを算出する算出式［ＤＥ２］を示す。
【０２２８】
【数３０】
2012098649.tif 000032
【０２２９】
復号部３１３は、算出した平文データＭを出力する。例えば、復号部３１３は、平文データＭを表示装置に表示する。
Ｓ５４０により、復号方法は終了する。
【０２３０】
階層型ＩＤベース暗号システム１００において、平文データＭの暗号化に使用されたパターンＰに該当する正当なユーザであれば、自分のユーザ秘密鍵ＳＫとユーザ識別子ＩＤとを用いて暗号化データＣＴを復号することができる。
パターンＰに含まれる複数の要素ｐのうちユーザ識別子ＩＤの非空欄階層（≠φ）に対応する要素ｐｊがユーザ識別子ＩＤの要素Ｉｊまたはワイルドカード値「＊」であり、復号処理（図１５のＳ５３０）でワイルドカード値「＊」がユーザ識別子ＩＤの要素Ｉｊで「焼き直し」されるからである。
【０２３１】
一方、パターンＰに該当するユーザ以外の不正なユーザは、自分のユーザ秘密鍵ＳＫとユーザ識別子ＩＤとを用いて暗号化データＣＴを復号することができない。
復号処理でワイルドカード値「＊」が不正なユーザ識別子ＩＤの要素Ｉｊで「焼き直し」されるからである。
【０２３２】
以下に、暗号文データＣＴを復号して得られる平文データＭと暗号化する前の平文データＭとの関係式を示す。
【０２３３】
【数３１】
2012098649.tif 000033
【０２３４】
一行目の式は、上記式［ＤＥ２］（図１５のＳ５４０参照）である。
二行目の式は、一行目の右辺を上記式「ＤＥ１」（図１５のＳ５３０参照）に基づいて展開した式である。
三行目の式は、二行目の式を以下に示すペアリング群の（性質１）に基づいて展開した式である。
四行目の式は、三行目の式の分母を分解した式である。
そして、四行目の式の分母と分子とで共通項を消去することにより平文データＭが得られる。
【０２３５】
以下に、ペアリング群の性質（１）を示す。
【０２３６】
【数３２】
2012098649.tif 000034
【０２３７】
階層型ＩＤベース暗号システム１００は、暗号文の匿名性を確保することができる。なお、ここでいう匿名性とは、非特許文献５のＡＮＯＮ−ｓＩＤで定義されるような安全性のことをいう。言い換えれば、暗号文からワイルドカード箇所を除く要素ｐｊすなわちユーザ識別子に関する情報が漏洩しないという性質である。
【０２３８】
また、暗号文の秘匿性を確保することができる。なお、ここでいう秘匿性とは、非特許文献５のＩＮＤ−ｓＩＤで定義されるような安全性のことをいう。言い換えれば、暗号文から平文に関する情報が漏洩しないという性質である。
【０２３９】
上記の匿名性および秘匿性については、暗号分野で一般的なシミュレーションベースの安全性証明によって示される。その際の数論仮定は、非特許文献５に記載の仮定と同じである。当業者であればその安全性について理解でき、必要であれば安全性証明を再現できるものと考える。
【０２４０】
本実施の形態では対称ペアリングを用いて構成する方法を説明したが、これを非対称ペアリングを用いる構成に拡張することは、当業者であれば容易に理解し得ることである。
【０２４１】
本実施の形態によれば、ワイルドカード対応の匿名性階層型ＩＤベース暗号方式を実現することができる。すなわち、階層内のある層に属する全てのユーザに対してユーザ毎に暗号文を生成する必要がなく、１つの暗号文を生成すればよい。
これにより、暗号文のサイズ（数）を低減することができる。
【０２４２】
さらに、復号演算（図１５のＳ５４０参照）において、ペアリングｅの演算回数を階層数に比例した回数ではなく、一定回数（具体的には３回）にすることができる。
これは、暗号文の構成要素の中で階層数に比例する要素を除去したためである。
これにより、大企業や官公庁のように大きな階層を持つ組織においても高速な復号演算を実現することができる。
【０２４３】
さらに、中間の階層に対応付けてユーザ識別子に空欄「φ」をおくことができる。
これにより、図２に示した田中さんのように通常の階層構造から外れるようなユーザにも柔軟に対応することができる。
つまり、特異な階層構造にも柔軟に対応できるという効果がある。
【０２４４】
実施の形態において、セットアップ装置２００は、セットアップ装置（セットアップ処理部２１０）と鍵生成装置（鍵生成処理部２２０）とに分割しても構わない。
また、復号装置３００は、復号装置（復号処理部３１０）と鍵委譲装置（鍵委譲処理部３２０）とに分割しても構わない。
【０２４５】
図１６は、実施の形態における階層型ＩＤベース暗号システム１００のハードウェア資源の一例を示す図である。
図１６において、セットアップ装置２００、復号装置３００、暗号化装置４００および検索装置５００（実施の形態３参照）は、ＣＰＵ９０１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えている。ＣＰＵ９０１は、バス９０２を介してＲＯＭ９０３、ＲＡＭ９０４、通信ボード９０５、ディスプレイ装置９１１、キーボード９１２、マウス９１３、ドライブ装置９１４、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。ドライブ装置９１４は、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）などの記憶媒体を読み書きする装置である。
【０２４６】
通信ボード９０５は、有線または無線で、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、電話回線などの通信網に接続している。
【０２４７】
磁気ディスク装置９２０には、ＯＳ９２１（オペレーティングシステム）、プログラム群９２２、ファイル群９２３が記憶されている。
【０２４８】
プログラム群９２２には、実施の形態において「〜部」として説明する機能を実行するプログラムが含まれる。プログラムは、ＣＰＵ９０１により読み出され実行される。すなわち、プログラムは、「〜部」としてコンピュータを機能させるものであり、また「〜部」の手順や方法をコンピュータに実行させるものである。
【０２４９】
ファイル群９２３には、実施の形態において説明する「〜部」で使用される各種データ（入力、出力、判定結果、計算結果、処理結果など）が含まれる。
【０２５０】
実施の形態において構成図およびフローチャートに含まれている矢印は主としてデータや信号の入出力を示す。
【０２５１】
実施の形態において「〜部」として説明するものは「〜回路」、「〜装置」、「〜機器」であってもよく、また「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ファームウェア、ソフトウェア、ハードウェアまたはこれらの組み合わせのいずれで実装されても構わない。
【０２５２】
実施の形態２．
合成数ｎ（＝ｐｑ）を位数とするペアリング群を用いる代わりに、素数ｐを位数とするペアリング群の直積を用いる形態について説明する。
以下、実施の形態１と異なる事項について主に説明する。説明を省略する事項については実施の形態１と同様である。
【０２５３】
以下、合成数を位数とするペアリング群のことを「合成数位数のペアリング群」といい、素数を位数とするペアリング群のことを「素数位数のペアリング群」という。
【０２５４】
素数位数ｐのペアリング群（非対称ペアリング群）の直積から成る直積群は、式（２−１）で定義される。
【０２５５】
【数３３】
2012098649.tif 000035
【０２５６】
直積群の一部を構成する部分群は式（２−２）で定義される。
【０２５７】
【数３４】
2012098649.tif 000036
【０２５８】
ペアリングｅは式（２−３）で定義される。
【０２５９】
【数３５】
2012098649.tif 000037
【０２６０】
上記の定義において性質（２）が成り立つ。
【０２６１】
【数３６】
2012098649.tif 000038
【０２６２】
この性質（２）は次のように確かめることができる。
【０２６３】
【数３７】
2012098649.tif 000039
【０２６４】
この性質（２）は、実施の形態１で説明した性質（１）と同等の性質である。
したがって、素数位数ｐのペアリング群の直積を用いて、階層型ＩＤベース暗号システム１００を構成することができる。
つまり、実施の形態１で説明した各群を以下のように上記の各群に置き換えることにより、階層型ＩＤベース暗号システム１００を構成することができる。
【０２６５】
【数３８】
2012098649.tif 000040
【０２６６】
ここでは、素数位数のペアリング群の直積を用いる場合の一例を示した。
但し、合成数位数のペアリング群を素数位数のペアリング群に変換する変換方法を用いても構わない。このような変換方法は、例えば、非特許文献６に開示されている。
【０２６７】
本実施の形態によれば、合成数位数のペアリング群ではなく、素数位数のペアリング群を用いてワイルドカード対応の匿名性階層型ＩＤベース暗号方式を実現することができる。
通常、素数位数のペアリング群は合成数位数のペアリング群よりも小さいビットサイズで同等の安全性を実現できる。
したがって、暗号文や秘密鍵のサイズを実施の形態１よりも小さくすることができる。
【０２６８】
また、ビットサイズが小さいほど群演算の時間は短縮される。つまり、演算速度を実施の形態１よりも向上させることができる。
【０２６９】
また、実施の形態１と同様に、復号演算で行うペアリング演算の回数を階層数に比例した回数ではなく、一定の回数にすることができる。
【０２７０】
実施の形態３．
実施の形態１、２で説明した「ワイルドカード対応の匿名性階層型ＩＤベース暗号方式」を応用して「グループ共有型公開鍵秘匿検索方式」について説明する。
以下、実施の形態１、２と異なる事項について主に説明する。説明を省略する事項については実施の形態１、２と同様である。
【０２７１】
図１７は、実施の形態３における公開鍵秘匿検索システム１１０の構成図である。
実施の形態３における公開鍵秘匿検索システム１１０の構成について、図１７に基づいて説明する。
【０２７２】
公開鍵秘匿検索システム１１０は、実施の形態１で説明した階層型ＩＤベース暗号システム１００の構成（図１参照）に加えて、検索装置５００を備える。
【０２７３】
検索装置５００は、暗号化装置４００により生成された複数の暗号文データＣＴを記憶した検索記憶部５９０（暗号文記憶部の一例）を備える。
【０２７４】
検索装置５００は、検索クエリＱＫを入力し、入力した検索クエリＱＫを用いて検索記憶部５９０を検索し、検索クエリＱＫに該当する暗号文データＣＴを出力する。
【０２７５】
復号装置３００は、検索装置５００によって検索された暗号文データＣＴを復号し、平文データＭを出力する。
【０２７６】
図１８は、実施の形態３における復号装置３００の概要図である。
実施の形態３における復号装置３００の概要について、図１８に基づいて説明する。
【０２７７】
復号装置３００は、実施の形態１で説明した構成（図７参照）に加えて、クエリ生成処理部３３０を備える。
【０２７８】
クエリ生成処理部３３０は、クエリ生成入力部、クエリ生成前処理部、クエリ鍵値算出部およびクエリ生成部（図示省略）を備える。
【０２７９】
クエリ生成処理部３３０は、公開鍵ＰＫとユーザｉのユーザ秘密鍵ＳＫ（ＩＤｉ）とユーザｉのユーザ識別子ＩＤｉとキーワードＫＷとを入力し、検索クエリＱＫ（ＩＤｉ，ＫＷ）を出力する。
【０２８０】
図１９は、実施の形態３における検索装置５００の概要図である。
実施の形態３における検索装置５００の概要について、図１９に基づいて説明する。
【０２８１】
検索装置５００は、検索処理部５１０と検索記憶部５９０とを備える。
【０２８２】
検索処理部５１０は、公開鍵ＰＫと検索クエリＱＫ（ＩＤｉ，ＫＷ）とを入力し、検索記憶部５９０に記憶された暗号文データＣＴを検索し、検索クエリＱＫ（ＩＤｉ，ＫＷ）に該当する暗号文データＣＴを出力する。
【０２８３】
検索記憶部５９０は、検索装置５００で使用するデータを記憶する記憶部である。
公開鍵ＰＫ、検索クエリＱＫ（ＩＤｉ，ＫＷ）、暗号文データＣＴは検索記憶部５９０に記憶されるデータの一例である。
【０２８４】
図２０は、実施の形態３における検索装置５００の機能構成図である。
実施の形態３における検索装置５００の機能構成について、図２０に基づいて説明する。
【０２８５】
検索装置５００は、前述の通り、検索処理部５１０と検索記憶部５９０とを備える。
【０２８６】
検索記憶部５９０は、複数の暗号文データＣＴと複数の暗号文データＣＴＷとを予め記憶する。
【０２８７】
暗号文データＣＴＷは、暗号化装置４００（図１０参照）によって以下のように生成される。
暗号値算出部４１３は、特定の平文データＭＷを暗号化して平文暗号値ＣＷ０を算出する。
暗号化入力部４１１は、前記暗号文データＣＴの検索に用いるキーワードＫＷを入力する。
暗号値算出部４１３は、前記パターンＰを含むと共に前記キーワードＫＷを第Ｋ＋１階層を識別する階層識別子として含むパターンＰＷを用いてワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを算出する。
暗号文生成部４１４は、算出された平文暗号値ＣＷ０とワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを含んだ暗号文データＣＴＷを生成し、生成した暗号文データＣＴＷを前記暗号文データＣＴに対応付けて出力する。
【０２８８】
図２０に戻り、検索装置５００の説明を続ける。
【０２８９】
検索処理部５１０は、検索クエリ入力部５１１と検索部５１２と検索結果出力部５１３とを備える。
【０２９０】
検索クエリ入力部５１１は、検索クエリ入力処理を行う。
例えば、検索クエリ入力部５１１は、検索クエリＱＫとワイルドカード階層値Ｗとを入力する。
【０２９１】
検索クエリＱＫは、復号装置３００（図１８参照）によって以下のように生成される。
クエリ生成処理部３３０のクエリ生成入力部（図示省略）は、前記ユーザ識別子ＩＤと前記キーワードＫＷとを入力する（クエリ生成入力）。
クエリ生成処理部３３０のクエリ鍵値算出部（図示省略）は、入力されたユーザ識別子ＩＤとキーワードＫＷとを用いて前記平文暗号値ＣＷ０の復号に用いる鍵値ａＷ０を算出する（クエリ鍵値算出処理）。
クエリ生成処理部３３０のクエリ生成部（図示省略）は、算出された鍵値ａＷ０と前記ユーザ識別子ＩＤとを含んだ検索クエリＱＫを生成し、生成した検索クエリＱＫを出力する（検索クエリ生成処理）。
【０２９２】
図２０に戻り、検索装置５００の説明を続ける。
【０２９３】
検索部５１２は、検索記憶部５９０から暗号文データＣＴＷを選択する。
検索部５１２は、入力されたワイルドカード階層値Ｗに基づいて入力された検索クエリＱＫに含まれるユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出する。
検索部５１２は、抽出したワイルドカード識別子と選択した暗号文データＣＴＷに含まれるワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３と入力された検索クエリＱＫに含まれる鍵値ａＷ０とを用いて、選択した暗号文データＣＴＷに含まれる平文暗号値ＣＷ０を復号する。
検索部５１２は、前記平文暗号値ＣＷ０を復号して得られた復号データが前記平文データＭＷと一致するか否かを判定する。
検索部５１２は、前記復号データが前記平文データＭＷと一致した場合、選択した暗号文データＣＴＷに対応する暗号文データＣＴを検索記憶部５９０から取得する。
【０２９４】
検索結果出力部５１３は、取得された暗号文データＣＴを入力された検索クエリＱＫに対する検索結果として出力する。
【０２９５】
図２１は、実施の形態３における階層型ＩＤベース暗号システム１００の階層構造の一例を示す図である。
図２２は、実施の形態３における階層型ＩＤベース暗号システム１００のパターンＰＷの一例を示す図である。
【０２９６】
図２１に示すように階層構造にはキーワード用の階層（第５階層）が含まれ、図２２に示すようにパターンＰＷにはパターンＰと暗号文データＣＴの検索用のキーワードＫＷとが含まれる。
【０２９７】
図２３は、実施の形態３における暗号化装置４００による暗号化方法を示すフローチャートである。
実施の形態３における暗号化方法の処理の流れについて、図２３に基づいて説明する。
【０２９８】
Ｓ４１１において、暗号化入力部４１１は、Ｓ４１０（図１４参照）と同様に、公開鍵ＰＫとユーザｉ用のパターンＰＷｉと平文データＭとを入力する。
Ｓ４１１の後、Ｓ４２０に進む。
【０２９９】
Ｓ４２０−Ｓ４４０において、暗号処理部４１０は、パターンＰＷｉに含まれるパターンＰｉを用いてユーザｉ用の暗号文データＣＴを生成する（図１４参照）。
Ｓ４４０の後、Ｓ４５０に進む。
【０３００】
Ｓ４５０において、暗号化前処理部４１２は、暗号文データＣＴを入力として所定のハッシュ関数ｈを計算し、暗号文データＣＴのハッシュ値ｈ（ＣＴ）を算出する。
ハッシュ値ｈ（ＣＴ）は暗号文データＣＴを群ＧＴの要素に写した値である。例えば、ハッシュ値ｈ（ＣＴ）は、暗号文データＣＴをビット列として入力した場合のハッシュ関数ＳＨＡ−１の出力値である。
Ｓ４５０の後、Ｓ４６０に進む。
【０３０１】
Ｓ４６０−Ｓ４８０において、暗号処理部４１０は、Ｓ４５０で算出されたハッシュ値ｈ（ＣＴ）を平文データＭＷとしてＳ４２０−Ｓ４４０と同様に、パターンＰＷｉを用いてユーザｉ用の暗号文データＣＴＷを生成する。このとき、キーワードＫＷに対応する階層は「識別階層」として扱う。
Ｓ４８０の後、Ｓ４９０に進む。
【０３０２】
Ｓ４９０において、暗号文生成部４１４は、Ｓ４４０で生成した暗号文データＣＴとＳ４８０で生成した暗号文ＣＴＷとを含んだ暗号文データＣＴＷを生成し、生成した暗号文データＣＴＷを出力する。
Ｓ４９０により、暗号化方法の処理は終了する。
【０３０３】
図２４は、実施の形態３における復号装置３００によるクエリ生成方法を示すフローチャートである。
復号装置３００のクエリ生成処理部３３０が実行するクエリ生成方法の処理の流れについて、図２４に基づいて説明する。
【０３０４】
Ｓ６１０において、クエリ生成処理部３３０は、公開鍵ＰＫとユーザｉのユーザ秘密鍵ＳＫ（ＩＤｉ）とユーザｉのユーザ識別子ＩＤｉとキーワードＫＷとを入力する。
Ｓ６１０の後、Ｓ６２０に進む。
【０３０５】
Ｓ６２０−Ｓ６５０において、クエリ生成処理部３３０は、ユーザ識別子ＩＤｉにキーワードＫＷを加えたデータをユーザｊのユーザ識別子ＩＤｊとして扱い、鍵委譲処理部３２０と同様に（図１３のＳ３２０−Ｓ３５０参照）、複数の復号鍵値を算出する。
Ｓ６５０の後、Ｓ６６０に進む。
【０３０６】
Ｓ６６０において、クエリ生成処理部３３０は、ユーザｉのユーザ識別子ＩＤｉとＳ６５０で算出した複数の復号鍵値とを含んだ検索クエリＱＫを生成し、生成した検索クエリＱＫを出力する。
Ｓ６６０により、クエリ生成方法の処理は終了する。
【０３０７】
図２５は、実施の形態３における検索装置５００による検索方法を示すフローチャートである。
検索装置５００の検索処理部５１０が実行する検索方法の処理の流れについて、図２５に基づいて説明する。
【０３０８】
Ｓ７１０において、検索クエリ入力部５１１は、検索クエリＱＫと公開鍵ＰＫとを入力する。
Ｓ７１０の後、Ｓ７１１に進む。
【０３０９】
Ｓ７１１において、検索クエリ入力部５１１は、検索記憶部５９０から未処理の暗号文データＣＴＷを順番にまたはランダムに一つ選択する。
Ｓ７１２の後、Ｓ７２０に進む。
【０３１０】
Ｓ７２０−Ｓ７４０において、検索部５１２は、公開鍵ＰＫと検索クエリＱＫに含まれる復号鍵値と検索クエリＱＫに含まれるユーザ識別子ＩＤｉと暗号文データＣＴＷに含まれる暗号文データＣＴＷとを用いて、平文データＭＷを算出する。
平文データＭＷの算出方法は、復号方法（図１５のＳ５２０−Ｓ５４０参照）と同様である。
Ｓ７４０の後、Ｓ７５０に進む。
【０３１１】
Ｓ７５０において、検索部５１２は、暗号文データＣＴＷに含まれる暗号文データＣＴのハッシュ値ｈ（ＣＴ）を算出する。
ハッシュ値ｈ（ＣＴ）の算出方法は、Ｓ４５０（図２３参照）と同様である。
Ｓ７５０の後、Ｓ７６０に進む。
【０３１２】
Ｓ７６０において、検索部５１２は、Ｓ７４０で算出した平文データＭＷとＳ７５０で算出したハッシュ値ｈ（ＣＴ）とを比較する。
平文データＭＷとハッシュ値ｈ（ＣＴ）とが一致する場合（ＹＥＳ）、Ｓ７７０に進む。
平文データＭＷとハッシュ値ｈ（ＣＴ）とが一致しない場合（ＮＯ）、Ｓ７１１に戻る。
【０３１３】
Ｓ７７０において、検索部５１２は、暗号文データＣＴＷに含まれる暗号文データＣＴを出力する。
Ｓ７７０により、検索方法の処理は終了する。
【０３１４】
Ｓ７７０で出力された暗号文データＣＴは、実施の形態１で説明した復号方法（図１５参照）により復号される。
【０３１５】
公開鍵秘匿検索システム１１０は、キーワードを秘匿したままキーワード検索を行うことができる。なぜならば、検索される暗号文が秘匿性に加えて匿名性を有しており、暗号文を見てもキーワードについて何ら情報を得ることが出来ないからである。
【０３１６】
また、ワイルドカードの使用に対応しているため、実施の形態１と同様にグループ内で暗号文を共有することができる。
【０３１７】
検索キーワードは複数設けても構わない。つまり、キーワードに対応する階層を複数設けても構わない。
この場合、暗号文データＣＴＷは検索キーワードと同じ数の暗号文データＣＴＷを含み、少なくともいずれかの暗号文データＣＴＷについてハッシュ値ｈ（ＣＴ）が一致した場合に検索にヒットしたと判定し、暗号文データＣＴを出力する。但し、全ての暗号文データＣＴＷについてハッシュ値ｈ（ＣＴ）が一致した場合に検索にヒットしたと判定しても構わない。さらに、暗号文データＣＴＷの順番、つまり、検索キーワードの階層順序が一致した場合に検索にヒットしたと判定しても構わない。
【０３１８】
暗号化処理（図２３参照）および検索方法（図２５参照）において、ハッシュ値ｈ（ＣＴ）の代わりに検索定数（例えば、定数０）を平文データＭＷとして扱ってもよい。つまり、検索時に復号された値が検索定数と一致した場合に検索にヒットしたと判定する。
これにより、暗号文データＣＴと暗号文データＣＴＷ（暗号化キーワード）とを一緒に保持しておく必要はなくなり、別々に管理しておくことができる。したがって、データ管理の柔軟性を向上させることができる。
【０３１９】
本実施の形態では、検索クエリに検索ユーザのユーザ識別子を含ませる構成とした。これは、検索時に暗号文の中のワイルドカードに対応する要素を検索ユーザのユーザ識別子で「焼き直す」ためである。
しかし、「焼き直し」を必要としない場合（すなわち自分宛の暗号文のみを検索する場合）には、検索クエリにユーザ識別子を含まない構成にしてもよい。
このようにすれば、検索ユーザは検索装置に対して自らのユーザ識別子を隠したまま検索を依頼することができる。
【０３２０】
本実施の形態では、実施の形態１と同様に合成数位数のペアリング群を用いることもできるし、実施の形態２と同様に素数位数のペアリング群の直積を用いることもできる。
【０３２１】
また、より一般に、「委譲可能な秘匿ベクトル暗号」（Ｄｅｌｅｇａｔａｂｌｅ  ｈｉｄｄｅｎ  ｖｅｃｔｏｒ  ｅｎｃｒｙｐｔｉｏｎ）を用いて「グループ共有型公開鍵秘匿検索」を実現することもできる。
ここで言う「委譲可能な秘匿ベクトル暗号」とは、ＩＤベース暗号または属性ベース暗号などのいわゆる述語暗号（Ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ）または関数型暗号（Ｆｕｎｃｔｉｏｎａｌ  ｅｎｃｒｙｐｔｉｏｎ）である。
但し、「委譲可能な秘匿ベクトル暗号」は、鍵委譲の機能を備え、かつ暗号化のＩＤまたは属性としてワイルドカード相当の機能を備えているものとする。さらに、「委譲可能な秘匿ベクトル暗号」は、ＩＤまたは属性の情報が暗号文から漏洩しない匿名性を備えているものとする。
この具体的な実現方式には、例えば非特許文献７に記載のＤｅｌｅｇａｔａｂｌｅ  ＨＶＥや、非特許文献８に記載のＨｉｅｒａｒｃｈｉｃａｌ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎなどがある。
それぞれの暗号方式によって具体的なアルゴリズムやパラメータ、あるいは根拠とする数論仮定は異なる。しかし、いずれの暗号方式も基本的には実施の形態１と同様にセットアップ手段、鍵生成手段、鍵委譲手段、暗号化手段および復号手段、またはそれらに類するものを含む構成となっている。このため、本実施の形態に開示した構成に準じた構成をとることにより、本実施の形態と同様に「グループ共有型公開鍵秘匿検索」を実現することができる。これは、当業者であれば容易に理解し得ることである。
【０３２２】
本実施の形態によれば、グループ共有型公開鍵秘匿検索を実現することができる。
【０３２３】
さらに、検索演算および復号演算（検索にヒットした暗号文を復号する演算）の中のペアリング演算の回数を階層数に比例せず一定回数（具体的には３回）にすることができる。
これにより、大企業や官公庁のように大きな階層を持つ組織においても高速な検索および復号を実現することができる。
【０３２４】
さらに、実施の形態１と同様に、ユーザ秘密鍵の生成・委譲においても、また暗号化においても、ユーザ識別子を指定する際に中間の階層部分に空欄をおくことができる。
これによって、図２１に示した田中さんのように通常の階層構造から外れるようなユーザにも柔軟に対応することができる。つまり、特異な階層構造にも柔軟に対応することができる。
【０３２５】
さらに、より一般に、「委譲可能な秘匿ベクトル暗号」を用いて「グループ共有型公開鍵秘匿検索」を実現することができる。これによって、グループ共有型公開鍵秘匿検索方式を実現するためのより一般的な方法を提供することができる。
【０３２６】
実施の形態４．
検索可能なユーザを追加または削除する形態について説明する。
以下、実施の形態３と異なる事項について主に説明する。説明を省略する事項については実施の形態３と同様である。
【０３２７】
まず、検索可能なユーザを追加する形態について説明する。
【０３２８】
検索可能なユーザを追加するには、追加するユーザにユーザ識別子ＩＤを割り当てればよい。
【０３２９】
図２６は、実施の形態４におけるユーザ識別子ＩＤの一例を示す図である。
例えば、採用係に高橋さんが新たに配属された場合、図２６に示すように高橋さんのユーザ識別子ＩＤ９を生成する。
採用係長は実施の形態１で説明した鍵委譲方法により高橋さんにユーザ秘密鍵ＳＫを委譲し、高橋さんは委譲されたユーザ秘密鍵ＳＫを用いて実施の形態３で説明したクエリ生成方法により検索クエリＱＫを生成する。
【０３３０】
また、人事課に査定係が新たに設けられた場合、図２６に示すように査定係（査定係長）のユーザ識別子ＩＤ１０を生成する。
人事課長は査定係長にユーザ秘密鍵ＳＫを委譲し、査定係長は委譲されたユーザ秘密鍵ＳＫを用いて検索クエリを生成する。また、査定係長は委譲されたユーザ秘密鍵ＳＫを用いて査定係の各社員にユーザ秘密鍵ＳＫを委譲する。
【０３３１】
次に、検索可能なユーザを削除する形態について説明する。
【０３３２】
検索可能なユーザを削除するには、検索できないユーザのリスト（削除者リスト）を作成すればよい。
【０３３３】
図２７は、実施の形態４における削除者リストの一例を示す図である。
例えば、図２７に示すような削除者リストを検索装置５００の検索記憶部５９０（検索識別子記憶部の一例）に記憶しておく。
削除者リストは、検索できないユーザ（検索権限が無いユーザ）のユーザ識別子ＩＤ（非検索識別子）の一覧を示す。
【０３３４】
例えば、採用係の山田さんが別の部署に異動になった場合、採用係長は山田さんのユーザ識別子ＩＤ１３を検索装置５００に入力し、削除者リストへの山田さんの登録を依頼する。検索装置５００のユーザ管理部（図示省略）は、入力されたユーザ識別子ＩＤ１３を図２７に示すように削除者リストに追加することにより、削除者リストに山田さんを登録する。
人事課の研修係が廃止になった場合、同様に、人事課長が削除者リストへの研修係の登録を依頼し、検索装置５００のユーザ管理部が研修係のユーザ識別子ＩＤ３７を図２７に示すように削除者リストに追加する。
【０３３５】
また、山田さんが採用係に再び配属になった場合、採用係長は山田さんのユーザ識別子ＩＤ１３を検索装置５００に入力し、削除者リストからの消去を依頼する。検索装置５００のユーザ管理部は、入力されたユーザ識別子ＩＤ１３を削除者リストから消去する。
人事課の研修係が復活した場合、同様に、人事課長が削除者リストからの消去を依頼し、検索装置５００のユーザ管理部が研修係のユーザ識別子ＩＤ３７を削除者リストから消去する。
【０３３６】
このとき、他人からの虚偽の依頼を防ぐため、依頼者の電子署名の入力を要求してもよい。検索装置５００のユーザ管理部は入力された電子署名を従来の署名検証方法により検証し、電子署名が正しい場合に依頼を受け付ける。
【０３３７】
図２８は、実施の形態４における検索装置５００の検索方法を示すフローチャートである。
実施の形態４における検索装置５００の検索方法について、図２８に基づいて説明する。
【０３３８】
実施の形態４では、実施の形態３で説明した処理（図２５参照）に加えて、Ｓ７１２とＳ７１３とを実行する。
【０３３９】
Ｓ７１２において、検索クエリ入力部５１１は、検索クエリＱＫに含まれるユーザ識別子ＩＤが削除者リストに含まれているか否かを判定する。つまり、検索クエリＱＫに含まれるユーザ識別子ＩＤが削除者リストに含まれるユーザ識別子ＩＤと一致するか否かを判定する。
ユーザ識別子ＩＤが削除者リストに含まれている場合（ＹＥＳ）、検索方法の処理を終了する。
ユーザ識別子ＩＤが削除者リストに含まれていない場合（ＮＯ）、Ｓ７１３に進む。
【０３４０】
例えば、検索クエリＱＫに山田さんのユーザ識別子ＩＤ１３が含まれている場合、図２３の削除者リストには山田さんのユーザ識別子ＩＤ１３が含まれているため、検索方法の処理を終了する。
この場合、山田さんは検索装置５００を用いて検索を行うことができない。
【０３４１】
Ｓ７１３において、検索クエリ入力部５１１は、検索クエリＱＫに含まれるユーザ識別子ＩＤより上位の階層のユーザ識別子ＩＤが削除者リストに含まれているか否かを判定する。つまり、検索クエリＱＫに含まれるユーザ識別子ＩＤが削除者リスト内のユーザ識別子ＩＤを含んでいるか否かを判定する。
ユーザ識別子ＩＤより上位の階層のユーザ識別子が削除者リストに含まれている場合（ＹＥＳ）、検索方法の処理を終了する。
ユーザ識別子ＩＤより上位の階層のユーザ識別子が削除者リストに含まれていない場合（ＮＯ）、Ｓ７１１に進む。
【０３４２】
例えば、検索クエリＱＫに研修係の社員のユーザ識別子ＩＤが含まれている場合、図２３の削除者リストには研修係のユーザ識別子ＩＤ３７が含まれているため、検索方法の処理を終了する。
この場合、研修係の社員は検索装置５００を用いて検索を行うことができない。
【０３４３】
ところで、削除者リストに含まれている山田さんが検索装置５００に対して検索クエリを送る際、削除されていない別のユーザの名前を騙って検索依頼をする可能性もある。
しかしその場合でも、山田さんは、採用係宛て（あるいはそれより広範囲の人事課宛てや総務部宛て、全社員宛ても含む）の暗号文を検索することができない。
【０３４４】
例えば、山田さんが佐藤さんの名前（ユーザ識別子）を使って検索依頼した場合、山田さんが属する採用係用のパターンＰ２は図２２に示したように社員名の欄（第４階層）がワイルドカードになっているはずである。
したがって、検索手順の中で、暗号文の各要素のうちワイルドカードに対応する要素の「焼き直し」が行われる。山田さんは佐藤氏の名前を使っているので、暗号文のワイルドカードは佐藤さんの名前で焼き直される。
一方、山田さんが送った検索クエリの中に含まれている復号鍵ｄｋは、山田さんの名前を使って委譲された鍵であり、名前に対応する箇所には山田さんの名前が含まれている。
このように、焼き直しに使われる名前（佐藤）と復号鍵に含まれる名前（山田）とが異なるので、仮にキーワードが一致していても、検索にヒットすることはない。
【０３４５】
ここでは、社員名の欄がワイルドカードになっている場合で説明したが、それ以外の欄がワイルドカードになっている場合でも同様である。
【０３４６】
したがって、削除されていない別のユーザの名前を使って検索依頼をしても、暗号文を検索することができない。
【０３４７】
なお、これを逆手にとれば、削除者リストに山田さんが含まれていても、山田さん宛ての暗号文を検索することができる。
なぜならば、山田さん用のパターン（図２２のパターンＰ１）にはワイルドカードが含まれていないからである。このため、暗号文の「焼き直し」が発生せず、山田さんの復号鍵ｄｋが有効に機能する。
このようにするには、実施の形態３にも記載のように、山田さんの検索クエリの中にユーザ識別子ＩＤを含まない構成にすればよい。
【０３４８】
本実施の形態は、実施の形態３と同様に、「委譲可能な秘匿ベクトル暗号」であればどの方式でも実現可能である。
【０３４９】
本実施の形態によれば、グループ（階層）に新たにユーザまたは下位グループを追加し、新たに追加したユーザまたは下位グループにキーワード検索を実行させることができる。
また、グループからユーザまたは下位グループを削除して、そのグループに関連するキーワード検索をできないようにすることができる。
したがって、ユーザやグループの追加および脱退に柔軟に対応することができる。
【０３５０】
実施の形態５．
削除者リストに含まれるユーザが個人宛ての暗号文も検索できない形態について説明する。
以下、実施の形態４と異なる事項について主に説明する。説明を省略する事項については実施の形態４と同様である。
【０３５１】
図２９は、実施の形態５におけるユーザ識別子ＩＤの一例を示す図である。
図２９に示すように、実施の形態５では社員（ユーザの一例）を対応付ける階層を複数設ける。
例えば、山田さんのユーザ識別子ＩＤ６には第４階層と第５階層との２つの階層に“山田”が含まれている。つまり、社員層が二重化されている。
【０３５２】
図３０は、実施の形態５におけるパターンＰの一例を示す図である。
図３０に示すように、実施の形態５では社員を対応付けた複数の階層のうち少なくとも１つの階層にワイルドカード値「＊」を設定する。
例えば、山田さん用のパターンＰ１には、第４階層の要素としてワイルドカード値「＊」が含まれている。
【０３５３】
これにより、ユーザの失効を実現することができる。なぜならば、そのユーザが検索できる暗号文には必ずワイルドカードが含まれ、検索クエリの中にユーザ識別子が必ず含まれるからである。また、実施の形態４で述べたように、他人の名前を使って検索クエリを出すことができないためである。
したがって、削除者リストに名前が載れば、そのユーザは検索を行うことができなくなる。つまり、そのユーザの検索権限は失効する。
【０３５４】
本実施の形態において、社員層より上位の階層を失効させる場合には、その階層を多重化すればよい。また、予め、全ての階層を多重化してもおいてもよい。
【０３５５】
本実施の形態によれば、ユーザまたはグループを失効させ、キーワード検索をできないようにすることができる。
したがって、ユーザやグループの失効に柔軟に対応することができる。
【符号の説明】
【０３５６】
１００  階層型ＩＤベース暗号システム、１１０  公開鍵秘匿検索システム、２００  セットアップ装置、２１０  セットアップ処理部、２１１  セットアップ入力部、２１２  セットアップ前処理部、２１３  公開鍵値算出部、２１４  公開鍵生成部、２１５  マスタ秘密鍵生成部、２１６  セットアップ出力部、２２０  鍵生成処理部、２２１  鍵生成入力部、２２２  鍵生成前処理部、２２３  ユーザ秘密鍵値算出部、２２４  ユーザ秘密鍵生成部、２９０  セットアップ記憶部、３００  復号装置、３１０  復号処理部、３１１  復号入力部、３１２  復号前処理部、３１３  復号部、３２０  鍵委譲処理部、３２１  鍵委譲入力部、３２２  鍵委譲前処理部、３２３  委譲鍵値算出部、３２４  委譲鍵生成部、３３０  クエリ生成処理部、３９０  復号記憶部、４００  暗号化装置、４１０  暗号処理部、４１１  暗号化入力部、４１２  暗号化前処理部、４１３  暗号値算出部、４１４  暗号文生成部、４９０  暗号化記憶部、５００  検索装置、５１０  検索処理部、５１１  検索クエリ入力部、５１２  検索部、５１３  検索結果出力部、５９０  検索記憶部、９０１  ＣＰＵ、９０２  バス、９０３  ＲＯＭ、９０４  ＲＡＭ、９０５  通信ボード、９１１  ディスプレイ装置、９１２  キーボード、９１３  マウス、９１４  ドライブ装置、９２０  磁気ディスク装置、９２１  ＯＳ、９２２  プログラム群、９２３  ファイル群。
【図１】
2012098649.tif 000041
【図２】
2012098649.tif 000042
【図３】
2012098649.tif 000043
【図４】
2012098649.tif 000044
【図５】
2012098649.tif 000045
【図６】
2012098649.tif 000046
【図７】
2012098649.tif 000047
【図８】
2012098649.tif 000048
【図９】
2012098649.tif 000049
【図１０】
2012098649.tif 000050
【図１１】
2012098649.tif 000051
【図１２】
2012098649.tif 000052
【図１３】
2012098649.tif 000053
【図１４】
2012098649.tif 000054
【図１５】
2012098649.tif 000055
【図１６】
2012098649.tif 000056
【図１７】
2012098649.tif 000057
【図１８】
2012098649.tif 000058
【図１９】
2012098649.tif 000059
【図２０】
2012098649.tif 000060
【図２１】
2012098649.tif 000061
【図２２】
2012098649.tif 000062
【図２３】
2012098649.tif 000063
【図２４】
2012098649.tif 000064
【図２５】
2012098649.tif 000065
【図２６】
2012098649.tif 000066
【図２７】
2012098649.tif 000067
【図２８】
2012098649.tif 000068
【図２９】
2012098649.tif 000069
【図３０】
2012098649.tif 000070
【手続補正書】
【提出日】平成26年1月16日(2014.1.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる暗号システムにおいて、
暗号化する平文データＭを入力し、入力した平文データＭを暗号化して平文暗号値Ｃ０を算出し、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力し、入力したパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、ｋ個の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、入力したパターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出し、算出した平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを生成し、生成した暗号文データＣＴを出力する暗号化装置と、
前記暗号文データＣＴと前記ユーザ識別子ＩＤとを入力し、入力した暗号文データＣＴに含まれるワイルドカード階層値Ｗに基づいて入力したユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と入力した暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて入力した暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する復号装置と
を備えたことを特徴とする暗号システム。
【請求項２】
前記公開鍵ＰＫは、ｋ個の階層に対応付けられたｋ個の鍵値Ｈ’を含むＨ’鍵値群を含み、
前記暗号化装置は、入力した公開鍵ＰＫに含まれるＨ’鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈ’を第２のワイルドカード鍵値として抽出し、抽出した第２のワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１’を算出し、入力した公開鍵ＰＫに含まれるＨ’鍵値群から前記識別階層に対応付けられた鍵値Ｈ’を第２の識別鍵値として抽出し、抽出した第２の識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３’を算出し、算出したワイルドカード暗号値Ｃ１’と識別暗号値Ｃ３’とを含めて前記暗号文データＣＴを出力し、
前記復号装置は、抽出したワイルドカード識別子と入力した暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とワイルドカード暗号値Ｃ１’と識別暗号値Ｃ３’とを用いて入力した暗号文データＣＴに含まれる平文暗号値Ｃ０を復号する
ことを特徴とする請求項１記載の暗号システム。
【請求項３】
前記暗号化装置は、さらに、特定の平文データＭＷを暗号化して平文暗号値ＣＷ０を算出し、前記暗号文データＣＴの検索に用いるキーワードＫＷを入力し、前記パターンＰを含むと共に前記キーワードＫＷを第Ｋ＋１階層を識別する階層識別子として含むパターンＰＷを用いてワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを算出し、算出した平文暗号値ＣＷ０とワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを含んだ暗号文データＣＴＷを前記暗号文データＣＴに対応付けて出力し、
前記暗号システムは、さらに、
前記ユーザ識別子ＩＤと前記キーワードＫＷとを入力し、入力したユーザ識別子ＩＤとキーワードＫＷとを用いて前記平文暗号値ＣＷ０の復号に用いる鍵値ｙ０を算出し、算出した鍵値ｙ０と前記ユーザ識別子ＩＤとを含んだ検索クエリＱＫを生成し、生成した検索クエリＱＫを出力する検索クエリ生成装置と、
複数の暗号文データＣＴと複数の暗号文データＣＴＷとを対応付けて記憶する暗号文記憶部を有する検索装置とを備え、
前記検索装置は、前記検索クエリＱＫと前記ワイルドカード階層値Ｗとを入力し、前記暗号文記憶部から暗号文データＣＴＷを選択し、入力したワイルドカード階層値Ｗに基づいて入力した検索クエリＱＫに含まれるユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と選択した暗号文データＣＴＷに含まれるワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３と入力した検索クエリＱＫに含まれる鍵値ｙ０とを用いて選択した暗号文データＣＴＷに含まれる平文暗号値ＣＷ０を復号し、前記平文暗号値ＣＷ０を復号して得られた復号データが前記平文データＭＷと一致するか否かを判定し、前記復号データが前記平文データＭＷと一致した場合、選択した暗号文データＣＴＷに対応する暗号文データＣＴを前記暗号文記憶部から取得し、取得した暗号文データＣＴを入力した検索クエリＱＫに対する検索結果として出力する
ことを特徴とする請求項１記載の暗号システム。
【請求項４】
前記暗号化装置は、前記暗号文データＣＴのハッシュ値を前記平文データＭＷとして算出し、算出した平文データＭＷを暗号化して前記平文暗号値ＣＷ０を算出し、
前記検索装置は、選択した暗号文データＣＴＷに対応する暗号文データＣＴのハッシュ値を前記平文データＭＷとして算出し、前記復号データが算出した平文データＭＷと一致するか否かを判定する
ことを特徴とする請求項３記載の暗号システム。
【請求項５】
前記暗号化装置は、前記平文データＭＷとして所定の検索定数を予め記憶し、予め記憶した検索定数を暗号化して前記平文暗号値ＣＷ０を算出し、
前記検索装置は、前記平文データＭＷとして前記検索定数を予め記憶し、前記復号データが前記検索定数と一致するか否かを判定する
ことを特徴とする請求項３記載の暗号システム。
【請求項６】
前記検索装置は、検索する権限が無いユーザのユーザ識別子ＩＤを非検索識別子として記憶する非検索識別子記憶部を備え、
前記検索装置は、入力した検索クエリＱＫに含まれるユーザ識別子ＩＤと前記非検索識別子記憶部に記憶された非検索識別子とが一致するか否かを判定し、前記ユーザ識別子ＩＤと前記非検索識別子とが一致する場合に前記検索結果を出力しない
ことを特徴とする請求項３記載の暗号システム。
【請求項７】
前記検索装置は、検索する権限が無いユーザが属する階層より上位の階層の階層識別子を非検索識別子として記憶する非検索識別子記憶部を備え、
前記検索装置は、入力した検索クエリＱＫに含まれるユーザ識別子ＩＤに前記非検索識別子記憶部に記憶された非検索識別子が含まれるか否かを判定し、前記ユーザ識別子ＩＤに前記非検索識別子が含まれる場合に前記検索結果を出力しない
ことを特徴とする請求項３記載の暗号システム。
【請求項８】
前記ユーザ識別子ＩＤは、前記特定のユーザの第１のユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に前記特定のユーザの第２のユーザ識別子を第ｋ＋１階層を識別する階層識別子として含み、
前記公開鍵ＰＫに含まれるＨ鍵値群は、ｋ＋１個の階層に対応付けられたｋ＋１個の鍵値Ｈを含み、
前記パターンＰは、第ｋ階層と第ｋ＋１階層との少なくともいずれかの階層のパターン値としてワイルドカード値を含む
ことを特徴とする請求項３記載の暗号システム。
【請求項９】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる暗号システムの暗号処理方法において、
暗号化装置が、暗号化する平文データＭを入力し、入力した平文データＭを暗号化して平文暗号値Ｃ０を算出し、階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力し、入力したパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、ｋ個の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、入力したパターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、入力した公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出し、算出した平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを出力し、
復号化装置が、前記暗号文データＣＴと前記ユーザ識別子ＩＤとを入力し、入力した暗号文データＣＴに含まれるワイルドカード階層値Ｗに基づいて入力したユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と入力した暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて入力した暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する
ことを特徴とする暗号システムの暗号処理方法。
【請求項１０】
前記暗号化装置は、さらに、特定の平文データＭＷを暗号化して平文暗号値ＣＷ０を算出し、前記暗号文データＣＴの検索に用いるキーワードＫＷを入力し、前記パターンＰを含むと共に前記キーワードＫＷを第Ｋ＋１階層を識別する階層識別子として含むパターンＰＷを用いてワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを算出し、算出した平文暗号値ＣＷ０とワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３とを含んだ暗号文データＣＴＷを前記暗号文データＣＴに対応付けて出力し、
検索クエリ生成装置が、前記ユーザ識別子ＩＤと前記キーワードＫＷとを入力し、入力したユーザ識別子ＩＤとキーワードＫＷとを用いて前記平文暗号値ＣＷ０の復号に用いる鍵値ｙ０を算出し、算出した鍵値ｙ０と前記ユーザ識別子ＩＤとを含んだ検索クエリＱＫを出力し、
検索装置が、複数の暗号文データＣＴと複数の暗号文データＣＴＷとを対応付けて記憶する暗号文記憶部を有し、
前記検索装置は、前記検索クエリＱＫと前記ワイルドカード階層値Ｗとを入力し、前記暗号文記憶部から暗号文データＣＴＷを選択し、入力したワイルドカード階層値Ｗに基づいて入力した検索クエリＱＫに含まれるユーザ識別子ＩＤから前記ワイルドカード階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と選択した暗号文データＣＴＷに含まれるワイルドカード暗号値ＣＷ１と識別暗号値ＣＷ３と入力した検索クエリＱＫに含まれる鍵値ｙ０とを用いて選択した暗号文データＣＴＷに含まれる平文暗号値ＣＷ０を復号し、前記平文暗号値ＣＷ０を復号して得られた復号データが前記平文データＭＷと一致するか否かを判定し、前記復号データが前記平文データＭＷと一致した場合、選択した暗号文データＣＴＷに対応する暗号文データＣＴを前記暗号文記憶部から取得し、取得した暗号文データＣＴを入力した検索クエリＱＫに対する検索結果として出力する
ことを特徴とする請求項９記載の暗号システムの暗号処理方法。
【請求項１１】
暗号化する平文データＭを入力し、ｋ個（ｋは２以上の特定の整数）の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、階層を識別する階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力する暗号化入力部と、
前記暗号化入力部が入力した平文データＭを暗号化して平文暗号値Ｃ０を算出し、前記暗号化入力部が入力したパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、前記暗号化入力部が入力した公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、前記パターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、前記公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出する暗号値算出部と、
前記暗号値算出部により算出された平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを生成し、生成した暗号文データＣＴを出力する暗号文出力部と
を備えたことを特徴とする暗号化装置。
【請求項１２】
暗号化する平文データＭを入力し、ｋ個（ｋは２以上の特定の整数）の階層に対応付けられたｋ個の鍵値Ｈを含むＨ鍵値群を含んだ公開鍵ＰＫを入力し、階層を識別する階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを入力する暗号化入力処理と、
前記暗号化入力処理により入力された平文データＭを暗号化して平文暗号値Ｃ０を算出し、前記暗号化入力処理により入力されたパターンＰに基づいて前記パターン値がワイルドカード値である階層をワイルドカード階層として判定し、前記暗号化入力処理により入力された公開鍵ＰＫに含まれるＨ鍵値群から前記ワイルドカード階層に対応付けられた鍵値Ｈをワイルドカード鍵値として抽出し、抽出したワイルドカード鍵値を用いて前記平文暗号値Ｃ０の復号に用いるワイルドカード暗号値Ｃ１を算出し、前記パターンＰに基づいて前記パターン値が階層識別子である階層を識別階層として判定し、前記公開鍵ＰＫに含まれるＨ鍵値群から前記識別階層に対応付けられた鍵値Ｈを識別鍵値として抽出し、抽出した識別鍵値を用いて前記平文暗号値Ｃ０の復号に用いる識別暗号値Ｃ３を算出する暗号値算出処理と、
前記暗号値算出処理により算出された平文暗号値Ｃ０とワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを含むと共に前記ワイルドカード階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを生成し、生成した暗号文データＣＴを出力する暗号文出力処理と
をコンピュータに実行させることを特徴とする暗号化プログラム。
【請求項１３】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる復号装置において、
階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを用いて生成された暗号文データＣＴであって平文データＭを暗号化した平文暗号値Ｃ０と特定のワイルドカード暗号値Ｃ１と特定の識別暗号値Ｃ３とを含むと共に前記パターンＰに含まれるパターン値がワイルドカード値である階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを入力し、前記ユーザ識別子ＩＤを入力する復号入力部と、
前記復号入力部が入力した暗号文データＣＴに基づいて、前記復号入力部が入力したユーザ識別子ＩＤから前記ワイルドカード階層値Ｗによって示される階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と前記暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて前記暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する復号部と
を備えたことを特徴とする復号装置。
【請求項１４】
階層構造を有する組織内で第ｋ階層（ｋは２以上の特定の整数）に属する特定ユーザのユーザ識別子を第ｋ階層を識別する階層識別子として含むと共に第１階層から第ｋ−１階層までの階層を識別するｋ−１個の階層識別子を含むユーザ識別子ＩＤを用いる復号プログラムにおいて、
階層識別子と任意のユーザを意味するワイルドカード値と不要な階層を意味する空欄値とのいずれかを階層毎にパターン値として含んだパターンＰを用いて生成された暗号文データＣＴであって平文データＭを暗号化した平文暗号値Ｃ０と特定のワイルドカード暗号値Ｃ１と特定の識別暗号値Ｃ３とを含むと共に前記パターンＰに含まれるパターン値がワイルドカード値である階層を示すワイルドカード階層値Ｗを含む暗号文データＣＴを入力し、前記ユーザ識別子ＩＤを入力する復号入力処理と、
前記復号入力処理により入力された暗号文データＣＴに基づいて、前記復号入力処理により入力されたユーザ識別子ＩＤから前記ワイルドカード階層値Ｗによって示される階層の階層識別子をワイルドカード識別子として抽出し、抽出したワイルドカード識別子と前記暗号文データＣＴに含まれるワイルドカード暗号値Ｃ１と識別暗号値Ｃ３とを用いて前記暗号文データＣＴに含まれる平文暗号値Ｃ０を復号し、前記平文暗号値Ｃ０を復号して得られる前記平文データＭを出力する復号処理と
をコンピュータに実行させることを特徴とする復号プログラム。
【国際調査報告】
2012098649.tif 000071
2012098649.tif 000072
2012098649.tif 000073