Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.07859 · ACM Symposium on Theory of Computing (STOC)

A Meta-complexity Characterization of Minimal Quantum Cryptography

Bruno Pasqualotto Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, Xingjian Li

Published Jun 9, 2026• 6 citations
arXivHTMLPDF

Abstract

We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy.

DOI
10.1145/3798129.3800783

Related papers

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

Rishabh Batra

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.

quant-pharXiv:2610.18799•Oct 14, 2026•0 citations

On the Computational Hardness Needed for Quantum Cryptography

Zvika Brakerski, Ran Canetti, Luowen Qian

In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

arXiv:2209.04101•Leibniz international proceedings in informatics•Sep 9, 2022•56 citations

Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity

Morteza Saberikamarposhti

We initiate the time-bounded meta-complexity program for quantum cryptography. Recent work characterizes one-way puzzles, the minimal search primitive of quantum cryptography without one-way functions, by the average-case hardness of approximating the plain, uncomputable Kolmogorov complexity over quantumly samplable distributions; the classical program of Liu and Pass, by contrast, lives at polynomial time bounds. We define a probabilistic time-bounded quantum program complexity pKq^t for classical strings and prove two unconditional theorems. First, a quantum coding theorem: any string output by a quantum polynomial-time sampler with probability delta admits a description of the information-theoretically optimal length log(1/delta) plus logarithmic terms, decodable by a quantum machine in time O(sqrt(1/delta)) times a polynomial, via amplitude amplification over the coherently executed sampler. Second, an exact characterization at subexponential time: one-way puzzles exist if and only if the gap problem for pKq at time bound 2^(n/2) poly(n) is weakly quantum-average-hard, refining the plain-complexity characterizations. We then isolate the polynomial-time coding theorem as the single load-bearing open conjecture of the program, prove that it implies the full polynomial-time characterization, analyze why the classical derandomization proof resists quantization, and formulate a relativized barrier conjecture delimiting string-valued meta-complexity at one-way puzzles. Conjectures are labeled as such throughout.

quant-pharXiv:2609.02687•Sep 3, 2026•0 citations

Computationally secure quantum cryptography without one-way functions

Luowen Qian

Most interesting cryptography happens in the computational realm where all parties can only perform efficient computations. On one hand, without this constraint many practically relevant cryptographic tasks are infeasible; on the other, this constraint still captures the power of any physical attacker with limited resources. Classically, if the task of attacking almost any interesting computational cryptography is provably hard, then we would also derive from it the existence of one-way functions, and thus P ≠ NP as well. Quantum mechanics offers a more complete model of physical information in the real world. Recent works have proved oracle separations (Kretschmer’21; Kretschmer, Qian, Sinha, Tal’23; Lombardi, Ma, Wright’23) suggesting that computationally secure quantum cryptography could exist even if P = NP, or in other words, that classical cryptography is infeasible. This hints at the possibility of constructing a quantum cryptosystem and establishing its security without unproven assumptions, liberating cryptographers from the perpetual cat-and-mousegame. In this dissertation, we make initial progress towards this goal by developing a theory of quantum computational cryptography without assuming the existence ofone-way functions. More specifically, we establish the following results: • We introduce a simple and natural quantum cryptographic primitive called EFI pairs, and prove its existential equivalence to various other quantum cryptographic primitives, including commitment schemes, oblivious transfer, and zero knowledge.• We establish the “minimality” of EFI pairs by showing that their existence is implied by many natural cryptographic primitives. EFI pairs thus appear easier to construct than other primitives. • We show that the existence of EFI pairs (and the existentially equivalent primitives) is robust by showing how to upgrade various notions of “weak” security to standard security without any additional assumption. • We finally construct commitment schemes, oblivious transfer, and zero knowledge unconditionally if a piece of quantum advice is allowed. In contrast, classical analogues of these are impossible without first settling P ≠ NP even if we allow randomized advice.

•Jan 1, 2024•0 citations

Computational Cryptography from Pseudoentanglement

Ilia Ryzov, Manuel Goulão, Faedi Loulidi +1 more

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.

quant-pharXiv:2609.29917•Sep 25, 2026•1 citation

Pseudo-Entanglement is Necessary for EFI Pairs

Manuel Goulão, David Elkouss

Regarding minimal assumptions, most of classical cryptography is known to depend on the existence of One-Way Functions (OWFs). However, recent evidence has shown that this is not the case when considering quantum resources. Besides the well known unconditional security of Quantum Key Distribution, it is now known that computational cryptography may be built on weaker primitives than OWFs, e.g., pseudo-random states [JLS18], one-way state generators [MY23], or EFI pairs of states [BCQ23]. We consider a new quantum resource, pseudo-entanglement, and show that the existence of EFI pairs, one of the current main candidates for the weakest computational assumption for cryptography (necessary for commitments, oblivious transfer, secure multi-party computation, computational zero-knowledge proofs), implies the existence of pseudo-entanglement, as defined by [ABF+24, ABV23] under some reasonable adaptations. We prove this by constructing a new family of pseudo-entangled quantum states given only EFI pairs. Our result has important implications for the field of computational cryptography. It shows that if pseudo-entanglement does not exist, then most of cryptography cannot exist either. Moreover, it establishes pseudo-entanglement as a new minimal assumption for most of computational cryptography, which may pave the way for the unification of other assumptions into a single primitive. Finally, pseudo-entanglement connects physical phenomena and efficient computation, thus, our result strengthens the connection between cryptography and the physical world.

arXiv:2406.06881•Jun 11, 2024•5 citations
We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy.
EFI⇔1PRS\mathsf{EFI}\Leftrightarrow\mathsf{1PRS}EFI⇔1PRS
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.
In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.
We initiate the time-bounded meta-complexity program for quantum cryptography. Recent work characterizes one-way puzzles, the minimal search primitive of quantum cryptography without one-way functions, by the average-case hardness of approximating the plain, uncomputable Kolmogorov complexity over quantumly samplable distributions; the classical program of Liu and Pass, by contrast, lives at polynomial time bounds. We define a probabilistic time-bounded quantum program complexity pKq^t for classical strings and prove two unconditional theorems. First, a quantum coding theorem: any string output by a quantum polynomial-time sampler with probability delta admits a description of the information-theoretically optimal length log(1/delta) plus logarithmic terms, decodable by a quantum machine in time O(sqrt(1/delta)) times a polynomial, via amplitude amplification over the coherently executed sampler. Second, an exact characterization at subexponential time: one-way puzzles exist if and only if the gap problem for pKq at time bound 2^(n/2) poly(n) is weakly quantum-average-hard, refining the plain-complexity characterizations. We then isolate the polynomial-time coding theorem as the single load-bearing open conjecture of the program, prove that it implies the full polynomial-time characterization, analyze why the classical derandomization proof resists quantization, and formulate a relativized barrier conjecture delimiting string-valued meta-complexity at one-way puzzles. Conjectures are labeled as such throughout.
Most interesting cryptography happens in the computational realm where all parties can only perform efficient computations. On one hand, without this constraint many practically relevant cryptographic tasks are infeasible; on the other, this constraint still captures the power of any physical attacker with limited resources. Classically, if the task of attacking almost any interesting computational cryptography is provably hard, then we would also derive from it the existence of one-way functions, and thus P ≠ NP as well. Quantum mechanics offers a more complete model of physical information in the real world. Recent works have proved oracle separations (Kretschmer’21; Kretschmer, Qian, Sinha, Tal’23; Lombardi, Ma, Wright’23) suggesting that computationally secure quantum cryptography could exist even if P = NP, or in other words, that classical cryptography is infeasible. This hints at the possibility of constructing a quantum cryptosystem and establishing its security without unproven assumptions, liberating cryptographers from the perpetual cat-and-mousegame. In this dissertation, we make initial progress towards this goal by developing a theory of quantum computational cryptography without assuming the existence ofone-way functions. More specifically, we establish the following results: • We introduce a simple and natural quantum cryptographic primitive called EFI pairs, and prove its existential equivalence to various other quantum cryptographic primitives, including commitment schemes, oblivious transfer, and zero knowledge.• We establish the “minimality” of EFI pairs by showing that their existence is implied by many natural cryptographic primitives. EFI pairs thus appear easier to construct than other primitives. • We show that the existence of EFI pairs (and the existentially equivalent primitives) is robust by showing how to upgrade various notions of “weak” security to standard security without any additional assumption. • We finally construct commitment schemes, oblivious transfer, and zero knowledge unconditionally if a piece of quantum advice is allowed. In contrast, classical analogues of these are impossible without first settling P ≠ NP even if we allow randomized advice.
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.
Regarding minimal assumptions, most of classical cryptography is known to depend on the existence of One-Way Functions (OWFs). However, recent evidence has shown that this is not the case when considering quantum resources. Besides the well known unconditional security of Quantum Key Distribution, it is now known that computational cryptography may be built on weaker primitives than OWFs, e.g., pseudo-random states [JLS18], one-way state generators [MY23], or EFI pairs of states [BCQ23]. We consider a new quantum resource, pseudo-entanglement, and show that the existence of EFI pairs, one of the current main candidates for the weakest computational assumption for cryptography (necessary for commitments, oblivious transfer, secure multi-party computation, computational zero-knowledge proofs), implies the existence of pseudo-entanglement, as defined by [ABF+24, ABV23] under some reasonable adaptations. We prove this by constructing a new family of pseudo-entangled quantum states given only EFI pairs. Our result has important implications for the field of computational cryptography. It shows that if pseudo-entanglement does not exist, then most of cryptography cannot exist either. Moreover, it establishes pseudo-entanglement as a new minimal assumption for most of computational cryptography, which may pave the way for the unification of other assumptions into a single primitive. Finally, pseudo-entanglement connects physical phenomena and efficient computation, thus, our result strengthens the connection between cryptography and the physical world.