Foundations of Non-Malleable Hash and One-Way Functions

Alexandra Boldyreva, David Cash, Marc Fischlin, Bogdan Warinschi

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

29 Citations (Scopus)


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 \new{4}{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 based on trapdoor permutations). We exemplify the usefulness of our definition in cryptographic applications by showing that (some variant of) 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.
Translated title of the contributionFoundations of Non-Malleable Hash and One-Way Functions
Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2009
PublisherSpringer Berlin Heidelberg
Publication statusPublished - 2009

Bibliographical note

Other page information: -
Conference Proceedings/Title of Journal: Advances in Cryptology - Asiacrypt 2009
Other identifier: 2001103


Dive into the research topics of 'Foundations of Non-Malleable Hash and One-Way Functions'. Together they form a unique fingerprint.

Cite this