Performance Bounds in Secure Network Coding.
详细信息
文摘
In a communication network on which a secure message is transmitted,there may exist illegal users who want to obtain information about the message. Here we refer to the network and those illegal users as the wiretap network and wiretappers,respectively. In secure network coding,we aim to find a network code which can protect the message against the wiretappers under certain constraints. To protect the message we transmit a ciphertext which is a mixture of the message and a private random key,through the channels in the network. In this work,we consider two kinds of security levels: perfect security and imperfect security. In perfect security,the ciphertext is statistically independent of the message,i.e.,the wiretapper can obtain only some randomly generated messages. While in imperfect security,the wiretapper can obtain partial information about the message which is measured by the wiretappers equivocation. If the wiretappers equivocation is equal to the message size,then the imperfect security reduces to perfect security. The focus of our work is to protect the message at the minimum cost,which is measured by the size the key and the bandwidth of the network. Here we denote the network by G＝V,E,where V is the set of nodes and E is the set of point-to-point channels in the network. A wiretapper may access the information transmitted on a certain subset of E . In our model,it is assumed that the wiretapper can access any one but not more than one set of channels,called a wiretap set,out of a collection A of all possible wiretap sets. In a wiretap network,if perfect security is required,existing works show that when A consists of all the r-subsets of E i.e. subsets of size r),there exists a linear network code,which is optimal according to the following two criteria: i) the size of the message is maximum； ii) the size of random key is minimum. But when A consists of arbitrary subsets of E,very little is known about the fundamental performance limit. In the first part of our work,we investigate this problem and obtain some results on the above fundamental performance limits. In this work,we adopt the convention that the size of a random variable X is measured by its entropy HX). 1) For the size of the message,we derive an upper bound on HM) and provide a polynomial algorithm to compute it. 2) For the size of the key,we analyze it from the aspects of fractional covering and fractional packing,respectively,by which we obtain two bounds on HK) and we prove the duality between them. Then we discuss the algorithms to compute the lower bound,including a brute force algorithm and a polynomial algorithm in terms of V,E and d,where d is the number of wiretap sets. At last,we discuss the tightness of the lower bound in some special cases and we prove that in the point-to-point communication system,the lower bound is tight. In the remaining part,we are largely concerned with imperfect security in a point-to-point communication system,where a classical security model referred to as the wire-tap channel II is generalized by introducing imperfect security. In wire-tap channel II,information is sent to the receiver through a set of point-to-point channels. It is assumed that the wiretapper can access any one but not more than one set in A which consists of all the subsets of the channel set with size r. The strategy to protect the private message is the same as that in the wiretap network. Specifically,a lower bound on the size of the key which can be attained by a group code was proved. In our extension,A is arbitrary and from each wiretap set in A,the wiretapper can obtain some partial information about the message. Under these settings,we define an achievable rate tuple in terms of the message,the key and the wiretappers equivocation,and prove a tight rate region of the rate tuples.