Random linear network coding with probabilistic polynomial-time wiretap adversary
Hu Zhi, Li Zhu, Huaqing Mao · International Journal of Electronic Security and Digital Forensics · 2015
Linear network coding can achieve the network capacity in the single source multicast case. For the single source multicast network with wiretap adversary, Cai and Yeung (2002) suggest an information–secure linear coding which tightly achieves the transmitting rate upper bound C − t, where C is the capacity of the network and t is the maximum number of edges with wiretap adversary. In this paper, we consider the cryptographic security for the messages in the random linear network coding setting. The indistinguishability under chosen–message–attack (or CMA–security) from probabilistic polynomial–time (PPT) wiretap adversary is defined. With a pseudorandom generator against linear cryptanalysis, a peer–to–peer protocol is constructed for multicast network using random linear network coding. When the adversary wiretap less than C edges, the protocol is CMA–secure and attains transmitting rate approaching the network's capacity C from below, asymptotically in the expanding ratio (i.e., length of output string/length of input string) of the pseudorandom generator. Compared with secret–key–based scheme, no secret is needed by the receiver nodes, which means the key managing issues for dynamic networks would never come up.