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.

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.