CAREER: Sketching for Secure Computation on Large Inputs

George Washington University, Washington DC

Investigators

Abstract

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.