Mycelium: Large-Scale Distributed Graph Queries with Differential Privacy
Mycelium: Large-Scale Distributed Graph Queries with Differential Privacy
复制标题
DOI：
10.1145/3477132.3483585
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Edo Roth;Karan Newatia;Ke Zhong;Sebastian Angel;Andreas Haeberlen
中科院分区：
文献类型：
--
作者：
Edo Roth;Karan Newatia;Ke Zhong;Sebastian Angel;Andreas Haeberlen
本文介绍了 Mycelium，这是第一个对分布在数百万用户设备上的大型图进行差分隐私查询的系统。例如，在跟踪疾病或恶意软件的传播时，就会出现此类图表。如今，查询此类图表的唯一实用方法是将它们上传到中央聚合器，这需要用户的极大信任并完全排除某些类型的研究。借助 Mycelium，用户的私人数据永远不会在其个人设备上处于未加密状态，并且每个用户都会获得强大的隐私保证。 Mycelium 确实需要能够访问数据中心的中央聚合器的帮助，但聚合器只是通过提供带宽和计算能力来促进计算；它永远不会学习图的拓扑或底层数据。 Mycelium 通过结合同态加密、可验证的秘密重新分配方案和基于伸缩电路的混合网络来实现这一目标。我们的评估表明，Mycelium 可以通过数百万台设备回答医学文献中的一系列不同问题。
This paper introduces Mycelium, the first system to process differentially private queries over large graphs that are distributed across millions of user devices. Such graphs occur, for instance, when tracking the spread of diseases or malware. Today, the only practical way to query such graphs is to upload them to a central aggregator, which requires a great deal of trust from users and rules out certain types of studies entirely. With Mycelium, users' private data never leaves their personal devices unencrypted, and each user receives strong privacy guarantees. Mycelium does require the help of a central aggregator with access to a data center, but the aggregator merely facilitates the computation by providing bandwidth and computation power; it never learns the topology of the graph or the underlying data. Mycelium accomplishes this with a combination of homomorphic encryption, a verifiable secret redistribution scheme, and a mix network based on telescoping circuits. Our evaluation shows that Mycelium can answer a range of different questions from the medical literature with millions of devices.