(57)【要約】ネットワーク符号化に対するデジタル署名を説明する。一態様では、ネットワーク符号化に対するデジタル署名を説明する。一態様では、分配されるセグメント化コンテンツブロックを、楕円曲線から生成した準同型デジタル署名を使用して、デジタル署名する。デジタル署名済みコンテンツを備えるパケットの線形結合を、実装した分散方式に従って目的の装置に分配する。パケットの線形結合は、セグメント化ブロックをデジタル署名するときの公開情報を含む。準同型デジタル署名および公開情報により、パケットの線形結合の１つまたは複数のパケットを受信する装置は、その１つまたは複数のパケットをデジタル署名するために使用する秘密鍵およびハッシュダイジェストの安全な送信と独立して、我々のパケットの１つに関連付けたコンテンツを検証および認証することができる。
2009515480.tif 000002
【特許請求の範囲】
【請求項１】
それぞれの準同型のデジタル署名を使用して、一連のセグメント化コンテンツブロックの各々をデジタル署名し、デジタル署名済みコンテンツブロックを生成するステップと、
分配方式を使用してパケットの線形結合を目的の装置に分配するステップであって、前記のパケットの線形結合は前記のデジタル署名済みコンテンツブロックと、前記のセグメント化ブロックの各々をデジタル署名するために使用する公開情報とを含むステップと、
を含み、
前記の準同型のデジタル署名と前記の公開情報とにより、１つまたは複数の前記のパケットの線形結合を受信する装置は、前記の１つまたは複数のパケットをデジタル署名するために使用する秘密鍵とハッシュダイジェストとの安全な送信と独立して、我々のパケットの１つと関連付けたコンテンツを検証および認証できること
を特徴とするコンピュータ実行型の方法。
【請求項２】
前記の分配方式はネットワーク符号化コンテンツ分配方式であることを特徴とする請求項１に記載の方法。
【請求項３】
前記の公開情報は、前記のそれぞれのパケットに署名するために使用する、ある特定の相異なる素数と楕円曲線上の点とを含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記の準同型のデジタル署名と前記の公開情報とにより、１つまたは複数の前記のパケットの線形結合を受信する装置は、前記の１つまたは複数のパケットの情報源に接触することと独立して、前記のパケットの線形結合の任意の部分集合に関連付けたコンテンツを再署名でき、前記の再署名したコンテンツを前記の目的の装置に対して新規の線形結合で引き続き分配し、前記の目的の装置ではない任意の中間のクライアント装置により引き続き検証および認証ならびに分配できることを特徴とする請求項１に記載の方法。
【請求項５】
デジタル署名するステップは、前記それぞれのパケットのベクトルを、ベクトル空間から楕円曲線上の素数個の捩れ点の群への準同型である衝突回避ハッシュ関数を使用して、前記の楕円曲線上の点集合に変換するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項６】
デジタル署名するステップは、
大きな素数を取るステップと、
適切な素数ｌと、ｐの倍数個の多点を有するＦl上の楕円曲線Ｅとを選択するステップと、
【数１】
2009515480.tif 000108
となるように体Ｆlの拡張Ｆqを配置するステップであって、Ｅ［ｐ］は全てのｐ捩れ点からなる集合に関連するステップと、
【数２】
2009515480.tif 000109
であり、体Ｆlの拡張Ｆqがｐ捩れ点を有し、Ｏ≠Ｐ∈Ｅ（Ｆl）が前記の楕円曲線上のｐ捩れ点であるように
【数３】
2009515480.tif 000110
に対して
【数４】
2009515480.tif 000111
および
【数５】
2009515480.tif 000112
に対して
【数６】
2009515480.tif 000113
と決定するステップであって、
【数７】
2009515480.tif 000114
および
【数８】
2009515480.tif 000115
は集合１，・・・，ｐ−１からランダムに選択されるステップと、
秘密鍵ｓ1，・・・，ｓkおよびｒ1，・・・，ｒdを
【数９】
2009515480.tif 000116
からランダムに選択するステップと、および
前記のそれぞれのパケットのベクトルを前記の楕円曲線上の点集合にハッシュするステップと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項７】
それぞれの準同型のデジタル署名を使用して、一連のセグメント化コンテンツブロックの各々をデジタル署名し、デジタル署名済みコンテンツブロックを生成するステップと、
分配方式を使用してパケットの線形結合を目的の装置に分配するステップであって、前記のパケットの線形結合は前記のデジタル署名済みコンテンツブロックと、前記のセグメント化ブロックの各々をデジタル署名するために使用する公開情報とを備えるステップ
に対するプロセッサが実行可能なコンピュータプログラム命令を備え、
前記の準同型のデジタル署名と前記の公開情報とにより、１つまたは複数の前記のパケットの線形結合を受信する装置は、前記の１つまたは複数のパケットをデジタル署名するために使用する秘密鍵とハッシュダイジェストとの安全な送信とは独立して、我々のパケットの１つと関連付けたコンテンツを検証および認証すること
を特徴とするコンピュータ可読媒体。
【請求項８】
前記の分配方式はネットワーク符号化コンテンツ分配方式であることを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項９】
前記の公開情報は、前記のそれぞれのパケットに署名するために使用する、ある特定の相異なる素数と楕円曲線上の点とを備えることを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１０】
前記の準同型のデジタル署名と前記の公開情報とにより、１つまたは複数の前記のパケットの線形結合を受信する装置は、前記の１つまたは複数のパケットの情報源に接触することと独立して、前記のパケットの線形結合の任意の部分集合に関連付けたコンテンツを再署名でき、前記の再署名したコンテンツを前記の目的の装置に対して新規の線形結合で引き続き分配し、前記の目的の装置ではない任意の中間のクライアント装置により引き続き検証および認証および分配できることを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１１】
デジタル署名する前記のコンピュータプログラム命令は、前記それぞれのパケットのベクトルを、ベクトル空間から楕円曲線上の素数個の捩れ点の群への準同型である衝突回避ハッシュ関数を使用して、前記の楕円曲線上の点集合に変換する命令をさらに備えることを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１２】
前記のデジタル署名するコンピュータプログラム命令は、
大きな素数を取るステップと、
適切な素数ｌと、ｐの倍数個の多点を有するＦl上の楕円曲線Ｅとを選択するステップと、
【数１０】
2009515480.tif 000117
となるように体Ｆlの拡張Ｆqを配置するステップであって、Ｅ［ｐ］は全てのｐ捩れ点からなる集合に関連するステップと、
【数１１】
2009515480.tif 000118
であり、体Ｆlの拡張Ｆqがｐ捩れ点を有し、Ｏ≠Ｐ∈Ｅ（Ｆl）が前記の楕円曲線上のｐ捩れ点であるように
【数１２】
2009515480.tif 000119
に対して
【数１３】
2009515480.tif 000120
および
【数１４】
2009515480.tif 000121
に対して
【数１５】
2009515480.tif 000122
と決定するステップであって、
【数１６】
2009515480.tif 000123
および
【数１７】
2009515480.tif 000124
は集合１，・・・，ｐ−１からランダムに選択されるステップと、
秘密鍵ｓ1，・・・，ｓkおよびｒ1，・・・，ｒdを
【数１８】
2009515480.tif 000125
からランダムに選択するステップと、および
前記のそれぞれのパケットのベクトルを前記の楕円曲線上の点集合にハッシュするステップ
に対する命令をさらに備えることを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１３】
プロセッサと、および
前記のプロセッサに接続したメモリであって、
それぞれの準同型のデジタル署名を使用して、一連のセグメント化コンテンツブロックの各々をデジタル署名し、デジタル署名済みコンテンツブロックを生成するステップと、
分配方式を使用してパケットの線形結合を目的の装置に分配するステップであって、前記のパケットの線形結合は前記のデジタル署名済みコンテンツブロックと、前記のセグメント化ブロックの各々をデジタル署名するために使用する公開情報とを備えるステップ
に対するプロセッサが実行可能なコンピュータプログラム命令を備え、
前記の準同型のデジタル署名と前記の公開情報とにより、１つまたは複数の前記のパケットの線形結合を受信する装置は、前記の１つまたは複数のパケットをデジタル署名するために使用する秘密鍵とハッシュダイジェストとの安全な送信とは独立して、我々のパケットの１つと関連付けたコンテンツを検証および認証でき、前記プロセッサが実行可能なコンピュータプログラム命令を備えるメモリ
を備えることを特徴とするコンピューティング装置。
【請求項１４】
前記の分配方式はネットワーク符号化コンテンツ分配方式であることを特徴とする請求項１３に記載のコンピューティング装置。
【請求項１５】
前記の公開情報は、前記のそれぞれのパケットを署名するために使用する、ある特定の相異なる素数と楕円曲線上の点とを備えることを特徴とする請求項１３に記載のコンピューティング装置。
【請求項１６】
前記の準同型のデジタル署名と前記の公開情報とにより、１つまたは複数の前記のパケットの線形結合を受信する装置は、前記の１つまたは複数のパケットの情報源に接触することと独立して、前記のパケットの線形結合の任意の部分集合に関連付けたコンテンツを再署名でき、前記の再署名したコンテンツを前記の目的の装置に対して新規の線形結合で引き続き分配し、前記の目的の装置ではない任意の中間のクライアント装置により引き続き検証および認証ならびに分配できることを特徴とする請求項１３に記載のコンピューティング装置。
【請求項１７】
デジタル署名する前記のコンピュータプログラム命令は、前記それぞれのパケットのベクトルを、ベクトル空間から楕円曲線上の素数個の捩れ点の群への準同型である衝突回避ハッシュ関数を使用して、前記の楕円曲線上の点集合に変換する命令をさらに備えることを特徴とする請求項１３に記載のコンピューティング装置。
【請求項１８】
前記のデジタル署名するコンピュータプログラム命令は、
大きな素数を取るステップと、
適切な素数ｌと、ｐの倍数個の多点を有するＦl上の楕円曲線Ｅとを選択するステップと、
【数１９】
2009515480.tif 000126
となるように体Ｆlの拡張Ｆqを配置するステップであって、Ｅ［ｐ］は全てのｐ捩れ点からなる集合に関連するステップと、
【数２０】
2009515480.tif 000127
であり、体Ｆlの拡張Ｆqがｐ捩れ点を有し、Ｏ≠Ｐ∈Ｅ（Ｆl）が前記の楕円曲線上のｐ捩れ点であるように
【数２１】
2009515480.tif 000128
に対して
【数２２】
2009515480.tif 000129
に対して
【数２３】
2009515480.tif 000130
と決定するステップであって、
【数２４】
2009515480.tif 000131
および
【数２５】
2009515480.tif 000132
は集合１，・・・，ｐ−１からランダムに選択されるステップと、
秘密鍵ｓ1，・・・，ｓkおよびｒ1，・・・，ｒdを
【数２６】
2009515480.tif 000133
からランダムに選択するステップと、および
前記のそれぞれのパケットのベクトルを前記の楕円曲線上の点集合にハッシュするステップ
に対する命令をさらに備えることを特徴とする請求項１３に記載のコンピューティング装置。
【発明の詳細な説明】
【背景技術】
【０００１】
増大したネットワーク帯域幅により、大量および多種のメディアコンテンツをインターネット上で分配できるようになった。中間ノードによるデータ送信も可能とすることで、ピアツーピアネットワークは、単一の情報源から複数の受信者へネットワーク上でデータをブロードキャストする問題に対処する。大きなファイルを送信するため、従来の分配システムは一般にファイルを小部分にセグメント化して送信する。上記の方式の問題は、上流にボトルネックが存在する恐れがあるので帯域幅の利用が必ずしも最適化されないことである。ネットワーク符号化を大規模なコンテンツ分配メカニズムとともに使用してこの間題を取り扱っている。ネットワーク符号化により、ネットワーク内の全ノードは到着データを局所的に符号化することができる。これは理論的にも実用的にも最適にネットワーク能力を利用することが示されてきた。しかしながら現時点まで、セキュリティ問題のため、ネットワーク符号化でコンテンツを分配させるという考えは現実的には適用されてこなかった。例えば、従来のネットワーク符号化システムおよび技術では、送信データを認証および検証することができない。
【発明の開示】
【０００２】
本要約は、選択した概念を簡潔な形で導入するために与える。これらの概念は以下の「発明を実施するための最良の形態」でさらに説明する。本要約は請求項主題の主要な特徴または本質的な特徴を特定するようには意図しておらず、請求項主題の範囲を決定するための支援として使用するようにも意図していない。
【０００３】
上述のことを考慮して、ネットワーク符号化に対するデジタル署名を説明する。一態様では、分配用のセグメント化コンテンツブロックを、楕円曲線から生成した準同型のデジタル署名を使用してデジタル署名する。デジタル署名済みコンテンツを備えるパケットの線形結合を、実装した分配方式に従って目的の装置に分配する。パケットの線形結合は、セグメント化ブロックをデジタル署名するときの公開情報を含む。準同型のデジタル署名および公開情報により、パケットの線形結合からなる１つまたは複数のパケットを受信する装置は、その１つまたは複数のパケットをデジタル署名するために用いる秘密鍵およびハッシュダイジェストの安全な送信とは独立して、我々のパケットの１つに関連付けたコンテンツを検証および認証することができる。
【０００４】
図面では、構成要素の参照番号の左端の数字は、その構成要素が最初に出現した図面を示す。
【発明を実施するための最良の形態】
【０００５】
概要
ネットワーク符号化に対するデジタル署名のシステム（例えば、システム、装置、コンピュータ可読媒体、等）および方法を、図１−図３を参照して以下で説明する。これらのシステムおよび方法は、分配ネットワークにコンテンツを分配するためのネットワーク符号化使用について、上述のセキュリティ問題と他の既存のセキュリティ制限とを取り扱う。これらの目的のため、システムおよび方法はネットワーク符号化操作において準同型ハッシングを利用する。衝突の発見が計算上実現不可能かつ線形であるハッシュ関数が与えられると、そのシステムおよび方法は入力のハッシュ値を考慮して入力メッセージの線形結合のハッシュを計算する。計算したハッシュを楕円曲線理論に基づく署名方式で利用して、メッセージが変更されたかどうか、または不要データがメッセージに書き込まれたかどうかを決定する。幾つかのメッセージの署名を知ると、このシステムおよび方法はメッセージの線形結合に署名する。署名方式は準同型であり、これは署名の線形結合が線形結合の署名と同じであることを意味する。これにより、システムおよび方法は、ネットワークに不要データを書き込む（すなわち、汚染攻撃（ｐｏｌｕｔｉｏｎ  ａｔｔａｃｋｓ））悪質なノードを即座に検出し、ネットワーク符号化方式に認証情報を加えることができる。
【０００６】
楕円曲線上の離散対数問題が困難であると仮定する（暗号化における一般的な仮定）と、ネットワーク符号化におけるデジタル署名のシステムおよび方法は安全である。システムおよび方法は、小さな体の上で動作することで、準同型のハッシングと同じレベルのセキュリティを実現し、同じレベルのセキュリティに関する他の方式に対して性能的な優位性を与える。このセキュリティは、局所的な計算を利用して効率的に実装する。
【０００７】
上述のことを考慮して、ネットワーク符号化におけるデジタル署名のシステムおよび方法は、分配される幾つかのファイル（複数）の署名を知りえて、そのファイル（複数）の任意の線形結合の署名（複数）を生成する。これにより、データの受信者はネットワーク内の様々なノードで結合したパケットを、そのパケットに署名するためのデータ源に接触することなしに署名することができる。これは、システムおよび方法が、分散ベクトルに対するハッシュダイジェストを安全に送信する必要がないことを意味する。この署名によりデータを認証することができる。さらに、セキュリティを保証するには短いビット長で十分である。その本質的な理由は、有限体上の楕円曲線の点群に関する離散対数に対して既知の（一般的な）準指数関数アルゴリズムが存在しないためである。
【０００８】
ネットワーク符号化におけるデジタル署名のシステムおよび方法のこれらおよび他の態様をさらに詳細に説明する。
【０００９】
例示的なシステム
必ずしも必要ではないが、ネットワーク符号化に対するデジタル署名のシステムおよび方法を、パーソナルコンピュータのようなコンピューティング装置により実行されているコンピュータ実行可能命令（プログラムモジュール）の汎用的なコンテキストで説明する。プログラムモジュールは、一般に特定のタスクを実施するか、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造、等を含む。システムおよび方法を前述のコンテキストで説明するが、以降説明する働きおよび操作をハードウェアに実装してもよい。
【００１０】
図１は、一実施形態に従って、ネットワーク符号化におけるデジタル署名の例示的なシステム１００を示す。本実装では、システム１００はコンテンツ分配システムを表す。システム１００は、ネットワーク１０４に渡って任意数のクライアントコンピューティング装置１０６に接続した１つまたは複数のサーバコンピューティング装置１０２を含む。サーバ１０２は、コンテンツをデジタル署名し、ネットワーク符号化操作を使用して、その署名したコンテンツをパケットの線形結合として、クライアント装置１０６に分配する操作を実装する。パケットの線形結合を受信すると、クライアント装置１０６は受信パケットに埋め込んだデジタル署名済みのコンテンツを検証および認証する。クライアント１０６が受信コンテンツを検証する場合、およびクライアント１０６が受信コンテンツに対してシステム１０４内の最終目的地でない場合、受信コンテンツをデジタル署名し、検証および新規に署名したコンテンツをネットワーク符号化操作を使用して、パケットの新規な線形結合として別のクライアント１０６に分配する操作をクライアント１０６は実装する。上述のことを考慮して、任意の受信したデジタル署名済みコンテンツに対してそれぞれのコンピューティング装置１０２および１０６が、システム１００内で最終目的地であるかどうかに依存して、各コンピューティング装置１０２および１０６は、ネットワーク符号化を使用してコンテンツをデジタル署名および分配して受信コンテンツを検証および認証する１つまたは複数の操作を実施することができる。
【００１１】
図１を参照する。各サーバ１０２およびクライアントコンピューティング装置１０６は、それぞれのシステムメモリ１１０（例えば、１１０−１および１１０−２）に接続した１つまたは複数のそれぞれのプロセッサ１０８（例えば、１０８−１および１０８−２）を含む。システムメモリ１１０はコンピュータプログラムモジュール１１２（例えば、１１２−１および１１２−２）およびプログラムデータ１１４（例えば、１１４−１および１１４−２）を含む。プロセッサ１０８はコンピュータプログラム命令をプログラムモジュール１１２の各々から抽出および実行する。プログラムモジュール１１２は、ネットワーク符号化モジュール１１６（例えば、１１６−１および１１６−２）および、オペレーティングシステム、コンテンツ分配モデル、等のような他のプログラムモジュール１１８（例えば、１１８−１および１１８−２）に対するデジタル署名を含んでいる。ネットワーク符号化モジュール（「符号化モジュール」）１１６に対するデジタル署名は、ネットワーク１０４に渡るそれぞれのサーバ（複数）１０２とクライアント（複数）１０６との間で安全で信頼性のあるコンテンツ分配に対するプログラムロジックを含む。例示の目的で、分配されるコンテンツを「他のプログラムデータ」１２０（例えば、１２０−１および１２０−２）のそれぞれの部分として示してある。すなわち、符号化モジュール１１６は、ネットワーク符号化におけるデジタル署名を使用してコンテンツをクライアント装置１０６に分配し、受信したデジタル署名済みコンテンツを検証および認証する１つまたは複数の操作を実施する。
【００１２】
本例では、サーバ１０２の符号化モジュール１１６−１は、最初に、分配されるコンテンツを小さなデータブロックにセグメント化する。これらのブロックセグメントを、「他のデータ」１２０−１のセグメント化コンテンツのそれぞれの部分として示してある。サーバ１０２は、デジタル署名方式を使用してブロックセグメントの各々に対するそれぞれの準同型デジタル署名１２２−１を計算し、ブロックセグメントをそれぞれの署名１２２−１で署名してそれぞれの署名済みブロック１２４−１を生成する。システム１００では、ベクトル空間の２つのベクトルとハッシングとを楕円曲線に加えたことで得た結果が、その楕円曲線上の２つのベクトルのそれぞれのハッシュ値の和と同じであるとき準同型性が示される。ブロックセグメントを署名するための例示的な上記の方式を、「例示的な準同型署名方式」というタイトルの節で詳細に後述する。サーバ１０２は、署名済みブロック１２４−１がパケット（またはベクトル）の線形結合であることをネットワーク１０４に渡って１つまたは複数のクライアント装置１０６に伝える。上記のパケットの線形結合を生成する例示的なネットワーク符号化操作を、「ネットワーク符号化モデル」というタイトルの節でさらに詳細に後述する。
【００１３】
署名済みブロック１２４−１を備えるパケットのランダムな線形結合の受信に応じて、クライアント装置１０６は各署名済みブロック１１８に対するサーバ１０２の署名を検証する。Ｗｅｉｌペアリングの双線形性に基づく例示的な上記の検証プロセスを、「例示的な準同型署名方式」というタイトルの節で後述する。これらの検証操作により、クライアント装置１０６はコンテンツ分配システム１００内の不正なサーバ１０２を識別することができる。各署名済みブロック１２４−１の検証および認証に応じて、受信したパケットのランダムな線形結合に対してクライアント装置１０６が最終目的地でない場合、クライアント装置１０６は上述（および後述）の操作をサーバ１０２に関して実装し、準同型ハッシュ関数を使用してデータを楕円曲線上の点にデジタル的に再署名し、ネットワーク符号化操作を使用してその署名したデータを目的の装置に再分配する。
【００１４】
すなわち、受信コンテンツに対する最終的な受信者であるとクライアント装置１０６がパケットの線形結合により指定されない場合、および受信コンテンツを無事に検証および認証した場合、符号化モジュール１１６−２は、一部の受信コンテンツのデジタル署名が既知であり、（ａ）受信コンテンツを再署名し、（ｂ）その新規に再署名したコンテンツをパケットの新規の線形結合（「他のデータ」１１６−２のそれぞれの部分）として別のクライアント装置１０６に再分配する。サーバ１０２および／またはクライアント装置１０６の何れかから受信したパケットの線形結合のコンテンツに対して、それぞれのクライアント装置１０６が最終目的地であるまで、本プロセスを繰り返す。これらの後者の操作により、データ受信クライアント装置１０６は、新規パケットの線形結合のパケットを署名するための情報源（例えば、サーバ１０２および／または別のクライアント装置１０６）に接触なしで、ネットワーク１０４の様々なノードで結合したパケットを署名することができる。
【００１５】
楕円曲線の背景
本節は、有限体上の楕円曲線の態様を提示する。有限体Ｆq上の楕円曲線Ｅ（これをＥ／Ｆqと省略する場合もある）を考える。有限体に関して、ｑ＞３は素数の累乗であり、射影曲線Ｐ2（Ｆq）は次の形の方程式で与えられる。
【００１６】
【数１】
2009515480.tif 000003
【００１７】
ここで、Ａ，Ｂ∈Ｆqであり、４Ａ3＋２７Ｂ2≠０である。本曲線は２つのアフィン部分を有する。すなわち、Ｚ≠０である部分はアフィン形ｙ2＝ｘ3＋Ａｘ＋Ｂ（ｘ＝Ｘ/Ｚかつｙ＝Ｙ/Ｚと置くことで得られる）であり、Ｚ＝０である部分は唯一の（射影）点、すなわち（０：１：０）を有し、これをＯと表す。Ｋを、Ｆqを含む（必ずしも有限でない）体とする。集合
【００１８】
【数２】
2009515480.tif 000004
【００１９】
に、Ｏをその群の単元として有するアーベル群の構造を与えることができる。さらに、群操作を効率的に計算することができ、特に、Ｐ，ＱがＦq内の座標を有するＥ上の点である場合、任意のε＞０に対してＰ＋Ｑおよび−ＰをＯ（log1+εｑ）のビット操作で計算することができる。Ｈａｓｓｅの理論により群Ｅ（Ｆq）の大きさが厳密に見積もられる。すなわち、
【００２０】
【数３】
2009515480.tif 000005
【００２１】
である。
【００２２】
Ｓｃｈｏｏｆ−Ｅｌｋｉｅｓ−Ａｔｋｉｎアルゴリズムは
【００２３】
【数４】
2009515480.tif 000006
【００２４】
を計算する決定的多項式時間アルゴリズムである。
【００２５】
Ｗｅｉｌペアリング
Ｅ／Ｆqを楕円曲線とし、
【００２６】
【数５】
2009515480.tif 000007
【００２７】
をＦqの代数的閉包とする。ｍが体Ｆqの標数に対して相対的に素な整数である場合、ｍ捩れ点の群
【００２８】
【数６】
2009515480.tif 000008
【００２９】
は以下の構造を有する。
【００３０】
【数７】
2009515480.tif 000009
【００３１】
以下の特性を有する写像
【００３２】
【数８】
2009515480.tif 000010
【００３３】
が存在する。
写像ｅmが双線形である。すなわち
【００３４】
【数９】
2009515480.tif 000011
【００３５】
交代性：ｅm（Ｔ，Ｔ）＝１従ってｅm（Ｔ，Ｓ）＝ｅm（Ｓ，Ｔ）-1である。
非退化性：全てのＳ∈Ｅ［ｍ］に対してｅm（Ｓ，Ｔ）＝１ならばＴ＝Ｏである。
【００３６】
Ｅ／Ｆqを楕円曲線としＳ，ＴをＦqの座標を有するＥ上の２つのｍ捩れ点であるとする。するとｅm（Ｓ，Ｔ）をＯ（logｍlog1+εｑ）のビット操作で評価できる決定的アルゴリズムが存在する。このコンテキトから明らかな場合、ｅmの下付き文字ｍを省略する。
【００３７】
ネットワーク符号化モデル
コンテンツ分配に対する標準的なネットワーク符号化フレームワークを説明する。Ｇ＝（Ｖ，Ｅ）を有向グラフとする。情報源ｓ∈Ｖ（例えば、サーバ１０２および／またはクライアント１０６）は幾つかのデータ（分配されるコンテンツ）を頂点集合Ｔ⊆Ｖに送信することが望まれる。（例えば次元ｄの）ベクトル空間Ｗ／Ｆを選択し、一連のベクトルｗ1，・・・，ｗk∈Ｗとして送信されるデータ（例えば、セグメント化コンテンツ）を参照する。情報源は次いで、
【００３８】
【数１０】
2009515480.tif 000012
【００３９】
と置くことで拡張ベクトルｖ1，・・・，ｖkを生成する。ここで、ｗijはベクトルｗiのｊ番目の座標である。一般性を失うことなく、ベクトルｖiは線形独立であると仮定できる。これらのベクトルが張る（
【００４０】
【数１１】
2009515480.tif 000013
【００４１】
の）部分空間をＶで表す。各枝ｅ∈Ｅは、頂点ν＝ｉｎ（ｅ）に入るベクトルの線形結合ｙ（ｅ）を計算する。すなわち、
【００４２】
【数１２】
2009515480.tif 000014
【００４３】
である。ここで、ｍe∈Ｆpである。ｋ個のベクトルｗiを持つｋ個の入力枝を情報源が有すると考える。帰納法により、任意の枝のベクトルｙ（ｅ）は線形結合
【００４４】
【数１３】
2009515480.tif 000015
【００４５】
であり、Ｖ内のベクトルであることが分かる。ｋ次元ベクトル
【００４６】
【数１４】
2009515480.tif 000016
【００４７】
は単にベクトルｙ（ｅ）の最初のｋ個の座標である。行がベクトルｇ（ｅ1），・・・，ｇ（ｅk）である行列を、ｔに対するグローバル符号化行列（ｇｌｏｂａｌ  ｅｎｃｏｄｉｎｇ  ｍａｔｒｉｘ）と呼び、Ｇtで表す。ここで、ｅiはｔ∈Ｔに対する入力枝である。実際は、Ｇtが高い確率で可逆であるように符号化ベクトルをランダムに選択する。従って、任意の受信機はベクトルをｙ1，・・・，ｙk受信すると、次式を解くことでｗ1，・・・，ｗkを見つけることができる。
【００４８】
【数１５】
2009515480.tif 000017
【００４９】
ここで、ｙiはベクトルｙiの最初のｋ個の座標を除去することで形成したベクトルである。
【００５０】
例示的な準同型署名方式
ネットワーク符号化モジュール１１６は以下の例示的な準同型署名方式を実装する。ｐ（「他のプログラムデータ」１２０のそれぞれの部分で示す）を素数とし、ｑをｐ＜＜ｑとなるような異なる素数の累乗とする。Ｖ／Ｆqをｄ＋ｋ次元のベクトル空間とし、Ｅ／Ｆqを、Ｒ1，・・・，Ｒk，Ｐ1，・・・，ＰdがＥ（Ｆq）上の全ての（相異なる）ｐ捩れの点であるような楕円曲線とする。関数
【００５１】
【数１６】
2009515480.tif 000018
【００５２】
を次のように定義することができる。すなわち、
【００５３】
【数１７】
2009515480.tif 000019
【００５４】
に対して、
【００５５】
【数１８】
2009515480.tif 000020
【００５６】
関数
【００５７】
【数１９】
2009515480.tif 000021
【００５８】
はベクトル空間Ｖから、曲線上のｐ捩れ点（「他のプログラムデータ」１２０のそれぞれの部分）の群Ｅ［ｐ］への（加法アーベル群の）準同型である。
【００５９】
サーバ１０２（またはクライアント１０６）がｖ1，・・・，ｖk∈Ｖをクライアント装置１０６に分配することが望まれた場合を仮定すると、サーバはＦp内で秘密であるｓ1，・・・，ｓkとｒ1，・・・，ｒdを選択する。上記の秘密鍵は「他のプログラムデータ」１２０のそれぞれの部分として示される。サーバ１０２はパケットｖi（すなわち、署名済みブロック１２４）を
【００６０】
【数２０】
2009515480.tif 000022
【００６１】
を計算することで署名する。
【００６２】
サーバは１≦ｊ≦ｋに対してＲ1，・・・，Ｒk，Ｐ1，・・・，Ｐd，Ｑ，ｓjＱと、１≦ｉ≦ｄに対してｒiＱとを公開する（すなわち、サーバは「他のプログラムデータ」１２０のデータ部分を公開する）。ここで、Ｑは他とは異なる楕円曲線の別のｐ捩れ点であり、１≦ｊ≦ｋおよび１≦ｉ≦ｄに対してｅp（Ｒj，Ｑ）≠１かつｅp（Ｐi，Ｑ）≠１である。
【００６３】
本署名ｈj（すなわち、準同型のデジタル署名１２２）はさらにデータｖjに添付され、分配方式に従って送信される。ここで、任意の枝ｅで次式を計算する。
【００６４】
【数２１】
2009515480.tif 000023
【００６５】
符号化モジュール１１６はさらに
【００６６】
【数２２】
2009515480.tif 000024
【００６７】
を計算し、ｈ（ｅ）をデータｙ（ｅ）とともにパケットの線形結合として送信する。署名ｈ（ｅ）の計算は準同型であるので、
【００６８】
【数２３】
2009515480.tif 000025
【００６９】
である場合、
【００７０】
【数２４】
2009515480.tif 000026
【００７１】
となる。
【００７２】
例示的な検証プロセス
それぞれのクライアント装置１０６が実装する検証プロセスを説明する。
【００７３】
【数２５】
2009515480.tif 000027
【００７４】
と仮定して、ネットワーク符号化モジュール１１６−２に対するデジタル署名が
【００７５】
【数２６】
2009515480.tif 000028
【００７６】
であるかどうかを決定する。これは、ｈ（ｅ）がｙ（ｅ）の正規の署名であるならば定義から
【００７７】
【数２７】
2009515480.tif 000029
【００７８】
であり、従って
【００７９】
【数２８】
2009515480.tif 000030
【００８０】
【数２９】
2009515480.tif 000031
【００８１】
【数３０】
2009515480.tif 000032
【００８２】
であるので正常に動作する。
【００８３】
上記の検証はＷｅｉｌペアリングの双線形性を使用する。上の検証における全ての項を、ベクトルｙ（ｅ）または公開情報のいずれかから計算できることに留意されたい。
【００８４】
署名１２２はＦq内の座標を有する楕円曲線上の点で、従って署名の大きさはＯ（logｑ）ビットであり、これは送信オーバヘッドである。署名ｈ（ｅ）の計算はＯ（ｄinlogｐ log1+εｑ）ビット操作を必要とする。ここで、ｄinはｉｎ（ｅ）の入次数である。署名の検証はＯ（（ｄ＋ｋ）logｐ log1+εｑ）ビット操作を必要とする。
【００８５】
セキュリティの証明
前節の記法を本節でも使用する。説明した署名方式を阻止するため、敵対者は関数
【００８６】
【数３１】
2009515480.tif 000033
【００８７】
に対してハッシュ衝突を生成すること、または検証を通り抜けるように署名を偽造することの何れかを行うことができる。この場合、敵対者は点ｓ1Ｒ1，・・・，ｓkＲkおよびｒ1Ｐ1，・・・，ｒdＰdを知らないことに留意されたい。先ず、たとえ敵対者がそれらの点を知ったとしても、衝突の生成が離散対数の計算と同程度困難であることを示す。次に本主張を明確にする。
【００８８】
問題：ハッシュ衝突。整数ｒ＞１を固定する。入力：楕円曲線Ｅ／Ｆq上の次元ｐ（素数）の巡回部分群における所与の点Ｐ1，・・・，Ｐr。出力：ａ≠ｂかつ
【００８９】
【数３２】
2009515480.tif 000034
【００９０】
となるような組
【００９１】
【数３３】
2009515480.tif 000035
【００９２】
命題１：楕円曲線上の次元ｐの巡回群上の離散対数からハッシュ衝突への多項式時間変換が存在する。
【００９３】
証明：先ず、ｒ＝２の場合を扱う。ＰおよびＱを、恒等式ではないＥ（Ｆq）上の次元ｐの点であるとする。Ｑは、Ｐが生成した部分群内にあると仮定する。目標は、
【００９４】
【数３４】
2009515480.tif 000036
【００９５】
となるような
【００９６】
【数３５】
2009515480.tif 000037
【００９７】
を発見することであり、このためにハッシュ衝突を解決する本アルゴリズムを点ＰおよびＱに適用する。本アルゴリズムは、
【００９８】
【数３６】
2009515480.tif 000038
【００９９】
となるような２つの相異なる対
【０１００】
【数３７】
2009515480.tif 000039
【０１０１】
を生成する。これにより関係
【０１０２】
【数３８】
2009515480.tif 000040
【０１０３】
が与えられる。
【０１０４】
【数３９】
2009515480.tif 000041
【０１０５】
かつ
【０１０６】
【数４０】
2009515480.tif 000042
【０１０７】
であることが要求される。
【０１０８】
【数４１】
2009515480.tif 000043
【０１０９】
であると仮定すると
【０１１０】
【数４２】
2009515480.tif 000044
【０１１１】
となるが、Ｑは次元ｐ（素数）の点であるので
【０１１２】
【数４３】
2009515480.tif 000045
【０１１３】
、換言すればＦp内で
【０１１４】
【数４４】
2009515480.tif 000046
【０１１５】
である。これは、
【０１１６】
【数４５】
2009515480.tif 000047
【０１１７】
および
【０１１８】
【数４６】
2009515480.tif 000048
【０１１９】
が
【０１２０】
【数４７】
2009515480.tif 000049
【０１２１】
内の相異なる対であるという仮定と矛盾する。従って、
【０１２２】
【数４８】
2009515480.tif 000050
【０１２３】
である。ここで、逆変換はｐを法として取る。
【０１２４】
ｒ＞２とすると、２つの事のうち１つを行うことができる。前述のようにＰ1＝ＰかつＰ2＝Ｑを取ってｉ＞２に対してＰi＞Ｏと置くこと（この場合、証明はｒ＝２の場合に帰着する）、またはｒiをＦpからランダムに選択してＰ1＝ｒ1ＰおよびＰi＝ｒiＱを取ることの何れかを行うことができる。未知数が１つ（Ｑの離散対数）の式１つを得る。得た式が上記の未知数を含まない可能性も十分にある。しかしながら、この発生確率は次で議論するように非常に低い。ハッシュ衝突に対するアルゴリズムが
【０１２５】
【数４９】
2009515480.tif 000051
【０１２６】
を与えると仮定すると、
【０１２７】
【数５０】
2009515480.tif 000052
【０１２８】
である限り、Ｑの離散対数に関して解くことができる。しかしながらｒiがハッシュ衝突のオラクルに対して未知であるので、本プロセスの実施順序を交換することができる。換言すれば、
【０１２９】
【数５１】
2009515480.tif 000053
【０１３０】
に対してｂiが与えられると、選択したｒiが
【０１３１】
【数５２】
2009515480.tif 000054
【０１３２】
を満たす確率は幾つであろうか。後者の確率は
【０１３３】
【数５３】
2009515480.tif 000055
【０１３４】
であることは明らかである。従って、高い確率でＱの離散対数に関して解くことができる。
【０１３５】
上述の命題を、Ｂｅｌｌａｒｅ，Ｍ．；Ｇｏｌｄｒｅｉｃｈ，Ｏ．；Ｇｏｌｄｗａｓｓｅｒ，Ｓ；Ｉｎｃｒｅｍｅｎｔａｌ  ｃｒｙｔｏｇｒａｐｈｙ：Ｔｈｅ  ｃａｓｅ  ｏｆ  ｈａｓｈｉｎｇ  ａｎｄ  ｓｉｇｎｉｎｇ，ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  ＣＲＹＰＴＯ‘９４，Ｓａｎｔａ  Ｂａｒｂａｒａ，ＣＡ，１９９４で示されている証明から導くこともできる。本証明は有限体を扱うが、その議論は楕円曲線の場合にも同様に当てはまる。
【０１３６】
ネットワーク符号化モジュール１１６に対するデジタル署名で実装した方式では、ハッシュ衝突を生成することは困難であることを示した。敵対者がその方式を阻止しうる他の手段は、署名を偽造することである。しかしながら、署名の偽造は少なくとも、いわゆる楕円曲線上のｃｏ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題を解くことと同程度困難である。楕円曲線上の本問題を解く唯一の既知の方法は、離散対数の計算を通したものである。従って、署名の偽造は少なくとも楕円曲線上の計算論的ｃｏ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ｃｏｍｐｕｔａｔｉｏｎａｌ  ｃｏ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）問題を解くことと同程度困難であり、恐らく離散対数の計算と同程度困難であろう。
【０１３７】
例示的な設定
ネットワーク符号化モデルと例示的な準同型署名方式とを説明する場合に、上記で提示した記法を本節でも利用する。署名方式を初期化するため、図１のモジュール１１６は素数ｐを、適切な体上で定義したｐ捩れ全体を有するその適切な体上の後述するものとともに選択する。楕円曲線を選択する例示的な技術を「適切な楕円曲線の発見」というタイトルの節で後述する。モジュール１１６はさらに、準同型署名１２２の定義に必要な一連のｐ捩れ点を識別する。本節では、全てのこれらの事柄を議論し、さらに例を提供する。
【０１３８】
要約すると、
大きな素数ｐを取る。
（「適切な楕円曲線の発見」というタイトルの節で後述するように）適切な素数lを取り、ｐの倍数の多点を有するＦl上の楕円曲線Ｅを取る。
【０１３９】
【数５４】
2009515480.tif 000056
【０１４０】
となるように、体Ｆlの拡張Ｆqを発見する（ここで、Ｅ［ｐ］は全てのｐ捩れ点の集合を指す）。
【０１４１】
【数５５】
2009515480.tif 000057
【０１４２】
であるので、体Ｆlの拡張Ｆqはｐ捩れ点を有する。Ｏ≠Ｐ∈Ｅ（Ｆl）を曲線上のｐ捩れ点とする。
【０１４３】
【数５６】
2009515480.tif 000058
【０１４４】
に対して
【０１４５】
【数５７】
2009515480.tif 000059
【０１４６】
および
【０１４７】
【数５８】
2009515480.tif 000060
【０１４８】
に対して
【０１４９】
【数５９】
2009515480.tif 000061
【０１５０】
を取る。ここで、
【０１５１】
【数６０】
2009515480.tif 000062
【０１５２】
および
【０１５３】
【数６１】
2009515480.tif 000063
【０１５４】
は集合１，・・・，ｐ−１からランダムに取得する。
Ｑはｅ（Ｒi，Ｑ）≠１かつｅ（Ｐj，Ｑ）≠１となるような点である。これを保証するため、より小さな体Ｆl上ではなくＦq上で定義したｐ捩れの点を取れば十分である。実際、Ｑを上記の点とすると、ｅ（Ｒi，Ｑ）＝１である場合、（Ｒi，およびＱがＥ［ｐ］を生成するので）これは任意のＡ，Ｂ∈Ｅ［ｐ］に対してｅ（Ａ，Ｂ）＝１であることを意味するであろう。これはＷｅｉｌペアリングの非退化性と矛盾する。
最後に、モジュール１１６は秘密鍵ｓ1，・・・，ｓkとｒ1，・・・，ｒdを
【０１５５】
【数６２】
2009515480.tif 000064
【０１５６】
からランダムに選択する。
【０１５７】
適切な楕円曲線の発見
一般に、有限体Ｋ上に楕円曲線Ｅがある場合、ｐ捩れ点を体Ｋ上のΘ（ｐ2）次元の拡張上に定義することができる。モジュール１１６の操作を多項式時間で実行できるように、ｐ捩れ点を小さい体上で定義する。本節では、適切な体Ｆlとこの体上の楕円曲線とをどのように取ることができるかを議論する。その楕円曲線は、全ての自身のｐ捩れ点を基礎体の小さな相対的拡張上で定義する。
【０１５８】
楕円曲線の既知の虚数乗法論を使用して、一定数の点を有する有限体上で楕円曲線を定義することができる。本アルゴリズムの詳細は我々の使用には必要ではないが、その実行時間を利用するのでそれを次に説明する。厳密にＮ個の点を有する楕円曲線Ｅ／Ｆl（lは素数）を生成したいとする。ここで、Ｎは区間
【０１５９】
【数６３】
2009515480.tif 000065
【０１６０】
内にある。Ｎを
【０１６１】
【数６４】
2009515480.tif 000066
【０１６２】
と書き、
【０１６３】
【数６５】
2009515480.tif 000067
【０１６４】
とする。ここでＤまたはＤ／４は平方因子を含まない（Ｈａｓｓｅ境界のためＤは負であることに留意されたい）。次いで上記曲線を生成するアルゴリズムは時間
【０１６５】
【数６６】
2009515480.tif 000068
【０１６６】
で実行する。
【０１６７】
システム１００では、楕円曲線をｐの小さな倍数個の点で求め、このことは上記曲線を求めるべき体Ｆlは
【０１６８】
【数６７】
2009515480.tif 000069
【０１６９】
を満たさなければならないことを意味する。さらに、
【０１７０】
【数６８】
2009515480.tif 000070
【０１７１】
は小さな平方因子を含まない部分を有するべきである。なぜならば、これが上記曲線の生成方法の実行時間を決定するからである。小さな（負の）Ｄに対して
【０１７２】
【数６９】
2009515480.tif 000071
【０１７３】
かつl≡−１modｐとなるように素数lを選択し、
【０１７４】
【数７０】
2009515480.tif 000072
【０１７５】
と置く。従って、
【０１７６】
【数７１】
2009515480.tif 000073
【０１７７】
であり、楕円曲線上の点の数はｐの倍数となり、
【０１７８】
【数７２】
2009515480.tif 000074
【０１７９】
が小さいため上記曲線の生成時間も合理的となる。
【０１８０】
上記素数lを生成するため、（負の）（
【０１８１】
【数７３】
2009515480.tif 000075
【０１８２】
が小さい）Ｄを選択する。
【０１８３】
【数７４】
2009515480.tif 000076
【０１８４】
がｙ＝０，１，・・・に対して素数かどうかを決定する。≡−１modｐである素数にのみ関心があるので、上記の検査を、−Ｄｙ2≡−４modｐであるｙの値に対してのみ実施する。Ｌａｎｇ−Ｔｒｏｔｔｅｒの予想によると、素数を生成する多数のｙの値が存在することになる。これは、２次多項式の素数値に関するＨａｒｄｙ−Ｌｉｔｔｌｅｗｏｏｄの予想にも関連する。この虚数乗数法により、幾つかのｐ捩れ点を有するＦl上の楕円曲線Ｅが与えられる。しかしながら、Ｆlの小さな次数拡張上でＥ［ｐ］が定義されるような楕円曲線を必要とする。これは、l≡−１modｐである付加制限を使用する場合である。l≡−１modｐであるので、
【０１８５】
【数７５】
2009515480.tif 000077
【０１８６】
内のlの次数は２である。Ｋｏｂｌｉｔｚ−Ｂａｌａｓｕｂｒａｍａｎｉａｎの定理によると、この場合、全体のｐ捩れが基礎体上の次数２の拡張上で定義されること、換言すれば
【０１８７】
【数７６】
2009515480.tif 000078
【０１８８】
であることが示される。楕円曲線Ｅ／Ｆl（「他のプログラムデータ」１２０のそれぞれの部分）を得たので、全てのそのｐ捩れがＥ［l］上で定義されることを知るが、これらの点をどのように発見できるであろうか。これが次の段落の主題である。
【０１８９】
所見１。虚数乗法の理論によると、曲線Ｅは量Ｄにのみ依存する。より厳密には、各Ｄに対して、Ｅ mod l が我々の要件を満たすような数体Ｋ上の楕円曲線の有限リストＥ1，・・・，Ｅmが存在する。これを、以下の「例」というタイトルの節で例示する。
【０１９０】
ｐ捩れ点の発見
Ｅ／Ｆlを上記で与えた方法を使用して特定した楕円曲線とする。すると、
【０１９１】
【数７７】
2009515480.tif 000079
【０１９２】
であり、ｍを、ｐに対して素数である
【０１９３】
【数７８】
2009515480.tif 000080
【０１９４】
の最大因数であるとする。Ｐを、曲線Ｅ（Ｆl）上のランダムな点であるとする。ｍＰ≠Ｏと仮定すると、（Ｌａｇｒａｎｇｅの定理によれば）ｍＰはｐ乗の捩れの点である。
【０１９５】
【数７９】
2009515480.tif 000081
【０１９６】
を、
【０１９７】
【数８０】
2009515480.tif 000082
【０１９８】
だが
【０１９９】
【数８１】
2009515480.tif 000083
【０２００】
であるような最小の整数とする。すると
【０２０１】
【数８２】
2009515480.tif 000084
【０２０２】
はｐ捩れの点である。もちろん、ｍＰ＝Ｏであることが分かれば、別のランダムな点Ｐを発見することで繰り返す。ランダムな点Ｐに対してｍＰ＝Ｏである確率は高々
【０２０３】
【数８３】
2009515480.tif 000085
【０２０４】
であり、従って非常に高い確率で自明でないｐ捩れの点を発見するであろう。
【０２０５】
これにより、Ｆl上で定義したｐ捩れの１部が与えられる。
【０２０６】
【数８４】
2009515480.tif 000086
【０２０７】
上で定義されるそのｐ捩れを発見するため、上記のプロセスを
【０２０８】
【数８５】
2009515480.tif 000087
【０２０９】
上で繰り返す。本プロセスを実行するため、
【０２１０】
【数８６】
2009515480.tif 000088
【０２１１】
上の点の数を知る必要がある。Ｅを有限体Ｋ上で定義すると、Ｋの任意の拡張上でのＥ上の点の数は
【０２１２】
【数８７】
2009515480.tif 000089
【０２１３】
により決定されることが分かる。その理論によると、我々の曲線Ｅに対して
【０２１４】
【数８８】
2009515480.tif 000090
【０２１５】
であることが予測される。ここで、
【０２１６】
【数８９】
2009515480.tif 000091
【０２１７】
、
【０２１８】
【数９０】
2009515480.tif 000092
【０２１９】
は方程式
【０２２０】
【数９１】
2009515480.tif 000093
【０２２１】
の（Ｃにおける）２つの根である。
【０２２２】
例
本例は、コンピュータ代数パッケージＭＡＧＭＡを使用して生成した。本例に対して、Ｄ＝−４を取る。任意の素数ｐに対し、適切な素数lは、l≡−１modｐとなるように
【０２２３】
【数９２】
2009515480.tif 000094
【０２２４】
を満たすものである。その合同性は、ｙ2≡−１modｐ、換言すれば必ず−１がｐを法とする２乗残余であることを意味する。これは次いでｐ≡１mod４であることを意味し、我々が求める必要があるｙの値は必ず−１modｐの２乗根の１つと合同であることを意味する。
【０２２５】
ｐを次のような素数とする。
【０２２６】
【数９３】
2009515480.tif 000095
【０２２７】
特殊な特性を有する素数値ｐ2＋ｙ2を求める。虚数乗数法により、楕円曲線
【０２２８】
【数９４】
2009515480.tif 000096
【０２２９】
が適切な楕円曲線であることが分かる。ＭＡＧＭＡにより、
【０２３０】
【数９５】
2009515480.tif 000097
【０２３１】
は
【０２３２】
【数９６】
2009515480.tif 000098
【０２３３】
であることが分かる。これは実際≡０modｐである。
【０２３４】
【数９７】
2009515480.tif 000099
【０２３５】
上の点の数はＭＡＧＭＡによると、
【０２３６】
【数９８】
2009515480.tif 000100
【０２３７】
であり、これは≡０modｐ2である。これはＥ［ｐ］が
【０２３８】
【数９９】
2009515480.tif 000101
【０２３９】
の部分群であるための必要条件である。ｐ捩れの部分群を生成する２つの点を発見することで、Ｅ［ｐ］が実際に
【０２４０】
【数１００】
2009515480.tif 000102
【０２４１】
に含まれることを示す。５．２節で概説した方法に従って、
【０２４２】
【数１０１】
2009515480.tif 000103
【０２４３】
のｐ捩れ全体を生成する２つのｐ捩れの点ＰおよびＱを発見する。
【０２４４】
【数１０２】
2009515480.tif 000104
【０２４５】
ここで、ｕは２次既約（ｑｕａｄｒａｔｉｃ  ｉｒｒｅｄｕｃｉｂｌｅ）
【０２４６】
【数１０３】
2009515480.tif 000105
【０２４７】
に対する同型
【０２４８】
【数１０４】
2009515480.tif 000106
【０２４９】
を与える変数である。ＰおよびＱのＷｅｉｌペアリングは
【０２５０】
【数１０５】
2009515480.tif 000107
【０２５１】
である。
【０２５２】
例示的な手順
図２は、一実施形態に従って、ネットワーク符号化に対するデジタル署名の例示的な手順２００を示す。例示的な説明のため、手順２００の操作を図１のシステム１００の構成要索に関連して説明する。構成要素の参照番号の左端の数字は、構成要素を最初に説明した特定の図面を示す。
【０２５３】
ブロック２０２、サーバ１０２は、分配されるコンテンツの一連のセグメント化ブロックの各々を、それぞれの準同型のデジタル署名１２２（図１）でデジタル署名する。これを、ベクトル（例えば、それぞれのセグメント化ブロック）を楕円曲線上の点集合に変換することで実現する。これらの変換を、衝突回避ハッシュ関数を使用して実施する。その衝突回避ハッシュ関数は、ベクトル空間から、楕円曲線上の素数個の捩れ点からなる群への（加法アーベル群の）準同型である。
【０２５４】
ブロック２０４で、サーバ１０２はパケットを、そのパケット内にカプセル化したセグメント化コンテンツの署名に使用される公開情報（例えば、楕円曲線上のある特定の相異なる素数（ｐ）個の捩れ点）とともに、ネットワーク１０４に渡って目的の装置（例えば、それぞれのクライアント装置１０６）に分配する。そのパケットおよび情報を、分配方式を使用して分配する。一実装では、その分配方式はネットワーク符号化分配方式である。セグメント化コンテンツ（すなわち、ベクトル）をデジタル署名するためにブロック２０２の操作で使用した秘密鍵およびハッシュダイジェストのような秘密情報を、サーバ１０２によりパケットおよび公開情報の線形結合とともに分配することはない。
【０２５５】
ブロック２０６で、クライアント装置１０６は１つまたは複数の分配したパケットの線形結合を受信する。ブロック２０８で、クライアント装置１０６は、受信パケットとともにサーバが分配した公開情報を使用して、受信パケット内にカプセル化したコンテンツを検証および認証する。ブロック２１０で、クライアント装置１０６は、それが受信パケットの受信に関して最終目的装置であるかどうかを決定する。最終目的装置でない場合、操作は上述のようにブロック２０２で継続するが、この場合クライアント装置１０６は、実際にはサーバ１０２になる。より詳細には、本シナリオでは、クライアント装置１０６はパケットの線形結合の一部のデジタル署名を知りえて、クライアント装置１０６はパケット（すなわち、受信パケット）の任意の線形結合の署名を生成することができる。これによりクライアント装置１０６は、情報源（すなわち、本繰り返しではサーバ１０２）と接触せずにパケットをデジタル的に再署名することができる。さらに、これによりクライアント装置は、入力の線形結合を送信したと不当に主張する任意のノード（例えば、サーバ１０２および／またはクライアント１０６）を、実際にそのノードが他のデータまたは不要なデータを投入したときに、検出することができる。この点を考慮して、クライアント装置は、セグメント化ブロックをデジタル署名するために使用する関連公開情報とともに、再署名したパケットを新規の線形結合で目的の装置に分配する。ブロック２０２から２１０までの操作を、分配コンテンツが目的の装置に到着するまで任意数のサーバ１０２およびクライアント装置１０６により繰り返す。
【０２５６】
例示的操作環境
図３は、ネットワーク符号化に対するデジタル署名を完全または部分的に実装可能で、適切なコンピューティング環境の例を示す。例示的なコンピューティング環境３００は、図１の例示的なシステムおよび図２の例示的な操作に対する適切なコンピューティング環境の１つの例に過ぎず、本明細書で説明したシステムおよび方法の使用または機能性の範囲に関する限定を暗示するようには意図していない。コンピューティング環境３００を、コンピューティング環境３００に示した構成要素の任意の１つ、または組合せに関する任意の依存性または要件を有するものとして解釈すべきでない。
【０２５７】
本明細書で説明した方法およびシステムは、多数の他の汎用または特殊目的のコンピューティングシステム、環境または構成と操作可能である。使用に適する可能性がある公知のコンピューティングシステム、環境、および／または構成の例には、パーソナルコンピュータ、サーバコンピュータ、マルチプロセッサシステム、マイクロプロセッサベースのシステム、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、任意の上記のシステムまたは装置を含む分散コンピューティング環境、等が含まれるがこれらに限らない。フレームワークの小型またはサブセットの版を、ハンドヘルドコンピュータ、または他のコンピューティング装置のようなリソースが制限されたクライアントで実装することもできる。本発明を、通信ネットワークを通して接続したリモートプロセッシング装置によりタスクが実施される分散コンピューティング環境で実践する。分散コンピューティング環境では、プログラムモジュールをローカルおよびリモートメモリ記憶装置の両方に配置することができる。
【０２５８】
図３を参照すると、ネットワーク符号化に対するデジタル署名の例示的なシステムは、例えば図１のシステム１００を実装するコンピュータ３１０の形式で汎用コンピューティング装置を含む。以下で説明するコンピュータ３１０の態様は、図１のコンピューティング装置１０２および１０４の例示的な実装である。コンピュータ３１０の構成要素は、演算装置（複数）３２０、システムメモリ３３０、およびシステムメモリを含む様々なシステムコンポーネントを演算装置３２０に接続するシステムバス３２１を含むことができるが、これらに限らない。システムバス３２１は任意の数種のバス構造で可能である。このバス構造には、メモリバスまたはメモリコントローラ、周辺バス、および任意の様々なバスアーキテクチャを使用するローカルバスが含まれる。限定ではなく例として、上記のアーキテクチャはＩＳＡ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、およびメザニンバスとしても知られるＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）バスを含むことができる。
【０２５９】
コンピュータ３１０は一般に様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ３１０がアクセス可能な任意の利用可能な媒体で可能で、揮発性および不揮発性媒体、取り外し可能および取り外し不可能媒体の両方を含む。限定ではなく例として、コンピュータ可読媒体はコンピュータ記憶媒体および通信媒体を備えることができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータのような情報の記憶に対する任意の方法または技術で実装した揮発性および不揮発性、取り外し可能および取り外し不可能媒体を含む。コンピュータ記憶媒体にはＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｋｓ）もしくは他の光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶もしくは他の磁気記憶装置、または所望の情報の記憶に使用でき、かつコンピュータ３１０がアクセス可能な任意の他の媒体が含まれるがこれらに限らない。
【０２６０】
通信媒体は一般にコンピュータ可読命令、データ構造、プログラムモジュール、または、搬送波もしくは他の送信メカニズムのような変調データ信号の他のデータを具現化し、任意の情報配信媒体を含む。用語「変調データ信号」は１つまたは複数の特性集合を有するか、または情報を信号内で符号化するよう変化した信号を意味する。限定ではなく例として、通信媒体には、有線ネットワークまたは直接配線通信のような有線媒体、および音響、ＲＦ、赤外線および他の無線媒体のような無線媒体が含まれる。上述の任意の組合せもコンピュータ可読媒体の範囲に含まれるべきである。
【０２６１】
システムメモリ３３０はＲＯＭ（ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）３３１およびＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）３３２のような揮発性および／または不揮発性メモリの形式でコンピュータ記憶媒体を含む。コンピュータシステム３１０内部の要素間で起動中のときような情報転送を支援する基本ルーチンを含むＢＩＯＳ（ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）３３３を一般にＲＯＭ３３１に記憶する。ＲＡＭ３３２は一般に、演算装置３２０が即座にアクセス可能および／または演算装置３２０上で現在実行中のデータおよび／またはプログラムモジュールを含む。限定ではなく例として、図３はオペレーティングシステム３３４、アプリケーションプログラム３３３、他のプログラムモジュール３３６、およびプログラムデータ３３７を示す。
【０２６２】
コンピュータ３１０は、他の取り外し可能／取り外し不可能、揮発性／不揮発性コンピュータ記憶媒体も含んでもよい。例としてのみ、図３は、取り外し不可能、不揮発性磁気媒体を読み書きするハードディスクドライブ３４１、取り外し可能、不揮発性磁気ディスク３３２を読み書きする磁気ディスクドライブ３３２、およびＣＤ−ＲＯＭまたは他の光媒体のような取り外し可能、不揮発性光ディスク３３６を読み書きする光ディスクドライブ３３３を示す。例示的な操作環境で使用可能な他の取り外し可能／取り外し不可能、揮発性／不揮発性コンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、半導体ＲＡＭ、半導体ＲＯＭ、等を含まれるがこれらに限らない。ハードディスクドライブ３４１は一般にインタフェース３４０のような取り外し不可能メモリインタフェースを通してシステムバス３２１に接続され、磁気ディスクドライブ３３１および光ディスクドライブ３３３は一般にインタフェース３３０のような取り外し可能メモリインタフェースによってシステムバス３２１に接続される。
【０２６３】
上記および図３で示したドライブおよびその関連コンピュータ記憶媒体は、コンピュータ３１０に対するコンピュータ可読命令、データ構造、プログラムモジュールおよび他のデータを記憶する。図３では、例えば、ハードディスクドライブ３４１をオペレーティングシステム３４４、アプリケーションプログラム３４３、他のプログラムモジュール３４６、およびプログラムデータ３４７を記憶するとして示してある。これらのコンポーネントは、オペレーティングシステム３３４、アプリケーションプログラム３３３、他のプログラムモジュール３３６、およびプログラムデータ３３７と同一であるか、または異なるかのいずれかで可能であることに留意されたい。アプリケーションプログラム３３３は、例えば、図１のプログラムモジュール１２２を含み、プログラムデータ３３７は、例えば、図１のプログラムデータ１１４を含んでいる。オペレーティングシステム３４４、アプリケーションプログラム３４３、他のプログラムモジュール３４６、およびプログラムデータ３４７に異なる数字を与えて、それらが少なくとも異なるコピーであることをここでは示している。
【０２６４】
ユーザは、キーボード３６２、一般的にマウスと呼ばれるポインティングデバイス３６１、トラックボールまたはタッチパッドのような入力装置を通して命令および情報をコンピュータ３１０に入力することができる。他の入力装置（図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナ、等を挙げることができる。これらおよび他の入力装置を、システムバス３２１に接続したユーザ入力インタフェース３６０を通して演算装置３２０に接続することがよくあるが、パラレルポート、ゲームポートまたはＵＳＢ（ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ）のような他のインタフェースおよびバス構造により接続してもよい。
【０２６５】
モニタ３９１または他種のディスプレイ装置も、ビデオインタフェース３９０のようなインタフェース経由でシステムバス３２１に接続する。モニタに加えて、コンピュータはプリンタ３９６およびオーディオ装置（複数）３９７のような、出力周辺インタフェース３９３を通して接続可能な他の周辺出力装置を含むこともできる。
【０２６６】
コンピュータ３１０は、リモートコンピュータ３８０のような１つまたは複数のリモートコンピュータに論理接続を使用して、ネットワーク環境で操作することができる。一実装では、リモートコンピュータ３８０は図１のコンピューティング装置１０２またはネットワークコンピュータ１０４を表す。リモートコンピュータ３８０はパーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイスまたは他の共通ネットワークノードで可能であり、その特定の実装の機能として、コンピュータ３１０に関して上記した要素の多数または全てを含むことができるが、メモリ記憶装置３８１のみを図３に示してある。図３に示した論理接続はローカルエリアネットワーク（ＬＡＮ）３７１および広域エリアネットワーク（ＷＡＮ）３７３を含むが、他のネットワークを含むこともできる。上記のネットワーク環境は職場、企業規模のコンピュータネットワーク、イントラネットおよびインターネットで一般的である。
【０２６７】
ＬＡＮネットワーク環境で使用する場合、ネットワークインタフェースまたはアダプタ３７０を通してコンピュータ３１０をＬＡＮ３７１に接続する。ＷＡＮネットワーク環境で使用するとき、コンピュータ３１０は一般にモデム３７２、または、インターネットのようなＷＡＮ３７３上で通信を確立するための他の手段を含む。モデム３７２は、内部または外部でよく、ユーザ入力インタフェース３６０、または他の適切なメカニズムを通してシステムバス３２１に接続することができる。ネットワーク環境では、コンピュータ３１０、またはその一部に関して示したプログラムモジュールをリモートメモリ記憶装置に記憶することができる。限定ではなく例として、図３ではメモリ装置３８１上に存在するとしてリモートアプリケーションプログラム３８３を示してある。示したネットワーク接続は例であって、コンピュータ間の通信を確立する他の手段を使用することが可能である。
【０２６８】
結論
ネットワーク符号化におけるデジタル署名のシステムおよび方法を構造的特徴および／または方法論的操作もしくは働きに固有な言葉で説明したが、添付請求項で定義した実装は必ずしも説明した特徴または働きに限定されないことは理解されよう。むしろ、システム１００の特徴および操作は請求項主題を実装する例示的な形態として開示してある。
【図面の簡単な説明】
【０２６９】
【図１】一実施形態に従って、ネットワーク符号化の分配方式に基づき、コンテンツの分配時にデジタル署名を利用する例示的なシステムの図である。
【図２】一実施形態に従って、ネットワーク符号化の分配方式でデジタル署名を使用するための例示的な手順を示す図である。
【図３】ネットワーク符号化に対するデジタル署名を完全または部分的に実装可能であり、適切なコンピューティング環境の例を示す図である。
【図１】
2009515480.tif 000134
【図２】
2009515480.tif 000135
【図３】
2009515480.tif 000136
【国際調査報告】
2009515480.tif 000137
2009515480.tif 000138