説明

ネットワークシステム、ネットワーク構成方法およびプログラム

【課題】強セキュアなネットワーク符号を用いたシンプルなネットワークを構成するとともに、高速な処理を実現する。
【解決手段】ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行い、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する。そして、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証し、ネットワーク上への全リンクの符号化ベクトルを出力する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、強セキュアなネットワーク符号を用いたネットワークシステム、ネットワーク構成方法およびプログラムに関する。
【背景技術】
【0002】
近年、ネットワーク上のノード(たとえばルータ・スイッチ)に従来のコピー・転送機能ではなく、数学的演算機能を持たせることによって、伝送レート・スループットの向上や消費エネルギーの低減を実現するネットワーク符号化と呼ばれる技術が注目を浴びている(例えば、非特許文献1参照。)。
【0003】
ところで、ネットワーク上では、「伝送リンクの盗聴」攻撃が懸念される。このため、盗聴対策を施したネットワーク符号の構成法がいくつか提案されている(例えば、非特許文献2から非特許文献4参照。)。これらの手法は、ネットワークを構成するリンクのうち、ある一定個数個まで盗聴されても、送信情報が情報理論的に漏えいしない安全性が示されている。
【先行技術文献】
【非特許文献】
【0004】
【非特許文献1】R. Ahlswede, N. Cai, S.−Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp.1204-1216, 2000.
【非特許文献2】N. Cai and R. W. Yeung, “Secure network coding,” in Proceeding of IEEE International Symposium on Information Theory (ISIT) 2002, pp.323, 2002.
【非特許文献3】N. Cai and R. W. Yeung, “Secure network Coding on a wiretap network,” IEEE Transactions on Information Theory, vol. 57, no. 1, pp.424-435,2011.
【非特許文献4】S. Y. E. Rouayheb and E. Soljanin, “On wiretap networks II,” in Proceeding of IEEE International Symposium on Information Theory (ISIT) 2007, pp.551-555, 2007.
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、上記に記載の技術では、一定個数を超える数のリンクを盗聴されると、送信情報の一部が確定的に漏えいする可能性があることが指摘されている。
【0006】
そこで、本発明は、上述の課題に鑑みてなされたものであり、強セキュアなネットワーク符号を用いたシンプルなネットワークを構成するとともに、高速な処理を実現するネットワークシステム、ネットワーク構成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【0007】
本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【0008】
(1)本発明は、送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムであって、前記符号化ベクトル設定装置が、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行うアルゴリズム実行手段(例えば、図2のアルゴリズム実行部110に相当)と、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する線形独立性検証手段(例えば、図2の線形独立性検証部120に相当)と、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する検証手段(例えば、図2の検証部130に相当)と、ネットワーク上への全リンクの符号化ベクトルを出力する出力手段(例えば、図2の出力部140に相当)と、を備えたことを特徴とするネットワークシステムを提案している。
【0009】
この発明によれば、アルゴリズム実行手段は、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行う。線形独立性検証手段は、アルゴリズム実行手段の各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する。検証手段は、アルゴリズム実行手段の各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する。出力手段は、ネットワーク上への全リンクの符号化ベクトルを出力する。したがって、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができる。
【0010】
(2)本発明は、(1)のネットワークシステムについて、前記アルゴリズム実行手段のアルゴリズムが、LIF(Linear Information Flow)アルゴリズムであることを特徴とするネットワークシステムを提案している。
【0011】
この発明によれば、アルゴリズム実行手段のアルゴリズムが、LIF(Linear Information Flow)アルゴリズムである。したがって、シンプルなアルゴリズムにより、符号化ベクトル設定装置を構築することができる。
【0012】
(3)本発明は、(1)または(2)のネットワークシステムについて、前記最大距離分離符号が、リードソロモン符号をはじめとして既存の符号を利用可能であることを特徴とするネットワークシステムを提案している。
【0013】
この発明によれば、最大距離分離符号として、たとえばリードソロモン符号が利用できる。したがって、シンプルな構成が可能である。また、既存の最大距離分離符号の符号化および復号手法の周辺技術を利用することが可能であるため、高速な手法が利用できる。
【0014】
(4)本発明は、(1)から(3)のネットワークシステムについて、前記送信装置が、乱数を生成する乱数生成手段(例えば、図3の乱数生成部210に相当)と、最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する符号化手段(例えば、図3の符号化部220に相当)と、該出力された符号語を前記符号化ベクトル設定装置により構成されたネットワークへ送信する送信手段(例えば、図3の送信部230に相当)と、を備えたことを特徴とするネットワークシステムを提案している。
【0015】
この発明によれば、乱数生成手段は、乱数を生成する。符号化手段は、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する。送信手段は、出力された符号語を符号化ベクトル設定装置により構成されたネットワークへ送信する。したがって、シンプルな構成で、シンドローム符号語を導出して送信することができる。
【0016】
(5)本発明は、(4)のネットワークシステムについて、最大距離分離符号を利用することを特徴とするネットワークシステムを提案している。
【0017】
この発明によれば、最大距離分離符号として、たとえばリードソロモン符号が利用できる。したがって、シンプルな構成が可能である。また、既存の最大距離分離符号の符号化および復号手法の周辺技術を利用することが可能であるため、高速な手法が利用できる。
【0018】
(6)本発明は、(5)のネットワークシステムについて、前記符号化手段が、送信情報のコセット符号化を行い符号語を出力することを特徴とするネットワークシステムを提案している。
【0019】
この発明によれば、符号化手段が、送信情報のコセット符号化を行い符号語を出力する。したがって、シンプルな構成で、符号語を導出することができる。
【0020】
(7)本発明は、(1)から(3)のネットワークシステムについて、前記受信装置が、(1)から(3)に記載の符号化ベクトル設定装置により構成されたネットワークから受信ベクトルを受信する受信手段(例えば、図4の受信部310に相当)と、該受信ベクトルを線形変換して符号語を導出する符号語導出手段(例えば、図4の符号語導出部320に相当)と、該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号するシンドローム導出手段(例えば、図4のシンドローム導出部330に相当)と、を備えたことを特徴とするネットワークシステムを提案している。
【0021】
この発明によれば、受信手段は、構成されたネットワークから受信ベクトルを受信する。符号語導出手段は、受信ベクトルを線形変換して符号語を導出する。シンドローム導出手段は、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する。したがって、シンプルな構成で、送信情報を復号することができる。
【0022】
(8)本発明は、(7)のネットワークシステムについて、前記符号語導出手段が、コセット符号化の符号語を導出することを特徴とするネットワークシステムを提案している。
【0023】
この発明によれば、符号語導出手段が、コセット符号化の符号語を導出する。したがって、シンプルな構成で、符号語を導出することができる。
【0024】
(9)本発明は、(8)のネットワークシステムについて、最大距離分離符号を利用することを特徴とするネットワークシステムを提案している。
【0025】
この発明によれば、最大距離分離符号として、たとえばリードソロモン符号が利用できる。したがって、シンプルな構成が可能である。また、既存の最大距離分離符号の符号化および復号手法の周辺技術を利用することが可能であるため、高速な手法が利用できる。
【0026】
(10)本発明は、送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムにおけるネットワーク構成方法であって、前記符号化ベクトル設定装置が、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行う第1のステップ(例えば、図5のステップS101に相当)と、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する第2のステップ(例えば、図5のステップS102に相当)と、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する第3のステップ(例えば、図5のステップS103に相当)と、ネットワーク上への全リンクの符号化ベクトルを出力する第4のステップ(例えば、図5のステップS104に相当)と、を備えたことを特徴とするネットワーク構成方法を提案している。
【0027】
この発明によれば、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行い、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する。そして、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証し、ネットワーク上への全リンクの符号化ベクトルを出力する。したがって、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができる。
【0028】
(11)本発明は、(10)のネットワーク構成方法について、前記送信装置が、乱数を生成する第5のステップ(例えば、図6のステップS201に相当)と、最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する第6のステップ(例えば、図6のステップS202に相当)と、該出力された符号語を前記構成されたネットワークへ送信する第7のステップ(例えば、図6のステップS203に相当)と、を備えたことを特徴とするネットワーク構成方法を提案している。
【0029】
この発明によれば、乱数を生成し、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する。そして、出力された符号語を構成されたネットワークへ送信する。したがって、シンプルな処理で、符号語を導出して送信することができる。
【0030】
(12)本発明は、(11)のネットワーク構成方法について、前記受信装置が、前記構成されたネットワークから受信ベクトルを受信する第8のステップ(例えば、図7のステップS301に相当)と、該受信ベクトルを線形変換して符号語を導出する第9のステップ(例えば、図7のステップS302に相当)と、該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する第10のステップ(例えば、図7のステップS303に相当)と、を備えたことを特徴とするネットワーク構成方法を提案している。
【0031】
この発明によれば、構成されたネットワークから受信ベクトルを受信し、受信ベクトルを線形変換して符号語を導出する。そして、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する。したがって、シンプルな処理で、送信情報を復号することができる。
【0032】
(13)本発明は、送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムにおけるネットワーク構成方法をコンピュータに実行させるためのプログラムであって、前記符号化ベクトル設定装置が、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行う第1のステップ(例えば、図5のステップS101に相当)と、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する第2のステップ(例えば、図5のステップS102に相当)と、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する第3のステップ(例えば、図5のステップS103に相当)と、ネットワーク上への全リンクの符号化ベクトルを出力する第4のステップ(例えば、図5のステップS104に相当)と、をコンピュータに実行させるためのプログラムを提案している。
【0033】
この発明によれば、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行い、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する。そして、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証し、ネットワーク上への全リンクの符号化ベクトルを出力する。したがって、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができる。
【0034】
(14)本発明は、(13)のプログラムについて、前記送信装置が、乱数を生成する第5のステップ(例えば、図6のステップS201に相当)と、最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する第6のステップ(例えば、図6のステップS202に相当)と、該出力された符号語を前記構成されたネットワークへ送信する第7のステップ(例えば、図6のステップS203に相当)と、をコンピュータに実行させるためのプログラムを提案している。
【0035】
この発明によれば、乱数を生成し、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する。そして、出力された符号語を構成されたネットワークへ送信する。したがって、シンプルな処理で、符号語を導出して送信することができる。
【0036】
(15)本発明は、(13)のプログラムについて、前記受信装置が、前記構成されたネットワークから受信ベクトルを受信する第8のステップ(例えば、図7のステップS301に相当)と、該受信ベクトルを線形変換して符号語を導出する第9のステップ(例えば、図7のステップS302に相当)と、該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する第10のステップ(例えば、図7のステップS303に相当)と、をコンピュータに実行させるためのプログラムを提案している。
【0037】
この発明によれば、構成されたネットワークから受信ベクトルを受信し、受信ベクトルを線形変換して符号語を導出する。そして、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する。したがって、シンプルな処理で、送信情報を復号することができる。
【発明の効果】
【0038】
本発明によれば、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができるという効果がある。
【図面の簡単な説明】
【0039】
【図1】本発明の実施形態に係るネットワークシステムの構成図である。
【図2】本発明の実施形態に係る符号化ベクトル設定装置の構成図である。
【図3】本発明の実施形態に係る送信装置の構成図である。
【図4】本発明の実施形態に係る受信装置の構成図である。
【図5】本発明の実施形態に係る符号化ベクトル設定装置の処理フロー図である。
【図6】本発明の実施形態に係る送信装置の処理フロー図である。
【図7】本発明の実施形態に係る受信装置の処理フロー図である。
【発明を実施するための形態】
【0040】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【0041】
図1から図7を用いて、本発明の実施形態に係るネットワークシステムについて、説明する。
【0042】
<ネットワークシステムの構成>
本実施形態に係るネットワークシステムは、図1に示すように、符号化ベクトル設定装置100と、送信装置200と、受信装置300とから構成されている。本実施形態に係るネットワークシステムは、符号化ベクトル設定装置100が、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号によるネットワークシステムを構築し、送信装置200が送信情報をコセット符号語に変換し、符号化ベクトル設定装置100が構築するネットワークを介して、送信するとともに、受信装置300が符号化ベクトル設定装置100が構築するネットワークを介して、受信したコセット符号語を復号して送信情報を得るものである。
【0043】
<符号化ベクトル設定装置の構成>
図2を用いて、本実施形態に係る符号化ベクトル設定装置の構成について説明する。
【0044】
本実施形態に係る符号化ベクトル設定装置は、図2に示すように、アルゴリズム実行部110と、線形独立性検証部120と、検証部130と、出力部140とから構成されている。
【0045】
アルゴリズム実行部110は、ネットワーク構成を入力とし、ネットワーク上の上流リンクから下流リンク(最下流リンクは受信ノードへ接続される)へと1つずつリンクを辿っていき、当該リンクの保持する符号化ベクトルの設定を行う。
【0046】
線形独立性検証部120は、当該リンクの符号化ベクトルの設定を行うステップ1回毎に、設定した符号化ベクトルが強セキュアなネットワーク符号を構成する条件を満たすか否かの2段のチェックを行う。まず、LIFアルゴリズム内で受信ノードへの情報フローを構成する符号化ベクトルがすべて線形独立か否かをチェックする。すべて線形独立であれば、次のチェック装置へ移行する。
【0047】
検証部130は、最大距離分離符号のパリティ検査行列、当該リンクに設定された符号化ベクトル、および設定済みリンクの符号化ベクトルを用いて、線形独立性のチェックを行う。これらチェックを満たしていれば、1つ下流のリンクの符号化ベクトルの設定へと移る。そうでなければ再度当該リンクに対しての符号化ベクトルの設定を行う。出力部140は、ネットワーク上への全リンクの符号化ベクトルを出力する。
【0048】
<送信装置の構成>
図3を用いて、本実施形態に係る送信装置の構成について説明する。
【0049】
本実施形態に係る送信装置は、図3に示すように、乱数生成部210と、符号化部220と、送信部230とから構成されている。
【0050】
乱数生成部210は、乱数を生成する。符号化部220は、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する。送信部230は、出力された符号語を符号化ベクトル設定装置により構成されたネットワークへ送信する。
【0051】
<受信装置の構成>
図4を用いて、本実施形態に係る受信装置の構成について説明する。
【0052】
本実施形態に係る受信装置は、図4に示すように、受信部310と、符号語導出部320と、シンドローム導出部330とから構成されている。
【0053】
受信部310は、符号化ベクトル設定装置により構成されたネットワークから受信ベクトルを受信する。符号語導出部320は、受信ベクトルを線形変換して符号語を導出する。シンドローム導出部330は、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する。
【0054】
<符号化ベクトル設定装置の処理>
図5を用いて、本実施形態に係る符号化ベクトル設定装置の処理について説明する。
【0055】
まず、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行う(ステップS101)。各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する(ステップS102)。
【0056】
そして、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証し(ステップS103)、ネットワーク上への全リンクの符号化ベクトルを出力する(ステップS104)。
【0057】
<送信装置の処理>
図6を用いて、本実施形態に係る送信装置の処理について説明する。
【0058】
まず、乱数を生成し(ステップS201)、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する(ステップS202)。そして、出力された符号語を構成されたネットワークへ送信する(ステップS203)。
【0059】
<受信装置の処理>
図7を用いて、本実施形態に係る受信装置の処理について説明する。
【0060】
まず、構成されたネットワークから受信ベクトルを受信し(ステップS301)、受信ベクトルを線形変換して符号語を導出する(ステップS302)。そして、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する(ステップS302)。
【0061】
<実施例>
以下、具体的な事項を提示して、本実施形態に係るネットワークシステムの実施例について説明する。
【0062】
<前提条件>
以下、実施例の説明を行う前に、その前提条件について説明する。
【0063】
<ネットワークモデル>
G=(E、V)を遅延のない非巡回有向ネットワークとする。E、Vは、それぞれリンク(edge)、ノードの集合である。R⊂Vを受信ノードの集合、s∈V(s∈R)を送信ノードとする。全てのリンクはFの1要素を1単位時間に送信できる単位容量を有すると仮定する。さらに、Gについて、nmin{maxflow(s、r):r∈R}とする。ここで、maxflow(i,j)(i,j∈V)はiからjへの最大フローを示す。このとき、Gについて、レートnでsからRの全要素へマルチキャストを行うための線形ネットワーク符号化が可能である。
【0064】
<送信モデルおよび盗聴モデル>
ネットワークG上に、レートnでsからRの全要素へマルチキャストを行う線形ネットワーク符号化が施されているとする。すなわち、各リンクe∈Eについて、当該リンク上を流れる情報を表す符号化ベクトルb(e)∈F(Grobal Coding Vector、GCV)が設定されている。ある時刻におけるsからの送信語をn次元ベクトルX=(X,X、・・・、X)∈Fと表す。このとき、リンクe上を流れる情報は、w(e)=b(e)・Xと表される。Tは、ベクトルの転置を表す。したがって,m本のリンクe、・・・、e∈Eが盗聴されたとき、盗聴者は、
【数1】

というm次元ベクトルを入手することとなる。セキュアなネットワーク符号化では、k次元ベクトル(k≦n)で表される秘密の情報S=(S、・・・、S)∈Fを送信ノードにおいてn次元ベクトルで表される送信語(符号語)X∈Fへ符号化し、そのXを送信する。この際、盗聴者が入手した情報WからSに関する情報が情報理論的に漏れないことが目的である。
【0065】
<Weakly μ−Secureの定義(定義1)>
S=(S、・・・、S)とし、個々のS、・・・、Sは、F上で独立で一様だと仮定する。また、m=n−kとする。このとき、線形ネットワーク符号化が施されたネットワークにおいて、E中のm+1本のリンクが盗聴されたとき、以下が成立する。
I(S;W=B・X)=H(S)−H(S|W)
=[rankB−μ]
≦l
ただし、l=0、1、・・・、k−1であり、[a]+=max{a、0}、I(A、B)は、確率変数AとBの相互情報量、H()は、シャノンの情報エントロピーを表す。上記の定義は、m本まで盗聴されても情報理論的にSに関する情報を一切、盗聴者が手に入れられないことを示している。また、m本を超えるリンクが盗聴された場合、Sに関する曖昧さが薄れ、盗聴者は、Sに関して何らかの情報を得る可能性があることが示されている。
【0066】
<Strongly μ−Secureの定義(定義2)>
S=(S、・・・、S)とし、個々のS、・・・、Sは、F上で独立で一様だと仮定する。また、m=n−kとする。m+1本のリンクが盗聴されたとき、Weakly μ−Secureの定義を満たす。このとき、∀{i、・・・、in−rankB}⊂{1、・・・、k}において、以下が成立する。
I(Si1、・・・、Sin−rankB;W=B・X)=H(Si1、・・・、Sin−rankB)−H(Si1、・・・、Sin−rankB|W)=0
但し、l=0、1、・・・、k−1。
上記の定義は、m本を超え、m+k−1=n−1本までのリンクが盗聴されたとしても、秘密の情報のベクトルSの個々の要素のどの要素も確定的には盗聴者の手に渡らない(秘密情報同士がミックスされて曖昧なまま)ことを示している。
【0067】
<最大距離分離符号のコセット符号化を用いた構成の一例>
定義2を満たす(すなわち、定義1も満たす)ネットワーク符号の構成を示す。
【0068】
<ネットワーク符号の構成(符号化ベクトル設定装置の処理)>
数1を[n、n−k]線形最大距離分離符号のパリティチェック行列とする。
【数2】

また、A={a、・・・、a|A|}⊂{1、・・・、k}について、Hの部分行列Hを以下、数2のように定義する。
【数3】

【0069】
LIFアルゴリズムにおけるt∈Rへのn次の情報フローをFとする。また、LIFアルゴリズムの動作において、上流から下流へステップを進めていく際に、更新しながら常に正則行列であるように保つ行列をBFt∈Fn×nと表す。最終ステップにおいて、BFtは、受信ノードtの受け取る受信ベクトルの構成を示す。BFtの正則性の保持は、「情報フローの線形独立性チェック」に相当する。上流から下流へのステップ番号をiと示す。このとき、LIFアルゴリズムにおいて構成されるネットワーク符号をStrongly μ−Secureに保つには、BFtの正則性に加え、l=0、・・・、k−1の個々の値において、
1)取り得る全てのA⊂{1、・・・、k}(ただし、|A|=k−l)
2)取り得るWi、A={e}∪W´(ただし、W´⊂P、|W´|=μ+l−1)
について、
【数4】

を満たすように、符号化ベクトル(Grobal Coding Vector,GCV)b(e)を設定し、BFtを更新する。ここで、e∈Eは、i番目のステップでGCVを設定しょうとしているリンクであり、Pは、i番目のステップまで処理されたリンクの集合である。Cwi、Aは、Wi、Aの要素のGCVを行とした行列である。これは、「最大距離分離符号のパリティ検査行列、当該リンクの符号化ベクトル、設定済みリンクの符号化ベクトルの線形独立性チェック」に相当する。
【0070】
また、この構成では、Strongly μ−Secureな手法を実現するネットワーク符号を構成するには,体Fの位数qは、数4を満たせば十分である。
【0071】
【数5】

【0072】
<復号語の生成方法(送信装置の処理)>
ネットワークのGCVの設定に用いた最大距離分離符号のパリティ検査行列H∈Fk×nによるコセット符号化によって実現される。コセット符号化器の一つの実現手法として、例えば、以下の手法がある。数5が正則となるような行列H∈F(n−k)×kを準備する。
【0073】
【数6】

【0074】
また、乱数生成器にてm=n−k次元乱数ベクトルV=(V、・・・、Vn−k)を生成する。これらを用いて、Sをコセット符号化し、Xの導出が以下の数6のように可能である。
【0075】
【数7】

【0076】
<秘密の情報Sの導出方法(受信装置の処理)>
受信ノードt(t∈R)において受信される受信ベクトルY∈Fは、ネットワーク符号化によってXが線形変換されたものである。ネットワーク符号化によって、設定される線形変換行列をA∈Fn×nとして表すと、Y=A・Xとして表される。このとき、Aは必ず正則である。そのため、符号語導出部において、XはX=A−1・Yより導出される。さらに、Xに対して、Hを用いて最大距離分離符号のシンドロームS=H・Xを導出し、秘密の情報が得られる。単純に、受信ベクトルYから以下の数7のように、直接Sを導出してもよい。
【0077】
【数8】

【0078】
以上、説明したように、本実施形態によれば、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができる。
【0079】
なお、ネットワークシステムの処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをネットワークシステムに読み込ませ、実行することによって本発明のネットワークシステムを実現することができる。ここでいうコンピュータシステムとは、OSや周辺装置等のハードウェアを含む。
【0080】
また、「コンピュータシステム」は、WWW(World Wide Web)システムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク(通信網)や電話回線等の通信回線(通信線)のように情報を伝送する機能を有する媒体のことをいう。
【0081】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル(差分プログラム)であっても良い。
【0082】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【0083】
100;符号化ベクトル設定装置
110;アルゴリズム実行部
120;線形独立性検証部
130;検証部
140;出力部
200;送信装置
210;乱数生成部
220;符号化部
230;送信部
300;受信装置
310;受信部
320;符号語導出部
330;シンドローム導出部

【特許請求の範囲】
【請求項1】
送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムであって、
前記符号化ベクトル設定装置が、
ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行うアルゴリズム実行手段と、
各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する線形独立性検証手段と、
各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する検証手段と、
ネットワーク上への全リンクの符号化ベクトルを出力する出力手段と、
を備えたことを特徴とするネットワークシステム。
【請求項2】
前記アルゴリズム実行手段のアルゴリズムが、LIF(Linear Information Flow)アルゴリズムであることを特徴とする請求項1に記載のネットワークシステム。
【請求項3】
前記最大距離分離符号が、リードソロモン符号をはじめとして既存の符号を利用可能なことを特徴とする請求項1または請求項2に記載のネットワークシステム。
【請求項4】
前記送信装置が、
乱数を生成する乱数生成手段と、
最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する符号化手段と、
該出力された符号語を前記符号化ベクトル設定装置により構成されたネットワークへ送信する送信手段と、
を備えたことを特徴とする請求項1から請求項3に記載のネットワークシステム。
【請求項5】
前記最大距離分離符号が、リードソロモン符号をはじめとして既存の符号を利用可能なことを特徴とする請求項4に記載のネットワークシステム。
【請求項6】
前記符号化手段が、送信情報のコセット符号化を行い符号語を出力することを特徴とする請求項5に記載のネットワークシステム。
【請求項7】
前記受信装置が、
前記請求項1から請求項3に記載の符号化ベクトル設定装置により構成されたネットワークから受信ベクトルを受信する受信手段と、
該受信ベクトルを線形変換して符号語を導出する符号語導出手段と、
該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号するシンドローム導出手段と、
を備えたことを特徴とする請求項1から請求項3に記載のネットワークシステム。
【請求項8】
前記符号語導出手段が、コセット符号化の符号語を導出することを特徴とする請求項7に記載のネットワークシステム。
【請求項9】
前記最大距離分離符号が、リードソロモン符号をはじめとして既存の符号を利用可能なことを特徴とする請求項8に記載のネットワークシステム。
【請求項10】
送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムにおけるネットワーク構成方法であって、
前記符号化ベクトル設定装置が、
ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行う第1のステップと、
各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する第2のステップと、
各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する第3のステップと、
ネットワーク上への全リンクの符号化ベクトルを出力する第4のステップと、
を備えたことを特徴とするネットワーク構成方法。
【請求項11】
前記送信装置が、
乱数を生成する第5のステップと、
最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する第6のステップと、
該出力された符号語を前記構成されたネットワークへ送信する第7のステップと、
を備えたことを特徴とする請求項10に記載のネットワーク構成方法。
【請求項12】
前記受信装置が、
前記構成されたネットワークから受信ベクトルを受信する第8のステップと、
該受信ベクトルを線形変換して符号語を導出する第9のステップと、
該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する第10のステップと、
を備えたことを特徴とする請求項11に記載のネットワーク構成方法。
【請求項13】
送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムにおけるネットワーク構成方法をコンピュータに実行させるためのプログラムであって、
前記符号化ベクトル設定装置が、
ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと1つずつ符号化ベクトルの設定を行う第1のステップと、
各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する第2のステップと、
各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する第3のステップと、
ネットワーク上への全リンクの符号化ベクトルを出力する第4のステップと、
をコンピュータに実行させるためのプログラム。
【請求項14】
前記送信装置が、
乱数を生成する第5のステップと、
最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する第6のステップと、
該出力された符号語を前記構成されたネットワークへ送信する第7のステップと、
をコンピュータに実行させるための請求項13に記載のプログラム。
【請求項15】
前記受信装置が、
前記構成されたネットワークから受信ベクトルを受信する第8のステップと、
該受信ベクトルを線形変換して符号語を導出する第9のステップと、
該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する第10のステップと、
をコンピュータに実行させるための請求項14に記載のプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate