Implementing post-quantum KEMs: Practical challenges and solutions ⋆ Pavlo Vorobets1,†, Oleksandr Vakhula1,†, Andrii Horpenyuk1,† and Nataliia Korshun2,*,† 1 Lviv Polytechnic National University, 12 Stepana Bandery str., 79013 Lviv, Ukraine 2 Borys Grinchenko Kyiv Metropolitan University, 18/2 Bulvarno-Kudryavska str., 04053 Kyiv Ukraine Abstract The paper provides an overview and analysis of the current state, problems, and prospects of post-quantum key encapsulation mechanisms. The essential cryptographic building blocks for implementing secure communication protocols are key-encapsulation mechanisms. KEMs enable two parties to securely establish a shared secret key over an insecure channel. This shared key can then be used for symmetric encryption of messages, ensuring confidentiality and integrity of the exchanged data. The National Institute of Standards and Technology (NIST) is actively working on standardizing post-quantum cryptography including KEMs. After the third round of the NIST PQC Standardization Process, NIST has identified the CRYSTALS-KYBER KEM algorithm for standardization. The four algorithms selected for a fourth round are BIKE, Classic McEliece, HQC, and SIKE. In this paper, we explore all these algorithms. Keywords post-quantum cryptography, KEM, standardization process, NIST, CRYSTALS-KYBER, BIKE, Classic McEliece, HQC, SIKE 1 1. Introduction The transition to post-quantum cryptography, including KEMs, is a proactive measure to secure communications As quantum computing advances, the implementation of against future quantum threats. Standardization bodies like post-quantum Key Encapsulation Mechanisms (KEMs) the National Institute of Standards and Technology (NIST) becomes critical for securing data against future threats. are actively working on evaluating and standardizing post- Quantum computing represents a paradigm shift in quantum cryptographic algorithms, including KEMs, to computational power, capable of solving complex provide clear guidelines and frameworks for adoption. mathematical problems much faster than classical As quantum computing advances, the cryptographic computers. This capability poses a significant threat to landscape must evolve to ensure the continued security of current cryptographic systems, particularly those relying on key exchanges and communications. Post-quantum Key public-key algorithms like RSA and ECC, which are Encapsulation Mechanisms are at the forefront of this vulnerable to quantum attacks. The most widely used key evolution, offering new approaches to secure key exchange exchange algorithms today are based on hard mathematical that are resistant to quantum attacks. Understanding and problems, such as integer factorization and the discrete implementing these mechanisms will be crucial for logarithm problem. However, these problems can be protecting sensitive information in the quantum era, efficiently solved by a quantum computer [1]. ensuring that cryptographic systems remain robust and Key Encapsulation Mechanisms are cryptographic secure against emerging threats. protocols designed to securely exchange symmetric keys over insecure channels. They are a cornerstone of many 2. Literature review and problem secure communication systems, enabling the safe transmission of encryption keys that can then be used for statement symmetric encryption. In the quantum era, the security of Cryptography is an essential aspect of modern life, these key exchanges is paramount. providing the necessary security and trust in our digital To counteract the threat posed by quantum computing, interactions, financial transactions, communication, and researchers are developing post-quantum cryptographic data privacy. Its widespread use ensures the confidentiality, algorithms, including post-quantum KEMs. These integrity, and authenticity of information in various aspects mechanisms are based on mathematical problems believed of our daily lives. to be resistant to quantum attacks. CPITS-II 2024: Workshop on Cybersecurity Providing in Information 0009-0007-3870-829X (P. Vorobets); and Telecommunication Systems II, October 26, 2024, Kyiv, Ukraine 0009-0008-5367-3344 (O. Vakhula); ∗ Corresponding author. 0000-0001-5821-2186 (A. Horpenyuk); † These authors contributed equally. 0000-0003-2908-970X (N. Korshun) pavlo.a.vorobets@lpnu.ua (P. Vorobets); © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). oleksandr.p.vakhula@lpnu.ua (O. Vakhula); \ andrii.y.horpeniuk@lpnu.ua (A. Horpenyuk); n.korshun@kubg.edu.ua (N. Korshun) CEUR Workshop ceur-ws.org ISSN 1613-0073 212 Proceedings As quantum computing continues to advance, the threat it Public key encryption is often used to transmit symmetric poses to classical cryptographic systems becomes more encryption keys, which are then used to encrypt the apparent. Quantum computers, once fully realized, will be originally intended plain-text content needing encryption able to efficiently break commonly used cryptographic protection. Symmetric keys are faster and stronger (for schemes like RSA and ECC through Shor’s algorithm, smaller key sizes) than asymmetric encryption, and so PKEs rendering traditional cryptographic infrastructure insecure. are often just used as a secure transport vehicle for the In response to this looming threat, post-quantum symmetric keys that do all the direct encryption work. PKEs cryptography has emerged as a field focused on developing have worked great for decades, but they have at least one cryptographic algorithms that are resistant to quantum big inherent flaw [6]. attacks. Key Encapsulation Mechanisms, which are used for When the public key is longer than the content being secure key exchange, are a key focus in this field [2]. encrypted (such as is usually the case with the symmetric The National Institute of Standards and Technology key in key exchanges), it allows attackers a very easy way (NIST) launched its Post-Quantum Cryptography to derive the original private key. To prevent this scenario, Standardization project in 2017, aiming to identify and when the message content to be encrypted (e.g., the standardize quantum-resistant cryptographic algorithms. symmetric key) is shorter than the asymmetric private key Many algorithms have been proposed, with a significant used to do the encryption, PKEs will usually add additional portion focusing on KEMs due to their critical role in secure “padding” to the message to be encrypted (e.g., the communications [3]. symmetric key) to remove the vulnerability. To address this, post-quantum key encapsulation Key encapsulation methods, also known as key mechanisms are being developed to ensure the secure encapsulation schemes, are a type of asymmetric encryption exchange of encryption keys, even in the presence of technique designed to improve the secure transmission (or powerful quantum adversaries [4]. generation) of symmetric keys because they don’t need random padding added to short messages to stay secure. 3. Introduction to key encapsulation Many postquantum cryptographic algorithms are especially conducive to creating KEMs and because postquantum mechanisms in post-quantum algorithms often have even longer asymmetric keys, you cryptography will see many quantum-resistant teams offering KEMs A Key Encapsulation Mechanism (KEM) is a cryptographic instead of PKEs. Also, some post-quantum cryptographic protocol used to securely exchange encryption keys algorithms will offer both PKE and KEM versions [7]. between two parties. The primary goal of KEMs is to generate and securely encapsulate a random key, which can then be used for further cryptographic operations, such as symmetric encryption. A KEM typically consists of three main phases: Key Generation: The sender generates a pair of keys (public and private keys). The public key is shared with the recipient. Encapsulation: The sender uses the public key to generate a random secret and encapsulates it. The Figure 1: Key Encapsulation Mechanisms encapsulated secret is sent to the recipient. Decapsulation: The recipient uses their private key to 3.1. Types of KEMs in post-quantum recover the original secret from the encapsulated data. cryptography The most widely used key exchange algorithms today are based on hard mathematical problems, such as integer In the post-quantum world, the security of KEMs must rely factorization and the discrete logarithm problem. But these on quantum-resistant mathematical problems. Here are the problems can be efficiently solved by a quantum computer. key post-quantum techniques used for designing KEMs: KEMs are generally designed to be non-interactive,  Lattice-based cryptography—uses lattices and meaning they only require a single communication round their associated mathematical properties to (i.e., one message from the sender to the recipient). provide security. A lattice is a set of points in a The main security goal of a KEM is to prevent attackers multi-dimensional space that form a regular grid- from gaining any useful information about the shared like structure. Lattice-based cryptography is one of secret. These goals are formalized using security definitions, the most promising post-quantum techniques often based on the IND-CCA (Indistinguishability under because it provides strong security guarantees and Chosen Ciphertext Attack) security model [5]. relatively efficient operations. It is based on the A KEM can be seen as similar to a Public Key Encryption hardness of problems like Learning with Errors (PKE) scheme since both use a combination of public and and Short Integer Solution [8]. Lattice-based KEMs private keys. In a PKE, one encrypts a message using the are attractive due to their relatively small key sizes public key and decrypts using the private key. In a KEM, one and fast operations, making them suitable for uses the public key to create an “encapsulation”—giving a practical implementations [9]. randomly chosen shared key—and one decrypts this “encapsulation” with the private key.  Code-based cryptography—relies on error-correcting codes to provide security. The security of these 213 schemes is based on the hardness of decoding certain Table 1 structured codes, making them resistant to quantum Performance Assessment attacks. Code-based cryptography uses the difficulty Algorithm Type Performance of decoding random linear codes, particularly CRYSTALS- Lattice- Overall performance of generalized Goppa codes. One of the oldest forms of KYBER based CRYSTALS-KYBER in software, hardware, and post-quantum cryptography, it offers a high level of hybrid settings is excellent. security but often comes with larger key sizes [10]. BIKE Code-based The performance of BIKE  Hash-based cryptography—built upon cryptographic would be suitable for most of hash functions. These schemes are based on the the applications as confirmed by several hardware hardness of finding collisions in the hash function, benchmarks. offering a potential post-quantum solution. Hash- HQC Code-based The bandwidth of the HQC based cryptography’s fundamental benefit is that it is exceeds that of BIKE, HQC’s a commonly used, well-researched technique that key generation but decapsulation only requires a ensures great resistance to quantum assaults, making fraction of the kilocycles it a candidate for long-term security in the post- required by BIKE. HQC is one quantum period (as a long enough key is utilized). of the top two alternate KEMs. While primarily used in signature schemes, hash- The overall performance of the HQC is not optimal but based cryptography can also be adapted for KEM. still, it is acceptable. These rely on the difficulty of finding preimages or Classic Code-based It has the smallest ciphertext collisions in cryptographic hash functions. McEliece among any of the NIST PQC  Multivariate polynormal cryptography—relies on candidates SIKE Isogeny- It has relatively low algebraic equations with multivariate polynomials. based communication costs. Although secure, the size of the public and private However, performance on keys can be large [11, 12]. embedded devices may be an  Isogeny-based cryptography—based on the issue because of the time to perform a single key mathematics of elliptic curves and isogenies. These encapsulation/decapsulation. schemes rely on constructing mappings between elliptic curves. It offers some of the smallest key sizes For instance, lattice-based schemes like CRYSTALS-KYBER of any post-quantum cryptosystem but is relatively are efficient in terms of security but may still require more slow [13–16]. CPU cycles compared to classical systems. Implementing During the transition to post-quantum cryptography, these algorithms on resource-constrained devices (e.g., IoT hybrid KEMs are being used. These combine classical devices) can be difficult, as they may not have the cryptographic methods (like RSA or ECC) with post- processing power required to handle the increased quantum methods. For example, a hybrid KEM could computational load. The increased computation can simultaneously run both a lattice-based KEM (for post- introduce latency in key exchange processes. This can be a quantum security) and an RSA-based KEM (for classical significant issue for real-time systems (e.g., VoIP, video security), ensuring safety from both quantum and classical conferencing), where even small delays in establishing attacks [17]. secure connections can degrade user experience [17]. Many existing security protocols (e.g., TLS, SSH, IPsec) 3.2. Practical challenges in implementing are based on classical cryptographic primitives like RSA and ECC. Implementing post-quantum KEMs requires either post-quantum KEMs significant changes to these protocols or hybrid systems Implementing post-quantum Key Encapsulation that combine classical and post-quantum techniques. Mechanisms in real-world systems presents several Modifying or extending widely used protocols to support practical challenges. post-quantum KEMs can be complex [18]. It requires not Many post-quantum KEMs, especially those based on only software updates but also widespread adoption to lattice and code-based cryptography, involve much larger ensure that all parties in a communication system can use key sizes compared to classical systems. For example, code- the new algorithms [8]. based KEMs like Classic McEliece have public keys that are One solution to this challenge is the use of hybrid several hundred kilobytes in size, which is significantly cryptography, where both classical and post-quantum larger than RSA or ECC public keys. Larger key sizes algorithms are used together in a key exchange process. increase the bandwidth needed for key exchange, which can However, this increases the complexity of the system and slow down communication, particularly in low-bandwidth can further slow down performance. Hybrid methods can environments such as mobile networks, IoT devices, or add overhead, as two cryptographic algorithms (classical satellite communications. and post-quantum) are run in parallel, increasing Post-quantum cryptographic schemes often require computational and communication costs [19]. more computational power than traditional cryptographic Many post-quantum algorithms, especially those based algorithms. on lattice cryptography, are vulnerable to side-channel attacks such as timing attacks, power analysis, and fault injection attacks. These attacks exploit the physical characteristics of a system to recover secret keys. Protecting 214 implementations of post-quantum KEMs from side-channel communication can agree on a common cryptographic attacks requires additional countermeasures, such as approach. Implementing dual cryptographic systems can constant-time implementations or masking techniques. lead to security risks if not done properly, such as potential These countermeasures can increase the complexity and downgrade attacks where an adversary forces the use of reduce the performance of the system [20]. weaker, classical algorithms. While NIST is in the process of standardizing post- The transition to post-quantum KEMs is necessary to quantum algorithms, the field is still evolving. ensure long-term security in the face of quantum computing Organizations face uncertainty when selecting which post- advancements, but it comes with practical challenges related quantum algorithm to implement, as premature adoption to efficiency, key sizes, integration, and trust. Overcoming could lead to interoperability issues or the need for future these challenges will require advances in both cryptographic upgrades. Additionally, ensuring interoperability between research and engineering, as well as widespread industry different implementations of post-quantum KEMs remains adoption of post-quantum standards [21]. a challenge. After careful consideration during the third round of the NIST PQC Standardization Process, NIST has 4. Overview of post-quantum KEM identified a candidate algorithm for standardization. NIST will recommend the primary KEM algorithm to be algorithms implemented for most use cases: CRYSTALS-KYBER. The NIST has selected several KEMs for standardization, four algorithms selected for this fourth round are BIKE, including CRYSTAL-Kyber and BIKE, Classic McEliece, Classic McEliece, HQC, and SIKE. Many industries rely on HQC, and SIKE. These algorithms represent some of the cryptographic standards and certifications to ensure most promising candidates for post-quantum Key security (e.g., FIPS 140-2/3). Post-quantum cryptographic Encapsulation Mechanisms that have emerged from the systems will need to go through extensive certification NIST Post-Quantum Cryptography Standardization project. processes to be widely adopted in regulated environments, Each one is based on different hard mathematical problems, which can be time-consuming. providing diverse approaches to ensuring security in the While post-quantum KEMs are designed based on post-quantum era [22–24]. problems thought to be hard for quantum computers (e.g., lattice problems, isogenies, etc.), there is still some 4.1. CRYSTALS-Kyber uncertainty about the long-term security of these CRYSTALS-Kyber (Cryptographic Suite for Algebraic algorithms. It is possible that future mathematical Lattices) is one of the most prominent lattice-based KEMs and breakthroughs or quantum algorithms could weaken these was selected as a NIST finalist due to its efficiency, security, assumptions. Building trust in the security of post-quantum and small key and ciphertext sizes. It is based on the Module KEMs is essential for their widespread adoption. However, Learning With Errors (Module-LWE) problem, a variant of businesses may be reluctant to deploy post-quantum the Learning With Errors (LWE) problem, which is widely solutions until there is a high level of confidence in their regarded as hard for quantum computers to solve [25]. security. There is also resistance to change in the industry. The construction of Kyber follows a two-stage Many organizations have deeply entrenched cryptographic approach: first introduce an INDCPA-secure public-key infrastructures that rely on RSA or ECC, and the cost of encryption scheme encrypting messages of a fixed length of transitioning to post-quantum cryptography may be 32 bytes, which is called Kyber.CPAPKE. Then use a slightly prohibitive in the short term. tweaked Fujisaki–Okamoto (FO) transform to construct the During the transition to post-quantum cryptography, IND-CCA2-secure KEM, which is called Kyber.CCAKEM. systems will need to support both classical and quantum- Kyber defines three parameter sets, which we call safe algorithms simultaneously. This creates additional Kyber512, Kyber768, and Kyber1024. The parameters are complexity in terms of key management, negotiation of listed in Table 2. algorithms, and ensuring that both parties in a Table 2 Parameter sets for Kyber NIST Level Designation n k q n1 n2 (du, dv) b Level 1 Kyber512 256 2 3329 3 2 (10,4) 2-130 Level 2 Kyber768 256 3 3329 2 2 (10,4) 2-164 Level 3 Kyber1024 256 4 3329 2 2 (11,5) 2-174 n is set to 256 because the goal is to encapsulate keys with primes for which this property holds, namely 257 and 769. 256 bits of entropy (i.e., use a plaintext size of 256 bits in However, for those primes we would not be able to achieve Kyber.CPAPKE.Enc). Smaller values of n would require the negligible failure probability required for CCA security, encoding multiple key bits into one polynomial coefficient, so was chosen the next largest, i.e., q = 3329. which requires lower noise levels and therefore lowers k is selected to fix the lattice dimension as a multiple of n; security. Larger values of n would reduce the capability to changing k is the main mechanism in Kyber to scale security easily scale security via parameter k. (and as a consequence, efficiency) to different levels. q as a small prime satisfying n | (q-1); this is required to enable fast NTT-based multiplication. There are two smaller 215 Kyber offers a good balance between key/ciphertext size been studied for decades, and no quantum or classical and performance. It is more efficient in both space and speed efficient algorithms are known to solve it. The core compared to many other post-quantum candidates. cryptographic mechanism is the decoding process for Public Key Size: Ranges from 736 bytes (Kyber512) to MDPC codes, which involves flipping bits to correct errors 1,568 bytes (Kyber1024). in a way that only the legitimate parties can succeed. Ciphertext Size: Ranges from 800 bytes (Kyber512) to BIKE’s first building block is a public key encryption 1,568 bytes (Kyber1024). scheme based on a variant of the Niederreiter framework. Kyber’s computational efficiency makes it suitable for a The plaintext is represented by the sparse vector (e0, e1), wide range of applications, including low-power devices and the ciphertext by its syndrome. The decryption is such as IoT and mobile devices. Kyber provides a very performed with a decoding procedure. Next, this PKE is efficient encapsulation and decapsulation process, converted into an IND-CCA KEM with the application of particularly when compared to other post-quantum KEMs. the Fujisaki-Okamoto transformation. For the scheme to be truly IND-CCA, there must be conditions on the decoding 4.2. BIKE failure rate (also called DFR), which is the case here with the chosen decoder [26, 27]. BIKE (Bit-Flipping Key Encapsulation) is a code-based As defined in the specifications, the parameters should cryptographic system that uses Quasi-Cyclic Moderate- satisfy several constraints. The block length r should be a Density Parity-Check (QC-MDPC) codes. It’s designed to prime number, and 2 should be primitive modulo r. The offer efficient key encapsulation while relying on the parameter w should be such that w = 2d ≈ √n with d being hardness of decoding random linear codes, a well- odd. In addition, the error weight should be such that t ≈ √n. established hard problem in cryptography. Instantiated parameters are present in Table 3. BIKE is based on the decoding of QC-MDPC codes, which involves error correction methods. This problem has Table 3 Parameter sets for BIKE r w t l Public key, bits Private key, bits Ciphertext, bits Level 1 12323 142 134 256 12323 2244 12579 Level 2 24659 206 274 256 24659 3346 24915 Level 3 40973 199 264 256 40973 4640 4640 While BIKE offers relatively compact ciphertext sizes, it The original purpose is to encode data and transmit it on a tends to require larger public keys compared to lattice-based noisy channel, allowing the receiver to remove the errors to KEMs like Kyber. get the correct message. If the decoder is kept secret and Public Key Size: Ranges from 1,254 bytes to 4,140 cannot be deduced from the encoder, it makes encoding with bytes, depending on the security level. errors a one-way trapdoor function: the sender encodes with Ciphertext Size: Approximately 154 bytes to 284 bytes. the public encoder and adds as many errors as the decoder BIKE is relatively efficient in the key encapsulation can remove. The receiver with the decoder is then the only process due to the use of fast bit-flipping decoding one who can remove the errors and read the message. algorithms, although it can be slower than some lattice- The public key size grows substantially from 261120 based systems in some use cases. The reliance on error- bytes at NIST level 1 to 1357824 bytes at NIST level 5c. The correcting codes is a tried-and-tested approach, giving private key size also sees a significant increment from 6492 confidence in its long-term security against both classical bytes at level 1 to 14120 bytes at level 5c. These increases and quantum attacks. align with the general principle that larger key sizes translate into stronger security, making the system more 4.3. Classic McEliece resilient against cryptographic attacks. The ciphertext size and the session key size also increase as the NIST level Classic McEliece is one of the oldest and most established progresses, pointing to stronger security and larger post-quantum cryptosystems, first proposed in 1978. It communication overheads [29]. However, the session key relies on the hardness of decoding random Goppa codes, a size remains consistent at 32 bytes, as its primary role is to task that has resisted efficient attacks for over four decades. ensure confidentiality and integrity during a session, Classic McEliece has gained attention due to its long- regardless of the NIST level. standing security record and robust resistance to quantum attacks [28]. Table 4 Parameter sets for Classic McEliece NIST Level Designation Public key, bytes Private key, bytes Ciphertext, bytes Session key, bytes Level 1 mceliece348864 261120 6492 96 32 Level 3 mceliece460896 524160 13608 156 32 Level 5 mceliece6688128 1044992 13932 208 32 Level 5b mceliece6960119 1047319 13948 194 32 Level 5c mceliece8192128 1357824 14120 208 32 216 Classic McEliece is known for its very large public key sizes, is derived from the multiplication of two polynomials, one which are its primary drawback, but it has very small of which is a secret, and another is a random element. The ciphertext sizes and extremely fast decapsulation. process relies on encoding the secret key, which consists of Public Key Size: Up to 1 MB or more for higher small random polynomials, and performing multiplication security levels. in a finite field to produce part of the public key. Ciphertext Size: 208 bytes. During the encapsulation process, the key encapsulator Although the public keys are large, the small ciphertext generates a random message and encodes it using a public size and fast decryption process make McEliece suitable for codeword. The encoding procedure involves polynomial high-performance applications where the size of the public multiplication between the message (represented as a key is not a critical issue. The major disadvantage of polynomial) and the public key polynomial. The ciphertext McEliece is the size of its public keys, which can be as large is generated as the sum of a product of polynomials as several hundred kilobytes to over a megabyte. This makes (including the random polynomials and the public key) it less practical for systems with bandwidth or storage along with some error terms. These multiplications are done limitations. in a ring of polynomials, where coefficients are taken modulo a prime number. 4.4. HQC On the receiver’s side, the decryption process also involves polynomial multiplication. The receiver uses their HQC (Hamming Quasi-Cyclic) is another code-based private key to multiply it with part of the ciphertext. By cryptographic system that uses Quasi-Cyclic codes to multiplying the ciphertext polynomial by the private key achieve secure key encapsulation. HQC is based on the and removing the error components, the original message hardness of decoding random linear codes but uses a can be recovered. The structure of the private key, being different type of code construction compared to Classic sparse (i.e., consisting mostly of small entries), ensures that McEliece and BIKE. this operation is efficient despite the potential for larger HQC is built on the difficulty of decoding random linear polynomials. codes, which is believed to be a hard problem both for In all cases, these polynomial multiplications are classical and quantum computers. performed in a finite ensuring that the polynomials remain HQC uses SHAKE256 for multiple purposes e.g., as a manageable in size and that the modular arithmetic PRNG for fixed weight vector generation and random vector preserves the structure of the quasi-cyclic codes. generation in Key Generation, as a PRNG for fixed weight Polynomial multiplication in HQC is typically implemented vector generation in Encryption, and for hashing in using efficient algorithms such as the Number Theoretic encapsulation and decapsulation. HQC-KEM uses Transform (NTT), which is a variant of the Fast Fourier polynomial multiplication in various stages of its operation. Transform (FFT) for polynomials over finite fields, to speed In HQC, the fundamental mathematical structure involves up the process of large polynomial multiplications. Thus, cyclic codes, and polynomial operations over finite fields polynomial multiplication is a critical and recurring play a crucial role in both the encryption and decryption operation in the key generation, encryption, and decryption processes [30]. steps of HQC-KEM. Polynomial Multiplication is used in the public key generation stage. The public key involves a codeword that Table 5 Parameter sets for HQC NIST Level Designation n k t Public key, bytes Private key, bytes Ciphertext, bytes Level 1 hqc-128 35338 17669 132 2249 56 4497 Level 2 hqc-192 71702 35851 200 4522 64 9042 Level 3 hqc-256 115274 57637 262 7245 72 14485 HQC’s key sizes are intermediate between those of McEliece 4.5. SIKE and BIKE, but its ciphertexts are generally larger. Public Key Size: Ranges from 2,249 bytes to 7,245 SIKE (Supersingular Isogeny Key Encapsulation) is based on bytes. isogeny-based cryptography, a relatively new and Ciphertext Size: Approximately 7,245 bytes to 7,870 promising post-quantum cryptographic approach. SIKE bytes. uses the difficulty of finding isogenies (mappings) between HQC provides security levels aligned with NIST’s elliptic curves. While elliptic curve cryptography (ECC) is requirements, targeting 128-bit and 256-bit classical security vulnerable to quantum attacks, isogeny-based systems levels. remain secure. HQC is more efficient in terms of key generation and SIKE is protected by the computational supersingular encapsulation compared to Classic McEliece, while still isogeny (CSSI) problem and allows for an IND-CCA2 key offering strong security guarantees. As a code-based establishment between two parties [31]. system, HQC benefits from decades of cryptographic The underlying hard problem for SIKE, the research, giving confidence in its resistance to quantum and Computational Supersingular Isogeny problem, involves classical attacks. Compared to other post-quantum KEMs, finding a secret isogeny (a specific type of function between HQC produces relatively large ciphertexts, which may be a elliptic curves) between two given supersingular elliptic disadvantage in bandwidth-constrained applications. curves. This is believed to be computationally infeasible, even for quantum computers, making it a good foundation 217 for post-quantum security. SIKE provides IND-CCA2 uses a prime number 𝑝 of a particular form to define the security, which is a strong form of security for encryption finite field Fp over which elliptic curves are constructed. The schemes. This means that even if an attacker can request form of these primes allows efficient isogeny computations decryptions of ciphertexts of their choice, they cannot learn and ensures that the curves used are supersingular. any useful information about the encryption of a different SIKE primes are of the form: message. This ensures that the key establishment process p=2a*3b*f-1 between two parties is secure even against active attackers where a and b are large integers. who can manipulate and intercept communications. f is a small cofactor, typically set to 1 in many cases. SIKE primes are carefully chosen to optimize both The prime is of a size that ensures 128-bit, 192-bit, or performance and security in the context of supersingular 256-bit security levels, depending on the target. elliptic curves and the supersingular isogeny problem. SIKE Table 6 Parameter sets for HQC NIST Level Prime Form Designation Public key, bytes Private key, bytes Ciphertext, bytes Level 1 22163137 − 1 SIKEp434 330 374 346 Level 2 22503159 − 1 SIKEp503 378 434 402 Level 3 23053192 − 1 SIKEp610 462 524 486 Level 5 23723239 − 1 SIKEp751 564 644 596 SIKE offers one of the smallest key and ciphertext sizes of Real-World Implementation: Testing includes both any other post-quantum cryptosystem, making it hardware and software implementations to ensure that the particularly attractive for use in bandwidth-constrained algorithms are suitable for a range of use cases, from small environments. However, it tends to have slower devices (like IoT) to high-performance systems (like cloud performance compared to other post-quantum KEMs. servers) [33, 34]. Public Key Size: As small as 330 bytes. The ongoing development of post-quantum KEMs like Ciphertext Size: Ranges from 346 to 596 bytes. Crystal-Kyber, BIEK, HQC, Classic McEliece, SIKE, and SIKE’s compact key and ciphertext sizes make it one of others is crucial to ensuring secure communication in a the most bandwidth-efficient post-quantum cryptosystems, quantum future. Each of these algorithms brings unique making it attractive for specific use cases where data size advantages in terms of performance, security, and and storage are a concern, despite its slower performance efficiency, and the NIST competition is helping to refine compared to other schemes. these technologies for eventual standardization and widespread adoption. 5. Conclusions Cryptographers, researchers, and industry experts are References working together to develop and test these algorithms to [1] L. K. Grover, A Fast Quantum Mechanical Algorithm ensure their security and efficiency in real-world for Database Search, Proceedings of the 28th Annual applications. These algorithms are being evaluated for their ACM Symposium on Theory of Computing (1996). ability to resist both classical and quantum attacks as part [2] D. J. Bernstein, J. Buchmann, E. Dahmen, Code-based of the NIST Post-Quantum Cryptography Standardization Cryptography (2016). process. The goal is to identify cryptosystems that will be [3] Horpenyuk, I. Opirskyy, P. Vorobets, Analysis of secure in a future where quantum computers could break Problems and Prospects of Implementation of Post- existing cryptography, while also being efficient in real- Quantum Cryptographic Algorithms, in: Classic, world applications. Quantum, and Post-Quantum Cryptography, vol. 3504 KEMs are critical for secure key exchange in (2023) 39–49. cryptographic protocols, enabling two parties to securely [4] Bernhardt, Quantum Computing for Everyone, establish a shared secret over an insecure channel. In post- Cambridge, MA: MIT Press (2019). quantum cryptography, various KEMs are being explored [5] V. Cini, et al., CCA-Secure (Puncturable) KEMs from for their security and practicality in terms of key sizes, Encryption with Non-Negligible Decryption Errors, speed, and resilience against quantum attacks [32]. Advances in Cryptology – ASIACRYPT 2020. Lecture The development of these KEMs involves close Notes in Computer Science, vol. 12491. (2020). doi: collaboration between academia, industry, and government 10.1007/978-3-030-64837-4_6. organizations. The NIST process, for example, has provided [6] Woodward, Will Quantum Computers Be the End of a platform where researchers can submit their Public Key Encryption? J. Cyber Secur. Technol. 1(1) cryptographic algorithms for rigorous evaluation by the (2016). 1–22. doi: 10.1080/23742917.2016.1226650. global cryptographic community. This collaboration [7] L. Chen, Cryptography Standards in Quantum Time: ensures that these algorithms are tested for: New Wine in an Old Wineskin? IEEE Security & Security: To withstand both classical and quantum Privacy 15(4) (2017) 51–57. doi: attacks. 10.1109/MSP.2017.3151339. Performance: In terms of speed, key size, and memory usage in practical applications. 218 [8] P. Hauke, et al., Perspectives of Quantum Annealing: [24] G. Alagic, et al., Status Report on the Third Round of Methods and Implementations, Reports on Progress in the NIST Post-Quantum Cryptography Physics 83(5) (2020). Standardization Process, NIST Publications (2022). [9] J. Bernstein, Visualizing Size-Security Tradeoffs for doi: 10.6028/NIST.IR.8413. Lattice-Based Encryption, IACR Cryptol, ePrint Arch [25] J. Bos, et al., CRYSTALS - Kyber: A CCA-Secure (2019). Module-Lattice-based KEM, 2018 IEEE European [10] M. Baldi, P. Santini, G. Cancellieri. Post-Quantum Symposium on Security and Privacy (EuroS&P) (2018) Cryptography based on Codes: State of the Art and 353–367. doi: 10.1109/EuroSP.2018.00032. Open Challenges, AEIT International Annual [26] L. Demange, M. Rossi, A Provably Masked Conference. (2017). doi: 10.23919/aeit.2017.8240549. Implementation of BIKE Key Encapsulation [11] Casanova, et al., A Great Multivariate Short Signature, Mechanism, Cryptology ePrint Archive (2024). Submission to NIST (2017). doi: 10.62056/aesgvua5v. [12] R. A. Grimes, Cryptography Apocalypse (2020). [27] Y. Lia, L. -P. Wang, Security Analysis of the Classic [13] A. Bessalov, et al., Implementation of the CSIDH McEliece, HQC and BIKE Schemes in Low Memory, J. Algorithm Model on Supersingular Twisted and Inf. Secur. Appl. 79 (2023). doi: 10.1016/j.jisa.2023. Quadratic Edwards Curves, in: Workshop on 103651. Cybersecurity Providing in Information and [28] O. Kuznetsov, et al., Trade-offs in Post-Quantum Telecommunication Systems, vol. 3187, no. 1 (2022) Cryptography: A Comparative Assessment of BIKE, 302–309. HQC, and Classic McEliece, in: Classic, Quantum, and [14] A. Bessalov, et al., Modeling CSIKE Algorithm on Post-Quantum Cryptography, vol. 3504 (2023) 12–25. Non-Cyclic Edwards Curves, in: Workshop on [29] C. Nugier, V. Migliore, Acceleration of a Classic Cybersecurity Providing in Information and McEliece Postquantum Cryptosystem with Cache Telecommunication Systems, vol. 3288 (2022) 1–10. Processing, in: IEEE Micro, 44(1) (2024) 59–68. [15] A. Bessalov, et al., Multifunctional CRS Encryption doi: 10.1109/MM.2023.3304425. Scheme on Isogenies of NonSupersingular Edwards [30] R. Azarderakhsh, et al., Hardware Deployment of Curves, in: Workshop on Classic, Quantum, and Post- Hybrid PQC, Cryptology ePrint Archive (2021). Quantum Cryptography, vol. 3504 (2023) 12–25. [31] R. Elkhatib, B. Koziel, R. Azarderakhsh, Faster [16] A. Bessalov, et al., CSIKE-ENC Combined Encryption Isogenies for Quantum-Safe SIKE, Topics in Scheme with Optimized Degrees of Isogeny Cryptology – CT-RSA (2022) 49–72. doi: 10.1007/978- Distribution, in: Workshop on Cybersecurity 3-030-95312-6_3. Providing in Information and Telecommunication [32] M. Raavi1, et al., Security Comparisons and Systems, vol. 3421 (2023) 36–45. Performance Analyses of Post-Quantum Signature [17] V. Pastushenko, D. Kronberg, Improving the Algorithms, ACNS 2021: Applied Cryptography and Performance of Quantum Cryptography by Using the Network Security (2021) 424–447. doi: 10.1007/978-3- Encryption of the Error Correction Data, Entropy 030-78375-4_17. 25(956) (2023). doi: 10.3390/e25060956. [33] O. I. Harasymchuk, et al., Generator of Pseudorandom [18] U. Banerjee, S. Das, A. P. Chandrakasan, Accelerating Bit Sequence with Increased Cryptographic Security, Post-Quantum Cryptography using an Energy- Metallurgical and Mining Industry: Sci. Tech. J. 5 Efficient TLS Crypto-Processor, IEEE International (2014) 25–29. Symposium on Circuits and Systems (2020). [34] V. Maksymovych, et al., Combined Pseudo-Random doi: 10.1109/iscas45731.2020.9180550. Sequence Generator for Cybersecurity, Sensors 22 [19] M. Kumar. Post-Quantum Cryptography Algorithm’s (2022). doi: 10.3390/s22249700. Standardization and Performance Analysis, Array, 15 (2022). doi: 10.1016/j.array.2022.100242. [20] F. Borges, P. R. Reis, D. Pereira. A Comparison of Security and Its Performance for Key Agreements in Post-Quantum Cryptography, IEEE Access, 8 (2020) 142413–142422. doi: 10.1109/access.2020.3013250. [21] Bellizia, et al., Post-Quantum Cryptography: Challenges and Opportunities for Robust and Secure HW Design, IEEE International Symposium on Defect and fault tolerance in VLSI and Nanotechnology systems (DFT) (2021) 1–6. doi: 10.1109/DFT52944.2021.9568301. [22] L. Chen, et al., Report on Post-Quantum Cryptography, NIST Publications (2016). doi: 10.6028/NIST.IR.8105. [23] G. Alagic, et al., Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process, NIST Publications (2020). doi: 10.6028/NIST.IR.8309. 219