CAREER: Sketching for Secure Computation on Large Inputs

如今，隐私敏感的个人数据无处不在。对大量个人数据的收集和分析已经变得很普遍，并且是快速增长的应用程序和服务的内在功能。虽然从功能的角度来看是可取的，但这种现在流行的计算范式引发了前所未有的安全和隐私问题。一个关键的研究挑战是设计安全和私有计算协议，可以扩展到这些海量数据。这个项目的重点是通过结合安全多方计算、草图算法和差分隐私等技术来开发这样的协议。为了使安全计算扩展到大量输入，有必要开发成本（即计算和通信）在输入大小上呈次线性的协议。该项目结合了上述三个领域的进展来实现这一目标。首先，研究了素描算法的隐私特性，开发了适合安全多方计算的算法。接下来，该项目将研究必要的修改，以使生成的协议对恶意用户和输入具有鲁棒性。然后，它将考虑素描算法的近似性质如何影响结果计算的隐私性，并利用差分隐私来确保维护个人隐私。最后，该项目将这些方法结合起来，为实际应用程序实例化协议。该项目的成果将为机器学习和网络测量等大数据应用提供新的安全和隐私保护计算。此外，该项目将为研究生和本科生提供研究机会和新的课程材料。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Today, privacy sensitive personal data is everywhere. Collecting and performing analytics on large amounts of personal data has become widespread and is intrinsic to the functionality of a rapidly growing number of apps and services. While desirable from a functionality perspective, this now popular computing paradigm raises unprecedented security and privacy concerns. A key research challenge is to design protocols for secure and private computation that can scale to these massive volumes of data. The focus of this project is to develop such protocols by combining techniques from secure multi-party computation, sketching algorithms, and differential privacy.To make secure computation scale to massive inputs, it is necessary to develop protocols with costs (i.e., computation and communication) sublinear in the input size. This project combines advances in all three of the areas mentioned above to achieve this goal. First, the project studies the privacy properties of sketching algorithms and develops algorithms well suited to secure multi-party computation. Next, the project will study the necessary modification to make the resulting protocols robust to malicious users and inputs. Then, it will consider how the approximate nature of sketching algorithms impacts the privacy of the resulting computations and leverage differential privacy to ensure that individual privacy is maintained. Finally, the project combines these approaches to instantiate protocols for real-world applications. The results of this project will enable new secure and privacy-preserving computations for large-data applications such as machine learning and network measurement. Additionally, the project will result in research opportunities and new course materials for graduate and undergraduate students.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.