Abstract
This work considers locally decodable codes in the computationally bounded channel model. The computationally bounded channel model, introduced by Lipton in 1994, views the channel as an adversary which is restricted to polynomial-time computation. Assuming the existence of IND-CPA secure public-key encryption, we present a construction of public-key locally decodable codes, with constant codeword expansion, tolerating constant error rate, with locality \({\mathcal O}(\lambda)\), and negligible probability of decoding failure, for security parameter λ. Hemenway and Ostrovsky gave a construction of locally decodable codes in the public-key model with constant codeword expansion and locality \({\mathcal O}(\lambda^2)\), but their construction had two major drawbacks. The keys in their scheme were proportional to n, the length of the message, and their schemes were based on the Φ-hiding assumption. Our keys are of length proportional to the security parameter instead of the message, and our construction relies only on the existence of IND-CPA secure encryption rather than on specific number-theoretic assumptions. Our scheme also decreases the locality from \({\mathcal O}(\lambda^2)\) to \({\mathcal O}(\lambda)\). Our construction can be modified to give a generic transformation of any private-key locally decodable code to a public-key locally decodable code based only on the existence of an IND-CPA secure public-key encryption scheme.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bhattacharyya, R., Chakraborty, S.: Constant query locally decodable codes against a computationally bounded adversary (2011), http://people.cs.uchicago.edu/sourav/papers/LDCbounded.pdf
Babi, L., Fortnow, L., Levin, L., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC 1991, pp. 21–31 (1991)
Cachin, C., Micali, S., Stadler, M.A.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Efremenko, K.: 3-query locally decodable codes of subexponential length. In: STOC 2009, pp. 39–44. ACM, New York (2009)
Gopalan, P., Lipton, R.J., Ding, Y.Z.: Error correction against computationally bounded adversaries (2004) (manuscript)
Guruswami, V., Smith, A.: Codes for computationally simple channels: Explicit constructions with optimal rate. In: FOCS 2010 (2010)
Hemenway, B., Ostrovsky, R.: Public-key locally-decodable codes. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 126–143. Springer, Heidelberg (2008)
Hush, D., Scovel, C.: Concentration of the hypergeometric distribution. Statistics and Probability Letters 75, 127–132 (2005)
Kopparty, S., Saraf, S., Yekhanin, S.: High-rate codes with sublinear-time decoding. In: STOC 2011 (2011)
Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC 2000: Proceedings of the 32nd Annual Symposium on the Theory of Computing, pp. 80–86 (2000)
Lipton, R.J.: A new approach to information theory. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol. 775, pp. 699–708. Springer, Heidelberg (1994)
Micali, S., Peikert, C., Sudan, M., Wilson, D.A.: Optimal error correction against computationally bounded noise. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 1–16. Springer, Heidelberg (2005)
Ostrovsky, R., Pandey, O., Sahai, A.: Private locally decodable codes. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 387–398. Springer, Heidelberg (2007)
Polishchuk, A., Spielman, D.: Nearly linear size holographic proofs. In: STOC 1994, pp. 194–203 (1994)
Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal 27, 343–379, 623–656 (1948)
Sudan, M.: Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. PhD thesis, UC Berkeley (1992)
Trevisan, L.: Some applications of coding theory in computational complexity. Quaderni di Matematica 13, 347–424 (2004)
Yekhanin, S.: Locally decodable codes. Foundations and Trends in Theoretical Computer Science (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hemenway, B., Ostrovsky, R., Strauss, M.J., Wootters, M. (2011). Public Key Locally Decodable Codes with Short Keys. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2011 2011. Lecture Notes in Computer Science, vol 6845. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22935-0_51
Download citation
DOI: https://doi.org/10.1007/978-3-642-22935-0_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22934-3
Online ISBN: 978-3-642-22935-0
eBook Packages: Computer ScienceComputer Science (R0)