Title: Random linear network coding with probabilistic polynomial-time wiretap adversary

Authors: Zhiwen Hu; Li Zhu; Huaqing Mao

Addresses: College of New Media, Zhejiang University of Media and Communications, No. 998 Xueyuan Street, Xiasha Higher Education Zone, Hangzhou, 310018, China ' Oujiang College, Wenzhou University, Chashan University Town, Wenzhou, 325035, China ' Oujiang College, Wenzhou University, Chashan University Town, Wenzhou, 325035, China

Abstract: 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.

Keywords: linear network coding; confidentiality; computational bounded adversaries; pseudorandom generator; linear cryptanalysis; cryptography; probabilistic polynomial-time; PPT wiretap adversary; multicast networks; chosen-message-attack; CMA; network security.

DOI: 10.1504/IJESDF.2015.067993

International Journal of Electronic Security and Digital Forensics, 2015 Vol.7 No.1, pp.41 - 53

Received: 22 Oct 2014
Accepted: 30 Oct 2014

Published online: 11 Mar 2015 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article