- One-way puzzles use quantum mechanics to create encryption keys that exist but cannot efficiently unlock anything.
- Khurana and Tomer connected their quantum cryptographic foundation to the matrix permanent problem.
- Quantum computational advantage and quantum cryptographic security may be equivalent.
Dakshita Khurana spent months stuck on a problem in quantum cryptography that seemed to defy logic. She needed to build encryption from keys that could never unlock anything.
The University of Illinois cryptographer and her graduate student Kabir Tomer were trying to answer a question that keeps security researchers awake: what happens to digital encryption if someone finds a shortcut through the hard math problems protecting it?
Their answer, published in a pair of papers, suggests that quantum physics could provide a safety net beneath the entire cryptographic enterprise.
Key figure
2 → 1
Open cryptography problems collapsed into one by connecting one-way puzzles to quantum computational advantage
Why Classical Encryption Sits on Shaky Ground
Modern encryption relies on mathematical problems that are hard to solve but easy to check. Factor a large number into its primes, and anyone can verify the answer by multiplying them back together. This asymmetry powers everything from online banking to classified communications.
The trouble is that no one has proved these problems are genuinely hard.
A sufficiently clever algorithm could, in principle, crack them all.
What are one-way functions?
One-way functions are the mathematical building blocks beneath modern encryption. They let you create a lock easily but make it practically impossible to pick. If someone finds a fast way to reverse any one-way function, most current cryptography collapses.
Earlier quantum approaches tried to sidestep this vulnerability, but they relied on hypothetical computing devices called oracles. Useful for theory, impossible to build. Fermi Ma, a cryptography researcher at the Simons Institute, described the earlier work as a proof of concept rather than a statement about the real world.
Quantum Locks That Work, Keys That Don't
Khurana and Tomer's answer arrived through a peculiar detour. They defined a new mathematical object they called a one-way puzzle.
Like a classical one-way function, it generates locks and keys made of ordinary bits. Unlike a classical one-way function, generating those pairs requires a quantum computer.
The strangest part: the keys are too inefficient to actually open their locks.
This seems useless. A lock whose key does not work is, by most practical standards, a broken lock. But Khurana and Tomer showed that this apparent defect was precisely the point. The mere existence of a matching key, however slow, was enough to support an entire architecture of quantum cryptographic protocols.
Just knowing that there exists some algorithm that can be arbitrarily slow is sufficient. That is very surprising.
William Kretschmer, Simons Institute
They finished the proof on August 4, 2023. Khurana's daughter was born days later.
From Theoretical Blueprint to Mathematical Bedrock
The first paper established one-way puzzles as a viable foundation. The second phase was harder: grounding them in real mathematics rather than theoretical oracles.
By November 2023, Khurana was back at work. She and Tomer initially planned to anchor their quantum foundation through an intermediate structure called one-way state generators. Instead, they pivoted. They connected one-way puzzles directly to the matrix permanent problem, a notoriously difficult calculation that even quantum computers struggle with.
Read Also
Why Entangled Particles Can't Send Messages Faster Than Light
John Clauser tried to prove Einstein right about quantum mechanics. Instead, his 1972 experiment helped establish that entanglement is real - while confirming it can't…
→This connection collapsed two open problems into one. If researchers can prove that quantum computers truly surpass classical ones at specific sampling tasks, quantum cryptography automatically stands on firmer theoretical ground than nearly any classical encryption scheme.
A Kyoto University team has since strengthened the case, showing that quantum computational advantage exists if and only if one-way puzzles remain secure. The two concepts, once thought separate, appear to be the same question asked in different mathematical languages.
For anyone wondering whether current encryption faces real quantum threats, the practical timeline remains distant. But the theoretical architecture for quantum-resistant encryption is taking shape remarkably fast.
The useless key, it seems, was the most useful idea in the room.
Sources
- Primary Research: Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P-Hardness (Khurana & Tomer, 2024)
- Additional Context:
- Commitments from Quantum One-Wayness (Khurana & Tomer, STOC 2024)
- Quantum Scientists Have Built a New Math of Cryptography (Quanta Magazine, Ben Brubaker)
Fact Check: Claim-by-Claim Verification Verified
All claims verified against academic papers, Quanta Magazine reporting, and Kyoto University research. Quotes, timeline, and technical descriptions confirmed.
Commentary
- Article is primarily sourced from the Quanta Magazine piece by Ben Brubaker, which is well-researched science journalism.
- The theoretical results are rigorous but practical quantum cryptography applications remain distant.
Sources used for verification
Academic/Peer-reviewed:
- Commitments from Quantum One-Wayness - arxiv.org (STOC 2024)
- Founding Quantum Cryptography on Quantum Advantage - iacr.org
Other reliable sources:
- Quantum Scientists Have Built a New Math of Cryptography - quantamagazine.org
Fact-checked by Perplexity Sonar Pro on 2026-03-15
