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 Symposium on Electronic Commerce and Security

Applying the Fujisaki-Okamoto Conversion to Certificate-based Encryption

Yang Lu, Jiguo Li, Junmo Xiao

Published Jan 1, 2008• 10 citations
Publisher

Abstract

The Fujisaki-Okamoto (FO) conversion is a generic conversion to enhance a public key encryption scheme with security of one-way against chosen plaintext attacks (OW-CPA) to security of indistinguishable against adaptive chosen ciphertext attacks (IND-CCA) in the random oracle model. Existing works have shown that the FO conversion also can generically upgrade the security of the identity-based encryption (IBE) schemes or certificateless public key encryption (CL-PKE) schemes. However, it is still unknown if the same holds for certificate-based encryption (CBE) schemes. In this paper, we investigate the generic security of the CBE scheme obtained by applying the FO conversion to an arbitrary underlying OW-CBE-CPA secure CBE scheme and confirm that the FO conversion can generically convert any OW-CBE-CPA secure CBE into an IND-CBE-CCA secure CBE. We also note that the straightforward application of the FO conversion only leads to a CBE scheme with a loose reduction. To solve this problem, we propose an enhanced FO conversion which just introduces minor extra computation overhead, but results in considerably more efficient security reduction.

DOI
10.1109/isecs.2008.61

Related papers

Strong Multiple-CCA Security in the Quantum Random Oracle Model for an FO-like PKE Combiner

Tudor Soroceanu, Nicolas Buchmann, Theresa Graeber +1 more

Combiners for cryptographic schemes are a common way to increase security using redundancy. The security notions for public key encryption (PKE) combiners can be extended beyond the standard IND-CCA security to achieve even stronger security notions. In the indistinguishability under adaptive strong multiple chosen-ciphertext attack (IND-sMCCA) security notion, the adversary has additional oracle access to the underlying cipher components of the combiner. Recently, combiners have received more attention because of the possibility of combining classical and post-quantum (PQ) cryptography. This allows for the use of novel PQ algorithms while still having the security guarantees of the classical algorithms. In order to examine the security against quantum adversaries, the quantum random oracle model (QROM) has become the most relevant security model. However, there are no PKE combiners that achieve IND-sMCCA security in the QROM, even though this security notion describes much better the current state where classical, PQ, and combined schemes are deployed at the same time. In this paper, we close this gap by providing a new PKE combiner that is IND-sMCCA secure in the QROM. Our construction is more efficient and lean than the existing PKE combiners, considering the primitives used and the ciphertext size. We accomplish this by applying the Fujisaki-Okamoto (FO) transformation to a PKE combiner of Asmuth and Blakley. To achieve IND-sMCCA security for the combiner, the PKE components must be OW-CCA secure. However, when using weaker (OW-CPA secure) PKE components, we still achieve standard IND-CCA security for the combiner. The security reductions are given in the ROM and the QROM, achieving bounds of different tightness.

IACR Communications in Cryptology•Oct 6, 2025•1 citation

On the Anonymity of Multi-Receiver Identity-Based Encryption Based on Fujisaki–Okamoto Transformation

Yi‐Fan Tseng, Chun‐I Fan, Cheng-Wei Sung

In 2010, Fan et al. first introduced the concept of anonymous multi-receiver identity-based encryption (AMRIBE). They used the concept of Fujisaki–Okamoto transformation (F.O. transformation) to support their proof in random oracle models. Recently, many works on this topic have been proposed. Most of them adopted Fujisaki–Okamoto transformation to achieve the indistinguishability of encryptions under multi-ID, chosen-ciphertext attacks (IND-MID-CCA) security. However, we find out that these schemes do not gain anonymity against insider attacks. In this manuscript, we use a sequence of games to prove that any AMRIBE scheme will fail to gain anonymity under chosen-ciphertext attacks and chosen-plaintext attacks if the IND-MID-CCA security is proven using Fujisaki–Okamoto transformation.

International Journal of Foundations of Computer Science•Jun 1, 2019•0 citations

Efficient Generic Construction of CCA-Secure Identity-Based Encryption from Randomness Extraction

Joonsang Baek, Duncan S. Wong, Jin Li +1 more

We propose a generic construction that yields efficient identity-based encryption (IBE) schemes secure against chosen ciphertext attack (CCA) in the standard model. Our construction extends Kiltz et al.'s (Eurocrypt '09) method of constructing CCA-secure public-key encryption schemes via randomness extraction to the identity-based setting. The main idea of our construction is to transform ‘|$\epsilon _1$|-almost |$\kappa $|-entropic’ and valid/invalid ciphertext indistinguishable (VI-IND) identity-based hash proof system to the one that satisfies the stronger ‘|$\epsilon _2$|-universal’ and VI-IND property. This transformation is realized by a randomness extractor based on the 4-wise hash function. We demonstrate that our generic construction can produce CCA-secure IBE schemes whose efficiency is comparable with the most efficient but non-generic CCA-secure IBE schemes without random oracles in the literature.

The Computer Journal•Sep 3, 2015•4 citations

On the application of generic CCA‐secure transformations to proxy re‐encryption

David Núñez, Isaac Agudo, Javier López

Abstract Several generic methods exist for achieving chosen‐ciphertext attack (CCA)‐secure public‐key encryption schemes from weakly secure cryptosystems, such as the Fujisaki–Okamoto and REACT transformations. In the context of proxy re‐encryption (PRE), it would be desirable to count on analogous constructions that allow PRE schemes to achieve better security notions. In this paper, we study the adaptation of these transformations to proxy re‐encryption and find both negative and positive results. On the one hand, we show why it is not possible to directly integrate these transformations with weakly secure PRE schemes because of general obstacles coming from both the constructions themselves and the security models, and we identify 12 PRE schemes that exhibit these problems. On the other hand, we propose an extension of the Fujisaki–Okamoto transformation for PRE, which achieves a weak form of CCA security in the random oracle model, and we describe the sufficient conditions for applying it. Copyright © 2016 John Wiley & Sons, Ltd.

Security and Communication Networks•Feb 19, 2016•8 citations

Anonymous Identity Based Encryption with Plaintext Awareness in the Two Identities Setting

C. LIN, Yong Li, Qingqing Zhang +1 more

An anonymous identity based encryption (anonymous IBE) scheme requires that an adversary can not determine the identity of the recipient from a ciphertext encrypted by the corresponding public key. The anonymity was formalized in previous works [1], [13], and this can be considered under chosen plaintext attack and adaptive chosen ciphertext attack, yielding two notions of security, ID-II-CPA and ID-II-CCA, where II denotes “indistinguishability of identities.” However, how to obtain an ID-II-CCA secure anonymous IBE in the random oracle model is still a challenging problem. We firstly propose a new notion of plaintext awareness in the two identities setting, called PATI. Secondly, we prove that the IBE scheme is ID-II-CCA secure if it is PATI secure. Finally, we propose the first generic conversion for anonymous IBE from ID-II-CPA to ID-II-CCA in the random oracle model.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Dec 1, 2008•0 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
The Fujisaki-Okamoto (FO) conversion is a generic conversion to enhance a public key encryption scheme with security of one-way against chosen plaintext attacks (OW-CPA) to security of indistinguishable against adaptive chosen ciphertext attacks (IND-CCA) in the random oracle model. Existing works have shown that the FO conversion also can generically upgrade the security of the identity-based encryption (IBE) schemes or certificateless public key encryption (CL-PKE) schemes. However, it is still unknown if the same holds for certificate-based encryption (CBE) schemes. In this paper, we investigate the generic security of the CBE scheme obtained by applying the FO conversion to an arbitrary underlying OW-CBE-CPA secure CBE scheme and confirm that the FO conversion can generically convert any OW-CBE-CPA secure CBE into an IND-CBE-CCA secure CBE. We also note that the straightforward application of the FO conversion only leads to a CBE scheme with a loose reduction. To solve this problem, we propose an enhanced FO conversion which just introduces minor extra computation overhead, but results in considerably more efficient security reduction.
Combiners for cryptographic schemes are a common way to increase security using redundancy. The security notions for public key encryption (PKE) combiners can be extended beyond the standard IND-CCA security to achieve even stronger security notions. In the indistinguishability under adaptive strong multiple chosen-ciphertext attack (IND-sMCCA) security notion, the adversary has additional oracle access to the underlying cipher components of the combiner. Recently, combiners have received more attention because of the possibility of combining classical and post-quantum (PQ) cryptography. This allows for the use of novel PQ algorithms while still having the security guarantees of the classical algorithms. In order to examine the security against quantum adversaries, the quantum random oracle model (QROM) has become the most relevant security model. However, there are no PKE combiners that achieve IND-sMCCA security in the QROM, even though this security notion describes much better the current state where classical, PQ, and combined schemes are deployed at the same time. In this paper, we close this gap by providing a new PKE combiner that is IND-sMCCA secure in the QROM. Our construction is more efficient and lean than the existing PKE combiners, considering the primitives used and the ciphertext size. We accomplish this by applying the Fujisaki-Okamoto (FO) transformation to a PKE combiner of Asmuth and Blakley. To achieve IND-sMCCA security for the combiner, the PKE components must be OW-CCA secure. However, when using weaker (OW-CPA secure) PKE components, we still achieve standard IND-CCA security for the combiner. The security reductions are given in the ROM and the QROM, achieving bounds of different tightness.
In 2010, Fan et al. first introduced the concept of anonymous multi-receiver identity-based encryption (AMRIBE). They used the concept of Fujisaki–Okamoto transformation (F.O. transformation) to support their proof in random oracle models. Recently, many works on this topic have been proposed. Most of them adopted Fujisaki–Okamoto transformation to achieve the indistinguishability of encryptions under multi-ID, chosen-ciphertext attacks (IND-MID-CCA) security. However, we find out that these schemes do not gain anonymity against insider attacks. In this manuscript, we use a sequence of games to prove that any AMRIBE scheme will fail to gain anonymity under chosen-ciphertext attacks and chosen-plaintext attacks if the IND-MID-CCA security is proven using Fujisaki–Okamoto transformation.
We propose a generic construction that yields efficient identity-based encryption (IBE) schemes secure against chosen ciphertext attack (CCA) in the standard model. Our construction extends Kiltz et al.'s (Eurocrypt '09) method of constructing CCA-secure public-key encryption schemes via randomness extraction to the identity-based setting. The main idea of our construction is to transform ‘|ϵ1\epsilon _1ϵ1​|-almost |$\kappa ∣−entropic’andvalid/invalidciphertextindistinguishable(VI−IND)identity−basedhashproofsystemtotheonethatsatisfiesthestronger‘∣|-entropic’ and valid/invalid ciphertext indistinguishable (VI-IND) identity-based hash proof system to the one that satisfies the stronger ‘|∣−entropic’andvalid/invalidciphertextindistinguishable(VI−IND)identity−basedhashproofsystemtotheonethatsatisfiesthestronger‘∣\epsilon _2$|-universal’ and VI-IND property. This transformation is realized by a randomness extractor based on the 4-wise hash function. We demonstrate that our generic construction can produce CCA-secure IBE schemes whose efficiency is comparable with the most efficient but non-generic CCA-secure IBE schemes without random oracles in the literature.
Abstract Several generic methods exist for achieving chosen‐ciphertext attack (CCA)‐secure public‐key encryption schemes from weakly secure cryptosystems, such as the Fujisaki–Okamoto and REACT transformations. In the context of proxy re‐encryption (PRE), it would be desirable to count on analogous constructions that allow PRE schemes to achieve better security notions. In this paper, we study the adaptation of these transformations to proxy re‐encryption and find both negative and positive results. On the one hand, we show why it is not possible to directly integrate these transformations with weakly secure PRE schemes because of general obstacles coming from both the constructions themselves and the security models, and we identify 12 PRE schemes that exhibit these problems. On the other hand, we propose an extension of the Fujisaki–Okamoto transformation for PRE, which achieves a weak form of CCA security in the random oracle model, and we describe the sufficient conditions for applying it. Copyright © 2016 John Wiley & Sons, Ltd.
An anonymous identity based encryption (anonymous IBE) scheme requires that an adversary can not determine the identity of the recipient from a ciphertext encrypted by the corresponding public key. The anonymity was formalized in previous works [1], [13], and this can be considered under chosen plaintext attack and adaptive chosen ciphertext attack, yielding two notions of security, ID-II-CPA and ID-II-CCA, where II denotes “indistinguishability of identities.” However, how to obtain an ID-II-CCA secure anonymous IBE in the random oracle model is still a challenging problem. We firstly propose a new notion of plaintext awareness in the two identities setting, called PATI. Secondly, we prove that the IBE scheme is ID-II-CCA secure if it is PATI secure. Finally, we propose the first generic conversion for anonymous IBE from ID-II-CPA to ID-II-CCA in the random oracle model.
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.