The importance of hash functions for protecting the authenticity of information is demonstrated. Applications include integrity protection, conventional message authentication and digital signatures. An overview is given of the study of basic building blocks of cryptographic hash functions leads to the study of the cryptographic properties of Boolean functions and the information theoretic approach to authentication is described. An overview is given of the complexity theoretic definitions and constructions .New criteria are defined and functions satisfying new and existing criteria are studied.