Quantum Encryption and Generalized Quantum Shannon Impossibility

The famous Shannon impossibility result says that any encryption scheme with perfect secrecy requires a secret key at least as long as the message. In this paper we provide its quantum analogue with imperfect secrecy and imperfect correctness. We also give a systematic study of information-theoretically secure quantum encryption with two secrecy definitions. We show that the weaker one implies the stronger but with a security loss in $d$, where $d$ is the dimension of the encrypted quantum system. This is good enough if the target secrecy error is of $o(d^{-1})$.


I. INTRODUCTION
Encryption schemes are typically considered as a computational primitive, since an information-theoretically secure (ITS) symmetric key encryption scheme can only securely encrypt messages of length at most the length of the secret key by Shannon's impossibility result [1]. This impossibility result has been extended to the case of imperfect secrecy and imperfect correctness (see [2]).
We start by revisiting the quantum Shannon impossibility for quantum encryption using classical keys. Let K be a discrete random variable. An encryption scheme is a quantum operation Ψ that maps a quantum state ρ to Ψ k (ρ) using a classical key k ← K with probability Pr(k). We say an encryption scheme is perfect if it maps an arbitrary quantum state to a fixed state and it is invertible. There is a lower bound on the entropy of keys that if an encryption scheme that perfectly encrypts n qubits using a classical key drawn from K, then where H is the Shannon entropy. The proof was given by Boykin and Roychowdhury for the case without any initial ancilla in encryption [3]. Ambainis et al. provided a more general proof that allows an initial fixed ancilla [4]. (A slightly more general version, where the initial ancilla state may depend on the key, was given in [5]. See also [6,7] for a different proof of the same lower bound.) For imperfect encryption, the encrypted state can deviate from a fixed state by an amount ǫ, which is called secrecy error (see Def. 5). It was shown by Desrosiers and Dupuis [8] that for an encryption scheme with secrecy error ǫ, the classical key K must have length [9] log |K| ≥ 2n + 2 log(1 − ǫ), where |K| denotes the size of the alphabet of K.
Herein we further consider the case of imperfect correctness, that is, the encryption is allowed to be non-invertible. The amount that a quantum state after encryption-decryption deviates its original is called correctness error (see Def. 4), We use the proof technique in [8] and generalize the statement: for an encryption scheme with secrecy error ǫ and correctness error γ, the classical key K must have length In the security definition of quantum encryption, it should be considered that the adversary may hold a quantum system that is entangled with the message quantum state to be encrypted. To achieve such security (Def. 5), the quantum Shannon impossibility says that a quantum encryption scheme has to use a classical key roughly twice as long as the quantum message. If the sender is not entangled with the adversary, Hayden et al. argued that a key of n + log n + 2 log(1/ǫ) bits is enough to approximately encrypt n qubits [10]. (See [11] for a discussion of the security with respect to different norms.) Ambainis and Smith proposed one quantum encryption scheme based on δ-biased set (generalized from [12]) that requires a key of n + 2 log n + 2 log(1/ǫ) + O(1) bits, together with two other schemes that use shorter keys [13]. Later Dickinson and Nayak improved this upper bound to n + 2 log(1/ǫ) + O(1) [14]. The entropic notion of this security was studied by Desrosiers [15]. Herein we will proceed to study this notion of security without assuming that the message quantum state is not entangled with the adversary (Def. 7), which is called weak information-theoretic security in this paper. We show that a weak ITS quantum encryption with secrecy error ǫ is also ITS but with secrecy error d 2 ǫ, where d is the dimension of the message state to be encrypted. As an application, we can prove the security of an encryption with respect to this weak notion when the secrecy loss is not that important. For example, the quantum homomorphic encryption scheme for Clifford circuits uses a key from the permutation group of O(n log n) bits, where n = log d [16]. Finally we will also prove a Shannon impossibility result for this weak notion of security. This paper is organized as follows. In Sec. II we give some basics about quantum information processing. Then we discuss the notions of quantum encryption in Sec. III. We prove the quantum Shannon impossibility results in Sec. IV, followed by the discussion section.

II. PRELIMINARIES
A quantum system will be denoted by a capital letter and its corresponding complex Hilbert space will be denoted by the corresponding calligraphic letter. For example, the Hilbert space of a quantum system A is A. We will use d A to denote the dimension of A. Let L(A) denote the space of linear operators on a complex Hilbert space A. A quantum state of system A is described by a density operator ρ ∈ L(A) that is positive semidefinite and with unit trace (tr(ρ) = 1). Let D(A) = {ρ ∈ L(A) : ρ ≥ 0, tr(ρ) = 1} be the set of density operators on A. When ρ ∈ D(A) is of rank one, it is called a pure quantum state and we can write ρ = |ψ ψ| for some unit vector |ψ ∈ A, where ψ| = |ψ † is the conjugate transpose of |ψ . If ρ is not pure, it is called a mixed state and can be expressed as a convex combination of pure quantum states.
Associated with an n-qubit quantum system is a complex Hilbert space C When ρ ∈ D(A) is diagonal in the computational basis {|0 , |1 , . . . , |d A − 1 }, we say ρ is classical. In this case, ρ corresponds to a discrete distribution on {0, 1, . . . , d A − 1}. In other words, a random variable of n classical bits can be represented as an n-qubit quantum state that is diagonal in the computational basis.
The Hilbert space of a joint quantum system AB is the tensor product of the corresponding Hilbert spaces A ⊗ B. We will use a subscript to specify which subsystem a vector belongs to or an operator operates on. Let I A denote the identity on the subsystem A. Thus the totally-mixed state in A is 1 dA I A . For ρ AB ∈ D(A ⊗ B), we will use ρ A = tr B (ρ AB ) to denote its reduced density operator in system A, where the partial trace is defined by A separable state ρ AB has a density operator of the form where ρ x A ∈ D(A) and ρ x B ∈ D(B). Especially when A is classical, is called a classical-quantum (cq) state.
The evolution of a quantum state ρ ∈ D(A) is described by a completely positive and trace-preserving map In particular, if the evolution is a unitary U , we have the evolved state U (ρ) = U ρU † . The trace distance between two quantum states ρ and σ is The fidelity between ρ and σ is where the maximization is over all purifications |φ of σ A and all purifications |ψ of ρ A or any fixed purification |ψ ′ of ρ A .
Below is a variant of Uhlmann's theorem.
Proof. Let |ψ ABR be a purification of ρ AB , which is immediately a purification of A relation between the fidelity and the trace distance of two quantum states was proved by Fuchs and van de Graaf [19] that When ρ or σ is pure, we have The min-entropy of A conditioned on B is defined as König et al. gave an operational definition of min-entropy [20]: where Ψ : B → B ′ is a quantum operation as defined in Eq. (2), B ′ ≡ A, and |Φ AB ′ = 1 √ dA x |x A |x B ′ is the maximally-entangled state. The leakage chain rule for conditional min-entropy when ρ AB is separable [8] says that

III. INFORMATION-THEORETICALLY SECURE QUANTUM ENCRYPTION
Suppose the sender holds a quantum system M , which may or may not be entangled with a quantum system E held by the adversary. The joint system of the sender and the adversary will be denoted by the subscript ρ ME . Definition 3. A symmetric-key quantum encryption scheme F is defined by the following algorithms: 1) (Key generation) F.KeyGen: 1 η → K, where η is a security parameter and K is a discrete random variable {k, Pr(k)} depending on η. The algorithm outputs a classical private key k ∈ K.
2) (Encryption) F.Enc k : D(M) → D(C). The algorithm takes a secret key k and a quantum state ρ ∈ D(M) as input and outputs a ciphertext σ ∈ D(C).
We will use Γ arg F.func to denote the quantum operation corresponding to the algorithm F.func with argument arg. For example, Γ k F.Enc is the encryption algorithm of F using a secret key k generated from the distribution K. In addition, when arg is a distribution, it means the quantum operation is averaged over the distribution. Consequently, Γ K F.Enc denotes the encryption algorithm of F weighted by the probability distribution K, that is, The encrypted quantum state in the view of the adversary is then Definition 4. (Correctness) F is an encryption scheme with correctness error γ = γ(η) if for any ρ ME ∈ D(M ⊗ E) and k ← F.KeyGen(1 η ), Semantic security in the computational setting was introduced by Goldwasser and Micali [21]. Following that, an information-theoretic security notion of entropy security was defined (in a classical setting) by Russel and Wang [22]. Dodis and Smith [12] discussed the security notions more generally and showed that entropy security is equivalent to a security notion of indistinguishability. Several ITS notions of perfect security are further discussed in [23,24]. Entropic security and entropic indistinguishability are also equivalent in the quantum settings [8,15]. It is natural to use trace distance as a measure of the indistinguishability of two quantum states.
Definition 5. (Secrecy) F is an ITS encryption scheme with secrecy error ǫ = ǫ(η) if there exists Ω M ∈ D(M) such that for any ρ ME ∈ D(M ⊗ E), This security definition says that an encrypted quantum state of an ITS encryption is statistically indistinguishable to the tensor product of a fixed quantum state and the local state of the adversary.
We can also define the security as follows.
Definition 6. (Secrecy) F is an ITS encryption scheme with secrecy error ǫ = ǫ(η) if for any ρ ME , ρ ′ ME ∈ D(M ⊗ E) with tr M (ρ ME ) = tr M (ρ ′ ME ), Definition 5 directly implies Def. 6 with secrecy error 2ǫ by the triangle inequality. On the other hand, consider ρ ′ ME = |0 E 0|⊗ ρ E , where ρ E = tr M ρ ME . Then Def. 6 directly implies Def. 5 with Ω M = Γ K F.Enc (|0 M 0|) and secrecy error ǫ. Therefore, these two definitions are equivalent up to a factor of 2. As a consequence, we will use Def. 6 for secrecy error and operationally we use the one that is more convenient for the context.
We can also define a weaker security without any reference involved.
Definition 7. (Weak Secrecy) F is a weak ITS encryption scheme with secrecy error ǫ = ǫ(η) if for ρ, ρ ′ ∈ D(M), For a perfect encryption scheme, the two notions are equivalent. If we assume that the message state is not entangled with the adversary, then the weak secrecy is equivalent to the regular secrecy. It is easy to show that if ρ ME is separable, the two notions are equivalent. Remark As in the standard language of cryptography, we define the secret key K, correctness error γ, and secrecy error ǫ as functions of the security parameter η. In the following discussion we will omit the security parameter as it is irelevent to our discussion.
Next we show that an weak ITS encryption scheme is also ITS but with an additional security loss in the dimension of the message system to be encrypted. Before we prove this statement, we need the following lemma.
Lemma 8. If F is a weak ITS encryption scheme with security error at most ǫ(κ), then, for x|y = 0, we have the following mathematical result: Proof. Assume x|y = 0. Consider |ψ 0 = 1 ✷ Theorem 9. If F is a weak ITS encryption scheme with security error at most ǫ, then F is a regular ITS encryption scheme with secrecy error at most d 2 ǫ, where d is the dimension of the encrypted message system.
Proof. Suppose that F is a weak ITS encryption scheme by Def. 7 with secrecy error ǫ. We first consider a pure state ρ ME = |ψ ME ψ| with |ψ ME = i √ λ i |i M |i E and ρ E = tr M (|ψ ME ψ|) = i λ i |i E i|. We would like to show that If this equation holds for any pure ρ ME , then for σ ME = j p j ρ j ME , where ρ j ME are pure, we have It remains to prove Eq. (12).
where (a) is because A ⊗ |i j| tr = 1 2 A † A ⊗ |j j| = A tr and (b) is by Def. 7 and Lemma 8. ✷ As an application of this theorem, it suffices to prove that an encryption scheme is ITS with respect to Def. 6 if we target at secrecy error o(2 −n ), where n is the number of encrypted qubits. Example 1. Ambainis and Smith introduced an approximate quantum encryption scheme based on δ-based sets [13]. It was shown that the Ambainis-Smith scheme is ITS with secrecy error δ2 n [8] On the other hand, it is weak ITS with secrecy error δ2 0.5n [13] and hence ITS with secrecy error at most δ2 2.5n by Theorem 9.
Example 2. The secrecy of the quantum homomorphic encryption scheme for Clifford circuits by Ouyang et al. [16] was proved with respect to the weak secrecy (Def. 7) but we can prove its IT-security with respect to Def. 6 without much loss in parameters by Theorem 9. Similarly for the secrecy of the quantum homomorphic encryption scheme for the instantaneous quantum polynomial (IQP) circuits in [25].
At the end of this section we prove a theorem, which is similar to [4,Theorem 5.2], saying that an n-qubit imperfect encryption scheme can encrypt 2n classical bits with the same correctness and secrecy errors. Proof. Suppose F is ITS by Def 6. Define U |x = σ x ⊗ I 1 √ 2 n i∈{0,1} n |i A |i B for x ∈ {0, 1, 2, 3} n , where σ x = n j=1 σ xj . That is, U maps x to one of the 2n-qubit Bell states. Let F ′ .Enc k : {0, 1, 2, 3} n → D(C 2 2n ) be the algorithm corresponding to the following operation: LetŨ denote the inverse of U , which does the Bell measurement such thatŨ (U |x x|U † ) = |x x|. Note that U can be implemented by a unitary circuit, and henceŨ can be implemented by the reverse of that unitary circuit. Let F ′ .Dec k : D(C 2 2n ) → {0, 1, 2, 3} n be the algorithm corresponding to the following operation: When the message is classical, the joint state of the sender and the adversary ρ ME is a cq state. Thus the correctness of the encryption on the message alone implies the general correctness in Def. 4. Therefore, by the correctness of F . Similarly, for the encryption of classical messages, the weak security in Def. 7 implies the regular security in Def. 6. For v, v ′ ∈ {0, 1, 2, 3} n , where ρ AB = 1 2 n i,j∈{0,1} n σ v |i j| (σ v ) † ⊗ |i j| and similarly for ρ ′ AB . Note that tr A ρ AB = tr A ρ ′ AB . The last inequality follows from the secrecy of F (Def 6). ✷

IV. QUANTUM SHANNON IMPOSSIBILITY
In this section we generalize Shannon's impossibility in the quantum case.
Theorem 11. Suppose F = (KeyGen, Enc, Dec) is an ITS quantum encryption scheme on M = C 2 n with correctness error γ and secrecy error ǫ. Then Proof. Let where |Φ MC is the maximally-entangled state. Let By the secrecy of F, we have ρ MC − σ MC tr ≤ ǫ and hence by Eq. (4), Let which satisfies tr K ρ MCK = ρ MC . By Uhlmann's theorem (Corollary 2) and Eq. (13), there exists σ MCK with tr K (σ MCK ) = σ MC such that Let V = k |kk KK ′ k| K and let τ MCK = tr K ′ V σ MCK V † . This ensures that τ MCK is classical on K and it still holds that tr K τ MCK = σ MC . Then we have where Γ F.Dec,K is the decryption operation controlled by the K subsystem. Hence tr K I M ⊗ Γ F.Dec,K (ρ MCK ) − tr K I M ⊗ Γ F.Dec,K ( √ 2ǫ. Thus which implies, by Eq. (5), where (a) is by Eq. (6); (b) follows from the leakage chain rule Eq. (7) and that tr K τ MCK = σ MC and H min (M |C) τ = n. Therefore, we have log |K| ≥ 2n + log 1 − γ + √ 2ǫ .

✷
Next we consider a quantum Shannon impossibility for quantum encryption with weak IT-security in Def. 7.
Following steps similar to the proof of the previous theorem, we have log |K| ≥ 2n + log 1 − γ + √ 2 n ǫ .

V. DISCUSSION
In this paper we studied quantum encryption with imperfect correctness and imperfect secrecy. We discussed two notions of information-theoretic security and we showed that the weak security (Def. 7) implies the regular security (Def. 5) but with a secrecy loss in the dimension of the encrypted message (Theorem 9). Two examples of the Ambainis-Smith δ-biased set scheme and the quantum homomorphic encryption scheme for Clifford circuits were given for applications of Theorem 9. We also showed that an imperfect quantum encryption scheme that encrypts n qubits can encrypt 2n classical bits with the same correctness and secrecy errors (Theorem 10).
The quantum Shannon impossibility results were generalized to the case with imperfect secrecy and imperfect correctness for both notions of security. For ǫ ≪ 2 −n , a weak ITS quantum encryption scheme is also ITS by Theorem 9. In this case, our Shannon impossibility results for weak ITS scheme also agrees that roughly 2n bits are necessary to encrypt n qubits. For regular ITS quantum encryption schemes our lower bound (Theorem 11) is slightly lower than the one by Desrosiers and Dupuis in Eq. (1) in the case of γ = 0. This is because we have to use fidelity and trace distance alternatively in the proof, using the inequalities of Fuchs and van de Graaf Eq. (4), which induces a loss in the secrecy error.