Generalized Rank Weight of Linear Codes and Its
Application to Secure Network Coding
Ryutaroh MATSUMOTO1 (speaker)(jont work with Jun KURIHARA2 , andTomohiko UYEMATSU1 )
1 Tokyo Institute of Technology, Japan 2 KDDI Laboratories, Japan

Institute of Mathmatics for Industry Workshop
Kyushu University, Japan
March 2013
(Please ask your question at any time.)

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

1 / 32

Structure of this talk1

Review
Network coding
Secure network coding
Silva and Kschischang’s secure network coding

2

Definition of new parameters of linear codes and its meaning

3

Relation to known parameters

4

Conclusion

5

Appendix: Proofs of key theorems

6

Appendix: Application to secret sharing

7

Appendix: Extension to non-uniform distributions

Pp.21–32 are not included in the proceedings at your hand.
This slide is available at http://www.rmatsumoto.org/rgrw.pdf.
Note that itemizations and enumerations are somehow not printed in theproceedings.
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

2 / 32

Routing vs. network coding

We consider computer networks and wireless networks with multiple nodes.
Routing An intermediate node only forwards incoming data.
Network Coding (NC) An intermediate node combines data incoming fromits multiple links and jointly encodes them.
Advantages of NC are
Throughput can increase.
Optimal NC can be constructed easily while finding optimal routing is
NP-hard.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

3 / 32

Most famous example of NC — The butterfly network

NC multicasts 2 symbols to
2 sinks while routing canmulticast at most 1 symbol.
Linear processing works
well as the coding in NC.
Consider the single source multicast scenario (All sinks want the same
information). The maximum throughput is the minimum of max-flow
between the source and each sink.
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

4 / 32

Secure network coding
Assumptions:
single source multicast, andan adversary (Eve) can eavesdrop her chosen µ links in the network.
Goal: The legitimate users want to hide transmitted data from Eve.
The above problem and its solution were proposed as “secure network
coding” by Cai and Yeung (2002).
Relation to other areas:
Secure network coding is the network coding counterpart of the wiretap
channel coding initiated by Wyner (1975) and Csiszár-Körner (1978).
Secure network coding is a generalization of (threshold-type linear)secret sharing proposed by Shamir and Blakley (1979).

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

5 / 32

Secure network coding

Questions:
How does one model Eve’s observation?
How does one measure the amount of information obtained by Eve’s
observation?
I will review necessary materials to answer the above questions.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

6 / 32

Transfer matrix in linear network coding
Assume:single source multicast, linear processing at every node,
network can be modeled as an acyclic graph,delay can be ignored, or data generated by the source at the same time
are linearly combined,
the source node has n outgoing links,
m consecutive time slots are used for the source to send one packet, anda link can carry one GF(q) symbol per one time slot,
xij : GF(q) symbol at time j on the i-th outgoing link from the source.
Fix µ links e1 , . . . , eµ .
zij : GF(q) symbol at time j on ei .
Observation at time j = z1j  x1j 
 .  ..  = B  ...  , transfer matrix B ∈ GF(q)µ×n




zµj
xnj
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

7 / 32

Information leaked by Eve’s observation

Random variable S: (secret) message to legitimate receivers
Random variable Z: Eve’s (adversary’s) observation
Amount of information leaked in Eve’s observation= I(S; Z) = the mutual information between S and Z.
Special case: I(S; Z) = 0 ⇔ S and Z are statistically independent⇔ Having Z does not help guessing the value of S.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

8 / 32

Silva and Kschischang’s universal secure network coding
Silva and Kschischang (2011) proposed network coding that is1

secure2

error-correcting,3

and universal (working well with any transfer matrix)

by using
C2 $ C1 ⊆ GF(qm )n ,with C1 and C2 being MRD (maximum rank distance).

Questions
What is the security performance and the error correction capability
when C1 or C2 is not MRD?
What parameter of C1 and C2 exactly expresses the security and the error
correction capability?
I will answer those questions.
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. Coding
2013

9 / 32

Review of Silva and Kschischang (2011)
single source multicast (acyclic, delay-free)n: minimum of max-flows (' # outgoing links from the source)
m: time slots in a packet, m must be ≥ n for existence of MRD codes.
One GF(q) symbol is carried on a link per time slot
GF(q)-linear coding at all intermediate nodes
m × n GF(q) symbols in a packet.
C2 $ C1 ⊆ GF(qm )n : GF(qm )-linear (MRD) codes
A message is a coset ~a + C2 = {~a + ~x : ~x ∈ C2 } ∈ C1 /C2 , for ~a ∈ C1 .
|~a + C2 | = |C2 | for any ~a.
The number of messages is=

R. Matsumoto (Tokyo Tech.)|C1 | qm dim C1== qm(dim C1 −dim C2 ) .
|C2 | qm dim C2Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 10 / 32

Generation of a packet from a given message

C2 $ C1 ⊆ GF(qm )n : GF(qm )-linear (MRD) codes
S ∈ C1 /C2 : Given message
1
2

3

Randomly choose a vector ~x = (x1 , . . . , xn ) ∈ S $ GF(qm )n .
Expand xi ∈ GF(qm ) into (xi(1) , . . . , xi(m) ) ∈ GF(q)m by some fixed
GF(q)-linear basis of GF(qm ),(j)

Send xi on link i at time j.

Generation of ~x from S is called the nested coset coding.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 11 / 32

Roles of C1 and C2

C2 $ C1 ⊆ GF(qm )n : GF(qm )-linear (MRD) codes
A message is a coset ~a + C2 = {~a + ~x : ~x ∈ C2 } ∈ C1 /C2 .
C1 realizes the error correction. By not using vectors outside of C1 , error
correction becomes feasible. Setting C1 = GF(qm )n turns off the error
correction capability.
C2 realizes the secrecy of the message by randomizing it. Setting C2 = {0}removes the randomization and the secrecy of messages.
The same kind of message randomization is used in the wiretap channel
coding and the secret sharing for the same purpose.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 12 / 32

q-th power of subspaces (Stichtenoth (1990))~x = (x1 , . . . , xn ) ∈ GF(qm )n ,qq~xq = (x1 , . . . , xn ).
V q = {~xq : ~x ∈ V} for an GF(qm )-linear subspace V of GF(qm )n .
V q is again an GF(qm )-linear subspace despite ~x 7→ ~xq is GF(qm )-nonlinear.
23
m−1
V∗ = V + Vq + Vq + Vq + · · · + Vq .
Γ = {V ⊆ GF(qm )n : V is GF(qm )-linear and V q = V}1

2

For an GF(qm )-subspace V ⊆ GF(qm )n , V q = V iff V has an
GF(qm )-basis written in GF(q)n ,V ∗ is the smallest GF(qm )-space in Γ containing V.

The above were given by Stichtenoth (1990) for studying subfield subcodes.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 13 / 32

j-th Relative Generalized Rank Weight (RGRW)For C2 $ C1 ⊆ GF(qm )n ,Mj (C1 , C2 ) = min{dim V : V ∈ Γ, dim C1 ∩ V − dim C2 ∩ V ≥ j}
= min{dim V : V ∈ Γ, dim C1 ∩ V − dim C2 ∩ V = j}
Eve creates a network of arbitrary shape and choose arbitrary µ links toobserve.
Z: observed information, S: secret message (uniform distribution)

Relation between RGRW and eavesdropped information
max I(S; Z) in logqm ≥ j ⇔ µ ≥ Mj (C2⊥ , C1⊥ )The maximum is taken over all shapes of network and all choices of µ links.

CorollaryIf µ < M1 (C2⊥ , C1⊥ ) then there is no information leakage.
I will explain why “rank” is included in its name.
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 14 / 32

Review of Gabidulin’s rank weight

Recall C2 $ C1 ⊆ GF(qm )n
The rank weight is related to error correction for network coding.
The legitimate receiver can correct errors occurred at arbitrary t links ⇐ theminimum rank weight of C1 is ≥ 2t + 1.
~x = (x1 , . . . , xn ) ∈ GF(qm )n ,P
hx1 , . . . , xn i = { ni=1 ai xi : ai ∈ GF(q)} ⊂ GF(qm ).
wR (~x) = Gabidulin’s rank weight = dimGF(q) hx1 , . . . , xn i
The minimum rank weight dR (C1 ) of C1 = min{wR (~x) | ~0 , ~x ∈ C1 }.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 15 / 32

Relation to Gabidulin’s rank weight

Recall C2 $ C1 ⊆ GF(qm )n
The proposed 1st RGRW M1 (C1 , C2 ) is related to wR as
M1 (C1 , C2 ) = min{wR (~x) : ~x ∈ C1 \ C2 }.
M1 (C1 , {~0}) = the minimum rank weight dR (C1 ) of C1 .
RGRW generalizes Gabidulin’s rank weight.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 16 / 32

Relation to (relative) generalized Hamming weightI ⊆ {1, . . . , n}
VI = {~x ∈ GF(qm )n : xi = 0 if i < I}
dim VI = |I|C1 ∩ VI is the shortened code of C1 to the index set I.
j-th generalized Hamming weight (GHW) of C1 ⊆ GF(qm )n= min{dim VI : dim C1 ∩ VI ≥ j} (V.K. Wei (1991))
j-th relative generalized Hamming weight (RGHW) of C2 $ C1 ⊆ GF(qm )n= min{dim VI : dim C1 ∩ VI − dim C2 ∩ VI ≥ j} (Luo et al. (2005))
Recall that RGRW was
Mj (C1 , C2 ) = min{dim V : V ∈ Γ, dim C1 ∩ V − dim C2 ∩ V ≥ j}.
The difference between RGRW and RGHW is the set of intersecting
subspaces. Our naming of RGRW follows the conventions set by Gabidulinand Luo et al.
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 17 / 32

Error correction and RGRW

Fix single sink with N incoming links.
A ∈ GF(q)N×n : transfer matrix from the source to the sink
The sink knows A (coherent network error correction)t broken links inject erroneous symbols from time 1 to m.
The sink can correct any t link errors with any A of rankA ≥ n − ρ iff
M1 (C1 , C2 ) > 2t + ρ.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 18 / 32

Summary
j-th relative generalized rank weight Mj (C1 , C2 ) was introduced for
C2 $ C1 ⊆ GF(qm )n .
max I(S; Z) ≥ j ⇔ the number of eavesdropped link ≥ Mj (C2⊥ , C1⊥ ).
C2 $ C1 can correct t link errors and ρ rank deficiency iff
2t + ρ < M1 (C1 , C2 ).
RGRW is a generalization of Gabidulin’s rank weight and is related to
Luo et al.’s relative generalized Hamming weight.
All proofs are available from arXiv:1207.1936 or the final version of theAllerton 2012 conference proceedings arXiv:1301.5482. The GRW (without
the 1st R) was also concurrently and independently introduced in
F. Oggier and A. Sboui, “On the existence of generalized rank weights," inProc. ISITA 2012, Honolulu, Hawaii, USA, Oct. 2012, pp. 406–410.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 19 / 32

What can be done next?

By this result, we can evaluate the error correction capability and the securityof any C2 $ C1 . I expect that more convenient C2 $ C1 exist, e.g. with smaller
m of GF(qm ) (for MRD C1 , C2 , m must be ≥ n).
This direction of research was also pointed out by M. Médard at Q&A of theAllerton conference, but our investigation has not started.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 20 / 32

Proof sketch: the relation between secrecy and dimension 1
Random variable S ∈ C1 /C2 : Given message
Random variable X ∈ S ⊂ GF(qm )n : transmitted codeword (or packet)
B ∈ GF(q)µ×n : a fixed transfer matrix
Assumption: X and S are uniformly distributed.
⇒ As an RV, X can take any vector in C1 .
I(BX; S) = H(BX) − H(BX|S)The uniformity assumption implies
H(BX) = logqm the number of possible BX= logqm |image of map X 7→ BX|= dim C1 − dim(C1 ∩ ker(B))
ker(B) as a linear map from GF(qm )n to GF(qm )µ .

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 21 / 32

Proof sketch: the relation between secrecy and dimension 2I(BX; S) = H(BX) − H(BX|S)The uniformity assumption also implies
H(BX|S) = logqm the number of possible BX given S = s= logqm the number of possible BX given S = C2
= logqm |image of map S → BS|= dim C2 − dim(C2 ∩ ker(B))⇒ I(BX; S) = dim C1 − dim C2 − (dim(C1 ∩ ker(B)) − dim(C2 ∩ ker(B))).

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 22 / 32

Extension of Forney’s second duality lemma

For any space V ⊂ GF(qm )n we have
dim C1 ∩ V − dim C2 ∩ V = dim C1 /C2 − dim(C2⊥ ∩ V ⊥ ) + dim(C1⊥ ∩ V ⊥ ).
Substituting the above extension of Forney’s lemma into
I(BX; S) = dim C1 − dim C2 − (dim(C1 ∩ ker(B)) − dim(C2 ∩ ker(B)))
yieldsI(BX; S) = dim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ ).

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 23 / 32

Universality leads RGRW
For a fixed B ∈ GF(q)µ×n , we have
I(BX; S) = dim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ ).
The universal security deals with all B ∈ GF(q)µ×n :max

I(BX; S)maxdim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ )maxdim(C2⊥ ∩ V) − dim(C1⊥ ∩ V)

B∈GF(q)µ×n==

B∈GF(q)µ×nV∈Γ,dim V≤µ(by the 1st item in p.13)
RecallMj (C2⊥ , C1⊥ ) = min{dim V : V ∈ Γ, dim C2⊥ ∩ V − dim C1⊥ ∩ V ≥ j}
= min{dim V : V ∈ Γ, dim C2⊥ ∩ V − dim C1⊥ ∩ V = j}
Claims in p.14 follow from the above.
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 24 / 32

Some remarks on the proof argument

One can remove all the assumptions on the probability distributions of S
and X, which make the proof more complicated.
One can deduce the relation between secret sharing and RGHW by
restricting the set of matrices B.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 25 / 32

Threshold-type linear secret sharing
Goal: Distribute a secret S to n participants so thatAny α or more participants can recover S, andAny β or less participants have NO information on S.
We need to evaluate α and β.
Coding method:C2 ⊂ C1 ⊂ GF(q)nS ∈ C1 /C2 : Given secret
S 3 X = (x1 , . . . , xn )T : randomly chosen vector
xi is distributed to the i-th participant.

Recoverability
Recovery of S by a subset of n participants is equivalent to the erasure
decoding by the subset of participants for C1 /C2 . Recoverability iscompletely determined by the coset distance (= 1st RGHW) of C1 /C2(Duursma and Park 2010).
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 26 / 32

Information gained by fixed µ participantsC2 ⊂ C1 ⊂ GF(q)nS ∈ C1 /C2 : Given secret
S 3 X = (x1 , . . . , xn ): randomly chosen vector
Fixed µ participants have (xi1 , . . . , xiµ ).
B ∈ GF(q)µ×n such that (xi1 , . . . , xiµ )T = BX. Every entry in B is either 0 or 1.
I(BX; S) = dim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ ).
On the other hand, ker(B)⊥ = VI with I = {i1 , . . . , iµ }.
⇒ I(BX; S) = dim(C2⊥ ∩ VI ) − dim(C1⊥ ∩ VI ).
Recall VI = {~x ∈ GF(q)n : xi = 0 if i < I}.

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 27 / 32

Worst-case information gain by arbitrary µ participants

maxB is taken over all possible combinations of µ participants.
max I(BX; S)
B= max dim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ )B= max dim(C2⊥ ∩ VI ) − dim(C1⊥ ∩ VI )|I|≤µRecall that j-th RGHW of C2⊥ and C1⊥= min{dim VI : dim C2⊥ ∩ VI − dim C1⊥ ∩ VI ≥ j}
The above leads to . . .

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 28 / 32

Secret sharing and RGHW
Z: shares of arbitrary µ participants, S: secret (uniform distribution)

Relation between RGHW and Z
max I(S; Z) in logqm ≥ j ⇔ µ ≥ j-th RGHW of C2⊥ and C1⊥
The maximum is taken over all choices of µ participants.

CorollaryIf µ < 1st RGHW (= coset distance) of C2⊥ and C1⊥ then there is no
information leakage of S into Z.
The above were reported at J. Kurihara et al.,
http://dx.doi.org/10.1587/transfun.E95.A.2067

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 29 / 32

Extension to non-uniform distributions

S: secret message, X: transmitted packet (codeword)(S, X) are often assumed to be uniformly distributed.
Zhang and Yeung considered artibrary distributions of (S, X) (ISIT 2009).
For extension of our result, evaluation of I(BX; S) for a fixed B is enough. For
any B ∈ B and A ∈ A(B) ⊂ A,
H(A) = log |A| − D(AkUA ) (see an information theory textbook),
H(A|B) = EB [log |A(B)|] − D(AkUA(B) |B) (similarly shown as above).
When B = b, possible realizations of A is narrowed to A(b) ⊂ A.
UA(B) : RV conditionally uniform on A(B) given B.
By using the above, . . .

R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 30 / 32

Extension to non-uniform distributions (contd.)
H(A) = log |A| − D(AkUA ),H(A|B) = EB [log |A(B)|] − D(AkUA(B) |B)
give
H(S) = dim C1 /C2 − D(SkUC1 /C2 ),H(X|S) = dim C2 − D(XkUS |S),..
.
By using the above, one has, for a fixed B,
dim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ ) − D(SkUC1 /C2 )≤ I(BX; S)≤ dim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ ) + D(XkUS |S).
D(SkUC1 /C2 ) quantifies the non-uniformity of S, while
D(XkUS |S) quantifies the conditional non-uniformity of X given S.
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 31 / 32

Extension to non-uniform distributions (contd.)dim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ ) − D(SkUC1 /C2 )≤ I(BX; S)≤ dim(C2⊥ ∩ ker(B)⊥ ) − dim(C1⊥ ∩ ker(B)⊥ ) + D(XkUS |S).
D(SkUC1 /C2 ) quantifies the non-uniformity of S, while
D(XkUS |S) quantifies the conditional non-uniformity of X given S.
Non-uniform S may decrease Eve’s information I(BX; S),
while conditionally non-uniform X given S may increase I(BX; S).
One can remove all the assumptions on distributions of S and X in this talk.
All mathematical claims and proofs are available as arXiv:1301.5482.
This slide is available at http://www.rmatsumoto.org/rgrw.pdf.
R. Matsumoto (Tokyo Tech.)

Generalized Rank Weight of Linear Codes and Its Application to Secure Network
Mar. 2013
Coding 32 / 32