Locally Decodable Codes and Private Information Retrieval Schemes

This thesis studies two closely related notions, namely Locally Decodable Codes (LDCs) and Private Information Retrieval Schemes (PIRs). Locally decodable codes are error-correcting codes that allow extremely efficient, "sublinear-time" decoding procedures. More formally, a k-query locally decodable code encodes n-bit messages x in such a way that one can probabilistically recover any bit xi of the message by querying only k bits of the (possibly corrupted) code-word, where k can be as small as 2. LDCs were initially introduced in complexity theory in the context of worst-case to average-case reductions and probabilistically checkable proofs. Later they have found applications in numerous other areas including information theory, cryptography and the theory of fault tolerant computation. The major goal of LDC related research is to establish the optimal trade-off between length N and query complexity k of such codes, for a given message length n. Private information retrieval schemes are cryptographic protocols developed in order to protect the privacy of the user's query, when accessing a public database. In such schemes a database (modelled by an n-bit string x) is replicated between k non-communicating servers. The user holds an index i and is interested in obtaining the value of the bit xi. To achieve this goal, the user queries each of the servers and gets replies from which the desired bit xi can be computed. The query to each server is distributed independently of i and therefore each server gets no information about what the user is after. The main parameter of interest in a PIR scheme is its communication complexity, namely the number of bits exchanged by the user accessing an n-bit database and the servers. In this thesis we provide a fresh algebraic look at the theory of locally decodable codes and private information retrieval schemes.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2007

Author dc:creator

• Yekhanin, Sergey

Advisor dc:contributor.advisor

• Madhu Sudan.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/42242

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/42242