Abstract:

This work examines the Fujisaki–Okamoto (FO) transform, the standard technique for upgrading a public key encryption scheme secure only against chosen plaintext attacks to one achieving full chosen ciphertext security (CCA2). The FO transform has been central to the design of key encapsulation mechanisms in the NIST Post Quantum Cryptography competition, and its security has been established in the classical Random Oracle Model (ROM). A crucial challenge arises in the post quantum setting, since the ROM differs fundamentally from the Quantum Random Oracle Model (QROM), where adversaries can issue superposition queries. This subtle distinction, often overlooked outside a narrow circle of experts, calls into question the validity of classical proofs when extended to quantum capable adversaries. Our study addresses this gap by analyzing the FO transform explicitly within the QROM framework. On the practical side, we implement and evaluate two variants of the CRYSTALS-Kyber scheme: the CPA secure encryption scheme and the CCA secure key encapsulation mechanism derived via the FO transform. The experiments demonstrate that while the transform introduces negligible overhead in key generation and encapsulation, it substantially increases the cost of decapsulation due to the additional re encryption step. These results highlight the trade off between achieving strong CCA2 security and maintaining efficiency. As future work, we aim to explore refinements of CRYSTALS-Kyber that achieve full compatibility with the QROM, thereby contributing to the development of encryption schemes that combine rigorous post quantum security with practical performance.