(57)【要約】【課題】双線型写像を用いずに標準モデルで双線型写像を用いた場合と同程度の安全性を有する双方向複数ホップ型のプロキシ再暗号化システムを実現する。【解決手段】公開パラメータ生成装置と送信装置と受信装置と再暗号化鍵生成手段とプロキシとを備える双方向複数ホップ型のプロキシ再暗号化システムにおいて、鍵の生成、暗号化処理、復号処理の際に、ＡＢＯ−ＴＤＦ（All-But-One落とし戸付一方向性関数）、及びｒｅＬＴＤＦ（(re-appliable (n,k)-lossy落とし戸付一方向性関数）とその準同型性を利用する。【選択図】図１
2011147047.tif 000002
【特許請求の範囲】
【請求項１】
ＡＢＯ−ＴＤＦの関数インデックスｓaboとｒｅＬＴＤＦのパラメータparとハッシュ関数ｈとからなるシステムの公開パラメータを生成して公開する公開パラメータ生成装置と、
電子署名の公開鍵vkと秘密鍵skσとを生成する署名鍵生成手段と、乱数ｘを生成する乱数生成手段と、第１受信装置の公開鍵pk１と乱数ｘとに基づきｒｅＬＴＤＦを評価し結果ｃ1,1を出力するｒｅＬＴＤＦ評価手段と、関数インデックスｓaboと公開鍵vkと乱数ｘとに基づきＡＢＯ−ＴＤＦを評価し結果ｃ２を出力するＡＢＯ−ＴＤＦ評価手段と、メッセージｍと乱数ｘとハッシュ関数ｈとが入力され、ハッシュ値ｈ(ｘ)とメッセージｍとの排他的論理和ｃ３を出力するハッシュ値計算手段と、ｃ２とｃ３と秘密鍵skσとから電子署名σを生成する電子署名生成手段と、を備え、暗号文Ｃ１＝（ｃ1,1,ｃ２,ｃ3,vk,σ）を出力する送信装置と、
パラメータparを用いｒｅＬＴＤＦの鍵生成アルゴリズムにより公開鍵pkｉ（ｉ＝１，・・・，Ｎ−１、Ｎ≧２）と秘密鍵skｉとを生成し出力する鍵生成手段と、暗号文Ｃｉを中継する中継手段と、を備える第ｉ受信装置と、
第ｉ受信装置の秘密鍵skｉと第ｉ＋１受信装置の秘密鍵ski+1とからｒｅＬＴＤＦの再暗号化鍵生成アルゴリズムにより再暗号化鍵rki_i+1を生成する再暗号化鍵生成装置と、
暗号文Ｃｉと再暗号化鍵rki_i+1とが入力され、再暗号化アルゴリズムによりｃ1,iをｃ1,i+1に変換して、暗号文Ｃi+1＝（ｃ1,i+1,ｃ２,ｃ3,vk,σ）を出力する第ｉプロキシ装置と、
パラメータparを用いｒｅＬＴＤＦの鍵生成アルゴリズムにより公開鍵pkＮと秘密鍵skＮとを生成し出力する鍵生成手段と、ｃ２とｃ３と公開鍵vkと電子署名σとから電子署名の正当性を検証する電子署名検証手段と、上記電子署名が正当であった場合に秘密鍵skＮとｃ1,ＮとからｒｅＬＴＤＦの復元アルゴリズムによりｘ´を求めるｘ´計算手段と、ｘ´と公開鍵pkＮとに基づきｒｅＬＴＤＦを評価し結果がｃ1,Ｎと等しいことの成否を検証するｒｅＬＴＤＦ検証手段と、ｘ´と関数インデックスｓaboと公開鍵vkとに基づきＡＢＯ−ＴＤＦを評価し結果がｃ２に等しいことの成否を検証するＡＢＯ−ＴＤＦ検証手段と、各検証手段での検証が成功した場合にｃ３とハッシュ値ｈ(ｘ´)との排他的論理和を計算することによりメッセージｍを復元して出力する復元手段と、を備える第Ｎ受信装置と、
を備えるプロキシ再暗号化システム。
【請求項２】
電子署名の公開鍵vkと秘密鍵skσとを生成する署名鍵生成手段と、
乱数ｘを生成する乱数生成手段と、
受信装置の公開鍵pkと乱数ｘとに基づきｒｅＬＴＤＦを評価し結果ｃ1を出力するｒｅＬＴＤＦ評価手段と、
関数インデックスｓaboと公開鍵vkと乱数ｘとに基づきＡＢＯ−ＴＤＦを評価し結果ｃ２を出力するＡＢＯ−ＴＤＦ評価手段と、
メッセージｍと乱数ｘとハッシュ関数ｈとが入力され、ハッシュ値ｈ(ｘ)とメッセージｍとの排他的論理和ｃ３を出力するハッシュ値計算手段と、
ｃ２とｃ３と秘密鍵skσとから電子署名σを生成する電子署名生成手段と、
を備え、暗号文Ｃ＝（ｃ1,ｃ２,ｃ3,vk,σ）を出力する送信装置。
【請求項３】
第ｉ受信装置（ｉ＝１，・・・，Ｎ−１、Ｎ≧２）の秘密鍵skｉと第ｉ＋１受信装置の秘密鍵ski+1とからｒｅＬＴＤＦの再暗号化鍵生成アルゴリズムにより再暗号化鍵rki_i+1を生成する再暗号化鍵生成装置。
【請求項４】
暗号文Ｃｉ＝（ｃ1,i,ｃ２,ｃ3,vk,σ）（ｉ＝１，・・・，Ｎ−１、Ｎ≧２）と再暗号化鍵rki_i+1とが入力され、再暗号化アルゴリズムによりｃ1,iをｃ1,i+1に変換して、暗号文Ｃi+1＝（ｃ1,i+1,ｃ２,ｃ3,vk,σ）を出力するプロキシ装置。
【請求項５】
ｒｅＬＴＤＦのパラメータparを用いｒｅＬＴＤＦの鍵生成アルゴリズムにより公開鍵pkと秘密鍵skとを生成し出力する鍵生成手段と、
ｃ２とｃ３と公開鍵vkと電子署名σとから電子署名の正当性を検証する電子署名検証手段と、
上記電子署名が正当であった場合に秘密鍵skＮ（Ｎ≧２）とｃ1,ＮとからｒｅＬＴＤＦの復元アルゴリズムによりｘ´を求めるｘ´計算手段と、
ｘ´と公開鍵pkＮとに基づきｒｅＬＴＤＦを評価し結果がｃ1,Ｎと等しいことの成否を検証するｒｅＬＴＤＦ検証手段と、
ｘ´と関数インデックスｓaboと公開鍵vkとに基づきＡＢＯ−ＴＤＦを評価し結果がｃ２に等しいことの成否を検証するＡＢＯ−ＴＤＦ検証手段と、
各検証手段での検証が成功した場合にｃ３とハッシュ値ｈ(ｘ´)との排他的論理和を計算することによりメッセージｍを復元して出力する復元手段と、
を備える受信装置。
【請求項６】
公開パラメータ生成装置が、ＡＢＯ−ＴＤＦの関数インデックスｓaboとｒｅＬＴＤＦのパラメータparとハッシュ関数ｈとからなるシステムの公開パラメータを生成して公開する公開パラメータ生成ステップと、
送信装置が、電子署名の公開鍵vkと秘密鍵skσとを生成する署名鍵生成サブステップと、乱数ｘを生成する乱数生成サブステップと、第１受信装置の公開鍵pk１と乱数ｘとに基づきｒｅＬＴＤＦを評価し結果ｃ1,1を出力するｒｅＬＴＤＦ評価サブステップと、関数インデックスｓaboと公開鍵vkと乱数ｘとに基づきＡＢＯ−ＴＤＦを評価し結果ｃ２を出力するＡＢＯ−ＴＤＦ評価サブステップと、メッセージｍと乱数ｘとハッシュ関数ｈとが入力され、ハッシュ値ｈ(ｘ)とメッセージｍとの排他的論理和ｃ３を出力するハッシュ値計算サブステップと、ｃ２とｃ３と秘密鍵skσとから電子署名σを生成する電子署名生成サブステップと、を実行し、暗号文Ｃ１＝（ｃ1,1,ｃ２,ｃ3,vk,σ）を出力する送信ステップと、
第ｉ（ｉ＝１，・・・，Ｎ−１、Ｎ≧２）受信装置が、パラメータparを用いｒｅＬＴＤＦの鍵生成アルゴリズムにより公開鍵pkｉと秘密鍵skｉとを生成して出力する鍵生成サブステップと、暗号文Ｃｉを中継する中継サブステップと、を実行する第ｉ受信ステップと、
再暗号化鍵生成装置が、第ｉ受信装置の秘密鍵skｉと第ｉ＋１受信装置の秘密鍵ski+1とからｒｅＬＴＤＦの再暗号化鍵生成アルゴリズムにより再暗号化鍵rki_i+1を生成する再暗号化鍵生成ステップと、
第ｉプロキシ装置が、暗号文Ｃｉと再暗号化鍵rki_i+1とが入力され、再暗号化アルゴリズムによりｃ1,iをｃ1,i+1に変換して、暗号文Ｃi+1＝（ｃ1,i+1,ｃ２,ｃ3,vk,σ）を出力する第ｉプロキシステップと、
第Ｎ受信装置が、パラメータparを用いｒｅＬＴＤＦの鍵生成アルゴリズムにより公開鍵pkＮと秘密鍵skＮとを生成し出力する鍵生成サブステップと、ｃ２とｃ３と公開鍵vkと電子署名σとから電子署名の正当性を検証する電子署名検証サブステップと、上記電子署名が正当であった場合に秘密鍵skＮとｃ1,ＮとからｒｅＬＴＤＦの復元アルゴリズムによりｘ´を求めるｘ´計算サブステップと、ｘ´と公開鍵pkＮとに基づきｒｅＬＴＤＦを評価し結果がｃ1,Ｎと等しいことの成否を検証するｒｅＬＴＤＦ検証サブステップと、ｘ´と関数インデックスｓaboと公開鍵vkとに基づきＡＢＯ−ＴＤＦを評価し結果がｃ２に等しいことの成否を検証するＡＢＯ−ＴＤＦ検証サブステップと、各検証サブステップでの検証が成功した場合にｃ３とハッシュ値ｈ(ｘ´)との排他的論理和を計算することによりメッセージｍを復元して出力する復元サブステップと、を実行する第Ｎ受信ステップと、
を実行するプロキシ再暗号化方法。
【請求項７】
請求項１乃至５のいずれかに記載のシステム又は装置としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項１乃至５のいずれかに記載のシステム又は装置としてコンピュータを機能させるためのプログラムを記録したコンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムで暗号化方式において使われる双方向複数ホップ型のプロキシ再暗号化システム、送信装置、再暗号化鍵生成装置、プロキシ装置、受信装置、プロキシ再暗号化方法、それらのプログラムおよび記録媒体に関する。
【背景技術】
【０００２】
プロキシ再暗号化方式は、ユーザ１とユーザ２との間でやりとりするメッセージにつき暗号通信を行う際に、両者間に配置したプロキシを用い、ユーザ１の暗号鍵で暗号化された暗号文を、ユーザ１の復号鍵を公開することなくユーザ２の復号鍵で復号可能な暗号文に変換することを可能とする方式である。暗号文の変換を行うプロキシには変換に用いる再暗号化鍵が与えられるのみであり、メッセージの内容を知ることなく変換処理を実行する。例えば、図7に示すように、ある送信者が文書ｍをAliceに送信する際、Aliceの公開鍵pk1により暗号化した暗号文Ｃを、Aliceが復号することなくそのままBobに転送したい場合を考える。このような場合に、プロキシ再暗号化方式ではこの暗号文Ｃをプロキシが再暗号化鍵rk1_2によりBobの秘密鍵sk2により復号可能な暗号文Ｃ´に変換することにより、Bobの下での文書ｍの復元を可能とする。なお、再暗号化鍵rk1_2は信頼できる第三者から提供され、プロキシにAliceの秘密鍵を与えることなく再暗号化が可能である。
【０００３】
プロキシ再暗号化方式は、図８(a)に示すように、一つの再暗号化鍵rk1_2でユーザ１(Alice)の暗号文をユーザ２(Bob)の暗号文に変換することのみが可能な一方向型と、図８(b)に示すようにユーザ２の暗号文をユーザ１の暗号文に変換することも可能な双方向型とに分類することができる。また、暗号文変換が可能な回数という観点から、図８(a)に示すような暗号文変換が１回（ユーザ１からユーザ２への暗号文変換）のみが可能な単一ホップ型と、図８(c)に示すようなユーザ１からユーザ２への暗号文変換を行った後、更にユーザ２からユーザ３(Carol)への暗号文変換、・・・というように繰り返し暗号文変換が可能な複数ホップ型とに分類することができる。
【０００４】
従来の双方向複数ホップ型のプロキシ再暗号化方式として、例えば非特許文献１に示す方式が挙げられる。また、双方向単一ホップ型の方式として、例えば非特許文献２に示す方式が、片方向単一ホップ型の方式として、例えば非特許文献３に示す方式が挙げられる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】R. Canetti and S. Hohenberger, "Chosen-Ciphertext Secure Proxy Re-Encryption", Proceedings of the 14th ACM conference on Computer and communications security, 2007年, p.185-194
【非特許文献２】J. Weng, R. H. Deng, S. Liu, K. Chen, J. Lai, and X. Wang, "Chosen-Ciphertext Secure Proxy Re-Encryption Schemes without Pairings", Proceedings of the 7th International Conference on Cryptology and Network Security, 2008年, volume 5339 of Lecture Notes in Computer Science, p.1-17
【非特許文献３】J. Shao and Z. Cao, "CCA-Secure Proxy Re-Encryption without Pairings", Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography, 2009年, volume 5443 of Lecture Notes in Computer Science, p.357-376
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１の方式は、標準モデルで安全性が証明されているが、まだ歴史の浅い双線型写像を用いるものであり、安全性の根拠となる仮定について、評価がまだ十分でなく信頼性に不安がある。一方、非特許文献２、３の方式は、双線型写像は用いない方式であるが、安全性がランダムオラクルモデルでしか証明されていない。
【０００７】
本発明の目的は、双線型写像を用いずに標準モデルで双線型写像を用いた場合と同程度の安全性を有する双方向複数ホップ型のプロキシ再暗号化システムを実現することにある。
【課題を解決するための手段】
【０００８】
本発明のプロキシ再暗号化システムは、公開パラメータ生成装置と送信装置と第ｉ受信装置と再暗号化鍵生成装置と第ｉプロキシ装置と第Ｎ受信装置とを備える。
【０００９】
公開パラメータ生成装置は、ＡＢＯ−ＴＤＦの関数インデックスｓaboとｒｅＬＴＤＦのパラメータparとハッシュ関数ｈとからなるシステムの公開パラメータを生成して公開する。
【００１０】
送信装置は、電子署名の公開鍵vkと秘密鍵skσとを生成する署名鍵生成手段と、乱数ｘを生成する乱数生成手段と、第１受信装置の公開鍵pk１と乱数ｘとに基づきｒｅＬＴＤＦを評価し結果ｃ1,1を出力するｒｅＬＴＤＦ評価手段と、関数インデックスｓaboと公開鍵vkと乱数ｘとに基づきＡＢＯ−ＴＤＦを評価し結果ｃ２を出力するＡＢＯ−ＴＤＦ評価手段と、メッセージｍと乱数ｘとハッシュ関数ｈとが入力され、ハッシュ値ｈ(ｘ)とメッセージｍとの排他的論理和ｃ３を出力するハッシュ値計算手段と、ｃ２とｃ３と秘密鍵skσとから電子署名σを生成する電子署名生成手段と、を備え、暗号文Ｃ１＝（ｃ1,1,ｃ２,ｃ3,vk,σ）を出力する。
【００１１】
第ｉ（ｉ＝１，・・・，Ｎ−１、Ｎ≧２）受信装置は、パラメータparを用いｒｅＬＴＤＦの鍵生成アルゴリズムにより公開鍵pkｉと秘密鍵skｉとを生成して出力する鍵生成手段と、暗号文Ｃｉを中継する中継手段と、を備える。
【００１２】
再暗号化鍵生成装置は、第ｉ受信装置の秘密鍵skｉと第ｉ＋１受信装置の秘密鍵ski+1とからｒｅＬＴＤＦの再暗号化鍵生成アルゴリズムにより再暗号化鍵rki_i+1を生成する。
【００１３】
第ｉプロキシ装置は、暗号文Ｃｉと再暗号化鍵rki_i+1とが入力され、再暗号化アルゴリズムによりｃ1,iをｃ1,i+1に変換して、暗号文Ｃi+1＝（ｃ1,i+1,ｃ２,ｃ3,vk,σ）を出力する。
【００１４】
第Ｎ受信装置は、パラメータparを用いｒｅＬＴＤＦの鍵生成アルゴリズムにより公開鍵pkＮと秘密鍵skＮとを生成し出力する鍵生成手段と、ｃ２とｃ３と公開鍵vkと電子署名σとから電子署名の正当性を検証する電子署名検証手段と、上記電子署名が正当であった場合に秘密鍵skＮとｃ1,NとからｒｅＬＴＤＦの復元アルゴリズムによりｘ´を求めるｘ´計算手段と、ｘ´と公開鍵pkＮとに基づきｒｅＬＴＤＦを評価し結果がｃ1,Nと等しいことの成否を検証するｒｅＬＴＤＦ検証手段と、ｘ´と関数インデックスｓaboと公開鍵vkとに基づきＡＢＯ−ＴＤＦを評価し結果がｃ２に等しいことの成否を検証するＡＢＯ−ＴＤＦ検証手段と、各検証サブステップでの検証が成功した場合にｃ３とハッシュ値ｈ(ｘ´)との排他的論理和を計算することによりメッセージｍを復元して出力する復元手段と、を備える。
【発明の効果】
【００１５】
本発明のプロキシ再暗号化システムによれば、ＡＢＯ−ＴＤＦ、及びｒｅＬＴＤＦとその準同型性を利用することにより、電子署名方式がワンタイム選択文書攻撃に対し強存在的偽造負荷かつ判定ディッフィー・ヘルマン仮定が真であれば双線型写像を用いずに標準モデルで双線型写像を用いた場合と同程度の安全性を確保することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明のプロキシ再暗号化システム１００のＮ＝２（ホップ数が１）の場合の構成例を示すブロック図。
【図２】本発明のプロキシ再暗号化システム１００のＮ≧３（ホップ数が２以上）である場合の構成例を示すブロック図。
【図３】本発明の送信装置１２０の構成例を示すブロック図。
【図４】本発明の第ｉ受信装置１３０の構成例を示すブロック図。
【図５】本発明の第Ｎ受信装置１６０の構成例を示すブロック図。
【図６】本発明のプロキシ再暗号化システム１００の処理フローの例を示す図。
【図７】プロキシ再暗号化方式を説明する図。
【図８】双方向性複数ホップ型を説明する図。
【発明を実施するための形態】
【００１７】
〔本発明において用いる用語の定義および基礎となる技術の説明〕
実施形態の説明に先立ち、本発明において用いる用語の定義および基礎となる技術について説明する。
【００１８】
（１）共通事項
λはセキュリティパラメータとし、ｎ、ｋ、ｋ′、ｋ″及びνはλに依存したパラメータとする。Sig＝Sig.{Gen,Sign,Vrfy}は強偽造不可能ワンタイム署名方式とし、公開の検証鍵の長さをνとする。なお、Sig.{Gen,Sign,Vrfy}は当該署名方式Sigが、Sig.Gen、Sig.Sign、Sig.Vrfyの３つのアルゴリズムから構成されていることを表す。
【００１９】
reLTDF＝reLTDF.{Set,Gen,Eval,Inv,ReIndex,ReEval,Trans,FakeKey}は、re-appliable (n,k)-lossy落とし戸付一方向性関数(ｒｅＬＴＤＦ)とする。また、ABO = ABO.{Gen,Eval,Inv}はbranch集合がBλ＝{0,1}νの(n,k′)-All-But-One落とし戸付一方向性関数(ＡＢＯ−ＴＤＦ)とする。Ｈは{0,1}nを{0,1}″へ写す対独立ハッシュ関数族とする。
【００２０】
なお、あるδ１＝ω(logλ)とδ２＝ω(logλ)に対して、
ｎ−(ｋ＋ｋ′＋ｋ″)≧δ１＋δ２
であることが要求される。また、暗号方式のメッセージ空間は{0,1}ｋ″である。
【００２１】
（２）lossy落とし戸付一方向性関数(lossy trapdoor function：ＬＴＤＦ)
lossy落とし戸付一方向性関数は、４つの確率的多項式時間アルゴリズムの組LTDF.{Set,Gen,Eval,Inv}である。アルゴリズムLTDF.Set(1λ)は公開パラメータparを出力する。他のアルゴリズムLTDF.Gen、LTDF.Eval、LTDF.Invはパラメータparをその計算に使用するが、使用を省略する場合もある。
【００２２】
以下の条件を満たすとき、(n,k)-lossy落とし戸付一方向性関数という。
【００２３】
Injectivity: 任意の公開パラメータ par ← LTDF.Set(1λ)と、任意の関数インデックスと落とし戸のペア(s,td) ← LTDF.Gen(inj)に対して、アルゴリズムLTDF.Eval(s,・)は{0,1}ｎ上の単射関数fs(・)を計算し、アルゴリズムLTDF.Inv(td,・)はfs-1(・)を計算する。
【００２４】
Lossiness: 任意の公開パラメータ par ← LTDF.Set(1λ)と、任意の関数インデックスと擬似落とし戸のペア(s,ptd) ← LTDF.Gen(los)に対して、アルゴリズムLTDF.Eval(s,・)は{0,1}n上の関数fs(・)を計算する。ただし|fs({0,1}n)|≦2n-kである。
【００２５】
Indistinguishability: 公開パラメータ parはLTDF.Set(1λ)の出力であり、関数インデックスsinjとslosはそれぞれ、LTDF.Gen(inj)とLTDF.Gen(los)の第一出力とする。このとき{(par,sinj)}と{(par,slos)}は計算量的識別不可能である。
【００２６】
（３）re-appliable (n,k)-lossy落とし戸付一方向性関数(ｒｅＬＴＤＦ)
ｒｅＬＴＤＦとは、８つの確率的多項式時間アルゴリズムreLTDF.{Set,Gen,Eval,ReIndex,ReEval,Trans,FakeKey}であり、reLTDF.Setによって出力された任意の公開パラメータparに対し、以下の条件を満たす。
【００２７】
Lossy trapdoor function: reLTDF.{Set,Gen,Eval,Inv}は(n,k)-lossy trapdoor functionsである。
【００２８】
Re-applying with respect to function indeces: reLTDF.Gen(inj)が出力した２組の関数インデックスと落とし戸のペア(sｉ,tdｉ),(sｊ,tdｊ)を入力として、reLTDF.ReIndex(tdｉ,tdｊ)はsi_jを出力とする。任意のｘ∈{0,1}nに対して、reLTDF.Eval(sｊ,x)＝reLTDF.ReEval(si_j,reLTDF.Eval(si,x))が成立する。
【００２９】
Transitivity: reLTDF.Gen(inj)によって出力された３組の関数インデックスと落とし戸のペア(sｉ,tdｉ),(sｊ,tdｊ),(sｋ,tdｋ)に対して、reLTDF.ReIndex(tdｉ,tdｊ),reLTDF.ReIndex(tdｉ,tdｋ),reLTDF.ReIndex(tdｊ,tdｋ)がそれぞれ、si_j,si_k，sj_kを出力したとき、sj_k＝reLTDF.Trans(si_j,si_k)が成立している。
【００３０】
Statistical indistinguishability of the fake key: reLTDF.Gen(inj)が出力した２組の関数インデックスと落とし戸のペア(sｉ,tdｉ),(sｊ,tdｊ)に対して、reLTDF.FakeKeyアルゴリズムはsｉを入力にとって、(sj´,si_j´)←reLTDF.FakeKey(sｉ)を出力する。このとき、(par,sｉ,sｊ,si_j)と(par,sｉ,sｊ´,si_j´)は統計的識別不可能である。
【００３１】
Generation of Injective functions from loss functions: (s１,s２)←reLTDF.FakeKey(slos)、(slos,ptd)←reLTDF.Gen(los)のとき、reLTDF.Eval(s1,・)は単射関数fs1(・)に一致している。
【００３２】
（４）双方向ホップ方式(Bidirectional Multi-Hop Schemes)
双方向かつ複数ホップのプロキシ再暗号化方式Σは６つのアルゴリズム(Setup,KeyGen,Enc,Dec,ReKeyGen,ReEnc)から成る。
【００３３】
PP←Setup(1ｋ): セキュリティパラメータ1ｋが与えられると、公開パラメータPPを出力する。
【００３４】
(pk,sk)←KeyGen(PP): 公開パラメータPPが与えられると、公開鍵pkと秘密鍵skとを出力する。
【００３５】
Ｃ←Enc(pk,ｍ): 公開鍵pkとメッセージｍ∈Ｍ（Ｍはメッセージ空間）が与えられると、暗号文Ｃを出力する。
【００３６】
ｍ←Dec(sk,Ｃ):  秘密鍵skと暗号文Ｃが与えられると、メッセージｍまたはエラーシンボルを出力する。
【００３７】
rki_j←ReKeyGen(skｉ,skｊ): ２つの秘密鍵skｉ,skｊ(ただし、i≠j)が与えられると、ｉとｊとの間の再暗号化鍵rki_jを出力する。
【００３８】
Ｃｊ←ReEnc(rki_j,Ｃｉ): ｉとｊとの間の再暗号化鍵rki_jとｉの暗号文Ｃｉとが入力されると、別の公開鍵pkｊの下での暗号文Ｃｊかエラーシンボルを出力する。
【００３９】
そして、以下の条件を満たすとプロキシ再暗号化方式Σは正当性を満たす。
【００４０】
・任意の(pk,sk)←KeyGenと任意のメッセージｍ∈Ｍに対し、Pr[Dec(sk,Ｃ)＝ｍ：Ｃ←Enc(pk,ｍ)]が成立する。
【００４１】
・任意のｎ∈Ｎ、任意の(pk１,sk１)...(pkｎ,skｎ)←KeyGen、任意のメッセージｍ∈Ｍ、任意のrk1_2...rkn-1_n(ただし、rki_i+1←ReKeyGen(skｉ,ski+1))に対し、Pr[Dec(skｎ,ReEnc(rkn-1_n,...ReEnc(rk1_2,Ｃ1)...))＝ｍ：Ｃ1←Enc(pk１,ｍ)]の値は十分大きい。
【００４２】
（５）All-But-One落とし戸付一方向性関数（参考文献１参照）
λはセキュリティパラメータとする。n(λ)は関数の入力長を表し、k(λ)は関数の欠落度を表す（以後この項目ではλを省略する）。ｒ＝ｎ−ｋは剰余漏洩量を表す。All-But-One落とし戸付一方向性関数は枝を持つ。Ｂ＝{Ｂλ}λ∈Ｎを枝の集合とする。枝集合Ｂを持つ(n,k)-All-But-One落とし戸付一方向性関数は３つのアルゴリズムの組ABO.{Gen,Eval,Inv}からなり、以下の性質を持つ。
【００４３】
・任意のｂ＊∈Ｂλに対し、(s,t)←ABO.Gen(1λ,b*)を生成できる。ただし、ｓは関数のインデックスでｔは落とし戸である。
【００４４】
・任意のｂ∈Ｂλに対し、ABO.Eval(s,b,・)は定義域{0,1}n上で単射関数gs,b(・)を計算し、ABO.Inv(t,b,・)は逆関数gs,b-1(・)を計算する。ただし、ｂ≠ｂ＊。
【００４５】
・任意のｂ0＊、ｂ1＊∈Ｂλに対し、ｓ０とｓ１は多項式時間アルゴリズムでは識別不可能である。ただし、（s0,t0)←ABO.Gen(1λ,b0*)かつ（s1,t1)←ABO.Gen(1λ,b1*)。
【００４６】
（６）署名方式
電子署名は以下の３つの確率的多項式時間アルゴリズムの組Sig.{Gen,Sign,Vrfy}からなる。
・Sig.Gen(1λ)は検証鍵vkと署名鍵skσを出力する。
・Sig.Sign(skσ,ｍ)は署名鍵skσとメッセージｍ∈Ｍ（ただしＭは固定されたメッセージ空間）とを入力とし、署名σを出力する。
・Sig.Vrfy(vk,ｍ,σ)は検証鍵vk、メッセージｍ∈Ｍ、及び署名σを入力とし、０または１を出力する。
【００４７】
任意の(vk,skσ)←Sig.Gen(1λ)とｍ∈Ｍに対して、Sig.Vrfy(vk,ｍ,Sig.Sign(skσ,ｍ))＝１であることが要求される。電子署名がワンタイム選択文書攻撃に対して強存在的偽造不可能とは、
AdvAsEUF-OT＝Pr[(ｍ,σ)≠(ｍ*,σ*)∧Sig.vrfy(vk,ｍ,σ)＝１;
(vk,skσ)←Sig.Gen(λ); (ｍ*,st)←Ａ(vk);
σ*←Sig.Sign(skσ,ｍ*); (ｍ,σ)←Ａ(st,σ*)]
と敵の優位性を定義したとき、AdvAsEUF-OTが無視できるほど小さい場合をいう。
【００４８】
〈参考文献１〉C.Peikert and B.Waters,"Lossy trapdoor Functions and Their Applications", STOC '08, 2008年, p.187-196
【００４９】
（７）対独立ハッシュ関数(pairwise independent hash function)（参考文献２参照）
ドメインＤからレンジＲへのハッシュ関数族Ｈ＝{ｈi：Ｄ→Ｒ}が対独立であるとは、任意の相異なるｘ、ｘ´∈Ｄと任意のｙ、ｙ´∈Ｒに対して、以下が成立することである。
【００５０】
Prh←H[h(x)＝y ∧ h(x´)＝ｙ´]＝１／|Ｒ|２
【００５１】
〈参考文献２〉V.Shoup,"A Computational Introduction to Number Theory and Algebra", Cambridge University Press, 2005年
【００５２】
（８）暗号学的仮定
素数である位数ｐの巡回群Ｇを考える。ｇを群Ｇの生成元とする。Ｇｇは標準的な群の生成アルゴリズムで、セキュリティパラメータλを入力とし(Ｇ,ｐ,ｇ)を生成する。判定ディッフィー・ヘルマン問題とは(Ｇ,ｐ,ｇ)と(ｇａ,ｇｂ,ｚ)(ａ,ｂ←Ｚｐ、ｚ∈Ｇ)が与えられたときに、ｚがランダムなＧの元かｇabかどうかを判定する問題である。この優位性は以下で定義される。
【００５３】
AdvADDH(λ)＝|Pr[Ａ(Ｇ,p,g,ga,gb,z): a,b←Ｚp、z←Ｇ]−Pr[Ａ(Ｇ,p,g,ga,gb,gab): a,b←Ｚp]|
【００５４】
判定ディッフィー・ヘルマン仮定が成立しているとは、判定ディッフィー・ヘルマン問題が困難である、つまり、どのような敵Ａに対してもAdvADDH(λ)が無視できる場合をいう。
【００５５】
〔実施例〕
本発明のプロキシ再暗号化システム１００の機能ブロック構成例を図１、図２に示す。プロキシ再暗号化システム１００は、公開パラメータ生成装置１１０と送信装置１２０と第ｉ受信装置１３０と再暗号化鍵生成装置１４０と第ｉプロキシ装置１５０と第Ｎ受信装置１６０とを備える。なお、ｉ＝１，・・・，Ｎ−１、Ｎ≧２であり、つまり、第ｉ受信装置１３０にあたる受信装置及び第ｉプロキシ装置１５０にあたるプロキシ装置は、それぞれ第１〜第Ｎ−１のＮ−１個ずつある。図１はＮ＝２の場合、図２はＮ≧３の場合の構成例である。
【００５６】
公開パラメータ生成装置１１０は、ＡＢＯ−ＴＤＦの関数インデックスｓaboとｒｅＬＴＤＦのパラメータparとハッシュ関数ｈとからなるシステムの公開パラメータＰＰ＝(sabo,par,h)を生成して公開する。ｓaboはlossy branch b*＝0νとして生成する。つまり、(sabo,tdabo)←ABO.Gen(1λ,0ν)を計算する。また、parはpar←LTDF.Set(1λ)により生成し、ハッシュ関数ｈ←Ｈを選ぶ。
【００５７】
送信装置１２０は、署名鍵生成手段１２１と乱数生成手段１２２とｒｅＬＴＤＦ評価手段１２３とＡＢＯ−ＴＤＦ評価手段１２４とハッシュ値計算手段１２５と電子署名生成手段１２６とを備える。機能ブロック構成例を図３に示す。署名鍵生成手段１２１は電子署名の公開鍵vkと秘密鍵skσを(vk,skσ)←Sig.Gen(1λ)により生成する。乱数生成手段１２２は乱数ｘを生成する。ｒｅＬＴＤＦ評価手段１２３は、第１受信装置１３０の公開鍵pk１と乱数ｘとに基づきｃ1,1を、ｃ1,1＝reLTDF.Eval(pk１,x)により求めて出力する。ＡＢＯ−ＴＤＦ評価手段１２４は、関数インデックスｓaboと公開鍵vkと乱数ｘとに基づきｃ２を、ｃ２＝ABO.Eval(sabo,vk,x)により求めて出力する。ハッシュ値計算手段１２５は、メッセージｍと乱数ｘとハッシュ関数ｈとが入力され、ハッシュ値ｈ(ｘ)とメッセージｍとの排他的論理和ｃ３を求めて出力する。電子署名生成手段１２６は、ｃ２とｃ３と秘密鍵skσとから電子署名σを、σ←Sig.Sign(skσ,(c2,c3))により生成する。そして、送信装置１２０は暗号文Ｃ１＝（ｃ1,1,ｃ２,ｃ３,vk,σ）を出力する。
【００５８】
第ｉ（ｉ＝１，・・・，Ｎ−１、Ｎ≧２）受信装置１３０は、鍵生成手段１３１と中継手段１３２とを備える。機能ブロック構成例を図４に示す。鍵生成手段１３１は、パラメータparを用い公開鍵pkｉと秘密鍵skｉを、(pkｉ,skｉ)＝(sｉ,tdｉ)←reLTDF.Gen(inj)により生成する。中継手段１３２は送信装置１２０から受信した暗号文Ｃｉを第ｉプロキシ装置１５０に送信する。
【００５９】
再暗号化鍵生成装置１４０は、第ｉ受信装置の秘密鍵skｉと第ｉ＋１受信装置の秘密鍵ski+1とから再暗号化鍵rki_i+1を、rki_i+1＝ｓi_i+1＝reLTDF.ReIndex(skｉ,ski+1)により生成し、第ｉプロキシ装置１５０に与える。
【００６０】
第ｉプロキシ装置１５０は、暗号文Ｃｉ＝(ｃ1,i,ｃ２,ｃ３,vk,σ)と再暗号化鍵rki_i+1とが入力され、ｃ1,i+1＝reLTDF.ReEval(rki_i+1,ｃ1,i)により、ｃ1,iをｃ1,i+1に変換して、暗号文Ｃi+1＝(ｃ1,i+1,ｃ２,ｃ３,vk,σ)を出力する。
【００６１】
第Ｎ受信装置１６０は、鍵生成手段１６１と電子署名検証手段１６２とｘ´計算手段１６３とｒｅＬＴＤＦ検証手段１６４とＡＢＯ−ＴＤＦ検証手段１６５と復元手段１６６とを備える。機能ブロック構成例を図５に示す。鍵生成手段１６１は、パラメータparを用い公開鍵pkＮと秘密鍵skＮを、(pkＮ,skＮ)＝(sＮ,tdＮ)←reLTDF.Gen(inj)により生成する。電子署名検証手段１６２は、Sig.Vrfy(vk,(c２,c３),σ)により電子署名の正当性を検証し、正当性が認められない場合には処理を終了する。電子署名が正当であった場合、ｘ´計算手段１６３は秘密鍵skＮとｃ1,Nとからｘ´をｘ´＝reLTDF.Inv(skＮ,ｃ1,N)により求める。ｒｅＬＴＤＦ検証手段１６４は、ｃ1,N＝reLTDF.Eval(pkＮ,x)が成立するか否かを検証し、成立しない場合には処理を終了する。ＡＢＯ−ＴＤＦ検証手段１６５は、ｃ２＝ABO.Eval(sabo,vk,ｘ´)が成立するか否かを検証し、成立しない場合には処理を終了する。復元手段１６６は、各検証手段での検証が成功した場合にｃ３とハッシュ値ｈ(ｘ´)との排他的論理和を計算することによりメッセージｍを復元して出力する。
【００６２】
図６に本発明のプロキシ再暗号化システム１００の処理フロー例を示す。まず、公開パラメータ生成装置１１０が公開パラメータＰＰを生成して公開する（Ｓ１）。送信装置１２０は、電子署名の公開鍵vkと秘密鍵skσとを生成し（Ｓ２−１）、乱数ｘを生成し（Ｓ２−２）、ｒｅＬＴＤＦにより評価して結果ｃ1,1を出力し（Ｓ２−３）、ＡＢＯ−ＴＤＦにより評価して結果ｃ２を出力し（Ｓ２−４）、乱数ｘのハッシュ値とメッセージｍとの排他的論理和によりｃ３を求めて出力し（Ｓ２−５）、電子署名σを生成する（Ｓ２−６）。またＳ２−１〜６と並行して、第ｉ受信装置１３０が公開鍵vkｉと秘密鍵skｉを生成し（Ｓ３ａ）、第Ｎ受信装置１６０が公開鍵vkＮと秘密鍵skＮを生成し（Ｓ６ａ）、再暗号化鍵生成装置１４０が再暗号化鍵rki_i+1を生成する（Ｓ４）。続いて、第ｉ受信装置１３０がＣｉを中継し（Ｓ３ｂ）、第ｉプロキシ装置が暗号文ＣｉをＣi+1に変換する（Ｓ５）。Ｓ３ｂとＳ５はｉが１からＮ−１になるまで繰り返す。続いて、第Ｎ受信装置１６０が、電子署名σを検証し（Ｓ６−１）、署名が正当である場合にはｘ´を計算し（Ｓ６−２）、ｃ1,Nを検証し（Ｓ６−３）、ｃ２を検証し（Ｓ６−４）、最後にｘ´のハッシュ値とｃ３との排他的論理和をとることによりメッセージｍを復元する（Ｓ６−５）。なお、検証に失敗した場合には処理を終了する。
【００６３】
以上のように本発明のプロキシ再暗号化システムによれば、ＡＢＯ−ＴＤＦ、及びｒｅＬＴＤＦとその準同型性を利用することにより、電子署名方式がワンタイム選択文書攻撃に対し強存在的偽造不可かつ判定ディッフィー・ヘルマン仮定が真であれば双線型写像を用いずに標準モデルで双線型写像を用いた場合と同程度の安全性を確保することができる。
【００６４】
〔実施例の各パラメータの具体的計算例等〕
・ＡＢＯ−ＴＤＦの関数インデックスｓaboについて
プロキシ再暗号化方式において、ｒｅＬＴＤＦとＡＢＯ−ＴＤＦの実現方法として判定ディッフィーへルマン問題を利用した方法で、システムパラメータに含まれるＡＢＯ−ＴＤＦの関数インデックスｓaboを生成するために、素数ｐ、位数ｐの巡回群Ｇ、Ｇの生成元ｇを用い、公開情報をｈｊ＝ｇz_j、秘密の落とし戸情報をz_j∈Ｚｐ(ただし,j∈[n])、lossy branch b＊＝０νとし、ｍ∈Ｚｐを入力として、乱数ｒ∈Ｚｐを使って、c＝(c1,c2)＝Ench(m;r)＝(gr,hrgm)を生成する手続きを行い、Ench(m1;r1)◎Ench(m2;r2)＝Ench(m1+m2;r1+r2)（ただし、◎は成分ごとの掛け算を表す）であること、また、ｘ∈Ｚｐに対しEnch(m;r)ｘ＝Ench(mx;mr)であること、さらに演算□を次のように定義することで、c□ν＝(c1,c2・gν)＝Ench(m;r)◎Ench(ν;０)＝Ench(m+ν;r)、ci,j＝Ench(0;rｉ)から行列Ｃ＝(ci,j)＝(Ｃ１,Ｃ２)（ただし、i,j∈[n]）を生成して、ｓabo＝Ｃとする。ただし、r1,・・・,rn←Ｚｐ、b＊＝０である。
【００６５】
【数１】
2011147047.tif 000003
【００６６】
・ｒｅＬＴＤＦの公開パラメータparについて
ランダムなu1,・・・,un←Ｚｐを選び、Ｄ１を
【００６７】
【数２】
2011147047.tif 000004
【００６８】
とする。このＤ１をparとする。
【００６９】
・ｒｅＬＴＤＦの関数インデックス(s,td)＝(pk,sk)について
対角成分(i,i)が独立ランダムな値で、残りの成分が０の行列Ｍを考える。つまり、
【００７０】
【数３】
2011147047.tif 000005
【００７１】
ただし、m1,1,・・・,mn,n←Ｚｐである。
【００７２】
入力として公開パラメータＤ１(par)とコマンド（inj又はlos）を受け取り、w1,w2,・・・,wn←Ｚｐをランダムに選ぶ。コマンドがinjの場合は行列Ｍを上記の通りとし、コマンドがlossの場合はＭ＝０、すなわちゼロ行列とする。そして、
【００７３】
【数４】
2011147047.tif 000006
【００７４】
とする。落とし戸はｗ＝(w1,w2,・・・,wn)である。入力のコマンドがlossの場合はm1,1＝・・・＝mn,n＝０である。このように求めた関数インデックスＤ２と落とし戸ｗの組（Ｄ２,ｗ）が（s,td)=(pk,sk)である。
【００７５】
・ｒｅＬＴＤＦの評価結果ｃ１について
公開パラメータＤ１(par)、関数インデックス(pk)、乱数ｘ=(x1,・・・,xn)∈{0,1}nを入力として、ｒｅＬＴＤＦを評価する手順が、
【００７６】
【数５】
2011147047.tif 000007
【００７７】
であり、この計算結果として出力される(y1,y2)がｃ１である。
【００７８】
・ＡＢＯ−ＴＤＦの評価結果ｃ２について
乱数ｘと署名検証鍵vkを入力として関数インデックスｓabo＝ＣのＡＢＯ−ＴＤＦを評価する手順がｃ２＝Ψ＝ｘ(Ｃ□vk・Ｉ)（ただし、ｘ＝(x1,・・・,xn)、xj∈{0,1}、Ψ＝(ψ1,・・・,ψn)であり、Ｉ∈Ｚｐn×nは単位行列、つまり対角成分のみ１で残りは全て０の行列、□は成分ごとに演算を行うことを示す）であり、
【００７９】
【数６】
2011147047.tif 000008
【００８０】
（ただし、i＝jならδi,j＝１、i≠jならδi,j＝０）である。
【００８１】
・reLTDF.ReIndexについて
(sｉ,tdｉ),(sｊ,tdｊ)をreLTDF.Gen(inj)の出力としたとき、reLTDF.ReIndexはtdｉとtdｊを入力にとって、再暗号化鍵si_j＝tdｊ−tdｉ＝(w1´−w1, w2´−w2,・・・, wn´−wn)＝(w1,1_2,・・・,wn,1_2)を出力とする。
【００８２】
・reLTDF.ReEvalについて
reLTDF.ReEvalは、(si_j,(y1,y2))を入力にとって、新たな出力
【００８３】
【数７】
2011147047.tif 000009
【００８４】
を得る。(y1,y2´)を出力とする。このとき、任意のｘ∈{0,1}nに対して、reLTDF.Eval(sj,x)＝reLTDF.ReEval(si_j,reLTDF.Eval(si,x))が成立する。reLTDF.Transはs2_3＝reLTDF.Trans(s1_2,s1_3)= s1_3−s1_2を計算する。
【００８５】
本発明のプロキシ再暗号化システム及びその構成装置をコンピュータによって実現する場合、各処理機能はプログラムによって記述される。そしてパソコンや携帯端末上で、入力手段や各種記憶手段とＣＰＵとのデータのやりとりを通じてこのプログラムを実行することにより、ハードウェアとソフトウェアが協働し、各処理機能がコンピュータ上で実現されて本発明のプロキシ再暗号化システム及びその構成装置の作用効果を奏する。なおこの場合、処理機能の少なくとも一部をハードウェア的に実現することとしてもよい。また、上記の各種処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００８６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００８７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８８】
また、上述した実施形態とは別の実行形態として、コンピュータが可搬型記録媒体から直接このプログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【図１】
2011147047.tif 000010
【図２】
2011147047.tif 000011
【図３】
2011147047.tif 000012
【図４】
2011147047.tif 000013
【図５】
2011147047.tif 000014
【図６】
2011147047.tif 000015
【図７】
2011147047.tif 000016
【図８】
2011147047.tif 000017