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