"Gを可換群、EをGの元を平文とする公開鍵暗号方式における準同型性の暗号化関数、Bを集合S⊆Gを値域とし任意の0ではないx∈GについてSx∩Sの元で0ではないものを計算することが困難な関数、mをメッセージ、C=EBmを暗号文、IをGの元xを入力としてx=Bm’となるm’が存在する場合には真を出力する関数として、乱数r∈Gを生成する乱数生成部と、送信情報C0=Erを計算する送信情報生成部と、CC0を、上記暗号化関数Eを復号可能であり受信したCC0を復号しその復号結果dを出力する復号装置に送信する送信部と、上記復号装置から上記復号結果dを受信する受信部と、検証情報d’=d-rを計算する検証情報生成部と、Id’=真であるか判定する判定部と、を含む復号結果検証装置。請求項1の復号結果検証装置において、AをGの元を入力としてあるメッセージを出力する関数で任意のメッセージmに対してABm=mの性質を満たす関数として、Id’=真であれば、Ad’を出力する出力部を更に含む、復号結果検証装置。請求項1又は2の復号結果検証装置において、hをハッシュ関数、をビット結合として、上記Bm=mhmであることを特徴とする、復号結果検証装置。Gを可換群、EをGの元を平文とする公開鍵暗号方式における準同型性の暗号化関数、Bを集合S⊆Gを値域とし任意の0ではないx∈GについてSx∩Sの元で0ではないものを計算することが困難な関数、mをメッセージ、C=EBmを暗号文、IをGの元xを入力としてx=Bm’となるm’が存在する場合には真を出力する関数として、乱数生成部が、乱数r∈Gを生成する乱数生成ステップと、送信情報生成部が、送信情報C0=Erを計算する送信情報生成ステップと、送信部が、CC0を、上記暗号化関数Eを復号可能であり受信したCC0を復号しその復号結果dを出力する復号装置に送信する送信ステップと、受信部が、上記復号装置から上記復号結果dを受信する受信ステップと、検証情報生成部が、検証情報d’=d-rを計算する検証情報生成ステップと、判定部が、Id’=真であるか判定する判定ステップと、を含む復号結果検証方法。請求項1から3の何れかに記載の復号結果検証装置の各部としてコンピュータを機能させるためのプログラム。背景技術に記載した技術では、復号装置は依頼装置の判断を欺きながら、メッセージmを改変することが可能である。例えば、復号装置は、暗号文EmQmを復号したmQmから確認情報Qmを分離する。復号装置は、任意の改変されたメッセージm及びこのメッセージmに対応する確認情報Qmを生成する。例えば、mを構成するビットのうち何れか2つのビットの値を反転させたものをmとする。この場合、Qmの値とQmの値とは同じになる。復号装置は、mQmに代えてmQmを依頼装置に送信する。この場合、依頼装置は、受信したmQmを、メッセージmと確認情報Qmとに分離し、分離された確認情報Qmと、分離されたメッセージmから生成した確認情報Qmとが一致しているか判断するが、この値は一致してしまう。このようにして、復号装置は依頼装置の判断を欺きながら、メッセージmを改変することが可能である。言い換えれば、背景技術の依頼装置は、復号装置が復号のための計算を正しく行ったかどうかを検証することはできない。この発明の課題は、復号装置が復号のための計算を正しく行ったかどうかを検証可能な復号結果検証装置、方法及びプログラムを提供することである。この発明の一態様による復号結果検証装置は、Gを可換群、EをGの元を平文とする公開鍵暗号方式における準同型性の暗号化関数、Bを集合S⊆Gを値域とし任意の0ではないx∈GについてSx∩Sの元で0ではないものを計算することが困難な関数、mをメッセージ、C=EBmを暗号文、IをGの元xを入力としてx=Bm’となるm’が存在する場合には真を出力する関数として、乱数r∈Gを生成する乱数生成部と、送信情報C0=Erを計算する送信情報生成部と、CC0を、暗号化関数Eを復号可能であり受信したCC0を復号しその復号結果dを出力する復号装置に送信する送信部と、復号装置から復号結果dを受信する受信部と、d’=d-rを計算する検証情報生成部と、Id’=真であるか判定する判定部と、を含む。復号結果検証装置は、復号装置が復号のための計算を正しく行ったかどうかを検証することができる。以下、図面を参照してこの発明の一実施形態を説明する。[記号の定義]まず、以下のように記号を定義する。Gは、可換群である。なお、群の演算は、加法的に表記する。Eは、Gの元を平文とする公開鍵暗号方式における準同型性の暗号化関数である。Eは、準同型性の性質を有するため、任意のa∈G及び任意のb∈Gに対してEaEb=Eabである。Eは公開されており、復号結果検証装置1は関数Eの計算が可能であるとする。Dは、Eに対応する公開鍵暗号方式における復号関数である。すなわち、任意のy∈Gに対してDEy=yである。Bは、集合S⊆Gを値域とする関数である。また、Bは、任意の0ではないx∈GについてSx∩Sの元で0ではないものを計算することが困難な関数であるという性質を有する。mは、メッセージである。C=EBmは、復号の対象となる暗号文である。暗号文Cは、図示されていない暗号文生成装置により生成されたものである。Iは、Gの元xを入力としてx=Bm’となるm’が存在する場合には真を出力し、存在しない場合には偽を出力する関数である。Aは、Gの元を入力としてあるメッセージを出力する関数で任意のメッセージmに対してABm=mの性質を満たす関数である。hは、例えばSHA-256等の安全なハッシュ関数である。は、ビット結合である。[復号結果検証装置及び方法]この発明の一実施形態である復号結果検証装置1図1は、復号装置2に行わせた所定の計算の結果を用いて、暗号文EBmを復号する。その際、復号結果検証装置1は、復号装置2の計算結果が、正しく行われたかどうかを検証可能である。言い換えれば、復号装置2が、メッセージmを改変したかどうか検証可能である。図1に示すように、復号結果検証装置1は、乱数生成部11、送信情報生成部12、送信部13、受信部14、検証情報生成部15、判定部16、出力部17を例えば含む。復号結果検証装置1の乱数生成部11図1は、乱数r∈Gを生成するステップS1。生成された乱数rは、送信情報生成部12及び検証情報生成部15に送信される。復号結果検証装置1の送信情報生成部12は、乱数rを用いて、送信情報C0=Erを生成するステップS2。生成された送信情報C0は、送信部13に送信される。復号結果検証装置1の送信部13には、暗号文C=EBm及び送信情報C0が入力される。送信部13は、CC0を計算して、復号装置2に送信するステップS3。復号装置2は、CC0を受信する。復号装置2は、暗号化関数Eを復号可能であり、受信したCC0を復号し、その復号結果dを復号結果検証装置1に送信するステップS4。復号装置2は、具体的には、復号関数Dを用いて、CC0を復号する。Eの準同型性から、復号装置2の計算が正しく行われた場合には、復号結果d=DCC0=DEBmEr=DEBmr=Bmrとなる。復号結果検証装置1の受信部14は、復号結果dを受信するステップS5。受信部14は、受信した復号結果dを検証情報生成部15に送信する。復号結果検証装置1の検証情報生成部15は、復号結果d及び乱数rを用いて、検証情報d’=d-rを計算するステップS6。計算された’は、判定部16に送信される。判定部16は、Id’=真であるか判定するステップS7。すなわち、検証情報d’が、集合Sに属するかどうかを判定する。Id’=真であれば、復号装置2の復号結果dは正しいと判断することができる。その理由については後述する。この場合、判定部16は、検証情報d’を出力部17に送信する。検証情報d’を受信した出力部17は、Ad’を計算して出力するステップS8。この場合、Ad’=mとなる。Id’=真でなければ、復号装置2の復号結果dは正しいと判断することはできない。その理由については後述する。この場合、判定部16は、エラーが生じた旨の情報を出力する。このようにして、復号結果検証装置1は、復号装置2が復号のための計算を正しく行ったかどうかを検証することができる。[B,A及びIの具体例]例えば、Bm=mhmとすることができる。もし、このように定義されたBが、Bの性質を満たさなければ、hをランダムオラクルと識別することができるが、安全なハッシュ関数をランダムオラクルと識別するための実施可能なアルゴリズムは存在しないと考えられている。よって、このように定義されたBは、Bの性質を満たす。ハッシュ関数hの出力のビット長をLとすると、Aは、入力に対して下位Lビットを除いたビット列を出力する関数である。また、Id’は、dの下位Lビットと、d’の下位Lビット以外のビットのハッシュ値hAd’とが一致している場合に真を出力し、一致していない場合に偽を出力する関数である。[Id’の値に基づいて、復号装置2の復号結果dが正しいかどうか判断することができる理由]上記の実施形態のアルゴリズムは、次の<方式1>のように記述することができる。ここで、暗号文C=EBmである。機械Xは、上記実施形態の復号装置2に対応する。<方式1>1.乱数rを生成し、C0=Erを計算する。2.機械Xに暗号文CC0を入力し、機械Xから復号結果dを受信する。3.d’=d-rを計算する。4.Id’が真であれば、Adを出力する。そうでなければ、エラーを出力する。<方式1>において、機械Xが悪意を持って返答する可能性を考慮するときに、Id’が真でかつAd’がm以外となる事象を、Xによる攻撃が成功したと呼ぶことにする。以下では、機械Xによる攻撃が成功する確率を評価する。<方式1>において機械Xに送信する情報の暗号化を省略すると下記の<方式2>が得られる。機械Xが悪意を持って返答する可能性を考慮するときに、Id’が真でかつAd’がm以外となる事象を、機械Xによる攻撃が成功したと呼ぶことにする。<方式2>1.機械XにBmrを入力し、機械Xから復号結果dを受信する。2.d’=d-rを計算する。3.Id’が真であれば、Ad’を出力する。そうでなければ、エラーを出力する。記号rをr-Bmで置き換えると、次の<方式3>を得る。機械Xが悪意を持って返答する可能性を考慮するときに、Id’が真でかつAd’がm以外となる事象を、機械Xによる攻撃が成功したとよぶことにする。<方式3>1.機械Xに暗号文rを入力し、機械Xから復号結果dを受信する。2.d’=d-rBmを計算する。3.Id’が真であれば、Ad’を出力する。そうでなければ、エラーを出力する。任意のBmについて、乱数rとrBmの分布は等しいか、識別困難であるから、任意の機械Xについて、<方式2>において攻撃が成功する確率と<方式3>において攻撃が成功する確率は等しいまたは識別困難である。ここで、次の<方式4>を考える。機械Yが悪意を持って返答する可能性を考慮するときに、Id’が真でかつAd’がm以外となる事象を、機械Yによる攻撃が成功したとよぶことにする。<方式4>1.機械Yから復号結果dを受信する。2.d’=dBmを計算する。3.Id’が真であれば、Ad’を出力する。そうでなければ、エラーを出力する。さて、ある機械Xが存在して、<方式3>において攻撃が成功する確率がpXであるとする。機械Xをサブルーチンとして用いて外部の機械Mと通信する機械YXを次のように構成することができる。<YX>1.乱数rを生成し、機械Xに送信する。機械Xからdを受信する。2.d-rを計算し、機械Mに返信する。<方式4>を機械Mとみなして、<方式4>における機械Yを機械YXに置き換えると、置き換えて得られた方式の出力は<方式3>と等しい。したがって、機械Xが<方式3>の攻撃に成功する確率は、機械YXが<方式4>の攻撃に成功する確率と等しい。ところで、上記実施形態のBについての定義を仮定すると、任意の機械Yについて、機械Yが<方式4>の攻撃に成功する確率は無視できる。そのBについての定義とは、Bは次の性質を満たすとする:Bの値域をSとするとき、任意の0ではないx∈GについてSx∩Sの元で0ではないものを計算することは困難である。というものである。なぜならば、もし<方式4>の攻撃に成功するならばd≠0であり、Id’が真であるならば、Bm∈SについてBmd∈Sとなり、dを上記のx∈Gとみなせば、Bm∈Sx∩Sを計算できたことになるからである。したがって、任意の機械Xについて機械YXを機械Yとして用いれば、機械YXが<方式4>の攻撃に成功する確率は無視できる。機械Xが<方式3>の攻撃に成功する確率は、機械YXが<方式4>の攻撃に成功する確率と等しいから、任意の機械XについてpXは無視できる量である。<方式2>は<方式1>から公開鍵暗号による暗号化を取り去ったものであるから、任意の機械Xが<方式1>の攻撃に成功する確率は、機械Xが<方式2>の攻撃に成功する確率よりも小さい。よって、任意の機械Xが<方式1>の攻撃に成功する確率は無視できる量である。すなわち、復号装置2は復号結果検証装置1の判断を欺きながら、メッセージmを改変することはできない。言い換えれば、復号結果検証装置1は、復号装置2が復号のための計算を正しく行ったかどうかを検証することができる。[変形例等]乱数rは、復号装置2が知ることができない所定の整数であってもよい。復号結果検証装置1の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。"