dorsal/arxiv
View SchemaQuantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
| Authors | Akinori Kawachi, Tomoyuki Yamakami |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0602088 |
| URL | https://arxiv.org/abs/quant-ph/0602088 |
| Journal | (journal version) SIAM Journal on Computing, Vol.39, pp.2941-2969, 2010 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
Hardcore functions have been used as a technical tool to construct secure cryptographic systems; however, little is known on their quantum counterpart, called quantum hardcore functions. With a new insight into fundamental properties of quantum hardcores, we present three new quantum hardcore functions for any (strong) quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on a classical hardcore property of his pseudorandom generator, by proving its quantum hardcore property. Our major technical tool is the new notion of quantum list-decoding of "classical" error-correcting codes (rather than "quantum" error-correcting codes), which is defined on the platform of computational complexity theory and computational cryptography (rather than information theory). In particular, we give a simple but powerful criterion that makes a polynomial-time computable classical block code (seen as a function) a quantum hardcore for all quantum one-way functions. On their own interest, we construct efficient quantum list-decoding algorithms for classical block codes whose associated quantum states (called codeword states) form a nearly phase-orthogonal basis.
{
"annotation_id": "957cdf1e-93fd-475e-bf66-5ea0b1560747",
"date_created": "2026-03-02T18:02:23.629000Z",
"date_modified": "2026-03-02T18:02:23.629000Z",
"file_hash": "58b348bca20ecfa69be9bf8df3ce6a9380ccc8f11dde82e757a3a728fa9d23aa",
"private": false,
"record": {
"abstract": "Hardcore functions have been used as a technical tool to construct secure\ncryptographic systems; however, little is known on their quantum counterpart,\ncalled quantum hardcore functions. With a new insight into fundamental\nproperties of quantum hardcores, we present three new quantum hardcore\nfunctions for any (strong) quantum one-way function. We also give a \"quantum\"\nsolution to Damgard\u0027s question (CRYPTO\u002788) on a classical hardcore property of\nhis pseudorandom generator, by proving its quantum hardcore property. Our major\ntechnical tool is the new notion of quantum list-decoding of \"classical\"\nerror-correcting codes (rather than \"quantum\" error-correcting codes), which is\ndefined on the platform of computational complexity theory and computational\ncryptography (rather than information theory). In particular, we give a simple\nbut powerful criterion that makes a polynomial-time computable classical block\ncode (seen as a function) a quantum hardcore for all quantum one-way functions.\nOn their own interest, we construct efficient quantum list-decoding algorithms\nfor classical block codes whose associated quantum states (called codeword\nstates) form a nearly phase-orthogonal basis.",
"arxiv_id": "quant-ph/0602088",
"authors": [
"Akinori Kawachi",
"Tomoyuki Yamakami"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "(journal version) SIAM Journal on Computing, Vol.39, pp.2941-2969,\n 2010",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding",
"url": "https://arxiv.org/abs/quant-ph/0602088"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a74484d0-34c0-4228-9a60-78a52799bcfe",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}