Security of cryptographic hash functions: Difference between revisions

Revision as of 17:55, 2 March 2010

Revision as of 15:30, 10 March 2010

Line 52:

But the algorithm is quite inefficient because it requires on average 1.5 multiplications modulo ''n'' per message-bit.

=== More practical Provablyprovably Securesecure Hashhash Functionsfunctions ===

* [[Very smooth hash|VSH - Very Smooth Hash function]] - a provably secure collision-resistant hash function assuming the hardness of finding nontrivial modular square roots modulo composite number <math>n</math> (this is proven to be as hard as [[Integer factorization|factoring]] <math>n</math>).

* [[MuHASH]]

* [[Elliptic curve only hash|ECOH - Elliptic Curve Only hash function]] - based on the concept of Elliptic curves, Subset Sum Problem and summation of polynomials. The security proof of the collision resistance was based on weakendweakened assumptions and eventually a second pre-image attack was found.

* [[Fast Syndrome Based Hash|FSB - Fast Syndrome-Based hash function]] - it can be proven that breaking FSB is at least as difficult as solving a certain NP-complete problem known as Regular Syndrome Decoding.

* [[SWIFFT]] - SWIFFT is based on the [[Fast fourierFourier transform]] and is provably collision resistant, under a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/ideal [[lattice]]s.

* [[Chaum, van Heijst, Pfitzmann hash function]] - A compression function where finding collisions is as hard as finding a [[discrete logarithm|discrete logarithm problem]] in a finite group <math>F_{2p+1}</math>.

* [[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 [[Special linear group|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 <math>2^{n/2}</math>. This beat by far the birthday bound and ideal preimagepre-image complexities which are <math>2^{3n/2}</math> and <math>2^{3n}</math> for the Zémor-Tillich hash function. As the attacks include a birthday search in a reduced set of size <math>2n</math> they indeed do not distroydestroy the idea of provable security of invalidate the scheme but rather suggest that the initial parameters were too small. <ref>{{Citation

| last1 = Petit | first1 = C.

| last2 = Quisquater | first2 = J.-J.