Computational Cryptography from Pseudoentanglement

1 Introduction

• EFI pairs are efficiently preparable, statistically far, and computationally indistinguishable, and are a candidate minimal assumption for quantum cryptography [BCQ23].The paper addresses the open question in [ABV23] about the relationship between pseudoentanglement and cryptography, focusing on its operational definition.Source: §1 · p. 2

1.1 Contributions

• The introduction divides the results into conceptual connections to minimal cryptographic assumptions and technical lemmas intended to support the main theorems and have independent interest.The conceptual results are presented as relations between pseudoentanglement and computational cryptography.Source: §1.1 · p. 3

Conceptual contributions

• These results connect physical phenomena to computational hardness and make pseudoentanglement a differently structured candidate minimal assumption for cryptography.EFI pairs constructed from fully-computational pseudoentanglement can then yield commitments, oblivious transfer, and secure multiparty computation [BCQ23].Source: Conceptual contributions · pp. 3–4

Other technical results

• The paper establishes error-continuity for computational entanglement cost, relates entanglement gaps to trace distance, and shows that sufficiently distant state families can be distinguished from polynomially many copies with exponentially small error.When the first family's error and its trace distance from the second family both vanish, the second family's error vanishes as well; an entanglement gap implies the corresponding families are far in trace distance.Source: Other technical results · pp. 4–5

1.2 Technical Overview

• The technical overview highlights error-continuity, the trace-distance relation for entanglement gaps, and near-perfect distinguishability between uniform mixtures of states.For mixtures with inverse-polynomial pairwise trace distance across families, polynomially many copies suffice for negligible error; the proof uses the Holevo-Helstrom bound, a Pretty Good Measurement, and Gram-matrix techniques.Source: §1.2 · p. 5, Main contributions · p. 6

Background concepts

• The work studies operational pseudoentanglement via one-shot cost (reconstruction with c(λ) EPR pairs and error at most ε(λ)) and distillable entanglement (production of d(λ) EPR pairs with error at most ε(λ)), including computational versions with QPT-restricted LOCC.EFI pairs can construct computational cryptographic primitives and are implied by almost all other candidate assumptions, including OWFs and pseudorandom states [BCQ23] [AQY22].Source: Background concepts · p. 5

Main contributions

• Fully-computational pseudoentanglement [ABV23] with efficiently generated states suffices for EFI pairs, and inefficiently-distillable pseudoentanglement [GE24] is equivalent to EFI pairs.For the latter, the paper proves sufficiency, completing the necessity result established in [GE24].Source: Main contributions · pp. 6–7

1.3 Related Work

• Earlier constructions of pseudoentanglement [ABV23] [GB23] depend on OWFs, while prior work established necessity for inefficiently-distillable pseudoentanglement [GE24] and sufficiency for regularized relative pseudoentanglement [GY26].The relationship between the original operational definition [ABV23] and quantum cryptography remained open.Source: §1 · p. 2, §1.3 · p. 7
• EFI pairs were shown to imply inefficiently-distillable pseudoentanglement [GE24], motivating a definition that replaces uniform computational distillability with a one-shot information-theoretic condition.The reference family need only possess entanglement, even if it is not efficiently preparable.Source: §1.3 · p. 7
• A construction from EFI pairs makes both pseudoentangled families efficiently preparable, and prior work posed whether inefficiently-distillable pseudoentanglement also implies EFI pairs.This assumption was proposed as a new minimal assumption for computational cryptography.Source: §1.3 · p. 8
• The work [GY26] introduced regularized relative pseudoentanglement and showed that it implies EFI pairs, using asymptotic regularized relative entropy of entanglement rather than one-shot measures.Its structural continuity properties aid EFI construction, but the notion is not tied to efficient LOCC protocols.Source: §1.3 · p. 8
• The paper extends the EFI–pseudoentanglement connection to operational settings, where explicit witnesses can support entanglement certification in cryptographic and LOCC protocols.Such witnesses can include keys and descriptions of efficient distillation and dilution maps for an arbitrary entanglement gap.Source: §1.3 · p. 8
• Unlike regularized relative pseudoentanglement, operational definitions guarantee a separation in entanglement available for efficient preparation or distillation, supporting manipulation and testing procedures.The paper contrasts this with a relative-entropy gap, which alone does not yield such procedures and requires a gap above 2 + 1/Poly(λ).Source: §1.3 · p. 8

2 Background

• The paper works with quantum states on a finite-dimensional Hilbert space, defining a state as a self-adjoint, unit-trace, positive semidefinite operator, and says trace distance and fidelity have useful properties used throughout.It identifies Proposition 2.1 as multiplicativity of fidelity and Proposition 2.2 as the Fuchs-van de Graaf inequality.Source: §2 · pp. 8–9
• The background defines QPT algorithms, negligible functions, and computational indistinguishability for state families against non-uniform QPT distinguishers with polynomial-size advice.Results involving a security parameter are taken asymptotically as that parameter grows.Source: §2 · pp. 9–10

2.1 Entanglement Measures

• One-shot distillable entanglement and entanglement cost quantify LOCC extraction and reconstruction, while computational variants restrict operations to efficient LOCC and include uniform keyed families [BD10] [ABV23].Negligible errors are used for computational indistinguishability, whereas entanglement-measure and trace-distance errors use the weaker vanishing-at-infinity condition.Source: §2.1 · pp. 10, 11, 13

2.2 Pseudoentanglement

• The pseudoentanglement definition introduced in [GE24] replaces Definition 16(ii)’s requirement that more-entangled states be computationally distillable with a requirement on one-shot information-theoretic distillable entanglement.Source: §2.2 · p. 13
• The work assumes a strict entanglement gap, c(λ) < d(λ), and polynomial-time preparability of both families, an additional operational assumption [ABV23, GE24, ABF+24, BFG+24].The gap is identified as necessary for pseudoentanglement to be interesting; efficient preparation is not explicit in the original definitions.Source: §2.2 · p. 14

2.3 EFI Pairs

• EFI pairs [BCQ23] are statistically distinguishable state families that remain indistinguishable to quantum algorithms running in QPT.The families have large trace distance despite their computational indistinguishability.Source: §2.3 · p. 14
• A uniform QPT algorithm must be able to prepare either state family given the security parameter and a bit b ∈ {0, 1}.This is the efficient-preparation condition in the definition.Source: §2.3 · p. 14
• The two states must have noticeable statistical distance, at least 1/p(λ) for some positive polynomial p and sufficiently large λ.This is the definition’s statistical-distance condition.Source: §2.3 · p. 14

3 Error-Continuity of Computational Entanglement Cost and Gap in Computational Entanglement

• When two state families are close in trace distance, a computational entanglement cost upper bound transfers to the second family with an error penalty depending on their closeness.If the first family's error and the trace distance both vanish, the second family's error also vanishes.Source: §3 · p. 14
• Under the lemma's assumptions, a vanishing trace distance between two families precludes an eventual gap between their computational distillable-entanglement lower bound d(λ) and cost upper bound c(λ): c(λ) ≥ d(λ).The stated conclusion holds for all sufficiently large λ.Source: §3 · p. 15
• The gap argument first relates a distillable-entanglement lower bound to a cost bound, then applies the continuity result for one-shot computational cost.The proof uses the trace-distance assumption to transfer the cost bound between families.Source: §3 · pp. 15–16
• Corollary 3.4 gives the analogous eventual c(λ) ≥ d(λ) conclusion when the distillable-entanglement lower bound is information-theoretic rather than computational.The corollary retains the trace-distance closeness condition.Source: §3 · p. 16

• Lemma 4.2 shows that inverse-polynomial pairwise distances suffice for family discrimination with negligible error using polynomially many copies and a PGM.Its proof uses a Gram-matrix approach to bound the PGM’s error.Source: §4 · pp. 17, 20, 21
• Fully-computational pseudoentanglement with efficiently preparable state families implies the existence of EFI pairs.Theorem 4.3 constructs the pair from the two families in the pseudoentanglement structure.Source: §4 · pp. 16, 21
• The construction samples a random key, prepares polynomially many copies from each family, and forgets the key, yielding computationally indistinguishable outputs.The proof uses efficient preparation for the pair and transfers the families’ computational indistinguishability to the resulting states.Source: §4 · p. 21
• The entanglement gap yields inverse-polynomial trace distance for every cross-family pair, which Lemma 4.2 transfers to the uniform mixtures.This establishes the statistical-distance requirement for the constructed EFI pair.Source: §4 · p. 21
• The stepwise functions preserve the asymptotic behavior of p and ε, so the bounds eventually satisfy c⋆ ≥ d⋆.Both ε⋆ and 1/p⋆ converge to zero as λ grows.Source: §4 · pp. 22–23
• If c(λ) < d(λ) for every λ, then beyond a threshold, every pair of keyed states has trace distance exceeding an inverse polynomial.This separation enables the polynomial-copy averaging step used to obtain statistical distance.Source: §4 · p. 23
• Averaging polynomially many copies of the keyed states yields two mixtures that are statistically far, satisfying the EFI pairs’ statistical-distance requirement.The passage states that their trace distance is at least inverse-polynomial for sufficiently large λ.Source: §4 · p. 23

5 Equivalence Between Inefficiently-Distillable Pseudoentanglement and EFI Pairs

• The prior direction constructs inefficiently-distillable pseudoentanglement from an EFI pair, as established in [GE24].The cited result starts from EFI pairs outputting n(λ)-qubit states.Source: §5 · p. 23
• The converse shows that efficiently generated families of inefficiently-distillable pseudoentanglement yield an EFI pair.The construction verifies efficient preparation, computational indistinguishability, and statistical distance requirements.Source: §5 · pp. 23–24
• Efficiently preparable inefficiently-distillable pseudoentanglement with c(λ) < d(λ) is necessary and sufficient for EFI pairs under the stated conditions.The theorem assumes ε(λ) ∈ O(2^-λ).Source: §5 · p. 24

6 Discussion

• The work focuses on operational pseudoentanglement versions from [ABV23] and [GE24], connecting computational constraints on entanglement with cryptography.The discussion highlights differences in the efficiency of distilling entanglement from the high-entanglement family.Source: §6 · p. 24
• The paper shows EFI pairs arise from uniformly efficiently preparable pseudoentanglement and are equivalent to efficiently preparable, inefficiently-distillable pseudoentanglement.The two results address the open EFI-pair connection for [ABV23] and the converse left open in [GE24].Source: §6 · p. 24
• The technical results include the first continuity relation for a computational entanglement measure, a trace-distance condition for entanglement gaps, and a bound for distinguishing mixtures of state families.The paper also proves an amplification result exponential in the number of copies.Source: §6 · pp. 24–25
• The paper leaves open whether fully-computational pseudoentanglement can yield more powerful cryptographic primitives, and whether the studied definitions are equivalent or separated.It also identifies links between physical phenomena and hardness conjectures, and feasibility or experimental realization, as open directions.Source: §6 · p. 25