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.

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…[…] Read more »….