CryptoDB
Computational Indistinguishability between Quantum States and Its Cryptographic Application
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2006-21641,
title={Computational Indistinguishability between Quantum States and Its Cryptographic Application},
booktitle={IACR Eprint archive},
keywords={foundations / quantum cryptography, computational indistinguishability, trapdoor property, worst-case/average-case equivalence, graph automorphism problem, quantum public-key cryptosystem},
url={http://eprint.iacr.org/2006/148},
note={ kawachi@is.titech.ac.jp 13285 received 14 Apr 2006, last revised 17 May 2006},
author={Akinori Kawachi and Takeshi Koshiba and Harumichi Nishimura and Tomoyuki Yamakami},
year=2006
}