# What is Post-Quantum Cryptography?

A Fields primer on the key to a more cyber-secure future.

*Did you know that there are over 25,000 vacant cybersecurity jobs across Canada? Cyber Connexion, powered by the Fields Institute, is an intensive cybersecurity upskilling program that gives diverse talent in Canada the skills to quickly transition into high-demand careers at **leading organizations.** Our grads are now top cybersecurity professionals at leading companies like KPMG, Deloitte, IBM, Questrade, eSentire, Scotiabank, CIBC and many more. Visit our website to learn more!*

******

Cryptography is the practice of securing information to prevent third parties from accessing it. You can think of it more simply as creating a code to ensure private messages don’t get read by anyone who shouldn’t be reading them. Like the time you invented a cipher with your friend in Grade 5 so you could pass notes in class without fear of what would happen if the teacher intercepted. No key to the cipher? Your teacher wasn’t going to be reading anything out loud to the class that day.

On a computational scale, cryptography gets far more complex. It requires a thorough understanding of mathematics, specifically algorithms designed around computational hardness assumptions.In other words, how difficult it would be for a computer to decrypt, i.e., “crack the code” of a message without access to a key.

**Let’s take RSA encryption as an example.** This technique uses modular arithmetic to encrypt and decrypt messages.

Here’s how it works:

Bob wants to send a message m to Alice. The message m is encoded as an integer of a fixed size. Alice chooses two large prime numbers – p, q – and multiplies them together to get a number n:= pq. Alice will then choose an encryption key e which is less than n, and has no common factors with n. Alice will also compute a decryption key d, such that for all numbers x between 1 and m, x^(e*d) = x (mod n). Alice publishes the values n and d as her public key. If Bob wants to encrypt a message m to send to Alice, he computes a ciphertext c := m^e (mod n). If Alice wants to access the message, she computes c^d (mod n). Notice that c^d (mod n) = (m^e)^d (mod n) = m^(e*d) (mod n) = m.

The key to computing the decryption exponent d is the ability to factor the number n into its prime factors p, q. Without knowing these prime factors of n, it is considered computationally infeasible to compute the value of d. But, since Alice knows the prime factors of n, it is easy for her to compute the value of d. In principle, the value of d is computable from the knowledge of e and n, but it would take a classical computer thousands of years to do the necessary computations to yield the answer. The security of RSA encryption is derived from the computational difficulty of decrypting for anyone other than Alice, who holds the private key.

Any cybersecurity program worth its weight will have a core cryptography module, that includes techniques like RSA encryption, and graduates should have a firm grasp of these mathematical principles before they enter the workforce. To create secure systems requires a foundational understanding to anticipate new ways bad actors can subvert security protocols.

**Warning: Steep cliff ahead**

Did you follow the logic in that RSA encryption example? That’s good. Unfortunately, things are about to get a lot more complicated: quantum computing threatens to compromise the security of numerous protocols we rely on for the verification of online identity as well as encryption.

Quantum computers are like classical computers in the sense that they are able to perform computations using inputs and outputs of strings of 1s and 0s – or “bits”. Let’s say we’ve got three bits: a, b and c. Each can take on the value of 0 or 1. I want to do a computation using a, b and c whose outcome depends on their values. A classical computer would have to assign every possible value assignment to a, b and c so that every possible value assignment is 2^3.

A quantum computer could, instead, form something called a superposition of states in which each of a, b and c are able to simultaneously hold the values of 0 and 1. With superposition, the machine can perform certain computations on all eight of these states in a single operation. In some situations, this facilitates a significant computational speed-up that can’t be achieved on a classical computer. For example, this quantum advantage allows us to factor numbers very efficiently, which makes it easier to break security protocols like RSA encryption.

To date, this computational ability remains in the hypothetical realm, but the technological gap is closing and we need to be prepared. This means changes have to come to public key cryptography. Specifically, the so-called “hard” problems that provide the foundations of manyonline security measures are no longer hard if you have a quantum computer. Anyone with a public key will be able to compute the private key, which defeats the purpose.

This has prompted a rethinking of the mathematical foundations that we use to ensure everything from secure online payments to transactions on the blockchain. Preparing for this presents a massive logistical challenge for both government and private industry as they prepare to update older cryptographic software and hardware with more secure variants before a quantum attack becomes technologically feasible. The organizations preparing for this inevitability will be far better situated when that day comes.

**How nature inspired the quantum quest**

So how did we get here? Since the 1970s, modern public key cryptography has solved problems related to confidentiality, the integrity of data and the authentication of identity using mathematical schemes called “trapdoor” problems. These are processes that can be performed very efficiently one way, but are extremely difficult to reverse. In every case, the security of the system depends on the difficulty of reversing some process. When a computational trapdoor is tricky enough, it is essentially impossible for someone to break through the encryption without a public key.

**Quantum leap**

By 1985, **David Deutsch** had discovered a rigid formal model of quantum computation, and researchers began developing quantum algorithms which could be implemented on a hypothetical quantum computer.

In 1994, **Peter Shor** at Bell Labs was successful. Shor’s algorithm would be able to perform a large number of classically hard problems very efficiently and set the stage for a potential industrialization of quantum computers in the future. Notably, Shor’s algorithm was able to factor large integers and compute discrete logarithms over both finite fields and elliptic curves in polynomial time. These are exactly the kinds of trapdoor problems that underpin the security of essentially all modern public key cryptosystems. With Shor’s discovery, we had reached an understanding, in principle, that if a quantum computer were to be built, these cryptosystems would instantly collapse, creating a security catastrophe.

By the early 2010s, a few quantum computers started to appear but they were very limited in scope. None of these computers could implement any given quantum algorithm the way a basic laptop can run any software program. Instead, these machines were purpose-built to perform very specific computations.

And so it remains to this day. No one has successfully implemented Shor’s algorithm in a way that could break universal encryption, and the timeline for this scary moment remains unknown. The first actor to successfully achieve this feat would have unprecedented powers of surveillance over the rest of the world. But just because we haven’t seen it happen yet doesn’t mean this surveillance isn’t already underway. And like Y2K, disaster can only be averted if we proactively update all of our systems. If a large organization had reason to believe they could build a quantum computer in the near future, they could already begin intercepting secure communications with the intent to decrypt them down the road when they have the right tools. A government typically classifies documents for about 30 years, after which they figure that information is no longer harmful. That means any government relying on encryption to keep secrets should be asking themselves not whether a quantum computer exists, but whether one could exist in the hands of an adversary within 30 years.

**Ensuring Canada is able to safely keep passing ‘notes’ in class**

Now begins the very difficult task of implementing these new algorithms and integrating them into our electronic infrastructure. Unfortunately, the scope of this task isn’t completely clear, which leaves us vulnerable in the interim. The Canadian Forum for Digital Infrastructure Resilience (CFDIR), a public-private collaborative body dedicated to ensuring the security and resilience of critical digital assets in Canada, has convened a **Quantum Readiness Working Group (QRWG)** to study solutions and strategies to respond to this problem in a timely and effective manner. In July 2021, they published a document outlining best practices and guidelines for organizations looking to migrate to quantum secure infrastructure. To date, nothing more substantive has been distributed, but it’s a start.

The QRWG-recommendations require that Canadian companies and governmental agencies foster internal teams to understand the threats posed by quantum computing, and to catalog IT assets that need to be updated or replaced. As usual, there is a communications problem: Many organizations may not even be aware of the countless ways their IT infrastructure relies on quantum-insecure encryption, and the process of identifying and classifying these assets alone could take years. That’s provided there are even enough skilled professionals to scale that mountain. Canada already faces a substantial talent gap in the cybersecurity industry, with estimates of a labour deficit of 25,000 jobs as of 2022*. This number will likely grow as more Canadian companies begin to develop their quantum migration strategies, which will lead to an explosion of jobs in the post-quantum migration.

Fields sees this as an opportunity for talented young Canadians with the technical capability to understand the intricacies of the quantum threats to cryptography and the technical solutions required to mitigate them. At Cyber Connexion, our curriculum is designed to help prepare for a post-quantum future. We help place our graduates at forward-thinking partner companies, closing the talent gap one expert at a time.

*Aaron Crighton is Cyber Connexion’s Academic Coordinator. He completed his PhD in mathematics at McMaster University.*