{'fraction_non_alphanumeric': 0.034911444141689375, 'fraction_numerical': 0.0062329700272479565, 'mean_word_length': 4.368623148656061, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum Steganography over Noisy Channels: Achievability and Bounds

Quantum steganography is the study of hiding secret quantum information by encoding it into what an eavesdropper would perceive as an innocent-looking message. Here we study an explicit steganographic encoding for a sender, Alice, to hide a secret message in the syndromes of an error-correcting code, so that the encoding simulates a given noisy quantum channel that Eve believes to connect Alice and Bob. The actual physical channel connecting Alice and Bob is noisy, but less noisy than Eve believes. We show that for the bit-flip and depolarizing channels Alice can use Eve's lack of knowledge of the channel parameter to encode quantum information steganographically. We give an explicit encoding procedure and calculate the rate at which Alice and Bob can communicate secretly. We also show that our encoding is optimal for nondegenerate quantum codes. We calculate the rate at which secret key must be consumed. Finally, we discuss the possibility of steganographic communication over more general quantum channels, and conjecture a general formula for the steganographic rate.


I. INTRODUCTION
Suppose Alice and Bob are the respective leaders of two countries and they wish to communicate highly classified information with each other over a public channel. They do not want other countries to know they are communcating secret information, perhaps because they have a history of shady international political relations. Simple cryptography would not be good enough here beacause it would alert a potential eavesdropper (Eve) that secret communication is taking place, even if she cannot read it. Therefore, if Alice and Bob wish to keep their conversations secret, they must employ a steganographic protocol.
Both cryptography and steganography are interesting and well-developed subjects, the studies of which date back millenia [1,2]. In cryptography, a secret message is encrypted using a shared secret key between Alice and Bob, and Alice sends the resulting ciphertext across a channel to be decoded. Should Eve observe this ciphertext, she would not be able to decode it without the secret key. However, she would undoubtedly become suspicious if she weren't already, due to Alice sending encrypted messages to Bob.
Steganography solves this problem of secrecy. Although cryptography allows for secure communication, in this paper we are interested in secret communication. In steganography, a secret message is hidden into a larger covertext, which appears to Eve as an innocuous message. This seeming innocuousness of the message is what makes the protocol secret. The hidden message may also be encrypted itself to make the protocol not only secret but secure, so that even if Eve were tipped off to there being secret communication between Alice and Bob, she would not be able to decode the hidden message. For example, digital audio, video, and pictures are increasingly furnished with distinguishing but imperceptible marks, which may contain a hidden copyright notice or encrypted serial number [3].
Ever since Shor's remarkable discovery that a quantum computer could solve the prime factorization problem efficiently, hence cracking one of the internet's most common encryption schemes [4], interest in quantum cryptography has been intense. Quantum steganography is of more recent development [5][6][7]. The protocol we will be considering is to encode quantum information steganographically as error syndromes of a quantum error-correcting code. This was detailed extensively by Shaw and Brun [8,9], where it was shown that such schemes can hide both quantum and classical information, with a quantitative measure of secrecy, even in the presence of a noisy physical channel.
A more precise analysis of this quantum steganographic protocol over noiseless channels was done by the present authors in terms of achievability and converse proofs [10]. In this work, we treated the case where Eve believes the channel connecting Alice and Bob to be some noisy quantum channel, but the actual physical channel is noiseless, and we gave optimal rates of steganographic communication.
A related field is known as covert quantum communication [11][12][13][14][15]. In covert communications, it is often assumed that the channel between Alice and Bob is a noisy optical channel, which is modelled by a beamsplitter with some transmissivity parameter that characterizes how many photons are lost to Eve. Covert quantum communication can be seen as a special case of quantum steganography over noisy quantum channels in the case where the eavesdropper has exact knowledge of the channel, and where Eve assumes the channel is idle (so only noise is being transmitted). Similarily, quantum steganography is a type of covert quantum communication where Eve knows about the covertext communication but not the hidden stegotext, and where Eve may not have perfect knowledge of the channel. In covert quantum communication, it has been shown that in general one can secretly communicate an amount of classical information which scales like the square root of the number arXiv:1808.03183v2 [quant-ph] 29 Jul 2019 of channel uses.
The goal of this paper is to extend the previous work on quantum steganography over noiseless channels in [10] to the scenario where the channel Alice and Bob share is noisy. We assume that Eve believes the channel to be noisier than it is, which allows Alice and Bob to communicate at a linear rate in the number of channel uses. This assumption is not unreasonable, especially when Alice and Bob have been systemetically deceiving Eve by adding extra noise. We also assume that Alice and Bob are using an error-correcting code powerful enough to correct errors induced by the channel Eve believes to be connecting them, or else she would become suspicious. Eve would also become suspicious if the pattern of errors Alice uses to encode her secret information does not match the typical errors induced by the channel that Eve expects.
In Section II we formalize our notion of quantum steganography where secret messages are hidden in the syndromes of an error-correcting code. We outline a specific steganographic encoding where Alice is able to emulate a bit flip or depolarizing channel N p+δp (the channel Eve believes to be connecting them) on her encoded secret message and covertext, where the actual physical channel is N p . We also calculate the amount of key consumed in our protocol. In Section III we prove upper bounds on the amount of steganographic communication possible over these channels, and show that these bounds are asymptotically equal to the rates achieved in the previous section. Finally, in Section IV we summarize our results, and discuss quantum steganography for general quantum channels, conjecturing a capacity formula for general quantum steganographic communication.

A. Bit Flip Channel
Suppose that Alice wishes to communicate steganographically to Bob by secretly sending him a message m drawn from a set of possible messages M, assumed to all be equally likely. Alice and Bob can communicate via a quantum channel, but the eavesdropper Eve can monitor their communications over this channel if she chooses. They cannot communicate clasically without Eve intercepting their communications, but before the protocol began they exchanged a secret key, in the form of an arbitrarily long string of random bits, unknown to Eve. We assume that Eve believes the quantum channel shared between Alice and Bob to be a bit flip channel with error rate p + δp, i.e., N BF p+δp (ρ) = (1 − (p + δp))ρ + (p + δp)XρX. (1) However, the actual physical channel between Alice and Bob is N BF p . First, Alice encodes an innocent state, i.e. the covertext ρ c , into a nondegenerate quantum errorcorrecting code (QECC) on N qubits. This code should be able to correct typical errors induced by the channel (N BF p+δp ) ⊗N . Next, depending on the secret key k ∈ K and the message m ∈ M that she would like to send, she applies the error to her state. This produces the codeword corresponding to the message m. If her message to Bob is a quantum state, she can prepare the system in a superposition of these codewords. These codewords are generated by applying errors drawn randomly from the channel (N BF q ) ⊗N , using the shared secret key k as the source of randomness. That is, the errors X or I on each qubit are drawn from the product distribution p E N (e N ), where p E (e) is given by where q = δp/(1 − 2p). Since the set of errors is selected using the shared secret key k, Bob knows which codeword corresponds to each message m. The errors given by Eq.
(2) are typical errors associated with the channel (N BF q ) ⊗N [16,17]. By the asymptotic equipartition theorem [18], for large enough N , it is highly likely that each of these codewords that Alice generates is a typical sequence with a sample entropy close to . This will become important later when we discuss the secrecy of this protocol.
Alice then sends her state through the channel (N BF p ) ⊗N . We are now essentially in the scenario of classical random coding over a classical bit-flip channel with parameter p. By the asymptotic equipartition theorem for conditionally typical sequences [18], for each input sequence (i.e., error E N (k, m) applied to the encoded covertext) there is a corresponding conditionally typical set of errors {F N (k, m)} which has the following properties: its total probability is close to 1, its size is ≈ 2 nH(F |E) , and the probability of each conditionally typical error given knowledge of the input error With high probability, the error F N Bob observes will be a typical error of the channel (N BF p+δp ) ⊗N . We know from Shannon's noisy channel coding theorem that if Alice and Bob set the number of messages |M| = 2 N R such that then Bob is able to decode correctly with high probability [18][19][20] which error E N (k, m) was applied by Alice, as long as the code is nondegenerate. For our protocol, it is straightforward to calculate that H(F ) = h(p+q−2pq) = h(p+δp) for q = δp/(1−2p), and H(F |E) = h(p). Hence Alice can communicate bits of information to Bob steganographically. Moreover, this protocol does not arouse suspicion from Eve. We say that this protocol is secret, because the state passing through the channel is to good approximation the state Eve would expect to see. To see this, note that k∈K m∈M where V is the isometry corresponding to the QECC Alice and Bob are using. The first equality follows from linearity of quantum operations. The approximate equality follows from the fact that when we average the transmitted codeword over the key and all possible messages, we are applying all the typical errors of the channel (N BF q ) ⊗N with their correct probabilities, and hence to good approximation [16,17] we are simply applying the full channel. The final equality follows from calculating the composition of these quantum operations. This is exactly the state Eve expects to observe, hence our steganographic protocol is secret to an arbitrarily good approximation.
As described above, this protocol allows Alice to transmit a classical message m secretly to Bob. But in fact, by making this protocol coherent Alice can equally well transmit a quantum state-that is, a superposition of possible messages m. So we see that this protocol can transmit either classical or quantum information at the same rate h(p + δp) − h(p). The one significant difference between these two cases is that if Eve actually carries out a measurement of the error on the transmitted state, this would destroy the superpositions of a quantum message, but not affect the ability to transmit classical messages. So this protocol works for secret quantum communication if it is assumed that Eve only sometimes checks the code blocks transmitted from Alice to Bob. As we did in the case of steganographic communication over a noiseless channel [10], we can show this by considering a protocol in which Alice sends a subsystem M to Bob which is maximally entangled with a reference subsystem R (see Figure 1).

B. Depolarizing Channel
Suppose that Eve believes the quantum channel shared between Alice and Bob is a depolarizing channel with error rate p + δp, i.e., where the actual physical channel between Alice and Bob is N DC p . The protocol for Alice and Bob to communicate steganographically in this scenario is nearly identical to the protocol described in the previous subsection. First, Alice encodes an innocent state, i.e,. the covertext ρ c , into a nondegenerate quantum error-correcting code (QECC) on N qubits. This code should be able to correct typical errors induced by the channel (N DC p+δp ) ⊗N . Next, depending on the secret key k ∈ K and the message m ∈ M that she would like to send, she applies the error to her state. This produces the codeword corresponding to the message m. If her message to Bob is a quantum state, she can prepare the system in a superposition of these codewords. These codewords are generated by applying errors drawn randomly from the channel (N DC q ) ⊗N , using the shared secret key k as the source of randomness. That is, the errors X, Y , Z or I on each qubit are drawn from the product distribution p G N (g N ), where p G (g) is given by and q = δp/(1 − 4p/3). Since the errors are selected using the shared secret key k, Bob knows what codeword corresponds to each message m. The errors given by Eq. (8) are typical errors associated with the channel (N DC q ) ⊗N [16,17]. By the asymptotic equipartition theorem [18], for large enough N , it is highly likely that each of these codewords that Alice generates is a typical sequence with a sample entropy close to H(G) = −(1 − q) log(1 − q) − q log(q/3) ≡ s(q), where s(q) is the classical Shannon entropy of the depolarizing channel on one qubit with error parameter q in the Pauli representation. Furthermore, it follows from a simple calculation that N p •N q = N p+δp if we set q = δp/(1−4p/3), which is important for secrecy as discussed in the previous subsection.
Alice then sends her state through the channel (N DC p ) ⊗N . Following the same random coding argument described for the bit-flip channel, with high probability, the error J N Bob observes will be a typical error of the channel (N DC p+δp ) ⊗N . We know from Shannon's noisy channel coding theorem that if Alice and Bob set the number of messages |M| = 2 N R such that then Bob is able to decode correctly with high probability [18][19][20] classical or quantum bits of information to Bob steganographically. The proof of secrecy of this protocol is nearly identical to the one given in Eq. (6). Note that the assumption of a nondegenerate code is quite natural in the case of the bit-flip channel, which is essentially classical; but not as much so for the depolarizing channel, where the errors do not commute. We believe that this general procedure for encoding will work for degenerate codes as well, but the achievable rate may be lower, and will require an analysis specific to the code in question. We will return to this point at the end of the paper, where we conjecture a general formula for the steganographic rate of a quantum channel using general quantum codes.

C. Secret key consumption
Here we analyze how much secret key is used by the encodings outlined above. The details of the encodingthat is, how each message m is mapped to a codeword for a particular key element k-we assume have been decided between Alice and Bob ahead of time. Therefore secret key is required to pick the subsets of errors used in the encoding, but it is not needed otherwise.
Before the protocol begins, Alice and Bob divide the set of typical errors of the channel (N BF δp/(1−2p) ) ⊗N into n nonoverlapping subsets of size For each transmitted block, Alice and Bob must randomly choose one of these n subsets to encode her messages. This requires a number of bits K of secret key, which is positive for p + δp < 0.5. Therefore the key consumption scales linearly with N . Notice in the limit where the physical channel is noiseless i.e., p = 0, we have that K = 0, which agrees with our result in [10] where it was shown that only a sublinear amount of key is needed for encoding across noiseless channels. As discussed in [10], using this amount K of shared secret is key is sufficient to make the steganographic protocol secret, but not necessarily secure. That is, Eve should not become suspicious if she observes the state passing through the channel. However, if for some reason she knew a message was being sent, she would be able to deduce significant information about the message. This can be prevented by first encrypting the message before doing the steganographic encoding. If we wish to make the protocol both secret and secure, encryption would require M bits of secret key in the case of an Mbit classical message (using a one-time pad), or 2M bits of secret key in the case of an M -qubit quantum message (by twirling). Thus the rate of key consumption would FIG. 1. The information processing task we consider, of Alice sending M stego qubits to Bob over a quantum channel Np (which is either the quantum bit flip channel or depolarizing channel), which Eve believes to be noisier. Eve's ignorance of the channel is characerized by the parameter δp. Dependent on the secret key k, Alice encodes her message subsystem M and an innocent covertext ρc into a suitable quantum errorcorrecting code in such a way that once passed through the physical channel, it looks as though typical errors of the channel N p+δp have been applied. Bob then decodes the message and covertext using his copy of the shared secret key k. Alice's message is entangled with a reference system R. The ability to transmit entanglement can be used to bound the ability to do general quantum communication.
be increased by R (classical) or 2R (quantum, where R is the steganographic rate).

III. SECRECY, RELIABILITY, AND BOUNDS
A. The information processing task Now we wish to put a bound on the amount of information that can be sent with the steganographic scenario outlined above. Recall that Alice is using Eve's ignorance of the actual noise rate of the physical channel to hide her message. We will consider the quantum information processing task known as entanglement transmission (visualized in Figure 1) in this section. The maximum rate of entanglement transmission is clearly an upper bound on the maximum rate of quantum communication and so we will use this to derive a bound on the steganographic transmission rate. Alice prepares a secret message of M = log 2 |A 1 | qubits along with an innocent covertext ρ c . Her secret message qubits are maximally entangled with a reference system R. Her covertext will be encoded into the N -qubit quantum error-correcting code. Therefore her encoded state, which is dependent on the secret key element k, can be written as: The dependence of the encoding on the secret key corresponds to choosing among the different sets of typical errors of the channel N q in the protocols from the previous section. To someone (like Eve) who does not know the secret key k, the state is effectively where we have used linearity of quantum operations and ω A n R ≡ k p k ω k,A n R is the state averaged over all possible values of the secret key k with probabilities p k . (We can choose this probability to be uniform for simplicity, if we so desire.) What is a good way to guarentee secrecy from Eve? We propose the following secrecy condition: where N p+δp is what Eve believes the physical channel to be, V is an isometry representing the encoding of the covertext into a suitably chosen codeword (one which can correct typical errors induced by the channel N p+δp ) and δ > 0 is some small parameter. This condition means that if Eve observes the quantum state, it will be effectively indistinguishable from an encoded covertext being sent through the noisy quantum channel N p+δp . It is also important to discuss the requirement of recoverability. When Bob receives the state, he applies his decoder D k,A n →B1C to obtain the original state ρ c ⊗ Φ B1R . The recoverability condition can be written as follows: for all k, where > 0 is a small parameter.

B. Upper bound on steganographic rate
We are now in a position to put a bound on the number of qubits M that can be sent reliably and steganographically from Alice to Bob. First we define σ E = N ⊗N p+δp (V ρ c V † ) and apply the Fannes-Audeneart inequality [21] to the secrecy condition in Eq. (16): where g(N, δ) ≡ δN + h 2 (δ), and h 2 (·) is the binary entropy function. Also, from the recoverability condition we have (19) where f (N, ) ≡ N +(1+ )h 2 ( /[1+ ]). The first equality follows from the fact that the coherent information of a maximally entangled state is just the logarithm of the dimension of one of the subsystems. The first inequality follows from the Alicki-Fannes-Audeneart inequality [22] applied to the recoverability condition given in Eq. (17). The second inequality is a quantum data processing inequality [18]. The last equality follows from the definition of the coherent information.
Furthermore, using the concavity of the von Neumann entropy and linearity of quantum operations we have that and for many cases we expect H(N ⊗N p (Tr R [ω k,A n R ])) to be roughly the same for every k (see Sec. III C 1 and III C 2). Thus (21) for all k. Now putting Eq. (18), (19), and (21) together we arrive at our main result for this section, which states that Alice can secretly and reliably send M stego qubits to Bob, where M is bounded above by Thus, if we can compute a maximum for H(σ E ) = H(N ⊗N p+δp (ρ)) where ρ is pure (because V is an isometric encoding and ρ c is pure), and also compute a lower bound for H (N ⊗N p ⊗ I R )(ω k,A n R ) (or compute it explictly, recalling that ω k,A n R is a pure state), then we have a tight upper bound on the number of qubits M that can be sent steganographically over a noisy quantum channel N p .

C. Upper bounds for specific channels
For the channels discussed in the achievability section of this paper, we can now apply our result given in Eq. (22), where we make the implicit assumption that Alice is using a nondegenerate code. Though our result given by Eq. (22) is true in general, for a degenerate code the number of distinct error syndromes is smaller (depending on the code), and the bounds discussed here and achievable rates discussed in the previous section would be adjusted.

The bit flip channel
For the bit flip channel with parameter p + δp given by Eq. (1), the maximum of H((N BF p+δp ) ⊗N (ρ)) over all Nqubit pure states ρ is N h(p+δp) where h(p+δp) = −(p+ δp) log(p+δp)−(1−(p+δp)) log(1−(p+δp)) is the entropy of a single qubit sent through this bit flip channel. To prove this, consider some pure state ρ = |ψ ψ|. Then where we are summing over all binary strings s of length N ; X s is the operator acting on N qubits with an X acting at every location where s has a 1 and an I where s has a 0. The probability p(s) is given by where w(s) is the weight of string s. The Shannon entropy of this distribution is N h(p + δp) since it is a binomial distribution. The von Neumann entropy is the minimum Shannon entropy over all possible ensemble decompositions of the given state, and it is not hard to check that it is achieved when |ψ is a Z eigenstate. Thus we have computed a maximum for the first term on the right hand side of Eq. (22). Now we compute a lower bound for the second term on the right hand side of Eq. (22) in the case of the bit flip channel, i.e., H((N BF p ) ⊗N ⊗ I R )(ω k,A n R )). First note that we can write where the index is i = i 1 i 2 ...i N , the errors E i are given by and T is the set of typical sequences i corresponding to the typical errors of the channel (N BF p ) ⊗N [16,17]. Recall we are making the assumption that the QECC Alice is using to correct the typical errors of the channel (N BF p+δp ) ⊗N is nondegenerate. Because of this, we can infer that for each k, her encoded state ω k,A n R forms a nondegenerate code for the channel (N BF p ) ⊗N . This follows from the discussion in Section II A. This means that on a valid codeword in the QECC, for i ∈ T the typical errors E i all have distinct error syndromes, and act as unitaries that move the code space to a distinct, orthogonal subspace labeled by i. So an error E i occurs with a fixed probability p i for all valid codewords of the QECC. Recall also that since these errors are typical, they have almost all the probability, i.e.
for arbitrarily small > 0 (in the limit of large N ). From Eq. (25) we have that where the first inequality follows from the concavity of the von Neumann entropy and Eq. (27) , and the second inequality follows because the term proportional to is positive. Continuing, we have The first equality follows from the definition of the von Neumann entropy and Eq. (25). The inequality follows from performing a Taylor expansion on log(1 − ) and from the fact that for the bit flip channel (N BF p ) ⊗N : where the approximate equalities follow directly from the theory of typical sequences. Thus and combining this with the upper bound we computed for the first term in Eq. (22) gives for a sufficiently reliable and secret protocol and large enough block size N . Comparing this to Eq. (5), we have that the encoding described in the previous section for steganography over the channel N BF p where Eve expects the channel to be N BF p+δp is essentially optimal.

The depolarizing channel
Unfortunately, for the depolarizing channel N DC we do not know what N -qubit pure state ρ maximizes H((N DC p+δp ) ⊗N (ρ)). However, we can still bound this quantity, i.e., give an upper bound on the first term in Eq. (22). Consider the action of this channel on an N qubit pure state as follows: where {E j } is the set of typical errors associated with N applications of the channel (N DC p+δp ) ⊗N . Recall that we are choosing our isometric encoding to correct for typical errors of the channel Eve beleives to be connecting Alice and Bob, i.e. N DC p+δp . Furthermore, we're assuming that our code is nondegenerate. Therefore the states E j ρE † j are all orthogonal to each other for ρ in the codespace, and Tr[E j ρE † j ] = p j where p j are the typical probabilities associated with the errors E j . The von Neumann entropy is the Shannon entropy minimized over all possible decompositions, so the entropy of this state is clearly In a similar argument to the one given in Sec. III C 1 , we can give a lower bound for the second term on the right hand side of Eq. (22) in the case of the depolarizing channel. We get that where becomes arbitrarily small for large N . Combining this with the upper bound given in Eq. (34) we have that for a sufficiently reliable and secret protocol and large enough block size N . Comparing this to Eq. (11) we have that the encoding described in the previous section for steganography over the channel N DC p where Eve expects the channel to be N DC p+δp is essentially optimal, at least when we restrict ourselves to nondegenerate codes.

IV. CONCLUSION
Characterizing secret communication over noisy quantum channels is an interesting problem from both a practical and theoretical perspective. Here we have shown that two parties are able to communicate secretly with each other at a nonzero rate over a bit-flip or a depolarizing channel N p using a shared secret key, without arousing suspicion from a potential eavesdropper Eve, so long as Eve believes the channel to be noisier than it really is. Eve can be made to believe this through Alice and Bob systematically adding extra noise to the channel prior to secret communication. In this paper we gave explicit bounds on the number of stego qubits that Alice can send to Bob by hiding her secret message in the syndromes of a nondegenerate error-correcting code designed to correct the typical errors of the channel Eve believes: N p+δp . We also gave explicit encodings that achieve these bounds.
Interesting future work should include a generalization of these results to steganography over general quantum channels N . It is possible that in order to achieve the maximum possible rates in this scenario that degenerate codes are needed. For example, it is likely that the steganographic capacity we calculated for the depolarizing channel in this paper could be improved in this way. It is also possible that coding across multiple codeblocks using degenerate quantum codes could increase the steganographic capacity.
If the actual physical channel shared between Alice and Bob is N , and the channel Eve believes is M, then what is the quantum steganographic capacity? In this paper we proved that for the bit-flip channel, the rate is the difference of quantum capacities, i.e., Q(N BF p ) − Q(N BF p+δp ) = N (1 − h(p) − 1 + h(p + δp)) = N (h(p + δp) − h(p)). Also, allowing for our restriction to nondegenerate codes, this is true for the depolarizing channel as well. We conjecture that one might be able to prove that the steganographic rate in general will be Q(N ) − Q(M). This will require proof methods that go beyond those of the current paper, but we believe that this wll be an area of fruitful future study.