CWI Cryptology Group

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.

Abstract: We present as-strong-as-possible definitions of privacy, and constructions achieving them, for public-key encryption schemes where the encryption algorithm is deterministic. We obtain as a consequence database encryption methods that permit fast (ie. sub-linear, and in fact logarithmic, time) search while provably providing privacy that is as strong as possible subject to this fast search constraint. One of our constructs, called RSA-DOAEP, has the added feature of being length preserving, so that it is the first example of a public-key cipher. We generalize this to obtain a notion of efficiently-searchable encryption schemes which permit more flexible privacy to search-time trade-offs via a technique called bucketization. Our results answer much-asked questions in the database community and provide foundations for work done there.
Joint work with Mihir Bellare (UCSD) and Alexandra Boldyreva (Georgia Tech)