Quantum key distribution is renowned for information-theoretic security on point-to-point connections, while it is by itself not directly capable of end-to-end security. Multipath transmission is known for perfect end-to-end security, provided that perfect point-to-point security is achievable. The marriage of the two is as natural as it is difficult to achieve in real life networks: secure multipath transmission imposes stringent requirements on the network connectivity, perhaps rarely found in a real-life network infrastructure. We consider the problem of network augmentation to support perfect end-to-end security in a network in which adjacent nodes share a perfectly confidential channel. Quantum networks are one example for this. Starting with a decision-theoretic formalization of risk and confidentiality, we cast the network augmentation task into a nonlinear optimization problem, whose computational complexity is studied. With the problem turning out NP-hard in at least two of its variants, we sketch heuristics that can help to keep calculations feasible in practical applications.
Quantum key distribution is renowned for information-theoretic security on point-to-point connections, while it is by itself not directly capable of end-to-end security. Multipath transmission is known for perfect end-to-end security, provided that perfect point-to-point security is achievable. The marriage of the two is as natural as it is difficult to achieve in real life networks: secure multipath transmission imposes stringent requirements on the network connectivity, perhaps rarely found in a real-life network infrastructure. We consider the problem of network augmentation to support perfect end-to-end security in a network in which adjacent nodes share a perfectly confidential channel. Quantum networks are one example for this. Starting with a decision-theoretic formalization of risk and confidentiality, we cast the network augmentation task into a nonlinear optimization problem, whose computational complexity is studied. With the problem turning out NP-hard in at least two of its variants, we sketch heuristics that can help to keep calculations feasible in practical applications.
Information-theoretic secrecy is the strongest known security notion. Despite perfect secrecy being theoretically well-understood, one faces substantial practical difficulties when attempting to build communication systems providing this highest level of security. We consider two major approaches to perfectly secure communication: multipath transmission and quantum key distribution. The latter has seen a promising evolution over the last decades, culminating in the recent presentations of the world’s first real-life quantum networks. This book advocates a combination of the two techniques in order to complement each other and to overcome existing limitations in both worlds. Getting started with a graph-theoretic groundwork for multipath transmission networks, we continue by deriving results about multipath channel coding and interactive error correction. Based on game-theory, we introduce a general quantitative security valuation enjoying broad applicability. For a given network, the security measure indicates the quality of protection as well as it permits security infrastructure optimization. Both topics receive attention in dedicated chapters.
Quantum networks are communication networks in which adjacent nodes enjoy perfectly secure channels thanks to quantum key distribution (QKD). Drawing end- to-end security from QKD-supported point-to-point security can be done by virtue of multipath transmission. This concept buys security at the cost of strongly connected networks and perfect routing. Particularly the latter is hard to ensure, since congestions or (passive) may cause QKD key- buffers to run empty, thus enforcing local re-routing of packets. Hence, the adversary may use not to extract information, but to redirect the information flow towards a relay-node that he controls. Such attacks can readily invalidate the stringent requirements of multipath transmission protocols and thus defeat any formal arguments for perfect secrecy. Moreover, this form of indirect eavesdropping seems to be unconsidered in the literature so far. We investigate whether or not unconditional security in a quantum network with non- reliable routing is possible. Using Markov-chains, we derive various sufficient criteria for retaining perfect secrecy under imperfect packet relay. In particular, we explicitly do not assume trusted relay or quantum repeaters available. Keywords-Quantum Cryptography, Markov-Chain, Secure
Abstract—Quantum networks are communication networks in which adjacent nodes enjoy perfectly secure channels thanks to quantum key distribution (QKD). While QKD is renowned for perfect point-to-point security and its eavesdropping detec-tion capabilities, end-to-end security is nontrivial to achieve. More importantly, the eavesdropping detection can indeed be turned against the system itself. It is known that perfect end-to-end security can be created from point-to-point security by means of multipath transmission (in fact, there is no other way to do this, assuming no pre-shared secrets and avoiding public-key cryptography). However, multipath transmission requires node-disjoint paths, which in turn are to be assured by the underlying routing protocol. At this point, an active or passive adversary may intentionally eavesdrop on the QKD protocol to temporarily cut a channel and to cause key-buffers running empty and enforcing local rerouting of packets towards nodes under his control. Consequently, the multipath transmission channels might no longer be non-intersecting, thus defeating the overall security by exploiting QKD’s eavesdropping detec-tion facilities. Alternatively, an active adversary may as well insert bogus traff c to cause local congestion, thus even sparing the effort of eavesdropping on a QKD link. In this work, we use Markov chains to model a multipath transmission, and we discuss the extent to which secure multipath transmission is resilient against local congestions caused by an adversary. We argue that a protection against an active adversary who uses bogus traff c to f ddle with the routing, calls for additional security measures, perhaps even beyond the capabilities of QKD or multipath transmission. It turns out that robustness against passive and active adversaries can be retained as long as no bogus traff c is observed.
We present a general framework for casting the problem of designing secure quantum networks into a classical optimization problem. We introduce a measure of risk that serves as upper bound on the probability of loosing a message to the adversary. Based on this results, we can transform the problem of secure network design into an optimization procedure, which opens the field for the entire framework of optimization theory to tackle the problem most efficiently. The latter is particularly appealing, since we prove the problem to be NP-hard in general. Our methodology is formulated to yield results that have interpretations in probabilistic terms, but can be generalized to other settings in a straightforward manner. The modeling approach is simple, and naturally accounts for different notions of security, depending on the situation at hand. Furthermore, our results are not limited to security in quantum networks, as we rely on quantum cryptography only to the extent of securing links. Hence, the analysis is equally applicable for any (multipath) transmission setup, where information-theoretic security is demanded.
Shannon showed that to achieve perfect secrecy in point-to-point communication, the message rate cannot exceed the shared secret key rate giving rise to the simple one-time pad encryption scheme. In this paper, we extend this work from point-to-point to networks. We consider a connected network with pairwise communication between the nodes. We assume that each node is provided with a certain amount of secret bits before communication commences. An eavesdropper with unlimited computing power has access to all communication and can hack a subset of the nodes not known to the rest of the nodes. We investigate the limits on information-theoretic secure communication for this network. We establish a tradeoff between the secure channel rate (for a node pair) and the secure network rate (sum over all node pair rates) and show that perfect secrecy can be achieved if and only if the sum rate of any subset of unhacked channels does not exceed the shared unhacked-secret-bit rate of these channels. We also propose two practical and efficient schemes that achieve a good balance of network and channel rates with perfect secrecy guarantee. This work has a wide range of potential applications for which perfect secrecy is desired, such as cyber-physical systems, distributed-control systems, and ad-hoc networks.
Shannon showed that to achieve perfect secrecy in point-to-point communication, the message rate cannot exceed the shared secret key rate giving rise to the simple one-time pad encryption scheme. In this paper, we extend this work from point-to-point to networks. We consider a connected network with pairwise communication between the nodes and assume that each node is provided with a certain amount of secret bits before communication commences. An eavesdropper with unlimited computing power has access to all communication and can hack a subset of the nodes not known to the rest of the nodes. We investigate the limits on information-theoretic secure communication with end-to-end encryption for this network. We establish a tradeoff between the secure channel rate (for a node pair) and the secure network rate (sum over all node pair rates) and show that information-theoretic secrecy can be achieved asymptotically if and only if the sum rate of any subset of unhacked channels does not exceed the shared unhacked-secret-bit rate of these channels. We also propose a practical scheme that achieves a good balance of network and channel rates with information-theoretic secrecy guarantee. This work has a wide range of potential applications for which strong secrecy is desired, such as cyber-physical systems, distributed-control systems, and ad-hoc networks.