Verifiable Identity-Based Encryption with Keyword Search for IoT from Lattice

Lin Mei,Chungen Xu,＊,Lei Xu,Xiaoling Yu and Cong Zuo

1School of Science,Nanjing University of Science and Technology,Nanjing,210094,China

2College of Data Science,Taiyuan University of Technology,Taiyuan,030000,China

3Faculty of Information Technology,Monash University,Clayton,3800,Australia

Abstract:Internet of Things(IoT),which provides the solution of connecting things and devices, has increasingly developed as vital tools to realize intelligent life.Generally, source-limited IoT sensors outsource their data to the cloud, which arises the concerns that the transmission of IoT data is happening without appropriate consideration of the profound security challenges involved.Though encryption technology can guarantee the confidentiality of private data,it hinders the usability of data.Searchable encryption (SE)has been proposed to achieve secure data sharing and searching.However, most of existing SE schemes are designed under conventional hardness assumptions and may be vulnerable to the adversary with quantum computers.Moreover, the untrusted cloud server may perform an unfaithful search execution.To address these problems,in this paper,we propose the first verifiable identity-based keyword search (VIBKS) scheme from lattice.In particular,a lattice-based delegation algorithm is adopted to help the data user to verify both the correctness and the integrity of the search results.Besides, in order to reduce the communication overhead, we refer to the identity-based mechanism.We conduct rigorous proof to demonstrate that the proposed VIBKS scheme is ciphertext indistinguishable secure against the semi-honestbut-curious adversary.In addition, we give the detailed computation and communication complexity of our VIBKS and conduct a series of experiments to validate its efficiency performance.

Keywords: Internet of Things; verifiable; lattice; searchable encryption

1 Introduction

Internet of Things (IoT) has developed as one of the most popular and exciting technologies in information and communications [1,2].Recent years’studies have witnessed a broader range of applications in IoT networks, e.g., intelligent traffic, household appliances and medical devices.By 2025, forecasts suggest that there will be more than 75 billion Internet of Things (IoT) connected devices in use.A large number of devices produce tens of zettabytes of data in IoT makes the data storage and processing become a major challenger.Fortunately, cloud storage provides a solution that helps the IoT devices store and process data.However, due to the personal nature of the information collected in IoT networks, consumers are concerned about the sharing of information that reveals their personal habits.Therefore, sensitive private data needs to be encrypted before outsourced to the IoT cloud [3].

Along with data privacy, data utility is indispensable as well.Take the intelligent traffic as an example, the sensor (i.e., the data owner) transmits its data to the cloud server every day for subsequent maintenance and dispatch tasks.However, as mentioned, the above data is encrypted which may incur many practical issues.The primary problem is that how can the data owner get the desired data from such a large amount of encrypted dataset for data analytics.The na?ve decrypt to search approach involves very expensive computation and communication overhead,and thus promotes the study of efficient and practical retrieval over the encrypted data.

Searchable symmetric encryption (SSE) [4] is such a promising paradigm proposed to address aforementioned encrypted retrieval problem.Despite SSE translates encrypted retrieval into reality,this mechanism is with limits in achieving practical data-sharing principle guarantee.As known, in SSE, the data owner and the data user are required to be the same one, but the above data analyst(user) are always experts from many different areas.To fill the gap, public key encryption with keyword search (PEKS) scheme is proposed [5].In PEKS, a data owner first encrypts keywords with the public key of a designated data user and then uploads them to the cloud together with encrypted data.Afterwards, when the data user wants to retrieve data containing a specific keyword, he generates a search token for the keyword with his secret key and sends it to the cloud server.Once the cloud server receives the above search token, it performs well-designed search algorithm to check if the data containing the expected keywords and returns the matched data to the user.

To date, PEKS make considerable progress in strengthening security, enriching functionality,and facilitating efficiency [6-8].Nevertheless, most of these PEKS constructions are built under the traditional hardness assumptions like discrete logarithm problem.As pointed out in [9],the quantum computers of the near future hold a high potential to invalidate these schemes.More urgently, researchers have made breakthrough progress in quantum computers [10].Most recently, some initial efforts have been made from lattice [11-14], opening a direction to designing quantum secure encrypted search schemes.Following this way, in this paper, we will focus on the investigation of quantum secure encrypted search schemes and develop a new PEKS scheme with better performance in security and efficiency.

1.1 Our Motivation

The first problem we aim to address is the integrity of the search result.Note that, the realworld cloud server is always semi-honest-but-curious [15], it may intentionally return partial search or even unmatched results to the user for saving its cost.This is not a new problem in traditional PEKS, many researchers propose to use verifiable PEKS to solve this problem.Specifically, a verification block is adopted and will be sent to the user, together with the search result.The user can use this block to verify if the search result is integral.However, to the best of our knowledge, few lattice-based verifiable searchable encryption schemes have been known before.For this concern, our first effort is to design a verifiable PEKS from lattice.Our key idea is to design a verification algorithm, which can be imposed on existing lattice-based PEKS schemes directly.To achieve this goal, we introduce a lattice-based delegation algorithm, which can flexibly generate the verification block under the circumstance of semi-honest-but-curious server.

Based on the above result, our second problem is how to deploy the above verifiable PEKS scheme to an IoT system.Observe that, in a public-key cryptosystem, before encrypting the data,a user always needs to verify the authenticity of a public-key.However, the public key in a latticebased encryption scheme is usually made up of some high-dimension matrices, transmitting these matrices through source-limited sensors is infeasible.Inspired by Zhang et al.’s ideal [13], we deal with this problem by introducing the identity-based encryption mechanism, where a small size identity-tag is used to denote the public key of the user.In particular, when a user enrolls, he registers the system with his individual identity and gets a credential from the central authority as his secret key.After that, he uses this identity and corresponding secret key to perform encryption and verification operations.

1.2 Our Contributions

In light of the above observations, our contributions can be summarized as follows:

(1) We propose the first verifiable PEKS scheme from lattice to check the result integrity of a quantum secure search scheme.

(2) We introduce the philosophy of identity-based encryption mechanism and use it to mitigate the heavy communication cost in public key authentication.

(3) We compare our scheme with some closely-related works, and the results demonstrate that our scheme performs better than prior arts in efficiency.

Organizations.The rest of this paper is organized as follows.In Section 2, we introduce some related work.The proposed system overview, corresponding threat model and design goals are presented in Section 3.In Section 4, we first introduce preliminaries, including the lattice-based knowledge, the hardness problem and some algorithms.Then we define the VIBKS scheme with the security model.In Section 5, we show the construction of our lattice-based VIBKS scheme, as well as its correctness and verifiability proof.In Section 6, we provide the security proof of our scheme.The theoretical comparison and performance analysis are presented in Section 7.Finally,we give a short conclusion in Section 8.

2 Related Work

With the rapid increase of data volume from quantities of IoT devices, cloud storage technology plays an increasingly crucial role in IoT.In terms of data confidentiality, it becomes prevalent to use cloud storage data encryption services.To achieve the goal of searching over encrypted data outsourced to the cloud server without leaking information about the messages shared by the data sender, searchable encryption (SE) is one of the essential approaches.SE is divided into symmetry searchable encryption and asymmetric searchable encryption.The SSE scheme was firstly introduced in [4].Although the SSE scheme is with relatively high computational efficiency,it is only suitable for a single user model, but could not be well applied in multi-user model.

PEKS based on conventional hardness assumption.The first PEKS scheme was proposed to enable one to search over encrypted data generated by public key system [5].Following with Boneh et al.’s work [5], a multitude of PEKS schemes that achieve various kinds of functionality are proposed [6-8].Park et al.[6] considered the need for conjunctive keyword query and proposed the first public key encryption with conjunctive field keyword search scheme.To fill the gap in the area of fuzzy search on encrypted data, a PEKS scheme supporting fuzzy keyword query was proposed by Xu et al.[7].Besides, schemes support proxy re-encryption with keyword search under the assistance of the proxy were proposed in [8].However, the mentioned schemes above are all fragile to the attack from quantum computers.

PEKS based on lattice assumption.Lattice has been widely used to construct cryptosystems that can resist the near future quantum computer.The first PEKS built for quantum security is proposed by Gu et al.[11], whose security can be reduced to LWE assumption in the standard model.To further pursue the practicability, several lattice-based works have been proposed to support fine-grained access control [12], proxy-oriented search [13], conjunctive keyword search [14],verifiable search [15].In addition to extending the functionality, researches on resisting varieties of attack methods have been sufficiently developed.In order to ensure the security when the scheme suffers from key-exposure problems, Zhang et al.[16] constructed a scheme satisfying the forward security in the quantum security level.Besides, keyword guessing attack is practical in PEKS as the keywords in real-life are with inherently low entropy.To prevent inside KGA, Yu et al.[17] employed the preimage sample algorithm on a random bit and a part of ciphertext,which prevents the malicious server from forging a valid ciphertext.

Verifiable searchable encryption.The verifiable search has been substantially developed in the plaintext retrieval using special data structures (e.g., signature and merkle tree) in case a malicious cloud server returns false results or conceals data loss incidents.For example, in 2010, Benabbas et al.[18] presented the first practical verifiable computation scheme for high degree polynomial functions.In the encrypted data search scenario, Zheng et al.[19] utilized bloom filter and signature algorithm to verify whether the cloud has faithfully executed the search operations,and proposed two different schemes, i.e., KP-ABKS and CP-ABKS.Sun et al.[15] proposed a scheme to enable authenticity check over the returned search result in the multi-user multi-datacontributor search scenario.Miao et al.[20] constructed the Verifiable SE Framework (VSEF),which can withstand the inside KGA and achieve verifiable searchability.Wu et al.[21] presented a new authenticated data structure based on homomorphic encryption, and shows how to apply it to verify the correctness and completeness of search results.However, the verification proof in their scheme is generated by the cloud server, who can forge the proof to pass the verification when it is viewed as an adversary.In summary, the above verifiable searchable encryption schemes seldom consider how to ensure the integrity of returned data when the cloud server is semi-honest-but-curious and equipmented with quantum computers.

3 Problem Statement

In this section, we will first give a high-level description of our proposed scheme and introduce the role of each participant involved in.Then, to explicitly show the capability of each party,we define the threat model.

3.1 System Overview

As shown in Fig.1, we illustrate the architecture of the proposed VIBKS in an IoT system.The designed scheme is consisted of four entities:central authority (CA), cloud server (CS), IoT sensor (IoTs) and data receiver (DR).

Figure 1:System overview

? CA:CA is assumed full responsibility for key generation and public parameters generation.

? IoTs:IoTs is the sensor deployed in an IoT system, who holds the duty that transmits data to CS over the Internet.Specifically, the transmitted data requires to be encrypted before sent to CS.To further pursue the goal of data verification, a verification block is attached.

? DR:DR is authorized by IoTs, it holds the ability of keyword retrieval and result verification.The former is realized by submitting search token, while the latter is due to the verification block generated by IoTs.

? CS:CS is mainly responsible for two aspects of work in the system, the first is to store the encrypted data with keyword ciphertexts and verification block, the second is to perform test operation.

Overview.Here we elaborate on the implementation process of the proposed scheme with Fig.1.First of all, the CA generates the system public parameters and the master secret key,with which it generates the corresponding identity secret key according to the tag submitted by other entities later.After obtaining tags of IoTs and DR, CA sends the public and secret key pairs to each entity.IoTs generates the keyword ciphertexts to allow the DR visit its data and compute the verification block for integrity check, which are sent with the encrypted data to CS.When DR wants to obtain ciphertexts corresponding to a keyword, the secret key will be used to create a keyword-oriented token, which is transmitted to the CS subsequently.Then, by testing whether the token and keyword ciphertexts match, the corresponding results (including encrypted data, data identity sets and verification blocks) are returned.Finally, DR decrypts the encrypted data and detects the correctness and integrity of results.

3.2 Threat Model

First of all, CA is supposed to be completely trusted in our model, who knows the secret key of the whole system but never launch an attack on the system.Then, we primarily stress that the server in our model behaves entirely in a “semi-honest-but-curious” fashion, as described in some previous literature.We assume that the server will not honestly follow the algorithm we set up and possibly returns a fraction of results or unrelated files.Lastly, in our model, IoTs with plaintexts and DR with search capability are both considered reliable, which means they are not considered the outside adversary.

To prove the security of VIBEKS under the above threat model, we follow the security definition of ciphertext indistinguishability.Details will be provided in Section 4.2.

3.3 Design Goals

In order to achieve secure and efficient searchable encryption over IoT data, we design our scheme to accomplish the following objects:

(a)Efficiency.It may involve some operations with high computational cost when designing a lattice-based SE scheme, e.g., matrix inverse operation.In order to gain higher efficiency,considering constructing the scheme in which the matrix inverse operation need to be performed only once.

(b)Security.Our scheme should achieve ciphertext indistinguishability under selective-ID attacks.The quantum computer cannot violate the privacy of outsourced data as it does for some SE schemes based on traditional hardness problems.Lattice-based tools are deployed in our scheme and the security of our scheme is based on the LWE problems,which has been proved to be secure under the attack from quantum computer.

(c)Functionality.Our scheme also aims to enable verifiable search on encrypted outsourced data.Verifiable search is more practical than the common encrypted search, since quantities of deceptions occur every day.The lattice-based delegation algorithm applied in the proposed scheme makes sure that any cheated behavior of server can be recognized by the user.

4 Preliminaries

4.1 Lattice and Hardness Problem

Now, we first give some notations applied in our scheme and definitions about lattice-based cryptography as follows.

NotationZ denotes the set of integers.The bold font denotes vector.denotes the Gram-Schmidt norm of matrixA, whereis the Gram-Schmidt orthogonalization ofA.

Definition 4.1Given two random variablesxandyon a countable setS, there is a defined function Δ(x,y)=as statistical distance.If the distanced(λ)=Δ(x(λ),y(λ))is negligible inλ, we sayxandyare statistically close.

Definition 4.2Letbi∈Rmfori∈{1,...,n} be some linearly independent vectors andB={b1,...,bn}.The m-dimensional latticeΛgenerated by the above vectors is Λ(B)=Z}.Heremis the dimension andnis the rank.Whenn=m, the lattice is full-rank.The basis of the latticeΛis {b1,...,bn}.

Definition 4.3[8] Given a matrixA∈a vectorand a primeq, define:

(1)Λ⊥q(A):={e∈Zm|Ae=0mod q},

(2)Λuq(A):={e∈Zm|Ae=u mod q},

(3)Λq(A):={μ∈Zmq|?s∈Znq,μ=ATs mod q}.

The ciphertext indistinguishability of VIBKS can be reduced to the learning with errors(LWE) problem.We introduce the LWE problem as follows.

Definition 4.4[22] Given a primeq, a positive integern, and a Guassian noise distribution χ over Zq, for a vectors∈, the LWE problem is to distinguish the distribution between the following two distributions:

(1) LWE distribution:samples are in the form of(v,u)=(v,vTs+e), wherevis a random vector chosen from,eis a sample drawn from distribution χ.

(2) Uniform distribution:samples are uniformly chosen from×Zq.

Then, we introduce the TrapGen algorithm and preimage sampleable algorithm SamplePre,which are utilized in Setup, Encrypt and TokGen of the proposed scheme.

Definition 4.5[23] The probabilistic polynomial-time (PPT) algorithm TrapGen(q,n)generates a uniformly random matrixA∈together with a short basissatisfyingwith all but negligible probability inn.

Definition 4.6[24] Given a matrixA∈with basisa vectorμ∈Znq,m≥2n「logq, and a parameteras inputs, the PPT algorithm SamplePre(A,TA,μ,σ)generates a vectort∈sampled from a distribution statistically close tosuch thatAt=μmodq.

Then we give the definition of the lattice basis delegation BasisDel [25], which is used in the private key derivation in our VIBKS scheme.

Definition 4.7[25] Given a matrixA∈with a short basisinvertible matrixRsampled fromDm×m, and a parameteras inputs,wherethe PPT algorithm BasisDel(A,TA,R,δ)generates a random short lattice basisTBof Λ⊥q (B), whereB=AR?1.

Finally, to prove the ciphertext indistinguishability of our scheme, we introduce a PPT algorithm SampleR, referring to [24], to sample matrices from a distribution statistically close toDm×mover.Moreover, we employ a PPT algorithm SampleRwithBasis to simulate a random short lattice basis, which is defined as follows.

Definition 4.8[25] Given a primeq>2,m≥2n「logq, a matrixA∈as inputs, the PPT algorithm SampleRwithBasis(A)generates a low-form matrixRwhich is statistically close toDm×moverand a random short lattice basisTBof(B), whereB=AR?1, such thatwith an overwhelming probability.

4.2 VIBKS and Security Definition

A formal definition of VIBKS is given in the following part.

Definition 4.9VIBKS consists of the following six algorithms.

(1)Setup(1n):This probabilistic algorithm is run by the CA to setup the system.It inputs a security parameternand returns the public parameter PP, the master secret key MSK.

(2)KeyDerive(PP, MSK,τ):This probabilistic algorithm is run by the CA to derive keys for users.It inputs the public parameter SP, the master secret key MSK and the user’s tagτ,and returns the private key skτand public key pkτfor the user.

(3)Encrypt(PP,τ,w,F,KS):This probabilistic algorithm is run by the IoTs to generate the keyword ciphertexts tuple set and the verification tuple set.It inputs the public parameter PP, the tagτof data receiver, the keywordw, the file setFand the keyword setKS, and returns the keyword ciphertext tuple setCTand verification tuple setVT.

(4)TokGen(PP,τ, skτ,w*):This probabilistic algorithm is run by the receiver whenever he wants to search for some files containing the keywordw*.It inputs the keywordw*, the user’s private key skτand the public parameter PP, and returns the search tokenSTw?.

(5)Test(CT,STw?):This algorithm is run by the cloud server to search for the matched files containing the keywordw?.It inputs the search tokenSTw?and the keyword ciphertext tuple setCTand verification tuple setVT, and returns the corresponding file setRwith its verification blockV, otherwise returns nothing.

(6)Verify(R,V):This algorithm is run by the data receiver to verify if the cloud server returns the correct and complete results.

The formal definition given above shows that our proposed VIBKS scheme provides the function of result verification, i.e., data receiver can check if the cloud server honestly performs the test operation and returns complete results.For security, we introduce a security game to define the security model of our proposed scheme.

Definition 4.10Given the security parametern, the game is carried out between an adversaryAand a challengerC.

Setup:Take the security parameternas input,Coutputs the system public parameters PP and sends it toA.Asubmits a target identityid?rtoC, and then it adaptively queries the following oracles.

KeyDerive oracle:Upon receiving the KeyDerive query onidfromA, where the only restriction isid/=id?r,Cgenerates the private keyskidand returns it toA.

TokGen oracle:Upon receiving the TokGen query onwfromA,Cgenerates the search tokenstwand returns it toA.

Challenge phase:After finishing the above queries,Asends(id?r,w?0,w?1)toC, wherew?0,w?1are two different randomly chosen keywords that have never been queried in the above oracles,id?ris the target identity.Crandomly chooses a bitb∈{0,1}, and returns a random searchable ciphertext tupleC?=(c?0,c?1)toA.

Acontinues to query the TokGen oracle as above, the only restriction is that neitherw?0norw?1can be queried to obtain its search token.

Guess:Finally,Aoutputs a bitb′∈{0,1}.It wins the game if and only ifb′=b.

The probability ofAwinning the above game is defined as

Definition 4.11We say that our VIBKS scheme achieves ciphertext indistinguishability under the selective-ID attack if AdvA(n)is negligible for any PPT adversaryA.

5 Our Construction

As introduced in Section 3, our scheme is composed of six algorithms, which will be described one by one in this section.Note that, we adopt a symmetric encryption schemeSE=(KeyGen,Enc,Dec)to encrypt data files.

5.1 Intuition Behind Our Construction

After we noticed that the existing lattice-based SE schemes only consider the server is honestbut-curious, we began to think about efficient lattice-based SE scheme that can thwart the server perform lazy search (i.e., search only a fraction of data or fooling users with previous search results) or return unfaithful result.Bloom filter can achieve this, but we want to avoid its false positive rate.We notice that we can solve this by adopting signature technique.The idea is to combine an efficient hash function with a lattice-based delegation algorithm to make sure that the verification result is deterministic, which implies that the user can check the completeness and correctness with 100% accuracy.

5.2 Construction

Now we describe the construction details of our lattice-based VIBKS scheme.It is composed of the following six polynomial-time algorithms.

Setup:Taking as input a security parametern, CA generates the system public parameters q,m,σ,α,s, whereqis prime,sis the gaussian parameter.Then CA performs the following steps:

(1) Set two secure hash functionH1:{0,1}l1→,H2:{0,1}l2→,H3:{0,1}?→,where the outputs ofH1are distributed inDm×m.

(2) InvokeTrapGen(q,n)to generate a uniformly random matrixA0∈together with a short basisTA0∈for(A0).

(3) Select a uniformly random vectort∈Znq.

Finally, CA outputs the system public parameters PP and master secret key MSK given by MSK=TA0, PP=(q,m,n,l1,l2,σ,α,s,t,A0,H1,H2,H3).

KeyDerive:Taking as inputs the system public parameters PP, the master secret key MSK and a tagτ∈{0,1}l1, CA generates the public and secret key pair for the tag-belonged IoTs as follows:

(1) Compute the tag-matrixRτ=H1(τ)∈.

(2) Runskτ←BasisDel(A0,Rτ,TA0,s)to obtain a short random basis for Λ⊥q (pkτ), wherepkτ=A0Rτ?1.

Finally, CA sends the private keyskτand the public keypkτto the IoTs whose tag isτ.

Encrypt:Taking as inputs the system public parameters PP, the file setF={F1,...,Fh}, the keyword setKS={w1,...,wu}, the IoTs’s key pair(sko,pko), the receiver’s tagτ∈{0,1}l1, the IoTs generates the keyword ciphertext tuple and the verification tuple as follows:

(1) For each fileFiinF, generate the symmetric keysk=SE·KeyGen(1n)and encrypt the file with it to get the ciphertextCi=SE·Enc(sk,Fi).

(2) For each keywordwij∈{0,1}l2in fileFi, first compute the tag-matrixand setthen compute the keyword-vectorGwij=t+H2wij∈Znq,finally compute the keyword ciphertextscij=where r is a uniformly random vector from Znq,x∈Zqand y ∈Zmqare noise vectors chosen fromandrespectively.

(3) LetCTi=(Ci,{cij|wij∈Fi})be the keyword ciphertext tuple ofFi.

(4) For each keywordwk∈KS, first generate the keyword ciphertextckas in step 2, then computehwk=H3(id1‖...‖idz‖wk)∈Znq, where {id1,...,idz}is the identity set of files containing the keywordwk, finally evaluate the verification blockVk←SamplePre(pks,sks,hwk,σ).Note thatVk·pks=hwk∈Znq, and the verification block is distributed in

(5) LetVTk=(ck,Vk)be the verification tuple of keywordwk.

Finally, the IoTs outsources the keyword ciphertext tuple setCT={CTi}(i∈{1,...,h})and the verification tuple setVT={VTk}(k∈{1,...,u})to the cloud server.

TokGen:Taking as inputs the system public parameters PP, the receiver’s tagτ∈{0,1}l1, the keywordw?∈{0,1}l2and the secret keyskτ∈, the data receiver computes the search token for searching as follows:

(1) Compute the tag-matrixRτ=H1(τ)∈and setFτ=A0Rτ?1∈.

(2) Compute the keyword-vectorGw?=t+H2(w?)∈Znq.

(3) Setstw?←SamplePre(Fτ,skτ,Gw?,σ).Note thatFτstw?=Gw?∈Znq, and the search token is distributed in

The data receiver sends the search tokenstw?to the cloud server.

Test:Taking as inputs the keyword ciphertext tuple setCT, the verification tuple setVTand the search tokenstw?, the cloud server searches for the matched files and the verification block as follows:

(1) For each keyword ciphertext tupleCTi∈CT, check if the fileFicontains the same keyword asstw?.To achieve this goal, for allcij∈CTi, computeγij=if there existγij, such that |γij|≤q/4」, add the corresponding encrypted fileCito the result setR.Otherwise, the cloud server aborts.

(2) For each verification tupleVTk∈VT, computeif |γk|≤q/4」, return the verification blockVk.Otherwise, the cloud server aborts.

The cloud server returns the result setRand the verification blockVkto the data receiver.

Verify:Taking as inputs the result setRand the verification blockVk, the data receiver verifies if the cloud server returns the integral results as follows:

(1) Decrypt the returning ciphertextsFi=SE.Dec(sk,Ci).

(2) Compute hw=H3(id1‖...‖idh‖w?)∈Znq, wherew?is the queried keyword, {id1,...,idh}is the identity set of the returned files.

(3) Check whether the equationpkoVk=hw?holds, and whetherVkis distributed inIf they hold, it implies that the cloud server has faithfully returned all results.Otherwise,the cloud server behaviors dishonestly.

5.3 Correctness of VIBKS

Let(skτ,pkτ)be the data receiver’s key pair,wbe the keyword contained inCTwandw?be that instw?.InTest, take the tokenstw?as the input, the cloud server can computeγas follows:

Whenw=w?,γ=x?stTwy, as discussed in [23],Whenw/=w?, asγx?stTwy,thus we conclude that the ciphertextCTwand the token contain different keyword.

5.4 Verifiability of VIBKS

Let {id1,...,idh}be the identity set of decrypted files,Vbe the verification block,pkobe the public key of data owner.InVerify, the data receiver computes hw=H3(id1‖...‖idh‖w?)andpkoVk.When the identity set of decrypted files is the same as the file identity setIDwthat the data owner embeds in the verification block, the equationpkoVk=hw?holds from the definition of algorithm SamplePre.Thus, we come to the conclusion that the cloud server has returned the correct and complete results.Otherwise, we consider that the cloud server performs unfaithfully.

6 Security

In this section, we will give the security proof of our proposed scheme.

Theorem 6.1VIBKS from lattice achieves ciphertext indistinguishability under the selective-ID attack in the random oracle model, provided that the hardness assumption of decisional-LWE problem holds.

Proof.LetAbe an adversary, which breaks the ciphertext indistinguishability under the selective-ID attack with a non-negligible probabilityεin the random oracle model.We construct a challengerCwith a non-negligible probability solving the hardness assumption of LWE problem.

Setup:Crequests from LWE oracleOform+1 times to obtain fresh pair(uk,vk)∈Znq×Zq, wherek=0,1,...,m.Then sets two listsL1,L2,L3, and letqHibe the maximum number ofA’s queries toHi, wherei=1,2,3.Finally,Cprepares the system public parameters PP forAas follows.

(1)Csamples a random matrixR?←Dm×mby running SampleR.

(2)Cconstructs a random matrixF?←frommof the given LWE samples, where thek-th column ofF?be the vectoruk∈for allk=1,...,m.

(3)CsetsA0=F?R?, whereA0is uniform insinceR?∈are invertible moduloqandF?is uniform inCalso lett=u0, and finally sets PP=(A0,t,H1,H2,H3)and sends it toA.Ahead of time, the target identity isid?rsubmitted byA.

Note that, regardless whenAperforms the KeyDrive oracle query, it has made all relevantH1queries before.Now,Aperforms the following queries.

H1query:For thel-th query, wherel= 1,2,...,qH1,Aqueries toH1on any identityidadaptively.Ifl=I?1, such thatid=id?r,CsetsH1(id)=R?and returns it toA.Otherwise,Cruns SampleRwithBasis(A0)to obtain a random matrixand a short random lattice basisThenCaddsto listL1, and returnsRidtoA.

H2query:For thel-th query, wherel=1,2,...,qH2,Aqueries toH2on any keywordwadaptively.Ifl=qH2, such thatw=w?,CsetsH2(w)=t0?t=t0?u0and adds it to listL2, then returns it toA.Otherwise,CsetsH2(w)=t0, wheret0←Znqand adds it to listL2, then returns it toA.

KeyDerive oracle:Upon receiving the KeyDerive query onidfromA, where the only restriction isid/=id?r,Cchecks the listL1to findif it is found,CreturnsTidtoA.Otherwise,Cperforms the same operation asH1query onid, obtainsand returnsTidtoA.

TokenGen oracle:Upon receiving the TokenGen query onwfromA, where the only restriction isid/=id?r,Cfinds (id,A0,Rid,Tid) in listL1andt0in listL2, it they are found,CcomputesGw=t+t0and runs SamplePre(A0,Tid,Gw,σ)to obtainstw.Finally,CreturnsstwtoA.

Challenge phase:Asends(id?r,w?0,w?1)toC, wherew?0,w?1are two different keywords that have never been queried before,id?ris the challenge identity.Crandomly chooses a bitb∈{0,1}, ifb=0,Creturns a random searchable ciphertextC?=(c?0,c?1)toA.Otherwise,Cperforms as follows:

For eachk=0,1,...,m, retrievevk∈Zqfrom LWE instance, setv?=(v1,v2,...,vm)T∈Zmq,and setc?0=v0,c?1=v?.Finally,Creturns the searchable ciphertextC?=(c?0,c?1)toA.

Guess:At last,Aoutputs its guessb′∈{0,1}.

The goal ofAis to decide which keyword is contained in the challenged ciphertextC?,since the challengerCreturns the searchable ciphertext which is associated with each keyword with probability 1/2.Now, we evaluate the probability ofAin breaking the ciphertext indistinguishability under the selective-ID attack in the random oracle model.With the system public parameters PP, we haveandc?0=v0=t0Tr?+x?c?1=v?=F?Tr?+y?for some random valuesx?∈Zqand vectorsr?∈Znqandy?∈Zmqwith Gaussian distribution.Therefore,c?0,c?1have the correct ciphertext form.We assume thatAcan successfully guess the keywordw?0is associated with the ciphertextC?with the probabilityε, where the keywordw?0is theqH2-thH2query whenw?0=w?with the probability 1/qH2.Whenid?ris theI?1-thH1query, it occurs with the probability 1/qH1.Thus, ifAbreaks the ciphertext indistinguishability under the selective-ID attack with a non-negligible probabilityεin the random oracle model,Ccan solve the hardness assumption of decisional-LWE problem with the non-negligible probabilityε′=ε/(2qH1qH2), which is contradictory.Consequently, AdvA(n)is negligible, and VIBKS achieves ciphertext indistinguishability under the selective-ID attack in the random oracle model.

7 Performance Analysis

7.1 Theoretical Analysis

In this section, we show a theoretical performance comparison of our proposed scheme and some other searchable encryption schemes [13,16,20].First, we give the theoretical analysis of the computation overhead of keyword encryption, token generation, test operation, and verification process.Moreover, we describe the hardness problems on which the security models of each scheme are based.Finally, with regard to the functionalities, we describe the verifiability and post-quantum security.

Now, we specify some notations used in the comparison below.In particular, m denotes the number of results, E denotes the modular exponentiation operation, h denotes the hash operation which maps the arbitrary string into G, P denotes the bilinear pairing operation, H denotes the hash operation which maps the arbitrary string into a matrix.I denotes the matrix inversion operation, M denotes the matrix multiplication operation, BD denotes the BasisDel, SP denotes the SamplePre.The performance comparison is listed in Tab.1.

Table 1:Performance comparison

7.2 Experiment Analysis

In this section, we conduct experiments of our proposed scheme in a laptop using Matlab R2017a.The environment is Windows 10 Ultimate (x64) with an Intel (R) Core (TM) i7-10750H CPU@2.60 GHz.We set the parametersm≥6nlogq.The security level of [13,16] is set tol=10,as it utilized in their experiments.Under the above parameters, the time cost of SamplePre, hash operation and matrix multiplication are about 0.326574 s, 0.13221 s, and 0.028051 s respectively,which are far less than 183.067383 s required for matrix inverse operation.Therefore, we can only pay attention to the time cost of matrix inverse when considering the performance of algorithms that involves matrix inverse.

As shown in Tab.1, although the theoretical computation cost ofEncryptin both [13,16]and our scheme contains matrix inverse operation, we found that the efficiency of our scheme is much higher than that of [13,16] in experiments.The advantage is due to that in our scheme,inverse matrix is only related to the user’s identity.It indicates that the matrix inverse operation can be done before theEncryptprocess and keep it locally for the nextEncryptprocess.In [13,16],the keyword-related matrix needs to be inversed, so that the matrix inverse operation must be conducted once the keyword updates, which brings huge computation overhead.For the same reason, the efficiency ofTokGenin our scheme is superior to that of [13,16].Indeed, our scheme enjoys a greater advantage inTokGenbecause of the additional BasisDel overhead in [13,16].

Fig.2 provides the comparison of test time with the increasing of the number of keywords.The left graph of Fig.3 proves that our scheme and the scheme in [13] spend less time to complete the test no matter what the number of keywords is.The scheme in [20] involves time-consuming operation (i.e., bilinear pairing) when matching the token and encrypted keywords.We can observe thatTestin [20] consumes around 9 times more computation time than that in [16] with the same number of keywords.Then, we consider the test time comparison of our scheme and [13,16],which are all constructed based on lattice hardness assumptions.From the left figure of Fig.2,we can also see that the test time of [16] and our scheme is almost the same, far less than that in [13].In order to further explore the relationship of time cost in [16] and our scheme, we list them in the right figure of Fig.2.When the number of keywords is 100, we observe that our scheme and [16] take about 0.126 ms and 0.333 ms, respectively.The results again confirm the superiority of our scheme.

Figure 2:Comparison of Test

With respect toVerify, we implement the experiments to compare the verification time of our scheme and the basic scheme in [20].As the basic scheme in [20] supports multi-keyword search, we set the number of keywords in one query to 1 to facilitate comparison.Furthermore,from Tab.1, we can see that the performance of [20] inVerifydepends on the number of results.In Fig.3, we set the number of results to 1, which is the optimal case for [20].Under the above setting, we notice that the performance of our scheme is significantly better than [20]as the verification times increases.It costs only 0.106 s to finish 100 times verification in our scheme, while it costs 2.899 s in [20].The reason is that the scheme in [20] adopts time-consuming operations such as bilinear pairing and modular exponentiation, while our proposed scheme only involves in efficient matrix multiplication and hash operations.

Figure 3:Comparison of Verify

8 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.This paper proposes a lattice-based VIBKS scheme that can detect the misbehavior of cloud server and resist quantum computing attack.In the scheme, we use the preimage sample algorithm to generate a verification block for keyword ciphertext, which can be utilized by users to verify if the server returns correct and complete results.Then, we prove that our proposed scheme is secure under the selective-ID attack, and achieves both correctness and verifiability.Finally, we give theoretical and experimental comparisons with other searchable encryption schemes.The results demonstrate that our scheme achieves a better balance in efficiency and security.As future works, we consider the construction of lattice-based PEKS schemes with rich query functions.

Funding Statement:This work is supported by the National Natural Science Foundation of China (No:62072240) and the National Key Research and Development Program of China (No.2020YFB1804604).

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.