(57)【要約】【課題】排除される契約者数が少ない場合にも、ヘッダサイズを削減することが可能な、鍵生成装置、暗号化装置、受信装置、鍵生成方法、暗号化方法、鍵処理方法、およびプログラムを提供する。【解決手段】本発明に係る鍵生成装置は、ｎ個の受信装置がリーフに割り当てられたＹ分木構造を階層的に構成し、当該Ｙ分木構造のリーフとルートとの間に存在する中間ノードを各々親ノードとするサブグループを構成する。中間ノードそれぞれに、新たにパラメータを付与することにより、サブグループの構成を柔軟に行うことができ、排除される契約者がいないもしくは少ない場合において、配信されるヘッダサイズおよび契約者が実行する必要がある演算の計算量を、削減することが可能である。【選択図】図１
2008113201.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成する、木構造構成部と、
前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当てるリーフキー割当部と、
前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当部と、
前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて、鍵を算出する鍵算出部と、
を備えることを特徴とする、鍵生成装置。
【請求項２】
前記鍵生成装置は、前記鍵算出部により算出された前記パス上の鍵セットを各受信装置それぞれに配布する配布部を、更に備えることを特徴とする、請求項１に記載の鍵生成装置。
【請求項３】
前記鍵生成装置は、
素数ｐを無作為に選択し、前記素数ｐを位数とする双線形群Ｇを決定し、前記Ｇの生成元であるｇを無作為に選択し、秘密の乱数α（αは整数）を無作為に選択する乱数決定部を更に備え、
前記リーフキー割当部は、以下の式Ａを満たす前記リーフキーｇｙを算出することを特徴とする、請求項１に記載の鍵生成装置。
【数１】
2008113201.tif 000031
（ｙ＝１，２，・・・，Ｙ，Ｙ＋２，・・・，２Ｙ）
【請求項４】
前記パラメータ割当部は、前記リーフを除く全てのノードと前記ルートのそれぞれに対して、ノードパラメータγx,y（γx,yは整数）を無作為に選択し、以下の式Ｂで表されるパラメータνｘ，ｙを算出することを特徴とする、請求項３に記載の鍵生成装置。
【数２】
2008113201.tif 000032
【請求項５】
前記鍵算出部は、前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙの、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータγｘ，ｙ乗で得られる値を、秘密鍵とすることを特徴とする、請求項４に記載の鍵生成装置。
【請求項６】
前記鍵算出部は、前記リーフキーｇｙおよび前記パラメータνｘ，ｙに基づき、公開鍵を算出し、
前記配布部は、前記公開鍵を公開する公開鍵公開部を備えることを特徴とする、請求項５に記載の鍵生成装置。
【請求項７】
前記配布部は、前記鍵算出部において算出された秘密鍵を各受信装置に送信する送信部を更に備えることを特徴とする、請求項５に記載の鍵生成装置。
【請求項８】
ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する、排除受信装置特定部を備えることを特徴とする、暗号化装置。
【請求項９】
前記暗号化装置は、整数ｔを無作為に選択し、セッション鍵ｓ＝ｅ（ｇＹ，ｇ１）ｔを決定するセッション鍵決定部を、更に備えることを特徴とする、請求項８に記載の暗号化装置。
ここで、前記ｅ（ｇＹ，ｇ１）は、双線形群上の２つの元ｇＹ、ｇ１に対する双線形写像を表す。
【請求項１０】
前記暗号化装置は、前記セッション鍵ｓを用いて、配信するコンテンツを暗号化する暗号化部を更に備えることを特徴とする、請求項９に記載の暗号化装置。
【請求項１１】
前記セッション鍵決定部は、階層化された木構造において、前記排除された受信装置が割り当てられたリーフから前記ルートに至るパス上に存在する全てのノードそれぞれにマークをし、前記マークされたノードに割り当てられた前記パラメータνｘ，ｙと、前記マークされたノードを親ノードとする中間ノードに割り当てられた前記リーフキーｇｙと、に基づいて、以下の式Ｃで表されるｃｘ，ｙを算出するヘッダ要素算出部を、更に備えることを特徴とする、請求項９に記載の暗号化装置。
【数３】
2008113201.tif 000033
ここで、Ｓｘ，ｙは、前記マークされたノードを親ノードとする各サブグループに所属する、マークされていない子ノードの集合を示す。
【請求項１２】
前記セッション鍵決定部は、前記ヘッダ要素算出部において得られた前記ｃｘ，ｙと、ｇｔと、をヘッダ情報とするヘッダ情報生成部を更に備えることを特徴とする、請求項１１に記載の暗号化装置。
【請求項１３】
鍵生成装置および暗号化装置と通信可能な受信装置であって、
前記鍵生成装置において、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成し、前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当て、前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて算出された鍵を受信する、受信部を備えることを特徴とする、受信装置。
【請求項１４】
前記受信装置は、暗号化コンテンツをセッション鍵ｓにより復号する復号部を更に備えることを特徴とする、請求項１３に記載の受信装置。
【請求項１５】
前記受信部は、排除する受信装置が特定された情報である、排除されていない受信装置の集合Ｓに関する情報を更に受信し、
前記受信装置は、受信装置が前記集合Ｓに含まれているか否かを判定する判定部を更に備えることを特徴とする、請求項１４に記載の受信装置。
【請求項１６】
前記判定部において、受信装置が前記集合Ｓに含まれていると判定された場合、前記復号部は、セッション鍵ｓを以下に示す式Ｄに基づいて算出し、算出された当該セッション鍵ｓを用いることで、前記暗号化コンテンツを復号化することを特徴とする、請求項１４に記載の受信装置。
【数４】
2008113201.tif 000034
【請求項１７】
ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成する木構造構成ステップと、
前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当てるリーフキー割当ステップと、
前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当ステップと、
前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて、鍵を算出する鍵算出ステップと、
を備えることを特徴とする、鍵生成方法。
【請求項１８】
ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する、排除受信装置特定ステップを備えることを特徴とする、暗号化方法。
【請求項１９】
ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成し、前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当て、前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて算出された鍵を受信するステップを備えることを特徴とする、鍵処理方法。
【請求項２０】
コンピュータに、
ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成する、木構造構成機能と、
前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当てるリーフキー割当機能と、
前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当機能と、
前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて、鍵を算出する鍵算出機能と、
を実現させるためのプログラム。
【請求項２１】
コンピュータに、ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する、排除受信装置特定機能を実現させるためのプログラム。
【請求項２２】
コンピュータに、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成し、前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当て、前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて算出された暗号鍵を受信する受信機能を実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵生成装置、暗号化装置、受信装置、鍵生成方法、暗号化方法、鍵処理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、パーソナルコンピュータ（ＰＣ）のみならず、携帯電話やディジタル家電等の普及、発達に伴い、音楽や映像等のコンテンツ配信ビジネスが益々重要になってきている。コンテンツ配信ビジネスとしては、例えば、ケーブルテレビや衛星放送、またはインターネットを利用した有料放送や、ＣＤ、ＤＶＤ等の物理メディアを利用したコンテンツの販売等があるが、いずれの場合においても、契約者のみがコンテンツを取得可能となる仕組みを構成する必要がある。
【０００３】
通常、このようなコンテンツ配信システムでは、システムの管理者（以下、センタと表記する。）が予め契約者のみに鍵を提供しておき、コンテンツの配信時には、コンテンツＭをセッション鍵ｓで暗号化した暗号文Ｃと、契約者のみがセッション鍵ｓを取得可能とするためのヘッダｈを配信することにより、契約者のみがコンテンツＭを取得可能となる。
【０００４】
上記のような状況を実現するコンテンツ配信方式として、例えば公開鍵を利用した方式がある（例えば、非特許文献１参照。）。
【０００５】
【非特許文献１】Ｄ．Ｂｏｎｅｈ，Ｃ．Ｇｅｎｔｒｙ，Ｂ．Ｗａｔｅｒｓ，“Ｃｏｌｌｕｓｉｏｎ  Ｒｅｓｉｓｔａｎｔ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ  Ｗｉｔｈ  Ｓｈｏｒｔ  Ｃｉｐｈｅｒｔｅｘｔｓ  ａｎｄ  Ｐｒｉｖａｔｅ  Ｋｅｙｓ”，ＣＲＹＰＴＯ’０５，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ２５ｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ，Ｌｏｎｄｏｎ，ＵＫ，Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ，２００５，ｐｐ．５８〜７５．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記の非特許文献１に記載の公開鍵暗号方式では、配信が排除される契約者数が少ない場合であっても、常に一定サイズのヘッダｈを配信する必要があるため、排除される契約者数がゼロの場合、もしくは、契約者全体に占める割合が少ない場合といった現実的に起こりうる状況において、ヘッダサイズを削減することができず、暗号化されたコンテンツの配信時におけるデータの冗長性が高くなるという問題があった。
【０００７】
そこで、本発明は、このような問題に鑑みてなされたもので、その目的は、排除される契約者数が少ない場合であってもヘッダサイズを削減することが可能な、新規かつ改良された鍵生成装置、暗号化装置、受信装置、鍵生成方法、暗号化方法、鍵処理方法、およびプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明の第１の観点によれば、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、リーフとルートとの間に存在する中間ノードの下位に存在する複数のリーフからなるサブグループを構成する、木構造構成部と、リーフおよび中間ノードそれぞれに対して、リーフキーｇｙを割り当てるリーフキー割当部と、中間ノードおよびルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当部と、ルートからリーフに至るパスを特定し、当該パス上に存在する中間ノードまたはリーフに割り当てられたリーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられたパラメータνｘ，ｙおよびノードパラメータγx,yに基づいて、鍵を算出する鍵算出部と、を備える鍵生成装置が提供される。
【０００９】
上記の鍵生成装置は、鍵算出部により算出されたパス上の鍵セットを各受信装置それぞれに配布する配布部を、更に備えるように構成してもよい。
【００１０】
上記の鍵生成装置は、素数ｐを無作為に選択し、素数ｐを位数とする双線形群Ｇを決定し、Ｇの生成元であるｇを無作為に選択し、秘密の乱数α（αは整数）を無作為に選択する乱数決定部を更に備え、上記のリーフキー割当部は、以下の式Ａを満たすリーフキーｇｙを算出するようにしてもよい。ここで、以下の式Ａにおいて、ｙ＝１，２，・・・，Ｙ，Ｙ＋２，・・・，２Ｙである。
【００１１】
【数１】
2008113201.tif 000003
【００１２】
上記パラメータ割当部は、リーフを除く全てのノードとルートのそれぞれに対して、ノードパラメータγx,y（γx,yは整数）を無作為に選択し、以下の式Ｂに示すパラメータνｘ，ｙを算出するようにしてもよい。
【００１３】
【数２】
2008113201.tif 000004
【００１４】
鍵算出部は、中間ノードまたはリーフに割り当てられたリーフキーｇｙの、当該中間ノードまたは当該リーフの親ノードに割り当てられたパラメータγｘ，ｙ乗で得られる値を、秘密鍵としてもよい。すなわち、中間ノードまたはリーフに割り当てられたリーフキーｇｙをＫと略記し、当該中間ノードまたは当該リーフの親ノードに割り当てられたパラメータγｘ，ｙをＴと略記する場合に、ＫＴで得られる値を、秘密鍵としてもよい。
【００１５】
上記の鍵算出部は、リーフキーｇｙおよびパラメータνｘ，ｙに基づき、公開鍵を算出し、上記の配布部は、公開鍵を公開する公開鍵公開部を備えるようにしてもよい。
【００１６】
上記の配布部は、鍵算出部において算出された秘密鍵を各受信装置に送信する送信部を更に備えるようにしてもよい。
【００１７】
上記課題を解決するために、本発明の第２の観点によれば、ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する、排除受信装置特定部を備える暗号化装置が提供される。
【００１８】
上記の暗号化装置は、整数ｔを無作為に選択して、セッション鍵ｓ＝ｅ（ｇＹ，ｇ１）ｔを決定する、セッション鍵決定部を更に備えてもよい。
【００１９】
ここで、上記のｅ（ｇＹ，ｇ１）は、双線形群上の２つの元ｇＹ、ｇ１に対する双線形写像を表す。
【００２０】
上記の暗号化装置は、上記セッション鍵ｓを用いて、配信するコンテンツを暗号化する暗号化部を、更に備えるようにしてもよい。
【００２１】
上記セッション鍵決定部は、階層化された木構造において、排除された受信装置のリーフからルートに至るパス上に存在する全てのノードそれぞれにマークをし、マークされたノードに割り当てられたパラメータνｘ，ｙと、マークされたノードを親ノードとする中間ノードに割り当てられたリーフキーｇｙとに基づいて、以下の式Ｃによりヘッダ要素を算出するヘッダ要素算出部を、更に備えるようにしてもよい。ここで、Ｓｘ，ｙは、マークされたノードを親ノードとする各サブグループに所属する、マークされていない子ノードの集合を表す。
【００２２】
【数３】
2008113201.tif 000005
【００２３】
上記ヘッダ要素算出部において得られたｃｘ，ｙと、ｇｔと、をヘッダ情報とする、ヘッダ情報生成部を更に備えるようにしてもよい。
【００２４】
上記課題を解決するために、本発明の第３の観点によれば、鍵生成装置および暗号化装置と通信可能な受信装置であって、鍵生成装置において、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、リーフとルートとの間に存在する中間ノードの下位に存在する複数のリーフからなるサブグループを構成し、リーフおよび中間ノードそれぞれに対して、リーフキーｇｙを割り当て、中間ノードおよびルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、ルートからリーフに至るパスを特定し、当該パス上に存在する中間ノードまたはリーフに割り当てられたリーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられたパラメータνｘ，ｙおよびノードパラメータγx,yに基づいて算出された鍵を受信する、受信部を備える受信装置が提供される。
【００２５】
上記の受信装置は、暗号化コンテンツを、セッション鍵ｓにより復号する復号部を更に備えるように構成してもよい。
【００２６】
上記の受信部は、排除する受信装置が特定された情報である、排除されていない受信装置の集合Ｓに関する情報を更に受信し、上記受信装置は、受信装置が集合Ｓに含まれているか否かを判定する判定部を更に備えるように構成してもよい。
【００２７】
上記判定部において、受信装置が集合Ｓに含まれていると判定された場合、上記復号部は、セッション鍵ｓを、以下の式Ｄに基づいて算出し、算出された当該セッション鍵ｓを用いることで、暗号化コンテンツを復号化してもよい。
【００２８】
【数４】
2008113201.tif 000006
【００２９】
上記課題を解決するために、本発明の第４の観点によれば、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、リーフとルートとの間に存在する中間ノードの下位に存在する複数のリーフからなるサブグループを構成する木構造構成ステップと、リーフおよび中間ノードそれぞれに対して、リーフキーｇｙを割り当てるリーフキー割当ステップと、中間ノードおよびルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当ステップと、ルートからリーフに至るパスを特定し、当該パス上に存在する中間ノードまたはリーフに割り当てられたリーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられたパラメータνｘ，ｙおよびノードパラメータγx,yに基づいて、鍵を算出する鍵算出ステップと、を備える鍵生成方法が提供される。
【００３０】
上記課題を解決するために、本発明の第５の観点によれば、ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する、排除受信装置特定ステップを備える暗号化方法が提供される。
【００３１】
上記課題を解決するために、本発明の第６の観点によれば、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、リーフとルートとの間に存在する中間ノードの下位に存在する複数のリーフからなるサブグループを構成し、リーフおよび中間ノードそれぞれに対して、リーフキーｇｙを割り当て、中間ノードおよびルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、ルートからリーフに至るパスを特定し、当該パス上に存在する中間ノードまたはリーフに割り当てられたリーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられたパラメータνｘ，ｙおよびノードパラメータγx,yに基づいて算出された鍵を受信するステップを備える鍵処理方法が提供される。
【００３２】
上記課題を解決するために、本発明の第７の観点によれば、コンピュータに、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、リーフとルートとの間に存在する中間ノードの下位に存在する複数のリーフからなるサブグループを構成する、木構造構成機能と、リーフおよび中間ノードそれぞれに対して、リーフキーｇｙを割り当てるリーフキー割当機能と、中間ノードおよびルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当機能と、ルートからリーフに至るパスを特定し、当該パス上に存在する中間ノードまたはリーフに割り当てられたリーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられたパラメータνｘ，ｙおよびノードパラメータγx,yに基づいて、鍵を算出する鍵算出機能と、を実現させるためのプログラムが提供される。
【００３３】
かかる構成によれば、コンピュータプログラムは、コンピュータが備える記憶部に格納され、コンピュータが備えるＣＰＵに読み込まれて実行されることにより、そのコンピュータを上記の鍵生成装置として機能させる。また、コンピュータプログラムが記録された、コンピュータで読み取り可能な記録媒体も提供することができる。記録媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、フラッシュメモリなどである。また、上記のコンピュータプログラムは、記録媒体を用いずに、例えばネットワークを介して配信してもよい。
【００３４】
上記課題を解決するために、本発明の第８の観点によれば、コンピュータに、ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する、排除受信装置特定機能を実現させるためのプログラムが提供される。
【００３５】
かかる構成によれば、コンピュータプログラムは、コンピュータが備える記憶部に格納され、コンピュータが備えるＣＰＵに読み込まれて実行されることにより、そのコンピュータを上記の暗号化装置として機能させる。また、コンピュータプログラムが記録された、コンピュータで読み取り可能な記録媒体も提供することができる。記録媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、フラッシュメモリなどである。また、上記のコンピュータプログラムは、記録媒体を用いずに、例えばネットワークを介して配信してもよい。
【００３６】
上記課題を解決するために、本発明の第９の観点によれば、コンピュータに、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、リーフとルートとの間に存在する中間ノードの下位に存在する複数のリーフからなるサブグループを構成し、リーフおよび中間ノードそれぞれに対して、リーフキーｇｙを割り当て、中間ノードおよびルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、ルートからリーフに至るパスを特定し、当該パス上に存在する中間ノードまたはリーフに割り当てられたリーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられたパラメータνｘ，ｙおよびノードパラメータγx,yに基づいて算出された暗号鍵を受信する受信機能を実現させるためのプログラムが提供される。
【００３７】
かかる構成によれば、コンピュータプログラムは、コンピュータが備える記憶部に格納され、コンピュータが備えるＣＰＵに読み込まれて実行されることにより、そのコンピュータを上記の受信装置として機能させる。また、コンピュータプログラムが記録された、コンピュータで読み取り可能な記録媒体も提供することができる。記録媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、フラッシュメモリなどである。また、上記のコンピュータプログラムは、記録媒体を用いずに、例えばネットワークを介して配信してもよい。
【発明の効果】
【００３８】
本発明によれば、排除される契約者数が少ない場合にも、ヘッダサイズを削減することが可能である。
【発明を実施するための最良の形態】
【００３９】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００４０】
（第１の実施形態）
以下に、本発明の第１の実施形態に係る暗号鍵配信システムについて、詳細に説明する。
【００４１】
図１は、本実施形態に係る暗号鍵配信システム１０を示した説明図である。暗号鍵配信システム１０は、例えば、通信網１２と、鍵生成装置２０と、暗号化装置３０と、受信装置４０Ａと、受信装置４０Ｂと、を含む。
【００４２】
通信網１２は、鍵生成装置２０、暗号化装置３０および受信装置４０を双方向通信又は一方向通信可能に接続する通信回線網である。この通信網は、例えば、インターネット、電話回線網、衛星通信網、同報通信路等の公衆回線網や、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＩＰ−ＶＰＮ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ−Ｖｉｒｔｕａｌ  Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ）、ワイヤレスＬＡＮ等の専用回線網などで構成されており、有線／無線を問わない。
【００４３】
鍵生成装置２０は、公開鍵と、複数の受信装置それぞれに固有の秘密鍵とを生成し、公開鍵を公開するとともに、各受信装置に対して、安全な通信路を介して、それぞれの秘密鍵を配信する。なお、この鍵生成装置２０は、公開鍵および秘密鍵の生成・管理を行うセンタが所有する。
【００４４】
暗号化装置３０は、鍵生成装置２０によって生成および公開された公開鍵を用いて、任意のコンテンツを暗号化し、通信網１２を介して、各受信装置に配信する。この暗号化装置３０は、任意の第三者が所有することが可能であり、また、鍵生成装置２０の所有者や、受信装置４０の所有者が所有することも可能である。
【００４５】
受信装置４０は、暗号化装置３０から配信された暗号化されたコンテンツを、固有の秘密鍵によって復号化して利用することが可能である。なお、受信装置４０Ａと受信装置４０Ｂとは、通信網１２または有線を介して互いに接続可能である。なお、この受信装置４０は、各契約者によって所有されるものである。
【００４６】
なお、図示の例では、受信装置４０として、パーソナルコンピュータ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ：ＰＣ）等のコンピュータ装置（ノート型、デスクトップ型を問わない。）を示しているが、かかる例に限定されず、ネットワークを介した通信機能を有する機器であれば、例えばＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、家庭用ゲーム機、ＤＶＤ／ＨＤＤレコーダ、テレビジョン受像器等の情報家電、テレビジョン放送用のチューナやデコーダなどで構成することもできる。また、受信装置４０は、契約者が持ち運びできるポータブルデバイス（Ｐｏｒｔａｂａｌｅ  Ｄｅｖｉｃｅ）、例えば、携帯型ゲーム機、携帯電話、携帯型映像／音声プレーヤ、ＰＤＡ、ＰＨＳなどであってもよい。
【００４７】
次に、本実施形態に係る鍵生成装置２０のハードウェア構成について、図２を参照しながら簡単に説明する。
【００４８】
図２は、鍵生成装置２０のハードウェア構成を示したブロック図である。鍵生成装置２０は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２０１と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）２０３と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２０５と、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）２０７と、暗号処理部２０９と、メモリ（セキュアモジュール）２１１とを備える。
【００４９】
ＣＰＵ２０１は、演算処理装置および制御装置として機能し、各種プログラムに従って鍵生成装置２０内の動作全般を制御する。ＲＯＭ２０３は、ＣＰＵ２０１が使用するプログラムや演算パラメータ等を記憶する。ＲＡＭ２０５は、ＣＰＵ２０１の実行において使用するプログラムや、このプログラムの実行において適宜変化するパラメータ等を、一次記憶する。
【００５０】
ＨＤＤ２０７は、本実施形態に係る鍵生成装置２０の記憶部の一例として構成されたデータ格納用の装置である。このＨＤＤ２０７は、ハードディスクを駆動し、ＣＰＵ２０１が実行するプログラムや各種データを格納する。暗号処理部２０９は、本実施形態に係る鍵生成装置２０がＣＰＵ２０１の制御のもとで実行する各種の暗号処理を実行する。メモリ（セキュアモジュール）２１１は、主に、個人秘密鍵や、センタ秘密である乱数等の秘匿が必要な情報を安全に格納するが、このメモリ２１１の内部に格納された情報は、外部から参照することができないという特徴がある。また、メモリ（セキュアモジュール）２１１は、例えば、耐タンパ性を有する記憶装置により構成されていてもよい。なお、セキュアモジュールはメモリである旨の記載をしているが、本発明に係るセキュアモジュールは、メモリに限定されるわけではなく、例えば、磁気ディスク、光ディスク、光磁気ディスクであってもよく、また、半導体メモリ等の記憶媒体であってもよい。
【００５１】
上記のＣＰＵ２０１、ＲＯＭ２０３、ＲＡＭ２０５、ＨＤＤ２０７、暗号処理部２０９、および、メモリ２１１は、ＣＰＵバス等から構成されるバス２１３により、相互に接続されている。
【００５２】
バス２１３は、ブリッジを介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの入出力インターフェース２１５に接続されている。
【００５３】
入力部２１７は、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチおよびレバー等のユーザが操作する操作手段と、使用者による操作に基づいて入力信号を生成し、ＣＰＵ２０１に出力する入力制御回路等から構成されている。鍵生成装置２０の使用者は、この入力部２１７を操作することにより、鍵生成装置２０に対して各種のデータを入力したり処理動作を指示したりすることができる。
【００５４】
出力部２１９は、例えば、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）ディスプレイ装置、液晶ディスプレイ（ＬＣＤ）装置およびランプ等の表示装置と、スピーカおよびヘッドホン等の音声出力装置等で構成される。出力部２１９は、例えば、再生されたコンテンツを出力することが可能である。具体的には、表示装置は、再生された映像データ等の各種情報を、テキストまたはイメージで表示する。一方、音声出力装置は、再生された音楽データ等を音声に変換して出力する。
【００５５】
通信部２２１は、例えば、通信網１２に接続するための通信デバイス等で構成された通信インターフェースである。この通信部２２１は、例えば暗号化装置３０や受信装置４０Ａ、４０Ｂとの間で、通信網１２を介して、暗号鍵に関する情報や、コンテンツ情報等といった、各種データを送受信する。
【００５６】
ドライブ２２３は、記憶媒体用リーダライタであり、鍵生成装置２０に内蔵、あるいは外付けされる。ドライブ２２３は、装着されている磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリ等のリムーバブル記録媒体１４に記録されている情報を読み出して、ＲＡＭ２０５に出力する。
【００５７】
なお、暗号化装置３０および受信装置４０のハードウェア構成は、鍵生成装置２０のハードウェア構成と実質的に同一であるので、説明を省略する。
【００５８】
以上、本実施形態に係る鍵生成装置２０、暗号化装置３０および受信装置４０の機能を実現可能なハードウェア構成の一例を示した。上記の各構成要素は、汎用的な部材を用いて構成されていてもよいし、各構成要素の機能に特化したハードウェアにより構成されていてもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用するハードウェア構成を変更することが可能である。また、上記のハードウェア構成は、あくまでも一例であり、これに限定されるものでないことは言うまでもない。例えば、ＨＤＤ２０７とメモリ（セキュアモジュール）２１１とを同一の記憶装置により構成してもよい。また、利用形態によっては、バス２１３、又は入出力インターフェース２１５等を省略する構成も可能である。以下、上記のようなハードウェア構成により実現される暗号鍵生成方式について詳述する。
【基盤技術に関する説明】
【００５９】
まず、本発明に係る好適な実施形態について詳細なる説明をするに先立ち、本実施形態を実現する上で基盤を成す技術的事項について述べる。なお、本実施形態は、以下に記載する基盤技術の上に改良を加えることにより、より顕著な効果を得ることができるように構成されたものである。従って、その改良に係る技術こそが本実施形態の特徴を成す部分である。つまり、本実施形態は、ここで述べる技術的事項の基礎概念を踏襲するが、その本質はむしろ改良部分に集約されており、その構成が明確に相違すると共に、その効果において基盤技術とは一線を画するものであることに注意されたい。
【００６０】
従来の公開鍵を利用したコンテンツ配信方式では、センタがコンテンツ配信システムのシステムパラメータｋを決定し、このシステムパラメータｋに基づくｋ次のセンタ秘密多項式を構成する。その後、このｋ次の秘密多項式を用いて、公開鍵ＰＫと、契約者ｉに固有の秘密鍵ｄｉ（以下、個人秘密鍵と表記する。）とを生成し、公開鍵ＰＫを公開するとともに、安全な通信路を用いて、契約者ｉに個人秘密鍵ｄｉを配布していた。また、コンテンツ配信時には、暗号文Ｃとヘッダｈとを配信するが、ヘッダｈは公開鍵ＰＫを利用して生成されるため、任意の配信者がヘッダｈを生成可能となる。この従来の公開鍵を利用したコンテンツ配信方式では、契約者ｉは個人秘密鍵ｄｉ一つのみを保持すればよく、また、公開鍵ＰＫを公開することによって、センタ以外の配信者がコンテンツを配信することが可能となる。
【００６１】
しかしながら、個人秘密鍵を生成するためにセキュリティパラメータであるｋに基づいたｋ次多項式を利用しており、ｋ＋１人以上の契約者が結託すると、システムの安全性が保持されなくなるという、結託問題が存在していた。
【００６２】
そこで、上記の非特許文献１では、任意数の契約者が結託してもシステムの安全性が保持されるという、公開鍵コンテンツ配信法を提案している。
【００６３】
Ｂｏｎｅｈ，Ｇｅｎｔｒｙ，Ｗａｔｅｒｓらによる非特許文献１に記載の方式は、個人秘密鍵の生成にｋ次多項式を利用せず、双線形群と呼ばれる巡回乗法群の一種を利用し、この群における契約者ｉに固有の要素を、個人秘密鍵ｄｉとして提供する。また、ヘッダｈの生成および各契約者によるセッション鍵ｓの取得に、双線形写像と呼ばれる演算を利用することによって、従来の公開鍵を利用したコンテンツ配信システムにおいて大きな問題となっていた結託問題を、解決している。
【００６４】
非特許文献１では、まず基本方式として、契約者集合を一つのグループとして取り扱う方式を示している。以下では、図３を参照しながら、この基本方式について説明する。この基本方式では、センタ５１が双線形群の生成元ｇと、センタ秘密であるαを生成し、これらを用いて契約者ｉ（ｉ＝１，・・・，ｎ）に、パラメータ
【数５】
2008113201.tif 000007
を割り当てる．
【００６５】
また、契約者５５の集合を一つのグループとして扱うためのパラメータν＝ｇγを生成し、これらの生成元ｇおよびパラメータνとを、公開鍵ＰＫ＝（ｇ，ｇ１，・・・，ｇｎ，ｇｎ＋２，・・・，ｇ２ｎ，ν）として公開する。さらに契約者ｉには、ｉに割り当てられたパラメータ
【数６】
2008113201.tif 000008
を用いて、個人秘密鍵
【数７】
2008113201.tif 000009
を、安全な一対一通信路５３を介して、予め提供しておく。
【００６６】
配信者は、公開鍵ＰＫ＝（ｇ，ｇ１，・・・，ｇｎ，ｇｎ＋２，・・・，ｇ２ｎ，ν）から、排除されていない全ての契約者に割り当てられたパラメータ
【数８】
2008113201.tif 000010
と、契約者を一つのグループにまとめるためのパラメータν＝ｇγとから、排除されていない全ての契約者に対応する共通のヘッダ要素を一つ作成し、このヘッダ要素と、セッション鍵生成時に利用される乱数要素と、を含んだヘッダ要素を用いて、ヘッダｈを生成し、暗号文Ｃと共に配信する。
【００６７】
このように、基本方式では、契約者集合を一つのグループとして取り扱い、そのグループに対応するヘッダ要素を構成することにより、ヘッダｈの大きさ（以下、ヘッダサイズと表記する。）を最小にしている。
【００６８】
しかしながら、全ての契約者を一つのグループとして取り扱うため、各契約者に各々異なるパラメータｇ１，・・・，ｇｎを割り当てる必要があるため、公開鍵サイズが、契約者数の二倍以上の大きさになる。また、各契約者がヘッダｈからセッション鍵ｓを取得する際には、自身を除く排除されていない全契約者に対応するパラメータｇ１，・・・，ｇｎの積を計算する必要があるため、契約者の総数であるｎの値が非常に大きな値となる場合には、契約者に対する計算量の負担が非常に大きくなる。現実的なコンテンツ配信においては、有料放送やＤＶＤ等の物理メディア、インターネット等を通じて、非常に多くの契約者に対してコンテンツを配信する必要があるため、以上のような問題点を考慮すると、基本方式は現実的に利用不可能であるといえる。
【００６９】
上記の問題点を解消する方法として、非特許文献１では、契約者集合を複数のサブグループに分割することにより公開鍵サイズを抑えることが可能となる、一般化方式を提案している。一般化方式では、契約者集合を複数のサブグループに分割し、分割された各サブグループに対して、基本方式同様の動作を行っている。従って、サブグループ毎に異なるヘッダ要素を生成する必要があり、ヘッダサイズは増大するが、公開鍵サイズを抑えることが可能となっている。また、各契約者は、分割されたサブグループに所属する各契約者に割り当てられたパラメータの積を計算する必要があるが、基本方式と比較して、契約者集合がサブグループに分割されているため、計算する必要があるパラメータ数を抑えることが可能となり、基本方式における問題点の解消している。
【００７０】
以下では、非特許文献１に記載の一般化方式について、図４〜図８を参照しながら、詳細に説明する。はじめに、上記の一般化方式を説明する上で必要となる記号の定義を示し、非特許文献１において利用される双線形群および双線形写像について説明する。続いて、これらの定義を利用して、非特許文献１に記載の一般化方式の詳細や問題点等について説明する。
【００７１】
＜記号の定義＞
非特許文献１に記載の一般化方式を説明する上で使用する各記号を、以下のように定義する。
【００７２】
ｎ  ：契約者の総数
Ａ  ：契約者グループを複数のサブグループに分割する際の分割数
Ｂ  ：分割されたサブグループに所属する契約者数
ＰＫ  ：システムの公開鍵
ｄｉ  ：ｉ番目の契約者の個人秘密鍵
ｒ  ：排除される契約者の総数
ｐ  ：双線形群の位数となる大きな素数
Ｇ，Ｇ１  ：位数ｐの双線形群
ｇ  ：Ｇの生成元
Ｍ  ：暗号化されていないコンテンツ（平文）
ｓ  ：セッション鍵
Ｃ  ：平文Ｍをセッション鍵ｓで暗号化したときの暗号文
Ｅｓ（Ｍ）  ：平文Ｍの鍵ｓによる暗号化
Ｄｓ（Ｃ）  ：暗号文Ｃの鍵ｓによる復号
ｅ（ｕ，ｖ）  ：双線形群Ｇ上の二つの元ｕ，ｖに対する双線形写像
【００７３】
＜双線形群における双線形写像＞
続いて、非特許文献１において用いられる双線形群上の双線形写像に関して説明する。双線形写像ｅ（ｕ，ｖ）とは、巡回乗法群Ｇの二つの要素ｕ，ｖを巡回乗法群Ｇ１の要素へと変換する写像であり、以下の性質を満たすものである。
【００７４】
１．双線形性：任意のｕ，ｖ∈Ｇ及びａ，ｂ∈Ｚに対して、ｅ（ｕａ，ｖｂ）＝ｅ（ｕ，ｖ）ａｂが成立する。
２．非退化性：ｅ（ｇ，ｇ）≠１
【００７５】
続いて、非特許文献１に記載の一般化方法について、各ステップを詳細に説明する。この一般化方法は、主に、鍵生成フェーズ、暗号化フェーズ、復号フェーズという三つのフェーズから構成される。鍵生成フェーズは、センタがシステム構成時に一度だけ実行し、暗号化フェーズは配信者、復号フェーズは契約者が、各々配信ごとに実行する。以下、各フェーズの説明を行う。
【００７６】
＜鍵生成フェーズ＞
以下では、図４および図５を参照しながら、鍵生成フェーズについて説明する。図４は、非特許文献１の一般化方式における鍵生成フェーズを説明するための説明図である。図５は、非特許文献１の一般化方式における鍵生成フェーズの流れ図である。
【００７７】
センタ５１は、以下の手順に従って、各契約者５５の個人秘密鍵と公開鍵とを生成する。
まず、センタ５１は、大きな素数ｐを無作為に選択し、選択されたｐを位数とする双線形群Ｇを決定する（ステップＳ１１）。
【００７８】
続いて、センタ５１は、上記ステップＳ１１で決定した双線形群Ｇの生成元であるｇと、センタ秘密である乱数α（αは整数である。）とを、それぞれ無作為に選択する（ステップＳ１３）。
【００７９】
次に、センタ５１は、分割されたサブグループに所属する契約者の数Ｂを決定し、分割数Ａを以下の計算により決定する。その後、契約者をＡ個のサブグループに分割する（ステップＳ１５）。
【００８０】
【数９】
2008113201.tif 000011
【００８１】
ここで、上式の右辺に示されている記号は、「（ｎ／Ｂ）以上の最小の整数」を表す記号である。
【００８２】
続いて、センタ５１は、ｉ（ｉ＝１，・・・Ｂ，Ｂ＋２，・・・，２Ｂ）に対して、リーフキーｇｉを以下のようにして算出する（ステップＳ１７）。
【００８３】
【数１０】
2008113201.tif 000012
【００８４】
次に、センタ５１は、サブグループ数Ａに対応するＡ個の乱数γ（γ１，・・・，γＡ、γは整数。）を無作為に選択する。続いて、双線形群Ｇに属するν１，・・・，νＡを、以下のようにして算出する（ステップＳ１９）。
【００８５】
【数１１】
2008113201.tif 000013
【００８６】
続いて、センタ５１は、上記のステップＳ１３で選択したｇと、ステップＳ１７で算出したｇｉと、ステップＳ１９で算出したνｉとに基づいて、以下で表される公開鍵ＰＫを決定し、公開する（ステップＳ２１）。
【００８７】
ＰＫ＝（ｇ，ｇ１，・・・，ｇＢ，ｇＢ＋２，・・・，ｇ２Ｂ，ν１，・・・，νＡ）
・・・（式４）
【００８８】
続いて、センタ５１は、契約者ｉが所属するサブグループＳａ（ａは、ｉ／Ｂ以上の最小の整数である。）と、このサブグループにおける契約者ｉのインデックスであるｂ＝ｉｍｏｄＢ（ここで、ｉは１以上Ｂ以下の整数である。）に対応するパラメータｇｂ、γａを選択して、以下の式で算出される契約者ｉの個人秘密鍵ｄｉを生成する（ステップＳ２３）。
【００８９】
【数１２】
2008113201.tif 000014
【００９０】
続いて、センタ５１は、上記のようにして生成した個人秘密鍵ｄｉを、安全な一対一通信路５３を介して、秘密裏にそれぞれの契約者ｉに配信する（ステップＳ２３）。
【００９１】
上記のように、非特許文献１における鍵生成フェーズでは、ステップＳ１５において、センタ５１がｎ人の契約者からなる契約者集合をＢ人ずつＡ個のサブグループに分割し、ステップＳ１１、ステップＳ１３、ステップＳ１７、ステップＳ１９において、コンテンツ配信システムを運営する上で必要となる各種パラメータを設定している。
【００９２】
また、ステップＳ２１では、生成したパラメータを利用して公開鍵ＰＫを生成し、続くステップＳ２３では、ステップＳ１５において決定したサブグループの分割数Ａと、一つのサブグループに所属する契約者数であるＢとに基づいて、各契約者の個人秘密鍵を生成している。
【００９３】
この際、各契約者は、自身に与えられた契約者固有の番号により、自身が所属するサブグループと、そのサブグループにおけるインデックスが決定される。上記で説明したように、個人秘密鍵の生成にｋ次多項式を利用していないため、任意数の契約者が結託したとしても、他契約者の個人秘密鍵偽造や、排除された契約者がヘッダからセッション鍵を取得可能となるような不正鍵を、構成することができなくなっている。
【００９４】
＜暗号化フェーズ＞
以下では、図６および図７を参照しながら、暗号化フェーズについて説明する。図６は、非特許文献１の一般化方式における暗号化フェーズを説明するための説明図である。図７は、非特許文献１の一般化方式における暗号化フェーズの流れ図である。
【００９５】
配信者５７は、以下の手順に従って配信するコンテンツを暗号化し、同報通信路５９を介して、非契約者６１および契約者６３に、暗号化したコンテンツをまとめて配信する。
まず、配信者５７は、整数ｔを無作為に選択し、セッション鍵ｓを以下のように計算する（ステップＳ３１）。
【００９６】
ｓ＝ｅ（ｇＢ＋１，ｇ）ｔ＝ｅ（ｇＢ，ｇ１）ｔ  ・・・（式６）
【００９７】
続いて、配信者５７は、コンテンツを復号可能な契約者の集合Ｓを決定し、ｌ＝１，・・・，Ａに対して、以下のように各サブグループを決定する（ステップＳ３３）。
【００９８】
【数１３】
2008113201.tif 000015
【００９９】
ここで、添字ｌはサブグループを表すパラメータであり、上記の式７で表される集合は、パラメータｌで表されるサブグループに含まれる契約者および非契約者の集合であり、上記の式８で表される集合は、パラメータｌで表されるサブグループ内において、契約者はサブグループ内の何番目の人なのかを表す集合である。
【０１００】
続いて、配信者５７は、契約者６３がセッション鍵ｓを算出するために必要なヘッダｈを、以下のように構成する（ステップＳ３５）。
【０１０１】
【数１４】
2008113201.tif 000016
【０１０２】
次に、配信者５７は、ステップＳ３１で算出したセッション鍵ｓに基づいて、式１０に示すように、送信するコンテンツを暗号化する。その後、暗号化したコンテンツＣを、ステップＳ３３で決定した集合Ｓに関する情報およびステップＳ３５で算出したヘッダｈとともに、同報通信路５９を介して、非契約者６１、契約者６３を問わず、送信する（ステップＳ３７）。
【０１０３】
Ｃ＝Ｅｓ（Ｍ）  ・・・（式１０）
【０１０４】
上述のように、配信時には、配信者５７は、暗号化フェーズのステップＳ３１においてセッション鍵を生成した後、ステップＳ３３において各サブグループに所属するコンテンツを復号可能な契約者の集合を決定する。その後、ステップＳ３５において、各サブグループに対応する要素を含んだヘッダｈを作成している。このとき、ヘッダｈの各要素は、その各サブグループにおいて復号可能な契約者に対応するパラメータｇｂのみによって構成されており、排除された契約者に対応するｇｂは含まれていない。これにより、後に述べる復号時において、非契約者の排除を実現している。
【０１０５】
＜復号フェーズ＞
以下では、図８を参照しながら、復号フェーズについて説明する。図８は、非特許文献１の一般化方式における復号フェーズの流れ図である。
【０１０６】
暗号化コンテンツ等の配信を受けた契約者ｉは、以下の手順に従って、暗号化コンテンツの復号処理を行う。
まず、契約者６３は、自身のインデックスであるｉが、配信者５７により配信された集合Ｓに含まれているかどうかを確認する（ステップＳ５１）。自身のインデックスｉが集合Ｓに含まれていないならば、自身は排除されたものとして、復号処理を終了する。自身のインデックスｉが集合Ｓに含まれている場合には、引き続き以下の処理を行う。
【０１０７】
次に、契約者６３は、送信されたヘッダｈのうち、自身が所属するサブグループＳａに対応するヘッダ要素を選択して、セッション鍵ｓを算出する（ステップＳ５３）。すなわち、ヘッダｈは、ｈ＝（Ｃ０，Ｃ１，・・・，ＣＡ）のように、それぞれのサブグループに対応するヘッダ要素によって構成されており、自身が所属するサブグループＳａに対応する要素Ｃ０、Ｃａを選択し、これらのヘッダ要素に基づき、以下の計算のようにセッション鍵ｓを取得する。
【０１０８】
【数１５】
2008113201.tif 000017
【０１０９】
上記の式１１−５と、式６とから明らかなように、契約者６３は、配信者５７から送信されたヘッダｈと公開鍵ＰＫ、および、契約者６３自身が保有している個人秘密鍵ｄｉを用いることによって、配信者５７が暗号化に利用したコンテンツ鍵ｓと同じものを、算出することが可能である。
【０１１０】
続いて、契約者６３は、上記のステップＳ５３で算出したセッション鍵ｓを用いて、配信された暗号化コンテンツＣを平文Ｍへと復号する（ステップＳ５５）。
【０１１１】
Ｍ＝Ｄｓ（Ｃ）  ・・・（式１２）
【０１１２】
上述のように、復号時には、契約者６３は、まずステップＳ５１において、自身が排除されているかどうかを確認する。排除されていた場合は、後述する理由によってセッション鍵ｓを取得することが不可能となるため、復号処理を終了する。ステップＳ５１での判定により、自身が排除されていないとわかった契約者は、ステップＳ５３において、配信されたヘッダのうち自身が所属するサブグループに対応するヘッダ要素を取り出して、このヘッダ要素と、自身の個人秘密鍵および公開鍵に基づいて、式１１−１から式１１−５に示した双線形写像による復号演算を行うことによって、セッション鍵ｓを取得する。そして、算出したセッション鍵ｓを用いて、暗号文の復号を行う。
【０１１３】
ここで、もし排除された契約者が式１１−１から式１１−５に示した双線形写像による復号演算を実行したとしても、ステップＳ５３中の式１１−２における
【数１６】
2008113201.tif 000018
の部分に、自身のｇｂに対応する値ｇＢ＋１−ｂが含まれていないため、非特許文献１において安全性の根拠となるＢＤＨＥＰ（Ｂｉｌｉｎｅａｒ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ｅｘｐｏｎｅｎｔｉａｌ  Ｐｒｏｂｌｅｍ）の困難性から、式１１−３への変形が不可能となり、正しいセッション鍵ｓを計算することが不可能となっている。
【０１１４】
このように、非特許文献１の方式は従来のｋ次多項式を利用する公開鍵コンテンツ配信法において問題となっていた、結託の問題を解決している。また、鍵生成フェーズのステップＳ１５においてセンタが契約者集合をＡ個のサブグループに予め分割しておくことにより、配信者が生成する必要のあるヘッダは、常にＡ＋１個の要素を持つように構成可能となる。したがって、排除される契約者数に関係なく、ヘッダサイズを一定に保つことが可能となっている。
【０１１５】
上記のように、非特許文献１の方式では、常に一定の大きさを持つヘッダを送信する必要がある。そのため、排除される契約者が存在しない、または少ない場合において、効率的なコンテンツ配信が不可能となるという問題点が存在する。実際のコンテンツ配信システムでは、契約者数が非常に大きな値となることが多いため、排除される契約者数は、契約者数全体に対して小さな値となることが多い。また、仮に排除される契約者数が大きくなってしまった場合には、コンテンツ配信システム自体が、崩壊してしまう可能性がある。従って、コンテンツ配信システムとしては、排除される契約者が存在しないか、全体に対して少数にとどまっている場合においては、効率良くコンテンツを配信することが要求される。
【０１１６】
しかしながら、上述したように、非特許文献１では、この条件を満たすことが困難となる。さらに非特許文献１では、復号化フェーズのステップＳ５３の式１１−１において、双線形写像による演算を行うために、以下の式１４で表される、自身の所属するサブグループ内に存在する排除されていない契約者に割り当てられたパラメータと、自身が保持する個人秘密鍵との積を、予め計算しておく必要がある。
【０１１７】
【数１７】
2008113201.tif 000019
【０１１８】
ここで、双線形写像による演算をＰＡＩＲ、双線形群Ｇ１上での逆元演算をＩＮＶ、双線形群Ｇ上での乗算をＭＵＬとし、契約者ｉが所属するサブグループＳａにおいて排除された契約者の数をｒａおくと、復号化フェーズにおいて契約者が実行する必要がある演算の計算量は、「２ＰＡＩＲ＋ＩＮＶ＋（Ｂ−１−ｒａ）ＭＵＬ」と表すことができる。
【０１１９】
これより、分割されたサブグループに所属する契約者数Ｂの値が大きい場合や、自身が所属するサブグループにおいて排除される契約者の数ｒａが小さい場合には、各契約者が復号時に必要とする計算量が増大するという問題点も存在することがわかる。
【０１２０】
このように、非特許文献１における一般化方式を利用したとしても、契約者集合の分割数を大きくすると、各契約者におけるコンテンツ復号時の計算量は抑えることが可能となるが、ヘッダサイズが増大する。また、逆に契約者集合の分割数を小さくすると、ヘッダサイズは抑えられるものの、計算量が増大するという問題点が存在する。また、排除される契約者数が少ない場合であっても、常に一定サイズのヘッダｈを配信する必要があるため、排除される契約者数がいない、もしくは全体に対して占める割合が少ない、というような現実的に最も起こりうるような状況において、ヘッダサイズを削減することができず、コンテンツ配信時におけるデータの冗長性が高くなるという問題点が存在する。
【０１２１】
そこで、本願発明者らは、上記の問題点を解決すべく鋭意研究を行い、以下に説明するような、本発明の一実施形態に係る暗号鍵配信システムを開発した。本実施形態に係る鍵生成装置では、非特許文献１の方式に若干のパラメータを加えて論理木を構成することにより、排除される契約者数が少ない場合においても、非特許文献１に記載の方式よりもヘッダサイズを削減することが可能となる。また、このような構成を取ることにより、契約者が復号時に実行する必要のある演算の計算量を、同等以下に削減することが可能となり、効率的なコンテンツ配信を実現することができる。
【本実施形態に係る説明】
【０１２２】
これまで説明したような基盤技術を踏まえながら、以下において、本実施形態に係る鍵生成装置、暗号化装置および受信装置について、詳細に説明する。本実施形態に係る鍵生成装置２０は、非特許文献１の方式を利用した論理木を構成し、この論理木を利用することによって、排除される契約者が存在しない、もしくは少ない場合において、非特許文献１の方式よりも効率的なコンテンツ配信を実現するものである。
【０１２３】
まず、本実施形態に係る鍵生成装置２０の構成について、図９を参照しながら説明する。図９は、本実施形態に係る鍵生成装置２０の構成を示したブロック図である。
【０１２４】
鍵生成装置２０は、例えば、木構造構成部２３１と、乱数決定部２３３と、リーフキー割当部２３５と、パラメータ割当部２３７と、鍵算出部２３９と、記憶部２４１と、配布部２５２と、を備える。
【０１２５】
木構造構成部２３１は、本実施形態に係る鍵生成装置の重要な要素である、論理木を構築する。すなわち、対象となるｎ個の受信装置をリーフに割り当て、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構築する。さらに、リーフとルートとの間に存在する中間ノードを、各々親ノードとする、Ｙ分木からなるサブグループを構成する。つまり、木構造構成部２３１により、１つのノードから下に向かって、常にＹ本の枝がでているＹ分木構造が、階層的に積み重ねられる。構築された階層化Ｙ分木構造の全体を見ると、最上位階層（以下、第０階層と称する。）にはルートが１つだけ存在し、このルートの下には、このルートを親ノードとするＹ個の子ノードが、第１階層として構築される。また、この第１階層に存在するＹ個の子ノードそれぞれを親ノードとして、第２階層には、さらにＹ２個の子ノードが存在する。このような構造が繰り返され、一番下の階層、すなわち、第（ｌｏｇＹｎ）階層には、全体としてｎ個のリーフが存在する。
【０１２６】
ここで、１つのノードから下向きに１本の枝が伸びており、この枝の先に１つのノードが存在する場合に、相対的に上側のノードのことを親ノードと呼び、相対的に下側のノードのことを子ノードと呼ぶこととする。この親ノード、子ノードという概念は相対的なものである。例えば、３つのノードが１本の枝で上下につながっている場合に、最上部のノードを親ノードとした場合には、中間に位置するノードは子ノードとなる。また、最下部のノードに着目した場合には、最下部のノードは、中間に位置するノードを親ノードとする子ノードとなる。
【０１２７】
また、階層化された木構造において、最上位階層に存在するルートと、最下位階層に存在するｎ個のリーフとの間に存在する各ノードを、中間ノードと呼ぶこととする。
【０１２８】
乱数決定部２３３は、本実施形態に係る鍵生成装置が用いる様々な乱数や、双線形群を決定する。すなわち、乱数決定部２３３は、素数ｐを無作為に選択して、この素数ｐを位数とする双線形群Ｇを決定するほかに、Ｇの生成元であるｇを無作為に選択したり、秘密の乱数である整数αを無作為に選択したりする。
【０１２９】
リーフキー割当部２３５は、木構造構成部２３１が構築した、階層化されたＹ分木構造において、末端のｎ個のリーフと、このリーフとルート以外の全ての中間ノードに対して、リーフキーｇｙを割り当てる。
【０１３０】
パラメータ割当部２３７は、木構造構成部２３１が構築した、階層化されたＹ分木構造において、末端のｎ個のリーフ以外の全てのノード、すなわち、最上位階層のルートと、ルートとリーフとの間に存在する全ての中間ノードに対して、任意のパラメータνｘ，ｙを割り当てる。ここで、ｘ、ｙはそれぞれノードの位置を表す添字であり、ｘは階層を示すものであり、ｙは階層ｘの何番目のノードに当たるかを示すものである。
【０１３１】
鍵算出部２３９は、乱数決定部２３３が決定した双線形群Ｇや乱数、リーフキー割当部２３５が割り当てたリーフキー、およびパラメータ割当部２３７が割り当てたパラメータ等に基づいて、公開鍵および個人秘密鍵を算出する。
【０１３２】
記憶部２４１は、例えば、木構造記憶部２４３、乱数記憶部２４５、リーフキー記憶部２４７、パラメータ記憶部２４９、および鍵記憶部２５１等を含む。これらの記憶部には、各処理部が行った処理の途中で必要となった変数や計算結果、または、処理の結果得られたもの記憶する。木構造構成部２３１、乱数決定部２３３、リーフキー割当部２３５、パラメータ割当部２３７および鍵算出部２３９等の各処理部は、この記憶部２４１に対して、自由にデータを書き込んだり、データを読み出したりすることが可能である。
【０１３３】
また、この記憶部２４１には、上記の記憶部２４３、２４５、２４７、２４９、２５１以外にも、様々なデータを記憶させておくことが可能である。なお、図９においては、記憶部２４１の中に様々な記憶部が個別に存在するように示しているが、様々な記憶部を個別に存在させず、全体として１つの記憶部に様々なデータを記憶させておいてもよい。また、記憶部２４１としては、セキュアモジュールを備えた記憶媒体を用いることも可能である。
【０１３４】
本実施形態に係る鍵生成装置における配布部２５２は、例えば、送信部２５３と、公開鍵公開部２５５とを備える。送信部２５３は、鍵算出部２３９が算出し、鍵記憶部２５１に記憶されている個人秘密鍵を、各受信装置へと送信する。また、公開鍵公開部２５５は、鍵算出部２３９が算出し、鍵記憶部２５１に記憶されている公開鍵を、各受信装置に公開する。
【０１３５】
続いて、本実施形態に係る暗号化装置３０の構成について、図１０を参照しながら説明する。図１０は、本実施形態に係る暗号化装置３０の構成を示したブロック図である。
【０１３６】
図１０に示したように、暗号化装置３０は、例えば、受信部３０１と、記憶部３０３と、排除受信装置特定部３０５と、セッション鍵決定部３０７と、コンテンツ記憶部３１３と、暗号化部３１５と、コンテンツ送信部３１７と、を備える。
【０１３７】
受信部３０１は、鍵生成装置２０により生成され、公開された公開鍵を受信する。また、受信部３０１は、公開鍵以外にも、鍵生成装置２０により生成された素数ｐや、排除する受信装置が特定された情報である、排除されていない受信装置の集合Ｓに関する情報を更に受信することができる。
【０１３８】
記憶部３０３は、例えば、鍵生成装置２０によって生成された公開鍵を記憶する。また、公開鍵以外にも、素数ｐや排除されていない受信装置の集合Ｓに関する情報等の情報を記憶することが可能である。
【０１３９】
排除受信装置特定部３０５は、暗号化装置３０に通信網１２を介して接続されている複数の受信装置４０の中から、コンテンツの配信を排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する。集合Ｓの決定に際しては、排除受信装置特定部３０５は、記憶部３０３に記憶されている様々なデータを参照することができる。
【０１４０】
セッション鍵決定部３０７は、配信しようとするコンテンツを暗号化するためのセッション鍵ｓを決定する。このセッション鍵決定部３０７は、例えば、ヘッダ要素算出部３０９とヘッダ情報生成部３１１とを更に備えてもよい。
【０１４１】
セッション鍵決定部３０７がセッション鍵ｓを算出する際には、整数ｔを無作為に選択し、公開されている公開鍵を利用して、双線形写像の演算を行う。
【０１４２】
ヘッダ要素算出部３０９は、鍵生成装置２０により構築された階層化された木構造において、排除された受信装置が割り当てられたリーフからルートに至るパス上に存在する全てのノードそれぞれにマークをし、マークされたノードに割り当てられたパラメータと、マークされたノードを親ノードとする中間ノードに割り当てられたリーフキーと、に基づいて、ヘッダ要素を算出する。
【０１４３】
ヘッダ情報生成部３１１は、ヘッダ要素算出部３０９において得られたヘッダ要素と、公開鍵とに基づいて、ヘッダ情報を生成する。
【０１４４】
コンテンツ記憶部３１３は、暗号化されていないコンテンツを記憶する。また、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）やメモリーカード等のメディア媒体から取得したコンテンツを記憶するとしてもよい。ここで、上記のコンテンツとは、例えば、映画、テレビジョン番組、ビデオプログラム、図表等の動画又は静止画からなる映像（Ｖｉｄｅｏ）コンテンツ、音楽、講演、ラジオ番組等の音声（Ａｕｄｉｏ）コンテンツや、ゲームコンテンツ、文書コンテンツ、ソフトウェアなど、任意のコンテンツデータであってもよい。映像コンテンツは、映像データのみならず、音声データを含んでいてもよい。
【０１４５】
暗号化部３１５は、コンテンツ記憶部３１３から配信するコンテンツを選び出し、セッション鍵決定部３０７で算出されたセッション鍵ｓを用いて、コンテンツを暗号化する。
【０１４６】
コンテンツ送信部３１７は、暗号化部３１５によって暗号化された暗号化コンテンツと、ヘッダ情報生成部３１１によって決定されたヘッダと、排除受信装置特定部３０５によって特定された集合Ｓとを、通信網１２を介して、各受信装置に送信する。
【０１４７】
続いて、本実施形態に係る受信装置４０の構成について、図１１を参照しながら説明する。図１１は、本実施形態に係る受信装置４０の構成を示したブロック図である。
【０１４８】
図１１に示したように、受信装置４０は、例えば、受信部４０１と、記憶部４０３と、判定部４０５と、復号部４０７と、を備える。
【０１４９】
受信部４０１は、鍵生成装置２０により生成された個人秘密鍵を受信する。また、受信部４０１は、個人秘密鍵以外にも、鍵生成装置２０により生成された公開鍵や、排除する受信装置が特定された情報である、排除されていない受信装置の集合Ｓに関する情報を更に受信することができる。また、暗号化装置３０によって暗号化されたコンテンツについても、受信することが可能である。
【０１５０】
記憶部４０３は、例えば、鍵生成装置２０によって生成された公開鍵や個人秘密鍵を記憶する。また、これらの暗号鍵以外にも、排除されていない受信装置の集合Ｓに関する情報や、配信された暗号化コンテンツや復号されたコンテンツ等のコンテンツ情報を記憶することが可能である。
【０１５１】
判定部４０５は、受信装置自身が、受信した集合Ｓの中に含まれているか否かを判定する。判定部４０５の判定結果に伴い、復号部４０７は、暗号化コンテンツの復号処理を行う。
【０１５２】
復号部４０７は、受信部４０１が受信したヘッダｈと、記憶部４０３が記憶している公開鍵および個人秘密鍵とを用いて、暗号化コンテンツの復号に必要なセッション鍵ｓを、算出する。セッション鍵ｓを算出した後に、復号部４０７は引き続き、暗号化コンテンツの復号化を行う。
【０１５３】
以上、本実施形態に係る鍵生成装置２０、暗号化装置３０および受信装置４０の機能の一例を示した。上記の各構成要素は、汎用的な部材や回路を用いて構成されていてもよいし、各構成要素の機能に特化したハードウェアにより構成されていてもよい。また、各構成要素の機能を、ＣＰＵ等が全て行ってもよい。従って、本実施形態を実施する時々の技術レベルに応じて、適宜、利用する構成を変更することが可能である。
【０１５４】
本実施形態に係る暗号鍵配信システム１０は、非特許文献１同様、鍵生成、暗号化、および復号という、三つのフェーズから構成される。鍵生成フェーズは、センタがシステム構成時に一度だけ実行する。また、暗号化フェーズは配信者が、復号フェーズは契約者が、各々配信ごとに実行する。なお、本実施形態に係る暗号鍵配信システム１０を説明する上で使用する各記号及び演算は、基盤技術の説明の際に定義したものと同一のものとする。以下、初めに本実施形態において構成する論理木に関して定義及び説明を行い、その後、各フェーズについて、詳細に説明する。
【０１５５】
＜論理木の構成と定義＞
本実施形態に係る鍵生成装置２０を説明する上で必要となる論理木に関して、まず説明および定義を行う。本実施形態に係る鍵生成装置２０では、各契約者をリーフに割り当て、かつ非特許文献１における契約者の分割をこの論理木に割り当てることによって、効率的なコンテンツ配信を実現している。この論理木は、本実施形態に係る鍵生成装置２０における、木構造構成部２３１によって構成される。
【０１５６】
なお、簡単のため、本実施形態では、Ｙ分木を利用するものとする。また、全契約者をリーフに割り当てる必要があるため、契約者の総数ｎが、Ｙのべき乗で表される値であると仮定する。ただし、実際のコンテンツ配信においては、ｎがＹのべき乗とならない場合も多々存在する。しかし、この場合には、ｎよりも十分に大きいＹのべき乗数のリーフを予め用意しておくことによって、容易に対応することが可能である。以下に、論理木の構成について、各定義を示す。
【０１５７】
本実施形態において利用するＹ分木は、リーフの個数がｎであるので、ルートを除くＹ分木の高さをＨとすると、Ｈ＝ｌｏｇＹｎとなる。また、リーフを除くノードの総数をＮとすると、Ｎ＝（ｎ−１）／（Ｙ−１）となる。よって、Ｙ分木にはルート以外にＨ個の階層が存在し、ここでは、この階層をＬａｙｅｒと定義する。すなわち、ルートの子ノードの集合をＬａｙｅｒ１とし、Ｌａｙｅｒ１の全ノードの子ノード（すなわち、ルートの孫ノード）の集合をＬａｙｅｒ２、という形で、Ｙ分木の各階層を、Ｌａｙｅｒ  ｘ（ｘ＝０，・・・，Ｈ）と定義する。ここで、ｘは、階層を表す添字である。また、Ｌａｙｅｒ  ｘに含まれる各ノードのインデックスを、ノードインデックスと呼ぶこととし、（ｘ，ｙ）、（ｙ＝１，・・・，Ｙｘ）と定義する。このとき、ルートは、Ｌａｙｅｒ０のノードであり、そのインデックスは（０，１）となる。
【０１５８】
上記のように定義したＹ分木の例として、図１２に契約者数ｎ＝９、分岐数Ｙ＝３とした場合を示す。
【０１５９】
契約者数ｎが９であるため、ルートを除く３分木の高さＨは、ｌｏｇ３９＝２となる。従って、この３分木には、ルートを含めて３つの階層が存在する。すなわち、ルートを含む階層５０１がＬａｙｅｒ０となり、ルートの子ノードである３つのノードを含む階層５０３が、Ｌａｙｅｒ１となる。Ｌａｙｅｒ１に存在する３つのノードをそれぞれ親ノードとした場合の子ノードの階層５０５が、Ｌａｙｅｒ２となる。Ｌａｙｅｒ２には、Ｌａｙｅｒ１に存在する３つのノードそれぞれから、３つの子ノードが形成されるために、全部で９個のリーフが存在することとなる。
【０１６０】
また、リーフを除くノードの数Ｎ、すなわち、ルートと中間ノードの数の和は、（９−１）／（３−１）＝４となる。
【０１６１】
リーフを含めたそれぞれのノードに割り当てられるノードインデックスは、例えば、ルートは（０，１）となり、Ｌａｙｅｒ１の３つのノードは、それぞれ左端から（１，１）、（１，２）、（１，３）となる。また、Ｌａｙｅｒ２の９個のノード、すなわちリーフには、左端からそれぞれ（２，１）、（２，２），・・・，（２，９）というノードインデックスが付される。
【０１６２】
また、本実施形態に係る鍵生成装置２０では、このリーフそれぞれに受信装置４０、すなわち、コンテンツ配信に関する契約者５０７を割り当てる。つまり、Ｌａｙｅｒ２のリーフ（２，１）、（２，２）、・・・、（２，９）には、それぞれ、契約者１（５０７Ａ）、契約者２（５０７Ｂ）、・・・、契約者９（５０７Ｉ）が割り当てられる。
【０１６３】
続いて、前述の論理木に関する定義を利用し、以下に、本実施形態に係る暗号鍵配信システムの具体的な説明を示す。
【０１６４】
＜鍵生成装置２０の動作：暗号鍵生成フェーズ＞
センタは、所有する鍵生成装置２０を操作し、以下の手順に従って、公開鍵と各契約者の個人秘密鍵とを生成する。以下に、図１２、図１３および図１４を参照しながら、本実施形態に係る鍵生成装置２０の動作について、詳細に説明する。図１３は、鍵生成装置２０による鍵生成の概要を説明するための説明図である。図１４は、鍵生成装置２０による暗号鍵生成フェーズの流れ図である。
【０１６５】
まず、鍵生成装置２０の乱数決定部２３３は、値の大きな素数ｐを無作為に選択し、選択したｐを位数とする双線形群Ｇを決定する（ステップＳ１０１）。ここで、値の大きな素数ｐとは、桁数の多い素数を意味する。乱数決定部２３３は、容易に離散対数問題が解けないような桁数の多い素数を選択することで、本実施形態に係る暗号鍵の安全性を担保する。
【０１６６】
続いて、乱数決定部２３３は、双線形群Ｇの生成元であるｇと、センタ秘密である乱数α（αは整数）を、無作為に選択する（ステップＳ１０３）。
【０１６７】
これらの素数ｐ、双線形群Ｇ、生成元ｇおよび乱数αに関するデータは、例えば、記憶部２４１中の乱数記憶部２４５の中に記憶され、リーフキー割当部２３５、パラメータ割当部２３７、または暗号鍵算出部２３９等によって参照される。
【０１６８】
続いて、鍵生成装置２０の木構造構成部２３１は、分割されたサブグループに所属する契約者数Ｙを決定し、分割数Ｘを以下の計算により決定した後、契約者をＸ個のサブグループに分割する。さらに、各契約者をリーフとして割り当てたＹ分木を構成する（ステップＳ１０５）。ここで、以下の式１０１中のｎは、契約者の総数である。
【０１６９】
【数１８】
2008113201.tif 000020
【０１７０】
例えば、図１２に示したように、契約者の総数ｎが９人であり、Ｙ＝３、つまり３分木を構築する場合には、分割数Ｘは、式１０１より３となる。
【０１７１】
以上のようにして構築されたＹ分木構造を、木構造構成部２３１は、記憶部２４１中の木構造記憶部２４３に記憶させる。
【０１７２】
次に、鍵生成装置２０のリーフキー割当部２３５は、ｉ（ｉ＝１，・・・，Ｙ，Ｙ＋２，・・・，２Ｙ）に対して、リーフキーｇｉを、以下のようにして算出する（ステップＳ１０７）。
【０１７３】
【数１９】
2008113201.tif 000021
【０１７４】
上記の式１０２から明らかなように、リーフキーｇｉの算出にあたっては、乱数決定部２３３が決定した生成元ｇ、および、センタ秘密である乱数αを用いる。そのため、リーフキー割当部２３５は、記憶部２４１中の乱数記憶部２４５にアクセスして、これらのデータを読み出す。リーフキーを算出した後は、リーフキー割当部２３５は、算出したリーフキーｇｉを、記憶部２４１中のリーフキー記憶部２４７に保存する。
【０１７５】
なお、ステップＳ１０７においては、リーフキーｇｉを、サブグループに所属する契約者の数であるＹ個だけでなく、ｉをＹ＋１を除く２Ｙまで変化させて、リーフキーｇｉを算出している。ｇＹ＋１を算出しない理由は、本実施形態に係る暗号鍵配信システム１０の安全性を担保するためであり、ｇＹ＋２からｇ２Ｙまでのリーフキーｇｉは、後に述べる復号フェーズで復号を行う際に必要となるからである。
【０１７６】
続いて、暗号鍵作成装置２０のパラメータ割当部２３７は、リーフを除く全ノード（ｘ，ｙ）に対応する乱数γｘ，ｙ（γｘ，ｙは整数）を無作為に選択する。続いて、パラメータνｘ，ｙを以下のように算出し、Ｙ分木のリーフを除く各ノードに、それぞれ割り当てる（ステップＳ１０９）。ここで、ｘ＝０，・・・，Ｈ−１（Ｈは、Ｙ分木構造の高さである。）であり、ｙ＝１，・・・，Ｙｘである。
【０１７７】
【数２０】
2008113201.tif 000022
【０１７８】
例えば、図１２のように、９人の契約者に対して３分木構造を構築した場合には、３分木構造の高さＨは２であるため、ｘは０または１となる。また、ｙは、１，２，３となる。つまり、図１２の場合は、パラメータ割当部２３７によって割り当てられるパラメータνｘ，ｙは、ν０，１、ν１，１、ν１，２、ν１，３の計４個となる。したがって、γｘ，ｙについても、４つの整数が無作為に選択されることとなる。このようにして決定された値に基づき、式１０３によって、各ノードにパラメータが割り当てられる。
【０１７９】
また、パラメータ割当部２３７によって算出されたパラメータνｘ，ｙやノードパラメータγｘ，ｙ等は、記憶部２４１中のパラメータ記憶部２４９に記憶される。
【０１８０】
続いて、リーフキー割当部２３５は、ルートを除く全ノードに対して、ｇｘ，ｙを割り当てる（ステップＳ１１１）。ここで、ｙ＝１，・・・，Ｙｘであり、ｇｘ，ｙは、ｇ１，・・・，ｇＹからなる集合｛ｇ１，・・・，ｇＹ｝の元である。以上のように、リーフキー割当部２３５は、リーフキーｇｙを算出する機能と、算出したリーフキーを、ルートを除く全ノードに割り当てる機能の双方を有する。割り当てた結果は、記憶部２４１中のリーフキー記憶部２４７に、木構造に関連付けられて記憶される。
【０１８１】
例として、図１２に示した場合を考える。この場合、Ｌａｙｅｒ１（５０３）には、ルートを親ノードとする３つの子ノードが存在し、１つのサブグループを構成している。したがって、ノード（１，１）には、ｇ１，１としてｇ１が、ノード（１，２）には、ｇ１，２としてｇ２が、ノード（１，３）には、ｇ１，３としてｇ３が割り当てられる。
【０１８２】
また、Ｌａｙｅｒ２（５０５）を考えると、このノード（１，１）を親ノードとする３つの子ノード（２，１）、（２，２）、（２，３）からなるサブグループと、ノード（１，２）を親ノードとする３つの子ノード（２，４）、（２，５）、（２，６）からなるサブグループと、ノード（１，３）を親ノードとする３つの子ノード（２，７）、（２，８）、（２，９）からなるサブグループの、計３つのサブグループが存在している。この場合、ノード（２，１）には、ｇ２，１としてｇ１が、ノード（２，２）には、ｇ２，２としてｇ２が、ノード（２，３）には、ｇ２，３としてｇ３が割り当てられる。同様にして、ノード（２，４）には、ｇ２，４としてｇ１が、ノード（２，５）には、ｇ２，５としてｇ２が、ノード（２，６）には、ｇ２，６としてｇ３が割り当てられ、ノード（２，７）には、ｇ２，７としてｇ１が、ノード（２，８）には、ｇ２，８としてｇ２が、ノード（２，９）には、ｇ２，９としてｇ３が割り当てられる。
【０１８３】
続いて、鍵生成装置２０の鍵算出部２３９は、公開鍵ＰＫを以下のように構成して、公開鍵公開部２５５を介して公開する（ステップＳ１１３）。
【０１８４】
ＰＫ＝（ｇ，ｇ１，・・，ｇＹ，ｇＹ＋２，・・，ｇ２Ｙ，ν０，１，・・，νＨ−１，Ｘ）
・・・（式１０４）
【０１８５】
上記の式１０４から明らかなように、公開鍵ＰＫは、乱数決定部２３３が決定した生成元ｇと、リーフキー割当部２３５が算出したリーフキーｇｉと、パラメータ割当部２３７が算出したパラメータνｘ，ｙから構成されている。したがって、鍵算出部２３９は、記憶部２４１中の各記憶部２４５、２４７、２４９を参照して、公開鍵ＰＫを構成する。鍵算出部２３９は、構成した公開鍵ＰＫを、記憶部２４１中の鍵記憶部２５１に記憶する。公開鍵公開部２５５は、この鍵記憶部２５１を参照して、公開鍵を公開する。なお、鍵算出部２３９は、構成した公開鍵ＰＫを、直接公開鍵公開部２５５へと送信してもよい。
【０１８６】
例として、図１２に示した場合を考える。この場合、公開鍵ＰＫとして公開されるものは、（ｇ，ｇ１，ｇ２，ｇ３，ｇ５，ｇ６，ν０，１，ν１，１，ν１，２，ν１，３）となる。
【０１８７】
続いて、鍵算出部２３９は、契約者ｉ（ｉ＝１，・・・，ｎ）に対して、ルートから契約者ｉに割り当てられたリーフに至るパスを特定し、そのパス上にあるＬａｙｅｒ  ｘ上のノードに対する契約者ｉのインデックスをｉｘとする。すなわち、ｉ０＝（０，１）であり、ｉＨ＝（Ｈ，ｉ）である。センタは、契約者ｉに割り当てられたルートを除く全ノードｉ１，・・・，ｉＨに対して、これらのノードに割り当てられたパラメータｇｉｘを特定する。また、リーフを除く全ノードｉ０，・・・，ｉＨ−１に割当てられたパラメータγｉｘを特定し、以下のようにして契約者ｉの個人秘密鍵ｄｉを計算する。その後、送信部２５３は、個人秘密鍵ｄｉを、安全な通信路を用いて契約者ｉに配布する（ステップＳ１１５）。
【０１８８】
【数２１】
2008113201.tif 000023
【０１８９】
式１０５から明らかなように、個人秘密鍵ｄｉの各要素は、特定したパス上にあるノードｉｘに割り当てられたリーフキーｇｉｘと、ノードｉｘの親ノードとなるノードに割り当てられたパラメータγｉｘ−１と、に基づいて計算される。すなわち、それぞれの個人秘密鍵ｄｉは、各ノードに割り当てられたリーフキーに基づいて算出された鍵のセットであるといえる。なお、上記のステップＳ１１５の具体例については、以下で、図１５を参照しながら詳細に説明する。
【０１９０】
なお、鍵算出部２３９において、各契約者固有の個人秘密鍵ｄｉが算出されると、鍵算出部２３９は、これらの個人秘密鍵を、記憶部２４１中の鍵記憶部２５１に記憶する。送信部２５３が、各契約者に対して個人秘密鍵ｄｉを送信する場合には、送信部２５３は、記憶部２４１中の鍵記憶部２５１を参照して、必要な情報を取得する。また、鍵算出部２３９が、生成した個人秘密鍵を、直接送信部２５３へと受け渡すようにしてもよい。
【０１９１】
続いて、図１５を参照しながら、上記のステップＳ１１５の具体例を例示する。図１５では、９人の契約者に対して、３分木構造が構築されている。ここで、リーフ（２，３）に割り当てられている契約者３に、個人秘密鍵ｄ３を送信する場合を考える。
【０１９２】
ルート（０，１）から、契約者３であるリーフ（２，３）へと至るパスは、ルート（０，１）から、中間ノード（１，１）を経由して、リーフ（２，３）へと至るパスとなる。この場合、ルート（０，１）以外のパス上のノードである（１，１）と（２，３）が、それぞれｉ１とｉ２となる。ここで、ノード（０，１）、（１，１）、（２，３）にそれぞれ割り当てられているパラメータを考える。ノード（０，１）には、γｉ０として、γ０，１が割り当てられている。ノード（１，１）には、γｉ１としてγ１，１が割り当てられ、ｇｉ１として、ｇ１，１であるｇ１が割り当てられている。また、リーフ（２，３）には、ｇｉ２としてｇ２，３であるｇ３が割り当てられている。
【０１９３】
契約者３が保持することとなる個人秘密鍵ｄ３は、式１０５より、ノード（１，１）に割り当てられたリーフキーｇ１をノード（１，１）の親ノードであるルート（０，１）に割り当てられたγ０，１でべき乗したものと、リーフ（２，３）に割り当てられたリーフキーｇ３をリーフ（２，３）の親ノードであるノード（１，１）に割り当てられたγ１，１でべき乗したもののセットとなる。
【０１９４】
以上説明したように、本実施形態に係る鍵生成装置２０は、図１３に示したように、センタ５０９が所有する鍵生成装置２０が、双線形群Ｇや、各種のパラメータを選択し、公開鍵ＰＫと、契約者固有の個人秘密鍵ｄｉを生成する。そして、センタ５０９は、公開鍵ＰＫを公開するとともに、各契約者５０７に対して、安全な一対一通信路５１１を用いて、個人秘密鍵ｄｉを配布する。
【０１９５】
＜暗号化装置３０の動作：暗号化フェーズ＞
続いて、図１６および１７を参照しながら、本実施形態に係る暗号化装置３０の動作、すなわち暗号化フェーズを、詳細に説明する。図１６は、暗号化装置３０による暗号化の概要を説明するための説明図である。図１７は、暗号化装置３０による暗号化フェーズの流れ図である。なお、以下に説明する暗号化フェーズは、暗号化装置３０を所有する任意の第三者が行うことも可能である。また、鍵生成装置２０の所有者や受信装置４０の所有者であっても、暗号化装置３０の所有者であれば、以下の暗号化フェーズを行うことが可能である。
【０１９６】
以下に説明する暗号化フェーズを実行するに先立ち、暗号化装置３０の受信部３０１は、鍵生成装置２０によって生成および公開された公開鍵と、素数ｐと、木構造に関する情報と、排除されていない受信装置の集合Ｓに関する情報と、をそれぞれ受信する。受信部３０１が取得したこれらの情報は、記憶部３０３に記憶される。記憶部３０３に記憶されたこれらの情報は、暗号化装置３０の各処理部が、自由に読み出すことができる。
【０１９７】
まず、排除受信装置特定部３０５は、排除したい全ての契約者に割り当てられたリーフからルートに至るパス上にある全てのノードをマークし、排除されていない契約者が、ヘッダｈから自身に割り当てられたヘッダ要素を特定するためのノードインデックスの集合Ｓを、Ｓ＝φ（φは空集合を表す。）として初期化する（ステップＳ３０１）。
【０１９８】
続いて、セッション鍵決定部３０７は、任意の整数ｔを無作為に選択して、セッション鍵ｓを以下のように算出する（ステップＳ３０３）。
【０１９９】
ｓ＝ｅ（ｇＹ＋１，ｇ）ｔ＝ｅ（ｇＹ，ｇ１）ｔ  ・・・（式１０６）
【０２００】
続いて、ヘッダ要素算出部３０９は、階層を表すパラメータであるｘを−１と設定する（ステップＳ３０５）。すなわち、このステップＳ３０５は、階層を表すパラメータｘの初期化ステップである。
【０２０１】
続いて、ヘッダ要素算出部３０９は、ｘにｘ＋１を代入して、ｘの値を１つ増加させる（ステップＳ３０７）。
【０２０２】
次に、ヘッダ要素算出部３０９は、ｙをゼロとして、パラメータの初期化をはかる（ステップＳ３０９）。
【０２０３】
続いて、ヘッダ要素算出部３０９は、各ｌａｙｅｒにおけるノードの位置を表すパラメータであるｙに、ｙ＋１を代入して、ｙの値を１つ増加させる（ステップＳ３１１）。
【０２０４】
次に、ヘッダ要素算出部３０９は、ノード（ｘ，ｙ）に対応するヘッダ要素ｃｘ，ｙを、ｃｘ，ｙ＝０として、初期化する（ステップＳ３１３）。
【０２０５】
以下に示すステップより、ヘッダ要素算出部３０９は、ヘッダ要素を算出するための具体的な処理を行うこととなる。
【０２０６】
続いて、ヘッダ要素算出部３０９は、ノード（ｘ，ｙ）の子ノードが、全てマークされているか否かを判定する（ステップＳ３１５）。判定の結果、全ての子ノードがマークされている場合には、以下に示すステップＳ３２１へと進む。また、マークされていない子ノードが存在する場合には、以下のステップＳ３１７へと進む。
【０２０７】
次に、ヘッダ要素算出部３０９は、マークされていない子ノードの集合をＳｘ，ｙとし、Ｓｘ，ｙの各要素をルートとする部分木（サブグループ）に所属する契約者に対応するヘッダ要素を、以下のように算出する（ステップＳ３１７）。
【０２０８】
【数２２】
2008113201.tif 000024
【０２０９】
また、ヘッダ要素算出部３０９は、集合Ｓを以下のように設定する（ステップＳ３１７）。
【０２１０】
【数２３】
2008113201.tif 000025
【０２１１】
次に、ヘッダ要素算出部３０９は、Ｓｘ，ｙの各要素をルートとする部分木に対して、その部分木に所属する全ノード（リーフを含む。）をマークする（ステップＳ３１９）。
【０２１２】
続いて、ヘッダ要素算出部３０９は、現在着目しているパラメータｙが、Ｙｘに該当するか否かを判定する（ステップＳ３２１）。判定の結果、ｙがＹｘである場合には、以下に示すステップＳ３２３へと移行する。また、ｙがＹｘではない場合には、ステップＳ３１１へと戻って、パラメータｙを１増加させる。
【０２１３】
次に、ヘッダ要素算出部３０９は、現在着目しているパラメータｘが、Ｈ−１であるか否かを判定する（ステップＳ３２３）。判定の結果、ｘがＨ−１であれば、以下のステップＳ３２５へと移行する。また、ｘがＨ−１でない場合には、ステップＳ３０７へと戻って、パラメータｘを１増加させる。
【０２１４】
上記のように、ステップＳ３２１およびステップＳ３２３の条件を共に満足するまで、ステップＳ３０７〜ステップＳ３２３を繰り返すことで、ヘッダ要素算出部３０９は、ヘッダ生成に必要な全てのヘッダ要素を算出することが可能である。
【０２１５】
すなわち、具体的なヘッダ要素の算出に先立ち、ステップＳ３１３において、着目しているノード（ｘ，ｙ）に対応するヘッダ要素ｃｘ，ｙをゼロに初期化しているため、ステップＳ３１５において、着目しているノード（ｘ，ｙ）の子ノードが全てマークされている場合には、ノード（ｘ，ｙ）のヘッダ要素ｃｘ，ｙはゼロのままで記憶される。一方、着目しているノード（ｘ，ｙ）の子ノードが全てマークされていない場合には、ステップＳ３１７において、ｃｘ，ｙに新たな値が代入されるため、ｃｘ，ｙはゼロではない値を有することとなる。
【０２１６】
上記のステップを繰り返すことで得られたヘッダ要素の全てを、ヘッダ要素算出部３０９は、ヘッダ情報生成部３１１へと受け渡す。また、ヘッダ要素算出部３０９は、算出したヘッダ要素を、記憶部３０３に記憶してもよい。
【０２１７】
続いて、ヘッダ情報生成部３１１は、生成元ｇと、ステップＳ３０３で選択したｔと、を用いて、ｇｔを計算する。また、ヘッダ要素ｃｘ，ｙがゼロではないヘッダ要素のみを利用して、ヘッダｈを以下のように構成する（ステップＳ３２５）。
【０２１８】
ｈ＝（ｇｔ，ｃ０，１，・・・，ｃＨ−１，Ｘ）  （ｃｘ，ｙ≠０）  ・・・（式１０９）
【０２１９】
ヘッダ情報生成部３１１は、ヘッダ情報を生成すると、生成したヘッダｈを暗号化部３１５へと受け渡す。また、ヘッダ情報生成部３１１は、生成したヘッダｈを、記憶部３０３に記憶してもよい。
【０２２０】
続いて、暗号化部３１５は、暗号化されていない配信予定のコンテンツＭをコンテンツ記憶部３１３から受け取り、セッション鍵決定部３０７が決定したセッション鍵ｓを用いて、以下のように、コンテンツＭを暗号化する。その後、コンテンツ送信部３１７は、暗号化したコンテンツＣを、ヘッダ情報生成部３１１が生成したヘッダｈおよびノードインデックスの集合Ｓと共に、契約者へと送信する（ステップＳ３２７）。
【０２２１】
Ｃ＝Ｅｓ（Ｍ）  ・・・（式１１０）
【０２２２】
続いて、図１８〜図２０を参照しながら、本実施形態に係る暗号化フェーズについて、具体的に説明する。図１８〜図２０は、本実施形態に係る暗号化フェーズについて、具体的に説明するための説明図である。図１８〜図２０では、３分木構造が構築され、リーフに９人の契約者が割り当てられている場合である。
【０２２３】
以下の例では、排除したい契約者が契約者２および契約者３である場合を説明する。図１８に示したように、契約者２にはリーフ（２，２）が割り当てられ、契約者３にはリーフ（２，３）が割り当てられている。この場合、排除したい契約者である契約者２からルートへ至るパスは、リーフ（２，２）からノード（１，１）を経由してルート（０，１）へと至る、図１８において点線で示したパスである。同様に、排除したい契約者である契約者３からルートへ至るパスは、リーフ（２，３）からノード（１，１）を経由してルート（０，１）へと至る、図１８において点線で示したパスである。この場合、排除受信装置特定部２６１は、ルート（０，１）、ノード（１，１）、リーフ（２，２）、および、リーフ（２，３）にマークを付すこととなる。なお、図１８では、マークが付されたノードを、点線で囲んで示している。その後、セッション鍵決定部３０７により、ステップＳ３０３が実行され、セッション鍵ｓが決定される。
【０２２４】
続いて、ヘッダ要素算出部３０９により、ステップＳ３０５〜ステップＳ３１１が実行される。その結果、パラメータｘには０が代入され、パラメータｙには１が代入される。続いて、ヘッダ要素算出部３０９は、ステップＳ３１３を実行する。この場合、ノード（０，１）に対するヘッダ要素ｃ０，１がゼロに初期化される。続いて、ヘッダ要素算出部３０９は、ステップＳ３１５を実行し、ルート（０，１）の子ノードが全てマークされているかを判定する。図１９から明らかなように、ルート（０，１）の子ノードは（１，１）、（１，２）、（１，３）の３つであるが、ノード（１，２）および（１，３）には、マークが付されていない。したがって、ヘッダ要素算出部３０９は、ステップＳ３１７を実行することとなる。
【０２２５】
図１９の場合、マークされていない子ノードの集合Ｓ０，１は、｛（１，２），（１，３）｝となる。また、ノード（１，２）にはｇ２が、ノード（１，３）にはｇ３がそれぞれ割り当てられているため、ヘッダ要素ｃ０，１を算出すると、（ν０，１・ｇ２・ｇ１）ｔとなる。
【０２２６】
続いて、ヘッダ要素算出部３０９は、ステップＳ３１９を実行する。ステップＳ３１９により、Ｓ０，１の要素であるノード（１，２）をルートとする部分木の全ノードである、ノード（１，２）、リーフ（２，４）、リーフ（２，５）、リーフ（２，６）にマークが付されることとなる。Ｓ０，１のもうひとつの要素であるノード（１，３）についても同様に、ノード（１，３）、リーフ（２，７）、リーフ（２，８）、リーフ（２，９）にマークが付されることとなる。
【０２２７】
ヘッダ要素算出部３０９によるステップＳ３２１の判定は、ｙ＝１となっているため、条件を満たすこととなる。したがって、ヘッダ要素算出部３０９は、引き続き、ステップＳ３２３の判定を行う。この場合、ｘ＝０≠１であるので、分岐条件は満たされてはいない。したがって、ヘッダ要素算出部３０９は、ステップＳ３０７に戻って、ｘ＝１として、処理を繰り返すこととなる。
【０２２８】
再度戻ってきたステップＳ３０７から、ステップＳ３１１まで順に処理が行われると、ｘには１が、ｙには１が代入されている。したがって、次は、ノード（１，１）に対して、同様な処理を行う。
【０２２９】
この場合、ノード（１，１）のマークされていない子ノードの集合Ｓ１，１は、｛（２，１）｝のみである。同様にして、ヘッダ要素の算出が行われ、ヘッダ要素ｃ１，１として、（ν１，１・ｇ３）ｔが算出される。そして、ステップＳ３１９により、ノード（１，１）をルートとする部分木の全ノードにマークが付されるため、未だマークが付されていなかったリーフ（２，１）に対しても、マークが付されることとなる。
【０２３０】
その結果、ルートおよびリーフを含む、３分木構造の全てのノードに対してマークが付されるため、ステップＳ３２３における判定では、分岐条件を満足することとなる。
【０２３１】
上記の処理により、ヘッダ情報生成部３１１は、ヘッダ要素ｃｘ，ｙの値がゼロではないヘッダ要素、すなわち、ｃ０，１とｃ１，１を用いて、ヘッダｈを構成することとなる。したがって、ヘッダｈとしては、（ｇｔ，ｃ０，１，ｃ１，１）が構成されることとなる。また、配信されるコンテンツを復号可能な契約者の集合を意味するＳは、上記の処理により、｛（１，２），（１，３），（２，１）｝となる。
【０２３２】
以上説明したように、本実施形態に係る暗号化コンテンツ配信ブロックは、図１６に示したように、配信者５１３が、公開鍵ＰＫと、自身が選択した乱数ｔとを用いて、セッション鍵ｓと、ヘッダｈとを算出する。同時に、配信者５１３は、コンテンツを復号可能な契約者の集合Ｓも決定する。そして、配信者５１３は、同報通信路５１５を介して、契約者５０７、非契約者５１７を問わず、暗号化コンテンツＣ、ヘッダｈ、および集合Ｓを配信する。
【０２３３】
＜受信装置４０の動作：復号フェーズ＞
続いて、図２１を参照しながら、本実施形態に係る受信装置４０の動作、すなわち復号フェーズを、詳細に説明する。図２１は、受信装置４０による鍵処理方法である、復号フェーズの流れ図である。
【０２３４】
まず、暗号化コンテンツＣ、ヘッダｈ、集合Ｓを受信部４０１により受信した受信装置４０は、これらの情報を、一旦記憶部４０３に記憶する。この後、暗号化コンテンツＣの復号処理が行われる。
【０２３５】
まず、受信装置４０の判定部４０５は、記憶部４０３に記憶されている集合Ｓを参照して、自身に割り当てられたリーフからルートに至るまでの各ノードのうち、集合Ｓに含まれるものが存在するか否かを判定する（ステップＳ５０１）。判定の結果、集合Ｓに含まれるノードが存在しなければ、自身は排除されたものとして、以下の復号処理を終了する。また、判定の結果、集合Ｓに含まれるノードが存在する場合には、集合Ｓに含まれるノードのノードインデックスを（ｘ’，ｙ’）として、以下のステップＳ５０３を行うこととなる。
【０２３６】
受信装置４０の復号部４０７は、受信部４０１が受信し記憶部４０３に記憶されているヘッダｈの各要素のうち、ノード（ｘ’，ｙ’）の親ノード（ｘ，ｙ）に対応するヘッダ要素ｃｘ，ｙとｇｔとを選択する（ステップＳ５０３）。ここで、ノード（ｘ’，ｙ’）の親ノード（ｘ，ｙ）は、以下の式で表される。
【０２３７】
【数２４】
2008113201.tif 000026
【０２３８】
また、復号部４０７は、公開鍵と、自身の個人秘密鍵ｄｉからノード（ｘ’，ｙ’）に対応する要素とを利用して、以下のようにセッション鍵ｓを取得する（ステップＳ５０３）。
【０２３９】
【数２５】
2008113201.tif 000027
【０２４０】
続いて、復号部４０７は、得られたセッション鍵ｓを用いて、暗号化されたコンテンツＣを復号し、平文Ｍを得る（ステップＳ５０５）。
【０２４１】
Ｍ＝Ｄｓ（Ｃ）  ・・・（式１１３）
【０２４２】
続いて、図２２を参照しながら、本実施形態に係る復号フェーズを、具体的に説明する。図２２は、本実施形態に係る復号フェーズを具体的に説明するための説明図である。図２２では、３分木構造が構築され、リーフに９人の契約者が割り当てられている場合である。
【０２４３】
以下の例では、排除したい契約者が契約者２および契約者３であるとして、契約者１〜９に暗号化コンテンツＣ、ヘッダｈ、集合Ｓが配信されている場合を想定する。以下では、リーフ（２，４）に割り当てられた契約者４が、配信されたコンテンツを復号する場合について、詳細に説明する。
【０２４４】
図２２の場合、契約者４自身に割り当てられたリーフ（２，４）から、ルート（０，１）に至るまでに含まれるノードは、上記のリーフ（２，４）、ノード（１，２）、ルート（０，１）である。ここで、契約者４が使用している受信装置４０の判定部４０５は、受信部４０１が受信した集合Ｓに関する情報のなかに、上記の３つのノードが含まれているかを判定する。
【０２４５】
図２２の場合、契約者２および契約者３が排除したい契約者であるため、集合Ｓは、｛（１，２），（１，３），（２，１）｝となっている。これより、契約者４が割り当てられたリーフ（２，４）の親ノードである、ノード（１，２）が、集合Ｓに含まれていることがわかる。そのため、判定部４０５は、ステップＳ５０１の分岐条件が満たされていると判断し、復号部４０７が、引き続き復号処理を行う。
【０２４６】
この場合、ステップＳ５０３におけるノード（ｘ’，ｙ’）が、ノード（１，２）に該当する。そのため、ノード（ｘ’，ｙ’）の親ノード（ｘ、ｙ）は、ルート（０，１）となる。そこで、復号部４０７は、ノード（０，１）に対応するヘッダ要素ｃ０，１と、ｇｔとを選択する。また、自身の個人秘密鍵ｄ４から、ノード（０，１）に対する要素である、ν０，１に関する要素と、公開鍵ＰＫとを利用して、セッション鍵ｓを算出する。具体的には、セッション鍵ｓを得るための双線形群写像は、以下の式のようになる。
【０２４７】
【数２６】
2008113201.tif 000028
【０２４８】
以上、本実施形態に係る暗号鍵配信システム１０における鍵生成、暗号化、および復号という、三つのフェーズの一例を、詳細に説明した。
【０２４９】
なお、コンピュータを、上述したような本実施形態に係る鍵生成装置２０、暗号化装置３０および受信装置４０として機能させるためのコンピュータプログラムを、作成することも可能である。コンピュータプログラムは、コンピュータが備える記憶部に格納され、コンピュータが備えるＣＰＵに読み込まれて実行されることにより、そのコンピュータを上記の鍵生成装置２０、暗号化装置３０および受信装置４０として機能させる。また、コンピュータプログラムが記録された、コンピュータで読み取り可能な記録媒体も提供することができる。記録媒体は、例えば、磁気ディスク、光ディスク、光磁気ディスク、フラッシュメモリなどである。また、上記のコンピュータプログラムは、記録媒体を用いずに、例えばネットワークを介して配信してもよい。
【０２５０】
続いて、以下では、本実施形態に係る暗号鍵配信システム１０と、基盤技術である非特許文献１に記載のコンテンツ配信システムとの比較を行うこととする。
【０２５１】
基盤技術である非特許文献１の方法は、公開鍵を利用したコンテンツ配信システムにおいて、双線形写像を利用することにより、結託問題を解決した方式である。この方式は、予め契約者を複数のサブグループに分割しておき、コンテンツ配信時に、サブグループ毎に異なるヘッダ要素をすべて含むヘッダを配信している。これにより、排除される契約者数が増加したとしても、ヘッダサイズを一定の値とすることが可能となる。しかしながら、現実的なコンテンツ配信システムにおいて想定される、排除される契約者がいない、もしくは少ない場合においても、常に一定サイズのヘッダを配信する必要があるため、配信効率が悪くなるという問題点が存在する。
【０２５２】
また、分割されたサブグループに所属する契約者数Ｂが大きな値である、もしくは自身が所属するサブグループにおいて、排除される契約者数が少ない場合には、復号時に契約者が実行する必要がある演算の計算量が、大きくなるという問題点も存在する。
【０２５３】
これに対して、本実施形態に係る鍵生成装置では、基盤技術の方式を利用して論理木を構成し、若干のパラメータ増加を許すことによって、サブグループの構成を柔軟にし、特に排除される契約者がいないもしくは少ない場合において、配信されるヘッダサイズを削減可能とするとともに、契約者が実行する必要がある演算の計算量を、基盤技術に記載の方式と同等以下に削減することを可能とするものである。以下、基盤技術と本実施形態との主な相違点について、フェーズ毎の違いに着目して説明するとともに、ヘッダサイズおよび復号時に必要となる計算量に関して、具体的な数値例を用いて比較する。
【０２５４】
＜鍵生成フェーズの相違点＞
はじめに、鍵生成フェーズにおける相違点について述べる。基盤技術の方式では、ステップＳ１１およびステップＳ１３において各種パラメータを設定した後、ステップＳ１５において、契約者をＢ人ずつＡ個のサブグループに分割している。本実施形態においても同様に、ステップＳ１０１およびステップＳ１０３において各種パラメータを設定し、ステップＳ１０５において、契約者をＹ人ずつＸ個のサブグループに分割している。
【０２５５】
しかしながら、本実施形態では、さらにステップＳ１０５において、契約者をリーフに割り当てたＹ分木構造を構成している。これにより、基盤技術では、ステップＳ１９において、各サブグループに対応するヘッダ要素を一つにまとめるために利用するセンタ秘密であるγ１，・・・，γＡや、これらのセンタ秘密に対応する公開の値ν１，・・・，νＡが、サブグループの分割数であるＡ個必要となるのに対し、本実施形態では、ステップＳ１０５において構成したＹ分木のうち、リーフを除く全てのノードに対してサブグループを構成することが可能になるため、リーフを除く全ノード数であるＮ個の値が必要となる。
【０２５６】
また、基盤技術では、契約者ｉが所属するサブグループは、以下の式で表されるＳａ一つのみである。
【数２７】
2008113201.tif 000029
【０２５７】
そのため、センタは、契約者ｉに対して、個人秘密鍵
【数２８】
2008113201.tif 000030
を秘密裏に配布するが、本実施形態では、ステップＳ１０５おいて論理木を構成した後、ステップＳ１０９において、論理木の各ノードを、サブグループの再構成に利用することが可能であるため、契約者ｉは、自身に割り当てられたリーフからルートに至る全ノードによって構成される複数のサブグループに、所属しておく必要がある。
【０２５８】
したがって、本実施形態におけるステップＳ１１５では、契約者ｉに対して、複数の個人秘密鍵を保持する必要がある。このように、鍵生成フェーズにおいて、本実施形態では論理木を構成しているため、必要とされるパラメータが、基盤技術におけるものよりも、若干増加している。しかしながら、排除される契約者が存在しない、または少ない場合において、次に示す暗号化フェーズで生成されるヘッダのヘッダサイズを、基盤技術よりも削減することが可能となる。
【０２５９】
＜暗号化フェーズの相違点＞
次に、暗号化フェーズに関して説明する。基盤技術では、ステップＳ３１においてセッション鍵を生成し、その後、ステップＳ３３において、サブグループ毎に排除されない契約者を選定して、それらの契約者に割り当てられたサブグループにおける契約者インデックスの集合Ｓｌ（ｌ＝１，・・・，Ａ）を決定している。その後、ステップＳ３５において、各サブグループにおける排除されていない契約者のみがセッション鍵を取得可能なヘッダ要素を計算し、ヘッダを構成している。したがって、サブグループに所属する契約者が全員排除されない限り、全てのサブグループに対応するヘッダ要素を、計算する必要がある。そのため、ヘッダサイズは、排除される契約者数ｒの大小に関わらず、常に一定となる。
【０２６０】
これに対して本実施形態では、ステップＳ３０１において、排除される契約者に割り当てられたリーフからルートに至る全てのノードをマークし、排除されていない契約者が、ヘッダｈから自身に割り当てられたヘッダ要素を特定するための、ノードインデックスの集合を、Ｓとしている。その後、ステップＳ３０３において、基盤技術と同様の手法によってセッション鍵ｓを生成し、ステップＳ３０５からステップＳ３２５において、マークされていないノードに割り当てられている契約者のみが、セッション鍵ｓを取得することが可能なヘッダ要素を計算し、ヘッダｈを構成している。
【０２６１】
より詳細には、本実施形態のステップＳ３１７において、Ｌａｙｅｒ  ｘに所属するノードのうち、マークされていないノードに対するヘッダ要素を作成している。これは、基盤技術におけるステップＳ３５の動作と同様の動作である。ただし、基盤技術では、すでにサブグループがＡ個存在しているため、ステップＳ３５においてＡ個のヘッダ要素を生成する必要があるのに対して、本実施形態では、ステップＳ３１７において、あるノードの子ノード集合についてのみ実行しており、ステップＳ３０７からステップＳ３２３において、この処理を繰り返している。
【０２６２】
ここで、ステップＳ３１５からステップＳ３１９において示したように、一度ヘッダ要素が生成されたノードに対しては、そのノードを頂点とする部分木に所属する全てのノードをマークすることによって、これらのノードに対応するヘッダ要素を、生成する必要がなくなる。これにより、パス上に、そのノードを含む全ての排除されていない契約者に対するヘッダ要素を、まとめることが可能になるという利点が生じる。したがって、排除されている契約者が少ない場合には、より多くのノードをまとめることが可能となり、ヘッダサイズを削減することが可能となっている。
【０２６３】
＜復号フェーズの相違点＞
最後に、復号フェーズに関して述べる。基盤技術では、ステップＳ５３において、排除されていない契約者が、自身の所属するサブグループに対応するヘッダ要素を取得し、このヘッダ要素と公開鍵及び個人秘密鍵を利用して、セッション鍵を導出している。これに対して本実施形態では、ステップＳ５０３において、排除されていない契約者が、自身に割り当てられたリーフからルートに至るパス上に存在するノードのうち、Ｓに含まれるノードの親ノードに対応するヘッダ要素を取得し、このヘッダ要素と公開鍵及び個人秘密鍵を利用して、セッション鍵を導出している。
【０２６４】
これは、対応するヘッダ要素および使用する個人秘密鍵が異なるのみであり、基盤技術と同様の動作である。ただし、基盤技術の復号フェーズにおいて、契約者が実行する必要のある演算の計算量は、２ＰＡＩＲ＋ＩＮＶ＋（Ｂ−１−ｒａ）ＭＵＬであるのに対し、本実施形態では、２ＰＡＩＲ＋ＩＮＶ＋（Ｙ−１−ｒａ）ＭＵＬとなる。
【０２６５】
＜ヘッダサイズおよび計算量に関する比較＞
基盤技術では、契約者集合をＢ人ずつＡ個のサブグループに分割し、コンテンツ配信時には、サブグループ毎に対応するヘッダ要素を生成し、全てのヘッダ要素を一括してヘッダとして配信している。従って、そのヘッダサイズは排除される契約者数ｒの大小に関わらず、常にＡ＋１となる。これは、ヘッダサイズが一定に抑えられるという利点を有する一方で、排除される契約者数に関わらずヘッダサイズを削減不可能であるという欠点でもある。現実的なコンテンツ配信システムでは、全契約者数に対する排除される契約者数の割合が小さい範囲で、効率よくコンテンツを配信可能であることが要求されるため、安全性および利便性を重視して基盤技術の方式を利用したとしても、コンテンツ配信時におけるヘッダサイズの冗長性が大きくなってしまうという問題点が存在する。
【０２６６】
基盤技術においてこの問題を改善するためには、契約者集合の分割数Ａを小さくすることにより、ヘッダサイズそのものを小さくすることが考えられる。しかし、この場合には、分割されたサブグループに所属する契約者数であるＢの値が大きくなり、各契約者が実行する必要のある演算の計算量の値２ＰＡＩＲ＋ＩＮＶ＋（Ｂ−１−ｒａ）ＭＵＬが大きくなってしまうという問題点が存在する。
【０２６７】
これに対して本実施形態では、基盤技術同様、契約者集合をＹ人ずつＸ個のサブグループに分割している。しかし、さらにその上、若干のパラメータを追加することにより、分割したサブグループの各契約者をリーフとするＹ分木を構成している。これによって、基盤技術では、排除された契約者が存在するかどうかに関わらず、ヘッダサイズがＡ＋１となっているものを、排除された契約者が存在しないサブグループに所属する各契約者は、ルートを最上位とした場合、より上位のＬａｙｅｒのメンバとして扱うことが可能となる。そのため、複数のサブグループを一つのサブグループとして扱うことが可能となり、ヘッダサイズを削減することを可能としている。また、各契約者が実行する必要のある演算の計算量は、上記のように２ＰＡＩＲ＋ＩＮＶ＋（Ｙ−１−ｒａ）ＭＵＬとなるが、ＹはＢ以下であるとして設定することにより、基盤技術の方式と同等以下に、計算量を削減することが可能となっている。
【０２６８】
以上、基盤技術と比較しながら説明したように、本発明は、公開鍵を利用したコンテンツ配信方式の一方式であり、基盤技術と比較して、以下の特徴を有する。
【０２６９】
第１に、本実施形態では、基盤技術の方式にパラメータを追加することによって論理木を構成し、追加したパラメータを、論理木の各ノードに割り当てている。
【０２７０】
第２に、センタである鍵生成装置は、各契約者に対して、論理木に割り当てられたパラメータに関連する情報を、追加の個人秘密鍵として、予め配布しておく。
【０２７１】
第３に、暗号化コンテンツの配信者は、暗号化装置を操作して、契約者が排除された場合には、共通鍵を利用したコンテンツ配信方式同様、ノードごとの排除を行ったヘッダｈを生成する。
【０２７２】
第４に、各契約者は、受信装置を操作して、基盤技術と同様の方法により、公開鍵ＰＫ、ヘッダｈ、および個人秘密鍵ｄｉから、セッション鍵ｓを算出する。
【０２７３】
第５に、基盤技術の方式を、上記第１〜第４の特徴のようにして構成することにより、契約者における復号時に必要となる計算量を、基盤技術の方式と同等以下に削減することが可能となる。
【０２７４】
第６に、基盤技術の方式を、上記第１〜第４の特徴のようにして構成することにより、排除される契約者が少ない場合には、基盤技術よりもヘッダサイズを削減することが可能となる。
【実施例】
【０２７５】
本実施形態の効果をより詳細に説明するために、具体例としてパラメータｎ、Ａ、Ｂ、Ｘ、Ｙを小さな値に設定した場合における、ヘッダサイズ及び復号時に必要となる計算量の比較について、図２３〜図２６に示す。
【０２７６】
基盤技術では、分割されたサブグループに含まれる契約者数Ｂの値を、契約者数ｎに対してＢ＝（ｎ）１／２として設定することを推奨している。これに対して本実施形態では、基盤技術のＢに対応するパラメータである論理木の分岐数Ｙを、ＹはＢ以下であると設定することにより、ヘッダサイズ及び計算量の点で効率化を図ることが可能である。
【０２７７】
よって以下では、比較のため、契約者数ｎを同一とし、Ｙ＜Ｂと設定した。基盤技術と本実施形態におけるヘッダサイズおよび復号時に必要となる演算の計算量比較を、各々図２３および図２４に示す。また、Ｙ＝Ｂとした場合のヘッダサイズ及び復号時に必要となる計算量比較を、各々図２５および図２６に示す。
【０２７８】
具体的な数値として、図２３および図２４では、基盤技術の方式における各パラメータを、ｎ＝６４、Ａ＝８、Ｂ＝８とし、本実施形態では、ｎ＝６４、Ｘ＝１６、Ｙ＝４とした。また、図２５および図２６では、ｎ＝６４、Ｘ＝８、Ｂ＝Ｙ＝８とした。ただし、利用する双線形群やその大きさについては、簡単のため同一のものとした。
【０２７９】
（Ｙ＜Ｂと設定した場合について）
はじめに、図２３および図２４について説明する。図２３の横軸は、排除された契約者数を表し、縦軸は、ヘッダサイズ（ヘッダ要素の総数）を表す。また、図２４の横軸は、排除された契約者数を表し、縦軸は、復号時に必要となる演算の計算量を表す。ただし、復号時に必要となる演算の計算量に関して、基盤技術と本実施形態の違いに影響するのは双線形群Ｇ上での乗算部分においてのみであるため、図２４の縦軸は、双線形群Ｇ上での乗算回数を表すものとする。また、図２３における実線は、基盤技術の方式におけるヘッダサイズを表し、破線は、本実施形態におけるヘッダサイズを表している。また、図２４における実線は、基盤技術の方式における計算量を表し、破線は、本実施形態における計算量を表している。
【０２８０】
ヘッダサイズの比較に関しては、図２３より明らかなように、排除される契約者数ｒが４より小さい場合には、本実施形態に係る方式の方が、基盤技術の方式に比べてヘッダサイズが少なくなることがわかった。すなわち、この場合、全契約者に対して約６％程度までの契約者が排除されても、本実施形態に係る方式の方が、効率的にコンテンツを配信可能であることを示している。
【０２８１】
復号時に必要となる計算量の比較に関しては、図２４より明らかなように、排除される契約者数ｒが６０より小さい場合には、本実施形態に係る方式の方が、基盤技術の方式よりも、計算量が少ないことがわかった。これは、本実施形態に係る方式の方が、効率的にコンテンツを復号可能であることを示している。また、排除される契約者数が６０を超えた場合においても、基盤技術の方式における計算量と同等であることがわかった。したがって、上記のようにパラメータを設定した場合においては、排除される契約者が存在しない、あるいは少ない場合において、本実施形態に係る方式の方が、基盤技術に係る方式よりも、ヘッダサイズを小さくすることが可能であり、さらに、各契約者が復号時に実行する必要のある演算の計算量を、少なくすることが可能である。そのため、本実施形態に係る方式の方が、基盤技術に係る方式よりも、効率的にコンテンツ配信を実現することが可能であるといえる。
【０２８２】
（Ｙ＝Ｂと設定した場合について）
次に、図２５および図２６について説明する。図２５および図２６は、前述の図２３および図２４に対してＸおよびＹの値を変更したのみであるため、その横軸および縦軸、ならびに、実線、破線が表すものは、図２３および図２４のそれと同一である。
【０２８３】
Ｘ＝Ａ＝８、Ｙ＝Ｂ＝８とした場合のヘッダサイズの比較に関しては、図２５より明らかなように、排除される契約者数ｒが７より小さい場合には、本実施形態に係る方式の方が、基盤技術に係る方式よりも、ヘッダサイズが少なくなることがわかった。すなわち、この場合、全契約者に対して約９％程度までの契約者が排除されても、本実施形態に係る方式の方が、効率的にコンテンツを配信可能であることを示している。排除される契約者数が７以上となった場合においても、基盤技術の方式と同等のヘッダサイズとなっており、排除される契約者数に関わらず、ヘッダサイズを基盤技術の方式以下に削減することが可能となっている。
【０２８４】
また、復号時に必要となる計算量の比較に関しては、図２６より明らかなように、排除される契約者数ｒに関わらず、基盤技術の方式と同等であることがわかった。よって、各パラメータをＸ＝Ａ＝８、Ｙ＝Ｂ＝８と設定した場合には、排除される契約者が存在しない、あるいは少ない場合において、ヘッダサイズを削減することが可能であると共に、復号時の計算量は、基盤技術の方式と同等で済むことがわかった。
【０２８５】
以上より、本実施形態を適用することにより、基盤技術と同様の利便性、安全性を維持したまま、より現実的なコンテンツ配信システムにおいて、基盤技術よりも効率的なコンテンツ配信を実現することが可能となることがわかる。
【０２８６】
以上説明したように、本発明は、公開鍵を利用してコンテンツを安全に配信するコンテンツ配信システムにおいて、従来の方式よりも、配信されるデータ量の削減および復号時に必要となる計算量の削減を実現する方法である。本発明の実施により、従来の公開鍵を利用したコンテンツ配信法と比較して、より効率的なコンテンツ配信が実現可能となる。
【０２８７】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明はかかる例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【０２８８】
例えば、上記の木構造構成部２３１は、上から下に枝が広がった木構造を想定していたが、必ずしもこれに限定されず、下から上、左から右、又は右から左に向かって枝が広がった木構造を有していてもよい。
【０２８９】
また、本明細書の各流れ図における各ステップは、必ずしも流れ図として記載された順序に沿って時系列に処理する必要はなく、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）も含むとしても良い。
【図面の簡単な説明】
【０２９０】
【図１】本発明の好適な実施形態に係る暗号鍵生成システムを説明するための説明図である。
【図２】同実施形態に係る鍵生成装置のハードウェア構成を説明するためのブロック図である。
【図３】本発明の基盤技術の基本方式に係る鍵生成の概略を説明するための説明図である。
【図４】本発明の基盤技術の一般化方式に係る鍵生成の概略を説明するための流れ図である。
【図５】本発明の基盤技術の一般化方式に係る鍵生成フェーズを説明するための流れ図である。
【図６】本発明の基盤技術の一般化方式に係る暗号化の概略を説明するための説明図である。
【図７】本発明の基盤技術の一般化方式に係る暗号化フェーズを説明するための流れ図である。
【図８】本発明の基盤技術の一般化方式に係る復号フェーズを説明するための流れ図である。
【図９】本発明の好適な実施形態に係る鍵生成装置の構成を説明するためのブロック図である。
【図１０】同実施形態に係る暗号化装置の構成を説明するためのブロック図である。
【図１１】同実施形態に係る受信装置の構成を説明するためのブロック図である。
【図１２】同実施形態に係る論理木の具体例を説明するための説明図である。
【図１３】同実施形態に係る鍵生成の概略を説明するための説明図である。
【図１４】同実施形態に係る鍵生成フェーズを説明するための流れ図である。
【図１５】同実施形態に係る鍵生成の具体例を説明するための説明図である。
【図１６】同実施形態に係る暗号化の概略を説明するための説明図である。
【図１７】同実施形態に係る暗号化フェーズを説明するための流れ図である。
【図１８】同実施形態に係る暗号化の具体例を説明するための説明図である。
【図１９】同実施形態に係る暗号化の具体例を説明するための説明図である。
【図２０】同実施形態に係る暗号化の具体例を説明するための説明図である。
【図２１】同実施形態に係る復号フェーズを説明するための流れ図である。
【図２２】同実施形態に係る復号の具体例を説明するための説明図である。
【図２３】契約者に配信されるヘッダのヘッダサイズを比較したグラフ図である。
【図２４】双線形群上での乗算の回数を比較したグラフ図である。
【図２５】契約者に配信されるヘッダのヘッダサイズを比較したグラフ図である。
【図２６】双線形群上での乗算の回数を比較したグラフ図である。
【符号の説明】
【０２９１】
１０    暗号鍵配信システム
１２    通信網
１４    リムーバブル記録媒体
２０    鍵生成装置
３０    暗号化装置
４０    受信装置
２０１    ＣＰＵ
２０３    ＲＯＭ
２０５    ＲＡＭ
２０７    ＨＤＤ
２０９    暗号処理部
２１１    メモリ
２１３    バス
２１５    入出力インターフェース
２１７    入力部
２１９    出力部
２２１    通信部
２２３    ドライブ
２３１    木構造構成部
２３３    乱数決定部
２３５    リーフキー割当部
２３７    パラメータ割当部
２３９    鍵算出部
２４１    記憶部
２４３    木構造記憶部
２４５    乱数記憶部
２４７    リーフキー記憶部
２４９    パラメータ記憶部
２５１    鍵記憶部
２５２    配布部
２５３    送信部
２５５    公開鍵公開部
３０１    受信部
３０３    記憶部
３０５    排除受信装置特定部
３０７    セッション鍵決定部
３０９    ヘッダ要素算出部
３１１    ヘッダ情報生成部
３１３    コンテンツ記憶部
３１５    暗号化部
３１７    コンテンツ送信部
４０１    受信部
４０３    記憶部
４０５    判定部
４０７    復号部
【図１】
2008113201.tif 000035
【図２】
2008113201.tif 000036
【図３】
2008113201.tif 000037
【図４】
2008113201.tif 000038
【図５】
2008113201.tif 000039
【図６】
2008113201.tif 000040
【図７】
2008113201.tif 000041
【図８】
2008113201.tif 000042
【図９】
2008113201.tif 000043
【図１０】
2008113201.tif 000044
【図１１】
2008113201.tif 000045
【図１２】
2008113201.tif 000046
【図１３】
2008113201.tif 000047
【図１４】
2008113201.tif 000048
【図１５】
2008113201.tif 000049
【図１６】
2008113201.tif 000050
【図１７】
2008113201.tif 000051
【図１８】
2008113201.tif 000052
【図１９】
2008113201.tif 000053
【図２０】
2008113201.tif 000054
【図２１】
2008113201.tif 000055
【図２２】
2008113201.tif 000056
【図２３】
2008113201.tif 000057
【図２４】
2008113201.tif 000058
【図２５】
2008113201.tif 000059
【図２６】
2008113201.tif 000060