Post-Quantum Cryptography

What is Post-Quantum Cryptography (PQC)?

Post-quantum cryptography (PQC), also known as quantum-resistant cryptography (QRC), refers to algorithms and cryptosystems believed to be resistant to both classical and quantum computation. Though symmetric cryptographic primitives such as AES fall into this category, the term PQC usually refers specifically to public-key algorithms meant to replace current public-key algorithms such as Rivest-Shamir-Adelman (RSA), Diffie-Hellman (DH) key exchange, and Elliptic Curve Diffie-Hellman (ECDH) key exchange that are vulnerable to a quantum computer of sufficient size. Post-quantum cryptography does not require a quantum computer to run; the algorithms are all implementable on general purpose classical computing devices.

What is a quantum computer? What can it do?

A classical computer uses a “bit” as the fundamental unit of information. A bit can store a value of either a 0 or a 1. By contrast, a quantum computer operates on “qubits,” which can exist in a state that is simultaneously a 0 and a 1. This mind-bending ability is enabled by the principles of quantum mechanics and means that a quantum computer can efficiently solve certain classes of problems that would take a classical computer millions of years. This is referred to as “quantum advantage” or sometimes “quantum supremacy”, and is found in problems such as modeling atoms to develop new materials, solving optimization problems, searching databases, or testing new proteins. In the future, these uses will help advance research and technology. Quantum computers, however, will not surpass classical computing capabilities for all tasks, and indeed, will operate in concert with classical computers. 

Why is Quantum Computing a threat?

Though quantum computers do not surpass classical computers for all tasks, it turns out that quantum computers can efficiently solve the mathematical problems underlying much of the public-key cryptography in use today, including RSA, Diffie-Hellman (DH) key exchange, and Elliptic Curve Diffie-Hellman (ECDH) key exchange. Discovered in 1994 by Peter Shor, “Shor’s algorithm” is the quantum algorithm that poses an existential threat to these public-key cryptography schemes. Though it would take a modern supercomputer millions of years to crack an RSA key of sufficient size, it would only take a quantum computer with around 4,000 qubits a few hours. On “Q-Day,” the day when such a “cryptographically relevant quantum computer” can use Shor’s algorithm to crack RSA, DH, or ECDH, bad actors will be able to decrypt most of the encrypted data sent across computer networks, including national security secrets, financial transactions, and health records. 

What is the quantum timeline?

As of early 2024, publicly available data indicates quantum computers capable of breaking public-key cryptography in widespread use today do not exist. That being said, due to the geopolitically strategic promise of quantum computers, there is significant government investment in quantum research programs, and it is unlikely that the public will be made aware of government-led breakthroughs in quantum computing. To date, the largest quantum computers are claimed to have around 1000 qubits. Even just two years ago, however, the largest quantum computer was around 100 qubits, a mere fraction of today’s number. The pace of development has only accelerated in recent years, with many industry experts now predicting that Q-Day could be in the next 5-10 years. Concretely, this timeline means that powerful quantum computers will likely be able to break today’s encryption methods in the next decade. 

What are SNDL attacks?

Though Q-Day is potentially still a decade away, this timeline does not mean data is necessarily safe from quantum computers, even today. There is an increasing prevalence of “Store Now, Decrypt Later” (SNDL) attacks, where hackers or foreign nation-states steal encrypted data without being able to decrypt it. They plan to store the data until quantum computers are available and powerful enough to decrypt it. This is a serious threat because most data has a lifetime of more than ten years. For example, information such as national security secrets, bank records, or health information needs to be kept private for the next 30 or more years. SNDL attacks will allow hackers to see today’s data decrypted in the next decade, and these attacks are going on every day. Luckily, once data is protected by quantum-resistant encryption, it is no longer vulnerable to SNDL attacks, as hackers with quantum computers will still be unable to decrypt it. 

What is the government doing on this? – is there regulatory oversight on this?

The U.S. government recognizes the serious threat quantum computing poses. In 2022, the White House published a National Security Memorandum which requires federal agencies to start switching to quantum-secure cryptography. Additionally, there is bipartisan support for action in Congress. The Endless Frontiers Act, which includes $100 billion in federal funding, supports quantum computing and post-quantum encryption efforts. In December of 2022, the equally bipartisan Quantum Computing Cybersecurity Preparedness Act was passed into law and lays a plan to mitigate the quantum threat. NIST has also recently completed a six-year search for algorithms to use as the standard for post-quantum cryptography (PQC). These will replace current cryptography algorithms, such as RSA. The search gives guidance towards future cybersecurity efforts, which will have to comply with NIST’s standards. All four potential algorithms are compatible with QuProtect, QuSecure’s quantum security solution. 

How do we know NIST’s algorithms work if we can’t go at them with quantum computers? What is the long-term prognosis of current Post-Quantum Cryptography algorithms / Will the upgrade process be cyclical?

Though we don’t have quantum computers capable of breaking modern cryptography as of early 2024, this limitation does not prevent researchers from deducing if new or existing quantum algorithms (e.g., Shor’s algorithm) can break the proposed cryptographic schemes. This process is known as “quantum cryptanalysis” and is a vital component of the NIST Post-Quantum Cryptography selection process. Quantum computing, however, is a relatively young field, meaning that there are likely many quantum algorithms yet to be discovered.

More broadly, new cryptanalysis, side channel attacks, and software bugs have prompted PQC submission teams to respond with algorithm tweaks, larger key sizes, and software patches. In several dramatic cases, researchers completely broke a candidate algorithm. To react to this shifting landscape, any PQC solution must be able to rapidly restore secure communications by supporting the ability to swap out a vulnerable algorithm, increase key sizes, or patch vulnerable implementations. If vulnerabilities are found in the new PQC standards, all IT systems will need to migrate again to a different set of cryptographic algorithms. QuSecure recognizes this reality. QuProtect is designed to support cryptographic agility (also known as crypto-agility), permitting a network or security operator to easily swap out a vulnerable algorithm without disruption to their networks. QuProtect can thus easily leave behind obsolete algorithms and embrace new, better solutions.

Do I need a quantum computer to protect myself?

No, quantum computers or specialized hardware devices are not needed to protect your data from the threat of quantum computers. Post-quantum cryptography can run on any general purpose (classical) computing platform. As such, QuProtect has zero dependencies on quantum computers to operate. All the necessary technology is available today and integrates with existing networks and IT infrastructure. 

Why should I try out QuSecure’s solution?

Without quantum-resilient encryption, organizations are vulnerable to SNDL attacks now, and potentially catastrophic data breaches in the future. This puts heavy impetus on organizations to solve their quantum-security vulnerabilities. QuSecure offers by far the easiest and most comprehensive quantum security solution on the market, with a variety of selling points. QuProtect is orchestrated, lightweight, and backwards-compatible, allowing our single solution to fit the needs of any client. It is also crypto-agile, which allows QuProtect to use whichever encryption algorithm is the best in any given situation. Lastly, QuProtect is proven, having been chosen as the U.S. government’s default PQC provider. As a trusted, non-invasive, flexible solution, QuSecure is the easy button for quantum security.

AES is immune from quantum attacks; why do I need you?

AES is what is known as a “symmetric” cryptographic primitive used primarily for encrypting data between two entities. Experts do not believe quantum computers pose a major threat to symmetric primitives such as block ciphers (e.g., AES) or hash algorithms (e.g., SHA). However, to use AES to secure data transmissions, the two communicating entities must first establish a shared, secret key in a secure manner; this the “key distribution” problem. Most secure channel protocols such as TLS and IPsec use public-key (aka “asymmetric”) cryptographic primitives such as Diffie-Hellman (DH) key exchange and Elliptic Curve Diffie-Hellman (ECDH) key exchange to establish this AES key. It is this initial asymmetric key exchange that is most vulnerable to quantum attack by Shor’s algorithm. In summary, though AES may be secure from quantum attack, the broader protocol or system is vulnerable to quantum attack if the AES keys cannot be established in a quantum-resistant manner. 

The bottom line is that AES is quantum-resistant, but the method that enables us to use AES securely is quantum-vulnerable.