pith. sign in

arxiv: 2312.16025 · v4 · pith:WZK3ACBOnew · submitted 2023-12-26 · 🪐 quant-ph · cs.CC· cs.CR

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

Minki Hhan , Tomoyuki Morimae , Takashi Yamakawa This is my paper

Pith reviewed 2026-05-24 05:40 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.CR
keywords one-way state generatorsoutput lengthEFIsquantum cryptographyone-way functionssecurity boundspseudorandom generators
0
0 comments X

The pith

There do not exist one-way state generators with O(log λ)-qubit outputs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that standard one-way state generators cannot have outputs of only O(log λ) qubits long. This strengthens an earlier conjecture and shows that a known construction achieving any ω(log λ) output length is optimal. The work also gives nearly matching constructions and impossibility results for inverse-polynomial-advantage OWSGs, constant-advantage OWSGs, weak OWSGs, and EFIs under standard assumptions such as the existence of one-way functions or pseudorandom generators. These bounds clarify the minimal state sizes needed to satisfy the one-wayness property against quantum polynomial-time adversaries.

Core claim

The central claim is that there do not exist OWSGs with O(log λ)-qubit outputs. This is shown by reducing any such short-output generator to a contradiction with the definition of one-wayness. Parallel results prove non-existence of O(log λ)-qubit EFIs while constructing ω(log λ)-qubit EFIs from exponentially secure PRGs, and give tight bounds for OWSG variants parameterized by their advantage ε.

What carries the argument

The standard OWSG security definition (a quantum polynomial-time adversary cannot recover the input with non-negligible probability from the output state) together with the fixed 2^m-dimensional Hilbert space of an m-qubit output register.

If this is right

  • The Cavalar et al. construction with m=ω(log λ) is optimal for standard OWSGs.
  • λ^{-c}-OWSGs require at least (c log λ - 2) qubit outputs.
  • O(1)-advantage OWSGs require more than ((log log λ)/2) qubit outputs.
  • Weak OWSGs ((1-1/poly(λ))-advantage) require ω(1) qubit outputs.
  • EFIs cannot exist with O(log λ) qubit outputs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The results suggest that quantum one-way primitives require output states with dimension growing faster than any polynomial in the security parameter to achieve negligible advantage.
  • Designers of quantum protocols may need to allocate at least logarithmic qubit overhead when replacing classical one-way functions with state generators.
  • The gap between the O(log log λ) constructions and the Ω(log log λ) lower bound for constant-advantage OWSGs leaves open whether the constants can be improved.

Load-bearing premise

That OWSG security is defined solely by the inability of a quantum polynomial-time adversary to recover the input with non-negligible probability from the output state.

What would settle it

An explicit construction of an OWSG whose outputs are O(log λ) qubits long and that meets the standard security definition against quantum polynomial-time adversaries.

read the original abstract

We study the output length of one-way state generators (OWSGs), their weaker variants, and EFIs. - Standard OWSGs. Recently, Cavalar et al. (arXiv:2312.08363) give OWSGs with $m$-qubit outputs for any $m=\omega(\log \lambda)$, where $\lambda$ is the security parameter, and conjecture that there do not exist OWSGs with $O(\log \log \lambda)$-qubit outputs. We prove their conjecture in a stronger manner by showing that there do not exist OWSGs with $O(\log \lambda)$-qubit outputs. This means that their construction is optimal in terms of output length. - Inverse-polynomial-advantage OWSGs. Let $\epsilon$-OWSGs be a parameterized variant of OWSGs where a quantum polynomial-time adversary's advantage is at most $\epsilon$. For any constant $c\in \mathbb{N}$, we construct $\lambda^{-c}$-OWSGs with $((c+1)\log \lambda+O(1))$-qubit outputs assuming the existence of OWFs. We show that this is almost tight by proving that there do not exist $\lambda^{-c}$-OWSGs with at most $(c\log \lambda-2)$-qubit outputs. - Constant-advantage OWSGs. For any constant $\epsilon>0$, we construct $\epsilon$-OWSGs with $O(\log \log \lambda)$-qubit outputs assuming the existence of subexponentially secure OWFs. We show that this is almost tight by proving that there do not exist $O(1)$-OWSGs with $((\log \log \lambda)/2+O(1))$-qubit outputs. - Weak OWSGs. We refer to $(1-1/\mathsf{poly}(\lambda))$-OWSGs as weak OWSGs. We construct weak OWSGs with $m$-qubit outputs for any $m=\omega(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 \lambda)$-qubit EFIs. We show that this is tight by proving that there exist $\omega(\log \lambda)$-qubit EFIs assuming the existence of exponentially secure PRGs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves lower bounds on output lengths for one-way state generators (OWSGs) and their variants (including ε-OWSGs, constant-advantage OWSGs, and weak OWSGs) as well as for EFIs. It shows non-existence of standard OWSGs with O(log λ)-qubit outputs (strengthening Cavalar et al.'s conjecture), provides almost-tight constructions from OWFs for weaker variants with specific output lengths like ((c+1)log λ + O(1)) for λ^{-c}-OWSGs, and establishes matching lower bounds; similar tightness results hold for EFIs assuming exponentially secure PRGs.

Significance. If the results hold, they establish optimality of known OWSG constructions in output length and resolve an open conjecture, while giving new constructions for parameterized/weak variants. The work strengthens the foundations of quantum cryptographic primitives by relating output size directly to security parameters and advantage levels.

major comments (2)
  1. [Abstract / main theorems on non-existence] Abstract and main non-existence claims: the proofs that no OWSGs exist with O(log λ)-qubit outputs (and analogous bounds for ε-OWSGs and constant-advantage OWSGs) reduce existence to a contradiction with one-wayness via a counting/search argument. This relies on modeling the output as an m-qubit register whose Hilbert space has dimension exactly 2^m. If the OWSG definition permits states supported on a strictly larger space (effective dimension not pinned to 2^m), the inversion advantage may become negligible and the non-existence result would not apply. Please state the precise definition of OWSG output used and confirm whether the argument extends to more general state spaces.
  2. [ε-OWSG results] Abstract, ε-OWSG section: the construction achieves ((c+1)log λ + O(1))-qubit outputs while the lower bound rules out at most (c log λ - 2) qubits. The O(1) additive gap is not closed; if the central claim is that the construction is 'almost tight,' the paper should either tighten the constants or explain why the gap cannot be removed under the same assumptions.
minor comments (2)
  1. [Preliminaries] Notation for output length m is used interchangeably with 'm-qubit outputs' without an explicit definition of the register dimension in the preliminaries; add a short paragraph clarifying the Hilbert-space modeling.
  2. [Weak OWSGs] The weak-OWSG construction assumes exponentially secure OWFs with linear expansion; cite the precise theorem or reference used for this assumption.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive recommendation of minor revision and the detailed comments. We address each major comment below and will update the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract / main theorems on non-existence] Abstract and main non-existence claims: the proofs that no OWSGs exist with O(log λ)-qubit outputs (and analogous bounds for ε-OWSGs and constant-advantage OWSGs) reduce existence to a contradiction with one-wayness via a counting/search argument. This relies on modeling the output as an m-qubit register whose Hilbert space has dimension exactly 2^m. If the OWSG definition permits states supported on a strictly larger space (effective dimension not pinned to 2^m), the inversion advantage may become negligible and the non-existence result would not apply. Please state the precise definition of OWSG output used and confirm whether the argument extends to more general state spaces.

    Authors: We use the standard definition of an m-qubit OWSG, in which the output state resides in a Hilbert space of dimension exactly 2^m (i.e., the state is supported on an m-qubit register). This matches the definitions employed in Cavalar et al. and other prior works on OWSGs. The counting argument in our non-existence proofs explicitly uses the fact that there are at most 2^{2^m} distinct pure states in this space to obtain the contradiction with one-wayness. We will add a clarifying sentence in the preliminaries (and a footnote in the abstract) stating this precise definition. The argument does not apply to states whose effective support has dimension larger than 2^m, but such a relaxation falls outside the standard OWSG definition we consider. revision: yes

  2. Referee: [ε-OWSG results] Abstract, ε-OWSG section: the construction achieves ((c+1)log λ + O(1))-qubit outputs while the lower bound rules out at most (c log λ - 2) qubits. The O(1) additive gap is not closed; if the central claim is that the construction is 'almost tight,' the paper should either tighten the constants or explain why the gap cannot be removed under the same assumptions.

    Authors: The leading coefficient c in both the construction ((c+1)log λ + O(1)) and the lower bound (c log λ - 2) matches exactly; the additive O(1) discrepancy is an artifact of the concrete security reductions (hybrid arguments and Chernoff bounds in the construction, and the precise counting thresholds in the lower bound). We view the bounds as almost tight because the dominant term is identical. Under plain OWFs it is unclear whether the additive constants can be fully closed without additional assumptions. In the revision we will insert a short paragraph after the ε-OWSG theorem statements explaining the source of the gap and reiterating that the results are asymptotically tight in the leading term. revision: yes

Circularity Check

0 steps flagged

No circularity: non-existence proofs rely on standard one-wayness definitions and dimension counting

full rationale

The paper proves non-existence of short-output OWSGs by reducing any candidate generator to a QPT adversary that inverts with non-negligible probability, using the standard definition of OWSG security and the modeling of outputs as m-qubit states (Hilbert space dimension 2^m). This reduction is external to the paper's own constructions or prior self-citations; it invokes no fitted parameters, self-definitional equations, or load-bearing self-citations. The cited conjecture of Cavalar et al. is treated as an external statement being strengthened, not as an internal premise. All bounds follow directly from counting arguments on the output register without renaming or smuggling ansatzes. The derivation is therefore self-contained against the standard cryptographic definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Results rest on the standard cryptographic assumption that one-way functions or subexponentially secure one-way functions exist; these are external to the paper. No free parameters are fitted inside the derivations. No new entities are postulated.

axioms (2)
  • domain assumption Existence of (subexponentially secure) one-way functions or pseudorandom generators with linear expansion.
    Invoked for all positive constructions of ε-OWSGs, weak OWSGs, and EFIs.
  • standard math Standard definition of quantum polynomial-time adversaries and negligible vs. inverse-polynomial advantage.
    Used throughout the security definitions and lower-bound arguments.

pith-pipeline@v0.9.0 · 6016 in / 1454 out tokens · 27769 ms · 2026-05-24T05:40:04.963689+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Pseudorandom (function-like) quantum state generators: New definitions and applications

    Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. Pseudorandom (function-like) quantum state generators: New definitions and applications. TCC, 2022

    work page 2022

  2. [2]

    Quantum versus classical proofs and advice

    Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. Theory OF Computing , 3:129--157, 2007

    work page 2007

  3. [3]

    Pseudorandom strings from pseudorandom quantum states

    Prabhanjan Ananth, Yao-Ting Lin, and Henry Yuen. Pseudorandom strings from pseudorandom quantum states. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2024

    work page 2024

  4. [4]

    Cryptography from pseudorandom quantum states

    Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I , volume 13507 of LNCS , pages 208--236. Springer, Heidelberg, August 2022

    work page 2022

  5. [5]

    Alice and Bob meet Banach , volume 223

    Guillaume Aubrun and Stanis aw J Szarek. Alice and Bob meet Banach , volume 223. American Mathematical Soc., 2017

    work page 2017

  6. [6]

    On the computational hardness needed for quantum cryptography

    Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. ITCS 2023, 2023

    work page 2023

  7. [7]

    Quantum fingerprinting

    Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Phys. Rev. Lett. , 87:167902, 2001

    work page 2001

  8. [8]

    Random oracles in a quantum world

    Dan Boneh, \"O zg \"u r Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011 , volume 7073 of LNCS , pages 41--69. Springer, Heidelberg, December 2011

    work page 2011

  9. [9]

    o rn M \

    Aleksandrs Belovs and Juris Smotrovs. A criterion for attaining the welch bounds with applications for mutually unbiased bases. In Jacques Calmet, Willi Geiselmann, and J \" o rn M \" u ller - Quade, editors, Mathematical Methods in Computer Science, MMICS 2008, Karlsruhe, Germany, December 17-19, 2008 - Essays in Memory of Thomas Beth , volume 5393 of Le...

    work page 2008

  10. [10]

    Scalable pseudorandom quantum states

    Zvika Brakerski and Omri Shmueli. Scalable pseudorandom quantum states. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II , volume 12171 of LNCS , pages 417--440. Springer, Heidelberg, August 2020

    work page 2020

  11. [11]

    On the computational hardness of quantum one-wayness

    Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall, Yanyi Liu, and Angelos Pelecanos. On the computational hardness of quantum one-wayness. arXiv:2312.08363 , 2023

    work page arXiv 2023

  12. [12]

    Perfectly concealing quantum bit commitment from any quantum one-way permutation

    Paul Dumais, Dominic Mayers, and Louis Salvail. Perfectly concealing quantum bit commitment from any quantum one-way permutation. In Bart Preneel, editor, EUROCRYPT 2000 , volume 1807 of LNCS , pages 300--315. Springer, Heidelberg, May 2000

    work page 2000

  13. [13]

    A note on computational indistinguishability

    Oded Goldreich. A note on computational indistinguishability. Information Processing Letters 34.6 (1990), pp.277–281., 1990

    work page 1990

  14. [14]

    The Foundations of Cryptography - Volume 1: Basic Techniques

    Oded Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques . Cambridge University Press, 2001

    work page 2001

  15. [15]

    From the hardness of detecting superpositions to cryptography: Quantum public key encryption and commitments

    Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa. From the hardness of detecting superpositions to cryptography: Quantum public key encryption and commitments. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I , volume 14004 of LNCS , pages 639--667. Springer, Heidelberg, April 2023

    work page 2023

  16. [16]

    One-way functions are essential for complexity based cryptography (extended abstract)

    Russell Impagliazzo and Michael Luby. One-way functions are essential for complexity based cryptography (extended abstract). In 30th FOCS , pages 230--235. IEEE Computer Society Press, October / November 1989

    work page 1989

  17. [17]

    Levin, and Michael Luby

    Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In 21st ACM STOC , pages 12--24. ACM Press, May 1989

    work page 1989

  18. [18]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III , volume 10993 of LNCS , pages 126--152. Springer, Heidelberg, August 2018

    work page 2018

  19. [19]

    Quantum cryptography in algorithmica

    William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. STOC, 2023

    work page 2023

  20. [20]

    Kretschmer

    W. Kretschmer. Quantum pseudorandomness and classical complexity. TQC 2021 , 2021

    work page 2021

  21. [21]

    A one-query lower bound for unitary synthesis and breaking quantum cryptography

    Alex Lombardi, Fermi Ma, and John Wright. A one-query lower bound for unitary synthesis and breaking quantum cryptography. Cryptology ePrint Archive, Paper 2023/1602, 2023. https://eprint.iacr.org/2023/1602

    work page 2023

  22. [22]

    Learning quantum states without entangled measurements

    Angus Lowe. Learning quantum states without entangled measurements. Master's thesis, University of Waterloo, 2021

    work page 2021

  23. [23]

    Pseudo-random permutation generators and cryptographic composition

    Michael Luby and Charles Rackoff. Pseudo-random permutation generators and cryptographic composition. In 18th ACM STOC , pages 356--363. ACM Press, May 1986

    work page 1986

  24. [24]

    Quantum commitments and signatures without one-way functions

    Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I , volume 13507 of LNCS , pages 269--295. Springer, Heidelberg, August 2022

    work page 2022

  25. [25]

    One-wayness in quantum cryptography

    Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. In TQC 2024 , 2024. (to appear)

    work page 2024

  26. [26]

    Quantum Computation and Quantum Information

    Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information . Cambridge University Press, 2010

    work page 2010

  27. [27]

    Trace distance from the viewpoint of quantum operation techniques

    Alexey E Rastegin. Trace distance from the viewpoint of quantum operation techniques. Journal of Physics A: Mathematical and Theoretical , 40(31):9533, 2007

    work page 2007

  28. [28]

    L. Welch. Lower bounds on the maximum cross correlation of signals (corresp.). IEEE Transactions on Information Theory , 20(3):397--399, 1974

    work page 1974

  29. [29]

    General properties of quantum bit commitments (extended abstract)

    Jun Yan. General properties of quantum bit commitments (extended abstract). In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV , volume 13794 of LNCS , pages 628--657. Springer, Heidelberg, December 2022

    work page 2022

  30. [30]

    Theory and applications of trapdoor functions (extended abstract)

    Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd FOCS , pages 80--91. IEEE Computer Society Press, November 1982

    work page 1982