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

协作研究：CIF：中：缓存辅助多用户私有函数检索的基本限制

• 批准号: 2312229
• 负责人: Daniela Tuninetti
• 金额: $ 46万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-10-01 至 2027-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2312229&HistoricalAwards=false
• 关键词: Collaborative; Research; CIF; Medium; Fundamental

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.

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