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.