Longshot: Indexing Growing Databases using MPC and Differential Privacy
Longshot: Indexing Growing Databases using MPC and Differential Privacy
复制标题
DOI：
10.14778/3594512.3594529
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Yanping Zhang;Johes Bater;Kartik Nayak;Ashwin Machanavajjhala
中科院分区：
文献类型：
--
作者：
Yanping Zhang;Johes Bater;Kartik Nayak;Ashwin Machanavajjhala
在这项工作中，我们提出了一种新的安全外包数据库系统的设计，它通过使用安全多方计算和差异隐私来支持即席查询。通过结合这两种技术，我们构建和维护数据结构(即概要、索引和存储)，以提高查询执行效率，同时保持强大的隐私和安全保证。随着数据所有者上传新的数据记录，这些数据结构通过使用新颖的算法不断更新，这些算法利用有限的信息泄漏将昂贵的加密协议的使用降至最低。此外，Long-Scan根据更新发生的时间将数据结构组织为分层树，从而允许随时间提供对数误差的更新策略。通过这种方法，LongSshot在隐私、准确性和效率之间引入了可调的三向权衡。我们的实验结果证实，我们的优化不仅是渐近的改进，而且在实践中也是可以观察到的。特别是，在更新次数少于200次的情况下，我们发现更新数据结构的效率提高了5倍。此外，随着时间的推移，数据结构显著改善了查询运行时间，与20次更新后的基线相比，速度提高了约103倍。
In this work, we propose Longshot, a novel design for secure outsourced database systems that supports ad-hoc queries through the use of secure multi-party computation and differential privacy. By combining these two techniques, we build and maintain data structures (i.e., synopses, indexes, and stores) that improve query execution efficiency while maintaining strong privacy and security guarantees. As new data records are uploaded by data owners, these data structures are continually updated by Longshot using novel algorithms that leverage bounded information leakage to minimize the use of expensive cryptographic protocols. Furthermore, Long-shot organizes the data structures as a hierarchical tree based on when the update occurred, allowing for update strategies that provide logarithmic error over time. Through this approach, Longshot introduces a tunable three-way trade-off between privacy, accuracy, and efficiency. Our experimental results confirm that our optimizations are not only asymptotic improvements but also observable in practice. In particular, we see a 5x efficiency improvement to update our data structures even when the number of updates is less than 200. Moreover, the data structures significantly improve query runtimes over time, about ~10 3 x faster compared to the baseline after 20 updates.