Stealthy Secret Key Generation

Abstract

In order to make a warden, Willie, unaware of the existence of meaningful communications, there have been different schemes proposed including covert and stealth communications. When legitimate users have no channel advantage over Willie, the legitimate users may need additional secret keys to confuse Willie, if the stealth or covert communication is still possible. However, secret key generation (SKG) may raise Willie’s attention since it has a public discussion, which is observable by Willie. To prevent Willie’s attention, we consider the source model for SKG under a strong secrecy constraint, which has further to fulfill a stealth constraint. Our first contribution is that, if the stochastic dependence between the observations at Alice and Bob fulfills the strict more capable criterion with respect to the stochastic dependence between the observations at Alice and Willie or between Bob and Willie, then a positive stealthy secret key rate is identical to the one without the stealth constraint. Our second contribution is that, if the random variables observed at Alice, Bob, and Willie induced by the common random source form a Markov chain, then the key capacity of the source model SKG with the strong secrecy constraint and the stealth constraint is equal to the key capacity with the strong secrecy constraint, but without the stealth constraint. For the case of fast fading models, a sufficient condition for the existence of an equivalent model, which is degraded, is provided, based on stochastic orders. Furthermore, we present an example to illustrate our results.

1. Introduction

Consider the following motivating example. Two agents, Alice and Bob, want to establish a communication that does not raise the curiosity of a warden Willie, whose duty is to monitor if there is any suspicious activity and also decrypts the data. In order to realize a confidential transmission for such a scenario, we may adopt the following two steps. The first step is to make Willie unaware of the existence of the meaningful communication, which is embedded in the messages intended to be delivered to Bob. In contrast, in a meaningless communication, Bob does not care about the received signal, which is only used to confuse Willie. If Willie can successfully detect the existence of the meaningful transmission, then the second step is to use wiretap coding [1] to provide secrecy (or hidability [2]). There are two main concepts to attain the goal of the first step: (1) communications with a stealth constraint [2,3] and (2) communications with a covert constraint [2,4,5]. Both concepts make Willie unable to differentiate between the existence or nonexistence of the meaningful transmission, solely according to the probability distributions of his observations. More specifically, in the first concept, we transmit meaningful and meaningless signals non-overlapped in time. Note that the meaningful signal is the one Alice wants to communicate with Bob, while the meaningless signal is used to confuse Willie. If well designed, Willie cannot differentiate between those two signals, because the induced output distributions are close (the closeness can be defined in several different ways, e.g., by total variational distance, divergence, etc.) to each other. In the second concept, the meaningful signal can be superimposed on the meaningless one. Under the stealth constraint, we can have a positive capacity, while the covert transmission rate is zero, asymptotically. Even though the transmission rate of the second concept is in general zero, asymptotically, the second order rate is positive following the square root law [5,6].

For the aforementioned two concepts, if the channel between Alice and Bob (denoted by Bob’s channel in the following) is no better than the channel between Alice and Willie (denoted by Willie’s channel in the following), we need additional keys to conceal the meaningful signals, e.g., [4,5]. In particular, these additional keys are used to choose between codebooks to fool Willie. Our motivation is to design an achievable scheme for the source model secret key generation (SKG) for the above scenario, i.e., Bob has no channel advantage over Willie, while fulfilling both the security and stealth constraints, simultaneously. Note that the keys generated from the stealthy SKG can also be used to protect the data on top of concealing the behavior of transmission, e.g., encryption/one-time pad, etc. Note also that our design goal is violated if we directly apply common SKG schemes [7]. This is because common SKG schemes use public communications for several important operations including advantage distillation, information reconciliation, and privacy amplification ([7] Chapter 4.3).Without subtle modifications, these operations will raise Willie’s curiosity. To attain our objective, we focus on stealthy SKG, which is from its counterpart, stealth communications [3]. The main reason not to consider covertness but stealth for the SKG is that, under the assumption of a noiseless public discussion channel, there is no ambient noise to hide the discussion signal. Instead, covert SKG may be feasible if there is a noisy public channel. In addition, in general, the covert SKG suffers a sub-linear rate, e.g., [8], which is inherited from the covert communications. Recall that a channel-model SKG with a rate-unlimited public channel was considered in [8]. The authors applied the scheme from covert communication to the key transmission, while a stealth-like public discussion was used.

The main contributions of this work are summarized in the following:

• We investigate a source-model SKG under strong secrecy with an additional stealth constraint.
• We derive an achievable secret key (SK) rate under the stealth constraint, if $I(X;Y)\ge I(X;Z)$, where X, Y, and Z are the observations of the common randomness source at Alice, Bob, and Willie, respectively. Moreover, if $(X,Y,Z)$ form a Markov chain $X-Y-Z$, then the SK capacity with the additional stealth constraint can be achieved without extra cost, compared to the SKG without the stealth constraint.
• We prove that a sufficient condition to achieve the stealthy SK capacity can be relaxed from the physically degraded channel to a stochastically degraded one.
• A sufficient condition for the existence of an equivalent degraded model is derived by the usual stochastic order [9], which is for the fast fading Gaussian Maurer’s (satellite) model [10].

Notation: Lower case bold letters denote deterministic vectors, and upper case normal/bold letters denote random variables/random vectors (or matrices), which will be defined when they are first mentioned. We denote the probability mass function (pmf) by P. The entropy of X is denoted as $H\left(X\right)$. The mutual information between two random variables X and Y is denoted by $I(X;Y)$. The divergence between distributions $P_X$ and $P_Y$ is denoted by $\mathbb{D}\left(P_X\right|\left|P_Y\right)$. $X\sim F$ denotes that the random variable X follows the distribution F, while $\overline{F}\triangleq 1-F.$ The subscript i in $X_i$ denotes the ith symbol, and $X^i\triangleq [X_1,X_2,\cdots ,X_i]$. $X-Y-Z$ denotes the Markov chain. $\lceil ·\rceil$ denotes the ceiling operator. All logarithms are to base two. ${\left(a\right)}^{+}\triangleq max(a,0)$.

The rest of the paper is organized as follows. In Section 2, we introduce the preliminaries and the considered system model. In Section 3, we derive our main results. Finally, Section 4 concludes this paper.

2. Preliminaries and System Model

2.1. Preliminaries

We first introduce some necessary definitions and results to develop our work.

Definition 1.

The strong secrecy and the stealth constraints are respectively defined as:

$$\begin{array}{cc}\hfill \mathbb{D}\left(P_{M{Z}^n}\right|\left|P_M{P}_{Z^n}\right)& \le ϵ,\hfill \\ \hfill \mathbb{D}\left(P_{Z^n}\right|\left|Q_{Z^n}\right)& \le ϵ,\hfill \end{array}$$

for arbitrarily small $ϵ>0$, where M, $Z^n$, $P_{Z^n}$, and $Q_{Z^n}$ are transmitted messages, the observed signal at Willie, and the output distributions at Willie induced by meaningful and meaningless signals, respectively.

The second constraint in the above definition can be explained by hypothesis testing as discussed in [3]. By this viewpoint, if the second constraint is fulfilled, the adversary’s best strategy is to blindly guess whether the current transmitted signal is meaningful or meaningless.

Definition 2.

Denote a common random source as $(\mathcal{X},\mathcal{Y},\mathcal{Z},P_{XYZ})$, where $\mathcal{X},\mathcal{Y},\mathrm{and}\mathcal{Z}$ are the alphabets of the observations at Alice, Bob, and Willie. The random source is stochastically degraded, if the marginal distributions $P_{Y|X}$ and $P_{Z|X}$ are identical to those of another source of common randomness $(\mathcal{X},\mathcal{Y},\mathcal{Z},P_{X\tilde{Y}\tilde{Z}})$ following the physical degradedness, i.e., $X-\tilde{Y}-\tilde{Z}$.

Corollary 1.

The same marginal property for one transmitter ([11] Theorem 13.9) Consider a discrete memoryless multiuser channel including one transmitter and two non-cooperative receivers with input and output alphabets $\mathcal{X}$ and $\mathcal{Y}\times \mathcal{Z}$, respectively. The capacity region of such a channel depends only on the conditional marginal distributions $P_{Y|X}$ and $P_{Z|X}$ and not on the joint conditional distribution $P_{Y,Z|X}$, where $X\in \mathcal{X}$ and $Y\in \mathcal{Y}$ and $Z\in \mathcal{Z}$ are the transmit signal and the two receive signals, respectively.

Definition 3.

δ-robust typicality ([12] Appendix)

The sequence $x^n\in {\mathcal{X}}^n$ is δ-robust typical for $\delta >0$:

$$\begin{array}{c}\hfill T_{\delta }^{\left(n\right)}\left(P_X\right)=\left\{x^n\in {\mathcal{X}}^n:\left|\frac{N\left(a\right|x^n)}{n}-P_X\left(a\right)\right|\le \delta P_X\left(a\right),\forall a\in \mathcal{X}\right\},\end{array}$$

(1)

where $N\left(a\right|x^n)$ is the number of occurrences of a in $x^n$.

Definition 4. 

([9] (1.A.3) For random variables A and B, $A{\le }_{st}B$ if and only if ${\overline{F}}_A\left(a\right)\le {\overline{F}}_B\left(a\right)$ for all a.

Let $A{=}_{st}{A}^{\prime }$ denote that A and $A^{\prime }$ have the same distribution.

Lemma 1.

Coupling [13]: $A{\le }_{st}B$ if and only if there exists random variables $\widehat{A}{=}_{st}A$ and $\widehat{B}{=}_{st}B$ such that $\widehat{A}\le \widehat{B}$ almost surely.

2.2. System Model

The considered system model is shown in Figure 1. We denote the n-time source observations at Alice, Bob, and Willie by $X^n$, $Y^n$, and $Z^n$, respectively, which follow the independent and identically distributed (i.i.d.) joint distribution $P_{X^n{Y}^n{Z}^n}={\prod }_{i=1}^n{P}_{X_i{Y}_i{Z}_i}={\prod }_{i=1}^n{P}_{XYZ}$ with alphabets $\mathcal{X},\mathcal{Y},\mathcal{Z}$, respectively. The public discussion between Alice and Bob through a noiseless channel is denoted by a random vector $F^n\in {\mathcal{F}}^n$. We consider the case without rate limitation on the public discussion channel. Willie can perfectly observe $F^n$. The joint distributions of the signals that Willie can observe when the SKG is meaningful and meaningless are denoted by $P_{F^n{Z}^n}$ and $Q_{F^n{Z}^n}$, respectively. Alice and Bob aim at sharing keys $K\in \mathcal{K}$ satisfying the constraints as follows:

$$\begin{array}{cc}\hfill {\mathbb{P}}_e\triangleq Pr(K\ne \widehat{K})& \le ϵ,\hfill \end{array}$$

(2)

$$\begin{array}{cc}\hfill log\left|\mathcal{K}\right|-H\left(K\right)& \le ϵ,\hfill \end{array}$$

(3)

$$\begin{array}{cc}\hfill \mathbb{D}\left(P_{K{Z}^n{F}^n}\right|\left|P_K{P}_{Z^n{F}^n}\right)& \le ϵ,\hfill \end{array}$$

(4)

$$\begin{array}{cc}\hfill \mathbb{D}\left(P_{F^n{Z}^n}\right|\left|Q_{F^n{Z}^n}\right)& \le ϵ\hfill \end{array}$$

(5)

for arbitrarily small $ϵ>0$, where (2) is the error probability having different keys at Bob from Alice, (3) is the keys’ uniformity constraint, while $\left|\mathcal{K}\right|$ is the number of keys and (4) is the constraint for the strong secret key, which is an adaptation from the stealth communication in Definition 1. In particular, K is dual to M, and $Z^n{F}^n$ is dual to $Z^n$. The stealth constraint is considered in (5), which is again an adaptation from Definition 1, i.e., here, $F^n{Z}^n$ is what Willie can observe, instead of solely $Z^n$ in stealth communications.

Definition 5.

The rate of the keys generated fulfilling (2)–(5) is called the achievable stealthy strong SK rate.

Definition 6.

The maximum achievable stealthy strong SK rate is called the stealthy strong SK capacity.

3. Main Results

We show two main result in this section: (1) the stealthy strong SK rate and a condition to attain the capacity; (2) a scheme to identify the fast fading Gaussian Maurer’s model as a degraded one, so that the stealth SK capacity can be determined explicitly.

3.1. Stealthy Strong Secret Key Rate and Capacity

Our main result is described by the following theorem followed by discussions.

Theorem 1.

If $(X,Y,Z)$ drawn from the common random source $(\mathcal{X},\mathcal{Y},\mathcal{Z},P_{XYZ})$, then the stealthy strong SK capacity $C_{SK}$ of source model SKG with the stealth constraint can be bounded by:

$$\begin{array}{c}\hfill max\{I(X;Y)-I(X;Z),I(Y;X)-I(Y;Z)\}\le C_{SK}\le min\{I(X;Y|Z),I(X;Y)\}.\end{array}$$

(6)

Furthermore, if $(X,Y,Z)$ forms a Markov chain $X-Y-Z$, the stealthy strong SK capacity is:

$$\begin{array}{c}\hfill C_{SK}=I(X;Y)-I(X;Z).\end{array}$$

(7)

3.2. Sufficient Conditions for a Degraded Common Randomness

In this section, we derive a sufficient condition to obtain $C_{SK}=I(X;Y)-I(X;Z)$. In particular, we show that this sufficient condition, i.e., the common randomness forming a Markov chain $X-Y-Z$, can be relaxed to be stochastically degraded. After that, we show that this relaxed condition can be satisfied under a quite common setting by, e.g., the fast fading Gaussian Maurer’s (satellite) model [10]. In particular, a central random source $S_0$ emits signals passing through fast fading additive white Gaussian noise (AWGN) channels, which are observed as X, Y, and Z at Alice, Bob, and Willie, respectively.

Theorem 2.

If a common random source $(\mathcal{X},\mathcal{Y},\mathcal{Z},P_{X\tilde{Y}\tilde{Z}})$ is stochastically degraded such that $P_{\tilde{Y}|X}=P_{Y|X}$ and $P_{\tilde{Z}|X}=P_{Z|X}$, where $X-Y-Z$, then:

$$\begin{array}{c}\hfill C_{SK}=I(X;Y)-I(X;Z).\end{array}$$

(8)

The proof is delegated to Appendix C.

Example: Consider the fast fading Gaussian Maurer’s (satellite) model [10] as a special case of Theorem 2:

$$\begin{array}{cc}\hfill X& =A_X{S}_0+N_X,\hfill \end{array}$$

(9a)

$$\begin{array}{cc}\hfill Y& =A_Y{S}_0+N_Y,\hfill \end{array}$$

(9b)

$$\begin{array}{cc}\hfill Z& =A_Z{S}_0+N_Z,\hfill \end{array}$$

(9c)

where $N_X$, $N_Y$, and $N_Z$ are independent AWGNs at Bob and Willie, respectively, while both are with zero mean and unit variance; $A_X$, $A_Y$, and $A_Z$ follow CDFs $F_X$, $F_Y$, and $F_Z$, respectively, and are the i.i.d. fast fading channel gains from the source $S_0$ to Alice and Willie, respectively. Note that intuitively, X, Y, and Z have no degradedness relation in general due to the random fading. This is because, by the definition of degradedness, the trichotomy order of all realizations between the two fading channels within a codeword length should be the same. We can invoke the same marginal property [14] to construct an equivalent channel, wherein by imposing the usual stochastic order constraint, we can identify those fading channels that can be re-ordered in the equivalent channel to keep the trichotomy order fixed.

If the random channels $A_X$ and $A_Z$ fulfill ${\overline{F}}_{A_X^2}\left(x\right)\ge {\overline{F}}_{A_Z^2}\left(x\right)$ for all x, where the subscripts denote the absolute square of the channel magnitudes, then from Lemma 1, we have equivalent (in the sense of having the same stealthy SK capacity) observations at Bob and Willie as $\widehat{Y}={\widehat{A}}_X{S}_0+N_Y$ and $\widehat{Z}={\widehat{A}}_Z{S}_0+N_Z$, respectively, where ${\widehat{A}}_X^2\ge {\widehat{A}}_Z^2$ almost surely. Therefore, it is clear that ${\overline{F}}_{A_X^2}\left(x\right)\ge {\overline{F}}_{A_Z^2}\left(x\right)$ is a relaxed sufficient condition to guarantee that Z is an equivalently stochastically degraded version of Y.

Assume that $A_X$ and $A_Z$ in Equations (9a)–(9c) are fast fading magnitudes following the Nakagami-m distribution with shape parameters $m_x$ and $m_z$ and spread parameters $w_x$ and $w_z$ [15], respectively. From Theorem 2, we know that Z is a degraded version of X if:

$$\begin{array}{c}\hfill \gamma \left(m_x,\frac{m_x}{w_x}x\right)\Gamma \left(m_z\right)\ge \gamma \left(m_z,\frac{m_z}{w_z}x\right)\Gamma \left(m_x\right),\forall x,\end{array}$$

where $\gamma (s,x)={\int }_0^x{t}^{s-1}{e}^{-t}dt$ is the incomplete gamma function and $\Gamma \left(s\right)={\int }_0^{\infty }{t}^{s-1}{e}^{-t}dt$ is the ordinary gamma function. An example satisfying the above inequality is $(m_x,w_x)=(1,3)$ and $(m_z,w_z)=(1,2)$.

4. Conclusions

In this work, we analyzed the performance of the secret key generation from a common random source, which satisfied the additional constraint that the generation of keys should not invoke the warden Willie’s attention. Our results showed that compared to the normal SKG, the additional stealth constraint could be fulfilled without extra cost. In particular, the stealthy SK capacity with strong secrecy constraint is $I(X;Y)-I(X;Z)$, if the common random source satisfies $I(X;Y)\ge I(X;Z)$. To emphasize the practical relevance, a sufficient condition was derived to attain the degradedness by the usual stochastic order for the Gaussian Maurer’s (satellite) model for the source of common randomness under fast fading. As a final note, we can also use Slepian–Wolf coding with a proper use of the binning code book to derive the same result.