【手続補正書】
【提出日】平成21年11月18日(2009.11.18)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
実体の集合と関連付けられた送信用のメッセージを形成するデータを選択するコンピュータに実装される方法であって、
（１）第１のコンピュータ・データを取得する工程と
（２）Ｒの内、少なくとも０かつ多くともｆ個の実体をフリーライダーと指定することにより、フリーライダー割当を行う工程とを含み、
（１）前記第１のコンピュータ・データは、
（１Ａ）前記実体の集合Ｕと
（１Ｂ）Ｕの部分集合である対象集合Ｐと、
（１Ｃ）Ｕの部分集合の集合である集合体ＣＳ（Ｕ）と、
（１Ｄ）前記対象集合Ｐに対するｆ＋冗長の被覆ＣＶ＝ＣＶ（ｆ，Ｐ）を構築する際に許容されるフリーライダーの正の最大数ｆとを表し、
（２）前記被覆ＣＶ（ｆ，Ｐ）は、前記集合体ＣＳ（Ｕ）の要素である０以上の集合Ｓにより、前記集合Ｓの和が、対象集合Ｐ、および集合Ｒ＝Ｕ＼Ｐのうち多くともｆ個の実体を含むように、構成されるものであり、
前記選択されるデータは、前記被覆ＣＶの前記要素に関連付けられたデータ片であり、
フリーライダー割当を行う工程は、前記集合体ＣＳ（Ｕ）の要素である少なくとも１つの部分集合ｖ及びｆｖ＜ｆである少なくとも１つの正数ｆｖについて、ｖに対するｆｖ＋冗長の被覆のコストを求める工程を含み、
任意の被覆に対するコストは、定数ではない前記被覆内の要素数に関する非減少関数であり、
ｖに対する前記ｆｖ＋冗長の被覆のコストを求める工程は、
（２Ａ）ｖの部分集合であり、かつ前記集合体ＣＳ（Ｕ）の要素である、互いに素である空集合ではない部分集合ｘ１，ｘ２，．．．を特定する工程と、
（２Ｂ）０以上の整数ｆ１，ｆ２，．．．の２つ以上の数（ｆ１，ｆ２，．．．）の組を選択する工程と、
（２Ｃ）前記組から、対応する割当候補が、ｖに対するｆｖ＋冗長の被覆の最適性コストとなる組を選択する工程とを含み、
（２Ｂ）各組に含まれる前記数の和はｆｖ以下であり、
各組は、ｉ＝１，２，．．．である各ｉについて、ｖに対するｆｖ＋冗長の被覆を取得するための多くともｆｉ人のフリーライダーのｘｉへの割当候補を示し、
（２Ｃ）最適性コストとは、最小コストに対して、所定の最適性関係を有するコストであり、
さらに、ｆ＋冗長の被覆の各集合のそれぞれについて、対応するデータ片を用いてメッセージを生成し、前記メッセージを送信する工程を更に含むことを特徴とする方法。
【請求項２】
最適コストは、前記最小コストに等しいコストであることを特徴とする請求項１に記載の方法。
【請求項３】
最適コストは、εが所定の正の定数である場合、前記最小コストの多くとも（１＋ε）倍のコストであることを特徴とする請求項１に記載の方法。
【請求項４】
要素ｖ、ｘ１およびｘ２は、それぞれ合流点であり、前記合流点は、
（ａ）ＣＳ（Ｕ）において、各々がＲの要素を備える少なくとも２つの直下の子を有するか、または
（ｂ）Ｒの要素である単一の実体から構成されるか、
のいずれかを満たすような体系ＣＳ（Ｕ）の要素であり、
ＣＳ（Ｕ）の任意の要素ｅ１がＣＳ（Ｕ）の他の要素ｅ２の真部分集合であり、かつ、真部分集合としてｅ１を含みかつｅ２の真部分集合であるような要素ｅ３がＣＳ（Ｕ）に存在しないならば、ｅ１は、ｅ２の直下の子と呼ばれ、
工程（２Ａ）は、ｖの真部分集合である少なくとも２つの合流点を探索し、前記探索の結果、ｘ１およびｘ２を検出する工程を含むことを特徴とする請求項１に記載の方法。
【請求項５】
ｘ１およびｘ２の少なくとも一方が、ｖの直下の子ではないことを特徴とする請求項４に記載の方法。
【請求項６】
ＣＳ（Ｕ）は、ｘ１およびｖ間にいずれの合流点を含まず、ｘ２およびｖ間にもいずれの合流点も含まず、
ＣＳ（Ｕ）の要素ｅ１が、ＣＳ（Ｕ）の要素ｅ２またはｅ３のいずれか一方の真部分集合であり、かつ、ｅ２またはｅ３の他方がｅ１の真部分集合であるならば、ｅ１は、ｅ２およびｅ３の間にあることを特徴とする請求項４に記載の方法。
【請求項７】
ＣＳ（Ｕ）内のすべての合流点の集合を、高さ順に並べた状態で算出する工程と、
すべての合流点の集合から、高さの非減少順に合流点を選択し、前記選択された合流点に対して工程（２Ａ）〜（２Ｃ）を行う工程を更に含み、
合流点の高さは、前記合流点を始点とし、ＣＳ（Ｕ）のいずれの要素の部分集合でもない要素を終点とする連鎖において、ＣＳ（Ｕ）の要素の数を表し、前記連鎖における最後の要素を除く各要素は、前記連鎖における次の要素の直下の子であることを特徴とする請求項４に記載の方法。
【請求項８】
工程（２Ａ）〜（２Ｃ）は、複数の正数ｆｖに対して行われ、
前記被覆ＣＶ（ｆ，Ｐ）の最適性コストを与える数ｆｖを選択する工程を
を更に含むことを特徴とする請求項１に記載の方法。
【請求項９】
各データ片は、デジタルデータの有効性または無効性の証明を生成するための暗号鍵又は値を構成し、
各メッセージは、前記暗号鍵、又は、有効性又は無効性の前記証明を用いた、暗号を備えることを特徴とする請求項１に記載の方法。
【請求項１０】
実体の集合と関連付けられた送信用メッセージを形成するデータを、コンピュータによって選択する方法であって、
（１）コンピュータ・データを取得する工程と、
（２）少なくとも対象集合Ｐを被覆する被覆ＣＶを特定する工程と、
（３）被覆ＣＶの集合のそれぞれについて、対応するデータ片を用いてメッセージを生成し、前記メッセージを送信する工程とを含み、
（１）前記コンピュータ・データは、
（１Ａ）前記実体の集合Ｕと
（１Ｂ）Ｕの部分集合である前記対象集合Ｐと、
（１Ｃ）Ｕの部分集合の集合である集合体ＣＳ（Ｕ）とを表し、
（２）前記被覆ＣＶは、前記集合体ＣＳ（Ｕ）の要素である０以上の集合Ｓにより、前記集合Ｓの和が前記対象集合Ｐを構成するように構成されるものであり、
前記選択されるデータは、前記被覆ＣＶの前記要素に関連付けられたデータ片であり、
前記被覆ＣＶを特定する工程は、
（２ａ）ＣＳ（Ｕ）における全ての合流点の順序集合ＭＰを算出する工程と、
（２ｂ）前記合流点から、前記被覆ＣＶを決定する工程とを含み、
（２ａ）前記合流点は、前記合流点の高さに応じて順序付けられており、（ａ）ＣＳ（Ｕ）において、各々がＲ＝Ｕ＼Ｐの要素を備える少なくとも２つの直下の子を有する要素であるか、または（ｂ）Ｒの要素である単一の実体から成る要素であるかのいずれかであるような、集合体ＣＳ（Ｕ）の要素であり、
ＣＳ（Ｕ）の任意の要素ｅ１がＣＳ（Ｕ）の他の要素ｅ２の真部分集合であり、かつ部分集合としてｅ１を含みかつｅ２の真部分集合であるような要素ｅ３がＣＳ（Ｕ）に存在しないならば、ｅ１は、ｅ２の直下の子と呼ばれ、
合流点の高さは、前記合流点を始点とし、ＣＳ（Ｕ）のいずれの要素の部分集合でもない要素を終点とする連鎖の要素における、ＣＳ（Ｕ）の要素の数を表し、前記連鎖の最後の要素を除く各要素は、前記連鎖における次の要素の直下の子であることを特徴とする方法。
【請求項１１】
前記全ての合流点の前記集合ＭＰを算出する工程は、
（２ａ−１）ｒ＞１である場合、ＣＳ（Ｕ）の各要素ｕｉ（ｉ＝１，２，…ｒ）がＲの１つの要素を構成するように、前記集合ＭＰを列ｕ１，ｕ２，…ｕｒに初期化する工程と、
（２ａ−２）ＣＳ（Ｕ）の要素のついの集合Ｅを定義し、前記集合Ｅを、ｉ＝１，…，ｒ−１である隣接する要素の全対｛ｕｉ，ｕｉ＋１｝の集合に初期化する工程と、
（２ａ−３）前記集合Ｅから、要素ａ（ｕｉ，ｕｉ＋１）がＥにおける全対の最大の高さを有する対｛ｕｉ，ｕｉ＋１｝を取り除く工程と、
（２ａ−４）前記取り除かれた対について、前記要素ａ（ｕｉ，ｕｉ＋１）を前記集合ＭＰに付加する工程と、
（２ａ−５）前記集合Ｅが前記工程（２ａ−３）における要素ｕ又はｕｉ＋１を構成する少なくとも１つの対を含む場合、少なくとも１つの対の各要素ｕｉ又はｕｉ＋１を、工程（２ａ−４）の前記要素ａ（ｕｉ，ｕｉ＋１）に置き換える工程とを含み、
前記工程（２ａ−１）の前記列ｕ１，ｕ２，…ｕｒにおける各要素ｕｉについて、ｖ∈ＣＳ（Ｕ）が、ｕｉとは異なり、Ｒの１つの要素を構成するように、要素ａ（ｕｉ，ｕｉ＋１）又は要素ａ（ｕｉ−１，ｕｉ）のいずれかが、全ての要素ａ（ｕｉ，ｖ）の最大の高さを有し、ＣＳ（Ｕ）の２つの要素ｕ，ｖについて、ａ（ｕ，ｖ）が、ｕとｖとの両方を含む全要素の最大の高さを有するＣＳ（Ｕ）の要素を示すことを特徴とする請求項１０に記載の方法。
【請求項１２】
工程（２ａ−１）から（２ａ−５）は、前記集合Ｅが空となるまで行われることを特徴とする請求項１１に記載の方法。
【請求項１３】
請求項１に記載の方法を実行するように構成された装置であって、
前記（２）の動作を実行するように構成された１つ又は複数の演算装置を有するコンピュータ・システムを備えることを特徴とする装置。
【請求項１４】
コンピュータ・システムが請求項１に記載の方法を実行するための１つ以上のコンピュータ命令を備えることを特徴とするコンピュータ可読記憶媒体。
【請求項１５】
コンピュータ・システムが請求項１に記載の方法を実行するためのコンピュータ・プログラムを、通信網を介して送信する工程を含むことを特徴とするデータ送信方法。
【請求項１６】
請求項４に記載の方法を実行するように構成された装置であって、
前記（２）の動作を実行するように構成された１つ又は複数の演算装置を有するコンピュータ・システムを備えることを特徴とする装置。
【請求項１７】
コンピュータ・システムが請求項４に記載の方法を実行するための１つ以上のコンピュータ命令を備えることを特徴とするコンピュータ可読記憶媒体。
【請求項１８】
コンピュータ・システムが請求項４に記載の方法を実行するためのコンピュータ・プログラムを、通信網を介して送信する工程を含むことを特徴とするデータ送信方法。
【請求項１９】
請求項１０に記載の方法を実行するように構成された装置であって、
前記（２）の動作を実行するように構成された１つ又は複数の演算装置を有するコンピュータ・システムを備えることを特徴とする装置。
【請求項２０】
コンピュータ・システムが請求項１０に記載の方法を実行するための１つ以上のコンピュータ命令を備えることを特徴とするコンピュータ可読記憶媒体。
【請求項２１】
コンピュータ・システムが請求項１０に記載の方法を実行するためのコンピュータ・プログラムを、通信網を介して送信する工程を含むことを特徴とするデータ送信方法。