Strong Secrecy and Reliable Byzantine Detection in the Presence of an Untrusted Relay

We consider a Gaussian two-hop network where the source and the destination can communicate only via a relay node who is both an eavesdropper and a Byzantine adversary. Both the source and the destination nodes are allowed to transmit, and the relay receives a superposition of their transmitted signals. We propose a new coding scheme that satisfies two requirements simultaneously: the transmitted message must be kept secret from the relay node, and the destination must be able to detect any Byzantine attack that the relay node might launch reliably and fast. The three main components of the proposed scheme are the nested lattice code, the privacy amplification scheme, and the algebraic manipulation detection (AMD) code. Specifically, for the Gaussian two-hop network, we show that lattice coding can successfully pair with AMD codes enabling its first application to a noisy channel model. We prove, using this new coding scheme, that the probability that the Byzantine attack goes undetected decreases exponentially fast with respect to the number of channel uses, while the loss in the secrecy rate, compared to the rate achievable when the relay is honest, can be made arbitrarily small. In addition, in contrast with prior work in Gaussian channels, the notion of secrecy provided here is strong secrecy.

I. Introduction

Information-theoretic secrecy, first proposed by Shannon [1], provides confidentiality of transmitted information against an adversary regardless of its computational power. Shannon proved that if the adversary has access to the signals transmitted by the sender of the secret message through a noiseless channel, then, to achieve complete independence between the confidential message and the adversary's observation, the sender and the receiver have to share a secret key of the same rate as the message. Although Shannon's result implied that secret communication was impractical in this setting, it was later shown by Wyner [2] that this pessimistic result was a consequence of the noiseless channel assumption. Specifically, it was shown that when the adversary has noisy observations of the signals transmitted by the sender, a nonzero transmission rate for the secret message is achievable without requiring the transmitter to preshare a key with the receiver [2]–[4]. More recently, the fundamental rate limits at which the secret communication can take place in the presence of an eavesdropper were studied for a number of multiterminal models, e.g., the broadcast channel [5], [6], the multiple access channel [7]–[9], and the interference channel [10]–[12].