text:
# Security of EPR-based Quantum Key Distribution

## 1 Introduction

Quantum key distribution is a cryptographic task that uses properties of quantum mechanics to allow two legitimate parties to share a secret random number. This random number can be used as a key for a symmetric classical cipher to establish a perfectly secure communication channel between the legitimate parties. The first quantum key distribution protocol, called BB84, was proposed by Bennett and Brassard . It was followed by other protocols, such as  and the security of these protocols were analysed . The unconditional security of quantum key distribution – i.e. security against enemies with unlimited computational power – was obtained by Mayers  for the BB84 protocol and many notions and techniques introduced in the proof are used in the present paper. Other proofs of the unconditional security of BB84 followed . The security of EPR-based quantum key distribution protocol proposed by Ekert, E91 , has also been proved in , and the security of entanglement-based quantum key distribution using untrusted apparatus has been proved in . In this paper, we propose another proof of the security of E91. The protocol is proved secure against enemies with unlimited computational power. However, it is assumed that both legitimate parties receive an ensemble of a given number of single photons. Furthermore we assume that the efficiency of their detection unit is one, which is far from true in any practical implementation of quantum key distribution today. The results in this paper therefore do not apply to practical implementations of EPR-based quantum key distribution. Nevertheless it is hoped that techniques employed in this paper can be generalised to prove security of practical EPR-based quantum key distribution protocols.

## 2 Definition of security

We adopt the same definition of security as described in .

The rôle of key distribution between two distant legitimate parties, traditionally called Alice and Bob, is to generate a shared random number, called the *private key*, that is guaranteed to be known only by the legitimate parties. A non-authorised party, traditionally called Eve, should not be able to obtain any information about the private key, whichever eavesdropping strategy she might adopt.

However, most quantum key distribution protocols do not allow Alice and Bob to share a private key in all circumstances. It is only when some conditions are satisfied that Alice and Bob can ascertain a potential eavesdropper will only have negligible information about the key. The protocol therefore provides a *validation test* that tells whether a key can be generated with unconditional privacy. A key is created only if the test is passed. Otherwise the session is abandoned. Nevertheless, as in  we will adopt the convention that when the validation test is not passed, Alice chooses a random value for the private key with uniform probability distribution. As a result, the private key is defined regardless the outcome of the validation test, but, of course, when the validation test is not passed, Bob does not share the key with Alice.

Finally, we consider families of protocols for which a parameter quantifying the amount of a resource used in a protocol characterises its security. Such parameter is called *security parameter*. Usually, the higher the security parameter’s value is, the higher is the level of security, but also the amount of a resource required by the protocol. We now give a formal definition of security.

A random variable will always be denoted by a bold letter, and values taken by this random variable by the corresponding plain letter. Only discrete random variables will be considered in this paper. The probability distribution of a random variable $`𝒙`$ is denoted by $`\mathrm{P}_𝒙`$, i.e. $`\mathrm{P}_𝒙(x)=\mathrm{Pr}(𝒙=x)`$ is the probability that $`𝒙`$ takes the value $`x`$. The joint distribution of two random variables $`𝒙`$ and $`𝒚`$ is denoted by $`\mathrm{P}_{𝒙𝒚}`$, i.e. $`\mathrm{P}_{𝒙𝒚}(x,y)=\mathrm{Pr}(𝒙=x,𝒚=y)`$. The conditional probability of $`𝒙`$ given that $`𝒚`$ takes a value $`y`$ is denoted by $`\mathrm{P}_{𝒙|𝒚=y}`$ whenever $`\mathrm{P}_𝒚(y)>0`$, i.e. $`\mathrm{P}_{𝒙|𝒚=y}(x)=\mathrm{Pr}(𝒙=x|𝒚=y)=\frac{\mathrm{P}_{𝒙𝒚}(x,y)}{\mathrm{P}_𝒚(y)}`$, whenever $`\mathrm{P}_𝒚(y)`$ is positive. Let $`f`$ be a function defined on the image of $`𝒙`$. When no confusion is possible, the notation $`𝒇`$ will be adopted to denote the random variable $`f(𝒙)`$.

We will denote by $`\stackrel{\mathbf{}}{𝜿}`$ the random variable giving the private key generated in a key distribution session. The key is a string of $`m`$ bits where $`m`$ is a positive integer specified by the legitimate users. That is $`\stackrel{\mathbf{}}{𝜿}`$ takes value in $`\{0,1\}^m`$. Given an eavesdropping strategy chosen by Eve, we denote by $`𝒗`$ the random variable giving collectively all data Eve gets during this key distribution session. Henceforth, given the eavesdropping strategy adopted by Eve, $`𝒗`$ is called the *view* of Eve, and we will denote by $`𝒱`$ the set of all values $`𝒗`$ may take.

We adopt the following definition of security for quantum key distribution protocols.

###### Definition 1

Consider a quantum key distribution protocol returning a key $`\stackrel{\mathbf{}}{𝛋}\{0,1\}^m`$ regardless the outcome of the validation test, where the length of the key, $`m`$, is fixed and chosen by the user. We say that the protocol offers *perfect privacy* if and only if:

* the protocol is parametrised by a parameter $`N`$ taking value in $`𝐍`$ called the security parameter, and
* there exists a function $`ϵ:𝐍\times 𝐍𝐑^+`$ such that $`ϵ(N,m)`$ is vanishing exponentially as $`N`$ grows (i.e. there exist $`\alpha >0`$, $`\beta >0`$, $`N_{min}𝐍`$ and a function $`f:𝐍𝐑^+`$ such that $`N>N_{min},ϵ(N,m)<e^{\alpha N^\beta }f(m)`$) , and
* there exists a function $`N_0:𝐍𝐍`$ such that, for any strategy adopted by Eve,

$`m,NN_0(m),`$
$`H(\stackrel{\mathbf{}}{𝜿}|𝒗)mϵ(N,m)`$
where $`𝒗`$ is Eve’s view given her strategy, and

$$H(\stackrel{\mathbf{}}{𝜿}|𝒗)\stackrel{Def}{=}\underset{\stackrel{}{\kappa },v:\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v)>0}{}\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v)\mathrm{log}_2\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}|𝒗=v}(\stackrel{}{\kappa })$$

is the Shannon entropy  of the key $`\stackrel{\mathbf{}}{𝜿}`$ given Eve’s view $`𝒗`$.

Another important aspect of security of key distribution protocols is the *integrity* or the faithfulness of the distributed key. We must require that whatever Eve does, it is very unlikely that Alice and Bob fail to share an identical private key while the validation test is passed. However, the integrity of the protocol depends mainly on the efficiency of the error detection/correction scheme that is used. This point is discussed in Appendix, but the reader is referred for instance to  for a more complete explanation.

## 3 The protocol

We describe the quantum key distribution protocol under consideration. It is a variation  of the protocol originally proposed in . The protocol is designed to use classical error-reconciliation schemes like the interactive scheme proposed in .

Alice and Bob specify:

* $`m`$, the length (in bits) of the private key to be generated.
* $`ϵ`$, the maximum threshold value for the error rate during the quantum transmission ($`ϵ<1/4`$).
* $`\tau `$, a security constant such that $`\frac{2ϵ}{1ϵ}<\frac{2ϵ}{1ϵ}+\tau <1`$.
* the security parameter $`r`$. It must be large enough so that Alice and Bob can find a binary matrix $`K`$ of size $`m\times r`$ such that any linear combination of rows of $`K`$ that contains at least one row of $`K`$ has weight greater than $`d_K=\left(2\frac{ϵ}{1ϵ}+\tau \right)r`$ (i.e. $`\mathrm{min}_{\stackrel{}{x}\{0,1\}^m\stackrel{}{0}}(w(\stackrel{}{x}^TK))d_K`$ where for any vector $`\stackrel{}{y}`$, $`w(\stackrel{}{y})`$ is the weight of $`\stackrel{}{y}`$, that is, the number of non zero entries in $`\stackrel{}{y}`$). Alice and Bob choose one such matrix $`K`$. Shannon’s coding theorem  tells that for asymptotic values of $`m`$, such matrix can be found if $`r`$ obeys the inequality:

$$\frac{m}{r}1h\left(\frac{ϵ}{1ϵ}+\frac{\tau }{2}\right),$$

where $`h(ϵ)=ϵ\mathrm{log}_2ϵ(1ϵ)\mathrm{log}_2(1ϵ)`$ is Shannon’s binary entropy.
* An error reconciliation scheme between Alice and Bob such that:

+ it tells, with high probability of correctness, whether more than $`ϵs`$ errors are present in a string of $`s`$ bits, where $`s=\frac{r}{1ϵ}`$,
    + if there are less than $`ϵs`$ errors in the string, the scheme corrects these errors, at least with high probability of success,
    + only positions of the errors are possibly disclosed publicly. In particular the scheme should disclose no information about parities of the reconciled string.

The error reconciliation can be a probabilistic scheme for which an upper-bound on the probability of failure can be specified by Alice and Bob. One can achieve such a task by first estimating the error rate on a small randomly chosen proportion of the string and then by using for instance the interactive error-reconciliation scheme proposed in . In these processes, the exchanged parities or bits should be encrypted with the one-time pad method . A basic explanation of this scheme can be found in Appendix A, but the reader is referred to  for a complete description. The above requires that Alice and Bob share beforehand a secret private key for the one-time pad encryption. According to Shannon’s coding theorem, for asymptotic values of $`s`$, such probabilistic error-reconciliation is possible if the entropy111That is, the length of the previously shared key if it is uniformly distributed. $`q`$ (in bits) of the previously shared private key obeys the inequality:

$$qsh(ϵ).$$
* $`n`$, the number of pairs of photons to be sent to the legitimate parties. A good choice for $`n`$ is $`\frac{r}{\frac{1ϵ}{2}\tau _S}`$ where $`\tau _S`$ is a small but strictly positive constant.

* A source sends a sequence of $`n`$ photons to Alice and another sequence of $`n`$ photons to Bob. It is assumed that ideally, for each $`i\{1\mathrm{}n\}`$, the source emits a pair of photons in the state:

$$|\mathrm{\Phi }^+=\frac{|\mathrm{\hspace{0.17em}0}_+|\mathrm{\hspace{0.17em}0}_++|\mathrm{\hspace{0.17em}1}_+|\mathrm{\hspace{0.17em}1}_+}{\sqrt{2}}$$

and that Alice’s $`i`$-th photon is the first photon of this pair, and Bob’s $`i`$-th photon is the second photon of this pair. The kets $`|\mathrm{\hspace{0.17em}0}_+`$ and $`|\mathrm{\hspace{0.17em}1}_+`$ form an orthonormal basis $`+`$ of the Hilbert space describing the polarisation of one photon. The kets $`|\mathrm{\hspace{0.17em}0}_\times =\frac{|\mathrm{\hspace{0.17em}0}_++|\mathrm{\hspace{0.17em}1}_+}{\sqrt{2}}`$ and $`|\mathrm{\hspace{0.17em}1}_\times =\frac{|\mathrm{\hspace{0.17em}0}_+|\mathrm{\hspace{0.17em}1}_+}{\sqrt{2}}`$ form its conjugate basis $`\times `$.

However, the source needs not to be trusted. In particular, it can be under control of a possible eavesdropper. The only assumption is that Alice and Bob receive a sequence of $`n`$ single photon signals on each side.
* We assume that the measurement devices of Alice and Bob have efficiency one. For each $`i\{1\mathrm{}n\}`$,

1. Alice picks randomly a basis $`a_i\{+,\times \}`$ with uniform probability distribution. Alice measures her $`i`$-th photon in the basis $`a_i`$, obtaining the outcome $`\alpha _i\{0,1\}`$, corresponding to the state $`|\alpha _i_{a_i}`$.
    2. Similarly, Bob picks randomly and independently of Alice a basis $`b_i\{+,\times \}`$ with uniform probability distribution. Bob measures his $`i`$-th photon in the basis $`b_i`$, obtaining the outcome $`\beta _i\{0,1\}`$, corresponding to the state $`|\beta _i_{b_i}`$.

We denote by $`\stackrel{}{a}=(a_1,a_2,\mathrm{},a_n)`$, $`\stackrel{}{b}=(b_1,b_2,\mathrm{},b_n)`$, $`\stackrel{}{\alpha }=(\alpha _1,\alpha _2,\mathrm{},\alpha _n)`$ and $`\stackrel{}{\beta }=(\beta _1,\beta _2,\mathrm{},\beta _n)`$ the outcomes of the quantum transmission. For any vector $`\stackrel{}{y}=(y_1,y_2,\mathrm{},y_n)`$ in $`\{0,1\}^n`$ or $`\{+,\times \}^n`$, and for any subset $`X`$ of $`\{1\mathrm{}n\}`$, we denote by $`y_X`$ the restriction of $`\stackrel{}{y}`$ on $`X`$.

Alice and Bob compare publicly their bases $`\stackrel{}{a}`$ and $`\stackrel{}{b}`$. We denote by $`\stackrel{}{d}`$ the vector in $`\{0,1\}^n`$ such that for any $`i\{1\mathrm{}n\}`$, $`d_i=1`$ if and only if $`a_i=b_i`$. If the number of indexes $`i\{1\mathrm{}n\}`$ such that $`a_i=b_i`$ is greater than or equal to $`s`$ (i.e. $`w(\stackrel{}{d})s`$) then the *sifted set* $`S`$ is defined as the set of the first $`s`$ such indexes. Otherwise the validation test is failed. The bit strings $`\alpha _S`$ and $`\beta _S`$ are usually referred to as the *sifted keys*.

Alice and Bob perform the error correction on their sifted keys $`\alpha _S`$ and $`\beta _S`$ as specified in the protocol setup. We define the *error set* $`E`$ as the set of indexes in $`S`$ in which an error is found, that is, $`\alpha _i\beta _i`$. Likewise, we define the *error vector* $`\stackrel{}{e}`$ as the vector in $`\{0,1\}^s`$ giving the positions of the errors ($`i\{1,\mathrm{},s\}`$, $`e_i=1`$ if and only if $`\alpha _i\beta _i`$). We denote by $`e`$ the size of the set $`E`$, i.e. $`e=|E|=w(\stackrel{}{e})`$. The validation test is passed if $`e<ϵs`$, otherwise it is failed. If the validation test is passed, then Alice and Bob define the *reconciled set* $`R`$ as the set of the first $`r`$ indexes $`iSE`$ 222 Note that $`|SE|r`$ if the validation test is passed.. Therefore $`|R|=r`$ and $`iR`$, $`a_i=b_i`$ and $`\alpha _i=\beta _i`$. Alice and Bob obtain an identical string of bits $`\alpha _R\{0,1\}^r`$, called the *reconciled key*.

The private key is defined as:

1. $`\stackrel{}{\kappa }=K\alpha _R(mod2)`$ if the validation test is passed.
2. an $`m`$-bit string $`\stackrel{}{\kappa }`$ picked randomly by Alice with uniform probability distribution each time the validation test is failed.

## 4 Privacy of the protocol

The main result of this paper is stated.

###### Property 1

The protocol described above offers perfect privacy: for any eavesdropping strategy chosen by a possible eavesdropper, the conditional entropy of the private key $`\stackrel{\mathbf{}}{𝛋}`$ given the eavesdropper’s view $`𝐯`$ is bounded from below by:

$$H(\stackrel{\mathbf{}}{𝜿}|𝒗)m2\left(m+\frac{1}{\mathrm{ln}2}\right)\left(\theta (r)+2\sqrt{\theta (r)}\right),$$

where

$$\theta (r)=2^{\left(1h\left(\frac{1}{2}\frac{3}{16}\tau \right)\right)\frac{\tau }{2}r}.$$

The above bound applies for any value of the security parameter $`r`$ such that the matrix $`K`$ specified in the protocol exists.

The protocol uses previously shared private key for the error reconciliation. A net gain in shared private bits is achieved if $`m`$ is greater than the number of the secret bits used during error reconciliation. For asymptotic values of $`m`$, we can take arbitrarily small values for the security parameter and a net gain in private bits is obtained if $`m>sh(ϵ)\frac{r}{1ϵ}h(ϵ)`$. We have seen that privacy amplification is possible if $`\frac{m}{r}1h\left(\frac{ϵ}{1ϵ}\right)`$. Therefore, a net gain in shared private bits can be obtained for asymptotic values of $`m`$ if:

$$1h\left(\frac{ϵ}{1ϵ}\right)\frac{1}{1ϵ}h(ϵ)>0.$$

## 5 Proof of the privacy

### 5.1 Notations

We define the notations used throughout the proof.

We denote collectively by $`C=(\stackrel{}{a},\stackrel{}{b},\stackrel{}{\alpha },\stackrel{}{\beta })`$ the classical data Alice and Bob generate during the protocol (after the setup). Note that other variables Alice and Bob generate during the protocol can be deterministically derived from $`C`$. We denote by $`P=(\stackrel{}{a},\stackrel{}{d},\stackrel{}{e})`$ the data that are publicly announced by Alice and Bob during the protocol. Recall that specifying $`\stackrel{}{a}`$ and $`\stackrel{}{d}`$ is equivalent to specifying $`\stackrel{}{a}`$ and $`\stackrel{}{b}`$. For any possible $`P`$, we denote by $`𝒞_P`$ the set of values for the classical data that are compatible with the public announcement of $`P`$. That is, for a given $`P=(\stackrel{}{a},\stackrel{}{d},\stackrel{}{e})`$,

$`𝒞_P`$ $`=`$ $`\{C^{}=(\stackrel{}{a}^{},\stackrel{}{b}^{},\stackrel{}{\alpha }^{},\stackrel{}{\beta }^{}):\stackrel{}{a}^{}=\stackrel{}{a},`$
$`i,b_i^{}=a_i\text{ if }d_i=1,b_i^{}a_i\text{ if }d_i=0`$
$`iE,\alpha _i^{}\beta _i^{}\text{ and }iSE,\alpha _i^{}=\beta _i^{}`$
$`\text{where }S\text{ and }E\text{ are given by }\stackrel{}{d}\text{ and }\stackrel{}{e}\text{.}\}.`$
Given a possible $`P`$ and a value for the private key $`\stackrel{}{\kappa }`$, we define $`𝒞_{P,\stackrel{}{\kappa }}`$ as the set of values for the classical data that are compatible with the public announcement of $`P`$ and generation of $`\stackrel{}{\kappa }`$ for the private key. That is, for a given $`P=(\stackrel{}{a},\stackrel{}{d},\stackrel{}{e})`$,

$`𝒞_{P,\stackrel{}{\kappa }}`$ $`=`$ $`\{C^{}=(\stackrel{}{a}^{},\stackrel{}{b}^{},\stackrel{}{\alpha }^{},\stackrel{}{\beta }^{}):\stackrel{}{a}^{}=\stackrel{}{a},`$
$`i,b_i^{}=a_i\text{ if }d_i=1,b_i^{}a_i\text{ if }d_i=0`$
$`iE,\alpha _i^{}\beta _i^{}\text{ and }iSE,\alpha _i^{}=\beta _i^{}`$
$`K\alpha _R^{}=\stackrel{}{\kappa }(mod2),`$
$`\text{where }S\text{}E\text{ and }R\text{ are given by }\stackrel{}{d}\text{ and }\stackrel{}{e}\text{.}\}.`$
Finally, we denote by $`𝒫`$ the set of all possible public announcements for which the validation test is passed. That is,

$$𝒫=\{P=(\stackrel{}{a},\stackrel{}{d},\stackrel{}{e}):w(\stackrel{}{d})s\text{ and }e<ϵs\}.$$

For any vector $`\stackrel{}{x}`$ and any symbol $`A`$, $`w(\stackrel{}{x})`$ is the number of non-zero entries, and $`w_A(\stackrel{}{x})`$ is the number of entries with symbol $`A`$. For any vector $`\stackrel{}{x}\{0,1\}^n`$, we denote by $`\neg \stackrel{}{x}`$ the vector whose $`i`$-th entry is $`1+x_i(mod2)`$ for all $`i\{1\mathrm{}n\}`$. Finally, we denote by $`T`$ the subset $`S(ER)`$, and by $`t`$ the size of $`T`$.

For each $`i\{1\mathrm{}n\}`$, we define the Bell basis $`\{|\mathrm{\hspace{0.17em}0}_i,|\mathrm{\hspace{0.17em}1}_i,|\mathrm{\hspace{0.17em}2}_i,|\mathrm{\hspace{0.17em}3}_i\}`$ of the $`i`$-th pair of photons as:

$`|\mathrm{\hspace{0.17em}0}_i`$ $`=`$ $`{\displaystyle \frac{|\mathrm{\hspace{0.17em}0}_{+,i}|\mathrm{\hspace{0.17em}0}_{+,i}+|\mathrm{\hspace{0.17em}1}_{+,i}|\mathrm{\hspace{0.17em}1}_{+,i}}{\sqrt{2}}},`$
$`|\mathrm{\hspace{0.17em}1}_i`$ $`=`$ $`{\displaystyle \frac{|\mathrm{\hspace{0.17em}0}_{+,i}|\mathrm{\hspace{0.17em}0}_{+,i}|\mathrm{\hspace{0.17em}1}_{+,i}|\mathrm{\hspace{0.17em}1}_{+,i}}{\sqrt{2}}},`$
$`|\mathrm{\hspace{0.17em}2}_i`$ $`=`$ $`{\displaystyle \frac{|\mathrm{\hspace{0.17em}0}_{+,i}|\mathrm{\hspace{0.17em}1}_{+,i}+|\mathrm{\hspace{0.17em}1}_{+,i}|\mathrm{\hspace{0.17em}0}_{+,i}}{\sqrt{2}}},`$
$`|\mathrm{\hspace{0.17em}3}_i`$ $`=`$ $`{\displaystyle \frac{|\mathrm{\hspace{0.17em}0}_{+,i}|\mathrm{\hspace{0.17em}1}_{+,i}|\mathrm{\hspace{0.17em}1}_{+,i}|\mathrm{\hspace{0.17em}0}_{+,i}}{\sqrt{2}}},`$
where the first and the second state in the product states in the rhs. correspond to Alice’s and Bob’s $`i`$-th photon’s polarisation state, respectively. Tensor products are implied when we consider state of several photons, that is, $`|\stackrel{}{\alpha },\stackrel{}{\beta }_{\stackrel{}{a},\stackrel{}{b}}=_{i=1}^n|\alpha _i_{a_i,i}|\beta _i_{b_i,i}`$ and $`|\stackrel{}{c}=_{i=1}^n|c_i_i`$. For any subset $`X`$ of $`\{1\mathrm{}n\}`$, $`|\alpha _X,\beta _X_{a_X,b_X}=_{iX}|\alpha _i_{a_i,i}|\beta _i_{b_i,i}`$.

Given a basis $`a\{+,\times \}`$, we define $`X_a`$ as the set of indexes of Bell states that are compatible with Alice and Bob measuring in the same basis $`a`$ and sharing the same bit value. Likewise, we define $`Y_a`$ as the set of indexes of Bell states that are compatible with Alice and Bob measuring in basis $`a`$ and not sharing the same bit value. That is, $`X_+=\{0,1\}`$, $`X_\times =\{0,2\}`$, $`Y_+=\{2,3\}`$ and $`Y_\times =\{1,3\}`$. Given the choice of bases $`\stackrel{}{a}`$ and a set $`A\{1\mathrm{}n\}`$, we define $`X_{a_A}`$ as $`\{c_A\{0,1,2,3\}^A:iA,c_iX_{a_i}\}`$ and $`Y_{a_A}`$ as $`\{c_A\{0,1,2,3\}^A:iA,c_iY_{a_i}\}`$. Given a reconciled set $`R`$ and the choice of bases $`a_R`$ on $`R`$, for any $`c_RX_{a_R}`$, we will denote by $`\stackrel{}{\gamma }`$ the unique $`\stackrel{}{\gamma }\{0,1\}^r`$ such that for each $`i\{1,\mathrm{},r\}`$, $`c_i=(1+w_\times a_i)\gamma _i`$, i.e. $`c_i=\gamma _i`$ if $`a_i=+`$, and $`c_i=2\gamma _i`$ if $`a_i=\times `$. For any vectors $`\stackrel{}{x}`$, $`\stackrel{}{y}`$ $`\{0,1\}^r`$, we define $`\stackrel{}{x}\stackrel{}{y}`$ as $`\stackrel{}{x}\stackrel{}{y}\stackrel{Def}{=}_{i=1}^rx_iy_i`$. Given $`R`$ and $`a_R`$, for any $`c_RX_{a_R}`$, we have the identity $`{}_{a_R}{}^{}\alpha _R,\alpha _R|c_R=\frac{(1)^{\alpha _R\stackrel{}{\gamma }}}{\sqrt{2}^r}`$.

### 5.2 Model of measurements

A mathematical model of measurements on the quantum state generated by the source is given. The source can be under complete control of Eve, as long as it sends $`n`$ single photons to both Alice and Bob. In such a scenario, Eve may entangle a probe of any dimension to the photons she sends to Alice and Bob which are in any state Eve wants. We write the state of these $`n`$ couples of photons and the probe in the Bell basis as follows:

$$\rho =\underset{\stackrel{}{c},\stackrel{}{c}^{}}{}|E_\stackrel{}{c}E_\stackrel{}{c}^{}||\stackrel{}{c}\stackrel{}{c}^{}|,$$

where the states $`|E_\stackrel{}{c}`$ are states of Eve’s probe that are possibly nor orthogonal nor normalised. The positive operator giving the probability that Alice and Bob get $`C=(\stackrel{}{a},\stackrel{}{b},\stackrel{}{\alpha },\stackrel{}{\beta })`$ as their classical data is simply:

$$F_C=\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒃}(\stackrel{}{b})|\stackrel{}{\alpha },\stackrel{}{\beta }_{\stackrel{}{a},\stackrel{}{b}}_{\stackrel{}{a},\stackrel{}{b}}\stackrel{}{\alpha },\stackrel{}{\beta }|,$$

where $`\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})=1/2^n`$ and $`\mathrm{P}_\stackrel{\mathbf{}}{𝒃}(\stackrel{}{b})=1/2^n`$ for any choice of $`\stackrel{}{a}`$ and $`\stackrel{}{b}`$. Note that $`\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒃}(\stackrel{}{b})=\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})`$ where $`\mathrm{P}_\stackrel{\mathbf{}}{𝒅}=1/2^n`$.

The positive operator giving the probability that Alice and Bob publicly announce $`P=(\stackrel{}{a},\stackrel{}{d},\stackrel{}{e})`$ while they get the private key $`\stackrel{}{\kappa }`$ is the sum of the operators $`F_C^{}`$ for $`C^{}`$ running over $`𝒞_{P,\stackrel{}{\kappa }}`$:

$`F_{P,\stackrel{}{\kappa }}`$ $`=`$ $`{\displaystyle \underset{C^{}𝒞_{P,\stackrel{}{\kappa }}}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a}^{})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}^{})|\stackrel{}{\alpha }^{},\stackrel{}{\beta }^{}_{\stackrel{}{a}^{},\stackrel{}{b}^{}}_{\stackrel{}{a}^{},\stackrel{}{b}^{}}\stackrel{}{\alpha }^{},\stackrel{}{\beta }^{}|`$
$`=`$ $`\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})\text{1}_{\overline{S}}{\displaystyle \underset{\alpha _E\{0,1\}^e}{}}|\alpha _E,\neg \alpha _E_{a_E,a_E}_{a_E,a_E}\alpha _E,\neg \alpha _E|`$
$`{\displaystyle \underset{\alpha _T\{0,1\}^t}{}}|\alpha _T,\alpha _T_{a_T,a_T}_{a_T,a_T}\alpha _T,\alpha _T|`$
$`{\displaystyle \underset{\begin{array}{c}\alpha _R\{0,1\}^r:\hfill \\ K\alpha _R=\stackrel{}{\kappa }\hfill \end{array}}{}}|\alpha _R,\alpha _R_{a_R,a_R}_{a_R,a_R}\alpha _R,\alpha _R|`$
where $`\text{1}_{\overline{S}}`$ is the identity operator acting on the Hilbert space describing photons not in $`S`$. Note that $`\stackrel{}{b}(S)=\stackrel{}{a}(S)`$.

Similarly, the positive operator giving the marginal probability that Alice and Bob publicly announce $`P=(\stackrel{}{a},\stackrel{}{d},\stackrel{}{e})`$ is the sum of the operators $`F_C^{}`$ for $`C^{}`$ running over $`𝒞_P`$:

$`F_P`$ $`=`$ $`{\displaystyle \underset{C^{}𝒞_P}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a}^{})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}^{})|\stackrel{}{\alpha }^{},\stackrel{}{\beta }^{}_{\stackrel{}{a}^{},\stackrel{}{b}^{}}_{\stackrel{}{a}^{},\stackrel{}{b}^{}}\stackrel{}{\alpha }^{},\stackrel{}{\beta }^{}|`$
$`=`$ $`\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})\text{1}_{\overline{S}}{\displaystyle \underset{\alpha _E\{0,1\}^e}{}}|\alpha _E,\neg \alpha _E_{a_E,a_E}_{a_E,a_E}\alpha _E,\neg \alpha _E|`$
$`{\displaystyle \underset{\alpha _T\{0,1\}^t}{}}|\alpha _T,\alpha _T_{a_T,a_T}_{a_T,a_T}\alpha _T,\alpha _T|`$
$`{\displaystyle \underset{\alpha _R\{0,1\}^r}{}}|\alpha _R,\alpha _R_{a_R,a_R}_{a_R,a_R}\alpha _R,\alpha _R|.`$
Eve may perform a general measurement on her probe. This general measurement can take place after Alice and Bob’s public announcements and therefore can be conditioned on $`𝑷`$. We will denote by $`𝒱_P`$ the set of views $`v`$ that are compatible with the public announcement $`P`$. The positive operator giving the probability that Eve gets the view $`v`$ given that Alice and Bob announced $`P`$ will be denoted by $`G_{v|P}`$. We will assume without loss of generality that the operators $`G_{v|P}`$ are of rank one, i.e. $`G_{v|P}=|\chi _{v|P}\chi _{v|P}|`$ where the vectors $`|\chi _{v|P}`$ are possibly not orthogonal nor normalised, but obey the relation $`_{v𝒱_P}G_{v|P}=\text{1}`$.

### 5.3 The rôle of the validation test

Here we show that it is very unlikely that the validation test is passed when the state of the photons emitted by the source is very different from the ideal state specified by the protocol. The underlying principle has been advanced in . More precisely, given a possible reconciled set $`R`$, let $`\mathrm{\Pi }_R`$ be the orthogonal projection operator defined as:

$`\mathrm{\Pi }_R`$ $`=`$ $`{\displaystyle \underset{\begin{array}{c}\stackrel{}{c}\{0,1,2,3\}^n:\hfill \\ w(c_R)d_K/2\hfill \end{array}}{}}|\stackrel{}{c}\stackrel{}{c}|`$
$`=`$ $`\text{1}_{\overline{R}}{\displaystyle \underset{\begin{array}{c}c_R\{0,1,2,3\}^r:\hfill \\ w(c_R)d_K/2\hfill \end{array}}{}}|c_Rc_R|.`$
The operator $`\mathrm{\Pi }_R`$ projects onto Bell states for pairs of photons in $`R`$ with weight greater than $`d_K/2=\left(\frac{ϵ}{1ϵ}+\frac{\tau }{2}\right)r`$. The following property is then proved.

###### Property 2

The eigenvalues of the semi-definite positive Hermitian operator

$$\underset{P𝒫}{}\mathrm{\Pi }_RF_P\mathrm{\Pi }_R,$$

where $`R`$ is specified by $`P`$ in the sum, are bounded from above by

$$\theta (r)=2^{\left(1h\left(\frac{1}{2}\frac{3}{16}\tau \right)\right)\frac{\tau }{2}r}.$$

Proof The above operator can be written as:

$$\underset{P𝒫}{}\mathrm{\Pi }_RF_P\mathrm{\Pi }_R=\underset{\begin{array}{c}\stackrel{}{d}\{0,1\}^n:\hfill \\ w(\stackrel{}{d})s\hfill \end{array}}{}\underset{\begin{array}{c}\stackrel{}{e}\{0,1\}^s:\hfill \\ w(\stackrel{}{e})<ϵs\hfill \end{array}}{}\mathrm{\Pi }_R\left(\underset{\stackrel{}{a}}{}F_P\right)\mathrm{\Pi }_R.$$

Now for given $`\stackrel{}{d}`$ and $`\stackrel{}{e}`$,

$$\underset{\stackrel{}{a}}{}F_P=\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})\text{1}_{\overline{S}}_{iE}Y_i_{jT}X_j_{kR}X_k,$$

where

$`X_i`$ $`=`$ $`|\mathrm{\hspace{0.17em}0}0|+{\displaystyle \frac{1}{2}}|\mathrm{\hspace{0.17em}1}1|+{\displaystyle \frac{1}{2}}|\mathrm{\hspace{0.17em}2}2|,`$
$`Y_i`$ $`=`$ $`|\mathrm{\hspace{0.17em}3}3|+{\displaystyle \frac{1}{2}}|\mathrm{\hspace{0.17em}1}1|+{\displaystyle \frac{1}{2}}|\mathrm{\hspace{0.17em}2}2|`$
are operators acting on $`i`$-th photon pair’s Hilbert space. The last equalities are derived directly from the definition of the Bell states. As a consequence, we have,

$$\mathrm{\Pi }_R\left(\underset{\stackrel{}{a}}{}F_P\right)\mathrm{\Pi }_R=\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})\text{1}_{\overline{S}}_{iE}Y_i_{jT}X_j\left(\underset{\begin{array}{c}c_R\{0,1,2\}:\hfill \\ w(c_R)d_K/2\hfill \end{array}}{}\frac{|c_Rc_R|}{2^{w_1(c_R)+w_2(c_R)}}\right).$$

Now, given $`\stackrel{}{d}\{0,1\}^n`$, the operator:

$$\underset{\stackrel{}{e}:w(\stackrel{}{e})<ϵs}{}\mathrm{\Pi }_R\left(\underset{\stackrel{}{a}}{}F_P\right)\mathrm{\Pi }_R$$

is diagonal in the Bell basis $`|c`$. Given a vector $`\stackrel{}{c}\{0,1,2,3\}^n`$ and an error vector $`\stackrel{}{e}\{0,1\}^s`$, a necessary condition for the scalar:

$$c|\mathrm{\Pi }_R\left(\underset{\stackrel{}{a}}{}F_P\right)\mathrm{\Pi }_R|c$$

to be non zero is that, for all $`iS`$,

* $`e_i=0`$ if $`c_i=0`$,
* $`e_i=1`$ if $`c_i=3`$, and
* $`w_1(c_S)+w_2(c_S)ew_3(c_S)+d_K/2`$ (otherwise $`w(c_R)`$ is smaller than $`d_K/2`$).

Let $`k=ew_3(c_S)`$. Then there are $`\left(\genfrac{}{}{0pt}{}{w_1(c_S)+w_2(c_S)}{k}\right)`$ such vectors $`\stackrel{}{e}`$ of weight $`e`$, if $`0k<ϵsw_3(c_S)`$ and $`kw_1(c_S)+w_2(c_S)d_K/2`$. Therefore,

$`c|{\displaystyle \underset{\stackrel{}{e}:w(\stackrel{}{e})<ϵs}{}}\mathrm{\Pi }_R\left({\displaystyle \underset{\stackrel{}{a}}{}}F_P\right)\mathrm{\Pi }_R|c`$
$``$ $`{\displaystyle \frac{\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})}{2^{w_1(c_S)+w_2(c_S)}}}{\displaystyle \underset{\begin{array}{c}0k<ϵsw_3(c_S),\text{and}\hfill \\ kw_1(c_S)+w_2(c_S)\frac{d_K}{2}\hfill \end{array}}{}}\left({\displaystyle \genfrac{}{}{0pt}{}{w_1(c_S)+w_2(c_S)}{k}}\right).`$
Now, $`d_K`$ is either greater or smaller than $`(w_1(c_S)+w_2(c_S))\left(1+\frac{\tau }{2}(1ϵ)\right)`$.

* If $`d_K>(w_1(c_S)+w_2(c_S))\left(1+\frac{\tau }{2}(1ϵ)\right)`$, then

$$w_1(c_S)+w_2(c_S)\frac{d_K}{2}<\frac{1}{2}\left(1\frac{\tau }{2}(1ϵ)\right)(w_1(c_S)+w_2(c_S))\text{ and,}$$
* if $`d_K(w_1(c_S)+w_2(c_S))\left(1+\frac{\tau }{2}(1ϵ)\right)`$, then

$`ϵsw_3(c_S)`$ $``$ $`{\displaystyle \frac{ϵr}{1ϵ}}`$
$`=`$ $`{\displaystyle \frac{d_K}{2}}{\displaystyle \frac{\tau }{2}}r`$
$``$ $`{\displaystyle \frac{1}{2}}\left(1{\displaystyle \frac{\tau }{2}}(1ϵ)\right)(w_1(c_S)+w_2(c_S)),`$
where we have used $`rs(1ϵ)`$ and $`sw_1(c_S)+w_2(c_S)`$.

We thus derived that:

$`c|{\displaystyle \underset{\stackrel{}{e}:w(\stackrel{}{e})<ϵs}{}}\mathrm{\Pi }_R\left({\displaystyle \underset{\stackrel{}{a}}{}}F_P\right)\mathrm{\Pi }_R|c`$
$``$ $`{\displaystyle \frac{\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})}{2^{w_1(c_S)+w_2(c_S)}}}{\displaystyle \underset{0k<\frac{1}{2}\left(1\frac{\tau }{2}(1ϵ)\right)(w_1(c_S)+w_2(c_S))}{}}\left({\displaystyle \genfrac{}{}{0pt}{}{w_1(c_S)+w_2(c_S)}{k}}\right)`$
$``$ $`\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})2^{\left(1h\left(\frac{1}{2}\left(1\frac{\tau }{2}(1ϵ)\right)\right)\right)(w_1(c_S)+w_2(c_S))}`$
$``$ $`\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})2^{\left(1h\left(\frac{1}{2}\frac{3}{16}\tau \right)\right)\frac{\tau }{2}r}`$
$`=`$ $`\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})\theta (r)`$
where we have used the binomial inequality stating that $`_{0k<pn}\left(\genfrac{}{}{0pt}{}{n}{k}\right)2^{nh(p)}`$ for any positive integer $`n`$ and $`0p<1/2`$. In the last inequality we have used the inequalities $`ϵ<1/4`$ and $`w_1(c_S)+w_2(c_S)d_K/2`$ when the above scalar is non zero.

Remarking that the operator $`_{\stackrel{}{a},\stackrel{}{e}:e<ϵs}\mathrm{\Pi }_RF_P\mathrm{\Pi }_R`$ is diagonal in the Bell basis for all $`\stackrel{}{d}`$ and $`_{\stackrel{}{d}:w(\stackrel{}{d})s}\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})1`$, this concludes the proof.$`\mathrm{}`$

We recall that $`\rho =_{\stackrel{}{c},\stackrel{}{c}^{}}|E_\stackrel{}{c}E_\stackrel{}{c}^{}||\stackrel{}{c}\stackrel{}{c}^{}|`$ is the density operator describing Alice and Bob’s photons and Eve’s probe. The above property implies that:

$$\mathrm{Tr}\left(\text{1}_{\text{Eve}}\underset{P𝒫}{}\mathrm{\Pi }_RF_P\mathrm{\Pi }_R\rho \right)\theta (r)$$

where $`\text{1}_{\text{Eve}}`$ is the identity operator acting on the Hilbert space of the probe. That is,

$$\underset{P𝒫}{}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})\underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}\underset{\begin{array}{c}c_RX_{a_R}:\hfill \\ w(c_R)d_K/2\hfill \end{array}}{}E_\stackrel{}{c}|E_\stackrel{}{c}\theta (r).$$

### 5.4 Quasi-independence of the key and the view

In this section we compute the joint probability distribution of the key and the view. We prove that this distribution is very close to a product of an uniform distribution for the key and the marginal probability distribution of the view.

###### Property 3

For any given eavesdropping strategy chosen by Eve and returning a view $`𝐯`$, the probability distribution of the key $`\stackrel{\mathbf{}}{𝛋}`$ and the view $`𝐯`$ obeys the following inequality:

$$\underset{P𝒫}{}\underset{v𝒱_P}{}\underset{\stackrel{}{\kappa }\{0,1\}^m}{}\left|\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v)\frac{1}{2^m}\mathrm{P}_𝒗(v)\right|2\left(\theta (r)+2\sqrt{\theta (r)}\right)$$

where $`m`$ is the length of the private key and $`r`$ is the size of the reconciled set.

Proof For any $`\stackrel{}{\kappa }\{0,1\}^m`$, $`P`$ and $`v𝒱_P`$, we have:

$`\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v){\displaystyle \frac{1}{2^m}}\mathrm{P}_𝒗(v)`$
$`=`$ $`\mathrm{Tr}(G_{v|P}F_{P,\stackrel{}{\kappa }}\rho ){\displaystyle \frac{1}{2^m}}\mathrm{Tr}(G_{v|P}F_P\rho )`$
$`=`$ $`\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}){\displaystyle \underset{\begin{array}{c}\stackrel{}{c},\stackrel{}{c}^{}:\hfill \\ c_E,c_E^{}Y_{a_E},\hfill \\ c_T,c_T^{}X_{a_T},\hfill \\ c_R,c_R^{}X_{a_R}\hfill \end{array}}{}}E_\stackrel{}{c}^{}|G_{v|P}|E_\stackrel{}{c}\delta _{c_{\overline{R}},c_{\overline{R}}^{}}d_\stackrel{}{\kappa }(\stackrel{}{\gamma },\stackrel{}{\gamma }^{}),`$
where

$$d_\stackrel{}{\kappa }(\stackrel{}{\gamma },\stackrel{}{\gamma }^{})=\underset{\begin{array}{c}\alpha _R\{0,1\}^r:\hfill \\ K\alpha _R=\stackrel{}{\kappa }(mod2)\hfill \end{array}}{}\frac{(1)^{\alpha _R(\stackrel{}{\gamma }+\stackrel{}{\gamma }^{})}}{2^r}\frac{1}{2^m}\delta _{\stackrel{}{\gamma },\stackrel{}{\gamma }^{}}.$$

where we have used the identity $`{}_{a_R,a_R}{}^{}\alpha _R,\alpha _R|c_R=\frac{(1)^{\alpha _R\stackrel{}{\gamma }}}{\sqrt{2}^r}`$ for any $`c_RX_{a_R}`$. We denote by:

* $`𝒢`$ the set of all linear combinations over $`\{0,1\}`$ of rows of $`K`$. It is a vector space of dimension $`m`$.
* $`𝒮`$ a subspace of $`\{0,1\}^r`$ that is supplement to the subspace $`𝒢`$, that is $`𝒢𝒮=\{0,1\}^r`$. The dimension of $`𝒮`$ is $`rm`$.
* $`𝒦`$ the set of all vectors $`\stackrel{}{x}\{0,1\}^r`$ such that $`K\stackrel{}{x}=\stackrel{}{0}(mod2)`$. The set $`𝒦`$ is a vector space of dimension $`rm`$, since the rows of $`K`$ are linearly independent. We will denote by $`\{\stackrel{}{u}_1,\mathrm{},\stackrel{}{u}_{rm}\}`$ a basis of $`𝒦`$.

Given a subspace $`F`$ of $`\{0,1\}^r`$, we denote by $`F^{}`$ the set of all vectors $`\stackrel{}{x}\{0,1\}^r`$ such that for all $`\stackrel{}{y}F`$, $`\stackrel{}{x}\stackrel{}{y}=0(mod2)`$. Remark that $`𝒦^{}=𝒢`$. Since the rows of $`K`$ are linearly independent, for any $`\stackrel{}{\kappa }\{0,1\}^m`$, there exists a vector $`\stackrel{}{\theta }_\stackrel{}{\kappa }\{0,1\}^r`$ such that $`K\stackrel{}{\theta }_\stackrel{}{\kappa }=\stackrel{}{\kappa }(mod2)`$. It follows that $`K\alpha _R=\stackrel{}{\kappa }(mod2)`$ if and only if $`\alpha _R\stackrel{}{\theta }_\stackrel{}{\kappa }+𝒦`$. Thus following the techniques used in ,

$`{\displaystyle \underset{\begin{array}{c}\alpha _R\{0,1\}^r:\hfill \\ K\alpha _R=\stackrel{}{\kappa }(mod2)\hfill \end{array}}{}}(1)^{\alpha _R(\stackrel{}{\gamma }+\stackrel{}{\gamma }^{})}`$ $`=`$ $`{\displaystyle \underset{\alpha _R\stackrel{}{\theta }_\stackrel{}{\kappa }+𝒦}{}}(1)^{\alpha _R(\stackrel{}{\gamma }+\stackrel{}{\gamma }^{})}`$
$`=`$ $`(1)^{\stackrel{}{\theta }_\stackrel{}{\kappa }(\stackrel{}{\gamma }+\stackrel{}{\gamma }^{})}{\displaystyle \underset{i=1}{\overset{rm}{}}}\left[1+(1)^{\stackrel{}{u}_i(\stackrel{}{\gamma }+\stackrel{}{\gamma }^{})}\right]`$
$`=`$ $`\{\begin{array}{cc}(1)^{\stackrel{}{\theta }_\stackrel{}{\kappa }(\stackrel{}{\gamma }+\stackrel{}{\gamma }^{})}2^{rm}\hfill & \text{ if }\stackrel{}{\gamma }+\stackrel{}{\gamma }^{}𝒦^{}=𝒢,\hfill \\ 0\hfill & \text{ if }\stackrel{}{\gamma }+\stackrel{}{\gamma }^{}𝒢.\hfill \end{array}`$
One obtains therefore that:

$$\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v)\frac{1}{2^m}\mathrm{P}_𝒗(v)=\frac{1}{2^m}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})\underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}(U_{v\stackrel{}{\kappa }c_{\overline{R}}}+V_{v\stackrel{}{\kappa }c_{\overline{R}}})^{}\mathrm{\Delta }(U_{v\stackrel{}{\kappa }c_{\overline{R}}}+V_{v\stackrel{}{\kappa }c_{\overline{R}}}),$$

where $`U_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ and $`V_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ are complex vectors of dimension $`2^r`$ and $`\mathrm{\Delta }`$ is a $`2^r\times 2^r`$ complex matrix, whose entries are indexed by $`\stackrel{}{\gamma }\{0,1\}^r`$. The $`\stackrel{}{\gamma }`$-th entry of $`U_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ and $`V_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ are:

$`\left(U_{v\stackrel{}{\kappa }c_{\overline{R}}}\right)_\stackrel{}{\gamma }`$ $`=`$ $`\{\begin{array}{cc}(1)^{\stackrel{}{\theta }_\stackrel{}{\kappa }\stackrel{}{\gamma }}\chi _{v|P}|E_\stackrel{}{c}& \text{ if }w(\stackrel{}{\gamma })<d_K/2,\hfill \\ 0& \text{ if }w(\stackrel{}{\gamma })d_K/2.\hfill \end{array}`$
$`\left(V_{v\stackrel{}{\kappa }c_{\overline{R}}}\right)_\stackrel{}{\gamma }`$ $`=`$ $`\{\begin{array}{cc}0& \text{ if }w(\stackrel{}{\gamma })<d_K/2,\hfill \\ (1)^{\stackrel{}{\theta }_\stackrel{}{\kappa }\stackrel{}{\gamma }}\chi _{v|P}|E_\stackrel{}{c}& \text{ if }w(\stackrel{}{\gamma })d_K/2,\hfill \end{array}`$
where $`\stackrel{}{c}`$ is given by $`c_{\overline{R}}`$, $`a_R`$ and $`\stackrel{}{\gamma }`$. The $`(\stackrel{}{\gamma },\stackrel{}{\gamma }^{})`$-th entry of $`\mathrm{\Delta }`$ is:

$$\left(\mathrm{\Delta }\right)_{\stackrel{}{\gamma },\stackrel{}{\gamma }^{}}=\{\begin{array}{cc}1\hfill & \text{ if }\stackrel{}{\gamma }+\stackrel{}{\gamma }^{}𝒢\{0\},\hfill \\ 0\hfill & \text{ if }\stackrel{}{\gamma }+\stackrel{}{\gamma }^{}𝒢\{0\}.\hfill \end{array}$$

This implies $`U_{v\stackrel{}{\kappa }c_{\overline{R}}}^{}\mathrm{\Delta }U_{v\stackrel{}{\kappa }c_{\overline{R}}}=0`$, since $`w(\stackrel{}{\gamma })<d_K/2`$ and $`w(\stackrel{}{\gamma }^{})<d_K/2`$ imply that $`w(\stackrel{}{\gamma }+\stackrel{}{\gamma }^{})<d_K`$, that is, $`\stackrel{}{\gamma }+\stackrel{}{\gamma }^{}𝒢\{\stackrel{}{0}\}`$.

The matrix $`\mathrm{\Delta }`$ is Hermitian, of eigenvalues $`2^m1`$ and $`1`$. There are $`2^{rm}`$ eigenvectors $`\stackrel{}{v}_\stackrel{}{x}`$ ($`\stackrel{}{x}𝒮`$) associated with the eigenvalue $`2^m1`$. The $`\stackrel{}{\gamma }`$-th entry of $`\stackrel{}{v}_\stackrel{}{x}`$ is:

$$\left(\stackrel{}{v}_\stackrel{}{x}\right)_\stackrel{}{\gamma }=\{\begin{array}{cc}1& \text{ if }\stackrel{}{\gamma }+\stackrel{}{x}𝒢\hfill \\ 0& \text{ if }\stackrel{}{\gamma }+\stackrel{}{x}𝒢.\hfill \end{array}$$

There are $`2^{rm}\left(2^m1\right)`$ eigenvectors $`\stackrel{}{w}_{\stackrel{}{x},\stackrel{}{\sigma }}`$ ($`\stackrel{}{x}𝒮`$, $`\stackrel{}{\sigma }\{0,1\}^m\{\stackrel{}{0}\}`$) associated with the eigenvalue $`1`$. The $`\stackrel{}{\gamma }`$-th entry of $`\stackrel{}{w}_{\stackrel{}{x},\stackrel{}{\sigma }}`$ is:

$$\left(\stackrel{}{w}_{\stackrel{}{x},\stackrel{}{\sigma }}\right)_\stackrel{}{\gamma }=\{\begin{array}{cc}(1)^{\stackrel{}{\omega }_{\stackrel{}{\gamma }+\stackrel{}{x}}\stackrel{}{\sigma }}& \text{ if }\stackrel{}{\gamma }+\stackrel{}{x}𝒢\hfill \\ 0& \text{ if }\stackrel{}{\gamma }+\stackrel{}{x}𝒢.\hfill \end{array}$$

where for any $`\stackrel{}{y}𝒢`$, $`\stackrel{}{\omega }_\stackrel{}{y}`$ is the unique vector in $`\{0,1\}^m`$ such that $`K^T\stackrel{}{\omega }_\stackrel{}{y}=\stackrel{}{y}(mod2)`$. Note that for any $`\stackrel{}{\gamma }\{0,1\}^r`$, there is an unique $`(\stackrel{}{x},\stackrel{}{y})𝒮\times 𝒢`$ such that $`\stackrel{}{\gamma }=\stackrel{}{x}+\stackrel{}{y}`$, and that:

$$\mathrm{𝟏}_\stackrel{}{\gamma }=\frac{1}{2^m}\left(\stackrel{}{v}_x+\underset{\stackrel{}{\sigma }\{0,1\}^m\{\stackrel{}{0}\}}{}(1)^{\stackrel{}{\omega }_\stackrel{}{y}\stackrel{}{\sigma }}\stackrel{}{w}_{\stackrel{}{x},\stackrel{}{\sigma }}\right),$$

where $`\mathrm{𝟏}_\stackrel{}{\gamma }`$ is the canonical vector with entry $`1`$ at position $`\stackrel{}{\gamma }`$ and $`0`$ everywhere else. We can express the vectors $`U_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ and $`V_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ as linear combinations of these eigenvectors:

$`U_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ $`=`$ $`{\displaystyle \underset{\stackrel{}{x}𝒮}{}}(1)^{\stackrel{}{\theta }_\stackrel{}{\kappa }\stackrel{}{x}}\varphi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}\stackrel{}{v}_\stackrel{}{x}+{\displaystyle \underset{\stackrel{}{x}𝒮}{}}{\displaystyle \underset{\stackrel{}{\sigma }\stackrel{}{0}}{}}(1)^{\stackrel{}{\theta }_\stackrel{}{\kappa }\stackrel{}{x}}\varphi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }+\stackrel{}{\sigma }}\stackrel{}{w}_{\stackrel{}{x},\stackrel{}{\sigma }},`$
$`V_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ $`=`$ $`{\displaystyle \underset{\stackrel{}{x}𝒮}{}}(1)^{\stackrel{}{\theta }_\stackrel{}{\kappa }\stackrel{}{x}}\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}\stackrel{}{v}_\stackrel{}{x}+{\displaystyle \underset{\stackrel{}{x}𝒮}{}}{\displaystyle \underset{\stackrel{}{\sigma }\stackrel{}{0}}{}}(1)^{\stackrel{}{\theta }_\stackrel{}{\kappa }\stackrel{}{x}}\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }+\stackrel{}{\sigma }}\stackrel{}{w}_{\stackrel{}{x},\stackrel{}{\sigma }},`$
where for any $`\stackrel{}{z}\{0,1\}^m`$,

$`\varphi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{z}}`$ $`=`$ $`{\displaystyle \underset{\begin{array}{c}\stackrel{}{y}𝒢:\hfill \\ w(\stackrel{}{x}+\stackrel{}{y})<d_K/2\hfill \end{array}}{}}{\displaystyle \frac{(1)^{\stackrel{}{\omega }_\stackrel{}{y}\stackrel{}{z}}}{2^m}}\chi _{v|P}|E_\stackrel{}{c},`$
$`\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{z}}`$ $`=`$ $`{\displaystyle \underset{\begin{array}{c}\stackrel{}{y}𝒢:\hfill \\ w(\stackrel{}{x}+\stackrel{}{y})d_K/2\hfill \end{array}}{}}{\displaystyle \frac{(1)^{\stackrel{}{\omega }_\stackrel{}{y}\stackrel{}{z}}}{2^m}}\chi _{v|P}|E_\stackrel{}{c}.`$
In deriving the above formulae, we used the identity $`\stackrel{}{\theta }_\stackrel{}{\kappa }\stackrel{}{y}=\stackrel{}{\omega }_\stackrel{}{y}\stackrel{}{\kappa }(mod2)`$ for any $`\stackrel{}{y}𝒢`$ and $`\stackrel{}{\kappa }\{0,1\}^m`$. It follows that:

$`V_{v\stackrel{}{\kappa }c_{\overline{R}}}^{}\mathrm{\Delta }V_{v\stackrel{}{\kappa }c_{\overline{R}}}`$ $`=`$ $`{\displaystyle \underset{\stackrel{}{x}𝒮}{}}|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|^2(2^m1)\stackrel{}{v}_\stackrel{}{x}^2{\displaystyle \underset{\begin{array}{c}\stackrel{}{x}𝒮\hfill \\ \stackrel{}{\sigma }\stackrel{}{0}\hfill \end{array}}{}}|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }+\stackrel{}{\sigma }}|^2\stackrel{}{w}_{\stackrel{}{x},\stackrel{}{\sigma }}^2`$
$`=`$ $`2^m\left[(2^m1){\displaystyle \underset{\stackrel{}{x}𝒮}{}}|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|^2{\displaystyle \underset{\begin{array}{c}\stackrel{}{x}𝒮\hfill \\ \stackrel{}{\sigma }\stackrel{}{0}\hfill \end{array}}{}}|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }+\stackrel{}{\sigma }}|^2\right],`$
thus,

$`{\displaystyle \underset{\stackrel{}{\kappa }\{0,1\}^m}{}}\left|V_{v\stackrel{}{\kappa }c_{\overline{R}}}^{}\mathrm{\Delta }V_{v\stackrel{}{\kappa }c_{\overline{R}}}\right|`$
$``$ $`2^m{\displaystyle \underset{\stackrel{}{x}𝒮}{}}\left[(2^m1){\displaystyle \underset{\stackrel{}{\kappa }}{}}|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|^2+{\displaystyle \underset{\stackrel{}{\sigma }\stackrel{}{0},\stackrel{}{\kappa }}{}}|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }+\stackrel{}{\sigma }}|^2\right]`$
$`=`$ $`2^{m+1}(2^m1){\displaystyle \underset{\stackrel{}{x}𝒮}{}}{\displaystyle \underset{\stackrel{}{\kappa }}{}}|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|^2.`$
Similarly, we have,

$$\underset{\stackrel{}{\kappa }\{0,1\}^m}{}\left|U_{v\stackrel{}{\kappa }c_{\overline{R}}}^{}\mathrm{\Delta }V_{v\stackrel{}{\kappa }c_{\overline{R}}}\right|2^{m+1}(2^m1)\underset{\stackrel{}{x}𝒮}{}\underset{\stackrel{}{\kappa }}{}|\varphi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}^{}\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|.$$

Now,

$`{\displaystyle \underset{P𝒫}{}}{\displaystyle \underset{v𝒱_P}{}}{\displaystyle \underset{\stackrel{}{\kappa }\{0,1\}^m}{}}\left|\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v){\displaystyle \frac{1}{2^m}}\mathrm{P}_𝒗(v)\right|`$
$``$ $`{\displaystyle \underset{P𝒫}{}}{\displaystyle \frac{1}{2^m}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}){\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{v𝒱_P}{}}{\displaystyle \underset{\stackrel{}{\kappa }\{0,1\}^m}{}}\left[|V_{v\stackrel{}{\kappa }c_{\overline{R}}}^{}\mathrm{\Delta }V_{v\stackrel{}{\kappa }c_{\overline{R}}}|+2|U_{v\stackrel{}{\kappa }c_{\overline{R}}}^{}\mathrm{\Delta }V_{v\stackrel{}{\kappa }c_{\overline{R}}}|\right]`$
$``$ $`2(2^m1){\displaystyle \underset{P𝒫}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}){\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{v𝒱_P}{}}{\displaystyle \underset{\stackrel{}{x}𝒮}{}}{\displaystyle \underset{\stackrel{}{\kappa }}{}}\left[|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|^2+2|\varphi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}^{}\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|\right]`$
$``$ $`2(2^m1)(\eta +2\sqrt{\eta }\sqrt{\xi }),`$
where we used the Schwartz inequality, and where

$`\eta `$ $`=`$ $`{\displaystyle \underset{P𝒫}{}}{\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{v𝒱_P}{}}{\displaystyle \underset{\stackrel{}{x}𝒮}{}}{\displaystyle \underset{\stackrel{}{\kappa }}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})|\psi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|^2,`$
$`\xi `$ $`=`$ $`{\displaystyle \underset{P𝒫}{}}{\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{v𝒱_P}{}}{\displaystyle \underset{\stackrel{}{x}𝒮}{}}{\displaystyle \underset{\stackrel{}{\kappa }}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d})|\varphi _{v,c_{\overline{R}},\stackrel{}{x},\stackrel{}{\kappa }}|^2.`$
We derive an upper-bound on $`\eta `$ and $`\xi `$. We have:

$`\eta `$ $`=`$ $`{\displaystyle \underset{P𝒫}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}){\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{v𝒱_P}{}}{\displaystyle \underset{\stackrel{}{x}𝒮}{}}{\displaystyle \underset{\begin{array}{c}\stackrel{}{y},\stackrel{}{y}^{}𝒢\hfill \\ w(\stackrel{}{x}+\stackrel{}{y})d_K/2\hfill \\ w(\stackrel{}{x}+\stackrel{}{y}^{})d_K/2\hfill \end{array}}{}}{\displaystyle \underset{\stackrel{}{\kappa }}{}}{\displaystyle \frac{(1)^{\stackrel{}{\omega }_{\stackrel{}{y}+\stackrel{}{y}^{}}\stackrel{}{\kappa }}}{2^{2m}}}E_\stackrel{}{c}^{}|\chi _{v|P}\chi _{v|P}|E_\stackrel{}{c}`$
$`=`$ $`{\displaystyle \frac{1}{2^m}}{\displaystyle \underset{P𝒫}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}){\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{\stackrel{}{x}𝒮}{}}{\displaystyle \underset{\begin{array}{c}\stackrel{}{y}𝒢\hfill \\ w(\stackrel{}{x}+\stackrel{}{y})d_K/2\hfill \end{array}}{}}{\displaystyle \underset{v𝒱_P}{}}E_\stackrel{}{c}|\chi _{v|P}\chi _{v|P}|E_\stackrel{}{c}`$
$`=`$ $`{\displaystyle \frac{1}{2^m}}{\displaystyle \underset{P𝒫}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}){\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{\begin{array}{c}\stackrel{}{x}𝒮,\stackrel{}{y}𝒢\hfill \\ w(\stackrel{}{x}+\stackrel{}{y})d_K/2\hfill \end{array}}{}}E_\stackrel{}{c}|E_\stackrel{}{c}`$
$`=`$ $`{\displaystyle \frac{1}{2^m}}{\displaystyle \underset{P𝒫}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}){\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{\begin{array}{c}c_RX_{a_R}:\hfill \\ w(c_R)d_K/2\hfill \end{array}}{}}E_\stackrel{}{c}|E_\stackrel{}{c}`$
$``$ $`{\displaystyle \frac{1}{2^m}}\theta (r),`$
using the result of the previous section. Similarly,

$`\xi `$ $`=`$ $`{\displaystyle \frac{1}{2^m}}{\displaystyle \underset{P𝒫}{}}\mathrm{P}_\stackrel{\mathbf{}}{𝒂}(\stackrel{}{a})\mathrm{P}_\stackrel{\mathbf{}}{𝒅}(\stackrel{}{d}){\displaystyle \underset{\begin{array}{c}c_{\overline{R}}:\hfill \\ c_EY_{a_E},\hfill \\ c_TX_{a_T}\hfill \end{array}}{}}{\displaystyle \underset{\begin{array}{c}c_RX_{a_R}:\hfill \\ w(c_R)<d_K/2\hfill \end{array}}{}}E_\stackrel{}{c}|E_\stackrel{}{c}`$
$``$ $`{\displaystyle \frac{1}{2^m}}.`$
Consequently,

$`{\displaystyle \underset{P𝒫}{}}{\displaystyle \underset{v𝒱_P}{}}{\displaystyle \underset{\stackrel{}{\kappa }\{0,1\}^m}{}}\left|\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v){\displaystyle \frac{1}{2^m}}\mathrm{P}_𝒗(v)\right|`$
$``$ $`2\left(\theta (r)+2\sqrt{\theta (r)}\right)`$
which concludes our proof.$`\mathrm{}`$

### 5.5 Bound on the conditional entropy

We conclude the proof of privacy by using the following property from classical information theory.

###### Property 4

Let $`𝐱`$ and $`𝐲`$ be two discrete random variables taking values in the sets $`𝒳`$ and $`𝒴`$ respectively. Let $`\mu `$ be a nonnegative real number. If the following inequality is satisfied:

$$\underset{x𝒳,y𝒴}{}\left|\mathrm{P}_{𝒙𝒚}(x,y)\frac{1}{|𝒳|}\mathrm{P}_𝒚(y)\right|\mu ,$$

then the conditional entropy of $`𝐱`$ given $`𝐲`$ is lower-bounded by:

$$H(𝒙|𝒚)(1\mu )\mathrm{log}_2|𝒳|\frac{1}{\mathrm{ln}2}\mu .$$

Proof The hypothesis implies that there exist a set of real numbers $`\eta _{x,y}`$ for all $`x𝒳`$ and $`y𝒴`$ such that:

$$\mathrm{P}_{𝒙𝒚}(x,y)=\frac{1}{|𝒳|}\mathrm{P}_𝒚(y)(1+\eta _{x,y}),$$

($`\eta _{x,y}`$ is assigned the value zero if $`\mathrm{P}_𝒚(y)=0`$) obeying the inequality:

$$\underset{x𝒳,y𝒴}{}\frac{1}{|𝒳|}\mathrm{P}_𝒚(y)|\eta _{x,y}|\mu .$$

Note that for all $`x`$ and $`y`$, we have $`1\eta _{x,y}|𝒳|1`$. Now,

$`H(𝒙|𝒚)`$ $`=`$ $`{\displaystyle \underset{x𝒳,y𝒴:\mathrm{P}_{𝒙𝒚}(x,y)>0}{}}\mathrm{P}_{𝒙𝒚}(x,y)\mathrm{log}_2\mathrm{P}_{𝒙|𝒚=y}(x)`$
$`=`$ $`\mathrm{log}_2|𝒳|{\displaystyle \underset{x𝒳,y𝒴:\eta _{x,y}>1}{}}{\displaystyle \frac{1}{|𝒳|}}\mathrm{P}_𝒚(y)\underset{\frac{|\eta _{x,y}|}{\mathrm{ln}2}}{\underset{}{\mathrm{log}_2(1+\eta _{x,y})}}`$
$`{\displaystyle \underset{x𝒳,y𝒴:\eta _{x,y}>1}{}}{\displaystyle \frac{1}{|𝒳|}}\mathrm{P}_𝒚(y)\eta _{x,y}\mathrm{log}_2\underset{|𝒳|}{\underset{}{(1+\eta _{x,y})}}`$
$``$ $`\mathrm{log}_2|𝒳|{\displaystyle \frac{\mu }{\mathrm{ln}2}}\mu \mathrm{log}_2|𝒳|,`$
which concludes the proof.$`\mathrm{}`$

The probability distribution of the private key and the view obeys the following inequality:

$`{\displaystyle \underset{\begin{array}{c}\stackrel{}{\kappa }\{0,1\}^m,\hfill \\ v𝒱\hfill \end{array}}{}}\left|\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v){\displaystyle \frac{1}{2^m}}\mathrm{P}_𝒗(v)\right|`$
$``$ $`{\displaystyle \underset{P𝒫}{}}{\displaystyle \underset{\begin{array}{c}v𝒱_P,\hfill \\ \stackrel{}{\kappa }\{0,1\}^m\hfill \end{array}}{}}\left|\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v){\displaystyle \frac{\mathrm{P}_𝒗(v)}{2^m}}\right|+{\displaystyle \underset{P𝒫}{}}{\displaystyle \underset{\begin{array}{c}v𝒱_P,\hfill \\ \stackrel{}{\kappa }\{0,1\}^m\hfill \end{array}}{}}\left|\mathrm{P}_{\stackrel{\mathbf{}}{𝜿}𝒗}(\stackrel{}{\kappa },v){\displaystyle \frac{\mathrm{P}_𝒗(v)}{2^m}}\right|`$
$``$ $`2(\theta (r)+2\sqrt{\theta (r)})+0.`$
where we have used the fact that the key is randomly chosen by Alice with uniform probability distribution if the validation test is not passed. Applying the above property for the random variables $`\stackrel{\mathbf{}}{𝜿}`$ and $`𝒗`$, we obtain:

$$H(\stackrel{\mathbf{}}{𝜿}|𝒗)m2\left(m+\frac{1}{\mathrm{ln}2}\right)\left(\theta (r)+2\sqrt{\theta (r)}\right),$$

which concludes the proof of privacy.$`\mathrm{}`$

Acknowledgement  The author gratefully acknowledges support provided by the European TMR Network ERP-4061PL95-1412, and thanks Hans Briegel, Artur Ekert, Nicolas Gisin, Patrick Hayden, Norbert Lütkenhaus, Dominic Mayers, Michele Mosca, Luke Rallan, Peter Shor and Vlatko Vedral for interesting discussions and helpful comments.

## Appendix A Appendix: Error detection and correction

We describe here how we can estimate the error rate in the sifted set $`S`$ and then correct the discrepancies between Alice’s and Bob’s sifted keys using the interactive error-reconciliation scheme .

The error rate in the sifted set can be estimated by comparing a small proportion of the bits chosen randomly in the sifted key. The compared bits should be encrypted with the one-time pad method so that a potential eavesdropper learns only the positions of the errors. A probabilistic property such as the Hoeffding inequality can be used to show that the observed error rate in the sampled proportion is not considerably lower than the error rate in the remaining part of the sifted set . For asymptotic size of the sifted set, one can take arbitrarily small but positive proportion of the sifted key for this error rate estimation.

The remaining part of the sifted set that was not sampled in the previous step must be corrected. One-way linear error-correcting codes can be used for error correction. However, they are not very efficient and considerably higher number of redundant bits are required than the Shannon limit. A practical interactive correction scheme, devised by Brassard and Salvail  gets closer to this theoretical limit. A basic description of the scheme follows:

Alice and Bob group their bits into blocks of a given size, which has to be optimised as a function of the error rate. They exchange information about the parity of each block over the public channel. These parities should be encrypted using the one-time pad method. If their parities agree then they proceed to the next block. If their parities disagree, they deduce that there was an odd number of errors in the corresponding block, and search one of them recursively by cutting the block into two subblocks and comparing the parities of the first subblock: if the parities agree then the second subblock has an odd number of errors and if they do not, then the first subblock has an odd number of errors. Again, these parities should be encrypted. This procedure is continued recursively on the subblock with an odd number of errors. As a result of the encryption of the exchanged parities, a possible eavesdropper learns only the positions of the errors .

After this first step, every considered block has either an even number of errors or none. Alice and Bob then shuffle the positions of their bits and repeat the same procedure with blocks of bigger size (this size being optimised as well). However, when an error is corrected, Alice and Bob might deduce that some blocks treated previously now have an odd number of errors. They choose the smallest block amongst them and correct one error recursively, as before. They proceed until every previously treated block has an even number of errors, or none.

Similar steps follow, and the interactive error correction terminates after a specified number of steps. This number is to be optimised in order to maximise the probability that no discrepancies remain and, at the same time, minimise the number of bits used for the one-time pad encryption. Readers are referred to the original paper  for precise description and treatment of this scheme.