セキュアネットワーク符号化構成法に関する研究 0530031　竹内裕介 指導教員　小林欣吾　栗原正純 2007/2/6(火)

発表内容 ネットワーク符号化 セキュアネットワーク符号化 ベクトル空間への半順序関係の導入と その極大元 効率よく極大元を求める方法 シミュレーション実験結果 結論

ネットワーク符号化 ネットワーク符号化とはAhlswedeら[1]が提案した、ネットワークの内部ノードで符号化を行うことで伝送可能な情報量の限界を達成する方法 S Liら[2]によって、ネットワーク符号化が線形符号で達成できることが示された リンク上に列ベクトルを割り当て、情報源から行ベクトルの情報を送信する 各リンクは情報ベクトルとリンクに割り当てられた列ベクトルの積の値が送信される

セキュアネットワーク符号化 Caiら[3]はネットワークに盗聴者の存在を仮定し、盗聴される本数がある値以下であるなら情報理論的に安全であるネットワーク符号化の構成法を示した S あつかう有限体のサイズを増やし、ベクトルの構成を右図のように変更する 情報源から等確率で生起する情報シンボル 　　　　　と一様乱数　　　　　　をネットワーク に送信する どのリンクを盗聴しようと1本だけでは 情報シンボル　　を知ることはできない

セキュアネットワーク符号化 S 　　　　　本のリンクが盗聴される ネットワーク 盗聴される本数が　　以下であるなら情報理論的に安全で、盗聴されたリンクの符号シンボルによって、情報シンボル　　　　　　　　　　　の情報エントロピーは変化しない

セキュアネットワーク符号化構成法 セキュアネットワーク符号化の安全性は暗号理論分野の秘密分散法の考え方に基づいている ネットワーク符号化は与えられているものとする グラフを　　　　　、リンク　　　　　に割り当てられたベクトルを　　　とする 盗聴可能なリンクのうちの　　本のリンクベクトル集合を　　　　　　　　　　とし、 であるとする

セキュアネットワーク符号化構成法 条件：下図のように全ての組み合わせについて考えたとき、どの に対しても となる 次のような条件を満たすベクトル集合　　　　　　　　　　　　　　　　　　　　　　　　　を求め、 これを基にセキュア変換を行う。 条件：下図のように全ての組み合わせについて考えたとき、どの　　 に対しても 　　　　となる

セキュアネットワーク符号化構成法 の逆行列 がセキュアネットワーク符号化の線形変換行列となる リンク に流れる符号シンボル が 　　の逆行列　　　がセキュアネットワーク符号化の線形変換行列となる リンク　　に流れる符号シンボル　　　　　が となるように線形変換を行う

セキュアネットワーク符号化構成法 セキュアネットワーク符号化はベクトル集合 を求めることが大きなポイントとなる セキュアネットワーク符号化はベクトル集合　　を求めることが大きなポイントとなる ネットワークのリンク全てが盗聴可能であるとすると、　　　　　　　　　　もの盗聴パターンについて考えなくてはならない しかし、ネットワーク符号化においては、盗聴パターンのベクトル空間に多くの重複が見られる　

ベクトル空間への半順序関係の導入 全空間 ベクトル空間 ベクトル空間 　　が　　の部分空間　　　　　　であるとき, 半順序関係　　　　　　　を定義する.

半順序関係と極大元 このとき を極大元と呼ぶ 極大元に対して一次独立なベクトルであれば、その他のベクトル空間に対しても一次独立であるといえる 　　　　　　　　　　のベクトルによるすべての組合せを考える 　　　　　　　　　　によるベクトル空間は他の集合によるベクトル空間を含んでいる このとき　　　　　　　　　を極大元と呼ぶ 極大元に対して一次独立なベクトルであれば、その他のベクトル空間に対しても一次独立であるといえる Hasse図

例

効率よく極大元を求める方法 の組合せから一度に極大元を求めるのは大変 　　　　　から　　まで再帰的に 各段階の極大元を求める

組合せのリストアップ 　　から　　　の組合せを全て書き出す

組合せのリストアップ この手順で考えれば漏れなく全ての組合せについて考えている

極大元と組合せのリストアップ ベクトルの添字のみの表記 極大元に対してのみ　組合せのリストアップをすればよい

シミュレーション実験結果 表：セキュアネットワークの構成時間 (ms) 組合せ SNC0 SNC1 SNC２ time(ms) 29 3 　network 組合せ SNC0 SNC1 SNC２ 　の総数 time(ms) 29 3 3654 281 265 15 70 2 54740 2813 3359 78 151 11325 812 844 31 562475 　- 47 117 6786 678 750 4 7413705 93 55 26235 3547 5734 125 5 3478761

結論 セキュアネットワーク符号化構成の効率化 シミュレーションによる実験 今後の課題 ベクトル空間への半順序関係の導入 盗聴パターンに対する極大元の考慮 極大元を求めるアルゴリズムの提案 シミュレーションによる実験 提案アルゴリズムの効果の確認 今後の課題 しきい値以上の盗聴に対する構成[5]

参考文献 [1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Trans. Inform. Theory, vol. 46, pp. 1204–1216, July 2000. [2]S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Trans. Inf. Theory, vol. 49, no. 2, pp. 371–381, Feb. 2003. [3]Cai and R. W. Yeung “Secure Network Coding” ISIT ’02, June 2002 [4]栗原正純, “セキュアネットワーク符号化”アルゴリズム　－条件付正則行列の構成アルゴリズム(I)－”, Proc. SITA2006, Hokkaido, pp.763-766, Nov. 2006. [5]原田邦彦, 山本博資, “強いランプ型しきい値特性を持つ安全なネットワーク符号化法”, Proc. SITA2005, Okinawa, pp.741-744, Nov. 2005.

セキュアネットワーク符号化 S S この2本を盗聴すると　　が 復号できる どの2本の組み合わせからも 　　は復号できない　

S

network グラフの情報 5C4 |E|=29 h=4 r=3 29C3=3654 極大元の数:10 6C4 |E|=70 r=2 70C3=54740 極大元の数:26 7C4 |E|=151 151C2=11325 極大元の数:32 151C3=562475 極大元の数:47 7C5 |E|=117 h=5 r=2 117C2=6786 極大元の数:41 r=4 117C4=7413705 極大元の数:57 7C6 |E|=55 h=6 r=3 55C3=26235 極大元の数:84 r=5 55C5=3478761 極大元の数:21

実験結果