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

In the world of digital security, the entire system rests on a single, fragile pillar: the belief that some mathematical tasks are easy to do but nearly impossible to undo. Imagine a lock that anyone can snap shut in a second, but for which no one has ever found the key to open it again. This concept, known as a one-way function, is the bedrock of classical cryptography. It allows us to send secret messages, verify identities, and secure transactions, all based on the assumption that while we can easily generate a complex code, reversing the process to find the original input is computationally hopeless. For decades, scientists have believed that if this one-way lock exists, then almost every other useful security tool can be built from it.

However, the rules change when we move from classical bits to quantum states. In the quantum realm, information is carried by particles that can exist in multiple states at once, and the laws of physics that govern them are fundamentally different. Here, the old rules about what is easy or hard to compute do not always apply in the same way. Researchers have discovered that certain quantum security tools might exist even if the classical one-way locks do not. This has led to a search for a new, minimal foundation for quantum cryptography—a single, simple assumption that is weak enough to potentially exist in a quantum world, yet strong enough to build all the necessary security tools. For a long time, a specific pair of quantum states, which are statistically different but look identical to any efficient computer, stood as the leading candidate for this minimal foundation.

A recent study by Rishabh Batra at EPFL has now closed a significant gap in our understanding of this quantum landscape. The research establishes a precise and complete link between these special quantum state pairs and another fundamental quantum tool known as a pseudorandom state generator. In the past, scientists knew these two concepts were equivalent, but only if they allowed for a specific type of "advantage" where the computer could be given a tiny, pre-computed hint to help it solve the problem. This hint, while small, meant the equivalence was not perfectly clean. Batra's work removes this need for any pre-computed advice, proving that the two concepts are equivalent in their purest, most honest form. This means that if one of these quantum tools exists, the other must exist as well, and neither requires any external shortcuts to function.

The significance of this finding lies in how it unifies the field. By proving that these two distinct quantum objects are actually two sides of the same coin, the paper provides the first complete and uniform map of the lowest layer of quantum cryptography. It shows that a wide variety of security tasks, from creating unbreakable commitments to performing secure multi-party calculations, all rely on the exact same underlying assumption. This is a major step forward because it organizes a complex and confusing field around a single, clear principle. Just as classical cryptography was organized around the one-way function, quantum cryptography is now being organized around this new, minimal pair of states.

The path to this discovery involved a clever reimagining of how information is extracted from quantum systems. The researchers started with the known quantum state pairs and asked how to turn them into a generator that produces random-looking quantum states. A previous attempt by other scientists had succeeded, but it relied on knowing a specific number in advance—a number that determined how much information could be safely pulled out of the system. Because this number was unknown, the previous method required a small piece of advice to be fed into the computer to tell it where to stop. Batra's innovation was to design a process that does not need to know this number beforehand. Instead of trying to find the exact stopping point, the new method uses a technique that samples from many different starting points simultaneously. This approach allows the system to extract the necessary randomness without ever needing to pinpoint the exact entropy or information content of the source.

The result is a construction that is both simpler and more robust. It takes the quantum states and, through a series of carefully orchestrated steps involving purification and randomization, produces a stream of states that are indistinguishable from true randomness to any efficient observer. Crucially, this process works without any external hints or pre-computed data. The paper demonstrates that the ability to generate these random states is not just a side effect of the quantum state pairs, but is fundamentally the same capability. This equivalence is not merely a theoretical curiosity; it serves as a rigorous proof that the entire edifice of quantum cryptographic primitives can be built from this single, minimal assumption.

This work also clarifies the relationship between quantum cryptography and the broader field of meta-complexity, which studies how hard it is to describe or compress information. The paper shows that the difficulty of distinguishing these quantum states is directly linked to the difficulty of describing them. If an efficient computer cannot tell the difference between the generated states and true randomness, it also cannot find a short description for them. This connection provides a new way to think about quantum security, framing it not just as a game of hiding information, but as a test of how complex that information truly is. By removing the non-uniformity from the previous proofs, the research offers a uniform characterization, meaning the security holds even when the attacker does not have any pre-computed advantages.

The implications of this finding extend beyond just connecting two concepts. It suggests that the quantum world is more structured than previously thought. The fact that these diverse tools—state generators, commitment schemes, and state pairs—are all equivalent implies a deep underlying unity in quantum information theory. It tells us that we do not need to assume the existence of multiple, unrelated hard problems to build a secure quantum future. Instead, we only need to assume that one specific, minimal condition holds true. If that condition holds, everything else follows naturally. If it does not, then the entire structure of quantum cryptography as we know it may need to be reconsidered.

In the end, this paper provides a solid foundation for the future of quantum security. It takes a question that was left open by previous researchers—whether the equivalence between these tools required a small advantage—and answers it with a definitive "no." The proof is rigorous and relies on established principles of quantum mechanics and information theory. It confirms that the minimal assumption for quantum cryptography is indeed minimal, requiring no extra help to function. For the scientific community, this is a moment of clarity, bringing order to a complex field and providing a clear path forward for building the secure systems of tomorrow. The work stands as a testament to the power of removing unnecessary assumptions to reveal the true, elegant structure of the quantum world.