{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T01:53:08Z","timestamp":1778291588690,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642542411","type":"print"},{"value":"9783642542428","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54242-8_21","type":"book-chapter","created":{"date-parts":[[2014,2,3]],"date-time":"2014-02-03T02:42:54Z","timestamp":1391395374000},"page":"489-514","source":"Crossref","is-referenced-by-count":25,"title":["Locally Updatable and Locally Decodable Codes"],"prefix":"10.1007","author":[{"given":"Nishanth","family":"Chandran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bhavana","family":"Kanukurthi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-10366-7_19","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"G. Ateniese","year":"2009","unstructured":"Ateniese, G., Kamara, S., Katz, J.: Proofs of storage from homomorphic identification protocols. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 319\u2013333. Springer, Heidelberg (2009)"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Bowers, K.D., Juels, A., Oprea, A.: Proofs of retrievability: theory and implementation. In: Proceedings of the First ACM Cloud Computing Security Workshop, CCSW 2009, pp. 43\u201354 (2009)","DOI":"10.1145\/1655008.1655015"},{"key":"21_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-38348-9_17","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"D. Cash","year":"2013","unstructured":"Cash, D., K\u00fcp\u00e7\u00fc, A., Wichs, D.: Dynamic proofs of retrievability via oblivious RAM. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol.\u00a07881, pp. 279\u2013295. Springer, Heidelberg (2013)"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Chandran, N., Kanukurthi, B., Ostrovsky, R.: Locally updatable and locally decodable codes. Cryptology ePrint Archive, Report 2013\/520 (2013), http:\/\/eprint.iacr.org\/","DOI":"10.1007\/978-3-642-54242-8_21"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Chandran, N., Kanukurthi, B., Ostrovsky, R., Reyzin, L.: Privacy amplification with asymptotically optimal entropy loss. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 785\u2013794 (2010)","DOI":"10.1145\/1806689.1806796"},{"issue":"1","key":"21_CR6","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00037-011-0017-1","volume":"22","author":"Y.M. Chee","year":"2013","unstructured":"Chee, Y.M., Feng, T., Ling, S., Wang, H., Zhang, L.F.: Query-efficient locally decodable codes of subexponential length. Computational Complexity\u00a022(1), 159\u2013189 (2013)","journal-title":"Computational Complexity"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-00457-5_8","volume-title":"Theory of Cryptography","author":"Y. Dodis","year":"2009","unstructured":"Dodis, Y., Vadhan, S.P., Wichs, D.: Proofs of retrievability via hardness amplification. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 109\u2013127. Springer, Heidelberg (2009)"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC, pp. 39\u201344 (2009)","DOI":"10.1145\/1536414.1536422"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Towards a theory of software protection and simulation by oblivious rams. In: STOC, pp. 182\u2013194 (1987)","DOI":"10.1145\/28395.28416"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1007\/978-3-642-22012-8_46","volume-title":"Automata, Languages and Programming","author":"M.T. Goodrich","year":"2011","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Privacy-preserving access of outsourced data via oblivious RAM simulation. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 576\u2013587. Springer, Heidelberg (2011)"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Guo, A., Kopparty, S., Sudan, M.: New affine-invariant codes from lifting. In: Innovations in Theoretical Computer Science, ITCS, pp. 529\u2013540 (2013)","DOI":"10.1145\/2422436.2422494"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-642-22935-0_51","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"B. Hemenway","year":"2011","unstructured":"Hemenway, B., Ostrovsky, R., Strauss, M.J., Wootters, M.: Public key locally decodable codes with short keys. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM 2011 and APPROX 2011. LNCS, vol.\u00a06845, pp. 605\u2013615. Springer, Heidelberg (2011)"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1007\/978-3-642-39206-1_46","volume-title":"Automata, Languages, and Programming","author":"B. Hemenway","year":"2013","unstructured":"Hemenway, B., Ostrovsky, R., Wootters, M.: Local correctability of expander codes. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 540\u2013551. Springer, Heidelberg (2013)"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Juels, A., Kaliski, B.: Pors: proofs of retrievability for large files. In: Proceedings of the 2007 ACM Conference on Computer and Communications Security, pp. 584\u2013597 (2007)","DOI":"10.1145\/1315245.1315317"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Kopparty, S., Saraf, S., Yekhanin, S.: High-rate codes with sublinear-time decoding. In: STOC, pp. 167\u2013176 (2011)","DOI":"10.1145\/1993636.1993660"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious ram and a new balancing scheme. In: SODA, pp. 143\u2013156 (2012)","DOI":"10.1137\/1.9781611973099.13"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Naor, M., Rothblum, G.N.: The complexity of online memory checking. In: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, pp. 573\u2013584 (2005)","DOI":"10.1109\/SFCS.2005.71"},{"key":"21_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/0-387-34805-0_55","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"R. Ostrovsky","year":"1990","unstructured":"Ostrovsky, R.: An efficient software protection scheme. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 610\u2013611. Springer, Heidelberg (1990)"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: Efficient computation on oblivious rams. In: Ortiz, H. (ed.) STOC, pp. 514\u2013523. ACM (1990)","DOI":"10.1145\/100216.100289"},{"key":"21_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-540-73420-8_35","volume-title":"Automata, Languages and Programming","author":"R. Ostrovsky","year":"2007","unstructured":"Ostrovsky, R., Pandey, O., Sahai, A.: Private locally decodable codes. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 387\u2013398. Springer, Heidelberg (2007)"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-642-14623-7_27","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"B. Pinkas","year":"2010","unstructured":"Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 502\u2013519. Springer, Heidelberg (2010)"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Schulman, L.J.: Communication on noisy channels: A coding theorem for computation. In: 33rd Annual Symposium on Foundations of Computer Science, FOCS, pp. 724\u2013733 (1992)","DOI":"10.1109\/SFCS.1992.267778"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Schulman, L.J.: Deterministic coding for interactive communication. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC, pp. 747\u2013756 (1993)","DOI":"10.1145\/167088.167279"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-540-89255-7_7","volume-title":"Advances in Cryptology - ASIACRYPT 2008","author":"H. Shacham","year":"2008","unstructured":"Shacham, H., Waters, B.: Compact proofs of retrievability. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol.\u00a05350, pp. 90\u2013107. Springer, Heidelberg (2008)"},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC, pp. 388\u2013397 (1995)","DOI":"10.1145\/225058.225165"},{"key":"21_CR27","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego"},{"issue":"3","key":"21_CR28","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1561\/0400000030","volume":"6","author":"S. Yekhanin","year":"2012","unstructured":"Yekhanin, S.: Locally decodable codes. Foundations and Trends in Theoretical Computer Science\u00a06(3), 139\u2013255 (2012)","journal-title":"Foundations and Trends in Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54242-8_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T19:09:04Z","timestamp":1746126544000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54242-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642542411","9783642542428"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54242-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}