Detecting and Tracing i.i.d. Attacks in Networks With Any Number of Relays

This paper investigates the detection and tracing problems in a multi-relay network, where a source wants to exchange the information with a destination through multiple potential malicious relay nodes. We find that the destination could probabilistically detect the maliciousness in a multi-relay network if and only if the network satisfies a non-manipulable condition. Notice that the non-manipulable condition of the whole network is complicated to be checked. We divide the whole network into several sub-networks, and check the non-manipulability of the small-scale sub-networks in turn, which finally constitutes to a simplified checking method of the non-manipulable condition for the whole relay network. Furthermore, we propose a tracing algorithm to pinpoint the malicious relays individually in a multi-relay network if a tracing condition is satisfied. No pre-shared secret is needed in our proposed detecting and tracing schemes. Numerical examples are presented to validate the effectiveness of the proposed schemes.