Abstract
We introduce the notion of locally updatable and locally decodable codes (LULDCs). In addition to having low decode locality, such codes allow us to update a codeword (of a message) to a codeword of a different message, by rewriting just a few symbols. While, intuitively, updatability and error-correction seem to be contrasting goals, we show that for a suitable, yet meaningful, metric (which we call the Prefix Hamming metric), one can construct such codes. Informally, the Prefix Hamming metric allows the adversary to arbitrarily corrupt bits of the codeword subject to one constraint – he does not corrupt more than a δ fraction (for some constant δ) of the t “most-recently changed” bits of the codeword (for all 1 ≤ t ≤ n, where n is the length of the codeword).
Our results are as follows. First, we construct binary LULDCs for messages in {0, 1}k with constant rate, update locality of \(\mathcal{O}(\log^2 k)\), and read locality of \(\mathcal{O}(k^\epsilon)\) for any constant ε < 1. Next, we consider the case where the encoder and decoder share a secret state and the adversary is computationally bounded. Here too, we obtain local updatability and decodability for the Prefix Hamming metric. Furthermore, we also ensure that the local decoding algorithm never outputs an incorrect message – even when the adversary can corrupt an arbitrary number of bits of the codeword. We call such codes locally updatable locally decodable-detectable codes (LULDDCs) and obtain dramatic improvements in the parameters (over the information-theoretic setting). Our codes have constant rate, an update locality of \(\mathcal{O}(\log^2 k)\) and a read locality of \(\mathcal{O}(\lambda \log ^2k)\), where λ is the security parameter.
Finally, we show how our techniques apply to the setting of dynamic proofs of retrievability (DPoR) and present a construction of this primitive with better parameters than existing constructions. In particular, we construct a DPoR scheme with linear storage, \(\mathcal{O}(\log^2 k)\) write complexity, and \(\mathcal{O}(\lambda \log k)\) read and audit complexity.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ateniese, G., Kamara, S., Katz, J.: Proofs of storage from homomorphic identification protocols. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 319–333. Springer, Heidelberg (2009)
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–54 (2009)
Cash, D., Küpçü, A., Wichs, D.: Dynamic proofs of retrievability via oblivious RAM. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 279–295. Springer, Heidelberg (2013)
Chandran, N., Kanukurthi, B., Ostrovsky, R.: Locally updatable and locally decodable codes. Cryptology ePrint Archive, Report 2013/520 (2013), http://eprint.iacr.org/
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–794 (2010)
Chee, Y.M., Feng, T., Ling, S., Wang, H., Zhang, L.F.: Query-efficient locally decodable codes of subexponential length. Computational Complexity 22(1), 159–189 (2013)
Dodis, Y., Vadhan, S.P., Wichs, D.: Proofs of retrievability via hardness amplification. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 109–127. Springer, Heidelberg (2009)
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–44 (2009)
Goldreich, O.: Towards a theory of software protection and simulation by oblivious rams. In: STOC, pp. 182–194 (1987)
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. 6756, pp. 576–587. Springer, Heidelberg (2011)
Guo, A., Kopparty, S., Sudan, M.: New affine-invariant codes from lifting. In: Innovations in Theoretical Computer Science, ITCS, pp. 529–540 (2013)
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. 6845, pp. 605–615. Springer, Heidelberg (2011)
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. 7965, pp. 540–551. Springer, Heidelberg (2013)
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–597 (2007)
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–86 (2000)
Kopparty, S., Saraf, S., Yekhanin, S.: High-rate codes with sublinear-time decoding. In: STOC, pp. 167–176 (2011)
Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious ram and a new balancing scheme. In: SODA, pp. 143–156 (2012)
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–584 (2005)
Ostrovsky, R.: An efficient software protection scheme. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 610–611. Springer, Heidelberg (1990)
Ostrovsky, R.: Efficient computation on oblivious rams. In: Ortiz, H. (ed.) STOC, pp. 514–523. ACM (1990)
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)
Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 502–519. Springer, Heidelberg (2010)
Schulman, L.J.: Communication on noisy channels: A coding theorem for computation. In: 33rd Annual Symposium on Foundations of Computer Science, FOCS, pp. 724–733 (1992)
Schulman, L.J.: Deterministic coding for interactive communication. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC, pp. 747–756 (1993)
Shacham, H., Waters, B.: Compact proofs of retrievability. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 90–107. Springer, Heidelberg (2008)
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–397 (1995)
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
Yekhanin, S.: Locally decodable codes. Foundations and Trends in Theoretical Computer Science 6(3), 139–255 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 International Association for Cryptologic Research
About this paper
Cite this paper
Chandran, N., Kanukurthi, B., Ostrovsky, R. (2014). Locally Updatable and Locally Decodable Codes. In: Lindell, Y. (eds) Theory of Cryptography. TCC 2014. Lecture Notes in Computer Science, vol 8349. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54242-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-54242-8_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54241-1
Online ISBN: 978-3-642-54242-8
eBook Packages: Computer ScienceComputer Science (R0)