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