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

这个项目的动机是需要有效地执行复杂的查询，在大规模的数据库的方式，最大限度地减少使用的通信资源，同时保护发起查询的实体的隐私。这样的查询是存储在远程服务器上的数据点的函数;例如，双线性操作是用于构建支持在线大数据分析和数据挖掘过程的复杂查询的广泛使用的基本原语。在移动边缘计算等场景中，为了计算所需的输出值而在本地下载所有输入变量太消耗资源。相反，希望直接下载所需输出函数的结果，这也应该保持私有。该项目开发了一个原则性和整体性的框架，用于在分布式缓存辅助节点上私下检索基于本地计算的数据和从多个服务器接收的数据的函数输出的问题。这个问题是在交叉点的领域，个别已收到显着的关注，最近，即分布式编码缓存和私人信息检索。该项目旨在从信息理论和算法设计的角度显着推进分布式环境中私有函数检索的最新技术，从而建立私有缓存，计算和通信的基础。该项目还具有丰富的教育内容。该项目的新发现将被纳入三个合作机构的本科和研究生教育课程。该项目的目标是组织在三个主要的研究方向：（1）设计最佳的编码缓存计划，用户私有功能检索;（2）由分布式设置，其中用户也可能是一个发送者的动机，设计最佳的服务器私有功能检索策略;（3）克服复杂性瓶颈，在实际的分布式计算系统与服务器和/或用户隐私。设计的代码和算法将在Amazon EC2和POWDER（5G平台）上实现，以提供概念验证，证明所提出的解决方案具有大规模的实际影响。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.