Towards efficient and accountable oblivious cloud storage

Thumbnail Image
Ma, Qiumao
Major Professor
Wensheng Zhang
Committee Member
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence

Related Units

Journal Issue
Is Version Of

Due to the convenience and unprecedented 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.

Though encryption helps to secure data, the server or the attacker who compromise the

server is still able to infer private information from the user's access pattern. It is possible

for an attacker to use the access pattern information to reconstruct the data query and infer

the plaintext of the data. Hence, a large variety of schemes based on the oblivious RAM

(ORAM) model have been proposed to allow a user to access the exported data while preserving

user's data access pattern. Most of these research has focused on the communication efficiency

improvement, but the storage efficiency has not received much attention. To host N data blocks,

in general, the state-of-the-art ORAM constructions need the storage server to also store cN

with c > 3 or O(N logN) dummy data blocks, which represents a huge storage overhead

when N is large. In addition to the inefficiency in server storage, most of existing ORAM

constructions incur O(logN) blocks or higher client-server communication cost. Though some

recent work has reduced the cost to O(1) blocks by employing multiple non-colluding servers,

the system could become vulnerable if some server does not follow the protocol completely.


To address the above limitations, we develop a series of new ORAM constructions, gradually

towards a more practical and secure solution that can obliviously protect the data access pattern

for users of cloud storage with more affordable storage, client-server communication, and server

communication overheads. Specifically, this dissertation presents:

SE-ORAM, which reduces server storage overhead to zero, but at the same time, incurs

a client server communication cost of O(log2 N) blocks;

Octopus ORAM, which incurs 0:34NB server storage overhead, and reduces client-server

communication cost to three blocks for query and about 1:5 logN blocks for eviction per


Three-server Octopus ORAM, an efficient and accountable multi-server ORAM, which

incurs 0:3N B server storage overhead and reduces client-server communication cost to

O(1) blocks, at the expense of server-server communication cost at O(logN) blocks per


We have rigorously quantified and proved the security strengths of these constructions and

demonstrated their performance efficiency through detailed analysis.

Subject Categories
Sat Dec 01 00:00:00 UTC 2018