Paper 2014/663

Locally Decodable and Updatable Non-Malleable Codes and Their Applications

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


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.

Available format(s)
Publication info
Preprint. Minor revision.
non-malleable codestamper-resilienceRAM computation
Contact author(s)
danadach @ ece umd edu
2014-08-28: received
Short URL
Creative Commons Attribution


      author = {Dana Dachman-Soled and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou},
      title = {Locally Decodable and Updatable Non-Malleable Codes and Their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2014/663},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.