Collaborative Research: CIF: Medium: Fundamental Limits of Cache-aided Multi-user Private Function Retrieval

About This Grant

This project is motivated by the need to efficiently execute complex queries on massive databases in a way that minimizes the use of communication resources while preserving the privacy of the entity that initiated the query. Such queries are functions of the data points that are stored at remote servers; for example, bi-linear operations are widely used fundamental primitives for building the complex queries that support on-line big-data analytics and data mining procedures. In scenarios such as mobile-edge computing, it is too resource-consuming to download locally all the input variables in order to compute the desired output value. Instead, it is desirable to directly download the result of the desired output function, which should also be kept private. This project develops a principled and holistic framework for the problem of privately retrieving, at distributed cache-aided nodes, the output of functions based on both data that is locally computed and data that is received from multiple servers. This problem is at the intersection of areas that individually have received significant attention lately, namely, distributed coded caching and private information retrieval. This project aims to significantly advance the state-of-the-art of private function retrieval in distributed settings from both an information theory and an algorithm design perspective, thus establishing a foundation of private caching, computing and communication. The project also features a rich educational component. The novel findings from this project will be incorporated into the education offerings, in both undergraduate and graduate levels, at the three collaborating institutions. The project objectives are organized in three main research thrusts: (1) design optimal coded caching schemes for user-private function retrieval; (2) motivated by distributed settings in which a user may also be a sender, devise optimal server-private function retrieval strategies; and (3) overcome complexity bottlenecks in practical distributed computing systems with server- and/or user-privacy. The designed codes and algorithms will be implemented on Amazon EC2 and POWDER (5G platform) to provide a proof-of-concept that the proposed solutions have a practical impact at scale. 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.