Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
<|reference_start|>Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding: 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.<|reference_end|>
@article{kawachi2006quantum,
    title={Quantum Hardcore Functions by Complexity-Theoretical Quantum List
  Decoding},
    author={Akinori Kawachi and Tomoyuki Yamakami},
    journal={(journal version) SIAM Journal on Computing, Vol.39, pp.2941-2969,
  2010},
    year={2006},
    archivePrefix={arXiv},
    eprint={quant-ph/0602088},
    primaryClass={quant-ph cs.CC}
}