Lightweight Techniques for Private Heavy Hitters
Lightweight Techniques for Private Heavy Hitters
复制标题
DOI：
10.1109/sp40001.2021.00048
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
D. Boneh;Elette Boyle;Henry Corrigan-Gibbs;N. Gilboa;Yuval Ishai
中科院分区：
文献类型：
--
作者：
D. Boneh;Elette Boyle;Henry Corrigan-Gibbs;N. Gilboa;Yuval Ishai
本文提出了一种新的解决私密重击问题的协议。在这个问题中，有许多客户端和一组很小的数据收集服务器。每个客户端都有一个私有的位串。服务器希望恢复所有常用字符串的集合，而不需要了解有关任何客户端字符串的任何其他信息。例如，一家网络浏览器供应商可以使用我们的协议来确定哪些主页很受欢迎，而不需要了解任何用户的主页。我们还考虑了更简单的私有子集-直方图问题，在该问题中，服务器希望统计在特定集合中有多少客户端持有字符串，而不向客户端透露该集合。我们的协议使用两个数据收集服务器，在协议运行中，每个客户端发送端只向服务器发送一条消息。我们的协议保护客户端隐私，防止其中一个服务器的任意不当行为，并且我们的方法不需要公钥密码术(安全通道除外)，也不需要通用多方计算。相反，我们依赖于增量分布式点函数，这是一种新的密码工具，允许客户端简洁地秘密共享指数级大的二叉树节点上的标签，前提是该树有一条非零路径。在此过程中，我们开发了新的通用工具，用于在分布式点函数的应用中提供恶意安全。我们的Heavy-Hit协议的一个限制是，它向服务器揭示的信息比流行字符串本身稍微多一些。我们准确地定义和量化了这种泄漏，并解释了如何改善其影响。在对美国两边两台服务器进行的试验性评估中，服务器可以在54分钟内从一组40万个客户端持有的256位字符串中找到200个最受欢迎的字符串。我们的协议高度可并行化。我们估计，每台逻辑服务器有20台物理机，我们的协议可以在一个小时多一点的计算时间内计算1000多万台重量级客户端。
This paper presents a new protocol for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client’s string. A web-browser vendor, for instance, can use our protocol to figure out which homepages are popular, without learning any user’s homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients.Our protocols use two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Our protocols protect client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions.A limitation of our heavy-hitters protocol is that it reveals to the servers slightly more information than the set of popular strings itself. We precisely define and quantify this leakage and explain how to ameliorate its effects. In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, our protocols could compute heavy hitters over ten million clients in just over one hour of computation.