Security of cryptographic hash functions: Difference between revisions

Revision as of 19:26, 13 June 2011

Revision as of 16:28, 19 March 2012

Line 1:

In [[cryptography]], [[cryptographic hash functions]] can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, [[Computational complexity theory|complexity theory]] and [[Reduction (complexity)|formal reduction]]. These functions are called '''Provably Secure Cryptographic Hash Functions'''. However this does not mean that such a function could not be broken. To construct them is very difficult and only a few examples were introduced. The practical use is limited.

In the second category are functions that are not based on mathematical problems but on an ad hoc basis, where the bits of the message are mixed to produce the hash. They are then believed to be hard to break, but no such formal proof is given. Almost all widely-spread hash functions fall in this category. Some of these functions are already broken and are no longer in use.

== Types of Security of Hash Functions ==

Line 60:

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

* [[Chaum, van Heijst, Pfitzmann hash function]] - A compression function where finding collisions is as hard as solving the [[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 pre-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 destroy 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.

Line 72:

{{Reflist}}

{{CryptoCryptography navbox | hash}}

[[Category:Cryptographic hash functions]]