Physics – Quantum Physics
Scientific paper
2006-02-10
(journal version) SIAM Journal on Computing, Vol.39, pp.2941-2969, 2010
Physics
Quantum Physics
25 pages, 10 point, letter size. This is a revised version of the complete version of a conference paper that appeared in the
Scientific paper
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.
Kawachi Akinori
Yamakami Tomoyuki
No associations
LandOfFree
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-600553