Paper 2018/247

Hardware-Supported ORAM in Effect: Practical Oblivious Search and Update on Very Large Dataset

Thang Hoang and Muslum Ozgur Ozmen and Yeongjin Jang and Attila A. Yavuz

Abstract

Ability to query and update over encrypted data is an essential feature to enable breach-resilient cyber-infrastructures. Statistical attacks on searchable encryption (SE) have demonstrated the importance of sealing information leakages in access patterns. In response to such attacks, Oblivious Random Access Machine (ORAM) has been proposed. However, the composition of ORAM and SE is extremely costly in client-server model, and this poses a critical barrier towards its practical adaptations. In this paper, we create a new hardware-supported privacy-enhancing platform called as Practical Oblivious Search and Update Platform (POSUP), which enables oblivious keyword search/update operations on very large datasets with a high efficiency. We harness Intel SGX to realize highly optimized oblivious data structures for oblivious search/update purposes. We implemented POSUP and evaluated its performance with Wikipedia dataset containing $\ge 2^{29}$ keyword-file pairs. Our implementation is highly efficient, where it takes 1ms to access a 3 KB block with Circuit-ORAM. Our experiments have shown that POSUP offers up to $70\times$ less end-to-end delay and $100\times$ reduced bandwidth consumption, compared with the traditional ORAM-SE composition without secure hardware. POSUP is also at least $10\times$ faster for up to 99.5% fraction of keywords to be searched, compared with existing Intel SGX-assisted search platforms.