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 E4-04-06, Engineering block E4, NUS 
FEES No Charge 

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 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.

In this work, we show that information-theoretic 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 k-server 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 k-server 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 *k-server PIR codes*. We then show how such codes can be constructed from Steiner systems, from one-step majority logic decodable codes, from constant-weight codes, and from certain locally recoverable codes. We also establish several bounds on the parameters of k-server 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]

Alexander Vardy came to the Jacobs School in 1998 from the faculty of the University of Illinois, Urbana-Champaign. 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 Editor-in-Chief 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. 

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.