"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と、前記第1情報入力部が入力した属性情報x→tと、所定の値δと、基底Btの基底ベクトルbt,ii=1,...,2ntとに基づき、数1に示すベクトルを含む鍵要素ktを生成する鍵要素生成部と、前記鍵要素生成部が生成した鍵要素ktと、前記属性情報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とを入力する第2情報入力部と、r個の要素を有するベクトルf→と、前記第2情報入力部が入力した行列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=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,i’i’=1,...,2ntを用いて、数2に示すベクトルを含む暗号要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,ii=1,...,2ntを用いて、数3に示すベクトルを含む暗号要素ciを生成する暗号要素ci生成部と、前記暗号要素ci生成部が生成したi=1,...,Lの各整数iについての暗号要素ciと、前記変数ρiと、前記行列Mとを含む暗号化データctSを前記復号装置へ送信する暗号化データ送信部とを備え、前記復号装置は、前記d個の鍵生成装置のうち、少なくとも1つ以上の鍵生成装置の前記復号鍵送信部が送信した復号鍵uskを受信する復号鍵受信部と、前記暗号化データ送信部が送信した暗号化データctSを受信するデータ受信部と、前記復号鍵受信部が受信した復号鍵uskに含まれる属性情報xt→と、前記データ受信部が受信した暗号化データctSに含まれる変数ρiとに基づき、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について、前記暗号化データctSに含まれる行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算部と、前記補完係数計算部が計算した集合Iと補完係数αiとに基づき、前記暗号化データctSに含まれる暗号要素ciと、前記復号鍵uskに含まれる鍵要素ktとについて、数4に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算部とを備えることを特徴とする暗号処理システム。前記暗号処理システムは、t=1,...,dの少なくとも1つ以上の整数tについて、少なくとも基底ベクトルbt,ii=1,...,2nt,...,2ntut,...,2ntutwt,...,2ntutwtztut,wt,ztは1以上の整数を有する基底Btと、少なくとも基底ベクトルbt,ii=1,...,2nt,...,2ntut,...,2ntutwt,...,2ntutwtztを有する基底Btとを用いて暗号処理を実行し、前記鍵生成装置では、前記鍵要素生成部は、前記整数tについて、前記属性情報x→tと、前記所定の値δと、i=1,...,wtの各整数iについての乱数φt,iとに基づき、数5に示す鍵要素ktを生成し、前記暗号化装置では、前記暗号要素ci生成部は、前記列ベクトルs→T及び前記列ベクトルs→’Tと、i=1,...,Lの各整数iについての前記所定の値θi,θi’と、i=1,...,Lの各整数iとi’=1,...,ztの各整数i’とについての乱数ηi,i’とに基づき、i=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、数6に示す暗号要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、数7に示す暗号要素ciを生成することを特徴とする請求項2に記載の暗号処理システム。前記暗号化装置は、さらに、所定の整数iについて前記基底Btの基底ベクトルbt,iと前記基底Btの基底ベクトルbt,iとについてペアリング演算をして計算される値gTと、前記s0とに基づき、メッセージmを暗号化した数8に示す暗号要素cd1を生成する暗号要素cd1生成部を備え、前記暗号化データ送信部は、前記暗号要素ciと、前記暗号要素cd1生成部が生成した暗号要素cd1とを含む暗号化データctを前記復号装置へ送信し、前記復号装置は、さらに、前記ペアリング演算部が計算した所定の情報Kで、前記暗号要素cd1を除して、前記メッセージmを計算するメッセージ計算部を備えることを特徴とする請求項1に記載の暗号処理システム。t=1,...,ddは1以上の整数の少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて暗号処理を実行する暗号処理システムにおいて、復号鍵uskを生成する鍵生成装置であり、t=1,...,dのうち予め定められた整数tについての属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数を入力する第1情報入力部と、前記整数tと、前記第1情報入力部が入力した属性情報x→tと、所定の値δと、基底Btの基底ベクトルbt,ii=1,...,2ntとに基づき、数9に示すベクトルを含む鍵要素ktを生成する鍵要素生成部と、前記鍵要素生成部が生成した鍵要素ktと、前記属性情報x→tとを含む復号鍵uskを復号装置へ送信する復号鍵送信部とを備えることを特徴とする鍵生成装置。t=1,...,ddは1以上の整数の少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて暗号処理を実行する暗号処理システムにおいて、暗号化データctSを生成する暗号化装置であり、i=1,...,LLは1以上の整数の各整数iについての変数ρiであって、識別情報tt=1,...,dのいずれかの整数と、属性情報v→i:=vi,i’i’=1,...,nt,ntは1以上の整数との肯定形の組t,v→i又は否定形の組¬t,v→iのいずれかである変数ρiと、L行r列rは1以上の整数の所定の行列Mとを入力する第2情報入力部と、r個の要素を有するベクトルf→と、前記第2情報入力部が入力した行列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=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,i’i’=1,...,2ntを用いて、数10に示すベクトルを含む暗号要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,ii=1,...,2ntを用いて、数11に示すベクトルを含む暗号要素ciを生成する暗号要素ci生成部と、前記暗号要素ci生成部が生成したi=1,...,Lの各整数iについての暗号要素ciと、前記変数ρiと、前記行列Mとを含む暗号化データctSを復号装置へ送信する暗号化データ送信部とを備えることを特徴とする暗号化装置。t=1,...,ddは1以上の整数の少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて暗号処理を実行する暗号処理システムにおいて、暗号化データctSを復号鍵uskで復号する復号装置であり、t=1,...,dのうち少なくとも一部の整数tについて、属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数と、数12に示すベクトルを含むように生成された鍵要素ktとを含む復号鍵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と、i=1,...,Lの各整数iについて数13に示すベクトルを含むように生成された暗号要素ciとを含む暗号化データctSを受信するデータ受信部と、前記復号鍵受信部が受信した復号鍵uskに含まれる属性情報xt→と、前記データ受信部が受信した暗号化データctSに含まれる変数ρiとに基づき、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について、前記暗号化データctSに含まれる行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算部と、前記補完係数計算部が計算した集合Iと補完係数αiとに基づき、前記暗号化データctSに含まれる暗号要素ciと、前記復号鍵uskに含まれる鍵要素ktとについて、数14に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算部とを備えることを特徴とする復号装置。t=1,...,ddは1以上の整数の少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて暗号処理を実行する暗号処理方法であり、複数の鍵生成装置のうち少なくとも1つ以上の鍵生成装置が、t=1,...,dのうち鍵生成装置毎に予め定められた整数tについての属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数を入力する第1情報入力工程と、前記1つ以上の鍵生成装置が、前記整数tと、前記第1情報入力工程で入力された属性情報x→tと、所定の値δと、基底Btの基底ベクトルbt,ii=1,...,2ntとに基づき、数15に示すベクトルを含む鍵要素ktを生成する鍵要素生成工程と、前記1つ以上の鍵生成装置が、前記鍵要素生成工程で生成された鍵要素ktと、前記属性情報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とを入力する第2情報入力工程と、前記暗号化装置が、r個の要素を有するベクトルf→と、前記第2情報入力工程で入力された行列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=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,i’i’=1,...,2ntを用いて、数16に示すベクトルを含む暗号要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,ii’=1,...,2ntを用いて、数17に示すベクトルを含む暗号要素ciを生成する暗号要素ci生成工程と、前記暗号化装置が、前記暗号要素ci生成工程で生成されたi=1,...,Lの各整数iについての暗号要素ciと、前記変数ρiと、前記行列Mとを含む暗号化データctSを前記復号装置へ送信する暗号化データ送信工程と、前記復号装置が、前記d個の鍵生成装置のうち、前記少なくとも1つ以上の鍵生成装置の前記復号鍵送信工程で送信された復号鍵uskを受信する復号鍵受信工程と、前記暗号化データ送信工程で送信された暗号化データctSを受信するデータ受信工程と、前記復号装置が、前記復号鍵受信工程で受信された復号鍵uskに含まれる属性情報xt→と、前記データ受信工程で受信された暗号化データctSに含まれる変数ρiとに基づき、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について、前記暗号化データctSに含まれる行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算工程と、前記復号装置が、前記補完係数計算工程で計算された集合Iと補完係数αiとに基づき、前記暗号化データctSに含まれる暗号要素ciと、前記復号鍵uskに含まれる鍵要素ktとについて、数18に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算工程とを備えることを特徴とする暗号処理方法。d個dは1以上の整数の鍵生成装置で動作させる鍵生成プログラムと、暗号化装置で動作させる暗号化プログラムと、復号装置で動作させる復号プログラムとを備え、t=1,...,dの少なくとも1つ以上の整数tについての基底Btと基底Btとを用いて暗号処理を実行する暗号処理プログラムであり、前記鍵生成プログラムは、t=1,...,dのうち鍵生成装置毎に予め定められた整数tについての属性情報x→t:=xt,ii=1,...,nt,ntは1以上の整数を入力する第1情報入力処理と、前記整数tと、前記第1情報入力処理で入力された属性情報x→tと、所定の値δと、基底Btの基底ベクトルbt,ii=1,...,2ntとに基づき、数19に示すベクトルを含む鍵要素ktを生成する鍵要素生成処理と、前記鍵要素生成処理で生成された鍵要素ktと、前記属性情報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とを入力する第2情報入力処理と、r個の要素を有するベクトルf→と、前記第2情報入力処理で入力された行列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=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,i’i’=1,...,2ntを用いて、数20に示すベクトルを含む暗号要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,ii=1,...,2ntを用いて、数21に示すベクトルを含む暗号要素ciを生成する暗号要素ci生成処理と、前記暗号要素ci生成処理で生成されたi=1,...,Lの各整数iについての暗号要素ciと、前記変数ρiと、前記行列Mとを含む暗号化データctSを前記復号装置へ送信する暗号化データ送信処理とをコンピュータに実行させ、前記復号プログラムは、前記復号鍵送信処理で送信された復号鍵uskを受信する復号鍵受信処理と、前記暗号化データ送信処理で送信された暗号化データctSを受信するデータ受信処理と、前記復号鍵受信処理で受信された復号鍵uskに含まれる属性情報xt→と、前記データ受信処理で受信された暗号化データctSに含まれる変数ρiとに基づき、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について、前記暗号化データctSに含まれる行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算処理と、前記補完係数計算処理で計算された集合Iと補完係数αiとに基づき、前記暗号化データctSに含まれる暗号要素ciと、前記復号鍵uskに含まれる鍵要素ktとについて、数22に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算処理とをコンピュータに実行させることを特徴とする暗号処理プログラム。関数型暗号には、システム全体のセキュリティが1つの機関に依存するという課題がある。この発明は、システム全体のセキュリティが1つの機関に依存することのない分散多管理者関数型暗号を提供することを目的とする。この発明に係る暗号処理システムは、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と、前記第1情報入力部が入力した属性情報x→tと、所定の値δと、基底Btの基底ベクトルbt,ii=1,...,2ntとに基づき、数1に示すベクトルを含む鍵要素ktを生成する鍵要素生成部と、前記鍵要素生成部が生成した鍵要素ktと、前記属性情報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とを入力する第2情報入力部と、r個の要素を有するベクトルf→と、前記第2情報入力部が入力した行列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=1,...,Lの各整数iについて、変数ρiが肯定形の組t,v→iである場合には、その組の識別情報tが示す基底Btの基底ベクトルbt,i’i’=1,...,2ntを用いて、数2に示すベクトルを含む暗号要素ciを生成し、変数ρiが否定形の組¬t,v→iである場合には、その組の識別情報tが示す基底ベクトルbt,ii=1,...,2ntを用いて、数3に示すベクトルを含む暗号要素ciを生成する暗号要素ci生成部と、前記暗号要素ci生成部が生成したi=1,...,Lの各整数iについての暗号要素ciと、前記変数ρiと、前記行列Mとを含む暗号化データctSを前記復号装置へ送信する暗号化データ送信部とを備え、前記復号装置は、前記d個の鍵生成装置のうち、少なくとも1つ以上の鍵生成装置の前記復号鍵送信部が送信した復号鍵uskを受信する復号鍵受信部と、前記暗号化データ送信部が送信した暗号化データctSを受信するデータ受信部と、前記復号鍵受信部が受信した復号鍵uskに含まれる属性情報xt→と、前記データ受信部が受信した暗号化データctSに含まれる変数ρiとに基づき、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について、前記暗号化データctSに含まれる行列Mのi行目の要素であるMiに基づき、αiMiを合計した場合に所定のベクトルh→となる補完係数αiを計算する補完係数計算部と、前記補完係数計算部が計算した集合Iと補完係数αiとに基づき、前記暗号化データctSに含まれる暗号要素ciと、前記復号鍵uskに含まれる鍵要素ktとについて、数4に示すペアリング演算を行い、前記所定の情報Kを計算するペアリング演算部とを備えることを特徴とする。この発明に係る暗号処理システムでは、複数の鍵生成装置それぞれが復号鍵の一片を生成する。したがって、一部の鍵生成装置のセキュリティが破られても、復号鍵の一片の機能が失われるだけであり、システム全体のセキュリティが破られることにはならない。以下、図に基づき、発明の実施の形態を説明する。以下の説明において、処理装置は後述する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の転置行列を表す。数110に示す基底Bと基底Bとに対して、数111である。e→t,jは、数112に示す正規基底ベクトルを示す。また、以下の説明において、ntが下付き又は上付きで示されている場合、このntはntを意味する。同様に、Vtが下付き又は上付きで示されている場合、このVtはVtを意味する。同様に、δi,jが上付きで示されている場合、このδi,jは、δi,jを意味する。また、ベクトルを意味する→が下付き文字又は上付き文字に付されている場合、この→は下付き文字又は上付き文字に上付きで付されていることを意味する。また、復号鍵uskgid,t,xtにおけるxtは、xtのことである。また、以下の説明において、暗号処理とは、鍵生成処理、暗号化処理、復号処理を含むものである。実施の形態1.この実施の形態では、分散多管理者関数型暗号を実現する基礎となる概念を説明した上で、分散多管理者関数型暗号の構成について説明する。第1に、分散多管理者関数型暗号について簡単に説明する。まず、関数型暗号について説明する。次に、分散多管理者について説明する。第2に、関数型暗号を実現するための空間である双対ペアリングベクトル空間DualPairingVectorSpaces,DPVSという豊かな数学的構造を有する空間を説明する。第3に、関数型暗号を実現するための概念を説明する。ここでは、スパンプログラムSpanProgram、属性ベクトルの内積とアクセスストラクチャ、秘密分散秘密共有について説明する。第4に、この実施の形態に係る分散多管理者関数型暗号を説明する。まず、分散多管理者関数型暗号の基本構成について説明する。次に、この分散多管理者関数型暗号を実現する暗号処理システム10の基本構成について説明する。そして、この実施の形態に係る分散多管理者関数型暗号及び暗号処理システム10について詳細に説明する。<第1.分散多管理者関数型暗号><第1-1.関数型暗号>関数型暗号は、公開鍵暗号の概念を発展させ、きめ細かくした暗号である。関数型暗号は、IDベース暗号Identity-BasedEncryption,IBE非特許文献3,4,6,14,17参照、秘匿ベクトル暗号Hidden-VectorEncryption非特許文献9参照、述語暗号PredicateEncryption非特許文献22、属性ベース暗号Attribute-BasedEncryption,ABE特許文献2,20,32-34を特別な場合として包含する暗号方式である。関数型暗号では、復号鍵skψ秘密鍵はパラメータψに関連付けられている。そして、メッセージmは、パラメータψとは異なるパラメータγを伴う公開鍵pkを用いて暗号文Encm,pk,γに暗号化される。関係Rψ,γが成立する場合に限り、復号鍵skψは暗号文Encm,pk,γを復号することができる。関数型暗号では、管理者Authorityと呼ばれる信頼された機関が必要である。管理者は、公開鍵pkとマスター秘密鍵mskとのペアを生成する。公開鍵pkはシステムパラメータとして配布され、マスター秘密鍵はユーザのパラメータψに関連付けられたユーザの復号鍵skψを生成するのに用いられる。IDベース暗号の場合、パラメータψは、ユーザのIDであり、関係Rは等号関係である。つまり、関係Rψ、γはψ=γの場合に限り成立する。一般的なアクセスストラクチャに対するCPCiphertext-Policy属性ベース暗号の場合、パラメータψはユーザの属性の組x1,...,xiであり、関係R,γは一般的なアクセスストラクチャである。より正確には、関係R,γはM^,v1,...,viによって表される。そして、属性の要素の要素毎の等号関係、つまり{xt=vt}t∈{1,...,i}がモノトーンスパンプログラムM^に入力され、関係Rψ,γはTx1=v1,...,Txi=viの新の値のベクトルがスパンプログラムM^に受理された場合に限り成立する。ここで、ψが真ならTψ:=1であり、ψが偽ならTψ:=0である。例えば、x=vならTx=v:=1であり、x≠vならTx=v:=0である。関数型暗号には多くのアプリケーションが存在する。しかし、関数型暗号の概念には、システム全体のセキュリティが1つの機関に依存するという大きな課題がある。言い換えると、管理者のセキュリティが破られたり、マスター秘密鍵が漏えいした場合、システム全体が機能しなくなってしまう。<第1-2.分散多管理者>まず、多管理者について説明する。多管理者とは、ユーザの復号鍵を生成する管理者が複数存在するという意味である。上述したように、通常の関数型暗号では、システム全体のセキュリティが1つの機関管理者に依存していた。しかし、多管理者とすることで、一部の管理者のセキュリティが破られたり、一部の管理者の秘密鍵マスター鍵が漏洩した場合であっても、システムの一部だけが機能しなくなるだけであり、他の部分については正常に機能する状態とすることができる。図1は、多管理者の説明図である。図1では、役所が、住所、電話番号、年齢等の属性について管理する。また、警察が、運転免許の種別等の属性について管理する。また、会社Aが、会社Aにおける役職、会社Aにおける所属等の属性について管理する。そして、役所が管理する属性に関連付けられた復号鍵1は役所が発行し、警察が管理する属性に関連付けられた復号鍵2は警察が発行し、会社Aが管理する属性に関連付けられた復号鍵3は会社Aが発行する。暗号文を復号する復号者は、役所、警察、会社A等の各管理者が発行した復号鍵1,2,3を合わせた復号鍵を用い、暗号文を復号する。つまり、復号者から見た場合、各管理者から発行された復号鍵を合わせたものが、自分に発行された1つの復号鍵となる。例えば、会社Aのマスター鍵が漏洩した場合、暗号処理システムは、会社Aの属性に関しては機能しなくなるが、他の管理者が管理する属性に関しては機能する。つまり、会社Aが管理する属性については、指定した属性以外の属性のユーザによって復号されてしまう虞があるが、他の属性については、指定した属性のユーザによってのみ復号可能である。また、図1の例からも分かるように、関数型暗号では、複数の管理者が存在し、各管理者が属性におけるあるカテゴリー部分空間又は定義域を管理し、そのカテゴリーにおけるユーザの属性についての復号鍵の一片を発行することが自然である。次に、分散Decentralizedについて説明する。分散とは、どの機関も管理者となることができ、他の機関とやりとりすることなく、復号鍵の一片を発行することができ、各ユーザが他の機関とやりとりすることなく、管理者から復号鍵の一片を取得できることである。例えば、中央管理者がいる場合、分散とは言えない。中央管理者とは、他の管理者よりも上位の管理者である。中央管理者のセキュリティが破られた場合、全ての管理者のセキュリティが破られてしまう。<第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である。以下の説明において、数113を、1λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を出力するアルゴリズムとする。次に、双対ペアリングベクトル空間について説明する。双対ペアリングベクトル空間q,V,GT,A,eは、対称双線形ペアリング群paramG:=q,G,GT,g,eの直積によって構成することができる。双対ペアリングベクトル空間q,V,GT,A,eは、素数q、数114に示すFq上のN次元ベクトル空間V、位数qの巡回群GT、空間Vの標準基底A:=a1,...,aNの組であり、以下の演算12を有する。ここで、aiは、数115に示す通りである。演算1:非退化双線形ペアリング空間Vにおけるペアリングは、数116によって定義される。これは、非退化双線形である。つまり、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:ディストーション写像数117に示す空間Vにおける線形変換φi,jは、数118を行うことができる。ここで、線形変換φi,jをディストーション写像と呼ぶ。以下の説明において、数119を、1λλ∈自然数、N∈自然数、双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を入力として、セキュリティパラメータがλであり、N次元の空間Vとする双対ペアリングベクトル空間のパラメータparamV:=q,V,GT,A,eの値を出力するアルゴリズムとする。なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。<第3.関数型暗号を実現するための概念><第3-1.スパンプログラム>図2は、行列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の行とからなる部分行列である。図3は、行列Mδの説明図である。なお、図3では、n=7,L=6,r=5としている。つまり、変数の集合は、{p1,...,p7}であり、行列Mは6行×5列の行列である。また、図3において、ラベルρは、ρ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番目の行である。つまり、図3では、写像γ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である行ベクトルである。例えば、図3の例であれば、行列Mの1,2,4行目からなる行列Mδの各行を線形結合して1→が得られる場合に限り、スパンプログラムM^は入力列δを受理する。つまり、α1M1α2M2α4M4=1→となるα1,α2,α4が存在する場合には、スパンプログラムM^は入力列δを受理する。ここで、ラベルρが正のリテラル{p1,...,pn}にのみ対応付けられている場合、スパンプログラムはモノトーンと呼ばれる。一方、ラベルρがリテラル{p1,...,pn,¬p1,...,¬pn}に対応付けられている場合、スパンプログラムはノンモノトーンと呼ばれる。ここでは、スパンプログラムはノンモノトーンとする。そして、ノンモノトーンスパンプログラムを用いて、アクセスストラクチャノンモノトーンアクセスストラクチャを構成する。アクセスストラクチャとは、簡単に言うと暗号へのアクセス制御を行うものである。つまり、暗号文を復号できるか否かの制御を行うものである。詳しくは後述するが、スパンプログラムがモノトーンではなく、ノンモノトーンであることにより、スパンプログラムを利用して構成する関数型暗号方式の利用範囲が広がる。なお、行列Mは、i=1,...,Lの各整数iについて、Mi≠0→であると仮定する。ここで、Miは、行列Mのi行目のことである。<第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,ρはΓを受理する。<第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を復元できるか否かを制御する秘密分散方式もある。図4は、s0の説明図である。図5は、s→Tの説明図である。行列MをL行×r列の行列とする。f→Tを数120に示す列ベクトルとする。数121に示すs0を共有される秘密情報とする。また、数122に示す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}が存在する。これは、図3の例で、α1M1α2M2α4M4=1→となるα1,α2,α4が存在する場合には、スパンプログラムM^は入力列δを受理すると説明したことからも明らかである。つまり、α1M1α2M2α4M4=1→となるα1,α2,α4が存在する場合には、スパンプログラムM^が入力列δを受理するのであれば、α1M1α2M2α4M4=1→となるα1,α2,α4が存在する。そして、数123である。なお、定数{αi}は、行列Mのサイズにおける多項式時間で計算可能である。この実施の形態及び以下の実施の形態に係る関数型暗号方式は、上述したように、スパンプログラムに内積述語と秘密分散方式とを適用してアクセスストラクチャを構成する。そのため、スパンプログラムにおける行列Mや、内積述語における属性情報x及び属性情報v述語情報を設計するにより、アクセス制御を自由に設計することができる。つまり、非常に高い自由度でアクセス制御の設計を行うことができる。なお、行列Mの設計は、秘密分散方式の閾値等の条件設計に相当する。例えば、属性ベース暗号方式は、この実施の形態関数型暗号方式におけるアクセスストラクチャにおいて、内積述語の設計をある条件に限定した場合に相当する。つまり、この実施の形態に係る関数型暗号方式におけるアクセスストラクチャに比べ、属性ベース暗号方式におけるアクセスストラクチャは、内積述語における属性情報x及び属性情報v述語情報の設計の自由度がない分、アクセス制御の設計の自由度が低い。なお、具体的には、属性ベース暗号方式は、属性情報{x→t}t∈{1,...,d}と{v→t}t∈{1,...,d}とを、等号関係に対する2次元ベクトル、例えばx→t:=1,xtとv→t:=vt,-1とに限定した場合に相当する。特に、この実施の形態及び以下の実施の形態に係る関数型暗号方式におけるアクセスストラクチャは、ノンモノトーンスパンプログラムを用いたノンモノトーンアクセスストラクチャを構成する。そのため、アクセス制御の設計の自由度がより高くなる。具体的には、ノンモノトーンスパンプログラムには、否定形のリテラル¬pを含むため、否定形の条件を設定できる。例えば、第1会社には、A部とB部とC部とD部との4つの部署があったとする。ここで、第1会社のB部以外の部署の属するユーザにのみアクセス可能復号可能というアクセス制御をしたいとする。この場合に、否定形の条件の設定ができないとすると、第1会社のA部とC部とD部とのいずれかに属することという条件を設定する必要がある。一方、否定形の条件の設定ができるとすると、第1会社の社員であって、B部以外に属することという条件を設定することができる。つまり、否定形の条件が設定できることで、自然な条件設定が可能となる。なお、ここでは部署の数が少ないが、部署の数が多い場合等は非常に有効であることが分かる。<第4.分散多管理者関数型暗号の基本構成><第4-1.分散多管理者関数型暗号の基本構成>分散多管理者関数型暗号の構成を簡単に説明する。分散多管理者関数型暗号は、GSetup、ASetup、AttrGen、Enc、Decの5つのアルゴリズムを備える。GSetupGSetupアルゴリズムは、セキュリティパラメータλを入力として、グローバル公開パラメータgparamを出力する確率的アルゴリズムである。GSetupアルゴリズムは、ある1つの機関により実行される。グローバル公開パラメータgparamは公開される。ASetupASetupアルゴリズムは、グローバル公開パラメータgparamと、管理者の識別情報tと、属性のフォーマットn→とを入力として、管理者公開鍵apktと、管理者秘密鍵asktとを出力する確率的アルゴリズムである。ASetupアルゴリズムは、1≦t≦dの少なくとも1つのtを識別情報として持つ管理者tによって実行される。管理者公開鍵apktは公開され、管理者秘密鍵asktは管理者tによって保持される。AttrGenAttrGenアルゴリズムは、グローバル公開パラメータgparamと、管理者の識別情報tと、管理者秘密鍵asktと、ユーザの識別情報gidと、属性x→t:=xt,ii=1,...,nt∈Fqとを入力として、復号鍵uskgid,t,xtを出力する確率的アルゴリズムである。AttrGenアルゴリズムは、識別情報gidが示すユーザに属性x→tに関連する復号鍵を管理者tが生成する場合に、管理者tによって実行される。管理者tは復号鍵uskgid,t,xtを識別情報gidが示すユーザに与える。EncEncアルゴリズムは、グローバル公開パラメータgparamと、管理者公開鍵apktと、メッセージm∈GTと、アクセスストラクチャSとを入力として、暗号化データctSを出力する確率的アルゴリズムである。Encアルゴリズムは、暗号化データctSを生成するユーザによって実行される。DecDecアルゴリズムは、グローバル公開パラメータgparamと、管理者公開鍵apktと、復号鍵uskgid,t,xtと、暗号化データctSとを入力として、メッセージm、又は、識別情報⊥を出力するアルゴリズムである。Decアルゴリズムは、暗号化データctSを復号するユーザによって実行される。<第4-2.暗号処理システム10>上述した分散多管理者関数型暗号のアルゴリズムを実行する暗号処理システム10について説明する。図6は、分散多管理者関数型暗号を実行する暗号処理システム10の構成図である。いずれか1つの鍵生成装置100は、セキュリティパラメータλを入力としてGSetupアルゴリズムを実行して、グローバル公開パラメータgparamを生成する。そして、その鍵生成装置100は、生成したグローバル公開パラメータgparamを公開する。各鍵生成装置100は、グローバル公開パラメータgparamと、その鍵生成装置100に割り当てられた識別情報tと、属性のフォーマットn→とを入力としてASetupアルゴリズムを実行して、管理者公開鍵apktと、管理者秘密鍵asktとを生成する。そして、各鍵生成装置100は、グローバル公開パラメータgparamと、その鍵生成装置100に割り当てられた識別情報tと、管理者秘密鍵asktと、ユーザの識別情報gidと、属性xt:=xt,ii=1,...,nt∈Fqとを入力としてAttrGenアルゴリズムを実行して、復号鍵uskgid,t,xtを生成して復号装置300へ秘密裡に配布する。暗号化装置200は、グローバル公開パラメータgparamと、管理者公開鍵apktと、メッセージm∈GTと、アクセスストラクチャSとを入力としてEncアルゴリズムを実行して、暗号化データctSを生成する。暗号化装置200は、生成した暗号化データctSを復号装置300へ送信する。復号装置300は、グローバル公開パラメータgparamと、管理者公開鍵apktと、復号鍵uskgid,t,xtと、暗号化データctSとを入力としてDecアルゴリズムを実行して、メッセージm、又は、識別情報⊥を出力する。<第4-3.分散多管理者関数型暗号及び暗号処理システム10の詳細>図7から図14に基づき、実施の形態1に係る分散多管理者関数型暗号、及び、分散多管理者関数型暗号を実行する暗号処理システム10の機能と動作とについて説明する。図7は、鍵生成装置100の機能を示す機能ブロック図である。図8は、暗号化装置200の機能を示す機能ブロック図である。図9は、復号装置300の機能を示す機能ブロック図である。図10から図12は、鍵生成装置100の動作を示すフローチャートである。なお、図10はGSetupアルゴリズムの処理を示すフローチャートであり、図11はASetupアルゴリズムの処理を示すフローチャートであり、図12はAttrGenアルゴリズムの処理を示すフローチャートである。図13は、暗号化装置200の動作を示すフローチャートであり、Encアルゴリズムの処理を示すフローチャートである。図14は、復号装置300の動作を示すフローチャートであり、Decアルゴリズムの処理を示すフローチャートである。鍵生成装置100の機能と動作とについて説明する。図7に示すように、鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130第1情報入力部、復号鍵生成部140、鍵配布部150復号鍵送信部を備える。また、マスター鍵生成部110は、グローバルパラメータ生成部111、管理者秘密鍵生成部112を備える。復号鍵生成部140は、乱数生成部141、鍵要素生成部142を備える。まず、図10に基づき、鍵生成装置100が実行するGSetupアルゴリズムの処理について説明する。なお、上述したように、GSetupアルゴリズムは、複数の鍵生成装置100のうち1つの鍵生成装置100が実行すればよい。S101:セキュリティパラメータ入力ステップグローバルパラメータ生成部111は、入力装置により、セキュリティパラメータλ1λを入力する。S102:双線形ペアリング群生成ステップグローバルパラメータ生成部111は、処理装置により、S101で入力したセキュリティパラメータλ1λを入力としてアルゴリズムGbpgを実行して、ランダムに双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を生成する。S103:パラメータ生成ステップハッシュ関数Hを、数124に示すハッシュ関数とする。グローバルパラメータ生成部111は、処理装置により、数125に示すグローバルパラメータgparamの要素G0,G1を生成する。また、グローバルパラメータ生成部111は、gT:=eG0,G1する。S104:パラメータ記憶ステップマスター鍵記憶部120は、S102で生成したparamGと、S103で設定したハッシュ関数Hと、要素G0,G1と、値gTとを、グローバルパラメータgparamとして記憶装置に記憶する。つまり、S101からS103において、鍵生成装置100は数126に示すGSetupアルゴリズムを実行して、グローバルパラメータgparamを生成する。そして、S104で、鍵生成装置100は生成されたグローバルパラメータgparamを記憶装置に記憶する。なお、グローバルパラメータgparamは、例えば、ネットワークを介して公開され、他の鍵生成装置100や暗号化装置200や復号装置300が取得可能な状態にされる。次に、図11に基づき、鍵生成装置100が実行するASetupアルゴリズムの処理について説明する。なお、上述したように、ASetupアルゴリズムは、複数の鍵生成装置100全てが実行してもよいし、複数の鍵生成装置100のうち一部の鍵生成装置100だけが実行してもよい。S201:情報入力ステップ情報入力部130は、入力装置により、自己その鍵生成装置100に割り当てられた識別情報tを入力する。なお、各鍵生成装置100には、それぞれ異なる識別情報tが割り当てられている。また、情報入力部130は、例えば、通信装置によりネットワークを介して、グローバルパラメータgparamを取得する。なお、自己がグローバルパラメータgparamを生成した鍵生成装置100である場合には、グローバルパラメータgparamをマスター鍵記憶部120から読み出せばよい。S202:空間生成ステップ管理者秘密鍵生成部112は、処理装置により、セキュリティパラメータλ1λと、Nt=2ntutwtztと、paramG:=q,G,GT,g,eの値とを入力としてアルゴリズムGdpvsを実行して、双対ペアリングベクトル空間のパラメータparamVt:=q,Vt,GT,At,eの値を生成する。なお、nt,ut,wt,ztは、1以上の整数である。S203:基底U生成ステップ管理者秘密鍵生成部112は、処理装置により、j=0,1の各整数jについて、基底Ujを数127に示すように生成する。S204:線形変換生成ステップ管理者秘密鍵生成部112は、処理装置により、Ntと、Fqとを入力として、線形変換Xt:=χt,i,ji,jを数128に示すようにランダムに生成する。なお、GLは、GeneralLinearの略である。つまり、GLは、一般線形群であり、行列式が0でない正方行列の集合であり、乗法に関し群である。また、χt,i,ji,jは、行列χt,i,jの添え字i,jに関する行列という意味であり、ここでは、i,j=1,...,Ntである。S205:基底B生成ステップ管理者秘密鍵生成部112は、処理装置により、基底Bt及び基底Btを数129に示すように生成する。S206:基底B^生成ステップ管理者秘密鍵生成部112は、処理装置により、基底Btの部分基底B^tと、基底Bの部分基底B^tとを数130に示すように生成する。S207:マスター鍵記憶ステップマスター鍵記憶部120は、S202で生成したパラメータparamVtと、S206で生成した部分基底B^tとを管理者公開鍵apktとして記憶装置に記憶する。また、マスター鍵記憶部120は、S204で生成した線形変換Xtを管理者秘密鍵asktとして記憶装置に記憶する。つまり、S201からS206において、鍵生成装置100は数131に示すASetupアルゴリズムを実行して、管理者公開鍵apktと管理者秘密鍵asktとを生成する。そして、S207で、鍵生成装置100は生成された管理者公開鍵apktと管理者秘密鍵asktとを記憶装置に記憶する。なお、管理者公開鍵apktは、例えば、ネットワークを介して公開され、暗号化装置200や復号装置300が取得可能な状態にされる。次に、図12に基づき、鍵生成装置100が実行するAttrGenアルゴリズムの処理について説明する。なお、上述したように、AttrGenアルゴリズムは、複数の鍵生成装置100のうち、ASetupアルゴリズムを実行した鍵生成装置100が実行する。S301:情報入力ステップ情報入力部130は、入力装置により、自己その鍵生成装置100に割り当てられた識別情報tと、復号鍵を発行するユーザの識別情報gidと、数132に示す属性情報x→t:=xt,ii=1,...,ntとを入力する。また、情報入力部130は、例えば、通信装置によりネットワークを介して、グローバルパラメータgparamを取得する。なお、自己がグローバルパラメータgparamを生成した鍵生成装置100である場合には、グローバルパラメータgparamをマスター鍵記憶部120から読み出せばよい。また、情報入力部130は、マスター鍵記憶部120から管理者秘密鍵asktを読み出す。S302:乱数生成ステップ乱数生成部141は、処理装置により、識別情報tについて、乱数φ→tを数133に示すように生成する。S303:鍵要素生成ステップ数134であるとする。鍵要素生成部142は、処理装置により、識別情報tについて、復号鍵uskgid,t,xtの要素である鍵要素ktを数135に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数135は、以下のように、基底Btの基底ベクトルの係数が設定されることを意味する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。基底ベクトル1,...,ntの係数としてδ1xt,1,...,δ1xt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,2ntの係数として-δxt,1,...,-δxt,ntここで、ntはntのことであるが設定される。基底ベクトル2nt1,...,2ntutの係数として0が設定される。基底ベクトル2ntut1,...,2ntutwtの係数として乱数φt、1,...,φt,wtここで、wtはwtのことであるが設定される。基底ベクトル2ntutwt1,...,2ntutwtztの係数として0が設定される。S304:鍵配布ステップ鍵配布部150は、ユーザの識別情報gidと、識別情報t及び属性情報x→tと、鍵要素ktとを要素とする復号鍵uskgid,t,xtを、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵uskgid,t,xtは、他の方法により復号装置300へ配布されてもよい。つまり、S301からS303において、鍵生成装置100は数136に示すAttrGenアルゴリズムを実行して、復号鍵uskgid,t,xtを生成する。そして、S304で、鍵生成装置100は生成された復号鍵uskgid,t,xtを復号装置300へ配布する。暗号化装置200の機能と動作とについて説明する。図8に示すように、暗号化装置200は、公開鍵取得部210、情報入力部220第2情報入力部、暗号化データ生成部230、暗号化データ送信部240を備える。また、情報入力部220は、属性情報入力部221、メッセージ入力部222を備える。また、暗号化データ生成部230は、乱数生成部231、fベクトル生成部232、sベクトル生成部233、暗号要素ci生成部234、暗号要素cd1生成部235を備える。図13に基づき、暗号化装置200が実行するEncアルゴリズムの処理について説明する。S401:公開鍵取得ステップ公開鍵取得部210は、例えば、通信装置によりネットワークを介して、各鍵生成装置100が生成した管理者公開鍵apktを取得する。また、公開鍵取得部210は、鍵生成装置100が生成したグローバルパラメータgparamを取得する。S402:情報入力ステップ属性情報入力部221は、入力装置により、アクセスストラクチャS:=M,ρを入力する。なお、行列Mは、L行×r列の行列である。L,rは、1以上の整数である。また、メッセージ入力部222は、入力装置により、暗号化するメッセージmを入力する。なお、アクセスストラクチャSの設定については、実現したいシステムの条件に応じて設定されるものである。S403:fベクトル生成ステップfベクトル生成部232は、処理装置により、r個の要素を有するベクトルf→を数137に示すようにランダムに生成する。S404:sベクトル生成ステップsベクトル生成部233は、処理装置により、S402で入力したアクセスストラクチャSのL行×r列の行列Mと、S403で生成したr個の要素を有するベクトルf→とに基づき、ベクトルs→Tを数138に示すように生成する。また、sベクトル生成部233は、処理装置により、S403で生成したベクトルf→に基づき、値s0を数139に示すように生成する。なお、1→は、全ての要素が値1のベクトルである。S405:f’ベクトル生成ステップfベクトル生成部232は、処理装置により、r個の要素を有するベクトルf→’を数140に示すようにs0=1→f→’という条件下でランダムに生成する。S406:s’ベクトル生成ステップsベクトル生成部233は、処理装置により、S402で入力したアクセスストラクチャSのL行×r列の行列Mと、r個の要素を有するベクトルf→’とに基づき、S405で生成したベクトルs→’Tを数141に示すように生成する。S407:乱数生成ステップ乱数生成部231は、処理装置により、i=1,...,Lの各整数iについて乱数η→i,θi,θ’iを数142に示すように生成する。S408:暗号要素ci生成ステップ暗号要素生成部234は、処理装置により、i=1,...,Lの各整数iについて、暗号化データctSの要素である暗号要素ciを数143に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数143は、以下のように、基底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,...,2ntutwtの係数として0が設定される。基底ベクトル2ntutwt1,...,2ntutwtztの係数としてη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,...,2ntutwtの係数として0が設定される。基底ベクトル2ntutwt1,...,2ntutwtztの係数としてηi,1,...,ηi,ztここで、ztはztのことであるが設定される。S409:暗号要素cd1生成ステップ暗号要素cd1生成部235は、処理装置により、暗号化データctSの要素である暗号要素cd1を数144に示すように生成する。S410:データ送信ステップ暗号化データ送信部240は、アクセスストラクチャS:=M,ρと、暗号要素cii=1,...,Lと、暗号要素cd1とを含む暗号化データctSを、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号化データctSは、他の方法により復号装置300へ送信されてもよい。つまり、S401からS409において、暗号化装置200は数145に示すEncアルゴリズムを実行して、暗号化データctSを生成する。そして、S410で、暗号化装置200は生成された暗号化データctSを復号装置300へ配布する。復号装置300の機能と動作とについて説明する。図9に示すように、復号装置300は、復号鍵受信部310復号鍵取得部、データ受信部320データ取得部、スパンプログラム計算部330、補完係数計算部340、ペアリング演算部350、メッセージ計算部360を備える。図14に基づき、Decアルゴリズムの処理について説明する。S501:復号鍵取得ステップ復号鍵受信部310は、例えば、通信装置によりネットワークを介して、鍵生成装置100から配布された復号鍵uskgid,t,xtを受信する。また、復号鍵受信部310は、鍵生成装置100が生成した管理者公開鍵apktを受信する。S502:データ受信ステップデータ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号化データctSを受信する。S503:スパンプログラム計算ステップスパンプログラム計算部330は、処理装置により、S502で受信した暗号化データctSに含まれるアクセスストラクチャSが、S501で取得した復号鍵uskgid,t,xtに含まれる属性情報x→tの集合Γを受理するか否かを判定する。アクセスストラクチャSがΓを受理するか否かの判定方法は、第3.関数型暗号を実現するための概念で説明した通りである。スパンプログラム計算部330は、アクセスストラクチャSがΓを受理する場合S503で受理、処理をS504へ進める。一方、アクセスストラクチャSがΓを拒絶する場合S503で拒絶、暗号化データctSを復号鍵uskgid,t,xtで復号できないとして処理を終了する。S504:補完係数計算ステップ補完係数計算部340は、処理装置により、数146となるIと、定数補完係数{αi}i∈Iとを計算する。S505:ペアリング演算ステップペアリング演算部350は、処理装置により、数147を計算して、セッション鍵K=gTs0ここで、s0はs0のことであるを生成する。なお、数148に示すように、数147を計算することにより鍵K=gTs0ここで、s0はs0のことであるが得られる。S506:メッセージ計算ステップメッセージ計算部360は、処理装置により、m’=cd1/Kを計算して、メッセージm’=mを生成する。なお、cd1は数144に示す通りgTs0mここで、s0はs0のことであるであり、KはgTs0ここで、s0はs0のことであるであるから、m’=cd1/Kを計算すればメッセージmが得られる。つまり、S501からS506において、復号装置300は、数149に示すDecアルゴリズムを実行して、メッセージm’=mを生成する。以上のように、実施の形態1に係る暗号処理システム10は、複数の鍵生成装置100が復号鍵を生成する多管理者関数型暗号方式を実現する。特に、暗号処理システム10が実現する署名方式は、中央管理者がいない分散多管理者関数型暗号方式である。なお、実施の形態1に係る暗号処理システム10は、ノンモノトーン述語を伴う関数型暗号方式を実現する。なお、上記説明において、ut、wt、ztt=1,...,dの次元は、安全性を高めるために設けた次元である。したがって、安全性が低くなってしまうが、ut、wt、ztt=1,...,dをそれぞれ0として、ut、wt、ztt=1,...,dの次元を設けなくてもよい。また、上記説明では、基底Bt及び基底Btの次元数をNt:=2ntutwtztに設定した。しかし、2ntutwtztを2nt3nt2nt1=7nt1として、基底Bt及び基底Btの次元数を7nt1としてもよい。この場合、数131に示すASetupアルゴリズムは、数150のように書き換えられる。また、数136に示すAttrGenアルゴリズムは、数151のように書き換えられる。また、数145に示すEncアルゴリズムは、数152のように書き換えられる。なお、GSetupアルゴリズムとDecアルゴリズムとには変更はない。また、GSetupアルゴリズムは、暗号処理システム10のセットアップ時にいずれかの鍵生成装置100が一度実行すればよく、復号鍵を生成する度に実行する必要はない。同様に、ASetupアルゴリズムは、暗号処理システム10のセットアップ時に各鍵生成装置100が一度実行すればよく、復号鍵を生成する度に実行する必要はない。また、上記説明では、GSetupアルゴリズムとASetupアルゴリズムとKeyGenアルゴリズムとを鍵生成装置100が実行するとしたが、GSetupアルゴリズムとASetupアルゴリズムとKeyGenアルゴリズムとをそれぞれ異なる装置が実行するとしてもよい。実施の形態2.実施の形態1では、双対ベクトル空間において暗号処理を実現する方法について説明した。この実施の形態では、双対加群において暗号処理を実現する方法について説明する。つまり、実施の形態1では、素数位数qの巡回群において暗号処理を実現した。しかし、合成数Mを用いて数153のように環Rを表した場合、環Rを係数とする加群においても、実施の形態1で説明した暗号処理を適用することができる。実施の形態1で説明した分散多管理者関数型暗号方式を、環Rを係数とする加群において実現すると数154から数158のようになる。なお、安全性の証明の観点から、以上の実施の形態において、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→が得られる場合に限り、入力列δを受理するとしてもよい。この場合、Encアルゴリズムにおいて、s0:=1→f→Tではなく、s0:=h→f→Tとし、s0:=1→f→’Tではなく、s0:=h→f→’Tとすればよい。次に、実施の形態における暗号処理システム10鍵生成装置100、暗号化装置200、復号装置300のハードウェア構成について説明する。図15は、鍵生成装置100、暗号化装置200、復号装置300のハードウェア構成の一例を示す図である。図15に示すように、鍵生成装置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、復号鍵受信部310、データ受信部320、スパンプログラム計算部330、補完係数計算部340、ペアリング演算部350、メッセージ計算部360等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。ファイル群924には、上記の説明においてグローバルパラメータgparam、管理者公開鍵apk、管理者秘密鍵ask、復号鍵uskgid,t,xt、暗号化データctS、アクセスストラクチャS、属性情報、メッセージm等の情報やデータや信号値や変数値やパラメータが、ファイルやデータベースの各項目として記憶される。ファイルやデータベースは、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出検索参照比較演算計算処理出力印刷表示などのCPU911の動作に用いられる。抽出検索参照比較演算計算処理出力印刷表示のCPU911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、その他光ディスク等の記録媒体やICチップに記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。また、上記の説明において~部として説明するものは、~回路、~装置、~機器、~手段、~機能であってもよく、また、~ステップ、~手順、~処理であってもよい。また、~装置として説明するものは、~回路、~機器、~手段、~機能であってもよく、また、~ステップ、~手順、~処理であってもよい。さらに、~処理として説明するものは~ステップであっても構わない。すなわち、~部として説明するものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子デバイス基板配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM913等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、上記で述べた~部としてコンピュータ等を機能させるものである。あるいは、上記で述べた~部の手順や方法をコンピュータ等に実行させるものである。"