Paper 2022/1083

Enigmap : External-Memory Oblivious Map for Secure Enclaves

Abstract

Imagine that a privacy-conscious client would like to query a key-value store residing on an untrusted server equipped with a secure processor. To protect the privacy of the client's queries as well as the database, one approach is to implement an {\it oblivious map} inside a secure enclave. Indeed, earlier works demonstrated numerous applications of an enclaved-based oblivious map, including private contact discovery, key transparency, and secure outsourced databases. Our work is motivated by the observation that the previous enclave implementations of oblivious algorithms are sub-optimal both asymptotically and concretely. We make the key observation that for enclave applications, the {\it number of page swaps} should be a primary performance metric. We therefore adopt techniques from the {\it external-memory} algorithms literature, and we are the first to implement such algorithms inside hardware enclaves. We also devise asymptotically better algorithms for ensuring a strong notion of obliviousness that resists cache-timing attacks. We complement our algorithmic improvements with various concrete optimizations that save constant factors in practice. The resulting system, called Enigmap, achieves 15$\times$ speedup over Signal's linear scan implementation, and 53$\times$ speedup over the %state-of-the-art prior best oblivious algorithm implementation, at a realistic database size of 256 million and a batch size of 1000. The speedup is asymptotical in nature and will be even greater as Signal's user base grows.

Note: This is the full online version containing additional technical details that are not included in the conference version.