Planning for post-quantum cryptography: Impact, challenges and next steps

Symmetric vs. asymmetric cryptography

Encryption algorithms can be classified into one of two categories based on their use of encryption keys. Symmetric encryption algorithms use the same secret key for both encryption and decryption. Asymmetric or public-key encryption algorithms use a pair of related keys. Public keys are used for encryption and digital signature validation, while private keys are used for decryption and digital signature validation.

Different types of encryption algorithms have different benefits and downsides. For example, symmetric encryption algorithms are often more efficient, making them well-suited to bulk data encryption. However, they need the shared secret key to be shared between the sender and recipient over a secure channel before message encryption/decryption can be performed.

Asymmetric cryptography is less efficient but does not have this requirement. Encryption is performed using public keys, which, as their name suggests, are designed to be public. As a result, asymmetric algorithms are often used to create a secret channel over which a shared symmetric key is established for bulk data encryption.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Asymmetric cryptography and “hard” problems

Asymmetric encryption algorithms are built using a mathematically “hard” problem. This is a mathematical function where performing an operation is far easier than undoing it. For example, a commonly used “hard” problem in asymmetric cryptography is the factoring problem. Multiplying two large prime numbers together is relatively “easy” with polynomial complexity. In contrast, factoring the result of this multiplication is “hard” with exponential complexity.

This difference in complexity makes it possible to develop cryptographic algorithms that are both usable and secure. Public key encryption algorithms are designed so that legitimate users only perform “easy” operations, while an attacker must perform “hard” ones. The asymmetric complexity between these operations makes it possible to choose key lengths for which performing the “easy” operation” is possible, while the “hard” operations are infeasible on modern computers.

Impacts of quantum computing on asymmetric cryptography

The security of public-key cryptography depends on the “hardness” of these underlying problems. If the “hard” problem (factoring, logarithms, etc.) can be solved with polynomial complexity, then the security of the algorithm is broken. Even if the complexity of breaking cryptography is hundreds, thousands, etc., times more difficult than using it, an attacker with sufficient resources and incentives (nation-states, etc.) could perform the attack.

Quantum computing poses a threat to asymmetric cryptography due to the existence of Shor’s algorithm. On a sufficiently large quantum computer, Shor’s algorithm has the ability to solve the factoring problem in polynomial time, breaking the security of asymmetric cryptography.

Public key cryptography underpins the modern Internet, so the emergence of quantum computers large enough to break it is a significant future threat. 

Some common applications of asymmetric cryptographic algorithms include

• Data encryption
• Key sharing for symmetric encryption (in TLS, etc.)
• Digital signatures (PKI, code signatures, etc.)

Post-quantum cryptography secures asymmetric cryptography

The classical asymmetric cryptography algorithms in common use today are vulnerable because they use “hard” problems (factoring, logarithms, etc.) that are not “hard” for quantum computers. However, other “hard” problems exist that are currently believed to be “hard” for quantum computers as well. These problems can be used to create post-quantum asymmetric cryptographic algorithms.

NIST is in the midst of a contest designed to select algorithms for standards for post-quantum cryptography, similar to how AES is a standard for symmetric cryptography. The contest is nearing its end, with the selected algorithms expected to be announced within the next couple of years.

Once the final algorithms are announced, standards will be defined based on these algorithms. This will kick off an implementation process as organizations work to shift protocols and technologies away from classical algorithms to post-quantum ones.

Challenges of post-quantum cryptographic algorithms

Asymmetric encryption algorithms play critical roles in modern technology. Ideally, post-quantum algorithms will enable the development of “drop-in replacements” for certain types of algorithms based on public-key cryptography, especially key sharing and digital signature algorithms.

According to NIST, however, many of the finalist candidates for post-quantum cryptographic standards have issues that preclude their use as drop-in solutions. These include:

• Large signature sizes
• Excessive processing requirements
• Large key sizes
• Asymmetric operations between senders and recipients

Implementations and standards based on these algorithms may need to include support and solutions for:

• Public key validation
• Public key reuse
• Unanticipated decryption failure
• Selection of new auxiliary functions

These challenges and requirements make it unlikely that post-quantum algorithms will be able to slot into existing protocols. New and updated protocols will be required, which may need to define how different algorithms should be used for different scenarios, how messages should be segmented to address size issues etc. Defining these new protocols must wait until algorithm selection is complete and must occur before standardized implementations can be developed.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Next steps for post-quantum encryption

While quantum computers exist today, they are nowhere near the size needed to break the asymmetric encryption algorithms needed today. While the industry is advancing quickly, large-scale quantum computing is still many years in the future.

However, NIST is running its post-quantum contest and developing standards today because the process takes time. Also, deploying post-quantum encryption as soon as possible is essential to protecting against “collect now, decrypt later” attacks.

In its whitepaper, NIST detailed some of the steps that will need to be completed during the transition to post-quantum encryption. These include

• Developing standards. Once post-quantum algorithms have been selected, standards will be developed that describe their configuration and usage.
• Identifying cryptographic applications. Cryptographic algorithms underpin much of modern technology. Companies often lack visibility into where vulnerability cryptography may exist in their environments, making it necessary to develop tools and techniques for identifying crypto usage.
• Creating strategies to update algorithms. Post-quantum cryptographic algorithms are often not drop-in replacements for classical algorithms. New protocols will need to be developed to accommodate these new algorithms.

The transition to post-quantum encryption will not be fast or easy. However, large quantum computers are still years off, thus providing time to find solutions.

Sources:

• Asymmetric Cryptography, Infosec Institute
• Post-Quantum Cryptography, NIST
• Getting Ready for Post-Quantum Cryptography, NIST