|Computers, Materials & Continua |
Verifiable Identity-Based Encryption with Keyword Search for IoT from Lattice
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
*Corresponding Author: Chungen Xu. Email: email@example.com
Received: 19 January 2021; Accepted: 24 February 2021
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-honest-but-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
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 .
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)  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 . 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 , 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 . 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 real-world cloud server is always semi-honest-but-curious , 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 lattice-based 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 , 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 . 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 . Following with Boneh et al.’s work , a multitude of PEKS schemes that achieve various kinds of functionality are proposed [6–8]. Park et al.  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. . Besides, schemes support proxy re-encryption with keyword search under the assistance of the proxy were proposed in . 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. , 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 , proxy-oriented search , conjunctive keyword search , verifiable search . 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.  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.  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.  presented the first practical verifiable computation scheme for high degree polynomial functions. In the encrypted data search scenario, Zheng et al.  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.  proposed a scheme to enable authenticity check over the returned search result in the multi-user multi-data-contributor search scenario. Miao et al.  constructed the Verifiable SE Framework (VSEF), which can withstand the inside KGA and achieve verifiable searchability. Wu et al.  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).
• 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.1 Lattice and Hardness Problem
Now, we first give some notations applied in our scheme and definitions about lattice-based cryptography as follows.
Notation denotes the set of integers. The bold font denotes vector. denotes the Gram-Schmidt norm of matrix A, where is the Gram-Schmidt orthogonalization of A.
Definition 4.1 Given two random variables x and y on a countable set S, there is a defined function as statistical distance. If the distance is negligible in , we say x and y are statistically close.
Definition 4.2 Let for be some linearly independent vectors and . The m-dimensional lattice generated by the above vectors is . Here m is the dimension and n is the rank. When n = m, the lattice is full-rank. The basis of the lattice is .
Definition 4.3  Given a matrix , a vector and a prime q, define:
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  Given a prime q, a positive integer n, and a Guassian noise distribution over , for a vector , the LWE problem is to distinguish the distribution between the following two distributions:
1. LWE distribution: samples are in the form of , where is a random vector chosen from , e is a sample drawn from distribution .
2. Uniform distribution: samples are uniformly chosen from .
Then, we introduce the algorithm and preimage sampleable algorithm , which are utilized in Setup, Encrypt and TokGen of the proposed scheme.
Definition 4.5  The probabilistic polynomial-time (PPT) algorithm generates a uniformly random matrix together with a short basis for , satisfying , and with all but negligible probability in n.
Definition 4.6  Given a matrix with basis of , a vector , , and a parameter as inputs, the PPT algorithm generates a vector sampled from a distribution statistically close to , such that .
Then we give the definition of the lattice basis delegation , which is used in the private key derivation in our VIBKS scheme.
Definition 4.7  Given a matrix with a short basis of , a -invertible matrix R sampled from , and a parameter as inputs, where , the PPT algorithm generates a random short lattice basis TB of , where B = AR−1.
Finally, to prove the ciphertext indistinguishability of our scheme, we introduce a PPT algorithm , referring to , to sample matrices from a distribution statistically close to over . Moreover, we employ a PPT algorithm to simulate a random short lattice basis, which is defined as follows.
Definition 4.8  Given a prime q > 2, , a matrix as inputs, the PPT algorithm generates a low-form matrix R which is statistically close to over , and a random short lattice basis TB of , where B = AR−1, such that with an overwhelming probability.
4.2 VIBKS and Security Definition
A formal definition of VIBKS is given in the following part.
Definition 4.9 VIBKS 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 parameter n and 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 keyword w, the file set F and the keyword set KS, and returns the keyword ciphertext tuple set CT and verification tuple set VT.
4. TokGen (PP, , sk, w*): This probabilistic algorithm is run by the receiver whenever he wants to search for some files containing the keyword w*. It inputs the keyword w*, the user’s private key sk and the public parameter PP, and returns the search token STw *.
5. Test (CT, ): This algorithm is run by the cloud server to search for the matched files containing the keyword w*. It inputs the search token STw * and the keyword ciphertext tuple set CT and verification tuple set VT, and returns the corresponding file set R with its verification block V, 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.10 Given the security parameter n, the game is carried out between an adversary and a challenger .
Setup: Take the security parameter n as input, outputs the system public parameters PP and sends it to . submits a target identity to , and then it adaptively queries the following oracles.
KeyDerive oracle: Upon receiving the KeyDerive query on id from , where the only restriction is , generates the private key skid and returns it to .
TokGen oracle: Upon receiving the TokGen query on w from , generates the search token stw and returns it to .
Challenge phase: After finishing the above queries, sends to , where are two different randomly chosen keywords that have never been queried in the above oracles, is the target identity. randomly chooses a bit , and returns a random searchable ciphertext tuple to .
continues to query the TokGen oracle as above, the only restriction is that neither nor can be queried to obtain its search token.
Guess: Finally, outputs a bit . It wins the game if and only if .
The probability of winning the above game is defined as .
Definition 4.11 We say that our VIBKS scheme achieves ciphertext indistinguishability under the selective-ID attack if is negligible for any PPT adversary .
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 scheme 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 honest-but-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.
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 parameter n, CA generates the system public parameters , where q is prime, s is the gaussian parameter. Then CA performs the following steps:
1. Set two secure hash function , , , where the outputs of H1 are distributed in .
2. Invoke to generate a uniformly random matrix together with a short basis for .
3. Select a uniformly random vector .
Finally, CA outputs the system public parameters PP and master secret key MSK given by , .
KeyDerive: Taking as inputs the system public parameters PP, the master secret key MSK and a tag , CA generates the public and secret key pair for the tag-belonged IoTs as follows:
1. Compute the tag-matrix .
2. Run to obtain a short random basis for , where .
Finally, CA sends the private key and the public key to the IoTs whose tag is .
Encrypt: Taking as inputs the system public parameters PP, the file set , the keyword set , the IoTs’s key pair , the receiver’s tag , the IoTs generates the keyword ciphertext tuple and the verification tuple as follows:
1. For each file Fi in F, generate the symmetric key and encrypt the file with it to get the ciphertext .
2. For each keyword in file Fi, first compute the tag-matrix and set , then compute the keyword-vector , finally compute the keyword ciphertexts , where is a uniformly random vector from , and are noise vectors chosen from and respectively.
3. Let be the keyword ciphertext tuple of Fi.
4. For each keyword , first generate the keyword ciphertext ck as in step 2, then compute , where is the identity set of files containing the keyword wk, finally evaluate the verification block . Note that , and the verification block is distributed in .
5. Let be the verification tuple of keyword wk.
Finally, the IoTs outsources the keyword ciphertext tuple set and the verification tuple set to the cloud server.
TokGen: Taking as inputs the system public parameters PP, the receiver’s tag , the keyword and the secret key , the data receiver computes the search token for searching as follows:
1. Compute the tag-matrix and set .
2. Compute the keyword-vector .
3. Set . Note that , and the search token is distributed in .
The data receiver sends the search token stw* to the cloud server.
Test: Taking as inputs the keyword ciphertext tuple set CT, the verification tuple set VT and the search token stw*, the cloud server searches for the matched files and the verification block as follows:
1. For each keyword ciphertext tuple , check if the file Fi contains the same keyword as stw*. To achieve this goal, for all , compute , if there exist , such that , add the corresponding encrypted file Ci to the result set R. Otherwise, the cloud server aborts.
2. For each verification tuple , compute , if , return the verification block Vk. Otherwise, the cloud server aborts.
The cloud server returns the result set R and the verification block Vk to the data receiver.
Verify: Taking as inputs the result set R and the verification block Vk, the data receiver verifies if the cloud server returns the integral results as follows:
1. Decrypt the returning ciphertexts .
2. Compute , where is the queried keyword, is the identity set of the returned files.
3. Check whether the equation holds, and whether Vk is distributed in . If 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 be the data receiver’s key pair, w be the keyword contained in CTw and w* be that in stw*. In Test, take the token stw* as the input, the cloud server can compute as follows:
When w = w*, , as discussed in , . When , as , , thus we conclude that the ciphertext CTw and the token contain different keyword.
5.4 Verifiability of VIBKS
Let be the identity set of decrypted files, V be the verification block, pko be the public key of data owner. In Verify, the data receiver computes and pkoVk. When the identity set of decrypted files is the same as the file identity set IDw that the data owner embeds in the verification block, the equation holds from the definition of algorithm . 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.
In this section, we will give the security proof of our proposed scheme.
Theorem 6.1 VIBKS 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. Let be 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 challenger with a non-negligible probability solving the hardness assumption of LWE problem.
Setup: requests from LWE oracle for m + 1 times to obtain fresh pair , where . Then sets two lists L1, L2, L3, and let qHi be the maximum number of ’s queries to Hi, where i = 1, 2, 3. Finally, prepares the system public parameters PP for as follows.
1. samples a random matrix by running .
2. constructs a random matrix from m of the given LWE samples, where the k-th column of F* be the vector for all .
3. sets A0 = F*R*, where A0 is uniform in since are invertible modulo q and F* is uniform in . also let , and finally sets and sends it to . Ahead of time, the target identity is submitted by .
Note that, regardless when performs the KeyDrive oracle query, it has made all relevant H1 queries before. Now, performs the following queries.
H1 query: For the l-th query, where , queries to H1 on any identity id adaptively. If , such that , sets and returns it to . Otherwise, runs to obtain a random matrix and a short random lattice basis for . Then adds () to list L1, and returns Rid to .
H2 query: For the l-th query, where , queries to H2 on any keyword w adaptively. If l = qH2, such that w = w*, sets and adds it to list L2, then returns it to . Otherwise, sets , where and adds it to list L2, then returns it to .
KeyDerive oracle: Upon receiving the KeyDerive query on id from , where the only restriction is , checks the list L1 to find (), if it is found, returns Tid to . Otherwise, performs the same operation as H1 query on id, obtains () and returns Tid to .
TokenGen oracle: Upon receiving the TokenGen query on w from , where the only restriction is , finds () in list L1 and in list L2, it they are found, computes and runs to obtain stw. Finally, returns stw to .
Challenge phase: sends to , where are two different keywords that have never been queried before, is the challenge identity. randomly chooses a bit , if b = 0, returns a random searchable ciphertext to . Otherwise, performs as follows:
For each , retrieve from LWE instance, set , and set . Finally, returns the searchable ciphertext to .
Guess: At last, outputs its guess .
The goal of is to decide which keyword is contained in the challenged ciphertext C*, since the challenger returns the searchable ciphertext which is associated with each keyword with probability 1/2. Now, we evaluate the probability of in breaking the ciphertext indistinguishability under the selective-ID attack in the random oracle model. With the system public parameters PP, we have , , and for some random values and vectors and with Gaussian distribution. Therefore, have the correct ciphertext form. We assume that can successfully guess the keyword is associated with the ciphertext C* with the probability , where the keyword is the qH2-th H2 query when with the probability 1/qH2. When is the -th H1 query, it occurs with the probability 1/qH1. Thus, if breaks the ciphertext indistinguishability under the selective-ID attack with a non-negligible probability in the random oracle model, can solve the hardness assumption of decisional-LWE problem with the non-negligible probability , which is contradictory. Consequently, 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 , SP denotes the . The performance comparison is listed in Tab. 1.
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 parameters . The security level of [13,16] is set to l = 10, as it utilized in their experiments. Under the above parameters, the time cost of , 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 of Encrypt in 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 the Encrypt process and keep it locally for the next Encrypt process. 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 of TokGen in our scheme is superior to that of [13,16]. Indeed, our scheme enjoys a greater advantage in TokGen because of the additional 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  spend less time to complete the test no matter what the number of keywords is. The scheme in  involves time-consuming operation (i.e., bilinear pairing) when matching the token and encrypted keywords. We can observe that Test in  consumes around 9 times more computation time than that in  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  and our scheme is almost the same, far less than that in . In order to further explore the relationship of time cost in  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  take about 0.126 ms and 0.333 ms, respectively. The results again confirm the superiority of our scheme.
With respect to Verify, we implement the experiments to compare the verification time of our scheme and the basic scheme in . As the basic scheme in  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  in Verify depends on the number of results. In Fig. 3, we set the number of results to 1, which is the optimal case for . Under the above setting, we notice that the performance of our scheme is significantly better than  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 . The reason is that the scheme in  adopts time-consuming operations such as bilinear pairing and modular exponentiation, while our proposed scheme only involves in efficient matrix multiplication and hash operations.
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.
|This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.|