  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.
