CAREER: Sketching for Secure Computation on Large Inputs

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

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.