Post-Quantum Cryptography (PQC)

What is post-quantum cryptography (PQC)?

Cryptography is critical for securing and authenticating information in nearly every digital technology we use today, from applications and websites to financial transactions. Through protocols and algorithms, traditional cryptography encrypts information that only a unique key can decipher. And it works for solving complex math on traditional computers. As advances in mathematics, cryptanalysis, classical and quantum computing steadily accelerate, threats, too, will keep pace.

Today's encryption techniques largely rely on how long traditional computers take to do complicated mathematical and factorization calculations. Therefore, current algorithms can crack, but not in a reasonable amount of time or compute power (money). The once secure DES encryption standard can now be broken in hours with modern computers. It is estimated that a modern computer would take 300 trillion years to crack an RSA 2048 bit key.

Quantum computing is changing this. While there are debates about whether academic and state-sponsored researchers can break current algorithms, it is indisputable that the reality of more significant threats will be here in the not-too-distant future. A properly equipped quantum computer could potentially break that same RSA 2048-bit key in 10 seconds.

Why does post-quantum cryptography matter now?

You might think this is a future problem because quantum computing is still in its early stages of development and isn't widely accessible or powerful enough to be a serious threat to current encryption technology. But it's a problem we need to start solving now. When every encryption algorithm in use becomes crackable, the basis of all digital trust unfolds. 

But it's not just the encryption of private data. Entities using quantum computing can compromise the authentication and validation of signatures. That means proving digital content hasn't been tampered with isn’t just a problem for things created in the future. It would be necessary to go back and validate historical content quickly, or it will become untrustworthy.

That's significant when you consider how long the communities will take to transition to a new encryption standard. The Mosca theorem provides a framework for thinking about when that transition has to start: 

For the software supply chain:

• X is the lifetime of a long-lived version of a package.

• Y is the time it will take the community to agree on a new signature standard and sign all packages with it.

• Z is the day quantum computers that can break the existing signature algorithms.

If the date when quantum computers might be able to break your algorithm is shorter than how long your package matters, plus how long it takes you to retool to use new PQC, it’s too late. For many digital artifacts, it’s quite likely that the time is now.

Post-quantum cryptography (PQC) is being presented as an option to secure sensitive data against bad actors using quantum computers. The advantage of PQC is to re-introduce complexity so that even quantum computers can’t immediately crack the algorithm. (Basically, making Z in our equation above very far in the future, again) This provides longer-term security options for the public and private sectors alike.

How does PQC affect software supply chains?

PQC will have a huge impact on software supply chains. Organizations will be forced to upgrade their encryption methods to post-quantum algorithms, requiring significant changes to existing software, infrastructure, and developer training as quantum computing becomes a reality.

A new level of scrutiny for components containing traditional cryptographic algorithms will be necessary. Depending on the organization's adoption of PQC, this will be a heavier lift for some companies that still need to prepare for this new frontier.

Today, for non-trivial hash algorithms, it's still hard to tamper with a file and have a hash match. So, many companies and practitioners aren't validating signatures for things moving through the supply chain. Instead, they rely on simple hashes to detect tampering. Post-quantum, we cannot assume that will be true, not only for future content but for today’s content that still matters in the future.

What are the challenges of post-quantum cryptography?

There are several barriers to deployment of PQC, including:

• Lack of standardization: There are no widely accepted standards, making it difficult for organizations to implement.

• Interoperability: PQC may not be compatible with existing protocols and systems, potentially making it difficult to integrate into existing systems.

• Performance: PQC algorithms are significantly slower than traditional cryptography. An organization with limited computing resources would find it challenging to implement.

• Adoption: Widespread adoption requires coordination and collaboration across multiple industries, including technology, finance, and government.

• Cost: Implementing PQC will be expensive and possibly require organizations to invest in new software, hardware, research, and development.

What are the types of post-quantum approaches?

Different post-quantum (PQ) approaches commonly discussed to address threats posed by quantum computers to the current encryption methods include:

• Lattice-based cryptography: Considered one of the most secure PQ encryption methods, it uses mathematical structures called lattices to encrypt data. While current algorithms, like RSA, rely on factoring large prime numbers, lattice algorithms rely on the difficulty of finding the right lattice point in a high dimensional vector space.

• Code-based cryptography: This approach uses error-correcting code for encryption. While it’s one of the easiest methods, it’s also one of the least secure.

• Multivariate cryptography: One of the quickest methods and also one of the least secure, uses mathematical functions to encrypt data.

• Hash-based cryptography: Coming in as one of the most secure PQ methods, using hash-based functions to encrypt data is also one of the slowest.

• Isogeny-based cryptography: Also known as one of the more secure methods but slow, this approach uses mathematical structures called isogenies for encrypting data. Some more recent modern algorithms, like ECC, rely on finding points on elliptic curves. Isogency-based algorithms extend this by mapping the original elliptic curve to an isogenous one, making it difficult to work backward without the right information.

What is the current status of PQC algorithms?

Executive Order 14028 called for Improving the Nation's Cybersecurity, which states there must be more than government action to protect against malicious attacks. They'll need to partner with the private sector to ensure a higher level of security.

"The transition to post-quantum encryption algorithms is as much dependent on the development of such algorithms as it is on their adoption. While the former is already ongoing, planning for the latter remains in its infancy. We must prepare for it now to protect the confidentiality of data that already exists today and remains sensitive in the future."

- U.S. Secretary of Homeland Security, Alejandro Mayorkas, March 31, 2021

The National Institute of Standards and Technology (NIST) recently named its first four quantum-resistant algorithms. 

• General encryption recommendation

• CRYSTALS-Kyber: Algorithm allows two parties to exchange a comparability small encryption key without sacrificing too much speed and is a lattice-based approach.

• Digital signature recommendation 

• CRYSTALS-DILITHIM: High efficiency and primary recommendation, a lattice-based approach. 

• FALCON: Also high efficiency and lattice-based approach for applications requiring smaller signatures. 

• SPHINCS+: Though larger and slower, this hash-based approach is a reasonable backup to the other three.

While NIST is encouraging security teams and IT departments to explore and educate themselves about the algorithms, they've also stated the algorithms might be slightly tweaked before they are officially finalized. NIST is encouraging users to inventory their current systems so they know which applications are using public-key cryptography and will need to be updated when it’s time.