Paper 2013/520
Locally Updatable and Locally Decodable Codes
Nishanth Chandran, Bhavana Kanukurthi, and Rafail Ostrovsky
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
Note: There were minor errors in the parameters stated in the previous version.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in TCC 2014
- Contact author(s)
- bhavanak @ cs bu edu
- History
- 2014-03-10: revised
- 2013-08-22: received
- See all versions
- Short URL
- https://ia.cr/2013/520
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/520, author = {Nishanth Chandran and Bhavana Kanukurthi and Rafail Ostrovsky}, title = {Locally Updatable and Locally Decodable Codes}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/520}, year = {2013}, url = {https://eprint.iacr.org/2013/520} }