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

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

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.