Xiaojun Zhang＊, Chunxiang Xu, Liming Mu, Jie Zhao

1 School of Computer Science, Southwest Petroleum University, Chengdu 610500, China

2 School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China

I. INTRODUCTION

In a storage system, sensitive data often needs to be encrypted before being outsourced to the server to protect its privacy. Hence the issue how to search encrypted data through keywords has emerged. In 2004, Boneh et al. [1]proposed the first scheme which can search encrypted data in server through keywords by using public key cryptographic system, and their work opens a novel research fi eld that is public key encryption scheme with keyword search (PEKS).

In a PEKS scheme, with the receiver’s public key, the data sender attaches some encrypted keywords with the encrypted data. The receiver then sends the trapdoor of a keyword to the server for data searching. Using the trapdoor and the PEKS ciphertext, the server can test whether the keyword associated with the PEKS ciphertxt is equal to the one selected by the receiver. If so, the server sends the matching encrypted data to the receiver. After that, Baek et al. [2] proposed a designated tester PEKS scheme, only the designated tester can confirm whether or not a given dPEKS ciphertext is corresponding to a trapdoor by using the tester’s private key. Different from the PEKS scheme in [1], the designated tester PEKS scheme in [2] has no requirement of a secure channel between the date receiver and the server, whereas the scheme in [1] needs one, which becomes impractical when building a secure channel is expensive. We know that since the designated tester in [2] is the unique tester who executes the test process, howerer,only mastering the knowledge of a trapdoor is not enough to break the keyword con fi dentiality. Actually, the schemes in [1, 2] can suffer from the off-line keyword guessing attacks for the given trapdoor from an outside attacker. It means that given a trapdoor, any outside adversary can choose a guessing keyword from the keyword space and then uses the keyword to generate a PEKS ciphertext, the tester then can test whether the guessing keyword is the one associated with the trapdoor. To further protect the keyword confidentiality of the date receiver, Rhee et al. [3] have proposed a scheme respectively to guarantee trapdoor security from an outside adversary, where no one can distinguish the difference of two trapdoors which are generated from the same selected keyword . The previous PEKS schemes are all certificate-based cryptographic system, while identity-based cryptographic system possesses some advantages over certificate-based system, since it can avoid the cost of management of the traditional Public Key Infrastructure(PKI). In 2014, Wu et al. [4] constructed a designated tester pair-based identity-based encryption scheme with keyword search, and proved that the scheme satis fi es ciphertext indistinguishability and can achieve trapdoor security. Particularly, in recent, with the Smooth Projective Hash Functions (SPHF), Chen et al. [5, 6] constructed dual-server public key encryption with keyword search schemes, and their proposed schemes can even resist the inside keyword guessing attack (KGA) without collusion between the dual servers. Moreover,some public key encryption with keyword serach schemes with novel properties have also been proposed [7, 8, 9, 10, 11].

Furthermore, as far as we are concerned,the existing PEKS schemes are based on traditional complexity assumptions. However,the traditional complexity assumptions will be seriously challenged by quantum computing[12]. Therefore, post quantum cryptography has been booming and becomes increasingly significant.

To compensate for the defect from quantum computer attacks, and try to achieve all the security properties of the PEKS, including the trapdoor security and the off-line keyword guessing attacks resistance, in this paper,we propose a PEKS scheme from lattice assumption, which can offer a promising approach to post-quantum cryptography due to its quantum-secure complexity assumptions.The functionality and security requirements of PEKS can be seen in table 1. Speci fi cally,our scheme is identity-based cryptographic system, which can avoid the cost of management of PKI. Our scheme delegates a particular tester to search the results, thus only the unique tester can finish the test process. And our proposed scheme can guarantee that a malicious tester and an outside adversary can not break ciphertext indistinguishability under an adaptive chosen plaintext attack in the random oracle model under the hardness of deciding LWE assumption. Moreover, our scheme can achieve trapdoor security such that an outside adversary can not distinguish the trapdoors for two challenged keywords. Naturally, our scheme can protect against off-line keyword guessing attacks from outside adversary.

II. PRELIMINARIES

Integer Lattices.

L e tbe a set,which consists ofmlinearly independent vectors. We define integer lattice as follows:where the setBis a basis of the lattice.

Definition 1(see [13]) With a matrix, a vector, a primeq, and some integersm,n, we de fi ne as follows:

Table I. Functionality and security requirements of PEKS

Discrete Gaussians.For a parameterδ＞0, the Gaussian function on?mcentered atcwith deviationδis

The discrete Gaussian distribution over Λ with centercand parameterδis

The LWE Hardness Assumption.

Definition 2(see [14]) For a primeq, a positive integern, and a Gaussian noise distributionoverZqdescribed in [14]. Aconsists of an LWE oracle O, which is either Ot, or On, they are described respectively as follows:

Ot: It generates samples from

On: It outputs, whereis a random uniform vector,is a sampled fromandis uniform random vector.

Note that astance allows to repeatedly query to O. Here we define that a probabilistic polynomial time (PPT) adversary A decides theinstance ifis non-negligible.

Lemma 1(see [14]) If there exists a possibly efficient quantum algorithm for decidingassumption satisfyingthen there exists an efficient quantum algorithm for approximating theSIVPassumption andGapSVPassumption,to withinfactors in ?2norm in the worst case.

Moreover, with an LWE instanceif we get the trapdoorT, suchandzis sampled from a discrete Gaussian noise distributionwe can recoverxeasily. Now we employ the technique in [16] to solve the searching the LWE assumption. Set(mod(modq),there are only small entries inTandz, and each entry in the vectorTTzis much smaller thanqand thusTTz(modq) is equal toTTz. Multiplying by (TT)?1, thus getsz, after which it is easy to recoverx.

Preimage Sampleable Functions and Lattice Basis Delegation Technique.

Lemma 2(see [16]). For integersq,n,mthere is a PPT algorithm TrapGen(q,n) that outputs a pair (A,T)satisfying:

(1)is statistically close to a uniform matrix in

(2)is a basis of, each Euclidean norm of all the rows is bounded byO(nlogn).

Lemma 3(see [17]). The probabilistic polynomial time (PPT) algorithmSamplePre(A,T,y,)δt a k e s a m a t r i x, a basis, a vectorand a parameteras input, it outputs a sample from a distribution which is statistically close towhereis a Gaussian noise distribution overwith parameterδ.

Now, we describe Agrawal et al. [18] lattice basis delegation technique, we first describe the distribution Dm×mas follows:

Dm×mdenotes the distribution on matrics inwhich is defined asconditioned on the resulting matrix beingZq-invertible. Here the parameterandZq-invertible means that the matrixR mod qis invertible as a matrix in

Now we describeSampleR(1m)in [18] as follows.

SampleR(1m):This algorithm samples matrices from a noise distribution overwhich is statistically close to the distribution Dm×m.

(1) SetTto be a canonical basis of the latticeZm.

(2)sample noise vectorri←SampleGaussiandescribed in [18].

(3) OutputR, if-invertible, otherwise repeat the step 2.

Then we describe the algorithmNewBasisDelin [18] forB=AR?1. The algorithmNewBasisDeltakes a matrixZq-invertible matrixRfrom Dm×mdescribed in [18], a short basisTAforas input,and generates a short basisTBof

NewBasisDel( A, R, TA,σ)is detailed as follows.

(1) Evaluate

(2) Takeand an arbitrary basisTofas input, output a short basisofwith its Gram-Schmidt norm is no more than that of

(3) Run the algorithmdescribed in [20] to make randomized basis

Furthermore, we utilizeSample R with Basisto realize security proof of ciphertext indistinguishability. The algorithm takes a random matrixAinas input, and generates a low-normm×mdimension matrixR, a short basis forThe algorithmSample R with Basisis described as follows:

(1) RunTrapGen(q,n) to get a random uniformand a good short basisTBsatisfying

(2) S e ti=1,…,m, do as follows:

(2a) Sample anmdimension noise vectormodq.

(2b) Repeat step (2a) untily independent of

(3) SetoutputTB,R.

Note thatmodq, thusBR=Amodq, andRisZq-invertible matrix, thusB=AR?1modq. We get thatTBis a basis of

III. DEFINITION OF IDENTITY-BASED ENCRYPTION WITH KEYWORD SEARCH WITH A DESIGNATED TESTER

In this section, we first give the system model of public key encryption with keyword search(PEKS) with a designated tester (cloud server)which consists of three entities: data owner,cloud server, and data receiver, as illustrated infigure1.

Then, we give the definition of IBEKS, then we give security definition of IBEKS scheme.

An IBEKS scheme consists of the following six algorithms:

?Setup(κ): This is a PPT algorithm, it takes a security parameterκas input, then generates system public parametersPPand a master private keymk.

?This algorithm is executed by the PKG. It takes the master private keymkand a receiver’s identityIDras input, then outputs the receiver’s private keySKIDr.

Fig. 1. The system model of PEKS.

?This algorithm is also executed by the PKG. It takes the master private keymkand a designated tester’s identityIDtas input, then outputs the designated tester’s private keySKIDt.This algorithm takes system public parametersPP, the receiver’s identityIDr, the designated tester’s identityIDt, and keywordwas input, then outputs ciphertextCTfor keywordw.This algorithm takesPP, the receiver’s private keySKIDr, the designated tester’s identityIDt, and keywordw′ as input. Finally, it outputs trapdoorTw′for the keywordw′.Once receiving the trapdoorTw′, this algorithm takes as inputsPP, a ciphertextCT, the designated tester’s private keySKIDt, and trapdoorTw′. It outputs true ifw=w′ and false otherwise.

3.1 Security of IBEKS

We say an IBEKS scheme is semantically secure, that means the IBEKS scheme can guarantee ciphertext indistinguishability. Ciphertext indistinguishability implies that a malicious tester and an outside adversary can not distinguish the ciphertexts for two challenged keywords chosen by them.

In our secure model, in order to prove IBEKS scheme can guarantee ciphertext indistinguishability, we de fi ne two games, they are Game 1 and Game 2 respectively below.

Game 1:Here, we consider a malicious tester as a PPT adversary A1, which interacts with the challenger C as follows.

Setup:C setsPP, and C runsKeyExtracttesterto get A1'sprivate key

Phase 1:A1adaptively performs different queries to C below:

?KeyExtractreceiverquery: Once the adversary A1makes his query forIDr, C runsKeyExtractreceiveralgorithm to getSKIDr, then it returnsSKIDrto A1.

?Trapdoorquery: Once the adversary A1makes this query for a keywordw, C runsTrapdoorto get trapdoorTwfor the keywordw, then C returnsTwto A1.

Challenge:After performing a number of queries above, the adversary A1sendsto C, whereandare two challenged keywords. The restrictions are that A1did not make thequery for, and theTrapdoorquery forThen C choosesb∈{0,1} and employsto generate ciphertextCT*by running the algorithm IBEKS. Finally, C returns the resultedCT*to A1.

Phase 2:A1is able to make theKeyExtractreceiverquery for any identityIDrand theTrapdoorquery for any keywordwin an adaptive manner.

Guess:Finally, A1outputsb′∈{0,1}. We assume that A1wins Game 1 ifb′=b.

Game 2:Here, we consider an outside adversary (malicious receiver) as a PPT adversary A2, which interacts with C below:

Setup:C sets system public parametersPP, and C sendsPPto A2.

Phase 1:A2may adaptively execute different queries to C adaptively as follows:

?KeyExtractreceiverquery: Once the adversary A2makes his query for an identityIDr,C runsKeyExtractreceiveralgorithm to generateSKIDr, then it returnsSKIDrto A2.

?KeyExtracttesterquery: Once the adversary A2makes his query for a tester identityIDt,the challenger C runsKeyExtracttesteralgorithm to generateSKIDt, then it returnsSKIDtto A2.

?Trapdoorquery: Once the adversary A2makes this query for a keywordw, C runsTrapdoorto get trapdoorTwfor the corresponding keywordw, then returnsTwto the adversary A2.

Challenge:After performing a number of queries above, the adversary A2sendsto the challenger C,whereare two challenged keywords.The restrictions are that A2did not make theKeyExtracttesterquery for, and theTrapdoorquery forand. Then C choosesb∈{0,1} and employsto get ciphertextC*by running the encryption algorithm. Finally, C returns the resultCT*to A2.

Phase 2:A2is able to make theKeyExtracttesterquery for any identityIDtand theTrapdoorquery for any keywordwto C.The restrictions are that A2did not make theKeyExtracttesterquery forIand A2did not make theTrapdoorquery keywordto C.

Guess: Finally, A2outputsb′∈{0,1}. We assume that A2wins Game 2 ifb′=b.

Definition 3: The advantage ofbreaking the ciphertext indistinguishability of IBEKS scheme with a designated tester is defined specified as:

If for any adversary Ai(i=1,2),is negligible, then the IBEKS scheme with a designated tester is semantically secure against an adaptive chosen plaintext attack.

IV. IDENTITY-BASED ENCRYPTION WITH KEYWORD SEARCH FROM LATTICE ASSUMPTION

4.1 Our construction

In this section, we give our lattice-based IBEKS scheme. In particular, we designate a unique tester to finish the test process and return the results, thus can avoid establishing an additional secure channel to transmit the trapdoor. Our scheme is described as follows.

Setup()κ:Take a security parameterκas input, and setq,n,m,σ,,δ αas specified in Section 2. Next, do the following:

(1) RunTrapGen(q,n) to generate a random uniformn×mmatrixA∈Zqn×mand a short basis

(2) Select two random uniform vectors

(3) S e t s e c u r e h a s h f u n c-their outputs are distributed as in Dm×m.

(4) Output system public parameters and master private key respectively as follows:On inputPP, a master private keymkand a receiver’s identityIDr∈{0,1}?1, The PKG executes as follows:

(3) The designated tester checks ifτ′ =τ′′,then it returns true. Otherwise, it returns false.

4.2 Correctness

In the test process, with the private keyTt, the designated tester can easily generatetw′, then it can computeMeantime,with the private keyTt, the designated tester can also easily getthen it can computeAs we know that,are both error terms, to decrypt correctly, we need to make sure that these error terms are less thanq/5 discussed in [17]. To make sureτis correctly decrypted, the discussion of these error terms and the concrete setting of the security parameters can be referred to [19].

After being correctly decrypted, the designated testerIDtcan getτ′=τfromU, andτ′′ =τfromV,id, thus it can successfully check thatτ′τ′′= . Therefore, the designated tester can believe that the ciphertextcorresponds with the trapdoorTwfrom the receiverIDr.

V. SECURITY PROOF OF OUR IBEKS SCHEME

5.1 Ciphertext Indistinguishability

In this section, we first proves our IBEKS scheme can achieve the security of ciphertext indistinguishability in the random oracle model under the hardness assumption of decision

To simplify the proof of security, we prove two lemmas, namely Lemma 4 and Lemma 5 respectively. In Lemma 4, we assume that the adversary A1is a malicious tester. In Lemma 5, the adversary A2is considered as an outside adversary.

Lemma 4:We assume that a malicious tester A1with a non-negligible probabilityεcan break ciphertext indistinguishability of the proposed IBEKS scheme in the ran-dom oracle model under an adaptive chosen plaintext attack. Then, there exists a challenger C also withwho can solve the hardness assumption of decision

Proof:Suppose that a malicious tester A1with a non-negligible probabilityεcan break ciphertext indistinguishability, we build a challenger C that can decideassumption also with a non-negligible probability by running A1as a subroutine. The challenger C makes use of the adversary A1to distinguish the LWE oracle O.C fi rst queries the LWE oracle O form+1 times and obtains fresh pairsThen the challenger C performs as follows:

The challenger C prepares system public parameters environment for the adversary A1as follows:

(1) The challenger C samples two random matricesby runningSampleR(1m).

(2) Construct the random matrixfrommof the givenLWEinstances, wherethei-th column ofA0isui. Setμto beu0, and randomly chooseν←Zqn. Meanwhile, for the random-oracle hash queries, to keep consistency, C sets four listsrespectively.LetqHibe the maximum number of A1'squeries toHifori=1,2,3,4, the challenger C randomly choosesFinally, the challenger C setsa n d runsKeyExtracttesterto get the adversary A1'sprivate keySKIDt, then C returnsto A1. A1can adaptively query on the variousas follows:

H1query forIDr: A1may query the random oracleH1on thei-th query for any receiver identityIDrof its choice. C can answer thei-th query below.

Fig. 2. The process of search and test.

If, C setsreturnsto the adversary A1. Otherwise, C executesSampleRwithBasis(A)to get a randomm×mdimension matrixand a short basisSKIDrforthen the challenger C storesinto the listL1and returnsRIDrto the adversary A1.

H2query forw: A1may query the random oracleH2on thei-th query for any keywordwcorresponding to thej-th receiverIDr. Here we consider the following two cases:

If, such thatlenger C performs as follows:

The challenger C returnsRw, if there existsL2. If, such thatw=w*, the challenger C storesand returnsto the adversary A1. Otherwise, the challenger C runs the a l g o r i t h mto get a randomm×mdimension matrixand a short basisFinally, C saves the tuplein listL2, and returnsRwto the adversary A1.

If, such thatlenger C performs as follows:

The challenger C returnsRw, if there existsi n l i s tL2. I f, s u c h t h a tw=w*, C directly returnsto the adversary A1. Otherwise, C randomly chooses matrix, and looks into the listL1to fi ndthen runs the algorithmto generate a short basisFinally, C storesin listL2, and returnsRwto the adversary A1.

H3query forIDt: C returnsRIDtto the adversary, ifis in listL3.Otherwise, C executesSampleRwithBasis(A)to generate a randomm×mdimensionand a short basisthen C storesinto the listL3and returnsRIDtto A1.

H4query forid: C returnsthere existsin listL4. Otherwise,C randomly chooses

Phase 1:In this phase, A1can make different queries to the challenger C adaptively as follows:

KeyExtractreceiverquery: when the adversary A1makes the query for any identityIDr, C looks into the listL1for the corresponding tupleand returnsSKIDrto the adversary A1. Ifis not in the listL1,then C calls theH1query forIDr. Finally, C storesinto the listL1and returnsRIDrto the adversary A1.

Trapdoorquery onw: Once receiving the query onthe adversary A1, whereRIDtis the hash value ofIDt, the challenger C first looks intoL2, ifis in list L2,C can getthen the challenger C runsto generate thetw. Finally, the challenger C randomly choosesand computesand returnsTwto the adversary A1.

Challenge:A1the challenger C, whereandare two challenged keywords. A1randomly selectsb←{0,1}, and messageτ*←{0,1}, then the challenger C performs as follows:

(1) Retrievefrom the LWE instance and se tcompute

(2) C randomly selects an identityid*∈{0,1}?1and it looks intoL L3,4respectively to find the hash values of. Then C randomly choos-and chooses noise vectorsaccording to Gaussian noise distributionrespectively, computes

During the challenge phase, the restrictions for A1are that it can not makeKeyExtractreceiverquery forand theTrapdoorquery for two keywordsand

.

Finally, C returns the challenged ciphertextto the adversary A1,where

Phase 2:The adversary A1can makeKeyExtractreceiverquery for any identityIDrand theTrapdoorquery for any keywordwto the challenger C such thatwis not in the set

Guess:Finally, A1outputsb′∈{0,1}.

The goal of the adversary A1is to decide which keyword is used in the challengedCT*.Actually, it is easy to see that the above challenged ciphertext has the correct distribution.When O is a pseudo-random LWE oracle,according to the setting of the public parametersPP, recall thatfor some randomand some random noise vectorwith Gaussian distributionTherefore,have the correct forms. We consider the case that the adversary A1can succeed in guessing that the keywordis used in generationCT*with the non-negligible probabilityε, where the keywordis just thequery, that meansthis case can occur with the probability 1/qH2. Whilequery, this case can occur with the probability 1/qH1. Therefore, if A1with a non-negligible probabilityεcan break ciphertext indistinguishability of the proposed IBEKS scheme in the random oracle model under an adaptive chosen plaintext attack, then C has the advan-assumption by running A1as a subroutine.This completes the Lemma 4 proof.

Lemma 5:We assume that A2with a non-negligible probability ∈ can break ciphertext indistinguishability of the proposed IBEKS scheme in the random oracle model under an adaptive chosen plaintext attack. Then, there exists a challenger C also withwho can decide theassumption.

Proof:We can consider the outside adversary A2as a malicious receiver. Similar to the Lemma 4, suppose that A2with ∈can break ciphertext indistinguishability,we build a challenger C that can decide theassumption also with a non-negligible probability ∈′ by running A2as a subroutine. The challenger C makes use of the adversary A2to distinguish the LWE oracle O. C first queries the LWE oracle O form+1 times and obtains fresh pairswherethe challenger C performs as follows:

The challenger C prepares system public parameters environment for the adversary A2as follows:

(1) To generate system public parameters, C samples two random matricesby running the algorithmSampleR(1m).

(2) Construct the randomn×mdimensionfrommof the givenLWEinstances, where for allthei-th column ofand randomly chooseMeanwhile, for the random-oracle hash queries, to keep consistency,C sets four listsrespectively. LetqHibe the maximum number ofqueries toHifori=1,2,3,4, then randomly choosesFinally, C setsa n d returns it to A2.

A2can adaptively query for the various oracles

H1query forIDr: C returnsRIDrto the adversary, ifis in listL1. Otherwise, C executesSampleRwithBasis(A) to get a randomm×mdimension matrixand a short ba-then C storesinto the listL1and sendsRIDrto the adversary A2.

H2query forw: Once receiving the query on some keywordwchosen by a receiverIDr, the challenger C first looks into the listL2, ifis in listL2, then C returnsRwto

H3query forIDt: A2may query the random oracleH3on thei-th query for any server identityIDtof its choice. C can answer thei-th query as below.

H4query forid: A2may queryH4on thei-th query for any challengedidcorresponding to thej-th serverIDt. Here we consider the following two cases:

Phase 1:In this phase, A2may performKeyExtractreceiverquery, andTrapdoorquery as the same to the Phase 1 of Lemma 5. And A2performsKeyExtracttesteras follows. When the adversary A2makes the query for any tester identityIDt, C looks into the listL3for the corresponding tupleand returnsSKIDtto the adversary A2. Ifis not in the listL3,then C calls theH3query forIDt. Finally, C storesinto the listL3and returnsRIDtto the adversary A2.for the adversary A2are that A2did not make thequery forand theTrapdoorquery for.

Finally, C randomly selects chooses an identityand returnsto the adversary A as the

2challenged ciphertext, where

Phase 2:A2can makeKeyExtracttesterquery for any identityIDtand theTrapdoorquery for any keywordwto the challenger C such thatandwis not in the set

Guess:Finally, A2outputsb′∈{0,1} .

The goal of the adversary A2is to decide which keyword is used in the challengedCT*. In fact, it is easy to see that the above challenged ciphertext has the correct distribution.As O is a pseudo-random LWE oracle, by the setting of the public parameters, recall thatthus we have the followi n g:

ID||id3t4

a n dfor some randomand some random noise vectorwith Gaussian distribution Ψ . Therefore,have the

acorrect forms. As O is a random oracle, thenare uniform inand thereforeis uniform in. We consider the case that the adversarycan succeed in guessing that the keywordis used in generation, it means the adversarycan guess that the challenged testeris just thequery, andid*is just thequery. This case can occur in the same time with the probability. Therefore,if A2with a non-negligible probability ∈ can break ciphertext indistinguishability of the proposed IBEKS scheme in the random oracle model under an adaptive chosen plaintext attack, then C has the advantageto decide theassumption by running A2as a subroutine. This completes the Lemma 5 proof.

By Lemma 4 and Lemma 5, we can conclude Theorem 1.

Theorem 1:Our proposed IBEKS scheme satisfies ciphertext indistinguishability in the random oracle model against an adaptive chosen plaintext attack due to the hardness of deciding theassumption.

5.2 Trapdoor security

Now we begin to demonstrate the trapdoor security of our proposed IBEKS scheme.The trapdoor security means that an outside adversary (except the receiver and the tester)is unable to distinguish the trapdoors for challenged keywords.

As we can see that, during theTrapdoorquery, with the private keyTr, the receiverIDrfirst runsto gete, and runs the algorithmto generatetw. Then the receiver randomly choosesand uses the designated tester’s public keyto computewhich is an LWE instance, by the hardness of searching the LWE assumption, the distribution ofTwis indistinguishable from the random uniform vector inZqm. Thus if any other outside adversary wants to recovertwfromTw, he has to get the knowledge of the designated tester’s private key. Otherwise,he has to solve the LWE assumption. However, this is impossible as described in [14].Therefore, we conclude that no one except the receiver and designated tester can get the trapdoortw, thus the designated tester can perform theTestphase correctly, then he returns the correct challenged ciphertext corresponding to the right keyword to the receiverIDr.

According to the theorem in [3], since our proposed IBEKS scheme satisfies ciphertext indistinguishability and trapdoor security which can protect against an adaptive chosen keyword attack, we can conclude that our IBEKS can resist off-line keyword guessing attacks from an outside adversary.

VI. PERFORMANCE COMPARISON

In this section, we give the performance comparison with classic PEKS schemes in [4, 6]in terms of efficiency, communication overhead and hardness assumptions. We fi rst need to consider computational costs, including modular exponentiationmodular multiplicationpairing operationand inverse operationInG, hash operationHash,and we also define the computational cost ofSamPreandNewBasisDelasTSP,TNBDrespectively. Additionally, we set the length of a keyword isλ, and de fi nelq,lGas the bit length ofZq,Grespectively.

In the PEKS schemes, the computational costs includes PEKS ciphertext generation, trapdoor generation and testing.In the aspect of computational costs in[4], the computational costs of PEKS ciphertext generation, trapdoor generation and testing arerespectively. In the aspect of computational costs in [6], the computational costs of PEKS ciphertext generation, trapdoor generation and testing arerespectively. While in the aspect of computational costs in our proposed scheme, the computational costs of PEKS ciphertext generation, trapdoor generation and testinga r erespectively.

Table II. Efficiency comparison.

Table III. Communication overhead comparison and hardness assumption.

In the PEKS schemes, the communication overhead includes ciphertext size and trapdoor size. In the aspect of communication overhead in [4], the ciphertext size and trapdoor size are 2lG+λand 2lGrespectively. In the aspect of communication overhead in [6], the ciphertext size and trapdoor size are 3lG, 3lG. While in the aspect of communication overhead of our proposed scheme, the ciphertext size and trapdoor size arerespectively.

From table 2, the computational cost of PEKS ciphertext generation in our scheme is much less than the scheme in [4, 6], since the scheme in [4, 6] needs time-consuming pairing operation and modular exponentiation. Aslqis much less thanlG, and we set proper parametermto be small enough, compared with the scheme in [4, 6] in table 3, our proposed scheme also owns more advantages in the aspect of communication overhead. Moreover,our scheme is based on lattice assumption,which is an interesting stepping stone in the post-quantum cryptographic communication.

VII. CONCLUSION

Due to the booming of post-quantum cryptography, in this paper, we have constructed a lattice-based identity-based encryption with keyword search which can protect against quantum computer attacks. Our scheme is provable secure and can be guaranteed trapdoor security. Furthermore, the scheme can resist off-line keyword guessing attacks from an outside adversary and can avoid the complex certificate management. As far as we are concerned, our scheme is the first identity-based construction based on lattice assumption,which is an interesting stepping stone in the post-quantum cryptographic communication.

ACKNOWLEDGEMENTS

This work is supported by the National Natural Science Foundation of China (No.61370203),China Postdoctoral Science Foundation Funded Project (No.2017M623008), Scientific Research Starting Project of SWPU(No.2017QHZ023) and State Scholarship Foundation of China Scholarship Council(No.201708515149).

References

[1] D. Boneh, G. D. Crescenzo, R. Ostrovsky, G.Persiano, “Public key encryption with keyword search,”Proceedings of Advances in Cryptology-Eurocrypt, 2014, pp. 506-522.

[2] J. Baek, R. Safavi-Naini, W. Susilo, “Public key encryption with keyword search revisited,”Proceedings of ACIS, 2006, pp. 1249–1259.

[3] H. S. Rhee, J. H. Park, W. Susilo, D. H. Lee, “Trapdoor security in a searchable public-key encryption scheme with a designated tester,”Journal of Systems and Software, vol. 83, no. 5, 2010, pp.763–771.

[4] T. Y. Wu, T. T. Tsai, Y. M. Tseng, “Efficient searchable identity-based encryption with a designated server,”Annales des Télécommunications, vol.69, no.7-8, 2014, pp. 391-402.

[5] R. Chen, Y. Mu, G. Yang, F. Guo, X. Wang, “A new general framework for secure public key encryption with keyword search,”Proceedings of ACISP, 2015, pp. 59-76.

[6] R. Chen, Y. Mu, G. Yang, F. Guo, “Dual-Server Public-Key Encryption With Keyword Search for Secure Cloud Storage,”IEEE Transactions on Information Forensics and Security, vol. 11, no. 4,2016, pp.789-798.

[7] Q. Tang, H. Ma, X. Chen, “Extend the concept of public key encryption with delegated search,”TheComputer Journal, vol. 58, no. 4, 2015, pp.724-734.

[8] Y. Yu, J. Ni, H. Yang, Q. Xia, “Efficient public key encryption with revocable keyword search,”Security and Communication Networks, vol. 7, no.2, 2014, pp. 466-472.

[9] B. Yang, M. Zhang, J. Du, “An error-tolerant keyword search scheme based on public-key encryption in secure cloud computing,”Concurrency and Computation: Practice and Experience,vol. 28, no. 4, 2015, pp. 1083-1093.

[10] Y. Miao, J. Ma, F. Wei, Z. Liu, X. Wang, C. Lu,“VCSE: Verifiable conjunctive keywords search over encrypted data without secure-channel”.Peer-to-Peer Networking and Applications, 2016,vol. 10, no. 4, 2017, pp. 995-1007.

[11] X. Jiang, J. Yu, J. Yan, R. Hao, “Enabling efficient and verifiable multi-keyword ranked search over encrypted cloud data”.Information Sciences, 2017, pp. 22-41.

[12] P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,”SIAM Journal on Computing, vol. 26, no. 5, 1997, pp.1484-1509.

[13] M. Ajtai, “Generating hard instances of the short basis problem,”Proceedings of Automata,languages and Programming ICALP, 1999, pp.1-9.

[14] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,”Proceedings of STOC, 2005, pp. 84-93.

[15] S. D. Gordon, J. Katz, V. Vaikuntanathan, “A group signature from lattice assumptions,”Proceedings of Advances in Cryptology-ASIACRYPT,2010, pp.395-412.

[16] J. Alwen, C. Peikert, “Generating shorter bases for hard random lattices,”Theorem of Comput.Syst, 2009, pp.75-86.

[17] C. Gentry, C. Peikert, V. Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,”Proceedings of the 40th Annual ACM Symposium on Theory of Computing,STOC,2008, pp. 197-206, 2008.

[18] S. Agrawal, D. Boneh, X. Boyen, “Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE,”Proceedings of Advances in cryptology-CRYPTO, 2010, pp. 98-115.

[19] D. Cash, D. Hofheinz, E. Kiltz, C. Peikert, “Bonsai trees, or how to delegate a lattice basis,”Proceedings of Advances in cryptology-EUROCRYPT,2010, pp.523-552.