Abstract One-way quantum state generators (), which serve as the quantum analog of one-way functions (), have attracted significant interest due to their potential applications and the reduced assumption requirements compared to . This paper explores the applications of structured and presents several results: We construct efficiently samplable, statistically far but computationally indistinguishable pairs of distributions ( pairs) from secretly-verifiable with somewhat injectivity, which has implications for quantum commitment schemes; We demonstrate that somewhat injective can be derived from almost regular ; We also focus on a specific type of , termed , and prove that the existence of a single-copy-secure hard-core predicate for these is both necessary and sufficient for constructing pairs; Moreover, we propose a simple quantum commitment scheme based on the decisional assumption, offering improved parameter choices and flexibility over classical schemes. These findings contribute to the understanding and potential applications of in quantum cryptography.
Abstract One-way quantum state generators (), which serve as the quantum analog of one-way functions (), have attracted significant interest due to their potential applications and the reduced assumption requirements compared to . This paper explores the applications of structured and presents several results: We construct efficiently samplable, statistically far but computationally indistinguishable pairs of distributions ( pairs) from secretly-verifiable with somewhat injectivity, which has implications for quantum commitment schemes; We demonstrate that somewhat injective can be derived from almost regular ; We also focus on a specific type of , termed , and prove that the existence of a single-copy-secure hard-core predicate for these is both necessary and sufficient for constructing pairs; Moreover, we propose a simple quantum commitment scheme based on the decisional assumption, offering improved parameter choices and flexibility over classical schemes. These findings contribute to the understanding and potential applications of in quantum cryptography.
One-way functions are central to classical cryptography. They are necessary for the existence of non-trivial classical cryptosystems, and also sufficient to realize meaningful primitives including commitments, pseudorandom generators and digital signatures. At the same time, a mounting body of evidence suggests that assumptions even weaker than one-way functions may suffice for many cryptographic tasks of interest in a quantum world, including bit commitments and secure multi-party computation. This work studies one-way state generators [Morimae-Yamakawa, CRYPTO 2022], a natural quantum relaxation of one-way functions. Given a secret key, a one-way state generator outputs a hard to invert quantum state. A fundamental question is whether this type of quantum one-wayness suffices to realize quantum cryptography. We obtain an affirmative answer to this question, by proving that one-way state generators with pure state outputs imply quantum bit commitments and secure multiparty computation. Along the way, we use efficient shadow tomography [Huang et. al., Nature Physics 2020] to build an intermediate primitive with classical outputs, which we call a (quantum) one-way puzzle. Our main technical contribution is a proof that one-way puzzles imply quantum bit commitments. This proof develops new techniques for pseudoentropy generation [Hastad et. al., SICOMP 1999] from arbitrary distributions, which may be of independent interest.
The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski, Canetti, and Qian recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations. However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures. In this paper, we study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions. We first revisit the definition of OWSGs and generalize it by allowing mixed output states. Then we show the following results. (1) We define a weaker version of OWSGs, weak OWSGs, and show that they are equivalent to OWSGs. (2) Quantum digital signatures are equivalent to OWSGs. (3) Private-key quantum money schemes (with pure money states) imply OWSGs. (4) Quantum pseudo one-time pad schemes imply both OWSGs and EFI pairs. (5) We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs, and show that they are equivalent to EFI pairs.
EFI⇔1PRS
A series of recent works has established EFI pairs as the "minimal" assumption for quantum cryptography. Recently, Cavalar et al. [CCC+26] showed that EFI pairs are equivalent to non-uniform expanding single-copy pseudorandom state generators (1PRS), and obtained a non-uniform meta-complexity characterization of EFI pairs. We remove the non-uniformity in their construction and prove that EFI pairs are equivalent to expanding 1PRS. As a corollary, we obtain the first uniform meta-complexity characterization of EFI pairs. Together with the equivalence of statistically verifiable one-way state generators and commitments proved by Batra and Jain [BJ24], this gives a quantum analogue of the classical equivalence between one-way functions, commitments, and pseudorandom generators.
In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.
One-way state generators (OWSG) [1] are natural quantum analogs to classical one-way functions. We consider statistically-verifiable OWSGs (sv-OWSG), which are potentially weaker objects than OWSGs. We show thatO(log(n)n)-copy sv-OWSGs (nrepresents the input length) are equivalent topoly(n)-copy sv-OWSGs and to quantum commitments. Since known results show thato(log(n)n)-copy OWSGs cannot imply commitments [2], this shows thatO(log(n)n)-copy sv-OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography). Our construction follows along the lines of Hastad, Impagliazzo, Levin and Luby [3], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [3] to obtain a classical mildly non-uniform PRG from any classical OWF. Since we do not argue conditioned on the outputf(x), our construction and analysis is arguably simpler and may be of independent interest. For converting a mildly non-uniform PRG to a uniform PRG, we can use the same construction as [3].
There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that P ≠ N P , which gives a lower bound on the necessary hardness.One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.We show that pseudorandom states compressing n bits to log n + 1 qubits can be used to build one-way state generators and pseudorandom states compressing n bits to ω ( log n ) qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than c log n -qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a P P oracle.An interesting implication of our results is that a t ( n ) -copy one-way state generator exists unconditionally, for every t ( n ) = o ( n / log n ) . This contrasts nicely with the previously known fact that O ( n ) -copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments.