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
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
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.
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) 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) 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 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.
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 2O(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(nlognloglogn)-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].
Given a classical error-correcting block code, the task of quantum list decoding is to produce from any quantumly corrupted codeword a short list containing all messages whose codewords exhibit high "presence" in the quantumly corrupted codeword.Efficient quantum list decoders have been used to prove a quantum hardcore property of classical codes.However, the code rates of all known families of efficiently quantum list-decodable codes are, unfortunately, too small for other practical applications.To improve those known code rates, we prove that a specific code family of polynomially small code rate over a fixed code alphabet, obtained by concatenating generalized Reed-Solomon codes as outer codes with Hadamard codes as inner codes, has an efficient quantum list-decoding algorithm if its codewords have relatively high codeword presence in a given quantumly corrupted codeword.As an immediate application, we use the quantum list decodability of this code family to solve a certain form of quantum search problems in polynomial time.When the codeword presence becomes smaller, in contrast, we show that the quantum list decodability of generalized Reed-Solomon codes with high confidence is closely related to the efficient solvability of the following two problems: the noisy polynomial interpolation problem and the bounded distance vector problem.Moreover, assuming that NP BQP, we also prove that no efficient quantum list decoder exists for the generalized Reed-Solomon codes.
In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022].
In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity.
Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.