2018-06-07: The capacity of private information retrieval with eavesdroppers

Abstract

With the evolution of the Internet of things, big data, cloud storage and computing, much of the emerging technology relies on open systems and networks, which brings up new challenges in preserving data privacy and security in such applications. Recently, various privacy and security problems in the storage, fetching, and communication of data have been studied using tools from information theory, among which the problem of private information retrieval (PIR) brought up in the 90s in the computer science community has drawn new attention from researchers working in information theory.

In the problem of private information retrieval (PIR), a user wants to retrieval a file/message from a database efficiently, without revealing the identity of the retrieved file/message to the operator of the database. In some cases, the privacy of the database needs also to be preserved from the user, that is, the user should learn no information about the other files in the database. This is known as the problem of symmetric private information retrieval (SPIR).

In this talk, I will formulate the problem from an information theoretic perspective, and present our recent result on the capacity of private information retrieval with colluding servers and eavesdroppers (ETPIR). We find a surprising phenomenon that by adding eavesdroppers and allowing servers to collude in the PIR problem, there is a synergistic effect and the problem behaves differently in two regimes. The ETPIR problem includes many previous works and capacity results as special cases, and our work capitalizes on all ideas used in these works. Further, new challenges arise that go beyond previously studied problems, and we propose new ideas to resolve the corresponding challenges.

About Qiwen Wang

Qiwen Wang is currently a postdoctoral researcher at the Department of Information Science and Engineering. She received her B.Sc. in Mathematics and B.Eng. in Information Engineering in 2010, and doctoral degree in Information Engineering in 2015, all from the Chinese University of Hong Kong.

Her doctoral dissertation was focused on network error correction codes and file synchronization with insertions and deletions. Her main research interests include information theory, coding theory, and statistical learning.