Dynamic symmetric searchable encryption (SSE) enables clients to perform searches and updates on an encrypted database outsourced to an untrusted server while preserving the privacy of data and queries. For restricting information leakage, it is very important to limit what the server can learn about the deleted data during searches after the deletion, i.e., to satisfy backward privacy. However, previous backward privacy definitions only considered the logical deletion of keywords in documents while ignoring security risks caused by the actual deletion of documents. Moreover, existing SSE schemes often depend on heavy cryptographic primitives for achieving high-level backward privacy, which greatly degrades the end-to-end performance. To this end, we define a new backward privacy notion named BP-DEL, which restricts the information leakage of the actual deletion. Moreover, we design a hybrid index structure that provides BP-DEL for SSE schemes such that they support deletions securely. Based on the hybrid index, we propose a BP-DEL construction named LUNA and design its protocols with a trusted execution environment (TEE) to maintain the index efficiently. Finally, we implement LUNA in the MySQL database by encapsulating it in UDFs. The experimental results show that LUNA has a performance much better than previous works satisfying BP-DEL.

To achieve efficiently search and update on outsourced encrypted data, dynamic searchable symmetric encryption (DSSE) was proposed by just leaking some well-defined leakages. Though small, many recent works show that an attacker can exploit these leakages to undermine the security of existing DSSE schemes. In particular, an attacker can exploit even seemingly harmless size pattern to perform severe attacks. Many exiting schemes resort to oblivious RAM (ORAM) to hide search/access pattern; however, even such powerful cryptographic primitive cannot protect size pattern leakage. In this article, we first show that size pattern can lead to more information leakages, which is not well studied or protected by existing schemes. We then extend the existing privacy notion for DSSE to capture the size pattern leakage, achieving a strong forward and backward privacy definition. Following the definition, we propose a new DSSE scheme Eurus. Eurus can eliminate search/access pattern by relying on a multi-server ORAM scheme, meanwhile reducing size pattern with reasonable efficiency. We show that Eurus can reduce leakage significantly with better efficiency, compared with state-of-the-art leakage reduction schemes.

Order-preserving encryption (OPE) is a cryptographic primitive that preserves the order of plaintexts. In the past few years, many OPE schemes were proposed to solve the problem of executing range queries in encrypted databases. However, OPE leaks some certain information (for example, the order of ciphertext), so it is vulnerable to many attacks. Subsequently, order-revealing encryption (ORE) was proposed by Bonehet al.(Eurocrypt 2015) as a generalization of order-preserving encryption. It breaks through the limitation of the numeric order of OPE plaintext. It implements ciphertext comparison for any specific form of plaintext through a publicly computable comparison function. In this article, we aim to design a new ORE scheme which reduces the leakages and preserves the practicality in terms of ciphertext length and encryption time. We first propose the hybrid model namedHybridORE. Then, we propose an improved scheme namedEncodeOREwhich achieves acceptable security and appropriate ciphertext length. They both explore the encode strategy of encoding plaintext into different parts and apply suitable ORE algorithms to each part according to its security characteristics to reduce leakages. Compared with the typical CLWW scheme (FSE 2016) and Lewi-Wu (CCS 2016) in large domain, they have fewer leakages. The experiment shows that the proposedEncodeOREis very practical.

The range query on encrypted databases is usually implemented using the order-preserving encryption (OPE) technique which preserves the order of plaintexts. Since the frequency leakage of plaintexts makes OPE vulnerable to frequency-analyzing attacks, some frequency-hiding order-preserving encryption (FH-OPE) schemes are proposed. However, existing FH-OPE schemes require either the large client storage of size O ( n ) or O (log n ) rounds of interactions for each query, where n is the total number of plaintexts. To this end, we propose a FH-OPE scheme that achieves the small client storage without additional client-server interactions. In detail, our scheme achieves O ( N ) client storage and 1 interaction per query, where N is the number of distinct plaintexts and N ≤ n . Especially, our scheme has a remarkable performance when N ≪ n . Moreover, we design a new coding tree for producing the order-preserving encoding which indicates the order of each ciphertext in the database. The coding strategy of our coding tree ensures that encodings update in the low frequency when inserting new ciphertexts. Experimental results show that the single round interaction and low-frequency encoding updates make our scheme more efficient than previous FH-OPE schemes.

Searchable symmetric encryption (SSE) has been widely applied in the encrypted database for queries in practice. Although SSE is powerful and feature-rich, it is always plagued by information leaks. Some recent attacks point out that forward privacy which disallows leakage from update operations, now becomes a basic requirement for any newly designed SSE schemes. However, the subsequent search operations can still leak a significant amount of information. To further strengthen security, we extend the definition of forward privacy and propose the notion of “forward search privacy”. Intuitively, it requires search operations over newly added documents do not leak any information about past queries. The enhanced security notion poses new challenges to the design of SSE. We address the challenges by developing the hidden pointer technique (HPT) and propose a new SSE scheme called Khons, which satisfies our security notion (with the original forward privacy notion) and is also efficient. We implemented Khons and our experiment results on large dataset (wikipedia) show that it is more efficient than existing SSE schemes with forward privacy.

Encryption alone is not enough to protect data privacy, because access pattern leaks some sensitive information. Oblivious RAM (ORAM), the solution to this problem, is still far from practical deployment for heavy storage and communication/computation overhead. To reduce them, an insightful idea was proposed to utilize non-colluding clouds to shift client computation and client-cloud communication to the clouds. The proposed multi-cloud ORAM achieved O(1) client-cloud bandwidth cost and removed most of client computation. In this paper, we exploit “disconnected ORAMoperation” and design “two-layerencryption” to further reduce these overheads. Experiments show that our proposed scheme, NewMCOS, significantly reduces evict cache size from GB/MB to KB level with about 2-3 times lower response time and 20 percent savings in bandwidth for clouds, compared to other schemes. Theoretically speaking, we reduce evict cache size from O(√N) to O(ZK), where N is the number of real data blocks, K is the number of clouds (2 <; K <; <; √N ), and Z is the number of real blocks uploaded from the client for eviction. By employing “lazy eviction operation”, the write frequency is reduced by O(Z), the shuffling bandwidth cost is reduced by Ω(Z log Z). Meanwhile, NewMCOS is proved to be secure.

Oblivious RAM (ORAM) is important for applications that require hiding of access patterns. However, most of existing implementations of ORAM are very expensive, which are infeasible to be deployed in lightweight devices, like the terminal equipment for Internet of Things (IoT). In this article, we focus on how to apply the expensive ORAM to protect access pattern in IoT devices and propose an ORAM scheme supporting thin-client, called “ThinORAM”, under non-colluding clouds. Our proposed scheme removes complicated computations in the client side and requires only O(1) communication cost with a reasonable response time. We further show how to securely deploy ThinORAM in the fog computing environment to achieve oblivious data access with minimum client cost. Experiments show that our scheme can eliminate most of the client storage and reduce the cloud-cloud bandwidth by 2×, with 3× faster response time, when compared to the best scheme that aims at reducing client side overheads.