2
$\begingroup$

Is it possible to encrypt a quantum state, such that a $BQP$ attacker who does not know the secret key cannot obtain any information about the original state, but a $BQP$ decryptor with the key can recover the original state?

Assume (classical) one-way functions that are hard for quantum attackers to break exist (as is believed to be the case).

$\endgroup$
7
$\begingroup$

One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse operator is applied to decrypt.)

The resulting scheme is perfectly secure -- if the key is selected uniformly at random, then even an attacker who know a state entangled with the plaintext cannot distinguish the true ciphertext from an independent random state.

This observation was first made in A Ambainis, M Mosca, A Tapp, R de Wolf. "Private quantum channels", FOCS 2000.

They also showed that 2n bits of key are necessary for encryption of entangled quantum states.

If you have a classical PRG secure against quantum distinguishers, then you can get away with a much shorter key (as short as seed length required by the generator to generate 2 n output bits).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is this analogous to a one-time pad? $\endgroup$ – Demi Apr 10 '16 at 2:11
  • 2
    $\begingroup$ Yes, it is in fact called a quantum one-time pad. In the quantum case, you have to be a bit careful in how you define the security requirement for computational or statistical notions of secrecy. But for perfect secrecy, it is fairly straightforward: for every input state, the density matrix of the ciphertext should be the same when you average over keys. $\endgroup$ – Adam Smith Apr 10 '16 at 2:42
  • $\begingroup$ Ah okay. So the version with a CSPRNG is a quantum stream cipher. $\endgroup$ – Demi Apr 10 '16 at 2:43

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.