Locally Decodable Codes, 2-Server PIR, and MPIR

Abstract

Locally decodable codes solve the problem of encoding messages in such a way that they are both resistant to corruption in some bits, and can efficiently be decoded locally without decoding the entire message. Private information retrieval protocols allow a user to retrieve some data from a server without the server knowing which data the user is looking for. LDCs and PIR protocols are closely linked; defining an instance of one immediately provides the other. We give an introduction to these two ideas, and show how they are linked. We pay particular attention to 2-server PIR protocols, describing some known constructions. Then, we turn our attention to PIR protocols with multiple rounds, and show that a linear MPIR protocol can be reduced to a single round without an increase in communication cost.