(57)【要約】【課題】同報通信暗号システムにおいて、コンテンツの送信者に対する制限を抑止する。【解決手段】同報通信システム１は、第１乃至３の同報通信暗号を実現するものであり、コンテンツを暗号化して送信する送信装置１０、暗号化されたコンテンツを受信して復号化する受信端末装置２０、送信装置１０と受信端末装置２０を結ぶ通信網３０から構成される。なお、受信端末装置２０は複数存在するものとする。第１の同報通信暗号ではＳＤ法、およびBTEを利用する。第２の同報通信暗号ではＳＤ法、BTE、およびＦＳを利用する。第３の同報通信暗号ではBGW Scheme、BTE、およびＦＳを利用する。本発明は、放送や記録媒体の配布によるコンテンツの同報通信に適用することができる。【選択図】図１
2007189597.tif 000002
【特許請求の範囲】
【請求項１】
２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが復号化できないようにコンテンツを暗号化する暗号化装置において、
ＳＤ(Subset Difference)法に基づき、前記不正な復号化装置が割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段と、
コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段と、
決定されたカバーリングに対応して前記コンテンツ鍵を暗号化する第２の暗号化手段と、
前記コンテンツの暗号化結果、および前記コンテンツ鍵の暗号化結果を含む暗号文を出力する出力手段と
を含む暗号化装置。
【請求項２】
２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが復号化できないようにコンテンツを暗号化する暗号化装置の暗号化方法において、
ＳＤ法に基づき、前記不正な復号化装置が割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定ステップと、
コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化ステップと、
決定されたカバーリングに対応して前記コンテンツ鍵を暗号化する第２の暗号化ステップと、
前記コンテンツの暗号化結果、および前記コンテンツ鍵の暗号化結果を含む暗号文を出力する出力ステップと
を含む暗号化方法。
【請求項３】
ＳＤ法に基づき、２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段と、
コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段と、
決定されたカバーリングに対応して前記コンテンツ鍵を暗号化する第２の暗号化手段と
を含む暗号化装置から出力された、前記コンテンツの暗号化結果、および前記コンテンツ鍵の暗号化結果を含む暗号文を復号化する復号化装置において、
予め保持している第１の秘密鍵に基づき、前記カバーリングに対応する第２の秘密鍵を導出する導出手段と、
導出された前記第２の秘密鍵に基づき、前記暗号文から前記コンテンツ鍵を取得する取得手段と、
取得された前記コンテンツ鍵に基づき、前記暗号文を復号化して前記コンテンツを得る復号化手段と
を含む復号化装置。
【請求項４】
ＳＤ法に基づき、２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段と、
コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段と、
決定されたカバーリングに対応して前記コンテンツ鍵を暗号化する第２の暗号化手段と
を含む暗号化装置から出力された、前記コンテンツの暗号化結果、および前記コンテンツ鍵の暗号化結果を含む暗号文を復号化する復号化装置の復号化方法において、
予め保持している第１の秘密鍵に基づき、前記カバーリングに対応する第２の秘密鍵を導出する導出ステップと、
導出された前記第２の秘密鍵に基づき、前記暗号文から前記コンテンツ鍵を取得する取得ステップと、
取得された前記コンテンツ鍵に基づき、前記暗号文を復号化して前記コンテンツを得る復号化ステップと
を含む復号化方法。
【請求項５】
２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが復号化できないようにコンテンツを暗号化する暗号化装置において、
ＳＤ法に基づき、前記不正な復号化装置が割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段と、
コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段と、
決定されたカバーリングに対応し、時刻ｔ２において前記コンテンツ鍵を暗号化する第２の暗号化手段と、
前記コンテンツの暗号化結果、前記コンテンツ鍵の暗号化結果、および時刻ｔ２を含む暗号文を出力する出力手段と
を含む暗号化装置。
【請求項６】
２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが復号化できないようにコンテンツを暗号化する暗号化装置の暗号化方法において、
ＳＤ法に基づき、前記不正な復号化装置が割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定ステップと、
コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化ステップと、
決定されたカバーリングに対応し、時刻ｔ2において前記コンテンツ鍵を暗号化する第２の暗号化ステップと、
前記コンテンツの暗号化結果、前記コンテンツ鍵の暗号化結果、および時刻ｔ2を含む暗号文を出力する出力ステップと
を含む暗号化方法。
【請求項７】
ＳＤ法に基づき、２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段と、
コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段と、
決定されたカバーリングに対応し、時刻ｔ2において前記コンテンツ鍵を暗号化する第２の暗号化手段と
を含む暗号化装置から出力された、前記コンテンツの暗号化結果、前記コンテンツ鍵の暗号化結果、および時刻ｔ2を含む暗号文を復号化する復号化装置において、
予め保持している時刻ｔ1（≦ｔ2）の第１の秘密鍵に基づき、前記カバーリングに対応する時刻ｔ2の第２の秘密鍵を導出する導出手段と、
導出された時刻ｔ2の前記第２の秘密鍵に基づき、前記暗号文から前記コンテンツ鍵を取得する取得手段と、
取得された前記コンテンツ鍵に基づき、前記暗号文を復号化して前記コンテンツを得る復号化手段と
を含む復号化装置。
【請求項８】
前記導出手段は、予め保持している時刻ｔ1の第１の秘密鍵に基づき、前記カバーリングに対応する時刻ｔ1の第２の秘密鍵を生成し、生成した時刻ｔ1の前記第２の秘密鍵を時刻ｔ2の前記第２の秘密鍵に更新する
請求項７に記載の復号化装置。
【請求項９】
前記導出手段は、生成した時刻ｔ1の前記第２の秘密鍵を更新することにより、２つの前記第２の秘密鍵を取得し、一方を時刻ｔ2の前記第２の秘密鍵とし、他方を蓄積する
請求項８に記載の復号化装置。
【請求項１０】
前記導出手段は、予め保持している時刻ｔ1の第１の秘密鍵を時刻ｔ2の前記第１の秘密鍵に更新し、更新した時刻ｔ2の前記第１の秘密鍵に基づき、前記カバーリングに対応する時刻ｔ2の第２の秘密鍵を生成する
請求項７に記載の復号化装置。
【請求項１１】
ＳＤ法に基づき、２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段と、
コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段と、
決定されたカバーリングに対応し、時刻ｔ2において前記コンテンツ鍵を暗号化する第２の暗号化手段と
を含む暗号化装置から出力された、前記コンテンツの暗号化結果、前記コンテンツ鍵の暗号化結果、および時刻ｔ2を含む暗号文を復号化する復号化装置の復号化方法において、
予め保持している時刻ｔ1（≦ｔ2）の第１の秘密鍵に基づき、前記カバーリングに対応する時刻ｔ2の第２の秘密鍵を導出する導出ステップと、
導出された時刻ｔ2の前記第２の秘密鍵に基づき、前記暗号文から前記コンテンツ鍵を取得する取得ステップと、
取得された前記コンテンツ鍵に基づき、前記暗号文を復号化して前記コンテンツを得る復号化ステップと
を含む復号化方法。
【請求項１２】
BGW Schemeに基づいてコンテンツを暗号化する暗号化装置において、
時刻ｔ＝ｔ2において暗号化アルゴリズムENCBGW_FS（Ｓ、Ｋ、ｔ）により暗号文Ｃ，Hdrを生成する生成手段と、
生成された暗号文Ｃ，Hdrを出力する出力手段とを含み、
前記暗号文Hdrには時刻ｔが含まれる
暗号化装置。
【請求項１３】
BGW Schemeに基づいてコンテンツを暗号化する暗号化装置の暗号化方法において、
時刻ｔ＝ｔ2において暗号化アルゴリズムENCBGW_FS（Ｓ、Ｋ、ｔ）により暗号文Ｃ，Hdrを生成する生成ステップと、
生成された暗号文Ｃ，Hdrを出力する出力ステップとを含み、
前記暗号文Hdrには時刻ｔが含まれる
暗号化方法。
【請求項１４】
時刻ｔ＝ｔ2において暗号化アルゴリズムENCBGW_FS（Ｓ、Ｋ、ｔ）により暗号文Ｃ，Hdrを生成する生成手段と、
前記暗号文Hdrには時刻ｔが含まれる暗号化装置から出力された暗号文Ｃ，Hdrを復号化する復号化装置において、
予め保持している時刻ｔ1（≦ｔ2）に対応する秘密鍵に基づき、暗号文Hdrに含まれる時刻ｔ＝ｔ2に対応する秘密鍵を導出する導出手段と、
導出された時刻ｔ2に対応する秘密鍵に基づき、前記暗号文Hdrからセッション鍵を取得する取得手段と、
取得された前記セッション鍵に基づき、前記暗号文Ｃを復号化して前記コンテンツを得る復号化手段と
を含む復号化装置。
【請求項１５】
前記導出手段は、予め保持している時刻ｔ1（≦ｔ2）に対応する秘密鍵に基づき、２つの秘密鍵を導出し、一方を暗号文Hdrに含まれる時刻ｔ＝ｔ2に対応する秘密鍵として、他方を蓄積する
請求項１４に記載の復号化装置。
【請求項１６】
時刻ｔ＝ｔ2において暗号化アルゴリズムENCBGW_FS（Ｓ、Ｋ、ｔ）により暗号文Ｃ，Hdrを生成する生成手段と、
前記暗号文Hdrには時刻ｔが含まれる暗号化装置から出力された暗号文Ｃ，Hdrを復号化する復号化装置の復号化方法において、
予め保持している時刻ｔ1（≦ｔ2）に対応する秘密鍵に基づき、暗号文Hdrに含まれる時刻ｔ＝ｔ2に対応する秘密鍵を導出する導出ステップと、
導出された時刻ｔ2に対応する秘密鍵に基づき、前記暗号文Hdrからセッション鍵を取得する取得ステップと、
取得された前記セッション鍵に基づき、前記暗号文Ｃを復号化して前記コンテンツを得る復号化ステップと
を含む復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化装置および暗号化方法、並びに復号化装置および復号化方法に関し、特に、データを暗号化して同報通信する場合に用いて好適な暗号化装置および暗号化方法、並びに復号化装置および復号化方法に関する。
【背景技術】
【０００２】
映像や楽曲などに代表されるコンテンツをテレビジョン放送やラジオ放送として送信したり、インターネットに代表されるネットワークを介して配信したり、記録媒体に記録して配布したりするサービスにおいては、コンテンツの著作権を保護するとともに、不正なユーザによってコンテンツが視聴されることを抑止するため、コンテンツをコンテンツ鍵によって暗号化し、このコンテンツ鍵をデバイス鍵によって暗号化して、暗号化されているコンテンツとデバイス鍵を送信（あるいは配信や記録）し、受信端末装置において予め保持しているデバイス鍵を用いて暗号化されているコンテンツ鍵を復号し、その結果得られるコンテンツ鍵を用いてコンテンツを復号するシステムの利用が一般的である。以下、このようなシステムを同報通信暗号システムと称する。
【０００３】
同報通信暗号システムにおいては、何らかの事故や不正な工作によって受信端末装置に保持されている鍵が流出してしまうと、コンテンツの視聴権限を有しているユーザによって操作される正規の受信端末装置ではない不正な受信端末装置（コンテンツの視聴権限を有してないユーザによって操作される正規の受信端末装置）がコンテンツを再生できてしまうことになる。
【０００４】
そこで、このような事態を抑止するため、流出したデバイス鍵では復号不可能となるように暗号化を行うことができる無効化鍵管理法(Revocation Scheme)が存在する。ただし、この無効化鍵管理法は、単純に個別の受信端末装置に対して鍵の無効化を行った場合、システムとして予め必要となる鍵の数が膨大になるという問題がある。
【０００５】
システムとして予め必要となるデバイス鍵の数を抑えることができる鍵管理手法としては、Subset-Cover Revocationが存在する。Subset-Cover Revocationでは、デバイス鍵を木構造を用いて管理し、木構造のリーフ（木構造の最下層）に受信端末装置を割り当て、ノードにデバイス鍵を割り当てるようになされている。Subset-Cover Revocationの具体的な実現方式としては、Subset Difference Method（ＳＤ法）が知られている（非特許文献１参照）。
【０００６】
【非特許文献１】D.Naor,M.Naor,and J.Lotspiech,”!Revocation and tracing schemes for stateless receivers”,CRYPTO,'01,2001.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ＳＤ法は、無効化したいデバイス鍵の数が増加しても、暗号化符号列のメッセージ長を短く抑えることが可能である。しかしながら、送信側において秘密鍵を用いて暗号化している鍵管理方式の場合、コンテンツの送信は秘密鍵を知り得る信頼された機関に限定されてしまう。また、デバイス鍵が流出してしまった際にそのデバイス鍵を無効化しても、既に送信済みの暗号化されたコンテンツは、無効化されたデバイス鍵を用いて再生されてしまうという問題がある。
【０００８】
本発明はこのような状況に鑑みてなされたものであり、同報通信暗号システムの送信側における暗号化に公開鍵を用いることにより、コンテンツの送信者に対する制限を外すものである。
【課題を解決するための手段】
【０００９】
本発明の第１の側面は、２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが復号化できないようにコンテンツを暗号化する暗号化装置（暗号化方法）において、ＳＤ法に基づき、前記不正な復号化装置が割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段（ステップ）と、コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段（ステップ）と、決定されたカバーリングに対応して前記コンテンツ鍵を暗号化する第２の暗号化手段（ステップ）と、前記コンテンツの暗号化結果、および前記コンテンツ鍵の暗号化結果を含む暗号文を出力する出力手段（ステップ）とを含む暗号化装置（暗号化方法）である。
【００１０】
本発明の第１の側面においては、ＳＤ法に基づき、不正な復号化装置が割り当てられているリーフに対応して２分木におけるカバーリングが決定され、決定されたカバーリングに対応してコンテンツ鍵が暗号化され、コンテンツの暗号化結果、およびコンテンツ鍵の暗号化結果を含む暗号文が出力される。
【００１１】
本発明の第２の側面は、ＳＤ法に基づき、２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段と、コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段と、決定されたカバーリングに対応して前記コンテンツ鍵を暗号化する第２の暗号化手段とを含む暗号化装置から出力された、前記コンテンツの暗号化結果、および前記コンテンツ鍵の暗号化結果を含む暗号文を復号化する復号化装置（復号化方法）において、予め保持している第１の秘密鍵に基づき、前記カバーリングに対応する第２の秘密鍵を導出する導出手段（ステップ）と、導出された前記第２の秘密鍵に基づき、前記暗号文から前記コンテンツ鍵を取得する取得手段（ステップ）と、取得された前記コンテンツ鍵に基づき、前記暗号文を復号化して前記コンテンツを得る復号化手段（ステップ）とを含む復号化装置（復号化方法である）。
【００１２】
本発明の第２の側面においては、予め保持している第１の秘密鍵に基づき、カバーリングに対応する第２の秘密鍵が導出され、導出された第２の秘密鍵に基づき、暗号文からコンテンツ鍵が取得され、取得されたコンテンツ鍵に基づき、暗号文が復号化されてコンテンツが得られる。
【００１３】
本発明の第３の側面は、２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが復号化できないようにコンテンツを暗号化する暗号化装置（暗号化方法）において、ＳＤ法に基づき、前記不正な復号化装置が割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段（ステップ）と、コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段（ステップ）と、決定されたカバーリングに対応し、時刻ｔ2において前記コンテンツ鍵を暗号化する第２の暗号化手段（ステップ）と、前記コンテンツの暗号化結果、前記コンテンツ鍵の暗号化結果、および時刻ｔ2を含む暗号文を出力する出力手段（ステップ）とを含む暗号化装置（暗号化方法）である。
【００１４】
本発明の第３の側面においては、ＳＤ法に基づき、不正な復号化装置が割り当てられているリーフに対応して２分木におけるカバーリングが決定され、コンテンツ鍵を用いてコンテンツが暗号化される。そして、決定されたカバーリングに対応し、時刻ｔ2においてコンテンツ鍵が暗号化され、コンテンツの暗号化結果、コンテンツ鍵の暗号化結果、および時刻ｔ2を含む暗号文が出力される。
【００１５】
本発明の第４の側面は、ＳＤ法に基づき、２分木の各リーフに割り当てられた複数の復号化装置のうち、不正なものが割り当てられているリーフに対応して前記２分木におけるカバーリングを決定する決定手段と、コンテンツ鍵を用いて前記コンテンツを暗号化する第１の暗号化手段と、決定されたカバーリングに対応し、時刻ｔ2において前記コンテンツ鍵を暗号化する第２の暗号化手段とを含む暗号化装置から出力された、前記コンテンツの暗号化結果、前記コンテンツ鍵の暗号化結果、および時刻ｔ2を含む暗号文を復号化する復号化装置において、予め保持している時刻ｔ1（≦ｔ2）の第１の秘密鍵に基づき、前記カバーリングに対応する時刻ｔ2の第２の秘密鍵を導出する導出手段（ステップ）と、導出された時刻ｔ2の前記第２の秘密鍵に基づき、前記暗号文から前記コンテンツ鍵を取得する取得手段（ステップ）と、取得された前記コンテンツ鍵に基づき、前記暗号文を復号化して前記コンテンツを得る復号化手段（ステップ）とを含む復号化装置（復号化方法）である。
【００１６】
前記導出手段は、予め保持している時刻ｔ1の第１の秘密鍵に基づき、前記カバーリングに対応する時刻ｔ1の第２の秘密鍵を生成し、生成した時刻ｔ1の前記第２の秘密鍵を時刻ｔ2の前記第２の秘密鍵に更新するようにすることができる。
【００１７】
前記導出手段は、生成した時刻ｔ1の前記第２の秘密鍵を更新することにより、２つの前記第２の秘密鍵を取得し、一方を時刻ｔ2の前記第２の秘密鍵とし、他方を蓄積するようにすることができる。
【００１８】
前記導出手段は、予め保持している時刻ｔ1の第１の秘密鍵を時刻ｔ2の前記第１の秘密鍵に更新し、更新した時刻ｔ2の前記第１の秘密鍵に基づき、前記カバーリングに対応する時刻ｔ2の第２の秘密鍵を生成するようにすることができる。
【００１９】
本発明の第４の側面においては、予め保持している時刻ｔ1（≦ｔ2）の第１の秘密鍵に基づき、カバーリングに対応する時刻ｔ2の第２の秘密鍵が導出され、導出された時刻ｔ2の第２の秘密鍵に基づき、暗号文からコンテンツ鍵が取得され、取得されたコンテンツ鍵に基づき、暗号文が復号化されてコンテンツが得られる。
【００２０】
本発明第５の側面は、BGW Schemeに基づいてコンテンツを暗号化する暗号化装置（暗号化方法）において、時刻ｔ＝ｔ2において暗号化アルゴリズムENCBGW_FS（Ｓ、Ｋ、ｔ）により暗号文Ｃ，Hdrを生成する生成手段（ステップ）と、生成された暗号文Ｃ，Hdrを出力する出力手段（ステップ）とを含み、前記暗号文Hdrには時刻ｔが含まれる暗号化装置（暗号化方法）である。
【００２１】
本発明第５の側面においては、時刻ｔ＝ｔ2において暗号化アルゴリズムENCBGW_FS（Ｓ、Ｋ、ｔ）により暗号文Ｃ，Hdrが生成され、生成された暗号文Ｃ，Hdrが出力される。
【００２２】
本発明の第６の側面は、時刻ｔ＝ｔ2において暗号化アルゴリズムENCBGW_FS（Ｓ、Ｋ、ｔ）により暗号文Ｃ，Hdrを生成する生成手段と、前記暗号文Hdrには時刻ｔが含まれる暗号化装置から出力された暗号文Ｃ，Hdrを復号化する復号化装置（復号化方法）において、予め保持している時刻ｔ1（≦ｔ2）に対応する秘密鍵に基づき、暗号文Hdrに含まれる時刻ｔ＝ｔ2に対応する秘密鍵を導出する導出手段（ステップ）と、導出された時刻ｔ2に対応する秘密鍵に基づき、前記暗号文Hdrからセッション鍵を取得する取得手段（ステップ）と、取得された前記セッション鍵に基づき、前記暗号文Ｃを復号化して前記コンテンツを得る復号化手段（ステップ）とを含む復号化装置（復号化方法）である。
【００２３】
前記導出手段は、予め保持している時刻ｔ1（≦ｔ2）に対応する秘密鍵に基づき、２つの秘密鍵を導出し、一方を暗号文Hdrに含まれる時刻ｔ＝ｔ2に対応する秘密鍵として、他方を蓄積するようにすることができる。
【００２４】
本発明の第６の側面においては、予め保持している時刻ｔ1（≦ｔ2）に対応する秘密鍵に基づき、暗号文Hdrに含まれる時刻ｔ＝ｔ2に対応する秘密鍵が導出され、導出された時刻ｔ2に対応する秘密鍵に基づき、暗号文Hdrからセッション鍵が取得され、取得されたセッション鍵に基づき、暗号文Ｃが復号化されてコンテンツが得られる。
【発明の効果】
【００２５】
以上のように、本発明の第１および第２の側面によれば、同報通信暗号システムにおいて、コンテンツの送信者に対する制限を外すことが可能となる。また、システムとして予め用意する公開鍵の数を減少させることができるとともに、比較的少ない計算量で秘密鍵を導出することが可能となる。
【００２６】
本発明の第３および第４の側面によれば、同報通信暗号システムにおいて、コンテンツの送信者に対する制限を外すことが可能となる。また、システムとして予め用意する公開鍵の数を減少させることができるとともに、比較的少ない計算量で秘密鍵を導出することが可能となる。さらに、過去に送信された暗号文が復号化されることを抑止することが可能となる。
【００２７】
本発明の第５および第６の側面によれば、同報通信暗号システムにおいて、コンテンツの送信者に対する制限を外すことが可能となる。また、復号化装置の総数や不正な復号化装置の数に拘わりなく、メッセージ長を一定に保つことが可能となる。さらに、過去に送信された暗号文が復号化されることを抑止することが可能となる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００２９】
図１は、本発明を適用した同報通信システムの構成例を示している。この同報通信システム１は、後述する３種類の同報通信暗号を実現するものであり、コンテンツを暗号化して送信する送信装置１０、暗号化されたコンテンツを受信して復号化する受信端末装置２０、送信装置１０と受信端末装置２０を結ぶ通信網３０から構成される。なお、受信端末装置２０は複数存在するものとする。
【００３０】
送信装置１０は、予め保持している公開鍵を用いてコンテンツを暗号化する暗号化部１１、および、暗号化部１１によって暗号化されたコンテンツを通信網３０を介して受信端末装置２０に送信する送信部１２から構成される。
【００３１】
受信端末装置２０は、暗号化されているコンテンツを通信網３０を介して受信する受信部２１、および、受信部２１によって受信された暗号化されているコンテンツを予め保持している秘密鍵に基づいて復号化する復号化部２２から構成される。
【００３２】
通信網３０は、テレビジョン放送、ラジオ放送、有線放送などの放送網、インターネットに代表されるWAN(Wide Area Network)やLAN(Local Area Network)などのデータネットワークなどの他、暗号化されたデータを記録媒体に記録して配布することなどを含むものとする。
【００３３】
なお、送信装置１０の暗号化部１１と受信端末装置２０の復号化部２２は、それぞれハードウェアによって実現してもよいし、ソフトウェアによって実現してもよい。
【００３４】
ソフトウェアにより実現する場合、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば図２に示すように構成される汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【００３５】
このパーソナルコンピュータ５０は、CPU(Central Processing Unit)５１を内蔵している。CPU５１にはバス５４を介して、入出力インタフェース５５が接続されている。バス５４には、ROM(Read Only Memory)５２およびRAM(Random Access Memory)５３が接続されている。
【００３６】
入出力インタフェース５５には、キーボード、マウス等の入力デバイスよりなる入力部５６、操作画面などを表示するCRT(Cathode Ray Tube)またはLCD(Liquid Crystal Display)等のディスプレイよりなる出力部５７、プログラムや各種データを格納するハードディスクドライブなどよりなる記憶部５８、およびモデム、LAN（Local Area Network）アダプタなどよりなり、インターネットに代表されるネットワークを介した通信処理を実行する通信部５９が接続されている。また、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory)、DVD(Digital Versatile Disc)を含む）、光磁気ディスク（ＭＤ(Mini Disc)を含む）、もしくは半導体メモリなどの記録媒体６１に対してデータを読み書きするドライブ６０が接続されている。
【００３７】
このパーソナルコンピュータ５０に暗号化部１１あるいは復号化部２２としての処理を実行させるプログラムは、記録媒体６１に格納された状態でパーソナルコンピュータ５０に供給され、ドライブ６０によって読み出されて記憶部５８に内蔵されるハードディスクドライブにインストールされている。記憶部５８にインストールされているプログラムは、入力部５６に入力されるユーザからのコマンドに対応するCPU５１の指令によって、記憶部５８からRAM５３にロードされて実行される。
【００３８】
次に、同報通信システム１によって実現される３種類の同報通信暗号（以下、それぞれを第１の同報通信暗号、第２の同報通信暗号、または第３の同報通信暗号と称する）の基礎となる４種類の技術、すなわち、ＳＤ法、BTE(Binary Tree Encryption)、ＦＳ(Forward Security)、およびBGW Schemeについて説明する。
【００３９】
なお、第１の同報通信暗号ではＳＤ法、およびBTEを利用する。第２の同報通信暗号ではＳＤ法、BTE、およびＦＳを利用する。第３の同報通信暗号ではBGW Scheme、BTE、およびＦＳを利用する。以下、受信端末装置２０の符号”２０”を適宜省略する。
【００４０】
ＳＤ法
ＳＤ法は、Subset-Cover Revocationの一種である。Subset-Cover Revocationでは、暗号化されているコンテンツを復号化できないようにする処理を無効化(Revocation)と称し、複数存在する受信端末装置の全体の集合をＮ、無効化する受信端末装置の集合をＲとした場合、送信装置１０からの暗号化されているコンテンツを復号化する権限を有する受信端末装置∈Ｎ＼Ｒは、暗号化されているコンテンツを復号化できるが、無効化された受信端末装置∈Ｒは、これが多数結託したとしても暗号化されているコンテンツを復号化できないようにするものである。
【００４１】
ＳＤ法は、集合Ｒのサイズの拡大に伴ってカバーする部分木の個数（メッセージ長）が増加するＣＳ(Complete Subtree method)法の欠点を解決する手法であり、複数の受信端末装置２０をグループ化するとき、無効化する受信端末装置をその配下の部分木に含めて完全部分木の差ＳＤa,cを用いてカバーリングを行う。ここで、ａは、外部の完全部分木のルートであり、ｃは、無効化する受信端末装置を含む内部の完全部分木のルートである。例えば図３に示すように、無効化する受信端末装置（図中×印で示す）の集合Ｒ＝｛ｕ011，ｕ110，ｕ111｝とした場合、カバーリングはＳＤ0,011，ＳＤ1,11となる。
【００４２】
ＳＤ法における、無効化された複数の受信端末装置が結託して暗号化されているコンテンツを復号化しようとする攻撃に対する安全性の要件は、受信端末装置をグループ化するカバーリングＳＤa,cごとに異なる鍵を割り当てることである。しかしながら、全てのカバーリングＳＤa,cに対して異なる鍵を割り当てるために必要な鍵数はＯ(ｎlogｎ)となる。
【００４３】
非特許文献１には、擬似乱数生成器を用い、親の鍵から子の鍵を作成できるようにすることで必要な鍵数をＯ(log2ｎ)まで減少させる方法が開示されている。この手法では、擬似乱数生成器の入力値である木の各内部ノードに割り当てられたラベル（鍵を生成する元のデータ）を全て異なる値に設定すると異なる鍵を生成できる。
【００４４】
なお、カバーリングＳa,cはＣＳ法において分割されていた部分木を統合できるので、メッセージ長（カバーリングに必要な部分木の個数と一致する）はＣＳ法に比較して短くなる。また、無効化する受信端末装置の総数をｒとした場合、部分木の個数はその上限値が２ｒ−１になることが知られている。
【００４５】
BTE
BTEは、階層型ＩＤベース暗号(HIDE)を２分木に簡易化したものであり、ルートノードをε、親ノードをｗ∈｛０，１｝*とすると、左子ノードｗ０を、右子ノードをｗ１としてＩＤとみなしている。
【００４６】
以下、ノードｗのビット長を｜ｗ｜、ノードｗの左からｉビット目までをｗ｜iと記述する。ただし、「ｗ｜i」などを下付文字として使用する場合、表記の都合上、ｉの下付を解除して|w|iとも記述する。また、ｗ０はノードｗの最下位ビット側に０を追加した値、ｗ１はノードｗの最下位ビット側に１を追加した値とする。例えば、ノードｗ＝１０１１である場合、｜ｗ｜＝４、ｗ｜2＝１０、ｗ｜3＝１０１、ｗ０＝１０１１０、ｗ１＝１０１１１である。
【００４７】
BTEの安全性は、BDH(Bilinear Diffie-Hellman)問題の難しさに基づいている。Ｇ1，Ｇ2は位数を素数ｑとした巡回群であって、Ｇ1は加法群、Ｇ2は乗法群とした場合、双線形写像ｅ：Ｇ1×Ｇ1→Ｇ2は、∀Ｐ，Ｑ∈Ｇ1，∀ａ，ｂ∈Ｚqについて、ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（Ｐ，Ｑ）abである。
【００４８】
BTEにおけるセットアップアルゴリズムGENBTE、鍵生成アルゴリズムDERBTE、暗号化アルゴリズムENCBTE、および復号化アルゴリズムDECBTEについて説明する。
【００４９】
セットアップアルゴリズムGENBTE
セキュリティパラメータ１λと木の高さｈを入力とした場合のセットアップアルゴリズムGENBTE（１λ，ｈ）は、以下の（１）乃至（４）の処理からなる。
（１）BDHパラメータジェネレータＩＧ（１λ）を実行し、位数ｑの群Ｇ1、Ｇ2と双線形写像ｅを生成する。
（２）ランダムにＰ∈Ｇ1とα∈Ｚqを選択し、Ｑ＝αＰとする。ここで、Ｚqは０以上ｑ未満の整数の集合である。
（３）暗号的ハッシュ関数Ｈ：｛０，１｝*→Ｇ1を選択する。
（４）ＰＫ＝（Ｇ1，Ｇ2，ｅ，Ｐ，Ｑ，Ｈ）を公開鍵、Ｓε＝αＨ（ε）をルートの秘密鍵とする。
【００５０】
鍵生成アルゴリズムDERBTE
公開鍵ＰＫ、ノードｗに対応する秘密鍵ＳＫwを入力として、左子ノードｗ０、右子ノードｗ１にそれぞれ対応する秘密鍵ＳＫw0、ＳＫw1を出力する鍵生成アルゴリズムDERBTE（ＰＫ，ｗ，ＳＫw）は、以下の（１）および（２）の処理からなる。
（１）ランダムにρw0，ρw1∈Ｚqを選択し、Ｒw0＝ρw0Ｐ、Ｒw1＝ρw1Ｐ、Ｓw0＝Ｓw＋ρw0Ｈ（ｗ０）、Ｓw1＝Ｓw＋ρw1Ｈ（ｗ１）を算出する。
（２）ＳＫw0＝（Ｒw|1，…，Ｒw||w|，Ｒw0，Ｓw0）、ＳＫw1＝（Ｒw|1，…，Ｒw||w|，Ｒw1，Ｓw1）を出力する。
【００５１】
暗号化アルゴリズムENCBTE
公開鍵ＰＫ、ノードｗ、メッセージＭ∈Ｇ2を入力として、暗号文Ｃを出力する暗号化アルゴリズムENCBTE（ＰＫ，ｗ，Ｍ）は、以下の（１）および（２）の処理からなる。
（１）乱数ｒ∈Ｚqを発生する。
（２）Ｃ＝（ｒＰ，ｒＨ（ｗ｜1），ｒＨ（ｗ｜2），…,ｒＨ（ｗ｜|w|），Ｍ・ｄ）＝（Ｕ0，Ｕ1，…，Ｕ|w|，Ｖ）を出力する。
ここで、Ｕ0＝ｒＰ、Ｕi＝ｒＨ（ｗ｜i）（ｉは１以上、｜ｗ｜以下の整数）、ｄ＝ｅ（Ｑ，Ｈ（ε））rである。
【００５２】
復号化アルゴリズムDECBTE
公開鍵ＰＫ、ノードｗ、秘密鍵ＳＫw＝（Ｒw|1，…，Ｒw||w|，Ｓw）に基づいて、暗号文Ｃを復号化する復号化アルゴリズムDECBTE（ＰＫ，ｗ，ＳＫw，Ｃ）は、以下の（１）および（２）の処理からなる。
（１）ＳＫwとＣに基づいてｄを算出する。
【数１】
2007189597.tif 000003
（２）Ｖ／ｄを算出することによりメッセージＭを得る。Ｍ＝Ｖ／ｄ
【００５３】
ＦＳ
ＦＳは、受信端末装置に保持されているデバイス鍵（秘密鍵）をそれ自身に基づいて所定の周期で更新することにより、ある時点においてデバイス鍵が流出したとしても、既に送信済みの暗号化されているコンテンツの復号化を不能とするものである。
【００５４】
本発明においてＦＳの実現は、BTEと秘密鍵を格納するスタックを用いる手法を適用する。秘密鍵は、２分木の全てのノードに対応づける。２分木の高さをｈとした場合、更新される秘密鍵の数は最大で２h+1−１である。
【００５５】
図４に示す時間の２分木のように、秘密鍵の更新は、時刻ｔ＝０に木のルートから開始され、前順探索(pre-order)の順序である。時刻ｔに対応するノードをｗ(t)とする。ただし、「ｗ(t)」などを下付文字として使用する場合、表記の都合上、（ｔ）の上付きを解除してw(t)とも記述する。当該ノードｗ(t)に対応する秘密鍵をＳＫw(t)とする。また、時刻ｔ＋１に対応するノードｗ(t+1)は、ノードｗ(t)が内部ノードである場合にはｗ(t+1)＝ｗ(t)０とし、ノードｗ(t)がリーフである場合にはｗ(t+1)＝（ｗ＋１）｜i'とする。ここで｜i'は、最下位ビット側から１が出現するまで０を消去した値を示すものとする。
【００５６】
例えば、時刻ｔ＝５のノードｗ(5)＝０１tであり、このノードｗ(5)は内部ノードであるので、時刻ｔ＝６のノードｗ(6)＝０１０tとなる。ノードｗ(6)はリーフであるので、時刻ｔ＝７のノードｗ(7)＝０１０＋１＝０１１であり、最下位ビットに１が出現するので、ｗ(7)＝０１１tとなる。ノードｗ(7)はリーフであるので、時刻ｔ＝８のノードｗ(8)＝０１１＋１＝１００であり、最下位ビット側から１が出現するまで０を消去すると１である。よって、ノードｗ(8)＝１tとなる。
【００５７】
秘密鍵の更新は、時刻ｔの秘密鍵ＳＫw(t)が内部ノードに割り当てられている場合、その子ノードの一方に割り当てられた秘密鍵ＳＫw(t)0を次の時刻ｔ＋１の秘密鍵として使用するようにし、他方に割り当てられた秘密鍵ＳＫw(t)1スタックに蓄積する。そして、秘密鍵ＳＫw(t)がリーフに割り当てられている場合、スタックに最後に蓄積した秘密鍵を取り出し、時刻ｔ＋１の秘密鍵とする。
【００５８】
ＦＳにおけるセットアップアルゴリズムGENFS、鍵更新アルゴリズムKUDFS、暗号化アルゴリズムENCFS、および復号化アルゴリズムDECFSについて説明する。
【００５９】
セットアップアルゴリズムGENFS
セキュリティパラメータ１λ、最大更新回数Ｌを入力とした場合のセットアップアルゴリズムGENFS（１λ，Ｌ）では、上述したGENBTE（１λ，ｈ）を実行することにより、公開鍵ＰＫ、ルートノードの秘密鍵ＳＫε＝Ｓεを得る。なお、Ｌは２h+1−１以下の整数である。
【００６０】
鍵更新アルゴリズムKUDFS
時刻ｔの秘密鍵を更新によって得る鍵更新アルゴリズムKUDFS（ＰＫ，ｔ，ＳＫw(t)）は、以下の（１）乃至（４）の処理からなる。
（１）時刻ｔのノードｗ(t)を計算する。
（２）ノードｗ(t)が２分木の内部ノードであるかリーフであるかを判定する。
（３）ノードｗ(t)が内部ノードである場合、上述した鍵生成アルゴリズムDERBTE（ＰＫ、ｗ(t)，ＳＫw(t)）を実行して秘密鍵ＳＫw(t)0，ＳＫw(t)1を生成する。そして、秘密鍵ＳＫw(t)0を時刻ｔ＋１の秘密鍵ＳＫw(t+1)とし、秘密鍵ＳＫw(t)1をスタックに蓄積して、秘密鍵ＳＫw(t)を消去する。
（４）ノードｗ(t)がリーフである場合、スタックに蓄積されている秘密鍵を取り出して時刻ｔ＋１の秘密鍵ＳＫw(t+1)とする。
【００６１】
暗号化アルゴリズムENCFS
公開鍵ＰＫ、時刻ｔ、メッセージＭ∈Ｇ2を入力として、暗号文Ｃを出力する暗号化アルゴリズムENCFS（ＰＫ，ｔ，Ｍ）は、以下の（１）および（２）の処理からなる。
（１）時刻ｔのノードｗ(t)を計算する。
（２）上述したENCBTE（ＰＫ，ｗ(t)，Ｍ）を実行することにより暗号文Ｃを得る。
【００６２】
復号化アルゴリズムDECFS
公開鍵ＰＫ、時刻ｔ、時刻ｔの秘密鍵ＳＫw(t)に基づいて、暗号文Ｃを復号化する復号化アルゴリズムDECFS（ＰＫ，ｔ，ＳＫw(t)，Ｃ）は、以下の（１）および（２）の処理からなる。
（１）時刻ｔのノードｗ(t)を計算する。
（２）上述したDECBTE（ＰＫ，ｗ(t)，ＳＫw(t)，Ｃ）を実行することによりメッセージＭを得る。
【００６３】
BGW Scheme
BGW Schemeは、D.Boneh,C.Gentry，and B.Waters,"Collusion Resistant Broadcast Encryption With Short Ciphertext and Private Keys",CRYPTO'05,2005.に開示されている技術であり、受信端末装置の総数ｎや不正な受信端末装置の数（無効化する受信端末装置の数）に拘わらず、常にメッセージ長を２、各受信端末装置がそれぞれ保持する秘密鍵の数を１個にすることが可能な公開鍵型同報通信暗号である。
【００６４】
BGW Schemeの安全性は、BTEの安全性と同様に、BDH問題の難しさに基づいている。Ｇ1，Ｇ2は位数を素数ｑとした巡回群であって、それぞれは乗法群とした場合、双線形写像ｅ：Ｇ1×Ｇ1→Ｇ2は、∀Ｐ，Ｑ∈Ｇ1，∀ａ，ｂ∈Ｚqについて、ｅ（Ｐa，Ｑb）＝ｅ（Ｐb，Ｑa）＝ｅ（Ｐ、Ｑ）abである。
【００６５】
BGW SchemeにおけるセットアップアルゴリズムGENBGW、暗号化アルゴリズムENCBGW、および復号化アルゴリズムDECBGWについて説明する。
【００６６】
セットアップアルゴリズムGENBGW
セキュリティパラメータ１λと受信端末装置の総数ｎを入力とした場合のセットアップアルゴリズムGENBGW（１λ，ｎ）は、以下の（１）乃至（３）の処理からなる。
（１）BDHパラメータジェネレータＩＧ（１λ）を実行し、位数ｑの乗法群Ｇ1，Ｇ2と双線形写像ｅを生成する。
（２）Ｇ1の生成元ｇとα，β∈Ｚqをランダムに選択し、ｇi，ｓｋi，ｖを計算する。
【数２】
2007189597.tif 000004
（３）ＰＫ＝（ｇ，ｇ1，…，ｇn，ｇn+2，…，ｇ2n，ｖ）を公開鍵、ｓｋiを受信端末装置ｉ（ｉ＝１，…，ｎ，ｎ＋２，…，２ｎ）の秘密鍵、α，βをシステムの秘密鍵とする。
【００６７】
暗号化アルゴリズムENCBGW
正規の受信端末装置の集合Ｓ⊆｛１，２，…，ｎ｝と公開鍵ＰＫを入力とする暗号化アルゴリズムENCBGW（Ｓ，ＰＫ）は、以下の（１）乃至（３）の処理からなる。なお、正規の受信端末装置の集合Ｓ⊆｛１，２，…，ｎ｝に対するセッション鍵Ｋを用いた暗号化関数をＥKとする。
（１）乱数ｒ∈Ｚqを発生し、セッション鍵Ｋ＝ｅ（ｇn+1，ｇ）rを決定する。なお、ｅ（ｇn+1，ｇ）は、（ｇn，ｇ1）に基づいて計算する。
（２）コンテンツＭを暗号化関数ＥKを用いて暗号化し、暗号文Ｃ＝ＥK（Ｍ）を得る。さらに、Hdrを計算する。
【数３】
2007189597.tif 000005
（３）暗号文ＣとHdrを出力する。
【００６８】
復号化アルゴリズムDECBGW
暗号文Ｃを復号化する復号化アルゴリズムDECBGW（Ｃ，Hdr，Ｓ，ｉ，ｓｋi，ＰＫ）は、以下の（１）および（２）の処理からなる。
（１）ｉ∈Ｓを満たす受信端末装置ｉでは、保持する秘密鍵ｓｋiを用いてセッション鍵Ｋを算出する。
【数４】
2007189597.tif 000006
（２）ＥK（Ｃ）でコンテンツＭを復号化する。
【００６９】
次に、本発明を適用した同報通信システム１によって実現される第１乃至３の同報通信暗号について説明する。
【００７０】
第１の同報通信暗号では、送信側において公開鍵を用いるＳＤ法にBTEを適用する。BTEでは、上述したように親の秘密鍵から子の秘密鍵を作成できるので、２分木の内部ノードａを基点として子の秘密鍵を生成する場合、それぞれ異なるρa,cを用いて秘密鍵ＳＫa,cを作成すれば、各カバーリングに対してそれぞれ異なる秘密鍵を割り当てることができる。また、BTEは双線形写像を用いているので、公開鍵を用いて暗号化を行う同報通信暗号が実現できる。
【００７１】
第１の同報通信暗号におけるセットアップアルゴリズムGENSD、初期鍵生成アルゴリズムDER_CENTSD、鍵導出アルゴリズムDER_TERMSD、暗号化アルゴリズムENCSD、および復号化アルゴリズムDECSDについて説明する。
【００７２】
セットアップアルゴリズムGENSD
セキュリティパラメータ１λと木の高さｈを入力とした場合のセットアップアルゴリズムGENSD（１λ，ｈ）は、以下の（１）乃至（４）の処理からなる。
（１）BDHパラメータジェネレータＩＧ（１λ）を実行し、位数ｑの群Ｇ1、Ｇ2と双線形写像ｅを生成する。
（２）ランダムにＰ∈Ｇ1とα∈Ｚqを選択し、Ｑ＝αＰとする。ここで、Ｚqは０以上ｑ未満の整数の集合である。
（３）暗号的ハッシュ関数Ｈ1：｛０，１｝*→Ｇ1を選択する。
（４）ＰＫ＝（Ｇ1，Ｇ2，ｅ，Ｐ，Ｑ，Ｈ1）を公開鍵、Ｓε＝αＨ1（ε）をルートの秘密鍵、Ｓε'＝αＨ1（ε’）を無効化する受信端末装置がない場合におけるＳＤ法のカバーリングに対応しない秘密鍵とする。
【００７３】
初期鍵生成アルゴリズムDER_CENTSD
受信端末装置に保持させる、ＳＤ法のカバーリングＳＤa,bに対応する秘密鍵ＳＫa,bを生成する初期鍵生成アルゴリズムDERSD（ＰＫ，ａ，ｂ）は、以下の（１）および（２）の処理からなる。
（１）ランダムにρa,b∈Ｚqを選択し、Ｒa,b＝ρa,bＰ、Ｓa,b＝Ｓε＋ρa,bＨ1（ｂ）を算出する。
（２）ＳＫa,b＝（Ｒa,b，Ｓa,b）を出力する。
【００７４】
なお、受信端末装置にはＳＤ法と同数の秘密鍵ＳＫa,bと秘密鍵Ｓε'を保持させる。例えば、ノードｗに割り当てられた受信端末装置には、ルートからノードｗまでのパス上のノードをａ、当該パスから分岐するノードをｂとした場合、秘密鍵ＳＫa,b＝（Ｒa,b，Ｓa,b）＝（ρa,bＰ，Ｓε＋ρa,bＨ（ｂ））が保持される。
ａはｗ｜i    ０≦ｉ＜logｎ
ｂはｗ｜jの兄弟ノード    １≦ｊ≦logｎ
【００７５】
鍵導出アルゴリズムDER_TERMSD
受信端末装置において親の秘密鍵ＳＫa,bから子の秘密鍵ＳＫ’a,b0、ＳＫ’a,b1を導出する鍵導出アルゴリズムDER_TERMSD（ＰＫ，ａ，ｂ，ＳＫa,b）は、以下の（１）および（２）の処理からなる。なお、ＳＫ’a,b0などの「’」は、受信端末装置において導出した秘密鍵とその鍵成分を意味するものとする。
（１）ランダムにρ’a,b0，ρ’a,b1∈Ｚqを選択し、Ｒ’a,b0＝ρ’a,b0Ｐ、Ｒ’a,b1＝ρ’a,b1Ｐ、Ｓ’a,b0＝Ｓa,b＋ρ’a,b0Ｈ1（ｂ０）、Ｓ’a,b1＝Ｓa,b＋ρ’a,b1Ｈ1（ｂ１）を算出する。
（２）ＳＫ’a,b0＝（Ｒa,b，Ｒ’a,b0，Ｓ’a,b0）、ＳＫ’a,b1＝（Ｒa,b，Ｒ’a,b1，Ｓ’a,b1）を出力する。
【００７６】
暗号化アルゴリズムENCSD
コンテンツ鍵Ｋ∈Ｇ2を入力とし、カバーリングＳＤa,cに対応する暗号文Ｕa，Ｖaを出力する暗号化アルゴリズムENCSD（ＰＫ，ａ，ｃ，Ｋ）は、以下の（１）乃至（５）の処理からなる。
（１）乱数ｒa∈Ｚqを発生する。
（２）ノードａからノードｃまでのパス上に存在するノードａの子ノードｂを検出する。
（３）Ｖa＝Ｋ・ｄaを算出する。ここで、ｄa＝ｅ（Ｑ，Ｈ1（ε））raである。
（４）Ｕa＝（ｒaＰ，ｒaＨ1（ｃ｜|b|），ｒaＨ1（ｃ｜|b|+1），…,ｒaＨ1（ｃ｜|c|））＝（Ｕa,0，Ｕa,c||b|，…，Ｕa,c||c|）を算出する。
（５）暗号文Ｕa，Ｖaと乱数ｒaを出力する。
【００７７】
復号化アルゴリズムDECSD
受信端末装置において秘密鍵ＳＫa,bに基づいて、暗号文Ｕa，Ｖaを復号化する復号化アルゴリズムDECSD（ＰＫ，ａ，ｂ，ｃ，ＳＫa,b，Ｕa，Ｖa）は、以下の（１）および（２）の処理からなる。
（１）受信端末装置が保持している秘密鍵ＳＫa,bを用い、上述した鍵導出アルゴリズムDER_TERMSD（ＰＫ，ａ，ｂ，ＳＫa,b）をノードｂからノードｃに到るまで繰り返し実行することにより、秘密鍵ＳＫ’a,c＝（Ｒa,c||b|，Ｒ’a,c||b|+1，…，Ｒ’a,c||c|，Ｓ’a,c）を得る。
（２）次式に基づいてｄaを算出する。
【数５】
2007189597.tif 000007
ここで、Ｄは次式のとおりである。
【数６】
2007189597.tif 000008
（３）Ｖa／ｄaを算出することによりコンテンツ鍵Ｋを得る。Ｋ＝Ｖa／ｄa
（４）コンテンツ鍵Ｋを用いて暗号文ＥK（Ｍ）を復号化し、コンテンツＭを得る。
【００７８】
次に、例えば図５に示すように、８台の受信端末装置（リーフ000に割り当てられた受信端末装置をｕ000と記述する。他も同様とする）のうち、ｕ001，ｕ100，ｕ101の３台を無効化するようにコンテンツを送信し、ｕ010においてコンテンツを再生する場合を例にして、第１の同報通信暗号を具体的に説明する。
【００７９】
なお、ｕ010には、秘密鍵Ｓε'と初期鍵生成アルゴリズムDER_CENTSDを用いて生成された秘密鍵ＳＫε,1，ＳＫε,00，ＳＫε,011，ＳＫ0,00，ＳＫ0,011，ＳＫ01,011が予め保持されているものとする。
【００８０】
図６は、第１の同報通信暗号における送信装置１０の処理(第１の暗号化処理)を説明するフローチャートである。
【００８１】
ステップＳ１において、暗号化部１１は、無効化する受信端末装置のノードに基づいてＳＤ法におけるカバーリングＳＤa,cを決定する。図５の例の場合、２個のカバーリングＳＤ0,001，ＳＤ1,10が決定される。
【００８２】
ステップＳ２において、暗号化部１１は、コンテンツ鍵Ｋを選択し、選択したコンテンツ鍵Ｋを用いてコンテンツＭを暗号化し、ＥK（Ｍ）を得る。
【００８３】
ステップＳ３において、暗号化部１１は、ステップＳ１で決定したカバーリングＳＤa,cにそれぞれ対応して暗号化アルゴリズムENCSDを実行する。図５の例の場合、暗号化アルゴリズムENCSD（ＰＫ，０，００１，Ｋ），ENCSD（ＰＫ，１，１０，Ｋ）を実行する。そして、暗号化アルゴリズムENCSD（ＰＫ，０，００１，Ｋ）の結果として、Ｕ0＝（ｒ0Ｐ，ｒ0Ｈ1（００），ｒ0Ｈ1（００１）），Ｖ0＝Ｋ・ｄ0を得る。また、暗号化アルゴリズムENCSD（ＰＫ，１，１０，Ｋ）の結果として、Ｕ1＝（ｒ1Ｐ，ｒ1Ｈ1（１０）），Ｖ1＝Ｋ・ｄ1を得る。ここで、ｄ0＝ｅ（Ｑ，Ｈ1（ε））r0，ｄ1＝ｅ（Ｑ，Ｈ1（ε））r1である。
【００８４】
ステップＳ４において、暗号化部１１は、ステップＳ２およびＳ３の処理結果に、カバーリングＳＤa,cの個数だけ検索情報ｉを付加して暗号文ＣSDを生成し、送信部１２に出力する。図５の例の場合、検索情報ｉ0，ｉ1を付加して暗号文ＣSD＝＜ｉ0，ｉ1；Ｕ0，Ｕ1；Ｖ0，Ｖ1；ＥK（Ｍ）＞を生成し、送信部1２に出力する。なお、検索情報ｉ0，ｉ1は、受信端末装置において暗号文ＣSDの中から暗号化鍵Ｕ0，Ｕ1；Ｖ0，Ｖ1を検索するためのものである。送信部１２は、暗号文ＣSDを通信網３０を介して送信する。以上で、第１の暗号化処理は終了される。
【００８５】
図７は、第１の同報通信暗号における受信端末装置ｕ010の処理(第１の復号化処理)を説明するフローチャートである。
【００８６】
ステップＳ１１において、受信部２１は、送信装置１０から送信された暗号文ＣSDを取得して復号化部２２に出力する。ステップＳ１２において、復号化部２２は、暗号文ＣSDに含まれる検索情報ｉ0，ｉ1に基づいて暗号化鍵Ｕ0，Ｕ1；Ｖ0，Ｖ1を検索し、予め保持している秘密鍵ＳＫ0,00を入力として鍵導出アルゴリズムDER_TERMSD（ＰＫ，０，００，ＳＫ0,00）を実行し、秘密鍵ＳＫ’0,000，ＳＫ’0,001を生成する。このうち、秘密鍵ＳＫ’0,001が目的の機密鍵である。
【００８７】
ステップＳ１３において、復号化部２２は、秘密鍵ＳＫ’0,001＝（Ｒ0,00，Ｒ’0,001，Ｓ’0,001）を用い、次式のようにｄ0を計算する。ただし、ｄ0を算出する過程で発生させるρ’0,001は、送信装置１０で発生されたρ0,001と異なることに注意が必要である。さらに、復号化部２２は、Ｖ0／ｄ0を計算することによってコンテンツ鍵Ｋを取得する。
【数７】
2007189597.tif 000009
【００８８】
ステップＳ１４において、復号化部２２は、ステップＳ１３で生成したコンテンツ鍵Ｋを用い、ＥK（Ｍ）を復号化してコンテンツＭを取得する。以上で、受信端末装置ｕ010による第１の復号化処理は終了される。
【００８９】
なお、例えば、受信端末装置ｕ0O0は、予め秘密鍵ＳＫ0,001を保持しているので、ステップＳ１２の処理を省略することができる。
【００９０】
次に、第２の同報通信暗号について説明する。第２の同報通信暗号は、上述した第１の同報通信暗号にＦＳを適用した。すなわち、第２の同報通信暗号では、ＳＤ法における親の秘密鍵から子の秘密鍵を生成する２分木と、各秘密鍵を所定の時間周期で更新させる２分木の２つの２分木が用いられる。
【００９１】
第２の同報通信暗号におけるセットアップアルゴリズムGENSD_FS、鍵生成アルゴリズムDER_CENTSD_FS、鍵更新アルゴリズムKUP_TERMSD_FS、暗号化アルゴリズムENCSD_FS、および復号化アルゴリズムDECSD_FSについて説明する。
【００９２】
セットアップアルゴリズムGENSD_FS
セキュリティパラメータ１λと木の高さｈを入力とした場合のセットアップアルゴリズムGENSD_FS（１λ，ｈ）は、以下の（１）乃至（３）の処理からなる。
（１）セットアップアルゴリズムGENSD（１λ，ｈ）を実行することにより公開鍵ＰＫを得る。
（２）暗号的ハッシュ関数Ｈ2：｛０，１｝*→Ｇ1を選択する。
（３）ＰＫにＨ2を追加し、ＰＫ＝（Ｇ1，Ｇ2，ｅ，Ｐ，Ｑ，Ｈ1，Ｈ2）を公開鍵とする。
【００９３】
鍵生成アルゴリズムDER_CENTSD_FS
受信端末装置に保持させる、ＳＤ法のカバーリングＳＤa,bに対応する時刻ｔ＝０の秘密鍵ＳＫa,b,w(0)を生成する鍵生成アルゴリズムDERSD_FS（ＰＫ，ａ，ｂ，ｔ）は、以下の（１）および（２）の処理からなる。
（１）初期鍵生成アルゴリズムDER_CENTSDを実行してＳＫa,b＝（Ｒa,b，Ｓa,b）を得る。
（２）ＳＫa,bを秘密鍵ＳＫa,b,w(0)として出力する。
【００９４】
鍵更新アルゴリズムKUP_TERMSD_FS
受信端末装置において、保持している時刻ｔの秘密鍵ＳＫa,b,w(t)を時刻ｔ＋１の秘密鍵ＳＫa,b,w(t+1)に更新する鍵更新アルゴリズムKUP_TERMSD_FS（ＰＫ，ｔ，ＳＫa,b,w(t)）は、以下の（１）乃至（５）の処理からなる。
（１）時刻ｔに対応するノードｗ(t)を算出する。
（２）ノードｗ(t)が２分木の内部ノードであるか、リーフであるかを判定する。
（３）ノードｗ(t)が２分木の内部ノードである場合、ランダムにσ’w(t)0，σ’w(t)1∈Ｚqを選択し、Ｒ’w(t)0＝σ’w(t)0Ｐ、Ｒ’w(t)1＝σ’w(t)1Ｐ、Ｓ’a,b,w(t)0＝Ｓa,b,w(t)＋σ’w(t)0Ｈ2（ｗ(t)０）、Ｓ’a,b,w(t)1＝Ｓa,b,w(t)＋σ’w(t)1Ｈ2（ｗ(t)１）を算出する。
さらに、秘密鍵ＳＫ’a,b,w(t)0
＝（Ｒa,b，Ｒ’w|1，…，Ｒ’w||w(t)|，Ｒ’w(t)0，Ｓ’a,b,w(t)0）
秘密鍵ＳＫ’a,b,w(t)1
＝（Ｒa,b，Ｒ’w|1，…，Ｒ’w||w(t)|，Ｒ’w(t)1，Ｓ’a,b,w(t)1）
を生成して秘密鍵ＳＫ’a,b,w(t)0を時刻ｔ＋１の秘密鍵ＳＫ’a,b,w(t+1)として使用し、秘密鍵ＳＫ’a,b,w(t)1をスタックに蓄積する。
（４）ノードｗ(t)が２分木のリーフである場合、スタックに蓄積されている秘密鍵を取り出して時刻ｔ＋１の秘密鍵秘密鍵ＳＫ’a,b,w(t+1)として使用する。
（５）時刻ｔの秘密鍵ＳＫa,b,w(t)を消去する。
【００９５】
暗号化アルゴリズムENCSD_FS
暗号化アルゴリズムENCSD_FSは、カバーリングＳＤa,bごとに異なる時刻ｔを設定して実行することができる。受信端末装置が時刻ｔ1の秘密鍵ＳＫ’a,b,w(t1)を保持している場合、暗号化アルゴリズムENCSD_FSの実行タイミングは時刻ｔ2とする（ｔ2≧ｔ1）。ただし、「ｔ1」，「ｔ2」などを上付文字や下付文字として使用する場合、表記の都合上、数字の下付を解除して、t1，t2，t1，t2とも記述する。コンテンツ鍵Ｋ∈Ｇ2を入力とし、カバーリングＳＤa,c、時刻ｔ＝ｔ２に対応する暗号文Ｕa，Ｖaを出力する暗号化アルゴリズムENCSD_FS（ＰＫ，ａ，ｃ，ｔ，Ｋ）は、以下の（１）乃至（４）の処理からなる。
（１）時刻ｔ2のノードｗ(t2)を計算する。
（２）ENCSD（ＰＫ，ａ，ｃ，Ｋ）を実行し、暗号文Ｕa，Ｖaと乱数ｒaを得る。
（３）（ｒaＨ2（ｗ(t2)｜1），…,ｒaＨ2（ｗ(t2)｜|w(t2)|））＝（Ｕa,w(t2)|1，…，Ｕa,w(t2)|w(t2)，ｔ2）をＵaに追加する。
（４）暗号文Ｕa，Ｖaを出力する。
【００９６】
復号化アルゴリズムDECSD_FS
受信端末装置において、保持する時刻ｔ1の秘密鍵ＳＫ’a,b,w(t1)に基づいて、暗号文Ｕa，Ｖaを復号化する復号化アルゴリズムDECSD_FS（ＰＫ，ａ，ｂ，ｃ，ＳＫa,b,w(t)，Ｕa，Ｖa）は、以下の（１）乃至（４）の処理からなる。
（１）鍵更新アルゴリズムKUP_TERMSD_FS（ＰＫ，ｔ，ＳＫ’a,b,w(t1)）を時刻ｔ2まで適用して秘密鍵ＳＫ’a,b,w(t2)を得る。次式に基づいてｄaを算出する。
【数８】
2007189597.tif 000010
ここで、Ｄ1、Ｄ2は次式のとおりである。
【数９】
2007189597.tif 000011
（２）受信端末装置が保持している秘密鍵ＳＫ’a,b,w(t2)を用い、鍵導出アルゴリズムDER_TERMSD（ＰＫ，ａ，ｂ，ＳＫ’a,b,w(t2)）をノードｂからノードｃに到るまで繰り返し実行することにより、秘密鍵ＳＫ’a,c,w(t2)を得る。
（３）Ｖa／ｄaを算出することによりコンテンツ鍵Ｋを得る。Ｋ＝Ｖa／ｄa
（４）コンテンツ鍵Ｋを用いて暗号文ＥK（Ｍ）を復号化し、コンテンツＭを得る。
【００９７】
なお、スタックに蓄積する秘密鍵は、受信端末装置に初期に格納された秘密鍵を入力として鍵更新アルゴリズムKUP_TERMSD_FSを実行した結果得られる秘密鍵であり、鍵導出アルゴリズムDER_TERMSDの実行結果を入力として鍵更新アルゴリズムKUP_TERMSD_FSを実行して得る秘密鍵ではないことに注意する。
【００９８】
次に、上述した図５に示された場合を例にして、第２の同報通信暗号を具体的に説明する。
【００９９】
なお、ｕ010には、時刻ｔ1に対応する秘密鍵Ｓε',w(t1)と初期鍵生成アルゴリズムDER_CENTSD_FSを用いて生成された秘密鍵ＳＫε,1,w(t1)，ＳＫε,00,w(t1)，ＳＫε,011,w(t1)，ＳＫ0,00,w(t1)，ＳＫ0,011,w(t1)，ＳＫ01,011,w(t1)が予め保持されているものとする。
【０１００】
図８は、第２の同報通信暗号における送信装置１０の処理(第２の暗号化処理)を説明するフローチャートである。
【０１０１】
ステップＳ２１において、暗号化部１１は、無効化する受信端末装置のノードに基づいてＳＤ法におけるカバーリングＳＤa,cを決定する。図５の例の場合、２個のカバーリングＳＤ0,001，ＳＤ1,10が決定される。
【０１０２】
ステップＳ２２において、暗号化部１１は、コンテンツ鍵Ｋを選択し、選択したコンテンツ鍵Ｋを用いてコンテンツＭを暗号化し、ＥK（Ｍ）を得る。
【０１０３】
ステップＳ２３において、暗号化部１１は、ステップＳ２１で決定したカバーリングＳＤa,cにそれぞれ対応し、暗号化アルゴリズムENCSD_FSを実行し、暗号文を得る。図５の例の場合、暗号化アルゴリズムENCSD_FS（ＰＫ，０，００１，ｔ2，Ｋ），ENCSD_FS（ＰＫ，１，１０，ｔ2，Ｋ）を実行し、暗号文Ｕ0，Ｖ0と暗号文Ｕ1，Ｖ1を得る。
【０１０４】
ステップＳ２４において、暗号化部１１は、ステップＳ２２およびＳ２３の処理結果に、カバーリングＳＤa,cの個数に対応する検索情報ｉを付加して暗号文ＣSDを生成し、送信部１２に出力する。図５の例の場合、検索情報ｉ0，ｉ1を付加して暗号文ＣSD＝＜ｉ0，ｉ1；Ｕ0，Ｕ1；Ｖ0，Ｖ1；ＥK（Ｍ）＞を生成し、送信部1２に出力する。送信部１２は、暗号文ＣSDを通信網３０を介して送信する。以上で、第２の暗号化処理は終了される。
【０１０５】
図９は、第２の同報通信暗号における受信端末装置ｕ010の処理(第２の復号化処理)を説明するフローチャートである。
【０１０６】
ステップＳ３１において、受信部２１は、送信装置１０から送信された暗号文ＣSDを取得して復号化部２２に出力する。ステップＳ３２において、復号化部２２は、暗号文ＣSDに含まれる検索情報ｉ0，ｉ1に基づいて暗号化鍵Ｕ0，Ｕ1；Ｖ0，Ｖ1を検索する。そして、予め保持している時刻ｔ1の秘密鍵ＳＫ0,00,w(t)を入力として鍵更新アルゴリズムKUP_TERMSD_FS（ＰＫ，ｔ，ＳＫ’0,00,w(t1)）を時刻ｔ2まで適用し、秘密鍵ＳＫ’0,00,w(t2)を生成する。さらに生成した秘密鍵ＳＫ’0,00,w(t2)を入力として、鍵導出アルゴリズムDER_TERMSD（ＰＫ，０，００，ＳＫ0,00,w(t2)）を実行し、秘密鍵ＳＫ’0,000,w(t2)，ＳＫ’0,001,w(t2)を生成する。
【０１０７】
ステップＳ３３において、復号化部２２は、秘密鍵ＳＫ’0,001,w(t2)を用いてｄ0を計算し、Ｖ0／ｄ0を計算することによってコンテンツ鍵Ｋを取得する。
【０１０８】
ステップＳ３４において、復号化部２２は、ステップＳ３３で生成したコンテンツ鍵Ｋを用い、ＥK（Ｍ）を復号化してコンテンツＭを取得する。以上で、受信端末装置ｕ010による第２の復号化処理は終了される。
【０１０９】
なお、時刻ｔ2＝ｔ1である場合、ステップＳ３２において実行した鍵更新アルゴリズムKUP_TERMSD_FSを省略することができる。
【０１１０】
次に、第３の同報通信暗号について説明する。第３の同報通信暗号は、上述したBGW SchemeにＦＳを適用した。
【０１１１】
第３の同報通信暗号におけるセットアップアルゴリズムGENBGW_FS、鍵更新アルゴリズムKUP_TERMBGW_FS、暗号化アルゴリズムENCBGW_FS、および復号化アルゴリズムDECBGW_FSについて説明する。
【０１１２】
セットアップアルゴリズムGENBGW_FS
セキュリティパラメータ１λと受信端末装置の総数ｎを入力とした場合のセットアップアルゴリズムGENBGW_FS（１λ，ｎ）は、以下の（１）乃至（３）の処理からなる。
（１）BDHパラメータジェネレータＩＧ（１λ）を実行し、位数ｑの乗法群Ｇ1，Ｇ2と双線形写像ｅを生成する。
（２）Ｇ1の生成元ｇとα，β∈Ｚqをランダムに選択し、ｇi，ｓｋi,w(0)，ｖを計算する。
【数１０】
2007189597.tif 000012
（３）ＰＫ＝（ｇ，ｇ1，…，ｇn，ｇn+2，…，ｇ2n，ｖ）を公開鍵、ｓｋi,w(0)を受信端末装置ｉ（ｉ＝１，…，ｎ，ｎ＋２，…，２ｎ）の時刻ｔ＝０における秘密鍵、α，βをシステムの秘密鍵とする。
【０１１３】
鍵更新アルゴリズムKUP_TERMBGW_FS
受信端末装置において、保持している時刻ｔの秘密鍵ＳＫi,w(t)を時刻ｔ＋１の秘密鍵ＳＫi,w(t+1)に更新する鍵更新アルゴリズムKUP_TERMBGW_FS（ＰＫ，ｔ，ＳＫi,w(t)）は、以下の（１）乃至（５）の処理からなる。
（１）時刻ｔに対応するノードｗ(t)を算出する。
（２）ノードｗ(t)が２分木の内部ノードであるか、リーフであるかを判定する。
（３）ノードｗ(t)が２分木の内部ノードである場合、ランダムにσ’w(t)0，σ’w(t)1∈Ｚqを選択し、次式に基づいてＲ’i,w(t)0，Ｒ’i,w(t)1，ｓｋi,w(t)0，ｓｋi,w(t)1を算出する。
【数１１】
2007189597.tif 000013
さらに、秘密鍵ＳＫ’i,w(t)0
＝（Ｒ’i,w|1，…，Ｒ’i,w||w(t)|，Ｒ’i,w(t)0，ｓｋi,w(t)0）
秘密鍵ＳＫ’i,w(t)1
＝（Ｒ’i,w|1，…，Ｒ’i,w||w(t)|，Ｒ’i,w(t)1，ｓｋi,w(t)1）
を生成して、秘密鍵ＳＫ’i,w(t)0を時刻ｔ＋１の秘密鍵ＳＫ’i,w(t+1)として使用し、秘密鍵ＳＫ’i,w(t)1をスタックに蓄積する。
（４）ノードｗ(t)が２分木のリーフである場合、スタックに蓄積されている秘密鍵を取り出して時刻ｔ＋１の秘密鍵秘密鍵ＳＫ’i,w(t+1)として使用する。
（５）時刻ｔの秘密鍵ＳＫi,w(t)を消去する。
【０１１４】
暗号化アルゴリズムENCBGW_FS
正規の受信端末装置の集合Ｓ⊆｛１，２，…，ｎ｝と公開鍵ＰＫ、時刻ｔ2を入力とする暗号化アルゴリズムENCBGW_FS（Ｓ，ＰＫ，ｔ）は、以下の（１）乃至（６）の処理からなる。なお、正規の受信端末装置の集合Ｓ⊆｛１，２，…，ｎ｝に対するセッション鍵Ｋを用いた暗号化関数をＥKとする。
（１）時刻ｔ2に対応するノードｗ(t2)を算出する。
（２）乱数ｒ∈Ｚqを発生し、セッション鍵Ｋ＝ｅ（ｇn+1，ｇ）rを決定する。なお、ｅ（ｇn+1，ｇ）は、（ｇn，ｇ1）に基づいて計算する。
（３）コンテンツＭを暗号化関数ＥKを用いて暗号化し、暗号文Ｃ＝ＥK（Ｍ）を得る。さらに、Hdrを計算する。
【数１２】
2007189597.tif 000014
（４）（Ｈ（ｗ(t2)｜1）r，…,Ｈ（ｗ(t2)｜|w(t2)|）r）
＝（Ｕw(t2)|1，…，Ｕw(t2)||w(t2)|）をHdrに追加する。
（５）ｔをHdrに追加する。
（６）暗号文ＣとHdrを出力する。
【０１１５】
復号化アルゴリズムDECBGW_FS
受信端末装置において、保持している時刻ｔ１の秘密鍵ＳＫi,w(t1)を用いて、暗号文Ｃを復号化する復号化アルゴリズムDECBGW_FS（Ｃ，Hdr，Ｓ，ｉ，ＳＫi,w(t1)，ＰＫ）は、以下の（１）乃至（３）の処理からなる。
（１）ｉ∈Ｓを満たす受信端末装置ｉの受信端末装置では、保持する秘密鍵ＳＫi,w(t1)をHdrに含まれている時刻ｔ＝ｔ2まで、鍵更新アルゴリズムKUP_TERMBGW_FSを適用して更新し、秘密鍵ＳＫi,w(t2)を得る。
（２）秘密鍵ＳＫi,w(t2)を用いてセッション鍵Ｋを算出する。
【数１３】
2007189597.tif 000015
（３）ＥK（Ｃ）でコンテンツＭを復号化する。
【０１１６】
次に、受信端末装置の集合を｛１，２，３｝、正規受信端末装置の集合Ｓ＝｛１，２｝、時刻の２分木の高さｈ＝３、時刻ｔ＝１の場合を例にして、第３の同報通信暗号を具体的に説明する。
【０１１７】
図１０は、第３の同報通信暗号における送信装置１０の処理(第３の暗号化処理)を説明するフローチャートである。
【０１１８】
ステップＳ４１において、暗号化部１１は、ENCBGW_FS（Ｓ，ＰＫ，１）を実行し、その結果得られる暗号文Ｃ，Hdr＝（Ｃ0，Ｃ1，Ｕ0，１）を送信部１２に出力する。ここで、
【数１４】
2007189597.tif 000016
である。
【０１１９】
ステップＳ４２において、送信部１２は、暗号文Ｃ，Hdrを通信網３０を介して送信する。以上で、第３の暗号化処理は終了される。
【０１２０】
図１１は、第３の同報通信暗号における正規の受信端末装置１による処理(第３の復号化処理)を説明するフローチャートである。
【０１２１】
ステップＳ５１において、受信部２１は、送信装置１０から送信された暗号文Ｃ,Hdrを取得して復号化部２２に出力する。ステップＳ５２において、復号化部２２は、予め保持している秘密鍵ＳＫ1,εに復号化アルゴリズムDECBGW_FS（Ｃ，Hdr，Ｓ，ｉ，ＳＫ1,ε，ＰＫ）を適用して、セッション鍵Ｋを取得する。
【０１２２】
具体的には、Hdrから時刻情報ｔ＝１を読み出し、ノードｗ(1)＝０を計算する。そして、秘密鍵ＳＫ1,εを入力として鍵更新アルゴリズムKUP_TERMBGW_FS（ＰＫ，１，ＳＫ1,ε）を実行する。εは２分木の内部ノードであるので、ランダムにσ’1,0，σ’1,1∈Ｚqを選択し、次式に基づいてＲ’1,0，Ｒ’1,1，ｓｋ1,0，ｓｋ1,1を算出する。
【数１５】
2007189597.tif 000017
さらに、秘密鍵ＳＫ’1,0＝（Ｒ’1,0，ｓｋ1,0），ＳＫ’1,1＝（Ｒ’1,1，ｓｋ1,1）を生成し、秘密鍵ＳＫ’1,0，ＳＫ’1,1のうち、一方の秘密鍵ＳＫ’1,0を時刻ｔ＝１の秘密鍵として使用する。他方の秘密鍵ＳＫ’1,1はスタックに蓄積される。そして、時刻ｔ＝１の秘密鍵ＳＫ’1,0を用いてセッション鍵Ｋが算出される。
【数１６】
2007189597.tif 000018
【０１２３】
このようにして得られるセッション鍵Ｋが得られた後、ステップＳ５３において、復号化部２２は、ＥK（Ｃ）でコンテンツＭを復号化する。以上で、正規の受信端末装置１による第３の復号化処理は終了される。
【０１２４】
なお、正規の受信端末装置２による第３の復号化処理も同様に実行され、処理結果としてコンテンツＭを得ることができる。反対に、正規ではない不正な受信端末装置３においてはコンテンツＭを得ることができない。この不正な受信端末装置３に対する安全性について説明する。
【０１２５】
不正な受信端末装置３が復号化アルゴリズムDECBGW_FS（Ｃ，Hdr，Ｓ，ｉ，ＳＫ3,ε，ＰＫ）を実行すると、セッション鍵となるＫは次式のように算出される。
【数１７】
2007189597.tif 000019
【０１２６】
分子の第１項より、ｅ（ｇ3，（ｖｇ3ｇ2）r）＝ｅ（ｇr，ｖｇ6ｇ5）となるので、セッション鍵に相当するｅ（ｇr，ｇ4）が得られないことがわかる。したがって、コンテンツＭを得ることができない。
【０１２７】
仮に、セッション鍵に相当するｅ（ｇr，ｇ4）を得るため、アルゴリズムに反してＩＤを偽造し、分子の第１項をｅ（ｇ1，（ｖｇ3ｇ2）r）にしてみるとセッション鍵となるＫは次式のように算出される。
【数１８】
2007189597.tif 000020
【０１２８】
このように、１行目の第１項に用いる公開鍵（いまの場合、ｇ１）を自己のＩＤ以外のものに変更してしまうと、４行目の分子の第２項を消すことができない。すなわち、セッション鍵を得ることができない。よって、第３の同報通信暗号の不正な受信端末装置３に対する安全性が証明された。
【０１２９】
次に、第３の同報通信暗号がＦＳ(Forward Security)を満たしていることを説明する。例えば、正規の受信端末装置１の時刻ｔ=１における秘密鍵ＳＫ’1,0が漏洩したと仮定し、この秘密鍵ＳＫ’1,0に基づいて時刻ｔ＝０の暗号文Ｃ，Hdrが復号化できないことを示す。
【０１３０】
まず、秘密鍵ＳＫ’1,0から時刻ｔ＝０の秘密鍵ＳＫ’1,εを算出することができないことを示す。漏洩した秘密鍵ＳＫ’1,0＝（Ｒ’1,0，ｓｋ1,0）＝（ｇρ'1,0，ｓｋ1,ε・Ｈ（０）ρ'1,0）である。したがって、秘密鍵ＳＫ’1,0からρ’1,0を求めることができない。よってＳＫ’1,0からＳＫ’1,εを算出することができない。
【０１３１】
次に、秘密鍵ＳＫ’1,0を用いて時刻ｔ＝０の暗号文Ｃ，Hdrからセッション鍵Ｋが得られないことを示す。ここで、Ｃ，Ｋ，Hdr，Ｃ0，Ｃ1は以下のとおりである。
【数１９】
2007189597.tif 000021
このとき、復号化アルゴリズムDECBGW_FS（Ｃ，Hdr，Ｓ，ｉ，ＳＫ’1,0，ＰＫ）を実行して得られるＫは、
【数２０】
2007189597.tif 000022
となる。
【０１３２】
この式より、分子にｅ（Ｒ’1,0，Ｈ（０）r）を乗算することができれば、これが分母と相殺されて、セッション鍵に相当するｅ（ｇr，ｇ4）を得られることになる。しかしながら、漏洩した秘密鍵ＳＫ’1,0からＲ’1,0＝ｇρ'1,0は導出できるものの、Ｈ（０）rを導出することはできない。なぜならば、ｒはコンテンツの送信側のみが知りえる値であるからである。したがって、秘密鍵ＳＫ’1,0を用いて時刻ｔ＝０の暗号文Ｃ，Hdrからセッション鍵Ｋを得ることができない。よって、秘密鍵ＳＫ’1,0に基づいて時刻ｔ＝０の暗号文Ｃ，Hdrが復号化できないことが証明された。
【０１３３】
次に、上述した第１乃至３の同報通信暗号の性能を比較する。
【０１３４】
図１２は、第１乃至３の同報通信暗号それぞれのメッセージ長、鍵導出に要する計算量、復号化時に使用される公開鍵数の絶対的な評価とＦＳ機能の有無を示している。第１の同報通信暗号については、その長所として、鍵導出に要する計算量の少なさ、および公開鍵の少なさが挙げられる。第２の同報通信暗号については、その長所として、鍵導出に要する計算量の少なさ、公開鍵の少なさ、およびＦＳ機能を有することを挙げられる。第３の同報通信暗号については、その長所として、正規の受信端末装置の数や不正な受信端末装置の数に拘わらずメッセージ長が短いこと、およびＦＳ機能を有することを挙げられる。
【０１３５】
図１３は、第１乃至３の同報通信暗号それぞれの受信端末装置に保持させるデバイス鍵（秘密鍵）数、同報通信される暗号文に含まれるメッセージ長、受信端末装置での鍵導出時の計算量、および暗号化時と復号化時に使用される公開鍵数の評価値を示している。また図１３には、ＳＤ法に階層型ＩＤベース暗号を適用した同報通信暗号（Y.Dois, and N.Fazio,"Public Key Broadcast Encryption for Stateless Receivers",proceeding of ACM FRM '02,2002参照。以下、DF02と記述する）、およびBGW Schemeに対応するそれぞれの評価値も追記した。
【０１３６】
なお、評価値は想定される最悪値を示しており、鍵数は、鍵の成分の数も考慮した値である。例えば、第１の同報通信暗号におけるデバイス鍵数は、ＳＫa,b＝（Ｒa,b，Ｓa,b）であるので、ＳＤ法におけるデバイス鍵数の２倍とした。
【０１３７】
図１３より、第１の同報通信暗号は、公開鍵数について、DF02やBGW Schemeよりも有利であることがわかる。反対に、デバイス鍵数とメッセージ長については、DF02およびBGW Schemeよりも不利である。しかしながら、デバイス鍵数はＳDF02のわずか２倍に過ぎない。
【０１３８】
第２および第３の同報通信暗号は、従来考えられていなかったＦＳ機能を持っているので、DF02やBGW Schemeと単純に比較することができないが、第２の同報通信暗号では、ＦＳ機能を有するが故に鍵更新の影響でデバイス鍵数が増えているものの、その他の項目については第１の同報通信暗号と同様の性能を維持している。
【０１３９】
第３の同報通信暗号は、第２の同報通信暗号と同様、ＦＳ機能を有するが故にメッセージ長が若干長くなっているものの、その他の項目についてはBGW Schemeと同様の性能を維持している。
【０１４０】
以上説明した第１乃至３の同報通信暗号の評価をまとめると以下のとおりである。すなわち、第１の同報通信暗号は、デバイス鍵数、およびメッセージ長を大幅に増やすことなく、公開鍵を用いた同報通信暗号を実現しており、受信端末装置において目的の秘密鍵を得るまでに要する計算量がBGW Schemeよりも大幅に少ない。ここで、無効化する受信端末装置の数ｒを考慮して比較すると、ｒが少ない場合、第１の同報通信暗号の方がBGW Schemeよりも有利であると言える。このことからさらに、FS機能を考慮した場合、ｒが多い場合、第３の同報通信暗号が有利であり、ｒが少ない場合、第２の同報通信暗号が有利であると言える。
【０１４１】
ところで、本明細書において、プログラムに基づいて実行されるステップは、記載された順序に従って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１４２】
また、プログラムは、１台のコンピュータにより処理されるものであってもよいし、複数のコンピュータによって分散処理されるものであってもよい。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであってもよい。
【０１４３】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０１４４】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０１４５】
【図１】本発明を適用した同報通信システムの構成例を示すブロック図である。
【図２】汎用パーソナルコンピュータの構成例を示すブロック図である。
【図３】ＳＤ法のカバーリングを説明する図である。
【図４】ＦＳで用いる時間の２分木を示す図である。
【図５】第１の同報通信暗号の具体例を説明するための図である。
【図６】第１の暗号化処理を説明するフローチャートである。
【図７】第１の復号化処理を説明するフローチャートである。
【図８】第２の暗号化処理を説明するフローチャートである。
【図９】第２の復号化処理を説明するフローチャートである。
【図１０】第３の暗号化処理を説明するフローチャートである。
【図１１】第３の復号化処理を説明するフローチャートである。
【図１２】第１乃至３の同報通信暗号の絶対的な評価を示す図である。
【図１３】第１乃至３の同報通信暗号の評価値を示す図である。
【符号の説明】
【０１４６】
１  同報通信システム，  １０  送信装置，  １１  暗号化部，  １２  送信部，  ２０  受信端末装置，  ２１  受信部，  ２２  復号化部，  ３０  通信網，  ５１  CPU
【図１】
2007189597.tif 000023
【図２】
2007189597.tif 000024
【図３】
2007189597.tif 000025
【図４】
2007189597.tif 000026
【図５】
2007189597.tif 000027
【図６】
2007189597.tif 000028
【図７】
2007189597.tif 000029
【図８】
2007189597.tif 000030
【図９】
2007189597.tif 000031
【図１０】
2007189597.tif 000032
【図１１】
2007189597.tif 000033
【図１２】
2007189597.tif 000034
【図１３】
2007189597.tif 000035