Quantum pseudoresources imply cryptography
Alex B. Grilo, Álvaro Yángüez · 2025
Read Quantum pseudoresources imply cryptography by Alex B. Grilo, Álvaro Yángüez (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15025.txt.
Introduction
Alex Grilo and Alvaro Yanguez published a computing and physics paper in 2025 on whether faint quantum resources can power cryptography. In classical settings, one-way functions are the minimal base for secure computation. Quantum settings allow weaker bases, and the true minimum is open. Recent work showed one such faint resource is necessary, but no one had built security from it.
The authors study pseudoresources: pairs of quantum state families that differ in resource content yet look alike to any efficient test. They show such pairs yield a variant of a known cryptographic pair type. That variant equals quantum commitments and the standard pairs. The moral drawn is that quantum resources may anchor quantum security as randomness anchors the classical kind.
Catalog record
| CREATOR | Alex B. Grilo, Álvaro Yángüez |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15025
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum pseudoresources imply cryptography Alex B. Grilo, Álvaro Yángüez Abstract While one-way functions (OWFs) serve as the minimal assumption for computational cryptography in the classical setting, in quantum cryptography, we have even weaker cryptographic assumptions such as pseudo-random states, and EFI pairs, among others. Moreover, the minimal assumption for computational quantum cryptography remains an open question. Recently, it has been shown that pseudoentanglement is necessary for the existence of quantum cryptography (Goulão and Elkouss 2024), but no cryptographic construction has been built from it. In this work, we study the cryptographic usefulness of quantum pseudoresources —a pair of families of quantum states that exhibit a gap in their resource content yet remain computationally indistinguishable. We show that quantum pseudoresources imply a variant of EFI pairs, which we call EPFI pairs, and that these are equivalent to quantum commitments and thus EFI pairs. Our results suggest that, just as randomness is fundamental to classical cryptography, quantum resources may play a similarly crucial role in the quantum setting. Finally, we focus on the specific case of entanglement, analyzing different definitions of pseudoentanglement and their implications for constructing EPFI pairs. Moreover, we propose a new cryptographic functionality that is intrinsically dependent on entanglement as a resource. 1 Introduction Many quantum resources are fundamental to achieving quantum advantage in information-processing tasks over conventional classical devices, e.g., entanglement [ PV06 , HHHH09 ] , coherence [ BCP14 , SAP17 ] , or ”magic” [ VHMGE14 , HC17 ] . However, the manipulation of physical systems to operate with these resources is constrained in terms of time and space. Ignoring these computational limitations leads to an impractical characterization of such resources. Inspired by complexity theory, a recent line of research studies these resources from a computational perspective. This phenomenon, known as pseudoresources , characterizes states that do not possess a given resource yet ”look like” resourceful states to a computationally bounded observer [ HBK24 , BMB+24 ] . Among the different resources, the concept of pseudoentanglement [ ABF+23 , ABV23 , GE24 , LREJ25 ] stands out as a key example, where entanglement is the “hidden” resource of interest. More concretely, it describes the case where two families of states exhibit a large gap in the amount of their entanglement yet remain indistinguishable to a polynomial-time quantum adversary. In classical cryptography, the resource of randomness plays a crucial role. Moreover, its computational variant, pseudorandomness , is at the core of symmetric cryptographic constructions. This naturally raises the question of the role quantum resources play in quantum cryptography. How can pseudoresource states be constructed from other cryptographic primitives? Which cryptographic functionalities can be implemented given the existence of pseudoresources? In the specific case of pseudoentanglement, various constructions have been proposed, ranging from those based on One-Way Functions (OWFs) 1 1 1 In short, OWFs are functions that are easy to compute but hard to invert. for pure states [ ABF+23 , ABV23 , LREJ25 ] to EFI pairs 2 2 2 An EFI pair consists of two efficiently generated quantum states which are far in trace distance, but which are indistinguishable by computationally bounded adversaries. See Definition 3.1 for a formal definition for mixed states [ GE24 ] . In particular, this latter construction establishes pseudoentanglement as a minimal assumption for the existence of most computationally based quantum cryptographic protocols. However, to the best of our knowledge, no cryptographic primitive has yet been constructed directly from pseudoentangled states. Beyond entanglement, other quantum resources have also been explored from a computational complexity perspective. For instance, recent work has examined magic states [ GLG+24 ] and coherence [ HBK24 ] in the context of complexity theory. Moreover, based on pseudorandom density matrices (PRDMs), these resources have also been studied in the case of mixed states [ BMB+24 ] . PRDMs, which represent density matrices that are computationally indistinguishable from Haar random ones, and pseudomagic pure states have both been shown to imply EFI pairs [ BMB+24 , GLG+24 ] . 3 3 3 Actually, pseudomagic implies EPFI pairs, that we define in this work. In this work, we take a step further and demonstrate that quantum pseudoresources can be leveraged to construct useful cryptographic primitives. To do so, we introduce an extension of EFI pairs, which we call EPFI pairs , and show that they imply quantum commitment in a way similar to how EFI pairs do. More importantly, we present a general method for constructing EPFI pairs from quantum pseudoresources. As a corollary, this establishes that quantum pseudoresources can be used to construct several cryptographic primitives, including commitments, oblivious transfer, and secure multiparty computation. 1.1 Our contribution We describe now our contributions in more details. 1.1.1 Definition of EPFI pairs and constructing commitment schemes. The cryptographic primitive of EFI pairs (Efficiently generated, statistically far and indistinguishable states) was first defined in [ BCQ23 ] , and it consists of a pair of states \rho and \sigma that are far in trace distance but cannot be efficiently distinguished by polynomial-time algorithms. In [ BCQ23 ] , they showed that EFI pairs are equivalent to quantum commitments, more specifically, to the statistically binding variant of canonical quantum commitments introduced in [ Yan22 ] . Consequently, EFI pairs serve as a fundamental assumption for the existence of commitments, oblivious transfer, multiparty computation, and computational zero-knowledge proofs for non-trivial languages. In order to achieve our results, we need to slightly modify such a definition as follows. We consider two keyed families of states \{\rho_{k}\}_{k} and \{\sigma_{k^{\prime}}\}_{k^{\prime}} , and we require that for every k and k^{\prime} , \rho_{k} is far from \sigma_{k^{\prime}} in trace distance, but are still indistinguishable by efficient algorithms. We call such pair of ensembles as EPFI pairs for Efficiently generated, pairwise statistically far and computationally indistinguishable families. We notice that an EFI pair can be seen as an EPFI pair in which each ensemble contains one element. However, EPFI pairs do not trivially imply EFI pairs: we can have families of states that are pairwise far but whose mixture is close. In Section 3 , we demonstrate that the existence of EPFI pairs of ensembles implies the existence of quantum commitments. Informally, a commitment scheme is a two-party cryptographic primitive in which a committer commits to a bit that remains hidden from the receiver until the committer chooses to reveal it. The scheme must satisfy two properties: binding , meaning the committer cannot change the committed value, and hiding , meaning the receiver cannot learn the value before the reveal phase. We focus on the canonical quantum commitments introduced in [ Yan22 ] , where it is shown that proving either binding or hiding in the semi-honest setting—where both parties follow the protocol during the commitment phase—is sufficient. This model simplifies analysis by restricting adversarial behavior to the reveal phase and was proven in [ Yan22 ] to be equivalent to stronger notions of binding, such as sum-binding [ Unr16 ] . For completeness, we briefly explain this construction. As with EFI pairs, EPFI pairs naturally lead to the construction of canonical quantum commitments. • Commit stage: The committer commits to a bit b by generating a bipartite state \ket{\psi^b}_{CR} and sending the register C to the receiver.