Towards 3-query locally decodable codes of subexponential length

ABSTRACT

A q-query Locally Decodable Code (LDC) 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.

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(O(n^1/t)), for every n. Based on the largest known Mersenne prime, this translates to a length of less than exp(O(n^{10 − 7})) compared to exp(O(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^{O(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 logn)}) for infinitely many n.

Previous families of LDCs and PIR schemes were based on the properties of low-degree multivariate polynomials over finite fields. Our constructions are completely different and are obtained by constructing a large number of vectors in a small dimensional vector space whose inner products are restricted to lie in an algebraically nice set.

REFERENCES

• 1: Andris Ambainis, Upper Bound on Communication Complexity of Private Information Retrieval, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.401-407, July 07-11, 1997
• 2: László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
• 3: Babai, L., and Frankl, P. 1998. Linear algebra methods in combinatorics.
• 4: Richard Beigel , Lance Fortnow , William Gasarch, A tight lower bound for restricted PIR protocols, Computational Complexity, v.15 n.1, p.82-91, May 2006 [doi>10.1007/s00037-006-0208-3]
• 5: Amos Beimel , Yuval Ishai , Eyal Kushilevitz, General constructions for information-theoretic private information retrieval, Journal of Computer and System Sciences, v.71 n.2, p.213-247, August 2005 [doi>10.1016/j.jcss.2005.03.002]
• 6: Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Jean-François Raymond, Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.261-270, November 16-19, 2002
• 7: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 8: Amit Deshpande , Rahul Jain , T. Kavitha , Jaikumar Radhakrishnan , Satyanarayana V. Lokam, Better Lower Bounds for Locally Decodable Codes, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.184, May 21-24, 2002
• 9: Cooper, C., and Boone, S. 2006. http://www.mersenne.org/32582657.htm.
• 10: Gasarch, W. 2004. A survey on private information retrieval. Bull. EATCS 82, 72--107.
• 11: Goldreich, O. 2005. Short locally testable codes and proofs. Tech. Rep. TR05-014. In Proceedings of the Electronic Colloquim on Computational Complexity (ECCC).
• 12: Oded Goldreich , Howard Karloff , Leonard J. Schulman , Luca Trevisan, Lower bounds for linear locally decodable codes and private information retrieval, Computational Complexity, v.15 n.3, p.263-296, October 2006 [doi>10.1007/s00037-006-0216-3]
• 13: Itoh, T. 1999. Efficient private information retrieval. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E82-A, 1, 11--20.
• 14: Itoh, T. 2001. On lower bounds for the communication complexity of private information retrieval. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E84-A1, 157--164.
• 15: Kedlaya, K., and Yekhanin, S. 2007. Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. In Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-040.
• 16: Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
• 17: Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Journal of Computer and System Sciences, v.69 n.3, p.395-420, November 2004 [doi>10.1016/j.jcss.2004.04.007]
• 18: Lenstra, Jr., H. W. 1980. Primarlity testing. In Studieweek Getaltheorie en Computers (Sept. 1--5). Stichting Math., Centrum, Amsterdam, The Netherlands.
• 19: Lidl, R., and Niederreiter, H. 1983. Finite Fields. Cambridge University Press, Cambridge, MA.
• 20: Mann, E. 1998. Private access to distributed information. Master's thesis, Technion - Israel Institute of Technology, Haifa, Israel.
• 21: Kenji Obata, Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.39-50, September 13-15, 2002
• 22: Alexander Polishchuk , Daniel A. Spielman, Nearly-linear size holographic proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.194-203, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195132]
• 23: Pomerance, C. 1980/81. Recent developments in primality testing. Math. Intell. 3, 3, 97--105.
• 24: Alexander A. Razborov , Sergey Yekhanin, An \Omega(n^1/3 ) Lower Bound for Bilinear Group Based Private Information Retrieval, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.739-748, October 21-24, 2006 [doi>10.1109/FOCS.2006.10]
• 25: Madhu Sudan, Efficient checking of polynomials and proofs and the hardness of approximation problems, University of California at Berkeley, Berkeley, CA, 1992
• 26: Trevisan, L. 2004. Some applications of coding theory in computational complexity. Quad. Matemat. 13, 347--424.
• 27: Wehner, S., and de Wolf, R. 1997. Improved lower bounds for locally decodable codes and private information retrieval. In Proceedings of 32nd International Colloquium on Automata, Languages and Programming (ICALP'05). Lecture Notes in Computer Science, vol. 3580, Springer-Verlag, New York, pp. 1424--1436.
• 28: Wagstaff, S. 1983. Divisors of Mersenne numbers. Math. Comput. 40, 161, 385--397.
• 29: Woodruff, D. 2007. New lower bounds for general locally decodable codes. In Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-006.
• 30: David Woodruff , Sergey Yekhanin, A Geometric Approach to Information-Theoretic Private Information Retrieval, SIAM Journal on Computing, v.37 n.4, p.1046-1056, September 2007 [doi>10.1137/06065773X]
• 31: Yekhanin, S. 2006. New locally decodable codes and private infromation retrieval schemes. In Electronic Colloquium on Computational Complexity, Tech. rep. TR06-127.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

General Terms:
Theory

Keywords:
Locally decodable codes, Mersenne primes, private information retrieval