Information-theoretic Local Non-malleable Codes and their Applications

Abstract. Error correcting codes, though powerful, are only applica-ble in scenarios where the adversarial channel does not introduce “too many ” errors into the codewords. Yet, the question of having guarantees even in the face of many errors is well-motivated. Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), address precisely this question. Such codes guarantee that even if an adversary completely over-writes the codeword, he cannot transform it into a code-word for a related message. Not only is this a creative solution to the problem mentioned above, it is also a very meaningful one. Indeed, non-malleable codes have inspired a rich body of theoretical constructions as well as applications to tamper-resilient cryptography, CCA2 encryption schemes and so on. Another remarkable variant of error correcting codes were introduced by Katz and Trevisan (STOC 2000) when they explored the question of de-coding “locally”. Locally decodable codes are coding schemes which hav