CS Paper Radar

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

Rishabh Batra

cs.CR quant-ph ·submitted 2026-10-13 17:42 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity

cs.CR quant-ph ·2026-09-10 ·Atul Mantri
similarity 0.71
Abstract

EFI pairs (Brakerski, Canetti, and Qian, ITCS 2023) and one-way puzzles (Khurana and Tomer, STOC 2024) are the leading candidates for the minimal assumption of quantum cryptography. The first are efficiently preparable quantum states, statistically far yet computationally indistinguishable; the second are classical puzzles, easy to sample and hard to solve. One-way puzzles imply EFI pairs, and whether the converse holds is open. We construct a single classical oracle relative to which one-way puzzles do not exist, even with an unbounded verifier, while an EFI pair survives every distinguisher that queries the oracle classically throughout and holds advice about it, making its one superposition query at the end. The oracle answers every question about the output probabilities of quantum samplers, which removes the puzzles, and hides a Haar-random half-dimensional subspace. To prove security we reduce it to communication complexity. An adversary whose knowledge of the subspace arrives as classical query answers can be simulated inside a two-party protocol against the party holding it, so it does no better than the best classical protocol for Vector-in-Subspace (Klartag and Regev, STOC 2011), whatever the oracle computes. That argument does not cover the superposition query, which we bound instead using tools from random matrix theory. The same attack gives a classical simulation of any quantum party in a classical-message protocol with no entanglement shared in advance, so relative to the oracle there is no proof of quantumness either. Quantum polynomial time therefore offers no advantage on any task with classical inputs and outputs, while the two quantum states stay indistinguishable. We state conjectures on removing the restriction on superposition queries.

0.42

Computational Cryptography from Pseudoentanglement

cs.CR quant-ph ·2026-09-24 ·Ilia Ryzov, Manuel Goulão, Faedi Loulidi, David Elkouss
similarity 0.71
Abstract

The advent of pseudoentanglement and computational entanglement theory bootstrapped a wave of research at the intersection of computer science and information theory. In parallel, computational cryptography has undergone substantial development, prompted by the introduction of pseudorandom states and followed by the establishment of a baseline for the computational hardness required for quantum cryptography, from which EFI pairs emerge as a central primitive. We study the connection between pseudoentanglement and computational cryptography through EFI pairs. Our goal is to enable the use of resources arising from computational entanglement theory in the field of cryptography. For this, we establish the relation between operational instances of pseudoentanglement and the hierarchy of minimal assumptions for computational cryptography. We show that the existence of pseudoentanglement under two different operational definitions, with efficient state generation, is a sufficient condition for the existence of EFI pairs. Combined with a previously established result that the converse also holds under the second definition, this allows us to also demonstrate their equivalence. This places pseudoentanglement alongside other minimal assumptions in cryptography, not only offering an alternative perspective on this fundamental problem, but also building a bridge that allows insights from either area to inform the other. While proving these theorems, we introduce and demonstrate technical lemmas in quantum information and computational entanglement theory, relating the computational entanglement measures to the distance between states, establishing distinguishing conditions for mixtures of two families given pairwise distances between their states, and demonstrating the first continuity relation for a computational entanglement measure.

0.26

Quantum Key Exchange from Public Quantum Money

cs.CR quant-ph ·2026-11-04 ·Eli Goldin, Tomoyuki Morimae
theory similarity 0.65
Abstract · 43 pages, 1 figure

Two-message quantum key exchange (2QKE) cannot be realized in a statistically secure way, and therefore some computational assumptions are required. So far, the known weakest assumption for 2QKE is the existence of one-way functions (OWFs). Can we construct 2QKE from a weaker assumption than OWFs? In this paper, we give the first complete characterization of 2QKE. We show that the following four primitives are (existentially) equivalent: everlasting-secure 2QKE, standard 2QKE, efficiently-verifiable state puzzles (EV-StatePuzzs), and one-time secure digital signatures with quantum signatures and signing keys. Because EV-StatePuzzs are potentially weaker than OWFs [Kretschmer, Qian and Tal 2025], the equivalence implies that 2QKE are potentially weaker than OWFs. Moreover, our result shows the equivalence between standard 2QKE and everlasting-secure 2QKE, which means that everlasting security comes for free. Finally, one-shot signatures, quantum lightning, and public-key quantum money mini-schemes imply EV-StatePuzzs, and therefore, our result also gives a new lowerbound, namely everlasting-secure 2QKE, of these public-key unclonable primitives. We also show that one-shot signatures imply QPKE with quantum public keys. [Kitagawa, Morimae,Nishimaki and Yamakawa, 2024] constructed QPKE with quantum public keys from OWFs, and it was open whether QPKE with quantum public keys can be constructed from an assumption weaker than or incomparable to OWFs. Our result gives a potential answer to this question since one-shot signatures seem to be incomparable with OWFs. Moreover, QPKE constructed from one-shot signatures has an additional functionality, which we call certified freeze, that allows the receiver to publish a publicly verifiable classical certificate that computationally binds the receiver to an upper bound on the total number of distinct valid ciphertexts under its verification key.

0.31

Equivalence Between Average-Case Hardness of Learning and Cryptography for Mixed Quantum States

cs.CR quant-ph ·2026-08-14 ·Alexandru Cojocaru, Laura Lewis
theory similarity 0.64
Abstract · 12 pages, no figures

The relationship between cryptography and learning theory has long been a central theme in the foundations of theoretical computer science: cryptographic primitives can imply hardness of learning, while hardness of learning can in turn be used to construct cryptographic schemes. Recent works have begun exploring analogous connections in the quantum setting, relating the average-case hardness of learning quantum states (AHL) to cryptographic primitives such as one-way state generators (OWSG). Despite recent progress exploring this for pure states, the relationship for mixed states has remained an open question. In this work, we prove that the existence of AHL for mixed quantum states is equivalent to the existence of inefficiently verifiable one-way state generators (IV-OWSGs). As a consequence, this relates mixed-state AHL to EFI pairs. Moreover, as a corollary of existing results, we obtain a separation between IV-OWSGs and OWSGs relative to the SWAP oracle.

0.43

Need for Coherent Access in Constructing Quantum Cryptography

cs.CR quant-ph ·2026-09-30 ·Minki Hhan, Changhun Oh, Vaughn Sohn
hot direction similarity 0.64
Abstract

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.

0.21

A Complexity-Theoretic Approach to Proofs of Space

cs.CR cs.CC ·2026-08-10 ·Marshall Ball, Jiaxin Guan
published similarity 0.63
Abstract

A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.

0.22

Quantum Advantage has Few Complexity Implications

cs.CC quant-phcs.CR ·2026-11-03 ·Eli Goldin, Alex Lombardi, Tomoyuki Morimae
similarity 0.63
Abstract

We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.

0.24

Asymmetry and Complexity of Nondeterministic Computations

cs.CC ·2026-10-14 ·Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
theory similarity 0.63
Abstract

Symmetry of Information (SoI) [ZL70] is a fundamental theorem of classical Kolmogorov complexity whose status for time-bounded computation is closely related to central open problems in complexity theory and cryptography. In a recent development, [HMO26] showed that SoI fails for $rKt$ complexity, namely in the setting of randomized computation. By contrast, many basic properties of Kolmogorov complexity are known to remain valid in the presence of nondeterminism [HLO26], suggesting that SoI may provide a fruitful structural principle for exploring the relative power of randomness and nondeterminism in computation. Our results reveal that the validity of SoI for nondeterministic computation, namely for $nKt$ complexity, is a subtle question connected to several frontiers. We show that symmetry of information holds on average for randomized extensions of $nKt$, while its worst case validity would imply breakthrough complexity separations. Although the standard cryptographic argument for asymmetry does not extend to the nondeterministic setting, we provide evidence that information remains asymmetric in nondeterministic computations. Among other results, we show that SoI would imply a collapse of exponential time classes to low levels of the polynomial hierarchy. Then, building on the work of [Hir22b, GK22, KK26, HMO26], we develop a general framework connecting symmetry of information, meta-complexity, and explicit constructions in the nondeterministic setting. More precisely, we prove that suitable formulations of these three notions are quantitatively equivalent. We apply different aspects of this correspondence to make progress on complexity lower bounds and on the failure of SoI for nondeterministic computation. These consequences are unconditional and provide some of the strongest known lower bounds in meta-complexity.

0.22