Nov 16, 2007 - definition of entropic security and entropic indistinguishability defined by Dodis and Smith. We prove ... it is allowing relaxation of...

0 downloads 51 Views 193KB Size

arXiv:quant-ph/0703046v2 16 Nov 2007

Universit´e McGill, Montr´eal, Qu´ebec

Abstract. We present two new definitions of security for quantum ciphers which are inspired by the definition of entropic security and entropic indistinguishability defined by Dodis and Smith. We prove the equivalence of these two new definitions. We also propose a generalization of a cipher described by Dodis and Smith and show that it can actually encrypt n qubits using less than n bits of key under reasonable conditions and yet be secure in an information theoretic setting. This cipher also totally closes the gap between the key requirement of quantum ciphers and classical ciphers.

Keywords: Quantum cryptography, approximate encryption, entropic security, information theory, private quantum channel.

1

Introduction

In a seminal paper, Goldwasser and Micali [6], proposed a new definition of security in classical cryptography. In this article, they gave two new definitions of security, semantic security and indistinguishability, and proved that they are in fact equivalent. This was a significant paradigm shift from previously used security definitions. Both definitions rely on limitations imposed on an adversary that would intercept a cipher text, that is, the adversary is limited to be a probabilistic polynomial-time machine. This is fundamentally a computational security setting. How to translate these definitions to the information setting remained unknown for years. Russell and Wang [9] introduced in 2002 a satisfactory definition for the information theoretic setting. In their paper, Russell and Wang shifted the limitations imposed to the adversary from computational limitations to entropic limitations: the adversary limitation is in fact a lower bound on its min-entropy on the message space, bound which we will denote by t. It is to be mentioned that similar concepts for hash functions had already been developed by Canetti et al. in [3,4]. Unfortunately, Russell and Wang had limited the scope of their definition by requiring that the adversary could not predict any predicate of the message based on the cipher text. Furthermore, their proof was rather involved. This was remedied by Dodis and Smith [5] who extended the definition to all functions, gave a new definition of entropic indistinguishability similar to that of Goldwasser and Micali and proved the equivalence between the two. They also provided three different encryption schemes and proofs that they are secure according to entropic security. Entropic security is, in a sense, surprising since it is allowing relaxation of the traditional informational theoretic security definition that goes back to Shannon. Indeed, if one requires that the mutual information between the cipher text and the message be smaller than some ǫ, then one can only shorten the key length by ǫ bits. Entropic security lets one reduce the key size to n − t + 2 log (1/ǫ) + O(1) bits [5], which constitutes a nontrivial

improvement. If the reader whishes to gain some intuition on why this is possible, we advise him to read the introduction of [5]. In parallel to this development, quantum security began with a Shannon-like definition of security which requires the cipher text E(ρ) to be equal to ρ0 , some fixed state, for all messages ρ in the message space. This was initially proposed by Ambainis, Mosca, Tapp and de Wolf in 2000 [1]. This definition was later relaxed by Hayden, Leung, Shor, Winter [7] by requiring that the distance between the cipher text and the perfectly mixed state be smaller than some security parameter ǫ. They also made the critical assumption that the eavesdropper was not entangled with the sender, an assumption which was not necessary in [1] — we also impose this condition in order for our scheme to work. Unfortunately, their proof was not constructive, but they proved that there exists an encryption scheme such that the key length is n + log(n) + 2 log(1/ǫ). Ambainis and Smith [2] then gave explicit polynomial-time constructions that can reduce the key space further in certain conditions. Their first construction uses n + 2 log(n) + 2 log(1/ǫ) + O(1) bits of key to encrypt n qubits. Their second construction, which is not length preserving, even goes down to n + 2 log(1/ǫ) bits of key per n qubits. In this paper we shall reduce the key size even further. We shall prove that a generalization of a scheme proposed by Dodis and Smith can actually use less key, that is n − t + 2 log(1/ǫ) bits of key for n qubits, where t represents the min-entropy of the adversary on the message space. This means that if t is greater than 2 log(1/ǫ), which is not unreasonable, then the scheme actually requires less than n bits of key for n qubits. We achieve this by generalizing the entropic security and indistinguishability definitions contained in [5] to a quantum setting. We also prove their equivalence. These definitions look quite simple and straightforward, but in fact are quite unsettling to anyone close to the quantum computing community. The paper is divided as follows: in Section 2 we present our definitions of security and discuss the details of their interpretation. In Section 3 we prove that they are equivalent. In Section 4 we present an encryption scheme and prove that it uses n − t + 2 log(1/ǫ) bits of key for n qubits. Further contributions of this paper are: 1) a much simpler proof of the equivalence for all functions between our two definitions; 2) the first information-theoretic quantum encryption scheme which does not require more key than its classical counterpart. We assume that the reader is well-familiar with quantum information theory, that is linear algebra, POVMs, super-operators, distance measures and operator decompositions. For an introduction see [8].

2

Definitions

We are interested in the following scenario. The sender chooses a message from a known message space and encrypts the message. We want that whenever an adversary intercepts an encryption it P can not predict any function on the message. More P formally, let an interpretation of ρ = γ |ji hj| be an ensemble {(p , σ )} such that ρ = i i j j i pi σi , we say σi is compatible with ρ. This is the eavesdropper’s view of the message space — i.e. the a priori knowledge of the adversary is given by the ensemble {(pi , σi )}, which consists of all the possible messages (by which we mean valid density operators, or physically possible messages) with non-zero probability along with their probability. We want that whenever the sender chooses a message σi and encrypts it using a cipher 2

E, then no eavesdropper which intercepts E(σi ) can guess any function of σi . We will require this property to hold for all ρ with sufficiently high min-entropy, where H∞ (ρ) , H∞ ({γj }) , − log(maxj (γj )). Naturally, this question is pertinent in a context where interaction is not desirable or too costly to use. Definition 1. An operator E is an encryption scheme if there exists another operator D such that for all states ρ we have D(E(ρ)) = ρ. Definition 2. An encryption scheme E is said to be (t, ǫ)-entropically secure if for all states ρ such that H∞ (ρ) > t, all associated interpretations {(pi , σi )}, and all adversaries A there exists A′ such that for all functions f we have Pri [A(E(σi )) = f (σi )] − Pri [A′ (·) = f (σi )] < ǫ.1 (1)

A few explanations are in order. First, in this equation, only one state is physical, that is, E(σi ). For this equation to be meaningful, all other states are not considered to be physical but purely mathematical. By this we mean that the σi are considered to be strings of bits that can be interpreted as density operators. This is reasonable since A′ never gets his hands on any ciphers, exactly as in the traditional definition. Hence, {(pi , σi )} simply is the a priori knowledge of A and A′ on the message space from which the sender samples. We therefore naturally consider that the output of f (σi ) is simply a string of bits.2 Furthermore we do not impose any restriction on f . In particular, we do not require that f bePa physical process, hence f is not required to be linear or to be a function on operators — g(ρ) = i g(γj ) |ji hj|.

Hence A has to predict the output of the function f on the string of bits that represents the state σi , which is unknown to A, by only analyzing E(σi ) which is a physical state — no restriction are put on A, we only require it to be a physical process, i.e a POVM. The adversary A′ does not get this chance, he must predict the same function f on the same bit string but having access to nothing but the message interpretation {(pi , σi )}. The obvious best strategy for A′ is to bet on the most probable output for f , since all other outputs have less chance of occurring. So by definition Pri [A′ (·) is right] = Maxf , maxz Pri [f (σi ) = z] where Z = {z} is the set of possible outputs for the interpretation {(pi , σi )} — note that we assume that A and A′ know the correct interpretation which is considered to be the message space. Quantum entropic security states that if A can predict the function f with a given probability, then this probability can be matched by A′ up to ǫ, equivalently Pri [A(E(σi )) = f (σi )] 6 Maxf + ǫ.

As in [6] and [5], we can introduce a notion of indistinguishability and then show that indistinguishability and entropic security are equivalent. Definition 3. An encryption scheme E is said to be (t, ǫ)-indistinguishable if for all operators ρ such that H∞ (ρ) > t we have

E(ρ) − I < ǫ, (2)

d tr 1

2

Note that probabilities are not taken only over i, but also all randomness used by A, A′ and E . Note that instead of considering functions on strings of bits, one could consider that the function f acts on the indices i of σi and get an equivalent framework.

3

where d is equal to the dimension of the message space. We use the following definition for the trace distance: kρ − σktr = 12 tr |ρ − σ| and |A| , following theorem, Theorem 9.1 in [8], will be useful.

√

A† A. The

Theorem 1. Let {Em } be a POVM with pm = Tr (Em ρ) and qm = Tr (Em σ) as the probabilities of obtaining a measurment outcome labeled by m. Then ) ( 1X |Tr (Em (ρ − σ))| , (3) D(ρ, σ) = max D(pm , qm ) = max {Em } {Em } 2 m where the maximization is over all POVMs {Em } and D(ρ, σ) ,

1 2

kρ − σktr .

It is now time to introduce one assumption we are making all along this article. We assume that E(I/d) = I/d, which is true for all reasonable schemes we know: our cipher in section 4 will have this property. This is very powerful since we can, by the spectral decomposition theorem, decompose I/d in the basis of our choice, in particular the basis of E(ρ). This is equivalent to saying that I/d and E(ρ) commute (which is trivially true for I/d), hence that the trace distance between the two operators is equal to the statistical distance of their eigenvalues: kE(ρ) − I/dktr = D(λi , 1d ). This basically means that (t, ǫ)-indistinguishability implies that there is no POVM that can distinguish between E(ρ) and I/d.3 It is also easy to see, using the triangle inequality, that Definition 3 implies: Definition 4. An encryption scheme E is said to be weakly (t, ǫ)-indistinguishable if for all operators ρ and ρ′ such that H∞ (ρ) > t and H∞ (ρ′ ) > t we have

E(ρ) − E(ρ′ ) < 2ǫ. (4) tr

Obviously weak (t, ǫ)-indistinguishability implies (t, 2ǫ)-indistinguishability. We must introduce a fourth notion which is a strong version of Definition 2. Definition 5. An encryption scheme E is said to be strongly (t, ǫ)-entropically secure if for all states ρ such that H∞ (ρ) > t, all interpretations {(pi , σi )} and all adversaries A we have for all function f |Pri [A(E(σi )) = f (σi )] − Pri [A(E(ρ)) = f (σi )]| < ǫ. (5)

The only difference with Definition 2 is that we have restricted the notion of A′ : this adversary is now the same as A but it receives an encryption of ρ. Basically, Equation (5) means that whatever A can compute from E(σi ), with probability up to ǫ he could have computed it using only an oracle serving an encryption of ρ which is totally independent of σi . This strategy is clearly worse that the optimal one, since Pri [A(E(σi )) = f (σi )] 6 Pri [A(E(ρ)) = f (σi )] + ǫ 6 Maxf + ǫ, 3

See [8] Chapter 9 for a proof these statements.

4

(6)

because no strategy can do better than Maxf without seeing the cipher text. Therefore, it means that E(·) must be a better scheme to achieve this definition, since A can not do much better than this worse strategy can do (ǫ better at best). Furthermore, not only does there exist an adversary A′ but this adversary can be easily constructed using A as a black box. Hence strong-entropic security implies entropic security. As is traditionally the case in semantic security, Definition 2 carries the meaning of what is considered a secure encryption scheme. Definition 3 will allow us to prove that a given scheme is secure and Definition 5 will let us show easily that these two definitions are equivalent for all functions and not just for predicates.

3

Equivalence between the two paradigms

Lemma 1. Strong (t, ǫ)-entropic security implies (t−1, 2ǫ)-indistinguishability as long as t ≤ n−1. Proof : We are translating, for this lemma, the proof from Dodis and Smith to the quantum setting. The last part, for non-orthonormal states, is new to this work. It is well known that a classical t-source4 can be decomposed into a convex combination of flat sources over 2t points5 . Moreover the two are linked in an easy way: if X is a classical t-source, and Y is an equiprobable P distribution onPthe first t 2 points (the order is arbitrary), then there exists {Pi } such that X = i pi Pi Y , where i pi = 1 and the Pi ’s are permutation matrices. It is less known, yet also true, that we can say the same thing about density operators. Let ρ be a state such that H∞ (ρ) > t and let σ be a perfectly mixed state with H∞ (σ) = H(σ) = t (i.e the support(σ) has size 2t ). Then we can decompose ρ this way X pi Ui σUi† , (7) ρ= i

P

where i pi = 1 and the Ui ’s are unitary operators. It must also be said that if ρ and σ commute, then the Ui ’s are just permutation matrices.6 These observations will allow us to prove the lemma for flat sources of entropy t − 1 only. Indeed, E can not decrease entropy, so H∞ (E(ρ)) > t and I/d is of course a t source. So we can write P ρ = i pi Xi where Xi = Ui σUi† , the Ui ’s are permutation matrices and σ is a flat (t − 1)-source P which we choose in the eigenbasis of ρ. Similarly, we can write I/d = j qj Yj , where Yj = Vj σVj† (the reader should keep in mind that we can diagonalize I in the basis of our choice, so we choose the eigen-basis of ρ, hence ρ, I/d and σ all commute with one another). We know that E(I/d) = I/d.

P

P P P

So kE(ρ) − E(I/d)k = E( i pi Xi ) − E( j qj Yj ) .7 Since i pi = j qj = 1, we can write this:

P

P

P P P P

E(( j qj ) i pi Xi ) − E(( i pi ) j qj Yj ) which simplifies to E( i,j pi qj Xi ) − E( i,j pi qj Yj ) . 4

5

6 7

A t-source is a random variable with min-entropy no less than t. A t-flat source, is a uniform distribution over 2t points. For a proof of all these statements, read the section on majorization theory in [8]: Section 12.5.1. We have dropped momentarily the tr indices to the trace distance for compactness.

5

P

P

Since E is a linear operator we can rewrite everything this way: i,j pi qj E(Xi ) − i,j pi qj E(Yj )

P

which we can simplify to i,j pi qj (E(Xi ) − E(Yj )) . Using the triangle inequality, we can conclude: kE(ρ) − E(I/d)k 6

X

pi qj kE(Xi ) − E(Yj )k .

i,j

(8)

This equation tells us that if all terms kE(Xi ) − E(Yj )k are less than 2ǫ, then Equation (8) is bounded by 2ǫ and in particular the cipher must be (t − 1, 2ǫ)-indistinguishable. P So let W0 ∈ {Xi }, where, ρ = i pi Xi and let W1 ∈ {Yj }. Assume for now they have orthonormal support. Consider the operator Z = 1/2W0 + 1/2W1 : an equal mixture of the 2 states. By construction, H∞ (Z) = t. Define the predicate g such that for any state τ0 compatible (see page 2) with W0 , g(τ0 ) = 0, and for any state τ1 compatible with W1 , g(τ1 ) = 1. It is not necessary to define the value of g for any other state. Any adversary, A, that can predict g given E(τb ), for b ∈R {0, 1}, is therefore a distinguisher between E(W0 ) and E(W1 ). It is common knowledge (see [8]) that, at best, such an adversary can do this with probability: Pr[A(E(τb )) = g(τb ) = b] =

1 1 + kE(W0 ) − E(W1 )ktr . 2 2

(9)

We can now invoke the entropic security definition. So we can also write: Pr[A(E(τb )) = g(τb ) = b] 6 Pr[A′ (·) = g(τb ) = b] + ǫ =

1 + ǫ. 2

(10)

By construction no adversary A′ can guess the correct answer with probability better than one half. Using Equations (9) and (10), we can conclude: kE(W0 ) − E(W1 )ktr 6 2ǫ.

(11)

We are almost done. Let us now suppose that W0 and W1 are not orthogonal but not equal. Let V be the space spanned by their intersection. This space, V is well defined and V is not equal to W0 nor W1 . Because ρ and I/d commute and because we already concluded that W0 and W1 commute, we can treat these objects as classical distributions on classical points, and treat their eigen-basis as points in sets (We abuse notation in that spirit here). Hence we can create a new state W0′ such that W0 ∩ W0′ = W0 \ V and W0′ ∩ W1 = ∅. We can do this since t 6 n − 1, so we have plenty of space to choose new points. Of course we choose W0′ such that it has min-entropy equal to t − 1 and such that it is a t − 1 flat source. Obviously, by construction we have kW0 − W1 k 6 kW0′ − W1 k, hence, using our argumentation for orthogonal states, and the fact that W0 , W1 and W0′ commute, we can conclude that

kE(W0 ) − E(W1 )ktr 6 E(W0′ ) − E(W1 ) tr 6 2ǫ. (12) QED.

Lemma 2. Let ρ be a state such that H∞ (ρ) > t and let {(pi , σi )} be an interpretation of ρ. Then for all i we have that pi · λmaxi 6 2−t , where λmaxi is the biggest eigenvalue of σi . 6

Proof : Suppose, on the contrary, that pi ·λmaxi > 2−t . Since λmaxi is an eigenvalue of σi , there exists a vector |vi such that hv| σi |vi = λmax together let us writePhv| ρ |vi > pi hv| σi |vi > Pi . These two observationsP 2−t . We also know that ρ = k γk |ki hk|, so hv| ρ |vi = k γk hv|ki hk|vi 6 k 2−t hv|ki hk|vi = 2−t . Hence we conclude that 2−t < hv| ρ |vi 6 2−t , which is an obvious contradiction. QED. Lemma 3. Let ρ be a state, {(pi , σi )} be an interpretation, E be a cipher, f be a function and A be an Adversary such that |Pri [A(E(σi )) = f (σi )] − Pri [A(E(ρ)) = f (σi )]| > ǫ, then there exist an adversary B and a predicate h such that |Pri [B(E(σi )) = h(σi )] − Pri [B(E(ρ)) = h(σi )]| >

ǫ . 2

Proof : Let our predicate be a Goldreich-Levin predicate, that is hr (x) = r ⊙ f (x), where ⊙ denotes the scalar product of the binary vectors represented by the strings f (x) and r. Let p = Pri [A(E(σi )) = f (σi )] and q = Pri [A(E(ρ)) = f (σi )]. Then we know that |p − q| ≥ ǫ. Let us compute E = |Er [Pri [r ⊙ A(E(σi )) = hr (σi )] − Pri [r ⊙ A(E(ρ)) = hr (σi )]]| ,

(13)

where the expectation is taken over all r of adequate size. We need two observations. First, when A predicts correctly, then Pri [r ⊙ A(E(σi )) = hr (σi )] = 1. Second, when A does not predict correctly, the probability that r ⊙ A(E(σi )) = hr (σi ) is exactly one half. Hence Equation (13) reduces to p − q ǫ 1 1 > . (14) E = 1 · p + · (1 − p) − 1 · q + · (1 − q) = 2 2 2 2 There exists at least one value r such that the following is true:

ǫ |Pri [r ⊙ A(E(σi )) = hr (σi )] − Pri [r ⊙ A(E(ρ)) = hr (σi )]| > . 2 The lemma is proven if we define adversary B(·) as r ⊙ A(·) for this appropriate r. QED.

Lemma 4. (t − 1, ǫ/8)-indistinguishability implies strong (t, ǫ)-entropic security for all functions as long as t 6 n − 1. Proof : The proof technique used in this lemma is new to this work, as far as we know. Suppose that there exists an adversary B, a state ρ, where H∞ (ρ) > t, an interpretation {(pj , σj )} for ρ and a function f such that |Pri [B(E(σi )) = f (σi )] − Pri [B(E(ρ)) = f (σi )]| > ǫ.

(15)

We want to show that this adversary implies that the encryption scheme E is not (t − 1, ǫ/8)indistinguishable. Then, by the previous lemma, we know that there exists another adversary A and a predicate h such that strong (t, ǫ/2)-entropic security is violated. Let us define two sets E0 and E1 this way: 7

– E0 = {i|h(σi ) = 0} – E1 = {i|h(σi ) = 1}. P P P P Let r0 = i∈E1 pi σi /r1 . i∈E0 pi and r1 = i∈E1 pi . Let τ0 = i∈E0 pi σi /r0 and τ1 = Obviously, ρ is equal to r0 τ0 + r1 τ1 and both τ0 and τ1 are valid density operators. So if we restate the entropic security violation in terms of the τi , we get ǫ (16) |Pri [A(E(τi )) = h(τi )] − Pri [A(E(ρ)) = h(τi )]| > , 2 where h(τi ) = i. The adversary A is a POVM with two elements — A0 and A1 —, so we can rewrite equation (16) this way: X ǫ (17) pi Tr Ah(τi ) E(τi ) − Tr Ah(τi ) E(ρ) > i=0,1 2

where Tr (Ak γ) is the probability that A on γ outputs k, in our case, there are only two possible outputs: zero and one. From the last equation, since there are only two terms in the sum, we can conclude that there exists i such that ǫ (18) pi Tr Ah(τi ) E(τi ) − Tr Ah(τi ) E(ρ) > . 4 Let us assume without loss of generality that i is in fact zero and let us construct the two following states (choosing i to be one, would lead to a similar argument): – τ0′ , r0 τ0 + r1 dI – ρ′ , r0 ρ + r1 dI

Obviously, ρ′ is a t-source since it is a convex combination of two t-sources. On the other hand, the largest eigen-value of τ0′ cannot be larger than 2−t + r1 ∗ d1 (we have used Lemma 2, and the fact that we can decompose I/d in the same basis as the eigen basis of τ0 ). Since r1 1/d 6 2−t , we conclude that the largest eigen-value of τ0′ is not larger than 2−(t−1) . Hence, H∞ (τ0′ ) > t − 1. Let us now compute the following expression: Tr Ah(τ ) E(τ0′ ) − Tr Ah(τ ) E(ρ′ ) = Tr Ah(τ ) E(τ0′ ) − E(ρ′ ) , 0 0 0

(19)

which will give us a lower bound on the trace distance of E(τ0′ ) and E(ρ′ ) as Theorem 1 tells us, since Ah(τ0 ) is a fixed POVM element. Tr Ah(τ0 ) E(τ0′ ) − Tr(Ah(τ0 ) E(ρ′ )) I I = Tr Ah(τ0 ) E r0 τ0 + r1 − Tr Ah(τ0 ) E r0 ρ + r1 d d I I − Tr Ah(τ0 ) E (r0 ρ) − Tr Ah(τ0 ) E r1 = Tr Ah(τ0 ) E (r0 τ0 ) + Tr Ah(τ0 ) E r1 d d = r0 Tr Ah(τ0 ) E (τ0 ) − Tr Ah(τ0 ) E (ρ) ǫ > , 4 8

where the last step comes from equation (18). Hence τ0′ an ρ′ constitute a violation of (t − 1, ǫ/8)weak-indistinguishability, which in turns implies a violation of the (t−1, ǫ/8)−indistinguishability. QED. We can summarize the two last lemmas in this theorem. Theorem 2. Entropic security and entropic indistinguishability are equivalent up to small variation in parameters.

4

A quantum entropic encryption scheme

We now present a generalization of the scheme proposed in Section 3.2 of [5]. The proof technique used here is new to this work and achieves slightly better results than [5]. Definition 6. Let Hn = {hi }i∈I be a family of permutations over n bit strings. Consider the event A = hi (x) ⊕ hi (y). We say the family Hn is strongly-XOR-universal if for all x, y and all a 6= 0 we have 1 Pri←I [A = a] 6 n . 2 The family proposed in [5] naturally possesses this property. Notice that the probability of seeing A = a = 0 can be much larger than 1/2n : in fact it is equal to the collision probability of the input.

Proposition 1. Let H2n be a strongly-XOR-family of permutations. Consider the super-operator E(ρ) = hi, X a Z b ρZ b X a i 8 , where i is chosen at random uniformly over 2n bit strings and akb = hi (k), where k is the secret key (akb denotes the concatenation of the strings a and b). Then E is a quantum cipher.

Theorem 3. The cipher of proposition 1 is (t, ǫ)-indistinguishable for all state ρ such that H∞ (ρ) ≥ t as long as H∞ (K) + H∞ (ρ) > n + 2 log(1/ǫ).

Proof : We will use the following trick: if ρ has rank d and Tr E(ρ)2 6 1/d(1+ ǫ2 ), then kE(ρ)− I/dktr 6 ǫ, which implies the desired (t, ǫ)-indistinguishability.9 The adversary’s view can be written this way: 8 9

X a Z b = X a1 Z b1 ⊗ · · · ⊗ X an Z bn if a = a1 . . . an and b = b1 . . . bn . See [2] and [5].

9

ρ′ = E(ρ) = Ea,b,i [i ⊗ X a Z b ρZ b X a ]. We are interested in the following quantity Tr E(ρ)2 . So 1 Tr Ek,k′ ,i [X a Z b ρZ b X a X c Z d ρZ d X c ] (20) Tr E(ρ)2 = |I| 1 Tr Ek,k′ ,i [Z d X c X a Z b ρZ b X a X c Z d ρ] (21) = |I| 1 = Tr Ek,k′ ,i [(−1)d⊙c (−1)d⊙a X c X a Z d Z b ρZ b X a X c Z d ρ] (22) |I| 1 Tr Ek,k′ ,i [((−1)d⊙c )2 ((−1)d⊙a )2 X c X a Z d Z b ρZ b Z d X a X c ρ] (23) = |I| 1 Tr Eef,i [X e Z f ρZ f X e ρ] (24) = |I|

where akb = hi (k) and ckd = hi (k′ ) and where k and k′ are independent instances of the key. Also ekf = (a ⊕ c)k(b ⊕ d) = (akb) ⊕ (ckd). By Definition 6, we know that the probability of seeing any string ekf , different from zero, is bounded above by 1/22n . Let us divide Equation (24) into two terms, one for ekf = 0 and the other for all the ekf 6= 0. Let us introduce the following notations: ρef instead of X e Z f ρZ f X e and pef for the probability that ekf is observed. Thus, we can rewrite everything like this : ρ2 1 Tr + Tr E(ρ)2 = |I| |K|

X

e,f where ekf 6=0

pef ρef ρ .

(25)

P 1 n Observe two things: for all ekf 6= 0 we know that pef 6 1/22n and ef 22n ρef = I/2 , the perfectly mixed state. Quantum mechanic also tells us that Tr (ρσ) is the expectation of the observed eigenvalue if one measures the observable ρ on the state σ. A specific case is Tr 2In ρ = 1/2n , since all eigenvalues of the perfectly mixed state are equal to 1/2n , the average can not be different from this number. P Let A be the positive operator e,f pef ρef . From the previous observations, we can conclude that ekf 6=0 P there exists a positive operator B such that A + B = I/2n — B = e,f ( 21n − pef )ρef and p0k0 = 0. Therefore Tr ((A + B)ρ) 6 21n , thus Tr (Aρ) + Tr (Bρ) 6 21n and finally Tr (Aρ) 6 21n . So we can rewrite Equation (25) this way: 2

Tr E(ρ)

1 6 |I|

Tr

ρ2 |K|

1 + n 2

.

(26)

Let us denote H∞ (K) by tK = log |K| and H∞ (ρ) by tρ . By hypothesis, we have H∞ (K) + H∞ (ρ) > n + 2 log(1/ǫ), hence 2n−tk −tρ 6 ǫ2 . We can thus rewrite (26) this way: 1 1 n−tk −tρ 1 1 2 Tr E(ρ)2 6 +1 6 2 ǫ +1 , (27) n n |I| 2 |I| 2

since Tr ρ2 6 1/2tρ . This, in turn, implies that E(ρ) − dI tr 6 ǫ for tk = log |K| > n − t + 2 log(1/ǫ). QED. 10

5

Discussion

We have proposed two new definitions of security for quantum ciphers which are generalizations of entropic security and entropic indistinguishability. We have proven the equivalence of the two definitions up to slight variations of the parameters t and ǫ. We also presented the most efficient, in terms of the key size, quantum encryption scheme known yet. It is not hard to prove that the three schemes presented by Ambainis and Smith in [2] are all (t, ǫ)-indistinguishable. Furthermore, the first of these schemes, which uses δ-biased spaces, was also presented as a classical entropicallyscheme in [5]. Surprisingly, the quantum version of this scheme does not require longer key than its classical counterpart. So we ask (dare we conjecture ?): is entropic security a sufficient relaxation of information theoretic security so that quantum ciphers require no more key than their classical equivalent? If so, is this the simplest such relaxation possible?

References 1. Andris Ambainis, Michele Mosca, Alain Tapp, and Ronald de Wolf. Private quantum channels. In IEEE Symposium on Foundations of Computer Science, pages 547–553, 2000. 2. Andris Ambainis and Adam Smith. Small pseudo-random families of matrices: Derandomizing approximate quantum encryption. In Klaus Jansen, Sanjeev Khanna, Jos´e D. P. Rolim, and Dana Ron, editors, APPROX-RANDOM, volume 3122 of Lecture Notes in Computer Science, pages 249–260. Springer, 2004. 3. Ran Canetti. Towards realizing random oracles: Hash functions that hide all partial information. Lecture Notes in Computer Science, 1294:455–469, 1997. 4. Ran Canetti, Daniele Micciancio, and Omer Reingold. Perfectly one-way probabilistic hash functions (preliminary version). In Proc 30th ACM Sump. on Theory of Computing, pages 131–140, 1998. 5. Yevgeniy Dodis and Adam Smith. Entropic security and the encryption of high entropy messages. Cryptology ePrint Archive, Report 2004/219, 2004. urlhttp://eprint.iacr.org/. 6. Shafi Goldwasser and Silvio Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. In STOC ’82: Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 365–377, New York, NY, USA, 1982. ACM Press. 7. Patrick Hayden, Debbie Leung, Peter W. Shor, and Andreas Winter. Randomizing quantum states: Constructions and applications. Communications in Mathematical Physics, 250:371–391, Sep 2004. 8. M. A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, New York, NY, USA, 2000. 9. Alexander Russell and Hong Wang. How to fool an unbounded adversary with a short key. In EUROCRYPT ’02: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, pages 133–148, London, UK, 2002. Springer-Verlag.

11