A method and an apparatus that provides a hard problem based hashing mechanism to improve security of hash functions are described. The hashing mechanism can include a custom padding and/or a post processing to a hashed value strengthened via operations specifying a hard problem. In one embodiment, a new hash function may be provided or defined directly without introducing or relying on existing hash functions to embed security features based on this hard problem. The new hash functions can be used in usual constructions implying hash functions. For example, the standard HMAC construction could be applied on these hash functions, standard signature algorithms or authentication protocol, etc.