Expedient Non-malleability notions for hash functions

Baecher P, Fischlin M, Schröder D (2011)


Publication Status: Published

Publication Type: Authored book, Volume of book series

Publication year: 2011

Series: Topics in Cryptology - CT-RSA 2011

Pages Range: 268-283

Event location: San Francisco, CA

ISBN: 9783642190735

DOI: 10.1007/978-3-642-19074-2_18

Abstract

Non-malleability of a cryptographic primitive is a fundamental security property which ensures some sort of independence of cryptographic values. The notion has been extensively studied for commitments, encryption and zero-knowledge proofs, but it was not until recently that the notion-and its peculiarities-have been considered for hash functions by Boldyreva et al. (Asiacrypt 2009). They give a simulation-based definition, basically saying that for any adversary mauling hash values into related ones there is a simulator which is as successful in producing such hash values, even when not seeing the original hash values. Their notion, although following previous approaches to nonmalleability, is nonetheless quite unwieldy; it is hard to achieve and, due to the existential quantification over the simulator, hard to falsify. We also note that finding an equivalent indistinguishability-based notion is still open. Here we take a different, more handy approach to non-malleability of hash functions. Our definition avoids simulators completely and rather asks the adversary to maul the hash value and to also specify a transformation φ of the pre-image, taken from a fixed class Φ of admissible transformations. These transformations are usually determined by group operations and include such cases such as exclusive-ors (i.e., bit flips) and modular additions. We then simply demand that the probability of succeeding is negligible, as long as the original pre-image carries enough entropy. We continue to show that our notion is useful by proving that, for example, the strengthened Merkle-Damgård transformation meets our notion for the case of bit flips, assuming an ideal compression function. We also improve over the security result by Boldyreva et al., showing that our notion of non-malleability suffices for the security of the Bellare-Rogaway encryption scheme. © 2011 Springer-Verlag Berlin Heidelberg.

Authors with CRIS profile

How to cite

APA:

Baecher, P., Fischlin, M., & Schröder, D. (2011). Expedient Non-malleability notions for hash functions.

MLA:

Baecher, Paul, Marc Fischlin, and Dominique Schröder. Expedient Non-malleability notions for hash functions. 2011.

BibTeX: Download