Paper 2009/065

Foundations of Non-Malleable Hash and One-Way Functions

Alexandra Boldyreva, David Cash, Marc Fischlin, and Bogdan Warinschi


Non-malleability is an interesting and useful property which ensures that a cryptographic protocol preserves the independence of the underlying values: given for example an encryption Enc(m) of some unknown message m, it should be hard to transform this ciphertext into some encryption Enc(m*) of a related message m*. This notion has been studied extensively for primitives like encryption, commitments and zero-knowledge. Non-malleability of one-way functions and hash functions has surfaced as a crucial property in several recent results, but it has not undergone a comprehensive treatment so far. In this paper we initiate the study of such non-malleable functions. We start with the design of an appropriate security definition. We then show that non-malleability for hash and one-way functions can be achieved, via a theoretical construction that uses perfectly one-way hash functions and simulation-sound non-interactive zero-knowledge proofs of knowledge (NIZKPoK). We also discuss the complexity of non-malleable hash and one-way functions. Specifically, we give a black-box based separation of non-malleable functions from one-way permutations (which our construction bypasses due to the 'non-black-box' NIZKPoK). We exemplify the usefulness of our definition in cryptographic applications by showing that non-malleability is necessary and sufficient to securely replace one of the two random oracles in the IND-CCA encryption scheme by Bellare and Rogaway, and to improve the security of client-server puzzles.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Non-malleabilityhash functionperfect one-wayness.
Contact author(s)
marc fischlin @ gmail com
2009-02-10: received
Short URL
Creative Commons Attribution


      author = {Alexandra Boldyreva and David Cash and Marc Fischlin and Bogdan Warinschi},
      title = {Foundations of Non-Malleable Hash and One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2009/065},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.