Routing Algorithm Within the Multiple Non-Overlapping Paths’ Approach for Quantum Key Distribution Networks

Abstract

We develop a novel key routing algorithm for quantum key distribution (QKD) networks that utilizes a distribution of keys between remote nodes, i.e., not directly connected by a QKD link, through multiple non-overlapping paths. This approach focuses on the security of a QKD network by minimizing potential vulnerabilities associated with individual trusted nodes. The algorithm ensures a balanced allocation of the workload across the QKD network links, while aiming for the target key generation rate between directly connected and remote nodes. We present the results of testing the algorithm on two QKD network models consisting of 6 and 10 nodes. The testing demonstrates the ability of the algorithm to distribute secure keys among the nodes of the network in an all-to-all manner, ensuring that the information-theoretic security of the keys between remote nodes is maintained even when one of the trusted nodes is compromised. These results highlight the potential of the algorithm to improve the performance of QKD networks.

1. Introduction

Quantum key distribution (QKD) technologies represent an elegant mechanism for solving the key distribution problem [1,2,3], which is one of the central tasks of cryptography. Existing QKD protocols rely on the use of quantum channels for transmitting information that is encoded in quantum states of single photons (in practice, the transmission of weak laser pulses via fiber-optic and free-space communication channels is used) and authentic classical channels [1]. The idea behind this is that any interception in the process of transmitting quantum information can be detected by monitoring the quantum bit error rate (QBER) in the quantum channel, while authentication of classical communications is needed for the protection from man-in-the-middle attack during post-processing procedures [1,2]. In the view of the fact that the security of QKD is based on the laws of quantum physics, it is guaranteed to be secure against any unforeseen technological developments, such as cryptoanalysis using quantum computing [4]. QKD technologies have attracted a great deal of interest and they are a widely studied field of quantum technologies [3,5]. At the same time, existing realizations of QKD systems still face a number of challenges [5], such as limitations in the key generation rate and distance, as well as practical security.

One of the ways to overcome distance limitations, which are essentially related to losses during the transfer of quantum states, is to use QKD networks [6]. Moreover, QKD networks make key generation services available for multiple users. In the case of quantum communications, standard repeater schemes cannot be used, so quantum repeaters [7,8,9] are required. Despite significant progress in this field during recent decades (e.g., see Refs. [10,11,12,13]), quantum repeaters are not yet widely used in industrial QKD networks.

The most developed concept for large-scale, industrial QKD networks is to use trusted nodes [14,15,16,17,18,19,20], which play a role of a user in a QKD protocol that composes a common secret key by using the bit-wise XOR operation for two established keys with neighboring nodes. The negative side of the trusted-node paradigm is that all the users of the network must trust the node and that it needs to be physically well isolated, while the positive side is a reduction in costs and complexity as compared to the all connected point-to-point links. At this stage, the deployment of QKD networks faces the problem of optimal routing, which has the goal of optimally using resources of a network when establishing keys between two arbitrary users. Existing QKD networks solve the routing problem by means of various protocols [21,22,23,24,25,26,27,28,29,30,31,32] and tools (such as optical switches [18,33,34]); however, this problem is far from being fully solved, especially in the case of QKD networks of arbitrary topology [26,27,28,29,30,31,32].

In this work, we consider the key routing task within the multiple non-overlapping paths’ approach [35,36,37,38,39]. The idea of this approach is to minimize the requirement for trust by distributing a key across remote nodes via independent routes. This ensures that the final key remains secure, provided that all trusted nodes on at least one route remain secure. We propose a routing algorithm that is specifically designed for use with the multiple non-overlapping paths’ approach. This algorithm differs from previously considered algorithms for single-path routing [21,22,24,29,31] in that it is tailored to handle the unique requirements of the multiple non-overlapping path scenario. The developed algorithm differs from that proposed in [25] by incorporating the limited capacity for key generation in networks and addressing the routing issue for all nodes simultaneously. At the same time, it differs from the more recent scheme for hybrid trusted networks [30] in that all nodes in the network are assumed to have equal trust in it. Importantly, key routing algorithms designed for the standard single-path trusted node schemes do not guarantee the efficiency of a key distribution in the context of the non-overlapping paths’ approach. To address this challenge, we propose and test the first key routing algorithm, to our knowledge, which is specifically tailored for the non-overlapping paths’ framework.

This paper is organized as follows: In Section 2, we discuss the basic features of the multiple non-overlapping paths’ approach. In Section 3, we present the developed routing algorithm. In Section 4, we demonstrate the performance of the algorithm on two QKD network models. Finally, we conclude this article in Section 5.

2. The Concept of the $\mathit{M}$–Paths’ Scheme

To overcome the limitation of the QKD range, multiple short point-to-point QKD links are combined into QKD networks with so-called intermediate trusted nodes [6,40]. In this approach, quantum keys are generated only between the network nodes connected directly by a quantum channel, and trusted nodes perform a key hopping via subsequent bit-wise XOR operations. With the use of this technology, it is possible to build QKD networks of various topologies, like backbone, ring, star or a mixed one.

The downside of the trusted node paradigm is that remote network nodes have to trust the physical integrity of all nodes in the chain between them. It is possible to relax the trust requirement and increase the security by considering an M non-overlapping paths’ approach [35,36,37,38,39], where the secret key between two remote nodes is obtained by combining keys from M (with $M>1$) non-overlapping paths. In the following, we refer to it as the M–paths’ approach. We would like to note that, in this context, we refer to a path as an independent key hopping route. From a physical perspective, such independent paths can be realized even within a single transmission line, where certain nodes may be skipped, as is the case of quantum control-based key distribution networks [41,42].

Let us consider a communication between remote nodes i and j via a set of M non-overlapping paths ${\mathcal{P}}_{ij}^M$. Let each path $P\in {\mathcal{P}}_{ij}^M$ provide an ℓ–bit information-theoretically secure key ${\mathcal{K}}_{ij}^P$. Then, the final ℓ–bit secret key to be used for the unconditionally secure data encryption with the one-time pad (OTP) technique can be obtained as follows:

$${\mathcal{K}}_{ij}=\underset{P\in {\mathcal{P}}_{ij}^M}{⨁}{\mathcal{K}}_{ij}^P,$$

(1)

where ⨁ stands for a bit-wise exclusive or (XOR) operation. Therefore, due to the perfect secrecy of the OTP, the eavesdropping becomes technically more complicated in the M–path scheme since the intermediate nodes from each of M paths must be hacked (compromised) in order to reconstruct the entire secret key. Equivalently, compromising fewer than M nodes from ${\mathcal{P}}_{ij}^M$ would not compromise ${\mathcal{K}}_{ij}$. Assuming a probability of compromise of a node operated as a trusted node is ${ϵ}_{\mathrm{compr}}$, we can estimate that the probability of compromising a key between any two remote nodes in the M–paths’ regime is upper-bounded by ${ϵ}_{\mathrm{compr}}^M$.

Here, we would like to emphasize several points related to the M–paths’ scheme. First, the applicability of M–path schemes strictly depends on the topology of QKD networks. It is impossible to use this scheme in backbone-type networks, where there is only a single path between two remote nodes, or to apply a three-path scheme within a ring topology of the network graph. Second, distributing an ℓ–bit key using the M–path scheme reduces the remaining keys by ℓ bits for each direct link in each path (we discuss this in more detail in the following section). Therefore, increasing M also increases the “cost” of distributing keys between remote nodes in terms of the remaining key between network nodes. In this regard, the selection of M within the range allowed by the topology should consider a balance between the desired security level, estimated as ${ϵ}_{\mathrm{compr}}^M$, and the increased key usage in the network. Thirdly, the secret key ${\mathcal{K}}_{ij}$ can be obtained by concatenating several keys corresponding to different M–element sets of non-overlapping paths ${\left\{{\mathcal{P}}_{ij}^{M\left(k\right)}\right\}}_k$:

$${\mathcal{K}}_{ij}=\left(\underset{P\in {\mathcal{P}}_{ij}^{M\left(1\right)}}{⨁}{\mathcal{K}}_{ij}^P\right)\parallel \left(\underset{P^{\prime }\in {\mathcal{P}}_{ij}^{M\left(2\right)}}{⨁}{\mathcal{K}}_{ij}^{P^{\prime }}\right)\parallel \dots ,$$

(2)

where $\parallel$ denotes concatenation. It should be noted that some of the paths in the sets ${\left\{{\mathcal{P}}_{ij}^{M\left(k\right)}\right\}}_k$ may have common elements. Additionally, the lengths of concatenated parts may differ. The construction of ${\mathcal{K}}_{ij}$ in the form of Equation (2), assuming it is permitted by the network topology, enables a more balanced distribution of key consumption across the network. The last point raises an important challenge in finding a practical and efficient key routing algorithm within the M–path approach for QKD networks of arbitrary topology. This algorithm should allow for the selection of suitable combinations of paths in order to distribute keys between pairs of remote nodes. Additionally, it should ensure a sufficient reserve of available keys for directly connected nodes. We consider the construction of such an algorithm in the section below.

3. Routing Algorithm for the $\mathit{M}$–Path Scheme

We begin with introducing some formal definitions and notations used later. An arbitrary QKD network with N nodes is represented as a graph $G=(V,E)$, where the vertices $V={\left\{i\right\}}_{i=0}^{N-1}$ are the network nodes and the edges $E\subseteq \left\{\right(i,j\left)\right|i,j\in V\}$ are the fiber optic lines connecting them. The edge weight corresponds to the secret key generation rate of the corresponding section of the fiber optic line. The definition of the M–path routing scheme obviously implies that the degree of each vertex, i.e., the number of edges that are incident to the vertex, is required to be $deg\left(i\right)\ge M$. A path in a graph is a finite sequence of edges which joins a sequence of distinct vertices. An open path from Node i to Node j can be defined in a short way as a sequence of adjacent vertices, connected by edges,

$$P_{ij}≔(i,k,l,\cdots ,m,j),$$

(3)

with $(i,k),(k,l),\cdots ,(m,j)\in E$.

Let $R_{ij}=R_{ji}$ be the secret key generation rate for a pairwise QKD link or chain of links connecting nodes i and j such that $R_{ij}>0$ if $(i,j)\in E$ is zero. The average length of the local secret key, $K_{ij}$, accumulated during some time period $\tau$, is equal to $|K_{ij}|=R_{ij}\tau$. Let $T_{ij}$ be a target secret key generation rate between the nodes i and j, which can be associated with the key consumption rate. Note that it is possible to have $T_{ij}>0$ even if $(i,j)\notin E$. Then, the goal is to develop a (sub)optimal key flow that provides the desired $T_{ij}$ for all pairs $(i,j)$ by manipulating the effective key rates $R_{ij}^{\mathrm{eff}}$.

To illustrate the concept of the effective rate, consider a simple network of five nodes in Figure 1 and set $M=2$. The communication between the remote nodes 0 and 4 ($R_{04}\equiv 0$) in the 2–path scheme can be completed via three possible pairs of non-overlapping paths,

$$\begin{array}{c}\hfill {\mathcal{P}}_{04}^{2\left(1\right)}=\left\{\right(0,1,4),(0,2,4\left)\right\},\\ \hfill {\mathcal{P}}_{04}^{2\left(2\right)}=\left\{\right(0,2,4),(0,3,4\left)\right\},\\ \hfill {\mathcal{P}}_{04}^{2\left(3\right)}=\left\{\right(0,1,4),(0,3,4\left)\right\},\end{array}$$

(4)

while the communication between nodes 1 and 3 ($R_{13}\equiv 0$) is feasible only via one pair,

$${\mathcal{P}}_{13}^2=\{(1,0,3),(1,4,3)\}.$$

(5)

Every local accumulated secret key $K_{ij}$ is split into subsamples in the following way:

$$\begin{array}{c}{K}_{01}=K_{01}^{\mathrm{eff}}\parallel \delta K_{01}^{(0,1,4)}\parallel \delta K_{01}^{(0,1,4)\prime }\parallel \delta K_{01}^{(1,0,3)},\hfill \\ K_{02}=K_{02}^{\mathrm{eff}}\parallel \delta K_{02}^{(0,2,4)}\parallel \delta K_{02}^{(0,2,4)\prime },\hfill \\ K_{03}=K_{03}^{\mathrm{eff}}\parallel \delta K_{03}^{(0,3,4)}\parallel \delta K_{03}^{(0,3,4)\prime }\parallel \delta K_{03}^{(1,0,3)},\hfill \\ K_{14}=K_{14}^{\mathrm{eff}}\parallel \delta K_{14}^{(0,1,4)}\parallel \delta K_{14}^{(0,1,4)\prime }\parallel \delta K_{14}^{(1,4,3)},\hfill \\ K_{24}=K_{24}^{\mathrm{eff}}\parallel \delta K_{24}^{(0,2,4)}\parallel \delta K_{24}^{(0,2,4)\prime },\hfill \\ K_{34}=K_{34}^{\mathrm{eff}}\parallel \delta K_{34}^{(0,3,4)}\parallel \delta K_{34}^{(0,3,4)\prime }\parallel \delta K_{34}^{(1,4,3)},\hfill \end{array}$$

(6)

where the keys $\delta K_{ij}^{P(\prime )}$ are sacrificed for the key hopping through the path P with the OTP technique, while the remaining effective keys $K_{ij}^{\mathrm{eff}}$ are used for direct communication between connected nodes. We note that $\delta K_{ij}^P\ne \delta K_{ij}^{P\prime }$ since the path belongs to different M–path sets (see Equation (4)). The OTP technique requires the key lengths to satisfy the following conditions:

$$\begin{array}{cc}\hfill & |\delta K_{01}^{(0,1,4)}|=|\delta K_{14}^{(0,1,4)}|=|\delta K_{02}^{(0,2,4)}|=|\delta K_{24}^{(0,2,4)}|,\hfill \\ \hfill & |\delta K_{02}^{(0,2,4)\prime }|=|\delta K_{24}^{(0,2,4)\prime }|=|\delta K_{03}^{(0,3,4)}|=|\delta K_{34}^{(0,3,4)}|,\hfill \\ \hfill & |\delta K_{01}^{(0,1,4)\prime }|=|\delta K_{14}^{(0,1,4)\prime }|=|\delta K_{03}^{(0,3,4)\prime }|=|\delta K_{34}^{(0,3,4)\prime }|,\hfill \\ \hfill & |\delta K_{01}^{(1,0,3)}|=|\delta K_{03}^{(1,0,3)}|=|\delta K_{14}^{(1,4,3)}|=|\delta K_{34}^{(1,4,3)}|.\hfill \end{array}$$

Then, the final effective keys to encrypt the communication between remote nodes are formed according to Equation (2):

$$\begin{array}{cc}\hfill K_{04}^{\mathrm{eff}}& =\left(\delta K_{01}^{(0,1,4)}\oplus \delta K_{02}^{(0,2,4)}\right)\hfill \\ \hfill & \parallel \left(\delta K_{02}^{(0,2,4)\prime }\oplus \delta K_{03}^{(0,3,4)}\right)\hfill \\ \hfill & \parallel \left(\delta K_{01}^{(0,1,4)\prime }\oplus \delta K_{03}^{(0,3,4)\prime }\right),\hfill \\ \hfill K_{13}^{\mathrm{eff}}& =\delta K_{01}^{(1,0,3)}\oplus \delta K_{14}^{(1,4,3)}.\hfill \end{array}$$

(7)

Now, having all nodes “connected”, we can define the effective generation rate for arbitrary pair of nodes in the network as

$$R_{ij}^{\mathrm{eff}}≔{\displaystyle \frac{|K_{ij}^{\mathrm{eff}}|}{\tau }}>0.$$

(8)

It is easy to see that $R_{ij}^{\mathrm{eff}}<R_{ij}$ for all $(i,j)\in E$. In this way, the key management task is to find an optimal set of $\delta K_{ij}^{P(\prime )}$ in Equation (6) such that $R_{ij}^{\mathrm{eff}}\ge T_{ij}$ for all $i,j\in V$.

Here, we would like to draw attention to the fact that all OTP-secured communications must be authenticated, which also requires the use of a secret key. Due to the fixed consumption of secret keys in the authentication of each message, it is more efficient in practice to increase the interval between “key distribution rounds” and, consequently, the length of the keys transmitted in each message. This approach helps to minimize the relative costs associated with authentication. In the following section, we assume that the key consumption for authentication can be neglected compared to the transmitted key material.

The proposed routing Algorithm 1 follows an iterative process (see an example of a step-by-step workflow in Appendix A). As the basic target quantity to be minimized in each iteration, we consider

$$\Delta ≔\underset{i,j\in V}{max}\left[T_{ij}-R_{ij}^{\mathrm{eff}}\right],$$

(9)

which provides the discrepancy between the target and effective rates for the “worst” pair of nodes. Having $\Delta \le 0$ means that the goal is achieved, and thus the algorithm can be stopped. At every iteration $r=1,2,\cdots ,r_{max}$, where the hyperparameter $r_{max}$ stands for the maximal allowed number of iterations, we first search for the currently “worst” pair of nodes in the graph (i.e., with maximum value of $\Delta$), denoted by $(i^{*},j^{*})$. If the found pair is connected directly, then the algorithm stops. In the case of multiple pair candidates, a random candidate is selected. Then, among all possible sets of M non-overlapping paths from $i^{*}$ to $j^{*}$, denoted by ${\mathcal{L}}_{i^{*}{j}^{*}}^M$, the optimal set ${\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}$ is selected by searching for a set that has a path containing a pair of connected nodes with the minimal rate deficiency. In Algorithm 1, we formalize it by introducing the deficiency function $\mathbf{D}(·)$, which returns the maximal deficiency among all direct links within an input set of M non-overlapping paths. Again, if multiple candidates are found, a random candidate over candidates with the minimal total length is selected (this is formalized by the rand_ch_min_dist$(·)$ function). When the optimal M–path combination is determined, $R_{i^{*}{j}^{*}}^{\mathrm{eff}}$ is increased by a small amount of $\delta R$ (which is an input hyperparameter of the algorithm), while $R_{ij}^{\mathrm{eff}}$ is decreased by $\delta R$ for all adjacent nodes from every path in ${\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}$.

After that, we calculate the new value of the cost function according to Equation (9) and store it in ${\Delta }_{\mathrm{upd}}$. If the new value is “worse” than the one in the beginning of the iteration (${\Delta }_{\mathrm{upd}}>\Delta$), then the algorithm stops; otherwise, the information about the obtained key routing path ${\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}$ between $i^{*}$ and $j^{*}$ is added to the list $\mathsf{routing}$_$\mathsf{list}$, and the algorithm proceeds to the next iteration. Here, we assume that $\mathsf{routing}$_$\mathsf{list}$ consists of records of the form $({\mathcal{P}}_{i^{\prime }{j}^{\prime }}^M:R^{\prime })$. Each of these records means that during some fixed time period $\tau$, a key of length $R^{\prime }\tau$ has to be distributed between $i^{\prime }$ and $j^{\prime }$ over M paths in ${\mathcal{P}}_{i^{\prime }{j}^{\prime }}^M$. Thus, if $\mathsf{routing}$_$\mathsf{list}$ already contains a record of the form $({\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}:R_{i^{*}{j}^{*}}^{\mathrm{cur}})$, then it is replaced by $({\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}:R_{i^{*}{j}^{*}}^{\mathrm{cur}}+\delta R)$, or, otherwise, the new record $({\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}:\delta R)$ is added.

Algorithm 1:
Require: $\left(R_{ij}\right)$, $\left(T_{ij}\right)$, $\delta R$, $r_{max}$
Ensure: $\mathsf{routing}$_$\mathsf{list}$
$R_{ij}^{\mathrm{eff}}=R_{ij}\forall i,j\in V$	▹ initialization of the effective key generation matrix
$r=0$	▹ initialization of iteration counter
$\mathsf{routing}$_$\mathsf{list}$ = [ ]	▹ initialization of empty routing list
$\Delta ={max}_{i,j\in V}[T_{ij}-R_{ij}]$
while $\Delta >0\wedge r<r_{max}$do
$D(i,j)≔T_{ij}-R_{ij}^{\mathrm{eff}}$	▹ current rate deficiency function
$(i^{*},j^{*})=\mathtt{rand}\text{\_}\mathtt{ch}\left\{{arg\; max}_{i,j\in V}D(i,j)\right\}$	▹ selecting a random pair over pairs with the “worst” deficiency
if $(i^{*},j^{*})\in E$ then
return $\mathsf{routing}$_$\mathsf{list}$	▹ stopping the algorithm
end if
${\mathcal{P}}_{i^{*}{j}^{*}}=\{P=(i^{*},\cdots ,j^{*})\}$	▹ set of all possible paths from $i^{*}$ to $j^{*}$
${\mathcal{L}}_{i^{*}{j}^{*}}^M=\{{\mathcal{P}}_{i^{*}{j}^{*}}^M=\{P\in {\mathcal{P}}_{i^{*}{j}^{*}}:P\cap P^{\prime }=\{i^{*},j^{*}\}\forall P^{\prime }\in {\mathcal{P}}_{i^{*}{j}^{*}}^M,P^{\prime }\ne P\}:|{\mathcal{P}}_{i^{*}{j}^{*}}^M|=M\}$  ▹ list of all possible combinations of M non-overlapping paths from $i^{*}$ to $j^{*}$
$\mathbf{D}\left({\mathcal{P}}_{i^{*}{j}^{*}}^M\right)≔{max}_{P\in {\mathcal{P}}_{i^{*}{j}^{*}}^M}{max}_{(i,j)\in P}D(i,j)$  ▹ deficiency function which characterizes the M–path combination capacity (“deficiency of the worst link in the worst path”)
${\mathcal{P}}_{i^{*}{j}^{*}}^{M,\text{pre-opt}}={arg\; min}_{{\mathcal{P}}_{i^{*}{j}^{*}}^M\in \mathcal{L}}\mathbf{D}\left({\mathcal{P}}_{i^{*}{j}^{*}}^M\right)$
${\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}=\mathtt{rand}\text{\_}\mathtt{ch}\text{\_}\mathtt{min}\text{\_}\mathtt{dist}\left\{{\mathcal{P}}_{i^{*}{j}^{*}}^{M,\text{pre-opt}}\right\}$	▹ taking the optimal M–path combination
$R_{i^{*}{j}^{*}}^{\mathrm{eff}}=R_{i^{*}{j}^{*}}^{\mathrm{eff}}+\delta R$	▹ increase the effective key rate for the “worst” pair
for all $P\in {\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}$ do
for all $i,j\in P:(i,j)\in E$ do
$R_{ij}^{\mathrm{eff}}=R_{ij}^{\mathrm{eff}}-\delta R$	▹ decrease the effective key rates for adjacent pairs
end for
end for
${\Delta }_{\mathrm{upd}}={max}_{i,j\in V}[T_{ij}-R_{ij}^{\mathrm{eff}}]$
if ${\Delta }_{\mathrm{upd}}\le \Delta$ then
update $\mathsf{routing}$_$\mathsf{list}$ with a record $({\mathcal{P}}_{i^{*}{j}^{*}}^{M,\mathrm{opt}}:\delta R)$
$\Delta ={\Delta }_{\mathrm{upd}}$	▹ updating the value if the cost and function
$r=r+1$	▹ incrementing the counter
else
return $\mathsf{routing}$_$\mathsf{list}$	▹ stopping the algorithm
end if
end while
return $\mathsf{routing}$_$\mathsf{list}$

Finally, we would like to discuss the role of two hyperparameters: $r_{max}$ and $\delta R$. By bounding the number of iterations, $r_{max}$ limits the maximum running time of the algorithm. One can also consider replacing the condition $r<r_{max}$ in the main loop of the algorithm by a condition that checks if the current running time is less than the maximum allowed time. If there are no limits on running time, $r_{max}$ can be set to infinity. $\delta R$ determines the size of the step at each iteration. A smaller $\delta R$ results in more iterations and a higher precision in the final value of the cost function ($\Delta$). As we will see in the testing in the next section, reducing $\delta R$ can improve the cost function by the amount of $\delta R$. However, from a practical perspective, it is not advisable to reduce $\delta R$ below a level corresponding to the typical cost of a secret key for authentication purposes, assumed to be negligible within the construction of the algorithm.

4. Performance Demonstration of the Algorithm

To demonstrate the performance of the developed algorithm, we consider the task of routing the key within the 2–path scheme for two examples of QKD networks.

The first QKD network is represented by a six-vertex graph shown in Figure 2a. For simplicity, we assume that all adjacent links are equidistantly located and have equal initial key generation rates, namely $R_{ij}≔1$ kbit/s for all $(i,j)\in E$. The target rates are also set to be equal, $T_{ij}≔0.1$ kbit/s, for all possible pairs. The decrease in the cost function $\Delta$ with iteration number r is shown in Figure 2b. The algorithm completes the task after 80, 160 and 800 iterations, respectively. For all considered values of $\delta R$, the matrix of final effective rates $R^{\mathrm{eff}}$ approaches to a form shown in Figure 2c. The corresponding output routing list for remote nodes is obtained in the following:

$$\begin{array}{c}\hfill \mathsf{routing}\text{\_}\mathsf{list}=\left[\right\{(0,1,2),(0,3,2)\}:0.1,\\ \hfill \left\{\right(1,0,3),(1,2,3\left)\right\}:0.1,\\ \hfill \left\{\right(1,2,5),(1,4,5\left)\right\}:0.1,\\ \hfill \left\{\right(2,1,4),(2,5,4\left)\right\}:0.1,\\ \hfill \left\{\right(0,1,4,5),(0,3,2,5\left)\right\}:0.1,\\ \hfill \left\{\right(3,0,1,4),(3,2,5,4\left)\right\}:0.1,\\ \hfill \left\{\right(0,1,4),(0,3,2,5,4\left)\right\}:0.1,\\ \hfill \left\{\right(3,0,1,4,5),(3,2,5\left)\right\}:0.1].\end{array}$$

(10)

It can be seen that the resulting paths follow the graph symmetry and match intuitive expectations. It should be noted that each pair of remote nodes $(i,j)$ has a unique pair of paths through which the key is distributed between them. Considering the key management, the accumulated secret key, e.g., $K_{01}$, is split into multiple subsamples: six keys $\left\{\delta K_{01}^P\right\}$ of equal length $|\delta K_{01}^P|=0.1|K_{01}|$ are used for the key hopping via the paths (0,1,2), (1,0,3), (0,1,4,5), (3,0,1,4), (0,1,4) and (3,0,1,4,5), while the remaining key $K_{01}^{\mathrm{eff}}=K_{01}\backslash \left({\bigcup }_P\delta K_{01}^P\right)$ of length $|K_{01}^{\mathrm{eff}}|=0.4|K_{01}|$ can be entirely used for the direct communication between nodes 0 and 1. A similar key splitting procedure according to the $R^{\mathrm{eff}}$ matrix in Figure 2c is performed for other edges of the graph. Then, the effective secret key to encrypt the communication between a pair of remote nodes, e.g., 1 and 3, is $K_{13}^{\mathrm{eff}}=\delta K_{01}^{(1,0,3)}\oplus \delta K_{12}^{(1,2,3)}$.

The second considered example of a more complex QKD network topology, which is taken from ref. [29], is shown in Figure 3a. In contrast to the previous case, the network has different rates for each link and does not possess a symmetrical structure. The secret key generation rates are simulated for the decoy-state BB84 protocol [43,44,45,46,47] using the link distances from the corresponding graph in ref. [29]. For this example, we set $T_{ij}≔1.0$ kbit/s for all possible pairs of nodes and $M=2$. The behavior of the cost function $\Delta$ with iteration number r for $\delta R\in \{0.1,0.05,0.01\}$ is shown in Figure 3b. The algorithm stops after 78, 158, and 793 iterations, respectively. One can notice that $\Delta$ does not approach to zero like in the first example and stops around 0.75 since the chosen target matrix turns out to be overrated for this scheme. We also note that the choice of $\delta R$ slightly affects the resulting value of the cost function.

The resulting form of the $R^{\mathrm{eff}}$ matrix for $\delta R=0.01$, shown in Figure 3c, demonstrates that the algorithm provides a close-to-uniform distribution of the effective key generation rates among remote nodes. The 11 links, which keep an effective key generation rate noticeably above a “water level” of 0.25, correspond to directly connected nodes. However, note that the key generation in direct links $(2,4)$, $(5,8)$, and $(6,9)$ drops to the “water level”, stopping the algorithm.

For an additional illustration, we present all the path pairs from $\mathsf{routing}$_$\mathsf{list}$ used for the key distribution between the 0th and 9th nodes:

$$\begin{array}{c}\hfill (0,2,4,7,9),(0,3,5,8,9):0.02,\\ \hfill (0,1,5,8,9),(0,2,4,7,9):0.03,\\ \hfill (0,1,5,8,9),(0,3,6,9):0.1,\\ \hfill (0,2,4,7,9),(0,3,6,9):0.1,\\ \hfill (0,2,4,8,9),(0,3,6,9):0.01.\end{array}$$

(11)

Notably, the effective key generation rate of $R_{09}^{\mathrm{eff}}=0.26$ is realized in a quite non-trivial way via five different non-overlapping path pairs.

Then, the final effective secret key between nodes 0 and 9, assembled according to Equation (2), can be written as

$$\begin{array}{cc}\hfill K_{09}^{\mathrm{eff}}=& \left(\delta K_{02}^{(0,2,4,7,9)}\oplus \delta K_{03}^{(0,3,5,8,9)}\right)\hfill \\ \hfill \parallel & \left(\delta K_{01}^{(0,1,5,8,9)}\oplus \delta K_{02}^{(0,2,4,7,9)\prime }\right)\hfill \\ \hfill \parallel & \left(\delta K_{01}^{(0,1,5,8,9)\prime }\oplus \delta K_{03}^{(0,3,6,9)}\right)\hfill \\ \hfill \parallel & \left(\delta K_{02}^{(0,2,4,7,9)″}\oplus \delta K_{03}^{(0,3,6,9)\prime }\right)\hfill \\ \hfill \parallel & \left(\delta K_{02}^{(0,2,4,8,9)}\oplus \delta K_{03}^{(0,3,6,9)″}\right),\hfill \end{array}$$

(12)

where the lengths of the XORed pairs of keys depend on the respective effective rates. A more detailed description of such key management becomes highly non-trivial in this case and is beyond this research.

5. Conclusions and Outlook

In this work, we have addressed the issue of trust reduction in QKD networks by studying the key distribution among remote nodes through multiple non-overlapping paths (M–path scheme). We have proposed a novel iterative greedy algorithm for key routing in QKD networks, aimed at effectively facilitating the key distribution between remote nodes while utilizing the M–path scheme. The efficiency of the proposed algorithm has been shown through case studies involving two QKD networks comprising nodes 6 and 10, respectively. Our results have demonstrated the potential for generating non-trivial key routing paths between remote nodes while achieving a balanced load distribution across directly connected network nodes. This work not only contributes to enhancing the reliability of QKD systems but also opens avenues for further research in optimizing key distribution strategies for QKD networks.

As a potential limitation on the applicability of the developed algorithm, we would like to emphasize its strong dependence on network topology. Specifically, it is assumed that any two remote nodes can be connected by at least M non-overlapping paths. However, in a real QKD network, this assumption may not hold. It is possible to envision a scenario where some pairs of remote nodes are connected by non-overlapping paths, but others are not. This limitation can be addressed by considering a more flexible approach with different requirements for the value of M for each pair, or by considering “partially overlapping path” scenarios. This appears to be a promising avenue for future research.