Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Information and Communication Technology Convergence (ICTC)

Rethinking on Ciphertext Equality Check of Decapsulation of NIST PQC Standardization 3rd Round Finalist Candidate Saber

Donghoon Lee, Eun-Young Seo, Young-Sik Kim, Jong‐Seon No

Published Oct 19, 2022• 2 citations
Publisher

Abstract

In this paper, we rethink the ciphertext equality check step of the decapsulation procedure of Saber, which is one out of four KEM finalists in the third round NIST PQC standardization process. Through this investigation, we pursue cryptographic answers to some important questions. Those are why the re-encryption process of Fujisaki-Okamoto transformation, which is commonly used method to satisfy IND-CCA security in most existing lattice-based KEM algorithms including Saber, is especially necessary in the case of Saber, whether the re-encryption process can be further simplified, and whether the ciphertext equality check must be performed over the entire (re-encrypted/originally received) ciphertexts?

DOI
10.1109/ictc55196.2022.9952361

Related papers

Analysis of the FO Transformation in the Lattice-Based Post-Quantum Algorithms

Miguel Ángel González de la Torre, Luis Hernández Encinas, Araceli Queiruga‐Dios

Newer variants of the Fujisaki–Okamoto transformation are used in most candidates of the third round of the NIST Post-Quantum Cryptography standardization call in the category of public key encryption schemes. These transformations are applied to obtain a highly secure key encapsulation mechanism from a less secure public key encryption scheme. Furthermore, there are five candidates (three finalists and two alternatives) that passed to the third round of the process and whose security is based in lattice problems. This work analyzes the different ways in which the lattice-based candidates of the NIST call apply the Fujisaki–Okamoto transformation and the particularities of each application. The study of such differences and their repercussion in the design of the proposals will allow a better understanding of the algorithms. Moreover, we propose a modification of the Kyber algorithm—the only public key encryption candidate established as a PQC standard by NIST in its more recent publication—in order to avoid the re-encryption in the decapsulation algorithm and, in this way, to reduce the side channel attacks vulnerability.

Mathematics•Aug 17, 2022•2 citations

Error Term Checking: Towards Chosen Ciphertext Security without Re-encryption

Jan-Pieter D’Anvers, Emmanuela Orsini, Fréderik Vercauteren

Chosen ciphertext security for lattice based encryption schemes is generally achieved through a generic transformation such as the Fujisaki-Okamoto transformation. This method requires full re-encryption of the plaintext during decapsulation, which typically dominates the cost of the latter procedure. In this work we show that it is possible to develop alternative transformations specifically designed for lattice based encryption schemes. We propose two novel chosen ciphertext transformations, ETC1 and ETC2, in which re-encryption is replaced by checking the error term of the input ciphertext. We show that our new ciphertext validity check can be securely applied to lattice based encryption schemes under specific conditions. For the NIST post-quantum standardization candidate Threebears we show a speed-up for decapsulation of up to 37.4%. Moreover, as our method only changes the validation check during decapsulation, it is fully backwards compatible with existing implementations of the Fujisaki-Okamoto transformation.

ACM ASIA Public-Key Cryptography Workshop (APKC)•May 24, 2021•3 citations

On the applicability of the Fujisaki–Okamoto transformation to the BIKE KEM

Nir Drucker, Shay Gueron, Dušan Kostić +1 more

The QC-MDPC code-based KEM BIKE is one of the Round-3 candidates of the NIST PQC standardization project. Its Round-2 specification document described variants claiming to have IND-CCA security. The security proof used the Fujisaki–Okamoto transformation and a decoder targeting a Decoding Failure Rate (DFR) of 2−128 (for Level-1 security). However, several aspects needed to be amended in order for the IND-CCA proof to hold. The main issue is that using a decoder with DFR of 2−128 does not necessarily imply that the underlying PKE is δ-correct with δ=2−128, as required. In this paper, we handle the necessary aspects to ensure the security claim is correct. In particular, we close the gap in the proof by defining the notion of message-agnostic PKE. We show that the PKEs underlying the BIKE versions are message-agnostic. This implies that BIKE with a decoder that has a sufficiently low DFR is also an IND-CCA KEM.

International Journal of Computer Mathematics Computer Systems Theory•May 14, 2021•19 citations

Enhancing Post-Quantum KEMs: A Secure and Efficient Transformation

Sai Charan Reddy Nevuri

This paper proposes a new generic Encrypt-thenMAC (EtM) transformation for constructing IND-CCA secure Key Encapsulation Mechanisms (KEMs) in the post-quantum setting. The transformation builds on a public-key encryption scheme satisfying one-wayness under plaintext-checking attacks (OW-PCA) and an existentially unforgeable MAC, and formally achieves tight IND-CCA security in the random oracle model via a rigorous security reduction. Unlike the widely used FujisakiOkamoto (FO) transformation, our approach eliminates the need for ciphertext re-encryption during decapsulation-a major source of computational overhead and side-channel vulnerability in lattice-based implementations. We instantiate the transformation using the ML-KEM (FIPS 203) subroutine, yielding the ML-KEM-EtM variant. Experimental results show that ML-KEMEtM reduces decapsulation cycle counts by$72-79 {\%}$across security levels, with only a modest increase in encapsulation cost$(1.8-7.3 {\%})$and ciphertext size$(1.0-2.1 {\%})$. The scheme thus offers a practical and efficient a lternative to F O-based KEMs, especially in performance-critical scenarios such as post-quantum TLS handshakes, where decapsulation efficiency is paramount.

International Symposium on Digital Forensics and Security (ISDFS)•Mar 19, 2026•0 citations

On the Security and Efficiency of TLS 1.3 Handshake with Hybrid Key Exchange from CPA-Secure KEMs

Jinrong Chen, Wei Peng, Yi Wang +1 more

TLS 1.3 is a crucial protocol for securing modern internet communications. To facilitate a smooth transition to post-quantum security, hybrid key exchange, which combines classical key exchange algorithms with post-quantum key encapsulation mechanisms (KEMs), is proposed to enhance the security of the current TLS 1.3 handshake. However, existing drafts and implementations of hybrid key exchange for TLS 1.3 primarily rely on CCA-secure KEMs (i.e., secure against chosen-ciphertext attacks) based on the Fujisaki-Okamoto (FO) transform. The re-encryption step in their decapsulation algorithms not only introduces additional performance overhead but also raises the risk of side-channel attacks. Although Huguenin-Dumittan and Vaudenay (Eurocrypt 2022) and Zhou et al. (Asiacrypt 2024) demonstrated that the weaker CPA-secure KEMs (i.e., secure against chosen-plaintext attacks) suffice for constructing a secure TLS 1.3 handshake, their analyses were limited to single-KEM settings and did not consider the hybrid key exchange scenario. This work challenges the necessity of CCA security by proving that CPA-secure KEMs are sufficient for the TLS 1.3 handshake even in the hybrid key exchange setting. We provide the first formal security proofs for this claim, covering both the classical random oracle model (ROM) and the quantum random oracle model (QROM), thereby ensuring security against quantum adversaries. To validate the practical benefits, we conduct an extensive performance evaluation based on the latest OpenSSL implementation. Our results show that using CPA-secure KEMs yields up to 44.8% performance improvement at the key exchange layer and up to approximately 9% acceleration for the full TLS 1.3 handshake. Beyond performance gains, this approach reduces the codebase's attack surface by eliminating the re-encryption step, thereby mitigating a class of side-channel vulnerabilities. Our work positions CPA-secure KEMs as a secure, efficient, and practical alternative for standardizing and deploying post-quantum TLS 1.3 even with hybrid key exchange.

Entropy•Dec 8, 2025•6 citations

Faster Lattice-Based KEMs via a Generic Fujisaki-Okamoto Transform Using Prefix Hashing

Julien Duman, Kathrin Hövelmanns, Eike Kiltz +2 more

Constructing an efficient CCA-secure KEM is generally done by first constructing a passively-secure PKE scheme, and then applying the Fujisaki-Okamoto (FO) transformation. The original FO transformation was designed to offer security in a single user setting. A stronger notion, known as multi-user security, considers the attacker's advantage in breaking one of many user's ciphertexts. Bellare et al. (EUROCRYPT 2000) showed that standard single user security implies multi-user security with a multiplicative tightness gap equivalent to the number of users.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2021•33 citations
In this paper, we rethink the ciphertext equality check step of the decapsulation procedure of Saber, which is one out of four KEM finalists in the third round NIST PQC standardization process. Through this investigation, we pursue cryptographic answers to some important questions. Those are why the re-encryption process of Fujisaki-Okamoto transformation, which is commonly used method to satisfy IND-CCA security in most existing lattice-based KEM algorithms including Saber, is especially necessary in the case of Saber, whether the re-encryption process can be further simplified, and whether the ciphertext equality check must be performed over the entire (re-encrypted/originally received) ciphertexts?
Newer variants of the Fujisaki–Okamoto transformation are used in most candidates of the third round of the NIST Post-Quantum Cryptography standardization call in the category of public key encryption schemes. These transformations are applied to obtain a highly secure key encapsulation mechanism from a less secure public key encryption scheme. Furthermore, there are five candidates (three finalists and two alternatives) that passed to the third round of the process and whose security is based in lattice problems. This work analyzes the different ways in which the lattice-based candidates of the NIST call apply the Fujisaki–Okamoto transformation and the particularities of each application. The study of such differences and their repercussion in the design of the proposals will allow a better understanding of the algorithms. Moreover, we propose a modification of the Kyber algorithm—the only public key encryption candidate established as a PQC standard by NIST in its more recent publication—in order to avoid the re-encryption in the decapsulation algorithm and, in this way, to reduce the side channel attacks vulnerability.
Chosen ciphertext security for lattice based encryption schemes is generally achieved through a generic transformation such as the Fujisaki-Okamoto transformation. This method requires full re-encryption of the plaintext during decapsulation, which typically dominates the cost of the latter procedure. In this work we show that it is possible to develop alternative transformations specifically designed for lattice based encryption schemes. We propose two novel chosen ciphertext transformations, ETC1 and ETC2, in which re-encryption is replaced by checking the error term of the input ciphertext. We show that our new ciphertext validity check can be securely applied to lattice based encryption schemes under specific conditions. For the NIST post-quantum standardization candidate Threebears we show a speed-up for decapsulation of up to 37.4%. Moreover, as our method only changes the validation check during decapsulation, it is fully backwards compatible with existing implementations of the Fujisaki-Okamoto transformation.
The QC-MDPC code-based KEM BIKE is one of the Round-3 candidates of the NIST PQC standardization project. Its Round-2 specification document described variants claiming to have IND-CCA security. The security proof used the Fujisaki–Okamoto transformation and a decoder targeting a Decoding Failure Rate (DFR) of 2−128 (for Level-1 security). However, several aspects needed to be amended in order for the IND-CCA proof to hold. The main issue is that using a decoder with DFR of 2−128 does not necessarily imply that the underlying PKE is δ-correct with δ=2−128, as required. In this paper, we handle the necessary aspects to ensure the security claim is correct. In particular, we close the gap in the proof by defining the notion of message-agnostic PKE. We show that the PKEs underlying the BIKE versions are message-agnostic. This implies that BIKE with a decoder that has a sufficiently low DFR is also an IND-CCA KEM.
This paper proposes a new generic Encrypt-thenMAC (EtM) transformation for constructing IND-CCA secure Key Encapsulation Mechanisms (KEMs) in the post-quantum setting. The transformation builds on a public-key encryption scheme satisfying one-wayness under plaintext-checking attacks (OW-PCA) and an existentially unforgeable MAC, and formally achieves tight IND-CCA security in the random oracle model via a rigorous security reduction. Unlike the widely used FujisakiOkamoto (FO) transformation, our approach eliminates the need for ciphertext re-encryption during decapsulation-a major source of computational overhead and side-channel vulnerability in lattice-based implementations. We instantiate the transformation using the ML-KEM (FIPS 203) subroutine, yielding the ML-KEM-EtM variant. Experimental results show that ML-KEMEtM reduces decapsulation cycle counts by72−79%72-79 {\%}72−79%across security levels, with only a modest increase in encapsulation cost(1.8−7.3%)(1.8-7.3 {\%})(1.8−7.3%)and ciphertext size(1.0−2.1%)(1.0-2.1 {\%})(1.0−2.1%). The scheme thus offers a practical and efficient a lternative to F O-based KEMs, especially in performance-critical scenarios such as post-quantum TLS handshakes, where decapsulation efficiency is paramount.
TLS 1.3 is a crucial protocol for securing modern internet communications. To facilitate a smooth transition to post-quantum security, hybrid key exchange, which combines classical key exchange algorithms with post-quantum key encapsulation mechanisms (KEMs), is proposed to enhance the security of the current TLS 1.3 handshake. However, existing drafts and implementations of hybrid key exchange for TLS 1.3 primarily rely on CCA-secure KEMs (i.e., secure against chosen-ciphertext attacks) based on the Fujisaki-Okamoto (FO) transform. The re-encryption step in their decapsulation algorithms not only introduces additional performance overhead but also raises the risk of side-channel attacks. Although Huguenin-Dumittan and Vaudenay (Eurocrypt 2022) and Zhou et al. (Asiacrypt 2024) demonstrated that the weaker CPA-secure KEMs (i.e., secure against chosen-plaintext attacks) suffice for constructing a secure TLS 1.3 handshake, their analyses were limited to single-KEM settings and did not consider the hybrid key exchange scenario. This work challenges the necessity of CCA security by proving that CPA-secure KEMs are sufficient for the TLS 1.3 handshake even in the hybrid key exchange setting. We provide the first formal security proofs for this claim, covering both the classical random oracle model (ROM) and the quantum random oracle model (QROM), thereby ensuring security against quantum adversaries. To validate the practical benefits, we conduct an extensive performance evaluation based on the latest OpenSSL implementation. Our results show that using CPA-secure KEMs yields up to 44.8% performance improvement at the key exchange layer and up to approximately 9% acceleration for the full TLS 1.3 handshake. Beyond performance gains, this approach reduces the codebase's attack surface by eliminating the re-encryption step, thereby mitigating a class of side-channel vulnerabilities. Our work positions CPA-secure KEMs as a secure, efficient, and practical alternative for standardizing and deploying post-quantum TLS 1.3 even with hybrid key exchange.
Constructing an efficient CCA-secure KEM is generally done by first constructing a passively-secure PKE scheme, and then applying the Fujisaki-Okamoto (FO) transformation. The original FO transformation was designed to offer security in a single user setting. A stronger notion, known as multi-user security, considers the attacker's advantage in breaking one of many user's ciphertexts. Bellare et al. (EUROCRYPT 2000) showed that standard single user security implies multi-user security with a multiplicative tightness gap equivalent to the number of users.