(57)【特許請求の範囲】
【請求項１】
暗号化装置が再暗号化装置の秘密鍵に対応する公開鍵を用いて平文データを暗号化処理して得られた暗号文データを前記再暗号化装置に送信し、前記再暗号化装置がこの暗号文データを復号せずに再暗号化鍵により再暗号化処理して得られた再暗号文データを復号装置に送信し、前記復号装置が前記再暗号化装置の公開鍵を用いて前記再暗号文データを検証処理すると共に、前記復号装置が自己の公開鍵に対応する秘密鍵を用いて前記再暗号文データを復号処理して前記平文データを得る再暗号化システムに関し、前記再暗号化鍵生成装置の公開鍵と前記復号装置の秘密鍵を記憶する記憶手段を備えた前記復号装置に用いられる再暗号文検証プログラムであって、
前記復号装置を、
前記再暗号化システムに用いられる再暗号文データの一部と、当該再暗号文データを再暗号化処理する前の暗号文データの暗号化処理に用いられた公開鍵が代入された場合に成立する検証式が予め記述されたプログラムコードを保持する保持手段、
前記保持手段から読み出した検証式に基づき、前記再暗号化装置から受けた再暗号文データの一部と、前記記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵を当該検証式に代入して演算を実行することにより、この検証式が成立するか否かを判定する判定手段、
この判定の結果、前記検証式が成立したとき、前記平文データの暗号化処理に用いられた公開鍵が前記再暗号化鍵生成装置の公開鍵であった旨を示す検証成功を出力する出力手段、
として機能させるための再暗号文検証プログラム。
【請求項２】
請求項１に記載の再暗号文検証プログラムにおいて、
前記再暗号化鍵生成装置の秘密鍵及び公開鍵をそれぞれｘi及びＸiで表し（但し、セキュリティパラメータλに基づき、素数位数ｐ＞２λを満たす双線型写像群をＧ，ＧTで表し、第１生成元をｇ∈Ｇで表したとき、
公開パラメータ（ｐ，λ，Ｇ，ＧT，ｇ，ｕ，ｖ，Sig）
）、
前記平文データをｍ∈ＧTで表し、
前記暗号文データをＣi＝（Ｃ1，Ｃ2，Ｃ3，Ｃ4，σ）で表し（但し、使い捨て署名の署名鍵及び検証鍵をそれぞれｓｓｋ及びｓｖｋで表し、素数ｐに対する乗法群をＺp＊で表し、第１乱数をｒ∈Ｚp＊で表し、ペアリング関数をｅ（ ， ）で表し、第２及び第３生成元をそれぞれｕ，ｖ∈Ｇで表し、前記使い捨て署名の署名生成機能を
【数１】
0005389212.tif 000016
）、
前記復号装置の秘密鍵及び公開鍵をそれぞれｘj及びＸjで表し（但し、
【数２】
0005389212.tif 000017
）、
前記再暗号化鍵を
【数３】
0005389212.tif 000018
で表し、
前記再暗号文データをＣj＝（Ｃ1，Ｃ2’，Ｃ2’’，Ｃ2’’’， Ｃ2V，Ｃ3，Ｃ4，σ）で表すとき（但し、第２乱数をｔ∈Ｚp＊で表したとき、
【数４】
0005389212.tif 000019
）、
前記検証式は、
【数５】
0005389212.tif 000020
で表されることを特徴とする再暗号文検証プログラム。
【請求項３】
請求項１又は請求項２に記載の再暗号文検証プログラムを用いた前記再暗号化装置において、
前記再暗号文検証プログラムを記憶する検証プログラム記憶手段と、
この再暗号文検証プログラムの配信要求を前記復号装置から受けると、前記検証プログラム記憶手段内の再暗号文検証プログラムを当該復号装置に配信する検証プログラム配信手段と、
を備えたことを特徴とする再暗号化装置。
【請求項４】
暗号化装置、再暗号化鍵生成装置、再暗号化装置及び復号装置を備えた再暗号化システムであって、
前記暗号化装置は、
前記再暗号化鍵生成装置の公開鍵を記憶する第１記憶手段と、
前記第１記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵を用いて前記平文データを暗号化処理することにより、暗号文データを得る暗号化手段と、
前記得られた暗号文データを前記再暗号化装置に送信する手段と、
を備え、
前記再暗号化鍵生成装置は、
前記再暗号化鍵生成装置の公開鍵に対応する秘密鍵と、前記復号装置の秘密鍵に対応する公開鍵とを記憶する第２記憶手段と、
前記第２記憶手段から読み出した前記再暗号化鍵生成装置の秘密鍵と前記復号装置の公開鍵とを用いて再暗号化鍵を生成する手段と、
前記生成された再暗号化鍵を前記再暗号化装置に送信する手段と、
を備え、
前記再暗号化装置は、
前記再暗号化鍵生成装置から受けた再暗号化鍵を記憶する第３記憶手段と、
前記暗号化装置から暗号文データを受けると、前記第３記憶手段から読み出した再暗号化鍵を用いて当該暗号文データを復号せずに再暗号化処理することにより、再暗号文データを得る再暗号化手段と、
前記得られた再暗号文データを前記復号装置に送信する手段と、
を備え、
前記復号装置は、
前記再暗号化鍵生成装置の公開鍵と前記復号装置の秘密鍵を記憶する第４記憶手段と、
前記再暗号化装置から再暗号文データを受けると、前記第４記憶手段から読み出した当該復号装置の秘密鍵に基づいて、当該再暗号文データを復号処理することにより、前記平文データを得る復号手段と、
前記再暗号化システムに用いられる再暗号文データの一部と、当該再暗号文データを再暗号化処理する前の暗号文データの暗号化処理に用いられた公開鍵が代入された場合に成立する検証式を予め保持する保持手段と、
前記保持手段から読み出した検証式に基づき、前記再暗号化装置から受けた再暗号文データの一部と、前記第４記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵を当該検証式に代入して演算を実行することにより、この検証式が成立するか否かを判定する判定手段と、
この判定の結果、前記検証式が成立したとき、前記平文データの暗号化処理に用いられた公開鍵が前記再暗号化鍵生成装置の公開鍵であった旨を示す検証成功を出力する出力手段と、
を備えたことを特徴とする再暗号化システム。
【請求項５】
請求項４に記載の再暗号化システムにおいて、
前記暗号化手段は、前記再暗号化装置の公開鍵を前記平文データに埋め込むと、当該埋め込み済みの平文データに対して前記暗号化処理を実行し、
前記復号装置は、
前記保持手段、前記判定手段及び前記出力手段に代えて、
前記復号手段により復号された平文データから前記埋め込まれた公開鍵を抽出する抽出手段と、
前記抽出された公開鍵と、前記第４記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵とを比較する比較手段と、
この比較の結果、両者が一致したとき、前記平文データの暗号化処理に用いられた公開鍵が前記再暗号化鍵生成装置の公開鍵であった旨を示す検証成功を出力する手段と、
を備えたことを特徴とする再暗号化システム。
【請求項６】
鍵生成装置、暗号化装置、再暗号化鍵生成装置、再暗号化装置及び復号装置を備えた再暗号化システムであって、
前記鍵生成装置は、
前記再暗号化システムの各種パラメータ及び、前記再暗号化装置及び復号装置のそれぞれに係る公開鍵と秘密鍵のペアを生成するパラメータ及び鍵生成手段
を備え、
前記暗号化装置は、
前記再暗号化鍵生成装置の公開鍵を記憶する第１記憶手段と、
前記第１記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵を用いて前記平文データを暗号化処理することにより、暗号文データを得る暗号化手段と、
前記得られた暗号文データを前記再暗号化装置に送信する手段と、
を備え、
前記再暗号化鍵生成装置は、
前記再暗号化鍵生成装置の公開鍵に対応する秘密鍵と、前記復号装置の秘密鍵に対応する公開鍵とを記憶する第２記憶手段と、
前記第２記憶手段から読み出した前記再暗号化鍵生成装置の秘密鍵と前記復号装置の公開鍵とを用いて再暗号化鍵を生成する手段と、
前記生成された再暗号化鍵を前記再暗号化装置に送信する手段と、
を備え、
前記再暗号化装置は、
前記再暗号化鍵生成装置から受けた再暗号化鍵を記憶する第３記憶手段と、
前記暗号化装置から暗号文データを受けると、前記第３記憶手段から読み出した再暗号化鍵を用いて当該暗号文データを復号せずに再暗号化処理することにより、再暗号文データを得る再暗号化手段と、
前記得られた再暗号文データを前記復号装置に送信する手段と、
を備え、
前記復号装置は、
前記再暗号化鍵生成装置の公開鍵と前記復号装置の秘密鍵を記憶する第４記憶手段と、
前記再暗号化装置から再暗号文データを受けると、前記第４記憶手段から読み出した当該復号装置の秘密鍵に基づいて、当該再暗号文データを復号処理することにより、前記平文データを得る復号手段と、
前記再暗号化システムに用いられる再暗号文データの一部と、当該再暗号文データを再暗号化処理する前の暗号文データの暗号化処理に用いられた公開鍵が代入された場合に成立する検証式を予め保持する保持手段と、
前記保持手段から読み出した検証式に基づき、前記再暗号化装置から受けた再暗号文データの一部と、前記第４記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵を当該検証式に代入して演算を実行することにより、この検証式が成立するか否かを判定する判定手段と、
この判定の結果、前記検証式が成立したとき、前記平文データの暗号化処理に用いられた公開鍵が前記再暗号化鍵生成装置の公開鍵であった旨を示す検証成功を出力する出力手段と、
を備えたことを特徴とする再暗号化システム。
【請求項７】
暗号化装置、再暗号化鍵生成装置、再暗号化装置及び復号装置を備えた再暗号化システムであって、
前記暗号化装置は、
前記再暗号化鍵生成装置の公開鍵を記憶する第１記憶手段と、
前記第１記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵を用いて前記平文データを暗号化処理することにより、暗号文データを得る暗号化手段と、
前記得られた暗号文データを前記再暗号化装置に送信する手段と、
を備え、
前記再暗号化鍵生成装置は、
前記再暗号化鍵生成装置の公開鍵に対応する秘密鍵と、前記復号装置の秘密鍵に対応する公開鍵とを記憶する第２記憶手段と、
前記第２記憶手段から読み出した前記再暗号化鍵生成装置の秘密鍵と前記復号装置の公開鍵とを用いて再暗号化鍵を生成する手段と、
前記生成された再暗号化鍵を前記復号装置に送信する手段と、
を備え、
前記再暗号化装置は、
前記再暗号化鍵生成装置から受けた再暗号化鍵を記憶する第３記憶手段と、
前記暗号化装置から暗号文データを受けると、前記第３記憶手段から読み出した再暗号化鍵を用いて当該暗号文データを復号せずに再暗号化処理することにより、再暗号文データを得る再暗号化手段と、
前記得られた再暗号文データを前記復号装置に送信する手段と、
を備え、
前記復号装置は、
前記再暗号化鍵生成装置の公開鍵と前記復号装置の秘密鍵を記憶する第４記憶手段と、
前記再暗号化装置から再暗号文データを受けると、前記第４記憶手段から読み出した当該復号装置の秘密鍵に基づいて、当該再暗号文データを復号処理することにより、前記平文データを得る復号手段と、
前記再暗号化システムに用いられる再暗号文データの一部と、当該再暗号文データを再暗号化処理する前の暗号文データの暗号化処理に用いられた公開鍵が代入された場合に成立する検証式を予め保持する保持手段と、
前記保持手段から読み出した検証式に基づき、前記再暗号化装置から受けた再暗号文データの一部と、前記第４記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵を当該検証式に代入して演算を実行することにより、この検証式が成立するか否かを判定する判定手段と、
この判定の結果、前記検証式が成立したとき、前記平文データの暗号化処理に用いられた公開鍵が前記再暗号化鍵生成装置の公開鍵であった旨を示す検証成功を出力する出力手段と、
を備えたことを特徴とする再暗号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、再暗号文検証プログラム、再暗号化装置及び再暗号化システムに関する。
【背景技術】
【０００２】
１９９８年にブレーズ（Blaze）らにより、公開鍵暗号系に関してプロキシ再暗号化（Proxy Re-Encryption）と呼ばれる技術が提案されている。
【０００３】
この技術の基本的なモデルは以下の鍵生成、暗号化、復号、再暗号化鍵生成、再暗号化の５つの関数（以下、アルゴリズムともいう）からなる。鍵生成、暗号化、復号の機能は通常の公開鍵暗号と同様である。
【０００４】
（鍵生成）KeyGen（１k）→（ｐｋ，ｓｋ）
鍵生成アルゴリズムKeyGenは、セキュリティパラメータ１kが入力されると、公開鍵ｐｋと秘密鍵ｓｋの組（ｐｋ，ｓｋ）を出力する。
【０００５】
（暗号化）Enc（ｐｋA，ｍ）→ＣA 
暗号化アルゴリズムEncは、ユーザＡの公開鍵ｐｋAとメッセージｍが入力されると、ユーザＡ宛の暗号文ＣAを出力する。
【０００６】
（復号）Dec（ｓｋA，ＣA）→ｍ
復号アルゴリズムDecは、ユーザＡの秘密鍵ｓｋAと、ユーザＡ宛の暗号文ＣAとが入力されると、メッセージｍを出力する。
【０００７】
（再暗号化鍵生成）ReKeyGen（ｐｋA，ｓｋA，ｐｋB，ｓｋB）→ｒｋA→B 
再暗号化鍵生成アルゴリズムReKeyGenは、ユーザＡの公開鍵ｐｋA、ユーザＡの秘密鍵ｓｋA、ユーザＢの公開鍵ｐｋB、ユーザＢの秘密鍵ｓｋBが入力されると、再暗号化鍵ｒｋA→Bを出力する。
【０００８】
（再暗号化）ReEnc（ｒｋA→B，ＣA）→ＣB 
再暗号化アルゴリズムReEncは、再暗号化鍵ｒｋA→Bと、ユーザＡ宛の暗号文ＣAとが入力されると、ユーザＢ宛の暗号文ＣBを出力する。
【０００９】
以上が基本的なモデルである。但し、再暗号化の実現方式に応じて、関数への入力が異なるモデルや、上記以外の関数や鍵を含むモデルも考えられている。
【００１０】
例えば、再暗号化鍵生成アルゴリズムの入力において、ユーザＢの秘密鍵ｓｋBを不要とした非相互作用的（non-interactive）と呼ばれるモデルや、ユーザＡの秘密鍵ｓｋAに代えて、ユーザＢ宛の再暗号化鍵ｒｋA→BとユーザＣの秘密鍵ｓｋCとが入力されるモデルなども考えられている。
【００１１】
また、再暗号化鍵ｒｋA→Bで暗号文ＣA→ＣBの再暗号化を行える一方で、その逆の暗号文ＣB→ＣAの変換を行えない一方向性（unidirectional）と呼ばれるモデル、逆の変換も行える双方向性（bidirectional）と呼ばれるモデルなども知られている。なお、双方向性モデルでは、再暗号化鍵ｒｋA→BをｒｋA⇔Bと表すことがある。
【００１２】
さらに、公開鍵暗号の中でもＩＤベース暗号に基づく方式も考えられている。その場合、マスター鍵生成のための関数セットアップ（Setup）が増え、鍵生成アルゴリズムKeyGenの入力にマスター鍵とＩＤが追加される。ＩＤベース暗号において、公開鍵ｐｋはＩＤそのものである。
【００１３】
具体的な方式の例としては、一方向性モデルでは非特許文献３，４に記載の方式が、双方向性モデルでは非特許文献５に記載の方式が、ＩＤベース暗号では非特許文献６，７などに記載の方式がそれぞれ知られている。なお、実施形態では非特許文献８に記載の方式を参考にしている。
【００１４】
図９はこのような再暗号化技術を説明するためのコンテンツ配信システムの一例を示す模式図である。このコンテンツ配信システムは、コンテンツプロバイダ１、配信システム２及びユーザ３という３者のエンティティからなる。なお、ユーザ３は、各々のユーザを区別する場合にはユーザＡ又はユーザＢと呼ぶ。
【００１５】
事前準備として、コンテンツプロバイダ１は、配信システム２の公開鍵ｐｋGrを持っているものとする。配信システム２は、配信システム２宛の暗号文コンテンツＥ（ｐｋGr，Ｍ）を特定のユーザＡ又はＢ宛の暗号文コンテンツＥ（ｐｋA，Ｍ）又はＥ（ｐｋB，Ｍ）に再暗号化する再暗号化鍵ｒｋGr→A，ｒｋGr→B，を持っているものとする。各ユーザ３は自分宛の再暗号文コンテンツＥ（ｐｋA，Ｍ）又はＥ（ｐｋB，Ｍ）を復号する秘密鍵ｓｋA又はｓｋBを持っているものとする。その他の各種の鍵やパラメータの説明は省略する。
【００１６】
次に、コンテンツプロバイダ１は、コンテンツＭを配信システム２の公開鍵ｐｋGrで暗号化し、得られた暗号文コンテンツＥ（ｐｋGr，Ｍ）を配信システム２に配布する。
【００１７】
配信システム２は、コンテンツプロバイダ１から暗号文コンテンツＥ（ｐｋGr，Ｍ）を受ける。その後、配信システム２は、例えばユーザＡから受けたコンテンツ要求に対し、特定のユーザＡ宛の再暗号化鍵ｒｋGr→Aに基づいて、暗号文コンテンツＥ（ｐｋGr，Ｍ）をユーザＡ宛の再暗号文コンテンツＥ（ｐｋA，Ｍ）に再暗号化し、得られた再暗号文コンテンツＥ（ｐｋA，Ｍ）をユーザＡに配布する。
【００１８】
ユーザＡは、任意の配信システム２から受けた再暗号文コンテンツＥ（ｐｋA，Ｍ）を自身が保有する秘密鍵ｓｋAで復号し、得られたコンテンツＭを利用する。
【００１９】
以上のようなコンテンツ配信システムは、コンテンツプロバイダ１による暗号化からユーザＡによる復号までの間、コンテンツＭが一度も復号されないため、コンテンツ配信の過程における情報の漏洩を阻止することができる。
【００２０】
また、コンテンツプロバイダ１は、ユーザ３を特定せずに、配信システム２の公開鍵ｐｋGrで暗号化することから、管理する鍵が配信システム２の公開鍵ｐｋGrのみでよいので、鍵管理のコストを低減させることができる。
【００２１】
配信システム２は、暗号文コンテンツＥ（ｐｋGr，Ｍ）を復号せずにユーザ３宛に再暗号化することから、再暗号化に用いるサーバを厳重に管理しなくてもよいので、コストを低減させることができる。
【００２２】
ユーザ３は、単純に配信システム２にコンテンツ要求を出すだけで、これまで同様に任意のコンテンツＭを利用することができる。
【先行技術文献】
【特許文献】
【００２３】
【特許文献１】特開２００４−３６３７７９号公報
【特許文献２】特許第４０１０７６６号公報
【非特許文献】
【００２４】
【非特許文献１】M. Blaze, M. Strauss. Atomic Proxy Cryptography. AT&T Labs Research TR98.5.1, 1997.
【非特許文献２】M. Blaze, G. Bleumer, M. Strauss. Divertible Protocols and Atomic Proxy Cryptography. In Eurocrypt’98, LNCS 1403, pp. 127-144, 1998.
【非特許文献３】G. Ateniese, K. Fu, M. Green, S. Hohenberger. Improved Proxy Re-Encryption Schemes with Applications to Secure Distributed Storage. In NDSS’05, 2005.
【非特許文献４】B. Libert, D. Vergnaud. Tracing Malicious Proxies in Proxy Re-Encryption. In Pairing 2008, 2008.
【非特許文献５】R. Canetti, S. Hohenberger. Chosen-Ciphertext Secure Proxy Re-Encryption. In ACM CCS’07, 2005.
【非特許文献６】M. Green, G. Ateniese. Identity-Based Proxy Re-encryption. In ACNS’07, 2007.
【非特許文献７】T. Matsuo. Proxy Re-encryption Systems for Identity-based Encryption. In Pairing 2007, 2007.
【非特許文献８】Benoit Libert, Damien Vergnaud，”Unidirectional Chosen-Ciphertext Secure Proxy Re-encryption”, Public Key Cryptography 2008, pp.360-279
【非特許文献９】G. Ateniese, S. Hohenberger，”Proxy re-signature: new definitions, algorithm, and applications”, ACM Conference on Computer and Communications Security 2005, pp.310-319
【非特許文献１０】A. Menezes, P. van Oorschot, S. Vanstone, “Handbook of Applied Cryptography”, CRC Press, (1996),
【発明の概要】
【発明が解決しようとする課題】
【００２５】
しかしながら以上のような再暗号化技術は、通常は特に問題ないが、本発明者の検討によれば、次のような不都合がある。
【００２６】
従来の暗号システムは、暗号化する人と復号する人という２者のエンティティからなるため、復号する人を特定できればよい。これに対し、再暗号化技術において復号する人は、誰から再暗号文データを受けるか分からない場合には、元々誰宛の暗号文データを再暗号化した状態で受け取って復号するのかを検証できない不都合がある。
【００２７】
例えば、再暗号化技術では、再暗号化鍵を生成する機能と再暗号化を行う機能とを分離できるので、これらの機能を別のエンティティに実装する場合がある。この場合、復号するユーザは、再暗号化を行ったエンティティから再暗号文コンテンツを受けたとしても、元々誰宛の暗号文コンテンツを再暗号化した状態で受けたのかを検証する手段がない。
【００２８】
仮に、漏洩した暗号文コンテンツを再暗号化した状態でユーザ、または漏洩した原因を調査する第三者が受けたとしても、再暗号化した状態から元々誰宛の暗号文コンテンツだったのかを検証できないため、漏洩元を特定することが困難となる。
【００２９】
なお、上述した不都合の解消を図る技術の候補として、例えばプロキシ再署名（Proxy Re-Signature）が知られている。但し、この技術は署名の付け替えを行う方式であるため、前述した再暗号化機能を実現する再暗号化システム(Proxy Re-encryption)と再署名システム(Proxy Re-Signature)とを組み合わせて実現する必要がある。しかしながら、この組み合わせは、両者の機能を実現するための計算量やデータ長が大きくなるばかりでなく、両者のシステムを連携させる好適な方法が知られていないことから、実現が困難である。
【００３０】
また、不都合の解消を図る別の候補として、再暗号化システム(Proxy Re-Encryption)に既存の電子署名システムを組み合わせる技術が提案されている。しかしながら、この技術は、暗号化する人と再暗号化する人がどのデータにどのように電子署名を施せばよいのかが現状では知られていないため、実現が困難である。
【００３１】
すなわち、再暗号化技術は、前述した不都合が未だ解消されていない状況にある。
【００３２】
本明細書に開示した実施形態は、再暗号文データを受けた復号装置が、元々誰宛の暗号文データが再暗号化されたのかを検証し得る再暗号文検証プログラム、再暗号化装置及び再暗号化システムを提供することを目的とする。
【００３３】
そのため、本明細書では、再暗号化鍵を生成する機能と再暗号化を行う機能とを別のエンティティにより行う場合について説明する。
【課題を解決するための手段】
【００３４】
実施形態の再暗号化システムは、暗号化装置、再暗号化鍵生成装置、再暗号化装置及び復号装置を備えている。
【００３５】
前記暗号化装置においては、第１記憶手段が前記再暗号化装置の公開鍵を記憶する。暗号化手段は、前記第１記憶手段から読み出した前記再暗号化装置の公開鍵を用いて前記平文データを暗号化処理することにより、暗号文データを得る。前記暗号化装置は、前記得られた暗号文データを前記再暗号化装置に送信する。
【００３６】
前記再暗号化鍵生成装置においては、第２記憶手段が、前記再暗号化装置の公開鍵に対応する秘密鍵と、前記復号装置の秘密鍵に対応する公開鍵とを記憶する。前記再暗号化鍵生成装置は、前記第２記憶手段から読み出した前記再暗号化装置の秘密鍵と前記復号装置の公開鍵とを用いて再暗号化鍵を生成する。前記再暗号化鍵生成装置は、前記生成された再暗号化鍵を前記再暗号化装置に送信する。
【００３７】
前記再暗号化装置においては、第３記憶手段が、前記再暗号化鍵生成装置から受けた再暗号化鍵を記憶する。再暗号化手段は、前記暗号化装置から暗号文データを受けると、前記第３記憶手段から読み出した再暗号化鍵を用いて当該暗号文データを復号せずに再暗号化処理することにより、再暗号文データを得る。前記再暗号化装置は、前記得られた再暗号文データを前記復号装置に送信する。
【００３８】
前記復号装置は、第４記憶手段、復号手段、保持手段、判定手段及び出力手段を備えている。第４記憶手段は、前記再暗号化装置の公開鍵と前記復号装置の秘密鍵を記憶する。
【００３９】
復号手段は、前記再暗号化装置から再暗号文データを受けると、前記第４記憶手段から読み出した当該復号装置の秘密鍵に基づいて、当該再暗号文データを復号処理することにより、前記平文データを得る。
【００４０】
保持手段は、前記再暗号化システムに用いられる再暗号文データの一部と、当該再暗号文データを再暗号化処理する前の暗号文データの暗号化処理に用いられた公開鍵と、当該再暗号文データを復号可能な秘密鍵とが代入された場合に成立する検証式を予め保持する。
【００４１】
判定手段は、前記保持手段から読み出した検証式に基づき、前記再暗号化装置から受けた再暗号文データの一部と、前記第４記憶手段から読み出した前記再暗号化鍵生成装置の公開鍵と前記復号装置の秘密鍵とを当該検証式に代入して演算を実行することにより、この検証式が成立するか否かを判定する。
【００４２】
出力手段は、この判定の結果、前記検証式が成立したとき、前記平文データの暗号化処理に用いられた公開鍵が前記再暗号化鍵生成装置の公開鍵であった旨を示す検証成功を出力する。
【図面の簡単な説明】
【００４３】
【図１】第１の実施形態に係る再暗号化システムの構成を示す模式図である。
【図２】同実施形態における鍵セットアップ処理の動作を説明するためのシーケンス図である。
【図３】同実施形態における暗号化処理の動作を説明するためのシーケンス図である。
【図４】同実施形態における再暗号化鍵生成処理の動作を説明するためのシーケンス図である。
【図５】同実施形態における再暗号化処理の動作を説明するためのシーケンス図である。
【図６】同実施形態における復号処理の動作を説明するためのシーケンス図である。
【図７】第２の実施形態における暗号化処理の動作を説明するためのシーケンス図である。
【図８】第２の実施形態における復号処理の動作を説明するためのシーケンス図である。
【図９】一般的な再暗号化技術を説明するためのコンテンツ配信システムの一例を示す模式図である。
【発明を実施するための形態】
【００４４】
以下、各実施形態について図面を用いて説明する。なお、以下の各装置は、装置毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。
【００４５】
（第１の実施形態）
図１は第１の実施形態に係る再暗号化システムの構成を示す模式図である。この再暗号化システムは、鍵生成装置１０、暗号化装置２０、再暗号化鍵生成装置３０、再暗号化装置４０及び復号装置５０を備えている。ここで、鍵生成装置１０は、再暗号化システムの各種パラメータ及び各装置４０，５０の公開鍵・秘密鍵のペアを生成する。
【００４６】
暗号化装置２０は、再暗号化鍵生成装置３０の秘密鍵に対応する公開鍵を用いて平文データを暗号化処理して得られた暗号文データを再暗号化装置４０に送信する。
【００４７】
再暗号化鍵生成装置３０は、再暗号化鍵生成装置３０の秘密鍵と復号装置５０の公開鍵とを用いて再暗号化鍵を生成し、その後その再暗号化鍵を再暗号化装置４０に送信する。
【００４８】
再暗号化装置４０は、暗号化装置２０から受けた暗号文データを復号せずに、再暗号化鍵生成装置３０から送信された再暗号化鍵により再暗号化処理して得られた再暗号文データを復号装置５０に送信する。
【００４９】
復号装置５０は、再暗号化鍵生成装置３０の公開鍵を用いて再暗号文データを検証処理すると共に、自装置５０の公開鍵に対応する秘密鍵を用いて再暗号文データを復号処理して平文データを得る。なお、再暗号化鍵生成装置３０、再暗号化装置４０及び復号装置５０は、それぞれ複数台が設けられていてもよいが、ここでは一台ずつ設けられている場合を例に挙げて述べる。
【００５０】
続いて、各装置１０〜５０の構成を具体的に説明する。
【００５１】
鍵生成装置１０は、鍵生成パラメータ記憶部１１、一時データ記憶部１２、公開パラメータ生成部１３、公開鍵・秘密鍵生成部１４、通信部１５及び制御部１６を備えている。
【００５２】
ここで、鍵生成パラメータ記憶部１１は、鍵生成パラメータを記憶する記憶装置である。
【００５３】
一時データ記憶部１２は、各生成部１３，１４の処理途中及び処理結果などの一時データを記憶する記憶装置である。
【００５４】
公開パラメータ生成部１３は、鍵生成の公開パラメータを生成する。
【００５５】
公開鍵・秘密鍵生成部１４は、ユーザ宛の公開鍵・秘密鍵を生成する。
【００５６】
通信部１５は、他の装置２０〜５０と通信するための通信インタフェースであり、例えば、制御部１６に制御されて一時データ記憶部１２内の各３０，５０の公開鍵・秘密鍵のペアを当該各装置３０，５０に送信する機能と、制御部１６に制御されて一時データ記憶部１２内の再暗号化鍵生成装置３０の公開鍵を暗号化装置２０に送信する機能と、をもっている。なお、以下の説明では、送受信時の冗長な記載を避ける観点から、送受信の際に、通信部１５を介する旨の記載を省略する場合がある。これは他の装置２０〜５０の通信部についても同様である。
【００５７】
制御部１６は、図２に示す動作を実行するように、各部１１〜１５を制御する機能をもっている。
【００５８】
暗号化装置２０は、一時データ記憶部２１、通信部２２、暗号化データ生成部２３、暗号文生成部２４及び制御部２５を備えている。
【００５９】
ここで、一時データ記憶部２１は、鍵生成装置１０から受けた再暗号化鍵生成装置３０の公開鍵や、各生成部２３，２４の処理途中及び処理結果などの一時的なデータ（以下、一時データともいう）を記憶する記憶装置である。
【００６０】
通信部２２は、他の装置１０，３０〜５０と通信するための通信インタフェースであり、例えば、鍵生成装置１０に公開された再暗号化鍵生成装置３０の公開鍵を取得して一時データ記憶部２１に書き込む機能や、制御部２５に制御されて一時データ記憶部２１内の暗号文データを再暗号化装置４０に送信する機能をもっている。
【００６１】
暗号化パラメータ生成部２３は、暗号化パラメータを生成する機能をもっている。
【００６２】
暗号文生成部２４は、一時データ記憶部２１から読み出した再暗号化鍵生成装置３０の公開鍵を用いて平文データを暗号化処理することにより、暗号文データを生成する機能と、得られた暗号文データを一時データ記憶部２１に書き込む機能とをもっている。
【００６３】
制御部２５は、図３に示す動作を実行するように、各部２１〜２４を制御する機能をもっている。
【００６４】
再暗号化鍵生成装置３０は、秘密鍵記憶部３１、一時データ記憶部３２、通信部３３、再暗号化鍵生成部３４及び制御部３５を備えている。
【００６５】
秘密鍵記憶部３１は、鍵生成装置１０から受けた再暗号化鍵生成装置３０の秘密鍵を記憶する記憶装置である。
【００６６】
一時データ記憶部３２は、鍵生成装置１０から受けた復号装置５０の公開鍵や、再暗号化鍵生成部３４の処理途中及び処理結果などの一時データを記憶する記憶装置である。
【００６７】
通信部３３は、他の装置１０，２０，４０，５０と通信するための通信インタフェースであり、例えば制御部３５に制御されて一時データ記憶部３２内の再暗号化鍵を再暗号化装置４０に送信する機能をもっている。
【００６８】
再暗号化鍵生成部３４は、秘密鍵記憶部３１から読み出した再暗号化鍵生成装置３０の秘密鍵と、一時データ記憶部３２から読み出した復号装置５０の公開鍵とを用いて再暗号化鍵を生成する機能と、この再暗号化鍵を一時データ記憶部３２に書き込む機能とをもっている。
【００６９】
制御部３５は、図４に示す動作を実行するように、各部３１〜３４を制御する機能をもっている。
【００７０】
再暗号化装置４０は、再暗号化鍵記憶部４１、一時データ記憶部４２、通信部４３、再暗号化処理部４４、検証プログラム記憶部４５、配信部４６及び制御部４７を備えている。
【００７１】
再暗号化鍵記憶部４１は、再暗号化鍵生成装置３０から受けた再暗号化鍵を記憶する記憶装置である。
【００７２】
一時データ記憶部４２は、再暗号化処理部４４の処理途中及び処理結果などの一時データを記憶する記憶装置である。
【００７３】
通信部４３は、他の装置１０〜３０，５０と通信するための通信インタフェースであり、例えば、暗号化装置２０から受けた暗号文データを再暗号化処理部４４に送出する機能と、制御部４７に制御されて一時データ記憶部４２内の再暗号文データを復号装置５０に送信する機能と、配信部４６に制御されて検証プログラム記憶部４５内の再暗号文検証プログラムを復号装置５０に送信する機能とをもっている。
【００７４】
再暗号化処理部４４は、暗号化装置２０から暗号文データを受けると、再暗号化鍵記憶部４１から読み出した再暗号化鍵を用いて当該暗号文データを復号せずに再暗号化処理することにより、再暗号文データを得る機能と、得られた再暗号文データを一時データ記憶部４２に書き込む機能とをもっている。
【００７５】
検証プログラム記憶部４５は、再暗号文検証プログラムを記憶する記憶装置である。なお、再暗号化鍵記憶部４１及び検証プログラム記憶部４５は、同一の記憶装置における別々の記憶領域として実現してもよく、別々の記憶装置として実現してもよい。
【００７６】
配信部４６は、この再暗号文検証プログラムの配信要求を復号装置５０から受けると、検証プログラム記憶部４５内の再暗号文検証プログラムを通信部４３から当該復号装置５０に配信する機能をもっている。
【００７７】
なお、検証プログラム記憶部４５は、再暗号化装置４０にあり、そこから検証プログラム記憶部４５内の再暗号文検証プログラムが配信部４６を通じて配信されることになっているが、再暗号化装置４０以外から配信されても良い。上記で説明したのはあくまでも実施形態の一例であり、再暗号化装置４０以外から配信されることも考えられるからである。具体的には、鍵生成装置１０から以下で説明する復号装置５０への配信や、再暗号化鍵生成装置３０から以下で説明する復号装置５０への配信も考えられる。
【００７８】
制御部４７は、再暗号文検証プログラムを配信する動作（図示せず）と図５に示す動作を実行するように、各部４１〜４６を制御する機能をもっている。
【００７９】
復号装置５０は、秘密鍵記憶部５１、一時データ記憶部５２、通信部５３、復号処理部５４、暗号文検証処理部５５及び制御部５６を備えている。
【００８０】
秘密鍵記憶部５１は、鍵生成装置１０から受けた自装置５０の秘密鍵を記憶する記憶装置である。
【００８１】
一時データ記憶部５２は、鍵生成装置１０から受けた自装置５０の公開鍵及び再暗号化鍵生成装置３０の公開鍵や、復号処理部５４及び暗号文検証処理部５５の処理途中及び処理結果などの一時データを記憶する記憶装置である。
【００８２】
通信部５３は、他の装置１０〜４０と通信するための通信インタフェースであり、例えば、鍵生成装置１０から受けた自装置５０の秘密鍵を秘密鍵記憶部５１に書き込む機能と、鍵生成装置１０から受けた自装置５０の公開鍵及び再暗号化鍵生成装置３０の公開鍵を一時データ記憶部５２に書き込む機能と、再暗号化装置４０から受けた再暗号化データを復号処理部５４に送出する機能とをもっている。
【００８３】
復号処理部５４は、再暗号化装置４０から再暗号文データを受けると、秘密鍵記憶部５１から読み出した当該復号装置５０の秘密鍵に基づいて、当該再暗号文データを復号処理することにより、平文データを得る機能と、得られた平文データを一時データ記憶部５２に書き込む機能とをもっている。
【００８４】
暗号文検証処理部５５は、再暗号化システムに用いられる再暗号文データの一部と、当該再暗号文データを再暗号化処理する前の暗号文データの暗号化処理に用いられた公開鍵と、当該再暗号文データを復号可能な秘密鍵とが代入された場合に成立する検証式を予め保持する保持機能と、保持機能から読み出した検証式に基づき、再暗号化装置から受けた再暗号文データの一部と、一時データ記憶部５２から読み出した再暗号化鍵生成装置３０の公開鍵と秘密鍵記憶部５１内の復号装置５０の秘密鍵とを当該検証式に代入して演算を実行することにより、この検証式が成立するか否かを判定する判定機能と、この判定の結果、検証式が成立したとき、平文データの暗号化処理に用いられた公開鍵が再暗号化鍵生成装置３０の公開鍵であった旨を示す検証成功を出力する機能とをもっている。なお、検証式を予め保持する保持機能は、検証式が予め記述されたプログラムコードを保持する保持機能と読み替えてもよい。
【００８５】
制御部５６は、図６に示す動作を実行するように、各部５１〜５５を制御する機能をもっている。
【００８６】
次に、以上のように構成された再暗号化システムの動作を図２乃至図６のシーケンス図を用いて説明する。なお、復号装置５０においては、予め再暗号文検証プログラムの配信要求を再暗号化装置４０に送信しており、再暗号化装置４０の配信部４６から受信した再暗号文検証プログラムを実行中であるものとする。
【００８７】
また、以下の動作は（１）鍵セットアップ処理、（２）暗号化処理、（３）再暗号化鍵生成処理、（４）再暗号化処理、（５）復号処理の手順で実行される場合を例に挙げて述べる。但し、以下の動作は、必ずしも上記手順で処理を実行しなくてもよい。例えば、再暗号化鍵生成は、暗号化処理の前に実行されてもよい。また、再暗号化処理が実行されずに、暗号文データが復号されてもよい。
【００８８】
また、以下の動作は、復号装置５０内の暗号文検証処理部５５の処理を除き、非特許文献８に記載の技術を例に用いている。すなわち、暗号文検証処理部５５の処理以外の処理については、非特許文献８を補足的に参照して理解を深めることができる。
【００８９】
（１）鍵セットアップ処理は、鍵生成装置１０により、図２及び以下の各ステップＳＴ１〜ＳＴ１２に示すように実行される。
【００９０】
始めに、鍵生成装置１０の公開パラメータ生成部１３は、公開パラメータ（ｐ，λ，Ｇ，ＧT，ｇ，ｕ，ｖ，Sig）を生成する（ＳＴ１）。具体的には、公開パラメータ生成部１３は、予め鍵パラメータ記憶部１１に記憶したセキュリティパラメータλに基づいて、素数位数ｐ＞２λを満たす双線型写像群(bilinear map groups)（Ｇ，ＧT）、生成元ｇ，ｕ，ｖ∈Ｇ、強偽造不可能性を満たす使い捨て署名（one-time signature）
【数１】
0005389212.tif 000002
【００９１】
使い捨て署名については非特許文献１０に詳しい。また、Ｇ，ＧTは楕円曲線で定義される群集合であり、次式に示す如きペアリング関数に用いられる。
【００９２】
ペアリング関数：ｅ（ｇ1，ｇ2）＝ｇT 
但し、ｇ1，ｇ2∈Ｇ、ｇT∈ＧT 
このペアリング関数は、次式に示す如き性質がある。
【００９３】
ｅ（ｇa，ｇ）＝ｅ（ｇ，ｇa）＝ｅ（ｇ，ｇ）a 
但し、ｇ∈Ｇ、ａ∈Ｚp 
続いて、公開パラメータ生成部１３は、生成した公開パラメータを一時データ記憶部１２に書き込む。鍵生成装置１０は、一時データ記憶部１２内の公開パラメータ（ｐ，λ，Ｇ，ＧT，ｇ，ｕ，ｖ，Sig）を公開する（ＳＴ２）。
【００９４】
また、公開鍵・秘密鍵生成部１４は、再暗号化鍵生成装置３０の識別情報をｉとしたとき、再暗号化鍵生成装置３０の秘密鍵ｘｉ∈Ｚp＊を生成し、この秘密鍵ｘｉを用いて再暗号化鍵生成装置３０の公開鍵
【数２】
0005389212.tif 000003
【００９５】
を生成する（ＳＴ７）。なお、Ｚp＊はＺpかつｐと互いに素な整数の集合（＝（Ｚ/pＺ）＊）であり、素数ｐに対する乗法群Ｚp＊と呼んでもよい。Ｚpは０以上ｐ未満の整数の集合（＝（Ｚ/pＺ）である。
【００９６】
続いて、公開鍵・秘密鍵生成部１４は、生成した公開鍵・秘密鍵のペアを一時データ記憶部１２に書き込む。通信部１５は、制御部１６に制御されて一時データ記憶部１２内の秘密鍵ｘｉを再暗号化鍵生成装置３０に送信する（ＳＴ８）。鍵生成装置１０は、一時データ記憶部１２内の再暗号化鍵生成装置３０の公開鍵Ｘｉを公開する（ＳＴ９）。
【００９７】
また同様に、公開鍵・秘密鍵生成部１４は、復号装置５０の識別情報をｊとしたとき、復号装置５０の秘密鍵ｘj∈Ｚp＊を生成し、この秘密鍵ｘjを用いて復号装置５０の公開鍵
【数３】
0005389212.tif 000004
【００９８】
を生成する（ＳＴ１０）。
【００９９】
続いて、公開鍵・秘密鍵生成部１４は、生成した公開鍵・秘密鍵のペアを一時データ記憶部１２に書き込む。通信部１５は、制御部１６に制御されて一時データ記憶部１２内の秘密鍵ｘjを復号装置５０に送信する（ＳＴ１１）。鍵生成装置１０は、一時データ記憶部１２内の復号装置５０の公開鍵Ｘjを公開する（ＳＴ１２）。また、所望により、暗号化装置２０の秘密鍵ｘh及び公開鍵Ｘhについても各ステップＳＴ１０〜ＳＴ１２と同様の処理を実行して暗号化装置２０に秘密鍵ｘhを送信し、公開鍵Ｘhを公開してもよい。
【０１００】
以上により、鍵セットアップ処理が完了する。以後、各装置２０，３０，４０，５０では、各ステップＳＴ２，ＳＴ９，ＳＴ１２で公開された公開パラメータ及び公開鍵を適宜、取得して利用することができる。
【０１０１】
（２）暗号化処理は、暗号化装置２０により、図３及び以下の各ステップＳＴ２１〜ＳＴ２４に示すように実行される。
【０１０２】
すなわち、暗号化装置２０の暗号化パラメータ生成部２３は、公開パラメータにおけるセキュリティパラメータλ及び鍵ペア生成機能
【数４】
0005389212.tif 000005
【０１０３】
を生成し（ＳＴ２１）、第１暗号化データＣ1に検証鍵ｓｖｋをセットする（Ｃ1＝ｓｖｋ）。
【０１０４】
また、暗号化パラメータ生成部２３は、第１乱数ｒ∈Ｚp＊を生成して暗号文生成部２４に送出する。
【０１０５】
暗号文生成部２４は、この第１乱数ｒに基づき、平文データとしてのメッセージｍ∈ＧT に対して、以下の第２、第３及び第４暗号化データＣ2，Ｃ3，Ｃ4を生成する（ＳＴ２２）。
【数５】
0005389212.tif 000006
【０１０６】
具体的にはステップＳＴ２２において、暗号化パラメータ生成部２３は、再暗号化鍵生成装置３０の公開鍵Ｘiと、第１乱数ｒとに基づいて、第２暗号化データＣ2を生成する。また、暗号文生成部２４は、公開パラメータにおける生成元ｇと、第１乱数ｒと、メッセージｍとに基づき、ペアリング関数によって第３暗号化データＣ3を生成する。さらに、暗号文生成部２４は、公開パラメータにおける生成元ｕ，ｖと、ステップＳＴ２１で生成した検証鍵ｓｖｋと、第１乱数ｒとに基づいて、第４暗号化データＣ4を生成する。
【０１０７】
ステップＳＴ２２の終了後、暗号文生成部２４は、第３及び第４暗号化データＣ3，Ｃ4に対し、公開パラメータにおける署名生成機能
【数６】
0005389212.tif 000007
【０１０８】
しかる後、暗号文生成部２４は、これら第１乃至第４暗号化データＣ1〜Ｃ4と使い捨て署名σとを含む暗号文データＣi＝（Ｃ1，Ｃ2，Ｃ3，Ｃ4，σ）を生成し、得られた暗号文データを一時データ記憶部２１に書き込む。
【０１０９】
通信部２２は、制御部２５に制御されて一時データ記憶部２１内の暗号文データＣiを再暗号化装置４０に送信する（ＳＴ２４）。
【０１１０】
以上により、暗号化処理が完了する。
【０１１１】
（３）再暗号化鍵生成処理は、再暗号化鍵生成装置３０により、図４及び以下の各ステップＳＴ３１〜ＳＴ３３に示すように実行される。
【０１１２】
すなわち、再暗号化鍵生成装置３０の通信部３３は、制御部３５に制御されて、鍵生成装置１０から公開された復号装置５０の公開鍵Ｘjを取得して一時データ記憶部３２に書き込む（ＳＴ３１）。また、通信部３３は、前述したステップＳＴ５のとき、再暗号化鍵生成装置３０の秘密鍵ｘiを鍵生成装置１０から受信して秘密鍵記憶部３１に書き込んでいる。
【０１１３】
再暗号化鍵生成部３４は、秘密鍵記憶部３１内の再暗号化鍵生成装置３０の秘密鍵ｘiと、一時データ記憶部３２内の復号装置５０の公開鍵Ｘjから、再暗号化鍵Ｒijを次式に示すように生成する（ＳＴ３２）。
【数７】
0005389212.tif 000008
【０１１４】
しかる後、再暗号化鍵生成部３４は、生成した再暗号化鍵Ｒijを一時データ記憶部３２に書き込む。通信部３３は、制御部３５に制御されて、一時データ記憶部３２内の再暗号化鍵Ｒijを再暗号化装置４０に送信する（ＳＴ３３）。
【０１１５】
以上により、再暗号化鍵生成処理が完了する。
【０１１６】
（４）再暗号化処理は、再暗号化装置４０により、図５及び以下の各ステップＳＴ４１〜ＳＴ４３に示すように実行される。
【０１１７】
暗号化装置４０の通信部４３は、ステップＳＴ２４で送信された暗号文データＣiと、ステップＳＴ３３で送信された再暗号化鍵Ｒijとをそれぞれ一時データ記憶部４２に書き込む。
【０１１８】
再暗号化処理部４４は、公開パラメータと次の検証式を用い、一時データ記憶部４２内の暗号文データＣiを検証する（ＳＴ４１）。ここで、２つの検証式が成立すれば検証は成功し、１つでも成立しない検証式があれば検証は失敗する。
【数８】
0005389212.tif 000009
【０１１９】
再暗号化処理部４４は、検証に成功すると、第２乱数ｔ∈Ｚp＊を生成し、次式に示すように、第１、第２、第３及び第４再暗号化データＣ2’，Ｃ2’’，Ｃ2’’’ ，Ｃ2Vを生成する（ＳＴ４２）。
【数９】
0005389212.tif 000010
【０１２０】
具体的にはステップＳＴ４２において、再暗号化処理部４４は、再暗号化鍵生成装置３０の公開鍵Ｘiと、第２乱数ｔとに基づいて、第１再暗号化データＣ2’を生成する。また、再暗号化処理部４４は、再暗号化鍵Ｒij及び第２乱数ｔに基づいて、第２再暗号化データＣ2’’を生成する。さらに、再暗号化処理部４４は、第２暗号化データＣ2及び第２乱数ｔに基づいて、第３再暗号化データＣ2’’’を生成する。さらに、再暗号化処理部４４は、第２乱数ｔを用いて、第４再暗号化データＣ2Vを生成する。
【０１２１】
ステップＳＴ４２の終了後、再暗号化処理部４４は、これら第１乃至第４再暗号化データＣ2’〜Ｃ2’’’、Ｃ2Vを、暗号文データＣi内の第２暗号化データＣ2と置換して再暗号文データＣj＝（Ｃ1，Ｃ2’，Ｃ2’’，Ｃ2’’’，Ｃ２V，Ｃ3，Ｃ4，σ）を生成し、得られた暗号文データを一時データ記憶部４２に書き込む。
【０１２２】
通信部４３は、制御部４７に制御されて一時データ記憶部４２内の再暗号文データＣjを復号装置５０に送信する（ＳＴ４３）。
【０１２３】
以上により、再暗号化処理が完了する。
【０１２４】
（５）復号処理は、復号装置５０により、図６及び以下のステップＳＴ５１〜ＳＴ５４に示すように実行され、ステップＳＴ５４が失敗した場合には更にステップＳＴ５５，ＳＴ５６が実行される。
【０１２５】
すなわち、復号装置５０の通信部５３は、ステップＳＴ４３で送信された再暗号文データＣjを受信して一時データ記憶部５２に書き込む。
【０１２６】
復号処理部５４は、公開パラメータ及び自装置５０の公開鍵Ｘjと次の検証式を用い、一時データ記憶部５２内の再暗号文データＣjを検証する（ＳＴ５１）。ここで、３つの検証式が成立すれば検証は成功し、１つでも成立しない検証式があれば検証は失敗する。
【数１０】
0005389212.tif 000011
【０１２７】
復号処理部５４は、検証に成功すると、自装置の秘密鍵ｘjに基づいて、次式に示すように、再暗号文データＣjからメッセージｍを復号する（ＳＴ５２）。
【数１１】
0005389212.tif 000012
【０１２８】
一方、通信部５３は、制御部５６に制御され、鍵生成装置１０から公開された再暗号化鍵生成装置３０の公開鍵Ｘiを取得して一時データ記憶部５２に書き込む。ここで、再暗号化鍵生成装置３０の公開鍵Ｘiは、再暗号文データＣjが再暗号化処理される前の暗号文データＣiの宛先と思われる識別情報ｉをもつ装置の公開鍵Ｘiに相当する。
【０１２９】
暗号文検証処理部５５は、再暗号化システムに用いられる再暗号文データＣjの一部と、当該再暗号文データＣjを再暗号化処理する前の暗号文データＣiの暗号化処理に用いられた公開鍵Ｘiが代入された場合に成立する次式の如き検証式を予め保持している。
【数１２】
0005389212.tif 000013
【０１３０】
続いて、暗号文検証処理部５５は、前述した検証式に基づき、再暗号化装置４０から受けた再暗号文データＣjの一部（Ｃ2’，Ｃ2V）と、一時データ記憶部５２から読み出した再暗号化鍵生成装置３０の公開鍵Ｘiを当該検証式に代入して演算を実行することにより、この検証式が成立するか否かを判定して再暗号文データが元々誰宛の暗号文だったかを検証する（ＳＴ５４）。
【０１３１】
暗号文検証処理部５５は、この判定の結果、検証式が成立したとき、平文データとしてのメッセージｍの暗号化処理に用いられた公開鍵が再暗号化鍵生成装置３０の公開鍵Ｘiであった旨を示す検証成功を出力する。
【０１３２】
また、ステップＳＴ５４の判定の結果、検証式が成立しないとき、新たに別の装置（例、図示しない他の再暗号化装置）の公開鍵を取得し（ＳＴ５５）、ステップＳＴ５４と同様の検証を繰り返すことにより（ＳＴ５６）、検証式が成立する公開鍵をもつ再暗号化装置を特定する。
【０１３３】
上述したように本実施形態によれば、再暗号化システムに用いられる再暗号文データＣjの一部と、当該再暗号文データＣjを再暗号化処理する前の暗号文データＣiの暗号化処理に用いられた公開鍵Ｘiと、当該再暗号文データＣjを復号可能な秘密鍵ｘjとが代入された場合に成立する検証式を予め保持して当該検証式を検証する暗号文検証処理部５５を復号装置５０が備えた構成により、再暗号文データを受けた復号装置が、元々誰宛の暗号文データが再暗号化されたのかを検証することができる。
【０１３４】
なお、本実施形態は、適宜、処理の順番を変更してもよい。例えば、復号処理と暗号文検証処理の順番を変更してもよい。同様に、再暗号化鍵生成処理の順番を暗号化処理よりも前に変更してもよい。
【０１３５】
また、本実施形態は、非特許文献８にあるように再暗号化せずに暗号文データを復号する形態に変更してもよい。この場合、メッセージｍは、復号装置５０ではなく、再暗号化鍵生成装置３０が有する秘密鍵ｘｉにより復号される。例えば、再暗号化鍵生成装置３０は、ステップＳＴ４１と同様に暗号文データを検証した後、次式に基づいて、メッセージｍを復号する。
【数１３】
0005389212.tif 000014
【０１３６】
すなわち、本実施形態の再暗号化システムにおいて、非特許文献８に記載の技術に、再暗号化処理部４４でＣ２Vを生成する処理および暗号文検証処理部５５を付加すると実施することができる。
【０１３７】
これに加え、本実施形態では、再暗号化鍵生成装置３０が再暗号化処理を実行せずに暗号文データを復号する場合でも、次式に示すように暗号文データを検証すると、元々暗号文データに用いられていた公開鍵が、自身の装置（再暗号化鍵生成装置３０）の公開鍵Ｘiであることを確認することができる。
【数１４】
0005389212.tif 000015
【０１３８】
（第２の実施形態）
次に、第２の実施形態に係る再暗号化システムについて、前述した図１を用いて説明する。本実施形態は、第１の実施形態の変形例であり、予めメッセージｍに再暗号化鍵生成装置３０の公開鍵Ｘiを埋め込んでおく構成により、任意の再暗号化システムにおいて、元々誰宛の暗号文データであったかを検証可能にしたものである。
【０１３９】
具体的には、暗号化装置２０の暗号文生成部２４は、再暗号化鍵生成装置３０の公開鍵Ｘiを平文データとしてのメッセージｍに埋め込むと、当該埋め込み済みのメッセージｍに対して、前述した暗号化処理を実行する機能をもっている。ここで、埋め込む処理としては、例えば、電子透かしの生成処理を用いてもよく、あるいは単に、メッセージｍに公開鍵Ｘi又は公開鍵Ｘiの暗号文を追加（連結）する処理を用いてもよい。公開鍵Ｘiの暗号文は、例えば、暗号文生成部２４が自装置２０の秘密鍵ｘhで再暗号化鍵生成装置３０の公開鍵Ｘiを暗号化して作成された場合には、復号装置５０において、暗号化装置２０の公開鍵Ｘhで復号されることにより、再暗号化鍵生成装置３０の公開鍵Ｘiが抽出可能となっている。
【０１４０】
これに伴い、暗号化装置２０の制御部２５は、図７に示す動作を実行するように、各部２１〜２４を制御する機能をもっている。
【０１４１】
一方、復号装置５０の暗号文検証処理部５５は、前述した保持機能、判定機能及び出力機能に代えて、前述した復号機能により復号されたメッセージｍから埋め込まれた公開鍵Ｘiを抽出する抽出機能と、当該抽出された公開鍵Ｘiと、一時データ記憶部５２から読み出した再暗号化鍵生成装置３０の公開鍵Ｘiとを比較する比較機能と、この比較の結果、両者が一致したとき、メッセージｍの暗号化処理に用いられた公開鍵Ｘiが再暗号化鍵生成装置３０の公開鍵Ｘiであった旨を示す検証成功を出力する機能とをもっている。
【０１４２】
これに伴い、復号装置５０の制御部５６は、図８に示す動作を実行するように、各部５１〜５５を制御する機能をもっている。
【０１４３】
次に、以上のように構成された再暗号化システムの動作を図７及び図８のシーケンス図を用いて説明する。
【０１４４】
（１）鍵セットアップ処理の動作は、前述した通りである。
【０１４５】
（２）暗号化処理のステップＳＴ２１の動作は、前述した通りである。
【０１４６】
ステップＳＴ２１の終了後、暗号化装置２０の暗号文生成部２４は、図７に示すように、再暗号化鍵生成装置３０の公開鍵Ｘiを平文データとしてのメッセージｍに埋め込む（ＳＴ２２−ｘ）と、当該埋め込み済みのメッセージｍに対して、前述したステップＳＴ２２の動作を実行する。
【０１４７】
すなわち、暗号文生成部２４は、第１乱数ｒに基づき、当該埋め込む済みのメッセージｍ∈ＧT に対して、前述した通り、第２、第３及び第４暗号化データＣ2，Ｃ3，Ｃ4を生成する（ＳＴ２２）。
【０１４８】
暗号化処理のステップＳＴ２３〜ＳＴ２４の動作は、前述した通りである。
【０１４９】
（３）再暗号化鍵生成処理及び（４）再暗号化処理の動作は、前述した通りである。
【０１５０】
（５）復号処理のステップＳＴ５１〜ＳＴ５３の動作は、前述した通りである。
【０１５１】
ステップＳＴ５３の終了後、復号装置５０の暗号文検証処理部５５は、図８に示すように、復号されたメッセージｍから埋め込まれた公開鍵Ｘiを抽出する（ＳＴ５４−ｘ１）。
【０１５２】
暗号文検証処理部５５は、当該抽出された公開鍵Ｘiと、一時データ記憶部５２から読み出した再暗号化鍵生成装置３０の公開鍵Ｘiとを比較することにより、再暗号文データが元々誰宛の暗号文だったかを検証する（ＳＴ５４−ｘ２）。
【０１５３】
暗号文検証処理部５５は、この比較の結果、両者が一致したとき、メッセージｍの暗号化処理に用いられた公開鍵Ｘiが再暗号化鍵生成装置３０の公開鍵Ｘiであった旨を示す検証成功を出力する。
【０１５４】
また、ステップＳＴ５４−ｘ２の判定の結果、両者が一致しないとき、新たに別の装置（例、図示しない他の再暗号化装置）の公開鍵を取得して（ＳＴ５５−ｘ）一時データ記憶部５２に書き込み、ステップＳＴ５４−ｘ２と同様の検証を繰り返すことにより（ＳＴ５６−ｘ）、抽出された公開鍵に一致する公開鍵をもつ再暗号化装置を特定する。
【０１５５】
上述したように本実施形態によれば、再暗号化鍵生成装置３０の公開鍵Ｘiを平文データとしてのメッセージｍに埋め込むと、当該埋め込み済みのメッセージｍに対して、前述した暗号化処理を実行する暗号文生成部２４を暗号化装置２０が備え、復号されたメッセージｍから埋め込まれた公開鍵Ｘiを抽出して当該公開鍵Ｘiと、一時データ記憶部５２から読み出した再暗号化鍵生成装置３０の公開鍵Ｘiとを比較して検証する暗号文検証処理部５５を復号装置５０が備えた構成により、再暗号文データを受けた復号装置が、元々誰宛の暗号文データが再暗号化されたのかを検証することができる。
【０１５６】
以上説明した少なくとも一つの実施形態によれば、再暗号化システムにおいて、再暗号文データを受けた復号装置が、元々誰宛の暗号文データが再暗号化されたのかを検証することができる。
【０１５７】
なお、上記の各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１５８】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１５９】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１６０】
さらに、各実施形態における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１６１】
また、記憶媒体は１つに限らず、複数の媒体から上記の各実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１６２】
なお、各実施形態におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記の各実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１６３】
また、各実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１６４】
なお、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１６５】
１０…鍵生成装置、１１…鍵生成パラメータ記憶部、１２，２１，３２，４２，５２…一時データ記憶部、１３…公開パラメータ生成部、１４…公開鍵・秘密鍵生成部、１５，２２，３３，４３，５３…通信部、１６，２５，３５，４７，５６…制御部、２０…暗号化装置、２３…暗号化データ生成部、２４…暗号文生成部、３０…再暗号化鍵生成装置、３１…秘密鍵記憶部、３４…再暗号化鍵生成部、４０…再暗号化装置、４１…再暗号化鍵記憶部、４４…再暗号化処理部、４５…検証プログラム記憶部、４６…配信部、５０…復号装置、５１…秘密鍵記憶部、５４…復号処理部、５５…暗号文検証処理部。
【図１】
0005389212.tif 000021
【図２】
0005389212.tif 000022
【図３】
0005389212.tif 000023
【図４】
0005389212.tif 000024
【図５】
0005389212.tif 000025
【図６】
0005389212.tif 000026
【図７】
0005389212.tif 000027
【図８】
0005389212.tif 000028
【図９】
0005389212.tif 000029