【手続補正書】
【提出日】平成21年9月8日(2009.9.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
相異なる暗号鍵をそれぞれ生成する第１処理部および第２処理部を備える、鍵生成装置であって、
前記第１処理部は、
ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成する、木構造構成部と、
前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当てる第１リーフキー割当部と、
前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当部と、
前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて、鍵を算出する第１鍵算出部と、
を備え、
前記第２処理部は、前記ｎ個の受信装置を、前記Ｙ以上の整数Ｂに基づいてグループ化し、前記受信装置の暗号鍵を算出する、鍵生成装置。
【請求項２】
前記鍵生成装置は、素数ｐを無作為に選択し、前記素数ｐを位数とする双線形群Ｇを決定し、前記Ｇの生成元であるｇを無作為に選択する双線形群決定部を更に備え、
前記パラメータ割当部は、前記リーフを除く全てのノードそれぞれに、ノードパラメータγx,y（γx,yは整数）を無作為に選択し、前記生成元ｇおよび前記ノードパラメータγx,yに基づき、以下の式Ａを用いて前記中間ノードおよび前記ルートに前記パラメータνｘ，ｙを割り当てる、請求項１に記載の鍵生成装置。
【数１】
2008113203.tif 000001
【請求項３】
前記第１処理部は、
秘密の乱数α（αは整数）を無作為に選択する第１乱数決定部を更に備え、
前記第１リーフキー割当部は、
以下の式Ｂに基づき、前記リーフキーｇｙを算出し、
前記第１鍵算出部は、
前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙの、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータγｘ，ｙ乗で得られる値を、秘密鍵とする、請求項２に記載の鍵生成装置。
【数２】
2008113203.tif 000002
（ｙ＝１，２，・・・，Ｙ，Ｙ＋２，・・・，２Ｙ）
【請求項４】
前記第２処理部は、
秘密の乱数α’（α’は整数）を無作為に選択する第２乱数決定部と、
前記リーフに対して、リーフキーｇｂ’（ｂ＝１，２，・・・，Ｂ）を割り当てる第２リーフキー割当部と、
前記リーフキーｇｂ’に基づき、各受信装置の暗号鍵を算出する第２鍵算出部と、
を備え、
前記第２リーフキー割当部は、前記第２乱数決定部で決定された前記乱数α’に基づいて、以下の式Ｃを満たすリーフキーｇｂ’を算出する、請求項３に記載の鍵生成装置。
【数３】
2008113203.tif 000003
（ｂ＝１，２，・・・，Ｂ，Ｂ＋２，・・・，２Ｂ）
【請求項５】
前記鍵生成装置は、前記第１処理部または前記第２処理部により算出された鍵セットを、各受信装置にそれぞれ配布する配布部を更に備え、
前記配布部は、前記第１処理部において得られた第１の秘密鍵および前記第２処理部において得られた第２の秘密鍵の双方を各受信装置に送信する送信部を、備える、請求項１に記載の鍵生成装置。
【請求項６】
ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する排除受信装置特定部を備える、暗号化装置。
【請求項７】
前記暗号化装置は、
前記排除される受信装置の個数ｒが、以下の式Ｄを満たすか否かを判定し、
前記排除される受信装置の個数ｒが前記式Ｄを満たす場合には、前記第２処理部によって生成された鍵を利用してセッション鍵を生成する、第２セッション鍵決定部を選択し、
前記排除される受信装置の個数ｒが前記式Ｄを満たさない場合には、前記第１処理部によって生成された鍵を利用してセッション鍵を生成する、第１セッション鍵決定部を選択する、セッション鍵選択部を更に備える、請求項６に記載の暗号化装置。
【数４】
2008113203.tif 000004
【請求項８】
前記第１セッション鍵決定部は、ｔ（ｔは整数）を無作為に選択して、セッション鍵ｓ＝ｅ（ｇＹ，ｇ１）ｔを決定し、
前記第２セッション鍵決定部は、ｔ（ｔは整数）を無作為に選択して、セッション鍵ｓ＝ｅ（ｇＢ，ｇ１）ｔを決定し、
前記暗号化装置は、前記第１セッション鍵決定部によるセッション鍵ｓ、または、前記第２セッション鍵決定部によるセッション鍵ｓのいずれかを用いて、配信するコンテンツを暗号化する暗号化部を更に備える、請求項７に記載の暗号化装置。
ここで、前記ｅ（ｇＹ，ｇ１）は、双線形群上の２つの元ｇＹ、ｇ１に対する双線形写像を示し、前記ｅ（ｇＢ，ｇ１）は、双線形群上の２つの元ｇＢ、ｇ１に対する双線形写像を示す。
【請求項９】
前記第１セッション鍵決定部は、
階層化された木構造において、前記排除された受信装置のリーフから前記ルートに至るパス上に存在する全てのノードそれぞれにマークをし、前記マークされたノードに割り当てられたパラメータνｘ，ｙと、前記マークされたノードを親ノードとする中間ノードに割り当てられた前記リーフキーｇｙとを用いて、以下の式Ｅで表される第１ヘッダ要素を算出する、第１ヘッダ要素算出部と、
前記第１ヘッダ要素算出部において得られた前記第１ヘッダ要素ｃｘ，ｙと、ｇｔと、をヘッダ情報とする第１ヘッダ情報生成部と、
を更に備える、請求項８に記載の暗号化装置。
【数５】
2008113203.tif 000005
ここで、Ｓｘ，ｙは、前記マークされたノードを親ノードとする各サブグループに所属する、マークされていない子ノードの集合を示す。
【請求項１０】
前記第２セッション鍵決定部は、
前記リーフの親ノードを子ノードとする中間ノードに割り当てられたパラメータνｘ，ｙと、前記リーフに割り当てられた前記リーフキーｇｂ’と、を用いて、以下の式Ｆで表される第２ヘッダ要素を算出する、第２ヘッダ要素算出部と、
前記第２ヘッダ要素算出部において得られた前記第２ヘッダ要素ｃｂと、前記ｇｔと、をヘッダ情報とする第２ヘッダ情報生成部と、
を更に備える、請求項８に記載の暗号化装置。
【数６】
2008113203.tif 000006
【請求項１１】
鍵生成装置および暗号化装置と通信可能な受信装置であって、
前記鍵生成装置において、ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成し、前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当て、前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて算出された暗号鍵と、前記ｎ個の受信装置を、前記Ｙ以上の整数Ｂに基づいてグループ化して算出された暗号鍵と、をそれぞれ受信する受信部を備える、受信装置。
【請求項１２】
前記受信部は、排除する受信装置が特定された情報である、排除されていない受信装置の集合Ｓに関する情報を更に受信し、
前記受信装置は、
排除されていない受信装置の集合Ｓから排除される受信装置の個数ｒを算出し、前記排除される受信装置の個数ｒが、以下の式Ｇを満たすか否かを判定する、復号方式選択部を更に備え、
前記復号方式選択部は、
前記排除される受信装置の個数ｒが前記式Ｇを満たす場合には、第２復号処理部を選択し、
前記排除される受信装置の個数ｒが前記式Ｇを満たさない場合には、第１復号処理部を選択する、請求項１１に記載の受信装置。
【数７】
2008113203.tif 000007
【請求項１３】
前記第１復号処理部は、
受信装置が前記集合Ｓに含まれているか否かを判定する判定部と、
秘密鍵に基づきセッション鍵ｓを算出する、第１セッション鍵算出部と、
を備え、
前記判定部において、受信装置が前記集合Ｓに含まれていると判断された場合、前記第１セッション鍵算出部は、前記セッション鍵ｓを、以下の式Ｈに基づいて算出することで、前記暗号化コンテンツを復号化する、請求項１２に記載の受信装置。
【数８】
2008113203.tif 000008
【請求項１４】
前記第２復号処理部は、
受信装置が前記集合Ｓに含まれているか否かを判定する判定部と、
秘密鍵に基づきセッション鍵ｓを算出する、第２セッション鍵算出部と、
を備え、
前記判定部において、受信装置が前記集合Ｓに含まれていると判断された場合、前記第２セッション鍵算出部は、前記セッション鍵ｓを、以下の式Ｉに基づいて算出することで、前記暗号化コンテンツを復号化する、請求項１３に記載の受信装置。
【数９】
2008113203.tif 000009
【請求項１５】
ｎ個の受信装置をリーフに割り当て、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成する、木構造構成ステップと、
前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当てる第１リーフキー割当ステップと、
前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当ステップと、
前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて、各受信装置の暗号鍵を算出する第１鍵算出ステップと、
前記ｎ個の受信装置を、前記Ｙ以上の整数Ｂに基づいてグループ化し、前記受信装置の暗号鍵を算出する第２鍵算出ステップと、
を備える、鍵作成方法。
【請求項１６】
ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する排除受信装置特定ステップを備える、暗号化方法。
【請求項１７】
ｎ個の受信装置をリーフに割り当て、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成し、前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当て、前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて算出された暗号鍵と、前記ｎ個の受信装置を、前記Ｙ以上の整数Ｂに基づいてグループ化して算出された暗号鍵と、をそれぞれ受信する受信ステップを備える、鍵処理方法。
【請求項１８】
コンピュータに、
ｎ個の受信装置がリーフに割り当てられ、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成する、木構造構成機能と、
前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当てる第１リーフキー割当機能と、
前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当てるパラメータ割当機能と、
前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて、各受信装置の暗号鍵を算出する第１鍵算出機能と、
前記ｎ個の受信装置を、前記Ｙ以上の整数Ｂに基づいてグループ化し、前記受信装置の暗号鍵を算出する第２鍵算出機能と、
を実現させるためのプログラム。
【請求項１９】
コンピュータに、ｎ個の受信装置のなかから排除する受信装置を特定し、排除されていない受信装置の集合Ｓを決定する排除受信装置特定機能を実現させるためのプログラム。
【請求項２０】
コンピュータに、ｎ個の受信装置をリーフに割り当て、高さが（ｌｏｇＹｎ）で表されるＹ分木構造を階層的に構成し、前記リーフとルートとの間に存在する中間ノードの下位に存在する複数の前記リーフからなるサブグループを構成し、前記リーフおよび前記中間ノードそれぞれに対して、リーフキーｇｙを割り当て、前記中間ノードおよび前記ルートに、相異なるパラメータνｘ,ｙ（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とノードパラメータγx,y（ｘ：階層、ｙ：１，２，・・・，Ｙｘ）とをそれぞれ割り当て、前記ルートから前記リーフに至るパスを特定し、当該パス上に存在する前記中間ノードまたは前記リーフに割り当てられた前記リーフキーｇｙと、当該中間ノードまたは当該リーフの親ノードに割り当てられた前記パラメータνｘ，ｙおよび前記ノードパラメータγx,yに基づいて算出された暗号鍵と、前記ｎ個の受信装置を、前記Ｙ以上の整数Ｂに基づいてグループ化して算出された暗号鍵と、をそれぞれ受信する受信機能を実現させるためのプログラム。