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.
Metadata
- Available format(s)
- 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
-
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} }