Abstract. We present three new quantum hardcore functions for any quantum one-way function. We also give a “quantum ” solution to Damg˚ard’s question (CRYPTO’88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property. Our technical tool is 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 cryptography (rather than information theory). In particular, we give a simple but powerful criterion that makes a polynomial-time computable code (seen as a function) a quantum hardcore for any quantum one-way function. On their own interest, we also give quantum list-decoding algorithms for codes whose associated quantum states (called codeword states) are “almost ” orthogonal using the technique of pretty good measurement. 1 Introduction: From Hardcore to List-DecodingAbstract. We present three new quantum hardcore functions for any quantum one-way function. We also give a “quantum ” solution to Damg˚ard’s question (CRYPTO’88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property. Our technical tool is 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 cryptography (rather than information theory). In particular, we give a simple but powerful criterion that makes a polynomial-time computable code (seen as a function) a quantum hardcore for any quantum one-way function. On their own interest, we also give quantum list-decoding algorithms for codes whose associated quantum states (called codeword states) are “almost ” orthogonal using the technique of pretty good measurement. 1 Introduction: From Hardcore to List-Decoding

Feb 10, 20060 citations

Quantum Algorithmic Complexities

Fabio Benatti

Theoretical and mathematical physicsJan 1, 20090 citations

Complexity-Theoretical Quantum List Decoding and Applications to Quantum Hardcore Functions(New Trends in Theory of Computation and Algorithm)

Akinori Kawachi, Tomoyuki Yamakami

We poesent thoee new quantum hardcore functions for any quantum one-way function.We also give a quantum" solution to Damgdrd's question $(\mathrm{C}\mathrm{R}\mathrm{Y}\mathrm{F}\Gamma \mathrm{O}88)$ on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.Our technical tool is quantum list-decoding of 'classical" crrorcorrecting codes (rather than ' quantum" error-correcting codes).which is deflned on the platform of computational complexity theory and cryptography (rather than infonnation theory).In panicular, we give a simple but powerful criterion that makes a polynomial-time computable code (seen as a $\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\dot{\mathrm{u}}\mathrm{o}\mathrm{n})$ a quantum hardcore for any quantum one-way function.On their own inteoest, we also give quantum list-decoding algorithms for codes whose associated quantum states (called codeword states) are ' almost" orthogonal using the technique of poetty good measurement.We poesent thoee new quantum hardcore functions for any quantum one-way function.We also give a quantum" solution to Damgdrd's question $(\mathrm{C}\mathrm{R}\mathrm{Y}\mathrm{F}\Gamma \mathrm{O}88)$ on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.Our technical tool is quantum list-decoding of 'classical" crrorcorrecting codes (rather than ' quantum" error-correcting codes).which is deflned on the platform of computational complexity theory and cryptography (rather than infonnation theory).In panicular, we give a simple but powerful criterion that makes a polynomial-time computable code (seen as a $\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\dot{\mathrm{u}}\mathrm{o}\mathrm{n})$ a quantum hardcore for any quantum one-way function.On their own inteoest, we also give quantum list-decoding algorithms for codes whose associated quantum states (called codeword states) are ' almost" orthogonal using the technique of poetty good measurement.

May 1, 20060 citations

Computational complexity and applications of quantum algorithm

Satoshi Iriyama, Makoto Ohya

Applied Mathematics and ComputationJun 24, 20112 citations

Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Akinori Kawachi, Tomoyuki Yamakami

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.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.

arXiv:quant-ph/0602088Feb 10, 20060 citations

We poesent thoee new quantum hardcore functions for any quantum one-way function.We also give a quantum" solution to Damgdrd's question

(\mathrm{C}\mathrm{R}\mathrm{Y}\mathrm{F}\Gamma \mathrm{O}88)

on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.Our technical tool is quantum list-decoding of 'classical" crrorcorrecting codes (rather than ' quantum" error-correcting codes).which is deflned on the platform of computational complexity theory and cryptography (rather than infonnation theory).In panicular, we give a simple but powerful criterion that makes a polynomial-time computable code (seen as a

\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\dot{\mathrm{u}}\mathrm{o}\mathrm{n})

a quantum hardcore for any quantum one-way function.On their own inteoest, we also give quantum list-decoding algorithms for codes whose associated quantum states (called codeword states) are ' almost" orthogonal using the technique of poetty good measurement.