(57)【要約】【課題】複数の復号化装置に選択的に送信する暗号化メッセージのメッセージ長を低減する。【解決手段】暗号化通信システムにおいて、暗号化装置が、木構造における各末端ノードと各復号化装置とを対応付けるノード対応情報を、復号化を許可する復号化装置のグループに応じて生成するノード対応情報生成部と、復号化を許可する復号化装置を子孫の末端ノードとし、復号化を禁止する復号化装置を子孫のいずれの末端ノードにも有しない復号化許可ノードを抽出するノード抽出部と、復号化許可ノードのノード暗号鍵によりメッセージを暗号化するメッセージ暗号化部とを有し、各復号化装置が、ノード対応情報に基づいて、当該復号化装置が対応付けられた末端ノードを特定する末端ノード特定部と、末端ノードからルートノードに至るいずれかの復号化許可ノードのノード復号鍵により暗号化メッセージを復号化するメッセージ復号化部とを有する。【選択図】図２
2006013790.tif 000002
【特許請求の範囲】
【請求項１】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置であって、
前記暗号化装置は、
複数のノードを接続した第１の木構造における複数の第１末端ノードのそれぞれに複数の前記復号化装置のそれぞれを対応付けるノード対応情報を、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成し、
前記ノード対応情報により前記複数の復号化装置が対応付けられた前記第１の木構造において、前記暗号化メッセージの復号化を許可する前記復号化装置が子孫の第１末端ノードに対応付けられており、前記暗号化メッセージの復号化を禁止する前記復号化装置が子孫のいずれの第１末端ノードにも対応付けられていない第１の復号化許可ノードを抽出し、
前記第１の復号化許可ノードに対応付けられた第１のノード暗号鍵によりメッセージを暗号化するものであり、
当該復号化装置は、
前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成された前記ノード対応情報を取得するノード対応情報取得部と、
前記ノード対応情報に基づいて、当該復号化装置が対応付けられた前記第１末端ノードを特定する末端ノード特定部と、
当該復号化装置が対応付けられた前記第１末端ノードから前記第１の木構造のルートノードに至るいずれかのノードが前記第１の復号化許可ノードであった場合に、当該第１の復号化許可ノードに対応する第１のノード復号鍵により前記暗号化メッセージを復号化するメッセージ復号化部と
を備える復号化装置。
【請求項２】
それぞれの前記復号化装置に対応して、公開鍵及び秘密鍵が予め定められており、
前記暗号化装置は、前記複数の復号化装置のうち、前記第１の復号化許可ノードの子孫の各第１末端ノードに対応付けられていない各復号化装置に対応する前記秘密鍵の積に基づく前記第１のノード暗号鍵により前記メッセージを暗号化するものであり、
当該復号化装置は、
前記複数の復号化装置のうち、当該復号化装置以外の復号化装置に対応する前記秘密鍵の積に基づき定められた装置復号鍵を記憶する装置復号鍵記憶部と、
当該復号化装置が対応付けられた前記第１末端ノードから前記第１の木構造のルートノードに至るいずれかのノードが前記第１の復号化許可ノードであった場合に、前記第１の復号化許可ノードの子孫の各第１末端ノードに対応する、当該復号化装置以外のそれぞれの前記復号化装置に対応する前記公開鍵と、当該復号化装置の前記装置復号鍵とに基づいて、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない前記復号化装置に対応する前記秘密鍵の積に基づく前記第１のノード復号鍵を生成するノード復号鍵生成部と
を備える請求項１記載の復号化装置。
【請求項３】
それぞれの前記復号化装置に対応する前記公開鍵及び前記秘密鍵は、ＲＳＡ暗号系における公開鍵及び秘密鍵の組であり、
前記暗号化装置は、予め定められた数を、前記第１の復号化許可ノードの子孫の第１末端ノードに対応付けられた各復号化装置に対応する前記秘密鍵の積によりべき乗した値に基づく前記ノード暗号鍵により前記メッセージを暗号化するものであり、
前記装置復号鍵記憶部は、前記予め定められた数を、当該復号化装置以外の復号化装置に対応する秘密鍵の積によりべき乗した値に基づき定められた前記装置復号鍵を記憶し、
前記ノード復号鍵生成部は、当該復号化装置の前記装置復号鍵を、前記第１の復号化許可ノードの子孫の各第１末端ノードに対応する、当該復号化装置以外のそれぞれの前記復号化装置の前記公開鍵の積によりべき乗した値に基づいて、前記第１のノード暗号鍵と同一の値の前記ノード復号鍵を生成する
請求項２記載の復号化装置。
【請求項４】
前記暗号化装置は、
複数の前記第１の木構造のそれぞれのルートノードを複数の第２末端ノードとして接続する第２の木構造を記憶し、
少なくとも１つの前記第１の木構造に接続された全ての前記第１末端ノードに対応する前記復号化装置に対し前記暗号化メッセージの復号化を許可する場合に、当該第１の木構造のルートノードを子孫の第２末端ノードとして接続し、前記暗号化メッセージの復号化を許可しない前記復号化装置が前記第１末端ノードに対応付けられた前記第１の木構造のルートノードを子孫の第２末端ノードとして接続しない第２の復号化許可ノードを抽出し、
前記第１の復号化許可ノードに対応付けられた前記第１のノード暗号鍵、又は前記第２の復号化許可ノードに対応付けられた第２のノード暗号鍵により前記メッセージを暗号化するものであり、
前記メッセージ復号化部は、前記暗号化メッセージが前記第２のノード暗号鍵により暗号化されていた場合において、当該復号化装置が前記第１の末端ノードに対応付けられた前記第１の木構造のルートノードに対応する前記第２の末端ノードから前記第２の木構造のルートノードに至るいずれかのノードが前記第２の復号化許可ノードであった場合に、当該第２の復号化許可ノードに対応する第２のノード復号鍵により前記暗号化メッセージを復号化する
請求項１記載の復号化装置。
【請求項５】
当該復号化装置が前記第１の末端ノードに対応付けられた前記第１の木構造のルートノードに対応する前記第２の末端ノードから前記第２の木構造のルートノードに至る各ノードに対応する前記第２のノード復号鍵のそれぞれを記憶するノード復号鍵記憶部を更に備える請求項４記載の復号化装置。
【請求項６】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置であって、
複数の前記復号化装置のそれぞれに対応して、公開鍵及び秘密鍵が予め定められており、
前記暗号化装置は、複数の前記復号化装置のうち、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない各復号化装置に対応する前記秘密鍵の積に基づくグループ暗号鍵によりメッセージを暗号化するものであり、
当該復号化装置は、
前記複数の復号化装置のうち、当該復号化装置以外の復号化装置に対応する前記秘密鍵の積に基づき定められた装置復号鍵を記憶する装置復号鍵記憶部と、
前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属するそれぞれの前記復号化装置に対応する前記公開鍵と、当該復号化装置の前記装置復号鍵とに基づいて、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない前記復号化装置に対応する前記秘密鍵の積に基づく前記暗号化メッセージのグループ復号鍵を生成するグループ復号鍵生成部と、
前記グループ復号鍵を用いて前記暗号化メッセージを復号化するメッセージ復号化部と
を備える復号化装置。
【請求項７】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置であって、
前記暗号化装置は、
複数の復号化装置のそれぞれを末端ノードとし、複数のノードを接続した木構造を複数種類記憶し、
前記暗号化メッセージの復号化を許可する前記復号化装置の組に基づいて、いずれかの前記木構造を選択し、
選択された前記木構造について、前記暗号化メッセージの復号化を禁止する前記復号化装置を子孫の末端ノードに含まず、前記暗号化メッセージの復号化を許可する前記復号化装置をいずれかのノードの子孫の末端ノードに含む復号化許可ノードの組を抽出し、
選択された前記復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれにより前記メッセージを暗号化するものであり、
当該復号化装置は、
前記復号化許可ノードの組の選択元となった前記木構造において、当該復号化装置に対応する末端ノードからルートノードに至る経路上に位置するノードのうち、選択された前記復号化許可ノードを特定するノード特定部と、
前記復号化許可ノードの組の選択元となった前記木構造における前記ノード特定部により特定された前記復号化許可ノードに対応付けられたノード復号鍵を取得するノード復号鍵取得部と、
取得された前記ノード復号鍵を用いて、前記ノード特定部により特定された前記復号化許可ノードに対応付けられた前記ノード暗号鍵により暗号化された前記暗号化メッセージを復号化するメッセージ復号化部と
を備える復号化装置。
【請求項８】
前記暗号化装置は、第１の前記木構造の第１の前記復号化許可ノード及び第２の前記木構造の第２の前記復号化許可ノードの組であって、前記暗号化メッセージの復号化を許可する前記復号化装置を子孫の末端ノードに共通して含み、前記暗号化メッセージの復号化を禁止する前記復号化装置を少なくとも一方の前記復号化許可ノードの子孫の末端ノードに含まない前記第１の復号化許可ノード及び前記第２の復号化許可ノードの組を抽出し、
前記第１の復号化許可ノードに対応付けられた第１の前記ノード暗号鍵及び前記第２の復号化許可ノードに対応付けられた第２の前記ノード暗号鍵により前記メッセージを暗号化するものであり、
前記ノード特定部は、前記第１の復号化許可ノード及び前記第２の復号化許可ノードを特定し、
前記ノード復号鍵取得部は、前記第１の復号化許可ノードに対応付けられた第１の前記ノード復号鍵と、前記第２の復号化許可ノードに対応付けられた第２の前記ノード復号鍵とを取得し、
前記メッセージ復号化部は、取得された前記第１のノード復号鍵及び前記第２のノード復号鍵を用いて前記暗号化メッセージを復号化する
請求項７記載の復号化装置。
【請求項９】
メッセージを暗号化する暗号化装置であって、
複数のノードを接続した第１の木構造における複数の第１末端ノードのそれぞれに複数の復号化装置のそれぞれを対応付けるノード対応情報を、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成するノード対応情報生成部と、
前記ノード対応情報により前記複数の復号化装置が対応付けられた前記第１の木構造において、前記暗号化メッセージの復号化を許可する前記復号化装置が子孫の第１末端ノードに対応付けられており、前記暗号化メッセージの復号化を禁止する前記復号化装置が子孫のいずれの第１末端ノードにも対応付けられていない第１の復号化許可ノードを抽出するノード抽出部と、
前記第１の復号化許可ノードに対応付けられた第１のノード暗号鍵により前記メッセージを暗号化するメッセージ暗号化部と
を備える暗号化装置。
【請求項１０】
それぞれの前記復号化装置に対応して、公開鍵及び秘密鍵が予め定められており、
前記複数の復号化装置のうち、前記第１の復号化許可ノードの子孫の第１末端ノードに対応付けられていない各復号化装置に対応する前記秘密鍵の積に基づいて前記第１のノード暗号鍵を生成するノード暗号鍵生成部を更に備える
請求項９記載の暗号化装置。
【請求項１１】
それぞれの前記復号化装置は、
前記複数の復号化装置のうち、当該復号化装置以外の復号化装置に対応する前記秘密鍵の積に基づき定められた装置復号鍵を記憶し、
当該復号化装置が対応付けられた前記第１末端ノードから前記第１の木構造のルートノードに至るいずれかのノードが前記第１の復号化許可ノードであった場合に、前記第１の復号化許可ノードの子孫の各第１末端ノードに対応する、当該復号化装置以外のそれぞれの前記復号化装置に対応する前記公開鍵の積と、当該復号化装置の前記装置復号鍵とに基づいて、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない前記復号化装置に対応する前記秘密鍵の積に基づく前記第１のノード復号鍵を生成するものであり、
当該暗号化装置は、
前記第１の復号化許可ノードの子孫の各第１末端ノードに対応する、当該復号化装置以外のそれぞれの前記復号化装置に対応する前記公開鍵の積を算出する公開鍵乗算部と、
前記公開鍵の積を前記複数の復号化装置に対して公開する公開部と
を更に備える
請求項１０記載の暗号化装置。
【請求項１２】
前記ノード抽出部は、前記暗号化メッセージの復号化を許可する全ての前記復号化装置がいずれかの前記第１の復号化許可ノードの子孫の第１末端ノードに対応付けられた前記第１の復号化許可ノードの組のうち、前記第１の復号化許可ノードの数を最小とする前記第１の復号化許可ノードの組を抽出し、
前記ノード対応情報生成部は、前記ノード抽出部が抽出する前記第１の復号化許可ノードの数を最小とする前記ノード対応情報を生成し、
前記メッセージ暗号化部は、抽出された前記第１の復号化許可ノードの組に属するそれぞれの前記第１の復号化許可ノードに対応する前記第１のノード暗号鍵のそれぞれにより前記メッセージを暗号化した複数の前記暗号化メッセージを出力する
請求項９記載の暗号化装置。
【請求項１３】
第１の前記暗号化メッセージを出力した後、暗号化メッセージの復号化を許可する前記復号化装置の組が前記第１の暗号化メッセージと異なる第２の前記暗号化メッセージを出力する場合において、前記ノード対応情報生成部は、前記第１の暗号化メッセージの復号化を許可した前記復号化装置であって、前記第２の暗号化メッセージの復号化を許可する前記復号化装置を、前記第１の暗号化メッセージの暗号化において対応付けた前記第１末端ノードと同一の前記第１末端ノードに対応付ける前記ノード対応情報を生成する請求項１２記載の暗号化装置。
【請求項１４】
第１の前記暗号化メッセージを出力した後、暗号化メッセージの復号化を許可する前記復号化装置の組が前記第１の暗号化メッセージと異なる第２の前記暗号化メッセージを出力する場合において、前記ノード抽出部は、前記第２の暗号化メッセージの復号化を許可する前記復号化装置が子孫の前記第１末端ノードに対応付けられており、前記第２の暗号化メッセージの復号化を禁止する前記復号化装置が子孫のいずれの第１末端ノードにも対応付けられていない前記第１の復号化許可ノードを更に抽出し、
前記ノード対応情報生成部は、前記第２の暗号化メッセージに対応して前記ノード抽出部が抽出する前記第１の復号化許可ノードの数を最小とする前記ノード対応情報を更に生成する
請求項１３記載の暗号化装置。
【請求項１５】
メッセージを暗号化する暗号化装置であって、
暗号化された暗号化メッセージを復号化する複数の復号化装置のそれぞれに対応して、公開鍵及び秘密鍵が予め定められており、
前記複数の復号化装置のうち、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない各復号化装置に対応する前記秘密鍵の積に基づくグループ暗号鍵により前記メッセージを暗号化するメッセージ暗号化部
を備える暗号化装置。
【請求項１６】
メッセージを暗号化する暗号化装置であって、
複数の復号化装置のそれぞれを末端ノードとし、複数のノードを接続した木構造を複数種類記憶する木構造記憶部と、
前記暗号化メッセージの復号化を許可する前記復号化装置の組に基づいて、いずれかの前記木構造を選択する木構造選択部と、
選択された前記木構造について、前記暗号化メッセージの復号化を禁止する前記復号化装置を子孫の末端ノードに含まず、前記暗号化メッセージの復号化を許可する前記復号化装置をいずれかのノードの子孫の末端ノードに含む復号化許可ノードの組を抽出するノード抽出部と、
選択された前記復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれにより前記メッセージを暗号化した複数の前記暗号化メッセージを出力するメッセージ暗号化部と
を備える暗号化装置。
【請求項１７】
前記木構造選択部は、それぞれの前記木構造について選択された前記復号化許可ノードの組のうち、前記復号化許可ノードの数が最小となるノードの組を選択する請求項１６記載の暗号化装置。
【請求項１８】
前記木構造記憶部は、互いに異なる前記復号化装置の種類又は前記復号化装置の利用者の各種の特性に基づいて、より類似する前記種類又は前記特性を有する前記復号化装置の組を、末端ノードにより近い前記復号化許可ノードの子孫の末端ノードにそれぞれ対応付けた前記複数の木構造を記憶し、
前記木構造選択部は、前記暗号化メッセージの復号化を許可する前記復号化装置の種類又は利用者の特性に基づいて、いずれかの前記木構造を選択する
請求項１６記載の暗号化装置。
【請求項１９】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置における復号化方法であって、
前記暗号化装置は、
複数のノードを接続した第１の木構造における複数の第１末端ノードのそれぞれに複数の前記復号化装置のそれぞれを対応付けるノード対応情報を、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成し、
前記ノード対応情報により前記複数の復号化装置が対応付けられた前記第１の木構造において、前記暗号化メッセージの復号化を許可する前記復号化装置が子孫の第１末端ノードに対応付けられており、前記暗号化メッセージの復号化を禁止する前記復号化装置が子孫のいずれの第１末端ノードにも対応付けられていない第１の復号化許可ノードを抽出し、
前記第１の復号化許可ノードに対応付けられた第１のノード暗号鍵によりメッセージを暗号化するものであり、
前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成された前記ノード対応情報を取得するノード対応情報取得段階と、
前記ノード対応情報に基づいて、当該復号化装置が対応付けられた前記第１末端ノードを特定する末端ノード特定段階と、
当該復号化装置が対応付けられた前記第１末端ノードから前記第１の木構造のルートノードに至るいずれかのノードが前記第１の復号化許可ノードであった場合に、当該第１の復号化許可ノードに対応する第１のノード復号鍵により前記暗号化メッセージを復号化するメッセージ復号化段階と
を備える復号化方法。
【請求項２０】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置における復号化方法であって、
複数の前記復号化装置のそれぞれに対応して、公開鍵及び秘密鍵が予め定められており、
前記暗号化装置は、複数の前記復号化装置のうち、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない各復号化装置に対応する前記秘密鍵の積に基づくグループ暗号鍵によりメッセージを暗号化するものであり、
前記複数の復号化装置のうち、当該復号化装置以外の復号化装置に対応する前記秘密鍵の積に基づき定められた装置復号鍵を記憶する装置復号鍵記憶段階と、
前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属するそれぞれの前記復号化装置に対応する前記公開鍵と、当該復号化装置の前記装置復号鍵とに基づいて、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない前記復号化装置に対応する前記秘密鍵の積に基づく前記暗号化メッセージのグループ復号鍵を生成するグループ復号鍵生成段階と、
前記グループ復号鍵を用いて前記暗号化メッセージを復号化するメッセージ復号化段階と
を備える復号化方法。
【請求項２１】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置における復号化方法であって、
前記暗号化装置は、
複数の復号化装置のそれぞれを末端ノードとし、複数のノードを接続した木構造を複数種類記憶し、
前記暗号化メッセージの復号化を許可する前記復号化装置の組に基づいて、いずれかの前記木構造を選択し、
選択された前記木構造について、前記暗号化メッセージの復号化を禁止する前記復号化装置を子孫の末端ノードに含まず、前記暗号化メッセージの復号化を許可する前記復号化装置をいずれかのノードの子孫の末端ノードに含む復号化許可ノードの組を抽出し、
選択された前記復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれにより前記メッセージを暗号化するものであり、
前記復号化許可ノードの組の選択元となった前記木構造において、当該復号化装置に対応する末端ノードからルートノードに至る経路上に位置するノードのうち、選択された前記復号化許可ノードを特定するノード特定段階と、
前記復号化許可ノードの組の選択元となった前記木構造における前記ノード特定段階により特定された前記復号化許可ノードに対応付けられたノード復号鍵を取得するノード復号鍵取得段階と、
取得された前記ノード復号鍵を用いて、前記ノード特定段階により特定された前記復号化許可ノードに対応付けられた前記ノード暗号鍵により暗号化された前記暗号化メッセージを復号化するメッセージ復号化段階と
を備える復号化方法。
【請求項２２】
メッセージを暗号化する暗号化装置における暗号化方法であって、
複数のノードを接続した第１の木構造における複数の末端ノードのそれぞれに複数の復号化装置のそれぞれを対応付けるノード対応情報を、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成するノード対応情報生成段階と、
前記ノード対応情報により前記複数の復号化装置が対応付けられた前記第１の木構造において、前記暗号化メッセージの復号化を許可する前記復号化装置が子孫の第１末端ノードに対応付けられており、前記暗号化メッセージの復号化を禁止する前記復号化装置が子孫のいずれの第１末端ノードにも対応付けられていない第１の復号化許可ノードを抽出するノード抽出段階と、
前記第１の復号化許可ノードに対応付けられた第１のノード暗号鍵により前記メッセージを暗号化するメッセージ暗号化段階と
を備える暗号化方法。
【請求項２３】
メッセージを暗号化する暗号化装置における暗号化方法であって、
暗号化された暗号化メッセージを復号化する複数の復号化装置のそれぞれに対応して、公開鍵及び秘密鍵が予め定められており、
前記複数の復号化装置のうち、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない各復号化装置に対応する前記秘密鍵の積に基づくグループ暗号鍵により前記メッセージを暗号化するメッセージ暗号化段階
を備える暗号化方法。
【請求項２４】
メッセージを暗号化する暗号化装置における暗号化方法であって、
複数の復号化装置のそれぞれを末端ノードとし、複数のノードを接続した木構造を複数種類記憶する木構造記憶段階と、
前記暗号化メッセージの復号化を許可する前記復号化装置の組に基づいて、いずれかの前記木構造を選択する木構造選択段階と、
選択された前記木構造について、前記暗号化メッセージの復号化を禁止する前記復号化装置を子孫の末端ノードに含まず、前記暗号化メッセージの復号化を許可する前記復号化装置をいずれかのノードの子孫の末端ノードに含む復号化許可ノードの組を抽出するノード抽出段階と、
選択された前記復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれにより前記メッセージを暗号化した複数の前記暗号化メッセージを出力するメッセージ暗号化段階と
を備える暗号化方法。
【請求項２５】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置用の復号化プログラムであって、
前記暗号化装置は、
複数のノードを接続した第１の木構造における複数の第１末端ノードのそれぞれに複数の前記復号化装置のそれぞれを対応付けるノード対応情報を、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成し、
前記ノード対応情報により前記複数の復号化装置が対応付けられた前記第１の木構造において、前記暗号化メッセージの復号化を許可する前記復号化装置が子孫の第１末端ノードに対応付けられており、前記暗号化メッセージの復号化を禁止する前記復号化装置が子孫のいずれの第１末端ノードにも対応付けられていない第１の復号化許可ノードを抽出し、
前記第１の復号化許可ノードに対応付けられた第１のノード暗号鍵によりメッセージを暗号化するものであり、
当該復号化プログラムは、当該復号化装置を、
前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成された前記ノード対応情報を取得するノード対応情報取得部と、
前記ノード対応情報に基づいて、当該復号化装置が対応付けられた前記第１末端ノードを特定する末端ノード特定部と、
当該復号化装置が対応付けられた前記第１末端ノードから前記第１の木構造のルートノードに至るいずれかのノードが前記第１の復号化許可ノードであった場合に、当該第１の復号化許可ノードに対応する第１のノード復号鍵により前記暗号化メッセージを復号化するメッセージ復号化部と
して機能させる復号化プログラム。
【請求項２６】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置用の復号化プログラムであって、
複数の前記復号化装置のそれぞれに対応して、公開鍵及び秘密鍵が予め定められており、
前記暗号化装置は、複数の前記復号化装置のうち、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない各復号化装置に対応する前記秘密鍵の積に基づくグループ暗号鍵によりメッセージを暗号化するものであり、
当該復号化プログラムは、当該復号化装置を、
前記複数の復号化装置のうち、当該復号化装置以外の復号化装置に対応する前記秘密鍵の積に基づき定められた装置復号鍵を記憶する装置復号鍵記憶部と、
前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属するそれぞれの前記復号化装置に対応する前記公開鍵と、当該復号化装置の前記装置復号鍵とに基づいて、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない前記復号化装置に対応する前記秘密鍵の積に基づく前記暗号化メッセージのグループ復号鍵を生成するグループ復号鍵生成部と、
前記グループ復号鍵を用いて前記暗号化メッセージを復号化するメッセージ復号化部と
して機能させる復号化プログラム。
【請求項２７】
暗号化装置により暗号化された暗号化メッセージを復号化する復号化装置用の復号化プログラムであって、
前記暗号化装置は、
複数の復号化装置のそれぞれを末端ノードとし、複数のノードを接続した木構造を複数種類記憶し、
前記暗号化メッセージの復号化を許可する前記復号化装置の組に基づいて、いずれかの前記木構造を選択し、
選択された前記木構造について、前記暗号化メッセージの復号化を禁止する前記復号化装置を子孫の末端ノードに含まず、前記暗号化メッセージの復号化を許可する前記復号化装置をいずれかのノードの子孫の末端ノードに含む復号化許可ノードの組を抽出し、
選択された前記復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれにより前記メッセージを暗号化するものであり、
当該復号化プログラムは、当該復号化装置を、
前記復号化許可ノードの組の選択元となった前記木構造において、当該復号化装置に対応する末端ノードからルートノードに至る経路上に位置するノードのうち、選択された前記復号化許可ノードを特定するノード特定部と、
前記復号化許可ノードの組の選択元となった前記木構造における前記ノード特定部により特定された前記復号化許可ノードに対応付けられたノード復号鍵を取得するノード復号鍵取得部と、
取得された前記ノード復号鍵を用いて、前記ノード特定部により特定された前記復号化許可ノードに対応付けられた前記ノード暗号鍵により暗号化された前記暗号化メッセージを復号化するメッセージ復号化部と
して機能させる復号化プログラム。
【請求項２８】
メッセージを暗号化する暗号化装置用の暗号化プログラムであって、
当該暗号化装置を、
複数のノードを接続した第１の木構造における複数の末端ノードのそれぞれに複数の復号化装置のそれぞれを対応付けるノード対応情報を、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成するノード対応情報生成部と、
前記ノード対応情報により前記複数の復号化装置が対応付けられた前記第１の木構造において、前記暗号化メッセージの復号化を許可する前記復号化装置が子孫の第１末端ノードに対応付けられており、前記暗号化メッセージの復号化を禁止する前記復号化装置が子孫のいずれの第１末端ノードにも対応付けられていない第１の復号化許可ノードを抽出するノード抽出部と、
前記第１の復号化許可ノードに対応付けられた第１のノード暗号鍵により前記メッセージを暗号化するメッセージ暗号化部と
して機能させる暗号化プログラム。
【請求項２９】
メッセージを暗号化する暗号化装置用の暗号化プログラムであって、
暗号化された暗号化メッセージを復号化する複数の復号化装置のそれぞれに対応して、公開鍵及び秘密鍵が予め定められており、
当該暗号化プログラムは、当該暗号化装置を、
前記複数の復号化装置のうち、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない各復号化装置に対応する前記秘密鍵の積に基づくグループ暗号鍵により前記メッセージを暗号化するメッセージ暗号化部
として機能させる暗号化プログラム。
【請求項３０】
メッセージを暗号化する暗号化装置用の暗号化プログラムであって、
当該暗号化プログラムは、前記暗号化装置を、
複数の復号化装置のそれぞれを末端ノードとし、複数のノードを接続した木構造を複数種類記憶する木構造記憶部と、
前記暗号化メッセージの復号化を許可する前記復号化装置の組に基づいて、いずれかの前記木構造を選択する木構造選択部と、
選択された前記木構造について、前記暗号化メッセージの復号化を禁止する前記復号化装置を子孫の末端ノードに含まず、前記暗号化メッセージの復号化を許可する前記復号化装置をいずれかのノードの子孫の末端ノードに含む復号化許可ノードの組を抽出するノード抽出部と、
選択された前記復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれにより前記メッセージを暗号化した複数の前記暗号化メッセージを出力するメッセージ暗号化部と
して機能させる暗号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化通信システム、暗号化装置、復号化装置、暗号化方法、復号化方法、暗号化プログラム、及び復号化プログラムに関する。特に本発明は、複数の復号化装置に対して選択的にメッセージを配信する暗号化通信システム、暗号化装置、復号化装置、暗号化方法、復号化方法、暗号化プログラム、及び復号化プログラムに関する。
【背景技術】
【０００２】
近年、通信ネットワークのブロードバンド化に伴い、デジタルコンテンツの流通が盛んになってきており、コンテンツの保護が重要な課題となっている。コンテンツ保護技術の一つとして、送信者が選択した受信者のみが暗号化された情報を復号できる暗号化方式であるブロードキャスト・エンクリプション（Broadcast Encryption、以下ＢＥと示す。）が、例えばＣＰＲＭ／ＣＰＰＭ等に用いられている（非特許文献１を参照。）。
【０００３】
ＢＥ方式においては、各復号化装置に個別に鍵を管理すると、管理すべき鍵の数が膨大となる。また、各復号化装置用に暗号化した情報を暗号化メッセージに含めることになるため、ブロードキャストする暗号化メッセージのメッセージ長が大きくなってしまう。この問題を解決するために、木構造を用いて鍵を割り当てる方法が提案されている（特許文献１から４、及び非特許文献２から９を参照。）。
【０００４】
非特許文献２においては、木構造を用いたＢＥの代表的な方法であるComplete Subtree方式（以下ＣＳ法）、及びSubset Difference方式（以下ＳＤ法）を開示する。
【０００５】
ＣＳ法においては、各復号化装置は、完全二分木のリーフ（末端ノード）に割り当てられ、末端ノードからルートノードまでの各ノードのノード鍵を記憶しておく。暗号化装置は、メッセージの復号化を禁止する復号化装置を末端ノードに含まず、メッセージの復号化を許可する復号化装置のみを末端ノードに含む完全部分木Siの組を選択する。そして、暗号化装置は、メッセージ本体をタイトル鍵により暗号化し、タイトル鍵を、選択した１又は複数の完全部分木Siの頂点にそれぞれ位置する１又は複数のノードのノード鍵でそれぞれ暗号化して、これらを含む暗号化メッセージをブロードキャストする。これを受けて復号化装置は、当該復号化装置に対応する末端ノードからルートノードに至るまでのいずれかのノードのノード鍵で暗号化されたタイトル鍵を復号化して、復号化したタイトル鍵を用いてメッセージを復号化することができる。
ＣＳ法では、ノードの数をN、メッセージの復号化を禁止する復号化装置の数（無効化する復号化装置の数）をrとすると、各復号化装置は、logN+1の鍵を持つこととなる。ここで、logの底は、k分木を用いる場合kであり、例えば二分木の場合には２である（以下同様）。一方、メッセージ長（タイトル鍵の暗号化に用いるノード鍵の数）は、最悪r・log(N/r)となる。
【０００６】
ＳＤ法においては、各ノードに対応付けて、当該ノードを頂点とする完全部分木の末端ノードの１つがメッセージの復号化を禁止する復号化装置である場合に、当該完全部分木における、当該復号化装置以外の復号化装置が復号化できるノード鍵を更に設ける。
ＳＤ法では、各復号化装置は、((logN)2+logN)/2+1の鍵を持つこととなり、メッセージ長は最悪2r-1、平均1.25rとなる。
【０００７】
非特許文献４は、ＣＳ法及びＳＤ法を融合した方式を開示する。この方式においては、N=215の場合、メッセージ長はＳＤ法と比較し大きくなる。非特許文献５は、無効化する復号化装置の数が全体の半分程度の場合にメッセージ長を約N/3とする。非特許文献３は、木構造のノード鍵を暗号化して公開することにより複数のシステムに対応した木構造管理方法を開示する。この方法においては、暗号化装置は、ノード数に比例した数のノード鍵を公開する。
【特許文献１】特開２００３−２８９２９７号公報
【特許文献２】特開２００３−２７３８５８号公報
【特許文献３】特開２００２−１２３４２９号公報
【特許文献４】特開平１１−１８７０１３号公報
【非特許文献１】A. Fiat and M. Naor、"Broadcast Encryption"、Crypto '93、Lecture Notes in Computer Science (LNCS) 773、p.480-491、１９９４年
【非特許文献２】D. Naor, M. Naor, and J. Lotspiech、"Revocation and Tracing Scheme for Stateless Receivers"、Advances in Cryptology - Crypto 2001、Lecture Notes in Computer Science(LNCS) 2139、Springer、p. 41-62、２００１年
【非特許文献３】松崎、中野、松本、「複数システムに対応した木構造鍵管理方式」、SCIS'02、p.721-726、２００２年
【非特許文献４】奥秋、バグス、太田、「Complete Subtree MethodとSubset Difference Methodを融合したHybrid Systemの提案」、SCIS'03、p.221-226、２００３年
【非特許文献５】金、古原、今井、「許容受信者のおよそ半数の無効化に適したBroadcast Encryption方式」、SICS'03、p.305-309、２００３年
【非特許文献６】浅野、「木構造を用いた効率的なBroadcast Encryption方式」、SCIS'03、p.209-214、２００３年
【非特許文献７】尾形、桧座、ズオング、「RSA暗号を利用した効率的な木構造鍵管理方式」、SCIS'04、p.195-199、２００４年
【非特許文献８】菊地、酒田、「ユーザの秘密鍵サイズを削減したSD法」、SCIS'04、p.83-87、２００４年
【非特許文献９】野島、楫、「落とし戸付き一方向関数を利用した木構造鍵管理方式」、SCIS'03、p.131-136、２００３年
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ＣＳ法においては、メッセージの復号化を禁止する復号化装置の数が増加するにつれて、タイトル鍵の暗号化に用いるノード鍵の数が増加する結果、メッセージ長が増加してしまう。一方、ＳＤ法においては、ＣＳ法と比較しメッセージ長を低減することができるが、各復号化装置が持つべきノード鍵の数が増加してしまう。ＢＥの効率をより高めるためには、ＣＳ法、ＳＤ法、及びその他の従来技術と比較して、各復号化装置が持つべきノード鍵の数を増やさず、かつメッセージ長を大幅に低減する方式が求められる。
【０００９】
そこで本発明は、上記の課題を解決することのできる暗号化通信システム、暗号化装置、復号化装置、暗号化方法、復号化方法、暗号化プログラム、及び復号化プログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【００１０】
本発明の第１の形態によると、メッセージを暗号化する暗号化装置と、暗号化された暗号化メッセージを復号化する複数の復号化装置とを備える暗号化通信システムであって、前記暗号化装置は、複数のノードを接続した第１の木構造における複数の末端ノードのそれぞれに前記複数の復号化装置のそれぞれを対応付けるノード対応情報を、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成するノード対応情報生成部と、前記ノード対応情報により前記複数の復号化装置が対応付けられた前記第１の木構造において、前記暗号化メッセージの復号化を許可する前記復号化装置が子孫の第１末端ノードに対応付けられており、前記暗号化メッセージの復号化を禁止する前記復号化装置が子孫のいずれの第１末端ノードにも対応付けられていない第１の復号化許可ノードを抽出するノード抽出部と、前記第１の復号化許可ノードに対応付けられた第１のノード暗号鍵により前記メッセージを暗号化するメッセージ暗号化部とを有し、前記複数の復号化装置のそれぞれは、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに応じて生成された前記ノード対応情報を取得するノード対応情報取得部と、前記ノード対応情報に基づいて、当該復号化装置が対応付けられた前記第１末端ノードを特定する末端ノード特定部と、当該復号化装置が対応付けられた前記第１末端ノードから前記第１の木構造のルートノードに至るいずれかのノードが前記第１の復号化許可ノードであった場合に、当該第１の復号化許可ノードに対応する第１のノード復号鍵により前記暗号化メッセージを復号化するメッセージ復号化部とを有する暗号化通信システムと、当該暗号化通信システムに関する暗号化装置、復号化装置、暗号化方法、復号化方法、暗号化プログラム、復号化プログラム、及び記録媒体とを提供する。
【００１１】
本発明の第２の形態によると、メッセージを暗号化する暗号化装置と、暗号化された暗号化メッセージを復号化する複数の復号化装置とを備える暗号化通信システムであって、それぞれの前記復号化装置に対応して、公開鍵及び秘密鍵が予め定められており、前記暗号化装置は、複数の前記復号化装置のうち、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない各復号化装置に対応する前記秘密鍵の積に基づくグループ暗号鍵により前記メッセージを暗号化するメッセージ暗号化部を有し、前記複数の復号化装置のそれぞれは、前記複数の復号化装置のうち、当該復号化装置以外の復号化装置に対応する前記秘密鍵の積に基づき定められた当該復号化装置の装置復号鍵を記憶する装置復号鍵記憶部と、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属する、当該復号化装置以外のそれぞれの前記復号化装置に対応する前記公開鍵と、当該復号化装置の前記装置復号鍵とに基づいて、前記暗号化メッセージの復号化を許可する前記復号化装置のグループに属さない前記復号化装置に対応する前記秘密鍵の積に基づく前記暗号化メッセージのグループ復号鍵を生成するグループ復号鍵生成部と、前記グループ復号鍵を用いて前記暗号化メッセージを復号化するメッセージ復号化部とを有する暗号化通信システムと、当該暗号化通信システムに関する暗号化装置、復号化装置、暗号化方法、復号化方法、暗号化プログラム、復号化プログラム、及び記録媒体とを提供する。
【００１２】
本発明の第３の形態によると、メッセージを暗号化する暗号化装置と、暗号化された暗号化メッセージを復号化する複数の復号化装置とを備える暗号化通信システムであって、前記暗号化装置は、複数の前記復号化装置のそれぞれを末端ノードとし、複数のノードを接続した木構造を複数記憶する木構造記憶部と、前記暗号化メッセージの復号化を許可する前記復号化装置の組に基づいて、いずれかの前記木構造を選択する木構造選択部と、選択された前記木構造について、前記暗号化メッセージの復号化を禁止する前記復号化装置を子孫の末端ノードに含まず、前記暗号化メッセージの復号化を許可する前記復号化装置をいずれかのノードの子孫の末端ノードに含む復号化許可ノードの組を抽出するノード抽出部と選択された前記復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれにより前記メッセージを暗号化した複数の前記暗号化メッセージを出力するメッセージ暗号化部とを有し、前記複数の復号化装置のそれぞれは、前記ノードの組の選択元となった前記木構造において、当該復号化装置に対応する末端ノードからルートノードに至る経路上に位置するノードのうち、選択された前記復号化許可ノードを特定するノード特定部と、前記復号化許可ノードの組の選択元となった前記木構造における前記ノード特定部により特定された前記復号化許可ノードに対応付けられたノード復号鍵を取得するノード復号鍵取得部と、取得された前記ノード復号鍵を用いて、前記ノード特定部により特定された前記復号化許可ノードに対応付けられた前記ノード暗号鍵により暗号化された前記暗号化メッセージを復号化するメッセージ復号化部とを有する暗号化通信システムと、当該暗号化通信システムに関する暗号化装置、復号化装置、暗号化方法、復号化方法、暗号化プログラム、復号化プログラム、及び記録媒体とを提供する。
【００１３】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００１４】
本発明によれば、複数の復号化装置に選択的にメッセージを送信する場合において、暗号化メッセージのメッセージ長を低減することができる。
【発明を実施するための最良の形態】
【００１５】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１６】
図１は、本実施形態に係る暗号化通信システム１０の構成を示す。暗号化通信システム１０は、暗号化装置１００と、複数の復号化装置１１０と、ネットワーク１２０とを備え、各復号化装置１１０に記憶する鍵の数を抑えつつ、暗号化装置１００から復号化装置１１０へ送信する暗号化メッセージのメッセージ長を低減するブロードキャスト・エンクリプションを実現する。
暗号化装置１００は、全ての復号化装置１１０のうち、予め指定された復号化装置１１０のみが復号化できるようにメッセージを暗号化して、暗号化メッセージを出力する。復号化装置１１０のそれぞれは、暗号化メッセージの復号化を許可されている場合において、暗号化された暗号化メッセージを復号化する。ここで復号化装置１１０は、例えばＰＣ（パーソナルコンピュータ）、ＰＤＡ、携帯電話、又は情報家電等の情報処理装置である。また、２以上の復号化装置１１０が１台のコンピュータにより実現されてもよい。すなわち例えば、当該コンピュータは、第１の利用者が当該コンピュータを利用する場合に第１の復号化装置１１０として機能し、第２の利用者が当該コンピュータを利用する場合に第２の復号化装置１１０として機能してもよい。ネットワーク１２０は、暗号化装置１００と復号化装置１１０との間の通信を中継する。
【００１７】
以上において、メッセージは、例えばデジタルコンテンツ等であり、暗号化装置１００により暗号化され、復号化装置１１０に対して送信される。これに代えて、メッセージは、例えばＣＤやＤＶＤ等の記録媒体に記録された情報であってもよい。この場合、メッセージは、暗号化装置１００により暗号化されて記録媒体に記録され、復号化を許可された復号化装置１１０により読み出されて復号化される。
【００１８】
図２は、本実施形態に係る暗号化通信システム１０により鍵を管理する木構造を示す。本実施形態に係る暗号化通信システム１０は、暗号化メッセージの復号化に用いる復号鍵を、図２に示した木２００により管理する。
【００１９】
木２００は、複数の復号化装置１１０のそれぞれを末端ノード（リーフ）のそれぞれとし、複数のノードを接続した木構造である。より具体的には、木２００は、ルートノードv1から順に、１つの親ノードに対して１以上の子ノードを接続していくことにより構成され、子ノードを持たない末端ノードのそれぞれに復号化装置１１０が対応付けられる。本実施形態においては、木２００は２分木である場合を例として説明するが、他の形態の木構造であってもよい。以下、復号化装置１１０の総数がN（Nは２のべき乗の数）である場合を例として説明する。
【００２０】
木２００は、上位木２１０と、複数の下位部分木２２０とを備える。上位木２１０は、木２００のルートノードをルートノードとし、複数の下位部分木２２０のそれぞれのルートノードを複数の第２末端ノードとして接続する木構造を有する。本実施形態に係る上位木２１０は、木２００の１段目からh段目（1≦h≦logN-1）までの上位部分のノードにより構成され、各ノードにはv1からvw-1までの符号が幅優先で割り振られる（ただし、w=2h）。そして、各ノードには、互いに異なるノード鍵Lj（j=1,2,…,w-1）が割り当てられる。このノード鍵は、メッセージの暗号鍵及び復号鍵として用いられる。これに代えて、各ノードには、非対称の暗号鍵及び復号鍵が割り当てられてもよい。
【００２１】
それぞれの下位部分木２２０は、当該下位部分木２２０に対応付けられた複数の復号化装置１１０のそれぞれを第１末端ノードとし、複数のノードを接続した木構造である。複数の下位部分木２２０（Si（i=1,2,…,w/2）と示す）のそれぞれは、上位木２１０の末端ノードであるvw/2-1+iをルートノードとする。i番目（i=1,2,…w/2）の下位部分木２２０の各ノードには、vi,1からvi,2y-1までの符号が幅優先で割り振られる（ただし、y=2N/w）。そして、各ノードには、互いに異なるノード鍵Li,l（l=1,2,…2y-1）が割り当てられる。このノード鍵は、メッセージの暗号鍵及び復号鍵として用いられる。下位部分木２２０の各末端ノードvi,y, …, vi,2y-1には、当該下位部分木２２０に対応付けられた各復号化装置１１０（ui,j（j=1,2,…y）と示す）が対応付けられる。
【００２２】
暗号化装置１００は、十分大きい互いに異なるw/2個の素数の組（pi,qi）を予め定め、ni=piqiを用意する。このniは、Siの下位部分木２２０の暗号系における法として用いられる。また、それぞれの復号化装置１１０に対応して、公開鍵ej及び秘密鍵di,jを予め定める。ここで、公開鍵ej（j=1,…,y）は、互いに異なるy個の素数であり、mini(ni)以下の数である。また、N組の(ej, di,j)（i=1,2,…,w/2、j=1,2,…,y）は、niを法とするＲＳＡ暗号系における公開鍵及び暗号鍵の組である。
そして、暗号化装置１００は、全てのejを各復号化装置１１０に公開し、di,jを秘密に保持する。ここで、各復号化装置１１０は、全てのejを予め記憶しておいてもよく、ejを生成するプログラムを保持してもよい。また、復号化装置１１０には、当該復号化装置１１０が接続された下位部分木２２０に対応するniが予め設定される。
【００２３】
Siで示される下位部分木２２０に対応付けられた復号化装置１１０は、当該下位部分木２２０のルートノードから木２００のルートノードに至る経路上のh個のノードのノード鍵と、以下の式（１）に示す当該復号化装置１１０の装置鍵（装置復号鍵）Ii,jとを秘密に保持する。
【数１】
2006013790.tif 000003
【００２４】
これらの装置鍵Ii,jは、下位部分木２２０の末端ノードのノード鍵としても用いられる。
【００２５】
以上において、各復号化装置１１０は、当該復号化装置１１０に対応付けられた下位部分木２２０の末端ノードから木２００のルートノードに至るまでの各ノードに対応するノード復号鍵を使用することができる。より具体的には、復号化装置１１０は、この経路上の上位木２１０内のノードに対応するノード復号鍵を予め記憶する。また、復号化装置１１０は、この経路上の下位部分木２２０内のノードに対応するノード復号鍵を、上記の装置鍵（装置復号鍵）から生成する。一方、各復号化装置１１０は、これ以外のノードに対応するノード復号鍵を使用することができない。
【００２６】
暗号化装置１００は、木２００の各ノードのうち、暗号化メッセージの復号化を許可する復号化装置１１０を子孫の末端ノードに含み、復号化を許可しない復号化装置１１０を子孫の末端ノードに含まないノードを復号化許可ノードとして選択し、当該復号化許可ノードに対応するノード暗号鍵によりメッセージを暗号化する。これにより、暗号化装置１００は、当該復号化許可ノードの子孫の末端ノードに対応する復号化装置１１０のみが復号化できる暗号化メッセージを生成することができる。なお、暗号化装置１００は、上記の復号化許可ノードを複数選択し、これらの復号化許可ノードに対応する各ノード暗号鍵によりそれぞれ暗号化された複数の暗号化メッセージを各復号化装置１１０へ送信してもよい。この場合、各復号化装置１１０は、いずれかのノード暗号鍵に対応するノード復号鍵を使用可能であれば、当該ノード暗号鍵により暗号化された暗号化メッセージを復号化することができる。
【００２７】
本実施形態に係る暗号化装置１００は、メッセージの暗号化に用いるノード暗号鍵の数を大幅に削減することを目的として、各下位部分木２２０に対応する複数の復号化装置１１０を下位部分木２２０の末端ノードのいずれに対応付けるかを、暗号化メッセージの復号化を許可する復号化装置１１０の組に応じて動的に選択する。これにより暗号化装置１００は、複数の復号化装置１１０を下位部分木２２０内で並べ替え、暗号化に用いるノード暗号鍵の数を最小化し、メッセージ長を削減することができる。
【００２８】
図３は、本実施形態に係る暗号化装置１００の構成を示す。暗号化装置１００は、メッセージと、復号化を許可する復号化装置１１０の組を識別する情報とを受けて、これらの復号化装置１１０のみが復号化できる暗号化メッセージを生成し、復号化装置１１０へ送信する。暗号化装置１００は、ノード対応情報生成部３００と、ノード抽出部３１０と、上位ノード暗号鍵生成部３２０と、下位ノード暗号鍵生成部３３０と、メッセージ暗号化部３４０とを備える。
【００２９】
ノード対応情報生成部３００は、復号化を許可する復号化装置１１０のグループの指定を受けて、各下位部分木２２０について、末端ノードに復号化装置１１０を対応付けるノード対応情報をメッセージ毎に生成する。ノード抽出部３１０は、複数の下位部分木２２０の木構造と、複数の下位部分木２２０のそれぞれのルートノードを複数の末端ノードとして接続する上位木２１０の木構造を記憶する。ノード抽出部３１０は、ノード対応情報を受けると、各下位部分木２２０に各復号化装置１１０を対応付ける。そして、ノード抽出部３１０は、暗号化メッセージの復号化を許可する復号化装置１１０を子孫の末端ノードに含み、復号化を禁止する復号化装置１１０を子孫の末端ノードに含まないノードの組を、復号化許可ノードの組として抽出する。
【００３０】
上位ノード暗号鍵生成部３２０は、抽出した復号化許可ノードのうち、上位木２１０内の復号化許可ノードに対応するノード暗号鍵を生成する。下位ノード暗号鍵生成部３３０は、本発明に係るノード暗号鍵生成部の一例であり、抽出した復号化許可ノードのうち、いずれかの下位部分木２２０内の復号化許可ノードに対応するノード暗号鍵を生成する。メッセージ暗号化部３４０は、各復号化許可ノードに対応するノード暗号鍵によりメッセージを暗号化して暗号化メッセージを生成し、復号化装置１１０へ送信する。
【００３１】
暗号化装置１００は、公開鍵乗算部３５０と、公開部３６０とを更に備えてもよい。
公開鍵乗算部３５０は、暗号化メッセージの復号化を許可する各復号化装置１１０がノード復号鍵を生成するために用いる公開鍵ejの積を算出する。公開部３６０は、公開鍵乗算部３５０により算出された公開鍵の積を、復号化装置１１０に対して公開する。
【００３２】
図４は、本実施形態に係る暗号化装置１００の動作フローを示す。
まず、ノード対応情報生成部３００は、復号化を許可する復号化装置１１０のグループの指定を受ける。そしてノード対応情報生成部３００は、復号化を許可する復号化装置１１０を１以上含む下位部分木２２０のそれぞれについて、下位部分木２２０における複数の末端ノードのそれぞれに複数の復号化装置１１０のそれぞれを対応付けるノード対応情報を、暗号化メッセージの復号化を許可する復号化装置１１０のグループに応じて生成する（Ｓ４００）。ここで、ノード対応情報生成部３００は、それぞれの下位部分木２２０について、ノード抽出部３１０が抽出する下位部分木２２０の復号化許可ノードの数を最小とするノード対応情報を生成する。
【００３３】
より具体的には、ノード対応情報生成部３００は、復号化を許可する復号化装置１１０を１以上含む下位部分木２２０であるSiについて、ノード対応情報として、並べ替えの方法を示すτi(…)を生成し、復号化装置１１０へ公開する。ここで、τi(…)は、集合{1,…,y}から{1,…,y}に対する全単射関数であり、ui,jの復号化装置１１０がSiのτi(j)番目の末端ノードに対応付けられることを示す。これに代えて、ノード対応情報生成部３００は、ノード対応情報として、複数の復号化装置１１０のそれぞれについて暗号化メッセージの復号化の許可／禁止をフラグにより表したビットマップを生成してもよい。このノード対応情報を用いることで、ノード対応情報生成部３００は、複数の復号化装置１１０を、メッセージ毎に動的に各末端ノードに対応付けることができる。そしてノード対応情報生成部３００は、例えば、下位部分木２２０における左側（vi,yに近い側）に復号化を許可する復号化装置１１０を連続して配置することにより、下位部分木２２０において暗号化メッセージを許可する全ての復号化装置１１０を子孫に有する復号化許可ノードの組のノード数を低減することができる。
【００３４】
次に、ノード抽出部３１０は、ノード対応情報により複数の復号化装置１１０が対応付けられた木２００において、暗号化メッセージの復号化を許可する復号化装置１１０が子孫の末端ノードに対応付けられており、暗号化メッセージの復号化を禁止する復号化装置１１０が子孫のいずれの末端ノードにも対応付けられていない復号化許可ノードの組を抽出する（Ｓ４１０）。この際、ノード抽出部３１０は、暗号化メッセージの復号化を許可する全ての復号化装置１１０がいずれかの復号化許可ノードの子孫の末端ノードに対応付けられた復号化許可ノードの組のうち、復号化許可ノードの数を最小とする復号化許可ノードの組を抽出する。
【００３５】
ここで、ノード抽出部３１０は、少なくとも１つの下位部分木２２０に接続された全ての末端ノードに対応する復号化装置１１０に対し暗号化メッセージの復号化を許可する場合に、当該下位部分木２２０のルートノードを子孫の末端ノードとして接続し、暗号化メッセージの復号化を許可しない復号化装置１１０が末端ノードに対応付けられた下位部分木２２０のルートノードを子孫の末端ノードとして接続しない復号化許可ノードを抽出する。これにより、下位部分木２２０に接続された全ての復号化装置１１０に復号化を許可する場合において、復号化装置１１０が下位部分木２２０の末端ノードから多数のノードを遡ってノード復号鍵を生成するのに要する計算コストを低減することができる。
【００３６】
次に、上位ノード暗号鍵生成部３２０及び下位ノード暗号鍵生成部３３０は、抽出した復号化許可ノードのそれぞれに対応するノード暗号鍵を生成する（Ｓ４２０）。すなわち上位ノード暗号鍵生成部３２０は、抽出した復号化許可ノードのうち、上位木２１０内の復号化許可ノードに対応するノード暗号鍵を生成する。例えば上位ノード暗号鍵生成部３２０は、非特許文献９に開示された落とし戸付き一方向関数を利用してノード暗号鍵を生成する。これに代えて上位ノード暗号鍵生成部３２０は、上位木２１０内の全ノードに対応するノード暗号鍵を予め格納しておき、抽出した復号化許可ノードに対応してノード暗号鍵を選択してもよい。
【００３７】
また、下位ノード暗号鍵生成部３３０は、抽出した復号化許可ノードのうち、いずれかの下位部分木２２０内の復号化許可ノードに対応するノード暗号鍵を生成する。本実施形態に係る下位ノード暗号鍵生成部３３０は、Siの下位部分木２２０内における復号化許可ノードvi,lのノード暗号鍵Li,lを、以下の式（２）により生成する。
【数２】
2006013790.tif 000004
【００３８】
なお、Ui,lは、ノード対応情報により各復号化装置１１０と各末端ノードの対応付けが変更された後における、当該復号化許可ノードをルートノードとする部分木に接続された全ての復号化装置１１０（ui,j）のjについての集合である。すなわち、下位ノード暗号鍵生成部３３０は、当該下位部分木２２０に対応付けられた複数の復号化装置１１０のうち、復号化許可ノードの子孫の各末端ノードに対応付けられていない各復号化装置１１０に対応する秘密鍵di,jの積Ti/αi,jに基づくノード暗号鍵Li,lを生成する。より具体的には、下位ノード暗号鍵生成部３３０は、上位木２１０の末端ノードに対応する予め定められたノード暗号鍵を、当該復号化許可ノードの子孫の末端ノードに対応付けられた各復号化装置１１０に対応する秘密鍵の積Ti/αi,jによりべき乗した値のniによる法を求め、当該べき乗値に基づくノード暗号鍵を生成する。
【００３９】
次に、メッセージ暗号化部３４０は、復号化許可ノードに対応付けられたノード暗号鍵によりメッセージを暗号化する（Ｓ４３０）。すなわち、メッセージ暗号化部３４０は、抽出された復号化許可ノードの組に属するそれぞれの復号化許可ノードに対応するノード暗号鍵のそれぞれによりメッセージを暗号化した１又は複数の暗号化メッセージを生成する。ここで、それぞれの暗号化メッセージは、いずれかの下位部分木２２０内の復号化許可ノードに対応付けられたノード暗号鍵、又は、上位木２１０内の復号化許可ノードに対応付けられたノード暗号鍵により暗号化されたものとなる。
【００４０】
より具体的には、メッセージ暗号化部３４０は、メッセージMを暗号化するためのタイトル鍵Kを決定し、復号化許可ノードの組{s1,…,sm}に対応するノード暗号鍵Ls1,…, Lsmを用いて、以下の内容を含むブロードキャスト用のメッセージを生成する。
【数３】
2006013790.tif 000005
【００４１】
ただし、ELx(K)は、タイトル鍵Kをノード暗号鍵Lxにより暗号化する関数であり、Fx(M)はメッセージMをタイトル鍵Kにより暗号化する関数である。式（３）に示したメッセージは、復号化許可ノードの組に属する各復号化許可ノードのノード番号s1, …, smと、ノード暗号鍵Ls1により暗号化されたタイトル鍵、…、及びノード暗号鍵Lsmにより暗号化されたタイトル鍵と、タイトル鍵により暗号化されたメッセージMとを含む。このように、メッセージMをタイトル鍵Kで暗号化し、タイトル鍵Kをノード暗号鍵Ls1により暗号化することで、メッセージMは、ノード暗号鍵Ls1により間接的に暗号化される。
【００４２】
次に、メッセージ暗号化部３４０は、式（３）に示したブロードキャスト用のメッセージを全ての復号化装置１１０に対して送信することにより出力する（Ｓ４４０）。
【００４３】
次に、公開鍵乗算部３５０は、暗号化メッセージの復号化を許可する各復号化装置１１０がノード復号鍵を生成するために用いる公開鍵ejの積を算出する（Ｓ４５０）。より具体的には、公開鍵乗算部３５０は、それぞれの復号化装置１１０に対応して、ノード抽出部３１０により抽出された下位部分木２２０の各復号化許可ノードについて、当該復号化許可ノードvi,lの子孫の各末端ノードに対応する、当該復号化装置１１０以外のそれぞれの復号化装置１１０に対応する公開鍵の積βi,lを算出する（以下の式（４）参照）。
【数４】
2006013790.tif 000006
【００４４】
次に、公開部３６０は、公開鍵乗算部３５０により算出された公開鍵の積を複数の復号化装置１１０に対して公開する（Ｓ４６０）。これにより、復号化装置１１０において公開鍵の積を算出する必要がなくなり、復号化装置１１０の計算負荷を低減することができる。
【００４５】
以上に示した暗号化装置１００によれば、暗号化メッセージの復号化を許可する復号化装置１１０の組に応じて、下位部分木２２０の末端ノードに対する復号化装置１１０の対応付けを動的に組み替えることにより、暗号化に用いるノード暗号鍵の数を大幅に削減することができる。
【００４６】
なお、以上に示した暗号化通信システム１０は、例えばテレビ番組等の番組を配信する場合、番組を構成する複数のメッセージを順次配信する。ここで、例えばコンテンツ配信会社がＰＰＶ（Pay Per View）の番組を配信するために用いられる場合において、暗号化装置１００は、番組の途中で利用料金を支払った利用者の復号化装置１１０に対し、新たに暗号化メッセージの復号化を許可する必要がある。これを実現するため暗号化装置１００は、復号化許可ノードの組を変更する。
【００４７】
この際、復号化許可ノードの組を大幅に変更すると、多くの復号化装置１１０において復号鍵の再計算が必要となってしまう。そこで、ノード対応情報生成部３００は、新たに利用者が加わった場合においても、復号化許可ノードの組をなるべく変更しないようにする。すなわち、第１の暗号化メッセージを出力した後、暗号化メッセージの復号化を許可する復号化装置１１０の組が第１の暗号化メッセージと異なる第２の暗号化メッセージを出力する場合において、ノード対応情報生成部３００は、復号鍵が変更される復号化装置１１０の数を最小とするようなノード対応情報を生成する。より具体的には、ノード対応情報生成部３００は、第１の暗号化メッセージの復号化を許可した復号化装置１１０であって、第２の暗号化メッセージの復号化を許可する既存の復号化装置１１０を、第１の暗号化メッセージの暗号化において対応付けた末端ノードと同一の末端ノードに対応付けるノード対応情報を生成し、復号鍵が変更される復号化装置１１０の数を最小化する。
更に、ノード対応情報生成部３００は、第２の暗号化メッセージに対応してノード抽出部３１０が抽出する復号化許可ノードの数を最小とするノード対応情報を生成する。一例として、ノード対応情報生成部３００は、下位部分木２２０における左側（vi,yに近い側）に復号化を許可された復号化装置１１０を連続して配置し、新たに復号化を許可された復号化装置１１０を既に復号化を許可された復号化装置１１０の右側に隣接して配置することにより、復号化許可ノードの数を最小化することができる。
【００４８】
図５は、本実施形態に係る復号化装置１１０の構成を示す。復号化装置１１０は、暗号化装置１００により暗号化された暗号化メッセージを受信して復号化する。復号化装置１１０は、ノード対応情報取得部５００と、末端ノード特定部５１０と、上位ノード復号鍵記憶部５２０と、上位ノード復号鍵取得部５３０と、装置復号鍵記憶部５４０と、下位ノード復号鍵生成部５５０と、メッセージ復号化部５６０とを備える。
【００４９】
ノード対応情報取得部５００は、暗号化メッセージを暗号化するために用いたノード対応情報を、暗号化装置１００から取得する。末端ノード特定部５１０は、ノード対応情報に基づいて、当該復号化装置１１０に対応する下位部分木２２０の末端ノードを特定する。上位ノード復号鍵記憶部５２０は、本発明に係るノード復号鍵記憶部の一例であり、当該復号化装置１１０が末端ノードに対応付けられた下位部分木２２０のルートノードに対応する上位木２１０の末端ノードから、上位木２１０のルートノードに至る各ノードに対応するノード復号鍵のそれぞれを記憶する。上位ノード復号鍵取得部５３０は、暗号化メッセージが上位木２１０内の復号化許可ノードに対応するノード暗号鍵により暗号化されていた場合に、当該復号化許可ノードに対応するノード復号鍵を上位ノード復号鍵記憶部５２０から取得する。
【００５０】
装置復号鍵記憶部５４０は、式（１）に示した当該復号化装置１１０の装置復号鍵Ii,jを記憶する。装置復号鍵Ii,jは、式（１）に示したように、当該復号化装置１１０が属する下位部分木２２０に対応付けられた複数の復号化装置１１０のうち、当該復号化装置１１０以外の復号化装置１１０に対応する秘密鍵di,jの積Ti/di,jに基づき定められる。より具体的には、装置復号鍵Ii,jは、予め定められた数である上位木２１０の末端ノードのノード鍵を、秘密鍵の積Ti/di,jによりべき乗した値をniによる法を求めることにより定められる。下位ノード復号鍵生成部５５０は、暗号化メッセージが下位部分木２２０内の復号化許可ノードに対応するノード暗号鍵により暗号化されていた場合に、当該復号化許可ノードに対応するノード復号鍵を装置復号鍵Ii,jに基づいて生成する。メッセージ復号化部５６０は、上位ノード復号鍵取得部５３０又は下位ノード復号鍵生成部５５０により取得又は生成されたノード復号鍵により暗号化メッセージを復号化する。
【００５１】
図６は、本実施形態に係る復号化装置１１０の動作フローを示す。
ノード対応情報取得部５００は、暗号化メッセージの復号化を許可する復号化装置１１０のグループに応じて生成されたノード対応情報を、暗号化装置１００から取得する（Ｓ６００）。次に、末端ノード特定部５１０は、ノード対応情報に基づいて、当該復号化装置１１０に対応する下位部分木２２０における、当該復号化装置１１０が対応付けられた末端ノードを特定する（Ｓ６１０）。
【００５２】
次に上位ノード復号鍵取得部５３０及び下位ノード復号鍵生成部５５０は、暗号化メッセージの暗号化に用いたノード暗号鍵に対応するノード復号鍵を上位ノード復号鍵記憶部５２０から取得し、又は装置復号鍵に基づき生成する（Ｓ６２０）。すなわち、上位ノード復号鍵取得部５３０は、暗号化装置１００によりブロードキャストされたメッセージに含まれる１つの暗号化メッセージが上位木２１０のノード暗号鍵により暗号化されていた場合において、当該ノード暗号鍵に対応するノード復号鍵を上位ノード復号鍵記憶部５２０から取得する。より具体的には、上位ノード復号鍵取得部５３０は、当該復号化装置１１０が末端ノードに対応付けられた下位部分木２２０のルートノードに対応する上位木２１０の末端ノードから、上位木２１０のルートノードに至るいずれかのノードが復号化許可ノードであった場合に、当該復号化許可ノードに対応するノード復号鍵を上位ノード復号鍵記憶部５２０から読み出す。
【００５３】
また、下位ノード復号鍵生成部５５０は、暗号化装置１００によりブロードキャストされたメッセージに含まれる１つの暗号化メッセージが下位部分木２２０のノード暗号鍵により暗号化されていた場合において、当該ノード暗号鍵に対応するノード復号鍵を生成する。すなわち下位ノード復号鍵生成部５５０は、当該復号化装置１１０が対応付けられた下位部分木２２０の末端ノードから下位部分木２２０のルートノードに至るいずれかのノードが復号化許可ノードであった場合に、当該復号化許可ノードに対応するノード復号鍵を生成する。
【００５４】
本実施形態に係る下位ノード復号鍵生成部５５０は、当該復号化装置１１０（ui,x）の装置復号鍵Ii,xと、当該復号化許可ノードの子孫の各末端ノードに対応する、当該復号化装置１１０以外のそれぞれの復号化装置１１０に対応する公開鍵ekとに基づいて、ノード復号鍵Li,lを生成する。より具体的には、下位ノード復号鍵生成部５５０は、当該復号化装置１１０の装置復号鍵を、当該復号化許可ノードの子孫の各末端ノードに対応する、当該復号化装置１１０以外のそれぞれの復号化装置１１０の公開鍵ekの積βi,l/exによりべき乗した値に基づいて、式（２）に示したノード暗号鍵と同一の値のノード復号鍵Li,lを生成する（式（５））。
【数５】
2006013790.tif 000007
【００５５】
このノード復号鍵Li,lは、当該下位部分木２２０に対応付けられた複数の復号化装置１１０のうち、暗号化メッセージの復号化を許可する復号化装置１１０のグループに属さない復号化装置１１０に対応する秘密鍵di,kの積に基づく。
【００５６】
式（５）においては、ＲＳＡ暗号系の公開鍵e及び暗号鍵dについて、Ae・d≡A（mod ni）となることを利用している。すなわち、装置復号鍵Ii,lの公開鍵の積βi,l/exによるべき乗を求めることにより、式（１）におけるAiの乗数部分である、当該復号化装置１１０以外の復号化装置１１０の暗号鍵の積Ti/di,jに、復号化を許可する復号化装置１１０の公開鍵の積βi,j/ejを乗じ、復号化を許可する復号化装置１１０の暗号鍵di,jを乗数から除く。これにより、下位ノード復号鍵生成部５５０は、暗号化装置１００により生成されたノード暗号鍵と同一のノード復号鍵を得ることができる。
【００５７】
次に、メッセージ復号化部５６０は、上位ノード復号鍵取得部５３０又は下位ノード復号鍵生成部５５０により取得又は生成されたノード復号鍵により暗号化メッセージを復号化する（Ｓ６３０）。すなわち、メッセージ復号化部５６０は、以下の式（６）に示したブロードキャストメッセージから、当該復号化装置１１０に対応する復号化許可ノードslを探す。
【数６】
2006013790.tif 000008
【００５８】
次に、メッセージ復号化部５６０は、復号化許可ノードslに対応するノード復号鍵Lslを用いて、以下の式（７）によりタイトル鍵Kを復号化する。
【数７】
2006013790.tif 000009
【００５９】
ここで、D()は、E()に対応する復号化の関数である。
【００６０】
そして、メッセージ復号化部５６０は、復号化されたタイトル鍵Kを用いて、以下の式（８）によりメッセージを復号化する。
【数８】
2006013790.tif 000010
【００６１】
以上に示した暗号化通信システム１０によれば、秘密鍵di,jは暗号化装置１００により管理され、復号化装置１１０に対しては秘密にされる。また、各復号化装置１１０は、下位部分木２２０に対応する復号化装置１１０のうち、当該復号化装置１１０以外の秘密鍵di,jに基づく装置復号鍵Ii,jを他の復号化装置１１０に対して秘密に管理する。そして、各復号化装置１１０は、メッセージの復号化を許可する他の復号化装置１１０に対応する公開鍵ejを用いて、秘密鍵di,jを装置復号鍵Ii,jを構成する乗数から取り除いていくことにより、ノード復号鍵Li,lを生成することができる。
【００６２】
一方、メッセージの復号化を禁止された復号化装置１１０は、当該復号化装置１１０に対応する暗号鍵di,jを持たないため、当該復号化装置１１０が有する装置復号鍵Ii,jを構成するべき乗数に当該暗号鍵di,jを加えることができない。また、メッセージの復号化を禁止された複数の復号化装置１１０が装置復号鍵を交換したとしても、当該復号化装置１１０が有する装置復号鍵Ii,jを構成するべき乗数に、メッセージの復号化を禁止された復号化装置１１０の暗号鍵di,jを加えることができない。したがって、メッセージの復号化を禁止された復号化装置１１０は、復号化許可ノードに対応するノード復号鍵を生成することができず、メッセージの機密性が保たれる。
【００６３】
なお、本実施形態に係る暗号化通信システム１０は、木２００の下位階層を木構造を用いて管理しているが、これに代えて暗号化通信システム１０は、木２００の下位階層を他の方法により管理してもよい。例えば暗号化通信システム１０は、各下位部分木２２０に対応する複数の復号化装置１１０のうち、復号化を許可する任意の復号化装置１１０の組を動的に選択してグループ化してもよい。
【００６４】
より具体的には、ノード対応情報生成部３００は、グループ対応情報生成部として機能し、上位木２１０の各末端ノードについて、当該末端ノードに対応付けられた複数の復号化装置１１０のうち暗号化メッセージの復号化を許可する復号化装置１１０のグループを動的に生成する。そして、当該グループに属する復号化装置１１０を識別するグループ情報をノード抽出部３１０及びネットワーク１２０へ出力する。ノード抽出部３１０は、木２００については復号化許可ノードを抽出し、上位ノード暗号鍵生成部３２０へ出力する。一方、下位階層について、グループ情報を下位ノード暗号鍵生成部３３０へ出力する。下位ノード暗号鍵生成部３３０は、下位階層の暗号鍵生成部として機能し、複数の復号化装置１１０のうち、暗号化メッセージの復号化を許可する復号化装置１１０のグループに属さない各復号化装置１１０に対応する秘密鍵di,jの積に基づくグループ暗号鍵を、ノード暗号鍵と同様にして算出する。そして、メッセージ暗号化部３４０は、上位ノード暗号鍵生成部３２０から出力されたノード暗号鍵又は下位ノード暗号鍵生成部３３０により生成されたグループ暗号鍵によりメッセージを暗号化する。
【００６５】
この場合、ノード対応情報取得部５００は、グループ情報取得部として機能し、暗号化装置１００により生成されたグループ情報を取得する。下位ノード復号鍵生成部５５０は、グループ復号鍵生成部として機能し、暗号化メッセージの復号化を許可する復号化装置１１０のグループに属するそれぞれの復号化装置１１０に対応する公開鍵ejと、当該復号化装置１１０の装置復号鍵Ii,jとに基づいて、暗号化メッセージの復号化を許可する復号化装置１１０のグループに属さない復号化装置１１０に対応する秘密鍵di,kの積に基づく暗号化メッセージのグループ復号鍵Li,lを生成する。そして、メッセージ復号化部５６０は、木２００の下位階層については、グループ復号鍵Li,lを用いて暗号化メッセージを復号化する。
【００６６】
図７は、本実施形態の変形例に係る暗号化通信システム１０における暗号化装置１００の構成を示す。本変形例に係る暗号化通信システム１０は、複数の木構造のうち、復号化許可ノードの数が最小となる木構造を選択することにより、メッセージ長を低減する。
【００６７】
本変形例に係る暗号化装置１００は、木構造記憶部７１０と、木構造選択部７００と、ノード抽出部３１０と、ノード暗号鍵生成部７２０と、メッセージ暗号化部３４０とを備える。木構造記憶部７１０は、木構造を複数記憶する。ここで、木構造記憶部７１０は、互いに異なる復号化装置１１０の種類又は復号化装置１１０の利用者の各種の特性に基づいて、より類似する種類又は特性を有する復号化装置１１０の組を、末端ノードにより近い復号化許可ノードの子孫の末端ノードにそれぞれ対応付けた複数の木構造を記憶する。例えば、木構造記憶部７１０は、復号化装置１１０として機能する情報処理装置がＰＣ、ＰＤＡ、又は携帯電話等のいずれであるか、復号化装置１１０として機能する情報処理装置の製造元、又は、利用者の年齢、性別、住所、嗜好、及び所属する団体等の特性に基づく木構造を複数種類記憶する。
【００６８】
木構造選択部７００は、暗号化メッセージの復号化を許可する復号化装置１１０の組に基づいて、いずれかの木構造を選択し、選択した木構造を特定する木構造選択情報をノード抽出部３１０及びネットワーク１２０へ出力する。ノード抽出部３１０は、図３に示したノード抽出部３１０と同様にして、選択された木構造について、復号化許可ノードの組を抽出する。ノード暗号鍵生成部７２０は、上位ノード暗号鍵生成部３２０と同様にして、各復号化許可ノードに対応するノード暗号鍵を生成する。メッセージ暗号化部３４０は、図３に示したメッセージ暗号化部３４０と同様にして、選択された復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれによりメッセージを暗号化する。
【００６９】
図８は、本実施形態の変形例に係る暗号化装置１００の動作フローを示す。
まず、木構造選択部７００は、暗号化メッセージの復号化を許可する復号化装置１１０の組に基づいて、いずれかの木構造を選択する（Ｓ８００）。ここで木構造選択部７００は、それぞれの木構造について選択された復号化許可ノードの組のうち、復号化許可ノードの数が最小となるノードの組を選択する。これに代えて、木構造選択部７００は、暗号化メッセージの復号化を許可する復号化装置１１０の種類又は利用者の特性に基づいて、いずれかの木構造を選択してもよい。すなわち例えば、配信するコンテンツの番組を視聴する可能性が高い利用者の年齢や性別等の特性に基づいて、当該特性に基づいて定められた木構造を選択する。
【００７０】
ノード抽出部３１０は、図４のＳ４１０と同様にして、暗号化メッセージの復号化を禁止する復号化装置１１０を子孫の末端ノードに含まず、暗号化メッセージの復号化を許可する復号化装置１１０をいずれかのノードの子孫の末端ノードに含む復号化許可ノードの組を抽出する（Ｓ４１０）。次に、ノード暗号鍵生成部７２０は、図４のＳ４２０と同様にして、復号化許可ノードの組に属するそれぞれの復号化許可ノードに対応するノード暗号鍵を生成する（Ｓ４２０）。この際、ノード暗号鍵生成部７２０は、非特許文献９に記載された落とし戸付き一方向性関数を利用し、ルートノードに対応するノード暗号鍵から開始して、親ノードのノード暗号鍵から子ノードのノード暗号鍵を順次生成していくことにより、各復号化許可ノードのノード暗号鍵を生成してもよい。
【００７１】
次に、メッセージ暗号化部３４０は、選択された復号化許可ノードの組に属する各復号化許可ノードに対応付けられた各ノード暗号鍵のそれぞれによりメッセージを暗号化する（Ｓ４３０）。より具体的には、メッセージ暗号化部３４０は、メッセージをタイトル鍵で暗号化し、タイトル鍵を各ノード暗号鍵のそれぞれにより暗号化することにより、各ノード暗号鍵で間接的に暗号化された暗号化メッセージを包含するブロードキャスト用のメッセージを生成する。そして、複数の暗号化メッセージを含むブロードキャスト用のメッセージを各復号化装置１１０へ送信する（Ｓ８３０）。
【００７２】
本変形例に係る暗号化装置１００によれば、暗号化メッセージの復号化を許可する復号化装置１１０の組に応じて木構造を動的に選択することにより、暗号化に用いるノード暗号鍵の数を削減することができる。
【００７３】
図９は、本実施形態の変形例に係る復号化装置１１０の構成を示す。本変形例に係る復号化装置１１０は、木構造選択情報取得部９００と、ノード特定部９１０と、ノード復号鍵記憶部９２０と、ノード復号鍵取得部９３０と、メッセージ復号化部５６０とを備える。木構造選択情報取得部９００は、暗号化装置１００から送信された木構造選択情報を取得する。ノード特定部９１０は、ノードの組の選択元となった木構造において、当該復号化装置１１０に対応する末端ノードからルートノードに至る経路上に位置するノードのうち、選択された復号化許可ノードを特定する。ノード復号鍵記憶部９２０は、複数の木構造のそれぞれについて、当該復号化装置１１０に対応する末端ノードからルートノードまでの経路上の各ノードに対応する各ノード復号鍵を記憶する。ノード復号鍵取得部９３０は、復号化許可ノードの組の選択元となった木構造における、ノード特定部９１０により特定された復号化許可ノードに対応付けられたノード復号鍵を、ノード復号鍵記憶部９２０から取得する。メッセージ復号化部５６０は、取得されたノード復号鍵を用いて、ノード復号鍵記憶部９２０により特定された復号化許可ノードに対応付けられたノード暗号鍵により暗号化された暗号化メッセージを復号化する。
【００７４】
図１０は、本実施形態の変形例に係る復号化装置１１０の動作フローを示す。
まず、木構造選択情報取得部９００は、暗号化装置１００から送信された木構造選択情報を取得する（Ｓ１０００）。次に、ノード特定部９１０は、選択された木構造において、当該復号化装置１１０に対応する末端ノードからルートノードに至る経路上の復号化許可ノードを特定する（Ｓ１０１０）。次に、ノード復号鍵取得部９３０は、選択された木構造における、当該復号化許可ノードに対応付けられたノード復号鍵をノード復号鍵記憶部９２０から取得する（Ｓ１０２０）。これに代えて、復号化装置１１０は、当該復号化装置１１０に対応する末端ノードから開始して、子ノードのノード復号鍵から親ノードのノード復号鍵を順次生成していくことにより、各復号化許可ノードのノード復号鍵を生成してもよい。次に、メッセージ復号化部５６０は、図５に示したメッセージ復号化部５６０と同様にして、取得されたノード復号鍵を用いて、ノード特定部９１０により特定された復号化許可ノードに対応付けられたノード暗号鍵により暗号化された暗号化メッセージを復号化する（Ｓ６３０）。より具体的には、当該ノード復号鍵を用いて、ノード暗号鍵により暗号化されたタイトル鍵を復号化し、復号化されたタイトル鍵を用いてメッセージを復号化する。
【００７５】
以上において、暗号化通信システム１０は、複数の木構造のＡＮＤ条件やＯＲ条件等により復号化を許可する復号化装置１１０を指定してもよい。
より具体的には、ＡＮＤ条件の場合、暗号化装置１００内の木構造選択部７００及びノード抽出部３１０は、ＡＮＤ条件として用いる第１の木構造及び第２の木構造を選択し、第１の木構造の第１の復号化許可ノード及び第２の木構造の第２の復号化許可ノードの組を抽出する。ここで、ノード抽出部３１０は、第１の復号化許可ノード及び第２の復号化許可ノードの組として、暗号化メッセージの復号化を許可する復号化装置１１０を子孫の末端ノードに共通して含み、暗号化メッセージの復号化を禁止する復号化装置１１０を少なくとも一方の復号化許可ノードの子孫の末端ノードに含まないノードの組を選択する。そして、ノード暗号鍵生成部７２０は、これらの復号化許可ノードに対応するノード暗号鍵を生成し、メッセージ暗号化部３４０は、第１の復号化許可ノードに対応付けられた第１のノード暗号鍵及び第２の復号化許可ノードに対応付けられた第２のノード暗号鍵によりメッセージを暗号化する。
【００７６】
暗号化メッセージを受信した復号化装置１１０内の木構造選択情報取得部９００は、木構造選択情報を受信し、第１の木構造及び第２の木構造を特定する。次に、ノード特定部９１０は、第１の復号化許可ノード及び第２の復号化許可ノードを特定する。次に、ノード復号鍵記憶部９２０は、第１の復号化許可ノードに対応付けられた第１のノード復号鍵と、第２の復号化許可ノードに対応付けられた第２のノード復号鍵とを取得する。そして、メッセージ復号化部５６０は、取得された第１のノード復号鍵及び第２のノード復号鍵を用いて暗号化メッセージを復号化する。
【００７７】
また、ＯＲ条件の場合、暗号化装置１００内の木構造選択部７００及びノード抽出部３１０は、ＯＲ条件として用いる第１の木構造及び第２の木構造を選択し、第１の木構造の第１の復号化許可ノード及び第２の木構造の第２の復号化許可ノードの組を抽出する。ここで、ノード抽出部３１０は、第１の復号化許可ノード及び第２の復号化許可ノードの組として、暗号化メッセージの復号化を許可する復号化装置１１０をいずれかの子孫の末端ノードに含み、暗号化メッセージの復号化を禁止する復号化装置１１０をいずれの復号化許可ノードの子孫の末端ノードに含まないノードの組を選択する。そして、ノード暗号鍵生成部７２０は、これらの復号化許可ノードに対応するノード暗号鍵を生成し、メッセージ暗号化部３４０は、第１の復号化許可ノードに対応付けられた第１のノード暗号鍵により暗号化された暗号化メッセージと、第２の復号化許可ノードに対応付けられた第２のノード暗号鍵により暗号化された暗号化メッセージとを生成する。
【００７８】
これらの暗号化メッセージを受信した復号化装置１１０内の木構造選択情報取得部９００は、木構造選択情報を受信し、第１の木構造及び第２の木構造を特定する。次に、ノード特定部９１０は、第１の復号化許可ノード及び第２の復号化許可ノードを特定する。次に、ノード復号鍵記憶部９２０は、第１の復号化許可ノードに対応付けられた第１のノード復号鍵と、第２の復号化許可ノードに対応付けられた第２のノード復号鍵とを取得する。そして、メッセージ復号化部５６０は、取得された第１のノード復号鍵又は第２のノード復号鍵を用いて、いずれかの暗号化メッセージを復号化する。
【００７９】
ＡＮＤ条件やＯＲ条件等により復号化許可ノードを選択可能とすることで、メッセージ長を更に低減することができる。
【００８０】
図１１は、本実施形態の変形例に係る暗号化通信システム１０により鍵を管理する木構造を示す。
本図において、暗号化通信システム１０は、互いに異なる復号化装置１１０の種類又は復号化装置１１０の利用者の各種の特性に基づいて決定された木構造TK1からTK3を用いる。暗号化装置１００内の木構造選択部７００は、暗号化メッセージの復号化を許可する復号化装置１１０の組に基づいて、TK1からTK3のいずれかの木構造を選択する。本例においては、暗号化メッセージの復号化を許可する復号化装置１１０の組は、{u2, u3, u6, u8, u9, u10, u11, u12, u13, u16}であり、復号化を禁止する復号化装置１１０の組は、{u1, u4, u5, u7, u14, u15}である。本例において木構造TK1からTK3を比較すると、復号化許可ノードの数を最小化するのは木構造TK2である。したがって木構造選択部７００は、木構造TK2を選択する。
【００８１】
本変形例に係る暗号化通信システム１０によれば、各復号化装置１１０は、選択された木構造を特定する木構造選択情報を付加した暗号化メッセージを受信し、選択された木構造における復号化許可ノードに対応する復号鍵を用いて暗号化メッセージを復号化することができる。これにより、暗号化に用いるノード鍵の数を低減することができ、メッセージ長を短くすることができる。また、これらの木構造を予め各復号化装置１１０に格納しておくことで、復号化装置１１０は、木構造選択情報と比較しデータ量が大きいノード対応情報を取得しなくてもノード鍵の数を低減することができる。このため、暗号化装置１００及び復号化装置１１０が通信できない環境においても、効率良く暗号化メッセージのメッセージ長を低減することができる。
【００８２】
図１２は、本実施形態に係る暗号化通信システム１０と従来方式とを比較したグラフを示す。本グラフは、N=214の場合におけるＣＳ法及びＳＤ法のメッセージ長、及び、上位木２１０の段数hを１、８、及び１１と変化させた場合におけるメッセージ長を縦軸とし、復号化を許可しない復号化装置１１０の数rを横軸としてプロットしたものである。ここで、各方式におけるメッセージ長は、復号化を許可しない復号化装置１１０をランダムに選択した場合の平均値である。本実施形態に係る暗号化通信システム１０によれば、hが１１の場合においてもメッセージ長を小さくすることができ、rの数が全体の半分程度まで大きくなった場合において特にメッセージ長を効果的に低減できることがわかる。
【００８３】
また、各復号化装置１１０が記憶すべき鍵の数は、ＣＳ法がlogN+1、ＳＤ法が((logN)2+  logN)/2+1であるのに対し、本実施形態に係る暗号化通信システム１０によればh+1(1≦h≦logN-1)となる。また、各復号化装置１１０において鍵を計算することにより鍵の数を削減した場合、鍵の数は、ＣＳ法が1、ＳＤ法がlogNであるのに対し、本実施形態に係る暗号化通信システム１０によれば1となる。したがって、本実施形態に係る暗号化通信システム１０は、復号化装置１１０が記憶すべき鍵の数をＣＳ方式と同等かつＳＤ法より少なく抑えつつ、メッセージ長を大幅に低減できる。
【００８４】
図１３は、本実施形態の変形例に係る暗号化通信システム１０と従来方式とを比較したグラフを示す。本グラフは、N=214の場合におけるＣＳ法及びＳＤ法のメッセージ長、及び、本実施形態の変形例に係る暗号化通信システム１０によるメッセージ長を縦軸とし、復号化を許可しない復号化装置１１０の数rを横軸としてプロットしたものである。ここで、本変形例に係る暗号化通信システム１０については、選択した木構造の中に、復号化を許可しない復号化装置１１０が何％含まれているかを示すヒット率毎に、メッセージ長を求めている。また、各方式におけるメッセージ長は、復号化を許可しない復号化装置１１０をランダムに選択した場合の平均値である。本変形例に係る暗号化通信システム１０によれば、ヒット率９０％の場合においても、メッセージ長をＳＤ法の略半分に低減することができる。
【００８５】
また、各復号化装置１１０が記憶すべき鍵の数は、ＣＳ法がlogN+1、ＳＤ法が((logN)2+logN)/2+1であるのに対し、本実施形態に係る暗号化通信システム１０によればT・logNとなる（ただし、Tは選択可能な木構造の数）。また、例えば落とし戸付き一方向関数を用いて各復号化装置１１０において鍵を計算可能とした場合、鍵の数は、ＣＳ法が１に対し、本変形例の暗号化通信システム１０はTとなる。したがって、本変形例に係る暗号化通信システム１０は、適切なTを用いることにより、復号化装置１１０が記憶すべき鍵の数をＣＳ法と比較しある程度増やすことで、メッセージ長を大幅に低減できる。
【００８６】
図１４は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部とを備える。
【００８７】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【００８８】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【００８９】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラムや、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０や、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を接続する。
【００９０】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【００９１】
コンピュータ１９００にインストールされ、コンピュータ１９００を図３に示した暗号化装置１００として機能させるプログラムは、ノード対応情報生成モジュールと、ノード抽出モジュールと、上位ノード暗号鍵生成モジュールと、下位ノード暗号鍵生成モジュールと、メッセージ暗号化モジュールと、公開鍵乗算モジュールと、公開モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、ノード対応情報生成部３００と、ノード抽出部３１０と、上位ノード暗号鍵生成部３２０と、下位ノード暗号鍵生成部３３０と、メッセージ暗号化部３４０と、公開鍵乗算部３５０と、公開部３６０としてそれぞれ機能させる。
【００９２】
コンピュータ１９００にインストールされ、コンピュータ１９００を図５に示した復号化装置１１０として機能させるプログラムは、ノード対応情報取得モジュールと、末端ノード特定モジュールと、上位ノード復号鍵記憶部５２０を管理する上位ノード復号鍵管理モジュールと、上位ノード復号鍵取得モジュールと、下位ノード復号鍵生成部５５０を管理する装置復号鍵管理モジュールと、下位ノード復号鍵生成モジュールと、メッセージ復号化モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、ノード対応情報取得部５００と、末端ノード特定部５１０と、上位ノード復号鍵記憶部５２０と、上位ノード復号鍵取得部５３０と、装置復号鍵記憶部５４０と、下位ノード復号鍵生成部５５０と、メッセージ復号化部５６０としてそれぞれ機能させる。
【００９３】
コンピュータ１９００にインストールされ、コンピュータ１９００を図７に示した暗号化装置１００として機能させるプログラムは、木構造選択モジュールと、木構造記憶部７１０を管理する木構造管理モジュールと、ノード抽出モジュールと、ノード暗号鍵生成モジュールと、メッセージ暗号化モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、木構造選択部７００と、木構造記憶部７１０と、ノード抽出部３１０と、ノード暗号鍵生成部７２０と、メッセージ暗号化部３４０としてそれぞれ機能させる。
【００９４】
コンピュータ１９００にインストールされ、コンピュータ１９００を図９に示した復号化装置１１０として機能させるプログラムは、木構造選択情報取得モジュールと、ノード特定モジュールと、ノード復号鍵記憶部９２０を管理するノード復号鍵管理モジュールと、ノード復号鍵取得モジュールと、メッセージ復号化モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、木構造選択情報取得部９００と、ノード特定部９１０と、ノード復号鍵記憶部９２０と、ノード復号鍵取得部９３０と、メッセージ復号化部５６０としてそれぞれ機能させる。
【００９５】
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤやＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【００９６】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００９７】
【図１】本発明の実施形態に係る暗号化通信システム１０の構成を示す。
【図２】本発明の実施形態に係る暗号化通信システム１０により鍵を管理する木構造を示す。
【図３】本発明の実施形態に係る暗号化装置１００の構成を示す。
【図４】本発明の実施形態に係る暗号化装置１００の動作フローを示す。
【図５】本発明の実施形態に係る復号化装置１１０の構成を示す。
【図６】本発明の実施形態に係る復号化装置１１０の動作フローを示す。
【図７】本発明の実施形態の変形例に係る暗号化装置１００の構成を示す。
【図８】本発明の実施形態の変形例に係る暗号化装置１００の動作フローを示す。
【図９】本発明の実施形態の変形例に係る復号化装置１１０の構成を示す。
【図１０】本発明の実施形態の変形例に係る復号化装置１１０の動作フローを示す。
【図１１】本発明の実施形態の変形例に係る暗号化通信システム１０により鍵を管理する木構造を示す。
【図１２】本発明の実施形態に係る暗号化通信システム１０と従来方式とを比較したグラフを示す。
【図１３】本発明の実施形態の変形例に係る暗号化通信システム１０と従来方式とを比較したグラフを示す。
【図１４】本発明の実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。
【符号の説明】
【００９８】
１０  暗号化通信システム
１００  暗号化装置
１１０  復号化装置
１２０  ネットワーク
２００  木
２１０  上位木
２２０  下位部分木
３００  ノード対応情報生成部
３１０  ノード抽出部
３２０  上位ノード暗号鍵生成部
３３０  下位ノード暗号鍵生成部
３４０  メッセージ暗号化部
３５０  公開鍵乗算部
３６０  公開部
５００  ノード対応情報取得部
５１０  末端ノード特定部
５２０  上位ノード復号鍵記憶部
５３０  上位ノード復号鍵取得部
５４０  装置復号鍵記憶部
５５０  下位ノード復号鍵生成部
５６０  メッセージ復号化部
７００  木構造選択部
７１０  木構造記憶部
７２０  ノード暗号鍵生成部
９００  木構造選択情報取得部
９１０  ノード特定部
９２０  ノード復号鍵記憶部
９３０  ノード復号鍵取得部
１９００  コンピュータ
２０００  ＣＰＵ
２０１０  ＲＯＭ
２０２０  ＲＡＭ
２０３０  通信インターフェイス
２０４０  ハードディスクドライブ
２０５０  フレキシブルディスク・ドライブ
２０６０  ＣＤ−ＲＯＭドライブ
２０７０  入出力チップ
２０７５  グラフィック・コントローラ
２０８０  表示装置
２０８２  ホスト・コントローラ
２０８４  入出力コントローラ
２０９０  フレキシブルディスク
２０９５  ＣＤ−ＲＯＭ
【図１】
2006013790.tif 000011
【図２】
2006013790.tif 000012
【図３】
2006013790.tif 000013
【図４】
2006013790.tif 000014
【図５】
2006013790.tif 000015
【図６】
2006013790.tif 000016
【図７】
2006013790.tif 000017
【図８】
2006013790.tif 000018
【図９】
2006013790.tif 000019
【図１０】
2006013790.tif 000020
【図１１】
2006013790.tif 000021
【図１２】
2006013790.tif 000022
【図１３】
2006013790.tif 000023
【図１４】
2006013790.tif 000024