MACAO: A Maliciously-Secure and Client-Efficient Active ORAM Framework

Thang Hoang (University of South Florida), Jorge Guajardo (Robert Bosch Research and Technology Center), Attila Yavuz (University of South Florida)

Oblivious Random Access Machine (ORAM) allows
a client to hide the access pattern and thus, offers a strong level of
privacy for data outsourcing. An ideal ORAM scheme is expected
to offer desirable properties such as low client bandwidth, low
server computation overhead and the ability to compute over
encrypted data. S3ORAM (CCS’17), is a very efficient active
ORAM scheme, which takes advantage of secret sharing to
provide ideal properties for data outsourcing such as low client
bandwidth, low server computation and low delay. Despite its
merits, S3ORAM only offers security in the semi-honest setting.
In practice, it is likely that an ORAM protocol will have to operate
in the presence of malicious adversaries who might deviate from
the protocol to compromise the client privacy.

In this paper, we propose MACAO, a new multi-server ORAM
framework, which offers integrity, access pattern obliviousness
against active adversaries, and the ability to perform secure
computation over the accessed data. MACAO harnesses authenticated
secret sharing techniques and tree-ORAM paradigm to
achieve low client communication, efficient server computation,
and low storage overhead at the same time. We fully implemented
MACAO and conducted extensive experiments in real cloud
platforms (Amazon EC2) to validate the performance of MACAO
compared with the state-of-the-art. Our results indicate that
MACAO can achieve comparable performance to S3ORAM while
offering security against malicious adversaries. Our MACAO is
a suitable candidate for integration into distributed file systems
with encrypted computation capabilities towards enabling a full-fledged
oblivious data outsourcing infrastructure. We will open-source
MACAO for broad testing and adaptations.