(57)【要約】【課題】強セキュアなネットワーク符号を用いたシンプルなネットワークを構成するとともに、高速な処理を実現する。【解決手段】ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行い、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する。そして、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証し、ネットワーク上への全リンクの符号化ベクトルを出力する。【選択図】図４
2012185245.tif 000002
【特許請求の範囲】
【請求項１】
送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムであって、
前記符号化ベクトル設定装置が、
ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行うアルゴリズム実行手段と、
各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する線形独立性検証手段と、
各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する検証手段と、
ネットワーク上への全リンクの符号化ベクトルを出力する出力手段と、
を備えたことを特徴とするネットワークシステム。
【請求項２】
前記アルゴリズム実行手段のアルゴリズムが、ＬＩＦ（Ｌｉｎｅａｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｌｏｗ）アルゴリズムであることを特徴とする請求項１に記載のネットワークシステム。
【請求項３】
前記最大距離分離符号が、リードソロモン符号をはじめとして既存の符号を利用可能なことを特徴とする請求項１または請求項２に記載のネットワークシステム。
【請求項４】
前記送信装置が、
乱数を生成する乱数生成手段と、
最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する符号化手段と、
該出力された符号語を前記符号化ベクトル設定装置により構成されたネットワークへ送信する送信手段と、
を備えたことを特徴とする請求項１から請求項３に記載のネットワークシステム。
【請求項５】
前記最大距離分離符号が、リードソロモン符号をはじめとして既存の符号を利用可能なことを特徴とする請求項４に記載のネットワークシステム。
【請求項６】
前記符号化手段が、送信情報のコセット符号化を行い符号語を出力することを特徴とする請求項５に記載のネットワークシステム。
【請求項７】
前記受信装置が、
前記請求項１から請求項３に記載の符号化ベクトル設定装置により構成されたネットワークから受信ベクトルを受信する受信手段と、
該受信ベクトルを線形変換して符号語を導出する符号語導出手段と、
該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号するシンドローム導出手段と、
を備えたことを特徴とする請求項１から請求項３に記載のネットワークシステム。
【請求項８】
前記符号語導出手段が、コセット符号化の符号語を導出することを特徴とする請求項７に記載のネットワークシステム。
【請求項９】
前記最大距離分離符号が、リードソロモン符号をはじめとして既存の符号を利用可能なことを特徴とする請求項８に記載のネットワークシステム。
【請求項１０】
送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムにおけるネットワーク構成方法であって、
前記符号化ベクトル設定装置が、
ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行う第１のステップと、
各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する第２のステップと、
各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する第３のステップと、
ネットワーク上への全リンクの符号化ベクトルを出力する第４のステップと、
を備えたことを特徴とするネットワーク構成方法。
【請求項１１】
前記送信装置が、
乱数を生成する第５のステップと、
最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する第６のステップと、
該出力された符号語を前記構成されたネットワークへ送信する第７のステップと、
を備えたことを特徴とする請求項１０に記載のネットワーク構成方法。
【請求項１２】
前記受信装置が、
前記構成されたネットワークから受信ベクトルを受信する第８のステップと、
該受信ベクトルを線形変換して符号語を導出する第９のステップと、
該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する第１０のステップと、
を備えたことを特徴とする請求項１１に記載のネットワーク構成方法。
【請求項１３】
送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムにおけるネットワーク構成方法をコンピュータに実行させるためのプログラムであって、
前記符号化ベクトル設定装置が、
ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行う第１のステップと、
各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する第２のステップと、
各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する第３のステップと、
ネットワーク上への全リンクの符号化ベクトルを出力する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１４】
前記送信装置が、
乱数を生成する第５のステップと、
最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する第６のステップと、
該出力された符号語を前記構成されたネットワークへ送信する第７のステップと、
をコンピュータに実行させるための請求項１３に記載のプログラム。
【請求項１５】
前記受信装置が、
前記構成されたネットワークから受信ベクトルを受信する第８のステップと、
該受信ベクトルを線形変換して符号語を導出する第９のステップと、
該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する第１０のステップと、
をコンピュータに実行させるための請求項１４に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、強セキュアなネットワーク符号を用いたネットワークシステム、ネットワーク構成方法およびプログラムに関する。
【背景技術】
【０００２】
近年、ネットワーク上のノード（たとえばルータ・スイッチ）に従来のコピー・転送機能ではなく、数学的演算機能を持たせることによって、伝送レート・スループットの向上や消費エネルギーの低減を実現するネットワーク符号化と呼ばれる技術が注目を浴びている（例えば、非特許文献１参照。）。
【０００３】
ところで、ネットワーク上では、「伝送リンクの盗聴」攻撃が懸念される。このため、盗聴対策を施したネットワーク符号の構成法がいくつか提案されている（例えば、非特許文献２から非特許文献４参照。）。これらの手法は、ネットワークを構成するリンクのうち、ある一定個数個まで盗聴されても、送信情報が情報理論的に漏えいしない安全性が示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｒ. Ａｈｌｓｗｅｄｅ, Ｎ. Ｃａｉ, Ｓ.−Ｙ. Ｒ. Ｌｉ, ａｎｄ Ｒ. Ｗ. Ｙｅｕｎｇ, “Ｎｅｔｗｏｒｋ ｉｎｆｏｒｍａｔｉｏｎ ｆｌｏｗ,” ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ, ｖｏｌ. ４６, ｎｏ. ４, ｐｐ.１２０４-１２１６, ２０００.
【非特許文献２】Ｎ. Ｃａｉ ａｎｄ Ｒ. Ｗ. Ｙｅｕｎｇ, “Ｓｅｃｕｒｅ ｎｅｔｗｏｒｋ ｃｏｄｉｎｇ,” ｉｎ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ （ＩＳＩＴ） ２００２, ｐｐ.３２３, ２００２.
【非特許文献３】Ｎ. Ｃａｉ ａｎｄ Ｒ. Ｗ. Ｙｅｕｎｇ, “Ｓｅｃｕｒｅ ｎｅｔｗｏｒｋ Ｃｏｄｉｎｇ ｏｎ ａ ｗｉｒｅｔａｐ ｎｅｔｗｏｒｋ,” ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ, ｖｏｌ. ５７, ｎｏ. １, ｐｐ.４２４-４３５，２０１１.
【非特許文献４】Ｓ. Ｙ. Ｅ. Ｒｏｕａｙｈｅｂ ａｎｄ Ｅ. Ｓｏｌｊａｎｉｎ, “Ｏｎ ｗｉｒｅｔａｐ ｎｅｔｗｏｒｋｓ ＩＩ,” ｉｎ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ （ＩＳＩＴ） ２００７, ｐｐ.５５１-５５５, ２００７.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記に記載の技術では、一定個数を超える数のリンクを盗聴されると、送信情報の一部が確定的に漏えいする可能性があることが指摘されている。
【０００６】
そこで、本発明は、上述の課題に鑑みてなされたものであり、強セキュアなネットワーク符号を用いたシンプルなネットワークを構成するとともに、高速な処理を実現するネットワークシステム、ネットワーク構成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【０００８】
（１）本発明は、送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムであって、前記符号化ベクトル設定装置が、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行うアルゴリズム実行手段（例えば、図２のアルゴリズム実行部１１０に相当）と、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する線形独立性検証手段（例えば、図２の線形独立性検証部１２０に相当）と、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する検証手段（例えば、図２の検証部１３０に相当）と、ネットワーク上への全リンクの符号化ベクトルを出力する出力手段（例えば、図２の出力部１４０に相当）と、を備えたことを特徴とするネットワークシステムを提案している。
【０００９】
この発明によれば、アルゴリズム実行手段は、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行う。線形独立性検証手段は、アルゴリズム実行手段の各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する。検証手段は、アルゴリズム実行手段の各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する。出力手段は、ネットワーク上への全リンクの符号化ベクトルを出力する。したがって、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができる。
【００１０】
（２）本発明は、（１）のネットワークシステムについて、前記アルゴリズム実行手段のアルゴリズムが、ＬＩＦ（Ｌｉｎｅａｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｌｏｗ）アルゴリズムであることを特徴とするネットワークシステムを提案している。
【００１１】
この発明によれば、アルゴリズム実行手段のアルゴリズムが、ＬＩＦ（Ｌｉｎｅａｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｌｏｗ）アルゴリズムである。したがって、シンプルなアルゴリズムにより、符号化ベクトル設定装置を構築することができる。
【００１２】
（３）本発明は、（１）または（２）のネットワークシステムについて、前記最大距離分離符号が、リードソロモン符号をはじめとして既存の符号を利用可能であることを特徴とするネットワークシステムを提案している。
【００１３】
この発明によれば、最大距離分離符号として、たとえばリードソロモン符号が利用できる。したがって、シンプルな構成が可能である。また、既存の最大距離分離符号の符号化および復号手法の周辺技術を利用することが可能であるため、高速な手法が利用できる。
【００１４】
（４）本発明は、（１）から（３）のネットワークシステムについて、前記送信装置が、乱数を生成する乱数生成手段（例えば、図３の乱数生成部２１０に相当）と、最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する符号化手段（例えば、図３の符号化部２２０に相当）と、該出力された符号語を前記符号化ベクトル設定装置により構成されたネットワークへ送信する送信手段（例えば、図３の送信部２３０に相当）と、を備えたことを特徴とするネットワークシステムを提案している。
【００１５】
この発明によれば、乱数生成手段は、乱数を生成する。符号化手段は、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する。送信手段は、出力された符号語を符号化ベクトル設定装置により構成されたネットワークへ送信する。したがって、シンプルな構成で、シンドローム符号語を導出して送信することができる。
【００１６】
（５）本発明は、（４）のネットワークシステムについて、最大距離分離符号を利用することを特徴とするネットワークシステムを提案している。
【００１７】
この発明によれば、最大距離分離符号として、たとえばリードソロモン符号が利用できる。したがって、シンプルな構成が可能である。また、既存の最大距離分離符号の符号化および復号手法の周辺技術を利用することが可能であるため、高速な手法が利用できる。
【００１８】
（６）本発明は、（５）のネットワークシステムについて、前記符号化手段が、送信情報のコセット符号化を行い符号語を出力することを特徴とするネットワークシステムを提案している。
【００１９】
この発明によれば、符号化手段が、送信情報のコセット符号化を行い符号語を出力する。したがって、シンプルな構成で、符号語を導出することができる。
【００２０】
（７）本発明は、（１）から（３）のネットワークシステムについて、前記受信装置が、（１）から（３）に記載の符号化ベクトル設定装置により構成されたネットワークから受信ベクトルを受信する受信手段（例えば、図４の受信部３１０に相当）と、該受信ベクトルを線形変換して符号語を導出する符号語導出手段（例えば、図４の符号語導出部３２０に相当）と、該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号するシンドローム導出手段（例えば、図４のシンドローム導出部３３０に相当）と、を備えたことを特徴とするネットワークシステムを提案している。
【００２１】
この発明によれば、受信手段は、構成されたネットワークから受信ベクトルを受信する。符号語導出手段は、受信ベクトルを線形変換して符号語を導出する。シンドローム導出手段は、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する。したがって、シンプルな構成で、送信情報を復号することができる。
【００２２】
（８）本発明は、（７）のネットワークシステムについて、前記符号語導出手段が、コセット符号化の符号語を導出することを特徴とするネットワークシステムを提案している。
【００２３】
この発明によれば、符号語導出手段が、コセット符号化の符号語を導出する。したがって、シンプルな構成で、符号語を導出することができる。
【００２４】
（９）本発明は、（８）のネットワークシステムについて、最大距離分離符号を利用することを特徴とするネットワークシステムを提案している。
【００２５】
この発明によれば、最大距離分離符号として、たとえばリードソロモン符号が利用できる。したがって、シンプルな構成が可能である。また、既存の最大距離分離符号の符号化および復号手法の周辺技術を利用することが可能であるため、高速な手法が利用できる。
【００２６】
（１０）本発明は、送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムにおけるネットワーク構成方法であって、前記符号化ベクトル設定装置が、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行う第１のステップ（例えば、図５のステップＳ１０１に相当）と、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する第２のステップ（例えば、図５のステップＳ１０２に相当）と、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する第３のステップ（例えば、図５のステップＳ１０３に相当）と、ネットワーク上への全リンクの符号化ベクトルを出力する第４のステップ（例えば、図５のステップＳ１０４に相当）と、を備えたことを特徴とするネットワーク構成方法を提案している。
【００２７】
この発明によれば、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行い、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する。そして、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証し、ネットワーク上への全リンクの符号化ベクトルを出力する。したがって、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができる。
【００２８】
（１１）本発明は、（１０）のネットワーク構成方法について、前記送信装置が、乱数を生成する第５のステップ（例えば、図６のステップＳ２０１に相当）と、最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する第６のステップ（例えば、図６のステップＳ２０２に相当）と、該出力された符号語を前記構成されたネットワークへ送信する第７のステップ（例えば、図６のステップＳ２０３に相当）と、を備えたことを特徴とするネットワーク構成方法を提案している。
【００２９】
この発明によれば、乱数を生成し、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する。そして、出力された符号語を構成されたネットワークへ送信する。したがって、シンプルな処理で、符号語を導出して送信することができる。
【００３０】
（１２）本発明は、（１１）のネットワーク構成方法について、前記受信装置が、前記構成されたネットワークから受信ベクトルを受信する第８のステップ（例えば、図７のステップＳ３０１に相当）と、該受信ベクトルを線形変換して符号語を導出する第９のステップ（例えば、図７のステップＳ３０２に相当）と、該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する第１０のステップ（例えば、図７のステップＳ３０３に相当）と、を備えたことを特徴とするネットワーク構成方法を提案している。
【００３１】
この発明によれば、構成されたネットワークから受信ベクトルを受信し、受信ベクトルを線形変換して符号語を導出する。そして、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する。したがって、シンプルな処理で、送信情報を復号することができる。
【００３２】
（１３）本発明は、送信装置と符号化ベクトル設定装置と受信装置とからなるネットワークシステムにおけるネットワーク構成方法をコンピュータに実行させるためのプログラムであって、前記符号化ベクトル設定装置が、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行う第１のステップ（例えば、図５のステップＳ１０１に相当）と、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する第２のステップ（例えば、図５のステップＳ１０２に相当）と、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証する第３のステップ（例えば、図５のステップＳ１０３に相当）と、ネットワーク上への全リンクの符号化ベクトルを出力する第４のステップ（例えば、図５のステップＳ１０４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３３】
この発明によれば、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行い、各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する。そして、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証し、ネットワーク上への全リンクの符号化ベクトルを出力する。したがって、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができる。
【００３４】
（１４）本発明は、（１３）のプログラムについて、前記送信装置が、乱数を生成する第５のステップ（例えば、図６のステップＳ２０１に相当）と、最大距離分離符号のパリティ検査行列と該生成された乱数を元に送信情報の符号語を出力する第６のステップ（例えば、図６のステップＳ２０２に相当）と、該出力された符号語を前記構成されたネットワークへ送信する第７のステップ（例えば、図６のステップＳ２０３に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３５】
この発明によれば、乱数を生成し、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する。そして、出力された符号語を構成されたネットワークへ送信する。したがって、シンプルな処理で、符号語を導出して送信することができる。
【００３６】
（１５）本発明は、（１３）のプログラムについて、前記受信装置が、前記構成されたネットワークから受信ベクトルを受信する第８のステップ（例えば、図７のステップＳ３０１に相当）と、該受信ベクトルを線形変換して符号語を導出する第９のステップ（例えば、図７のステップＳ３０２に相当）と、該導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する第１０のステップ（例えば、図７のステップＳ３０３に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３７】
この発明によれば、構成されたネットワークから受信ベクトルを受信し、受信ベクトルを線形変換して符号語を導出する。そして、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する。したがって、シンプルな処理で、送信情報を復号することができる。
【発明の効果】
【００３８】
本発明によれば、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができるという効果がある。
【図面の簡単な説明】
【００３９】
【図１】本発明の実施形態に係るネットワークシステムの構成図である。
【図２】本発明の実施形態に係る符号化ベクトル設定装置の構成図である。
【図３】本発明の実施形態に係る送信装置の構成図である。
【図４】本発明の実施形態に係る受信装置の構成図である。
【図５】本発明の実施形態に係る符号化ベクトル設定装置の処理フロー図である。
【図６】本発明の実施形態に係る送信装置の処理フロー図である。
【図７】本発明の実施形態に係る受信装置の処理フロー図である。
【発明を実施するための形態】
【００４０】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００４１】
図１から図７を用いて、本発明の実施形態に係るネットワークシステムについて、説明する。
【００４２】
＜ネットワークシステムの構成＞
本実施形態に係るネットワークシステムは、図１に示すように、符号化ベクトル設定装置１００と、送信装置２００と、受信装置３００とから構成されている。本実施形態に係るネットワークシステムは、符号化ベクトル設定装置１００が、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号によるネットワークシステムを構築し、送信装置２００が送信情報をコセット符号語に変換し、符号化ベクトル設定装置１００が構築するネットワークを介して、送信するとともに、受信装置３００が符号化ベクトル設定装置１００が構築するネットワークを介して、受信したコセット符号語を復号して送信情報を得るものである。
【００４３】
＜符号化ベクトル設定装置の構成＞
図２を用いて、本実施形態に係る符号化ベクトル設定装置の構成について説明する。
【００４４】
本実施形態に係る符号化ベクトル設定装置は、図２に示すように、アルゴリズム実行部１１０と、線形独立性検証部１２０と、検証部１３０と、出力部１４０とから構成されている。
【００４５】
アルゴリズム実行部１１０は、ネットワーク構成を入力とし、ネットワーク上の上流リンクから下流リンク（最下流リンクは受信ノードへ接続される）へと１つずつリンクを辿っていき、当該リンクの保持する符号化ベクトルの設定を行う。
【００４６】
線形独立性検証部１２０は、当該リンクの符号化ベクトルの設定を行うステップ１回毎に、設定した符号化ベクトルが強セキュアなネットワーク符号を構成する条件を満たすか否かの２段のチェックを行う。まず、ＬＩＦアルゴリズム内で受信ノードへの情報フローを構成する符号化ベクトルがすべて線形独立か否かをチェックする。すべて線形独立であれば、次のチェック装置へ移行する。
【００４７】
検証部１３０は、最大距離分離符号のパリティ検査行列、当該リンクに設定された符号化ベクトル、および設定済みリンクの符号化ベクトルを用いて、線形独立性のチェックを行う。これらチェックを満たしていれば、１つ下流のリンクの符号化ベクトルの設定へと移る。そうでなければ再度当該リンクに対しての符号化ベクトルの設定を行う。出力部１４０は、ネットワーク上への全リンクの符号化ベクトルを出力する。
【００４８】
＜送信装置の構成＞
図３を用いて、本実施形態に係る送信装置の構成について説明する。
【００４９】
本実施形態に係る送信装置は、図３に示すように、乱数生成部２１０と、符号化部２２０と、送信部２３０とから構成されている。
【００５０】
乱数生成部２１０は、乱数を生成する。符号化部２２０は、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する。送信部２３０は、出力された符号語を符号化ベクトル設定装置により構成されたネットワークへ送信する。
【００５１】
＜受信装置の構成＞
図４を用いて、本実施形態に係る受信装置の構成について説明する。
【００５２】
本実施形態に係る受信装置は、図４に示すように、受信部３１０と、符号語導出部３２０と、シンドローム導出部３３０とから構成されている。
【００５３】
受信部３１０は、符号化ベクトル設定装置により構成されたネットワークから受信ベクトルを受信する。符号語導出部３２０は、受信ベクトルを線形変換して符号語を導出する。シンドローム導出部３３０は、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する。
【００５４】
＜符号化ベクトル設定装置の処理＞
図５を用いて、本実施形態に係る符号化ベクトル設定装置の処理について説明する。
【００５５】
まず、ネットワーク構成を入力し、ネットワーク上の上流リンクから下流リンクへと１つずつ符号化ベクトルの設定を行う（ステップＳ１０１）。各ステップ毎に設定した符号化ベクトルが前ステップまでに構成した符号化ベクトルと線形独立か否かを検証する（ステップＳ１０２）。
【００５６】
そして、各ステップ毎に設定した符号化ベクトルが最大距離分離符号のパリティ検査行列と前ステップまでに構成した符号化ベクトルとが線形独立か否かを検証し（ステップＳ１０３）、ネットワーク上への全リンクの符号化ベクトルを出力する（ステップＳ１０４）。
【００５７】
＜送信装置の処理＞
図６を用いて、本実施形態に係る送信装置の処理について説明する。
【００５８】
まず、乱数を生成し（ステップＳ２０１）、最大距離分離符号のパリティ検査行列と生成された乱数を元に送信情報の符号語を出力する（ステップＳ２０２）。そして、出力された符号語を構成されたネットワークへ送信する（ステップＳ２０３）。
【００５９】
＜受信装置の処理＞
図７を用いて、本実施形態に係る受信装置の処理について説明する。
【００６０】
まず、構成されたネットワークから受信ベクトルを受信し（ステップＳ３０１）、受信ベクトルを線形変換して符号語を導出する（ステップＳ３０２）。そして、導出された符号語を最大距離分離符号のパリティ検査行列と乗じて送信情報を復号する（ステップＳ３０２）。
【００６１】
＜実施例＞
以下、具体的な事項を提示して、本実施形態に係るネットワークシステムの実施例について説明する。
【００６２】
＜前提条件＞
以下、実施例の説明を行う前に、その前提条件について説明する。
【００６３】
＜ネットワークモデル＞
Ｇ＝（Ｅ、Ｖ）を遅延のない非巡回有向ネットワークとする。Ｅ、Ｖは、それぞれリンク（ｅｄｇｅ）、ノードの集合である。Ｒ⊂Ｖを受信ノードの集合、ｓ∈Ｖ（ｓ∈Ｒ）を送信ノードとする。全てのリンクはＦｑの１要素を１単位時間に送信できる単位容量を有すると仮定する。さらに、Ｇについて、ｎ≦ｍｉｎ｛ｍａｘｆｌｏｗ（ｓ、ｒ）：ｒ∈Ｒ｝とする。ここで、ｍａｘｆｌｏｗ（ｉ,ｊ）（i,ｊ∈Ｖ）はｉからｊへの最大フローを示す。このとき、Ｇについて、レートｎでｓからＲの全要素へマルチキャストを行うための線形ネットワーク符号化が可能である。
【００６４】
＜送信モデルおよび盗聴モデル＞
ネットワークＧ上に、レートｎでｓからＲの全要素へマルチキャストを行う線形ネットワーク符号化が施されているとする。すなわち、各リンクｅ∈Ｅについて、当該リンク上を流れる情報を表す符号化ベクトルｂ（ｅ）∈Ｆｎｑ（Ｇｒｏｂａｌ  Ｃｏｄｉｎｇ  Ｖｅｃｔｏｒ、ＧＣＶ）が設定されている。ある時刻におけるｓからの送信語をｎ次元ベクトルＸ＝（Ｘ１，Ｘ２、・・・、Ｘｎ）∈Ｆｎｑと表す。このとき、リンクｅ上を流れる情報は、ｗ（ｅ）＝ｂ（ｅ）・ＸＴと表される。Ｔは、ベクトルの転置を表す。したがって，ｍ本のリンクｅ１、・・・、ｅｍ∈Ｅが盗聴されたとき、盗聴者は、
【数１】
2012185245.tif 000003
というｍ次元ベクトルを入手することとなる。セキュアなネットワーク符号化では、ｋ次元ベクトル（ｋ≦ｎ）で表される秘密の情報Ｓ＝（Ｓ１、・・・、Ｓｋ）∈Ｆｎｑを送信ノードにおいてｎ次元ベクトルで表される送信語（符号語）Ｘ∈Ｆｎｑへ符号化し、そのＸを送信する。この際、盗聴者が入手した情報ＷからＳに関する情報が情報理論的に漏れないことが目的である。
【００６５】
＜Ｗｅａｋｌｙ  μ−Ｓｅｃｕｒｅの定義（定義１）＞
Ｓ＝（Ｓ１、・・・、Ｓｋ）とし、個々のＳ１、・・・、Ｓｋは、Ｆｎｑ上で独立で一様だと仮定する。また、ｍ＝ｎ−ｋとする。このとき、線形ネットワーク符号化が施されたネットワークにおいて、Ｅ中のｍ＋１本のリンクが盗聴されたとき、以下が成立する。
Ｉ（Ｓ；Ｗ＝Ｂ・ＸＴ）＝Ｈ（Ｓ）−Ｈ（Ｓ｜Ｗ）
＝［ｒａｎｋＢ−μ］＋
≦ｌ
ただし、ｌ＝０、１、・・・、ｋ−１であり、［ａ］＋＝ｍａｘ｛ａ、０｝、Ｉ（Ａ、Ｂ）は、確率変数ＡとＢの相互情報量、Ｈ（）は、シャノンの情報エントロピーを表す。上記の定義は、ｍ本まで盗聴されても情報理論的にＳに関する情報を一切、盗聴者が手に入れられないことを示している。また、ｍ本を超えるリンクが盗聴された場合、Ｓに関する曖昧さが薄れ、盗聴者は、Ｓに関して何らかの情報を得る可能性があることが示されている。
【００６６】
＜Ｓｔｒｏｎｇｌｙ  μ−Ｓｅｃｕｒｅの定義（定義２）＞
Ｓ＝（Ｓ１、・・・、Ｓｋ）とし、個々のＳ１、・・・、Ｓｋは、Ｆｎｑ上で独立で一様だと仮定する。また、ｍ＝ｎ−ｋとする。ｍ＋１本のリンクが盗聴されたとき、Ｗｅａｋｌｙ  μ−Ｓｅｃｕｒｅの定義を満たす。このとき、∀｛ｉ１、・・・、ｉｎ−ｒａｎｋＢ｝⊂｛１、・・・、ｋ｝において、以下が成立する。
Ｉ（Ｓｉ１、・・・、Ｓｉｎ−ｒａｎｋＢ；Ｗ＝Ｂ・ＸＴ）＝Ｈ（Ｓｉ１、・・・、Ｓｉｎ−ｒａｎｋＢ）−Ｈ（Ｓｉ１、・・・、Ｓｉｎ−ｒａｎｋＢ｜Ｗ）＝０
但し、ｌ＝０、１、・・・、ｋ−１。
上記の定義は、ｍ本を超え、ｍ＋ｋ−１＝ｎ−１本までのリンクが盗聴されたとしても、秘密の情報のベクトルＳの個々の要素のどの要素も確定的には盗聴者の手に渡らない（秘密情報同士がミックスされて曖昧なまま）ことを示している。
【００６７】
＜最大距離分離符号のコセット符号化を用いた構成の一例＞
定義２を満たす（すなわち、定義１も満たす）ネットワーク符号の構成を示す。
【００６８】
＜ネットワーク符号の構成（符号化ベクトル設定装置の処理）＞
数１を［ｎ、ｎ−ｋ］線形最大距離分離符号のパリティチェック行列とする。
【数２】
2012185245.tif 000004
また、Ａ＝｛ａ１、・・・、ａ｜Ａ｜｝⊂｛１、・・・、ｋ｝について、Ｈの部分行列ＨＡを以下、数２のように定義する。
【数３】
2012185245.tif 000005
【００６９】
ＬＩＦアルゴリズムにおけるｔ∈Ｒへのｎ次の情報フローをＦｔとする。また、ＬＩＦアルゴリズムの動作において、上流から下流へステップを進めていく際に、更新しながら常に正則行列であるように保つ行列をＢＦｔ∈Ｆｎ×ｎｑと表す。最終ステップにおいて、ＢＦｔは、受信ノードｔの受け取る受信ベクトルの構成を示す。ＢＦｔの正則性の保持は、「情報フローの線形独立性チェック」に相当する。上流から下流へのステップ番号をｉと示す。このとき、ＬＩＦアルゴリズムにおいて構成されるネットワーク符号をＳｔｒｏｎｇｌｙ  μ−Ｓｅｃｕｒｅに保つには、ＢＦｔの正則性に加え、ｌ＝０、・・・、ｋ−１の個々の値において、
１）取り得る全てのＡ⊂｛１、・・・、ｋ｝（ただし、｜Ａ｜＝ｋ−ｌ）
２）取り得るＷｉ、Ａ＝｛ｅｉ｝∪Ｗ´Ａ（ただし、Ｗ´Ａ⊂Ｐｉ、｜Ｗ´Ａ｜＝μ＋ｌ−１）
について、
【数４】
2012185245.tif 000006
を満たすように、符号化ベクトル（Ｇｒｏｂａｌ  Ｃｏｄｉｎｇ  Ｖｅｃｔｏｒ，ＧＣＶ）ｂ（ｅｉ）を設定し、ＢＦｔを更新する。ここで、ｅｉ∈Ｅは、ｉ番目のステップでＧＣＶを設定しょうとしているリンクであり、Ｐｉは、ｉ番目のステップまで処理されたリンクの集合である。Ｃｗｉ、Ａは、Ｗｉ、Ａの要素のＧＣＶを行とした行列である。これは、「最大距離分離符号のパリティ検査行列、当該リンクの符号化ベクトル、設定済みリンクの符号化ベクトルの線形独立性チェック」に相当する。
【００７０】
また、この構成では、Ｓｔｒｏｎｇｌｙ  μ−Ｓｅｃｕｒｅな手法を実現するネットワーク符号を構成するには，体Ｆｑの位数ｑは、数４を満たせば十分である。
【００７１】
【数５】
2012185245.tif 000007
【００７２】
＜復号語の生成方法（送信装置の処理）＞
ネットワークのＧＣＶの設定に用いた最大距離分離符号のパリティ検査行列Ｈ∈Ｆｋ×ｎｑによるコセット符号化によって実現される。コセット符号化器の一つの実現手法として、例えば、以下の手法がある。数５が正則となるような行列Ｈ∈Ｆ（ｎ−ｋ）×ｋｑを準備する。
【００７３】
【数６】
2012185245.tif 000008
【００７４】
また、乱数生成器にてｍ＝ｎ−ｋ次元乱数ベクトルＶ＝（Ｖ１、・・・、Ｖｎ−ｋ）を生成する。これらを用いて、Ｓをコセット符号化し、Ｘの導出が以下の数６のように可能である。
【００７５】
【数７】
2012185245.tif 000009
【００７６】
＜秘密の情報Ｓの導出方法（受信装置の処理）＞
受信ノードｔ（ｔ∈Ｒ）において受信される受信ベクトルＹ∈Ｆｎｑは、ネットワーク符号化によってＸが線形変換されたものである。ネットワーク符号化によって、設定される線形変換行列をＡｔ∈Ｆｎ×ｎｑとして表すと、ＹＴ＝Ａｔ・ＸＴとして表される。このとき、Ａｔは必ず正則である。そのため、符号語導出部において、ＸはＸ＝Ａｔ−１・ＹＴより導出される。さらに、Ｘに対して、Ｈを用いて最大距離分離符号のシンドロームＳＴ＝Ｈ・Ｘｔを導出し、秘密の情報が得られる。単純に、受信ベクトルＹから以下の数７のように、直接Ｓを導出してもよい。
【００７７】
【数８】
2012185245.tif 000010
【００７８】
以上、説明したように、本実施形態によれば、一定個数のリンクが盗聴された場合は送信情報が情報理論的に漏えいせず、かつ一定個数以上のリンクが盗聴されても送信情報の一部が確定的に漏えいすることを回避可能な「強セキュア」なネットワーク符号を構成できるため、強セキュアでシンプルなネットワークを構築することができる。
【００７９】
なお、ネットワークシステムの処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをネットワークシステムに読み込ませ、実行することによって本発明のネットワークシステムを実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００８０】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００８１】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００８２】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００８３】
１００；符号化ベクトル設定装置
１１０；アルゴリズム実行部
１２０；線形独立性検証部
１３０；検証部
１４０；出力部
２００；送信装置
２１０；乱数生成部
２２０；符号化部
２３０；送信部
３００；受信装置
３１０；受信部
３２０；符号語導出部
３３０；シンドローム導出部
【図１】
2012185245.tif 000011
【図２】
2012185245.tif 000012
【図３】
2012185245.tif 000013
【図４】
2012185245.tif 000014
【図５】
2012185245.tif 000015
【図６】
2012185245.tif 000016
【図７】
2012185245.tif 000017