EnigMap: Signal Should Use Oblivious Algorithms for Private Contact Discovery
EnigMap: Signal Should Use Oblivious Algorithms for Private Contact Discovery
复制标题
EnigMap：信号应该使用不经意的算法来发现私人联系人
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
E. Shi
中科院分区：
文献类型：
--
作者：
Afonso Tinoco;Sixiang Gao;E. Shi
利用硬件飞地技术，Signal是第一个提供隐私保护联系人发现服务的公司，用户可以发现他们的朋友是否注册了该服务，而不会泄露他们的整个地址簿。他们设计的关键是搜索用户联系人的算法，这样访问模式与查询无关。为了实现这一点，Signal实现了一个简单的批量线性扫描算法，该算法针对每批查询扫描整个数据库。Signal发表了一篇高调的博客文章，认为对于数十亿大小的数据库，批量线性扫描优于渐进上级遗忘算法。虽然后续的工作重新审视了同一个问题，但我们仍然没有确凿的证据证明为什么Signal应该使用遗忘算法。我们的工作是出于观察，以前的飞地实现的不经意的算法是次优的渐近和具体的。我们的关键观察是，对于飞地应用程序，页面交换的数量应该是主要的性能指标。因此，我们采用了外部存储器算法文献中的技术，并且我们是第一个在硬件飞地内实现此类算法的人。我们还设计了渐近更好的算法，以确保一个强大的概念，抵抗缓存定时攻击的遗忘。我们用各种具体的优化来补充我们的算法改进，这些优化在实践中节省了常数因子。由此产生的系统，称为E NIG M AP，在实际数据库大小为2.56亿，批量大小为1000的情况下，实现了比Signal的线性扫描实现快5.5倍的加速，比先前的最佳遗忘算法实现快21倍。这种加速在本质上是渐进的，随着Signal用户群的增长，这种加速会更快。
—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 na ¨ ıve 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 E NIG M AP , achieves 5.5 × speedup over Signal’s linear scan implementation, and 21 × 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.
DOI：
10.1145/3409964.3461783
发表时间：
2021
期刊：
SPAA '21
影响因子：
--
作者：
Ramachandran, Vijaya;Shi, Elaine
通讯作者：
Shi, Elaine