Private Quantum Key Distribution (QKD)

In a previous lecture we discussed two types of secure communication protocols, Public Key and Private Key methods. We discussed the former at length and in this lecture we will discuss how Quantum Mechanics can also provide a mechanism for secure  single pad encryption.

Private key encryption

Suppose Alice wants to send a secure message to Bob, she encrypts it using a private 
key. First she takes a message and encodes it as a set of bits. Bob, as well as everyone else, knows
how to convert those bits back into a message (Examples: Bits on a CD translate into music, bits on the Internet translate into alphanumeric characters on your screen etc.) Alice wants Bob to get those
bits, but she is a wary of Eve who is eavesdropping and can intercept that message. So Alice makes a key. Example

Alicemessage={0,1,1,0,1,0,1,1,1,1,0,0};
Dimensions[Alicemessage]

So how does Alice encrypt this ? Since the message contains 12 bits, she generates a set of 12 random bits and adds them, using modular arithmetic, to her message.

key=Table[Random[Integer],{i,1,12}]
Dimensions[key]

encryptedmessage=Mod[Alicemessage+key,2]

If  Eve intercepts this message, it will be very difficult for her to decrypt it because it is really a set
of random bits, since a modular sum of random bits with anything else is also random. However
if Alice re-uses this key for other message, Eve can study the intercepted messages for patterns and
be able to eventually "guess" what the key is. Therefore, Alice should only use this key once, and
generate another random key for the other messages. This is therefore called a one time pad.
So Alice feels secure with her one time pad, but how will Bob be able to decrypt her message?

Easy, if Alice sent Bob her one-time pad by secret courier etc. He does the following

Bobsmessage=Mod[encryptedmessage-key,2]

Bobsmessage==Alicemessage

Now maybe Alice's courier is loyal, discreet and does not sell the key to Eve, but you never know. 
Because it is a one time pad, every time Alice wants to send a private message, she needs to generate a new key, and have the courier deliver it. This can get expensive, so what is Alice to do? 
She is faced with the Private Key Distribution problem. Quantum Mechanics can come to the rescue.

In 1992 Artur Ekart developed a private key distribution protocol that is based on the availability of  EPR pairs or Bell states. Prior to that, in 1984, Charles Bennet (at IBM) and Gilles Brassard introduced an implementation, of an idea first put forward by Stephen Wiesner in 1970,  for quantum key distribution (QKD). Today it is called the BB84 protocol and has already found  use in industry and government.

BB84 Protocol

Alice first produces her key based on random bits. She then encodes these bits in terms of
the states |0⟩ and |1⟩, i.e. our computational basis. She needs some sort of qubit (i.e. electron, photon, etc. ) to hold this information. So in the computational basis Alice makes the association

|0⟩ ⟶ 0
|1⟩ ⟶ 1

Her measurements are performed by the gate (1/2)- (1/2)S(θ=0,ϕ=0) ≡ (Subscript[G, 3]).  However we learned
that the following states  

H|0⟩ = (1/(Sqrt[2])) ( |0⟩+ |1⟩) 
H|1⟩= (1/(Sqrt[2])) ( |0⟩ -  |1⟩) 

are eigenstates of the measuring device S(θ=Pi/2,ϕ=0). So Alice can also decide to encode
her 0,1 bits in terms of the new basis  H|0⟩,  H|1⟩  by using the gate (Subscript[G, 1])=(1/2)- (1/2)S(θ=(π/2),ϕ=0)=
H (Subscript[G, 3]) (SuperDagger[H])

H|0⟩  ⟶  0
H|1⟩  ⟶  1

(* bits 0, 1 encoded in the computational basis *)
c[0]={1,0};
c[1]={0,1};

unit={{1,0},{0,1}};
G3=1/2 unit-1/2{{1,0},{0,-1}};

G3.c[0]==0 c[0]
G3.c[1]==1 c[1]

(* bits encoded in the new basis  H|0⟩ H|1⟩ *)

H=1/Sqrt[2] {{1,1},{1,-1}};

d[0]=H.{1,0};
d[1]=H.{0,1};

MatrixForm[d[0]]
MatrixForm[d[1]]

G1=H.G3.Transpose[H];

G1.d[0]==0 d[0]
G1.d[1]==1 d[1]

Suppose Alice sends a 5 bit string 01100 in terms of her computational basis, she loads her qubits in the following way

Qubitstring={c[0],c[1],c[1],c[0],c[0]}

Note that this qubit string is not a direct product, since we are not sending a coherent state
|0 1 1 0 0 ⟩.  Instead we are sending individual qubits one-at-time. ( The best way to handle such ensembles is through the use of density matrices)

Bob receives this qubit string and measures each individual qubit. But which device should he use? 
Since he knows that Alice encoded each bit using device (Subscript[G, 3]) he will measure each qubit using that
device.

Now because Bob knows quantum mechanics and he realizes that a measurement on a qubit
will always result in the value 0,1 (the eigenvalues of both (Subscript[G, 1]) and (Subscript[G, 3])) but with different probabilities,
given by the Born rule.

So measuring qubit 1 Bob knows its either going to be a 0 or 1, but which one.
One the average he will get for measurement of bit1

⟨ψ | (Subscript[G, 3]) | ψ⟩

EG3[bit_]:=Qubitstring[[bit]].G3.Qubitstring[[bit]]

EG3[1]
EG3[2]
EG3[3]
EG3[4]
EG3[5]

Notice that Bob either gets 0, and 1 for the expectation values. This implies that the results
are 100% certain. Why is that?

Now, suppose that Alice chooses to encode her bits in the following way

Qubitstring={c[0],d[1],c[1],d[0],c[0]}

This is the same bit string as before, but she did not always use the computational basis. For
the second and fourth bit she decided to use the (Subscript[G, 1]) basis to encode her 0 and 1.  Suppose
Alice did not tell Bob what she did, and again he uses the (Subscript[G, 3]) device to measure her qubits.
The average value for these measurements, are now

EG3[1]
EG3[2]
EG3[3]
EG3[4]
EG3[5]

Notice that the bits 2 and 4 no longer have the absolute expectation values of 0,1 because Bob
is using the wrong measuring device. So sometimes he gets the correct result for bits 2 and 4 and sometimes he gets the wrong result.  

However if Alice called him up beforehand and told him; "Bob, for bit 2 and 4 use (Subscript[G, 3]) not (Subscript[G, 1])”  he would use the following measuring scheme

EG1[bit_]:=Qubitstring[[bit]].G1.Qubitstring[[bit]]

EG3[1]
EG1[2]
EG3[3]
EG1[4]
EG3[5]

And we get perfect correlation again. So in order to get the right key Bob has to know which basis
instruments (Subscript[G, 1]), (Subscript[G, 3]) Alice is encoding her 0,1's.

Question I: Alice decides to randomly choose (Subscript[G, 1]) as her encoding scheme 50% of the time and
(Subscript[G, 3]) the other 50%.  Bob knows this and so decides to also pick  (Subscript[G, 1]) and  (Subscript[G, 3]) randomly about 1/2 the time each.

What percentage of time did Bob make the correct choice for the measuring device?

Question II:  For the cases he made the incorrect guess can he still get a correct answer?

Question III:  Overall what is the success rate for Bob in guessing the correct key?

Now this is not a perfect key, so Alice calls Bob on a public channel, and tells him which
qubits have been generated using either (Subscript[G, 1])or  (Subscript[G, 3]) but, of course, does not tell him the individual
values for the qubits. From those qubits which Alice's choice and Bob's choice agree, Bob can
be sure that the resulting bit values are correct. Bob then calls Alice, again on an insecure channel,
and tells her which Qbits measurement agrees with her measurement. With this joint information
they generate a one time key pad which they share.

So in the example above, Bob might receive the following string from his random measurements
{0,1,0,0,0}.  Assuming he used (Subscript[G, 3]) for every measurement. Subsequently Alice calls him and gives him the following information on an insecure channel {(Subscript[G, 3]),(Subscript[G, 1]),(Subscript[G, 3]),(Subscript[G, 1]),(Subscript[G, 3])}.  So now, he knows that qubit 2,4 are uncertain, and he throws them
away. He is now left with the following data {0,0,0}, having excised qubits 2,4. He calls back Alice and tells her that his qubits 2 and 4 have been dismissed. So she does the same and takes her original key {0,1,0,1,0} and excises qubit
2,4 to get {0,0,0}. Now Alice and Bob have identical keys, which can be used to encrypt, in this case, a smaller, 3 bit message.

Now the important question here is; how is this secure from Eve who is eavesdropping?

When Alice sends her  key

Qubitstring

Eve intercepts it, but she does not know which instruments Alice used  Suppose Eve chooses
the sequence (Subscript[G, 3]) (Subscript[G, 3]) (Subscript[G, 1]) (Subscript[G, 1]) (Subscript[G, 3]).  That is she uses (Subscript[G, 3]) on the first qubit. Since {1,0} is an eigenstate
of (Subscript[G, 3]) for the first qubit Eve will measure 0. For the second qubit she again uses (Subscript[G, 3])but this time
she will get either 0,1 because {(1/(Sqrt[2])),-(1/(Sqrt[2]))} is an eigenstate of (Subscript[G, 1]) not (Subscript[G, 3]). Suppose she gets
the value 1, and {(1/(Sqrt[2])),-(1/(Sqrt[2]))} will then collapse into {0,1}. For the third qubit Eve chooses
(Subscript[G, 1]) and will again get either 1,0. Suppose she gets 1, since she used the (Subscript[G, 1]) basis, that state must
collapse into {(1/(Sqrt[2])),-(1/(Sqrt[2]))}.  For the fourth qubit Eve chose correctly and that state stays the same.
Likewise so does the fifth qubit.

So after Eve's interception the original qubit string from Alice looks like

Evestring={{1,0},{0,1},{(1/(Sqrt[2])),-(1/(Sqrt[2]))},{(1/(Sqrt[2])),(1/(Sqrt[2]))},{1,0}}

So if Bob measures this bit string, which is different from the one Alice sent, the expectation value
of his measurements would be

EG3[bit_]:=Evestring[[bit]].G3.Evestring[[bit]]

EG3[1]
EG3[2]
EG3[3]
EG3[4]
EG3[5]

Notice now that Bob is only certain for qubits 1,2,4 since Eve disturbed the others by using
a different instrument. After the measurement Bob tells Alice that he measured the sequence {(Subscript[G, 3]),(Subscript[G, 3]),(Subscript[G, 3]),(Subscript[G, 3]),(Subscript[G, 3])} and  he also told her, on this insecure line, that he obtained the result {0,1,1,1,0}  (there are other possible results, can you itemize them?) . Alice compares the data {0,1,0,1,0} she sent and realizes that Bob should have gotten the value 1 for qubit 3, since Bob did use the correct measuring device for this qubits. Alice concludes that the only way Bob could get this error is by an  eavesdropping  Eve.

Diagram from Knight & Munro 2003

Ekert Protocol

In 1991 Artur Ekert proposed a QKD scheme using a Bell pair of particles.
Suppose the pair is found in the singlet state

 |ψ⟩ = (1/(Sqrt[2])) |01⟩ - (1/(Sqrt[2]))|1 0⟩
 
 Alice can measure the value of the spin projection  S·(Subscript[n, a])  where (Subscript[n, a]) is the direction
 of Alice’s measuring device. Likewise Bob measures  S·(Subscript[n, b]) where (Subscript[n, b]) is the direction
 of Bob’s measuring device. They both agree to randomly choose among 2 directions, along
 the z-axis, and along the x-axis. So sometimes their choice of axis agree, i.e. both
 choose either z- or x. Other times they disagree, Bob chooses x, and Alice chooses the z and
 visa versa. The expectation value for the correlation is
 
 ⟨ψ| (Subscript[S, a])·(Subscript[n, a]) (Subscript[S, b])·(Subscript[n, b]) |ψ⟩ = - (Subscript[n, a])·(Subscript[n, b])

Proof:

S[θ_,ϕ_]={{Cos[θ],Exp[-I ϕ]Sin[θ]},{Exp[I ϕ]Sin[θ],-Cos[θ]}};
psi=1/Sqrt[2](Flatten[KroneckerProduct[{1,0},{0,1}]]-Flatten[KroneckerProduct[{0,1},{1,0}]]);

SaSb=KroneckerProduct[S[θa,ϕa],S[θb,ϕb]];
MatrixForm[SaSb]

FullSimplify[psi.SaSb.psi]

na={Sin[θa]Cos[ϕa],Sin[θa]Sin[ϕa],Cos[θa]};
nb= {Sin[θb]Cos[ϕb],Sin[θb]Sin[ϕb],Cos[θb]};
FullSimplify[na.nb]

QED

Therefore,  if  (Subscript[n, a]) is parallel to  (Subscript[n, b])  the spin measurements are exactly anti-correlated ( ⟨ψ| S·(Subscript[n, a]) S·(Subscript[n, b]) |ψ⟩ = - 1 ). Thus if
Alice measures +1 Bob will surely measure -1 and visa versa.  If (Subscript[n, a]) is perpendicular to (Subscript[n, b]), then there is no correlation
( ⟨ψ| S·(Subscript[n, a]) S·(Subscript[n, b]) |ψ⟩ = 0 ), so if Alice measures +1, Bob is just as likely to measure +1 or -1. After measuring their qubits
Alice’s and Bob’s data might look something like this

({{Pair, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {Alice, Sx, Sz, Sz, Sx, Sx, Sz, Sz, Sx, Sx}, {result, 1, -1, 1, -1, 1, 1, -1, 1, 1}, {Bob, Sx, Sx, Sz, Sz, Sx, Sx, Sz, Sz, Sz}, {result, -1, 1, -1, -1, -1, 1, 1, -1, -1}})

Now Alice and Bob get on the telephone, and Bob announces he used the measuring devices {({{Sx,, Sx,, Sz,, Sz,, Sx,, Sx,, Sz,, Sz,, Sz}})} , Alice compares that with her choices and they both agree to throw out
the qubit measurements in which their basis do not agree. In this case it would be qubit 2,4,6,8,9. So Alice
would have left the sequence of measurements {1,1,1,-1} and Bob {-1,-1,-1,1}. Since Bob knows he is anti-correlated with Alice
he simply changes the sign of his measured values, and therefore both Alice and Bob share the same key {1,1,1,-1} (or {1,1,1,0}).

As in the BB84 protocol Alice and Bob can then share a subset of qubit measurements, which should agree exactly if
the qubits were not measured prior to their arrival at Alice and Bob. If the measured values for this subset do not agree, they know that Eve has been eavesdropping.

Hyperlink["http://www.youtube.com/watch?v=cWpqlgF7uEA"]