Paper 2022/1083

Enigmap : External-Memory Oblivious Map for Secure Enclaves

Afonso Tinoco, Carnegie Mellon University, Instituto de Telecomunicações
Sixiang Gao, Carnegie Mellon University
Elaine Shi, Carnegie Mellon University
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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Usenix Security 2023
Keywords
ORAMODSApplied cryptographyCloud computing securitySignalPrivate Contact Discovery
Contact author(s)
atinoco @ andrew cmu edu
sixiangg @ andrew cmu edu
runting @ gmail com
History
2023-06-09: revised
2022-08-20: received
See all versions
Short URL
https://ia.cr/2022/1083
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1083,
      author = {Afonso Tinoco and Sixiang Gao and Elaine Shi},
      title = {Enigmap : External-Memory Oblivious Map for Secure Enclaves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1083},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1083}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.