(57)【要約】【課題】階層型木構造を適用した暗号鍵等の暗号データ提供処理において、ルートから自己の属するリーフまでのパス上の各ノードに対応するノードキーを算出するための計算処理を軽減することを可能とした情報処理装置および方法を提供する。【解決手段】階層型木構造を適用した暗号データ提供処理において、ａ分木（ＨＫＴ）における各ノードキーの算出処理および設定処理に落とし戸つき一方向置換Ｆｉと、逆置換Ｆ−１ｉを適用し、各デバイスにおけるノードキーの算出において、最大でも木の高さの回数だけの落とし戸付き一方向置換Ｆｉを実行すればノードキー算出を完了する構成とした。デバイスに保持するキーを用いて、繰り返し、落とし戸付き一方向置換Ｆｉを実行することで、順次、上位ノードのノードキーが算出される。【選択図】  図５
2004320183.tif 000002
【特許請求の範囲】
【請求項１】
暗号データ生成処理を実行する情報処理装置であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する構成を有し、
前記送信秘密情報の暗号化に適用するノードキーは、前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定されたノードキーであることを特徴とする情報処理装置。
【請求項２】
前記情報処理装置は、
前記送信秘密情報の暗号化に適用する選択した各ノードキーを用いて秘密情報を暗号化した暗号文セットを生成するとともに、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用したノードキーとの対応を示す表現コードを生成し、前記暗号文セットおよび前記表現コードとをデバイスに対して送信する処理を実行する構成であることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用したノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応するノードキーＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記送信秘密情報の暗号化に適用するノードキーの選択処理は、
前記階層型木構造の最下位ノードに対応するデバイス中、前記選択された限定デバイス以外の排除デバイスに対応する前記階層型木構造の葉からルートにいたるパス上のノード以外のノードによって構成される部分木の頂点ノードに対応するノードキー選択処理として実行する構成であることを特徴とする請求項１に記載の情報処理装置。
【請求項６】
前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする請求項１に記載の情報処理装置。
【請求項７】
前記落とし戸つき一方向置換Ｆｉは、
異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする請求項１に記載の情報処理装置。
【請求項８】
前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数１】
2004320183.tif 000019
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする請求項１に記載の情報処理装置。
【請求項９】
前記情報処理装置は、
ノードキーＮＫｋを適用した送信秘密情報の暗号化処理による暗号文生成に際し、ハッシュ関数を適用し、暗号文のビット長変更処理を実行する構成であることを特徴とする請求項１に記載の情報処理装置。
【請求項１０】
暗号データ生成処理を実行する情報処理装置であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された公開ノードキーＰｕｂＮＫｋを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する構成を有し、
前記送信秘密情報の暗号化に適用する公開ノードキーは、前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された秘密ノードキーに対応して設定された公開ノードキーであることを特徴とする情報処理装置。
【請求項１１】
前記送信秘密情報の暗号化に適用する公開ノードキーＰｕｂＮＫｋは、
ＰｕｂＮＫｋ＝ｇＰｒｉＮＫｋｍｏｄｑ
ただし、ｑは大きな素数、ｇは巡回群Ｚｑの生成元、
によって算出される公開ノードキーであることを特徴とする請求項１０に記載の情報処理装置。
【請求項１２】
前記情報処理装置は、
公開ノードキーＰｕｂＮＫｋを適用した送信秘密情報Ｉの暗号化処理による暗号文ＣＴｋの生成を、
【数２】
2004320183.tif 000020
ただし、ｘは、区間［１，ｑ−１］からランダムに選択した値、
によって実行する構成であることを特徴とする請求項１１に記載の情報処理装置。
【請求項１３】
前記情報処理装置は、
前記送信秘密情報の暗号化に適用する選択した各公開ノードキーを用いて秘密情報を暗号化した暗号文セットを生成するとともに、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用した公開ノードキーとの対応を示す表現コードを生成し、前記暗号文セットおよび前記表現コードとをデバイスに対して送信する処理を実行する構成であることを特徴とする請求項１０に記載の情報処理装置。
【請求項１４】
前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用した公開ノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする請求項１３に記載の情報処理装置。
【請求項１５】
前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする請求項１０に記載の情報処理装置。
【請求項１６】
前記送信秘密情報の暗号化に適用する公開ノードキーの選択処理は、
前記階層型木構造の最下位ノードに対応するデバイス中、前記選択された限定デバイス以外の排除デバイスに対応する前記階層型木構造の葉からルートにいたるパス上のノード以外のノードによって構成される部分木の頂点ノードに対応する公開ノードキー選択処理として実行する構成であることを特徴とする請求項１０に記載の情報処理装置。
【請求項１７】
前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする請求項１０に記載の情報処理装置。
【請求項１８】
前記落とし戸つき一方向置換Ｆｉは、
異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする請求項１０に記載の情報処理装置。
【請求項１９】
前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数３】
2004320183.tif 000021
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする請求項１０に記載の情報処理装置。
【請求項２０】
前記情報処理装置は、
公開ノードキーＰｕｂＮＫｋを適用した送信秘密情報の暗号化処理による暗号文生成に際し、ハッシュ関数を適用し、暗号文のビット長変更処理を実行する構成であることを特徴とする請求項１０に記載の情報処理装置。
【請求項２１】
暗号データ復号処理を実行する情報処理装置であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した暗号データの復号処理を実行する構成を有し、
前記ａ分木構成を持つ階層型木構造のノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定された構成であり、
前記情報処理装置は、
情報処理装置対応ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用するノードキーの算出処理を実行する構成を有することを特徴とする情報処理装置。
【請求項２２】
前記情報処理装置は、
複数のノードキーを用いて秘密情報を暗号化した複数の暗号文から構成される暗号文セット中から、前記情報処理装置対応ノードキーに基づいて算出可能なノードキーを適用して復号可能な暗号文の検出処理を実行する構成を有し、
前記暗号文セットを構成する各暗号文と、該暗号文生成に適用したノードキーとの対応を示す表現コードに基づいて前記検出処理を実行する構成であることを特徴とする請求項２１に記載の情報処理装置。
【請求項２３】
前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用したノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする請求項２２に記載の情報処理装置。
【請求項２４】
前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応するノードキーＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする請求項２１に記載の情報処理装置。
【請求項２５】
前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする請求項２１に記載の情報処理装置。
【請求項２６】
前記落とし戸つき一方向置換Ｆｉは、
異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする請求項２１に記載の情報処理装置。
【請求項２７】
前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数４】
2004320183.tif 000022
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする請求項２１に記載の情報処理装置。
【請求項２８】
前記情報処理装置は、
秘密ノードキーＰｒｉＮＫｋを適用した送信秘密情報の復号処理に際し、ハッシュ関数を適用し、復号に適用する鍵のビット長変更処理を実行する構成であることを特徴とする請求項２１に記載の情報処理装置。
【請求項２９】
暗号データ復号処理を実行する情報処理装置であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された秘密ノードキーを選択的に適用して、前記秘密ノードキーに対応する公開ノードキーによって暗号化された暗号データの復号処理を実行する構成を有し、
前記ａ分木構成を持つ階層型木構造の各ノードに対応する秘密ノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された構成であり、
前記情報処理装置は、
情報処理装置対応秘密ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用する秘密ノードキーの算出処理を実行する構成を有することを特徴とする情報処理装置。
【請求項３０】
前記情報処理装置は、
秘密ノードキーＰｒｉＮＫｋを適用した暗号文ＣＴｋの復号による秘密情報Ｉの取得を、
【数５】
2004320183.tif 000023
ただし、ｇｘｍｏｄｑは、既知の値、
によって実行する構成であることを特徴とする請求項２９に記載の情報処理装置。
【請求項３１】
前記情報処理装置は、
前記ａ分木構成における複数の異なるノードの公開ノードキーを用いて秘密情報を暗号化した複数の暗号文から構成される暗号文セット中から、前記情報処理装置対応秘密ノードキーに基づいて算出可能な秘密ノードキーを適用して復号可能な暗号文の検出処理を実行する構成を有し、
前記暗号文セットを構成する各暗号文と、該暗号文生成に適用した公開ノードキーとの対応を示す表現コードに基づいて前記検出処理を実行する構成であることを特徴とする請求項２９に記載の情報処理装置。
【請求項３２】
前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用した公開ノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする請求項３１に記載の情報処理装置。
【請求項３３】
前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする請求項２９に記載の情報処理装置。
【請求項３４】
前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする請求項２９に記載の情報処理装置。
【請求項３５】
前記落とし戸つき一方向置換Ｆｉは、
異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする請求項２９に記載の情報処理装置。
【請求項３６】
前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数６】
2004320183.tif 000024
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする請求項２９に記載の情報処理装置。
【請求項３７】
前記情報処理装置は、
秘密ノードキーＰｒｉＮＫｋを適用した秘密情報の復号処理に際し、ハッシュ関数を適用する構成であることを特徴とする請求項２９に記載の情報処理装置。
【請求項３８】
暗号データ生成処理を実行する情報処理方法であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する暗号処理ステップを有し、
前記暗号処理に適用するノードキーは、前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定されたノードキーであることを特徴とする情報処理方法。
【請求項３９】
前記情報処理方法は、さらに、
前記送信秘密情報の暗号化に適用する選択した各ノードキーを用いて秘密情報を暗号化した暗号文セットを生成するとともに、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用したノードキーとの対応を示す表現コードを生成し、前記暗号文セットおよび前記表現コードとをデバイスに対して送信する処理を実行するステップを有することを特徴とする請求項３８に記載の情報処理方法。
【請求項４０】
前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用したノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする請求項３９に記載の情報処理方法。
【請求項４１】
前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応するノードキーＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする請求項３８に記載の情報処理方法。
【請求項４２】
前記送信秘密情報の暗号化に適用するノードキーの選択処理は、
前記階層型木構造の最下位ノードに対応するデバイス中、前記選択された限定デバイス以外の排除デバイスに対応する前記階層型木構造の葉からルートにいたるパス上のノード以外のノードによって構成される部分木の頂点ノードに対応するノードキー選択処理として実行することを特徴とする請求項３８に記載の情報処理方法。
【請求項４３】
前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする請求項３８に記載の情報処理方法。
【請求項４４】
前記落とし戸つき一方向置換Ｆｉは、
異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする請求項３８に記載の情報処理方法。
【請求項４５】
前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数７】
2004320183.tif 000025
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする請求項３８に記載の情報処理方法。
【請求項４６】
前記暗号処理ステップは、
ノードキーＮＫｋを適用した送信秘密情報の暗号化処理による暗号文生成に際し、ハッシュ関数を適用し、暗号文のビット長変更処理を実行することを特徴とする請求項３８に記載の情報処理方法。
【請求項４７】
暗号データ生成処理を実行する情報処理方法であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された公開ノードキーＰｕｂＮＫｋを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する暗号処理ステップを有し、前記暗号処理に適用する公開ノードキーは、前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された秘密ノードキーに対応して設定された公開ノードキーであることを特徴とする情報処理方法。
【請求項４８】
前記送信秘密情報の暗号化に適用する公開ノードキーＰｕｂＮＫｋは、
ＰｕｂＮＫｋ＝ｇＰｒｉＮＫｋｍｏｄｑ
ただし、ｑは大きな素数、ｇは巡回群Ｚｑの生成元、
によって算出される公開ノードキーであることを特徴とする請求項４７に記載の情報処理方法。
【請求項４９】
前記情報処理方法は、
公開ノードキーＰｕｂＮＫｋを適用した送信秘密情報Ｉの暗号化処理による暗号文ＣＴｋの生成を、
【数８】
2004320183.tif 000026
ただし、ｘは、区間［１，ｑ−１］からランダムに選択した値、
によって実行する構成であることを特徴とする請求項４８に記載の情報処理方法。
【請求項５０】
前記情報処理方法は、さらに、
前記送信秘密情報の暗号化に適用する選択した各公開ノードキーを用いて秘密情報を暗号化した暗号文セットを生成するとともに、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用した公開ノードキーとの対応を示す表現コードを生成し、前記暗号文セットおよび前記表現コードとをデバイスに対して送信する処理を実行するステップを有することを特徴とする請求項４７に記載の情報処理方法。
【請求項５１】
前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用した公開ノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする請求項５０に記載の情報処理方法。
【請求項５２】
前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする請求項４７に記載の情報処理方法。
【請求項５３】
前記送信秘密情報の暗号化に適用する公開ノードキーの選択処理は、
前記階層型木構造の最下位ノードに対応するデバイス中、前記選択された限定デバイス以外の排除デバイスに対応する前記階層型木構造の葉からルートにいたるパス上のノード以外のノードによって構成される部分木の頂点ノードに対応する公開ノードキー選択処理として実行することを特徴とする請求項４７に記載の情報処理方法。
【請求項５４】
前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする請求項４７に記載の情報処理方法。
【請求項５５】
前記落とし戸つき一方向置換Ｆｉは、
異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする請求項４７に記載の情報処理方法。
【請求項５６】
前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数９】
2004320183.tif 000027
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする請求項４７に記載の情報処理方法。
【請求項５７】
前記情報処理方法は、さらに、
公開ノードキーＰｕｂＮＫｋを適用した送信秘密情報の暗号化処理による暗号文生成に際し、ハッシュ関数を適用し、暗号文のビット長変更処理を実行する構成であることを特徴とする請求項４７に記載の情報処理方法。
【請求項５８】
暗号データ復号処理を実行する情報処理方法であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した暗号データの復号処理を実行する復号処理ステップを有し、
前記ａ分木構成を持つ階層型木構造のノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定された構成であり、
前記情報処理方法は、
情報処理装置対応ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用するノードキーの算出処理を実行するステップを有することを特徴とする情報処理方法。
【請求項５９】
前記情報処理方法は、さらに、
複数のノードキーを用いて秘密情報を暗号化した複数の暗号文から構成される暗号文セット中から、前記情報処理装置対応ノードキーに基づいて算出可能なノードキーを適用して復号可能な暗号文の検出処理を実行するステップを有し、
前記暗号文セットを構成する各暗号文と、該暗号文生成に適用したノードキーとの対応を示す表現コードに基づいて前記検出処理を実行することを特徴とする請求項５８に記載の情報処理方法。
【請求項６０】
前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用したノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする請求項５９に記載の情報処理方法。
【請求項６１】
前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応するノードキーＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする請求項５８に記載の情報処理方法。
【請求項６２】
前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする請求項５８に記載の情報処理方法。
【請求項６３】
前記落とし戸つき一方向置換Ｆｉは、
異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする請求項５８に記載の情報処理方法。
【請求項６４】
前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数１０】
2004320183.tif 000028
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする請求項５８に記載の情報処理方法。
【請求項６５】
前記情報処理方法は、さらに、
ノードキーＮＫｋを適用した送信秘密情報の復号処理に際し、ハッシュ関数を適用し、復号に適用する鍵のビット長変更処理を実行することを特徴とする請求項５８に記載の情報処理方法。
【請求項６６】
暗号データ復号処理を実行する情報処理方法であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された秘密ノードキーを選択的に適用して、前記秘密ノードキーに対応する公開ノードキーによって暗号化された暗号データの復号処理を実行する復号処理ステップを有し、
前記ａ分木構成を持つ階層型木構造の各ノードに対応する秘密ノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された構成であり、
前記情報処理方法は、
情報処理装置対応秘密ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用する秘密ノードキーの算出処理を実行するステップを有することを特徴とする情報処理方法。
【請求項６７】
前記情報処理方法は、
秘密ノードキーＰｒｉＮＫｋを適用した暗号文ＣＴｋの復号による秘密情報Ｉの取得を、
【数１１】
2004320183.tif 000029
ただし、ｇｘｍｏｄｑは、既知の値、
によって実行することを特徴とする請求項６６に記載の情報処理方法。
【請求項６８】
前記情報処理方法は、
前記ａ分木構成における複数の異なるノードの公開ノードキーを用いて秘密情報を暗号化した複数の暗号文から構成される暗号文セット中から、前記情報処理装置対応秘密ノードキーに基づいて算出可能な秘密ノードキーを適用して復号可能な暗号文の検出処理を実行するステップを有し、
前記暗号文セットを構成する各暗号文と、該暗号文生成に適用した公開ノードキーとの対応を示す表現コードに基づいて前記検出処理を実行することを特徴とする請求項６６に記載の情報処理方法。
【請求項６９】
前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用した公開ノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする請求項６８に記載の情報処理方法。
【請求項７０】
前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする請求項６６に記載の情報処理方法。
【請求項７１】
前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする請求項６６に記載の情報処理方法。
【請求項７２】
前記落とし戸つき一方向置換Ｆｉは、
異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする請求項６６に記載の情報処理方法。
【請求項７３】
前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数１２】
2004320183.tif 000030
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする請求項６６に記載の情報処理方法。
【請求項７４】
前記情報処理方法は、
秘密ノードキーＰｒｉＮＫｋを適用した秘密情報の復号処理に際し、ハッシュ関数を適用する構成であることを特徴とする請求項６６に記載の情報処理方法。
【請求項７５】
暗号データ生成処理を実行するコンピュータ・プログラムであり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する暗号処理ステップを有し、
前記暗号処理に適用するノードキーは、前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定されたノードキーであることを特徴とするコンピュータ・プログラム。
【請求項７６】
暗号データ生成処理を実行するコンピュータ・プログラムであり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された公開ノードキーＰｕｂＮＫｋを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する暗号処理ステップを有し、
前記暗号処理に適用する公開ノードキーは、前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された秘密ノードキーに対応して設定された公開ノードキーであることを特徴とするコンピュータ・プログラム。
【請求項７７】
暗号データ復号処理を実行するコンピュータ・プログラムであり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した暗号データの復号処理を実行する復号処理ステップを有し、
前記ａ分木構成を持つ階層型木構造のノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定された構成であり、
前記コンピュータ・プログラムは、
情報処理装置対応ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用するノードキーの算出処理を実行するステップを有することを特徴とするコンピュータ・プログラム。
【請求項７８】
暗号データ復号処理を実行するコンピュータ・プログラムであり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された秘密ノードキーを選択的に適用して、前記秘密ノードキーに対応する公開ノードキーによって暗号化された暗号データの復号処理を実行する復号処理ステップを有し、
前記ａ分木構成を持つ階層型木構造の各ノードに対応する秘密ノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された構成であり、
前記情報処理方法は、
情報処理装置対応秘密ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用する秘密ノードキーの算出処理を実行するステップを有することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報処理装置、および情報処理方法、並びにコンピュータ・プログラムに関する。さらに、詳細には、ＣＤ、ＤＶＤ、ＭＤ等、各種のコンテンツ記録媒体に、記録媒体識別子を格納し、不正記録媒体のリストとしてのリボケーションリストに基づくコンテンツ利用制御を行うことにより、不正コピーコンテンツを格納したＣＤ−Ｒディスク等の氾濫、利用の防止を実現する情報記録媒体、情報処理装置、情報記録媒体製造装置、および方法、並びにコンピュータ・プログラムに関する。
【０００２】
【従来の技術】
昨今、音楽等のオーディオデータ、映画等の画像データ、ゲームプログラム、各種アプリケーションプログラム等、様々なソフトウエアデータ（以下、これらをコンテンツ（Ｃｏｎｔｅｎｔ）と呼ぶ）が、インターネット等のネットワークを介して、あるいはＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、ＭＤ（Ｍｉｎｉ  Ｄｉｓｋ）等の情報記録媒体（メディア）を介して流通している。これらの流通コンテンツは、ユーザの所有するＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）、ＣＤプレーヤ、ＤＶＤプレーヤ、ＭＤプレーヤ等の再生装置、あるいはゲーム機器等において再生され利用される。
【０００３】
音楽データ、画像データ等、多くのコンテンツは、一般的にその作成者あるいは販売者に頒布権等が保有されている。従って、これらのコンテンツの配布に際しては、一定の利用制限、すなわち、正規なユーザに対してのみ、コンテンツの利用を許諾し、許可のない複製等が行われないようにする構成をとるのが一般的となっている。
【０００４】
特に、近年においては、情報をデジタル的に記録する記録装置や記憶媒体が普及しつつある。このようなデジタル記録装置および記憶媒体によれば、例えば画像や音声を劣化させることなく記録、再生を繰り返すことが可能であり、不正コピーコンテンツのインターネットを介した配信や、コンテンツをＣＤ−Ｒ等にコピーした、いわゆる海賊版ディスクが大量に流通しているという問題がある。
【０００５】
このようなコンテンツの不正利用を防止する１つの方式として、コンテンツあるいは暗号化コンテンツを復号するための鍵を暗号化して配布し、特定の正規ユーザまたは正規デバイスのみが、配布データを復号することを可能としたシステムがある。例えばブロードキャストエンクリプション（Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ）方式の一態様である階層型木構造を適用した構成が知られている。
【０００６】
階層型木構造を適用した暗号鍵等の暗号データ提供処理について、図を参照して説明する。図１の最下段に示すナンバ０〜１５が、例えばコンテンツ利用を行なう情報処理装置としてのユーザデバイスである。すなわち図１に示す階層ツリー（木）構造の各葉（リーフ：ｌｅａｆ）がそれぞれのデバイスに相当する。
【０００７】
各デバイス０〜１５は、製造時あるいは出荷時、あるいはその後において、図１に示す階層ツリー（木）構造における自分のリーフからルートに至るまでのノードに割り当てられた鍵（ノードキー）および各リーフのリーフキーからなるキーセット（デバイスノードキー（ＤＮＫ：Ｄｅｖｉｃｅ  Ｎｏｄｅ  Ｋｅｙ））をメモリに格納する。図１の最下段に示すＫ００００〜Ｋ１１１１が各デバイス０〜１５にそれぞれ割り当てられたリーフキーであり、最上段のＫＲ（ルートキー）から、最下段から２番目の節（ノード）に記載されたキー：ＫＲ〜Ｋ１１１をノードキーとする。
【０００８】
図１に示す木構造において、例えばデバイス０はリーフキーＫ００００と、ノードキー：Ｋ０００、Ｋ００、Ｋ０、ＫＲを所有する。デバイス５はＫ０１０１、Ｋ０１０、Ｋ０１、Ｋ０、ＫＲを所有する。デバイス１５は、Ｋ１１１１、Ｋ１１１、Ｋ１１、Ｋ１、ＫＲを所有する。なお、図１のツリーにはデバイスが０〜１５の１６個のみ記載され、ツリー構造も４段構成の均衡のとれた左右対称構成として示しているが、さらに多くのデバイスがツリー中に構成され、また、ツリーの各部において異なる段数構成を持つことが可能である。
【０００９】
また、図１のツリー構造に含まれる各デバイスには、様々な記録媒体、例えば、デバイス埋め込み型あるいはデバイスに着脱自在に構成されたＤＶＤ、ＣＤ、ＭＤ、フラッシュメモリ等を使用する様々なタイプのデバイスが含まれている。さらに、様々なアプリケーションサービスが共存可能である。このような異なるデバイス、異なるアプリケーションの共存構成の上に図１に示すコンテンツあるいは鍵配布構成である階層ツリー構造が適用される。
【００１０】
これらの様々なデバイス、アプリケーションが共存するシステムにおいて、例えば図１の点線で囲んだ部分、すなわちデバイス０，１，２，３を同一の記録媒体を用いる１つのグループとして設定する。例えば、この点線で囲んだグループ内に含まれるデバイスに対しては、まとめて、共通のコンテンツを暗号化してプロバイダからネットワークまたはＣＤ等の情報記録媒体に格納して提供したり、各デバイス共通に使用するコンテンツ鍵を送付したり、あるいは各デバイスからプロバイダあるいは決済機関等にコンテンツ料金の支払データをやはり暗号化して出力するといった処理が実行される。コンテンツサーバ、ライセンスサーバ、あるいはショップサーバ等、各デバイスとのデータ送受信を行なうエンティテイは、図１の点線で囲んだ部分、すなわちデバイス０，１，２，３を１つのグループとして一括してデータを送付する処理を実行可能となる。このようなグループは、図１のツリー中に複数存在する。
【００１１】
なお、ノードキー、リーフキーは、ある１つの鍵管理センタ機能を持つ管理システムによって統括して管理してもよいし、各グループに対する様々なデータ送受信を行なうプロバイダ、決済機関等のメッセージデータ配信手段によってグループごとに管理する構成としてもよい。これらのノードキー、リーフキーは例えばキーの漏洩等の場合に更新処理が実行され、この更新処理は鍵管理センタ機能を持つ管理システム、プロバイダ、決済機関等が実行可能である。
【００１２】
このツリー構造において、図１から明らかなように、１つのグループに含まれる３つのデバイス０，１，２，３はデバイスノードキー（ＤＮＫ：Ｄｅｖｉｃｅ  Ｎｏｄｅ  Ｋｅｙ）として共通のキーＫ００、Ｋ０、ＫＲを含むデバイスノードキー（ＤＮＫ：Ｄｅｖｉｃｅ  Ｎｏｄｅ  Ｋｅｙ）を保有する。このノードキー共有構成を利用することにより、例えば共通のキーをデバイス０，１，２，３のみに提供することが可能となる。たとえば、共通に保有するノードキーＫ００は、デバイス０，１，２，３に共通する保有キーとなる。また、新たなキーＫｎｅｗをノードキーＫ００で暗号化した値Ｅｎｃ（Ｋ００，Ｋｎｅｗ）を、ネットワークを介してあるいは記録媒体に格納してデバイス０，１，２，３に配布すれば、デバイス０，１，２，３のみが、それぞれのデバイスにおいて保有する共有ノードキーＫ００を用いて暗号Ｅｎｃ（Ｋ００，Ｋｎｅｗ）を解いて新たなキーＫｎｅｗを得ることが可能となる。なお、Ｅｎｃ（Ｋａ，Ｋｂ）はＫｂをＫａによって暗号化したデータであることを示す。
【００１３】
また、ある時点ｔにおいて、デバイス３の所有する鍵：Ｋ００１１，Ｋ００１，Ｋ００，Ｋ０，ＫＲが攻撃者（ハッカー）により解析されて露呈したことが発覚した場合、それ以降、システム（デバイス０，１，２，３のグループ）で送受信されるデータを守るために、デバイス３をシステムから切り離す必要がある。そのためには、ノードキー：Ｋ００１，Ｋ００，Ｋ０，ＫＲをそれぞれ新たな鍵Ｋ（ｔ）００１，Ｋ（ｔ）００，Ｋ（ｔ）０，Ｋ（ｔ）Ｒに更新し、デバイス０，１，２にその更新キーを伝える必要がある。ここで、Ｋ（ｔ）ａａａは、鍵Ｋａａａの世代（Ｇｅｎｅｒａｔｉｏｎ）：ｔの更新キーであることを示す。
【００１４】
更新キーの配布処理ついて説明する。キーの更新は、例えば、図２（Ａ）に示す有効化キーブロック（ＥＫＢ：Ｅｎａｂｌｉｎｇ  Ｋｅｙ  Ｂｌｏｃｋ）と呼ばれるブロックデータによって構成されるテーブルをたとえばネットワーク、あるいは記録媒体に格納してデバイス０，１，２に供給することによって実行される。なお、有効化キーブロック（ＥＫＢ）は、図１に示すようなツリー構造を構成する各リーフに対応するデバイスに新たに更新されたキーを配布するための暗号化キーによって構成される。有効化キーブロック（ＥＫＢ）は、キー更新ブロック（ＫＲＢ：Ｋｅｙ  Ｒｅｎｅｗａｌ  Ｂｌｏｃｋ）と呼ばれることもある。
【００１５】
図２（Ａ）に示す有効化キーブロック（ＥＫＢ）には、ノードキーの更新の必要なデバイスのみが更新可能なデータ構成を持つブロックデータとして構成される。図２の例は、図１に示すツリー構造中のデバイス０，１，２において、世代ｔの更新ノードキーを配布することを目的として形成されたブロックデータである。図１から明らかなように、デバイス０，デバイス１は、更新ノードキーとしてＫ（ｔ）００、Ｋ（ｔ）０、Ｋ（ｔ）Ｒが必要であり、デバイス２は、更新ノードキーとしてＫ（ｔ）００１、Ｋ（ｔ）００、Ｋ（ｔ）０、Ｋ（ｔ）Ｒが必要である。
【００１６】
図２（Ａ）のＥＫＢに示されるようにＥＫＢには複数の暗号化キーが含まれる。最下段の暗号化キーは、Ｅｎｃ（Ｋ００１０，Ｋ（ｔ）００１）である。これはデバイス２の持つリーフキーＫ００１０によって暗号化された更新ノードキーＫ（ｔ）００１であり、デバイス２は、自身の持つリーフキーによってこの暗号化キーを復号し、Ｋ（ｔ）００１を得ることができる。また、復号により得たＫ（ｔ）００１を用いて、図２（Ａ）の下から２段目の暗号化キーＥｎｃ（Ｋ（ｔ）００１，Ｋ（ｔ）００）を復号可能となり、更新ノードキーＫ（ｔ）００を得ることができる。以下順次、図２（Ａ）の上から２段目の暗号化キーＥｎｃ（Ｋ（ｔ）００，Ｋ（ｔ）０）を復号し、更新ノードキーＫ（ｔ）０、図２（Ａ）の上から１段目の暗号化キーＥｎｃ（Ｋ（ｔ）０，Ｋ（ｔ）Ｒ）を復号しＫ（ｔ）Ｒを得る。一方、デバイスＫ００００．Ｋ０００１は、ノードキーＫ０００は更新する対象に含まれておらず、更新ノードキーとして必要なのは、Ｋ（ｔ）００、Ｋ（ｔ）０、Ｋ（ｔ）Ｒである。デバイスＫ００００．Ｋ０００１は、図２（Ａ）の上から３段目の暗号化キーＥｎｃ（Ｋ０００，Ｋ（ｔ）００）を復号しＫ（ｔ）００、を取得し、以下、図２（Ａ）の上から２段目の暗号化キーＥｎｃ（Ｋ（ｔ）００，Ｋ（ｔ）０）を復号し、更新ノードキーＫ（ｔ）０、図２（Ａ）の上から１段目の暗号化キーＥｎｃ（Ｋ（ｔ）０，Ｋ（ｔ）Ｒ）を復号しＫ（ｔ）Ｒを得る。このようにして、デバイス０，１，２は更新した鍵Ｋ（ｔ）Ｒを得ることができる。なお、図２（Ａ）のインデックスは、復号キーとして使用するノードキー、リーフキーの絶対番地を示す。
【００１７】
図１に示すツリー構造の上位段のノードキー：Ｋ（ｔ）０，Ｋ（ｔ）Ｒの更新が不要であり、ノードキーＫ００のみの更新処理が必要である場合には、図２（Ｂ）の有効化キーブロック（ＥＫＢ）を用いることで、更新ノードキーＫ（ｔ）００をデバイス０，１，２に配布することができる。
【００１８】
図２（Ｂ）に示すＥＫＢは、例えば特定のグループにおいて共有する新たなコンテンツ鍵を配布する場合に利用可能である。具体例として、図１に点線で示すグループ内のデバイス０，１，２，３がある記録媒体を用いており、新たな共通のコンテンツ鍵Ｋ（ｔ）ｃｏｎが必要であるとする。このとき、デバイス０，１，２，３の共通のノードキーＫ００を更新したＫ（ｔ）００を用いて新たな共通の更新コンテンツ鍵：Ｋ（ｔ）ｃｏｎを暗号化したデータＥｎｃ（Ｋ（ｔ）００，Ｋ（ｔ）ｃｏｎ）を図２（Ｂ）に示すＥＫＢとともに配布する。この配布により、デバイス４など、その他のグループの機器においては復号されないデータとしての配布が可能となる。
【００１９】
すなわち、デバイス０，１，２はＥＫＢを処理して得たＫ（ｔ）００を用いて上記暗号文を復号すれば、ｔ時点でのキー、例えばコンテンツの暗号化復号化に適用するコンテンツ鍵Ｋ（ｔ）ｃｏｎを得ることが可能になる。
【００２０】
図３に、ｔ時点でのキー、例えばコンテンツの暗号化復号化に適用するコンテンツ鍵Ｋ（ｔ）ｃｏｎをＥＫＢの処理によって取得する処理例を示す。ＥＫＢには、Ｋ（ｔ）００を用いてコンテンツ鍵Ｋ（ｔ）ｃｏｎを暗号化したデータＥｎｃ（Ｋ（ｔ）００，Ｋ（ｔ）ｃｏｎ）と図２（Ｂ）に示すデータとが格納されているとする。ここでは、デバイス０の処理例を示す。
【００２１】
図３に示すように、デバイス０は、記録媒体に格納されている世代：ｔ時点のＥＫＢと自分があらかじめ格納しているノードキーＫ０００を用いて上述したと同様のＥＫＢ処理により、ノードキーＫ（ｔ）００を生成する。さらに、復号した更新ノードキーＫ（ｔ）００を用いて暗号化データＥｎｃ（Ｋ（ｔ）００，Ｋ（ｔ）ｃｏｎ）を復号して更新コンテンツ鍵Ｋ（ｔ）ｃｏｎを取得する。さらに、デバイスは、後にそれを使用するために自分だけが持つリーフキーＫ００００で暗号化して格納してもよい。
【００２２】
また、別の例としてツリー構造のノードキーの更新は不必要で、時点ｔでのコンテンツ鍵Ｋ（ｔ）ｃｏｎのみを必要な機器が得られればよいという場合もある。この場合、下記のような方式とすることができる。
【００２３】
いま、図６の例と同様にデバイス０，１，２にのみコンテンツ鍵Ｋ（ｔ）ｃｏｎを送りたいとする。このときＥＫＢは、
バージョン（Ｖｅｒｓｉｏｎ）：ｔ
インデックス  暗号化キー
０００        Ｅｎｃ（Ｋ０００，  Ｋ（ｔ）ｃｏｎ）
００１０        Ｅｎｃ（Ｋ００１０，Ｋ（ｔ）ｃｏｎ）
となる。
【００２４】
デバイス０，１はＫ０００を用いて、またデバイス２はＫ００１０を用いて上記ＥＫＢのうちの１つの暗号文を復号することによりコンテンツ鍵を得ることができる。このようにすることにより、ノードキーの更新は行えないものの必要な機器にコンテンツ鍵を与える方法をより効率よく（すなわち、ＥＫＢに含まれる暗号文数を減らしてＥＫＢのサイズを小さくするとともに管理センタでの暗号化およびデバイスでの復号処理の回数を減らせる）することができる。
【００２５】
【発明が解決しようとする課題】
上述の方法では、各デバイスは木の高さ分、すなわちｌｏｇ２Ｎ個のノードキーを安全に保持する必要がある。階層が増加すればノード数も増加し、リーフにあるデバイスは、増加したノード数に対応する多数のノードキーの保持を強いられることになる。
【００２６】
本発明は、上述の問題点に鑑みてなされたものであり、階層型木構造を適用した暗号鍵等、暗号データ提供処理において、各デバイスが保持すべき鍵の数が１つとすることを可能とし、また、その１つの鍵から、ルートから自己の属するリーフまでのパス上の各ノードに対応するノードキーを算出する処理を効率的に実行することを可能とした情報処理装置、および情報処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【００２７】
【課題を解決するための手段】
本発明の第１の側面は、
暗号データ生成処理を実行する情報処理装置であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する構成を有し、
前記送信秘密情報の暗号化に適用するノードキーは、前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定されたノードキーであることを特徴とする情報処理装置にある。
【００２８】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、前記送信秘密情報の暗号化に適用する選択した各ノードキーを用いて秘密情報を暗号化した暗号文セットを生成するとともに、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用したノードキーとの対応を示す表現コードを生成し、前記暗号文セットおよび前記表現コードとをデバイスに対して送信する処理を実行する構成であることを特徴とする。
【００２９】
さらに、本発明の情報処理装置の一実施態様において、前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用したノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする。
【００３０】
さらに、本発明の情報処理装置の一実施態様において、前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応するノードキーＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする。
【００３１】
さらに、本発明の情報処理装置の一実施態様において、前記送信秘密情報の暗号化に適用するノードキーの選択処理は、前記階層型木構造の最下位ノードに対応するデバイス中、前記選択された限定デバイス以外の排除デバイスに対応する前記階層型木構造の葉からルートにいたるパス上のノード以外のノードによって構成される部分木の頂点ノードに対応するノードキー選択処理として実行する構成であることを特徴とする。
【００３２】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする。
【００３３】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする。
【００３４】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数１３】
2004320183.tif 000003
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、であることを特徴とする。
【００３５】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、ノードキーＮＫｋを適用した送信秘密情報の暗号化処理による暗号文生成に際し、ハッシュ関数を適用し、暗号文のビット長変更処理を実行する構成であることを特徴とする。
【００３６】
さらに、本発明の第２の側面は、
暗号データ生成処理を実行する情報処理装置であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された公開ノードキーＰｕｂＮＫｋを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する構成を有し、
前記送信秘密情報の暗号化に適用する公開ノードキーは、前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された秘密ノードキーに対応して設定された公開ノードキーであることを特徴とする情報処理装置にある。
【００３７】
さらに、本発明の情報処理装置の一実施態様において、前記送信秘密情報の暗号化に適用する公開ノードキーＰｕｂＮＫｋは、
ＰｕｂＮＫｋ＝ｇＰｒｉＮＫｋｍｏｄｑ
ただし、ｑは大きな素数、ｇは巡回群Ｚｑの生成元、
によって算出される公開ノードキーであることを特徴とする。
【００３８】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、公開ノードキーＰｕｂＮＫｋを適用した送信秘密情報Ｉの暗号化処理による暗号文ＣＴｋの生成を、
【数１４】
2004320183.tif 000004
ただし、ｘは、区間［１，ｑ−１］からランダムに選択した値、
によって実行する構成であることを特徴とする。
【００３９】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、前記送信秘密情報の暗号化に適用する選択した各公開ノードキーを用いて秘密情報を暗号化した暗号文セットを生成するとともに、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用した公開ノードキーとの対応を示す表現コードを生成し、前記暗号文セットおよび前記表現コードとをデバイスに対して送信する処理を実行する構成であることを特徴とする。
【００４０】
さらに、本発明の情報処理装置の一実施態様において、前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用した公開ノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする。
【００４１】
さらに、本発明の情報処理装置の一実施態様において、前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする。
【００４２】
さらに、本発明の情報処理装置の一実施態様において、前記送信秘密情報の暗号化に適用する公開ノードキーの選択処理は、前記階層型木構造の最下位ノードに対応するデバイス中、前記選択された限定デバイス以外の排除デバイスに対応する前記階層型木構造の葉からルートにいたるパス上のノード以外のノードによって構成される部分木の頂点ノードに対応する公開ノードキー選択処理として実行する構成であることを特徴とする。
【００４３】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする。
【００４４】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする。
【００４５】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数１５】
2004320183.tif 000005
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする。
【００４６】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、公開ノードキーＰｕｂＮＫｋを適用した送信秘密情報の暗号化処理による暗号文生成に際し、ハッシュ関数を適用し、暗号文のビット長変更処理を実行する構成であることを特徴とする。
【００４７】
さらに、本発明の第３の側面は、
暗号データ復号処理を実行する情報処理装置であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した暗号データの復号処理を実行する構成を有し、
前記ａ分木構成を持つ階層型木構造のノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定された構成であり、
前記情報処理装置は、
情報処理装置対応ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用するノードキーの算出処理を実行する構成を有することを特徴とする情報処理装置にある。
【００４８】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、複数のノードキーを用いて秘密情報を暗号化した複数の暗号文から構成される暗号文セット中から、前記情報処理装置対応ノードキーに基づいて算出可能なノードキーを適用して復号可能な暗号文の検出処理を実行する構成を有し、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用したノードキーとの対応を示す表現コードに基づいて前記検出処理を実行する構成であることを特徴とする。
【００４９】
さらに、本発明の情報処理装置の一実施態様において、前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用したノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする。
【００５０】
さらに、本発明の情報処理装置の一実施態様において、前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応するノードキーＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする。
【００５１】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする。
【００５２】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする。
【００５３】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数１６】
2004320183.tif 000006
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする。
【００５４】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、秘密ノードキーＰｒｉＮＫｋを適用した送信秘密情報の復号処理に際し、ハッシュ関数を適用し、復号に適用する鍵のビット長変更処理を実行する構成であることを特徴とする。
【００５５】
さらに、本発明の第４の側面は、
暗号データ復号処理を実行する情報処理装置であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された秘密ノードキーを選択的に適用して、前記秘密ノードキーに対応する公開ノードキーによって暗号化された暗号データの復号処理を実行する構成を有し、
前記ａ分木構成を持つ階層型木構造の各ノードに対応する秘密ノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された構成であり、
前記情報処理装置は、
情報処理装置対応秘密ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用する秘密ノードキーの算出処理を実行する構成を有することを特徴とする情報処理装置にある。
【００５６】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、秘密ノードキーＰｒｉＮＫｋを適用した暗号文ＣＴｋの復号による秘密情報Ｉの取得を、
【数１７】
2004320183.tif 000007
ただし、ｇｘｍｏｄｑは、既知の値、
によって実行する構成であることを特徴とする。
【００５７】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、前記ａ分木構成における複数の異なるノードの公開ノードキーを用いて秘密情報を暗号化した複数の暗号文から構成される暗号文セット中から、前記情報処理装置対応秘密ノードキーに基づいて算出可能な秘密ノードキーを適用して復号可能な暗号文の検出処理を実行する構成を有し、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用した公開ノードキーとの対応を示す表現コードに基づいて前記検出処理を実行する構成であることを特徴とする。
【００５８】
さらに、本発明の情報処理装置の一実施態様において、前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用した公開ノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする。
【００５９】
さらに、本発明の情報処理装置の一実施態様において、前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする。
【００６０】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする。
【００６１】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする。
【００６２】
さらに、本発明の情報処理装置の一実施態様において、前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数１８】
2004320183.tif 000008
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする。
【００６３】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、秘密ノードキーＰｒｉＮＫｋを適用した秘密情報の復号処理に際し、ハッシュ関数を適用する構成であることを特徴とする。
【００６４】
さらに、本発明の第５の側面は、
暗号データ生成処理を実行する情報処理方法であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する暗号処理ステップを有し、
前記暗号処理に適用するノードキーは、前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定されたノードキーであることを特徴とする情報処理方法にある。
【００６５】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、さらに、前記送信秘密情報の暗号化に適用する選択した各ノードキーを用いて秘密情報を暗号化した暗号文セットを生成するとともに、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用したノードキーとの対応を示す表現コードを生成し、前記暗号文セットおよび前記表現コードとをデバイスに対して送信する処理を実行するステップを有することを特徴とする。
【００６６】
さらに、本発明の情報処理方法の一実施態様において、前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用したノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする。
【００６７】
さらに、本発明の情報処理方法の一実施態様において、前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応するノードキーＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする。
【００６８】
さらに、本発明の情報処理方法の一実施態様において、前記送信秘密情報の暗号化に適用するノードキーの選択処理は、前記階層型木構造の最下位ノードに対応するデバイス中、前記選択された限定デバイス以外の排除デバイスに対応する前記階層型木構造の葉からルートにいたるパス上のノード以外のノードによって構成される部分木の頂点ノードに対応するノードキー選択処理として実行することを特徴とする。
【００６９】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする。
【００７０】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする。
【００７１】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数１９】
2004320183.tif 000009
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、であることを特徴とする。
【００７２】
さらに、本発明の情報処理方法の一実施態様において、前記暗号処理ステップは、ノードキーＮＫｋを適用した送信秘密情報の暗号化処理による暗号文生成に際し、ハッシュ関数を適用し、暗号文のビット長変更処理を実行することを特徴とする。
【００７３】
さらに、本発明の第６の側面は、
暗号データ生成処理を実行する情報処理方法であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された公開ノードキーＰｕｂＮＫｋを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する暗号処理ステップを有し、
前記暗号処理に適用する公開ノードキーは、前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された秘密ノードキーに対応して設定された公開ノードキーであることを特徴とする情報処理方法にある。
【００７４】
さらに、本発明の情報処理方法の一実施態様において、前記送信秘密情報の暗号化に適用する公開ノードキーＰｕｂＮＫｋは、
ＰｕｂＮＫｋ＝ｇＰｒｉＮＫｋｍｏｄｑ
ただし、ｑは大きな素数、ｇは巡回群Ｚｑの生成元、
によって算出される公開ノードキーであることを特徴とする。
【００７５】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、公開ノードキーＰｕｂＮＫｋを適用した送信秘密情報Ｉの暗号化処理による暗号文ＣＴｋの生成を、
【数２０】
2004320183.tif 000010
ただし、ｘは、区間［１，ｑ−１］からランダムに選択した値、
によって実行する構成であることを特徴とする。
【００７６】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、さらに、前記送信秘密情報の暗号化に適用する選択した各公開ノードキーを用いて秘密情報を暗号化した暗号文セットを生成するとともに、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用した公開ノードキーとの対応を示す表現コードを生成し、前記暗号文セットおよび前記表現コードとをデバイスに対して送信する処理を実行するステップを有することを特徴とする。
【００７７】
さらに、本発明の情報処理方法の一実施態様において、前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用した公開ノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする。
【００７８】
さらに、本発明の情報処理方法の一実施態様において、前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする。
【００７９】
さらに、本発明の情報処理方法の一実施態様において、前記送信秘密情報の暗号化に適用する公開ノードキーの選択処理は、前記階層型木構造の最下位ノードに対応するデバイス中、前記選択された限定デバイス以外の排除デバイスに対応する前記階層型木構造の葉からルートにいたるパス上のノード以外のノードによって構成される部分木の頂点ノードに対応する公開ノードキー選択処理として実行することを特徴とする。
【００８０】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする。
【００８１】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする。
【００８２】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数２１】
2004320183.tif 000011
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする。
【００８３】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、さらに、公開ノードキーＰｕｂＮＫｋを適用した送信秘密情報の暗号化処理による暗号文生成に際し、ハッシュ関数を適用し、暗号文のビット長変更処理を実行する構成であることを特徴とする。
【００８４】
さらに、本発明の第７の側面は、
暗号データ復号処理を実行する情報処理方法であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した暗号データの復号処理を実行する復号処理ステップを有し、
前記ａ分木構成を持つ階層型木構造のノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定された構成であり、
前記情報処理方法は、
情報処理装置対応ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用するノードキーの算出処理を実行するステップを有することを特徴とする情報処理方法にある。
【００８５】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、さらに、複数のノードキーを用いて秘密情報を暗号化した複数の暗号文から構成される暗号文セット中から、前記情報処理装置対応ノードキーに基づいて算出可能なノードキーを適用して復号可能な暗号文の検出処理を実行するステップを有し、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用したノードキーとの対応を示す表現コードに基づいて前記検出処理を実行することを特徴とする。
【００８６】
さらに、本発明の情報処理方法の一実施態様において、前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用したノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする。
【００８７】
さらに、本発明の情報処理方法の一実施態様において、前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応するノードキーＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする。
【００８８】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする。
【００８９】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする。
【００９０】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数２２】
2004320183.tif 000012
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする。
【００９１】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、さらに、ノードキーＮＫｋを適用した送信秘密情報の復号処理に際し、ハッシュ関数を適用し、復号に適用する鍵のビット長変更処理を実行することを特徴とする。
【００９２】
さらに、本発明の第８の側面は、
暗号データ復号処理を実行する情報処理方法であり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された秘密ノードキーを選択的に適用して、前記秘密ノードキーに対応する公開ノードキーによって暗号化された暗号データの復号処理を実行する復号処理ステップを有し、
前記ａ分木構成を持つ階層型木構造の各ノードに対応する秘密ノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された構成であり、
前記情報処理方法は、
情報処理装置対応秘密ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用する秘密ノードキーの算出処理を実行するステップを有することを特徴とする情報処理方法にある。
【００９３】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、秘密ノードキーＰｒｉＮＫｋを適用した暗号文ＣＴｋの復号による秘密情報Ｉの取得を、
【数２３】
2004320183.tif 000013
ただし、ｇｘｍｏｄｑは、既知の値、
によって実行することを特徴とする。
【００９４】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、前記ａ分木構成における複数の異なるノードの公開ノードキーを用いて秘密情報を暗号化した複数の暗号文から構成される暗号文セット中から、前記情報処理装置対応秘密ノードキーに基づいて算出可能な秘密ノードキーを適用して復号可能な暗号文の検出処理を実行するステップを有し、前記暗号文セットを構成する各暗号文と、該暗号文生成に適用した公開ノードキーとの対応を示す表現コードに基づいて前記検出処理を実行することを特徴とする。
【００９５】
さらに、本発明の情報処理方法の一実施態様において、前記表現コードは、前記ａ分木の最上位ノードであるルートと暗号文生成に適用した公開ノードキーに対応するノードまでのａ分木のパスを結んだ表現木構成を示すコードデータであることを特徴とする。
【００９６】
さらに、本発明の情報処理方法の一実施態様において、前記ａ分木構成を持つ階層型木構造において、最上位ノードであるルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１は、落とし戸つき一方向置換Ｆｉの定義域の中からの選択値Ｓとして設定された値であることを特徴とする。
【００９７】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、ＲＳＡ関数に基づくことを特徴とする。
【００９８】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉは、異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくなる確率の低い置換を構成する落とし戸つき一方向置換であることを特徴とする。
【００９９】
さらに、本発明の情報処理方法の一実施態様において、前記落とし戸つき一方向置換Ｆｉ、および逆置換Ｆ−１ｉは、
【数２４】
2004320183.tif 000014
ただし、Ｍは、２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数であり、ｅｉ、ｄｉは、ｉが異なるときに異なる値として設定される値、ｃｉはｉが異なるとき、異なる整数となるように設定される値、
であることを特徴とする。
【０１００】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、秘密ノードキーＰｒｉＮＫｋを適用した秘密情報の復号処理に際し、ハッシュ関数を適用する構成であることを特徴とする。
【０１０１】
さらに、本発明の第９の側面は、
暗号データ生成処理を実行するコンピュータ・プログラムであり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する暗号処理ステップを有し、
前記暗号処理に適用するノードキーは、前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定されたノードキーであることを特徴とするコンピュータ・プログラムにある。
【０１０２】
さらに、本発明の第１０の側面は、
暗号データ生成処理を実行するコンピュータ・プログラムであり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された公開ノードキーＰｕｂＮＫｋを選択的に適用した送信秘密情報の暗号化により、前記階層型木構造の最下位ノードに対応するデバイス中、選択された限定デバイスのみが復号可能な暗号データを生成する処理を実行する暗号処理ステップを有し、
前記暗号処理に適用する公開ノードキーは、前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された秘密ノードキーに対応して設定された公開ノードキーであることを特徴とするコンピュータ・プログラムにある。
【０１０３】
さらに、本発明の第１１の側面は、
暗号データ復号処理を実行するコンピュータ・プログラムであり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定されたノードキーを選択的に適用した暗号データの復号処理を実行する復号処理ステップを有し、
前記ａ分木構成を持つ階層型木構造のノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応するノードキーがＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードのノードキーが、前記ノードキーＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＮＫｋ）〜Ｆ−１ａ（ＮＫｋ）として設定された構成であり、
前記コンピュータ・プログラムは、
情報処理装置対応ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用するノードキーの算出処理を実行するステップを有することを特徴とするコンピュータ・プログラムにある。
【０１０４】
さらに、本発明の第１２の側面は、
暗号データ復号処理を実行するコンピュータ・プログラムであり、
上位ノードに対応してａ個の子ノードを持つａ分木構成を持つ階層型木構造（ＨＫＴ：Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ）を構成する各ノードに対して設定された秘密ノードキーを選択的に適用して、前記秘密ノードキーに対応する公開ノードキーによって暗号化された暗号データの復号処理を実行する復号処理ステップを有し、
前記ａ分木構成を持つ階層型木構造の各ノードに対応する秘密ノードキーの設定構成は、
前記階層型木構造における上位ノードｖｋに対応する秘密ノードキーがＰｒｉＮＫｋであるとき、該ノードｖｋに対応するａ個の子ノードの秘密ノードキーが、前記秘密ノードキーＰｒｉＮＫｋに対して、落とし戸つき一方向置換Ｆｉ（ただし、ｉ＝１〜ａ）の逆置換Ｆ−１ｉを適用して算出されるａ個の値Ｆ−１１（ＰｒｉＮＫｋ）〜Ｆ−１ａ（ＰｒｉＮＫｋ）として設定された構成であり、
前記情報処理方法は、
情報処理装置対応秘密ノードキーに基づいて、前記落とし戸つき一方向置換Ｆｉを実行し、前記暗号データの復号処理に適用する秘密ノードキーの算出処理を実行するステップを有することを特徴とするコンピュータ・プログラムにある。
【０１０５】
【作用】
本発明の構成に従えば、階層型木構造を適用した暗号鍵等の暗号データ提供処理において、リーフの保持する鍵の数を１つのみとすることが可能となり、その保持する鍵に基づいてルートから自己の属するリーフまでのパス上の各ノードに対応するノードキーの算出を効率的に行い、暗号文の復号処理を少ない保持鍵に基づいて効率的に実行することが可能となる。具体的には、各デバイスは高々ｌｏｇａＮ回、すなわち最大でも木の高さの回数だけ一方向置換を実行すれば、自分が与えられた葉に対応するノードキーから、その葉からルートまでのパス上に存在する任意のノードキーを導出することが可能となる。
【０１０６】
さらに、本実施例の構成に従えば、階層型木構造を適用した暗号データ提供処理において、ａ分木（ＨＫＴ）における各ノードキーの算出処理および設定処理に落とし戸つき一方向置換Ｆｉと、逆置換Ｆ−１ｉを適用し、各デバイスにおけるノードキーの算出において、最大でも木の高さの回数だけの一方向置換Ｆｉを実行すればノードキー算出を完了する構成としたので、各デバイスにおける暗号文の復号プロセスにおける処理負荷が軽減される。
【０１０７】
さらに、本実施例の構成に従えば、リボークデバイスの排除処理に基づいて構成される部分木の頂点ノードを選択し、頂点ノードに基づいて構成される表現木を設定し、表現木の葉、すなわち部分木の頂点ノードに対応するノードキーを用いて送信する秘密情報（Ｉ）を暗号化して生成した暗号文を送信することで、部分木のルートとなるノードに対応するノードキーを導出することができるリボークされていないデバイスのみが、自己において導出可能なノードキーを用いた暗号文の復号により秘密情報の取得が可能となり、限定ユーザを特定した暗号化データの配信が可能となる。
【０１０８】
さらに、本発明の構成によれば、信頼性の必ずしも保証されない任意のエンティテイが、信頼センタの公開するノード対応の公開ノードキー情報を取得して、公開ノードキーを用いた秘密情報の暗号化処理を実行することで、秘密情報（Ｉ）を特定のリボークされないデバイスにのみ選択的に送信することが可能となり、本構成においても、それぞれのデバイスは高々ｌｏｇａＮ回、すなわち最大でも木の高さの回数だけ一方向置換を実行すれば、自分が与えられた葉に対応する秘密ノードキーから、その葉からルートまでのパス上に存在する任意の秘密ノードキーを導出することが可能となり、導出した秘密ノードキーを用いて暗号文を復号することによって秘密情報を取得することが可能となる。
【０１０９】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記憶媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【０１１０】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【０１１１】
【発明の実施の形態】
以下、本発明の情報処理装置、および情報処理方法、並びにコンピュータ・プログラムについて詳細に説明する。
【０１１２】
本発明は、木構造（ツリー構造）を用いた鍵配信方式において、用いる木構造の１つのノード（節点）に対する子ノードの数をａとして設定したａ分岐構造の木構造（ツリー構造）を用いた鍵配信方式において、ａ個の落とし戸つき一方向置換を用いることにより、リーフに設定されるデバイスが保管すべき鍵の数を１個として、デバイスが必要とする計算量を最大ｌｏｇａＮ回の落とし戸つき一方向置換の実行の計算量に抑えることを可能としたものである。ただし、Ｎは、木構造（ツリー構造）を用いた鍵配信方式において鍵配信処理対象となる全デバイス数である。以下、本発明の実施例について説明する。
【０１１３】
なお、以下に説明する実施例では、木構造（ツリー構造）を用いた鍵配信方式において適用する木構造を１つのノード（節点）に対する子ノードの数をａとして設定したａ分木構造とし、木構造（ツリー構造）のリーフとしての全デバイス数をＮとする。ただしａ，Ｎは２以上の自然数である。ここでは、簡単のため、デバイス数Ｎを正整数ａのべき乗の数とする。
【０１１４】
実施例では、ａ分木（Ｈｉｅｒａｒｃｈｉｃａｌ  Ｋｅｙ  Ｔｒｅｅ：ＨＫＴと呼ぶ）構造において、例えば暗号鍵等の秘密情報（Ｉ）を暗号化した暗号文を受信し、暗号文の復号により、秘密情報（Ｉ）を取得するユーザデバイス、例えば各ユーザの受信機はＨＫＴのリーフにそれぞれ割り当てられる。また、木構造（ツリー構造）を用いた暗号データ配信システムの管理者を信頼できるものとし、信頼センタ（Ｔｒｕｓｔｅｄ  Ｃｅｎｔｅｒ：ＴＣ）とする。
【０１１５】
［実施例１：基本方式］
実施例１では信頼センタＴＣが、暗号化鍵情報、暗号化データ等、各種の秘密情報（Ｉ）の送信者となる例を説明する。以下、処理手順に従って、次の（１）〜（３）の処理フェーズ、すなわち、
（１）秘密情報（Ｉ）の送信を行うための木構造を形成する各ノードに対するノードキーの割り当て等の処理を実行するセットアップ処理。
（２）セットアップ後の木構造を用いた暗号化秘密情報の送信処理。
（３）木構造のリーフに設定されたデバイスにおける暗号化秘密情報の受信および復号処理。
の３つの処理について、順次説明する。
【０１１６】
（１）セットアップ処理
信頼センタＴＣは、図４に示すような各ノードにａ個の子ノードまたはリーフを持つａ分木構造を持ち、デバイスを設定するリーフとしてのＮ個の葉を持つａ分木（ＨＫＴ）を定義し、その構成を公開する。図４に示すａ分木（ＨＫＴ）の最上位ノードであるルート１０１をルートｖ１とし、それ以降は幅方向優先の順番で各ノードに番号付けをし、各ノードをｖ１，ｖ２，ｖ３，ｖ４，・・とする。図４に示すａ分木（ＨＫＴ）は、ａ＝３、Ｎ＝２７の場合のａ分木（ＨＫＴ）である。
【０１１７】
Ｎ個の受信機等のデバイスをａ分木（ＨＫＴ）のそれぞれ異なる葉に割り当て、この割り当てを公開する。デバイスは、信頼センタから暗号鍵情報等の暗号化秘密情報を受信し、復号して利用するデバイスである。ａ分木（ＨＫＴ）のそれぞれ異なる葉に割り当てたデバイスをｕ１，ｕ２，ｕ３，ｕ４，・・ｕ２７とする。
【０１１８】
さらに、信頼センタＴＣは、ａ分木（ＨＫＴ）のそれぞれ異なるノードに設定するノードキーを生成するために適用するａ個の落とし戸つき一方向置換Ｆ１…Ｆａを作成し公開する。なお、以下の説明においては、ａ分木（ＨＫＴ）のルートからデバイスの設定された葉に至るまでの全てのルート、ノード、リーフ（葉）の全体を含めてノードと総称し、ルート、ノード、リーフ（葉）に割り当てるキーをノードキーと総称して説明する。
【０１１９】
信頼センタＴＣが、ノードキーを生成するために適用する落とし戸つき一方向置換Ｆｉ（）とは、入力ｘが与えられたときにｙ＝Ｆｉ（ｘ）を計算するのは容易であるが、ｙが与えられたときにｙ＝Ｆｉ（ｘ）を満たすようなｘを見つけること（すなわち逆置換Ｆ−１ｉ（ｙ）を行うこと）はＦｉ（）を作成したときに用いた秘密を知るものだけが容易に行え、秘密を知らないものはｘを見つけることが計算量的に困難であるような置換である。
【０１２０】
本発明で適用可能な落とし戸つき一方向置換の具体例について説明する。一般に、落とし戸つき一方向置換としてよく知られているものに、ＲＳＡ関数が挙げられる。落とし戸つき一方向置換としてのＲＳＡ関数の解説は、たとえばＯ．Ｇｏｌｄｒｅｉｃｈ著、岡本龍明、藤崎英一郎訳、「現代暗号・確率的証明・擬似乱数」、シュプリンガー・フェアラーク、２００１年、ｐｐ．１６８−１６９に記されている。
【０１２１】
落とし戸つき一方向置換としてのＲＳＡ関数を用いて、落とし戸つき一方向置換Ｆｉとその逆置換Ｆ−１ｉを下記のように定めることができる。
【０１２２】
【数２５】
2004320183.tif 000015
【０１２３】
上記式において、Ｍは２つの大きな素数ｐ、ｑの積であり、ｅｉは（ｐ−１）（ｑ−１）と互いに素になるような整数、ｄｉは（ｐ−１）（ｑ−１）を法としたときのｅｉの逆数である。ｅｉ、ｄｉは、ｉが異なるときに異なる値となるように設定される。つまり、ｉとｊが等しくないとき、ｅｉとｅｊが、またｄｉとｄｊが等しくならないように設定する。
【０１２４】
またｃｉはｉが異なるとき、異なる整数となるように設定される。つまり、ｉとｊが等しくないとき、ｃｉとｃｊが等しくならない整数である。ここで、ｐ，ｑとｄｉは信頼センタＴＣが秘密に保管し、Ｆｉを実現するのに必要なＭとｅｉとｃｉは全デバイスに公開する。
【０１２５】
このようにすることにより、各置換の定義域および値域がすべて等しく、また異なるｉ，ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくならない置換、あるいは、等しくなる確率が無視できるほど小さい置換を構成することが可能である。
【０１２６】
また、一例として、デバイスのプログラムコードサイズを減少させるために、ｅｉとｃｉを独立に選ぶのではなく、たとえばｅｉはある値（たとえば２１６＝６５５３６）を超える、ｉ番目の奇数とする、ｃｉはｃｉ＝ｉとする、など、規則性を持たせる設定としてもよい。
【０１２７】
逆置換Ｆ−１１…Ｆ−１ａは信頼センタＴＣが秘密に保管する。ただし、本実施例においてはＦ１…Ｆａはすべて定義域および値域がすべて等しく、また異なるｉ、ｊについてＦｉ（Ｆｊ（ｘ））とＦｊ（Ｆｉ（ｘ））が等しくならない（あるいは、等しくなる確率が無視できるほど小さい）置換である。
【０１２８】
次に信頼センタＴＣはルートｖ１に対応するノードキーＮＫ１を、置換Ｆｉ（）の定義域の中からランダムに選択する。そして、それ以外のノードｖｋに対応するノードキーＮＫｋを、下記の手順で再帰的に生成する。
【０１２９】
すなわち、あるノードｖｋに対応するノードキーをＮＫｋとするとき、ｖｋの子ノードのうち、左端の子ノードのノードキーをＦ−１１（ＮＫｋ）とし、左からｉ番目の子ノードのノードキーをＦ−１ｉ（ＮＫｋ）とし、右端のもののノードキーをＦ−１ａ（ＮＫｋ）とする。信頼センタＴＣはこの手法を用いて、まずルートの子ノードのノードキーを作り、さらにそれらのノードの子ノードのノードキーを作る、というようにしてａ分木（ＨＫＴ）のすべてのノード（葉も含む）に対応するノードキーを作成する。
【０１３０】
図５に、ルートｖ１１０１のノードキーをＳと置いたときの各ノードのノードキーの設定例を示す。図４、図５において、ノードＶ２１０２のノードキーＮＫ２はＦ−１１（Ｓ）であり、ノードＶ１１１０３のノードキーＮＫ１１はＦ−１１（Ｆ−１３（Ｓ））であり、ノードＶ２３１０４のノードキーＮＫ２３はＦ−１１（Ｆ−１１（Ｆ−１２（Ｓ）））である。これらの各ノードキーは、すべてルートに設定したノードキーＳから逆置換Ｆ−１ｉを用いて算出される。
【０１３１】
信頼センタＴＣは、ａ分木（ＨＫＴ）中の葉に対応するノードキーを、その葉に割り当てられたデバイスに秘密裏に与える。
【０１３２】
図４、図５において、葉であるノードＶ１４１０５のノードキーＮＫ１４、すなわち値としてはＦ−１１（Ｆ−１１（Ｆ−１１（Ｓ）））がその葉に割り当てられたデバイスｕ１に与えられ、葉であるノードＶ２３１０４のノードキーＮＫ２３、すなわち値としてはＦ−１１（Ｆ−１１（Ｆ−１２（Ｓ）））がその葉に割り当てられたデバイスｕ１０に与えられる。
【０１３３】
これらの葉に割り当てられたデバイスに与えられるノードキーは、たとえばデバイスの製造時にデバイスに格納される。デバイスはそれを外部に漏らさないように秘密に格納する。
【０１３４】
上述した木構造におけるルートからリーフに至る全ノードに対するノードキーの設定により、セットアップ処理が終了する。このセットアップ処理は、システム運用開始時に一度だけ行えばよく、その後は以下の秘密情報の送信を繰り返し行うことができる。
【０１３５】
（２）秘密情報の送信
次に、信頼センタＴＣが秘密情報を、選択したデバイスにのみ提供する方法について説明する。まず、信頼センタＴＣは秘密情報の取得を認めないデバイス、すなわちａ分木（ＨＫＴ）のそれぞれ異なる葉に割り当てたデバイスｕ１，ｕ２，ｕ３，ｕ４，・・ｕ２７から秘密情報の取得を認めないデバイス（排除（リボーク）デバイス）を決定する。以下、秘密情報の取得を認めないデバイスをリボークデバイスと呼ぶ。リボークデバイス以外のデバイスは、信頼センタＴＣが送信する秘密情報を取得可能な限定された正規デバイスである。
【０１３６】
図６において、リボークデバイスをＸ印で表す。図６の例ではデバイスｕ２、ｕ１３、ｕ１４、ｕ２２、ｕ２３、ｕ２４、ｕ２７がリボークデバイスである。
【０１３７】
信頼センタＴＣは、これら排除されるデバイスに割り当てられた葉からルートにいたるまでのパス上のすべてのノードを選択する。図６では黒丸でマークされたノードが選択ノードである。
【０１３８】
黒丸でマークされた選択ノードに対応するノードキーは、後述のように排除されたデバイスが持つノードキーから導出することができるので、これらのノードキーは使用することができない。
【０１３９】
黒丸でマークされなかったノードに注目すると、これらは１つ以上の部分木を構成している。例えば部分木２０１は、頂点ノードｖ６をルートとし、３つの葉ｖ１７、ｖ１８、ｖ１９を子ノードとした部分木２０１である。部分木２０２のように、ノードが１つ（ｖ２８）のものもあるが、これも部分木として考える。信頼センタＴＣはこれらの部分木のルートとなるノード、すなわち頂点ノードに対応するノードキーを用いて送信する秘密情報（Ｉ）を暗号化して生成した暗号文を同報通信路を用いて送信する。
【０１４０】
黒丸でマークされた選択ノードに対応するノードキーは、リボークデバイスが持つノードキーから導出することができるノードキーであり、これらのノードキーを使用しない暗号文をデバイスに送信することで、リボークデバイス（×印）は、自己において導出可能なノードキーを用いた暗号文の復号により秘密情報の取得ができないことになる。
【０１４１】
部分木のルートとなるノード、すなわち頂点ノードに対応するノードキーを用いて送信する秘密情報（Ｉ）を暗号化した暗号文のセットを同報通信路を用いて送信することで、部分木のルートとなるノードに対応するノードキーを導出することができるリボークされていないデバイスのみが、暗号文セットから、自己において導出可能なノードキーを用いて暗号化された暗号文を選択し、選択暗号文を自己において導出可能なノードキーを用いて復号することにより秘密情報の取得が可能となる。
【０１４２】
図６の例では、部分木のルートとなっているのは図６において四角マークで示したｖ６、ｖ７、ｖ８、ｖ１０、ｖ１１、ｖ１４、ｖ１６、ｖ２８、ｖ３８、ｖ３９であり、それぞれのノードに対応するノードキーを用いて、秘密情報（Ｉ）を暗号化して送信する。すなわち、秘密情報（Ｉ）を複数のノードキーでそれぞれ暗号化した複数の暗号文のセットが生成されて、送信される。
【０１４３】
暗号化のひとつの手法としては、たとえばＦＩＰＳ１９７で定められた米国暗号標準であるＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）など安全と考えられる既存の暗号化アルゴリズムを用いることができる。この場合、ＡＥＳの鍵サイズのひとつである１２８ビット長のブロック暗号化処理を適用するために、ノードキーを１２８ビットの値を出力するハッシュ関数に入力し、その出力を鍵としてＡＥＳアルゴリズムを用いて秘密情報（Ｉ）を暗号化するのが具体的構成の一例である。ＡＥＳアルゴリズムについては、例えば、ｈｔｔｐ：／／ｃｓｒｃ．ｎｉｓｔ．ｇｏｖ／ＣｒｙｐｔｏＴｏｏｌｋｉｔ／ａｅｓ／に詳細が記述されている。
【０１４４】
１２８ビットの値を出力するハッシュ関数としては、ハッシュ関数として知られたＭＤ５を適用することが可能である。ＭＤ５についての詳細は、例えば「１９９７年，ＣＲＣ  プレス社，Ａ．  Ｊ．  Ｍｅｎｅｚｅｓ，  Ｐ．  Ｃ．  ｖａｎ  Ｏｏｒｓｃｈｏｔ，  Ｓ．  Ａ．  Ｖａｎｓｔｏｎｅ  著，「Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」  ｐ．  ３４７」に記述されている。
【０１４５】
暗号文とそれを暗号化するのに用いられたノードキーとの対応を明示するためには、たとえば表現木を用いる。表現木は、ａ分木（ＨＫＴ）の最上位ノードであるルートと、そこから暗号文を作るのに用いられたノードキーに対応するノードまでのａ分木（ＨＫＴ）のパスを結んだものである。
【０１４６】
図７に、本実施例における表現木を示す。全体の木（ａ分木（ＨＫＴ））に対して、太線で表されている部分木が表現木となる。
【０１４７】
図６に示したように、暗号化に用いられるノードキーに対応するノードはｖ６、ｖ７、ｖ８、ｖ１０、ｖ１１、ｖ１４、ｖ１６、ｖ２８、ｖ３８、ｖ３９であり、これらのノードからルートまでのａ分木（ＨＫＴ）のパスを集めたものが表現木になる。
【０１４８】
表現木の各ノードは、もとのａ分木（ＨＫＴ）のノードの子ノードの数ａに対応するａビットの情報を持つ。ａビット中のそれぞれのビットは、対応する子ノードが表現木中に存在するか、否かを表す。存在する場合は１、存在しない場合は０とする。
【０１４９】
図７の例においては、表現木のルートｖ１の横に（１、１、１）が書かれているが、これはｖ１の子ノードｖ２、ｖ３、ｖ４がいずれも表現木中に存在することを表している。これに対して、ノードｖ５の横に示す値は（１、０、１）である。これは、ａ分木（ＨＫＴ）におけるこのノードｖ５の子ノードｖ１４、ｖ１５、ｖ１６のうち、左端のノードｖ１４と右端のノードｖ１６は表現木中に存在するが、中央のノードｖ１５は表現木中に存在しないことを表している。暗号文を作成するのに使われたノードキーに対応するノードが表現木の葉になっている場合、葉に対する子ノードは存在しないので、値としてすべて０、すなわち（０、０、０）を持つ。表現木の構造を表すのには、表現コードを用いる。
【０１５０】
表現コードは、表現木に含まれるすべてのノードの値を、ルートから幅優先順序で並べたものである。図７の例では、表現木に含まれるノードはｖ１、ｖ２、ｖ３、ｖ４、ｖ５、ｖ６、ｖ７、ｖ８、ｖ９、ｖ１０、ｖ１１、ｖ１３、ｖ１４、ｖ１６、ｖ２８、ｖ３８、ｖ３９であり、それぞれのノードは（１、１、１）、（１、１、１）、（１、１、１）、（１、０、１）、（１、０、１）、（０、０、０）、（０、０、０）、（０、０、０）、（０、０、１）、（０、０、０）、（０、０、０）、（１、１、０）、（０、０、０）、（０、０、０）、（０、０、０）、（０、０、０）、（０、０、０）の値を持つ。
【０１５１】
これらの値をシーケンシャルに並べたａビットのビット列、［１１１１１１１１１１０１１０１０００００００００００１００００００１１００００００００００００００００］が表現コードとなる。
【０１５２】
信頼センタＴＣは表現コードを秘密情報（Ｉ）を含む暗号文の送信に先立って、あるいは、秘密情報（Ｉ）を含む暗号文と一緒に、同報通信路を用いて送信する。また、暗号文は、暗号化に用いられたノードキー毎に、秘密情報を暗号化した暗号文を複数持つ暗号文セットであり、その順番は、暗号化に用いられたノードキーに対応するノードの番号が小さい順に設定される。
【０１５３】
図６に示したように、暗号化に用いられるノードキーに対応するノードはｖ６、ｖ７、ｖ８、ｖ１０、ｖ１１、ｖ１４、ｖ１６、ｖ２８、ｖ３８、ｖ３９であり、これらのノードに対応するノードキーによって秘密情報（Ｉ）が暗号化されて暗号文が生成された場合、ノードｖｎ、の対応ノードキーで秘密情報を暗号化した暗号文をＥｎｃ（ｖｎ，Ｉ）とした場合、デバイスに送信される暗号文は、
Ｅｎｃ（ｖ６，Ｉ），Ｅｎｃ（ｖ７，Ｉ），Ｅｎｃ（ｖ８，Ｉ），Ｅｎｃ（ｖ１０，Ｉ），Ｅｎｃ（ｖ１１，Ｉ），Ｅｎｃ（ｖ１４，Ｉ），Ｅｎｃ（ｖ１６，Ｉ），Ｅｎｃ（ｖ２８，Ｉ），Ｅｎｃ（ｖ３８，Ｉ），Ｅｎｃ（ｖ３９，Ｉ）
となる。
【０１５４】
この暗号文と、前述の表現コード［１１１１１１１１１１０１１０１０００００００００００１００００００１１００００００００００００００００］がデバイスに送信される。
【０１５５】
（３）受信、復号
次に、上述した表現コードと暗号文を受信したデバイスがどのようにして送信された秘密情報（Ｉ）を取得するかについて、説明する。
【０１５６】
まず、デバイスは、セットアップ処理において信頼センタの公開したａ分木（ＨＫＴ）の構成情報を用いて、受信した表現コードを表現木のノードに対応する値、すなわち（１、１、１）、（１、１、１）、（１、１、１）、（１、０、１）、（１、０、１）、（０、０、０）、（０、０、０）、（０、０、０）、（０、０、１）、（０、０、０）、（０、０、０）、（１、１、０）、（０、０、０）、（０、０、０）、（０、０、０）、（０、０、０）、（０、０、０）に分離する。
【０１５７】
デバイスは、これらの値に基づき、幅優先順の探索を行って表現木内における子ノードの有無を判定する。たとえば、最初の値（１、１、１）は、ルートｖ１に対応し、ルートの３つの子ノードｖ２、ｖ３、ｖ４すべてが表現木に存在することを示している。次の値（１、１、１）は、ノードｖ２に対応し、その３つの子ノードｖ５、ｖ６、ｖ７すべてが表現木に存在することを示している。
【０１５８】
デバイスは、ａ分木（ＨＫＴ）におけるデバイスのノードから根までのパス上のノードに対応する葉のノードを検出するまで、（例えば、幅優先順検索法を用いて）再構築された表現木を検索する（ここで、表現木のノードｖ１は、ａ分木（ＨＫＴ）のノードｖ１に対応する）。
【０１５９】
たとえば、図７において、デバイスｕ１３０１は、ノードｖ１４を、デバイスｕ３３０２はノードｖ１６を、デバイスｕ４、ｕ５、ｕ６３０３は、ノードｖ６を表現木の葉として認識する。ａ分木（ＨＫＴ）におけるデバイスのノードからルートまでのパス上のノードに対応する葉のノードが見付からない場合、デバイスは、自らが無効にされ、有効なノードキーを導出することができないと判断する。
【０１６０】
例えば、デバイスｕ２３１１は、無効（リボーク）にされており、したがって、デバイスｕ２３１１のノードから根までのパス上に葉を検出することができない。すなわち、デバイスｕ２３１１は、ノードｖ１５に対応し、ノードｖ１５からルート（ノードｖ１）までのパスには、ノードｖ１５、ｖ５、ｖ２、ｖ１が含まれるが、これらのノードｖ１５、ｖ５、ｖ２、ｖ１は、いずれも表現木の葉に対応していない。なお、デバイスは、例えば、ネットワーク接続を介して、管理センタと通信することにより、デバイスが無効にされたことを確認することができる。管理センタは、リボークされたデバイスのリスト、すなわちリボークリストを有し、ノードからの問い合わせに応答し、また信頼センタ（ＴＳ）に対してリボークリストに基づくリボーク情報を提供する。信頼センタ（ＴＳ）は、リボーク情報に基づいて上述した表現木を生成する。
【０１６１】
ａ分木（ＨＫＴ）において自身の葉からルートまでのパス上に、表現木の葉となるノードが存在した場合、デバイスは、信頼センタ（ＴＳ）から送信されてきた暗号文の中から、自デバイスにおいて処理すべき暗号文を選択する。
【０１６２】
信頼センタ（ＴＳ）は、暗号文を、一例として上述のルール、すなわち暗号化に用いられたノードキーに対応するノードの番号が小さい順に従ったシーケンスに並べて送信する。これにより、各デバイスが、自デバイスにおいて処理可能な暗号文をノードの番号と暗号文の送信される順番により求めることができる。
【０１６３】
デバイスは、選択した暗号文をそのノードに対応して設定されたノードキーを用いて復号する。この際、デバイスが与えられた鍵、すなわちデバイスが割り当てられたａ分木（ＨＫＴ）の葉に対応するノードキーから、その暗号文の暗号化に用いられたａ分木（ＨＫＴ）の葉、もしくは内部ノードのノードキーを下記のように導出する。
【０１６４】
もしａ分木（ＨＫＴ）においてデバイスが割り当てられた葉が表現木の葉と一致するときは、デバイスが与えられたノードキーを用いて暗号化がなされているので、直接これを用いて暗号文を復号する。
【０１６５】
もし表現木の葉が、ａ分木（ＨＫＴ）の内部ノードであるときは、デバイスはあらかじめ与えられたａ分木（ＨＫＴ）の葉のノードキーから内部ノードのノードキーを導出する。まず、ａ分木（ＨＫＴ）において、デバイスが割り当てられた葉がその親ノードの左から数えて何番目の子であるかを調べる。これをｉ番目とおくと、その与えられたノードキーＮＫｋに対して、公開されている一方向置換Ｆｉを適用した結果のＦｉ（ＮＫｋ）が親ノードのノードキーとなる。
【０１６６】
たとえば図７において、ノードｖ１８３０４は、その親ノードｖ６３０５の左から２番目の子ノードであるから、ノードｖ１８３０４に対応するデバイスｕ５３０６は、与えられたノードｖ１８３０４のノードキーＮＫ１８と、公開されている一方向置換Ｆ２を用いてノードｖ６３０５のノードキーＮＫ６＝Ｆ２（ＮＫ１８）を導出することができる。
【０１６７】
これは、図５において、ノードキーＮＫ６としてＦ−１２（Ｆ−１１（Ｓ））が定義され、デバイスｕ５が割り当てられた葉ｖ１８のノードキーＮＫ１８としてＦ−１２（Ｆ−１２（Ｆ−１１（Ｓ）））が定義されているので、Ｆ２（ＮＫ１８）＝Ｆ２（Ｆ−１２（Ｆ−１２（Ｆ−１１（Ｓ））））＝Ｆ−１２（Ｆ−１１（Ｓ））＝ＮＫ６となることからも確かめられる。
【０１６８】
もしデバイスがさらに上位のノードのノードキーを必要としていれば、デバイスはこの処理を繰り返すことでさらに上位のノードのノードキーを導出できる。すなわち、デバイスがこれまでに導出したノードキーＮＫｋに対応するノードがその親ノードの左からｉ番目の子ノードであるとき、親ノードのノードキーはＦｉ（ＮＫｋ）となる。デバイスは必要なノードキーを導出するまであるノードキーから親ノードのノードキーを導出する処理を繰り返す。たとえば、排除されるデバイスがひとつもないときは、ルートのノードキーが暗号化に用いられ、ただ１つの暗号文が送信される。この暗号文を復号するために、デバイスｕ８はルートのノードキーをＦ１（Ｆ３（Ｆ２（ＮＫ２１）））として求めることができる。
【０１６９】
先に述べた暗号化の例に准ずれば、必要なノードキーを導出したら、デバイスはそれをハッシュ関数に入力し、その出力をＡＥＳの鍵として暗号文の復号を行う。
【０１７０】
本実施例の構成を用いれば、それぞれのデバイスは高々ｌｏｇａＮ回、すなわち最大でも木の高さの回数だけ一方向置換を実行すれば、自分が与えられた葉に対応するノードキーから、その葉からルートまでのパス上に存在する任意のノードキーを導出することが可能となる。
【０１７１】
図８に、本実施例全体の流れと信頼センタＴＣおよびデバイスの処理を示す。
【０１７２】
処理は、上述した説明から明らかなように、
（１）セットアップ処理
（２）信頼センタによるリボークおよび暗号文送信
（３）デバイスによる暗号文受信、復号
の３フェーズによって構成される。
【０１７３】
（１）のセットアップ処理は１回、実行すればよく、セットアッサプされた後のリボーク処理、暗号文送信処理、暗号文受信および復号処理は繰り返し実行可能となる。
【０１７４】
セットアップ処理では信頼センタＴＣが、ステップＳ１０１において、以下の処理を実行する。
（ａ）ａ分木（ＨＫＴ）の生成、ａ分木（ＨＫＴ）構成情報の公開処理
（ｂ）落とし戸つき一方向置換Ｆｉとその逆置換Ｆ−１ｉを設定し、一方向置換Ｆｉを公開する処理
【０１７５】
（ｃ）ルートｖ１に対応するノードキーＮＫ１を、置換Ｆｉ（）の定義域の中からランダムに選択し、ａ分木（ＨＫＴ）のルートｖ１以外のノードｖｋに対応するノードキーＮＫｋを、下記の手順で再帰的に生成する処理。すなわち、あるノードｖｋに対応するノードキーをＮＫｋとするとき、ｖｋの子ノードのうち、左端のもののノードキーをＦ−１１（ＮＫｋ）とし、左からｉ番目の子ノードのノードキーをＦ−１ｉ（ＮＫｋ）とし、右端のもののノードキーをＦ−１ａ（ＮＫｋ）とする。信頼センタＴＣはこの手法を用いて、まずルートの子ノードのノードキーを作り、さらにそれらのノードの子ノードのノードキーを作る、というようにしてａ分木（ＨＫＴ）のすべてのノード（葉も含む）に対応するノードキーを作成する。
【０１７６】
（ｄ）葉のノードキーを各受信機へ送信する処理。これらの（ａ）〜（ｄ）の処理を信頼センタが実行する。
【０１７７】
一方、デバイスは、ステップＳ２０１において以下の処理を実行する。すなわち、上述した信頼センタＴＣのセットアップ処理において公開または提供される以下の情報、
（ｅ）ａ分木（ＨＫＴ）構成情報
（ｆ）落とし戸つき一方向置換Ｆｉ
（ｇ）自己ノードである葉のノードキー
の各情報を取得する。
【０１７８】
これらのセットアップ処理の後、（２）信頼センタによるリボークおよび暗号文送信処理が実行される。
【０１７９】
信頼センタＴＣは、ステップＳ１０２において、以下の処理を実行する。
（ｈ）リボークデバイスの選択
（ｉ）暗号化用ノードキーの選択
（ｊ）表現コード生成
（ｋ）暗号文生成
（ｌ）表現コード、暗号文送信
の各処理である。
【０１８０】
（ｈ）リボークデバイスの選択は、図６を参照して説明したように、秘密情報の取得を認めないデバイスを選択する処理である。例えば、図６の例では、ａ分木（ＨＫＴ）のそれぞれ異なる葉に割り当てたデバイスｕ１，ｕ２，ｕ３，ｕ４，・・ｕ２７を秘密情報の取得を認めないデバイス（排除（リボーク）デバイス）として決定している。
【０１８１】
（ｉ）暗号化用ノードキーの選択は、リボークデバイスに割り当てられた葉からルートにいたるまでのパス上のノード（図６の黒丸ノード）以外のノードによって構成される部分木のルート（頂点ノード）となるノード（図６の四角ノード）に対応するノードキーの選択処理として実行される。
【０１８２】
これらのノードキーによって送信する秘密情報（Ｉ）を暗号化した暗号文のセットを送信することで、リボークされていないデバイスは、部分木のルートとなるノードに対応するノードキーのいずれかを導出することができるので、受信暗号文セットから、自己において導出可能なノードキーによって暗号化された暗号文を選択して復号することにより秘密情報の取得が可能となる。暗号文のセット中には、リボークデバイスが持つノードキーから導出することができるノードキーによって暗号化された暗号文が含まれないため、リボークデバイス（×印）は、秘密情報の取得ができないことになる。
【０１８３】
（ｊ）表現コード生成は、デバイスに送信する暗号文のセットと、暗号化に用いたノードキーとの対応を明示するためのコードデータであり、ａ分木（ＨＫＴ）の最上位ノードであるルートと、そこから暗号文を作るのに用いられたノードキーに対応するノードまでのａ分木（ＨＫＴ）のパスを結んだ表現木（図７参照）構成を示すコードデータである。
【０１８４】
デバイスは、暗号文のセットと、表現コードとを対応付けて、自デバイスにおいて算出可能なノードキーを用いて、秘密情報（Ｉ）を暗号化した暗号文を選択することが可能となり、選択暗号文の復号により秘密情報（Ｉ）を取得できる。
【０１８５】
（ｋ）暗号文生成処理は、上述した（ｉ）暗号化用ノードキーの選択において選択したノードキー、すなわち、リボークデバイスに割り当てられた葉からルートにいたるまでのパス上のノード（図６の黒丸ノード）以外のノードによって構成される部分木のルート（頂点ノード）となるノード（図６の四角ノード）に対応するノードキーによって秘密情報（Ｉ）を暗号化する処理である。
【０１８６】
（ｌ）表現コード、暗号文送信処理は、上述の（ｊ）表現コード生成処理で生成した表現コードと、上述の（ｋ）暗号文生成処理において生成した暗号文のセットをデバイスに対して送信する処理である。例えば同報通信路を介したデータ送信として実行され、データ受信は、いずれのデバイスも可能である。ただし、上述したように、リボークされたデバイス以外のデバイスのみが導出可能なノードキーのみを用いて暗号化した暗号文のみが含まれるので、リボークデバイスは暗号文を受信しても復号することができず、リボークされていないデバイスのみが、暗号文を復号して秘密情報（Ｉ）を取得することが可能となる。
【０１８７】
次に、（３）デバイスによる暗号文受信、復号の処理として、デバイスは、ステップＳ２０２において、
（ｍ）表現コード、暗号文受信
（ｎ）表現木再構築
（ｏ）ノード、暗号文特定
（ｐ）ノードキー導出
（ｑ）暗号文復号
の各処理を実行する。
【０１８８】
（ｍ）表現コード、暗号文受信は、信頼センタＴＣの送信する表現コード、暗号文を受信する処理である。
【０１８９】
（ｎ）表現木再構築は、信頼センタＴＣから受信した表現コードに基づいて、表現木を再構築する処理である。表現コードは、デバイスが受信した暗号文のセットと、暗号化に用いたノードキーとの対応を明示するためのコードデータであり、ａ分木（ＨＫＴ）の最上位ノードであるルートと、そこから暗号文を作るのに用いられたノードキーに対応するノードまでのａ分木（ＨＫＴ）のパスを結んだ表現木（図７参照）構成を示すコードデータである。デバイスは、セットアップ処理時に信頼センタの公開したａ分木（ＨＫＴ）の構成情報と、信頼センタＴＣから受信した表現コードに基づいて、暗号文を作るのに用いられたノードキーに対応するノードまでのａ分木（ＨＫＴ）のパスを結んだ表現木（図７参照）構成を再構築する。
【０１９０】
（ｏ）ノード、暗号文特定処理は、信頼センタＴＣから受信した表現コードに基づいて再構築した表現木から、自デバイスにおいて導出可能なノードキーを持つノードを特定し、そのノードに対応するノードキーを用いて暗号化した暗号文を信頼センタＴＣから受信した暗号文のセットから特定する処理である。ａ分木（ＨＫＴ）において自身の葉からルートまでのパス上に、表現木の葉となるノードが存在した場合、表現木の葉となるノードに対応するノードキーを用いて暗号化された暗号文が、信頼センタＴＣから受信した暗号文のセットに含まれることになる。
【０１９１】
暗号文は、複数の暗号文のセットにより構成され、その順番は、前述したように、暗号化に用いられたノードキーに対応するノードの番号が小さい順に設定されたものであり、デバイスは、ａ分木（ＨＫＴ）において自身の葉からルートまでのパス上に、表現木の葉となるノードが存在した場合、表現木の葉となるノードに対応するノードキーを用いて暗号化された暗号文を選択することができる。
【０１９２】
デバイスは、このように、暗号文のセットと、表現コードとを対応付けて、自デバイスにおいて算出可能なノードキーを用いて、秘密情報（Ｉ）を暗号化した暗号文を選択することが可能となる。
【０１９３】
（ｐ）ノードキー導出処理は、以下のように実行する。もしａ分木（ＨＫＴ）においてデバイスが割り当てられた葉が表現木の葉と一致するときは、デバイスが与えられたノードキーを用いて暗号化がなされているので、直接これを用いて暗号文を復号する。もし表現木の葉が、ａ分木（ＨＫＴ）の内部ノードであるときは、デバイスはあらかじめ与えられたａ分木（ＨＫＴ）の葉のノードキーから内部ノードのノードキーを導出する。まず、ａ分木（ＨＫＴ）において、デバイスが割り当てられた葉がその親ノードの左から数えて何番目の子であるかを調べる。これをｉ番目とおくと、その与えられたノードキーＮＫｋに対して、公開されている一方向置換Ｆｉを適用した結果のＦｉ（ＮＫｋ）が親ノードのノードキーとなる。
【０１９４】
たとえば図７において、ノードｖ１８３０４は、その親ノードｖ６３０５の左から２番目の子ノードであるから、ノードｖ１８３０４に対応するデバイスｕ５３０６は、与えられたノードｖ１８３０４のノードキーＮＫ１８と、公開されている一方向置換Ｆ２を用いてノードｖ６３０５のノードキーＮＫ６＝Ｆ２（ＮＫ１８）を導出することができる。
【０１９５】
もしデバイスがさらに上位のノードのノードキーを必要としていれば、デバイスはこの処理を繰り返すことでさらに上位のノードのノードキーを導出できる。すなわち、デバイスがこれまでに導出したノードキーＮＫｋに対応するノードがその親ノードの左からｉ番目の子ノードであるとき、親ノードのノードキーはＦｉ（ＮＫｋ）となる。デバイスは必要なノードキーを導出するまであるノードキーから親ノードのノードキーを導出する処理を繰り返す。たとえば、排除されるデバイスがひとつもないときは、ルートのノードキーが暗号化に用いられ、ただ１つの暗号文が送信される。例えば、この暗号文を復号するために、デバイスｕ８はルートのノードキーをＦ１（Ｆ３（Ｆ２（ＮＫ２１）））として求めることができる。
【０１９６】
（ｑ）暗号文復号処理は、上述の（ｐ）ノードキー導出処理によって取得したノードキーを用いて、上述の（ｏ）ノード、暗号文特定処理において特定した処理対象の暗号文を復号する処理として実行する。例えば、ＡＥＳアルゴリズムに従ってノードキー導出処理によって取得したノードキーを用いて復号処理を実行することで、秘密情報（Ｉ）を取得する。
【０１９７】
このように、本実施例の構成を用いれば、それぞれのデバイスは高々ｌｏｇａＮ回、すなわち最大でも木の高さの回数だけ一方向置換を実行すれば、自分が与えられた葉に対応するノードキーから、その葉からルートまでのパス上に存在する任意のノードキーを導出することが可能となり、導出したノードキーを用いて暗号文を復号することによって秘密情報を取得することが可能となる。
【０１９８】
上述したように、本実施例の構成では、信頼センタが、ａ分木（ＨＫＴ）を設定し、リボークデバイスの排除処理に基づいて構成される部分木の頂点ノードを選択し、頂点ノードに基づいて構成される表現木を設定し、表現木の葉、すなわち部分木の頂点ノードに対応するノードキーを用いて送信する秘密情報（Ｉ）を暗号化して同報通信路を用いて暗号文を送信することで、部分木のルートとなるノードに対応するノードキーを導出することができるリボークされていないデバイスのみが、自己において導出可能なノードキーを用いた暗号文の復号により秘密情報の取得が可能となり、デバイスにおいてノードキー算出に必要な計算量の削減が可能となる。
【０１９９】
［実施例２：公開鍵バージョン］
実施例２では、実施例１の基本方式に対して公開鍵バージョンを構成し、必ずしも信頼性の保障されない任意のエンティテイが秘密情報の送信者になれるようにした構成例である。
【０２００】
実施例２では、ａ分木（ＨＫＴ）の各ノードに秘密ノードキー公開ノードキーとを設定し、公開ノードキーを公開して、公開ノードキーによって暗号文を生成し、受信デバイスにおいて、秘密ノードキーを導出して暗号文の復号を実行する構成である。
【０２０１】
図９を参照して、本実施例全体の流れと信頼センタＴＣ、秘密情報送信者、およびデバイスの処理を示す。秘密情報送信者は、必ずしも信頼性の保障されない任意のエンティテイである。
【０２０２】
処理は、上述した実施例１と同様、
（１）セットアップ処理
（２）信頼センタによるリボークおよび暗号文送信
（３）デバイスによる暗号文受信、復号
の３フェーズによって構成される。
【０２０３】
（１）のセットアップ処理は１回、実行すればよく、セットアッサプされた後のリボーク処理、暗号文送信処理、暗号文受信および復号処理は繰り返し実行可能となる。
【０２０４】
セットアップ処理では信頼センタＴＣが、ステップＳ３１１において、以下の処理を実行する。
（ａ）ａ分木（ＨＫＴ）の生成、ａ分木（ＨＫＴ）構成情報の公開処理
（ｂ）落とし戸つき一方向置換Ｆｉとその逆置換Ｆ−１ｉを設定し、一方向置換Ｆｉを公開する処理
これらの処理は、上述の実施例１と同様の処理である。
【０２０５】
（ｃ）ａ分木（ＨＫＴ）のルートｖｋに対応する秘密ノードキーＰｒｉＮＫｋと、公開ノードキーＰｕｂＮＫｋを以下の手順で生成する。
【０２０６】
信頼センタＴＣは、大きな素数ｑと巡回群Ｚｑの生成元ｇを公開する。実施例１のセットアップで作成したａ分木（ＨＫＴ）の各ノードに対応するノードキーを、秘密ノードキーＰｒｉＮＫｋとして定義する。
【０２０７】
すなわち、ルートｖ１に対応する秘密ノードキーＰｒｉＮＫ１を、落とし戸つき一方向置換Ｆｉ（）の定義域の中からランダムに選択し、ａ分木（ＨＫＴ）のルートｖ１以外のノードｖｋに対応する秘密ノードキーＰｒｉＮＫｋを、下記の手順で再帰的に生成する処理。すなわち、あるノードｖｋに対応する秘密ノードキーをＰｒｉＮＫｋとするとき、ｖｋの子ノードのうち、左端のものの秘密ノードキーをＦ−１１（ＰｒｉＮＫｋ）とし、左からｉ番目の子ノードの秘密ノードキーをＦ−１ｉ（ＰｒｉＮＫｋ）とし、右端のものの秘密ノードキーをＦ−１ａ（ＰｒｉＮＫｋ）とする。信頼センタＴＣはこの手法を用いて、まずルートの子ノードの秘密ノードキーを作り、さらにそれらのノードの子ノードの秘密ノードキーを作る、というようにしてａ分木（ＨＫＴ）のすべてのノード（葉も含む）に対応する秘密ノードキーを作成する。
【０２０８】
さらに、ａ分木（ＨＫＴ）の各ノードに対応する秘密ノードキーＰｒｉＮＫｋに対応する公開ノードキーＰｕｂＮＫｋを、
ＰｕｂＮＫｋ＝ｇＰｒｉＮＫｋｍｏｄｑ
として定め、
ａ分木（ＨＫＴ）の各ノードに対応するノード番号ｖｋと公開ノードキーＰｕｂＮＫｋとの対応データを公開鍵ファイルとして公開する。
【０２０９】
このように、信頼センタＴＣは、ａ分木（ＨＫＴ）の各ノードに対応する秘密ノードキーＰｒｉＮＫｋと公開ノードキーＰｕｂＮＫｋを設定し、各ノードに対応するノード番号ｖｋと公開ノードキーＰｕｂＮＫｋとの対応データを公開鍵ファイルとして公開する処理をセットアップ処理として実行する。
【０２１０】
ステップＳ３１１の（ｄ）公開ノードキーの公開処理は、上述したａ分木（ＨＫＴ）の各ノードに対応するノード番号ｖｋと公開ノードキーＰｕｂＮＫｋとの対応データを公開鍵ファイルとして公開する処理である。
【０２１１】
ステップＳ３１１の（ｅ）葉の秘密ノードキーを各受信機へ送信する処理は、デバイスの設定されるａ分木（ＨＫＴ）のノード（葉）に対応する秘密ノードキーを各デバイスに送信する処理である。この処理は、セキュアな通信路を確保して実行する。
【０２１２】
一方、デバイスは、ステップＳ３３１において以下の処理を実行する。すなわち、上述した信頼センタＴＣのセットアップ処理において公開または提供される以下の情報、
（ｇ）ａ分木（ＨＫＴ）構成情報
（ｈ）落とし戸つき一方向置換Ｆｉ
（ｉ）自己ノードである葉の秘密ノードキー
の各情報を取得する。
【０２１３】
さらに、任意のエンティテイによって構成される秘密情報（Ｉ）の送信処理を実行する秘密情報送信者は、ステップＳ３２１において、
（ｆ）公開ノードキー取得
を実行する。
これは、信頼センタＴＣがステップＳ３１１の処理（ｄ）公開ノードキーの公開処理で実行した各ノードに対応するノード番号ｖｋと公開ノードキーＰｕｂＮＫｋとの対応データ、すなわち、公開鍵ファイルを取得する処理である。
【０２１４】
これらのセットアップ処理の後、（２）秘密情報送信者によるリボークおよび暗号文送信処理が実行される。
【０２１５】
秘密情報送信者は、ステップＳ３２２において、以下の処理を実行する。
（ｊ）リボークデバイスの選択
（ｋ）暗号化用ノードキーの選択
（ｌ）表現コード生成
（ｍ）暗号文生成
（ｎ）表現コード、暗号文送信
の各処理である。
【０２１６】
（ｊ）リボークデバイスの選択は、図６を参照して説明したように、秘密情報の取得を認めないデバイスを選択する処理である。例えば、図６の例では、ａ分木（ＨＫＴ）のそれぞれ異なる葉に割り当てたデバイスｕ１，ｕ２，ｕ３，ｕ４，・・ｕ２７を秘密情報の取得を認めないデバイス（排除（リボーク）デバイス）として決定している。
【０２１７】
（ｋ）暗号化用公開ノードキーの選択は、リボークデバイスに割り当てられた葉からルートにいたるまでのパス上のノード（図６の黒丸ノード）以外のノードによって構成される部分木のルート（頂点ノード）となるノード（図６の四角ノード）に対応する公開ノードキーの選択処理として実行される。
【０２１８】
これらの公開ノードキーによって送信する秘密情報（Ｉ）を暗号化した暗号文のセットを送信することで、リボークされていないデバイスは、部分木のルートとなるノードに対応する秘密ノードキーのいずれかを導出することができるので、受信暗号文セットから、自己において導出可能な秘密ノードキーを適用して、対応する公開ノードキーで暗号化された暗号文を選択して復号することにより秘密情報の取得が可能となる。暗号文のセット中には、リボークデバイスが持つ秘密ノードキーから導出することができる秘密ノードキーに対応する公開ノードキーによって暗号化された暗号文が含まれないため、リボークデバイス（×印）は、秘密情報の取得ができないことになる。
【０２１９】
（ｌ）表現コード生成は、デバイスに送信する暗号文のセットと、暗号化に用いた公開ノードキーとの対応を明示するためのコードデータであり、ａ分木（ＨＫＴ）の最上位ノードであるルートと、そこから暗号文を作るのに用いられた公開ノードキーに対応するノードまでのａ分木（ＨＫＴ）のパスを結んだ表現木（図７参照）構成を示すコードデータである。
【０２２０】
デバイスは、暗号文のセットと、表現コードとを対応付けて、自デバイスにおいて算出可能な秘密ノードキーを用いて、その秘密ノードキーに対応する公開ノードキーで秘密情報（Ｉ）を暗号化した暗号文を選択することが可能となり、選択暗号文の復号により秘密情報（Ｉ）を取得できる。
【０２２１】
（ｍ）暗号文生成処理は、上述した（ｉ）暗号化用公開ノードキーの選択において選択した公開ノードキー、すなわち、リボークデバイスに割り当てられた葉からルートにいたるまでのパス上のノード（図６の黒丸ノード）以外のノードによって構成される部分木のルート（頂点ノード）となるノード（図６の四角ノード）に対応する公開ノードキーによって秘密情報（Ｉ）を暗号化する処理である。
【０２２２】
暗号化はたとえば下記のように行う。送信者は区間［１、ｑ−１］から数ｘをランダムに選び、これと公開ノードキーＰｕｂＮＫｋを用いて秘密情報（Ｉ）を下記のように暗号化してノードｖｋ用の暗号文ＣＴｋを生成する。
【０２２３】
【数２６】
2004320183.tif 000016
【０２２４】
送信者は、表現コードと暗号文ＣＴｋを生成する。なお、生成する暗号文は、選択した公開ノードキーＰｕｂＮＫｋの数に応じた複数の暗号文のセットとなる。さらに、上記式に対応する暗号文とともに、ｇｘｍｏｄｑを生成し、暗号文とともに、同報通信路を用いてデバイスに対して送信する。
【０２２５】
（ｎ）表現コード、暗号文送信処理は、上述の（ｌ）表現コード生成処理で生成した表現コードと、上述の（ｍ）暗号文生成処理において生成した暗号文セット、およびｇｘｍｏｄｑをデバイスに対して送信する処理である。例えば同報通信路を介したデータ送信として実行され、データ受信は、いずれのデバイスも可能である。ただし、上述したように、リボークされたデバイス以外のデバイスのみが導出可能な秘密ノードキーに対応する公開ノードキーのみを用いて暗号化した暗号文のみが含まれるので、リボークデバイスは暗号文を受信しても復号することができず、リボークされていないデバイスのみが、暗号文を復号して秘密情報（Ｉ）を取得することが可能となる。
【０２２６】
次に、（３）デバイスによる暗号文受信、復号の処理として、デバイスは、ステップＳ３３２において、
（ｏ）表現コード、暗号文受信
（ｐ）表現木再構築
（ｑ）ノード、暗号文特定
（ｒ）秘密ノードキー導出
（ｓ）暗号文復号
の各処理を実行する。
【０２２７】
（ｏ）表現コード、暗号文受信は、信頼センタＴＣの送信する表現コード、暗号文を受信する処理である。
【０２２８】
（ｐ）表現木再構築は、信頼センタＴＣから受信した表現コードに基づいて、表現木を再構築する処理である。表現コードは、デバイスが受信した暗号文のセットと、暗号化に用いた公開ノードキーとの対応を明示するためのコードデータであり、ａ分木（ＨＫＴ）の最上位ノードであるルートと、そこから暗号文を作るのに用いられた公開ノードキーに対応するノードまでのａ分木（ＨＫＴ）のパスを結んだ表現木（図７参照）構成を示すコードデータである。デバイスは、セットアップ処理時に信頼センタの公開したａ分木（ＨＫＴ）の構成情報と、信頼センタＴＣから受信した表現コードに基づいて、暗号文を作るのに用いられた公開ノードキーに対応するノードまでのａ分木（ＨＫＴ）のパスを結んだ表現木（図７参照）構成を再構築する。
【０２２９】
（ｑ）ノード、暗号文特定処理は、信頼センタＴＣから受信した表現コードに基づいて再構築した表現木から、自デバイスにおいて導出可能な秘密ノードキーを持つノードを特定し、そのノードに対応する公開ノードキーを用いて暗号化した暗号文を信頼センタＴＣから受信した暗号文のセットから特定する処理である。ａ分木（ＨＫＴ）において自身の葉からルートまでのパス上に、表現木の葉となるノードが存在した場合、表現木の葉となるノードに対応する公開ノードキーを用いて暗号化された暗号文が、信頼センタＴＣから受信した暗号文のセットに含まれることになる。
【０２３０】
暗号文は、複数の暗号文のセットにより構成され、その順番は、前述したように、暗号化に用いられた公開ノードキーに対応するノードの番号が小さい順に設定されたものであり、デバイスは、ａ分木（ＨＫＴ）において自身の葉からルートまでのパス上に、表現木の葉となるノードが存在した場合、表現木の葉となるノードに対応する公開ノードキーを用いて暗号化された暗号文を選択することができる。
【０２３１】
デバイスは、このように、暗号文のセットと、表現コードとを対応付けて、自デバイスにおいて算出可能な秘密ノードキーに対応する公開ノードキーを用いて、秘密情報（Ｉ）を暗号化した暗号文を選択することが可能となる。
【０２３２】
（ｒ）秘密ノードキー導出処理は、公開ノードキーを用いて秘密情報（Ｉ）を暗号化した暗号文の復号に適用する秘密ノードキーを導出する処理である。秘密ノードキー導出処理は、以下のように実行する。もしａ分木（ＨＫＴ）においてデバイスが割り当てられた葉が表現木の葉と一致するときは、デバイスがセットアップ処理のステップＳ３１１（ｉ）の処理で信頼センタＴＣから付与された秘密ノードキーを用いて暗号化がなされているので、直接これを用いて暗号文を復号する。
【０２３３】
もし表現木の葉が、ａ分木（ＨＫＴ）の内部ノードであるときは、デバイスはステップＳ３１１（ｉ）の処理で信頼センタＴＣから付与された秘密ノードキーから内部ノードのノードキーを導出する。まず、ａ分木（ＨＫＴ）において、デバイスが割り当てられた葉がその親ノードの左から数えて何番目の子であるかを調べる。これをｉ番目とおくと、その与えられた秘密ノードキーＰｒｉＮＫｋに対して、公開されている一方向置換Ｆｉを適用した結果のＦｉ（ＰｒｉＮＫｋ）が親ノードの秘密ノードキーとなる。
【０２３４】
たとえば図７において、ノードｖ１８３０４は、その親ノードｖ６３０５の左から２番目の子ノードであるから、ノードｖ１８３０４に対応するデバイスｕ５３０６は、与えられたノードｖ１８３０４の秘密ノードキーＰｒｉＮＫ１８と、公開されている一方向置換Ｆ２を用いてノードｖ６３０５の秘密ノードキーＰｒｉＮＫ６＝Ｆ２（ＰｒｉＮＫ１８）を導出することができる。
【０２３５】
もしデバイスがさらに上位のノードの秘密ノードキーを必要としていれば、デバイスはこの処理を繰り返すことでさらに上位のノードの秘密ノードキーを導出できる。すなわち、デバイスがこれまでに導出した秘密ノードキーＰｒｉＮＫｋに対応するノードがその親ノードの左からｉ番目の子ノードであるとき、親ノードの秘密ノードキーはＦｉ（ＰｒｉＮＫｋ）となる。デバイスは必要な秘密ノードキーを導出するまである秘密ノードキーから親ノードの秘密ノードキーを導出する処理を繰り返す。たとえば、排除されるデバイスがひとつもないときは、ルートの秘密ノードキーに対応する公開ノードキーが暗号化に用いられ、ただ１つの暗号文が送信される。例えば、この暗号文を復号するために、デバイスｕ８はルートの秘密ノードキーをＦ１（Ｆ３（Ｆ２（ＰｒｉＮＫ２１）））として求めることができる。
【０２３６】
（ｑ）暗号文復号処理は、上述の（ｐ）秘密ノードキー導出処理によって取得した秘密ノードキーを用いて、上述の（ｏ）ノード、暗号文特定処理において特定した処理対象の暗号文を復号する処理として実行する。例えば、ＡＥＳアルゴリズムに従って、秘密ノードキー導出処理によって取得した秘密ノードキーを用いて復号処理を実行することで、秘密情報（Ｉ）を取得する。
【０２３７】
デバイスは、前述の（ｏ）ノード、暗号文特定処理において、表現コードを用いて自分に対応するノードｖｋと暗号文ＣＴｋを特定する。そして、上述の（ｐ）秘密ノードキー導出処理によって、自身に与えられた葉の秘密ノードキーからノードｖｋの秘密ノードキーＰｒｉＮＫｋを導出する。最後に、次式により暗号文ＣＴｋを復号して秘密情報Ｉを得る。
【０２３８】
【数２７】
2004320183.tif 000017
【０２３９】
このように、本実施例の構成を用いれば、信頼性の必ずしも保証されない任意のエンティテイが、信頼センタの公開するノード対応の公開ノードキー情報を取得して、公開ノードキーを用いた秘密情報の暗号化処理を実行することで、秘密情報（Ｉ）を特定のリボークされないデバイスにのみ選択的に送信することが可能となる。本実施例の構成においても、それぞれのデバイスは高々ｌｏｇａＮ回、すなわち最大でも木の高さの回数だけ一方向置換を実行すれば、自分が与えられた葉に対応する秘密ノードキーから、その葉からルートまでのパス上に存在する任意の秘密ノードキーを導出することが可能となり、導出した秘密ノードキーを用いて暗号文を復号することによって秘密情報を取得することが可能となる。
【０２４０】
なお、公開ノードキーを用いた暗号化および秘密ノードキーを用いた復号処理は、上述した処理に限られるものでなく、例えば、下記式に従って実行する構成としてもよい。
【０２４１】
【数２８】
2004320183.tif 000018
【０２４２】
上記式において、Ｈは長さ｜ｑ｜の任意の値を、長さ｜Ｉ｜のランダムな値にマッピングするハッシュ関数である。たとえば、Ｉの長さが１２８ビットであれば、前述のハッシュ関数ＭＤ５をＨとして用いることができる。この手法を用いれば、個々の暗号文の長さを｜Ｉ｜に変換して送信することが可能となる。
【０２４３】
［情報処理装置構成例］
次に、上述した各実施例において説明したデバイス、信頼センタ、秘密情報送信者、各エンティテイを構成する情報処理装置の構成例を図１０を参照して説明する。デバイス、信頼センタ、秘密情報送信者、各エンティテイを構成する情報処理装置は、例えばＰＣ、情報処理サーバ等の汎用的な情報処理装置によって構成可能であり、デバイスは、さらに、暗号化コンテンツを再生する再生装置に暗号処理部を備えた様々な機器構成によっても実現可能である。以下、図１０を参照して、上述した各実施例において説明したデバイス、信頼センタ、秘密情報送信者、各エンティテイを構成する情報処理装置の構成例について説明する。
【０２４４】
ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０１は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）５０２に記憶されている各種プログラム、あるいは、記憶部５０８に格納され、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０３にロードされたプログラムに従って各種処理を実行する。タイマ５００は計時処理を行ない、クロック情報をＣＰＵ５０１に供給する。
【０２４５】
ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）５０２は、ＣＰＵ５０１が使用するプログラムや演算用のパラメータ、固定データ等を格納する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０３は、ＣＰＵ５０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これら各素子はバス５１１により相互に接続されている。
【０２４６】
暗号化復号部５０４は、上述したノードキー、秘密ノードキー、公開ノードキーによる暗号化、復号化等の暗号処理、例えばＡＥＳ暗号化アルゴリズムを適用した暗号処理等を実行する。
【０２４７】
入出力インタフェース５１２には、キーボード、マウス等の入力部５０６、ＣＲＴ、ＬＣＤ等のディスプレイ、スピーカ等からなる出力部５０７、ハードディスク等の記憶部５０８、通信部５０９が接続される。通信部５０９は、例えばインターネット等の通信網を介したデータ送受信を行ない、上述した暗号文の通信処理を実行する。
【０２４８】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０２４９】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０２５０】
例えば、プログラムは記憶媒体としてのハードディスクやＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ  ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０２５１】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記憶媒体にインストールすることができる。
【０２５２】
また、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０２５３】
【発明の効果】
以上、説明したように、本発明の構成によれば、階層型木構造を適用した暗号鍵等の暗号データ提供処理において、リーフの保持する鍵の数を１つのみとすることが可能となり、その保持する鍵に基づいてルートから自己の属するリーフまでのパス上の各ノードに対応するノードキーの算出を効率的に行い、暗号文の復号処理を少ない保持鍵に基づいて効率的に実行することが可能となる。具体的には、各デバイスは高々ｌｏｇａＮ回、すなわち最大でも木の高さの回数だけ一方向置換を実行すれば、自分が与えられた葉に対応するノードキーから、その葉からルートまでのパス上に存在する任意のノードキーを導出することが可能となる。
【０２５４】
さらに、本実施例の構成によれば、階層型木構造を適用した暗号データ提供処理において、ａ分木（ＨＫＴ）における各ノードキーの算出処理および設定処理に落とし戸つき一方向置換Ｆｉと、逆置換Ｆ−１ｉを適用し、各デバイスにおけるノードキーの算出において、最大でも木の高さの回数だけの一方向置換Ｆｉを実行すればノードキー算出を完了する構成としたので、各デバイスにおける暗号文の復号プロセスにおける処理負荷が軽減される。
【０２５５】
さらに、本発明の構成においては、リボークデバイスの排除処理に基づいて構成される部分木の頂点ノードを選択し、頂点ノードに基づいて構成される表現木を設定し、表現木の葉、すなわち部分木の頂点ノードに対応するノードキーを用いて送信する秘密情報（Ｉ）を暗号化して生成した暗号文を送信することで、部分木のルートとなるノードに対応するノードキーを導出することができるリボークされていないデバイスのみが、自己において導出可能なノードキーを用いた暗号文の復号により秘密情報の取得が可能となり、限定ユーザを特定した暗号化データの配信が可能となる。
【０２５６】
さらに、本発明の構成によれば、信頼性の必ずしも保証されない任意のエンティテイが、信頼センタの公開するノード対応の公開ノードキー情報を取得して、公開ノードキーを用いた秘密情報の暗号化処理を実行することで、秘密情報（Ｉ）を特定のリボークされないデバイスにのみ選択的に送信することが可能となり、本構成においても、それぞれのデバイスは高々ｌｏｇａＮ回、すなわち最大でも木の高さの回数だけ一方向置換を実行すれば、自分が与えられた葉に対応する秘密ノードキーから、その葉からルートまでのパス上に存在する任意の秘密ノードキーを導出することが可能となり、導出した秘密ノードキーを用いて暗号文を復号することによって秘密情報を取得することが可能となる。
【図面の簡単な説明】
【図１】各種キー、データの暗号化処理、配布処理に適用される階層型木構造を説明する図である。
【図２】各種キー、データの配布に使用される有効化キーブロック（ＥＫＢ）の例を示す図である。
【図３】コンテンツ鍵の有効化キーブロック（ＥＫＢ）を使用した配布例と復号処理例を示す図である。
【図４】各ノードにａ個の子ノードまたはリーフを持つａ分木構造におけるノード、デバイスを説明する図である。
【図５】ルートｖ１のノードキーをＳと置いたときの各ノードのノードキーの設定令を説明する図である。
【図６】リボークデバイスの設定について説明する図である。
【図７】表現木の構成について説明する図である。
【図８】実施例１に対応する処理の流れと信頼センタＴＣおよびデバイスの処理を説明する図である。
【図９】実施例２に対応する処理の流れと信頼センタＴＣおよびデバイスの処理を説明する図である。
【図１０】実施例において説明したデバイス、信頼センタ、秘密情報送信者、各エンティテイを構成する情報処理装置の構成例を示す図である。
【符号の説明】
１０１  ルート
１０２〜１０５  ノード
２０１，２０２  部分木
３０１〜３０６  デバイス
５００  タイマ
５０１  ＣＰＵ（Ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）
５０２  ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ−Ｍｅｍｏｒｙ）
５０３  ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）
５０４  暗号化復号部
５０６  入力部
５０７  出力部
５０８  記憶部
５０９  通信部
５１０  ドライブ
５１１  バス
５１２  入出力インタフェース
５２１  リムーバブル記録媒体
【図１】
2004320183.tif 000031
【図２】
2004320183.tif 000032
【図３】
2004320183.tif 000033
【図４】
2004320183.tif 000034
【図５】
2004320183.tif 000035
【図６】
2004320183.tif 000036
【図７】
2004320183.tif 000037
【図８】
2004320183.tif 000038
【図９】
2004320183.tif 000039
【図１０】
2004320183.tif 000040