On September 7, 2025, researchers reported a major theoretical advance: cryptographers Dakshita Khurana and Kabir Tomer have outlined a realistic route to quantum-based cryptography that does not rely on the classical one-way functions that underpin today’s encryption. Their work links new quantum primitives called one-way puzzles to strong, well-studied mathematical problems such as the matrix permanent, narrowing several open questions to a single, testable conjecture about quantum advantage.
Key Takeaways
- Classical cryptography rests on one-way functions built from hard NP-style problems; their provable hardness remains unestablished.
- William Kretschmer’s 2021 oracle-based result showed quantum cryptography could, in principle, avoid those classical foundations.
- Khurana and Tomer developed quantum-native building blocks—one-way state generators and the intermediate notion of one-way puzzles—that support many cryptographic tasks.
- They proved on August 4, 2023, a crucial structural step tying one-way puzzles to broader cryptographic protocols.
- Their later work anchors one-way puzzles directly to the matrix permanent and related assumptions, reducing two open problems to one.
- If a formal separation showing quantum advantage for a specific task is proven, it would imply strong theoretical foundations for quantum cryptography.
- Practical deployment remains distant: quantum hardware and engineering challenges mean applications are not imminent.
Verified Facts
Modern encryption typically depends on classical one-way functions: easy to compute in one direction but hard to invert without a secret key. Researchers proved in the 1980s that many cryptographic primitives can be built from such functions, which in turn are generally constructed from hard mathematical problems in NP. Those problems are easy to verify but not proven hard to solve, so the entire edifice rests on unproven complexity assumptions.
In 2021 William Kretschmer brought attention to a quantum-specific problem that, in idealized oracle models, could replace classical one-way functions as cryptographic bedrock. That line of work demonstrated a proof-of-concept that quantum properties can enable a wide range of cryptographic tasks even if classical NP problems were easy to solve.
Starting in fall 2022, Dakshita Khurana (University of Illinois at Urbana–Champaign and NTT Research) and her student Kabir Tomer set out to convert the oracle-based constructions into a framework grounded in more realistic, non-oracular assumptions. They defined quantum one-way state generators—procedures that produce quantum “locks” (qubits) that are easy to make but hard to invert classically—and then identified an intermediate primitive they call a one-way puzzle.
One-way puzzles are hybrid objects: they generate classical keys and locks using a quantum procedure. The locks are hard to break, and keys are easy to create, but using a key to efficiently open its corresponding lock need not be feasible. Khurana and Tomer showed that, combined with quantum techniques, these puzzles suffice to build many standard cryptographic tools.
On August 4, 2023, the pair completed a key formal proof connecting one-way puzzles to a broad suite of cryptographic protocols. Later, rather than rely on state generators as an extra layer, they linked one-way puzzles directly to classical hard problems—most notably the matrix permanent—so that the new quantum cryptographic tower rests on established, well-studied complexity assumptions.
Context & Impact
The move from oracle-based proofs to constructions founded on concrete mathematical problems matters because it brings quantum cryptography into the same style of theoretical accountability used in classical cryptography. By reducing the security of many quantum primitives to a single conjecture about quantum advantage for a specific computational task, Khurana and Tomer make the field’s assumptions clearer and more testable.
If researchers can prove that quantum devices outperform classical machines on the targeted task (a form of provable quantum advantage), that result would simultaneously validate one-way puzzles and provide a solid platform for quantum cryptography. In other words, two difficult open questions become one: establish the quantum advantage claim, and a wide array of quantum cryptography follows.
However, this is a theoretical advance. Building usable quantum cryptographic systems will require maturing hardware, error correction, and secure protocols for generating and transmitting quantum states. Other quantum cryptography schemes—some nearer to practical use—remain relevant while the community assesses security assumptions and develops engineering solutions.
Implications for practitioners and policymakers
- Cryptographers gain a clearer research agenda: either prove the necessary quantum advantage or continue hardening classical assumptions.
- Standards bodies should track theoretical progress but avoid premature adoption until practical, verifiable implementations exist.
- Agencies planning post-quantum security must account for both improved classical attacks and the potential for quantum-native protocols in the longer term.
“This work shows a concrete route from quantum primitives to full cryptographic systems under assumptions we can study,”
Fermi Ma, Simons Institute researcher
Unconfirmed
- Timing for any practical, deployed quantum cryptographic system based on these ideas remains unknown and depends on hardware advances.
- Whether a formal, widely accepted proof of the specific quantum advantage needed will be completed is still open.
- Concrete performance and security trade-offs for real-world protocols built from one-way puzzles require further study and experimental validation.
Bottom Line
Khurana and Tomer have moved quantum cryptography from oracle-based proofs toward constructions tied to established mathematical problems, notably the matrix permanent. Their results make the assumptions clear and testable: proving a particular quantum advantage would, in one step, give strong theoretical footing to a broad class of quantum cryptographic schemes. Practical application remains a longer-term prospect, but the new framework sharpens both the scientific targets and the research agenda.