# Path Hopping: An MTD Strategy for Long-Term Quantum-Safe Communication

Authors: Reihaneh Safavi-Naini; Alireza Poostindouz; Viliam Lisy
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Moving target defense (MTD) strategies have been widely studied for securing computer systems. We consider using MTD strategies to provide long-term cryptographic security for message transmission against an eavesdropping adversary who has access to a quantum computer. In such a setting, today’s widely used cryptographic systems including Diffie-Hellman key agreement protocol and RSA cryptosystem will be insecure and alternative solutions are needed. We will use a physical assumption, existence of multiple communication paths between the sender and the receiver, as the basis of security, and propose a cryptographic system that uses this assumption and an MTD strategy to guarantee efficient long-term information theoretic security even when only a single path is not eavesdropped. Following the approach of Maleki et al., we model the system using a Markov chain, derive its transition probabilities, propose two security measures, and prove results that show how to calculate these measures using transition probabilities. We define two types of attackers that we call risk-taking and risk-averse and compute our proposed measures for the two types of adversaries for a concrete MTD strategy. We will use numerical analysis to study tradeoffs between system parameters, discuss our results, and propose directions for future research.


---

## Body

## 1. Introduction

Cryptographic infrastructure of the Internet allows users from across the world to establish private and authenticated, confidential communication channels, and interact securely. Shor’s discovery of a quantum algorithm that can efficiently solve integer factorization and discrete logarithm problems [1], the two mathematical problems that are the basis of the security of the most prominent public key crypto algorithms such as RSA public key encryption and Diffie-Hellman key agreement, effectively brings down the cryptographic infrastructure of the Internet. The NSA’s recent call for quantum-safe cryptography and the prediction that significant progress in the development of quantum computers could be expected within fifteen years [2, 3] have created a flurry of activities in research community, standardization bodies [4, 5], and major industries [6–8]. The main approaches to quantum-safe cryptography use, (i) quantum cryptographic models and algorithms, (ii) cryptographic algorithms that rely on computational assumptions for which no efficient quantum algorithm is known [9], and (iii) cryptographic systems that do not use any computational assumptions. This last approach results in information theoretically secure systems and is followed in this paper.A prominent and widely researched direction in information theoretically secure communication isphysical layer security systems that base security on assumptions about the physical environment [10]. In these systems the advantage of the sender and the receiver over the adversary is captured through the properties of the physical layer of communication. For example, in Wyner’s model [11] Alice is connected to Bob and Eve through two noisy channels, and the assumption is that Eve’s reception is noisier than Bob’s reception. The extra noise in Eve’s channel is the resource and can be used for securing communication against Eve, without the need for a shared key. A unique property of this approach compared to computationally secure systems is providinglong-term security which refers to the property that Eve’s transcript of communication cannot be used for offline attacks. This is because security is due to the lack of information and not adversary’s limited computation.In this paper we assume there are multiple communicationpaths (N paths) between the sender and the receiver. A path is an abstraction of a channel and can have different realizations in practice. For example, in wireless communication, a path can correspond to a frequency that is used for transmission and reception by the sender and the receiver; and multiple paths are specified by a set of frequencies that will be used by the two. Or in a sensor network, a path consists of a sequence of nodes in the network which are used to send messages from the sender to the receiver. A similar notion of path can be defined for communication over the Internet. If the adversary can eavesdrop all the paths, secure communication without additional assumptions (e.g., quantum mechanical, computational or other physical layer assumptions) is impossible. We assume that although the set of all paths (e.g., possible frequencies) is known to the attacker, they cannot eavesdrop all the paths at the same time.To provide cryptographic security against an attacker whose goal is to learn the sent message, the sender can use an(N,N)-secret sharing (see Section 2) to construct N shares of the message and send each share along a path. This is an inefficient solution with communication rate of 1/N (i.e., for one bit of information, the sender must send N bits). If the number of paths that the adversary can simultaneously eavesdrop is bounded by K′<N, the sender and receiver can select a random set of K paths and use a (K,K)-secret sharing. Note that K is not necessarily equal to K′, but to keep the introductory discussion simple, let K=K′; we will later discuss the relation between K and K′ in Section 3. If the set of K paths is kept fixed, the attacker will discover them over time and will be able to learn the message. We propose “path hopping,” where the sender and the receiver regularly change (“hop”) one or more paths that have been chosen for communication. We also allow the attacker to change their selected paths. We model and analyze dynamic behaviour of the system and show that it results in efficient cryptographic security using an MTD strategy.


### 1.1. Our Work

Alice wants to send a stream of data to Bob. The adversary is computationally unlimited (no computational assumption is made). Alice and Bob are connected by a set ofN communication paths, up to K of which can be eavesdropped by the adversary at the same time. The adversary probes a path to determine if it carries data, and if it does, it captures it (e.g., scanning the port on a server and if open, later break into the path). The adversary ismobile[12] and can move in the network in the sense that, in each time step, it can release a captured path and capture a new one. Hence, it can eavesdrop different sets of paths during different time periods.We assume the attacker can eavesdrop up toKpaths, but only eavesdrops those that carry data, and not the ones that are not in use between Alice and Bob(one can consider a case where the attacker always eavesdrop on K paths. Although the analysis approach will be similar, the actual calculations will be different). Alice uses K (out of N) paths at each time and the attacker needs to know all the K paths (targets) to be able to determine the message.Time is divided into fixed consecutive intervals, each referred to as atime step. In each time step,defender (which includes Alice and Bob),attacker, or none of them takes an action (move). Using the MTD framework of [13], the combination of the attacker’s and the defender’s actions in each time step can be modelled as aMarkov chain. We define Gu,v Markov chain where (exactly) u and v paths are hopped by the defender and the attacker, respectively, and derive transition probabilities of the chain. (One can also consider G≤u,≤v Markov chain where in each time step, the defender randomizesup tou paths and the attacker hops and probesup tov paths. We leave this for future work.) For our concrete analysis we focus on G1,1 where the defender’s and the attacker’s actions involve a single path, only.In each time step, the system can be in one of theK+1states labeled by 0,1,…,K, where state 0 is the starting state of the system, state K is thewinning state for the attacker, and in state i, attacker has captured i paths. We assume the defender leads in each time step andmoves with a fixed probability λ. The attacker also moves in the same interval with a fixed probability μ that is upper bounded by 1-λ (the model assumes that, in each time step, the attacker and the defender do not act simultaneously.) Note that μ can be chosen by the adversary, knowing the upper bound. We define arisk-taking and arisk-averse attacker, depending on their choice of μ. A risk-taking adversary chooses the highest available attack probability, that is, μ=1-λ. Arisk-averse attacker would like to stay undetected and so limits their action rate to a threshold that is determined by the intrusion detection system (IDS) of the defender. Thus, in the case of a risk-averse adversary, in each time step, there is a probability that no one moves.We model the system as a Markov chain, and in Section3, derive the transition probabilities of the Markov chains associated with the risk-taking (case C1) and the risk-averse (case C2) attackers.Security Measures. We use two security measures to evaluate effectiveness of a path hopping strategy: (i) the expected number of times that the attacker reaches the winning state in T time steps, assuming that it is starting from state 0, and (ii) the expected number of time steps to enter the wining state for the first time, assuming that the attacker starts from state 0. The two measures are denoted by LT and Ewin(1), respectively.These security measures capture security requirements of different scenarios.LT is appropriate for data streams for which sporadic access to different parts of the stream may be tolerated. For example, small excerpts of a large file are not expected to leak much information about the file. Theorem 3 shows that LT is upper bounded by the product T·π(K), where π(K) is the Kth component of the stationary probability distribution of the Markov chain. This suggests that π(K)can be used to representLT, with higher values corresponding to less security.E w i n ( 1 ) is appropriate for highly sensitive data streams that must stay strictly inaccessible to the adversary and the sender wants to ensure that the expected number of time steps to the first compromise is sufficiently high (possibly higher than the length of the stream). Theorem 4 shows that Ewin(1) can be calculated by solving a set of linear equations whose coefficients are derived from the transition probabilities of the Markov chain. We use Ewin(1)as a security measure with higher values corresponding to higher security.Numerical Results. Deriving closed form expressions for LT and Ewin(1) is a challenging task. For G1,1, we use numerical calculations to study variations of security measures for different values of system parameters. Our results are given in Section 6. They show the following:(1) For fixedN and K, security increases (i.e., π(K) decrease, and Ewin(1) increases) as λ, the defender’s probability of action, increases (Figures 3 and 4 for C1 and Figures 6 and 7 for C2).(2) For fixedN, security can be maintained by increasing λ, even when K=N-1 (Figure 5) and in all cases communication rate is 1/K.Figure5 also shows that, for given values of N and λ, as K increases, security initially increases, then it reaches a plateau and then starts to decrease. This is because when K is small (relative to N), the target paths are hidden among many available paths and the success chance of correctly guessing a path would be small. However, when K is large (relative to N), the attacker’s probability of correct guessing increases. Interestingly, this point of saturation increase as λ that represents variability of the system increases. This graph can be used to select the optimal value of K to provide maximum security, while achieving the highest communication rate.(3) Using numerical analysis, one can estimate thecost of being risk-averse in terms of decrease in LT or increase in Ewin(1). In Section 7 we show that an adversary who chooses not to use all their attacking power (although they can act with probability 1-λ, they choose μ<1-λ) will effectively reduce the expected number of times that they will occupy the winning state (proportional to π(K)) and will have higher Ewin(1).Attack Costs. Our model focusses on the defender’s ability to provide security by making thephysical environment dynamic and does not consider the associated costs. Attacker and defender’s actions have payoffs. The attacker needs to spend resources to launch attacks and also bear consequences of being detected. The defender must spend resources to implement the randomization strategy. This introduces side effects such as packet loss and communication delays that are a function of the rate of randomization (captured with parameter λ). The attacker’s reward of their action is related to getting closer to the winning state, and the defender’s reward is preventing the attacker reaching the final state. In Section 7 we discuss these payoffs. We also use our numerical calculation results to quantify the cost of being risk-averse.Randomness Requirements of the System. Our proposed system assumes that the sender and the receiver share the set of target paths that is used for communication in each time step.In practice if one can assume that the receiver will receive on all paths all the times, then no shared randomness is required: the sender will hop the paths and the receiver will receive the content on the target paths used in each time step. If receiver has the same restriction as the sender on the number of target paths, that is, the receiver can only receive onK paths (e.g., cost or restriction on the receiving equipment), then the sender and the receiver need shared randomness to simultaneously hop the paths. This can be realized in two ways: (i) using a preshared random string or (ii) employing a secure pseudorandom generator to extend an initial shared random seed.The adversary view of the system in statei, in addition to the eavesdropped shares that are sent over that i target paths, includes the labels of the i target paths. In case (i), the sequence of random numbers associated with the labels of target paths will not reveal any information about future values of the sequence of target paths and so future path labels will remain unpredictable. In the case of (ii) however, each observation (of a target path) will leak information about the seed of the PR generator and one needs to use a PR generator with appropriate security level (e.g., a quantum-safe PR generators using a secure block cipher). Note that the MTD system will retain its security because the recorded transcript of communication although may reveal the seed of the PR generator in an offline attack will not have enough information about communicated message and so the message transmission will have long-term security.


### 1.2. Related Work

Breaking information into shares, to provide confidentiality and reliability, has been used in many cryptographic systems such as secret sharing [14] and information dispersal [15], in information theoretic setting, as well as computational setting [16]. These algorithms have been used in distributed storage systems [17] and are the building blocks of Secure Message Transmission [18] and network coding [19] which use multiple paths between the sender and receiver for providingsecurity and reliability.Uncoordinated Frequency Hopping (UFH) [20] has similarity to our work. In UFH the sender and receiver send and receive on two independently chosen subsets of frequencies, and the eavesdropper uses a third subset of frequency for eavesdropping. Authors show that, assuming public key infrastructure, one can communicate securely and reliably in this setting. The work of [21] uses a similar abstract model to construct information theoretic protocols for secure communication, without requiring public key infrastructure. The communication rate in this latter construction, however, is very low. Our approach iscoordinated path hopping where the sender and receiver share an initial secret key that can be established using the scheme of [21]. We leave the analysis of the secret key requirement of our system and in particular efficient ways of generating new keys at the required hopping rate for future work.Using diversity and introducing dynamic properties has been widely used in security systems. System properties that can be diversified and randomized include program instructions [22, 23], operating system distributions [24], and systems [25]. A comprehensive study of various methods is given in [26]. Using game theory for analyzing attackers’ strategies in dynamic systems has been studied in [27, 28].Organization. Section 2 recalls the MTD Markov chain framework. Section 3 presents our path hopping model. Security analysis and measures for our model are introduced in Section 4. Sections 5 and 6 present our simulation results for the G1,1 game. Sections 7 and 8 cover utility discussions and our concluding remarks.


## 1.1. Our Work

Alice wants to send a stream of data to Bob. The adversary is computationally unlimited (no computational assumption is made). Alice and Bob are connected by a set ofN communication paths, up to K of which can be eavesdropped by the adversary at the same time. The adversary probes a path to determine if it carries data, and if it does, it captures it (e.g., scanning the port on a server and if open, later break into the path). The adversary ismobile[12] and can move in the network in the sense that, in each time step, it can release a captured path and capture a new one. Hence, it can eavesdrop different sets of paths during different time periods.We assume the attacker can eavesdrop up toKpaths, but only eavesdrops those that carry data, and not the ones that are not in use between Alice and Bob(one can consider a case where the attacker always eavesdrop on K paths. Although the analysis approach will be similar, the actual calculations will be different). Alice uses K (out of N) paths at each time and the attacker needs to know all the K paths (targets) to be able to determine the message.Time is divided into fixed consecutive intervals, each referred to as atime step. In each time step,defender (which includes Alice and Bob),attacker, or none of them takes an action (move). Using the MTD framework of [13], the combination of the attacker’s and the defender’s actions in each time step can be modelled as aMarkov chain. We define Gu,v Markov chain where (exactly) u and v paths are hopped by the defender and the attacker, respectively, and derive transition probabilities of the chain. (One can also consider G≤u,≤v Markov chain where in each time step, the defender randomizesup tou paths and the attacker hops and probesup tov paths. We leave this for future work.) For our concrete analysis we focus on G1,1 where the defender’s and the attacker’s actions involve a single path, only.In each time step, the system can be in one of theK+1states labeled by 0,1,…,K, where state 0 is the starting state of the system, state K is thewinning state for the attacker, and in state i, attacker has captured i paths. We assume the defender leads in each time step andmoves with a fixed probability λ. The attacker also moves in the same interval with a fixed probability μ that is upper bounded by 1-λ (the model assumes that, in each time step, the attacker and the defender do not act simultaneously.) Note that μ can be chosen by the adversary, knowing the upper bound. We define arisk-taking and arisk-averse attacker, depending on their choice of μ. A risk-taking adversary chooses the highest available attack probability, that is, μ=1-λ. Arisk-averse attacker would like to stay undetected and so limits their action rate to a threshold that is determined by the intrusion detection system (IDS) of the defender. Thus, in the case of a risk-averse adversary, in each time step, there is a probability that no one moves.We model the system as a Markov chain, and in Section3, derive the transition probabilities of the Markov chains associated with the risk-taking (case C1) and the risk-averse (case C2) attackers.Security Measures. We use two security measures to evaluate effectiveness of a path hopping strategy: (i) the expected number of times that the attacker reaches the winning state in T time steps, assuming that it is starting from state 0, and (ii) the expected number of time steps to enter the wining state for the first time, assuming that the attacker starts from state 0. The two measures are denoted by LT and Ewin(1), respectively.These security measures capture security requirements of different scenarios.LT is appropriate for data streams for which sporadic access to different parts of the stream may be tolerated. For example, small excerpts of a large file are not expected to leak much information about the file. Theorem 3 shows that LT is upper bounded by the product T·π(K), where π(K) is the Kth component of the stationary probability distribution of the Markov chain. This suggests that π(K)can be used to representLT, with higher values corresponding to less security.E w i n ( 1 ) is appropriate for highly sensitive data streams that must stay strictly inaccessible to the adversary and the sender wants to ensure that the expected number of time steps to the first compromise is sufficiently high (possibly higher than the length of the stream). Theorem 4 shows that Ewin(1) can be calculated by solving a set of linear equations whose coefficients are derived from the transition probabilities of the Markov chain. We use Ewin(1)as a security measure with higher values corresponding to higher security.Numerical Results. Deriving closed form expressions for LT and Ewin(1) is a challenging task. For G1,1, we use numerical calculations to study variations of security measures for different values of system parameters. Our results are given in Section 6. They show the following:(1) For fixedN and K, security increases (i.e., π(K) decrease, and Ewin(1) increases) as λ, the defender’s probability of action, increases (Figures 3 and 4 for C1 and Figures 6 and 7 for C2).(2) For fixedN, security can be maintained by increasing λ, even when K=N-1 (Figure 5) and in all cases communication rate is 1/K.Figure5 also shows that, for given values of N and λ, as K increases, security initially increases, then it reaches a plateau and then starts to decrease. This is because when K is small (relative to N), the target paths are hidden among many available paths and the success chance of correctly guessing a path would be small. However, when K is large (relative to N), the attacker’s probability of correct guessing increases. Interestingly, this point of saturation increase as λ that represents variability of the system increases. This graph can be used to select the optimal value of K to provide maximum security, while achieving the highest communication rate.(3) Using numerical analysis, one can estimate thecost of being risk-averse in terms of decrease in LT or increase in Ewin(1). In Section 7 we show that an adversary who chooses not to use all their attacking power (although they can act with probability 1-λ, they choose μ<1-λ) will effectively reduce the expected number of times that they will occupy the winning state (proportional to π(K)) and will have higher Ewin(1).Attack Costs. Our model focusses on the defender’s ability to provide security by making thephysical environment dynamic and does not consider the associated costs. Attacker and defender’s actions have payoffs. The attacker needs to spend resources to launch attacks and also bear consequences of being detected. The defender must spend resources to implement the randomization strategy. This introduces side effects such as packet loss and communication delays that are a function of the rate of randomization (captured with parameter λ). The attacker’s reward of their action is related to getting closer to the winning state, and the defender’s reward is preventing the attacker reaching the final state. In Section 7 we discuss these payoffs. We also use our numerical calculation results to quantify the cost of being risk-averse.Randomness Requirements of the System. Our proposed system assumes that the sender and the receiver share the set of target paths that is used for communication in each time step.In practice if one can assume that the receiver will receive on all paths all the times, then no shared randomness is required: the sender will hop the paths and the receiver will receive the content on the target paths used in each time step. If receiver has the same restriction as the sender on the number of target paths, that is, the receiver can only receive onK paths (e.g., cost or restriction on the receiving equipment), then the sender and the receiver need shared randomness to simultaneously hop the paths. This can be realized in two ways: (i) using a preshared random string or (ii) employing a secure pseudorandom generator to extend an initial shared random seed.The adversary view of the system in statei, in addition to the eavesdropped shares that are sent over that i target paths, includes the labels of the i target paths. In case (i), the sequence of random numbers associated with the labels of target paths will not reveal any information about future values of the sequence of target paths and so future path labels will remain unpredictable. In the case of (ii) however, each observation (of a target path) will leak information about the seed of the PR generator and one needs to use a PR generator with appropriate security level (e.g., a quantum-safe PR generators using a secure block cipher). Note that the MTD system will retain its security because the recorded transcript of communication although may reveal the seed of the PR generator in an offline attack will not have enough information about communicated message and so the message transmission will have long-term security.


## 1.2. Related Work

Breaking information into shares, to provide confidentiality and reliability, has been used in many cryptographic systems such as secret sharing [14] and information dispersal [15], in information theoretic setting, as well as computational setting [16]. These algorithms have been used in distributed storage systems [17] and are the building blocks of Secure Message Transmission [18] and network coding [19] which use multiple paths between the sender and receiver for providingsecurity and reliability.Uncoordinated Frequency Hopping (UFH) [20] has similarity to our work. In UFH the sender and receiver send and receive on two independently chosen subsets of frequencies, and the eavesdropper uses a third subset of frequency for eavesdropping. Authors show that, assuming public key infrastructure, one can communicate securely and reliably in this setting. The work of [21] uses a similar abstract model to construct information theoretic protocols for secure communication, without requiring public key infrastructure. The communication rate in this latter construction, however, is very low. Our approach iscoordinated path hopping where the sender and receiver share an initial secret key that can be established using the scheme of [21]. We leave the analysis of the secret key requirement of our system and in particular efficient ways of generating new keys at the required hopping rate for future work.Using diversity and introducing dynamic properties has been widely used in security systems. System properties that can be diversified and randomized include program instructions [22, 23], operating system distributions [24], and systems [25]. A comprehensive study of various methods is given in [26]. Using game theory for analyzing attackers’ strategies in dynamic systems has been studied in [27, 28].Organization. Section 2 recalls the MTD Markov chain framework. Section 3 presents our path hopping model. Security analysis and measures for our model are introduced in Section 4. Sections 5 and 6 present our simulation results for the G1,1 game. Sections 7 and 8 cover utility discussions and our concluding remarks.


## 2. Preliminaries

We recall the basic MTD Markov chain framework that is used in our work and review construction and properties of(t,t) secret sharing schemes.MTD Markov Framework [13]. The system is a defined by the interaction between adefender and anattacker. The defender and the attacker each have a set of possible actions, denoted by D={ϵ,d1,d2,…} and A={ϵ,a1,a2,…}, respectively; in both ϵ shows no action. Time is divided into time steps. In each time step the system is in one of the N possible states. In each time step, the defender and the attacker get a turn to move and the state change probability is determined by their chosen actions and their results. Astrategy of a player determines all actions taken by the player in all points of the game. UsingMarkov model allows the player’s strategy to only depend on the state that the system is in and independent of the history of how the system has reached a state.Definition 1.
AnM-MTD game is defined by a (K+1)×(K+1) transition matrix M which describes a Markov chain of state transitions that reflects both defender and attacker moves. Initially the game starts in the state 0. At each next time step the game transitions from its current state i to a new state j with probability Mi,j.The stateK is the winning state from the adversary’s view (defender losing the game). Initially the system is in state 0 (from both attacker and defender’s view point). In each time step the defender takes an action according to matrix MD with probability λ, the attacker takes an action according to MA with probability μ, and with probability 1-λ-μ, both remain without any action.Definition 2.
An(MD,λ,MA,μ)-MTD Game is defined by(1)
parametersλ and μ that satisfy 0≤λ+μ<1; the parameters represent the rate of defender’s and the attacker’s play, respectively;(2)
(K+1)×(K+1) transition matrices MD and MA; for i,j∈{0,1,…,K}, Mi,jD (or Mi,jA) represents the probability of transitioning from state i to state j when the defender (or the attacker) plays a move in state i.Thus, in each time step a three-sided coin is tossed, and for each side, the corresponding action is realized, and we have the transition matrix(1)M=λMD+μMA+1-λ-μIK+1,where IK+1 is the (K+1)×(K+1) identity matrix.A Markov chainM isirreducible if each state can be reached from any other state. A Markov chain isaperiodic, if all the states have period 1 where the period of state i is defined as gcd{n>0:Pr(Xn=i∣X0=i)}, where Xn is the random variable describing the state of the game after n steps. The two properties together guarantee the existence of a limitingstationary distributionπ, where π=πM.Secret Sharing. A (t,t)-secret sharing is a cryptographic primitive [14] that divides a secret m into t shares, each given to a party, satisfying two properties: (i)reconstructability which means the share of all parties can perfectly reconstruct the original secret and (ii)perfect secrecy which means that if a single share is missing, the secret remains perfectly uncertain. A secret sharing scheme provides two algorithms forshare generation andsecret reconstruction. Let M=ZL, where ZL is the set of integers modulo L, denote the set of secrets, and assume that all secrets are equally likely (Pr(Z=zi)=1/L). The share generation algorithm takes a message m∈M as input and generates t shares s1,s2,…,st as follows. For si,i=1,…,st-1, randomly chooses an element ri in ZL. Then the shares of the secret m are (r1,r2,…,rt-1,rt=m-∑i=1t-1ri(mod⁡L)). It is easy to see that t shares recover the secret (finding the sum modulo L), and even if t-1 shares are known, the secret remains completely uncertain.


## 3. The MTD Game of Path Hopping

We consider the setting described in Section1.1: there is a message source that generates a stream of data that must be protected against an eavesdropper. There are N communication paths that connect the sender to the receiver. To protect message transmission against an eavesdropper who can simultaneously eavesdrop up to K′ paths (K′<N), the sender does the following: (i) randomly chooses a subset of K<N available paths; (ii) uses a (K,K) secret sharing to construct K shares for the message, and (iii) sends each share on one of the selected path. The chosen paths are also calledtarget paths. The receiver knows the paths that are used by the sender in each time step. If the adversary eavesdrops only a subset of the target paths (and not all target paths), because of the perfect secrecy of the (K,K)-secret sharing scheme, the attacker will stay completely uncertain about the message.We assume that the attacker will not keep a path that is not carrying data. That is, because of the limitation on the number of paths that they can simultaneously eavesdrop, they prefer to release a path that is not used in the current time step and wait for the next time step to try again, noting that, due to their probabilistic strategy, there would be a chance to try the released path in the next time step again. To simplify our analysis, we first consider the case thatK=K′. For the cases that K>K′ or K<K′, similar analysis can be used; we omit details because of space.To protect against this adversary, in each time step, the sender and receiver willhop one or more of the target paths, noting that lacking access to even one of the target paths will leave the adversary completely uncertain. We will use the MTD game framework of Definition 2 and model the problem as a dynamic system (game) influenced by (between) twoplayers, asystem defender (or simply defender) that includes thesender and thereceiver and anattacker. The attacker wins the MTD game (in each time step) if they find the K target paths.


### 3.1.Gu,v Games

In each time step, the defender can randomize a subset ofu target paths. Similarly, the adversary can simultaneously probe v paths.We first describe the Markov chain associated with the game, then derive transition probabilities ofGu,v, and finally present a detailed analysis of G1,1.


### 3.2. Markov Chain

The set of the defender’s and the attacker’s actions isD={ϵ,d1} and A={ϵ,a1}, respectively, where d1 and a1 are defender and attacker actions and ϵ is no action. Let S⊂[N] denote the set of current target paths and SA denote the subset of target paths known to the adversary.Defender’s Move. The defender cannot determine with certainty if a path is being eavesdropped. We thus consider a defender who, in all time steps, plays amemoryless strategy. That is the defender plays (issues the move a1) with probability λ, irrespective of any learnt information about the attacker’s state, or own history of actions. When the defender plays in state i, they will choose a subset SDi of the current target paths S and replace the paths in SDi with a randomly selected subset of (N-K) nontarget paths.The chosen paths inSDi may belong to SAi (attacker’s known path in state i) or be outside it.Attacker’s Move. The attacker is adaptive. In state i, the set SA of target paths that is known to the adversary is of size i. The adversary randomly selects a subset SAi of size v of ([N]∖SAi) possible target paths and keeps the message carrying paths and releases the rest. For the adversary, all paths that are not in their set of i known target paths have the same probability of being a target path.We assume that, in statei, as soon as the defender reallocates a target path that is in SAi, the attacker can detect the change (the path is not one of the K target paths). However this will not affect the adversary’s action at this state simply because they know that those paths are not possible target paths.No Move. Defender and attacker are probabilistic and no moves can be issued by either of them.In a time step, if the attacker does not issue an action, they will bear the risk of potentially losing one of their known target paths during the next time step. This is because the defender will play a memoryless strategy and will move with probabilityλ. This extra risk would translate into a higher probability of not being able to reach the winning position of the game.To reduce the probability of losing a target path while waiting, the attacker should act when possible and use the available1-λ action rate. We refer to this attacker as arisk-taking attacker as they focus on maximizing their winning chance. More frequent attacks however have the risk of triggering alarm in the defender’s intrusion detection system (IDS), tightening security, and reducing access to the system. Let τ be a threshold that is used by the defender’s IDS to raise the threat level of the system. To avoid reduction in accessing the system, the attacker may prefer to keep their attack rate below τ. We refer to this attacker as arisk-averse attacker.The defender plays memoryless with probabilityλ, and so in each time step the attacker moves with probability(2)μ=min⁡τ,1-λ.There will be no move by any of the players in a time step, with probability1-λ-μ. Thus the system transition matrix will be(3)M=λMD+μMA+1-λ-μIk+1.Equation (2) shows that, depending on the value of τ (the attack detection threshold of the defender), we have two cases:C1:τ>1-λ. In this case from (2), we have μ=1-λ and(4)M=λMD+1-λMA.C2:τ<1-λ. In this case from (2), we have μ=τ and(5)M=λMD+τMA+1-λ-τIk+1.We refer to C1 and C2 as risk-taking and risk-averse attacker, respectively.


### 3.3. Transition Probabilities ofGu,v

In statei, the attacker knows i target paths in SA. A state transition that starts from state i is in general because of the combination of the defender’s and the attacker’s actions in the following time step. A defender’s action reallocates target paths and (since the attacker only holds target paths) can result in state i to change to j where j≤i. An attacker’s action, however, could result in more target paths being captured and so change the state to j≥i. The state will not change that is stays at i, because of the defenderor the attacker’s actionor no moves at all. In the following, we obtain transition probabilities (starting from state i) for (i) the defender’s move and (ii) the attacker’s move and combine them to obtain the transition probabilities of the chain. For the case of “no move” (which happens with probability 1-λ-μ) the state of the game will not change.Defender’s Move in State i. Defender chooses a set SDi of u paths from the set S of current paths and replaces them with a set SD′i of u paths chosen from the N-K candidate target paths [N]∖S.LetSD,1i=SDi∩SA be the intersection of SDi and the adversary’s set of captured paths, and let SD,1i=x. We note that 0≤x≤min⁡{i,u}. Thus the state of the game after the defender’s action will be i-x (because x target paths have been removed from SA) and we have(6)pDi-x∣i=ixK-iu-xKu,0≤x≤min⁡i,u.Note that, for x=0, the state of the game will not change.Attacker’s Move in State i. Attacker holds the target paths in SA and knows the state of the game. The attacker will choose a set SAi of v paths from [N]∖SA, the set of N-i available candidate target paths.LetSA,1i=SAi∩(S∖SA) be the intersection of SAi and defender’s set of target paths S that are not captured yet, and let SA,1i=y. We have 0≤y≤min⁡{K-i,v}. With the new y captured target paths, the sate of the game will become i+y and we have(7)pAi+y∣i=K-iyN-Kv-yN-iv,0≤y≤min⁡K-i,v.For y=0, the state of the game will not change.Transition Probability from State i to j. Transition probabilities from state i to j will be calculated using (6) and (7) and max⁡{0,i-u}≤j≤max⁡{i+v,K}. We note that transitions with j<i occur only due to the defender’s move, and transitions with j>i occur due to the attacker’s move. No transition will be due to the defender, the attacker, or no move, with probabilities λ, μ and 1-λ-μ, respectively. Thus we have the following transition probabilities:(8)pj∣i=λpDj∣iifi-min⁡i,u≤j<i;λpDi∣i+μpAi∣i+1-λ-μifj=i;μpAj∣iifi<j≤i+min⁡K-i,v;0otherwise.Here pD(j∣i) and pA(j∣i) are defined in (6) and (7), respectively.The above probabilities show that in each time step a state can be changed to up tou+v other states or stay the same.


### 3.4. System Parameters

The Markov chain that models the system is determined by the parametersN,K,λ, and μ. In the following we will define security measures for the system and prove Theorems that relate these measures to the system parameters.


## 3.1.Gu,v Games

In each time step, the defender can randomize a subset ofu target paths. Similarly, the adversary can simultaneously probe v paths.We first describe the Markov chain associated with the game, then derive transition probabilities ofGu,v, and finally present a detailed analysis of G1,1.


## 3.2. Markov Chain

The set of the defender’s and the attacker’s actions isD={ϵ,d1} and A={ϵ,a1}, respectively, where d1 and a1 are defender and attacker actions and ϵ is no action. Let S⊂[N] denote the set of current target paths and SA denote the subset of target paths known to the adversary.Defender’s Move. The defender cannot determine with certainty if a path is being eavesdropped. We thus consider a defender who, in all time steps, plays amemoryless strategy. That is the defender plays (issues the move a1) with probability λ, irrespective of any learnt information about the attacker’s state, or own history of actions. When the defender plays in state i, they will choose a subset SDi of the current target paths S and replace the paths in SDi with a randomly selected subset of (N-K) nontarget paths.The chosen paths inSDi may belong to SAi (attacker’s known path in state i) or be outside it.Attacker’s Move. The attacker is adaptive. In state i, the set SA of target paths that is known to the adversary is of size i. The adversary randomly selects a subset SAi of size v of ([N]∖SAi) possible target paths and keeps the message carrying paths and releases the rest. For the adversary, all paths that are not in their set of i known target paths have the same probability of being a target path.We assume that, in statei, as soon as the defender reallocates a target path that is in SAi, the attacker can detect the change (the path is not one of the K target paths). However this will not affect the adversary’s action at this state simply because they know that those paths are not possible target paths.No Move. Defender and attacker are probabilistic and no moves can be issued by either of them.In a time step, if the attacker does not issue an action, they will bear the risk of potentially losing one of their known target paths during the next time step. This is because the defender will play a memoryless strategy and will move with probabilityλ. This extra risk would translate into a higher probability of not being able to reach the winning position of the game.To reduce the probability of losing a target path while waiting, the attacker should act when possible and use the available1-λ action rate. We refer to this attacker as arisk-taking attacker as they focus on maximizing their winning chance. More frequent attacks however have the risk of triggering alarm in the defender’s intrusion detection system (IDS), tightening security, and reducing access to the system. Let τ be a threshold that is used by the defender’s IDS to raise the threat level of the system. To avoid reduction in accessing the system, the attacker may prefer to keep their attack rate below τ. We refer to this attacker as arisk-averse attacker.The defender plays memoryless with probabilityλ, and so in each time step the attacker moves with probability(2)μ=min⁡τ,1-λ.There will be no move by any of the players in a time step, with probability1-λ-μ. Thus the system transition matrix will be(3)M=λMD+μMA+1-λ-μIk+1.Equation (2) shows that, depending on the value of τ (the attack detection threshold of the defender), we have two cases:C1:τ>1-λ. In this case from (2), we have μ=1-λ and(4)M=λMD+1-λMA.C2:τ<1-λ. In this case from (2), we have μ=τ and(5)M=λMD+τMA+1-λ-τIk+1.We refer to C1 and C2 as risk-taking and risk-averse attacker, respectively.


## 3.3. Transition Probabilities ofGu,v

In statei, the attacker knows i target paths in SA. A state transition that starts from state i is in general because of the combination of the defender’s and the attacker’s actions in the following time step. A defender’s action reallocates target paths and (since the attacker only holds target paths) can result in state i to change to j where j≤i. An attacker’s action, however, could result in more target paths being captured and so change the state to j≥i. The state will not change that is stays at i, because of the defenderor the attacker’s actionor no moves at all. In the following, we obtain transition probabilities (starting from state i) for (i) the defender’s move and (ii) the attacker’s move and combine them to obtain the transition probabilities of the chain. For the case of “no move” (which happens with probability 1-λ-μ) the state of the game will not change.Defender’s Move in State i. Defender chooses a set SDi of u paths from the set S of current paths and replaces them with a set SD′i of u paths chosen from the N-K candidate target paths [N]∖S.LetSD,1i=SDi∩SA be the intersection of SDi and the adversary’s set of captured paths, and let SD,1i=x. We note that 0≤x≤min⁡{i,u}. Thus the state of the game after the defender’s action will be i-x (because x target paths have been removed from SA) and we have(6)pDi-x∣i=ixK-iu-xKu,0≤x≤min⁡i,u.Note that, for x=0, the state of the game will not change.Attacker’s Move in State i. Attacker holds the target paths in SA and knows the state of the game. The attacker will choose a set SAi of v paths from [N]∖SA, the set of N-i available candidate target paths.LetSA,1i=SAi∩(S∖SA) be the intersection of SAi and defender’s set of target paths S that are not captured yet, and let SA,1i=y. We have 0≤y≤min⁡{K-i,v}. With the new y captured target paths, the sate of the game will become i+y and we have(7)pAi+y∣i=K-iyN-Kv-yN-iv,0≤y≤min⁡K-i,v.For y=0, the state of the game will not change.Transition Probability from State i to j. Transition probabilities from state i to j will be calculated using (6) and (7) and max⁡{0,i-u}≤j≤max⁡{i+v,K}. We note that transitions with j<i occur only due to the defender’s move, and transitions with j>i occur due to the attacker’s move. No transition will be due to the defender, the attacker, or no move, with probabilities λ, μ and 1-λ-μ, respectively. Thus we have the following transition probabilities:(8)pj∣i=λpDj∣iifi-min⁡i,u≤j<i;λpDi∣i+μpAi∣i+1-λ-μifj=i;μpAj∣iifi<j≤i+min⁡K-i,v;0otherwise.Here pD(j∣i) and pA(j∣i) are defined in (6) and (7), respectively.The above probabilities show that in each time step a state can be changed to up tou+v other states or stay the same.


## 3.4. System Parameters

The Markov chain that models the system is determined by the parametersN,K,λ, and μ. In the following we will define security measures for the system and prove Theorems that relate these measures to the system parameters.


## 4. Security Analysis

We use two security measures related to the success criteria of the attack.


### 4.1. Expected Number of Compromises

Consider the system over a period ofT time steps, starting from the state 0. Within these T time steps, the expected number of times that the system will be in the compromised state, that is, the attacker is able to learn the message, is an important security measure. (Note that one can use coding strategies [15] to spread information over longer sequences, and so estimating the expected number of compromises provides the required parameter for encoding.)Theorem 3.
For an MTD game of path hopping with transition matrixM and stationary distribution π=(π(0),π(1),…,π(K)), where K is the winning state, LT, which is the expected number of times the adversary wins in the first T time steps, is less than or equal to T·π(K), assuming that the game starts with the 0=(1,0,…,0) distribution.Proof.
The game starts at0=(1,0,…,0). Let LT denote the expected number of times the attacker wins in the first T time steps.
We first assume the attacker’s starting position is chosen according to the stationary distributionπ=(π(0)⋯π(K)). Our goal is to find the expected number of times the attacker wins in T steps, starting with this distribution.
LetXj,j=1,…,T be an indicator variable that takes the value 1 if the attacker wins in the time step j and zero otherwise. Note that, starting from stationary distribution π, the distribution of next step position of the attacker is πM=π, and so each Xj has identical distribution Pr(Xj=1)=π(K).
The random variableS=∑j=1TXj is the number of times that the attacker wins in T time steps. Noting the linearity of the expectation function E(·), that is, E(X+Y)=E(X)+E(Y), we have (9)ES=T·πK.
The adversary will have zero chance of winning in the firstK/v time steps if they start with the 0 distribution, and so(10)LT≤T·πK.The last step of the argument assumes that, starting from the initial distribution (1,0,…,0), Pr(Xj=1) is monotonically increasing (in fact a weaker assumption would suffice for this last step of the argument, which is Pr(Xj=1)≤π(K) for all j) in each step of the chain until it reaches π(K).In our numerical computation we useπ(K) to represent this security measure.


### 4.2. Expected Number of Steps to the First Time Win

Our second security metric is theexpected number of steps to first time compromise. This is an important measure for defender to estimate unbreakability of the system and for the attacker to estimate the work (in terms of the number of time steps that could be translated into attacker’s cost) needed to break the system. This measure can be calculated by solving a set of linear equations.Theorem 4.
Consider an MTD game with transition matrixM. Let vj denote the expected number of times to reach the state K (the winning state) for the first time, if the game M has started with state j. We have(11)v=r+M~v,where r(j)=1 for all j∈{0,…,K-1} and M~ is the same matrix as M with the last (Kth) row removed.Proof.
We consider an attacker that starts in state 0. LetEwin(1) denote the expected number of time steps to compromise the system. Let vj denote the expected number of time steps to reach state K (the winning state) for the first time, if the game M starts at state j. In both MTD games, starting from state 0, the next state will be state 0 or 1, and so we can write(12)v0=1+M00v0+M01v1. That is, the expected number of times to reach state K from state 0 is one (time step) more than the weighted average of the expected number of times to reach state K from state 0 if the next move was to 0, and the expected number of times to reach state K from state 1, if the next move was to state 1. We can write similar equations for all states except state K, for which vK=0. Let v and r be column vectors such that v(j)=vj and r(j)=1 for all j∈{0,…,K-1}. The set of equations can be written as(13)v=r+M~v, where M~ is M with the Kth row removed. This linear equation can be solved for v for any given M and the first element of v is our desired Ewin(1) security metric. In Section 6 we will present graphs of Ewin(1) for various game settings.


## 4.1. Expected Number of Compromises

Consider the system over a period ofT time steps, starting from the state 0. Within these T time steps, the expected number of times that the system will be in the compromised state, that is, the attacker is able to learn the message, is an important security measure. (Note that one can use coding strategies [15] to spread information over longer sequences, and so estimating the expected number of compromises provides the required parameter for encoding.)Theorem 3.
For an MTD game of path hopping with transition matrixM and stationary distribution π=(π(0),π(1),…,π(K)), where K is the winning state, LT, which is the expected number of times the adversary wins in the first T time steps, is less than or equal to T·π(K), assuming that the game starts with the 0=(1,0,…,0) distribution.Proof.
The game starts at0=(1,0,…,0). Let LT denote the expected number of times the attacker wins in the first T time steps.
We first assume the attacker’s starting position is chosen according to the stationary distributionπ=(π(0)⋯π(K)). Our goal is to find the expected number of times the attacker wins in T steps, starting with this distribution.
LetXj,j=1,…,T be an indicator variable that takes the value 1 if the attacker wins in the time step j and zero otherwise. Note that, starting from stationary distribution π, the distribution of next step position of the attacker is πM=π, and so each Xj has identical distribution Pr(Xj=1)=π(K).
The random variableS=∑j=1TXj is the number of times that the attacker wins in T time steps. Noting the linearity of the expectation function E(·), that is, E(X+Y)=E(X)+E(Y), we have (9)ES=T·πK.
The adversary will have zero chance of winning in the firstK/v time steps if they start with the 0 distribution, and so(10)LT≤T·πK.The last step of the argument assumes that, starting from the initial distribution (1,0,…,0), Pr(Xj=1) is monotonically increasing (in fact a weaker assumption would suffice for this last step of the argument, which is Pr(Xj=1)≤π(K) for all j) in each step of the chain until it reaches π(K).In our numerical computation we useπ(K) to represent this security measure.


## 4.2. Expected Number of Steps to the First Time Win

Our second security metric is theexpected number of steps to first time compromise. This is an important measure for defender to estimate unbreakability of the system and for the attacker to estimate the work (in terms of the number of time steps that could be translated into attacker’s cost) needed to break the system. This measure can be calculated by solving a set of linear equations.Theorem 4.
Consider an MTD game with transition matrixM. Let vj denote the expected number of times to reach the state K (the winning state) for the first time, if the game M has started with state j. We have(11)v=r+M~v,where r(j)=1 for all j∈{0,…,K-1} and M~ is the same matrix as M with the last (Kth) row removed.Proof.
We consider an attacker that starts in state 0. LetEwin(1) denote the expected number of time steps to compromise the system. Let vj denote the expected number of time steps to reach state K (the winning state) for the first time, if the game M starts at state j. In both MTD games, starting from state 0, the next state will be state 0 or 1, and so we can write(12)v0=1+M00v0+M01v1. That is, the expected number of times to reach state K from state 0 is one (time step) more than the weighted average of the expected number of times to reach state K from state 0 if the next move was to 0, and the expected number of times to reach state K from state 1, if the next move was to state 1. We can write similar equations for all states except state K, for which vK=0. Let v and r be column vectors such that v(j)=vj and r(j)=1 for all j∈{0,…,K-1}. The set of equations can be written as(13)v=r+M~v, where M~ is M with the Kth row removed. This linear equation can be solved for v for any given M and the first element of v is our desired Ewin(1) security metric. In Section 6 we will present graphs of Ewin(1) for various game settings.


## 5. TheG1,1 Game

To better understand the relationship between parameter values (N,K,λ,μ), in the following we will focus on G1,1 where SAi=SDi=1.That is, in statei, the defender moves by randomly choosing one of the K paths in S and swapping it with a randomly chosen path from the N-K paths in [N]∖S. If the random choice from S is one of the i paths in SAi that is known to the adversary, the adversary loses one of their i captured paths, and the state will move to state i-1, and this happens with probability i/K. Otherwise, if the defender’s selected path is not in SAi the system stays in the same state i and this has probability 1-i/K.The attacker will randomly choose one of the[N]∖SA possible paths. The new path will be a new target path with probability (K-i)/(N-i) and so the system will move to the state i+1 with this probability. On the other hand with probability 1-(K-i)/(N-i), the selected path will not be a target path and with this probability the system will remain in state i.


### 5.1. Case C1: Risk-Taking Adversary

State transition probabilities are given by (4). Figure 1(a) shows state transition probabilities due to the attacker’s and the defender’s actions. The transition probabilities on the upper part of the figure are due to the attacker’s action. Figure 1(b) shows the combined transition probabilities.Figure 1
State transition probabilities for case C1. (a) shows the defender’s moves,λMD, with arrows bellow and attacker’s moves, (1-λ)MA, with arrows above. (b) shows the combined transition matrix M=λMD+(1-λ)MA.
(a) (b)This is a Markov chain and the state transition matrixM=[Mi,j]=[p(j∣i)] can be obtained from Figure 1(b) as(14)pi-1∣i=λiK,(15)pi∣i=N-KN-i+λK-iN-i-iK,(16)pi+1∣i=1-λK-iN-i.It is easy to see that the Markov chain is irreducible and aperiodic. Using this matrix we can find stationary probability distribution of the system denoted byπ=(π(0)⋯π(K)).


### 5.2. Risk-Averse Adversary: Case C2

The state transition matrix is given by (5). At each time step, (i) defender moves (randomize) with probability λ, (ii) attacker moves with probability τ, and (iii) no move happens with probability 1-λ-τ.The adversary knows the state and moves with probabilityτ. The state transition matrix M can be obtained from Figure 2(b), given by(17)pi-1∣i=λiK,pi∣i=1-λiK-μN-KN-i,pi+1∣i=μK-iN-i,where M=[Mi,j]=[p(j∣i)]. Using this matrix we can find stationary probabilities π=(π(0)⋯π(K)). Again, the Markov process is irreducible and aperiodic and a limiting stationary distribution always exists.Figure 2
State transition probabilities for case C2. (a) shows the defender’s moves,λMD, with arrows bellow and attacker’s moves, μMA, with arrows above and the no move 1-μ-λ. (b) shows the combined transition matrix M=λMD+μMA+(1-λ-μ)I.
(a) (b)Figure 3
Numerical computation results forπ(K), the winning probability in the stationary state as a function of λ for different values of N and K for the case C1. For any fixed N and K, by increasing λ security of the system increases; that is, π(K) decreases.Figure 4
Variation ofEwin(1) as a function of λ for different values of N and K for C1, using analytic calculations. Similar to π(K), for any fixed N and K, increasing λ improves security of the system; that is, Ewin(1) increases.Figure 5
Results for security measuresπ(K) and Ewin(1) as functions of K for N=20 and different values of λ. Note that for large values of λ the system can remain secure even if K=N-1 as Ewin(1) remains very large (a) or π(K) remains very close to zero (b).
(a) (b)Figure 6
Numerical computation results forπ(K), the winning probability in the stationary state as a function of λ for different values of N and K for the case C2. For any fixed N, K, and μ, by increasing λ security of the system increases; that is, π(K) decreases.Figure 7
Variation ofEwin(1) as a function of λ for different values of N and K for C2, using analytic calculations. Similar to π(K), for any fixed N, K, and μ, increasing λ improves security of the system; that is, Ewin(1) increases.


### 5.3. Bounds onπ(K)

We prove an upper bound onπ(K) using the following lemma.Lemma 5.
LetM=[Mi,j]=[p(j∣i)] be the transition matrix of a Markov chain such that, for any row i, all components except Mi,i-1,Mi,i,Mi,i+1 are zero.
Then for anyi one has(18)πiMi,i+1=πi+1Mi+1,i.Proof.
We prove this by induction. For the base casei=0, we know that (19)π0=π0M0,0+π1M1,0. Also we know that elements of a row in M sum to 1, that is, ∑jMi,j=1. Thus, π(0)=π(0)M0,0+π(0)M0,1. Therefore, (20)π0M0,1=π1M1,0.
Now we assume that the equality holds for the casei=k; that is, (21)πkMk,k+1=πk+1Mk+1,k. As π=πM, for the case of i=k+1 we have (22)πk+1=πkMk,k+1+πk+1Mk+1,k+1+πk+2Mk+2,k+1. Assuming the case i=k holds we have(23)πk+1=πk+1Mk+1,k+πk+1Mk+1,k+1+πk+2Mk+2,k+1. Recall that ∑jMi,j=1; thus (24)Mk+1,k+Mk+1,k+1+Mk+1,k+2=1. Combining the last two equalities will yield (25)πk+1=πk+11-Mk+1,k+2+πk+2Mk+2,k+1, or equivalently (26)πk+1Mk+1,k+2=πk+2Mk+2,k+1.Theorem 6.
LetM be the (K+1)×(K+1) transition matrix of the Markov chain of the G1,1 game defined in (17). Also let π=(π(0)⋯π(K)) be the stationary probability distribution of M. Then the following inequality holds:(27)πK≤μKλN-K+1K.Proof.
The Markov chains ofG1,1 games satisfy Lemma 5. Therefore, using (17) we have(28)πK=π0∏i=0K-1πi+1πi=π0∏i=0K-1Mi,i+1Mi+1,i=π0∏i=0K-1μK-i/N-iλi+1/K=π0×μKλK×∏i=0K-1K-iN-ii+1≤μKλN-K+1K. The second equality is due to Lemma 5, and the third equality is due to the transition probabilities of G1,1. Note that for the case of risk-taking adversary μ=1-λ.


## 5.1. Case C1: Risk-Taking Adversary

State transition probabilities are given by (4). Figure 1(a) shows state transition probabilities due to the attacker’s and the defender’s actions. The transition probabilities on the upper part of the figure are due to the attacker’s action. Figure 1(b) shows the combined transition probabilities.Figure 1
State transition probabilities for case C1. (a) shows the defender’s moves,λMD, with arrows bellow and attacker’s moves, (1-λ)MA, with arrows above. (b) shows the combined transition matrix M=λMD+(1-λ)MA.
(a) (b)This is a Markov chain and the state transition matrixM=[Mi,j]=[p(j∣i)] can be obtained from Figure 1(b) as(14)pi-1∣i=λiK,(15)pi∣i=N-KN-i+λK-iN-i-iK,(16)pi+1∣i=1-λK-iN-i.It is easy to see that the Markov chain is irreducible and aperiodic. Using this matrix we can find stationary probability distribution of the system denoted byπ=(π(0)⋯π(K)).


## 5.2. Risk-Averse Adversary: Case C2

The state transition matrix is given by (5). At each time step, (i) defender moves (randomize) with probability λ, (ii) attacker moves with probability τ, and (iii) no move happens with probability 1-λ-τ.The adversary knows the state and moves with probabilityτ. The state transition matrix M can be obtained from Figure 2(b), given by(17)pi-1∣i=λiK,pi∣i=1-λiK-μN-KN-i,pi+1∣i=μK-iN-i,where M=[Mi,j]=[p(j∣i)]. Using this matrix we can find stationary probabilities π=(π(0)⋯π(K)). Again, the Markov process is irreducible and aperiodic and a limiting stationary distribution always exists.Figure 2
State transition probabilities for case C2. (a) shows the defender’s moves,λMD, with arrows bellow and attacker’s moves, μMA, with arrows above and the no move 1-μ-λ. (b) shows the combined transition matrix M=λMD+μMA+(1-λ-μ)I.
(a) (b)Figure 3
Numerical computation results forπ(K), the winning probability in the stationary state as a function of λ for different values of N and K for the case C1. For any fixed N and K, by increasing λ security of the system increases; that is, π(K) decreases.Figure 4
Variation ofEwin(1) as a function of λ for different values of N and K for C1, using analytic calculations. Similar to π(K), for any fixed N and K, increasing λ improves security of the system; that is, Ewin(1) increases.Figure 5
Results for security measuresπ(K) and Ewin(1) as functions of K for N=20 and different values of λ. Note that for large values of λ the system can remain secure even if K=N-1 as Ewin(1) remains very large (a) or π(K) remains very close to zero (b).
(a) (b)Figure 6
Numerical computation results forπ(K), the winning probability in the stationary state as a function of λ for different values of N and K for the case C2. For any fixed N, K, and μ, by increasing λ security of the system increases; that is, π(K) decreases.Figure 7
Variation ofEwin(1) as a function of λ for different values of N and K for C2, using analytic calculations. Similar to π(K), for any fixed N, K, and μ, increasing λ improves security of the system; that is, Ewin(1) increases.


## 5.3. Bounds onπ(K)

We prove an upper bound onπ(K) using the following lemma.Lemma 5.
LetM=[Mi,j]=[p(j∣i)] be the transition matrix of a Markov chain such that, for any row i, all components except Mi,i-1,Mi,i,Mi,i+1 are zero.
Then for anyi one has(18)πiMi,i+1=πi+1Mi+1,i.Proof.
We prove this by induction. For the base casei=0, we know that (19)π0=π0M0,0+π1M1,0. Also we know that elements of a row in M sum to 1, that is, ∑jMi,j=1. Thus, π(0)=π(0)M0,0+π(0)M0,1. Therefore, (20)π0M0,1=π1M1,0.
Now we assume that the equality holds for the casei=k; that is, (21)πkMk,k+1=πk+1Mk+1,k. As π=πM, for the case of i=k+1 we have (22)πk+1=πkMk,k+1+πk+1Mk+1,k+1+πk+2Mk+2,k+1. Assuming the case i=k holds we have(23)πk+1=πk+1Mk+1,k+πk+1Mk+1,k+1+πk+2Mk+2,k+1. Recall that ∑jMi,j=1; thus (24)Mk+1,k+Mk+1,k+1+Mk+1,k+2=1. Combining the last two equalities will yield (25)πk+1=πk+11-Mk+1,k+2+πk+2Mk+2,k+1, or equivalently (26)πk+1Mk+1,k+2=πk+2Mk+2,k+1.Theorem 6.
LetM be the (K+1)×(K+1) transition matrix of the Markov chain of the G1,1 game defined in (17). Also let π=(π(0)⋯π(K)) be the stationary probability distribution of M. Then the following inequality holds:(27)πK≤μKλN-K+1K.Proof.
The Markov chains ofG1,1 games satisfy Lemma 5. Therefore, using (17) we have(28)πK=π0∏i=0K-1πi+1πi=π0∏i=0K-1Mi,i+1Mi+1,i=π0∏i=0K-1μK-i/N-iλi+1/K=π0×μKλK×∏i=0K-1K-iN-ii+1≤μKλN-K+1K. The second equality is due to Lemma 5, and the third equality is due to the transition probabilities of G1,1. Note that for the case of risk-taking adversary μ=1-λ.


## 6. Numerical Results forG1,1

To study the effect of different system parameters on the system security, we calculated security measures of the two MTD games for different values of system parameters and graphed the results. We used the results of Section4 to calculate π(K) and Ewin(1) for different choices of N,K, λ, and μ. We used MATLAB for our calculations. For each set of system parameters N,K,λ, or μ, using (6)–(14), we first obtained the transition matrix M. For C1 λ is varied from 1% to 99% in steps of 1%. For C2 λ is varied from 1% to 1-μ in steps of 1%.To calculateEwin(1), we used the results of Theorem 4 and employed the linear equation solver (linsolve) of MATLAB to solve the set of equations v=r+M~v for each parameter set. For large values of K, M becomes near-singular and an exact solution cannot be found (in fact, for large values of K and large values of λ a MATLAB warning occurred due to the equation being near-singular and thus only an approximation of the answer was calculated. We have excluded those cases from our analysis and the graphs are only included with exact results here). This explains the choice of K<10 in our graphs. The choice of N determines the computation time but otherwise is not restricted. We chose values of N and K such that the cases of K<N/2 and K>N/2 both are shown in the graphs.To calculateπ(K) we used MATLAB eigenvector analysis function ([V,D]=eig(M′)) to find for the stationary distribution π where πM=π. The stationary distribution is obtained by normalizing the eigenvector that corresponds to the eigenvalue + 1. We could use N up to 1000 and K up to 200 in this analysis. For the choice μ we ensured that μ<0.5, μ=0.5, and μ>0.5 are represented. The results of the above calculations are graphed.


### 6.1. Case C1

The results of numerical computations for different settings are depicted in Figures3, 4, and 5.Stationary Probability. For fixed N and K, as λ increases π(K) decreases. For fixed N and λ, when K increases, π(K) decreases. Both imply better security as expected from more dynamic systems (Figure 3).Figure5(b) shows that, for fixed N and λ, increase in K results in the reduction of π(K) and increase in Ewin(1) and so better security. However, this gain in security diminishes after K reaches a threshold. In this last case almost all paths are target paths and so attacker’s chance of correctly guessing is high. The thresholding behaviour suggests using higher K (and so higher system cost) will not have a substantial effect on security.The figures also show that, for fixedK as λ increases, π(K) decreases. For example, for N=30, K=3,5, and 7, for all λ≥0.5, we have π(K)≤10-3 (see Figure 3).Expected Number of Steps to the First Win E w i n ( 1 ). Figure 4 shows that, for given parameters N and K, increasing λ increases the security of the game. Moreover, we observe that Ewin(1) behaves linearly in the log graphs of Figure 4 as λ increases, and it increases faster for higher λ’s. Therefore, with increasing λ, the risk-taking attacker needs much longer time to compromise the system.We also observe that, for givenN and λ, as K increases, after a certain threshold value, π(K) increases. For example for N=20, K=N-1=19, and λ=0.2, this threshold is π(K)=0.57 (see Figure 5(b)). For λ>0.5 however, even for K=N-1, π(K) remains small (very close to zero). The same behaviour exists for Ewin(1): for given N and λ, the expected number of steps to the first win of the adversary decreases as K increases. However, decrease in security is negligible if λ is sufficiently large (see Figure 5(a)).


### 6.2. Case C2

The stationary distribution for givenN,K,λ, and μ is given in Figure 6. We consider three different values of μ=0.3,0.5, an 0.7.We also show our results forEwin(1) in Figure 7. The figures demonstrate that the defender achieves better security by choosing higher λ’s.Figure6 shows that, for fixed values of N,K, and μ, the security of the system increases with the increase in λ, represented by the reduction in π(K). We also observe that, similar to the case C1, for fixed K, λ, and μ, we gain more security with increasing N. Moreover, as can be expected, smaller values of μ will let defender to reach higher security by increasing λ.Figure7 shows our analytical calculation results of Ewin(1). Again for fixed values of N,K, and μ, the security of the system increases with the increase in λ, and this is shown by the increase in Ewin(1). It can also be seen that for fixed values of K, λ, and μ, more security can be gained with the increase in N. The figures also indicate that smaller values of μ allows the defender to increase security of the system by increasing λ.As it was discussed in Section7, we can calculate the cost of being a risk-averse adversary in terms of Ewin(1). Figure 8 shows the behaviour of this cost (penalty) as a function of λ<1-μ.Figure 8
The cost of being risk-averse in terms ofEwin(1) as a function of λ for different values of N,K and μ.


## 6.1. Case C1

The results of numerical computations for different settings are depicted in Figures3, 4, and 5.Stationary Probability. For fixed N and K, as λ increases π(K) decreases. For fixed N and λ, when K increases, π(K) decreases. Both imply better security as expected from more dynamic systems (Figure 3).Figure5(b) shows that, for fixed N and λ, increase in K results in the reduction of π(K) and increase in Ewin(1) and so better security. However, this gain in security diminishes after K reaches a threshold. In this last case almost all paths are target paths and so attacker’s chance of correctly guessing is high. The thresholding behaviour suggests using higher K (and so higher system cost) will not have a substantial effect on security.The figures also show that, for fixedK as λ increases, π(K) decreases. For example, for N=30, K=3,5, and 7, for all λ≥0.5, we have π(K)≤10-3 (see Figure 3).Expected Number of Steps to the First Win E w i n ( 1 ). Figure 4 shows that, for given parameters N and K, increasing λ increases the security of the game. Moreover, we observe that Ewin(1) behaves linearly in the log graphs of Figure 4 as λ increases, and it increases faster for higher λ’s. Therefore, with increasing λ, the risk-taking attacker needs much longer time to compromise the system.We also observe that, for givenN and λ, as K increases, after a certain threshold value, π(K) increases. For example for N=20, K=N-1=19, and λ=0.2, this threshold is π(K)=0.57 (see Figure 5(b)). For λ>0.5 however, even for K=N-1, π(K) remains small (very close to zero). The same behaviour exists for Ewin(1): for given N and λ, the expected number of steps to the first win of the adversary decreases as K increases. However, decrease in security is negligible if λ is sufficiently large (see Figure 5(a)).


## 6.2. Case C2

The stationary distribution for givenN,K,λ, and μ is given in Figure 6. We consider three different values of μ=0.3,0.5, an 0.7.We also show our results forEwin(1) in Figure 7. The figures demonstrate that the defender achieves better security by choosing higher λ’s.Figure6 shows that, for fixed values of N,K, and μ, the security of the system increases with the increase in λ, represented by the reduction in π(K). We also observe that, similar to the case C1, for fixed K, λ, and μ, we gain more security with increasing N. Moreover, as can be expected, smaller values of μ will let defender to reach higher security by increasing λ.Figure7 shows our analytical calculation results of Ewin(1). Again for fixed values of N,K, and μ, the security of the system increases with the increase in λ, and this is shown by the increase in Ewin(1). It can also be seen that for fixed values of K, λ, and μ, more security can be gained with the increase in N. The figures also indicate that smaller values of μ allows the defender to increase security of the system by increasing λ.As it was discussed in Section7, we can calculate the cost of being a risk-averse adversary in terms of Ewin(1). Figure 8 shows the behaviour of this cost (penalty) as a function of λ<1-μ.Figure 8
The cost of being risk-averse in terms ofEwin(1) as a function of λ for different values of N,K and μ.


## 7. Utilities

There are costs and gains associated with the defender’s and the attacker’s actions. Below we outline important aspects of utilities of the two players and note that our basic modelling and numerical analysis could provide insight into better quantifying these utilities. More concrete analysis and estimation of utilities require considering specific realization of path hoping systems and more detailed modelling and numerical computations.Defender’s cost in state i is denoted by ciD,ϵ and ciD,d1 for no action and action d1, respectively.(i)ciD,ϵ is the cost of the defender if they do not move. In this case, the defender does not need to bear any resource cost; however, the chance of the attacker winning in the next time step would increase because the attacker may capture additional target paths in the next time step and the state will change to j>i. The defender, however, does not know the exact state of the system, i, and so their cost would be an expected value, where expectation will be taken over the stationary probabilities of the system.(ii)ciD,d1 is the cost of randomization. This will be a fixed cost (that could depend on the number of of paths that will be randomized in one time slot) associated with redirecting traffic, possibly packet losses, and delays to reestablish the paths.Attacker’s costs in state i is denoted by ciA,ϵ and ciA,a1 for no action and action a1.(iii)ciA,ϵ is the cost of the attacker not taking action. They do not need to spend resources, but their success chance would reduce because the defender’s action in the next time step may result in one of the target paths in SAi to be removed from the target path set. As discussed below, this cost can be estimated in terms of increase in Ewin(1).(iv)ciA,a1 is the cost of launching the attack in state i and indicates the resources that the attacker must spend to realize the attack. This cost would be fixed as long as the attack rate is below τ and will increase if the attack rate μ is above τ.One can also consider gains associated with actions of the attacker and the defender. Utilities of the players will be a function of the costs and the gains.Estimating c i A , ϵ. A risk-averse adversary will use an attack rate below 1-λ and so, with probability 1-λ-μ, there is no action from the attacker. Intuitively, no action means that the attacker will have a reduced success chance in breaking security. This can be quantified by the larger expected number of time steps to win for the first time. For example, consider N=30, K=7, and λ=0.6. A risk-averse adversary who moves with probability μ=0.3<1-0.6=0.4 will have Ewin(1)(μ=0.3,λ=0.6)=6×106; however, for the same values of N and K, a risk-taking attacker with μ=1-λ=0.4 will have Ewin(1)(1-λ,λ=0.6)≈1.0×106. This shows that a risk-averse adversary is paying the penalty of being risk-averse and (most likely) must wait for its first win much longer than a risk-taking adversary. By defining the cost of being risk-averse as RiskAverseCost=Ewin(1)(μ,λ)-Ewin(1)(1-λ,λ) for a risk-averse adversary with probability of moving μ, we can graph the behaviour of this cost (penalty) as a function of λ<1-μ.Figure8 shows that smaller μ (being more risk-averse) will have higher costs, and as μ increases, the cost decreases. However, as defender increases λ, the available attack rate of the attacker (1-λ) decreases and after a certain threshold value of λ, the cost of being risk-averse decreases and becomes 0 when λ=1-μ.


## 8. Concluding Remarks

We introduced path hopping as an approach to providing efficient long-term cryptographic security for communication against an adversary with access to a quantum computer. We considered a general class of dynamic strategies that can be modelled as a Markov chain that models the attacker’s and the defender’s interaction and gave detailed analysis ofG1,1. Our work opens new directions for future work including considering more complex set of actions for the players. For example, allow defender and attacker to choose λ and μ in each state, and/or use different values of u and v at different state. Including the actual costs of the defender and the attacker in the modelling and analysis will unravel the limits of randomization strategies in practice. Also, an important question is to efficiently provide sufficient shared randomness for the sender and the receiver, to be used in the path hopping algorithm. For our analysis, we assumed that sufficient number of random bits has been shared by the sender and receiver through another protocol, before transmission starts. Sharing true random bits without computational assumptions in practice requires sharing a random pad which would restrict application of the system in practice. Efficient sharing of randomness can be achieved by using a pseudorandom number generator and only sharing an initial random seed. Security of the resulting system, however, needs to be analyzed to ensure that this will not affect postquantum security of the system. This will be an interesting problem for future research. There are also similar games that can be modelled using this approach. For example, one can consider the path hopping game associated with the model in [21].



---

*Source: 8475818-2018-05-07.xml*