The Quantum Frontier: NTT's Quest for Unbreakable Cryptography

Quantum computers take advantage of the principles of quantum mechanics to perform calculations at speeds unattainable by classical computers for specific problems. They have the potential to revolutionize a number of fields, including material science and medicine. For example, quantum computers are able to efficiently simulate molecular structures for drug discovery and optimize complex systems in logistics and finance.

The power of quantum computers also brings potential problems, however. Although they are not inherently dangerous, their potential computational capabilities pose genuine challenges to current cryptographic systems. One way in which quantum computers could affect security is by breaking public-key cryptography. The RSA algorithm, which is widely used for securing online transactions, emails, and more, is a public-key cryptographic algorithm introduced in 1978, which has become one of the most widely used encryption and digital signature algorithms. RSA relies on the mathematical properties of prime numbers and their difficulty to factor when it comes to large composite numbers. The security of RSA is primarily based on the computational difficulty of factoring large composite numbers into their prime components, a problem for which no efficient solution currently exists for classical computers.

However, Shor's factorization algorithm, developed in 1994, predicted that the RSA cipher could be broken by quantum computers, which can solve problems exponentially faster than the best-known algorithms running on classical computers. For this reason, research has taken place in recent years on whether it might be possible to develop computer cryptography that cannot be deciphered—even by quantum computers.

Thanks to NTT, a solution may be in sight.

NTT has succeeded in creating a world-first commitment that balances high quantum-resistant security and communication efficiency just through one-way functions—the technology that makes it possible to construct safe and efficient cryptographic protocols against attackers with quantum computers. A commitment scheme in computer security is a cryptographic element that allows one party (the sender) to "commit" to a certain value while keeping it hidden from another party (the receiver), then reveal the committed value later. Once the sender has committed to a value, they cannot change it without the receiver knowing. This ensures that the sender cannot cheat by changing their mind after the fact. Meanwhile, the receiver cannot know the committed value until the sender chooses to reveal it. This ensures that the sender's choice remains confidential until they are ready to disclose it. Think of a sealed bid in an auction: you put your bid in an envelope and seal it (commit); once all bids are collected, all envelopes are then opened (reveal). If the scheme is secure, you cannot change your bid once the envelope is sealed (binding), and no one can see your bid until all envelopes are opened (hiding).

NTT’s Distinguished Researcher Takashi Yamakawa, in collaboration with Dr. Xiao Liang of NTT Research Cryptography & Information Security Lab and Associate Professor Omkant Pandey of Stony Brook University, has developed a new solution to ensure secure communications even when faced with the challenge of quantum computers. Their solution has two key features:

1. Quantum Computer Resistance (Non-malleability): The solution is designed to protect against tampering by quantum computers. This means that once a user sends a message, another user cannot modify it to send a different, related message. This is called non-malleability, and it ensures that messages remain unchanged from what the original sender intended.

2. Efficient Communication (Constant-roundness): The second feature is about maintaining a consistent level of communication efficiency, regardless of how secure you want the communication to be. In technical terms, this is known as "constant-roundness." It means that the number of back-and-forth communications (or rounds) between the sender and receiver stays the same, no matter how high the security level is set.

NTT achieved these features using the simplest possible approach, relying on what are known as one-way functions. These are mathematical functions that are easy to compute in one direction but very difficult to reverse, making them ideal for secure communication systems.

When it comes to designing safety for classical computers, commitment schemes have been known since 2011; however, achieving similar solutions for quantum computers has been an impossibility until now, because quantum computers operate on different principles from classical computers and traditional safety proofs for attackers using classical computers cannot be applied to attackers using quantum computers.

Professor Yamakawa and his colleagues have redesigned the commitment scheme in a completely different way and have achieved secure commitment with non-malleability.

NTT’s research is expected to lead to the development of a more secure and efficient secure computation protocol for quantum computers in the future. Designing commitment schemes is only the beginning—in the future, NTT intends to apply its method to other cryptographic protocols such as secure computing protocols and aim to improve quantum security resistance. Eventually, NTT aims to develop quantum-resistant security through the application of its research to other cryptographic protocols such as secret computation protocols and zero-knowledge proofs.

NTT—Innovating the Future of Online Security