Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Akinori Kawachi, Tomoyuki Yamakami

Published Jan 1, 2006• 9 citations
Publisher
DOI
10.1007/11787006_19

Related papers

Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Akinori Kawachi, Tomoyuki Yamakami

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

•Feb 10, 2006•0 citations

Quantum Complexity Theory and Quantum Algorithm

R. Hayakawa, Tomoyuki Morimae

電子情報通信学会誌•Nov 1, 2021•0 citations

Complexity-Theoretical Quantum List Decoding and Applications to Quamtum Hardcore Functions (計算理論とアルゴリズムの新展開 RIMS研究集会報告集)

亮周 河内, 智幸 山上

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, 2006•0 citations

A survey of quantum complexity theory

Umesh V. Vazirani

Proceedings of symposia in applied mathematics•Jan 1, 2002•44 citations

Quantum Algorithmic Complexities

Fabio Benatti

Theoretical and mathematical physics•Jan 1, 2009•0 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 Damgård's question [Advances in Cryptology, Lecture Notes in Comput. Sci. 403, Springer, Berlin, 1990, pp. 163–172] 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/0602088•SIAM Journal on Computing•Jan 1, 2010•7 citations
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-Decoding
We poesent thoee new quantum hardcore functions for any quantum one-way function.We also give a quantum" solution to Damgdrd's question (CRYFΓO88)(\mathrm{C}\mathrm{R}\mathrm{Y}\mathrm{F}\Gamma \mathrm{O}88)(CRYFΓO88) 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 funcu˙on)\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\dot{\mathrm{u}}\mathrm{o}\mathrm{n})funcu˙on) 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.
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 Damgård's question [Advances in Cryptology, Lecture Notes in Comput. Sci. 403, Springer, Berlin, 1990, pp. 163–172] 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.