Technical Report PHD-2008-08

Title: Locally decodable codes and their applications
Authors: Omer Barkol
Supervisors: Yuval Ishai and Ronny Roth
Abstract: Locally Decodable Codes (LDCs) are error-correcting codes in which each symbol of the message can be retrieved by probabilistically probing a limited number of symbols from an adversarially corrupted encoding of the message. This thesis covers several questions that are related to LDCs.

A stronger and desirable property than local decodability is that of self-correction, allowing to efficiently recover not only symbols of the message but also arbitrary symbols of the encoded message. In contrast to the initial constructions of LDCs, the recent and most efficient constructions are not known to be self-correctable. The existence of self-correctable codes of comparable efficiency remains open. The best self-correctable codes known are based on multivariate polynomial representations over finite fields. We study the question of closing this current gap, and relate this question to a conjecture from the 1970s concerning the algebraic rank of combinatorial designs.

Closely related to LDCs is the cryptographic problem of Private Information Retrieval (PIR). A PIR protocol allows a user to retrieve a data item from a database which is replicated amongst a number of servers, such that each individual server learns nothing about the identity of the item being retrieved. We use LDCs and self-correctable codes to construct better PIR protocols that offer privacy even against coalitions of several servers.

We then investigate a generalization of PIR, where the user privately searches a database, e.g., for partial match or nearest neighbor. Motivated by the observation that many natural database search problems can be solved by constant-depth circuits, we present efficient distributed protocols for privately evaluating circuits from this class. To this end we extend previous techniques for representing constant-depth circuits by probabilistic low-degree polynomials.

Motivated in part by the goal of improving our protocols for private database search, we study the power of d-multiplicative secret sharing. Such secret sharing schemes allow players to locally convert shares of d secrets into an additive sharing of their product. While the case d=2 is fairly well understood, in the case of d>2 secrets it was not even known how the minimal number of players should depend on the desired level of privacy. We prove a negative result, showing that known constructions are optimal with respect to the required number of players. Interestingly, the proof relies on a quantitative communication complexity argument.

Finally, inspired by techniques used for constructing LDCs, we consider a setting where different players get replicated copies of the same database which are partially erased, and should still allow a referee to compute a function of the database with no interaction and with minimum communication. This is applicable in different settings, such as sensors that measure the same phenomena in parallel, or a database that is locally changed after it was distributed. We present interesting connections between this problem and secret sharing. We use these connections to obtain nontrivial upper bounds and lower bounds using results and techniques from the domain of secret sharing.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2008
To the main CS technical reports page

Computer science department, Technion