Uncertainty in Identification Systems
M.T. Vu, T.J. Oechtering, M. Skoglund, H. Boche
IEEE Transactions on Information Theory 67 (3), 1400-1414 (2021).
High-dimensional identification systems consisting of two groups of users in the presence of statistical uncertainties are considered in this work. The task is to design enrollment mappings to compress users' information and an identification mapping that combines the stored information in the database and an observation to estimate the underlying user index. The compression-identification trade-off regions are established for the compound, extended compound, general and mixture settings. It is shown that several settings admit the same compression-identification trade-offs. We then study a connection between the Wyner-Ahlswede-Korner network and the identification setting. It indicates that a strong converse for the WAK network is equivalent to a strong converse for the identification setting. Finally, we present strong converse arguments for the discrete identification setting that are extensible to the Gaussian scenario.
Semantic Security via Seeded Modular Coding Schemes and Ramanujan Graphs
M. Wiese, H. Boche
IEEE Transactions on Information Theory 67 (1), 52-80 (2021).
A novel type of functions called biregular irreducible functions is introduced and applied as security components (instead of, e.g., universal hash functions) in seeded modular wiretap coding schemes, whose second component is an error-correcting code. These schemes are called modular BRI schemes. An upper bound on the semantic security information leakage of modular BRI schemes in a one-shot setting is derived which separates the effects of the biregular irreducible function on the one hand and the error-correcting code plus the channel on the other hand. The effect of the biregular irreducible function is described by the second-largest eigenvalue of an associated stochastic matrix. A characterization of biregular irreducible functions is given in terms of connected edge-disjoint biregular graphs. It allows for the construction of new biregular irreducible functions from families of edge-disjoint Ramanujan graphs, which are shown to exist. A concrete and frequently used arithmetic universal hash function can be converted into a biregular irreducible function for certain parameters. Sequences of Ramanujan biregular irreducible functions are constructed which exhibit an optimal trade-off between the size of the regularity set and the rate of decrease of the associated second-largest eigenvalue. Together with the one-shot bound on the information leakage, the existence of these sequences implies an asymptotic coding result for modular BRI schemes applied to discrete and Gaussian wiretap channels. It shows that the separation of error correction and security as done in a modular BRI scheme is secrecy capacity-achieving for every discrete and Gaussian wiretap channel. The same holds for a derived construction where the seed is generated locally by the sender and reused several times. It is shown that the optimal sequences of biregular irreducible functions used in the above constructions must be nearly Ramanujan.
Extending Quantum Links: Modules for Fiber- and Memory-Based Quantum Repeaters
P. van Loock, W. Alt, C. Becher, O. Benson, H. Boche, C. Deppe, J. Eschner, S. Höfling, D. Meschede, P. Michler, F. Schmidt, H. Weinfurter.
Advancing Quantum Technologies - Chances and Challenges Advanced Quantum Technologies, (2020).
Elementary building blocks for quantum repeaters based on fiber channels and memory stations are analyzed. Implementations are considered for three different physical platforms, for which suitable components are available: quantum dots, trapped atoms and ions, and color centers in diamond. The performances of basic quantum repeater links for these platforms are evaluated and compared, both for present‐day, state‐of‐the‐art experimental parameters as well as for parameters that can in principle be reached in the future. The ultimate goal is to experimentally explore regimes at intermediate distances—up to a few 100 km—in which the repeater‐assisted secret key transmission rates exceed the maximal rate achievable via direct transmission. Two different protocols are considered, one of which is better adapted to the higher source clock rate and lower memory coherence time of the quantum dot platform, while the other circumvents the need of writing photonic quantum states into the memories in a heralded, nondestructive fashion. The elementary building blocks and protocols can be connected in a modular form to construct a quantum repeater system that is potentially scalable to large distances.
On the Algorithmic Solvability of Spectral Factorization and Applications
H. Boche, V. Pohl.
IEEE Transactions on Information Theory 66, 4574-4592 (2020).
Spectral factorization is an operation which appears in many different engineering applications. This paper studies whether spectral factorization can be algorithmically computed on an abstract machine (a Turing machine). It is shown that there exist computable spectral densities with very good analytic properties (i.e. smooth with finite energy) such that the corresponding spectral factor cannot be determined on a Turing machine. Further, it will be proved that it is impossible to decide algorithmically whether or not a given computable density possesses a computable spectral factor. This negative result has consequences for applications of spectral factorization in computer-aided design, because there it is necessary that this problem be decidable. Conversely, this paper will show that if the logarithm of a computable spectral density belongs to certain Sobolev space of sufficiently smooth functions, then the spectral factor is always computable. As an application, the paper discusses the possibility of calculating the optimal causal Wiener filter on an abstract machine.
Message Transmission over Classical Quantum Channels with a Jammer with Side Information: Correlation as Resource, Common Randomness Generation
H. Boche, M. Cai, N. Cai.
Journal of Mathematical Physics 61, 062201 (2020).
In this paper, we analyze the capacity of a general model for arbitrarily varying classical-quantum channels (AVCQCs) when the sender and the receiver use correlation as a resource. In this general model, a jammer has side information about the channel input. We determine a single letter formula for the correlation assisted capacity. As an application of our main result, we determine the correlation assisted common randomness generation capacity. In this scenario, the two channel users have access to correlation as a resource and further use an AVCQC with an informed jammer for additional discussion. The goal is to create common randomness between the two channel users. We also analyze these capacity formulas when only a small number of signals from the correlation are available. For the correlation assisted common randomness generation capacity, we show an additional interesting property: For a sufficient amount of “public communication,” common randomness generation capacity is Turing computable; however, without this public communication constraint, the correlation assisted common randomness generation capacity is, in general, not Turing computable. Furthermore, we show that even without knowing the capacity formula of the deterministic capacity using the maximal error criterion, we can show that it is impossible to evaluate the performance algorithmically on any current or future digital computer.
Denial-of-Service Attacks on Communication Systems: Detectability and Jammer Knowledge
H. Boche, R.F. Schaefer, H.V. Poor.
IEEE Transactions on Signal Processing 68, 3754-3768 (2020).
Wireless communication systems are inherently vulnerable to intentional jamming. In this paper, two classes of such jammers are considered: those with partial and full knowledge. While the first class accounts for those jammers that know the encoding and decoding function, the latter accounts for those that are further aware of the actual transmitted message. Of particular interest are so-called denial-of-service (DoS) attacks in which the jammer is able to completely disrupt any transmission. Accordingly, it is of crucial interest for the legitimate users to detect such adversarial DoS attacks. This paper develops a detection framework based on Turing machines. Turing machines have no limitations on computational complexity and computing capacity and storage and can simulate any given algorithm. For both scenarios of a jammer with partial and full knowledge, it is shown that there exists no Turing machine which can decide whether or not a DoS attack is possible for a given channel and the corresponding decision problem is undecidable. On the other hand, it is shown for both scenarios that it is possible to algorithmically characterize those channels for which a DoS attack is not possible. This means that it is possible to detect those scenarios in which the jammer is not able to disrupt the communication. For all other channels, the Turing machine does not stop and runs forever making this decision problem semidecidable. Finally, it is shown that additional coordination resources such as common randomness make the communication robust against such attacks.
Secure Storage Capacity Under Rate Constraints—Continuity and Super Activation
S. Baur, H. Boche, R.F. Schaefer, H.V. Poor.
IEEE Transactions on Information Forensics and Security 15, 959-970 (2020).
The source model for secret key generation with one way public communication refers to a setting in which a secret key should be agreed upon at two terminals. At both terminals correlated components of a common source are available. In addition, a message can be sent from one terminal to the other via a public channel. In this paper, a related scenario is considered where instead of secret key generation, the goal is to securely store data in a public database. The database allows for error-free storing of the data, but is constrained in its size which imposes a rate constraint on storing. The corresponding capacity for secure storage is known and it has been shown that the capacity-achieving strategy satisfies the strong secrecy criterion. Here, the case when the storage in the public database is subject to errors is considered and the corresponding capacity is characterized. In addition, the continuity properties of the two capacity functions are analyzed. These capacity functions are continuous as opposed to the discontinuous secret key capacity with rate constraint. It is shown that for secure storage the phenomenon of super activation can occur. Finally, it is discussed how the results in this paper differ from previous results on super activation.
Secure Communication and Identification Systems - Effective Performance Evaluation on Turing Machines
H. Boche, R.F. Schaefer, H.V. Poor
IEEE Transactions on Information Forensics and Security 15, 1013-1025 (2020).
Modern communication systems need to satisfy pre-specified requirements on spectral efficiency and security. Physical layer security is a concept that unifies both and connects them with entropic quantities. In this paper, a framework based on Turing machines is developed to address the question of deciding whether or not a communication system meets these requirements. It is known that the class of Turing solvable problems coincides with the class of algorithmically solvable problems so that this framework provides the theoretical basis for effective verification of such performance requirements. A key issue here is to decide whether or not the performance functions, i.e., capacities, of relevant communication scenarios, particularly those with secrecy requirements and active adversaries, are Turing computable. This is a necessary condition for the corresponding communication protocols to be effectively verifiable. Within this framework, it is then shown that for certain scenarios including the wiretap channel the corresponding capacities are Turing computable. Next, a general necessary condition on the performance function for Turing computability is established. With this, it is shown that for certain scenarios, including the wiretap channel with an active jammer, the performance functions are not computable when deterministic codes are used. As a consequence, such performance functions are also not computable on all other computer architectures such as the von Neumann-architecture or the register machines.
Communication Under Channel Uncertainty: An Algorithmic Perspective and Effective Construction
H. Boche, R.F. Schaefer, H.V. Poor
IEEE Transactions on Signal Processing 68, 6224-6239 (2020).
The availability and quality of channel state information heavily influences the performance of wireless communication systems. For perfect channel knowledge, optimal signal processing and coding schemes have been well studied and often closed-form solutions are known. On the other hand, the case of imperfect channel information is less understood and closed-form characterizations of optimal schemes remain unknown in many cases. This paper approaches this question from a fundamental, algorithmic point of view by studying whether or not such optimal schemes can be constructed algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). To this end, the concepts of compound channels and averaged channels are considered as models for channel uncertainty and block fading and it is shown that, although the compound channel and averaged channel themselves are computable channels, the corresponding capacities are not computable in general, i.e., there exists no algorithm (or Turing machine) that takes the channel as an input and computes the corresponding capacity. As an implication of this, it is then shown that for such compound channels, there are no effectively constructible optimal (i.e., capacity-achieving) signal processing and coding schemes possible. This is particularly noteworthy as such schemes must exist (since the capacity is known), but they cannot be effectively, i.e., algorithmically, constructed. Thus, there is a crucial difference between the existence of optimal schemes and their algorithmic constructability. In addition, it is shown that there is no search algorithm that can find the maximal number of messages that can be reliably transmitted for a fixed blocklength. Finally, the case of partial channel knowledge is studied in which either the transmitter or the receiver have perfect channel knowledge while the other part remains uncertain. It is shown that also in the cases of an informed encoder and informed decoder, the capacity remains non-computable in general and, accordingly, optimal signal processing and coding schemes are not effectively constructible.
Secret message transmission over quantum channels under adversarial quantum noise: Secrecy capacity and super-activation
H. Boche, M. Cai, J. Nötzel, C. Deppe.
Journal of Mathematical Physics 60, 062202-1 to 062202-39 (2019).
We determine the secrecy capacities of arbitrarily varying quantum channels (AVQCs). Both secrecy capacities with average error probability and with maximal error probability are derived. Both derivations are based on one common code construction. The code we construct fulfills a stringent secrecy requirement, which is called the strong code concept. As an application of our result for secret message transmission over AVQCs, we determine when the secrecy capacity is a continuous function of the system parameters and completely characterize its discontinuity points both for average error criterion and for maximal error criterion. Furthermore, we prove the phenomenon “superactivation” for secrecy capacities of arbitrarily varying quantum channels, i.e., two quantum channels both with zero secrecy capacity, which, if used together, allow secure transmission with positive capacity. We give therewith an answer to the question “When is the secrecy capacity a continuous function of the system parameters?,” which has been listed as an open problem in quantum information problem page of the Institut für Theoretische Physik (ITP) Hannover. We also discuss the relations between the entanglement distillation capacity, the entanglement generating capacity, and the strong subspace transmission capacity for AVQCs. Ahlswede et al. made in 2013 the conjecture that the entanglement generating capacity of an AVQC is equal to its entanglement generating capacity under shared randomness assisted quantum coding. We demonstrate that the validity of this conjecture implies that the entanglement generating capacity, the entanglement distillation capacity, and the strong subspace transmission capacity of an AVQC are continuous functions of the system parameters. Consequently, under the premise of this conjecture, the secrecy capacities of an AVQC differ significantly from the general quantum capacities.
Message Transmission Over Classical Quantum Channels With a Jammer With Side Information: Message Transmission Capacity and Resources
H. Boche, M. Cai, N. Cai.
IEEE Transactions on Information Theory 65 (5), 2922 - 2943 (2019).
In this paper, a new model for arbitrarily varying classical-quantum channels is proposed. In this model, a jammer has side information. The communication scenario in which a jammer can select only classical inputs as a jamming sequence is considered in the first part of the paper. This situation corresponds to the standard model of arbitrarily varying classical-quantum channels. Two scenarios are considered. In the first scenario, the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. The capacity for both average and maximum error criteria for both scenarios is determined in this paper. A strong converse is also proved. It is shown that all these corresponding capacities are equal, which means that additionally revealing the message to the jammer does not change the capacity. The communication scenario with a fully quantum jammer is considered in the second part of the paper. A single letter characterization for the capacity with secret random key as assistance for both average and maximum error criteria is derived in the paper.
Simultaneous transmission of classical and quantum information under channel uncertainty and jamming attacks
H. Boche, G. Janssen, S. Saeedinaeeni.
Journal of Mathematical Physics 60, 022204 (2019).
We derive universal codes for simultaneous transmission of classical messages and entanglement through quantum channels, possibly under the attack of a malignant third party. These codes are robust to different kinds of channel uncertainties. To construct such universal codes, we invoke and generalize the properties of random codes for classical and quantum message transmission through quantum channels. We show these codes to be optimal by giving a multi-letter characterization of regions corresponding to capacity of compound quantum channels for simultaneously transmitting and generating entanglement with classical messages. In addition, we give dichotomy statements in which we characterize the capacity of arbitrarily varying quantum channels for simultaneous transmission of classical messages and entanglement. These include cases where the malignant jammer present in the arbitrarily varying channel model is classical (chooses channel states of the product form) and fully quantum (is capable of general attacks not necessarily of the product form).