Towards 3-query locally decodable codes of subexponential length

ABSTRACT

A q-query Locally Decodable Code (LDC) encodes an n-bitmessage x as an n-bit codeword C(x), such that one canprobabilistically recover any bit x_i of the message by queryingonly q bits of the codeword C(x), even after some constantfraction of codeword bits has been corrupted.We give new constructions of three query LDCs of vastly shorterlength than that of previous constructions. Specifically, givenany Mersenne prime p = 2^t - 1, we design three query LDCs of length N=(n^1/t), for every n. Based on thelargest 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 hasoften been conjectured that there are infinitely many Mersenneprimes. Under this conjecture, our constructions yield three querylocally decodable codes of length N=exp(n^{O(1/(log log n))}) forinfinitely many n.

We also obtain analogous improvements for Private InformationRetrieval (PIR) schemes. We give 3-server PIR schemes withcommunication complexity of O(n^10-7) to accessan n-bit database, compared to the previous best scheme withcomplexity O(n^1/5.25). Assuming again that there areinfinitely many Mersenne primes, we get 3-server PIR schemes ofcommunication complexity n^{O(1/(log log n))}for infinitely many n.

Previous families of LDCs and PIR schemes were based on theproperties of low-degree multivariate polynomials over finitefields. Our constructions are completely different and areobtained by constructing a large number of vectors in a smalldimensional vector space whose inner products are restricted tolie in an algebraically nice set.

References

1. A. Ambainis, "Upper bound on the communication complexity of private information retrieval," Proc. of 32th ICALP, LNCS 1256, pp. 401--407, 1997.
2. R. Beigel, L. Fortnow, and W. Gasarch, "A tight lower bound for restricted PIR protocols," Computational Complexity, vol.15 pp. 82--91, 2006.
3. L. Babai, L. Fortnow, L. Levin, and M. Szegedy, "Checking computations in polylogarithmic time," . In Proc. of the 23th ACM Sym. on Theory of Computing (STOC), pp. 21--31, 1991.
4. L. Babai, P. Frankl, "Linear Algebra Methods in Combinatorics." 1998.
5. A. Beimel, Y. Ishai and E. Kushilevitz,"General constructions for information-theoretic private information retrieval," Journal of Computer and System Sciences, vol. 71, pp. 213--247, 2005. Preliminary versions in STOC 1999 and ICALP 2001.
6. A. Beimel, Y. Ishai, E. Kushilevitz, and J. F. Raymond. "Breaking the O(n^1/(2k-1)) barrier for information-theoretic private information retrieval," In Proc. of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 261--270, 2002.
7. B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. "Private information retrieval," In Proc. of the 36rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 41--50, 1995. Also, in Journal of the ACM, 45, 1998.
8. A. Deshpande, R. Jain, T. Kavitha, S. Lokam and J. Radhakrishnan, "Better lower bounds for locally decodable codes," In Proc. of the 20th IEEE Computational Complexity Conference (CCC), pp. 184--193, 2002.
9. Curtis Cooper, Steven Boone, http://www.mersenne.org/32582657.htm
10. W. Gasarch, "A survey on private information retrieval," The Bulletin of the EATCS, 82:72--107, 2004.
11. O. Goldreich, "Short Locally Testable Codes and Proofs," Technical Report TR05-014, Electronic Colloquim on Computational Complexity (ECCC), 2005.
12. O. Goldreich, H. Karloff, L. Schulman, L. Trevisan "Lower bounds for locally decodable codes and private information retrieval," In Proc. of the 17th IEEE Computational Complexity Conference (CCC), pp. 175--183, 2002.
13. T. Itoh, "Efficient private information retrieval," IEICE Trans. Fund. of Electronics, Commun and Comp. Sci., E82-A(1):11--20, 1999.
14. T. Itoh, "On lower bounds for the communication complexity of private information retrieval," IEICE Trans. Fund. of Electronics, Commun. and Comp. Sci., E84-A(1):157--164, 2001.
15. J. Katz and L. Trevisan, "On the efficiency of local decoding procedures for error-correcting codes," In Proc. of the 32th ACM Sym. on Theory of Computing (STOC), pp. 80--86, 2000.
16. I. Kerenidis, R. de Wolf, "Exponential Lower Bound for 2-query locally decodable codes via a quantum argument," Journal of Computer and System Sciences, 69(3), pp. 395--420. Earlier version in STOC'03. quant-ph/0208062.
17. R. Lidl and H. Niederreiter, Finite Fields. Cambridge: Cambridge University Press, 1983.
18. E. Mann, Private access to distributed information. Master's thesis, Technion - Israel Institute of Technology, Haifa, 1998.
19. L. Murata, C. Pomerance, "On the largest prime factor of a Mersenne number," Number theory, CRM Proc. Lecture Notes of American Mathematical Society vol. 36, pp. 209--218, 2004.
20. K. Obata, "Optimal lower bounds for 2-query locally decodable linear codes," In Proc. of the 6th RANDOM, vol. 2483 of Lecture Notes in Computer Science, pp. 39--50, 2002.
21. A. Polishchuk and D. Spielman," Nearly-linear size holographic proofs," In Proc. of the 26th ACM Sym. on Theory of Computing (STOC), pp. 194--203, 1994.
22. C. Pomerance, "Recent developments in primality testing," Math. Intelligencer, 3:3, pp. 97--105, (1980/81).
23. A. Razborov and S. Yekhanin "An Ω(n^1/3) Lower Bound for Bilinear Group Based Private Information Retrieval," In Proc. of the 47rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 739--748, 2006.
24. M. Sudan, Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. PhD thesis, University of California at Berkeley, 1992.
25. L. Trevisan, "Some Applications of Coding Theory in Computational Complexity," Quaderni di Matematica, 13:347--424, 2004.
26. S. Wehner and R. de Wolf, "Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval," In Proc. of 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), LNCS 3580, pp.1424--1436.
27. Lenstra-Pomerance-Wagstaff conjecture. (2006, May 22). In Wikipedia, The Free Encyclopedia. Retrieved 00:18, October 3, 2006, from http://en.wikipedia.org/w/index.php?title=Lenstra-Pomerance-Wagstaff_conjecture&oldid=54506577
28. S. Wagstaff, "Divisors of Mersenne numbers," Math. Comp., 40:161, pp. 385--397, 1983.
29. Mersenne prime. (2006, October 1). In Wikipedia, The Free Encyclopedia. Retrieved 21:04, October 2, 2006, from http://en.wikipedia.org/w/index.php?title=Mersenne_prime&oldid=78877957
30. D. Woodruff, "New lower bounds for general locally decodable codes," Electronic Colloquium on Computational Complexity, TR07-006, 2007.
31. D. Woodruff and S. Yekhanin, "A Geometric Approach to Information Theoretic Private Information Retrieval," In Proc. of the 20th IEEE Computational Complexity Conference (CCC), pp. 275--284, 2005.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software development techniques

      • Error handling and recovery