Research And Design For High Efficiency Null Keys Based Network Coding Schemes Against Pollution Attacks

Network coding allows participating nodes in a network to code incoming data flowsrather than simply forwarding them. It has gained wide attention nowadays for itssignificant advantages on network throughput, content confidentiality, flow untraceability,and transmission reliability, etc. comparing with traditional routing mechanism.Although systems with network coding enjoy the advantages mentioned above, theirperformance will greatly decrease when malicious relay nodes launch pollution attacks.The null keys scheme, proposed by Kehdi et al., defends against pollution attacks well.Furthermore, it has many advantages such as, good distribution characteristic, lowcomputation overheads during verification, simple to implemented, and so on. However,the obtained distributed null space by malicious nodes will lead to vanished security of thesystem, i.e., the scheme has a low security level.For the mentioned problem, we propose the concept of complete null space, with theproperty that no pollution packet can pass the verification of the null space. If thedistributed null space can compose complete null space in the original null keys basedscheme, it can improve the security level of the scheme efficiently. However, it will heavilyburden the system.Targeting at distributing complete null space together with reducing the overheads inintroducing null keys, we generlize the concept of null keys, propose the idea of partiallyposition detection, and construct short length null keys. We prove the existence ofcomplete null space of short null keys, and prove that the brought overheads of short nullkeys in constructing complete null space are reduced, comparing with that of the originalnull keys. Subsequently, we further give the sufficient condition for the existence of thecomplete null space of short length null keys.In succession, we design the short null keys based pollution detection scheme.Rigorous theoretical proofs are given to analyze the security of the scheme. Sorts ofperformances are considered comprehensively, via numerical analyses, to determine the value of each parameter in the scheme. Under the settings of these parameters, short nullkeys scheme enjoys high security level, low computation and communication overheads. Itis a high efficiency null keys based pollution detection scheme.Since the verification positions of short null keys are not necessarily the same, sourcenode has to secretly distribute short null keys to every node in the short null keys basedscheme. It will burden the source node heavily, and influence the distributed performanceof the scheme if the network is in large scale, or in high dynamic. To settele the problem,we construct compressed short null keys. This kind of null keys can be distributed innetwork coding way. Moreover, we optimize the compressed short null keys, and constructnew compressed short null keys. We prove the existence of complete null space of thecompressed short null keys and the new compressed short null keys. Then we prove thatthe brought overheads of these two kinds of null keys are reduced in constructing completenull space, comparing with that of the original null keys.Afterwards, we design the new compressed short null keys based pollution detectionscheme. In the scheme, null keys are distrubuted in the network coding way. Thismaintains the good distributed performance of the original null keys based scheme, andsettle the problem of poor distribution performance in short null keys scheme. Then weanalyze the security of the scheme through strict proofs. We prove that under certainconditions of the parameters, the computation overheads, the communication overheadsand the security level of the new compressed null keys scheme will be better than theoriginal null keys scheme. Finally, simulation results show that the new compressed nullkeys scheme has better performances than homomorphic scheme and original null keysscheme and it is a high efficiency null keys based pollution detection scheme.