Abstract
We consider a 1-to-$K$ communication scenario, where a source transmits private messages to $K$ receivers through a broadcast erasure channel, and the receivers feed back strictly causally and publicly their channel states after each transmission. We explore the achievable rate region when we require that the message to each receiver remains secret - in the information theoretical sense - from all the other receivers. We characterize the capacity of secure communication in all the cases where the capacity of the 1-to-$K$ communication scenario without the requirement of security is known. As a special case, we characterize the secret-message capacity of a single receiver point-to-point erasure channel with public state-feedback in the presence of a passive eavesdropper. We find that in all cases where we have an exact characterization, we can achieve the capacity by using linear complexity two-phase schemes: in the first phase we create appropriate secret keys, and in the second phase we use them to encrypt each message. We find that the amount of key we need is smaller than the size of the message, and equal to the amount of encrypted message the potential eavesdroppers jointly collect. Moreover, we prove that a dishonest receiver that provides deceptive feedback cannot diminish the rate experienced by the honest receivers. We also develop a converse proof which reflects the two-phase structure of our achievability scheme. As a side result, our technique leads to a new outer bound proof for the non-secure communication problem.
Problem Definition
In a typical wireless broadcast scenario, transmissions are inherently "leaky." When a source (Alice) sends a packet to one receiver, others may also overhear it. If Alice wants to send private, independent messages to each person, she must ensure that no receiver learns anything about another's message.
This paper addresses the Broadcast Erasure Channel with State-feedback. In this model, packets are either received perfectly or lost (erased) with some probability $\delta_j$. Receivers publicly announce which packets they received via acknowledgments (ACKs). The central question is: Can we leverage these public ACKs and the random nature of erasures to create a perfectly secure communication system using information-theoretic security, which remains secure regardless of an attacker's computing power?
Methodology
The authors propose a linear-complexity, two-phase architecture to achieve secure capacity:
- Key Generation Phase: Alice sends random packets. Because the channel is an erasure channel, some packets will be received by one user but not by others. Using public feedback, Alice identifies these "exclusive" packets to establish a shared secret key with the intended receiver.
- Encrypted Broadcast Phase: Alice uses these generated keys to encrypt actual messages using a one-time pad approach. Rather than requiring a key as large as the message, the authors develop an efficient scheme where keys are reused based on the side information receivers collect, exploiting the fact that eavesdroppers only intercept a fraction of the encrypted traffic.
The paper establishes the fundamental limit of this system by providing both an achievability scheme and a mathematical converse proof.
Key Insights
- Erasures as an Asset: Packet loss, usually a nuisance, is utilized here as the source of security. The event of one user missing a packet while another receives it allows for the creation of a secret.
- Key Size Efficiency: The required key size is smaller than the message size. Alice only needs enough "key" to cover the specific bits the eavesdroppers actually manage to intercept.
- Resilience to Dishonesty: The authors demonstrate that even if a receiver provides deceptive feedback (lying about received packets), they cannot reduce the transmission rate for honest receivers.
- Bridge to Cryptography: The work demonstrates a formal equivalence between information-theoretic security metrics and "semantic security," the gold standard in computational cryptography.
Key Results
The authors successfully characterized the secret-message capacity region for several configurations, including 2-user, 3-user, and symmetric $K$-user cases.
For a single receiver and one eavesdropper (the wiretap channel) with public feedback, they derived a closed-form expression for capacity: $$C_E = (1 - \delta)\delta_E \frac{1 - \delta\delta_E}{1 - \delta\delta_E^2}$$ where $\delta$ is the legitimate user's erasure rate and $\delta_E$ is the eavesdropper's. Importantly, the proposed schemes maintain linear complexity, making them viable for real-time systems.
Limitations and Future Work
While the paper provides a robust framework, it assumes "strictly causal" and "public" feedback. In high-speed or long-distance links, feedback delay might impact key-generation efficiency. Additionally, the model assumes Alice has accurate knowledge of erasure probabilities ($\delta_j$), which can be challenging to estimate in highly dynamic environments. While the paper solves common configurations, a universal characterization for any arbitrary $K$-user erasure channel without symmetry remains an open problem.
Summary updated