Colloquia, Seminars and Conference News
Title : New Locally Decodable Codes and Private Information Retrieval Schemes
Date : March 23, 2007. (2:00 pm) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Mr. Sergey Yekhanin
Abstract:
A q-query Locally Decodable Code (LDC) is an error-correcting code that encodes an n-bit message x as a 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. The goal of LDC related research is to minimize the length of such codes.
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 goal of PIR related research is to minimize the communication complexity of such schemes.
We present a novel algebraic approach to LDCs and PIRs and obtain vast improvements upon the earlier work. Specifically, given any Mersenne prime p = 2^t - 1, we design three query LDCs of length 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. We also design 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}).
It has often been conjectured that there are infinitely many Mersenne primes. Under this conjecture, our constructions yield three query locally decodable codes of subexponential length and three server private information retrieval schemes with subpolynomial communication complexity.
Bio: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.
[Back]
