(57)【要約】【課題】権限委譲を可能とした述語暗号を実現することを目的とする。【解決手段】ペアリング演算によって関連付けられた双対ベクトル空間（双対ディストーションベクトル空間）である空間Ｖと空間Ｖ＊とを用いて暗号処理を行う。暗号化装置は、空間Ｖにおけるベクトルであって、送信情報を埋め込んだベクトルを暗号ベクトルとして生成する。復号装置は、空間Ｖ＊における所定のベクトルを鍵ベクトルとして、暗号化装置が生成した暗号ベクトルと鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して送信情報に関する情報を抽出する。特に、暗号化装置及び復号装置は、空間Ｖと空間Ｖ＊の一部の次元を使用せずに暗号処理を行う。【選択図】図７
2011141472.tif 000002
【特許請求の範囲】
【請求項１】
数１に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Ｖと空間Ｖ＊とを用いて述語暗号処理を行う暗号処理システムであり、
前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾と、所定の属性情報とが公開鍵として与えられ、前記基底Ｂ＾の基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうちの少なくとも一部の基底ベクトルに対する係数として属性情報を設定するとともに、前記基底ベクトルｂｎ＋１に対する係数として所定の情報を設定したベクトルを暗号ベクトルｃ１として処理装置により生成する暗号化装置と、
前記空間Ｖ＊の基底Ｂ＊におけるベクトルであって、基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）うちの少なくとも一部の基底ベクトルに対する係数として述語情報を設定するとともに、前記基底Ｂ＊の基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして、前記暗号化装置が生成した暗号ベクトルｃ１と前記鍵ベクトルｋ＊Ｌ，ｄｅｃとについて、処理装置により数１に示すペアリング演算ｅ（ｃ１，ｋ＊Ｌ，ｄｅｃ）を行い前記暗号ベクトルｃ１を復号して前記所定の情報に関する値を抽出する復号装置と
を備えることを特徴とする暗号処理システム。
【数１】
2011141472.tif 000116
【請求項２】
前記復号装置は、前記基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｒ，．．．，Ｓ，．．．，Ｎ）（Ｎは４以上の整数，Ｓはｎ＋２以上Ｎ−１以下の整数，Ｒはｎ＋１以上Ｓ−１以下の整数，ｎは１以上Ｎ−３以下の整数）の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）うちの少なくとも一部の基底ベクトルに述語情報を設定し、前記基底Ｂ＊の基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定し、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）に対する係数として乱数値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして、前記暗号ベクトルｃ１と前記鍵ベクトルｋ＊Ｌ，ｄｅｃとについて、前記ペアリング演算ｅ（ｃ１，ｋ＊Ｌ，ｄｅｃ）を行う
ことを特徴とする暗号処理システム。
【請求項３】
前記暗号処理システムは、さらに、
前記基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｒ，．．．，Ｓ，．．．，Ｎ）のうち、基底ベクトルｂ＊ｉ（ｉ＝０，．．．，ｎ）の少なくとも一部の基底ベクトルに対する係数として述語情報を設定し、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定し、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）に対する係数として乱数値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして処理装置により生成する鍵生成装置を備え、
前記復号装置は、前記鍵生成装置が生成した鍵ベクトルｋ＊Ｌ，ｄｅｃを取得して、取得した鍵ベクトルｋ＊Ｌ，ｄｅｃと暗号ベクトルｃ１とについて前記ペアリング演算を行う
ことを特徴とする請求項２に記載の暗号処理システム。
【請求項４】
前記暗号処理システムは、さらに、
前記鍵生成装置が生成した鍵ベクトルｋ＊Ｌ，ｄｅｃが復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能なベクトルであって、述語情報を設定した基底ベクトルに対する係数として一様に分布させた値を持つ乱数値を設定したベクトルを鍵ベクトルｋ＊Ｌ＋１，ｄｅｃとして生成する鍵委譲装置
を備えることを特徴とする請求項３に記載の暗号処理システム。
【請求項５】
述語暗号における秘密鍵である鍵ベクトルｋ＊Ｌ，ｄｅｃを生成する鍵生成装置であって、数２に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Ｖと空間Ｖ＊とのうちの前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾が公開鍵として与えられた場合における秘密鍵である鍵ベクトルｋ＊Ｌ，ｄｅｃを生成する鍵生成装置であり、
前記空間Ｖ＊における所定の基底Ｂ＊を記憶装置に記憶するマスター鍵記憶部と、
前記マスター鍵記憶部が記憶した前記基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）のうち、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）の少なくとも一部の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として述語情報を設定するとともに、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして処理装置により生成する鍵ベクトル生成部と
を備えることを特徴とする鍵生成装置。
【数２】
2011141472.tif 000117
【請求項６】
前記鍵ベクトル生成部は、前記基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｒ，．．．，Ｓ，．．．，Ｎ）（Ｎは４以上の整数，Ｓはｎ＋２以上Ｎ−１以下の整数，Ｒはｎ＋１以上Ｓ−１以下の整数，ｎは１以上Ｎ−３以下の整数）のうち、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）の少なくとも一部の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として述語情報を設定するとともに、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定し、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）に対する係数として乱数値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして処理装置により生成する
ことを特徴とする請求項５に記載の鍵生成装置。
【請求項７】
前記鍵ベクトル生成部は、数３に示す鍵ベクトルｋ＊L，ｄｅｃを生成する
ことを特徴とする請求項６に記載の鍵生成装置。
【数３】
2011141472.tif 000118
【請求項８】
前記鍵ベクトル生成部は、数４に示す鍵ベクトルｋ＊Ｌ，ｄｅｃを生成する
ことを特徴とする請求項６に記載の鍵生成装置。
【数４】
2011141472.tif 000119
【請求項９】
前記鍵生成装置は、さらに、
前記鍵ベクトル生成部が生成した鍵ベクトルｋ＊Ｌ，ｄｅｃで復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能な鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成するためのベクトルであって、少なくともｊ＝μＬ＋１，．．．，ｎの各ｊについて、基底ベクトルｂ＊ｊに対する係数として乱数値が設定されるとともに、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）の一部の基底ベクトルに対する係数として乱数値が設定された少なくともｎ−μＬ個のベクトルを鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊとして処理装置により生成する鍵生成用ベクトル生成部と、
前記鍵生成用ベクトル生成部が生成した鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊで生成される鍵ベクトルｋ＊Ｌ＋１，ｄｅｃのうち、述語情報が設定される基底ベクトルの係数に一様に分布した値を設定するためのベクトルであって、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として乱数値倍された述語情報が設定されるとともに、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）の一部の基底ベクトルに対する係数として乱数値が設定された少なくともＬ＋１個のベクトルをランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊとして処理装置により生成するランダム化ベクトル生成部と
を備えることを特徴とする請求項６に記載の鍵生成装置。
【請求項１０】
前記鍵ベクトル生成部は、数５に示す鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊを生成し、
前記ランダム化ベクトル生成部は、数６に示すランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊを生成する
ことを特徴とする請求項９に記載の鍵生成装置。
【数５】
2011141472.tif 000120
【数６】
2011141472.tif 000121
【請求項１１】
前記鍵ベクトル生成部は、数７に示す鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊを生成し、
前記ランダム化ベクトル生成部は、数８に示すランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊを生成する
ことを特徴とする請求項９に記載の鍵生成装置。
【数７】
2011141472.tif 000122
【数８】
2011141472.tif 000123
【請求項１２】
述語暗号における秘密鍵である鍵ベクトルｋ＊Ｌ，ｄｅｃで復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能な鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する鍵委譲装置であって、数９に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Ｖと空間Ｖ＊とのうちの前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｒ，．．．，Ｓ，．．．，Ｎ）（Ｎは４以上の整数，Ｓはｎ＋２以上Ｎ−１以下の整数，Ｒはｎ＋１以上Ｓ−１以下の整数，ｎは１以上Ｎ−３以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾が公開鍵として与えられた場合における秘密鍵である鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する鍵委譲装置であり、
前記基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｒ，．．．，Ｓ，．．．，Ｎ）のうち、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）の少なくとも一部の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として述語情報が設定され、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値が設定され、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）に対する係数として乱数値が設定された鍵ベクトルｋ＊Ｌ，ｄｅｃを取得する鍵ベクトル取得部と、
少なくともｊ＝μＬ＋１，．．．，ｎの各ｊについて、基底ベクトルｂ＊ｊに対する係数として乱数値が設定されるとともに、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）に対する係数として乱数値が設定された少なくともｎ−μＬ個の鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊを取得する鍵生成用ベクトル取得部と、
前記鍵生成用ベクトル取得部が取得した前記鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊの少なくとも一部の前記鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊの各基底ベクトルの係数を述語情報倍し、前記鍵ベクトル取得部が取得した前記鍵ベクトルｋ＊Ｌ，ｄｅｃに加算して鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する鍵ベクトル生成部と
を備えることを特徴とする鍵委譲装置。
【数９】
2011141472.tif 000124
【請求項１３】
前記鍵委譲装置は、さらに、
基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として乱数値倍された述語情報が設定されるとともに、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）に対する係数として乱数値が設定された少なくともＬ＋１個のランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊを取得するランダム化ベクトル取得部を備え、
前記鍵ベクトル生成部は、前記ランダム化ベクトル取得部が取得した前記ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊの少なくとも一部の前記ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊの各基底ベクトルの係数を乱数値倍し、前記鍵ベクトルｋ＊Ｌ＋１，ｄｅｃにさらに加算して鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する
ことを特徴とする請求項１２に記載の鍵委譲装置。
【請求項１４】
前記鍵ベクトル取得部は、数１０に示す鍵ベクトルｋ＊Ｌ，ｄｅｃを取得し、
前記鍵生成用ベクトル取得部は、数１１に示す鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊを取得し、
前記ランダム化ベクトル取得部は、数１２に示すランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊを取得し、
前記鍵ベクトル生成部は、数１３に示す鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する
ことを特徴とする請求項１３に記載の鍵委譲装置。
【数１０】
2011141472.tif 000125
【数１１】
2011141472.tif 000126
【数１２】
2011141472.tif 000127
【数１３】
2011141472.tif 000128
【請求項１５】
前記鍵ベクトル取得部は、数１４に示す鍵ベクトルｋ＊Ｌ，ｄｅｃを取得し、
前記鍵生成用ベクトル取得部は、数１５に示す鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊを取得し、
前記ランダム化ベクトル取得部は、数１６に示すランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊを取得し、
前記鍵ベクトル生成部は、数１７に示す鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する
ことを特徴とする請求項１３に記載の鍵委譲装置。
【数１４】
2011141472.tif 000129
【数１５】
2011141472.tif 000130
【数１６】
2011141472.tif 000131
【数１７】
2011141472.tif 000132
【請求項１６】
前記鍵委譲装置は、さらに、
前記鍵ベクトル生成部が生成した鍵ベクトルｋ＊Ｌ＋１，ｄｅｃで復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能な鍵ベクトルｋ＊Ｌ＋２，ｄｅｃを生成するためのベクトルであって、少なくともｊ＝μＬ＋１＋１，．．．，ｎの各ｊについて、基底ベクトルｂ＊ｊに対する係数として乱数値を設定した少なくともｎ−μＬ＋１個のベクトルを鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊとして処理装置により生成する鍵生成用ベクトル生成部と、
前記鍵生成用ベクトル生成部が生成した鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊで生成される鍵ベクトルｋ＊Ｌ＋２，ｄｅｃのうち、述語情報が設定される基底ベクトルの係数に一様に分布した値を設定するためのベクトルであって、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として乱数値倍された述語情報が設定した少なくともＬ＋２個のベクトルをランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊとして処理装置により生成するランダム化ベクトル生成部と
を備えることを特徴とする請求項１３に記載の鍵委譲装置。
【請求項１７】
前記鍵生成用ベクトル取得部は、数１８に示す鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊを取得し、
前記ランダム化ベクトル取得部は、数１９に示すランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊを取得し、
前記鍵ベクトル生成部は、数２０に示す鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊを生成し、
前記ランダム化ベクトル生成部は、数２１に示すランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊを生成する
ことを特徴とする請求項１６に記載の鍵委譲装置。
【数１８】
2011141472.tif 000133
【数１９】
2011141472.tif 000134
【数２０】
2011141472.tif 000135
【数２１】
2011141472.tif 000136
【請求項１８】
前記鍵生成用ベクトル取得部は、数２２に示す鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊを取得し、
前記ランダム化ベクトル取得部は、数２３に示すランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊを取得し、
前記鍵ベクトル生成部は、数２４に示す鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊを生成し、
前記ランダム化ベクトル生成部は、数２５に示すランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊを生成する
ことを特徴とする請求項１６に記載の鍵委譲装置。
【数２２】
2011141472.tif 000137
【数２３】
2011141472.tif 000138
【数２４】
2011141472.tif 000139
【数２５】
2011141472.tif 000140
【請求項１９】
ペアリング演算によって関連付けられた双対ベクトル空間である空間Ｖと空間Ｖ＊とにおいて実現される述語暗号処理における暗号文である暗号ベクトルｃ１を生成する暗号化装置であり、
前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾を取得するとともに、所定の属性情報を取得する公開鍵取得部と、
前記公開鍵取得部が取得した基底Ｂ＾におけるベクトルであって、基底ベクトルｂｎ＋１に対する係数として所定の情報を設定したベクトルを送信情報ベクトルζｖとして処理装置により生成する送信情報設定部と、
前記基底Ｂ＾の前記基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうちの少なくとも一部の基底ベクトルに対する係数として前記属性情報を設定した属性情報ベクトルを、前記送信情報設定部が生成した送信情報ベクトルζｖに加算して暗号ベクトルｃ１を処理装置により生成する暗号ベクトル生成部と
を備えることを特徴とする暗号化装置。
【請求項２０】
前記送信情報設定部は、数２６に示す送信情報ベクトルζｖを生成し、
前記暗号ベクトル生成部は、数２７に示す暗号ベクトルｃ１を生成する
ことを特徴とする請求項１９に記載の暗号化装置。
【数２６】
2011141472.tif 000141
【数２７】
2011141472.tif 000142
【請求項２１】
前記送信情報設定部は、数２８に示す送信情報ベクトルζｖを生成し、
前記暗号ベクトル生成部は、数２９に示す暗号ベクトルｃ１を生成する
ことを特徴とする請求項１９に記載の暗号化装置。
【数２８】
2011141472.tif 000143
【数２９】
2011141472.tif 000144
【請求項２２】
前記暗号化装置は、さらに、
数３０に示す暗号情報ｃ２を生成する暗号情報生成部
を備えることを特徴とする請求項１９に記載の暗号化装置。
【数３０】
2011141472.tif 000145
【請求項２３】
数３１に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Ｖと空間Ｖ＊とにおいて実現される述語暗号処理における暗号文を復号する復号装置であり、
前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾が公開鍵として与えられた場合に生成される暗号文である暗号ベクトルｃ１であって、前記基底Ｂ＾の基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうち少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，μｈ）に対する係数として属性情報が設定されるとともに、前記基底ベクトルｂｎ＋１に対する係数として所定の情報が設定されたベクトルである暗号ベクトルｃ１を入力するベクトル入力部と、
前記空間Ｖ＊における所定の基底Ｂ＊の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）のうち、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）の少なくとも基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）（μＬ≦μｈ）に対する係数として述語情報ｖｉ（ｉ＝１，．．．，μＬ）が設定され、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値が設定された鍵ベクトルｋ＊Ｌ，ｄｅｃを記憶装置に記憶する鍵ベクトル記憶部と、
前記ベクトル入力部が入力した暗号ベクトルｃ１と、前記鍵ベクトル記憶部が記憶した鍵ベクトルｋ＊Ｌ，ｄｅｃとについて処理装置により数３１に示すペアリング演算を行い、前記暗号ベクトルｃ１から前記所定の情報に関する値を抽出するペアリング演算部と
を備えることを特徴とする復号装置。
【数３１】
2011141472.tif 000146
【請求項２４】
前記鍵ベクトル記憶部は、前記基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｒ，．．．，Ｓ，．．．，Ｎ）（Ｎは４以上の整数，Ｓはｎ＋２以上Ｎ−１以下の整数，Ｒはｎ＋１以上Ｓ−１以下の整数，ｎは１以上Ｎ−３以下の整数）の少なくとも基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）（μＬ≦μｈ）に対する係数として述語情報ｖｉ（ｉ＝１，．．．，μＬ）が設定され、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値が設定され、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）の一部の基底ベクトルに対する係数として所定の値が設定された鍵ベクトルｋ＊Ｌ，ｄｅｃを記憶する
ことを特徴とする請求項２３に記載の復号装置。
【請求項２５】
前記ベクトル入力部は、数３２に示す暗号ベクトルｃ１を入力し、
前記鍵ベクトル記憶部は、数３３に示す鍵ベクトルｋ＊Ｌ，ｄｅｃを記憶し、
前記ペアリング演算部は、数３４に示すペアリング演算を行い、前記暗号ベクトルから前記所定の情報に関する値を抽出する
ことを特徴とする請求項２４に記載の復号装置。
【数３２】
2011141472.tif 000147
【数３３】
2011141472.tif 000148
【数３４】
2011141472.tif 000149
【請求項２６】
前記ベクトル入力部は、数３５に示す暗号ベクトルｃ１を入力し、
前記鍵ベクトル記憶部は、数３６に示す鍵ベクトルｋ＊Ｌ，ｄｅｃを記憶し、
前記ペアリング演算部は、数３７に示すペアリング演算を行い、前記暗号ベクトルから前記所定の情報に関する値を抽出する
ことを特徴とする請求項２４に記載の復号装置。
【数３５】
2011141472.tif 000150
【数３６】
2011141472.tif 000151
【数３７】
2011141472.tif 000152
【請求項２７】
前記ベクトル入力部は、数３８に示す暗号ベクトルｃ１と、平文情報ｍを暗号化した数３９に示す暗号情報ｃ２とを入力し、
前記鍵ベクトル記憶部は、数４０に示す鍵ベクトルｋ＊Ｌ，ｄｅｃを記憶し、
前記ペアリング演算部は、数４１に示す演算を行い、前記暗号ベクトルｃ１から前記平文情報ｍを抽出する
ことを特徴とする請求項２４に記載の復号装置。
【数３８】
2011141472.tif 000153
【数３９】
2011141472.tif 000154
【数４０】
2011141472.tif 000155
【数４１】
2011141472.tif 000156
【請求項２８】
前記ベクトル入力部は、数４２に示す暗号ベクトルｃ１と、平文情報ｍを暗号化した数４３に示す暗号情報ｃ２とを入力し、
前記鍵ベクトル記憶部は、数４４に示す鍵ベクトルｋ＊Ｌ，ｄｅｃを記憶し、
前記ペアリング演算部は、数４５に示す演算を行い、前記暗号ベクトルｃ１から前記平文情報ｍを抽出する
ことを特徴とする請求項２４に記載の復号装置。
【数４２】
2011141472.tif 000157
【数４３】
2011141472.tif 000158
【数４４】
2011141472.tif 000159
【数４５】
2011141472.tif 000160
【請求項２９】
数４６に示すペアリング演算によって関連付けられた双対加群である空間Ｖと空間Ｖ＊とを用いて述語暗号処理を行う暗号処理システムであり、
前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾と、所定の属性情報とが公開鍵として与えられ、前記基底Ｂ＾の基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうちの少なくとも一部の基底ベクトルに対する係数として属性情報を設定するとともに、前記基底ベクトルｂｎ＋１に対する係数として所定の情報を設定したベクトルを暗号ベクトルｃ１として処理装置により生成する暗号化装置と、
前記空間Ｖ＊の基底Ｂ＊におけるベクトルであって、基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）うちの少なくとも一部の基底ベクトルに対する係数として述語情報を設定するとともに、前記基底Ｂ＊の基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして、前記暗号化装置が生成した暗号ベクトルｃ１と前記鍵ベクトルｋ＊Ｌ，ｄｅｃとについて、処理装置により数４６に示すペアリング演算ｅ（ｃ１，ｋ＊Ｌ，ｄｅｃ）を行い前記暗号ベクトルｃ１を復号して前記所定の情報に関する値を抽出する復号装置と
を備えることを特徴とする暗号処理システム。
【数４６】
2011141472.tif 000161
【請求項３０】
述語暗号における秘密鍵である鍵ベクトルｋ＊Ｌ，ｄｅｃを生成する鍵生成装置であって、数４７に示すペアリング演算によって関連付けられた双対加群である空間Ｖと空間Ｖ＊とのうちの前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾が公開鍵として与えられた場合における秘密鍵である鍵ベクトルｋ＊Ｌ，ｄｅｃを生成する鍵生成装置であり、
前記空間Ｖ＊における所定の基底Ｂ＊を記憶装置に記憶するマスター鍵記憶部と、
前記マスター鍵記憶部が記憶した前記基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）のうち、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）の少なくとも一部の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として述語情報を設定するとともに、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして処理装置により生成する鍵ベクトル生成部と
を備えることを特徴とする鍵生成装置。
【数４７】
2011141472.tif 000162
【請求項３１】
述語暗号における秘密鍵である鍵ベクトルｋ＊Ｌ，ｄｅｃで復号可能な暗号ベクトルのうちの一部の暗号ベクトルを復号可能な鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する鍵委譲装置であって、数４８に示すペアリング演算によって関連付けられた双対加群である空間Ｖと空間Ｖ＊とのうちの前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｒ，．．．，Ｓ，．．．，Ｎ）（Ｎは４以上の整数，Ｓはｎ＋２以上Ｎ−１以下の整数，Ｒはｎ＋１以上Ｓ−１以下の整数，ｎは１以上Ｎ−３以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾が公開鍵として与えられた場合における秘密鍵である鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する鍵委譲装置であり、
前記基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｒ，．．．，Ｓ，．．．，Ｎ）のうち、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）の少なくとも一部の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として述語情報が設定され、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値が設定され、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）に対する係数として乱数値が設定された鍵ベクトルｋ＊Ｌ，ｄｅｃを取得する鍵ベクトル取得部と、
少なくともｊ＝μＬ＋１，．．．，ｎの各ｊについて、基底ベクトルｂ＊ｊに対する係数として乱数値が設定されるとともに、基底ベクトルｂ＊ｉ（ｉ＝Ｒ＋１，．．．，Ｓ）に対する係数として乱数値が設定された少なくともｎ−μＬ個の鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊを取得する鍵生成用ベクトル取得部と、
前記鍵生成用ベクトル取得部が取得した前記鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊの少なくとも一部の前記鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊの各基底ベクトルの係数を述語情報倍し、前記鍵ベクトル取得部が取得した前記鍵ベクトルｋ＊Ｌ，ｄｅｃに加算して鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを生成する鍵ベクトル生成部と
を備えることを特徴とする鍵委譲装置。
【数４８】
2011141472.tif 000163
【請求項３２】
ペアリング演算によって関連付けられた双対加群である空間Ｖと空間Ｖ＊とにおいて実現される述語暗号処理における暗号文である暗号ベクトルｃ１を生成する暗号化装置であり、
前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾を取得するとともに、所定の属性情報を取得する公開鍵取得部と、
前記公開鍵取得部が取得した基底Ｂ＾におけるベクトルであって、基底ベクトルｂｎ＋１に対する係数として所定の情報を設定したベクトルを送信情報ベクトルζｖとして処理装置により生成する送信情報設定部と、
前記基底Ｂ＾の前記基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうちの少なくとも一部の基底ベクトルに対する係数として前記属性情報を設定した属性情報ベクトルを、前記送信情報設定部が生成した送信情報ベクトルζｖに加算して暗号ベクトルｃ１を処理装置により生成する暗号ベクトル生成部と
を備えることを特徴とする暗号化装置。
【請求項３３】
数４９に示すペアリング演算によって関連付けられた双対加群である空間Ｖと空間Ｖ＊とにおいて実現される述語暗号処理における暗号文を復号する復号装置であり、
前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾が公開鍵として与えられた場合に生成される暗号文である暗号ベクトルｃ１であって、前記基底Ｂ＾の基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうち少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，μｈ）に対する係数として属性情報が設定されるとともに、前記基底ベクトルｂｎ＋１に対する係数として所定の情報が設定されたベクトルである暗号ベクトルｃ１を入力するベクトル入力部と、
前記空間Ｖ＊における所定の基底Ｂ＊の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）のうち、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）の少なくとも基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）（μＬ≦μｈ）に対する係数として述語情報ｖｉ（ｉ＝１，．．．，μＬ）が設定され、基底ベクトルｂ＊ｎ＋１に対する係数として所定の値が設定された鍵ベクトルｋ＊Ｌ，ｄｅｃを記憶装置に記憶する鍵ベクトル記憶部と、
前記ベクトル入力部が入力した暗号ベクトルｃ１と、前記鍵ベクトル記憶部が記憶した鍵ベクトルｋ＊Ｌ，ｄｅｃとについて処理装置により数４９に示すペアリング演算を行い、前記暗号ベクトルｃ１から前記所定の情報に関する値を抽出するペアリング演算部と
を備えることを特徴とする復号装置。
【数４９】
2011141472.tif 000164
【請求項３４】
数５０に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Ｖと空間Ｖ＊とを用いて述語暗号処理を行う暗号処理方法であり、
処理装置が、前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾と、所定の属性情報とが公開鍵として与えられ、前記基底Ｂ＾の基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうちの少なくとも一部の基底ベクトルに対する係数として属性情報を設定するとともに、前記基底ベクトルｂｎ＋１に対する係数として所定の情報を設定したベクトルを暗号ベクトルｃ１として生成する暗号化ステップと、
処理装置が、前記空間Ｖ＊の基底Ｂ＊におけるベクトルであって、基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）うちの少なくとも一部の基底ベクトルに対する係数として述語情報を設定するとともに、前記基底Ｂ＊の基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして、前記暗号化装置が生成した暗号ベクトルｃ１と前記鍵ベクトルｋ＊Ｌ，ｄｅｃとについて、数５０に示すペアリング演算ｅ（ｃ１，ｋ＊Ｌ，ｄｅｃ）を行い前記暗号ベクトルｃ１を復号して前記所定の情報に関する値を抽出する復号ステップと
を備えることを特徴とする暗号処理方法。
【数５０】
2011141472.tif 000165
【請求項３５】
数５１に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Ｖと空間Ｖ＊とを用いて述語暗号処理を行う暗号処理プログラムであり、
処理装置が、前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾と、所定の属性情報とが公開鍵として与えられ、前記基底Ｂ＾の基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうちの少なくとも一部の基底ベクトルに対する係数として属性情報を設定するとともに、前記基底ベクトルｂｎ＋１に対する係数として所定の情報を設定したベクトルを暗号ベクトルｃ１として生成する暗号化処理と、
処理装置が、前記空間Ｖ＊の基底Ｂ＊におけるベクトルであって、基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）うちの少なくとも一部の基底ベクトルに対する係数として述語情報を設定するとともに、前記基底Ｂ＊の基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして、前記暗号化装置が生成した暗号ベクトルｃ１と前記鍵ベクトルｋ＊Ｌ，ｄｅｃとについて、数５１に示すペアリング演算ｅ（ｃ１，ｋ＊Ｌ，ｄｅｃ）を行い前記暗号ベクトルｃ１を復号して前記所定の情報に関する値を抽出する復号処理と
を備えることを特徴とする暗号処理プログラム。
【数５１】
2011141472.tif 000166
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、階層的述語鍵秘匿方式及び階層的述語暗号に関するものである。
【背景技術】
【０００２】
非特許文献１８には、ペアリング演算によって関連付けられた双対空間において階層的述語鍵秘匿方式及び階層的述語暗号を実現することが記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｂｅｔｈｅｎｃｏｕｒｔ，  Ｊ．，  Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：Ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ．Ｉｎ：  ２００７  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ，  ｐｐ．  ３２１−−３３４．  ＩＥＥＥ  Ｐｒｅｓｓ  （２００７）
【非特許文献２】Ｂｏｎｅｈ，  Ｄ．，  Ｂｏｙｅｎ，  Ｘ．：  Ｅｆｆｉｃｉｅｎｔ  ｓｅｌｅｃｔｉｖｅ−ＩＤ  ｓｅｃｕｒｅ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ｒａｎｄｏｍｏｒａｃｌｅｓ．Ｉｎ：  Ｃａｃｈｉｎ，  Ｃ．，  Ｃａｍｅｎｉｓｃｈ，  Ｊ．  （ｅｄｓ．）ＥＵＲＯＣＲＹＰＴ  ２００４．  ＬＮＣＳ，  ｖｏｌ．  ３０２７，  ｐｐ．  ２２３−−２３８．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２００４）
【非特許文献３】Ｂｏｎｅｈ，  Ｄ．，  Ｂｏｙｅｎ，  Ｘ．：  Ｓｅｃｕｒｅ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ．Ｉｎ：  Ｆｒａｎｋｌｉｎ，  Ｍ．Ｋ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００４．ＬＮＣＳ，  ｖｏｌ．  ３１５２，  ｐｐ．  ４４３−−４５９．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００４）
【非特許文献４】Ｂｏｎｅｈ，  Ｄ．，  Ｂｏｙｅｎ，  Ｘ．，  Ｇｏｈ，  Ｅ．：  Ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｃｏｎｓｔａｎｔ  ｓｉｚｅｃｉｐｈｅｒｔｅｘｔ．Ｉｎ：  Ｃｒａｍｅｒ，  Ｒ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００５．  ＬＮＣＳ，  ｖｏｌ．  ３４９４，  ｐｐ．  ４４０−−４５６．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００５）
【非特許文献５】Ｂｏｎｅｈ，  Ｄ．，  Ｆｒａｎｋｌｉｎ，  Ｍ．：  Ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  ｐａｉｒｉｎｇ．Ｉｎ：  Ｋｉｌｉａｎ，  Ｊ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００１．  ＬＮＣＳ，  ｖｏｌ．  ２１３９，  ｐｐ．  ２１３−−２２９．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００１）
【非特許文献６】Ｂｏｎｅｈ，  Ｄ．，  Ｈａｍｂｕｒｇ，  Ｍ．：  Ｇｅｎｅｒａｌｉｚｅｄ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ａｎｄ  ｂｒｏａｄｃａｓｔ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅ．  Ｉｎ：  Ｐｉｅｐｒｚｙｋ，  Ｊ．  （ｅｄ．）  ＡＳＩＡＣＲＹＰＴ  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ５３５０，  ｐｐ．  ４５５−−４７０．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００８）
【非特許文献７】Ｂｏｎｅｈ，  Ｄ．，  Ｗａｔｅｒｓ，  Ｂ．：Ｃｏｎｊｕｎｃｔｉｖｅ，  ｓｕｂｓｅｔ，  ａｎｄ  ｒａｎｇｅ  ｑｕｅｒｉｅｓ  ｏｎｅｎｃｒｙｐｔｅｄ  ｄａｔａ．  Ｉｎ：  Ｖａｄｈａｎ，  Ｓ．Ｐ．  （ｅｄ．）  ＴＣＣ  ２００７．  ＬＮＣＳ，  ｖｏｌ．  ４３９２，  ｐｐ．  ５３５−−５５４．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００７）
【非特許文献８】Ｂｏｙｅｎ，  Ｘ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ａｎｏｎｙｍｏｕｓ  ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  （ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ）．Ｉｎ：  Ｄｗｏｒｋ，  Ｃ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００６．  ＬＮＣＳ，  ｖｏｌ．  ４１１７，  ｐｐ．  ２９０−−３０７．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００６）
【非特許文献９】Ｃｏｃｋｓ，  Ｃ．：Ａｎ  ｉｄｅｎｔｉｔｙ  ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  ｑｕａｄｒａｔｉｃ  ｒｅｓｉｄｕｅｓ．Ｉｎ：  Ｈｏｎａｒｙ，  Ｂ．  （ｅｄ．）  ＩＭＡ  Ｉｎｔ．  Ｃｏｎｆ．  ＬＮＣＳ，  ｖｏｌ．  ２２６０，  ｐｐ．  ３６０−−３６３．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００１）
【非特許文献１０】Ｇｅｎｔｒｙ，  Ｃ．：Ｐｒａｃｔｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ．  Ｉｎ：  Ｖａｕｄｅｎａｙ，  Ｓ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００６．  ＬＮＣＳ，  ｖｏｌ．  ４００４，  ｐｐ．  ４４５−−４６４．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００６）
【非特許文献１１】Ｇｅｎｔｒｙ，  Ｃ．，  Ｈａｌｅｖｉ，  Ｓ．：  Ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｐｏｌｙｎｏｍｉａｌｌｙ  ｍａｎｙ  ｌｅｖｅｌｓ．  Ｉｎ：  Ｒｅｉｎｇｏｌｄ，  Ｏ．  （ｅｄ．）  ＴＣＣ  ２００９．ＬＮＣＳ，  ｖｏｌ．  ５４４４，  ｐｐ．  ４３７−−４５６．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００９）
【非特許文献１２】Ｇｅｎｔｒｙ，  Ｃ．，  Ｓｉｌｖｅｒｂｅｒｇ，  Ａ．：  Ｈｉｅｒａｒｃｈｉｃａｌ  ＩＤ−ｂａｓｅｄ  ｃｒｙｐｔｏｇｒａｐｈｙ．  Ｉｎ：  Ｚｈｅｎｇ，  Ｙ．  （ｅｄ．）  ＡＳＩＡＣＲＹＰＴ  ２００２．ＬＮＣＳ，  ｖｏｌ．  ２５０１，  ｐｐ．  ５４８−−５６６．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００２）
【非特許文献１３】Ｇｏｙａｌ，  Ｖ．，  Ｐａｎｄｅｙ，  Ｏ．，  Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｆｉｎｅ−ｇｒａｉｎｅｄ  ａｃｃｅｓｓ  ｃｏｎｔｒｏｌ  ｏｆ  ｅｎｃｒｙｐｔｅｄ  ｄａｔａ．  Ｉｎ：  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ２００６，  ｐｐ．  ８９−−９８，  ＡＣＭ  （２００６）
【非特許文献１４】Ｇｒｏｔｈ，  Ｊ．，  Ｓａｈａｉ，  Ａ．：  Ｅｆｆｉｃｉｅｎｔ  ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ  ｐｒｏｏｆ  ｓｙｓｔｅｍｓ  ｆｏｒ  ｂｉｌｉｎｅａｒ  ｇｒｏｕｐｓ．Ｉｎ：  Ｓｍａｒｔ，  Ｎ．Ｐ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００８．ＬＮＣＳ，  ｖｏｌ．  ４９６５，ｐｐ．  ４１５−−４３２．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００８）
【非特許文献１５】Ｈｏｒｗｉｔｚ，  Ｊ．，  Ｌｙｎｎ，  Ｂ．：Ｔｏｗａｒｄｓ  ｈｉｅｒａｒｃｈｉｃａｌ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ．  Ｉｎ：  Ｋｎｕｄｓｅｎ，  Ｌ．Ｒ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００２．ＬＮＣＳ，  ｖｏｌ．  ２３３２，  ｐｐ．  ４６６−−４８１．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００２）
【非特許文献１６】Ｋａｔｚ，  Ｊ．，  Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｓｕｐｐｏｒｔｉｎｇ  ｄｉｓｊｕｎｃｔｉｏｎｓ，ｐｏｌｙｎｏｍｉａｌ  ｅｑｕａｔｉｏｎｓ，  ａｎｄ  ｉｎｎｅｒ  ｐｒｏｄｕｃｔｓ．Ｉｎ：  Ｓｍａｒｔ，  Ｎ．Ｐ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００８．ＬＮＣＳ，  ｖｏｌ．  ４９６５，ｐｐ．  １４６−−１６２．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００８）
【非特許文献１７】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：Ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍｖｅｃｔｏｒ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ．Ｉｎ：  Ｇａｌｂｒａｉｔｈ，  Ｓ．Ｄ．，  Ｐａｔｅｒｓｏｎ，  Ｋ．Ｇ．  （ｅｄｓ．）  Ｐａｉｒｉｎｇ  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ５２０９，  ｐｐ．  ５７−−７４．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００８）
【非特許文献１８】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：Ａ  ｇｅｏｍｅｔｒｉｃ  ａｐｐｒｏａｃｈ  ｏｎ  ｐａｉｒｉｎｇｓ  ａｎｄ  ｈｉｅｒａｒｃｈｉｃａｌ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ．Ｉｎ：  Ｐｏｓｔｅｒ  ｓｅｓｓｉｏｎ，  ＥＵＲＯＣＲＹＰＴ  ２００９．（２００９）
【非特許文献１９】Ｏｓｔｒｏｖｓｋｙ，  Ｒ．，  Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ｎｏｎ−ｍｏｎｏｔｏｎｉｃ  ａｃｃｅｓｓｓｔｒｕｃｔｕｒｅｓ．Ｉｎ：ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ２００７，  ｐｐ．  １９５−−２０３，  ＡＣＭ，（２００７）
【非特許文献２０】Ｐｉｒｒｅｔｔｉ，  Ｍ．，  Ｔｒａｙｎｏｒ，  Ｐ．，  ＭｃＤａｎｉｅｌ，  Ｐ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｓｅｃｕｒｅ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｓｙｓｔｅｍｓ．Ｉｎ：ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ２００６，  ｐｐ．  ９９−−１１２，  ＡＣＭ，（２００６）
【非特許文献２１】Ｓａｈａｉ，  Ａ．，  Ｗａｔｅｒｓ，  Ｂ．：  Ｆｕｚｚｙ  ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ．  Ｉｎ：  Ｃｒａｍｅｒ，  Ｒ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００５．ＬＮＣＳ，  ｖｏｌ．  ３４９４，  ｐｐ．  ４５７−−４７３．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００５）
【非特許文献２２】Ｓｈｉ，  Ｅ．，  Ｗａｔｅｒｓ，  Ｂ．：Ｄｅｌｅｇａｔｉｎｇ  ｃａｐａｂｉｌｉｔｙ  ｉｎ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｓｙｓｔｅｍｓ．  Ｉｎ：  Ａｃｅｔｏ，  Ｌ．，  Ｄａｍｇａｒｄ，  Ｉ．，  Ｇｏｌｄｂｅｒｇ，  Ｌ．Ａ．，  Ｈａｌｌｄｏｒｓｓｏｎ，  Ｍ．Ｍ．，  Ｉｎｇｏｌｆｓｄｏｔｔｉｒ，  Ａ．，  Ｗａｌｕｋｉｅｗｉｃｚ，  Ｉ．  （ｅｄｓ．）ＩＣＡＬＰ  （２）  ２００８．ＬＮＣＳ，  ｖｏｌ．  ５１２６，  ｐｐ．  ５６０−−５７８．Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００８）
【非特許文献２３】Ｔａｋａｓｈｉｍａ，  Ｋ．：Ｅｆｆｉｃｉｅｎｔｌｙ  ｃｏｍｐｕｔａｂｌｅ  ｄｉｓｔｏｒｔｉｏｎ  ｍａｐｓ  ｆｏｒ  ｓｕｐｅｒｓｉｎｇｕｌａｒｃｕｒｖｅｓ．Ｉｎ：  ｖａｎ  ｄｅｒ  Ｐｏｏｒｔｅｎ，  Ａ．Ｊ．，  Ｓｔｅｉｎ，  Ａ．  （ｅｄｓ．）ＡＮＴＳ  ＶＩＩＩ，  ＬＮＣＳ，  ｖｏｌ．  ５０１１，  ｐｐ．  ８８−−１０１．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００８）
【非特許文献２４】Ｗａｔｅｒｓ，  Ｂ．：Ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ  ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ：  ａｎ  ｅｘｐｒｅｓｓｉｖｅ，  ｅｆｆｉｃｉｅｎｔ，  ａｎｄ  ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｒｅａｌｉｚａｔｉｏｎ．  ｅＰｒｉｎｔ，  ＩＡＣＲ，  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００８／２９０
【非特許文献２５】Ｔ．Ｏｋａｍｏｔｏ  ａｎｄ  Ｋ．Ｔａｋａｓｈｉｍａ，  “Ｈｉｅｒａｒｃｈｉｃａｌ  ｐｒｅｄｉｃａｔｅ  ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｉｎｎｅｒ−ｐｒｏｄｕｃｔｓ”，  Ａｓｉａｃｒｙｐｔ  ２００９，  ＬＮＣＳ  ｖｏｌ．  ５９１２，  ｐｐ．２１４−２３１．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００９）
【非特許文献２６】Ｂ．Ｗａｔｅｒｓ，  “Ｄｕａｌ  ｓｙｓｔｅｍ  ｅｎｃｒｙｐｔｉｏｎ  ：  Ｒｅａｌｉｚｉｎｇ  ｆｕｌｌｙ  ｓｅｃｕｒｅ  ＩＢＥ  ａｎｄ  ＨＩＢＥ  ｕｎｄｅｒ  ｓｉｍｐｌｅ  ａｓｓｕｍｐｔｉｏｎｓ”，  ＣＲＹＰＴＯ  ２００９，  ＬＮＣＳ  ｖｏｌ．  ５６７７，  ｐｐ．６１９−６３６．  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ（２００９）
【非特許文献２７】Ａ．Ｌｅｗｋｏ  ａｎｄ  Ｂ．Ｗａｔｅｒｓ，  “Ｎｅｗ  ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  ｄｕａｌ  ｓｙｓｔｅｍ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｆｕｌｌｙ  ｓｅｃｕｒｅ  ＨＩＢＥ  ｗｉｔｈ  ｓｈｏｒｔ  ｃｉｐｈｅｒｔｅｘｔｓ”，  ｅＰｒｉｎｔ，  ＩＡＣＲ，  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００９／４８２
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１８で提案されている階層的述語鍵秘匿方式及び階層的述語暗号は、理想化されたモデル（Ｇｅｎｅｒｉｃ  Ｍｏｄｅｌ）における安全性が証明されている。しかし、非特許文献１８で提案されている階層的述語鍵秘匿方式及び階層的述語暗号は、標準のモデル（Ｓｔａｎｄａｒｄ  Ｍｏｄｅｌ）における安全性は証明されていない。
この発明は、安全性が高い述語暗号及び述語鍵秘匿方式を提供することを目的とする。特に、権限委譲を可能とした述語暗号及び述語鍵秘匿方式を提供することを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る暗号処理システムは、例えば、
数１に示すペアリング演算によって関連付けられた双対ベクトル空間である空間Ｖと空間Ｖ＊とを用いて述語暗号処理を行う暗号処理システムであり、
前記空間Ｖにおける所定の基底Ｂを構成する基底ベクトルｂｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）（Ｎは３以上の整数，Ｓはｎ＋１以上Ｎ−１以下の整数，ｎは１以上Ｎ−２以下の整数）のうちの基底ベクトルｂｉ（ｉ＝Ｓ＋１，．．．，Ｎ）を除いた少なくとも基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋１）を有する基底Ｂ＾と、所定の属性情報とが公開鍵として与えられ、前記基底Ｂ＾の基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）のうちの少なくとも一部の基底ベクトルに対する係数として属性情報を設定するとともに、前記基底ベクトルｂｎ＋１に対する係数として所定の情報を設定したベクトルを暗号ベクトルｃ１として処理装置により生成する暗号化装置と、
前記空間Ｖ＊の基底Ｂ＊におけるベクトルであって、基底Ｂ＊を構成する基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ，．．．，Ｓ，．．．，Ｎ）の基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）うちの少なくとも一部の基底ベクトルに対する係数として述語情報を設定するとともに、前記基底Ｂ＊の基底ベクトルｂ＊ｎ＋１に対する係数として所定の値を設定したベクトルを鍵ベクトルｋ＊Ｌ，ｄｅｃとして、前記暗号化装置が生成した暗号ベクトルｃ１と前記鍵ベクトルｋ＊Ｌ，ｄｅｃとについて、処理装置により数１に示すペアリング演算ｅ（ｃ１，ｋ＊Ｌ，ｄｅｃ）を行い前記暗号ベクトルｃ１を復号して前記所定の情報に関する値を抽出する復号装置と
を備えることを特徴とする。
【数１】
2011141472.tif 000003
【発明の効果】
【０００６】
この発明に係る暗号システムによれば、安全性が高い述語暗号及び述語鍵秘匿方式を実現することができる。
【図面の簡単な説明】
【０００７】
【図１】「権限委譲（階層的な権限委譲）」という概念を説明するための図。
【図２】階層を飛ばした権限委譲を説明するための図。
【図３】属性情報と述語情報との階層構造を示す図。
【図４】階層的内積述語暗号の応用例である階層的ＩＤベース暗号の例を示す図。
【図５】基底と基底ベクトルとを説明するための図。
【図６】ベクトル空間における階層構造の実現方法の一例を説明するための図。
【図７】暗号処理システム１０の構成図。
【図８】暗号処理システム１０の鍵生成装置１００と第Ｌ層目の暗号化装置２００と復号装置３００との動作を示すフローチャート。
【図９】暗号処理システム１０の第Ｌ層目の鍵委譲装置４００と、第Ｌ＋１層目の暗号化装置２００と復号装置３００との動作を示すフローチャート。
【図１０】基底変換方法を説明するための図。
【図１１】実施の形態２に係る階層的述語暗号を実現する暗号処理システム１０の機能を示す機能ブロック図。
【図１２】実施の形態２に係る鍵生成装置１００の動作を示すフローチャート。
【図１３】実施の形態２に係る暗号化装置２００の動作を示すフローチャート。
【図１４】実施の形態２に係る復号装置３００の動作を示すフローチャート。
【図１５】実施の形態２に係る鍵委譲装置４００の動作を示すフローチャート。
【図１６】実施の形態２に係る双対ペアリングベクトル空間の基底の構造を示す概念図。
【図１７】実施の形態２に係る階層的述語鍵秘匿方式を実現する暗号処理システム１０の機能を示す機能ブロック図。
【図１８】実施の形態２に係る暗号化装置２００の動作を示すフローチャート。
【図１９】実施の形態２に係る復号装置３００の動作を示すフローチャート。
【図２０】実施の形態３に係る権限委譲が可能な述語暗号を実現する暗号処理システム１０の機能を示す機能ブロック図。
【図２１】鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【０００８】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するＣＰＵ９１１等である。記憶装置は後述するＲＯＭ９１３、ＲＡＭ９１４、磁気ディスク９２０等である。通信装置は後述する通信ボード９１５等である。入力装置は後述するキーボード９０２、通信ボード９１５等である。出力装置は後述するＲＡＭ９１４、磁気ディスク９２０、通信ボード９１５、ＬＣＤ９０１等である。つまり、処理装置、記憶装置、通信装置、入力装置、出力装置はハードウェアである。
【０００９】
以下の説明における記法について説明する。
Ａがランダムな変数または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
2011141472.tif 000004
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
2011141472.tif 000005
数１０３は、ｙがｚにより定義された集合であること、又はｙがｚを代入された集合であることを表す。
【数１０３】
2011141472.tif 000006
ａが定数であるとき、数１０４は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数１０４】
2011141472.tif 000007
ベクトル表記は、有限体Ｆｑにおけるベクトル表示を表す。つまり、数１０５である。
【数１０５】
2011141472.tif 000008
数１０６は、数１０７に示す２つのベクトルｘ→とｖ→との数１０８に示す内積を表す。
【数１０６】
2011141472.tif 000009
【数１０７】
2011141472.tif 000010
【数１０８】
2011141472.tif 000011
ＸＴは、行列Ｘの転置行列を表す。
【００１０】
また、以下の説明において、暗号処理とは、暗号化処理、復号処理、鍵生成処理を含むものであり、鍵秘匿処理も含むものである。
【００１１】
実施の形態１．
この実施の形態では、後の実施の形態で説明する「権限委譲を有する述語暗号（Ｐｒｅｄｉｃａｔｅ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｄｅｌｅｇａｔｉｏｎ）」や「権限委譲を有する述語鍵秘匿方式（Ｐｒｅｄｉｃａｔｅ  Ｋｅｙ  Ｅｎｃａｐｓｕｌａｔｉｏｎ  Ｍｅｃｈａｎｉｓｍ  ｗｉｔｈ  Ｄｅｌｅｇａｔｉｏｎ）」を実現する基礎となる概念と、権限委譲を有する述語暗号（述語鍵秘匿方式）の基本構成について説明する。
第１に、権限委譲を有する述語暗号（述語鍵秘匿方式）の一種である「権限委譲を有する内積述語暗号（内積述語鍵秘匿方式）」という概念を説明する。後の実施の形態で説明する権限委譲を有する述語暗号（述語鍵秘匿方式）は、権限委譲を有する内積述語暗号（内積述語鍵秘匿方式）である。権限委譲を有する内積述語暗号という概念を説明するに当たり、まず「権限委譲」という概念を説明する。また、併せて、「階層的（Ｈｉｅｒａｒｃｈｉａｌ）な権限委譲」という概念を説明する。次に、「内積述語暗号」を説明する。そして、階層的な権限委譲という概念を内積述語暗号に加えた「階層的内積述語暗号（階層的内積述語鍵秘匿方式）」を説明する。さらに、階層的内積述語暗号の理解を深めるため、階層的内積述語暗号の応用例を説明する。
第２に、ベクトル空間における階層的内積述語暗号を説明する。この実施の形態及び以下の実施の形態では、階層的述語暗号と階層的述語鍵秘匿方式とをベクトル空間において実現する。ここでは、まず、「基底」と「基底ベクトル」について説明する。次に、「ベクトル空間における内積述語暗号」について説明する。そして、「ベクトル空間における階層構造の実現方法」について説明する。さらに、理解を深めるため、階層構造の実現例を説明する。
第３に、この実施の形態及び後の実施の形態に係る「階層的述語暗号」と「階層的述語鍵秘匿方式」との基本構成を説明する。併せて、階層的述語暗号と階層的述語鍵秘匿方式とを実行する「暗号処理システム１０」の概要を説明する。
第４に、階層的述語鍵秘匿方式や階層的述語暗号を実現するための概念を説明する。ここでは、「双線形ペアリンググループ」、「ベクトル空間Ｖとベクトル空間Ｖ＊」、「標準的な双対基底Ａ，Ａ＊」、「ペアリング演算」、「基底変換」、「ディストーション写像」を説明する。
第５に、階層的述語鍵秘匿方式と階層的述語暗号とを実現するための空間である「双対ペアリングベクトル空間（Ｄｕａｌ  Ｐａｉｒｉｎｇ  Ｖｅｃｔｏｒ  Ｓｐａｃｅｓ，ＤＰＶＳ）」という豊かな数学的構造を有する空間を説明する。
そして、第６に、以上の説明を踏まえ、後の実施の形態で詳細に説明する階層的述語暗号と階層的述語鍵秘匿方式との実現方法を簡単に説明する。
【００１２】
＜第１．階層的内積述語暗号＞
＜第１−１．権限委譲（階層的な権限委譲）という概念＞
図１は、「権限委譲（階層的な権限委譲）」という概念を説明するための図である。
権限委譲とは、上位の鍵を有する利用者が、その鍵（上位の鍵）よりも機能が制限された下位の鍵を生成することである。
図１では、Ｒｏｏｔ（鍵生成装置）は、マスター秘密鍵を用いて、第１層目（Ｌｅｖｅｌ−１）の利用者へ秘密鍵を生成する。つまり、Ｒｏｏｔは、第１層目の利用者１，２，３それぞれへ鍵１，２，３を生成する。そして、例えば、利用者１であれば、鍵１を用いて、利用者１の下位（第１層目）の利用者である利用者１１，１２，１３それぞれへ鍵１１，１２，１３を生成することができる。ここで、利用者１が有する鍵１よりも、利用者１１，１２，１３が有する鍵１１，１２，１３は機能が制限されている。機能が制限されているとは、その秘密鍵によって復号できる暗号文が限定されているということである。つまり、上位の秘密鍵で復号できる暗号文の一部の暗号文のみ下位の秘密鍵で復号できることを意味する。すなわち、利用者１が有する鍵１で復号できる暗号文のうち、一部の暗号文のみ利用者１１，１２，１３が有する鍵１１，１２，１３で復号することができる。また、通常は、鍵１１と鍵１２と鍵１３とが復号できる暗号文は異なる。一方、鍵１１と鍵１２と鍵１３が復号できる暗号文は、鍵１で復号することができる。
また、図１に示すように、各秘密鍵が階層（レベル）分けされていることを「階層的」という。つまり、図１に示すように、階層的に下位の鍵を生成することを「階層的な権限委譲」と呼ぶ。
【００１３】
なお、図１では、Ｒｏｏｔが第１層目の利用者へ秘密鍵を生成し、第１層目の利用者が第２層目の利用者へ秘密鍵を生成し、第２層目の利用者が第３層目の利用者へ秘密鍵を生成すると説明した。しかし、図２に示すように、Ｒｏｏｔは、第１層目の利用者へ秘密鍵を生成するだけでなく、第２層目以下の層の利用者へ秘密鍵を生成することもできる。同様に、第１層目の利用者は、第２層目の利用者へ秘密鍵を生成するだけでなく、第３層目以下の層の利用者へ秘密鍵を生成することもできる。つまり、Ｒｏｏｔや利用者は、自分が持つ秘密鍵よりも下位の層の秘密鍵を生成することができる。
【００１４】
＜第１−２．内積述語暗号＞
次に、「内積述語暗号」について説明する。
まず、述語暗号とは、述語情報ｆｖに属性情報ｘを入力した場合に１（Ｔｒｕｅ）となる場合（ｆｖ（ｘ）＝１となる場合）に、暗号文を復号できる暗号方式である。通常、暗号文に属性情報ｘが埋め込まれ、秘密鍵に述語情報ｆｖが埋め込まれる。つまり、述語暗号では、属性情報ｘに基づき暗号化された暗号文ｃを、述語情報ｆｖに基づき生成された秘密鍵ＳＫｆにより復号する。述語暗号は、例えば、述語情報ｆｖが条件式であり、属性情報ｘがその条件式への入力情報であり、入力情報（属性情報ｘ）が条件式（述語情報ｆｖ）を満たせば（ｆｖ（ｘ）＝１）、暗号文を復号できる暗号方式であるとも言える。
なお、述語暗号について詳しくは非特許文献１６に記載されている。
【００１５】
内積述語暗号とは、属性情報ｘと述語情報ｆｖとの内積が所定の値の場合に、ｆｖ（ｘ）＝１となる述語暗号である。つまり、属性情報ｘと述語情報ｆｖとの内積が所定の値の場合にのみ、属性情報ｘにより暗号化された暗号文ｃを、述語情報ｆｖに基づき生成された秘密鍵ＳＫｆにより復号することができる。以下の説明では、属性情報ｘと述語情報ｆｖとの内積が０の場合に、ｆｖ（ｘ）＝１となるものとする。
【００１６】
＜第１−３．階層的内積述語暗号＞
階層的内積述語暗号（階層的内積述語鍵秘匿方式）とは、上述した「階層的な権限委譲」という概念を有する「内積述語暗号」である。
【００１７】
階層的内積述語暗号は、内積述語暗号に階層的な権限委譲システムを持たせるため、属性情報と述語情報とに階層構造を持たせる。
図３は、属性情報と述語情報との階層構造を示す図である。
図３において、符号が対応する属性情報と述語情報とは対応する（つまり、内積が０となる）ものとする。つまり、属性１と述語１との内積は０となり、属性１１と述語１１との内積は０となり、属性１２と述語１２との内積は０となり、属性１３と述語１３との内積は０となるとする。すなわち、属性１により暗号化された暗号文ｃ１は、述語１に基づき生成された秘密鍵ｋ１であれば復号できる。また、属性１１により暗号化された暗号文ｃ１１は、述語１１に基づき生成された秘密鍵ｋ１１であれば復号できる。属性１２と述語１２、属性１３と述語１３についても同様のことが言える。
上記の通り、階層的内積述語暗号は階層的な権限委譲システムを有する。そのため、述語１に基づき生成された秘密鍵ｋ１と、述語１１とに基づき、秘密鍵ｋ１１を生成することができる。つまり、上位の秘密鍵ｋ１を有する利用者は、その秘密鍵ｋ１と下位の述語１１とから、秘密鍵ｋ１の下位の秘密鍵ｋ１１を生成することができる。同様に、秘密鍵ｋ１と述語１２とから秘密鍵ｋ１２を生成でき、秘密鍵ｋ１と述語１３とから秘密鍵ｋ１３を生成できる。
また、下位の秘密鍵に対応する鍵（公開鍵）で暗号化された暗号文を上位の秘密鍵で復号できる。一方、上位の秘密鍵に対応する鍵（公開鍵）で暗号化された暗号文は、下位の秘密鍵で復号できない。つまり、属性１１、属性１２、属性１３により暗号化された暗号文ｃ１１、ｃ１２、ｃ１３は、述語１に基づき生成された秘密鍵ｋ１であれば復号できる。一方、属性１により暗号化された暗号文ｃ１は、述語１１、述語１２、述語１３に基づき生成された秘密鍵ｋ１１、ｋ１２、ｋ１３では復号できない。すなわち、属性１１、属性１２、属性１３と述語１との内積は０となる。一方、属性１と述語１１、述語１２、述語１３との内積は０とならない。
【００１８】
＜第１−４．階層的内積述語暗号の応用例＞
図４は、後述する階層的内積述語暗号の応用例である階層的ＩＤベース暗号（Ｈｉｅｒａｒｃｈｉａｌ  Ｉｄｅｎｔｉｆｉｅｒ  Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ，ＨＩＢＥ）の例を示す図である。なお、階層的ＩＤベース暗号とは、ＩＤベース暗号が階層的になった暗号処理である。ＩＤベース暗号は、述語暗号の一種であり、暗号文に含まれるＩＤと秘密鍵に含まれるＩＤとが一致する場合に暗号文を復号できるマッチング述語暗号である。
図４に示す例では、Ｒｏｏｔ（鍵生成装置）は、マスター秘密鍵ｓｋとＡ会社のＩＤである「Ａ」とに基づき、ＩＤ「Ａ」に対応する秘密鍵（鍵Ａ）を生成する。例えば、Ａ会社のセキュリティ担当者は、鍵Ａと各部門のＩＤとに基づき、そのＩＤに対応する秘密鍵を生成する。例えば、セキュリティ担当者は、営業部門のＩＤである「Ａ−１」に対応する秘密鍵（鍵１）を生成する。次に、例えば、各部門の管理者は、その部門の秘密鍵とその部門に属する各課のＩＤとに基づき、そのＩＤに対応する秘密鍵を生成する。例えば、営業部門の管理者は、営業１課のＩＤである「Ａ−１１」に対応する秘密鍵（鍵１１）を生成する。
ここで、営業１課のＩＤ「Ａ−１１」に対応する秘密鍵である鍵１１により、営業１課のＩＤ「Ａ−１１」で暗号化された暗号文を復号することができる。しかし、鍵１１により、営業２課や営業３課のＩＤで暗号化された暗号文は復号することはできない。また、鍵１１により、営業部門のＩＤで暗号化された暗号文は復号することができない。
営業部門のＩＤ「Ａ−１」に対応する秘密鍵である鍵１により、営業部門のＩＤ「Ａ−１」で暗号化された暗号文を復号することができる。また、鍵１により、営業部門に属する課のＩＤで暗号化された暗号文を復号することができる。つまり、鍵１により、営業１課、営業２課、営業３課のＩＤで暗号化された暗号文を復号することができる。しかし、鍵１により、製造部門（ＩＤ：Ａ−２）やスタッフ部門（ＩＤ：Ａ−３）のＩＤで暗号化された暗号文は復号することができない。また、鍵１により、Ａ会社のＩＤで暗号化された暗号文は復号することができない。
Ａ会社のＩＤ「Ａ」に対応する秘密鍵である鍵Ａにより、Ａ会社のＩＤ「Ａ」で暗号化された暗号文を復号することができる。また、Ａ会社に属する各部門や、その部門に属する課のＩＤで暗号化された暗号文を復号することができる。
【００１９】
階層的内積述語暗号は、ＩＤベース暗号以外へも様々な応用が可能である。特に、以下に説明する暗号処理は、等号関係テストのクラスに限定されたものではないため、非常に多くの応用が可能である。例えば、内積述語暗号の一種である検索可能暗号等についても、階層毎に検索可能な範囲をＡＮＤ条件やＯＲ条件等の条件式を用いて限定する等、従来の権限委譲システムを有する述語暗号では実現できなかった応用が可能である。
つまり、後の実施の形態で説明する階層的述語鍵秘匿方式と階層的述語暗号とは、ＩＤベース暗号や検索可能暗号等へ幅広い応用が可能である。
【００２０】
＜第２．ベクトル空間における階層的内積述語暗号＞
階層的述語鍵秘匿方式と階層的述語暗号とは、後述する双対ペアリングベクトル空間という高次元ベクトル空間において実現される。そこで、ベクトル空間における階層的内積述語暗号を説明する。
【００２１】
＜第２−１．基底と基底ベクトル＞
まず、ベクトル空間の説明において使用する「基底」と「基底ベクトル」とについて簡単に説明する。
図５は、基底と基底ベクトルとを説明するための図である。
図５は、２次元ベクトル空間におけるベクトルｖを示す。ベクトルｖは、ｃ１ａ１＋ｃ２ａ２である。また、ベクトルｖは、ｙ１ｂ１＋ｙ２ｂ２である。ここで、ａ１，ａ２を基底Ａにおける基底ベクトルといい、基底Ａ：＝（ａ１，ａ２）と表す。また、ｂ１，ｂ２を基底Ｂにおける基底ベクトルといい、基底Ｂ：＝（ｂ１，ｂ２）と表す。また、ｃ１，ｃ２，ｙ１，ｙ２は、各基底ベクトルに対する係数である。図５では、２次元ベクトル空間であったため、各基底における基底ベクトルは２個であった。しかし、Ｎ次元ベクトル空間であれば、各基底における基底ベクトルはＮ個である。
【００２２】
＜第２−２．ベクトル空間における内積述語暗号＞
次に、ベクトル空間における内積述語暗号を説明する。
上記の通り、内積述語暗号とは、属性情報ｘと述語情報ｆｖとの内積が所定の値（ここでは、０）の場合に、ｆｖ（ｘ）＝１となる述語暗号である。属性情報ｘと述語情報ｆｖとがベクトルであった場合、つまり属性ベクトルｘ→と述語ベクトルｖ→とであった場合、内積述語は数１０９のように定義される。
【数１０９】
2011141472.tif 000012
つまり、属性ベクトルｘ→と述語ベクトルｖ→との内積、つまり要素毎の内積の和が０である場合に、述語情報ｆｖに属性情報ｘを入力した結果が１（Ｔｒｕｅ）となる。また、属性ベクトルｘ→と述語ベクトルｖ→との内積が０でない場合に、述語情報ｆｖに属性情報ｘを入力した結果が０（Ｆａｌｓｅ）となる述語暗号である。
【００２３】
＜第２−３．ベクトル空間における階層構造の実現方法＞
次に、ベクトル空間における階層構造の実現方法を説明する。
図６は、ベクトル空間における階層構造の実現方法の一例を説明するための図である。
ここで扱うベクトル空間は、高次元（Ｎ次元）ベクトル空間であるとする。つまり、ベクトル空間における所定の基底Ｃには、基底ベクトルｃｉ（ｉ＝１，．．．，Ｎ）のＮ個の基底ベクトルが存在する。
Ｎ個の基底ベクトルのうちのｎ個の基底ベクトル（基底ベクトルｃｉ（ｉ＝1，．．．，ｎ））を階層構造を表すために使用する。また、基底ベクトルｃｉ（ｉ＝１，．．．，ｎ）を、基底ベクトルｃｉ（ｉ＝１，．．．，μ１）と、基底ベクトルｃｉ（ｉ＝μ１＋１，．．．，μ２）と、．．．、基底ベクトルｃｉ（ｉ＝μｄ−１＋１，．．．，ｎ）とのｄ個に分割する。ここで、ｄは、階層の深さを表す数となる。
そして、μ１個の基底ベクトルｃｉ（ｉ＝１，．．．，μ１）を第１層目の属性情報や述語情報を表すために割り当てる。また、μ２−μ１個の基底ベクトルｃｉ（ｉ＝μ１＋１，．．．，μ２）を第２層目の属性情報や述語情報を表すために割り当てる。以下同様に、μｄ−μｄ−１個の基底ベクトルｃｉ（ｉ＝μｄ−１＋１，．．．，μｄ（＝ｎ））を第ｄ層目の属性情報や述語情報を表すために割り当てる。
また、第Ｌ層目の属性情報によって暗号文を生成する場合には、第Ｌ層目の属性情報だけでなく、第１層目から第Ｌ層目までの属性情報を用いて暗号文を生成する。同様に、第Ｌ層目の述語情報によって秘密鍵を生成する場合には、第Ｌ層目の述語情報だけでなく、第１層目から第Ｌ層目までの述語情報を用いて秘密鍵を生成する。つまり、第Ｌ層目の属性情報によって暗号文を生成する場合や、第Ｌ層目の述語情報によって秘密鍵を生成する場合には、第１層目から第Ｌ層目までに割り当てられたμＬ個の基底ベクトルｃｉ（ｉ＝１，．．．，μＬ）を用いる。例えば、第３層目の属性情報によって暗号文を生成する場合には、第１層目から第３層目までに割り当てられたμ３個の基底ベクトルｃｉ（ｉ＝１，．．．，μ３）を用いて、第１層目から第３層目までの属性情報を用いて暗号文を生成する。同様に、第３層目の述語情報によって秘密鍵を生成する場合には、第１層目から第３層目までに割り当てられたμ３個の基底ベクトルｃｉ（ｉ＝１，．．．，μ３）を用いて、第１層目から第３層目までの述語情報を表して秘密鍵を生成する。つまり、下位の層で使用される属性情報や述語情報には、上位の層で使用される属性情報や述語情報が含まれる。これにより、属性情報と述語情報とに階層構造を持たせる。そして、この属性情報と述語情報とに階層構造を利用して、内積述語暗号に権限委譲システムを持たせる。
【００２４】
なお、以下の説明においては、ベクトル空間における階層的構造を示すために、階層情報μ→を用いる。階層情報μ→を数１１０に示す。
【数１１０】
2011141472.tif 000013
つまり、階層情報μ→は、階層構造を表すために割り当てられた基底ベクトル数（次元数）を示すｎと、階層の深さを示すｄと、各階層に割り当てられた基底ベクトルを示すためのμ１，．．．，μｄとの情報を有する。
【００２５】
次に、ベクトル空間における階層的内積述語暗号を説明する。
属性空間ΣＬ（Ｌ＝１，．．．，ｄ）を、第Ｌ層目の属性情報を表すために割り当てられた空間であるとする。ここで、各ΣＬは、数１１１である。
【数１１１】
2011141472.tif 000014
階層的な属性を数１１２に示すΣとする。ここで、和集合は互いに素な和集合である。
【数１１２】
2011141472.tif 000015
すると、数１１３に示す階層的な属性における数１１４に示す階層的な述語は、数１１５のように定義される。
【数１１３】
2011141472.tif 000016
【数１１４】
2011141472.tif 000017
【数１１５】
2011141472.tif 000018
階層的な述語空間を数１１６に示すＦとする。
【数１１６】
2011141472.tif 000019
また、数１１７のｈと数１１８のＬとを階層と呼ぶ。
【数１１７】
2011141472.tif 000020
【数１１８】
2011141472.tif 000021
【００２６】
＜第２−４．階層構造の実現例＞
ここで、簡単な例を用いて階層構造を説明する。ここでは、３つの階層を備え、各階層が２次元で構成された６次元空間を用いて説明する。つまり、μ→：＝（ｎ，ｄ；μ１，．．．，μｄ）＝（６，３；２，４，６）である。
第１層目の述語ベクトルｖ→１：＝（ｖ１，ｖ２）に基づき生成された第１層目の秘密鍵ｓｋ１を有する利用者は、第１層目の秘密鍵ｓｋ１と第２層目の述語ベクトルｖ→２：＝（ｖ３，ｖ４）に基づき第２層目の秘密鍵ｓｋ２を生成することができる。つまり、第２層目の秘密鍵ｓｋ２は、述語ベクトル（ｖ→１，ｖ→２）に基づき生成される。同様に、第２層目の秘密鍵ｓｋ２を有する利用者は、第２層目の秘密鍵ｓｋ２と第３層目の述語ベクトルｖ→３：＝（ｖ５，ｖ６）に基づき第３層目の秘密鍵ｓｋ３を生成することができる。つまり、第３層目の秘密鍵ｓｋ３は、述語ベクトル（ｖ→１，ｖ→２，ｖ→３）に基づき生成される。
第１層目の述語ベクトルｖ→１に基づき生成された第１層目の秘密鍵ｓｋ１は、（ｖ→１，（０，０），（０，０））により生成された秘密鍵である。そのため、第１層目の秘密鍵ｓｋ１は、属性ベクトル（ｘ→１，（＊，＊），（＊，＊））：＝（（ｘ１，ｘ２），（＊，＊），（＊，＊））により暗号化された暗号文を、ｖ→１・ｘ→１＝０である場合には復号できる。なぜなら、（＊，＊）・（０，０）＝０であるためである。ここで、“＊”は、任意の値を示す。
同様に、第２層目の述語ベクトル（ｖ→１，ｖ→２）に基づき生成された第２層目の秘密鍵ｓｋ２は、（ｖ→１，ｖ→２，（０，０））により生成された秘密鍵である。そのため、第２層目の秘密鍵ｓｋ２は、属性ベクトル（ｘ→１，ｘ→２，（＊，＊））：＝（（ｘ１，ｘ２），（ｘ３，ｘ４），（＊，＊））により暗号化された暗号文を、ｖ→１・ｘ→１＝０かつｖ→２・ｘ→２＝０である場合には復号できる。
しかし、第２層目の秘密鍵ｓｋ２は、第１層目の属性ベクトルｘ→１：＝（ｘ１，ｘ２）（つまり、（ｘ→１，（＊，＊），（＊，＊））により暗号化された暗号文を復号することはできない。なぜなら、ｖ→２＝（０，０）でなければ、（＊，＊）・ｖ→２≠０であり、ｖ→２・ｘ→２≠０であるためである。そのため、第２層目の秘密鍵ｓｋ２は、親である秘密鍵鍵ｓｋ２よりも限定された能力のみを有していると言える。
【００２７】
＜第３．階層的述語暗号と階層的述語鍵秘匿方式との構成＞
＜第３−１．階層的述語暗号＞
階層的述語暗号の構成を簡単に説明する。
階層的述語暗号は、Ｓｅｔｕｐ、ＧｅｎＫｅｙ、Ｅｎｃ、Ｄｅｃ、ＤｅｌｅｇａｔｅＬ（Ｌ＝１，．．．，ｄ−１）の５つの確率的多項式時間アルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムでは、セキュリティパラメータ１λと階層情報μ→とが入力され、マスター公開鍵ｐｋとマスター秘密鍵ｓｋとが出力される。マスター秘密鍵ｓｋは最も上位の鍵である。
（ＧｅｎＫｅｙ）
ＧｅｎＫｅｙアルゴリズムでは、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと数１１９に示す述語ベクトルが入力され、数１２０に示す第Ｌ層目の秘密鍵が出力される。
【数１１９】
2011141472.tif 000022
【数１２０】
2011141472.tif 000023
（Ｅｎｃ）
Ｅｎｃアルゴリズムでは、マスター公開鍵ｐｋと数１２１に示す属性ベクトルと平文情報ｍとが入力され、暗号文ｃが出力される。つまり、Ｅｎｃアルゴリズムでは、平文情報ｍを埋め込み、数１２１に示す属性ベクトルにより暗号化された暗号文ｃが出力される。
【数１２１】
2011141472.tif 000024
（Ｄｅｃ）
Ｄｅｃアルゴリズムでは、マスター公開鍵ｐｋと数１２２に示す第Ｌ層目の秘密鍵と暗号文ｃとが入力され、平文情報ｍ又は識別情報⊥が出力される。識別情報⊥とは、復号に失敗したことを示す情報である。つまり、Ｄｅｃアルゴリズムでは、暗号文ｃを第Ｌ層目の秘密鍵で復号して、平文情報ｍを抽出する。また、復号に失敗した場合には識別情報⊥を出力する。
【数１２２】
2011141472.tif 000025
（ＤｅｌｅｇａｔｅＬ）
ＤｅｌｅｇａｔｅＬでは、マスター公開鍵ｐｋと数１２３に示す第Ｌ層目の秘密鍵と数１２４に示す第Ｌ＋１層目の述語ベクトルとが入力され、数１２５に示す第Ｌ＋１層目の秘密鍵が出力される。つまり、ＤｅｌｅｇａｔｅＬアルゴリズムでは、下位の秘密鍵が出力される。
【数１２３】
2011141472.tif 000026
【数１２４】
2011141472.tif 000027
【数１２５】
2011141472.tif 000028
【００２８】
＜第３−２．階層的述語暗号＞
階層的述語鍵秘匿方式の構成を簡単に説明する。
階層的述語鍵秘匿方式は、階層的述語暗号と同様に、Ｓｅｔｕｐ、ＧｅｎＫｅｙ、Ｅｎｃ、Ｄｅｃ、ＤｅｌｅｇａｔｅＬ（Ｌ＝１，．．．，ｄ−１）の５つの確率的多項式時間アルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムでは、セキュリティパラメータ１λと階層情報μ→とが入力され、マスター公開鍵ｐｋとマスター秘密鍵ｓｋとが出力される。マスター秘密鍵ｓｋは最も上位の鍵である。
（ＧｅｎＫｅｙ）
ＧｅｎＫｅｙアルゴリズムでは、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと数１２６に示す述語ベクトルが入力され、数１２７に示す第Ｌ層目の秘密鍵が出力される。
【数１２６】
2011141472.tif 000029
【数１２７】
2011141472.tif 000030
（Ｅｎｃ）
Ｅｎｃアルゴリズムでは、マスター公開鍵ｐｋと数１２８に示す属性ベクトルとが入力され、暗号文ｃとセッション鍵Ｋとが出力される。つまり、Ｅｎｃアルゴリズムでは、所定の情報（ρ）を埋め込み、数１２８に示す属性ベクトルにより暗号化された暗号文ｃと、所定の情報（ρ）から生成したセッション鍵Ｋとが出力される。
【数１２８】
2011141472.tif 000031
（Ｄｅｃ）
Ｄｅｃアルゴリズムでは、マスター公開鍵ｐｋと数１２９に示す第Ｌ層目の秘密鍵と暗号文ｃとが入力され、セッション鍵Ｋ又は識別情報⊥が出力される。識別情報⊥とは、復号に失敗したことを示す情報である。つまり、Ｄｅｃアルゴリズムでは、暗号文ｃを第Ｌ層目の秘密鍵で復号して、所定の情報（ρ）に関する情報を抽出し、セッション鍵Ｋを生成する。また、復号に失敗した場合には識別情報⊥を出力する。
【数１２９】
2011141472.tif 000032
（ＤｅｌｅｇａｔｅＬ）
ＤｅｌｅｇａｔｅＬアルゴリズムでは、マスター公開鍵ｐｋと数１３０に示す第Ｌ層目の秘密鍵と数１３１に示す第Ｌ＋１層目の述語ベクトルとが入力され、数１３２に示す第Ｌ＋１層目の秘密鍵が出力される。つまり、ＤｅｌｅｇａｔｅＬアルゴリズムでは、下位の秘密鍵が出力される。
【数１３０】
2011141472.tif 000033
【数１３１】
2011141472.tif 000034
【数１３２】
2011141472.tif 000035
【００２９】
＜第３−３．暗号処理システム１０＞
暗号処理システム１０について説明する。暗号処理システム１０は、上述した階層的述語暗号と階層的述語鍵秘匿方式とのアルゴリズムを実行する。
図７は、暗号処理システム１０の構成図である。
暗号処理システム１０は、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００を備える。なお、ここでは、復号装置３００は、鍵委譲装置４００を備えるものとする。また、上述したように、暗号処理システム１０は、階層的な暗号処理を実行するものであるため、暗号処理システム１０は、複数の暗号化装置２００、複数の復号装置３００、複数の鍵委譲装置４００を備えるものとする。
鍵生成装置１００は、階層的述語鍵秘匿方式と階層的述語暗号とのＳｅｔｕｐ、ＧｅｎＫｅｙアルゴリズムを実行する。
暗号化装置２００は、階層的述語鍵秘匿方式と階層的述語暗号とのＥｎｃアルゴリズムを実行する。
復号装置３００は、階層的述語鍵秘匿方式と階層的述語暗号とのＤｅｃアルゴリズムを実行する。
鍵委譲装置４００は、階層的述語鍵秘匿方式と階層的述語暗号とのＤｅｌｅｇａｔｅＬアルゴリズムを実行する。
【００３０】
図８は、暗号処理システム１０の鍵生成装置１００と第Ｌ層目の暗号化装置２００と復号装置３００との動作を示すフローチャートである。つまり、図８は、マスター鍵（マスター公開鍵とマスター秘密鍵）の生成、第Ｌ層目の秘密鍵の生成から、第Ｌ層目における暗号化と復号とまでの動作を示すフローチャートである。
（Ｓ１０１：鍵生成ステップ）
鍵生成装置１００は、Ｓｅｔｕｐアルゴリズムを実行してマスター公開鍵ｐｋとマスター秘密鍵ｓｋとを生成する。また、鍵生成装置１００は、生成したマスター公開鍵ｐｋとマスター秘密鍵ｓｋと、所定の復号装置３００（第Ｌ層目の復号装置３００）に対応する述語ベクトルｖ→Ｌ（ｖ→Ｌ＝（ｖ１，．．．，ｖｉ）（ｉ＝μＬ））とに基づき、ＧｅｎＫｅｙアルゴリズムを実行して第Ｌ層目の秘密鍵を生成する。そして、鍵生成装置１００は、生成したマスター公開鍵ｐｋを公開（配布）するとともに、第Ｌ層目の秘密鍵を前記所定の復号装置３００へ秘密裡に配布する。なお、鍵生成装置１００は、マスター秘密鍵を秘密裡に保持する。
（Ｓ１０２：暗号化ステップ）
暗号化装置２００は、（Ｓ１０１）で鍵生成装置１００が配布したマスター公開鍵ｐｋと、前記復号装置３００の属性ベクトルｘ→Ｌ（ｘ→Ｌ＝（ｘ１，．．．，ｘｉ）（ｉ＝μＬ））とに基づき、Ｅｎｃアルゴリズムを実行して暗号文ｃを生成する。なお、階層的述語鍵秘匿方式であれば、暗号化装置２００は、セッション鍵Ｋも併せて生成する。そして、暗号化装置２００は、生成した暗号文ｃを前記復号装置３００へネットワーク等を介して送信する。なお、属性ベクトルｘ→Ｌは、公開されているものとしてもよいし、暗号化装置２００が鍵生成装置１００や復号装置３００から取得するものとしてもよい。
（Ｓ１０３：復号ステップ）
復号装置３００は、（Ｓ１０１）で鍵生成装置１００が配布したマスター公開鍵ｐｋと第Ｌ層目の秘密鍵とに基づき、アルゴリズムＤｅｃを実行して、暗号化装置２００から受信した暗号文ｃを復号する。復号装置３００は、暗号文ｃを復号した結果、階層的述語鍵秘匿方式であればセッション鍵Ｋを取得し、階層的述語暗号であれば平文情報ｍを取得する。復号装置３００は、復号に失敗した場合には識別情報⊥を出力する。
【００３１】
図９は、暗号処理システム１０の第Ｌ層目の鍵委譲装置４００と、第Ｌ＋１層目の暗号化装置２００と復号装置３００との動作を示すフローチャートである。つまり、図９は、第Ｌ＋１層目の秘密鍵の生成から、第Ｌ＋１層目における暗号化と復号とまでの動作を示すフローチャートである。
（Ｓ２０１：鍵委譲ステップ）
第Ｌ層目の鍵委譲装置４００（第Ｌ層目の復号装置３００が備える鍵委譲装置４００）は、（Ｓ１０１）で鍵生成装置１００が配布したマスター公開鍵ｐｋと、鍵生成装置１００又は第Ｌ−１層目の鍵委譲装置４００が配布した第Ｌ層目の秘密鍵と、第Ｌ＋１層目の復号装置３００に対応する述語ベクトルｖ→Ｌ＋１（ｖ→Ｌ＋１＝（ｖｉ，．．．，ｖｊ）（ｉ＝μＬ＋１，ｊ＝μＬ＋１））とに基づき、アルゴリズムＤｅｌｅｇａｔｅＬを実行して第Ｌ＋１層目の秘密鍵を生成する。そして、第Ｌ層目の鍵委譲装置４００は、生成した秘密鍵を第Ｌ＋１層目の復号装置３００へ秘密裡に配布する。
（Ｓ２０２：暗号化ステップ）
暗号化装置２００は、（Ｓ１０１）で鍵生成装置１００が配布したマスター公開鍵ｐｋと、第Ｌ＋１層目までの復号装置３００の属性ベクトルｘ→１から属性ベクトルｘ→Ｌ＋１（ｘ→ｉ（ｉ＝１，．．．，Ｌ＋１）（＝（ｘ１，．．．，ｘｉ）（ｉ＝μＬ＋１）））とに基づき、Ｅｎｃアルゴリズムを実行して暗号文ｃを生成する。なお、階層的述語鍵秘匿方式であれば、暗号化装置２００は、セッション鍵Ｋも併せて生成する。そして、暗号化装置２００は、生成した暗号文ｃを前記復号装置３００へネットワーク等を介して送信する。なお、属性ベクトルｘ→１から属性ベクトルｘ→Ｌ＋１（ｘ→ｉ（ｉ＝１，．．．，Ｌ＋１））は、公開されているものとしてもよいし、暗号化装置２００が鍵生成装置１００や復号装置３００から取得するものとしてもよい。
（Ｓ２０３：復号ステップ）
復号装置３００は、（Ｓ１０１）で鍵生成装置１００が配布したマスター公開鍵ｐｋと、（Ｓ２０１）で第Ｌ層目の鍵委譲装置４００が配布した秘密鍵とに基づき、アルゴリズムＤｅｃを実行して、暗号化装置２００から受信した暗号文ｃを復号する。復号装置３００は、暗号文ｃを復号した結果、階層的述語鍵秘匿方式であればセッション鍵Ｋを取得し、階層的述語暗号であれば平文情報ｍを取得する。
【００３２】
＜第４．階層的述語鍵秘匿方式と階層的述語暗号とを実現するための概念＞
次に、上述した階層的述語暗号と階層的述語鍵秘匿方式との各アルゴリズムを実現するために必要となる概念を説明する。
ここでは、非対称ペアリンググループの直積により後述する双対ペアリングベクトル空間を構成する例を用いて、暗号処理を実現する方法を説明する。しかし、双対ペアリングベクトル空間は、非対称ペアリンググループの直積により実現されるものに限定されない。つまり、他の方法により構成された双対ペアリングベクトル空間においても、以下に説明する暗号処理は実現可能である。なお、双対ペアリングベクトル空間の典型的な３つの例が、非特許文献１７に記載されている。
【００３３】
＜第４−１．双線形ペアリンググループ＞
双線形ペアリンググループ（ｑ，Ｇ１，Ｇ２，ＧＴ，ｇ１，ｇ２，ｇＴ）を説明する。
双線形ペアリンググループ（ｑ，Ｇ１，Ｇ２，ＧＴ，ｇ１，ｇ２，ｇＴ）は、位数ｑの３つの巡回群Ｇ１，Ｇ２，ＧＴの組である。ｇ１はＧ１の生成元であり、ｇ２はＧ２の生成元である。そして、双線形ペアリンググループ（ｑ，Ｇ１，Ｇ２，ＧＴ，ｇ１，ｇ２，ｇＴ）は、以下の非退化双線形ペアリングの条件を満たす。
（条件：非退化双線形ペアリング）
多項式時間で計算可能な数１３３に示す非退化双線形ペアリングが存在すること。
【数１３３】
2011141472.tif 000036
ここで、Ｇ１＝Ｇ２（＝：Ｇ）である場合、対象双線形ペアリングと呼ぶ。一方、Ｇ１≠Ｇ２である場合、非対称双線形ペアリングと呼ぶ。対象双線形ペアリングは、超特異（超）楕円曲線を用いて構築できる。一方、非対称双線形ペアリングは、どんな（超）楕円曲線を用いても構築できる。非対称双線形ペアリングは、例えば、通常の楕円曲線を用いて構築できる。
【００３４】
＜第４−２．ベクトル空間Ｖとベクトル空間Ｖ＊＞
１次元空間の巡回群を高次元空間（高次元ベクトル空間）へ拡張する。つまり、数１３４に示すように、Ｇ１とＧ２との直積によりＮ次元ベクトル空間ＶとＮ次元ベクトル空間Ｖ＊とを構築する。
【数１３４】
2011141472.tif 000037
【００３５】
＜第４−３．標準的な双対基底Ａ，Ａ＊＞
Ｎ次元ベクトル空間Ｖの標準基底Ａと、Ｎ次元ベクトル空間Ｖ＊の標準基底Ａ＊とを説明する。
数１３５は、標準基底Ａと標準基底Ａ＊とを示す。
【数１３５】
2011141472.tif 000038
標準基底Ａと標準基底Ａ＊とは、数１３６に示す条件を満たす。
【数１３６】
2011141472.tif 000039
つまり、標準基底Ａと標準基底Ａ＊とは、双対正規直交基底であり、空間Ｖと空間Ｖ＊とは、ペアリング演算ｅによって関連付けられた双対ベクトル空間である。
標準基底Ａと標準基底Ａ＊とが数１３６に示す条件を満たすことについて補足する。
まず、ｅ（ａｉ，ａ＊ｉ）＝ｇＴであることについて説明する。一例として、ｅ（ａ１，ａ＊１）について計算する。上記の通り、ａ１＝（ｇ１，０，．．．，０）であり、ａ＊１＝（ｇ２，０，．．．，０）である。したがって、ｅ（ａ１，ａ＊１）＝ｅ（ｇ１，ｇ２）×ｅ（０，０）×，．．．，×ｅ（０，０）である。ここで、上記の通り、ｅ（ｇ１，ｇ２）＝ｇＴである。また、ｅ（０，０）＝ｅ（０・ｇ１，０・ｇ２）＝ｅ（ｇ１，ｇ２）０であるから、ｅ（０，０）＝１である。したがって、ｅ（ａ１，ａ＊１）＝ｇＴとなる。他のｅ（ａｉ，ａ＊ｉ）についても同様の計算が成立し、ｅ（ａｉ，ａ＊ｉ）＝ｇＴとなる。
次に、ｅ（ａｉ，ａ＊ｊ）＝１（ｉ≠ｊ）であることについて説明する。一例として、ｅ（ａ１，ａ＊２）について計算する。上記の通り、ａ１＝（ｇ１，０，．．．，０）であり、ａ＊２＝（０，ｇ２，０，．．．，０）である。したがって、ｅ（ａ１，ａ＊２）＝ｅ（ｇ１，０）×ｅ（０，ｇ２）×ｅ（０，０）×，．．．，×ｅ（０，０）である。ｅ（ｇ１，０）＝ｅ（ｇ１，０・ｇ２）＝ｅ（ｇ１，ｇ２）０であるから、ｅ（ｇ１，０）＝１である。同様に、ｅ（０，ｇ２）＝１である。また、上記の通り、ｅ（０，０）＝１である。したがって、ｅ（ａｉ，ａ＊ｊ）＝１となる。他のｅ（ａｉ，ａ＊ｊ）についても同様の計算が成立し、ｅ（ａｉ，ａ＊ｊ）＝１となる。
したがって、標準基底Ａと標準基底Ａ＊とにおいて、ｅ（ａｉ，ａ＊ｉ）＝ｇＴであり、ｅ（ａｉ，ａ＊ｊ）＝１（ｉ≠ｊ）である。
【００３６】
＜第４−４．ペアリング演算＞
Ｎ次元ベクトル空間Ｖ，Ｖ＊におけるペアリング演算ｅを数１３７に示すように定義する。
【数１３７】
2011141472.tif 000040
つまり、Ｎ次元ベクトル空間Ｖのベクトルｘ：＝（ｘ１ｇ１，ｘ２ｇ１，．．．，ｘＮｇ１）とＮ次元ベクトル空間Ｖ＊のベクトルｙ：＝（ｙ１ｇ２，ｙ２ｇ２，．．．，ｙＮｇ２）とのペアリング演算ｅ（ｘ，ｙ）は、ベクトルｘとベクトルｙとの要素毎のペアリング演算の積と定義する。すると、上述した非退化双線形ペアリングの条件から、ペアリング演算ｅ（ｘ，ｙ）は、数１３８に示すように表すことができる。
【数１３８】
2011141472.tif 000041
【００３７】
＜第４−５．基底変換＞
標準基底Ａと標準基底Ａ＊とから他の基底Ｂと基底Ｂ＊とへ変換する基底変換方法について説明する。図１０は、基底変換方法を説明するための図である。
空間Ｖにおける標準基底Ａから空間Ｖにおける他の基底Ｂ：＝（ｂ１，．．．，ｂＮ）へ変換する。ここでは、数１３９に示す一様に選択された線形変換Ｘを用いて、数１４０に示すように空間Ｖにおける標準基底Ａから空間Ｖにおける他の基底Ｂに変換する。
【数１３９】
2011141472.tif 000042
【数１４０】
2011141472.tif 000043
ここで、ＧＬは、Ｇｅｎｅｒａｌ  Ｌｉｎｅａｒの略である。つまり、ＧＬは、一般線形群であり、行列式が０でない正方行列の集合であり、乗法に関し群である。
Ｘを用いることにより、空間Ｖ＊における標準基底Ａ＊から空間Ｖ＊における基底Ｂ＊：＝（ｂ＊１，．．．，ｂ＊Ｎ）を効率的に計算できる。ここでは、数１４１に示すようにＸを用いて、空間Ｖ＊における基底Ｂ＊を計算する。
【数１４１】
2011141472.tif 000044
【００３８】
ここで、数１４２が成立する。
【数１４２】
2011141472.tif 000045
つまり、基底Ｂと基底Ｂ＊とは、双対空間ＶとＶ＊における双対正規直交基底である。すなわち、Ｘを用いて標準基底ＡとＡ＊とを変形した場合であっても、双対正規直交基底は保存される。
【００３９】
＜第４−６．ディストーション写像＞
標準基底Ａにおける空間Ｖの生成元ｘに対するディストーション写像という線形変換について説明する。
空間Ｖの標準基底Ａにおけるディストーション写像φｉ，ｊは、数１４３に示す写像である。
【数１４３】
2011141472.tif 000046
数１４４が成立するため、ディストーション写像φｉ，ｊは、数１４５の変換を行うことができる。
【数１４４】
2011141472.tif 000047
【数１４５】
2011141472.tif 000048
つまり、標準基底Ａのベクトルｘの基底ベクトルｊの要素を基底ベクトルｉの要素へ変換することができる。この際、変換された基底ベクトルｊの要素を除く他の要素は、全て０となる。すなわち、ベクトルｘの基底ベクトルｊの要素が基底ベクトルｉの要素となり、その他の要素は０となる。
空間Ｖ＊の標準基底Ａ＊におけるディストーション写像φ＊ｉ，ｊも、空間Ｖの標準基底Ａにおけるディストーション写像φｉ，ｊと同様に表すことができる。
【００４０】
ディストーション写像φｉ，ｊ（φ＊ｉ，ｊ）を用いることにより、数１４６に示すＮ×Ｎ行列として表される線形変換Ｗであって、ｘ∈Ｖに対するどんな線形変換Ｗも数１４７によって効率的に計算することができる。
【数１４６】
2011141472.tif 000049
【数１４７】
2011141472.tif 000050
【００４１】
＜第５．双対ペアリングベクトル空間＞
第４で説明した概念を踏まえて、双対ペアリングベクトル空間について説明する。後述する階層的述語暗号と階層的述語鍵秘匿方式とは、双対ペアリングベクトル空間において実現される。
双対ペアリングベクトル空間（ｑ，Ｖ，Ｖ＊，ＧＴ，Ａ，Ａ＊）は、素数位数ｑと、Ｆｑ上の２つのＮ次元ベクトル空間Ｖ，Ｖ＊と、位数ｑの巡回群ＧＴと、空間Ｖの標準基底Ａ：＝（ａ１，．．．，ａＮ−１）と、空間Ｖ＊の標準基底Ａ＊：＝（ａ＊１，．．．，ａ＊Ｎ−１）とを有する空間である。そして、双対ペアリングベクトル空間（ｑ，Ｖ，Ｖ＊，ＧＴ，Ａ，Ａ＊）は、以下の（１）非退化双線形ペアリングが存在する、（２）標準基底Ａ，Ａ＊が双対正規直交基底である、（３）ディストーション写像が存在するという３つの条件を満たす空間である。
【００４２】
（１）非退化双線形ペアリング（上記第４−１参照）
多項式時間で計算可能な非退化双線形ペアリングｅが存在すること。
つまり、数１４８に示す非退化双線形ペアリングｅが存在することが１つ目の条件である。
【数１４８】
2011141472.tif 000051
【００４３】
（２）双対正規直交基底（上記第４−２参照）
空間Ｖの標準基底Ａと空間Ｖ＊の標準基底Ａ＊とが双対正規直交基底であること。
つまり、空間Ｖの標準基底Ａと空間Ｖ＊の標準基底Ａ＊とが、数１４９に示す条件を満たすことが２つ目の条件である。
【数１４９】
2011141472.tif 000052
【００４４】
（３）ディストーション写像（上記第４−６参照）
多項式時間で計算可能なディストーション写像φｉ，ｊとφ＊ｉ，ｊが存在すること。
つまり、数１５０に示す空間Ｖの準同型φｉ，ｊと空間Ｖ＊の準同型φ＊ｉ，ｊが多項式時間で計算可能であることが３つ目の条件である。
【数１５０】
2011141472.tif 000053
３つ目の条件を満たすことにより、空間Ｖと空間Ｖ＊とがペアリング演算ｅ（上記第４−２参照）によって関連付けられた双対空間であるということも言える。
【００４５】
＜第６．階層的述語暗号と階層的述語鍵秘匿方式との実現方法の概要＞
上述した概念（上記第４参照）と、双対ペアリングベクトル空間（上記第５参照）とを踏まえて、上述した暗号処理システム１０（上記第３参照）が階層的述語暗号と階層的述語鍵秘匿方式とを実現する方法を簡単に説明する。
【００４６】
まず、暗号処理システム１０により実現される内積述語暗号の概要について説明する。なお、説明の簡単のため、ここでは、階層的という概念を省略し、１階層のみで構成される内積述語暗号の概要について説明する。
暗号処理システム１０は、双対ペアリングベクトル空間（ｑ，Ｖ，Ｖ＊，ＧＴ，Ａ，Ａ＊）において内積述語暗号を実現する。なお、ここで、空間Ｖ，Ｖ＊は、いずれもｎ＋４次元空間である。
鍵生成装置１００は、第４−５で説明した基底変換により、標準基底Ａ，Ａ＊から正規直交基底Ｂ：＝（ｂ１，．．．，ｂｎ＋４）と、Ｂ＊：＝（ｂ＊１，．．．，ｂ＊ｎ＋４）とを生成する。鍵生成装置１００は、基底Ｂ：＝（ｂ１，．．．，ｂｎ＋４）のうちの基底ベクトル基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋２）からなる基底Ｂ＾：＝（ｂ１，．．．，ｂｎ＋２）を生成する。そして、基底Ｂ＾をマスター公開鍵ｐｋとし、基底Ｂ＊をマスター秘密鍵ｓｋとする。さらに、鍵生成装置１００は、述語ベクトルｖ→（ｖ→＝（ｖ１，．．．，ｖｎ）∈Ｆｎｑから秘密鍵ｋ＊を数１５１のように生成して復号装置３００へ秘密裡に送信する。
【数１５１】
2011141472.tif 000054
暗号化装置２００は、属性ベクトルｘ→（ｘ→＝（ｘ１，．．．，ｘｎ）∈Ｆｎｑと平文情報ｍとから、２つの暗号文ｃ１とｃ２とを生成する。暗号文ｃ１とｃ２とは数１５２のように生成される。
【数１５２】
2011141472.tif 000055
復号装置３００は、暗号文ｃ１，ｃ２と秘密鍵ｋ＊とに基づき、数１５３を計算して、平文情報ｍを抽出する。
【数１５３】
2011141472.tif 000056
ここで、ｖ→・ｘ→＝０であるなら、数１５４に示すように、数１５３を計算することにより、復号装置３００は平文情報ｍを得ることができる。
【数１５４】
2011141472.tif 000057
【００４７】
次に、階層的な権限委譲を可能にした内積述語暗号、つまり階層的内積述語暗号の概要について、簡単な例を用いて説明する。ここでは、３つの階層を備え、各階層が２次元で構成された６次元を述語ベクトルと属性ベクトルとに用い、その他に４次元を有する１０次元空間を用いて説明する。つまり、空間Ｖ，Ｖ＊は、１０次元空間である。したがって、マスター公開鍵に含まれる基底Ｂ＾：＝（ｂ１，．．．，ｂ６，ｂ７，ｂ８）である。また、マスター秘密鍵に含まれる基底Ｂ＊：＝（ｂ＊１，．．．，ｂ＊１０）である。
なお、以下の説明において、添え字の「ｄｅｃ」は「ｄｅｃｒｙｐｔｉｏｎ」の略であり、添え字に「ｄｅｃ」とあるものは、暗号文の復号に用いられる鍵ベクトルである。また、添え字の「ｒａｎ」は「ｒａｎｄｏｍｉｚａｔｉｏｎ」の略であり、添え字に「ｒａｎ」とあるものは、下位の鍵ベクトルの所定の基底ベクトルに対する係数をランダム化するためのランダム化ベクトルである。また、添え字の「ｄｅｌ」は「ｄｅｌｅｇａｔｉｏｎ」の略であり、添え字に「ｄｅｌ」とあるものは、下位の鍵ベクトルを生成するための鍵生成用ベクトルである。
【００４８】
ここで、暗号文ｃ１，ｃ２は、属性ベクトル（ｘ→１，ｘ→２，ｘ→３）：＝（（ｘ１，ｘ２），（ｘ３，ｘ４），（ｘ５，ｘ６））と平文情報ｍとにより、数１５５のように生成される。
【数１５５】
2011141472.tif 000058
もし、属性ベクトルが、ｘ→１：＝（ｘ１，ｘ２）のように高い階層である場合、属性ベクトルを数１５６のように修正する。
【数１５６】
2011141472.tif 000059
つまり、属性ベクトルｘ→１で生成された暗号文ｃ１は、数１５６に示す属性ベクトルｘ→＋で生成された暗号文ｃ１として生成される。
【００４９】
第１層目の述語ベクトルｖ→１：＝（ｖ１，ｖ２）∈Ｆ２ｑに基づき生成された第１層目の秘密鍵ｋ→＊１：＝（ｋ＊１，ｄｅｃ，ｋ＊１，ｒａｎ，１，ｋ＊１，ｒａｎ，２，ｋ＊１，ｄｅｌ，３，．．．，ｋ＊１，ｄｅｌ，６）は、ｋ＊１，ｄｅｃと、（ｋ＊１，ｒａｎ，１，ｋ＊１，ｒａｎ，２）と、（ｋ＊１，ｄｅｌ，３，．．．，ｋ＊１，ｄｅｌ，６）との３つの要素からなる。ここで、ｋ＊１，ｄｅｃは、暗号文の復号に用いられる鍵ベクトルである。（ｋ＊１，ｒａｎ，１，ｋ＊１，ｒａｎ，２）は、下位の鍵ベクトルの所定の基底ベクトルに対する係数をランダム化するためのランダム化ベクトルである。（ｋ＊１，ｄｅｌ，３，．．．，ｋ＊１，ｄｅｌ，６）は、下位の鍵ベクトルを生成するための鍵生成用ベクトルである。ｋ＊１，ｄｅｃと、（ｋ＊１，ｒａｎ，１，ｋ＊１，ｒａｎ，２）と、（ｋ＊１，ｄｅｌ，３，．．．，ｋ＊１，ｄｅｌ，６）とは、数１５７のように生成される。
【数１５７】
2011141472.tif 000060
暗号文ｃ１を生成する際用いられた属性ベクトルが、（ｘ１，ｘ２）・（ｖ１，ｖ２）＝０となる（（ｘ１，ｘ２），（＊，＊），（＊，＊））であるなら、数１５８であるため、ｋ＊１，０は、数１５９を計算することにより、暗号文ｃ１，ｃ２を復号することができる。
【数１５８】
2011141472.tif 000061
【数１５９】
2011141472.tif 000062
【００５０】
第２層目の述語ベクトルｖ→２：＝（ｖ３，ｖ４）により第２層目の秘密鍵ｋ→＊２：＝（ｋ＊２，ｄｅｃ，ｋ＊２，ｒａｎ，１，ｋ＊２，ｒａｎ，２，ｋ＊２，ｒａｎ，３，ｋ＊２，ｄｅｌ，５，ｋ＊２，ｄｅｌ，６）を生成する。
まず、ｋ＊２，ｄｅｃを生成する場合、σ２，０（ｖ３ｋ＊１，ｄｅｌ，３＋ｖ４ｋ＊１，ｄｅｌ，４）を、ｋ＊１，ｄｅｃに加える。ｋ＊２，ｒａｎ，ｊを生成する場合、σ２，ｊ（ｖ３ｋ＊１，ｄｅｌ，３＋ｖ４ｋ＊１，ｄｅｌ，４）を０に加える（ｊ＝１，２，３）。ｋ＊２，ｄｅｌ，ｊを生成する場合、σ２，ｊ（ｖ３ｋ＊１，ｄｅｌ，３＋ｖ４ｋ＊１，ｄｅｌ，４）をψ＋ｋ＊１，ｄｅｌ，ｊに加える（ｊ＝５，６）。ここで、σ２，ｊ（ｊ＝０，１，２，３，５，６）と、ψ＋とは一様に選択された値である。
また、第２層目の秘密鍵の（ｖ１ｂ＊１＋ｖ２ｂ＊２）とｂ＊７とｂ＊８との係数の値をランダム化する（一様に分布させる）。そこで、ｋ＊２，ｄｅｃを生成する場合、さらに（α０，１ｋ＊１，ｒａｎ，１＋α０，２ｋ＊１，ｒａｎ，２）を加える。ｋ＊２，ｒａｎ，ｊを生成する場合、（αｊ，１ｋ＊１，ｒａｎ，１＋αｊ，２ｋ＊１，ｒａｎ，２）を加える（ｊ＝１，２，３）。ｋ＊２，ｄｅｌ，ｊを生成する場合、（αｊ，１ｋ＊１，ｒａｎ，１＋αｊ，２ｋ＊１，ｒａｎ，２）を加える（ｊ＝５，６）。ここで、αｊ，１とαｊ，２と（ｊ＝０，１，２，３，５，６）は一様に選択された値である。
つまり、第２層目の秘密鍵鍵ｋ→＊２：＝（ｋ＊２，ｄｅｃ，ｋ＊２，ｒａｎ，１，ｋ＊２，ｒａｎ，２，ｋ＊２，ｒａｎ，３，ｋ＊２，ｄｅｌ，５，ｋ＊２，ｄｅｌ，６）が数１６０のように生成される。
【数１６０】
2011141472.tif 000063
なお、ｋ＊２，ｄｅｃは、暗号文の復号に用いられる鍵ベクトルである。（ｋ＊２，ｒａｎ，１，ｋ＊２，ｒａｎ，２，ｋ＊２，ｒａｎ，３）は、下位の鍵ベクトルの所定の基底ベクトルに対する係数をランダム化するためのランダム化ベクトルである。（ｋ＊２，ｄｅｌ，５，ｋ＊２，ｄｅｌ，６）は、下位の鍵の生成に用いられる。
【００５１】
一般に、第Ｌ層目の秘密鍵ｋ→＊Ｌ：＝（ｋ＊Ｌ，ｄｅｃ，ｋ＊Ｌ，ｒａｎ，ｊ，ｋ＊Ｌ，ｄｅｌ，ｊ）において、ｋ＊Ｌ，ｄｅｃは、暗号文の復号に用いられる鍵ベクトルである。ｋ＊Ｌ，ｒａｎ，ｊは、下位の鍵ベクトルの所定の基底ベクトルに対する係数をランダム化するためのランダム化ベクトルである。ｋ＊Ｌ，ｄｅｌ，ｊは、下位の鍵ベクトルを生成するための鍵生成用ベクトルである。
【００５２】
実施の形態２．
この実施の形態では、実施の形態１で説明した概念に基づき、階層的述語暗号を実現する暗号処理システム１０について説明する。
【００５３】
図１１から図１６に基づき、実施の形態２に係る暗号処理システム１０の機能と動作とについて説明する。
図１１は、階層的述語暗号を実現する暗号処理システム１０の機能を示す機能ブロック図である。暗号処理システム１０は、上述したように、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００を備える。また、ここでも、復号装置３００が鍵委譲装置４００を備えるものとする。
図１２は、鍵生成装置１００の動作を示すフローチャートである。図１３は、暗号化装置２００の動作を示すフローチャートである。図１４は、復号装置３００の動作を示すフローチャートである。図１５は、鍵委譲装置４００の動作を示すフローチャートである。
図１６は、双対ペアリングベクトル空間の基底の構造を示す概念図である。
【００５４】
鍵生成装置１００の機能と動作とについて説明する。鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、鍵ベクトル生成部１３０、ランダム化ベクトル生成部１４０、鍵生成用ベクトル生成部１５０、鍵配布部１６０を備える。
【００５５】
（Ｓ３０１：マスター鍵生成ステップ）
マスター鍵生成部１１０は、数１６１を計算して、マスター公開鍵ｐｋとマスター秘密鍵ｓｋとを処理装置により生成してマスター鍵記憶部１２０に記憶する。
【数１６１】
2011141472.tif 000064
つまり、（１）マスター鍵生成部１１０は、セキュリティパラメータ１λで、Ｎ（＝ｎ＋２＋ｓ＋ｒ）次元の双対ペアリングベクトル空間（ｑ，Ｖ，Ｖ＊，ＧＴ，Ａ，Ａ＊）を処理装置により生成する。ここで、Ｇｄｐｖｓは、１λとＮとを入力として、セキュリティパラメータ１λとＮ次元空間とについての双対ペアリングベクトル空間（ｑ，Ｖ，Ｖ＊，ＧＴ，Ａ，Ａ＊）を出力する双対ペアリングベクトル空間生成アルゴリズムである。また、ｎは１以上の整数、ｓは１以上の整数、ｒは０以上の整数である。また、ｎ＋２＝Ｒであり、ｎ＋２＋ｒ＝Ｓである。特に、（ｓ，ｒ）＝（１，０），（１，１），（ｎ，１），（１，ｎ），（ｎ，ｎ）の場合が重要である。ここで、ｎは２以上の任意の値である。ｓやｒが小さい値であれば効率がよくなり、ｓやｒが大きな値であれば安全性が高くなる。
（２）マスター鍵生成部１１０は、標準基底Ａから基底Ｂを生成するための線形変換Ｘを処理装置によりランダムに選択する。
（３）マスター鍵生成部１１０は、選択した線形変換Ｘに基づき、基底Ａ：＝（ａ１，．．．，ａＮ）から基底Ｂ：＝（ｂ１，．．．，ｂＮ）を処理装置により生成する。
（４）マスター鍵生成部１１０は、基底Ｂにおける基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋２）を有する基底ベクトルＢ＾：＝（ｂ１，．．．，ｂｎ，ｂｎ＋１，ｂｎ＋２）を処理装置により生成する。
（５）マスター鍵生成部１１０は、基底Ａ＊：＝（ａ＊１，．．．，ａ＊Ｎ）から基底Ｂ＊：＝（ｂ＊１，．．．，ｂ＊Ｎ）を生成するための線形変換（ＸＴ）−１を線形変換Ｘから処理装置により生成する。
（６）マスター鍵生成部１１０は、生成した線形変換（ＸＴ）−１に基づき、基底Ａ＊から基底Ｂ＊：＝（ｂ＊１，．．．，ｂ＊Ｎ）を処理装置により生成する。
（７）マスター鍵生成部１１０は、生成した線形変換Ｘと基底Ｂ＊とをマスター秘密鍵ｓｋとし、生成した基底Ｂ＾を含む（１λ，ｑ，Ｖ，Ｖ＊，ＧＴ，Ａ，Ａ＊，Ｂ＾）をマスター公開鍵ｐｋとする。そして、マスター鍵記憶部１２０は、マスター鍵生成部１１０が生成したマスター公開鍵ｐｋとマスター秘密鍵ｓｋとを記憶装置に記憶する。
なお、双対ペアリングベクトル空間の次元数は、Ｎ（＝ｎ＋２＋ｒ＋ｓ）であるとした。ここで、ｎは、階層情報μ→が有する階層構造をあらわすために割り当てられている基底数を表すｎである。つまり、ここでは、階層構造をあらわすために割り当てられている基底数ｎに加え、２＋ｒ＋ｓ個の基底ベクトルが設けられている。
図１６に示すように、Ｎ（＝ｎ＋２＋ｒ＋ｓ）個の基底ベクトルのうち、ｎ個の基底ベクトルが述語ベクトルや属性ベクトルのために割り当てられている。述語ベクトルや属性ベクトルのために割り当てられている基底ベクトルの構造は、図６に示す構造と同様である。残り２＋ｒ＋ｓ個の基底ベクトルのうちのｎ＋１番目の基底ベクトルは、セッション鍵を生成する情報のための基底ベクトルである。ｎ＋２番目の基底ベクトルは、暗号文ｃ１をランダム化するための基底ベクトルである。ｎ＋３番目からｎ＋２＋ｒ番目までの基底ベクトルは、鍵ｋ＊Ｌをランダム化するための基底ベクトルである。ｎ＋２＋ｒ＋１番目からｎ＋２＋ｒ＋ｓ番目までの基底ベクトルは、使用しない。
【００５６】
すなわち、（Ｓ３０１）において、マスター鍵生成部１１０は、数１６２に示すＳｅｔｕｐアルゴリズムを実行して、マスター公開鍵ｐｋとマスター秘密鍵ｓｋとを生成する。
【数１６２】
2011141472.tif 000065
【００５７】
（Ｓ３０２：鍵ベクトルｋ＊Ｌ，ｄｅｃ生成ステップ）
鍵ベクトル生成部１３０は、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと、数１６３に示す述語ベクトル（ｖ→１，．．．，ｖ→Ｌ）とに基づき、数１６４を計算して、第Ｌ層目（レベルＬ）の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ，ｄｅｃを処理装置により生成する。
【数１６３】
2011141472.tif 000066
【数１６４】
2011141472.tif 000067
つまり、（１）鍵ベクトル生成部１３０は、乱数σ０，ｉ（ｉ＝１，．．．，Ｌ）と乱数η０，ｈ（ｈ＝１，．．．，ｒ）とを処理装置により生成する。
（２）鍵ベクトル生成部１３０は、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として、生成した乱数σ０，ｔでランダム化した述語ベクトルの各要素を設定して、ベクトルｖｖを処理装置により生成する。つまり、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、述語ベクトルの各要素が埋め込まれる。
（３）鍵ベクトル生成部１３０は、基底ベクトルｂ＊ｉ（ｉ＝ｎ＋２＋１，．．．，ｎ＋２＋ｒ）に対する係数として、生成した乱数η０，ｈを設定して、ベクトルｒｖを処理装置により生成する。
（４）鍵ベクトル生成部１３０は、生成したベクトルｖｖとベクトルｒｖとを、基底ベクトルｂ＊ｎ＋１に対する係数として１を設定したベクトルに加算して、鍵ベクトルｋ＊Ｌ，ｄｅｃを生成する。
【００５８】
（Ｓ３０３：ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ生成ステップ）
ランダム化ベクトル生成部１４０は、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと、数１６３に示す述語ベクトル（ｖ→１，．．．，ｖ→Ｌ）とに基づき、数１６５を計算して、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）を生成する。ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）は、下位の鍵のうち、述語ベクトルの各要素が埋め込まれる基底ベクトルに対する係数を一様に分布させるためのベクトルである。なお、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊは、第Ｌ層目の秘密鍵のｊ番目の要素である。
【数１６５】
2011141472.tif 000068
つまり、（１）ランダム化ベクトル生成部１４０は、乱数σｊ，ｉ（ｊ＝１，．．．，Ｌ＋１；ｉ＝１，．．．，Ｌ）と乱数ηｊ，ｈ（ｊ＝１，．．．，Ｌ＋１；ｈ＝１，．．．，ｒ）とを処理装置により生成する。
（２）ランダム化ベクトル生成部１４０は、ｊ＝１，．．．，Ｌ＋１の各ｊについて、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として、乱数σｊ，ｔでランダム化した述語ベクトルの各要素を設定して、ベクトルｖｖｊを処理装置により生成する。つまり、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、述語ベクトルの各要素が埋め込まれる。
（３）ランダム化ベクトル生成部１４０は、ｊ＝１，．．．，Ｌ＋１の各ｊについて、基底ベクトルｂ＊ｉ（ｉ＝ｎ＋２＋１，．．．，ｎ＋２＋ｒ）に対する係数として、乱数ηｊ，ｈを処理装置により設定して、ベクトルｒｖｊを処理装置により生成する。
（４）ランダム化ベクトル生成部１４０は、ｊ＝１，．．．，Ｌ＋１の各ｊについて、生成したベクトルｖｖｊとベクトルｒｖｊと加算して、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）を生成する。
【００５９】
（Ｓ３０４：鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ生成ステップ）
鍵生成用ベクトル生成部１５０は、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと、数１６３に示す述語ベクトル（ｖ→１，．．．，ｖ→Ｌ）とに基づき、数１６６を計算して、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）を処理装置により生成する。鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）は、下位の秘密鍵（下位の鍵ベクトル）を生成するためのベクトルである。なお、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊは、第Ｌ層目の秘密鍵のｊ番目の要素である。
【数１６６】
2011141472.tif 000069
つまり、（１）鍵生成用ベクトル生成部１５０は、乱数σｊ，ｉ（ｊ＝μＬ＋１，．．．，ｎ；ｉ＝１，．．．，Ｌ）と乱数ψと乱数ηｊ，ｈ（ｊ＝μＬ＋１，．．．，ｎ；ｈ＝１，．．．，ｒ）とを処理装置により生成する。
（２）鍵生成用ベクトル生成部１５０は、ｊ＝μＬ＋１，．．．，ｎの各ｊについて、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数として、乱数σｊ，ｔでランダム化した述語ベクトルの各要素を設定して、ベクトルｖｖｊを処理装置により生成する。つまり、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、述語ベクトルの各要素が埋め込まれる。
（３）鍵生成用ベクトル生成部１５０は、ｊ＝μＬ＋１，．．．，ｎの各ｊについて、基底ベクトルｂ＊ｊに対する係数として乱数ψを設定して、ベクトルψｖｊを処理装置により生成する。
（４）鍵生成用ベクトル生成部１５０は、ｊ＝μＬ＋１，．．．，ｎの各ｊについて、基底ベクトルｂ＊ｉ（ｉ＝ｎ＋２＋１，．．．，ｎ＋２＋ｒ）に対する係数として、乱数ηｊ，ｈを処理装置により設定して、ベクトルｒｖｊを処理装置により生成する。
（５）鍵生成用ベクトル生成部１５０は、ｊ＝μＬ＋１，．．．，ｎの各ｊについて、ベクトルｖｖｊと、ベクトルψｖｊと、ベクトルｄｖｊとを加算して、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）を生成する。
【００６０】
すなわち、（Ｓ３０２）から（Ｓ３０４）において、鍵ベクトル生成部１３０とランダム化ベクトル生成部１４０と鍵生成用ベクトル生成部１５０とは、数１６７に示すＧｅｎＫｅｙアルゴリズムを処理装置により実行する。これにより、鍵ベクトルｋ＊Ｌ，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）と、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）とを含む第Ｌ層目の秘密鍵（鍵情報ｋ→＊Ｌ）が生成される。
【数１６７】
2011141472.tif 000070
【００６１】
（Ｓ３０５：鍵配布ステップ）
鍵配布部１６０は、マスター鍵生成部１１０が生成したマスター公開鍵と、鍵ベクトル生成部１３０とランダム化ベクトル生成部１４０と鍵生成用ベクトル生成部１５０とが生成した鍵情報ｋ→＊Ｌとを復号装置３００へ通信装置を介して送信する。また、鍵配布部１６０は、マスター公開鍵を暗号化装置２００へ通信装置を介して送信する。ここで、鍵情報ｋ→＊Ｌは秘密裡に復号装置３００へ送信されるが、鍵情報ｋ→＊Ｌを秘密裡に復号装置３００へ送信する方法に関しては、どのような方法であっても構わない。例えば、従来の暗号処理を使用して送信してもよい。
【００６２】
暗号化装置２００の機能と動作とについて説明する。暗号化装置２００は、送信情報設定部２１０、暗号ベクトル生成部２２０、暗号情報生成部２３０、データ送信部２４０、公開鍵取得部２５０を備える。
なお、以下の処理の前に、公開鍵取得部２５０は、マスター公開鍵ｐｋと、復号装置３００の述語情報ベクトルに対応する属性情報ベクトルを取得しているものとする。
【００６３】
（Ｓ４０１：送信情報設定ステップ）
送信情報設定部２１０は、マスター公開鍵ｐｋに基づき、数１６８を処理装置により計算して送信情報ベクトルζｖを生成する。
【数１６８】
2011141472.tif 000071
つまり、（１）送信情報設定部２１０は、乱数ζを処理装置により生成する。
（２）送信情報設定部２１０は、マスター公開鍵ｐｋに含まれる基底Ｂ＾の基底ベクトルｂｎ＋１に対する係数として乱数ζを処理装置により設定して、送信情報ベクトルζｖを生成する。
【００６４】
（Ｓ４０２：暗号ベクトルｃ１生成ステップ）
暗号ベクトル生成部２２０は、マスター公開鍵ｐｋと、数１６９に示す属性ベクトル（ｘ→１，．．．，ｘ→Ｌ）とに基づき、数１７０を処理装置により計算して暗号ベクトルｃ１を生成する。
【数１６９】
2011141472.tif 000072
【数１７０】
2011141472.tif 000073
つまり、（１）暗号ベクトル生成部２２０は、乱数（ｘ→Ｌ＋１，．．．，ｘ→ｄ）と、乱数δｉ（ｉ＝１，．．．，ｄ，ｎ＋２）を処理装置により生成する。
（２）暗号ベクトル生成部２２０は、マスター公開鍵ｐｋに含まれる基底Ｂの基底ベクトルｂｉ（ｉ＝１，．．．，μＬ）に対する係数として属性ベクトルの各要素を処理装置により設定する。つまり、基底ベクトルｂｉ（ｉ＝１，．．．，μＬ）に対する係数には、属性ベクトルの各要素が埋め込まれる。また、暗号ベクトル生成部２２０は、基底ベクトルｂｉ（ｉ＝μＬ＋１，．．．，ｎ）に対する係数として乱数を処理装置により設定する。これにより、暗号ベクトル生成部２２０は、ベクトルｘｖを生成する。
（３）暗号ベクトル生成部２２０は、マスター公開鍵ｐｋに含まれる基底Ｂの基底ベクトルｂｎ＋２に対する係数として乱数δｎ＋２を処理装置により設定して、ベクトルｒｖを生成する。
（４）暗号ベクトル生成部２２０は、生成したベクトルｘｖとベクトルｒｖとを、送信情報設定部２１０が生成した送信情報ベクトルζｖに加算して暗号ベクトルｃ１を処理装置により生成する。
なお、ベクトルｒｖは、安全性を高くするために加えられるものであり、必須の要素ではない。
【００６５】
（Ｓ４０３：暗号情報ｃ２生成ステップ）
暗号情報生成部２３０は、平文情報ｍに基づき、数１７１を処理装置により計算して暗号情報ｃ２を生成する。
【数１７１】
2011141472.tif 000074
【００６６】
（Ｓ４０４：データ送信ステップ）
データ送信部２４０は、暗号ベクトル生成部２２０が生成した暗号ベクトルｃ１と、暗号情報生成部２３０が生成した暗号情報ｃ２とを復号装置３００へ通信装置を介して送信する。
【００６７】
すなわち、暗号化装置２００は、数１７２に示すＥｎｃアルゴリズムを実行して、暗号ベクトルｃ１と暗号情報ｃ２とを生成する。
【数１７２】
2011141472.tif 000075
【００６８】
復号装置３００の機能と動作とについて説明する。復号装置３００は、ベクトル入力部３１０、鍵ベクトル記憶部３２０、ペアリング演算部３３０を備える。
【００６９】
（Ｓ５０１：ベクトル入力ステップ）
ベクトル入力部３１０は、暗号化装置２００のデータ送信部２４０が送信した暗号ベクトルｃ１と暗号情報ｃ２とを通信装置を介して受信して入力する。
【００７０】
（Ｓ５０２：復号ステップ）
ペアリング演算部３３０は、マスター公開鍵ｐｋと第Ｌ層目の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ，ｄｅｃとに基づき、数１７３を処理装置により計算して平文情報ｍ’を生成する。
【数１７３】
2011141472.tif 000076
つまり、ペアリング演算部３３０は、ベクトル入力部３１０が入力した暗号ベクトルｃ１と、鍵ベクトル記憶部３２０が記憶装置に記憶した鍵ベクトルｋ＊Ｌ，ｄｅｃとについて、ペアリング演算ｅを処理装置により行う。これにより、ペアリング演算部３３０は、ｇζＴを計算する。そして、計算したｇζＴで暗号情報ｃ２（＝ｇζＴｍ）を除することにより、平文情報ｍ’（＝ｍ）を計算する。なお、鍵ベクトル記憶部３２０は、鍵生成装置１００又は上位の鍵委譲装置４００から鍵ベクトルｋ＊Ｌ，ｄｅｃを配布された際、鍵ベクトルｋ＊Ｌ，ｄｅｃを記憶装置に記憶している。
ここで、暗号化装置２００が暗号化に用いた属性ベクトルｘ→ｉ（ｉ＝１，．．．，ｈ）と、復号装置３００が復号に用いた鍵ベクトルの述語ベクトルｖ→ｉ（ｉ＝１，．．．，Ｌ）とについて、Ｌ≦ｈであり、全てのｉ（ｉ＝１，．．．，Ｌ）についてｘ→ｉ・ｖ→ｉ＝０であれば、数１７４に示すように、暗号ベクトルｃ１と鍵ベクトルｋ＊Ｌ，ｄｅｃとについてペアリング演算ｅを行うことにより、ｇζＴを得ることができる。
【数１７４】
2011141472.tif 000077
【００７１】
つまり、復号装置３００は、数１７５に示すＤｅｃアルゴリズムを実行して、平文情報ｍ’を生成する。
【数１７５】
2011141472.tif 000078
【００７２】
鍵委譲装置４００の機能と動作とについて説明する。鍵委譲装置４００は、鍵ベクトル取得部４１０（鍵生成用ベクトル取得部）、鍵ベクトル生成部４２０、ランダム化ベクトル生成部４３０、鍵生成用ベクトル生成部４４０、鍵配布部４５０を備える。
【００７３】
（Ｓ６０１：鍵情報ｋ＊Ｌ取得ステップ）
鍵ベクトル取得部４１０は、第Ｌ層目の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）と、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）とを含む第Ｌ層目の秘密鍵（鍵情報ｋ→＊Ｌ）を通信装置を介して取得する。
【００７４】
（Ｓ６０２：鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ生成ステップ）
鍵ベクトル生成部４２０は、マスター公開鍵ｐｋと鍵情報ｋ→＊Ｌと数１７６に示す述語ベクトルｖ→Ｌ＋１とに基づき、数１７７を計算して、第Ｌ＋１層目の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを処理装置により生成する。
【数１７６】
2011141472.tif 000079
【数１７７】
2011141472.tif 000080
つまり、（１）鍵ベクトル生成部４２０は、乱数α０，ｉ（ｉ＝１，．．．，Ｌ＋１）と乱数σ０とを処理装置により生成する。
（２）鍵ベクトル生成部４２０は、ｉ＝１，．．．，Ｌ＋１の各ｉについて、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉの係数を乱数α０，ｉ倍したベクトルを加算して、ベクトルｒｖを処理装置により生成する。なお、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉ（ｉ＝１，．．．，Ｌ＋１）における基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、述語ベクトルの各要素が埋め込まれている。そのため、ベクトルｒｖにおける基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、乱数倍された述語ベクトルの各要素が埋め込まれる。
（３）鍵ベクトル生成部４２０は、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｉ（ｉ＝μＬ＋１，．．．，μＬ＋１）の係数に述語ベクトルｖ→Ｌ＋１の各要素を設定したベクトルを加算し、乱数σ０倍してベクトルｖｖを処理装置により生成する。つまり、基底ベクトルｂ＊ｉ（ｉ＝μＬ＋１，．．．，μＬ＋１）に対する係数には、述語ベクトルの各要素が埋め込まれる。
（４）鍵ベクトル生成部４２０は、鍵ベクトルｋ＊Ｌ，ｄｅｃと、ベクトルｒｖとベクトルｖｖとを加算して、鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを処理装置により生成する。
【００７５】
（Ｓ６０３：ランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊ生成ステップ）
ランダム化ベクトル生成部４３０は、マスター公開鍵ｐｋと鍵情報ｋ→＊Ｌと数１７６に示す述語ベクトルｖ→Ｌ＋１とに基づき、数１７８を計算して、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋２）を生成する。ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋２）は、下位の鍵のうち、述語ベクトルの各要素が埋め込まれる基底ベクトルに対する係数を一様に分布させるためのベクトルである。なお、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊは、第Ｌ＋１層目の秘密鍵のｊ番目の要素である。
【数１７８】
2011141472.tif 000081
つまり、（１）ランダム化ベクトル生成部４３０は、乱数αｊ，ｉ（ｊ＝１，．．．，Ｌ＋２；ｉ＝１，．．．，Ｌ）と乱数σｊ（ｊ＝１，．．．，Ｌ＋２）とを処理装置により生成する。
（２）ランダム化ベクトル生成部４３０は、ｊ＝１，．．．，Ｌ＋２の各ｊについて、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉ（ｉ＝１，．．．，Ｌ＋１）の係数を乱数αｊ，ｉ（ｉ＝１，．．．，Ｌ＋１）倍してベクトルｒｖｊを処理装置により生成する。上述したように、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉ（ｉ＝１，．．．，Ｌ＋１）における基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、述語ベクトルの各要素が埋め込まれている。そのため、ベクトルｒｖｊにおける基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、乱数倍された述語ベクトルの各要素が埋め込まれる。
（３）ランダム化ベクトル生成部４３０は、ｊ＝１，．．．，Ｌ＋２の各ｊについて、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｉ（ｉ＝μＬ＋１，．．．，μＬ＋１）の係数に述語ベクトルの各要素を設定したベクトルを加算し、乱数σｊ倍してベクトルｖｖｊを処理装置により生成する。つまり、基底ベクトルｂ＊ｉ（ｉ＝μＬ＋１，．．．，μＬ＋１）に対する係数には、述語ベクトルの各要素が埋め込まれる。
（４）ランダム化ベクトル生成部４３０は、ｊ＝１，．．．，Ｌ＋２の各ｊについて、生成したベクトルｒｖｊとベクトルｖｖｊとを加算して、ランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊを処理装置により生成する。
【００７６】
（Ｓ６０４：鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊ生成ステップ）
鍵生成用ベクトル生成部４４０は、マスター公開鍵ｐｋと鍵情報ｋ→＊Ｌと数１７６に示す述語ベクトルｖ→Ｌ＋１とに基づき、数１７９を計算して、鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊ（ｊ＝μＬ＋１＋１，．．．，ｎ）を処理装置により生成する。鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊ（ｊ＝μＬ＋１＋１，．．．，ｎ）は、下位の秘密鍵（下位の鍵ベクトル）を生成するためのベクトルである。なお、鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊは、第Ｌ＋１層目の秘密鍵のｊ番目の要素である。
【数１７９】
2011141472.tif 000082
つまり、（１）鍵生成用ベクトル生成部４４０は、乱数αｊ，ｉ（ｊ＝μＬ＋１＋１，．．．，ｎ；ｉ＝１，．．．，Ｌ＋１）と、乱数σｊ（ｊ＝μＬ＋１＋１，．．．，ｎ）と、乱数ψ’とを処理装置により生成する。
（２）鍵生成用ベクトル生成部４４０は、ｊ＝μＬ＋１＋１，．．．，ｎの各ｊについて、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉ（ｉ＝１，．．．，Ｌ＋１）の係数を乱数αｊ，ｉ倍したベクトルｒｖｊを処理装置により生成する。上述したように、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉ（ｉ＝１，．．．，Ｌ＋１）における基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、述語ベクトルの各要素が埋め込まれている。そのため、ベクトルｒｖｊにおける基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）に対する係数には、乱数倍された述語ベクトルの各要素が埋め込まれる。
（３）鍵生成用ベクトル生成部４４０は、ｊ＝μＬ＋１＋１，．．．，ｎの各ｊについて、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｉ（ｉ＝μＬ＋１，．．．，μＬ＋１）の係数に述語ベクトルの各要素を設定したベクトルを加算し、乱数σｊ倍してベクトルｖｖｊを処理装置により生成する。つまり、基底ベクトルｂ＊ｉ（ｉ＝μＬ＋１，．．．，μＬ＋１）に対する係数には、述語ベクトルの各要素が埋め込まれる。
（４）鍵生成用ベクトル生成部４４０は、ｊ＝μＬ＋１＋１，．．．，ｎの各ｊについて、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊの係数を乱数ψ’倍して、ベクトルψｖｊを処理装置により生成する。なお、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊにおける基底ベクトルｂ＊ｊ（ｊ＝μＬ＋１＋１，．．．，ｎ）に対する係数には、述語ベクトルの要素が埋め込まれている。そのため、ベクトルψｖｊ（ｊ＝μＬ＋１＋１，．．．，ｎ）における基底ベクトルｂ＊ｊに対する係数には、乱数倍された述語ベクトルの要素が埋め込まれる。
（５）鍵生成用ベクトル生成部４４０は、ｊ＝μＬ＋１＋１，．．．，ｎの各ｊについて、生成したベクトルｒｖｊと、ベクトルｖｖｊと、ベクトルψｖｊとを加算して、鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊ（ｊ＝μＬ＋１＋１，．．．，ｎ）を処理装置により生成する。
【００７７】
すなわち、（Ｓ６０２）から（Ｓ６０４）において、鍵ベクトル生成部４２０とランダム化ベクトル生成部４３０と鍵生成用ベクトル生成部４４０とは、数１８０に示すＤｅｌｅｇａｔｅＬアルゴリズムを実行して、鍵ベクトルｋ＊Ｌ＋１，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋２）と、鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊ（ｊ＝μＬ＋１＋１，．．．，ｎ）とを含む第Ｌ＋１層目の秘密鍵（鍵情報ｋ→＊Ｌ＋１）を処理装置により生成する。
【数１８０】
2011141472.tif 000083
【００７８】
（Ｓ６０５：鍵配布ステップ）
鍵配布部４４０は、鍵ベクトル生成部４２０とランダム化ベクトル生成部４３０と鍵生成用ベクトル生成部４４０とが生成した鍵情報ｋ→＊Ｌ＋１を下位の復号装置３００へ通信装置を介して送信する。ここで、鍵情報ｋ→＊Ｌ＋１は秘密裡に復号装置３００へ送信されるが、鍵情報ｋ→＊Ｌ＋１を秘密裡に復号装置３００へ送信する方法に関しては、どのような方法であっても構わない。例えば、従来の暗号処理を使用して送信してもよい。
【００７９】
以上のように、暗号処理システム１０が実現する暗号処理は、非特許文献１８で提案されている暗号処理よりも安全性が高く、標準のモデル（Ｓｔａｎｄａｒｄ  Ｍｏｄｅｌ）における安全性を証明することができる。
この理由は、主に以下の（１）から（３）の３点である。
（１）暗号処理に利用している空間ＶとＶ＊とは、Ｎ（＝ｎ＋２＋ｒ＋ｓ）次元であるのに対して、暗号化装置２００が暗号ベクトルｃ１を生成するのに利用している基底ベクトルは、基底ベクトルｂｉ（ｉ＝１，．．．，ｎ＋２）のｎ＋２次元のみである。また、復号装置３００が復号に利用している基底ベクトルは、基底ベクトル基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ＋２＋ｒ）のｎ＋２＋ｒ次元のみである。つまり、暗号処理では、空間ＶとＶ＊のうち、ｓ次元分（基底ベクトルｂｎ＋２＋ｒ＋１，．．．，ｂｎ＋２＋ｒ＋ｓ）を使用しない。言い替えれば、暗号処理で使用するｎ＋２＋ｒ次元の空間よりもｓ次元だけ次元数の多い空間においてマスター秘密鍵やマスター公開鍵が生成される。そのため、暗号処理で使用するｎ＋２＋ｒ次元の空間でマスター秘密鍵やマスター公開鍵を生成する場合に比べ、マスター秘密鍵やマスター公開鍵を生成するのに用いられる線形変換Ｘ等のランダム要素がｓ次元分だけ増える。ランダム要素が増えることにより安全性が高くなる。
（２）鍵生成装置１００が生成する鍵ベクトルｋ＊Ｌ，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）と、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）とにランダム要素が加えられている。つまり、鍵ベクトルｋ＊Ｌ，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）と、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）とのそれぞれに、基底ベクトルｂ＊ｎ＋３に乱数を設定している。鍵ベクトルｋ＊Ｌ，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）と、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）とにランダム要素が加えられることにより、安全性が高くなる。
（３）鍵委譲装置４００が下位の鍵を生成する場合に、ランダム化ベクトルを用いて生成する。これにより、下位の鍵の所定の基底ベクトルに対する係数をランダム化することができ、下位の鍵を生成することによって、鍵の安全性が劣化しない。
ここで、ランダム化ベクトルを用いない場合、鍵情報→ｋ＊Ｌから生成される２つの下位の鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ａ）と鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ｂ）とは、数１８１のようになる。
【数１８１】
2011141472.tif 000084
つまり、ランダム化ベクトルを用いない場合、鍵ベクトルｋ＊Ｌ，ｄｅｃに含まれる述語情報が設定された基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）の係数は、鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ａ）と鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ｂ）との間で共通になってしまう。
しかし、ランダム化ベクトルを用いる場合、鍵情報ｋ→＊Ｌから生成される２つの下位の鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ａ）と鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ｂ）とは、数１８２のようになる。
【数１８２】
2011141472.tif 000085
つまり、ランダム化ベクトルを用いる場合、鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ａ）には、乱数αＡ，ｉで係数の値を一様に分布したランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉが加えられ、鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ｂ）には、乱数αＢ，ｉで係数の値を一様に分布したランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉが加えられる。ここで、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｉには、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）が含まれている。したがって、鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ａ）と鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ｂ）とにおける基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）の係数の値は一様に分布している。つまり、鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ａ）と鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ（Ｂ）とにおいて、述語情報が設定された基底ベクトルｂ＊ｉ（ｉ＝１，．．．，μＬ）の係数は異なる。
【００８０】
また、上記説明では、Ｎ（＝ｎ＋２＋ｒ＋ｓ）次元ベクトル空間で暗号処理を実現したが、権限委譲のない暗号処理であれば、ｎは１以上の整数である。また、権限委譲を有する暗号処理であれば、ｎは２以上の整数である。また、ｒは０以上の整数である。また、ｓは１以上の整数である。
ｒが０の場合には、鍵ベクトルｋ＊Ｌ，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）と、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝μＬ＋１，．．．，ｎ）とにランダム要素が加えられない。
なお、上述したように、（Ｓ４０２）において、暗号化装置２００が基底ベクトルｂｎ＋２を用いて、ベクトルｒｖを生成することは必須ではない。ベクトルｒｖを生成しないのであれば、Ｎ（＝ｎ＋１＋ｒ＋ｓ）次元ベクトル空間で暗号処理を実現できる。
したがって、権限委譲のない暗号処理であれば、Ｎは２以上の整数であり、権限委譲を有する暗号処理であれば、Ｎは３以上の整数である。
【００８１】
また、上述した暗号処理では、双対ペアリングベクトル空間であることの条件に含まれていたディストーション写像を利用していない。ディストーション写像については、暗号処理を実現するアルゴリズムでは使用せず、暗号処理の安全性を証明するために使用する。したがって、上述した暗号処理は、ディストーション写像がない空間であっても成立するということができる。すなわち、上述した暗号処理を実現する空間にディストーション写像があることは、必須ではない。以下に説明する暗号処理についても同様である。
【００８２】
また、上記説明では、階層的述語暗号について説明した。次に、階層的述語鍵秘匿方式について説明する。階層的述語鍵秘匿方式について、上述した階層的述語暗号と異なる部分のみを説明する。
図１７は、階層的述語鍵秘匿方式を実現する暗号処理システム１０の機能を示す機能ブロック図である。
ここで、鍵生成装置１００の処理と鍵委譲装置４００の処理とは、上述した階層的述語暗号の場合と同様である。そこで、ここでは、暗号化装置２００の処理と復号装置３００の処理とのみを説明する。
図１８は、暗号化装置２００の動作を示すフローチャートである。図１９は、復号装置３００の動作を示すフローチャートである。
【００８３】
暗号化装置２００の機能と動作とについて説明する。
図１７に示す暗号化装置２００は、図１１に示す暗号化装置２００が備える機能に加え、セッション鍵生成部２６０を備える。なお、図１７に示す暗号化装置２００は、図１１に示す暗号化装置２００が備える暗号情報生成部２３０は備えていない。
（Ｓ７０１）と（Ｓ７０２）とは、（Ｓ４０１）と（Ｓ４０２）と同様である。
（Ｓ７０３：データ送信ステップ）では、（Ｓ７０２）で暗号ベクトル生成部２２０が生成した暗号ベクトルｃ１を復号装置３００へ通信装置を介して送信する。つまり、階層的述語鍵秘匿方式では、平文情報ｍを埋め込んだ暗号情報ｃ２は生成されず、復号装置３００へ送信されない。
（Ｓ７０４：セッション鍵生成ステップ）では、セッション鍵生成部２６０が数１８３を処理装置により計算してセッション鍵Ｋを生成する。
【数１８３】
2011141472.tif 000086
【００８４】
すなわち、暗号化装置２００は、数１８４に示すＥｎｃアルゴリズムを実行して、暗号ベクトルｃ１とセッション鍵Ｋとを生成する。
【数１８４】
2011141472.tif 000087
【００８５】
復号装置３００の機能と動作とについて説明する。
図１７に示す復号装置３００は、図１１に示す復号装置３００と同様の機能構成である。
（Ｓ８０１：ベクトル入力ステップ）
ベクトル入力部３１０は、暗号化装置２００のデータ送信部２４０が送信した暗号ベクトルｃ１を通信装置を介して受信して入力する。
【００８６】
（Ｓ８０２：復号ステップ）
ペアリング演算部３３０は、マスター公開鍵ｐｋと第Ｌ層目の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ，ｄｅｃとに基づき、数１８５を処理装置により計算してセッション鍵Ｋを生成する。
【数１８５】
2011141472.tif 000088
つまり、ペアリング演算部３３０は、ベクトル入力部３１０が入力した暗号ベクトルｃ１と、鍵ベクトル記憶部３２０が記憶装置に記憶した鍵ベクトルｋ＊Ｌ，ｄｅｃとについて、ペアリング演算ｅを処理装置により行う。これにより、ペアリング演算部３３０は、暗号化装置２００が埋め込んだζに関する値であるｇζＴ（＝Ｋ）を計算する。
【００８７】
すなわち、復号装置３００は、数１８６に示すＤｅｃアルゴリズムを実行して、セッション鍵Ｋ’（＝Ｋ）を生成する。
【数１８６】
2011141472.tif 000089
【００８８】
以上のように、階層的述語鍵秘匿方式によれば、暗号化装置２００から復号装置３００へ、セッション鍵Ｋを秘密裡に送信することができる。つまり、暗号化装置２００と復号装置３００との間でセッション鍵を共有することができる。
【００８９】
実施の形態３．
実施の形態３では、実施の形態２で説明した階層的述語暗号と階層的述語鍵秘匿方式とよりも一般化された権限委譲を有する述語暗号について説明する。
【００９０】
上述したように、実施の形態２で説明した階層的述語暗号と階層的述語鍵秘匿方式とでは、図１６に示すように基底ベクトルを使用した。つまり、ｎ＋２＋ｒ＋ｓ個の基底ベクトルのうち、ｎ個の基底ベクトルを属性ベクトルや述語ベクトルのための基底ベクトルとして、階層構造を表すために使用した。特に、初めのμ１個の基底ベクトルを第１層目の属性ベクトルや述語ベクトルのための基底ベクトルとし、μ２−μ１個の基底ベクトルを第２層目の属性ベクトルや述語ベクトルのための基底ベクトルとし、以下同様に、μＬ−μＬ−１個の基底ベクトルを第Ｌ層目の属性ベクトルや述語ベクトルのための基底ベクトルとした。
そして、第Ｌ層目の鍵ベクトルｋ＊Ｌ，ｄｅｃを数１６４に示すように計算した。つまり、第Ｌ層目の鍵ベクトルｋ＊Ｌ，ｄｅｃは、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，Ｌ）に対する係数として述語ベクトルの各要素を割り当てられ、基底ベクトルｂ＊ｉ（ｉ＝Ｌ＋１，．．．，ｎ）に対する係数として０を割り当てられた。
また、第Ｌ層目の暗号ベクトルｃ１を数１７０に示すように計算した。つまり、第Ｌ層目の暗号ベクトルｃ１は、基底ベクトルｂｉ（ｉ＝１，．．．，Ｌ）に対する係数として属性ベクトルの各要素を割り当てられ、基底ベクトルｂｉ（ｉ＝Ｌ＋１，．．．，ｎ）に対する係数として乱数を割り当てられた。
これにより、階層的に権限委譲することが実現された。
【００９１】
実施の形態３で説明する述語暗号（述語鍵秘匿方式）では、実施の形態２の場合と同様に、ｎ＋２＋ｒ＋ｓ個の基底ベクトルのうち、ｎ個の基底ベクトルを属性ベクトルや述語ベクトルのための基底ベクトルとして使用する。しかし、どの鍵であっても（上位の鍵であっても、下位の鍵であっても）、ｎ個の基底ベクトル全てを述語ベクトルのための基底ベクトルとする。つまり、ｎ個の基底ベクトル全てを常に属性ベクトルや述語ベクトルのための基底ベクトルとする。
そして、鍵ベクトルｋ＊Ｌ，ｄｅｃは、基底ベクトルｂ＊ｉ（ｉ＝１，．．．，ｎ）に対する係数として述語ベクトルの各要素を割り当てられる。また、第Ｌ層目の暗号ベクトルｃ１は、基底ベクトルｂｉ（ｉ＝１，．．．，ｎ）に対する係数として属性ベクトルの各要素を割り当てられる。
つまり、ｎ個の基底ベクトルについて階層構造という概念はない。また、秘密鍵が階層的に権限委譲される概念はない。そのため、実施の形態２で説明した暗号方式に比べ、より自由度の高い権限委譲が可能となる。
【００９２】
まず、権限委譲を有する述語暗号を実現する場合について説明する。
図２０は、権限委譲を有する述語暗号を実現する暗号処理システム１０の機能を示す機能ブロック図である。なお、図２０に示す暗号処理システム１０が備える機能は、図１１に示す暗号処理システム１０が備える機能と同様である。
権限委譲を有する述語暗号を実現する場合における実施の形態３に係る暗号処理システム１０の動作の流れは、実施の形態２に係る暗号処理システム１０の動作の流れと同様である。そこで、図２０と、図１２から図１６とに基づき、実施の形態３に係る暗号処理システム１０の機能と動作とについて説明する。
【００９３】
鍵生成装置１００の機能と動作とについて説明する。
（Ｓ３０１：マスター鍵生成ステップ）
実施の形態２における（Ｓ３０１）と同様に、マスター鍵生成部１１０は、数１８７を計算して、マスター公開鍵ｐｋとマスター秘密鍵ｓｋとを処理装置により生成してマスター鍵記憶部１２０に記憶する。
【数１８７】
2011141472.tif 000090
【００９４】
（Ｓ３０２：鍵ベクトルｋ＊Ｌ，ｄｅｃ生成ステップ）
鍵ベクトル生成部１３０は、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと、数１８８に示す述語ベクトル（ｖ→１，．．．，ｖ→Ｌ）とに基づき、数１８９を計算して、第Ｌ層目（レベルＬ）の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ，ｄｅｃを処理装置により生成する。
【数１８８】
2011141472.tif 000091
【数１８９】
2011141472.tif 000092
【００９５】
（Ｓ３０３：ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ生成ステップ）
ランダム化ベクトル生成部１４０は、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと、数１８８に示す述語ベクトル（ｖ→１，．．．，ｖ→Ｌ）とに基づき、数１９０を計算して、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）を生成する。
【数１９０】
2011141472.tif 000093
【００９６】
（Ｓ３０４：鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ生成ステップ）
鍵生成用ベクトル生成部１５０は、マスター公開鍵ｐｋとマスター秘密鍵ｓｋと、数１８８に示す述語ベクトル（ｖ→１，．．．，ｖ→Ｌ）とに基づき、数１９１を計算して、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝１，．．．，ｎ）を処理装置により生成する。
【数１９１】
2011141472.tif 000094
【００９７】
すなわち、（Ｓ３０２）から（Ｓ３０４）において、鍵ベクトル生成部１３０とランダム化ベクトル生成部１４０と鍵生成用ベクトル生成部１５０とは、数１９２に示すＧｅｎＫｅｙアルゴリズムを処理装置により実行する。これにより、鍵ベクトルｋ＊Ｌ，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）と、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝１，．．．，ｎ）とを含む第Ｌ層目の秘密鍵（鍵情報ｋ→＊Ｌ）が生成される。
【数１９２】
2011141472.tif 000095
【００９８】
（Ｓ３０５：鍵配布ステップ）
実施の形態２における（Ｓ３０５）と同様に、鍵配布部１６０は、マスター鍵生成部１１０が生成したマスター公開鍵と、鍵ベクトル生成部１３０とランダム化ベクトル生成部１４０と鍵生成用ベクトル生成部１５０とが生成した鍵情報ｋ→＊Ｌとを復号装置３００へ通信装置を介して送信する。また、鍵配布部１６０は、マスター公開鍵を暗号化装置２００へ通信装置を介して送信する。
【００９９】
暗号化装置２００の機能と動作とについて説明する。
（Ｓ４０１：送信情報設定ステップ）
実施の形態２における（Ｓ４０１）と同様に、送信情報設定部２１０は、マスター公開鍵ｐｋに基づき、数１９３を処理装置により計算して送信情報ベクトルζｖを生成する。
【数１９３】
2011141472.tif 000096
【０１００】
（Ｓ４０２：暗号ベクトルｃ１生成ステップ）
暗号ベクトル生成部２２０は、マスター公開鍵ｐｋと、数１９４に示す属性ベクトル（ｘ→１，．．．，ｘ→Ｌ）とに基づき、数１９５を処理装置により計算して暗号ベクトルｃ１を生成する。
【数１９４】
2011141472.tif 000097
【数１９５】
2011141472.tif 000098
【０１０１】
（Ｓ４０３：暗号情報ｃ２生成ステップ）
実施の形態２における（Ｓ４０３）と同様に、暗号情報生成部２３０は、平文情報ｍに基づき、数１９６を処理装置により計算して暗号情報ｃ２を生成する。
【数１９６】
2011141472.tif 000099
【０１０２】
（Ｓ４０４：データ送信ステップ）
実施の形態２における（Ｓ４０４）と同様に、データ送信部２４０は、暗号ベクトル生成部２２０が生成した暗号ベクトルｃ１と、暗号情報生成部２３０が生成した暗号情報ｃ２とを復号装置３００へ通信装置を介して送信する。
【０１０３】
すなわち、暗号化装置２００は、数１９７に示すＥｎｃアルゴリズムを実行して、暗号ベクトルｃ１と暗号情報ｃ２とを生成する。
【数１９７】
2011141472.tif 000100
【０１０４】
復号装置３００の機能と動作とについて説明する。
（Ｓ５０１：ベクトル入力ステップ）
実施の形態２における（Ｓ５０１）と同様に、ベクトル入力部３１０は、暗号化装置２００のデータ送信部２４０が送信した暗号ベクトルｃ１と暗号情報ｃ２とを通信装置を介して受信して入力する。
【０１０５】
（Ｓ５０２：復号ステップ）
実施の形態２における（Ｓ５０２）と同様に、ペアリング演算部３３０は、マスター公開鍵ｐｋと第Ｌ層目の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ，ｄｅｃとに基づき、数１９８を処理装置により計算して平文情報ｍ’を生成する。
【数１９８】
2011141472.tif 000101
ここで、暗号化装置２００が暗号化に用いた属性ベクトルｘ→ｉ（ｉ＝１，．．．，ｈ）と、復号装置３００が復号に用いた鍵ベクトルの述語ベクトルｖ→ｊ（ｊ＝１，．．．，Ｌ）とについて、全てのｉ（ｉ＝１，．．．，ｈ）、ｊ（ｊ＝１，．．．，Ｌ）についてｘ→ｉ・ｖ→ｊ＝０であるなら、ペアリング演算部３３０は、平文情報ｍを生成することができる。なお、平文情報ｍ∈ＧＴであるとする。
【０１０６】
つまり、復号装置３００は、数１９９に示すＤｅｃアルゴリズムを実行して、平文情報ｍ’を生成する。
【数１９９】
2011141472.tif 000102
【０１０７】
鍵委譲装置４００の機能と動作とについて説明する。
（Ｓ６０１：鍵情報ｋ→＊Ｌ取得ステップ）
実施の形態２における（Ｓ６０１）と同様に、鍵ベクトル取得部４１０は、第Ｌ層目の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋１）と、鍵生成用ベクトルｋ＊Ｌ，ｄｅｌ，ｊ（ｊ＝１，．．．，ｎ）とを含む第Ｌ層目の秘密鍵（鍵情報ｋ→＊Ｌ）を通信装置を介して取得する。
【０１０８】
（Ｓ６０２：鍵ベクトルｋ＊Ｌ＋１，ｄｅｃ生成ステップ）
鍵ベクトル生成部４２０は、マスター公開鍵ｐｋと鍵情報ｋ→＊Ｌと数２００に示す述語ベクトルｖ→Ｌ＋１とに基づき、数２０１を計算して、第Ｌ＋１層目の秘密鍵の先頭要素である鍵ベクトルｋ＊Ｌ＋１，ｄｅｃを処理装置により生成する。
【数２００】
2011141472.tif 000103
【数２０１】
2011141472.tif 000104
【０１０９】
（Ｓ６０３：ランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊ生成ステップ）
ランダム化ベクトル生成部４３０は、マスター公開鍵ｐｋと鍵情報ｋ→＊Ｌと数２００に示す述語ベクトルｖ→Ｌ＋１とに基づき、数２０２を計算して、ランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋２）を生成する。
【数２０２】
2011141472.tif 000105
【０１１０】
（Ｓ６０４：鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊ生成ステップ）
鍵生成用ベクトル生成部４４０は、マスター公開鍵ｐｋと鍵情報ｋ→＊Ｌと数２００に示す述語ベクトルｖ→Ｌ＋１とに基づき、数２０３を計算して、鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊ（ｊ＝１，．．．，ｎ）を処理装置により生成する。
【数２０３】
2011141472.tif 000106
【０１１１】
すなわち、（Ｓ６０２）から（Ｓ６０４）において、鍵ベクトル生成部４２０とランダム化ベクトル生成部４３０と鍵生成用ベクトル生成部４４０とは、数２０４に示すＤｅｌｅｇａｔｅＬアルゴリズムを実行して、鍵ベクトルｋ＊Ｌ＋１，ｄｅｃと、ランダム化ベクトルｋ＊Ｌ＋１，ｒａｎ，ｊ（ｊ＝１，．．．，Ｌ＋２）と、鍵生成用ベクトルｋ＊Ｌ＋１，ｄｅｌ，ｊ（ｊ＝１，．．．，ｎ）とを含む第Ｌ＋１層目の秘密鍵（鍵情報ｋ→＊Ｌ＋１）を処理装置により生成する。
【数２０４】
2011141472.tif 000107
【０１１２】
（Ｓ６０５：鍵配布ステップ）
実施の形態２における（Ｓ６０５）と同様に、鍵配布部４５０は、鍵ベクトル生成部４２０とランダム化ベクトル生成部４３０と鍵生成用ベクトル生成部４４０とが生成した鍵情報ｋ→＊Ｌ＋１を下位の復号装置３００へ通信装置を介して送信する。
【０１１３】
上述したように、暗号化装置２００が暗号化に用いた属性ベクトルｘ→ｊ（ｉ＝１，．．．，ｈ）と、復号装置３００が復号に用いた鍵ベクトルｋ＊Ｌ，ｄｅｃの述語ベクトルｖ→ｉ（ｊ＝１，．．．，Ｌ）とについて、全てのｉ（ｉ＝１，．．．，ｈ）、ｊ（ｊ＝１，．．．，Ｌ）についてｘ→ｉ・ｖ→ｊ＝０であるなら、復号装置３００は復号することができる。つまり、述語ベクトル（ｖ→１）に基づき生成された鍵ベクトルｋ＊１，ｄｅｃで復号する場合、ｘ→・ｖ→１＝０であるなら、復号装置３００は復号することができる。また、述語ベクトル（ｖ→１，ｖ→２）に基づき生成された鍵ベクトルｋ＊２，ｄｅｃで復号する場合、ｘ→・ｖ→１＝０かつｘ→・ｖ→２＝０であるなら、復号装置３００は復号することができる。つまり、実施の形態２で説明したアルゴリズムと同様に、下位の鍵ベクトルｋ＊２，ｄｅｃは、上位の鍵ベクトルｋ＊１，ｄｅｃよりも機能が制限されている。
【０１１４】
また、実施の形態２と同様に、暗号化装置２００が実行するＥｎｃアルゴリズムと、復号装置３００が実行するＤｅｃアルゴリズムとを、それぞれ数２０５と数２０６とのように変更することで、階層的述語鍵秘匿方式を実現することも可能である。
【数２０５】
2011141472.tif 000108
【数２０６】
2011141472.tif 000109
【０１１５】
実施の形態４．
以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。この実施の形態では、双対加群において暗号処理を実現する方法について説明する。
【０１１６】
つまり、以上の実施の形態では、素数位数ｑの巡回群において暗号処理を実現した。しかし、合成数Ｍを用いて数２０７のように環Ｒを表した場合、環Ｒを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数２０７】
2011141472.tif 000110
【０１１７】
例えば、実施の形態２で説明した階層的述語暗号を、環Ｒを係数とする加群において実現すると数２０８から数２１２のようになる。
【数２０８】
2011141472.tif 000111
【数２０９】
2011141472.tif 000112
【数２１０】
2011141472.tif 000113
【数２１１】
2011141472.tif 000114
【数２１２】
2011141472.tif 000115
【０１１８】
ここでは、実施の形態２で説明した階層的述語暗号についてのみ、環Ｒを係数とする加群において実現する方法を示した。しかし、原則として、以上の実施の形態で体Ｆｑとして説明した処理を、環Ｒに置き換えることにより、以上の実施の形態で説明した他の暗号処理についても、環Ｒを係数とする加群において実現できる。
【０１１９】
次に、実施の形態における暗号処理システム１０（鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００）のハードウェア構成について説明する。
図２１は、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００のハードウェア構成の一例を示す図である。
図２１に示すように、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。
【０１２０】
ＲＯＭ９１３、磁気ディスク装置９２０は、不揮発性メモリの一例である。ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３とＲＡＭ９１４と磁気ディスク装置９２０とは、記憶装置（メモリ）の一例である。また、キーボード９０２、通信ボード９１５は、入力装置の一例である。また、通信ボード９１５は、通信装置（ネットワークインタフェース）の一例である。さらに、ＬＣＤ９０１は、表示装置の一例である。
【０１２１】
磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【０１２２】
プログラム群９２３には、上記の説明において「マスター鍵生成部１１０」、「マスター鍵記憶部１２０」、「鍵ベクトル生成部１３０」、「ランダム化ベクトル生成部１４０」、「鍵生成用ベクトル生成部１５０」、「鍵配布部１６０」、「送信情報設定部２１０」、「暗号ベクトル生成部２２０」、「暗号情報生成部２３０」、「データ送信部２４０」、「公開鍵取得部２５０」、「セッション鍵生成部２６０」、「ベクトル入力部３１０」、「鍵ベクトル記憶部３２０」、「ペアリング演算部３３０」、「鍵ベクトル取得部４１０」、「鍵ベクトル生成部４２０」、「ランダム化ベクトル生成部４３０」、「鍵生成用ベクトル生成部４４０」、「鍵配布部４５０」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、上記の説明において「マスター公開鍵ｐｋ」、「マスター秘密鍵ｓｋ」、「暗号ベクトルｃ」、「鍵ベクトル」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【０１２３】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【０１２４】
１０  暗号処理システム、１００  鍵生成装置、１１０  マスター鍵生成部、１２０  マスター鍵記憶部、１３０  鍵ベクトル生成部、１４０  ランダム化ベクトル生成部、１５０  鍵生成用ベクトル生成部、１６０  鍵配布部、２００  暗号化装置、２１０  送信情報設定部、２２０  暗号ベクトル生成部、２３０  暗号情報生成部、２４０  データ送信部、２５０  公開鍵取得部、２６０  セッション鍵生成部、３００  復号装置、３１０  ベクトル入力部、３２０  鍵ベクトル記憶部、３３０  ペアリング演算部、４００  鍵委譲装置、４１０  鍵ベクトル取得部、４２０  鍵ベクトル生成部、４３０  ランダム化ベクトル生成部、４４０  鍵生成用ベクトル生成部、４５０  鍵配布部。
【図１】
2011141472.tif 000167
【図２】
2011141472.tif 000168
【図３】
2011141472.tif 000169
【図４】
2011141472.tif 000170
【図５】
2011141472.tif 000171
【図６】
2011141472.tif 000172
【図７】
2011141472.tif 000173
【図８】
2011141472.tif 000174
【図９】
2011141472.tif 000175
【図１０】
2011141472.tif 000176
【図１１】
2011141472.tif 000177
【図１２】
2011141472.tif 000178
【図１３】
2011141472.tif 000179
【図１４】
2011141472.tif 000180
【図１５】
2011141472.tif 000181
【図１６】
2011141472.tif 000182
【図１７】
2011141472.tif 000183
【図１８】
2011141472.tif 000184
【図１９】
2011141472.tif 000185
【図２０】
2011141472.tif 000186
【図２１】
2011141472.tif 000187