Degree Type


Date of Award


Degree Name

Doctor of Philosophy


Computer Science


Computer Science

First Advisor

Wensheng Zhang


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.~\cite{Islam12}, data encryption alone is not sufficient. The server is still able to infer private information from the user's {\em 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.

Therefore, Oblivious RAMs (ORAM) have been proposed to allow a user to access the exported data while preserving user's data access pattern. In recent years, interests in ORAM research have increased, and many ORAM constructions have been proposed to improve the performance in terms of the communication cost between the user and the server, the storage costs at the server and the user, and the computational costs at the server and the user.

However, the practicality of the existing ORAM constructions is still questionable:

Firstly, in spite of the improvement in performance, the existing ORAM constructions still require either large bandwidth consumption or storage capacity. %in practice.

Secondly, these ORAM constructions all assume a single user mode, which has limited the application to more general, multiple user scenarios.

In this dissertation, we aim to address the above limitations by proposing four new ORAM constructions:

S-ORAM, which adopts piece-wise shuffling and segment-based query techniques to improve the performance of data shuffling and query through factoring block size into design;

KT-ORAM, which organizes the server storage as a $k$-ary tree with each node acting as a fully-functional PIR storage, and adopts a novel delayed eviction technique to optimize the eviction process;

GP-ORAM, a general partition-based ORAM that can adapt the number of partitions to the available user-side storage and can outsource the index table to the server to reduce local storage consumption; and

MU-ORAM, which can deal with stealthy privacy attack in the application scenarios where multiple users share a data set outsourced to a remote storage server and meanwhile want to protect each individual's data access pattern from being revealed to one another.

We have rigorously quantified and proved the security strengths of these constructions and demonstrated their performance efficiency through detailed analysis.


Copyright Owner

Jinsheng Zhang



File Format


File Size

146 pages