盗聴・改ざんに対して耐性を持つ ネットワーク符号化について 堀井 俊佑 松嶋 敏泰 平澤 茂一 早稲田大学
発表内容 研究背景・研究の位置づけ （線形）ネットワーク符号 従来研究：ネットワーク誤り訂正符号とセキュアなネットワーク符号 盗聴・改ざんに対して耐性を持つネットワーク符号 まとめと今後の課題
１．研究背景・研究の位置づけ ネットワーク符号 リレーが符号化をすることで，ルーティングよりも効率良くマルチキャストできる [Ahlswede et al. 2000] 送信者（単一） 複数のリレー 受信者（複数）
１．研究背景・研究の位置づけ 本研究 ネットワーク符号のセキュリティへの応用 攻撃者が盗聴と改ざんを同時に行う問題 セキュアなネットワーク符号化 [Cai et al. 2002],[Feldman et al. 2004],[原田ら 2005] ネットワークに盗聴者の存在を仮定 盗聴される通信路の本数がしきい値以下ならば情報理論的に安全なネットワーク符号の構成 改ざんに対して安全なネットワーク符号化 [Yeung et al 2006],[Matsumoto 2007] 通信路上を流れるシンボルが改ざんされる ネットワーク誤り訂正の問題と等価 改ざんされたシンボルがしきい値以下ならば受信者が情報を復元できるネットワーク符号の構成 本研究 攻撃者が盗聴と改ざんを同時に行う問題 主結果：レートに関する必要十分条件の導出
2．ネットワーク符号 ネットワーク符号の数学的記述 中間ノードで符号化操作をすることで，ルーティングより高いレートを達成可能 情報源ノード 受信 ノード 中間ノードで符号化操作をすることで，ルーティングより高いレートを達成可能
3．線形ネットワーク符号
3．線形ネットワーク符号の構成アルゴリズム [Li et al. 2003] [Jaggi et al. 2005]：
3．線形ネットワーク符号の構成アルゴリズム 任意のカットに含まれるエッジに割り当てられた符号化ベクトルが線形独立になるように
3．線形ネットワーク符号の構成アルゴリズム Step１： Step2：
3．線形ネットワーク符号の構成アルゴリズム Step3：
4．従来研究 ネットワーク誤り訂正 構成法： [Yeung et al 2006] [Matsumoto 2007]
4．従来研究 セキュアなネットワーク符号 [Cai et al. 2002]
4．盗聴・改ざんを考慮したネットワーク符号 モデル 攻撃者：使用されているネットワーク符号は完全に知っている 攻撃者は，ネットワーク内の t 本のエッジを 盗聴可能 改ざん可能 送信者： 安全基準 1． 2．
4．盗聴・改ざんを考慮したネットワーク符号 主結果 必要条件 十分条件
4．盗聴・改ざんを考慮したネットワーク符号 メッセージの集合
4．盗聴・改ざんを考慮したネットワーク符号 符号化ベクトル割り当て時の条件 初期条件 変数の追加 変数の更新
攻撃者が盗聴と改ざんを行うネットワーク符号化の問題において安全になるためのレートの必要十分条件を導出した 5．まとめと今後の課題 攻撃者が盗聴と改ざんを行うネットワーク符号化の問題において安全になるためのレートの必要十分条件を導出した 必要な有限体のサイズの評価 より効率的な符号の構成法 受信ノードが1つの場合，問題は1-roundのsecure message transmission scheme（SMTS）の問題と等価 SMTSにおける結果の応用 受信ノードから送信ノードへのフィードバックが存在する場合の 符号化⇒情報源ノードが複数存在する場合のネットワーク符号
付録