"hをハッシュ関数、Em,rを整数rを用いてメッセージmを暗号化して暗号文を生成しその生成された暗号文から上記メッセージmの情報を漏洩しない暗号化関数、Em,hmを暗号文cとして、上記暗号文cを、上記暗号化関数Eに対応する復号関数Dで受信した暗号文cを復号可能でありその復号結果m’を出力する復号装置に送信する送信部と、上記復号装置から上記復号結果m’を受信する受信部と、上記復号結果m’を用いて検証情報Em’,hm’を計算する検証情報生成部と、上記暗号文cと上記検証情報Em’,hm’とが一致するか判定する判定部と、を含む復号結果検証装置。請求項1の復号結果検証装置において、p,qを素数、N=pq、N2を公開鍵、p-1とq-1の最小公倍数であるλを秘密鍵、gをZ/N2Zの可逆元として、上記暗号化関数Em,rは、gmrNmodN2であり、上記復号関数Dは、下記式により定義されるm’の値を計算する関数である、w=gλmodN2z=w-1/Nμ=z-1modNu=cλmodN2v=u-1/Nm’=vμmodN復号結果検証装置。請求項1の復号結果検証装置において、Gを巡回群、gを群Gの生成元、所定の整数sを秘密鍵、y=gsを公開鍵として、上記暗号化関数Em,rは、c0=myr及びc1=grを出力する関数であり、上記暗号文cは、第一暗号文c0=myhm及び第二暗号文c1=ghmであり、上記復号関数Dは、c0c1-sであり、上記検証情報生成部は、第一検証情報c0’=m’yhm’及び第二検証情報c1’=ghm’を計算し、上記判定部は、上記第一暗号文c0と上記第一検証情報c0’とが一致するか、及び、上記第一暗号文c1と上記第一検証情報c1’とが一致するかを判定する、復号結果検証装置。hをハッシュ関数、Em,rを整数rを用いてメッセージmを暗号化して暗号文を生成しその生成された暗号文から上記メッセージmの情報を漏洩しない暗号化関数、Em,hmを暗号文cとして、送信部が、上記暗号文cを、上記暗号化関数Eに対応する復号関数Dで受信した暗号文cを復号可能でありその復号結果m’を出力する復号装置に送信する送信ステップと、受信部が、上記復号装置から上記復号結果m’を受信する受信ステップと、検証情報生成部が、上記復号結果m’を用いて検証情報Em’,hm’を計算する検証情報生成ステップと、判定部が、上記暗号文cと上記検証情報Em’,hm’とが一致するか判定する判定ステップと、を含む復号結果検証方法。hをハッシュ関数、Em,rを整数rを用いてメッセージmを暗号化して暗号文を生成しその生成された暗号文から上記メッセージmの情報を漏洩しない暗号化関数、Em,hmを暗号文cとして、上記暗号化関数Eに対応する復号関数Dで受信した上記暗号文cを復号可能でありその復号結果m’を出力する復号装置と、上記暗号文cを上記復号装置に送信する送信部と、上記復号装置から上記復号結果m’を受信する受信部と、上記復号結果m’を用いて検証情報Em’,hm’を計算する検証情報生成部と、上記暗号文cと上記検証情報Em’,hm’とが一致するか判定する判定部と、を含む復号結果検証装置と、を含む復号結果検証システム。請求項1から3の何れかの復号結果検証装置の各部としてコンピュータを機能させるためのプログラム。背景技術に記載した技術では、メッセージmに確認情報Qmを付加したものが暗号化の対象となり、メッセージmのみを暗号化の対象とする場合と比較して、生成される暗号文の長さが長くなる可能性がある。この発明の課題は、暗号化の対象はメッセージmのままで、復号装置が復号のための計算を正しく行ったかどうかを検証可能な復号結果検証装置、方法、システム及びプログラムを提供することである。この発明の一態様による復号結果検証装置は、hをハッシュ関数、Em,rを整数rを用いてメッセージmを暗号化して暗号文を生成しその生成された暗号文からメッセージmの情報を漏洩しない暗号化関数として、Em,hmを暗号文cとして、暗号文cを、暗号化関数Eに対応する復号関数Dで受信した暗号文cを復号可能でありその復号結果m’を出力する復号装置に送信する送信部と、復号装置から復号結果m’を受信する受信部と、復号結果m’を用いて検証情報Em’,hm’を計算する検証情報生成部と、暗号文cと検証情報Em’,hm’とが一致するか判定する判定部と、を含む。暗号化関数が用いる整数としてメッセージmのハッシュ値hmを用いることにより、暗号化の対象はメッセージmのままで、復号装置が復号のための計算を正しく行ったかどうかを検証することができる。以下、図面を参照してこの発明の一実施形態を説明する。[記号の定義]まず、以下のように記号を定義する。mは、メッセージである。Em,rは、整数rを用いてメッセージmを暗号化して暗号文を生成しその生成された暗号文からメッセージmの情報を漏洩しない暗号化関数である。rは、例えば乱数である。例えば、Em,rを、確率的アルゴリズムにより記述された確率的公開鍵暗号の暗号化関数とする。Em,rは、所定の整数rを乱数の初期値として用いてもよい。暗号化関数Em,rの具体例は、後述する。hは、例えばランダム関数と見なすことができるSHA-256等の安全なハッシュ関数である。c=Em,hmは、暗号文である。Dは、Eに対応する公開鍵暗号方式における復号関数である。すなわち、任意のメッセージmに対してDEm=mである。[実施形態]この発明の一実施形態である復号結果検証装置1図1は、復号装置2に行わせた所定の計算の結果を用いて、暗号文cを復号する。その際、復号結果検証装置1は、復号装置2の計算結果が、正しく行われたかどうかを検証可能である。また、復号装置2が、メッセージmを改変したかどうかについても検証可能である。図1に示すように、復号結果検証装置1は、送信部11、受信部12、検証情報生成部13、判定部14、出力部15を例えば含む。また、この実施形態のアルゴリズムの概要を図3に示す。暗号文c=Em,hmは、暗号化装置0により生成されてステップe1、図2、復号結果検証装置1に送信される。復号結果検証装置1の送信部11は、暗号文cを復号装置2に送信するステップv1。復号装置2は、受信した暗号文cを復号関数Dで復号可能であり、その復号結果m’を出力するステップd1。復号装置2が正しく計算を行った場合には、復号結果m’=mとなる。しかし、復号装置2は、正しく計算を行わなくてもよい。この結果、復号結果m’≠mである復号結果m’が、復号結果検証装置1に送信されることもある。復号結果検証装置1の受信部12は、復号結果m’を復号装置2から受信するステップv2。受信した復号結果m’は、検証情報生成部13に送信される。復号結果検証装置1の検証情報生成部13は、復号結果m’を用いて検証情報Em’,hm’を計算するステップv3。計算された検証情報Em’,hm’は、判定部14に送信される。判定部14は、暗号文cと検証情報Em’,hm’とが一致するか判定するステップv4。判定結果は、出力部15に送信される。これらが一致していれば、復号装置2の計算結果は正しく、復号結果m’がmであると判断することができるステップv5。これらが一致していなければ、復号装置2の計算結果は正しくなく、復号結果m’はmでないと判断することができるステップv6。Em,rの定義から、生成された暗号文cからメッセージmの情報は漏洩しない。このため、復号装置2は、暗号文cと検証情報Em’,hm’とが一致するような、m’=mでない復号結果m’を生成することはできない。このため、上記のように判断することができるのである。復号結果m’がmであると判断することができた場合には、復号結果検証装置1の出力部15は、復号結果m’をmとして出力する。このように、暗号化関数Eが用いる整数としてメッセージmのハッシュ値hmを用いることにより、暗号化の対象はメッセージmのままで、復号装置が復号のための計算を正しく行ったかどうかを検証することができる。[暗号化関数及び復号関数の具体例1]いわゆるPailler暗号を用いて、暗号化関数E及び復号関数Dを構成することができる。この場合のアルゴリズムの概要を、図4に例示する。Pailler暗号については、例えば下記参考文献を参照のこと。参考文献PascalPaillierPublicKeyCryptosystemsBasedonCompositeDegreeResiduosityClassesADVANCESINCRYPTOLOGY―EUROCRYPT99LectureNotesinComputerScience1999Volume15921999pp223238p,qを素数、N=pq、N2を公開鍵、p-1とq-1の最小公倍数であるλを秘密鍵、gをZ/N2Zの可逆元として、暗号化関数Em,r=gmrNmodN2とする。すなわち、暗号文c=Em,hm=gmhmNmodN2となる。復号関数Dは、例えば次の5個の式により定義される。復号装置2は、ステップd1において、下記式により定義されるm’の値を計算して、復号結果として出力する。なお、下記式により定義されるm’の値の計算をするとは、その値を計算しさえすればその計算方法は問わないことを意味する。すなわち、その値を計算するために、数学的に等価な計算方法により計算してもよいことを意味する。w=gλmodN2z=w-1/Nμ=z-1modNu=cλmodN2v=u-1/Nm’=vμmodNハッシュ関数hをランダム関数とみなすことができて、識別合成剰余問題DecisionalCompositeResiduosityProblemが困難であるようにNやgが選ばれているならば、この具体例1の方式は安全である。識別合成剰余問題とは、秘密の数をaとして、乱数r1,r2についてgar1NmodN2とr2NmodN2を与えられたとき、それらを識別する問題である。mをある分布Mに従う確率変数によって定められるメッセージとする。hをランダム関数と見なすことができるならば、c=gmhmNmodN2は乱数r1についてc=gmr1NmodN2と識別困難である。もし、識別合成剰余問題が困難であれば、gmr1NmodN2は乱数r2についてr2NmodN2と識別困難である。したがって、cは、r2NmodN2と識別困難である。r2NmodN2はメッセージmの情報を含まないから、暗号文cからのメッセージmの情報は漏洩しない。例えば、Nの素因数分解が困難であれば識別合成剰余問題を効率良く解くアルゴリズムは知られておらず、識別合成剰余問題は困難であると考えられている。また、hとしてSHA-256などの安全なハッシュ関数を選べば、セキュリティパラメータkについて、Mがkビット以上のエントロピーを持つときに、Mから選んだmについてhmで与えられる分布を乱数と識別することは困難であるから、hをランダム関数とみなすことができる。[暗号化関数及び復号関数の具体例2]いわゆるElGamal暗号を用いて、暗号化関数E及び復号関数Dを構成することができる。この場合のアルゴリズムの概要を、図5に例示する。Gを巡回群、gを群Gの生成元、所定の整数sを秘密鍵、y=gsを公開鍵とする。暗号化関数Em,rを、c0=myr及びc1=grを出力する関数とする。すなわち、第一暗号文c0=myhm及び第二暗号文c1=ghmの組c0,c1が、暗号文cとなる。復号関数Dを、c0c1-sとする。復号結果検証装置1の検証情報生成部13は、ステップv3において、第一検証情報c0’=m’yhm’及び第二検証情報c1’=ghm’を計算し、この計算された第一検証情報c0’及び第二検証情報c1’の組c0’,c1’が検証情報となる。復号結果検証装置1の判定部14は、ステップv4において、第一暗号文c0と第一検証情報c0’とが一致するか、及び、第一暗号文c1と第一検証情報c1’とが一致するかを判定する。何れも一致すれば、暗号文cと検証情報とが一致すると判定する。少なくとも一方が一致しない場合には、暗号文cと検証情報とが一致しないと判定する。ハッシュ関数hをランダム関数とみなすことができて、識別Diffie-Hellman問題が困難であれば、この具体例2の方式は安全である。識別Diffie-Hellman問題とは、ランダムなa,b,cについて、組g,ga,gb,gabと組g,ga,gb,gcとを確率的多項式時間のアルゴリズムで識別する問題である。ランダム関数と見なすことができるハッシュ関数として例えばSHA-256が知られている。また、識別Diffie-Hellman問題が困難な群として、有限体の乗法群や、楕円曲線等の一般的なElGamal暗号に用いられる群がある。このとき、dを任意の整数として、組g,gs,ghm,gshmと組g,gs,ghm,gdとは識別困難である。このため、各組の4番目の要素をm倍した組g,gs,ghm,mgshmと組g,gs,ghm,mgdとも識別困難である。このことは、y=gsであることを考慮すると、g,gsを既知として、組myhm,ghmと組mgd,ghmとが識別困難であることと同義である。このため、組myhm,ghmの分布と組mgd,ghmの分布とは等しく、暗号文cである組myhm,ghmからメッセージmについての情報は得られない。このように、具体例2で定義した暗号化関数Eは、生成された暗号文からメッセージmの情報を漏洩しないという性質を満たす。[変形例等]復号結果検証装置1の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。"