Abstract
We give a security proof of the ‘round-robin differential phase shift’ (RRDPS) quantum key distribution scheme, and we give a tight bound on the required amount of privacy amplification. Our proof consists of the following steps. We construct an EPR variant of the scheme. We show that the RRDPS protocol is equivalent to RRDPS with basis permutation and phase flips performed by Alice and Bob; this causes a symmetrization of Eve’s state. We identify Eve’s optimal way of coupling an ancilla to an EPR qudit pair under the constraint that the bit error rate between Alice and Bob should not exceed a value \(\beta \). As a function of \(\beta \), we derive, for non-asymptotic key size, the trace distance between the real state and a state in which no leakage exists. We invoke post-selection in order to go from qudit-wise attacks to general attacks. For asymptotic key size, we obtain a bound on the trace distance based on the von Neumann entropy. Our asymptotic result for the privacy amplification is sharper than existing bounds. At low qudit dimension, even our non-asymptotic result is sharper than existing asymptotic bounds.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
1.1 Quantum key distribution and the RRDPS scheme
Quantum-physical information processing is different from classical information processing in several remarkable ways. Performing a measurement on an unknown quantum state typically destroys information; it is impossible to clone an unknown state by unitary evolution [1]; quantum entanglement is a form of correlation between subsystems that does not exist in classical physics. Numerous ways have been devised to exploit these quantum properties for security purposes [2]. By far, the most popular and well-studied type of protocol is quantum key distribution (QKD). QKD was first proposed in a famous paper by Bennett and Brassard [3]. Given that Alice and Bob have a way to authenticate classical messages to each other (typically a short key) and that there is a quantum channel from Alice to Bob, QKD allows them to create a random key of arbitrary length about which Eve knows practically nothing. BB84 works with two conjugate bases in a two-dimensional Hilbert space. Many QKD variants have since been described in the literature [4,5,6,7,8,9], using, e.g. different sets of qubit states, EPR pairs, qudits instead of qubits or continuous variables. Furthermore, various proof techniques have been developed [10,11,12,13].
In 2014, Sasaki et al. [14] introduced round-robin differential phase shift (RRDPS), a QKD scheme based on d-dimensional qudits. It has the advantage that it is very noise resilient while being easy to implement using photon pulse trains and interference measurements. One of the interesting aspects of RRDPS is that it is possible to omit the monitoring of signal disturbance. Even at high disturbance, Eve can obtain little information \(I_{\mathrm{AE}}\) about Alice’s secret bit. The value of \(I_{\mathrm{AE}}\) determines how much privacy amplification is needed. As a result of this, the maximum possible QKD rate (the number of actual key bits conveyed per quantum state) is \(1-h(\beta )-I_{\mathrm{AE}}\), where h is the binary entropy function and \(\beta \) the bit error rate.
1.2 Prior work on the security of RRDPS
The security of RRDPS has been discussed in a number of papers [14,15,16,17]. The original RRDPS paper gives an asymptotic upper bound for the privacy amplification,
(Eq. 5 in [14] with photon number set to 1). The security analysis in [14] is based on the Shor–Preskill proof technique [11] and an estimate of the phase error. It is not known how tight the bound (1) is. Ref. [15] follows [14] and does a more accurate computation of phase error rate, tightening the \(1/(d-1)\) in (1) to 1 / d. In [16], Sasaki and Koashi add noise dependence to their analysis and claim a bound
and \(I_{\mathrm{AE}}\le h({\textstyle \frac{1}{d-1}})\) for \(\beta \in [{\textstyle \frac{1}{2}}\cdot {\textstyle \frac{d-2}{d-1}},{\textstyle \frac{1}{2}}]\) (see Sect. 5). The analysis in [17] considers only intercept–resend attacks and hence puts a lower bound on Eve’s potential knowledge, \(I_{\mathrm{AE}}\ge 1-h({\textstyle \frac{1}{2}}+{\textstyle \frac{1}{d}})={{\mathcal {O}}}(1/d^2)\).Footnote 1
1.3 Contributions and outline
In this paper, we give a security proof of RRDPS. We give a bound on the required amount of privacy amplification. We use a proof technique inspired by [11, 13] and [10]. We consider the case where Alice and Bob do monitor the channel (i.e. they are able to tune the amount of privacy amplification (PA) as a function of the observed bit error rate) as well as the saturated regime where the leakage does not depend on the amount of noise.
-
We show that the RRDPS protocol is equivalent to a protocol that contains an additional randomization step by Alice and Bob. The randomization consists of phase flips and a permutation of the basis states. We construct an EPR variant of RRDPS with randomization; it is equivalent to RRDPS if Alice creates the EPR pair and immediately does her measurement. The effect of the randomization is that Alice and Bob’s entangled state after Eve’s attack on the EPR pair is symmetrized and can be described using just three real degrees of freedom.
-
We identify Eve’s optimal way of coupling an ancilla to an EPR qudit pair under the constraint that the bit error rate between Alice and Bob does not exceed some value \(\beta \).
-
We consider an attack where Eve applies the above coupling to each EPR qudit pair individually. We compute an upper bound on the statistical distance (after PA) of the full QKD key from uniformity, conditioned on Eve’s ancilla states. From this, we derive how much privacy amplification is needed. The result does not depend on the way in which Eve uses her ancillas, i.e. she may apply a postponed coherent measurement on the whole system of ancillas.
-
We go from qudit-wise attacks to general attacks by using the post-selection technique. This inflicts a penalty \((d^4-1)\log (n+1)\) on the amount of privacy amplification.
-
We compute the von Neumann mutual information between one ancilla state and Alice’s secret bit. This provides a bound on the PA in the asymptotic (long key) regime [12]. Our result is sharper than [14].
-
We provide a number of additional results by way of supplementary information. (i) We show that Eve’s ancilla coupling can be written as a unitary operation on the Bob–Eve system. This means that the attack can be executed even if Eve has no access to Alice’s qudit; this is important especially in the reduction from the EPR version to the original RRDPS. (ii) We compute the min-entropy of one secret bit given the corresponding ancilla. (iii) We compute the accessible information (mutual Shannon entropy) of one secret bit given the corresponding ancilla. These results give some insight into simple attacks that Eve can launch against individual qudits.
In Sect. 2, we introduce notation and post-selection. In Sect. 3, we briefly summarize the RRDPS scheme and discuss the attacker model. Section 4 states the main result: The amount of privacy amplification needed for RRDPS to be secure, (i) at finite key length and (ii) asymptotically. Section 5 compares our results to previous bounds. The remainder of the paper builds towards the proof of the main results. In Sect. 6, we show that the randomization step does not modify RRDPS and we introduce the EPR version of the protocol. In Sect. 7, we impose the constraint that Eve’s actions must not cause a bit error rate higher than \(\beta \), and determine which mixed states of the Alice–Bob system are still allowed. There are only two scalar degrees of freedom left, which we denote as \(\mu \) and V. In Sect. 8, we do the purification of the Alice–Bob mixed state, thus obtaining an expression for the state of Eve’s ancilla. Although the ancilla space has dimension \(d^2\), we show that only a four-dimensional subspace is relevant for the analysis. In Sect. 9, we prove the non-asymptotic main result by deriving an upper bound on the statistical distance between the distribution of the QKD key and the uniform distribution, conditioned on Eve’s ancillas. In Sect. 10, we prove the asymptotic result by computing Eve’s knowledge in terms of von Neumann entropy. “Appendix” provides supplementary information about the leakage in terms of min-entropy loss and accessible information.
2 Preliminaries
2.1 Notation and terminology
Classical random variables (RVs) are denoted with capital letters and their realizations with lowercase letters. The probability that a RV X takes value x is written as \(\mathrm{Pr}[X=x]\). The expectation with respect to RV X is denoted as \({{\mathbb {E}}}_x f(x)=\sum _{x\in {{\mathcal {X}}}}\mathrm{Pr}[X=x]f(x)\). The constrained sum \(\sum _{t,t':t\ne t'}\) is abbreviated as \(\sum _{[tt']}\) and \({{\mathbb {E}}}_{u,v:u\ne v}\) as \({{\mathbb {E}}}_{[uv]}\). The Shannon entropy of X is written as \(\mathsf{H}(X)\). Sets are denoted in calligraphic font. The notation ‘\(\log \)’ stands for the logarithm with base 2. The min-entropy of \(X\in {{\mathcal {X}}}\) is \(\mathsf{H}_{\mathrm{min}}(X)=-\log \max _{x\in {{\mathcal {X}}}}\mathrm{Pr}[X=x]\), and the conditional min-entropy is \(\mathsf{H}_{\mathrm{min}}(X|Y)=-\log {{\mathbb {E}}}_y \max _{x\in {{\mathcal {X}}}}\mathrm{Pr}[X=x|Y=y]\). The notation h stands for the binary entropy function \(h(p)=p\log {\textstyle \frac{1}{p}}+(1-p)\log {\textstyle \frac{1}{1-p}}\). Bitwise XOR of binary strings is written as ‘\(\oplus \)’. The Kronecker delta is denoted as \(\delta _{ab}\). For quantum states, we use Dirac notation. The notation ‘tr’ stands for trace. The Hermitian conjugate of an operator A is written as \(A^{\dag }\). When A is a complicated expression, we sometimes write \((A+\mathrm{h.c.})\) instead of \(A+A^{\dag }\). The complex conjugate of z is denoted as \(z^*\). We use the positive operator valued measure (POVM) formalism. A POVM \({{\mathcal {M}}}\) consists of positive semidefinite operators, \({{\mathcal {M}}}=(M_x)_{x\in {{\mathcal {X}}}}\), \(M_x\ge 0\), and satisfies the condition \(\sum _x M_x={\mathbb {1}}\). The trace norm of A is \(\Vert A\Vert _1=\mathrm{tr}\,\sqrt{A^{\dag }A}\). The trace distance between matrices \(\rho \) and \(\sigma \) is denoted as \(D(\rho ,\sigma )=\frac{1}{2} \left\| \rho -\sigma \right\| _1\); it is a generalization of the statistical distance and represents the maximum possible advantage one can have in distinguishing \(\rho \) from \(\sigma \). The von Neumann entropy of a mixed state \(\rho \) is denoted as \(S(\rho )\) and equals \(-\mathrm{tr}\,\rho \log \rho \).
Consider a bipartite system ‘XE’ where X is a uniform classical random variable and Eve’s part ‘E’ depends on X. The combined quantum-classical state is \(\rho ^{\mathrm{XE}}={{\mathbb {E}}}_x | x \rangle \langle x |\otimes \rho ^{\mathrm{E}}(x)\). The individual parts are in state \(\rho ^{\mathrm{X}}={{\mathbb {E}}}_x| x \rangle \langle x |\) and \(\rho ^{\mathrm{E}}={{\mathbb {E}}}_x\rho ^{\mathrm{E}}(x)\), respectively. The statistical distance between X and a uniform variable given \(\rho (X)\) is a measure of the security of X given \(\rho \). This distance is given by [18]
i.e. the distance between the true quantum-classical state and a state in which Eve’s part is decoupled from X. If the distance is \(\varepsilon \), then it is said that X is \(\varepsilon \)-secure. Statements like (3) that are stated in terms of statistical distance have the advantage of being universally composable [18]. The term privacy amplification is abbreviated as PA.
2.2 Post-selection
In a collective attack, Eve acts on individual qudits. This is not the most general attack. For protocols that obey permutation symmetry, a post-selection argument [19] can be used to show that \(\varepsilon \)-security against collective attacks implies \(\varepsilon '\)-security against general attacks, with \(\varepsilon '=\varepsilon (n+1)^{d^4-1}\), where d is the dimension of the qudit space. Hence, by paying a price in terms of privacy amplification, e.g. changing the usual privacy amplification term \(2\log {\textstyle \frac{1}{\varepsilon }}\) to \(2\log {\textstyle \frac{1}{\varepsilon }}+2(d^4-1)\log (n+1)\), one can ‘buy’ security against general attacks.
3 The RRDPS scheme
We briefly review the RRDPS scheme [14]. For proof-technical reasons, we explicitly include a channel monitoring procedure (step 4); our proof technique needs this step in the non-saturated regime. Step 4 can be omitted if Alice and Bob decide to perform privacy amplification as if Eve causes 50% noise in every qudit.
3.1 The RRDPS protocol
The dimension of the qudit space is d. The basis statesFootnote 2 are denoted as \(| t \rangle \), with time indices \(t\in \{0,\ldots ,d-1\}\). Whenever we use notation ‘\(t_1+t_2\)’, it should be understood that the addition of time indices is modulo d. The number of qudits is denoted as n. We introduce a system parameter L denoting a list length and system parameters \({\tilde{\beta }}\in [0,{\textstyle \frac{1}{2}}]\), \(\eta \ll 1\) related to the tolerated noise level. The RRDPS scheme consists of the following steps.
-
1.
Alice generates a random bitstring \(a\in \{0,1\} ^d\). She prepares the single-photon state
$$\begin{aligned} | \mu _a \rangle {\mathop {=}\limits ^{\mathrm{def}}}\frac{1}{\sqrt{d}}\sum _{t=0}^{d-1}(-1)^{a_t}| t \rangle \end{aligned}$$(4)and sends it to Bob.
-
2.
Bob chooses a random integer \(r\in \{1,\ldots ,d-1\}\). Bob performs a POVM measurement \({{\mathcal {M}}}^{(r)}\) described by a set of 2d operators \((M^{(r)}_{ks})_{k\in \{0,\ldots ,d-1\},s\in \{0,1\} }\),
$$\begin{aligned} M^{(r)}_{ks} = \frac{1}{2}| {\varPsi }^{(r)}_{ks} \rangle \langle {\varPsi }^{(r)}_{ks} |&\quad \quad \quad | {\varPsi }^{(r)}_{ks} \rangle = \frac{| k \rangle +(-1)^s| k+r \rangle }{\sqrt{2}}. \end{aligned}$$(5)The result of the measurement \({{\mathcal {M}}}^{(r)}\) on \(| \mu _a \rangle \) is an integer \(k\in \{0,\ldots ,d-1\}\) and a bit s which equals \(a_k\oplus a_{k+r}\) if there is no noise/interference.Footnote 3
-
3.
Bob announces k and r over a public but authenticated channel. Alice computes \(s'=a_k\oplus a_{k+r}\). Alice and Bob now have a shared secret bit s.
Steps 1–3 are repeated N times.
-
4.
Alice selects a random subset \({{\mathcal {L}}}\subset [N]\), with \(|{{\mathcal {L}}}|=L\). For the rounds indicated by \({{\mathcal {L}}}\), Alice and Bob publicly compare their values of \(s'\) and s. They continue the protocol only if the number of occurrences \(s\ne s'\) is smaller than \({\tilde{\beta }} L\).
-
5.
Finally, on the remaining \(n=N-L\) bits Alice and Bob carry out the standard procedures of information reconciliation and Privacy Amplification. After PA the size of the key is \(\ell \) bits.
If step 4 is not performed, Alice and Bob have to assume that Eve learns as much as when causing bit error rate \({\textstyle \frac{1}{2}}\). This mode of operation (without monitoring) was proposed in the original RRDPS paper [14].
If Eve causes bit error probability exceeding \(\beta \) (with \(\beta >{\tilde{\beta }}\)), her probability of passing step 4 is exponentially small. Applying the Hoeffding inequality yields an upper bound on the probability of \(\exp [-2L(\beta -{\tilde{\beta }})^2]\). Let \(\eta \ll 1\) be a security parameter. By setting \({\tilde{\beta }}\le \beta -\sqrt{{\textstyle \frac{1}{2L}}\ln {\textstyle \frac{1}{\eta }}}\), we can make sure that an Eve who causes bit error probability exceeding \(\beta \) fails the test except with probability \(\eta \).
In order for \({{\mathcal {L}}}\) to be statistically representative, L needs to be at least of order \(\log \ell \) [20]. We will assume \(L> \log \ell \).
The security of RRDPS is intuitively understood as follows. A measurement in a d-dimensional space cannot extract more than \(\log d\) bits of information. The state \(| \mu _a \rangle \), however, contains \(d-1\) pieces of information, which is a lot more than \(\log d\). Eve can learn only a fraction of the string a embedded in the qudit. Furthermore, what information she has is of limited use, because she cannot force Bob to select specific phases. (i) She cannot force Bob to choose a specific r value. (ii) Even if she feeds Bob a state of the form \(| {\varPsi }^{(r)}_{\ell u} \rangle \), where r accidentally equals Bob’s r, then there is a 50% probability that Bob’s measurement \({{\mathcal {M}}}^{(r)}\) yields \(k\ne \ell \) with random s.
3.2 Attacker model
There is a quantum channel from Alice to Bob. There is an authenticated but non-confidential classical channel between Alice and Bob. We allow Eve to attack individual qudit positions in any way allowed by the laws of quantum physics, e.g. using unbounded quantum memory, entanglement, lossless operations, arbitrary POVMs, arbitrary unitary operators, etc. All bit errors observed by Alice and Bob are assumed to be caused by Eve. Eve cannot influence the random choices of Alice and Bob, nor the state of their (measurement) devices. There are no side channels. This is the standard attacker model for quantum cryptographic schemes.
We will first analyse attacks in which Eve couples an ancilla to each EPR pair individually. Then, we invoke the post-selection method [19] to cover general attacks.
We will see that the leakage becomes constant when \(\beta \) reaches a saturation point. If Alice and Bob are willing to tolerate such a noise level, then channel monitoring is no longer necessary for determining the leakage; they just assume that the maximum possible leakage occurs. (Monitoring is still necessary to determine which error-correcting code should be applied.)
4 Main results
4.1 Non-asymptotic result
Our first result is a non-asymptotic bound on the secrecy of the QKD key z.
Theorem 1
Let \(\mathbf{r}=(r_1,\ldots ,r_n)\) be the values of the parameter r in n rounds of RRDPS and similarly \(\mathbf{k}=(k_1,\ldots ,k_n)\). Let \(z\in \{0,1\} ^\ell \) be the QKD key derived from the n rounds. Let u be the (public) random seed used in the privacy amplification. Let \(\beta \in [0,{\textstyle \frac{1}{2}}]\). Consider a collective attack such that Eve’s probability of causing a bit flip, averaged per qudit, does not exceed \(\beta \). At given \(\mathbf{r},\mathbf{k}\) let \(\rho ^{\mathrm{ZUE}}(\mathbf{r},\mathbf{k})\) denote the quantum-classical state of the variables Z, U and Eve’s subsystem ‘E’, which consists of all n ancillas. The security of Z given R, K, U and Eve’s quantum information can be expressed as
where T is given by
and \(\beta _*\) is a saturation value that depends on d as
where \(x_d\) is the solution on (0, 1) of the equation
The proof is given in Sect. 9, after several sections that prepare the ground. Theorem 1 holds for attacks in which Eve couples an ancilla to each individual EPR pair (though she may later act in any way whatsoever on the whole set of n ancillas). As explained in Sect. 2.2, by a post-selection argument security against qudit-wise attacks implies security against general attacks, but with a less favourable security parameter. In the case of general attacks, we have to multiply the right-hand side of (6) by \((n+1)^{d^4-1}\). Hence, in order to obtain \(\varepsilon \)-security we have to set \(\ell =n(1-2\log T)-(d^4-1)\log (n+1)-2\log {\textstyle \frac{1}{\varepsilon }}+2\).
Let Alice and Bob use an error-correcting code with codeword size n and syndrome size \(\sigma \). The information reconciliation leaks \(\sigma \) bits of information. (Or consumes \(\sigma \) bits of key material, depending on the information reconciliation procedure). It holds that \(\sigma > nh({\tilde{\beta }})\). Asymptotically \({\tilde{\beta }}\rightarrow \beta \) and \(\sigma \rightarrow nh(\beta )\). The QKD key generation rate is \((\ell -\sigma )/N\), where \(N=n+L\) (see Sect. 3.1), with L the number of qubits spent on channel monitoring (if monitoring is performed at all).
The achieved security level is \(\max \{\varepsilon ,\eta \}\), where \(\eta \) is the probability that the number of bit errors is smaller than \({\tilde{\beta }} L\) when Eve causes bit error probability larger than \(\beta \) (see Sect. 3.1).Footnote 4 It is advantageous to set \(\eta =\varepsilon \).
4.2 Asymptotic result
For asymptotically large n, it has been shown [21], using the properties of smooth Rényi entropies, that \( \Vert \rho ^{\mathrm{ZUE}}-\rho ^{\mathrm{Z}}\otimes \rho ^{\mathrm{UE}} \Vert _1 \le \sqrt{2^{ \ell - n (1 - I_{\mathrm{AE}})}}, \) where \(I_{\mathrm{AE}}\) is the single-qudit von Neumann information leakage, \(I_{\mathrm{AE}}{\mathop {=}\limits ^{\mathrm{def}}}S(E)-S(E|S')\). Here, ‘E’ stands for Eve’s ancilla state and \(S'\) is Alice’s secret bit.
Our second result is a computation of the von Neumann leakage \(I_{\mathrm{AE}}\) for RRDPS.
Theorem 2
The information leakage about the secret bit S’ given R, K and Eve’s quantum state, in terms of von Neumann entropy, is given by:
Here, \(\beta _0\) is a saturation value (different from \(\beta _*\)) given by
where \(y_d\) is the unique positive root of the polynomial \(y^{d-1}+y-1\).
The proof is given in Sect. 10. The formulation of our main results in terms of statistical distance ensures that the results are universally composable. In Sect. 10, we will see that Theorem 2 is sharper than (2) and hence allows for a higher QKD key generation rate.
5 Comparison with previous analyses
5.1 Phase error
Sasaki and Koashi [16] provided an upper bound on the PA equal to \(h(e^{\mathrm{ph}})\), where \(e^{\mathrm{ph}}\) is the phase error rate. They derived a relation between the phase error rate and the bit error rate, \(e^{\mathrm{ph}}\le \inf _{\lambda \ge 0}[\lambda \beta +\max \{{\varOmega }_-(\nu ,\lambda ),{\varOmega }_+(\nu ,\lambda ) \}]\), where \(\nu \) is the photon number and \({\varOmega }_\pm \) are functions which for \(\nu =1\) reduce to \({\varOmega }_-(1,\lambda )=0\) and \({\varOmega }_+(1,\lambda )={\textstyle \frac{1}{d-1}}-\lambda {\textstyle \frac{d-2}{2(d-1)}}\). At \(\nu =1\) the optimal \(\lambda \) is \({\textstyle \frac{2}{d-2}}\), yielding \(e^{\mathrm{ph}}\le {\textstyle \frac{2\beta }{d-2}}\) and thus an upper bound of \(h({\textstyle \frac{2\beta }{d-2}})\) on the PA.
5.2 Comparison
We first compare our asymptotic result (Theorem 2) to the asymptotic \(h({\textstyle \frac{2\beta }{d-2}})\) of [16]. For all \(\beta \in [0,\beta _0]\) and \(d>2\), it holds that
This is verified as follows. Let \(p_0=2\beta \), \(p_1=1-2\beta \), \(x_0=0\), \(x_1={\textstyle \frac{2\beta }{(d-2)(1-2\beta )}}\). The left-hand side of (16) can be expressed as \(p_0 h(x_0)+p_1 h(x_1)\) and the right-hand side as \(h(p_0 x_0 + p_1 x_1)\). Because h is concave, we have \({{\mathbb {E}}}h(\cdots )\le h({{\mathbb {E}}}\cdots )\).
Thus, our von Neumann result is sharper than [16]. It is difficult to pinpoint what causes the difference in tightness.
Note too that our saturation occurs at lower \(\beta \) than in [16], especially for small d.
Our Theorem 1 is non-asymptotic; we cannot compare it to previous results since the previous results are for the asymptotic regime.
Figures 1 and 2 show plots of the PA per qudit. In Fig. 1, the post-selection ‘price’ proportional to \(d^4{\textstyle \frac{\log n}{n}}\) is clearly visible; for large d, the cost is prohibitive. Interestingly, at small d our non-asymptotic result for the saturated PA is sharper than the asymptotic \(h({\textstyle \frac{1}{d-1}})\) [14, 16].
6 Symmetrized EPR version of the protocol
6.1 RRDPS is equivalent to RRDPS with random permutations
We show that inserting a symmetrization step into RRDPS does not affect the protocol. More specifically, the following protocol is equivalent to RRDPS steps 1 to 3. (For brevity, we do not explicitly write down the channel monitoring, information reconciliation and privacy amplification.)
- S1 :
-
Alice picks a random \(a\in \{0,1\} ^d\) and a random permutation \(\pi \).
She prepares \(| \mu _a \rangle ={\textstyle \frac{1}{\sqrt{d}}}\sum _t (-1)^{a_t}| t \rangle \).
- S2 :
-
Alice performs the permutation \(\pi \) on the state \(| \mu _a \rangle \). She sends the result to Bob. After pausing for a while, she sends \(\pi \) to Bob.
- S3 :
-
Eve does something with the state, without knowing \(\pi \). Then, she sends the result to Bob.
- S4 :
-
Bob receives a state and stores it until he receives \(\pi \). Bob applies \(\pi ^{-1}\) to the state.
- S5 :
-
Bob picks a random \(r\in \{1,\ldots ,d-1\}\) and does the \({{\mathcal {M}}}^{(r)}\) POVM. The result is an index \(k\in \{0,\ldots ,d-1\}\) and a bit \(s=a_k\oplus a_{k+r}\). He computes \(\ell =k+r\;\mathrm{mod}\;d\). He announces \(k,\ell \).
- S6 :
-
Alice computes \(s'=a_k\oplus a_\ell \).
The equivalence is shown as follows. After step S2, the state is \({\textstyle \frac{1}{\sqrt{d}}}\sum _t (-1)^{a_t}| \pi (t) \rangle ={\textstyle \frac{1}{\sqrt{d}}}\sum _\tau (-1)^{a_{\pi ^{-1}\tau }}| \tau \rangle \) \(=| \mu _{\pi ^{-1}(a)} \rangle \). Hence, Alice’s process {state preparation followed by \(\pi \)} can be replaced by {acting with \(\pi ^{-1}\) on a followed by state preparation}. Similarly, Bob’s process {apply \(\pi ^{-1}\) to state; pick random r; do \({{\mathcal {M}}}^{(r)}\); send \(k,\ell \)} has exactly the same effect as {pick random r; do \({{\mathcal {M}}}^{(r)}\); apply \(\pi \) to k, l; send \(\pi (k),\pi (\ell )\)}. Next, Bob’s computation of \(\pi (k),\pi (\ell )\) can be moved to Alice. Then, Alice’s actions {pick random a; send \(\pi ^{-1}(a)\) to state preparation; send a to step S6} can be replaced by {pick random \(a'\); send \(a'\) to state preparation; send \(\pi (a)\) to step S6}. Finally, in step S6 we use \(\pi (a)_{\pi (k)}=a_k\) and \(\pi (a)_{\pi (\ell )}=a_\ell \).
Remark
In step S3, it is crucial that Eve does not know \(\pi \) at the moment of her manipulation of the state. This will allow us to derive a symmetrized form of the density matrix in Sect. 6.3.
6.2 RRDPS is equivalent to RRDPS with random phase flips
Analogous with Sect. 6.1, it can be seen that adding an extra phase-flipping step to RRDPS does not affect RRDPS. Consider the following protocol.
- F1 :
-
Alice picks a random \(a\in \{0,1\} ^d\) and a random \(c\in \{0,1\} ^d\). She prepares \(| \mu _a \rangle ={\textstyle \frac{1}{\sqrt{d}}}\sum _t (-1)^{a_t}| t \rangle \).
- F2 :
-
Alice performs the phase flips on the state \(| \mu _a \rangle \), according to the rule \(| t \rangle \rightarrow (-1)^{c_t}| t \rangle \) for basis states. She sends the result to Bob. After pausing for a while, she sends c to Bob.
- F3 :
-
Eve does something with the state, without knowing c. Then, she sends the result to Bob.
- F4 :
-
Bob receives a state and stores it until he receives c. Bob applies phase flips c to the state.
- F5 :
-
Bob picks a random \(r\in \{1,\ldots ,d-1\}\) and does the \({{\mathcal {M}}}^{(r)}\) POVM. The result is an index \(k\in \{0,\ldots ,d-1\}\) and a bit \(s=a_k\oplus a_{k+r}\). He computes \(\ell =k+r\;\mathrm{mod}\;d\). He announces \(k,\ell \).
- F6 :
-
Alice computes \(s'=a_k\oplus a_\ell \).
The equivalence to RRDPS is seen as follows. After step F2, the state is \(| \mu _{a\oplus c} \rangle \). Hence, Alice’s process {pick random a; prepare state; flip with c} is equivalent to {pick random a; flip with c; prepare state}. Similarly, Bob’s process {flip with c; pick random r; do \({{\mathcal {M}}}^{(r)}\)} is equivalent to {pick random r; do \({{\mathcal {M}}}^{(r)}\); change s to \(s\oplus c_k\oplus c_\ell \) }. This holds because in the first case Bob obtains \(s=(a\oplus c)_k\oplus (a\oplus c)_\ell =(a_k\oplus a_\ell )\oplus c_k\oplus c_\ell \). Furthermore, Alice’s steps {pick random a; send a to computation of \(s'\) and flipped a to state preparation} are equivalent to {pick random \(a'\); send flipped a to computation of \(s'\) and \(a'\) to state preparation}. The final effect of these transformations of the ‘F’ protocol is that (i) there is no physical phase flipping at all, (ii) Bob needs no quantum memory and (iii) Alice and Bob both obtain a secret bit \((a_k\oplus a_\ell )\oplus c_k\oplus c_\ell \); though not equal to \(a_k\oplus a_\ell \), it is statistically the same.
6.3 EPR version
We introduce a protocol based on EPR pairs that is equivalent to the combined ‘S’ and ‘F’ protocols and hence also equivalent to RRDPS.
- E1 :
-
A maximally entangled two-qudit state is prepared.
$$\begin{aligned} | \alpha _0 \rangle {\mathop {=}\limits ^{\mathrm{def}}}\frac{1}{\sqrt{d}}\sum _{t=0}^{d-1}| tt \rangle . \end{aligned}$$(17)One qudit (‘A’) is intended for Alice and one (‘B’) for Bob.
- E2 :
-
Eve does something with the EPR pair. Then, Alice and Bob each receive their own qudit.
- E3 :
-
Alice and Bob pick a random permutation \(\pi \). They both apply \(\pi \) to their own qudit. Then, they forget \(\pi \).
- E4 :
-
Alice and Bob pick a random string \(c\in \{0,1\} ^d\). They both apply phase flips \(| t \rangle \rightarrow (-1)^{c_t}| t \rangle \) to their own qudit. Then, they forget c.
- E5 :
-
Alice performs a POVM \({{\mathcal {Q}}}=(Q_z)_{z\in \{0,1\} ^d}\) on her own qudit, where
$$\begin{aligned} Q_z=\frac{d}{2^d}| \mu _z \rangle \langle \mu _z |. \end{aligned}$$(18)This results in a measured string \(a\in \{0,1\} ^d\).
- E6 :
-
Bob picks a random integer \(r\in \{1,\ldots ,d-1\}\) and performs the POVM measurement \({{\mathcal {M}}}^{(r)}\) on his qudit. The result of the measurement is an integer \(k\in \{0,\ldots ,d-1\}\) and a bit s. Bob computes \(\ell =k+r\;\mathrm{mod}\;d\). Bob announces \(k,\ell \).
- E7 :
-
Alice computes \(s'=a_k\oplus a_\ell \).
The equivalence to the protocol in Sect. 6.1 is seen as follows. First, let Alice be the origin of the EPR pair, and let her perform \({{\mathcal {Q}}}\) as soon as she has created the EPR pair. This process is equivalent to preparing a qudit state \(| \mu _a \rangle \) with random a. The only difference is that the EPR protocol allows Eve to couple her ancilla to the AB system instead of only the B system. Hence, the EPR version overestimates Eve’s power. Security of the EPR version implies security of the original RRDPS.Footnote 5 Furthermore, the permutations and phase flips in steps E3,E4 cancel out exactly like in protocols ‘S’ and ‘F’.
Remark
The protocol equivalences in Sects. 6.1–6.3 can be nicely visualized using diagrammatic techniques [22]. We do not show the protocol diagrams in this paper.
Lemma 1
The hermitian matrices \(Q_z\) as defined in (18) form a POVM, i.e. \(\sum _{z\in \{0,1\} ^d}Q_z={\mathbb {1}}\).
Proof
\(\sum _z| \mu _z \rangle \langle \mu _z |=\) \(\sum _z{\textstyle \frac{1}{d}}\sum _{t,t'=0}^{d-1}(-1)^{z_{t'}+z_{t}}| t \rangle \langle t' |={\textstyle \frac{1}{d}}\sum _{t,t'=0}^{d-1}| t \rangle \langle t' |\sum _z(-1)^{z_{t'}+z_t}\).
Using \(\sum _z(-1)^{z_{t'}+z_t}=2^d\delta _{tt'}\), we get \(\sum _z| \mu _z \rangle \langle \mu _z |={\textstyle \frac{2^d}{d}}\sum _t| t \rangle \langle t |={\textstyle \frac{2^d}{d}}{\mathbb {1}}\). \(\square \)
Alice and Bob’s measurements can be carried out in the opposite order. It is not important whether \({{\mathcal {Q}}}\) is practical or not; it is a theoretical construct which allows us to build an EPR version of RRDPS.
6.4 Effect of the random transforms: state symmetrization
Let \(\rho ^{\mathrm{AB}}=| \alpha _0 \rangle \langle \alpha _0 |\) denote the pure EPR state of Alice and Bob, and let \({\hat{\rho }}^\mathrm{AB}\) be the mixed state of the AB system after Eve’s manipulation in step E2. We write
with \({\hat{\rho }}^{\tau \tau '}_{tt'}=({\hat{\rho }}^{tt'}_{\tau \tau '})^*\) and \(\sum _{tt'}{\hat{\rho }}^{tt'}_{tt'}=1\). The effect of step E3 is that the AB state gets averaged over all permutations, i.e. we get the following mapping
Here, the parameters \({\tilde{\rho }}^{tt'}_{\tau \tau '}\) are invariant under simultaneous permutation of the four indices, i.e. \({\tilde{\rho }}^{\pi (t),\pi (t')}_{\pi (\tau ),\pi (\tau ')}={\tilde{\rho }}^{tt'}_{\tau \tau '}\) for all \(\pi \),t,\(t'\),\(\tau \),\(\tau '\). The consequence is that \({\tilde{\rho }}^{\mathrm{AB}}\) contains only a few degrees of freedom, namely the constants \({\tilde{\rho }}^{ss}_{ss}\), \({\tilde{\rho }}^{ss}_{st}\), \({\tilde{\rho }}^{ss}_{ts}\), \({\tilde{\rho }}^{ss}_{tt}\), \({\tilde{\rho }}^{st}_{st}\), \({\tilde{\rho }}^{st}_{ts}\), \({\tilde{\rho }}^{ss}_{tu}\), \({\tilde{\rho }}^{st}_{su}\), \({\tilde{\rho }}^{ts}_{us}\), \({\tilde{\rho }}^{st}_{us}\), \({\tilde{\rho }}^{st}_{uv}\), where s, t, u, v are mutually distinct.
Next, the random phase flips reduce the degrees of freedom even further. Let \(F_c\) be the phase flip operator.
From (24), we see that any time index that occurs an odd number of times will be wiped out, i.e. \({{\mathbb {E}}}_c (-1)^{c_t}=0\). The only surviving degrees of freedom are the four constants \({\bar{\rho }}^{\bullet \bullet }_{\bullet \bullet }\), \({\bar{\rho }}^{\bullet \bullet }_{\circ \circ }\), \({\bar{\rho }}^{\bullet \circ }_{\bullet \circ }\), \({\bar{\rho }}^{\bullet \circ }_{\circ \bullet }\), where \(\bullet \) and \(\circ \) denote distinct arbitrary indices. Note that these constants are real-valued. We can now write
Furthermore, the requirement \(\mathrm{tr}\,{\bar{\rho }}^{\mathrm{AB}}=1\) imposes the constraint \(d{\bar{\rho }}^{\bullet \bullet }_{\bullet \bullet }+d(d-1){\bar{\rho }}^{\bullet \circ }_{\bullet \circ }=1\), reducing the number of degrees of freedom to three.
7 Imposing the noise constraint
The channel monitoring restricts the ways in which Eve can alter the AB state. We will determine the most general allowed \({\bar{\rho }}^{\mathrm{AB}}\) that is compatible with bit error rate \(\beta \). (We will later see that it is optimal for Eve to cause the same bit error rate in all rounds. This is due to the concavity of the leakage as a function of the error rate.) We introduce the notation \(P_{aks|r}=\mathrm{Pr}[A=a,K=k,S=s|R=r]\).
Lemma 2
Let Alice and Bob’s bipartite state be \({\bar{\rho }}^{\mathrm{AB}}\), and let them perform the measurements \({{\mathcal {Q}}}\) and \({{\mathcal {M}}}^{(r)}\) respectively. At given r, the joint probability of the outcomes a, k, s is given by
Proof
\(P_{aks|r}=\mathrm{tr}\,(Q_a\otimes M^{(r)}_{ks}){\bar{\rho }}^{\mathrm{AB}}=\mathrm{tr}\,({\textstyle \frac{1}{2^d}}\sum _{\ell \ell '}(-1)^{a_\ell +a_{\ell '}}| \ell \rangle \langle \ell ' |\otimes \frac{1}{2}\frac{| k \rangle +(-1)^s| k+r \rangle }{\sqrt{2}} \frac{\langle k |+(-1)^s\langle k+r |}{\sqrt{2}}) \sum _{tt'\tau \tau '}{\bar{\rho }}^{tt'}_{\tau \tau '}| t \rangle \langle \tau |\otimes | t' \rangle \langle \tau ' |=\frac{1}{2^d 4}\sum _{tt'\tau \tau '}{\bar{\rho }}^{tt'}_{\tau \tau '}(-1)^{a_t+a_\tau } [\delta _{t'k}+(-1)^s \delta _{t',k+r}] [\delta _{\tau 'k}+(-1)^s \delta _{\tau ',k+r}]=\frac{1}{2^d 4}\sum _{t\tau }(-1)^{a_t+a_\tau }[{\bar{\rho }}^{tk}_{\tau k}+{\bar{\rho }}^{t,k+r}_{\tau ,k+r} +(-1)^s {\bar{\rho }}^{tk}_{\tau ,k+r}+(-1)^s {\bar{\rho }}^{t,k+r}_{\tau k}]\). We use \({\bar{\rho }}^{t\ell }_{\tau \ell }=\delta _{t\ell }\delta _{\tau \ell }{\bar{\rho }}^{\bullet \bullet }_{\bullet \bullet }\) \(+\delta _{\tau t}(1-\delta _{t\ell }){\bar{\rho }}^{\bullet \circ }_{\bullet \circ }\) for the first two terms, setting \(\ell =k\) and \(\ell =k+r\). Since \(k+r\ne k\) we write \({\bar{\rho }}^{tk}_{\tau ,k+r}=\delta _{tk}\delta _{\tau ,k+r}{\bar{\rho }}^{\bullet \bullet }_{\circ \circ } +\delta _{t,k+r}\delta _{\tau k}{\bar{\rho }}^{\bullet \circ }_{\circ \bullet }\), and similarly for \({\bar{\rho }}^{t,k+r}_{\tau k}\). Finally, we use \({\bar{\rho }}^{\bullet \bullet }_{\bullet \bullet }+(d-1){\bar{\rho }}^{\bullet \circ }_{\bullet \circ }=1/d\). (See end of Sect. 6.4.) \(\square \)
We now impose the constraint that a bit error occurs with probability \(\beta \),
Here, the random variables are A, R, K, and S.
Theorem 3
The constraint (28) can only be satisfied by a density function of the form
with \(\mu ,V\in {{\mathbb {R}}}\). Written componentwise,
Proof
We write \(\mathrm{Pr}[S= A_K\oplus A_{K+R}]=\sum _{akrs}{\textstyle \frac{1}{d-1}}P_{aks|r}\delta _{s,a_k\oplus a_{k+r}}\) and use Lemma 2. This yields \(\mathrm{Pr}[S= A_K\oplus A_{K+R}]={\textstyle \frac{1}{2}}+{\textstyle \frac{d}{2}}({\bar{\rho }}^{\bullet \bullet }_{\circ \circ }+{\bar{\rho }}^{\bullet \circ }_{\circ \bullet })\). The constraint (28) can only be satisfied by setting \({\bar{\rho }}^{\bullet \bullet }_{\circ \circ }+{\bar{\rho }}^{\bullet \circ }_{\circ \bullet }={\textstyle \frac{1-2\beta }{d}}\). We choose \({\bar{\rho }}^{\bullet \bullet }_{\circ \circ }, {\bar{\rho }}^{\bullet \circ }_{\bullet \circ }\) as the two independent degrees of freedom and re-parametrize them as \({\bar{\rho }}^{\bullet \bullet }_{\circ \circ }=(1-2\beta -V)/d\) and \({\bar{\rho }}^{\bullet \circ }_{\bullet \circ }=(2\beta -\mu )/d^2\), where \(\mu ,V\in {{\mathbb {R}}}\) are the new independent degrees of freedom. Substitution into (26) yields (29). \(\square \)
Theorem 3 shows that (at fixed \(\beta \)) there are still two degrees of freedom, \(\mu \) and V, in Eve’s manipulation of the EPR pair. This differs from standard qubit-wise QKD, where the bit error probability completely fixes Eve’s ancilla state.
8 Purification
According to the attacker model, we have to assume that Eve has the purification of the state \({\bar{\rho }}^{\mathrm{AB}}\). The purification contains all information about s that exists outside the AB system.
8.1 The purified state and its properties
We introduce the following notation,
Lemma 3
The \({\bar{\rho }}^{\mathrm{AB}}\) given in (29) has the following orthonormal eigensystem,
Proof
The term proportional to \({\mathbb {1}}\) in (29) yields a contribution \((2\beta -\mu )/d^2\) to each eigenvalue. First, we look at \(| \alpha _j \rangle \). We have \(\langle \alpha _0 | \alpha _j \rangle =\delta _{j0}\). Furthermore, \(\langle t't | \alpha _j \rangle =\delta _{t't}e^{i\frac{2\pi }{d}jt}/\sqrt{d}\), which gives \((\sum _{tt'}| tt' \rangle \langle t't |)| \alpha _j \rangle =| \alpha _j \rangle \). Similarly we have \((\sum _{t}| tt \rangle \langle tt |)| \alpha _j \rangle =| \alpha _j \rangle \). Next we look at \(| D^\pm _{tt'} \rangle \). We have \(\langle \alpha _0 | D^\pm _{tt'} \rangle =0\) and \(\langle uu | D^\pm _{tt'} \rangle =0\). Hence, the \((1-2\beta -V)\)-term and the \(\mu \)-term in (29) yield zero when acting on \(| D^\pm _{tt'} \rangle \). Furthermore, \(\sum _{uu'}| uu' \rangle \langle u'u | D^+_{tt'} \rangle \) \(=\sum _{uu'}| uu' \rangle \frac{\delta _{ut}\delta _{u't'}+\delta _{ut'}\delta _{u't}}{\sqrt{2}}\) \(=| D^+_{tt'} \rangle \). Similarly, \(\sum _{uu'}| uu' \rangle \langle u'u | D^-_{tt'} \rangle \) \(=\sum _{uu'}| uu' \rangle \frac{\delta _{ut}\delta _{u't'}-\delta _{ut'}\delta _{u't}}{\sqrt{2}}\mathrm{sgn}(u-u')\) \(=-| D^-_{tt'} \rangle \). \(\square \)
In diagonalized form, the \({\bar{\rho }}^{\mathrm{AB}}\) is given by
The purification is
where we have introduced orthonormal basis states \(| E_j \rangle \), \(| E_{tt'}^\pm \rangle \) in Eve’s Hilbert space. In “Appendix A”, we give more details on Eve’s unitary operation.
8.2 Eve’s state
Eve waits for Alice and Bob to perform their measurements and reveal k and r.
Lemma 4
After Alice has measured \(a\in \{0,1\} ^d\) and Bob has measured \(k\in \{0,\ldots ,d-1\}\), \(s\in \{0,1\} \), Eve’s state is given by
Proof
The POVM elements \(Q_a\) and \(M^{(r)}_{ks}\) are proportional to projection operators. Hence, the tripartite ABE pure state after the measurement is proportional to \((Q_a\otimes M^{(r)}_{ks}\otimes {\mathbb {1}})| {\varPsi }^{\mathrm{ABE}} \rangle \). It is easily verified that the normalization in (36) is correct: taking the trace in E-space yields \(\mathrm{tr}\,_\mathrm{AB}\mathrm{tr}\,_\mathrm{E}| {\varPsi }^{\mathrm{ABE}} \rangle \langle {\varPsi }^{\mathrm{ABE}} | Q_a\otimes M^{(r)}_{ks}\otimes {\mathbb {1}}\) \(=\mathrm{tr}\,_\mathrm{AB}\;{\bar{\rho }}^{\mathrm{AB}}Q_a\otimes M^{(r)}_{ks}\) \(=P_{aks|r}\). \(\square \)
Lemma 5
It holds that
Proof
We have \(| \mu _a \rangle \langle \mu _a |=\frac{1}{d}{\mathbb {1}}+\frac{1}{d}\sum _{[t\tau ]}| t \rangle \langle \tau |(-1)^{a_t+a_\tau }\). Summation of the \({\textstyle \frac{1}{d}}{\mathbb {1}}\) term is trivial and yields \(2^{d-2}\cdot \frac{1}{d}{\mathbb {1}}\). In the summation of the factor \((-1)^{a_t+a_\tau }\) in the second term, any summation \(\sum _{a_t}(-1)^{a_t}\) yields zero. The only nonzero contribution arises when \(t=k,\tau =k+r\) or \(t=k+r,\tau =k\); the a-summation then yields a factor \(2^{d-2}\). \(\square \)
Lemma 6
It holds that
Proof
We have \({{\mathbb {E}}}_{a:a_k\oplus a_{k+r}=s'}| \mu _a \rangle \langle \mu _a | =2^{-(d-1)}\sum _{a_k}\sum _{a_{k+r}}\delta _{a_k\oplus a_{k+r},s'}\cdot \sum _{a\,\mathrm{without}\,a_k,a_{k+r}}| \mu _a \rangle \langle \mu _a |\). For the rightmost summation, we use Lemma 5. Performing the \(\sum _{a_k}\) and \(\sum _{a_{k+r}}\) summations yields (39). \(\square \)
Eve’s task is to guess Alice’s bit \(s'=a_k\oplus a_{k+r}\) from the mixed state \(\sigma ^{rk}_{as}\), where Eve does not know a and s. We define
This represents Eve’s ancilla state given some value of Alice’s bit \(s'\). Next we introduce notations that are useful for understanding the structure of \(\sigma ^{rk}_{s'}\). We define, for \(t,t'\in \{0,\ldots ,d-1\}\), non-normalized vectors \(| w_{tt'} \rangle \) in Eve’s Hilbert space as
Furthermore, we define angles \(\alpha \) and \(\varphi \) as
and vectors \(| A \rangle , | B \rangle , | C \rangle , | D \rangle \)
The \(| A \rangle \), \(| B \rangle \), \(| C \rangle \), \(| D \rangle \) are mutually orthogonal and also orthogonal to any vector \(| w_{tt'} \rangle \) (\(t'\ne t\)) with \(\{t,t'\}\ne \{k,k+r\}\).
Theorem 4
The eigenvalues of \(\sigma ^{rk}_{s'}\) are given by
and the diagonal representation of \(\sigma ^{rk}_{s'}\) is
Proof
We have
We use Lemma 6 to evaluate the \({{\mathbb {E}}}_a\) factor. We use \(\sum _s M^{(r)}_{ks}={\textstyle \frac{1}{2}}| k \rangle \langle k |+{\textstyle \frac{1}{2}}| k+r \rangle \langle k+r |\). This allows us to write everything in terms of \(| w_{tt'} \rangle \) states. For \(t=t'\), we have
and for \(t\ne t'\), we have
The following properties hold (\(t\ne t'\))
We get
After some tedious algebra, the result (50) follows. \(\square \)
Note that the \(\sigma ^{rk}_0\) and \(\sigma ^{rk}_1\) have the same set of eigenvalues: \(2(d-2)\) times \(\xi _0\), and once \(\xi _1\) and \(\xi _2\).
Corollary 1
It holds that
Proof
It follows directly from Theorem 4 by discarding the terms in (50) that contain \((-1)^{s'}\) (the AC and BD crossterms). \(\square \)
Corollary 2
The difference between \(\sigma ^{rk}_0\) and \(\sigma ^{rk}_1\) can be written as
Proof
Using Theorem 4, we see everything except the AC and BD crossterms cancel from (50). \(\square \)
9 Statistical distance; proof of Theorem 1
Now that we have described Eve’s most general allowed state and how it is connected to Alice’s secret bit \(s'\), it is finally time to prove Theorem 1.
Let \(r_i\) be the ‘r’-value in round i and similarly \(k_i\), \(s_i'\). We use the notation \(\mathbf{r}=(r_1,\ldots ,r_n)\), \(\mathbf{k}=(k_1,\ldots ,k_n)\). Let \(x=(s_1',\ldots ,s_n')\). Let \(z\in \{0,1\} ^\ell \) be the QKD key obtained by applying privacy amplification to x, i.e. \(z=\texttt {Ext}(x,u)\), where \(\texttt {Ext}\) is a universal hash function (UHF) and \(u\in {{\mathcal {U}}}\) is public randomness. We write \({{\mathbb {E}}}_u[\cdots ]={\textstyle \frac{1}{|{{\mathcal {U}}}|}}\sum _u(\cdots )\) and \({{\mathbb {E}}}_x[\cdots ]=2^{-n}\sum _{x\in \{0,1\} ^n}(\cdots )\). At given \((\mathbf{r},\mathbf{k})\), the quantum-classical state describing Z, U and Eve’s system ‘E’ is given by
The state of the ‘Z’ and ‘UE’ subsystems is
Note that \(\omega _{\mathrm{av}}\) does not depend on u. For notational brevity, we stop explicitly mentioning the r,k dependence from this point on. From (60)–(62), we get
Because of the zu block structure, we have
Lemma 7
It holds that
Proof
\(2^{-\ell }\sum _z{{\mathbb {E}}}_{u}\Vert {\varDelta }_{zu} \Vert _1=2^{-\ell }\sum _z{{\mathbb {E}}}_{u}\mathrm{tr}\,\sqrt{{\varDelta }_{zu}^2}\) \(=\mathrm{tr}\,2^{-\ell }\sum _z{{\mathbb {E}}}_{u}\sqrt{{\varDelta }_{zu}^2}\). We apply Jensen’s inequality for operator concave functions. \(\square \)
Lemma 8
It holds that
Proof
From the definition of \({\varDelta }_{zu}\) and \(\omega _{\mathrm{av}}\), we get
We split the \(\sum _{xy}\) sum into a sum with \(y=x\) and a sum with \(y\ne x\). Then we use \(\sum _z \delta _{z,\texttt {Ext}(x,u)}=1\) and \(\sum _z {{\mathbb {E}}}_u\delta _{z,\texttt {Ext}(x,u)}\delta _{z,\texttt {Ext}(y,u)}=2^{-\ell }\) for \(y\ne x\). The latter is the defining property of UHFs. Then, we rewrite \(\sum _{xy:\,y\ne x}\) as \(\sum _{xy}-\sum _{xy}\delta _{xy}\). Finally, after applying \(2^{-n}\sum _x\bigotimes _i \sigma ^{r_i k_i}_{x_i}=\omega _{\mathrm{av}}\), most of the terms cancel and (68) is what remains. \(\square \)
Lemma 9
It holds that
with \(\xi _0,\xi _1,\xi _2\) as defined in Theorem 4.
Proof
It follows directly from Theorem 4. \(\square \)
Lemma 10
The statistical distance between the real and decoupled state can be bounded as
Proof
Substitution of Lemma 8 into Lemma 7 gives \(\Vert \rho ^{\mathrm{ZUE}}-\rho ^{\mathrm{Z}}\otimes \rho ^{\mathrm{UE}} \Vert _1\) \(\le \sqrt{\frac{2^\ell -1}{2^n}}\prod _{i=1}^n \mathrm{tr}\,\sqrt{\frac{(\sigma ^{r_i k_i}_0)^2+(\sigma ^{r_i k_i}_1)^2}{2}}\). The trace does not depend on the actual value of \(r_i\) and \(k_i\). We define \(T=\mathrm{tr}\,\sqrt{(\sigma ^{r k}_0)^2+(\sigma ^{r k}_1)^2}/\sqrt{2}\) for arbitrary r, k. From Lemma 9, we obtain (71). Finally, we use \(2^\ell -1<2^\ell \). \(\square \)
Remark
We are able to derive a tight bound because the expression \(\mathrm{tr}\,\sqrt{\sigma _0^2+\sigma _1^2}\) is easy to compute without applying any inequalities.
Since Eve is still free to choose the parameters \(\mu \) and V (or, equivalently, \(\lambda _+\) and \(\lambda _-\)), she can choose them such that the trace distance is maximized.
Theorem 5
Eve’s choice that maximizes \(\Vert \rho ^{\mathrm{ZUE}}-\rho ^{\mathrm{Z}}\otimes \rho ^{\mathrm{UE}} \Vert _1\) is given by
Here, \(\beta _*\) is a saturation value that depends on d as follows,
where \(x_d\) is the solution on (0, 1) of the equation
Proof
We start from (71). At \(\beta ={\textstyle \frac{1}{2}}\), the expression for T is symmetric in \(\lambda _+\) and \(\lambda _-\). Hence, the overall maximum achievable at any \(\beta \) lies at \(\lambda _+=\lambda _-=\frac{q}{d(d-2)}\) for some as yet unknown q. We have
On the other hand, we note that substitution of (73) into (71) yields (72), which is precisely of the form \(\zeta (q,d)\) if we identify \(2\beta \equiv q\). Hence, at some \(\beta <{\textstyle \frac{1}{2}}\) it is already possible to achieve \(T=T^{\beta =1/2}_{\mathrm{max}}\), i.e. we have saturation. We note that substitution of (75) into (71) yields (74). The saturation value \(\beta _*\) is found by solving \(\partial \zeta (2\beta ,d)/\partial \beta =0\); after some simplification, this equation can be rewritten as (77) by setting \(x=2\beta /(1-2\beta )\).Footnote 6 \(\square \)
The upper bound on the amount of information that Eve has about \(S'\) is \(2 \log T\). This is a concave function of \(\beta \) (see Fig. 3). Hence, there is no advantage for Eve to cause different error rates in different rounds. For Eve, it is optimal to cause error rate \(\beta \) in every round.
This concludes the proof of Theorem 1.
The optimal \(\lambda _+,\lambda _-\) are plotted in Fig. 5 (“Appendix B”). The expression \(2\log T\) is plotted in Fig. 3.
Lemma 11
The large-d asymptotics of the saturation value \(\beta _*\) is given by
which yields
Proof
We set \(x_d=1-1/\sqrt{d-2}+a/(d-2)\), where a is supposedly of order 1, and substitute this into (77). This yields \(a={\textstyle \frac{1}{2}}+{{\mathcal {O}}}(1/\sqrt{d-2})\), which is indeed of order 1. Substitution of \(x_d\) into (76) gives (79), and substitution of \(\beta _*\) into (74) gives (80). Finally, substitution of (80) into Lemma 10 yields (81). \(\square \)
10 Von Neumann entropy; Proof of Theorem 2
Using smooth Rényi entropies, it was shown in [12] that, in the large n limit, the von Neumann leakage per qubit is the relevant quantity for determining the required amount of PA.Footnote 7 We denote the leakage from Alice to Eve, in terms of von Neumann entropy, as \(I_{\mathrm{AE}}\). It is given by
In the last line, we used that the eigenvalues of \(\sigma ^{rk}_{s'}\) and \(\sigma ^{rk}_0+\sigma ^{rk}_1\) do not actually depend on r and k. Again \(\lambda _+\) and \(\lambda _-\) can be optimized to Eve’s advantage.
Theorem 6
Eve’s choice that maximizes the von Neumann leakage is given by
Here, \(\beta _0\) is a saturation value that depends on d as follows,
where \(y_d\) is the unique positive root of the polynomial \(y^{d-1}+y-1\).
Proof
We start from (82). We note that the eigenvalue set of \((\sigma ^{rk}_0+\sigma ^{rk}_1)/2\) largely coincides with that of \(\sigma ^{rk}_0\) and \(\sigma ^{rk}_1\) (Theorem 4 and Corollary 1). What remains of (82) comes entirely from the \(| A \rangle ,| B \rangle ,| C \rangle ,| D \rangle \) subspace,
We note that (88) is invariant under the transformation \((\beta \rightarrow 1-\beta ; \lambda _+\leftrightarrow \lambda _-)\). At \(\beta =1/2\), we must hence have \(\lambda _+=\lambda _-=\lambda \).
At \(\beta ={\textstyle \frac{1}{2}}\), the largest leakage that Eve can cause is \(\max _\lambda g(d,\lambda )=g(d,\lambda _*)\).Footnote 8 Next we note that substitution of (86) into (88) yields (85); this has the same form as \(g(d,\lambda )\) (89) if we make the identification \(\lambda d(d-2)=2\beta _0\). Moreover, by setting \(\beta _0={\textstyle \frac{1}{2}} \lambda _* d(d-2)\), Eve achieves the overall maximum leakage \(g(d,\lambda _*)\) already at a value of \(\beta \) smaller than \({\textstyle \frac{1}{2}}\). Since the maximum leakage cannot decrease with \(\beta \), this implies that the maximum leakage saturates at \(\beta =\beta _0\) and stays constant at \(I_{\mathrm{AE}}^{\mathrm{max}}(\beta )=g(d,\lambda _*)\) on the interval \(\beta \in [\beta _0,{\textstyle \frac{1}{2}}]\). The value \(g(d,\lambda _*)\) precisely equals (85). Next we determine the value of \(\beta _0\). Demanding \(\partial g(d,\lambda )/\partial \lambda =0\) at \(\lambda =\lambda _*\) yields
This is equivalent to the polynomial equation \(y^{d-1}+y-1=0\) with \(y\in [0,1]\) if we make the identification \(y=1-\frac{\lambda _* d}{1-\lambda _* d(d-2)}=\frac{1-\lambda _* d(d-1)}{1-\lambda _* d(d-2)}\). (It is readily seen that \(\lambda _*\in [0,{\textstyle \frac{1}{d(d-1)}}]\) implies \(y\in [0,1]\).) This precisely matches (87), because of the optimal choice \(\beta _0={\textstyle \frac{1}{2}} \lambda _* d(d-2)\). By Descartes’ rule of signs, the function \(y^{d-1}+y-1\) has exactly one positive root.
When \(\beta \) is decreased below \(\beta _0\), the location \((\lambda _-,\lambda _+)\) of the maximum of the stationary point of \(I_{\mathrm{AE}}\) leaves the ‘allowed’ triangular region; this happens at a corner of the triangle, \(\lambda _-=0\), \(\lambda _+=\frac{4\beta }{d(d-2)}\). For \(\beta <\beta _0\), this corner yields the highest achievable leakage. Substitution of (84) into (88) yields (83). \(\square \)
This concludes the proof of theorem 2.
Note that the leakage \(I_{\mathrm{AE}}\) is a concave function of \(\beta \). Hence, it is optimal for Eve to cause error rate \(\beta \) in every round.
Remark
From \(y> 0\) and (87), it follows that \(\beta _0<\frac{1}{2}\cdot \frac{d-2}{d-1}\).
Figure 4 shows the von Neumann leakage for three values of d. The optimal \(\lambda _+\),\(\lambda _-\) are plotted in Fig. 5 (“Appendix B”).
Lemma 12
The large-d asymptotics of the \(I_{\mathrm{AE}}\) is given by
Proof
The result for \(\beta <\beta _0\) follows by doing a series expansion of (83) in the small parameter \(1/(d-2)\). For \(\beta >\beta _0\), we study the equation \(y^{d-1}=1-y\). Let us try a solution of the form \(y=1-\frac{\ln [(d-1)/\alpha ]}{d-1}\) for some unknown \(\alpha \). This yields \(\alpha \cdot \{(1-\frac{\ln [(d-1)/\alpha ]}{d-1})^{d-1}\frac{d-1}{\alpha }\}=\ln \frac{d-1}{\alpha }\). Using the fact that \(\lim _{n\rightarrow \infty }(1-x/n)^n=e^{-x}\), we see that the expression \(\{\cdots \}\) is close to 1 if it holds that \(\ln \frac{d-1}{\alpha }\ll d-1\), and that the equation is then satisfied by \(\alpha ={{\mathcal {O}}}(\ln d)\), which is indeed consistent with \(\ln \frac{d-1}{\alpha }\ll d-1\). Substituting \(\alpha ={{\mathcal {O}}}(\ln d)\) into the expression for y and then into (87) gives \(1-2\beta _0=\frac{1}{\ln d}+{{\mathcal {O}}}(\frac{\ln \ln d}{[\ln d]^2})\). Substituting this result for \(1-2\beta _0\) into (85) finally yields (92). \(\square \)
11 Discussion
We remark on the optimal attack. The \({\bar{\rho }}^{\mathrm{AB}}\) mixed state allowed by the noise constraint has two degrees of freedom, \(\mu \) and V. While this is more than the zero degrees of freedom in the case of qubit-based QKD [12], it is still a small number, given the dimension \(d^2\) of the Hilbert space.
Eve’s attack has an interesting structure. Eve entangles her ancilla with Bob’s qudit. Bob’s measurement affects Eve’s state. When Bob reveals r, k, Eve knows which four-dimensional subspace is relevant. However, the basis state \(| k \rangle \) in Bob’s qudit is coupled to \(| A^a_k \rangle \) in Eve’s space (see “Appendix A”), which is spanned by \(d-1\) different basis vectors \(| E^+_{(kt')} \rangle \) (Eq. 96 with \(\lambda _1=0\), \(\lambda _-=0\)), each carrying different phase information \(a_k\oplus a_{t'}\). Only one out of \(d-1\) carries the information she needs, and she cannot select which one to read out. Eve’s problem is aggravated by the fact that the \(| A^a_t \rangle \) vectors are not orthogonal (except at \(\beta ={\textstyle \frac{1}{2}}\)). Note that this entanglement-based attack is far more powerful than the intercept–resend attack studied in [17].
Notes
Reference [17] gives a min-entropy of \(-\log ({\textstyle \frac{1}{2}}+{\textstyle \frac{1}{d}})\), which translates to Shannon entropy \(h({\textstyle \frac{1}{2}}+{\textstyle \frac{1}{d}})\).
The physical implementation [14] is a pulse train: a photon is split into d coherent pieces which are released at different, equally spaced, points in time.
The phase \((-1)^{a_k\oplus a_{k+r}}\) is the phase of the field oscillation in the \((k+r)\)th pulse relative to the kth. The measurement \({{\mathcal {M}}}^{(r)}\) is an interference measurement where one path is delayed by r time units.
If this rare event occurs, we have no other bound than \({\textstyle \frac{1}{2}}\Vert \rho ^{\mathrm{ZUE}}-\rho ^{\mathrm{Z}}\otimes \rho ^{\mathrm{UE}} \Vert _1\le 1\).
In “Appendix A”, it will turn out that Eve’s optimal attack is achieved by acting on Bob’s qudit only; hence, the EPR version is fully equivalent to original RRDPS.
After some rewriting, it can be seen that (77) is equivalent to a complicated 6th order polynomial equation. We have not yet been able to prove that the solution on (0, 1) is unique. Our numerical solutions, however, indicate that this is the case.
By applying Jensen’s inequality once more to Lemma 7, we can move the trace into the square root and get an expression which is equivalent to Lemma 4.4 in [21]. After this point, the proof structure from [21] can be followed. Thus, the von Neumann leakage is also an asymptotic case of our statistical distance result Theorem 1.
\(\frac{\partial ^2 g(d,\lambda )}{\partial \lambda ^2}=-\frac{d}{\lambda }[1-d(d-2)\lambda ]^{-1}[1-d(d-1)\lambda ]^{-1}\); hence, g is a concave function of \(\lambda \) on the interval \(\lambda \in [0,\frac{1}{d(d-1)}]\), which interval coincides with the region allowed by the constraints on \(\mu ,V\). The function g has a single maximum at some point \(\lambda _*\).
References
Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299, 802–803 (1982)
Broadbent, A., Schaffner, C.: Quantum cryptography beyond quantum key distribution. Des. Codes Cryptogr. 78, 351–382 (2016)
Bennett, C.H., Brassard, G.: Quantum cryptography: Public key distribution and coin tossing. In: IEEE International Conference on Computers, Systems and Signal Processing, pp. 175–179 (1984)
Ekert, A.K.: Quantum cryptography based on Bell’s theorem. Phys. Rev. Lett. 67, 661–663 (1991)
Bennett, C.H.: Quantum cryptography using any two nonorthogonal states. Phys. Rev. Lett. 68(21), 3121–3124 (1992)
Ralph, T.C.: Continuous variable quantum cryptography. Phys. Rev. A 61, 010303 (1999)
Hillery, M.: Quantum cryptography with squeezed states. Phys. Rev. A 61, 022309 (2000)
Gottesman, D., Preskill, J.: Secure quantum key distribution using squeezed states. Phys. Rev. A 63, 022309 (2001)
Inoue, K., Waks, E., Yamamoto, Y.: Differential phase shift quantum key distribution. Phys. Rev. Lett. 89(3), 037902,1–037902,3 (2002)
Bruß, D.: Optimal eavesdropping in quantum cryptography with six states. Phys. Rev. Lett. 81(14), 3018–3021 (1998)
Shor, P., Preskill, J.: Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett. 85, 441 (2000)
Renner, R., Gisin, N., Kraus, B.: Information-theoretic security proof for quantum-key-distribution protocols. Phys. Rev. A 72, 012332 (2005)
Kraus, B., Gisin, N., Renner, R.: Lower and upper bounds on the secret key rate for quantum key distribution protocols using one-way classical communication. Phys. Rev. Lett. 95, 080501 (2005)
Sasaki, T., Yamamoto, Y., Koashi, M.: Practical quantum key distribution protocol without monitoring signal disturbance. Nature 509, 475–478 (2014)
Zhang, Z., Yuan, X., Cao, Z., Ma, X.: Practical round-robin differential-phase-shift quantum key distribution. N. J. Phys. 19, 033013 (2017)
Sasaki, T., Koashi, M.: A security proof of the round-robin differential phase shift quantum key distribution protocol based on the signal disturbance. Quantum Sci. Technol. 2(2), 024006 (2017)
Škorić, B.: A short note on the security of round-robin differential phase-shift QKD (2017). https://eprint.iacr.org/2017/052.pdf. Accessed 15 Aug 2018
König, R., Renner, R.: Universally composable privacy amplification against quantum adversaries. In: Proceedings of TCC, LNCS 3378 (2005)
Christandl, M., König, R., Renner, R.: Postselection technique for quantum channels with applications to quantum cryptography. Phys. Rev. Lett. 102, 020504 (2009)
Lo, Hoi-Kwong: Efficient quantum key distribution scheme and a proof of its unconditional security. J. Cryptol. 18(2), 133–165 (2005)
Renner, R.: Security of quantum key distribution. Ph.D. thesis, ETH Zürich (2005)
Coecke, B., Kissinger, A.: Picturing Quantum Processes. Cambridge University Press, Cambridge (2017)
König, R., Renner, R., Schaffner, C.: The operational meaning of min- and max-entropy. IEEE Trans. Inf. Theory 55(9), 4337–4347 (2009)
Holevo, A.S.: Statistical decision theory for quantum systems. J. Multivar. Anal. 3, 337–394 (1973)
Acknowledgements
We thank Serge Fehr for useful discussions. We thank the anonymous reviewers of Eurocrypt 2018 for their comments about symmetrization. Part of this research was funded by NWO (CHIST-ERA project ID_IOT).
Author information
Authors and Affiliations
Corresponding author
Appendices
Details of Eve’s unitary operation
In Theorem 7, we show that Eve does not have to touch Alice’s qudit. Hence, the attacks that we are describing here can also be carried out in the original (non-EPR) protocol, where Eve gets access only to the qudit state sent to Bob.
Theorem 7
The operation that maps the pure EPR state to \(| {\varPsi }^{\mathrm{ABE}} \rangle \) (35) can be represented as a unitary operation on Bob’s subsystem and Eve’s ancilla.
Proof
Let Eve’s ancilla have initial state \(| E_0 \rangle \). The transition from the pure EPR state to (35) can be written as the following mapping,
where \(| {\varOmega }_t \rangle \) is a state in the BE system defined as
The notation \((tt')\) indicates ordering of t and \(t'\) such that the smallest index occurs first. It holds that \(\langle {\varOmega }_t | {\varOmega }_\tau \rangle =\delta _{t\tau }\). Eqs. (93, 94) show that the attack can be represented as an operation that does not touch Alice’s subsystem. Next we have to prove that the mapping is unitary. The fact that \(\langle {\varOmega }_t | {\varOmega }_\tau \rangle =\delta _{t\tau }\) shows that orthogonality in Bob’s space is correctly preserved. In order to demonstrate full preservation of orthogonality, we have to define the action of the operator U on states of the form \(| t \rangle _{\mathrm{B}}\otimes | \varepsilon \rangle _{\mathrm{E}}\), where \(| \varepsilon \rangle \) is one of Eve’s basis vectors orthogonal to \(| E_0 \rangle \), in such a way that the resulting states are mutually orthogonal and orthogonal to all \(| {\varOmega }_t \rangle \), \(t\in \{0,\ldots ,d-1\}\). The dimension of the BE space is \(d^3\) and allows us to make such a choice of \(d(d^2-1)\) vectors. \(\square \)
Theorem 8
Let Alice send the state \(| \mu _a \rangle \) to Bob. Let Eve apply the unitary operation U (specified in the proof of Theorem 7) to this state and her ancilla. The result can be written as
The states \(| A^a_t \rangle \) are normalized and satisfy \(\forall _{t\tau :\tau \ne t}\;\langle A^a_\tau | A^a_t \rangle =(1-2\beta )\).
Proof
We start from \(U(| \mu _a \rangle | E_0 \rangle )=(1/\sqrt{d})\sum _t(-1)^{a_t}| {\varOmega }_t \rangle \), and we substitute (94). Re-labelling of summation variables yields (95, 96). The norm \(\langle A^a_t | A^a_t \rangle \) equals \(\lambda _0+(d-1)\lambda _1+\frac{d(d-1)}{2}\lambda _+ +\frac{d(d-1)}{2}\lambda _-\), which equals 1 since this is also equal to the trace of \({\tilde{\rho }}^{\mathrm{AB}}\). For \(\tau \ne t\), the inner product \(\langle A^a_\tau | A^a_t \rangle \) yields
We use \(\sum _{j=1}^{d-1}e^{i\frac{2\pi }{d} j(t-\tau )}=d\delta _{\tau t}-1=-1\). Furthermore, the Kronecker deltas in (97) set the phase \((-1)^{\cdots }\) to 1 and \(\mathrm{sgn}(t'-t)\mathrm{sgn}(\tau '-\tau )=\mathrm{sgn}(\tau -t)\mathrm{sgn}(t-\tau )=-1\). Finally, we use \(\lambda _0-\lambda _1=1-2\beta -V\) and \(\lambda _+-\lambda _-=2V/d\). \(\square \)
Theorem 8 reveals an intuitive picture. In the noiseless case (\(\beta =0\)), it holds that \(\forall _t\; | A^a_t \rangle =| E_0 \rangle \), i.e. Eve does nothing, resulting in the factorized state \(| \mu _a \rangle | E_0 \rangle \). In the case of extreme noise (\(\beta ={\textstyle \frac{1}{2}}\)), we have \(\langle A^a_t | A^a_\tau \rangle =\delta _{t\tau }\), which corresponds to a maximally entangled state between Bob and Eve.
Corollary 3
The pure state (95) in Bob and Eve’s space gives rise to the following mixed state \(\rho ^{\mathrm{B}}_a\) in Bob’s subsystem,
Proof
It follows directly from (95) by tracing out Eve’s space and using the inner product \(\langle A^a_\tau | A^a_t \rangle =(1-2\beta )\) for \(\tau \ne t\). \(\square \)
From Bob’s point of view, what he receives is a mixture of the \(| \mu _a \rangle \) state and the fully mixed state. The interpolation between these two is linear in \(\beta \). Note that the parameters \(\mu ,V\) are not visible in \(\rho ^{\mathrm{B}}_a\).
Min-entropy and accessible entropy
By way of supplementary information, we present a number of results about simple attacks on individual qudits. This teaches us which kind of qubit-wise measurement is informative for Eve. Furthermore, it quantifies the gap between what is provable for general attacks and what is provable for more restricted attacks. We compute leakage in terms of min-entropy loss and in terms of accessible (Shannon) information. Since min-entropy is a very conservative measure, we will see that the min-entropy loss exceeds the leakage found in Theorems 1 and 2. The main interest is in Eve’s measurement. It is possible to give a composable security proof based on the min-entropy result and post-selection, but this yields a lower rate than Theorem 1.
The accessible information is the relevant quantity when Eve’s quantum memory is short-lived, forcing her to perform a measurement on her ancillas before she has observed Alice and Bob’s usage of the QKD key. As expected, the accessible information turns out to be smaller than the leakage of Theorems 1 and 2.
1.1 (Min-)entropy of a classical variable given a quantum state
The notation \({{\mathcal {M}}}(\rho )\) stands for the classical RV resulting when \({{\mathcal {M}}}\) is applied to mixed state \(\rho \). Consider a bipartite system ‘AB’ where the ‘A’ part is classical, i.e. the state is of the form \(\rho ^{\mathrm{AB}}={{\mathbb {E}}}_{x\in {{\mathcal {X}}}}| x \rangle \langle x |\otimes \rho _x\) with the \(| x \rangle \) forming an orthonormal basis. The min-entropy of the classical RV X given part ‘B’ of the system is [23]
Here, \({{\mathcal {M}}}=(M_x)_{x\in {{\mathcal {X}}}}\) denotes a POVM. Let \({\varLambda }{\mathop {=}\limits ^{\mathrm{def}}}\sum _x \rho _x M_x\). If a POVM can be found that satisfies the conditionFootnote 9 [24]
then there can be no better POVM for guessing X (but equally good POVMs may exist). For states that also depend on a classical RV \(Y\in {{\mathcal {Y}}}\), the min-entropy of X given the quantum state and Y is
A simpler expression is obtained when X is a binary variable. Let \(X\in \{0,1\} \).
Then,
This generalizes in a straightforward manner for states that depend on multiple classical RVs. The Shannon entropy of a classical variable given a measurement on a quantum state is given by
The ‘accessible information’ is defined as the mutual information \(\mathsf{H}(X)-\mathsf{H}(X|\rho _X)\). In contrast to the min-entropy case, there is no simple test analogous to (100) which tells you whether a local minimum in (103) is a global minimum.
1.2 Min-entropy
Eve’s ability to distinguish between the cases \(s'=0\) and \(s'=1\) depends on the distance between \(\sigma ^{rk}_0\) and \(\sigma ^{rk}_1\) (see Sect. B.1). Equation (102) with \(p_0={\textstyle \frac{1}{2}}\), \(p_1={\textstyle \frac{1}{2}}\) tells us that the relevant quantity is \(\Vert \sigma ^{rk}_0-\sigma ^{rk}_1 \Vert _1\). For notational convenience, we define the value \(\beta _{\mathrm{{sat}}}\),
Again we optimize \(\lambda _+\) and \(\lambda _-\).
Lemma 13
For all r, k the choice for \(\lambda _+\) and \(\lambda _-\) that maximizes the trace distance \(\frac{1}{2}\left\| \sigma ^{rk}_0-\sigma ^{rk}_1 \right\| _1\) is
which gives
Proof
From Corollary 2, it is easy to see that
In “Appendix C”, we derive the \(\lambda _+\), \(\lambda _-\) that maximize (108) while keeping all eigenvalues non-negative. \(\square \)
Remark
The optimal choice for \(\lambda _+\),\(\lambda _-\) has the same form for all three optimizations that we have performed. The only difference is the saturation value. Although (106) is shown in a simplified form, one can manipulate it to the same form as (75) and (86) with \(\beta _{\mathrm{sat}}\) instead of \(\beta _*\) or \(\beta _0\).
Figure 5 shows the optimal \(\lambda _+\) and \(\lambda _-\) together with the constraints on the \(\lambda \) parameters for all three optimizations. The lower dots in the figure correspond to \(\beta =\frac{1}{2}\). For all three information measures, the optimum moves towards the top corner of the triangle for decreasing \(\beta \). For \(\beta \) values below the saturation point the optimum is the top corner, with \(\lambda _-=0\) and \(\lambda _1=0\).
Knowing the optimal values for \(\lambda _+\) and \(\lambda _-\), we compute the min-entropy leakage.
Theorem 9
The min-entropy of the bit \(S'\) given R, K and the state \(\sigma ^{RK}_{S'}\) is
Proof
Equation (102) with X uniform, \(X\rightarrow S'\), \(Y\rightarrow (R,K)\) becomes
In the last step, we omitted the expectation over r and k since the trace distance does not depend on r, k. Substitution of (107) into (111) gives the end result. \(\square \)
Corollary 4
Eve’s optimal POVM \({{\mathcal {T}}}^{rk}=(T^{rk}_0,T^{rk}_1)\) for maximizing the min-entropy leakage is given by
Proof
The trace distance in Lemma 13 is the sum of the positive eigenvalues of \(\sigma ^{rk}_0-\sigma ^{rk}_1\). In the space spanned by \(| A \rangle , | B \rangle , | C \rangle , | D \rangle \), the optimal \(T_0\) consists of the projection onto the space spanned by the eigenvectors corresponding to the positive eigenvalues. These eigenvectors are \(| v_1 \rangle =\frac{| A \rangle +| C \rangle }{\sqrt{2}}\) and \(| v_2 \rangle =\frac{| D \rangle -| B \rangle }{\sqrt{2}}\). The matrix that projects onto them is \(| v_1 \rangle \langle v_1 |+| v_2 \rangle \langle v_2 |={\textstyle \frac{1}{2}}| A \rangle \langle A |+{\textstyle \frac{1}{2}}| B \rangle \langle B |+{\textstyle \frac{1}{2}}| C \rangle \langle C |+{\textstyle \frac{1}{2}}| D \rangle \langle D |\) \(+| A \rangle \langle C |+| C \rangle \langle A |-| B \rangle \langle D |-| D \rangle \langle B |\). In order to satisfy the constraint \(T_0+T_1={\mathbb {1}}\) and symmetry, half the identity matrix in the remaining \(d^2-4\) dimensions has to be added to \(T_0\). We mention, without showing it, that (112) satisfies the test (100). \(\square \)
As expected, the min-entropy loss decreases as the dimension of the Hilbert space grows. We see that the entropy loss saturates at \(\beta = \beta _{\mathrm{{sat}}}\); hence, RRDPS is secure up to arbitrarily high noise levels. Figure 6 shows the min-entropy leakage as a function of \(\beta \).
1.3 Accessible Shannon information
Lemma 14
Let \(X\in {{\mathcal {X}}}\) be a uniformly distributed random variable. Let \(Y\in {{\mathcal {Y}}}\) be a random variable. Let \(\rho _{xy}\) be a quantum state coupled to the classical x, y. The Shannon entropy of X given a state \(\rho _{XY}\) that has to be measured (for unknown X and Y) is given by
Proof
We have \(\mathsf{H}(X|\rho _{XY})=\min _{{\mathcal {M}}}\mathsf{H}(X|Z)\), where Z is the outcome of the POVM measurement \({{\mathcal {M}}}\). Z is a classical random variable that depends on X and Y. We can write \(\mathsf{H}(X|Z)=\mathsf{H}(X)-\mathsf{H}(Z)+\mathsf{H}(Z|X)\). Since X is uniform and Z is an estimator for X, the Z is uniform as well. Thus, we have \(\mathsf{H}(X)-\mathsf{H}(Z)=0\), which yields \(\mathsf{H}(X|\rho _{XY})=\min _{{\mathcal {M}}}\mathsf{H}(Z|X) = \min _{{\mathcal {M}}}{{\mathbb {E}}}_x \mathsf{H}(Z|X=x)\). The probability \(\mathrm{Pr}[z|x]\) is given by \(\mathrm{Pr}[z|x]={{\mathbb {E}}}_{y|x}\mathrm{Pr}[z|xy]={{\mathbb {E}}}_{y|x}\mathrm{tr}\,M_z\rho _{xy}\). \(\square \)
Corollary 5
It holds that
Proof
Application of Lemma 14 yields
where in the last step we used the definition of \(\sigma ^{rk}_{s'}\). Finally, the Shannon entropy of a binary variable is given by the binary entropy function h, where \(h(1-p)=h(p)\). \(\square \)
From Corollary 5, we see that the POVM \({{\mathcal {T}}}^{rk}\) associated with the min-entropy also optimizes the Shannon entropy: Maximizing the guessing probability \(\mathrm{tr}\,G^{rk}_{s'}\sigma ^{rk}_{s'}\) minimizes the Shannon entropy.
Theorem 10
The Shannon entropy of Alice’s bit \(S'\) given the state \(\sigma ^{RK}_{AS}\), R and K is:
Proof
The min-entropy result (109, 110) can be written as \(\mathsf{H}_{\mathrm{min}}(S'|RK\sigma ^{RK}_{S'}) = -\log \mathrm{tr}\,T^{rk}_{s'} \sigma ^{rk}_{s'}\), so we already have an expression for \(\mathrm{tr}\,T^{rk}_{s'} \sigma ^{rk}_{s'}\). Substitution of \({{\mathcal {T}}}^{rk}\) for \({{\mathcal {G}}}^{rk}\) in (114) yields the result. \(\square \)
Since the optimal POVMs for min-entropy and Shannon entropy are the same, saturation occurs at the same point (\(\beta =\beta _{\mathrm{{sat}}}\)). Figure 7 shows the Shannon entropy leakage (mutual information) \(I_{\mathrm{AE}}=1-\mathsf{H}(S'|RK\sigma ^{RK}_{AS})\) as a function of \(\beta \).
Optimization for the min-entropy
Here, we prove that (105, 106) maximizes (108). We first show that (108) is concave and obtain the optimum for \(\beta \ge \beta _{\mathrm{sat}}\). Then, we take into account the constraints on the eigenvalues and derive the optimum for \(\beta <\beta _{\mathrm{sat}}\).
Unconstrained optimization For notational convenience, we define
This allows us to formulate everything in terms of \(\lambda _+\) and \(\lambda _-\). Equation (108) becomes
Next, we compute the derivatives,
Setting both these derivatives to zero yields a stationary point of the function. Setting \(w_1\sqrt{\lambda _+}\frac{\partial }{\partial \lambda _+}\left\| \sigma ^{rk}_0-\sigma ^{rk}_1 \right\| _1\) \(-w_2\sqrt{\lambda _-}\frac{\partial }{\partial \lambda _-} \left\| \sigma ^{rk}_0-\sigma ^{rk}_1 \right\| _1\) to zero gives \(\lambda _+w_1^2-\lambda _-w_2^2 =0\), which describes a hyperbola
Next, the equations \(\sqrt{\lambda _+} w_1 w_2 \frac{\partial }{\partial \lambda _+} \left\| \sigma ^{rk}_0-\sigma ^{rk}_1 \right\| _1=0\) and \(\sqrt{\lambda _-} w_1 w_2 \frac{\partial }{\partial \lambda _-} \left\| \sigma ^{rk}_0-\sigma ^{rk}_1 \right\| _1=0\) can both easily be written in the form \(\frac{w_2}{w_1}=expression\). Equating these two expressions gives us another hyperbola,
The stationary point lies at the crossing of these two hyperbolas. There are four crossing points,
In the steps above, we have multiplied our derivatives by \(\lambda _+\), \(\lambda _-\), \(w_1\) and \(w_2\); this has introduced spurious zeros that now need to be removed. From (121, 122), it is easily seen that \(\lambda _+=0\) and \(\lambda _-=0\) are never stationary points since the derivatives diverge near these values. Furthermore, we find that substitution of (128) into the derivatives does not yield two zeros. Expression (127) is the only stationary point. As the function value lies higher there than in other points, we conclude that \(\left\| \sigma ^{rk}_0-\sigma ^{rk}_1 \right\| _1\) is concave.
Constrained optimization The optimization problem is constrained by the fact that the \(\lambda \) eigenvalues are nonnegative. For \(\beta \ge \beta _{\mathrm{sat}}\), the stationary point satisfies the constraints and hence is the optimal choice for \(\beta \ge \beta _{\mathrm{sat}}\).
For \(\beta <\beta _{\mathrm{sat}}\), the stationary point has \(\lambda _- <0\), i.e. it lies outside the allowed region. Because of the concavity, the highest function value which satisfies the constraints occurs at \(\lambda _0=0\), \(\lambda _1=0\), \(\lambda _+=0\) or \(\lambda _-=0\). It is easily seen that \(\lambda _0 \ge 0\) implies \(\lambda _+ \le \frac{1}{d-1}-\frac{2\beta }{d}\) and \(\lambda _1 \ge 0\) implies \(\lambda _+ \le \frac{4\beta }{d(d-2)} - \frac{d}{d-2}\lambda _-\) and \(\lambda _- \le \frac{4\beta }{d^2} -\frac{d-2}{d}\lambda _+\). In the range \(\beta < \beta _{\mathrm{sat}}\) it holds that \(\frac{4\beta }{d(d-2)}<\frac{1}{d-1}-\frac{2\beta }{d}\); hence, the \(\lambda _0\)-constraint is irrelevant in this region. We get \(\lambda _1=0\) when \(\lambda _+=\frac{4\beta }{d(d-2)} - \frac{d}{d-2} \lambda _-\). Substitution gives \(\frac{1}{2} \left| \left| \sigma ^{rk}_0-\sigma ^{rk}_1 \right| \right| _1 = \frac{\sqrt{2}}{d-2} \sqrt{2(1-\beta )+d (1-2\beta +d\left( 1-2\beta (d-1)\lambda _-) \right) \left( d^2 \lambda _--4\beta \right) }\) which has its maximum at \(\lambda _-=0\) for nonnegative values of \(\lambda _-\). So either \(\lambda _-=0\) or \(\lambda _+=0\). This leaves two options for the maximum at low \(\beta \),
Clearly, (130) is the larger of the two and therefore the optimal choice. \(\square \)
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Leermakers, D., Škorić, B. Security proof for round-robin differential phase shift QKD. Quantum Inf Process 17, 250 (2018). https://doi.org/10.1007/s11128-018-2027-2
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11128-018-2027-2