(57)【要約】      （修正有）【課題】ブロードキャスト暗号化方式において、最適又は概最適な集合被覆を算出する。【解決手段】最適又は概最適な集合被覆ＣＶ（ｆ，Ｐ）は、権限を有するユーザと、所定数ｆの失効したユーザ（「フリーライダー」）との集合Pに対して算出される。被覆は、全ユーザＵの集合に対する所定の集合被覆ＣＣ（Ｕ）の要素から成る。被覆は、Uの真部分集合であるＣＣ（U）要素の権限を有するユーザに対する最適又は概最適な被覆を検出することによって算出される。一実施形態では、ＣＣ（U）の要素の「合流点」のみが検査される。合流点は、各々が失効しているユーザを含む少なくとも２つの「直下の子」要素を含む、要素である。「親」要素の直下の子要素は、中間要素を持たない親の真部分集合である。合流点の順序リストＭＰは、効率的に計算される。【選択図】図１４
2010158054.tif 000002
【特許請求の範囲】
【請求項１】
実体の集合と関連付けられた送信用メッセージを形成するデータを、コンピュータによって選択する方法であって、
（１）コンピュータ・データを取得する工程と、
（２）少なくとも対象集合Ｐを被覆する被覆ＣＶを特定する工程と、
（３）被覆ＣＶの集合のそれぞれについて、対応するデータ片を用いてメッセージを生成し、前記メッセージを送信する工程とを含み、
（１）前記コンピュータ・データは、
（１Ａ）前記実体の集合Ｕと
（１Ｂ）Ｕの部分集合である前記対象集合Ｐと、
（１Ｃ）Ｕの部分集合の集合である集合体ＣＳ（Ｕ）とを表し、
（２）前記被覆ＣＶは、前記集合体ＣＳ（Ｕ）の要素である０以上の集合Ｓにより、前記集合Ｓの和が前記対象集合Ｐを構成するように構成されるものであり、
前記選択されるデータは、前記被覆ＣＶの前記要素に関連付けられたデータ片であり、
前記被覆ＣＶを特定する工程は、
（２ａ）ＣＳ（Ｕ）における全ての合流点の順序集合ＭＰを算出する工程と、
（２ｂ）前記合流点から、前記被覆ＣＶを決定する工程とを含み、
（２ａ）前記合流点は、前記合流点の高さに応じて順序付けられており、（ａ）ＣＳ（Ｕ）において、各々がＲ＝Ｕ＼Ｐの要素を備える少なくとも２つの直下の子を有する要素であるか、または（ｂ）Ｒの要素である単一の実体から成る要素であるかのいずれかであるような、集合体ＣＳ（Ｕ）の要素であり、
ＣＳ（Ｕ）の任意の要素ｅ１がＣＳ（Ｕ）の他の要素ｅ２の真部分集合であり、かつ部分集合としてｅ１を含みかつｅ２の真部分集合であるような要素ｅ３がＣＳ（Ｕ）に存在しないならば、ｅ１は、ｅ２の直下の子と呼ばれ、
合流点の高さは、前記合流点を始点とし、ＣＳ（Ｕ）のいずれの要素の部分集合でもない要素を終点とする連鎖の要素における、ＣＳ（Ｕ）の要素の数を表し、前記連鎖の最後の要素を除く各要素は、前記連鎖における次の要素の直下の子であることを特徴とする方法。
【請求項２】
前記全ての合流点の前記集合ＭＰを算出する工程は、
（２ａ−１）ｒ＞１である場合、ＣＳ（Ｕ）の各要素ｕｉ（ｉ＝１，２，…ｒ）がＲの１つの要素を構成するように、前記集合ＭＰを列ｕ１，ｕ２，…ｕｒに初期化する工程と、
（２ａ−２）ＣＳ（Ｕ）の要素のついの集合Ｅを定義し、前記集合Ｅを、ｉ＝１，…，ｒ−１である隣接する要素の全対｛ｕｉ，ｕｉ＋１｝の集合に初期化する工程と、
（２ａ−３）前記集合Ｅから、要素ａ（ｕｉ，ｕｉ＋１）がＥにおける全対の最大の高さを有する対｛ｕｉ，ｕｉ＋１｝を取り除く工程と、
（２ａ−４）前記取り除かれた対について、前記要素ａ（ｕｉ，ｕｉ＋１）を前記集合ＭＰに付加する工程と、
（２ａ−５）前記集合Ｅが前記工程（２ａ−３）における要素ｕ又はｕｉ＋１を構成する少なくとも１つの対を含む場合、少なくとも１つの対の各要素ｕｉ又はｕｉ＋１を、工程（２ａ−４）の前記要素ａ（ｕｉ，ｕｉ＋１）に置き換える工程とを含み、
前記工程（２ａ−１）の前記列ｕ１，ｕ２，…ｕｒにおける各要素ｕｉについて、ｖ∈ＣＳ（Ｕ）が、ｕｉとは異なり、Ｒの１つの要素を構成するように、要素ａ（ｕｉ，ｕｉ＋１）又は要素ａ（ｕｉ−１，ｕｉ）のいずれかが、全ての要素ａ（ｕｉ，ｖ）の最大の高さを有し、ＣＳ（Ｕ）の２つの要素ｕ，ｖについて、ａ（ｕ，ｖ）が、ｕとｖとの両方を含む全要素の最大の高さを有するＣＳ（Ｕ）の要素を示すことを特徴とする請求項１に記載の方法。
【請求項３】
工程（２ａ−１）から（２ａ−５）は、前記集合Ｅが空となるまで行われることを特徴とする請求項２に記載の方法。
【請求項４】
請求項１に記載の方法を実行するように構成された装置であって、
前記（２）の動作を実行するように構成された１つ又は複数の演算装置を有するコンピュータ・システムを備えることを特徴とする装置。
【請求項５】
コンピュータ・システムが請求項１に記載の方法を実行するための１つ以上のコンピュータ命令を備えることを特徴とするコンピュータ可読記憶媒体。
【請求項６】
コンピュータ・システムが請求項１に記載の方法を実行するためのコンピュータ・プログラムを、通信網を介して送信する工程を含むことを特徴とするデータ送信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の説明）
本願は、参照により本明細書に援用される、米国仮出願第６０／７３９，６５７号（２００５年１１月２２日出願）および米国特許第１１／５６１，０９６号（２００６年１１月１７日出願）に対して優先権を主張するものである。米国指定では、本願は、上述の米国特許第１１／５６１，０９６号の継続出願である。
【０００２】
本発明は、データ処理に関し、特に、例えば、ブロードキャスト暗号化や証明書失効等の各種のアプリケーションに利用できるような集合システムのコンピュータ処理に関する。
【背景技術】
【０００３】
排他的集合体
［８］において、ＫｕｍａｒとＲｕｓｓｅｌｌは、排他的集合体という概念を形式化した。排他的集合体とは、以下の条件を満たす集合族である。すなわち、全体集合に対する大きな部分集合はすべて、族から抽出した部分集合の集まりの和として記述できる。より形式化した形で示すと、
定義１
【０００４】
【数１】
2010158054.tif 000003
【０００５】
である任意の部分集合Ｒ⊂［ｎ］について、
【０００６】
【数２】
2010158054.tif 000004
【０００７】
を満たす任意のｉjに関して、
【０００８】
【数３】
2010158054.tif 000005
【０００９】
と書ける場合、［ｎ］に対する部分集合族ＣＣ＝｛Ｓ１，．．．，Ｓｋ｝は（ｎ，ｋ，ｒ，ｔ）において排他的である。添え字ｉjは必ずしも互いに異なる数である必要はないため、Ｒは、ｔ個未満の互いに異なる集合
【００１０】
【数４】
2010158054.tif 000006
【００１１】
の和でありうる。ここで、［ｎ］は自然数の集合｛１，．．．，ｎ｝を表す。なお、自明ながら、［ｎ］は、ｎ個の要素を持つ任意の集合Ｕに置き換えることができる。
【００１２】
ここで、集合族
【００１３】
【数５】
2010158054.tif 000007
【００１４】
を集合［ｎ］＼Ｒの被覆または集合被覆と呼び、本明細書中では、ＣＲとも表す。実際のアプリケーションにおいては、Ｒを「失効した」要素の集合、集合Ｐ＝Ｕ＼Ｒを「権限を有する」要素の集合と考えることができる。以下、Ｐを対象集合とも呼ぶ。本明細書において、Ｃ（Ｐ）＝ＣＲと表す。
【００１５】
図１の例では、［ｎ］の各要素は二次元平面上の×印で示されている。ｉ∈［ｎ］である各要素ｉには、参照符号１０４．ｉが付されている。集合Ｒは、要素１０４．１、１０４．２および１０４．３
【００１６】
【数６】
2010158054.tif 000008
【００１７】
から成る。また、Ｓ１＝｛４，５，６｝、Ｓ２＝｛６，７｝およびＳ３＝｛８｝であり、集合［ｎ］＼Ｒはこれら３つの集合Ｓ１、Ｓ２およびＳ３
【００１８】
【数７】
2010158054.tif 000009
【００１９】
によって被覆される。
【００２０】
ｎ，ｋ，ｒおよびｔ間の正確なトレードオフの決定は、コンピュータ科学における主要なアプリケーションを用いた基本的な組み合わせ問題である。
【００２１】
ブロードキャスト暗号化への応用
ブロードキャスト暗号化方式においては、ｎ個のクライアント１０４．１〜１０４．ｎにブロードキャストを行うサーバ２１０（図２Ａ）が存在する。ブロードキャスト・コンテンツＢは、秘密鍵ｂｋを用いて、何らかの対称暗号化アルゴリズム１（２２０で示す）で暗号化される。暗号化されたコンテンツＥ１ｂｋ（Ｂ）は、複数のクライアント１０４にブロードキャストされる。各クライアント１０４．ｉは、対称暗号化アルゴリズム２に対する暗号鍵ｋｉを有する。本例では、失効したクライアントの集合Ｒは、端末｛１，．．．，ｒ｝から成り、すなわち｛１０４．１，．．．，１０４．ｒ｝である。サーバは、失効していないクライアントの鍵ｋｒ＋１，．．．，ｋｎのそれぞれを用いて、ｎ−ｒ回、アルゴリズム２（２３０で示す）により鍵ｂｋを暗号化する。結果として得られる暗号を、
【００２２】
【数８】
2010158054.tif 000010
【００２３】
で示す。サーバは、これらの暗号を、（おそらく無線ネットワークを介して）ブロードキャストする。
【００２４】
各クライアント１０４（図２Ｂ）は、これらのブロードキャストを受信する。失効していないクライアント１０４．ｒ＋１，．．．，１０４．ｎの各々は、暗号化アルゴリズム２に対応する復号化アルゴリズム２（２４０で示す）を実行する。ステップ２４０において、これらのクライアントｉ（ｉ＝ｒ＋１，．．．，ｎ）の各々は、対応する鍵ｋｉと暗号
【００２５】
【数９】
2010158054.tif 000011
【００２６】
とを用いて、鍵ｂｋを復元する。鍵ｂｋおよびブロードキャスト暗号Ｅ１ｂｋ（Ｂ）は、２５０に示す通り、暗号化アルゴリズム１に対応する復号化アルゴリズム１に対する入力として与えられる。その出力がブロードキャスト・コンテンツＢである。
【００２７】
失効したクライアント１０４．１，．．．，１０４．ｒは、鍵ｋ１，．．．，ｋｒで暗号化されたブロードキャスト鍵ｂｋの暗号を受信していないため、ブロードキャスト・コンテンツＢを復元できない。
【００２８】
本例では、ステップ２３０において、各ブロードキャストはｎ−ｒ個の暗号を含む。各集合Ｓｉが、集合Ｓｉの要素であるすべてのクライアント１０４に与えられる暗号鍵
【００２９】
【数１０】
2010158054.tif 000012
【００３０】
に関連付けられる場合、暗号の数を多くともｔまで減らすことができる。図３を参照されたい。サーバは、集合［ｎ］＼Ｒの被覆集合
【００３１】
【数１１】
2010158054.tif 000013
【００３２】
を求める。ステップ２３０（図４Ａ）において、サーバ２１０は、対応する鍵
【００３３】
【数１２】
2010158054.tif 000014
【００３４】
を使って鍵ｂｋを暗号化する。失効していない各クライアントのみが、１つ以上の鍵
【００３５】
【数１３】
2010158054.tif 000015
【００３６】
を有するため、これらのクライアントのみが、鍵ｂｋを復号し、ステップ２４０（図４Ｂ）において、ブロードキャスト・コンテンツＢを復元できる。ステップ２４０において、クライアントは、自身の属する集合
【００３７】
【数１４】
2010158054.tif 000016
【００３８】
に対応付けられた任意の鍵
【００３９】
【数１５】
2010158054.tif 000017
【００４０】
を利用することができる。失効した要素（失効したクライアント）がいかに連携し、結託したとしても、該ブロードキャストから全く情報を得ることができない。
【００４１】
ｔ個の鍵の部分集合の各々が、多くとも１つの集合［ｎ］＼Ｒに対応しうるので、
【００４２】
【数１６】
2010158054.tif 000018
【００４３】
、またはこれに相当する
【００４４】
【数１７】
2010158054.tif 000019
【００４５】
であることが要求される。（ここで用いる下限は、［１０］における補題１１によって与えられるものと等しく、一般的なｎ，ｒおよびｔに対して密接な未知数である。尚、［１０］で用いられる限界は、通常密接ではない。）例えば、［１０］における定理１２は、ひまわり定理の代わりに、互いに素であることが緩和された数（［６］の８２頁）を用いたひまわり定理を用いることにより、改良できる。この排他的集合体をブロードキャスト暗号化に用いる汎用技術は、部分集合−被覆フレームワーク（ｓｕｂｓｅｔ−ｃｏｖｅｒ  ｆｒａｍｅｗｏｒｋ）として、当該技術分野では周知されている。特に、一つの排他的集合体が一つの「部分集合被覆」を形成する。
【００４６】
定義２
Ｐ⊆Ｕである任意の部分集合Ｐについて、
【００４７】
【数１８】
2010158054.tif 000020
【００４８】
を満たす添え字ｉ１，．．．，ｉｍ∈［１，ｗ］が存在する場合、
【００４９】
【数１９】
2010158054.tif 000021
【００５０】
を満たす部分集合Ｓ１，．．．，Ｓｗの系ＣＣ（Ｕ）を、Ｕの部分集合被覆と呼ぶ。また、ｍを被覆の大きさと呼ぶ。
【００５１】
集合被覆問題などの問題は、ＮＰ困難ではあるが、ある部分集合系が、ある対象集合の被覆を形成するか否かの判定は、非常に簡単であることが分かっている。
【００５２】
補題
全ての単要素集合（すなわち、ｕεＵである全てのｕに対する｛ｕ｝）がＳｊに含まれる「場合」、およびその「場合に限り」、
【００５３】
【数２０】
2010158054.tif 000022
【００５４】
を満たす部分集合系Ｓ１，．．．，Ｓｗは、部分集合被覆を形成する。
【００５５】
証明
Ｐ⊂Ｕである任意の（有限）集合Ｐに関して、
【００５６】
【数２１】
2010158054.tif 000023
【００５７】
であるため、かつ、部分集合｛ｕ｝は、仮定により被覆に含まれるため、上述の「場合」のに該当するかを示すことは容易である。一方、上述の「場合に限り」に該当するかについては、Ｐ＝｛ｕ｝ならば必然的に、集合｛ｕ｝は、部分集合被覆の一部でなければならない。従って、ｕεＵである全てのｕに対する｛ｕ｝は、部分集合被覆内である。
【００５８】
ブロードキャスト暗号化技術は、有料の映像、音声および文字コンテンツのような特権的コンテンツの、セキュアなマルチキャストのために利用することができる。また、携帯電話のハードディスクや、ＵＳＢ記憶装置、フラッシュカード、ＣＤおよびＤＶＤ  ＲＯＭのような外部記憶媒体におけるコンテンツ保護に利用してもよい。その他の利用例としては、対称鍵インフラストラクチャが挙げられ、有償コンテンツは、安全な形で複数の受信者に送信する必要のある状況にも利用できる。
【００５９】
証明書失効への応用
図５において、証明書１０４はそれぞれ、ネットワーク・コンピュータ環境における公開鍵の安全利用・管理の円滑化のために、公開鍵インフラストラクチャ（ＰＫＩ）で用いられるデジタル証明書である。各証明書１０４は、ユーザの公開鍵ＰＫおよび該ユーザ名を含み、該ユーザのＥメールアドレスまたは住所、証明書のシリアル番号ＳＮ（認証局（ＣＡ）６１０（図６Ａ）が証明書管理の簡便化のために作成）、証明書発行日Ｄｌ、失効日Ｄ２、公開鍵および秘密鍵と組み合わせて用いられるアルゴリズムの識別子、ＣＡ６１０の識別子、有効性証明データ１０４−Ｖ（後述）およびおそらくは他のデータを含んでもよい。上記のデータを１０４Ｄで示す。さらに、証明書１０４は、データ１０４Ｄに関するＣＡの署名１０４−ＳｉｇＣＡを含む。ＣＡ６１０は、ユーザ（鍵所有者）のコンピュータ・システム（図示せず）に証明書１０４を送る。該所有者またはＣＡ６１０のいずれかが、該証明書を通信相手に配布し、該ユーザの公開鍵ＰＫを知らせることができる。配布先の通信相手は、ＣＡの署名１０４−ＳｉｇＣＡをＣＡの公開鍵を用いて検証し、証明書の公開鍵ＰＫが、証明書内に名前およびｅメールアドレスが記載されちえる人物に本当に属するものであることを確認できる。
【００６０】
証明書１０４が失効した場合、他の通信相手が該証明書を利用するのを阻止しなければならない。該証明書の有効性の確認には、有効性証明データ１０４−Ｖが用いられる。Ｍｉｃａｌｉの方式［１２，１３，１４］、およびその後のＡｉｅｌｌｏ等による方式［２］などの、本技術分野で周知されている既存の証明書失効方式では、認証局６１０は、期間ｍ毎に（例えば、毎日）、公開鍵インフラストラクチャ内の失効していない証明書の各々に対して、有効性証明ｃｍを（おそらく、無線ネットワークなどの何らかの種類のネットワークを介して）発行する。ＣＡのクライアント６２０（図６Ｂ）は、６３０で示すように、検証アルゴリズムに対して、証明書の有効性データ１０４−Ｖと共に、証明書の有効性証明ｃｍを提供する。この検証アルゴリズムの出力は、証明書が期間ｍにおいて有効であるか否かを表す。
【００６１】
元となるＭｉｃａｌｉの論文では、有効性証明は、失効していない証明書毎に発行される。従って、ｎを全ユーザ数、ｒを失効していない証明書の数とすると、システム全体の通信複雑性は、ｎ−ｒに比例する。Ａｉｅｌｌｏ等は、１つの有効性証明を１人の個別ユーザに適用するのではなく、ユーザを、定義１または２で示される各種部分集合Ｓｉに、グループ化できることに気が付いた。図３及び６Ａでは、各部分集合Ｓｉは、暗号情報
【００６２】
【数２２】
2010158054.tif 000024
【００６３】
に関連付けられる。この暗号情報
【００６４】
【数２３】
2010158054.tif 000025
【００６５】
から、ＣＡは、期間ｍにおける有効性証明ｃｍ（Ｓｉ）を生成できる。この１つの有効性証明が、部分集合Ｓi内のすべての証明書の有効性を証明する。各期間ｍに対して、ＣＡは、失効していない証明書の集合に対する被覆
【００６６】
【数２４】
2010158054.tif 000026
【００６７】
を決定し、有効性証明
【００６８】
【数２５】
2010158054.tif 000027
【００６９】
を算出し、クライアント６２０（証明書保有者および／または他の相手を含んでよい）に対して該有効性証明を配布する。
【００７０】
各部分集合Ｓｉに有効性証明ｃｍ（Ｓｉ）を与えなければならないので、有効性証明の総数は増加するかもしれないが、証明書送信時の通信複雑性は、なお、部分集合−被覆体系におけるパラメータｔに比例し、一般的には、ｔ＜ｎ−ｒである。よって、通信量全体で見ると、本手法が必要とする量は、元となるＭｉｃａｌｉの手法が必要とする量よりも少ない。
【００７１】
部分集合被覆は、木構造を用いて構築できる。図７は、１から８までの番号が割り振られた８個の証明書を表す二分木７１０を示している。各ノードは、証明書の集合Ｕに対する部分集合被覆ＣＣ（Ｕ）内のある集合Ｓｉを表す。葉ノード（１，２，．．．が割り振られている）は、それぞれ、証明書１，２，．．．用の単要素集合を示す。上位の階層のノードはそれぞれ、その子の和を表す。例えば、ノード１−４は、証明書１から証明書４までの集合を表す。根ノードは全証明書を表す。（本説明においては、木構造と部分集合被覆の両方、すなわち部分集合体を表すために参照番号７１０を用いる。）
証明書が失効すると、対応する葉ノードも失効し、有効性証明を与えるべきではない集合であることが示される。さらに、該葉から根に至る経路上に存在する各ノードもまた失効する。図７の例では、（「×」印で示される）証明書３、７および８が、失効している。これに従い、集合３−４，１−４，１−８，７−８，５−８が失効している。失効していない証明書の最小被覆は、ノード１−２，４および５−６から成る。一般に、最小被覆Ｃ（Ｐ）は、失効したノードの直下の子ノード全てから成る。木走査に対するコンピュータ・アルゴリズムとしては、ＣＡ６１０に実装され、証明書の失効時に失効したノードに印を付け、該失効ノードの直下で失効していない子を全て見つけることができるものが、知られている。
【００７２】
図８は、失効ノードの直下で失効していない子の集合として、Ｃ（Ｐ）を生成するアルゴリズムを示している。まず、Ｃ（Ｐ）を初期化し、空集合とする（ステップ１）。ステップ２において、各失効ノードｖが失効していない子を持つ場合、その子はＣ（Ｐ）に追加される。
【００７３】
図７のツリー法は、完全部分木法として知られるものである。各ユーザは、１＋ｌｏｇ２ｎ個の鍵を格納する。これらの鍵は、ユーザに割り当てられた葉から木の根に至る経路上の各頂点（すなわちノード）に関連付けられている鍵に対応する。完全部分木法を使うと、被覆の大きさはＯ（ｒｌｏｇ（ｎ／ｒ））となる。［９］を参照されたい。
【００７４】
フリーライダー
ブロードキャスト暗号化に関する従来技術は、殆どが厳しい安全性基準を想定している。特に、権限を保有する集合Ｐの任意の要素が、ブロードキャストの復号が可能である一方、該集合外のいずれの要素も復号が不可能であるべき、との基準を想定している。ただ、多くのアプリケーションにおいて、これは必要ではない。特に、本システムは、権限を保有しないユーザの一部がブロードキャストを復号可能とすることを許容し得る。このようなユーザをフリーライダーと呼ぶ。
【００７５】
ここで、フリーライダーを許容するのが望ましい理由について考察する。多くの場合、システムの条件を緩和して、フリーライダーを許容すれば、その他のシステム費用が大幅に削減されると考えられる。例えば、ブロードキャスト時に通信するデータ量を削減できる可能性がある。また、データをブロードキャスト送信されるユーザが多数存在するならば、これにより、全体のネットワークトラフィックが大幅に削減されるであろう。例えば、図７の部分集合被覆（証明書失効の文脈で説明したが、ブロードキャスト暗号化用に構築することも可能である）の場合を検討されたい。この例では、権限を保有するユーザの集合に対する最適な（最小の）被覆Ｃ（Ｐ）は、上述の通り、ノード１−２，４および５−６の３つから成る。フリーライダーを１人許容する場合には、ノード３をフリーライダーにすることができる。これにより、最小被覆は、２つのノード１−４および５−６のみから成ることになり、ネットワークトラフィックが削減されるであろう。
【００７６】
フリーライダーという概念は、Ａｂｄａｌｌａ，ＳｈａｖｉｔおよびＷｏｏｌ［１］（括弧内の番号は本開示の最後に列挙した参考文献を示している）により導入された。［１］の著者らは、フリーライダーを許容することにより、多くの場合、通信するデータ量を（そして、その結果、全体のネットワークトラフィックを）削減できるということを、まず実例を挙げて実証した。次に、同著者らは、あたえられフリーライダーの数に対して、トラフィックを最小化する「最適な」解にいかにして到達できるかという問題を考察した。同著者らは、この問題が、最悪ケースのＮＰ完全であること、すなわち、そこには有効な解がない、ということに気付く。さらに同著者らは、最適な解に常に近似するパフォーマンスを発揮するアルゴリズムを発見するという課題もまた難易度が高いものであることを証明した。次に、同著者らは、部分集合−被覆フレームワークに依拠するブロードキャスト暗号化方式に、ある「経験則的な」手法を適用することを提案する。最後に、同著者らは、自らの経験則的手法を完全部分木法に適応した場合のパフォーマンスを分析する実験を行う。同著者らの経験則的手法は、これらの実験において十分なパフォーマンスを発揮したようで、同著者らは、この結果に基づき、フリーライダーはブロードキャスト暗号化の文脈において有用な概念である、という自らの主張を裏付けた。
【００７７】
特に、［１］は、Ｐ⊆Ｕである各集合Ｐについて、以下の条件
【００７８】
【数２６】
2010158054.tif 000028
【００７９】
を満たす被覆
【００８０】
【数２７】
2010158054.tif 000029
【００８１】
が存在するように、ｆ冗長の被覆を、被覆ＣＣ＝｛Ｓｉ｝として定義する。
【００８２】
完全分木法に対して同著者らが用いた経験則的手法は、以下の通りである。まず、被覆Ｃｆ（Ｐ）を初期化し、空集合とする。次に、（図７に示すような）木は、根（図７の例ではノード１−８）から、深さ優先順または幅優先順のいずれかの探索順序で走査される。そして「合格の」集合（すなわちノード）ｖが見つかるたびに、被覆Ｃｆ（Ｐ）にｖを追加し、ｖの子を無視する。集合ｖは、以下の条件を満たすときに、合格とされる。
【００８３】
ｖＵが、Ｃｆ（Ｐ）によってまだ被覆されていない（すなわち、Ｃｆ（Ｐ）内のいずれの集合にも含まれない）、ｖ内の全ユーザを表すとする。ｖＰが、Ｃｆ（Ｐ）によってまだ被覆されていない、権限を保有する全ユーザ（すなわちＰの全要素）を表すとする。このとき、
【００８４】
【数２８】
2010158054.tif 000030
【００８５】
である場合、ｖが合格とされる。
【発明の概要】
【発明が解決しようとする課題】
【００８６】
［１］は、上記手法が、二分木以外の木構造においても有効であることを注記している。
【００８７】
上記手法によって、期間Ｏ（ｎ）におけるｆ冗長の被覆が求められる。しかしながら、［１］の著者らは、被覆Ｃｆ（Ｐ）が最小であることを保証していない。
【課題を解決するための手段】
【００８８】
本節では、本発明の特徴の一部について概要を示す。その他の特徴については、後述する各節において説明する。本発明は、参照により本明細書に援用される添付の特許請求の範囲によって規定される。
【００８９】
本発明の一実施形態では、最小またはほぼ最小の被覆を算出し、これにより最適またはほぼ最適なネットワークトラフィックを保証するアルゴリズムを提供する。アルゴリズムは、一実施形態において、効果的である。発明者らが達した結論は、Ａｂｄａｌｌａらの［１］の結論と矛盾しない。特に、ＮＰ完全の理論は、最悪のシナリオに関する説に過ぎない−しかしながら、ブロードキャスト暗号化について言うと、本発明者は、ある特定のブロードキャスト暗号化方式に何が起こるかを関心対象としている。ある特定の方式については、以下に実証するように、最適な解に効率的に発見できるかもしれない。一実施形態では、本発明の手法が、完全部分木法に対して実施されている。一実施形態では、
【００９０】
【数２９】
2010158054.tif 000031
【００９１】
とすると、本手法は（１＋ε）近似アルゴリズムである。この設定では、ε＝０のときに、最小被覆を常に生成するアルゴリズムが得られる。εの増加に従い、該被覆は、最適ではなくなるかもしれないが、計算速度が速くなることがある。
【００９２】
一実施形態では、最適またはほぼ最適な集合被覆ＣＶ（ｆ，Ｐ）は、権限を保有するユーザの集合Ｐに対して、または、多くとも所定数ｆの失効したユーザに対して算出される。被覆は、全ユーザの集合Ｕに対する所定の集合被覆ＣＣ（Ｕ）の要素から成る。該被覆は、Ｕの真部分集合であるＣＣ（Ｕ）の要素に対する最適またはほぼ最適な被覆を求めることにより算出される。一実施形態では、ＣＣ（Ｕ）の要素に対して可能なフリーライダーの割当が調べられ、全体の集合被覆に対して所定の最適化基準を満たすよう、１つの割当が選択される。一実施形態では、「合流点」要素のみが用いられる。合流点とは、各々が失効したユーザを含む、少なくとも２つの「直下の子」要素を含む要素である。「親」要素の直下の子とは、中間要素（子を真部分集合として含み、それ自身が親の真部分集合である要素）を持たない親要素の真部分集合である。合流点の順序リストＭＰが算出される。該リストは、該合流点から根に至る連なりにおける要素の数の順に並べられる。一実施形態では、完全部分木法が利用される。
【００９３】
本発明の他の態様においては、木における合流点を算出する方法が提供される。本方法はフリーライダー法やその他の何らかのアプリケーションにおいて用いられる。
【００９４】
本概要は、本発明を限定するものではない。添付の特許請求の範囲によって規定する通り、他の実施形態および変形例も、本発明の範囲内に属する。
【図面の簡単な説明】
【００９５】
【図１】従来技術の部分集合被覆を示す図である。
【図２Ａ】失効していない各クライアントに暗号化されたブロードキャストを行う従来技術のサーバを示す。
【図２Ｂ】図２Ａで行われたブロードキャストを受信した従来技術のクライアントを示す。
【図３】クライアントの集合に割り当てられた復号鍵を示す図である。
【図４Ａ】失効していないクライアントの各集合に一度に暗号化されたブロードキャストを行う従来技術のサーバを示す。
【図４Ｂ】図４Ａで行われたブロードキャストを受信した従来技術のクライアントを示す。
【図５】従来技術のデジタル証明書を示す図である。
【図６Ａ】従来技術の認証局（ＣＡ）が、証明書の有効性に関する証明を送信する様子を示す。
【図６Ｂ】従来技術のクライアントが証明書の有効性を検証する様子を示す。
【図７】完全部分木法に対応する従来技術のデータ構造を示す図である。
【図８】従来技術の完全部分木法に対応する疑似コードを示す図である。
【図９】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１０】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１１】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１２】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１３】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１４】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１５】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１６】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１７】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【図１８】本発明の一実施形態におけるコンピュータ・データ構造を示す図である。
【発明を実施するための形態】
【００９６】
本節では、本発明の一実施形態を説明する。本発明はこれらの発明には限定されない。特に、本発明は、特定のデータ構造、アルゴリズム、又は計算量範囲に限定されない。本発明は、添付の特許請求の範囲により規定される。
【００９７】
以下、複数のブロードキャスト暗号化方式を参照し、本発明の一実施形態を説明する。これらの方式の技術は、例えば、図７に関して上述したように、マルチ証明書の検証などの他のアプリケーションにも用いることができる。ここで、フリーライダーとは、所有する証明書が失効しているが、まだそのように認識されていない、すなわち、有効な証明書を持っているかのように動作することを許可されるクライアントのことである。
【００９８】
以下の説明では、本発明についてより詳細な説明を行うため、多くの詳細が示される。しかし、本発明がこれら特定の詳細を含まずとも実施可能であることは、当業者には明らかであろう。また、本発明を不明瞭にするのを避けるため、公知の構造及び装置はブロック図で示される。
【００９９】
以下の詳細な説明において、一部を、コンピュータ・メモリ内のデータ・ビットに対する操作のアルゴリズムおよび記号表記の用語で示している。これらのアルゴリズムの記述および記号表記は、データ処理の当業者によって、自らの仕事を最も効果的に他の当業者に伝えるために使用される手段である。アルゴリズムとは、何かをするための方法である。この方法は、物理的量の物理的操作を必要とする場合もある。必ずというわけではないが、通常、これらの物理的量は、格納、転送、合成および比較等の操作が可能な電気又は磁気信号の形をとる。主に通常使用の理由のため、これらの信号をビット、値、要素、記号、文字、用語、数等と呼ぶことが好都合であることがわかっている。
【０１００】
しかしながら、これらおよび類似の用語はすべて、適切な物理的量と対応付けられるべきであり、これら物理的量に付与した便宜上のラベルに過ぎないということに留意すべきである。特に断りのない限り、以下の説明から明らかなように、本説明全体において、「処理する」、「計算する」、「算出する」、「求める」又は「表示する」等の用語を使った説明は、コンピュータ・システムのレジスタおよびメモリ内で物理的（電子的）量として示されるデータの操作、および同データの、コンピュータ・システム・メモリまたはレジスタ等の情報記憶装置、送信信号または表示装置内で同様に物理量として表現される他のデータへの変換を行うコンピュータ・システムや類似の電子計算装置の動作や処理に関するものである。
【０１０１】
また本発明は、該操作を内部で行う装置にも関連する。本装置は、所要の目的のために特別に作られたものであってもよく、あるいは内部に格納されたコンピュータ・プログラムによって選択的に動作されるか、または再構成される汎用コンピュータを備えてもよい。このようなコンピュータ・プログラムは、コンピュータ可読記憶媒体に格納されてもよい。このようなコンピュータ可読記憶媒体としては、フロッピィ・ディスク、光ディスク、ＣＤ−ＲＯＭおよび光磁気ディスクなどの任意の種類のディスク、リード・オンリー・メモリ（ＲＯＭ）、ランダム・アクセス・メモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カードまたは光カード等の、コンピュータの命令の格納に適した任意の種類の媒体が挙げられるが、これらに限定されない。また、そのようなコンピュータ・プログラムはネットワークを介して送信できる。
【０１０２】
本発明は、特定のプログラミング言語に関して説明を行うものではない。本明細書に記載される本発明の教示は、様々なプログラミング言語を使って実現できることが理解されよう。コンピュータ・プログラムは、コンピュータ可読媒体等のデータキャリアに格納され得る。また、コンピュータ・プログラムは、ネットワーク上のデータ搬送信号によって搬送され得る。コンピュータ可読媒体は、機械（例えば、コンピュータ）が読み出し可能な形式で、情報を格納・送信するための任意の機構を含む。例えば、機械可読媒体は、リード・オンリー・メモリ（「ＲＯＭ」）、ランダム・アクセス・メモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光学式記憶媒体、フラッシュ・メモリ装置、および電気、光または音声等の形式の伝播信号（例えば、搬送波、赤外線信号、デジタル信号等）等を含む。
【０１０３】
計算量的な仮定
多くの場合、暗号化分野の当業者にとって、暗号化に関する発明の安全性が、計算量的困難性の仮定に依拠することは、周知である。例えば、特定の数をその素因数に効率的に分解することが困難であるならば、ある暗号システムは安全である、ということを証明しようとする人がいるかもしれない。「計算量的」という用語は、この種の暗号化の発明を表すために、本技術分野ではよく用いられる。本発明は、パスワード認証型鍵交換に対する計算量的方式を提供する。「情報理論的」または「無条件」という用語は、数学的見地から見ていかなる種類の仮定も行わずに、特定の重要な安全性定義を満たすと認められる方式と組み合わせて、本技術分野ではしばしば用いられる。
【０１０４】
一般に、純粋に安全性の見地から見ると、いかなる計算上の仮定も立てないことが好ましいが、そのような仮定を立てない限り解決できない問題も一部存在する（本発明もそのような例の１つである）。さらに、計算量的な仮定を組み込むことにより、暗号化方法がより効率的になりうる場合があることは、当業者一般に周知されている。
【０１０５】
多くの場合、１つの仮定が他の仮定を含意することにも留意すべきである。すなわち、複数の仮定のうちの１つが、実際に正しいとするならば、数学的論理の原理より、他のある仮定も正しいと認められるであろう。このような含意を示すために当業者が通常用いる手段として、第２の仮定に反するメカニズムを、第１の仮定に反するメカニズムに変換する変換（本技術分野では、しばしば縮小として知られる）がある。このような場合、第１の仮定が「より強い」と呼ばれるか、あるいは第２の仮定が「より弱い」と呼ばれる。一般に、より弱い仮定が好ましい。
【０１０６】
計算量的か情報理論的かという問題は、本発明の方法及び装置とは関係がない。具体的には、排他的集合体のアプリケーションは、計算量的暗号化メカニズムまたは情報理論的暗号化メカニズムのいずれを用いても実現可能である。
【０１０７】
計算量的か情報理論的かという問題は、多くの暗号化に関する発明には関係があるが、本発明の方法及び装置とは関係がない。本発明の技術は、既存のブロードキャスト暗号化方式または証明書失効方式の上に適用されるものである。これらの基盤となるブロードキャスト暗号化方式および証明書失効方式は、その安全性を何らかの仮定に依拠しているが、本開示における発明はいずれも、それらに追加の仮定を付け加えることがない。
【０１０８】
方法の説明に際した数学的証明の利用
本明細書において開示される方法は、基本的な数学的概念に依拠している。本明細書中に示される方法の記述は、あるアルゴリズム的ステップが実行されることを規定するものである。しかしながら、これらのステップが実際に実行されうるのか、あるいはこれらのステップを実行することで所望の結果（本件においては、所望の近似界でのフリーライダー構成）を得られるのか、という重要な問題については、正式な数学的議論を用いて扱わねばならない。なお、ここで開示される方法を実現または実行するために、必ずしもこれらの議論に精通している必要はない。これらの議論は、単に、本手順が実際に正確でありかつ所望の結果につながるものであることを、当業者に判定可能ならしめるものに過ぎない。従って、完全を期すため、本明細書中にこれらの議論を適宜盛り込んだ。しかしながら、本方式の正確さ、実現可能性および性能に関する議論は、本開示に示される実際の方法や装置から切り離して考えるべきである。
【０１０９】
上述の説明では、ユーザ数ｎを２のべき乗として処理している。ただし、本発明の方法を、任意のユーザ数に容易に拡張できることは、当業者には理解されるであろう。例えば、ｎをユーザ数より大きい最小の２のべき乗数とすれば、計算量は、多くとも２の因数ごとに増加する。以下、２を底とする対数を、ｌｏｇ（）を用いて表す。
【０１１０】
木構造の頂点ｖについて、Ｔ（ｖ）を、ｖを根とする部分木とし、ＬＶ（ｖ）およびＲＶ（ｖ）をそれぞれｖの左右の子とし、Ｌ（ｖ）およびＲ（ｖ）を、それぞれｖの左右の子ノードを根とする部分木とするとする。ここでは、完全二分木９１０に示すように標準的なノードの識別方法を用いる（図９）。すなわち、根に１を割り当て、根の左の子に２、右の子に３をそれぞれ割り当てる。一般に、あるノードに整数ｉが割り当てられている場合、その左の子が２ｉ、その右の子が２ｉ＋１となる。図９の木は、ｎから２ｎ−１までの値を割り当てられたｎ枚の葉ノードを有する。ここで、ノードｖの高さ、すなわち、二分木におけるノードの階層レベルを、
【０１１１】
【数３０】
2010158054.tif 000032
【０１１２】
とする。ノードｕおよびｖについて、ｕおよびｖに共通の先祖のうち最高位のノードをａ（ｕ，ｖ）とする。例えば、図９において、ａ（４，５）＝２であり、ａ（５，６）＝１である。本明細書においては、ｕ∈Ｌ（ａ（ｕ，ｖ））かつｖ∈Ｒ（ａ（ｕ，ｖ））ならば、ノードｕがノードｖの左側にあるとする。
【０１１３】
本発明の方法に要する時間計算量を解析する際に、ＲＡＭモデルで作業を行うものとし、かつＯ（ｌｏｇｎ）の大きさの語に対する演算を、Ｏ（１）の時間で行えるものとする。本発明は、適切なアルゴリズム・ステップを実行できるならば、いかなる計算モデルにおいても実行可能である。所要時間は、計算モデルによって異なることがある。
【０１１４】
全ユーザの集合をＵとし、全ユーザ数（すなわち、｜Ｕ｜＝ｎ）をｎとし、権限を保有するユーザの集合をＰとし、えられたタイミングで失効しているユーザの集合をＲとし、ｒ＝｜Ｒ｜とする。
【０１１５】
ブロードキャスト暗号化方式の目的は、暗号化されたメッセージＭを全ユーザＵに送信し、Ｐのメンバーが同メッセージを復号できると同時に、Ｒのメンバーには復号できないようにすることである。一実施形態においては、Ｒに属するユーザが連携し、その知識を結集したとしてもＭを復号できないようにする。この目的を達成するため、本システムは複数の暗号鍵ＫＵからなる集合を備える。各ユーザｕは、これらの鍵の部分集合Ｋuについての知識を有することになる。ユーザｕはこれらの鍵を、何らかの受信装置（例えば、ユーザの携帯電話、ＤＶＤプレーヤ、またはセットトップ・ボックス）に格納する。一実施形態においては、受信側の鍵ＫＵが静的であり、ステートレスな場合に焦点を当てる。すなわち、ＫＵは、何らかの初期段階で割り当てられ、その後変化しない。
【０１１６】
定義３  
集合系Ｓ１，．．．，Ｓｗが、集合Ｕの部分集合被覆ＣＣ（Ｕ）を形成する場合を想定されたい。ＰをＵの部分集合とし、ｉ１，．．．，ｉｍ∈［１，ｗ］を
【０１１７】
【数３１】
2010158054.tif 000033
【０１１８】
を満たすようにする。このとき、
【０１１９】
【数３２】
2010158054.tif 000034
【０１２０】
である場合、与えられた０以上の整数ｆについて、
【０１２１】
【数３３】
2010158054.tif 000035
【０１２２】
をＰのｆ＋冗長の被覆と呼ぶ。さらに、
【０１２３】
【数３４】
2010158054.tif 000036
【０１２４】
とし、ｍをｆ＋冗長の被覆の大きさとする。
【０１２５】
ここで、１つ補足をする。冗長化された被覆について、本願における定義と、ＡＳＷ論文（上述の（１）参照）で与えられる定義との違いは表面的なものである。従って、どの定義を使うかの選択に、重要な意味はない。すなわち、得られるパフォーマンスを何ら変化させずに、本開示のすべての結果を、ＡＳＷ定義を使って再計算できる。本願における定義は、得られた結果を説明するのに、より都合がよいというだけのことである。ＡＳＷにおけるパラメータｆをｆ′とすれば、ｆ＝｜Ｐ｜・（ｆ′−１）、すなわちｆ′＝１＋ｆ／｜Ｐ｜ならば、ｆ′冗長の被覆はｆ＋冗長の被覆であり、逆もまた同様に成り立つ。
【０１２６】
ここで、目的は、フリーライダーの数ｆを所与として、冗長した被覆の大きさｍを最小化することにある。また、より一般的な意味では、最悪でも（権限を保有する集合Ｐの選択に係わらず）ｍを比較的小さくすることが目的である。本発明の一実施形態には、完全部分木法に対する、最適またはほぼ最適なｆ＋冗長の被覆を算出する有効なアルゴリズムが含まれる。
【０１２７】
一実施形態では、基本概念は、動的計画法の採用である。完全部分木法を使って最適なｆ＋冗長を求めた場合を想定されたい。（図９に示すような）完全二分木９１０の各ノードｖに対して、ｆｖが、木Ｔ（ｖ）における、許容可能なフリーライダーの最大数を示しているものとする。フリーライダーの追加により、被覆の大きさは増大するする可能性があるため、最適被覆におけるフリーライダーの実際の数は、この最大数ｆよりも小さくなりうる。例えば、最適被覆の大きさが０である（すなわち、全ユーザの権限が失効している）場合、１人のユーザをフリーライダーにするためには、被覆の大きさを正にして、そのフリーライダーを被覆する必要がある。ここでは、最適被覆を得たと想定すると、各内部ノードｖに対して、許容数ｆｖがその子の許容数の合計となるよう許容数ｆｖを割り当てる。つまり、根では、ｆ＝ｆ１＝ｆ１＋ｆ２である。
【０１２８】
最適被覆が、根（すなわち集合Ｕ）から構成されないならば、該被覆は、ｆ２人までのフリーライダーを含むＴ（２）、すなわち最初のｎ／２人のユーザ、に対する被覆、およびｆ３人までのフリーライダーを含むＴ（３）に対する被覆を含む。これらの２つの被覆は、最適でなければならない。すなわち、左の部分木がもたらす被覆は、最適なｆ２＋冗長の被覆であり、右の部分木がもたらす被覆は、最適なｆ３＋冗長の被覆である。これにより、部分木Ｔ（２）およびＴ（３）に対する被覆から、最適被覆ＣＶ（ｆ，Ｐ）を構築できる。おおよそだが、０からｆ１間で全てのとりうるｆ２値について、Ｔ（２）に対する最適被覆を決定し、同様に、全てのとりうるｆ３値について、Ｔ（３）に対する最適被覆を決定する。そして、木全体の被覆を最小化するｆ１についてｆ２＋ｆ３＝ｆ１である値の組（ｆ２，ｆ３）を選択する。同様の手法を用いて、Ｔ（２）およびＴ（３）に対する最適被覆を求めることができる。（木の最適被覆が根から成る場合を例外とする。この場合、最適被覆は
【０１２９】
【数３５】
2010158054.tif 000037
【０１３０】
であると、簡単に求めることができる。）
ここで、一実施形態についてより詳細に説明する。ｖを（図９に示すような）完全二分木９１０における頂点とし、Ｕ（ｖ）を、ｖを根とする部分木における全ユーザの集合とする。該木構造内の任意の頂点ｖについて、集合Ｕ（ｖ）が、完全部分木法による被覆内で用いられる集合の１つであることに注目されたい。また、ｒｖが木Ｔ（ｖ）内の権限が失効したユーザの数を表し、すなわち
【０１３１】
【数３６】
2010158054.tif 000038
【０１３２】
であり、Ｐ（ｖ）が木Ｔ（ｖ）内の権限を保有するユーザの部分集合を表す、すなわち、
【０１３３】
【数３７】
2010158054.tif 000039
【０１３４】
とする。
【０１３５】
ここで、Ｔ（ｖ，ｆ，Ｐ（ｖ），Ｕ（ｖ））．ｓｉｚｅが、ｖを根とする部分木におけるユーザの集合Ｐ（ｖ）に対する最適なｆ＋冗長の被覆ＣＶ（ｆ，Ｐ（ｖ））の大きさを表すとする。同様に、Ｔ（ｖ，ｆ，Ｐ（ｖ），Ｕ（ｖ））．ｃｏｖｅｒが、ｖを根とする部分木におけるユーザの集合Ｐ（ｖ）に対する最適なｆ＋冗長の被覆を構成する被覆集合の和を表すとする。以下、Ｐ（ｖ）およびＵ（ｖ）の記述を省略し、（Ｔ（ｖ，ｆ，Ｐ（ｖ），Ｕ（ｖ））をＴ（ｖ，ｆ）と記述する場合がある。
【０１３６】
後述する付録１および２は、本発明の方法の一実施形態を説明するものである。付録１のステップ１で、初期化が行われる（後述するその他のアルゴリズムでは、本ステップを示さない場合がある）。ステップ２で、ＯｐｔｉｍａｌＣｏｖｅｒメソッドを呼び出し、フリーライダーの数を多くともｆ人とした場合の、根ノード１の最適被覆を求める。ステップ３で、該最適被覆を用いて、適当なネットワーク送信等の適当な処理（例えば、図２Ａ〜６Ｂに関連して上述した処理）を行う。ステップ３は、後述するその他のアルゴリズムでは示さない場合がある。
【０１３７】
ＯｐｔｉｍａｌＣｏｖｅｒメソッドを付録２に示す。本メソッドに対する入力値は、ノードｖおよび許容可能なフリーライダーの最大数ｆｖである。３つの基本的な（重複する）境界ケースがあり、これらが、付録２におけるステップ１および２で示される再帰における基本ケースを構成する。第１のケースとして、ｆ＝０（ステップ１）の時、フリーライダーは存在しない。この場合、関連する部分木を被覆するために、Ｎａｏｒらによる基本アルゴリズム［２０］を採用する。例えば、図８を参照されたい。この集合の集まりをＢａｓｉｃＣｏｖｅｒ（ｖ，Ｐ（ｖ），Ｕ（ｖ））あるいは、単にＢａｓｉｃＣｏｖｅｒ（ｖ）と表す。
【０１３８】
第２のケースとして、Ｐ（ｖ）が空集合である、すなわち、Ｕ（ｖ）内のすべてのユーザの権限が失効しているとき、最適被覆は空集合である。もしフリーライダーをＵ（ｖ）に割り当てたならば、該フリーライダーを被覆するために、被覆の大きさは増大するであろう。本ケースでは、ＢａｓｉｃＣｏｖｅｒ（ｖ）が空被覆を生成するため、最適被覆は、第１のケースと同様の方法で算出できる。被覆の大きさは０である。
【０１３９】
第３の事例（ステップ２）として、
【０１４０】
【数３８】
2010158054.tif 000040
【０１４１】
（かつＰ（ｖ）が空集合でない）ならば、許容できるフリーライダーの数は、該部分木において権限が失効した人数と等しいか、またはそれを上回る。この場合、単純に、全ての権限を保有しないユーザをフリーライダーとすることにより、大きさ１の最適被覆を得ることができる。すなわち、Ｔ（ｖ，ｆ，Ｐ（ｖ），Ｕ（ｖ））．ｓｉｚｅ＝１かつＴ（ｖ，ｆ，Ｐ（ｖ），Ｕ（ｖ））．ｃｏｖｅｒ＝Ｕ（ｖ）である（本明細書では、ｖとＵ（ｖ）を、同じ意味で使う場合がある）。
【０１４２】
尚、ｖが木構造における葉のとき、これら３つの境界ケースのいずれかが適用される。特に、ｆｖ＝０または葉ノードが失効しているとき、第１または第２のケースが適用される。ｆｖ＞０かつ葉ノードが失効していないとき、ｒｖ＝１であり、よって
【０１４３】
【数３９】
2010158054.tif 000041
【０１４４】
である。従って、第３のケースが適用される。
【０１４５】
付録２のステップ３は、ｆｖ＞０の場合の内部頂点ｖに対する一般帰納ケースである。ｆＬ＝ｆＬＶ（ｖ）とすると、
【０１４６】
【数４０】
2010158054.tif 000042
【０１４７】
（５）を最小化するｆＬ＝ｆＬｍｉｎについて、
【０１４８】
【数４１】
2010158054.tif 000043
【０１４９】
（（５）を最小化するｆＬ値は複数存在するが、ｆＬｍｉｎは、その中の任意の値をとりうる。）
効率性の評価
一実施形態では、各値Ｔ（ｖ，ｆｖ）は（２ｎ−１）×（ｆ＋１）のテーブルＴＢＬ１（図１０）に格納される。テーブルの各行は、頂点ｖに関連付けられている。なお、ｎ人のユーザが与えられるとき（これらのユーザは、それぞれ木の葉ノードに位置し）、木は、合計２ｎ−１個の頂点を含む。テーブルの各列は、フリーライダーの数の限界値ｊ＝ｆｖ（０からｆまでの値をとる）を規定する。テーブルの各エントリは、個のフィールドを含むレコードを規定する。１番目のフィールド（「大きさ」）は、最適な被覆の大きさＴ（ｖ，ｆｖ）．ｓｉｚｅを規定する。２番目のフィールド（「被覆」）は、実際の最適被覆であるＴ（ｖ，ｆｖ）．ｃｏｖｅｒを規定する。３番目のフィールド（「確定？」）には、１番目および２番目のフィールドが、本アルゴリズムによってまだ確定されたか否かを明示するブール値である。「確定？」はＦＡＬＳＥに初期化されている。テーブル全体を初期化し、上記すべてのレコードをＦＡＬＳＥに設定するには、Ｏ（（２ｎ−１）×（ｆ＋１））＝Ｏ（ｎｆ）の演算を要する。レコードに、被覆の大きさおよび実際の被覆に関する情報が収容されると、「確定？」がＴＲＵＥに設定される。
【０１５０】
テーブルの各要素にアクセスするために、一実施形態では、木データ構造（図示せず）を用いて、（図９に示すような）完全二分木９１０を表す。木データ構造の各ノードが、ｆ＋１の大きさの配列を収容する。ノードｖに対する配列の各要素［ｊ］が、図１０のテーブル内のエントリＴＢＬ１［ｖ，ｊ］へのポインタを含む。これにより、付録２の中で規定した再帰関係に従い、テーブルの要素を効率的に走査することが可能になる。尚、いかなる場合でも、木構造自体が、そのテーブル内にレコードを含むという単純な形をとることができる。言い換えれば、別途テーブルを設ける理由は全くない。動的計画法は、テーブルを使って実現すると考えるほうが簡単であるため、ここではテーブル表記を用いている。
【０１５１】
次に、一実施形態では、一番目の列（すなわち、ｆｖ＝０）を付録１のステップ１において初期化する。この初期化は、ＢａｓｉｃＣｏｖｅｒ（ｖ，Ｐ（ｖ），Ｕ（ｖ））を各ｖに対して個別に算出する標準的な手法（［２０］または図８）を用いて、実施できる。これは、およそ
【０１５２】
【数４２】
2010158054.tif 000044
【０１５３】
の演算を必要とする。
【０１５４】
実際には、部分木に対して行った演算を再利用することにより、より容易に実施できる。内部頂点ｖに対して、一旦ＢａｓｉｃＣｏｖｅｒ（Ｌ（ｖ），Ｐ（Ｌ（ｖ）），Ｕ（Ｌ（ｖ）））およびＢａｓｉｃＣｏｖｅｒ（Ｒ（ｖ），Ｐ（Ｒ（ｖ）），Ｕ（Ｒ（ｖ）））を算出すると、ＢａｓｉｃＣｏｖｅｒ（ｖ，Ｐ（ｖ），Ｕ（ｖ））を一定時間で算出できることに注目されたい。特に、
【０１５５】
【数４３】
2010158054.tif 000045
【０１５６】
ならば、ＢａｓｉｃＣｏｖｅｒ（ｖ，Ｐ（ｖ），Ｕ（ｖ））＝Ｕ（ｖ）である。言い換えると、
【０１５７】
【数４４】
2010158054.tif 000046
【０１５８】
である。
【０１５９】
葉ノードにおいては、最適な基本被覆を算出するのに、わずかＯ（１）の時間しか要しない（すなわち、ある葉ｖついて、
【０１６０】
【数４５】
2010158054.tif 000047
【０１６１】
ならば被覆はＵ（ｖ）であり、そうでない場合には、被覆は空集合である）。従って、上記の再帰を用いれば、内部頂点に関しては、わずかＯ（１）の時間しか要しない。従って、Ｏ（ｎ）の時間で、１番目の列を初期化できる。
【０１６２】
ここで、本アルゴリズムの本体について考えてみたい。再帰の各ポイントにおいて、最も時間の要する部分は、上記の式（５）の計算（付録２のステップ３）の中にある。これは、Ｏ（ｆｖ）の演算を必要とする（ｆｖは列番号）。これをテーブル内のエントリごとに繰り返す必要がある。したがって、本体部分に必要な全体の所要時間は、
【０１６３】
【数４６】
2010158054.tif 000048
【０１６４】
である。これにより、アルゴリズム全体の所要時間は、
【０１６５】
【数４７】
2010158054.tif 000049
【０１６６】
となる。
【０１６７】
ここで一つ指摘されるかもしれない問題点としては、アルゴリズムに対して入力されるのは、厳密には、ユーザに関する説明、権限を保有する集合、完全部分木法（少なくともΩ（ｎ）ビットを必要とする）に関連付けられた集合の集まり、および（ｌｏｇｆビットを要する）ｆに関する説明である、ということがある。これは、所要時間が厳密には、ｆの大きさのべき乗であることを意味している。しかしながら、これは実際には正しくない。フリーライダーの数ｆは、多くともユーザ数ｎであり、従って、ｆの大きさは、多くともｌｏｇｎである。これは、入力の大きさが少なくともΩ（ｎ）ビットであり、所要時間が多くともＯ（ｎ３）であることを意味している。
【０１６８】
より無駄を省いた分析も可能である。（根がレベル０にあるときの）レベルｌの各ノードに対して、最小値（５）を算出すると、Ｏ（ｍｉｎ｛ｆ，ｎ／２ｌ｝）の演算を省略できることに注目されたい。これは、レベルｌでは、各部分木にｎ／２ｌ個の葉が存在するためである。フリーライダーの数が葉の数を上回ったときに何が起こるかについては、考えるまでもない。従って、レベルｌの各頂点ｖに、Ｏ（ｎ／２ｌ）のコストを課すことができる。さらに、レベルｌには２ｌ個の頂点がある。従って、最も時間を要するステップの所要時間は、
【０１６９】
【数４８】
2010158054.tif 000050
【０１７０】
となる。
【０１７１】
これをｆｖがとりうる値全てに対して行う必要がある（なぜなら、全て各部分木に対する最適解を組み合わせるときに、これらの値が必要になるためである）。これにより、Ｏ（ｎｆｌｏｇｎ）の実行時間が与えられる。さらに、各頂点に対してｆ＋１個のレコードを保持する必要は全くない。レベルｌの各頂点に対してｎ／２ｌ個のエントリを保持すればよい。これら複数のレコードを初期化するのにＯ（ｎｌｏｇｎ）の時間を要する。したがって、この分析により、本アルゴリズム全体の所要時間は、最悪の場合でもＯ（ｎｆｌｏｇｎ））であることが示される。これは、先に求めた
【０１７２】
【数４９】
2010158054.tif 000051
【０１７３】
である場合に必ず成立する範囲よりも好ましい範囲である。これはおそらく、パラメータの実際の設定のいずれの場合にも当てはまるであろう。例えば、正確に言えば、ｎが１０億であるならば、他方の限界値についてｆは３０より大きい必要がある。
【０１７４】
一実施形態では、ＯｐｔｉｍａｌＣｏｖｅｒメソッドは、最適被覆自体を算出するものではなく、ｆＬｍｉｎ値を算出するものに過ぎない。ＯｐｔｉｍａｌＣｏｖｅｒＳｉｚｅメソッドを示す付録３を参照されたい。図１１は、ＴＢＬ１の代わりに、付録３の一実施形態に適したデータ構造であるＴＢＬ２を示す。本データ構造においては、「大きさ」パラメータの代わりに、ＯｐｔｉｍａｌＣｏｖｅｒのステップ３で算出されるようなｆＬｍｉｎ値が格納される。ｆＬｍｉｎを算出すると、付録４のメソッド（付録４において、フリーライダーの集合はＦで示される）により、フリーライダーの葉を決定し、ＢａｓｉｃＣｏｖｅｒを呼び出すことにより、権限を付与されたノードとしてフリーライダーの葉を扱った上で被覆を求める（付録４のステップ５）。
【０１７５】
特に、付録３では、各ノードｖに対して、対応する「確定」パラメータがＴＲＵＥに設定される（付録３のステップ１）。付録３のステップ２〜４はそれぞれ、付録２のステップ１〜３と類似している。ｆＬｍｉｎ値は、付録３のステップ（４ｂ２）において、ＴＢＬ２に格納される。
【０１７６】
最適被覆は、付録４のＦｒｅｅＲｉｄｅｒｓメソッドで算出される。ステップ１において、フリーライダーの葉の集合Ｆを初期化し、空集合とする（初期化により、空集合ではなく、所定の基準により、該ブロードキャストを受信することが決まっているユーザの集合に設定してもよい）。ステップ２において、ｆｖ＝ｆであるノード１に対して、ＯｐｔｉｍａｌＣｏｖｅｒＳｉｚｅ（付録３）を呼び出す。そして、フリーライダーの最適な割当数の配列ｆｆ［ｖ］を算出する。この算出は、図１２（該配列値は、各ｖに対するテーブル形式で示される）および図１３（該配列値は、木のノードそれぞれに隣接して示される）に示すように行われる。付録３から分かるように、ｆｆ［ｖ］はｖに割り当てられるフリーライダー数の上限値である。ｆｆ［１］をｆとする（ステップ３）。基本的な考え方としては、ノードｖについて一つおきに、そのｖの親ノードに対する最適割当数ｆｆに対応するＴＢＬ２のｆＬｍｉｎ値を調べる。ｖが左の子ならば、ｆＬｍｉｎ人のフリーライダーを割り当てる、すなわち、そのｆｆ［ｖ］を、その親に対するｆＬｍｉｎ値に設定する。ｖが右の子ならば、その親のｆｆ値とｆＬｍｉｎ値の差分を割り当てる。ただし、付録４のステップ４に示すような例外は存在する。
【０１７７】
ステップ４において、上から下（例えば、幅優先探索順または深さ優先探索順）に、木を走査する。ステップ（４ａ）において、ｆｆ［ｖ］＝０ならば、木Ｔ（ｖ）にフリーライダーが存在しないため、走査を省略できる。Ｐ（ｖ）が空集合の場合もまた、フリーライダーが割り当てられていない（付録３のステップ２参照）ため、やはり木Ｔ（ｖ）の走査は省略できる。Ｐ（ｖ）が空集合であるという条件は、ＴＢＬ２［ｖ，ｆｆ［ｖ］］．Ｓｉｚｅ＝０と言い換えることができる。実際、最適被覆の大きさが０ならば、フリーライダーの割当後に被覆すべきノードが存在しないことになり、従って、フリーライダーは割り当てられていないことになる。ステップ（４ｂ）において、
【０１７８】
【数５０】
2010158054.tif 000052
【０１７９】
ならば、最適なｆ＋冗長の被覆ＣＶ（ｆｆ［ｖ］，Ｕ（ｖ））は、ノードｖから成る。従って、Ｔ（ｖ）内の、失効した全てのノードがＦに追加され、以降のＴ（ｖ）に対する走査は省略される。
【０１８０】
ｖが葉ノードである場合、該ノードは、ステップ（４ａ）または（４ｂ）において処理される。従って、ステップ（４ｃ）においては、内部ノードのみが処理される。本ステップでは、上述と同様に（つまり、左の子にｆＬｍｉｎ、右の子にｆｆ［Ｖ］−ｆＬｍｉｎという形で）、子ＬＶ（ｖ）およびＲＶ（ｖ）に対するｆｆ値が算出される。
【０１８１】
ステップ５において、
【０１８２】
【数５１】
2010158054.tif 000053
【０１８３】
が呼び出され、最適被覆とその大きさが算出される。
【０１８４】
本発明は、付録１〜４の特定の態様に限定されない。例えば、それぞれの木を下から上に走査して、テーブルＴＢＬ１およびＴＢＬ２それぞれの適正値を算出する場合には、付録２および３における再帰を避けることができる。
【０１８５】
一実施形態においては、計算量を削減することと引き換えに、最小よりも大きな被覆を許容する。最小の被覆の大きさをｓｍｉｎとする。
【０１８６】
【数５２】
2010158054.tif 000054
【０１８７】
である何らかの数に対して、以下を満たすように、被覆の大きさｓεを求めることができるかもしれない。
【０１８８】
【数５３】
2010158054.tif 000055
【０１８９】
一実施形態においては、ε＞０ならば、このような被覆は、付録２のステップ３または付録３のステップ４において必要な計算量を削減する。これについては、このすぐ後に説明するＭｉｎＳｕｍ問題を考察する中で説明する。
【０１９０】
ＭｉｎＳｕｍ問題
上述した式（５）の最小値は、公知のＭｉｎＳｕｍアルゴリズムを使って求めることができる。実際、ある定ノードｖについて、以下のように値を定める。
【０１９１】
【数５４】
2010158054.tif 000056
【０１９２】
このとき、ｊ＝ｆＬおよびｉ＝ｆｖとすると、（５）の最小値は、以下の式で表すことができる。
【０１９３】
【数５５】
2010158054.tif 000057
【０１９４】
｛ａｉ｝および｛ｂｉ｝のそれぞれがｉの減少（すなわち、非増加）列である場合に、このような最小値を求めるのが、いわゆる公知のＭｉｎＳｕｍ問題である。本発明の場合には、各ノードｖに対して、Ｔ（ｖ，ｆｖ）．ｓｉｚｅの値はｆｖの減少関数である（必ずしも、厳密な減少関数である必要はない。言い換えれば、この関数は、非増加関数である）。実際、ｆｖは許容可能なフリーライダー数の上限値であり、最小被覆の大きさは、該上限値の緩和に従い、（非厳密な意味で）減少する。
【０１９５】
【数５６】
2010158054.tif 000058
【０１９６】
とし、かつ
【０１９７】
【数５７】
2010158054.tif 000059
【０１９８】
が整数列であり、該整数列は、全てのｉについて、｜ａｉ−ａｉ−１｜および｜ｂｉ−ｂｉ−１｜が、所定の範囲Ａによって規定される、とする。
【０１９９】
【数５８】
2010158054.tif 000060
【０２００】
を満たす全てのｉについて、
【０２０１】
【数５９】
2010158054.tif 000061
【０２０２】
を満たすような配列ｃを出力するアルゴリズムＭｉｎＳｕｍ（（ａｉ），（ｂｉ），ε）が存在することは、当業者には明らかであろう。ａｉおよびｂｉが、（８）で規定するものであるならば、ｃ［ｉ］＝ｆＬｍｉｎ（ｉ＝ｆｖであり、自明ながらｆＬｍｉｎの値はｆｖによって決まる）である。ｃ［ｉ］の算出に要する時間計算量は、範囲Ａに関する増加関数である。
【０２０３】
定理  
【０２０４】
【数６０】
2010158054.tif 000062
【０２０５】
ならば、ＭｉｎＳｕｍの時間計算量は
【０２０６】
【数６１】
2010158054.tif 000063
【０２０７】
である。
【０２０８】
証明：
この場合に対するアルゴリズムは、本技術分野ではすでに周知されており、［１６］にも含まれる。このアルゴリズムは、［１５］に記載の技術の直接的なアプリケーションである。完全を期すために、ここに該アルゴリズムを説明する。（尚、本発明は、これ以外の任意のＭｉｎＳｕｍアルゴリズムを用いて実現可能であり、以下に記載するものでなくてもよく、本定理で与えられる時間計算量範囲を満たさなくてもよい。）
本アルゴリズムは、ｄ次元空間における、赤い点の集合と青い点の集合間の全重要対を探し出すサブルーチンを使用する。ｉ∈［ｄ］を満たす全てのｉについてｐｉ＜ｑｉが成り立つならば、および成り立つ場合に限り、赤い点ｐ＝（ｐ１，．．．，ｐｄ）および青い点ｑ＝（ｑ１，．．．，ｑｄ）は重要対を成す。ここで、［ｄ］は１以上ｄ以下の全ての整数の集合を指す。以下に、［１５］の補題２．１を示す。
【０２０９】
補題４
ｄ次元空間上に、ｎ個の赤または青の点が与えられた場合、ｃε＝２ε／（２ε−１）とすると、ε∈（０，１）を満たす任意の定数εについて、Ｋ個の重要対の検出を
【０２１０】
【数６２】
2010158054.tif 000064
【０２１１】
の時間で行うことができる。
【０２１２】
本補題のＭｉｎＳｕｍ応用については、［１６］に示されている。十分に微小な定数δについて、ｄ＝δｌｏｇ（ｍ１＋ｍ２）とする。この考え方により、２つの点集合｛ｐｉ｝および｛ｑｊ｝が定義される。すなわち、
｛ｐｉ＝（ａｉ−ａｉ−ｄ，ａｉ−ａｉ−ｄ＋１，．．．，ａｉ−ａｉ＋ｄ）｜全てのｉ｝
｛ｑｉ＝（ｂｊ＋ｄ，−ｂｊ，ｂｊ＋ｄ−１−ｂｊ，．．．，ｂｊ−ｄ−ｂｊ）｜全てのｊ｝。
【０２１３】
次に、両集合間に重要対を算出する。ａｉ−ａｉ′＜ｂｋ−ｉ′−ｂｋ−ｉならば、およびその場合に限り、ａｉ＋ｂｋ−ｉ＜ａｉ′＋ｂｋ−ｉ′であるため、（ｐｉ，ｑｋ−ｉ）という重要対が得られるならば、ａｉ＋ｂｋ−ｉ＝ｍｉｎｉ＝ｄ，．．．，ｉ＋ｄ（ａｉ′＋ｂｋ−ｉ）′である。一般的な摂動法により、任意のｉ′≠ｉ″に対してａｉ′＋ｂｋ−ｉ′≠ａｉ″＋ｂｋ−ｉ″が成り立つことが保証できる。これにより、多くともＯ（（ｍ１＋ｍ２）ｍｉｎ（ｍ１，ｍ２）／ｄ）＝Ｏ（ｍ１ｍ２／ｄ）個の重要対が存在しうることが導かれ、よって、補題４より、δを十分に微小な定数とすると、これらの全ての対は、Ｏ（ｍ１ｍ２／ｌｏｇ（ｍ１＋ｍ２））の時間で探し出すことができる。最後に、わずかＯ（ｍｉｎ（ｍ１，ｍ２）／ｄ）個の期間、すなわち重要対によって与えられる期間の最小値をとることにより、ＭｉｎＳｕｍはその配列ｃの各エントリを出力できる。従って、合計時間は、所望のＯ（ｍ１ｍ２／ｌｏｇ（ｍ１＋ｍ２））となる。
【０２１４】
合流点
付録２および３の各メソッドに戻ることにより、以下のような一層の最適化が達成できる。図１４は、完全二分木９１０の一部を示す。頂点ｖは、失効した子ｖ１およびｗ１を持つ。連続する頂点ｖ１，ｖ２，．．．，ｖｍは、失効した葉ノードに至る経路上の頂点である（ｖｍは葉ノードであっても、そうでなくてもよい）。頂点ｖ２′，．．．，ｖｍ′は頂点ｖ２，．．．，ｖｍそれぞれの兄弟ノードである。これらの兄弟ノードは、失効していない。
【０２１５】
ここで、フリーライダーの最適な割当により、ノードｖ１に対して、許容可能なフリーライダーの最大数
【０２１６】
【数６３】
2010158054.tif 000065
【０２１７】
が割り当てられるとする。この場合、ｖ２′は失効していないので、最適な割当を行えば、ｖ１に割り当てられたフリーライダーは、全てｖ２に割り当てられることになる。すなわち、
【０２１８】
【数６４】
2010158054.tif 000066
【０２１９】
としなくてはならない。これは、
【０２２０】
【数６５】
2010158054.tif 000067
【０２２１】
を実行する際に、付録２のステップ（３ａ）において、値ｆＬｍｉｎがｆＬｍｉｎ＝０である場合に対応する。従って、ステップ（３ａ）において通常の最小値問題（ＭｉｎＳｕｍ）を解く必要がなくなる。（さらに、ステップ（３ｂ）においてＴＬ．ｓｉｚｅ＝１，ＴＬ．ｃｏｖｅｒ＝ｖ２′とできる）。一方、ノードｖ２が左の子であったら、
【０２２２】
【数６６】
2010158054.tif 000068
【０２２３】
とすることになる。
【０２２４】
実際には、値
【０２２５】
【数６７】
2010158054.tif 000069
【０２２６】
は、頂点列ｖ２，．．．，ｖｍにおける全てのノードに割り当てられねばならない。ノードｖ１に対する最適被覆は、集合ｖ２′，．．．，ｖｍ′を、ノードｖｍに対する最適被覆に追加することにより、直接算出できる。
【０２２７】
同様に、連続する頂点ｗ１，ｗ２，．．．，ｗｓは、ｗ１から失効した葉ノードに至る経路上の頂点である（ｗｓは葉ノードであっても、そうでなくてもよい）。頂点ｗ２，．．．，ｗｓの兄弟ノードであるｗ２′，．．．，ｗｓ′は、失効していない。最適な割当を行えば、ｗ１に割り当てられたフリーライダーの数の上限値
【０２２８】
【数６８】
2010158054.tif 000070
【０２２９】
が、ｗ２，．．．，ｗｓの全てのノードに割り当てられることになる。ノードｗ１に対する最適被覆は、ノードｗｓに対する最適被覆から、直接算出できる。
【０２３０】
ここで、ノードｖを「合流点」（失効したノードｖｍおよびｗｓのそれぞれから根に至る両経路が合流する点）と呼ぶことにする。一般に、合流点とは、直下の子の双方が失効している内部ノードのことである。さらに、失効した葉ノードもまた、合流点と呼ぶ。
【０２３１】
合流点は、以下のように定義することもできる。本技術分野においては、重み付けがされていない木ＴＲにおける、頂点の部分集合Ｓのシュタイナー木Ｔが、Ｓの各頂点を含む最小の大きさの木として一意的に決まることを思い出されたい。ここで、完全二分木９１０の部分集合Ｒのシュタイナー木Ｔを算出するとする。図１５に、完全二分木９１０の例を示し、図１６に、それに対応するシュタイナー木を示す。シュタイナー木は、単純に完全二分木９１０から、失効していないノード（すなわち、失効していない葉、および失効していない葉から根に至る経路上の任意のノード）、およびこれらの失効していないノードに至る任意のエッジを取り除くことにより、算出できる。（例えば、シュタイナー木は、以下のようにして算出できる。まず、失効していない葉に印をつける。次に、木を上方向に遡り、両方の子に印がついている内部ノードに印をつける。最後に、印のついた全てのノード、およびこれらノードに至る任意のエッジを取り除く。）その後、各合流点は、Ｔの葉（図１６におけるノード１０，１３，１４および１５）、および完全二分木９１０の内部ノードｖであり、かつＴにおいてＬ（ｖ）およびＲ（ｖ）がいずれも空でないノード（図１５のノード１，３および７）と定義される。本明細書中では、後者のノードを内部合流点と呼ぶ。
【０２３２】
上記の考察と図１４とを合わせて考えれば明らかなように、これら合流点の最適被覆を算出すれば、それで十分である。（ｒについての帰納により、証明されうるように）合流点の数は２ｒ−１であるから、漸近的時間計算量を削減できる。
【０２３３】
付録５は、付録２のＯｐｔｉｍａｌＣｏｖｅｒメソッドの変形例である
【０２３４】
【数６９】
2010158054.tif 000071
【０２３５】
メソッドを示している。ここで、εは式（１０）の通りである。付録５のメソッドでは、ステップ３において合流点しか走査しない。葉ではない各合流点ｖについて、関数ＭＰｌｅｆｔ（ｖ）は、ｖの左の部分木Ｌ（ｖ）における、最下層の合流点を返す。関数ＭＰｒｉｇｈｔ（ｖ）は、右の部分木Ｒ（ｖ）における、最下層の合流点を返す。尚、任意の部分木において、最下層の合流点は一意的に決定される。実際、最下層に２つの合流点ｖ１およびｖ２が存在すると仮定すると、これらの合流点から部分木の根に至る両経路は、さらに下の階層の別の合流点で合流することになる。しかし、部分木の根に至る両経路の全体、従って両経路の合流点は、部分木内に存在せねばならないことから、この仮定からは矛盾が生じたことになる。
【０２３６】
付録５のステップ（３ａ）において、ε＞０ならば、εよりも小さくなりうるパラメータε′を使って、最適被覆
【０２３７】
【数７０】
2010158054.tif 000072
【０２３８】
を求める。根（ｖ＝１）に対するε値を用いて、最適性条件（１０）を求めるため、ステップ（３ａ）において、部分木に対してより小さな値であるε′値を使う必要があるかもしれない。これについては後で、付録１０と関連して、さらに深く説明する。
【０２３９】
付録５のステップ（３ｂ）に関して、ノードｖに対する最適被覆は、ノードｘおよびｙと、ｘおよびｙからｖに至る両経路それぞれの上にあるノードｘおよびｙの兄弟ノードに対する複数の被覆の和である。（すなわち、図１４においては、ｖに対する最適被覆は、ｖｍおよびｗｓとｖ２′，．．．，ｖｍ′およびｗ２′，．．．，ｗｓ′に対する複数の最適被覆の和である）。ここで、兄弟ノードを、Ｃｏｎｏｄｅｓと表す。すなわち、ｘ∈Ｔ（ｖ）を満たす任意のノードｘについて、Ｃｏｎｏｄｅｓ（ｘ，ｖ）は、ｘからｖに至る経路上の全ノード―ただし、ｘは含むが、ｖは含まない−の兄弟ノードの集合を表す。ｖが根である場合には、ｖを省略できる。すなわち、Ｃｏｎｏｄｅｓ（ｘ）＝Ｃｏｎｏｄｅｓ（ｘ，１）である。
【０２４０】
ここで、｜Ｃｏｎｏｄｅｓ（ｘ，ｖ）｜＝ｈｅｉｇｈｔ（ｘ）−ｈｅｉｇｈｔ（ｖ）であることは自明である。
【０２４１】
根は、合流点であっても、そうでなくてもよいため、付録１のメソッドを、付録６に示すように変形することにより、完全二分木９１０内で最下層の合流点ｖＭを求めることができる（付録６のステップ２Ａ）。
【０２４２】
付録７は、付録３のＯｐｔｉｍａｌＣｏｖｅｒＳｉｚｅを変形することにより得られるメソッドＯｐｔｉｍａｌＣｏｖｅｒＳｉｚｅＭを示している。尚、ステップ４のみ示す。付録８は、付録４のＦｒｅｅＲｉｄｅｒｓを変形することにより得られるメソッドＦｒｅｅＲｉｄｅｒｓＭを示している。両メソッドにおいて、合流点のみが走査される。
【０２４３】
一実施形態においては、最適被覆を算出する前に、合流点の順序リストが作成される。この際の順序は、高さの増加順または減少順のいずれでもよい。同じ高さの合流点は、任意の順番で現れうる。これにより、合流点の走査をより効率的に実施できる。以下、そのような方法について説明する。
【０２４４】
以下の方法においては、ｒ＞１であると想定する。ｒ＝１ならば、証明するまでもないためである（権限の失効したユーザがただ１人ならば、単にそのユーザをフリーライダーにすることで、最適解を求めることができる）。また、さらに
【０２４５】
【数７１】
2010158054.tif 000073
【０２４６】
であるとする。
【０２４７】
合流点を求める方法
ｒ＞１より、シュタイナー木Ｔ（図１６）の根を、内部合流点に定めることができる。（図１５の木のような）完全二分木９１０における、比較的低い高さの合流点に、Ｔの根を定めることを選択する。すでに説明した通り、このような合流点は、一意的なものである。
【０２４８】
付録９に、合流点算出のためのメソッドの一実施形態を示す。ここで、本発明のアルゴリズムに与えられる権限の失効した集合Ｒは、｛ｎ，ｎ＋１，．．．，２ｎ−１｝の範囲内の整数リストであると、一般性を失うことなく想定できる。図９を参照されたい。例えば、図１５において、Ｒ＝｛１０，１３，１４，１５｝である。まず、Ｒの入力リストがソートされていない可能性があるため、Ｒに対して有効なソートアルゴリズムｓｏｒｔを適用する。付録９のステップ１を参照されたい。本技術分野において最も周知された整数ソートアルゴリズムの場合、期待時間で
【０２４９】
【数７２】
2010158054.tif 000074
【０２５０】
［１９］、最悪の時間ではＯ（ｒｌｏｇｌｏｇｒ）［１８］で、実行される。ただし、Ｏ（ｒｌｏｇｒ）またはＯ（ｒｌｏｇｌｏｇｎ）の時間で実行されるより実用的なアルゴリズムも、本技術分野において周知であり、これらは、基本的なアルゴリズム［１７］またはヴァンエムデボアズ（ｖａｎ  Ｅｍｄｅ  Ｂｏａｓ）木に依拠してもよい。
【０２５１】
説明のため、ｒ個の点を含む線（図１５の完全二分木９１０に対応する、図１７の４個の点１０，１３，１４および１５を持つ線など）を描くことによって、本発明の合流点算出のためのアルゴリズム方法を視覚化してもよい。ｉ番目の点は、ｕｉ、すなわち、与えられたソート済リストにおいてｉ番目の、権限が失効したユーザである。エッジ（ｕｉ，ｕｉ＋１）に対するラベル付けは、以下のように行われる。ａ＝ａ（ｕｉ，ｕｉ＋１）を見つけると、（ｕｉ，ｕｉ＋１）にａおよびｈｅｉｇｈｔ（ａ）をラベル付けする。ｈｅｉｇｈｔ（ａ）を、エッジの重みと呼ぶ。これに従い、図１７において、エッジ（１０，１３）にはａ＝１およびｈｅｉｇｈｔ（ａ）＝０、ｅｄｇｅ（１３，１４）にはａ＝３およびｈｅｉｇｈｔ（ａ）＝１、といった形でラベルが付される。尚、ａおよびその高さは、ｕｉおよびｕｉ＋１の二進展開（すなわち、二進法表示）に対して二分探索法を適用することにより、Ｏ（ｌｏｇｌｏｇｎ）の量の算術演算を用いて求めることができる。よって、ａはｕｉ∈Ｌ（ａ）かつｕｉ＋１∈Ｒ（ａ）である内部合流点である。
【０２５２】
本発明では、エッジとそれに対応する対（ａ，ｈｅｉｇｈｔ（ａ））のソート済リストＥを保持する。付録９（ステップ２）において、エッジはｅと表わされている。ステップ３において、該リストを、高さの減少順にソートする。図１７は、図１５に対するリストＥの初期状態を示す。合流点の出力リストＭＰも保持されている。付録９のステップ１において、ＭＰは初期化され、失効したユーザの集合（図１７の｛１０，１３，１４，１５｝）に設定される。次に、任意に結合を切断し、リストＥにおいて重みが最大のエッジｅ＝｛ｕ，ｖ｝（図１７においては、ｅ＝｛１４，１５｝）を検出し（付録９のステップ（４ａ））、ＭＰの最後尾にａ（ｕ，ｖ）を追加し、Ｅからｅを削除する（ステップ（４ｂ））。この処理は、線上のエッジ｛ｕ，ｖ｝を崩壊させ、頂点ａ（ｕ，ｖ）に置換することに対応する。図１８を参照されたい。図１８は、一回目の反復後の変数の状態を示している。ステップ（４ｃ）において、ｕまたはｖを含む各エッジｅ′について、ｕまたはｖをａ（ｕ，ｖ）に置換し、その重みと先祖識別子ｅ′．ｗ，およびｅ′．ａを更新する。付録Ａのステップ（４ｃ）を参照されたい。いずれの反復中においても、残るエッジの「線構造」Ｅが保存されるため、線上の任意の頂点ｕは、多くとも２本のエッジに属することができており、よって本更新ステップが効率的に実行できたことが分かるであろう。ｒ−１回の削除が行われると、線の全体が崩壊して、単一の頂点、すなわちシュタイナー木の根となり、処理は終了する。
【０２５３】
まず、ＭｅｅｔｉｎｇＰｏｉｎｔｓの幾つかの特徴を証明する。これらの特徴は、本アルゴリズムの正確性や所要時間条件を具体的に示すために含まれるものである。本発明は、これらの特徴を考慮せずに実行してよい。
【０２５４】
補題５
ＭＰ内のノードは、高さの非昇順にソートされる。
【０２５５】
証明：
これが真ではない、と仮定する。ＭＰ内で、頂点ｖの前に最初に現れる、ｈｅｉｇｈｔ（ｕ）＜ｈｅｉｇｈｔ（ｖ）である頂点ｕを考える。ｕおよびｖは内部合流点であるので、それぞれ、何らかのエッジｅおよびｅ′＝｛α，β｝∈Ｅを崩壊させることにより、ＭＰに追加されることになる。ｕをＭＰに追加する反復、すなわちＥからｅを削除する反復を考える。ｅ′．ｗ＝ｈｅｉｇｈｔ（ｖ）＞ｈｅｉｇｈｔ（ｕ）＝ｅ．ｗより
【０２５６】
【数７３】
2010158054.tif 000075
【０２５７】
であり、Ｅはソートされているので、ｅではなくｅ′が選択されることになる。しかし、ｅ′はいずれＥ内に現れるものであり、ｅ″．ａがαまたはβの子孫であるようなエッジｅ″∈Ｅは必ず存在する。よって、ｅ″．ｗ＞ｅ．ｗであるが、これは矛盾している。
【０２５８】
系６
エッジは、重みに関して非減少順にＥから削除される。
【０２５９】
次の補題は、Ｅの「線構造」が保存されることを示している。各エッジＥ＝｛ｕ，ｖ｝について、ｕがｖの左側にあるならば、該エッジを（ｕ，ｖ）と記述する。
【０２６０】
補題７
Ｖ＝Ｖ（Ｅ）が、任意の固定反復の間にＥ内の何らかのエッジ内に現れるノードを指すとする。グラフＧ＝（Ｖ，Ｅ）は線であり、ｕ＜ｖ（ともに整数）かつ、ｕおよびｖ∈Ｖならば、ｕはｖの左側にある。
【０２６１】
証明
この特徴は、構造上、ステップ（３）の最後においては保たれている。本特徴が、さらに維持されることを確認するため、何らかの反復中に、ｅ＝（ｕ，ｖ）がＥから削除される場合を想定されたい。ステップ（４ｃ）において、Ｅ内で変更されるのは、わずか２つのエントリ、すなわち、（ｕ′，ｕ）の形のエッジおよび（ｖ，ｖ′）の形のエッジ、に過ぎない。これらのエッジは、存在する場合には、それぞれ（ｕ′，ａ（ｕ，ｖ））および（ａ（ｕ，ｖ），ｖ′）に変更される。これにより、ｕ′がａ（ｕ，ｖ）の左側にあることが分かるであろう。ａ（ｕ，ｖ）がｖ′の右側にあることの証明についても同様である。
【０２６２】
ｅが削除される前までは、本特徴が保たれることから、ｕ′はｕの左側にある。ｅは（ｕ′，ｕ）より前に削除されているため、系６より、ｈｅｉｇｈｔ（ａ（ｕ′，ｕ））＞ｈｅｉｇｈｔ（ａ（ｕ，ｖ））となる。従って、ａ（ｕ，ｖ）∈Ｒ（ａ（ｕ′，ｕ））あるいはａ（ｕ，ｖ）＝ａ（ｕ′，ｕ）である。ここで、ａ（ｕ，ｖ）∈Ｒ（ａ（ｕ′，ｕ））のとき、ｕ′はａ（ｕ，ｖ）の左側にある。しかし、該木は二分木であり、｛ｕ′，ｕ，ｖ｝のうち２つの要素は、必ずＬ（ｖ）またはＲ（ｖ）に現れることから、ａ＝ａ（ｕ，ｖ）＝ａ（ｕ′，ｕ）ならば、ｕ′がｕの左側にあることはなく、またｕがｖの左側にあることもない。よって、ｕ′とｕに共通の、最上層の先祖がａであることはない。以上述べた特徴により、ＭｅｅｔｉｎｇＰｏｉｎｔｓの出力を解析できる。
【０２６３】
補題８
ＭＰは、合流点の集合そのものである。
【０２６４】
証明
まず、全ての合流点がＭＰ内に現れる、と提起する。これは、集合Ｒに対しては明らかに真であり、よって、逆に何らかの内部合流点ｖがＭＰ内に現れない、と仮定する。ｖを最上層のノードとする。さらに、ｐｌをＬ（ｖ）においてｖに最も近接した合流点とし、ｐｒも同様に定義する。すると、ｖが最上層にあることから、ｐｌおよびｐｒはともにＭＰ内に現れる。
【０２６５】
さらに、万一エッジ（ｐｌ，ｐｒ）がＥ内に現れるならば、ｖ∈ＭＰである、と提起する。実際、そうでない場合、ｐｌまたはｐｒのいずれかが、ｖ以外の先祖に置換されていることになる。しかし、ａ（ｐｌ，ｐｒ）＝ｖより、ｐｌまたはｐｒの任意の先祖ａは、ｖの子孫または先祖のいずれかであり、かつ、ｐｌからｖに至る経路およびｐｒからｖに至る経路上にはその端部点を除き、合流点は含まれないため、ａはｖの先祖でなければならない。しかし、この場合、ａがＭＰに追加される際に結ばれるエッジが、（ｐｌ，ｐｒ）よりも大きな重みを持つことになり、これは系６と矛盾する。
【０２６６】
最後に、（ｐｌ，ｐｒ）がＥ内に現れることを証明する。ｐｌがＭＰに追加された直後の反復を想定されたい。すると、ｐｒは、その後にＭＰに追加されるので、ｗ∈Ｔ（ｐｒ）である何らかの頂点ｗが必ず存在することになる。必然的に、ｐｌはｗの左側にあるので、補題７より、（ｐｌ，ｗ′）∈Ｅであるエッジ（ｐｌ，ｗ′）が存在する。尚、ａ（ｐｌ，ｗ′）はｐｌの先祖であり、かつｐｌはｖに最も近接しているため、
【０２６７】
【数７４】
2010158054.tif 000076
【０２６８】
が成り立つ。よって、ｈｅｉｇｈｔ（ｐｒ）＜ｈｅｉｇｈｔ（ｖ）より、ｐｒがＭＰに追加されるまで、（ｐｌ，ｗ′）がＥから削除され得ない。よって、ｗ′は、
【０２６９】
【数７５】
2010158054.tif 000077
【０２７０】
を満たす整数であり、よって
【０２７１】
【数７６】
2010158054.tif 000078
【０２７２】
である。これによりｈｅｉｇｈｔ（ｖ）＝ｈｅｉｇｈｔ（ａ（ｐｌ，ｗ′））であり、かつｐｌが、所与の階層の先祖をただ１つしか持ち得ないことから、ａ（ｐｌ，ｗ′）＝ｖである。これは、ｗ′∈Ｒ（ｖ）、従ってｗ′＝ｐｒであるｗ′、すなわちｐｒが、Ｒ（ｖ）においてｖに最近接する合流点ではないことを意味している。ゆえに、（ｐｌ，ｐｒ）∈Ｅとなり、証明が成立した。
【０２７３】
各合流点ｖについて、Ｌ（ｖ）およびＲ（ｖ）において、それぞれ一意的に決まるｖに最近接する合流点ｐｌおよびｐｒが、合流点のリスト内でｖの前に現れるならば、そのリストは順序リストであると言える。次の補題は、補題５および補題８から直接導き出されるものである。
【０２７４】
補題９
ＭＰは順序リストである。
【０２７５】
これまでの結論をまとめる。
【０２７６】
定理１０
ＭｅｅｔｉｎｇＰｏｉｎｔｓは、合流点の順序リストを、Ｏ（ｒｌｏｇｌｏｇｎ）の時間で出力する。
【０２７７】
証明：
補題８および９より、あとは、時間計算量を示せばよい。あるノードｕおよびｖについて、ａ（ｕ，ｖ）およびｈｅｉｇｈｔ（ａ（ｕ，ｖ））の両方を算出する場合、二分探索法を用いて、例えば、べき乗数２ｉで割り、等値を調べることにより、Ｏ（ｌｏｇｌｏｇｎ）の演算で、算出可能であることは、容易に理解されるであろう。したがって、ステップ（１〜３）はＯ（ｒｌｏｇｌｏｇｎ）の時間で実行可能である。ステップ（４）に関しては、初期状態では｜Ｅ｜＝ｒであり、｜Ｅ｜は、反復の毎に１減少することに留意されたい。さらに、補題７より、ステップ（４ｃ）において、多くとも２個の異なるｅ′が現れることがわかる。また、ステップ（４ｃｉｉｉ）は、標準的なヴァンエムデボアズ木を用いて、一回の実行につきＯ（ｌｏｇｌｏｇｎ）の時間で実行されうる。従って、時間計算量の合計は、Ｏ（ｒｌｏｇｌｏｇｎ）である。
【０２７８】
フリーライダーの最適または略最適な集合を算出する方法
付録１０に、ＭｅｅｔｉｎｇＰｏｉｎｔｓおよびＭｉｎＳｕｍをサブルーチンとして利用するＦｒｅｅｒｉｄｅｒ−Ａｐｐｒｏｘメソッドを示す（上述のＭｉｎＳｕｍの節を参照）。ここで、（１０）において、ε＝０の時、ＭｉｎＳｕｍアルゴリズムは、
【０２７９】
【数７７】
2010158054.tif 000079
【０２８０】
の時間で、正確な解を生むことを付言したい。ε＞０を許容すれば、（１０）の解はもはや最適ではない（ただし、ほぼ最適であるかもしれない）が、より高速なアルゴリズムを得ることができるかもしれない。
【０２８１】
整数ｉおよび任意の木Ｓについて、ｏｐｔ（ｉ，Ｓ）が、多くともｉ人のフリーライダーを木Ｓに割り当てる際の最適なコスト（最小被覆の大きさ）を表すとする。
【０２８２】
ここで、近似エラーについて簡単に説明する。最適な割当コストの多くとも（１＋ε）倍のコストを伴うフリーライダーの割当が目的であると想定されたい。Ｒに対するシュタイナー木Ｔ内の任意の単純路が、多くともｍｉｎ（ｒ，ｌｏｇｎ）の長さを有することは明らかである。付録１０のステップ２において実行されるように、
【０２８３】
【数７８】
2010158054.tif 000080
【０２８４】
とおく。動的計画法における各ステップについて、パラメータε′を用いてＭｉｎＳｕｍを呼び出すならば、Ｆｒｅｅｒｉｄｅｒ−Ａｐｐｒｏｘによって求められた最終的な割当数が、最適な数の多くとも（１＋ε′）倍であると証明できる。
【０２８５】
【数７９】
2010158054.tif 000081
【０２８６】
である各頂点ｖ∈ＭＰ＝ＭｅｅｔｉｎｇＰｏｉｎｔｓ（Ｒ）について、ｖ＝ａ（ｘ，ｙ）である２つの合流点ｘおよびｙが、定数時間で特定できるとする。これは、ポインタをＭｅｅｔｉｎｇＰｏｉｎｔｓの態様内に維持することにより容易に達成しうる。例えば、ＭＰ内の、内部合流点に対応する各エントリは、該合流点、ｖ、ＭＰ内の合流点ｘおよびｙのインデックス、を収容できる。このインデックスは、付録９のステップ（４ａ）および（４ｂ）において、ｅ＝｛ｘ，ｙ｝を選択し、ＭＰに追加するときに、格納されうる。ＭＰｌｅｆｔ（ｖ）をｘを返す演算、ＭＰｒｉｇｈｔ（ｖ）を、ｙを返す演算とする。
【０２８７】
本発明のアルゴリズムでは、各ノードｕは、自らに関連付けられた３つのデータフィールドｒｕ、ＡｕおよびＢｕを有する。上述の通り、ｒｕは木Ｔ（ｕ）における権限が失効したユーザ数を表す。Ａｕ［ｉ］は、図１０および１１におけるフィールド「ＴＢＬ１［ｕ，ｉ］．Ｓｉｚｅ」および「ＴＢＬ２［ｕ，ｉ］．Ｓｉｚｅ」と類似している。より正確には、Ａｕは、
【０２８８】
【数８０】
2010158054.tif 000082
【０２８９】
であるｉをインデックスとする配列であり、多くともｉ人のフリーライダーをＲ∩Ｔ（ｕ）に割り当てる際の、本発明のアルゴリズムによって求められるコストを記録するものである。（１０）より、
【０２９０】
【数８１】
2010158054.tif 000083
【０２９１】
最後に、ＢｕはＡｕと対をなす配列であり、ｆＬｍｉｎ値を格納する。多くともｉ人のフリーライダーをノードｕに割り当てるとき（図１１のＴＢＬ２［ｕ，ｉ］．ｆＬｍｉｎと類似）、Ｂｕ［ｉ］はｆＬｍｉｎ値である。より正確には、Ｂｕは、
【０２９２】
【数８２】
2010158054.tif 000084
【０２９３】
であるｉをインデックスとする配列であり、内部合流点ｕについて、以下の特徴が得られる。
【０２９４】
【数８３】
2010158054.tif 000085
【０２９５】
｜ＭＰ｜＝２ｒ−１であることに注目されたい。
【０２９６】
ステップ３（付録１０）において、失効した各ノードについて、ｒｕ値は１に設定され、Ａｕ［０］およびＡｕ［１］は０に設定される。
【０２９７】
ステップ４において、木の下から上に、すなわち、高さの減少順に、内部合流点を走査する。本ステップは、付録７のステップ４に類似しているが、再帰の必要はない。各合流点ｖについて、左右の最近接の合流点ｘおよびｙが、付録１０のステップ（４ａ）において求められる。ステップ（４ｂ）において、
【０２９８】
【数８４】
2010158054.tif 000086
【０２９９】
である各エントリＡｘ［ｊ］は、ｘおよびｖ間のノード−ノードｘおよびｖを含まないの兄弟ノードの数だけ増加される（ｘ＝ＬＶ（ｖ）ならば、このようなノード数は０である）。上述の図１４の説明を参照されたい。従って、Ａｘ［ｊ］は、多くともｊ人のフリーライダーをｖの左の子に割り当てる際の最適またはほぼ最適なコストに等しくなる。さらに、
【０３００】
【数８５】
2010158054.tif 000087
【０３０１】
かつ対応する最適コストが０でない（すなわち、Ｐ（ｘ）が空集合ではない）ならば、Ａｘ［ｒｘ］は１に設定される。
【０３０２】
（４ｃ）において、同様の演算がＡｙに対しても実施される。
【０３０３】
（４ｄ）において、ε′について
【０３０４】
【数８６】
2010158054.tif 000088
【０３０５】
である各ｊに関して、ｆＬｍｉｎ値であるＢｖ［ｊ］が算出される。
【０３０６】
（４ｅ）において、ｒｖ値が算出される。
【０３０７】
（４ｆ）において、
【０３０８】
【数８７】
2010158054.tif 000089
【０３０９】
を満たす各ｊについて、Ａｖ［ｊ］値が、ｊに対応するｆＬｍｉｎ値に対する、ｖの左右の子に課される最適またはほぼ最適なコストの合計値として算出される。ただし、
【０３１０】
【数８８】
2010158054.tif 000090
【０３１１】
であり、かつＡｖ［ｒｖ］が０ではないならば、Ａｖ［ｒｖ］は１に設定される。
【０３１２】
ステップ（５）が、合流点走査の後に実行される。本ステップは、多くともｆ人のフリーライダーについての最下層の合流点に、該合流点を始点として根ノードに至るノード（合流点を含む）の兄弟数を加えたノードに対する略最適な被覆のコストとして、合計のコストを出力するものである。
【０３１３】
ステップ（６）では、合流点を走査し、フリーライダーの割当数を出力する。一実施形態では、ステップ（６）は付録８と類似している。付録８のステップ（２Ａ）において、ｖＭは、単にＭＰ［２ｒ−１］と設定できる。ステップ（４ａ）において、条件Ｐ（ｖ）＝φはＡｖ［ｆｆ［ｖ］］＝０と置き換えることが可能である。ステップ（４ｃ１）において、右側のｆＬｍｉｎ値を、単にＢｖ［ｆｆ［ｖ］］とする。
【０３１４】
以下の定理は、ＦｒｅｅＲｉｄｅｒ−Ａｐｐｒｏｘメソッドが、最適コストの多くとも（１＋ε）倍のコストを伴うフリーライダー割当を生成することを、示すものである。やはり、本発明は、本定理（およびその証明）とは無関係に実現してよい。しかしながら、本発明が、実際に妥当かつ所定の性能限界の範囲内で正常に動作することを、所定の当業者に納得させるという説明上の目的で含まれている。
【０３１５】
定理１１
Ｆｒｅｅｒｉｄｅｒ−Ａｐｐｒｏｘは、最適割当のコストの多くとも（１＋ε）倍のコストを伴うフリーライダー割当を出力する。
【０３１６】
本定理の証明は、以下の補題１２および定理１３と同様、米国仮出願第６０／７３９，６５７号に記載されている。［２１］も参照されたい。
【０３１７】
補題１２
完全二分木体系における各ノードｖについて、かつ任意の０以上の整数ｉについて、Ｔ（ｖ）の葉に対して多くともｉ人のフリーライダーを最適に割り当てるコストは、多くともｉ＋１人を最適に割り当てるコストより、多くともｌｏｇｎだけ大きい。
【０３１８】
定理１３  
【０３１９】
【数８９】
2010158054.tif 000091
【０３２０】
ならば、Ｆｒｅｅｒｉｄｅｒ−Ａｐｐｒｏｘの時間計算量はＯ（ｒ（ｆ２／ｌｏｇｆ＋ｌｏｇｌｏｇｎ））である。
【０３２１】
以上、完全二分木−部分木手法を対象にした、最適なフリーライダー集合の算出方法を提示してきたが、同じ技術を他の木類似体系および非木類似体系に適用可能であることは、当業者には理解されるであろう。例えば、ｋ進体系を「２値化」、すなわち、ｋ次数のノードをｋ個の葉を有する木に置換することにより、本技術をｋ進体系に適用できる。同様に、Ｎａｏｒ，ＮａｏｒおよびＬｏｔｓｐｉｅｃｈの部分木−差分法（Ｓｕｂｓｅｔ−Ｄｉｆｆｅｒｅｎｃｅ  Ｍｅｔｈｏｄ）およびＳｈａｍｉｒおよびＨａｌｅｖｙの部分木階層化差分法（Ｌａｙｅｒｅｄ  Ｓｕｂｓｅｔ  Ｄｉｆｆｅｒｅｎｃｅ  Ｍｅｔｈｏｄ）に適用してもよい。主な変形箇所は動的計画法ステップ法になるが、この際、結合ノードに関連付けられた鍵が含まれるようにする点にのみ、注意が必要である。
【０３２２】
上述の方法は、様々な種類の専用および／または汎用コンピュータ・システム（電子レンジ、携帯電話などの機器に内蔵されるもの等）を用いて実行できる。このようなシステムは、図２Ａ〜６Ｂのシステム２１０，１０４，６１０および６２０に内蔵されるような従来技術のハードウェアに基づいてよい。コンピュータ・システムは、コンピュータの命令を実行する１つ以上のコンピュータ・プロセッサを含んでよく、また命令およびデータを格納するためのコンピュータ記憶装置（半導体メモリ、磁気または光ディスク、および／またはその他の種類の記憶装置）を含んでよい。従って、前記システムは、ハードウェア装置（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータ・システムまたは専用機械上で動作するもの等）、またはそれらの組み合わせであってよい。システムは、外部通信網インタフェースに接続されたプロセッサ、およびメモリを含んでよく、さらに前記プロセッサは、集合体と関連付けられた複数の鍵を用いて暗号化されたブロードキャストを受信し、（システムがまだ失効していないか、フリーライダー集合の一部であるならば）前記ブロードキャストを復号することが可能であってよい。ブロードキャストは、ブロードキャストヘッダーとデータ内容の２つの部分を備えてよい。ブロードキャストヘッダーは、ブロードキャスト暗号化方式に関連付けられた集合体に含まれる鍵を用いて、ブロードキャスト・セッション鍵を暗号化するものであり、データ内容は、セッション鍵を用いて暗号化されている。（まだ失効していない、またはフリーライダーの）クライアントコンピュータ・システムは、排他的集合体に含まれる１つ以上の鍵を通知される。排他的集合体に含まれる鍵は、ヘッダーの内容を復号し、セッション鍵を取得し、さらに送信のデータ内容を復号するために用いられる。
【０３２３】
コンピュータ・システムは、外部通信網インタフェースを含むサーバ、および外部通信網インタフェースおよびメモリに接続されたプロセッサであってよい。コンピュータ・システムは、インタフェースを通じて、（通常、ブロードキャスト暗号化システムに含まれる、失効していないユーザまたはフリーライダーがアクセス可能な鍵を用いて、ブロードキャスト・セッション鍵を暗号化する、ブロードキャストヘッダーと、セッション鍵を用いて暗号化されたデータ内容を備える）暗号化されたブロードキャストを送ることができる。さらにプロセッサは、失効していないユーザまたはフリーライダーと関連付けられた鍵を用いて、基盤となるブロードキャスト暗号化方式に基づき、ブロードキャスト送信を構築する。
【０３２４】
コンピュータ・システムは、コンピュータ・ユーザに情報を表示するバスに接続されたブラウン管（ＣＲＴ）ディスプレイまたは液晶ディスプレイ（ＬＣＤ）などの表示装置を含んでよい。さらに、英数字およびその他のキーを含む英数字入力装置が、プロセッサに情報および命令選択を伝達するバスに接続されていてもよい。追加のユーザ入力装置としては、プロセッサに方向情報や命令選択を伝達し、かつ表示装置上のカーソルの動きを制御するバスに接続されたカーソル制御がある。カーソル制御には、マウス、トラックボール、トラックパッド、スタイラス、またはカーソル方向キー等がある。
【０３２５】
尚、本発明において、システムおよび関連ハードウェアの構成要素のうち、任意またはすべてを用いてよい。ただし、コンピュータ・システムの他の構成が装置の一部またはすべてを含んでよいことが、理解されうるであろう。
【０３２６】
本発明は、前述の、および下記の付録に含まれる実施形態に限定されない。本発明は、特定の時間計算量範囲を満たすアルゴリズム、および特定のデータ値の利用に何ら限定されない。たとえば、パラメータｆＬｍｉｎは、ｆＲｍｉｎ＝ｆｖ−ｆＬｍｉｎに置き換えることができる。さらに、非二分木を、２値化すら行わずに利用する実施形態もある。このような実施形態の幾つかにおいては、各ノードｖについて、Ｔ（ｖ）に対する最適またはほぼ最適な被覆を提供するために、ｖの直下の子を根とする部分木ごとに、最適またはほぼ最適な被覆が求められる。また、一実施形態においては、コンピュータ・システム（例えば、サーバ）が、実体の集合ＵおよびＵの部分集合である対象集合Ｐを表すコンピュータ・データを取得する。該対象集合Ｐは、権限を保有するユーザの集合であってよく、または逆に、（例えば、該サーバが、権限が失効したユーザにのみ、何らかの情報、例えば何らかの広告提供、を送信することを希望する場合、または該サーバが、無効化された証明書に対する無効証明を送信することを希望する場合には）権限が失効したユーザの集合であってよい。さらに、該コンピュータ・データはまた、集合体ＣＣ（Ｕ）を表す。該集合体は、Ｕの部分集合の集合である。（定義２に示す通り、）集合体ＣＣ（Ｕ）は、必ずしも部分集合被覆である必要はない。例えば、一実施形態では、集合体ＣＣ（Ｕ）は、すべての単要素集合を含むとは限らない（単要素集合を何ら含まない場合すらある）ため、Ｕの部分集合Ｐの被覆Ｃ（Ｐ）を何ら提供しない。
【０３２７】
該集合体の各要素Ｓｉは、送信されるメッセージ（例えば、図４Ａにおける
【０３２８】
【数９０】
2010158054.tif 000092
【０３２９】
ｓまたは図６Ａにおけるｃｍ）を形成するために用いられ得るデータ（例えば、ｋＳ）に関連付けられてもよい。
【０３３０】
該コンピュータ・データはまた、前記対象集合Ｐに対するｆ＋冗長の被覆ＣＶ＝ＣＶ（ｆ，Ｐ）を構築する際に許容されるフリーライダーの正の最大数ｆを表す。例えば、ＣＶは、Ｔ（１，ｆ，Ｐ，Ｕ）であってよい。該コンピュータ・データが示す情報は、様々な形で表され得る。例えば、数ｆは、（１）によって与えられるパラメータによって規定することができ、また該コンピュータ・システムによって、該パラメータから算出できる。
【０３３１】
該コンピュータ・システムは、Ｒ＝Ｕ＼ＰであるＲの内、少なくとも０かつ多くともｆ個の実体をフリーライダーと指定することにより、フリーライダー割当を行う。フリーライダー割当を行う工程は、前記集合体ＣＣ（Ｕ）の要素である少なくとも１つの部分集合ｖについて、および
【０３３２】
【数９１】
2010158054.tif 000093
【０３３３】
である少なくとも１つの正数ｆｖについて、ｖに対するｆｖ＋冗長の被覆のコストを決定する工程を有する。任意の被覆に対するコストは、該被覆内の要素数に関する、定数ではない非減少関数である。一実施形態では、任意の被覆のコストは、該被覆内の要素数そのものである（非減少関数が恒等関数である）が、その他の選択肢も可能である。
【０３３４】
ｖに対するｆｖ＋冗長の被覆のコストを決定する工程は、以下の工程を有する。
【０３３５】
Ａ．ｖの部分集合であり、かつ系ＣＣ（Ｕ）の要素である、空集合ではない互いに素の部分集合ｘ１，ｘ２，．．．を決定する工程。例えば、付録２のステップ３において、ｘ１はＬ（ｖ）内の全ユーザ（葉ノード）の集合であり、またｘ２はＲ（ｖ）内の全ユーザの集合である。付録１０においては、ｘ１はＴ（ｘ）内の全ユーザの集合であり、またｘ２はＴ（ｙ）内の全ユーザの集合である。
【０３３６】
Ｂ．０以上の整数ｆ１，ｆ２，．．．の２つ以上の組（ｆ１，ｆ２，．．．）を選択する工程。各組に含まれる数の和はｆｖ以下であり、各組は、ｉ＝１，２，．．．である各ｉについて、ｖに対するｆｖ＋冗長の被覆を取得するための多くともｆｉ人のフリーライダーのｘｉへの割当候補を示す。例えば、付録２においてｆ１＝ｆＬおよびｆ２＝ｆＶ−ｆＬである。付録１０のステップ（４ｄ）においては、ｆ１およびｆ２は、ＭｉｎＳｕｍが最小（またはほぼ最小）の和Ａｘ［ｆ１］＋Ａｙ［ｆ２］を求めるときに用いるインデックスである。また、付録２および１０において、ｆ１およびｆ２の全ての組み合わせについて、ｆ１＋ｆ２＝ｆｖとされているが、一実施形態においては、数ｆ１，ｆ２，．．．の和はｆｖより小さいことがある。
【０３３７】
Ｃ．前記組から、対応する割当候補がｖに対するｆｖ＋冗長の被覆の最適性コストとなる組を選択する工程。ここで、最適性コストとは、最小コストに対して、予め定義された最適性関係を有するコストである。一実施形態では、
【０３３８】
【数９２】
2010158054.tif 000094
【０３３９】
が予め定義されているときに、最適性コストは、最小コストの多くとも（１＋ε）倍のコストである。一実施形態では、ε＜１である。
【０３４０】
一実施形態では、要素ｖ、ｘ１およびｘ２は合流点である。上述では、合流点を、木データ構造（図１４）の文脈において定義したが、本発明は、木を用いずに説明することが可能である。ＣＣ（Ｕ）における親−子関係を、以下のように定義できる。ＣＣ（Ｕ）の要素ｅ１が、ｅ２∈ＣＣ（Ｕ）である要素ｅ２の真部分集合であるならば、ｅ１はｅ２の子である。要素ｅ１がｅ２の真部分集合であり、かつ真部分集合としてｅ１を含みかつｅ２の真部分集合であるような要素ｅ３がＣＣ（Ｕ）に存在しないならば、ｅ１はｅ２の直下の子である。合流点とは、（ａ）ＣＣ（Ｕ）において、各々がＲの要素である少なくとも２つの直下の子を有するか、または（ｂ）Ｒの要素である単一の実体から構成されるかのいずれかである体系ＣＣ（Ｕ）の要素である。
【０３４１】
一実施形態では、空集合ではない互いに素の部分集合ｘ１，ｘ２，．．．を特定する工程は、ｖの真部分集合である少なくとも２つの合流点を探索し、前記探索の結果、ｘ１およびｘ２を検出する工程を有する。例えば、付録７または１０のステップ（４ａ）を参照されたい。
【０３４２】
一実施形態では、工程Ａ〜Ｃは、複数の正数ｆｖに対して行われ、前記数ｆｖのうち１つが選択されることにより、被覆ＣＶ（ｆ，Ｐ）のほぼ最適なコストを提供する。例えば、付録２において、ｆｖを選択することは、ｆＬｍｉｎを選択することに対応する。付録１０において、この選択は、ステップ（４ｄ）で行われる。
【０３４３】
一実施形態では、合流点の順序集合ＭＰを算出する方法を提供する。合流点は高さ順、すなわち、高さの非減少順または非増加順、に並べられている。合流点の高さは、合流点を始点とし、ＣＣ（Ｕ）のいずれの要素の部分集合でもない要素を終点とする連鎖の要素における、ＣＣ（Ｕ）の要素の数を表し、連鎖の最後の要素を除く各要素は、連鎖における次の要素の直下の子である。一実施形態では、最後の要素は、集合Ｕである。
【０３４４】
一実施形態では、すべての合流点の集合ＭＰを算出する工程は、以下の工程を有する。
（１）集合ＭＰを、ｒ＞１としたときに各要素ｕｉ（ｉ＝１，２，．．．，ｒ）がＲの単要素から成るように、ＣＣ（Ｕ）の要素列ｕ１，ｕ２，．．．，ｕｒに初期化する工程。付録９の実施形態では、ステップ１において、この列は完全二分木（図１５）における位置の順（左から右）にソートされる。しかしながら、本発明は、木を参照しなくとも定義できる。ｖ∈ＣＣ（Ｕ）であるｖがｕｉとは異なる要素であり、Ｒの単要素から成るような要素ａ（ｕｉ，ｖ）を考えた場合に、単要素集合ｕ１，ｕ２．．．の列は、各要素ｕｉについて、ａ（ｕｉ，ｕｉ＋１）またはａ（ｕｉ−１，ｕｉ）のいずれかが、全要素ａ（ｕｉ，ｖ）のうちの最大の高さを持つような何らかの順番に並べられ得る。ここで、ＣＣ（Ｕ）の任意の２つの要素ｕおよびｖについて、ａ（ｕ，ｖ）は、ｕおよびｖの双方を含む要素すべてのうち最大の高さをもつＣＣ（Ｕ）の要素を表す。
（２）ＣＣ（Ｕ）の要素の対の集合Ｅを定義し、集合Ｅを、隣接する要素の対｛ｕｉ，ｕｉ＋１｝のすべてから成る集合に初期化する工程。ここで、ｉ＝１，．．．，ｒ−１である。
（３）集合Ｅから、要素ａ（ｕｉ，ｕｉ＋１）がＥの全ての対のうち最大の高さを持つような対｛ｕｉ，ｕｉ＋１｝を取り除く工程。
（４）取り除かれた対の代わりに、要素ａ（ｕｉ，ｕｉ＋１）を集合ＭＰに追加する工程。
（５）集合Ｅが、工程（３）における要素ｕｉまたはｕｉ＋１を備える少なくとも１つの対を、依然として含むならば、そのような少なくとも１つの対の各々における要素ｕｉまたはｕｉ＋１の各々を工程（４）における要素ａ（ｕｉ，ｕｉ＋１）に置換する工程。
【０３４５】
本発明は、特定のデータ構造または操作に限定されない。添付の特許請求の範囲に規定される通り、他の実施形態および変形例も本発明の範囲に含まれる。
【０３４６】
以下の引用文献は、参照により本明細書に援用される。これらの引用文献は、本願に関する先行技術であるものと、そうでないものがある。
［１］Ｍ．Ａｂｄａｌｌａ、Ｙ．ＳｈａｖｉｔｔおよびＡ．Ｗｏｏｌ。Ｋｅｙ  Ｍａｎａｇｅｍｅｎｔ  ｆｏｒ  Ｒｅｓｔｒｉｃｔｅｄ  Ｍｕｌｔｉｃａｓｔ  Ｕｓｉｎｇ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ。ＡＣＭ  Ｔｒａｎｓ．ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ、ｖｏｌ．８、ｎｏ．４、４４３−４５４頁、２０００年。
［２］Ｗ．Ａｉｅｌｌｏ、Ｓ．ＬｏｄｈａおよびＲ．Ｏｓｔｒｏｖｓｋｙ。Ｆａｓｔ  ｄｉｇｉｔａｌ  ｉｄｅｎｔｉｔｙ  ｒｅｖｏｃａｔｉｏｎ。Ｉｎ  ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ａｓｉａｃｒｙｐｔ  ’０１、２００１年。
［３］Ｕ．Ｆｅｉｇｅ．Ａ  ｔｈｒｅｓｈｏｌｄ  ｏｆ  Ｉｎｎ  ｆｏｒ  ａｐｐｒｏｘｉｍａｔｉｎｇ  ｓｅｔ  ｃｏｖｅｒ、ＪＡＣＭ、１９９８年、６３４−６５２頁。
［４］Ａ．ＦｉａｔおよびＭ．Ｎａｏｒ。Ｂｒｏａｄｃａｓｔ  ｅｎｃｒｙｐｔｉｏｎ、Ｃｒｙｐｔｏ、１９９３年、４８０−４９１頁。
［５］Ｅ．Ｇａｆｎｉ、Ｊ．ＳｔａｄｄｏｎおよびＹ．Ｌ．Ｙｉｎ。Ｅｆｆｉｃｉｅｎｔ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｉｎｔｅｇｒａｔｉｎｇ  ｔｒａｃｅａｂｉｌｉｔｙ  ａｎｄ  ｂｒｏａｄｃａｓｔ  ｅｎｃｒｙｐｔｉｏｎ、Ｃｒｙｐｔｏ、１９９９年、３７２−３８７頁。
［６］Ｓ．Ｊｕｋｎａ。Ｅｘｔｒｅｍａｌ  Ｃｏｍｂｉｎａｔｏｒｉｃｓ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、２００１年。
［７］Ｒ．Ｋｕｍａｒ、Ｓ．ＲａｊａｇｏｐａｌａｎおよびＡ．Ｓａｈａｉ。Ｃｏｄｉｎｇ  ｃｏｎｓｔｒｕｃｔｉｏｎｓ  ｆｏｒ  ｂｌａｃｋｌｉｓｔｉｎｇ  ｐｒｏｂｌｅｍｓ  ｗｉｔｈｏｕｔ  ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｓｓｕｍｐｔｉｏｎｓ、Ｃｒｙｐｔｏ、１９９９年、６０９−６２３頁。
［８］Ｒ．ＫｕｍａｒおよびＡ．Ｒｕｓｓｅｌｌ。Ａ  ｎｏｔｅ  ｏｎ  ｔｈｅ  ｓｅｔ  ｓｙｓｔｅｍｓ  ｕｓｅｄ  ｆｏｒ  ｂｒｏａｄｃａｓｔ  ｅｎｃｒｙｐｔｉｏｎ、ＳＯＤＡ、２００３年、４７０−４７１頁。
［９］Ｊ．Ｌｏｔｓｐｉｅｃｈ、Ｄ．ＮａｏｒおよびＭ．Ｎａｏｒ。Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  ｔｒａｃｉｎｇ  ｓｃｈｅｍｅｓ  ｆｏｒ  ｓｔａｔｅｌｅｓｓ  ｒｅｃｅｉｖｅｒｓ、Ｃｒｙｐｔｏ、２０００年、４１−６２頁。
［１０］Ｍ．ＬｕｂｙおよびＪ．Ｓｔａｄｄｏｎ。Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｂｏｕｎｄｓ  ｆｏｒ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ、Ｅｕｒｏｃｒｙｐｔ、１９９８年、５１２−５２６頁。
［１１］Ｃ．ＬｕｎｄおよびＭ．Ｙａｎｎａｋａｋｉｓ。Ｏｎ  ｔｈｅ  ｈａｒｄｎｅｓｓ  ｏｆ  ａｐｐｒｏｘｉｍａｔｉｎｇ  ｍｉｎｉｍｉｚａｔｉｏｎ  ｐｒｏｂｌｅｍｓ、  ＪＡＣＭ、１９９４年、９６０−９８１頁。
［１２］Ｓ．Ｍｉｃａｌｉ。Ｅｆｆｉｃｉｅｎｔ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ。ＭＩＴ／ＬＣＳ／ＴＭ  ５４２ｂ、Ｍａｓｓａｃｈｕｓｅｔｔｓ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ、１９９６年。
［１３］Ｓ．Ｍｉｃａｌｉ。Ｅｆｆｉｃｉｅｎｔ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ。Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＲＳＡ  Ｄａｔａ  Ｓｅｃｕｒｉｔｙ  Ｃｏｎｆｅｒｅｎｃｅ、１９９７年。および米国特許第５，６６６，４１６号。
［１４］Ｓ．Ｍｉｃａｌｉ。ＮＯＶＯＭＯＤＯ：ｓｃａｌａｂｌｅ  ｃｅｒｔｉｆｉｃａｔｅ  ｖａｌｉｄａｔｉｏｎ  ａｎｄ  ｓｉｍｐｌｉｆｉｅｄ  ＰＫＩ  ｍａｎａｇｅｍｅｎｔ。Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １ｓｔ  Ａｎｎｕａｌ  ＰＫＩ  Ｒｅｓｅａｒｃｈ  Ｗｏｒｋｓｈｏｐ、２００２年。
［１５］Ｔ．Ｍ．Ｃｈａｎ。Ａｌｌ−ｐａｉｒｓ  ｓｈｏｒｔｅｓｔ  ｐａｔｈｓ  ｗｉｔｈ  ｒｅａｌ  ｗｅｉｇｈｔｓ  ｉｎ  Ｏ（ｎ３／ｌｏｇｎ）ｔｉｍｅ。Ｐｒｏｃ  ９ｔｈ  ＷＡＤＳ，ＬＮＣＳ  ３６０８、３１８−３２４頁、２００５年。
［１６］Ｊ．Ｅｒｉｃｋｓｏｎ。ｈｔｔｐ：／／３ｄｐａｎｃａｋｅｓ．ｔｙｐｅｐａｄ．ｃｏｍ／ｅｒｎｉｅ／２００５／０８／ｃｈａｎｓ−ｔｅｃｈｎｉｑｕｅ．ｈｔｍｌ掲載のブログ
［１７］Ｔ．Ｈ．Ｃｏｒｍｅｎ、Ｃ．Ｅ．ＬｅｉｓｅｒｓｏｎおよびＲ．Ｌ．Ｒｉｖｅｓｔ。Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ａｌｇｏｒｉｔｈｍｓ、１９９０年、Ｔｈｅ  ＭＩＴ  Ｐｒｅｓｓ／ＭｃＧｒａｗ−Ｈｉｌｌ。
［１８］Ｙ．Ｈａｎ。Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ｓｏｒｔｉｎｇ  ｉｎ  Ｏ（ｎｌｏｇｌｏｇｎ）ｔｉｍｅ  ａｎｄ  ｌｉｎｅａｒ  ｓｐａｃｅ。Ｊｏｕｒｎａｌ  ｏｆ  Ａｌｇｏｒｉｔｈｍｓ、２００４年、９６−１０５頁。
［１９］Ｙ．ＨａｎおよびＭ．Ｔｈｏｒｕｐ。Ｓｏｒｔｉｎｇ  ｉｎ  
【０３４７】
【数９３】
2010158054.tif 000095
【０３４８】
ｅｘｐｅｃｔｅｄ  ｔｉｍｅ  ａｎｄ  ｌｉｎｅａｒ  ｓｐａｃｅ。ＦＯＣＳ、２００２年、１３５−１４４頁。
［２０］Ｄ．Ｎａｏｒ、Ｍ．ＮａｏｒおよびＪ．Ｌｏｔｓｐｉｅｃｈ。Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｔｒａｃｉｎｇ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｓｔａｔｅｌｅｓｓ  Ｒｅｃｅｉｖｅｒｓ。Ｐｒｏｃ．  Ｏｆ  Ｃｒｙｐｔｏ  ２００１、ＬＮＣＳ  ２１３９、４１−６２頁。Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、２００１年。
［２１］Ｚ．ＲａｍｚａｎおよびＤ．Ｐ．Ｗｏｏｄｒｕｆｆ。Ｆａｓｔ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔｈｅ  Ｆｒｅｅ  Ｒｉｄｅｒｓ  Ｐｒｏｂｌｅｍ  ｉｎ  Ｂｒｏａｄｃａｓｔ  Ｅｎｃｒｙｐｔｉｏｎ。Ｐｒｏｃ．Ｏｆ  Ｃｒｙｐｔｏ  ２００６。
【０３４９】
付録１１．初期化。２．Ｔ（１，ｆ）←ＯｐｔｉｍａｌＣｏｖｅｒ（１，ｆ）。３．Ｔ（１，ｆ）．ｃｏｖｅｒ内の集合に対してネットワーク送信を適宜実施。付録１終了
付録２ＯｐｔｉｍａｌＣｏｖｅｒ（ｖ，ｆｖ）
入力：ｖは、木のノードである。ｆｖは、許容可能なフリーライダーの最大数である。
【０３５０】
出力：Ｔｏｕｔ＝｛Ｔｏｕｔ．ｃｏｖｅｒ，Ｔｏｕｔ．ｓｉｚｅ｝が最適被覆である。１．ｆｖ＝０またはＰ（ｖ）＝φの場合、
（ａ）Ｔｏｕｔ．ｃｏｖｅｒ←ＢａｓｉｃＣｏｖｅｒ（ｖ）。
【０３５１】
（ｂ）Ｔｏｕｔ．ｓｉｚｅ←｜ＢａｓｉｃＣｏｖｅｒ（ｖ）｜。
【０３５２】
（ｃ）Ｔｏｕｔを出力し終了。２．
【０３５３】
【数９４】
2010158054.tif 000096
【０３５４】
の場合、
（ａ）Ｔｏｕｔ．ｃｏｖｅｒ←｛ｖ｝。
【０３５５】
（ｂ）Ｔｏｕｔ．ｓｉｚｅ←１。
【０３５６】
（ｃ）Ｔｏｕｔを出力し、終了。３．ｆＬをＬＶ（ｖ）に割り当てるフリーライダーの最大数の候補とし、ｆｖ−ｆＬをＲＶ（ｖ）に割り当てるフリーライダーの最大数の候補とし、
（ａ）
【０３５７】
【数９５】
2010158054.tif 000097
【０３５８】
を最小にするｆＬを算出。このｆＬをｆＬｍｉｎとすると、
【０３５９】
【数９６】
2010158054.tif 000098
【０３６０】
が成立。対応する被覆を、ＴＬおよびＴＲで表す。すなわち、
【０３６１】
【数９７】
2010158054.tif 000099
【０３６２】
。
（ｂ）  （１）Ｔｏｕｔ．ｓｉｚｅ←ＴＬ．ｓｉｚｅ＋ＴＲ．ｓｉｚｅ。
【０３６３】
（２）Ｔｏｕｔ．ｃｏｖｅｒ←ＴＬ．ｃｏｖｅｒ∪ＴＲ．ｃｏｖｅｒ。
【０３６４】
（３）Ｔｏｕｔを出力し、終了。付録２終了
付録３ＯｐｔｉｍａｌＣｏｖｅｒＳｉｚｅ（ｖ，ｆｖ）
入力：ｖは、木のノードである。
【０３６５】
ｆｖは、許容可能なフリーライダーの最大数である。１．ＴＢＬ２［ｖ，ｆｖ］．Ｄｅｆｉｎｅ←ＴＲＵＥ。２．ｆｖ＝０またはＰ（ｖ）＝φの場合、
（ａ）ＴＢＬ２［ｖ，ｆｖ］．Ｓｉｚｅ←｜ＢａｓｉｃＣｏｖｅｒ（ｖ）｜。
【０３６６】
（ｂ）終了。３．
【０３６７】
【数９８】
2010158054.tif 000100
【０３６８】
の場合、
（ａ）ＴＢＬ２［ｖ，ｆｖ］．Ｓｉｚｅ←１。
【０３６９】
（ｂ）終了。４．ｆＬをＬＶ（ｖ）に割り当てるフリーライダーの最大数の候補とし、ｆｖ−ｆＬをＲＶ（ｖ）に対するフリーライダーの最大数の候補とし、
（ａ）
【０３７０】
【数９９】
2010158054.tif 000101
【０３７１】
を最小にするｆＬを検出。このｆＬをｆＬｍｉｎとすると、
【０３７２】
【数１００】
2010158054.tif 000102
【０３７３】
が成立。対応する被覆の大きさを、ＴＬＳｉｚｅおよびＴＲＳｉｚｅで表す。すなわち、
【０３７４】
【数１０１】
2010158054.tif 000103
【０３７５】
。
【０３７６】
（ｂ）  （１）ＴＢＬ２［ｖ．ｆｖ］．Ｓｉｚｅ←ＴＬＳｉｚｅ＋ＴＲＳｉｚｅ．
（２）ＴＢＬ２［ｖ．ｆｖ］．ｆＬｍｉｎ←ｆＬｍｉｎ。
【０３７７】
（３）終了。付録３終了
付録４ＦｒｅｅＲｉｄｅｒｓ１．Ｆ←φ。２．ＯｐｔｉｍａｌＣｏｖｅｒＳｉｚｅ（１，ｆ）。３．ｆｆ［１］←ｆ。４．木の内部ノードを、上から順（例えば、幅優先探索順）に走査。各内部ノードｖに対して、その左右の子ＬＶ（ｖ）およびＲＶ（ｖ）のｆｆを算出。
【０３７８】
（ａ）ｆｆ［ｖ］＝０またはＰ（ｖ）＝φの場合、ｖの子の木走査を省略、次のノードの木走査に進む（Ｔ（ｖ）に対するフリーライダーの割当なし）。
【０３７９】
（ｂ）
【０３８０】
【数１０２】
2010158054.tif 000104
【０３８１】
の場合、
（１）Ｔ（ｖ）内の、失効した全てのノードをＦに追加。
【０３８２】
（２）ｖの子の木走査をスキップし、次のノードの木走査に進む。
【０３８３】
（ｃ）  （１）ｆｆ［ＬＶ（ｖ）］←ＴＢＬ２［ｖ，ｆｆ［ｖ］］．ｆＬｍｉｎ。
【０３８４】
（２）ｆｆ［ＲＶ（ｖ）］←ｆｆ［ｖ］−ｆｆ［ＬＶ（ｖ）］。５．Ｔ（１，ｆ）．ｃｏｖｅｒ←ＢａｓｉｃＣｏｖｅｒ（１，Ｐ∪Ｆ，Ｕ）。
【０３８５】
Ｔ（１，ｆ）．ｓｉｚｅ＋←｜ＢａｓｉｃＣｏｖｅｒ（１，Ｐ∪Ｆ，Ｕ）｜。付録４終了
付録５ＯｐｔｉｍａｌＣｏｖｅｒＭ（ｖ，ｆｖ，ε）
．．．３．  （ａ）ｘ←ＭＰｌｅｆｔ（ｖ），ｙ←ＭＰｒｉｇｈｔ（ｖ）。ｆＬをｘに割り当てるフリーライダーの最大数の候補とし、ｆｖ−ｆＬをｙに対するフリーライダーの最大数の候補とし、
（１０）の範囲でＯｐｔｉｍａｌＣｏｖｅｒＭ（ｘ，ｆＬ，ε′）．ｓｉｚｅ＋ＯｐｔｉｍａｌＣｏｖｅｒＭ（ｙ，ｆｖ−ｆＬ，ε′）．ｓｉｚｅを略最適にするｆＬを検出。このｆＬをｆＬｍｉｎとすると、
【０３８６】
【数１０３】
2010158054.tif 000105
【０３８７】
が成立。対応する被覆を、ＴＬおよびＴＲで表す。すなわち、
【０３８８】
【数１０４】
2010158054.tif 000106
【０３８９】
。
（ｂ）  （１）Ｔｏｕｔ．ｓｉｚｅ←ＴＬ．ｓｉｚｅ＋ＴＲ．ｓｉｚｅ＋ｈｅｉｇｈｔ（ｘ）＋ｈｅｉｇｈｔ（ｙ）−２・ｈｅｉｇｈｔ（ｖ）−２。
【０３９０】
（２）Ｔｏｕｔ．ｃｏｖｅｒ←ＴＬ．ｃｏｖｅｒ∪ＴＲ．ｃｏｖｅｒ∪Ｃｏｎｏｄｅｓ（ｘ，ＬＶ（ｖ））∪Ｃｏｎｏｄｅｓ（ｙ，ＲＶ（ｖ））。
【０３９１】
（３）Ｔｏｕｔを出力し、終了。付録５終了
付録６１．初期化。２Ａ．最下層の合流点ｖＭを検出。２Ｂ．ＴｏｐｔＭ←ＯｐｔｉｍａｌＣｏｖｅｒＭ（ｖＭ，ｆ，ε）。２Ｃ．Ｔ（１，ｆ）．ｃｏｖｅｒ←ＴｏｐｔＭ．ｃｏｖｅｒ∪Ｃｏｎｏｄｅｓ（ｖＭ）。２Ｄ．Ｔ（１，ｆ）．ｓｉｚｅ←ＴｏｐｔＭ．ｓｉｚｅ＋ｈｅｉｇｈｔ（ｖＭ）。３．Ｔ（１，ｆ）．ｃｏｖｅｒ内の集合に対してネットワーク送信を適宜実施。付録６終了
付録７ＯｐｔｉｍａｌＣｏｖｅｒＳｉｚｅＭ（ｖ，ｆｖ，ε）
．．．４．  （ａ）ｘ←ＭＰｌｅｆｔ（ｖ）およびｙ←ＭＰｒｉｇｈｔ（ｖ）。ｆＬをｘに割り当てるフリーライダーの最大数の候補とし、ｆｖ−ｆＬをｙに対するフリーライダーの最大数の候補とし、
（１０）の範囲でＯｐｔｉｍａｌＣｏｖｅｒＭ（ｘ，ｆＬ，ε′）．ｓｉｚｅ＋ＯｐｔｉｍａｌＣｏｖｅｒＭ（ｙ，ｆｖ−ｆＬ，ε′）．ｓｉｚｅを略最適にするｆＬを算出。このｆＬをｆＬｍｉｎとすると、
【０３９２】
【数１０５】
2010158054.tif 000107
【０３９３】
が成立。対応する被覆の大きさを、ＴＬＳｉｚｅおよびＴＲＳｉｚｅで表す。すなわち、
【０３９４】
【数１０６】
2010158054.tif 000108
【０３９５】
。
【０３９６】
（ｂ）  （１）ＴＢＬ２［ｖ，ｆｖ］．Ｓｉｚｅ←ＴＬＳｉｚｅ＋ＴＲＳｉｚｅ＋ｈｅｉｇｈｔ（ｘ）＋ｈｅｉｇｈｔ（ｙ）−２・ｈｅｉｇｈｔ（ｖ）。
【０３９７】
（２）ＴＢＬ２［ｖ，ｆｖ］．ｆＬｍｉｎ←ｆＬｍｉｎ。
【０３９８】
（３）終了。付録７終了
付録８ＦｒｅｅＲｉｄｅｒｓＭ１．Ｆ←φ。２Ａ．最下層の合流点ｖＭを検出。２Ｂ．ＯｐｔｉｍａｌＣｏｖｅｒＳｉｚｅＭ（ｖＭ，ｆ，ε）。３．ｆｆ［ｖＭ］←ｆ。４．木Ｔ（ｖｍ）を、上から順（例えば、幅優先探索順）に走査。尚、合流点以外のノードは無視。各合流点ｖに対して、その左右の合流点ｘ＝ＭＰｌｅｆｔ（ｖ）およびｙ＝ＭＰｒｉｇｈｔ（ｖ）のｆｆを算出。
【０３９９】
（ａ）ｆｆ［ｖ］＝０またはＰ（ｖ）＝φの場合、部分木Ｔ（ｖ）の走査を省略、次の合流点の木走査に進む（Ｔ（ｖ）に対するフリーライダーの割当なし）。
【０４００】
（ｂ）
【０４０１】
【数１０７】
2010158054.tif 000109
【０４０２】
の場合、
（１）Ｔ（ｖ）内の、失効した全てのノードをＦに追加。
【０４０３】
（２）Ｔ（ｖ）の走査をスキップし、次の合流点の木走査に進む。
【０４０４】
（ｃ）  （１）ｆｆ［ｘ］←ＴＢＬ２［ｖ，ｆｆ［ｖ］］．ｆＬｍｉｎ。
【０４０５】
（２）ｆｆ［ｙ］←ｆｆ［ｖ］−ｆｆ［ｘ］。５．  （ａ）Ｔ（１，ｆ）．ｃｏｖｅｒ←ＢａｓｉｃＣｏｖｅｒ（ｖＭ，Ｐ（ｖＭ）∪Ｆ，Ｕ（ｖＭ））∪Ｃｏｎｏｄｅｓ（ｖＭ）、
（ｂ）Ｔ（１，ｆ）．ｓｉｚｅ←（５ａ）における被覆の大きさ。付録８終了
付録９ＭｅｅｔｉｎｇＰｏｉｎｔｓ（Ｒ）１．Ｒ←ｓｏｒｔ（Ｒ）、およびＭＰ←Ｒ。２．ｅ＝｛ｕｉ，ｕｉ＋１｝∈Ｒを満たす、隣接する対ｅの各々について、ｅ．ａ＝ａ（ｕｉ，ｕｉ＋１）およびｅ．ｗ＝ｈｅｉｇｈｔ（ｅ．ａ）と設定。３．Ｅを、ｅ．ｗ．に関して非昇順にソートされた、対ｅのリストと設定。４．Ｅ≠φであり、
（ａ）Ｅの要素のうち重みが最大の要素ｅを選択。
【０４０６】
（ｂ）Ｅからｅを削除、ＭＰにｅ．ａを追加。
【０４０７】
（ｃ）ｚ＝ｅ′∩ｅ≠φを満たすｅ′∈Ｅである各ｅ′について、
ｉ．      ｅ′において、ｚをｅ．ａに置換。
【０４０８】
ｉｉ．    ｅ′．ａおよびｅ′．ｗを再計算。
【０４０９】
ｉｉｉ．  ソート順を保持した状態で、ｅ′をＥに再挿入。５．ＭＰを出力付録９終了
付録１０Ｆｒｅｅｒｉｄｅｒ−Ａｐｐｒｏｘ（Ｒ，ｆ，ε）：１．ＭＰ←ＭｅｅｔｉｎｇＰｏｉｎｔｓ（Ｒ）。２．ε′＝ε／（２ｍｉｎ（ｒ，ｌｏｇｎ））。３．権失効した各ユーザｕについて、ｒｕ＝１と設定、Ａｕ←（０，０）。４．ｉ＝ｒ＋１，．．．，２ｒ−１であるｉについて（すなわち、全ての内部合流点について）、
（ａ）ｖ←ＭＰ［ｉ］、ｘ←ＭＰｌｅｆｔ（ｖ）およびｙ←ＭＰｒｉｇｈｔ（ｖ）。
【０４１０】
（ｂ）Ａｘの各エントリにｈｅｉｇｈｔ（ｘ）−ｈｅｉｇｈｔ（ｖ）−１を加算。
【０４１１】
【数１０８】
2010158054.tif 000110
【０４１２】
かつＡｘ［ｒｘ］≠０ならば、Ａｘ［ｒｘ］＝１と設定。
【０４１３】
（ｃ）Ａｙの各エントリにｈｅｉｇｈｔ（ｙ）−ｈｅｉｇｈｔ（ｖ）−１を加算。
【０４１４】
【数１０９】
2010158054.tif 000111
【０４１５】
かつＡｙ［ｒｙ］≠０ならば、Ａｙ［ｒｙ］＝１と設定。
【０４１６】
（ｄ）Ｂｙ←ＭｉｎＳｕｍ（Ａｘ，Ａｙ，ε′）。
【０４１７】
（ｅ）ｒｖ＝ｒｘ＋ｒｙ。
【０４１８】
（ｆ）
【０４１９】
【数１１０】
2010158054.tif 000112
【０４２０】
である各ｊについて、Ａｖ［ｊ］＝Ａｘ［Ｂｖ［ｊ］］＋Ａｙ［ｊ−Ｂｖ［ｊ］］と設定。
【０４２１】
【数１１１】
2010158054.tif 000113
【０４２２】
かつＡｖ［ｒｖ］≠０ならば、Ａｖ［ｒｖ］＝１と設定。５．ＡＭＰ［２ｒ−１］［ｆ］＋ｈｅｉｇｈｔ（ＭＰ［２ｒ−１］）をコストとして出力。６．Ｂｖ’を用いて、ＭＰを深さ優先探索し、割当を算出し、出力。付録１０終了
【図１】
2010158054.tif 000114
【図２Ａ】
2010158054.tif 000115
【図２Ｂ】
2010158054.tif 000116
【図３】
2010158054.tif 000117
【図４Ａ】
2010158054.tif 000118
【図４Ｂ】
2010158054.tif 000119
【図５】
2010158054.tif 000120
【図６Ａ】
2010158054.tif 000121
【図６Ｂ】
2010158054.tif 000122
【図７】
2010158054.tif 000123
【図８】
2010158054.tif 000124
【図９】
2010158054.tif 000125
【図１０】
2010158054.tif 000126
【図１１】
2010158054.tif 000127
【図１２】
2010158054.tif 000128
【図１３】
2010158054.tif 000129
【図１４】
2010158054.tif 000130
【図１５】
2010158054.tif 000131
【図１６】
2010158054.tif 000132
【図１７】
2010158054.tif 000133
【図１８】
2010158054.tif 000134