(57)【要約】  本発明によるシステムは、グループキーＧＫとアドレスキー（Ｘｊ，Ｙｊ，ＺＪ）を提供するキー提供手段を有する少なくとも１つの送信機Ｓを有する。複数の受信機ｒの各々は、各受信機アドレスキーセットとグループキーにアクセスするアクセス手段を有する。グループキーは、同一グループのすべての受信機に対して同一である。各受信機アドレスキーセットは、アドレスキーベースセットのサブセットである。受信機アドレスキーセットは、同一グループのすべての受信機ペアに対してペア単位で異なっている。各受信機に対して、受信機アドレスキーセットに含まれない１以上の排除キー（Ｘ，Ｙ，Ｚ）が存在する。本システムは、各受信機に関する認証情報を格納する認証格納手段（３０）を有する。暗号化手段（２４）は、複数の暗号化メッセージｍｋ＊をメッセージｍｋから生成するのに使用される。各暗号化メッセージｍｋ＊は、合成キーのすべてのキーを使用してのみ解読可能となるように合成キーにより暗号化される。各暗号化メッセージｍｋ＊は、１つの受信機グループを対象とし、合成キーは、当該グループのグループキーを含む。非認証受信機を排除するため、合成キーはさらに、グループの非認証受信機の１以上の排除キーを有する。
2007538454.tif 000002
【特許請求の範囲】
【請求項１】
メッセージの選択的マルチキャストのためのシステムであって、
少なくとも１つの送信機と、
前記送信機に係り、グループキーベースセットとアドレスキーベースセットとを提供するキー提供手段と、
暗号化メッセージを送信する送信手段と、
を有し、
当該システムはさらに、
複数のグループのメンバーである複数の受信機と、
前記受信機の各々に係り、各受信機アドレスキーセットと１以上のグループキーとにアクセスするアクセス手段と、
を有し、
前記１以上のグループキーは、同一グループのすべての受信機について同一であり、
前記受信機アドレスキーセットの各々は、前記アドレスキーベースセットのサブセットであり、
前記受信機アドレスキーセットは、同一グループの受信機のすべてのペアについてペア毎に異なっており、
各受信機に対して、該受信機の受信機アドレスキーセットに含まれていない前記アドレスキーベースセットからの１以上の排除キーが存在し、
当該システムはさらに、前記受信機の各々に関する認証情報を格納する認証格納手段を有し、
当該システムはさらに、
前記メッセージから複数の暗号化メッセージを生成する暗号化手段を有し、
前記暗号化メッセージの各々は、合成キーからのすべてのキーを使用してのみ解読可能となるように前記合成キーにより暗号化され、
前記暗号化メッセージの各々は、前記受信機のグループからのターゲットグループを対象とし、前記合成キーは、前記ターゲットグループの１以上のグループキーを有し、
前記合成キーはさらに、前記ターゲットグループの非認証受信機の１以上の排除キーを含む、
ことを特徴とするシステム。
【請求項２】
請求項１記載のシステムであって、
複数の前記受信機アドレスキーセットが、異なるグループの受信機に対して同一であることを特徴とするシステム。
【請求項３】
請求項１又は２記載のシステムであって、
前記暗号化手段は、前記合成キーを使用して前記メッセージを再帰的に暗号化するよう構成されることを特徴とするシステム。
【請求項４】
請求項１乃至３何れか一項記載のシステムであって、さらに、
前記アドレスキーベースセットを生成するアドレスキー生成手段と、
前記アドレスキーを前記受信機に選択的に送信する選択的キー送信手段と、
を有することを特徴とするシステム。
【請求項５】
請求項４記載のシステムであって、
前記キー提供手段は、暗号キー選択ベースセットを格納するよう構成される格納手段を前記送信機に有し、
前記受信機の各々は、受信機選択キーセットを格納する格納手段を有し、
前記受信機選択キーセットの各々は、前記選択ベースキーセットのサブセットであり、
同一グループの受信機の前記受信機選択キーセットは、互いにペア毎には含まれず、
異なるグループの受信機の複数の受信機選択キーセットは、同一であり、
前記選択的キー送信手段は、前記選択キーの１以上により前記アドレスキーを暗号化するよう構成される、
ことを特徴とするシステム。
【請求項６】
請求項１乃至５何れか一項記載のシステムであって、
各受信機に対して、該受信機の受信機アドレスキーセットに含まれていない前記アドレスキーベースセットに含まれる排除キーは１つしか存在せず、
該排除キーは、前記受信機と同一グループの残りの受信機の受信機アドレスキーセットに含まれる、
ことを特徴とするシステム。
【請求項７】
請求項５又は６記載のシステムであって、
各グループは、最大でｂｄ個の受信機を有し（ただし、ｂは整数ベーシス数であって、ｂ≧２であり、ｄは次元数であって、ｄ≧１である）、
前記選択ベースキーセットは、ｂ＊ｄ個の選択キーを有し、
各受信機の受信機選択キーセットは、（ｂ−１）＊ｄ個の選択キーを有し、
各受信機の受信機選択キーセットは、ベーシスｂに対する番号システムによる受信機番号ｒの表現に対応し（０≦ｒ≦ｂｄ−１）、ｒの各桁は、ｄ個の異なる選択キーの１つにより表される、
ことを特徴とするシステム。
【請求項８】
請求項７記載のシステムであって、
前記アドレスベースキーセットは、ｂｄ個のアドレスキーを有し、
前記アドレスキーの各々は、ｄ回送信され、各回毎に送信合成選択キーからの異なる１つにより暗号化され、
各アドレスキーに対する前記送信合成選択キーは、ベーシスｂに対する番号システムのキー番号ｔの表現に対応するよう選択され（０≦ｔ≦ｂｄ−１）、ｔの各桁は、ｄ個の異なる選択キーの１つにより表される、
ことを特徴とするシステム。
【請求項９】
請求項１乃至５何れか一項記載のシステムであって、
各受信機に対して、対応する受信機アドレスキーセットに含まれていない前記アドレスキーベースセットからの少なくとも２つの排除キーが存在し、
各合成排除キーは、各グループ内で一意的である、
ことを特徴とするシステム。
【請求項１０】
請求項１乃至５何れか一項又は請求項９記載のシステムであって、
前記アドレスキーベースセットは、第１アドレスキーと第２アドレスキーとに分割され、
前記グループは、複数のサブグループに分割され、
前記受信機アドレスキーセットは、第１受信機アドレスキーセットと、第２受信機アドレスキーセットとを有し、
同一サブグループ内の各受信機の受信機アドレスキーセットは、同一の第１受信機アドレスキーセットを有し、
各受信機の受信機アドレスキーセットは、該受信機のサブグループ内において一意的な第２受信機アドレスキーセットを含む、
ことを特徴とするシステム。
【請求項１１】
請求項１０記載のシステムであって、
各サブグループに対して、前記第１受信機アドレスキーセットに含まれない前記第１アドレスキーからのサブグループ排除キーが１つ存在し、該サブグループ排除キーは、前記グループの残りのサブグループの第１受信機アドレスキーセットに含まれ、
各受信機に対して、前記第２受信機アドレスキーセットに含まれない前記第２アドレスキーからのポジション排除キーは１つしか存在せず、前記ポジション排除キーは、前記サブグループの残りの第２受信機アドレスキーセットに含まれ、
前記暗号化手段は、前記グループの非認証受信機の前記サブグループ排除キーと前記ポジション排除キーとから前記排除キーを計算するよう構成される、
ことを特徴とするシステム。
【請求項１２】
請求項１１記載のシステムであって、
前記暗号化手段は、前記サブグループ排除キーと前記ポジション排除キーとの再帰的指数化によって、前記排除キーを計算するよう構成されることを特徴とするシステム。
【請求項１３】
請求項１０乃至１２何れか一項記載のシステムであって、
各グループは、最大でｂ２ｄ個の受信機を有し（ただし、ｂは整数ベーシス数であって、ｂ≧２であり、ｄは次元数であって、ｄ≧１である）、各グループは、各サブグループに最大でｂｄ個の受信機を有する最大でｂｄ個のサブグループを有し、
前記選択ベースキーセットは、ｂ＊ｄ個の第１選択キーとｂ＊ｄ個の第２選択キーとを有する２＊ｂ＊ｄ個の選択キーを有し、
各受信機の受信機選択キーセットは、（ｂ−１）＊ｄ個の第１選択キーセットと、（ｂ−１）＊ｄ個の第２選択キーセットとを有し、
各受信機の受信機選択キーセットの第１選択キーセットは、ベーシスｂに対する番号システムによる受信機番号ｒの表現に対応し（０≦ｒ≦ｂｄ−１）、ｒの各桁は、ｄ個の異なる選択キーの１つにより表され、
各受信機の受信機選択キーセットの第２選択キーセットは、ベーシスｂに対する番号システムによるサブグループ番号ｓの表現に対応し（０≦ｓ≦ｂｄ−１）、ｓの各桁は、ｄ個の異なる選択キーの１つにより表される、
ことを特徴とするシステム。
【請求項１４】
請求項１３記載のシステムであって、
前記アドレスベースキーセットは、ｂｄ個の第１アドレスキーとｂｄ個の第２アドレスキーとを有し、
前記アドレスキーの各々は、ｄ回送信され、各回毎に送信合成選択キーからの異なる１つにより暗号化され、
各アドレスキーに対する前記送信合成選択キーは、ベーシスｂに対する番号システムのキー番号ｔの表現に対応するよう選択され（０≦ｔ≦ｂｄ−１）、ｔの各桁は、ｄ個の異なる選択キーの１つにより表される、
ことを特徴とするシステム。
【請求項１５】
少なくとも１つのスクランブリングキーによりスクランブル化されるスクランブル化されたコンテンツメッセージをブロードキャストする送信機と、
前記スクランブル化されたメッセージを受信する複数の受信機と、
前記スクランブリングキーを認証受信機に選択的に送信する請求項１乃至１４何れか一項記載のシステムと、
を有することを特徴とするブロードキャストシステム。
【請求項１６】
少なくとも１つの送信機と、複数のグループに分割される複数の受信機とを有するシステムにおいてメッセージを選択的にマルチキャストする方法であって、
グループキーベースセットを提供するステップと、
アドレスキーベースセットを提供するステップと、
前記受信機の各々に対して、同一グループのすべての受信機に同一のグループキーが提供されるように、１以上のグループキーを提供するステップと、
各受信機アドレスキーセットが前記アドレスキーベースセットのサブセットとなり、各受信機に対して対応する受信機アドレスキーセットに含まれていない前記アドレスキーベースセットからの少なくとも１つの排除キーが存在するように、前記受信機の各々に対して受信機アドレスキーセットを提供するステップと、
非認証受信機と認証受信機とに関する情報を取得するステップと、
各暗号化メッセージが、合成キーからのすべてのキーを使用してのみ解読可能となるように前記合成キーを使用して暗号化され、前記合成キーが受信機のターゲットグループの１以上のグループキーを有し、前記合成キーが前記ターゲットグループの非認証受信機の複数の排除キーを有するように、前記暗号化メッセージの各々が前記受信機のターゲットグループを対象とし、複数の暗号化メッセージを生成するよう前記メッセージを処理するステップと、
前記暗号化メッセージを前記送信機から前記受信機に送信するステップと、
を有することを特徴とする方法。
【請求項１７】
請求項１６記載の方法であって、
前記アドレスキーセットは、前記送信機において生成され、
前記アドレスキーセットからのアドレスキーは、前記受信機に選択的に送信され、
前記アドレスキーセットは、限定数のメッセージを送信するのに使用される、
ことを特徴とする方法。
【請求項１８】
請求項１６又は１７記載の方法であって、
前記受信機アドレスキーセットを提供するステップは、前記暗号化メッセージを送信するステップの後に実行されることを特徴とする方法。
【請求項１９】
請求項１８記載の方法であって、
前記暗号化メッセージは、完全な受信機アドレスキーセットを格納することなく、受信に応答して前記受信機アドレスキーを使用することによって前記受信機において解読されることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージの選択的マルチキャストシステム並びに選択的マルチキャストのためのブロードキャストシステム及び方法に関する。
【背景技術】
【０００２】
基本的なデータ送信システムでは、データは、送信機からチャネルを介し複数の受信機に送信される。データ送信に使用される物理チャネルは、本発明の範囲外であり、何れか既知の形式のデータ送信方法及び何れかのタイプの媒体を含みうる。本開示において扱われる問題は、複数の受信機にデータを選択的に送信し、他の受信機が当該データを受信することを排除する方法である。この選択性は、当該タスクについて具体的に適応される暗号化スキームにより解決される。
【０００３】
ある送信機から複数の受信機へのデータ送信は、「マルチキャスト」又は「ポイント・ツー・マルチポイント」送信と呼ばれる。選択的なマルチキャスト送信は、有料テレビなどのエリアですでに適用されている。しかしながら、インターネット通信と共にモバイル通信でさえも選択的マルチキャストを利用するかもしれない。
【０００４】
ブロードキャストシステムでは、チャネルを介し送信されるデータは、スクランブル処理され、当該データをスクランブル解除するのに必要なキー情報（ここでは、「マルチキャストキー」と呼ばれる）が、所望の選択性が実現されるように（認証された受信機のみが当該メッセージを解読可能であり、認証されていない受信機は当該メッセージを解読することができない）、受信機間に配布されている。使用される暗号化により、これらのシステムは、送信方法及びチャネルが受信機の個数を制限しないブロードキャストアプリケーションに良好に適している。
【０００５】
しかしながら、この方法は、構成員の変化に関してあまりフレキシブルではない。以前に認証された受信機がマルチキャストグループから離れる場合、以前に使用されていたマルチキャストキー（共有キー）が変更される必要があり、これにより、排除された受信機にはさらなる送信はもはや読み取り可能ではない。新たなマルチキャストキーが、残りの認証された受信機にのみ安全かつ選択的に送信される必要がある。ペイ・パー・ビューシステムを含む有料テレビなどのいくつかのアプリケーションでは、構成員はかなり動的であるかもしれない。これらのアプリケーションにとって、必要なキー変更に係るオーバヘッドは、小さなものに維持される必要がある。特に中規模な個数（１００〜１００，０００など）の受信機を有するマルチキャスト又はブロードキャストシステムにおいて、そして大規模な個数（１０，０００以上など）の受信機を有するマルチキャストシステムについては、帯域幅要求は大変重要である。さらに、特に多数の受信機を有する大規模システムでは、受信機側にシンプルかつ安価なハードウェアを利用可能であることが大変望ましい。従って、マルチキャストシステムの他の重要なパラメータは、受信機側に対するメモリ消費及び計算量である。
【０００６】
ＵＳ−Ａ−６０４９８７８において、上記問題を解決する選択的データ送信のためのシステムの一例が与えられる。当該システムは、ある送信機といくつかの受信機を含む。各受信機において、複数のキーがアクセス可能である。マルチキャストキー（ここでは、トラフィック暗号キー（ＴＥＫ）と呼ばれる）が、送信機と他のすべての受信機に共有される。さらに、各受信機は、複数のキー暗号キー（ＫＥＫ）を保持する。システムの論理構造は、送信機がルートであり、受信機がリーフであるバイナリツリー構造となっている。各リーフは、ルートからリーフへのパスにより構成されるキーを保持する。
【０００７】
退出処理の場合、すなわち、受信機はもはやデータを受信する許可が与えられていない場合、退出する送信機へのパスのすべてのキーが、ボトムアップ方式により変更される。その後、マルチキャストキー（ＴＥＫ）が、退出する受信機を排除するよう変更される。退出した受信機によってもはや読み取ることができない新たな変更されたＴＥＫを利用して、さらなるトラフィックがスクランブル処理される。
【０００８】
ＵＳ−Ａ−６０４９８７８に開示されるシステム及び方法は、退出処理の場合に求められる帯域幅を良好に低減する。しかしながら、すべての退出処理について、依然として論理ツリーの完全パスの再キー処理が必要である。
【０００９】
ＩＥＴＦ（Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ）によって発行されたＲＦＣ２６２７“Ｋｅｙ  Ｍａｎａｇｅｍｅｎｔ  Ｆｏｒ  Ｍｕｌｔｉｃａｓｔ：Ｉｓｓｕｅｓ  Ａｎｄ  Ａｒｃｈｉｔｅｃｔｕｒｅｓ”（１９９９年６月）は、マルチキャストグループの各種アーキテクチャを説明している。動的なマルチキャストグループの帯域幅及び格納要求の具体的な問題が、テレビ会議及び分散ゲームなどのアプリケーションについて記載されている。推奨されるアーキテクチャは、ＵＳ−Ａ−６０４９８７８に提起されたものと同様の階層ツリーである。他のアーキテクチャとして、送信機が各受信機とＤｉｆｆｉｅ−Ｈｅｌｌｍａｎプロトコルによる公開鍵交換を実行する送信機と受信機との間のペアキーが提案され、それは、暗号化形式によりマルチキャストキーを送信するのに使用される各暗号キー（ＫＥＫ）の確立を可能にする。この基本的アーキテクチャを精緻化したものでは、補完変数と呼ばれる異なるキーセットが受信機の間に分散されている。ＲＦＣ２６２７では、すべての受信機は、自らを除いてすべての補完変数を受信する。従って、排除される受信機の補完変数及び以前のマルチキャストキーに基づき、新たなマルチキャストキーを生成することによって、マルチキャストグループから各受信機を排除することが可能である。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の課題は、メッセージの選択的なマルチキャストのためのシステム並びに特に中規模又は大規模な個数の受信機に良好に適したメッセージの選択的マルチキャストのためのブロードキャストシステム及び方法を提案する。
【課題を解決するための手段】
【００１１】
本発明によると、上記課題は、請求項１記載のマルチキャストシステム、請求項１５記載のブロードキャストシステム及び請求項１６記載の方法によって解決される。従属クレームは、本発明の好適な実施例に関する。
【００１２】
本発明によるシステムは、少なくとも１つの送信機と複数の受信機とを有する。セキュアなマルチキャストの以下の説明は送信機から受信機への一方向の通信に限定されているが、これはおそらくバックチャネル、すなわち、以降の通信中における送信機と受信機の役割の可能な逆転の可能性を排除するものではないということに留意すべきである。
【００１３】
本システムは、暗号化利用することによって選択的なマルチキャストを可能にする。送信機に関連付けされて、グループキーベースセットとアドレスキーベースセットを格納するキー格納手段が、送信機に配置されるか、あるいは送信機によりアクセス可能である。さらに、各受信機は、アクセス手段、すなわち、各受信機のキーセットにアクセスするため、格納又は受信を通じて受信機がキーにアクセスすることを可能にするのに適した手段を有する。受信機は、複数のグループのメンバーである。各受信機のキーセットは、一方では受信機アドレスキーセットを、他方では１以上のグループキーを有する。同一グループ内のすべての受信機は、同一のグループキーにアクセス可能であるが、異なる受信機アドレスキーセットを有することが可能である。各受信機アドレスキーセットは、送信機にアクセス可能なアドレスキーベースセットの一部である。
【００１４】
各受信機について、１以上の暗号キーが存在する。排除キーは、各受信機のキーセットには含まれていないアドレスキーベースセットからのキーである。排除キーによるメッセージの暗号化は、対応する受信機が当該メッセージを受信することを排除し、このためこの用語となっている。
【００１５】
本システムにおいて、さらに認証された及び／又は認証されていない受信機に関する認証情報を格納可能な認証格納手段が構成される。ここでの選択的マルチキャストについては、認証された受信機がメッセージを受信し、認証されていない受信機は当該メッセージを受信すべきでない。
【００１６】
選択的マルチキャストは、送信対象となるメッセージから複数の暗号化メッセージを生成するための暗号化手段を使用し、これらの暗号化メッセージを送信する送信することによって実行される。各暗号化メッセージは、キーの組み合わせにより暗号化される。これらのキーはＡＮＤ関係にあり、すなわち、組み合わせからのすべてのキーがわかっている場合に限って、メッセージが解読可能である。このような複数のキーによる暗号化方法の具体例が、さらに説明される。
【００１７】
各暗号化メッセージは、ターゲットとなる受信機グループを対象とする。１つのグループには複数のメッセージが存在する可能性があるが、各受信機グループについて１つのみの暗号化メッセージを有することが好ましい。ターゲットグループのメンバーのみが当該メッセージを受信することを保証するため（又は、より正確には、当該メッセージを解読し、平文を受信することが可能となることを保証するため）、適用されるキーの組み合わせは、少なくとも１つ、好ましくは、ターゲットグループのすべてのグループキーを含む。各グループ内において、認証された受信機のみが平文メッセージを受信することを保証するため、適用される組み合わせは、ターゲットグループ内の認証されていない受信機の排除キーを有する。
【００１８】
従って、本発明によるシステム及び方法は、複数のグループ内の多数の受信機にあるメッセージを選択的にマルチキャストすることを可能にする。使用される暗号化は、異なる暗号化メッセージのキーの組み合わせの注意深い選択によって、認証された受信機のみがメッセージを受信可能であることを保証する。好適な実施例に関して示されるように、これは大変効果的な解決手段であり、選択的なマルチキャストに必要な帯域幅を最小限にすることを可能にし、格納及び計算要求に関して受信機側の要求を抑える。
【００１９】
本発明によるブロードキャストシステムでは、選択的マルチキャストのための上記システム及び方法が、スクランブリングキーを選択的に送信するのに利用される。スクランブリングキーは、その後に、スクランブリングキーにアクセス可能な受信機によってスクランブル解除可能なコンテンツメッセージをスクランブル化するのに使用される。ここでは、「スクランブル処理」という用語は、暗号化の一種に関するものであり、好ましくは、ブロック暗号化である。「スクランブル処理」という用語は、ここでは、上述されたマルチキャストメッセージの暗号化とコンテンツメッセージのスクランブル処理を区別するため、「暗号化」の代わりに使用される。
【００２０】
本発明が広範な用途に適用可能であるということに留意すべきである。送信機から受信機への送信のために使用されるチャネルは、任意のタイプの送信方法及び／又は媒体とすることが可能である。また実際的には、キーを用いてデータを暗号化する任意の暗号化方法が利用可能である。これは、具体的には、対称及び非対称暗号化方法の両方の使用を意味する。対称暗号化方法は、暗号化と解読に同一のキーを使用するものであり、非対称暗号化方法では、「キー」は、実際には１つのキー部分（通常は、「公開」鍵と呼ばれる）が暗号化に使用され、他方（「秘密鍵」）が解読に使用されるキーペアである。何れのタイプの方法も、本発明によるシステムにおいて使用可能である。本システムはまた、特定の個数の受信機に限定されるものではない。明らかに、本システムの効果は、例えば、１，０００以上などの多数の受信機を有するシステムにおいてより明白となる。
【００２１】
本発明の好適な実施例によると、異なるグループの受信機に属し、同一の複数の受信機アドレスキーセットが存在する。これは、送信機に格納される必要があるアドレスベースキーの個数を限定する。同一の受信機アドレスキーセットを有する受信機を有することは、受信機が異なるグループに属しているため、選択性を排除するものではない。いくつかの同一の受信機アドレスキーセットが存在するだけでなく、複数のグループのすべての受信機、より好ましくは、過半数のグループのすべての受信機、そして最も好ましくはすべてのグループのすべての受信機でさえ同一の受信機アドレスキーセットを有することがさらに好ましい。一方ではこれは、システムにおける暗号鍵の合計数を大きく低減するが、また、さらなる効果として複数のグループからの１以上の受信機によって解読可能な１つの暗号化メッセージを送信可能であるということを提供する。上述されたように、キーの組み合わせによる暗号化は、当該キーの組み合わせのすべてがメッセージを解読するのに必要となるように実行される。従って、キーがＡＮＤ形式により結合される暗号化を実現するため異なる可能性が存在する。１つの可能な方法は、ある組み合わせのキーから暗号鍵を生成すること、すなわち、キーに対して数学的演算を使用することによって行われる。例えば、２進数として表すことが可能な２つのキーが、合成キーを取得するのに排他的論理和が実行されてもよい。合成キーによる暗号化は、一般には両方のオリジナルキーが知られている場合に限って可逆となるであろう。
【００２２】
しかしながら、複数のキーによる暗号化を再帰的暗号化として実現することが好ましい。この再帰的暗号化は、ここではまた「キー連鎖化」とも呼ばれ、第１暗号化データを取得するため第１キーによりデータを暗号化し、第２暗号化データを取得するため第２キーをさらに使用して第１暗号化データを暗号化し、同様に続けられることに関する。明らかに、いくつかのキーによる再帰的暗号化後の最終的に取得される結果は、同一のキーによる再帰的解読後にのみ読み取ることが可能である（一般には、順序が重要である場合には、逆の順序により）。再帰的に暗号化されたデータを読み取るため、再帰的暗号化処理に使用されるキーの完全な組み合わせが、受信機に利用可能であることが必要とされる。
【００２３】
本発明のさらなる展開によると、本システムは、アドレスキーのベースを生成するアドレスキー生成手段を有する。本システムはさらに、生成されたアドレスキーを受信機に選択的に送信する選択的キー送信手段を有する。このとき、受信機のアクセス手段は、送信したアドレスキーを受信する受信手段を有する。これは、限られた個数のメッセージについてのみ使用される一時的なアドレスキーを使用することを可能にする。実際、アドレスキーは、例えば、１０未満の少数のメッセージの送信にのみ使用されることが好ましい。アドレスキーの頻繁な変更は、各アドレスキーを交換する受信機の連携によって、システムの攻撃に対する影響を最小限にする。
【００２４】
新たに生成されたアドレスキーの選択的な提供のため、選択ベースキーセットに構成されるさらなる暗号キーセットを使用することが好ましい。選択ベースキーセットの一部である対応する受信機選択キーセットは、好ましくは、各受信機に格納される。同一グループの受信機の選択キーは、互いにペアにより含まれてはいない。しかしながら、異なるグループの受信機の受信機選択キーセットが同一であることが好ましい。これは、好ましくは、複数のグループ、又は過半数のグループ及び最も好ましくはすべてのグループのすべての受信機に対するケースである。上述したキー配布を利用して、選択キーの組み合わせによって送信される受信機アドレスキーを暗号化することによって、選択的なキー送信を実現することが可能である。ここでは、同一の受信機選択キーセットを有する受信機は、同一のアドレスキーセットを受信する。本発明によるシステム及び方法について重要な問題は、選択されたキーの発行スキーム、すなわち、受信機間のグループキー、アドレスキー及び／又は選択キーの配布である。好適な実施例を参照してさらに説明されるように、好適な具体的発行スキームは２つあり、１つは中規模（約１００〜１００，０００の受信機数）シナリオと、他方は大規模（１０，００以上、好ましくは、１００，０００以上の受信機数）シナリオである。
【００２５】
中規模シナリオに良好に適した第１の好適な発行スキームでは、各受信機に対して１つのみの排除キーが存在する。この排除キーは、排除キーの「所有者」、すなわち、当該キーを使用して排除可能な受信機を除いて、同一のグループのすべての受信機の受信機アドレスキーセットに含まれる。従って、特定の受信機の排除キーによるメッセージの暗号化は、排除された受信機を除いて、当該グループのすべての受信機がメッセージを解読することを可能にする。同様に、上述したＡＮＤ形式による排他キーの組み合わせによる暗号化は、排除された受信機を除いて、グループのすべての受信機がメッセージを解読することを可能にする。好適な大変効率的な発行スキームでは、整数ベーシス数ｂと次元数ｄが選択される。ベーシスｂは２以上であり、典型的には、１６以下である。次元数ｄは１以上であり、典型的には２〜２０の範囲内である。ｂとｄの選択に関する詳細が、好適な実施例に関して説明される。各グループは、最大ｂｄまでの受信機を有する。もちろん、おそらく最後の１つを除いてグループは充填されていることが好ましい。ｂ＊ｄ個の選択キーが存在し、そのうち、各受信機セットは、（ｂ−１）＊ｄ個を有する。これら（ｂ−１）＊ｄ個の選択キーは、ベーシスｂに対する記数法により受信機番号ｒを表し、当該表現の各桁について、ｂ個の所定の選択キーの１つを割り当てることによって決定される。この発行スキームは、大変シンプルかつ数学的に正確に、同一グループ内の異なる受信機の受信機選択キーセットが少なくとも１つの選択キーだけ異なることを保証する。
【００２６】
中規模シナリオ発行スキームについては、アドレスベースキーセットは、ｂｄ個のアドレスキー、すなわち、グループの受信機と同程度の個数のアドレスキーを有することがさらに好ましい。上述した選択キー発行スキームを利用して、好適なアドレスキー配布は、各アドレスキーをｄ回だけ送信することによって実現可能であり、各回毎に、選択キーの送信組み合わせのうちの１つにより暗号化される。この送信組み合わせは、再びベーシスｂに対する番号システムによる記号表現に従って選択される。上述した選択キー発行スキームと共に、これは、各受信機がそれの排除キーとなる１つを除いて、すべてのアドレスキーを受信することを保証する。大規模シナリオの他の発行スキームでは、グループの各受信機について少なくとも２つの排除キーが存在する。排除キーの各組み合わせは、当該グループ内では一意的である。これは、グループ内の認証されていない受信機を正確に排除することを可能にする。さらに、グループは複数のサブグループに分割されていることが好ましい。これに応じて、アドレスキーは、第１アドレスキーと第２アドレスキーに分割される。同一のサブグループの受信機は、同一の第１アドレスキーであるが、異なる第２アドレスキーセットを有する。このさらなる分割は、グループ内の受信機の擬似的な２次元アドレッシングを可能にする。第１アドレスキーがサブグループをアドレス指定し、第２アドレスキーがサブグループ内の各受信機をアドレス指定する第１及び第２アドレスキーを利用することによって、合計のアドレスキー数を大きく低減することができる。
【００２７】
大規模シナリオ発行スキームのさらなる進展に従って、各サブグループについて１つのサブグループ排除キーと、サブグループ内の各受信機について、１つのポジション排除キーが存在する。再び、ポジション排除キーという用語は、各受信機のキーセット（第２アドレスキー）と各サブグループのキーセット（第１アドレスキー）を表し、対応する受信機／サブグループキーセットに含まれないが、残りの受信機／サブグループキーセットに含まれるキーを指定する。グループ内の認証されていない受信機の排除のため、認証されていない受信機のポジション排除キーとサブグループ排除キーから排除キーが計算される。従って、排除キーは、各受信機のサブグループとポジション排除キーの数学的な組み合わせである。これは、１つの受信機を正確かつ安全に排除することを可能にする。対応する排除キーペアの使用は、それのグループ内の当該受信機の２次元アドレッシングとしてみなすことが可能である。
【００２８】
好ましくは、サブグループ排除キーとポジション排除キーの数学的な組み合わせが、再帰的冪乗により、すなわち、２つの排除キーの１つによるベースの冪乗を計算し、さらに他方の排除キーによる結果の冪乗によって計算される。好適な実施例の説明において明らかになるように、これは、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎキー確立処理に対応する。特別な状況下では、すなわち、各排除キーによる冪乗の各結果がわかっている場合、このタイプの排除キーの組み合わせは、２つの排除キーの１つのみがわかっている場合には逆転されてもよい（すなわち、メッセージが解読される）。この方法は、メッセージを依然として解読することができるように、ポジション排除キー又はサブグループ排除キーを知ることが十分となるように、効果的にＯＲ関係を実現する。この結果、どちらも保持しない認証されていない受信機のみが、メッセージを解読することが不可となる。
【００２９】
大規模シナリオ発行スキームでは、整数ベーシス数ｂと整数次元数ｄを選択することが好ましい。ｂは２以上であり、典型的には、１６以下である。ｄは１以上であり、典型的には２〜２０の範囲内である。各グループは、最大でｂ２ｄまでの受信機を有し、各々がｂｄまでの受信機を有するｂｄ個のサブグループに分割される。ここで再び、サブグループとグループ（最後の１つを除いて）は、最大数まで充填されていることが好ましい。選択ベースキーセットは、ｂ＊ｄ個の第１選択キーとｂ＊ｄ個の第２選択キーとを有し、そのうち各受信機は、（ｂ−１）＊ｄ個の第１選択キーと（ｂ−１）＊ｄ個の第２選択キーとを保持する２＊ｂ＊ｄ個の選択キーを有する。中規模シナリオ発行スキームに関して上述したように、各受信機に与えられるキーの組み合わせは、ベーシスｂに対する番号システムによる受信機番号ｒの表現に従って決定される。さらなる進展では、ｂｄ個の第１アドレスキーとｂｄ個の第２アドレスキーを有するアドレスベースキーセットが使用される。これらアドレスキーのそれぞれは、各回ごとに選択キーの送信組み合わせからの異なる１つにより暗号化され、ｄ回だけ送信される。中規模シナリオ発行スキームに関して上述されたように、送信組み合わせは、バーシスｂに対する番号システムによるキー番号ｔの表現に従って選択される。これは、グループ内のすべての受信機について１つのサブグループ排除キーと１つのポジション排除キーが存在する上述したアドレスキー発行スキームを保証する。上述したように、各受信機が各自の受信機キーセットにアクセスすることを可能にする本発明によるアクセス手段は、受信機に配置される格納手段として実現される必要はない。代わりに、上述したように、アドレスキー自体が送信機から受信機に選択的に送信されることが好ましい。まずアドレスキーを送信し、その後暗号化されたメッセージを送信することが可能であるが、まず暗号化されたメッセージを送信し、その後に対応するアドレスキーを送信することが好ましい。暗号化されたメッセージが極めて短く、多数のビットを有しない場合（例えば、マルチキャストキーのみが送信される場合）、受信機が暗号化されたメッセージから１つを格納し（受信機のグループを対象とする１つのメッセージ）、その後に、対応するアドレスキーを受信し、それらを格納することなく解読中に使用することがより簡単である。
【００３０】
以下において、本発明の実施例が、図面を参照して説明される。
【発明を実施するための最良の形態】
【００３１】
図１は、本発明の実施例による基本的なブロードキャストシステム１０を示す。システム１０は、送信機Ｓと、一例として、いくつかの受信機Ｒ０、Ｒ１、Ｒ８及びＲ９とを有する。送信機Ｓは、チャネルＣを介し受信機Ｒ０、Ｒ１、Ｒ８及びＲ９のそれぞれに接続される。本例のチャネルＣは、送信機から受信機への一方向の通信のみを可能にする。当該チャネルは、送信機Ｓから送信されるデータが受信機Ｒ０、Ｒ１、Ｒ８及びＲ９のそれぞれにおいて受信可能であるようなものである。システム１０は一般的な例であり、当該チャネルＣは、無線ブロードキャスト、コンピュータネットワークなどにおけるデータ送信などの任意のタイプの媒体及び送信方法を含むことが可能である。
【００３２】
コンテンツソース（図示せず）は、コンテンツデータＦ１，Ｆ２，Ｆ３，．．．をブロードキャスト送信機Ｓに連続的に配信する。送信機Ｓは、マルチキャストキー生成装置（図示せず）によって連続的に配信される複数のスクランブリングキー（マルチキャストキー）ｍ１，ｍ２，ｍ３，．．．を使用してコンテンツデータをスクランブル化されたコンテンツデータ１２にスクランブル処理するスクランブル処理ユニット（図示せず）を有する。ブロードキャスト送信機Ｓは、このスクランブル化されたコンテンツデータを連続的にブロードキャストする。他方、受信機Ｒ０、Ｒ１、Ｒ８及びＲ９のそれぞれは、後述されるように、スクランブル解除ユニット及びマルチキャストキーストレージとを有する。
【００３３】
スクランブル化及びスクランブル解除処理について、一般に任意のタイプの暗号化方法が利用可能である。高速のブロック暗号化を利用することが好ましい。以下で説明される例では、１２８ビットの等しいサイズのキーサイズとブロックサイズを仮定する。ブロードキャストシステム１０は、例えば、テレビコンテンツがスクランブル化された形式により連続的にブロードキャストされ、加入者ユーザ（認証された受信機）のみがコンテンツを視聴することが可能であるべき有料テレビシステムとすることが可能である。システムは、例えば、ペイ・パー・ビューが可能となるように動的性が高いものとなるように構成される。従って、スクランブリングキー（マルチキャストキー）は、例えば、毎分などかなり頻繁に変更される。
【００３４】
配信された実際のテレビコンテンツデータＦ１，Ｆ２，Ｆ３，．．．は、異なる時点において有効なマルチキャストキーを使用して連続的にスクランブル化される。
【００３５】
ブロードキャスト送信機Ｓｂのスクランブル化されたブロードキャストとパラレルに、送信機Ｓは、任意の与えられた時点において有効なマルチキャストキーを認証されている受信機に連続的に配布する。
【００３６】
図２は、図１の送信機Ｓの記号表示を示す。送信機は、コンテンツデータＦ１，Ｆ２，Ｆ３を受信する処理ユニット１４を有する。処理ユニット１４は、当該データをスクランブル化し、それをチャネルＣを介して、無線送信機やコンピュータネットワークインタフェースなどの任意のタイプのブロードキャスト送信機とすることが可能な送信手段１６によりブロードキャストする。処理ユニットはまた、マルチキャストキーを生成及び配布する。図３は、記号表示による包括的な受信機Ｒを示す。受信機Ｒは、チャネルＣを介しデータを受信する受信手段２６を有する。受信したデータは、処理ユニット３６において処理される。
【００３７】
送信機と受信機の両方の処理ユニットの具体的構成は、具体的な実施例に依存する。後述されるように、図２ａ及び３ａは、第１実施例による処理ユニットの詳細を示し、図２ｂ及び３ｂは、第２実施例による処理ユニットの詳細を示す。
【００３８】
送信機Ｓにおいて、認証された受信機と認証されていない受信機について、認証情報が利用可能である。以下において、送信機Ｓの処理ユニット１４は、認証されている受信機Ｒの処理ユニット３６がデータを解読可能であるが、認証されていない受信機は当該データを解読不可となるように、コンテンツデータＦ１，Ｆ２，Ｆ３，．．．を暗号化する。
［第１実施例］
本発明の第１実施例は、約１００〜１００，０００までの受信機を有する中規模シナリオ向けのものである。図４において、対応するシステムの基本的構成が示される。受信機は、グループＧ０，Ｇ１，．．．に分割される。各受信機は、関連するキーメモリ５０を有する。送信機は、グループキーメモリ５２と選択キーメモリ５４とを有する。
【００３９】
使用される実際の暗号化アルゴリズムは、ここではさらには説明されない。本発明の実施例では、当業者に知られている実質的にすべての暗号化アルゴリズムが利用可能である。ここでは、以下のように暗号化及び解読処理を一般的にしか定義しない。
【００４０】
暗号化
Ｅｎｃ（Ｋ，Ｍ）＝Ｃ
解読
Ｄｅｃ（Ｋ，Ｃ）＝Ｍ
グループキーメモリ５２は、グループキーＧＫ１，ＧＫ２，ＧＫ３，．．．を有する。グループキーは、暗号化された送信を特定のグループを対象とするのに使用される。各グループに単一の一意的なグループキーを割り当てることが可能であるが、図４に示されるように、グループキーメモリ５２はグループキーベースセットを有し、各グループのメンバーはこれらのグループキーの同一かつ一意的な組み合わせを保持することが好ましい。例えば、図４において、グループＧ０のすべてのメンバーがグループキーＧＫ１とＧＫ２を保持し、Ｇ１のすべてのメンバーがＧＫ１とＧＫ３を保持する。従って、例えば、ＧＫ１とＧＫ２の両方により再帰的に暗号化されたメッセージは、グループＧ０のメンバーによってのみ解読可能である。
【００４１】
送信機Ｓの選択キーストレージ５４に格納されている選択キーは、選択キーベースセットＳＫ０，ＳＫ１，．．．，ＳＫ５を構成する。各グループＧ０とＧ１内において、各受信機は、３つの選択キーの一意的組み合わせを保持する。しかしながら、異なるグループの受信機によって保持される選択キーの組み合わせは同一であり、すなわち、第１グループＧ０の第１メンバーである第１受信機Ｒ０は、グループＧ１からの第１受信機Ｒ８及び何れかさらなるグループからの第１受信機と同一の選択キーセットを保持する。
【００４２】
一般に、合計Ｎ個の受信機に対するマルチキャストシステムを確立するため、整数ｂとｄが選択される。ただし、ｂ（≧２）はベーシス数であり、ｄ（≧１）は次元数である。受信機は、サイズｂｄのグループにグループ化される。当該グループ内の選択キーの発行スキーム（すなわち、何れの受信機が、何れのキーの組み合わせにアクセス可能であるか）は、ベーシスｂに対する番号システムによる受信機番号の表現に従って決定される。発行スキームの数学的定義について、以下の定義を使用する。
【００４３】
すなわち、Ｎ及びＮ０をそれぞれ０を含む、又は含まない自然数の集合とする。集合Ｓについて、Ｐ（Ｓ）を冪集合（Ｓのすべての部分集合の集合）とする。Ｎ０からＰ（Ｎ）へのマッピングを以下のように定義する。
【００４４】
ｆＧ：辞書式順序によりサイズｇのＮのすべての部分集合をリストする（ただし、各集合は、降順に読まれる）。例えば、ｇ＝２について、リスト｛１，２｝，｛１，３｝，｛２，３｝，｛１，４｝，｛２，４｝，｛３，４｝，｛１，５｝，．．．が生成される。これは、マッピングｆＧ：Ｎ０→Ｐ（Ｎ）を定義する（この例では、ｆＧ（０）＝｛１，２｝，ｆＧ（１）＝｛１，３｝，．．．など）。
【００４５】
ｄｉｇｉｔｉ（ｎ）：ｎ（≧０）をベーシスｂに対する番号システムにより提供されるものとし、ｄｉｇｉｔｉ（ｎ）をｉ番目の桁を示すものとする（０から始まった左からカウントされる）。例えば、ｂ＝３について、ｄｉｇｉｔ２（１５）＝１であり、ｄｉｇｉｔ３（１５）＝０である。すなわち、
【００４６】
【数１】
2007538454.tif 000003
となる。（ただし、％はモジュロー演算を示し、
【００４７】
【数２】
2007538454.tif 000004
は整数の切り捨てである。）
ｆＳ：ｆＳ（ｎ）を
【００４８】
【数３】
2007538454.tif 000005
とする。
【００４９】
【数４】
2007538454.tif 000006
を
【００５０】
【数５】
2007538454.tif 000007
とする。（ただし、＼は、集合の差分演算を示す。）
ｆＧは、単射（構成上）であり、ｆＳと
【００５１】
【数６】
2007538454.tif 000008
の両方は、｛０，．．．，ｂｄ−１｝からＰ（｛１，．．．，ｂｄ｝）の単射写像であることに留意されたい。
【００５２】
これらの定義を使用して、発行スキームが定義可能となる。０からＮ−１までのインデックスｎが受信機に一意的に割り当てられると仮定すると、キー発行スキームは、以下のルールにより記述される。
【００５３】
インデックスｎを有する受信機は、
【００５４】
【数７】
2007538454.tif 000009
によるすべてのグループキーＧＫｉと、
【００５５】
【数８】
2007538454.tif 000010
によるすべての選択キーＳＫｉを取得する。
【００５６】
受信機に関する認証情報は、システムのすべての受信機に対するエントリを含む加入ベクトルにより要約される。ここでは、エントリは、認証されていない受信機については「０」、認証されている受信機については「１」とされる。
【００５７】
上述したような選択及びグループキー発行スキームによるシステムでは、メッセージ（この場合には、マルチキャストキーｍ１，ｍ２，ｍ３，．．．のコピー）が、以下のアルゴリズムを使用することによってすべての認証されている受信機に送信される。任意の加入ベクトル
【００５８】
【数９】
2007538454.tif 000011
が与えられると、以下のようにｍビットマルチキャストキーｍｋの情報が送信される。（ただし、すべての「送信」は、オープンなチャネルを介したブロードキャストを表す。）
１．ｊｏｉｎ０，ｊｏｉｎ１，．．．，ｊｏｉｎＮ−１の送信
２．ｂｄ個のランダムｍビットシーケンスＺ０，．．．，Ｚｂｄ−１の生成
３．
【００５９】
【数１０】
2007538454.tif 000012
４．
【００６０】
【数１１】
2007538454.tif 000013
このアルゴリズムは、ユーザをサイズｂｄのグループに分割することに基づく。受信機に永続的に格納されているグループキーＧＫと選択キーＳＫについてさらに、一時的なアドレスキーとして機能するランダムビットシーケンスＺが、暗号化のため使用される。マルチキャストキーのコピーは、グループのすべての非加入ユーザについて排除キーによるビット単位の排他的論理和の後であって、当該結果をすべての対応するグループキーにより暗号化した後、各グループについて個別に送信される。アドレスキーＺｊはｄ回送信され、各回毎にベーシスｂに対する番号システムによるｊの桁に従って選択キーの１つにより暗号化される。
【００６１】
インデックスｎを有する受信機は、ｊｏｉｎｎ＝１である場合、かつその場合に限ってブロードキャストされたストリームからｍｋを再構成する可能となるであろう。
【００６２】
図２ａは、送信機Ｓにおける処理ユニット１４の対応する構成を示す。マルチキャストキー生成装置２０は、マルチキャストキーｍ１，ｍ２，ｍ３，．．．を連続的に生成する。コンテンツデータＦ１，Ｆ２，Ｆ３，．．．は、異なる時点において有効なマルチキャストキーを使用してスクランブル処理ユニット２２においてスクランブル化される。スクランブル化されたコンテンツフィーチャ（ｃｏｎｔｅｎｔ  ｆｅａｔｕｒｅ）Ｆ１＊，Ｆ２＊，Ｆ３＊，．．．がブロードキャストされる。これとパラレルに、認証ストレージ手段３０から配信される加入情報に従って、マルチキャストキーｍ１，ｍ２，ｍ３，．．．が暗号化ユニット２４により暗号化される。暗号化されたマルチキャストキーｍ１＊，ｍ２＊，ｍ３＊，．．．がブロードキャストされる。
【００６３】
暗号化ユニット２４は、暗号化のため、グループキーＧＫ０，ＧＫ１，．．．と、マルチキャストキーの各暗号化のためアドレスキー生成装置２６により新たに生成されるアドレスキーＺ０，Ｚ１，．．．を使用する。アドレスキーＺ０，Ｚ１，．．．は、１２８ビットなどのマルチキャストキーと同じ長さのランダムビットシーケンスである。これらのアドレスキーは、選択キーストレージ５４から配信される選択キーＳＫ０，ＳＫ１，．．．によりキー暗号化ユニット２８によって暗号化される。暗号化されたアドレスキーＺ０＊，Ｚ１＊，．．．がブロードキャストされる。
【００６４】
受信機側では、ブロードキャストされたデータが受信され、認証された受信機は、それからコンテンツデータ情報Ｆ１，Ｆ２，Ｆ３，．．．を抽出する。図３ａにおいて、受信機Ｒの処理ユニット３６の対応する構成が示される。受信した暗号化されたアドレスキーＺ０＊，Ｚ１＊，．．．は、選択キーストレージ５０から配信される利用可能な選択キーＳＫ０，ＳＫ１，．．．を使用して、キー解読ユニット４２において解読される。解読されたアドレスキーＺ０，Ｚ１，．．．は、暗号化されたマルチキャストキーｍ１＊，ｍ２＊，ｍ３＊，．．．を解読するため、マルチキャストキー解読ユニット４０において使用される。解読されたマルチキャストキーｍ１，ｍ２，ｍ３，．．．が、スクランブル化されたコンテンツデータＦ１＊，Ｆ２＊，Ｆ３＊，．．．をスクランブル解除し、平文のコンテンツデータＦ１，Ｆ２，Ｆ３，．．．を取得するため、スクランブル解除ユニット４４において使用される。
【００６５】
受信機側における加入情報、暗号化されたアドレスキー及び暗号化されたマルチキャストキーの受信及び解読は、以下のアルゴリズムに従って実行される。
【００６６】
【数１２】
2007538454.tif 000014
ステップ２及び３において、受信機のグループｈに関する情報が、データストリームからフィルタリングされる。ステップ４は、グループキーによる暗号化を逆転し、ステップ５において、すべての非加入グループメンバーについて、ランダムビットシーケンスが復元及び減算される。この結果が、元のマルチキャストキーとなる。
【００６７】
ｊｏｉｎｎ＝０を有する受信機は、すべての適合する選択キーを有していないため、ｓ＝ｎ％ｂｄによりＺＳを復元する可能性を有しない（暗号を攻撃することを除いて）。非加入の受信機ｎについて、当該メッセージは、排除キーとして機能するランダムビットシーケンスＺＳ（ＸＯＲによる与えられた単なる実現では）により再帰的に暗号化されるため、排除された受信機は、自らのグループに対応する送信から、マルチキャストキーｍｋに関する情報を取得することができなくなる。他のすべてのグループについて、グループキーの少なくとも１つが当該受信機はなく、このため、情報を取得することも不可能となる。
【００６８】
選択的なマルチキャストを実行するため、マルチキャストキーの暗号化及び解読の一般的構成が説明された後、図５〜１３ａ及び１３ｂを参照して、第１実施例の具体的実施例が説明される。
【００６９】
以下の例において、システムのパラメータは、ベーシスｂ＝２と次元ｄ＝３となるよう選択される。各グループはｂｄ（８）のメンバーを有しているため、合計２４個の受信機を有する最初の３つのグループのみを考える。システムの動作を明示することが可能となるように、少数の受信機のみを有するよう本例は意図的に選択されているということに留意すべきである。本発明の実際的な実現では、受信機の個数は一般により多くなるであろう。内部パラメータの選択が、以下において説明される。図６のテーブルにおいて、２４このすべての受信機に対する選択キーとグループキーによる発行スキームが、与えられる。上述されたように、３つのグループのそれぞれの内部における選択キーの配布は同一である。
【００７０】
ベーシスｂは２に等しくなるよう選択されているため、各受信機番号（ポジションインデックス）は、選択キー発行スキームを決定するよう２重の表現（ベーシス２に対する番号システム）により記述されるようにしてもよい。図５に示されるように、二重の表現による受信機番号の各桁について、ちょうど１つの選択キーが「０」の値に割り当てられ、異なる者には「１」の値が割り当てられる。各グループの選択キーは、この表現法に従って配布されている。ここで、マルチキャストキーの各送信ステップについて、一時的なアドレスキーとして使用されるランダムビットシーケンスＺ０，．．．，Ｚ７が生成される。これらの一時的キーは、１つの送信についてのみ使用されることに留意すべきである。あるいは、複数の送信について一時的キーを使用することが可能であるかもしれない。
【００７１】
アドレスキーＺ０，．．．，Ｚ７が、上述した送信アルゴリズムのステップ４に従って受信機に送信される場合、これは、図８に示されるような暗号化されたパッケージの送信を導く。各アドレスキーはｄ回送信され（ここでは、ｄ＝３）、各回毎に、異なる選択キーＳＫにより暗号化される。インデックスｊを有するアドレスキーの暗号化のため、インデックスｊを有する受信機が保持していない選択キーのみが使用される。
【００７２】
図９は、説明される暗号化により実現されるアドレスキーの配布を示す。テーブルに示されているように、各グループの各受信機について、ちょうど１つの排除キーが存在する。例えば、排除キーＺ０は、Ｒ０がＺ０にアクセス不可であるグループ内の受信機のみであるため、受信機Ｒ０を排除するのに利用可能である。同じことが、Ｒ１及びＺ１などに適用される。
【００７３】
ここでは、上で与えられた送信及び受信アルゴリズムによる実現では、図９のテーブルは受信機のキーストレージではなく、アルゴリズムの実行中における受信機の各アドレスキーへのアクセス性を反映している。それは他の実施例においても存在可能であるが、上に与えられた送信及び受信アルゴリズムは、受信機におけるアドレスキーの格納を含むものではない。代わりに、当業者が理解するように、アドレスキーは、解読中の使用のため「ちょうど（ｊｕｓｔ  ｉｎ  ｔｉｍｅ）」受信され、格納される必要はなく、受信機側における格納要求をさらに最小化する。
【００７４】
本例において、図１０に示されるような加入ベクトル６０を仮定する。各受信機に続く「１」と「０」のエントリは、何れの受信機がマルチキャストキーを受信することが許可されているかを反映している。例えば、グループ０において、受信機Ｒ０、Ｒ１、Ｒ５、Ｒ６及びＲ７は、マルチキャストキーを受信することが認められているが、Ｒ２、Ｒ３及びＲ４は認められていない。
【００７５】
ここで、暗号化中に（送信アルゴリズムのステップ３）、マルチキャストキーｍｋの暗号化されたものが計算される。ここで提起されている暗号化アルゴリズムは、アドレスキーによるシンプルなＸＯＲであるが、もちろん、より高度なアルゴリズムが利用されてもよい。各グループについて、マルチキャストキーが、認証されていない受信機の排除キーにより暗号化される。例えば、図１１ａは、暗号化に使用されるアドレスキーＺ２、Ｚ３及びＺ４（すなわち、認証されていない受信機Ｒ２、Ｒ３及びＲ４の排除キー）によるグループ０のマルチキャストキーｍｋの暗号化を示している。従って、図１１ｂ及び１１ｃは、それぞれグループ１及び２の暗号化されたマルチキャストキーを示す。このように再帰的に暗号化された各グループに対するマルチキャストキーは、最終的には当該グループのすべてのグループキーにより暗号化される。図１２ａ〜１２ｃは、それぞれグループ０、１及び２の対応する暗号化されたマルチキャストキーｍｋ＊を示す。
【００７６】
受信機における暗号化されたマルチキャストキーｍｋ＊の受信及び解読が、図１３ａ及び１３ｂを参照して示される。ここで、図１３ａは、受信機Ｒ０（加入ベクトル６０において「１」のエントリを有し、従って、マルチキャストキーを受信することが認められている）と、受信機Ｒ１２（加入ベクトル６０において「０」のエントリを有し、従って、マルチキャストキーを受信することが認められていない）における解読に対応する。
【００７７】
受信機Ｒ０は、図９に関して上述されたように、自らの排除キーＺ０を除く、それのグループの２つのグループキーＧＫ１とＧＫ２の両方とすべてのアドレスキーにアクセス可能である。従って、受信機Ｒ０は、第１暗号化マルチキャストキーパッケージｍｋ＊の暗号化に使用されるすべてのアドレスキーＺ２、Ｚ３及びＺ４にアクセス可能であり、ｍｋの平文を受信するようｍｋ＊を再帰的に解読することが可能である。しかしながら、受信機Ｒ０は、少なくとも１つのグループキー（ＧＫ３）を有していないため、残りのグループについて指定されたその他のｍｋ＊パッケージの何れも解読することができないことに留意すべきである。
【００７８】
図１３ｂに示されるように、受信機Ｒ１２は、所持していないグループキーＧＫ２のため、第１及び第３暗号化マルチキャストキーパッケージｍｋ＊を解読することはできない。しかしながら、受信機Ｒ１２はまた、再帰的暗号化が自らの排除キーＺ４を含んでいるため、第２パッケージｍｋ＊もまた解読することができない。
【００７９】
以下において、潜在的なユーザのユーザ数Ｎと、キー及びブロックサイズｍと、内部パラメータｇ（各受信機により所持されるグループキーの個数）、ｂ（ベーシス）及びｄ（次元）とに応じて、上記システムの動作に必要とされるリソースを参照する。
【００８０】
【数１３】
2007538454.tif 000015
「ブロードキャスト帯域幅」は、ブロードキャストされる必要があるビット数を与える。「ワークスペース」では、プロトコルに使用される変数のメモリ要求が与えられる。最後の２つの行は、非加入ユーザの比率を示すパラメータαを含む（従って、
【００８１】
【数１４】
2007538454.tif 000016
であり、すべてのユーザが加入している場合には、α＝０であり、ユーザの何れも加入していない場合には、α＝１となる）。ユーザ側の列では、最後の２つの行において、計算量に対するワーストケースの上限と期待値（すべてのユーザに対して平均化された）が与えられている。
【００８２】
提案されるプロトコルは、フリーパラメータ（ｂ，ｄ，ｇ）の調整に関してある程度の自由度を残している。これは、何れのリソース（計算要求、格納要素、帯域幅）が最適化されると仮定されるかに応じて、様々な方法により実行可能である。他の必須の決定は、加入ユーザのユーザ数Ｎが変化するとき、何れのパラメータが固定されたままにされるべきかである。潜在的なユーザ数の増加によりｂ、ｄ及びｇ（又はそれらの任意の部分集合）を増加するとき、これに応じて既存のユーザにより所持されるキーセットを更新する必要があることに留意されたい。しかしながら、ユーザのインデックスが適切な方法により再構成される場合、すべてのユーザが自らがすでに所持しているキーを維持可能であることを確認することが可能である。これと同様に、相対的に少数の増加したキーしか既存のユーザには取り扱われる必要がない。
【００８３】
第１実施例は、主として、他の理由のためアクセスポイント毎のユーザの最大数が制限されるシナリオ（例えば、無線モバイル装置に対するサービスなど）に関するものである。さらに、これらの状況では、個別の通信のためのコストは（すなわち、非ブロードキャストセキュアチャネルを介し）、比較的大きなものとみなされるべきである。これに加えて、装置側における計算能力及びメモリ消費に対する要求は、重要な要因である。
【００８４】
従って、ここでは、ユーザに発行されるベースキーの個数と帯域幅を同時に最適化するよう選択される固定的なパラメータｇ、ｄ及びｂを選択することが提案される。これと同様に、新たなユーザしか加入中にベースキーを受信する必要がないが、キー交換又は増加したキーの配信が、マルチキャストサービスの全期間において既存のユーザに対して行われる必要がある。
【００８５】
パラメータｇは、サーバ側に格納されるキーの個数とユーザ毎のベースキーの個数について反対方向の影響を与える（テーブル１の第１行を参照されたい）。サーバ側におけるメモリ消費は重大なものではないため（Ｎ＜１０６のため）、このパラメータは、可能な最小値であるｇ＝１に設定されるべきである。
【００８６】
ｂとｄの最適な選択は、自明なものではない。ユーザ毎のベースキーの個数に上限Ｋを与えると、すなわち、（ｂ−１）ｄ＋１≦Ｋの制約の下では、送信作業を最適化する、すなわち、
【００８７】
【数１５】
2007538454.tif 000017
を最小化する必要がある。
【００８８】
１０，０００から４０，０００までの潜在的なユーザのユーザ最大数ＮとＫ＝１２（各受信機のベースキー）について、上述した最適化問題に対する最適解は、ｂ＝４とｄ＝３であると求められる。ｇ＝１とｍ＝１２８と共にこれらの値を使用することは、以下の要求を導く（簡単化のため、Ｎは６４の倍数であると仮定する）。
【００８９】
【数１６】
2007538454.tif 000018
Ｎ＜２１６について、プロトコルは以下の性質による安全なマルチキャストを可能にすることを記載可能である。
・各ユーザについて１０個のベースキーが発行され、トータルで最大１，０３６個のベースキー
・装置側において極めて少数のフットプリント実現が可能であり、２００バイト見何のワーキングスペース（ベースキーを含む）であって、マルチキャストキーの確定毎に高々６５ブロックの解読が必要とされる。
・帯域幅要求：ブロードキャストチャネルを介し高々２７ｋｂのセキュアチャネルを介した各ユーザに対する１６０バイト（キー発行のため）
概略すると、提案されている内部パラメータの選択は、潜在的なユーザ毎に３ビットのブロードキャスト帯域幅の使用を導く。典型的なアプリケーションの具体例として、無線ＭＰ３ストリーミング（１２８ｋｂｉｔ／ｓ）を考える。２分ごとにマルチキャストキーを新たに確定するため、プロトコルにより生じるオーバヘッドは、アクセスポイント毎に最大で２１６の加入者について１．４％となる（従って、より少数のものについてはより小さくなる）。
【００９０】
以下において、マルチキャストシステム及び対応する発行スキームの実現の第２実施例が説明される。第２実施例による発行スキーム及びアルゴリズムは、１，０００個の以上の受信機、一般には１０，０００個以上の受信機が存在する大規模マルチキャストシナリオに関するものであり、好ましくは、受信機の個数は１００，０００以上となる。
【００９１】
当該アルゴリズムでは、周知のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎプロトコルが使用される。Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎプロトコルは、オープンチャネルを介した２人のユーザ間において暗号キーを当該キーを取得する可能性を他のユーザに残すことなく確定するため発明されたものである。それは、大きな素数ｐに対する有限フィールドに一般化されるシンプルな指数的規則
【００９２】
【数１７】
2007538454.tif 000019
に基づくものである。プロトコルのセキュリティは、離散的アルゴリズム（指数化モジュローｐへの逆関数）が大きなｐに対して計算的に困難である（トラップドア関数）という観察によるものである。すなわち、ａｂ（ｍｏｄ）ｐ、ａ及びｐがわかっているときでさえ、ｂに関する情報を取得することは実際的に不可能である。
【００９３】
２つのｍビットシーケンスを１つのｍビットシーケンスにマッピングする以下の関数Ｅｘｐ、
【００９４】
【数１８】
2007538454.tif 000020
の形式によるＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ原理を使用する。
【００９５】
ここで、ビットシーケンスＡとＢは、ある数のｐに対する法として読まれ、指数化の結果は、｛０，．．．，ｐ−１｝の数に還元され、ビットシーケンスとして解釈される。予め選択された数ｐは、本記載を通じて一定であると仮定される。それは、ｍを送信されるマルチキャストキーのビット数としたとき、２ｍよりやや小さい素数であるべきである（例えば、２ｍ−２ｍ／２から２ｍの間でランダムに選択される）。
【００９６】
指数的規則は、開示されたプロトコルにおいて以下に方法により使用されるＥｘｐ（Ｅｘｐ（Ａ，Ｂ），Ｃ）＝Ｅｘｐ（Ｅｘｐ（Ａ，Ｃ），Ｂ）を意味する。すなわち、Ｅｘｐ（Ａ，Ｂ）とＥｘｐ（Ａ，Ｃ）が公開されている場合、Ｂ又はＣを知っているユーザは、Ｅｘｐ（Ｅｘｐ（Ａ，Ｂ），Ｃ）を計算することが可能であるが、ＡもＢも知らないユーザは計算することができない。従って、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎプロトコルは、２つのキーの間のＯＲ関係を実現するのに利用可能である。
【００９７】
第２実施例では、当該プロトコルは、２つのタイプの発行されるベースキー、すなわち、グループキーＧＫ１，ＧＫ２，．．．と、ｂ・ｄ個の選択キーの２つの集合、ＳＫ１＿１，ＳＫ１＿２，．．．，ＳＫ１＿ｂ・ｄとＳＫ２＿１，ＳＫ２＿２，．．．，ＳＫ２＿ｂ・ｄを使用する。要求されるグループキーの個数ｇは、受信機の総数Ｎとグループ数に依存する。０からＮ−１までのインデックスが受信機に一意的に割り当てられると仮定すると、キー発行スキームは、以下の規則によって記述される。
【００９８】
インデックスｎのユーザは、
【００９９】
【数１９】
2007538454.tif 000021
のすべてのグループキーＧＫと、
【０１００】
【数２０】
2007538454.tif 000022
のすべての選択キーＳＫ１＿ｉと、
【０１０１】
【数２１】
2007538454.tif 000023
のすべての第２選択キーＳＫ２＿ｉを取得する。
【０１０２】
送信者側では、以下のアルゴリズムがデータを送信するのに使用される。
【０１０３】
【数２２】
2007538454.tif 000024
このアルゴリズムは、ユーザをサイズｂ２ｄのグループに分割することに基づく。各グループに対して、マルチキャストキーの再帰的に暗号化されたコピーが個別に送信され、グループの非加入ユーザに対応するすべてのｊとｋに対して、Ｅｘｐ（Ｅｘｐ（Ｂ，Ｘｊ），Ｙｋ）により暗号化され、またグループに属するすべてのグループキーにより暗号化される。ランダムビットシーケンス（アドレスキー）ＸｊとＹｊがｄ回送信され、各回毎に、ベーシスｂに対する番号システムにおけるｊの桁に従って選択キーＳＫ１ｋとＳＫ２ｋの１つにより暗号化される。指数Ｅｘｐ（Ｂ，Ｙｊ）とＥｘｐ（Ｂ，Ｙｊ）は、暗号化されることなく送信される。
【０１０４】
インデックスｎを有する受信機は、以下のアルゴリズムを使用することによって、ｊｏｉｎｎ＝１である場合、かつその場合に限って、ブロードキャストされたストリームからＭＫを再構成することが可能となる。
【０１０５】
【数２３】
2007538454.tif 000025
ステップ２及び３において、受信機グループｈに関する情報がデータストリームからフィルタリングされる。ステップ４は、グループキーによる暗号化をリバースしたものである。ステップ５において、Ｅｘｐ（Ｂ，Ｘｊ）とＥｘｐ（Ｂ，Ｙｊ）の値が読まれ、それぞれ２つのアレイＵｊ１とＵｊ２に格納される。また、ビットシーケンスＸｊとＹｊは、正しい選択キー（利用可能である場合）により解読することにより復元される。これらの結果は、Ｖｊ１とＶｊ２に格納される。最後にステップ６において、ビットシーケンスＥｘｐ（Ｅｘｐ（Ｂ，Ｘｊ），Ｙｋ）＝Ｅｘｐ（Ｅｘｐ（Ｂ，Ｙｋ），Ｘｊ）が、すべての非加入ユーザに対して復元され、元のマルチキャストキーを解読するのに使用される。
【０１０６】
図２ｂ及び３ｂは、送信機及び受信機側の処理ユニット１４及び３６の対応する構成を示す。この構成は大部分は第１実施例のもの（図２ａ及び３ａ）に対応しているため、第１実施例と第２実施例の相違点のみがさらに説明される。
【０１０７】
送信機側において、選択キーストレージ５４は、２つのタイプの選択キーベーシックセット、第１選択キーＳＫ１＿０，ＳＫ１＿１，．．．と第２選択キーＳＫ２＿０，ＳＫ２＿１，．．．を保持する。また、アドレスキー生成ユニット２６は、第１アドレスキーＸ０，Ｘ１，．．．と第２アドレスキーＹ０，Ｙ１，．．．の両方を生成する。
【０１０８】
キー暗号化ユニット２８は、第１選択キーＳＫ１＿０，ＳＫ１＿１，．．．により第１アドレスキーＸ０，Ｘ１，．．．を第１暗号化アドレスキーＸ０＊，Ｘ１＊，．．．として暗号化し、第２選択キーＳＫ２＿０，ＳＫ２＿１，．．．により第２アドレスキーＹ０，Ｙ１，．．．を第２暗号化アドレスキーＹ０＊，Ｙ１＊，．．．を暗号化する。キー暗号化ユニット２８はさらに、指数Ｚ０，Ｚ１，．．．をＥｘｐ（Ｂ，Ｙ０），Ｅｘｐ（Ｂ，Ｙ１），．．．と共にＥｘｐ（Ｂ，Ｘ０）、Ｅｘｐ（Ｂ，Ｘ１），．．．として計算し、それらをさらなる暗号化を行うことなく送信する。
【０１０９】
マルチキャストキー暗号化ユニット２４は、グループキーストレージ５２からのグループキーＧＫ０，ＧＫ１，．．．と、第１及び第２アドレスキーＸ０，Ｘ１，．．．，Ｙ０，Ｙ１，．．．の両方を使用して、暗号化マルチキャストキーｍ１＊，ｍ２＊，ｍ３＊，．．．を生成する。
【０１１０】
処理ユニット３６（図３ｂ）内の受信機側では、キー解読ユニット４２は、第１及び第２選択キーの両方を使用して、暗号化アドレスキーＸ０＊，Ｙ０＊，．．．を解読する。マルチキャストキー解読ユニット４０は、指数Ｚ０，Ｚ１，．．．，Ｅｘｐ（Ｘ０），．．．と第１及び第２アドレスキーＸ０，Ｙ０，．．．及びＺ０，Ｚ１，．．．を使用して、暗号化マルチキャストキーｍ１＊，ｍ２＊，ｍ３＊，．．．を解読する。
【０１１１】
以下において、図１４〜２３ｂを参照して、第２実施例の一例が詳細に説明される。
【０１１２】
本例では、内部パラメータは、ベーシスｂ＝２と次元ｄ＝２として選択される。これは、サイズｂ２ｄの２つのグループをもたらし、すなわち、各グループは、１６の受信機を有する。簡単化のため、本例では２つのグループしか着目しない。再び、大変少数の受信機しか有しないシンプルな例が、システムの動作を示すのに選択された。
【０１１３】
図１５ａ及び１５ｂのテーブルは、本例の３２個すべての受信機に対する選択キーの発行スキームを示す。再び、同一グループのすべてのメンバーは、同一のグループキーを保持している。受信機間における選択キーの配布は、すべてのグループについて同じである。ｂ２ｄのメンバーの各グループは、ｂｄのメンバーのｂｄ個のサブグループに分割される。選択キーには、サブグループをアドレス指定する第１選択キーＳＫ１と、サブグループ内の各受信機ポジションをアドレス指定する第２の選択キーＳＫ２の２つが存在する。この結果、同一のサブグループ内のすべての受信機が、同一の第１アドレスキーＳＫ１のセットを有する（例えば、サブグループ０のすべてのメンバーが、ＳＫ１＿０とＳＫ１＿１を所持し、これは、グループ０と１に適用される）。他方、各サブグループ内において、各受信機は、一意的な第２選択キーセットを有するが、第２選択キーの配布は、４つすべてのサブグループについて同じである（例えば、４つのサブグループのそれぞれの第２受信機は、再びすべてのグループに適用されるＳＫ２＿０とＳＫ２＿３を所持する）。
【０１１４】
再び、第１及び第２選択キーの配布が、ベーシスｂに対する番号システムによるサブグループインデックス（第１選択キーＳＫ１に対する）と、ポジションインデックス（第２選択キーＳＫ２に対する）の表現に従って決定される。図１４は、第１及び第２選択キーに対する二重の番号システムにおける桁の表現を与える。
【０１１５】
上述の送信者アルゴリズムのステップ２において、一時的なアドレスキーＸｉとＹｉが、ランダムなｍビットシーケンスとして生成される（ｍは、マルチキャストキーｍｋのビット数である）。ここで、Ｘｉは第１アドレスキーとして使用され、Ｙｊは第２アドレスキーとして使用される。さらに、ベースＢが、ランダムなｍビットシーケンスとしてランダムに決定される。
【０１１６】
指数Ｚ０，Ｚ１，Ｚ２，Ｚ３は、Ｅｘｐ（Ｂ，Ｙｉ）として計算され、指数Ｅｘｐ（Ｂ，Ｘｉ）と共に中間キーとして使用される。図１７に示されるこれらの値は、暗号化することなくブロードキャストされ、従って、すべての受信機についてアクセス可能である。
【０１１７】
ステップ４の第１部分では、各Ｘｉがｄ回送信され、各回毎に異なるＳＫ１により暗号化される。ここで、暗号化に使用される第１選択キーＳＫ１の組み合わせは、ベーシスＢに対する番号システムのサブグループインデックスの表現に従って決定される。従って、ステップ４の第２部分では、各第２アドレスキーＹｉはｄ回送信され、各回毎に異なるＳＫ２により暗号化され、ここでは、使用される第２選択キーＳＫ２の組み合わせは、ベーシスｂに対する番号システムにおけるポジションインデックスの表現に従って決定される。
【０１１８】
図１８において、上記配布アルゴリズムから得られるグループ０の受信期間のアドレスキーの配布が、与えられる。第１実施例と異なって、当該アルゴリズムは、受信機側におけるアドレスキーを一時的に格納することを含むことに留意すべきである。
【０１１９】
図１８に示されるように、グループ０からの受信機間への第１及び第２アドレスキーの配布は、各サブグループについて、当該サブグループのメンバーが所持しない第１アドレスキーからの１つのサブグループ排除キーが存在するようになされる（例えば、サブグループ０のすべてのメンバーはＸ０を所持しないが、他のすべての受信機は所持している）。また、各サブグループ内の各受信機について、各受信機が所持しないが、サブグループの他のすべてのメンバーが保持する第２アドレスキーから１つのポジション排除キーが存在する（例えば、各サブグループの第１メンバーＲ０，Ｒ４，Ｒ８，Ｒ１２はＹ０を所持しないが、他のすべての受信機は所持している）。
【０１２０】
以下において、図１９に示される加入ベクトル６２によるマルチキャストキーｍｋの暗号化が説明される。図２０において、グループ０に含まれる受信機がテーブルにリストされ、そこでは、同じ列のすべての受信機は同一のサブグループ排除キーを有し、同じ行のすべての受信機は同一のポジション排除キーを有している。例えば、受信機Ｒ１２は、Ｘ３及びＹ０は所持せず、すなわち、サブグループ排除キーＸ３とポジション排除キーＹ０とを有する。
【０１２１】
認証されていない受信機（本例では、Ｒ３，Ｒ６，Ｒ１１，Ｒ１２，Ｒ１３）の各排除キーペア（例えば、サブグループ／ポジション排除キーなど）から、送信アルゴリズムのステップ３において、数学的合成がＥｘｐ（Ｚｉ，Ｙｋ）として計算される。マルチキャストキーｍｋは、このように生成された合成キーを使用して再帰的に暗号化される。図２１は、グループ０に対して暗号化されるような対応する再帰的に暗号化されたマルチキャストキーｍｋを示す。このパッケージは、さらに暗号化パケットｍｋ＊を与えるため、グループ０のすべてのグループキーを使用して暗号化される。このタイプの対応するパケットが、各グループに対して決定される。
【０１２２】
以下において、認証された受信機Ｒ５（図２３ａ）と認証されていない受信機Ｒ１１（図２３ｂ）における暗号化されたマルチキャストキーｍｋ＊の解読が説明される。
【０１２３】
受信機Ｒ５は、グループ０のグループキーＧＫ１とＧＫ２を所持する。Ｒ５はさらに、それのサブグループ排除キーＸ１を除くすべての第１アドレスキーＸと、それのポジション排除キーＹ１を除くすべての第２アドレスキーＹを所持する。Ｒ５はさらに、すべての受信機と同様に、上述した指数（すべての第１アドレスキーＸと第２アドレスキーＹによるベースＢの指数の計算された結果）を所持する。
【０１２４】
この情報を使用して、受信機Ｒ５は、Ｚ０とＹ３からＥｘｐ（Ｚ０，Ｙ３）を、Ｚ１とＹ２からＥｘｐ（Ｚ１，Ｙ２）を、Ｚ２とＹ３からＥｘｐ（Ｚ２，Ｙ３）を、Ｚ３とＹ０からＥｘｐ（Ｚ３，Ｙ０）を計算することが可能である。
【０１２５】
しかしながら、Ｒ５はＹ１を所持していないため、それはＥｘｐ（Ｚ３，Ｙ１）を直接的には計算することはできない。しかしながら、Ｒ５はＸ３を所持しているため、それはＥｘｐ（Ｚ３，Ｙ１）をＥｘｐ（Ｅｘｐ（Ｂ，Ｙ１），Ｘ３）として計算することが可能である。従って、受信機Ｒ５は、必要なすべてのキーを取得することが可能であるため、ｍｋ＊を解読することが可能である。従って、受信機Ｒ５は、マルチキャストキーｍｋを取得することが可能である。
【０１２６】
図２３ｂを参照するに、受信機Ｒ１１はそれのグループキーＧＫ１とＧＫ２と、それのサブグループ排除キーＸ２とポジション排除キーＹ３を除くすべてのアドレスキーを所持する。Ｒ１１はさらに、利用可能なすべての指数を所持する。
【０１２７】
ｍｋ＊の生成中に使用されるキーから、Ｒ１１は、Ｚ１とＹ２からＥｘｐ（Ｚ１，Ｙ２）を、Ｚ３とＹ１からＥｘｐ（Ｚ３，Ｙ１）を、Ｚ３とＹ０からＥｘｐ（Ｚ３，Ｙ０）を計算することが可能である。
【０１２８】
Ｒ１１はまた、Ｙ３を所持していないが、Ｅｘｐ（Ｚ０，Ｙ３）を計算可能である。Ｒ１１はＸ０を所持しているため、Ｅｘｐ（Ｅｘｐ（Ｂ，Ｙ３），Ｘ０）を計算することが可能である。
【０１２９】
しかしながら、Ｒ１１は、Ｅｘｐ（Ｚ２，Ｙ３）を計算することはできない。一方では、Ｒ１１は、それのポジション排除キーＹ３を所持していない。他方では、Ｒ１１は、それのサブグループ排除キーＸ２を所持していない。この結果、Ｘ１１がＥｘｐ（Ｚ２，Ｙ３）を計算することはできない。従って、Ｒ１１は、ｍｋ＊を解読する１つのキーを欠いており、この結果、マルチキャストキーｍｋを取得することはできない。
【０１３０】
上述した実施例に対するいくつかの可能な変更が存在する。
【０１３１】
第１の変更は、両方の実施例の送信アルゴリズムのステップ１において、完全な加入ベクトルのブロードキャストを削除することである。その代わりに、加入ベクトルに対する変更のみが送信される。
【０１３２】
他の変更は、受信機が比較的低い帯域幅チャネルによってアクセスポイント（モデムなど）に接続されているインターネットなどのコンピュータネットワークなど、低速の「ラストマイル（ｌａｓｔ  ｍｉｌｅ）」による接続に関するものである。この場合、アクセスポイントは、ステップ２及び３のフィルタリングを実行し、低速なラストマイルチャネルを介しユーザに関連するｂ２ｄ＋ｍビットのみを送信することが可能である。
【０１３３】
以下において、ユーザ数ｎと、キー及びブロックサイズｍと、内部パラメータｇ、ｂ及びｄとに応じて計算の帯域幅、メモリ及び計算量に関する第２実施例の要求を参照する。
【０１３４】
【数２４】
2007538454.tif 000026
第１実施例と同様に、第２実施例もまた、利用可能なリソースに従ってフリーなパラメータ（ｂ，ｄ，ｇ）の調整に関するある程度の自由度を残している。第２実施例は、潜在的なユーザの数が膨大である（数百万から数十億）シナリオについて使用可能である。これらの状況では、サーバにより格納されるベースキーの個数が重要な要因となる（要求されるブロードキャスト帯域幅に加えて）。
【０１３５】
従って、ブロードキャスト帯域幅の漸近的に「良好な」動作の制約の下、ベースキーの合計を最適化することが提案されている。グループベースキーの合計数Ｇと、ユーザ毎のグループベースキーの個数ｇとは、以下の条件を満たしていることが必要である（なぜなら、
【０１３６】
【数２５】
2007538454.tif 000027
のグループが、グループベースキーセットのｇ個の要素のサブセットによって特定される必要があるためである）。
【０１３７】
【数２６】
2007538454.tif 000028
２項式の対称性により、ほぼ最適な選択はＧ＝２ｇとなる（いくつかのケースでは、最適解はＧ＝２ｇ−１であるが、簡単化のため、このケースは無視している）。ここで、ｇは、
【０１３８】
【数２７】
2007538454.tif 000029
を満足する最小の自然数である。スターリングの近似を利用して、これは、
【０１３９】
【数２８】
2007538454.tif 000030
を導く。
【０１４０】
このとき、ベースキーの合計は、ほぼｌｏｇ２Ｎ＋２ｄ（ｂ−ｌｏｇ２ｂ）となるため、ベースキー数と要求されるブロードキャスト帯域幅に関する適切なワーキングポイントの検出は、以下の問題を導く。すなわち、与えられたＮについて、２ｄ（ｂ−ｌｏｇ２ｂ）と、
【０１４１】
【数２９】
2007538454.tif 000031
を同時に最小化する。明らかに、同時に双方の式を最小化する（ｂ、ｄ）の選択はなく、このため、ブロードキャスト帯域幅とベースキー数との間にはトレードオフが存在する。異なるＮの値に対して、（ｂ、ｄ）に対する妥当な選択が容易に検出可能であるが、ここでは、可能性のある最善の漸近的動作による一般的な解を与えようとしている（しかしながら、ある特別なＮについては、次善的な選択であるかもしれない）。
【０１４２】
漸近的にベストなブロードキャスト帯域幅の使用は、
【０１４３】
【数３０】
2007538454.tif 000032
である場合に実現される。ベースキー数に対する式においてｄを１／３ｌｏｇｂＮに置き換えることにより、ｂ＝３の解を有する最小化問題
【０１４４】
【数３１】
2007538454.tif 000033
を導く。ｂを一定に保つと、最小のブロードキャスト帯域幅は、方程式
【０１４５】
【数３２】
2007538454.tif 000034
の解に対応する。ｂ＝３に対して、最適なｄを求めるための良好な経験に基づく方法は、以下の式により与えられる。
【０１４６】
【数３３】
2007538454.tif 000035
結果として得られる近似値を代入すると、
【０１４７】
【数３４】
2007538454.tif 000036
ｂ＝３とｄとなり、テーブル１において、以下のプロトコルの漸近的な動作を取得することができる。
【０１４８】
【数３５】
2007538454.tif 000037
一例として、ペイ・パー・ビューサービスの２億の加入者（Ｎ＝２・１０８）によるペイ・パー・ビューサービスに関して検討する。
【０１４９】
上に与えられたルールに従って、内部パラメータのベストな選択は、ｂ＝３，ｄ＝５，ｇ＝７である。マルチキャストキーとベースキーのキーサイズが、ｍ＝２５６ビットとなるよう選択されると仮定する。以下のテーブルでは、追加的な仮定α＝０．９５もまた含まれている。
【０１５０】
【数３６】
2007538454.tif 000038
さらなる例として、インターネットなどのコンピュータネットワークにおけるマルチキャストトラフィックを検討する。
【０１５１】
かなり大規模なシナリオに対して、潜在的なユーザ数、すなわち、最大限利用可能なＩＰアドレスの個数をＮ＝２３２とする。上述したルールは、ｂ＝３，ｄ＝６，ｇ＝８を示唆している。マルチキャストキーとベースキーのキーサイズは、ｍ＝２５６ビットに設定され、αは０．９９９に設定される（４３億人のユーザが、同じマルチキャストタイムスロットにおいて同一のコンテンツを購入しようとしていることを意味する）。このとき、要求リストは、以下のようになる。
【０１５２】
【数３７】
2007538454.tif 000039
最後の２つの行において、加入ユーザはグループにおいて統計的に良好に分散していると仮定することができるため、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ指数とブロック暗号化ステップの平均値が与えられる。ブロードキャスト帯域幅エントリでは、低速なラストマイルチャネルの場合において、ステップ２及び３のフィルタリングがアクセスポイントにおいて実行されるとき、上述した変更を利用するときの潜在的な効果が示される。
【０１５３】
上記具体例が示すように、提案されたプロトコルは、驚くほど少ないベースキーを使用して、比較的小さな帯域幅使用による膨大な数のユーザに対するマルチキャストサービスを可能にする（２５６ビットキーなど高いセキュリティレベルにおいて）。
【０１５４】
上記実施例では、スクランブル化されたコンテンツデータと暗号化されたマルチキャストキー情報の両方をブロードキャストする送信機はＳのみであると仮定されていた。同一のブロードキャストデータストリームにおいてこの情報を送信することが好ましいが、キー情報とスクランブル化されたコンテンツデータが、例えば、異なるチャネルを介し、又は異なる送信主体によって、実際には別々に送信される他の実施例もあるかもしれない。
【０１５５】
上記記載はブロードキャストシステム及び方法の具体例を示しているが、これらの具体例は、説明のためだけに選ばれたものであり、本発明の範囲を限定するものとして解釈されるべきではない。上記システム及び方法に対するいくつかの可能な変更及び拡張が存在する。例えば、中規模又は大規模シナリオについて与えられたユーザ範囲が好適な選択であるが、当業者は、これらのアルゴリズムが異なるサイズのシナリオについて利用可能であると理解するであろう。
【図面の簡単な説明】
【０１５６】
【図１】図１は、本発明によるブロードキャストシステムの実施例の概略図を示す。
【図２】図２は、図１に示されるシステムの送信機の概略図を示す。
【図２ａ】図２ａは、図２の送信機の処理ユニットの第１実施例の概略図を示す。
【図２ｂ】図２ｂは、図２の送信機の処理ユニットの第２実施例の概略図を示す。
【図３】図３は、処理ユニットを有する図１の受信機の概略図を示す。
【図３ａ】図３ａは、受信機の処理ユニットの第１実施例の概略図を示す。
【図３ｂ】図３ｂは、受信機の処理ユニットの第２実施例の概略図を示す。
【図４】図４は、図１のブロードキャストシステム内のキー配布システムを概略的に示す。
【図５】図５は、ベース２に対する番号システムにおける桁を表す選択キーを示すテーブルを示す。
【図６】図６は、発行スキームの第１実施例を示すテーブルを示す。
【図７】図７は、一時的なアドレスキーセットを示すテーブルを示す。
【図８】図８は、選択キーにより暗号化された一時的なアドレスキーを概略的に示す。
【図９】図９は、発行スキームの第１実施例によるアドレスキー配布によるテーブルを示す。
【図１０】図１０は、加入ベクトルを概略的に示す。
【図１１】図１１ａ〜ｃは、マルチキャストキーの暗号化されたものを概略的に示す。
【図１２】図１２ａ〜ｃは、マルチキャストキーを含む暗号化されたメッセージを概略的に示す。
【図１３】図１３ａ及びｂは、図１２ａ〜ｃの暗号化されたパッケージの２つの処理例を概略的に示す。
【図１４】図１４は、本発明の第２実施例によるベース２に対する番号システムにおける桁を表す選択キーによる２つのテーブルを示す。
【図１５ａ】図１５ａは、グループ及びサブグループを有する本発明の第２実施例による発行スキームを概略的に示す。
【図１５ｂ】図１５ｂは、グループ及びサブグループを有する本発明の第２実施例による発行スキームを概略的に示す。
【図１６ａ】図１６ａは、第１選択キーにより暗号化された第１中間キーを概略的に示す。
【図１６ｂ】図１６ｂは、第２選択キーにより暗号化された第２中間キーを概略的に示す。
【図１７】図１７は、補助キーを概略的に示す。
【図１８】図１８は、第２実施例によるアドレスキー配布によるテーブルを示す。
【図１９】図１９は、加入ベクトルを概略的に示す。
【図２０】図２０は、排除された受信機によるテーブルを示す。
【図２１】図２１は、暗号化マルチキャストキーを概略的に示す。
【図２２】図２２は、マルチキャストキーを含む暗号化メッセージを概略的に示す。
【図２３ａ】図２３ａは、図２２の暗号化メッセージの解読を概略的に示す。
【図２３ｂ】図２３ｂは、図２２の暗号化メッセージの解読を概略的に示す。
【図１】
2007538454.tif 000040
【図２】
2007538454.tif 000041
【図２ａ】
2007538454.tif 000042
【図２ｂ】
2007538454.tif 000043
【図３】
2007538454.tif 000044
【図３ａ】
2007538454.tif 000045
【図３ｂ】
2007538454.tif 000046
【図４】
2007538454.tif 000047
【図５】
2007538454.tif 000048
【図６】
2007538454.tif 000049
【図７】
2007538454.tif 000050
【図８】
2007538454.tif 000051
【図９】
2007538454.tif 000052
【図１０】
2007538454.tif 000053
【図１１ａ】
2007538454.tif 000054
【図１１ｂ】
2007538454.tif 000055
【図１１ｃ】
2007538454.tif 000056
【図１２ａ】
2007538454.tif 000057
【図１２ｂ】
2007538454.tif 000058
【図１２ｃ】
2007538454.tif 000059
【図１３ａ】
2007538454.tif 000060
【図１３ｂ】
2007538454.tif 000061
【図１４】
2007538454.tif 000062
【図１５ａ】
2007538454.tif 000063
【図１５ｂ】
2007538454.tif 000064
【図１６ａ】
2007538454.tif 000065
【図１６ｂ】
2007538454.tif 000066
【図１７】
2007538454.tif 000067
【図１８】
2007538454.tif 000068
【図１９】
2007538454.tif 000069
【図２０】
2007538454.tif 000070
【図２１】
2007538454.tif 000071
【図２２】
2007538454.tif 000072
【図２３ａ】
2007538454.tif 000073
【図２３ｂ】
2007538454.tif 000074
【国際調査報告】
2007538454.tif 000075
2007538454.tif 000076
2007538454.tif 000077