Computers, Materials & Continua DOI:10.32604/cmc.2022.026751  
Article 
ChosenCiphertext Attack Secure PublicKey Encryption with Keyword Search
Samsung Electronics Co. Ltd., Suwonsi, 16677, Korea
*Corresponding Author: Hyun Sook Rhee. Email: hyunsook.rhee@gmail.com
Received: 04 January 2022; Accepted: 02 March 2022
Abstract: As the use of cloud storage for various services increases, the amount of private personal information along with data stored in the cloud storage is also increasing. To remotely use the data stored on the cloud storage, the data to be stored needs to be encrypted for this reason. Since “searchable encryption” is enable to search on the encrypted data without any decryption, it is one of convenient solutions for secure data management. A public key encryption with keyword search (for short, PEKS) is one of searchable encryptions. Abdalla et al. firstly defined INDCCA security for PEKS to enhance it’s security and proposed consistent INDCCA secure PEKS based on the “robust” ANOCCA secure identitybased encryption(IBE). In this paper, we propose two generic constructions of consistent INDCCA secure PEKS combining (1) a hierarchical identity based encryption (for short, HIBE) and a signature scheme or (2) a HIBE, an encapsulation, and a message authentication code (for short, MAC) scheme. Our generic constructions identify that HIBE requires the security of a signature or a MAC as well as the weaker “ANOCPA security (resp., INDCPA security)” of HIBE than “ANOCCA security (resp., INDCCA security)” of IBE required in for achieving INDCCA secure (resp., consistent) PEKS. Finally, we prove that our generic constructions satisfy INDCCA security and consistency under the security models.
Keywords: Searchable encryption; publickey encryption with keyword search; chosen ciphertext security; data privacy
As various services are transferred into the cloud environment, the safe management of information stored on the cloud storage is one of the important issues. Countries have enacted legislation to reduce the damage caused by exposure to privacy of their own citizens through personal information protection laws such as GDPR(General Data Protection Regulation) [1] and LGPD(Brazilian General Data Protection Law) [2] etc. The laws mandate that personal information be encrypted when stored or transmitted. Searchable encryption is a very useful primitive for providing the functionality of “searching on encrypted data”. Recently, there has been intensive interest in searchable encryption [3–14]. As a variant of searchable encryption on a storeandforward system, the notion of publickey encryption with keyword search (PEKS) was suggested by Boneh et al. [15]. Informally, a PEKS scheme enables an email server to correctly test whether or not a given keyword is present in an encrypted email without revealing any information on the email. In PEKS, the sender generates a PEKS ciphertext
As security of public key encryption, INDCPA (indistinguishability under a chosen plaintext attack) requires that it should be infeasible for an adversary to compute any information on a plaintext when given its ciphertext and the corresponding public key [16]. In PEKS, a keyword is a plaintext. The security condition of a PEKS system [15] requires that an adversary (or the server) runs the test function with the inputs,
Abdalla et al. [3,15] showed that an INDCPA PEKS scheme can be constructed from an ANOCPA (anonymity under chosen plaintext attack) identitybased encryption (IBE) scheme and that a consistent PEKS scheme can be constructed from an INDCPA IBE scheme. Here, “an IBE scheme is anonymous” means that the ciphertext does not reveal the identity of the intended recipient. In PKE, the notion of INDCPA security only considers an adversary that may choose plaintexts of its choice and generate the corresponding ciphertexts. INDCPA security does not guarantee indistinguishability under a chosen ciphertext attack (INDCCA security), where an adversary can choose ciphertexts of its choice and obtain the corresponding plaintexts. It has been shown that chosen ciphertext attacks are practical [17–19] and INDCCA security is considered as the minimum level of security for a encryption scheme to be deployed in practice.
The goal of this paper is to design a consistent INDCCA secure PEKS scheme. An INDCCA secure PEKS scheme in a random oracle can be easily derived from the decryptable searchable encryption proposed by Fuhr et al. [20]. However, this approach does not guarantee consistency of the result. In PKE(public key encryption) & PEKS schemes [4,8,12,14], INCCCA security had been considered. Strictly speaking, ‘‘ciphertext of a message” instead of ‘‘PEKS chiphertext of a keyword” is the target of the INDCCA security. However, when data is stored in real environments such as the cloud storage, it is encrypted using symmetric key encryption such as AES(Advanced Encryption Standard). Hence, applying an encryption of data with a PKE is bound to be limited.
Meanwhile, analogously to the result in [3,15], an INDCCA PEKS scheme can be directly constructed from an ANOCCA secure IBE scheme. In taking this approach, Abdalla et al. [4] identified that “robustness” is the property necessary for a consistency in the resulting PEKS scheme. Here, “robustness” means the difficulty of producing a ciphertext valid under two different encryption keys. They mentioned “BonehFlanklin IBE scheme [21]” as satisfying both “robustness” and “ANOCCA security” among the IBE schemes [4]. Compared to the result of Abdalla et al. in Tab. 1, our main contribution is enable to construct consistent INDCCA secure PEKS scheme by using the underlying schemes which satisfy the weaker security (ANOCPA security) than ANOCCA security. Also, since general constructions can be developed using proven safety primitives codes, the generic constructions to solve new security issues can be applied immediately in the development environment to speed up application time. So, proposing various general constructions using different primitives (such as a publickey encryption (for short, PKE), a signature, a MAC, and a hash etc) will maximize utilization in real life.
In this paper, for alternatives for providing the consistent INDCCA secure PEKS, we propose two generic constructions: For INDCCA security of PEKS, one is based on any ANOCPA secure twolevel hierarchical IBE (HIBE) and a strong onetime signature, and the other is based on ANOCPA secure twolevel HIBE, a secure encapsulation, and a strong onetime MAC. For consistency of PEKS, one is based on any INDCPA secure twolevel HIBE and an existential unforgeable signature and the other is based on any INDCPA secure twolevel HIBE and a computational binding encapsulation.
INDCCA security of PEKS. In chosen plaintext attack of PEKS, an adversary is given access to a trapdoor oracle. An adversary can chose a keyword w of its own and obtain the trapdoor Tw of w quering the trapdoor oracle. The adversary then can test whether or not w is present in a given PEKS ciphertext CT by running a test function with inputs CT and Tw. In chosen ciphertext attack of PEKS, an adversarial model is strengthened so that it can freely chose a PEKS ciphetext CT and is given access to a test oracle. The test oracle takes as inputs a PEKS ciphertext CT and a keyword w and outputs the test result whether or not CT is an encryption of w. The INDCCA of PEKS requires that for given two keywords
We note that (
Consistency of PEKS. In [3], it was shown that the confidentiality (INDCPA security) of the IBE scheme is sufficient for the computational consistency of a CPA secure PEKS scheme. (Computational consistency means that it is hard for any polynomialtime adversary to find distinct keywords w and w′ such that the result of the test function with
Paper Organization. The remainder of this paper is organized as follows. We review several primitives that are necessary for our constructions, such as the HIBE, Signature and MAC schemes in Section 2. In Section 3, we review the notions “IDNCPA security” and “consistency” in a PEKS scheme and propose two generic constructions of a PEKS scheme and add the flowchat of PEKS encryption process to help understand. In Section 4, we establish the security and computational consistency of our two generic constructions for a PEKS scheme. Finally, Section 5 concludes the paper.
We review the notation and recall the definitions of a hierarchical identitybased encryption (HIBE) scheme, a strong onetime signature scheme and a secure message authentication code. We also review the concepts of security and anonymity for HIBE schemes.
Notation : For any string x, x denotes its length. For any set
2.1 Hierarchical IdentityBased Encryption
A hierarchical identitybased encryption (HIBE) scheme is an extension of an IBE scheme [9,22] in which an identity is a vector of strings
Definition 2.1. A ℓlevel hierarchical identitybased encryption (HIBE) scheme HIBE = (
•
•
•
•
•
where the probability is taken over the coins of
Confidentiality and Anonymity of HIBE : Suppose that HIBE = (
The confidentiality (HIBEINDCPA) and anonymity (HIBEANOCPA) of the HIBE scheme against adaptive chosenplaintext attacks, which is defined using the following experiments as shown in Tabs. 2 and 3, follows [3,23]. We say that
We also say that
Definition 2.2. We say that a HIBE scheme HIBE is HIBEINDCPA secure (resp., HIBEANOCPA secure) if the advantage
We recall the standard functional definition for signature schemes and the definition for strong onetime security that is appropriate for signature schemes.
Definition 2.3. A signature scheme
•
•
•
We require that
Security of Signature Schemes: The securities (strong unforgeability or existential unforgeability) for signature schemes [24] are defined using the above experiments in Tab. 4. We define the advantages of
Definition 2.4. We say that a signature scheme Sig is a strong onetime signature (resp., existential unforgeable onetime signature) if for any PPT adversary
We review encapsulation schemes which may be viewed as weak variants of commitment, and the security notions of encapsulation schemes [24].
Definition 2.5. An encapsulation scheme
•
•
We refer to
•
We require that for all
Security of Encapsulation Schemes : The security notions of binding and hiding in an encapsulation scheme [24] are defined using the above experiment in Tab. 5. We define the advantages of
Definition 2.6. We say that an encapsulation scheme Encap is secure if for any PPT adversary
2.4 Message Authentication Code Scheme
We review a definition for message authentication codes and a definition for strong unforgeability that is appropriate for message authentication codes.
Definition 2.7. A message authentication code (MAC) scheme
•
•
We require that for all sk ∈ {0, 1}k, all M ∈ M, and all tag
Security of Message Authentication Codes : The security (strong unforgeability) for MAC [24] is defined using the above experiment in Tab. 6. We define the advantage of
Definition 2.8. We say that a message authentication code scheme
We review a definition of public key encryption with keyword search (PEKS) suggested by Boneh et al. [15], the definitions of the security against chosenciphertext attacks (PEKSINDCCA) and the consistency in PEKS.
Definition 2.9. A PEKS scheme
•
•
•
•
Confidentiality(INDCCA security) of PEKS: The INDCCA security for PEKS is defined using the experiment in Tab. 7. We define the advantage of
where the probability is taken over all possible coin flips of all the algorithms involved.
Definition 2.10. We say that a PEKS scheme is semantically secure against an adaptive chosen ciphertext attack (PEKSINDCCA secure) if for any PPT adversary ,
Consistency of PEKS: In [3], Abdalla et al. identified the concept of the consistency of PEKS schemes and defined computational and statistical relaxations of the notion of perfect consistency. They showed that Boneh et al.’s PEKS scheme is computationally consistent. Suppose there is an adversary
where the probability is taken over all possible coin flips of all the algorithms involved.
Definition 2.11. We say that a PEKS scheme is “perfectly consistent” if the advantage is 0 for all (computationally unrestricted) adversaries
3 Generic Construction of PEKS Scheme
In this Section, we provide two generic constructions of a consistent INDCCA secure PEKS scheme. The first generic construction combines an anonymous (ANOCPA secure) and confidential (INDCPA secure) 2level HIBE scheme HIBE = (
We use a delegation property of the HIBE scheme and a security of the signature scheme (or the message authentication code (MAC)) to construct an INDCCA secure PEKS scheme. In our first construction, to generate a PEKS ciphertext CT of a keyword
In our second construction, the idea of constructing for an INDCCA security by using a strong MAC is similar to that employed in the first construction.
We examine the required security conditions of primitives, such as the HIBE, signature, and MAC schemes, which are used to produce generic constructions for a computationally consistent INDCCA secure PEKS scheme.
The first construction of a PEKS scheme, using an anonymous (HIBEANOCPA) 2level HIBE scheme HIBE = (
•
•
•
• Test(CT,
The second construction of PEKS scheme, using anonymous (HIBEANOCPA) 2level HIBE scheme HIBE = (
•
•
•
• Test(CT,
3.2 Flowchat of PEKS Encryption Process
The Fig. 1 shows the flowchart of the encryption module for our construction of PEKS scheme. It provides detail workflow of the module to compute the encrypted keyword “PEKS ciphertext”.
We now show that the confidentiality and consistency of proposed generic constructions are satisfied. In Theorem 4.1. and Theorem 4.2., we identify that (1) the confidentiality (specif.,INDCCA security) of the first PEKS scheme comes from combining the anonymity (ANOCPA security) of the 2level HIBE and the strong onetime security of Sig and (2) the confidentiality (specif., INDCCA security) of the second PEKS scheme comes from combining the anonymity (ANOCPA security) of 2level HIBE, the security of Encap and the strong onetime security of Mac. In Theorem 4.3. and Theorem 4.4., we identify that (3) the computational consistency of the first PEKS scheme comes from combining the confidentiality (HIBEINDCPA) of the 2level HIBE and the existential unforgeability of Sig and (4) the computational consistency of the second PEKS scheme comes from combining the confidentiality (HIBEINDCPA) of 2level HIBE and the binding property of Encap. The idea underlying the proof about the security of the PEKS scheme draws from Boneh et al. [24].
Theorem 4.1. If HIBE is HIBEANOCPA secure and Sig is a strong onetime signature scheme, then the first construction for PEKS scheme is PEKSINDCCA secure.
Proof. Let Π′ denote the HIBE scheme and Π denote the PEKS scheme. Suppose that there is a PPT adversary
Claim 1.
Claim 2. 
To show that these imply the theorem, note that
which is negligible given the stated claims.
Proof of Claim 1.

 If
Proof of Claim 2.
 On trapdoor queries w,
 On ciphertext queries [CT, w],
1.
2. Before the challenge ciphertext
(2.a) If Vrfy(
(2.b) If Vrfy(
3. After
(3.a) If
(3.b) If
(3.c) If
 On the challenge query
1.
2.
Eventually,
Note that
Theorem 4.2. If HIBE is HIBEANOCPA secure and Encap is secure (in the sense of Definition 2.6), and Mac is a strong onetime message authentication code (MAC), then the second construction for PEKS scheme is PEKSINDCCA secure.
Proof. Since the proof of Theorem 4.2 is similar to that of Theorem 4.1, the detail of proof will be omitted. Theorem 4.3. If HIBE is HIBEINDCPA secure and Sig is an existential unforgeable signature scheme, then the first construction for PEKS scheme is computationally consistent.
Proof. Suppose there is a PPT adversary
Claim 3.
Claim 4. 
As in Theorem 4.1, we can prove Theorem 4.3 by establishing the above two clams.
Proof of Claim 3.
Proof of Claim 2.
In its find stage, the given master public key
Here, for every
This completes the proof of the Theorem 4.3.
Theorem 4.4. If HIBE is HIBEINDCPA secure, Encap satisfies a binding property, then the second construction for PEKS scheme is computationally consistent.
Proof. Since the proof of Theorem 4.4 is similar to that of Theorem 4.3, the detail of proof will be omitted.
General constructions have the advantage of being able to present protocols that provide new functions and safety using primitives that their securities previously been proven. [4,25] However, libraries such as Java, C, and the like may not support all kinds of functions that are cryptographic primitives. Hence, when considering the fact that you can select appropriate primitives depending on the development environment, it is meaningful to propose various general constructions using different primitives (as PKE, signature, massage authentication code, hash etc). Therefore, it is meaningful to propose a new type of generic construction using different types of primitives and to prove its security.
In this paper, we have examined the properties of the HIBE, signature and MAC, encapsulation schemes used to construct two confidential(INDCCA secure) and computationally consistent generic constructions for PEKS schemes. We obtained the first generic construction by combining anonymous (ANOCPA secure) 2level HIBE and a secure signature scheme and the second by combining anonymous (ANOCPA secure) 2level HIBE, a secure encapsulation, and a secure MAC schemes [26]. A confidential PEKS scheme has resulted from the anonymity of the HIBE scheme and the security of the signature scheme (or of the MAC scheme). The computational consistency of the PEKS scheme has resulted from the confidential HIBE scheme and the security of the signature scheme (or the security of the encapsulation and MAC schemes). Hence, the proposed scheme will be one of the generic constructions for providing the consistent INDCCA secure PEKS.
Funding Statement: The author received no specific funding for this study.
Conflicts of Interest: The author declare that they have no conflicts of interest to report regarding the present study.
1. General Data Protection Regulation (GDPR) – Official Legal Text, 2016. https://gdprinfo.eu. [Google Scholar]
2. Brazil’s General Data Protection Law (Lei Geral de Proteção de Dados  LGPD) Compliance, 2020. https://cpl.thalesgroup.com/engb/compliance/americas/brazilgeneraldataprotectionlaw. [Google Scholar]
3. M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno et al., “Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions,” Journal of Cryptology, vol. 21, no. 3, pp. 350–391, 2008. [Google Scholar]
4. M. Abdalla, M. Bellare and G. Neven, “Robust encryption,” in Proc. TCC2010, LNCS 5978, Berlin, Germany, Springer, pp. 480–497, 2010. [Google Scholar]
5. J. Baek, R. SafaviNaini and W. Susilo, “Public key encryption with keyword search revisited,” in Proc. ACIS2006, LNCS 5072, Springer: Perugia, Italy, pp. 1249–1259, 2008. [Google Scholar]
6. D. Boneh and B. Waters, “Conjunctive, subset, and range queries on encrypted data,” in Proc. Fourth IACR Theory of Cryptography Conf., TCC 2007, LNCS 4392, Springer: Berlin, Heidelberg, pp. 535–554, 2007. [Google Scholar]
7. B. Chor, E. Kushilevitz, O. Goldreich and M. Sudan, “Private information retrieval,” Journal of the ACM, vol. 45, no. 6, pp. 965–981, 1998. [Google Scholar]
8. Y. Chen, J. Zhang, D. Lin and Z. Zhang, “Generic constructions of integrated PKE and PEKS,” Journal of Designs, Codes and Cryptography, vol. 78, no. 2, pp. 493–526, 2016. [Google Scholar]
9. C. Gentry and A. Silverberg, “Hierarchical IDbased cryptography,” in Proc. ASIACRYPT2002, LNCS 2501, Springer: Queenstown, New Zealand, pp. 548–566, 2002. [Google Scholar]
10. Y. H. Hwang and P. J. Lee, “Public key encryption with conjunctive keyword search and its extension to a multiuser system,” in Proc. Pairing2007, LNCS 4575, Springer: Tokyo, Japan, pp. 2–22, 2007. [Google Scholar]
11. J. Katz, A. Sahai and B. Waters, “Predicate encryption supporting disjunctions, polynomial equations, and inner products,” in Proc. EUROCRYPT2008, LNCS 4965, Springer: Istanbul, Turkey, pp. 146–162, 2008. [Google Scholar]
12. S. Ma and Q. Huang, “A new framework of INDCCA secure public key encryption with keyword search,” Computer Journal, vol. 63, no. 12, pp. 1849–1858, 2020. [Google Scholar]
13. H. S. Rhee, J. H. Park, W. Susilo and D. H. Lee, “Improved searchable public key encryption with designated tester,” in Proc. ASIACCS2009, New York, United States, pp. 376–379, 2009. [Google Scholar]
14. T. Suzuki, K. Emura and T. Ohigashi, “A generic construction of integrated securechannel free PEKS and PKE and its application to EMRs in cloud storage,” Journal of Medical Systems, vol. 43, no. 5, pp. 1–15, 2019. [Google Scholar]
15. D. Boneh, G. D. Crescenzo, R. Ostrovsky and G. Persiano, “Publickey encryption with keyword search,” in Proc. EUROCRYPT2004, LNCS 3027, Springer: Interlaken, Switzerlan, pp. 506–522, 2004. [Google Scholar]
16. S. Goldwasser and S. Micali, “Probabilistic encryption,” Journal of Computer and System Sciences, vol. 28, no. 2, pp. 270–299, 1984. [Google Scholar]
17. J. Manger, “A Chosen ciphertext attack on RSA optimal asymmetric encryption padding (OAEP) as standardized in PKCS #1v2.0,” in Proc. CRYPTO’01, LNCS 2139, Springer: Santa Barbara, California, USA, pp. 230–238, 2001. [Google Scholar]
18. V. Shoup, “Why chosen ciphertext security matters,” IBM Research Report, RZ 3076, 1998. [Online]. Available: http://www.shoup.net/papers. [Google Scholar]
19. D. Bleichenbacher, “Chosenciphertext attacks against protocols based on the RSA encryption standard PKCS #1,” in Proc. CRYPTO’98, LNCS 1462, Springer: Santa Barbara, California, USA, pp. 1–12, 1998. [Google Scholar]
20. T. Fuhr and P. Paillier, “Decryptable searchable encryption,” in Proc. Provably Security’07, LNCS 4784, Springer: Wollongong, Australia, pp. 228–236, 2007. [Google Scholar]
21. D. Boneh and M. Franklin, “Identitybased encryption from the weil pairing,” SIAM Journal on Computing, vol. 32, no. 3, pp. 586–615, 2003. [Google Scholar]
22. J. Horwitz and B. Lynn, “Toward hierarchical identitybased encryption,” in Proc. EUROCRYPT 2002, LNCS 2332, Springer: Amsterdam, The Netherlands, pp. 466–481, 2002. [Google Scholar]
23. D. Boneh, A. Boldyreva, A. Desai and D. Pointcheval, “Keyprivacy in publickey encryption,” in Proc. Asiacrypt2001, LNCS 2248, Springer: Gold Coast, Australia, pp. 566–582, 2001. [Google Scholar]
24. D. Boneh, R. Canetti, S. Halevi and J. Katz, “Chosenciphertext security from identitybased encryption,” SIAM Journal on Computing, vol. 36, no. 5, pp. 915–942, 2006. [Google Scholar]
25. Y. Wang, W. Susilo, J. Baek, J. Kim and I. Kim, “Generic construction of fair exchange scheme with semitrusted adjudicator,” Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications, vol. 10, no. 4, pp. 68–87, 2019. [Google Scholar]
26. D. H. Duong, W. Susilo and V. C. Trinh, “Wildcarded identitybased encryption with constantsize ciphertext and secret key,” Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications, vol. 11, no. 2, pp. 74–86, 2020. [Google Scholar]
This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 