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

该项目的动机是需要高效地在大型数据库上执行复杂的查询，同时最大限度地减少通信资源的使用，同时保护发起查询的实体的隐私。这种查询是存储在远程服务器上的数据点的函数；例如，双线性运算是用于构建支持在线大数据分析和数据挖掘过程的复杂查询的广泛使用的基本原语。在移动边缘计算等场景中，为了计算期望的输出值，在本地下载所有输入变量太耗费资源。相反，希望直接下载所需输出函数的结果，这也应该是保密的。该项目为在分布式缓存辅助节点上根据本地计算的数据和从多个服务器接收的数据私自检索函数输出的问题开发了一个原则性的整体框架。这个问题是最近单独受到关注的领域的交叉点，即分布式编码缓存和私有信息检索。该项目旨在从信息论和算法设计的角度，显著提高分布式环境下私有函数检索的最新水平，从而为私有缓存、计算和通信奠定基础。该项目还具有丰富的教育内容。这一项目的新发现将被纳入三个合作机构的本科生和研究生教育课程。该项目的目标被组织为三个主要的研究主题：(1)设计用于用户-私有函数检索的最优编码缓存方案；(2)受分布式环境(其中用户可能也是发送者)的启发，设计最优的服务器-私有函数检索策略；(3)克服具有服务器和/或用户隐私的实际分布式计算系统中的复杂性瓶颈。所设计的代码和算法将在Amazon EC2和SHARE(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.