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

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.