International Association
for Cryptologic Research

We introduce the notion of locally updatable and locally decodable codes (LULDCs). 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 corrupt an arbitrary (constant fraction of) bits of the codeword subject to the constraint that he does not corrupt more than a $\\delta$ fraction of the $t$ ``most-recently changed\" bits of the codeword (for all $1\\leq t\\leq n$, where $n$ is the length of the codeword).

We first construct binary LULDCs for messages in $\\{0,1\\}^{k}$ with constant rate, update locality of $\\bigo(\\log^2 k)$, and read locality of $\\bigo(k^\\epsilon)$ for any constant $\\epsilon