Quantum-Safe Cryptography: What, Why, and for Whom?

Thiparat Chotibut
Sep 12, 2019 · 6 min read

written by Poompong Chaiwongkhot, a PhD candidate at the Intstitute for Quantum Computing, University of Waterloo, Canada & QTFT.
edited by Dr. Thiparat Chotibut, Chulalongkorn University & QTFT.

Authors’ note: It is highly recommended for uninitiated readers on Cryptography to check out this article before continuing.

Image for post
Image for post
“It is a sad truth that we usually do not discuss the nature of cryptography and its limitation until it is broken…” [image source]

One of the major challenges multinational corporations and governments is facing is the assurance of secure data transmission across communication networks. In most cases, secure data transmission protocols require encryption of data or messages using a key, which is a secret bit string only known to the sender and the intended receivers. This key transforms the original messages into incomprehensible texts, known as ciphertext, so that any malicious eavesdroppers who spy on the ciphertext can not comprehend the messages without a key. At the other end of the communication channel, the transmitted ciphertext is decrypted by the receiver’s key such that the original messages can be recovered. (If you are confused here, please consult this introductory article on cryptography before proceeding!)

The security of today’s cryptography protocols often relies on “presumably” hard-to-solve mathematical problems. For instance, the ubiquitous public key encryption protocol known as RSA [1] utilizes the multiplication of two large prime numbers in order to exchange the secret key between two parties. The security of this protocol which prevents fast decryption is based on the assumption that it is incredibly difficult (for today’s computer to solve using the best known algorithm within the lifetime of the encrypted message) to find the two large prime numbers (factorization) given the multiplication result.

However, security protocols that rely on the asymmetry between encryption (easy and fast) and decryption (difficult and slow) may fail if solutions to relevant mathematical problems arise, either via a faster decryption algorithm or via new technologies and tools that offer new ways to solve problems.

An emerging quantum technology that can potentially solve many hard mathematical problems is a scalable quantum computer. It is theoretically shown by Peter Shor about two decades ago that, if a scalable quantum computer can be built, it can crack the factorization problem exponentially faster than today’s best classical computer [2]. This is a warning to our current cryptographic systems. To ensure secure transmission protocols in the quantum era, we need to start thinking about Quantum-safe Cryptography.

This article aims to provide a basic overview of the topic by attempting to answer the following questions; what is Quantum–Safe Cryptography, why do we need them, and who will benefit from this technology? The technical details of Quantum cryptographic protocols will follow in future articles.

What is Quantum-Safe Cryptography?

Quantum-safe Cryptography is an umbrella term for the studies of cryptographic tools that are safe against quantum computers and quantum algorithms. There are two main directions for this security paradigm:

Post-Quantum Cryptography (PQC): PQC focuses on finding new mathematical problems that are also hard-to-solve by quantum computers.

Quantum Cryptography: This field focuses on cryptography with provable security, based on physical properties and rules of quantum mechanics. One of the most well-studied topics in this field is Quantum Key Distribution (QKD), which focuses on secure generation and distribution of symmetric secret key exploiting quantum mechanical rules.

Why do we need it, and who will benefit from it?

Undoubtedly, unconditionally secure communication would benefit everyone. To build such a utopia where malignant eavesdroppers can not thrive, it is important for us all to be aware of the capabilities and the limitations of each cryptographic tools.

Today, Post Quantum Cryptography (PQC) can be implemented with existing infrastructure. However, PQC is suitable for a short-term security. This is because better (quantum) algorithm or other tools to solve mathematical problems proposed by PQC can emerge anytime, thus we must consider this as a risk. Nevertheless, PQC can help improve our security while the new infrastructure for a long-term security is being deployed. In the future, PQC can be used on a problem with short-lived secrecy, such as authentication problem.

Quantum Cryptography, on the other hand, promises information theoretic security; i.e., the security against an adversary who could intercept, temper, and analyze information transmitted during the key exchange by any means allowed by the laws of physics. This high level of security is achievable thanks to two peculiar phenomena of the quantum world.

First, the uncertainty principle. Any eavesdropping attempt to gather the information of the quantum state during the key exchange would alter the quantum state itself. Therefore, any trace of an eavesdropper will be detectable by the legitimate parties. We will discuss why this follows from the uncertainty principle in the followed-up articles.

Second, no-cloning theorem, which states that a quantum state cannot be reliably duplicated. This implies that if the adversary does not actively measure information about the quantum state (or does not have the technology to do so) during the key exchange, the information about the quantum state can neither be recorded nor kept to be analyzed in the future (when the new technology is capable). This so-called “forward security” is a major advantage of Quantum Cryptography over the classical counterpart, where the electric signal can be tapped into and recorded to be analyzed later. We will also discuss why this follows from no-cloning theorem in the followed-up articles.

Image for post
Image for post
A sketch of BB84 Quantum cryptographic protocol that exploits no-cloning theorem to heighten communication security. [image source]

The long-term security from Quantum Cryptography would help secure highly sensitive data, such as industrial record in a corporation, transaction record in a bank, health record in a hospital, personal information in civil services record, and the list goes on… However, this high level of security does not come without cost; the implementation of these systems requires a long-term plan and a relatively higher cost of upgrading and/or retooling existing infrastructures.

As mentioned earlier, different approaches and protocols provides different advantages and disadvantages. We must adopt each cryptographic tools for the right task.

Similar to the chain strength that is dictated by its weakest link, information security is also dictated by the weakest component in the system. As we heighten the level of security in the hardwares and the protocols, we users, as a part of the information security ecosystem, must also adapt not to become the weakest link…

How do we prepare ourselves?

As online communication changes from convenience to necessity, user’s behaviors must also adapt accordingly. The following are some common practices we can adopt to improve our information security and prepare ourselves for the quantum information age. Most of these practices can start from today:

  • To solve any problem without long term side effects is to study, and identify problems thoroughly and apply the available tools appropriately. The same applies to the information security problem.
  • Expose yourselves to the concept of cryptography and computation, including quantum computing and quantum cryptography.
  • Not everyone needs to be information security experts or quantum physicist. However, everyone should at least understand basic concept, capability, and limitations of each tool being used. This would at least prevent them from falling a victim of fake news or false advertisements.
  • Information security is a long-term issue that requires a long-term plan. Governments, industries, and academics should join force to develop and deploy the security system, as well as to make crucial information available to the public.
  • Service providers should take responsibility and update/upgrade their system to ensure the security of information entrusted to you by the users. The same goes for all civil service entities, who hold sensitive civil information.
  • Legal entities should revise and update their legal documents to take into account new security developments, as well as provide standardization and proper usages of information security protocols.
  • Users should learn the importance of information privacy, and properly take care of their own sensitive information. To show that “we care” has a huge impact on the previous two bullet points.

Perhaps, start with setting sufficiently secure passwords and update them regularly :)

Image for post
Image for post
[image source]

References

[1] R. L. Rivest, A. Shamir, and L. Adleman, Commun. ACM 21, 120 (1978).
[2] P. W. Shor, SIAM J. Comput. 26, 1484 (1997).

QTFT

Quantum Technology Foundation (Thailand)

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store