Performance Bounds on a Wiretap Network With Arbitrary Wiretap Sets

DOI10.1109/TIT.2014.2315821zbMATH Open1360.94012arXiv1212.0101MaRDI QIDQ2986331FDOQ2986331

Fan Cheng, Raymond W. Yeung

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Consider a communication network represented by a directed graph $mathcalG=(mathcalV,mathcalE)$, where $mathcalV$ is the set of nodes and $mathcalE$ is the set of point-to-point channels in the network. On the network a secure message $M$ is transmitted, and there may exist wiretappers who want to obtain information about the message. In secure network coding, we aim to find a network code which can protect the message against the wiretapper whose power is constrained. Cai and Yeung cite{cai2002secure} studied the model in which the wiretapper can access any one but not more than one set of channels, called a wiretap set, out of a collection $mathcalA$ of all possible wiretap sets. In order to protect the message, the message needs to be mixed with a random key $K$. They proved tight fundamental performance bounds when $mathcalA$ consists of all subsets of $mathcalE$ of a fixed size $r$. However, beyond this special case, obtaining such bounds is much more difficult. In this paper, we investigate the problem when $mathcalA$ consists of arbitrary subsets of $mathcalE$ and obtain the following results: 1) an upper bound on $H(M)$; 2) a lower bound on $H(K)$ in terms of $H(M)$. The upper bound on $H(M)$ is explicit, while the lower bound on $H(K)$ can be computed in polynomial time when $|mathcalA|$ is fixed. The tightness of the lower bound for the point-to-point communication system is also proved.

Full work available at URL: https://arxiv.org/abs/1212.0101

Mathematics Subject Classification ID

Communication theory (94A05) Applications of graph theory to circuits and networks (94C15)

Cited In (1)

• (Secure) linear network coding multicast

This page was built for publication: Performance Bounds on a Wiretap Network With Arbitrary Wiretap Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986331)