(57)【特許請求の範囲】
【請求項１】
復号装置に暗号文の復号を依頼して、戻ってきた結果を検証する復号結果検証装置であって、
ｈをハッシュ関数、Ｅ（ｍ，ｒ）を公開鍵と整数ｒを用いてメッセージｍのみを暗号化して暗号文を生成する暗号化関数、Ｅ（ｍ，ｈ（ｍ））を暗号文ｃとして、
上記暗号化関数Ｅは、生成された暗号文から上記メッセージｍの情報を漏洩しない確率的公開鍵暗号方式であり、
上記Ｅ（ｍ，ｈ（ｍ））に入力される上記メッセージｍは付加ビットのない平文であり、
上記暗号文ｃを、上記暗号化関数Ｅに対応する復号関数Ｄで受信した上記暗号文ｃを秘密鍵を用いて復号可能でありその復号結果ｍ’を出力する上記復号装置に送信する送信部と、
上記復号装置から上記復号結果ｍ’を受信する受信部と、
上記復号結果ｍ’を用いて上記公開鍵のみで検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する検証情報生成部と、
上記暗号文ｃと上記検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する判定部と、
を含む復号結果検証装置。
【請求項２】
請求項１の復号結果検証装置において、
検証する暗号文ｃを生成する上記暗号化関数Ｅ（ｍ，ｒ）は、ｐ，ｑを素数、Ｎ＝ｐｑ、Ｎ２を上記公開鍵、ｐ−１とｑ−１の最小公倍数であるλを上記秘密鍵、ｇをＺ／Ｎ２Ｚの可逆元として、ｇｍｒＮ  ｍｏｄ  Ｎ２で表わされるものであり、
上記暗号文ｃを復号するための上記復号関数Ｄは、下記式により定義されるｍ’の値を計算する関数で表わされるものである、
ｗ＝ｇλ  ｍｏｄ  Ｎ２
ｚ＝（ｗ−１）／Ｎ
μ＝ｚ−１  ｍｏｄ  Ｎ
ｕ＝ｃλ  ｍｏｄ  Ｎ２
ｖ＝（ｕ−１）／Ｎ
ｍ’＝ｖμ  ｍｏｄ  Ｎ
ことを特徴とする復号結果検証装置。
【請求項３】
請求項１の復号結果検証装置において、
検証する暗号文ｃを生成する上記暗号化関数Ｅ（ｍ，ｒ）は、Ｇを巡回群、ｇを群Ｇの生成元、所定の整数ｓを上記秘密鍵、ｙ＝ｇｓを上記公開鍵として、ｃ０＝ｍｙｒ及びｃ１＝ｇｒを出力する関数で表わされるものであり、
上記暗号文ｃは、第一暗号文ｃ０＝ｍｙｈ（ｍ）及び第二暗号文ｃ１＝ｇｈ（ｍ）の組で表わされるものであり、
上記暗号文ｃを復号するための上記復号関数Ｄは、ｃ０ｃ１−ｓで表わされるものであり、
上記検証情報生成部は、第一検証情報ｃ０’＝ｍ’ｙｈ（ｍ’）及び第二検証情報ｃ１’＝ｇｈ（ｍ’）を計算し、
上記判定部は、上記第一暗号文ｃ０と上記第一検証情報ｃ０’とが一致するか、及び、上記第二暗号文ｃ１と上記第二検証情報ｃ１’とが一致するかを判定する、
ことを特徴とする復号結果検証装置。
【請求項４】
復号装置に暗号文の復号を依頼して、戻ってきた結果を検証する復号結果検証方法であって、
ｈをハッシュ関数、Ｅ（ｍ，ｒ）を公開鍵と整数ｒを用いてメッセージｍのみを暗号化して暗号文を生成する暗号化関数、Ｅ（ｍ，ｈ（ｍ））を暗号文ｃとして、
上記暗号化関数Ｅは、生成された暗号文から上記メッセージｍの情報を漏洩しない確率的公開鍵暗号方式であり、
上記Ｅ（ｍ，ｈ（ｍ））に入力される上記メッセージｍは付加ビットのない平文であり、
送信部が、上記暗号文ｃを、上記暗号化関数Ｅに対応する復号関数Ｄで受信した暗号文ｃを秘密鍵を用いて復号可能でありその復号結果ｍ’を出力する上記復号装置に送信する送信ステップと、
受信部が、上記復号装置から上記復号結果ｍ’を受信する受信ステップと、
検証情報生成部が、上記公開鍵のみで上記復号結果ｍ’を用いて検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する検証情報生成ステップと、
判定部が、上記暗号文ｃと上記検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する判定ステップと、
を含む復号結果検証方法。
【請求項５】
復号装置に暗号文の復号を依頼して、戻ってきた結果を検証する復号結果検証システムにおいて、
ｈをハッシュ関数、Ｅ（ｍ，ｒ）を公開鍵と整数ｒを用いてメッセージｍのみを暗号化して暗号文を生成する暗号化関数、Ｅ（ｍ，ｈ（ｍ））を暗号文ｃとして、
上記暗号化関数Ｅは、生成された暗号文から上記メッセージｍの情報を漏洩しない確率的公開鍵暗号方式であり、
上記Ｅ（ｍ，ｈ（ｍ））に入力される上記メッセージｍは付加ビットのない平文であり、
上記暗号化関数Ｅに対応する復号関数Ｄで受信した上記暗号文ｃを秘密鍵を用いて復号可能でありその復号結果ｍ’を出力する復号装置と、
上記暗号文ｃを上記復号装置に送信する送信部と、上記復号装置から上記復号結果ｍ’を受信する受信部と、上記公開鍵のみで上記復号結果ｍ’を用いて検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する検証情報生成部と、上記暗号文ｃと上記検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する判定部と、を含む復号結果検証装置と、
を含む復号結果検証システム。
【請求項６】
請求項１から３の何れかの復号結果検証装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータによる計算技術に関する。特に、他の計算機に行わせた計算結果を用いて計算を行う技術に関する。
【背景技術】
【０００２】
パリティビット等の確認情報Ｑ（ｍ）を用いて、復号装置に行わせた復号の計算結果が正しいかどうかを判断する以下のような技術が考えられる。パリティビットについては、例えば非特許文献１を参照のこと。
【０００３】
依頼装置は、メッセージｍに対してパリティビット等の確認情報Ｑ（ｍ）をビット結合して得られるｍ||Ｑ（ｍ）を平文とした暗号文Ｅ（ｍ||Ｑ（ｍ））を、復号装置に行わせる計算結果を用いて復号する。ここで、Ｑ（ｍ）を例えば偶数性のパリティビットとする。すなわち、Ｑ（ｍ）を構成するビットのうち１のビットの数が、偶数の場合には０を出力し、奇数の場合には１を出力するパリティビットとする。
【０００４】
まず、依頼装置が、暗号文Ｅ（ｍ||Ｑ（ｍ））を復号装置に送信する。
【０００５】
復号装置は、受信した暗号文Ｅ（ｍ||Ｑ（ｍ））を復号し、計算結果ｍ||Ｑ（ｍ）を依頼装置に送信する。
【０００６】
依頼装置は、受信した計算結果ｍ||Ｑ（ｍ）を、メッセージｍと確認情報Ｑ（ｍ）とに分離する。依頼装置は、分離された確認情報Ｑ（ｍ）と、分離されたメッセージｍから生成した確認情報Ｑ（ｍ）とが一致しているか判断する。
【０００７】
一致していれば、受信した計算結果ｍ||Ｑ（ｍ）は正しいと判断することができ、分離されたメッセージｍを、正しく復号されたメッセージｍとする。
【０００８】
一致していなければ、受信した計算結果ｍ||Ｑ（ｍ）は正しくないと判断することができ、分離されたメッセージｍを、正しく復号されたメッセージｍではないとする。
【０００９】
これにより、依頼装置は、復号装置の計算結果ｍ||Ｑ（ｍ）が偶発的な誤りを含む場合に、その誤りを一定の確率で検出することができる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】長尾真（外７名）編，「岩波  情報科学辞典」，第１刷，岩波書店，１９９５年５月２５日，ｐ．５９２
【発明の概要】
【発明が解決しようとする課題】
【００１１】
背景技術に記載した技術では、メッセージｍに確認情報Ｑ（ｍ）を付加したものが暗号化の対象となり、メッセージｍのみを暗号化の対象とする場合と比較して、生成される暗号文の長さが長くなる可能性がある。
【００１２】
この発明の課題は、暗号化の対象はメッセージｍのままで、復号装置が復号のための計算を正しく行ったかどうかを検証可能な復号結果検証装置、方法、システム及びプログラムを提供することである。
【課題を解決するための手段】
【００１３】
この発明の一態様による復号結果検証装置は、ｈをハッシュ関数、Ｅ（ｍ，ｒ）を整数ｒを用いてメッセージｍのみを暗号化して暗号文を生成しその生成された暗号文からメッセージｍの情報を漏洩しない暗号化関数として、Ｅ（ｍ，ｈ（ｍ））を暗号文ｃとして、暗号文ｃを、暗号化関数Ｅに対応する復号関数Ｄで受信した暗号文ｃを復号可能でありその復号結果ｍ’を出力する復号装置に送信する送信部と、復号装置から復号結果ｍ’を受信する受信部と、復号結果ｍ’を用いて検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する検証情報生成部と、暗号文ｃと検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する判定部と、を含む。
【発明の効果】
【００１４】
暗号化関数が用いる整数としてメッセージｍのハッシュ値ｈ（ｍ）を用いることにより、暗号化の対象はメッセージｍのままで、復号装置が復号のための計算を正しく行ったかどうかを検証することができる。
【図面の簡単な説明】
【００１５】
【図１】実施形態の復号結果検証装置の構成を説明するためのブロック図。
【図２】実施形態の復号結果検証装置の処理を説明するためのフローチャート。
【図３】実施形態のアルゴリズムの概要を説明するための図。
【図４】Ｐａｉｌｌｅｒ暗号を用いたアルゴリズムの例の概要を説明するための図。
【図５】ＥｌＧａｍａｌ暗号を用いたアルゴリズムの例の概要を説明するための図。
【発明を実施するための形態】
【００１６】
以下、図面を参照してこの発明の一実施形態を説明する。
【００１７】
［記号の定義］
まず、以下のように記号を定義する。
ｍは、メッセージである。
Ｅ（ｍ，ｒ）は、整数ｒを用いてメッセージｍを暗号化して暗号文を生成しその生成された暗号文からメッセージｍの情報を漏洩しない暗号化関数である。ｒは、例えば乱数である。例えば、Ｅ（ｍ，ｒ）を、確率的アルゴリズムにより記述された確率的公開鍵暗号の暗号化関数とする。Ｅ（ｍ，ｒ）は、所定の整数ｒを乱数の初期値として用いてもよい。暗号化関数Ｅ（ｍ，ｒ）の具体例は、後述する。
【００１８】
ｈは、例えばランダム関数と見なすことができるＳＨＡ−２５６等の安全なハッシュ関数である。
ｃ＝Ｅ（ｍ，ｈ（ｍ））は、暗号文である。
【００１９】
Ｄは、Ｅに対応する公開鍵暗号方式における復号関数である。すなわち、任意のメッセージｍに対してＤ（Ｅ（ｍ））＝ｍである。
【００２０】
［実施形態］
この発明の一実施形態である復号結果検証装置１（図１）は、復号装置２に行わせた所定の計算の結果を用いて、暗号文ｃを復号する。その際、復号結果検証装置１は、復号装置２の計算結果が、正しく行われたかどうかを検証可能である。また、復号装置２が、メッセージｍを改変したかどうかについても検証可能である。
【００２１】
図１に示すように、復号結果検証装置１は、送信部１１、受信部１２、検証情報生成部１３、判定部１４、出力部１５を例えば含む。また、この実施形態のアルゴリズムの概要を図３に示す。
【００２２】
暗号文ｃ＝Ｅ（ｍ，ｈ（ｍ））は、暗号化装置０により生成されて（ステップｅ１、図２）、復号結果検証装置１に送信される。
【００２３】
復号結果検証装置１の送信部１１は、暗号文ｃを復号装置２に送信する（ステップｖ１）。
【００２４】
復号装置２は、受信した暗号文ｃを復号関数Ｄで復号可能であり、その復号結果ｍ’を出力する（ステップｄ１）。復号装置２が正しく計算を行った場合には、復号結果ｍ’＝ｍとなる。しかし、復号装置２は、正しく計算を行わなくてもよい。この結果、復号結果ｍ’≠ｍである復号結果ｍ’が、復号結果検証装置１に送信されることもある。
【００２５】
復号結果検証装置１の受信部１２は、復号結果ｍ’を復号装置２から受信する（ステップｖ２）。受信した復号結果ｍ’は、検証情報生成部１３に送信される。
【００２６】
復号結果検証装置１の検証情報生成部１３は、復号結果ｍ’を用いて検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する（ステップｖ３）。計算された検証情報Ｅ（ｍ’，ｈ（ｍ’））は、判定部１４に送信される。
【００２７】
判定部１４は、暗号文ｃと検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する（ステップｖ４）。判定結果は、出力部１５に送信される。
【００２８】
これらが一致していれば、復号装置２の計算結果は正しく、復号結果ｍ’がｍであると判断することができる（ステップｖ５）。
【００２９】
これらが一致していなければ、復号装置２の計算結果は正しくなく、復号結果ｍ’はｍでないと判断することができる（ステップｖ６）。
【００３０】
Ｅ（ｍ，ｒ）の定義から、生成された暗号文ｃからメッセージｍの情報は漏洩しない。このため、復号装置２は、暗号文ｃと検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するような、ｍ’＝ｍでない復号結果ｍ’を生成することはできない。このため、上記のように判断することができるのである。
【００３１】
復号結果ｍ’がｍであると判断することができた場合には、復号結果検証装置１の出力部１５は、復号結果ｍ’をｍとして出力する。
【００３２】
このように、暗号化関数Ｅが用いる整数としてメッセージｍのハッシュ値ｈ（ｍ）を用いることにより、暗号化の対象はメッセージｍのままで、復号装置が復号のための計算を正しく行ったかどうかを検証することができる。
【００３３】
［暗号化関数及び復号関数の具体例１］
いわゆるＰａｉｌｌｅｒ暗号を用いて、暗号化関数Ｅ及び復号関数Ｄを構成することができる。この場合のアルゴリズムの概要を、図４に例示する。Ｐａｉｌｌｅｒ暗号については、例えば下記参考文献を参照のこと。
【００３４】
〔参考文献〕Pascal Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes”, ADVANCES IN CRYPTOLOGY ― EUROCRYPT '99, Lecture Notes in Computer Science, 1999, Volume 1592/1999, pp.223-238
【００３５】
ｐ，ｑを素数、Ｎ＝ｐｑ、Ｎ２を公開鍵、ｐ−１とｑ−１の最小公倍数であるλを秘密鍵、ｇをＺ／Ｎ２Ｚの可逆元として、暗号化関数Ｅ（ｍ，ｒ）＝ｇｍｒＮ  ｍｏｄ  Ｎ２とする。すなわち、暗号文ｃ＝Ｅ（ｍ，ｈ（ｍ））＝ｇｍｈ（ｍ）Ｎ  ｍｏｄ  Ｎ２となる。
【００３６】
復号関数Ｄは、例えば次の５個の式により定義される。復号装置２は、ステップｄ１において、下記式により定義されるｍ’の値を計算して、復号結果として出力する。なお、下記式により定義されるｍ’の値の計算をするとは、その値を計算しさえすればその計算方法は問わないことを意味する。すなわち、その値を計算するために、数学的に等価な計算方法により計算してもよいことを意味する。
【００３７】
ｗ＝ｇλ  ｍｏｄ  Ｎ２
ｚ＝（ｗ−１）／Ｎ
μ＝ｚ−１  ｍｏｄ  Ｎ
ｕ＝ｃλ  ｍｏｄ  Ｎ２
ｖ＝（ｕ−１）／Ｎ
ｍ’＝ｖμ  ｍｏｄ  Ｎ
【００３８】
ハッシュ関数ｈをランダム関数とみなすことができて、識別合成剰余問題（Ｄｅｃｉｓｉｏｎａｌ  Ｃｏｍｐｏｓｉｔｅ  Ｒｅｓｉｄｕｏｓｉｔｙ  Ｐｒｏｂｌｅｍ）が困難であるようにＮやｇが選ばれているならば、この具体例１の方式は安全である。識別合成剰余問題とは、秘密の数をａとして、乱数ｒ１，ｒ２についてｇａｒ１Ｎ  ｍｏｄ  Ｎ２とｒ２Ｎ  ｍｏｄ  Ｎ２を与えられたとき、それらを識別する問題である。
【００３９】
ｍをある分布Ｍに従う確率変数によって定められるメッセージとする。ｈをランダム関数と見なすことができるならば、ｃ＝ｇｍｈ（ｍ）Ｎ  ｍｏｄ  Ｎ２は乱数ｒ１についてｃ＝ｇｍｒ１Ｎ  ｍｏｄ  Ｎ２と識別困難である。もし、識別合成剰余問題が困難であれば、ｇｍｒ１Ｎ  ｍｏｄ  Ｎ２は乱数ｒ２についてｒ２Ｎ  ｍｏｄ  Ｎ２と識別困難である。したがって、ｃは、ｒ２Ｎ  ｍｏｄ  Ｎ２と識別困難である。ｒ２Ｎ  ｍｏｄ  Ｎ２はメッセージｍの情報を含まないから、暗号文ｃからのメッセージｍの情報は漏洩しない。
【００４０】
例えば、Ｎの素因数分解が困難であれば識別合成剰余問題を効率良く解くアルゴリズムは知られておらず、識別合成剰余問題は困難であると考えられている。また、ｈとしてＳＨＡ−２５６などの安全なハッシュ関数を選べば、セキュリティパラメータｋについて、Ｍがｋビット以上のエントロピーを持つときに、Ｍから選んだｍについてｈ（ｍ）で与えられる分布を乱数と識別することは困難であるから、ｈをランダム関数とみなすことができる。
【００４１】
［暗号化関数及び復号関数の具体例２］
いわゆるＥｌＧａｍａｌ暗号を用いて、暗号化関数Ｅ及び復号関数Ｄを構成することができる。この場合のアルゴリズムの概要を、図５に例示する。
【００４２】
Ｇを巡回群、ｇを群Ｇの生成元、所定の整数ｓを秘密鍵、ｙ＝ｇｓを公開鍵とする。
【００４３】
暗号化関数Ｅ（ｍ，ｒ）を、ｃ０＝ｍｙｒ及びｃ１＝ｇｒを出力する関数とする。すなわち、第一暗号文ｃ０＝ｍｙｈ（ｍ）及び第二暗号文ｃ１＝ｇｈ（ｍ）の組（ｃ０，ｃ１）が、暗号文ｃとなる。
【００４４】
復号関数Ｄを、ｃ０ｃ１−ｓとする。
【００４５】
復号結果検証装置１の検証情報生成部１３は、ステップｖ３において、第一検証情報ｃ０’＝ｍ’ｙｈ（ｍ’）及び第二検証情報ｃ１’＝ｇｈ（ｍ’）を計算し、この計算された第一検証情報ｃ０’及び第二検証情報ｃ１’の組（ｃ０’，ｃ１’）が検証情報となる。
【００４６】
復号結果検証装置１の判定部１４は、ステップｖ４において、第一暗号文ｃ０と第一検証情報ｃ０’とが一致するか、及び、第一暗号文ｃ１と第一検証情報ｃ１’とが一致するかを判定する。何れも一致すれば、暗号文ｃと検証情報とが一致すると判定する。少なくとも一方が一致しない場合には、暗号文ｃと検証情報とが一致しないと判定する。
【００４７】
ハッシュ関数ｈをランダム関数とみなすことができて、識別Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が困難であれば、この具体例２の方式は安全である。
【００４８】
識別Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題とは、ランダムなａ，ｂ，ｃについて、組（ｇ，ｇａ，ｇｂ，ｇａｂ）と組（ｇ，ｇａ，ｇｂ，ｇｃ）とを確率的多項式時間のアルゴリズムで識別する問題である。ランダム関数と見なすことができるハッシュ関数として例えばＳＨＡ−２５６が知られている。また、識別Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が困難な群として、有限体の乗法群や、楕円曲線等の一般的なＥｌＧａｍａｌ暗号に用いられる群がある。
【００４９】
このとき、ｄを任意の整数として、組（ｇ，ｇｓ，ｇｈ（ｍ），ｇｓｈ（ｍ））と組（ｇ，ｇｓ，ｇｈ（ｍ），ｇｄ）とは識別困難である。このため、各組の４番目の要素をｍ倍した組（ｇ，ｇｓ，ｇｈ（ｍ），ｍｇｓｈ（ｍ））と組（ｇ，ｇｓ，ｇｈ（ｍ），ｍｇｄ）とも識別困難である。このことは、ｙ＝ｇｓであることを考慮すると、ｇ，ｇｓを既知として、組（ｍｙｈ（ｍ），ｇｈ（ｍ））と組（ｍｇｄ，ｇｈ（ｍ））とが識別困難であることと同義である。このため、組（ｍｙｈ（ｍ），ｇｈ（ｍ））の分布と組（ｍｇｄ，ｇｈ（ｍ））の分布とは等しく、暗号文ｃである組（ｍｙｈ（ｍ），ｇｈ（ｍ））からメッセージｍについての情報は得られない。
【００５０】
このように、具体例２で定義した暗号化関数Ｅは、生成された暗号文からメッセージｍの情報を漏洩しないという性質を満たす。
【００５１】
［変形例等］
復号結果検証装置１の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【００５２】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５５】
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００５６】
１      復号結果検証装置
１１    送信部
１２    受信部
１３    検証情報生成部
１４    判定部
１５    出力部
２      復号装置
【図１】
0005912281.tif 000002
【図２】
0005912281.tif 000003
【図３】
0005912281.tif 000004
【図４】
0005912281.tif 000005
【図５】
0005912281.tif 000006