Computational indistinguishability between quantum states and its cryptographic application

Akinori Kawachi*, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)


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 cryptosys-tem 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.

Original languageEnglish
Pages (from-to)528-555
Number of pages28
JournalJournal of Cryptology
Issue number3
Publication statusPublished - 2012 Jul
Externally publishedYes


  • Computational indistinguishability
  • Graph automorphism problem
  • Quantum cryptography
  • Quantum publickey cryptosystem
  • Trapdoor
  • Worst-case/average-case equivalence

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Computational indistinguishability between quantum states and its cryptographic application'. Together they form a unique fingerprint.

Cite this