Title: Storage Efficient Oblivious RAM for Protecting User’s Privacy in Cloud
Date/Time: April 6^th, 2017 @ 4:00 PM
Place: 223 Atanasoff  
Major Professor: Wensheng Zhang
Committee Members: Yong Guan, Simanta Mitra, Daji Qiao, Lu Ruan

Abstract:

Cloud-based storage service has been popular nowadays. Due to the convenience and unprecedent cost-effectiveness, more and more individuals and organizations have utilized cloud storage servers to host their data. However, because of security and privacy concerns, not all data can be outsourced without reservation. The concerns are rooted from the users' loss of data control from their hands to the cloud servers' premise and the infeasibility for them to fully trust the cloud servers. The cloud servers can be compromised by hackers, and they themselves may not be fully trustable.

As found by Islam et. al., data encryption alone is not sufficient. The server is still able to infer private information from the user's  access pattern. Furthermore, it is possible for an attacker to use the access pattern information to construct the data query and infer the plaintext of the data. Oblivious RAM (ORAM) has been a security-provable approach to protect clients' access patterns to remote cloud storage. Recently, numerous ORAM constructions have been proposed to improve the communication efficiency of the ORAM model.

However, little attention has been paid to the storage efficiency. In fact, most of the state-of-the-art ORAM constructions have the storage overhead of $O(N\cdot B)$ or $O(N\log N\cdot B)$ bits at the server, when $N$ real data blocks are hosted and each block size is $B$ bits. To fill the gap, we aim to design new ORAM constructions which focus on improving the server storage efficiency.

In this preliminary, we present two preliminary designs:

SE-ORAM: we first design a generic storage-efficient ORAM (SE-ORAM) construction with configurable security parameter and zero storage overhead at the server. Extensive analysis and  comparisons show that SE-ORAM can achieve $O(\log^2 N \cdot B)$ communication cost while introducing no storage overhead to the server and a storage overhead of $O(\log N\cdot B)$ to the client.

DF-ORAM: we also design a dummy-free ORAM (DF-ORAM), which further reduces the communication cost to $O(\log N\cdot B)$, removes dummy data blocks in server storage and at the same time introduces a server-side storage overhead of only $3N$ bits. Asymptotical and preliminary implementation-based evaluation demonstrate DF-ORAM to be the more communication-efficient and storage-efficient.

Based on these preliminary works, we will design, analyze and implement more practical storage-efficient and communication-efficient ORAM constructions, as well as build practical, secure cloud storage system atop the ORAM constructions.