Title: 2-Server PIR with sub-polynomial communication
Speaker: Sivakanth Gopi, Princeton University
Date: Wednesday, February 18, 2015 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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. The privacy of the user is information theoretic and does not rely on any cryptographic assumptions. In this work we construct a new 2-server PIR scheme with total communication cost sub polynomial in $n$. This improves over the currently known 2-server protocols which require $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.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S15/