Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1506.00154 · IEEE International Symposium on Information Theory (ISIT)

Resolvability in Eγ with applications to lossy compression and wiretap channels

Jingbo Liu, Paul Cuff, Sergio Verdu

Published Jun 1, 2015• 9 citations
arXivHTMLPDF

Abstract

We study the amount of randomness needed for an input process to approximate a given output distribution of a channel in the Eγ distance. A general one-shot achievability bound for the precision of such an approximation is developed. In the i.i.d. setting where γ = exp(nE), a (nonnegative) randomness rate above infQU:D(QX||πX)≤E{D(QX||πX) + I(QU, QX|U) - E} is necessary and sufficient to asymptotically approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX. The new resolvability result is then used to derive a oneshot upper bound on the error probability in the rate distortion problem; and a lower bound on the size of the eavesdropper list to include the actual message in the wiretap channel problem. Both bounds are asymptotically tight in i.i.d. settings.

DOI
10.1109/isit.2015.7282556

Related papers

$E_{\gamma}$-Resolvability

Jingbo Liu, Paul Cuff, Sergio Verdú

The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper, we study Eγ-resolvability, in which total variation is replaced by the more general Eγdistance. A general one-shot achievability bound for the precision of such an approximation is developed. Let QX|Ube a random transformation, n be an integer, and E ∈ (0, +∞). We show that in the asymptotic setting where γ = exp(nE), a (nonnegative) randomness rate above inf QU:D(QXIIπX)≤E{D(QXIIπX) + I(QU, QX|U) - E} is sufficient to approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX, and is also necessary in the case of finite U and X . In particular, a randomness rate of inf QUI(QU, QX|U) - E is always sufficient. We also study the convergence of the approximation error under the high-probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating Eγand other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive: 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d. setting; 2) a one-shot version of the mutual covering lemma; and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.

arXiv:1511.07829•IEEE Transactions on Information Theory•Jan 1, 2016•32 citations

Rényi Resolvability and Its Applications to the Wiretap Channel

Lei Yu, Vincent Y. F. Tan

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ényi divergence (with the Rényi parameter in[0, 2] U {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi 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ényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi 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ényi 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ényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.

arXiv:1707.00810•IEEE Transactions on Information Theory•Dec 7, 2018•45 citations

Resolvability theory for the multiple-access channel

Yossef Steinberg

We study the randomness needed for approximating the output distribution of a multiple-access channel, where the original input processes are independent of each other. The approximation is achieved by simulating (possibly alternative) input processes at each of the entries, where the sources of randomness available for the simulators are independent of each other, and the simulators do not cooperate. The resolvability region of a multiple-access channel is defined as the set of all random-bit rate pairs at which accurate output approximation is possible, where the simulation accuracy is measured by the variational distance between finite-dimensional output distributions. Inner and outer bounds on the resolvability region are derived, and close relations between the concepts of resolvability region and capacity region are demonstrated.

IEEE Transactions on Information Theory•Mar 1, 1998•32 citations

General nonasymptotic and asymptotic formulas in channel resolvability and identification capacity and their application to the wiretap channel

Masahito Hayashi

Several nonasymptotic formulas are established in channel resolvability and identification capacity, and they are applied to the wiretap channel. By using these formulas, the epsi capacities of the above three problems are considered in the most general setting, where no structural assumptions such as the stationary memoryless property are made on a channel. As a result, we solve an open problem proposed by Han and Verduacute. Moreover, we obtain lower bounds of the exponents of error probability and the wiretapper's information in the wiretap channel

arXiv:cs/0503088•IEEE Transactions on Information Theory•Apr 1, 2006•253 citations

Wiretap Channel With Secure Rate-Limited Feedback

Ehsan Ardestanizadeh, Massimo Franceschetti, Tara Javidi +1 more

This paper studies the problem of secure communication over a wiretap channel p(y,z|x) with a secure feedback link of rate Rf, where X is the channel input, and Y and Z are channel outputs observed by the legitimate receiver and the eavesdropper, respectively. It is shown that the secrecy capacity, the maximum data rate of reliable communication while the intended message is not revealed to the eavesdropper, is upper bounded as Cs(Rf) les maxmin/p(x) {I(X;Y), I(X;Y |Z) + Rf}. The proof of the bound crucially depends on a recursive argument which is used to obtain the single-letter characterization. This upper bound is shown to be tight for the class of physically degraded wiretap channels. A capacity-achieving coding scheme is presented for this case, in which the receiver securely feeds back fresh randomness with rate Rf, generated independent of the received channel output symbols. The transmitter then uses this shared randomness as a secret key on top of Wyner's coding scheme for wiretap channels without feedback. Hence, when a feedback link is available, the receiver should allocate all resources to convey a new key rather than sending back the channel output.

IEEE Transactions on Information Theory•Nov 24, 2009•142 citations

Strong Secrecy for Interference Channels Based on Channel Resolvability

Zhao Wang, Rafael F. Schaefer, Mikael Skoglund +2 more

Interference channels with confidential messages are studied under strong secrecy constraints, based on the framework of channel resolvability theory. It is shown that if the random binning rate for securing a confidential message is above the resolution of its corresponding wiretapped channel, strong secrecy can be guaranteed. The information-spectrum method introduced by Han and Verdú is generalized to an arbitrary interference channel to obtain a direct channel resolvability result as a first step. For stationary and memoryless channels with discrete output alphabets, the results show that the achievable rates under weak and strong secrecy constraints are the same. This result is then generalized to channels with continuous output alphabets by deriving a reverse direction of Pinsker's inequality to bound the secrecy measure from above by a function of the variational distance of relevant distributions. As an application, Gaussian interference channels are studied in which the agreement between the best known weak and strong secrecy rate regions also appear. Following the footsteps of Csiszár, Hayashi and of Bloch and Laneman, these results provide further evidence that channel resolvability is a powerful and general framework for strong secrecy analysis in multiuser networks.

IEEE Transactions on Information Theory•May 9, 2018•11 citations
We study the amount of randomness needed for an input process to approximate a given output distribution of a channel in the Eγ distance. A general one-shot achievability bound for the precision of such an approximation is developed. In the i.i.d. setting where γ = exp(nE), a (nonnegative) randomness rate above infQU:D(QX||πX)≤E{D(QX||πX) + I(QU, QX|U) - E} is necessary and sufficient to asymptotically approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX. The new resolvability result is then used to derive a oneshot upper bound on the error probability in the rate distortion problem; and a lower bound on the size of the eavesdropper list to include the actual message in the wiretap channel problem. Both bounds are asymptotically tight in i.i.d. settings.
EγE_{\gamma}Eγ​-Resolvability
The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper, we study Eγ-resolvability, in which total variation is replaced by the more general Eγdistance. A general one-shot achievability bound for the precision of such an approximation is developed. Let QX|Ube a random transformation, n be an integer, and E ∈ (0, +∞). We show that in the asymptotic setting where γ = exp(nE), a (nonnegative) randomness rate above inf QU:D(QXIIπX)≤E{D(QXIIπX) + I(QU, QX|U) - E} is sufficient to approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX, and is also necessary in the case of finite U and X . In particular, a randomness rate of inf QUI(QU, QX|U) - E is always sufficient. We also study the convergence of the approximation error under the high-probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating Eγand other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive: 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d. setting; 2) a one-shot version of the mutual covering lemma; and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.
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ényi divergence (with the Rényi parameter in[0, 2] U {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi 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ényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi 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ényi 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ényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.
We study the randomness needed for approximating the output distribution of a multiple-access channel, where the original input processes are independent of each other. The approximation is achieved by simulating (possibly alternative) input processes at each of the entries, where the sources of randomness available for the simulators are independent of each other, and the simulators do not cooperate. The resolvability region of a multiple-access channel is defined as the set of all random-bit rate pairs at which accurate output approximation is possible, where the simulation accuracy is measured by the variational distance between finite-dimensional output distributions. Inner and outer bounds on the resolvability region are derived, and close relations between the concepts of resolvability region and capacity region are demonstrated.
Several nonasymptotic formulas are established in channel resolvability and identification capacity, and they are applied to the wiretap channel. By using these formulas, the epsi capacities of the above three problems are considered in the most general setting, where no structural assumptions such as the stationary memoryless property are made on a channel. As a result, we solve an open problem proposed by Han and Verduacute. Moreover, we obtain lower bounds of the exponents of error probability and the wiretapper's information in the wiretap channel
This paper studies the problem of secure communication over a wiretap channel p(y,z|x) with a secure feedback link of rate Rf, where X is the channel input, and Y and Z are channel outputs observed by the legitimate receiver and the eavesdropper, respectively. It is shown that the secrecy capacity, the maximum data rate of reliable communication while the intended message is not revealed to the eavesdropper, is upper bounded as Cs(Rf) les maxmin/p(x) {I(X;Y), I(X;Y |Z) + Rf}. The proof of the bound crucially depends on a recursive argument which is used to obtain the single-letter characterization. This upper bound is shown to be tight for the class of physically degraded wiretap channels. A capacity-achieving coding scheme is presented for this case, in which the receiver securely feeds back fresh randomness with rate Rf, generated independent of the received channel output symbols. The transmitter then uses this shared randomness as a secret key on top of Wyner's coding scheme for wiretap channels without feedback. Hence, when a feedback link is available, the receiver should allocate all resources to convey a new key rather than sending back the channel output.
Interference channels with confidential messages are studied under strong secrecy constraints, based on the framework of channel resolvability theory. It is shown that if the random binning rate for securing a confidential message is above the resolution of its corresponding wiretapped channel, strong secrecy can be guaranteed. The information-spectrum method introduced by Han and Verdú is generalized to an arbitrary interference channel to obtain a direct channel resolvability result as a first step. For stationary and memoryless channels with discrete output alphabets, the results show that the achievable rates under weak and strong secrecy constraints are the same. This result is then generalized to channels with continuous output alphabets by deriving a reverse direction of Pinsker's inequality to bound the secrecy measure from above by a function of the variational distance of relevant distributions. As an application, Gaussian interference channels are studied in which the agreement between the best known weak and strong secrecy rate regions also appear. Following the footsteps of Csiszár, Hayashi and of Bloch and Laneman, these results provide further evidence that channel resolvability is a powerful and general framework for strong secrecy analysis in multiuser networks.