CIF: Small: Secure and Private Function Computation by Interactive Communication

这项研究采用信息论的方法来开发管理托管用户数据的多个终端的安全或私有函数计算的原则。终端的目标是使用交互通信协议本地且可靠地计算所有可能相关的用户数据的给定函数。该协议需要满足不同的安全和隐私条件。前者规定，对于每个终端，剩余终端的联盟不应从它们自己的数据和通信中收集关于终端上的数据的更多信息--比从函数值中获得的信息更多。后者保护每个单独用户在终端上的数据不受类似联盟的影响。为分析不同的安全和隐私概念，开发了一个公共框架，并提出了新的信息理论公式和方法，目的是理解基本的基本原理。例如，潜在的应用出现在：存储临床药物试验结果的医院数据库或具有学生表现记录的大学数据库；从存储在私有云中的用户数据检索私人信息；以及对参与众包交通和导航服务的社区和个人的身份/位置进行安全和隐私认证。研究人员的技术方法涉及到一个具有三个主要特点的理论的发展。它(I)确定了交互通信在降低通信复杂性和增强安全性和保密性方面的关键作用；并用条件Renyi熵的形式来表示安全和隐私的可计算度量；(Ii)提供了一个公共框架来描述和分析安全和私有函数计算问题，其中经典香农理论和零错误组合信息理论具有突出的作用；并引入了多用户隐私区域的概念来量化用户之间的隐私权衡；(Iii)通过分析交互通信协议在函数计算中产生的公共随机性或共享信息，提出了一种获得通信复杂性逆界的新方法。这项研究植根于信息论、估计论和理论计算机科学，其中心目标是阐明计算精度、终端安全和用户隐私之间的权衡；这些权衡的关键是交互通信的关键作用。此外，它的目的是通过引入新的模型和概念来促进信息论的进步。预期结果是上述基本权衡的精确描述，以及用于安全和私有计算的相关算法。

This research takes an information theoretic approach to develop principles that govern secure or private function computation by multiple terminals that host user data. The goal of the terminals is to compute locally and reliably, a given function of all the possibly correlated user data, using an interactive communication protocol. The protocol is required to satisfy separate security and privacy conditions. The former stipulates for each terminal that a coalition of the remaining terminals should glean no more information about the data at the terminal from their own data and the communication -- than can be obtained from the function value. The latter protects each individual user's data at a terminal from a similar coalition. A common framework is developed for analyzing the distinct concepts of security and privacy, and new information theoretic formulations and approaches are proposed with the objective of understanding basic underlying principles. Potential applications arise, for instance, in: hospital databases that store clinical drug trial results or university databases with student performance records; private information retrieval from user data stored in private clouds; and security and privacy certifications for the identities/locations of communities and individuals participating in crowd-sourced traffic and navigation services. The investigators' technical approach involves the development of a theory with three main distinguishing features. It (i) establishes a key role for interactive communication in reducing communication complexity, and in enhancing security and privacy; and formulates computable measures of security and privacy in terms of conditional Renyi entropy; (ii) provides a common framework for formulating and analyzing problems of secure and private function computation with prominent roles for classical Shannon theory as well as zero-error combinatorial information theory; and introduces the concept of a multiuser privacy region for quantifying privacy tradeoffs among users; and (iii) develops a new method for obtaining converse bounds for communication complexity, upon analyzing the common randomness or shared information generated in function computation with an interactive communication protocol. Rooted in information theory, estimation theory and theoretical computer science, a central objective of the research is to elucidate tradeoffs among computation accuracy, terminal security and user privacy; key to these tradeoffs is the essential role of interactive communication. Furthermore, it aims at creating advances in information theory through the introduction of new models and concepts. Expected outcomes are precise characterizations of the mentioned fundamental tradeoffs, and associated algorithms for secure and private computing.