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

SIAM Journal on ComputingJan 1, 20103 citations

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

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

Quantum Pseudorandom Error-Correcting Codes

Min-Hsiu Hsieh, Shogo Yamada

Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn [CRYPTO 2024], are classical error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings. We initiate the study of quantum analogues of PRCs. We define quantum pseudorandom error-correcting codes (QPRCs). Assuming that Learning Parity with Noise (LPN) is hard for $2^{O(\sqrt{n})}$ -time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all $o(n \frac{\log \log n}{\log n})$ -local quantum noise, where $n$ is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all $αn$ -local quantum noise for some constant $α>0$ . The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn [CRYPTO 2024], are classical error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings. We initiate the study of quantum analogues of PRCs. We define quantum pseudorandom error-correcting codes (QPRCs). Assuming that Learning Parity with Noise (LPN) is hard for $2^{O(\sqrt{n})}$-time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all $o(n \frac{\log \log n}{\log n})$-local quantum noise, where $n$ is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all $αn$-local quantum noise for some constant $α>0$. The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].

quant-pharXiv:2609.38986Oct 1, 20260 citations

Efficient Quantum Pseudorandomness from Hamiltonian Phase States

John Bostanci, Jonas Haferkamp, Dominik Hangleiter +1 more

Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems, and, more recently, in the foundations of quantum cryptography. Kretschmer (TQC '21) showed that both pseudorandom states and pseudorandom unitaries exist even in a world without classical one-way functions. To this day, however, all known constructions require classical cryptographic building blocks which are themselves synonymous with the existence of one-way functions, and which are also challenging to realize on realistic quantum hardware. In this work, we seek to make progress on both of these fronts simultaneously -- by decoupling quantum pseudorandomness from classical cryptography altogether. We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit Z-rotations and CNOT circuits. We show that the hardness of our problem reduces to a worst-case version of the problem, and we provide evidence that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We also show information-theoretic hardness when only few copies of HPS are available by proving an approximate $t$ -design property of our ensemble. Finally, we show that our HPS assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys.Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems, and, more recently, in the foundations of quantum cryptography. Kretschmer (TQC '21) showed that both pseudorandom states and pseudorandom unitaries exist even in a world without classical one-way functions. To this day, however, all known constructions require classical cryptographic building blocks which are themselves synonymous with the existence of one-way functions, and which are also challenging to realize on realistic quantum hardware. In this work, we seek to make progress on both of these fronts simultaneously -- by decoupling quantum pseudorandomness from classical cryptography altogether. We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit Z-rotations and CNOT circuits. We show that the hardness of our problem reduces to a worst-case version of the problem, and we provide evidence that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We also show information-theoretic hardness when only few copies of HPS are available by proving an approximate $t$-design property of our ensemble. Finally, we show that our HPS assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys.

arXiv:2410.08073Leibniz international proceedings in informaticsOct 10, 20241 citation

Efficient Quantum Pseudorandomness from Hamiltonian Phase States

Bostanci, John, Haferkamp, Jonas, Hangleiter, Dominik +1 more

Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems, and, more recently, in the foundations of quantum cryptography. Kretschmer (TQC '21) showed that both pseudorandom states and pseudorandom unitaries exist even in a world without classical one-way functions. To this day, however, all known constructions require classical cryptographic building blocks which are themselves synonymous with the existence of one-way functions, and which are also challenging to implement on realistic quantum hardware. In this work, we seek to make progress on both of these fronts simultaneously - by decoupling quantum pseudorandomness from classical cryptography altogether. We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit Z rotations and CNOT circuits. We show that the hardness of our problem reduces to a worst-case version of the problem, and we provide evidence that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We also show information-theoretic hardness when only few copies of HPS are available by proving an approximate t-design property of our ensemble. Finally, we show that our HPS assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys.Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems, and, more recently, in the foundations of quantum cryptography. Kretschmer (TQC '21) showed that both pseudorandom states and pseudorandom unitaries exist even in a world without classical one-way functions. To this day, however, all known constructions require classical cryptographic building blocks which are themselves synonymous with the existence of one-way functions, and which are also challenging to implement on realistic quantum hardware. In this work, we seek to make progress on both of these fronts simultaneously - by decoupling quantum pseudorandomness from classical cryptography altogether. We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit Z rotations and CNOT circuits. We show that the hardness of our problem reduces to a worst-case version of the problem, and we provide evidence that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We also show information-theoretic hardness when only few copies of HPS are available by proving an approximate t-design property of our ensemble. Finally, we show that our HPS assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys.

Jan 1, 20252 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.

2^{O(\sqrt{n})}

-time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all

o(n \frac{\log \log n}{\log n})

-local quantum noise, where

n

is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all

αn

-local quantum noise for some constant

α>0

. The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].

t

-design property of our ensemble. Finally, we show that our HPS assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys.