"各行各列に少なくとも1つは定数値0以外の値を有する疎行列を用いて所定の基底Aを変形して生成された基底Bと基底Bを利用し、暗号処理を行う暗号処理システムであり、前記基底Bにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化装置と、前記基底Bにおける所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号装置とを備えることを特徴とする暗号処理システム。前記疎行列は、n行n列nは2以上の整数の行列であり、定数値0以外の値として、少なくともn個の異なる値を有することを特徴とする請求項1に記載の暗号処理システム。前記疎行列は、少なくとも1つの列における全ての成分が定数値0以外の値であることを特徴とする請求項2に記載の暗号処理システム。前記疎行列は、対角成分と、少なくとも1つの列における全ての成分が定数値0以外の値であることを特徴とする請求項3に記載の暗号処理システム。前記疎行列は、全ての成分が定数値0以外の値である列を除き、対角成分の値が同一であることを特徴とする請求項4に記載の暗号処理システム。前記疎行列は、数1に示す行列であることを特徴とする請求項5に記載の暗号処理システム。前記暗号処理システムは、1行1列からn行n列までの値が数2に示す疎行列であるN行N列Nはn以上の整数の線形変換Xを用いて、数3に示すように前記基底Aから生成された基底Bと基底Bとを用い、前記暗号化装置は、数4を含むベクトルを前記暗号ベクトルとして生成し、前記復号装置は、数5を含むベクトルkを前記鍵ベクトルとして、前記暗号ベクトルを復号することを特徴とする請求項1に記載の暗号処理システム。前記数2に示す疎行列の値Bii=1,...,n-1の値は同一の値Bであり、前記暗号化装置は、数6を含むベクトルC1と数7を含むベクトルC2とを含むベクトルを前記暗号ベクトルとして生成し、前記復号装置は、数8に示すDを計算して、数9に示すペアリング演算を行うことを特徴とする請求項7に記載の暗号処理システム。前記数2に示す疎行列の値Bii=1,...,n-1の値は同一の値Bであり、前記暗号化装置は、数10を含むベクトルC1と数11を含むベクトルC2とを含むベクトルを前記暗号ベクトルとして生成し、前記復号装置は、数12に示すDを計算して、数13に示すペアリング演算を行うことを特徴とする請求項7に記載の暗号処理システム。前記暗号処理システムは、1行1列からn行n列までの値が数14に示す疎行列であるN行N列Nはn以上の整数の線形変換Xを用いて、数15に示すように前記基底Aから生成された基底Bと基底Bとを用い、前記暗号化装置は、数16を含むベクトルcを前記暗号ベクトルとして生成し、前記復号装置は、数17を含むベクトルを前記鍵ベクトルとして、前記暗号ベクトルを復号することを特徴とする請求項1に記載の暗号処理システム。前記数14に示す疎行列の値Bii=1,...,n-1の値は同一の値Bであり、前記復号装置は、数18を含むベクトルK1と数19を含むベクトルK2とを含むベクトルを前記鍵ベクトルとして、数20に示すDを計算して、数21に示すペアリング演算を行うことを特徴とする請求項10に記載の暗号処理システム。前記数14に示す疎行列の値Bii=1,...,n-1の値は同一の値Bであり、前記復号装置は、数22を含むベクトルK1と数23を含むベクトルK2とを含むベクトルを前記鍵ベクトルとして、数24に示すDを計算して、数25に示すペアリング演算を行うことを特徴とする請求項10に記載の暗号処理システム。各行各列に少なくとも1つは0以外の値を有する疎行列を用いて所定の基底Aを変形して生成された基底Bと基底Bを利用し、暗号処理を行う暗号処理方法であり、暗号化装置が、前記基底Bにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成し、復号装置が、前記基底Bにおける所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出することを特徴とする暗号処理方法。各行各列に少なくとも1つは0以外の値を有する疎行列を用いて所定の基底Aを変形して生成された基底Bと基底Bを利用し、暗号処理を行う暗号処理プログラムであり、前記基底Bにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化処理と、前記基底Bにおける所定のベクトルを鍵ベクトルとして、前記暗号化処理で生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号処理とをコンピュータに実行させることを特徴とする暗号処理プログラム。公開鍵暗号における公開パラメータと秘密鍵とを生成する鍵生成装置であり、各行各列に少なくとも1つは0以外の値を有する疎行列を含む線形変換Xを生成する行列生成部と、前記行列生成部が生成した線形変換Xを用いて、所定の基底Aから数26に示すように基底Dと基底Dとを生成する基底生成部と、前記基底生成部が生成した前記基底Dと前記基底Dとの一方の基底の少なくとも一部の基底ベクトルを公開パラメータとし、他方の基底の少なくとも一部の基底ベクトルを秘密鍵として生成するマスター鍵生成部とを備えることを特徴とする鍵生成装置。非特許文献13,16,17に記載された内積暗号では、内積暗号に用いるベクトルの長さをNとすると、公開パラメータやマスター秘密鍵のサイズはN2に比例し、ユーザへ与える秘密鍵の生成や暗号化の処理にN2に比例する時間がかかる。この発明は、公開パラメータやマスター秘密鍵のサイズを小さくするとともに、ユーザへ与える秘密鍵の生成の処理や暗号化の処理にかかる時間を短くすることを目的とする。この発明に係る暗号処理システムは、各行各列に少なくとも1つは0以外の値を有する疎行列を用いて所定の基底Aを変形して生成された基底Bと基底Bを利用し、暗号処理を行う暗号処理システムであり、前記基底Bにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化装置と、前記基底Bにおける所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号装置とを備えることを特徴とする。この発明に係る暗号処理システムでは、公開パラメータやマスター秘密鍵となる基底Bと基底Bとを生成するために用いる行列に疎行列を用いる。これにより、公開パラメータやマスター秘密鍵のサイズが小さくなるとともに、ユーザへ与える秘密鍵の生成の処理や暗号化の処理にかかる時間が短くなる。以下、図に基づき、発明の実施の形態を説明する。以下の説明において、処理装置は後述するCPU911等である。記憶装置は後述するROM913、RAM914、磁気ディスク920等である。通信装置は後述する通信ボード915等である。入力装置は後述するキーボード902、通信ボード915等である。出力装置は後述するRAM914、磁気ディスク920、通信ボード915、LCD901等である。つまり、処理装置、記憶装置、通信装置、入力装置、出力装置はハードウェアである。以下の説明における記法について説明する。Aがランダムな変数または分布であるとき、数101は、Aの分布に従いAからyをランダムに選択することを表す。つまり、数101において、yは乱数である。Aが集合であるとき、数102は、Aからyを一様に選択することを表す。つまり、数102において、yは一様乱数である。ベクトル表記は、位数qの有限体Fqにおけるベクトル表示を表す。例えば、数103である。数104は、数105に示す2つのベクトルx→とv→との数106に示す内積を表す。XTは、行列Xの転置行列を表す。bii=1,...,nが空間Vのベクトルの要素であるとき、つまり、数107であるとき、数108は、数109によって生成される部分空間を表す。数110に示す基底Bと基底Bとに対して、数111である。j=1,...,nのn個のベクトルに対して、e→jは、数112に示す標準基底ベクトルを示す。GLn,Fqは、有限体Fqにおける次数nの一般線形群を表す。また、以下の説明において、ベクトルを意味する→が下付き文字又は上付き文字に付されている場合、この→は下付き文字又は上付き文字に上付きで付されていることを意味する。同様に、基底Bにおけるが下付き文字又は上付き文字に付されている場合、このは下付き文字又は上付き文字に上付きで付されていることを意味する。また、同様に、空間Vtにおけるtが下付き文字又は上付き文字に付されている場合、このtは下付き文字又は上付き文字に下付きで付されていることを意味する。また、以下の説明において、暗号処理とは、暗号化処理、復号処理、鍵生成処理を含むものである。実施の形態1.この実施の形態では、内積暗号を実現する基礎となる概念と、内積暗号の構成とについて説明する。第1に、内積暗号の概念を説明する。第2に、内積暗号を実現するための空間である双対ペアリングベクトル空間DualPairingVectorSpaces,DPVSを説明する。第3に、以下の実施の形態で説明する内積暗号方式の基本構成を説明する。第4に、以下の実施の形態で説明する内積暗号方式を実行する暗号処理システム10の基本構成を説明する。第5に、以下の実施の形態で説明する内積暗号方式の基本的な考え方を説明する。<第1.内積暗号の概念>まず、関数型暗号FunctionalEncryptionについて説明する。関数型暗号は、進歩した暗号の概念である。また、関数型暗号は、公開鍵暗号Public-KeyEncryption,PKEやIDベース暗号Identity-BasedEncryption,IBEの一般化である。関数型暗号システムでは、暗号文を特定するパラメータyにパラメータxが適切に関連付けられているなら、受信者はパラメータxに対応する秘密鍵を用いて暗号文を復号できる。つまり、復号には、ある関係Rx,yに対して成立する関係Rに対してRx,y=1ことが必要である。内積暗号は、関数型暗号の一種である。内積暗号には、零内積暗号ZeroInnerProductEncryption,ZIPEと、非零内積暗号Non-zeroInnerProductEncryption,NIPEとがある。零内積暗号では、ベクトルx→に対して暗号化された暗号文は、x→y→=0であるベクトルy→と関連付けられた秘密鍵で復号することができる。つまり、x→y→=0である場合に限り、RZIPEx→,y→=1であることが必要である。非零内積暗号では、ベクトルx→に対して暗号化された暗号文は、x→y→≠0であるベクトルy→と関連付けられた秘密鍵で復号することができる。つまり、x→y→≠0である場合に限り、RNIPEx→,y→=1であることが必要である。<第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である。以下の説明において、Gbpgを、1λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータparamG:=q,G,GT,g,eの値を出力するアルゴリズムとする。次に、双対ペアリングベクトル空間について説明する。双対ペアリングベクトル空間q,V,GT,A,eは、対称双線形ペアリング群paramG:=q,G,GT,g,eの直積によって構成することができる。双対ペアリングベクトル空間q,V,GT,A,eは、素数q、数113に示す有限体Fq上のN次元ベクトル空間V、位数qの巡回群GT、空間Vの標準基底A:=a1,...,aNの組であり、以下の演算12を有する。ここで、aiは、数114に示す通りである。演算1:非退化双線形ペアリング空間Vにおけるペアリングは、数115によって定義される。これは、非退化双線形である。つまり、esx,ty=ex,ystであり、全てのy∈Vに対して、ex,y=1の場合、x=0である。また、全てのiとjとに対して、eai,aj=eg,gδi,jであるこのδi,jはδi,jを意味する。ここで、i=jであれば、δi,j=1であり、i≠jであれば、δi,j=0である。また、eg,g≠1∈GTである。演算2:標準写像数116に示す空間Vにおける線形変換φi,jは、数117によって容易に実現することができる。ここで、線形変換φi,jを標準写像と呼ぶ。以下の説明において、Gdpvsを、1λλ∈自然数、N∈自然数を入力として、セキュリティパラメータがλであり、N次元の空間Vとする双対ペアリングベクトル空間のパラメータparamV:=q,V,GT,A,eの値を出力するアルゴリズムとする。なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。<第3.内積暗号方式の基本構成>まず、零内積暗号方式について説明する。零内積暗号方式における関係RZIPEは、ベクトルx→∈Fnq\{0→}と、ベクトルv→∈Fnq\{0→}とにおいて定義される。そして、x→v→=0である場合に限り、関係RZIPEx→,v→:=1である。同様に、非零内積暗号方式における関係RNIPEは、ベクトルx→∈Fnq\{0→}と、ベクトルv→∈Fnq\{0→}とにおいて定義される。そして、x→v→≠0である場合に限り、関係RNIPEx→,v→:=1である。零内積暗号方式と非零内積暗号方式とは、Setup、KeyGen、Enc、Decの4つのアルゴリズムを備える。SetupSetupアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータpkと、マスター秘密鍵skとを出力する確率的アルゴリズムである。KeyGenKeyGenアルゴリズムは、ベクトルv→と、公開パラメータpkと、マスター秘密鍵skとを入力として、復号鍵skv→を出力する確率的アルゴリズムである。EncEncアルゴリズムは、メッセージmと、ベクトルx→と、公開パラメータpkとを入力として、暗号文ctx→を出力する確率的アルゴリズムである。DecDecアルゴリズムは、ベクトルx→の下で暗号化された暗号文ctx→と、ベクトルv→に対する復号鍵skv→と、公開パラメータpkとを入力として、メッセージm、又は、識別情報⊥を出力するアルゴリズムである。識別情報⊥は、復号できなかったことを示す情報である。<第4.暗号処理システム10の基本構成>図1は、零内積暗号方式と非零内積暗号方式とを実行する暗号処理システム10の構成図である。鍵生成装置100は、セキュリティパラメータλを入力としてSetupアルゴリズムを実行して、公開パラメータpkとマスター秘密鍵skとを生成する。そして、鍵生成装置100は、生成した公開パラメータpkを公開する。また、鍵生成装置100は、ベクトルv→を入力としてKeyGenアルゴリズムを実行して、復号鍵skv→を生成して復号装置300へ秘密裡に配布する。暗号化装置200は、メッセージmと、ベクトルx→と、公開パラメータpkとを入力としてEncアルゴリズムを実行して、暗号文ctx→を生成する。暗号化装置200は、生成した暗号文ctx→を復号装置300へ送信する。復号装置300は、公開パラメータpkと、復号鍵skv→と、暗号文ctx→とを入力としてDecアルゴリズムを実行して、メッセージm’=m又は識別情報⊥を出力する。<第5.暗号方式の基本的な考え方>双対ペアリングベクトル空間を暗号処理に適用した典型的なアプリケーションでは、双対基底又は正規直交基底のペアである基底Bと基底Bとが生成される。基底Bと基底Bとは、GLN,Fqから一様に選択された、完全にランダムな線形変換X基底変換行列を用いて生成される。特に、基底Bと基底Bとは、それぞれ、線形変換Xと、X-1Tとにより、標準基底Aを変換して生成される。なお、Nは、span<B>とspan<B>との次元数である。そして、双対ペアリングベクトル空間を暗号処理に適用した典型的なアプリケーションでは、基底Bの一部B^というが公開パラメータとして用いられ、これに対応する基底Bの一部B^というが秘密鍵又はトラップドアとして用いられる。以下の実施の形態で説明する内積暗号では、上述した完全にランダムな線形変換Xに代えて、X∈GLN,Fqであるランダムな線形変換Xの特別な形式を用いる。この特別な形式の線形変換Xにより、暗号文又は秘密鍵のサイズを小さくすることができるとともに、処理に時間のかかるペアリング演算の数を減らすことができる。図2は、特別な形式の線形変換Xの説明図である。図2aは、完全にランダムな線形変換Xを示し、図2bは、特別な形式の線形変換Xを示す。図2abにおいて、四角が示す部分は成分の値が0以外の乱数であることを示し、図2bにおいて、空白部分は成分の値が0であることを示している。また、図2bにおいて、斜線が入れられた四角が示す部分は成分の値が同じ値であることを示す。なお、ここでは、N=5としている。図2aに示すように、従来の線形変換Xは、N2ここでは、52=25のサイズであった。これに対して、図2bに示すように、以下の実施の形態で説明する内積暗号で用いる線形変換X以下、新しい線形変換Xは、N1ここでは、51=6のサイズである。上述したように、基底Bと基底Bとは、線形変換Xを用いて標準基底Aを変換して生成される。そのため、基底Bと基底Bとのサイズは、線形変換Xのサイズに比例する。また、上述したように、基底Bと基底Bとは、その一部が公開パラメータと秘密鍵にされる。したがって、公開パラメータと秘密鍵とのサイズは、線形変換Xのサイズに比例する。つまり、従来の線形変換Xを用いた場合、公開パラメータと秘密鍵とのサイズは、N2に比例する。これに対して、新しい線形変換Xを用いた場合、公開パラメータと秘密鍵とのサイズは、N1に比例する。その結果、従来の線形変換Xを用いた場合、ユーザ鍵の生成の処理や暗号化の処理にN2に比例した時間がかかっていた。これに対して、新しい線形変換Xを用いた場合、ユーザ鍵の生成の処理や暗号化の処理にN1に比例した時間になる。つまり、新しい線形変換Xを用いた場合、計算時間が、Nのオーダーになる。次に、非零内積暗号方式を例として、定数サイズの暗号文と効率的な復号を実現する具体的な方法について説明する。なお、暗号文のサイズを説明する場合、ベクトルの記述は暗号文の一部に含めないものとする。復号鍵のサイズを説明する場合も同様に、ベクトルの記述は暗号文の一部に含めないものとする。以下の実施の形態で説明する非零内積暗号方式を簡略化したものを用いて説明する。簡略化した非零内積暗号方式における暗号文は、2つのベクトル要素c0,c1∈G5×Gnと、c3∈GTとからなる。秘密鍵は、2つのベクトル要素k0,k1∈G5×Gnからなる。なお、c0,c1∈G5×Gnとは、c0がGの5個の要素であり、c1がGのn個の要素であることを意味する。同様に、k0,k1∈G5×Gnとは、k0がGの5個の要素であり、k1がGのn個の要素であることを意味する。そのため、暗号文のサイズを定数サイズにするには、c1∈Gnをnについての定数サイズに圧縮する必要がある。数118に示す特別な線形変換Xを用いる。ここで、μ,μ’1,...,μ’nは有限体Fqから一様に選択された値であり、線形変換Xにおける空白は定数値0∈Fqであることを示す。定数値0とは、値が0に固定されていることを意味する。つまり、μ,μ’1,...,μ’nは0も取り得る一様乱数であるのに対して、線形変換Xにおける空白は値が0に固定されている。また、Hn,Fqとは、有限体Fqを要素とするn次元の行列の集合を意味する。システムパラメータ又はDPVSの公開基底は、数119に示す基底Bである。x→:=x1,...,xnに関連付けられた暗号文を、数120に示す暗号文c1とする。ここで、ωは有限体Fqから一様に選択された値である。すると、暗号文c1は、数121に示す2つのグループの要素C1,C2と、ベクトルx→とに圧縮できる。暗号文c1は、x1C1,...,xn-1C1,C2によって得られるためである。なお、i=1,...,n-1の各iについて、xiC1=xiωμgである。したがって、暗号文ベクトルx→を除いた部分は、2つのグループの要素とすることができ、nについての定数サイズとなる。B:=biを、B:=biの双対正規直交基底とし、基底Bを、簡略化した非零内積暗号方式におけるマスター秘密鍵であるとする。c0,k0,c3を、ec0,k0=gTζgTωδであり、c3:=gTζm∈GTであると規定する。また、ベクトルv→に対する秘密鍵を、k1:=δv→B=δv1b1vnbnのように設定する。基底Bと基底Bとの双対正規直交性により、ec1,k1=gTωδx→v→が成立する。そのため、復号者は、x→v→≠0である場合に限り、gTωδを計算できる。つまり、復号者は、数122によりメッセージmを得ることができる。暗号文c1は、x1C1,...,xn-1C1,C2∈Gnとして表され、秘密鍵k1は、K1,...,Knのn組に分解される。そのため、ec1,k1の値は、数123である。つまり、ec1,k1を計算するには、Gにおけるn-1個のスカラー乗法と、2つのペアリング演算とで十分である。すなわち、復号には、少ない数定数のペアリング演算だけが必要となる。一般に、ペアリング演算は、処理時間がかかる演算であるため、ペアリング演算の数を減らすことにより、処理全体としての処理時間を短くすることができる。なお、簡略化した非零内積暗号方式では、暗号文c1はベクトルx→が設定される基底ベクトル実際の符号化部のみを備え、秘密鍵k1はベクトルv→が設定される基底ベクトル実際の符号化部のみを備えた。以下の実施の形態で説明する非零内積暗号方式では、安全性を高めるため、暗号文c1と秘密鍵k1とに、実際の符号化部に加え、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための基底ベクトルを加える。そのため、線形変換Xを数124のように拡張する。ここで、各Xi,jは、数118に示すX∈Hn,Fqである。そして、ベクトル空間は、4つの直交する部分空間で構成される。つまり、ベクトル空間は、符号化部と、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための4つの直交する部分空間で構成される。実施の形態2.実施の形態2では、暗号文のサイズを定数サイズとした非零内積暗号方式について説明する。図3は、実施の形態2に係る鍵生成装置100の構成図である。図4は、実施の形態2に係る暗号化装置200の構成図である。図5は、実施の形態2に係る復号装置300の構成図である。図6と図7とは、実施の形態2に係る鍵生成装置100の動作を示すフローチャートである。なお、図6は、実施の形態2に係るSetupアルゴリズムの処理を示すフローチャートであり、図7は、実施の形態2に係るKeyGenアルゴリズムの処理を示すフローチャートである。図8は、実施の形態2に係る暗号化装置200の動作を示すフローチャートであり、実施の形態2に係るEncアルゴリズムの処理を示すフローチャートである。図9は、実施の形態2に係る復号装置300の動作を示すフローチャートであり、実施の形態2に係るDecアルゴリズムの処理を示すフローチャートである。なお、以下の説明において、入力されるベクトルx→:=x1,...,xnは、L=1,...,n-1の各整数LについてxL≠0であり、入力されるベクトルv→:=v1,...,vnは、vn≠0であるとする。鍵生成装置100について説明する。図3に示すように、鍵生成装置100は、マスター鍵生成部110、マスター鍵記憶部120、情報入力部130、復号鍵生成部140、鍵配布部150を備える。マスター鍵生成部110は、空間生成部111、行列生成部112、基底生成部113、鍵生成部114を備える。復号鍵生成部140は、乱数生成部141、鍵要素生成部142を備える。図6に基づき、Setupアルゴリズムの処理について説明する。S101:空間生成ステップ空間生成部111は、セキュリティパラメータ1λを入力として、処理装置によりGbpgを実行して、対称双線形ペアリング群のパラメータparamG:=q,G,GT,g,eを生成する。さらに、空間生成部111は、N0:=5、N1:=4nを設定する。そして、空間生成部111は、t=0,1の各tについて、セキュリティパラメータ1λと、Ntと、対称双線形ペアリング群のパラメータparamGとを入力として、処理装置によりGdpvsを実行して、双対ペアリングベクトル空間のパラメータparamVt:=q,Vt,GT,At,eを生成する。S102:線形変換生成ステップ行列生成部112は、数125に示すように、処理装置により線形変換X0を生成する。なお、数125におけるχ0,i,ji,j=1,...,5は、行列χ0,i,jの添え字i,jに関する行列という意味という意味である。また、行列生成部112は、数126に示すように、処理装置により線形変換X1を生成する。数126におけるLN,Fqは、数127に示す通りである。なお、以下、{μi,j,μ’i,j,L}i,j=1,...,4;L=1,...,nは、線形変換X1における定数値0以外の要素を示す。S103:基底B生成ステップ基底生成部113は、数128に示すように、処理装置により基底B0と変数Bi,jと変数B’i,j,Lとを生成する。また、基底生成部113は、数129に示すように、処理装置により基底B0と基底B1とを生成する。S104:基底B^生成ステップ鍵生成部114は、数130に示すように、処理装置により基底B^0と、基底B^0と、基底B^1とを生成する。S105:マスター鍵生成ステップ鍵生成部114は、処理装置により公開パラメータpk:=1λ,paramn,B^0,{Bi,j,B’i,j,L}i=1,4;j=1,...,4;L=1,...,nとし、マスター秘密鍵sk:={B^t}t=0,1とする。そして、鍵生成部114は、公開パラメータpkと、マスター秘密鍵skとをマスター鍵記憶部120に記憶する。なお、paramn:={paramVt}t=0,1,gTである。つまり、S101からS105において、鍵生成装置100は、数131に示すアルゴリズムG1obを用いた、数132に示すSetupアルゴリズムを実行して、公開パラメータpkとマスター秘密鍵skとを生成する。なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置200や復号装置300が取得可能な状態にされる。S103では、基底B1を生成せず、代わりに変数Bi,jを生成した。基底B1を生成するのであれば、数133のようになる。数133の行列における空白部分は成分の値が0∈Gであることを示している。基底B1は、基底B1の正規直交基底である。つまり、eb1,i,b1,j=gTであり、1≦i≠j≦4nの整数i,jに対して、eb1,i,b1,j=1である。図7に基づき、KeyGenアルゴリズムの処理について説明する。S111:情報入力ステップ情報入力部130は、ベクトルv→を入力装置により入力する。S112:乱数生成ステップ乱数生成部141は、数134に示すように、処理装置により乱数を生成する。S113:要素k0生成ステップ鍵要素生成部142は、数135に示すように、処理装置により復号鍵skv→の要素である要素k0を生成する。なお、上述したように、数110に示す基底Bと基底Bとに対して、数111である。したがって、数135は、基底B0の基底ベクトルb0,1の係数としてδを設定し、基底ベクトルb0,2の係数として0を設定し、基底ベクトルb0,3の係数として1を設定し、基底ベクトルb0,4の係数としてφ0を設定し、基底ベクトルb0,5の係数として0を設定することを意味する。S114:要素k1生成ステップ鍵要素生成部142は、数136に示すように、処理装置により復号鍵skv→の要素である要素k1を生成する。数136は、数135と同様に、基底B1の基底ベクトルb1,1,...,b1,nの係数としてδv1,...,δvnを設定し、基底ベクトルb1,n1,...,b1,2nの係数として0を設定し、基底ベクトルb1,2n1,...,b1,3nの係数としてφ1v1,...,φ1vnを設定し、基底ベクトルb1,3n1,...,b1,4nの係数として0を設定することを意味する。S115:鍵配布ステップ鍵配布部150は、S111で入力したベクトルv→と、S113で生成した要素k0と、S114で生成した要素k1とを要素とする復号鍵skv→を、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skv→は、他の方法により復号装置300へ配布されてもよい。つまり、S111からS114において、鍵生成装置100は、数137に示すKeyGenアルゴリズムを実行して、復号鍵skv→を生成する。そして、S115において、鍵生成装置100は、生成された復号鍵skv→を復号装置300へ配布する。暗号化装置200について説明する。図4に示すように、暗号化装置200は、公開パラメータ取得部210、情報入力部220、暗号文生成部230、データ送信部240を備える。暗号文生成部230は、乱数生成部231、暗号要素生成部232を備える。図8に基づき、Encアルゴリズムの処理について説明する。S121:公開パラメータ取得ステップ公開パラメータ取得部210は、例えば、通信装置によりネットワークを介して、鍵生成装置100が生成した公開パラメータpkを取得する。S122:情報入力ステップ情報入力部220は、ベクトルx→を入力装置により入力する。また、情報入力部220は、メッセージmを入力装置により入力する。S123:乱数生成ステップ乱数生成部231は、数138に示すように、処理装置により乱数を生成する。S124:要素c0生成ステップ暗号要素生成部232は、数139に示すように、処理装置により暗号文ctx→の要素である要素c0を生成する。数139は、数135と同様に、基底B0の基底ベクトルb0,1の係数として-ωを設定し、基底ベクトルb0,2の係数として0を設定し、基底ベクトルb0,3の係数としてζを設定し、基底ベクトルb0,4の係数として0を設定し、基底ベクトルb0,5の係数としてη0を設定することを意味する。S125:要素C生成ステップ暗号要素生成部232は、数140に示すように、処理装置により暗号文ctx→の要素である要素C1,jと要素C2,jとを生成する。S126:要素c3生成ステップ暗号要素生成部232は、数141に示すように、処理装置により暗号文ctx→の要素である要素c3を生成する。S127:データ送信ステップデータ送信部240は、S122で入力したベクトルx→と、S124で生成した要素c0と、S125で生成した要素C1,j,C2,jと、S126で生成した要素c3とを要素とする暗号文ctx→を、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号文ctx→は、他の方法により復号装置300へ送信されてもよい。つまり、S121からS126において、暗号化装置200は、数142に示すEncアルゴリズムを実行して、暗号文ctx→を生成する。そして、S127において、暗号化装置200は、生成された暗号文ctx→を復号装置300へ送信する。復号装置300について説明する。図5に示すように、復号装置300は、復号鍵取得部310、データ受信部320、ペアリング演算部330、メッセージ計算部340を備える。図9に基づき、Decアルゴリズムの処理について説明する。S131:復号鍵取得ステップ復号鍵取得部310は、例えば、通信装置によりネットワークを介して、鍵生成装置100から配布されたskv→を取得する。また、復号鍵取得部310は、鍵生成装置100が生成した公開パラメータpkを取得する。S132:データ受信ステップデータ受信部320は、例えば、通信装置によりネットワークを介して、暗号化装置200が送信した暗号文ctx→を受信する。S133:値Dj計算ステップペアリング演算部330は、数143に示すように、処理装置により値Djを計算する。ここで、要素k1は、K1,...,K4n∈G4nの4n組に分解される。S134:ペアリング演算ステップペアリング演算部330は、数144に示すように、処理装置によりペアリング演算を実行して、値Fを計算する。S135:メッセージ計算ステップメッセージ計算部340は、数145に示すように、処理装置によりメッセージm’を計算する。つまり、S131からS135において、復号装置300は、数146に示すDecアルゴリズムを実行して、メッセージm’を計算する。なお、数133からB1:=b1,1,...,b1,4nは、{Bi,j,B’i,j,L}i,j=1,...,4;L=1,...,nによって特定される。また、Setupアルゴリズムの出力に含まれる{Bi,j,B’i,j,L}i=1,4;j=1,...,4;L=1,...,nは、B^1:=b1,1,...,b1,n,b1,3n1,...,b1,4nによって特定される。そして、Decアルゴリズムは、数147に示すDec’アルゴリズムのように記述することができる。数148に示すように、Decアルゴリズムを用いた場合、x→v→≠0であれば、F=gζTが得られる。そのため、c3=gζTmをFで除することにより、メッセージm’=mが得られる。実施の形態2で説明した非零内積暗号方式では、暗号文ctx→は、数139に示す要素c0で5個と、数140に示す、j=1,...,4の各整数jについての要素C1,j及び要素C2,jで8個との合計13個のGの要素を含む。また、数141に示す要素c3で1個のGTの要素を含む。つまり、暗号文ctx→は、nについて定数サイズである。また、実施の形態2で説明した非零内積暗号方式では、復号処理Decアルゴリズムは、数144に示すec0,k0で5個と、Πj=14eC1,j,DjeC2,j,Kjnで8個との合計13個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。実施の形態3.実施の形態3では、秘密鍵のサイズを定数サイズとした非零内積暗号方式について説明する。鍵生成装置100、暗号化装置200、復号装置300の構成は、それぞれ図3、図4、図5に示す実施の形態2に係る鍵生成装置100、暗号化装置200、復号装置300の構成と同一である。図10と図11とは、実施の形態3に係る鍵生成装置100の動作を示すフローチャートである。なお、図10は、実施の形態3に係るSetupアルゴリズムの処理を示すフローチャートであり、図11は、実施の形態3に係るKeyGenアルゴリズムの処理を示すフローチャートである。図12は、実施の形態3に係る暗号化装置200の動作を示すフローチャートであり、実施の形態3に係るEncアルゴリズムの処理を示すフローチャートである。図13は、実施の形態3に係る復号装置300の動作を示すフローチャートであり、実施の形態3に係るDecアルゴリズムの処理を示すフローチャートである。なお、以下の説明において、入力されるベクトルv→:=v1,...,vnは、L=1,...,n-1の各整数LについてvL≠0であり、入力されるベクトルx→:=x1,...,xnは、xn≠0であるとする。鍵生成装置100について説明する。図10に基づき、Setupアルゴリズムの処理について説明する。S201からS202までの処理は、図6に示すS101からS102までの処理と同じである。S203:基底B生成ステップ基底生成部113は、実施の形態2における基底B0と変数Bi,jと同様に、数149に示すように、処理装置により基底D0と変数Di,jと変数D’i,j,Lとを生成する。また、基底生成部113は、実施の形態2における基底B0と基底B1と同様に、数150に示すように、処理装置により基底D0と基底D1とを生成する。そして、基底生成部113は、基底D0を基底B0とし、基底D0を基底B0とし、基底D1を基底B1とする。また、基底生成部113は、i,j=1,...,4の各整数i,jと、L=1,...,nの各整数Lとについて、変数Di,jを変数Bi,jとし、変数D’i,j,Lを変数B’i,j,Lとする。S204:基底B^生成ステップ鍵生成部114は、数151に示すように、処理装置により基底B^0と、基底B^1と、基底B^0とを生成する。S205:マスター鍵生成ステップ鍵生成部114は、処理装置により公開パラメータpk:=1λ,paramn,{B^t}t=0,1とし、マスター秘密鍵sk:=B^0,{Bi,j,B’i,j,L}i=1,3;j=1,...,4;L=1,...,nとする。そして、鍵生成部114は、公開パラメータpkと、マスター秘密鍵skとをマスター鍵記憶部120に記憶する。なお、paramn:={paramVt}t=0,1,gTである。つまり、S201からS205において、鍵生成装置100は、数152に示すアルゴリズムG2obを用いた、数153に示すSetupアルゴリズムを実行して、公開パラメータpkとマスター秘密鍵skとを生成する。ここで、数152に示すように、アルゴリズムG2obは、数131に示すアルゴリズムG1obを用いる。なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置200や復号装置300が取得可能な状態にされる。図11に基づき、KeyGenアルゴリズムの処理について説明する。S211からS213までの処理は、図7に示すS111からS113までの処理と同じである。S214:要素K生成ステップ鍵要素生成部142は、数154に示すように、処理装置により復号鍵skv→の要素である要素K1,jと要素K2,jとを生成する。S215:鍵配布ステップ鍵配布部150は、S211で入力したベクトルv→と、S213で生成した要素k0と、S214で生成した要素K1,j,K2,jとを要素とする復号鍵skv→を、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skv→は、他の方法により復号装置300へ配布されてもよい。つまり、S211からS214において、鍵生成装置100は、数155に示すKeyGenアルゴリズムを実行して、復号鍵skv→を生成する。そして、S215において、鍵生成装置100は、生成された復号鍵skv→を復号装置300へ配布する。暗号化装置200について説明する。図12に基づき、Encアルゴリズムの処理について説明する。S221からS224までの処理は、図8に示すS121からS124までの処理と同じである。S225:要素c1生成ステップ暗号要素生成部232は、数156に示すように、処理装置により暗号文ctx→の要素である要素c1を生成する。数156は、数135と同様に、基底B1の基底ベクトルb1,1,...,b1,nの係数としてωx1,...,ωxnを設定し、基底ベクトルb1,n1,...,b1,3nの係数として0を設定し、基底ベクトルb1,3n1,...,b1,4nの係数としてη1x1,...,η1xnを設定することを意味する。S226の処理は、図8に示すS126の処理と同じである。S227:データ送信ステップデータ送信部240は、S222で入力したベクトルx→と、S224で生成した要素c0と、S225で生成した要素c1と、S226で生成した要素c3とを要素とする暗号文ctx→を、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号文ctx→は、他の方法により復号装置300へ送信されてもよい。つまり、S221からS226において、暗号化装置200は、数157に示すEncアルゴリズムを実行して、暗号文ctx→を生成する。そして、S227において、暗号化装置200は、生成された暗号文ctx→を復号装置300へ送信する。復号装置300について説明する。図13に基づき、Decアルゴリズムの処理について説明する。S231からS232までの処理は、図9に示すS131からS132までの処理と同じである。S233:値Dj計算ステップペアリング演算部330は、数158に示すように、処理装置により値Djを計算する。ここで、要素c1は、C1,...,C4n∈G4nの4n組に分解される。S234:ペアリング演算ステップペアリング演算部330は、数159に示すように、処理装置によりペアリング演算を実行して、値Fを計算する。S235の処理は、図9に示すS135の処理と同じである。つまり、S231からS235において、復号装置300は、数160に示すDecアルゴリズムを実行して、メッセージm’を計算する。なお、B1:=b1,1,...,b1,4nは、{Bi,j,B’i,j,L}i,j=1,...,4;L=1,...,nによって特定される。また、Setupアルゴリズムの出力に含まれる{Bi,j,B’i,j,L}i=1,3;j=1,...,4;L=1,...,nは、B^1:=b1,1,...,b1,n,b1,2n1,...,b1,3nによって特定される。そして、Decアルゴリズムは、数161に示すDec’アルゴリズムのように記述することができる。実施の形態3で説明した非零内積暗号方式では、復号鍵skv→は、数135に示す要素k0で5個と、数154に示す、j=1,...,4の各整数jについての要素K1,j及び要素K2,jで8個との合計13個のGの要素を含む。つまり、復号鍵skv→は、nについて定数サイズである。また、実施の形態3で説明した非零内積暗号方式では、復号処理Decアルゴリズムは、数159に示すec0,k0で5個と、Πj=14eDj,K1,jeCjn,K2,jで8個との合計13個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。実施の形態4.実施の形態4では、暗号文のサイズを定数サイズとした零内積暗号方式について説明する。鍵生成装置100、暗号化装置200、復号装置300の構成は、それぞれ図3、図4、図5に示す実施の形態2に係る鍵生成装置100、暗号化装置200、復号装置300の構成と同一である。図14と図15とは、実施の形態4に係る鍵生成装置100の動作を示すフローチャートである。なお、図14は、実施の形態4に係るSetupアルゴリズムの処理を示すフローチャートであり、図15は、実施の形態4に係るKeyGenアルゴリズムの処理を示すフローチャートである。図16は、実施の形態4に係る暗号化装置200の動作を示すフローチャートであり、実施の形態4に係るEncアルゴリズムの処理を示すフローチャートである。図17は、実施の形態4に係る復号装置300の動作を示すフローチャートであり、実施の形態4に係るDecアルゴリズムの処理を示すフローチャートである。なお、以下の説明において、入力されるベクトルx→:=x1,...,xnは、L=1,...,n-1の各整数LについてxL≠0であり、入力されるベクトルv→:=v1,...,vnは、vn≠0であるとする。鍵生成装置100について説明する。図14に基づき、Setupアルゴリズムの処理について説明する。S301:空間生成ステップ空間生成部111は、セキュリティパラメータ1λを入力として、処理装置によりGbpgを実行して、対称双線形ペアリング群のパラメータparamG:=q,G,GT,g,eを生成する。さらに、空間生成部111は、N:=4n1を設定する。そして、空間生成部111は、セキュリティパラメータ1λと、Nと、対称双線形ペアリング群のパラメータparamGとを入力として、処理装置によりGdpvsを実行して、双対ペアリングベクトル空間のパラメータparamVt:=q,V,GT,A,eを生成する。S302:線形変換生成ステップ行列生成部112は、数162に示すように、処理装置により線形変換Xを生成する。数162におけるL’N,Fqは、数163に示す通りである。なお、以下、{χ0,0,χ0,j,χi,0,L,μi,j,μ’i,j,L}i,j=1,...,4;L=1,...,nは、線形変換Xにおける定数値0以外の要素を示す。S303:基底B生成ステップ基底生成部113は、数164に示すように、処理装置により変数B0,0と変数B0,jと変数Bi,0,Lと変数Bi,jと変数B’i,j,Lとを生成する。また、基底生成部113は、数165に示すように、処理装置により基底Bを生成する。S304:基底B^生成ステップ鍵生成部114は、数166に示すように、処理装置により基底B^を生成する。S305:マスター鍵生成ステップ鍵生成部114は、処理装置により公開パラメータpk:=1λ,paramn,B^0,{B0,0,B0,j,Bi,0,L,Bi,j,B’i,j,L}i=1,4;j=1,...,4;L=1,...,nとし、マスター秘密鍵sk:=B^とする。そして、鍵生成部114は、公開パラメータpkと、マスター秘密鍵skとをマスター鍵記憶部120に記憶する。なお、paramn:=paramV,gTである。つまり、S301からS305において、鍵生成装置100は、数167に示すアルゴリズムG3obを用いた、数168に示すSetupアルゴリズムを実行して、公開パラメータpkとマスター秘密鍵skとを生成する。なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置200や復号装置300が取得可能な状態にされる。図15に基づき、KeyGenアルゴリズムの処理について説明する。S311の処理は、図7に示すS111の処理と同じである。S312:乱数生成ステップ乱数生成部141は、数169に示すように、処理装置により乱数を生成する。S313:要素k生成ステップ鍵要素生成部142は、数170に示すように、処理装置により復号鍵skv→の要素である要素kを生成する。数170は、数135と同様に、基底Bの基底ベクトルb0の係数として1を設定し、基底ベクトルb1,...,bnの係数としてδv1,...,δvnを設定し、基底ベクトルbn1,...,b2nの係数として0を設定し、基底ベクトルb2n1,...,b3nの係数としてφv1,...,φvnを設定し、基底ベクトルb3n1,...,b4nの係数として0を設定することを意味する。S314:鍵配布ステップ鍵配布部150は、S313で生成した要素kを要素とする復号鍵skv→を、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skv→は、他の方法により復号装置300へ配布されてもよい。つまり、S311からS313において、鍵生成装置100は、数171に示すKeyGenアルゴリズムを実行して、復号鍵skv→を生成する。そして、S314において、鍵生成装置100は、生成された復号鍵skv→を復号装置300へ配布する。暗号化装置200について説明する。図16に基づき、Encアルゴリズムの処理について説明する。S321からS322までの処理は、図8に示すS121からS122までの処理と同じである。S323:乱数生成ステップ乱数生成部231は、数172に示すように、処理装置により乱数を生成する。S324:要素C生成ステップ暗号要素生成部232は、数173に示すように、処理装置により暗号文ctx→の要素である要素C0と要素C1,jと要素C2,jとを生成する。S325の処理は、図8に示すS126の処理と同じである。S326:データ送信ステップデータ送信部240は、S322で入力したベクトルx→と、S324で生成した要素C0,C1,j,C2,jと、S325で生成した要素c3とを要素とする暗号文ctx→を、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号文ctx→は、他の方法により復号装置300へ送信されてもよい。つまり、S321からS325において、暗号化装置200は、数174に示すEncアルゴリズムを実行して、暗号文ctx→を生成する。そして、S326において、暗号化装置200は、生成された暗号文ctx→を復号装置300へ送信する。復号装置300について説明する。図17に基づき、Decアルゴリズムの処理について説明する。S331からS332までの処理は、図9に示すS131からS132までの処理と同じである。S333:値Dj計算ステップペアリング演算部330は、数175に示すように、処理装置により値Djを計算する。ここで、要素kは、K0,...,K4n∈G4n1の4n1組に分解される。S334:ペアリング演算ステップペアリング演算部330は、数176に示すように、処理装置によりペアリング演算を実行して、値Fを計算する。S335の処理は、図9に示すS135の処理と同じである。つまり、S331からS335において、復号装置300は、数177に示すDecアルゴリズムを実行して、メッセージm’を計算する。なお、B:=b0,...,b4nは、{B0,0,B0,j,Bi,0,L,Bi,j,B’i,j,L}i,j=1,...,4;L=1,...,nによって特定される。また、Setupアルゴリズムの出力に含まれる{B0,0,B0,j,Bi,0,L,Bi,j,B’i,j,L}i=1,4;j=1,...,4;L=1,...,nは、B^:=b0,...,bn,b3n1,...,b4nによって特定される。そして、Decアルゴリズムは、数178に示すDec’アルゴリズムのように記述することができる。数179に示すように、Decアルゴリズムを用いた場合、x→v→=0であれば、F=gζTが得られる。そのため、c3=gζTmをFで除することにより、メッセージm’=mが得られる。実施の形態4で説明した零内積暗号方式では、暗号文ctx→は、数173に示す要素C0で1個と、j=1,...,4の各整数jについての要素C1,j及び要素C2,jで8個との合計9個のGの要素を含む。また、要素c3で1個のGTの要素を含む。つまり、暗号文ctx→は、nについて定数サイズである。また、実施の形態4で説明した零内積暗号方式では、復号処理Decアルゴリズムは、数176に示すeC0,K0で1個と、Πj=14eC1,j,DjeC2,j,Kjnで8個との合計9個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。実施の形態5.実施の形態5では、秘密鍵のサイズを定数サイズとした零内積暗号方式について説明する。鍵生成装置100、暗号化装置200、復号装置300の構成は、それぞれ図3、図4、図5に示す実施の形態2に係る鍵生成装置100、暗号化装置200、復号装置300の構成と同一である。図18と図19とは、実施の形態5に係る鍵生成装置100の動作を示すフローチャートである。なお、図18は、実施の形態5に係るSetupアルゴリズムの処理を示すフローチャートであり、図19は、実施の形態5に係るKeyGenアルゴリズムの処理を示すフローチャートである。図20は、実施の形態5に係る暗号化装置200の動作を示すフローチャートであり、実施の形態5に係るEncアルゴリズムの処理を示すフローチャートである。図21は、実施の形態5に係る復号装置300の動作を示すフローチャートであり、実施の形態5に係るDecアルゴリズムの処理を示すフローチャートである。なお、以下の説明において、入力されるベクトルv→:=v1,...,vnは、L=1,...,n-1の各整数LについてvL≠0であり、入力されるベクトルx→:=x1,...,xnは、xn≠0であるとする。鍵生成装置100について説明する。図18に基づき、Setupアルゴリズムの処理について説明する。S401からS402までの処理は、図14に示すS301からS302までの処理と同じである。S403:基底B生成ステップ基底生成部113は、実施の形態4における変数B0,0と変数B0,jと変数Bi,0,Lと変数Bi,jと変数B’i,j,Lと同様に、数180に示すように、処理装置により変数D0,0と変数D0,jと変数Di,0,Lと変数Di,jと変数D’i,j,Lとを生成する。また、基底生成部113は、実施の形態4における基底Bと同様に、数181に示すように、処理装置により基底Dを生成する。そして、基底生成部113は、基底Dを基底Bとする。また、基底生成部113は、i,j=1,...,4の各整数i,jと、L=1,...,nの各整数Lとについて、変数D0,0を変数B0,0とし、変数D0,jを変数B0,jとし、変数Di,0,Lを変数Bi,0,Lとし、変数Di,jを変数Bi,jとし、変数D’i,j,Lを変数B’i,j,Lとする。S404:基底B^生成ステップ鍵生成部114は、数182に示すように、処理装置により基底B^を生成する。S405:マスター鍵生成ステップ鍵生成部114は、処理装置により公開パラメータpk:=1λ,paramn,B^とし、マスター秘密鍵sk:={B0,0,B0,j,Bi,0,L,Bi,j,B’i,j,L}i=1,3;j=1,...,4;L=1,...,nとする。そして、鍵生成部114は、公開パラメータpkと、マスター秘密鍵skとをマスター鍵記憶部120に記憶する。なお、paramn:=paramV,gTである。つまり、S401からS405において、鍵生成装置100は、数183に示すアルゴリズムG4obを用いた、数184に示すSetupアルゴリズムを実行して、公開パラメータpkとマスター秘密鍵skとを生成する。ここで、数183に示すように、アルゴリズムG4obは、数167に示すアルゴリズムG3obを用いる。なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置200や復号装置300が取得可能な状態にされる。図19に基づき、KeyGenアルゴリズムの処理について説明する。S411からS412までの処理は、図15に示すS311からS312までの処理と同じである。S413:要素K生成ステップ鍵要素生成部142は、数185に示すように、処理装置により復号鍵skv→の要素である要素K0と要素K1,jと要素K2,jとを生成する。S414:鍵配布ステップ鍵配布部150は、S411で入力したベクトルv→と、S313で生成した要素K0,K1,j,K2,jとを要素とする復号鍵skv→を、例えば通信装置によりネットワークを介して秘密裡に復号装置300へ配布する。もちろん、復号鍵skv→は、他の方法により復号装置300へ配布されてもよい。つまり、S411からS413において、鍵生成装置100は、数186に示すKeyGenアルゴリズムを実行して、復号鍵skv→を生成する。そして、S414において、鍵生成装置100は、生成された復号鍵skv→を復号装置300へ配布する。暗号化装置200について説明する。図20に基づき、Encアルゴリズムの処理について説明する。S421からS423までの処理は、図16に示すS321からS323までの処理と同じである。S424:要素c生成ステップ暗号要素生成部232は、数187に示すように、処理装置により暗号文ctx→の要素である要素cを生成する。数187は、数135と同様に、基底Bの基底ベクトルb0の係数としてζを設定し、基底ベクトルb1,...,bnの係数としてωx1,...,ωxnを設定し、基底ベクトルbn1,...,b3nの係数として0を設定し、基底ベクトルb3n1,...,b4nの係数としてηx1,...,ηxnを設定することを意味する。S425の処理は、図16に示すS325の処理と同じである。S426:データ送信ステップデータ送信部240は、S422で入力したベクトルx→と、S424で生成した要素cと、S425で生成した要素c3とを要素とする暗号文ctx→を、例えば通信装置によりネットワークを介して復号装置300へ送信する。もちろん、暗号文ctx→は、他の方法により復号装置300へ送信されてもよい。つまり、S421からS425において、暗号化装置200は、数188に示すEncアルゴリズムを実行して、暗号文ctx→を生成する。そして、S426において、暗号化装置200は、生成された暗号文ctx→を復号装置300へ送信する。復号装置300について説明する。図21に基づき、Decアルゴリズムの処理について説明する。S431からS432までの処理は、図17に示すS331からS332までの処理と同じである。S433:値Dj計算ステップペアリング演算部330は、数189に示すように、処理装置により値Djを計算する。ここで、要素cは、C0,...,C4n∈G4n1の4n1組に分解される。S434:ペアリング演算ステップペアリング演算部330は、数190に示すように、処理装置によりペアリング演算を実行して、値Fを計算する。S435の処理は、図17に示すS335の処理と同じである。つまり、S431からS435において、復号装置300は、数191に示すDecアルゴリズムを実行して、メッセージm’を計算する。なお、B:=b0,...,b4nは、{B0,0,B0,j,Bi,0,L,Bi,j,B’i,j,L}i,j=1,...,4;L=1,...,nによって特定される。また、Setupアルゴリズムの出力に含まれる{B0,0,B0,j,Bi,0,L,Bi,j,B’i,j,L}i=1,3;j=1,...,4;L=1,...,nは、B^:=b0,...,bn,b2n1,...,b3nによって特定される。そして、Decアルゴリズムは、数192に示すDec’アルゴリズムのように記述することができる。実施の形態5で説明した零内積暗号方式では、復号鍵skv→は、数185に示す要素K0で1個と、j=1,...,4の各整数jについての要素K1,j及び要素K2,jで8個との合計9個のGの要素を含む。つまり、復号鍵skv→は、nについて定数サイズである。また、実施の形態5で説明した零内積暗号方式では、復号処理Decアルゴリズムは、数190に示すeC0,K0で1個と、Πj=14eDj,K1,jeCjn,K2,jで8個との合計9個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。なお、以上の実施の形態では、図2bに示す線形変換Xを用いた。しかし、線形変換Xは、図2bに示すものに限らない。例えば、図2bにおける斜線が入れられた四角が示す部分をそれぞれ異なる値としてもよい。また、図2bでは、N列における全ての成分を定数値0以外の乱数としたが、N列ではなく、他のいずれか少なくとも1列における全ての成分を定数値0以外の乱数としてもよい。より一般的には、線形変換Xは、各行各列に少なくとも1つは定数値0以外の値を有する疎行列であればよい。さらに、線形変換Xは、n行n列の行列である場合、定数値0以外の値として、少なくともn個の異なる値を有しているとよい。さらに、線形変換Xは、少なくとも1つの列における全ての成分が定数値0以外の値であるとよい。さらに、線形変換Xは、対角成分と、少なくとも1つの列における全ての成分が定数値0以外の値であるとよい。さらに、線形変換Xは、全ての成分が定数値0以外の値である列を除き、対角成分の値が同一であるとよい。このような線形変換Xを用いた場合であっても、従来の線形変換Xを用いた場合に比べ、公開パラメータと秘密鍵とのサイズは小さくなる。また、ユーザ鍵の生成や暗号化の処理の処理時間も短くなる。但し、線形変換Xの形式によっては、ペアリング演算の数を減らすことができない場合もある。以上の実施の形態では、ベクトル空間は、符号化部と、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための4つの直交する部分空間で構成した。そして、これに対応するため、数124に示すように、線形変換Xを、n行n列の行列Xi,ji,j=1,...,4を用いて構成した。線形変換Xのこの構成は、秘匿部と秘密鍵ランダム化部と暗号文ランダム化部との部分空間が、符号化部の部分空間と同じn次元であることを前提としている。しかし、秘匿部と秘密鍵ランダム化部と暗号文ランダム化部との部分空間は、符号化部の部分空間と同じn次元でなくてもよい。例えば、秘匿部の部分空間はn×u次元、秘密鍵ランダム化部の部分空間はn×w次元、暗号文ランダム化部の部分空間はn×z次元u,w,zは0以上の整数であってもよい。この場合、数193に示すように、線形変換Xを、n行n列の行列Xi,ji,j=1,...,1uwzを用いて構成すればよい。関数型暗号の一種として、IDベースレボケーションIdentity-BasedRevocation,IBRやIDベースブロードキャスト暗号Identity-BasedBroadcastEncryption,IBBEがある非特許文献1,5,6,8,19,12参照。IDベースレボケーションでは、暗号文は識別子の集合S=ID1,...,IDnに対して暗号化され、ID∈SでないIDと関連付けられた秘密鍵によって暗号文は復号される。つまり、復号には、ID∈Sでない場合に限り、RIBRID,S=1であることが必要である。IDベースブロードキャスト暗号では、暗号文は識別子の集合S=ID1,...,IDnに対して暗号化され、ID∈SであるIDと関連付けられた秘密鍵によって暗号文は復号される。つまり、復号には、ID∈Sである場合に限り、RIBBEID,S=1であることが必要である。S:={ID1,...,IDn}である場合に、SX:=Σi=0nviXi:=Πi=1nX-IDiとする。そして、ベクトルv→:=v0,v1,...,vnとし、ベクトルx→:=1,ID,...,IDnとする。すると、実施の形態2,3で説明した非零内積暗号方式は、IDベースレボケーション方式となり、実施の形態4,5で説明した零内積暗号方式は、IDベースブロードキャスト暗号方式となる。つまり、以上の実施の形態で説明した内積暗号方式により、IDベースレボケーション方式及びIDベースブロードキャスト暗号方式を実現できる。この場合においても、暗号文又は復号鍵をnについての定数サイズとすることができ、少ない数のペアリング演算で復号することができる。実施の形態2-4で説明した具体的な暗号方式以外にも、非特許文献13、15、16、17等で説明されている暗号方式に、上述した線形変換Xを適用することで、公開パラメータと秘密鍵とのサイズは小さくなる。また、ユーザ鍵の生成や暗号化の処理の処理時間も短くなる。図22は、実施の形態2-4で説明した非零内積暗号方式及び零内積暗号方式と、非特許文献2に記載された非零内積暗号方式及び零内積暗号方式とを比較した図である。なお、図22において、|G|、|GT|、|Fq|、P、Mは、それぞれGのサイズ、GTのサイズ、Fqのサイズ、ペアリング演算、Gにおけるスカラー積演算を示している。また、CT、SK、IP、DBDHは、それぞれ暗号文、秘密鍵復号鍵、内積、決定的双線形Diffie-Hellmanを示している。実施の形態6.以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。実施の形態6では、双対加群において暗号処理を実現する方法について説明する。つまり、以上の実施の形態では、素数位数qの巡回群において暗号処理を実現した。しかし、合成数Mを用いて数194のように環Rを表した場合、環Rを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。以上の実施の形態で説明したアルゴリズムにおけるFqをRに変更すれば、双対加群における暗号処理を実現することができる。次に、実施の形態における暗号処理システム10鍵生成装置100、暗号化装置200、復号装置300のハードウェア構成について説明する。図23は、鍵生成装置100、暗号化装置200、復号装置300、鍵委譲装置400のハードウェア構成の一例を示す図である。図23に示すように、鍵生成装置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等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。ファイル群924には、上記の説明において公開パラメータpk、マスター秘密鍵sk、復号鍵skv→、暗号文ctx→等の情報やデータや信号値や変数値やパラメータが、ファイルやデータベースの各項目として記憶される。ファイルやデータベースは、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出検索参照比較演算計算処理出力印刷表示などのCPU911の動作に用いられる。抽出検索参照比較演算計算処理出力印刷表示のCPU911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、その他光ディスク等の記録媒体やICチップに記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。また、上記の説明において~部として説明するものは、~回路、~装置、~機器、~手段、~機能であってもよく、また、~ステップ、~手順、~処理であってもよい。また、~装置として説明するものは、~回路、~機器、~手段、~機能であってもよく、また、~ステップ、~手順、~処理であってもよい。さらに、~処理として説明するものは~ステップであっても構わない。すなわち、~部として説明するものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子デバイス基板配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM913等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、上記で述べた~部としてコンピュータ等を機能させるものである。あるいは、上記で述べた~部の手順や方法をコンピュータ等に実行させるものである。"