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

arXiv:2404.03220 · Annual Symposium on Foundations of Computer Science

Commitments are Equivalent to Statistically-Verifiable One-Way State Generators

Rishabh Batra, Rahul Jain

Published Oct 27, 2024• 8 citations
arXivHTMLPDF

Abstract

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 that$O\left(\frac{n}{\log (n)}\right)$-copy sv-OWSGs ($n$represents the input length) are equivalent to$poly (n)$-copy sv-OWSGs and to quantum commitments. Since known results show that$o\left(\frac{n}{\log (n)}\right)$-copy OWSGs cannot imply commitments [2], this shows that$O\left(\frac{n}{\log(n)}\right)$-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 output$f(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].

DOI
10.1109/focs61266.2024.00077

Related papers

$\mathsf{EFI}\Leftrightarrow\mathsf{1PRS}$

Rishabh Batra

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.

quant-pharXiv:2610.18799•Oct 14, 2026•0 citations

One-Wayness in Quantum Cryptography

Tomoyuki Morimae, Takashi Yamakawa

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.

arXiv:2210.03394•Leibniz international proceedings in informatics•Oct 7, 2022•13 citations

On the Computational Hardness of Quantum One-Wayness

Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray +3 more

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.

arXiv:2312.08363•Quantum•Mar 27, 2025•6 citations

Commitments from Quantum One-Wayness

Dakshita Khurana, Kabir Tomer

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.

arXiv:2310.11526•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•23 citations

Need for Coherent Access in Constructing Quantum Cryptography

Minki Hhan, Changhun Oh, Vaughn Sohn

We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRSs) with superlogarithmic output length do not. At first glance, this appears to contradict the known black-box constructions of PRS generators from quantum-secure OWFs. The distinction lies in the access model to the oracles; our oracle separation uses \emph{classical-accessible} random oracles that can be accessed only classically even by quantum algorithms. In fact, our impossibility of PRSs applies to \emph{any} classically accessible classical oracle in place of the random oracle, while keeping the other oracle component unchanged, showing the need for coherent access in constructing PRSs. We further show that logarithmic output length pseudorandom function-like states (PRFSs) exist relative to our oracles, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs. This shows that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS.

quant-pharXiv:2609.40301•Oct 1, 2026•0 citations

A Note on Output Length of One-Way State Generators and EFIs

Minki Hhan, Tomoyuki Morimae, Takashi Yamakawa

We study the output length of one-way state generators (OWSGs), their weaker variants, and EFIs. Standard OWSGs: Recently, Cavalar et al. (Quantum 9, 1679 (2025)) give OWSGs with m-qubit outputs for any m = ω(log λ), where λ is the security parameter, and conjecture that there do not exist OWSGs with O(log log λ)-qubit outputs. We prove their conjecture in a stronger manner by showing that there do not exist OWSGs with O(log λ)-qubit outputs. This means that their construction is optimal in terms of output length. Inverse-polynomial-advantage OWSGs: Let ε-OWSGs be a parameterized variant of OWSGs where a quantum polynomial-time adversary's advantage is at most ε. For any constant c ∈ N, we construct λ^(-c)-OWSGs with ((c+1) log λ + O(1))-qubit outputs assuming the existence of OWFs. We show that this is almost tight by proving that there do not exist λ^(-c)-OWSGs with at most (c log λ – 2)-qubit outputs. Constant-advantage OWSGs: For any constant ε > 0, we construct ε-OWSGs with O(log log λ)-qubit outputs assuming the existence of subexponentially secure OWFs. We show that this is almost tight by proving that there do not exist Θ(1)-OWSGs with ((log log λ)/2 + O(1))-qubit outputs. Weak OWSGs: We refer to (1 – 1/poly(λ))-OWSGs as weak OWSGs. We construct weak OWSGs with m-qubit outputs for any m = ω(1) assuming the existence of exponentially secure OWFs with linear expansion. We show that this is tight by proving that there do not exist weak OWSGs with O(1)-qubit outputs. EFIs: We show that there do not exist O(log λ)-qubit EFIs. We show that this is tight by proving that there exist m(λ)-qubit EFIs for any m(λ) = ω(log λ) assuming the existence of exponentially secure pseudorandom generators.

arXiv:2312.16025•IACR Communications in Cryptology•Oct 6, 2025•1 citation
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(nlog⁡(n))O\left(\frac{n}{\log (n)}\right)O(log(n)n​)-copy sv-OWSGs (nnnrepresents the input length) are equivalent topoly(n)poly (n)poly(n)-copy sv-OWSGs and to quantum commitments. Since known results show thato(nlog⁡(n))o\left(\frac{n}{\log (n)}\right)o(log(n)n​)-copy OWSGs cannot imply commitments [2], this shows thatO(nlog⁡(n))O\left(\frac{n}{\log(n)}\right)O(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)f(x)f(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].
EFI⇔1PRS\mathsf{EFI}\Leftrightarrow\mathsf{1PRS}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.
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.
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.
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.
We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRSs) with superlogarithmic output length do not. At first glance, this appears to contradict the known black-box constructions of PRS generators from quantum-secure OWFs. The distinction lies in the access model to the oracles; our oracle separation uses \emph{classical-accessible} random oracles that can be accessed only classically even by quantum algorithms. In fact, our impossibility of PRSs applies to \emph{any} classically accessible classical oracle in place of the random oracle, while keeping the other oracle component unchanged, showing the need for coherent access in constructing PRSs. We further show that logarithmic output length pseudorandom function-like states (PRFSs) exist relative to our oracles, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs. This shows that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS.
We study the output length of one-way state generators (OWSGs), their weaker variants, and EFIs. Standard OWSGs: Recently, Cavalar et al. (Quantum 9, 1679 (2025)) give OWSGs with m-qubit outputs for any m = ω(log λ), where λ is the security parameter, and conjecture that there do not exist OWSGs with O(log log λ)-qubit outputs. We prove their conjecture in a stronger manner by showing that there do not exist OWSGs with O(log λ)-qubit outputs. This means that their construction is optimal in terms of output length. Inverse-polynomial-advantage OWSGs: Let ε-OWSGs be a parameterized variant of OWSGs where a quantum polynomial-time adversary's advantage is at most ε. For any constant c ∈ N, we construct λ^(-c)-OWSGs with ((c+1) log λ + O(1))-qubit outputs assuming the existence of OWFs. We show that this is almost tight by proving that there do not exist λ^(-c)-OWSGs with at most (c log λ – 2)-qubit outputs. Constant-advantage OWSGs: For any constant ε > 0, we construct ε-OWSGs with O(log log λ)-qubit outputs assuming the existence of subexponentially secure OWFs. We show that this is almost tight by proving that there do not exist Θ(1)-OWSGs with ((log log λ)/2 + O(1))-qubit outputs. Weak OWSGs: We refer to (1 – 1/poly(λ))-OWSGs as weak OWSGs. We construct weak OWSGs with m-qubit outputs for any m = ω(1) assuming the existence of exponentially secure OWFs with linear expansion. We show that this is tight by proving that there do not exist weak OWSGs with O(1)-qubit outputs. EFIs: We show that there do not exist O(log λ)-qubit EFIs. We show that this is tight by proving that there exist m(λ)-qubit EFIs for any m(λ) = ω(log λ) assuming the existence of exponentially secure pseudorandom generators.