Information-theoretical Secret-key agreement and Bound information

Information-theoretical Secret-key agreement and Bound information Master Thesis / Diplomarbeit by Martin Kreißig Institute of Photonic Sciences Quantum Optics group Advisor: Prof. Dr. Antonio Acin Universitat Politecnica de Catalunya Escola Tecnica Superior d’Enginyeria de Telecomunicacio de Barcelona Co-Advisor: Prof. Josep Sole Pareta Universität Stuttgart Institut für Kommunikationsnetze und Rechnersysteme Co-Advisor: Dipl.-Ing. Andreas Gutscher, Prof. Paul J. Kühn Abstract One big problem of the communication between two parties is the secrecy. That means how much information a third party can obtain by intercepting the messages transmitted from one honest party to the other one. Therefore cryptography offers a wide range of protocols to ensure security with assumptions on the eavesdropper. So one was looking for an information-theoretical description of the scenario to get unconditional secure communication. In this scenario we are considering two honest parties that want to communicate over an authenticated channel that the eavesdropper is wiretapping. This scenario introduced the definition of the intrinsic information and the secret-key rate which are a measure of the secrecy in this setting. Later because of strong analogies to quantum mechanics it turned out that this description was lacking a phenomena called bound information which is the disability of a probability distribution to create a secret-key even though it has predicted secrecy. Nearly ten years of research have shown the existence of bound information for the multipartite case where several parties are communicating but not yet for the bipartite case. Hence the approach of non-distillability seems a very promising one to find this conjecture. Motivated by this the approach we implemented this tool and simulated some distributions that have conjectured bound information. Thereby we improved the tool to reduce its calculation time and to get closer to the aim. iii Contents 1 Secret key agreement 1 1.1 Introduction to information theory . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation for secret-key agreement . . . . . . . . . . . . . . . . . . . . . 2 1.3 The scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Unconditional secret key agreement . . . . . . . . . . . . . . . . . . . . . 5 1.5 Protocol: Advantage distillation . . . . . . . . . . . . . . . . . . . . . . . 8 2 Bound information 13 2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Example of conjectured bound information . . . . . . . . . . . . . . . . . 14 2.3 Multipartite bound information and activation . . . . . . . . . . . . . . . . 18 3 A non-distillability criterion 23 3.1 General ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 The criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4 Implementation and optimization 29 4.1 Analysis and implementation of the tool . . . . . . . . . . . . . . . . . . . 29 4.1.1 Combination of both distributions . . . . . . . . . . . . . . . . . . 30 4.1.2 Constraint on secret-bit fraction of Qαβ ABK ............... 31 4.1.3 Additional constraint 1 . . . . . . . . . . . . . . . . . . . . . . . . 32 4.1.4 Additional constraint 2 . . . . . . . . . . . . . . . . . . . . . . . . 33 4.1.5 Remaining conditions and start of the optimization . . . . . . . . . 33 4.2 Implementation of the maps MAand NB................... 34 4.3 Examined distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5 Solutions and improvements . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5.1 Maps of 100% and 0% . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5.2 Decimal maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.5.3 Including the eavesdropper . . . . . . . . . . . . . . . . . . . . . . 38 4.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.6.1 Maps of 100% and 0% . . . . . . . . . . . . . . . . . . . . . . . . 39 i ii Contents 4.6.2 Decimal maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5 Conclusion and outlook 43 A Appendix: Conditional mutual information 45 B Appendix: Introduction to quantum mechanics 47 B.1 Postulates of quantum mechanics . . . . . . . . . . . . . . . . . . . . . . . 47 B.1.1 State space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 B.1.2 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 B.1.3 Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 B.1.4 Composite systems . . . . . . . . . . . . . . . . . . . . . . . . . . 49 B.2 Mixed states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 B.2.1 Density operator . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 B.2.2 Pure and mixed states . . . . . . . . . . . . . . . . . . . . . . . . . 50 B.3 Entanglement and separability . . . . . . . . . . . . . . . . . . . . . . . . 50 Bibliography 53 List of Figures 1.1 Graphical representation of the entropy, the conditional and the mutual information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Communication model used in this thesis . . . . . . . . . . . . . . . . . . 4 1.3 Model of the cascaded channels used in the broadcasting scenario . . . . . 9 2.1 Map on Eve’s side to reduce the secret key rate . . . . . . . . . . . . . . . 15 2.2 Overview over the ranges of separability/entanglement and distillability/nondistillability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Data flow diagram of the maps MAand NB................. 25 4.1 Code implementation of equation (4.1) . . . . . . . . . . . . . . . . . . . . 31 4.2 Code implementation of equation (4.2) . . . . . . . . . . . . . . . . . . . . 32 4.3 Code implementation of equation (4.3) . . . . . . . . . . . . . . . . . . . . 33 4.4 Code implementation of equation (4.4) . . . . . . . . . . . . . . . . . . . . 33 4.5 Code implementation of the bounds from probability theory . . . . . . . . 34 4.6 Start of the linear programming . . . . . . . . . . . . . . . . . . . . . . . . 34 4.7 Single pair optimization over D2for all 24·24possible combinations . . . . 38 4.8 Outputs of the optimization for distribution D1over the uncertain range including the maps of table 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.9 Optimization over the partial pairs of maps over the distribution D2. . . . . 42 B.1 Relation of separability, PPT and entanglement . . . . . . . . . . . . . . . 51 iii iv List of Tables 1.1 Arbitrary distribution PXYZ. Condition α+β+γ+δ+ε=1. . . . . . . . . 4 1.2 Distribution Sbetween Alice and Bob for a secret bit . . . . . . . . . . . . 5 1.3 Resulting distribution after receiving the broadcasted signal . . . . . . . . . 10 2.1 Distribution PXYZ coming from example 3 in [1] . . . . . . . . . . . . . . . 14 2.2 PXYZ1and PXYZ2after the map of Eve . . . . . . . . . . . . . . . . . . . . . 15 2.3 Generalized maps for the intrinsic information with 0 <i<6 . . . . . . . . 16 2.4 Distribution PXYZ obtained from a general map of PXYZ . . . . . . . . . . . 16 2.5 Distribution only depending on ai,biand ciunder the condition that Xand Y are independent (to be normalized) . . . . . . . . . . . . . . . . . . . . . . 16 2.6 Binarization of the distribution PXYZ from 2.1 . . . . . . . . . . . . . . . . 17 2.7 Maps of Alice and Bob to exclude Eve . . . . . . . . . . . . . . . . . . . . 18 2.8 Distribution for a tripartite scenario . . . . . . . . . . . . . . . . . . . . . 19 2.9 Distribution P2showing the part with positive conditional mutual information of P1................................... 20 2.10 Distribution P3after Eve’s map . . . . . . . . . . . . . . . . . . . . . . . . 20 2.11 Distribution P4obtained for those cases where B=C. . . . . . . . . . . . 20 3.1 Relation between distribution QABE′and new variable k(illustrative) . . . . 28 4.1 QABK arrangement for the use in the program . . . . . . . . . . . . . . . . 30 4.2 General view of a binarization map acting on one alphabet. . . . . . . . . . 34 4.3 Distribution D1to show bound information . . . . . . . . . . . . . . . . . 35 4.4 Distribution D2to show bound information . . . . . . . . . . . . . . . . . 35 4.5 Maps of alphabet HAto BAwith probabilities of 100% and 0% . . . . . . 37 4.6 Decimal maps for the binarization . . . . . . . . . . . . . . . . . . . . . . 39 4.7 Results of the optimization of distribution D2................ 40 v 61. SECRET KEY AGREEMENT That means that: (1.6) the correlation (mutual information) between Ncopies of Eve’s random variable, the communication Cand the key Sis arbitrary small, (1.7) the entropy of the secret key is arbitrary close to its maximum, namely an uniform distribution and (1.8) the rate is non-zero in the limit of large blocks. Based on this definition it is hard to find the secret-key rate for a given distribution. Hence it is very useful to establish more easily computable upper and lower bounds for this quantity. It seems quite reasonable that the rate at which Alice and Bob agree on a secret bit cannot be lower than their shared information degraded by the mutual information between Eve and one of them. In other words the secret-key rate must be larger than what Eve knows about one random variable of the honest parties. max {I(X,Y)−I(X,Z),I(Y,X)−I(Y,Z)} ≤ S(X,Y||Z) (1.9) This bound is reachable using LOPC protocols where all the communication goes in one direction, say from Alice to Bob [7] if max {I(X,Y)−I(X,Z),I(Y,X)−I(Y,Z)}=I(X,Y)− I(X,Z). Indeed, Alice and Bob can first use error correction to eliminate their errors and agree on a perfectly correlated list of symbols and then apply privacy amplification (see also [8]) to the new list to obtain an unconditionally secure key. Privacy amplification is a map of a K-bit string to Lbits, where K>L, by universal hash functions. It is known however that two-way communication protocols are more powerful than one-way, since it was shown in [5] - and we will prove it in chapter 1.5 - that it is even possible to create a positive secret-key rate in situations where I(X,Z)>I(X,Y) and I(Y,Z)>I(X,Y). Furthermore it seems quite intuitive that the secret-key rate cannot exceed the mutual information between Alice and Bob because that is the total amount of information they share. It cannot be larger either than the mutual information between the honest parties conditioned on the eavesdropper. Thus, one has: S(X,Y||Z)≤min {I(X,Y),I(X,Y|Z)}(1.10) But what happens if Eve performs any kind of local operation on her random variable? Then she is able to change the conditional mutual information and hence we get a tighter bound on the secret-key rate. This operation can be described through a channel characterized by the conditional probability PZ|Zwith Zbeing the input and Zbeing the output random variable. Definition 2 Given a distribution PXYZ the intrinsic (conditional mutual) information is defined as I(X,Y↓Z) :=inf PZ|Z       I(X,Y|Z) : PXYZ =X zǫZ PXYZ ·PZ|Z       (1.11) 1. SECRET KEY AGREEMENT 7 This leads to a stronger upper bound on the secret-key rate S(X,Y||Z)≤I(X,Y↓Z)≤I(X,Y|Z) (1.12) Another quantity to classify the correlations of Alice and Bob was introduced in [9] that is the rate at which Alice and Bob can generate a distribution by public communication that is at least as good as PXYZ. Definition 3 Let PXYZ be the joint distribution of three discrete random variables X, Y and Z. The information of formation of X and Y given Z, denoted by If orm(X,Y|Z), is the infimum of all numbers R ≥0with the property that for all ε > 0there exists N0such that for all N≥N0, there exists a protocol between Alice and Bob with communication C and achieving the following: Alice and Bob, both knowing the same random ⌊RN⌋-bit string S , can finally compute X′and Y′, respectively, sucht that there exist random variables XN, YNand ZNjointly distributed according to (PXYZ)N(this is the distribution corresponding to n-fold independent repetition of the random experiment PXYZ) and a channel PC|ZNsucht that Prob h(X′,Y′,C)=(XN,YN,C)i≥1−ε(1.13) holds. This shows that the synthesis of our distribution is somehow only depending on PN XY because the communication Ccan be simulated by an Eve knowing the corresponding ZN. From this we can also formalize the fact, that Eve does not gain any information by observing C. It was also proven that the information of formation is lower bounded from the intrinsic informtion. This means that the intrinsic information bounds the minimum number of secret bits required to create the desired distribution. Hence we have for every distribution PXYZ S(X,Y||Z)≤I(X,Y↓Z)≤If orm(X,Y|Z) (1.14) We want to remark here that a distribution can be established by LOPC if and only if If orm(X,Y|Z)=0 [10]. If If orm(X,Y|Z)>0, the distribution requires the use of secret correlations for its generation. Before concluding this section, we would like to discuss other possible bounds on the secretkey rate. One may for instance consider how the secret-key rate is affected when Eve gets some additional side information Ufrom an oracle. This can be formulated as Z′=[Z,U] and would only affect equation (1.6) in the way that I(S,CZ′N)≤ǫ. But this formulation is already included in I(S,CZN)≤ǫand hence we can follow: S(X,Y||[Z,U]) ≤S(X,Y||Z) (1.15) 81. SECRET KEY AGREEMENT Another interesting question is what happens if Alice or Bob perform local maps PX|Xand PY|Y. This can be described as the following: Let X,Y,Z,Xand Ybe random variables jointly distributed like PXYZXY =PXYZ ·PX|X·PY|Y. Then we can state due to the fact that the secret-key rate is the maximum rate taken over all possible protocols between Alice and Bob that S(X,Y||Z)≥S(X,Y||Z) (1.16) This shows us that Alice and Bob cannot increase their secrecy by applying any kind of local operation which leads us to another interesting quantity the binarization of the alphabet of the honest parties which is the reduction of one’s alphabet Xor Y, respectively, to a binary one BAor BB. It is shown in [6] and [1] that the restriction of the ranges: X→˜ Xwith ˜ X≤Xand Y→˜ Ywith ˜ Y≤Ydoes not increase the secret-key rate. Lemma 4 Let X, Y and Z be random variables with ranges X,Yand Zand joint distribution PXYZ. For ˜ X⊂Xand ˜ Y⊂Y, we define a new random experiment with random variables ˜ X and ˜ Y (with ranges ˜ Xand ˜ Y, respectively). If Ωis the event that X ∈˜ Xand Y∈˜ Y, then the joint distribution of ˜ X and ˜ Y with Z is defined as follows: P˜ X˜ YZ(x,y,z) :=PXYZ(x,y,z) PXYZ[Ω](1.17) for all (x,y,z)∈˜ Xט Y×Z. Then S(X,Y||Z)≥PXYZ[Ω]·S(˜ X,˜ Y||Z) (1.18) This follows from the definition of the secret-key rate which is already the maximal rate for key generation. In the next section, we introduce the most commonly used key distillation protocol and then discuss how it can be used for secret key distillation in a relevant scenario. 1.5 Protocol: Advantage distillation Advantage distillation is an LOPC protocol for key agreement that uses two-way communication. It may allow distilling a key even in situations when standard one-way communication techniques fail [5,6]. Although initially presented in the binary case, the protocol works for variables of arbitrary size. It works as follows: Alice locally generates a random variable Cof the same size das X. Then, she take Nrealizations of Xand computes the Nvalues Mi satisfying C=Mi+Xi, 1. SECRET KEY AGREEMENT 9 where the sum is modulo d. The Nvariables Miare then transmitted to Bob over the public channel. Bob receives the bit-string Miand performs the same sum with his corresponding set of variables Yi: Yi+Mi. Bob will accept the codeword only if all these sums give the same result, D, which he keeps as his new symbol. We will now give an example showing how this protocol can distill a key from a probability distribution where Eve’s information on Alice and Bob’s variables is larger than the correlations between the honest parties. We will see how it enables mapping the initial probability distribution into a new probability distribution where equation (1.9) is positive. Thus, the honest parties can apply error correction and privacy amplification to the new distribution, obtained after advantage distillation, and obtain an unconditional secure key. Consider the situation in which the joint distribution is coming from a broadcasted signal with random variable Rand PR(0) =PR(1) =1/2 as shown in the figure 1.3. This signal arrives at Alice, Bob and Eve with different error probabilities PX|R(1,0) =PX|R(0,1) =ǫA/2, PY|R(1,0) =PY|R(0,1) =ǫB/2 and PZ|R(1,0) =PZ|R(0,1) =ǫE/2 Moreover δA=1−ǫA, δB=1−ǫBand δE=1−ǫEbeing the probabilities of a correct transmission. Without loss of generality we can assume that ǫA=ǫB=ǫand hence δA=δB=δ, i.e. Alice’s and Bob’s channels are identical2. Hence all three parties have a different knowledge about the transmitted bits and this is reflected by the probability distribution 1.3. In this scenario, one can see that no one-way communication protocol enables secret-key distillation if Eve’s error is smaller than Alice and Bob’s. Figure 1.3: Model of the cascaded channels used in the broadcasting scenario Let’s analyze how the initial distribution changes after application of the advantage distil2If e.g. ǫA< ǫBwe can cascade another channel with error probability (ǫB−ǫA)/(1 −2ǫA) to obtain ǫA=ǫB 10 1. SECRET KEY AGREEMENT lation protocol previously described. After this protocol, the probability that Bob accepts a message correctly is given by the fidelity F FN=(δ2+ǫ2)N(1.19) and in the case of a false accepted message we obtain the disturbance D DN=1−(ǫ2+δ2)N(1.20) Moreover we can say that Bob accepts a message in general with the probability paccept =FN+DN(1.21) and thus we can derive Bob’s overall error probability, getting: βN=DN FN+DN(1.22) We are now interested in the conditional probability γNthat Eve decides the wrong message X Y (Z) 0 1 0(0) δF·F 2 (1) (1 −δF)·F 2 (0) δD·D 2 (1) (1 −δD)·D 2 1(0) (1 −δD)·D 2 (1) δD·D 2 (0) (1 −δF)·F 2 (1) δF·F 2 Table 1.3: Resulting distribution after receiving the broadcasted signal under the condition that Bob accepts the correct one. Therefore we introduce the probability δF=P(Z=X|X=Y) that Eve makes a right decision given that Bob accepts the correct one. δF=δ2δE+ǫ2ǫE(1.23) Thus we can derive the probability when Eve decides a wrong bit given that Bob accepts the correct one P(Z,X|X=Y) as 1−δF=δ2ǫE+ǫ2δE(1.24) The other case can be described as, given that Bob accepts a wrong bit Eve can either decide for the correct one (δD=P(Z=X|X,Y)=δǫǫE+ǫδδE) or the false one (1 −δD=δǫδE+ǫδǫE). This leads us directly to table 1.3 which illustrates the probabilities of a correct decision on Bob’s side (fidelity and disturbance) as well as the conditional probabilities of Eve based on the outcome of Bob for each bit broadcasted. 1. SECRET KEY AGREEMENT 11 We can now conclude Eve’s error probability for the whole message as the following: γN=1 2·1 paccept · N X i=N/2 N i!δi F(1 −δF)N−i+δi D(1 −δD)N−i(1.25) ≥1 2·1 paccept · N N/2!δN/2 F(1 −δF)N/2+δN/2 D(1 −δD)N/2(1.26) As one can easily see δN/2 D(1 −δD)N/2=(δǫ)Nwhich is a very small value that we can also neglect. Moreover when using the Stirling formula (see [6]): N N/2≥1 √2πN·2N, we can rewrite (1.26) as: γN≥1 2√2πN·1 paccept ·2pδF(1 −δF)N(1.27) For ǫ < 1/2 and with equalities (1.23) and (1.24) we can show that: pδF(1 −δF)=p(1 −2ǫ+ǫ2−ǫE+2ǫǫE)(ǫ2−2ǫǫE+ǫE) ≥ǫ(1 −ǫ) (1.28) which is equal for ǫE=0 and maximal for 1/2. From equation (1.20) we can conclude D=2·(ǫ−ǫ2). This leads us to the result: γN>1 2√2πN·1 paccept ·DN(1.29) =1 2√2πN·βN(1.30) This shows that Bob’s error decreases exponentially with the number of copies compared to Eve’s. We proof later that secret key agreement is only possible if D 1−D <2pδF(1 −δF) (1.31) Now we have to show that with βN< γNthe secret-key rate is positive. Therefore consider the scenario that we want to construct the random variables ˜ Xand ˜ Yfrom our XNand YN random variables exchanged over the authenticated channel. Then it suffices to show that I(˜ X,˜ Y)−I(˜ X,˜ Z)=H(˜ X|˜ Z)−H(˜ X|˜ Y)>0 (1.32) where ˜ Z=[ZN,V] with Vbeing the collection of all messages over the public channel. Then we define ˜ Xand ˜ Yas follows: If Bob accepts ˜ X=Cand ˜ Y=C′and if he rejects publicly 12 1. SECRET KEY AGREEMENT ˜ X=˜ Y=”re ject”. Given that Bob accepts Alice’s bit and given that βN=bNwe can state that: H(C|C′)=h(βN)≤2bN·log(1/bN)=2bN·N·log(1/b)< γN(1.33) for sufficiently large Nand h(p)=−plog p−(1 −p) log(1 −p) being the binary entropy. The first inequality in (1.33) is derived from −plog p≥ −(1 −p) log(1 −p) for p≤1/2 and the second one from the Jensen’s inequality . Eve’s side can be described as H(C|˜ Z)=X ˜z P˜ Z(˜z)H(C|˜ Z=˜z)=E[h(q(˜ Z))] ≥E[q(˜ Z)] =γN(1.34) where q(˜z) denotes the probability of Eve guessing Cincorrectly with her optimal strategy, i.e. q(˜z)≤1/2 and h(q(˜z)) >q(˜z). For Bob’s public rejection we have H(˜ X|˜ Y)=H(˜ X|˜ Z)=H(˜ X|V)=0 (1.35) Concluding this we get I(˜ X,˜ Y)−I(˜ X,˜ Z)>0 which proofs the information-theoretical security of this protocol. Now we proof that condition (1.31) leads to secret key agreement by showing that the contrary condition that means D 1−D ≥2pδF(1 −δF) (1.36) leads to non-distillability. Therefore we consider our distribution of table 1.3 where Alice and Bob are independent and hence I(X,Y|Z)=0 which is a sufficient condition for nondistillability if PXYZ(0,0|z)·PXYZ(1,1|z)=PXYZ(0,1|z)·PXYZ(1,0|z) (1.37) For z=0 (and z=1 respectively) we obtain from the previous condition that δF(1 −δF)·F2 4=δD(1 −δD)·D2 4 By the definition of δDwe see that δD=1−δDand this concludes the equality of (1.36). It remains to show the inequality of (1.36). Herefore we assume that Eve performs the maps P˜ Z|Z(0,0) =p,P˜ Z|Z(1,0) =1−p,P˜ Z|Z(1,1) =qand P˜ Z|Z(0,1) =1−q. It is easy to check that this leads to the conditions D 1−D =qδ2 F+(1 −δF)2which is included in condition 1.36 and this concludes the proof. The protocol explained here does not claim to be the most efficient one. It shall only illustrate the mechanisms. 2 Bound information 2.1 Motivation Given a probability distribution, it is not easy to check whether it is distillable since the computation of the secret-key rate requires a maximization over all possible LOPC protocols. Clearly, the positivity of the intrinsic information is a necessary condition for a probability distribution to be distillable (see equation (1.12)). However, it is an open problem whether this condition turns out to be sufficient. If this was the case, all probability distributions that could not be created by LOPC would be distillable. On the other hand, the existence of non-distillable probability distributions with positive intrinsic information would imply the existence of an irreversible form of secret correlations, as (i) some sort of secrecy is needed for the preparation of the distribution but (ii) this secrecy cannot be distilled into a secret key. This irreversible form of secret correlations is known as bound information. A similar phenomenon was observed in quantum physics, concerning the problem of distilling pure-state entanglement from an entangled quantum state. There, it was shown that the distillation of an entangled quantum state into a maximally entangled state is not always possible. This irreversible form of entanglement is known as bound entanglement1. The strong analogies between entanglement distillation and secret-key agreement motivated the conjecture that there may also exist probability distributions containing secret correlations, in the sense that its formation by LOPC is impossible, that cannot be used for secret key agreement. These distributions would be the classical cryptographic analog of bound entangled states. The relation between bound entanglement and bound information has been discussed in previous articles and is beyond the scope of this thesis. We refer to references [1] and [11] for details. Before proceeding, let us precisely define bound information. Definition 5 A distribution contains bound information when (i) its formation by LOPC is impossible and (ii) no secret key can be distilled out of it by LOPC. 1Entanglement is the term usually employed to name quantum correlations. We would like to refer to appendix B for an introduction to quantum physics 13 14 2. BOUND INFORMATION This definition is general and applies to scenarios with more than two honest parties, as it will be discussed below. However, in this thesis we mainly consider the standard case of two honest parties plus the eavesdropper. Then, the existence of bound information is equivalent to finding a probability distribution such that: S(X,Y||Z)=0If orm(X,Y|Z)>0 (2.1) The first condition means that the distribution is useless for key distribution, while the second one implies that the formation of the distribution by LOPC is impossible. This last condition can also be replaced by I(X,Y↓Z)>0, since I(X,Y↓Z)>0 if and only if If orm(X,Y|Z)>0. 2.2 Example of conjectured bound information We give in what follows an example of a probability distribution which is conjectured to have bound information. The distribution was presented in [1] and was constructed from a bound entangled quantum state. The distribution reads (to be normalized): X Y (Z) 123 1 (0) 2 (4) 5-α(3) α 2 (1) α(0) 2 (5) 5-α 3 (6) 5-α(2) α(0) 2 Table 2.1: Distribution PXYZ coming from example 3 in [1] In the following we will show that distribution PXYZ is distillable, non-distillable and has conjectured bound information for different ranges of α[1]. Initially we calculate the conditional mutual information of this distribution, having I(X,Y|Z)=PZ(0) ·I(X,Y|Z=0) + 6 X z=1 PZ(z)·I(X,Y|Z=z) =Px,yPXYZ(x,y,0) Px,y,zPXYZ(x,y,z)· 3 X i=1 PXYZ(i,i,0) Px,yPXYZ(x,y,0) log Pxy PXYZ(x,y,0) PXYZ(i,i,0) +0 =6 Px,y,zPXYZ(x,y,z)log 3 (2.2) >0 (2.3) Our first goal is to see when the distribution has positive intrinsic information. Therefore we 2. BOUND INFORMATION 15 Figure 2.1: Map on Eve’s side to reduce the secret key rate consider the maps by Eve of figure 2.1: she maps all values of her alphabet except zero onto themselves with probability por p′, depending on their probability of occurrence, given in PXYZ, and onto zero with probability (1 −p) and (1 −p′). The conditions in figure 2.1 result from the fact that all PXYZ(x,y,z=0) =2 in table 2.1. Thus we end in a distribution that we can split in PXYZ1and PXYZ2like shown in table 2.2: PXYZ = X Y (Z)1 2 3 1 (0) 2 (0) 2 (0) 2 2 (0) 2 (0) 2 (0) 2 3 (0) 2 (0) 2 (0) 2 + X Y (Z)1 2 3 1 (0) 0 (4) q′(3) q 2 (1) q(0) 0 (5) q′ 3 (6) q′(2) q(0) 0 Table 2.2: PXYZ1and PXYZ2after the map of Eve One can see that the intrinsic information of these two distributions PXYZ1and PXYZ2, and thus also for our distribution PXYZ, is zero. So we can state: S(X,Y||Z)≤I(X,Y↓Z)=I(X,Y|Z)=0 (2.4) This is however only possible for 2 ≤α≤3 because only then all values PXYZ(x,y,z)≥2 and hence can be mapped to PXYZ(x,y,z=0) =2. What happens for 0 < α < 2? In this case, we consider a generic map by Eve Z→Z, as shown in 2.3. Here she maps every value of her alphabet onto arbitrary symbols labeled by i. Applying these maps leads us to the distribution PXYZ of table 2.4 which shows us the slice of one specific i. 22 3 A non-distillability criterion The examples that have conjectured (chapter 2.2) and provable multipartite bound information (chapter 2.3) have been derived from quantum states having a very similar characterization. However, the existence of bipartite bound information still remains open. As mentioned, the main difficulty comes from the fact that one has to prove that no LOPC protocol can distill a key from a given probability distribution. In the quantum case, this was possible because there exists an easily computable criterion for non-distillability, namely the positivity of partial transposition (see appendix B.3). However, in the classical cryptographic case, we lack such a simple criterion. The first step in this direction was provided in [13]. There, a possible criterion for detecting the non-distillability of a given probability distribution was proposed. Potentially, it could detect the presence of bound information. Therefore, the purpose of this work is to apply the criterion to some examples of probability distribution with conjectured bound information and see how it performs. The main hope was to prove bound information, but, unfortunately, this has not been the case. Actually, as we discussed later, it is also possible that the criterion is useless for detecting bound information. In this chapter, we first present the concept of secret-bit fraction in Section 3.1, which plays a key role in all what follows, and then discuss in Section 3.2 the non-distillability criterion proposed in [13]. Later, we will apply the criterion to some candidates of probability distributions having conjectured bipartite bound information. 3.1 General ideas As mentioned, to derive the criterion we first need to introduce the concept of secret-bit fraction. Definition 6 Given a distribution PABE.The secret bit fraction is given by: λ[PABE]=2Pemin{PABE(0,0,e),PABE(1,1,e)} Pa,b,ePABE(a,b,e)(3.1) 23 24 3. A NON-DISTILLABILITY CRITERION and the maximal extractable secret bit fraction is calculated by: Λ[PABE]=sup MA,NB λ[MANBPABE] (3.2) over all linear maps MAand NBacting on the spaces HAand HBrespectively in the way: MA:HA→BAand NB:HB→BBwhere Bdenotes the binary output space of each alphabet. The secret bit fraction represents the minimal part of a distribution where Aand Bshare the same binary output value. The denominator in equation (3.1) ensures the normalization of the distribution. The range of the maximal extractable secret bit fraction is given by Λ∈[1 2,1] where 1/2 is related to the case of uniformly distributed parties Aand B, means PABE(a,b,e)= 1 4∀(a,b)∈ {0,1}. This is related to the worst case because it means that the honest parties are independent and hence share no (secret) correlations. The best scenario is given by PABE(0,0,e)=PABE(1,1,e)=1/2. Then the secret bit fraction will give the value one. It was also shown in [14] that a secret bit fraction bigger than 1/2 is always related to a positive secret key rate or, in other words, any candidate for bound information should have maximum secret bit fraction equal to 1/2. Another property that this criterion makes use of is that every linear map M:H1⊗H2→H3 with positive coefficients can be split like: M=UM′(3.3) with -M′:H1→H3⊗H2 -U: (H3⊗H2)⊗H2→H3where Uy3 x3x2y2=δy3 x3δx2y2 Where upper indices are outputs and lower indices are inputs and the number indicates the corresponding space. What Udoes is to compare the inputs x2and y2from H2and only if they are the same it passes the input x3belonging to H3and passes it to the output y3, while M′makes a map from x1to x3and x2, which are both used in U. Figure 3.1 shows our usage of this property: We take two distributions with the spaces HA and HB, respectively, and HEand HKwhich are of no importance in this consideration. Now we apply each map as described in equation (3.3) on either space HAor space HB. We can do the following assignments: H1≡HA(B)⊗BA(B),H2≡HA(B)and H3≡BA(B) Summarizing this: we have two input distributions GABE and QABK where we apply the maps MAand NBon each alphabet. These maps are each split in the operations defined by the map Uthat compares the two input alphabets and passes the binary aphabet and map M′ which performs an arithmetic operation to calculate the binary output. 3. A NON-DISTILLABILITY CRITERION 25 Figure 3.1: Data flow diagram of the maps MAand NB 3.2 The criterion Having introduced the previous concept, we are in position of presenting the criterion for non-distillability. The idea is to consider two distributions - the one, denoted by GABE, for which the presence of bound information has been conjectured and an arbitrary second probability distribution, QABE′. Then we study the secret bit fraction of QABE′alone and in combination with the conjectured bound information distribution. One can then show that if GABE does not improve the secrecy of any arbitrary distribution, then it cannot be used for secretkey agreement, S(X,Y||Z)=0, and, thus, has bound information. An important aspect of the criterion is that these conditions can be mapped into a linear programming problem, which makes its numerical optimization feasible. Let us now introduce the criterion. As stated in the previous chapter we know that a distribution is distillable if its maximal extractable secret bit fraction is bigger than 1/2. From that we can derive the following two conditions: Λ[QABE′]≤λ0(3.4) λ[UAUBQABE′⊗GABE]> λ0(3.5) That is, if a distribution GABE is distillable, there exists another distribution QABE′, with secret-bit fraction smaller than λ0(3.4), such that its secret bit fraction is increased when combined with GABE, see equation (3.5). Then, the distribution GABE is said to activate the distribution QABE′. 26 3. A NON-DISTILLABILITY CRITERION To proof this we have to know that the distribution GABE is (secret-key) distillable if there exists n, such that Λ[G⊗n ABE]> λ0for each λ0∈[1/2,1). If we consider the maps MAand NB according to equation (3.3) we can define QABE′=M′AN′BG⊗(n−1) ABE . Because Λis defined by an optimization (see (3.2)) the following inequality holds: ΛhG⊗(n−1) ABE i≥ΛhM′AN′BG⊗(n−1) ABE i= Λ [QABE′] (3.6) By the definition of nwe know that ΛhG⊗(n−1) ABE i≤λ0which concludes inequality (3.4). The properties of the maps show that UAUBQABE′⊗GABE =MANBG⊗n ABE (3.7) and we know that λhMANBG⊗n ABEi> λ0which concludes inequality (3.5). This implies not only that the distribution GABE activates the distribution QABE′, but moreover it activates itself. Now, the aim of the criterion is to show that no such a distribution can exist, which can be seen as an optimization problem. The problem is that Eve’s alphabet E′is unbounded which would lead to an endless search. However, as shown in [13], it is possible to (i) bound Eve’s alphabet to a finite alphabet and (ii) map the optimization problem into a linear programming instance. These two properties make the optimization problem tractable using standard numerical techniques. Moreover in the following we only consider the case λ0=1/2 that belongs to minimal distillability. At the same time we have to check all possible pairs of maps (Mi A,Ni B) : i=1,···,Mthat may improve the maximal extractable secret-bit fraction of QABE′above λ0which would violate equation (3.4). For the linearization of equation (3.4) and (3.5) we rewrite them as 4X e′ min a∈{0,1}nhMi ANi BQABE′i(a,a,e′)o−X a,b,e′hMi ANi BQABE′i(a,b,e′)≤0 (3.8) 4X e′,e min a∈{0,1}nhUAUBQABE′⊗GABEi(a,a,e′,e)o− X a,b,e′,ehUAUBQABE′⊗GABEi(a,b,e′,e)>0 (3.9) 3. A NON-DISTILLABILITY CRITERION 27 Let us now define the dimension of Eve in GABE as d(e=1, ...d) and introduce the new functions: si(e′)=(0 if Pa(−1)a[Mi ANi BQABE′](a,a,e′)<0 1 if Pa(−1)a[Mi ANi BQABE′](a,a,e′)>0(3.10) re(e′)=(0 if Pa(−1)a[UAUBQABE′⊗GABE](a,a,e′,e)<0 1 if Pa(−1)a[UAUBQABE′⊗GABE](a,a,e′,e)>0(3.11) For clarification one may have a closer look at the specific example re(e′)=0. Then [UAUBQABE′⊗GABE](0,0,e′,e)<[UAUBQABE′⊗GABE](1,1,e′,e) which is equal to say that the distribution has the smaller value with a=0. This is directly related to re(e′)=0 as stated above. Therewith we can replace the min function by substituting awith si(e′) in equation (3.8) and with re(e′) in equation (3.9). This gives us 4X e′hMi ANi BQABE′i(si(e′),si(e′),e′)−X a,b,e′hMi ANi BQABE′i(a,b,e′)≤0 (3.12) and 4X e′,ehUAUBQABE′⊗GABEi(re(e′),re(e′),e′,e)− X a,b,e′,ehUAUBQABE′⊗GABEi(a,b,e′,e)>0 (3.13) respectively. Additionally we define the vector k(e′) like the following: k(e′)=[r0(e′),r1(e′), ..., rd(e′),s1(e′), ..., sM(e′)] (3.14) and rewrite the distribution QABE′like in table 3.1. Here one can see that several of the possible infinite outcomes of E′end up in the same vector kjof the alphabet j=1, .., kwith the dimension k=2d+M. If we now merge all coefficients with the same kj, like shown in equation (3.15) we will get our new finite i.e. bounded distribution QABK. QABK(a,b,kj)=X e′:k(e′)=kj QABE′(a,b,e′) (3.15) Finally we have to adjust our summations in equations (3.12) and (3.13) from e′to the new variable kand conclude the equations for the algorithm: X k 4·hMi ANi BQABKi(kd+i,kd+i,k)−X a,bhMi ANi BQABKi(a,b,k)!≤0 (3.16) X k,e 4·hUAUBQABK ⊗GABEi(ke,ke,k,e)− X a,bhUAUBQABK ⊗GABEi(a,b,k,e)!>0 (3.17) 28 3. A NON-DISTILLABILITY CRITERION QABE′r0(e′)r1(e′)··· rd(e′)s1(e′)··· sM(e′)kj qab00 0 ··· 0 0 ··· 0 qab10 1 ··· 0 1 ··· 0→k0 . . .. . ..... . .. . . qabm 0 0 ··· 1 0 ··· 0 qabn 0 1 ··· 0 1 ··· 0→k0 qabo 1 0 ··· 1 0 ··· 0 . . .. . ..... . . Table 3.1: Relation between distribution QABE′and new variable k(illustrative) For this transformation we still have to take into account the constraints coming from equations (3.10) and (3.11). Adjusted to our new notation we get: X a (−1)a[Mi ANi BQABK](kd+i⊕a,kd+i⊕a,k)<0 (3.18) X a (−1)a[UAUBQABK ⊗GABE](ke⊕a,ke⊕a,k,e)<0 (3.19) Let me refer to chapter 4.1 for another analysis of this set of equations. The aim as mentioned above is to find the distribution QABK by a linear programming such that we maximize equation (3.17) and also fulfill equations (3.16), (3.18) and (3.19). Furthermore we have the constraints from probability theory that QABK >0 and Pabk QABK =1. If our maximization returns zero we can conclude that the distribution GABE does not activate any arbitrary distribution (including itself!) and hence its secret key rate is equal to zero. Now, if one is able to show that GABE has also positive intrinsic information, the existence of bound information can be established. Remark If the maximization returns a positive value we cannot state anything because there might always be the case that the specific pairs of maps (Mi A,Ni B) that have to be choosen in advance and show undistillability, were missing in the optimization. 4 Implementation and optimization The implementation of the criterion explained in the previous chapter was done in MATLABc  aiming for the use of its internal linprog algorithm. This function is a linear programming algorithm that is defined by the formulation max qf(q) : Aineq ·q≤bineq Aeq ·q=beq lb ≤q≤ub where capital letters represent a matrix and small letters a vector. Moreover lb and ub define bounds on the coefficients of vector q. 4.1 Analysis and implementation of the tool The goal as already mentioned is to find the maximum over the distribution QABK which needs to be fit to the vector q. But first we consider the implementation of this distribution and how we programmed the maps. The distribution must be of three dimensions where the alphabets HAand HBmust be twice the size of the given distribution GABE due to the binarization done by the maps MA and NB. The approach was to write Alice and Bob’s alphabet on the yand x-axis, respectively, according to the graphical representation of the distributions given in this thesis. Eve is represented by the z-axis. That produces a three dimensional matrix where each slice for Z=zshows a distribution over Alice’s and Bob’s alphabet. We want to emphasize at this point that all coefficients are real and we do not have to care about complex numbers. So we can create a two dimensional matrix for each value of Eve in the way shown in table 4.1 where dA=dim(HA) and dB=dim(HB) are the corresponding dimensions and αand β the binary outputs of the maps. One can think of QABK(a,b,k)≡Qαβ ABK(α, β, a,b,k) to emphasize the binary output values. Hence we rewrite equations (3.17), (3.16), (3.18) and (3.19) following this new notation. 29 30 4. IMPLEMENTATION AND OPTIMIZATION β∈ {0,1}0 1 b∈HB0··· db0··· db α∈ {0,1}a∈HA 0 0 . . . da QABK 1 0 . . . da Table 4.1: QABK arrangement for the use in the program 4.1.1 Combination of both distributions max QABK X k,e 4·X a,bhUAUBQαβ ABK ⊗GABEi(ke,ke,a,b,k,e) −X α,β,a,bhUAUBQαβ ABK ⊗GABEi(α, β, a,b,k,e)!=0 (4.1) Equation (4.1) takes each specific plane ein GABE and plane kin Qαβ ABK and makes a product between all values aand b. Therefore we take the corresponding quarter of Qαβ ABK characterized by αand β(see table 4.1) and multiply it with GABE. Finally we make the sum over the aand bvalues to get the probability. The corresponding quarter of Qαβ ABK for the first summand is depending on the value kethat is deduced from the e-th coefficient in k. The second summand takes consecutively all parts, i.e. for (α, β)=(0,0) then (0,1), (1,0) and (1,1). Thus we can say that every quarter section in Qαβ ABK will be substracted by its corresponding values in GABE. Moreover due to the tensor product we have to substract the sum over all efor each corresponding (a,b)-pair as given in figure 4.1 line 24-27. How do we include the first summand? We know that we only have to care about the parts (α, β)=(0,0) or (1,1) which depend on ke. So we have to find for each kand ewhether ke=0 or 1, then remember those indices (figure 4.1, line 15-18) and add the corresponding range (figure 4.1, line 24 and 27). Finally we reshape the matrix to the vector to introduce it in the linear programming which is going to find the maximal values for the distribution Qαβ ABK. 4. IMPLEMENTATION AND OPTIMIZATION 31 Figure 4.1: Code implementation of equation (4.1) 4.1.2 Constraint on secret-bit fraction of Qαβ ABK X k 4·X a,bhMi ANi BQαβ ABKi(kd+i,kd+i,a,b,k) −X α,β,a,bhMi ANi BQαβ ABKi(α, β, a,b,k)!<0 (4.2) Equation (4.2) is the first constraint on our optimized distribution. Here we have nearly an equivalent formalism to equation (4.1) except for the tensor product with GABE. The first summand depends in this case on the (d+i)-th coefficient in kthat is related to the i-th pair of maps MAand NB. We will discuss the implementation of the maps in chapter 4.5. So far let us assume that they are predefined matrices of the size 2 ·dA×2·dBand stored in a structure data type with corresponding matrices to each binary output combination denoted by mapped2_00, mapped2_01, etc. A linear map is characterized by a product of the mapping coefficient with the value. Hence we have to arrange the maps according to the part (α, β)=(0,0) or (1,1) which is checked 38 4. IMPLEMENTATION AND OPTIMIZATION 0 50 100 150 200 250 300 0.1 0.12 0.14 0.16 0.18 0.2 0.22 0.24 0.26 single pair optimization over D2, all 24*24 possibilities Combinations of pairs of maps on the alphabet HA and HB Output of the linprog: fval Figure 4.7: Single pair optimization over D2for all 24·24possible combinations that follow the condition: Pα|a(i,0) =Pα|a(i,1) for i={0,1} and the same for alphabet HB. This gives us a set of m=22+11 ·10 =114 maps to α=0. Developing this strategy we have the same amount of maps to α=1 and the whole number of maps for the alphabet HB, too. That makes a total amount of possible pairs of maps: M=m4=168,896,016 - to be checked individually. This represents a reduction to M′of 21%. The conclusions and results of this version of the tool are presented in chapter 4.6.2. 4.5.3 Including the eavesdropper Another idea for an improvement has been to include Eve’s maps in the secret-bit fraction formula, but it has been shown in [14] that this has no influence on the secret-bit fraction: Let Γ˜ E|Ebe an arbitrary operation Eve may perform on the distribution. Then λ[Γ˜ E|EPABE]=2X e′ min X e Γ˜ E|E(e′,e)PABE(0,0,e),X e Γ˜ E|E(e′,e)PABE(1,1,e) ≥2X e′,e Γ˜ E|E(e′,e) min [PABE(0,0,e),PABE(1,1,e)] =2X e min [PABE(0,0,e),PABE(1,1,e)] =λ[PABE] 4. IMPLEMENTATION AND OPTIMIZATION 39 α: 0 1 a: 0 1 0 1 1. 0 0 0 0 2. 0 0 0 0.1 3. 0 0 0 0.2 . . .··· . . . 9. 0 0 0 1 10. 0 0 0.1 0 11. 0 0 0.1 0.1 . . .··· . . . (114−1). 1 1 1 0.9 114. 1 1 1 1 Table 4.6: Decimal maps for the binarization The inequality comes from the min function and is independent on Eves’ actions. 4.6 Results 4.6.1 Maps of 100% and 0% Following the description in chapter 4.5.1 we implemented the program and could obtain the results described in this section. For the distribution D1shown in table 4.3 we checked the range: δ={0.01,0.02,··· ,0.10} and for the distribution D2from table 4.4 we took: β={0.1,0.2,0.3}. The results for D1are presented in figure 4.8 that shows the solutions of the linear programming f val and additionally the conditional mutual information of distribution D1for each δ. We can see that there is no exceptional behaviour in the curve, neither for the distillable region δ∈[0.093,1], represented by δ=0.1, nor for the uncertain range δ∈[0,0.093). Our goal of reaching f val =0 and hence showing S(X,Y||Z)=0 could not be reached with this family of maps. The results for D2were similar i.e. they did not return zero from the maximization. The specific values can be taken from table 4.7 (range of conjectured bound information: β= [0.17,0.33]). 40 4. IMPLEMENTATION AND OPTIMIZATION Figure 4.8: Outputs of the optimization for distribution D1over the uncertain range including the maps of table 4.5 β0.1 0.2 0.3 f val 0.012 0.025 0.037 Table 4.7: Results of the optimization of distribution D2 4.6.2 Decimal maps After adapting the program to the specifications of chapter 4.5.2 we were able to measure the following time consumptions with the given server details: - Servers capacities: . Quadcore processors with 2.2 - 2.8 GHz . Main memory per node 8 - 24 GB . Architecture: 64 bit - After 17 hours the server passed 0.2% of all pairs of maps. - That makes a total calculation time of 17h/0.002 =8500h≈350d. - This measurement was based on a loop with a backup in each pass. By the profiler function in MATLABc we could detected that each backup takes 0.11ms, which has no big influence at all on the complete optimization: t=0.11ms∗1144/3600/24 =0.21d. 4. IMPLEMENTATION AND OPTIMIZATION 41 Concluding one can see that we were limited with the number of possible pairs that we could check. So we decided to examine only a suitable part in the remaining time and with the given capabilities. Partial results Even though we were not able to simulate a closed bigger range of pairs of maps we concentrated on simpler combinations between them. Therefore we concluded to use pairs where two maps are always equivalent: (1) same maps inside each alphabet: a→α=0≡a→α=1 and b→β=0≡b→β=1 (2) same maps to the same output value: a→α=0≡b→β=0 and a→α=1≡b→β=1 Therefore we were able to reduce the amount of pairs of maps to 1142=12996. The results were quite similar for both distributions thus we consider only the results for distribution D2. In figure 4.9 we plot the outcomes of the optimization for each pair of maps based on distribution D2and following the restriction of (2). One can see that there exists a periodicity in the combination of maps that is due to the loops that start every pass with very low mapping coefficients. From both cases (1) and (2) we obtained the same optimized value for the distribution D2: f val (β=0.2)=0.005 which is an improvement of 80% but still not enough to show our conjectured quantity. This value has been obtained with the maps: α: 0 1 a: 0 1 0 1 0.3 0.7 0.3 0.7 β: 0 1 b: 0 1 0 1 0.3 0.7 0.3 0.7 A more specific simulation around the best mapping vector combination mentioned above, with a probability step size of 0.01 did not improve the result. 42 4. IMPLEMENTATION AND OPTIMIZATION 0 2000 4000 6000 8000 10000 12000 14000 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 Combinations of pairs of maps on alphabet HA and HB Output of the linprog: fval Single pair optimization over D2: part of 1142 possibilities Figure 4.9: Optimization over the partial pairs of maps over the distribution D2 5 Conclusion and outlook The problem of secure communication is usually solved by making assumptions on the eavesdropper’s computational power - the computational security. There is a however a stronger form of security, known as information-theoretical security, where a protocol can be shown to be secure using Information Theory terms. In this formalism, it is enough to consider the part of the secret-key agreement because there are protocols that ensure the secret communication given a secret-key. The standard key-agreement scenario consists of two honest parties, that communicate over an authenticated channel, and the wire-tapper, all of them sharing correlated random variables described by a joint probability distribution. One of the main questions is to understand how, if possible, the honest parties can distill a secret key out of their correlated variables. There exists strong evidence towards the existence of distributions that contain an irreversible form of secrecy, i.e. secrecy that cannot be distilled into a secret-key by local operations and public communication. This form of secrecy, known as bound information, has been proven so far for the multipartite case, with more than two honest parties, but is still an open question for the more natural bipartite case. The main difficulty in proving the existence of bound information comes from the fact that, given an initial probability distribution, one has to show that there is no protocol leading to a secret key. Indeed, all the support so far to the existence of this quantity comes from probability distributions containing secret correlations that cannot be distilled into a secret key by any of the known protocols. The non-distillability criterion discussed in chapter 3 is a potentially promising approach to find this irreversible form of secrecy, as may allow proving the non-distillability of a distribution. The main goal of this thesis was first to implement this criterion, to test it and then to simulate the most suitable distributions. From the theory we knew that the algorithm could be adapted to a linear programming algorithm that was already available in the MATLABc repository. The adaptation did not turn out to be such a big problem, but it pointed out that the testing was the bigger challenge. The condition that a non-distillable distribution has a secret-bit fraction of 1/2 is necessary so we could not check the functionality by a distribution that is known to be non-distillable. Therefore we had to revise the code step by step. Once we were certain that the program worked well we faced the next problem of the bi43 44 5. CONCLUSION AND OUTLOOK narization maps. With the number of maps we exceeded the memory of the simulation machines and also the suitable limit of simulation time. So it was necessary to reduce the number of pairs of maps. This was accomplished by the removal of redundant maps and a pre-optimization to detect the most suitable ones. Due to the limited remaining time we decided to simulate a part of all possibilities to obtain meaningful results. Indeed we were able to show a big improvement towards the nondistillability of our distribution, but none of the obtained results was conclusive. For a complete test it is an option to split the missing part of the maps in several smaller optimizations and combine those results to attempt to obtain the highest efficiency of the program in an iterative way. This can also be automated by another program to facilitate the process. Another approach can be to find the best maps through another non-linear optimization. This is non-linear because we have to find two matrices for alphabet A and B at the same time. These results may be introduced as the starting point of the maximization of our linear programming. We would also like to mention that it is also possible that the proposed criterion is in fact useless to prove the existence of bound information. The main idea of the criterion is to show that the initial distribution, with conjectured bound information, cannot improve the secrecy properties of any distribution. If this is the case, the distribution has to be non-distillable. Recall however that bound information was introduced as a cryptographic analog of bound entanglement, an irreversible form of quantum correlations observed in Quantum Information Theory. In the quantum case, all bound entangled states have been shown to improve the entanglement properties of another state. If the same was true for probability distributions, the analyzed criterion would be useless for the detection of bound information. This is however a theoretical open question in the classical case that deserves further investigation. To conclude, the existence of bound information, conjectured in 2000 by Gisin and Wolf, is a nice and natural question in the key agreement scenario that remains open in spite of years of research. In this work, we have tested the first proposed criterion for the detection of non-distillable secret correlations. The obtained results somehow give more evidence for the existence of this quantity but, unfortunately, cannot solve the problem. A Appendix: Conditional mutual information The mutual information gives us some knowledge about the correlation between two parties within their distribution. It can be written in the following forms: I(X,Y)=X x∈XX y∈Y P(x,y) log P(x|y) P(x) =H(X)−H(X|Y) =H(Y)−H(Y|X) =H(X)+H(Y)−H(X,Y) The conditional entropy for the tripartite scenario can be derived as: H(X,Y|Z)=H(Y|Z,X)+H(X|Z) =H(X,Y,Z)−H(Z) And hence we can formulate the conditional mutual information as the correlation between two parties given the information of a third one: I(X,Y|Z)=H(X|Z)−H(X|Y,Z) here we used the formulas for the n-dimensional case: H(X1, ...Xn)= n X i=1 H(Xi|Xi−1, ...X1) (A.1) H(X1, ...Xn|Y)= n X i=1 H(Xi|Y;X1, ...Xi−1) (A.2) 45 46 B Appendix: Introduction to quantum mechanics Most of the distributions analyzed in this thesis are derived from measurements applied to tripartite quantum states. The very same concept of bound information was indeed proposed as a classical analog of bound entanglement, an irreversible form of quantum correlations appearing in quantum information theory. For the sake of completeness, we provide in this appendix a short introduction to the basic mathematical objects of quantum mechanics in general and, later, quantum information theory. This chapter is not thought to be a complete summary of quantum theory. Therefore we would like to refer those readers interested in the quantum formalism to [16]. Indeed, most of the discussion in the next lines follows this reference. B.1 Postulates of quantum mechanics In quantum mechanics on uses the bra hφ|and ket |φinotation to represent a quantum states, where ket is considered to be a columnvector and bra is the adjoint one, i.e. hφ|=(|φi∗)T, both having complex elements. B.1.1 State space Postulate Associated to any isolated physical system is a complex vector space with inner product (that is, a Hilbert space) known as the state space of the system. The system is completely described by its state vector, which is a unit vector in the system’s state space. The simplest quantum mechanical system is the qubit, which corresponds to a two - dimensional Hilbert space. Suppose |0iand |1iform an orthonormal basis for that state space. Then an arbitrary state vector in the state space can be written as the superposition of the basis vectors |ψi=a|0i+b|1i,(B.1) where a,b∈and |ψiis a new valid state of the system. This is main difference to a classical bit which can only be in the zero or one state. Thus the qubit system is located in a 47 54 Bibliography [13] M, L. ; W, A.: A non-distillability criterion for secret correlations. (2008) [14] J, N. S. ; M, L.: Key distillation and the secret-bit fraction. In: IEEE Transactions on Information Theory 54 (2008), S. 680 [15] A, A. ; G, N. ; M, L.: From Bell’s theorem to secure quantum key distribution. In: Physical Review Letters 97 (2006), S. 120405 [16] N, M. A. ; C, I. L.: Quantum computation and quantum information. Cambridge University Press, 2000 [17] H, M. ; H, P. ; H, R.: Separability of mixed states: necessary and sufficient conditions. In: Physics Letters A (1996)