Cryptology ePrint Archive: Report 2014/663

Locally Decodable and Updatable Non-Malleable Codes and Their Applications

Dana Dachman-Soled and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou

Abstract: Non-malleable codes, introduced as a relaxation of error-correcting codes by Dziembowski, Pietrzak and Wichs (ICS '10), provide the security guarantee that the message contained in a tampered codeword is either the same as the original message or is set to an unrelated value. Various applications of non-malleable codes have been discovered, and one of the most significant applications among these is the connection with tamper-resilient cryptography. There is a large body of work considering security against various classes of tampering functions, as well as non-malleable codes with enhanced features such as leakage resilience.

In this work, we propose combining the concepts of non-malleability, leakage resilience, and locality in a coding scheme. The contribution of this work is three-fold:

1. As a conceptual contribution, we define a new notion of locally decodable and updatable non-malleable code that combines the above properties.

2. We present two simple and efficient constructions achieving our new notion with different levels of security.

3. We present an important application of our new tool--securing RAM computation against memory tampering and leakage attacks. This is analogous to the usage of traditional non-malleable codes to secure implementations in the circuit model against memory tampering and leakage attacks.

Category / Keywords: foundations / non-malleable codes, tamper-resilience, RAM computation

Date: received 25 Aug 2014

Contact author: danadach at ece umd edu

Available format(s): PDF | BibTeX Citation

Version: 20140828:222337 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]