A Numerical Study on the Wiretap Network with a Simple Network Topology

Abstract

In this paper, we study a security problem on a simple wiretap network, consisting of a source node S, a destination node D, and an intermediate node R. The intermediate node connects the source and the destination nodes via a set of noiseless parallel channels, with sizes \(n_1\) and \(n_2\), respectively. A message \(M\) is to be sent from S to D. The information in the network may be eavesdropped by a set of wiretappers. The wiretappers cannot communicate with one another. Each wiretapper can access a subset of channels, called a wiretap set. All the chosen wiretap sets form a wiretap pattern. A random key \(K\) is generated at S and a coding scheme on \((M, K)\) is employed to protect \(M\). We define two decoding classes at D: In Class-I, only \(M\) is required to be recovered and in Class-II, both \(M\) and \(K\) are required to be recovered. The objective is to minimize \(H(K)/H(M)\) {for a given wiretap pattern} under the perfect secrecy constraint. The first question we address is whether routing is optimal on this simple network. By enumerating all the wiretap patterns on the Class-I/II \((3,3)\) networks and harnessing the power of Shannon-type inequalities, we find that gaps exist between the bounds implied by routing and the bounds implied by Shannon-type inequalities for a small fraction~(\(<2\%\)) of all the wiretap patterns. The second question we investigate is the following: What is \(\min H(K)/H(M)\) for the remaining wiretap patterns where gaps exist? We study some simple wiretap patterns and find that their Shannon bounds (i.e., the lower bound induced by Shannon-type inequalities) can be achieved by linear codes, which means routing is not sufficient even for the (\(3\), \(3\)) network. For some complicated wiretap patterns, we study the structures of linear coding schemes under the assumption that they can achieve the corresponding Shannon bounds....