JP5912281B2 - 復号結果検証装置、方法、システム及びプログラム - Google Patents

Description

この発明は、コンピュータによる計算技術に関する。特に、他の計算機に行わせた計算結果を用いて計算を行う技術に関する。

パリティビット等の確認情報Ｑ（ｍ）を用いて、復号装置に行わせた復号の計算結果が正しいかどうかを判断する以下のような技術が考えられる。パリティビットについては、例えば非特許文献１を参照のこと。

依頼装置は、メッセージｍに対してパリティビット等の確認情報Ｑ（ｍ）をビット結合して得られるｍ||Ｑ（ｍ）を平文とした暗号文Ｅ（ｍ||Ｑ（ｍ））を、復号装置に行わせる計算結果を用いて復号する。ここで、Ｑ（ｍ）を例えば偶数性のパリティビットとする。すなわち、Ｑ（ｍ）を構成するビットのうち１のビットの数が、偶数の場合には０を出力し、奇数の場合には１を出力するパリティビットとする。

まず、依頼装置が、暗号文Ｅ（ｍ||Ｑ（ｍ））を復号装置に送信する。

復号装置は、受信した暗号文Ｅ（ｍ||Ｑ（ｍ））を復号し、計算結果ｍ||Ｑ（ｍ）を依頼装置に送信する。

依頼装置は、受信した計算結果ｍ||Ｑ（ｍ）を、メッセージｍと確認情報Ｑ（ｍ）とに分離する。依頼装置は、分離された確認情報Ｑ（ｍ）と、分離されたメッセージｍから生成した確認情報Ｑ（ｍ）とが一致しているか判断する。

一致していれば、受信した計算結果ｍ||Ｑ（ｍ）は正しいと判断することができ、分離されたメッセージｍを、正しく復号されたメッセージｍとする。

一致していなければ、受信した計算結果ｍ||Ｑ（ｍ）は正しくないと判断することができ、分離されたメッセージｍを、正しく復号されたメッセージｍではないとする。

これにより、依頼装置は、復号装置の計算結果ｍ||Ｑ（ｍ）が偶発的な誤りを含む場合に、その誤りを一定の確率で検出することができる。

長尾真（外７名）編，「岩波 情報科学辞典」，第１刷，岩波書店，１９９５年５月２５日，ｐ．５９２

背景技術に記載した技術では、メッセージｍに確認情報Ｑ（ｍ）を付加したものが暗号化の対象となり、メッセージｍのみを暗号化の対象とする場合と比較して、生成される暗号文の長さが長くなる可能性がある。

この発明の課題は、暗号化の対象はメッセージｍのままで、復号装置が復号のための計算を正しく行ったかどうかを検証可能な復号結果検証装置、方法、システム及びプログラムを提供することである。

この発明の一態様による復号結果検証装置は、ｈをハッシュ関数、Ｅ（ｍ，ｒ）を整数ｒを用いてメッセージｍのみを暗号化して暗号文を生成しその生成された暗号文からメッセージｍの情報を漏洩しない暗号化関数として、Ｅ（ｍ，ｈ（ｍ））を暗号文ｃとして、暗号文ｃを、暗号化関数Ｅに対応する復号関数Ｄで受信した暗号文ｃを復号可能でありその復号結果ｍ’を出力する復号装置に送信する送信部と、復号装置から復号結果ｍ’を受信する受信部と、復号結果ｍ’を用いて検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する検証情報生成部と、暗号文ｃと検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する判定部と、を含む。

暗号化関数が用いる整数としてメッセージｍのハッシュ値ｈ（ｍ）を用いることにより、暗号化の対象はメッセージｍのままで、復号装置が復号のための計算を正しく行ったかどうかを検証することができる。

実施形態の復号結果検証装置の構成を説明するためのブロック図。 実施形態の復号結果検証装置の処理を説明するためのフローチャート。 実施形態のアルゴリズムの概要を説明するための図。 Ｐａｉｌｌｅｒ暗号を用いたアルゴリズムの例の概要を説明するための図。 ＥｌＧａｍａｌ暗号を用いたアルゴリズムの例の概要を説明するための図。

以下、図面を参照してこの発明の一実施形態を説明する。

［記号の定義］
まず、以下のように記号を定義する。
ｍは、メッセージである。
Ｅ（ｍ，ｒ）は、整数ｒを用いてメッセージｍを暗号化して暗号文を生成しその生成された暗号文からメッセージｍの情報を漏洩しない暗号化関数である。ｒは、例えば乱数である。例えば、Ｅ（ｍ，ｒ）を、確率的アルゴリズムにより記述された確率的公開鍵暗号の暗号化関数とする。Ｅ（ｍ，ｒ）は、所定の整数ｒを乱数の初期値として用いてもよい。暗号化関数Ｅ（ｍ，ｒ）の具体例は、後述する。

ｈは、例えばランダム関数と見なすことができるＳＨＡ−２５６等の安全なハッシュ関数である。
ｃ＝Ｅ（ｍ，ｈ（ｍ））は、暗号文である。

Ｄは、Ｅに対応する公開鍵暗号方式における復号関数である。すなわち、任意のメッセージｍに対してＤ（Ｅ（ｍ））＝ｍである。

［実施形態］
この発明の一実施形態である復号結果検証装置１（図１）は、復号装置２に行わせた所定の計算の結果を用いて、暗号文ｃを復号する。その際、復号結果検証装置１は、復号装置２の計算結果が、正しく行われたかどうかを検証可能である。また、復号装置２が、メッセージｍを改変したかどうかについても検証可能である。

図１に示すように、復号結果検証装置１は、送信部１１、受信部１２、検証情報生成部１３、判定部１４、出力部１５を例えば含む。また、この実施形態のアルゴリズムの概要を図３に示す。

暗号文ｃ＝Ｅ（ｍ，ｈ（ｍ））は、暗号化装置０により生成されて（ステップｅ１、図２）、復号結果検証装置１に送信される。

復号結果検証装置１の送信部１１は、暗号文ｃを復号装置２に送信する（ステップｖ１）。

復号装置２は、受信した暗号文ｃを復号関数Ｄで復号可能であり、その復号結果ｍ’を出力する（ステップｄ１）。復号装置２が正しく計算を行った場合には、復号結果ｍ’＝ｍとなる。しかし、復号装置２は、正しく計算を行わなくてもよい。この結果、復号結果ｍ’≠ｍである復号結果ｍ’が、復号結果検証装置１に送信されることもある。

復号結果検証装置１の受信部１２は、復号結果ｍ’を復号装置２から受信する（ステップｖ２）。受信した復号結果ｍ’は、検証情報生成部１３に送信される。

復号結果検証装置１の検証情報生成部１３は、復号結果ｍ’を用いて検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する（ステップｖ３）。計算された検証情報Ｅ（ｍ’，ｈ（ｍ’））は、判定部１４に送信される。

判定部１４は、暗号文ｃと検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する（ステップｖ４）。判定結果は、出力部１５に送信される。

これらが一致していれば、復号装置２の計算結果は正しく、復号結果ｍ’がｍであると判断することができる（ステップｖ５）。

これらが一致していなければ、復号装置２の計算結果は正しくなく、復号結果ｍ’はｍでないと判断することができる（ステップｖ６）。

Ｅ（ｍ，ｒ）の定義から、生成された暗号文ｃからメッセージｍの情報は漏洩しない。このため、復号装置２は、暗号文ｃと検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するような、ｍ’＝ｍでない復号結果ｍ’を生成することはできない。このため、上記のように判断することができるのである。

復号結果ｍ’がｍであると判断することができた場合には、復号結果検証装置１の出力部１５は、復号結果ｍ’をｍとして出力する。

このように、暗号化関数Ｅが用いる整数としてメッセージｍのハッシュ値ｈ（ｍ）を用いることにより、暗号化の対象はメッセージｍのままで、復号装置が復号のための計算を正しく行ったかどうかを検証することができる。

［暗号化関数及び復号関数の具体例１］
いわゆるＰａｉｌｌｅｒ暗号を用いて、暗号化関数Ｅ及び復号関数Ｄを構成することができる。この場合のアルゴリズムの概要を、図４に例示する。Ｐａｉｌｌｅｒ暗号については、例えば下記参考文献を参照のこと。

〔参考文献〕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

ｐ，ｑを素数、Ｎ＝ｐｑ、Ｎ^２を公開鍵、ｐ−１とｑ−１の最小公倍数であるλを秘密鍵、ｇをＺ／Ｎ^２Ｚの可逆元として、暗号化関数Ｅ（ｍ，ｒ）＝ｇ^ｍｒ^Ｎ ｍｏｄ Ｎ^２とする。すなわち、暗号文ｃ＝Ｅ（ｍ，ｈ（ｍ））＝ｇ^ｍｈ（ｍ）^Ｎ ｍｏｄ Ｎ^２となる。

復号関数Ｄは、例えば次の５個の式により定義される。復号装置２は、ステップｄ１において、下記式により定義されるｍ’の値を計算して、復号結果として出力する。なお、下記式により定義されるｍ’の値の計算をするとは、その値を計算しさえすればその計算方法は問わないことを意味する。すなわち、その値を計算するために、数学的に等価な計算方法により計算してもよいことを意味する。

ｗ＝ｇ^λ ｍｏｄ Ｎ^２
ｚ＝（ｗ−１）／Ｎ
μ＝ｚ^−１ ｍｏｄ Ｎ
ｕ＝ｃ^λ ｍｏｄ Ｎ^２
ｖ＝（ｕ−１）／Ｎ
ｍ’＝ｖμ ｍｏｄ Ｎ

ハッシュ関数ｈをランダム関数とみなすことができて、識別合成剰余問題（Ｄｅｃｉｓｉｏｎａｌ Ｃｏｍｐｏｓｉｔｅ Ｒｅｓｉｄｕｏｓｉｔｙ Ｐｒｏｂｌｅｍ）が困難であるようにＮやｇが選ばれているならば、この具体例１の方式は安全である。識別合成剰余問題とは、秘密の数をａとして、乱数ｒ_１，ｒ_２についてｇ^ａｒ_１ ^Ｎ ｍｏｄ Ｎ^２とｒ_２ ^Ｎ ｍｏｄ Ｎ^２を与えられたとき、それらを識別する問題である。

ｍをある分布Ｍに従う確率変数によって定められるメッセージとする。ｈをランダム関数と見なすことができるならば、ｃ＝ｇ^ｍｈ（ｍ）^Ｎ ｍｏｄ Ｎ^２は乱数ｒ_１についてｃ＝ｇ^ｍｒ_１ ^Ｎ ｍｏｄ Ｎ^２と識別困難である。もし、識別合成剰余問題が困難であれば、ｇ^ｍｒ_１ ^Ｎ ｍｏｄ Ｎ^２は乱数ｒ_２についてｒ_２ ^Ｎ ｍｏｄ Ｎ^２と識別困難である。したがって、ｃは、ｒ_２ ^Ｎ ｍｏｄ Ｎ_２と識別困難である。ｒ_２ ^Ｎ ｍｏｄ Ｎ^２はメッセージｍの情報を含まないから、暗号文ｃからのメッセージｍの情報は漏洩しない。

例えば、Ｎの素因数分解が困難であれば識別合成剰余問題を効率良く解くアルゴリズムは知られておらず、識別合成剰余問題は困難であると考えられている。また、ｈとしてＳＨＡ−２５６などの安全なハッシュ関数を選べば、セキュリティパラメータｋについて、Ｍがｋビット以上のエントロピーを持つときに、Ｍから選んだｍについてｈ（ｍ）で与えられる分布を乱数と識別することは困難であるから、ｈをランダム関数とみなすことができる。

［暗号化関数及び復号関数の具体例２］
いわゆるＥｌＧａｍａｌ暗号を用いて、暗号化関数Ｅ及び復号関数Ｄを構成することができる。この場合のアルゴリズムの概要を、図５に例示する。

Ｇを巡回群、ｇを群Ｇの生成元、所定の整数ｓを秘密鍵、ｙ＝ｇ^ｓを公開鍵とする。

暗号化関数Ｅ（ｍ，ｒ）を、ｃ_０＝ｍｙ^ｒ及びｃ_１＝ｇ^ｒを出力する関数とする。すなわち、第一暗号文ｃ_０＝ｍｙ^ｈ（ｍ）及び第二暗号文ｃ_１＝ｇ^ｈ（ｍ）の組（ｃ_０，ｃ_１）が、暗号文ｃとなる。

復号関数Ｄを、ｃ_０ｃ_１ ^−ｓとする。

復号結果検証装置１の検証情報生成部１３は、ステップｖ３において、第一検証情報ｃ_０’＝ｍ’ｙ^{ｈ（ｍ’）}及び第二検証情報ｃ_１’＝ｇ^{ｈ（ｍ’）}を計算し、この計算された第一検証情報ｃ_０’及び第二検証情報ｃ_１’の組（ｃ_０’，ｃ_１’）が検証情報となる。

復号結果検証装置１の判定部１４は、ステップｖ４において、第一暗号文ｃ_０と第一検証情報ｃ_０’とが一致するか、及び、第一暗号文ｃ_１と第一検証情報ｃ_１’とが一致するかを判定する。何れも一致すれば、暗号文ｃと検証情報とが一致すると判定する。少なくとも一方が一致しない場合には、暗号文ｃと検証情報とが一致しないと判定する。

ハッシュ関数ｈをランダム関数とみなすことができて、識別Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が困難であれば、この具体例２の方式は安全である。

識別Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題とは、ランダムなａ，ｂ，ｃについて、組（ｇ，ｇ^ａ，ｇ^ｂ，ｇ^ａｂ）と組（ｇ，ｇ^ａ，ｇ^ｂ，ｇ^ｃ）とを確率的多項式時間のアルゴリズムで識別する問題である。ランダム関数と見なすことができるハッシュ関数として例えばＳＨＡ−２５６が知られている。また、識別Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題が困難な群として、有限体の乗法群や、楕円曲線等の一般的なＥｌＧａｍａｌ暗号に用いられる群がある。

このとき、ｄを任意の整数として、組（ｇ，ｇ^ｓ，ｇ^ｈ（ｍ），ｇ^{ｓｈ（ｍ）}）と組（ｇ，ｇ^ｓ，ｇ^ｈ（ｍ），ｇ^ｄ）とは識別困難である。このため、各組の４番目の要素をｍ倍した組（ｇ，ｇ^ｓ，ｇ^ｈ（ｍ），ｍｇ^{ｓｈ（ｍ）}）と組（ｇ，ｇ^ｓ，ｇ^ｈ（ｍ），ｍｇ^ｄ）とも識別困難である。このことは、ｙ＝ｇ^ｓであることを考慮すると、ｇ，ｇ^ｓを既知として、組（ｍｙ^ｈ（ｍ），ｇ^ｈ（ｍ））と組（ｍｇ^ｄ，ｇ^ｈ（ｍ））とが識別困難であることと同義である。このため、組（ｍｙ^ｈ（ｍ），ｇ^ｈ（ｍ））の分布と組（ｍｇ^ｄ，ｇ^ｈ（ｍ））の分布とは等しく、暗号文ｃである組（ｍｙ^ｈ（ｍ），ｇ^ｈ（ｍ））からメッセージｍについての情報は得られない。

このように、具体例２で定義した暗号化関数Ｅは、生成された暗号文からメッセージｍの情報を漏洩しないという性質を満たす。

［変形例等］
復号結果検証装置１の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。

その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。

また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

１ 復号結果検証装置
１１ 送信部
１２ 受信部
１３ 検証情報生成部
１４ 判定部
１５ 出力部
２ 復号装置

Claims (6)

1. 復号装置に暗号文の復号を依頼して、戻ってきた結果を検証する復号結果検証装置であって、
   ｈをハッシュ関数、Ｅ（ｍ，ｒ）を公開鍵と整数ｒを用いてメッセージｍのみを暗号化して暗号文を生成する暗号化関数、Ｅ（ｍ，ｈ（ｍ））を暗号文ｃとして、
   上記暗号化関数Ｅは、生成された暗号文から上記メッセージｍの情報を漏洩しない確率的公開鍵暗号方式であり、
   上記Ｅ（ｍ，ｈ（ｍ））に入力される上記メッセージｍは付加ビットのない平文であり、
   上記暗号文ｃを、上記暗号化関数Ｅに対応する復号関数Ｄで受信した上記暗号文ｃを秘密鍵を用いて復号可能でありその復号結果ｍ’を出力する上記復号装置に送信する送信部と、
   上記復号装置から上記復号結果ｍ’を受信する受信部と、
   上記復号結果ｍ’を用いて上記公開鍵のみで検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する検証情報生成部と、
   上記暗号文ｃと上記検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する判定部と、
   を含む復号結果検証装置。
2. 請求項１の復号結果検証装置において、
   検証する暗号文ｃを生成する上記暗号化関数Ｅ（ｍ，ｒ）は、ｐ，ｑを素数、Ｎ＝ｐｑ、Ｎ^２を上記公開鍵、ｐ−１とｑ−１の最小公倍数であるλを上記秘密鍵、ｇをＺ／Ｎ^２Ｚの可逆元として、ｇ ^ｍ ｒ^Ｎ ｍｏｄ Ｎ^２で表わされるものであり、
   上記暗号文ｃを復号するための上記復号関数Ｄは、下記式により定義されるｍ’の値を計算する関数で表わされるものである、
   ｗ＝ｇ^λ ｍｏｄ Ｎ^２
   ｚ＝（ｗ−１）／Ｎ
   μ＝ｚ^−１ ｍｏｄ Ｎ
   ｕ＝ｃ^λ ｍｏｄ Ｎ^２
   ｖ＝（ｕ−１）／Ｎ
   ｍ’＝ｖμ ｍｏｄ Ｎ
   ことを特徴とする復号結果検証装置。
3. 請求項１の復号結果検証装置において、
   検証する暗号文ｃを生成する上記暗号化関数Ｅ（ｍ，ｒ）は、Ｇを巡回群、ｇを群Ｇの生成元、所定の整数ｓを上記秘密鍵、ｙ＝ｇ^ｓを上記公開鍵として、ｃ _０ ＝ｍｙ^ｒ及びｃ_１＝ｇ^ｒを出力する関数で表わされるものであり、
   上記暗号文ｃは、第一暗号文ｃ_０＝ｍｙ^ｈ（ｍ）及び第二暗号文ｃ_１＝ｇ^ｈ（ｍ） の組で表わされるものであり、
   上記暗号文ｃを復号するための上記復号関数Ｄは、ｃ_０ｃ_１ ^−ｓで表わされるものであり、
   上記検証情報生成部は、第一検証情報ｃ_０’＝ｍ’ｙ^{ｈ（ｍ’）}及び第二検証情報ｃ_１’＝ｇ^{ｈ（ｍ’）}を計算し、
   上記判定部は、上記第一暗号文ｃ_０と上記第一検証情報ｃ_０’とが一致するか、及び、上記第二暗号文ｃ_１と上記第二検証情報ｃ_１’とが一致するかを判定する、
   ことを特徴とする復号結果検証装置。
4. 復号装置に暗号文の復号を依頼して、戻ってきた結果を検証する復号結果検証方法であって、
   ｈをハッシュ関数、Ｅ（ｍ，ｒ）を公開鍵と整数ｒを用いてメッセージｍのみを暗号化して暗号文を生成する暗号化関数、Ｅ（ｍ，ｈ（ｍ））を暗号文ｃとして、
   上記暗号化関数Ｅは、生成された暗号文から上記メッセージｍの情報を漏洩しない確率的公開鍵暗号方式であり、
   上記Ｅ（ｍ，ｈ（ｍ））に入力される上記メッセージｍは付加ビットのない平文であり、
   送信部が、上記暗号文ｃを、上記暗号化関数Ｅに対応する復号関数Ｄで受信した暗号文ｃを秘密鍵を用いて復号可能でありその復号結果ｍ’を出力する上記復号装置に送信する送信ステップと、
   受信部が、上記復号装置から上記復号結果ｍ’を受信する受信ステップと、
   検証情報生成部が、上記公開鍵のみで上記復号結果ｍ’を用いて検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する検証情報生成ステップと、
   判定部が、上記暗号文ｃと上記検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する判定ステップと、
   を含む復号結果検証方法。
5. 復号装置に暗号文の復号を依頼して、戻ってきた結果を検証する復号結果検証システムにおいて、
   ｈをハッシュ関数、Ｅ（ｍ，ｒ）を公開鍵と整数ｒを用いてメッセージｍのみを暗号化して暗号文を生成する暗号化関数、Ｅ（ｍ，ｈ（ｍ））を暗号文ｃとして、
   上記暗号化関数Ｅは、生成された暗号文から上記メッセージｍの情報を漏洩しない確率的公開鍵暗号方式であり、
   上記Ｅ（ｍ，ｈ（ｍ））に入力される上記メッセージｍは付加ビットのない平文であり、
   上記暗号化関数Ｅに対応する復号関数Ｄで受信した上記暗号文ｃを秘密鍵を用いて復号可能でありその復号結果ｍ’を出力する復号装置と、
   上記暗号文ｃを上記復号装置に送信する送信部と、上記復号装置から上記復号結果ｍ’を受信する受信部と、上記公開鍵のみで上記復号結果ｍ’を用いて検証情報Ｅ（ｍ’，ｈ（ｍ’））を計算する検証情報生成部と、上記暗号文ｃと上記検証情報Ｅ（ｍ’，ｈ（ｍ’））とが一致するか判定する判定部と、を含む復号結果検証装置と、
   を含む復号結果検証システム。
6. 請求項１から３の何れかの復号結果検証装置の各部としてコンピュータを機能させるためのプログラム。

Images