Locally Updatable and Locally Decodable Codes
Nishanth Chandran, Bhavana Kanukurthi, 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 codeword of a different message, by reqriting just a few symbols.While,intuitively,updatability and error−correction seem to be contrasting goals, we show that for a suitable, yet meaningful, metric (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}kwith constant rate, update locality of ο(log2k), and read locality ofο(Kε for any constant ε< 1.Next, we consider the case where the encoder and decoder share a secret state and 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 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 ο(log2k) and a read locality of ο(λlog2k),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 liner storage, ο(log2k) write complexity, and ο(λlogk) read and audit complexity.
comment: CRYOPTO 2015 PP: 573−590
Fetch PDF file of the paper
| Back to Publications List |