Author: Taiga Hirooka

Introduction

In this note, we explore the concept of "Quantum Advantage" in cryptography. We will examine the capabilities and limitations of both classical computers and quantum computers to clarify how quantum technology fundamentally changes the landscape of cryptography.

Basic Concepts and Classical Cryptography

The primary goal of cryptography is secure communication. Imagine a "Sender" who wants to transmit private information—such as sensitive biometric data—to a "Receiver." If the Sender transmits this data directly without any protection, it is highly vulnerable. While the Receiver will receive it, an "Attacker" could intercept the communication channel and obtain the exact same information. The goal of cryptography is to ensure that even if data is intercepted, the Sender's private information remains confidential.

The most fundamental protocol for secure communication is Secret Key Encryption. Here, a Sender and Receiver share a "secret key" sk in advance. The process is straightforward: the Sender uses the key sk to encrypt the message M into encrypted data Encsk​(M). The Receiver, possessing the same key, uses sk to decrypt the data and recover M. Critically, an attacker cannot extract any information about the message M from the encrypted data Encsk​(M), regardless of how much time they spend on analysis. This level of security, which remains unbreakable despite an attacker's computational power, is called Information-Theoretic Security. Thus, secret key encryption provides a perfectly secure channel between two parties who already share a key.

While secure, secret key encryption faces a major problem: the Key Distribution Problem. Before secure communication can even begin, the two parties must share the secret key in advance. Sending the key sk over a public communication channel risks interception, while meeting in person to exchange it is often impractical and costly. Ideally, we need a way to communicate securely using only the communication channel itself, without a pre-shared secret key.

Public Key Encryption was developed to solve this problem. (See Figure 1.) Among various protocols, the RSA algorithm is the most renowned. In this system, the Receiver generates their own credentials. Roughly speaking, he chooses two large prime numbers as a secret key sk—for example, 167 and 181. He then calculates the product 167×181=30,227, which becomes the "public key" pk. The Receiver sends this public key pk=30,227 to the Sender. Anyone with the public key pk can encrypt a message M, resulting in Encpk​(M), but decryption requires the original prime factors sk=(167,181). Because the Receiver created the secret key, they can easily decrypt Encpk​(M) and obtain M. An attacker, however, must find the factors of the large number pk=30,227.

In mathematics, prime factorization of massive numbers is considered extremely difficult for computers. As long as the attacker cannot solve this math puzzle, the message me is not leaked. This type of security is known as Computational Security. Public key cryptography enables secure communication without pre-sharing keys, but its security is "conditional." It assumes the attacker lacks the power to solve a specific mathematical problem. Specifically, RSA depends on the difficulty of prime factorization—a problem that a quantum computer can solve efficiently. Ideally, we want Information-Theoretic Security, but it has been proven that achieving this over open channels is impossible with classical computers. However, quantum mechanics allows us to overcome this limitation.

Quantum Cryptography

Classical protocols are designed for users with conventional computers. Quantum Cryptography, however, assumes users have access to quantum computers. These machines operate on entirely different principles, allowing for information-theoretically secure communication that was previously thought impossible. The core of these quantum protocols is a fundamental law of physics: a quantum state is altered or destroyed by the act of measurement. In quantum computing, data is represented as "quantum states" rather than standard binary strings (0s and 1s). To extract information from a quantum state, one must measure it. However, once measured, the original state is disturbed and cannot be restored. By utilizing this unique property, we can achieve truly secure communication.

The most famous application of this is Quantum Key Distribution (QKD) (See figure 2). QKD allows two parties to establish a secure key without sharing one in advance, all while maintaining information-theoretic security. The Sender and Receiver exchange quantum states to build their key. If an attacker tries to intercept them, they must measure the states, which inevitably destroys or changes them. The Sender and Receiver can then detect this interference. Informally, since this "destruction by measurement" is a law of nature, the security does not depend on the attacker's computing power.

Limitations and Certified Deletion

We have seen how quantum computers provide a "Quantum Advantage" in secure communication. Now, we turn to the limitations of quantum cryptography and the concept of Certified Deletion. To understand this, we must look at "functionality" in cryptography. Modern research aims for more than just secure communication: it seeks advanced "functionalities." A key example is Bit Commitment. This protocol ensures a message remains secret while also "binding" the Sender to it. Specifically, the Sender sends an encrypted "commitment" Com(M). The Receiver cannot see the message yet, but the Sender can later prove that the commitment corresponds exactly to that message without being able to change it.

With classical computers, it is impossible to achieve information theoretic security for bit commitment. Thus, we cannot rule out the possibility that future technology might leak the information in Com(M). Unfortunately, even with quantum computers, information-theoretic security for bit commitment remains impossible. This suggests a fundamental struggle: we cannot easily have both long-term security and high functionality.

To bridge this gap, the concept of Certified Deletion was recently proposed. It occupies a middle ground between computational and information-theoretic security. Certified Deletion allows a user to verify that encrypted data has been truly deleted. Once deletion is certified, the information is guaranteed to remain secret forever.

Using bit commitment as an example (See Figure 3.): the Sender encrypts a message M such that it requires a specific quantum state ) to be read, and generate Com(M). The Receiver holds the commitment Com(M). To "delete" the data, the Receiver is asked to measure (4). Based on the measurement result, the Sender can verify if the measurement was done correctly. Because measurement destroys the quantum state (4) permanently, and since (4) is necessary to recover M, the message becomes impossible to extract ever again.

While we used bit commitment as an example, many other high-functionality protocols face similar security challenges. Even in the quantum era, information-theoretic security is not always possible. Consequently, the development of protocols that balance advanced functionality with long-term security—like those using Certified Deletion—is currently an active and vital field of research.

Bibliography

[1] S.J. Wiesner, "Conjugate Coding", SIGACT News 15:1 (1983) 78-88.

[2] R.L. Rivest, A. Shamir, and L. Adleman "A method for obtaining digital signatures and public-key cryptosystems", Communications of the ACM, Volume 21, Issue 2, (1978) 120-126.

[3] C. Bennett and G. Brassard, "Quantum cryptography: Public key distribution and coin tossing" in Proc. IEE ICCSSP vol.1 (1984) 175-179.

[4] T. Hiroka, T. Morimae, R. Nishimaki, and T. Yamakawa. Certified everlasting zero-knowledge proof for QMA. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, (2022) 434-456.