Paper 2006/148

Computational Indistinguishability between Quantum States and Its Cryptographic Application

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

Abstract

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 three cryptographic properties: (i) QSCDff has the trapdoor property; (ii) the average-case hardness of QSCDff coincides with its worst-case hardness; and (iii) QSCDff is computationally at least as hard in the worst case as the graph automorphism problem. 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 relying on the cryptographic properties of QSCDcyc.

Note: References are added.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
quantum cryptographycomputational indistinguishabilitytrapdoor propertyworst-caseaverage-case equivalencegraph automorphism problemquantum public-key cryptosystem
Contact author(s)
kawachi @ is titech ac jp
History
2006-05-17: revised
2006-04-22: received
See all versions
Short URL
https://ia.cr/2006/148
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/148,
      author = {Akinori Kawachi and Takeshi Koshiba and Harumichi Nishimura and Tomoyuki Yamakami},
      title = {Computational Indistinguishability between Quantum States and Its Cryptographic Application},
      howpublished = {Cryptology ePrint Archive, Paper 2006/148},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/148}},
      url = {https://eprint.iacr.org/2006/148}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.