"送信装置、N個の受信装置R1,...,RN、再暗号化装置、鍵生成手段を有するプロキシ再暗号化システムであって、Nは2以上の整数、nとmは1以上N以下の整数、λはセキュリティパラメータを示す整数、qはλビットの素数、GとGTは素数位数qの巡回乗算群、gは群Gの生成元、eはG×G→GTのように写像する双線形ペアリング関数、Hは群Gの元と群GTの元を入力とし所定のビット長の整数に写像するハッシュ関数を示す記号、g1,h,u,v,dはランダムに選択された群Gの生成元、xnを0以上q-1以下からランダムに選ばれた整数、^はべき乗を示す記号とし、前記送信装置は、受信装置Rnの公開鍵pknと平文Mとを取得すると、0以上q-1以下の整数からランダムにr,sを選び、Cn1=pknrCn2=hrCn3=eg,g1rMt=HCn2,Cn3Cn4=utvsdrCn5=sを生成し、Cn1,Cn2,Cn3,Cn4,Cn5が含まれる暗号文Cnを生成する暗号化部を備え、前記受信装置Rnは、skn=xnまたはskn=1/xn、pkn=g^sknの関係を有する秘密鍵sknと公開鍵pknを記録する復号記録部と、受信した暗号文CnからCn1,Cn2,Cn3,Cn4,Cn5を取得し、t=HCn2,Cn3を計算し、eh,Cn1=eCn2,pkneh,Cn4=eCn2,utv^Cn5dが成り立つ場合には、M=Cn3/eCn1,g1^1/sknを計算し、平文Mを求める復号部と、を備え、前記鍵生成手段は、受信装置Rnの秘密鍵sknと受信装置Rmただし、m≠nの秘密鍵skmを記録する鍵記録部と、再暗号化鍵rkm/nをrkm/n=skm/sknのように生成する再暗号化鍵生成部と、を備え、前記再暗号化装置は、再暗号化鍵rkm/nを記録する再暗号化記録部と、秘密鍵sknで復号できる暗号文Cnから、再暗号化鍵rkm/nを用いて秘密鍵skmで復号できる暗号文Cmを生成するときには、暗号文CnからCn1,Cn2,Cn3,Cn4,Cn5を取得し、t=HCn2,Cn3を計算し、eh,Cn1=eCn2,pkneh,Cn4=eCn2,utv^Cn5dが成り立つ場合には、Cm1=Cn1^rkm/nCm2=Cn2Cm3=Cn3Cm4=Cn4Cm5=Cn5の関係を有するCm1,Cm2,Cm3,Cm4,Cm5が含まれる暗号文Cmを生成する再暗号化部と、を備えるプロキシ再暗号化システム。請求項1記載のプロキシ再暗号化システムであって、前記再暗号化部は、秘密鍵skmで復号できる暗号文Cmから、再暗号化鍵rkm/nを用いて秘密鍵sknで復号できる暗号文Cnを生成するときには、暗号文CmからCm1,Cm2,Cm3,Cm4,Cm5を取得し、t=HCm2,Cm3を計算し、eh,Cm1=eCm2,pkmeh,Cm4=eCm2,utv^Cm5dが成り立つ場合には、Cn1=Cm1^1/rkm/nCn2=Cm2Cn3=Cm3Cn4=Cm4Cn5=Cm5の関係を有するCn1,Cn2,Cn3,Cn4,Cn5が含まれる暗号文Cnを生成することを特徴とするプロキシ再暗号化システム。受信装置Rnの秘密鍵sknで復号できる暗号文Cnと受信装置Rmただし、m≠nの秘密鍵skmで復号できる暗号文Cmとの間で再暗号化を行うための再暗号化鍵rkm/nを生成する鍵生成装置であって、秘密鍵sknと秘密鍵skmを記録する鍵記録部と、再暗号化鍵rkm/nをrkm/n=skm/sknのように生成する再暗号化鍵生成部と、を備える鍵生成装置。受信装置Rnの秘密鍵sknで復号できる暗号文Cnと受信装置Rmただし、m≠nの秘密鍵skmで復号できる暗号文Cmとの間で再暗号化を行う再暗号化装置であって、rkm/n=skm/sknである再暗号化鍵rkm/nを記録する再暗号化記録部と、秘密鍵sknで復号できる暗号文Cnから、再暗号化鍵rkm/nを用いて秘密鍵skmで復号できる暗号文Cmを生成するときには、暗号文CnからCn1,Cn2,Cn3,Cn4,Cn5を取得し、t=HCn2,Cn3を計算し、eh,Cn1=eCn2,pkneh,Cn4=eCn2,utv^Cn5dが成り立つ場合には、Cm1=Cn1^rkm/nCm2=Cn2Cm3=Cn3Cm4=Cn4Cm5=Cn5の関係を有するCm1,Cm2,Cm3,Cm4,Cm5が含まれる暗号文Cmを生成する再暗号化部と、を備える再暗号化装置。請求項4記載の再暗号化装置であって、前記再暗号化部は、秘密鍵skmで復号できる暗号文Cmから、再暗号化鍵rkm/nを用いて秘密鍵sknで復号できる暗号文Cnを生成するときには、暗号文CmからCm1,Cm2,Cm3,Cm4,Cm5を取得し、t=HCm2,Cm3を計算し、eh,Cm1=eCm2,pkmeh,Cm4=eCm2,utv^Cm5dが成り立つ場合には、Cn1=Cm1^1/rkm/nCn2=Cm2Cn3=Cm3Cn4=Cm4Cn5=Cm5の関係を有するCn1,Cn2,Cn3,Cn4,Cn5が含まれる暗号文Cnを生成することを特徴とする再暗号化装置。再暗号化装置、鍵生成手段を用いたプロキシ再暗号化方法であって、Nは2以上の整数、nとmは1以上N以下の整数、λはセキュリティパラメータを示す整数、qはλビットの素数、GとGTは素数位数qの巡回乗算群、gは群Gの生成元、eはG×G→GTのように写像する双線形ペアリング関数、Hは群Gの元と群GTの元を入力とし所定のビット長の整数に写像するハッシュ関数を示す記号、g1,h,u,v,dはランダムに選択された群Gの生成元、xn,r,sは0以上q-1以下からランダムに選ばれた整数、^はべき乗を示す記号とし、秘密鍵sknはskn=xnまたはskn=1/xn、公開鍵pknはpkn=g^sknの関係を有し、暗号文Cnは、Cn1=pknrCn2=hrCn3=eg,g1rMt=HCn2,Cn3Cn4=utvsdrCn5=sであるCn1,Cn2,Cn3,Cn4,Cn5を含んでおり、前記鍵生成手段が、再暗号化鍵rkm/nただし、m≠nをrkm/n=skm/sknのように生成する再暗号化鍵生成ステップと、前記再暗号化装置が、秘密鍵sknで復号できる暗号文Cnから、再暗号化鍵rkm/nを用いて秘密鍵skmで復号できる暗号文Cmを生成するときには、暗号文CnからCn1,Cn2,Cn3,Cn4,Cn5を取得し、t=HCn2,Cn3を計算し、eh,Cn1=eCn2,pkneh,Cn4=eCn2,utv^Cn5dが成り立つ場合には、Cm1=Cn1^rkm/nCm2=Cn2Cm3=Cn3Cm4=Cn4Cm5=Cn5の関係を有するCm1,Cm2,Cm3,Cm4,Cm5が含まれる暗号文Cmを生成する再暗号化ステップと、を有するプロキシ再暗号化方法。請求項6記載のプロキシ再暗号化方法であって、前記再暗号化部が、秘密鍵skmで復号できる暗号文Cmから、再暗号化鍵rkm/nを用いて秘密鍵sknで復号できる暗号文Cnを生成するときには、暗号文CmからCm1,Cm2,Cm3,Cm4,Cm5を取得し、t=HCm2,Cm3を計算し、eh,Cm1=eCm2,pkmeh,Cm4=eCm2,utv^Cm5dが成り立つ場合には、Cn1=Cm1^1/rkm/nCn2=Cm2Cn3=Cm3Cn4=Cm4Cn5=Cm5の関係を有するCn1,Cn2,Cn3,Cn4,Cn5が含まれる暗号文Cnを生成する逆向き再暗号化ステップも有することを特徴とするプロキシ再暗号化方法。請求項1または2に記載のプロキシ再暗号化システムを構成する前記送信装置、前記受信装置、前記再暗号化装置、前記鍵生成手段のいずれかとしてコンピュータを機能させるためのプログラム。しかしながら、非特許文献1の方式は、使い捨て署名を使用しているため、暗号文のサイズが大きい。非特許文献2の方式は、システムパラメータのサイズが非常に大きくなってしまう。本発明のプロキシ再暗号化システムは、従来技術と同じ安全性を確保しながら、使い捨て署名を用いず、システムパラメータや暗号文のサイズが小さい方式を提供することを目的とする。本発明のプロキシ再暗号化システムは、送信装置、N個の受信装置R1,...,RN、再暗号化装置、鍵生成手段を有する。ここで、Nは2以上の整数、nとmは1以上N以下の整数、λはセキュリティパラメータを示す整数、qはλビットの素数、GとGTは素数位数qの巡回乗算群、gは群Gの生成元、eはG×G→GTのように写像する双線形ペアリング関数、Hは群Gの元と群GTの元を入力とし所定のビット長の整数に写像するハッシュ関数を示す記号、g1,h,u,v,dはランダムに選択された群Gの生成元、^はべき乗を示す記号とする。送信装置は、暗号化部を備える。受信装置R1,...,RNは、それぞれ復号記録部と復号部を備える。鍵生成手段は、鍵記録部と再暗号化鍵生成部を備える。再暗号化装置は、再暗号化記録部と再暗号化部を備える。送信装置の暗号化部は、受信装置Rnの公開鍵pknと平文Mとを取得すると、0以上q-1以下の整数からランダムにr,sを選ぶ。そして、Cn1=pknrCn2=hrCn3=eg,g1rMt=HCn2,Cn3Cn4=utvsdrCn5=sを計算し、Cn1,Cn2,Cn3,Cn4,Cn5が含まれる暗号文Cnを生成する。受信装置Rnの復号記録部は、あらかじめ秘密鍵sknと公開鍵pknを記録する。なお、秘密鍵sknと公開鍵pknは、xnを0以上q-1以下からランダムに選ばれた整数とし、skn=xnまたはskn=1/xn、pkn=g^sknの関係を有する。また、秘密鍵sknと公開鍵pknは、受信装置Rn自身が生成してもよいし、信頼できる鍵生成装置が生成してもよい。復号部は、受信した暗号文CnからCn1,Cn2,Cn3,Cn4,Cn5を取得し、t=HCn2,Cn3を計算し、eh,Cn1=eCn2,pkneh,Cn4=eCn2,utv^Cn5dが成り立つかを確認する。そして、この条件が成り立つ場合には、M=Cn3/eCn1,g1^1/sknを計算し、平文Mを求める。鍵生成手段の鍵記録部は、受信装置Rnの秘密鍵sknと受信装置Rmただし、m≠nの秘密鍵skmを記録する。再暗号化鍵生成部は、再暗号化鍵rkm/nをrkm/n=skm/sknのように生成する。再暗号化装置の再暗号化記録部は、再暗号化鍵rkm/nを記録する。再暗号化部は、公開鍵pknを用いて暗号化された暗号文CnからCn1,Cn2,Cn3,Cn4,Cn5を取得し、t=HCn2,Cn3を計算し、eh,Cn1=eCn2,pkneh,Cn4=eCn2,utv^Cn5dが成り立つかを確認する。そして、この条件が成り立つ場合には、Cm1=Cn1^rkm/nCm2=Cn2Cm3=Cn3Cm4=Cn4Cm5=Cn5の関係を有するCm1,Cm2,Cm3,Cm4,Cm5が含まれる暗号文Cmを生成する。本発明のプロキシ再暗号化システムによれば、暗号文Cの中のCn4が署名の役割を果たすので、暗号文の正当性を保証できる。したがって、従来技術と同じ安全性を確保できる。また、使い捨て署名を用いておらず、システムパラメータや暗号文のサイズが従来技術に比べて小さい。以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。図1に実施例1のプロキシ再暗号化システムの構成例を示す。図2に実施例1のn番目の受信装置の公開鍵pknを用いて暗号化された暗号文Cnをn番目の受信装置が復号する場合の処理フローを示す。図3に実施例1のn番目の受信装置の公開鍵pknを用いて暗号化された暗号文Cnをm番目の受信装置が復号する場合の処理フローを示す。実施例1のプロキシ再暗号化システムは、ネットワーク1000で接続された送信装置100、N個の受信装置2011,...,201N、再暗号化装置300、鍵生成手段401を有する。ここで、Nは2以上の整数、nとmは1以上N以下の整数、λはセキュリティパラメータを示す整数、qはλビットの素数、GとGTは素数位数qの巡回乗算群、gは群Gの生成元、eはG×G→GTのように写像する双線形ペアリング関数、Hは群Gの元と群GTの元を入力とし所定のビット長の整数に写像するハッシュ関数を示す記号、g1,h,u,v,dはランダムに選択された群Gの生成元、^はべき乗を示す記号とする。送信装置は、暗号化記録部190、暗号化部110を備える。各受信装置201nは、秘密鍵公開鍵生成部210n、復号記録部290n、復号部220nを備える。鍵生成手段401は、鍵記録部490と再暗号化鍵生成部420を備える。再暗号化装置300は、再暗号化記録部390と再暗号化部310を備える。なお、鍵生成手段401は、受信装置2011,...,201Nの秘密鍵sk1,...,skNを鍵記録部490に安全に記録し、必要な計算に利用できる手段であればよく、方式を限定する必要はない。例えば、鍵生成手段401は、1つの信頼できる鍵生成装置でもよいし、秘密鍵sknを秘密分散して記録するような複数の装置から構成された秘密計算システムでもよいこの場合は鍵記録部490と再暗号化鍵生成部420も複数の装置に分散されて構成される。秘密計算システムの具体例としては、参考文献1千田浩司濱田浩気五十嵐大高橋克巳軽量検証可能3パーティ秘匿関数計算の再考InCSS2010などがある。まず、図2にしたがって、n番目の受信装置201nの公開鍵pknを用いて暗号化された暗号文Cnをn番目の受信装置201nが復号する場合の処理フローを説明する。受信装置201nの秘密鍵公開鍵生成部210nは、xnを0以上q-1以下の整数からランダムに選ぶ。秘密鍵公開鍵生成部210nは、秘密鍵sknをskn=xnまたはskn=1/xnとし、公開鍵pknをpkn=g^sknとするS211n。そして、秘密鍵sknと公開鍵pknを復号記録部290nに記録し、公開鍵pknを公開する。受信装置201nの公開鍵pknと暗号化の対象である平文Mは、送信装置100の暗号化記録部190に記録しておけばよい。そして、送信装置100の暗号化部110は、公開鍵pknと平文Mとを取得すると、0以上q-1以下の整数からランダムにr,sを選ぶ。そして、Cn1=pknrCn2=hrCn3=eg,g1rMt=HCn2,Cn3Cn4=utvsdrCn5=sを計算し、Cn1,Cn2,Cn3,Cn4,Cn5が含まれる暗号文Cnを生成しS410n、受信装置201nに送信する。受信装置201nの復号部220nは、受信した暗号文CnからCn1,Cn2,Cn3,Cn4,Cn5を取得し、t=HCn2,Cn3を計算し、eh,Cn1=eCn2,pkneh,Cn4=eCn2,utv^Cn5dが成り立つかを確認する。そして、この条件が成り立つ場合には、M=Cn3/eCn1,g1^1/sknを計算し、平文Mを求めるS221n。なお、上記の条件が成り立たない場合には、エラーを出力する。次に、図3にしたがって、n番目の受信装置201nの公開鍵pknを用いて暗号化された暗号文Cnをm番目の受信装置201mが復号する場合の処理フローを説明する。受信装置201nの秘密鍵公開鍵生成部210nは、xnを0以上q-1以下の整数からランダムに選ぶ。秘密鍵sknをskn=xnまたはskn=1/xnとし、公開鍵pknをpkn=g^sknとするS211n。そして、秘密鍵sknと公開鍵pknを復号記録部290nに記録し、公開鍵pknを公開する。また、受信装置201nは、秘密鍵sknを鍵生成手段401に送信する。さらに、受信装置201mただし、m≠nの秘密鍵公開鍵生成部210mは、xmを0以上q-1以下の整数からランダムに選ぶ。秘密鍵skmをskm=xmまたはskm=1/xmとし、公開鍵pkmをpkm=g^skmとするS211m。そして、秘密鍵skmと公開鍵pkmを復号記録部290mに記録し、公開鍵pkmを公開する。また、受信装置201mは、秘密鍵skmを鍵生成手段401に送信する。鍵生成手段401の鍵記録部490は、受信した受信装置201nの秘密鍵sknと受信装置201mの秘密鍵skmを記録する。このときに、受信装置201nは、秘密鍵sknを鍵生成手段401にそのまま記録させてもよいし、鍵生成手段401に対して秘密鍵sknを秘匿できるように秘密分散して送信し、秘密分散された秘密鍵sknの断片を記録させてもよい。送信装置100の暗号化部110は、公開鍵pknと平文Mとを取得すると、0以上q-1以下の整数からランダムにr,sを選ぶ。そして、Cn1=pknrCn2=hrCn3=eg,g1rMt=HCn2,Cn3Cn4=utvsdrCn5=sを計算し、Cn1,Cn2,Cn3,Cn4,Cn5が含まれる暗号文Cnを生成しS410n、再暗号化装置300に送信する。鍵生成手段401の再暗号化鍵生成部420は、再暗号化鍵rkm/nをrkm/n=skm/sknのように生成するS421m/n。そして、再暗号化装置300に再暗号化鍵rkm/nを送信する。再暗号化装置300の再暗号化記録部390は、再暗号化鍵rkm/nを記録する。なお、ステップS410nとステップS421m/nの順番は逆でもよい。例えば、再暗号化装置300が、暗号文Cnを受信した後で、鍵生成手段401に再暗号化前の受信装置の番号nと再暗号化の後の受信装置の番号mを送って再暗号化鍵の生成を依頼し、鍵生成手段401が再暗号化鍵rkm/nを生成するのであれば、ステップS410n、ステップS421m/nの順番になる。一方、鍵生成手段401が、秘密鍵skn,skmを受信したときに再暗号化鍵rkm/nを生成しておくのであれば、ステップS421m/n、ステップS410nの順番になる。再暗号化部310は、再暗号化鍵rkm/nを用いて、秘密鍵sknで復号できる暗号文Cn公開鍵pknで暗号化された暗号文Cnまたは再暗号化によって生成された暗号文Cnから秘密鍵skmで復号できる暗号文Cm公開鍵pkmで暗号化されたのと同等な暗号文Cmを生成するときには、次のように再暗号化する。まず、受信した暗号文CnからCn1,Cn2,Cn3,Cn4,Cn5を取得し、t=HCn2,Cn3を計算し、eh,Cn1=eCn2,pkneh,Cn4=eCn2,utv^Cn5dが成り立つかを確認する。そして、この条件が成り立つ場合には、Cm1=Cn1^rkm/nCm2=Cn2Cm3=Cn3Cm4=Cn4Cm5=Cn5の関係を有するCm1,Cm2,Cm3,Cm4,Cm5が含まれる暗号文Cmを生成するS310。なお、上記の条件が成り立たない場合には、エラーを出力する。また、再暗号化鍵rkm/nを用いて、秘密鍵skmで復号できる暗号文Cm公開鍵pkmで暗号化された暗号文Cmまたは再暗号化によって生成された暗号文Cmから秘密鍵sknで復号できる暗号文Cn公開鍵pknで暗号化されたのと同等な暗号文Cnを生成するときには、再暗号化部310は、次のように再暗号化すればよい。受信した暗号文CmからCm1,Cm2,Cm3,Cm4,Cm5を取得する。そして、t=HCm2,Cm3を計算し、eh,Cm1=eCm2,pkmeh,Cm4=eCm2,utv^Cm5dが成り立つかを確認する。そして、この条件が成り立つ場合には、Cn1=Cm1^1/rkm/nCn2=Cm2Cn3=Cm3Cn4=Cm4Cn5=Cm5の関係を有するCn1,Cn2,Cn3,Cn4,Cn5が含まれる暗号文Cnを生成しS310、受信装置201mに送信する。受信装置201mの復号部220mは、受信した暗号文CmからCm1,Cm2,Cm3,Cm4,Cm5を取得し、t=HCm2,Cm3を計算し、eh,Cm1=eCm2,pkmeh,Cm4=eCm2,utv^Cm5dが成り立つかを確認する。そして、この条件が成り立つ場合には、M=Cm3/eCm1,g1^1/skmを計算し、平文Mを求めるS221m。なお、上記の条件が成り立たない場合には、エラーを出力する。[変形例]実施例1では、秘密鍵公開鍵生成部を各受信装置が備えたが、変形例では鍵生成手段が備える場合を示す。この場合は、鍵生成手段を、例えば信頼できる鍵生成装置にすればよい。図4に変形例のプロキシ再暗号化システムの構成例を示す。図5に変形例のn番目の受信装置の公開鍵pknを用いて暗号化された暗号文Cnをn番目の受信装置が復号する場合の処理フローを示す。図6に変形例のn番目の受信装置の公開鍵pknを用いて暗号化された暗号文Cnをm番目の受信装置が復号する場合の処理フローを示す。変形例のプロキシ再暗号化システムは、ネットワーク1000で接続された送信装置100、N個の受信装置2021,...,202N、再暗号化装置300、鍵生成手段402を有する。実施例1との構成上の違いは、受信装置202nが秘密鍵公開鍵生成部を備えておらず、鍵生成手段402が秘密鍵公開鍵生成部410を備えている点だけである。まず、図5にしたがって、n番目の受信装置202nの公開鍵pknを用いて暗号化された暗号文Cnをn番目の受信装置202nが復号する場合の処理フローを説明する。鍵生成手段402の秘密鍵公開鍵生成部410は、xnを0以上q-1以下の整数からランダムに選ぶ。秘密鍵公開鍵生成部410は、秘密鍵sknをskn=xnまたはskn=1/xnとし、公開鍵pknをpkn=g^sknとするS412n。そして、秘密鍵sknと公開鍵pknを鍵記録部490に記録し、公開鍵pknを公開し、秘密鍵sknを受信装置201nに送信する。受信装置202nは、秘密鍵sknと公開鍵pknを復号記録部290nに記録する。このように、変形例の場合も、復号記録部290nに秘密鍵sknと公開鍵pknが記録される。この状態は、実施例1のステップS211nが終了した状態と同じである。この後の処理は実施例1と同じなので説明を省略する。次に、図6にしたがって、n番目の受信装置の公開鍵pknを用いて暗号化された暗号文Cnをm番目の受信装置が復号する場合の処理フローを説明する。鍵生成手段402の秘密鍵公開鍵生成部410は、xnを0以上q-1以下の整数からランダムに選ぶ。秘密鍵公開鍵生成部410は、秘密鍵sknをskn=xnまたはskn=1/xnとし、公開鍵pknをpkn=g^sknとするS412n。そして、秘密鍵sknと公開鍵pknを鍵記録部490に記録し、公開鍵pknを公開し、秘密鍵sknを受信装置202nに送信する。受信装置202nは、秘密鍵sknと公開鍵pknを復号記録部290nに記録する。なお、この処理フローの場合、受信装置202nは処理を行わないので、鍵生成手段402が秘密鍵sknを受信装置202nに送信する処理と、受信装置202nが秘密鍵sknと公開鍵pknを記録する処理とが実行されていなくても、図6の処理フローは進めることができる。秘密鍵公開鍵生成部410は、xmを0以上q-1以下の整数からランダムに選ぶ。秘密鍵公開鍵生成部410は、秘密鍵skmをskm=xmまたはskm=1/xmとし、公開鍵pkmをpkm=g^skmとするS412m。そして、秘密鍵skmと公開鍵pkmを鍵記録部490に記録し、公開鍵pkmを公開し、秘密鍵skmを受信装置202mに送信する。受信装置202mは、秘密鍵skmと公開鍵pkmを復号記録部290mに記録する。ここまでの処理で、受信装置202mの復号記録部290mに秘密鍵skmと公開鍵pkmが記録され、鍵生成手段402の鍵記録部490に秘密鍵sknと秘密鍵skmが記録された状態となる。つまり、実施例1のステップS211mが終了した状態と同じである。この後の処理は実施例1と同じなので説明は省略する。実施例1と変形例1が相違する部分は、本発明を実行するための準備の部分である。つまり、本発明は、何らかの方法で、受信装置が自己の秘密鍵を記録し、鍵生成手段が複数の受信装置の秘密鍵を記録し、受信装置の公開鍵が公開された状態にすれば実行可能である。つまり、この状態にするまでの方法は、限定する必要がない。以下に、本発明の効果について説明する。なお、実施例1と変形例の効果は同じである。図7に、従来技術と本発明との比較表を示す。なお、|Zq|は0以上q-1以下の整数で形成される群Zqの要素サイズ、|G|は群Gの要素サイズ、|GT|は群GTの要素サイズ、|H|はハッシュ関数の記述長、nhはハッシュ関数の出力長、|vk|,|Sig|はそれぞれ使い捨て署名の検証鍵のサイズと署名のサイズを示している。図7に示すように、本発明のプロキシ再暗号化システムによれば、使い捨て署名を用いておらず、非特許文献2の方式よりもシステムパラメータのサイズが小さく、非特許文献1の方式よりも暗号文のサイズが小さい。本発明のプロキシ再暗号化システムによれば、暗号文Cの中のCn4が署名の役割を果たすので、後述の安全性の証明で示すように暗号文の正当性を保証できる。したがって、従来技術と同じ安全性を確保できる。また、本発明のプロキシ再暗号化システムによれば、再暗号化鍵rkm/nがrkm/n=skm/sknのように生成されるので、再暗号化鍵を繰返し乗算することで別の再暗号化鍵を生成できる。具体的には、n番目の受信装置201nで復号できる暗号文Cnからm番目の受信装置201mで復号できる暗号文Cmに再暗号化するための再暗号化鍵rkm/nと、m番目の受信装置201mで復号できる暗号文Cmからi番目の受信装置201iで復号できる暗号文Ciに再暗号化するための再暗号化鍵rki/mとがある場合に、rki/n=rki/mrkm/nのように再暗号化鍵を乗算するだけでrki/nn番目の受信装置201nで復号できる暗号文Cnからi番目の受信装置201iで復号できる暗号文Ciに再暗号化するための再暗号化鍵を生成できる。この方法の場合、3つ以上の再暗号化鍵を乗算することも可能である。また、1/rkm/nのように逆数にするだけで、逆方向の再暗号化鍵rkn/mになる。したがって、再暗号化を繰り返すことや双方向の再暗号化が容易である。[安全性の証明]定理:もしDBDH仮定が成立し、ハッシュ関数が標的衝突困難ハッシュ関数ならば、方式Σは標準モデルでIND-biPRE-CCA2安全な双方向プロキシ再暗号方式である。略証:DBDH仮定と等価なmDBDH仮定を用いる。Σの攻撃者Aがオラクルに質問する回数をqOとする。どのようなPPTAに対してもあるPPTBが存在してが成立することを示す。mDBDH問題を解くPPTBはg,ga,gb,gc,Qを入力として受け取り、Qがeg,gab/cかランダムなGTの元か判定したい。BはIND-bi-CCA2安全性を破る攻撃者Aを利用するためにシステムパラメータを準備し、各オラクルのシミュレーションを行う。最初にシステムパラメータを以下のように設定する。Setup:入力g,ga,gb,gc,Qを受け取ると0以上q-1以下の整数ωを選び、h=gaωを計算する。次にg1=gaとして、さらに0以上q-1以下の整数xv,xd,yu,yv,ydを選び、u=ggc^yuv=g^xvgc^yvd=g^xdgc^ydを計算してPP=G,GT,e,q,g,g1,h,u,v,dとする。鍵生成、再暗号鍵生成、再暗号化、復号オラクルのシミュレーションを以下のように行う。なおアスタリスクが付いた文字はチャレンジ暗号文の要素であることを示す。KeyGeneration:0以上q-1以下の整数xiを選び、ユーザiがuncorruptedならpki=gc^xiを返し,corruptedならski=xipki=g^xiとしてpki,skiを返す。ReKeyGeneration:i,jを受け取ると、もしユーザiとユーザjの一方がuncorruptedでもう一方がcorruptecdならば何も返さない。そうでなければxj/xiを返す。Decryption:pkiとC=C1,C2,C3,C4,C5を受け取ると以下を実行する。1.checkC=1を検証する。成立しないならエラーを出力する。2.C2,C3≠C2,C3かつt=tを検証する。成立するならシミュレーションを中止しランダムなビットを出力する。3.tsxvxd=0を検証する。成立するならシミュレーションを中止しランダムなビットを出力する。なお。DO2の場合,上記2の判定は行わない。これまでの検証に合格している場合、ある0以上p-1以下の整数rが存在してC1=pki^rC4=utvsdrt=HC2,C3s=C5という形になっているcheckC=1が成立するため。このときpkiはuncorruptedユーザの鍵でありC1^xi=g^crが成立する。したがって、α=C1^tyusyvyd/xi=g^crtyusyvydが計算できる。システムパラメータの設定よりC4=utvsdr=g^rtsxvxdctyusyvydと書けるため、τ=C4/α=g^rtsxvxdとすればτ^1/tsxvxd=grを得ることができる。これを用いてm’=C3/egr,g1を計算して返す。ReEncryption:暗号文C=C1,C2,C3,C4,C5を受け取ると以下を実行する。1.ユーザi,jが共にuncorruptedならxj/xiを再暗号化鍵としてReEncを実行し、C’=ReEncxj/xi,Cを返す。2.ユーザiがcorrupted、ユーザjがuncorruptedならpki=g^xi,pkj=g^cxjとなっているため、C1’=C2^xj/ω=hr^xj/ω=g^crxj=pkjrとしてC’=C1’,C2,C3,C4,C5を返す。3.ユーザiがuncorrupted、ユーザjがcorruptedならpki=g^cxi,pkj=g^xjとなっているため、復号オラクルのシミュレーションと同様の方法でgrを得てC1’=gr^xj=pkjrとし、C’=C1’,C2,C3,C4,C5を返す。IND-biPRE-CCA2の攻撃者Aがi,m0,m1を出力すると以下のようにチャレンジ暗号文を生成する。Challenge:{0,1}からランダムにσを選び、C1=gb^xi=g^cxi=pkib/cC2=gbω=hb/cC3=Qmσt=HC2,C3s=-txd/xvC4=gb^tyusyvyd=gb/c^tsxvxdctyusyvyd=u^tvdb/cを計算する。以上がBによるシミュレーションの記述である。最終的にAはσ’を出力し、このときBはσ’=σならば1を出力Q=eg,gab/cと判定し、そうでなければ0を出力Qはランダムと判定する。復号オラクルDecryptionのシミュレーションにおいて、2番目の条件によって中止する確率は高々AdvATCRλである。また、攻撃者Aがtsxvxd=0を満たす暗号文C=C1,C2,C3,C4,sを質問しない限り、再暗号化オラクルと復号オラクルを完全にシミュレート可能である。チャレンジ暗号文からtsxvxd=0という情報が得られるが、攻撃者Aはxv,xdの情報を得られないためtsxvxd=0が成立する確率は高々1/pしかない。よって3番目の条件によって中止する確率は高々qO/qである。Q=eg,gab/cの場合、IND-biPRE-CCA2ゲームを完全にシミュレートしており、が成立する証明終。[プログラム、記録媒体]上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"