Skip to main content

Cryptography, Quantum Computing, and Paths Forward

February 7, 2018

Author:

Eleanor Mount

Cryptography is a fundamental building block in the security of many systems integral to the modern web. It protects online communications, secures websites, ensures safe transactions between parties, and verifies identities online. Cryptography is used in everything from cell phones, email, e-commerce, to banking information and sensitive national security information.

RSA encryption is the common algorithm that ensures confidentiality, authenticity, and integrity in online communications and transactions (the RSA stands for Rivest–Shamir–Adleman, the names of the men who first described it). Thus far, there have been no known attacks on RSA encryption. In 1994, researchers theorized how one might execute an attack, but there was no computer with sufficient computing power to do it.

However, recent developments in quantum computing have changed the long-term security profile for RSA encryption and concern is growing that the encryption crucial to everyday operations online will no longer be safe. For instance, a group of physicists at the University of California, Santa Barbara together with Google published a paper in October 2017 demonstrating a proof of principle for how “quantum supremacy” could be achieved. Quantum supremacy is the ability of quantum machines to outperform classical computers—and this has long been the goal of a supposed future quantum computer that could outperform all of the world’s most powerful supercomputers combined.

The dawn of quantum computing means that there will also be a need for “post-quantum cryptography.” Post-quantum cryptography refers to algorithms that are thought to be secure against attacks from quantum computers. A quick survey of online information regarding post-quantum cryptography may feel like going on WebMD when someone has the sniffles: she might start the search thinking she may have a mild cold, but leave convinced she has a diagnosis for a fatal disorder and feeling a helpless, imminent doom about the future. A panicked rhetoric surrounds many conversations regarding post-quantum cryptography. This leads to one question: Are we all doomed?

In order to answer the question of whether we are all doomed, it is helpful to provide background information on quantum computing, current encryption, and proposed future encryption systems. Understanding how recent developments in these two fields interact with one another helps to answer the question about the seemingly imminent day everything is vulnerable.

Understanding Encryption

In classical computing, a bit is the smallest unit that of data that holds a single piece of information. A bit can exist in only one of two states: either 0 or 1. Quantum computers use qubits.” Qubits have many similarities to bits, but one of their distinct differences is qubits can exist in a state of 0 and 1 simultaneously. Additionally, multiple qubits exhibit a process known as quantum entanglement, where groups of particles interact so the state of each particle cannot be described independently of the others. This allows multiple states to be acted on simultaneously. In practice, this means while traditional computers may have to cycle through possible solutions one at a time to find an answer, a quantum computer can try many possible solutions at once, finding an answer quickly.

In general, encryption makes a document invisible to anyone that does not possess the correct encryption key. Encryption can be as simple as basic substitution ciphers (such as replacing letters of the alphabet with a number), but advances in technology have made these forms largely obsolete. Cryptography now encodes data with complex processes in order to maintain secrecy. Today, encryption uses complex algorithms to mix characters of a message with other characters or values, resulting in an electronic file that is unreadable to anyone without the password or encryption key (Edgett 2003, 365).

Much of the world’s digital information is protected by public-key cryptography. Public key cryptography utilizes a public key, which is universally known, and a private key, which is needed to unlock the document encoded with a public key. Public-key is also known as “asymmetric encryption” because while both parties exchanging a message have the public key, an individual’s private key is kept secret. An example is helpful to understand how this operates in practice.

Model_of_how_encryption_works

In the diagram above, Bob sends a message to Sally in unencrypted form. Bob encrypts the message with Sally’s public key. When Sally receives the encrypted message, Sally uses their private key to decode it. Sally can then read the message from Bob in plain, unencrypted text.

This system is simple, but remains secure because the only method of breaking the security is for either party to give away their private key.

As mentioned, RSA encryption is currently the most common form of public key cryptography. In RSA, the public key is a product of two large prime numbers. The private key is the factors of this large integer (Rouse). Encryption strength is directly related to the key size: RSA keys are 1024 or 2048 bits long. These keys are sufficient in length to be secure, but short enough to work quickly. RSA’s security is based on the difficulty of factoring large integers that are the product of two prime numbers. Multiplying the numbers to create the public key can be done quickly, but determining the factors of a large number is so difficult it is infeasible, even for supercomputers. RSA encryption is used widely for sharing sensitive information over the Internet.

The difficulty associated with finding two prime factors of a large integer is a valid assumption in classical computing, but quantum computing fundamentally changes this assumption. In 1994, the mathematician Peter Shor published an algorithm that runs on quantum computers for integer factorization. As it is now known, “Shor’s algorithm” factors in polynomial time, which speeds up the process of finding factors and makes it feasible to break RSA cryptography (Bernstein 2009, 3). Shor’s algorithm has been a powerful motivator for the design, construction, testing and research on developing new quantum-resistant cryptography (Kobie).

Simply building a computer that could find the prime factors of a large number has the potential to break not only the encryption that is a standard part of online communication and transactions, but to break the encryption protecting sensitive national security information. How this will impact security depends on a web of complex factors — including when a computer is created, if quantum-resistant algorithms are implemented before this, and what actor obtains the computer and how they plan to use it.

The Coming Storm: Quantum Computers

Cryptographers are concerned a quantum computer is coming more quickly than current infrastructure is prepared for and, therefore, keys have the potential to be broken. A quantum computer capable of running Shor’s algorithm would have to have “hundreds or thousands of qubits,” but given rapid developments in technology, this computer is no longer just a theoretical possibility, it is feasible in the near future (Greenberg).

In 2012, IBM estimated a sufficient quantum computer was “maybe 10 years off or 15 years off” (“IBM’s Stunning Breakthrough: Quantum Computing finally ‘within reach.’”). In March 2017, IBM announced a 16-qubit quantum computer that is freely accessible to developers, programmers, and researchers to run quantum algorithms at no cost via the IBM cloud. Additionally, IBM announced a 17-qubit prototype commercial processor. This processor is the basis for IBM Q early-access commercial systems, and IBM hopes to scale this model to 50 or more qubits in the “next few years to demonstrate capabilities beyond today’s classical systems” (“IBM’s Most Powerful Universal Quantum Computing Processors.”). Quantum test chips with around 49 qubits are enough to possibly achieve quantum supremacy (Hsu). Google aimed to complete a 49-qubit system by the end of 2017, but the company has yet to break ground. Intel became the first company to pass this key milestone when the company announced a superconducting quantum test chip with 49-qubits, named Tangle Lake, during 2018 CES, an annual consumer electronics tradeshow in Las Vegas (Hsu).

Quantum computing technology is growing rapidly, but only recently have scientists started to take action in order to maintain security and privacy against quantum computers. Developing and implementing new encryption algorithms could take much more time than building a quantum computer. In 2016, the National Institute of Standards and Technology (NIST) published a report on the status of research into quantum computers, and a long-term approach for avoiding this vulnerability before it arises. The report shares details about what NIST is doing to mitigate risk in the future and recommends organizations focus on “crypto agility” or the ability to switch out algorithms they are using for newer, safer ones (Chen et. al 2016). Post-quantum cryptography refers to cryptography algorithms that are thought to be secure against quantum computers. NIST also re-opened their open collaboration process with the public to devise and vet cryptographic methods that will be resistant to quantum attacks. They are expecting to have candidates between 2020 and 2022 (“NIST Kicks Off Effort to Defend Encrypted Data from Quantum Computer Threat”). Even after candidates are selected, it takes time to test, standardize, and implement algorithms. With this current timeline, the risk of cryptography being broken appears very real—quantum computing seems to be moving faster than safeguards against it are.

Indications from industry and government further demonstrate quantum computing is now a significant enough threat to warrant taking preventative measures. In August 2015, the National Security Administration Information Assurance Directorate (IAD) made announcements on Post-Quantum Cryptography and its importance. The IAD recognized there would be a move in the “not so distant future” to quantum resistant algorithms and in response, they “have determined to start planning and communicating early about the upcoming transition to quantum resistant algorithms.” The IAD updated their list of “Suite B” cryptographic algorithms to include several quantum resistant algorithms. Suite B is a list of algorithms promulgated by the NSA to serve as an interoperable cryptographic base for both classified and unclassified information. A corresponding set of unpublished algorithms, Suite A, is used in applications where “Suite B may not be appropriate.” In their announcement, the NSA specifically made clear their motivation was due to the future threat of quantum, stating their ultimate goal “is to provide cost effective security against a potential quantum computer.” The announcement went on to recommend partners and vendors that have not yet made the transition to Suite B algorithms to “prepare for the upcoming quantum resistant algorithm transition” (“NSA Plans for a Post-Quantum World.”).

Following the NSA announcements, Google announced in July 2016 it was testing a new form of encryption on a small percentage of Chrome desktop installations. This new form of encryption is designed to resist attacks from quantum computers (“Google’s Post-Quantum Cryptography.”). Adam Langley, a Google security engineer, noted they are testing the supposedly post-quantum cryptography because “the possibility that large quantum computers could be built in the future is not zero. We shouldn’t panic about it, but it could happen” (Greenberg). Additionally, Google is considering sophisticated actors could be stockpiling encrypted cipher text now to break the encryption on in the future with a quantum computer. The TLS or SSL encryption protecting web browsing today could be easily decrypted in the future by a quantum computer (Greenberg).

The back-and-forth between quantum computing and developing new standards has important implications for current debates regarding value trade-offs between privacy and security. These concerns relate to issues in encryption now, but the potential impact is heightened due to the technological capabilities. The implications vary largely depending on who obtains the technology, their intentions, and if their intentions ultimately translate to capabilities.

Paths Forward

Encryption is a vital component of the online world today. In order to understand the risk quantum computing poses to information security, it is necessary to examine developments both in quantum computing and in post-quantum cryptography. Efforts are being made to secure information for the future, but technology is developing more quickly than safeguards against it are. There are numerous technical difficulties to overcome before a quantum computer capable of running Shor’s algorithm can be built, but the risk they pose to information security and privacy is clear.

Unless someone can write up a new crypto-system to protect us all for NIST (if you happen to be this person, your time to shine is now), the reality is there is not much any one person can do to completely protect themselves if quantum computing really does come before a quantum-resistant algorithm. With this in mind, there is certainly no need panic and revert back to hiding all of your documents in a locked briefcase. Some suggestions follow:

Stay informed: A key takeaway from research in this area demonstrates quantum computing and post-quantum cryptography are quickly developing fields. Because all encryption will only be broken if a quantum computer is made before quantum-resistant algorithms are implemented, staying informed on news in both areas will be important in order to best “predict” the future.

Remain “crypto-agile”: Most involved members in the cybersecurity community know one of the golden rules is to update software as soon as patches come out in order to stay updated on vulnerability patches. This will certainly be integral in the future if new cryptography standards are developed. Don’t be victim to the next security breach—stay updated.

Public-private partnerships: Government could work with private companies, such as Google, in order to better monitor developments in quantum computing and to ensure systems of vital national interest are secure.

Continue to support NIST efforts: Everyone should continue to support efforts from NIST to test “quantum-resistant” algorithms in order to improve security and efficiency.

Achieving quantum supremacy, creating a quantum computer, running Shor’s algorithm, and breaking RSA encryption are certainly not easy feats. Cryptography has a history of algorithms being defined and broken, and there is never any guarantee of security. As quantum computing continues to make significant leaps, post-quantum cryptography awaits its Rivest, Shamir, and Adleman (the cryptographers who invented RSA).

Works Cited

Bernstein, Daniel J., Johannes Buchmann, and Erik Dahmen. Post-quantum Cryptography. Berlin: Springer, 2009. Print.

Chen, L., Liu, Y.-K., Jordan, S., Moody, D., Peralta, R., Perlner, R., Smith-Tone, D.: “Report on post-quantum cryptography.” NISTIR 8105, Draft, February 2016.

Edgett, Sean J. Double-Clicking on Fourth Amendment Protection: Encryption Creates a Reasonable Expectation of Privacy, 30 Pepp L. Rev. 2 (2003).

Greenberg, Andy. “Google Tests New Crypto in Chrome to Fend Off Quantum Attacks.” Wired. Conde Nast, 07 July 2016. Web.

Hsu, Jeremy. “CES 2018: Intel’s 49-Qubit Chip Shoots for Quantum Supremacy.” IEEE Spectrum, IEEE, 9 Jan 2018. Web.

“IBM’s Most Powerful Universal Quantum Computing Processors.” IBM News Room. IBM, 17 May 2017. Web.

“IBM’s Stunning Breakthrough: Quantum Computing finally ‘within reach.’” Fox News, FOX News Network, LLC., 28 Feb 2012. Web. 

Kobie, Nicole. “The Quantum Clock Is Ticking on Encryption – and Your Data Is under Threat.” Wired UK. Wired Magazine, 4 Oct. 2016. Web.

“NIST Kicks Off Effort to Defend Encrypted Data from Quantum Computer Threat.” National Institute of Standards and Technology, U.S. Department of Commerce. 28 April 2016. Web.

Rouse, Margaret. “What Is RSA Algorithm (Rivest-Shamir-Adleman)? – Definition from WhatIs.com.” SearchSecurity, TechTarget, Nov. 2014.

Schneier, Bruce. “NSA Plans for a Post-Quantum World.” Lawfare. The Lawfare Institute, 23 Aug. 2015. Web.

Schneier, Bruce. “Google’s Post-Quantum Cryptography.” Blog post. Schneier on Security. Schneier.com, 12 July 2016. Web.

This publication was made possible in part by a grant from Carnegie Corporation of New York. The statements made and views expressed are solely the responsibility of the author.