Paper 2014/173

Continuous Non-malleable Codes

Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen, and Daniele Venturi

Abstract

Non-malleable codes are a natural relaxation of error correcting/detecting codes that have useful applications in the context of tamper resilient cryptography. Informally, a code is non-malleable if an adversary trying to tamper with an encoding of a given message can only leave it unchanged or modify it to the encoding of a completely unrelated value. This paper introduces an extension of the standard non-malleability security notion – so-called continuous non-malleability – where we allow the adversary to tamper continuously with an encoding. This is in contrast to the standard notion of non-malleable codes where the adversary only is allowed to tamper a single time with an encoding. We show how to construct continuous non-malleable codes in the common split-state model where an encoding consist of two parts and the tampering can be arbitrary but has to be independent with both parts. Our main contributions are outlined below: 1. We propose a new uniqueness requirement of split-state codes which states that it is computationally hard to find two codewords C = (X0;X1) and C0 = (X0;X1') such that both codewords are valid, but X0 is the same in both C and C0. A simple attack shows that uniqueness is necessary to achieve continuous non-malleability in the split-state model. Moreover, we illustrate that none of the existing constructions satisfies our uniqueness property and hence is not secure in the continuous setting. 2. We construct a split-state code satisfying continuous non-malleability. Our scheme is based on the inner product function, collision-resistant hashing and non-interactive zero-knowledge proofs of knowledge and requires an untamperable common reference string. 3. We apply continuous non-malleable codes to protect arbitrary cryptographic primitives against tampering attacks. Previous applications of non-malleable codes in this setting required to perfectly erase the entire memory after each execution and and required the adversary to be restricted in memory. We show that continuous non-malleable codes avoid these restrictions.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2014
Keywords
non-malleable codessplit-statetamper-resilience
Contact author(s)
pratyay85 @ gmail com
History
2014-03-04: received
Short URL
https://ia.cr/2014/173
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/173,
      author = {Sebastian Faust and Pratyay Mukherjee and Jesper Buus Nielsen and Daniele Venturi},
      title = {Continuous Non-malleable Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2014/173},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/173}},
      url = {https://eprint.iacr.org/2014/173}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.