Chosen-Ciphertext Attack Secure Public-Key Encryption with Keyword Search

Hyun Sook Rhee

Samsung Electronics Co.Ltd.,Suwon-si,16677,Korea

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 IND-CCA security for PEKS to enhance it’s security and proposed consistent IND-CCA secure PEKS based on the “robust” ANO-CCA secure identity-based encryption(IBE).In this paper,we propose two generic constructions of consistent IND-CCA 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“ANO-CPA security(resp.,IND-CPA security)”of HIBE than“ANOCCA security (resp.,IND-CCA security)”of IBE required in for achieving IND-CCA secure(resp.,consistent)PEKS.Finally,we prove that our generic constructions satisfy IND-CCA security and consistency under the security models.

Keywords:Searchable encryption;public-key encryption with keyword search;chosen ciphertext security;data privacy

1 Introduction

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 store-and-forward 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 CTwof a keyword w under the public key of the receiver and sends the PEKS ciphertext CTwalong with an encrypted email message to a server.To retrieve the email messages containing a keyword w′from the server,a receiver provides the server with a trapdoor Tw′(which is generated under the receiver’s secret key).The server then runs a test function with CTwand Tw′to identify whether or not w=w′,and forwards the corresponding email messages to the receiver.

As security of public key encryption,IND-CPA (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,CTwand Tw′,without learning any information on keywords except the fact that two keywords w and w’are equal.This security condition has been considered as INDCPA in PEKS.If a PEKS scheme does not provide the confidentiality of a keyword,the privacy of the email message is not guaranteed.Additionally,PEKS should provide consistency[3]that requires that the server’s test function with the inputs,CTwand Tw′,returns “true”if w = w′,and returns“false”otherwise.If a PEKS system does not meet the consistency condition,email messages may be incorrectly routed.

Abdalla et al.[3,15]showed that an IND-CPA PEKS scheme can be constructed from an ANOCPA (anonymity under chosen plaintext attack) identity-based encryption (IBE) scheme and that a consistent PEKS scheme can be constructed from an IND-CPA 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 IND-CPA security only considers an adversary that may choose plaintexts of its choice and generate the corresponding ciphertexts.IND-CPA security does not guarantee indistinguishability under a chosen ciphertext attack(IND-CCA 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 IND-CCA 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 IND-CCA 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],INC-CCA security had been considered.Strictly speaking,‘‘ciphertext of a message”instead of‘‘PEKS chiphertext of a keyword”is the target of the IND-CCA 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 IND-CCA PEKS scheme can be directly constructed from an ANO-CCA 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“Boneh-Flanklin 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 IND-CCA secure PEKS scheme by using the underlying schemes which satisfy the weaker security(ANO-CPA security)than ANO-CCA 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 public-key encryption(for short,PKE),a signature,a MAC,and a hash etc)will maximize utilization in real life.

Table 1:Comparison

In this paper,for alternatives for providing the consistent IND-CCA secure PEKS,we propose two generic constructions:For IND-CCA security of PEKS,one is based on any ANO-CPA secure twolevel hierarchical IBE(HIBE)and a strong one-time signature,and the other is based on ANO-CPA secure two-level HIBE,a secure encapsulation,and a strong one-time MAC.For consistency of PEKS,one is based on any IND-CPA secure two-level HIBE and an existential unforgeable signature and the other is based on any IND-CPA secure two-level HIBE and a computational binding encapsulation.

IND-CCA 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 IND-CCA of PEKS requires that for given two keywords w0andw1and a challenge PEKS ciphertext CT*,it is infeasible for an adversary to distinguish which keywords has been encrypted,provided the test query of the form(CT*,wb)(b=0,1)has never been submitted to the test oracle.

We note that(CT*,w)or(CT,wb)(b=0,1)still can be queried to the test oracle,for wwband CTCT*.In particular,to provide IND-CCA security,a PEKS scheme should have a mechanism to validate a PEKS ciphertext CT in a query of the form(CT,wb).That is,honestly-generated PEKS ciphertexts should be distinguishable from PEKS ciphertexts that are forged with CT*.In our generic constructions,a PEKS ciphertext CT of a keyword w is generated in such a way that the party who encrypted w can be authenticated by the addition of a signature or MAC of the party.This enforces that an attacker should counterfeit a signature or MAC to forge a valid PEKS ciphertext.

Consistency of PEKS.In[3],it was shown that the confidentiality(IND-CPA 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 polynomial-time adversary to find distinct keywords w and w′such that the result of the test function with CTwand Tw′is true.)To provide computational consistency in our two constructions for IND-CCA secure PEKS,we identify that the confidentiality(IND-CPA security)of the HIBE scheme as well as existentially unforgeability of a signature scheme or binding property of an encapsulation scheme are required.

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“IDN-CPA 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.

This scenario6 demonstrates the tremendous impor-tance of giving young people caring attention and encouraging them to develop and practice such gifts as they might have. Years later, I was able to repay my debt to Marguerite Byrne by dedicating one of my books, Wry7 on the Rocks -- A Collection of Poems, to her.

2 Preliminaries

We review the notation and recall the definitions of a hierarchical identity-based encryption(HIBE) scheme,a strong one-time 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 S,|S|denotes its size.The symbol k denotes a security parameter.We let a ←b denote the assignment to a the result of evaluating b.We say a function μ is negligible if for any constant k,there exists N such that μ(n)＜1/nkfor n＞N.

2.1 Hierarchical Identity-Based Encryption

Table 2:The confidentiality(HIBE-IND-CPA)of HIBE scheme

Table 3:The anonymity(HIBE-ANO-CPA)of HIBE scheme

2.2 Signature Scheme

Table 4:Strong unforgeability and existential unforgeability of Sig

2.3 Encapsulation Scheme

Table 5:Securities(hiding and binding)of encap

2.4 Message Authentication Code Scheme

Table 6:One-time security of MAC

2.5 PEKS Scheme

Table 7:CCA security of PEKS

Table 8:Consistency of PEKS

Definition 2.11.We say that a PEKS scheme is“perfectly consistent”if the advantage is 0 for all(computationally unrestricted)adversariesA,“statistically consistent”if the advantage is negligible for all(computationally unrestricted)adversaries)A,and“computationally consistent”if the advantage is negligible for all probabilistic polynomial-time(PPT)adversariesA.

3 Generic Construction of PEKS Scheme

In this Section,we provide two generic constructions of a consistent IND-CCA secure PEKS scheme.The first generic construction combines an anonymous(ANO-CPA secure)and confidential(IND-CPA secure) 2-level HIBE schemeHIBE= (SetupHIBE,KeyGenHIBE,KeyDerHIBE,EncHIBE,DecHIBE),which handles identities of length 2 and a strong one-time signature schemeSig=(G,Sign,Vrfy)in which the verification key out-put by G(1k)has length n(k).The second generic construction combines an anony- mous (ANO-CPA secure) and confidential (IND-CPA secure) 2-level HIBE schemeHIBE= (SetupHIBE,KeyGenHIBE,KeyDerHIBE,EncHIBE,DecHIBE),which handles identities of length 2,a secure encapsulation scheme schemeEncap=(Init,S,R)in which commitments com output by S have length n(k)and a strong one-time message authentication code schemeMAC=(SigMac,VrfyMac).

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 IND-CCA secure PEKS scheme.In our first construction,to generate a PEKS ciphertext CT of a keywordw,the sender first generates a keypair(vk,sk)for a strong one-time signature scheme,chooses a random message R,generates a HIBE ciphertext C of R with the vector of identities(w‖vk)and finally signs on C using sk to obtain a signature σ.Then CT consists of the verification keyvk,the HIBE ciphertext C,the message R and the signature σ.To search the corresponding ciphertext CT with a keywordw′,the receiver derives the private key SKw′corresponding tow′and gives it to the server.Suppose that CT =(vk,C,R,σ)is a PEKS ciphertext.Then the server first verifies the signature σ on C with respect tovkand stops if the verification fails.(That is,the test algorithm checks if C is generated by an identical signer.)Otherwise,the server can generate the private key SK(w′‖vk)by using SKw′and a key-derivation algorithm to decrypt the HIBE ciphertext C using the underlying HIBE scheme.If the result of decryption R′of C is identical to R,then the server obtains the test result 1.(This result 1 means that thew′that is used to generate the private key SKw′is identical to w which is used to generate the ciphertext CT.)

In our second construction,the idea of constructing for an IND-CCA 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,sig-nature,and MAC schemes,which are used to produce generic constructions for a computationally consistent IND-CCA secure PEKS scheme.

3.1 Our Constructions

The first construction of a PEKS scheme,using an anonymous (HIBE-ANO-CPA) 2-level HIBE schemeHIBE=(SetupHIBE,KeyGenHIBE,KeyDerHIBE,EncHIBE,DecHIBE),and a strong one-time signature scheme schemeSig=(G,Sign,Vrfy),proceeds as follows.

?Trapdoor(SK,w):Let w ∈{0,1}nbe a keyword.To generate a trapdoor Twof w,the trapdoor algorithm runs d0w←KeyGenHIBE(SK,0w).The trapdoor is Tw=d0w.

?PEKS(PK,w):To encrypt a keyword w ∈{0,1}nunder the public key PK,this algorithm picks a random message R ∈M and runs G(k)to obtain the pair of signing and verification key(sk,vk).It computes A ←EncHIBE(PK,0w‖1vk,R)and σ ←Sign(sk,A‖R)to generate a PEKS ciphertext CT =[C1,C2,C3,C4]=[vk,A,R,σ].

?Test(CT,Tw):Let CT =[C1,C2,C3,C4]be a ciphertext and Tw=d0wbe a trapdoor.To obtain the test result,this algorithm first checks if Vrfy(C1,C2,C3,C4)=1.If not,it simply outputs ⊥.Otherwise,it computes d(0w‖1vk)←KeyDerHIBE(Tw,1C1)and A′←DecHIBE(d(0w‖1vk),C3).If A′= C2,it outputs 1;else,it outputs 0.

The second construction of PEKS scheme,using anonymous (HIBE-ANO-CPA) 2-level HIBE schemeHIBE=(SetupHIBE,KeyGenHIBE,KeyDerHIBE,EncHIBE,DecHIBE),a secure encapsulation scheme Encap = (Init,S,R),and a strong one-time MAC schemeMAC= (SigMac,VrfyMac),proceeds as follows.

?Gen(k):This algorithm runs SetupHIBE(k)to obtain(PP,mk).The public key is PK = PP and the secret key is SK = mk.It outputs(PK,SK)=(PP,mk).

?Trapdoor(SK,w):Let w ∈{0,1}nbe a keyword.To generate a trapdoor Twof w,the trapdoor algorithm runs d0w←KeyGenHIBE(SK,0w).The trapdoor is Tw=d0w.

? PEKS(PK,w):To encrypt a keyword w ∈ {0,1}nunder PK,this algorithm computes(r,com,dec) ←S(k,pub),A ←EncHIBE(PK,0w ‖ 1com,dec),and tag ←SigMac(r,A).It generates a PEKS ciphertext CT =[C1,C2,C3]=[com,A,tag].

? Test(CT,Tw):Let CT =[C1,C2,C3]and Tw= d0w.This algorithm computes d(0w‖1com)←KeyDerHIBE(Tw,1C1),dec′←DecHIBE(d(0w‖1com),C2),and r′←R(pub,C1,dec′) to obtain a string r′.If r′⊥and VrfyMac(r′,C2,C3)=1,it outputs 1;else,it outputs 0.

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 work-flow of the module to compute the encrypted keyword“PEKS ciphertext”.

Figure 1:Flowchat for PEKS encryption process

4 Security Proofs

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.,IND-CCA security)of the first PEKS scheme comes from combining the anonymity(ANO-CPA security)of the 2-level HIBE and the strong one-time security of Sig and (2) the confidentiality (specif.,IND-CCA security) of the second PEKS scheme comes from combining the anonymity (ANO-CPA security)of 2-level HIBE,the security of Encap and the strong one-time 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(HIBE-IND-CPA)of the 2-level HIBE and the existential unforgeability of Sig and (4) the computational consistency of the second PEKS scheme comes from combining the confidentiality (HIBE-IND-CPA) of 2-level 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].

5 Conclusion

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(IND-CCA secure)and computationally consistent generic constructions for PEKS schemes.We obtained the first generic construction by combining anonymous(ANO-CPA secure) 2-level HIBE and a secure signature scheme and the second by combining anonymous (ANO-CPA secure) 2-level 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 IND-CCA 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.