Quantum Cryptography: From Theoretical Concepts to Practical Aspirations

The original account of this narrative was initially published in Quanta Magazine.

The Significance of Hard Problems in Cryptography

Hard problems typically evoke a sense of trepidation. However, cryptographers hold them in high regard. This is because specific challenging mathematical problems form the bedrock of modern encryption security. Any novel and efficient solution to these problems would potentially undermine most existing cryptographic forms.

A Quantum - Inspired Breakthrough and Its Initial Shortcomings

Several years ago, researchers uncovered a revolutionary approach to encryption. This method capitalizes on the unique characteristics of quantum physics, thereby circumventing a potential vulnerability present in traditional encryption. Unlike earlier quantum encryption schemes, which were limited to a narrow set of specialized tasks, the new approach has a broader scope of application. It could remain viable even if the fundamental problems in conventional “classical” cryptography were to be effortlessly solved.

Nonetheless, this remarkable discovery was predicated on unrealistic assumptions. As Fermi Ma, a cryptography researcher at the Simons Institute for the Theory of Computing in Berkeley, California, put it, the result was “more of a proof of concept” rather than a statement applicable to the real world.

A New Path to Quantum Cryptography

Now, a recent paper by two cryptographers has charted a course towards quantum cryptography without relying on such outlandish assumptions. Ma commented, “This paper posits that if certain other conjectures hold true, then quantum cryptography must be a feasible reality.”

The Structure of Modern Cryptography

Modern cryptography can be metaphorically envisioned as a tower composed of three essential components.

1. The Bedrock: Lying deep beneath the tower, it consists of hard mathematical problems.

2. The Tower Itself: This is where specific cryptographic protocols are located, enabling functions such as sending private messages, digitally signing documents, and conducting secret ballots.

3. The Foundation: Situated between the bedrock and the tower, it is constructed from building blocks known as one - way functions. These functions are responsible for the asymmetry inherent in any encryption scheme. As Mark Zhandry, a cryptographer at NTT Research, explained, “It’s one - way because encryption of messages is possible, but decryption without the proper key is not.”

In the 1980s, researchers demonstrated that cryptography built on one - way functions could ensure security for a diverse range of tasks. However, even decades later, the strength of the bedrock remains uncertain. The bedrock is made up of special hard problems, technically referred to as NP problems. These problems are characterized by the ease of verifying the correctness of a candidate solution, despite the difficulty of finding the solution itself. For instance, factoring a large number into its prime factors is an NP problem: computationally intensive for large numbers, yet straightforward to verify.

Although many of these problems seem inherently difficult, computer scientists have yet to provide a conclusive proof. If an ingenious algorithm were to be discovered for rapidly solving the most challenging NP problems, the bedrock would crumble, leading to the collapse of the entire cryptographic tower. Moreover, the tower’s foundation, one - way functions, can only be supported by a bedrock of NP problems.

Quantum Physics as a New Hope

To construct a more robust cryptographic tower, cryptographers needed a new foundation not reliant on one - way functions. This seemingly impossible task became feasible a few years ago with the realization that quantum physics could offer a solution.

It all began with a 2021 paper by graduate student William Kretschmer, which highlighted a peculiar problem regarding the properties of quantum systems. Subsequently, researchers demonstrated that Kretschmer’s problem could substitute one - way functions as the foundation for a new edifice of cryptographic protocols. In the following year, Kretschmer and his colleagues proved that this alternative approach could function independently of hard NP problems, suggesting the possibility of building a far more secure cryptographic structure.

However, the quantum problem Kretschmer used as a foundation involved hypothetical computing devices called oracles. These oracles can instantaneously answer specific questions but do not exist in reality. Thus, Kretschmer’s proofs were akin to a blueprint for constructing a castle in the sky, leading to the question of how to make it a practical reality.

Building a New Cryptographic Tower

In the fall of 2022, Dakshita Khurana, a cryptographer at the University of Illinois at Urbana - Champaign and NTT Research, and her graduate student Kabir Tomer took up the challenge of building a new cryptographic tower.

1. Constructing the New Foundation: Their first step was to create a new foundation using quantum building blocks instead of classical one - way functions. They focused on a quantum version of a one - way function, known as a one - way state generator. This generator needed to satisfy three key properties that make one - way functions useful:

2. It must operate efficiently, enabling the easy generation of a cryptographic lock and its corresponding key for each message to be sent.

3. Each lock must be highly secure, requiring substantial effort to break without the correct key.

4. Every lock must be easily opened with the appropriate key.

The key difference was in the nature of the locks. Classical one - way functions generate mathematical locks composed of bits (0s and 1s used in classical computing), while quantum one - way state generators generate locks made of qubits, the units of quantum information. These quantum locks had the potential to remain secure even if all classical locks were easily breakable. However, Khurana and Tomer faced significant difficulties in this step, remaining stuck for many months.

1. The Breakthrough: By July 2023, with Khurana nearly nine months pregnant and Tomer running out of ideas, they made a crucial breakthrough. They defined another mathematical building block, similar to a basement floor, which connected the foundation of one - way state generators to the tower of cryptographic protocols. This building block, which they named one - way puzzles, had a curious combination of quantum and classical characteristics. Locks and keys were made of classical bits, but the generation process required a quantum computer. It satisfied the first two properties of one - way functions (easy generation of locks and keys, and difficulty in breaking locks) but not the third (keys did not easily open their locks). Despite this counterintuitive property, Khurana and Tomer showed that one - way puzzles, in combination with other quantum techniques, could enable many cryptographic protocols. As Kretschmer, now a researcher at the Simons Institute, remarked, “Just knowing that there exists some algorithm that can be arbitrarily slow is sufficient. That is very surprising.” They completed the proof on August 4, shortly before Khurana’s daughter was born.

Anchoring to a New Bedrock

By November, Khurana returned to work and embarked on the second phase of their plan. Initially, they intended to connect the quantum foundation (one - way state generators) to a new, more secure bedrock of math problems. However, they decided to take a more direct approach: anchoring one - way puzzles directly to the mathematical bedrock.

One - way puzzles had some advantages. Their generated locks and keys were classical, despite being a quantum - based concept, which Khurana thought might simplify the connection to classical mathematics. Additionally, the unwieldy keys generated by one - way puzzles could potentially be linked to problems so difficult that even solution verification seemed nearly impossible.

Khurana proposed the matrix permanent problem as a candidate for the new bedrock. This problem, which involves calculating a specific combination of entries in a matrix, is notoriously difficult to solve for large matrices, and there is no straightforward way to check the correctness of a calculation. It also has other appealing mathematical properties for cryptographers. Moreover, the matrix permanent problem is related to a problem where quantum computers have an apparent advantage over classical computers. Khurana and Tomer showed that a proof of this quantum computational advantage would enable them to build secure one - way puzzles and, by extension, the entire edifice of quantum cryptography on top of the permanent problem.

With their new result, Khurana and Tomer have effectively reduced two open problems to one. If researchers can prove that quantum computers truly outperform classical computers at a specific task, it will firmly establish quantum cryptography on a much stronger theoretical footing than most classical cryptographic methods.

The Road Ahead

Alas, the new approach by Khurana and Tomer cannot be immediately utilized for sending secret messages. Quantum computing technology is still in the process of maturation, and thus, their ideas cannot be put into practice at present. Meanwhile, other researchers have developed quantum cryptography methods that may be implemented sooner, although further work is required to ensure their true security.

Quantum cryptography has already been a source of numerous surprises, and researchers are only beginning to explore its vast potential. As Zhandry put it, “We’re just trying to understand this new landscape that really existed the whole time.”

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.