Waldo: A Private Time-Series Database from Function Secret Sharing
Waldo: A Private Time-Series Database from Function Secret Sharing
复制标题
DOI：
10.1109/sp46214.2022.9833611
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Emma Dauterman;Mayank Rathee;Raluca A. Popa;I. Stoica
中科院分区：
文献类型：
--
作者：
Emma Dauterman;Mayank Rathee;Raluca A. Popa;I. Stoica
如今的应用程序依赖云数据库来存储和查询时间序列数据。虽然外包存储很方便，但这些数据通常很敏感，导致数据泄露成为严重问题。我们推出了 Waldo，一个功能丰富、安全保障强大的时序数据库：Waldo 支持多谓词过滤，保护数据内容以及查询过滤值和搜索访问模式，并在 3 方诚实多数设置下提供恶意安全。相比之下，诸如Timecrypt和Zeph之类的现有系统的功能和安全性有限：（1）这些系统只能按时间进行过滤，（2）它们向服务器透露查询的时间间隔。 Oblivious RAM (ORAM) 和通用多方计算 (MPC) 是消除先前工作泄漏的自然选择，但由于往返次数和带宽开销，这两种方法在我们的设置中都非常昂贵。为了最大限度地减少这两者，Waldo 在函数秘密共享的基础上构建，使 Waldo 能够以非交互方式评估谓词。我们开发了新技术，将函数秘密共享应用于存在恶意服务器、秘密输入和链接谓词的加密数据库设置。在 32 核机器上，Waldo 在 3.03 秒内运行一个包含 8 个范围谓词、超过 218 条记录的查询，而 MPC 基线为 12.88 秒，ORAM 基线为 16.56 秒。与 Waldo 相比，MPC 基线在服务器之间使用了 9-82 倍的带宽（对于不同数量的记录），而 ORAM 基线在客户端和服务器之间使用了 20-152 倍的带宽（对于不同数量的谓词）。
Applications today rely on cloud databases for storing and querying time-series data. While outsourcing storage is convenient, this data is often sensitive, making data breaches a serious concern. We present Waldo, a time-series database with rich functionality and strong security guarantees: Waldo supports multi-predicate filtering, protects data contents as well as query filter values and search access patterns, and provides malicious security in the 3-party honest-majority setting. In contrast, prior systems such as Timecrypt and Zeph have limited functionality and security: (1) these systems can only filter on time, and (2) they reveal the queried time interval to the server. Oblivious RAM (ORAM) and generic multiparty computation (MPC) are natural choices for eliminating leakage from prior work, but both of these are prohibitively expensive in our setting due to the number of roundtrips and bandwidth overhead, respectively. To minimize both, Waldo builds on top of function secret sharing, enabling Waldo to evaluate predicates non-interactively. We develop new techniques for applying function secret sharing to the encrypted database setting where there are malicious servers, secret inputs, and chained predicates. With 32-core machines, Waldo runs a query with 8 range predicates over 218 records in 3.03s, compared to 12.88s or an MPC baseline and 16.56s for an ORAM baseline. Compared to Waldo, the MPC baseline uses $9-82 \times$ more bandwidth between servers (for different numbers of records), while the ORAM baseline uses $20-152 \times$ more bandwidth between the client and server(s) (for different numbers of predicates).