Events Fall 2014

TCS+ Online Seminar

Jan 21, 2015 10:00 am – 11:00 am 

Add to Calendar


Zeev Dvir (Princeton University)


Calvin Lab 116

2-Server PIR with sub-polynomial communication

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit database replicated among two servers (which do not communicate) while not revealing any information about i to either server. In this work we construct a 1-round 2-server PIR with total communication cost O(n^sqrt(log log n/log n)). This improves over the currently known 2-server protocols which require O(n^(1/3)) communication and matches the communication cost of known 3-server PIR schemes. Our improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives

Joint work with Sivakanth Gopi (Princeton University). [arXiV abs/1407.6692]