as solving the discrete logarithm problem in a finite group . Knapsack-based hash functions - A family of hash functions based on the Knapsack problem. The Zémor-Tillich hash function - A family of hash functions that rely on the arithmetic of the group of matrices SL2. Finding collisions is at least as difficult as finding factorization of certain elements in this group. This is supposed to be hard, at least PSPACE-complete. For this hash, an attack was eventually discovered with a time complexity close to . This beat by far the birthday bound and ideal pre-image complexities which are and for the Zémor-Tillich hash function. As the attacks include a birthday search in a reduced set of size they indeed do not destroy the idea of provable security or invalidate the scheme but rather suggest that the initial parameters were too small. Hash functions from Sigma Protocols - there exists a general way of constructing a provably secure hash, specifically from any (suitable) sigma protocol. A faster version of VSH (called VSH*) could be obtained in this way. References Cryptographic hash functions