4
$\begingroup$

After getting help here with XNOR, RCA & XOR linked lists, I am now curious about quantum XOR ciphers (Google returns "no results").

In cryptography, the simple XOR cipher is a type of additive cipher, an encryption algorithm that operates according to the principles:

$A \oplus 0 = A$,
$A \oplus A = 0$,
$(A \oplus B) \oplus C = A \oplus (B \oplus C)$,
$(B \oplus A) \oplus A = B \oplus 0 = B$,

where $\oplus$ denotes the exclusive disjunction (XOR) operation.

-Wikipedia

How would a quantum XOR cipher be expressed?

$\endgroup$
  • 1
    $\begingroup$ So if you're imagining a one time pad $(m_i,s_i) \to (m_i \bigoplus s_i,s_i)$ on bitstreams. Which do you want to be a sequence of qubits instead? Both? $\endgroup$ – AHusain Aug 31 '18 at 2:46
  • $\begingroup$ @AHusain I think this is a nice approach. $\endgroup$ – meowzz Aug 31 '18 at 2:51
  • $\begingroup$ Could you repeat the description there into this question? Clarify this question so it is more self contained. $\endgroup$ – AHusain Aug 31 '18 at 2:54
  • $\begingroup$ @AHusain Is that better? $\endgroup$ – meowzz Aug 31 '18 at 3:02
  • 2
    $\begingroup$ The quantum equivalent of the one time pad (i.e. xoring a message with a secret key) is quantum teleportation. $\endgroup$ – Craig Gidney Aug 31 '18 at 8:27
5
$\begingroup$

There are two simple ways in which you can generalise an "XOR cipher" (i.e., a one-time pad or Vernam cipher) to the quantum regime.

  • One way is to use the fact that the Pauli operators form a quantum 1-design, which is a fancy way of saying that applying a uniformly random Pauli operator to any single-qubit quantum state makes it indistinguishable from the maximally mixed state — provided of course that which Pauli operator you perform is kept secret from any interfering party.

    Using this fact, you can realise a simple "quantum XOR cipher" between Alice and Bob by sharing a one-time pad between them, and then doing the following for any input state $\rho$ of Alice's:

    1. Alice takes two bits $(x,z)$ from the one-time pad, and performs the transformation $\rho \mapsto \sigma := P \rho P^\dagger$, where $P = X^x Z^z$.

    2. Alice transmits $\sigma$ to Bob. By averaging over all values of $(x,z) \in \{00,01,10,11\}$ it is easy to see that, to someone who doesn't know the value of $(x,z)$, the state $\sigma$ is indistinguishable from $\tfrac{1}{2} \mathbf 1$ and contains no information about the state $\rho$.

    3. Bob recovers $\rho = P^\dagger \!\sigma P$ using the same operator $P = X^x Z^z$ defined by his copy of the one-time pad.

  • Building on this idea, another way of generalising the XOR cipher (as Craig Gidney indicates, and which seems to be part of the folklore, see for example a post of mine on Physics.SE), is teleportation.

    In this case, the EPR state is akin to a shared random bit which is independent of any data which is to be encoded, and again must be carefully distributed between Alice and Bob.

    1. The Bell-basis measurement performed by Alice is akin to computing the parity of the (arbitrary) input quantum state with that shared random bit;

    2. The pair of classical bits which indicate the outcome play the role of the result of the parity computation, which contain no information about the state which is being "encoded";

    3. The correction performed by Bob is akin to reversing the parity computation, reproducing the input state original possessed by Alice.

    An intriguing feature of this analogy is that, whereas a one-time pad should only be used once, in the quantum regime the EPR pair can only be used once, as it is consumed. Also intriguing is that what one would think of as the encoded quantum state is effectively stored by the system playing the role of the shared random bit — the outcome of the "parity computation" instead plays the role of the reversible encoding of that qubit (this part of the protocol is effectively the same as the encoding of a state using a random Pauli operator).

In both cases above, two random bits are involved in what might be thought of as the encoding procedure. This might seem deep, but actually, I would suggest that it is just the fact that a uniformly random Pauli operator is involved in both cases (albeit slightly more subtly in teleportation than in using the Pauli operators as a 1-design).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.