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