Stochastic routing in large grid-shaped quantum networks

Abstract

This paper investigates the problem of secret key transmissions for an arbitrary Alice-Bob pair in Quantum Key Distribution (QKD)-based networks. We develop a realistic QKD-based network framework and we show that the key transmission problem on such a framework can be considered as a variant of the classical percolation problem. We also present an adaptive stochastic routing algorithm protect from inevitable eavesdroppers. Simulations were carried out not only to validate our approach, but also to compute critical parameters ensuring security. These results show that large quantum networks with eavesdroppers do provide security. Most applications transport secret keys over the Internet using Public Key Infrastructure (PKI). PKI relies on assumptions about the calculation power of eavesdroppers and the nonexistence of effective algorithms for a certain mathematical “hard” problems. This is not enough for some applications. Quantum Key Distribution (QKD) technology provides proved unconditional security in the key transmissions [1], [2]. However, it has several limitations, most prominently throughput and range [3], [4]. This makes more complex the construction of large QKD-based networks enabling perfectly secret key exchange between members. Besides, large networks are vulnerable, and some intermediate nodes may be controlled by eavesdroppers. This paper studies a model of partially compromised QKD network in which two members want to establish a common key with almost certainty that this key will not be eavesdropped. The contributions are (i) a model of partially compromised QKD networks, (ii) a proposal based on stochastic routing to augment the secrecy, (iii) the use of percolation theory techniques to demonstrates how almost-certainty can be achieved. The remainder is organized as follows. In Section I, we introduce the context and define our problem statement. In Section II, we present a first algorithm and analyze it using percolation theory. In Section III, we present a new secret key agreement scheme that could be considered as an extension of our first proposal. Relations with other works is presented in Section IV and we conclude in Section V. I. A PROPOSED QUANTUM NETWORK FRAMEWORK AND ITS QUESTION OF INTEREST We first state the context of our work (cryptography, QKD links and networks, stochastic routing), then formulate our Fig. 1. A single QKD Link proposal, and introduce percolation theory as the tool we use to evaluate some critical parameters. A. Cryptography basics Suppose Alice wants to transmit a secret message M to Bob over some public network, say the Internet. According to Claude Shannon’s information theory [5], a cipher is perfectly secret if the cipher-text C reveals no information about the message M , i.e., if I(C,M) = 0. The one-time pad cipher can help Alice and Bob to share a perfect secrecy provided that they have a common secret key K that is as long as the message: • Alice sends K to Bob, K has the same size as M . • Alice uses K as an one-time pad key to cipher the private message: C = M ⊕K and sends it. • Bob deciphers C: M = C ⊕K. The question is: how can Alice send K to Bob with perfect secrecy?