Computational Cryptography from Pseudoentanglement

AI summary

Overview

Research area: Quantum cryptography, computational entanglement theory, and quantum information theory.
Technical level: Advanced. The paper assumes familiarity with quantum states, trace distance, LOCC, quantum polynomial-time (QPT) algorithms, and cryptographic indistinguishability.
Scope: The paper proves that two operational notions of pseudoentanglement are sufficient for EFI pairs, establishes an equivalence for one of them, and develops technical lemmas linking computational entanglement measures to trace distance.

What This Paper Is About

Pseudoentanglement describes families of quantum states that appear highly entangled to an efficient quantum observer but are actually low-entanglement. EFI pairs are pairs of efficiently preparable quantum states that are statistically far apart but computationally indistinguishable, and they are a leading candidate for the minimal assumption underlying quantum cryptography. This paper asks how pseudoentanglement and EFI pairs relate, and shows that pseudoentanglement can serve as a cryptographic resource under operational definitions.

Key Contributions

1. Fully-computational pseudoentanglement implies EFI pairs. The authors show that pseudoentanglement as defined by [3], with efficient state generation, is sufficient to construct EFI pairs, and they give an explicit construction.
2. Inefficiently-distillable pseudoentanglement is equivalent to EFI pairs. Building on [11], they prove the missing direction, so that this version of pseudoentanglement is both necessary and sufficient for EFI pairs.
3. New technical lemmas in computational entanglement theory. The paper establishes error-continuity of the computational entanglement cost, relates entanglement gaps to trace distance, and proves an amplification result for distinguishing mixtures of states.
4. A bridge between physics and cryptography. The results place pseudoentanglement alongside other minimal assumptions in cryptography and give a new operational resource for constructing cryptographic primitives.

Main Findings

• Fully-computational pseudoentanglement is sufficient for EFI pairs (Theorem 1.4 / Theorem 4.3). Given families ({k,\psi^k}_k) and ({k,\phi^k}_k) with (c<d) and efficient QPT generators, the authors construct an EFI pair by taking uniform mixtures of polynomially many copies: ((\rho_0^\lambda,\rho_1^\lambda) := (\mathbb{E}_k[\psi^{k\otimes q(\lambda)}], \mathbb{E}_k[\phi^{k\otimes q(\lambda)}])). Efficient preparation is assumed, computational indistinguishability follows from pseudoentanglement, and statistical distance follows from the trace-distance/entanglement-gap lemma.

• Inefficiently-distillable pseudoentanglement is equivalent to EFI pairs (Theorem 1.6 / Theorem 5.3). The existence of inefficiently-distillable ((\varepsilon,c,d))-pseudoentanglement with (c<d), (\varepsilon(\lambda)\in O(2^{-\lambda})), and both families efficiently preparable is both necessary and sufficient for EFI pairs. The explicit construction is ((\rho_0^\lambda,\rho_1^\lambda):=(\psi^\lambda,\phi^\lambda)).

• Error-continuity of the computational entanglement cost (Lemma 1.1 / Lemma 3.1). If two families are at most (\delta)-close in trace distance, with (\frac12|\rho^\lambda-\sigma^\lambda|_1\leq \delta(\lambda)) and (\sqrt{\varepsilon(\lambda)}+\delta(\lambda)\leq 1), then an upper bound (\hat{E}_C^\varepsilon({\rho^\lambda})\leq n) implies (\hat{E}_C^{\varepsilon'}({\sigma^\lambda})\leq n), where (\varepsilon') is polynomial in ((\delta,\sqrt{\varepsilon})). The paper describes this as the first continuity relation for a computational entanglement measure.

• Small trace distance rules out an entanglement gap (Lemma 1.2 / Lemma 3.3). If (\hat{E}_C^\varepsilon({\rho^\lambda})\leq c), (\hat{E}_D^\varepsilon({\sigma^\lambda})\geq d), (\varepsilon) vanishes at infinity, and the trace distance is bounded by a vanishing function (\delta), then for large enough (\lambda), (c(\lambda)\geq d(\lambda)). Equivalently, a genuine entanglement gap implies that the states are far in trace distance.

• Mixtures of pairwise-distant states are distinguishable (Lemma 1.3 / Lemma 4.2). If the pairwise trace distance between states from two families is at least an inverse polynomial (1/p(\lambda)), then there exists a polynomial (q(\lambda)) such that the trace distance between the (q(\lambda))-copy mixtures is at least (1-\varepsilon(\lambda)) for negligible (\varepsilon). The

Authors’ 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.