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