(57)【要約】【課題】安全性を確保しながら、使い捨て署名を用いず、システムパラメータや暗号文のサイズが小さい方式を提供する。【解決手段】本発明のプロキシ再暗号化システムは、送信装置、Ｎ個の受信装置、再暗号化装置、鍵生成手段を有する。送信装置は暗号化部を、受信装置は復号部を、鍵生成手段は再暗号化鍵生成部を、再暗号化装置は再暗号化部を備える。秘密鍵をｓｋｎ＝ｘｎ、公開鍵をｐｋｎ＝ｇ＾ｓｋｎとする。暗号化部は、Ｃ１＝ｐｋｎｒ，Ｃ２＝ｈｒ，Ｃ３＝ｅ（ｇ，ｇ１）ｒ・Ｍ，ｔ＝Ｈ（Ｃ２，Ｃ３），Ｃ４＝（ｕｔｖｓｄ）ｒ，Ｃ５＝ｓを計算し、暗号文Ｃとする。復号部は、平文Ｍ＝Ｃ３／（ｅ（Ｃ１，ｇ１）＾（１／ｓｋｎ））を求める。再暗号化鍵生成部は、再暗号化鍵ｒｋｍ／ｎ＝ｓｋｍ／ｓｋｎを生成する。再暗号化部は、Ｃｍ１＝Ｃ１＾ｒｋｍ／ｎとし、暗号文Ｃｍ＝（Ｃｍ１，Ｃ２，Ｃｎ３，Ｃ４，Ｃ５）とする。【選択図】図１
2012150378.tif 000002
【特許請求の範囲】
【請求項１】
送信装置、Ｎ個の受信装置Ｒ１，…，ＲＮ、再暗号化装置、鍵生成手段を有するプロキシ再暗号化システムであって、
Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、λはセキュリティパラメータを示す整数、ｑはλビットの素数、ＧとＧＴは素数位数ｑの巡回乗算群、ｇは群Ｇの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈは群Ｇの元と群ＧＴの元を入力とし所定のビット長の整数に写像するハッシュ関数を示す記号、ｇ1，ｈ，ｕ，ｖ，ｄはランダムに選択された群Ｇの生成元、ｘｎを０以上ｑ−１以下からランダムに選ばれた整数、＾はべき乗を示す記号とし、
前記送信装置は、
受信装置Ｒｎの公開鍵ｐｋｎと平文Ｍとを取得すると、０以上ｑ−１以下の整数からランダムにｒ，ｓを選び、
Ｃｎ１＝ｐｋｎｒ
Ｃｎ２＝ｈｒ
Ｃｎ３＝ｅ（ｇ，ｇ１）ｒ・Ｍ
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
Ｃｎ４＝（ｕｔｖｓｄ）ｒ
Ｃｎ５＝ｓ
を生成し、Ｃｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５が含まれる暗号文Ｃｎを生成する暗号化部
を備え、
前記受信装置Ｒｎは、
ｓｋｎ＝ｘｎまたはｓｋｎ＝１／ｘｎ、ｐｋｎ＝ｇ＾ｓｋｎの関係を有する秘密鍵ｓｋｎと公開鍵ｐｋｎを記録する復号記録部と、
受信した暗号文ＣｎからＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を取得し、
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
を計算し、
ｅ（ｈ，Ｃｎ１）＝ｅ（Ｃｎ２，ｐｋｎ）
ｅ（ｈ，Ｃｎ４）＝ｅ（Ｃｎ２，ｕｔ（ｖ＾Ｃｎ５）ｄ）
が成り立つ場合には、
Ｍ＝Ｃｎ３／（ｅ（Ｃｎ１，ｇ１）＾（１／ｓｋｎ））
を計算し、平文Ｍを求める復号部と、
を備え、
前記鍵生成手段は、
受信装置Ｒｎの秘密鍵ｓｋｎと受信装置Ｒｍ（ただし、ｍ≠ｎ）の秘密鍵ｓｋｍを記録する鍵記録部と、
再暗号化鍵ｒｋｍ／ｎを
ｒｋｍ／ｎ＝ｓｋｍ／ｓｋｎ
のように生成する再暗号化鍵生成部と、
を備え、
前記再暗号化装置は、
再暗号化鍵ｒｋｍ／ｎを記録する再暗号化記録部と、
秘密鍵ｓｋｎで復号できる暗号文Ｃｎから、再暗号化鍵ｒｋｍ／ｎを用いて秘密鍵ｓｋｍで復号できる暗号文Ｃｍを生成するときには、暗号文ＣｎからＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を取得し、
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
を計算し、
ｅ（ｈ，Ｃｎ１）＝ｅ（Ｃｎ２，ｐｋｎ）
ｅ（ｈ，Ｃｎ４）＝ｅ（Ｃｎ２，ｕｔ（ｖ＾Ｃｎ５）ｄ）
が成り立つ場合には、
Ｃｍ１＝Ｃｎ１＾ｒｋｍ／ｎ
Ｃｍ２＝Ｃｎ２
Ｃｍ３＝Ｃｎ３
Ｃｍ４＝Ｃｎ４
Ｃｍ５＝Ｃｎ５
の関係を有するＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５が含まれる暗号文Ｃｍを生成する再暗号化部と、
を備える
プロキシ再暗号化システム。
【請求項２】
請求項１記載のプロキシ再暗号化システムであって、
前記再暗号化部は、
秘密鍵ｓｋｍで復号できる暗号文Ｃｍから、再暗号化鍵ｒｋｍ／ｎを用いて秘密鍵ｓｋｎで復号できる暗号文Ｃｎを生成するときには、暗号文ＣｍからＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５を取得し、
ｔ＝Ｈ（Ｃｍ２，Ｃｍ３）
を計算し、
ｅ（ｈ，Ｃｍ１）＝ｅ（Ｃｍ２，ｐｋｍ）
ｅ（ｈ，Ｃｍ４）＝ｅ（Ｃｍ２，ｕｔ（ｖ＾Ｃｍ５）ｄ）
が成り立つ場合には、
Ｃｎ１＝Ｃｍ１＾（１／ｒｋｍ／ｎ）
Ｃｎ２＝Ｃｍ２
Ｃｎ３＝Ｃｍ３
Ｃｎ４＝Ｃｍ４
Ｃｎ５＝Ｃｍ５
の関係を有するＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５が含まれる暗号文Ｃｎを生成する
ことを特徴とするプロキシ再暗号化システム。
【請求項３】
受信装置Ｒｎの秘密鍵ｓｋｎで復号できる暗号文Ｃｎと受信装置Ｒｍ（ただし、ｍ≠ｎ）の秘密鍵ｓｋｍで復号できる暗号文Ｃｍとの間で再暗号化を行うための再暗号化鍵ｒｋｍ／ｎを生成する鍵生成装置であって、
秘密鍵ｓｋｎと秘密鍵ｓｋｍを記録する鍵記録部と、
再暗号化鍵ｒｋｍ／ｎを
ｒｋｍ／ｎ＝ｓｋｍ／ｓｋｎ
のように生成する再暗号化鍵生成部と、
を備える鍵生成装置。
【請求項４】
受信装置Ｒｎの秘密鍵ｓｋｎで復号できる暗号文Ｃｎと受信装置Ｒｍ（ただし、ｍ≠ｎ）の秘密鍵ｓｋｍで復号できる暗号文Ｃｍとの間で再暗号化を行う再暗号化装置であって、
ｒｋｍ／ｎ＝ｓｋｍ／ｓｋｎである再暗号化鍵ｒｋｍ／ｎを記録する再暗号化記録部と、
秘密鍵ｓｋｎで復号できる暗号文Ｃｎから、再暗号化鍵ｒｋｍ／ｎを用いて秘密鍵ｓｋｍで復号できる暗号文Ｃｍを生成するときには、暗号文ＣｎからＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を取得し、
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
を計算し、
ｅ（ｈ，Ｃｎ１）＝ｅ（Ｃｎ２，ｐｋｎ）
ｅ（ｈ，Ｃｎ４）＝ｅ（Ｃｎ２，ｕｔ（ｖ＾Ｃｎ５）ｄ）
が成り立つ場合には、
Ｃｍ１＝Ｃｎ１＾ｒｋｍ／ｎ
Ｃｍ２＝Ｃｎ２
Ｃｍ３＝Ｃｎ３
Ｃｍ４＝Ｃｎ４
Ｃｍ５＝Ｃｎ５
の関係を有するＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５が含まれる暗号文Ｃｍを生成する再暗号化部と、
を備える再暗号化装置。
【請求項５】
請求項４記載の再暗号化装置であって、
前記再暗号化部は、
秘密鍵ｓｋｍで復号できる暗号文Ｃｍから、再暗号化鍵ｒｋｍ／ｎを用いて秘密鍵ｓｋｎで復号できる暗号文Ｃｎを生成するときには、暗号文ＣｍからＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５を取得し、
ｔ＝Ｈ（Ｃｍ２，Ｃｍ３）
を計算し、
ｅ（ｈ，Ｃｍ１）＝ｅ（Ｃｍ２，ｐｋｍ）
ｅ（ｈ，Ｃｍ４）＝ｅ（Ｃｍ２，ｕｔ（ｖ＾Ｃｍ５）ｄ）
が成り立つ場合には、
Ｃｎ１＝Ｃｍ１＾（１／ｒｋｍ／ｎ）
Ｃｎ２＝Ｃｍ２
Ｃｎ３＝Ｃｍ３
Ｃｎ４＝Ｃｍ４
Ｃｎ５＝Ｃｍ５
の関係を有するＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５が含まれる暗号文Ｃｎを生成する
ことを特徴とする再暗号化装置。
【請求項６】
再暗号化装置、鍵生成手段を用いたプロキシ再暗号化方法であって、
Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、λはセキュリティパラメータを示す整数、ｑはλビットの素数、ＧとＧＴは素数位数ｑの巡回乗算群、ｇは群Ｇの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈは群Ｇの元と群ＧＴの元を入力とし所定のビット長の整数に写像するハッシュ関数を示す記号、ｇ1，ｈ，ｕ，ｖ，ｄはランダムに選択された群Ｇの生成元、ｘｎ，ｒ，ｓは０以上ｑ−１以下からランダムに選ばれた整数、＾はべき乗を示す記号とし、
秘密鍵ｓｋｎはｓｋｎ＝ｘｎまたはｓｋｎ＝１／ｘｎ、公開鍵ｐｋｎはｐｋｎ＝ｇ＾ｓｋｎの関係を有し、
暗号文Ｃｎは、
Ｃｎ１＝ｐｋｎｒ
Ｃｎ２＝ｈｒ
Ｃｎ３＝ｅ（ｇ，ｇ１）ｒ・Ｍ
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
Ｃｎ４＝（ｕｔｖｓｄ）ｒ
Ｃｎ５＝ｓ
であるＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を含んでおり、
前記鍵生成手段が、再暗号化鍵ｒｋｍ／ｎ（ただし、ｍ≠ｎ）を
ｒｋｍ／ｎ＝ｓｋｍ／ｓｋｎ
のように生成する再暗号化鍵生成ステップと、
前記再暗号化装置が、秘密鍵ｓｋｎで復号できる暗号文Ｃｎから、再暗号化鍵ｒｋｍ／ｎを用いて秘密鍵ｓｋｍで復号できる暗号文Ｃｍを生成するときには、暗号文ＣｎからＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を取得し、
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
を計算し、
ｅ（ｈ，Ｃｎ１）＝ｅ（Ｃｎ２，ｐｋｎ）
ｅ（ｈ，Ｃｎ４）＝ｅ（Ｃｎ２，ｕｔ（ｖ＾Ｃｎ５）ｄ）
が成り立つ場合には、
Ｃｍ１＝Ｃｎ１＾ｒｋｍ／ｎ
Ｃｍ２＝Ｃｎ２
Ｃｍ３＝Ｃｎ３
Ｃｍ４＝Ｃｎ４
Ｃｍ５＝Ｃｎ５
の関係を有するＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５が含まれる暗号文Ｃｍを生成する再暗号化ステップと、
を有するプロキシ再暗号化方法。
【請求項７】
請求項６記載のプロキシ再暗号化方法であって、
前記再暗号化部が、秘密鍵ｓｋｍで復号できる暗号文Ｃｍから、再暗号化鍵ｒｋｍ／ｎを用いて秘密鍵ｓｋｎで復号できる暗号文Ｃｎを生成するときには、暗号文ＣｍからＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５を取得し、
ｔ＝Ｈ（Ｃｍ２，Ｃｍ３）
を計算し、
ｅ（ｈ，Ｃｍ１）＝ｅ（Ｃｍ２，ｐｋｍ）
ｅ（ｈ，Ｃｍ４）＝ｅ（Ｃｍ２，ｕｔ（ｖ＾Ｃｍ５）ｄ）
が成り立つ場合には、
Ｃｎ１＝Ｃｍ１＾（１／ｒｋｍ／ｎ）
Ｃｎ２＝Ｃｍ２
Ｃｎ３＝Ｃｍ３
Ｃｎ４＝Ｃｍ４
Ｃｎ５＝Ｃｍ５
の関係を有するＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５が含まれる暗号文Ｃｎを生成する逆向き再暗号化ステップも有する
ことを特徴とするプロキシ再暗号化方法。
【請求項８】
請求項１または２に記載のプロキシ再暗号化システムを構成する前記送信装置、前記受信装置、前記再暗号化装置、前記鍵生成手段のいずれかとしてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵方式の暗号文をその暗号文を暗号化する際に用いた公開鍵以外の公開鍵で暗号化したと同等の暗号文に再暗号化するプロキシ再暗号化システム、鍵生成装置、再暗号化装置、プロキシ再暗号化方法、プログラムに関する。
【背景技術】
【０００２】
公開鍵暗号を用いて何らかのデータを暗号化してやりとりする場合，アリスの公開鍵ｐｋ１で暗号化されたデータをボブの公開鍵ｐｋ２で暗号化されたデータに変換したいという状況が考えられる。例えばアリスが自分宛の（暗号化された）メールをボブに転送してボブに読んで欲しい場合、アリスが自分の保有する秘密鍵ｓｋ１で一度復号し、ボブの公開鍵ｐｋ２で再度暗号化して転送すればよい。しかしこの場合、転送時にアリスがオンラインである必要があり、さらに一度復号するという手間が発生する。そのため、メールサーバのような（信頼できない可能性がある）第三者が復号することなく直接ボブの公開鍵による暗号文に変換し、転送できることが望ましい（もちろんメールサーバはメールの内容について一切知ることができないことが要求される）。これを実現する方法の一つにプロキシ再暗号が挙げられる。プロキシと呼ばれる第三者は（アリスとボブ間の）再暗号化鍵と呼ばれる鍵ｒｋ２−１を用いて，アリスへの暗号文Ｃ１を（ｓｋ１を利用することなく）ボブへの暗号文Ｃ２に変換できる。この技術によって、安全なｅ−ｍａｉｌ転送，安全な分散ファイル（ストレージ）システム、安全なdigital right management（ＤＲＭ）システムなどを実現することが期待できる。
【０００３】
プロキシ再暗号は公開鍵暗号を拡張した概念と考えられるため、公開鍵暗号と同様に適応的選択暗号文攻撃（ＣＣＡ２）に対して安全な方式が望ましい。非特許文献１や非特許文献２が、安全性の高いプロキシ再暗号化技術として知られている。非特許文献１では、（双方向）プロキシ再暗号に対するＣＣＡ２安全性を定義し、判定双線型Diffie-Hellman（ＤＢＤＨ）仮定に基づく具体的な方式（ランダムオラクルモデルで安全な方式と標準モデルで安全な方式）を構成した。非特許文献２では、非特許文献３に示されたＩＤベース暗号を利用することで使い捨て署名を使わずにＣＣＡ２安全な方式を構成できることを指摘している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】R. Canetti and S. Hohenberger, “Chosenciphertext secure proxy re-encryption”, In ACM Conference on Computer and Communications Security, pp.185-194, ACM, 2007.
【非特許文献２】B. Libert and D. Vergnaud, “Unidirectional Chosen-Ciphertext Secure Proxy Reencryption”, In Public Key Cryptography, volume 4939 of Lecture Notes in Computer Science, pp.360-379, Springer, 2008.
【非特許文献３】B. Waters, “Efficient Identity-Based Encryption Without Random Oracles”, In EUROCRYPT, volume 3494 of Lecture Notes in Computer Science, pp.114-127, Springer, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１の方式は、使い捨て署名を使用しているため、暗号文のサイズが大きい。非特許文献２の方式は、システムパラメータのサイズが非常に大きくなってしまう。
【０００６】
本発明のプロキシ再暗号化システムは、従来技術と同じ安全性を確保しながら、使い捨て署名を用いず、システムパラメータや暗号文のサイズが小さい方式を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明のプロキシ再暗号化システムは、送信装置、Ｎ個の受信装置Ｒ１，…，ＲＮ、再暗号化装置、鍵生成手段を有する。ここで、Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、λはセキュリティパラメータを示す整数、ｑはλビットの素数、ＧとＧＴは素数位数ｑの巡回乗算群、ｇは群Ｇの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈは群Ｇの元と群ＧＴの元を入力とし所定のビット長の整数に写像するハッシュ関数を示す記号、ｇ1，ｈ，ｕ，ｖ，ｄはランダムに選択された群Ｇの生成元、＾はべき乗を示す記号とする。
【０００８】
送信装置は、暗号化部を備える。受信装置Ｒ１，…，ＲＮは、それぞれ復号記録部と復号部を備える。鍵生成手段は、鍵記録部と再暗号化鍵生成部を備える。再暗号化装置は、再暗号化記録部と再暗号化部を備える。
【０００９】
送信装置の暗号化部は、受信装置Ｒｎの公開鍵ｐｋｎと平文Ｍとを取得すると、０以上ｑ−１以下の整数からランダムにｒ，ｓを選ぶ。そして、
Ｃｎ１＝ｐｋｎｒ
Ｃｎ２＝ｈｒ
Ｃｎ３＝ｅ（ｇ，ｇ１）ｒ・Ｍ
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
Ｃｎ４＝（ｕｔｖｓｄ）ｒ
Ｃｎ５＝ｓ
を計算し、Ｃｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５が含まれる暗号文Ｃｎを生成する。
【００１０】
受信装置Ｒｎの復号記録部は、あらかじめ秘密鍵ｓｋｎと公開鍵ｐｋｎを記録する。なお、秘密鍵ｓｋｎと公開鍵ｐｋｎは、ｘｎを０以上ｑ−１以下からランダムに選ばれた整数とし、ｓｋｎ＝ｘｎまたはｓｋｎ＝１／ｘｎ、ｐｋｎ＝ｇ＾ｓｋｎの関係を有する。また、秘密鍵ｓｋｎと公開鍵ｐｋｎは、受信装置Ｒｎ自身が生成してもよいし、信頼できる鍵生成装置が生成してもよい。復号部は、受信した暗号文ＣｎからＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を取得し、
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
を計算し、
ｅ（ｈ，Ｃｎ１）＝ｅ（Ｃｎ２，ｐｋｎ）
ｅ（ｈ，Ｃｎ４）＝ｅ（Ｃｎ２，ｕｔ（ｖ＾Ｃｎ５）ｄ）
が成り立つかを確認する。そして、この条件が成り立つ場合には、
Ｍ＝Ｃｎ３／（ｅ（Ｃｎ１，ｇ１）＾（１／ｓｋｎ））
を計算し、平文Ｍを求める。
【００１１】
鍵生成手段の鍵記録部は、受信装置Ｒｎの秘密鍵ｓｋｎと受信装置Ｒｍ（ただし、ｍ≠ｎ）の秘密鍵ｓｋｍを記録する。再暗号化鍵生成部は、再暗号化鍵ｒｋｍ／ｎを
ｒｋｍ／ｎ＝ｓｋｍ／ｓｋｎ
のように生成する。
【００１２】
再暗号化装置の再暗号化記録部は、再暗号化鍵ｒｋｍ／ｎを記録する。再暗号化部は、公開鍵ｐｋｎを用いて暗号化された暗号文ＣｎからＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を取得し、
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
を計算し、
ｅ（ｈ，Ｃｎ１）＝ｅ（Ｃｎ２，ｐｋｎ）
ｅ（ｈ，Ｃｎ４）＝ｅ（Ｃｎ２，ｕｔ（ｖ＾Ｃｎ５）ｄ）
が成り立つかを確認する。そして、この条件が成り立つ場合には、
Ｃｍ１＝Ｃｎ１＾ｒｋｍ／ｎ
Ｃｍ２＝Ｃｎ２
Ｃｍ３＝Ｃｎ３
Ｃｍ４＝Ｃｎ４
Ｃｍ５＝Ｃｎ５
の関係を有するＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５が含まれる暗号文Ｃｍを生成する。
【発明の効果】
【００１３】
本発明のプロキシ再暗号化システムによれば、暗号文Ｃの中のＣｎ４が署名の役割を果たすので、暗号文の正当性を保証できる。したがって、従来技術と同じ安全性を確保できる。また、使い捨て署名を用いておらず、システムパラメータや暗号文のサイズが従来技術に比べて小さい。
【図面の簡単な説明】
【００１４】
【図１】実施例１のプロキシ再暗号化システムの構成例を示す図。
【図２】実施例１のｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｎ番目の受信装置が復号する場合の処理フローを示す図。
【図３】実施例１のｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｍ番目の受信装置が復号する場合の処理フローを示す図。
【図４】変形例のプロキシ再暗号化システムの構成例を示す図。
【図５】変形例のｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｎ番目の受信装置が復号する場合の処理フローを示す図。
【図６】変形例のｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｍ番目の受信装置が復号する場合の処理フローを示す図。
【図７】従来技術と本発明との比較表を示す図。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１６】
図１に実施例１のプロキシ再暗号化システムの構成例を示す。図２に実施例１のｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｎ番目の受信装置が復号する場合の処理フローを示す。図３に実施例１のｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｍ番目の受信装置が復号する場合の処理フローを示す。
【００１７】
実施例１のプロキシ再暗号化システムは、ネットワーク１０００で接続された送信装置１００、Ｎ個の受信装置２０１１，…，２０１Ｎ、再暗号化装置３００、鍵生成手段４０１を有する。ここで、Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、λはセキュリティパラメータを示す整数、ｑはλビットの素数、ＧとＧＴは素数位数ｑの巡回乗算群、ｇは群Ｇの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈは群Ｇの元と群ＧＴの元を入力とし所定のビット長の整数に写像するハッシュ関数を示す記号、ｇ1，ｈ，ｕ，ｖ，ｄはランダムに選択された群Ｇの生成元、＾はべき乗を示す記号とする。
【００１８】
送信装置は、暗号化記録部１９０、暗号化部１１０を備える。各受信装置２０１ｎは、秘密鍵・公開鍵生成部２１０ｎ、復号記録部２９０ｎ、復号部２２０ｎを備える。鍵生成手段４０１は、鍵記録部４９０と再暗号化鍵生成部４２０を備える。再暗号化装置３００は、再暗号化記録部３９０と再暗号化部３１０を備える。なお、鍵生成手段４０１は、受信装置２０１１，…，２０１Ｎの秘密鍵ｓｋ１，…，ｓｋＮを鍵記録部４９０に安全に記録し、必要な計算に利用できる手段であればよく、方式を限定する必要はない。例えば、鍵生成手段４０１は、１つの信頼できる鍵生成装置でもよいし、秘密鍵ｓｋｎを秘密分散して記録するような複数の装置から構成された秘密計算システムでもよい（この場合は鍵記録部４９０と再暗号化鍵生成部４２０も複数の装置に分散されて構成される）。秘密計算システムの具体例としては、参考文献１（千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, In CSS, 2010.）などがある。
【００１９】
まず、図２にしたがって、ｎ番目の受信装置２０１ｎの公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｎ番目の受信装置２０１ｎが復号する場合の処理フローを説明する。受信装置２０１ｎの秘密鍵・公開鍵生成部２１０ｎは、ｘｎを０以上ｑ−１以下の整数からランダムに選ぶ。秘密鍵・公開鍵生成部２１０ｎは、秘密鍵ｓｋｎをｓｋｎ＝ｘｎまたはｓｋｎ＝１／ｘｎとし、公開鍵ｐｋｎをｐｋｎ＝ｇ＾ｓｋｎとする（Ｓ２１１ｎ）。そして、秘密鍵ｓｋｎと公開鍵ｐｋｎを復号記録部２９０ｎに記録し、公開鍵ｐｋｎを公開する。
【００２０】
受信装置２０１ｎの公開鍵ｐｋｎと暗号化の対象である平文Ｍは、送信装置１００の暗号化記録部１９０に記録しておけばよい。そして、送信装置１００の暗号化部１１０は、公開鍵ｐｋｎと平文Ｍとを取得すると、０以上ｑ−１以下の整数からランダムにｒ，ｓを選ぶ。そして、
Ｃｎ１＝ｐｋｎｒ
Ｃｎ２＝ｈｒ
Ｃｎ３＝ｅ（ｇ，ｇ１）ｒ・Ｍ
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
Ｃｎ４＝（ｕｔｖｓｄ）ｒ
Ｃｎ５＝ｓ
を計算し、Ｃｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５が含まれる暗号文Ｃｎを生成し（Ｓ４１０ｎ）、受信装置２０１ｎに送信する。
【００２１】
受信装置２０１ｎの復号部２２０ｎは、受信した暗号文ＣｎからＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を取得し、
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
を計算し、
ｅ（ｈ，Ｃｎ１）＝ｅ（Ｃｎ２，ｐｋｎ）
ｅ（ｈ，Ｃｎ４）＝ｅ（Ｃｎ２，ｕｔ（ｖ＾Ｃｎ５）ｄ）
が成り立つかを確認する。そして、この条件が成り立つ場合には、
Ｍ＝Ｃｎ３／（ｅ（Ｃｎ１，ｇ１）＾（１／ｓｋｎ））
を計算し、平文Ｍを求める（Ｓ２２１ｎ）。なお、上記の条件が成り立たない場合には、エラーを出力する。
【００２２】
次に、図３にしたがって、ｎ番目の受信装置２０１ｎの公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｍ番目の受信装置２０１ｍが復号する場合の処理フローを説明する。受信装置２０１ｎの秘密鍵・公開鍵生成部２１０ｎは、ｘｎを０以上ｑ−１以下の整数からランダムに選ぶ。秘密鍵ｓｋｎをｓｋｎ＝ｘｎまたはｓｋｎ＝１／ｘｎとし、公開鍵ｐｋｎをｐｋｎ＝ｇ＾ｓｋｎとする（Ｓ２１１ｎ）。そして、秘密鍵ｓｋｎと公開鍵ｐｋｎを復号記録部２９０ｎに記録し、公開鍵ｐｋｎを公開する。また、受信装置２０１ｎは、秘密鍵ｓｋｎを鍵生成手段４０１に送信する。さらに、受信装置２０１ｍ（ただし、ｍ≠ｎ）の秘密鍵・公開鍵生成部２１０ｍは、ｘｍを０以上ｑ−１以下の整数からランダムに選ぶ。秘密鍵ｓｋｍをｓｋｍ＝ｘｍまたはｓｋｍ＝１／ｘｍとし、公開鍵ｐｋｍをｐｋｍ＝ｇ＾ｓｋｍとする（Ｓ２１１ｍ）。そして、秘密鍵ｓｋｍと公開鍵ｐｋｍを復号記録部２９０ｍに記録し、公開鍵ｐｋｍを公開する。また、受信装置２０１ｍは、秘密鍵ｓｋｍを鍵生成手段４０１に送信する。鍵生成手段４０１の鍵記録部４９０は、受信した受信装置２０１ｎの秘密鍵ｓｋｎと受信装置２０１ｍの秘密鍵ｓｋｍを記録する。このときに、受信装置２０１ｎは、秘密鍵ｓｋｎを鍵生成手段４０１にそのまま記録させてもよいし、鍵生成手段４０１に対して秘密鍵ｓｋｎを秘匿できるように秘密分散して送信し、秘密分散された秘密鍵ｓｋｎの断片を記録させてもよい。
【００２３】
送信装置１００の暗号化部１１０は、公開鍵ｐｋｎと平文Ｍとを取得すると、０以上ｑ−１以下の整数からランダムにｒ，ｓを選ぶ。そして、
Ｃｎ１＝ｐｋｎｒ
Ｃｎ２＝ｈｒ
Ｃｎ３＝ｅ（ｇ，ｇ１）ｒ・Ｍ
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
Ｃｎ４＝（ｕｔｖｓｄ）ｒ
Ｃｎ５＝ｓ
を計算し、Ｃｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５が含まれる暗号文Ｃｎを生成し（Ｓ４１０ｎ）、再暗号化装置３００に送信する。
【００２４】
鍵生成手段４０１の再暗号化鍵生成部４２０は、再暗号化鍵ｒｋｍ／ｎを
ｒｋｍ／ｎ＝ｓｋｍ／ｓｋｎ
のように生成する（Ｓ４２１ｍ／ｎ）。そして、再暗号化装置３００に再暗号化鍵ｒｋｍ／ｎを送信する。再暗号化装置３００の再暗号化記録部３９０は、再暗号化鍵ｒｋｍ／ｎを記録する。なお、ステップＳ４１０ｎとステップＳ４２１ｍ／ｎの順番は逆でもよい。例えば、再暗号化装置３００が、暗号文Ｃｎを受信した後で、鍵生成手段４０１に再暗号化前の受信装置の番号ｎと再暗号化の後の受信装置の番号ｍを送って再暗号化鍵の生成を依頼し、鍵生成手段４０１が再暗号化鍵ｒｋｍ／ｎを生成するのであれば、ステップＳ４１０ｎ、ステップＳ４２１ｍ／ｎの順番になる。一方、鍵生成手段４０１が、秘密鍵ｓｋｎ，ｓｋｍを受信したときに再暗号化鍵ｒｋｍ／ｎを生成しておくのであれば、ステップＳ４２１ｍ／ｎ、ステップＳ４１０ｎの順番になる。
【００２５】
再暗号化部３１０は、再暗号化鍵ｒｋｍ／ｎを用いて、秘密鍵ｓｋｎで復号できる暗号文Ｃｎ（公開鍵ｐｋｎで暗号化された暗号文Ｃｎまたは再暗号化によって生成された暗号文Ｃｎ）から秘密鍵ｓｋｍで復号できる暗号文Ｃｍ（公開鍵ｐｋｍで暗号化されたのと同等な暗号文Ｃｍ）を生成するときには、次のように再暗号化する。まず、受信した暗号文ＣｎからＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５を取得し、
ｔ＝Ｈ（Ｃｎ２，Ｃｎ３）
を計算し、
ｅ（ｈ，Ｃｎ１）＝ｅ（Ｃｎ２，ｐｋｎ）
ｅ（ｈ，Ｃｎ４）＝ｅ（Ｃｎ２，ｕｔ（ｖ＾Ｃｎ５）ｄ）
が成り立つかを確認する。そして、この条件が成り立つ場合には、
Ｃｍ１＝Ｃｎ１＾ｒｋｍ／ｎ
Ｃｍ２＝Ｃｎ２
Ｃｍ３＝Ｃｎ３
Ｃｍ４＝Ｃｎ４
Ｃｍ５＝Ｃｎ５
の関係を有するＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５が含まれる暗号文Ｃｍを生成する（Ｓ３１０）。なお、上記の条件が成り立たない場合には、エラーを出力する。
【００２６】
また、再暗号化鍵ｒｋｍ／ｎを用いて、秘密鍵ｓｋｍで復号できる暗号文Ｃｍ（公開鍵ｐｋｍで暗号化された暗号文Ｃｍまたは再暗号化によって生成された暗号文Ｃｍ）から秘密鍵ｓｋｎで復号できる暗号文Ｃｎ（公開鍵ｐｋｎで暗号化されたのと同等な暗号文Ｃｎ）を生成するときには、再暗号化部３１０は、次のように再暗号化すればよい。受信した暗号文ＣｍからＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５を取得する。そして、
ｔ＝Ｈ（Ｃｍ２，Ｃｍ３）
を計算し、
ｅ（ｈ，Ｃｍ１）＝ｅ（Ｃｍ２，ｐｋｍ）
ｅ（ｈ，Ｃｍ４）＝ｅ（Ｃｍ２，ｕｔ（ｖ＾Ｃｍ５）ｄ）
が成り立つかを確認する。そして、この条件が成り立つ場合には、
Ｃｎ１＝Ｃｍ１＾（１／ｒｋｍ／ｎ）
Ｃｎ２＝Ｃｍ２
Ｃｎ３＝Ｃｍ３
Ｃｎ４＝Ｃｍ４
Ｃｎ５＝Ｃｍ５
の関係を有するＣｎ１，Ｃｎ２，Ｃｎ３，Ｃｎ４，Ｃｎ５が含まれる暗号文Ｃｎを生成し（Ｓ３１０）、受信装置２０１ｍに送信する。
【００２７】
受信装置２０１ｍの復号部２２０ｍは、受信した暗号文ＣｍからＣｍ１，Ｃｍ２，Ｃｍ３，Ｃｍ４，Ｃｍ５を取得し、
ｔ＝Ｈ（Ｃｍ２，Ｃｍ３）
を計算し、
ｅ（ｈ，Ｃｍ１）＝ｅ（Ｃｍ２，ｐｋｍ）
ｅ（ｈ，Ｃｍ４）＝ｅ（Ｃｍ２，ｕｔ（ｖ＾Ｃｍ５）ｄ）
が成り立つかを確認する。そして、この条件が成り立つ場合には、
Ｍ＝Ｃｍ３／（ｅ（Ｃｍ１，ｇ１）＾（１／ｓｋｍ））
を計算し、平文Ｍを求める（Ｓ２２１ｍ）。なお、上記の条件が成り立たない場合には、エラーを出力する。
【００２８】
［変形例］
実施例１では、秘密鍵・公開鍵生成部を各受信装置が備えたが、変形例では鍵生成手段が備える場合を示す。この場合は、鍵生成手段を、例えば信頼できる鍵生成装置にすればよい。図４に変形例のプロキシ再暗号化システムの構成例を示す。図５に変形例のｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｎ番目の受信装置が復号する場合の処理フローを示す。図６に変形例のｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｍ番目の受信装置が復号する場合の処理フローを示す。
【００２９】
変形例のプロキシ再暗号化システムは、ネットワーク１０００で接続された送信装置１００、Ｎ個の受信装置２０２１，…，２０２Ｎ、再暗号化装置３００、鍵生成手段４０２を有する。実施例１との構成上の違いは、受信装置２０２ｎが秘密鍵・公開鍵生成部を備えておらず、鍵生成手段４０２が秘密鍵・公開鍵生成部４１０を備えている点だけである。
【００３０】
まず、図５にしたがって、ｎ番目の受信装置２０２ｎの公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｎ番目の受信装置２０２ｎが復号する場合の処理フローを説明する。鍵生成手段４０２の秘密鍵・公開鍵生成部４１０は、ｘｎを０以上ｑ−１以下の整数からランダムに選ぶ。秘密鍵・公開鍵生成部４１０は、秘密鍵ｓｋｎをｓｋｎ＝ｘｎまたはｓｋｎ＝１／ｘｎとし、公開鍵ｐｋｎをｐｋｎ＝ｇ＾ｓｋｎとする（Ｓ４１２ｎ）。そして、秘密鍵ｓｋｎと公開鍵ｐｋｎを鍵記録部４９０に記録し、公開鍵ｐｋｎを公開し、秘密鍵ｓｋｎを受信装置２０１ｎに送信する。受信装置２０２ｎは、秘密鍵ｓｋｎと公開鍵ｐｋｎを復号記録部２９０ｎに記録する。このように、変形例の場合も、復号記録部２９０ｎに秘密鍵ｓｋｎと公開鍵ｐｋｎが記録される。この状態は、実施例１のステップＳ２１１ｎが終了した状態と同じである。この後の処理は実施例１と同じなので説明を省略する。
【００３１】
次に、図６にしたがって、ｎ番目の受信装置の公開鍵ｐｋｎを用いて暗号化された暗号文Ｃｎをｍ番目の受信装置が復号する場合の処理フローを説明する。鍵生成手段４０２の秘密鍵・公開鍵生成部４１０は、ｘｎを０以上ｑ−１以下の整数からランダムに選ぶ。秘密鍵・公開鍵生成部４１０は、秘密鍵ｓｋｎをｓｋｎ＝ｘｎまたはｓｋｎ＝１／ｘｎとし、公開鍵ｐｋｎをｐｋｎ＝ｇ＾ｓｋｎとする（Ｓ４１２ｎ）。そして、秘密鍵ｓｋｎと公開鍵ｐｋｎを鍵記録部４９０に記録し、公開鍵ｐｋｎを公開し、秘密鍵ｓｋｎを受信装置２０２ｎに送信する。受信装置２０２ｎは、秘密鍵ｓｋｎと公開鍵ｐｋｎを復号記録部２９０ｎに記録する。なお、この処理フローの場合、受信装置２０２ｎは処理を行わないので、鍵生成手段４０２が秘密鍵ｓｋｎを受信装置２０２ｎに送信する処理と、受信装置２０２ｎが秘密鍵ｓｋｎと公開鍵ｐｋｎを記録する処理とが実行されていなくても、図６の処理フローは進めることができる。
【００３２】
秘密鍵・公開鍵生成部４１０は、ｘｍを０以上ｑ−１以下の整数からランダムに選ぶ。秘密鍵・公開鍵生成部４１０は、秘密鍵ｓｋｍをｓｋｍ＝ｘｍまたはｓｋｍ＝１／ｘｍとし、公開鍵ｐｋｍをｐｋｍ＝ｇ＾ｓｋｍとする（Ｓ４１２ｍ）。そして、秘密鍵ｓｋｍと公開鍵ｐｋｍを鍵記録部４９０に記録し、公開鍵ｐｋｍを公開し、秘密鍵ｓｋｍを受信装置２０２ｍに送信する。受信装置２０２ｍは、秘密鍵ｓｋｍと公開鍵ｐｋｍを復号記録部２９０ｍに記録する。ここまでの処理で、受信装置２０２ｍの復号記録部２９０ｍに秘密鍵ｓｋｍと公開鍵ｐｋｍが記録され、鍵生成手段４０２の鍵記録部４９０に秘密鍵ｓｋｎと秘密鍵ｓｋｍが記録された状態となる。つまり、実施例１のステップＳ２１１ｍが終了した状態と同じである。この後の処理は実施例１と同じなので説明は省略する。
【００３３】
実施例１と変形例１が相違する部分は、本発明を実行するための準備の部分である。つまり、本発明は、何らかの方法で、受信装置が自己の秘密鍵を記録し、鍵生成手段が複数の受信装置の秘密鍵を記録し、受信装置の公開鍵が公開された状態にすれば実行可能である。つまり、この状態にするまでの方法は、限定する必要がない。
【００３４】
以下に、本発明の効果について説明する。なお、実施例１と変形例の効果は同じである。図７に、従来技術と本発明との比較表を示す。なお、｜Ｚｑ｜は０以上ｑ−１以下の整数で形成される群Ｚｑの要素サイズ、｜Ｇ｜は群Ｇの要素サイズ、｜ＧＴ｜は群ＧＴの要素サイズ、｜Ｈ｜はハッシュ関数の記述長、ｎｈはハッシュ関数の出力長、｜ｖｋ｜，｜Ｓｉｇ｜はそれぞれ使い捨て署名の検証鍵のサイズと署名のサイズを示している。図７に示すように、本発明のプロキシ再暗号化システムによれば、使い捨て署名を用いておらず、非特許文献２の方式よりもシステムパラメータのサイズが小さく、非特許文献１の方式よりも暗号文のサイズが小さい。
【００３５】
本発明のプロキシ再暗号化システムによれば、暗号文Ｃの中のＣｎ４が署名の役割を果たすので、後述の安全性の証明で示すように暗号文の正当性を保証できる。したがって、従来技術と同じ安全性を確保できる。また、本発明のプロキシ再暗号化システムによれば、再暗号化鍵ｒｋｍ／ｎが
ｒｋｍ／ｎ＝ｓｋｍ／ｓｋｎ
のように生成されるので、再暗号化鍵を繰返し乗算することで別の再暗号化鍵を生成できる。具体的には、ｎ番目の受信装置２０１ｎで復号できる暗号文Ｃｎからｍ番目の受信装置２０１ｍで復号できる暗号文Ｃｍに再暗号化するための再暗号化鍵ｒｋｍ／ｎと、ｍ番目の受信装置２０１ｍで復号できる暗号文Ｃｍからｉ番目の受信装置２０１ｉで復号できる暗号文Ｃｉに再暗号化するための再暗号化鍵ｒｋｉ／ｍとがある場合に、
ｒｋｉ／ｎ＝ｒｋｉ／ｍ・ｒｋｍ／ｎ
のように再暗号化鍵を乗算するだけでｒｋｉ／ｎ（ｎ番目の受信装置２０１ｎで復号できる暗号文Ｃｎからｉ番目の受信装置２０１ｉで復号できる暗号文Ｃｉに再暗号化するための再暗号化鍵）を生成できる。この方法の場合、３つ以上の再暗号化鍵を乗算することも可能である。また、
１／ｒｋｍ／ｎ
のように逆数にするだけで、逆方向の再暗号化鍵ｒｋｎ／ｍになる。したがって、再暗号化を繰り返すことや双方向の再暗号化が容易である。
【００３６】
［安全性の証明］
定理：もしＤＢＤＨ仮定が成立し、ハッシュ関数が標的衝突困難ハッシュ関数ならば、方式Σは標準モデルでＩＮＤ−ｂｉＰＲＥ−ＣＣＡ２安全な双方向プロキシ再暗号方式である。
略証：ＤＢＤＨ仮定と等価なｍＤＢＤＨ仮定を用いる。Σの攻撃者Ａがオラクルに質問する回数をｑＯとする。どのようなＰＰＴ Ａに対してもあるＰＰＴ Ｂが存在して
【００３７】
【数１】
2012150378.tif 000003
【００３８】
が成立することを示す。ｍＤＢＤＨ問題を解くＰＰＴ Ｂは（ｇ，ｇａ，ｇｂ，ｇｃ，Ｑ）を入力として受け取り、Ｑがｅ（ｇ，ｇ）ａｂ／ｃかランダムなＧＴの元か判定したい。ＢはＩＮＤ−ｂｉ−ＣＣＡ２安全性を破る攻撃者Ａを利用するためにシステムパラメータを準備し、各オラクルのシミュレーションを行う。最初にシステムパラメータを以下のように設定する。
Setup：入力（ｇ，ｇａ，ｇｂ，ｇｃ，Ｑ）を受け取ると０以上ｑ−１以下の整数ωを選び、
ｈ＝（ｇａ）ω
を計算する。次にｇ１＝ｇａとして、さらに０以上ｑ−１以下の整数ｘｖ，ｘｄ，ｙｕ，ｙｖ，ｙｄを選び、
ｕ＝ｇ（ｇｃ）＾ｙｕ
ｖ＝（ｇ＾ｘｖ）（ｇｃ）＾ｙｖ
ｄ＝（ｇ＾ｘｄ）（ｇｃ）＾ｙｄ
を計算してＰＰ＝（Ｇ，ＧＴ，ｅ，ｑ，ｇ，ｇ１，ｈ，ｕ，ｖ，ｄ）とする。
【００３９】
鍵生成、再暗号鍵生成、再暗号化、復号オラクルのシミュレーションを以下のように行う。なおアスタリスクが付いた文字はチャレンジ暗号文の要素であることを示す。
Key Generation：０以上ｑ−１以下の整数ｘｉを選び、ユーザｉがuncorruptedなら
ｐｋｉ＝（ｇｃ）＾ｘｉ
を返し，corruptedなら
ｓｋｉ＝ｘｉ, ｐｋｉ＝ｇ＾ｘｉ
として（ｐｋｉ，ｓｋｉ）を返す。
Re-Key Generation：（ｉ，ｊ）を受け取ると、もしユーザｉとユーザｊの一方がuncorrupted でもう一方がcorruptecdならば何も返さない。そうでなければｘｊ／ｘｉを返す。
Decryption：ｐｋｉとＣ＝（Ｃ１，Ｃ２，Ｃ３，Ｃ４，Ｃ５）を受け取ると以下を実行する。
１．  ｃｈｅｃｋ（Ｃ）＝１を検証する。成立しないならエラーを出力する。
２．  （Ｃ２，Ｃ３）≠（Ｃ２＊，Ｃ３＊）かつｔ＝ｔ＊を検証する。成立するならシミュレーションを中止しランダムなビットを出力する。
３．  ｔ＋ｓｘｖ＋ｘｄ＝０を検証する。成立するならシミュレーションを中止しランダムなビットを出力する。
なお。ＤＯ２の場合，上記２の判定は行わない。
【００４０】
これまでの検証に合格している場合、ある０以上ｐ−１以下の整数ｒが存在して
Ｃ１＝ｐｋｉ＾ｒ
Ｃ４＝（ｕｔｖｓｄ）ｒ
ｔ＝Ｈ（Ｃ２，Ｃ３）
ｓ＝Ｃ５
という形になっている（ｃｈｅｃｋ（Ｃ）＝１が成立するため）。このときｐｋｉはuncorruptedユーザの鍵であり
Ｃ１＾ｘｉ＝ｇ＾（ｃｒ）
が成立する。したがって、
α＝Ｃ１＾（（ｔｙｕ＋ｓｙｖ＋ｙｄ）／ｘｉ）
＝ｇ＾（ｃｒ（ｔｙｕ＋ｓｙｖ＋ｙｄ））
が計算できる。システムパラメータの設定より
Ｃ４＝（ｕｔｖｓｄ）ｒ＝ｇ＾（ｒ（ｔ＋ｓｘｖ＋ｘｄ＋ｃ（ｔｙｕ＋ｓｙｖ＋ｙｄ）））
と書けるため、
τ＝Ｃ４／α＝ｇ＾（ｒ（ｔ＋ｓｘｖ＋ｘｄ））
とすれば
τ＾（１／（ｔ＋ｓｘｖ＋ｘｄ））＝ｇｒ
を得ることができる。これを用いて
ｍ’＝Ｃ３／ｅ（ｇｒ，ｇ１）
を計算して返す。
Re-Encryption：暗号文Ｃ＝（Ｃ１，Ｃ２，Ｃ３，Ｃ４，Ｃ５）を受け取ると以下を実行する。
１．  ユーザｉ，ｊが共にuncorruptedならｘｊ／ｘｉを再暗号化鍵としてＲｅＥｎｃを実行し、
Ｃ’＝ＲｅＥｎｃ（ｘｊ／ｘｉ，Ｃ）
を返す。
２．  ユーザｉがcorrupted、ユーザｊがuncorruptedならｐｋｉ＝ｇ＾ｘｉ，ｐｋｊ＝ｇ＾（ｃｘｊ）となっているため、
Ｃ１’＝Ｃ２＾（ｘｊ／ω）＝（ｈｒ）＾（ｘｊ／ω）＝ｇ＾（ｃｒｘｊ）＝ｐｋｊｒ
としてＣ’＝（Ｃ１’，Ｃ２，Ｃ３，Ｃ４，Ｃ５）
を返す。
３．  ユーザｉがuncorrupted、ユーザｊがcorruptedならｐｋｉ＝ｇ＾（ｃｘｉ），ｐｋｊ＝ｇ＾ｘｊとなっているため、復号オラクルのシミュレーションと同様の方法でｇｒを得て
Ｃ１’＝（ｇｒ）＾ｘｊ＝ｐｋｊｒ
とし、Ｃ’＝（Ｃ１’，Ｃ２，Ｃ３，Ｃ４，Ｃ５）を返す。
ＩＮＤ−ｂｉＰＲＥ−ＣＣＡ２の攻撃者Ａが（ｉ＊，ｍ０，ｍ１）を出力すると以下のようにチャレンジ暗号文を生成する。
Challenge：｛０，１｝からランダムにσを選び、
Ｃ１＊＝（ｇｂ）＾ｘｉ＊＝ｇ＾（ｃｘｉ＊）＝（ｐｋｉ＊）ｂ／ｃ
Ｃ２＊＝（ｇｂ）ω＝ｈｂ／ｃ
Ｃ３＊＝Ｑｍσ
ｔ＊＝Ｈ（Ｃ２＊，Ｃ３＊）
ｓ＊＝−（ｔ＊＋ｘｄ）／ｘｖ
Ｃ４＊＝（ｇｂ）＾（ｔ＊ｙｕ＋ｓ＊ｙｖ＋ｙｄ）
＝（ｇｂ／ｃ）＾（ｔ＊＋ｓ＊ｘｖ＋ｘｄ＋ｃ（ｔ＊ｙｕ＋ｓ＊ｙｖ＋ｙｄ））
＝（ｕ＾（ｔ＊ｖ＊ｄ））ｂ／ｃ
を計算する。
【００４１】
以上がＢによるシミュレーションの記述である。最終的にＡはσ’を出力し、このときＢはσ’＝σならば１を出力（Ｑ＝ｅ（ｇ，ｇ）ａｂ／ｃと判定）し、そうでなければ０を出力（Ｑはランダムと判定）する。
【００４２】
復号オラクル（Decryption）のシミュレーションにおいて、２番目の条件によって中止する確率は高々ＡｄｖＡＴＣＲ（λ）である。また、攻撃者Ａがｔ＋ｓｘｖ＋ｘｄ＝０を満たす暗号文Ｃ＝（Ｃ１，Ｃ２，Ｃ３，Ｃ４，ｓ）を質問しない限り、再暗号化オラクルと復号オラクルを完全にシミュレート可能である。チャレンジ暗号文からｔ＊＋ｓ＊ｘｖ＋ｘｄ＝０という情報が得られるが、攻撃者Ａは（ｘｖ，ｘｄ）の情報を得られないためｔ＋ｓｘｖ＋ｘｄ＝０が成立する確率は高々１／pしかない。よって３番目の条件によって中止する確率は高々ｑＯ／ｑである。Ｑ＝ｅ（ｇ，ｇ）ａｂ／ｃの場合、ＩＮＤ−ｂｉＰＲＥ−ＣＣＡ２ゲームを完全にシミュレートしており、
【００４３】
【数２】
2012150378.tif 000004
【００４４】
が成立する（証明終）。
【００４５】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００４７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５１】
１００  送信装置
１１０  暗号化部
１９０  暗号化記録部
２０１１，…，２０１Ｎ，２０２１，…，２０２Ｎ  受信装置
２１０ｎ  秘密鍵・公開鍵生成部
２２０ｎ  復号部
２９０ｎ  復号記録部
３００  再暗号化装置
３１０  再暗号化部
３９０  再暗号化記録部
４０１，４０２  鍵生成手段
４１０  秘密鍵・公開鍵生成部
４２０  再暗号化鍵生成部
４９０  鍵記録部
１０００  ネットワーク
【図１】
2012150378.tif 000005
【図２】
2012150378.tif 000006
【図３】
2012150378.tif 000007
【図４】
2012150378.tif 000008
【図５】
2012150378.tif 000009
【図６】
2012150378.tif 000010
【図７】
2012150378.tif 000011