"鍵生成装置と署名装置と検証装置とを備え、t=0,...,d1dは1以上の整数の各整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムであり、前記鍵生成装置は、t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数とを含む属性集合Γを入力する第1情報入力部と、基底B0の基底ベクトルb0,1の係数として所定の値δを設定した鍵要素k0を生成する鍵要素0生成部と、前記第1情報入力部が入力した属性集合Γに含まれる各識別情報tについて、基底Btの基底ベクトルbt,ii=1,...,ntの係数として属性情報x→tに前記所定の値δを乗じたδxt,ii=1,...,ntを設定した鍵要素ktを生成する鍵要素t生成部と、基底Bd1の基底ベクトルbd1,1の係数として前記所定の値δを設定した鍵要素kd1,1と、基底Bd1の基底ベクトルbd1,2の係数として前記所定の値δを設定した鍵要素kd1,2とを生成する鍵要素d1生成部と、前記鍵要素0生成部が生成した鍵要素k0と、前記鍵要素t生成部が生成した前記属性集合Γに含まれる各識別情報tについての鍵要素ktと、前記鍵要素d1生成部が生成した鍵要素kd1,1及び鍵要素kd1,2と、前記属性集合Γとを含む署名鍵skΓを前記署名装置へ送信する署名鍵送信部とを備え、前記署名装置は、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報v→i:=vi,i’i’=1,...,ntとの肯定形の組t,v→i又は否定形の組¬t,v→iのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mと、メッセージmとを入力する第2情報入力部と、前記署名鍵送信部が送信した署名鍵skΓを取得する署名鍵取得部と、前記第2情報入力部が入力した変数ρiと、前記署名鍵取得部が取得した署名鍵skΓに含まれる属性集合Γとに基づき、i=1,...,Lの各整数iのうち、変数ρiが肯定形の組t,v→iであり、かつ、その組のv→iと、その組の識別情報tが示す属性集合Γに含まれるx→tとの内積が0となるiと、変数ρiが否定形の組¬t,v→iであり、かつ、その組のv→iと、その組の識別情報tが示す属性集合Γに含まれるx→tとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記第2情報入力部が入力した行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算部と、前記署名鍵skΓに含まれる鍵要素k0を含む署名要素s0を生成する署名要素0生成部と、i=1,...,Lの各整数iについて、前記補完係数計算部が特定した集合Iに含まれる整数iであり、かつ、変数ρiが肯定形の組t,v→iである場合には値γi:=αiとし、前記集合Iに含まれるiであり、かつ、変数ρiが否定形の組¬t,v→iである場合には値γi:=αi/v→ix→tとし、前記集合Iに含まれない整数iの場合には値γi:=0として、前記署名鍵skΓに含まれる鍵要素ktに前記値γiを乗じたγiktを含む署名要素siを生成する署名要素i生成部と、前記署名鍵skΓに含まれる鍵要素kd1,1と、前記メッセージmを用いて生成される値m’を前記鍵要素kd1,2に乗じたm’kd1,2との和を含む署名要素sL1を生成する署名要素L1生成部と、前記署名要素0生成部が生成した署名要素s0と、前記署名要素i生成部が生成したi=1,...,Lの各整数iについての署名要素siと、前記署名要素L1生成部が生成した署名要素sL1と、前記メッセージmと、前記変数ρiと、前記行列Mとを含む署名データσを前記検証装置へ送信する署名データ送信部とを備え、前記検証装置は、前記署名データ送信部が送信した署名データσを取得するデータ取得部と、r個の要素を有するベクトルf→と前記ベクトルh→と用いて生成される値s0:=h→f→Tと、所定の値sL1とから計算される-s0-sL1を、基底B0の基底ベクトルb0,1の係数として設定して検証要素c0を生成する検証要素0生成部と、前記ベクトルf→と前記データ取得部が取得した署名データσに含まれる行列Mとに基づき生成される列ベクトルs→T:=s1,...,sLT:=Mf→Tと、i=1,...,Lの各整数iについての所定の値θiとを用いて、i=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,1の係数としてsiθivi,1を設定し、基底ベクトルbt,i’i’=2,...,ntの係数としてθivi,i’i’=2,...,ntを設定して検証要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,i’i’=1,...,ntの係数としてsivi,i’i’=1,...,ntを設定して検証要素ciを生成する検証要素i生成部と、基底Bd1の基底ベクトルbd1,1の係数として、前記所定の値sL1と前記値m’と所定の値θL1とから計算されるsL1-θL1m’を設定し、基底ベクトルbd1,2の係数として前記所定の値θL1を設定して検証要素cL1を生成する検証要素L1生成部と、前記検証要素0生成部が生成した検証要素c0と、前記検証要素i生成部が生成した検証要素ciと、前記検証要素L1生成部が生成した検証要素cL1と、前記署名データσに含まれる署名要素s0,si,sL1とについて、ペアリング演算Πi=0L1eci,siを行い、前記署名データσの正当性を検証するペアリング演算部とを備えることを特徴とする署名処理システム。前記署名処理システムは、少なくとも基底ベクトルbt,ii=1,...,1u0,...,1u0w0,...,1u0w0z0を有する基底B0と、少なくとも基底ベクトルbt,ii=1,...,nt,...,ntut,...,ntutwt,...,ntutwtztut,wt,ztは1以上の整数を有する基底Btt=1,...,dと、少なくとも基底ベクトルbt,ii=1,2,...,2ud1,...,2ud1wd1,...,2ud1wd1zd1を有する基底Bd1と、少なくとも基底ベクトルbt,ii=1,...,1u0,...,1u0w0,...,1u0w0z0を有する基底B0と、少なくとも基底ベクトルbt,ii=1,...,nt,...,ntut,...,ntutwt,...,ntutwtztut,wt,ztは1以上の整数を有する基底Btt=1,...,dと、少なくとも基底ベクトルbt,ii=1,2,...,2ud1,...,2ud1wd1,...,2ud1wd1zd1を有する基底Bd1とを用いて署名処理を実行し、前記鍵生成装置では、前記鍵要素0生成部は、乱数δと乱数φ0,ii=1,...,w0とに基づき、数1に示す鍵要素k0を生成し、前記鍵要素t生成部は、前記乱数δと乱数φt,ii=1,...,wtとに基づき、前記属性集合Γに含まれる各識別情報tについて、数2に示す鍵要素ktを生成し、前記鍵要素d1生成部は、前記乱数δと乱数φd1,1,ii=1,...,wd1と乱数φd1,2,ii=1,...,wd1とに基づき、数3に示す鍵要素kd1,1と鍵要素kd1,2とを生成し、前記署名装置では、前記署名要素0生成部は、乱数ξに基づき、数4に示す署名要素s0を生成し、前記署名要素i生成部は、i=1,...,Lの各整数iについて、前記乱数ξに基づき、数5に示す署名要素siを生成し、前記署名要素L1生成部は、前記乱数ξと前記値m’とに基づき、数6に示す署名要素sL1を生成し、前記検証装置では、前記検証要素0生成部は、前記値s0と乱数sL1と乱数η0,ii=1,...,z0とに基づき、数7に示す検証要素c0を生成し、前記検証要素i生成部は、前記列ベクトルs→Tと乱数θiと乱数ηi,i’i=1,...,L;i’=1,...,ztとに基づき、i=1,...,Lの各整数iについて、数8に示す検証要素ciを生成し、前記検証要素L1生成部は、前記乱数sL1と乱数θL1と乱数ηL1,i’i’=1,...,zd1と前記値m’とに基づき、数9に示す検証要素cL1を生成することを特徴とする請求項1に記載の署名処理システム。前記署名装置では、前記署名要素L1生成部は、前記メッセージmと、前記行列Mと、i=1,...,Lの各整数iについての前記変数ρiとを入力としたハッシュ値を前記値m’として用いて、署名要素sL1を生成し、前記検証装置では、前記検証要素L1生成部は、前記ハッシュ値を前記値m’として用いて、検証要素cL1を生成することを特徴とする請求項1又は2に記載の署名処理システム。t=0,...,d1dは1以上の整数の各整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムにおいて、署名鍵skΓを生成する鍵生成装置であり、t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数とを含む属性集合Γを入力する第1情報入力部と、基底B0の基底ベクトルb0,1の係数として所定の値δを設定した鍵要素k0を生成する鍵要素0生成部と、前記第1情報入力部が入力した属性集合Γに含まれる各識別情報tについて、基底Btの基底ベクトルbt,ii=1,...,ntの係数として属性情報x→tに前記所定の値δを乗じたδxt,ii=1,...,ntを設定した鍵要素ktを生成する鍵要素t生成部と、基底Bd1の基底ベクトルbd1,1の係数として前記所定の値δを設定した鍵要素kd1,1と、基底Bd1の基底ベクトルbd1,2の係数として前記所定の値δを設定した鍵要素kd1,2とを生成する鍵要素d1生成部と、前記鍵要素0生成部が生成した鍵要素k0と、前記鍵要素t生成部が生成した前記属性集合Γに含まれる各識別情報tについての鍵要素ktと、前記鍵要素d1生成部が生成した鍵要素kd1,1及び鍵要素kd1,2と、前記属性集合Γとを含む署名鍵skΓを署名装置へ送信する署名鍵送信部とを備えることを特徴とする鍵生成装置。t=0,...,d1dは1以上の整数の各整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムにおいて、署名データσを生成する署名装置であり、t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数とを含む属性集合Γと、基底B0の基底ベクトルb0,1の係数として所定の値δが設定された鍵要素k0と、前記第1情報入力部が入力した属性集合Γに含まれる各識別情報tについて、基底Btの基底ベクトルbt,ii=1,...,ntの係数として属性情報x→tに前記所定の値δを乗じたδxt,ii=1,...,ntが設定された鍵要素ktと、基底Bd1の基底ベクトルbd1,1の係数として前記所定の値δが設定された鍵要素kd1,1と、基底Bd1の基底ベクトルbd1,2の係数として前記所定の値δが設定された鍵要素kd1,2とを署名鍵skΓとして取得する署名鍵取得部と、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報v→i:=vi,i’i’=1,...,ntとの肯定形の組t,v→i又は否定形の組¬t,v→iのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mと、メッセージmとを入力する第2情報入力部と、前記第2情報入力部が入力した変数ρiと、前記署名鍵取得部が取得した署名鍵skΓに含まれる属性集合Γとに基づき、i=1,...,Lの各整数iのうち、変数ρiが肯定形の組t,v→iであり、かつ、その組のv→iと、その組の識別情報tが示す属性集合Γに含まれるx→tとの内積が0となるiと、変数ρiが否定形の組¬t,v→iであり、かつ、その組のv→iと、その組の識別情報tが示す属性集合Γに含まれるx→tとがの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記第2情報入力部が入力した行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算部と、前記署名鍵skΓに含まれる鍵要素k0を含む署名要素s0を生成する署名要素0生成部と、i=1,...,Lの各整数iについて、前記補完係数計算部が特定した集合Iに含まれる整数iであり、かつ、変数ρiが肯定形の組t,v→iである場合には値γi:=αiとし、前記集合Iに含まれるiであり、かつ、変数ρiが否定形の組¬t,v→iである場合には値γi:=αi/v→ix→tとし、前記集合Iに含まれない整数iの場合には値γi:=0として、前記署名鍵skΓに含まれる鍵要素ktに前記値γiを乗じたγiktを含む署名要素siを生成する署名要素i生成部と、前記署名鍵skΓに含まれる鍵要素kd1,1と、前記メッセージmを用いて生成される値m’を前記鍵要素kd1,2に乗じたm’kd1,2との和を含む署名要素sL1を生成する署名要素L1生成部と、前記署名要素0生成部が生成した署名要素s0と、前記署名要素i生成部が生成したi=1,...,Lの各整数iについての署名要素siと、前記署名要素L1生成部が生成した署名要素sL1と、前記メッセージmと、前記変数ρiと、前記行列Mとを含む署名データσを検証装置へ送信する署名データ送信部とを備えることを特徴とする署名装置。t=0,...,d1dは1以上の整数の各整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムにおいて、署名データσを検証する検証装置であり、署名要素s0と、i=1,...,Lの各整数iについての署名要素siと、署名要素sL1と、メッセージmと、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報v→i:=vi,i’i’=1,...,ntとの肯定形の組t,v→i又は否定形の組¬t,v→iのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mとを含む署名データσを取得するデータ取得部と、r個の要素を有するベクトルf→とr個の要素を有するベクトルh→と用いて生成される値s0:=h→f→Tと、所定の値sL1とから計算される-s0-sL1を、基底B0の基底ベクトルb0,1の係数として設定して検証要素c0を生成する検証要素0生成部と、前記ベクトルf→と前記データ取得部が取得した署名データσに含まれる行列Mとに基づき生成される列ベクトルs→T:=s1,...,sLT:=Mf→Tと、i=1,...,Lの各整数iについての所定の値θiとを用いて、i=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,1の係数としてsiθivi,1を設定し、基底ベクトルbt,i’i’=2,...,ntの係数としてθivi,i’i’=2,...,ntを設定して検証要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,i’i’=1,...,ntの係数としてsivi,i’i’=1,...,ntを設定して検証要素ciを生成する検証要素i生成部と、基底Bd1の基底ベクトルbd1,1の係数として、前記所定の値sL1と前記値m’と所定の値θL1とから計算されるsL1-θL1m’を設定し、基底ベクトルbd1,2の係数として前記所定の値θL1を設定して検証要素cL1を生成する検証要素L1生成部と、前記検証要素0生成部が生成した検証要素c0と、前記検証要素i生成部が生成した検証要素ciと、前記検証要素L1生成部が生成した検証要素cL1と、前記署名データσに含まれる署名要素s0,si,sL1とについて、ペアリング演算Πi=0L1eci,siを行い、前記署名データσの正当性を検証するペアリング演算部とを備えることを特徴とする検証装置。d個dは1以上の整数の鍵生成装置と、署名装置と、検証装置とを備え、t=1,...,dの少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムであり、前記d個の鍵生成装置の各鍵生成装置は、t=1,...,dのうち鍵生成装置毎に予め定められた整数tについての属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数を入力する第1情報入力部と、前記整数tと、j=1,2の各整数jについて、前記第1情報入力部が入力した属性情報x→tと、所定の値δjと、所定の値Δと、基底Btの基底ベクトルbt,ii=1,...,2ntとに基づき、数10に示すベクトルを含む鍵要素kt,jを生成する鍵要素生成部と、前記鍵要素生成部が生成した鍵要素kt,jと、前記属性情報x→tとを含む署名鍵uskを前記署名装置へ送信する署名鍵送信部とを備え、前記署名装置は、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報v→i:=vi,i’i’=1,...,ntとの肯定形の組t,v→i又は否定形の組¬t,v→iのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mと、メッセージmとを入力する第2情報入力部と、前記d個の鍵生成装置のうち、少なくとも1つ以上の鍵生成装置の署名鍵送信部が送信した署名鍵uskを取得する署名鍵取得部と、前記第2情報入力部が入力した変数ρiと、前記署名鍵取得部が取得した署名鍵uskに含まれる属性情報xtとに基づき、i=1,...,Lの各整数iのうち、変数ρiが肯定形の組t,v→iであり、かつ、その組の識別情報tが示すxtを含む署名鍵uskを前記署名鍵取得部が取得しており、かつ、その組のv→iと、その組の識別情報tが示す属性情報x→tとの内積が0となるiと、変数ρiが否定形の組¬t,v→iであり、かつ、その組の識別情報tが示すx→tを含む署名鍵uskを前記署名鍵取得部が取得しており、かつ、その組のv→iと、その組の識別情報tが示す属性情報x→tとの内積が0とならないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記第2情報入力部が入力した行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算部と、前記署名鍵uskに含まれる鍵要素kt,1及び鍵要素kt,2と、所定の値ξ1,Ε,μと、前記メッセージmから計算される値m’とに基づき、i=1,...,Lの各整数iについて、前記補完係数計算部が特定した集合Iに含まれる整数iであり、かつ、変数ρiが肯定形の組t,v→iである場合には値γi:=αiとし、前記集合Iに含まれるiであり、かつ、変数ρiが否定形の組¬t,v→iである場合には値γi:=αi/vixtとし、前記集合Iに含まれない整数iの場合には値γi:=0として、基底Btの基底ベクトルbt,ii=2nt1,2nt2を用いて、数11に示すベクトルを含む署名要素siを生成する署名要素生成部と、前記署名要素生成部が生成したi=1,...,Lの各整数iについての署名要素siと、前記メッセージmと、前記変数ρiと、前記行列Mとを含む署名データσを前記検証装置へ送信する署名データ送信部とを備え、前記検証装置は、前記署名データ送信部が送信した署名データσを取得するデータ取得部と、r個の要素を有するベクトルf→と、前記データ取得部が取得した署名データσに含まれる行列Mとに基づき列ベクトルs→T:=s1,...,sLT:=Mf→Tを生成するとともに、s0:=h→f→Tとして、s0=h→f→’Tであるr個の要素を有するベクトルf→’と、前記行列Mとに基づき列ベクトルs→’T:=s1’,...,sL’T:=Mf→’Tを生成するベクトル生成部と、前記ベクトル生成部が生成した列ベクトルs→T及び列ベクトルs→’Tと、i=1,...,Lの各整数iについての所定の値θi,θi’,θi’’,σiとに基づき、i=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,i’i’=1,...,2nt2を用いて、数12に示すベクトルを含む検証要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,ii’=1,...,2nt2を用いて、数13に示すベクトルを含む検証要素ciを生成する検証要素生成部と、前記検証要素生成部が生成した検証要素ciと、前記署名データσに含まれる署名要素siとについて、ペアリング演算Πi=1Leci,siを行い、前記署名データσの正当性を検証するペアリング演算部とを備えることを特徴とする署名処理システム。前記署名処理システムは、t=1,...,dの少なくとも1つ以上の整数tについて、少なくとも基底ベクトルbt,ii=1,...,2nt2,...,2nt2ut,...,2nt2utwt,...,2nt2utwtztut,wt,ztは1以上の整数を有する基底Btと、少なくとも基底ベクトルbt,ii=1,...,2nt2,...,2nt2ut,...,2nt2utwt,...,2nt2utwtztを有する基底Btとを用いて署名処理を実行し、前記鍵生成装置では、前記属性情報x→tと前記所定の値δj,Δと乱数φt,j,ij=1,2;i=1,...,wtとに基づき、前記整数tと、j=1,2の各整数jについて、数14に示す鍵要素kt,jを生成し、前記署名装置では、前記署名要素生成部は、前記鍵要素kt,1及び前記鍵要素kt,2と乱数ξ1,ξ2と所定の値Ε,π,π’,μと前記値m’とに基づき、i=1,...,Lの各整数iについて、数15に示すri,γi,y→i:=yi,ii=1,...,nt,y’→i:=y’i,ii=1,...,ntを用いて、数16に示す署名要素siを生成し、前記検証装置では、前記検証要素生成部は、前記列ベクトルs→T及び前記列ベクトルs→’Tと乱数θi,θi’,θi’’と前記所定の値σiと乱数ηi,i’i=1,...,L;i’=1,...,ztとに基づき、i=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、数17に示す検証要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、数18に示す検証要素ciを生成することを特徴とする請求項7に記載の署名処理システム。前記署名装置では、前記署名要素生成部は、前記メッセージmと、前記行列Mと、i=1,...,Lの各整数iについての前記変数ρiとを入力としたハッシュ値を前記値m’として用いて、署名要素siを生成し、前記検証装置では、前記検証要素生成部は、前記ハッシュ値を前記値m’として用いて、検証要素ciを生成することを特徴とする請求項7又は8に記載の署名処理システム。t=1,...,dの少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムにおいて、署名鍵uskを生成する鍵生成装置であり、t=1,...,dのうち所定の整数tについて、属性情報x→t:=xt,ii=1,...,ntを入力する第1情報入力部と、前記整数tと、j=1,2の各整数jについて、前記第1情報入力部が入力した属性情報x→tと、所定の値δjと、所定の値Δと、基底Btの基底ベクトルbt,ii=1,...,2ntとに基づき、数19に示すベクトルを含む鍵要素kt,jを生成する鍵要素生成部と、前記鍵要素生成部が生成した鍵要素kt,jと、前記属性情報x→tとを含む署名鍵uskを署名装置へ送信する署名鍵送信部とを備えることを特徴とする鍵生成装置。t=1,...,dの少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムにおいて、署名データσを生成する署名装置であり、t=1,...,dのうち少なくとも一部の整数tと、j=1,2の各整数jとについて、属性情報x→t:=xt,ii=1,...,ntと、所定の値δjと、所定の値Δと、基底Btの基底ベクトルbt,ii=1,...,2ntとに基づき、数20に示すベクトルを含むように生成された鍵要素kt,jと、前記属性情報x→tとを含む署名鍵uskを取得する署名鍵取得部と、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報v→i:=vi,i’i’=1,...,ntとの肯定形の組t,v→i又は否定形の組¬t,v→iのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mと、メッセージmとを入力する第2情報入力部と、前記第2情報入力部が入力した変数ρiと、前記署名鍵取得部が取得した署名鍵uskに含まれる属性情報x→tとに基づき、i=1,...,Lの各整数iのうち、変数ρiが肯定形の組t,v→iであり、かつ、その組の識別情報tが示すx→tを含む署名鍵uskを前記署名鍵取得部が取得しており、かつ、その組のv→iと、その組の識別情報tが示す属性情報x→tとの内積が0となるiと、変数ρiが否定形の組¬t,v→iであり、かつ、その組の識別情報tが示すx→tを含む署名鍵uskを前記署名鍵取得部が取得しており、かつ、その組のv→iと、その組の識別情報tが示す属性情報x→tとの内積が0とならないが等しくないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記第2情報入力部が入力した行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算部と、前記署名鍵uskに含まれる鍵要素kt,1及び鍵要素kt,2と、所定の値ξ1,Ε,μと、前記メッセージmから計算される値m’とに基づき、i=1,...,Lの各整数iについて、前記補完係数計算部が特定した集合Iに含まれる整数iであり、かつ、変数ρiが肯定形の組t,v→iである場合には値γi:=αiとし、前記集合Iに含まれるiであり、かつ、変数ρiが否定形の組¬t,v→iである場合には値γi:=αi/v→ix→tとし、前記集合Iに含まれない整数iの場合には値γi:=0として、基底Btの基底ベクトルbt,ii=2nt1,2nt2を用いて、数21に示すベクトルを含む署名要素siを生成する署名要素生成部と、前記署名要素生成部が生成したi=1,...,Lの各整数iについての署名要素siと、前記メッセージmと、前記変数ρiと、前記行列Mとを含む署名データσを前記検証装置へ送信する署名データ送信部とを備えることを特徴とする署名装置。t=1,...,dの少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムにおいて、署名データσを検証する検証装置であり、i=1,...,Lの各整数iについての署名要素siと、メッセージmと、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報v→i:=vi,i’i’=1,...,ntとの肯定形の組t,v→i又は否定形の組¬t,v→iのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mとを含む署名データσを取得するデータ取得部と、r個の要素を有するベクトルf→と、前記データ取得部が取得した署名データσに含まれる行列Mとに基づき列ベクトルs→T:=s1,...,sLT:=Mf→Tを生成するとともに、s0:=h→f→Tとして、s0=h→f→’Tであるr個の要素を有するベクトルf→’と、前記行列Mとに基づき列ベクトルs→’T:=s1’,...,sL’T:=Mf→’Tを生成するベクトル生成部と、前記ベクトル生成部が生成した列ベクトルs→T及び列ベクトルs→’Tと、i=1,...,Lの各整数iについての所定の値θi,θi’,θi’’,σiとに基づき、i=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,i’i’=1,...,2nt2を用いて、数22に示すベクトルを含む検証要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,ii’=1,...,2nt2を用いて、数23に示すベクトルを含む検証要素ciを生成する検証要素生成部と、前記検証要素生成部が生成した検証要素ciと、前記署名データσに含まれる署名要素siとについて、ペアリング演算Πi=1Leci,siを行い、前記署名データσの正当性を検証するペアリング演算部とを備えることを特徴とする検証装置。t=0,...,d1dは1以上の整数の各整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理方法であり、鍵生成装置が、t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数とを含む属性集合Γを入力する第1情報入力工程と、前記鍵生成装置が、基底B0の基底ベクトルb0,1の係数として所定の値δを設定した鍵要素k0を生成する鍵要素0生成工程と、前記鍵生成装置が、前記第1情報入力工程で入力された属性集合Γに含まれる各識別情報tについて、基底Btの基底ベクトルbt,ii=1,...,ntの係数として属性情報x→tに前記所定の値δを乗じたδxt,ii=1,...,ntを設定した鍵要素ktを生成する鍵要素t生成工程と、前記鍵生成装置が、基底Bd1の基底ベクトルbd1,1の係数として前記所定の値δを設定した鍵要素kd1,1と、基底Bd1の基底ベクトルbd1,2の係数として前記所定の値δを設定した鍵要素kd1,2とを生成する鍵要素d1生成工程と、前記鍵生成装置が、前記鍵要素0生成工程で生成された鍵要素k0と、前記鍵要素t生成工程で生成された前記属性集合Γに含まれる各識別情報tについての鍵要素ktと、前記鍵要素d1生成工程で生成された鍵要素kd1,1及び鍵要素kd1,2と、前記属性集合Γとを含む署名鍵skΓを署名装置へ送信する署名鍵送信工程と、前記署名装置が、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報v→i:=vi,i’i’=1,...,ntとの肯定形の組t,v→i又は否定形の組¬t,v→iのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mと、メッセージmとを入力する第2情報入力工程と、前記署名装置が、前記署名鍵送信工程で送信された署名鍵skΓを取得する署名鍵取得工程と、前記署名装置が、前記第2情報入力工程で入力された変数ρiと、前記署名鍵取得工程で取得された署名鍵skΓに含まれる属性集合Γとに基づき、i=1,...,Lの各整数iのうち、変数ρiが肯定形の組t,v→iであり、かつ、その組のv→iと、その組の識別情報tが示す属性集合Γに含まれるx→tとの内積が0となるiと、変数ρiが否定形の組¬t,v→iであり、かつ、その組のv→iと、その組の識別情報tが示す属性集合Γに含まれるx→tとの内積が0とならないiとの集合Iを特定するとともに、特定された集合Iに含まれるiについて、前記第2情報入力工程で入力された行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算工程と、前記署名装置が、前記署名鍵skΓに含まれる鍵要素k0を含む署名要素s0を生成する署名要素0生成工程と、前記署名装置が、i=1,...,Lの各整数iについて、前記補完係数計算工程で特定された集合Iに含まれる整数iであり、かつ、変数ρiが肯定形の組t,v→iである場合には値γi:=αiとし、前記集合Iに含まれるiであり、かつ、変数ρiが否定形の組¬t,v→iである場合には値γi:=αi/v→ix→tとし、前記集合Iに含まれない整数iの場合には値γi:=0として、前記署名鍵skΓに含まれる鍵要素ktに前記値γiを乗じたγiktを含む署名要素siを生成する署名要素i生成工程と、前記署名装置が、前記署名鍵skΓに含まれる鍵要素kd1,1と、前記メッセージmを用いて生成される値m’を前記鍵要素kd1,2に乗じたm’kd1,2との和を含む署名要素sL1を生成する署名要素L1生成工程と、前記署名装置が、前記署名要素0生成工程で生成された署名要素s0と、前記署名要素i生成工程で生成されたi=1,...,Lの各整数iについての署名要素siと、前記署名要素L1生成工程で生成された署名要素sL1と、前記メッセージmと、前記変数ρ従来の属性ベース署名方式では、ノンモノトーン述語をサポートしていなかった。この発明は、ノンモノトーン述語をサポートした属性ベース署名方式を提供することを目的とする。この発明に係る署名処理システムは、鍵生成装置と署名装置と検証装置とを備え、t=0,...,d1dは1以上の整数の各整数tについての基底Btと基底Btとを用いて署名処理を実行する署名処理システムであり、前記鍵生成装置は、t=1,...,dの少なくとも1つ以上の整数tについて、識別情報tと、属性情報xtとを含む属性集合Γを入力する第1情報入力部と、基底B0の基底ベクトルb0,1の係数として所定の値δを設定した鍵要素k0を生成する鍵要素0生成部と、前記第1情報入力部が入力した属性集合Γに含まれる各識別情報tについて、基底Btの基底ベクトルbt,1の係数として前記所定の値δを設定し、基底ベクトルbt,2の係数として属性情報xtに前記所定の値δを乗じたδxtを設定した鍵要素ktを生成する鍵要素t生成部と、基底Bd1の基底ベクトルbd1,1の係数として前記所定の値δを設定した鍵要素kd1,1と、基底Bd1の基底ベクトルbd1,2の係数として前記所定の値δを設定した鍵要素kd1,2とを生成する鍵要素d1生成部と、前記鍵要素0生成部が生成した鍵要素k0と、前記鍵要素t生成部が生成した前記属性集合Γに含まれる各識別情報tについての鍵要素ktと、前記鍵要素d1生成部が生成した鍵要素kd1,1及び鍵要素kd1,2と、前記属性集合Γとを含む署名鍵skΓを前記署名装置へ送信する署名鍵送信部とを備え、前記署名装置は、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報viとの肯定形の組t,vi又は否定形の組¬t,viのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mと、メッセージmとを入力する第2情報入力部と、前記署名鍵送信部が送信した署名鍵skΓを取得する署名鍵取得部と、前記第2情報入力部が入力した変数ρiと、前記署名鍵取得部が取得した署名鍵skΓに含まれる属性集合Γとに基づき、i=1,...,Lの各整数iのうち、変数ρiが肯定形の組t,viであり、かつ、その組のviと、その組の識別情報tが示す属性集合Γに含まれるxtとが等しいiと、変数ρiが否定形の組¬t,viであり、かつ、その組のviと、その組の識別情報tが示す属性集合Γに含まれるxtとが等しくないiとの集合Iを特定するとともに、特定した集合Iに含まれるiについて、前記第2情報入力部が入力した行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算部と、前記署名鍵skΓに含まれる鍵要素k0を含む署名要素s0を生成する署名要素0生成部と、i=1,...,Lの各整数iについて、前記補完係数計算部が特定した集合Iに含まれる整数iであり、かつ、変数ρiが肯定形の組t,viである場合には値γi:=αiとし、前記集合Iに含まれるiであり、かつ、変数ρiが否定形の組¬t,viである場合には値γi:=αi/vi-xtとし、前記集合Iに含まれない整数iの場合には値γi:=0として、前記署名鍵skΓに含まれる鍵要素ktに前記値γiを乗じたγiktを含む署名要素siを生成する署名要素i生成部と、前記署名鍵skΓに含まれる鍵要素kd1,1と、前記メッセージmを用いて生成される値m’を前記鍵要素kd1,2に乗じたm’kd1,2との和を含む署名要素sL1を生成する署名要素L1生成部と、前記署名要素0生成部が生成した署名要素s0と、前記署名要素i生成部が生成したi=1,...,Lの各整数iについての署名要素siと、前記署名要素L1生成部が生成した署名要素sL1と、前記メッセージmと、前記変数ρiと、前記行列Mとを含む署名データσを前記検証装置へ送信する署名データ送信部とを備え、前記検証装置は、前記署名データ送信部が送信した署名データσを取得するデータ取得部と、r個の要素を有するベクトルf→と前記ベクトルh→と用いて生成される値s0:=h→f→Tと、所定の値sL1とから計算される-s0-sL1を、基底B0の基底ベクトルb0,1の係数として設定して検証要素c0を生成する検証要素0生成部と、前記ベクトルf→と前記データ取得部が取得した署名データσに含まれる行列Mとに基づき生成される列ベクトルs→T:=s1,...,sLT:=Mf→Tと、i=1,...,Lの各整数iについての所定の値θiとを用いて、i=1,...,Lの各整数iについて、変数ρiが肯定形の組t,viである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,1の係数としてsiθiviを設定し、基底ベクトルbt,2の係数として-θiを設定して検証要素ciを生成し、変数ρiが否定形の組¬t,viである場合には、その組の識別情報tが示す基底ベクトルbt,1の係数としてsiviを設定し、基底ベクトルbt,2の係数として-siを設定して検証要素ciを生成する検証要素i生成部と、基底Bd1の基底ベクトルbd1,1の係数として、前記所定の値sL1と前記値m’と所定の値θL1とから計算されるsL1-θL1m’を設定し、基底ベクトルbd1,2の係数として前記所定の値θL1を設定して検証要素cL1を生成する検証要素L1生成部と、前記検証要素0生成部が生成した検証要素c0と、前記検証要素i生成部が生成した検証要素ciと、前記検証要素L1生成部が生成した検証要素cL1と、前記署名データσに含まれる署名要素s0,si,sL1とについて、ペアリング演算Πi=0L1eci,siを行い、前記署名データσの正当性を検証するペアリング演算部とを備えることを特徴とする。この発明に係る属性ベース署名方式では、ノンモノトーン述語をサポートしている。そのため、利用範囲の広い属性ベース署名方式を実現している。以下、図に基づき、発明の実施の形態を説明する。以下の説明において、処理装置は後述するCPU911等である。記憶装置は後述するROM913、RAM914、磁気ディスク920等である。通信装置は後述する通信ボード915等である。入力装置は後述するキーボード902、通信ボード915等である。つまり、処理装置、記憶装置、通信装置、入力装置はハードウェアである。以下の説明における記法について説明する。Aがランダムな変数または分布であるとき、数101は、Aの分布に従いAからyをランダムに選択することを表す。つまり、数101において、yは乱数である。Aが集合であるとき、数102は、Aからyを一様に選択することを表す。つまり、数102において、yは一様乱数である。数103は、yがzにより定義された集合であること、又はyがzを代入された集合であることを表す。aが定数であるとき、数104は、機械アルゴリズムAが入力xに対しaを出力することを表す。数105、つまりFqは、位数qの有限体を示す。ベクトル表記は、有限体Fqにおけるベクトル表示を表す。つまり、数106である。数107は、数108に示す2つのベクトルx→とv→との数109に示す内積を表す。XTは、行列Xの転置行列を表す。bii=1,...,nが空間Vのベクトルの要素であるとき、つまり、数110であるとき、数111は、数112によって生成される部分空間を表す。数113に示す基底Bと基底Bとに対して、数114である。また、以下の説明において、paramVtにおけるVtはVtのことである。同様に、Fqntにおけるntはntのことである。同様に、skgid,t,xtにおけるxtはxtのことである。同様に、δi,jが上付きで示されている場合、このδi,jは、δi,jを意味する。また、ベクトルを意味する→が下付き文字又は上付き文字に付されている場合、この→は下付き文字又は上付き文字に上付きで付されていることを意味する。また、以下の説明において、署名処理とは、鍵生成処理、署名処理、検証処理を含むものである。実施の形態1.この実施の形態では、属性ベース署名方式について説明する。第1に、属性ベース署名について簡単に説明する。第2に、属性ベース署名方式を実現するための空間である双対ペアリングベクトル空間DualPairingVectorSpaces,DPVSという豊かな数学的構造を有する空間を説明する。第3に、属性ベース署名方式を実現するための概念を説明する。ここでは、スパンプログラムSpanProgram、属性ベクトルの内積とアクセスストラクチャ、秘密分散方式秘密共有方式について説明する。また、衝突困難ハッシュ関数CollisionResistantHashFunctionsについても説明する。第4に、この実施の形態に係る属性ベース署名方式を説明する。まず、属性ベース署名方式の基本構成について説明する。次に、属性ベース署名方式を実現する署名処理システム10の基本構成について説明する。そして、この実施の形態に係る属性ベース署名方式及び署名処理システム10について詳細に説明する。<第1.属性ベース署名>デジタル署名の概念は、DiffieとHellmanとによって1976年に論文で紹介された。そこでは、デジタル署名の概念は、秘密にされる署名鍵skと公開される検証鍵pkとのペアが署名者に対して生成され、署名鍵skを用いて生成されたメッセージmの署名σが、対応する検証鍵pkによって検証されることとされた。つまり、署名鍵skを使って署名されたメッセージm,σの署名者が、検証鍵pkによって確認されることとされた。これは、デジタル署名の要件の1つではある。しかし、署名鍵skと検証鍵pkとの関係が密接なため、署名者と署名によって証明される内容との間の関係に柔軟性やプライバシーがない。署名鍵と検証鍵との関係がより柔軟になり又は洗練されることで、用途が広く、プライバシーが向上したデジタル署名の改良型が研究されている。署名のこのクラスでは、署名鍵と検証鍵とはそれぞれ、属性xと述語vとによってパラメータ化されている。そして、署名されたメッセージm,σは、パラメータxを伴う署名鍵skxによって生成され、公開された鍵pkとパラメータvとによって、述語vが属性xを受理する場合vxが成立する場合にのみ、正しいことが検証される。署名のこのクラスにおける署名者のプライバシーとは、署名鍵skxによって生成された述語vに対する署名が、vxが成立することを除き属性xに関する情報を漏らさないことである。述語vがパラメータvとの等号関係である場合つまり、x=vの場合にのみvxが成立する場合、この述語に対する署名のクラスはIDベース署名Identity-BasedSignatures,IBSである非特許文献46参照。なお、IDベース署名では、x=vのように、署名者の秘密鍵であるskxの属性xを述語vが一意に識別する。そのため、IDベース署名にはプライバシーの余地はない。グループ署名GroupSignaturesは、署名のこのクラスに含まれる署名である非特許文献19参照。グループ署名は、述語のパラメータvがグループ識別子であり、属性xがグループvのメンバーの識別子である又はpkvがグループvを識別する公開鍵であり、skxがグループvのメンバーxの秘密鍵である場合にのみ、vxが成立するという述語vを伴う署名である。プライバシーの要件に基づき、秘密鍵skxを使って生成された署名はxがグループvのメンバーであることを除き、識別子xに関する情報を漏らさない。属性ベース署名は、署名のこのクラス含まれる署名であり、より洗練された述語を伴う署名である非特許文献26,29,30,34-36,45,51参照。属性ベース署名は、署名鍵skxに対するxが属性x1,...,xiの組であり、検証のためのvが閾値又はアクセスストラクチャの述語である。存在する属性ベース署名方式における述語の最も広いクラスはモノトーンアクセスストラクチャである非特許文献36,37参照。モノトーンアクセスストラクチャでは、述語vは、属性v1,...,vjの組を伴うモノトーンスパンプログラムM,ρMSPM,ρによって特定され、MSPM,ρがTxi_1=v1,...,Txi_j=vjの真の値のベクトルを受理する場合のみ、vxが成立する。ここで、φが真である場合、Tφ:=1であり、φが偽である場合、Tφ:=1である。例えば、x=vである場合、Tx=v:=1であり、x≠vである場合、Tx=v:=0である。このようなモノトーン述語は、AND、OR、閾値のゲートを表現することができる。属性ベース署名に対するモノトーン述語vの例を説明する。モノトーン述語vの例としては、Institute=Univ.AANDTH2Department=Biology,Gender=Female,Age=50‘sORPosition=Professorである。ここで、TH2は閾値の値が2の閾値ゲートつまり、2つ以上成立することを要求するゲートを意味する。アリスの属性xAが、Institute=Univ.A,Department=Biology,Position=Postdoc,Age=30,Gender=Femaleであり、ボブの属性xBが、Institute=Univ.A,Department=Mathematics,Position=Professor,Age=45,Gender=Maleであるとする。属性xAと属性xBとは全く異なるが、vxAとvxBとがいずれも成立することは明らかである。また、述語vを満たす他の多くの属性があることは明らかである。そのため、アリスとボブとは、この述語における署名を生成することができる。また、属性ベース署名のプライバシー要件に基づき、署名者の属性が述語vを満たすことを除き、述語vに対する署名は署名者、つまりアリスとボブ又はその他の属性に関して情報を漏らさない。属性ベース署名には、属性ベースメッセージングAttributed-BasedMassaging,ABM、属性ベース認証Attributed-Basedauthentication、trust-negotiation、leakingsecrets等の多くのアプリケーションが存在する非特許文献36,37参照。しかし、ノンモノトーン述語に対する属性ベース署名方式は、弱い安全性のものであっても存在しなかった。ノンモノトーン述語は、AND、OR、閾値のゲートと同様に、NOTのゲートを表現することができる。つまり、モノトーン述語では、Institute=Univ.Aのように、肯定形の条件は設定できるが、Institute≠Univ.Aつまり、NotInstitute=Univ.Aのように否定形の条件は設定できない。これに対して、ノンモノトーン述語では、否定形の条件を設定できる。大学がUniv.A以外にも多数存在する場合、肯定形の条件のみを用いて、Univ.A以外という否定形の条件を設定するのは困難である記述が複雑になる。このことからも、ノンモノトーン述語の有用性が分かる。<第2.双対ペアリングベクトル空間>まず、対称双線形ペアリング群SymmetricBilinearPairingGroupsについて説明する。対称双線形ペアリング群q,G,GT,g,eは、素数qと、位数qの巡回加法群Gと、位数qの巡回乗法群GTと、g≠0∈Gと、多項式時間で計算可能な非退化双線形ペアリングNondegenerateBilinearPairinge:G×G→GTとの組である。非退化双線形ペアリングは、esg,tg=eg,gstであり、eg,g≠1である。以下の説明において、数115を、1λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を出力するアルゴリズムとする。次に、双対ペアリングベクトル空間について説明する。双対ペアリングベクトル空間q,V,GT,A,eは、対称双線形ペアリング群paramG:=q,G,GT,g,eの直積によって構成することができる。双対ペアリングベクトル空間q,V,GT,A,eは、素数q、数116に示すFq上のN次元ベクトル空間V、位数qの巡回群GT、空間Vの標準基底A:=a1,...,aNの組であり、以下の演算12を有する。ここで、aiは、数117に示す通りである。演算1:非退化双線形ペアリング空間Vにおけるペアリングは、数118によって定義される。これは、非退化双線形である。つまり、esx,ty=ex,ystであり、全てのy∈Vに対して、ex,y=1の場合、x=0である。また、全てのiとjとに対して、eai,aj=eg,gδi,jである。ここで、i=jであれば、δi,j=1であり、i≠jであれば、δi,j=0である。また、eg,g≠1∈GTである。演算2:ディストーション写像数119に示す空間Vにおける線形変換φi,jは、数120を行うことができる。ここで、線形変換φi,jをディストーション写像と呼ぶ。以下の説明において、数121を、1λλ∈自然数、N∈自然数、双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を入力として、セキュリティパラメータがλであり、N次元の空間Vとする双対ペアリングベクトル空間のパラメータparamV:=q,V,GT,A,eの値を出力するアルゴリズムとする。なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。<第3.属性ベース署名方式を実現するための概念><第3-1.スパンプログラム>図1は、行列M^の説明図である。{p1,...,pn}を変数の集合とする。M^:=M,ρは、ラベル付けされた行列である。ここで、行列Mは、Fq上のL行×r列の行列である。また、ρは、行列Mの各列に付されたラベルであり、{p1,...,pn,¬p1,...,¬pn}のいずれか1つのリテラルへ対応付けられる。なお、Mの全ての行に付されたラベルρii=1,...,Lがいずれか1つのリテラルへ対応付けられる。つまり、ρ:{1,...,L}→{p1,...,pn,¬p1,...,¬pn}である。全ての入力列δ∈{0,1}nに対して、行列Mの部分行列Mδは定義される。行列Mδは、入力列δによってラベルρに値1が対応付けられた行列Mの行から構成される部分行列である。つまり、行列Mδは、δi=1であるようなpiに対応付けられた行列Mの行と、δi=0であるような¬piに対応付けられた行列Mの行とからなる部分行列である。図2は、行列Mδの説明図である。なお、図2では、n=7,L=6,r=5としている。つまり、変数の集合は、{p1,...,p7}であり、行列Mは6行×5列の行列である。また、図2において、ラベルρは、ρ1が¬p2に、ρ2がp1に、ρ3がp4に、ρ4が¬p5に、ρ5が¬p3に、ρ6がp5にそれぞれ対応付けられているとする。ここで、入力列δ∈{0,1}7が、δ1=1,δ2=0,δ3=1,δ4=0,δ5=0,δ6=1,δ7=1であるとする。この場合、破線で囲んだリテラルp1,p3,p6,p7,¬p2,¬p4,¬p5に対応付けられている行列Mの行からなる部分行列が行列Mδである。つまり、行列Mの1行目M1,2行目M2,4行目M4からなる部分行列が行列Mδである。言い替えると、写像γ:{1,...,L}→{0,1}が、[ρj=pi]∧[δi=1]又は[ρj=¬pi]∧[δi=0]である場合、γj=1であり、他の場合、γj=0であるとする。この場合に、Mδ:=Mjγj=1である。ここで、Mjは、行列Mのj番目の行である。つまり、図2では、写像γj=1j=1,2,4であり、写像γj=0j=3,5,6である。したがって、Mjγj=1は、M1,M2,M4であり、行列Mδである。すなわち、写像γjの値が0であるか1であるかによって、行列Mのj番目の行が行列Mδに含まれるか否かが決定される。1→∈span<Mδ>である場合に限り、スパンプログラムM^は入力列δを受理し、他の場合には入力列δを拒絶する。つまり、入力列δによって行列M^から得られる行列Mδの行を線形結合して1→が得られる場合に限り、スパンプログラムM^は入力列δを受理する。なお、1→とは、各要素が値1である行ベクトルである。例えば、図2の例であれば、行列Mの1,2,4行目からなる行列Mδの各行を線形結合して1→が得られる場合に限り、スパンプログラムM^は入力列δを受理する。つまり、α1M1α2M2α4M4=1→となるα1,α2,α4が存在する場合には、スパンプログラムM^は入力列δを受理する。ここで、ラベルρが正のリテラル{p1,...,pn}にのみ対応付けられている場合、スパンプログラムはモノトーンと呼ばれる。一方、ラベルρがリテラル{p1,...,pn,¬p1,...,¬pn}に対応付けられている場合、スパンプログラムはノンモノトーンと呼ばれる。ここでは、スパンプログラムはノンモノトーンとする。そして、ノンモノトーンスパンプログラムを用いて、アクセスストラクチャノンモノトーンアクセスストラクチャを構成する。上述したように、スパンプログラムがモノトーンではなく、ノンモノトーンであることにより、スパンプログラムを利用して構成する属性ベース署名方式の利用範囲が広がる。<第3-2.属性ベクトルの内積とアクセスストラクチャ>ここでは、属性ベクトルの内積を用いて上述した写像γjを計算する。つまり、属性ベクトルの内積を用いて、行列Mのどの行を行列Mδに含めるかを決定する。Utt=1,...,dでありUt⊂{0,1}は、部分全集合sub-universeであり、属性の集合である。そして、Utは、それぞれ部分全集合の識別情報tと、nt次元ベクトルv→とを含む。つまり、Utは、t,v→である。ここで、t∈{1,...,d}であり、v→∈Fqntである。Ut:=t,v→をスパンプログラムM^:=M,ρにおける変数pとする。つまり、p:=t,v→である。そして、変数p:=t,v→,t’,v’→,...としたスパンプログラムM^:=M,ρをアクセスストラクチャSとする。つまり、アクセスストラクチャS:=M,ρであり、ρ:{1,...,L}→{t,v→,t’,v’→,...,¬t,v→,¬t’,v’→,...}である。次に、Γを属性の集合とする。つまり、Γ:={t,x→t|x→t∈Fqnt,1≦t≦d}である。アクセスストラクチャSにΓが与えられた場合、スパンプログラムM^:=M,ρに対する写像γ:{1,...,L}→{0,1}は、以下のように定義される。i=1,...,Lの各整数iについて、[ρi=t,v→i]∧[t,x→t∈Γ]∧[v→ix→t=0]、又は、[ρi=¬t,v→i]∧[t,x→t∈Γ]∧[v→ix→t≠0]である場合、γj=1であり、他の場合、γj=0とする。つまり、属性ベクトルv→とx→との内積に基づき、写像γが計算される。そして、上述したように、写像γにより、行列Mのどの行を行列Mδに含めるかが決定される。すなわち、属性ベクトルv→とx→との内積により、行列Mのどの行を行列Mδに含めるかが決定され、1→∈span<Miγi=1>である場合に限り、アクセスストラクチャS:=M,ρはΓを受理する。t∈{1,...,d}の全ての整数tについて、nt=2とし、x→:=1,x、v→:=v,-1とした場合、このアクセスストラクチャにおける内積述語の関係がより簡単な形式になる。この場合、t,x→t:=t,1,x,t,v→i:=t,vi,-1である。しかし、これらを簡単化してt,xt、t,viと表す。すると、アクセスストラクチャSは、ρ:={1,...,L}→{t,v,t’、v’,...,¬t,v,¬t’,v’,...}v,v’,...∈FqであるS:=M,ρとなる。また、属性の集合Γは、Γ:={t,xt|xt∈Fq,1≦t≦d}となる。そして、アクセスストラクチャSにΓが与えられた場合、スパンプログラムM^:=M,ρに対する写像γ:{1,...,L}→{0,1}は、以下のように定義される。i=1,...,Lの各整数iについて、[ρi=t,vi]∧[t,xt∈Γ]∧[vi=xt]、又は、[ρi=¬t,vi]∧[t,xt∈Γ]∧[vi≠xt]である場合、γj=1であり、他の場合、γj=0とする。<第3-3.秘密分散方式>アクセスストラクチャS:=M,ρに対する秘密分散方式について説明する。なお、秘密分散方式とは、秘密情報を分散させ、意味のない分散情報にすることである。例えば、秘密情報sを10個に分散させ、10個の分散情報を生成する。ここで、10個の分散情報それぞれは、秘密情報sの情報を有していない。したがって、ある1個の分散情報を手に入れても秘密情報sに関して何ら情報を得ることはできない。一方、10個の分散情報を全て手に入れれば、秘密情報sを復元できる。また、10個の分散情報を全て手に入れなくても、一部だけ例えば、8個手に入れれば秘密情報sを復元できる秘密分散方式もある。このように、10個の分散情報のうち8個で秘密情報sを復元できる場合を、8-out-of-10と呼ぶ。つまり、n個の分散情報のうちt個で秘密情報sを復元できる場合を、t-out-of-nと呼ぶ。このtを閾値と呼ぶ。また、d1,...,d10の10個の分散情報を生成した場合に、d1,...,d8までの8個の分散情報であれば秘密情報sを復元できるが、d3,...,d10までの8個の分散情報であれば秘密情報sを復元できないというような秘密分散方式もある。つまり、手に入れた分散情報の数だけでなく、分散情報の組合せに応じて秘密情報sを復元できるか否かを制御する秘密分散方式もある。図3は、s0の説明図である。図4は、s→Tの説明図である。行列MをL行×r列の行列とする。f→Tを数122に示す列ベクトルとする。数123に示すs0を共有される秘密情報とする。また、数124に示すs→Tをs0のL個の分散情報のベクトルとする。そして、分散情報siをρiに属するものとする。アクセスストラクチャS:=M,ρがΓを受理する場合、つまりγ:{1,...,L}→{0,1}について1→∈span<Miγi=1>である場合、I⊆{i∈{1,...,L}|γi=1}である定数{αi∈Fq|i∈I}が存在する。これは、図2の例で、α1M1α2M2α4M4=1→となるα1,α2,α4が存在する場合には、スパンプログラムM^は入力列δを受理すると説明したことからも明らかである。つまり、α1M1α2M2α4M4=1→となるα1,α2,α4が存在する場合には、スパンプログラムM^が入力列δを受理するのであれば、α1M1α2M2α4M4=1→となるα1,α2,α4が存在する。そして、数125である。なお、定数{αi}は、行列Mのサイズにおける多項式時間で計算可能である。この実施の形態及び以下の実施の形態に係る属性ベース署名方式は、上述したように、スパンプログラムに内積述語と秘密分散方式とを適用してアクセスストラクチャを構成する。そのため、スパンプログラムにおける行列Mや、内積述語における属性情報x及び属性情報v述語情報を設計することにより、アクセス制御を自由に設計することができる。つまり、非常に高い自由度でアクセス制御の設計を行うことができる。なお、行列Mの設計は、秘密分散方式の閾値等の条件設計に相当する。特に、この実施の形態及び以下の実施の形態に係る属性ベース署名方式におけるアクセスストラクチャは、ノンモノトーンスパンプログラムを用いたノンモノトーンアクセスストラクチャを構成する。つまり、この実施の形態及び以下の実施の形態に係る属性ベース署名方式は、ノンモノトーン述語を伴う署名方式である。そのため、アクセス制御の設計の自由度がより高くなる。<第3-4.衝突困難ハッシュ関数>衝突困難ハッシュ関数とは、出力が同じになる2つの入力を見つけることが困難なハッシュ関数である。自然数λをセキュリティパラメータとする。アルゴリズムGbpgに関する衝突困難ハッシュ関数系Hと、多項式polyλとについて以下の2つのことが言える。1.鍵空間系は、λによって索引付けされる。各鍵空間は、KHλによって示されるビット列における確率空間である。1λを入力とした場合の出力分布がKHλと等しい確率的多項式時間アルゴリズムが存在する。2.ハッシュ関数系は、λと、KHλからランダムに選択されたhkと、D:={0,1}polyλとによって索引付けされる。ここで、各関数Hhkλ,Dは、Dの要素からFqXへの写像である。なお、qは、アルゴリズムGbpg1λの出力paramGの最初の要素である。1λとhkとd∈Dとを入力として、Hhkλ,Ddを出力する決定的多項式時間アルゴリズムがある。εを確率的多項式時間機械であるとする。全てのλに対して、数126を定義する。どんな確率的多項式時間攻撃者εに対しても、AdvεH,CRλが無視し得る程度であるなら、Hは衝突困難ハッシュ関数系である。<第4.属性ベース署名方式の構成><第4-1.属性ベース署名方式の基本構成>属性ベース署名方式は、Setup、KeyGen、Sig、Verの4つのアルゴリズムを備える。SetupSetupアルゴリズムは、セキュリティパラメータλと、属性のフォーマットn→:=d;nt,ut,wt,ztt=1,...,dとを入力として、公開パラメータpkと、マスター鍵skとを出力する確率的アルゴリズムである。KeyGenKeyGenアルゴリズムは、属性の集合であるΓ:={t,x→t|x→t∈Fqnt\0→,1≦t≦d}と、公開パラメータpkと、マスター鍵skとを入力として、署名鍵skΓを出力する確率的アルゴリズムである。SigSigアルゴリズムは、メッセージmと、属性の集合Γを受理するようなアクセスストラクチャS:=M,ρと、署名鍵skΓと、公開パラメータpkとを入力として、署名s→とメッセージmとアクセスストラクチャSとを含む署名データσを出力する確率的アルゴリズムである。VerVerアルゴリズムは、署名データσと、公開パラメータpkとを入力として、ブール値1受理又は0拒絶を出力するアルゴリズムである。属性ベース署名方式は、数127に示す全ての公開パラメータpk及びマスター鍵skと、全てのメッセージmと、全ての属性の集合Γと、数128に示す全ての署名鍵skΓと、属性の集合Γを受理する全てのアクセスストラクチャSと、数129に示す全ての署名データσとに対して、確率1で1=Verpk,m,S,σが成立する。<第4-2.署名処理システム10>上述した属性ベース署名方式のアルゴリズムを実行する署名処理システム10について説明する。図5は、属性ベース署名方式のアルゴリズムを実行する署名処理システム10の構成図である。署名処理システム10は、鍵生成装置100、署名装置200、検証装置300を備える。鍵生成装置100は、セキュリティパラメータλと、属性のフォーマットn→:=d;nt,ut,wt,ztt=1,...,dとを入力としてSetupアルゴリズムを実行して、公開パラメータpkとマスター鍵skとを生成する。そして、鍵生成装置100は、生成した公開パラメータpkを公開する。また、鍵生成装置100は、属性の集合であるΓ:={t,x→t|x→t∈Fqnt\0→,1≦t≦d}と、公開パラメータpkと、マスター鍵skとを入力としてKeyGenアルゴリズムを実行して、署名鍵skΓを生成して署名装置200へ秘密裡に配布する。署名装置200は、メッセージmと、属性の集合Γを受理するようなアクセスストラクチャS:=M,ρと、署名鍵skΓと、公開パラメータpkとを入力としてSigアルゴリズムを実行して、署名s→とメッセージmとアクセスストラクチャSとを含む署名データσを生成する。署名装置200は、生成した署名データσを検証装置300へ送信する。検証装置300は、署名データσと、公開パラメータpkとを入力としてVerアルゴリズムを実行して、ブール値1受理又は0拒絶を出力する。<第4-3.属性ベース署名方式及び署名処理システム10の詳細>図6から図12に基づき、属性ベース署名方式、及び、属性ベース署名方式を実行する署名処理システム10の機能と動作とについて説明する。図6は、鍵生成装置100の機能を示す機能ブロック図である。図7は、署名装置200の機能を示す機能ブロック図である。図8は、検証装置300の機能を示す機能ブロック図である。図9と図10とは、鍵生成装置100の動作を示すフローチャートである。なお、図9はSetupアルゴリズムの処理を示すフローチャートであり、図10はKeyGenアルゴリズムの処理を示すフローチャートである。図11は、署名装置200の動作を示すフローチャートであり、Sigアルゴリズムの処理を示すフローチャートである。図12は、検証装置300の動作を示すフローチャートであり、Verアルゴリズムの処理を示すフローチャートである。鍵生成装置100の機能と動作とについて説明する。図6に示すように、鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130第1情報入力部、署名鍵生成部140、鍵配布部150署名鍵送信部を備える。また、署名鍵生成部140は、乱数生成部141、鍵要素0生成部142、鍵要素t生成部143、鍵要素d1生成部144を備える。なお、以下の説明において、H:=KHλ,Hhkλ,Dは、上述した衝突困難ハッシュ関数系である。まず、図9に基づき、鍵生成装置100が実行するSetupアルゴリズムの処理について説明する。S101:正規直交基底生成ステップマスター鍵生成部110は、処理装置により、数130を計算して、paramn→と、t=0,...,d1の各整数tについて基底Bt及び基底Btとをランダムに生成する。つまり、マスター鍵生成部110は以下の処理を実行する。1マスター鍵生成部110は、入力装置により、セキュリティパラメータλ1λと、属性のフォーマットn→:=d;nt,ut,wt,ztt=0,...,d1とを入力する。ここで、dは1以上の整数である。t=0についてのntは1であり、t=1,...,dまでの各整数tについてntは1以上の整数であり、t=d1についてのntは2である。t=0,...,d1までの各整数tについてut,wt,ztは1以上の整数である。2マスター鍵生成部110は、処理装置により、1で入力したセキュリティパラメータλ1λを入力としてアルゴリズムGbpgを実行して、ランダムに双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を生成する。3マスター鍵生成部110は、処理装置により、乱数ψを生成する。また、マスター鍵生成部110は、t=0,...,d1の各整数tについてNtにntutwtztを設定する。続いて、マスター鍵生成部110は、t=0,...,d1の各整数tについて以下の4から8までの処理を実行する。4マスター鍵生成部110は、処理装置により、1で入力したセキュリティパラメータλ1λと、3で設定したNtと、2で生成したparamG:=q,G,GT,g,eの値とを入力としてアルゴリズムGdpvsを実行して、双対ペアリングベクトル空間のパラメータparamVt:=q,Vt,GT,At,eの値を生成する。5マスター鍵生成部110は、処理装置により、3で設定したNtと、Fqとを入力として、線形変換Xt:=χt,i,ji,jをランダムに生成する。なお、GLは、GeneralLinearの略である。つまり、GLは、一般線形群であり、行列式が0でない正方行列の集合であり、乗法に関し群である。また、χt,i,ji,jは、行列χt,i,jの添え字i,jに関する行列という意味であり、ここでは、i,j=1,...,ntである。6マスター鍵生成部110は、処理装置により、乱数ψと線形変換Xtとに基づき、νt,i,ji,j:=ψXtT-1を生成する。なお、νt,i,ji,jもχt,i,ji,jと同様に、行列νt,i,jの添え字i,jに関する行列という意味であり、ここでは、i,j=1,...,ntである。7マスター鍵生成部110は、処理装置により、5で生成した線形変換Xtに基づき、4で生成した標準基底Atから基底Btを生成する。8マスター鍵生成部110は、処理装置により、6で生成したνt,i,ji,jに基づき、4で生成した標準基底Atから基底Btを生成する。9マスター鍵生成部110は、処理装置により、gTにeg,gψを設定する。また、マスター鍵生成部110は、paramn→に4で生成した{paramVt}t=0,...,d1と、gTとを設定する。なお、t=0,...,d1とi=1,...,Ntとの各整数t,iについて、gT=ebt,i,bt,iである。すなわち、S101で、マスター鍵生成部110は、数131に示すアルゴリズムGobを実行して、paramn→と、t=0,...,d1の各整数tについて基底Bt及び基底Btとを生成する。S102:ハッシュキー生成ステップマスター鍵生成部110は、処理装置により、数132を計算して、ハッシュキーhkをランダムに生成する。S103:公開パラメータ生成ステップマスター鍵生成部110は、処理装置により、基底B0の部分基底B^0と、t=1,...,dの各整数tについて基底Btの部分基底B^tと、基底Bd1の部分基底B^d1とを数133に示すように生成する。また、マスター鍵生成部110は、処理装置により、t=1,...,dの各整数tについて基底Btの部分基底B^tと、基底Bd1の部分基底B^d1とを数134に示すように生成する。マスター鍵生成部110は、生成した部分基底B^tt=0,...,d1と部分基底B^tt=1,...,d1と、S101で入力されたセキュリティパラメータλ1λと、S101で生成したparamn→と、S102で生成したハッシュキーhkと、基底ベクトルb0,1u01,...,b0,1u0w0ここでu0、w0は、u0,w0のことであるとを合わせて、公開パラメータpkとする。S104:マスター鍵生成ステップマスター鍵生成部110は、基底B0の基底ベクトルb0,1をマスター鍵skとする。S105:マスター鍵記憶ステップマスター鍵記憶部120は、S103で生成した公開パラメータpkを記憶装置に記憶する。また、マスター鍵記憶部120は、S104で生成したマスター鍵skを記憶装置に記憶する。つまり、S101からS104において、鍵生成装置100は数135に示すSetupアルゴリズムを実行して、公開パラメータpkとマスター鍵skとを生成する。そして、S105で、鍵生成装置100は生成された公開パラメータpkとマスター鍵skとを記憶装置に記憶する。なお、公開パラメータは、例えば、ネットワークを介して公開され、署名装置200や検証装置300が取得可能な状態にされる。次に、図10に基づき、鍵生成装置100が実行するKeyGenアルゴリズムの処理について説明する。S201:情報入力ステップ情報入力部130は、入力装置により、属性の集合Γ:={t,x→t:=xt,ii=1,...,nt|1≦t≦d}を入力する。tは、1以上d以下の全ての整数ではなく、1以上d以下の少なくとも一部の整数であってもよい。S202:乱数生成ステップ乱数生成部141は、処理装置により、乱数δと、乱数φ0,φt,ι,φd1,1,ι,φd1,2,ιt=1,...,d;ι=1,...,wtとを数136に示すように生成する。S203:鍵要素0生成ステップ鍵要素0生成部142は、処理装置により、署名鍵skΓの要素である鍵要素k0を数137に示すように生成する。なお、上述したように、数113に示す基底Bと基底Bとに対して、数114である。したがって、数137は、以下のように、基底B0の基底ベクトルの係数が設定されることを意味する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として乱数δが設定される。基底ベクトル11,...,1u0の係数として0が設定される。基底ベクトル1u01,...,1u0w0の係数として乱数φ0,1,...,φ0,woここで、w0はw0のことであるが設定される。基底ベクトル1u0w01,...,1u0w0z0の係数として0が設定される。S204:鍵要素t生成ステップ鍵要素t生成部143は、処理装置により、属性の集合Γに含まれるt,x→tの各整数tについて、署名鍵skΓの要素である鍵要素ktを数138に示すように生成する。つまり、数138は、数137と同様に、以下のように、基底Btの基底ベクトルの係数が設定されることを意味する。なお、ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。基底ベクトル1,...,ntの係数としてδxt,1,...,δxt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数として乱数φt,1,...,φt,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。S205:鍵要素d1生成ステップ鍵要素d1生成部144は、処理装置により、署名鍵skΓの要素である鍵要素kd1,1と鍵要素kd1,2とを数139に示すように生成する。つまり、数139は、数137と同様に、以下のように、基底Bd1の基底ベクトルの係数が設定されることを意味する。なお、ここでは、表記を簡略化して、基底ベクトルbd1,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbd1,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbd1,1,...,bd1,3を意味する。まず、鍵要素kd1,1については、基底ベクトル1の係数として乱数δが設定される。基底ベクトル2の係数として0が設定される。基底ベクトル21,...,2ud1の係数として0が設定される。基底ベクトル2ud11,...,2ud1wd1の係数として乱数φd1,1,1,...,φd1,1,wd1ここで、wd1はwd1のことであるが設定される。基底ベクトル2ud1wd11,...,2ud1wd1zd1の係数として0が設定される。また、鍵要素kd1,2については、基底ベクトル1の係数として0が設定される。基底ベクトル2の係数として乱数δが設定される。基底ベクトル21,...,2ud1の係数として0が設定される。基底ベクトル2ud11,...,2ud1wd1の係数として乱数φd1,2,1,...,φd1,2,wd1ここで、wd1はwd1のことであるが設定される。基底ベクトル2ud1wd11,...,2ud1wd1zd1の係数として0が設定される。S206:鍵配布ステップ鍵配布部150は、属性の集合Γと、鍵要素k0と、鍵要素kttは属性の集合Γに含まれるt,x→tにおけるtと、鍵要素kd1,1及び鍵要素kd1,2とを要素とする署名鍵skΓを、例えば通信装置によりネットワークを介して秘密裡に署名装置200へ配布する。もちろん、署名鍵skΓは、他の方法により署名装置200へ配布されてもよい。つまり、S201からS205において、鍵生成装置100は数140に示すKeyGenアルゴリズムを実行して、署名鍵skΓを生成する。そして、S206で、鍵生成装置100は生成された署名鍵skΓを署名装置200へ配布する。署名装置200の機能と動作とについて説明する。図7に示すように、署名装置200は、署名鍵取得部210、情報入力部220第2情報入力部、スパンプログラム計算部230、補完係数計算部240、署名データ生成部250、署名データ送信部260署名データ出力部を備える。また、情報入力部220は、述語情報入力部221、メッセージ入力部222を備える。また、署名データ生成部250は、乱数生成部251、署名要素0生成部252、署名要素i生成部253、署名要素L1生成部254を備える。図11に基づき、署名装置200が実行するSigアルゴリズムの処理について説明する。S301:署名鍵取得ステップ署名鍵取得部210は、例えば、通信装置によりネットワークを介して、鍵生成装置100が生成した署名鍵skΓを取得する。また、署名鍵取得部210は、鍵生成装置100が生成した公開パラメータpkを取得する。S302:情報入力ステップ述語情報入力部221は、入力装置により、アクセスストラクチャS:=M,ρを入力する。なお、行列Mは、L行×r列の行列である。L,rは、1以上の整数である。また、メッセージ入力部222は、入力装置により、署名を付すメッセージmを入力する。なお、アクセスストラクチャSの行列Mの設定については、実現したいシステムの条件に応じて設定されるものである。S303:スパンプログラム計算ステップスパンプログラム計算部230は、処理装置により、S302で入力したアクセスストラクチャSが、S301で取得した署名鍵skΓに含まれる属性の集合Γを受理するか否かを判定する。なお、アクセスストラクチャが属性の集合を受理するか否かの判定方法は、第3.関数型暗号を実現するための概念で説明した通りである。スパンプログラム計算部230は、アクセスストラクチャSが属性の集合Γを受理する場合S303で受理、処理をS304へ進める。一方、アクセスストラクチャSが属性の集合Γを拒絶する場合S303で拒絶、処理を終了する。S304:補完係数計算ステップ補完係数計算部430は、処理装置により、数141となるIと、Iに含まれる各整数iについて定数補完係数αiとを計算する。なお、Miとは、行列Mのi行目のことである。S305:乱数生成ステップ乱数生成部251は、処理装置により、乱数ξと、乱数βii=1,...,Lとを数142に示すように生成する。S306:署名要素0生成ステップ署名要素0生成部252は、処理装置により、署名データσの要素である署名要素s0を数143に示すように生成する。ここで、r0は、数144数110から数112及びこれらの数式の説明を参照である。S307:署名要素i生成ステップ署名要素i生成部253は、処理装置により、i=1,...,Lの各整数iについて、署名データσの要素である署名要素siを数145に示すように生成する。ここで、riは、数146数110から数112及びこれらの数式の説明を参照である。また、γiとy→i:=yi,i’i’=1,...,ntとは、数147である。S308:署名要素L1生成ステップ署名要素L1生成部254は、処理装置により、署名データσの要素である署名要素sL1を数148に示すように生成する。ここで、rL1は、数149数110から数112及びこれらの数式の説明を参照である。S309:データ送信ステップ署名データ送信部260は、署名要素s0と、署名要素sii=1,...,Lと、署名要素sL1と、メッセージmと、アクセスストラクチャS:=M,ρとを含む署名データσを、例えば通信装置によりネットワークを介して検証装置300へ送信する。もちろん、署名データσは、他の方法により検証装置300へ送信されてもよい。つまり、S301からS308において、署名装置200は数150に示すSigアルゴリズムを実行して、署名データσを生成する。そして、S309で、署名装置200は生成された署名データσを検証装置300へ配布する。検証装置300の機能と動作とについて説明する。図8に示すように、検証装置300は、公開パラメータ取得部310、データ受信部320、検証鍵生成部330、ペアリング演算部340を備える。また、検証鍵生成部330は、乱数生成部331、fベクトル生成部332、sベクトル生成部333、検証要素0生成部334、検証要素i生成部335、検証要素L1生成部336を備える。図12に基づき、検証装置300が実行するVerアルゴリズムの処理について説明する。S401:公開パラメータ取得ステップ公開パラメータ取得部310は、例えば、通信装置によりネットワークを介して、鍵生成装置100が生成した公開パラメータpkを取得する。S402:署名データ受信ステップデータ受信部320は、例えば、通信装置によりネットワークを介して、署名装置200が送信した署名データσを受信する。S403:fベクトル生成ステップfベクトル生成部332は、処理装置により、r個の要素を有するベクトルf→を数151に示すようにランダムに生成する。S404:sベクトル生成ステップsベクトル生成部333は、処理装置により、S402で受信した署名データσに含まれるアクセスストラクチャSのL行×r列の行列Mと、S403で生成したr個の要素を有するベクトルf→とに基づき、ベクトルs→Tを数152に示すように生成する。また、sベクトル生成部333は、処理装置により、S403で生成したベクトルf→に基づき、値s0を数153に示すように生成する。なお、1→は、全ての要素が値1のベクトルである。S405:乱数生成ステップ乱数生成部331は、処理装置により、i=1,...,z0の各整数iについて乱数η0,iと、i=1,...,zd1の各整数iについて乱数ηL1,iと、乱数θL1と、乱数sL1とを数154に示すように生成する。S406:検証要素0生成ステップ検証要素0生成部334は、処理装置により、検証鍵の要素である検証要素c0を数155に示すように生成する。なお、上述したように、数113に示す基底Bと基底Bとに対して、数114である。したがって、数155は、以下のように、基底B0の基底ベクトルの係数が設定されることを意味する。こでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-s0-sL1が設定される。基底ベクトル11,...,1u0w0の係数として0が設定される。基底ベクトル1u0w01,...,1u0w0z0の係数として乱数η0,1,...,η0,z0ここで、z0はz0のことであるが設定される。S407:検証要素i生成ステップ検証要素i生成部335は、処理装置により、i=1,...,Lの各整数iについて、検証鍵の要素である検証要素ciを数156に示すように生成する。つまり、数156は、数155と同様に、以下のように、基底Btの基底ベクトルの係数が設定されることを意味する。なお、ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。ρiが肯定形の組t,v→iである場合には、基底ベクトル1の係数としてsiθivi,1が設定される。基底ベクトル2,...,ntの係数としてθivi,2,...,θivi,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutwtの係数として0が設定される。基底ベクトルntutwt1,...,ntutwtztの係数としてηi,1,...,ηi,ztここで、ztはztのことであるが設定される。一方、ρiが否定形の組¬t,v→iである場合には、基底ベクトル1,...,ntの係数としてsivi,1,...,θivi,ntここで、ntはntのことであるが設定される。基底ベクトル2の係数として-siが設定される。基底ベクトルnt1,...,ntutwtの係数として0が設定される。基底ベクトルntutwt1,...,ntutwtztの係数としてηi,1,...,ηi,ztここで、ztはztのことであるが設定される。なお、θi及びηi,i’i’=1,...,ztは乱数生成部233によって生成される一様乱数である。S408:署名要素L1生成ステップ検証要素L1生成部336は、処理装置により、検証鍵の要素である検証要素cL1を数157に示すように生成する。つまり、数157は、数155と同様に、以下のように、基底Bd1の基底ベクトルの係数が設定されることを意味する。なお、ここでは、表記を簡略化して、基底ベクトルbd1,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbd1,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbd1,1,...,bd1,3を意味する。基底ベクトル1の係数としてsL1-θL1Hhkλ,Dm||Sが設定される。基底ベクトル2の係数としてθL1が設定される。基底ベクトル21,...,2ud1wd1の係数として0が設定される。基底ベクトル2ud1wd11,...,2ud1wd1zd1の係数として乱数ηL1,1,...,ηL1,zd1ここで、zd1はzd1のことであるが設定される。S409:第1ペアリング演算ステップペアリング演算部340は、処理装置により、ペアリング演算eb0,1,s0を計算する。ペアリング演算eb0,1,s0を計算した結果が値1であれば、ペアリング演算部340は、署名の検証に失敗したことを示す値0を出力して、処理を終了する。一方、ペアリング演算eb0,1,s0を計算した結果が値1でなければ、ペアリング演算部340は、処理をS410へ進める。S410:第2ペアリング演算ステップペアリング演算部340は、処理装置により、数158に示すペアリング演算を計算する。数158に示すペアリング演算を計算した結果が値1であれば、ペアリング演算部340は、署名の検証に成功したことを示す値1を出力する。一方、その他の値であれば、ペアリング演算部340は、署名の検証に失敗したことを示す値0を出力する。なお、数159に示すように、数158を計算することにより、署名データσが正当なものであれば、値1が得られる。つまり、S401からS410において、検証装置300は、数160に示すVerアルゴリズムを実行して、署名データσを検証する。以上のように、実施の形態1に係る署名処理システム10は、スパンプログラムと内積述語と秘密分散とを用いて構成したアクセスストラクチャSを用いて、属性ベース署名方式を実現する。特に、実施の形態1に係る署名処理システム10は、ノンモノトーンスパンプログラムを用いるため、ノンモノトーン述語を伴う属性ベース署名方式を実現する。実施の形態1に係る署名処理システム10が実現する属性ベース署名方式は、安全性が高く、プライバシー要件を満たしている。なお、安全性が高いとは、署名を他人に偽造される可能性が低いということである。なお、S409でペアリング演算eb0,1,s0を行うのは、署名データσが、秘密であるマスター鍵skである基底ベクトルb0,1を用いることなく生成された署名データでないことを確認するためである。ペアリング演算eb0,1,s0は、署名要素s0に基底ベクトルb0,1が含まれているか、つまり基底ベクトルb0,1の係数として0以外の値が設定されているかを確認する演算である。ペアリング演算eb0,1,s0=1であれば、署名要素s0では基底ベクトルb0,1の係数として0が設定されており、署名データσは、基底ベクトルb0,1を用いることなく生成された署名データであるということになる。したがって、この場合、署名データσは不正なものであると認められる。なお、上記説明において、ut、wt、ztt=0,...,d1の次元は、安全性を高めるために設けた次元である。したがって、安全性が低くなってしまうが、ut、wt、ztt=0,...,d1をそれぞれ0として、ut、wt、ztt=0,...,d1の次元を設けなくてもよい。また、上記説明では、S101でNtにntutwtztを設定した。しかし、ntutwtztをntntnt1として、Ntに3nt1を設定してもよい。ここで、n0は1であり、ntt=1,...,d1は2である。この場合、数135に示すSetupアルゴリズムは、数161のように書き換えられる。なお、Gobは数162のように書き換えられる。また、数140に示すKeyGenアルゴリズムは、数163のように書き換えられる。また、数150に示すSigアルゴリズムは、数164のように書き換えられる。また、数159に示すVerアルゴリズムは、数165のように書き換えられる。また、Setupアルゴリズムは、署名処理システム10のセットアップ時に一度実行すればよく、署名鍵を生成する度に実行する必要はない。また、上記説明では、SetupアルゴリズムとKeyGenアルゴリズムとを鍵生成装置100が実行するとしたが、SetupアルゴリズムとKeyGenアルゴリズムとをそれぞれ異なる装置が実行するとしてもよい。実施の形態2.この実施の形態では、分散多管理者属性ベース署名方式について説明する。第1に、分散多管理者DecentralizedMulti-Authorityという概念について説明する。第2に、この実施の形態に係る分散多管理者属性ベース署名方式を説明する。まず、分散多管理者属性ベース署名方式の基本構成について説明する。次に、分散多管理者属性ベース署名方式を実現する署名処理システム10の基本構成について説明する。そして、この実施の形態に係る分散多管理者属性ベース署名方式及び署名処理システム10について詳細に説明する。<第1.分散多管理者という概念>まず、多管理者について説明する。多管理者とは、署名鍵を生成する管理者が複数存在するという意味である。一般的な署名処理システムでは、システム全体のセキュリティはある1つの機関管理者に依存している。例えば、実施の形態1で説明した署名処理システム10であれば、システム全体のセキュリティは、マスター鍵skを生成する鍵生成装置100に依存している。鍵生成装置100のセキュリティが破られたり、マスター鍵skが漏洩した場合、署名処理システム10は全体が機能しなくなる。しかし、多管理者とすることで、一部の管理者のセキュリティが破られたり、一部の管理者の秘密鍵マスター鍵が漏洩した場合であっても、署名処理システムの一部だけが機能しなくなるだけであり、他の部分については正常に機能する状態とすることができる。図13は、多管理者の説明図である。図13では、役所が、住所、電話番号、年齢等の属性について管理する。また、警察が、運転免許の種別等の属性について管理する。また、会社Aが、会社Aにおける役職、会社Aにおける所属等の属性について管理する。そして、役所が管理する属性を示すための署名鍵1は役所が発行し、警察が管理する属性を示すための署名鍵2は警察が発行し、会社Aが管理する属性を示すための署名鍵3は会社Aが発行する。署名をする署名者は、役所、警察、会社A等の各管理者が発行した署名鍵1,2,3を合わせた署名鍵用い、署名データを生成する。つまり、署名者から見た場合、各管理者から発行された署名鍵を合わせたものが、自分に発行された1つの署名鍵となる。例えば、会社Aのマスター鍵が漏洩した場合、署名処理システムは、会社Aの属性に関しては機能しなくなるが、他の管理者が管理する属性に関しては機能する。つまり、署名データの検証ができた場合、会社Aが管理する属性については信頼できないが、他の属性については信頼することができる。また、図13の例からも分かるように、属性ベース署名では、複数の管理者が存在し、各管理者が属性におけるあるカテゴリー部分空間又は定義域を管理し、そのカテゴリーにおけるユーザの属性についての署名鍵の一片を発行することが自然である。次に、分散Decentralizedについて説明する。分散とは、どの機関も管理者となることができ、他の機関とやりとりすることなく、署名鍵の一片を発行することができ、各ユーザが他の機関とやりとりすることなく、管理者から署名鍵の一片を取得できることである。例えば、中央管理者がいる場合、分散とは言えない。中央管理者とは、他の管理者よりも上位の管理者である。中央管理者のセキュリティが破られた場合、全ての管理者のセキュリティが破られてしまう。<第2.分散多管理者属性ベース署名方式の構成><第2-1.分散多管理者属性ベース署名方式の基本構成>分散多管理者属性ベース署名方式は、GSetup、ASetup、AttrGen、Sig、Verの4つのアルゴリズムを備える。GSetupGSetupアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータgparamを出力する確率的アルゴリズムである。ASetupASetupアルゴリズムは、公開パラメータgparamと、管理者の識別情報tとを入力として、管理者秘密鍵asktと、管理者公開パラメータapktとを出力する確率的アルゴリズムである。AttrGenAttrGenアルゴリズムは、公開パラメータgparamと、管理者の識別情報tと、管理者秘密鍵asktと、ユーザの識別情報gidと、属性x→t:=xt,ii=1,...,nt∈Fqとを入力として、署名鍵uskgid,t,xtを出力する確率的アルゴリズムである。SigSigアルゴリズムは、公開パラメータgparamと、署名鍵uskgid,t,xtと、メッセージmと、アクセスストラクチャS:=M,ρとを入力として、署名s→とメッセージmとアクセスストラクチャSとを含む署名データσを出力する確率的アルゴリズムである。VerVerアルゴリズムは、署名データσと、公開パラメータgparamと、管理者公開パラメータapktとを入力として、ブール値1受理又は0拒絶を出力するアルゴリズムである。<第2-2.署名処理システム10>上述した分散多管理者属性ベース署名方式のアルゴリズムを実行する署名処理システム10について説明する。図14は、分散多管理者属性ベース署名方式のアルゴリズムを実行する署名処理システム10の構成図である。署名処理システム10は、複数の鍵生成装置100、署名装置200、検証装置300を備える。いずれか1つの鍵生成装置100は、セキュリティパラメータλを入力としてGSetupアルゴリズムを実行して、公開パラメータgparamを生成する。そして、その鍵生成装置100は、生成した公開パラメータgparamを公開する。各鍵生成装置100は、公開パラメータgparamと、その鍵生成装置100に割り当てられた識別情報tとを入力としてASetupアルゴリズムを実行して、管理者秘密鍵asktと、管理者公開パラメータapktとを生成する。そして、各鍵生成装置100は、公開パラメータgparamと、その鍵生成装置100に割り当てられた識別情報tと、管理者秘密鍵asktと、ユーザの識別情報gidと、属性xt:=xt,ii=1,...,nt∈Fqとを入力としてAttrGenアルゴリズムを実行して、署名鍵uskgid,t,xtを生成して署名装置200へ秘密裡に配布する。署名装置200は、公開パラメータgparamと、署名鍵uskgid,t,xtと、メッセージmと、アクセスストラクチャS:=M,ρとを入力としてSigアルゴリズムを実行して、署名s→とメッセージmとアクセスストラクチャSとを含む署名データσを生成する。署名装置200は、生成した署名データσを検証装置300へ送信する。検証装置300は、署名データσと、公開パラメータgparamと、管理者公開パラメータapktとを入力としてVerアルゴリズムを実行して、ブール値1受理又は0拒絶を出力する。<第2-3.分散多管理者属性ベース署名方式及び署名処理システム10の詳細>図15から図22に基づき、分散多管理者属性ベース署名方式、及び、分散多管理者属性ベース署名方式を実行する署名処理システム10の機能と動作とについて説明する。図15は、各鍵生成装置100の機能を示す機能ブロック図である。図16は、署名装置200の機能を示す機能ブロック図である。図17は、検証装置300の機能を示す機能ブロック図である。図18から図20は、鍵生成装置100の動作を示すフローチャートである。なお、図18はGSetupアルゴリズムの処理を示すフローチャートであり、図19はASetupアルゴリズムの処理を示すフローチャートであり、図20はAttrGenアルゴリズムの処理を示すフローチャートである。図21は、署名装置200の動作を示すフローチャートであり、Sigアルゴリズムの処理を示すフローチャートである。図22は、検証装置300の動作を示すフローチャートであり、Verアルゴリズムの処理を示すフローチャートである。鍵生成装置100の機能と動作とについて説明する。図15に示すように、鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130第1情報入力部、署名鍵生成部140、鍵配布部150署名鍵送信部を備える。また、マスター鍵生成部110は、グローバルパラメータ生成部111、管理者秘密鍵生成部112を備える。署名鍵生成部140は、乱数生成部141、鍵要素生成部145を備える。まず、図18に基づき、鍵生成装置100が実行するGSetupアルゴリズムの処理について説明する。なお、上述したように、GSetupアルゴリズムは、複数の鍵生成装置100のうち1つの鍵生成装置100が実行すればよい。S501:セキュリティパラメータ入力ステップグローバルパラメータ生成部111は、入力装置により、セキュリティパラメータλ1λを入力する。S502:双線形ペアリング群生成ステップグローバルパラメータ生成部111は、処理装置により、S501で入力したセキュリティパラメータλ1λを入力としてアルゴリズムGbpgを実行して、ランダムに双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を生成する。S503:パラメータ生成ステップハッシュ関数H1とH2とを、数166に示すハッシュ関数とする。グローバルパラメータ生成部111は、処理装置により、数167に示すグローバルパラメータgparamの要素G0,G1,G2,G3,G4を生成する。また、グローバルパラメータ生成部111は、gt:=eG0,G1、g4:=eG0,G4とする。S504:パラメータ記憶ステップマスター鍵記憶部120は、S502で生成したparamGと、S503でグローバルパラメータ生成部111が設定したハッシュ関数H1,H2と、生成した要素G0,G1,G2,G3,G4と、設定した値gt,g4とを、グローバルパラメータgparamとして記憶装置に記憶する。つまり、S501からS503において、鍵生成装置100は数168に示すGSetupアルゴリズムを実行して、グローバルパラメータgparamを生成する。そして、S504で、鍵生成装置100は生成されたグローバルパラメータgparamを記憶装置に記憶する。なお、グローバルパラメータgparamは、例えば、ネットワークを介して公開され、他の鍵生成装置100や署名装置200や検証装置300が取得可能な状態にされる。次に、図19に基づき、鍵生成装置100が実行するASetupアルゴリズムの処理について説明する。なお、上述したように、ASetupアルゴリズムは、複数の鍵生成装置100全てが実行してもよいし、複数の鍵生成装置100のうち一部の鍵生成装置100だけが実行してもよい。S601:情報入力ステップ情報入力部130は、入力装置により、自己その鍵生成装置100に割り当てられた識別情報tを入力する。なお、各鍵生成装置100には、それぞれ異なる識別情報tが割り当てられている。また、情報入力部130は、例えば、通信装置によりネットワークを介して、グローバルパラメータgparamを取得する。なお、自己がグローバルパラメータgparamを生成した鍵生成装置100である場合には、グローバルパラメータgparamをマスター鍵記憶部120から読み出せばよい。S602:空間生成ステップ管理者秘密鍵生成部112は、処理装置により、セキュリティパラメータλ1λと、Nt=2nt2utwtztと、paramG:=q,G,GT,g,eの値とを入力としてアルゴリズムGdpvsを実行して、双対ペアリングベクトル空間のパラメータparamVt:=q,Vt,GT,At,eの値を生成する。なお、nt,ut,wt,ztは、1以上の整数である。S603:基底U生成ステップ管理者秘密鍵生成部112は、処理装置により、l=1,...,4の各整数lについて、基底Ulを数169に示すように生成する。S604:線形変換生成ステップ管理者秘密鍵生成部112は、処理装置により、ntutwtztと、Fqとを入力として、線形変換Xt:=χt,i,ji,jを数170に示すようにランダムに生成する。S605:基底B生成ステップ管理者秘密鍵生成部112は、処理装置により、基底Bt及び基底Btを数171に示すように生成する。また、管理者秘密鍵生成部112は、π,π’,μ∈Fqを、G2=πG1,G3=π’G1,G3=μG1となる値とする。すると、数172となる。S606:基底B^生成ステップ管理者秘密鍵生成部112は、処理装置により、基底Btの部分基底B^tと、基底Bの部分基底B^tとを数173に示すように生成する。S607:マスター鍵記憶ステップマスター鍵記憶部120は、S602で生成したパラメータparamVtと、S606で生成した部分基底B^t及び部分基底B^tとを管理者公開パラメータapktとして記憶装置に記憶する。また、マスター鍵記憶部120は、S604で生成した線形変換Xtを管理者秘密鍵asktとして記憶装置に記憶する。つまり、S601からS606において、鍵生成装置100は数174に示すASetupアルゴリズムを実行して、管理者公開パラメータapktと管理者秘密鍵asktとを生成する。そして、S607で、鍵生成装置100は生成された管理者公開パラメータapktと管理者秘密鍵asktとを記憶装置に記憶する。なお、管理者公開パラメータapktは、例えば、ネットワークを介して公開され、署名装置200や検証装置300が取得可能な状態にされる。次に、図20に基づき、鍵生成装置100が実行するAttrGenアルゴリズムの処理について説明する。なお、上述したように、AttrGenアルゴリズムは、複数の鍵生成装置100のうち、ASetupアルゴリズムを実行した鍵生成装置100が実行する。S701:情報入力ステップ情報入力部130は、入力装置により、自己その鍵生成装置100に割り当てられた識別情報tと、署名鍵を発行するユーザの識別情報gidと、属性情報x→t:=xt,ii=1,...,ntとを入力する。また、情報入力部130は、例えば、通信装置によりネットワークを介して、グローバルパラメータgparamを取得する。なお、自己がグローバルパラメータgparamを生成した鍵生成装置100である場合には、グローバルパラメータgparamをマスター鍵記憶部120から読み出せばよい。また、情報入力部130は、マスター鍵記憶部120から管理者秘密鍵asktを読み出す。S702:乱数生成ステップ乱数生成部141は、処理装置により、識別情報tとj=1,2の各整数jとについて、乱数φ→t,jを数175に示すように生成する。S703:鍵要素生成ステップ数176であるとする。鍵要素生成部145は、処理装置により、識別情報tとj=1,2の各整数jとについて、署名鍵uskgid,t,xtの要素である鍵要素kt,jを数177に示すように生成する。なお、上述したように、数113に示す基底Bと基底Bとに対して、数114である。したがって、数177は、以下のように、基底Btの基底ベクトルの係数が設定されることを意味する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。基底ベクトル1,...,ntの係数としてδj1xt,1,...,δj1xt,ntここで、ntはntのことであるが設定される。基底tクトルnt1,...,2ntの係数として-δjxt,1,...,-δjxt,ntここで、ntはntのことであるが設定される。基底ベクトル2nt1,...,2nt2utの係数として0が設定される。基底ベクトル2nt2ut1,...,2nt2utwtの係数として乱数φt,j、1,...,φt,j,wtここで、wtはwtのことであるが設定される。基底ベクトル2nt2utwt1,...,2nt2utwtztの係数として0が設定される。S704:鍵配布ステップ鍵配布部150は、ユーザの識別情報gidと、識別情報t及び属性情報x→tと、鍵要素kt,jとを要素とする署名鍵uskgid,t,xtを、例えば通信装置によりネットワークを介して秘密裡に署名装置200へ配布する。もちろん、署名鍵uskgid,t,xtは、他の方法により署名装置200へ配布されてもよい。つまり、S701からS703において、鍵生成装置100は数178に示すAttrGenアルゴリズムを実行して、署名鍵uskgid,t,xtを生成する。そして、S704で、鍵生成装置100は生成された署名鍵uskgid,t,xtを署名装置200へ配布する。署名装置200の機能と動作とについて説明する。図16に示すように、署名装置200は、署名鍵取得部210、情報入力部220第2情報入力部、スパンプログラム計算部230、補完係数計算部240、署名データ生成部250、署名データ送信部260署名データ出力部を備える。また、情報入力部220は、述語情報入力部221、メッセージ入力部222を備える。また、署名データ生成部250は、乱数生成部251、署名要素生成部255を備える。図21に基づき、署名装置200が実行するSigアルゴリズムの処理について説明する。S801:署名鍵取得ステップ署名鍵取得部210は、例えば、通信装置によりネットワークを介して、各鍵生成装置100が生成した署名鍵uskgid,t,xtを取得する。また、署名鍵取得部210は、鍵生成装置100が生成したグローバルパラメータgparamを取得する。S802:情報入力ステップ述語情報入力部221は、入力装置により、アクセスストラクチャS:=M,ρを入力する。なお、行列Mは、L行×r列の行列である。L,rは、1以上の整数である。また、メッセージ入力部222は、入力装置により、署名を付すメッセージmを入力する。なお、アクセスストラクチャSの行列Mの設定については、実現したいシステムの条件に応じて設定されるものである。S803:スパンプログラム計算ステップスパンプログラム計算部230は、処理装置により、S802で入力したアクセスストラクチャSが、S801で取得した署名鍵uskgid,t,xtに含まれる属性情報x→tの集合Γを受理するか否かを判定する。なお、アクセスストラクチャが属性の集合を受理するか否かの判定方法は、実施の形態1における第3.関数型暗号を実現するための概念で説明した通りである。スパンプログラム計算部230は、アクセスストラクチャSが属性の集合Γを受理する場合S803で受理、処理をS804へ進める。一方、アクセスストラクチャSが属性情報x→tの集合Γを拒絶する場合S803で拒絶、処理を終了する。S804:補完係数計算ステップ補完係数計算部430は、処理装置により、数179となるIと、Iに含まれる各整数iについて定数補完係数αiとを計算する。なお、Miとは、行列Mのi行目のことである。S805:乱数生成ステップ乱数生成部251は、処理装置により、乱数ξ1,ξ2と、乱数βi,βi’i=1,...,Lとを数180に示すように生成する。S806:署名要素生成ステップ署名要素生成部255は、処理装置により、i=1,...,Lの各整数iについて、署名データσの要素である署名要素siを数181に示すように生成する。ここで、riは、数182数110から数112及びこれらの数式の説明を参照である。また、γiとy→i:=yi,i’i’=1,...,ntとy’→i:=y’i,i’i’=1,...,ntとは、数183である。S807:データ送信ステップ署名データ送信部260は、署名要素sii=1,...,Lと、メッセージmと、アクセスストラクチャS:=M,ρと、g0:=g4ξ2ここで、ξ2はξ2であるとを含む署名データσを、例えば通信装置によりネットワークを介して検証装置300へ送信する。もちろん、署名データσは、他の方法により検証装置300へ送信されてもよい。つまり、S801からS806において、署名装置200は数184に示すSigアルゴリズムを実行して、署名データσを生成する。そして、S807で、署名装置200は生成された署名データσを検証装置300へ配布する。検証装置300の機能と動作とについて説明する。図17に示すように、検証装置300は、公開パラメータ取得部310、データ受信部320データ取得部、検証鍵生成部330、ペアリング演算部340を備える。また、検証鍵生成部330は、乱数生成部331、fベクトル生成部332、sベクトル生成部333、検証要素生成部337を備える。図22に基づき、検証装置300が実行するVerアルゴリズムの処理について説明する。S901:公開パラメータ取得ステップ公開パラメータ取得部310は、例えば、通信装置によりネットワークを介して、各鍵生成装置100が生成したグローバルパラメータgparamと、管理者公開パラメータapktとを取得する。S902:署名データ受信ステップデータ受信部320は、例えば、通信装置によりネットワークを介して、署名装置200が送信した署名データσを受信する。S903:fベクトル生成ステップfベクトル生成部332は、処理装置により、r個の要素を有するベクトルf→を数185に示すようにランダムに生成する。S904:sベクトル生成ステップsベクトル生成部333は、処理装置により、S902で受信した署名データσに含まれるアクセスストラクチャSのL行×r列の行列Mと、S903で生成したr個の要素を有するベクトルf→とに基づき、ベクトルs→Tを数186に示すように生成する。また、sベクトル生成部333は、処理装置により、S903で生成したベクトルf→に基づき、値s0を数187に示すように生成する。なお、1→は、全ての要素が値1のベクトルである。S905:f’ベクトル生成ステップfベクトル生成部332は、処理装置により、r個の要素を有するベクトルf→’を数188に示すようにランダムに生成する。S906:s’ベクトル生成ステップsベクトル生成部333は、処理装置により、L行×r列の行列Mと、r個の要素を有するベクトルf→’とに基づき、ベクトルs→’Tを数189に示すように生成する。S907:乱数生成ステップ乱数生成部331は、処理装置により、乱数σ→と値σ0とを数190に示すように生成する。S908:検証要素生成ステップ検証要素生成部337は、処理装置により、i=1,...,Lの各整数iについて、検証鍵の要素である検証要素ciを数191に示すように生成する。なお、上述したように、数113に示す基底Bと基底Bとに対して、数114である。したがって、数191は、以下のように、基底Btの基底ベクトルの係数が設定されることを意味する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。ρiが肯定形の組t,v→iである場合には、基底ベクトル1の係数としてsiθivi,1が設定される。基底ベクトル2,...,ntの係数としてθivi,2,...,θivi,ntここで、ntはntのことであるが設定される。基底ベクトルnt1の係数としてsi’θi’vi,1が設定される。基底ベクトルnt2,...,2ntの係数としてθi’vi,2,...,θi’vi,ntここで、ntはntのことであるが設定される。基底ベクトル2nt1の係数としてσi-θi’’H2m,Sが設定される。なお、H2m,Sとは、ハッシュ関数H2の入力として、メッセージmとアクセスストラクチャSとが与えられることを意味する。例えば、H2m||Sとしてもよい。基底ベクトル2nt2の係数としてθi’’が設定される。基底ベクトル2nt21,...,2nt2utwtの係数として0が設定される。基底ベクトル2nt2utwt1,...,2nt2utwtztの係数としてηi,1,...,ηi,ztここで、ztはztのことであるが設定される。一方、ρiが否定形の組¬t,v→iである場合には、基底ベクトル1,...,ntの係数としてsivi,1,...,sivi,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,2ntの係数としてsi’vi,1,...,si’vi,ntここで、ntはntのことであるが設定される。基底ベクトル2nt1の係数としてσi-θi’’H2m,Sが設定される。基底ベクトル2nt2の係数としてθi’’が設定される。基底ベクトル2nt21,...,2nt2utwtの係数として0が設定される。基底ベクトル2nt2utwt1,...,2nt2utwtztの係数としてηi,1,...,ηi,ztここで、ztはztのことであるが設定される。S909:ペアリング演算ステップペアリング演算部340は、処理装置により、数192に示すペアリング演算を計算する。数192に示すペアリング演算を計算した結果が値gTs0g0σ0ここでs0はs0であり、σ0はσ0であるであれば、ペアリング演算部340は、署名の検証に成功したことを示す値1を出力する。一方、その他の値であれば、ペアリング演算部340は、署名の検証に失敗したことを示す値0を出力する。なお、数193に示すように、数192を計算することにより、署名データσが正当なものであれば、値1が得られる。つまり、S901からS909において、検証装置300は、数194に示すVerアルゴリズムを実行して、署名データσを検証する。以上のように、実施の形態2に係る署名処理システム10は、複数の鍵生成装置100が署名鍵を生成する多管理者属性ベース署名方式を実現する。特に、署名処理システム10が実現する署名方式は、中央管理者がいない分散多管理者属性ベース署名方式である。なお、実施の形態2に係る署名処理システム10は、実施の形態1に係る署名処理システム10と同様に、ノンモノトーン述語を伴う属性ベース署名方式を実現する。実施の形態2に係る署名処理システム10が実現する属性ベース署名方式は、安全性が高く、プライバシー要件を満たしている。なお、上記説明において、ut、wt、ztt=1,...,dの次元は、安全性を高めるために設けた次元である。したがって、安全性が低くなってしまうが、ut、wt、ztt=1,...,dをそれぞれ0として、ut、wt、ztt=1,...,dの次元を設けなくてもよい。また、上記説明では、基底Bt及び基底Btの次元数を2nt2utwtztに設定した。しかし、2nt2utwtztを222641として、基底Bt及び基底Btの次元数を17としてもよい。この場合、数168に示すGSetupアルゴリズムは、数195のように書き換えられる。また、数174に示すASetupアルゴリズムは、数196のように書き換えられる。また、数178に示すAttrGenアルゴリズムは、数197のように書き換えられる。また、数184に示すSigアルゴリズムは、数198のように書き換えられる。また、数194に示すVerアルゴリズムは、数199のように書き換えられる。また、GSetupアルゴリズムは、署名処理システム10のセットアップ時にいずれかの鍵生成装置100が一度実行すればよく、署名鍵を生成する度に実行する必要はない。同様に、ASetupアルゴリズムは、署名処理システム10のセットアップ時に各鍵生成装置100が一度実行すればよく、署名鍵を生成する度に実行する必要はない。また、上記説明では、GSetupアルゴリズムとASetupアルゴリズムとKeyGenアルゴリズムとを鍵生成装置100が実行するとしたが、GSetupアルゴリズムとASetupアルゴリズムとKeyGenアルゴリズムとをそれぞれ異なる装置が実行するとしてもよい。実施の形態3.以上の実施の形態では、双対ベクトル空間において署名処理を実現する方法について説明した。この実施の形態では、双対加群において署名処理を実現する方法について説明する。つまり、以上の実施の形態では、素数位数qの巡回群において署名処理を実現した。しかし、合成数Mを用いて数200のように環Rを表した場合、環Rを係数とする加群においても、上記実施の形態で説明した署名処理を適用することができる。実施の形態1で説明した属性ベース署名方式を、環Rを係数とする加群において実現すると数201から数205のようになる。実施の形態2で説明した分散多管理者属性ベース署名方式を、環Rを係数とする加群において実現すると数206から数210のようになる。なお、安全性の証明の観点から、以上の実施の形態において、i=1,...,Lの各整数iについてのρiは、それぞれ異なる識別情報tについての肯定形の組t,v→i又は否定形の組¬t,v→iであると限定してもよい。言い替えると、ρi=t,v→i又はρi=¬t,v→iである場合に、関数ρ~を、ρ~i=tである{1,...,L}→{1,..,d}の写像であるとする。この場合、ρ~が単射であると限定してもよい。なお、ρiは、上述したアクセスストラクチャS:=M,ρiのρiである。また、上記説明では、スパンプログラムM^は、入力列δによって行列M^から得られる行列Mδの行を線形結合して1→が得られる場合に限り、入力列δを受理するとした。しかし、スパンプログラムM^は、1→ではなく、他のベクトルh→が得られる場合に限り、入力列δを受理するとしてもよい。この場合、KeyGenアルゴリズムにおいて、s0:=1→f→Tではなく、s0:=h→f→Tとすればよい。次に、実施の形態における署名処理システム10鍵生成装置100、署名装置200、検証装置300のハードウェア構成について説明する。図23は、鍵生成装置100、署名装置200、検証装置300のハードウェア構成の一例を示す図である。図23に示すように、鍵生成装置100、署名装置200、検証装置300は、プログラムを実行するCPU911CentralProcessingUnit、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいうを備えている。CPU911は、バス912を介してROM913、RAM914、LCD901LiquidCrystalDisplay、キーボード902K/B、通信ボード915、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置920固定ディスク装置の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置920は、所定の固定ディスクインタフェースを介して接続される。ROM913、磁気ディスク装置920は、不揮発性メモリの一例である。RAM914は、揮発性メモリの一例である。ROM913とRAM914と磁気ディスク装置920とは、記憶装置メモリの一例である。また、キーボード902、通信ボード915は、入力装置の一例である。また、通信ボード915は、通信装置の一例である。さらに、LCD901は、表示装置の一例である。磁気ディスク装置920又はROM913などには、オペレーティングシステム921OS、ウィンドウシステム922、プログラム群923、ファイル群924が記憶されている。プログラム群923のプログラムは、CPU911、オペレーティングシステム921、ウィンドウシステム922により実行される。プログラム群923には、上記の説明においてマスター鍵生成部110、マスター鍵記憶部120、情報入力部130、署名鍵生成部140、鍵配布部150、署名鍵取得部210、情報入力部220、スパンプログラム計算部230、補完係数計算部240、署名データ生成部250、署名データ送信部260、公開パラメータ取得部310、データ受信部320、検証鍵生成部330、ペアリング演算部340等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。ファイル群924には、上記の説明において公開パラメータ、マスター鍵、署名データσ、署名鍵、アクセスストラクチャS、属性情報、属性の集合Γ、メッセージm等の情報やデータや信号値や変数値やパラメータが、ファイルやデータベースの各項目として記憶される。ファイルやデータベースは、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出検索参照比較演算計算処理出力印刷表示などのCPU911の動作に用いられる。抽出検索参照比較演算計算処理出力印刷表示のCPU911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、その他光ディスク等の記録媒体やICチップに記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。また、上記の説明において~部として説明するものは、~回路、~装置、~機器、~手段、~機能であってもよく、また、~ステップ、~手順、~処理であってもよい。また、~装置として説明するものは、~回路、~機器、~手段、~機能であってもよく、また、~ステップ、~手順、~処理であってもよい。さらに、~処理として説明するものは~ステップであっても構わない。すなわち、~部として説明するものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子デバイス基板配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM913等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、上記で述べた~部としてコンピュータ等を機能させるものである。あるいは、上記で述べた~部の手順や方法をコンピュータ等に実行させるものである。"