(57)【要約】【課題】複数の復号用データを用いて暗号データを復号する処理装置が保持する復号用データの数を削減できるデータ処理方法を提供する。【解決手段】受信装置ｕ１〜ｕ１６の各々が複数の集合の要素となるように集合を規定し、複数の集合のそれぞれについて、当該集合に割り当てた素数データｐと非公開データＫとを基に、当該集合の要素となる受信装置が暗号データの復号に用いるラベルデータを生成する。また、受信装置を要素とする上記複数の集合に割り当てられた素数データと非公開データＫとを基に、当該複数の集合についてそれぞれ生成された複数の上記ラベルデータを当該受信装置が素数データｐを基に生成するための単数のマスタラベルデータＭＬｍを生成し、これを受信装置にセキュアな状態に提供する。【選択図】  図５
2005012280.tif 000002
【特許請求の範囲】
【請求項１】
暗号データの復号に処理装置で用いられる復号用データを生成するデータ処理方法であって、
前記暗号データの復号に前記処理装置で用いられる異なる複数の第１の復号用データの各々を、前記複数の第１の復号用データのそれぞれに割当てられ前記処理装置に公開された異なる複数の固有データのうち当該第１の復号用データに割当てられた前記固有データと、所定の非公開データとを基に生成する第１の工程と、
前記第１の工程で生成した前記複数の第１の復号用データを前記処理装置が前記固有データを基に生成するために用いられ、前記処理装置にセキュアな状態で提供される単数の第２の復号用データを、前記非公開データと前記固有データとを基に生成する第２の工程と
を有するデータ処理方法。
【請求項２】
前記第１の工程は、当該第１の復号用データに割当てられた前記固有データである素数データｐと、前記非公開データＫと、所定の定数Ｔと、所定の素数の積を示す公開データＭと、ハッシュ関数Ｈとを用いて、下記式（１）により、前記第１の復号用データＬＡＢＥＬを生成し、
前記第２の工程は、前記異なる複数の固有データである前記素数データｐの積を示すデータｗと、前記定数Ｔと、前記非公開データＫと、前記公開データＭとを基に、下記式（２）により、前記第２の復号データＭＬを生成する
請求項１に記載のデータ処理方法。
【数１】
2005012280.tif 000007
【数２】
2005012280.tif 000008
【請求項３】
複数の前記処理装置に異なる複数の前記固有データを割り当て、前記複数の処理装置の各々について前記第１の工程および前記第２の工程により前記第２の復号用データを生成する場合に、
前記定数Ｔは、前記複数の処理装置に割当てられた前記複数の固有データの積を示す
請求項２に記載のデータ処理方法。
【請求項４】
複数の処理装置のうち同じ集合の要素となる前記処理装置に対して共通の復号用データを基に暗号データを復号させるデータ処理方法であって、
前記処理装置の各々が複数の前記集合の要素となるように、相互に異なる前記処理装置を要素とする複数の前記集合を規定した場合に、
前記複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、前記処理装置に公開される相互に異なる固有データを割り当てる第１の工程と、
前記複数の集合のそれぞれについて、当該集合に前記第１の工程で割り当てた前記固有データと非公開データとを基に、当該集合の要素となる前記処理装置が前記暗号データの復号に用いる第１の復号用データを生成する第２の工程と、
前記複数の処理装置の各々について、当該処理装置を要素とする前記複数の集合に前記第１の工程で割り当てられた前記固有データと非公開データとを基に、当該複数の集合について前記第２の工程でそれぞれ生成された複数の前記第１の復号用データを当該処理装置が前記固有データを基に生成するために用いられ、当該処理装置にセキュアな状態で提供される単数の第２の復号用データを生成する第３の工程と
を有するデータ処理方法。
【請求項５】
前記第２の工程で生成した複数の前記第１の復号用データのうち、指定した前記集合に対応する前記第１の復号用データを基に暗号化され前記処理装置に提供される前記暗号データを生成する第４の工程
をさらに有する請求項４に記載のデータ処理方法。
【請求項６】
各リーフに単数の前記処理装置が対応付けられたツリー上のルートと前記リーフとの間の同じパス上に位置する２つの構成要素からなる組に対して、当該組の構成要素のうちルートに近い第１の前記構成要素から分岐したリーフから、第２の前記構成要素から分岐したリーフを除いたリーフに割り当てられた前記処理装置を要素とする前記集合を規定した場合に、
前記第１の工程は、前記２つの構成要素が親子関係を持つ組の複数の前記集合に対して、相互に異なる前記固有データを割り当てる
請求項４に記載のデータ処理方法。
【請求項７】
前記第１の工程において前記固有データを割り当てた前記集合について前記第２の工程で生成した前記第１の復号用データを基に、当該組の前記第１の構成要素を共通にし、当該組の前記第２の構成要素から分岐したノードあるいはリーフを前記第２の構成要素とする組に対応する集合の復号用データを生成する第５の工程
をさらに有する請求項６に記載のデータ処理方法。
【請求項８】
前記複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、前記ツリーにおいて当該処理装置が割り当てられた前記リーフと前記ルートとの間のパス上にあるルートまたはノードを前記第１の構成要素とし、当該パス上の当該第１の構成要素と当該リーフとを除くこれらの間のノードから当該パス以外の向きに直接分岐したノードまたはリーフを前記第２の構成要素とし、当該第１の構成要素と当該第２の構成要素とが親子関係にない組に対応する前記集合に対して割り当てた復号用データを、当該集合の要素となる前記処理装置にセキュアな状態で提供する第６の工程
をさらに有する請求項７に記載のデータ処理方法。
【請求項９】
前記第１の工程は、前記複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、相互に異なる素数データｐを前記固有データとして割り当て、
前記第２の工程は、非公開データＫと、前記素数データｐと、所定の素数の積を示す公開データＭと、ハッシュ関数Ｈと、前記第１の工程について前記複数の処理装置の全てについて当該処理装置が要素となる複数の前記集合に割り当てた前記素数データｐの積を示す定数Ｔとを基に、下記式（３）により、前記第１の復号用データＬＡＢＥＬを生成し、
前記第３の工程は、前記複数の処理装置のそれぞれについて、当該処理装置が要素となる前記複数の集合に前記第１の工程でそれぞれ割り当てられた複数の前記素数データの積を示すデータｗと、前記非公開データＫと、前記公開データＭと、前記定数Ｔとを基に、下記式（４）により、前記第２の復号データＭＬを生成する
請求項４に記載のデータ処理方法。
【数３】
2005012280.tif 000009
【数４】
2005012280.tif 000010
【請求項１０】
前記選択された復号用データを当該復号用データの識別データを用いて指定する指定データを前記処理装置に提供する第７の工程をさらに有する
請求項４に記載のデータ処理方法。
【請求項１１】
前記処理装置が、前記第７の工程で受けた前記指定データに対応する前記公開された固有データと、提供を受けた前記第２の復号用データとを基に、前記第１の復号用データを生成する第８の工程と、
前記処理装置が、提供を受けた前記暗号データを、前記第８の工程で生成した前記第１の復号用データを用いて復号する第９の工程と
をさらに有する請求項１０に記載のデータ処理方法。
【請求項１２】
暗号データの復号に処理装置で用いられる復号用データを生成するデータ処理装置が実行するプログラムであって、
前記暗号データの復号に前記処理装置で用いられる異なる複数の第１の復号用データの各々を、前記複数の第１の復号用データのそれぞれに割当てられ前記処理装置に公開された異なる複数の固有データのうち当該第１の復号用データに割当てられた前記固有データと、所定の非公開データとを基に生成する第１の手順と、
前記第１の手順で生成した前記複数の第１の復号用データを前記処理装置が前記固有データを基に生成するために用いられ、前記処理装置にセキュアな状態で提供される単数の第２の復号用データを、前記非公開データと前記固有データとを基に生成する第２の手順と
を有するプログラム。
【請求項１３】
暗号データの復号に処理装置で用いられる復号用データを生成するデータ処理装置であって、
前記暗号データの復号に前記処理装置で用いられる異なる複数の第１の復号用データの各々を、前記複数の第１の復号用データのそれぞれに割当てられ前記処理装置に公開された異なる複数の固有データのうち当該第１の復号用データに割当てられた前記固有データと、所定の非公開データとを基に生成する第１の手段と、
前記第１の手段で生成した前記複数の第１の復号用データを前記処理装置が前記固有データを基に生成するために用いられ、前記処理装置にセキュアな状態で提供される単数の第２の復号用データを、前記非公開データと前記固有データとを基に生成する第２の手段と
を有するデータ処理装置。
【請求項１４】
複数の処理装置のうち同じ集合の要素となる前記処理装置に対して共通の復号用データを基に暗号データを復号させるデータ処理装置が実行するプログラムであって、
前記処理装置の各々が複数の前記集合の要素となるように、相互に異なる前記処理装置を要素とする複数の前記集合を規定した場合に、
前記複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、前記処理装置に公開される相互に異なる固有データを割り当てる第１の手順と、
前記複数の集合のそれぞれについて、当該集合に前記第１の手順で割り当てた前記固有データと非公開データとを基に、当該集合の要素となる前記処理装置が前記暗号データの復号に用いる第１の復号用データを生成する第２の手順と、
前記複数の処理装置の各々について、当該処理装置を要素とする前記複数の集合に前記第１の手順で割り当てられた前記固有データと非公開データとを基に、当該複数の集合について前記第２の手順でそれぞれ生成された複数の前記第１の復号用データを当該処理装置が前記固有データを基に生成するために用いられ、当該処理装置にセキュアな状態で提供される単数の第２の復号用データを生成する第３の手順と
を有するプログラム。
【請求項１５】
複数の処理装置のうち同じ集合の要素となる前記処理装置に対して共通の復号用データを基に暗号データを復号させるデータ処理装置であって、
前記処理装置の各々が複数の前記集合の要素となるように、相互に異なる前記処理装置を要素とする複数の前記集合を規定した場合に、
前記複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、前記処理装置に公開される相互に異なる固有データを割り当てる第１の手段と、
前記複数の集合のそれぞれについて、当該集合に前記第１の手段で割り当てた前記固有データと非公開データとを基に、当該集合の要素となる前記処理装置が前記暗号データの復号に用いる第１の復号用データを生成する第２の手段と、
前記複数の処理装置の各々について、当該処理装置を要素とする前記複数の集合に前記第１の手段で割り当てられた前記固有データと非公開データとを基に、当該複数の集合について前記第２の手段でそれぞれ生成された複数の前記第１の復号用データを当該処理装置が前記固有データを基に生成するために用いられ、当該処理装置にセキュアな状態で提供される単数の第２の復号用データを生成する第３の手段と
を有するデータ処理装置。
【請求項１６】
復号用データを基に暗号データを復号する処理装置が実行するプログラムであって、
前記暗号データと、当該暗号データを復号するための復号用データの指定を受ける第１の手順と、
予め保持している複数の固有データのうち、前記第１の手順で指定された復号用データに対応する固有データを選択する第２の手順と、
予め保持している復号用データと、前記第２の手順で選択した固有データとを基に、前記指定された復号用データを生成する第３の手順と、
前記第３の手順で生成した前記指定された復号用データを基に、前記第１の手順で受けた前記暗号データを復号する第４の手順と
を前記処理装置に実行させるプログラム。
【請求項１７】
前記第３の手順は、前記固有データＭＬｍと、前記予め保持している複数の固有データの積を示すデータｗｍと、前記第１の手順で指定された復号用データに対応する固有データｐと、２つの素数の積を示すデータＭと、ハッシュ関数Ｈとを用いて、下記式（５）を基に、前記復号用データＬＡＢＥＬを生成する
請求項１６に記載のプログラム。
【数５】
2005012280.tif 000011
【請求項１８】
複数の前記処理装置のうち同じ集合の要素となる前記処理装置に共通の復号用データを提供し、前記複数の処理装置に提供した暗号データを、指定した前記処理装置に前記復号用データを基に復号させるために、前記処理装置の各々が複数の前記集合の要素となるように、相互に異なる前記処理装置を要素とする複数の前記集合を規定した場合に、
前記固有データは、前記プログラムを実行する前記処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、相互に異なるように割り当てられており、
前記予め保持している前記復号用データは、当該処理装置を要素とする前記複数の集合に割り当てられた固有データと非公開データとを基に、当該複数の集合についてそれぞれ生成された複数の前記復号用データを当該処理装置が前記固有データを基に生成するための単数の復号用データである
請求項１６に記載のプログラム。
【請求項１９】
復号用データを基に暗号データを復号する処理装置であって、
前記暗号データと、当該暗号データを復号するための復号用データの指定を受ける第１の手段と、
予め保持している複数の固有データのうち、前記第１の手段で指定された復号用データに対応する固有データを選択する第２の手段と、
予め保持している復号用データと、前記第２の手段で選択した固有データとを基に、前記指定された復号用データを生成する第３の手段と、
前記第３の手段で生成した前記指定された復号用データを基に、前記第１の手段で受けた前記暗号データを復号する第４の手段と
を有する処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号データの復号に係わる処理を行うデータ処理方法、そのプログラムおよびその装置と処理装置に関する。
【０００２】
【従来の技術】
例えば、管理装置が、複数の受信装置に暗号データを送信し、リボークしない受信装置でのみ、当該暗号データを復号させる場合がある。
このような方式に、下記非特許文献１，２に記載されているＳＤ（Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）  がある。
このＳＤ方式では、２分木によって構成されるツリーの各リーフに受信装置を対応付け、前記ツリーのルートまたはノードと、これらから分岐したノードまたはリーフの２つの要素からなる組を規定する。そして、各組について、当該組の要素のうちルートに近い一方の要素から分岐したリーフから、他方の要素から分岐したリーフを除いたリーフに対応付けられた受信装置を要素とする複数の集合を規定する。
これにより、各受信装置は、各々要素が異なる複数の集合の要素となる。
【０００３】
また、管理装置が、各集合にラベルデータを割り当て、各受信装置に、当該受信装置が要素となる集合に割り当てたラベルデータのうち、所定のラベルデータをセキュアな状態で提供する。
そして、管理装置が、リボークしない受信装置のみを要素とする単数または複数の集合を特定し、当該集合に割り当てたそれぞれラベルデータから取得した鍵データを基に、コンテンツデータをそれぞれ暗号化して単数または複数の暗号データを生成し、これを全ての受信装置に送信すると共に、上記特定した集合を受信装置に指定する。
受信装置は、指定を受けた集合の要素である場合に、当該集合に対応するラベルデータを基に鍵データを生成し、管理装置から受信した暗号データを、当該鍵データを用いて復号する。
【０００４】
【非特許文献１】
Ｄ．Ｈａｌｅｖｙ  ａｎｄ  Ａ  Ｓｈａｍｉｒ，  ”Ｔｈｅ  ＬＣＤ  ｂｒｏａｄｃａｓｔ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅ”，  ＣＲＹＰＴＯ  ２００２，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｖｏｌ．２４４２．  ｐｐ．４７−６０，２００２
【非特許文献２】
Ｄ．Ｎａｏｒ，Ｍ．Ｎａｏｒ  ａｎｄ  Ｊ．Ｌｏｔｓｐｉｅｃｈ，”Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  ｔｒａｃｉｎｇ  ｓｃｈｅｍｅｓ  ｆｏｒ  ｓｔａｔｅｌｅｓｓ  ｒｅｃｅｉｖｅｒｓ”，  ＣＲＹＰＴＯ  ２００１．Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ．ｖｏｌ  ２１３９．ｐｐ．４１−６２，２００１．
【０００５】
【発明が解決しようとする課題】
上述した従来のＳＤ方式では、後述するように、各受信装置について、当該受信装置が割り当てられたツリー上のリーフとルートとの間に位置するルートおよび各ノードについて、当該ルートおよびノードと、これらに対してリーフ側に位置すると共に上記パス上のノードから当該パス以外の方向に直接分岐したノードまたはリーフとの組によって規定される集合に割り当てたラベルデータを、当該受信装置にセキュアな状態で提供して保持させる。受信装置は、上記規定した組の集合のうち、ラベルデータを受けていない集合のラベルデータを、上記提供を受けたラベルデータを基に演算を行って取得する。
ここで、受信装置の数をＮとした場合に、管理装置が各受信装置に提供して保持させるラベルデータの数は、下記式（６）で示される。
【０００６】
【数６】
2005012280.tif 000003
【０００７】
ところで、上述した従来のＳＤ方式では、各受信装置に保持させるラベルデータの数（データ量）をさらに削減したいという要請がある。
上記非特許文献１に記載されたＬＳＤ方式についても、同様な要請がある。
また、上述した例の他に、暗号データの復号に複数の復号用データが用いられる場合に、復号を行う処理装置が保持する復号用データの数を削減したいという要請がある。
【０００８】
本発明はかかる事情に鑑みてなされたものであり、複数の復号用データを用いて暗号データを復号する処理装置が保持する復号用データの数を削減できるデータ処理方法、そのプログラムおよびその装置と処理装置を提供することを目的とする。
また、本発明は、複数の処理装置に提供した暗号データを、指定した前記処理装置に復号用データを基に復号させる場合に、各処理装置に保持させる復号用データの数を削減できるデータ処理方法、そのプログラムおよびその装置と処理装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
上述した従来技術の問題点を解決し、上述した目的を達成するために、第１の発明のデータ処理方法は、暗号データの復号に処理装置で用いられる復号用データを生成するデータ処理方法であって、前記暗号データの復号に前記処理装置で用いられる異なる複数の第１の復号用データの各々を、前記複数の第１の復号用データのそれぞれに割当てられ前記処理装置に公開された異なる複数の固有データのうち当該第１の復号用データに割当てられた前記固有データと、所定の非公開データとを基に生成する第１の工程と、前記第１の工程で生成した前記複数の第１の復号用データを前記処理装置が前記固有データを基に生成するために用いられ、前記処理装置にセキュアな状態で提供される単数の第２の復号用データを、前記非公開データと前記固有データとを基に生成する第２の工程とを有する。
【００１０】
第１の発明のデータ処理方法の作用は以下のようになる。
先ず、第１の工程において、前記暗号データの復号に前記処理装置で用いられる異なる複数の第１の復号用データの各々を、前記複数の第１の復号用データのそれぞれに割当てられ前記処理装置に公開された異なる複数の固有データのうち当該第１の復号用データに割当てられた前記固有データと、所定の非公開データとを基に生成する。
次に、第２の工程において、前記第１の工程で生成した前記複数の第１の復号用データを前記処理装置が前記固有データを基に生成するために用いられ、前記処理装置にセキュアな状態で提供される単数の第２の復号用データを、前記非公開データと前記固有データとを基に生成する。
【００１１】
第２の発明のデータ処理方法は、複数の処理装置のうち同じ集合の要素となる前記処理装置に対して共通の復号用データを基に暗号データを復号させるデータ処理方法であって、前記処理装置の各々が複数の前記集合の要素となるように、相互に異なる前記処理装置を要素とする複数の前記集合を規定した場合に、前記複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、前記処理装置に公開される相互に異なる固有データを割り当てる第１の工程と、前記複数の集合のそれぞれについて、当該集合に前記第１の工程で割り当てた前記固有データと非公開データとを基に、当該集合の要素となる前記処理装置が前記暗号データの復号に用いる第１の復号用データを生成する第２の工程と、前記複数の処理装置の各々について、当該処理装置を要素とする前記複数の集合に前記第１の工程で割り当てられた前記固有データと非公開データとを基に、当該複数の集合について前記第２の工程でそれぞれ生成された複数の前記第１の復号用データを当該処理装置が前記固有データを基に生成するために用いられ、当該処理装置にセキュアな状態で提供される単数の第２の復号用データを生成する第３の工程とを有する。
【００１２】
第２の発明のデータ処理方法の作用は以下のようになる。
先ず、第１の工程において、複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、前記処理装置に公開される相互に異なる固有データを割り当てる。
第２の工程において、前記複数の集合のそれぞれについて、当該集合に前記第１の工程で割り当てた前記固有データと非公開データとを基に、当該集合の要素となる前記処理装置が前記暗号データの復号に用いる第１の復号用データを生成する。
第３の工程において、前記複数の処理装置の各々について、当該処理装置を要素とする前記複数の集合に前記第１の工程で割り当てられた前記固有データと非公開データとを基に、当該複数の集合について前記第２の工程でそれぞれ生成された複数の前記第１の復号用データを当該処理装置が前記固有データを基に生成するために用いられ、当該処理装置にセキュアな状態で提供される単数の第２の復号用データを生成する。
【００１３】
第３の発明のプログラムは、暗号データの復号に処理装置で用いられる復号用データを生成するデータ処理装置が実行するプログラムであって、前記暗号データの復号に前記処理装置で用いられる異なる複数の第１の復号用データの各々を、前記複数の第１の復号用データのそれぞれに割当てられ前記処理装置に公開された異なる複数の固有データのうち当該第１の復号用データに割当てられた前記固有データと、所定の非公開データとを基に生成する第１の手順と、前記第１の手順で生成した前記複数の第１の復号用データを前記処理装置が前記固有データを基に生成するために用いられ、前記処理装置にセキュアな状態で提供される単数の第２の復号用データを、前記非公開データと前記固有データとを基に生成する第２の手順とを有する。
【００１４】
第４の発明のデータ処理装置は、暗号データの復号に処理装置で用いられる復号用データを生成するデータ処理装置であって、前記暗号データの復号に前記処理装置で用いられる異なる複数の第１の復号用データの各々を、前記複数の第１の復号用データのそれぞれに割当てられ前記処理装置に公開された異なる複数の固有データのうち当該第１の復号用データに割当てられた前記固有データと、所定の非公開データとを基に生成する第１の手段と、前記第１の手段で生成した前記複数の第１の復号用データを前記処理装置が前記固有データを基に生成するために用いられ、前記処理装置にセキュアな状態で提供される単数の第２の復号用データを、前記非公開データと前記固有データとを基に生成する第２の手段とを有する。
【００１５】
第４の発明のデータ処理装置の作用は以下のようになる。
先ず、第１の手段が、暗号データの復号に前記処理装置で用いられる異なる複数の第１の復号用データの各々を、前記複数の第１の復号用データのそれぞれに割当てられ前記処理装置に公開された異なる複数の固有データのうち当該第１の復号用データに割当てられた前記固有データと、所定の非公開データとを基に生成する。
次に、第２の手段が、前記第１の手段で生成した前記複数の第１の復号用データを前記処理装置が前記固有データを基に生成するために用いられ、前記処理装置にセキュアな状態で提供される単数の第２の復号用データを、前記非公開データと前記固有データとを基に生成する。
【００１６】
第５の発明のプログラムは、複数の処理装置のうち同じ集合の要素となる前記処理装置に対して共通の復号用データを基に暗号データを復号させるデータ処理装置が実行するプログラムであって、前記処理装置の各々が複数の前記集合の要素となるように、相互に異なる前記処理装置を要素とする複数の前記集合を規定した場合に、前記複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、前記処理装置に公開される相互に異なる固有データを割り当てる第１の手順と、前記複数の集合のそれぞれについて、当該集合に前記第１の手順で割り当てた前記固有データと非公開データとを基に、当該集合の要素となる前記処理装置が前記暗号データの復号に用いる第１の復号用データを生成する第２の手順と、前記複数の処理装置の各々について、当該処理装置を要素とする前記複数の集合に前記第１の手順で割り当てられた前記固有データと非公開データとを基に、当該複数の集合について前記第２の手順でそれぞれ生成された複数の前記第１の復号用データを当該処理装置が前記固有データを基に生成するために用いられ、当該処理装置にセキュアな状態で提供される単数の第２の復号用データを生成する第３の手順とを有する。
【００１７】
第６の発明のデータ処理装置は、複数の処理装置のうち同じ集合の要素となる前記処理装置に対して共通の復号用データを基に暗号データを復号させるデータ処理装置であって、前記処理装置の各々が複数の前記集合の要素となるように、相互に異なる前記処理装置を要素とする複数の前記集合を規定した場合に、前記複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、前記処理装置に公開される相互に異なる固有データを割り当てる第１の手段と、前記複数の集合のそれぞれについて、当該集合に前記第１の手段で割り当てた前記固有データと非公開データとを基に、当該集合の要素となる前記処理装置が前記暗号データの復号に用いる第１の復号用データを生成する第２の手段と、前記複数の処理装置の各々について、当該処理装置を要素とする前記複数の集合に前記第１の手段で割り当てられた前記固有データと非公開データとを基に、当該複数の集合について前記第２の手段でそれぞれ生成された複数の前記第１の復号用データを当該処理装置が前記固有データを基に生成するために用いられ、当該処理装置にセキュアな状態で提供される単数の第２の復号用データを生成する第３の手段とを有する。
【００１８】
第６の発明のデータ処理装置の作用は以下のようになる。
先ず、第１の手段が、複数の処理装置の各々について、当該処理装置が要素となる複数の前記集合のうち、全部または一部の複数の前記集合に対して、前記処理装置に公開される相互に異なる固有データを割り当てる。
次に、第２の手段が、前記複数の集合のそれぞれについて、当該集合に前記第１の手段で割り当てた前記固有データと非公開データとを基に、当該集合の要素となる前記処理装置が前記暗号データの復号に用いる第１の復号用データを生成する。
次に、第３の手段が、前記複数の処理装置の各々について、当該処理装置を要素とする前記複数の集合に前記第１の手段で割り当てられた前記固有データと非公開データとを基に、当該複数の集合について前記第２の手段でそれぞれ生成された複数の前記第１の復号用データを当該処理装置が前記固有データを基に生成するために用いられ、当該処理装置にセキュアな状態で提供される単数の第２の復号用データを生成する。
【００１９】
第７の発明のプログラムは、復号用データを基に暗号データを復号する処理装置が実行するプログラムであって、前記暗号データと、当該暗号データを復号するための復号用データの指定を受ける第１の手順と、予め保持している複数の固有データのうち、前記第１の手順で指定された復号用データに対応する固有データを選択する第２の手順と、予め保持している復号用データと、前記第２の手順で選択した固有データとを基に、前記指定された復号用データを生成する第３の手順と、前記第３の手順で生成した前記指定された復号用データを基に、前記第１の手順で受けた前記暗号データを復号する第４の手順とを前記処理装置に実行させる。
【００２０】
第８の発明の処理装置は、復号用データを基に暗号データを復号する処理装置であって、前記暗号データと、当該暗号データを復号するための復号用データの指定を受ける第１の手段と、予め保持している複数の固有データのうち、前記第１の手段で指定された復号用データに対応する固有データを選択する第２の手段と、予め保持している復号用データと、前記第２の手段で選択した固有データとを基に、前記指定された復号用データを生成する第３の手段と、前記第３の手段で生成した前記指定された復号用データを基に、前記第１の手段で受けた前記暗号データを復号する第４の手段とを有する。
【００２１】
第８の発明の処理装置の作用は以下のようになる。
先ず、第１の手段が、暗号データと、当該暗号データを復号するための復号用データの指定を受ける。
次に、第２の手段が、予め保持している複数の固有データのうち、前記第１の手段で指定された復号用データに対応する固有データを選択する。
次に、第３の手段が、予め保持している復号用データと、前記第２の手段で選択した固有データとを基に、前記指定された復号用データを生成する。
次に、第４の手段が、前記第３の手段で生成した前記指定された復号用データを基に、前記第１の手段で受けた前記暗号データを復号する。
【００２２】
【発明の実施の形態】
第１実施形態
以下、本発明の実施形態に係わる通信システムについて説明する。
図１は、本発明の実施形態に係わる通信システム１の全体構成図である。
図１に示すように、通信システム１は、例えば、管理装置２と、１６個の受信装置ｕ１〜ｕ１６を有する。
ここで、管理装置２が、本発明のデータ処理装置に対応し、受信装置ｕ１〜ｕ１６が本発明の処理装置に対応している。
なお、受信装置ｕの数Ｎは、１６個に限定されず、複数であれば任意である。
【００２３】
通信システム１では、管理装置２から受信装置ｕ１〜ｕ１６には、例えば、無線で暗号データが送信（提供）される。
なお、本発明では、受信装置の代わりに、再生装置などの処理装置を用い、管理装置（送信装置）から処理装置への暗号データの提供を、光ディスク、磁気ディスクあるいは半導体記憶装置などの記録媒体を介して行ってもよい。
【００２４】
通信システム１では、単数または複数の受信装置ｕｍ（ｕは１〜１６のいずれかの整数）を要素とする複数の集合を規定し、同じ集合の要素となる受信装置ｕｍに共通のラベルデータＬＡＢＥＬを取得させ、当該ラベルデータを基に暗号化した暗号データを復号させる。
【００２５】
管理装置２は、受信装置ｕｍの各々について、当該受信装置ｕｍが要素となる複数の上記集合のうち、全部または一部の複数の集合に対して、相互に異なる素数データを割り当て、それを受信装置ｕｍに公開する。
また、管理装置２は、上記複数の集合のそれぞれについて、当該集合に割り当てた素数データｐと非公開データＫとを基に、当該集合の要素となる受信装置ｕｍが暗号データの復号に用いるラベルデータＬＡＢＥＬを生成する。
そして、管理装置２が、受信装置ｕｍの各々について、当該受信装置ｕｍを要素とする上記複数の集合に割り当てられた素数データと非公開データＫとを基に、当該複数の集合についてそれぞれ生成された複数の上記ラベルデータＬＡＢＥＬを当該受信装置ｕｍが素数データｐを基に生成するための単数のマスタラベルデータＭＬｍを生成する。
そして、管理装置２が、上記マスタラベルデータＭＬｍを、受信装置ｕｍにセキュアな状態に提供する。
また、管理装置２が、上記複数のラベルデータＬＡＢＥＬのうち、暗号データを復号させる受信装置ｕｍの指定に応じて選択した集合のラベルデータＬＡＢＥＬを基に暗号化した暗号データを受信装置ｕｍに提供する。
【００２６】
以下、図１に示す管理装置２および受信装置ｕ１〜ｕ１６について説明する。
〔管理装置３〕
図２は、図１に示す管理装置２のハードウェア構成図である。
図２に示すように、管理装置２は、例えば、通信部１１、メモリ１２および処理部１３を有する。
通信部１１は、処理部１３が生成したデータを無線方式で送信する。当該送信は、例えば、放送などのプッシュ（ＰＵＳＨ）方式で、ソフトウェア無線（ＳＤＲ：Ｓｏｆｔｗａｒｅ  Ｄｅｆｉｎｅｄ  Ｒａｄｉｏ）によるＳＤＲ・セキュア・ダウンロードを行う。
メモリ１２は、処理部１３によって実行されるプログラムＰＲＧ１と、プログラムＰＲＧ１の実行に用いられる種々データを記憶する。
ここで、プログラムＰＲＧ１が第５の発明のプログラムに対応している。
メモリ１２は、例えば、後述するツリー、当該ツリーのリーフへの受信装置ｕ１〜ｕ１６の割り当て、素数ｑ１，ｑ２、その積を示す公開データＭ、疑似乱数生成器Ｇ、ハッシュ関数Ｈ、非公開データＫ、ラベルデータＬＡＢＥＬ（ｉ，ｊ）、マスタラベルデータＭＬに関する情報をセキュアな状態で記憶している。
本明細書において、セキュアな状態とは、データや内容を外部から監視、改竄できない状態をいう。
また、メモリ１２は、後述するように、特別な集合に対して割り当てられた相互に異なる素数ｐ（ｊ）に関する情報を記憶する。ここで、ｊは、リーフの数をＮとした場合に、１以上（２Ｎ−１）以下の任意の整数である。
管理装置２は、積Ｍ、疑似乱数生成器Ｇ、ハッシュ関数Ｈ、素数ｐ（ｊ）に関する情報を受信装置ｕ１〜ｕ１６に公開する。
本明細書において、公開とは、例えば、管理装置２が受信装置ｕ１〜ｕ１６に情報を公開すること、管理装置２が受信装置ｕ１〜ｕ１６の各々に対して各受信装置ｕ１〜ｕ１６が後述する処理において必要とする情報を公開すること、並びに、管理装置２が受信装置ｕ１〜ｕ１６に限らず社会全般に情報を公開することのいずれか一つを示す。
【００２７】
処理部１３は、メモリ１２に記憶されたプログラムＰＲＧ１を実行し、その実行に応じて管理装置２の処理を統括して制御する。本実施形態において、管理装置２の処理は、処理部１３が実行するプログラムＰＲＧ１によって規定される。
【００２８】
処理部１３は、プログラムＰＲＧ１の実行に応じて、受信装置ｕ１〜ｕ１６に所定のラベルデータＬＡＢＥＬおよびマスタラベルデータＭＬを提供する前処理と、何れの受信装置をリボークするかに応じて選択した集合を指定する集合指定データと、リボークしない受信装置ｕ１〜ｕ１６のみが復号可能な暗号データを送信するリボケーション処理とを行う。
【００２９】
以下、管理装置２が行う各処理について説明する。
〔前処理〕
図３および図４は、管理装置２が行うリボケーション処理の前処理を説明するためのフローチャートである。
図３および図４において、ステップＳＴ７が第２の発明の第１の工程に対応し、ステップＳＴ９〜ＳＴ１１が第１の発明の第１の工程および第２の発明の第２の工程に対応し、ステップＳＴ１２が第１の発明の第２の工程および第２の発明の第３の工程に対応している。
また、図４に示すステップＳＴ１１が第２の発明のステップＳＴ５に対応し、ステップＳＴ１５が第２の発明の第６の工程に対応している。
また、第４の発明の第１の手段は処理部１３がステップＳＴ９〜ＳＴ１１を実行することで実現され、第４の発明の第２の手段は処理部１３がステップＳＴ１２を実行することで実現される。
また、第６の発明の第１の手段は処理部１３がステップＳＴ７を実行することで実現され、第６の発明の第２の手段は処理部１３がステップＳＴ９〜ＳＴ１１を実行することで実現され、第６の発明の第３の手段は処理部１３がステップＳＴ１２を実行することで実現される。
なお、以下に示す処理は、処理部１３によるプログラムＰＲＧ１の実行に応じて制御される。
【００３０】
ステップＳＴ１：
管理装置２は、先ず、例えば、図５に示す少なくともＮ個の葉を持つ２分木によって構成されるツリー２０を定義し、その情報をメモリ１２に記憶する。
ここでは簡単のため，Ｎを２のべき乗の数と仮定する。このとき，ツリー２０の葉の数がちょうどＮになるように２分木を決めることができる。
ステップＳＴ２：
管理装置２は、図５に示すように、ツリー２０の１６個のリーフの各々に１６個の受信装置ｕ１〜ｕ１６を割り当て、その情報をメモリ１２に記憶する。
【００３１】
ステップＳＴ３：
管理装置２は、各ノードについて、ノード（ｉ）の子孫であるノード（ｊ）に対応する集合Ｓ（ｉ，ｊ）を規定する。すなわち、ノード（ｉ）を本発明の第１の構成要素とし、ノード（ｊ）を本発明の第２の構成要素とする組で表される集合Ｓ（ｉ，ｊ）を規定する。
本実施形態では、リーフ、並びに２分木の分岐点（ルートを含む）をノードとする。
上記集合Ｓ（ｉ，ｊ）は、ツリー２０の２つのノード（ｉ），（ｊ）を用いて、「（ノード（ｉ）から分岐したリーフからなる集合）から（ノード（ｉ）から分岐したリーフからなる集合）を除いた集合」として規定する。
ノード（ｉ）がノード（ｊ）の先祖である（すなわち、ノードｊはノードｉと同一ではなく、ノード（ｊ）からルートへのパス上にノード（ｉ）が存在する）全てのノードの組についてこのような集合Ｓ（ｉ，ｊ）を定義する。
例えば、図５に示すツリー２０において、集合Ｓ（２，８）は、ノード「２」から分岐したリーフに割り当てられた受信装置の集合｛ｕ１，ｕ２，ｕ３，ｕ４，ｕ５，ｕ６，ｕ７，ｕ８｝から、ノード「８」から分岐したリーフに割り当てられた受信装置の集合｛ｕ１，ｕ２｝を除いた集合｛ｕ３，ｕ４，ｕ５，ｕ６，ｕ７，ｕ８｝となる。
【００３２】
ステップＳＴ４：
管理装置２は、ステップＳＴ３で規定した集合Ｓ（ｉ，ｊ）の中で、ノード（ｉ）とノード（ｊ）が親子関係になっているものを第１の特別な集合ＳＳ（ｉ，ｊ）とする。
さらに、リボークする受信装置がひとつもない場合に使用する、全受信装置ｕ１〜ｕ１６を要素とする第２の特別な集合ＳＳ（１，Φ）を定義する。
第１の特別な集合と第２の特別な集合との合計は、（２Ｎ−１）個、本実施形態では３１個となる。
【００３３】
ステップＳＴ５：
管理装置２は、２つの素数データｑ１，ｑ２を選択し、その積を示す公開データＭを生成する。
素数データｑ１，ｑ２としては、公開データＭから素数データｑ１，ｑ２を推定困難な程度に大きな値が選択される。
管理装置２は、公開データＭを受信装置ｕ１〜ｕ１６に公開する。
【００３４】
ステップＳＴ６：
管理装置２は、ハッシュ関数Ｈと擬似乱数生成器Ｇの構成を選択し、それを公開する。また、管理装置２は、これらの情報をメモリ１２に記憶する。
ハッシュ関数Ｈは，任意長の入力に対してあらかじめ定められた長さの出力を出す関数である。たとえば１２８ビット出力のハッシュ関数としてはＭＤ５が、１６０ビット出力のハッシュ関数としてはＳＨＡ−１がよく知られている。ＭＤ５は、Ａ．Ｊ．Ｍｅｎｅｚｅｓ，Ｐ．Ｃ．ｖａｎ  Ｏｏｒｓｃｈｏｔａｎｄ  Ｓ．Ａ．Ｖａｎｓｔｏｎｅ著，Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  ＣＲＣ  Ｐｒｅｓｓ  １９９７のｐ．３４７に、ＳＨＡ−１は同書のｐ．３４８にアルゴリズムが紹介されている。
また擬似乱数生成器Ｇは、図６に示すように、Ｃビットの入力に対し３Ｃビットの擬似乱数を出力する。
【００３５】
ステップＳＴ７：
管理装置２は、（２Ｎ−１）個の素数データｐ（ｊ）をランダムに選択する。
本実施形態では、Ｎ＝１６であるため、３１個の素数データｐ（ｊ）をランダムに選択する。ここで、素数データｐ（ｊ）が本発明の固有データに対応している。
ここで、固有データは、本明細書で示す複数の固有データの間で値が異なればよい。
管理装置２は、上記ランダムに選択した素数データｐ（ｊ）を、ステップＳＴ４で規定した第１の特別な集合ＳＳ（ｉ，ｊ）および第２の特別な集合ＳＳ（１，Φ）にそれぞれ割り当て、それを受信装置ｕ１〜ｕ１６に公開する。
具体的には、管理装置２は、図５に示すように、各特別な集合ＳＳ（ｉ，ｊ）に素数データｐ（ｊ）を割り当てる。ただし、ｊ＝２，．．．，２Ｎ−１である。また，素数データｐ（１）を第２の特別な集合ＳＳ（１，Φ）に割り当てる。
ステップＳＴ８：
管理装置２は、ステップＳＴ７で選択した（２Ｎ−１）個の素数データｐ（ｊ）の積を示すデータＴを生成する。
また、管理装置２は、Ｋ∈Ｚ＊ Ｍ  を満たす非公開データＫをランダムに選択する。
【００３６】
ステップＳＴ９：
管理装置２は、ステップＳＴ４で規定した第１の特別な集合ＳＳ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）を下記式（７）を基に生成する。
当該ラベルデータＬＡＢＥＬ（ｉ，ｊ）が本発明の第１の復号用データに対応している。
【００３７】
【数７】
ＬＡＢＥＬ（ｉ，ｊ）＝Ｈ（ＫＴ／ｐ（ｊ）  ｍｏｄＭ）          …（７）
【００３８】
ステップＳＴ１０：
管理装置２は、ステップＳＴ４で規定した第２の特別な集合ＳＳ（１，Φ）のラベルデータＬＡＢＥＬ（１，Φ）を下記式（８）を基に生成する。
【００３９】
【数８】
ＬＡＢＥＬ（１，Φ）＝Ｈ（ＫＴ／ｐ（１）    ｍｏｄＭ）                    …（８）
【００４０】
ステップＳＴ１１：
管理装置２は、ステップＳＴ９で生成した第１の特別な集合ＳＳ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）を基に、ノード（ｉ）を第１の構成要素とし、ノード（ｊ）から分岐したノードまたはリーフを第２の構成要素とする組で表される特別でない集合ＳのラベルデータＬＡＢＥＬを生成する。
具体的には、管理装置２は、図６および図７に示すように、ステップＳＴ９で生成した第１の特別な集合ＳＳ（ｉ，ｊ）のＣビットのラベルＬＡＢＥＬ（ｉ，ｊ）を擬似乱数生成器Ｇに入力し，その結果である３Ｃビットのデータのうち上位Ｃビット（＝ＧＬ（ＬＡＢＥＬ（ｉ，ｊ））を、ノード「ｉ」を始点としたノード「ｊ」の左側（一方）の子ノードＬＣ（ｊ）のラベルデータＬＡＢＥＬ（ｉ，ＬＣ（ｊ））とする。
また、管理装置２は、ステップＳＴ９で生成した第１の特別な集合ＳＳ（ｉ，ｊ）のラベルＬＡＢＥＬ（ｉ，ｊ）を擬似乱数生成器Ｇに入力し，その結果である３Ｃビットのデータのうち下位Ｃビット（＝ＧＲ（ＬＡＢＥＬ（ｉ，ｊ））を、ノード「ｉ」を始点としたノード「ｊ」の右側（他方）の子ノードＲＣ（ｊ）のラベルデータＬＡＢＥＬ（ｉ，ＲＣ（ｊ））とする。
そして、管理装置２は、上記生成したラベルデータＬＡＢＥＬ（ｉ，ＬＣ（ｊ）），ＬＡＢＥＬ（ｉ，ＲＣ（ｊ））を擬似乱数生成器ＧＬ，ＧＲに繰り返し入力することで、ノードｉを始点とした、ノードｊの子孫であるすべてのノードに対応するラベルデータを求める。
管理装置２は、ステップＳＴ９で生成した全ての特別な集合ＳＳ（ｉ，ｊ）のラベルデータに対して上記処理を行う。
上述したステップＳＴ７およびＳＴ８の処理により、ステップＳＴ３で規定した全ての集合Ｓ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）が生成される。
管理装置２は、集合Ｓ（ｉ，ｊ）の要素である受信装置が暗号データの復号に用いる鍵データＳＫ（ｉ，ｊ）を、例えば、ＳＫ（ｉ，ｊ）＝ＧＭ（ＬＡＢＥＬ（ｉ，ｊ））によって生成する。
すなわち、管理装置２は、ステップＳＴ７で生成した第１の特別な集合ＳＳ（ｉ，ｊ）のラベルＬＡＢＥＬ（ｉ，ｊ）を擬似乱数生成器Ｇに入力し、その結果である３Ｃビットのデータのうち中位Ｃビット（＝ＧＭ（ＬＡＢＥＬ（ｉ，ｊ））を、集合Ｓ（ｉ，ｊ）の要素である受信装置が暗号データの復号に用いる鍵データＳＫ（ｉ，ｊ）とする。
【００４１】
ステップＳＴ１２：
管理装置２は、受信装置ｕ１〜ｕ１６のそれぞれについて、当該受信装置ｕｍが要素となる第１の特別な集合ＳＳ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）と第２の特別な集合ＳＳ（１，Φ）のラベルデータＬＡＢＥＬ（１，Φ）のマスタラベルデータＭＬｍを下記式（９）を基に生成する。
ここで、マスタラベルデータＭＬｍが本発明の第２の復号用データに対応している。
下記式（９）において、データｗｍは、受信装置ｕｍが要素となる第１の特別な集合ＳＳ（ｉ，ｊ）に割り当てられた素数データｐ（ｊ）と、第２の特別な集合ＳＳ（１，Φ）に割り当てられた素数データｐ（１）との積を示している。
【００４２】
０
【数９】
ＭＬｍ＝ＫＴ／ｗｍ  ｍｏｄＭ                      …（９）
【００４３】
図５に示す例では、ｗ４は、ｐ（１）・ｐ（３）・ｐ（５）・ｐ（８）・ｐ（１８）となる。
また、受信装置ｕｍの特別な集合のラベルデータＬＡＢＥＬ（１，３），ＬＢＡＬＥ（２，５），ＬＡＢＥＬ（４，８），ＬＡＢＥＬ（９，１８），ＬＡＢＥＬ（１，Φ）の５つがマスタラベルデータＭＬｍから生成される。
【００４４】
ステップＳＴ１３：
管理装置２は、全ての受信装置ｕ１〜ｕ１６の各々に対して、当該受信装置が要素となる集合に対応するラベルデータを選択する。
具体的には、管理装置２は、受信装置ｕｍについて、受信装置ｕｍ（ｍは１〜１６の整数）が割り当てられたリーフからルートに至るパスｐａｔｈ（ｍ）上の内部のノード「ｉ」を始点とし、当該リ−フからノード「ｉ」までのパスから直接分岐した（枝分かれした）ノード「ｊ」に対応する集合Ｓ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）と、上記の第２の特別な集合ＳＳ（１，Φ）に対応するラベルデータＬＡＢＥＬ（１，Φ）を選択する。
図５に示すツリー２０の例では、管理装置２は、受信装置ｕ４について、図８の「従来のＳＤ」の欄に示すように、ラベルデータＬＡＢＥＬ（１，３），ＬＡＢＥＬ（１，５），ＬＡＢＥＬ（１，８），ＬＡＢＥＬ（１，１８），ＬＡＢＥＬ（２，５），ＬＡＢＥＬ（２，８），ＬＡＢＥＬ（２，１８），ＬＡＢＥＬ（４，８），ＬＡＢＥＬ（４，１８），ＬＡＢＥＬ（９，１８），ＬＡＢＥＬ（１，Φ）の１１個のラベルデータＬＡＢＥＬ（ｉ，ｊ）を選択する。
これらの１１個のラベルデータＬＡＢＥＬ（ｉ，ｊ）のち、図９に示すように、ＬＡＢＥＬ（１，３），ＬＡＢＥＬ（２，５），ＬＡＢＥＬ（４，８）およびＬＡＢＥＬ（９，１８）が第１の集合ＳＳ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）となる。
【００４５】
ステップＳＴ１４：
管理装置２は、各受信装置ｕｍについて、ステップＳＴ１３で選択したラベルデータＬＡＢＥＬ（ｉ，ｊ）のうち，前述した第１の特別な集合および第２の特別な集合に対応するラベルデータＬＡＢＥＬ（ｉ，ｊ）を除いたラベルデータＬＡＢＥＬ（ｉ，ｊ）を選択する。
図５に示すツリー２０の例では、管理装置２は、受信装置ｕ４について、ラベルデータＬＡＢＥＬ（１，５），ＬＡＢＥＬ（１，８），ＬＡＢＥＬ（１，１８），ＬＡＢＥＬ（２，８），ＬＡＢＥＬ（２，１８），ＬＡＢＥＬ（４，１８）を選択する。
【００４６】
ステップＳＴ１５：
管理装置２は、各受信装置ｕｍについて、ステップＳＴ１４で選択したラベルデータＬＡＢＥＬ（ｉ，ｊ）と、ステップＳＴ１２で導出したマスタラベルデータＭＬｍとを、当該受信装置ｕｍにセキュアな状態で提供する。
受信装置ｕｍは、当該受けたラベルデータＬＡＢＥＬ（ｉ，ｊ）とマスタラベルデータＭＬｍとをセキュアな状態で記憶する。
受信装置ｕ４の例では、図８に示す「第１実施形態」の欄のように、ラベルデータＬＡＢＥＬ（１，５），ＬＡＢＥＬ（１，８），ＬＡＢＥＬ（１，１８），ＬＡＢＥＬ（２，８），ＬＡＢＥＬ（２，１８），ＬＡＢＥＬ（４，１８）と、マスタラベルデータＭＬ４との合計７個のラベルデータを、受信装置ｕ４にセキュアな状態で提供する。
このように、通信システム１によれば、従来のＳＤ方式に比べて、管理装置２から受信装置ｕｍに提供して記憶させるラベルデータの数（データ量）を削減できる。
【００４７】
〔リボケーション処理〕
管理装置２は、上述した前処理を行った後に、例えば、コンテンツデータを暗号化した暗号データを受信装置ｕｍに送信する際に、当該リボケーション処理を行う。
なお、以下に示す処理は、処理部１３によるプログラムＰＲＧ１の実行に応じて制御される。
図１０は、管理装置２が行うリボケーション処理を説明するためのフローチャートである。
図１０に示す処理は第１の発明の第３の工程に対応している。
また、図１０に示すステップＳＴ２６が第２の発明の第４の工程に対応している。
ステップＳＴ２１：
管理装置２は、受信装置ｕ１〜ｕ１６のうち、リボークしない受信装置を特定する（暗号データを復号できる受信装置を指定する）。
ステップＳＴ２２：
管理装置２は、ステップＳＴ２１で特定したリボークしない受信装置を要素とし、かつ、リボークする受信装置を要素としない集合のうち、リボークしない受信装置がいずれかの集合の要素となりかつ、ノード（ｉ）がルートに最も近くなるような単数または複数の集合Ｓ（ｉ，ｊ）を特定する。
管理装置２は、例えば、図１１に示すように、受信装置ｕ２，ｕ１１，ｕ１２をリボークする場合には、集合Ｓ（２，１７）およびＳ（３，１３）を特定する。
【００４８】
ステップＳＴ２３：
管理装置２は、ステップＳＴ２２で特定した集合Ｓ（ｉ，ｊ）を指定する集合指定データを生成する。当該集合指定データは、例えば、集合Ｓ（ｉ，ｊ）の識別データを用いて、当該集合Ｓ（ｉ，ｊ）を指定する。
当該集合指定データが、本発明の指定データに対応し、集合の指定が本発明の復号用データに対応するラベルデータＬＡＢＥＬの指定になる。
ステップＳＴ２４：
管理装置２は、ステップＳＴ２３で特定した集合Ｓ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）を用いて、鍵データＳＫ（ｉ，ｊ）（＝ＧＭ（ＬＡＢＥＬ（ｉ，ｊ）））を生成する。
【００４９】
ステップＳＴ２５：
管理装置２は、送信するデータを、ステップＳＴ２４で生成した鍵データＳＫ（ｉ，ｊ）のそれぞれで暗号化して暗号データを生成する。
図１１に示す例では、管理装置２は、上記データを鍵データＳＫ（２，１７）で暗号化した暗号データと、上記データを鍵データＳＫ（３，１３）で暗号化した暗号データとの２つの暗号データを生成する。
ステップＳＴ２６：
管理装置２は、ステップＳＴ２３で生成した指定データと、ステップＳＴ２５で生成した暗号データとを、図２に示す通信部１１を介して受信装置ｕ１〜ｕ１６に送信する。
一例として、前述した「前処理」はシステム立ち上げ時の一度だけ行い，「リボケーション処理」は送信したい情報がある度に（たとえばコンテンツを放送するとかＲＯＭディスクを生産する度に）行う。受信装置もシステム立ち上げ時または自身がシステムに参加するときにラベルを受け取り、下記の受信処理を繰り返して行う．
【００５０】
〔受信装置ｕ１〜ｕ１６〕
図１２は、図１に示す受信装置ｕｍのハードウェア構成図である。
図１２に示すように、受信装置ｕｍは、例えば、通信部５１、メモリ５２および処理部５３を有する。
通信部５１は、前述したように管理装置２が送信した暗号データおよび集合指定データを受信する。
メモリ５２は、処理部５３によって実行されるプログラムＰＲＧ２と、プログラムＰＲＧ２の実行に用いられる種々データを記憶する。
ここで、プログラムＰＲＧ２が第５の発明のプログラムに対応している。
例えば、メモリ５２は、例えば、図４に示すツリー２０、ツリー２０の何れのリーフに受信装置ｕｍが割り当てられているかを示す情報、素数データｐ（ｊ）、並びにその割り当て情報、公開データＭ、疑似乱数生成器Ｇに関する情報、ハッシュ関数Ｈに関する情報、図４に示すステップＳＴ１５で管理装置２から受けたマスタラベルデータＭＬｍおよびラベルデータＬＡＢＥＬを記憶している。
【００５１】
処理部５３は、メモリ５２に記憶されたプログラムＰＲＧ２を実行し、その実行に応じて受信装置ｕｍの処理を統括して制御する。本実施形態において、受信装置ｕｍの処理は、処理部５３が実行するプログラムＰＲＧ２によって規定される。
【００５２】
処理部５３は、プログラムＰＲＧ２の実行に応じて、集合指定データによって指定された集合のラベルデータＬＡＢＥＬの生成、マスタラベルデータＭＬｍの生成、マスタラベルデータＭＬｍからラベルデータＬＡＢＥＬの生成、並びにラベルデータＬＡＢＥＬから鍵データＳＫの生成、鍵データＳＫを用いた暗号データの復号などの処理を行う。
【００５３】
図１３は、図１２に示す受信装置ｕｍの処理を説明するためのフローチャートである。
図１３において、ステップＳＴ３３が第２の発明の第８の工程に対応し、ステップＳＴ３４が第２の発明の第９の工程に対応している。
ステップＳＴ３１：
受信装置ｕｍの通信部５１は、管理装置２から、前述した集合指定データと、単数または複数の暗号データを受信する。
ステップＳＴ３２：
受信装置ｕｍの処理部５３は、当該受信装置ｕｍが、ステップＳＴ３１で受信した集合指定データが指定する単数または複数の集合のいずれかの要素であるか否かを判断し、要素であると判断するとステップＳＴ３３に進み、そうでない場合には処理を終了する。
なお、受信装置ｕｍは、管理装置２によってリボークされない場合に、管理装置２からの集合指定データが示す単数または複数の集合のうち一つの集合の要素となっている。
【００５４】
ステップＳＴ３３：
受信装置ｕｍの処理部５３は、後述するように、鍵データＳＫ（ｉ，ｊ）を生成する。
ステップＳＴ３４：
受信装置ｕｍは、ステップＳＴ３３で生成した鍵データＳＫ（ｉ，ｊ）を用いて、自らが要素となる集合に対応した暗号データを復号する。
【００５５】
以下、図１３に示す鍵データの生成処理（ステップＳＴ３３）を詳細に説明する。
図１４は、図１３に示すステップＳＴ３３の処理を説明するためのフローチャートである。
また、第８の発明の第１の手段は処理部５３が図１４に示すステップＳＴ４１を実行して実現され、第２の手段および第３の手段は処理部５３がステップＳＴ４６，ＳＴ４７，ＳＴ４８を実行して実現され、第４の手段は処理部５３が図１３に示すステップＳＴ３４を実行して実現される。
【００５６】
ステップＳＴ４１：
受信装置ｕｍは、集合指定データが指定する自らが要素となる集合Ｓ（ｉ，ｊ）が、第１あるいは第２の特別な集合であるか否かを判断し、特別な集合であると判断するとステップＳＴ４８に進み、そうでない場合にはステップＳＴ４２に進む。
ステップＳＴ４２：
受信装置ｕｍは、集合指定データが指定する自らが要素となる集合Ｓ（ｉ，ｊ）のラベルデータＬＡＢＥＬが、メモリ５２に記憶されているか否かを判断し、記憶されていると判断すると、ステップＳＴ４３に進み、そうでない場合にはステップＳＴ４４に進む。
ステップＳＴ４３：
受信装置ｕｍの処理部５３は、上記指定された集合Ｓ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）をメモリ５２から読み出し、これを擬似乱数生成器Ｇに入力し、その結果の中位ＣビットＧＭ（ＬＡＢＥＬ（ｉ，ｊ））を、鍵データＳＫ（ｉ，ｊ）とする。
【００５７】
ステップＳＴ４４：
受信装置ｕｍは、集合指定データが指定する自らが要素となる集合Ｓ（ｉ，ｊ）のラベルデータＬＡＢＥＬを得るのに第１または第２の特別な集合のラベルデータＬＡＢＥＬが必要か否かを判断し、必要であると判断するとステップＳＴ４６に進み、そうでない場合にはステップＳＴ４５に進む。
ステップＳＴ４５：
受信装置ｕｍの処理部５３は、メモリ５２から、上記指定された集合Ｓ（ｉ，ｊ）を表すノード（ｉ）および（ｊ）の，ノード（ｊ）からノード（ｉ）へのパス上に、受信装置ｕｍがラベルＬＡＢＥＬ（ｉ，ｋ）を持つノード（ｋ）を見つけ，当該ラベルデータＬＡＢＥＬ（ｉ，ｋ）をメモリ１２から読み出し、これを擬似乱数生成器Ｇに入力し、必要に応じてその結果を繰り返し擬似乱数生成器Ｇに入力して、ラベルデータＬＡＢＥＬ（ｉ，ｊ）を生成する。
そして、処理部５３は、上記生成したラベルデータＬＡＢＥＬ（ｉ，ｊ）を擬似乱数生成器Ｇに入力し、その結果の中位ＣビットＧＭ（ＬＡＢＥＬ（ｉ，ｊ））を、鍵データＳＫ（ｉ，ｊ）とする。
【００５８】
ステップＳＴ４６：
受信装置ｕｍの処理部５３は、指定された集合Ｓ（ｉ，ｊ）のラベルデータＬＡＢＥＬ（ｉ，ｊ）を得るのに必要な特別な集合ＳＳ（ｉ，ｋ）を特定し、当該特定した集合に割り当てられた素数データｐ（ｋ）をメモリ１２から読み出す。
処理部５３は、当該読み出した素数データｐ（ｋ）と、メモリ１２から読み出したマスタラベルデータＭＬｍおよび公開データＭと、ハッシュ関数Ｈと、データＷｍとを用いて、下記式（１０）を演算して当該特別な集合のラベルデータＬＡＢＥＬ（ｉ，ｋ）を生成する。
このとき、処理部５３は、メモリ５２から読み出した公開された素数データｐ（ｊ）のうち受信装置ｕｍが要素となる第１の特別な集合ＳＳ（ｉ，ｊ）に割当てられた素数データｐ（ｊ）と、第２の特別な集合ＳＳ（１，Φ）に割当てられた素数データｐ（１）との積を演算等してデータｗｍを得る。
【００５９】
【数１０】
ＬＡＢＥＬ（ｉ，ｋ）＝Ｈ（ＭＬｍｗｍ／ｐ（ｋ）  ｍｏｄＭ）…（１０）
【００６０】
ステップＳＴ４７：
受信装置ｕｍの処理部５３は、ステップＳＴ４６で生成した特別な集合のラベルデータＬＡＢＥＬ（ｉ，ｋ）を擬似乱数生成器Ｇに入力し、必要に応じてその結果を繰り返し擬似乱数生成器Ｇに入力して、ラベルデータＬＡＢＥＬ（ｉ，ｊ）を生成する。
そして、処理部５３は、上記生成したラベルデータＬＡＢＥＬ（ｉ，ｊ）を擬似乱数生成器Ｇに入力し、その結果の中位ＣビットＧＭ（ＬＡＢＥＬ（ｉ，ｊ））を、鍵データＳＫ（ｉ，ｊ）とする。
【００６１】
ステップＳＴ４８：
受信装置ｕｍの処理部５３は、指定された特別な集合ＳＳ（ｉ，ｊ）に割り当てられた素数データｐ（ｊ）をメモリ１２から読み出す。
処理部５３は、当該読み出した素数データｐ（ｊ）と、メモリ１２から読み出したマスタラベルデータＭＬｍおよび公開データＭと、ハッシュ関数Ｈとを用いて、下記式（１１）を演算して当該特別な集合のラベルデータＬＡＢＥＬ（ｉ，ｊ）を生成する。
【００６２】
【数１１】
ＬＡＢＥＬ（ｉ，ｊ）＝Ｈ（ＭＬｍｗｍ／ｐ（ｊ）  ｍｏｄＭ）…（１１）
【００６３】
受信装置ｕｍの処理部５３は、当該生成した特別な集合のラベルデータＬＡＢＥＬ（ｉ，ｊ）を擬似乱数生成器Ｇに入力し、その結果の中位ＣビットＧＭ（ＬＡＢＥＬ（ｉ，ｊ））を、鍵データＳＫ（ｉ，ｊ）とする。
【００６４】
以下、図１１を例に説明する。
図１１に示すように、受信装置ｕ２，ｕ１１，ｕ１２がリボークされ、集合Ｓ（２，１７），Ｓ（３，１３）に対応する鍵データＳＫ（２，１７），ＳＫ（３，１３）で暗号化された暗号データを管理装置２が送信する場合を考える。
この場合には、受信装置ｕ４は，ラベルデータＬＡＢＥＬ（１，５），ＬＡＢＥＬ（１，８），ＬＡＢＥＬ（１，１８），ＬＡＢＥＬ（２，８），ＬＡＢＥＬ（２、１８），ＬＡＢＥＬ（４，１８）の６個のラベルデータと、マスタラベルデータＭＬ４をメモリ５２に記憶する。
【００６５】
受信装置ｕ４は、集合Ｓ（２，１７）について、ノード（１７）の先祖であるノード（８）を用いたラベルデータＬＡＢＥＬ（２，８）を直接保持しているため、これに擬似乱数生成器Ｇを必要な回数だけ適用することで鍵データＳＫ（２，１７）を得ることができる。
一方、受信装置ｕ５は、ＬＡＢＥＬ（１，４），ＬＡＢＥＬ（１，１１），ＬＡＢＥＬ（１，２１），ＬＡＢＥＬ（２，１１），ＬＡＢＥＬ（２，２１），ＬＡＢＥＬ（５，２１）の６個のラベルデータとマスタラベルデータＭＬ５を、メモリ１２に記憶している。
受信装置ｕ５は、集合Ｓ（２，１７）に対し、ノード（１７）の先祖であるノード（ｋ）を用いたラベルデータＬＡＢＡＬ（２，ｋ）をメモリ１２に保持していない。
そのため、受信装置ｕ５は、メモリ１２に記憶しているマスタラベルデータＭＬ５から、ノード（１７）の先祖であるノード（４）に対応したラベルデータＬＡＢＥＬ（２，４）を生成し、これに擬似乱数生成器Ｇを必要な回数だけ適用することで鍵データＳＫ（２，１７）を得る。
【００６６】
なお、リボークすべき受信装置ｕｍが１台もなく、集合として第２の特別な集合ＳＳ（１，Φ）が使用されていた場合、受信装置ｕｍは、「ＬＡＢＥＬ（１，Φ）＝Ｈ（ＭＬｍｗｍ／ｐ（１）  ｍｏｄＭ）」の処理によりマスターラベルＭＬｍからラベルデータＬＡＢＡＬ（１，Φ）を計算し、それを擬似乱数生成器Ｇに入力して出力の中央部分のＣビットを求める。
すなわち、鍵データＳＫ（１，Φ）を、ＧＭ（ＬＡＢＡＬ（１，Φ））により求め、これを基に暗号データを復号する。
【００６７】
以上説明したように、通信システム１によれば、図４に示すステップＳＴ１２，ＳＴ１５を用いて説明したように、特別な集合の複数のラベルデータＬＡＢＥＬを生成するための単数のマスタラベルデータＭＬｍを生成し、これを受信装置ｕｍにセキュアな状態で提供して保持させることで、受信装置ｕｍが記憶（保持）するラベルデータおよびマスタラベルデータの数を、従来のＳＤ方式に比べて削減できる。
また、通信システム１によれば、受信装置ｕｍは、自らが保持するマスタラベルデータＭＬｍを基に図１４に示すステップＳＴ４６，ＳＴ４８を用いて説明したように、特別な集合の複数のラベルデータを適切に取得できる。そのため、リボークされない受信装置ｕｍは、管理装置２から受信した暗号データを当該鍵データを基に適切に復号できる。
その一方、マスタラベルデータＭＬｍを保持しない他の受信装置は、当該マスタラベルデータＭＬｍに対応したラベルデータＬＡＢＥＬを取得できない。
【００６８】
第２実施形態
本実施形態の管理装置２ａおよび受信装置ｕｍａは、以下に示す処理以外は、第１実施形態の管理装置２および受信装置ｕｍと同じである。
以下、上述したＳＤ方式を基礎としたＬＳＤ（Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ）方式に本発明を適用した場合を例示する。
ＬＳＤ方式には、Ｂａｓｉｃ（基本）方式と、その拡張であるＧｅｎｅｒａｌ（一般化）方式がある。
ここではＢａｓｉｃ＿ＬＳＤに本発明を適用した場合について説明する。
本実施形態の通信システムは、上述した第１の実施形態の通信システムにおいて、特別レベル（Ｓｐｅｃｉａｌ  Ｌｅｖｅｌ）と、特別レベル間の階層であるレイヤという新たな概念を取り入れたものである。
例えば、第１実施形態で説明したツリー２０内で、図１５に示すように、特定の階層を特別レベルとして定義する。
本実施形態では、特別ラベルデータは１種類だけであるが、後述する第３実施形態においては重要度の異なる複数の特別レベルを用いる。
ここで、簡単のため、ｌｏｇ１／２  Ｎ（Ｎは受信装置ｕｍの数）は整数であるとする。
【００６９】
本実施形態では、図１５に示すように、ツリー２０のルートからリーフに至るまでのそれぞれの階層のうち、ルートとリーフのレベルを含む、ｌｏｇ１／２  Ｎごとの階層を特別レベルと規定する。
そして、隣り合う２つの特別レベルに挟まれた単数または複数の階層（両方の特別レベルを含む）を、レイヤと呼ぶ。
図１５の例では、ルートの階層、ノードｋを含む階層、リーフの階層が特別レベルであり、ルートの階層とノードｉを含む階層とノードｋを含む階層が１つのレイヤを構成する。またノードｋを含む階層とノードｊを含む階層とリーフを含む階層が別のレイヤを構成する。
【００７０】
本実施形態では、管理装置２ａは、第１実施形態で規定した集合Ｓ（ｉ，ｊ）のうち、ノードｉとノードｊが同一レイヤにあるか、もしくはノードｉが特別レベルにあるものだけを規定し、当該規定した集合Ｓ（ｉ，ｊ）についてのみ、図３および図４を用いて説明したようにマスタラベルデータＭＬｍおよびラベルデータＬＡＢＥＬの生成を行う。
すなわち、本実施形態では、第１実施形態で規定した集合のうちのいくつかは規定されなくなるが、この規定されない集合は、本実施形態で規定される集合の高々２つの和集合で表すことができる。
例えば、図１５の例では、集合Ｓ（ｉ，ｊ）は、本実施形態では規定されないが、ノードｉからノードｊへのパス上の、ノードｉに最も近い特別レベル上のノード（ノードｋ）を用いて、Ｓ（ｉ，ｊ）＝Ｓ（ｉ，ｋ）∪Ｓ（ｋ，ｊ）と表すことができる。
前述した第１実施形態の管理装置２は、特定（選択）した集合Ｓ（ｉ，ｊ）について、それに対応する鍵データＳＫ（ｉ，ｊ）を用いて暗号化した１つの暗号データを生成して受信装置ｕｍに提供したが、本実施形態の管理装置２ａは、集合Ｓ（ｉ，ｋ）とＳ（ｋ，ｊ）に対応する集合キーＳＫ（ｉ，ｋ），ＳＫ（ｋ，ｊ）を用いてそれぞれ暗号化した２つの暗号データを生成して受信装置ｕｍａに送信（提供）する。
【００７１】
これにより、管理装置２ａでは、送信する暗号データの数（通信量）は、第１の実施形態の管理装置２の高々２倍に増加するが、各受信装置ｕｍａが保持するラベルデータの数を第１実施形態の受信装置ｕｍに比べて減らすことができる。
【００７２】
管理装置２ａでは、擬似乱数生成器Ｇを用いてラベルデータＬＡＢＥＬ（ｉ，ｊ）を順に生成する過程で、ノード（ｉ）が特別レベルにない場合、ノード（ｉ）の一つ下の特別レベルよりも下のノードをｊとするラベルデータは利用されないので、当該一つ下の特別レベルまででラベルデータの生成を止める。
管理装置２ａは、前述した前処理において、ラベルデータを各受信装置ｕｍにセキュアな状態で提供する場合にも、上述した条件で生成したラベルデータのなかから選択して受信装置ｕｍａに提供する。
【００７３】
図１６および図１７は、図９のツリー２０を基に受信装置ｕｍが割り当てられている場合に、本実施形態の受信装置ｕ４ａが記憶するラベルデータＬＡＢＥＬを説明するための図である。
図１７および図１８に示すように、従来のＢＡＳＩＣ＿ＬＳＤを採用した場合には、提供して記憶させたラベルデータＬＡＢＥＬ（１，３），ＬＡＢＥＬＥ（１，５），ＬＡＢＥＬ（１，８），ＬＡＢＥＬ（１，１８），ＬＡＢＥＬ（２，５），ＬＡＢＥＬ（４，８），ＬＡＢＥＬ（４，１８），ＬＡＢＥＬ（９，１８）と特別なラベルの合計９個のラベルデータを受信装置ｕ４が保持する必要がある。
これに対して、本実施形態の管理装置２ａでは、上述したようにマスタラベルデータＭＬｍを用いることで、ノード（ｉ），（ｊ）が親子関係にある第１の特別な集合のラベルデータＬＡＢＥＬと、前述した第２の特別な集合のラベルデータＬＡＢＥＬ（１，Φ）を、一つのマスタラベルデータＭＬｍから受信装置ｕｍが導出する。
そのため、管理装置２ａは、受信装置ｕ４ａに対して、前処理において、図１８に示すように、ラベルデータＬＡＢＥＬ（１，５），ＬＡＢＥＬ（１，８），ＬＡＢＥＬ（１，１８），ＬＡＢＥＬ（４，１８）と、マスタラベルデータＭＬ４の合計５個のラベルデータを提供して保持させる。
【００７４】
以下、受信装置ｕｍａの数をＮとした場合に、従来のＢＡＳＩＣ＿ＬＳＤに比べて、本実施形態において受信装置ｕｍａに記憶させるラベルデータの数を削減できることを説明する。
すなわち、ノード（ｉ），（ｊ）が親子関係になるようなラベルデータＬＡＢＥＬ（ｉ，ｊ）を各受信装置ｕｍａがいくつ保持すべきかを考える。
ノード（ｉ），（ｊ）が親子関係になっているときには，以下の３つの場合が考えられる。
（Ａ）ノード（ｉ）が特別レベルにある。
（Ｂ）ノード（ｊ）が特別レベルにある。
（Ｃ）ノード（ｉ），（ｊ）の双方が特別レベルにない。
【００７５】
上記（Ａ）〜（Ｃ）のいずれの場合も、ノード（ｉ），（ｊ）が親子関係にある（つまり，ツリー上で隣り合っている）以上、ノード（ｉ），（ｊ）は同一レイヤに存在する。すなわち、集合Ｓ（ｉ，ｊ）はＢａｓｉｃ＿ＬＳＤ方式で定義されるための条件を満たしている。
つまり、このような集合はＢａｓｉｃ＿ＬＳＤで定義され使用されるため、受信装置ｕｍａはそれに対応するＬＡＢＥＬ（ｉ，ｊ）を保持しておく必要がある。
このようなノード（ｉ），（ｊ）は、受信装置ｕｍａについては、ノード（ｉ）の位置がツリーの高さ分（すなわち，受信装置が割り当てられたリーフからルートへのパス上の、リーフを除くノードすべて）あり、ノード（ｉ）を決めればノード（ｊ）がただ１つ決まる（ノード（ｉ）の子で、上記のパス上にないノード）ため、ツリー２０の高さ分，すなわちｌｏｇＮ個だけ存在する。
【００７６】
本実施形態では、受信装置ｕｍａが、これらのｌｏｇＮ個の第１の特別なラベルデータと１つの第２の特別なラベルデータを、第１実施形態で説明したように、マスタラベルデータＭＬｍから生成できるように規定し、このマスタラベルデータＭＬを受信装置ｕｍａにセキュアな状態で提供して保持する。
これにより、受信装置ｕｍａが保持するラベルデータの数をｌｏｇＮ（＝ｌｏｇＮ＋１−１）だけ削減できる。
上述のように、従来のＢａｓｉｃ＿ＬＳＤ方式では受信装置ｕｍａが保持するラベルデータの総数はｌｏｇ３／２Ｎ＋１であるが、本実施形態では、受信装置ｕｍａが保持するラベルデータの数を、ｌｏｇ３／２Ｎ−ｌｏｇＮ＋１に削減できる。
【００７７】
第３実施形態
本実施形態の管理装置２ｂおよび受信装置ｕｍｂは、以下に示す処理以外は、第１および第２実施形態の管理装置２，２ａおよび受信装置ｕｍ，ｕｍａと同じである。
本実施形態では、Ｇｅｎｅｒａｌ＿ＬＳＤに本発明を適用した場合を説明する。
上述した従来のＢａｓｉｃ＿ＬＳＤ方式では，１種類の特別レイヤを用いたが、本実施形態では、Ｇｅｎｅｒａｌ＿ＬＳＤと同様に、重要度の異なる複数の特別レベルを用いる。
すなわち、前述したように受信装置ｕｍｂをリーフに対応付けたツリー２０において、ルートからノード（ｉ）を経てノード（ｊ）に至るパスを１本のグラフとして考える。
ツリー２０のルートとノード（ｊ）が端点となり、ツリー２０のノードがグラフのノードとなり，端点以外のノードのひとつがノード（ｊ）となっている。このグラフでは，各ノードはルートからの距離で表される。この距離は，ｄ桁のｂ進数（ただしｂ＝Ｏ（ｌｏｇ１／ｄＮ）で表される。
たとえば、ルートは「０．．．００」と表され、その隣のノード（ツリー２０において、ルートの子ノードであるノード）は「０．．．０１」と表される。
【００７８】
この場合に、第１実施形態で規定した集合Ｓ（ｉ，ｊ）は、規定された変換（ノードからノードへの遷移）を組み合わせることで、ノード（ｉ）からノード（ｊ）への最終的な遷移であると考える。
上記規定された変換は上記集合に対応し、最終的な遷移に要する個々の遷移が、集合Ｓ（ｉ，ｊ）を分割して表すのに必要な集合を示す。
【００７９】
例えば、ノード（ｉ），（ｋ１），（ｋ２），（ｋ（ｄ−１）），（ｊ）がこの順で、ツリー２０のパス上に存在する場合に、集合Ｓ（ｉ，ｊ）は、本実施形態では、下記式（１２）に示すように、高々ｄ個の集合の和集合で表される。
【００８０】
【数１２】
2005012280.tif 000004
【００８１】
本実施形態では、ノード（ｉ）が上記のグラフにおいて、（ｘ）ａ（０）と表されるとき、（ｘ＋１）０（０）あるいは（ｘ）（ａ’）（ｙ）で表されるノード（ｊ）への遷移を全て規定できる。
ここで、ａは非ゼロの数字のうち１番右にある数字、（ｘ）は任意の数字列、（０）はゼロの列、ａ’≧ａ、（ｙ）は（０）と同じ長さの任意の数字列である。
【００８２】
すなわち、第２実施形態は、当該第３実施形態においてｄ＝２、（一番右の）最終桁が０である２桁の数字で表されるレベルを特別レベルとしたものである。
本実施形態では、ノード（ｉ）を表す数字における一番右のゼロの列の桁数が、そのレベルの重要度を表し、本実施形態で定義される集合Ｓ（ｉ，ｊ）を表すノード（ｊ）は、ノード（ｉ＋１）からノード（ｉ）よりも重要度の高い最初のノードまでのいずれのノード（両端のノードを含む）にもなる可能性がある。
例えば、ｉ＝８２５１９７，ｊ＝８６４５６３とすると，ノード（ｉ）からノード（ｊ）への遷移、すなわち集合Ｓ（ｉ，ｊ）は、「８２５９１７→８２５９２０→８２６０００→８３００００→８６４５６３」という上述した４つの遷移によって表すことができる。
すなわち，ｋ１＝８２５９２０，ｋ２＝８２６０００，ｋ３＝８３００００とおけば、下記式（１３）が成り立つ。
【００８３】
【数１３】
2005012280.tif 000005
【００８４】
本実施形態では、管理装置２ｂは、サブセットＳ（ｉ，ｊ）の要素となる受信装置ｕｍｂに復号させる暗号データとして、集合Ｓ（ｉ，ｋ１），Ｓ（ｋ１，ｋ２），Ｓ（ｋ２，ｋ３），Ｓ（ｋ３，ｊ）に対応するラベルデータＬＡＢＥＬから生成した鍵データを用いて暗号化した４つの暗号データを生成および送信する。
【００８５】
本実施形態によれば、受信装置ｕｍｂが保持すべきラベルデータの数は、パラメータｄが大きくなるに従って減少し、最終的には下記式（１４）となる。
このとき，送信すべき暗号データの数は、ｄ（２ｒ−１）となる。ここで、ｒはリボークする受信装置の数を示している。
【００８６】
【数１４】
2005012280.tif 000006
【００８７】
本実施形態において、第１および第２実施形態と同様に、管理装置２ｂは、受信装置ｕｍｂに対して、受信装置ｕｍｂが復号に使用するラベルデータＬＡＢＥＬのうち、ノード（ｉ），（ｊ）が親子関係になっている特別な集合ＳＳ（ｉ，ｊ）に対応する複数のラベルデータＬＡＢＡＬ（ｉ，ｊ）を導出するための単数のマスタラベルデータＭＬｍをセキュアな状態で提供して保持させる。
これは、ノード（ｉ）としてどんな値をとっても、その子ノード（ｊ）、すなわちノード（ｉ＋１）への遷移は、上述した遷移の条件に当てはまるためである。
すなわち、本実施形態においても、第１および第２実施形態の場合と同様に、受信装置ｕｍについて、当該受信装置ｕｍが利用するラベルデータのうちノード（ｉ），（ｊ）が親子関係になっているものはｌｏｇＮ個ある。
管理装置２ｂは、これらｌｏｇＮ個の第１の特別なラベルデータと１つの第２の特別なラベルデータを、第１実施形態と同様に、１つのマスタラベルデータＭＬｍから作り出し、当該マスタラベルデータＭＬｍを受信装置ｕｍｂに保持させることで、受信装置ｕｍｂが保持するラベルデータを、従来のＧｅｎｅｒａｌ＿ＬＳＤに比べてｌｏｇＮ個削減できる。
【００８８】
本発明は上述した実施形態には限定されない。
上述した実施形態では、２分木を基に構成されたツリーのリーフに受信装置ｕｍを対応付けた場合を例示したが、３分木以上の木を少なくとも一つ含むツリーのリーフに受信装置ｕｍを対応付けた場合にも本発明は同様に適用可能である。
また、上述した実施形態では、ＳＤ，ＬＳＤなどのリボケーション方式に本発明を適用した場合を例示したが、処理装置が複数の鍵データ（復号用データ）を用いて暗号データを復号する場合に、当該処理装置が保持する鍵データの数を削減する要請のあるその他のシステムについても、本発明は同様に適用できる。
【００８９】
【発明の効果】
以上説明したように、第１、第３、第４、第７および第８の本発明によれば、複数の復号用データを用いて暗号データを復号する処理装置が保持する復号用データの数を削減できるデータ処理方法、そのプログラムおよびその装置と処理装置を提供することができる。
また、第２、第５および第６の発明によれば、複数の処理装置に提供した暗号データを、指定した前記処理装置に復号用データを基に復号させる場合に、各処理装置に保持させる復号用データの数を削減できるデータ処理方法、そのプログラムおよびその装置と処理装置を提供することができる。
【図面の簡単な説明】
【図１】図１は、本発明の第１実施形態に係わる通信システムの全体構成図である。
【図２】図２は、図１に示す管理装置のハードウェア構成図である。
【図３】図３は、図１に示す管理装置のリボケーション処理に先立って行う前処理を説明するためのフローチャートである。
【図４】図４は、図１に示す管理装置のリボケーション処理に先立って行う前処理を説明するための図３の続きのフローチャートである。
【図５】図５は、図１に示す管理装置が前処理等に使用するツリーを説明するための図である。
【図６】図６は、本発明の第１実施形態におけるラベルデータの生成方法を説明するための図である。
【図７】図７は、本発明の第１実施形態におけるラベルデータの生成方法を説明するための図である。
【図８】図８は、図１に示す受信装置に前処理で提供するラベルデータおよびマスタラベルデータを説明するための図である。
【図９】図９は、図１に示す管理装置によるリボケーション処理を説明するための図である。
【図１０】図１０は、図１に示す管理装置によるリボケーション処理を説明するためのフローチャートである。
【図１１】図１１は、図１に示す管理装置によるリボケーション処理を行う際に選択する集合を説明するための図である。
【図１２】図１２は、図１に示す受信装置のハードウェア構成図である。
【図１３】図１３は、図１に示す受信装置の全体動作を説明するためのフローチャートである。
【図１４】図１４は、図１３に示すステップＳＴ３３の処理を説明するためのフローチャートである。
【図１５】図１５は、図１に示す受信装置における中間ラベルデータの生成方法を説明するための図である。
【図１６】図１６は、本発明の第２実施形態の通信システムを説明するための図である。
【図１７】図１７は、本発明の第２実施形態の通信システムを説明するための図である。
【符号の説明】
２，２ａ，２ｂ…管理装置、ｕ１〜ｕ１６，ｕｍ，ｕｍａ，ｕｍｂ…受信装置、１１…通信部、１２…メモリ、１３…処理部、５１…通信部、５２…メモリ、５３…処理部
【図１】
2005012280.tif 000012
【図２】
2005012280.tif 000013
【図３】
2005012280.tif 000014
【図４】
2005012280.tif 000015
【図５】
2005012280.tif 000016
【図６】
2005012280.tif 000017
【図７】
2005012280.tif 000018
【図８】
2005012280.tif 000019
【図９】
2005012280.tif 000020
【図１０】
2005012280.tif 000021
【図１１】
2005012280.tif 000022
【図１２】
2005012280.tif 000023
【図１３】
2005012280.tif 000024
【図１４】
2005012280.tif 000025
【図１５】
2005012280.tif 000026
【図１６】
2005012280.tif 000027
【図１７】
2005012280.tif 000028