Secure Network Coding Against The Contamination And Eavesdropping Adversaeirs

In recent years, there has been increasing attention to the theory of network coding.Network coding is beneficial for the basic router infrastructure and wireless network, sinceit greatly improved the multicast rate, throughput and robust of the network. However,direct application of network coding may su?er from two kinds of adversaries: contamina-tion and eavesdropping. Here contamination refers to the distortion on the transmission,such as random errors and malicious modifications. Eavesdropping referring to the adver-sary aims to get the transfer of information by eavesdropping on some or all the channelsover a network. The application and promotion of the network coding are greatly re-stricted by these two kinds of adversaries. In this dissertation, we study these two kindsof adversaries and design some secure network coding schemes to conquer them. Themain results of this dissertation are as follows:(1) An algorithm that targets eavesdropping adversaries is presented. By means of thisalgorithm, an eavesdropper is unable to get any meaningful information about thesource, which we call weak security. We show that if we give up a small amountof overall capacity, then a random code achieves the weak security condition ata much higher probability. Besides, when there is a low rate secret channel or apublic encryption scheme between the source and destination, an algorithm thatnot only achieves the max-?ow but also the weak security condition is proposed.The probability of the coding scheme to be security is 1, when random codingscheme is used.(2) There are two main problems in the present secure network coding schemes. Firstly,in order to achieve the information security condition, some network capacity mustbe sacrificed and the max-?ow of the network could not be achieved. Secondly, whenrandom coding scheme is used, the probability of the coding scheme to be security islow. A max-?ow achieved information secure network coding scheme is proposed inthis dissertation. The coding scheme is a deterministic model instead of probabilitymodel i.e, the probability of the coding scheme to be information security is one,when random coding scheme is used.(3) A homomorphic hash scheme to verify the integrity of the received packets is pre-sented. Firstly, the public parameters are selected as the"intended"hash values.The original packets are padded so that they are hashed to the public parameters.In this way the distribution of the hash values is avoided and hence the communica-tion overhead is reduced. Secondly, when the topology of the network is fixed, the code coe?cients can be generated by a shared pseudo-random number generator sothat the distribution of the coe?cients can also be avoided. When the distributionof the hash values and the code coe?cients are both avoided, we indicate that thecommunication overhead of the scheme is negligible compared with previous works.(4) A random network coding scheme against the contamination adversary is proposed,using the idea that the message packets span a vector space. The proposed securescheme is a probability model. When the source and the destinations share a linearvector space, some redundancy is added to the source message. In this way, thevector space spanned by the padded message is orthogonal to the shared vectorspace and the original source message can be decoded.(5) Koetter and Kschischang proposed an error correcting network coding scheme viathe vector space perspective using the linearized polynomials over finite field. Itis noted that, the communication overhead of their scheme is high, actually 100%,which greatly restricted its application. Based on their coding scheme, we propose alow communication overhead error correcting network coding scheme in this disser-tation. The overhead of the proposed coding scheme is the same as the standard ran-dom network coding. Furthermore, the eavesdropping adversary is also consideredand a secure network coding scheme against the contamination and eavesdroppingadversary is proposed.