International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Locally Decodable and Updatable Non-malleable Codes and Their Applications

Authors:
Dana Dachman-Soled
Feng-Hao Liu
Elaine Shi
Hong-Sheng Zhou
Download:
DOI: 10.1007/s00145-018-9306-z
Search ePrint
Search Google
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 threefold: 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.
BibTeX
@article{jofc-2020-30107,
  title={Locally Decodable and Updatable Non-malleable Codes and Their Applications},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={33},
  pages={319-355},
  doi={10.1007/s00145-018-9306-z},
  author={Dana Dachman-Soled and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou},
  year=2020
}