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
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
-
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} }