Verifiable memory leakage-resilient dynamic searchable encryption

Abstract

Searchable symmetric encryption (SSE) allows a data owner to outsource his encrypted data to a cloud server while retaining the ability to perform keyword search over encrypted data. The security guarantees of existing SSE schemes require that the adversary has no access to the data owner’s secret keys. Unfortunately, adversaries may get some or all of the secret keys through memory attacks. Facing such memory attacks, most existing SSE schemes are no longer secure. Recently, a memory leakage-resilient dynamic SSE (MLR-DSSE) scheme has been proposed to resist memory attacks from physically unclonable functions (PUFs). However, this scheme does not consider the possibility of dishonest behaviors on the part of cloud servers. In this paper, we first propose a verifiable MLR-DSSE scheme based on PUFs and a verifiable hash table. The construction not only resists memory attacks but also supports verifiable search and dynamic updates. Besides, due to the combination of the secret sharing technique with PUFs, our proposed scheme can recover secret keys even if some PUFs are broken. Furthermore, the security analysis demonstrates that our proposed scheme is non-adaptively secure against memory attacks. The evaluation experiment results show that our scheme is efficient.

Keywords

Searchable symmetric encryption verifiability memory leakage-resilient physically unclonable functions cloud computing

1. Introduction

In the age of information, the amount of resources that have converged on the Internet is becoming increasingly enormous. To effectively manage and utilize Internet resources, cloud computing, which is a scalable and high-throughput computing paradigm, arose at a historic moment. Cloud computing has powerful data storage capabilities. Therefore, an increasing number of individuals and enterprises choose to outsource their data to cloud servers, which is helpful for reducing the enormous overhead of local data management. Although cloud computing brings users great benefits, it also inevitably leads to data security and privacy problems. An effective way to solve these problems is to encrypt data before outsourcing it to the cloud. However, how to carry out keyword search over encrypted data has become a new problem.

To address this issue, searchable symmetric encryption (SSE) was proposed by Song et al. [31]. In SSE schemes, a data owner can outsource his encrypted data to a cloud server while retaining the ability to perform keyword search over encrypted data. Most SSE schemes provide the cloud server with search capabilities through a so-called secure index [19]. An index is a data structure that maps the relationship between a keyword and corresponding encrypted data. To search for a keyword w, the data owner generates a trapdoor for w and sends it to the cloud server. Upon receiving the trapdoor, the cloud server searches the index and returns the corresponding search result. For a secure index, it is impossible to perform keyword search without the knowledge of a trapdoor. In addition, the trapdoor can only be generated using the secret key.

SSE has been well studied by plenty of researchers [8,24,25,32,34,37–39]. Most existing SSE schemes protect the data owner’s privacy through the use of secure indexes. That is, for an adversary who does not have the data owner’s secret key, the trapdoor does not reveal the search keyword, and the index does not reveal either the keywords contained in encrypted data or the relationships between keywords and encrypted data. Obviously, the security guarantees of these schemes rely on a simple assumption, that the adversary has no knowledge of or access to the secret key. However, long-term secret keys in these schemes are typically stored in non-volatile memory, such as ROM or flash. By using some fast and effective memory attacks [1,22], such as side-channel attacks, the adversary can easily obtain some or all of the content of non-volatile memory. Such memory attacks have made these schemes no longer secure. To the best of our knowledge, the only SSE construction that is secure against memory attacks is the memory leakage-resilient dynamic SSE (MLR-DSSE) scheme proposed by Dai et al. [17]. Their idea is to replace long-term secret keys stored in non-volatile memory with physically unclonable functions (PUFs) [28]. In this way, the adversary cannot obtain useful secret information through memory attacks.

However, the MLR-DSSE scheme by Dai et al. assumes that the cloud server is honest and does not support the verification of search results. In real life, a dishonest server may return incorrect search results due to financial incentives. Therefore, their scheme is not practical in real life. Some state-of-the-art searchable encryption schemes [23,29,36] can provide the verification of search results through the data authentication technology such as MAC [20] or Bloom filter [5]. Unfortunately, these schemes are not applicable in the scenario of memory leakage. In this paper, we observe that the primitive of verifiable hash table [7] is useful to achieve the verification when memory attacks occur. Therefore, we first propose a verifiable MLR-DSSE scheme based on PUFs and a verifiable hash table. Our proposed scheme not only is secure against memory attacks but also supports search results verification and dynamic updates.

Another shortcoming of the scheme by Dai et al. is that their key generation algorithm is not reliable enough. In their scheme, the outputs of PUFs are directly used as secret keys. However, a PUF is an unclonable function implemented by a physical system and can be broken due to collisions or other reasons. Because their scheme does not store secret keys in memory, the secret key is unrecoverable once the corresponding PUF is unusable. Motivated by this fact, in this paper, we apply the secret sharing technique [30] to our key generation algorithm. In our scheme, the output of each PUF is used to share a secret, and the data owner’s secret keys are generated from the shared secret. That is, as long as there remains a sufficient number of intact PUFs, the recovery of the secret keys is not affected by unusable PUFs. Therefore, our scheme is more applicable for real-world applications.

1.1. Our contribution

In this paper, we propose a verifiable MLR-DSSE scheme, which not only resists memory attacks but also supports dynamic updates and the verification of search results. Our contributions are summarized as follows:

Based on PUFs and a verifiable hash table, our proposed scheme is the first verifiable MLR-DSSE scheme. By using PUFs and fuzzy extractors as building blocks, our scheme can resist memory attacks. Besides, our scheme supports verifiable search and dynamic updates through the use of a verifiable hash table. Finally, we prove that our scheme can achieve the desired security requirements. The detailed evaluation experiment results show that our scheme is efficient.

We combine the secret sharing technique with PUFs to achieve a reliable key generation algorithm. In our proposed scheme, each PUF is used to build a share of a secret, and the data owner’s secret keys are generated from the shared secret. When some PUFs are broken, the data owner has the ability to recover the secret keys from the remaining intact PUFs.

1.2. Related work

Song et al. [31] were the first to consider the searchable encryption problem, and they proposed a scheme supporting dynamic updates. In their solution, a special two-layered encryption construction is applied to encrypt each word. Unfortunately, the search time is linear in the length of documents collection. Following the seminal work due to Song et al., many searchable encryption schemes have been proposed in the literature.

Static SSE schemes are only for fixed-size outsourced data. Curtmola et al. [16] firstly presented a static SSE scheme to achieve sublinear search time. Meanwhile, enhanced security definitions for searchable encryption schemes were put forward in [16]. Chase and Kamara [15] considered the problem of encrypting structured data and proposed an efficient SSE construction for labeled data. To achieve richer functionality, the first SSE solution that supports conjunctive keyword search was presented by Golle et al. [21]. Later, Cash et al. [9] constructed an SSE scheme implementing general Boolean queries on a large-scale database.

Dynamic SSE (DSSE) schemes allow to make dynamic updates to outsourced data or users. Goh [19] presented a DSSE scheme by using Bloom filter as a file index. However, his scheme requires linear search time and results in false positives. Chang and Mitzenmacher [14] put forward a dynamic solution without false positives, which is suitable for mobile users. In order to achieve a stronger privacy protection, Dai et al. [17] proposed a DSSE scheme that is secure against memory attacks. Their main idea is to utilize PUFs and fuzzy extractors [18] to achieve a real-time key generation. Furthermore, Alderman et al. [3] proposed a dynamic searchable encryption scheme that makes use of multi-level access control to protect hierarchical sensitive data. A hierarchical key assignment scheme is an effective solution to deal with privacy issues of searchable encryption. Castiglione et al. [10] investigated the relations between the security notions for hierarchical key assignment schemes supporting dynamic structures. Subsequently, on the basis of a symmetric encryption scheme, Castiglione et al. [11] proposed a concrete hierarchical key assignment scheme for dynamic updates. Castiglione et al. [12] also studied the Akl–Taylor scheme [2] in the dynamic setting and proposed a scheme supporting dynamic updates with the Akl–Taylor assignment.

As the cloud server may return incorrect or incomplete search results, it is essential to build an effective verification mechanism. Chai et al. [13] firstly presented a verifiable static SSE scheme based on the dictionary tree. In their scheme, the search path on the dictionary tree is used as evidence for the verification. Subsequently, Kurosawa et al. [26] utilized MAC to ensure the correctness and completeness of search results in their static scheme. In order to improve performance, Kurosawa et al. [27] later showed a verifiable DSSE construction via the use of a RSA accumulator. Their construction supports all updating operations for documents. To achieve a practical searchable encryption scheme, Jiang et al. [23] proposed a secure and efficient multi-keyword search scheme based on MAC and QSet, which supports not only verifiable search but also ranked search.

1.3. Organization

The rest of this paper is organized as follows. Some preliminaries applied in our scheme are presented in Section 2. The problem formulation is introduced in Section 3, including system model, formal definition, adversary model and security requirements. In Section 4, we describe the proposed verifiable MLR-DSSE scheme in detail. Security analysis and evaluation experiment are shown in Section 5. Finally, conclusion will be made in Section 6.

2. Preliminary

2.1. Physically unclonable functions and fuzzy extractors

Physically unclonable functions (PUFs), introduced by Pappu et al. [28], are one-way noise functions. A PUF can only be implemented on a physical system, and its randomness is extracted from its deep submicron physical characteristics [33]. The input/output of PUFs is called a challenge/response pair. Given an external challenge c, a PUF generates a response $r = PUF (c)$ that depends on both c and the unique randomness of the PUF. Generally, the main properties of PUFs are as follows:

Computable: Given a challenge c and a PUF, there is an efficient way to evaluate the response $r = PUF (c)$ .

Bounded noise: When accepting a legal challenge c, for the same PUF, responses $r_{1} = PUF (c)$ and $r_{2} = PUF (c)$ are different. However, the Hamming distance of $r_{1}$ , $r_{2}$ does not exceed a fixed bound $d_{1}$ .

Independence: There are no two distinct PUFs that show the same behavior.

One-wayness: Given a response r and a PUF, finding the challenge c that satisfies $r = PUF (c)$ is computationally infeasible.

Unclonability: There is no efficient known process that can physically clone a PUF.

Unpredictability: Even if a PUF has measured on a polynomial number of challenges, there is still a significant amount of entropy in the response that the PUF generates on a new challenge. Given a random variable Y, the average conditional min-entropy of X is defined as ${\tilde{H}}_{\infty} (X | Y) = - {log}_{2} (E_{y \leftarrow Y} [{max}_{x} Pr [X = x | Y = y]])$ . Let $CL = (c_{1}, \dots, c_{l})$ be a challenges list. Formally, a PUF is $m_{1}$ -unpredictable if the average min-entropy of a new challenge $c \notin CL$ satisfies ${\tilde{H}}_{\infty} (PUF (c) | PUF (CL)) ⩾ m_{1}$ , where $PUF (CL)$ represents a sequence of random variables $PUF (c_{1}), \dots, PUF (c_{l})$ .

For simplicity, we denote by $(n_{1}, d_{1}, m_{1})$ -PUF a probabilistic PUF, where $n_{1}$ is the number of output bits, $d_{1}$ is the noise bound and $m_{1}$ is the average conditional min-entropy of responses.

In our proposed scheme, we replace long-term secret keys stored in non-volatile memory with PUFs. However, the same challenge for a PUF may generate different responses. To solve this problem, we utilize the fuzzy extractor, which was proposed by Dodis et al. [18], to deal with the PUF’s responses. A fuzzy extractor can reliably extract a uniformly random string R from its input z and then recover R from the similar input $z^{'}$ and the helper data $h d$ .

Definition 1 (Fuzzy extractor).

Let $N$ be the collection of natural numbers. For positive integers $n_{1}$ , $d_{1}$ , $m_{1} \in N$ , a $(n_{1}, d_{1}, m_{1})$ fuzzy extractor consists of two efficient algorithms (Gen, Rep):

Gen: ${0, 1}^{n_{1}} \to {0, 1}^{l} \times {0, 1}^{*}$ . It is a probabilistic algorithm. On input a $n_{1}$ -bits string z, it outputs an “extracted” l-bits string R and the helper data $h d$ .

Rep: ${0, 1}^{n_{1}} \times {0, 1}^{*} \to {0, 1}^{l}$ . It is a deterministic algorithm. On input a $n_{1}$ -bits string $z^{'}$ and the helper data $h d$ , it outputs a l-bits string $R^{'}$ . As long as the Hamming distance between z and $z^{'}$ satisfies ${dis}_{ham} (z, z^{'}) < d_{1}$ , the correctness property of fuzzy extractors guarantees that $R^{'} = R$ .

The security of fuzzy extractors demands that R is computationally indistinguishable from the uniform distribution $U_{m}$ on condition that there are at least $m_{1}$ bits of min-entropy in z, even if given the helper data $h d$ .

2.2. Secret sharing scheme

The secret sharing scheme, which is also called the $(k, t)$ threshold scheme, was proposed by Shamir [30]. In a $(k, t)$ threshold scheme, a secret will be divided into t shares, and at least k shares together can recover the secret. To share a secret $a_{0}$ , the secret owner constructs a polynomial $f (x)$ of degree $k - 1$ $\begin{matrix} (1) & f (x) = a_{0} + a_{1} x + \dots + a_{k - 2} x^{k - 2} + a_{k - 1} x^{k - 1} mod p, \end{matrix}$ where $a_{1}, \dots, a_{k - 2}, a_{k - 1}$ are randomly selected in the finite domain on prime p. A share is a pair of $(x^{'}, f (x^{'}))$ , where $x^{'}$ is the input of $f (x^{'})$ . Given k shares, we can find the coefficients of $f (x)$ by interpolation and then evaluate $a_{0} = f (0)$ .

2.3. Verifiable hash table

Bost et al. [7] gave an efficient and concise instantiation of a verifiable hash table. It is a tree data structure that combines the characteristics of binary search trees and Merkle hash trees. Let $H : {0, 1}^{*} \to {0, 1}^{h_{1}}$ be a collision-resistant hash function and VHT be a verifiable hash table. Each node N of VHT is a tuple $(nkey, v, c_{l}, c_{r}, h_{N})$ , where $nkey$ is the key of the node, v is the value of the node, $c_{l}$ and $c_{r}$ respectively denote the left and right children of N, and $h_{N}$ is the hash value that is defined as $h_{N} = H (nkey ‖ v ‖ h_{c_{l}} ‖ h_{c_{r}})$ . If the node is ⊥, then we can define its hash value as $h_{⊥} = H (0)$ .

For each node $N \in VHT$ , the keys of the left subtree of N are smaller than $N . nkey$ , and the keys of the right subtree of N are larger than $N . nkey$ . Therefore, given a verifiable hash table VHT and an input key u, we can efficiently find a couple of nodes $(N_{big}, N_{small}) \in {(VHT \cup {⊥})}^{2}$ that satisfy the following conditions:

$(N_{big}, N_{small}) \neq (⊥, ⊥)$ .

If $N_{big} = N_{small}$ , then $u = N_{big} . nkey = N_{small} . nkey$ .

If $N_{big} \neq N_{small}$ and $N_{big} \neq ⊥$ , then $N_{big} . nkey > u$ .

If $N_{small} \neq N_{big}$ and $N_{small} \neq ⊥$ , then $N_{small} . nkey < u$ .

This pair of nodes is called enclosing nodes. Figure 1 gives an example of a verifiable hash table. For the sake of brevity, we only show the key of each node in Fig. 1. Given input keys

u_{1}

and

u_{2}

, it is easy to find that

(N_{20}, N_{17})

are a pair of enclosing nodes of

u_{1}

and

(N_{57}, N_{57})

are a pair of enclosing nodes of

u_{2}

Fig. 1.

Verifiable hash table.

3. Problem formulation

3.1. System model

As illustrated in Fig. 2, the system model involves two different entities: the cloud server and the data owner. The data owner has a set of documents $DB = {{DB}_{1}, \dots, {DB}_{n}}$ . He firstly extracts a set of keywords $W = {w_{1}, \dots, w_{m}}$ from $DB$ and builds a secure inverted index $I$ for the whole data set. Afterwards, he generates an encrypted documents collection $C$ using the secret key. Both $C$ and $I$ will be outsourced to the cloud server. To search the documents that contain the keyword w, the data owner generates a corresponding trapdoor $T K_{w}$ and submits it to the cloud server. Upon receiving the trapdoor $T K_{w}$ , the cloud server performs a data search on the index and returns a corresponding search result $R (w)$ and a proof τ. Besides, the data owner can update the outsourced data. Each update operation will result in an update of the search proof.

3.2. Formal definition

A verifiable DSSE scheme Π = (KeyGen, Enc, TrapGen, Search, Verify, Update) consists of following six algorithms:

$(K, PP) \leftarrow KeyGen (1^{λ})$ : On input a security parameter λ, it outputs a secret key K stored by the data owner and a public parameter PP.

$(C, I, σ) \leftarrow Enc (DB, W, K, PP)$ : On input a documents collection $DB$ , a keywords set $W$ , a secret key K and a public parameter PP, it outputs an inverted index $I$ , an encrypted documents collection $C$ and the data owner’s states collection σ. Afterwards, both $C$ and $I$ are outsourced to the cloud server.

${TK}_{w} \leftarrow TrapGen (w, K, PP)$ : On input a search keyword w, a secret key K and a public parameter PP, it generates a trapdoor ${TK}_{w}$ .

$(R (w), τ) \leftarrow Search (I, {TK}_{w})$ : Upon receiving ${TK}_{w}$ from the data owner, the cloud server runs this algorithm to return a corresponding search result $R (w)$ and a proof τ.

$C (w) / ⊥ \leftarrow Verify (R (w), τ, K, PP, σ)$ : If the search result $R (w)$ is correct with respect to the proof τ, then it accepts $R (w)$ and outputs a corresponding encrypted documents collection $C (w)$ . Otherwise, it outputs an error ⊥.

$(I^{'}, C^{'}, σ^{'}) \leftarrow Update (op, K, PP, σ)$ : On input an update operation op (modification, addition and deletion), it outputs an updated index $I^{'}$ , an updated encrypted documents collection $C^{'}$ and an updated states collection $σ^{'}$ .

Fig. 2.

System model of verifiable DSSE.

3.3. Adversary model

In this paper, we assume that the cloud server is “semi-honest-but-curious”. That is, the server may incorrectly execute the proposed protocol and return incorrect or incomplete search results. Additionally, because long-term secret keys in SSE schemes are stored in non-volatile memory, we consider the following memory attacks that are defined in [4]. The adversary $A$ in Definition 2 is called a μ-non-volatile memory adversary. If $μ = 1$ , then $A$ can perform full memory attacks and access the whole secret θ. Such an adversary is called a full non-volatile memory adversary.

Definition 2 (Memory attacks).

Let θ be the secret stored in non-volatile memory. The adversary $A$ can access an oracle $O$ that takes as input an adaptively chosen polynomial-size leakage function $L (\cdot)$ and outputs $L (θ)$ . For real number $0 ⩽ μ ⩽ 1$ , the total number of bits that $A$ obtains from the oracle is at most $μ | θ |$ .

3.4. Security requirements

On the basis of the above adversary model, we introduce some security requirements for our verifiable DSSE scheme in this section. The first requirement is the correctness. That is, the data owner can always successfully verify the search result returned by the honest server.

Definition 3 (Correctness).

Let λ be a security parameter and let Δ be a dictionary including all possible keywords. A verifiable DSSE scheme is correct if it satisfies the following requirements: $\forall (K, PP) \leftarrow KeyGen (1^{λ})$ , $\forall w \in Δ$ , the following logic statement is true: $\begin{matrix} Search (I, {TrapGen}_{K, PP} (w)) = (R (w), τ) \land {Verify}_{K, PP} (R (w), τ) = accept \land C (w) \end{matrix}$

The second requirement is the memory leakage-resilient (MLR) non-adaptive security. That is, our verifiable DSSE scheme is non-adaptively secure against memory attacks. Following the security definitions from [16], we formalize the definition of MLR non-adaptive security in terms of the real/ideal paradigm.

Definition 4 (MLR non-adaptive security).

Let Π be a verifiable DSSE scheme and λ be a security parameter. Let $A = (A_{0}, A_{1})$ be the non-volatile memory adversary and $S = (S_{0}, S_{1})$ be the simulator. In Table 1, we define two security experiments ${Real}_{A}^{Π} (1^{λ})$ and ${Ideal}_{A, S}^{Π} (1^{λ})$ , where ${Real}_{A}^{Π} (1^{λ})$ is run by the challenger and $A$ , and ${Ideal}_{A, S}^{Π} (1^{λ})$ is implemented by $S$ and $A$ .

Table 1
Real/ideal security experiments

${Real}_{A}^{Π} (1^{λ})$	${Ideal}_{A, S}^{Π} (1^{λ})$
$(K, PP) \leftarrow KeyGen (1^{λ})$	$(s t_{A}, DB, W) \leftarrow A_{0}^{L_{0} (θ)} (1^{λ})$
$(DB, W, s t_{A}) \leftarrow A_{0}^{L_{0} (θ)} (1^{λ})$	$V_{0} \leftarrow S_{0}^{L_{0}^{sm} (K)} (tr (DB, W))$
let $W = {w_{1}, \dots, w_{q_{1}}}$	$V_{0} = (\overline{C}, \overline{I}, \overline{TK})$
$(C, I) \leftarrow Enc (K, PP, DB, W)$	$(op, s t_{A}) \leftarrow A_{1}^{L_{1} (θ)} (\overline{C}, \overline{I}, s t_{A})$
for $1 ⩽ i ⩽ q_{1}$ ,	$(\overline{C^{'}}, \overline{I^{'}}) \leftarrow S_{1}^{L_{1}^{sm} (K)} (\overline{C}, \overline{I}, op)$
${TK}_{w_{i}} \leftarrow TrapGen (K, PP, w_{i})$	output: $V_{ideal} = (\overline{C}, \overline{I}, \overline{C^{'}}, \overline{I^{'}}, \overline{TK}, s t_{A})$
let $TK = {{TK}_{w_{1}}, \dots, {TK}_{w_{q_{1}}}}$
$(op, s t_{A}) \leftarrow A_{1}^{L_{1} (θ)} (C, I, s t_{A})$
$(C^{'}, I^{'}) \leftarrow Update (K, PP, op)$
output: $V_{real} = (C, I, C^{'}, I^{'}, TK, s t_{A})$

We say that a verifiable DSSE scheme Π is non-adaptively secure against μ-memory attacks if for each probabilistic polynomial time (PPT) μ-non-volatile memory adversary $A$ , there exists a PPT simulator $S$ such that $V_{real}$ and $V_{ideal}$ are computationally indistinguishable, that is, for each PPT distinguishers $D$ , $\begin{matrix} | Pr [D (V_{real}) = 1] - Pr [D (V_{ideal}) = 1] | ⩽ negl (λ), \end{matrix}$ where $negl (λ)$ denotes a negligible function of λ.

In above experiments, $s t_{A}$ denotes the string capturing $A$ ’s state. For $j \in {0, 1}$ , $L_{j} (\cdot)$ and $L_{j}^{sm} (\cdot)$ are the leakage functions submitted by $A$ and $S$ , respectively. We limit that $| L_{j}^{sm} (\cdot) | = | L_{j} (\cdot) |$ for all $j \in {0, 1}$ in order to ensure there is not too much information leaked to the simulator. θ is the secret information that the challenger stores in non-volatile memory. Let $L (θ) = L_{0} (θ) \cup L_{1} (θ)$ that satisfies $| L (θ) | ⩽ μ | θ |$ . In experiment ${Ideal}_{A, S}^{Π} (1^{λ})$ , $tr (DB, W)$ , which is defined in [16], denotes the trace of $DB$ and $W$ . The trace includes the search pattern, the access pattern, the length of the encrypted documents and the number of documents in $DB$ . Informally, the search pattern is the information that indicates whether the data owner has searched for the same keyword in the past. The access pattern is the set of encrypted documents that contain the keyword $w_{i}$ , for each $w_{i} \in W$ .

The third requirement is the soundness. That is, any tampering with the search result can be detected by the data owner. Definition 5 (Soundness).

Let Π be a verifiable DSSE scheme and $A$ be a PPT non-volatile memory adversary. Given a trapdoor ${TK}_{w}$ , the adversary $A$ forges an invalid result $R^{*} (w)$ and a corresponding proof $τ^{*}$ , where $R^{*} (w) \neq R (w)$ , $τ^{*} \neq τ$ and $(R (w), τ) \leftarrow Search (I, {TK}_{w})$ . We say that a verifiable DSSE scheme Π is sound if for each PPT μ-non-volatile memory adversary $A$ , the probability of successfully verifying $R^{*} (w)$ is negligible, i.e. $\begin{matrix} | Pr [Verify (R^{*} (w), τ^{*}) = accept] | ⩽ negl (λ), \end{matrix}$ where $negl (λ)$ denotes a negligible function.

4. Proposed verifiable memory leakage-resilient DSSE scheme

4.1. High description

In this paper, we construct a verifiable MLR-DSSE scheme from some cryptographic tools. The goal of our proposed scheme is to provide verifiable search and dynamic updates, while preserving the security against memory attacks. At the same time, we want to achieve a reliable key generation procedure.

To resist memory attacks, we use PUFs and fuzzy extractors as building blocks to generate secret keys in real-time, rather than storing long-term secret keys in non-volatile memory. Given a public parameter s as input, the building block outputs a random string $z_{i}$ that depends on the corresponding PUF. Due to the unclonability of PUFs, the non-volatile memory adversary has no access to PUFs and thus obtains nothing about $z_{i}$ . Therefore, $z_{i}$ can be used to generate secret keys. This idea has also been applied in the MLR-DSSE scheme by Dai et al. [17].

To achieve a reliable key generation procedure, we introduce a $(k, t)$ threshold scheme in our scheme. In Dai et al.’s scheme, each $z_{i}$ is directly used as a secret key. In this way, if a PUF’s physical system is broken because of collisions or other reasons, then the corresponding secret key is unrecoverable. Different from their scheme, we first choose t PUFs in the initialization phase, and then each $z_{i}$ is used to construct a share of a secret $a_{0}$ . Afterwards, the data owner’s secret keys are generated from collision-resistant hash functions and the shared secret $a_{0}$ . Therefore, as long as the number of unusable PUFs does not exceed $t - k$ , $a_{0}$ and the secret keys can be recovered from the remaining intact PUFs.

To support verifiable search and dynamic updates, a verifiable hash table VHT is used as a secure index in our scheme. For each node in VHT, the key is set as the permuted lexicographic order of the keyword, and the value is set as the corresponding encrypted set of identifiers. Firstly, VHT can be seen as a special binary search tree. Therefore, it supports efficient dynamic updates. Secondly, VHT also can be seen as a special Merkle hash tree. Therefore, the correctness and completeness of the search result can be verified through the computation of a new root node hash from the search path and a comparison of it to the root node hash returned from the cloud server. Besides, we bind the root node hash to a counter using a MAC function. This counter denotes the update times. There are two reasons for this binding operation. One is to prevent the cloud server from forging the root node hash. The other is to prevent the cloud server from returning previous search results after an update. The cloud server should compute a signature on the latest counter to ensure the counter is valid.

4.2. Notation definitions

To help understand our proposed scheme, we summarize the descriptions of symbols used throughout this paper in Table 2. For $n_{1} \in N$ , we use $[1, n_{1}]$ to denote ${1, \dots, n_{1}}$ . Without loss of generality, it is assumed that the length of each document in $DB$ is same, that is , ${DB}_{i} \in {0, 1}^{q}$ for all $i \in [1, n]$ .

Table 2
Notation definitions

Symbols Descriptions

$DB = {{DB}_{1}, \dots, {DB}_{n}}$ The set of documents

$W = {w_{1}, \dots, w_{m}}$ The set of keywords in $DB$

$C = {c_{1}, \dots, c_{n}}$ The set of encrypted documents

$Δ = {w_{1}, \dots, w_{d}}$ The dictionary that includes all possible keywords in lexicographic order

$i d ({DB}_{i}), 1 ⩽ i ⩽ n$ The identifier of the document ${DB}_{i}$

$DB (w_{j}), 1 ⩽ j ⩽ m$ The set of identifiers of documents that contain the keyword $w_{j}$ in $DB$

$C (w_{j}), 1 ⩽ j ⩽ m$ The set of encrypted documents that contain the keyword $w_{j}$ in $C$

$ID$ The identifier of the data owner

$I$ The index for $DB$

${TK}_{w}$ The trapdoor for a queried keyword w

$V_{w}, l > n$ The l-bit string for the keyword w

${ord}_{Δ}^{w}$ The lexicographic order of the keyword w

T The counter

Symbols	Descriptions
$DB = {{DB}_{1}, \dots, {DB}_{n}}$	The set of documents
$W = {w_{1}, \dots, w_{m}}$	The set of keywords in $DB$
$C = {c_{1}, \dots, c_{n}}$	The set of encrypted documents
$Δ = {w_{1}, \dots, w_{d}}$	The dictionary that includes all possible keywords in lexicographic order
$i d ({DB}_{i}), 1 ⩽ i ⩽ n$	The identifier of the document ${DB}_{i}$
$DB (w_{j}), 1 ⩽ j ⩽ m$	The set of identifiers of documents that contain the keyword $w_{j}$ in $DB$
$C (w_{j}), 1 ⩽ j ⩽ m$	The set of encrypted documents that contain the keyword $w_{j}$ in $C$
$ID$	The identifier of the data owner
$I$	The index for $DB$
${TK}_{w}$	The trapdoor for a queried keyword w
$V_{w}, l > n$	The l-bit string for the keyword w
${ord}_{Δ}^{w}$	The lexicographic order of the keyword w
T	The counter

4.3. The concrete construction

In this section, we proceed to the details of the construction of our verifiable MLR-DSSE scheme. Let $H_{1} : {0, 1}^{*} \to {0, 1}^{h_{1}}$ and $H_{2} : {0, 1}^{*} \to {0, 1}^{h_{2}}$ be collision-resistant hash functions. Let $ψ : {0, 1}^{h_{1}} \times {0, 1}^{{log}_{2} (d)} \to {0, 1}^{{log}_{2} (d)}$ be a pseudo-random permutation, where d denotes the number of keywords in the dictionary. Besides, $MAC : {0, 1}^{h_{1}} \times {0, 1}^{*} \to {0, 1}^{h_{3}}$ is a message authentication code function and SIGN is a secure signature scheme such as BLS short signature [6]. In addition, we make use of two PCPA-secure (pseudo-randomness against chosen-plaintext attacks) symmetric encryption schemes $E_{1} = (Enc 1, Dec 1)$ and $E_{2} = (Enc 2, Dec 2)$ , where $Enc 1 : {0, 1}^{h_{1}} \times {0, 1}^{l} \to {0, 1}^{l}$ and $Enc 2 : {0, 1}^{h_{1}} \times {0, 1}^{q} \to {0, 1}^{q}$ . PCPA-security, which is defined in [16] as a security notion for symmetric encryption schemes, guarantees that the ciphertexts are indistinguishable from random strings. Our proposed scheme is a collection of six polynomial-time algorithms (KeyGen, Enc, TrapGen, Search, Verify, Update) such that:

KeyGen $(1^{λ})$

Let ${PUF}_{i} : {0, 1}^{n_{1}} \to {0, 1}^{n_{1}}$ be a $(n_{1}, d_{1}, m_{1})$ -PUF. The data owner randomly chooses t $(n_{1}, d_{1}, m_{1})$ -PUFs and one secret $a_{0}$ . For each ${PUF}_{i}$ , he computes $\begin{matrix} (2) & r_{i} = {PUF}_{i} (s), (z_{i}, h d_{i}) \leftarrow FE . Gen (r_{i}), i \in [1, t], \end{matrix}$ where $FE = (FE . Gen, FE . Rep)$ is a $(n_{1}, d_{1}, m_{1})$ fuzzy extractor and s is a randomly selected $n_{1}$ -bit string. Secondly, he uses the secret sharing technique to construct a polynomial $f (x)$ that takes as input $z_{i}$ : $\begin{matrix} (3) & f (x) = a_{0} + a_{1} x + \dots + a_{k - 2} x^{k - 2} + a_{k - 1} x^{k - 1} mod p, \end{matrix}$ where $a_{1}, \dots, a_{k - 1}$ are randomly chosen from a uniform distribution over the integers in $[0, p)$ and $1 < k < t$ . A share is a pair of ( $z_{i}, f_{i}$ ), where $f_{i} = f (z_{i})$ . This algorithm outputs the public parameter $PP = {f_{1}, \dots, f_{t}, h d_{1}, \dots, h d_{t}, s, p}$ and the secret key $K = {{PUF}_{1}, \dots, {PUF}_{t}}$ .

Enc $(DB, W, K, PP)$

The data owner randomly selects k $PUFs$ from the K. Let ${PUF}_{t_{i}}$ denote the selected PUF, where $t_{i} \in [1, t]$ . For each $i \in [1, k]$ , he computes $\begin{matrix} (4) & r_{t_{i}}^{'} = {PUF}_{t_{i}} (s), z_{t_{i}} \leftarrow FE . Rep (r_{t_{i}}^{'}, h d_{t_{i}}) . \end{matrix}$ With k shares ${(z_{t_{1}}, f_{t_{1}}), \dots, (z_{t_{k}}, f_{t_{k}})}$ , he finds the coefficients of $f (x)$ by interpolation and computes $a_{0} = f (0)$ .

Construct an invert index $I$ . For each keyword $w_{j} \in W$ , $j \in [1, m]$ , the data owner firstly builds $DB (w_{j})$ and ${ord}_{Δ}^{w_{j}}$ , and then he translates $DB (w_{j})$ into a l-bit string $V_{w_{j}}$ , where $l > n$ . Let $V_{w_{j}}^{i}$ be the ith bit of $V_{w}$ . For $i \in [1, l]$ , we require that $V_{w_{j}}^{i} = 1$ if and only if $i d ({DB}_{i}) \in DB (w_{j})$ , otherwise $V_{w_{j}}^{i} = 0$ . Later, he constructs a look-up table VHT that is also a verifiable hash table. For each keyword $w_{j} \in W$ , $j \in [1, m]$ , he computes $\begin{matrix} (5) & \begin{matrix} K_{w_{j}} = H_{1} (a_{0} ∥ w_{j}), α_{w_{j}} = Enc 1_{K_{w_{j}}} (V_{w_{j}}), \\ K_{1} = H_{1} (a_{0} ∥ 1), {ord}_{PRP}^{w_{j}} = ψ_{K_{1}} ({ord}_{Δ}^{w_{j}}), \end{matrix} \end{matrix}$ and sets each node $N_{w_{j}}$ in VHT as a tuple $(nkey, v, c_{l}, c_{r}, h_{w_{j}})$ , where $nkey = {ord}_{PRP}^{w_{j}}$ , $v = α_{w_{j}}$ and $c_{l}$ and $c_{r}$ respectively denote left and right children of $N_{w_{j}}$ . The hash value of $N_{w_{j}}$ is defined as $\begin{matrix} (6) & h_{w_{j}} = H_{2} ({ord}_{PRP}^{w_{j}} ‖ α_{w_{j}} ‖ H_{2} (c_{l}) ‖ H_{2} (c_{r})) . \end{matrix}$ Figure 3 gives an example of the look-up table. Let $h_{root}$ denote the hash value of the root node of VHT. He sets counter $T = 1$ and computes $\begin{matrix} (7) & K_{2} = H_{1} (a_{0} ‖ 2), β = {MAC}_{K_{2}} (h_{root} ‖ T) . \end{matrix}$ Set the index $I = {VHT, h_{root}, β}$ .

Fig. 3.

Look-up table.

Build encrypted documents set $C$ . For each ${DB}_{i}$ , $i \in [1, n]$ , the data owner computes $\begin{matrix} (8) & \begin{matrix} K_{3} = H_{1} (a_{0} ‖ i d ({DB}_{i}) ‖ 1), c_{i}^{1} = Enc 2_{K_{3}} ({DB}_{i}), K_{4} = H_{1} (a_{0} ‖ i d ({DB}_{i}) ‖ 2), \\ c_{i}^{2} = {MAC}_{K_{4}} (c_{i}^{1}), c_{i} = (c_{i}^{1}, c_{i}^{2}) . \end{matrix} \end{matrix}$ Then he sets $c_{i}$ with the same identifier as ${DB}_{i}$ and $C = {c_{1}, \dots, c_{n}}$ .

The data owner sends T and ID to the cloud server. Afterwards, the cloud server computes a signature $δ = SIGN (T ‖ ID)$ and returns δ to the data owner. Finally, this algorithm outputs $C$ , $I$ and the data owner’s states collection $σ = {T, δ}$ . The data owner outsources $(C, I)$ to the cloud server and stores σ locally.

TrapGen $(w, K, PP)$

Given a keyword $w \in Δ$ , the data owner recovers $a_{0}$ from the secret key K and then computes the trapdoor $\begin{matrix} (9) & {TK}_{w} = {ord}_{PRP}^{w} = ψ_{K_{1}} ({ord}_{Δ}^{w}), K_{1} = H_{1} (a_{0} ‖ 1) . \end{matrix}$

Search $(I, {TK}_{w})$

Parse the index $I = {VHT, h_{root}, β}$ . Upon receiving a trapdoor ${TK}_{w}$ , the cloud server returns the enclosing nodes of ${TK}_{w}$ as the search result $R (w)$ along with the search proof τ to the data owner. The search process is summarized in Algorithm 1. For simplicity, we denote the root node of VHT by $r o o t (I . VHT)$ .

Note that the proof τ includes the search path from the root node to the enclosing nodes, the children nodes of the enclosing nodes and the siblings of each node on the search path.

Verify $(R (w), τ, K, PP, σ)$

When obtaining the search result $R (w)$ and the proof τ, the data owner recomputes the hash value of the root node, denoted by $h_{root}^{'}$ , from the search path. Besides, he recovers $a_{0}$ from K and checks $\begin{matrix} (10) & τ . h_{root} \overset{?}{=} h_{root}^{'}, τ . β \overset{?}{=} {MAC}_{K_{2}} (h_{root}^{'} ‖ T), \end{matrix}$ where $K_{2} = H_{1} (a_{0} ‖ 2)$ . If these two equations hold, then he accepts $R (w)$ and continues with subsequent validation. Otherwise, outputs ⊥.

If accepted $R (w)$ is composed of two identical nodes, then the data owner computes $\begin{matrix} (11) & K_{w} = H_{1} (a_{0} ∥ w), V_{w} = Dec 1_{K_{w}} (R (w) . N_{big} . α_{w}), \end{matrix}$ and sends $V_{w}$ to the server. Upon receiving it, the cloud server returns corresponding encrypted documents set $C (w)$ . Here, for $j \in [1, n]$ , $c_{j} \in C (w)$ if and only if $V_{w}^{j} = 1$ . For each $c_{j} \in C (w)$ , the data owner checks $c_{j}^{2} \overset{?}{=} {MAC}_{K_{4}} (c_{j}^{1})$ , where $K_{4} = H_{1} (a_{0} ‖ i d (c_{j}) ‖ 2)$ . If this equation holds, then the data owner outputs $C (w)$ . Otherwise, outputs ⊥.

If accepted $R (w)$ is composed of two different nodes, then set $C (w) = ⊥$ and output $C (w)$ .

Update $(op, K, PP)$

Let $op = {u p d, c, W^{'}}$ be an update operation, where $u p d$ denotes the update type, c denotes the document to be updated and $W^{'}$ denotes the set of keywords contained in c. According to the value of op, the data owner performs corresponding arithmetic operations:

Modification: $op = {modify, c_{i}, W^{'}}$ . Suppose that the data owner wants to modify $c_{i}$ to $c_{i}^{'}$ . For each keyword $w_{j} \in W^{'}$ , he firstly generates the trapdoor ${TK}_{w_{j}}$ and retrieves $R (w_{j})$ from the cloud server. That is, he obtains $(R (w_{j}), τ) \leftarrow Search (I, {TK}_{w_{j}})$ and checks $Verify (R (w_{j}), τ, K, PP, σ) = C (w_{j}) \neq ⊥$ . Secondly, he recovers $V_{w_{j}}$ from $R (w_{j})$ , sets $V_{w_{j}}^{i} = 1 / 0$ and then encrypts $V_{w_{j}}$ into $α_{w_{j}}^{'}$ to replace $R (w_{j}) . N_{big} . α_{w_{j}}$ . After each $w_{j}$ is updated, he computes a new root node hash $h_{root}^{'}$ , sets $T \leftarrow T + 1$ , $β^{'} = {MAC}_{K_{2}} (h_{root}^{'} ‖ T)$ and then sends $(c_{i}^{'}, h_{root}^{'}, β^{'}, T, ID)$ and ${({TK}_{w_{j}}, α_{w_{j}}^{'}) | w_{j} \in W^{'}}$ to the cloud server. Finally, the server sets $h_{root} \leftarrow h_{root}^{'}$ , $β \leftarrow β^{'}$ and $c_{i} \leftarrow c_{i}^{'}$ , updates VHT with $({TK}_{w_{j}}, α_{w_{j}}^{'})$ and computes $δ^{'} = SIGN (T ‖ ID)$ . The data owner is then given $δ^{'}$ and sets $δ \leftarrow δ^{'}$ if $δ^{'}$ is valid.

Deletion: $op = {delete, c_{i}, W^{'}}$ . When the data owner would like to delete $c_{i}$ , the operation of deletion can be viewed as a special case of the abovementioned modification. That is, the data owner modifies $c_{i}$ to $delete$ and sets $V_{w_{j}}^{i} = 0$ for each $w_{j} \in W^{'}$ .

Addition: $op = {add, c_{n + 1}, W^{'}}$ . Suppose that the data owner wants to add a new document $c_{n + 1}$ . For each keyword $w_{j} \in W^{'}$ , if $w_{j} \in W$ , then the operation of addition can be view as a special case of modification that set $V_{w_{j}}^{n + 1} = 1$ . Otherwise, the data owner firstly retrieves $(R (w_{j}), τ) \leftarrow Search (I, {TK}_{w_{j}})$ and checks $Verify (R (w_{j}), τ, K, PP, σ) = C (w_{j}) = ⊥$ . Secondly, he needs to create a children node $N_{w_{j}} = ({ord}_{PRP}^{w_{j}}, α_{w_{j}}, c_{l}, c_{r}, h_{w_{j}})$ for the last node on the search path (i.e., $R (w_{j}) . N_{big}$ or $R (w_{j_{}}) . N_{small}$ ). After each $w_{j}$ is updated, he computes a new root node hash $h_{root}^{'}$ , sets $T \leftarrow T + 1$ , $β^{'} = {MAC}_{K_{2}} (h_{root}^{'} ‖ T)$ and then sends $(c_{n + 1}, h_{root}^{'}, β^{'}, T, ID)$ and ${N_{w_{j}} | w_{j} \in W^{'}}$ to the cloud server. Finally, the server sets $h_{root} \leftarrow h_{root}^{'}$ and $β \leftarrow β^{'}$ , updates VHT with $N_{w_{j}}$ , inserts $c_{n + 1}$ into $C$ and computes $δ^{'} = SIGN (T ‖ ID)$ . The data owner is then given $δ^{'}$ and sets $δ \leftarrow δ^{'}$ if $δ^{'}$ is valid.

Algorithm 1

Search algorithm

5. Security and performance analysis

5.1. Security analysis

Firstly, we prove the correctness of our verifiable MLR-DSSE scheme through the correctness of the cryptographic tools used in our scheme.

Theorem 1.
The proposed verifiable MLR-DSSE scheme is correct.
Proof.
Given the trapdoor ${TK}_{w} = ψ_{K_{1}} ({ord}_{Δ}^{w})$ of a keyword w, the enclosing nodes of ${TK}_{w}$ in the look-up table VHT can be located by the cloud server and returned as the search result $R (w)$ . The proof τ consists of the search path L, the root node hash $h_{root}$ and the MAC value β. After getting the search result $R (w)$ and the proof τ from the cloud server, the data owner computes a new root node hash $h_{root}^{'}$ and checks whether $τ . h_{root} = h_{root}^{'}$ and $τ . β = {MAC}_{K_{2}} (h_{root}^{'} ‖ T)$ . If the cloud server has no dishonest behaviors, then the verification will pass and $R (w)$ will be accepted. After verification, if accepted $R (w)$ is composed of two identical nodes, then the data owner can obtain expected encrypted documents $C (w)$ by decrypting $V_{w} = Dec 1_{K_{w}} (R (w) . N_{big} . α_{w})$ . Otherwise, it means there are no matching documents. Finally, MAC functions can ensure the integrity of encrypted documents. Thus, the proposed verifiable MLR-DSSE scheme is correct. □

Secondly, we prove that our verifiable MLR-DSSE scheme is non-adaptively secure against full memory attacks by reduction. According to the simulation-based Definition 4, the proof of the following theorem is equivalent to constructing a PPT simulator $S$ such that $V_{real}$ and $V_{ideal}$ are computationally indistinguishable. Note that the simulator $S$ can also perform full memory attacks. In our proposed scheme, the data owner does not store any secret information in non-volatile memory. Therefore, the adversary $A$ and the simulator $S$ cannot obtain anything through full memory attacks. In the following theorem, we construct such a simulator $S$ by simulating each element in $V_{ideal}$ . The indistinguishability between $V_{real}$ and $V_{ideal}$ can be reduced to the security guarantees of the cryptographic tools we use.
Theorem 2.
If each ${PUF}_{i}$ ∈ ${{PUF}_{1}, \dots, {PUF}_{t}}$ is a $(n_{1}, d_{1}, m_{1})$ -PUF, $FE$ is a $(n_{1}, d_{1}, m_{1})$ fuzzy extractor, $H_{1}$ is a collision-resistant hash function, ψ is a pseudo-random permutation and $E_{1}$ and $E_{2}$ are PCPA-secure symmetric encryption schemes, then the proposed verifiable MLR-DSSE scheme is non-adaptively secure against full memory attacks.
Proof.
For each PPT full non-volatile memory adversary $A$ , we need to construct a PPT simulator $S$ such that $V_{real}$ is computationally indistinguishable from $V_{ideal}$ . In our proposed scheme, the data owner just stores his states collection $σ = {T, δ}$ in non-volatile memory, where T is a counter and δ is a signature. Without loss of generality, we assume that σ is given to both $A$ and $S$ . Next, we describe such a simulator $S$ that takes as input the trace $tr (DB, W)$ , the update operation op and the data owner’s states collection σ, and generates $(\overline{C}, \overline{I}, \overline{C^{'}}, \overline{I^{'}}, \overline{TK})$ as follows:
Simulating $\overline{C}$ . Let $\overline{C} = ({\overline{c}}_{1}, \dots, {\overline{c}}_{n})$ . Because the trace $tr (DB, W)$ includes the encrypted document length q, for $i \in [1, n]$ , $S$ sets each ${\overline{c}}_{i}$ to a uniformly selected q-bit string at random.

Simulating $\overline{I}$ . Let $\overline{VHT}$ be the look-up table in $\overline{I}$ . Obviously, the identifiers set $V_{w_{j}}$ of each keyword $w_{j}$ is included in $tr (DB, W)$ . Let $b \leftarrow_{R} B$ denote that b is picked uniformly at random from the set B. For each node $N_{w_{j}}$ in $\overline{VHT}$ , $S$ can set ${\overline{α}}_{w_{j}} = Enc 1_{K_{w_{j}}^{}} (V_{w_{j}})$ and ${\overline{ord}}_{PRP}^{w_{j}} = ψ_{K_{1}^{}} ({ord}_{Δ}^{w_{j}})$ , where $K_{w_{j}}^{}, K_{1}^{} \leftarrow_{R} {0, 1}^{h_{1}}$ .

Simulating $\overline{TK}$ . For a search keyword $w_{j}$ , $S$ simulates the trapdoor ${\overline{TK}}_{w_{j}} = ψ_{K_{1}^{}} ({ord}_{Δ}^{w_{j}})$ .

Simulating $(\overline{C^{'}}, \overline{I^{'}})$ . If $op = {modify, {\overline{c}}_{i}, W^{'}}$ , then $S$ modifies ${\overline{c}}_{i}$ to another randomly selected q-bit string ${\overline{c}}_{i}^{'}$ . For each $w_{j} \in W^{'}$ , $S$ sets $V_{w_{j}}^{i} = 1$ (or $V_{w_{j}}^{i} = 0$ ) and updates look-up table $\overline{VHT}$ with ${\overline{α}}_{w_{j}}^{'} = Enc 1_{K_{w_{j}}^{}} (V_{w_{j}})$ . Let $\overline{C^{'}} = ({\overline{c}}_{1}, \dots, {\overline{c}}_{i - 1}, {\overline{c}}_{i}^{'}, {\overline{c}}_{i + 1}, \dots, {\overline{c}}_{n})$ and $\overline{I^{'}}$ be the updated look-up table. Because the simulation for the deletion and addition operations is similar to the simulation for the modification operation, we omit this part for the sake of brevity.

We now prove that $V_{real} = (C, I, C^{'}, I^{'}, TK, s t_{A})$ is computationally indistinguishable from $V_{ideal} = (\overline{C}, \overline{I}, \overline{C^{'}}, \overline{I^{'}}, \overline{TK}, s t_{A})$ for any PPT distinguisher $D$ that is given $s t_{A}$ . Note that $s t_{A}$ denotes $A$ ’s state and contains σ. Firstly, we prove that $D$ has no access to the secret keys. A $(n_{1}, d_{1}, m_{1})$ -PUF is a unique function that is implemented by a physical system, and its output contains at least $m_{1}$ bits of min-entropy. When the output of a $(n_{1}, d_{1}, m_{1})$ -PUF is taken as the input for the $(n_{1}, d_{1}, m_{1})$ fuzzy extractor FE, the security of FE can ensure that the output of FE is computationally indistinguishable from the uniform distribution $U_{m}$ , even if given the helper data $h d$ . Let $z_{i}$ denote the output of FE. Due to the unclonability of PUFs, $D$ has no access to PUFs and thus cannot obtain $z_{i}$ . In addition, $s t_{A}$ does not contain any information about the secret keys. As a result, $D$ is unable to access the secret keys. We then prove that each element in $V_{real}$ is computationally indistinguishable from its counterpart in $V_{ideal}$ as follows:
$\overline{C}$ and $C$ . The PCPA-security of $E_{2}$ guarantees that $C$ is computationally indistinguishable from the uniform distribution $U_{m}$ . Therefore, $\overline{C}$ and $C$ are computationally indistinguishable for the distinguisher $D$ without the secret key of $E_{2}$ .

$\overline{TK}$ and $TK$ . The security of ψ guarantees that its outputs are computationally indistinguishable from random numbers. Therefore, $\overline{TK}$ and $TK$ are computationally indistinguishable.

$\overline{I}$ and $I$ . For each node in $\overline{VHT}$ , the PCPA-security of $E_{1}$ and the security of ψ guarantee that ${\overline{α}}_{w_{j}}$ and ${\overline{ord}}_{PRP}^{w_{j}}$ are computationally indistinguishable from corresponding $α_{w_{j}}$ and ${ord}_{PRP}^{w_{j}}$ in $VHT$ , which means $\overline{I}$ and $I$ are computationally indistinguishable.

$(\overline{C^{'}}, \overline{I^{'}})$ and $(C^{'}, I^{'})$ . Like in the above proof, the PCPA-security of $E_{1}$ and $E_{2}$ ensures that $(\overline{C^{'}}, \overline{I^{'}})$ are computationally indistinguishable from $(C^{'}, I^{'})$ .

Therefore, the proposed verifiable MLR-DSSE scheme is non-adaptively secure against full memory attacks. □

Finally, we prove the soundness of our verifiable MLR-DSSE scheme by contradiction. In the above proof, we have proved that a PPT full non-volatile memory adversary cannot obtain secret keys. Therefore, if there exists a PPT adversary $A$ that has a non-negligible advantage to trick the verification algorithm into accepting forged search results, then we can use $A$ to build an efficient algorithm to find collisions of the collision-resistant hash function. However, this contradicts the security of the collision-resistant hash function. Theorem 3.
If each ${PUF}_{i} \in {{PUF}_{1}, \dots, {PUF}_{t}}$ is a $(n_{1}, d_{1}, m_{1})$ -PUF, $FE$ is a $(n_{1}, d_{1}, m_{1})$ fuzzy extractor, $H_{2}$ is a collision-resistant hash function, MAC is a secure message authentication code and SIGN is a secure signature scheme, then the proposed verifiable MLR-DSSE scheme is sound.
Proof.
For each PPT full non-volatile memory adversary $A$ , we assume that the data owner’s states collection σ stored in non-volatile memory is given to $A$ . Similar to the proof in Theorem 2, without access to PUFs, $A$ cannot obtain the secret key of MAC. Let $R^{} (w)$ be an invalid search result forged by $A$ and $τ^{}$ be a corresponding forged proof. In the verification phase, the data owner first recomputes the root node hash $h_{root}^{'}$ from $R^{} (w)$ and $τ^{}$ , and then checks whether $τ^{} . h_{root} = h_{root}^{'}$ and $τ^{} . β = {MAC}_{k} (h_{root}^{'} ‖ T)$ . If these equations hold, then $A$ has found collisions of $H_{2}$ or got the secret key of MAC. However, this contradicts the security of $H_{2}$ and the previous proof. Therefore, this verification will fail. Furthermore, the local counter T can prevent replay attacks. After an update, T is increased by one and is denoted by $T^{new}$ . If $A$ returns the previous search result $(R^{'} (w), τ^{'})$ , then the equation $τ^{'} . β = {MAC}_{k} (h_{root}^{old} ‖ T^{new})$ does not hold, where $h_{root}^{old}$ is the root node hash that is computed from the previous search result and $τ^{'} . β$ is a previous MAC value. The signature δ that the cloud server computes for the latest counter can ensure the validity of $T^{new}$ . Therefore, the proposed verifiable MLR-DSSE scheme is sound. □

5.2. Comparison

In this section, we compare the proposed scheme with the schemes by Kurosawa et al. [27] and Dai et al. [17], respectively. Firstly, our scheme achieves memory leakage-resilience and verifiability simultaneously. Secondly, our scheme is efficient since the computational resources invested by the client is independent on the number of documents. Furthermore, there is no modular exponentiation or symmetric homomorphic encryption [35] in our scheme. Additionally, because our scheme just needs to store a signature and a counter locally, the space complexity is small. However, the client in scheme [17] is required to store a table of size $O (d)$ to finish searching, where d is the number of all possible keywords in the dictionary. Finally, even if some PUFs are broken, our scheme still can recover secret keys through the secret sharing technique, while the scheme [17] cannot do it.

Table 3
Comparison among three schemes

Schemes Kurosawa et al. [27] Dai et al. [17] Our proposed scheme

Memory leakage-resilience No Yes Yes

Verifiability Yes No Yes

Search computation (Server) $(m n - u) (Z + A)$ $1 P$ $log m I$

Verification computation (Client) $(u + n) (Z + A)$ – $log m A + (u + 1) M + 1 D + k U$

Addition computation (Client) $(m + 1) (Z + A)$ $| W | (2 U + P)$ $(| W | + 1) (log m A + M) + | W | D + k U$

Schemes	Kurosawa et al. [27]	Dai et al. [17]	Our proposed scheme
Memory leakage-resilience	No	Yes	Yes
Verifiability	Yes	No	Yes
Search computation (Server)	$(m n - u) (Z + A)$	$1 P$	$log m I$
Verification computation (Client)	$(u + n) (Z + A)$	–	$log m A + (u + 1) M + 1 D + k U$
Addition computation (Client)	$(m + 1) (Z + A)$	$\| W \| (2 U + P)$	$(\| W \| + 1) (log m A + M) + \| W \| D + k U$

Table 3 presents the comparison among the three schemes. In this table, n is the number of documents in $DB$ , m is the number of keywords in $W$ , u is the number of returned search documents, $| W |$ is the number of updated keywords, k is the number of PUFs that we choose to recover the shard secret, U is one operation on a PUF and a fuzzy extractor, I is one integer comparison operation, P is one operation on a symmetric homomorphic encryption scheme, D is one operation on a symmetric encryption scheme, Z is one exponent calculation, A is one operation on a hash function and M is one operation on a MAC function.

Fig. 4.

Efficiency comparison.

5.3. Performance evaluation

In this section, we provide a thorough experimental evaluation of the proposed scheme. We implement the experiments using Java language on a Windows laptop equipped with a 2.60 GHz Intel(R) Core(R) CPU and 8G RAM. We simulate both the client and the server on this Windows machine.

The time cost of building the index, search, verification and addition for scheme [17] and our scheme are shown in Fig. 4. In this simulation experiment, we set the number of keywords in the dictionary to 40000 for both schemes, and set $k = 4$ and $t = 5$ in our proposed scheme. The simulation results shown in Fig. 4(a) and (b) reveal that the time of building the index in our scheme is linear in keywords number m and is independent of documents number n. Although it takes a long time to build the index, it is a one-time overhead cost. In the search phase, the simulation results shown in Fig. 4(c) and (d) demonstrate that our scheme is more efficient than scheme [17] when m is not very large. In fact, our search time is linear in $log m$ . Even when $m = 8000$ , our search time is only 11 ms, which is suitable for real-world applications. Figure 4(e) indicates that our verification time is very short and increases slowly as m increases. That is, the time overhead of the client only increases a little bit when we improve security. Because deletion and modification operations are similar to the addition operation in our scheme and scheme [17], we just provide the time cost for addition in Fig. 4(f). It is obvious that the addition operation of scheme [17] is more efficient than that of our scheme, as shown in Fig. 4(f). However, the scheme [17] is not secure against the semi-honest server. Besides, the time cost of our update operation is still just milliseconds when $m = 8000$ , so it is suitable for large outsourced document sets. In general, our scheme is secure and efficient enough for real-world applications.

6. Conclusion

The primitive of searchable symmetric encryption is useful for solving the problem of how to implement keyword queries of encrypted data. However, the existing schemes either suffer from memory attacks or do not support the verification of search results. In this paper, we first propose a dynamic searchable symmetric encryption scheme from PUFs and a verifiable hash table, which is not only verifiable but also secure against memory attacks. Besides, while accounting for the physical properties of PUFs, we introduce a secret sharing technique in our scheme to make key generation highly reliable. Finally, we demonstrate that our scheme can achieve the desired security requirements and is sufficiently efficient.

Footnotes

Acknowledgements

This work is supported by National Natural Science Foundation of China (Nos. 61572382 and 61702401), Key Project of Natural Science Basic Research Plan in Shaanxi Province of China (No. 2016JZ021), China 111 Project (No. B16037), China Postdoctoral Science Foundation (No. 2017M613083), Guangxi Colleges and Universities Key Laboratory of Cloud Computing and Complex Systems (No. YF17103), Guangxi Cooperative Innovation Center of Cloud Computing and Big Data (No. YD17X07) and Guangxi Key Laboratory of Cryptography and Information Security (No. GCIS201606).

References

Akavia,

Goldwasser and

Vaikuntanathan, Simultaneous hardcore bits and cryptography against memory attacks, in: Proceedings of the Theory of Cryptography Conference (TCC’09), Vol. 5444, 2009, pp. 474–495. doi:10.1007/978-3-642-00457-5_28.

S.G.

Akl and

P.D.

Taylor, Cryptographic solution to a problem of access control in a hierarchy, ACM Transactions on Computer Systems (TOCS) 1(3) (1983), 239–248. doi:10.1145/357369.357372.

Alderman,

K.M.

Martin and

S.L.

Renwick, Multi-level access in searchable symmetric encryption, in: Proceedings of the International Workshops on Financial Cryptography and Data Security, 2017, pp. 35–52. doi:10.1007/978-3-319-70278-0_3.

Armknecht,

Maes,

A.R.

Sadeghi,

Sunar and

Tuyls, Memory leakage-resilient encryption based on physically unclonable functions, in: Towards Hardware-Intrinsic Security, Springer, Berlin Heidelberg, 2010, pp. 135–164. doi:10.1007/978-3-642-14452-3_6.

B.H.

Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM 13(7) (1970), 422–426. doi:10.1145/362686.362692.

Boneh,

Lynn and

Shacham, Short signatures from the Weil pairing, in: Proceedings of the Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT’01), 2001, pp. 514–532. doi:10.1007/3-540-45682-1_30.

Bost,

P.A.

Fouque and

Pointcheval, Verifiable dynamic symmetric searchable encryption: Optimality and forward security, IACR Cryptology ePrint Archive 2016 (2016), 62.

Bost,

Minaud and

Ohrimenko, Forward and backward private searchable encryption from constrained cryptographic primitives, in: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1465–1482. doi:10.1145/3133956.3133980.

Cash,

Jarecki,

Jutla,

Krawczyk,

M.C.

Rosu and

Steiner, Highly-scalable searchable symmetric encryption with support for Boolean queries, in: Proceedings of the International Conference on Cryptology (CRYPTO’13), 2013, pp. 353–373. doi:10.1007/978-3-642-40041-4_20.

10.

Castiglione,

De Santis,

Masucci,

Palmieri and

Castiglione, On the relations between security notions in hierarchical key assignment schemes for dynamic structures, in: Proceedings of the Australasian Conference on Information Security and Privacy, Springer International Publishing, 2016, pp. 37–54. doi:10.1007/978-3-319-40367-0_3.

11.

Castiglione,

De Santis,

Masucci,

Palmieri,

Castiglione and

Huang, Cryptographic hierarchical access control for dynamic structures, IEEE Transactions on Information Forensics and Security 11(10) (2016), 2349–2364. doi:10.1109/TIFS.2016.2581147.

12.

Castiglione,

De Santis,

Masucci,

Palmieri,

Huang and

Castiglione, Supporting dynamic updates in storage clouds with the Akl–Taylor scheme, Information Sciences 387 (2017), 56–74. doi:10.1016/j.ins.2016.08.093.

13.

Chai and

Gong, Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers, in: Proceedings of the IEEE International Conference on Communications (ICC’12), 2012, pp. 917–922. doi:10.1109/ICC.2012.6364125.

14.

Chang and

Mitzenmacher, Privacy preserving keyword searches on remote encrypted data, in: Proceedings of the International Conference on Applied Cryptography and Network Security (ACNS’05), Vol. 5, 2005, pp. 442–455. doi:10.1007/11496137_30.

15.

Chase and

Kamara, Structured encryption and controlled disclosure, in: Proceedings of the International Conference on Theory and Application of Cryptology and Information Security, 2010, pp. 577–594. doi:10.1007/978-3-642-17373-8_33.

16.

Curtmola,

Garay,

Kamara and

Ostrovsky, Searchable symmetric encryption: Improved definitions and efficient constructions, Journal of Computer Security 19(5) (2011), 895–934. doi:10.3233/jcs-2011-0426.

17.

Dai,

Li and

Zhang, Memory leakage-resilient searchable symmetric encryption, Future Generation Computer Systems 62 (2016), 76–84. doi:10.1016/j.future.2015.11.003.

18.

Dodis,

Ostrovsky,

Reyzin and

Smith, Fuzzy extractors: How to generate strong keys from biometrics and other noisy data, SIAM Journal on Computing 38(1) (2008), 97–139. doi:10.1137/060651380.

19.

E.J.

Goh, Secure indexes, IACR Cryptology ePrint Archive 2003 (2003), 216.

20.

Goldreich, Foundations of Cryptography – Volume 2, Basic Applications, Cambridge University Press, 2004. ISBN 0521830842.

21.

Golle,

Staddon and

Waters, Secure conjunctive keyword search over encrypted data, in: Proceedings of the International Conference on Applied Cryptography and Network Security (ACNS’04), Vol. 4, 2004, pp. 31–45. doi:10.1007/978-3-540-24852-1_3.

22.

J.A.

Halderman,

S.D.

Schoen,

Heninger,

Clarkson,

Paul,

J.A.

Calandrino,

A.J.

Feldman,

Appelbaum and

E.W.

Felten, Lest we remember: Cold boot attacks on encryption keys, Communications of the ACM 52(5) (2009), 91–98. doi:10.1145/1506409.1506429.

23.

Jiang,

Yu,

Yan and

Hao, Enabling efficient and verifiable multi-keyword ranked search over encrypted cloud data, Information Sciences 403 (2017), 22–41. doi:10.1016/j.ins.2017.03.037.

24.

Kamara and

Moataz, Boolean searchable symmetric encryption with worst-case sub-linear complexity, in: Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Cham, 2017, pp. 94–124. doi:10.1007/978-3-319-56617-7_4.

25.

K.S.

Kim,

Lee,

J.H.

Park and

W.-H.

Kim, Forward secure dynamic searchable symmetric encryption with efficient updates, in: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1449–1463. doi:10.1145/3133956.3133970.

26.

Kurosawa and

Ohtaki, UC-secure searchable symmetric encryption, in: Proceedings of the International Conference on Financial Cryptography and Data Security, Vol. 7397, 2012, pp. 285–298. doi:10.1007/978-3-642-32946-3_21.

27.

Kurosawa and

Ohtaki, How to update documents verifiably in searchable symmetric encryption, in: Proceedings of the International Conference on Cryptology and Network Security, 2013, pp. 309–328. doi:10.1007/978-3-319-02937-5_17.

28.

Pappu,

Recht,

Taylor and

Gershenfeld, Physical one-way functions, Science 297(5589) (2002), 2026–2030. doi:10.1126/science.1074376.

29.

Ramasamy,

S.S.

Vivek,

George and

B.S.R.

Kshatriya, Dynamic verifiable encrypted keyword search using bitmap index and homomorphic MAC, in: Proceedings of the 4th IEEE International Conference on Cyber Security and Cloud Computing (CSCloud 2017), 2017, pp. 357–362. doi:10.1109/CSCloud.2017.47.

30.

Shamir, How to share a secret, Communications of the ACM 22(11) (1979), 612–613. doi:10.1145/359168.359176.

31.

D.X.

Song,

Wagner and

Perrig, Practical techniques for searches on encrypted data, in: Proceedings of the IEEE Symposium on Security and Privacy, 2000, pp. 44–55. doi:10.1109/SECPRI.2000.848445.

32.

Stefanov,

Papamanthou and

Shi, Practical dynamic searchable encryption with small leakage, in: Proceedings of the International Symposium on Network and Distributed System Security (NDSS’14), Vol. 14, 2014, pp. 23–26. doi:10.14722/ndss.2014.23298.

33.

G.E.

Suh and

Devadas, Physical unclonable functions for device authentication and secret key generation, in: Proceedings of the 44th Annual ACM Design Automation Conference, 2007, pp. 9–14. doi:10.1109/dac.2007.375043.

34.

Sun,

Liu,

Lou,

Thomas and

Li, Catch you if you lie to me: Efficient verifiable conjunctive keyword search over large dynamic encrypted cloud data, in: Proceedings of the IEEE Conference on Computer Communications (INFOCOM’15), 2015, pp. 2110–2118. doi:10.1109/INFOCOM.2015.7218596.

35.

Van Dijk,

Gentry,

Halevi and

Vaikuntanathan, Fully homomorphic encryption over the integers, in: Proceedings of the Annual International Conference on Theory and Applications of Cryptographic Techniques, 2010, pp. 24–43. doi:10.1007/978-3-642-13190-5_2.

36.

Wang,

Chen,

Li,

Zhao and

Shen, Towards achieving flexible and verifiable search for outsourced database in cloud computing, Future Generation Computer Systems 67 (2017), 266–275. doi:10.1016/j.future.2016.05.002.

37.

Wang,

Yu and

Zhao, Fault-tolerant verifiable keyword symmetric searchable encryption in hybrid cloud, International Journal of Network Security 17(4) (2015), 471–483. doi:10.6633/IJNS.201507.17(4).12.

38.

Wang,

Wang and

Chen, Secure searchable encryption: A survey, Journal of Communications and Information Networks 1(4) (2016), 52–65. doi:10.1007/BF03391580.

39.

Wang,

S.F.

Sun,

J.K.

Liu,

Susilo and

Chen, Towards multi-user searchable encryption supporting Boolean query and fast decryption, in: Proceedings of the International Conference on Provable Security, Springer, Cham, 2017, pp. 24–38. doi:10.1007/978-3-319-68637-0_2.

Verifiable memory leakage-resilient dynamic searchable encryption

Abstract

Keywords

1. Introduction

1.1. Our contribution

1.2. Related work

1.3. Organization

2. Preliminary

2.1. Physically unclonable functions and fuzzy extractors

Definition 1 (Fuzzy extractor).

2.2. Secret sharing scheme

2.3. Verifiable hash table

3.1. System model

3.2. Formal definition

Definition 2 (Memory attacks).

3.4. Security requirements

Definition 3 (Correctness).

Definition 4 (MLR non-adaptive security).

Table 1 Real/ideal security experiments

4. Proposed verifiable memory leakage-resilient DSSE scheme

4.1. High description

4.2. Notation definitions

5.1. Security analysis

6. Conclusion

Footnotes

Acknowledgements

References

Table 1
Real/ideal security experiments