【手続補正書】
【提出日】平成25年11月14日(2013.11.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１
【補正方法】変更
【補正の内容】
【請求項１】
鍵生成装置と署名装置と検証装置とを備え、ｔ＝０，．．．，ｄ＋１（ｄは１以上の整数）の各整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理システムであり、
前記鍵生成装置は、
ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについて、識別情報ｔと、属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ，ｎｔは１以上の整数）とを含む属性集合Γを入力する第１情報入力部と、
基底Ｂ＊０の基底ベクトルｂ＊０，１の係数として所定の値δを設定した鍵要素ｋ＊０を生成する鍵要素０生成部と、
前記第１情報入力部が入力した属性集合Γに含まれる各識別情報ｔについて、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，ｎｔ）の係数として属性情報ｘ→ｔに前記所定の値δを乗じたδｘｔ，ｉ（ｉ＝１，．．．，ｎｔ）を設定した鍵要素ｋ＊ｔを生成する鍵要素ｔ生成部と、
基底Ｂ＊ｄ＋１の基底ベクトルｂ＊ｄ＋１，１の係数として前記所定の値δを設定した鍵要素ｋ＊ｄ＋１，１と、基底Ｂ＊ｄ＋１の基底ベクトルｂ＊ｄ＋１，２の係数として前記所定の値δを設定した鍵要素ｋ＊ｄ＋１，２とを生成する鍵要素ｄ＋１生成部と、
前記鍵要素０生成部が生成した鍵要素ｋ＊０と、前記鍵要素ｔ生成部が生成した前記属性集合Γに含まれる各識別情報ｔについての鍵要素ｋ＊ｔと、前記鍵要素ｄ＋１生成部が生成した鍵要素ｋ＊ｄ＋１，１及び鍵要素ｋ＊ｄ＋１，２と、前記属性集合Γとを含む署名鍵ｓｋΓを前記署名装置へ送信する署名鍵送信部と
を備え、
前記署名装置は、
ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍと、メッセージｍとを入力する第２情報入力部と、
前記署名鍵送信部が送信した署名鍵ｓｋΓを取得する署名鍵取得部と、
前記第２情報入力部が入力した変数ρ（ｉ）と、前記署名鍵取得部が取得した署名鍵ｓｋΓに含まれる属性集合Γとに基づき、ｉ＝１，．．．，Ｌの各整数ｉのうち、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）であり、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性集合Γに含まれるｘ→ｔとの内積が０となるｉと、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）であり、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性集合Γに含まれるｘ→ｔとの内積が０とならないｉとの集合Ｉを特定するとともに、特定した集合Ｉに含まれるｉについて、前記第２情報入力部が入力した行列Ｍのｉ行目の要素であるＭｉに基づき、αｉＭｉを合計した場合に所定のベクトルｈ→となる補完係数αｉを計算する補完係数計算部と、
前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊０を含む署名要素ｓ＊０を生成する署名要素０生成部と、
ｉ＝１，．．．，Ｌの各整数ｉについて、前記補完係数計算部が特定した集合Ｉに含まれる整数ｉであり、かつ、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉとし、前記集合Ｉに含まれるｉであり、かつ、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉ／（ｖ→ｉ・ｘ→ｔ）とし、前記集合Ｉに含まれない整数ｉの場合には値γｉ：＝０として、前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊ｔに前記値γｉを乗じたγｉｋ＊ｔを含む署名要素ｓ＊ｉを生成する署名要素ｉ生成部と、
前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊ｄ＋１，１と、前記メッセージｍを用いて生成される値ｍ’を前記鍵要素ｋ＊ｄ＋１，２に乗じたｍ’・ｋ＊ｄ＋１，２との和を含む署名要素ｓ＊Ｌ＋１を生成する署名要素Ｌ＋１生成部と、
前記署名要素０生成部が生成した署名要素ｓ＊０と、前記署名要素ｉ生成部が生成したｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、前記署名要素Ｌ＋１生成部が生成した署名要素ｓ＊Ｌ＋１と、前記メッセージｍと、前記変数ρ（ｉ）と、前記行列Ｍとを含む署名データσを前記検証装置へ送信する署名データ送信部と
を備え、
前記検証装置は、
前記署名データ送信部が送信した署名データσを取得するデータ取得部と、
ｒ個の要素を有するベクトルｆ→と前記ベクトルｈ→とを用いて生成される値ｓ０：＝ｈ→・ｆ→Ｔと、所定の値ｓＬ＋１とから計算される−ｓ０−ｓＬ＋１を、基底Ｂ０の基底ベクトルｂ０，１の係数として設定して検証要素ｃ０を生成する検証要素０生成部と、
前記ベクトルｆ→と前記データ取得部が取得した署名データσに含まれる行列Ｍとに基づき生成される列ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔ：＝Ｍ・ｆ→Ｔと、ｉ＝１，．．．，Ｌの各整数ｉについての所定の値θｉとを用いて、ｉ＝１，．．．，Ｌの各整数ｉについて、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底Ｂｔの基底ベクトルｂｔ，１の係数としてｓｉ＋θｉｖｉ，１を設定し、基底ベクトルｂｔ，ｉ’（ｉ’＝２，．．．，ｎｔ）の係数としてθｉｖｉ，ｉ’（ｉ’＝２，．．．，ｎｔ）を設定して検証要素ｃｉを生成し、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底ベクトルｂｔ，ｉ’（ｉ’＝１，．．．，ｎｔ）の係数としてｓｉｖｉ，ｉ’（ｉ’＝１，．．．，ｎｔ）を設定して検証要素ｃｉを生成する検証要素ｉ生成部と、
基底Ｂｄ＋１の基底ベクトルｂｄ＋１，１の係数として、前記所定の値ｓＬ＋１と前記値ｍ’と所定の値θＬ＋１とから計算されるｓＬ＋１−θＬ＋１ｍ’を設定し、基底ベクトルｂｄ＋１，２の係数として前記所定の値θＬ＋１を設定して検証要素ｃＬ＋１を生成する検証要素Ｌ＋１生成部と、
前記検証要素０生成部が生成した検証要素ｃ０と、前記検証要素ｉ生成部が生成した検証要素ｃｉと、前記検証要素Ｌ＋１生成部が生成した検証要素ｃＬ＋１と、前記署名データσに含まれる署名要素ｓ＊０，ｓ＊ｉ，ｓ＊Ｌ＋１とについて、ペアリング演算Πｉ＝０Ｌ＋１ｅ（ｃｉ，ｓ＊ｉ）を行い、前記署名データσの正当性を検証するペアリング演算部と
を備えることを特徴とする署名処理システム。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項５
【補正方法】変更
【補正の内容】
【請求項５】
ｔ＝０，．．．，ｄ＋１（ｄは１以上の整数）の各整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理システムにおいて、署名データσを生成する署名装置であり、
ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについて、識別情報ｔと、属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ，ｎｔは１以上の整数）とを含む属性集合Γと、
基底Ｂ＊０の基底ベクトルｂ＊０，１の係数として所定の値δが設定された鍵要素ｋ＊０と、
前記属性集合Γに含まれる各識別情報ｔについて、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，ｎｔ）の係数として属性情報ｘ→ｔに前記所定の値δを乗じたδｘｔ，ｉ（ｉ＝１，．．．，ｎｔ）が設定された鍵要素ｋ＊ｔと、
基底Ｂ＊ｄ＋１の基底ベクトルｂ＊ｄ＋１，１の係数として前記所定の値δが設定された鍵要素ｋ＊ｄ＋１，１と、
基底Ｂ＊ｄ＋１の基底ベクトルｂ＊ｄ＋１，２の係数として前記所定の値δが設定された鍵要素ｋ＊ｄ＋１，２と
を署名鍵ｓｋΓとして取得する署名鍵取得部と、
ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍと、メッセージｍとを入力する第２情報入力部と、
前記第２情報入力部が入力した変数ρ（ｉ）と、前記署名鍵取得部が取得した署名鍵ｓｋΓに含まれる属性集合Γとに基づき、ｉ＝１，．．．，Ｌの各整数ｉのうち、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）であり、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性集合Γに含まれるｘ→ｔとの内積が０となるｉと、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）であり、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性集合Γに含まれるｘ→ｔとの内積が０とならないｉとの集合Ｉを特定するとともに、特定した集合Ｉに含まれるｉについて、前記第２情報入力部が入力した行列Ｍのｉ行目の要素であるＭｉに基づき、αｉＭｉを合計した場合に所定のベクトルｈ→となる補完係数αｉを計算する補完係数計算部と、
前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊０を含む署名要素ｓ＊０を生成する署名要素０生成部と、
ｉ＝１，．．．，Ｌの各整数ｉについて、前記補完係数計算部が特定した集合Ｉに含まれる整数ｉであり、かつ、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉとし、前記集合Ｉに含まれるｉであり、かつ、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉ／（ｖ→ｉ・ｘ→ｔ）とし、前記集合Ｉに含まれない整数ｉの場合には値γｉ：＝０として、前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊ｔに前記値γｉを乗じたγｉｋ＊ｔを含む署名要素ｓ＊ｉを生成する署名要素ｉ生成部と、
前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊ｄ＋１，１と、前記メッセージｍを用いて生成される値ｍ’を前記鍵要素ｋ＊ｄ＋１，２に乗じたｍ’・ｋ＊ｄ＋１，２との和を含む署名要素ｓ＊Ｌ＋１を生成する署名要素Ｌ＋１生成部と、
前記署名要素０生成部が生成した署名要素ｓ＊０と、前記署名要素ｉ生成部が生成したｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、前記署名要素Ｌ＋１生成部が生成した署名要素ｓ＊Ｌ＋１と、前記メッセージｍと、前記変数ρ（ｉ）と、前記行列Ｍとを含む署名データσを検証装置へ送信する署名データ送信部とを備えることを特徴とする署名装置。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項６
【補正方法】変更
【補正の内容】
【請求項６】
ｔ＝０，．．．，ｄ＋１（ｄは１以上の整数）の各整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理システムにおいて、署名データσを検証する検証装置であり、
署名要素ｓ＊０と、ｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、署名要素ｓ＊Ｌ＋１と、メッセージｍと、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍとを含む署名データσを取得するデータ取得部と、
ｒ個の要素を有するベクトルｆ→とｒ個の要素を有するベクトルｈ→とを用いて生成される値ｓ０：＝ｈ→・ｆ→Ｔと、所定の値ｓＬ＋１とから計算される−ｓ０−ｓＬ＋１を、基底Ｂ０の基底ベクトルｂ０，１の係数として設定して検証要素ｃ０を生成する検証要素０生成部と、
前記ベクトルｆ→と前記データ取得部が取得した署名データσに含まれる行列Ｍとに基づき生成される列ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔ：＝Ｍ・ｆ→Ｔと、ｉ＝１，．．．，Ｌの各整数ｉについての所定の値θｉとを用いて、ｉ＝１，．．．，Ｌの各整数ｉについて、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底Ｂｔの基底ベクトルｂｔ，１の係数としてｓｉ＋θｉｖｉ，１を設定し、基底ベクトルｂｔ，ｉ’（ｉ’＝２，．．．，ｎｔ）の係数としてθｉｖｉ，ｉ’（ｉ’＝２，．．．，ｎｔ）を設定して検証要素ｃｉを生成し、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底ベクトルｂｔ，ｉ’（ｉ’＝１，．．．，ｎｔ）の係数としてｓｉｖｉ，ｉ’（ｉ’＝１，．．．，ｎｔ）を設定して検証要素ｃｉを生成する検証要素ｉ生成部と、
基底Ｂｄ＋１の基底ベクトルｂｄ＋１，１の係数として、前記所定の値ｓＬ＋１と前記メーセージｍから計算される値ｍ’と所定の値θＬ＋１とから計算されるｓＬ＋１−θＬ＋１ｍ’を設定し、基底ベクトルｂｄ＋１，２の係数として前記所定の値θＬ＋１を設定して検証要素ｃＬ＋１を生成する検証要素Ｌ＋１生成部と、
前記検証要素０生成部が生成した検証要素ｃ０と、前記検証要素ｉ生成部が生成した検証要素ｃｉと、前記検証要素Ｌ＋１生成部が生成した検証要素ｃＬ＋１と、前記署名データσに含まれる署名要素ｓ＊０，ｓ＊ｉ，ｓ＊Ｌ＋１とについて、ペアリング演算Πｉ＝０Ｌ＋１ｅ（ｃｉ，ｓ＊ｉ）を行い、前記署名データσの正当性を検証するペアリング演算部と
を備えることを特徴とする検証装置。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項７
【補正方法】変更
【補正の内容】
【請求項７】
ｄ個（ｄは１以上の整数）の鍵生成装置と、署名装置と、検証装置とを備え、ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理システムであり、
前記ｄ個の鍵生成装置の各鍵生成装置は、
ｔ＝１，．．．，ｄのうち鍵生成装置毎に予め定められた整数ｔについての属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ，ｎｔは１以上の整数）を入力する第１情報入力部と、
前記整数ｔと、ｊ＝１，２の各整数ｊについて、前記第１情報入力部が入力した属性情報ｘ→ｔと、所定の値δｊと、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，２ｎｔ）とに基づき、数１０に示すベクトルを含む鍵要素ｋ＊ｔ，ｊを生成する鍵要素生成部と、
前記鍵要素生成部が生成した鍵要素ｋ＊ｔ，ｊと、前記属性情報ｘ→ｔとを含む署名鍵ｕｓｋを前記署名装置へ送信する署名鍵送信部とを備え、
前記署名装置は、
ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍと、メッセージｍとを入力する第２情報入力部と、
前記ｄ個の鍵生成装置のうち、少なくとも１つ以上の鍵生成装置の署名鍵送信部が送信した署名鍵ｕｓｋを取得する署名鍵取得部と、
前記第２情報入力部が入力した変数ρ（ｉ）と、前記署名鍵取得部が取得した署名鍵ｕｓｋに含まれる属性情報ｘ→ｔとに基づき、ｉ＝１，．．．，Ｌの各整数ｉのうち、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）であり、かつ、その組の識別情報ｔが示すｘ→ｔを含む署名鍵ｕｓｋを前記署名鍵取得部が取得しており、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性情報ｘ→ｔとの内積が０となるｉと、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）であり、かつ、その組の識別情報ｔが示すｘ→ｔを含む署名鍵ｕｓｋを前記署名鍵取得部が取得しており、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性情報ｘ→ｔとの内積が０とならないｉとの集合Ｉを特定するとともに、特定した集合Ｉに含まれるｉについて、前記第２情報入力部が入力した行列Ｍのｉ行目の要素であるＭｉに基づき、αｉＭｉを合計した場合に所定のベクトルｈ→となる補完係数αｉを計算する補完係数計算部と、
前記署名鍵ｕｓｋに含まれる鍵要素ｋ＊ｔ，１及び鍵要素ｋ＊ｔ，２と、所定の値ξ１，Ε，μと、前記メッセージｍから計算される値ｍ’とに基づき、ｉ＝１，．．．，Ｌの各整数ｉについて、前記補完係数計算部が特定した集合Ｉに含まれる整数ｉであり、かつ、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉとし、前記集合Ｉに含まれるｉであり、かつ、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉ／（ｖｉ・ｘｔ）とし、前記集合Ｉに含まれない整数ｉの場合には値γｉ：＝０として、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝２ｎｔ＋１，２ｎｔ＋２）を用いて、数１１に示すベクトルを含む署名要素ｓ＊ｉを生成する署名要素生成部と、
前記署名要素生成部が生成したｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、前記メッセージｍと、前記変数ρ（ｉ）と、前記行列Ｍとを含む署名データσを前記検証装置へ送信する署名データ送信部と
を備え、
前記検証装置は、
前記署名データ送信部が送信した署名データσを取得するデータ取得部と、
ｒ個の要素を有するベクトルｆ→と、前記データ取得部が取得した署名データσに含まれる行列Ｍとに基づき列ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔ：＝Ｍ・ｆ→Ｔを生成するとともに、ｓ０：＝ｈ→・ｆ→Ｔとして、ｓ０＝ｈ→・（ｆ→’）Ｔであるｒ個の要素を有するベクトルｆ→’と、前記行列Ｍとに基づき列ベクトル（ｓ→’）Ｔ：＝（ｓ１’，．．．，ｓＬ’）Ｔ：＝Ｍ・（ｆ→’）Ｔを生成するベクトル生成部と、
前記ベクトル生成部が生成した列ベクトルｓ→Ｔ及び列ベクトル（ｓ→’）Ｔと、ｉ＝１，．．．，Ｌの各整数ｉについての所定の値θｉ，θｉ’，θｉ’’，σｉとに基づき、ｉ＝１，．．．，Ｌの各整数ｉについて、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底Ｂｔの基底ベクトルｂｔ，ｉ’（ｉ’＝１，．．．，２ｎｔ＋２）を用いて、数１２に示すベクトルを含む検証要素ｃｉを生成し、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底ベクトルｂｔ，ｉ（ｉ＝１，．．．，２ｎｔ＋２）を用いて、数１３に示すベクトルを含む検証要素ｃｉを生成する検証要素生成部と、
前記検証要素生成部が生成した検証要素ｃｉと、前記署名データσに含まれる署名要素ｓ＊ｉとについて、ペアリング演算Πｉ＝１Ｌｅ（ｃｉ，ｓ＊ｉ）を行い、前記署名データσの正当性を検証するペアリング演算部と
を備えることを特徴とする署名処理システム。
【数１０】
2012155088.tif 000001
【数１１】
2012155088.tif 000002
【数１２】
2012155088.tif 000003
【数１３】
2012155088.tif 000004
【手続補正５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理システムにおいて、署名鍵ｕｓｋを生成する鍵生成装置であり、
ｔ＝１，．．．，ｄのうち所定の整数ｔについて、属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ）を入力する第１情報入力部と、
前記整数ｔと、ｊ＝１，２の各整数ｊについて、前記第１情報入力部が入力した属性情報ｘ→ｔと、所定の値δｊと、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，２ｎｔ）とに基づき、数１９に示すベクトルを含む鍵要素ｋ＊ｔ，ｊを生成する鍵要素生成部と、
前記鍵要素生成部が生成した鍵要素ｋ＊ｔ，ｊと、前記属性情報ｘ→ｔとを含む署名鍵ｕｓｋを署名装置へ送信する署名鍵送信部と
を備えることを特徴とする鍵生成装置。
【数１９】
2012155088.tif 000005
【手続補正６】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１１
【補正方法】変更
【補正の内容】
【請求項１１】
ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理システムにおいて、署名データσを生成する署名装置であり、
ｔ＝１，．．．，ｄのうち少なくとも一部の整数ｔと、ｊ＝１，２の各整数ｊとについて、属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ）と、所定の値δｊと、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，２ｎｔ）とに基づき、数２０に示すベクトルを含むように生成された鍵要素ｋ＊ｔ，ｊと、前記属性情報ｘ→ｔとを含む署名鍵ｕｓｋを取得する署名鍵取得部と、
ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍと、メッセージｍとを入力する第２情報入力部と、
前記第２情報入力部が入力した変数ρ（ｉ）と、前記署名鍵取得部が取得した署名鍵ｕｓｋに含まれる属性情報ｘ→ｔとに基づき、ｉ＝１，．．．，Ｌの各整数ｉのうち、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）であり、かつ、その組の識別情報ｔが示すｘ→ｔを含む署名鍵ｕｓｋを前記署名鍵取得部が取得しており、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性情報ｘ→ｔとの内積が０となるｉと、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）であり、かつ、その組の識別情報ｔが示すｘ→ｔを含む署名鍵ｕｓｋを前記署名鍵取得部が取得しており、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性情報ｘ→ｔとの内積が０とならないが等しくないｉとの集合Ｉを特定するとともに、特定した集合Ｉに含まれるｉについて、前記第２情報入力部が入力した行列Ｍのｉ行目の要素であるＭｉに基づき、αｉＭｉを合計した場合に所定のベクトルｈ→となる補完係数αｉを計算する補完係数計算部と、
前記署名鍵ｕｓｋに含まれる鍵要素ｋ＊ｔ，１及び鍵要素ｋ＊ｔ，２と、所定の値ξ１，Ε，μと、前記メッセージｍから計算される値ｍ’とに基づき、ｉ＝１，．．．，Ｌの各整数ｉについて、前記補完係数計算部が特定した集合Ｉに含まれる整数ｉであり、かつ、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉとし、前記集合Ｉに含まれるｉであり、かつ、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉ／（ｖ→ｉ・ｘ→ｔ）とし、前記集合Ｉに含まれない整数ｉの場合には値γｉ：＝０として、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝２ｎｔ＋１，２ｎｔ＋２）を用いて、数２１に示すベクトルを含む署名要素ｓ＊ｉを生成する署名要素生成部と、
前記署名要素生成部が生成したｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、前記メッセージｍと、前記変数ρ（ｉ）と、前記行列Ｍとを含む署名データσを検証装置へ送信する署名データ送信部と
を備えることを特徴とする署名装置。
【数２０】
2012155088.tif 000006
【数２１】
2012155088.tif 000007
【手続補正７】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１２
【補正方法】変更
【補正の内容】
【請求項１２】
ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理システムにおいて、署名データσを検証する検証装置であり、
ｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、メッセージｍと、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍとを含む署名データσを取得するデータ取得部と、
ｒ個の要素を有するベクトルｆ→と、前記データ取得部が取得した署名データσに含まれる行列Ｍとに基づき列ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔ：＝Ｍ・ｆ→Ｔを生成するとともに、ｓ０：＝ｈ→・ｆ→Ｔとして、ｓ０＝ｈ→・（ｆ→’）Ｔであるｒ個の要素を有するベクトルｆ→’と、前記行列Ｍとに基づき列ベクトル（ｓ→’）Ｔ：＝（ｓ１’，．．．，ｓＬ’）Ｔ：＝Ｍ・（ｆ→’）Ｔを生成するベクトル生成部と、
前記ベクトル生成部が生成した列ベクトルｓ→Ｔ及び列ベクトル（ｓ→’）Ｔと、ｉ＝１，．．．，Ｌの各整数ｉについての所定の値θｉ，θｉ’，θｉ’’，σｉとに基づき、ｉ＝１，．．．，Ｌの各整数ｉについて、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底Ｂｔの基底ベクトルｂｔ，ｉ’（ｉ’＝１，．．．，２ｎｔ＋２）を用いて、数２２に示すベクトルを含む検証要素ｃｉを生成し、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底ベクトルｂｔ，ｉ（ｉ＝１，．．．，２ｎｔ＋２）を用いて、数２３に示すベクトルを含む検証要素ｃｉを生成する検証要素生成部と、
前記検証要素生成部が生成した検証要素ｃｉと、前記署名データσに含まれる署名要素ｓ＊ｉとについて、ペアリング演算Πｉ＝１Ｌｅ（ｃｉ，ｓ＊ｉ）を行い、前記署名データσの正当性を検証するペアリング演算部と
を備えることを特徴とする検証装置。
【数２２】
2012155088.tif 000008
【数２３】
2012155088.tif 000009
【手続補正８】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１３
【補正方法】変更
【補正の内容】
【請求項１３】
ｔ＝０，．．．，ｄ＋１（ｄは１以上の整数）の各整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理方法であり、
鍵生成装置が、ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについて、識別情報ｔと、属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ，ｎｔは１以上の整数）とを含む属性集合Γを入力する第１情報入力工程と、
前記鍵生成装置が、基底Ｂ＊０の基底ベクトルｂ＊０，１の係数として所定の値δを設定した鍵要素ｋ＊０を生成する鍵要素０生成工程と、
前記鍵生成装置が、前記第１情報入力工程で入力された属性集合Γに含まれる各識別情報ｔについて、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，ｎｔ）の係数として属性情報ｘ→ｔに前記所定の値δを乗じたδｘｔ，ｉ（ｉ＝１，．．．，ｎｔ）を設定した鍵要素ｋ＊ｔを生成する鍵要素ｔ生成工程と、
前記鍵生成装置が、基底Ｂ＊ｄ＋１の基底ベクトルｂ＊ｄ＋１，１の係数として前記所定の値δを設定した鍵要素ｋ＊ｄ＋１，１と、基底Ｂ＊ｄ＋１の基底ベクトルｂ＊ｄ＋１，２の係数として前記所定の値δを設定した鍵要素ｋ＊ｄ＋１，２とを生成する鍵要素ｄ＋１生成工程と、
前記鍵生成装置が、前記鍵要素０生成工程で生成された鍵要素ｋ＊０と、前記鍵要素ｔ生成工程で生成された前記属性集合Γに含まれる各識別情報ｔについての鍵要素ｋ＊ｔと、前記鍵要素ｄ＋１生成工程で生成された鍵要素ｋ＊ｄ＋１，１及び鍵要素ｋ＊ｄ＋１，２と、前記属性集合Γとを含む署名鍵ｓｋΓを署名装置へ送信する署名鍵送信工程と、
前記署名装置が、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍと、メッセージｍとを入力する第２情報入力工程と、
前記署名装置が、前記署名鍵送信工程で送信された署名鍵ｓｋΓを取得する署名鍵取得工程と、
前記署名装置が、前記第２情報入力工程で入力された変数ρ（ｉ）と、前記署名鍵取得工程で取得された署名鍵ｓｋΓに含まれる属性集合Γとに基づき、ｉ＝１，．．．，Ｌの各整数ｉのうち、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）であり、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性集合Γに含まれるｘ→ｔとの内積が０となるｉと、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）であり、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性集合Γに含まれるｘ→ｔとの内積が０とならないｉとの集合Ｉを特定するとともに、特定された集合Ｉに含まれるｉについて、前記第２情報入力工程で入力された行列Ｍのｉ行目の要素であるＭｉに基づき、αｉＭｉを合計した場合に所定のベクトルｈ→となる補完係数αｉを計算する補完係数計算工程と、
前記署名装置が、前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊０を含む署名要素ｓ＊０を生成する署名要素０生成工程と、
前記署名装置が、ｉ＝１，．．．，Ｌの各整数ｉについて、前記補完係数計算工程で特定された集合Ｉに含まれる整数ｉであり、かつ、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉとし、前記集合Ｉに含まれるｉであり、かつ、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉ／（ｖ→ｉ・ｘ→ｔ）とし、前記集合Ｉに含まれない整数ｉの場合には値γｉ：＝０として、前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊ｔに前記値γｉを乗じたγｉｋ＊ｔを含む署名要素ｓ＊ｉを生成する署名要素ｉ生成工程と、
前記署名装置が、前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊ｄ＋１，１と、前記メッセージｍを用いて生成される値ｍ’を前記鍵要素ｋ＊ｄ＋１，２に乗じたｍ’・ｋ＊ｄ＋１，２との和を含む署名要素ｓ＊Ｌ＋１を生成する署名要素Ｌ＋１生成工程と、
前記署名装置が、前記署名要素０生成工程で生成された署名要素ｓ＊０と、前記署名要素ｉ生成工程で生成されたｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、前記署名要素Ｌ＋１生成工程で生成された署名要素ｓ＊Ｌ＋１と、前記メッセージｍと、前記変数ρ（ｉ）と、前記行列Ｍとを含む署名データσを検証装置へ送信する署名データ送信工程と、
前記検証装置が、前記署名データ送信工程で送信された署名データσを取得するデータ
取得工程と、
前記検証装置が、ｒ個の要素を有するベクトルｆ→と前記ベクトルｈ→とを用いて生成される値ｓ０：＝ｈ→・ｆ→Ｔと、所定の値ｓＬ＋１とから計算される−ｓ０−ｓＬ＋１を、基底Ｂ０の基底ベクトルｂ０，１の係数として設定して検証要素ｃ０を生成する検証要素０生成工程と、
前記検証装置が、前記ベクトルｆ→と前記データ取得工程で取得された署名データσに含まれる行列Ｍとに基づき生成される列ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔ：＝Ｍ・ｆ→Ｔと、ｉ＝１，．．．，Ｌの各整数ｉについての所定の値θｉとを用いて、ｉ＝１，．．．，Ｌの各整数ｉについて、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底Ｂｔの基底ベクトルｂｔ，１の係数としてｓｉ＋θｉｖｉ，１を設定し、基底ベクトルｂｔ，ｉ’（ｉ’＝２，．．．，ｎｔ）の係数としてθｉｖｉ，ｉ’（ｉ’＝２，．．．，ｎｔ）を設定して検証要素ｃｉを生成し、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底ベクトルｂｔ，ｉ’（ｉ’＝１，．．．，ｎｔ）の係数としてｓｉｖｉ，ｉ’（ｉ’＝１，．．．，ｎｔ）を設定して検証要素ｃｉを生成する検証要素ｉ生成工程と、
前記検証装置が、基底Ｂｄ＋１の基底ベクトルｂｄ＋１，１の係数として、前記所定の値ｓＬ＋１と前記値ｍ’と所定の値θＬ＋１とから計算されるｓＬ＋１−θＬ＋１ｍ’を設定し、基底ベクトルｂｄ＋１，２の係数として前記所定の値θＬ＋１を設定して検証要素ｃＬ＋１を生成する検証要素Ｌ＋１生成工程と、
前記検証装置が、前記検証要素０生成工程で生成された検証要素ｃ０と、前記検証要素ｉ生成工程で生成された検証要素ｃｉと、前記検証要素Ｌ＋１生成工程で生成された検証要素ｃＬ＋１と、前記署名データσに含まれる署名要素ｓ＊０，ｓ＊ｉ，ｓ＊Ｌ＋１とについて、ペアリング演算Πｉ＝０Ｌ＋１ｅ（ｃｉ，ｓ＊ｉ）を行い、前記署名データσの正当性を検証するペアリング演算工程と
を備えることを特徴とする署名処理方法。
【手続補正９】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１４
【補正方法】変更
【補正の内容】
【請求項１４】
鍵生成装置で動作される鍵生成プログラムと署名装置で動作させる署名プログラムと検証装置で動作させる検証プログラムとを備え、ｔ＝０，．．．，ｄ＋１（ｄは１以上の整数）の各整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理プログラムであり、
前記鍵生成プログラムは、
ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについて、識別情報ｔと、属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ，ｎｔは１以上の整数）とを含む属性集合Γを入力する第１情報入力処理と、
基底Ｂ＊０の基底ベクトルｂ＊０，１の係数として所定の値δを設定した鍵要素ｋ＊０を生成する鍵要素０生成処理と、
前記第１情報入力処理で入力された属性集合Γに含まれる各識別情報ｔについて、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，ｎｔ）の係数として属性情報ｘ→ｔに前記所定の値δを乗じたδｘｔ，ｉ（ｉ＝１，．．．，ｎｔ）を設定した鍵要素ｋ＊ｔを生成する鍵要素ｔ生成処理と、
基底Ｂ＊ｄ＋１の基底ベクトルｂ＊ｄ＋１，１の係数として前記所定の値δを設定した鍵要素ｋ＊ｄ＋１，１と、基底Ｂ＊ｄ＋１の基底ベクトルｂ＊ｄ＋１，２の係数として前記所定の値δを設定した鍵要素ｋ＊ｄ＋１，２とを生成する鍵要素ｄ＋１生成処理と、
前記鍵要素０生成処理で生成された鍵要素ｋ＊０と、前記鍵要素ｔ生成処理で生成された前記属性集合Γに含まれる各識別情報ｔについての鍵要素ｋ＊ｔと、前記鍵要素ｄ＋１生成処理で生成された鍵要素ｋ＊ｄ＋１，１及び鍵要素ｋ＊ｄ＋１，２と、前記属性集合Γとを含む署名鍵ｓｋΓを前記署名装置へ送信する署名鍵送信処理と
をコンピュータに実行させ、
前記署名プログラムは、
ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，
ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍと、メッセージｍとを入力する第２情報入力処理と、
前記署名鍵送信処理で送信された署名鍵ｓｋΓを取得する署名鍵取得処理と、
前記第２情報入力処理で入力された変数ρ（ｉ）と、前記署名鍵取得処理で取得された署名鍵ｓｋΓに含まれる属性集合Γとに基づき、ｉ＝１，．．．，Ｌの各整数ｉのうち、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）であり、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性集合Γに含まれるｘ→ｔとの内積が０となるｉと、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）であり、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性集合Γに含まれるｘ→ｔとの内積が０とならないｉとの集合Ｉを特定するとともに、特定された集合Ｉに含まれるｉについて、前記第２情報入力処理で入力された行列Ｍのｉ行目の要素であるＭｉに基づき、αｉＭｉを合計した場合に所定のベクトルｈ→となる補完係数αｉを計算する補完係数計算処理と、
前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊０を含む署名要素ｓ＊０を生成する署名要素０生成処理と、
ｉ＝１，．．．，Ｌの各整数ｉについて、前記補完係数計算処理で特定された集合Ｉに含まれる整数ｉであり、かつ、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉとし、前記集合Ｉに含まれるｉであり、かつ、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉ／（ｖ→ｉ・ｘ→ｔ）とし、前記集合Ｉに含まれない整数ｉの場合には値γｉ：＝０として、前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊ｔに前記値γｉを乗じたγｉｋ＊ｔを含む署名要素ｓ＊ｉを生成する署名要素ｉ生成処理と、
前記署名鍵ｓｋΓに含まれる鍵要素ｋ＊ｄ＋１，１と、前記メッセージｍを用いて生成される値ｍ’を前記鍵要素ｋ＊ｄ＋１，２に乗じたｍ’・ｋ＊ｄ＋１，２との和を含む署名要素ｓ＊Ｌ＋１を生成する署名要素Ｌ＋１生成処理と、
前記署名要素０生成処理で生成された署名要素ｓ＊０と、前記署名要素ｉ生成処理で生成されたｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、前記署名要素Ｌ＋１生成処理で生成された署名要素ｓ＊Ｌ＋１と、前記メッセージｍと、前記変数ρ（ｉ）と、前記行列Ｍとを含む署名データσを前記検証装置へ送信する署名データ送信処理と
をコンピュータに実行させ、
前記検証プログラムは、
前記署名データ送信処理で送信された署名データσを取得するデータ取得処理と、
ｒ個の要素を有するベクトルｆ→と前記ベクトルｈ→とを用いて生成される値ｓ０：＝ｈ→・ｆ→Ｔと、所定の値ｓＬ＋１とから計算される−ｓ０−ｓＬ＋１を、基底Ｂ０の基底ベクトルｂ０，１の係数として設定して検証要素ｃ０を生成する検証要素０生成処理と、
前記ベクトルｆ→と前記データ取得処理で取得された署名データσに含まれる行列Ｍとに基づき生成される列ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔ：＝Ｍ・ｆ→Ｔと、ｉ＝１，．．．，Ｌの各整数ｉについての所定の値θｉとを用いて、ｉ＝１，．．．，Ｌの各整数ｉについて、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底Ｂｔの基底ベクトルｂｔ，１の係数としてｓｉ＋θｉｖｉ，１を設定し、基底ベクトルｂｔ，ｉ’（ｉ’＝２，．．．，ｎｔ）の係数としてθｉｖｉ，ｉ’（ｉ’＝２，．．．，ｎｔ）を設定して検証要素ｃｉを生成し、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底ベクトルｂｔ，ｉ’（ｉ’＝１，．．．，ｎｔ）の係数としてｓｉｖｉ，ｉ’（ｉ’＝１，．．．，ｎｔ）を設定して検証要素ｃｉを生成する検証要素ｉ生成処理と、
基底Ｂｄ＋１の基底ベクトルｂｄ＋１，１の係数として、前記所定の値ｓＬ＋１と前記値ｍ’と所定の値θＬ＋１とから計算されるｓＬ＋１−θＬ＋１ｍ’を設定し、基底ベクトルｂｄ＋１，２の係数として前記所定の値θＬ＋１を設定して検証要素ｃＬ＋１を生成する検証要素Ｌ＋１生成処理と、
前記検証要素０生成処理で生成された検証要素ｃ０と、前記検証要素ｉ生成処理で生成された検証要素ｃｉと、前記検証要素Ｌ＋１生成処理で生成された検証要素ｃＬ＋１と、前記署名データσに含まれる署名要素ｓ＊０，ｓ＊ｉ，ｓ＊Ｌ＋１とについて、ペアリング演算Πｉ＝０Ｌ＋１ｅ（ｃｉ，ｓ＊ｉ）を行い、前記署名データσの正当性を検証するペアリング演算処理と
をコンピュータに実行させることを特徴とする署名処理プログラム。
【手続補正１０】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１５
【補正方法】変更
【補正の内容】
【請求項１５】
ｔ＝１，．．．，ｄ（ｄは１以上の整数）の少なくとも１つ以上の整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理方法であり、
ｄ個の鍵生成装置の少なくとも１個以上の鍵生成装置が、ｔ＝１，．．．，ｄのうち鍵生成装置毎に予め定められた整数ｔについての属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ）を入力する第１情報入力工程と、
前記少なくとも１個以上の鍵生成装置が、前記整数ｔと、ｊ＝１，２の各整数ｊについて、前記第１情報入力工程で入力された属性情報ｘ→ｔと、所定の値δｊと、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，２ｎｔ）とに基づき、数２４に示すベクトルを含む鍵要素ｋ＊ｔ，ｊを生成する鍵要素生成工程と、
前記少なくとも１個以上の鍵生成装置が、前記鍵要素生成工程で生成された鍵要素ｋ＊ｔ，ｊと、前記属性情報ｘ→ｔとを含む署名鍵ｕｓｋを署名装置へ送信する署名鍵送信工程と、
前記署名装置が、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍと、メッセージｍとを入力する第２情報入力工程と、
前記署名装置が、前記ｄ個の鍵生成装置のうち、少なくとも１つ以上の鍵生成装置の署名鍵送信工程で送信された署名鍵ｕｓｋを取得する署名鍵取得工程と、
前記署名装置が、前記第２情報入力工程で入力された変数ρ（ｉ）と、前記署名鍵取得工程で取得された署名鍵ｕｓｋに含まれる属性情報ｘ→ｔとに基づき、ｉ＝１，．．．，Ｌの各整数ｉのうち、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）であり、かつ、その組の識別情報ｔが示すｘ→ｔを含む署名鍵ｕｓｋを前記署名鍵取得工程で取得しており、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性情報ｘ→ｔとの内積が０となるｉと、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）であり、かつ、その組の識別情報ｔが示すｘ→ｔを含む署名鍵ｕｓｋを前記署名鍵取得工程で取得しており、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性情報ｘ→ｔとの内積が０とならないｉとの集合Ｉを特定するとともに、特定された集合Ｉに含まれるｉについて、前記第２情報入力工程で入力された行列Ｍのｉ行目の要素であるＭｉに基づき、αｉＭｉを合計した場合に所定のベクトルｈ→となる補完係数αｉを計算する補完係数計算工程と、
前記署名装置が、前記署名鍵ｕｓｋに含まれる鍵要素ｋ＊ｔ，１及び鍵要素ｋ＊ｔ，２と、所定の値ξ１，Ε，μと、前記メッセージｍから計算される値ｍ’とに基づき、ｉ＝１，．．．，Ｌの各整数ｉについて、前記補完係数計算工程で特定された集合Ｉに含まれる整数ｉであり、かつ、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉとし、前記集合Ｉに含まれるｉであり、かつ、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉ／（ｖ→ｉ・ｘ→ｔ）とし、前記集合Ｉに含まれない整数ｉの場合には値γｉ：＝０として、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝２ｎｔ＋１，２ｎｔ＋２）を用いて、数２５に示すベクトルを含む署名要素ｓ＊ｉを生成する署名要素生成工程と、
前記署名装置が、前記署名要素生成工程で生成されたｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、前記メッセージｍと、前記変数ρ（ｉ）と、前記行列Ｍとを含む署名データσを検証装置へ送信する署名データ送信工程と、
前記検証装置が、前記署名データ送信工程で送信された署名データσを取得するデータ取得工程と、
前記検証装置が、ｒ個の要素を有するベクトルｆ→と、前記データ取得工程で取得された署名データσに含まれる行列Ｍとに基づき列ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔ：＝Ｍ・ｆ→Ｔを生成するとともに、ｓ０：＝ｈ→・ｆ→Ｔとして、ｓ０＝ｈ→・（ｆ→’）Ｔであるｒ個の要素を有するベクトルｆ→’と、前記行列Ｍとに基づき列ベクトル（ｓ→’）Ｔ：＝（ｓ１’，．．．，ｓＬ’）Ｔ：＝Ｍ・（ｆ→’）Ｔを生成するベクトル生成工程と、
前記検証装置が、前記ベクトル生成工程で生成された列ベクトルｓ→Ｔ及び列ベクトル（ｓ→’）Ｔと、ｉ＝１，．．．，Ｌの各整数ｉについての所定の値θｉ，θｉ’，θｉ’’，σｉとに基づき、ｉ＝１，．．．，Ｌの各整数ｉについて、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底Ｂｔの基底ベクトルｂｔ，ｉ’（ｉ’＝１，．．．，２ｎｔ＋２）を用いて、数２６に示すベクトルを含む検証要素ｃｉを生成し、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底ベクトルｂｔ，１から基底ベクトルｂｔ，ｉ（ｉ’＝１，．．．，２ｎｔ＋２）を用いて、数２７に示すベクトルを含む検証要素ｃｉを生成する検証要素生成工程と、
前記検証装置が、前記検証要素生成工程で生成された検証要素ｃｉと、前記署名データσに含まれる署名要素ｓ＊ｉとについて、ペアリング演算Πｉ＝１Ｌｅ（ｃｉ，ｓ＊ｉ）を行い、前記署名データσの正当性を検証するペアリング演算工程と
を備えることを特徴とする署名処理方法。
【数２４】
2012155088.tif 000010
【数２５】
2012155088.tif 000011
【数２６】
2012155088.tif 000012
【数２７】
2012155088.tif 000013
【手続補正１１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１６
【補正方法】変更
【補正の内容】
【請求項１６】
ｄ個（ｄは１以上の整数）の鍵生成装置で動作させる鍵生成プログラムと、署名装置で動作させる署名プログラムと、検証装置で動作させる検証プログラムとを備え、ｔ＝１，．．．，ｄの少なくとも１つ以上の整数ｔについての基底Ｂｔと基底Ｂ＊ｔとを用いて署名処理を実行する署名処理プログラムであり、
前記鍵生成プログラムは、
ｔ＝１，．．．，ｄのうち鍵生成装置毎に予め定められた整数ｔについての属性情報ｘ→ｔ：＝（ｘｔ，ｉ）（ｉ＝１，．．．，ｎｔ）を入力する第１情報入力処理と、
前記整数ｔと、ｊ＝１，２の各整数ｊについて、前記第１情報入力処理で入力された属性情報ｘ→ｔと、所定の値δｊと、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝１，．．．，２ｎｔ）とに基づき、数２８に示すベクトルを含む鍵要素ｋ＊ｔ，ｊを生成する鍵要素生成処理と、
前記鍵要素生成処理で生成された鍵要素ｋ＊ｔ，ｊと、前記属性情報ｘ→ｔとを含む署名鍵ｕｓｋを前記署名装置へ送信する署名鍵送信処理と
をコンピュータに実行させ、
前記署名プログラムは、
ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについての変数ρ（ｉ）であって、識別情報ｔ（ｔ＝１，．．．，ｄのいずれかの整数）と、属性情報ｖ→ｉ：＝（ｖｉ，ｉ’）（ｉ’＝１，．．．，ｎｔ）との肯定形の組（ｔ，ｖ→ｉ）又は否定形の組¬（ｔ，ｖ→ｉ）のいずれかである変数ρ（ｉ）と、Ｌ行ｒ列（ｒは１以上の整数）の所定の行列Ｍと、メッセージｍとを入力する第２情報入力処理と、
前記ｄ個の鍵生成装置のうち、少なくとも１つ以上の鍵生成装置の署名鍵送信処理で送信された署名鍵ｕｓｋを取得する署名鍵取得処理と、
前記第２情報入力処理で入力された変数ρ（ｉ）と、前記署名鍵取得処理で取得された署名鍵ｕｓｋに含まれる属性情報ｘ→ｔとに基づき、ｉ＝１，．．．，Ｌの各整数ｉのうち、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）であり、かつ、その組の識別情報ｔが示すｘ→ｔを含む署名鍵ｕｓｋを前記署名鍵取得処理で取得しており、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性情報ｘ→ｔとの内積が０となるｉと、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）であり、かつ、その組の識別情報ｔが示すｘ→ｔを含む署名鍵ｕｓｋを前記署名鍵取得処理で取得しており、かつ、その組のｖ→ｉと、その組の識別情報ｔが示す属性情報ｘ→ｔとの内積が０とならないｉとの集合Ｉを特定するとともに、特定された集合Ｉに含まれるｉについて、前記第２情報入力処理で入力された行列Ｍのｉ行目の要素であるＭｉに基づき、αｉＭｉを合計した場合に所定のベクトルｈ→となる補完係数αｉを計算する補完係数計算処理と、
前記署名鍵ｕｓｋに含まれる鍵要素ｋ＊ｔ，１及び鍵要素ｋ＊ｔ，２と、所定の値ξ１，Ε，μと、前記メッセージｍから計算される値ｍ’とに基づき、ｉ＝１，．．．，Ｌの各整数ｉについて、前記補完係数計算処理で特定された集合Ｉに含まれる整数ｉであり、かつ、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉとし、前記集合Ｉに含まれるｉであり、かつ、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には値γｉ：＝αｉ／（ｖ→ｉ・ｘ→ｔ）とし、前記集合Ｉに含まれない整数ｉの場合には値γｉ：＝０として、基底Ｂ＊ｔの基底ベクトルｂ＊ｔ，ｉ（ｉ＝２ｎｔ＋１，２ｎｔ＋２）を用いて、数２９に示すベクトルを含む署名要素ｓ＊ｉを生成する署名要素生成処理と、
前記署名要素生成処理で生成されたｉ＝１，．．．，Ｌの各整数ｉについての署名要素ｓ＊ｉと、前記メッセージｍと、前記変数ρ（ｉ）と、前記行列Ｍとを含む署名データσを前記検証装置へ送信する署名データ送信処理と
をコンピュータに実行させ、
前記検証プログラムは、
前記署名データ送信処理で送信された署名データσを取得するデータ取得処理と、
ｒ個の要素を有するベクトルｆ→と、前記データ取得処理で取得された署名データσに含まれる行列Ｍとに基づき列ベクトルｓ→Ｔ：＝（ｓ１，．．．，ｓＬ）Ｔ：＝Ｍ・ｆ→Ｔを生成するとともに、ｓ０：＝ｈ→・ｆ→Ｔとして、ｓ０＝ｈ→・（ｆ→’）Ｔであるｒ個の要素を有するベクトルｆ→’と、前記行列Ｍとに基づき列ベクトル（ｓ→’）Ｔ：＝（ｓ１’，．．．，ｓＬ’）Ｔ：＝Ｍ・（ｆ→’）Ｔを生成するベクトル生成処理と、
前記ベクトル生成処理で生成された列ベクトルｓ→Ｔ及び列ベクトル（ｓ→’）Ｔと、ｉ＝１，．．．，Ｌの各整数ｉについての所定の値θｉ，θｉ’，θｉ’’，σｉとに基づき、ｉ＝１，．．．，Ｌの各整数ｉについて、変数ρ（ｉ）が肯定形の組（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底Ｂｔの基底ベクトルｂｔ，ｉ’（ｉ’＝１，．．．，２ｎｔ＋２）を用いて、数３０に示すベクトルを含む検証要素ｃｉを生成し、変数ρ（ｉ）が否定形の組¬（ｔ，ｖ→ｉ）である場合には、その組の識別情報ｔが示す基底ベクトルｂｔ，ｉ（ｉ＝１，．．．，２ｎｔ＋２）を用いて、数３１に示すベクトルを含む検証要素ｃｉを生成する検証要素生成処理と、
前記検証要素生成処理で生成された検証要素ｃｉと、前記署名データσに含まれる署名要素ｓ＊ｉとについて、ペアリング演算Πｉ＝１Ｌｅ（ｃｉ，ｓ＊ｉ）を行い、前記署名データσの正当性を検証するペアリング演算処理と
をコンピュータに実行させることを特徴とする署名処理プログラム。
【数２８】
2012155088.tif 000014
【数２９】
2012155088.tif 000015
【数３０】
2012155088.tif 000016
【数３１】
2012155088.tif 000017