Ahlswede-Cai-Li-Yeungによって提案されたネットワーク符号化は,ネットワークの各点で符号化を行える場合を考え,情報を送信する情報源点と情報を受信する受信点の間により多くの情報を伝送するための符号化に関する研究分野である.コンピュータネットワークなど,情報通信網は複数の通信路と通信路を結ぶ節点をネットワークとしてモデル化できる.特に1個の情報源点から複数個の受信点へと完全に同一の情報を伝送する通信問題はマルチキャスト通信と呼ばれ,この通信問題に対しては伝送可能な情報量の上限がネットワークフローにおける各受信点に対する最大フローの最小値で与えられることが知られている.また,この上限を達成する符号は線形ネットワーク符号化で構成できることが知られている.以下では,マルチキャスト通信で伝送可能な最大の情報量を で表す.図 1に,マルチキャスト通信におけるネットワーク符号の一例を示す.例では,点 において符号化を行うことで,情報源点 から2個の受信点 に長さ2の情報 の情報伝送を可能にしている.

一方で,ノンマルチキャスト通信に対する伝送可能な情報量の領域に関しては,ほとんどが未解決問題となっているが,厳密な領域が示されている問題の一つに,1個の情報源点から2個の受信点への一般の通信問題がある.この問題では,2個の受信点の各々に対する個別情報と両方の受信点に対する共通情報を考えれば十分である.これらの各情報量を とする.この領域に含まれる任意の情報量を持つ情報を伝送可能な符号も線形ネットワーク符号化で構成できることが知られている.しかし,既存の研究で示されている符号構成手法は としたマルチキャスト通信問題に帰着する証明的手法で,実用的に使いやすい符号とは言えなかった.

本論文では,ネットワークに盗聴者が介在する場合に,情報を秘匿して伝送可能な線形ネットワーク符号化を扱った.ここでの情報秘匿特性は,情報量的安全性によるものであり,将来にわたって安全であることが保証されない計算量的安全性によるものではない.また,各点があらかじめ暗号化のための共通鍵を秘密に共有している仮定もおかない.本論文の成果を以下にまとめる.

まず,第3章では第一に,マルチキャスト通信に対して情報秘匿特性を持つ安全な線形ネットワーク符号を提案した.同じ方向性を持つ先行研究として,長さ の秘密情報 を伝送するとき,ネットワークの任意の 本以下の枝を盗聴されても に関する情報が全く漏洩しないという情報秘匿を扱ったものがある.この場合には, であることが秘匿して伝送可能な必要十分条件であることが知られている.本論文では,この情報秘匿特性をweakly -secureと呼び,これをさらに強めた情報秘匿であるstrongly -secureを定義した.Strongly -secureな情報秘匿は, -secureであり,かつ に対して 本の枝を盗聴されても,秘密情報の任意の シンボルが完全に漏洩しない手法である.本論文では,strongly -secureな情報秘匿を達成できる必要十分条件もまた であることを導出した.具体的には,この条件が満たされた場合に対して,strongly -secureな2つの符号構成アルゴリズムを示した.1つは符号構成時に直接安全となるように符号を構成する手法であり,もう1つは既存の安全とは限らない線形ネットワーク符号を線形変換することによる手法である. は,非線形符号を用いた場合にも導出できる上界であり, を達成できないという意味で,本論文による手法よりも効率の良い符号化手法は存在しない. 図 1の符号例を用いて,weakly 1-secureな情報秘匿とstrongly 0-secureな情報秘匿の2つの例を示す.Weakly 1-secure な情報秘匿を行って秘密情報 を伝送するには,一様乱数情報 を用意し, として伝送すればよい.このとき,任意の1本の枝を盗聴されたとしても,(アルファベットサイズが3以上であれば) に関する情報は全く漏洩しない.これに対し,strongly 0-secureに秘密情報 を秘匿して伝送するには, として伝送すればよい.このとき,任意の1本の枝が盗聴されたとしても,(アルファベットサイズが4以上であれば) の線形関係は漏れるが,それぞれの値は全く漏洩することはない.このように,strongly 0-secureな情報秘匿は, の場合でも安全性が意味を失わない符号となる.しかも,この例では,weakly 1-secure に伝送する と同程度の情報秘匿を達成しながら,strongly 0-secureでは2個の秘密シンボルを伝送することができている.

第3章では第二に,strongly -secureな線形ネットワーク符号が存在するために必要な有限体アルファベットサイズを議論した.線形ネットワーク符号はその計算の利便性から,アルファベットとして有限体を用いることが多い.そのサイズは実用上できるだけ小さいことが求められるが,あまり小さくすると符号が構成できなくなってしまう.そこで,符号が存在するために必要なアルファベットサイズを評価する必要がある.符号に課す制約が増えることから,情報秘匿しない場合よりもweakly -secureに構成する場合の方が,またそれよりもstrongly -secureに構成する場合の方がより大きい有限体を必要とする.実際に,有限体のサイズを評価し,この事実を確認した.また,weakly -secureの場合に対して示されたものと同じように, と とのギャップを大きくすればするほど指数的に小さな有限体をアルファベットとして用いることができることを示した.

第3章では第三に,ネットワークの余剰なリソースを利用して情報秘匿を達成する手法を提案した.Weakly -secureやstrongly -secureに秘密情報を秘匿して伝送する場合,情報源点と受信点との間のマルチキャスト通信だけを利用すると,大きくても の情報量を持つ秘密情報しか伝送することができない.しかし,一般にはこのマルチキャスト通信には利用していない通信リソースが多くある.これを利用して安全なネットワーク符号を構成することを考えた.具体的には,以下のように書ける.元のネットワークの問題にある変換を行った通信問題でのマルチキャスト容量が (必ず となる)であるとする.このとき,情報量 を持つ秘密情報をweakly -secureあるいはstrongly -secureに秘匿する符号を構成できることを示した.視点を変え, -secureな情報秘匿の を固定して考えれば,秘匿して伝送可能な秘密情報量は である.

第4章では,1個の情報源点から2個の受信点に個別情報と共通情報を伝送する問題に対して,その3つの情報(各々の受信点に対する個別情報と共通情報)を伝送するルートを完全に分離できる分離符号化が可能なことを,具体的な構成法を示すことにより証明した.分離符号化を用いると,情報量 を持つ個別情報はそれぞれ符号化を行わずルーティングで伝送し,情報量 を持つ共通情報は としたマルチキャスト通信で伝送することができる.また,既存手法より符号化を行う点を減すことができ,その結果小さい次元で符号化を行え,符号化の計算量を減すことができる.既存手法による符号化手法には,マルチキャスト通信に対して提案した安全なネットワーク符号をそのまま応用することができなかったが,分離符号化を用いればそのままに適用できることを示した.さらに,安全なネットワーク符号化を含めたさまざまな機能を持つ任意の符号化をそのまま適用可能である.本論文では,この適用を行った場合に対し,符号化の実現のために必要な有限体アルファベットサイズの評価も行った.

以上のように,本論文では既存の手法に比べより強い情報秘匿特性をネットワーク符号に導入し,その効率化を図った.また,既存の手法はマルチキャスト通信にしか応用できない符号であったが,より広い通信のクラスに対して情報秘匿特性を導入することに成功した.

本論文は、「安全な線形ネットワーク符号化」と題し、5章から構成されている。インターネットを始めとするコンピュータネットワークでは、通信路とその接続点であるコンピュータをそれぞれ枝と点としてモデル化するとき、各点において情報の符号化/復号化を行なうことができる。そのような符号化はネットワーク符号化と呼ばれ、符号化を行なわない場合に比べて、ネットワークを通してより多くの情報を伝送することが可能となる。本論文では、盗聴者がネットワークの幾つかの枝を盗聴する場合でも安全に情報が伝送できるネットワーク符号の構成法を取り扱っており、これらに対して新しい知見を与えている。

第1章「序論」では、ネットワーク符号に対する研究の背景と目的を述べると共に、従来研究に対する本研究の位置付けを与えている。また、本論文の構成を示している。

第2章「ネットワーク符号化」では、従来知られているネットワーク符号に関する重要な知見をまとめている。具体的には、全ての受信点に同じ情報を伝送するマルチキャスト通信に対して、伝送可能な情報量の上限を与える符号化定理、その上限を達成する線形ネットワーク符号の構成方法、その符号化に必要な有限体サイズなどの既知の結果をまとめている。

第3章「盗聴者に対して安全なマルチキャスト通信」では、マルチキャストネットワーク符号化おいて、枝に盗聴者が存在しても安全に情報が伝送可能となるネットワーク符号について論じている。ある閾値以下の本数の枝が盗聴されても、伝送している情報が全くもれないネットワーク符号化法は既に知られているが、従来の符号化法では閾値以上の本数の枝が盗聴されたときに、伝送している情報の一部が完全に盗聴者に漏洩する危険があった。それに対して、本論文では、閾値以上の本数の枝が盗聴されても、盗聴者に対して全情報の曖昧さは減少して行くものの、一部の情報が完全に漏洩することのない強い情報秘匿特性を定義し、その実現法を明らかにしている。具体的には、強い情報秘匿特性を線形符号で実現するためのネットワーク符号構成法を与えると共に、安全でない線形ネットワーク符号を利用して、強い情報秘匿特性を実現するための線形変換法を与えている。その結果、強い情報秘匿特性を実現する場合でも、従来の弱い情報秘匿特性の場合と同じ情報量を、ネットワークを通して伝送可能なことを明らかにしている。さらに、強い情報秘匿特性を持つネットワーク符号を実現するために必要な有限体サイズを評価している。また、直接ネットワーク符号化で利用していないネットワーク内の余剰な枝を利用することにより、さらに多くの情報を安全に伝送可能なことを示し、その伝送可能な情報量を与えている。

第4章「個別情報と共通情報の分離符号化と安全な符号化への応用」では、2つの受信点に共通情報を送ると共に各受信点にそれぞれ個別情報を送る一般の通信問題を取り扱っている。従来知られているネットワーク符号化法では、個別情報と共通情報を分離して符号化できないため、第3章で取り扱ったような情報秘匿特性を実現することができない。本論文では、2つの個別情報と共通情報を伝送するパスをネットワーク上で完全に分離し、かつ伝送可能な情報量の上限を線形ネットワーク符号で実現できることを、具体的な符号構成アルゴリズムを与えることにより証明している。この結果、2つの個別情報はネットワーク符号化を行なうことなくルーティングだけで伝送でき、共通情報はマルチキャスト通信用のネットワーク符号を利用すれば実現できる。さらに、第3章で示した情報秘匿特性を、2つの個別情報と共通情報にそれぞれ独立に安全性パラメータを設定して適用することが可能となっている。また、必要な有限体サイズも従来方式に比べて小さくなる特長がある。

第5章「結論」では、本論文の成果をまとめると共に、今後の研究課題を示している。

以上を要するに、本論文は、情報理論やグラフ理論などの数理情報学的手法を用いることにより、より安全で性能のよいネットワーク符号の構成法を明らかにしており、その成果は、数理情報学分野、特にネットワーク符号および暗号情報セキュリティ分野における理論研究の進歩に大きく貢献している。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。