On the Security of Index Coding With Side Information
Authors:
- 9 March 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 58 (6) , 3975-3988
Abstract
Security aspects of the index coding with side information (ICSI) problem are investigated. Building on the results of Bar-Yossef (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrix L, whose column space code C(L) has length n, minimum distance d , and dual distance d⊥ , is (d-1-t) -block secure (and hence also weakly secure) if the adversary knows in advance t ≤ d-2 messages, and is completely insecure if the adversary knows in advance more than n - d⊥ messages. Strong security is examined under the conditions that the adversary: 1) possesses t messages in advance; 2) eavesdrops at most μ transmissions; 3) corrupts at most δ transmissions. We prove that for sufficiently large q , an optimal linear index code which is strongly secure against such an adversary has length κq+μ+2δ . Here, κq is a generalization of the min-rank over Fq of the side information graph for the ICSI problem in its original formulation in the work of Bar-Yossef et al.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- On the Index Coding Problem and Its Relation to Network Coding and Matroid TheoryIEEE Transactions on Information Theory, 2010
- Universal weakly secure network coding2009
- Broadcasting with Side Information2008
- XORs in the Air: Practical Wireless Network CodingIEEE/ACM Transactions on Networking, 2008
- Efficient algorithms for Index Coding2008
- An algebraic approach to network codingIEEE/ACM Transactions on Networking, 2003
- Network information flowIEEE Transactions on Information Theory, 2000
- The intractability of computing the minimum distance of a codeIEEE Transactions on Information Theory, 1997
- Orthogonal representations over finite fields and the chromatic number of graphsCombinatorica, 1996
- Wire-Tap Channel IIAT&T Bell Laboratories Technical Journal, 1984