When implementing communication protocols in the real world, the idealized conditions that are assumed at the theoretical level often do not hold. At the practical level, one is interested in controlling aspects of the communication that might be considered negligible in the mathematical modeling of the protocol. This effect often renders a large class of protocols with such assumptions unreliable in practice. In this thesis, we attempt to address practical questions that undermine known communication protocols, by either re-modeling the protocols in such a way that they would be robust against practical uncertainties, or demonstrating that they face logical or feasibility problems prior to their implementation. There are two categories of such questions that are addressed here. The first one concerns the uncertainty in the communication system parameters and in particular, the communicating channel. This affects security as well as reliability measures. Reliable transmission of messages in protocols that assume the state of the channel to be perfectly known depends on this assumption. On the other hand, secure transmission of messages, depends on the powers ascribed to the eavesdropping and jamming parties. In quantum information theory, these powers are significantly higher. We start by giving results that have destructive implications for some established protocols in quantum key distribution in presence of a quantum jammer. We then offer a remodeling of communication protocols, that makes them robust to attacks at physical layer, as well as robust to system parameter uncertainties. Of particular interest are integrated services that are possible in quantum communication. Time-sharing between known coding strategies to perform multiple tasks is often sub-optimal. We derive universal codes that achieve full capacity regions of the quantum channel for communicating quantum, public and private messages. The notion of privacy or security in this work is an information theoretic one, that is different from its cryptographic counterpart. Here, we consider strategies that are implemented at the physical layer and are therefore only limited by the physical properties of the system. Given that our coding strategies are as mentioned, robust to uncertainties in the physical properties of the system, they offer a significant advantage to cryptographic methods in practice. The second category of practical questions concerns computability of the known protocols. Here, we specifically address the algorithmic computability of capacity functions. When capacity theorems are theoretically derived, a legitimate question is whether or not these functions can be fed to a machine via an algorithm. Asked differently, are optimal protocols that achieve capacities of channels for different communication tasks, implementable through algorithms? The value of these functions is derived from achievability and converse theorems that ideally establish converging computable sequences from below and above the capacity at any given point. A more relaxed requirement is the question of decidability of such problems. We end this thesis by giving examples of protocols that cannot in general be turned into algorithms that can be computed by Turing machines. We further show that the bounds for capacities achieved by these protocols are in general undecidable.     «

When implementing communication protocols in the real world, the idealized conditions that are assumed at the theoretical level often do not hold. At the practical level, one is interested in controlling aspects of the communication that might be considered negligible in the mathematical modeling of the protocol. This effect often renders a large class of protocols with such assumptions unreliable in practice. In this thesis, we attempt to address practical questions that undermine known communi...     »

Bei der Implementierung von Kommunikationsprotokollen in der realen Welt sind die idealisierten Bedingungen, die auf theoretischer Ebene angenommen werden, oft nicht gegeben. In der Praxis ist man daran interessiert, Aspekte der Kommunikation zu kontrollieren, die in der mathematischen Modellierung des Protokolls als vernachlässigbar angesehen werden könnten. Dieser Effekt macht eine große Klasse von Protokollen mit solchen Annahmen in der Praxis oft unzuverlässig. In dieser Arbeit versuchen wir, praktische Fragen zu klären, die bekannte Kommunikationsprotokolle untergraben, indem wir die Protokolle entweder so neu modellieren, dass sie gegenüber praktischen Unwägbarkeiten robust sind, oder indem wir zeigen, dass sie vor ihrer Implementierung logische oder Machbarkeitsprobleme haben. Es gibt zwei Kategorien von Fragen dieser Art, die hier behandelt werden. Die erste Kategorie betrifft die Unsicherheit der Parameter des Kommunikationssystems und insbesondere des Kommunikationskanals. Dies wirkt sich sowohl auf die Sicherheit als auch auf die Zuverlässigkeit aus. Die zuverlässige Übertragung von Nachrichten in Protokollen, die davon ausgehen, dass der Zustand des Kanals vollkommen bekannt ist, hängt von dieser Annahme ab. Andererseits hängt die sichere Übertragung von Nachrichten von den Kräften ab, die den abhörenden und störenden Parteien zugeschrieben werden. In der Quanteninformationstheorie sind diese Kräfte wesentlich höher. Wir beginnen mit Ergebnissen, die zerstörerische Auswirkungen auf einige etablierte Protokolle zur Verteilung von Quantenschlüsseln in Gegenwart eines Quantenjammers haben. Anschließend bieten wir einen Umbau von Kommunikationsprotokollen an, der sie robust gegenüber Angriffen auf der physikalischen Ebene sowie robust gegenüber Unsicherheiten der Systemparameter macht. Von besonderem Interesse sind die integrierten Dienste, die in der Quantenkommunikation möglich sind. Die Aufteilung der Zeit zwischen bekannten Kodierungsstrategien zur Durchführung mehrerer Aufgaben ist oft suboptimal. Wir leiten universelle Codes ab, die volle Kapazitätsbereiche des Quantenkanals für die Kommunikation von öffentlichen und privaten Quantennachrichten erreichen. Der Begriff der Privatsphäre oder Sicherheit in dieser Arbeit ist ein informationstheoretischer, der sich von seinem kryptographischen Gegenstück unterscheidet. Wir betrachten hier Strategien, die auf der physikalischen Ebene implementiert werden und daher nur durch die physikalischen Eigenschaften des Systems begrenzt sind. Da unsere Kodierungsstrategien, wie erwähnt, robust gegenüber Unsicherheiten in den physikalischen Eigenschaften des Systems sind, bieten sie in der Praxis einen erheblichen Vorteil gegenüber kryptografischen Methoden. Die zweite Kategorie von praktischen Fragen betrifft die Berechenbarkeit der bekannten Protokolle. Hier befassen wir uns speziell mit der algorithmischen Berechenbarkeit von Kapazitätsfunktionen. Wenn Kapazitätssätze theoretisch abgeleitet werden, ist die Frage legitim, ob diese Funktionen über einen Algorithmus an eine Maschine weitergegeben werden können. Anders gefragt, sind optimale Protokolle, die Kapazitäten von Kanälen für verschiedene Kommunikationsaufgaben erreichen, durch Algorithmen implementierbar? Der Wert dieser Funktionen ergibt sich aus Erreichbarkeits- und Umkehrsätzen, die im Idealfall konvergierende berechenbare Sequenzen unterhalb und oberhalb der Kapazität an jedem beliebigen Punkt festlegen. Eine entspanntere Anforderung ist die Frage der Entscheidbarkeit solcher Probleme. Wir beenden diese Arbeit mit Beispielen von Protokollen, die im Allgemeinen nicht in Algorithmen umgewandelt werden können, die von Turingmaschinen berechnet werden können. Wir zeigen außerdem, dass die Schranken für Kapazitäten, die durch diese Protokolle erreicht werden, im Allgemeinen unentscheidbar sind.     «

Bei der Implementierung von Kommunikationsprotokollen in der realen Welt sind die idealisierten Bedingungen, die auf theoretischer Ebene angenommen werden, oft nicht gegeben. In der Praxis ist man daran interessiert, Aspekte der Kommunikation zu kontrollieren, die in der mathematischen Modellierung des Protokolls als vernachlässigbar angesehen werden könnten. Dieser Effekt macht eine große Klasse von Protokollen mit solchen Annahmen in der Praxis oft unzuverlässig. In dieser Arbeit versuchen wir...     »