その2 - Information and Coding

セキュアネットワーク符号化構成法
に関する研究
0530031 竹内裕介
指導教員小林欣吾栗原正純
2007/2/6(火)
発表内容
• ネットワーク符号化
• セキュアネットワーク符号化
• ベクトル空間への半順序関係の導入と
その極大元
• 効率よく極大元を求める方法
• シミュレーション実験結果
• 結論
2
ネットワーク符号化
F2  0,1
X 2  x1 , x2 
ネットワーク符号化とはAhlswedeら[1]
が提案した、ネットワークの内部ノードで
符号化を行うことで伝送可能な情報量
の限界を達成する方法
1
 
 0
v1
Liら[2]によって、ネットワーク符号化が
線形符号で達成できることが示された
1
 
 0
 0
 
1
v2
v3
1
 
 0
リンク上に列ベクトルを割り当て、情報源
から行ベクトルの情報を送信する
1
 
1
各リンクは情報ベクトルとリンクに割り当て
られた列ベクトルの積の値が送信される
 0
 
1
S
1
 
1
v4
 0
 
1
1
 
1
t2
t1
x1 , x2  
1 1
  x1 , x1  x2 
0
1


x1, x2  
1 0
  x1  x2 , x2 
1
1


3
セキュアネットワーク符号化
F3   1,0,1
X 2  S , R
Caiら[3]はネットワークに盗聴者の存在を仮
定し、盗聴される本数がある値以下であるな
ら情報理論的に安全であるネットワーク符号
化の構成法を示した
あつかう有限体のサイズを増やし、ベクト
ルの構成を右図のように変更する
1

S 1
R

v1
S  Fq と一様乱数 R  Fq
1
S 1
R
0
R
1
をネットワーク
1
S 1R
 
1
S 1 R
v3
1

S1R

情報源から等確率で生起する情報シンボル
S
0
R 
1
v4
v2
1
S 1 R
0
 
R
1
に送信する
t2
t1
どのリンクを盗聴しようと1本だけでは
情報シンボル
S を知ることはできない
S , R  
1 0
  S  R, R 

1
1


S , R  
0 1
  R, S  R 
1
1


4
セキュアネットワーク符号化
S1,, Shr , R1,, Rr  Fqh
S

k ( r ) 本のリンクが
盗聴される

ネットワーク



t


盗聴される本数が r 以下であるなら情報理論的に安全で、盗聴された
t1
t2
リンクの符号シンボルによって、情報シンボル
エントロピーは変化しない
n
S1 ,, Shr 
の情報
5
セキュアネットワーク符号化構成法
セキュアネットワーク符号化の安全性は暗号理論分野の秘密分散法
の考え方に基づいている
•ネットワーク符号化は与えられているものとする
•グラフを (V , E )、リンク
e E
•盗聴可能なリンクのうちの
とし、
に割り当てられたベクトルを
ge
とする
k 本のリンクベクトル集合を Gl (l  1,, N )
Gl  g l ,1 , g l , 2 ,  , g l , k 
rank [g l ,1 ,  , g l , k ]  kl
であるとする
6
セキュアネットワーク符号化構成法
次のような条件を満たすベクトル集合
B  b1 , b 2 ,, b hr 
を求め、
これを基にセキュア変換を行う。
条件：下図のように全ての組み合わせについて考えたとき、どの Gl に対しても
rank [b1 ,  , b h  r , g l ,1 , , g l ,k ]  h  r  kl
となる
B  b1 , b 2 ,, b h  r 
G1  g1,1 , g1, 2 , , g1, k 
G2  g 2,1 , g 2, 2 ,  , g 2, k 


GN  g N ,1 , g N , 2 ,  , g N , k 
7
セキュアネットワーク符号化構成法
B  b1 , b 2 ,, b h  r 
B  b1 ,, b hr , b hr 1 ,, b h  rank [b1 ,, b h ]  h
M  [b1 , , b h ]
1
の逆行列
がセキュアネットワーク符号化の線形変換行列となる
M
M
リンク
eに流れる符号シンボル W (g e ) が W (g e )  X h M 1  g e
となるように線形変換を行う
8
セキュアネットワーク符号化構成法
セキュアネットワーク符号化はベクトル集合 B を求めることが大きな
ポイントとなる
ネットワークのリンク全てが盗聴可能であるとすると、
パターンについて考えなくてはならない
E
N   
r
もの盗聴
しかし、ネットワーク符号化においては、盗聴パターンのベクトル
空間に多くの重複が見られる
9
ベクトル空間への半順序関係の導入
全空間 Fqh
ベクトル空間
Gi
ベクトル空間
Gj
Gi が G j の部分空間 (Gi  G j ) であるとき,
半順序関係 Gi  G j を定義する.
10
半順序関係と極大元
{g1 , g 2 , g 3} のベクトルによるすべての
組合せを考える
 1   0   0  
      
{g1 , g 2 , g 3 }   0 ,  1 ,  0  
 0   0   1  
      
Hasse図
{g1 , g 2 , g 3} によるベクトル空間は他の
{g1 , g 2 , g 3 }
集合によるベクトル空間を含んでいる
このとき {g1 , g 2 , g 3} を極大元と呼ぶ {g1 , g 2 }
極大元に対して一次独立なベクトルで
あれば、その他のベクトル空間に対し
ても一次独立であるといえる
{g1}
{g1 , g 3 }
{g 2 }
{g 2 , g 3 }
{g 3 }

11
例
 1   0 
   
{g1 , g 3 }   0 ,  0 
 0   1 
   
 1   1 
   
{g1 , g 4 }   0 ,  0 
 0   1 
   
 0   1 
   
{g 3 , g 4 }   0 ,  0 
 1   1 
   
 0   0 
   
{g 2 , g 3 }   1 ,  0 
 0   1 
   
 0   0 
   
{g 2 , g 5 }   1 ,  1 
 0   1 
   
 0   0 
   
{g 3 , g 5 }   0 ,  1 
 1   1 
   
 1   0   0   1   0 
         
{g1 , g 2 , g 3 , g 4 , g 5 }   0 ,  1 ,  0 ,  0 ,  1 
 0   0   1   1   1 
         
{g 3 , g 4 }
{g 3 , g 5 }
{g1, g4}
{g 2 , g 5 }
{g1, g2} {g1 , g3} {g1 , g5 } {g 2 , g3} {g 2 , g 4} {g 4 , g 5 }
{g1}
{g 2 } { g 3 } {g 4 } { g 5 }

12
効率よく極大元を求める方法
| E |
 
 r 
の組合せから一度に極大元を求めるのは大変
r   1 から r まで再帰的に
各段階の極大元を求める
| E |
 
 r 
r   1,2,  , r
13
組合せのリストアップ
5
C1 から 5 C 2 の組合せを全て書き出す
5
C1 {1},{2},{3},{4},{5}
5 C 2 {1,2},{1,3},{1,4},{1,5},
{2,3},{2,4},{2,5},
{3,4},{3,5},
{4,5}
 {1}
 {2}
 {3}
 {4}
14
組合せのリストアップ
5
C2
{1,2},{1,3},{1,4},{1,5},
{2,3},{2,4},{2,5},
{3,4},{3,5},
{4,5}
 {1}
5
C3
{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},
{2,3,4},{2,3,5},{2,4,5},
 {2}
{3,4,5}
 {3}
この手順で考えれば漏れなく全ての組合せについて考えている
15
極大元と組合せのリストアップ
{g1 , g 2 , g 3 , g 4 , g 5 , g 6 , g 7 } 
{1,2}
{1,3}
 {1}
{2,3}
{1,2}
{1,4}
{1,5}
{1,2}
{1,6}
{1,7}{1,3}
1   0   0  1   0   2   0 
             
 0  1   0  1   0   2   0 
 ,  ,  ,  ,  ,  ,  
 0   0  1   0  1   0   2 
             

 0   0   0   0  1   0   0 

ベクトルの添字のみの表記
{1,2}
{2, 4}
{3, 4}
{4,5}
{2,5}
{3,5}
{1,2}
{4,5}
{
3
,
4
}
{
1
,
2
}
{4,6}
{5,6}
{2,6}
{3,6}
{3,4}
{
3
,
5
}
{1,3} {4,7}{3,4} {5,7}
{6,7}
{2,7}{2,3} {3,7}
極大元に対してのみ組合せのリストアップをすればよい
16
シミュレーション実験結果
表：セキュアネットワークの構成時間 (ms)
network
C4
6 C4
7 C4
7 C4
7 C5
7 C5
7 C6
7 C6
5
|E|
r
組合せ
SNC0
SNC1
の総数
time(ms)
SNC２
29
3
3654
281
265
15
70
2
54740
2813
3359
78
151
2
11325
812
844
31
151
3
562475
-
-
47
117
2
6786
678
750
31
117
4
7413705
-
-
93
55
3
26235
3547
5734
125
55
5
3478761
-
-
125
17
結論
• セキュアネットワーク符号化構成の効率化
– ベクトル空間への半順序関係の導入
– 盗聴パターンに対する極大元の考慮
– 極大元を求めるアルゴリズムの提案
• シミュレーションによる実験
– 提案アルゴリズムの効果の確認
• 今後の課題
– しきい値以上の盗聴に対する構成[5]
18
参考文献
[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.
19

Download Report