"t=1,...,L1Lは1以上の整数の各整数tについての基底Btと基底Btとを用いて暗号処理を行う暗号処理システムであり、t=1,...,Lのうち少なくとも一部の整数tについての基底Btの基底ベクトルに属性情報x→tを埋め込んだベクトルを暗号化データctとして生成する暗号化装置と、t=1,...,Lの各整数tについての基底Btの基底ベクトルに述語情報v→tを埋め込んだベクトルを復号鍵skLとして、前記暗号化装置が生成した暗号化データctと前記復号鍵skLとについてペアリング演算を行い前記暗号化データctを復号する復号装置と、基底BL1の基底ベクトルに述語情報v→L1を埋め込んだベクトルと、前記復号装置が使用した復号鍵skLとに基づき、前記復号鍵skLの下位の復号鍵skL1を生成する鍵委譲装置とを備えることを特徴とする暗号処理システム。前記暗号処理システムは、さらに、前記復号鍵skLを生成する鍵生成装置を備え、前記鍵生成装置は、t=1,...,Lの各整数tについて述語情報v→t:=vt,ii=1,...,ntを入力する第1情報入力部と、前記第1情報入力部が入力した述語情報v→tと、所定の値Δと、t=1,...,Lの各整数tについての所定の値θdec,tと、sdec,0=Σt=1Lsdec,tであるようなt=0,...,Lの各整数tについての所定の値sdec,tとを用いて、基底B0の基底ベクトルb0,ppは所定の値の係数として-sdec,0を設定し、基底B0の基底ベクトルb0,qqは所定の値の係数として前記Δを設定し、t=1,...,Lの各整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数としてsdec,te→t,1θdec,tvt,ii=1,...,ntを設定した復号要素kL,decを生成する復号要素生成部と、前記復号要素生成部が生成した復号要素kL,decを含む復号鍵skLを前記復号装置へ送信する復号鍵送信部とを備え、前記暗号化装置は、t=1,...,Lの少なくとも一部の整数tについて属性情報x→t:=xt,ii=1,...,ntを入力する第2情報入力部と、前記第2情報入力部が入力した属性情報x→tと、所定の値ω,ζとを用いて、基底B0の基底ベクトルb0,pの係数として前記ωを設定し、基底B0の基底ベクトルb0,qの係数として前記ζを設定し、前記少なくとも一部の整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数としてωxt,ii=1,...,ntを設定した暗号化データc1を生成する暗号化データc1生成部と、前記暗号化データc1生成部が生成した暗号化データc1を含む暗号化データctを前記復号装置へ送信するデータ送信部とを備え、前記復号装置は、前記データ送信部が送信した暗号化データctに含まれる暗号化データc1と、前記復号鍵送信部が送信した前記復号鍵skLに含まれる復号要素kL,decとについて、ペアリング演算ec1,kL,decを行うペアリング演算部を備えることを特徴とする請求項1に記載の暗号処理システム。前記暗号化装置は、さらに、値gT=eb0,1,b0,1と、前記Δと、前記ζとから得られるgTΔζを、メッセージmに乗じた暗号化データc2を生成する暗号化データc2生成部を備え、前記データ送信部は、暗号化データc1と、前記暗号化データc2生成部が生成した暗号化データc2とを含む暗号化データctを前記復号装置へ送信し、前記ペアリング演算部は、前記ペアリング演算ec1,kL,decを行い、セッション鍵K:=gTΔζを計算し、前記復号装置は、さらに、前記ペアリング演算部が計算したセッション鍵Kで、前記暗号化データc2を除して、前記メッセージmを計算するメッセージ計算部を備えることを特徴とする請求項2に記載の暗号処理システム。前記鍵生成装置は、さらに、τ=L1である整数τと、ι=1,...,nτの各整数ιとについて委譲要素kL,del,τ,ιを生成する委譲要素生成部であって、t=1,...,Lの各整数tについての所定の値θdel,τ,ι,tと、所定の値ψと、sdel,τ,ι,0=Σt=1L1sdel,τ,ι,tであるようなt=0,...,L1の各整数tについての所定の値sdel,τ,ι,tとを用いて、基底B0の基底ベクトルb0,pの係数として-sdel,τ,ι,0を設定し、t=1,...,Lの各整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数としてsdel,τ,ι,te→t,1θdel,τ,ι,tvt,ii=1,...,ntを設定し、基底Bτの基底ベクトルbτ,ii=1,...,nτの係数としてsdel,τ,ι,L1e→τ,1ψe→τ,ιi=1,...,nτを設定して委譲要素kL,del,τ,ιを生成する委譲要素生成部を備え、前記復号鍵送信部は、前記復号要素kL,decと、前記委譲要素生成部が生成した委譲要素kL,del,τ,ιとを含む復号鍵skLを前記委譲装置へ送信し、前記鍵委譲装置は、述語情報v→L1:=vL1,ii=1,...,nL1を入力する第3情報入力部と、前記第3情報入力部が入力した述語情報v→L1と、前記復号鍵送信部が送信した復号鍵skLとを用いて、数1に示すベクトルを含む下位復号要素kL1,decを生成する下位復号要素生成部と、前記下位復号要素生成部が生成した下位復号要素kL1,decを含む下位の復号鍵skL1を下位の復号装置へ送信する委譲鍵送信部とを備えることを特徴とする請求項2に記載の暗号処理システム。前記暗号処理システムは、少なくとも基底ベクトルb0,ii=1,...,1n0,1n01,...,1n01u0,...,1n01u0w0,...,1n01u0w0z0n0,u0,w0,z0は1以上の整数を有する基底B0と、少なくとも基底ベクトルb0,ii=1,...,1n0,1n01,...,1n01u0,...,1n01u0w0,...,1n01u0w0z0n0,u0,w0,z0は1以上の整数を有する基底B0と、少なくとも基底ベクトルbt,ii=1,...,nt,...,ntut,...,ntutwt,...,ntutwtztut,wt,ztは1以上の整数を有する基底Btt=1,...,L1と、少なくとも基底ベクトルbt,ii=1,...,nt,...,ntut,...,ntutwt,...,ntutwtztを有する基底Btt=1,...,L1とを用いて暗号処理を行い、前記復号要素生成部は、t=0,...,Lの各整数tについての乱数η→dec,t:=ηdec,t,ii=1,...,wtに基づき、数2に示す復号要素をkL,decを生成し、前記暗号化データc1生成部は、t=0,...,Lの各整数tについての乱数φ→t:=φt,ii=1,...,ztに基づき、数3に示す暗号化データc1を生成することを特徴とする請求項2に記載の暗号処理システム。前記鍵生成装置は、さらに、j=1,...,2Lの各整数jについて、第1ランダム化要素kL,ran,jを生成するとともに、τ=L1,...,ddはL1以上の整数の各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、第2ランダム化要素kL,ran,τ,ιを生成するランダム化要素生成部であって、t=1,...,Lの各整数tについての所定の値θran,j,tと、sran,j,0=Σt=1Lsran,j,tであるようなt=0,...,Lについての所定の値sran,j,tと、t=0,...,Lの各整数tについての乱数η→ran,j,t:=ηran,j,t,ii=1,...,wtとに基づき、数4に示す第1ランダム化要素kL,ran,jを生成し、t=1,...,Lの各整数tについての所定の値θran,τ,ι,tと、sran,τ,ι,0=Σt=1L1sran,τ,ι,tであるようなt=0,...,L1についての所定の値sran,τ,ι,tと、t=0,...,L1の各整数tについての乱数η→ran,τ,ι,t:=ηran,τ,ι,t,ii=1,...,wtとに基づき、数5に示す第2ランダム化要素kL,ran,τ,ιを生成するランダム化要素生成部を備え、前記委譲要素生成部は、τ=L1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、t=0,...,L1の各整数tについての乱数η→del,τ,ι,t:=ηdel,τ,ι,t,ii=1,...,wtに基づき、数6に示す委譲要素kL,del,τ,ιを生成し、前記復号鍵送信部は、前記復号要素kL,decと、前記ランダム化要素生成部が生成した第1ランダム化要素kL,ran,j及び第2ランダム化要素kL,ran,τ,ιと、前記委譲要素生成部が生成した委譲要素kL,del,τ,ιとを含む復号鍵skLを前記委譲装置へ送信し、前記下位復号要素生成部は、前記述語情報v→L1と、前記復号鍵送信部が送信した復号鍵skLと、j=1,...,2Lの各整数jについての乱数αdec,jと、乱数σdecと、t=0,...,L1の各整数tとi=1,...,wtの各整数iとについての乱数ηdec,t,iとを用いて、数7に示す下位復号要素kL1,decを生成することを特徴とする請求項5に記載の暗号処理システム。前記委譲装置は、さらに、j’=1,...,2L1の各整数j’について、第1下位ランダム化要素kL1,ran,j’を生成するとともに、τ=L2,...,ddはL2以上の整数の各整数τと、各整数τに関してι=1,...,nτの各整数ιについて、第2下位ランダム化要素kL1,ran,τ,ιを生成する下位ランダム化要素生成部であって、前記述語情報v→L1と、前記復号鍵skLと、j=1,...,2Lの各整数jとj’=1,...,2L1の各整数j’とについての乱数αran,j’,jと、j’=1,...,2L1の各整数j’についての乱数σran,j’と、t=0,...,L1の各整数tとi=1,...,wtの各整数iとについての乱数ηran,j’,t,iとに基づき、数8に示す第1下位ランダム化要素kL1,ran,j’を生成し、前記述語情報v→L1と、前記復号鍵skLと、j=1,...,2Lの各整数jについての乱数αran,τ,ι,jと、乱数σran,τ,ιと、乱数φran,τ,ιと、t=0,...,L1,τの各整数tとi=1,...,wtの各整数iとについてのηran,τ,ι,t,iとに基づき、数9に示す第2下位ランダム化要素kL1,ran,τ,ιを生成する下位ランダム化要素生成部と、τ=L2,...,ddはL2以上の整数の各整数τと、各整数τに関してι=1,...,nτの各整数ιについて、下位委譲要素kL1,del,τ,ιを生成する下位委譲要素生成部であって、前記述語情報v→L1と、前記復号鍵skLと、j=1,...,2Lの各整数jについての乱数αdel,τ,ι,jと、乱数σdel,τ,ιと、乱数ψ’と、乱数φdel,τ,ιと、t=0,...,L1,τの各整数tとi=1,...,wtの各整数iとについてのηdel,τ,ι,t,iとに基づき、数10に示す下位委譲要素kL1,del,τ,ιを生成する下位委譲要素生成部とを備え、前記委譲鍵送信部は、前記下位復号要素生成部が生成した下位復号要素kL1,decと、前記下位ランダム化要素生成部が生成した第1下位ランダム化要素kL1,ran,j’及び第2下位ランダム化要素kL1,ran,τ,ιと、前記下位委譲要素生成部が生成した下位委譲要素kL1,del,τ,ιとを含む下位の復号鍵skL1を下位の委譲装置へ送信することを特徴とする請求項6に記載の暗号処理システム。前記第1情報入力部は、t=1,...,Lの各整数tについて述語情報v→t:=vt,ii=1,...,nt,ρt∈{0,1}を入力し、前記復号要素生成部は、基底ベクトルb0,pの係数として-sdec,0を設定し、基底ベクトルb0,qの係数として前記Δを設定し、t=1,...,Lの各整数tについての基底ベクトルbt,iの係数として、ρtが0の場合にはsdec,te→t,1θdec,tvt,ii=1,...,ntを設定し、ρtが1の場合にはsdec,tvt,ii=1,...,ntを設定した復号要素kL,decを生成することを特徴とする請求項2に記載の暗号処理システム。前記鍵生成装置は、さらに、τ=L1である整数τと、ι=1,...,nτの各整数ιとについて第1委譲要素kL,del,τ,ι,0と第2委譲要素kL,del,τ,ι,1とを生成する委譲要素生成部であって、t=1,...,Lの各整数tについての所定の値θdel,0,tと、所定の値ψと、sdel,0,0=Σt=1L1sdel,0,tであるようなt=0,...,L1についての所定の値sdel,0,tとを用いて、基底B0の基底ベクトルb0,pの係数として-sdel,0,0を設定し、t=1,...,Lの各整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数として、ρtが0の場合にはsdel,0,te→t,1θdel,0,tvt,ii=1,...,ntを設定し、ρtが1の場合にはsdel,0,tvt,ii=1,...,ntを設定し、基底Bτの基底ベクトルbτ,ii=1,...,nτの係数としてsdel,0,L1e→τ,1ψe→τ,ιi=1,...,nτを設定して第1委譲要素kL,del,τ,ι,0を生成し、t=1,...,Lの各整数tについての所定の値θdel,1,tと、sdel,1,0=Σt=1L1sdel,1,tであるようなt=0,...,L1についての所定の値sdel,1,tとを用いて、基底B0の基底ベクトルb0,pの係数として-sdel,1,0を設定し、t=1,...,Lの各整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数として、ρtが0の場合にはsdel,1,te→t,1θdel,1,tvt,ii=1,...,ntを設定し、ρtが1の場合にはsdel,1,tvt,ii=1,...,ntを設定し、基底Bτの基底ベクトルbτ,ii=1,...,nτの係数としてsdel,1,L1e→τ,1i=1,...,nτを設定して第2委譲要素kL,del,τ,ι,1を生成する委譲要素生成部を備え、前記復号鍵送信部は、前記復号要素kL,decと、前記委譲要素生成部が生成した第1委譲要素kL,del,τ,ι,0及び第2委譲要素kL,del,τ,ι,1とを含む復号鍵skLを前記委譲装置へ送信し、前記鍵委譲装置は、述語情報v→L1:=vL1,ii=1,...,nL1,ρL1∈{0,1}を入力する第3情報入力部と、前記第3情報入力部が入力した述語情報v→L1と、前記復号鍵送信部が送信した復号鍵skLとを用いて、数11に示すベクトルを含む下位復号要素kL1,decを生成する下位復号要素生成部を備えることを特徴とする請求項8に記載の暗号処理システム。前記暗号処理システムは、少なくとも基底ベクトルb0,ii=1,...,1n0,1n01,...,1n01u0,...,1n01u0w0,...,1n01u0w0z0n0,u0,w0,z0は1以上の整数を有する基底B0と、少なくとも基底ベクトルb0,ii=1,...,1n0,1n01,...,1n01u0,...,1n01u0w0,...,1n01u0w0z0n0,u0,w0,z0は1以上の整数を有する基底B0と、少なくとも基底ベクトルbt,ii=1,...,nt,...,ntut,...,ntutwt,...,ntutwtztut,wt,ztは1以上の整数を有する基底Btt=1,...,L1と、少なくとも基底ベクトルbt,ii=1,...,nt,...,ntut,...,ntutwt,...,ntutwtztを有する基底Btt=1,...,L1とを用いて暗号処理を行い、前記復号要素生成部は、t=0,...,Lの各整数tについての乱数η→dec,t:=ηdec,t,ii=1,...,wtに基づき、数12に示す復号要素をkL,decを生成し、前記暗号化データc1生成部は、t=0,...,Lの各整数tについての乱数φ→t:=φt,ii=1,...,ztに基づき、数13に示す暗号化データc1を生成することを特徴とする請求項8に記載の暗号処理システム。前記鍵生成装置は、さらに、j=1,...,2Lの各整数jについて、第1ランダム化要素kL,ran,jを生成するとともに、τ=L1,...,ddはL1以上の整数の各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、第2ランダム化要素kL,ran,τ,ι,0を生成するランダム化要素生成部であって、t=1,...,Lの各整数tについての所定の値θran,j,tと、sran,j,0=Σt=1Lsran,j,tであるようなt=0,...,Lについての所定の値sran,j,tと、t=0,...,Lの各整数tについての乱数η→ran,j,t:=ηran,j,t,ii=1,...,wtに基づき、数14に示す第1ランダム化要素kL,ran,jを生成し、t=1,...,Lの各整数tについての所定の値θran,0,tと、sran,0,0=Σt=1L1sran,0,tであるようなt=0,...,L1についての所定の値sran,0,tと、t=0,...,Lの各整数tについての乱数η→ran,0,t:=ηran,0,t,ii=1,...,wtと、乱数η→ran,0,τ,ι:=ηran,0,τ,ι,ii=1,...,wtとに基づき、数15に示す第2ランダム化要素kL,ran,τ,ι,0を生成するランダム化要素生成部を備え、前記委譲要素生成部は、τ=L1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、t=0,...,Lの各整数tについての乱数η→del,0,t:=ηdel,0,t,ii=1,...,wtと、乱数η→del,0,τ,ι:=ηdel,0,τ,ι,ii=1,...,wtとに基づき、数16に示す第1委譲要素kL,del,τ,ι,0を生成するとともに、τ=L1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、t=0,...,Lの各整数tについての乱数η→del,1,t:=ηdel,1,t,ii=1,...,wtと、乱数η→del,1,τ,ι:=ηdel,1,τ,ι,ii=1,...,wtとに基づき、数17に示す第2委譲要素kL,del,τ,ι,1を生成し、前記復号鍵送信部は、前記復号要素kL,decと、前記ランダム化要素生成部が生成した第1ランダム化要素kL,ran,j及び第2ランダム化要素kL,ran,τ,ι,0と、前記委譲要素生成部が生成した第1委譲要素kL,del,τ,ι,0及び第2委譲要素kL,del,τ,ι,1とを含む復号鍵skLを前記委譲装置へ送信し、前記下位復号要素生成部は、前記述語情報v→L1と、前記復号鍵送信部が送信した復号鍵skLと、j=1,...,2Lの各整数jについての乱数αdec,jと、乱数σdecと、t=0,...,L1の各整数tとi=1,...,wtの各整数iとについての乱数ηdec,t,iとを用いて、数18に示す下位復号要素kL1,decを生成することを特徴とする請求項10に記載の暗号処理システム。前記委譲装置は、さらに、j’=1,...,2L1の各整数j’について、第1下位ランダム化要素kL1,ran,j’を生成するとともに、τ=L2,...,ddはL2以上の整数の各整数τと、各整数τに関してι=1,...,nτの各整数ιについて、第2下位ランダム化要素kL1,ran,τ,ι,0を生成する下位ランダム化要素生成部であって、前記述語情報v→L1と、前記復号鍵skLと、j=1,...,2Lの各整数jとj’=1,...,2L1の各整数j’とについての乱数αran,j’,jと、j’=1,...,2L1の各整数j’についての乱数σran,j’と、t=0,...,L1の各整数tとi=1,...,wtの各整数iとについての乱数ηran,j’,t,iとに基づき、数19に示す第1下位ランダム化要素kL1,ran,j’を生成し、前記述語情報v→L1と、前記復号鍵skLと、j=1,...,2Lの各整数jについての乱数αran,τ,ι,jと、乱数σran,τ,ι,0と、乱数φran,τ,ι,0と、t=0,...,L1の各整数tとi=1,...,wtの各整数iとについてのηran,τ,ι,0,t,iとに基づき、数20に示す第2下位ランダム化要素kL1,ran,τ,ι,0を生成する下位ランダム化要素生成部と、τ=L2,...,ddはL2以上の整数の各整数τと、各整数τに関してι=1,...,nτの各整数ιについて、第1下位委譲要素kL1,del,τ,ι,0と第2下位委譲要素kL1,del,τ,ι,1とを生成する下位委譲要素生成部であって、前記述語情報v→L1と、前記復号鍵skLと、j=1,...,2Lの各整数jについての乱数αdel,τ,ι,0,jと、乱数σdel,τ,ι,0と、乱数ψ0と、乱数φdel,τ,ι,0と、t=0,...,L1の各整数tとi=1,...,wtの各整数iとについてのηdel,τ,ι,0,t,iとに基づき、数21に示す第1下位委譲要素kL1,del,τ,ι,0を生成し、前記述語情報v→L1と、前記復号鍵skLと、j=1,...,2Lの各整数jについての乱数αdel,τ,ι,1,jと、乱数σdel,τ,ι,1と、乱数ψ1と、乱数φdel,τ,ι,1と、t=0,...,L1の各整数tとi=1,...,wtの各整数iとについてのηdel,τ,ι,1,t,iとに基づき、数22に示す第2下位委譲要素kL1,del,τ,ι,1を生成する下位委譲要素生成部とを備えることを特徴とする請求項11に記載の暗号処理システム。t=1,...,LLは1以上の整数の各整数tについての基底Btと基底Btとを用いて暗号処理を行う暗号処理システムにおいて、復号鍵skLを生成する鍵生成装置であり、t=1,...,Lの各整数tについて述語情報v→t:=vt,ii=1,...,ntを入力する第1情報入力部と、前記第1情報入力部が入力した述語情報v→tと、所定の値Δと、t=1,...,Lの各整数tについての所定の値θdec,tと、sdec,0=Σt=1Lsdec,tであるようなt=0,...,Lの各整数tについての所定の値sdec,tとを用いて、基底B0の基底ベクトルb0,ppは所定の値の係数として-sdec,0を設定し、基底B0の基底ベクトルb0,qqは所定の値の係数として前記Δを設定し、t=1,...,Lの各整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数としてsdec,te→t,1θdec,tvt,ii=1,...,ntを設定した復号要素kL,decを生成する復号要素生成部と、前記復号要素生成部が生成した復号要素kL,decを含む復号鍵skLを復号装置へ送信する復号鍵送信部とを備えることを特徴とする鍵生成装置。t=1,...,LLは1以上の整数の各整数tについての基底Btと基底Btとを用いて暗号処理を行う暗号処理システムにおいて、暗号化データctを生成する暗号化装置であり、t=1,...,Lの少なくとも一部の整数tについて属性情報x→t:=xt,ii=1,...,ntを入力する第2情報入力部と、前記第2情報入力部が入力した属性情報x→tと、所定の値ω,ζとを用いて、基底B0の基底ベクトルb0,ppは所定の値の係数として前記ωを設定し、基底B0の基底ベクトルb0,qqは所定の値の係数として前記ζを設定し、前記少なくとも一部の整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数としてωxt,ii=1,...,ntを設定した暗号化データc1を生成する暗号化データc1生成部と、前記暗号化データc1生成部が生成した暗号化データc1を含む暗号化データctを復号装置へ送信するデータ送信部とを備えることを特徴とする暗号化装置。t=1,...,LLは1以上の整数の各整数tについての基底Btと基底Btとを用いて暗号処理を行う暗号処理システムにおいて、暗号化データc1を復号鍵skLにより復号する復号装置であり、属性情報x→t:=xt,ii=1,...,ntと、所定の値ω,ζとを用いて、基底B0の基底ベクトルb0,ppは所定の値の係数として前記ωを設定し、基底B0の基底ベクトルb0,qqは所定の値の係数として前記ζを設定し、前記少なくとも一部の整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数としてωxt,ii=1,...,ntを設定した暗号化データc1を暗号化装置から受信するデータ受信部と、述語情報v→t:=vt,ii=1,...,ntと、所定の値Δと、t=1,...,Lの各整数tについての所定の値θdec,tと、sdec,0=Σt=1Lsdec,tであるようなt=0,...,Lの各整数tについての所定の値sdec,tとを用いて、基底B0の基底ベクトルb0,ppは所定の値の係数として-sdec,0を設定し、基底B0の基底ベクトルb0,qqは所定の値の係数として前記Δを設定し、t=1,...,Lの各整数tについての基底Btの基底ベクトルbt,ii=1,...,ntの係数としてsdec,te→t,1θdec,tvt,ii=1,...,ntを設定した復号要素kL,decを含む復号鍵skLを鍵生成装置から取得する復号鍵取得部と、前記データ受信部が受信した暗号化データc1と、前記復号鍵取得部が取得した前記復号鍵skLに含まれる復号要素kL,decとについて、ペアリング演算ec1,kL,decを行い、前記暗号化データc1を復号するペアリング演算部とを備えることを特徴とする復号装置。t=1,...,L1Lは1以上の整数の各整数tについての基底Btと基底Btとを用いて暗号処理を行う暗号処理システムにおいて、復号鍵skLの下位の復号鍵skL1を生成する鍵委譲装置であり、t=1,...,Lの各整数tについての基底Btの基底ベクトルに述語情報v→tを埋め込んだベクトルを復号鍵skLとして取得する復号鍵取得部と、前記復号鍵取得部が取得した復号鍵skLと、基底BL1の基底ベクトルに述語情報v→L1を埋め込んだベクトルとに基づき、前記復号鍵skLの下位の復号鍵skL1を生成する委譲鍵生成部とを備えることを特徴とする鍵委譲装置。t=1,...,L1Lは1以上の整数の各整数tについての基底Btと基底Btとを用いた暗号処理方法であり、暗号化装置が、t=1,...,Lのうち少なくとも一部の整数tについての基底Btの基底ベクトルに属性情報x→tを埋め込んだベクトルを暗号化データctとして生成する暗号化工程と、復号装置が、t=1,...,Lの各整数tについての基底Btの基底ベクトルに述語情報v→tを埋め込んだベクトルを復号鍵skLとして、前記暗号化工程で生成した暗号化データctと前記復号鍵skLとについて、ペアリング演算を行い前記暗号化データctを復号する復号工程と、鍵委譲装置が、基底BL1の基底ベクトルに述語情報を埋め込んだベクトルv→L1と、前記復号工程で使用した復号鍵skLとに基づき、前記復号鍵skLの下位の復号鍵skL1を生成する鍵委譲工程とを備えることを特徴とする暗号処理方法。t=1,...,L1Lは1以上の整数の各整数tについての基底Btと基底Btとを用いて暗号処理を実行する暗号処理プログラムであり、t=1,...,Lのうち少なくとも一部の整数tについての基底Btの基底ベクトルに属性情報x→tを埋め込んだベクトルを暗号化データctとして生成する暗号化処理と、t=1,...,Lの各整数tについての基底Btの基底ベクトルに述語情報v→tを埋め込んだベクトルを復号鍵skLとして、前記暗号化装置が生成した暗号化データctと前記復号鍵skLとについて、ペアリング演算を行い前記暗号化データctを復号する復号処理と、基底BL1の基底ベクトルに述語情報を埋め込んだベクトルv→L1と、前記復号処理で使用した復号鍵skLとに基づき、前記復号鍵skLの下位の復号鍵skL1を生成する鍵委譲処理とを備えることを特徴とする暗号処理プログラム。非特許文献21に記載された階層的内積述語暗号方式では、1つの大きな空間を使って暗号処理を構築していた。そのため、この階層的内積述語暗号方式を実装した場合、鍵のサイズが大きくなり、演算等の効率が悪くなる虞がある。この発明は、演算等の効率をよくした階層的内積述語暗号を提供することを目的とする。この発明に係る暗号処理システムは、t=1,...,L1Lは1以上の整数の各整数tについての基底Btと基底Btとを用いて暗号処理を行う暗号処理システムであり、t=1,...,Lのうち少なくとも一部の整数tについての基底Btの基底ベクトルに属性情報x→tを埋め込んだベクトルを暗号化データctとして生成する暗号化装置と、t=1,...,Lの各整数tについての基底Btの基底ベクトルに述語情報v→tを埋め込んだベクトルを復号鍵skLとして、前記暗号化装置が生成した暗号化データctと前記復号鍵skLとについてペアリング演算を行い前記暗号化データctを復号する復号装置と、基底BL1の基底ベクトルに述語情報を埋め込んだベクトルと、前記復号装置が使用した復号鍵skLとに基づき、前記復号鍵skLの下位の復号鍵skL1を生成する鍵委譲装置とを備えることを特徴とする。この発明に係る暗号処理システムでは、複数の空間を用いて階層構造を構築している。そのため、鍵のサイズを小さくでき、演算効率がよくなる。以下、図に基づき、発明の実施の形態を説明する。以下の説明において、処理装置は後述するCPU911等である。記憶装置は後述するROM913、RAM914、磁気ディスク920等である。通信装置は後述する通信ボード915等である。入力装置は後述するキーボード902、通信ボード915等である。出力装置は後述するRAM914、磁気ディスク920、通信ボード915、LCD901等である。つまり、処理装置、記憶装置、通信装置、入力装置、出力装置はハードウェアである。以下の説明における記法について説明する。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に示す正規基底ベクトルを示す。また、数113から数117である。また、数118である場合に、数119である。また、以下の説明において、Fqntにおけるntはntのことである。同様に、秘密鍵skv→1,...,v→Lにおけるv→1,...,v→Lはv→1,...,v→Lのことであり、秘密鍵skv→1,...,v→L1におけるv→1,...,v→L1はv→1,...,v→L1のことである。同様に、δi,jが上付きで示されている場合、このδi,jは、δi,jを意味する。また、ベクトルを意味する→が下付き文字又は上付き文字に付されている場合、この→は下付き文字又は上付き文字に上付きで付されていることを意味する。また、以下の説明において、暗号処理とは、暗号化処理、復号処理、鍵生成処理、鍵委譲処理を含むものである。実施の形態1.この実施の形態では、階層的内積述語暗号を実現する基礎となる概念と、階層的内積述語暗号の構成について説明する。第1に、階層的内積述語暗号の概念について説明する。階層的内積述語暗号という概念を説明するに当たり、まず権限委譲という概念を説明する。また、併せて、階層的Hierarchialな権限委譲という概念を説明する。次に、内積述語暗号を説明する。そして、階層的な権限委譲という概念を内積述語暗号に加えた階層的内積述語暗号を説明する。さらに、階層的内積述語暗号の理解を深めるため、階層的内積述語暗号の応用例を説明する。第2に、ベクトル空間における階層的内積述語暗号を説明する。この実施の形態及び以下の実施の形態では、階層的述語暗号と階層的述語鍵秘匿方式とをベクトル空間において実現する。ここでは、まず、基底と基底ベクトルについて説明する。次に、ベクトル空間における内積述語暗号について説明する。そして、ベクトル空間における階層構造の実現方法について説明する。さらに、理解を深めるため、階層構造の実現例を説明する。第3に、階層的内積述語暗号を実現するための空間である双対ペアリングベクトル空間DualPairingVectorSpaces,DPVSという豊かな数学的構造を有する空間を説明する。第4に、この実施の形態に係る階層的内積述語暗号方式の基本構成を説明する。次に、階層的述語暗号を実行する暗号処理システム10の基本構成を説明する。そして、この実施の形態に係る階層的述語暗号方式及び暗号処理システム10について詳細に説明する。<第1.階層的内積述語暗号><第1-1.権限委譲階層的な権限委譲という概念>図1は、権限委譲階層的な権限委譲という概念を説明するための図である。権限委譲とは、上位の鍵を有する利用者が、その鍵上位の鍵よりも機能が制限された下位の鍵を生成することである。図1では、Root鍵生成装置は、マスター秘密鍵を用いて、第1層目Level-1の利用者へ秘密鍵を生成する。つまり、Rootは、第1層目の利用者1,2,3それぞれへ鍵1,2,3を生成する。そして、例えば、利用者1であれば、鍵1を用いて、利用者1の下位第2層目の利用者である利用者11,12,13それぞれへ鍵11,12,13を生成することができる。ここで、利用者1が有する鍵1よりも、利用者11,12,13が有する鍵11,12,13は機能が制限されている。機能が制限されているとは、その秘密鍵によって復号できる暗号文が限定されているということである。つまり、上位の秘密鍵で復号できる暗号文の一部の暗号文のみ下位の秘密鍵で復号できることを意味する。すなわち、利用者1が有する鍵1で復号できる暗号文のうち、一部の暗号文のみ利用者11,12,13が有する鍵11,12,13で復号することができる。また、通常は、鍵11と鍵12と鍵13とが復号できる暗号文は異なる。一方、鍵11と鍵12と鍵13が復号できる暗号文は、鍵1で復号することができる。また、図1に示すように、各秘密鍵が階層レベル分けされていることを階層的という。つまり、図1に示すように、階層的に下位の鍵を生成することを階層的な権限委譲と呼ぶ。なお、図1では、Rootが第1層目の利用者へ秘密鍵を生成し、第1層目の利用者が第2層目の利用者へ秘密鍵を生成し、第2層目の利用者が第3層目の利用者へ秘密鍵を生成すると説明した。しかし、図2に示すように、Rootは、第1層目の利用者へ秘密鍵を生成するだけでなく、第2層目以下の層の利用者へ秘密鍵を生成することもできる。同様に、第1層目の利用者は、第2層目の利用者へ秘密鍵を生成するだけでなく、第3層目以下の層の利用者へ秘密鍵を生成することもできる。つまり、Rootや利用者は、自分が持つ秘密鍵よりも下位の層の秘密鍵を生成することができる。<第1-2.内積述語暗号>次に、内積述語暗号について説明する。まず、述語暗号とは、述語情報fvに属性情報xを入力した場合に1Trueとなる場合fvx=1となる場合に、暗号文を復号できる暗号方式である。通常、暗号文に属性情報xが埋め込まれ、秘密鍵に述語情報fvが埋め込まれる。つまり、述語暗号では、属性情報xに基づき暗号化された暗号文cを、述語情報fvに基づき生成された秘密鍵SKfにより復号する。述語暗号は、例えば、述語情報fvが条件式であり、属性情報xがその条件式への入力情報であり、入力情報属性情報xが条件式述語情報fvを満たせばfvx=1、暗号文を復号できる暗号方式であるとも言える。なお、述語暗号について詳しくは非特許文献17に記載されている。内積述語暗号とは、属性情報xと述語情報fvとの内積が所定の値の場合に、fvx=1となる述語暗号である。つまり、属性情報xと述語情報fvとの内積が所定の値の場合にのみ、属性情報xにより暗号化された暗号文cを、述語情報fvに基づき生成された秘密鍵SKfにより復号することができる。実施の形態1では、原則として、属性情報xと述語情報fvとの内積が0の場合に、fvx=1となるものとする。<第1-3.階層的内積述語暗号>階層的内積述語暗号階層的内積述語鍵秘匿方式とは、上述した階層的な権限委譲という概念を有する内積述語暗号である。階層的内積述語暗号は、内積述語暗号に階層的な権限委譲システムを持たせるため、属性情報と述語情報とに階層構造を持たせる。図3は、属性情報と述語情報との階層構造を示す図である。図3において、符号が対応する属性情報と述語情報とは対応するつまり、内積が0となるものとする。つまり、属性1と述語1との内積は0となり、属性11と述語11との内積は0となり、属性12と述語12との内積は0となり、属性13と述語13との内積は0となるとする。すなわち、属性1により暗号化された暗号文c1は、述語1に基づき生成された秘密鍵k1であれば復号できる。また、属性11により暗号化された暗号文c11は、述語11に基づき生成された秘密鍵k11であれば復号できる。属性12と述語12、属性13と述語13についても同様のことが言える。上記の通り、階層的内積述語暗号は階層的な権限委譲システムを有する。そのため、述語1に基づき生成された秘密鍵k1と、述語11とに基づき、秘密鍵k11を生成することができる。つまり、上位の秘密鍵k1を有する利用者は、その秘密鍵k1と下位の述語11とから、秘密鍵k1の下位の秘密鍵k11を生成することができる。同様に、秘密鍵k1と述語12とから秘密鍵k12を生成でき、秘密鍵k1と述語13とから秘密鍵k13を生成できる。また、下位の秘密鍵に対応する鍵公開鍵で暗号化された暗号文を上位の秘密鍵で復号できる。一方、上位の秘密鍵に対応する鍵公開鍵で暗号化された暗号文は、下位の秘密鍵で復号できない。つまり、属性11、属性12、属性13により暗号化された暗号文c11、c12、c13は、述語1に基づき生成された秘密鍵k1であれば復号できる。一方、属性1により暗号化された暗号文c1は、述語11、述語12、述語13に基づき生成された秘密鍵k11、k12、k13では復号できない。すなわち、属性11、属性12、属性13と述語1との内積は0となる。一方、属性1と述語11、述語12、述語13との内積は0とならない。<第1-4.階層的内積述語暗号の応用例>図4は、後述する階層的内積述語暗号の応用例である階層的IDベース暗号HierarchialIdentifierBasedEncryption,HIBEの例を示す図である。なお、階層的IDベース暗号とは、IDベース暗号が階層的になった暗号処理である。IDベース暗号は、述語暗号の一種であり、暗号文に含まれるIDと秘密鍵に含まれるIDとが一致する場合に暗号文を復号できるマッチング述語暗号である。図4に示す例では、Root鍵生成装置は、マスター秘密鍵skとA会社のIDであるAとに基づき、IDAに対応する秘密鍵鍵Aを生成する。例えば、A会社のセキュリティ担当者は、鍵Aと各部門のIDとに基づき、そのIDに対応する秘密鍵を生成する。例えば、セキュリティ担当者は、営業部門のIDであるA-1に対応する秘密鍵鍵1を生成する。次に、例えば、各部門の管理者は、その部門の秘密鍵とその部門に属する各課のIDとに基づき、そのIDに対応する秘密鍵を生成する。例えば、営業部門の管理者は、営業1課のIDであるA-11に対応する秘密鍵鍵11を生成する。ここで、営業1課のIDA-11に対応する秘密鍵である鍵11により、営業1課のIDA-11で暗号化された暗号文を復号することができる。しかし、鍵11により、営業2課や営業3課のIDで暗号化された暗号文は復号することはできない。また、鍵11により、営業部門のIDで暗号化された暗号文は復号することができない。営業部門のIDA-1に対応する秘密鍵である鍵1により、営業部門のIDA-1で暗号化された暗号文を復号することができる。また、鍵1により、営業部門に属する課のIDで暗号化された暗号文を復号することができる。つまり、鍵1により、営業1課、営業2課、営業3課のIDで暗号化された暗号文を復号することができる。しかし、鍵1により、製造部門ID:A-2やスタッフ部門ID:A-3のIDで暗号化された暗号文は復号することができない。また、鍵1により、A会社のIDで暗号化された暗号文は復号することができない。A会社のIDAに対応する秘密鍵である鍵Aにより、A会社のIDAで暗号化された暗号文を復号することができる。また、A会社に属する各部門や、その部門に属する課のIDで暗号化された暗号文を復号することができる。階層的内積述語暗号は、IDベース暗号以外へも様々な応用が可能である。特に、以下に説明する暗号処理は、等号関係テストのクラスに限定されたものではないため、非常に多くの応用が可能である。例えば、内積述語暗号の一種である検索可能暗号等についても、階層毎に検索可能な範囲をAND条件やOR条件等の条件式を用いて限定する等、従来の権限委譲システムを有する述語暗号では実現できなかった応用が可能である。つまり、後の実施の形態で説明する階層的述語鍵秘匿方式と階層的述語暗号とは、IDベース暗号や検索可能暗号等へ幅広い応用が可能である。<第2.ベクトル空間における階層的内積述語暗号>階層的述語鍵秘匿方式と階層的述語暗号とは、後述する双対ペアリングベクトル空間という高次元ベクトル空間において実現される。そこで、ベクトル空間における階層的内積述語暗号を説明する。<第2-1.基底と基底ベクトル>まず、ベクトル空間の説明において使用する基底と基底ベクトルとについて簡単に説明する。図5は、基底と基底ベクトルとを説明するための図である。図5は、2次元ベクトル空間におけるベクトルvを示す。ベクトルvは、c1a1c2a2である。また、ベクトルvは、y1b1y2b2である。ここで、a1,a2を基底Aにおける基底ベクトルといい、基底A:=a1,a2と表す。また、b1,b2を基底Bにおける基底ベクトルといい、基底B:=b1,b2と表す。また、c1,c2,y1,y2は、各基底ベクトルに対する係数である。図5では、2次元ベクトル空間であったため、各基底における基底ベクトルは2個であった。しかし、N次元ベクトル空間であれば、各基底における基底ベクトルはN個である。<第2-2.ベクトル空間における内積述語暗号>次に、ベクトル空間における内積述語暗号を説明する。上記の通り、内積述語暗号とは、属性情報xと述語情報fvとの内積が所定の値ここでは、0の場合に、fvx=1となる述語暗号である。属性情報xと述語情報fvとがベクトルであった場合、つまり属性ベクトルx→と述語ベクトルv→とであった場合、内積述語は数120のように定義される。つまり、属性ベクトルx→と述語ベクトルv→との内積、つまり要素毎の内積の和が0である場合に、述語情報fvに属性情報xを入力した結果が1Trueとなる。また、属性ベクトルx→と述語ベクトルv→との内積が0でない場合に、述語情報fvに属性情報xを入力した結果が0Falseとなる述語暗号である。<第2-3.ベクトル空間における階層構造の実現方法>次に、ベクトル空間における階層構造の実現方法を説明する。図6は、ベクトル空間における階層構造の実現方法の一例を説明するための図である。ここではd個dは1以上の整数のベクトル空間を扱う。各ベクトル空間は、高次元Nt次元t=1,...,dベクトル空間である。つまり、各ベクトル空間における所定の基底Ctt=1,...,dには、基底ベクトルcii=1,...,NtのNt個の基底ベクトルが存在する。そして、基底C1を第1層目の属性情報や述語情報を設定するための空間とする。また、基底C2を第2層目の属性情報や述語情報を設定するための空間とする。以下同様に、基底CLを第L層目の属性情報や述語情報を設定するための空間とする。したがって、ここでは、d層の階層を表すことができる。ここで、第L層目の秘密鍵は、基底CLを用いて第L層目の述語情報を設定するだけでなく、基底C1から基底CL-1を用いて第1層目から第L-1層目の述語情報を設定して生成される。つまり、下位の層の秘密鍵には、上位の層の秘密鍵に設定される述語情報も設定される。これにより、述語情報に階層構造を持たせる。そして、この述語情報に持たせた階層構造を利用して、内積述語暗号における権限委譲システムを構成する。なお、以下の説明においては、ベクトル空間における階層的構造を示すために、階層情報n→:=d;N1,...,Ndを用いる。ここで、dは、上述した階層の深さを表す値である。Nii=1,...,dは、各層iに割り当てられた空間の次元数、つまり基底ベクトルの数を表す値である。<第2-4.階層構造の実現例>ここで、簡単な例を用いて階層構造を説明する。ここでは、3つの階層を備え、各階層に割り当てられた空間が2次元で構成された例を用いて説明する。つまり、n→:=d;N1,...,Nd=3;2,2,2である。第1層目の述語ベクトルv→1:=v1,v2に基づき生成された第1層目の秘密鍵sk1を有する利用者は、第1層目の秘密鍵sk1と第2層目の述語ベクトルv→2:=v3,v4に基づき第2層目の秘密鍵sk2を生成することができる。つまり、第2層目の秘密鍵sk2は、述語ベクトルv→1,v→2に基づき生成される。同様に、第2層目の秘密鍵sk2を有する利用者は、第2層目の秘密鍵sk2と第3層目の述語ベクトルv→3:=v5,v6に基づき第3層目の秘密鍵sk3を生成することができる。つまり、第3層目の秘密鍵sk3は、述語ベクトルv→1,v→2,v→3に基づき生成される。第1層目の述語ベクトルv→1に基づき生成された第1層目の秘密鍵sk1は、v→1,0,0,0,0により生成された秘密鍵である。そのため、第1層目の秘密鍵sk1は、属性ベクトルx→1,,,,:=x1,x2,,,,により暗号化された暗号文を、v→1x→1=0である場合には復号できる。なぜなら、,0,0=0であるためである。ここで、は、任意の値を示す。同様に、第2層目の述語ベクトルv→1,v→2に基づき生成された第2層目の秘密鍵sk2は、v→1,v→2,0,0により生成された秘密鍵である。そのため、第2層目の秘密鍵sk2は、属性ベクトルx→1,x→2,,:=x1,x2,x3,x4,,により暗号化された暗号文を、v→1x→1=0かつv→2x→2=0である場合には復号できる。しかし、第2層目の秘密鍵sk2は、第1層目の属性ベクトルx→1:=x1,x2つまり、x→1,,,,により暗号化された暗号文を復号することはできない。なぜなら、v→2=0,0でなければ、,v→2≠0であり、v→2x→2≠0であるためである。そのため、第2層目の秘密鍵sk2は、親である秘密鍵鍵sk2よりも限定された能力のみを有していると言える。<第3.双対ペアリングベクトル空間>まず、対称双線形ペアリング群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である。以下の説明において、数121を、1λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を出力するアルゴリズムとする。次に、双対ペアリングベクトル空間について説明する。双対ペアリングベクトル空間q,V,GT,A,eは、対称双線形ペアリング群paramG:=q,G,GT,g,eの直積によって構成することができる。双対ペアリングベクトル空間q,V,GT,A,eは、素数q、数122に示すFq上のN次元ベクトル空間V、位数qの巡回群GT、空間Vの標準基底A:=a1,...,aNの組であり、以下の演算12を有する。ここで、aiは、数123に示す通りである。演算1:非退化双線形ペアリング空間Vにおけるペアリングは、数124によって定義される。これは、非退化双線形である。つまり、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:ディストーション写像数125に示す空間Vにおける線形変換φi,jは、数126を行うことができる。ここで、線形変換φi,jをディストーション写像と呼ぶ。以下の説明において、数127を、1λλ∈自然数、N∈自然数、双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を入力として、セキュリティパラメータがλであり、N次元の空間Vとする双対ペアリングベクトル空間のパラメータparamV:=q,V,GT,A,eの値を出力するアルゴリズムとする。なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。<第4.階層的述語暗号の構成と暗号処理システム10><第4-1.階層的内積述語暗号の基本構成>階層的内積述語暗号方式の構成を簡単に説明する。階層的内積述語暗号方式は、Setup、KeyGen、Enc、Dec、DelegateLL=1,...,d-1の5つの確率的多項式時間アルゴリズムを備える。SetupSetupアルゴリズムでは、セキュリティパラメータ1λと階層情報n→:=d;N0,...,Ndとが入力され、マスター公開鍵pkとマスター秘密鍵skとが出力される。マスター秘密鍵skは最も上位の鍵である。KeyGenKeyGenアルゴリズムでは、マスター公開鍵pkとマスター秘密鍵skと述語ベクトルv→1,...,v→L1≦L≦dが入力され、第L層目の秘密鍵skv→1,...,v→Lが出力される。EncEncアルゴリズムでは、マスター公開鍵pkと属性ベクトルx→1,...,x→h1≦h≦dと平文情報mとが入力され、暗号化データct暗号文が出力される。つまり、Encアルゴリズムでは、平文情報mを埋め込み、属性ベクトルx→1,...,x→hにより暗号化された暗号化データctが出力される。DecDecアルゴリズムでは、マスター公開鍵pkと第L層目の秘密鍵skv→1,...,v→Lと暗号化データctとが入力され、平文情報m又は識別情報⊥が出力される。識別情報⊥とは、復号に失敗したことを示す情報である。つまり、Decアルゴリズムでは、暗号化データctを第L層目の秘密鍵で復号して、平文情報mを抽出する。また、復号に失敗した場合には識別情報⊥を出力する。DelegateLDelegateLでは、マスター公開鍵pkと第L層目の秘密鍵skv→1,...,v→Lと第L1層目の述語ベクトルv→L1L1≦dとが入力され、第L1層目の秘密鍵skv→1,...,v→L1が出力される。つまり、DelegateLアルゴリズムでは、下位の秘密鍵が出力される。<第4-2.暗号処理システム10>階層的内積述語暗号方式のアルゴリズムを実行する暗号処理システム10について説明する。図7は、階層的内積述語暗号方式のアルゴリズムを実行する暗号処理システム10の構成図である。暗号処理システム10は、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400を備える。なお、ここでは、復号装置300が、鍵委譲装置400を備えるものとして説明するが、鍵委譲装置400は、復号装置300とは別に設けられていてもよい。鍵生成装置100は、セキュリティパラメータλと、階層情報n→:=d;N0,...,Ndとを入力としてSetupアルゴリズムを実行して、マスター公開鍵pkとマスター秘密鍵skとを生成する。そして、鍵生成装置100は、生成したマスター公開鍵pkを公開する。また、鍵生成装置100は、マスター公開鍵pkとマスター秘密鍵skと述語ベクトルv→1,...,v→L1≦L≦dとを入力としてKeyGenアルゴリズムを実行して、第L層目の秘密鍵skv→1,...,v→Lを生成して第L層目の復号装置300へ秘密裡に配布する。暗号化装置200は、マスター公開鍵pkと属性ベクトルx→1,...,x→h1≦h≦dと平文情報mとを入力としてEncアルゴリズムを実行して、暗号化データctを生成する。暗号化装置200は、生成した暗号化データctを復号装置300へ送信する。復号装置300は、マスター公開鍵pkと第L層目の秘密鍵skv→1,...,v→Lと暗号化データctとを入力としてDecアルゴリズムを実行して、平文情報m又は識別情報⊥を出力する。鍵委譲装置400は、スター公開鍵pkと第L層目の秘密鍵skv→1,...,v→Lと第L1層目の述語ベクトルv→L1L1≦dとを入力としてDelegateLアルゴリズムを実行して、第L1層目の秘密鍵skv→1,...,v→L1を生成して第L1層目の復号装置300へ秘密裡に配布する。<第4-3.階層的内積述語暗号方式及び暗号処理システム10の詳細>図8から図16に基づき、実施の形態1に係る階層的内積述語暗号方式、及び、階層的内積述語暗号方式を実行する暗号処理システム10の機能と動作とについて説明する。図8は、鍵生成装置100の機能を示す機能ブロック図である。図9は、暗号化装置200の機能を示す機能ブロック図である。図10は、復号装置300の機能を示す機能ブロック図である。図11は、鍵委譲装置400の機能を示す機能ブロック図である。図12と図13とは、鍵生成装置100の動作を示すフローチャートである。なお、図12はSetupアルゴリズムの処理を示すフローチャートであり、図13はKeyGenアルゴリズムの処理を示すフローチャートである。図14は、暗号化装置200の動作を示すフローチャートであり、Encアルゴリズムの処理を示すフローチャートである。図15は、復号装置300の動作を示すフローチャートであり、Decアルゴリズムの処理を示すフローチャートである。図16は、鍵委譲装置400の動作を示すフローチャートであり、DelegateLアルゴリズムの処理を示すフローチャートである。なお、以下の説明において、添え字のdecはdecryptionの略であり、添え字にdecとあるものは、暗号化データの復号に用いられる復号要素である。また、添え字のranはrandomizationの略であり、添え字にranとあるものは、下位の復号鍵の所定の基底ベクトルに対する係数をランダム化するためのランダム化要素である。また、添え字のdelはdelegationの略であり、添え字にdelとあるものは、下位の復号鍵を生成するための委譲要素である。鍵生成装置100の機能と動作とについて説明する。図8に示すように、鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130第1情報入力部、復号鍵生成部140、鍵配布部150復号鍵送信部を備える。また、復号鍵生成部140は、乱数生成部141、復号要素生成部142、ランダム化要素生成部143、委譲要素生成部144を備える。まず、図12に基づき、Setupアルゴリズムの処理について説明する。S101:正規直交基底生成ステップマスター鍵生成部110は、処理装置により、数128を計算して、paramn→と、t=0,...,dの各整数tについて基底Bt及び基底Btとをランダムに生成する。つまり、マスター鍵生成部110は以下の処理を実行する。1マスター鍵生成部110は、入力装置により、セキュリティパラメータλ1λと、属性のフォーマットn→:=d;n1,...,nd,u0,...,ud,w0,...,wd,z0,...,zdとを入力する。ここで、dは1以上の整数である。t=1,...,dの各整数tについてntは1以上の整数である。t=0,...,dまでの各整数tについてut,wt,ztは1以上の整数である。また、マスター鍵生成部110は、N0:=1u01w0z0とし、t=1,...,dの各整数tについてNt:=ntutwtztとする。2マスター鍵生成部110は、処理装置により、1で入力したセキュリティパラメータλ1λを入力としてアルゴリズムGbpgを実行して、ランダムに双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を生成する。3マスター鍵生成部110は、処理装置により、乱数ψを生成する。続いて、マスター鍵生成部110は、t=0,...,dの各整数tについて以下の4から8までの処理を実行する。4マスター鍵生成部110は、処理装置により、1で入力したセキュリティパラメータλ1λ及び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,...,dと、gTとを設定する。なお、t=0,...,dとi=1,...,Ntとの各整数t,iについて、gT=ebt,i,bt,iである。すなわち、S101で、マスター鍵生成部110は、数129に示すアルゴリズムGobを実行して、paramn→と、t=0,...,dの各整数tについて基底Bt及び基底Btとを生成する。S102:マスター公開鍵生成ステップマスター鍵生成部110は、処理装置により、基底B0の部分基底B^0と、t=1,...,dの各整数tについて、基底Btの部分基底B^tを数130に示すように生成する。マスター鍵生成部110は、生成した部分基底B^0及び部分基底B^tと、S101で入力されたセキュリティパラメータλ1λと、S101で生成したparamn→と、基底ベクトルb0,1u011,...,b0,1u01w0ここでu0、w0は、u0,w0のことであると、t=1,...,dの各整数tについて基底ベクトルbt,ntut1,...,bt,ntutwtここでnt,ut,wtは、nt,ut,wtのことであるとを合わせて、マスター公開鍵pkとする。S103:マスター秘密鍵生成ステップマスター鍵生成部110は、処理装置により、基底B0の部分基底B^0と、t=1,...,dの各整数tについて、基底Btの部分基底B^tを数131に示すように生成する。マスター鍵生成部110は、生成した部分基底B^0及び部分基底B^tとをマスター秘密鍵とする。S104:マスター鍵記憶ステップマスター鍵記憶部120は、S102で生成したマスター公開鍵pkを記憶装置に記憶する。また、マスター鍵記憶部120は、S103で生成したマスター秘密鍵skを記憶装置に記憶する。つまり、S101からS103において、鍵生成装置100は数132に示すSetupアルゴリズムを実行して、マスター公開鍵pkとマスター秘密鍵skとを生成する。そして、S104で、鍵生成装置100は生成された公開パラメータpkとマスター鍵skとを記憶装置に記憶する。なお、マスター公開鍵pkは、例えば、ネットワークを介して公開され、復号装置300が取得可能な状態にされる。次に、図13に基づき、鍵生成装置100が実行するKeyGenアルゴリズムの処理について説明する。S201:情報入力ステップ情報入力部130は、入力装置により、述語情報v→1,...,v→L:=v1,ii=1,...,n1,...,vL,ii=1,...,nLを入力する。なお、述語情報としては、鍵を使用する者の属性が入力される。S202:乱数生成ステップ乱数生成部141は、処理装置により、j=1,...,2Lと,τ=L1,...,dと,τ,ι=τ,1,...,τ,nτとの各整数j,τ,ιについて、乱数ψと、乱数sdec,t,sran,j,tt=1,...,Lと、乱数θdec,t,θran,j,t,η→dec,t,η→ran,j,tt=0,...,Lと、乱数sran,τ,ι,t,sdel,τ,ι,tt=1,...,L1と、乱数θran,τ,ι,t,θdel,τ,ι,t,η→ran,τ,ι,t,η→del,τ,ι,tt=0,...,L1とを数133に示すように生成する。また、数134に示すようにsdec,0と、sran,j,0と、sran,τ,ι,0と、sdel,τ,ι,0とを設定する。S203:復号要素生成ステップ復号要素生成部142は、処理装置により、復号鍵skLの要素である復号要素kL,decを数135に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数135は、以下のように、基底B0及び基底Btt=1,...,Lの基底ベクトルの係数が設定され、復号要素kL,decが生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sdec,0が設定される。基底ベクトル11,...,1u0の係数として0が設定される。基底ベクトル1u01の係数として1が設定される。基底ベクトル1u011,...,1u01w0の係数としてηdec,0,1,...,ηdec,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。基底Btt=1,...,Lの基底ベクトル1の係数としてsdec,tθdec,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθdec,tvt,2,...,θdec,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηdec,t,1,...,ηdec,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。S204:第1ランダム化要素生成ステップランダム化要素生成部143は、処理装置により、j=1,...,2Lの各整数jについて、復号鍵skLの要素である第1ランダム化要素kL,ran,jを数136に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数136は、以下のように、基底B0及び基底Btt=1,...,Lの基底ベクトルの係数が設定され、第1ランダム化要素kL,ran,jが生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sran,j,0が設定される。基底ベクトル11,...,1u01の係数として0が設定される。基底ベクトル1u011,...,1u01w0の係数としてηran,j,0,1,...,ηran,j,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。基底Btt=1,...,Lの基底ベクトル1の係数としてsran,j,tθran,j,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθran,j,tvt,2,...,θran,j,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηran,j,t,1,...,ηran,j,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。S205:第2ランダム化要素生成ステップランダム化要素生成部143は、処理装置により、τ=L1,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、復号鍵skLの要素である第2ランダム化要素kL,ran,τ,ιを数137に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数137は、以下のように、基底B0と基底Btt=1,...,Lと基底Bτとの基底ベクトルの係数が設定され、第2ランダム化要素kL,ran,τ,ιが生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sran,τ,ι,0が設定される。基底ベクトル11,...,1u01の係数として0が設定される。基底ベクトル1u011,...,1u01w0の係数としてηran,τ,ι,0,1,...,ηran,τ,ι,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。基底Btt=1,...,Lの基底ベクトル1の係数としてsran,τ,ι,tθran,τ,ι,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθran,τ,ι,tvt,2,...,θran,τ,ι,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηran,τ,ι,t,1,...,ηran,τ,ι,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。基底Bτの基底ベクトル1の係数としてsran,τ,ι,L1が設定される。基底ベクトル2,...,nτ,...,nτuτの係数として0が設定される。基底ベクトルnτuτ1,...,nτuτwτの係数としてηran,τ,ι,L1,1,...,ηran,τ,ι,L1,wτここで、wτはwτのことであるが設定される。基底ベクトルnτuτwτ1,...,nτuτwτzτの係数として0が設定される。S206:委譲要素生成ステップ委譲要素生成部144は、処理装置により、τ=L1,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、復号鍵skLの要素である委譲要素kL,del,τ,ιを数138に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数138は、以下のように、基底B0と基底Btt=1,...,Lと基底Bτとの基底ベクトルの係数が設定され、委譲要素kL,del,τ,ιが生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sdel,τ,ι,0が設定される。基底ベクトル11,...,1u01の係数として0が設定される。基底ベクトル1u011,...,1u01w0の係数としてηdel,τ,ι,0,1,...,ηdel,τ,ι,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。基底Btt=1,...,Lの基底ベクトル1の係数としてsdel,τ,ι,tθdel,τ,ι,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθdel,τ,ι,tvt,2,...,θdel,τ,ι,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηdel,τ,ι,t,1,...,ηdel,τ,ι,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。基底Bτの基底ベクトル1,...,nτの係数としてsdel,τ,ι,L1e→τ,1ψe→τ,ιが設定される。基底ベクトルnτ1,...,nτuτの係数として0が設定される。基底ベクトルnτuτ1,...,nτuτwτの係数としてηdel,τ,ι,L1,1,...,ηdel,τ,ι,L1,wτここで、wτはwτのことであるが設定される。基底ベクトルnτuτwτ1,...,nτuτwτzτの係数として0が設定される。S207:鍵配布ステップ鍵配布部150は、復号要素kL,decと、第1ランダム化要素kL,ran,jj=1,...,2Lと、第2ランダム化要素kL,ran,τ,ιτ=L1,...,d;τ,ι=τ,1,...,τ,nτと、委譲要素kL,del,τ,ιτ=L1,...,d;τ,ι=τ,1,...,τ,nτとを要素とする復号鍵skLを、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skLは、他の方法により復号装置300へ配布されてもよい。つまり、S201からS206において、鍵生成装置100は数139、数140に示すKeyGenアルゴリズムを実行して、復号鍵skLを生成する。そして、S207で、鍵生成装置100は生成された復号鍵skLを復号装置300へ配布する。暗号化装置200の機能と動作とについて説明する。図9に示すように、暗号化装置200は、マスター公開鍵取得部210、情報入力部220第2情報入力部、暗号化データ生成部230、データ送信部240を備える。また、情報入力部220は、属性情報入力部221、メッセージ入力部222を備える。また、暗号化データ生成部230は、乱数生成部231、暗号化データc1生成部232、暗号化データc2生成部233を備える。図14に基づき、暗号化装置200が実行するEncアルゴリズムの処理について説明する。S301:マスター公開鍵取得ステップマスター公開鍵取得部210は、例えば、通信装置によりネットワークを介して、鍵生成装置100が生成したマスター公開鍵pkを取得する。S302:情報入力ステップ属性情報入力部221は、入力装置により、属性情報x→1,...,x→L:=x1,ii=1,...,n1,...,xL,ii=1,...,nLを入力する。なお、属性情報としては、暗号化したメッセージを復号可能な者の属性が入力される。また、メッセージ入力部222は、入力装置により、暗号化するメッセージmを入力する。S303:乱数生成ステップ乱数生成部231は、処理装置により、乱数x→L1,...,x→d:=xL1,ii=1,...,nL1,...,xd,ii=1,...,ndと、乱数ω,ζ,φ→tt=0,...,dとを数141に示すように生成する。S304:暗号化データc1生成ステップ暗号化データc1生成部232は、処理装置により、暗号化データctの要素である暗号化データc1を数142に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数142は、以下のように、基底B0及び基底Btt=1,...,dの基底ベクトルの係数が設定され、暗号化データc1が生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数としてωが設定される。基底ベクトル11,...,1u0の係数として0が設定される。基底ベクトル1u01の係数としてζが設定される。基底ベクトル1u011,...,1u01w0の係数として0が設定される。基底ベクトル1u01w01,...,1u01w0z0の係数としてφ0,1,...,φ0,zoここで、z0はz0のことであるが設定される。次に、基底Btt=1,...,dの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。基底Btt=1,...,dの基底ベクトル1,...,ntの係数としてωxt,1,...,ωxt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutwtの係数として0が設定される。基底ベクトルntutwt1,...,ntutwtztの係数としてφt,1,...,φt,ztここで、ztはztのことであるが設定される。S305:暗号化データc2生成ステップ暗号化データc2生成部233は、処理装置により、暗号化データctの要素である暗号化データc2を数143に示すように生成する。S306:データ送信ステップデータ送信部240は、暗号化データc1と、暗号化データc2とを含む暗号化データctを、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号化データctは、他の方法により復号装置300へ送信されてもよい。つまり、S301からS305において、暗号化装置200は数144に示すEncアルゴリズムを実行して、暗号化データctを生成する。そして、S306で、暗号化装置200は生成された暗号化データctを復号装置300へ送信する。復号装置300の機能と動作とについて説明する。図10に示すように、復号装置300は、復号鍵取得部310、データ受信部320、ペアリング演算部330、メッセージ計算部340を備える。図15に基づき、復号装置300が実行するDecアルゴリズムの処理について説明する。S401:復号鍵取得ステップ復号鍵取得部310は、例えば、通信装置によりネットワークを介して、復号鍵skLを取得する。また、復号鍵取得部310は、鍵生成装置100が生成した公開パラメータpkを取得する。S402:データ受信ステップデータ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号化データctを受信する。S403:ペアリング演算ステップペアリング演算部330は、処理装置により、数145に示すペアリング演算を行い、セッション鍵K=gTζを計算する。なお、v→1,...,v→Lとx→1,...,x→Lとの内積が0であれば、数145を計算することにより、セッション鍵Kが計算される。S404:メッセージ計算ステップメッセージ計算部340は、処理装置により、暗号化データc2をセッション鍵Kで割ることにより、メッセージm’=mを計算する。つまり、S401からS404において、復号装置300は数146に示すDecアルゴリズムを実行して、メッセージm’=mを計算する。鍵委譲装置400の機能と動作とについて説明する。図11に示すように、鍵委譲装置400は、復号鍵取得部410、情報入力部420第3情報入力部、委譲鍵生成部430、鍵配布部440委譲鍵送信部を備える。また、委譲鍵生成部430は、乱数生成部431、下位復号要素生成部432、下位ランダム化要素生成部433、下位委譲要素生成部434を備える。図16に基づき、鍵委譲装置400が実行するDelegateLアルゴリズムの処理について説明する。S501:復号鍵取得ステップ復号鍵取得部410は、例えば、通信装置によりネットワークを介して、復号鍵skLを取得する。また、復号鍵取得部410は、鍵生成装置100が生成した公開パラメータpkを取得する。S502:情報入力ステップ情報入力部420は、入力装置により、述語情報v→L1:=vL1,ii=1,...,nL1を入力する。なお、述語情報としては、鍵を委譲される者の属性が入力される。S503:乱数生成ステップ乱数生成部431は、処理装置により、j=1,...,2Lと,j’=1,...,2L1と,τ=L2,...,dと,τ,ι=τ,1,...,τ,nτと,t=0,...,L1,τと,t,i=t,1,...,t,ntとの各整数j,j’,τ,ι,t,iについて、乱数αdec,j,σdec,αran,j’,j,σran,j’,αran,τ,ι,j,σran,τ,ι,φran,τ,ι,αdel,τ,ι,j,σdel,τ,ι,φdel,τ,ι,ψ’,ηdec,t,i,ηran,j’,t,i,ηran,τ,ι,t,i,ηdel,τ,ι,t,iを数147に示すように生成する。S504:下位復号要素生成ステップ下位復号要素生成部432は、処理装置により、委譲鍵skL1の要素である下位復号要素kL1,decを数148に示すように生成する。S505:第1下位ランダム化要素生成ステップ下位ランダム化要素生成部433は、処理装置により、j’=1,...,2L1の各整数j’について、委譲鍵skL1の要素である第1下位ランダム化要素kL1,ran,j’を数149に示すように生成する。S506:第2下位ランダム化要素生成ステップ下位ランダム化要素生成部433は、処理装置により、τ=L2,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、委譲鍵skL1の要素である第2下位ランダム化要素kL1,ran,τ,ιを数150に示すように生成する。S507:下位委譲要素生成ステップ下位委譲要素生成部434は、処理装置により、τ=L2,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、委譲鍵skL1の要素である下位委譲要素kL1,del,τ,ιを数151に示すように生成する。S508:鍵配布ステップ鍵配布部150は、下位復号要素kL1,decと、第1下位ランダム化要素kL1,ran,j’j’=1,...,2L1と、第2下位ランダム化要素kL1,ran,τ,ιτ=L2,...,d;τ,ι=τ,1,...,τ,nτと、下位委譲要素kL1,del,τ,ιτ=L2,...,d;τ,ι=τ,1,...,τ,nτとを要素とする委譲鍵skL1下位の復号鍵を、例えば通信装置によりネットワークを介して秘密裡に下位の復号装置300へ配布する。もちろん、委譲鍵skL1は、他の方法により下位の復号装置300へ配布されてもよい。つまり、S501からS507において、鍵委譲装置400は数152、153に示すDelegateLアルゴリズムを実行して、委譲鍵skL1を生成する。そして、S508で、鍵委譲装置400は生成された委譲鍵skL1を下位の復号装置300へ配布する。なお、下位の復号装置300が、委譲鍵skL1を用いてDecアルゴリズムを実行した場合、図15のS403では、v→1,...,v→L1とx→1,...,x→L1との内積が0であれば、数145を計算することにより、セッション鍵Kが計算される。以上のように、実施の形態1に係る暗号処理システム10は、d1個のNtt=0,...,d次元空間を用いて、d階層の階層的内積述語暗号方式を実現する。ここで、第L層目1≦L≦dの暗号処理に必要な空間は、L1個のNtt=0,...,L次元空間である。したがって、鍵のサイズを小さくでき、演算等の効率をよくすることができる。また、鍵を記録するメモリやレジスタ等の領域も小さくなる。なお、上記説明において、ut、wt、ztt=0,...,dの次元は、安全性を高めるために設けた次元である。したがって、安全性が低くなってしまうが、ut、wt、ztt=0,...,dをそれぞれ0として、ut、wt、ztt=0,...,dの次元を設けなくてもよい。また、上記説明では、N0に1u01w0z0を設定し、Ntにntutwtztを設定した。しかし、1u01w0z0を11111としてN0に5を設定し、ntutwtztをntntnt1としてNtに3nt1を設定してもよい。この場合、数132に示すSetupアルゴリズムは、数154のように書き換えられる。なお、Gobは数155のように書き換えられる。また、数139、数140に示すKeyGenアルゴリズムは、数156、数157のように書き換えられる。また、数144に示すEncアルゴリズムは、数158のように書き換えられる。また、数152、数153に示すDelegateLアルゴリズムは、数159、数160のように書き換えられる。なお、数146に示すDecアルゴリズムに変更はない。また、Setupアルゴリズムは、暗号処理システム10のセットアップ時に一度実行すればよく、復号鍵を生成する度に実行する必要はない。また、上記説明では、SetupアルゴリズムとKeyGenアルゴリズムとを鍵生成装置100が実行するとしたが、SetupアルゴリズムとKeyGenアルゴリズムとをそれぞれ異なる装置が実行するとしてもよい。実施の形態2.この実施の形態では、実施の形態1で説明した方式を一般化した階層的内積述語暗号方式について説明する。実施の形態1で説明した階層的内積述語暗号方式では、原則として暗号化データctに設定された属性情報と、復号鍵に設定された述語情報との内積が0の場合に、暗号化データctを復号鍵で復号可能であった。しかし、実施の形態2で説明する階層的内積述語暗号方式では、暗号化データctに設定された属性情報と、復号鍵に設定された述語情報との内積が0とならない場合であっても復号可能となるように設定できる。具体的には、以下の説明において、ρtt=1,...,dの値が0である整数tについては、属性情報x→tと述語情報v→tとの内積が0となり、ρtt=1,...,dの値が1である整数tについては、属性情報x→tと述語情報v→tとの内積が0とならない場合に、復号可能となる。これにより、例えば、ρtt=1,...,dの値の設定に応じて、肯定形の条件式例えば、属性情報=述語情報と否定形の条件式属性情報≠述語情報との設定をすることができる。図17から図19に基づき、実施の形態2に係る階層的内積述語暗号方式、及び、階層的内積述語暗号方式を実行する暗号処理システム10の機能と動作とについて説明する。なお、実施の形態2に係る暗号処理システム10の機能構成については、図8から図11に示す実施の形態1に係る暗号処理システム10の機能構成と同一である。図17は、鍵生成装置100の動作を示すフローチャートであり、KeyGenアルゴリズムの処理を示すフローチャートである。図18は、復号装置300の動作を示すフローチャートであり、Decアルゴリズムの処理を示すフローチャートである。図19は、鍵委譲装置400の動作を示すフローチャートであり、DelegateLアルゴリズムの処理を示すフローチャートである。なお、実施の形態2に係るSetupアルゴリズムとEncアルゴリズムとの処理は、実施の形態1に係るSetupアルゴリズムとEncアルゴリズムとの処理と同一であるため、説明を省略する。但し、Encアルゴリズムでは、暗号化データctに、暗号化データc1,c2だけでなく、属性情報x→ii=1,...,Lも含めて、復号装置300へ送信する。図17に基づき、鍵生成装置100が実行するKeyGenアルゴリズムの処理について説明する。S601:情報入力ステップ情報入力部130は、入力装置により、述語情報v→1,ρ1,...,v→L,ρL:=v1,ii=1,...,n1,ρ1∈{0,1},...,vL,ii=1,...,nL,ρL∈{0,1}を入力する。なお、述語情報としては、鍵を使用する者の属性が入力される。S602:乱数生成ステップ乱数生成部141は、処理装置により、j=1,...,2Lと、τ=L1,...,dと、τ,ι=τ,1,...,τ,nτとの各整数j,τ,ιについて、乱数ψと、乱数sdec,t,sran,j,tt=1,...,Lと、乱数θdec,t,θran,j,t,η→dec,t,η→ran,j,t,η→ran,0,t,η→del,0,t,η→del,1,tt=0,...,Lと、乱数sran,0,t,sdel,0,t,sdel,1,tt=0,...,L1と、乱数θran,0,t,θdel,0,t,θdel,1,tt=0,...,L1と、乱数η→ran,τ,ι,η→del,0,τ,ι,η→del,1,τ,ιとを数161に示すように生成する。また、数162に示すようにsdec,0と、sran,j,0と、sran,0,0と、sdel,0,0と、sdel,1,0とを設定する。S603:復号要素生成ステップ復号要素生成部142は、処理装置により、復号鍵skLの要素である復号要素kL,decを数163に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数163は、以下のように、基底B0及び基底Btt=1,...,Lの基底ベクトルの係数が設定され、復号要素kL,decが生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sdec,0が設定される。基底ベクトル11,...,1u0の係数として0が設定される。基底ベクトル1u01の係数として1が設定される。基底ベクトル1u011,...,1u01w0の係数としてηdec,0,1,...,ηdec,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底Btt=1,...,Lについては、ρtの値が0であるか、1であるかによって場合分けされる。ρtの値が0の場合、基底Btt=1,...,Lの基底ベクトル1の係数としてsdec,tθdec,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθdec,tvt,2,...,θdec,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηdec,t,1,...,ηdec,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。一方、ρtの値が1の場合、基底Btt=1,...,Lの基底ベクトル1,...,ntの係数としてsdec,tvt,1,...,sdec,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηdec,t,1,...,ηdec,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。S604:第1ランダム化要素生成ステップランダム化要素生成部143は、処理装置により、j=1,...,2Lの各整数jについて、復号鍵skLの要素である第1ランダム化要素kL,ran,jを数164に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数164は、以下のように、基底B0及び基底Btt=1,...,Lの基底ベクトルの係数が設定され、第1ランダム化要素kL,ran,jが生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sran,j,0が設定される。基底ベクトル11,...,1u01の係数として0が設定される。基底ベクトル1u011,...,1u01w0の係数としてηran,j,0,1,...,ηran,j,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底Btt=1,...,Lについては、ρtの値が0であるか、1であるかによって場合分けされる。ρtの値が0の場合、基底Btt=1,...,Lの基底ベクトル1の係数としてsran,j,tθran,j,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθran,j,tvt,2,...,θran,j,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηran,j,t,1,...,ηran,j,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。一方、ρtの値が1の場合、基底Btt=1,...,Lの基底ベクトル1,...,ntの係数としてsran,j,tvt,1,...,sran,j,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηran,j,t,1,...,ηran,j,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。S605:第2ランダム化要素生成ステップランダム化要素生成部143は、処理装置により、τ=L1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、復号鍵skLの要素である第2ランダム化要素kL,ran,τ,ι,0を数165に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数165は、以下のように、基底B0と基底Btt=1,...,Lと基底Bτとの基底ベクトルの係数が設定され、第2ランダム化要素kL,ran,τ,ι,0が生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sran,0,0が設定される。基底ベクトル11,...,1u01の係数として0が設定される。基底ベクトル1u011,...,1u01w0の係数としてηran,0,0,1,...,ηran,0,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底Btt=1,...,Lについては、ρtの値が0であるか、1であるかによって場合分けされる。ρtの値が0の場合、基底Btt=1,...,Lの基底ベクトル1の係数としてsran,0,tθran,0,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθran,0,tvt,2,...,θran,0,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηran,0,t,1,...,ηran,0,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。一方、ρtの値が1の場合、基底Btt=1,...,Lの基底ベクトル1,...,ntの係数としてsran,0,tvt,1,...,sran,0,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηran,0,t,1,...,ηran,0,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。基底Bτの基底ベクトル1の係数としてsran,0,L1が設定される。基底ベクトル2,...,nτ,...,nτuτの係数として0が設定される。基底ベクトルnτuτ1,...,nτuτwτの係数としてηran,0,τ,ι,1,...,ηran,0,τ,ιs,wτここで、wτはwτのことであるが設定される。基底ベクトルnτuτwτ1,...,nτuτwτzτの係数として0が設定される。S606:第1委譲要素生成ステップ委譲要素生成部144は、処理装置により、τ=L1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、復号鍵skLの要素である第1委譲要素kL,del,τ,ι,0を数166に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数166は、以下のように、基底B0と基底Btt=1,...,Lと基底Bτとの基底ベクトルの係数が設定され、第1委譲要素kL,del,τ,ι,0が生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sdel,0,0が設定される。基底ベクトル11,...,1u01の係数として0が設定される。基底ベクトル1u011,...,1u01w0の係数としてηdel,0,0,1,...,ηdel,0,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底Btt=1,...,Lについては、ρtの値が0であるか、1であるかによって場合分けされる。ρtの値が0の場合、基底Btt=1,...,Lの基底ベクトル1の係数としてsdel,0,tθdel,0,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθdel,0,tvt,2,...,θdel,0,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηdel,0,t,1,...,ηdel,0,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。一方、ρtの値が1の場合、基底Btt=1,...,Lの基底ベクトル1,...,ntの係数としてsdel,0,tvt,1,...,sdel,0,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηdel,0,t,1,...,ηdel,0,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。基底Bτの基底ベクトル1,...,nτの係数としてsdel,0,L1e→τ,1ψe→τ,ιが設定される。基底ベクトルnτ1,...,nτuτの係数として0が設定される。基底ベクトルnτuτ1,...,nτuτwτの係数としてηdel,0,τ,ι,1,...,ηdel,0,τ,ι,wτここで、wτはwτのことであるが設定される。基底ベクトルnτuτwτ1,...,nτuτwτzτの係数として0が設定される。S607:第2委譲要素生成ステップ委譲要素生成部144は、処理装置により、τ=L1,...,dの各整数τと、各整数τに関してι=1,...,nτの各整数ιとについて、復号鍵skLの要素である第2委譲要素kL,del,τ,ι,1を数167に示すように生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数167は、以下のように、基底B0と基底Btt=1,...,Lと基底Bτとの基底ベクトルの係数が設定され、第2委譲要素kL,del,τ,ι,1が生成されることを意味する。まず、基底B0の部分について説明する。ここでは、表記を簡略化して、基底ベクトルb0,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルb0,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルb0,1,...,b0,3を意味する。基底B0の基底ベクトル1の係数として-sdel,1,0が設定される。基底ベクトル11,...,1u01の係数として0が設定される。基底ベクトル1u011,...,1u01w0の係数としてηdel,1,0,1,...,ηdel,1,0,woここで、w0はw0のことであるが設定される。基底ベクトル1u01w01,...,1u01w0z0の係数として0が設定される。次に、基底Btt=1,...,Lの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbt,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbt,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbt,1,...,bt,3を意味する。また、基底Btt=1,...,Lについては、ρtの値が0であるか、1であるかによって場合分けされる。ρtの値が0の場合、基底Btt=1,...,Lの基底ベクトル1の係数としてsdel,1,tθdel,1,tvt,1が設定される。基底ベクトル2,...,ntの係数としてθdel,1,tvt,2,...,θdel,1,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηdel,1,t,1,...,ηdel,1,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。一方、ρtの値が1の場合、基底Btt=1,...,Lの基底ベクトル1,...,ntの係数としてsdel,1,tvt,1,...,sdel,1,tvt,ntここで、ntはntのことであるが設定される。基底ベクトルnt1,...,ntutの係数として0が設定される。基底ベクトルntut1,...,ntutwtの係数としてηdel,1,t,1,...,ηdel,1,t,wtここで、wtはwtのことであるが設定される。基底ベクトルntutwt1,...,ntutwtztの係数として0が設定される。次に、基底Bτの部分について説明する。ここでは、表記を簡略化して、基底ベクトルbτ,iのうち、iの部分のみで基底ベクトルを特定する。例えば、基底ベクトル1であれば、基底ベクトルbτ,1を意味する。また、基底ベクトル1,...,3であれば、基底ベクトルbτ,1,...,bτ,3を意味する。基底Bτの基底ベクトル1,...,nτの係数としてsdel,1,L1e→τ,ιが設定される。基底ベクトルnτ1,...,nτuτの係数として0が設定される。基底ベクトルnτuτ1,...,nτuτwτの係数としてηdel,1,τ,ι,1,...,ηdel,1,τ,ι,wτここで、wτはwτのことであるが設定される。基底ベクトルnτuτwτ1,...,nτuτwτzτの係数として0が設定される。S608:鍵配布ステップ鍵配布部150は、復号要素kL,decと、第1ランダム化要素kL,ran,jj=1,...,2Lと、第2ランダム化要素kL,ran,τ,ι,0τ=L1,...,d;τ,ι=τ,1,...,τ,nτと、第1委譲要素kL,del,τ,ι,0τ=L1,...,d;τ,ι=τ,1,...,τ,nτと、第2委譲要素kL,del,τ,ι,1τ=L1,...,d;τ,ι=τ,1,...,τ,nτとを要素とする復号鍵skLを、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skLは、他の方法により復号装置300へ配布されてもよい。つまり、S601からS607において、鍵生成装置100は数168、数169に示すKeyGenアルゴリズムを実行して、復号鍵skLを生成する。そして、S608で、鍵生成装置100は生成された復号鍵skLを復号装置300へ配布する。図18に基づき、復号装置300が実行するDecアルゴリズムの処理について説明する。S701:復号鍵取得ステップ復号鍵取得部310は、例えば、通信装置によりネットワークを介して、復号鍵skLを取得する。また、復号鍵取得部310は、鍵生成装置100が生成した公開パラメータpkを取得する。S702:データ受信ステップデータ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号化データctを受信する。S703:ペアリング演算ステップペアリング演算部330は、処理装置により、数170に示すペアリング演算を行い、セッション鍵K=gTζを計算する。ここで、数171である。なお、t=1,...,Lの各整数tに関して、ρt=0の整数tについてv→tとx→tとの内積が0であり、ρt=1の整数tについてv→tとx→tとの内積が0でなければ、数170を計算することにより、セッション鍵Kが計算される。S704:メッセージ計算ステップメッセージ計算部340は、処理装置により、暗号化データc2をセッション鍵Kで割ることにより、メッセージm’=mを計算する。つまり、S701からS704において、復号装置300は数172に示すDecアルゴリズムを実行して、メッセージm’=mを計算する。図19に基づき、鍵委譲装置400が実行するDelegateLアルゴリズムの処理について説明する。S801:復号鍵取得ステップ復号鍵取得部410は、例えば、通信装置によりネットワークを介して、復号鍵skLを取得する。また、復号鍵取得部410は、鍵生成装置100が生成した公開パラメータpkを取得する。S802:情報入力ステップ情報入力部420は、入力装置により、述語情報v→L1,ρL1:=vL1,ii=1,...,nL1,ρL1∈{0,1}を入力する。なお、述語情報としては、鍵を委譲される者の属性が入力される。S803:乱数生成ステップ乱数生成部431は、処理装置により、j=1,...,2Lと,j’=1,...,2L1と,τ=L2,...,dと,τ,ι=τ,1,...,τ,nτと,t=0,...,L1,τと,t,i=t,1,...,t,ntとの各整数j,j’,τ,ι,t,iについて、乱数αdec,j,σdec,αran,j’,j,σran,j’,αran,τ,ι,0,j,σran,τ,ι,0,φran,τ,ι,0,αdel,τ,ι,0,j,σdel,τ,ι,0,φdel,τ,ι,0,αdel,τ,ι,1,j,σdel,τ,ι,1,φdel,τ,ι,1,ηdec,t,i,ηran,j’,t,i,ηran,τ,ι,0,t,i,ηdel,τ,ι,0,t,i,ηdel,τ,ι,1,t,i,ψ0,ψ1を数173に示すように生成する。S804:下位復号要素生成ステップ下位復号要素生成部432は、処理装置により、委譲鍵skL1の要素である下位復号要素kL1,decを数174に示すように生成する。S805:第1下位ランダム化要素生成ステップ下位ランダム化要素生成部433は、処理装置により、j’=1,...,2L1の各整数j’について、委譲鍵skL1の要素である第1下位ランダム化要素kL1,ran,j’を数175に示すように生成する。S806:第2下位ランダム化要素生成ステップ下位ランダム化要素生成部433は、処理装置により、τ=L2,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、委譲鍵skL1の要素である第2下位ランダム化要素kL1,ran,τ,ιを数176に示すように生成する。S807:第1下位委譲要素生成ステップ下位委譲要素生成部434は、処理装置により、τ=L2,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、委譲鍵skL1の要素である第1下位委譲要素kL1,del,τ,ι,0を数177に示すように生成する。S808:第2下位委譲要素生成ステップ下位委譲要素生成部434は、処理装置により、τ=L2,...,dの各整数τと、各整数τについてι=1,...,nτの各整数ιとについて、委譲鍵skL1の要素である第2下位委譲要素kL1,del,τ,ι,1を数178に示すように生成する。S809:鍵配布ステップ鍵配布部150は、下位復号要素kL1,decと、第1下位ランダム化要素kL1,ran,j’j’=1,...,2L1と、第2下位ランダム化要素kL1,ran,τ,ι,0τ=L2,...,d;τ,ι=τ,1,...,τ,nτと、第1下位委譲要素kL2,del,τ,ι,0τ=L2,...,d;τ,ι=τ,1,...,τ,nτと、第2下位委譲要素kL2,del,τ,ι,1τ=L2,...,d;τ,ι=τ,1,...,τ,nτとを要素とする委譲鍵skL1を、例えば通信装置によりネットワークを介して秘密裡に下位の復号装置300へ配布する。もちろん、委譲鍵skL1は、他の方法により下位の復号装置300へ配布されてもよい。つまり、S501からS507において、鍵委譲装置400は数179、数180に示すDelegateLアルゴリズムを実行して、委譲鍵skL1を生成する。そして、S508で、鍵委譲装置400は生成された委譲鍵skL1を下位の復号装置300へ配布する。なお、下位の復号装置300が、委譲鍵skL1を用いてDecアルゴリズムを実行した場合、図15のS403では、v→1,...,v→L1とx→1,...,x→L1との内積が0であれば、数170を計算することにより、セッション鍵Kが計算される。以上のように、実施の形態2に係る暗号処理システム10は、一部については属性情報と述語情報との内積が0となり、残りの部分については属性情報と述語情報との内積が0とならない場合に、復号可能な階層的内積述語暗号方式を実現する。そのため、例えば、肯定形と否定形との条件設定などが可能である。なお、上記説明において、ut、wt、ztt=0,...,dの次元は、安全性を高めるために設けた次元である。したがって、安全性が低くなってしまうが、ut、wt、ztt=0,...,dをそれぞれ0として、ut、wt、ztt=0,...,dの次元を設けなくてもよい。また、上記説明では、N0に1u01w0z0を設定し、Ntにntutwtztを設定した。しかし、1u01w0z0を11111としてN0に5を設定し、ntutwtztをntntnt1としてNtに3nt1を設定してもよい。この場合、数168、数169に示すKeyGenアルゴリズムは、数181、数182のように書き換えられる。また、数179、数180に示すDelegateLアルゴリズムは、数183、数184のように書き換えられる。なお、数172に示すDecアルゴリズムに変更はない。また、Setupアルゴリズムは、暗号処理システム10のセットアップ時に一度実行すればよく、復号鍵を生成する度に実行する必要はない。また、上記説明では、SetupアルゴリズムとKeyGenアルゴリズムとを鍵生成装置100が実行するとしたが、SetupアルゴリズムとKeyGenアルゴリズムとをそれぞれ異なる装置が実行するとしてもよい。実施の形態3.以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。この実施の形態では、双対加群において暗号処理を実現する方法について説明する。つまり、以上の実施の形態では、素数位数qの巡回群において暗号処理を実現した。しかし、合成数Mを用いて数185のように環Rを表した場合、環Rを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。実施の形態1で説明した階層的述語暗号方式を、環Rを係数とする加群において実現すると数186から数193のようになる。実施の形態2で説明した階層的述語暗号方式を、環Rを係数とする加群において実現すると数194から数199のようになる。なお、SetupアルゴリズムとGobアルゴリズムとは、数186と数187とに示す通りである。次に、実施の形態における暗号処理システム10鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400のハードウェア構成について説明する。図20は、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400のハードウェア構成の一例を示す図である。図20に示すように、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400は、プログラムを実行する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、復号鍵取得部410、情報入力部420、委譲鍵生成部430、鍵配布部440等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。ファイル群924には、上記の説明においてマスター公開鍵pk、マスター秘密鍵sk、復号鍵skL、委譲鍵skL1、暗号化データct、属性情報、述語情報、メッセージm等の情報やデータや信号値や変数値やパラメータが、ファイルやデータベースの各項目として記憶される。ファイルやデータベースは、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出検索参照比較演算計算処理出力印刷表示などのCPU911の動作に用いられる。抽出検索参照比較演算計算処理出力印刷表示のCPU911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、その他光ディスク等の記録媒体やICチップに記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。また、上記の説明において~部として説明するものは、~回路、~装置、~機器、~手段、~機能であってもよく、また、~ステップ、~手順、~処理であってもよい。また、~装置として説明するものは、~回路、~機器、~手段、~機能であってもよく、また、~ステップ、~手順、~処理であってもよい。さらに、~処理として説明するものは~ステップであっても構わない。すなわち、~部として説明するものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子デバイス基板配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM913等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、上記で述べた~部としてコンピュータ等を機能させるものである。あるいは、上記で述べた~部の手順や方法をコンピュータ等に実行させるものである。"