TOPIC 
Private Information Retrieval: Coding Instead of Replication 
AREA 
Communications & Networks 
SPEAKER 
Professor Alexander Vardy, University of California San Diego 
DATE 
23 June 2016, Thursday 
TIME 
3.30 pm to 5.00 pm 
VENUE 
E40406, Engineering block E4, NUS 
FEES 
No Charge 
SYNOPSIS 
Private information retrieval 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 informationtheoretic kserver PIR, the database is replicated among k noncommunicating 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 singleserver informationtheoretic PIR is impossible, the storage overhead of all existing PIR protocols is at least 2.
In this work, we show that informationtheoretic PIR can be achieved with storage overhead arbitrarily close to the optimal value of 1, without sacrificing the communication complexity. Specifically, we prove that *all* known kserver PIR protocols can be efficiently emulated, while preserving both privacy and communication complexity but significantly reducing the storage overhead. To this end, we distribute the n bits of the database among s+r servers, each storing n/s coded bits (rather than replicas). Notably, our coding scheme remains the same, regardless of the specific kserver PIR protocol being emulated. For every fixed k, the resulting storage overhead (s+r)/s approaches 1 as s grows; explicitly we have r \leq k \sqrt{s} (1+o(1)).
In order to achieve these results, we introduce and study a new kind of binary linear codes, called here *kserver PIR codes*. We then show how such codes can be constructed from Steiner systems, from onestep majority logic decodable codes, from constantweight codes, and from certain locally recoverable codes. We also establish several bounds on the parameters of kserver PIR codes, and tabulate the results for all s &#lt; 32 and k &#lt; 16.
[Based on joint work with students of speaker: Arman Fazeli and Eitan Yaakobi] 
ABOUT THE SPEAKER
 Alexander Vardy came to the Jacobs School in 1998 from the faculty of the University of Illinois, UrbanaChampaign. Before that, he worked in the private sector, including a stint as a visiting scientist at the IBM Almaden Research Center. Among other honors, he is a Fellow of the IEEE and a past EditorinChief of the IEEE Transactions on Information Theory. He received his Ph.D. in Electrical Engineering in 1991 from Tel Aviv University. Vardy is a recipient of a David and Lucile Packard Fellowship and an NSF CAREER award. 
REMARKS, IF ANY
 Host: Dr Vincent Tan YF. 
 Back to seminar list 
All are welcome to attend these seminars. Should
you have any enquiries, please contact Ms Veronica Au , Tel: 6516 2109.
