Studies two problems in the theory of identification via channels. The first problem concerns the identification via channels with noisy feedback. Whereas for Shannon's transmission problem the capacity of a discrete memoryless channel does not change with feedback, it is known that the identification capacity is affected by feedback. The authors study its dependence on the feedback channel. They prove both, a direct and a converse coding theorem. Although a gap exists between the upper and lower bounds provided by these two theorems, the known result for channels without feedback and the known result for channels with complete feedback, are both special cases of these two new theorems, because in these cases the bounds coincide. The second problem is the identification via wiretap channels. A secrecy identification capacity is defined for the wiretap channel. A "dichotomy theorem" is proved which says that the second-order secrecy identification capacity is the same as Shannon's capacity for the main channel as long as the secrecy transmission capacity of the wiretap channel is not zero, and zero otherwise. Equivalently, one can say that the identification capacity is not lowered by the presence of a wiretapper as long as 1 bit can be transmitted (or identified) correctly with arbitrarily small error probability. This is in strong contrast to the case of transmission.>
Studies two problems in the theory of identification via channels. The first problem concerns the identification via channels with noisy feedback. Whereas for Shannon's transmission problem the capacity of a discrete memoryless channel does not change with feedback, it is known that the identification capacity is affected by feedback. The authors study its dependence on the feedback channel. They prove both, a direct and a converse coding theorem. Although a gap exists between the upper and lower bounds provided by these two theorems, the known result for channels without feedback and the known result for channels with complete feedback, are both special cases of these two new theorems, because in these cases the bounds coincide. The second problem is the identification via wiretap channels. A secrecy identification capacity is defined for the wiretap channel. A "dichotomy theorem" is proved which says that the second-order secrecy identification capacity is the same as Shannon's capacity for the main channel as long as the secrecy transmission capacity of the wiretap channel is not zero, and zero otherwise. Equivalently, one can say that the identification capacity is not lowered by the presence of a wiretapper as long as 1 bit can be transmitted (or identified) correctly with arbitrarily small error probability. This is in strong contrast to the case of transmission.>
The concept of the wiretap channel was first proposed by Wyner. He considered the case in which data is to be transmitted reliably over a discrete memoryless main channel to a legitimate receiver. The wiretapper views the output of the main channel through another discrete memoryless channel. It is assumed that the wiretapper knows the code being used and his only handicap is the additional noise in his signal. The problem is to maximize the transmission rate R to the legitimate receiver and the equivocation d of the wiretapper. In this dissertation, the additive white Gaussian noise wiretap channel is introduced and the set of all achievable (R,d) pairs is determined explicitly through the use of certain special properties of the Gaussian channel. Some useful characterizations of a special class of wiretap channels are also explored. A model of the wiretap channel with feedback is proposed. It turns out that with the introduction of feedback, even when the main channel is inferior to the wiretapper's channel, it is still possible to reliably communicate with the legitimate receiver in complete secrecy. The binary erasure wiretap channel with feedback is examined and inner and outer bounds on the achievable (R,d) region are given. Finally, a scheme for enlarging the capacity region of multiple-access channels using feedback is analyzed. It is shown that conditions under which an enlargement is possible are fairly weak, indicating that feedback can almost increase the capacity region. (Author)
In the theory of identification via noisy channels randomization in the encoding has a dramatic effect on the optimal code size, namely, it grows double-exponentially in the blocklength, whereas in the theory of transmission it has the familiar exponential growth. We consider now instead of the discrete memoryless channel (DMC) more robust channels such as the familiar compound (CC) and arbitrarily varying channels (AVC). They can be viewed as models for jamming situations. We make the pessimistic assumption that the jammer knows the input sequence before he acts. This forces communicators to use the maximal error concept and also makes randomization in the encoding superfluous. Now, for a DMC W by a simple observation, made by Ahlswede and Dueck (1989), in the absence of randomization the identification capacity, say C/sub NRI/(W), equals the logarithm of the number of different row-vectors in W. We generalize this to compound channels. A formidable problem arises if the DMC W is replaced by the AVC W. In fact, for 0-1-matrices only in W we are-exactly as for transmission-led to the equivalent zero-error-capacity of Shannon. But for general W the identification capacity C/sub NRI/(W) is quite different from the transmission capacity C(W). An observation is that the separation codes of Ahlswede (1989) are also relevant here. We present a lower bound on C/sub NRI/(W). It implies for instance for W={(/sub 0 1//sup 1 0/), (/sub /spl delta/ (1-/spl delta/)(1 0)/)}, /spl delta//spl isin/(0, 1/2 ) that C/sub NRI/(W)=1, which is obviously tight. It exceeds C(W), which is known to exceed 1-h(/spl delta/), where h is the binary entropy function. We observe that a separation code, with worst case average list size L~ (which we call an NRA code) can be partitioned into L~2/sup ne/ transmission codes. This gives a nonsingle-letter characterization of the capacity of AVC with maximal probability of error in terms of the capacity of codes with list decoding. We also prove that randomization in the decoding does not increase C/sub I/(W) and C/sub NRI/(W). Finally, we draw attention to related work on source coding.
A study is made of the identification problem in the presence of a noiseless feedback channel, and the second-order capacity C/sub f/ (resp. C/sub F/) for deterministic (resp. randomized) encoding strategies is determined. Several important phenomena are encountered. (1) Although feedback does not increase the transmission capacity of a discrete memoryless channel (DMC), it does increase the (second-order) identification capacity; (2) noise increases C/sub f/; (3) the structure of the new capacity formulas is simpler than C.E. Shannon's (1948) familiar formula. This has the effect that proofs of converses become easier than in the authors' previous work.>
We study the identification capacity of classical-quantum channels (“cq-channels”) under channel uncertainty and privacy constraints. To be precise, we first consider compound memoryless cq-channels and determine their identification capacity; then we add an eavesdropper by considering compound memoryless wiretap cqq-channels, and determine their secret identification capacity. In the first case (without privacy), we find the identification capacity always equal to the transmission capacity. In the second case, we find a dichotomy: either the secrecy capacity (also known as private capacity) of the channel is zero, and then the secrecy identification capacity is also zero, or the secrecy capacity is positive and then the secrecy identification capacity equals the transmission capacity of the main channel without the wiretapper. We perform the same analysis for the case of arbitrarily varying wiretap cqq-channels (cqq-AVWC) with analogous findings, and make several observations regarding the continuity and super-additivity of the identification capacity in the latter case.
We study the identification capacity of classical-quantum channels (“cq-channels”), under channel uncertainty and privacy constraints. To be precise, we consider first compound memoryless cq-channels and determine their identification capacity; then we add an eavesdropper, considering compound memoryless wiretap cqq-channels, and determine their secret identification capacity. In the first case (without privacy), we find the identification capacity always equal to the transmission capacity. In the second case, we find a dichotomy: either the secrecy capacity (also known as private capacity) of the channel is zero, and then also the secrecy identification capacity is zero, or the secrecy capacity is positive and then the secrecy identification capacity equals the transmission capacity of the main channel without the wiretapper. We perform the same analysis for the case of arbitrarily varying wiretap cqq-channels (cqq-AVWC), with analogous findings, and make several observations regarding the continuity and super-additivity of the identification capacity in the latter case.
In this paper, a new wiretap channel model is proposed, where the legitimate transmitter and receiver communicate over a discrete memoryless channel. The wiretapper has perfect access to a fixed-length subset of the transmitted codeword symbols of her choosing. Additionally, she observes the remainder of the transmitted symbols through a discrete memoryless channel. This new model subsumes the classical wiretap channel and wiretap channel II with noisy main channel as its special cases. The strong secrecy capacity of the proposed channel model is identified. Achievability is established by solving a dual secret key agreement problem in the source model, and converting the solution to the original channel model using probability distribution approximation arguments. In the dual problem, a source encoder and decoder, who observe random sequences independent and identically distributed according to the input and output distributions of the legitimate channel in the original problem, communicate a confidential key over a public error-free channel using a single forward transmission, in the presence of a compound wiretapping source who has perfect access to the public discussion. The security of the key is guaranteed for the exponentially many possibilities of the subset chosen at wiretapper by deriving a lemma which provides a doubly-exponential convergence rate for the probability that, for a fixed choice of the subset, the key is uniform and independent from the public discussion and the wiretapping source's observation. The converse is derived by using Sanov's theorem to upper bound the secrecy capacity of the new wiretap channel model by the secrecy capacity when the tapped subset is randomly chosen by nature.