Computational Indistinguishability between Quantum States and Its Cryptographic Application
<|reference_start|>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, QSCDff, 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 QSCDff has three properties of cryptographic interest: (i) QSCDff has a trapdoor; (ii) the average-case hardness of QSCDff coincides with its worst-case hardness; and (iii) QSCDff 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 QSCDff, called QSCDcyc, and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCDcyc.<|reference_end|>
@article{kawachi2004computational,
    title={Computational Indistinguishability between Quantum States and Its
  Cryptographic Application},
    author={Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura and Tomoyuki
  Yamakami},
    journal={Journal of Cryptology 25(3): 528-555 (2012)},
    year={2004},
    doi={10.1007/s00145-011-9103-4},
    archivePrefix={arXiv},
    eprint={quant-ph/0403069},
    primaryClass={quant-ph cs.CR}
}