Rényi Resolvability and Its Applications to the Wiretap Channel

Lei Yu, Vincent Y. F. Tan

TL;DR

This paper generalizes the concept of "channel resolvability" – determining the minimum rate needed to simulate a target output distribution from a given channel – by using Rényi divergences instead of traditional measures like KL divergence. They apply this to the wiretap channel, offering a more flexible way to characterize the trade-off between secret and non-secret message rates, especially when considering "stealthy" communication.

What Problem Does This Paper Address?

The core problem is understanding how much "randomness" or "rate" is needed to make a communication channel's output distribution closely mimic a desired target distribution. Traditionally, this has been measured using total variation distance or relative entropy (KL divergence). The authors extend this by introducing Rényi divergences, which offer a tunable parameter to control how "strict" the approximation needs to be. This generalization is particularly relevant for secure communication, specifically the wiretap channel, where we want to limit the information an eavesdropper can glean (leakage) while still transmitting useful data. The paper aims to provide a unified framework for analyzing these problems across a spectrum of divergence measures.

Methods

The paper introduces and analyzes Rényi divergences as a measure of approximation. They derive both finite-length and asymptotic expressions for these divergences. A key contribution is the characterization of Rényi resolvability, defined as the minimum rate required for the Rényi divergence to vanish asymptotically. They show that this resolvability rate is the same for normalized and unnormalized Rényi divergences. For parameters less than 1, it matches the traditional mutual information, but for parameters greater than 1, it can be higher. They also prove that the divergence decays exponentially fast with code rate exceeding the resolvability and characterize the optimal decay rate for i.i.d. random codes. Finally, they apply these findings to the wiretap channel to characterize the optimal trade-off between secret and non-secret message rates using Rényi divergence as the leakage measure.

Datasets

Not discussed in the paper. The paper deals with theoretical channel models and does not use empirical datasets.

Key Insights and Ideas

  • Tunable Secrecy/Approximation: Rényi divergences offer a flexible way to quantify "leakage" or "approximation error." By adjusting the Rényi parameter, one can tune the sensitivity to different types of errors, moving beyond the limitations of fixed measures like KL divergence.
  • Unified Framework: The paper unifies resolvability and wiretap channel analysis under a single, generalized divergence measure, showing how existing results (like those using KL divergence) are special cases.
  • Rényi Resolvability as a Fundamental Limit: The concept of Rényi resolvability provides a new fundamental limit for simulating distributions, with interesting properties that differ from traditional mutual information-based limits when the Rényi parameter is greater than 1.
  • Stealthy Communication: The application to the wiretap channel highlights how Rényi divergences can capture notions of "stealth" beyond just statistical independence, by requiring the eavesdropper's observation to approximate a target distribution.

Key Results

  • Rényi Divergence Bounds: Finite-length and asymptotic expressions for Rényi divergences are derived.
  • Rényi Resolvability Characterization: The minimum rate for asymptotic vanishing of Rényi divergence is characterized. This rate is equal to the minimum mutual information for Rényi parameters ≤ 1, and generally higher for parameters > 1.
  • Exponential Decay: The optimal exponential decay rate of Rényi divergence for i.i.d. random codes is characterized.
  • Wiretap Channel Trade-off: The optimal trade-off between secret and non-secret message rates for the wiretap channel is completely characterized using Rényi divergence as the leakage measure, offering a generalized result compared to previous work using mutual information.

Limitations and Future Work

  • Discrete Alphabets: While the paper mentions that some results hold for continuous alphabets, the primary focus and proofs are for discrete alphabets.
  • General Codes vs. i.i.d. Codes: The paper provides exact results for i.i.d. random codes but only lower bounds for general codes in some cases.
  • Future Work: The authors suggest exploring:
  • Rényi Common Information: Generalizing Wyner's common information using Rényi divergences.
  • Distributed Channel Synthesis: Extending distributed channel synthesis problems with Rényi divergences.
  • Second-Order Results: Investigating second-order asymptotics for Rényi divergence.

Summary updated

Abstract

The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) R\'enyi divergence (with the R\'enyi parameter in $[0,2]\cup\{\infty\}$) to measure the level of approximation. We also provide asymptotic expressions for normalized R\'enyi divergence when the R\'enyi parameter is larger than or equal to $1$ as well as (lower and upper) bounds for the case when the same parameter is smaller than $1$. We characterize the R\'enyi resolvability, which is defined as the minimum rate required to ensure that the R\'enyi divergence vanishes asymptotically. The R\'enyi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the R\'enyi parameter smaller than~$1$, consistent with the traditional case where the R\'enyi parameter is equal to~$1$, the R\'enyi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the R\'enyi parameter is larger than $1$ the R\'enyi resolvability is, in general, larger than the mutual information. The optimal R\'enyi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the R\'enyi resolvability. The optimal exponential rate of decay for i.i.d.\ random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) R\'enyi divergence.
BibTeX
@inproceedings{yu2017renyi,
  author = {Lei Yu and Vincent Y. F. Tan},
  title = {{Rényi Resolvability and Its Applications to the Wiretap Channel}},
  booktitle = {ICITS},
  year = {2017},
  doi = {10.1007/978-3-319-72089-0\_12},
}
Figure