Events - Colloquia & Seminars

CCIS Colloquium Spring 2007

New Locally Decodable Codes and Private Information Retrieval Schemes

Speaker: Sergey Yekhanin

Affiliation: MIT

Date: Monday, February 12, 2007

Talk: 12:00 pm, 366 WVH

Abstract

A line of research originating in early 1990s has led to discovery of two related beautiful notions that are of major importance to modern complexity theory and cryptography, namely that of Locally Decodable Codes (LDCs) and Private Information Retrieval schemes (PIRs). A q-query Locally Decodable Code (LDC) is an error-correcting code that encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only q bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. A q-server private information retrieval (PIR) scheme is a cryptographic protocol that allows a user to retrieve the i-th bit of an n-bit string x replicated between q servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity, namely the number of bits exchanged by the user and the servers.

We give new constructions of three query LDCs of vastly shorter length than that of previous constructions. Specifically, given any Mersenne prime p=2^t-1, we design three query LDCs of length N=EXP(n^{1/t}), for every n. Based on the largest known Mersenne prime, this translates to a length of less than EXP(n^{10^{-7}}), compared to EXP(n^{1/2}) in the previous constructions. It has often been conjectured that there are infinitely many Mersenne primes. Under this conjecture, our constructions yield three query locally decodable codes of length N=EXP(n^{1/log log n}) for infinitely many n.

We also obtain analogous improvements for Private Information Retrieval (PIR) schemes. We give 3-server PIR schemes with communication complexity of O(n^{10^{-7}}) to access an n-bit database, compared to the previous best scheme with complexity O(n^{1/5.25}). Assuming again that there are infinitely many Mersenne primes, we get 3-server PIR schemes of communication complexity n^{O(1/log log n)} for infinitely many n.

Biography

Sergey Yekhanin has graduated from Moscow State University in 2002, and is currently pursuing a Ph.D. at MIT under the supervision of Madhu Sudan. Sergey's research interests lie in computational complexity theory, cryptography and the theory of error-correcting codes.