(57)【要約】【課題】  ｎマルチリニアマップと階層木構成を組み合わせて適用した暗号文提供構成を構築し、効率的な処理の可能な暗号文提供構成を実現する。【解決手段】  頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理において、ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成し、暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文を生成し提供する。本構成により、暗号文の受領、復号処理における計算量が削減され、効率的な処理が実現される。【選択図】  図８
2005123678.tif 000002
【特許請求の範囲】
【請求項１】
暗号文生成処理を実行する情報処理装置であり、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号処理部を有し、
前記暗号処理部は、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成するとともに、生成した暗号鍵によって前記暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する構成であることを特徴とする情報処理装置。
【請求項２】
前記リーフに対応する複数の情報処理装置の各々は、前記ルートから自リーフに至るパス上のノードに対応するノードキーを有し、
前記暗号処理部は、
前記暗号文復号許容機器の格納ノードキーにおいてのみ復号可能な暗号文の生成処理を実行する構成であることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記暗号処理部は、
前記ｎマルチリニアマップを適用して生成する鍵として、下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓを生成する構成である、
ただし、Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Φｊは、下記の処理により定められる値、
（１）カウンタｊを用意し、ｊ＝１とセットする、
（２）カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（２ａ）もしｉ∈Ｋならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
（３）もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（３ａ）Φｊ＝ｇとセットし、ｊを１増やす、
ただし、Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合であり、
ｇｉは、ノードiの公開値でありｇｉ∈Ｇ１を満たす、
ｇはＧ１の生成元、
であることを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記暗号処理部は、
前記ｎマルチリニアマップを適用して生成する鍵として、下記定義、
【数１】
2005123678.tif 000060
に基づくセッションキーＫｓを生成する構成である、
ただし、Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
ｇは、群Ｇ１の生成元であり、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値として設定される、
ことを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記情報処理装置は、
前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、
【数２】
2005123678.tif 000061
として設定し、
ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、
【数３】
2005123678.tif 000062
として設定する構成、
ただし、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｒは、前記暗号文復号許容機器以外のリボーク（排除）機器数、
【数４】
2005123678.tif 000063
は、ｒｌｏｇ（Ｎ／ｒ）以下の最大の整数、
であることを特徴とする請求項１に記載の情報処理装置。
【請求項６】
前記情報処理装置は、
前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、
ｒ≦Ｎの任意のｒに対応可能な数ｎ、すなわちｒｌｏｇ（Ｎ／ｒ）の最大値に対応する整数値として設定する構成であることを特徴とする請求項５に記載の情報処理装置。
【請求項７】
前記情報処理装置は、
前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、
リボーク（排除）機器数ｒについて、その最大値Ｒを設定し、ｒ≦Ｒの任意数に対応可能な数ｎ、すなわち、ｒ＝Ｒとしたときのｒｌｏｇ（Ｎ／ｒ）の値に対応する整数値として設定する構成であることを特徴とする請求項５に記載の情報処理装置。
【請求項８】
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応して設定された情報処理装置であり、
前記ルートから自リーフに至るパス上のノードに対応するノードキーを格納した記憶部と、
暗号文の復号処理を実行する暗号処理部であり、暗号文の暗号処理鍵であるｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して生成された暗号鍵の算出処理を、前記ノードキーを適用して実行するとともに、生成した暗号鍵に基づいて暗号文の復号処理を実行する暗号処理部と、
を有することを特徴とする情報処理装置。
【請求項９】
前記暗号処理部は、
下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓによって暗号化された暗号文の復号処理を実行する構成であり、
セッションキーＫｓの算出処理として、下記処理１〜４、すなわち、
１．カウンタｊを用意し、ｊ＝１とセットする、
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（ａ）もしｉ∈Ｋならば、ｉとＩが一致するかどうかを調べる、
ｉ．もしｉ＝Ｉならば、Φｊ＝ｓｉとセットし、ｊを１増やして次のｉの処理に移る、
ｉｉ．もしｉ≠Ｉならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
３．もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（ａ）Φｊ＝ｇとセットし、ｊを１増やす、
４．Ｋｓ＝（φ１，・・・，φｎ）を求める、
ただし、
Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合、
ｓｉは、ノードｉの秘密キー、
ｇｉは、ノードｉの公開キー、
Ｉは、部分木ルート集合Ｋに含まれるノード、
ｇはＧ１の生成元、
上記処理１〜４を実行してセッションキーＫｓの算出を実行する構成であることを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
前記暗号処理部は、
下記定義、
【数５】
2005123678.tif 000064
に基づくセッションキーＫｓによって暗号化された暗号文の復号処理を実行する構成であり、
セッションキーＫｓの算出処理として、下記処理１〜４、すなわち、
１．カウンタｊ，ｌを用意し、ｊ＝１，ｌ＝２Ｎとセットする、
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（ａ）もしｉ∈Ｋかつｉ≠ＩならばΦｊ＝ｈｉとセットし、ｊを１増やして次のｉの処理に移る、
３．もしｊ≦ｎならばｊ≦ｎの間、下記の処理を繰り返す。
（ａ）Φｊ＝ｈｌとセットし、ｌを１増やし、ｊを１増やす，
４．セッションキーＫｓを、
【数６】
2005123678.tif 000065
により算出する、
ただし、
Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値、
Ｉは、部分木ルート集合Ｋに含まれるノード、
ｇは、群Ｇ１の生成元、
上記処理１〜４を実行してセッションキーＫｓの算出を実行する構成であることを特徴とする請求項８に記載の情報処理装置。
【請求項１１】
暗号文を格納した情報記録媒体であり、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文を格納し、
前記暗号文は、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して生成した暗号鍵によって暗号化のなされた暗号文であることを特徴とする情報記録媒体。
【請求項１２】
前記暗号文は、
前記ｎマルチリニアマップを適用して生成される鍵、すなわち、下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓによって暗号化された暗号文、
ただし、Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Φｊは、下記の処理により定められる値、
（１）カウンタｊを用意し、ｊ＝１とセットする、
（２）カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（２ａ）もしｉ∈Ｋならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
（３）もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（３ａ）Φｊ＝ｇとセットし、ｊを１増やす、
ただし、Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合であり、
ｇｉは、ノードiの公開値でありｇｉ∈Ｇ１を満たす、
ｇはＧ１の生成元，
であることを特徴とする請求項１１に記載の情報記録媒体。
【請求項１３】
前記暗号文は、
前記ｎマルチリニアマップを適用して生成される鍵、すなわち、下記定義、
【数７】
2005123678.tif 000066
に基づくセッションキーＫｓによって暗号化された暗号文、
ただし、Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
ｇは、群Ｇ１の生成元であり、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値として設定される、
であることを特徴とする請求項１１に記載の情報記録媒体。
【請求項１４】
暗号文生成処理を実行する情報処理方法であり、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号処理ステップを有し、
前記暗号処理ステップは、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成する鍵生成ステップと、
生成した暗号鍵によって前記暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号文生成ステップとを有することを特徴とする情報処理方法。
【請求項１５】
前記リーフに対応する複数の情報処理装置の各々は、前記ルートから自リーフに至るパス上のノードに対応するノードキーを有し、
前記暗号処理ステップは、
前記暗号文復号許容機器の格納ノードキーにおいてのみ復号可能な暗号文の生成処理を実行することを特徴とする請求項１４に記載の情報処理方法。
【請求項１６】
前記鍵生成ステップは、
前記ｎマルチリニアマップを適用して生成する鍵として、下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓを生成するステップである、
ただし、Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Φｊは、下記の処理により定められる値、
（１）カウンタｊを用意し、ｊ＝１とセットする、
（２）カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（２ａ）もしｉ∈Ｋならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
（３）もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（３ａ）Φｊ＝ｇとセットし、ｊを１増やす、
ただし、Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合であり、
ｇｉは、ノードiの公開値でありｇｉ∈Ｇ１を満たす、
ｇはＧ１の生成元，
であることを特徴とする請求項１４に記載の情報処理方法。
【請求項１７】
前記鍵生成ステップは、
前記ｎマルチリニアマップを適用して生成する鍵として、下記定義、
【数８】
2005123678.tif 000067
に基づくセッションキーＫｓを生成するステップである、
ただし、Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
ｇは、群Ｇ１の生成元であり、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値として設定される、
ことを特徴とする請求項１４に記載の情報処理方法。
【請求項１８】
前記情報処理方法は、さらに、
前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、
【数９】
2005123678.tif 000068
として設定し、
ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、
【数１０】
2005123678.tif 000069
として設定する構成、
ただし、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｒは、前記暗号文復号許容機器以外のリボーク（排除）機器数、
【数１１】
2005123678.tif 000070
は、ｒｌｏｇ（Ｎ／ｒ）以下の最大の整数、
を有することを特徴とする請求項１４に記載の情報処理方法。
【請求項１９】
前記情報処理方法において、
前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、
ｒ≦Ｎの任意のｒに対応可能な数ｎ、すなわちｒｌｏｇ（Ｎ／ｒ）の最大値に対応する整数値として設定することを特徴とする請求項１８に記載の情報処理方法。
【請求項２０】
前記情報処理方法において、
前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、
リボーク（排除）機器数ｒについて、その最大値Ｒを設定し、ｒ≦Ｒの任意数に対応可能な数ｎ、すなわち、ｒ＝Ｒとしたときのｒｌｏｇ（Ｎ／ｒ）の値に対応する整数値として設定することを特徴とする請求項１８に記載の情報処理方法。
【請求項２１】
暗号文の復号処理を実行する情報処理方法であり、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して生成された暗号鍵の算出処理を、階層木構成中の頂点ノードとしてのルートから自装置の対応するリーフに至るパス上のノードに設定されたノードキーを適用して実行する鍵算出ステップと、
前記鍵算出ステップにおいて算出した暗号鍵に基づいて暗号文の復号処理を実行する暗号文復号ステップと、
を有することを特徴とする情報処理方法。
【請求項２２】
前記鍵算出ステップは、
下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓの算出処理として、下記処理１〜４、すなわち、
１．カウンタｊを用意し、ｊ＝１とセットする、
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（ａ）もしｉ∈Ｋならば、ｉとＩが一致するかどうかを調べる、
ｉ．もしｉ＝Ｉならば、Φｊ＝ｓｉとセットし、ｊを１増やして次のｉの処理に移る、
ｉｉ．もしｉ≠Ｉならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
３．もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（ａ）Φｊ＝ｇとセットし、ｊを１増やす、
４．Ｋｓ＝（φ１，・・・，φｎ）を求める、
ただし、
Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合、
ｓｉは、ノードｉの秘密キー、
ｇｉは、ノードｉの公開キー、
ｇはＧ１の生成元、
Ｉは、部分木ルート集合Ｋに含まれるノード、
上記処理１〜４を実行してセッションキーＫｓの算出を実行するステップであることを特徴とする請求項２１に記載の情報処理方法。
【請求項２３】
前記鍵算出ステップは、
下記定義、
【数１２】
2005123678.tif 000071
に基づくセッションキーＫｓの算出処理として、下記処理１〜４、すなわち、
１．カウンタｊ，ｌを用意し、ｊ＝１，ｌ＝２Ｎとセットする、
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（ａ）もしｉ∈Ｋかつｉ≠ＩならばΦｊ＝ｈｉとセットし、ｊを１増やして次のｉの処理に移る、
３．もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す。
（ａ）Φｊ＝ｈｌとセットし、ｌを１増やし、ｊを１増やす、
４．上記セッションキーＫｓを算出する、
ただし、
Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値、
Ｉは、部分木ルート集合Ｋに含まれるノード、
ｇは、群Ｇ１の生成元、
上記処理１〜４を実行してセッションキーＫｓの算出を実行するステップであることを特徴とする請求項２１に記載の情報処理方法。
【請求項２４】
暗号文生成処理を実行するコンピュータ・プログラムであり、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号処理ステップを有し、
前記暗号処理ステップは、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成する鍵生成ステップと、
生成した暗号鍵によって前記暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号文生成ステップとを有することを特徴とするコンピュータ・プログラム。
【請求項２５】
暗号文の復号処理を実行するコンピュータ・プログラムであり、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して生成された暗号鍵の算出処理を、階層木構成中の頂点ノードとしてのルートから自装置の対応するリーフに至るパス上のノードに設定されたノードキーを適用して実行する鍵算出ステップと、
前記鍵算出ステップにおいて算出した暗号鍵に基づいて暗号文の復号処理を実行する暗号文復号ステップと、
を有することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報記録媒体、および情報処理方法、並びにコンピュータ・プログラムに関する。さらに、詳細には、マルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）に階層型木構造を組み合わせた暗号文配信構成を構築することにより、効率的な暗号文送受信および解析を可能とし、生成する暗号文の削減、暗号文を受領し復号するユーザデバイス、受信機等の情報処理装置における計算量の削減を実現する情報処理装置、情報記録媒体、および情報処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
昨今、音楽等のオーディオデータ、映画等の画像データ、ゲームプログラム、各種アプリケーションプログラム等、様々なソフトウエアデータ（以下、これらをコンテンツ（Content）と呼ぶ）が、インターネット等のネットワークを介して、あるいはＣＤ(Compact Disc)、ＤＶＤ(Digital Versatile Disk)、ＭＤ(Mini Disk)等の情報記録媒体（メディア）を介して流通している。これらの流通コンテンツは、ユーザの所有するＰＣ（Personal Computer）、ＣＤプレーヤ、ＤＶＤプレーヤ、ＭＤプレーヤ等の再生装置、あるいはゲーム機器等の様々な情報処理装置において再生され利用される。
【０００３】
音楽データ、画像データ等、多くのコンテンツは、一般的にその作成者あるいは販売者に頒布権等が保有されている。従って、これらのコンテンツの配布に際しては、一定の利用制限、すなわち、正規なユーザに対してのみ、コンテンツの利用を許諾し、許可のない複製等が行われないようにする構成をとるのが一般的となっている。
【０００４】
特に、近年においては、情報をデジタル的に記録する記録装置や記憶媒体が普及しつつある。このようなデジタル記録装置および記憶媒体によれば、例えば画像や音声を劣化させることなく記録、再生を繰り返すことが可能であり、不正コピーコンテンツのインターネットを介した配信や、ＣＤ−Ｒ等の記録媒体に対する不正コピーという問題が発生している。
【０００５】
このようなコンテンツの不正利用を防止する１つの方式として、コンテンツあるいは暗号化コンテンツを復号するための鍵を暗号化して提供するシステムがある。例えばブロードキャスト・エンクリプション（Broadcast Encryption）方式の一態様である階層型木構造を適用した暗号化データ提供構成は、提供する暗号化データに含まれる暗号文の設定を適宜変更することで、特定の選択された正規ユーザまたは正規デバイスのみにおいて復号可能な暗号文の提供を行うシステムである。
【０００６】
階層型木構造を適用した暗号鍵等の暗号データ提供処理について、図を参照して説明する。
【０００７】
図１に示す階層型木構造は２分木を用いており、その最下層が葉（リーフ）と呼ばれ、頂点、各分岐部およびリーフを含む部分をノードと称する。なお、頂点をルート、あるいはルートノードと呼ぶ。図１に示す２分木階層型木構造において、リーフは８〜１５、ノードは１〜１５、ルートは１である。
【０００８】
この２分木階層型木構造におけるリーフ８〜１５にコンテンツの利用機器としての再生機、受信機等の情報処理装置を１つずつ割り当てる。
【０００９】
また、木の各ノード（リーフを含む）１〜１５にそれぞれノードキーを１つずつ割り当てる。リーフ８〜１５に割り当てるノードキーはリーフキーと呼ばれる場合もある。
【００１０】
リーフに対応する各情報処理装置には、対応するリーフからルートまでの経路にあるノードに割り当てられたノードキーが与えられる。図１の構成では、リーフ８から１５までに割り当てられた８台の情報処理装置があり、ノード１から１５までにそれぞれノードキーが割り当てられており、リーフ８に対応する情報処理装置１０１には、ノード１，２，４，８に割り当てられた４個のノードキーが与えられる。また、リーフ１２に対応する情報処理装置１０２には、ノード１，３，６，１２に割り当てられた４個のノードキーが与えられる。核情報処理装置は、これらのノードキーを安全に保管する。
【００１１】
このノードキーの配布処理を伴うセッティングを用いて、選択した情報処理装置のみが取得可能な情報を送信する方法を図２を参照して説明する。たとえば、特定の音楽、画像データ等のコンテンツの暗号化データをブロードキャスト配信、あるいはＤＶＤ等の記録媒体に格納して誰でも取得可能な状態で流通させ、その暗号化コンテンツを復号するための鍵（コンテンツキー：Ｋｃ）を特定のユーザ、すなわち正規なコンテンツ利用権を持つユーザまたは情報処理装置のみにおいて取得可能とする構成を実現する。
【００１２】
図２に示すリーフ１４に割り当てられた情報処理装置を不正な機器として、排除（リボーク）し、それ以外の情報処理装置が正規な情報処理装置であるとする。この場合、リーフ１４に割り当てられた情報処理装置ではコンテンツキーＫｃを取得できないが、他の情報処理装置ではコンテンツキーＫｃを取得できる暗号文を生成して、その暗号文をネットワークを介してあるいは記録媒体に格納して配布する。
【００１３】
この場合、リボーク（排除）される情報処理装置が持つノードキー（図２では×印で表現）以外のノードキーのうち、できるだけ多数の情報処理装置に共有されているもの、すなわち木の上部にあるものをいくつか用いて、コンテンツキーを暗号化して送信すればよい。
【００１４】
図２に示す例では、ノード２，６，１５のノードキーを用いて、コンテンツキーＫｃを暗号化した暗号文のセットを生成して提供する。すなわち、
Ｅ（ＮＫ２，Ｋｃ），Ｅ（ＮＫ６，Ｋｃ），Ｅ（ＮＫ１５，Ｋｃ）
の暗号文を生成して、ネットワーク配信あるいは記録媒体に格納して提供する。なお、Ｅ（Ａ，Ｂ）はデータＢを鍵Ａで暗号化したデータを意味する。またＮＫｎは、図に示す第ｎ番のノードキーを意味する。従って、上記式は、
コンテンツキーＫｃをノードキーＮＫ２で暗号化した暗号化データＥ（ＮＫ２，Ｋｃ）と、コンテンツキーＫｃをノードキーＮＫ６で暗号化した暗号化データＥ（ＮＫ６，Ｋｃ）と、コンテンツキーＫｃをノードキーＮＫ１５で暗号化した暗号化データＥ（ＮＫ１５，Ｋｃ）と、を含む３つの暗号文のセットであることを意味している。
【００１５】
上記３つの暗号文を作り、例えば同報通信路を用いて全情報処理装置に送信すれば、リボーク対象でない情報処理装置（図２示すリーフ８〜１３および１５に対応する情報処理装置）はいずれかの暗号文を自分が持つノードキーで復号することが可能であり、コンテンツキーＫｃを得ることができる。しかし、リボーク（排除）されたリーフ１４に対応する情報処理装置は、上記の３つの暗号文に適用された３つのノードキーＮＫ２、ＮＫ６、ＮＫ１５のいずれも保有していないので、この暗号文を受領しても、復号処理を行うことができずコンテンツキーＫｃを得ることはできない。
【００１６】
上述した処理においては、３つの暗号文Ｅ（ＮＫ２，Ｋｃ），Ｅ（ＮＫ６，Ｋｃ），Ｅ（ＮＫ１５，Ｋｃ）が各情報処理装置に提供されることになる。リボークされていない各情報処理装置は、自分がどの暗号文を復号できるのかを調べ、その復号可能な暗号文を選択して復号処理を行う。上述の例では３つの暗号文の設定であるが、実際には、情報処理装置の数は膨大な数となり、情報処理装置に提供される暗号文の数も大量となる。従って、暗号文の先頭から順次、復号処理を繰り返し実行してみるといった処理は負担が大きくなる。
【００１７】
このため、暗号文の提供時に、各情報処理装置が選択すべき暗号文を知ることが可能な鍵指定コードを暗号文とともに各情報処理装置に提供する構成が提案されている。この構成については、例えば特許文献１に詳細が記述されている。
【００１８】
鍵指定コードを暗号文とともに各情報処理装置に提供する構成について、図３を参照して説明する。図３に示すように、暗号化に用いられたノードキーを木構造を用いて表し、その構造をコード化して鍵指定コードを作り、これを暗号文ブロックとともに同報送信する。情報処理装置は鍵指定コードを受領し、受領した鍵指定コードを解析することで自分がどの暗号文をどのノードキーを用いて復号すればよいかを知り、効率的に復号処理を行うことが可能となる。
【００１９】
鍵指定コードについて、説明する。図３は、先の図２と同様、リボーク（排除）機器をリーフ１４に対応する情報処理装置として、３つの暗号文、
Ｅ（ＮＫ２，Ｋｃ），Ｅ（ＮＫ６，Ｋｃ），Ｅ（ＮＫ１５，Ｋｃ）
を送信する場合の例を示している。
【００２０】
まず、図３において、太線で示した部分木は、暗号化に用いられたノードキーが割り当てられたすべてのノード１２１，１２２，１２３をリーフとし、もとの木構造のルート１２０をルートとする木であり、これを鍵指定木と呼ぶ。
【００２１】
鍵指定木の構造をデータで示すため、各ノードから、左右に枝が出ているかどうかを表す情報を設定する。
【００２２】
１つのノードにつき２ビットの情報（鍵指定情報）［００］［０１］［１０］［１１］のいずれかを用いて表現する。すなわち、あるノードにつけられた鍵指定情報の最初（左側）のビットが［１］ならばそのノードから左に枝が出ている（鍵指定木に左側の子ノードが存在する）ことを示し、［０］ならばそのノードから左に枝は出ていない（左側の子ノードは存在しない）ことを示す。鍵指定情報の最後（右側）は、同様に右側の枝の情報を表す。
【００２３】
すなわち、あるノードの鍵指定情報ビットが［１１］であればそのノードから両側に枝が出ていることを示し、［０１］であれば左側のみに、［１０］であれば右側のみに枝が出ていることを示す。また［００］は枝はいずれも出ておらず、そのノードが鍵指定木のリーフであることを示す。
【００２４】
すなわち、各ノードにおいて、左右に鍵指定木の枝があるか否かを２ビットの情報で示し、枝がある場合を［１］ない場合を［０］として、
左右とも枝ありの場合：［１１］
左にのみ枝ありの場合：［１０］
右にのみ枝ありの場合：［０１］
左右に枝なしの場合  ：［００］
として鍵指定情報ビットを設定する。
【００２５】
この鍵指定情報ビットを鍵指定木の上位層から順に、かつ同層については左から順に並べて、鍵指定コードを設定する。図３に示す構成の場合、鍵指定木は、ノードＮｏ．１，２，３，６，７，１５によって構成されているので、これらの各ノードの鍵指定情報ビットを順に並べたデータ、すなわち、
［１１００１１０００１００］
が、鍵指定コードとして設定される。
【００２６】
複数の暗号文からなる暗号文ブロックと、上記の鍵指定コードを受領したユーザデバイスとしての情報処理装置は、鍵指定コードに基づいて、鍵指定木を再構築し、自装置に格納したノードキーによって復号可能な暗号文を選択し、選択した暗号文を複合してコンテンツキーを取得し、取得したコンテンツキーで暗号化されたコンテンツを復号してコンテンツの利用を行なうことが可能となる。
【００２７】
このように同報通信路を用いて、暗号文の提供者としての送信機（送信者）が任意に選択した暗号文の受領者、すなわち受信機（受信者）のグループに安全にコンテンツキーなどの秘密情報を送信する手法は、一般的にリボケーションスキーム（ｒｅｖｏｃａｔｉｏｎ  ｓｃｈｅｍｅ）や、ブロードキャスト・エンクリプション（ｂｒｏａｄｃａｓｔ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅ）と呼ばれる。
【００２８】
リボケーションスキームや、ブロードキャスト・エンクリプションを実現する各方式の効率を評価する主要項目として、
（１）暗号文を受領して処理を行なうユーザデバイス、受信機等の情報処理装置が安全に保管しなければならない鍵の数（サイズ）
（２）同報通信されるメッセージの数（サイズ）、
（３）暗号文を受領して処理を行なうユーザデバイス、受信機等の情報処理装置が必要とする計算量
の３つの評価項目がある。
【００２９】
上記の３つの評価項目のすべてを小さくする方式、あるいは少なくとも上記項目中の１つまたは２つを小さくする方式が、より優れた方式であるとされるが、これまでに公知となっている各方式では、総受信機数Ｎや、暗号文の復号許容受信機以外の排除受信機（リボーク受信機）数ｒに依存していずれかの評価項目が大きくなってしまうという問題があった。
【００３０】
これまでに公知となっている方式のうち、非特許文献１に記載された方式では、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たす暗号学的なｎマルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）が存在するという仮定のもとで、上記の（１）と（２）の評価項目をともに定数とするようなブロードキャスト・エンクリプション方式が提案されている。なお、マルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）については、本明細書の［発明を実施するための最良の形態］中において詳細を説明する。
【００３１】
しかしながら、この方式では上記評価項目中の（３）の受信機が必要とする計算量が、総受信者数であるＮに比例するものとなってしまう。このため、この計算量を小さくする方式の開発が課題となっている。
【特許文献１】特開２００１−３５２３２２号公報
【非特許文献１】Ｄ．Ｂｏｎｅｈ  ａｎｄ  Ａ．Ｓｉｌｖｅｒｂｅｒｇ著の論文"Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｍｕｌｔｉｌｉｎｅａｒ  Ｆｏｒｍｓ  ｔｏ  Ｃｒｙｐｔｏｇｒａｐｈｙ"（この論文は、国際暗号研究協会が管理しているウェブサイトのテクニカルレポートとしてｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００２／０８０／に掲載されているとともに、著者の一人であるＰｒｏｆ．Ｂｏｎｅｈが管理するウェブサイトにｈｔｔｐ：／／ｃｒｙｐｔｏ．ｓｔａｎｆｏｒｄ．ｅｄｕ／~ｄａｂｏ．／ｐａｐｅｒｓ／ｍｌｉｎｅａｒ．ｐｄｆとして掲載されている）
【発明の開示】
【発明が解決しようとする課題】
【００３２】
本発明は、このような状況に鑑みてなされたものであり、以下の実施例中において詳細を説明するＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎ、またはｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすマルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）が存在するという前提の下で、マルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）に階層型木構造を組み合わせた暗号文配信構成を構築することにより、効率的な暗号文送受信および解析を可能とし、生成する暗号文の削減、暗号文を受領し復号するユーザデバイス、受信機等の情報処理装置における計算量の削減を実現したものである。
【００３３】
上記論文（非特許文献１）に記載の方式を適用した構成において計算量が大きいのは、必要とするマルチリニアマップがＮリニアマップ（Ｎは総受信機数）であるためである。本発明は、階層木構造を用いることによりこれを大幅に減少させることを可能とした情報処理装置、情報記録媒体、および情報処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３４】
本発明の第１の側面は、
暗号文生成処理を実行する情報処理装置であり、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号処理部を有し、
前記暗号処理部は、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成するとともに、生成した暗号鍵によって前記暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する構成であることを特徴とする情報処理装置にある。
【００３５】
さらに、本発明の情報処理装置の一実施態様において、前記リーフに対応する複数の情報処理装置の各々は、前記ルートから自リーフに至るパス上のノードに対応するノードキーを有し、前記暗号処理部は、前記暗号文復号許容機器の格納ノードキーにおいてのみ復号可能な暗号文の生成処理を実行する構成であることを特徴とする。
【００３６】
さらに、本発明の情報処理装置の一実施態様において、前記暗号処理部は、前記ｎマルチリニアマップを適用して生成する鍵として、下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓを生成する構成である、
ただし、Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Φｊは、下記の処理により定められる値、
（１）カウンタｊを用意し、ｊ＝１とセットする、
（２）カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（２ａ）もしｉ∈Ｋならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
（３）もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（３ａ）Φｊ＝ｇとセットし、ｊを１増やす、
ただし、Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合であり、
ｇｉは、ノードiの公開値でありｇｉ∈Ｇ１を満たす、
ｇはＧ１の生成元、
であることを特徴とする。
【００３７】
さらに、本発明の情報処理装置の一実施態様において、前記暗号処理部は、前記ｎマルチリニアマップを適用して生成する鍵として、下記定義、
【数１３】
2005123678.tif 000003
に基づくセッションキーＫｓを生成する構成である、
ただし、Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
ｇは、群Ｇ１の生成元であり、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値として設定される、
ことを特徴とする。
【００３８】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、
【数１４】
2005123678.tif 000004
として設定し、
ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、
【数１５】
2005123678.tif 000005
として設定する構成、
ただし、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｒは、前記暗号文復号許容機器以外のリボーク（排除）機器数、
【数１６】
2005123678.tif 000006
は、ｒｌｏｇ（Ｎ／ｒ）以下の最大の整数、
であることを特徴とする。
【００３９】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、ｒ≦Ｎの任意のｒに対応可能な数ｎ、すなわちｒｌｏｇ（Ｎ／ｒ）の最大値に対応する整数値として設定する構成であることを特徴とする。
【００４０】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、リボーク（排除）機器数ｒについて、その最大値Ｒを設定し、ｒ≦Ｒの任意数に対応可能な数ｎ、すなわち、ｒ＝Ｒとしたときのｒｌｏｇ（Ｎ／ｒ）の値に対応する整数値として設定する構成であることを特徴とする。
【００４１】
さらに、本発明の第２の側面は、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応して設定された情報処理装置であり、
前記ルートから自リーフに至るパス上のノードに対応するノードキーを格納した記憶部と、
暗号文の復号処理を実行する暗号処理部であり、暗号文の暗号処理鍵であるｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して生成された暗号鍵の算出処理を、前記ノードキーを適用して実行するとともに、生成した暗号鍵に基づいて暗号文の復号処理を実行する暗号処理部と、
を有することを特徴とする情報処理装置にある。
【００４２】
さらに、本発明の情報処理装置の一実施態様において、前記暗号処理部は、下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓによって暗号化された暗号文の復号処理を実行する構成であり、
セッションキーＫｓの算出処理として、下記処理１〜４、すなわち、
１．カウンタｊを用意し、ｊ＝１とセットする、
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（ａ）もしｉ∈Ｋならば、ｉとＩが一致するかどうかを調べる、
ｉ．もしｉ＝Ｉならば、Φｊ＝ｓｉとセットし、ｊを１増やして次のｉの処理に移る、
ｉｉ．もしｉ≠Ｉならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
３．もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（ａ）Φｊ＝ｇとセットし、ｊを１増やす、
４．Ｋｓ＝（φ１，・・・，φｎ）を求める、
ただし、
Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合、
ｓｉは、ノードｉのノードキー、
ｇｉは、ノードiの公開値、
ｇはＧ１の生成元，
Ｉは、部分木ルート集合Ｋに含まれるノード、
上記処理１〜４を実行してセッションキーＫｓの算出を実行する構成であることを特徴とする。
【００４３】
さらに、本発明の情報処理装置の一実施態様において、前記暗号処理部は、下記定義、
【数１７】
2005123678.tif 000007
に基づくセッションキーＫｓによって暗号化された暗号文の復号処理を実行する構成であり、
セッションキーＫｓの算出処理として、下記処理１〜４、すなわち、
１．カウンタｊ，ｌを用意し、ｊ＝１，ｌ＝２Ｎとセットする、
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（ａ）もしｉ∈Ｋかつｉ≠ＩならばΦｊ＝ｈｉとセットし、ｊを１増やして次のｉの処理に移る、
３．もしｊ≦ｎならばｊ≦ｎの間、下記の処理を繰り返す。
（ａ）Φｊ＝ｈｌとセットし、ｌを１増やし、ｊを１増やす、
４．セッションキーＫｓを、
【数１８】
2005123678.tif 000008
により算出する、
ただし、
Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値、
Ｉは、部分木ルート集合Ｋに含まれるノード、
ｇは、群Ｇ１の生成元、
上記処理１〜４を実行してセッションキーＫｓの算出を実行する構成であることを特徴とする。
【００４４】
さらに、本発明の第３の側面は、
暗号文を格納した情報記録媒体であり、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文を格納し、
前記暗号文は、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して生成した暗号鍵によって暗号化のなされた暗号文であることを特徴とする情報記録媒体にある。
【００４５】
さらに、本発明の情報記録媒体の一実施態様において、前記暗号文は、前記ｎマルチリニアマップを適用して生成される鍵、すなわち、下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓによって暗号化された暗号文、
ただし、Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Φｊは、下記の処理により定められる値、
（１）カウンタｊを用意し、ｊ＝１とセットする、
（２）カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（２ａ）もしｉ∈Ｋならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
（３）もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（３ａ）Φｊ＝ｇとセットし、ｊを１増やす、
ただし、Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合であり、
ｇｉは、ノードiの公開値、
ｇはＧ１の生成元、
であることを特徴とする。
【００４６】
さらに、本発明の情報記録媒体の一実施態様において、前記暗号文は、前記ｎマルチリニアマップを適用して生成される鍵、すなわち、下記定義、
【数１９】
2005123678.tif 000009
に基づくセッションキーＫｓによって暗号化された暗号文、
ただし、Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
ｇは、群Ｇ１の生成元であり、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値として設定される、
であることを特徴とする。
【００４７】
さらに、本発明の第４の側面は、
暗号文生成処理を実行する情報処理方法であり、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号処理ステップを有し、
前記暗号処理ステップは、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成する鍵生成ステップと、
生成した暗号鍵によって前記暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号文生成ステップとを有することを特徴とする情報処理方法にある。
【００４８】
さらに、本発明の情報処理方法の一実施態様において、前記リーフに対応する複数の情報処理装置の各々は、前記ルートから自リーフに至るパス上のノードに対応するノードキーを有し、前記暗号処理ステップは、前記暗号文復号許容機器の格納ノードキーにおいてのみ復号可能な暗号文の生成処理を実行することを特徴とする。
【００４９】
さらに、本発明の情報処理方法の一実施態様において、前記鍵生成ステップは、前記ｎマルチリニアマップを適用して生成する鍵として、下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓを生成するステップである、
ただし、Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Φｊは、下記の処理により定められる値、
（１）カウンタｊを用意し、ｊ＝１とセットする、
（２）カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（２ａ）もしｉ∈Ｋならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
（３）もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（３ａ）Φｊ＝ｇとセットし、ｊを１増やす、
ただし、Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合であり、
ｇｉは、ノードiの公開値、
ｇはＧ１の生成元、
であることを特徴とする。
【００５０】
さらに、本発明の情報処理方法の一実施態様において、前記鍵生成ステップは、前記ｎマルチリニアマップを適用して生成する鍵として、下記定義、
【数２０】
2005123678.tif 000010
に基づくセッションキーＫｓを生成するステップである、
ただし、Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
ｇは、群Ｇ１の生成元であり、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値として設定される、
ことを特徴とする。
【００５１】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、さらに、前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、
【数２１】
2005123678.tif 000011
として設定し、
ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、
【数２２】
2005123678.tif 000012
として設定する構成、
ただし、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｒは、前記暗号文復号許容機器以外のリボーク（排除）機器数、
【数２３】
2005123678.tif 000013
は、ｒｌｏｇ（Ｎ／ｒ）以下の最大の整数、
を有することを特徴とする。
【００５２】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法において、前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、ｒ≦Ｎの任意のｒに対応可能な数ｎ、すなわちｒｌｏｇ（Ｎ／ｒ）の最大値に対応する整数値として設定することを特徴とする。
【００５３】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法において、前記暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎを、リボーク（排除）機器数ｒについて、その最大値Ｒを設定し、ｒ≦Ｒの任意数に対応可能な数ｎ、すなわち、ｒ＝Ｒとしたときのｒｌｏｇ（Ｎ／ｒ）の値に対応する整数値として設定することを特徴とする。
【００５４】
さらに、本発明の第５の側面は、
暗号文の復号処理を実行する情報処理方法であり、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して生成された暗号鍵の算出処理を、階層木構成中の頂点ノードとしてのルートから自装置の対応するリーフに至るパス上のノードに設定されたノードキーを適用して実行する鍵算出ステップと、
前記鍵算出ステップにおいて算出した暗号鍵に基づいて暗号文の復号処理を実行する暗号文復号ステップと、
を有することを特徴とする情報処理方法にある。
【００５５】
さらに、本発明の情報処理方法の一実施態様において、前記鍵算出ステップは、下記定義、
Ｋｓ＝（Φ１，・・・Φｎ）α∈Ｇ２
に基づくセッションキーＫｓの算出処理として、下記処理１〜４、すなわち、
１．カウンタｊを用意し、ｊ＝１とセットする、
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（ａ）もしｉ∈Ｋならば、ｉとＩが一致するかどうかを調べる、
ｉ．もしｉ＝Ｉならば、Φｊ＝ｓｉとセットし、ｊを１増やして次のｉの処理に移る、
ｉｉ．もしｉ≠Ｉならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る、
３．もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す、
（ａ）Φｊ＝ｇとセットし、ｊを１増やす、
４．Ｋｓ＝（φ１，・・・，φｎ）を求める、
ただし、
Ｇ２は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
αは、α∈［１，ｐ−１］，ただし、ｐはＧ１の位数、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合、
ｓｉは、ノードｉの秘密キー、
ｇｉは、ノードｉの公開キー、
ｇはＧ１の生成元、
Ｉは、部分木ルート集合Ｋに含まれるノード、
上記処理１〜４を実行してセッションキーＫｓの算出を実行するステップであることを特徴とする。
【００５６】
さらに、本発明の情報処理方法の一実施態様において、前記鍵算出ステップは、下記定義、
【数２４】
2005123678.tif 000014
に基づくセッションキーＫｓの算出処理として、下記処理１〜４、すなわち、
１．カウンタｊ，ｌを用意し、ｊ＝１，ｌ＝２Ｎとセットする、
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる、
（ａ）もしｉ∈Ｋかつｉ≠ＩならばΦｊ＝ｈｉとセットし、ｊを１増やして次のｉの処理に移る、
３．もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す。
（ａ）Φｊ＝ｈｌとセットし、ｌを１増やし、ｊを１増やす、
４．上記セッションキーＫｓを算出する、
ただし、
Ｇ２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２を定義する群であり、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｎは、ｎマルチリニアマップの規定数ｎであり２以上の整数、
Ｋは、前記階層木構成において、暗号文復号許容機器のみを選択して設定される部分木ルート集合、
ｘｉは、階層木構成における各構成ノードｉに設定されるノードキーであり、ｈｉ＝ｇｘｉが公開値、
Ｉは、部分木ルート集合Ｋに含まれるノード、
ｇは、群Ｇ１の生成元、
上記処理１〜４を実行してセッションキーＫｓの算出を実行するステップであることを特徴とする。
【００５７】
さらに、本発明の第６の側面は、
暗号文生成処理を実行するコンピュータ・プログラムであり、
頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、前記リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号処理ステップを有し、
前記暗号処理ステップは、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成する鍵生成ステップと、
生成した暗号鍵によって前記暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理を実行する暗号文生成ステップとを有することを特徴とするコンピュータ・プログラムにある。
【００５８】
さらに、本発明の第７の側面は、
暗号文の復号処理を実行するコンピュータ・プログラムであり、
ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して生成された暗号鍵の算出処理を、階層木構成中の頂点ノードとしてのルートから自装置の対応するリーフに至るパス上のノードに設定されたノードキーを適用して実行する鍵算出ステップと、
前記鍵算出ステップにおいて算出した暗号鍵に基づいて暗号文の復号処理を実行する暗号文復号ステップと、
を有することを特徴とするコンピュータ・プログラムにある。
【００５９】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００６０】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００６１】
本発明の構成によれば、頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理において、ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成する構成とすることで、暗号文復号許容機器の格納鍵のみに基づいて復号可能な１つの暗号文として生成することが可能となり、暗号文の受領、復号処理を実行する受信機としてのユーザデバイスにおける計算量が削減され、効率的な処理が実現される。
【００６２】
本発明の構成によれば、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎ、またはｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすマルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）に階層型木構造を組み合わせた暗号文配信構成を構築することにより、階層木構成中のリーフに対応する複数の情報処理装置から選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文として必要な数を削減することが可能となり、リーフの数の増加、リボーク機器の増加などの要因が発生した場合においても、必要な暗号文数を増加させることのない効率的な暗号文の生成および提供構成が実現される。
【発明を実施するための最良の形態】
【００６３】
以下、図面を参照しながら本発明の情報処理装置、情報記録媒体、および情報処理方法、並びにコンピュータ・プログラムの詳細について説明する。
【実施例１】
【００６４】
実施例１は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすマルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）が存在するという前提の下で、マルチリニアマップを用いた鍵配信技術に階層木構造を組み合わせることによって、各受信機が必要とする計算量を削減させることを可能とした構成例である。
【００６５】
まず、上記背景技術の欄で説明した非特許文献「Ｄ．Ｂｏｎｅｈ  ａｎｄ  Ａ．Ｓｉｌｖｅｒｂｅｒｇ著の論文"Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｍｕｌｔｉｌｉｎｅａｒ  Ｆｏｒｍｓ  ｔｏ  Ｃｒｙｐｔｏｇｒａｐｈｙ」に基づいて、暗号学的なｎマルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）について説明する。
【００６６】
ｎマルチリニアマップｅ：Ｇ１ｎ→Ｇ２とは、下記の条件（１），（２），（３）を満たすものである。
（１）Ｇ１とＧ２は同じ素数の位数を持つ群である。
（２）下記条件を満足する。
【数２５】
2005123678.tif 000015
（３）もしｇ∈Ｇ１がＧ１の生成元であるならば、ｅ（ｇ，・・・ｇ）はＧ２の生成元である。
【００６７】
そして、暗号学的なｎマルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）とは、
（１）Ｇ１およびＧ２上の群の演算が効率的に行える。
（２）ｎマルチリニアマップｅが効率的に計算可能である。
（３）Ｇ１上の離散対数問題を解く効率的なアルゴリズムがない。
という３つの条件を満たすようなｎマルチリニアマップである。
【００６８】
現在までに、ｎ＝２については、Ｔａｔｅ  ｐａｒｉｎｇまたはＷｅｉｌ  ｐａｒｉｎｇという技術を用いて暗号学的なｎマルチリニアマップを構成できると考えられている。
【００６９】
本実施例の説明においては、以下の（ａ）（ｂ）の態様順に具体的な暗号文配信構成について説明する。
（ａ）任意数ｎ（ｎ＞１）について暗号学的なｎマルチリニアマップが存在すると仮定し、そのようなマップであるｎマルチリニアマップｅを用いたブロードキャスト・エンクリプション方式
（ｂ）ｎ＝２とした暗号学的な２マルチリニアマップを用いたブロードキャスト・エンクリプション方式
【００７０】
なお、本実施例において、暗号文の配信処理を実行する送信者は、図４に示すような、葉（リーフ）の数が受信者数Ｎである階層木を定義し、各ノードｉに番号をつけ、各ノードに受信機（またはユーザ）を対応付ける。各リーフは、それぞれ異なる鍵を持つ。これらの詳細構成については後述する。
【００７１】
この階層木構成に基づいて、特定の選択されたリーフを暗号文復号許容リーフとし、その他のリーフをリボーク（排除）リーフとして、暗号文の解読のできないリーフとして設定する。すなわち、暗号文提供者は、暗号文復号許容リーフにおいてのみ、解読可能な暗号文を生成して送信する。
【００７２】
暗号文は、ネットワークを介した通信、あるいはＣＤ，ＤＶＤ等の情報記録媒体に格納して提供される。この暗号文は、全てのリーフ対応の受信機（ユーザ）が取得可能である。ただし、提供した暗号文は、リボークされた機器に格納された鍵を用いて復号することはできず、リボーク機器以外の機器、すなわち、暗号文復号許容リーフに対応する機器に格納された鍵によってのみ復号できる。
【００７３】
本発明は、このような階層木構造を適用した暗号文提供構成において、ｎマルチリニアマップを用いたブロードキャスト・エンクリプション方式を適用した処理構成である。
【００７４】
（ａ）任意数ｎ（ｎ＞１）のｎマルチリニアマップｅを用いたブロードキャスト・エンクリプション方式
【００７５】
まず、任意数ｎ（ｎ＞１）のｎマルチリニアマップｅを用いたブロードキャスト・エンクリプション方式について説明する。
【００７６】
本実施例において説明するブロードキャスト・エンクリプション方式は、
（１）セットアップ、
（２）暗号化および送信、
（３）受信および復号、
の３つのフェーズに分かれている。セットアップフェーズは、システムの立ち上げ時に１度だけ行う。暗号化および送信、受信および復号の各フェーズは、情報の送信を行うたびに繰り返す。
【００７７】
ブロードキャスト・エンクリプション方式を構成するエンティティは、
（ａ）暗号文の生成および提供処理を行なう情報処理装置としての送信者（送信機）、
（ｂ）暗号文の受領および復号処理を行なう情報処理装置としてのユーザデバイス等の受信機あるいは受信者（ユーザ）
（ｃ）ブロードキャスト・エンクリプション・システムを管理する管理センタ
である。
【００７８】
暗号文の受領および復号処理を行なう情報処理装置またはユーザの総数をＮとする。また、システムを管理する管理センタを設ける。上記（１）セットアップ処理は、送信者あるいは管理センタが実行する。
【００７９】
簡単のため、暗号文を受領する情報処理装置またはユーザの総数：Ｎは２のべき乗の数とする。実際のＮが２のべき乗でない場合は、Ｎより大きな最小の２のべき乗の数をＮとして用いても構わない。
【００８０】
（１）セットアップ
以下、暗号文の生成および提供処理を行なうエンティティまたは情報処理装置を送信者または送信機とし、暗号文を受領するエンティティまたは情報処理装置を受信者または受信機として説明する。セットアップ処理は、送信者側、あるいはシステム管理者によって実行されるが、以下では、送信者においてセットアップ処理を行うものとして説明する。
【００８１】
図４に示すように、送信者は葉（リーフ）の数が受信者数Ｎである２分木を階層木として定義し、各ノードｉに番号をつける。すなわち、階層木のルート（頂点ノード）を１とし、それ以降、上位ノードから、また同一レベルのノード内では左のノードから、幅優先（ｂｒｅａｄｔｈ  ｆｉｒｓｔ  ｏｒｄｅｒ）で各ノードにノード識別子としてのノード番号２，３，４，・・・を付与する。
【００８２】
２分木の最下層にあるノードであるリーフ（葉）にはＮから２Ｎ−１までのリーフ識別子としてのリーフ番号を付与する。
【００８３】
受信機は１つずつ各リーフ（葉）に割り当てる。受信者数Ｎ＝１６である２分木の定義と受信機の割り当てを示したのが図４である。リーフ（葉）にはＮ＝１６から２Ｎ−１＝３１までのリーフ番号が付与される。
【００８４】
図５を参照して、暗号文を生成し提供する送信装置等の情報処理装置、暗号文を受領して、暗号文を選択し復号する処理を実行する受信装置等の情報処理装置（階層木構造のリーフに設定される機器）の構成例について説明する。なお、本方式においてディスクなどの記録媒体に暗号文、鍵指定コードを格納して提供する場合は、送信装置はディスク書き込み装置もしくはディスク製造装置、受信機はディスク再生装置などの情報処理装置によって構成される。
【００８５】
一例としての情報処理装置は、図５に示すように、コントローラ３０１、演算ユニット３０２、入出力インタフェース３０３、セキュア記憶部３０４、メイン記憶部３０５、大容量記憶部３０６を備える。
【００８６】
コントローラ３０１は、例えばコンピュータ・プログラムに従ったデータ処理を実行する制御部としての機能を有するＣＰＵによって構成される。演算ユニット３０２は、例えば暗号鍵の生成、乱数生成、及び暗号処理のための専用の演算機能を提供する。入出力インタフェース３０３は、キーボード、マウス等の入力手段からのデータ入力や、外部出力装置に対するデータ出力、ネットワークを介したデータ送受信処理に対応するインタフェースである。
【００８７】
セキュア記憶部３０４は、例えば暗号鍵としてのノードキー、各種ＩＤなど、安全にまたは秘密に保持すべきデータを保存する記憶部である。メイン記憶部３０５は、例えばコントローラ３０１において実行するデータ処理プログラム、その他、一時記憶処理パラメータ、プログラム実行のためのワーク領域等に使用されるメモリ領域である。セキュア記憶部３０４及びメイン記憶部３０５は、例えばＲＡＭ、ＲＯＭ等によって構成されるメモリである。大容量記憶部３０６は、ハードディスク、ＣＤ、ＤＶＤ、ＭＤ等の大容量のデータ記録、読み出し可能な記憶部であり暗号化コンテンツなどを記録する。
【００８８】
なお、以下の説明においては、理解を容易にするため、暗号文を提供する情報処理装置を送信機、暗号文を受領する情報処理装置（リーフに対応付けられている）を受信機と称して説明する。ただし、ユーザに対する暗号文の提供は、前述したように、ネットワークを介して、あるいは情報記録媒体に格納して提供することができるものであり、暗号文提供側、受領側においてデータ送受信構成が必ずしも必要な構成ではない。
【００８９】
背景技術の欄において説明したように、本出願人は先に出願済みの特開２００１−３５２３２２号公報において、例えば図４に示す木の各ノードにノードキーを割り当て、各受信機は自分が割り当てられたリーフ（葉）からルートまでのパス上のノードのノードキーを保持する構成としたブロードキャスト・エンクリプション方式を開示している。
【００９０】
この方式においては、各受信機が持つ鍵の数がｌｏｇＮ＋１、同報通信される暗号文数の上限がｒｌｏｇ（Ｎ／ｒ）各受信機が必要な計算量は１回の復号処理となる。すなわち、各受信機は、送信機から提供される複数の暗号文から、自装置（受信機）の有するノードキーによって復号可能な暗号文を１つ選択して、選択した暗号文の復号処理を行なう。
ただし、
Ｎ：ユーザ（受信機）の総数
ｒ：情報の受信者として選択されない（リボークされる）受信機の数
である。
【００９１】
具体的には、例えば図６の構成を持つ２分木構成、すなわち、リボーク（排除）機器をリーフ１４に対応する１つの情報処理装置とした場合は、
総受信機数Ｎ＝８（Ｎｏ．８〜Ｎｏ．１５）
リボーク受信機数ｒ＝１（Ｎｏ．１４）
となり、
各受信機が持つ鍵の数は、ｌｏｇＮ＋１＝ｌｏｇ８＋１＝４
同報通信される暗号文数の上限は、ｒｌｏｇ（Ｎ／ｒ）＝３
となる。
【００９２】
すなわち、リボーク（排除）機器をリーフ１４に対応する１つの情報処理装置とした場合には、以下の３つ（ｒｌｏｇ（Ｎ／ｒ）＝３）の暗号文、
Ｅ（ＮＫ２，Ｋｃ），Ｅ（ＮＫ６，Ｋｃ），Ｅ（ＮＫ１５，Ｋｃ）
を送信することが必要となる。
【００９３】
本発明では、上記の従来方式で、最大ｒｌｏｇ（Ｎ／ｒ）個の暗号文の送信を必要としていたものを、ｎ＝ｒｌｏｇ（Ｎ／ｒ）としたｎマルチリニアマップを適用することにより、１つの鍵を導出し、その鍵で暗号化した１つの暗号文を送信するのみで、リボーク機器を除く暗号文復号許容受信機においてのみ復号可能な暗号文提供を可能とした。
【００９４】
システム管理者または暗号文提供者としての送信者はＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを定め、受信機に公開する。
【００９５】
ここで、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすとは、ｇとｇｂ∈Ｇ１が与えられたときに、
ｅ（ｇ，・・・ｇ）１／ｂ∈Ｇ２
を計算することが困難であることを言う。なお、ｇは、群Ｇ１の生成元である。
【００９６】
ただし、ｎは下記のいずれかの定め方で定める。
（Ｉ）総受信機数Ｎと、リボーク受信機数ｒの全ての組み合わせから必要なｎマルチリニアマップの規定数ｎを決める。
（ＩＩ）システムでリボーク受信機数ｒの上限Ｒを定め、そこから必要なｎマルチリニアマップの規定数ｎを決める。
【００９７】
暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎの算出式は、
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、例えば、
【数２６】
2005123678.tif 000016
として設定できる。
ただし、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｒは、前記暗号文復号許容機器以外のリボーク（排除）機器数、
【数２７】
2005123678.tif 000017
は、ｒｌｏｇ（Ｎ／ｒ）以下の最大の整数である
【００９８】
いま、総受信機数Ｎ＝１６として、リボーク受信機数ｒ＝１からｒ＝１５までの各値に対する、従来方式における必要最大暗号分数ｒｌｏｇ（Ｎ／ｒ）の値を求めると下表のようになる。
【００９９】
【表１】
2005123678.tif 000018
【０１００】
上述のように、この方式においては、各リボーク受信機数ｒに対し最悪でもｒｌｏｇ（Ｎ／ｒ）個の暗号文を送信すればよいから、上表により、いかなるリボーク受信機数ｒに対しても最大８個の暗号文を送信すれば充分であり、最大暗号文数＝８となる。
【０１０１】
本発明では、複数個の暗号文を同報通信する代わりに、ｎマルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）を用いて作られた鍵に基づく１つの暗号文を送信する。
【０１０２】
暗号文送信システムに対応して必要なｎマルチリニアマップの規定数ｎの定め方には、上述の（Ｉ），（ＩＩ）があるが、
方式（Ｉ）を適用した場合、受信機総数Ｎ未満のいずれのリボーク受信機数ｒにも対応できるように、ｎ＝８とする。
【０１０３】
また、上記方式（ＩＩ）を適用した場合には、システムで対応するリボーク受信機数ｒの上限Ｒをあらかじめ定める。たとえば、このシステムでは２台までの受信機のリボークに対応する、すなわちＲ＝２とした場合、上表からｒ＝２のときｒｌｏｇ（Ｎ／ｒ）＝６であるので、ｎ＝６と定める。
【０１０４】
次に、各ノードｉ（ただしｉ＝１，２，・・・，２Ｎ−１）について、
公開値ｇｉ∈Ｇ１
を定める。
【０１０５】
ｇｉはＧ１中のランダムな要素をそれぞれ選んでもよいし、先に定めたマルチリニアマップから別の方法で定めてもよい。各ｇｉはノードとの対応とともに公開する。また、ランダムな値α∈［１，ｐ−１］を定め、各ｉについて、
秘密鍵ｓｉ＝ｇｉα
を計算する。
【０１０６】
ここでｐは群Ｇｉの位数である。また受信機ｕｍ（ただしｍ＝１，・・・，Ｎ）に対して、受信機ｕｍが割り当てられた葉からルートに至るパス上のノードの秘密鍵ｓｉを鍵として秘密に与える。受信機は秘密鍵ｓｉを安全に保管する。また送信者は群Ｇｉの生成元ｇを選び公開する。
【０１０７】
図４に示した例では、リーフＮｏ．１９の受信機ｕ４は秘密鍵ｓ１，ｓ２，ｓ４，ｓ９，ｓ１９を与えられる。
【０１０８】
（２）暗号化および送信
送信者は総受信機数Ｎ個の受信機のうち、その通信において情報を復号させる受信機の集合、すなわち、情報復号許容受信機集合Ｓ⊆｛１，・・・，ｎ｝を選択する。次に、情報復号許容受信機集合Ｓに含まれない、すなわちリボークする受信機に割り当てられたリーフ（葉）からルートまでのすべての枝、ノード、そのノードに接する枝を取り除く。すると、１つ以上の切り離された部分木が残るが、それぞれの部分木のルートの集合をＫと置く。
【０１０９】
図７に、図４のセッティングで受信機ｕ３，ｕ１１，ｕ１２の３台の受信機をリボークする場合の部分木を太線で示す。図に示すように、部分木のルートの集合Ｋ＝｛５，７，９，１２，１６｝となる。部分木は、図７に示す構成では、部分木１３１，１３２，１３３，１３４，１３５の５つの要素があり、各々は、通信において情報の復号を許容する受信機の集合Ｓ＝｛１６，１８〜１９，２０〜２３，２４〜２５，２８〜３０｝をリーフとして構成した部分木である。
【０１１０】
ここで、上記のｎの定め方において方式（Ｉ）を採用した場合には、いかなるリボーク機器数ｒの値に対しても、また方式（ＩＩ）を採用した場合には、ｒ≦Ｒなるｒ、すなわち最大リボーク受信機数Ｒ以下のいかなるリボーク受信機数ｒに対しても、部分木のルートの集合Ｋの要素数、即ち｜Ｋ｜が高々ｎになる。｜Ｋ｜は、部分木ルート集合Ｋの要素数である。図７の構成において、｜Ｋ｜、すなわち、部分木ルート集合Ｋ＝｛５，７，９，１２，１６｝の要素数は５である。
【０１１１】
そして、その通信におけるセッションキーＫｓを
Ｋｓ＝（Φ１，・・・，Φｎ）α∈Ｇ２
として計算する。ただし、Φｊは下記のように定める。
（１）カウンタｊを用意し、ｊ＝１とセットする。
（２）カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる。
（２ａ）もしｉ∈Ｋならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る。
（３）もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す。
（３ａ）Φｊ＝ｇとセットし、ｊを１増やす。
【０１１２】
上記の処理は、ｎマルチリニアマップｅの入力として、部分木ルート集合Ｋに含まれるｉについてｇｉを使用し、それ以外のｎ−｜Ｋ｜個の入力についてはｇ（ダミー）を用い、最後にｎマルチリニアマップの出力を（Ｇ２上で）α乗するものである。｜Ｋ｜は、部分木ルート集合Ｋの要素数である。
【０１１３】
図７のセッティングでｎ＝８の場合、セッションキーＫｓは、
Ｋｓ＝（ｇ５，ｇ７，ｇ９，ｇ１２，ｇ１６，ｇ，ｇ，ｇ）α
となる。
【０１１４】
送信者は、送信すべき情報をセッションキーＫｓを用いて暗号化して、セッションキーＫｓを作るのに用いられたノードの集合Ｋを表す情報（たとえば、ノード番号のリスト）とともに同報通信路で受信機に送信する。また、部分木ルート集合Ｋを表す情報は、背景技術の欄で説明した鍵指定コード等のタグ情報を用いて表してもよい。さらに、情報の暗号化は、セッションキーＫｓをそのまま使ってもよいし、たとえばセッションキーＫｓをＳＨＡ−１や、ＭＤ５等のハッシュ関数に入力して所望のサイズに変換した値を用いてもよい。
【０１１５】
たとえば放送アプリケーションの場合には、その通信における情報復号許容受信機集合Ｓを表す情報を送信した後に放送コンテンツをセッションキーＫｓで暗号化して送信してもよいし、情報復号許容受信機集合Ｓを表す情報と、セッションキーＫｓを用いてコンテンツキーＫｃを暗号化した暗号文を送信した後に、セッションキーＫｓで暗号化されたコンテンツを送信してもよい。ＣＤなどの記録メディアのアプリケーションの場合には、放送アプリケーションにおいて放送していた情報をディスクに記録して配布すればよい。
【０１１６】
（３）受信および復号
受信機ｕｍは、同報通信路から送信された情報を受信し、自分がその通信において情報を復号させる受信機の集合、すなわち情報復号許容受信機集合Ｓに含まれるかどうかを調べる。
【０１１７】
これは、自身が秘密鍵を持つノード（自分が割り当てられた葉からルートまでのパス上のノード）が部分木ルート集合Ｋに含まれるかどうかを調べることにより実行可能である。もし自分が情報復号許容受信機集合Ｓに含まれなければ、その通信を復号できないので処理を終了する。自分が情報復号許容受信機集合Ｓに含まれていれば、下記の処理によりセッションキーＫｓを求め、これを用いて送信された情報を復号する。もし受信機ｕｍが情報復号許容受信機集合Ｓに含まれていれば、部分木ルート集合Ｋに含まれるノードのうちのただ１つが、ｕｍが秘密鍵を保持しているノードの１つとなる。このノードをＩとする。
【０１１８】
１．カウンタｊを用意し、ｊ＝１とセットする。
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる。
（ａ）もしｉ∈Ｋならば、ｉとＩが一致するかどうかを調べる。
ｉ．もしｉ＝Ｉならば、Φｊ＝ｓｉとセットし、ｊを１増やして次のｉの処理に移る。
ｉｉ．もしｉ≠Ｉならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る。
３．もしｊ≦ｎならば、ｊ≦ｎの間下記の処理を繰り返す。
（ａ）Φｊ＝ｇとセットし、ｊを１増やす。
４．Ｋｓ＝（φ１，・・・，φｎ）を求める。
【０１１９】
たとえば図７のセッティングで、受信機ｕ４はノード９の秘密鍵ｓ９＝ｇ９αを所持しているので、
Ｋｓ＝（ｇ５，ｇ７，ｓ９，ｇ１２，ｇ１６，ｇ，ｇ，ｇ）
によりセッションキーＫｓを求める。
【０１２０】
上記の構成とすることにより、ｎマルチリニアマップを用いてブロードキャスト・エンクリプション方式を構成可能となる。
【０１２１】
本実施例の方式で同報通信される暗号文は１つであり、各受信機が安全に保持する鍵の数はｌｏｇＮ＋１個である。また、ｎはｒｌｏｇ（Ｎ／ｒ）を上限として定めることができる。関数の実行量は入力要素数に依存する。上述の論文で提案されている方式は、入力要素数ｎ＝Ｎであったためこのマッピングに要する計算量が大きくなると予想されるが、本発明では入力要素数を小さくすることでこの計算量を削減している。
【０１２２】
上述した処理例、すなわち、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすマルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）が存在するという前提の下で、マルチリニアマップを用いた鍵配信技術に階層木構造を組み合わせることによって、各受信機が必要とする計算量を削減させることを可能とした構成例において、暗号文を生成し、提供する情報処理装置において実行する処理シーケンスと、暗号文を受領して復号処理を行なうリーフ対応の例えば受信機等の情報処理装置における処理シーケンスについてフローチャートを参照して説明する。
【０１２３】
まず、図８を参照して、暗号文を生成し、提供する情報処理装置において実行する処理シーケンスについて説明する。
【０１２４】
暗号文送信側の情報処理装置は、まず、ステップＳ１０１において、Ｎ個の受信機のうち、その通信において情報を復号させる受信機の集合Ｓ⊆｛１，・・・，ｎ｝を選択する。
【０１２５】
ステップＳ１０２において、リボーク機器を除く情報を復号させる受信機の集合Ｓに基づいて決定される部分木のルートの集合Ｋを決定する。例えば図７の構成においては、部分木のルートの集合Ｋ＝｛５，７，９，１２，１６｝となる。
【０１２６】
ステップＳ１０３において、セッションキーＫｓを設定する。セッションキーＫｓを
Ｋｓ＝（Φ１，・・・，Φｎ）α∈Ｇ２
として計算する。
【０１２７】
セッションキーＫｓの具体的計算例を、図９に示す。この図９に示す処理は、前述したとおり、
Ｋｓ＝（Φ１，・・・，Φｎ）α∈Ｇ２
として計算する。ただし、Φｊは下記のように定める。
（１）カウンタｊを用意し、ｊ＝１とセットする。
（２）カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる。
（２ａ）もしｉ∈Ｋならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る。
（３）もしｊ≦ｎならば、ｊ≦ｎの間、下記の処理を繰り返す。
（３ａ）Φｊ＝ｇとセットし、ｊを１増やす。
【０１２８】
上記の処理は、マップｅの入力として、Ｋに含まれるｉについてｇｉを使用し、それ以外のｎ−｜Ｋ｜個の入力についてはｇを用い、最後にマップの出力を（Ｇ２上で）α乗するものである。
【０１２９】
ステップＳ１０４において、
セッションキーＫｓによってコンテンツキーＫｃを暗号化し、暗号化コンテンツキー
Ｅｎｃ（Ｋｓ，Ｋｃ）
を算出する。
【０１３０】
ステップＳ１０５において、
ａ．部分木のルート集合Ｋを示す情報（たとえば、ノード番号のリスト）
ｂ．暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）
ｃ．暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）
を通信路を介して送信する。あるいは情報記録媒体に書き込み、提供する。
【０１３１】
情報記録媒体に格納した情報例を図１０に示す。情報記録媒体４００は、例えばＣＤ、ＤＶＤ等の情報記録媒体である。ここに、
部分木のルート集合Ｋを示す情報（たとえば、ノード番号のリスト）４０１
暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）４０２
暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）４０３
を格納し、提供する。
【０１３２】
階層木構造のリーフに対応するユーザ機器としての情報処理装置は、いずれも同報通信路あるいは情報記録媒体を介して、これらの情報を受領することが可能である。しかし、その通信において情報を復号させる受信機の集合Ｓに含まれる機器のみが暗号文Ｅｎｃ（Ｋｓ，Ｋｃ）４０２に適用したセッションキーＫｓを自己の保有鍵として保持しており、リポーク機器は、暗号文Ｅｎｃ（Ｋｓ，Ｋｃ）４０２に適用したセッションキーＫｓを保有していないので、受信機の集合Ｓに含まれる機器のみが暗号文Ｅｎｃ（Ｋｓ，Ｋｃ）４０２を復号してコンテンツキーＫｃを取得し、取得したコンテンツキーＫｃに基づいて暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）４０３を復号してコンテンツ（Ｃｏｎ）を取得できる。
【０１３３】
図１１を参照して、
ａ．部分木のルート集合Ｋを示す情報（たとえば、ノード番号のリスト）
ｂ．暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）
ｃ．暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）
上記ａ〜ｃの各情報を受領したユーザ機器としての情報処理装置における処理手順について説明する。
【０１３４】
まず、ステップＳ２０１において、部分木のルート集合Ｋを示す情報（たとえば、ノード番号のリスト）を読み出す。
【０１３５】
ステップＳ２０２において、自身の装置が、その通信において情報を復号させる受信機の集合、すなわち情報復号許容受信機集合Ｓに含まれるか否かを判定する。これは、自身が秘密鍵を持つノード（自分が割り当てられた葉からルートまでのパス上のノード）が部分木のルート集合Ｋに含まれるかどうかを調べることにより実行可能である。もし、情報復号許容受信機集合Ｓに含まれなければ、その通信を復号できないので処理を終了する。
【０１３６】
自分が情報復号許容受信機集合Ｓに含まれていれば、ステップＳ２０３に進み、セッションキーＫｓを導出する。
【０１３７】
セッションキーＫｓの具体的計算例を、図１２に示す。この図１２に示す処理は、前述したとおり、以下の処理である。
１．カウンタｊを用意し、ｊ＝１とセットする。
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる。
（ａ）もしｉ∈Ｋならば、ｉとＩが一致するかどうかを調べる。
ｉ．もしｉ＝Ｉならば、Φｊ＝ｓｉとセットし、ｊを１増やして次のｉの処理に移る。
ｉｉ．もしｉ≠Ｉならば、Φｊ＝ｇｉとセットし、ｊを１増やして次のｉの処理に移る。
３．もしｊ≦ｎならばｊ≦ｎの間下記の処理を繰り返す。
（ａ）Φｊ＝ｇとセットし、ｊを１増やす。
４．Ｋｓ＝（φ１，・・・，φｎ）を求める。
【０１３８】
ステップＳ２０４において、セッションキーＫｓを適用して暗号文Ｅｎｃ（Ｋｓ，Ｋｃ）を復号してコンテンツキーＫｃを取得し、取得したコンテンツキーＫｃに基づいて暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）を復号してコンテンツ（Ｃｏｎ）を取得する。
【０１３９】
（ｂ）ｎ＝２とした暗号学的な２マルチリニアマップを用いたブロードキャスト・エンクリプション方式
【０１４０】
上述の実施例においては、任意のｎ（ｎ＞１）に対する暗号学的なｎマルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）が存在することを前提としているが、以下、既に実証されているｎ＝２とした暗号学的なｎマルチリニアマップ、すなわち２マルチリニアマップにおける具体例を説明する。なお、ｎ＝２とした暗号学的なｎマルチリニアマップについては、Ｄ．Ｂｏｎｅｈ  ａｎｄ  Ｍ．Ｆｒａｎｋｌｉｎ著の論文"Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  Ｐａｒｉｎｇ"（この論文は、著者の一人であるＰｒｏｆ．Ｂｏｎｅｈが管理するウェブサイトにｈｔｔｐ：／／ｃｒｙｐｔｏ．ｓｔａｎｆｏｒｄ．ｅｄｕ／~ｄａｂｏ．／ｐａｐｅｒｓ／ｉｂｅ．ｐｄｆとして掲載されている）
【０１４１】
前述したように、本出願人は、特開２００１−３５２３２２号公報において、図４に示す木の各ノードにノードキーを割り当て、各受信機は自分が割り当てられたリーフ（葉）からルートまでのパス上のノードのノードキーを保持する構成としたブロードキャスト・エンクリプション方式を開示している。
【０１４２】
従来方式においては、各受信機が持つ鍵の数がｌｏｇＮ＋１、同報通信される暗号文数の上限がｒｌｏｇ（Ｎ／ｒ）各受信機が必要な計算量は１回の復号処理である。
ただし、
ただし、Ｎ：ユーザ（受信機）の総数
ｒ：情報の受信者として選択されない（リボークされる）受信機の数
である。
【０１４３】
このような階層木構造の暗号文配信システムでは、リボーク機器数ｒに応じて、最大ｎｌｏｇ（Ｎ／ｒ）個の暗号文をすることになるが、２マルチリニアマップを適用することで、最大の暗号文数を、
【数２８】
2005123678.tif 000019
とすることができる。
【０１４４】
以下において説明するブロードキャスト・エンクリプション方式について、上述の任意のｎを適用した処理例と同様、
（１）セットアップ、
（２）暗号化および送信、
（３）受信および復号、
の３つのフェーズに区分して説明する。セットアップフェーズは、システムの立ち上げ時に１度だけ行う。暗号化および送信、受信および復号の各フェーズは、情報の送信を行うたびに繰り返す。
【０１４５】
ブロードキャスト・エンクリプション方式を構成するエンティティとして、暗号文の生成および提供処理を行なう情報処理装置としての送信者（送信機）と、暗号文の受領および復号処理を行なう情報処理装置としてのユーザデバイス等の受信機あるいは受信者（ユーザ）であり、暗号文の受領および復号処理を行なう情報処理装置またはユーザの総数をＮとする。また、システムを管理する管理センタを設ける。上記（１）セットアップ処理は、送信者あるいは管理センタが実行する。
【０１４６】
簡単のため、暗号文を受領する情報処理装置またはユーザの総数：Ｎは２のべき乗の数とする。実際のＮが２のべき乗でない場合は、Ｎより大きな最小の２のべき乗の数をＮとして用いても構わない。
【０１４７】
（１）セットアップ
以下、暗号文の生成および提供処理を行なうエンティティまたは情報処理装置を送信者または送信機とし、暗号文を受領するエンティティまたは情報処理装置を受信者または受信機として説明する。セットアップ処理は、送信者側、あるいはシステム管理者によって実行されるが、以下では、送信者においてセットアップ処理を行うものとして説明する。
【０１４８】
送信者は、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たす２マルチリニアマップ（２−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）を定め、受信機に公開する。
【０１４９】
ここで、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たすとは、ｇとｇｂ∈Ｇ１が与えられたときに、
ｅ（ｇ，・・・ｇ）１／ｂ∈Ｇ２
を計算することが困難であることを言う。なお、ｇは、群Ｇ１の生成元である。
【０１５０】
各ノードｉ（ただしｉ＝１，２，・・・，２Ｎ−１）について、
公開値ｇｉ∈Ｇ１
を定める。
【０１５１】
ｇｉはＧ１中のランダムな要素をそれぞれ選んでもよいし、先に定めたマルチリニアマップから別の方法で定めてもよい。各ｇｉはノードとの対応とともに公開する。また、ランダムな値α∈［１，ｐ−１］を定め、各ｉについて、
秘密鍵ｓｉ＝ｇｉα
を計算する。
【０１５２】
ここでｐは群Ｇｉの位数である。また受信機ｕｍ（ただしｍ＝１，・・・，Ｎ）に対して、ｕｍが割り当てられた葉からルートに至るパス上のノードの秘密鍵ｓｉを鍵として秘密に与える。受信機は秘密鍵ｓｉを安全に保管する。送信者は群Ｇｉの生成元ｇを選択し公開する。
【０１５３】
図４に示した例では、受信機ｕ４は秘密鍵ｓ１，ｓ２，ｓ４，ｓ９，ｓ１９を与えられる。
【０１５４】
（２）暗号化および送信
送信者はＮ個の受信機のうち、その通信において情報を復号させる受信機の集合Ｓ⊆｛１，・・・，ｎ｝を選択する。次に、情報復号許容受信機集合Ｓに含まれない、すなわちリボークするレシーバに割り当てられたリーフ（葉）からルートまでのすべての枝、ノード、そのノードに接する枝を取り除く。すると、１つ以上の切り離された部分木が残るが、それぞれの部分木のルートの集合をＫと置く。
【０１５５】
次に、部分木ルート集合Ｋの要素をその番号ｉの順に、２つずつ、
【数２９】
2005123678.tif 000020
個のサブグループＳＧｋに分割する。
ただし、
【数３０】
2005123678.tif 000021
である。
【０１５６】
なお、
｜Ｋ｜は、部分木ルート集合Ｋの要素数を示し、
【数３１】
2005123678.tif 000022
は、｜Ｋ｜／２以上である最小の整数を表す。
【０１５７】
ただし、最後のサブグループ
【数３２】
2005123678.tif 000023
に部分木のルートの集合Ｋの要素が１つしか入らない場合には、ノード番号２Ｎのダミーノードの存在を仮定し、このダミーノードがこのサブグループのもう１つの要素となる。
【０１５８】
上述の例と同様、図４に示す２分木構成、すなわち、各受信機が１つずつ各リーフ（葉）に割り当てられ受信者数Ｎ＝１６である２分木構成を想定し、図７に示すように、図４のセッティングでｕ３，ｕ１１，ｕ１２の３台の受信機をリボークする場合の処理について説明する。
【０１５９】
図７に示すように、部分木のルートの集合Ｋ＝｛５，７，９，１２，１６｝となる。この場合、サブグループは、
ＳＧ１＝｛５，７｝
ＳＧ２＝｛９，１２｝
ＳＧ３＝｛１６，３２｝
となる。
【０１６０】
そして、その通信におけるサブグループＳＧｋ用のサブグループキーＫＳＧｋを、
ＫＳＧｋ＝ｅ（Φｊ１，Φｊ２）α∈Ｇ２
として定める。
なお、Φｊ１，Φｊ２はサブグループＳＧｋの要素であるノードｊ１，ｊ２（ｊ１＜ｊ２とする）に対応する公開鍵ｇｊ１およびｇｊ２である。
ただし、ｊ２がＫの要素ではない。すなわちダミーノードである場合には、
Φｊ２＝ｇとする。
【０１６１】
上記の例では、各サブグループキーＫＳＧｋは、下記のように設定される。
ＫＳＧ１＝ｅ（ｇ５，ｇ７）α
ＫＳＧ２＝ｅ（ｇ９，ｇ１２）α
ＫＳＧ３＝ｅ（ｇ１６，ｇ）α
である。
【０１６２】
次に、その通信における全体のセッションキーＫｓをランダムに定める。セッションキーＫｓは通信の内容（たとえば映画などのコンテンツ）を暗号化するための鍵であり、たとえば暗号化アルゴリズムに米国標準のＡＥＳの１２８ｂｉｔ版を用いる際には、セッションキーＫｓは１２８ｂｉｔとなる。
【０１６３】
次に、個々のサブグループキーを用いてセッションキーＫｓを暗号化した暗号文
【数３３】
2005123678.tif 000024
を、暗号文
ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）として設定する。
ただし、Ｅ（Ａ，Ｂ）は鍵Ａを用いた平文Ｂの暗号化を示す。
【０１６４】
暗号化アルゴリズムとしてはたとえば米国標準のＡＥＳの１２８ｂｉｔ版を用いる。関数Ｈは、Ｇ２の任意の要素を、使用する暗号化アルゴリズムの鍵長（たとえば１２８ｂｉｔ）に縮約するハッシュ関数である。暗号化アルゴリズムＥとハッシュ関数Ｈはシステムであらかじめ定めてあり（送信者が定めてもよい）、公開されている。
【０１６５】
送信者は、送信すべき情報をセッションキーＫｓを用いて暗号化して、部分木のルートの集合Ｋを表す情報（たとえば、ノード番号のリスト）と、上記の暗号文、
【数３４】
2005123678.tif 000025
とを、ともに同報通信路で受信機に送信する。
【０１６６】
たとえば放送アプリケーションの場合には、部分木のルートの集合Ｋを表す情報を送信した後に、暗号文、
【数３５】
2005123678.tif 000026
を送信し、その後に放送コンテンツをセッションキーＫｓで暗号化して送信してもよい。
【０１６７】
あるいは、通信において情報を復号させる受信機の集合Ｓを表す情報と、暗号文
【数３６】
2005123678.tif 000027
と、セッションキーＫｓで暗号化したコンテンツキーＫｃを送信した後に、コンテンツキーＫｃで暗号化されたコンテンツを送信してもよい。ＣＤなどの記録メディアのアプリケーションの場合には、放送アプリケーションにおいて放送していた情報をディスクに記録して配布すればよい。
【０１６８】
（３）受信および復号
受信機ｕｍは、同報通信路から送信された情報を受信し、自分がその通信において情報を復号させる受信機の集合Ｓに含まれるかどうかを調べる。これは、自身が秘密鍵を持つノード（自分が割り当てられた葉からルートまでのパス上のノード）がＫに含まれるかどうかを調べることにより行える。
【０１６９】
もし自分が情報復号許容受信機集合Ｓに含まれなければ、その通信を復号できないので処理を終了する。自分が情報復号許容受信機集合Ｓに含まれていれば、自分がどのサブグループの暗号文を復号すべきかを調べる。これは、部分木ルート集合Ｋの要素を２つずつ区切ったときの何番目に、自分が秘密鍵を持つノードが入るかを探すことで求められる。そして、受信機ｕｍは、自分が所有する秘密鍵に対応するサブグループＳＧｋのサブグループキーを下記のようにして求める。
ＫＳＧｋ＝ｅ（ｓｉ，Φｊ）∈Ｇ２  （ｉ＜ｊの場合）
ＫＳＧｋ＝ｅ（Φｊ，ｓｉ）∈Ｇ２  （ｉ＞ｊの場合）
【０１７０】
ここで、ｓｉは、サブグループＳＧｋの要素のうち、受信機ｕｍが秘密鍵を持つノードｉに対応する秘密鍵であり、Φｊは、ｉではないほうのノードｊに対応する公開情報ｇｉである。ただし、ｊが部分木のルートの集合Ｋの要素ではない、すなわちダミーノードである場合には、Φｊ＝ｇとする。
【０１７１】
たとえば上記の例で受信機ｕｍはノードｇの秘密鍵ｓ９＝ｇ９αを所持しているので、
ＫＳＧ２＝ｅ（ｓ９，Φ１２）
としてサブグループＳＧ２のサブグループキーＫＳＧ２を求めることができる。
【０１７２】
次に、受信機ｕｍは、上で求めたサブグループキーＫＳＧｋからハッシュ値Ｈ（ＫＳＧｋ）を計算し、これを用いて暗号文ＣＴｋを復号してセッションキーＫｓを求め、これを用いて送信された情報を復号する。
【０１７３】
上記のような構成とすることにより、２マルチリニアマップを用いてＮ個の受信機に鍵（セッションキーＫｓ）を安全に配信できるシステムを構成することが可能となる。上記構成では受信機が安全に保管しなければならない鍵は１つ（ｘｉ）だけであり、たとえばセッションキーＫｓを直接コンテンツの暗号化に用いる場合などにおいて、鍵配信のために同報通信されるメッセージの個数は、
【数３７】
2005123678.tif 000028
となる。
【０１７４】
なお、リボークする受信機数をｒとしたときに、部分木ルート集合Ｋの要素数｜Ｋ｜の最大値はｒｌｏｇ２（Ｎ／ｒ）であることがわかっている。
【０１７５】
上記は２マルチリニアマップを用いる方法について詳しく述べたが、この方式は、前述したように、任意の整数ｎ＞１に対するｎマルチリニアマップを用いる方式にそのまま拡張可能である。ｎが大きくなると、受信機が保管する鍵数は１のままであるのに対し、同報通信されるメッセージ数が、
【数３８】
2005123678.tif 000029
となり、上記のｎ＝２の場合に比べてこの面での効率がよくなる。
【０１７６】
（変形例）
上述した実施例においては、最後のサブグループ
【数３９】
2005123678.tif 000030
に部分木ルート集合Ｋの要素が１つしか入らない場合には、ノード番号２Ｎのダミーノードを利用していたが、変形例としてはそのサブグループにＫの要素が１つしか入らない場合には、そのノードｉの秘密鍵ｓｉを用いて、セッションキーを暗号化してもよい。
【０１７７】
すなわち、暗号文を
【数４０】
2005123678.tif 000031
として設定してもよい。ここで、Ｈ'は、Ｇ１の任意の要素を、使用する暗号化アルゴリズムの鍵長（たとえば１２８ｂｉｔ）に縮約するハッシュ関数であり、公開されているものとする。
【０１７８】
上述した処理例、すなわち、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎを満たす２マルチリニアマップを用いた鍵配信技術に階層木構造を組み合わせることによって、各受信機が必要とする計算量を削減させることを可能とした構成例において、暗号文を生成し、提供する情報処理装置において実行する処理シーケンスと、暗号文を受領して復号処理を行なうリーフ対応の例えば受信機等の情報処理装置における処理シーケンスについてフローチャートを参照して説明する。
【０１７９】
まず、図１３を参照して、暗号文を生成し、提供する情報処理装置において実行する処理シーケンスについて説明する。
【０１８０】
暗号文送信側の情報処理装置は、まず、ステップＳ３０１において、Ｎ個の受信機のうち、その通信において情報を復号させる受信機の集合Ｓ⊆｛１，・・・，ｎ｝を選択する。
【０１８１】
ステップＳ３０２において、リボーク機器を除く情報を復号させる受信機の集合Ｓに基づいて決定される部分木のルートの集合Ｋを決定する。例えば図７の構成においては、部分木のルートの集合Ｋ＝｛５，７，９，１２，１６｝となる。
【０１８２】
ステップＳ３０３において、サブグループＳＧｋ用のサブグループキーＫＳＧｋを、
ＫＳＧｋ＝ｅ（Φｊ１，Φｊ２）α∈Ｇ２
として定める。
【０１８３】
ステップＳ３０４において、その通信における全体のセッションキーＫｓをランダムに定める。セッションキーＫｓは通信の内容（たとえば映画などのコンテンツ）を暗号化するための鍵であり、たとえば暗号化アルゴリズムに米国標準のＡＥＳの１２８ｂｉｔ版を用いる際には、セッションキーＫｓは１２８ｂｉｔとなる。
【０１８４】
次に、ステップＳ３０５において、個々のサブグループキーを用いてセッションキーＫｓを暗号化した暗号文
ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）を導出する。
【０１８５】
次にステップＳ３０６において、セッションキーＫｓによってコンテンツキーＫｃを暗号化し、暗号化コンテンツキー
Ｅｎｃ（Ｋｓ，Ｋｃ）
を算出する。
【０１８６】
ステップＳ３０７において、
ａ．部分木のルート集合Ｋを示す情報（たとえば、ノード番号のリスト）
ｂ．個々のサブグループキーを用いてセッションキーＫｓを暗号化した暗号文ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）
ｃ．暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）
ｄ．暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）
を通信路を介して送信する。あるいは情報記録媒体に書き込み、提供する。
【０１８７】
情報記録媒体に格納した情報例を図１４に示す。情報記録媒体５００は、例えばＣＤ、ＤＶＤ等の情報記録媒体である。ここに、
部分木のルート集合Ｋを示す情報（たとえば、ノード番号のリスト）５０１
個々のサブグループキーを用いてセッションキーＫｓを暗号化した暗号文ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）５０２
暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）５０３
暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）５０４
を格納し、提供する。
【０１８８】
階層木構造のリーフに対応するユーザ機器としての情報処理装置は、いずれも同報通信路あるいは情報記録媒体を介して、これらの情報を受領することが可能である。しかし、その通信において情報を復号させる受信機の集合Ｓに含まれる機器のみが、個々のサブグループキーを用いてセッションキーＫｓを暗号化した暗号文ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）５０２に適用したサブグループキーを導出するための秘密キーを自己の保有鍵として保持しており、リボーク機器は、暗号文ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）５０２に適用したサブグループキーを導出するための秘密キーを保有していないので、受信機の集合Ｓに含まれる機器のみが暗号文ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）５０２を復号してセッションキーＫｓを取得し、さらに、取得したセッションキーＫｓにより、暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）を復号してコンテンツキーＫｃを取得し、取得したコンテンツキーＫｃに基づいて暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）５０４を復号してコンテンツ（Ｃｏｎ）を取得できる。
【０１８９】
図１５を参照して、
ａ．部分木のルート集合Ｋを示す情報（たとえば、ノード番号のリスト）
ｂ．個々のサブグループキーを用いてセッションキーＫｓを暗号化した暗号文ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）
ｃ．暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）
ｄ．暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）
上記ａ〜ｄの各情報を受領したユーザ機器としての情報処理装置における処理手順について説明する。
【０１９０】
まず、ステップＳ４０１において、部分木のルート集合Ｋを示す情報（たとえば、ノード番号のリスト）を読み出す。
【０１９１】
ステップＳ４０２において、自身の装置が、その通信において情報を復号させる受信機の集合、すなわち情報復号許容受信機集合Ｓに含まれるか否かを判定する。これは、自身が秘密鍵を持つノード（自分が割り当てられた葉からルートまでのパス上のノード）が部分木のルート集合Ｋに含まれるかどうかを調べることにより実行可能である。もし、情報復号許容受信機集合Ｓに含まれなければ、その通信を復号できないので処理を終了する。
【０１９２】
自分が情報復号許容受信機集合Ｓに含まれていれば、ステップＳ４０３に進み、自分が所有する秘密鍵に対応するサブグループＳＧｋのサブグループキーを前述したように、下記のようにして求める。
ＫＳＧｋ＝ｅ（ｓｉ，Φｊ）∈Ｇ２ （ｉ＜ｊの場合）
ＫＳＧｋ＝ｅ（Φｊ，ｓｉ）∈Ｇ２ （ｉ＞ｊの場合）
【０１９３】
次に、ステップＳ４０４において、サブグループキーＫＳＧｋからハッシュ値Ｈ（ＫＳＧｋ）を計算し、これを用いてセッションキーの暗号化データである暗号文ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）を復号してセッションキーＫｓを求める。
【０１９４】
ステップＳ４０５において、セッションキーＫｓを適用して暗号文Ｅｎｃ（Ｋｓ，Ｋｃ）を復号してコンテンツキーＫｃを取得し、ステップＳ４０６において、取得したコンテンツキーＫｃに基づいて暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）を復号してコンテンツ（Ｃｏｎ）を取得する。
【実施例２】
【０１９５】
以下、本発明の第２実施例について説明する。実施例２は、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすマルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）が存在するという前提の下で、マルチリニアマップを用いた鍵配信技術に階層木構造を組み合わせることによって、各受信機が必要とする計算量を削減させることを可能とした実施例である。
【０１９６】
本実施例の説明においても上述の実施例１と同様、以下の（ａ）（ｂ）の態様別に、順に具体的な暗号文配信構成について説明する。
（ａ）任意数ｎ（ｎ＞１）について暗号学的なｎマルチリニアマップが存在すると仮定し、そのようなマップであるｎマルチリニアマップｅを用いたブロードキャスト・エンクリプション方式
（ｂ）ｎ＝２とした暗号学的な２マルチリニアマップを用いたブロードキャスト・エンクリプション方式
【０１９７】
（ａ）任意数ｎ（ｎ＞１）のｎマルチリニアマップｅを用いたブロードキャスト・エンクリプション方式
【０１９８】
まず、任意数ｎ（ｎ＞１）を設定したｎマルチリニアマップｅを用いたブロードキャスト・エンクリプション方式について説明する。
【０１９９】
以下、本実施例２におけるブロードキャスト・エンクリプション方式について、上述の実施例１と同様、
（１）セットアップ、
（２）暗号化および送信、
（３）受信および復号、
の３つのフェーズに区分して説明する。
【０２００】
セットアップフェーズは、システムの立ち上げ時に１度だけ行う。暗号化および送信、受信および復号の各フェーズは、情報の送信を行うたびに繰り返す。
【０２０１】
ブロードキャスト・エンクリプション方式を構成するエンティティとして、暗号文の生成および提供処理を行なう情報処理装置としての送信者（送信機）と、暗号文の受領および復号処理を行なう情報処理装置としてのユーザデバイス等の受信機あるいは受信者（ユーザ）であり、暗号文の受領および復号処理を行なう情報処理装置またはユーザの総数をＮとする。また、システムを管理する管理センタを設ける。上記（１）セットアップ処理は、送信者あるいは管理センタが実行する。
【０２０２】
簡単のため、暗号文を受領する情報処理装置またはユーザの総数：Ｎは２のべき乗の数とする。実際のＮが２のべき乗でない場合は、Ｎより大きな最小の２のべき乗の数をＮとして用いても構わない。
【０２０３】
（１）セットアップ
以下、暗号文の生成および提供処理を行なうエンティティまたは情報処理装置を送信者または送信機とし、暗号文を受領するエンティティまたは情報処理装置を受信者または受信機として説明する。セットアップ処理は、送信者側、あるいはシステム管理者によって実行されるが、以下では、送信者においてセットアップ処理を行うものとして説明する。
【０２０４】
送信者は、実施例１と同様に、リーフ（葉）の数がＮである２分木を定義し、各ノードｉに番号を付与する。受信機は１つずつ各リーフ（葉）に割り当てる。
【０２０５】
送信者はｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）を定め、受信機に公開する。ただし、ｎは総受信機数Ｎに対し、ｎ＝Ｎ−１と定める。
【０２０６】
ここで、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすとは、
【数４１】
2005123678.tif 000032
と、
ｎ個の受信機｛１，・・・，ｎ｝のうちの部分集合、情報復号許容受信機集合Ｓ⊂｛１，・・・，ｎ｝に対する
【数４２】
2005123678.tif 000033
が与えられたときに、
【数４３】
2005123678.tif 000034
を求めることが困難であることを言う。ここでｇは群Ｇ１の生成元である。
【０２０７】
ただし、ｎは、実施例１の方法で求めたものマイナス１とする。実施例１においては、ｎは下記のいずれかの定め方で定めていた。
（Ｉ）総受信機数Ｎと、リボーク受信機数ｒの全ての組み合わせから必要なｎを決める。
（ＩＩ）システムでリボーク受信機数ｒの上限Ｒを定め、そこから必要なｎを決める。
【０２０８】
暗号鍵の生成処理に適用するｎマルチリニアマップの規定数ｎの算出式は、
ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップを用いる場合、例えば、
【数４４】
2005123678.tif 000035
として設定可能である。
ただし、
Ｎは階層木構成の最下位ノードであるリーフに対応する情報処理装置の総数、
ｒは、前記暗号文復号許容機器以外のリボーク（排除）機器数、
【数４５】
2005123678.tif 000036
は、ｒｌｏｇ（Ｎ／ｒ）以下の最大の整数である。
【０２０９】
実施例２においては、例えば実施例１と同様にＮ＝１６のとき、実施例１の（Ｉ）の方法をとった場合にはｎ＝８としたが、実施例２ではｎ＝７とする。同様に（ＩＩ）の方法をとった場合には実施例１ではｎ＝６としたが、本実施例ではｎ＝５とする。
【０２１０】
次に、ｉ＝１，２，・・・，２Ｎ＋ｎ−１の各ｉに対し、ランダムな値ｘｉ∈［１，ｐ−１］を選び、それぞれに対し、
【数４６】
2005123678.tif 000037
を計算する。ここでｐは群Ｇ１の位数であり、ｇはＧ１の生成元である。各ｈｉを公開する。
【０２１１】
受信機ｕｍには、それが割り当てられた葉からルートに至るまでのパス上の各ノードｊに対応するｌｏｇＮ＋１個のｘｊを与える。受信機はｘｊを安全に保管する。
【０２１２】
いま、図４のセッティングで、Ｎ＝１６であり、ｎ＝７と決めたとする。すると、２Ｎ＋ｎ−１＝３８なので、送信者はｘ１，・・・，ｘ３８とｈ１，・・・，ｈ３８を用意してｈｉを公開する。例えば、受信機ｕ４には、ノード１，２，４，９，１９に対応するｘ１，ｘ２，ｘ４，ｘ９，ｘ１９を与える。
【０２１３】
（２）暗号化および送信
送信者はＮ個の受信機のうち、その通信において情報を復号させる受信機の集合、すなわち、情報復号許容受信機集合Ｓ⊆｛１，・・・，ｎ｝を選択する。次に、情報復号許容受信機集合Ｓに含まれない、すなわちリボークするレシーバに割り当てられたリーフ（葉）からルートまでのすべての枝、ノード、そのノードに接する枝を取り除く。
【０２１４】
すると、１つ以上の切り離された部分木が残るが、それぞれの部分木のルートの集合をＫと置く。図７に、図４のセッティングでｕ３，ｕ１１，ｕ１２の３台の受信機をリボークする場合の部分木を示す。
【０２１５】
図７に示すように、部分木ルート集合Ｋ＝｛５，７，９，１２，１６｝となる。ここで、上記のｎの定め方において（Ｉ）を採用した場合には、いかなるリボーク受信機数ｒの値に対しても、また（ＩＩ）を採用した場合には、ｒ≦Ｒなるｒ、すなわち最大リボーク受信機数Ｒ以下のいかなるリボーク受信機数ｒに対しても、部分木のルートの集合Ｋの要素数｜Ｋ｜が高々ｎ＋１になる。ｒは情報の受信者として選択されない（リボークされる）受信機の数である。Ｒは、システム上のリボーク数ｒの最大値である。
【０２１６】
階層木構造を適用した通信におけるセッションキーＫｓを下記のようにして導出し、それを用いて情報を暗号化して、Ｋを表す情報とともに同報送信する。
【数４７】
2005123678.tif 000038
【０２１７】
ここで、部分木ルート集合Ｋの要素数｜Ｋ｜＝ｎ＋１の場合には、上式のｘ２Ｎｘ２Ｎ＋１・・・ｘ２Ｎ＋ｎ−｜Ｋ｜の部分は使用されない点に注意されたい。
【０２１８】
図７のセッティングでｎ＝７の場合、
【数４８】
2005123678.tif 000039
となる。
【０２１９】
また、Ｋを表す情報は、背景技術の欄で説明した鍵指定コード等のタグ情報を用いて表してもよい。さらに、情報の暗号化は、セッションキーＫｓをそのまま使ってもよいし、たとえばセッションキーＫｓをＳＨＡ−１や、ＭＤ５等のハッシュ関数に入力して所望のサイズに変換した値を用いてもよい。
【０２２０】
たとえば放送アプリケーションの場合には、情報復号許容受信機集合Ｓを表す情報を送信した後に放送コンテンツをセッションキーＫｓで暗号化して送信してもよいし、情報復号許容受信機集合Ｓを表す情報と、セッションキーＫｓを用いてコンテンツキーＫｃを暗号化した暗号文を送信した後に、セッションキーＫｓで暗号化されたコンテンツを送信してもよい。ＣＤなどの記録メディアのアプリケーションの場合には、放送アプリケーションにおいて放送していた情報をディスクに記録して配布すればよい。
【０２２１】
ところで、送信者がセッションキーＫｓを導出する際には、別の方法を用いてもよい。すなわち、ｉ∈Ｋである部分木ルート集合Ｋの要素数｜Ｋ｜個のｉをピックアップし、さらに２Ｎから２Ｎ＋ｎ−｜Ｋ｜までのｎ＋１−｜Ｋ｜個のｉをピックアップする。ピックアップされた全部でｎ＋１個のｉのうちのｎ個に対応するｈｉをそれぞれ入力としてマップｅの出力を求め、その出力に対し残ったひとつのｉに対するｘｉ乗（Ｇ２上で）を行うことにより上記と等しいＫｓを求めることができる。なお、この求め方は、後述の、受信機ｕｍがＫｓを求める方法と同様である。
【０２２２】
（３）受信および復号
受信機ｕｍは、同報通信路から送信された情報を受信し、自分がその通信において情報を復号させる受信機の集合、すなわち情報復号許容受信機集合Ｓに含まれるかどうかを調べる。これは、自身が秘密鍵を持つノード（自分が割り当てられた葉からルートまでのパス上のノード）がＫに含まれるかどうかを調べることにより行える。もし自分が情報復号許容受信機集合Ｓに含まれなければ、その通信を復号できないので処理を終了する。自分が情報復号許容受信機集合Ｓに含まれていれば、下記の処理によりセッションキーＫｓを求め、これを用いて送信された情報を復号する。もし受信機ｕｍが情報復号許容受信機集合Ｓに含まれていれば、Ｋに含まれるノードのうちのただ１つが、ｕｍが秘密鍵を保持しているノードの１つとなる。このノードをＩとする。
【０２２３】
１．カウンタｊ，ｌを用意し、ｊ＝１，ｌ＝２Ｎとセットする。
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる。
（ａ）もしｉ∈Ｋかつｉ≠ＩならばΦｊ＝ｈｉとセットし、ｊを１増やして次のｉの処理に移る。
３．もしｊ≦ｎならばｊ≦ｎの間、下記の処理を繰り返す。
（ａ）Φｊ＝ｈｌとセットし、ｌを１増やし、ｊを１増やす。
４．以下のセッションキーＫｓを求める。
【数４９】
2005123678.tif 000040
【０２２４】
たとえば図７のセッティングで、受信機ｕ４はノード９の秘密鍵ｘ９を所持しているので、下式、
【数５０】
2005123678.tif 000041
によりＫｓを求める。
【０２２５】
上記の構成とすることにより、実施例１と同様、ｎマルチリニアマップを用いてブロードキャスト・エンクリプション方式を構成可能となる。
【０２２６】
本実施例の方式で同報通信される暗号文は１つであり、各受信機が安全に保持する鍵の数はｌｏｇＮ＋１個である。また、ｎはｒｌｏｇ（Ｎ／ｒ）−１を上限として定めることができる。関数の実行量は入力要素数に依存する。上述の論文で提案されている方式は、入力要素数ｎ＝Ｎであったためこのマッピングに要する計算量が大きくなると予想されるが、本発明では入力要素数を小さくすることでこの計算量を削減している。
【０２２７】
上述した処理例、すなわち、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすマルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）が存在するという前提の下で、マルチリニアマップを用いた鍵配信技術に階層木構造を組み合わせることによって、各受信機が必要とする計算量を削減させることを可能とした構成例において、暗号文を生成し、提供する情報処理装置において実行する処理シーケンスと、暗号文を受領して復号処理を行なうリーフ対応の例えば受信機等の情報処理装置における処理シーケンスは、実施例１において図８を参照して説明した暗号文送信側シーケンスと、図１１を参照して説明した暗号文受信側シーケンスと同様のものとなる。
【０２２８】
ただし、実施例２においては、暗号文送信側の処理におけるセッションキーＫｓの算出処理、および、暗号文受信側の処理におけるセッションキーＫｓの算出処理が異なるものとなる。
【０２２９】
すなわち、図８におけるステップＳ１０３におけるセッションキーＫｓは、図１６に示す算出処理、すなわち、前述したように、
【数５１】
2005123678.tif 000042
によって算出する。
【０２３０】
一方、暗号文受信側の処理におけるセッションキーＫｓの算出処理、すなわち、図１１におけるステップＳ２０３におけるセッションキーＫｓは、図１７に示す算出処理、すなわち、前述したように、以下の処理プロセスに従って、セッションキーＫｓを求める。
【０２３１】
１．カウンタｊ，ｌを用意し、ｊ＝１，ｌ＝２Ｎとセットする。
２．カウンタｉを用意し、以下の処理を行いながらｉを１から２Ｎ−１まで１ずつ増加させる。
（ａ）もしｉ∈Ｋかつｉ≠ＩならばΦｊ＝ｈｉとセットし、ｊを１増やして次のｉの処理に移る。
３．もしｊ≦ｎならばｊ≦ｎの間、下記の処理を繰り返す。
（ａ）Φｊ＝ｈｌとセットし、ｌを１増やし、ｊを１増やす。
４．以下のセッションキーＫｓを求める。
【数５２】
2005123678.tif 000043
【０２３２】
（ｂ）ｎ＝２とした暗号学的な２マルチリニアマップを用いたブロードキャスト・エンクリプション方式
【０２３３】
上述の実施例においては、任意のｎ（ｎ＞１）に対する暗号学的なｎマルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）が存在することを前提としているが、以下、既に実証されているｎ＝２とした暗号学的なｎマルチリニアマップ、すなわち２マルチリニアマップにおける具体例を説明する。なお、ｎ＝２とした暗号学的なｎマルチリニアマップについては、Ｄ．Ｂｏｎｅｈ  ａｎｄ  Ｍ．Ｆｒａｎｋｌｉｎ著の論文"Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  Ｐａｒｉｎｇ"（この論文は、著者の一人であるＰｒｏｆ．Ｂｏｎｅｈが管理するウェブサイトにｈｔｔｐ：／／ｃｒｙｐｔｏ．ｓｔａｎｆｏｒｄ．ｅｄｕ／~ｄａｂｏ．／ｐａｐｅｒｓ／ｉｂｅ．ｐｄｆとして掲載されている）
【０２３４】
以下、ｎ＝２とした２マルチリニアマップを適用したブロードキャスト・エンクリプション方式について、上述の例と同様、
（１）セットアップ、
（２）暗号化および送信、
（３）受信および復号、
の３つのフェーズに区分して説明する。
【０２３５】
セットアップフェーズは、システムの立ち上げ時に１度だけ行う。暗号化および送信、受信および復号の各フェーズは、情報の送信を行うたびに繰り返す。
【０２３６】
ブロードキャスト・エンクリプション方式を構成するエンティティとして、暗号文の生成および提供処理を行なう情報処理装置としての送信者（送信機）と、暗号文の受領および復号処理を行なう情報処理装置としてのユーザデバイス等の受信機あるいは受信者（ユーザ）であり、暗号文の受領および復号処理を行なう情報処理装置またはユーザの総数をＮとする。また、システムを管理する管理センタを設ける。上記（１）セットアップ処理は、送信者あるいは管理センタが実行する。
【０２３７】
簡単のため、暗号文を受領する情報処理装置またはユーザの総数：Ｎは２のべき乗の数とする。実際のＮが２のべき乗でない場合は、Ｎより大きな最小の２のべき乗の数をＮとして用いても構わない。
【０２３８】
（１）セットアップ
以下、暗号文の生成および提供処理を行なうエンティティまたは情報処理装置を送信者または送信機とし、暗号文を受領するエンティティまたは情報処理装置を受信者または受信機として説明する。セットアップ処理は、送信者側、あるいはシステム管理者によって実行されるが、以下では、送信者においてセットアップ処理を行うものとして説明する。
【０２３９】
送信者は、実施例１と同様に、リーフ（葉）の数がＮである２分木を定義し、各ノードｉに番号を付与する。受信機は１つずつ各リーフ（葉）に割り当てる。
【０２４０】
送信者はｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすｎマルチリニアマップ（ｎ−ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）を定め、受信機に公開する。ただし、ｎ＝２である。
【０２４１】
次に、ｉ＝１，２，・・・，２Ｎ＋ｎ−１の各ｉに対し、ランダムな値ｘｉ∈［１，ｐ−１］を選び、それぞれに対し、
【数５３】
2005123678.tif 000044
を計算する。ただし、ｎ＝２であるのでｉ＝１〜２Ｎ＋１である。また、ここでｐは群Ｇ１の位数であり、ｇはＧ１の生成元である。各ｈｉを公開する。
【０２４２】
なお、ｘｉ、ｈｉは、ノードｉに対応するが、ノード番号２Ｎおよび２Ｎ＋１のダミーノードの存在を仮定し、ｘ２Ｎ，ｈ２Ｎはノード２Ｎに、ｘ２Ｎ＋１，ｈ２Ｎ＋１はノード２Ｎ＋１に対応すると考える。
【０２４３】
受信機ｕｍには、それが割り当てられた葉からルートに至るまでのパス上の各ノードｊに対応するｌｏｇＮ＋１個のｘｊを与える。受信機はｘｊを安全に保管する。
【０２４４】
いま、図４のセッティングで、Ｎ＝１６であり、ｎ＝２であるので、２Ｎ＋ｎ−１＝３３なので、送信者はｘ１，・・・，ｘ３３とｈ１，・・・，ｈ３３を用意してｈｉを公開する。例えば、受信機ｕ４には、ノード１，２，４，９，１９に対応するｘ１，ｘ２，ｘ４，ｘ９，ｘ１９を与える。
【０２４５】
（２）暗号化および送信
送信者はＮ個の受信機のうち、その通信において情報を復号させる受信機の集合、すなわち情報復号許容受信機集合Ｓ⊆｛１，・・・，ｎ｝を選択する。次に、情報復号許容受信機集合Ｓに含まれない、すなわちリボークするレシーバに割り当てられたリーフ（葉）からルートまでのすべての枝、ノード、そのノードに接する枝を取り除く。すると、１つ以上の切り離された部分木が残るが、それぞれの部分木のルートの集合をＫと置く。
【０２４６】
次に、Ｋの要素をその番号ｉの順に、３つずつ、
【数５４】
2005123678.tif 000045
個のサブグループＳＧｋに分割する。
【０２４７】
ただし、
【数５５】
2005123678.tif 000046
である。
【０２４８】
なお、
｜Ｋ｜は、部分木ルート集合Ｋの要素数を示し、
【数５６】
2005123678.tif 000047
は、｜Ｋ｜／３以上である最小の整数を表す。
【０２４９】
ただし、最後のサブグループ
【数５７】
2005123678.tif 000048
にＫの要素が１つしか入らない場合には、ダミー受信機２Ｎと２Ｎ＋１もサブグループの要素であるとし、また、
【数５８】
2005123678.tif 000049
に、部分木のルートの集合Ｋの要素が２つだけ入る場合には、ダミーの受信機２Ｎもこのサブグループの要素であるとする。
【０２５０】
上述の例と同様、図４に示す２分木構成、すなわち、各受信機が１つずつ各リーフ（葉）に割り当てられ受信者数Ｎ＝１６である２分木構成を想定し、図７に示すように、図４のセッティングでｕ３，ｕ１１，ｕ１２の３台の受信機をリボークする場合の処理について説明する。
【０２５１】
図７に示すように、部分木のルートの集合Ｋ＝｛５，７，９，１２，１６｝となる。この場合、サブグループは、
ＳＧ１＝｛５，７，９｝
ＳＧ２＝｛１２，１６，３２｝
となる。
ただし、ノード３２はダミーノードである。
【０２５２】
そして、その通信におけるサブグループＳＧｋ用のサブグループキーＫＳＧｋを、
【数５９】
2005123678.tif 000050
として定める。
【０２５３】
上記の例では、サブグループＳＧ１とサブグループＳＧ２のサブグループキーは以下のように示される。
【数６０】
2005123678.tif 000051
【０２５４】
次に、その通信における全体のセッションキーＫｓをランダムに定める。セッションキーＫｓは通信の内容（たとえば映画などのコンテンツ）を暗号化するための鍵であり、たとえば暗号化アルゴリズムに米国標準のＡＥＳの１２８ｂｉｔ版を用いる際には、セッションキーＫｓは１２８ｂｉｔとなる。
【０２５５】
次に、個々のサブグループキーを用いてセッションキーＫｓを暗号化した暗号文
【数６１】
2005123678.tif 000052
を、暗号文
ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）として設定する。
ただし、Ｅ（Ａ，Ｂ）は鍵Ａを用いた平文Ｂの暗号化を示す。
【０２５６】
暗号化アルゴリズムとしてはたとえば米国標準のＡＥＳの１２８ｂｉｔ版を用いる。関数Ｈは、Ｇ２の任意の要素を、使用する暗号化アルゴリズムの鍵長（たとえば１２８ｂｉｔ）に縮約するハッシュ関数である。暗号化アルゴリズムＥとハッシュ関数Ｈはシステムであらかじめ定めてあり（送信者が定めてもよい）、公開されている。
【０２５７】
送信者は、送信すべき情報をセッションキーＫｓを用いて暗号化して、部分木のルートの集合Ｋを表す情報（たとえば、ノード番号のリスト）と、上記の暗号文、
【数６２】
2005123678.tif 000053
とを、ともに同報通信路で受信機に送信する。
【０２５８】
たとえば放送アプリケーションの場合には、部分木のルートの集合Ｋを表す情報を送信した後に、暗号文、
【数６３】
2005123678.tif 000054
を送信し、その後に放送コンテンツをセッションキーＫｓで暗号化して送信してもよいし、通信において情報を復号させる受信機の集合、すなわち情報復号許容受信機集合Ｓを表す情報と、暗号文
【数６４】
2005123678.tif 000055
と、セッションキーＫｓで暗号化したコンテンツキーＫｃを送信した後に、コンテンツキーＫｃで暗号化されたコンテンツを送信してもよい。ＣＤなどの記録メディアのアプリケーションの場合には、放送アプリケーションにおいて放送していた情報をディスクに記録して配布すればよい。
【０２５９】
（３）受信および復号
受信機ｕｍは、同報通信路から送信された情報を受信し、自分がその通信において情報を復号させる受信機の集合、すなわち情報復号許容受信機集合Ｓに含まれるかどうかを調べる。これは、自身が秘密鍵を持つノード（自分が割り当てられた葉からルートまでのパス上のノード）がＫに含まれるかどうかを調べることにより行える。
【０２６０】
もし自分が情報復号許容受信機集合Ｓに含まれなければ、その通信を復号できないので処理を終了する。自分が情報復号許容受信機集合Ｓに含まれていれば、自分がどのサブグループの暗号文を復号すべきかを調べる。これは、部分木のルートの集合Ｋの要素を３つずつ区切ったときの何番目に、自分が秘密鍵を持つノードが入るかを探すことで求められる。そして、受信機ｕｍは、自分が所有する秘密鍵に対応するサブグループＳＧｋのサブグループキーを下記のようにして求める。
【０２６１】
【数６５】
2005123678.tif 000056
ここで、ｘｉは、サブグループＳＧｋの要素のうち、受信機ｕｍが秘密鍵を持つノードｉに対応する秘密鍵であり、ｈｊ１、ｈｊ２は、ｉではないほうのノードｊ１，ｊ２に対応する公開情報ｇｉである。ただし、ｉが、サブグループ
【数６６】
2005123678.tif 000057
の要素であり、このサブグループに部分木のルートの集合Ｋの要素（実在の要素）が１つしか含まれない場合には、ダミーノード２Ｎおよび２Ｎ＋１に対応する公開情報ｈ２Ｎ，ｈ２Ｎ＋１を用い、このサブグループに部分木のルートの集合Ｋの要素（実在の要素）が２つだけ含まれる場合には、ダミーノード２Ｎに対応する公開情報ｈ２Ｎを用いる。
【０２６２】
たとえば上記の例で受信機ｕ４はノード９の秘密鍵ｘ９を所持しているので、
ＫＳＧ１＝ｅ（ｈ５，ｈ７）ｘ９
としてサブグループＳＧ１のサブグループキーＫＳＧ１を求めることができる。
【０２６３】
次に、受信機ｕｍは、上で求めたサブグループキーＫＳＧｋからハッシュ値Ｈ（ＫＳＧｋ）を計算し、これを用いて暗号文ＣＴｋを復号してセッションキーＫｓを求め、これを用いて送信された情報を復号する。
【０２６４】
上記のような構成とすることにより、２マルチリニアマップを用いてＮ個の受信機に鍵（セッションキーＫｓ）を安全に配信できるシステムを構成することが可能となる。上記構成では受信機が安全に保管しなければならない鍵は１つ（ｘｉ）だけであり、たとえばセッションキーＫｓを直接コンテンツの暗号化に用いる場合などにおいて、鍵配信のために同報通信されるメッセージの個数は、
【数６７】
2005123678.tif 000058
となる。
【０２６５】
なお、リボークする受信機数をｒとしたときに、部分木ルート集合Ｋの要素数｜Ｋ｜の最大値はｒｌｏｇ２（Ｎ／ｒ）であることがわかっている。
【０２６６】
上記は２マルチリニアマップを用いる方法について詳しく述べたが、この方式は、前述したように、任意の整数ｎ＞１に対するｎマルチリニアマップを用いる方式にそのまま拡張可能である。ｎが大きくなると、受信機が保管する鍵数は１のままであるのに対し、同報通信されるメッセージ数が、
【数６８】
2005123678.tif 000059
となり、上記のｎ＝２の場合に比べてこの面での効率がよくなる。
【０２６７】
上述した処理例、すなわち、ｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たす２マルチリニアマップを用いた鍵配信技術に階層木構造を組み合わせることによって、各受信機が必要とする計算量を削減させることを可能とした構成例において、暗号文を生成し、提供する情報処理装置において実行する処理シーケンスと、暗号文を受領して復号処理を行なうリーフ対応の例えば受信機等の情報処理装置における処理シーケンスは、先に実施例１において説明した図１３（暗号文提供側）、図１５（暗号文受領側）と同様の処理シーケンスによって実行される。ただし、それぞれの処理において、サブグループキーの算出処理方法が異なってくる。サブグループキーの算出処理は上述の説明に記載の通りである。
【０２６８】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０２６９】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０２７０】
例えば、プログラムは記録媒体としてのハードディスクやＲＯＭ（Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０２７１】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０２７２】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０２７３】
以上、説明したように、本発明の構成によれば、頂点ノードとしてのルートと、最下位ノードであるリーフを連結した構成を持つ階層木構成において、リーフに対応する複数の情報処理装置から暗号文の復号を許容する情報処理装置を選択し、選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文の生成処理において、ｎマルチリニアマップ（ただし、ｎは２以上の整数）を適用して暗号鍵を生成する構成とすることで、暗号文復号許容機器の格納鍵のみに基づいて復号可能な１つの暗号文として生成することが可能となり、暗号文の受領、復号処理を実行する受信機としてのユーザデバイスにおける計算量が削減され、効率的な処理が実現される。従って、本発明は、階層木構造を適用した暗号文の提供構成において利用可能である。具体的には、暗号文生成、提供、送信を実行する情報処理装置、暗号文の復号、再生を実行するユーザデバイスとしての情報処理装置、暗号化コンテンツ等を格納した情報記録媒体において適用可能である。
【０２７４】
本発明の構成によれば、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ｉｎｖｅｒｓｉｏｎ  ａｓｓｕｍｐｔｉｏｎ、またはｇｅｎｅｒａｌｉｚｅｄ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  ａｓｓｕｍｐｔｉｏｎを満たすマルチリニアマップ（ｍｕｌｔｉｌｉｎｅａｒ  ｍａｐ）に階層型木構造を組み合わせた暗号文配信構成を構築することにより、階層木構成中のリーフに対応する複数の情報処理装置から選択した暗号文復号許容機器の格納鍵のみに基づいて復号可能な暗号文として必要な数を削減することが可能となり、リーフの数の増加、リボーク機器の増加などの要因が発生した場合においても、必要な暗号文数を増加させることのない効率的な暗号文の生成および提供構成が実現される。従って、本発明は、階層木構造を適用した暗号文の提供構成において利用可能である。具体的には、暗号文生成、提供、送信を実行する情報処理装置、暗号文の復号、再生を実行するユーザデバイスとしての情報処理装置、暗号化コンテンツ等を格納した情報記録媒体において適用可能である。
【図面の簡単な説明】
【０２７５】
【図１】２分木階層型木構造について説明する図である。
【図２】２分木階層型木構造において、選択した情報処理装置のみが取得可能な情報を送信する方法を説明する図である。
【図３】鍵指定コードを暗号文とともに各情報処理装置に提供する構成について説明する図である。
【図４】本発明の適用可能な葉（リーフ）の数が受信者数Ｎである階層木構成例を示す図である。
【図５】暗号文を生成し提供する送信装置等の情報処理装置、暗号文を受領して情報取得を行なう受信装置等の情報処理装置の構成例を示す図である。
【図６】階層木構成に基づいて暗号文を情報処理装置に提供する構成におけるリーフの所有鍵数および提供暗号文数について説明する図である。
【図７】リボーク受信機を排除した部分木構成について説明する図である。
【図８】暗号文を生成し、提供する情報処理装置において実行する処理シーケンスについて説明するフローチャートである。
【図９】暗号文を生成し、提供する情報処理装置において実行するセッションキーＫｓの具体的計算例を説明する図である。
【図１０】暗号文を生成し、提供する情報処理装置において生成した情報の情報記録媒体格納例を示す図である。
【図１１】暗号文を受領し、復号する情報処理装置において実行する処理シーケンスについて説明するフローチャートである。
【図１２】暗号文を受領し、復号する情報処理装置において実行するセッションキーＫｓの具体的計算例を説明する図である。
【図１３】ｎ＝２のマルチリニアマップ適用時において、暗号文を生成し、提供する情報処理装置において実行する処理シーケンスについて説明するフローチャートである。
【図１４】ｎ＝２のマルチリニアマップ適用時において、暗号文を生成し、提供する情報処理装置において生成した情報の情報記録媒体格納例を示す図である。
【図１５】ｎ＝２のマルチリニアマップ適用時において、暗号文を受領し、復号する情報処理装置において実行する処理シーケンスについて説明するフローチャートである。
【図１６】暗号文を生成し、提供する情報処理装置において実行するセッションキーＫｓの具体的計算例を説明する図である。
【図１７】暗号文を受領し、復号する情報処理装置において実行するセッションキーＫｓの具体的計算例を説明する図である。
【符号の説明】
【０２７６】
１０１，１０２  情報処理装置
１２０  ルートノード
１２１，１２２，１２３  ノード
１３１，１３２，１３３，１３４，１３５  部分木
３０１  コントローラ
３０２  演算ユニット
３０３  入出力インタフェース
３０４  セキュア記憶部
３０５  メイン記憶部
３０６  大容量記憶部
４００  情報記録媒体
４０１  部分木のルート集合Ｋを示す情報
４０２  暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）
４０３  暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）
５００  情報記録媒体
５０１  部分木のルート集合Ｋを示す情報
５０２  暗号文ＣＴｋ＝Ｅ（Ｈ（ＫＳＧｋ），Ｋｓ）
５０３  暗号化コンテンツキーＥｎｃ（Ｋｓ，Ｋｃ）
５０４  暗号化コンテンツＥｎｃ（Ｋｃ，Ｃｏｎ）
【図１】
2005123678.tif 000072
【図２】
2005123678.tif 000073
【図３】
2005123678.tif 000074
【図４】
2005123678.tif 000075
【図５】
2005123678.tif 000076
【図６】
2005123678.tif 000077
【図７】
2005123678.tif 000078
【図８】
2005123678.tif 000079
【図９】
2005123678.tif 000080
【図１０】
2005123678.tif 000081
【図１１】
2005123678.tif 000082
【図１２】
2005123678.tif 000083
【図１３】
2005123678.tif 000084
【図１４】
2005123678.tif 000085
【図１５】
2005123678.tif 000086
【図１６】
2005123678.tif 000087
【図１７】
2005123678.tif 000088