Exploring the Post-Quantum Cryptography Part 1


13 min read

Exploring the Post-Quantum Cryptography Part 1

Exploring KEMs like: Kyber1024, Firesaber, and Classic McEliece


Welcome to the inaugural segment of our new series. In this journey towards developing a high-level encryption library using Rust, we focus on post-quantum encryption and the integration of related algorithms such as Kyber1024 and Firesaber KEMs. Complementing these, we implement AES and XChaCha20 for symmetric encryption, enhanced with SHA512-based MAC to ensure data integrity. To kick off this series, the article will delve into CRYSTALS-Kyber (Kyber1024) as a Key Encapsulation Mechanism (KEM), contrasting it with SABER (Firesaber) and Classic McEliece, to illuminate their significance in modern encryption.

Difference between a KEM and a KDF:

Key Derivation Functions (KDFs):

  • Purpose: KDFs are used to derive a secret key from a piece of non-secret input, such as a password or a master key. The derived key is then used for cryptographic purposes like encryption or authentication.

  • Functionality: A KDF processes input keying material, which may not be uniformly random or of adequate length, to produce a cryptographically strong key. This key can be used as a digital signature. The process typically involves the application of a hashing function or a block cipher.

  • Use Cases:

    • KDFs are commonly employed in password hashing, where they transform passwords into secure keys.

    • They are instrumental in generating keys from a master key as part of key management systems.

    • KDFs play a vital role in deriving keys from a shared secret, a process that is essential during key exchange protocols.

  • Quantum-Safe KDFs:

    • With the emergence of quantum computing, there's an increasing focus on quantum-safe KDFs, such as Falcon. Falcon (Fast-Fourier Lattice-based Compact Signatures over NTRU) is designed to be resistant to quantum computer attacks.

    • It uses lattice-based cryptography, which is believed to be secure against quantum computers. Lattice problems, on which Falcon is based, have not yet been solved efficiently by quantum algorithms.

    • Falcon is particularly notable for its application in digital signatures, providing a quantum-resistant alternative to traditional RSA and ECDSA signatures.

    • The adoption of Falcon and similar quantum-safe KDFs is critical for ensuring the long-term security of cryptographic systems in the quantum computing era.

Key Encapsulation Mechanisms (KEMs):

  • Purpose: KEMs are used to securely encrypt and transfer a key from one party to another. They are typically used in public key cryptography to encapsulate a symmetric key which can then be safely transmitted.

  • Functionality: In a KEM, a sender uses the recipient's public key to encrypt a secret key. The recipient then uses their private key to decrypt and obtain the secret key. The encapsulated key is typically used for encrypting a larger message with a symmetric encryption algorithm.

  • Use Cases: KEMs are commonly used in secure communications, where a shared secret key needs to be established between two parties over an insecure channel, such as in TLS/SSL protocols.

  • Quantum-Safe KEMs:

    • Quantum-safe KEMs are designed to withstand attacks from quantum computers. These KEMs often rely on mathematical problems that are believed to be hard even for quantum algorithms.

    • The primary function of a quantum-safe KEM is to securely exchange keys in a way that is resistant to quantum attacks. It allows two parties to establish a shared secret key over an insecure channel without risking exposure to quantum eavesdropping.

    • Quantum-safe KEMs are especially crucial for securing data and communications in a post-quantum world.

    • These KEMs are an essential component of the evolving cryptographic landscape, providing a robust defense against the potential threats posed by quantum adversaries.

In summary, KDFs are about deriving strong keys from possibly weak or non-random input, while KEMs are about safely transmitting keys using asymmetric encryption. Both are essential in different stages of secure communication and data protection.

Kyber1024 as a KEM: A Glimpse into the Future

Current Encryption Schemes:

In recent years, quantum computers have been making great strides. Unlike regular computers, these quantum computers work in a way that can solve certain problems much faster. This rapid development is exciting, but it also brings a big challenge, especially for keeping information safe online.

Most of the security on the internet today, like the kind that keeps your emails private or your online banking secure, relies on special codes called ciphers for encrypting and signing the incoming and outgoing communication. This encryption uses complex math problems that are really hard for regular computers to solve. Due to their unique operational framework, quantum computers have the capability to rapidly solve certain mathematical problems that traditional computers struggle with. This means they can potentially break these codes easily, making things like your personal information vulnerable.

The encryption schemes RSA and ECC are ubiquitous in securing everything from online transactions to confidential communications. However, quantum computers, leveraging algorithms like Shor's algorithm, could break these systems with relative ease. Shor's algorithm, in particular, is capable of factoring large numbers and computing discrete logarithms rapidly, which are the bases of RSA and ECC security. This looming threat has driven the need for new cryptographic standards that can withstand quantum attacks.

The Solution (possibly): Quantum-Resistant Algorithms

This is where quantum-resistant algorithms come into play. These are cryptographic algorithms believed to be secure against the onslaught of quantum computing. Among these, a notable contender is Kyber1024.

Kyber1024 is a post-quantum cryptographic algorithm, specifically designed to be resistant to quantum attacks. It's part of a broader initiative to develop and standardize post-quantum cryptography. Kyber1024 operates on principles that differ significantly from RSA and ECC, making it a strong candidate in the post-quantum era.

In conclusion, while quantum computing brings many potential benefits, it also poses significant threats to our current cryptographic infrastructure. The development and adoption of quantum-resistant algorithms like Kyber1024 are crucial to ensuring the security of our digital world in the face of quantum computing advancements. As developers and tech enthusiasts, it's essential to stay informed and prepared for these changes, which will define the future landscape of digital security.

Role of NIST in the Future of Encryption

The National Institute of Standards and Technology (NIST) plays a pivotal role in the transition to quantum-resistant cryptography. As a renowned and influential organization, The United States' NIST is tasked with setting the standards and guidelines that shape the technological and security protocols used not only in the United States but also globally. Their involvement is particularly crucial in the realm of cryptography, especially given the quantum threat.

The selection process is rigorous and transparent, focusing on security, performance, and adaptability. Among the many submissions, algorithms like Kyber1024 have emerged as strong candidates in certain categories. The evaluation criteria are comprehensive, assessing not just the quantum resistance of these algorithms, but also their practicality in terms of implementation and efficiency.

Beyond the selection of algorithms, their role extends to guiding the global community in the transition to post-quantum cryptography. This involves developing a roadmap for the adoption of new standards, offering resources and guidelines for implementation, and collaborating with various stakeholders to ensure a smooth transition. Their guidance is crucial for maintaining the integrity and security of digital systems during this paradigm shift.

The impact of the efforts is not limited to the United States; it has a global reach. The standards set by NIST often become benchmarks for other countries and industries, influencing international policies and practices. Furthermore, NIST actively collaborates with international cryptographic communities, ensuring a coordinated and unified approach to tackling the quantum threat.

Kyber1024: In-Depth Analysis and Features

Architectural Elegance and Working Mechanism

Kyber1024, notable for its lattice-based cryptographic framework, presents a significant shift from traditional cryptography. This system is built on the complexity of solving the learning-with-errors (LWE) problem over module lattices, which forms the core of its security against quantum attacks. The essence of Kyber1024's strength is its reliance on multi-dimensional lattice structures, offering robust quantum resistance and positioning itself as a future-proof cryptographic solution.

Key Features and Mechanisms

  • Private and Public Key Generation: Kyber1024's private key is generated using random small coefficients. The public key comprises a matrix of random polynomials and a vector of polynomials. The generation of these elements involves random coefficients and modular arithmetic.

  • Encryption and Decryption Process: Encryption in Kyber1024 involves using the public key to encrypt a message, which is transformed into a polynomial with binary coefficients. The decryption can only be conducted by parties possessing the private key. This process uses polynomial vectors and modular arithmetic to encrypt and decrypt messages, ensuring secure communication.

  • Quantum Resistance: The core of Kyber1024's defense against quantum computing lies in its reliance on the module-learning-with-errors (MLWE) problem. MLWE is expected to be intractable even for quantum computers, making Kyber1024 a strong candidate for post-quantum cryptography.

Practical Implications and Considerations

  • Security Levels: Kyber1024 is tailored for different security levels, analogous to AES-256, providing flexibility and adaptability in various cryptographic applications.

  • Hybrid Mode Recommendation: It is suggested to use Kyber1024 in hybrid mode, combining it with established pre-quantum security measures like elliptic-curve Diffie-Hellman, to enhance overall cryptographic robustness.

  • Performance Metrics: Performance benchmarks on various platforms indicate Kyber1024's practicality, including its implementation in C and optimized versions using AVX2 vector instructions. These benchmarks offer insights into its efficiency and potential for integration into existing systems.

In conclusion, Kyber1024 stands as a promising solution in the evolving landscape of cryptography, particularly in the face of quantum computing advancements. Its lattice-based architecture, grounded in the complexity of the MLWE problem, along with its adaptable security levels and practical performance metrics, position it as a viable candidate for securing digital communications in the post-quantum era.

Firesaber: In-Depth Analysis and Features

Architectural Design and Working Mechanism

Firesaber, part of the SABER family of cryptographic mechanisms, is known for its robustness in quantum-resistant encryption. It operates based on the Module Learning With Rounding (MLWR) problem, which remains secure even against quantum computing threats. Firesaber, positioned as equivalent to AES-256 in terms of post-quantum security, is recognized for its simplicity, efficiency, and flexibility.

Key Features and Mechanisms

  • Key Encapsulation Mechanism (KEM): Firesaber serves as an IND-CCA2 secure KEM. Its security, relying on the hardness of the MLWR problem, is designed to be resilient against both classical and quantum cryptanalysis.

  • Design Goals: The architecture of Firesaber is streamlined for both software and hardware implementations. This includes the use of power-of-two moduli to simplify modular reductions and improve masking simplicity. Additionally, the avoidance of sampling from an error distribution enhances both security and implementation ease.

  • Module Structure: This aspect of Firesaber offers flexibility, enabling different security levels with a singular core component. This design strategy simplifies implementation across various applications.

Practical Implications and Considerations

  • Security Levels: The SABER-suite, which includes Firesaber, offers varying levels of security analogous to different AES standards. Firesaber, in particular, aims for the highest security level comparable to AES-256.

  • Simplicity and Efficiency: The design choices in Firesaber, like power-of-two moduli and avoidance of rejection sampling, contribute to its simplicity and efficiency. These features make it a suitable candidate for applications requiring constant-time operations and secure anonymous communication.

  • Security Estimates: Conservative security estimates place Firesaber at a high level of resilience. The quantum security estimates, based on core SVP (Shortest Vector Problem) oracle costs, suggest a strong defense against potential quantum attacks.

In terms of performance and implementation details, Firesaber offers a balance between security level and efficiency. Its design considerations make it a strong contender for various applications, especially in environments where high-level security and quantum resistance are paramount. Firesaber's approach, focusing on simplicity and efficiency, positions it as a viable solution for the future of cryptography in the quantum computing era.

Classic McEliece: Comprehensive Analysis and Features

Overview and Mechanism

Classic McEliece, introduced in 1978 by McEliece, is a code-based public-key cryptosystem. Its foundation is built on the complexity of decoding a random binary Goppa code. The system's security primarily depends on the difficulty of decoding these codes, a challenge that remains formidable even against quantum computer attacks. The cryptosystem employs a mechanism where the ciphertext is a codeword combined with random errors, and the private key facilitates efficient decoding.

Key Cryptographic Process

Key Generation: Classic McEliece generates keys using Goppa codes. The public key specifies a random binary Goppa code, while the private key enables efficient decoding.

  • Encryption Process: In Classic McEliece, a message is first encoded as a binary string. This string is then transformed using the public key and combined with a randomly generated error vector to produce the ciphertext.

  • Decryption Process: The decryption involves computing the inverse of certain transformations and using the decoding algorithm to recover the original message from the ciphertext.

Core Aspects and Attributes

  • Code-based Cryptography: The system is based on algebraic coding theory, particularly focusing on block codes and polynomial rings over finite fields. This mathematical background contributes to its robustness against quantum attacks.

  • Efficiency and Scalability: Classic McEliece's parameters can be scaled to enhance security levels. The original parameters were designed for a lower security level, but the system allows scaling up to parameters that offer substantial security margins against both classical and quantum computational advances.

Security and Applications

  • Quantum Resilience: The main strength of Classic McEliece lies in its resistance to quantum computing threats. Its reliance on the hard problem of decoding random binary Goppa codes makes it a strong candidate for post-quantum cryptography.

  • Stability and Versatility: Despite numerous attack papers over decades, the security level of Classic McEliece has remained stable. The cryptosystem has undergone various improvements for efficiency, both in software and hardware, without compromising its security.

  • Conversion to KEM: Recent developments have shown how to efficiently convert the one-way McEliece system into a Key Encapsulation Mechanism (KEM) that is IND-CCA2 secure against all ROM attacks, further enhancing its application in secure communication protocols.

In conclusion, Classic McEliece stands as a testament to the enduring power of code-based cryptography. Its quantum resilience, coupled with its proven security record and the potential for efficient implementation, makes it a vital part of the conversation on securing digital communications in the quantum era.


As we conclude our deep dive into the intricate world of post-quantum cryptography, it's evident that the advancements in quantum computing pose significant challenges to our current cryptographic infrastructure. The exploration of Kyber1024, Firesaber, and Classic McEliece reveals the ingenuity and adaptability of cryptographic research in addressing these emerging threats.

Reflection on Kyber1024

Our analysis of Kyber1024 illuminated its lattice-based framework, showcasing a significant shift from traditional cryptographic methods. Its reliance on the complex module-learning-with-errors (MLWE) problem positions it as a formidable defense against quantum threats. The design of Kyber1024 represents a proactive step towards safeguarding our digital communications against the advancing capabilities of quantum computing.

Understanding Firesaber

Firesaber, another key player in this field, demonstrated its strength through the Module Learning With Rounding (MLWR) problem. The design goals of simplicity, efficiency, and flexibility, coupled with its quantum resistance, make Firesaber an attractive option for secure communications in a post-quantum world. Its adaptability to different security levels and constant-time operations strengthens its position as a crucial element in the cryptographic arsenal.

The Legacy of Classic McEliece

Classic McEliece, a code-based cryptosystem, has shown remarkable resilience over decades. Its foundation on the decoding of random binary Goppa codes and the ability to scale its parameters for enhanced security are testaments to its robustness. Classic McEliece's resistance to quantum computing threats and its stable security record underscore the importance of diversifying cryptographic approaches in anticipation of future challenges.

Moving Forward

The exploration of these three cryptographic mechanisms underscores a critical truth: the field of cryptography is rapidly evolving, with quantum computing advancements driving significant changes. The roles of Kyber1024, Firesaber, and Classic McEliece in this landscape are pivotal. They not only offer solutions to current challenges but also lay the groundwork for future innovations in securing digital communications.

In this dynamic era of cryptographic evolution, it becomes necessary to persistently engage in the exploration, enhancement, and implementation of new and sophisticated cryptographic technologies. Embedding them into our digital frameworks is key to safeguarding data privacy, maintaining unimpeachable integrity, and fortifying security as we step into the quantum future.

In our ongoing exploration of the field of cryptography, it is essential for developers, researchers, and engineers to stay deeply engaged with the latest developments. The future of digital security depends on our shared dedication to understanding, embracing, and incorporating these cutting-edge cryptographic breakthroughs.

Did you find this article valuable?

Support M by becoming a sponsor. Any amount is appreciated!