Private Information Retrieval — Coding Instead of Replication

Speaker: Tuvi Etzion
Affiliation: Technion, Haifa, Israel

Abstract: Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database without revealing any information about the identity of the item being retrieved. Specifically, in information-theoretic k-server PIR, the database is replicated among k non-communicating servers, and each server learns nothing about the item retrieved by the user. The effectiveness of PIR protocols is usually measured in terms of their communication complexity, which is the total number of bits exchanged between the user and the servers. However, another important cost parameter is the storage overhead, which is the ratio between the total number of bits stored on all the servers and the number of bits in the database. Since single-server information-theoretic PIR is impossible, the storage overhead of all existing PIR protocols is at least 2 (or k, in the case of k-server PIR). Coding in private information retrieval was considered only in the last two years by the information theory community, as opposed to the original problem which was considered by the computer science community for the last twenty years. One new direction was to consider only the download complexity, since by the large size R of a record the download complexity will be larger than the upload complexity. A second direction is to encode the information to reduce the storage overhead, while preserving the other communication costs. This talk will introduce these two new directions of research.

Biography: Tuvi Etzion (M’89–SM’94–F’04) was born in Tel Aviv, Israel, in 1956. He received the B.A., M.Sc., and D.Sc. degrees from the Technion – Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1984, respectively. From 1984, he held a position in the Department of Computer Science at the Technion, where he has a Professor position. During the years 1985-1987, he was Visiting Research Professor with the Department of Electrical Engineering – Systems at the University of Southern California, Los Angeles. During the summers of 1990 and 1991, he was visiting Bellcore in Morristown, New Jersey. During the years 1994-1996, he was a Visiting Research Fellow in the Computer Science Department at Royal Holloway College, Egham, England. He also had several visits to the Coordinated Science Laboratory at University of Illinois in Urbana-Champaign during the years 1995-1998; two visits to HP Bristol during the summers of 1996, 2000; a few visits to the Department of Electrical Engineering, University of California at San Diego during the years 2000-2016, and several visits to the Mathematics Department at Royal Holloway College, Egham, England, during the years 2007-2009 and 2016. His research interests include applications of discrete mathematics to problems in computer science and information theory, coding theory, and combinatorial designs. Dr. Etzion was an Associate Editor for Coding Theory for the IEEE Transactions on Information Theory from 2006 till 2009. From 2004 to 2009, he was an Editor for the Journal of Combinatorial Designs. From 2011, he has been an Editor for Designs, Codes, and Cryptography. From 2013, he has been an Editor for Advances of Mathematics in Communications.

For more information, contact Prof. Lara Dolecek ()

Date(s) - Nov 30, 2016
11:00 am - 12:30 pm

E-IV Maxwell Room #57-124
420 Westwood Plaza - 5th Flr. , Los Angeles CA 90095