Post-Quantum Cryptography

Key Takeaways

For decades, our digital security has relied on complex mathematical problems that are incredibly difficult for regular computers to solve. But quantum computing poses a major threat to this system. While quantum computers promise incredible breakthroughs in fields like medicine and materials science, they also pose a grave threat to our digital data protection barriers.

Hackers can spend a very long time attempting to guess number combinations; utilizing the shifting nature of quantum entanglement would allow them to guess combinations at an unheard-of rate. This is where post-quantum cryptography comes in.

Let’s explore what post-quantum cryptography means for encryption and data security practices.

What Is Post-Quantum Cryptography?

Post-quantum cryptography, also known as quantum-resistant cryptography, focuses on developing cryptographic methods that can withstand attacks from quantum computers, while still being deployable on current classical computers.

Think of a classical computer as a single path through a maze. It explores one route at a time. A quantum computer, on the other hand, can explore every path simultaneously. This ability allows it to decipher codes much faster than traditional computers.

In classical computers, a brute-force attack would take time as the computer tries every combination to break through security barriers. However, quantum computers run these attempts simultaneously, multiplying the threat of brute-force attacks.

One effective strategy involves increasing the size of digital keys. Doubling a key size from 128 bits to 256 bits dramatically increases the number of possible combinations a quantum computer must explore during a brute-force attack. This makes it exponentially harder and slower for quantum machines to crack the encryption.

Why is Quantum Computing so Powerful?

Quantum computers excel at solving specific problems more efficiently due to their ability to process multiple possibilities simultaneously.

Rather than standard mathematical algorithms and bits, a quantum computer uses quantum mechanics and qubits, which are more changeable and flexible than bits. Quantum computers also leverages concepts from quantum mechanics such as light particles, quantum superposition and entanglement, all of which enable it to be incredibly powerful.

So quantum computers are able to process information in an extremely advanced way by importing concepts and methods from the field of quantum mechanincs.

Pre-Quantum vs. Quantum vs. Post-Quantum Cryptography

We’ve relied on classical cryptographic methods to protect our information for decades. These methods use algorithms like RSA (Rivest–Shamir–Adleman), ECC (Elliptic Curve Cryptography), and DSA (Digital Signature Algorithm), which we cover in our detailed cryptography article.

They rely on mathematical problems such as integer factorization and discrete logarithms, which classical computers find extremely tough to solve. To give you an idea, an RSA 2048-bit key is so secure that even a supercomputer would struggle to crack it.

Enter quantum cryptography. Quantum cryptography uses atom properties and geometric ciphers to encrypt data. Quantum Key Distribution (QKD) is a fascinating subset using quantum mechanics principles to share encryption keys securely.

As we approach the quantum era, post-quantum cryptography becomes crucial.

The transition to post-quantum cryptographic methods is essential to maintain data security in the face of advancing quantum computing. The journey from pre-quantum to post-quantum cryptography highlights the ongoing efforts to stay ahead in the digital security race.

The table below provides a summary of the comparison. 

The Quest for Quantum-Resistant Algorithms

In 2016, the National Institute of Standards and Technology (NIST) began seeking submissions for algorithms to replace RSA, ECDSA, ECDH, and DSA cryptosystems. The NIST Post-Quantum Cryptography Standardization Project has progressed through multiple phases, selecting four algorithms for standardization in 2022: CRYSTALS-Kyber, for public-key encryption and key establishment, and CRYSTALS-Dilithium, FALCON, and SPHINCS+, for digital signatures.

Lattice-based schemes like CRYSTALS-Kyber are promising due to their strong security proofs and efficient implementation. Code-based cryptography, exemplified by Classic McEliece, and multivariate polynomial cryptography, offer additional strategies.

Despite progress, challenges include ensuring consistent device performance, continuous cryptanalysis, interoperability, and robust implementation.

Post Quantum Cryptography Algorithms

Post-quantum cryptography research covers six main approaches, each exploring different mathematical structures and concepts.

These include:

• Lattice-based cryptography
• Multivariate cryptography
• Hash-based cryptography
• Code-based cryptography
• Isogeny-based cryptography
• Symmetric key quantum resistance

Let’s discuss each one.

Lattice-Based Cryptography

Lattice-based cryptography is one of the most promising areas in post-quantum cryptography. It leverages the complexity of problems related to lattices, which are grid-like structures that extend infinitely in multiple dimensions. The security of lattice-based systems hinges on the difficulty of solving specific problems within these lattices, such as the Learning with Errors (LWE) problem.

Lattice-based cryptography has several advantages. It provides security against both classical and quantum attacks. Additionally, some lattice-based schemes allow for efficient operations, making them practical for real-world applications. For example, the NTRU encryption algorithm, which many have studied since the 1990s, remains unbroken despite extensive analysis.

Moreover, lattice-based cryptography is versatile. It supports many cryptographic primitives, including public-key encryption, digital signatures, and fully homomorphic encryption, allowing computations on encrypted data without decrypting. This versatility makes it a strong candidate for standardization in post-quantum cryptography.

Multivariate Cryptography

Multivariate cryptography focuses on the complexity of solving systems of multivariate polynomial equations over finite fields. This area has seen mixed results; while researchers have broken some encryption schemes, multivariate signature schemes like the Rainbow signature scheme continue to show promise.

Rainbow, in particular, is notable for its efficiency and relatively small key sizes compared to other post-quantum signature schemes. It creates a signature from a solution to a system of multivariate equations, a problem considered hard for both classical and quantum computers to solve.

However, the adoption of multivariate cryptography has been slower than other approaches because of the failure of several proposed schemes and the complexities involved in implementation. Yet, the potential for secure digital signatures makes it an area worth exploring, especially as the need for quantum-resistant signatures becomes more pressing.

Hash-Based Cryptography

Hash-based cryptography offers a simpler, more well-understood approach to quantum resistance. It builds on the strength of cryptographic hash functions, which are resistant to quantum attacks when used correctly. This area primarily focuses on digital signatures rather than encryption.

The Merkle Signature Scheme (MSS), one of the earliest hash-based signatures, exemplifies the potential of this approach. MSS offers a direct path to quantum resistance despite its limitations.

Recent developments, such as the eXtended Merkle Signature Scheme (XMSS) and SPHINCS+, address the limitations of earlier hash-based schemes by allowing for more signatures and improving efficiency. These schemes are appealing because they rely on trusted cryptographic hash functions.

Hash-based cryptography is critical for post-quantum security, particularly for critical applications like software updates, secure communications, and blockchain transactions.

Code-Based Cryptography

Code-based cryptography derives its security from the formidable challenge of decoding general linear codes, a complex problem that mathematicians have intensively studied since the 1970s. The McEliece cryptosystem, a prominent example of this approach, has withstood the test of time, resisting classical and quantum computer attacks for over four decades.

The McEliece system constructs a public key encryption scheme. While burdened by substantial key sizes, a notable drawback, it compensates with efficient encryption and decryption processes, making it a suitable option for performance-critical environments. Organizations like the National Institute of Standards and Technology currently consider code-based cryptography for standardization to protect critical infrastructure, underscoring its potential as a reliable foundation for post-quantum security.

Isogeny-Based Cryptography

Isogeny-based cryptography leverages the intricate mathematical properties of elliptic curves and their isogenies to construct a novel form of post-quantum cryptography. Researchers employ these mappings between curves to create cryptographic systems capable of withstanding threats from quantum computing. Isogeny-based cryptography allows using smaller key sizes compared to other post-quantum algorithms, a critical advantage for resource-constrained devices and applications demanding high efficiency.

The Supersingular Isogeny Diffie-Hellman (SIDH) protocol represents one of the most prominent examples of isogeny-based cryptography. Designed as a quantum-resistant counterpart to the widely adopted elliptic curve Diffie-Hellman (ECDH) key exchange, SIDH has shown promise in securing digital communications. However, in a significant development in 2022, researchers uncovered a key recovery attack capable of compromising the protocol under specific conditions.

Continued advancements in this area are crucial for ensuring the widespread adoption of post-quantum cryptography and protecting critical infrastructure in an era dominated by the looming threat of quantum computing.

Symmetric Key Quantum Resistance

Symmetric key cryptography, relying on shared secret keys, offers a strong foundation against the emerging threats from quantum computing technology. Unlike their public-key cryptography counterparts, symmetric encryption algorithms such as AES-256 maintain security against quantum attacks when using sufficiently large key sizes. However, Grover’s algorithm does reduce AES-256’s effective key length to 128 bits, emphasizing the ongoing need for vigilance.

The Achilles heel of symmetric key cryptography lies not in the encryption algorithms themselves but in the intricate process of key management. Systems like Kerberos, while capable of delivering quantum-resistant authentication and encryption, heavily rely on secure key distribution methods that can withstand the onslaught of quantum computing power.

Increasing key sizes provides an immediate enhancement, while hybrid systems, strategically combining quantum-resistant public-key cryptography with established symmetric key algorithms, offer a gradual pathway to post-quantum security without disrupting existing critical infrastructure.

Post-Quantum Cryptography vs. Quantum Key Distribution

Post-quantum cryptography develops algorithms immune to attacks from future quantum computers. In contrast, quantum key distribution leverages quantum mechanics to transmit encryption keys. This technology guarantees secure communication by detecting any eavesdropping attempts. While both approaches address the threat of quantum computing, they employ fundamentally different techniques to achieve their goals.

The Future of Post-Quantum Cryptography

Today’s encryption algorithms, including public-key cryptography, securely protect our data. While quantum computing exists, its high cost restricts its use to scientific and government research. However, a race unfolds between researchers developing post-quantum encryption and those aiming to break RSA and similar systems using quantum algorithms.

Many experts predict quantum supremacy within a decade, rendering RSA and similar asymmetric algorithms ineffective for safeguarding sensitive data. In response, NIST aggressively seeks a post-quantum encryption standard.

Experts advise organizations to create an encryption application index during NIST’s evaluation of proposed standards. The index, tracking public and third-party encryption libraries, will aid in developing a post-quantum cryptography implementation plan once a standard matures and receives approval.