Paper 2022/1083

EnigMap: Signal Should Use Oblivious Algorithms for Private Contact Discovery

Afonso Tinoco, Carnegie Mellon University, Instituto de Telecomunicações
Sixiang Gao, Carnegie Mellon University
Elaine Shi, Carnegie Mellon University
Abstract

Leveraging hardware enclaves technology, Signal was the first to offer a privacy-preserving contact discovery service, where users can discover whether their friends have signed up for the service, without divulging their entire address books. The crux of their design is an algorithm to search for the user's contacts such that the access patterns are independent of the queries. To achieve this, Signal implemented a naive batched linear scan algorithm that scans through the entire database for each batch of queries. Signal published a high-profile blog post arguing that for billion-sized databases, batched linear scan outperforms the asymptotically superior oblivious algorithms. While subsequent works revisited the same question, we still do not have conclusive evidence why Signal should use oblivious algorithms instead. 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 number of page swaps should be a primary performance metric. We therefore adopt techniques from the 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 5.5x speedup over Signal's linear scan implementation, and 21x speedup over the 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: Preprint

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
ORAM ODS Applied cryptography Cloud computing security Signal Private Contact Discovery
Contact author(s)
atinoco @ andrew cmu edu
sixiangg @ andrew cmu edu
runting @ gmail com
History
2022-08-21: approved
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: Signal Should Use Oblivious Algorithms for Private Contact Discovery},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1083},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1083}},
      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.