Deterministic quantum-public-key encryption: Forward search attack and randomization

In the classical setting, public-key encryption requires randomness in order to be secure against a forward search attack, whereby an adversary compares the encryption of a guess of the secret message with the encryption of the actual secret message. We show that this is also true in the information-theoretic setting—where the public keys are quantum systems—by defining and giving an example of a forward search attack for any deterministic quantum-public-key bit-encryption scheme. However, unlike in the classical setting, we show that any such deterministic scheme can be used as a black box to build a randomized bit-encryption scheme that is no longer susceptible to this attack.

Figure 1

(Color online) Symmetry test for the $\left(1,N-1\right)$-copy state distinguishing problem. The top (blue) wire is a $N!$-dimensional quantum system, whose state space is spanned by the computational-basis states, each of which is labeled by a permutation $\sigma ∊S_N$ (e.g., $|0⟩$ corresponds to the identity permutation). The bottom wire represents $N$ registers, each of dimension $d$.