Cryptography’s New Quantum Foundation
The very scaffolding of the digital economy we cannot see – cryptography – is built on a precarious foundation. We buy, we sell, we talk and we invent with a belief in its infallibility, yet that in itself harbors an unsettling vulnerability. Now, researchers are proposing a radical recalibration — one that rethinks the very assumptions we’ve taken for granted.
For decades, the security of all encrypted communications, digital signatures and protected databases was built on the foundation of what computer scientists referred to as “one-way functions”. These are like pieces of a cryptographic keystone: easy to calculate in one direction (to encrypt a message, say), but practically impossible the other way (i.e. decryption without the key). This asymmetry is of primary importance.
However, such security itself bases its power upon the alleged intractability of some difficult mathematical problems, in particular, “NP problems”. But the catch here is no one has come out and explicitly demonstrated that these problems are actually hard. It is in a way, a mammoth skyscraper built on land not adequately surveyed for seismic activity – we are one algorithmic masterstroke away, at least theoretically, from this global tower of digital trust crumbling.
Such fragility has been long eating away at cryptography. However, a subsequent breakthrough by researchers Dakshita Khurana and Kabir Tomer from the University of Illinois Urbana-Champaign, based on previous theoretical discoveries, provides a proposal for a radical re-synthesis of our digital future. They suggest laying the classical tower aside and building a whole new fortification on a bedrock not subjected to the dilemma of the classical NP problem.
Building Oracles
It all started with a 2021 paper by graduate student William Kretschmer that proposed building hypothetical computing devices called “oracles” to bypass traditional one-way functions. Several researchers consequently showed Kretschmer’s proposal could indeed potentially replace one-way functions and lead to the erection of a whole cryptographic paradigm. Khurana and Tomer have built on this very proposal in an effort to birth this theoretical beauty.
The first concept they had was to construct a quantum analog of one-way functions, problems known as “one-way state generators,” which would employ quantum information (qubits) as their locks, promising security even if classical “locks” were broken. This was however very difficult.
Their real eureka moment came several months later with the realization that an intermediate building block, dubbed “one-way puzzles”, though seemingly paradoxical, was the key. Such puzzles are very interesting: they produce classical locks and keys, analogous to classical one-way functions, but the generation itself is based on quantum computation. And the twist? The so-called “keys” to such puzzles are in no way meant to be unlocked efficiently.
But what use is a key that you cannot readily use, you may ask? Yet, Khurana and Tomer established that it is exactly this very counter-intuitive property that could make such puzzles, combined with other quantum methods, the basis of a broad range of cryptographic applications.
One for the future
This breakthrough in turn gave rise to a pivotal strategic decision: building such one-way puzzles square on a set of mathematical problems that are provably more difficult than the NP problems used in classical cryptography. And what do the researchers propose for this bedrock? The “matrix permanent problem” – a notoriously difficult calculation that involves combinations of numbers in a matrix – so complex that even authenticating a candidate solution is not straightforward. The strategic strength of this decision is closely tied to the notion of quantum computational advantage, if still in its early days, the power of quantum computers to solve certain problems that cannot be solved by classical computers.
Should scientists ever succeed in decisively demonstrating that a quantum computer can be counterpoised to obtain a genuine computational advantage on certain tasks (such as with the matrix permanent problem), that by itself would be the demonstration of a vastly powerful, theoretically independent justification of quantum cryptography.
This entails a paradigm shift in the digital security protocol. It implies that eventually we will develop cryptographic systems whose security would not depend on any hypothetically-hard classical NP problem, but on the actual laws of quantum physics and the known efficacy of quantum computation.
Here is the caveat for the pragmatists: this is not about product deployment right now. Quantum computing technology is still very much in the developing stage and there are no immediate practical applications related to Khurana and Tomer’s specific approach. However, the intellectual re-founding they proposed is enormous.
Their research also offers a roadmap to a cryptographic future in which digital confidence is founded on a whole new, possibly uncrackable, quantum foundation. This fundamental change of perception will be of unequivocal importance to business leaders and decision-makers.
This is a long-term game, yet one guaranteeing the unprecedented resilience in a rapidly digitalized world.
Read: Khurana, D., & Tomer, K. (2024). Founding quantum cryptography on quantum advantage, or, towards cryptography from #P‑hardness (arXiv:2409.15248v2 [quant‑ph]). arXiv.