dorsal/arxiv
View SchemaComputational Indistinguishability between Quantum States and Its Cryptographic Application
| Authors | Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0403069 |
| URL | https://arxiv.org/abs/quant-ph/0403069 |
| DOI | 10.1007/s00145-011-9103-4 |
| Journal | Journal of Cryptology 25(3): 528-555 (2012) |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
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 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.
{
"annotation_id": "b350eaf4-76c6-4a06-90a5-9fe51734c851",
"date_created": "2026-03-02T18:02:06.508000Z",
"date_modified": "2026-03-02T18:02:06.508000Z",
"file_hash": "e331ac8eedcb37e47c9d00379bbc138d33843eec083145caf8cc6df257737d3b",
"private": false,
"record": {
"abstract": "We introduce a computational problem of distinguishing between two specific\nquantum states as a new cryptographic problem to design a quantum cryptographic\nscheme that is \"secure\" against any polynomial-time quantum adversary. Our\nproblem, QSCDff, is to distinguish between two types of random coset states\nwith a hidden permutation over the symmetric group of finite degree. This\nnaturally generalizes the commonly-used distinction problem between two\nprobability distributions in computational cryptography. As our major\ncontribution, we show that QSCDff has three properties of cryptographic\ninterest: (i) QSCDff has a trapdoor; (ii) the average-case hardness of QSCDff\ncoincides with its worst-case hardness; and (iii) QSCDff is computationally at\nleast as hard as the graph automorphism problem in the worst case. These\ncryptographic properties enable us to construct a quantum public-key\ncryptosystem, which is likely to withstand any chosen plaintext attack of a\npolynomial-time quantum adversary. We further discuss a generalization of\nQSCDff, called QSCDcyc, and introduce a multi-bit encryption scheme that relies\non similar cryptographic properties of QSCDcyc.",
"arxiv_id": "quant-ph/0403069",
"authors": [
"Akinori Kawachi",
"Takeshi Koshiba",
"Harumichi Nishimura",
"Tomoyuki Yamakami"
],
"categories": [
"quant-ph",
"cs.CR"
],
"doi": "10.1007/s00145-011-9103-4",
"journal_ref": "Journal of Cryptology 25(3): 528-555 (2012)",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Computational Indistinguishability between Quantum States and Its Cryptographic Application",
"url": "https://arxiv.org/abs/quant-ph/0403069"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5d935e25-b2cb-4681-83c8-20b6ba712dd3",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}