Insecure Superdense Coding

R. Perry, 14 May 2019, QCE

Updated 5 Aug. 2019

Superdense coding is first described and illustrated using 2 qubits. Then an alternative protocol for communicating using more than 2 qubits is described and shown to be insecure against a woman-in-the-middle eavesdropper.

Introduction

Superdense coding (SDC) is a quantum protocol for communicating two classical bits of information from Alice to Bob using a single qubit, under the assumption of a pre-shared entangled state [1]. Initially Alice and Bob together prepare two qubits, and then Alice keeps one with her and Bob keeps the other one. Later Alice can encode one of the 2-bit values {00, 01, 10, 11} by performing one of the operations {I, X, Z, Z*X} respectively on her qubit, and then send the qubit to Bob. Combining Alice's qubit with his original qubit, Bob can then always correctly determine the two encoded classical bits.

SDC is secure against a woman-in-the-middle eavesdropper in the sense that Eve can not extract any information from an intercepted qubit. Eve will always measure the qubit as 0 or 1 with equal probability regardless of the encoded information. Additionally, if Eve measures the qubit before forwarding to Bob, then Bob's subsequent measurement has only a 50% chance of being correct.

The protocol can obviously be generalized to securely communicate n classical bits of information using n qubits (n/2 pairs, n even), with each pair independently encoding two classical bits, and Alice sending n/2 qubits to Bob.

Alternative Protocol

Consider a variation of SDC in which Alice keeps n-1 of the initial entangled qubits, Bob keeps only one qubit, and n does not have to be even. This version of the protocol may be useful if Bob has trouble maintaining more than one qubit, for example if he is traveling from Earth to Mars in a spaceship with limited quantum resources: 

time     Earth                                 Mars

  0      Alice & Bob
         qn-1...q0

  1      Alice                                 Bob
         qn-1...q1                              q0

  2      Alice        qn-1...q1 ->  Eve ->      qn-1...q1

Figure 1: Alternative Protocol, with Eve in the middle

At time 2 Alice encodes an n-bit value and sends her n-1 qubits to Bob. For n=2 this is identical to the original protocol and is secure. But for n>2 Eve can obtain information from the intercepted qubits without affecting Bob's subsequent measurement.

Example, n=2 qubits

The examples show the state indices in binary, the probability of each state (magnitude-squared of the state amplitude), and the state amplitudes (real).

Starting with 2 qubits in state 00, Bob and Alice jointly entangle the qubits by performing a Hadamard transformation on qubit #1, followed by a controlled-NOT on qubit #0 controlled by qubit #1: 

     Prob  Ampl
  00 1     (1)
  01 0     (0)
  10 0     (0)
  11 0     (0)

 H1
 00 0.5  (0.707107)
 01 0    (0)
 10 0.5  (0.707107)
 11 0    (0)

 CX10
 00 0.5  (0.707107)
 01 0    (0)
 10 0    (0)
 11 0.5  (0.707107)

Table 1: Joint Transformations, n=2
Bob then takes qubit #0 and travels to Mars.

Later, Alice encodes one of the 2-bit values {00, 01, 10, 11} by performing one of the operations {I, X, Z, Z*X} respectively on qubit #1, producing one of the following four states: 

  00
  I
  00 0.5  (0.707107)
  01 0    (0)
  10 0    (0)
  11 0.5  (0.707107)

 01
 X1
 00 0    (0)
 01 0.5  (0.707107)
 10 0.5  (0.707107)
 11 0    (0)

 10
 Z1
 00 0.5  (0.707107)
 01 0    (0)
 10 0    (0)
 11 0.5  (-0.707107)

 11
 Z1X1
 00 0    (0)
 01 0.5  (0.707107)
 10 0.5  (-0.707107)
 11 0    (0)

Table 2: Alice Encoding, n=2
Alice then sends qubit #1 to Bob. Bob performs a controlled-NOT on qubit #0 controlled by qubit #1, followed by a Hadamard transformation on qubit #1, and then a measurement. Each of the resulting possible four states has a measurement probability of 1 corresponding to the 2-bit value encoded by Alice: 
  00
  00 1  (1)
  01 0  (0)
  10 0  (0)
  11 0  (0)

 01
 00 0  (0)
 01 1  (1)
 10 0  (0)
 11 0  (0)

 10
 00 0  (0)
 01 0  (0)
 10 1  (1)
 11 0  (0)

 11
 00 0  (0)
 01 0  (0)
 10 0  (0)
 11 1  (1)

Table 3: Bob Decoding, n=2
Now suppose Eve measures the qubit from Alice before forwarding it to Bob. For each of the four possibilities in Table 2, the probability of measuring a 0 or 1 for qubit #1 is 0.5, so Eve can gain no information from that measurement.

Suppose Alice encoded 00 and Eve measures qubit #1 as 0. The states before and after the measurement, and after Bob's decoding are: 

  Alice
  00 0.5  (0.707107)
  01 0    (0)
  10 0    (0)
  11 0.5  (0.707107)

 Eve
 00 1  (1)
 01 0  (0)
 10 0  (0)
 11 0  (0)

 Bob
 00 0.5  (0.707107)
 01 0    (0)
 10 0.5  (0.707107)
 11 0    (0)

Table 4: Eve in the middle, n=2
So now Bob is equally likely to measure correctly 00 or incorrectly 10.
Example, n=3 qubits

Starting with 3 qubits in state 000, Bob and Alice jointly entangle the qubits by performing Hadamard transformations on qubits #1 and #2, followed by controlled-NOTs on qubit #0 controlled by qubit #1 and #2: 


  000 1  (1)
  001 0  (0)
  010 0  (0)
  011 0  (0)
  100 0  (0)
  101 0  (0)
  110 0  (0)
  111 0  (0)

 H1
 000 0.5  (0.707107)
 001 0    (0)
 010 0.5  (0.707107)
 011 0    (0)
 100 0    (0)
 101 0    (0)
 110 0    (0)
 111 0    (0)

 H2
 000 0.25  (0.5)
 001 0     (0)
 010 0.25  (0.5)
 011 0     (0)
 100 0.25  (0.5)
 101 0     (0)
 110 0.25  (0.5)
 111 0     (0)

 CX10
 000 0.25  (0.5)
 001 0     (0)
 010 0     (0)
 011 0.25  (0.5)
 100 0.25  (0.5)
 101 0     (0)
 110 0     (0)
 111 0.25  (0.5)

 CX20
 000 0.25  (0.5)
 001 0     (0)
 010 0     (0)
 011 0.25  (0.5)
 100 0     (0)
 101 0.25  (0.5)
 110 0.25  (0.5)
 111 0     (0)

Table 5: Joint Transformations, n=3
Bob then takes qubit #0 and travels to Mars.

Later, Alice encodes one of the possible 3-bit values by performing operations on qubits #1 and #2: 

  000
  I
  000 0.25  (0.5)
  001 0     (0)
  010 0     (0)
  011 0.25  (0.5)
  100 0     (0)
  101 0.25  (0.5)
  110 0.25  (0.5)
  111 0     (0)

 001
 X1
 000 0     (0)
 001 0.25  (0.5)
 010 0.25  (0.5)
 011 0     (0)
 100 0.25  (0.5)
 101 0     (0)
 110 0     (0)
 111 0.25  (0.5)

 010
 Z1
 000 0.25  (0.5)
 001 0     (0)
 010 0     (0)
 011 0.25  (-0.5)
 100 0     (0)
 101 0.25  (0.5)
 110 0.25  (-0.5)
 111 0     (0)

 011
 Z1X1
 000 0     (0)
 001 0.25  (0.5)
 010 0.25  (-0.5)
 011 0     (0)
 100 0.25  (0.5)
 101 0     (0)
 110 0     (0)
 111 0.25  (-0.5)

 100
 Z2
 000 0.25  (0.5)
 001 0     (0)
 010 0     (0)
 011 0.25  (0.5)
 100 0     (0)
 101 0.25  (-0.5)
 110 0.25  (-0.5)
 111 0     (0)

 101
 Z2X1
 000 0     (0)
 001 0.25  (0.5)
 010 0.25  (0.5)
 011 0     (0)
 100 0.25  (-0.5)
 101 0     (0)
 110 0     (0)
 111 0.25  (-0.5)

 110
 Z2Z1
 000 0.25  (0.5)
 001 0     (0)
 010 0     (0)
 011 0.25  (-0.5)
 100 0     (0)
 101 0.25  (-0.5)
 110 0.25  (0.5)
 111 0     (0)

 111
 Z2Z1X1
 000 0     (0)
 001 0.25  (0.5)
 010 0.25  (-0.5)
 011 0     (0)
 100 0.25  (-0.5)
 101 0     (0)
 110 0     (0)
 111 0.25  (0.5)

Table 6: Alice Encoding, n=3
In general, to encode the n-bit value specified in binary as bn-1...b0, Alice performs transformation X1 if b0=1, and transformation Zk if bk=1, for k=1,...,n-1.

Alice then sends qubits #2 and #1 to Bob. Bob performs controlled-NOTs on qubit #0 controlled by qubit #2 and #1, followed by Hadamard transformations on qubits #2 and #1, and then a measurement. Each of the resulting possible eight states has a measurement probability of 1 corresponding to the 3-bit value encoded by Alice: 

 000
 000 1  (1)
 001 0  (0)
 010 0  (0)
 011 0  (0)
 100 0  (0)
 101 0  (0)
 110 0  (0)
 111 0  (0)

 001
 000 0  (0)
 001 1  (1)
 010 0  (0)
 011 0  (0)
 100 0  (0)
 101 0  (0)
 110 0  (0)
 111 0  (0)

 010
 000 0  (0)
 001 0  (0)
 010 1  (1)
 011 0  (0)
 100 0  (0)
 101 0  (0)
 110 0  (0)
 111 0  (0)

 011
 000 0  (0)
 001 0  (0)
 010 0  (0)
 011 1  (1)
 100 0  (0)
 101 0  (0)
 110 0  (0)
 111 0  (0)

 100
 000 0  (0)
 001 0  (0)
 010 0  (0)
 011 0  (0)
 100 1  (1)
 101 0  (0)
 110 0  (0)
 111 0  (0)

 101
 000 0  (0)
 001 0  (0)
 010 0  (0)
 011 0  (0)
 100 0  (0)
 101 1  (1)
 110 0  (0)
 111 0  (0)

 110
 000 0  (0)
 001 0  (0)
 010 0  (0)
 011 0  (0)
 100 0  (0)
 101 0  (0)
 110 1  (1)
 111 0  (0)

 111
 000 0  (0)
 001 0  (0)
 010 0  (0)
 011 0  (0)
 100 0  (0)
 101 0  (0)
 110 0  (0)
 111 1  (1)

Table 7: Bob Decoding, n=3
Now suppose Eve measures the qubits from Alice before forwarding them to Bob. For each of the eight possibilities in Table 6, the probability of measuring a 0 or 1 for qubits #2 or #1 separately is 0.5, so Eve can gain no information from that direct measurement.

However, qubits #2 and #1 are entangled with each other due to their mutual entanglement with qubit #0. If Eve performs "disentangling" transformations before measuring, then she can gain information from the result. The transformations needed are a controlled-NOT on qubit #1 controlled by qubit #2, followed by a Hadamard transformation on qubit #2, and the resulting states are: 

 0
 000
 000 0.5  (0.707107)
 001 0    (0)
 010 0    (0)
 011 0.5  (0.707107)
 100 0    (0)
 101 0    (0)
 110 0    (0)
 111 0    (0)

 1
 001
 000 0    (0)
 001 0.5  (0.707107)
 010 0.5  (0.707107)
 011 0    (0)
 100 0    (0)
 101 0    (0)
 110 0    (0)
 111 0    (0)

 2
 010
 000 0    (0)
 001 0    (0)
 010 0    (0)
 011 0    (0)
 100 0.5  (0.707107)
 101 0    (0)
 110 0    (0)
 111 0.5  (-0.707107)

 3
 011
 000 0    (0)
 001 0    (0)
 010 0    (0)
 011 0    (0)
 100 0    (0)
 101 0.5  (0.707107)
 110 0.5  (-0.707107)
 111 0    (0)

 4
 100
 000 0    (0)
 001 0    (0)
 010 0    (0)
 011 0    (0)
 100 0.5  (0.707107)
 101 0    (0)
 110 0    (0)
 111 0.5  (0.707107)

 5
 101
 000 0    (0)
 001 0    (0)
 010 0    (0)
 011 0    (0)
 100 0    (0)
 101 0.5  (0.707107)
 110 0.5  (0.707107)
 111 0    (0)

 6
 110
 000 0.5  (0.707107)
 001 0    (0)
 010 0    (0)
 011 0.5  (-0.707107)
 100 0    (0)
 101 0    (0)
 110 0    (0)
 111 0    (0)

 7
 111
 000 0    (0)
 001 0.5  (0.707107)
 010 0.5  (-0.707107)
 011 0    (0)
 100 0    (0)
 101 0    (0)
 110 0    (0)
 111 0    (0)

Table 8: Eve Decoding, n=3
The measured value of qubit #2 will be 0 for encoded values 0, 1, 6, and 7, and it will be 1 for encoded values 2, 3, 4, and 5. So after this measurement Eve will know that the value encoded by Alice is one of only 4 possibilities instead of the original 8.

Furthermore, since qubit #2 is not in a superposition at this point, Eve's measurement of it does not change the state, so she can undo her transformations to restore the original state created by Alice, and then forward the qubits to Bob. Bob's measurement result will then be the same as if Eve had not interfered.

General Case, n>2 qubits

Starting with n qubits in state 0, Bob and Alice jointly entangle the qubits by performing Hadamard transformations on qubits #1,...,#n-1, followed by controlled-NOTs on qubit #0 controlled by qubit #1,...,#n-1.

Bob then takes qubit #0 and travels to Mars.

Later, Alice encodes one of the possible n-bit values bn-1...b0 by performing transformation X1 if b0=1, and transformation Zk if bk=1, for k=1,...,n-1.

Alice then sends the qubits to Bob.

Eve intercepts the qubits from Alice and performs a sequence of transformations and measurements to create an overall binary measurement value mn-2...m0, where m0=0, and mk is the measured value of qubit #n-1 after performing transformation CXn-1,k followed by Hn-1, for k=1,...,n-2. After each measurement mk Eve undoes the transformations by performing Hn-1 followed by CXn-1,k.

Eve then knows that the value encoded is one of only 4 possibilities: {m, m+1, (2n-1)-m, (2n-1)-(m+1)}.

Eve forwards the qubits to Bob who performs controlled-NOTs on qubit #0 controlled by qubit #n-1,...,#1, followed by Hadamard transformations on qubits #n-1,...,#1. Bob's measurement result will be the same as if Eve had not interfered.

Example, n=4 qubits

Alice encodes one of the possible 4-bit values v = 0,...,15 and Eve measures m = 0, 2, 4, or 6: 

  v   m2 m1 m0
  0   0  0  0
  1   0  0  0
  2   0  1  0
  3   0  1  0
  4   1  0  0
  5   1  0  0
  6   1  1  0
  7   1  1  0
  8   1  1  0
  9   1  1  0
 10   1  0  0
 11   1  0  0
 12   0  1  0
 13   0  1  0
 14   0  0  0
 15   0  0  0

Table 9: Encoded Value and Eve Measurements, n=4

Each possible value m measured by Eve corresponds to 4 possibilities for the encoded value v:
mv
  0     0, 1, 14, 15
  2     2, 3, 12, 13
  4     4, 5, 10, 11
  6     6, 7, 8, 9

Table 10: Eve Measurement and Possible Encoded Values, n=4

References

[1] wikipedia.org/wiki/Superdense_coding