Speaker:	David Cash (Georgia Tech)
Date/Time:	Thu 28.06.07, 14.00 - 14.30 h
Location:	Room H220 in the NIKHEF building (just next to the CWI building), CWI Amsterdam
Abstract:	There is currently a significant gap between the design goals for hash functions and actual properties needed by cryptographers, the formal methods community, and information security practitioners. This is best illustrated by the widespread adoption of the Random Oracle Model, a heuristic methodology for analyzing protocols that assumes that a hash function is an ideal random function. In this work we take a step towards rectifying this situation by introducing the notion of non-malleable hash functions. Briefly stated, non-malleability guarantees that, given the hash H(m) of some message m, an adversary should not be able to produce the hash H(m*) for some m* that is meaningfully related to m. Non-Malleability has proven to be a crucial property of primitives like encryption, commitments, and zero-knowledge proofs, but its application to hash functions has not been treated formally. Interestingly, the typical properties of hash functions, like public verifiability and length compression, prevent us from directly translating the definition of non-malleability from other contexts. In this talk we will give some motivating examples for the study of non-malleability, and we will describe some attempts at defining non-malleable hash functions on the way to developing a meaningful, achievable definition. Finally we will give a proof-of-concept construction for our definition and discuss its application to message authentication codes. This is joint work with Alexandra Boldyreva, Marc Fischlin, and Bogdan Warinschi.