Computational Indistinguishability Between Quantum States and Its Cryptographic Application
We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is "secure" against any polynomial-time quantum adversary. Our problem, QSCD(ff), is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show that QSCD(ff) has three properties of cryptographic interest: (i) QSCD(ff) has a trapdoor; (ii) the average-case hardness of QSCD(ff) coincides with its worst-case hardness; and (iii) QSCD(ff) is computationally at least as hard as the graph automorphism problem in the worst case. These cryptographic properties enable us to construct a quantum public-key cryptosystem which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCD(ff), called QSCD(cyc), and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCD(cyc).
computational indistinguishability trapdoor graph automorphism problem quantum public-key cryptosystem quantum cryptography worst-case/average-case equivalence