(57)【特許請求の範囲】
【請求項１】
Ｇを可換群、ＥをＧの元を平文とする公開鍵暗号方式における準同型性の暗号化関数、Ｂを集合Ｓ⊆Ｇを値域とし任意の０ではないｘ∈Ｇについて（Ｓ＋ｘ）∩Ｓの元で０ではないものを計算することが困難な関数、ｍをメッセージ、Ｃ＝Ｅ（Ｂ（ｍ））を暗号文、ＩをＧの元ｘを入力としてｘ＝Ｂ（ｍ’）となるｍ’が存在する場合には真を出力する関数として、
乱数ｒ∈Ｇを生成する乱数生成部と、
送信情報Ｃ０＝Ｅ（ｒ）を計算する送信情報生成部と、
Ｃ＋Ｃ０を、上記暗号化関数Ｅを復号可能であり受信したＣ＋Ｃ０を復号しその復号結果ｄを出力する復号装置に送信する送信部と、
上記復号装置から上記復号結果ｄを受信する受信部と、
検証情報ｄ’＝ｄ−ｒを計算する検証情報生成部と、
Ｉ（ｄ’）＝真であるか判定する判定部と、
を含む復号結果検証装置。
【請求項２】
請求項１の復号結果検証装置において、
ＡをＧの元を入力としてあるメッセージを出力する関数で任意のメッセージｍに対してＡ（Ｂ（ｍ））＝ｍの性質を満たす関数として、
Ｉ（ｄ’）＝真であれば、Ａ（ｄ’）を出力する出力部を更に含む、
復号結果検証装置。
【請求項３】
請求項１又は２の復号結果検証装置において、
ｈをハッシュ関数、||をビット結合として、
上記Ｂ（ｍ）＝ｍ||ｈ（ｍ）であることを特徴とする、
復号結果検証装置。
【請求項４】
Ｇを可換群、ＥをＧの元を平文とする公開鍵暗号方式における準同型性の暗号化関数、Ｂを集合Ｓ⊆Ｇを値域とし任意の０ではないｘ∈Ｇについて（Ｓ＋ｘ）∩Ｓの元で０ではないものを計算することが困難な関数、ｍをメッセージ、Ｃ＝Ｅ（Ｂ（ｍ））を暗号文、ＩをＧの元ｘを入力としてｘ＝Ｂ（ｍ’）となるｍ’が存在する場合には真を出力する関数として、
乱数生成部が、乱数ｒ∈Ｇを生成する乱数生成ステップと、
送信情報生成部が、送信情報Ｃ０＝Ｅ（ｒ）を計算する送信情報生成ステップと、
送信部が、Ｃ＋Ｃ０を、上記暗号化関数Ｅを復号可能であり受信したＣ＋Ｃ０を復号しその復号結果ｄを出力する復号装置に送信する送信ステップと、
受信部が、上記復号装置から上記復号結果ｄを受信する受信ステップと、
検証情報生成部が、検証情報ｄ’＝ｄ−ｒを計算する検証情報生成ステップと、
判定部が、Ｉ（ｄ’）＝真であるか判定する判定ステップと、
を含む復号結果検証方法。
【請求項５】
請求項１から３の何れかに記載の復号結果検証装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータによる計算技術に関する。特に、他の計算機に行わせた計算結果を用いて計算を行う技術に関する。
【背景技術】
【０００２】
パリティビット等の確認情報Ｑ（ｍ）を用いて、復号装置に行わせた復号の計算結果が正しいかどうかを判断する以下のような技術が考えられる。パリティビットについては、例えば非特許文献１を参照のこと。
【０００３】
依頼装置は、メッセージｍに対してパリティビット等の確認情報Ｑ（ｍ）をビット結合して得られるｍ||Ｑ（ｍ）を平文とした暗号文Ｅ（ｍ||Ｑ（ｍ））を、復号装置に行わせる計算結果を用いて復号する。ここで、Ｑ（ｍ）を例えば偶数性のパリティビットとする。すなわち、Ｑ（ｍ）を構成するビットのうち１のビットの数が、偶数の場合には０を出力し、奇数の場合には１を出力するパリティビットとする。
【０００４】
まず、依頼装置が、暗号文Ｅ（ｍ||Ｑ（ｍ））を復号装置に送信する。
【０００５】
復号装置は、受信した暗号文Ｅ（ｍ||Ｑ（ｍ））を復号し、計算結果ｍ||Ｑ（ｍ）を依頼装置に送信する。
【０００６】
依頼装置は、受信した計算結果ｍ||Ｑ（ｍ）を、メッセージｍと確認情報Ｑ（ｍ）とに分離する。依頼装置は、分離された確認情報Ｑ（ｍ）と、分離されたメッセージｍから生成した確認情報Ｑ（ｍ）とが一致しているか判断する。
【０００７】
一致していれば、受信した計算結果ｍ||Ｑ（ｍ）は正しいと判断することができ、分離されたメッセージｍを、正しく復号されたメッセージｍとする。
【０００８】
一致していなければ、受信した計算結果ｍ||Ｑ（ｍ）は正しくないと判断することができ、分離されたメッセージｍを、正しく復号されたメッセージｍではないとする。
【０００９】
これにより、依頼装置は、復号装置の計算結果ｍ||Ｑ（ｍ）が偶発的な誤りを含む場合に、その誤りを一定の確率で検出することができる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】長尾真（外７名）編，「岩波  情報科学辞典」，第１刷，岩波書店，１９９５年５月２５日，ｐ．５９２
【発明の概要】
【発明が解決しようとする課題】
【００１１】
背景技術に記載した技術では、復号装置は依頼装置の判断を欺きながら、メッセージｍを改変することが可能である。
【００１２】
例えば、復号装置は、暗号文Ｅ（ｍ||Ｑ（ｍ））を復号したｍ||Ｑ（ｍ）から確認情報Ｑ（ｍ）を分離する。復号装置は、任意の改変されたメッセージｍ＊及びこのメッセージｍ＊に対応する確認情報Ｑ（ｍ＊）を生成する。例えば、ｍを構成するビットのうち何れか２つのビットの値を反転させたものをｍ＊とする。この場合、Ｑ（ｍ＊）の値とＱ（ｍ）の値とは同じになる。復号装置は、ｍ||Ｑ（ｍ）に代えてｍ＊||Ｑ（ｍ＊）を依頼装置に送信する。
【００１３】
この場合、依頼装置は、受信したｍ＊||Ｑ（ｍ＊）を、メッセージｍ＊と確認情報Ｑ（ｍ＊）とに分離し、分離された確認情報Ｑ（ｍ＊）と、分離されたメッセージｍ＊から生成した確認情報Ｑ（ｍ＊）とが一致しているか判断するが、この値は一致してしまう。
【００１４】
このようにして、復号装置は依頼装置の判断を欺きながら、メッセージｍを改変することが可能である。言い換えれば、背景技術の依頼装置は、復号装置が復号のための計算を正しく行ったかどうかを検証することはできない。
【００１５】
この発明の課題は、復号装置が復号のための計算を正しく行ったかどうかを検証可能な復号結果検証装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１６】
この発明の一態様による復号結果検証装置は、Ｇを可換群、ＥをＧの元を平文とする公開鍵暗号方式における準同型性の暗号化関数、Ｂを集合Ｓ⊆Ｇを値域とし任意の０ではないｘ∈Ｇについて（Ｓ＋ｘ）∩Ｓの元で０ではないものを計算することが困難な関数、ｍをメッセージ、Ｃ＝Ｅ（Ｂ（ｍ））を暗号文、ＩをＧの元ｘを入力としてｘ＝Ｂ（ｍ’）となるｍ’が存在する場合には真を出力する関数として、乱数ｒ∈Ｇを生成する乱数生成部と、送信情報Ｃ０＝Ｅ（ｒ）を計算する送信情報生成部と、Ｃ＋Ｃ０を、暗号化関数Ｅを復号可能であり受信したＣ＋Ｃ０を復号しその復号結果ｄを出力する復号装置に送信する送信部と、復号装置から復号結果ｄを受信する受信部と、ｄ’＝ｄ−ｒを計算する検証情報生成部と、Ｉ（ｄ’）＝真であるか判定する判定部と、を含む。
【発明の効果】
【００１７】
復号結果検証装置は、復号装置が復号のための計算を正しく行ったかどうかを検証することができる。
【図面の簡単な説明】
【００１８】
【図１】実施形態の復号結果検証装置の構成を説明するためのブロック図。
【図２】実施形態の復号結果検証装置の処理を説明するためのフローチャート。
【発明を実施するための形態】
【００１９】
以下、図面を参照してこの発明の一実施形態を説明する。
【００２０】
［記号の定義］
まず、以下のように記号を定義する。
【００２１】
Ｇは、可換群である。なお、群の演算は、加法的に表記する。
【００２２】
Ｅは、Ｇの元を平文とする公開鍵暗号方式における準同型性の暗号化関数である。Ｅは、準同型性の性質を有するため、任意のａ∈Ｇ及び任意のｂ∈Ｇに対してＥ（ａ）＋Ｅ（ｂ）＝Ｅ（ａ＋ｂ）である。Ｅは公開されており、復号結果検証装置１は関数Ｅの計算が可能であるとする。
【００２３】
Ｄは、Ｅに対応する公開鍵暗号方式における復号関数である。すなわち、任意のｙ∈Ｇに対してＤ（Ｅ（ｙ））＝ｙである。
【００２４】
Ｂは、集合Ｓ⊆Ｇを値域とする関数である。また、Ｂは、任意の０ではないｘ∈Ｇについて（Ｓ＋ｘ）∩Ｓの元で０ではないものを計算することが困難な関数であるという性質を有する。
【００２５】
ｍは、メッセージである。
【００２６】
Ｃ＝Ｅ（Ｂ（ｍ））は、復号の対象となる暗号文である。暗号文Ｃは、図示されていない暗号文生成装置により生成されたものである。
【００２７】
Ｉは、Ｇの元ｘを入力としてｘ＝Ｂ（ｍ’）となるｍ’が存在する場合には真を出力し、存在しない場合には偽を出力する関数である。
【００２８】
Ａは、Ｇの元を入力としてあるメッセージを出力する関数で任意のメッセージｍに対してＡ（Ｂ（ｍ））＝ｍの性質を満たす関数である。
【００２９】
ｈは、例えばＳＨＡ−２５６等の安全なハッシュ関数である。
【００３０】
||は、ビット結合である。
【００３１】
［復号結果検証装置及び方法］
この発明の一実施形態である復号結果検証装置１（図１）は、復号装置２に行わせた所定の計算の結果を用いて、暗号文Ｅ（Ｂ（ｍ））を復号する。その際、復号結果検証装置１は、復号装置２の計算結果が、正しく行われたかどうかを検証可能である。言い換えれば、復号装置２が、メッセージｍを改変したかどうか検証可能である。
【００３２】
図１に示すように、復号結果検証装置１は、乱数生成部１１、送信情報生成部１２、送信部１３、受信部１４、検証情報生成部１５、判定部１６、出力部１７を例えば含む。
【００３３】
復号結果検証装置１の乱数生成部１１（図１）は、乱数ｒ∈Ｇを生成する（ステップＳ１）。生成された乱数ｒは、送信情報生成部１２及び検証情報生成部１５に送信される。
【００３４】
復号結果検証装置１の送信情報生成部１２は、乱数ｒを用いて、送信情報Ｃ０＝Ｅ（ｒ）を生成する（ステップＳ２）。生成された送信情報Ｃ０は、送信部１３に送信される。
【００３５】
復号結果検証装置１の送信部１３には、暗号文Ｃ＝Ｅ（Ｂ（ｍ））及び送信情報Ｃ０が入力される。送信部１３は、Ｃ＋Ｃ０を計算して、復号装置２に送信する（ステップＳ３）。
【００３６】
復号装置２は、Ｃ＋Ｃ０を受信する。復号装置２は、暗号化関数Ｅを復号可能であり、受信したＣ＋Ｃ０を復号し、その復号結果ｄを復号結果検証装置１に送信する（ステップＳ４）。復号装置２は、具体的には、復号関数Ｄを用いて、Ｃ＋Ｃ０を復号する。Ｅの準同型性から、復号装置２の計算が正しく行われた場合には、復号結果ｄ＝Ｄ（Ｃ＋Ｃ０）＝Ｄ（Ｅ（Ｂ（ｍ））＋Ｅ（ｒ））＝Ｄ（Ｅ（Ｂ（ｍ）＋ｒ））＝Ｂ（ｍ）＋ｒとなる。
【００３７】
復号結果検証装置１の受信部１４は、復号結果ｄを受信する（ステップＳ５）。受信部１４は、受信した復号結果ｄを検証情報生成部１５に送信する。
【００３８】
復号結果検証装置１の検証情報生成部１５は、復号結果ｄ及び乱数ｒを用いて、検証情報ｄ’＝ｄ−ｒを計算する（ステップＳ６）。計算された’は、判定部１６に送信される。
【００３９】
判定部１６は、Ｉ（ｄ’）＝真であるか判定する（ステップＳ７）。すなわち、検証情報ｄ’が、集合Ｓに属するかどうかを判定する。
【００４０】
Ｉ（ｄ’）＝真であれば、復号装置２の復号結果ｄは正しいと判断することができる。その理由については後述する。この場合、判定部１６は、検証情報ｄ’を出力部１７に送信する。検証情報ｄ’を受信した出力部１７は、Ａ（ｄ’）を計算して出力する（ステップＳ８）。この場合、Ａ（ｄ’）＝ｍとなる。
【００４１】
Ｉ（ｄ’）＝真でなければ、復号装置２の復号結果ｄは正しいと判断することはできない。その理由については後述する。この場合、判定部１６は、エラーが生じた旨の情報を出力する。
【００４２】
このようにして、復号結果検証装置１は、復号装置２が復号のための計算を正しく行ったかどうかを検証することができる。
【００４３】
［Ｂ，Ａ及びＩの具体例］
例えば、Ｂ（ｍ）＝ｍ||ｈ（ｍ）とすることができる。もし、このように定義されたＢが、Ｂの性質を満たさなければ、ｈをランダムオラクルと識別することができるが、安全なハッシュ関数をランダムオラクルと識別するための実施可能なアルゴリズムは存在しないと考えられている。よって、このように定義されたＢは、Ｂの性質を満たす。
【００４４】
ハッシュ関数ｈの出力のビット長をＬとすると、Ａは、入力に対して下位Ｌビットを除いたビット列を出力する関数である。
【００４５】
また、Ｉ（ｄ’）は、ｄの下位Ｌビットと、ｄ’の下位Ｌビット以外のビットのハッシュ値ｈ（Ａ（ｄ’））とが一致している場合に真を出力し、一致していない場合に偽を出力する関数である。
【００４６】
［Ｉ（ｄ’）の値に基づいて、復号装置２の復号結果ｄが正しいかどうか判断することができる理由］
上記の実施形態のアルゴリズムは、次の＜方式１＞のように記述することができる。ここで、暗号文Ｃ＝Ｅ（Ｂ（ｍ））である。機械Ｘは、上記実施形態の復号装置２に対応する。
【００４７】
＜方式１＞
１．乱数ｒを生成し、Ｃ０＝Ｅ（ｒ）を計算する。
【００４８】
２．機械Ｘに暗号文Ｃ＋Ｃ０を入力し、機械Ｘから復号結果ｄを受信する。
【００４９】
３．ｄ’＝ｄ−ｒを計算する。
【００５０】
４．Ｉ（ｄ’）が真であれば、Ａ（ｄ）を出力する。そうでなければ、エラーを出力
する。
【００５１】
＜方式１＞において、機械Ｘが悪意を持って返答する可能性を考慮するときに、Ｉ（ｄ’）が真でかつＡ（ｄ’）がｍ以外となる事象を、Ｘによる攻撃が成功したと呼ぶことにする。以下では、機械Ｘによる攻撃が成功する確率を評価する。
【００５２】
＜方式１＞において機械Ｘに送信する情報の暗号化を省略すると下記の＜方式２＞が得られる。機械Ｘが悪意を持って返答する可能性を考慮するときに、Ｉ（ｄ’）が真でかつＡ（ｄ’）がｍ以外となる事象を、機械Ｘによる攻撃が成功したと呼ぶことにする。
【００５３】
＜方式２＞
１．機械ＸにＢ（ｍ）＋ｒを入力し、機械Ｘから復号結果ｄを受信する。
【００５４】
２．ｄ’＝ｄ−ｒを計算する。
【００５５】
３．Ｉ（ｄ’）が真であれば、Ａ（ｄ’）を出力する。そうでなければ、エラーを出力
する。
【００５６】
記号ｒをｒ−Ｂ（ｍ）で置き換えると、次の＜方式３＞を得る。機械Ｘが悪意を持って返答する可能性を考慮するときに、Ｉ（ｄ’）が真でかつＡ（ｄ’）がｍ以外となる事象を、機械Ｘによる攻撃が成功したとよぶことにする。
【００５７】
＜方式３＞
１．機械Ｘに暗号文ｒを入力し、機械Ｘから復号結果ｄを受信する。
【００５８】
２．ｄ’＝ｄ−ｒ＋Ｂ（ｍ）を計算する。
【００５９】
３．Ｉ（ｄ’）が真であれば、Ａ（ｄ’）を出力する。そうでなければ、エラーを出力する。
【００６０】
任意のＢ（ｍ）について、乱数ｒとｒ＋Ｂ（ｍ）の分布は等しいか、識別困難であるから、任意の機械Ｘについて、＜方式２＞において攻撃が成功する確率と＜方式３＞において攻撃が成功する確率は等しいまたは識別困難である。
【００６１】
ここで、次の＜方式４＞を考える。機械Ｙが悪意を持って返答する可能性を考慮するときに、Ｉ（ｄ’）が真でかつＡ（ｄ’）がｍ以外となる事象を、機械Ｙによる攻撃が成功したとよぶことにする。
【００６２】
＜方式４＞
１．機械Ｙから復号結果ｄを受信する。
【００６３】
２．ｄ’＝ｄ＋Ｂ（ｍ）を計算する。
【００６４】
３．Ｉ（ｄ’）が真であれば、Ａ（ｄ’）を出力する。そうでなければ、エラーを出力する。
【００６５】
さて、ある機械Ｘが存在して、＜方式３＞において攻撃が成功する確率がｐＸであるとする。機械Ｘをサブルーチンとして用いて外部の機械Ｍと通信する機械ＹＸを次のように構成することができる。
【００６６】
＜ＹＸ＞
１．乱数ｒを生成し、機械Ｘに送信する。機械Ｘからｄを受信する。
【００６７】
２．ｄ−ｒを計算し、機械Ｍに返信する。
【００６８】
＜方式４＞を機械Ｍとみなして、＜方式４＞における機械Ｙを機械ＹＸに置き換えると、置き換えて得られた方式の出力は＜方式３＞と等しい。したがって、機械Ｘが＜方式３＞の攻撃に成功する確率は、機械ＹＸが＜方式４＞の攻撃に成功する確率と等しい。
【００６９】
ところで、上記実施形態のＢについての定義を仮定すると、任意の機械Ｙについて、機械Ｙが＜方式４＞の攻撃に成功する確率は無視できる。そのＢについての定義とは、「Ｂは次の性質を満たすとする：Ｂの値域をＳとするとき、任意の０ではないｘ∈Ｇについて（Ｓ＋ｘ）∩Ｓの元で０ではないものを計算することは困難である。」というものである。
【００７０】
なぜならば、もし＜方式４＞の攻撃に成功するならばｄ≠０であり、Ｉ（ｄ’）が真であるならば、Ｂ（ｍ）∈ＳについてＢ（ｍ）＋ｄ∈Ｓとなり、ｄを上記のｘ∈Ｇとみなせば、Ｂ（ｍ）∈（Ｓ＋ｘ）∩Ｓを計算できたことになるからである。
【００７１】
したがって、任意の機械Ｘについて機械ＹＸを機械Yとして用いれば、機械ＹＸが＜方式４＞の攻撃に成功する確率は無視できる。機械Ｘが＜方式３＞の攻撃に成功する確率は、機械ＹＸが＜方式４＞の攻撃に成功する確率と等しいから、任意の機械ＸについてｐＸは無視できる量である。
【００７２】
＜方式２＞は＜方式１＞から公開鍵暗号による暗号化を取り去ったものであるから、任意の機械Ｘが＜方式１＞の攻撃に成功する確率は、機械Ｘが＜方式２＞の攻撃に成功する確率よりも小さい。よって、任意の機械Ｘが＜方式１＞の攻撃に成功する確率は無視できる量である。
【００７３】
すなわち、復号装置２は復号結果検証装置１の判断を欺きながら、メッセージｍを改変することはできない。言い換えれば、復号結果検証装置１は、復号装置２が復号のための計算を正しく行ったかどうかを検証することができる。
【００７４】
［変形例等］
乱数ｒは、復号装置２が知ることができない所定の整数であってもよい。
【００７５】
復号結果検証装置１の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【００７６】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００７７】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７９】
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００８０】
１      復号結果検証装置
１１    乱数生成部
１２    送信情報生成部
１３    送信部
１４    受信部
１５    検証情報生成部
１６    判定部
１７    出力部
２      復号装置
【図１】
0005469631.tif 000002
【図２】
0005469631.tif 000003