Quantum Computing — Will it be the game changer?

Few years back, Blockchain was the in-thing. It was at the beginning of the hype cycle and there was no problem in the world, real or imagined, that was not solvable with blockchain. Then, starting 2019, the reality started to hit and exuberance gave way to a more realistic examination of the technology. The Gartner Hype Cycle for Blockchain 2020 shows how these technologies are reaching the Trough of Disillusionment now.

The Deloitte Blockchain Trends for 2020 notes “ faith in Blockchain has fallen victim to the massive hype and irrational exuberance in the past, driven largely over a Bitcoin buying frenzy.” It further notes “ In the wake of the hype, a tendency toward Blockchain tourism developed — where we would see intrigued companies come to gawk at the technology, kick it around for a few weeks before deciding they were more comfortable where they currently were.”

This article is not about Blockchain though. It is about Quantum computing and how it has the potential to disrupt the digital life as it exists today. This fear of potential disruption has existed for quite some time now and has been the subject of frenetic research and development. We are on the cusp of history where developments in the next few years will potentially set the direction for global evolution for the next many decades.

In this article I will try and explore if Quantum is just hype or it really is the mega disrupter? Will it fizzle out or will it cause the world the change the way we produce and consume digital content?

In the early nineties, as Internet took its baby steps, the entire network was primarily built on trust and most of the protocols in use such as HTTP, DNS, Telnet, FTP, IRC etc. were plain text. Everyone was expected to play nicely. Mass adoption of encryption in search of confidentiality and integrity led the massive boom allowing digitization of almost everything including business process, government and financial information etc.

Cryptography, itself is not new. It dates back thousands of years when ancient kings would invent methods to hide secret information from prying eyes by manipulating it. Read more about the history of cryptography at Cryptology — History of cryptology | Britannica or the timeline of cryptography at Timeline of cryptography — Wikipedia. But we are interested in modern times. Our timeline of interest lies in 1970’s when the two major streams of digital cryptography were born; symmetric (or private) key cryptography and asymmetric (or public) key cryptography. The DES (Digital Encryption Standard), a symmetric key algorithm was published in 1976, while the RSA algorithm, a public key algorithm, was published in 1977. DES remained the favorite until the turn of century when it was replaced with AES, or Advanced Encryption Standard, while RSA continues to remain the hot favorite even today. It is ubiquitous in every digital transaction that we conduct every day.

Symmetric Key Cryptography

At its core, symmetric encryption consists of two parts; an algorithm and a key. The algorithm is typically public such as the DES and it explains the exact mathematical manipulation data goes through while converting from plain text to cipher text (encryption) and back to plain text (decryption). Remember, the goal is that the sender and receiver can see the plan text whereas everyone and everything in between should see only the unintelligible cipher text.

What makes the cipher text confidential is the key, which is secret and known only to the sender and the receiver. The sender uses the secret key along with the algorithm to convert data into cipher text. The cipher text is then sent across the wire to the receiver, who in turn uses the key and the algorithm to covert the cipher text back to plain text. As the name suggest, a symmetric key algorithm uses the same key on both sides, which means anyone with the key can decrypt the cipher text; and thus the requirement to keep the key secret. Also, the key needs to be pre-shared before exchanging the message and that is the real challenge. If you could share the key secretly, why not the entire message itself using the same channel? This is where asymmetric key encryption comes in.

Asymmetric Key Cryptography

At conceptual level, the encryption and decryption processes are similar to symmetric key cryptography, except that the keys are different for encryption and decryption. These are a pair of keys that are mathematically related to each other such that when data is encrypted by one, it can be decrypted by the other. One of these is called public key and is shared with everyone, while the other is private key that is known only to the owner of that key.

So, when a sender wants to send a confidential message, she can encrypt the message with the receiver’s public key (which is public knowledge). This message can only be decrypted by the receiver’s private key which is known only to the receiver. Thus, even if this message is intercepted during transmission, it cannot be decrypted.

On the other hand, if the sender wanted to prove source or origin (or non-repudiation), the sender will encrypt the message with sender’s private key. Anyone in the world can decrypt the message by decrypting it with sender’s public key and hence verify that the message could have originated only from the sender. A variation of this principle is used widely for digital signatures across the Internet today.

Public key encryption uses a lot of mathematical gymnastic to achieve something magical. This article cannot go into those complexities. If you are interested, I recommend this Wikipedia article RSA (cryptosystem) — Wikipedia.

But there is one concept that must be discussed here since it leads to the next section. As mentioned earlier, the public and private keys are related to each other and operate in pairs. This relation is based on one-way mathematical functions that involves taking two very large prime numbers, multiplying them, and deriving the pair of keys from the product using complex mathematical functions. The security primarily relies on fundamental mathematical principle that multiplying two numbers is easy, but factoring large numbers is extremely difficult. If you make the number extremely large, factoring that number becomes impossible for classical computers. For example, take 7 and 13. Multiplying them gives us 91, which is child’s play. Now suppose we are provided 91 and asked to factor it. It will take much more time. Now imagine doing this with a 20-digit number, or more.

That is the fundamental mathematical concept that drives everything digital from browsing websites to financial transactions and government secrets and much more.

The challenge with public encryption algorithms is that the mathematical complexities involved, and the key sizes make the encryption and decryption considerably slow as compared to symmetric key encryption. Typical key sizes used for AES today is 256 bits whereas the same for RSA is 2048 bits, with 4096 bits gaining popularity.

Modern digital communications are not simple and uses multiple layers of encryption for efficiency, which are fairly transparent to us as users. For example, it uses public key cryptography for exchanging symmetric key called session key, which is then used in symmetric key cryptography to encrypt the actual message. Then there are hashing algorithm to ensure message integrity and key exchange algorithms to generate session keys. For example, a complete cipher suite may look like TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256, that suggests TLS protocol used with Elliptic Curve Diffie Hellman key exchange, RSA public key cryptography, AES 128 bit symmetric key cryptography in GCM mode (there are many) and SHA256 as the hashing algorithm.

Strength of Cryptography

While there are many types of mathematical and side channel attacks on cryptography, direct attacks are still brute force attacks, that involve trying every possible key combination. For example, breaking a 56-bit DES would involve trying out 2⁵⁶ possible combinations. In reality, on average, you would be expected to achieve success within half of the all possible combinations, or 2⁵⁵ combinations. While that would have been impossible with the compute resources in the 1970’s, it’s become trivial even for modern personal computers who can break a DES encryption within few minutes.

One of the ways to improve encryption strength is by increasing key size. Thus, AES 128 bits was common up to a few years back, but AES 256-bit keys is more common now. Similarly, RSA started with 1024-bit keys, then 2048-bit keys became popular and the world is already moving to 4096-bit keys.

In classical cryptography, this works. Increasing key lengths dramatically increases the computing resources required to brute force the keys. But there is a threat lurking around, and that is Quantum computing.

Quantum Computing

Quantum computing does not rely on the classical binary principles of computing where only two states are possible at any given time; 1 or 0. Rather, quantum works on the principles of physics such as superposition and entanglement such that it can exist in multiple states at any given time. There’s much complex mathematical principles involved but suffice to say for the purposes of this article that one of the features of quantum computing that has huge ramifications for anything digital is that they are really good at certain computational problems such as integer factorization.

Remember, as discussed above, strength of classical encryption mechanisms and all solutions built upon it, such as blockchain and bitcoin, relies on the difficulty of classical computers to undertake integer factorization. With quantum computers, that is under threat. Notably, quantum computers are believed to be able to quickly solve certain problems that no classical computer could solve in any feasible amount of time-a feat known as “ quantum supremacy.” Irrespective of few disputed claims of quantum supremacy in the recent past, what is sure that we will see quantum supremacy in near future. And when that happens, the entire digital eco-system will be under threat.

The classic encryption methods, especially those that rely on near impossible mathematical problems, are at risk of being broken trivially by Quantum computers designed for that purpose. It is estimated that Quantum computers of 4000 Qubits would be able to achieve that. Some organizations, including Google have already claimed ‘Quantum supremacy’ (although disputed) and development in this area is progressing fast.

The latest quantum computer from IBM boasts of 53 qubits of computation power. They also have a published roadmap targeting 1000 Qubits by 2023.

Development in this area is progressing feverishly. Imagine, if private industry has reached this far, where might nation states be?

As recent as January 2021, China claimed to have achieved “quantum supremacy” with the development of its Jiuzhang quantum computer, which surpassed Google’s Sycamore quantum device with its ability to calculate 100 trillion times faster than the fastest classical supercomputer. A Wired article puts this at 76 peak Qubits. Beijing announced it had also built the world’s first fully integrated quantum network.

The pace of growth in quantum is fast; really fast. In fact, just like the Moore’s theorem which predicted doubling of processing power every 2 years or so, there’s now a Neven’s law for quantum computing which postulates that “quantum computers are gaining computational power relative to classical ones at a “doubly exponential” rate — a staggeringly fast clip”.

Doomsday is not here yet, but it is not very far off either. Maybe a decade away.

Just imagine, everything ever encrypted with classical encryption, can be trivially decrypted. All the world’s secrets out in the open. Is the situation that bad? Let us examine.

How Quantum Computing affect Classical Encryption

As stated above, many encryption techniques rely on the factorization problem to ensure security and brute forcing keys, on an average, takes half the number of possible combinations to decrypt. So, a 128 bit key would, on an average, take 2¹²⁷ attempts. That is a lot and the problem can be further compounded simply by increasing the key size. Quantum changes the paradigm.

There are two mathematical algorithms of interest here. Shor’s algorithm and Grover’s algorithm. Shor algorithm is designed to solve the prime factorization problem which is the foundation of asymmetric key cryptography. As and when a true quantum computer is built that utilizes Shor algorithm, asymmetric key cryptography will be under real threat and make it trivial to find the private key associated with a given public key.

Grover algorithm, on the other hand is designed to solve the search problem, useful in breaking hashing and symmetric key cryptography, which are another widely used mechanism for ensuring data integrity and confidentiality. However, it is probabilistic in nature (not exact solutions) and only provides a square root speedup. This means that it will still take 2⁵⁶ attempts at decrypting a cipher text, which is way smaller than the 2¹²⁷ attempts with classical computer. Also, as seen while describing DES above, brute forcing 2⁵⁶ combinations is quite achievable even by today’s standards. However, solving the hash problem and breaking symmetric key cryptography will still be difficult and can easily be overcome by increasing the hash or key length. This is the probable reason why NSA mandates use of AES 256 for protecting SECRET and above, since it is quantum resistant. More on this later.

So, what is the world doing to counter this threat?

The requirement to develop Quantum resistant cryptography has been realized and many efforts are underway to discover the next global standard. But it is not easy. Developing an algorithm that satisfies all the requirements and be resistant to cryptanalysis is not trivial. It takes many years to develop, test, publish and build an entire eco-system around it. Imagine every product, all the hardware and software produced in the world, needing to natively support the new algorithm. That takes decades. Do we have the time left?

The current global standards, RSA and AES, have been around for decades. Thousands of mathematicians, researchers and academicians have tried to find flaws over the years and continue to do so, but these have proved to be resilient to cryptanalysis so far, at least publicly. If not for the threat of quantum computers, they may remain the default cryptography choice for many more decades. The new standard(s) will also have to protect us for many decades.

It’s a race between the development in quantum computing and development of quantum resistant cryptography.

In fact, efforts are already underway. NIST has been working on discovering post quantum cryptography since 2016. From the initial 82 post quantum cryptography proposals, they are down to 7 shortlisted candidates and 8 alternates over three rounds of evaluation. They expect to release the draft standard by 2024. So, by the time the threat from Quantum computers become clear and present, the world will probably have a solution. There will still be a massive problem of re-encrypting massive volumes of existing stored and confidential data with post quantum algorithms and that’s a challenge at another level to be still looked at.

The trigger for this article was the below quote from NSA, extracted from their “ NSA Cybersecurity Year in Review “

“More significantly, NSA has now embarked upon a broad effort to modernize the Department’s cryptography to make it resistant to exploitation by a quantum computer. Such a computer is still theoretical, but its development could render large swaths of the U.S. cryptographic inventory obsolete. Thus, the DoD and the Intelligence Community (IC) are relying heavily on NSA, with substantial fiscal investments to field next-generation encryption. To this end, NSA has approved a new suite of quantum-resistant cryptographic algorithms for use in National Security Systems that address a range of potential threats for future use in equipment supporting the warfighter.”

This shows that Quantum resistant cryptographic algorithms exists today, at least in some form. NSA’s public recommendations can be found at Commercial National Security Algorithm Suite (nsa.gov). NSA is also closely following the post quantum algorithm search at NIST and have given their recommendations at NSA’s Cybersecurity Perspective on Post-Quantum Cryptography Algorithms, preferring lattice based encryption.

The world is not likely to see post quantum cryptography anytime soon, but on the other hand, even Quantum computers will take some finite time to break encryption and with the world moving gradually towards more temporal keys, the greater risks will be faced only by those who need long term encryption for data storage and confidentiality such as militaries, governments, financial institutions etc.

The Next Steps

Do enterprises have anything to be alarmed about? Should they be doing anything now, or in the near future?

There is no cause to be alarmist yet due to Quantum computing and its adverse effect on asymmetric cryptography. Realization of Shor and Grover algorithms in practical computers are some years away. Even then, we have to consider their effect on data in motion and data at rest. Data at rest is typically encrypted using symmetric keys and they are relatively safe. Those keys are however, protected by layered encryption involving asymmetric cryptography which is vulnerable to quantum computers. Data in motion uses asymmetric key mostly for sharing sessions keys that are symmetric key and the session keys are short lived. By the time quantum computers achieve near real time crypto breaking capabilities, the world would have, hopefully, found mitigating solutions. Even when cryptography breaking quantum computers become available, these will most likely be with nation states who would possibly want to target other nation states. So, unless your enterprise holds critical information that may be targeted by nation state, there is no reason to worry, at least a decade.

What enterprises can do in the next few years is to start preparing for the post quantum world. They can mandate use of stronger symmetric and hashing algorithms such as those recommended by NSA like AES 256, SHA 384 or better, RSA 3072 bits or better etc. and discontinue use of weaker algorithms such as DES, AES128, SHA, MD5 etc., especially in legacy systems. Discontinuing weaker algorithms may not be easy since many legacy systems may not even support modern encryption or may continue to use insecure encryption by default. Enterprises would be well advised to identify and reconfigure devices and systems (that support it) to use quantum resistant cryptography only. They may also plan to progressively phase out of legacy systems that do not support quantum resistant cryptography.

Conclusion

Future will be interesting; that is a given. The entire digital world will look very different in the next decade or so. Solutions built on classical encryption like crypto currencies, digital ledgers, public and private blockchains etc. will be under severe risk. Data primacy, data privacy and data governance will occupy a much larger share of our time and effort, with many enterprises experiencing major re-engineering of their digital infrastructure.

Or, maybe, the transformation will be seamless. Pieces may fall into place at right times and the digital world may transition to post quantum world without any disruption.

Which of the two scenarios play out will depend upon whether the quantum computers reach the inflexion point of 4000 qubits before ubiquitous adoption of quantum resistant and quantum safe algorithms not only for future data sets but also for the historical ones.

Let the race begin!

Originally published at https://www.linkedin.com.