(57)【要約】【課題】ネットワーク上で攻撃者が挿入してくる誤りパケットの最大数を予め想定することなく、ネットワークの利用効率を向上でき、かつ、復号の失敗確率を小さくすること。【解決手段】情報伝送システム１は、情報を符号化する符号化装置１０と、符号化装置１０にネットワーク１５０を介して接続された復号装置２０と、を備える。符号化装置１０は、行列で表される情報を符号化し、予め定められた行列で構成される共有鍵と乗算して、この乗算結果を送信する。復号装置２０は、ネットワーク１５０から受信した乗算結果を、上述の共有鍵を構成する行列の逆行列と乗算し、この乗算結果を用いてＲＲＥ形行列を生成して、このＲＲＥ形行列に予め定められた部分行列が含まれているか否かにより、上述の復号を復号できるか否かを判定する。【選択図】図１
2014171020.tif 000002
【特許請求の範囲】
【請求項１】
情報を符号化する符号化装置と、当該符号化装置にネットワークを介して接続された復号装置と、を備える情報伝送システムであって、
前記符号化装置は、
行列で表される情報を符号化する符号化手段と、
前記符号化手段により符号化された情報と、予め定められた行列で構成される共有鍵と、を乗算する送信側乗算手段と、
前記送信側乗算手段による乗算結果を送信する送信手段と、
前記復号装置から再送要求があると、前記符号化手段、前記送信側乗算手段、および前記送信手段を制御して、再度、情報を符号化させて共有鍵と乗算させて送信させる再送制御手段と、
を備え、
前記復号装置は、
前記送信手段から送信された乗算結果を、前記ネットワークを介して受信する受信手段と、
前記受信手段により受信された乗算結果と、前記共有鍵を構成する行列の逆行列と、を乗算する受信側乗算手段と、
前記受信側乗算手段による乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成するＲＲＥ演算手段と、
前記ＲＲＥ演算手段により生成されたＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する判定手段と、
前記判定手段により復号できると判定された場合に、前記ＲＲＥ形行列から前記情報を生成する復号手段と、
前記判定手段により復号できないと判定された場合に、前記符号化装置に前記再送要求を行う再送要求手段と、
を備えることを特徴とする情報伝送システム。
【請求項２】
前記送信側乗算手段および前記受信側乗算手段は、前記再送要求手段により前記再送要求が行われるたびに、前記共有鍵を更新することを特徴とする請求項１に記載の情報伝送システム。
【請求項３】
前記ＲＲＥ演算手段は、
前記再送要求手段により再送要求が行われるより前では、前記受信側乗算手段による乗算結果から今回のＲＲＥ形行列を生成し、
前記再送要求手段により再送要求が行われた後では、前記受信側乗算手段による今回の乗算結果と、前回のＲＲＥ形行列と、を行連結して今回のＲＲＥ形行列を生成することを特徴とする請求項１または２に記載の情報伝送システム。
【請求項４】
前記ＲＲＥ演算手段は、
前記受信側乗算手段による今回までの乗算結果を行連結した後に行基本変形を行って、今回のＲＲＥ形行列を生成することを特徴とする請求項１または２に記載の情報伝送システム。
【請求項５】
復号装置にネットワークを介して接続され、情報を符号化する符号化装置であって、
前記復号装置は、
前記符号化装置から送信された乗算結果を、前記ネットワークを介して受信する受信手段と、
前記受信手段により受信された乗算結果と、共有鍵を構成する行列の逆行列と、を乗算する受信側乗算手段と、
前記受信側乗算手段による乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成するＲＲＥ演算手段と、
前記ＲＲＥ演算手段により生成されたＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する判定手段と、
前記判定手段により復号できると判定された場合に、前記ＲＲＥ形行列から前記情報を生成する復号手段と、
前記判定手段により復号できないと判定された場合に、前記符号化装置に再送要求を行う再送要求手段と、
を備えており、
行列で表される情報を符号化する符号化手段と、
前記符号化手段により符号化された情報と、前記共有鍵と、を乗算する送信側乗算手段と、
前記送信側乗算手段による乗算結果を送信する送信手段と、
前記復号装置から前記再送要求があると、前記符号化手段、前記送信側乗算手段、および前記送信手段を制御して、再度、情報を符号化させて共有鍵と乗算させて送信させる再送制御手段と、
を備えることを特徴とする符号化装置。
【請求項６】
情報を符号化する符号化装置にネットワークを介して接続された復号装置であって、
前記符号化装置は、
行列で表される情報を符号化する符号化手段と、
前記符号化手段により符号化された情報と、予め定められた行列で構成される共有鍵と、を乗算する送信側乗算手段と、
前記送信側乗算手段による乗算結果を送信する送信手段と、
前記復号装置から再送要求があると、前記符号化手段、前記送信側乗算手段、および前記送信手段を制御して、再度、情報を符号化させて共有鍵と乗算させて送信させる再送制御手段と、
を備えており、
前記送信手段から送信された乗算結果を、前記ネットワークを介して受信する受信手段と、
前記受信手段により受信された乗算結果と、前記共有鍵を構成する行列の逆行列と、を乗算する受信側乗算手段と、
前記受信側乗算手段による乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成するＲＲＥ演算手段と、
前記ＲＲＥ演算手段により生成されたＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する判定手段と、
前記判定手段により復号できると判定された場合に、前記ＲＲＥ形行列から前記情報を生成する復号手段と、
前記判定手段により復号できないと判定された場合に、前記符号化装置に前記再送要求を行う再送要求手段と、
を備えることを特徴とする復号装置。
【請求項７】
情報を符号化する符号化装置と、当該符号化装置にネットワークを介して接続された復号装置と、を備える情報伝送システムにおける情報伝送方法であって、
前記符号化装置が、行列で表される情報を符号化する第１のステップと、
前記符号化装置が、前記第１のステップにおいて符号化した情報と、予め定められた行列で構成される共有鍵と、を乗算する第２のステップと、
前記符号化装置が、前記第２のステップにおける乗算結果を送信する第３のステップと、
前記符号化装置が、前記復号装置から再送要求があると、前記第１のステップ、前記第２のステップ、および前記第３のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第４のステップと、
前記復号装置が、前記第４のステップにおいて送信された乗算結果を、前記ネットワークを介して受信する第５のステップと、
前記復号装置が、前記第５のステップにおいて受信した乗算結果と、前記共有鍵を構成する行列の逆行列と、を乗算する第６のステップと、
前記復号装置が、前記第６のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第７のステップと、
前記復号装置が、前記第７のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第８のステップと、
前記復号装置が、前記第８のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第９のステップと、
前記復号装置が、前記第８のステップにおいて復号できないと判定した場合に、前記符号化装置に前記再送要求を行う第１０のステップと、
を備えることを特徴とする情報伝送方法。
【請求項８】
復号装置にネットワークを介して接続され、情報を符号化する符号化装置における符号化方法であって、
前記復号装置は、
前記符号化装置から送信された乗算結果を、前記ネットワークを介して受信する第１のステップと、
前記第１のステップにおいて受信した乗算結果と、共有鍵を構成する行列の逆行列と、を乗算する第２のステップと、
前記第２のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第３のステップと、
前記第３のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第４のステップと、
前記第４のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第５のステップと、
前記第４のステップにおいて復号できないと判定した場合に、前記符号化装置に再送要求を行う第６のステップと、
を行うものであり、
前記符号化装置が、行列で表される情報を符号化する第７のステップと、
前記符号化装置が、前記第７のステップにおいて符号化した情報と、前記共有鍵と、を乗算する第８のステップと、
前記符号化装置が、前記第８のステップにおける乗算結果を送信する第９のステップと、
前記符号化装置が、前記復号装置から前記再送要求があると、前記第７のステップ、前記第８のステップ、および前記第９のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第１０のステップと、
を備えることを特徴とする符号化方法。
【請求項９】
情報を符号化する符号化装置にネットワークを介して接続された復号装置における復号方法であって、
前記符号化装置は、
行列で表される情報を符号化する第１のステップと、
前記第１のステップにおいて符号化した情報と、予め定められた行列で構成される共有鍵と、を乗算する第２のステップと、
前記第２のステップにおける乗算結果を送信する第３のステップと、
前記復号装置から再送要求があると、前記第１のステップ、前記第２のステップ、および前記第３のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第４のステップと、
を行うものであり、
前記復号装置が、前記第４のステップにおいて送信された乗算結果を、前記ネットワークを介して受信する第５のステップと、
前記復号装置が、前記第５のステップにおいて受信した乗算結果と、前記共有鍵を構成する行列の逆行列と、を乗算する第６のステップと、
前記復号装置が、前記第６のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第７のステップと、
前記復号装置が、前記第７のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第８のステップと、
前記復号装置が、前記第８のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第９のステップと、
前記復号装置が、前記第８のステップにおいて復号できないと判定した場合に、前記符号化装置に前記再送要求を行う第１０のステップと、
を備えることを特徴とする復号方法。
【請求項１０】
情報を符号化する符号化装置と、当該符号化装置にネットワークを介して接続された復号装置と、を備える情報伝送システムにおける情報伝送方法を、コンピュータに実行させるためのプログラムであって、
前記符号化装置が、行列で表される情報を符号化する第１のステップと、
前記符号化装置が、前記第１のステップにおいて符号化した情報と、予め定められた行列で構成される共有鍵と、を乗算する第２のステップと、
前記符号化装置が、前記第２のステップにおける乗算結果を送信する第３のステップと、
前記符号化装置が、前記復号装置から再送要求があると、前記第１のステップ、前記第２のステップ、および前記第３のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第４のステップと、
前記復号装置が、前記第４のステップにおいて送信された乗算結果を、前記ネットワークを介して受信する第５のステップと、
前記復号装置が、前記第５のステップにおいて受信した乗算結果と、前記共有鍵を構成する行列の逆行列と、を乗算する第６のステップと、
前記復号装置が、前記第６のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第７のステップと、
前記復号装置が、前記第７のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第８のステップと、
前記復号装置が、前記第８のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第９のステップと、
前記復号装置が、前記第８のステップにおいて復号できないと判定した場合に、前記符号化装置に前記再送要求を行う第１０のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１１】
復号装置にネットワークを介して接続され、情報を符号化する符号化装置における符号化方法を、コンピュータに実行させるためのプログラムであって、
前記復号装置は、
前記符号化装置から送信された乗算結果を、前記ネットワークを介して受信する第１のステップと、
前記第１のステップにおいて受信した乗算結果と、共有鍵を構成する行列の逆行列と、を乗算する第２のステップと、
前記第２のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第３のステップと、
前記第３のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第４のステップと、
前記第４のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第５のステップと、
前記第４のステップにおいて復号できないと判定した場合に、前記符号化装置に再送要求を行う第６のステップと、
を行うものであり、
前記符号化装置が、行列で表される情報を符号化する第７のステップと、
前記符号化装置が、前記第７のステップにおいて符号化した情報と、前記共有鍵と、を乗算する第８のステップと、
前記符号化装置が、前記第８のステップにおける乗算結果を送信する第９のステップと、
前記符号化装置が、前記復号装置から前記再送要求があると、前記第７のステップ、前記第８のステップ、および前記第９のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第１０のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１２】
情報を符号化する符号化装置にネットワークを介して接続された復号装置における復号方法を、コンピュータに実行させるためのプログラムであって、
前記符号化装置は、
行列で表される情報を符号化する第１のステップと、
前記第１のステップにおいて符号化した情報と、予め定められた行列で構成される共有鍵と、を乗算する第２のステップと、
前記第２のステップにおける乗算結果を送信する第３のステップと、
前記復号装置から再送要求があると、前記第１のステップ、前記第２のステップ、および前記第３のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第４のステップと、
を行うものであり、
前記復号装置が、前記第４のステップにおいて送信された乗算結果を、前記ネットワークを介して受信する第５のステップと、
前記復号装置が、前記第５のステップにおいて受信した乗算結果と、前記共有鍵を構成する行列の逆行列と、を乗算する第６のステップと、
前記復号装置が、前記第６のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第７のステップと、
前記復号装置が、前記第７のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第８のステップと、
前記復号装置が、前記第８のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第９のステップと、
前記復号装置が、前記第８のステップにおいて復号できないと判定した場合に、前記符号化装置に前記再送要求を行う第１０のステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを介して情報を伝送する情報伝送システム、符号化装置、復号装置、情報伝送方法、符号化方法、復号方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、ネットワーク上のノード（例えば、ルータやスイッチなど）に、従来のコピー機能や転送機能ではなく、数学的演算機能を持たせることによって、伝送レートやスループットの向上や消費エネルギーの低減を実現するネットワーク符号化と呼ばれる技術（例えば、非特許文献１参照）が注目を浴びている。このネットワーク上には、伝送リンクを盗聴する受動的な攻撃者（盗聴者）や、ネットワークに誤ったパケットを故意に挿入して情報の伝送を阻害する能動的な攻撃者などが、存在する場合がある。
【０００３】
ネットワーク符号を施したネットワークには、誤ったパケットの挿入が行われると、この影響が次々に伝搬し、情報が伝送不能になってしまうという特性がある。そこで、能動的な攻撃者への対策を施したネットワーク符号に関する技術が提案されている（例えば、非特許文献２、３、４参照）。非特許文献２から４に示されている技術は、ネットワーク誤り訂正符号と呼ばれる技術であり、おおよそｔ個（ｔは、ｔ≧０を満たす任意の整数）の誤パケット挿入攻撃に対して、情報の送信時に２ｔ個以上の冗長パケットを情報に付与することで、受信者が正しく情報を復号できるという技術である。このネットワーク誤り訂正符号について、図７を用いて以下に詳述する。
【０００４】
図７は、従来例に係る情報伝送システム１００のブロック図である。情報伝送システム１００は、送信ノードとしての符号化装置１１０と、ネットワーク１５０を介して符号化装置１１０に接続された受信ノードとしての復号装置１２０と、を備える。攻撃者端末２００は、上述の能動的な攻撃者が操作する端末を示す。
【０００５】
符号化装置１１０は、情報パケットを、ネットワーク誤り訂正符号により符号化し、送信パケットとして送信する。復号装置１２０は、受信パケットを、ネットワーク誤り訂正符号により復号し、情報パケットとして出力する。
【０００６】
符号化装置１１０と復号装置１２０とは、利用するネットワーク誤り訂正のパラメータ以外の情報を共有しない。この点について、非特許文献５に、符号化装置１１０および復号装置１２０のそれぞれで予め秘密の情報（秘密鍵）を共有することで、能動的な攻撃者に対して、通常のネットワーク誤り訂正符号よりも強力な耐性を得ることができると示されている。具体的には、例えば、ｔ個の誤りパケットに対して、ｔ個の冗長パケットを情報に付与すれば、受信者が正しく情報を復号できる。このため、より高い情報パケットの送信レートやスループットを実現して、ネットワークの利用効率を向上できる。
【０００７】
しかし、非特許文献５に示されている技術では、復号が失敗してしまう確率を任意に（無視できるほどに）小さくするためには、非常に大きな有限体サイズでの演算が必要である。そこで、非特許文献６に、パケット長を長くすることで、演算に必要な有限体サイズを抑えつつ、復号が失敗してしまう確率を任意に小さくすることができる技術が示されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】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.
【非特許文献２】R.  W.  Yeung  and  N.  Cai,  “Network  error  correction,  part  I:  Basic  concepts  and  upper  bounds,”  Communications  in  Information  and  Systems,  vol.6,  no.1,  pp.19-36,  2006.
【非特許文献３】N.  Cai  and  R.  W.  Yeung,  “Network  error  correction,  part  II:  Lower  bounds,”  Communications  in  Information  and  Systems,  vol.6,  no.1,  pp.37-54,  2006.
【非特許文献４】R.  Koetter  and  F.  R.  Kschischang,  “Coding  for  errors  and  erasures  in  random  network  coding,”  IEEE  Transactions  on  Information  Theory,  vol.54,  no.8,  pp.3579-3591,  2008.
【非特許文献５】S.  Jaggi,  M.  Langberg,  S.  Katti,  T.  Ho,  D.  Katabi,  M.  Medard,  and  M.  Effros,  “Resilient  network  coding  in  the  presence  of  byzantine  adversaries,”  IEEE  Transactions  on  Information  Theory,  vol.54,  no.6,  pp.2596-2603,  2008.
【非特許文献６】D.  Silva  and  F.  R.  Kschischang,  “A  key-based  error  control  scheme  for  network  coding,”  in  Proceedings  of  Canadian  Workshop  on  Information  Theory  (CWIT)  2009,  pp.5-8,  Otawa,  ON,  Canada,  May  2009.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献５や非特許文献６に示されている技術を用いるためには、ネットワーク上で攻撃者が挿入してくる誤りパケットの最大数を、予め想定する必要がある。このため、想定した最大数を超える誤りパケットが挿入されてしまうと、情報パケットを復号することができなかった。
【００１０】
そこで、本発明は、上述の課題に鑑みてなされたものであり、ネットワーク上で攻撃者が挿入してくる誤りパケットの最大数を予め想定することなく、ネットワークの利用効率を向上でき、かつ、復号の失敗確率を小さくすることを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、上記の課題を解決するために、以下の事項を提案している。
（１）  本発明は、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）と、当該符号化装置にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続された復号装置（例えば、図１の復号装置２０に相当）と、を備える情報伝送システム（例えば、図１の情報伝送システム１に相当）であって、前記符号化装置は、行列で表される情報を符号化する符号化手段（例えば、図２の符号化器１１に相当）と、前記符号化手段により符号化された情報と、予め定められた行列で構成される共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する送信側乗算手段（例えば、図２の乗算器１２に相当）と、前記送信側乗算手段による乗算結果を送信する送信手段（例えば、図２の送信器１３に相当）と、前記復号装置から再送要求があると、前記符号化手段、前記送信側乗算手段、および前記送信手段を制御して、再度、情報を符号化させて共有鍵と乗算させて送信させる再送制御手段（例えば、図２の再送制御部１４に相当）と、を備え、前記復号装置は、前記送信手段から送信された乗算結果を、前記ネットワークを介して受信する受信手段（例えば、図４の受信器２１に相当）と、前記受信手段により受信された乗算結果と、前記共有鍵を構成する行列の逆行列（例えば、後述のＴＨｉに相当）と、を乗算する受信側乗算手段（例えば、図４の乗算器２２に相当）と、前記受信側乗算手段による乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成するＲＲＥ演算手段（例えば、図４のＲＲＥ演算器２３や、図６のＲＲＥ演算器２３Ａに相当）と、前記ＲＲＥ演算手段により生成されたＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する判定手段（例えば、図４の判定器２４に相当）と、前記判定手段により復号できると判定された場合に、前記ＲＲＥ形行列から前記情報を生成する復号手段（例えば、図４の復号器２５に相当）と、前記判定手段により復号できないと判定された場合に、前記符号化装置に前記再送要求を行う再送要求手段（例えば、図４の再送要求部２６に相当）と、を備えることを特徴とする情報伝送システムを提案している。
【００１２】
この発明によれば、符号化装置は、行列で表される情報を符号化し、予め定められた行列で構成される共有鍵と乗算して、この乗算結果を送信することとした。このため、冗長パケットを情報に付与する必要がないため、さらに高い情報パケットの送信レートやスループットを実現して、ネットワークの利用効率を向上できる。
【００１３】
また、この発明によれば、符号化装置および復号装置は、同一の共有鍵を利用して、処理を行うこととした。このため、上述のような能動的な攻撃者に対して、高い堅牢性を実現できる。
【００１４】
また、この発明によれば、復号装置は、ネットワークから受信した乗算結果を、共有鍵を構成する行列の逆行列と乗算し、この乗算結果を用いてＲＲＥ形行列を生成して、このＲＲＥ形行列に予め定められた部分行列が含まれているか否かにより、情報を復号できるか否かを判定することとした。また、情報を復号できないと判定した場合には、符号化装置に対して、上述の符号化および乗算をやり直させて乗算結果を再送させ、再送させた乗算結果を用いて上述の判定をやり直すこととした。このため、ネットワーク上で攻撃者が挿入してくる誤りパケットの最大数を予め想定することなく、情報を復号することができ、復号の失敗確率を小さくすることができる。
【００１５】
（２）  本発明は、（１）の情報伝送システムについて、前記送信側乗算手段および前記受信側乗算手段は、前記再送要求手段により前記再送要求が行われるたびに、前記共有鍵を更新することを特徴とする情報伝送システムを提案している。
【００１６】
この発明によれば、（１）の情報伝送システムにおいて、復号装置が再送要求を行うたびに、符号化装置および復号装置が利用する共有鍵を更新することとした。このため、上述の堅牢性をさらに向上させることができる。
【００１７】
（３）  本発明は、（１）または（２）の情報伝送システムについて、前記ＲＲＥ演算手段（例えば、図４のＲＲＥ演算器２３に相当）は、前記再送要求手段により再送要求が行われるより前（例えば、後述の第１ステージに相当）では、前記受信側乗算手段による乗算結果から今回のＲＲＥ形行列を生成し、前記再送要求手段により再送要求が行われた後（例えば、後述の第２ステージ以降に相当）では、前記受信側乗算手段による今回の乗算結果と、前回のＲＲＥ形行列と、を行連結して今回のＲＲＥ形行列を生成することを特徴とする情報伝送システムを提案している。
【００１８】
この発明によれば、（１）または（２）の情報伝送システムにおいて、復号装置が再送要求を行うより前では、ネットワークから受信した乗算結果と共有鍵を構成する行列の逆行列との乗算結果から今回のＲＲＥ形行列を生成することとした。一方、復号装置が再送要求を行った後では、ネットワークから受信した乗算結果と共有鍵を構成する行列の逆行列との乗算結果と、前回のＲＲＥ形行列と、を行連結して、今回のＲＲＥ形行列を生成することとした。このため、情報を復号できないと判定した場合には、この際に生成したＲＲＥ形行列を、次回で生成するＲＲＥ形行列に反映させることができる。したがって、再送要求を行うに従って情報の訂正確率を向上させることができ、復号の失敗確率をさらに小さくすることができる。
【００１９】
（４）  本発明は、（１）または（２）の情報伝送システムについて、前記ＲＲＥ演算手段（例えば、図６のＲＲＥ演算器２３Ａに相当）は、前記受信側乗算手段による今回までの乗算結果を行連結した後に行基本変形を行って、今回のＲＲＥ形行列を生成することを特徴とする情報伝送システムを提案している。
【００２０】
この発明によれば、（１）または（２）の情報伝送システムにおいて、ネットワークから受信した乗算結果と、共有鍵を構成する行列の逆行列と、の今回までの乗算結果を行連結した後に行基本変形を行って、今回のＲＲＥ形行列を生成することとした。このため、情報を復号できないと判定した場合には、ネットワークから受信した乗算結果と共有鍵を構成する行列の逆行列とのそれまでの乗算結果を、次回で生成するＲＲＥ形行列に反映させることができる。したがって、再送要求を行うに従って情報の訂正確率を向上させることができ、復号の失敗確率をさらに小さくすることができる。
【００２１】
（５）  本発明は、復号装置（例えば、図１の復号装置２０に相当）にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続され、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）であって、前記復号装置は、前記符号化装置から送信された乗算結果を、前記ネットワークを介して受信する受信手段（例えば、図４の受信器２１に相当）と、前記受信手段により受信された乗算結果と、共有鍵を構成する行列（例えば、後述のＴＨｉに相当）の逆行列と、を乗算する受信側乗算手段（例えば、図４の乗算器２２に相当）と、前記受信側乗算手段による乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成するＲＲＥ演算手段（例えば、図４のＲＲＥ演算器２３や、図６のＲＲＥ演算器２３Ａに相当）と、前記ＲＲＥ演算手段により生成されたＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する判定手段（例えば、図４の判定器２４に相当）と、前記判定手段により復号できると判定された場合に、前記ＲＲＥ形行列から前記情報を生成する復号手段（例えば、図４の復号器２５に相当）と、前記判定手段により復号できないと判定された場合に、前記符号化装置に再送要求を行う再送要求手段（例えば、図４の再送要求部２６に相当）と、を備えており、行列で表される情報を符号化する符号化手段（例えば、図２の符号化器１１に相当）と、前記符号化手段により符号化された情報と、前記共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する送信側乗算手段（例えば、図２の乗算器１２に相当）と、前記送信側乗算手段による乗算結果を送信する送信手段（例えば、図２の送信器１３に相当）と、前記復号装置から前記再送要求があると、前記符号化手段、前記送信側乗算手段、および前記送信手段を制御して、再度、情報を符号化させて共有鍵と乗算させて送信させる再送制御手段（例えば、図２の再送制御部１４に相当）と、を備えることを特徴とする符号化装置を提案している。
【００２２】
この発明によれば、上述した効果と同様の効果を奏することができる。
【００２３】
（６）  本発明は、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続された復号装置（例えば、図１の復号装置２０に相当）であって、前記符号化装置は、行列で表される情報を符号化する符号化手段（例えば、図２の符号化器１１に相当）と、前記符号化手段により符号化された情報と、予め定められた行列で構成される共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する送信側乗算手段（例えば、図２の乗算器１２に相当）と、前記送信側乗算手段による乗算結果を送信する送信手段（例えば、図２の送信器１３に相当）と、前記復号装置から再送要求があると、前記符号化手段、前記送信側乗算手段、および前記送信手段を制御して、再度、情報を符号化させて共有鍵と乗算させて送信させる再送制御手段（例えば、図２の再送制御部１４に相当）と、を備えており、前記送信手段から送信された乗算結果を、前記ネットワークを介して受信する受信手段（例えば、図４の受信器２１に相当）と、前記受信手段により受信された乗算結果と、前記共有鍵を構成する行列（例えば、後述のＴＨｉに相当）の逆行列と、を乗算する受信側乗算手段（例えば、図４の乗算器２２に相当）と、前記受信側乗算手段による乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成するＲＲＥ演算手段（例えば、図４のＲＲＥ演算器２３や、図６のＲＲＥ演算器２３Ａに相当）と、前記ＲＲＥ演算手段により生成されたＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する判定手段（例えば、図４の判定器２４に相当）と、前記判定手段により復号できると判定された場合に、前記ＲＲＥ形行列から前記情報を生成する復号手段（例えば、図４の復号器２５に相当）と、前記判定手段により復号できないと判定された場合に、前記符号化装置に前記再送要求を行う再送要求手段（例えば、図４の再送要求部２６に相当）と、を備えることを特徴とする復号装置を提案している。
【００２４】
この発明によれば、上述した効果と同様の効果を奏することができる。
【００２５】
（７）  本発明は、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）と、当該符号化装置にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続された復号装置（例えば、図１の復号装置２０に相当）と、を備える情報伝送システム（例えば、図１の情報伝送システム１に相当）における情報伝送方法であって、前記符号化装置が、行列で表される情報を符号化する第１のステップ（例えば、図３のステップＳ１に相当）と、前記符号化装置が、前記第１のステップにおいて符号化した情報と、予め定められた行列で構成される共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する第２のステップ（例えば、図３のステップＳ２に相当）と、前記符号化装置が、前記第２のステップにおける乗算結果を送信する第３のステップ（例えば、図３のステップＳ３に相当）と、前記符号化装置が、前記復号装置から再送要求があると、前記第１のステップ、前記第２のステップ、および前記第３のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第４のステップ（例えば、図３のステップＳ４に相当）と、前記復号装置が、前記第４のステップにおいて送信された乗算結果を、前記ネットワークを介して受信する第５のステップ（例えば、図５のステップＳ１１に相当）と、前記復号装置が、前記第５のステップにおいて受信した乗算結果と、前記共有鍵を構成する行列（例えば、後述のＴＨｉに相当）の逆行列と、を乗算する第６のステップ（例えば、図５のステップＳ１２に相当）と、前記復号装置が、前記第６のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第７のステップ（例えば、図５のステップＳ１３に相当）と、前記復号装置が、前記第７のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第８のステップ（例えば、図５のステップＳ１４に相当）と、前記復号装置が、前記第８のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第９のステップ（例えば、図５のステップＳ１７に相当）と、前記復号装置が、前記第８のステップにおいて復号できないと判定した場合に、前記符号化装置に前記再送要求を行う第１０のステップ（例えば、図５のステップＳ１５に相当）と、を備えることを特徴とする情報伝送方法を提案している。
【００２６】
この発明によれば、上述した効果と同様の効果を奏することができる。
【００２７】
（８）  本発明は、復号装置（例えば、図１の復号装置２０に相当）にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続され、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）における符号化方法であって、前記復号装置は、前記符号化装置から送信された乗算結果を、前記ネットワークを介して受信する第１のステップ（例えば、図５のステップＳ１１に相当）と、前記第１のステップにおいて受信した乗算結果と、共有鍵を構成する行列（例えば、後述のＴＨｉに相当）の逆行列と、を乗算する第２のステップ（例えば、図５のステップＳ１２に相当）と、前記第２のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第３のステップ（例えば、図５のステップＳ１３に相当）と、前記第３のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第４のステップ（例えば、図５のステップＳ１４に相当）と、前記第４のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第５のステップ（例えば、図５のステップＳ１７に相当）と、前記第４のステップにおいて復号できないと判定した場合に、前記符号化装置に再送要求を行う第６のステップ（例えば、図５のステップＳ１５に相当）と、を行うものであり、前記符号化装置が、行列で表される情報を符号化する第７のステップ（例えば、図３のステップＳ１に相当）と、前記符号化装置が、前記第７のステップにおいて符号化した情報と、前記共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する第８のステップ（例えば、図３のステップＳ２に相当）と、前記符号化装置が、前記第８のステップにおける乗算結果を送信する第９のステップ（例えば、図３のステップＳ３に相当）と、前記符号化装置が、前記復号装置から前記再送要求があると、前記第７のステップ、前記第８のステップ、および前記第９のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第１０のステップ（例えば、図３のステップＳ４に相当）と、を備えることを特徴とする符号化方法を提案している。
【００２８】
この発明によれば、上述した効果と同様の効果を奏することができる。
【００２９】
（９）  本発明は、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続された復号装置（例えば、図１の復号装置２０に相当）における復号方法であって、前記符号化装置は、行列で表される情報を符号化する第１のステップ（例えば、図３のステップＳ１に相当）と、前記第１のステップにおいて符号化した情報と、予め定められた行列で構成される共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する第２のステップ（例えば、図３のステップＳ２に相当）と、前記第２のステップにおける乗算結果を送信する第３のステップ（例えば、図３のステップＳ３に相当）と、前記復号装置から再送要求があると、前記第１のステップ、前記第２のステップ、および前記第３のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第４のステップ（例えば、図３のステップＳ４に相当）と、を行うものであり、前記復号装置が、前記第４のステップにおいて送信された乗算結果を、前記ネットワークを介して受信する第５のステップ（例えば、図５のステップＳ１１に相当）と、前記復号装置が、前記第５のステップにおいて受信した乗算結果と、前記共有鍵を構成する行列（例えば、後述のＴＨｉに相当）の逆行列と、を乗算する第６のステップ（例えば、図５のステップＳ１２に相当）と、前記復号装置が、前記第６のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第７のステップ（例えば、図５のステップＳ１３に相当）と、前記復号装置が、前記第７のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第８のステップ（例えば、図５のステップＳ１４に相当）と、前記復号装置が、前記第８のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第９のステップ（例えば、図５のステップＳ１７に相当）と、前記復号装置が、前記第８のステップにおいて復号できないと判定した場合に、前記符号化装置に前記再送要求を行う第１０のステップ（例えば、図５のステップＳ１５に相当）と、を備えることを特徴とする復号方法を提案している。
【００３０】
この発明によれば、上述した効果と同様の効果を奏することができる。
【００３１】
（１０）  本発明は、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）と、当該符号化装置にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続された復号装置（例えば、図１の復号装置２０に相当）と、を備える情報伝送システム（例えば、図１の情報伝送システム１に相当）における情報伝送方法を、コンピュータに実行させるためのプログラムであって、前記符号化装置が、行列で表される情報を符号化する第１のステップ（例えば、図３のステップＳ１に相当）と、前記符号化装置が、前記第１のステップにおいて符号化した情報と、予め定められた行列で構成される共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する第２のステップ（例えば、図３のステップＳ２に相当）と、前記符号化装置が、前記第２のステップにおける乗算結果を送信する第３のステップ（例えば、図３のステップＳ３に相当）と、前記符号化装置が、前記復号装置から再送要求があると、前記第１のステップ、前記第２のステップ、および前記第３のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第４のステップ（例えば、図３のステップＳ４に相当）と、前記復号装置が、前記第４のステップにおいて送信された乗算結果を、前記ネットワークを介して受信する第５のステップ（例えば、図５のステップＳ１１に相当）と、前記復号装置が、前記第５のステップにおいて受信した乗算結果と、前記共有鍵を構成する行列（例えば、後述のＴＨｉに相当）の逆行列と、を乗算する第６のステップ（例えば、図５のステップＳ１２に相当）と、前記復号装置が、前記第６のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第７のステップ（例えば、図５のステップＳ１３に相当）と、前記復号装置が、前記第７のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第８のステップ（例えば、図５のステップＳ１４に相当）と、前記復号装置が、前記第８のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第９のステップ（例えば、図５のステップＳ１７に相当）と、前記復号装置が、前記第８のステップにおいて復号できないと判定した場合に、前記符号化装置に前記再送要求を行う第１０のステップ（例えば、図５のステップＳ１５に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３２】
この発明によれば、上述した効果と同様の効果を奏することができる。
【００３３】
（１１）  本発明は、復号装置（例えば、図１の復号装置２０に相当）にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続され、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）における符号化方法を、コンピュータに実行させるためのプログラムであって、前記復号装置は、前記符号化装置から送信された乗算結果を、前記ネットワークを介して受信する第１のステップ（例えば、図５のステップＳ１１に相当）と、前記第１のステップにおいて受信した乗算結果と、共有鍵を構成する行列（例えば、後述のＴＨｉに相当）の逆行列と、を乗算する第２のステップ（例えば、図５のステップＳ１２に相当）と、前記第２のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第３のステップ（例えば、図５のステップＳ１３に相当）と、前記第３のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第４のステップ（例えば、図５のステップＳ１４に相当）と、前記第４のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第５のステップ（例えば、図５のステップＳ１７に相当）と、前記第４のステップにおいて復号できないと判定した場合に、前記符号化装置に再送要求を行う第６のステップ（例えば、図５のステップＳ１５に相当）と、を行うものであり、前記符号化装置が、行列で表される情報を符号化する第７のステップ（例えば、図３のステップＳ１に相当）と、前記符号化装置が、前記第７のステップにおいて符号化した情報と、前記共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する第８のステップ（例えば、図３のステップＳ２に相当）と、前記符号化装置が、前記第８のステップにおける乗算結果を送信する第９のステップ（例えば、図３のステップＳ３に相当）と、前記符号化装置が、前記復号装置から前記再送要求があると、前記第７のステップ、前記第８のステップ、および前記第９のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第１０のステップ（例えば、図３のステップＳ４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３４】
この発明によれば、上述した効果と同様の効果を奏することができる。
【００３５】
（１２）  本発明は、情報を符号化する符号化装置（例えば、図１の符号化装置１０に相当）にネットワーク（例えば、図１のネットワーク１５０に相当）を介して接続された復号装置（例えば、図１の復号装置２０に相当）における復号方法を、コンピュータに実行させるためのプログラムであって、前記符号化装置は、行列で表される情報を符号化する第１のステップ（例えば、図３のステップＳ１に相当）と、前記第１のステップにおいて符号化した情報と、予め定められた行列で構成される共有鍵（例えば、後述のＴＨｉに相当）と、を乗算する第２のステップ（例えば、図３のステップＳ２に相当）と、前記第２のステップにおける乗算結果を送信する第３のステップ（例えば、図３のステップＳ３に相当）と、前記復号装置から再送要求があると、前記第１のステップ、前記第２のステップ、および前記第３のステップを行って、再度、情報を符号化して共有鍵と乗算して送信する第４のステップ（例えば、図３のステップＳ４に相当）と、を行うものであり、前記復号装置が、前記第４のステップにおいて送信された乗算結果を、前記ネットワークを介して受信する第５のステップ（例えば、図５のステップＳ１１に相当）と、前記復号装置が、前記第５のステップにおいて受信した乗算結果と、前記共有鍵を構成する行列（例えば、後述のＴＨｉに相当）の逆行列と、を乗算する第６のステップ（例えば、図５のステップＳ１２に相当）と、前記復号装置が、前記第６のステップにおける乗算結果を用いて、ＲＲＥ（Reduced  Row  Echelon）形行列を生成する第７のステップ（例えば、図５のステップＳ１３に相当）と、前記復号装置が、前記第７のステップにおいて生成したＲＲＥ形行列に予め定められた部分行列が含まれているか否かを判別し、含まれている場合には前記情報を復号できると判定し、含まれていない場合には前記情報を復号できないと判定する第８のステップ（例えば、図５のステップＳ１４に相当）と、前記復号装置が、前記第８のステップにおいて復号できると判定した場合に、前記ＲＲＥ形行列から前記情報を生成する第９のステップ（例えば、図５のステップＳ１７に相当）と、前記復号装置が、前記第８のステップにおいて復号できないと判定した場合に、前記符号化装置に前記再送要求を行う第１０のステップ（例えば、図５のステップＳ１５に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３６】
この発明によれば、上述した効果と同様の効果を奏することができる。
【発明の効果】
【００３７】
本発明によれば、ネットワーク上で攻撃者が挿入してくる誤りパケットの最大数を予め想定することなく、ネットワークの利用効率を向上でき、かつ、復号の失敗確率を小さくすることができる。
【図面の簡単な説明】
【００３８】
【図１】本発明の第１実施形態に係る情報伝送システムのブロック図である。
【図２】前記実施形態に係る情報伝送システムが備える符号化装置のブロック図である。
【図３】前記実施形態に係る情報伝送システムが備える符号化装置の動作を示すフローチャートである。
【図４】前記実施形態に係る情報伝送システムが備える復号装置のブロック図である。
【図５】前記実施形態に係る情報伝送システムが備える復号装置の動作を示すフローチャートである。
【図６】本発明の第２実施形態に係る情報伝送システムのブロック図である。
【図７】従来例に係る情報伝送システムのブロック図である。
【発明を実施するための形態】
【００３９】
以下、本発明の実施の形態について図面を参照しながら説明する。なお、以下の実施形態における構成要素は適宜、既存の構成要素などとの置き換えが可能であり、また、他の既存の構成要素との組み合せを含む様々なバリエーションが可能である。したがって、以下の実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００４０】
＜第１実施形態＞
［情報伝送システム１の構成］
図１は、本発明の第１実施形態に係る情報伝送システム１のブロック図である。情報伝送システム１は、図７に示した従来例に係る情報伝送システム１００とは、符号化装置１１０の代わりに符号化装置１０を備える点と、復号装置１２０の代わりに復号装置２０を備える点と、が異なる。なお、情報伝送システム１において情報伝送システム１００と同一構成要件については、同一符号を付し、その説明を省略する。
【００４１】
［符号化装置１０の構成および動作］
図２は、符号化装置１０のブロック図である。符号化装置１０は、符号化器１１、乗算器１２、送信器１３、および再送制御部１４を備える。
【００４２】
再送制御部１４は、復号装置２０から後述の再送要求があると、符号化器１１、乗算器１２、および送信器１３を制御して、再度、送信パケットを生成させてネットワーク１５０に出力させる。復号装置２０から再送要求があったか否かの判別は、以下のように行われる。
【００４３】
詳細については後述するが、復号装置２０は、正しく情報を復号できる場合には、復号完了通知を符号化装置１０に送信し、正しく情報を復号できない場合には、復号完了通知を符号化装置１０に送信しない。そこで、再送制御部１４は、符号化装置１０から送信パケットが送信されてから予め定められた時間が経過するまでの期間に、復号装置２０から復号完了通知を受信したか否かを判別する。そして、受信していないと判別した場合に、復号装置２０から上述の再送要求があったと判別する。
【００４４】
なお、以降では、符号化装置１０が送信パケットを送信した回数を、第ｉステージ（ｉは、ｉ≧１を満たす任意の整数）と表すものとする。例えば、ある情報について送信パケットの送信が初めての場合には、第１ステージと表し、上述のある情報について送信パケットを送信するのが２回目の場合、すなわち上述のある情報について送信パケットの再送が初めての場合には、第２ステージと表す。
【００４５】
符号化器１１は、符号化装置１０に入力された情報パケットを符号化する。この情報パケットは、以下の数式（１）に示す行列で表されるものとする。
【００４６】
【数１】
2014171020.tif 000003
【００４７】
なお、数式（１）において、Ｆｑは、位数ｑを有する有限体であり、ｑは、素数の累乗である。
【００４８】
また、ネットワーク１５０上の各リンクは、１単位時間にＦｑの要素を１つ伝送でき、符号化装置１０から復号装置２０に１単位時間にＦｑの要素をｎ個伝送するネットワーク符号が構成されているものとする。また、ｍ個の連続するＦｑの要素を１パケットと勘定し、敷設されているネットワーク符号は、１パケットの伝送ごとにネットワーク符号の構造が変化するものとする。
【００４９】
乗算器１２は、複数種類の共有鍵を記憶しており、上述のステージが変わるたびに、用いる共有鍵を予め定められたルールに従って更新する。第ｉステージで乗算器１２が用いる共有鍵Ｐｉは、以下の数式（２）に示す行列で表されるものとする。
【００５０】
【数２】
2014171020.tif 000004
【００５１】
また、乗算器１２は、共有鍵Ｐｉを用いて以下の数式（３）に示す行列ＴＨｉを求める。
【００５２】
【数３】
2014171020.tif 000005
【００５３】
なお、ｊ×ｊ単位行列Ｉｊ×ｊを以下の数式（４）のように示し、ｊ×ｋゼロ行列Ｏｊ×ｋを以下の数式（５）のように示すものとする。また、以降では、説明を簡略化するために、行列ＴＨｉのことを共有鍵と呼ぶこととする。
【００５４】
【数４】
2014171020.tif 000006
【００５５】
【数５】
2014171020.tif 000007
【００５６】
また、乗算器１２は、符号化器１１により符号化された情報パケットと、第ｉステージの共有鍵としての行列ＴＨｉと、を乗算して、以下の数式（６）に示す行列Ｘｉを求める。各送信パケットは、行列Ｘｉの各行で表される。
【００５７】
【数６】
2014171020.tif 000008
【００５８】
送信器１３は、ｎ本の出力リンクを備える。この送信器１３は、これらｎ本の出力リンクのそれぞれからネットワーク１５０に、乗算器１２により生成された行列Ｘｉの各行を、第ｉステージの送信パケットとして出力する。
【００５９】
図３は、符号化装置１０の動作を示すフローチャートである。
【００６０】
ステップＳ１において、符号化装置１０は、符号化器１１により符号化処理を行って、ステップＳ２に処理を移す。符号化処理では、符号化器１１が、上述のように情報パケットを符号化する。
【００６１】
ステップＳ２において、符号化装置１０は、乗算器１２により乗算処理を行って、ステップＳ３に処理を移す。乗算処理では、乗算器１２が、ステップＳ１において符号化した情報パケットと、第ｉステージの共有鍵としての行列ＴＨｉと、を上述のように乗算して、送信パケットを生成する。
【００６２】
ステップＳ３において、符号化装置１０は、送信器１３により送信処理を行って、ステップＳ４に処理を移す。送信処理では、送信器１３が、ステップＳ２において生成した送信パケットを、上述のようにネットワーク１５０に出力する。
【００６３】
ステップＳ４において、符号化装置１０は、再送制御部１４により、復号装置２０から再送要求があったか否かを判別する。再送要求があったと判別した場合には、ステップＳ１に処理を戻し、次のステージにおいてステップＳ１からステップＳ３の処理をもう一度繰り返す。一方、再送要求がなかったと判別した場合には、図３の処理を終了する。
【００６４】
［復号装置２０の構成および動作］
図４は、復号装置２０のブロック図である。復号装置２０は、受信器２１、乗算器２２、ＲＲＥ演算器２３、判定器２４、復号器２５、および再送要求部２６を備える。
【００６５】
受信器２１は、Ｎ本の入力リンクを備える。この受信器２１は、これらＮ本の入力リンクのそれぞれから、第ｉステージの受信パケットを受信する。第ｉステージの受信パケットとは、送信器１３から出力された第ｉステージの送信パケットが、ネットワーク１５０を介して復号装置２０に送信されたもののことである。
【００６６】
ここで、ネットワーク符号の構造は、ステージごとに変化するものとする。すると、受信器２１が受信する第ｉステージの受信パケットＹｉは、以下の数式（７）のように表される。
【００６７】
【数７】
2014171020.tif 000009
【００６８】
なお、第ｉステージのネットワーク符号の構造を表す遷移行列Ａｉを以下の数式（８）のように示し、第ｉステージで挿入される誤りパケットＺｉを以下の数式（９）のように示し、その遷移行列ＡｉＢｉを以下の数式（１０）のように示すものとする。また、数式（９）（１０）において、ｔｉは、第ｉステージで挿入された誤りパケット数を示す。また、復号装置２０にとって、Ａｉ、Ｘｉ、Ｂｉ、Ｚｉ、ｔｉなどの全てが未知である。
【００６９】
【数８】
2014171020.tif 000010
【００７０】
【数９】
2014171020.tif 000011
【００７１】
【数１０】
2014171020.tif 000012
【００７２】
乗算器２２は、符号化装置１０の乗算器１２で記憶されている複数種類の共有鍵を全て記憶しており、上述のステージが変わるたびに、用いる共有鍵を上述の予め定められたルールに従って更新する。このため、乗算器１２と乗算器２２とは、ステージが変わっても同一の共有鍵を用いることができる。
【００７３】
また、乗算器２２は、共有鍵Ｐｉを用いて、第ｉステージの共有鍵としての行列ＴＨｉの逆行列を求める。この逆行列は、以下の数式（１１）で表すことができる。
【００７４】
【数１１】
2014171020.tif 000013
【００７５】
また、乗算器２２は、受信器２１により受信された第ｉステージの受信パケットＹｉと、第ｉステージの共有鍵としての行列ＴＨｉの逆行列と、を乗算して、以下の数式（１２）に示す行列を求める。
【００７６】
【数１２】
2014171020.tif 000014
【００７７】
ＲＲＥ演算器２３は、乗算器２２により求められた第ｉステージにおける数式（１２）の行列を用いて、第ｉステージのReduced  Row  Echelon（ＲＲＥ）形行列を生成する。
【００７８】
具体的には、ＲＲＥ演算器２３は、第１ステージである場合（ｉ＝１である場合）には、乗算器２２により求められた第１ステージにおける数式（１２）の行列に対して、Gauss-Jordanの掃き出し法といったアルゴリズムを利用して、第１ステージのＲＲＥ形行列とする。一方、第２ステージ以降である場合（ｉ≧２である場合）には、乗算器２２により求められた第ｉステージにおける数式（１２）の行列と、第（ｉ−１）ステージのＲＲＥ形行列と、を行連結して、第ｉステージのＲＲＥ形行列とする。
【００７９】
判定器２４は、第ｉステージのＲＲＥ形行列に、符号化器１１で予め規定される特定の部分行列が含まれているか否かを判別する。
【００８０】
具体的には、判定器２４は、まず、ＲＲＥ演算器２３により生成された第ｉステージのＲＲＥ形行列ＲＲＥ（Ｙ＾（ｉ））が何らかのＴ≧０について以下の数式（１３）を満たすか否か、すなわちＲＲＥ（Ｙ＾（ｉ））の階段行列部の最後にＩ（ｎ−ｖ）×（ｎ−ｖ）が出現し、このＩ（ｎ−ｖ）×（ｎ−ｖ）が（ｖ＋１）行目からｎ行目までにおけるブロック行列であるか否かを判別する。
【００８１】
【数１３】
2014171020.tif 000015
【００８２】
なお、数式（１３）において、Ｐ、Ｑは、それぞれ数式（１４）、（１５）を満たすものとする。
【００８３】
【数１４】
2014171020.tif 000016
【００８４】
【数１５】
2014171020.tif 000017
【００８５】
次に、上述の数式（１３）を満たすと判別した場合には、正しく情報を復号できると判定し、上述の数式（１３）を満たさないと判別した場合には、正しく情報を復号できないと判定する。
【００８６】
復号器２５は、判定器２４により正しく情報を復号できると判定された場合に、以下の数式（１６）に示す情報パケットに相当する行列を求め、情報パケットとして出力する。
【００８７】
【数１６】
2014171020.tif 000018
【００８８】
再送要求部２６は、判定器２４により、正しく情報を復号できると判定された場合には、復号完了通知を符号化装置１０に送信し、正しく情報を復号できないと判定された場合には、復号完了通知を符号化装置１０に送信しない。
【００８９】
図５は、復号装置２０の動作を示すフローチャートである。
【００９０】
ステップＳ１１において、復号装置２０は、受信器２１により受信処理を行って、ステップＳ１２に処理を移す。受信処理では、受信器２１が、ネットワーク１５０から、上述のように受信パケットを受信する。
【００９１】
ステップＳ１２において、復号装置２０は、乗算器２２により乗算処理を行って、ステップＳ１３に処理を移す。乗算処理では、乗算器２２が、ステップＳ１１において受信した受信パケットと、第ｉステージの共有鍵としての行列ＴＨｉの逆行列と、を上述のように乗算する。
【００９２】
ステップＳ１３において、復号装置２０は、ＲＲＥ演算器２３によりＲＲＥ演算処理を行って、ステップＳ１４に処理を移す。ＲＲＥ演算処理では、ＲＲＥ演算器２３が、ステップＳ１２における乗算結果を用いて、上述のように第ｉステージのＲＲＥ形行列を生成する。
【００９３】
ステップＳ１４において、復号装置２０は、判定器２４により、正しく情報を復号できるか否かを判定する。正しく復号できないと判定した場合には、ステップＳ１５に処理を移し、正しく復号できると判定した場合には、ステップＳ１６に処理を移す。
【００９４】
ステップＳ１５において、復号装置２０は、再送要求部２６により復号未完了通知処理を行って、ステップＳ１１に処理を戻し、次のステージにおいてステップＳ１１からステップＳ１４の処理をもう一度繰り返す。復号未完了通知処理では、再送要求部２６が、復号完了通知を符号化装置１０に送信することなく、ステップＳ１１に処理が戻るようにする。
【００９５】
ステップＳ１６において、復号装置２０は、再送要求部２６により復号完了通知処理を行って、ステップＳ１７に処理を移す。復号完了通知処理では、再送要求部２６が、復号完了通知を符号化装置１０に送信する。
【００９６】
ステップＳ１７において、復号装置２０は、復号器２５により復号処理を行って、図５の処理を終了する。復号処理では、復号器２５が、ステップＳ１３において求めた現在のステージにおけるＲＲＥ形行列から、復号結果を求め、情報パケットとして出力する。
【００９７】
以上の情報伝送システム１によれば、以下の効果を奏することができる。
【００９８】
符号化装置１０は、行列で表される情報を符号化し、共有鍵としての行列ＴＨｉと乗算して、この乗算結果を送信する。このため、冗長パケットを情報に付与する必要がないため、さらに高い情報パケットの送信レートやスループットを実現して、ネットワークの利用効率を向上できる。
【００９９】
また、この発明によれば、符号化装置１０および復号装置２０は、同一の共有鍵としての行列ＴＨｉを利用して、処理を行う。このため、上述のような能動的な攻撃者に対して、高い堅牢性を実現できる。
【０１００】
また、この発明によれば、復号装置２０は、ネットワーク１５０から受信した乗算結果を、共有鍵としての行列ＴＨｉの逆行列と乗算し、この乗算結果を用いてＲＲＥ形行列を生成して、このＲＲＥ形行列に予め定められた部分行列が含まれているか否かにより、情報を復号できるか否かを判定する。また、情報を復号できないと判定した場合には、符号化装置１０に対して、上述の符号化および乗算をやり直させて乗算結果を再送させ、再送させた乗算結果を用いて上述の判定をやり直す。このため、ネットワーク１５０上で攻撃者が挿入してくる誤りパケットの最大数を予め想定することなく、情報を復号することができ、復号の失敗確率を小さくすることができる。
【０１０１】
＜第２実施形態＞
［情報伝送システム１Ａの構成］
本発明の第２実施形態に係る情報伝送システム１Ａについて、以下に説明する。情報伝送システム１Ａは、図１に示した本発明の情報伝送システム１とは、復号装置２０の代わりに復号装置２０Ａを備える点が異なる。なお、情報伝送システム１Ａにおいて、情報伝送システム１と同一構成要件については、同一符号を付し、その説明を省略する。
【０１０２】
［復号装置２０Ａの構成および動作］
図６は、復号装置２０Ａのブロック図である。復号装置２０Ａは、図４に示した本発明の第１実施形態に係る復号装置２０とは、ＲＲＥ演算器２３の代わりにＲＲＥ演算器２３Ａを備える点が異なる。
【０１０３】
ＲＲＥ演算器２３Ａは、ＲＲＥ演算器２３と同様に、乗算器２２により求められた第ｉステージにおける数式（１２）の行列を用いて、第ｉステージのReduced  Row  Echelon（ＲＲＥ）形行列を生成する。ただし、ＲＲＥ演算器２３Ａは、ＲＲＥ演算器２３とは、ＲＲＥ形行列の生成方法が異なる。
【０１０４】
具体的には、ＲＲＥ演算器２３Ａは、まず、乗算器２２により求められた数式（１２）の行列について、ｉ＝１からｉ＝ｉまでを行連結し、以下の数式（１７）に示す行列を求める。
【０１０５】
【数１７】
2014171020.tif 000019
【０１０６】
次に、上述の求めた数式（１７）の行列について行基本変形を行って、そのReduced  Row  Echelon形ＲＲＥ（Ｙ＾（ｉ））を求める。なお、行基本変形としては、例えば、Gauss-Jordanの掃き出し法を用いることができる。
【０１０７】
以上の情報伝送システム１Ａによれば、情報伝送システム１と同様の効果を奏することができる。
【０１０８】
なお、本発明の情報伝送システム１や情報伝送システム１Ａの処理を、コンピュータ読み取り可能な非一時的な記録媒体に記録し、この記録媒体に記録されたプログラムを情報伝送システム１や情報伝送システム１Ａに読み込ませ、実行することによって、本発明を実現できる。
【０１０９】
ここで、上述の記録媒体には、例えば、ＥＰＲＯＭやフラッシュメモリといった不揮発性のメモリ、ハードディスクといった磁気ディスク、ＣＤ−ＲＯＭなどを適用できる。また、この記録媒体に記録されたプログラムの読み込みおよび実行は、情報伝送システム１や情報伝送システム１Ａに設けられたプロセッサによって行われる。
【０１１０】
また、上述のプログラムは、このプログラムを記憶装置などに格納した情報伝送システム１や情報伝送システム１Ａから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネットなどのネットワーク（通信網）や電話回線などの通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【０１１１】
また、上述のプログラムは、上述の機能の一部を実現するためのものであってもよい。さらに、上述の機能を情報伝送システム１や情報伝送システム１Ａにすでに記録されているプログラムとの組み合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【０１１２】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計なども含まれる。
【０１１３】
例えば、上述の実施形態では、符号化装置１０の乗算器１２と、復号装置２０の乗算器２２とは、共通の共有鍵を複数種類記憶しており、ステージが変わるたびに、用いる共有鍵を予め定められたルールに従って更新するものとしたが、これに限らず、ステージが変わっても乗算器１２と乗算器２２とで同一の共有鍵を用いることができればよい。例えば、ネットワーク１５０とは別の安全な通信路で、ステージごとに用いる共有鍵を共有してもよい。共有する方法としては、例えば、第１ステージで用いる共有鍵のみを共有し、ステージが変わるたびに同期をとって、乗算器１２と乗算器２２とでそれぞれ更新してもよい。
【０１１４】
また、復号装置２０が正しく情報を復号できる場合に、復号装置２０は、復号完了通知を符号化装置１０に送信するものとしたが、これに限らず、例えば、復号装置２０は、正しく情報を復号できることを符号化装置１０に限らず公開するものとしてもよい。
【符号の説明】
【０１１５】
１、１Ａ、１００・・・情報伝送システム
１０、１１０・・・符号化装置
１１・・・符号化器
１２・・・乗算器
１３・・・送信器
１４・・・再送制御部
２０、２０Ａ、１２０・・・復号装置
２１・・・受信器
２２・・・乗算器
２３、２３Ａ・・・ＲＲＥ演算器
２４・・・判定器
２５・・・復号器
２６・・・再送要求部
１５０・・・ネットワーク
２００・・・攻撃者端末
【図１】
2014171020.tif 000020
【図２】
2014171020.tif 000021
【図３】
2014171020.tif 000022
【図４】
2014171020.tif 000023
【図５】
2014171020.tif 000024
【図６】
2014171020.tif 000025
【図７】
2014171020.tif 000026