() - 1210.1810v2.pdf

arXiv:1210.1810v2 [quant-ph] 25 Nov 2012

Fully device independent quantum key distribution

Umesh Vazirani

∗

Thomas Vidick

†

Abstract

The laws of quantum mechanics allow unconditionally secure

key distribution protocols. Neverthe-

less, security proofs of traditional quantum key distribut

ion (QKD) protocols rely on a crucial assump-

tion, the trustworthiness of the quantum devices used in the

protocol. In device-independent QKD, even

this last assumption is relaxed: the devices used in the prot

ocol may have been adversarially prepared,

and there is no a priori guarantee that they perform accordin

g to specification. Proving security in this

setting had been a central open problem in quantum cryptogra

phy.

We give the first device-independent proof of security of a pr

otocol for quantum key distribution that

guarantees the extraction of a linear amount of key even when

the devices are subject to a constant rate of

noise. Our only assumptions are that the laboratories in whi

ch each party holds his or her own device are

spatially isolated, and that both devices, as well as the eav

esdropper, are bound by the laws of quantum

mechanics. All previous proofs of security relied either on

the use of many independent pairs of devices,

or on the absence of noise.

1 Introduction

Quantum key distribution [BB84, Eke91] together with its pr

oof of security [May01, SP00] appeared to

have achieved the holy grail of cryptography — unconditiona

l security, or a scheme whose security was

based solely on the laws of physics. However, practical impl

ementations of QKD protocols necessarily

involve imperfect devices [BBB

92, MHH

97], and it was soon realized that these imperfections could

exploited by a malicious eavesdropper to break the “uncondi

tional” security of QKD (see e.g. [SK09] for a

review).

Mayers and Yao [MY98] put forth a vision for restoring uncond

itional security in the presence of im-

perfect or even maliciously designed devices, by subjectin

g them to tests that they fail unless they behave

consistently with “honest” devices. The fundamental chall

enge they introduced was of

device-independent

quantum key distribution

(DIQKD): establishing the security of a QKD protocol based o

nly on the validity

of quantum mechanics, the physical isolation of the devices

and the passing of certain statistical tests. The

germ of the idea for device-independence may already be seen

in Ekert’s original entanglement-based pro-

tocol for QKD [Eke91], and was made more explicit by Barrett,

Hardy, and Kent [BHK05], who showed

how to generate a single random bit secure against any non-si

gnalling eavesdropper. A long line of re-

search on DIQKD seeks to make the qualitative argument from [

BHK05] quantitative, devising protocols

that extract an amount of key that is linear in the number of us

es of the devices, and is secure against in-

creasingly general eavesdropping strategies. Initial wor

ks [AGM06, AMP06, SGB

06] give efficient and

∗

Department of Computer Science, UC Berkeley, California. S

upported by ARO Grant W911NF-09-1-0440 and NSF Grant

CCF-0905626. Email

vazirani@eecs.berkeley.edu

†

Computer Science and Artificial Intelligence Laboratory, M

assachusetts Institute of Technology. Supported by NSF Gra

0844626. Email

vidick@csail.mit.edu

noise-tolerant protocols that are secure against individu

al attacks by non-signalling eavesdroppers. Sub-

sequent work [MRC

09, Mas09] and [HRW10] also proved security against collect

ive attacks. Other

works [ABG

07, PAB

09, MRC

09, HR10, MPA11] obtain better key rates under the stronger a

ssumption

that the eavesdropper is bound by the laws of quantum mechani

cs. All these results, however, could only be

established under restrictive

independence

assumptions on the devices, e.g. in recent work [HR10, MPA11

]

a proof of security based on collected statistics requires t

hat the

uses of each device are causally indepen-

dent: measurements performed at successive steps of the pro

tocol commute with each other.

Very recently two papers [BCK12b, RUV12] announced proofs o

f security of DIQKD without requir-

ing any independence assumption between the different uses

of the devices. Unfortunately, although the

approaches in [BCK12b, RUV12] are very different both impli

ed protocols are polynomially inefficient and

unable to tolerate noisy devices. The protocol used in [BCK1

2b] is very similar to the one originally intro-

duced in [BHK05], and requires a large number of uses of a pair

of noise-free devices in order to generate

a single bit of key. In the case of [RUV12], DIQKD is obtained a

s a corollary of very strong testing that

allows the shared quantum state and operators of the two untr

usted devices to be completely characterized.

It is an open question whether such strong testing can be achi

eved in a manner that is robust to noise.

A major issue in QKD is dealing with the noise inherent in even

the best devices. Indeed, a good

DIQKD protocol should differentiate devices that are “hone

st but noisy” from devices that may attempt to

take advantage of the protocol’s necessary noise tolerance

in order to leak information to an eavesdropper

by introducing correlations in their “errors” [BCK12a]. Th

e protocols in [BCK12b, RUV12] do not achieve

this, since they cannot tolerate any constant noise rate. Th

is raises the question: is device-independent QKD

even

possible

without independence assumptions in a realistic, noise-to

lerant scenario?

1.1 Results

We answer this question in the affirmative by giving the first c

omplete device-independent proof of security

of quantum key distribution that tolerates a constant noise

rate and guarantees the generation of a linear

amount of key. Our only assumption on the devices is that they

can be modeled by the laws of quantum

mechanics, and that they are spatially isolated from each ot

her and from any adversary’s laboratory. In

particular, we emphasize that the devices may have quantum m

emory. While the proof of security is quite

non-trivial (it builds upon ideas from the work on certifiabl

e randomness generation mentioned below), the

actual protocol whose device independence properties we es

tablish is quite simple. It is a small variant of

Ekert’s entanglement-based protocol [Eke91].

In the protocol, the users Alice and Bob make

successive uses of their respective devices. At each

step, Alice (resp. Bob) privately chooses a random input

∈ {

0, 1, 2

}

(resp.

∈ {

0, 1

}

) for her device,

collecting an output bit

(resp.

). If the devices were honestly implemented they would share

Bell states

√

, and measure their qubits according to the following strate

gy: if

measure in the computational basis, if

measure in the Hadamard basis and if

measure in the

-rotated basis. If

measure in the

-rotated basis and if

measure in the

-rotated

basis.

To test the devices, after the

steps have been completed, the users select a random subset

⊆

{

1, . . . ,

}

of size

, where

is a small constant, and publicly announce their inputs and

outputs in

. Rounds in

will be called “Bell rounds”. Let

if and only if

and

⊕

∧

(

) = (

2, 1

)

and

. The users jointly compute the noise rate

= (

)

∑

∈

−

(

−

opt

)

where

opt

= (

2 cos

)

≥

0.5%

, say, they abort. If not, they announce their remaining

This corresponds to estimating the average amount by which t

he devices’ outputs in

differ from a maximal violation of a

input choices. Let

⊆ {

1, . . . ,

}

be the steps in which

(

) = (

2, 1

)

. We will call the rounds in

the

“check rounds”; outputs from the rounds

−

constitute the raw key. The users conclude by performing

standard information reconciliation and privacy amplifica

tion steps, extracting a key of length

for some

(

)

, where

is the desired security parameter. (We refer to Figures 1 and

2 for a more detailed

description of the protocol.)

Theorem 1

(Informal)

Let

be a large enough integer and

−

, where

is a small constant.

Given any pair of spatially isolated quantum devices

and

, the protocol described above generates a

shared key

of length

, where

≈

1.4%

, that is

-secure: the probability that the users Alice and Bob

do not abort and that the adversary can obtain information ab

out the key is at most

This informal statement hides a tradeoff between the parame

ters

, and

: the larger the security

parameter

and the smaller the noise rate

, the higher the key rate

. As

→

(provided

is chosen large

enough) our proof guarantees a secure key rate

≈

2.5%

, which with our setting of parameters corresponds

to about

15%

of the raw key. Conversely, the maximum noise rate for which w

e may extract a key of positive

length is

max

≈

1.2%

. This is worse than the optimal key rates obtained under the c

ausal independence

assumption [MPA11], but still quite reasonable.

1.2 Proof overview and techniques

We start with the observation that the randomness in the shar

ed secret key must necessarily be generated by

the two devices. Indeed, even though the users have the abili

ty to generate perfect random bits privately,

such bits cannot be used directly for the shared key, since an

y information transmitted about them is also

available to the adversary. It follows that a necessary cond

ition for DIQKD is that the users should be

able to use their untrusted devices to generate

certified

randomness — randomness they can guarantee was

not pre-encoded in the devices by the adversary, nor obtaine

d as some function of the users’ inputs to the

devices.

Luckily, the possibility of generating certified randomnes

s has already been investigated. Building on an

observation made in [Col06], Pironio et al. [PAM

10] devised a protocol in which the generation of random-

ness could be certified solely by testing for a sufficiently la

rge Bell inequality violation. In [FGS11, PM11]

it was further shown that the randomness generated was secur

e against an arbitrary classical adversary. Con-

currently, in [VV11] we gave a protocol that was secure even a

gainst a quantum adversary. This last protocol

provides us with a solid starting point for DIQKD, since our g

oal is to prove that the quantum adversary,

who may have fabricated the two devices, has no information a

bout the shared random key. Nevertheless,

extending this to DIQKD presents us with some serious new cha

llenges.

1. First, QKD is a task that involves two distant parties Alic

e and Bob. Any classical communication

between Alice and Bob must take place in the clear and is there

fore accessible to the adversary, thus

giving her additional power.

2. Second, in order to achieve QKD it is not sufficient just to g

enerate randomness — the point of QKD is

that Alice and Bob share the same random key. In our protocol t

his is accomplished by distinguishing

two different types of rounds: Bell rounds, in which the viol

ation of the CHSH inequality by the

devices is estimated, and check rounds, in which the devices

are supposed to produce identical outputs

from which the key will be generated. Unfortunately Alice an

d Bob must exchange information about

which rounds are which, and since the adversary has access to

all communicated classical information,

Bell inequality based on the CHSH inequality [CHSH69, BC90]

: see Section 2 for details.

this appears to render the Bell rounds pointless, since the a

dversary can ignore the Bell rounds and

attack only those rounds which are used to generate the key (t

he check rounds).

3. Finally, to be practical the protocol should tolerate noi

sy devices. As a result, the users can only

expect a non-maximal amount of correlation, both in the Bell

and check rounds. The randomness-

certification protocol from [VV11] did not tolerate any nois

e — in fact, the absence of noise played

a crucial role in the proof. As we already explained in the int

roduction, dealing with the presence of

noise is one of the major conceptual and technical hurdles of

the proof.

We now explain how our proof technique addresses these chall

enges. The proof proceeds in two steps.

As a first step, we argue that the following three conditions c

annot hold simultaneously in any single round

of the protocol: (i) the devices violate the CHSH inequality

, whenever the round was selected as a Bell

round (ii) the adversary can predict Bob’s output, whenever

the round was selected as a check round, and

(iii) the no-signalling condition is satisfied between all t

hree parties (Alice, Bob and the adversary). To

derive a contradiction from (i)–(iii) we use a simple concep

tual tool called the “guessing game”, which was

introduced in [VV11]. The main idea is that conditions (i) an

d (ii) imply that the adversary and Alice will

be able to team up to predict Bob’s output from their sole resp

ective input/output behavior, violating the

no-signalling condition (iii).

The second step is more challenging. All previous works on th

e subject reduced the general setting to a

single-round scenario similar to the one outlined above by r

equiring some form of independence assumption

on the devices or on the adversary’s attack. We do not use any s

uch assumption, and the main challenge is

to deal with correlations between all rounds and the adversa

ry in order to perform the reduction.

Our starting point is the existence of a pair of devices that p

ass the protocol with non-negligible prob-

ability, but such that the adversary may gain non-negligibl

e information about the secret key generated at

the end of the protocol. Our goal is to show the existence of a r

ound

of the protocol in which conditions

(i)–(iii) above are satisfied, thus deriving a contradictio

Our argument has two main ingredients. The first ingredient i

s the so-called “quantum reconstruction

paradigm”, a technique that was introduced in [DV10] and fur

ther developed in [DPVR12, VV11]. What

this achieves is the following: any adversary able to obtain

non-negligible information about the generated

key can be transformed into a seemingly much stronger advers

ary: she can

predict

the entire string of

outputs of Bob’s device on the check rounds (the rounds used t

o generate the key). Furthermore, the success

probability of this “guessing measurement” is of the same or

der as the original distinguishing probability

but does not depend on the length of the key — a fact that will be

crucial to obtaining good parameters. In

order to achieve this, the new adversary requires access to t

he same public information as the original one,

together with a small number of additional “advice bits” tak

en from Bob’s string of outputs.

This stronger form of the adversary guarantees that conditi

on (ii) above holds in all rounds with small

but non-negligible probability. Furthermore, the checkin

g performed as part of the protocol ensures that

(i) also holds on average over all rounds, with probability o

f the same order. The natural idea in order to

identify a round

in which conditions (i) and (ii) hold simultaneously with hi

gh probability is to perform

conditioning: there must exist many rounds

such that, provided both conditions hold in rounds

−

they must hold in round

with high probability.

Such conditioning, however, presents a new difficulty: it ma

y introduce such correlations that condition

(iii) is no longer satisfied. Indeed, recall that one of the ma

in difficulties in analyzing the QKD protocol is

that the adversary has considerable power, due to the large a

mount of public information that is leaked by the

protocol — including the users’ complete choice of inputs. H

ence conditioning on a low probability event

involving the outcome of a measurement performed by the adve

rsary on her system introduces correlations

between inputs in all rounds. For instance, this conditioni

ng could very well force the inputs in round

be a particular pair, say

(

0, 0

)

, making the guarantees (i) and (ii) all but useless.

The difficulty is reminiscent of one encountered in the analy

sis of parallel repetition, where conditioning

on success in a subset of the parallel repeated games may intr

oduce correlations among the players in the

remaining games. Here, the situation is further complicate

d by the fact that it involves three parties involved

in a relatively complex interaction. In particular, the con

ditioning is performed jointly on an event involving

Alice and Bob (the CHSH violation observed in previous round

s being sufficiently large) on the one hand,

and Bob and Eve (Eve’s guess being correct) on the other.

The final step in our proof consists in bounding the amount of c

orrelation introduced by the conditioning.

For this we use tools from information theory, including the

chain rule for mutual information and the

quantum Pinsker’s inequality, which had not previously bee

n applied to this setting. (Similar tools were

already used by Holenstein in his derivation of a parallel re

petition theorem for the case of two-player

games with no-signalling players [Hol09].)

1.3 Perspective

We have not attempted to optimize the relationship between t

he parameters

and

describing the key

rate, the noise rate and the security parameter respectivel

y, and it is likely that the explicit dependency

stated in Theorem 8 can be improved by tightening our argumen

ts. It is an interesting question to find out

whether our approach can lead to a trade-off as good as the one

that has been shown to be achievable under

additional assumptions on the devices [MPA11]. One possibi

lity for improvement would be to bias the

users’ input distribution towards the pair of inputs

(

2, 1

)

from which the raw key is extracted, as was done

in e.g. [AMP06]: indeed, only a very small fraction of the rou

nds are eventually required to estimate the

violation of the CHSH condition.

Our proof crucially makes use of quantum mechanics to model t

he devices and the adversary. Can one

obtain a fully device-independent proof of security of QKD a

gainst adversaries that are only restricted by

the no-signalling principle? Barrett et al. [BCK12b] recen

tly showed that such security is achievable in

principle; however their protocol is highly inefficient and

does not tolerate noisy devices.

Organization of the paper.

We start with some preliminaries in Section 2, introducing o

ur notation, the

information-theoretic quantities that will be used. We als

o summarize the main parameters of our protocol,

which is described in Figures 1 and 2. In Section 3 we formally

state our result and outline the security proof.

The two main ingredients are the analysis of Protocol B, whic

h is given in Section 4, and the “quantum

reconstruction paradigm” introduced in Section 5. Finally

, Section 6 contains probabilistic and information-

theoretic lemmas used in some of the proofs.

Acknowledgments.

We thank Anthony Leverrier for many useful comments on a prel

iminary version of

this manuscript.

2 Preliminaries

We assume familiarity with basic concepts and standard nota

tion in quantum information, including den-

sity matrices and distance measures such as the trace distan

ce and the fidelity. We refer the reader to the

books [NC00, Wil11] for detailed introductions.

Notation.

We use roman capitals

, . . . ,

both to refer to random variables and the registers, classic

or quantum, that contain them. Calligraphic letters

, . . . ,

are used to refer to the underlying Hilbert

space.

(

)

denotes the set of density operators (non-negative matrice

s with trace

) on

. For an arbitrary

matrix

we let

√

†

denote its Schatten

-norm.

denotes the natural logarithm and

log

the logarithm in base

. For

∈

[

0, 1

]

(

) =

−

log

−

(

−

)

log

(

−

)

is the binary entropy

function.

Information theoretic quantities.

Given a density matrix

∈

(

)

, its von Neuman entropy is

(

)

−

(

)

. For a classical-quantum state

X A

∑

| ⊗

∈

(

X ⊗ A

)

, where for every

∈

(

)

, the conditional entropy is defined as

(

)

∑

(

)

. Given a state

ABX

, where

is classical, the conditional mutual information is

(

)

(

)

(

)

−

(

)

We will use the following quantum analogue of the classical P

insker’s inequality (see e.g. Theorem 11.9.1

in [Wil11] for a proof): for any

∈

(

)

∥

−

⊗

∥

≤

(

2 ln 2

)

(

)

(1)

The most important information measure in our context is the

quantum conditional min-entropy, first intro-

duced in [Ren05], and defined as follows.

Definition 2.

Let

be a bipartite density matrix. The

min-entropy

conditioned on

is defined as

min

(

)

max

{

∈

∃

∈

(

)

s.t. 2

−

⊗

≥

}

We will often drop the subscript

when there is no doubt about the underlying state. The smooth

min-entropy is defined as follows.

Definition 3.

Let

≥

and

a bipartite density matrix. The

-smooth min-entropy

conditioned on

is defined as

min

(

)

max

∈

(

)

min

(

)

where

(

)

is a ball of radius

around

The CHSH condition.

The security of our DIQKD protocol is based on the statistica

l verification that

the pair of devices used have an input/output behavior consi

stent with certain pre-determined correlations,

which are those expected of a “honest” quantum-mechanical p

air of devices performing the measurements

described below.

Let

and

designate two spatially isolated devices. In the protocol,

there are three possible choices of

inputs

∈ {

0, 1, 2

}

, and two possible inputs

∈ {

0, 1

}

. Each of the

possible pairs of inputs is

chosen with uniform probability

1/6

. The devices are required to produce outputs

∈ {

0, 1

}

respectively.

The users select a random subset of the rounds of the protocol

in which to evaluate the frequency with which

the following constraints are satisfied. In case both inputs

were in

{

0, 1

}

, the constraint on the outputs is the

CHSH parity constraint

⊕

∧

[CHSH69]. If the inputs are

(

2, 1

)

the constraint is that the outputs

Theoretically any distance measure could be used to define an

-ball. As has become customary, we use the

purified distance

(

)

√

−

(

)

, where

(

)

is the fidelity.

(

)

should satisfy

⊕

. Finally, for the remaining pair of inputs

(

2, 0

)

all pairs of outputs are valid.

We will refer to this set of constraints collectively as “the

CHSH condition”. We note that the underlying

Bell inequality is similar to the so-called “chained inequa

lity” for two inputs [BC90].

Let

opt

be the maximum probability with which any two isolated devic

es, obeying the laws of quan-

tum mechanics, may produce outputs satisfying the CHSH cond

ition. It is not hard to show that

opt

(

2/3

)

cos

+ (

1/3

)

, which is achieved using the following strategy. The device

s are initialized in

a single EPR pair

= (

)

√

, each device holding one qubit. On input

performs a

measurement in the computational basis, and on input

it measures in the Hadamard basis. On input

measures in the computational basis rotated by

. If

gets input

, or if

gets input

, they measure in

the computational basis rotated by

. The devices may be used repeatedly, and honest devices perf

orm

measurements on a fresh EPR pair at each use.

Parameters.

For convenience, we summarize here the main parameters of th

e key distribution protocol

described in Figures 1 and 2.

•

is the total number of rounds in the protocol (in each round, a

n input to each of

is chosen, and

an output is collected).

•

are the “Bell rounds”, selected to perform parameter estima

tion. They are chosen uniformly at

random under the constraint that

, for some

specified in the protocol.

•

is the tolerated error rate: the protocol aborts as soon as th

e fraction of rounds in

satisfying the

CHSH condition is lower than

opt

−

•

⊆

[

]

are the “check rounds”. Those are rounds in which the inputs t

(

)

are

(

2, 1

)

. Since the

inputs are chosen uniformly at random, the number of check ro

unds

is highly concentrated around

•

The target min-entropy rate

. This is the rate of min-entropy that the users Alice and Bob e

xpect to

be present in the check rounds, provided the protocol did not

abort. Once information reconciliation

and privacy amplification have been performed, a secret key o

f length roughly

(

−

(

))

will

be produced.

•

is the security parameter: the statistical distance from un

iform of the extracted key (conditioned on

the eavesdropper’s side information). Precisely, if

denotes the system containing the extracted key,

we will obtain that

′

−

⊗

′

≤

, where

′

is a register containing all the side information

available to an arbitrary quantum eavesdropper in the proto

col, and

is the totally mixed state on

as qubits as the key length.

3 Analysis of the key distribution protocol

The analysis of Protocol A, and the proof of Theorem 1, is perf

ormed in two steps. The first, main step

consists in proving a lower bound on the quantum smooth condi

tional min-entropy

min

(

XYA

)

of the outputs obtained by Bob in the check rounds

(conditioned on the protocol not aborting). This lower

bound will depend on the maximal error rate

that is tolerated by the users in the sub-protocol B (see Fig-

ures 1 and 2 for a description of protocols A and B respectivel

y). Here the lower bound is taken conditioned

on the state of an arbitrary quantum adversary (whom we will c

all Eve and refer to indiscriminately as “the

Protocol A

1. Let

and

be parameters given as input. Let

be the constant from Theorem 8, and set

= (

)

(

)

2. Alice and Bob run Protocol B for

steps, choosing inputs

∈ {

0, 1, 2

}

(resp.

∈ {

0, 1

}

) and

obtaining outcomes

∈ {

0, 1

}

(resp.

∈ {

0, 1

}

). Let

be the set of rounds that were chosen to

perform parameter estimation.

3. Alice and Bob publicly reveal their choices of inputs. Let

be the set of rounds

in which

(

) =

(

2, 1

)

. If

| −

√

they abort the protocol.

4. Alice and Bob perform information reconciliation on thei

r outputs in

−

, which constitute the raw

key. For this, Bob sends a message of

ℓ

≤

(

)

log

(

)

bits to Alice.

5. Let

(

)

be as specified in Theorem 8. Alice and Bob perform privacy amp

lification using e.g.

two-universal hashing, extracting a shared key of length

(

−

(

)

−

(

log

(

)

))

from

the common

(

| − |

)

-bit string they obtained at the end of the previous step.

Figure 1: The device-independent key distribution protoco

l, Protocol A

Protocol B

1. Let

and

be parameters given as input.

2. Repeat, for

1, . . . ,

2.1 Alice picks

∈ {

0, 1, 2

}

, and Bob picks

∈ {

0, 1

}

, uniformly at random. They input

into their respective device, obtaining outputs

∈ {

0, 1

}

respectively.

3. Alice chooses a random subset

⊆

[

]

of size

and shares it publicly with Bob. Alice and

Bob announce their input/output pairs in

, and compute the fraction of pairs satisfying the CHSH

condition. Let

(

opt

−

′

)

be this fraction. If

′

they abort the protocol.

Figure 2: Theorem 8 shows that, at the end of protocol B, the bi

generated by Bob’s device in the

check rounds

both have high smooth min-entropy, conditioned on the adver

sary’s arbitrary quantum side

information.

adversary” or “the eavesdropper”) in the protocol, who has a

ccess to the information

revealed

publicly in the course of the protocol, as well as to a quantum

system

which may be correlated with the

systems

of the devices. Such an estimate is stated in Theorem 8 in Sect

ion 3.3 below.

The second step consists in showing that there exists approp

riate protocols for the information reconcil-

iation and privacy amplification steps, Steps 4 and 5 in Proto

col A respectively, such that the lower bound

on the conditional min-entropy from the first step guarantee

s the security (distance from uniform from the

point of view of the adversary) and correctness (Alice and Bo

b should obtain the same key) of the key that

is extracted. This step is standard, and all the ingredients

required already appear in the literature. We

summarize the result as Lemma 4 in Section 3.2 below.

Theorem 1 follows immediately by combining Theorem 8 and Lem

ma 4.

3.1 Probability space

Before stating and proving formally our results, we formall

y define the random variables and events that

will be used in their proof.

Modeling the devices.

Fix a pair of spatially isolated devices

(

)

. Device

takes inputs in

{

0, 1, 2

}

and device

takes inputs in

{

0, 1

}

. Whenever provided an input, each device produces an output

{

0, 1

}

The devices may be used repeatedly. We will assume that the pa

(

)

can be described by quantum

mechanics: the devices are modeled by a pair of quantum regis

ters; when provided an input each device

performs a measurement on the state contained in the corresp

onding subsystem.

We assume that user Alice holds

, and Bob is given

. In addition, there is an adversary Eve who

holds an additional quantum register

, initialized in a state arbitrarily correlated with that of

and

. Let

be the density matrix describing the joint state of all three

registers at the start of the protocol.

We define the following random variables and events.

∈ {

0, 1, 2

}

and

∈ {

0, 1

}

are two uni-

formly distributed random variables, used to represent the

inputs to

respectively, as chosen in the

protocol.

∈ {

0, 1

}

are random variables denoting the outputs produced by the de

vices, when se-

quentially provided their respective inputs

. We will always use

⊆

[

]

to denote the set of “check”

rounds, in which

(

) = (

2, 1

)

, and

⊆

[

]

the set of “Bell” rounds chosen by Alice and Bob to

perform parameter estimation.

Let

denote the reduced state of devices

and

in the

-th round of the protocol (before they have

been provided their

-th input). Formally,

∝

(

∏

⊗

)

(

∏

(

)

†

⊗

(

)

†

)

where

{

}

and

{

}

are the Kraus operators corresponding to the measurement pe

rformed by devices

and

in round

respectively, and

is normalized. Here

(

)

is the reduced state

of the devices at the start of the protocol. It is important to

note that for any

the state

may depend on

a measurement that is performed on system

as soon as a particular outcome of that measurement is fixed.

Measuring the CHSH condition.

Given a set

⊆

[

]

and

, CHSH

(

)

is the event that the

tuple

(

)

satisfies the CHSH condition (as described in Section 2) in a f

raction at least

opt

−

the rounds indicated by

. If

is omitted, CHSH

(

) =

CHSH

([

]

)

. Letting

∈ {

0, 1

}

be the

indicator random variable of the CHSH condition

not

being satisfied in any given round, we can write

CHSH

(

)

≡

{

∑

∈

≤

(

−

opt

) +

}

We also define VIOL

(

)

, where

∈

[

]

, to express the expected amount by which the CHSH condition

in round

is satisfied:

VIOL

(

) =

[

]

−

(

−

opt

)

where here the expectation is taken over the choice of inputs

(

)

in round

, and over the randomness

in the devices’ own measurements in round

. Note that VIOL

(

)

implicitly depends on the specific state

of the devices in round

, which may be affected by previous input and outputs obtaine

d in the protocol

as well as on other events that may be conditioned on. Hence th

e expression

(

VIOL

(

)

, for

some event

, indicates the average probability, over all possible

∈

, that the devices satisfy the CHSH

condition in round

with probability at least

opt

−

, provided their inputs are distributed according to the

conditional distribution

(

)

, and when performed on the post-measurement state of

A ⊗ B

round

conditioned on

. For any

we let VIOL

(

)

be the event that

(

)

∑

VIOL

(

)

≤

The adversary.

We introduce additional random variables that depend on the

adversary Eve, holding the

quantum register

. The adversary is described in Lemma 9 below; to understand t

he events below it may

be useful to read that lemma’s statement first.

Let

∈ {

0, 1

}

be the random variable that describes the outcome of the meas

urement on

described

in Lemma 9. Note that this outcome depends on the “advice” tha

t is given to the adversary. We use

denote the inputs that are given to the adversary, and

∈ {

0, 1

}

to denote the additional advice bits.

These random variables need not equal the actual values

: in general, the adversary’s measure-

ment is well-defined for any given advice bits, and

is used to denote its outcome irrespective of whether

the advice given was “correct” or not. For any

∈

[

]

, define GUESS

(

)

∈ {

0, 1

}

to be

if and only if,

either

∈

and

, or

∈

, and let GUESS

∧

GUESS

(

)

3.2 Information reconciliation and privacy amplification

For convenience, we let

′

XYA

denote the side information available to the eavesdropper.

show the following lemma, whose proof follows from standard

arguments in the analysis of QKD protocols

(see e.g. [Ren05]). We provide the relevant details below.

Lemma 4.

Let

. Let

′

−

/400

. Suppose that, after Step 2 of Protocol A, the condition

min

(

′

)

≥

is satisfied. Then with probability at least

−

′

, at the end of the protocol Alice and

Bob have a common shared key that is

-close to uniform and has length

min

(

′

)

−

(

1.1

)

| −

4 log

(

)

Information reconciliation.

We first analyze the information reconciliation step. The fo

llowing lemma

states the conditions that are required for there to exist a s

atisfactory information reconciliation procedure.

Lemma 5

(Lemma 6.3.4 in [Ren05])

Let

∈ {

0, 1

}

be two random variables, and

. Suppose

Alice holds

, and Bob holds

. There is an information reconciliation protocol in which B

ob communicates

ℓ

≤

max

(

) +

log

(

)

bits of information about

to Alice and is such that with probability at least

−

Alice and Bob both know

at the end of the protocol.

To apply Lemma 5 it suffices to prove an upper bound on the condi

tional max-entropy

max

(

)

By definition of the rounds

, the CHSH condition in those rounds imposes that

for all

∈

Hence, were it not for errors, we would have

max

(

) =

. The following claim shows that the bound

on the error rate that results from the estimation performed

in the rounds

in Step 3 of Protocol B is enough

to guarantee a good upper bound on the conditional max-entro

py.

Claim 6.

Suppose Alice and Bob do not abort after Step 3 in Protocol B. L

be the set of check rounds,

as designated in Step 4 of Protocol A. Then

′

max

(

)

≤

(

1.1

)

, where

′

−

/400

Proof.

Fix the set

. The set

chosen by Alice and Bob to perform parameter estimation cont

ains a fraction

at least

of the rounds in

, except with probability at most

−

. The protocol is aborted as soon as

more than an

fraction of those rounds are such that

. Hence with probability at least

−

/200

the total fraction of errors in

is at most

1.1

. In particular, with probability at least

−

/400

over

, with probability at least

−

/400

will take on at most

(

1.1

)

values.

Privacy amplification.

The following lemma states the existence of a good protocol f

or privacy amplifi-

cation.

Lemma 7

(Lemma 6.4.1 in [Ren05])

Suppose the information reconciliation protocol requires

at most

ℓ

bits of communication. Then for any

there is a privacy amplification protocol based on two-unive

rsal

hashing which extracts

min

(

′

)

−

ℓ

−

2 log

(

)

bits of key.

Lemma 4 now follows directly by combining Claim 6 with Lemma 7

and the assumption on the condi-

tional min-entropy placed in the lemma.

3.3 A lower bound on the conditional min-entropy

The main result of this section is a lower bound on the conditi

onal smooth min-entropy H

min

(

XYA

)

of the raw key.

Theorem 8.

Let

be given. There exists positive constants

(possibly depending on

) such

that the following hold. Let

be an integer and

≥

−

be given. Let

= (

)

(

)

be as

specified in Protocol A (Figure 1). Let

be any constant such that

(

√

−

)

(

4 ln

(

))

−

(

4/ ln

(

))

Suppose that the devices

are such that with probability at least

the protocol does not abort.

Let

be an auxiliary system held by an eavesdropper, who may also l

earn

(

)

and

(

)

. Then,

conditioned on the protocol not aborting, it holds that

min

(

XYA

)

≥

| −

(

)

We note that the precise relation between the parameters

and

stated in the theorem is the one that

we obtain from our proof; however we have not attempted to opt

imize it fully and it is likely that one may

be able to derive a better dependency. It is also clear from th

e proof that one may trade off the different

constants between each other, depending on whether one is in

terested in the maximum possible key rate in

the presence of very small noise, or to the opposite if one wis

hes to tolerate as much noise as possible.

The proof of Theorem 8 is based on three lemmas. We state the le

mmas first, and derive the theorem

from them below.

3.3.1

The reconstruction lemma

Our first lemma states that, if the min-entropy condition in t

he conclusion of the theorem is not satisfied,

then there must exist a measurement on the system

, depending on

and

, together with some

additional “advice” bits of information about

, whose outcome

∈ {

0, 1

}

agrees with

with non-

negligible probability.

Lemma 9.

Let

and suppose that

min

(

XYA

)

. Then there exists an

(

log

(

)

and a function

{

0, 1

}

→ {

0, 1

}

(

−

)

such that, given the bits

(

)

∈ {

0, 1

}

together with the inputs

, there exists a measurement on

that outputs a

string

∈ {

0, 1

}

such that with probability (over the randomness in

and in the measurement) at least

(

)

, where

is a universal constant, the equality

holds.

The proof of Lemma 9 is based on a “reconstruction”-type argu

ment from [DPVR12]. A very similar

argument was already used to establish an analogous lemma in

[VV11]. We give the proof of Lemma 9 in

Section 5.

3.3.2

Existence of a good round

Our second lemma states the existence of a “good” round

∈

[

]

in which both the CHSH condition is

satisfied, and the outcome

of the measurement described in Lemma 9 agrees with

, with good prob-

ability. Note also the additional condition (2) in the lemma

, which states that systems

and

are each

close to being independent from the random variables

describing the choice of inputs in round

This condition is necessary for condition (3), on the CHSH vi

olation, to be of any use: indeed, without (2)

it could in principle be that the conditioning on specific out

comes in previous rounds, including the adver-

sary’s outcomes, completely fixes the choice of inputs in the

-th round. Conditions (2)–(4) in the lemma

correspond to conditions (i)–(iii) discussed in Section 1.

Eq. (2) implies that the distribution that arises from the de

vices’ measurements on the states

is,

while not necessarily quantum, still no-signalling, and th

is is all that is required for the application of the

guessing lemma, Lemma 11 below. As explained in the introduc

tion, proving this condition is an impor-

tant point of departure of our proof from previous approache

s, which used an assumption of independence

between the devices or a limitation of the adversary in order

to automatically obtain that (an even stronger

form of) the condition held in all rounds without requiring a

ny conditioning.

We refer to Section 3.1 for a description of the events CHSH

and VIOL

appearing in the statement

of the lemma.

Lemma 10.

Let

be uniformly distributed in

{

0, 1

}

, and

be such that the following holds:

(

CHSH

(

)

∧

GUESS

)

≥

and let

. Then there exists a universal constant

, a

≤

√

log

(

)

, an

∈

[

]

and a set

⊆

(

{

0, 1, 2

} × {

0, 1

} × {

0, 1

}

)

−

such that for every

(

)

∈

, there is

a choice of

and an

consistent with

((

)

(

)

such that the following hold:

max

{

∥

−

⊗

(

∑

)

∥

−

⊗

(

∑

)

∥

}

≤

(2)

VIOL

(

)

≤

(3)

(

GUESS

(

))

≥

−

12 ln

(

)

−

(4)

where in

(2)

the state

is the (normalized) state of the corresponding systems in ro

und

, con-

ditioned on

(

)

, and similarly in

(3)

and

(4)

the violation is estimated conditioned on previous

input/outputs to the devices being

(

)

, and on Eve making her measurement based on the inputs

(

, 2,

)

and

(

, 1,

)

and advice string

, and obtaining outcomes

as her prediction in rounds

∩ {

1, . . . ,

−

}

The proof of Lemma 10 in given in Section 4.

3.3.3

The guessing lemma

We state the last lemma required for the proof of Theorem 8. A s

imilar lemma already appeared in [VV11].

Here we give a slightly more general version of the lemma stat

ed in a form that can be directly used in the

proof of the theorem.

Lemma 11

(Guessing lemma)

Let

. Suppose given six bipartite states

, where

∈ {

0, 1, 2

}

∈ {

0, 1

}

, such that the following hold:

1. If

= (

1/6

)

∑

(

)

and

= (

1/6

)

∑

(

)

∑

∥

−

∥

≤

and

∑

∥

−

∥

≤

(5)

2. There exists observables

−

respectively that satisfy

(

⊗

)

(

⊗

)

(

⊗

)

−

(

⊗

)

≥

√

−

3. Bob’s measurement

produces outcome

∈ {

0, 1

}

with probability

−

, when performed on his

share of

((

⊗

)

≥

−

Then the condition

≥

(

√

−

)

−

must hold.

Proof.

For every

(

)

∈ {

0, 1

}

× {

0, 1, 2

} × {

0, 1

}

let

(

)

((

⊗

)

. Con-

dition (5) implies that the distribution

is approximately no-signalling, in the following sense: on

average

over the choice of a uniformly random pair

(

)

, the statistical distance

∑

∣

∑

(

)

−

∑

′

(

∑

(

′

)

∣

≤

∑

∣

(

⊗

)(

−

)

∣

≤

∑

∥

−

∥

≤

and a similar bound holds for the marginals on

. Lemma 9.5 in [Hol09] implies that there exists a distribu-

tion

(

)

such that

is (perfectly) no-signalling, and moreover, on average ove

(

)

the statistical

distance

(

·|

)

−

(

·|

)

≤

. In particular, the second assumption in the lemma implies t

hat

the distribution

must violate the CHSH inequality by at least

√

2/2

−

, and the third assump-

tion implies that

∑

(

, 1

2, 1

)

≥

−

. Applying the bound (A.11) derived in the supplementary

information to [PAM

10] with

√

2/2

−

we obtain the inequality claimed in the lemma.

3.3.4

Proof of Theorem 8

We give the proof of Theorem 8, assuming the lemmas stated in t

he three previous subsections.

Proof of Theorem 8.

Let

(

)

be random variables describing Alice and Bob’s choice of inp

uts to

and

respectively, and the outputs obtained, in an execution of P

rotocol A. Let

(

)

be the random

variable that describes the outcome of the measurement on

described in Lemma 9, when the advice bits

are selected uniformly at random (independently from

and

). Denote by A

(

)

the “correct” advice bits.

The proof proceeds by contradiction. Assume that there exis

ted a pair of devices

(

)

such that

(

CHSH

(

)

≥

min

(

XYA

)

(6)

where

are as in the statement of the theorem. Denote GUESS

(

)

the event that

. Using

Lemma 9, we deduce from (6) that the following must hold:

(

CHSH

(

)

∧

GUESS

(

)

(

GUESS

(

)

CHSH

(

)

(

CHSH

(

)

≥

(

)

(7)

where

is the constant from Lemma 9. Since the rounds

are chosen uniformly at random, Claim 12

below states that, for any

≤

(

CHSH

((

)

CHSH

(

)

≥

−

(8)

where

. Choose

1/3

, and let

′

. Provided

is chosen large enough, the choice of

made in the theorem is such that

≥

log

(

)

((

2/9

)

, so that

−

≤

(

)

Hence we obtain the following by combining (7) and (8):

(

CHSH

(

′

)

∧

GUESS

(

)

≥

(

)) =

′

(9)

We may now apply Lemma 10. Let

√

log

(

′

)

, and

∈

[

]

be the “good” round that is

promised by the lemma. We proceed to show that the existence o

f such a round leads to a contradiction by

appealing to the guessing lemma, Lemma 11.

Consider the following setup. Alice, Bob and Eve prepare the

ir devices by selecting a random string of

inputs

for Eve, except that

and

always. Eve guesses the advice bits

at random

and makes a prediction

. Alice and Bob then use their devices up to round

−

by choosing inputs

(

) = (

)

. They verify that the resulting outputs

are such that

(

)

∈

;

if not they abort. Upon having succeeded in this conditionin

g they separate and play the guessing game.

Alice holds system

, while Bob holds system

Lemma 10 shows that all conditions in Lemma 11 are satisfied: a

s a result, it must be that

12 ln

(

)

≥

(

√

−

′

−

)

−

By definition, provided the constant

is large enough we have

≤

, where we used that

| ≤

√

(

√

(

))

, as enforced in the protocol, and

′

4/3

. Re-arranging

terms and using the definition of

and

we obtain the condition

√

−

4 ln

(

)

−

(

)

−

(

log

(

)

which, given the choice of

made in the theorem, is a contradiction provided

is chosen small enough.

Claim 12.

Let

. The following holds for any

≤

(

CHSH

((

)

CHSH

(

)

≥

−

where the probability is taken over the choice of a random sub

set

⊆

[

]

of size

Proof.

Consider a given run of the protocol. Suppose that the fracti

on of rounds in which the CHSH

condition is not satisfied is at least

(

−

opt

) + (

)

. By a standard Chernoff bound, a randomly

chosen set

⊆

[

]

will of size

will have at least

((

−

opt

) +

)

of its rounds with inputs

corresponding to the CHSH condition being violated, except

with probability at most

−

4 Proof of Lemma 10

This section is devoted to the proof of Lemma 10. Let

be the event CHSH

(

)

∧

GUESS

: the main

assumption of the lemma states that

(

)

≥

. We first prove two preliminary claims which

establish that, provided

is not too small, conditioning on

does not affect either the distribution of inputs

(

)

or the reduced density matrices of the inner state of each dev

ice’s system in most rounds

by too

much.

Claim 13.

Suppose that, in Protocol B, Alice and Bob choose inputs

(

)

∈ {

0, 1, 2

}

× {

0, 1

}

uni-

formly at random, obtaining outcomes

∈ {

0, 1

}

. Suppose that

is measured using Eve’s guessing

measurement (as described in Lemma 9) with inputs

(

) = (

)

and advice bits

, re-

sulting in an outcome

∈ {

0, 1

}

. Let

be the marginal distribution of the inputs in the

-th round,

conditioned on

(

) = (

)

∈

, the projection of

on the first

(

−

)

coordinates. Then the following bound holds on expectation

over

(

)

∑

∥

−

∥

≤

√

log

(

)

where

is the uniform distribution on

{

0, 1, 2

} × {

0, 1

}

Proof.

The Shannon entropy

(

) =

log

(

)

, and conditioned on

(

)

≥

log

(

)

−

log

(

)

. Applying the chain rule,

∑

(

)

≥

log

(

)

−

log

(

)

Using the classical Pinsker’s inequality as

−

≤

√

(

log

(

)

−

(

))

and Jensen’s

inequality we get

∑

∥

−

∥

≤

√

log

(

)

proving the claim.

The fact that

depends both on the choice of inputs

(

)

and on the adversary’s measurement out-

come implies that conditioning on

could not only bias the distribution of

(

)

but also introduce cor-

relations between

(

)

and the reduced state

of the devices. The following claim shows that, if

is an event with large enough probability, the correlations

introduced by this conditioning do not affect the

reduced state on either

by too much, for most rounds

Claim 14.

Consider the same situation as described in Claim 13. Let

denote the reduced den-

sity of the joint state of systems

(in round

) and

, conditioned on

(

) =

(

)

∈

. Then the following holds on expectation over

(

)

∑

∥

−

⊗

(

∑

)

∥

≤

√

log

(

)

(10)

Moreover, the same bound holds when

is replaced by

Proof.

We use Claim 27. Alice’s sequential measurements are taken t

o be the ones performed on

, while

Bob’s measurement is the combination of the measurements on

, together with Eve’s measurement, on

inputs

and advice bits

obtained from

. We set

in the claim to be

here, and the

outcomes

in the claim to

here. Together with the assumption

(

)

≥

, the claim

shows that

∑

(

;

)

≤

log

(

)

Using Pinsker’s inequality (1) together with Jensen’s ineq

uality,

∑

∥

−

⊗

(

∑

)

∥

≤

√

log

(

)

where we used Claim 13 to show that the marginal distribution

(

)

is close to uniform on

{

0, 1, 2

} ×

{

0, 1

}

, even conditioned on

The following claim replaces the event that the CHSH conditi

on is satisfied in a large fraction of rounds

by the event that their exists many rounds in which the CHSH co

ndition is

likely

to be satisfied (when

evaluated on the state of the devices in that round).

Claim 15.

There exists a set

⊆

[

]

such that

| ≥

, and a subset

′

⊆

such that

(

′

)

≥

1/2

and for every

∈

, conditioned on

and on inputs and outputs to the devices in rounds

prior to

being in

′

, the condition

VIOL

(

)

≤

√

(

)

holds.

Proof.

Let

∈ {

0, 1

}

if and only if the CHSH condition is not satisfied in round

. By definition,

[

] = (

−

opt

) +

VIOL

(

)

. Let

[

]

−

and

≤

· · ·

(

≤

)

is a

Martingale, and by Azuma’s inequality, for any

(

∑

VIOL

(

) + (

−

opt

)

∑

)

(

∑

)

≤

−

Since the string

is chosen by the adversary uniformly at random, we may furthe

r condition the equa-

tions above on

without affecting their validity. Note that the event CHSH

(

)

is equivalent

∑

≤

(

−

opt

) +

. Choosing

√

2 ln

(

)

, so that

−

, and using the

assumption

(

)

≥

to further condition on

CHSH

(

)

∧

GUESS

we get

(

∑

VIOL

(

)

∣

)

≤

1/2.

The quantity VIOL

(

)

is a nonnegative number which only depends on the state of the

devices in round

, itself only depending on the string of inputs and outputs ob

served thus far. Applying Markov’s inequality,

the condition above implies that there is a set

⊆

[

]

of size

| ≥

and a subset

′

⊆

of size

(

′

)

≥

1/2

such that for every

∈

it holds that VIOL

(

)

≤

(

)

, provided previous inputs

and outputs of the devices were in

′

Proof of Lemma 10.

Let

′

be the set from Claim 15. Consider the state of the devices

and

in an arbi-

trary round

of the protocol. By applying Markov’s inequality to the boun

d (10) from Claim 14, we obtain a

set

′

| ⊆

[

]

of size

′

| ≥

/12

and a subset

′′

⊆

′

satisfying

(

′′

′

)

≥

1/2

such that, for ev-

ery

∈

′

, conditioned on

and

(

) = (

)

∈

′′

both bounds

∥

−

⊗

(

∑

)

∥

≤

200

√

log

(

)

and the analogous bound where

is replaced by

hold. Letting

′′

′

∩

, where

is the set from

Claim 15, both the bound above and the condition VIOL

(

)

≤

√

(

)

hold simultaneously

in the rounds from

′′

(conditioned on previous inputs and outputs being in

′′

). Furthermore, note that

whether both conditions are satisfied or not only depends on t

he (post-selected) state of the protocol in round

, itself only depending on subsequent choices of inputs and o

utputs in the protocol to the extent that the

condition

is satisfied. Hence as long as the advice bits

that Eve uses to select the mea-

surement on her system have a positive probability of being t

he correct advice bits, given the data generated

up to round

−

, both bounds must hold verbatim. As a consequence, for any fix

(

)

∈

′′

there exists a string

(

)

from which advice bits

can be computed such that if Eve